Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!mailrus!tut.cis.ohio-state.edu!ukma!gatech!hubcap!wen-king
From: wen-king@cit-vax.Caltech.Edu (King Su)
Newsgroups: comp.parallel
Subject: Re: Wormhole Routing
Message-ID: <3401@hubcap.UUCP>
Date: 1 Nov 88 17:53:50 GMT
Sender: fpst@hubcap.UUCP
Lines: 17
Approved: parallel@hubcap.clemson.edu

In article <3388@hubcap.UUCP> grunwald@m.cs.uiuc.edu writes:

>In a hypercube architecture, circuit switching messages using the standard
<``ecube'' routing method leads to skewed resource utilization. E.g., you'll
>find 80% utilization of channel #0 but only ~10% utilization of channel #6
<because of the routing algorithm.

All channels are used equally if message pattern is random.  If the k-th bit
of the source and destination node ID differs, the message must go through
the k-th channel of some node somewhere.  If probability is the same for
any bit in the addresses to differ, the probability that the message will
go through a k-th channel somewhere in the cube, is the same for any k.
Since the number of k-th channels in the cube is the same for any k, the
channel ultilization must also be the same for any k.
-- 
/*------------------------------------------------------------------------*\
| Wen-King Su  wen-king@vlsi.caltech.edu  Caltech Corp of Cosmic Engineers |
\*------------------------------------------------------------------------*/