Designing BGP-based outbound traffic engineering techniques for stub ASes

ABSTRACT

Today, most multi-connected autonomous systems (AS) need to control the flow of their interdomain traffic for both performance and economical reasons. This is usually done by manually tweaking the BGP configurations of the routers on an error-prone trial-and-error basis. In this paper, we demonstrate that designing systematic BGP-based traffic engineering techniques for stub ASes are possible. Our approach to solve this traffic engineering problem is to allow the network operator to define objective functions on the interdomain traffic. Those objective functions are used by an optimization box placed inside the AS that controls the interdomain traffic by tuning the iBGP messages distributed inside the AS. We show that the utilization of an efficient evolutionary algorithm allows to both optimize the objective function and limit the number of iBGP messages. By keeping a lifetime on the tweaked routes, we also show that providing stability to the interdomain path followed by the traffic is possible. We evaluate the performance of solution based on traffic traces from two stub ASes of different sizes. Our simulations show that the interdomain traffic can be efficiently engineered by using not more than a few iBGP advertisements per minute.Our contribution in this paper is to demonstrate that by carefully thinking the design of the interdomain traffic engineering technique, stub ASes can engineer their outbound traffic over relatively short timescales, by exclusively tweaking their BGP routes, and with a minimal burden on BGP. Systematic BGP-based traffic engineering for stub ASes is thus possible at a very limited cost in terms of iBGP messages.

REFERENCES

• 1: Sharad Agarwal , Chen-Nee Chuah , Supratik Bhattacharyya , Christophe Diot, The impact of BGP dynamics on intra-domain traffic, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 2: S. Agarwal, C. Chuah, and R. Katz. Opca: Robust interdomain policy routing and traffic control. In IEEE Openarch, 2003.
• 3: Aditya Akella , Bruce Maggs , Srinivasan Seshan , Anees Shaikh , Ramesh Sitaraman, A measurement-based analysis of multihoming, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863995]
• 4: D. Allen. NPN: Multihoming and route optimization: Finding the best way home. Network Magazine, February 2002.
• 5: P. Aukia, M. Kodialam, P. Koppol, T. Lakshman, H. Sarin, and B. Suter. RATES: A server for MPLS traffic engineering. IEEE Network Magazine, pages 34--41, March/April 2000.
• 6: D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao. Overview and Principles of Internet Traffic Engineering. Internet Engineering Task Force, RFC3272, May 2002.
• 7: D. Awduche, J. Malcom, B. Agogbua, M. O'Dell, and J. McManus. Requirements for Traffic Engineering Over MPLS. Internet RFC 2702, September 1999.
• 8: Anindya Basu , Chih-Hao Luke Ong , April Rasala , F. Bruce Shepherd , Gordon Wilfong, Route oscillations in I-BGP with route reflection, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 9: O. Bonaventure, B. Quoitin, and S. Uhlig. Beyond interdomain reachability. Position paper at the Workshop on Internet Routing Evolution and Design (WIRED), October 2003.
• 10: O. Bonaventure, P. Trimintzios, G. Pavlou, B. Quoitin (Eds.), A. Azcorra, M. Bagnulo, P. Flegkas, A. Garcia-Martinez, P. Georgatsos, L. Georgiadis, C. Jacquenet, L. Swinnen, S. Tandel, and S. Uhlig. Internet Traffic Engineering. Chapter of COST263 final report, LNCS 2856, Springer-Verlag, September 2003.
• 11: O. Bonaventure, S. Uhlig, and B. Quoitin. The case for more versatile BGP Route Reflectors. Internet draft, draft-bonaventure-bgp-route-reflectors-00.txt, work in progress, July 2004.
• 12: George Edward Pelham Box , Gwilym M. Jenkins, Time Series Analysis: Forecasting and Control, Prentice Hall PTR, Upper Saddle River, NJ, 1994
• 13: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 1920
• 14: L. Burgstahler and M. Neubauer. New Modifications of the Exponential Moving Average Algorithm for Bandwidth Estimation. In Proc. of the 15th ITC Specialist Seminar, July 2002.
• 15: Hyunseok Chang , Ramesh Govindan , Sugih Jamin , Scott J. Shenker , Walter Willinger, Towards capturing representative AS-level Internet topologies, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.6, p.737-755, 22 April 2004 [doi>10.1016/j.comnet.2003.03.001]
• 16: B. Claise. Packet Sampling (PSAMP) Protocol Specifications. Internet draft, draft-ietf-psamp-protocol-01.txt, work in progress, February 2004.
• 17: Carlos A. Coello, An updated survey of GA-based multiobjective optimization techniques, ACM Computing Surveys (CSUR), v.32 n.2, p.109-143, June 2000 [doi>10.1145/358923.358929]
• 18: INTERNAP NETWORK SERVICES CORP. Internap Flow Control Platform. http://www.internap.com/.
• 19: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 20: Kalyanmoy Deb , Samir Agrawal , Amrit Pratap , T. Meyarivan, A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.849-858, September 18-20, 2000
• 21: L. Deri. nProbe: an Open Source NetFlow probe for Gigabit Networks. In Proc. of Terena TNC 2003, May 2003.
• 22: N. G. Duffield , Pawan Goyal , Albert Greenberg , Partho Mishra , K. K. Ramakrishnan , Jacobus E. van der Merwe, Resource management with hoses: point-to-cloud services for virtual private networks, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.679-692, October 2002 [doi>10.1109/TNET.2002.803918]
• 23: Nick Feamster , Hari Balakrishnan , Jennifer Rexford , Aman Shaikh , Jacobus van der Merwe, The case for separating routing from routers, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016707.1016709]
• 24: Nick Feamster , Jay Borkenhagen , Jennifer Rexford, Guidelines for interdomain traffic engineering, ACM SIGCOMM Computer Communication Review, v.33 n.5, October 2003 [doi>10.1145/963985.963988]
• 25: Nick Feamster , Jared Winick , Jennifer Rexford, A model of BGP routing for network engineering, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 26: B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. IEEE Communications Magazine, October 2002.
• 27: B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In INFOCOM 2000, March 2000.
• 28: David K. Goldenberg , Lili Qiuy , Haiyong Xie , Yang Richard Yang , Yin Zhang, Optimizing cost and performance for multihoming, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 29: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 30: Sam Halabi , Danny McPherson, Internet Routing Architectures, Second Edition, Cisco Systems, 2000
• 31: B. Huffaker, M. Fomenkov, D. Plummer, D. Moore, and K. Claffy. Distance Metrics in the Internet. In Proc. of IEEE International Telecommunications Symposium (ITS), September 2002.
• 32: J. Johnson. BGP is a reachability protocol. NANOG25 meeting, Toronto, Canada. June 2002. Available at http://www.nanog.org/mtg-0206/ppt/jerm2/ index.html.
• 33: J. Johnson. Intelligent route control improves BGP. Network World, February 2002.
• 34: Amit Kumar , Rajeev Rastogi , Avi Silberschatz , Bulent Yener, Algorithms for provisioning virtual private networks in the hose model, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.565-578, August 2002 [doi>10.1109/TNET.2002.802141]
• 35: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
• 36: S. Leinen. Evaluation of candidate protocols for IP flow information export (IPFIX). Internet draft, draft-leinen-ipfix-eval-contrib-02, work in progress, January 2004.
• 37: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 38: D. Meyer. University of Oregon Route Views Project. Available at http://antc.uoregon.edu/route-views/.
• 39: P. Morrissey. Mapping out the best route. Network Computing, http://www.nwc.com/showArticle.jhtml?articleID=16401572, December 2003.
• 40: F5 NETWORKS. Big-IP Link Controller. http://www.f5.com.
• 41: Juniper Networks. Junos software release 5.6 : New features list. http://www.juniper.net/products/ip_ infrastructure/junos/105012.html.
• 42: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 43: R. Purshouse and P. Fleming. Conflict, Harmony, and Independence: Relationships in Multi-criterion Optimisation. In Proc. of the Second International Conference on Multi-Criterion Optimization (EMO2003), Portugal, pages 16--30, April 2003.
• 44: Y. Qiao, J. Skicewicz, and P. Dinda. Multiscale predictability of network traffic. Technical Report NWU-CS-02-13, Nothwestern University, October 2002.
• 45: B. Quoitin. C-BGP, an efficient BGP simulator. http://cbgp.info.ucl.ac.be/, September 2003.
• 46: B. Quoitin, S. Uhlig, C. Pelsser, L. Swinnen, and O. Bonaventure. Interdomain traffic engineering with BGP. IEEE Communications Magazine, May 2003.
• 47: RADWARE. Linkproof. http://www.radware.com/.
• 48: Y. Rekhter, T. Li, and S. Hares. A Border Gateway Protocol 4 (BGP-4). Internet draft, draft-ietf-idr-bgp4-24.txt, work in progress, November 2003.
• 49: Jennifer Rexford , Jia Wang , Zhen Xiao , Yin Zhang, BGP routing stability of popular destinations, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637232]
• 50: A. Sang and S. Li. A Predictability Analysis of Network Traffic. In Proc. of IEEE INFOCOM 2000, 2000.
• 51: S. Sangli, D. Tappan, and Y. Rekhter. BGP Extended Communities Attribute. Internet draft, draft-ietf-idr-bgp-ext-communities-06.txt, work in progress, August 2003.
• 52: P. Smith. Weekly routing table report. Weekly reports from APNIC's router in Japan sent to [e-mail].
• 53: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 54: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet hierarchy from multiple vantage points. In INFOCOM 2002, June 2002.
• 55: Cisco Systems. BGP Case Studies Section 1. http: //www.cisco.com/warp/public/459/13.html.
• 56: Cisco Systems. Sample Configurations for Load Sharing with BGP in Single and Multihomed Environments. http: //www.cisco.com/warp/public/459/40.html.
• 57: CORPORATE Cisco Systems, Inc., Cisco IOS 12.0 Switching Services, Cisco Press, 1999
• 58: ROUTESCIENCE TECHNOLOGIES. PathControl. http://www.routescience.com/.
• 59: S. Uhlig. Implications of the traffic characteristics on interdomain traffic engineering. PhD Thesis, Computer Science and Engineering Department, Université catholique de Louvain, March 2004.
• 60: S. Uhlig. A multiple-objectives evolutionary perspective to interdomain traffic engineering in the internet. In Workshop on Nature Inspired Approaches to Networks and Telecommunications (NIANT) in PPSN04, Birmingham, UK, September 2004.
• 61: S. Uhlig, O. Bonaventure, and B. Quoitin. Interdomain Traffic Engineering with minimal BGP Configurations. In Proc. of ITC-18, September 2003.
• 62: Steve Uhlig , Oliver Bonaventure , Vincent Magnin , Chris Rapier , Luca Deri, Implications of the topological properties of Internet traffic on traffic engineering, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.967974]
• 63: S. Uhlig and B. Quoitin. BGP-based interdomain traffic engineering for transit ASes. Under submission, http://cbgp.info.ucl.ac.be/apps.html# section_transit_te.
• 64: D. Walton, D. Cook, A. Retana, and J. Scudder. Advertisement of multiple paths in BGP. Internet draft, draft-walton-bgp-add-paths-01.txt, work in progress, November 2002.
• 65: Y. Wang, Z. Wang, and L. Zhang. Internet traffic engineering without full mesh overlaying. In INFOCOM2001, April 2001.
• 66: X. Xiao, A. Hannan, B. Bailey, and L. Ni. Traffic engineering with MPLS in the Internet. IEEE Network Magazine, March 2000.
• 67: Tao Ye , Shivkumar Kalyanaraman, A recursive random search algorithm for large-scale network parameter configuration, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring; Network management
      C.2.5 Local and Wide-Area Networks

Keywords:
BGP, interdomain traffic engineering, multiple-objectives optimization