|
|
|
|
|
|
|
Figure 8.55
Message transmission from node to switch. |
|
|
|
|
|
|
|
|
The network switches have no storage. If a block is detected, a queue develops at the processor node; so there are N queues, each with occupancy r, requesting service from the network. Since the number of connection lines at each network level is the same (N), then expected occupancy is r. Thus, as shown by Kruskal and Snir [172], the delay for an open-queue model (arrival traffic is not affected by waiting time) can be modeled by an MB/D/1 open queueing model where p = d/k and d = r (the probability that a request is made during a service time), so that p = r/k. The binomial queueing model is appropriate here, since the output can be accessed by only one of k input ports with equal probability and the probability of a request from a source is simply d = r. The message time is Tm = (l/w) Tch and also corresponds to the time a switch (node) is occupied by a message. The channel occupancy is r = m ´ l/w, where m is the probability that a particular node makes a request in any cycle. In the remaining discussion, we assume the Tch = 1 cycle and express time in cycles. |
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
The total message transit time (h = 1), Tdynamic, is: |
|
|
|
|
|
|
|
|
A similar analysis may be performed on a static (k, n) network; but now the analysis is a bit more complicated and requires the use of the M/G/1 open queueing model. Let kd be the average number of hops required for a message to transit a single dimension. For a unidirectional network with closure  , and for a bidirectional network  (k even), the total time for a message to pass from source to destination is: |
|
|
|
|
|
|
|
|
Again, we assume that Tch = 1 cycle and perform the remaining computations on a cycle basis. Now the arrival rate on a channel is: |
|
|
|
|
|
|
|
|
where m is the probability of a message request being initiated in any cycle, and n kd is the expected number of message hops (hence cycles) for the message to transit to a destination. |
|
|
|
|
|
