Universal routing in distributed networks

Kevin F. Chen, Edwin H M Sha, Bin Xiao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

We show that universal routing can be achieved with low overhead in distributed networks. The validity of our results rests on a new network called the fat-stack. We show that from a routing perspective the fat-stack is efficient and is suitable for use as a baseline distributed network. We prove that the fat-stack is universal by routing efficiency. A requirement for the fat-stack to be universal is that link capacities double up the levels of the network. We use methods developed in the areas of VLSI and processor interconnect for much of our analysis. Our universality proof shows that a fat-stack of area θ(A) can simulate any competing network of area A with O(log3/2 A) overhead independently of wire delay. The universality result implies that the fat-stack of a given size is nearly the best routing network of that size. The fat-stack is also the minimal universal network for an O(log3/2 A) overhead in terms of number of links.
Original languageEnglish
Title of host publicationProceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
Pages555-559
Number of pages5
Volume2
DOIs
Publication statusPublished - 1 Sep 2005
Event11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005 - Fukuoka, Japan
Duration: 20 Jul 200522 Jul 2005

Conference

Conference11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
Country/TerritoryJapan
CityFukuoka
Period20/07/0522/07/05

ASJC Scopus subject areas

  • Engineering(all)

Cite this