Making routing robust to changing traffic demands: algorithms and evaluation

ABSTRACT

Intra-domain traffic engineering can significantly enhance the performance of large IP backbone networks. Two important components of traffic engineering are understanding the traffic demands and configuring the routing protocols. These two components are inter-linked, as it is widely believed that an accurate view of traffic is important for optimizing the configuration of routing protocols, and through that, the utilization of the network.This basic premise, however, seems never to have been quantified. How important is accurate knowledge of traffic demands for obtaining good utilization of the network? Since traffic demand values are dynamic and illusive, is it possible to obtain a routing that is "robust" to variations in demands?We develop novel algorithms for constructing optimal robust routings and for evaluating the performance of any given routing on loosely constrained rich sets of traffic demands. Armed with these algorithms we explore these questions on a diverse collection of ISP networks. We arrive at a surprising conclusion: it is possible to obtain a robust routing that guarantees a nearly optimal utilization with a fairly limited knowledge of the applicable traffic demands.

REFERENCES

• 1: David Applegate , Edith Cohen, Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863991]
• 2: David Applegate , Lee Breslau , Edith Cohen, Coping with network failures: routing strategies for optimal demand oblivious restoration, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 3: D. Awduche , J. Malcolm , J. Agogbua , M. O'Dell , J. McManus, Requirements for Traffic Engineering Over MPLS, RFC Editor, 1999
• 4: D. Awduche , A. Chiu , A. Elwalid , I. Widjaja , X. Xiao, Overview and Principles of Internet Traffic Engineering, RFC Editor, 2002
• 5: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 6: [6] S. Bhattacharya, C. Diot, J. Jetcheva, and N. Taft, "Geographical and temporal characteristics of inter-POP flows: view from a single POP," Eur. Trans. Telecommun., vol. 13, no. 1, pp. 5-22, Feb. 2002.
• 7: [7] J. Cao, D. Davis, S. V. Wiel, and B. Yu, "Time-varying network tomography: router link data," J. Amer. Statist. Assoc., vol. 95, pp. 1063-1075, 2000.
• 8: [8] Configuring OSPF Cisco, 1997 [Online]. Available: http://www.cisco. com/uni-verc/cc/td/doc/product/software/ios113ed/113ed_cr/np1_c/ 1cospf.htm
• 9: [9] CPLEX Large-Scale Mathematical Programming Software 2003 [On-line]. Available: http://www.cplex.com
• 10: N. G. Duffield , Matthias Grossglauser, Trajectory sampling for direct traffic observation, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.280-292, June 2001 [doi>10.1109/90.929851]
• 11: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 12: [12] B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, 2000, pp. 519-528.
• 13: [13] B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world," IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 756-767, May 2002.
• 14: [14] B. Grötschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. New York: Springer-Verlag, 1988.
• 15: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 16: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 17: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 18: [18] D. Mitra and K. G. Ramakrishna, "A case study of multiservice, multipriority traffic engineering design for data networks," in Proc. IEEE GLOBECOM, 1999, pp. 1077-1083.
• 19: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 20: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 21: Matthew Roughan , Albert Greenberg , Charles Kalmanek , Michael Rumsewicz , Jennifer Yates , Yin Zhang, Experience in measuring backbone traffic variability: models, metrics, measurements and meaning, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637213]
• 22: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 23: [23] Internet Traffic Engineering Working Group, 2003 [Online]. Available: http://www.ietf.org/html.charters/OLD/tewg-charter.html.

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
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Design, Management

Keywords:
oblivious routing, routing, traffic engineering