LCS Publication Details
Publication Title: ROUTING WITH POLYNOMIAL COMMUNICATION-SPACE TRADEOFF
Publication Author: Awerbuch, Baruch
Additional Authors: Peleg, D.
LCS Document Number: MIT-LCS-TM-411
Publication Date: 9-1-1989
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
This paper presents a family of memory-balanced routing schemes that use relatively short paths while storing relatively little routing information. The hierarchical schemes k (for every fixed k 1) guarantee a stretch factor of O ( ) on the length of the routes and require storing at most bits of routing information per vertex in an n-processor network with diameter D. The schemes are name-independent and applicable to general networks with arbitrary edge weights. This improves on previous designs whose stretch bound was exponential in k.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.