DIMACS TR: 99-18

On Lower Bound of the Number of Channels for Deadlock-Free Whormhole Routing

Authors: Li Sheng and Jie Wu


Libeskind-Hadas recently provided a tight lower bound on the number of channels required by a broad class of deadlock-free wormhole routing algorithm. Given an interconnection network represented by a digraph $G=(N,C)$, where each vertex in $N$ represents a node and each directed link in $C$ represents a unidirectional channel, Libeskind-Hadas showed that $|C|\ge 2|N|-2$ is the tight lowered on the number of Channels required for Deadlock-Free Whormhole Routing. In this short note, we show a simpler proof of this tight lower bound.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-18.ps.gz
DIMACS Home Page