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 configu-ration, 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. Index Terms—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. I