An Investigation on Space-Time Tradeoff of Routing Schemes in Large Computer Networks

Kenji ISHIDA  

IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.11   pp.1341-1347
Publication Date: 1993/11/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Responsive Computer Systems)
large computer network,  hierarchical routing,  responsive system,  

Full Text: PDF(509.2KB)>>
Buy this Article

Space-time tradeoff is a very fundamental issue to design a fault-tolerant real-time (called responsive) system. Routing a message in large computer networks is efficient when each node knows the full topology of the whole network. However, in the hierarchical routing schemes, no node knows the full topology. In this paper, a tradeoff between an optimality of path length (message delay: time) and the amount of topology information (routing table size: space) in each node is presented. The schemes to be analyzed include K-scheme (by Kamoun and Kleinrock), G-scheme (by Garcia and Shacham), and I-scheme (by authors). The analysis is performed by simulation experiments. The results show that, with respect to average path length, I-scheme is superior to both K-scheme and G-scheme, and that K-scheme is better than G-scheme. Additionally, an average path length in I-scheme is about 20% longer than the optimal path length. On the other hand, for the routing table size, three schemes are ranked in reverse direction. However, with respect to the order of size of routing table, the schemes have the same complexity O (log n) where n is the number of nodes in a network.