Path: utzoo!utgpu!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!agate!bionet!apple!bloom-beacon!tut.cis.ohio-state.edu!ukma!gatech!hubcap!grunwald
From: grunwald@m.cs.uiuc.edu
Newsgroups: comp.parallel
Subject: Re: Wormhole Routing
Message-ID: <3463@hubcap.UUCP>
Date: 7 Nov 88 18:58:35 GMT
Sender: fpst@hubcap.UUCP
Lines: 51
Approved: parallel@hubcap.clemson.edu

Consider the following:

	2 <- C -> 3
	^	  ^
	|	  |
	D	  B
	|	  |
	v	  v
	0 <- A -> 1

have every node send messags to every other node. The following is the
``worse case'' analysis:

Assume that it takes a single time unit to establish connection over a
single link.

Consider the following messages (same case applies to all other nodes by
symmetry)
	Msgs	   Route				Holds
----------------------------------------------------------------------	
	0 -> 1	uses link 0 at 0			#0 for 1 unit
	0 -> 2  uses link 1				#1 for 1
	0 -> 3  uses link 0 at 0, link 1 at 1		#0 for 2, #1 for 1

where ``holds'' means how many time steps the link is held when establishing
a circuit (i.e. during routing).

in general, with uniform routing, ~1/2 the msgs start on link #0,
~1/4 on link #1, etc.

the only other nodes using link zero are adjacent nodes (assuming we're
using a left-to-right ordering for resolving bits in the ecube routing),
and that's for traffic directed to node 0.

However, two messages are queued at node 0 to use link 0. The utilization
of link 0 is going to be higher than for the other links. Admittedly, this
is for the case where we're only routing messages, and not sending data.
As you send data that takes X time units to send, the routing time is
minimized and the difference in link utilization becomes meaningless.

In a worm-hole network, you have a similar problem if the route probe
blocks along the way. You're holding all those resources for several
units of time. If you model the probability of blocking at a link as
the expected time to wait for that link acquisition, you'll find that
link #0 will again be used more often than higher numbered links.

Of course, when you begin to send any reasonable amount of data, or if
you restrict yourself to small networks, this isn't a problem.
However, it's silly for real hardware to use straight Ecube anyway
unless you need to have deadlock free routing. You can do an
exhaustive search (which, remarkably, is very effective) and get much
better performance (balanced link utilization + avoid hot spots).