On Lower Bound of the Number of Channels for Deadlock-Free
Whormhole Routing
Authors: Li Sheng and Jie Wu
ABSTRACT
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.
DIMACS Home Page