About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIGCOMM 1990
Conference paper
Topology distribution cost vs. efficient routing in large networks
Abstract
Routing a message in a network is efficient (in terms of weight of the path used to carry the message) when nodes know the full topology of the network. This may not be the case in large networks since a network may be composed of smaller autonomous pieces by design or by requirements on performance, with each piece having less than complete information about other pieces. We present a trade-off between the amount of topology information exchanged among these pieces and the efficiency of routing in the network. The large network that we study is a collection of networks connected by boundary nodes. Each boundary node knows the topology of its network and the connectivity of networks to each other. The question addressed here is how much topology information about each network should be distributed to other networks in order to achieve reasonably efficient routing.