Anees Shaikh
Jennifer Rexford
ABSTRACT
Internet service providers face a daunting challenge in provisioning network resources, due to the rapid growth of the Internet and wide fluctuations in the underlying traffic patterns. The ability of dynamic routing to circumvent congested links and improve application performance makes it a valuable traffic engineering tool. However, deployment of load-sensitive routing is hampered by the overheads imposed by link-state update propagation, path selection, and signaling. Under reasonable protocol and computational overheads, traditional approaches to load-sensitive routing of IP traffic are ineffective, and can introduce significant route flapping, since paths are selected based on out-of-date link-state information. Although stability is improved by performing load-sensitive routing at the flow level, flapping still occurs, because most IP flows have a short duration relative to the desired frequency of link-state updates. To address the efficiency and stability challenges of load-sensitive routing, we introduce a new hybrid approach that performs dynamic routing of long-lived flows, while forwarding short-lived flows on static preprovisioned paths. By relating the detection of long-lived flows to the timescale of link-state update messages in the routing protocol, route stability is considerably improved. Through simulation experiments using a one-week ISP packet trace, we show that our hybrid approach significantly outperforms traditional static and dynamic routing schemes, by reacting to fluctuations in network load without introducing route flapping.
- 1.A. Khanna and J. ginky, "The revised ARPANET routing metric," in Proceedings of A CM $IGCOMM, pp. 45-56, September 1989. Google Scholar
Digital Library
- 2.g. Wang and J. Crowcroft, "Analysis. of shortest-path routing algorithms in a dynamic network environment," A CM Computer Communication Review, vol. 22, no. 2, pp. 63-71, April 1992. Google ScholarDigital Library
- 3.W. C. Lee, M. G. Hluchyj, and P. A. Humbler, "Routing subject to quality of service constraints in integrated communication networks," IEEE Network Magazine, pp. 46-55, July/August 1995. Google ScholarDigital Library
- 4.Z. Wang and J. Crowcroft, "Quality-of-service routing for supporting multimedia applications," IEEE Journal on Selected Areas in Communications, vol. 14, no. 7, pp. 1228-1234, September 1996. Google ScholarDigital Library
- 5.E. Crawley, R. N air, B. Rajagopalan, and H. Sandick. A Framework .for QoS-based Routing in the Internet. Request for Comments (RFC 2386), August 1998. Google ScholarDigital Library
- 6.S. Chen and K. Nahrstedt, "An overview of quality of service routing for next-generation high-speed networks: Problems and solutions," IEEE Network Magazine, pp. 64-79, November/December 1998. Google ScholarDigital Library
- 7.PNNI Specification Working Group, Private Network- Network Interface Specification Version 1.0, ATM Forum, March 1996.Google Scholar
- 8.Z. Zhang, C. Sanchez, B. Salkewicz, and E. S. Crawley. Quality of Service Extensions to OSPF or Quality o/Service Path First Routing (QOSPF). Internet Draft (draft-zbang-qos-ospf-01.txt), work in progress, September 1997.Google Scholar
- 9.G. Apostolopoulos, R. Guerin, S. Kamat, A. Orda, A. Przygienda, and D. Williams. QoS Routing Mechanisms and OSPF Extensions. Internet Draft (draftguerin-qos-routing-ospf-05.txt), April 1999. Google ScholarDigital Library
- 10.G. Apostolopoulos, R. Guerin, S. Kamat, and S. Tripathi, "Quality of service based routing: A performance perspective," in Proceedings o/ A CM $IG- COMM, September 1998. Google ScholarDigital Library
- 11.A. Sheikh, 2. Rexford, and K. Shin, "Evaluating the overheads of source-directed quality-of-service routing," in Proceedings o/ IEEE International Conference on Network Protocols, October 1998. Google ScholarDigital Library
- 12.K. C. Claffy, H.-W. Braun, and G. C. Polyzos, "A parameterizable methodology for Internet traffic flow profiling," IEEE Journal on Selected Areas in Communications, vol. 13, no. 8, pp. 1481-1494, October 1995. Google ScholarDigital Library
- 13.M. E. Crovella and A. Bestavros, "Self-similarity in world wide web traffic: Evidence and possible causes," IEEE/A CM Transactions on Networking, vol. 5, no. 6, pp. 835-846, December 1997. Google ScholarDigital Library
- 14.K. Thompson, G. J. Miller, and R. Wilder, "Widearea internet traffic patterns and characteristics," IEEE Network Magazine, vol. 11, no. 6, pp. 10-23, November/December 1997. Google ScholarDigital Library
- 15.A. Feldmann, J. Rexford, and R. Caceres, "Efficient policies for carrying Web traffic over flow-switched networks," IEEE/ACM Transactions on Networking, pp. 673-685, December 1998. Google ScholarDigital Library
- 16.M. Harchol-Balter and A. Downey, "Exploiting process lifetime distributions for dynamic load balancing," A CM Transactions on Computer Systems, vol. 15, no. 3, pp. 253-285, August 1997. Google ScholarDigital Library
- 17.Y. Katsube, K. Nagami, S. Matsuzawa, and H. Esaki, "Internetworking based on cell switch router- architecture and protocol overview," Proceedings o/the IEEE, vol. 85, no. 12, pp. 1998-2006, December 1997.Google ScholarCross Ref
- 18.ATM Forum MPOA Sub-Working Group, Multi- Protocol over ATM Version 1.0 (AF-MPOA-O087.000), July 1997.Google Scholar
- 19.P. Newman, G. Minshall, and T. Lyon, "IP switching: ATM under IP," IEEE/A CM Transactions on Networking, vol. 6, no. 2, pp. 117-129, April 1998. Google ScholarDigital Library
- 20.S. Lin and N. McKeown, "A simulation study of IP switching," in Proceedings o/A CM SIGCOMM, pp. 15- 24, September 1997. Google ScholarDigital Library
- 21.I. Widjaja, H. Wang, S. Wright, and A. Chatterjee, "Scalability evaluation of multi-protocol over ATM (MPOA),' in Proceedings o/IEEE INFOCOM, March 1999.Google Scholar
- 22.H. Che and S.-Q. Li, "MPOA flow classification design and analysis," in Proceedings of IEEE INFOCOM, March 1999.Google Scholar
- 23.C. Villamizar. OSPF Optimized Multipath (OSPF- OMP). Internet Draft (draft-ietf-ospf-omp-02), work in progress, February 1999.Google Scholar
- 24.D. O. Awduche, J. Malcolm, M. O'Dell, and J. Mc- Manus. Requirements for Traffic Engineering Over MPLS. Internet Draft (draft-awduche-mpls-traffic-eng- 00.txt), work in progress, October 1998. Google ScholarDigital Library
- 25.G. Apostolopoulos and S. K. Tripathi, '"On reducing the processing cost of on-demand QoS path computation,'' in Proceedings o/IEEE International Con/erence on Network Protocols, pp. 80-89, Austin, TX, October 1998. Google ScholarDigital Library
- 26.M. Peyravian and R. Onvural, "Algorithm for efficient generation of link-state updates in ATM networks," Computer Networks and ISDN Systems, vol. 29, no. 2, pp. 237-247, January 1997. Google ScholarDigital Library
- 27.R. J. Gibbens, P. J. Hunt, and F. P. Kelly, "Bistability in communication networks," Disorder in Physical Systems, 1990.Google Scholar
- 28.V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, "Fast scalable algorithms for level four switching," in Proceedings of A CM SIGCOMM, September 1998.Google Scholar
- 29.T. V. Lakshman and D. Stiliadis, "High-speed policy-based packet forwarding using efficient multidimensional range matching," in Proceedings o/ACM $IGCOMM, September 1998. Google ScholarDigital Library
- 30.R. Guerin, A. Orda, and D. Williams, "QoS routing mechanisms and OSPF extensions," in Proc. Global Internet Minicon/erence, November 1997.Google Scholar
- 31.A. ShaJkh, Efficient Dynamic Routing in Wide-Area Networks, PhD thesis, University of Michigan, May 1999. Google ScholarDigital Library
- 32.V. Paxson and S. Floyd, "Why we don't know how to simulate the Internet," in Proceedings o/the Winter Simulation Con/erence, Atlanta, GA, December 1997. Google ScholarDigital Library
- 33.B. M. Waxman, "Routing of multipoint connections," IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp. 1617-1622, December 1988.Google ScholarDigital Library
- 34.E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, "How to model an internetwork," in Proceedings o/ IEEE INFOCOM, pp. 594-602, March 1996. Google ScholarDigital Library
- 35.S. Floyd and V. Jacobson, "Synchronization of periodic routing messages," IEEE/ACM Transactions on Networking, vol. 2, no. 2, pp. 122-136, April 1994. Google ScholarDigital Library
Index Terms
- Load-sensitive routing of long-lived IP flows
Recommendations
Load-sensitive routing of long-lived IP flows
Internet service providers face a daunting challenge in provisioning network resources, due to the rapid growth of the Internet and wide fluctuations in the underlying traffic patterns. The ability of dynamic routing to circumvent congested links and ...
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 systemsDespite 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