IEEE Communications Magazine • October 2002118Traffic Engineering withTraditional IP Routing Protocols0163-6804/02/$17.00 © 2002 IEEEABSTRACTTraffic engineering involves adapting therouting of traffic to network conditions, with thejoint goals of good user performance and effi-cient use of network resources. In this article wedescribe an approach to intradomain trafficengineering that works within the existingdeployed base of interior gateway protocols,such as Open Shortest Path First and Intermedi-ate System-Intermediate System. We explainhow to adapt the configuration of link weights,based on a networkwide view of the traffic andtopology within a domain. In addition, we sum-marize the results of several studies of tech-niques for optimizing OSPF/IS-IS weights to theprevailing traffic. The article argues that tradi-tional shortest path routing protocols are sur-prisingly effective for engineering the flow oftraffic in large IP networks.INTRODUCTIONIn some sense, IP networks manage themselves.A host implementing the Transmission ControlProtocol (TCP) adjusts its sending rate to thebandwidth available on the path to the destina-tion, and routers react to changes in the net-work topology by computing new paths. Thishas made the Internet an extremely robustcommunication network, even in the face ofrapid growth and occasional failures. However,these mechanisms do not ensure that the net-work runs efficiently. For example, a particularlink may be congested despite the presence ofunderutilized links in other parts of the net-work, or a voice-over-IP call may travel over aroute with high propagation delay when a low-latency path is available. Improving user perfor-mance and making more efficient use ofnetwork resources requires adapting the routingof traffic to the prevailing demands. This task isreferred to as traffic engineering [1]. In this arti-cle we focus on engineering the flow of trafficwithin a single autonomous system (AS), suchas a company, university campus, or Internetservice provider (ISP).INTRADOMAIN TRAFFIC ENGINEERINGTraffic engineering depends on having a set ofperformance objectives that guide the selectionof paths, as well as effective mechanisms for therouters to select paths that satisfy these objec-tives. Most large IP networks run interior gate-way protocols (IGPs) such as Open ShortestPath First (OSPF) or Intermediate System-Inter-mediate System (IS-IS) that select paths basedon static link weights. These weights are typicallyconfigured by the network operators. Routersuse these protocols to exchange link weights andconstruct a complete view of the topology insidethe AS, as shown in Fig. 1. Then each routercomputes shortest paths (where the length of apath is the sum of the weights on the links) andcreates a table that controls the forwarding ofeach IP packet to the next hop in its route.On the surface, shortest path routing doesnot seem flexible enough to support traffic engi-neering in a network supporting a diverse set ofapplications. First, these IGPs are limited torouting scenarios that can be specified with asingle integer weight on each link. However, weargue that link weights suffice to specify near-optimal routing for large real-world networks.Second, in their basic forms, the OSPF and IS-ISprotocols do not adapt the link weights inresponse to changes in traffic or failures of net-work elements, and the path selection processdoes not directly incorporate any performanceobjectives. Recent standards activity has pro-posed traffic engineering extensions to OSPFand IS-IS to incorporate traffic load in the linkstate advertisements and path selection deci-sions. However, these extensions require modifi-cations to the routers to collect and disseminatethe traffic statistics and establish paths based onthe load metrics. Instead, we argue that it isoften possible to select static link weights thatare resilient to traffic fluctuations and link fail-ures, allowing the use of the traditional incarna-tions of OSPF and IS-IS.The example in Fig. 2 shows how to controlthe distribution of traffic in a network by tuningthe IGP weights. All three diagrams concern theBernard Fortz, Université Catholique de LouvainJennifer Rexford and Mikkel Thorup, AT&T Labs-ResearchTOPICS IN INTERNET TECHNOLOGYIEEE Communications Magazine • October 2002119same network where all links have the samecapacity and each of the nodes q, r, s, and whave one unit of traffic to send to node t. Thesimple performance objective here is to mini-mize the maximum link load.Initial configuration with unit weights: Thefirst diagram in Fig. 2 shows the results of havingthe same weight of 1 on every link. This directs allof the traffic from nodes q, r, and s through nodeu, forcing 3 units of load on link (u, t).Local change to the weight of the congestedlink: A naive approach to reducing the load is toincrease the IGP weight on the overloaded link(u, t). In the second diagram in Fig. 2, the weightof (u, t) is increased to 2. This configurationresults in two shortest paths for nodes q, r, and s,and an even splitting of traffic over paths via uand v. However, this solution places 2.5 units ofload on the link (w, t).Global optimization of the link weights: Aglobal optimization of the weights would pro-duce a weight setting like the one in the thirddiagram in Fig. 2, with no link carrying morethan 2 units of traffic. This distribution of trafficis optimal with regard to the maximum load.Since 4 units of traffic have to reach node talong its two incoming edges, no other routingscheme could produce a better solution.In this example, changing the link weights toalleviate the congestion on link (u, t) is an attrac-tive alternative to buying and deploying addi-tional bandwidth between routers u and t.ADVANTAGES OF USINGTRADITIONAL OSPF/IS-ISThis article presents an overview of a practicalapproach to working within the existing frame-work of static link weights, without modificationto the routing protocols or the routers them-selves. The article brings together the work invarious papers that describe individual compo-nents of this approach to traffic engineering.The main point underlying this body of work isthat the process of arriving at good values forthe weights, or a good set of changes to theexisting values of the weights, is handled exter-nally from the routers. This process coulddepend on traffic measurements and topologydata collected from the operational network.The selection of weights may also