Nick Feamster
Jennifer Rexford
ABSTRACT
The performance of IP networks depends on a wide variety of dynamic conditions. Traffic shifts, equipment failures, planned maintenance, and topology changes in other parts of the Internet can all degrade performance. To maintain good performance, network operators must continually reconfigure the routing protocols. Operators configure BGP to control how traffic flows to neighboring Autonomous Systems (ASes), as well as how traffic traverses their networks. However, because BGP route selection is distributed, indirectly controlled by configurable policies, and influenced by complex interactions with intradomain routing protocols, operators cannot predict how a particular BGP configuration would behave in practice. To avoid inadvertently degrading network performance, operators need to evaluate the effects of configuration changes before deploying them on a live network. We propose an algorithm that computes the outcome of the BGP route selection process for each router in a single AS, given only a static snapshot of the network state, without simulating the complex details of BGP message passing. We describe a BGP emulator based on this algorithm; the emulator exploits the unique characteristics of routing data to reduce computational overhead. Using data from a large ISP, we show that the emulator correctly computes BGP routing decisions and has a running time that is acceptable for many tasks, such as traffic engineering and capacity planning.
- D. O. Awduche, A. Chiu, A. Elwalid, I. Widjaja, andX. Xiao, "Overview and principles of Internet traffic engineering." Request for Comments 3272, May 2002.]] Google Scholar
Digital Library
- B. Fortz, J. Rexford, and M. Thorup, "Traffic engineering with traditional IP routing protocols," IEEE Communication Magazine, October 2002.]] Google ScholarDigital Library
- A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "NetScope: Traffic engineering for IP networks," IEEE Network Magazine, pp. 11--19, March 2000.]] Google ScholarDigital Library
- "Cariden." http://www.cariden.com/, 2003.]]Google Scholar
- "MainStation." http://www.makesystems.com/products/MainStation.html, 2003.]]Google Scholar
- "A Border Gateway Protocol 4 (BGP-4)." Internet Draft draft-ietf-idr-bgp4-23.txt, work in progress, November 2003.]]Google Scholar
- "SSFNet." http://www.ssfnet.org/, 2003.]]Google Scholar
- N. Feamster, J. Borkenhagen, and J. Rexford, "Guidelines for interdomain traffic engineering," ACM Computer Communication Review, vol. 33, October 2003.]] Google ScholarDigital Library
- T. Griffin, F. B. Shepherd, and G. Wilfong, "The stable paths problem and interdomain routing," IEEE/ACM Trans. Networking, vol. 10, no. 1, pp. 232--243, 2002.]] Google ScholarDigital Library
- C. Labovitz, A. Ahuja, and F. Jahanian, "Experimental study of Internet stability and wide-area network failures," in Proc. Fault Tolerant Computing Symposium, June 1999.]] Google ScholarDigital Library
- J. Rexford, J. Wang, Z. Xiao, and Y. Zhang, "BGP routing stability of popular destinations," in Proc. Internet Measurement Workshop, November 2002.]] Google ScholarDigital Library
- T. G. Griffin and G. Wilfong, "On the correctness of IBGP configuration," in Proc. ACM SIGCOMM, August 2002.]] Google ScholarDigital Library
- N. Feamster and J. Rexford, "Network-wide BGP route prediction for traffic engineering," in Proc. Workshop on Scalability and Traffic Control in IP Networks, SPIE ITCOM Conference, August 2002.]]Google ScholarCross Ref
- A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True, "Deriving traffic demands for operational IP networks: Methodology and experience," IEEE/ACM Trans. Networking, vol. 9, June 2001.]] Google ScholarDigital Library
- L. Gao and J. Rexford, "Stable Internet routing without global coordination," IEEE/ACM Trans. Networking, vol. 9, pp. 681--692, December 2001.]] Google ScholarDigital Library
- T. Ye, H. T. Kaur, and S. Kalyanaraman, "A recursive random search algorithm for large-scale network parameter configuration," in Proc. ACM SIGMETRICS, June 2003.]] Google ScholarDigital Library
- T. G. Griffin and G. Wilfong, "Analysis of the MED oscillation problem in BGP," in Proc. International Conference on Network Protocols, November 2002.]] Google ScholarDigital Library
- N. Feamster, "Practical verification techniques for wide-area routing," in 2nd ACM Workshop on Hot Topics in Networks, November 2003.]]Google Scholar
Index Terms
- A model of BGP routing for network engineering
Recommendations
The impact of BGP dynamics on intra-domain traffic
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systemsRecent work in network traffic matrix estimation has focused on generating router-to-router or PoP-to-PoP (Point-of-Presence) traffic matrices within an ISP backbone from network link load data. However, these estimation techniques have not considered ...
Neighbor-specific BGP: more flexible routing policies while improving global stability
SIGMETRICS '09: Proceedings of the eleventh international joint conference on Measurement and modeling of computer systemsThe Border Gateway Protocol (BGP) offers network administrators considerable flexibility in controlling how traffic flows through their networks. However, the interaction between routing policies in different Autonomous Systems (ASes) can lead to ...
A model of BGP routing for network engineering
The performance of IP networks depends on a wide variety of dynamic conditions. Traffic shifts, equipment failures, planned maintenance, and topology changes in other parts of the Internet can all degrade performance. To maintain good performance, ...
Comments