1986 | OriginalPaper | Buchkapitel
Computer Networks with Compact Routing Tables
verfasst von : J. van Leeuwen, R. B. Tan
Erschienen in: The Book of L
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The routing problem in computer networks is traditionally solved by providing detailed routing information for all destinations at every node. We consider the problem of routing messages with only a small amount of information at every node. For example, for every connected N-node network a scheme can be devised such that every message can be routed within O(√N) routing decisions. Improving on an observation of Santoro & Khatib [3] for trees we derive a general method of routing messages in arbitrary networks using tables of a size corresponding to the number of links at a node, while utilizing all links in the network.