## 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.

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