|
|
|
|
|
|
|
Figure 8.49
(a) Successive message transmission in a static
network through an intermediate node with store and
forward. (b) Relative message timing at a node with
wormhole routing. Header contains address of
destination path. |
|
|
|
|
|
|
|
|
when recognized, can improve systems performance by placing communicating processors at adjacent nodes in the system. Note that there is little advantage to siting a node in a k-ary (k > 2) unidirectional system, as adjacent nodes for an A to B transmission (distance = 1) will require a distance k - 1 for the B to A transmission. |
|
|
|
|
|
|
|
|
Associated with the link characterization is the length of the message in bits (l) plus H header bits. (The data portion of the message is frequently referred to as the ''payload.") Thus, Tch´ (l+H) / w will be the time required to transmit a message between two adjacent nodes and, in general, the total message transmission time is: |
|
|
|
|
|
|
|
|
where d is the distance between the two nodes and h is H/w, the header bit time. The preceding assumes that the node itself has a store and forward character. Suppose node A has a message for node C, which must be transmitted via node B. If node B is available, the message is transmitted from A to B and stored at B. After the message has been completely transmitted, node B accesses node C and transmits the message to C if C is available. An alternative to store-and-forward is wormhole routing. Under this scheme, as the message is received at B it is buffered only long enough to decode its header and determine its destination. As soon as this minimal amount of information can be determined, the message is retransmitted to C, assuming that C is available. The amount of buffering then required at B is significantly reduced and the overall time of transmission is decreased to: |
|
|
|
 |
|
|
|
|
Twormhole = Tch[d h + l/w], |
|
|
|
|
|
|
|
|
where h is the number of header bit times. |
|
|
|
|
|
|
|
|
There is a slight variation to wormhole routing called virtual cut-through [64], differing from wormhole routing in that only messages that are blocked |
|
|
|
|
|
