Internet traffic engineering by optimizing OSPF weights

Abstract

Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network opera- tor. The weights could be set proportional to their physical distances, but often the main goal is to avoid congestion, i.e. overloading of links, and a standard heuristic is to make the weight of a link inversely proportional to its capacity. Our starting point was a proposed AT&T WorldNet back- bone with demands projected from previous measurements. The desire was to optimize the weight setting based on the projected demands. We showed that optimizing the weight settings for a given set of demands is NP-hard, so we resorted to a local search heuristic. Surprisingly it turned out that for the proposed AT&T WorldNet backbone, we found weight settings that performed within a few percent from that of the optimal general routingwhere the flow for each demand is optimally distributed over all paths between source and des- tination. This contrasts the common belief that OSPF rout- ing leads to congestion and it shows that for the network and demand matrix studied we cannot get a substantially better load balancing by switching to the proposed more flexible Multi-protocol Label Switching (MPLS) technologies. Our techniques were also tested on synthetic internet- works, based on a model of Zegura et al. (INFOCOM'96), for which we did not always get quite as close to the opti- mal general routing. However, we compared with standard heuristics, such as weights inversely proportional to the ca- pacity or proportional to the physical distances, and found that, for the same network and capacities, we could support a 40%-150% increase in the demands. Our assumed demand matrix can also be seen as mod- eling service level agreements (SLAs) with customers, with demands representing guarantees of throughput for virtual leased lines.