| 2 (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract This paper analyzes the effect of virtual channels on the performance of wormhole routing algorithms. We show that in a network in which each edge can emulate up to q virtual channels, it is possible to route any set of b-bit messages whose paths have congestion c and dilation d in (b + d)c(d log d) 1=q 2 O(log \Lambda (c=d)) bit-steps. We also prove a nearly matching lower bound, i.e., for any values of c, d, q, and b, where c ss d and b * d, we show how to construct a network and a set of b-bit messages whose paths have congestion c and dilation d that require \Omega (bcd | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||