research-article

Improving service differentiation in IP networks through dual topology routing

Authors:

Shu TaoAuthors Info & Claims

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

Article No.: 16, Pages 1 - 12

https://doi.org/10.1145/1364654.1364675

Published: 10 December 2007 Publication History

Abstract

The convergence on IP of a wide variety of traffic types has strengthened the need for service differentiation. Service differentiation relies on two equally important components: (i) resource allocation, i.e., what resources does a given service class have access to; and (ii) contention resolution, i.e., how is access to shared resources arbitrated between services classes. The latter has been well studied with numerous mechanisms, e.g., scheduling and buffer management, supporting it in modern routers. In contrast, relatively few studies exist on the former, and in particular on the impact of routing that determines the resources a given service class is assigned to. This is the focus of the paper, which seeks to investigate how routing influences a network's ability to efficiently support different service classes. Of particular interest is the extent to which the ability to route service classes separately is beneficial. This question is explored for a base configuration involving two classes with either similar or entirely different service objectives (cost functions). The paper's contributions are in demonstrating and quantifying the benefits that the added flexibility of different (dual) routing affords, and in developing an efficient heuristic for computing jointly optimal routing solutions. The former can motivate the deployment of newly standardized multi-topology routing (MTR) functionality. The latter is a key enabler for the effective use of such capability.

References

[1]

P. Psenak, S. Mirtorabi, A. Roy, L. Nguyen, and P. Pillay-Esnault, "Multi-topology (MT) routing in OSPF," IETF RFC 4915, June 2007.

[2]

B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, 2000.

[3]

M. Ericsson, M. Resende, and P. Pardalos, "A genetic algorithm for the weight setting problem in OSPF routing," J. of Combinatorial Optimization, vol. 6, pp. 299--333, 2002.

[4]

L. Buriol, M. Resende, C. Ribeiro, and M. Thorup, "A memetic algorithm for OSPF routing," in Proc. 6th INFORMS Telecom, 2002.

[5]

A. Nucci, S. Bhattacharyya, N. Taft, and C. Diot, "IGP link weight assignment for operational Tier-1 backbones," IEEE/ACM Transactions on Networking, vol. 15, no. 4, pp. 789--802, August 2007.

Digital Library

[6]

S. Balon and G. Leduc, "Dividing the traffic matrix to approach optimal traffic engineering," in Proc. IEEE ICON, 2006.

[7]

G. Apostolopoulos, "Using multiple topologies for IP-only protection against network failures: A routing performance perspective," ICS-FORTH, Greece, Tech. Rep., 2006.

[8]

S. Gjessing and O. Norway, "Implementation of two resilience mechanisms using multi topology routing and stub routers," in Proc. AICT-ICIW, 2006.

Digital Library

[9]

A. Kvalbein, A. F. Hansen, T. Cicic, S. Gjessing, and O. Lysne, "Fast IP network recovery using multiple routing configurations," in Proc. IEEE INFOCOM, 2006.

[10]

W. C. Lee, M. G. Hluchyj, and P. A. Humblet, "Routing subject to quality of service constraints in integrated communication networks," IEEE Network, vol. 9, no. 4, pp. 46--55, Jul/Aug 1995.

Digital Library

[11]

E. Crawley, B. R. R. Nair, and H. Sandick, "A framework for QoS-based routing in integrated service networks," IETF RFC 2386, 1998.

Digital Library

[12]

J. Wang and K. Nahrstedt, "Hop-by-hop routing algorithms for premium traffic," ACM SIGCOMM Computer Communications Review, vol. 32, no. 5, pp. 73--88, November 2002.

Digital Library

[13]

R. Guérin and A. Orda, "QoS-based routing in networks with inaccurate information: Theory and algorithms," in Proc. IEEE INFOCOM, 1997.

Digital Library

[14]

Q. Ma and P. Steenkiste, "Supporting dynamic inter-class resource sharing: A multi-class QoS routing algorithm," in Proc. IEEE INFOCOM, 1999.

[15]

S. Chen and K. Nahrstedt, "An overview of quality of service routing for next-generation high-speed networks: Problems and solutions," IEEE Network, vol. 12, no. 6, pp. 64--79, Nov/Dec 1998.

Digital Library

[16]

D. Mitra and K. G. Ramakrishnan, "Techniques for traffic engineering of multiservice, multi-priority networks," Bell Labs Technical Journal, vol. 6, no. 1, pp. 139--151, 2001.

[17]

S. L. Spitler and D. C. Lee, "Integrating effective-bandwidth-based QoS routing and best effort routing," in Proc. IEEE INFOCOM, 2003.

[18]

S. Balon, F. Skivée, and G. Leduc, "How well do traffic engineering objective functions meet TE requirements," in Proc. IFIP Networking, 2006.

Digital Library

[19]

B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world," IEEE Journal on Selected Areas in Communications, vol. 20, no. 4, pp. 756--767, May 2002.

Digital Library

[20]

S. Boettcher and A. G. Percus, "Nature's way of optimizing," Artificial Intelligence, vol. 119, pp. 275--286, May 2000.

Digital Library

[21]

A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509--512, October 1999.

[22]

M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the Internet topology," in Proc. ACM SIGCOMM, 1999.

Digital Library

[23]

A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot, "Traffic matrix estimation: Existing techniques compared and new directions," in Proc. ACM SIGCOMM, 2002.

Digital Library

[24]

S. Bhattacharyya, N. Taft, J. Jetcheva, and C. Diot, "POP-level and access-link-level traffic dynamics in a Tier-1 POP," in Proc. ACM IMW, 2001.

Digital Library

[25]

K.-W. Kwong, R. Guérin, A. Shaikh, and S. Tao, "Improving service differentiation in IP networks through dual topology routing," University of Pennsylvania, Tech. Rep., June 2007. {Online}. Available: http://einstein.seas.upenn.edu/mnlab

Cited By

Li KFan P(2019)A generalized service deployment framework for OSPF networks using multi‐topology routing: Modeling and methodologyInternational Journal of Communication Systems10.1002/dac.397832:14Online publication date: 18-Jul-2019
https://doi.org/10.1002/dac.3978
Lee YNarasimha Reddy A(2012)Constructing disjoint paths for failure recovery and multipath routingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2011.10.01556:2(719-730)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.comnet.2011.10.015
Kwong KGao LGuérin RZhang Z(2011)On the feasibility and efficacy of protection routing in IP networksIEEE/ACM Transactions on Networking10.1109/TNET.2011.212391619:5(1543-1556)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1109/TNET.2011.2123916
Show More Cited By

Recommendations

Quality-of-service routing in IP networks

Multimedia applications such as video-conferencing, telemedicine, HDTV, etc. have very stringent quality-of-service (QoS) demands and require a connection-oriented service. For these applications, a path satisfying their requirements in terms of ...
Dynamics of hot-potato routing in IP networks

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Dynamics of hot-potato routing in IP networks
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

December 2007

448 pages

ISBN:9781595937704

DOI:10.1145/1364654

General Chairs:
Jim Kurose
University of Massachusetts
,
Henning Schulzrinne
Columbia University

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Alcatel-Lucent
SIGCOMM: ACM Special Interest Group on Data Communication
Thomson
CISCO
IMDEA
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Division of Computer and Network Systems

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
186
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li KFan P(2019)A generalized service deployment framework for OSPF networks using multi‐topology routing: Modeling and methodologyInternational Journal of Communication Systems10.1002/dac.397832:14Online publication date: 18-Jul-2019
https://doi.org/10.1002/dac.3978
Lee YNarasimha Reddy A(2012)Constructing disjoint paths for failure recovery and multipath routingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2011.10.01556:2(719-730)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.comnet.2011.10.015
Kwong KGao LGuérin RZhang Z(2011)On the feasibility and efficacy of protection routing in IP networksIEEE/ACM Transactions on Networking10.1109/TNET.2011.212391619:5(1543-1556)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1109/TNET.2011.2123916
Kwong KGao LGuérin RZhang Z(2010)On the feasibility and efficacy of protection routing in IP networksProceedings of the 29th conference on Information communications10.5555/1833515.1833699(1235-1243)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833699
Kwong KGuérin RShaikh ATao S(2010)Balancing performance, robustness and flexibility in routing systemsIEEE Transactions on Network and Service Management10.1109/TNSM.2010.1009.I9P03557:3(186-199)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1109/TNSM.2010.1009.I9P0355
Kwong KGao LGuerin RZhang Z(2010)On the Feasibility and Efficacy of Protection Routing in IP Networks2010 Proceedings IEEE INFOCOM10.1109/INFCOM.2010.5461923(1-9)Online publication date: Mar-2010
https://doi.org/10.1109/INFCOM.2010.5461923
Lee YReddy A(2010)Disjoint Multi-Path Routing and Failure Recovery2010 IEEE International Conference on Communications10.1109/ICC.2010.5502237(1-6)Online publication date: May-2010
https://doi.org/10.1109/ICC.2010.5502237
Lee JLee SSharma PChoi S(2010)Understanding the Effectiveness of a Co-Located Wireless Channel Monitoring Surrogate System2010 IEEE International Conference on Communications10.1109/ICC.2010.5502051(1-6)Online publication date: May-2010
https://doi.org/10.1109/ICC.2010.5502051
Menth MHartmann MMartin Ričić TKvalbein A(2010)Loop-free alternates and not-via addressesComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2009.10.02054:8(1300-1315)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.comnet.2009.10.020
Luan HKwong KHei XTsang D(2009)Adaptive topology formation for peer-to-peer video streamingPeer-to-Peer Networking and Applications10.1007/s12083-009-0048-43:3(186-207)Online publication date: 28-May-2009
https://doi.org/10.1007/s12083-009-0048-4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten