Improving Link-State Routing - by Using Estimated Future Link Delays (Revised)

Abstract

In link-state routing, routes are determined based on estimates of the current delays on the links. Ideally, a data packet should be routed based on the delays it will encounter at each link of the path at the time the packet gets to the link. To address this issue, we have developed a new approach that improves link-state routing by estimating and using the future link delays encountered by data packets. In link-state routing, link-delay estimates are periodically flooded throughout the network. This flooding of link-delay estimates is done without considering the relevance of these estimates to routing quality. Our approach also improves link-state routing by broadcasting these estimates only to the extent that they are relevant. Simulation studies suggest that our approach can lead to significant reductions in routing traffic with noticeable improvements of routing quality in high-load conditions. (UMIACS-TR-2001-75.2)