2.3.2 Variable-length messages

In the preceding discussion we assumed that packets were atomic. However, the algorithm as well as the analysis extends naturally to the case in which we have messages each consisting of several packets.

 

We can trivially prove the theorem by organizing the operation of the network into message cycles each consisting of m steps. During a message cycle, each node in the network can send and receive a single message on each edge. This is equivalent to a packet routing problem in which packets take m steps to cross each edge, and hence must complete in message cycles, or steps.

We note however that synchronizing the operation of the nodes into message cycles as described above is not necessary. In particular, it is possible to allow two changes:

1. Each node can operate upon the next message as soon as it is done with the previous, rather than having to wait until the end of the current message cycle. This will be useful if most of the messages are small.
2. It is possible to pipeline message transmission. Thus a node can start forwarding the first packet of the message with the smallest rank as soon as every incoming queue receives the first packet of its message. To achieve this, messages must be transmitted in a special format. Specifically, the rank must be placed in the leading packet in the message, followed by the destination address, followed by a type field that indicates whether the message is real, or a ghost or an EOS, with the data trailing at the end. If the rank cannot be accomodated in one packet, then the more significant bits of the rank must be transmitted before the less significant ones. With the message format as above, it is possible for each node to send outgoing message packets as soon as the corresponding packets arrive on all incoming edges. In fact message combining can also be made to work with pipelining [30, 31].

It is possible to show that Theorem 2.12 still applies. The analysis involves constructing a delay sequence and a counting argument similar that for Theorem 2.9.