Better Alternatives to OSPF Routing

Abstract

The current standard for intra-domain network routing, Open ShortestPath First (OSPF), suffers from a number ofproblems-the tunable parameters (the weights) are hard tooptimize, the chosen paths are not robust underchanges in traffic or network state, and some network links are over-usedat the expense of others. We present prototypical scenarios that illustrate these problems.Then we propose several variants of a protocol to eliminate oralleviate them and demonstrate the improvements in performance underthose scenarios. We also prove that these protocols never performsignificantly worse than OSPF and show that for at least a limitedclass of network topologies, it is possible to find efficiently theoptimal weight settings. Some of the problems with OSPF are well known; indeed, there areseveral routing protocols that perform better than OSPF in routingquality (i.e., in terms of congestion, delay, etc.). OSPF’spopularity persists in part because of its efficiency with respect toseveral resource bounds. In contrast, many competing protocols thatprovide routing superior to OSPF are computationally prohibitive.Motivated by this consideration, we designed our protocols not only toachieve better routing quality than OSPF, but also to use resources inamount comparable with OSPF with respect to offline broadcastcommunication, size of and time to compute routing tables, packet deliverylatency, and packet header structure and size.