🚀 go-pugleaf

pase%oregon-grad.csnet@RELAY.CS.NET (Douglas M. Pase (me)) writes:

	000 -> 001
	000 -> 010
	000 -> 001 -> 011
	... etc
-The channel between nodes 0 and 1 is used in four different cases, between 0
-and 2 in two cases, and 0 and 4 in only one case.  [...]


elroy!wen-king%cit-vlsi.Caltech.Edu@seismo.css.gov (Wen-King Su) writes:

-    000 -(0)-> 001
-    000 -(1)-> 010
-    000 -(0)-> 001 -(1)-> 011
-    000 -(2)-> 100
-    000 -(0)-> 001 -(2)-> 101
-    000 -(1)-> 010 -(2)-> 110
-    000 -(0)-> 001 -(1)-> 011 -(2)-> 111
-
-On the countrary, I counted that channels 0, 1, and 2 are each used
-exactly 4 times, though they are not all channels coming out of node
-0.  [...]

I see your point, but I think it doesn't help.

                                          110-------------10---------------111
                                          /|                               /|
                                         / |                              / |
                                        1  |                             2  |
                                       /   |                            /   |
                                      /    7                           /    6
                                    010---------------9--------------011    |
000 -(8)-> 001                       |     |                          |     |
000 -(4)-> 010                       |     |                          |     |
000 -(8)-> 001 -(5)-> 011            |     |                          |     |
000 -(0)-> 100                       4     |                          5     |
000 -(8)-> 001 -(3)-> 101            |    100-------------11----------|----101
000 -(4)-> 010 -(9)-> 110            |    /                           |    /
000 -(8)-> 001 -(5)-> 011 -(2)-> 111 |   /                            |   /
                                     |  0                             |  3
                                     | /                              | /
                                     |/                               |/
                                    000---------------8--------------001

The intent of the previous article was to find a solution to the following
problem:  Assume every node communicates with every other node with equal
probability.  Minimum response time will be achieved if all channels (0-11)
are used equally.  Excess contention will occur if one channel receives heavier
usage than the others.  This, of course, assumes sufficient message traffic.
What then would be a static routing algorithm which would uniformly distribute
the messages over the channels?

Again, assuming uniform message traffic, the previously posted algorithm will
place the most messages on channels 8, 9, 10 and 11.  The message traffic will
be twice that of channels 4, 5, 6, and 7, and four times that of channels 0,
1, 2, and 3.  Clearly, a dynamic approach which moves the message nearer to
its destination and sellects the channel based on traffic at that time will
be the big winner.  However, I am looking for a static algorithm which will
uniformly distribute messages over the channels.  The random algorithms are
an interesting possibility I had not thought of, but I'm hoping for a
deterministic (not random) approach.  (I can get it through enumeration, but
that approach is very expensive.)
--
Doug Pase   --   ...ucbvax!tektronix!ogcvax!pase  or  pase@Oregon-Grad.csnet