1986 | OriginalPaper | Chapter
Computer Networks with Compact Routing Tables
Authors : J. van Leeuwen, R. B. Tan
Published in: The Book of L
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.