UC San Diego

We describe and analyze a new communication-efficient routing algorithm for packet forwarding networks such as the Internet. The explicit design objective of our routing algorithm, called XL, is to reduce the communication overhead of routing, allowing the routing algorithm to support larger networks without resorting to artificial network partitioning techniques such as OSPF areas. We achieve this by allowing suboptimal forwarding paths up to a user-specified stretch factor. (By setting stretch to 1 it is also possible to force optimal routing.) The XL routing algorithm is a link state algorithm, meaning that network nodes disseminate information about the state of links in the network. The essential difference between XL and the classical link state algorithm used by OSPF and IS -IS is in the semantics of link state updates: in the classical algorithm, a link state update specifies the exact link cost, while in XL it specifies an upper bound on the actual cost. This allows XL to suppress updates when the route cost do not decrease significantly. In addition to the formal specification and correctness proof, we also compare XL to four existing routing algorithms in simulation. Two of these algorithms are the classical distance vector algorithm and the link state algorithm which are the basis of the RIP and OSPF routing protocols, respectively. The other two are state-of-the art experimental protocols: distance vector with parent pointer, and the link vector algorithm, both based on the idea of restricting updates to those about links in a node's shortest-path tree. Experimental results show that our algorithm consistently generates fewer updates in response to network changes, in some cases by nearly an order of magnitude