http://eeweb.poly.edu/el933/papers/fortz00internet.pdf
2016/01/01 22:40:00 cited 1100+
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 operator. 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 the standard heuristic recommended by Cisco is to make the weight of a link inversely proportional to its capacity.
Our starting point was a proposed AT&T WorldNet backbone 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 … This contrasts the common belief that OSPF routing 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 assumed demand matrix can also be seen as modeling service level agreements (SLAs) with customers, with demands representing guarantees of throughput for virtual leased lines.
ROVISIONING an Internet Service Provider (ISP) backbone network for intra-domain IP traffic is a big challenge, particularly due to rapid growth of the network and user demands. At times, the network topology and capacity may seem insufficient to meet the current demands. At the same time, there is mounting pressure for ISPs to provide Quality of Service (QoS) in terms of Service Level Agreements (SLAs) with customers, with loose guarantees on delay, loss, and throughput. All of these issues point to the importance of traffic engineering …
... traffic engineering, making more efficient use of existing network resources by tailoring routes to the prevailing traffic.
a demand matrix D that for each pair of nodes (s,t) tells us how much traffic flow we will need to send from s to t.
The general question studied in this paper
Can a sufficiently clever weight settings make OSPF routing perform nearly as well as optimal general/MPLS routing?
Finding a perfect answer is hard in the sense that it is NP-hard to find an optimal setting of the OSPF weights for an arbitrary network. ... a local search heuristic, ... for the proposed AT&T WorldNet backbone, the heuristic found weight settings making OSPF routing performing within a few percent from the optimal general routing ...
From (12), it follows that the maximal gap between optimal general routing and optimal OSPF routing is less than a factor 5000.