Conference rusure::math

423.0. "network probability problem" by HYDRA::THALLER () Sat Jan 11 1986 18:54

Consider the following network probability problem.

A network consists of N nodes arranged in a ring.  The ring of nodes is
in fact a double ring with one ring being reserved for transmission in
each direction.  That is, ring R passes data to the right and ring L
passes data to the left.

   .---------------------------------------------------.
   |  .----.     .----.     .----.            .----.   |
   `->| 0  |---->| 1  |---->| 2  |-->  ... -->| N  |---'
   .--|    |<----|    |<----|    |<--      <--|    |<--.
   |  `----'     `----'     `----'            `----'   |
   `---------------------------------------------------'


Now, at any given time, all nodes wish to transmit a packet of data to
another node. (assume a random distribution for the destination node)
The ring chose for transmission is always that ring/direction with the
fewest number of hops or links.  For example, for N>4, node 0 will xmit
to node 2 using ring R and will go through node 1.  This ties up links from
0-1 and 1-2 meaning that node 1 can not transmit on ring R. (ring L is still
available for node 1 and ring R is still available for nodes 2 or greater
wishing to transmit to other nodes than 0 or 1.)
Furthermore, a node may transmit and receive simultaneously but may not
accept data from both rings simultaneously.  Data can, however pass through
a node if the destination is futher down stream.

Question:
	For an N node system, what is the expectation of the number of
transmissions which can occure simultaneously.  Either a formula or
program would be appreciated.

As an example:  For N = 3
all nodes wish to transmit to some other nodes with the following
possibilities.
      Source     number of simult.
    0   1   2      transmissions
D-------------------------------------------
E   1   2   0           3
S   1   2   1           2
T   1   0   0           2
I   1   0   1           2
N   2   2   0           2
A   2   2   1           2
T   2   0   0           2
I   2   0   1           3
O
N                        

Note that in this simple example with only three nodes, the only
limiting factor for number of transmission is that a node can
not receive from two sources.  Traffic does not limit.

Since all configurations are equilly likely, the expectation is
18/8 or 2.25 simulataneous transmissions.

Thanx in advance for any help you can give me.
Let me know if there are any parts needing clarification.

Kurt Thaller

In the example for N=3, the destination nodes are equidistant.
Which ring (L or R) does a source node choose?  Choosing this
to maximize the number of simultaneous transmissions may not be
a reasonable model, because knowledge of all desired connections
is needed.

Also, in determining the maximum number of transmissions given the
desired connections, selecting which connections to (dis)allow to
maximize the transmissions does not seem a reasonable model.

re. 1
For nodes which are equidistant in both directions, an arbitrary selection
is made to determine the ring to use. (will not give the max).

When determining which nodes are (dis)allowed to transmit, assume that all
nodes wish to transmit however they are processed in a random order.
Again, this certainly does not maximize concurrent transmissions, but
selection algorithm is tremendously simplified.  (in actuality will be a
first come, first serve algorithm.)

	Kurt*