🚀 go-pugleaf

In article <291@hubcap.UUCP> wen-king@VLSI.CALTECH.EDU (Wen-King Su) writes:
>
>In article <285@hubcap.UUCP> ravi@CS.UCLA.EDU writes:
><>The obvious solution to this problem is to randomly choose the direction
> <in which the message should be routed, i.e. randomly choose one of the
> >bits that differ instead of scanning from right to left or left to right. 
> <Another possibility is that one could start the left to right scanning for 
> >each message at a randomly chosen bit for that message. 
>
>If you do this, you may have problems with deadlock due to lack of queue
>space along the path of the message.  One reason for using the routing
>algorithm described by pase in his article is that the algorithm is proven
>to be deadlock free provided that the destination node will eventually
>consumes all messages it receives.  This particular routing algorithm is
>call the e-cube routing algorithm.

I can see the possibility that a message will never reach its
destination when it is routed in an arbitrary direction (no longer
shortest path routing) instead of a direction towards the destination. 
A case can be made for doing this in a congested situation when buffers 
in the chosen direction are full. 

However when one chooses a direction toward the destination I 
see no reason why it should deadlock. I would appreciate if you
can give us the argument as to why it deadlocks or any references pointing
to the deadlock proof. 

ravi

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
T. M. Ravi 
UCLA Computer Science Department, 3680 Boelter Hall, UCLA
Los Angeles, CA 90024	          Phone: (213) 825-2266
ARPA : ravi@CS.UCLA.EDU
UUCP : {...sdcrdcf, ihnp4, trwspp, ucbvax}!ucla-cs!ravi
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~