IGP link weight assignment for operational Tier-1 backbones

ABSTRACT

Intradomain routing protocols, such as IS-IS or OSPF, associate a weight (or cost) with each link to compute traffic routes. Proposed methods for selecting link weights largely ignore two practical issues, that of service-level agreement (SLA) requirements and of failures. Optimizing the routing configuration, without bounding the SLA, could severely violate this requirement, which is one of the most important vehicles used by carriers to attract new customers. Since most failures are short-lived, it is much more practical not to have to change weight settings during these episodes. In this paper we propose a Tabu-search heuristic for choosing link weights that takes into account both SLA requirements and link failures. Our algorithm selects link weights that still perform well, without having to be changed, even under failure events. To validate the heuristic, we develop a lower bound based on a formal integer linear program (ILP) model, and show that our heuristic solution is within 10% of the optimal ILP lower bound. We study the performance of the heuristic using two operational Tier-1 backbones. Our results illustrate two tradeoffs, between link utilization and the SLA provided, and between performance under failures versus performance without failures. We find that performance under transient failures can be dramatically improved at the expense of a small degradation during normal network operation (i.e., no failures), while simultaneously satisfying SLA requirements. We use our algorithm inside a prototype tool to conduct a case study and illustrate how systematic link weight selection can facilitate topology planning.

REFERENCES

• 1: Supratik Bhattacharyya , Christophe Diot , Jorjeta Jetcheva, Pop-level and access-link-level traffic dynamics in a tier-1 POP, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505209]
• 2: [2] B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. EEE INFOCOM, Tel-Aviv, Israel, Mar. 2000.
• 3: [3] B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing World," IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 765-767, 2001.
• 4: [4] B. Fortz and M. Thorup, Fortifying OSPF/IS-IS against link failures. [Online]. Available: http://www.research.att.com/mthorup/PAPERS/ papers.html Tech. Rep.
• 5: [5] M. Pioro, A. Szentesi, J. Harmatos, A. Juttner, P. Gajowniczek, and S. Kozdrowski, "On OSPF related network optimisation problems," in Proc. IFIP ATM IP, Ilkley, U.K., Jul. 2000.
• 6: [6] F. Giroire, A. Nucci, N. Taft, and C. Diot, "Increasing the robustness of IP backbones in the absence of optical level protection," in Proc. IEEE INFOCOM, Apr. 2003.
• 7: Fred Glover, Tabu Search, Kluwer Boston, Inc., 1998
• 8: Sam Halabi , Danny McPherson, Internet Routing Architectures, Second Edition, Cisco Systems, 2000
• 9: [9] J. Harmatos, "A heuristic algorithm for solving the static weight assignment optimisation problem in OSPF networks," in Proc. Global Internet Conf., Dallas, TX, Nov. 2001.
• 10: 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]
• 11: [11] M. Krunz, B. Zhang, and C. Chen, "Stateless QOS routing in IP networks," in Proce. Global Internet Workshop, Dallas, TX, Nov. 2001.
• 12: [12] ILOG CPLEX. [Online]. Available: http://www.ilog.com/products/ cplex/
• 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: [14] A. Nucci, B. Schroeder, S. Bhattacharyya, N. Taft, and C. Diot, "Link weight assignment for transient link failures," in 18th Int. Teletraffic Congr. (ITC), Sep. 2003.
• 15: 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]
• 16: D. Oran, OSI IS-IS Intra-domain Routing Protocol, RFC Editor, 1990
• 17: 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]
• 18: [18] K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, F. Tobagi, and C. Diot, "Analysis of measured single-hop delay from an operational backbone network," in Proc. IEEE INFOCOM, New York, Jun. 2002.
• 19: [19] Y. Wang, Z. Wang, and L. Zhang, "Internet traffic engineering without full mesh overlaying," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001.
• 20: Sharad Agarwal , Antonio Nucci , Supratik Bhattacharyya, Measuring the Shared Fate of IGP Engineering and Interdomain Traffic, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.236-245, November 06-09, 2005 [doi>10.1109/ICNP.2005.22]

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Design, Performance

Keywords:
failures, interior gateway protocol (IGP) routing, intermediate system to intermediate system (IS-IS) protocol, open shortest path first (OSPF) protocol, optimization, robustness, tabu search, traffic engineering