Balancing performance, robustness and flexibility in routing systems

ABSTRACT

Modern networks face the daunting task of handling increasingly diverse traffic that is displaying a growing intolerance to disruptions. This has given rise to many initiatives, and in this paper we focus on multiple topology routing as the primary vehicle for meeting those demands. Specifically, we seek routing solutions capable of not just accommodating different performance goals, but also preserving them in the presence of disruptions. The main challenge is computational, i.e., to identify among the enormous number of possible routing solutions the one that yields the best compromise between performance and robustness. This is where our principal contribution lies, as we expand the definition of critical links -- a key concept in improving the efficiency of routing computation -- and develop a precise methodology to efficiently converge on those solutions. Using this new methodology, we demonstrate that one can compute routing solutions that are both flexible in accommodating different performance requirements and robust in maintaining them in the presence of failures and traffic fluctuations.

REFERENCES

• 1: G. Apostolopoulos. Using multiple topologies for IP-only protection against network failures: A routing performance perspective. Technical report, ICS-FORTH, Greece, 2006.
• 2: A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, October 1999.
• 3: J. Cao, D. Davis, S. V. Wiel, and B. Yu. Time-varying network tomography: Router link data. Journal of the American Statistical Association, Dec 2000.
• 4: R. G. Cole , J. H. Rosenbluth, Voice over IP performance monitoring, ACM SIGCOMM Computer Communication Review, v.31 n.2, April 2001 [doi>10.1145/505666.505669]
• 5: B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In IEEE INFOCOM, 2000.
• 6: B. Fortz and M. Thorup. Optimizing OSPF/IS-IS weights in a changing world. IEEE JSAC, May 2002.
• 7: B. Fortz and M. Thorup. Robust optimization of OSPF/IS-IS weights. In International Network Optimization Conference, 2003.
• 8: Stein Gjessing, Implementation of two Resilience Mechanisms using Multi Topology Routing and Stub Routers, Proceedings of the Advanced Int'l Conference on Telecommunications and Int'l Conference on Internet and Web Applications and Services, p.29, February 19-25, 2006
• 9: Gianluca Iannaccone , Chen-nee Chuah , Richard Mortier , Supratik Bhattacharyya , Christophe Diot, Analysis of link failures in an IP backbone, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637238]
• 10: A. Kvalbein, A. F. Hansen, T. Cicic, S. Gjessing, and O. Lysne. Fast IP network recovery using multiple routing configurations. In IEEE INFOCOM, 2006.
• 11: Kin Wah Kwong , Roch Guérin , Anees Shaikh , Shu Tao, Improving service differentiation in IP networks through dual topology routing, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York [doi>10.1145/1364654.1364675]
• 12: K.-W. Kwong, R. Guérin, A. Shaikh, and S. Tao. Balancing performance, robustness and flexibility in routing systems. Technical report, University of Pennsylvania, 2008.
• 13: 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
• 14: Antonio Nucci , Supratik Bhattacharyya , Nina Taft , Christophe Diot, IGP link weight assignment for operational Tier-1 backbones, IEEE/ACM Transactions on Networking (TON), v.15 n.4, p.789-802, August 2007 [doi>10.1109/TNET.2007.893878]
• 15: Antonio Nucci , Ashwin Sridharan , Nina Taft, The problem of synthetically generating IP traffic matrices: initial recommendations, ACM SIGCOMM Computer Communication Review, v.35 n.3, July 2005 [doi>10.1145/1070873.1070876]
• 16: Konstantina Papagiannaki , Rene Cruz , Christophe Diot, Network performance monitoring at small time scales, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948244]
• 17: T. Przygienda, N. Shen, and N. Sheth. M-ISIS: Multi topology (MT) routing in IS-IS. IETF RFC 5120, February 2008.
• 18: P. Psenak, S. Mirtorabi, A. Roy, L. Nguyen, and P. Pillay-Esnault. Multi-topology (MT) routing in OSPF. IETF RFC 4915, June 2007.
• 19: A. Sridharan and R. Guérin. Making IGP routing robust to link failures. In Networking, 2005.
• 20: D. Yuan. A bicriteria optimization approach for robust OSPF routing. In IEEE Workshop on IPOM, 2003.

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.0 General
          Subjects: Data communications
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance