In the following, we assume a Myrinet network of general topology, consisting of hosts and switches and pairs of unidirectional links. The links forward arbitrary-length packets, which are routed through the switches in wormhole manner. As reflected by the name, the process of routing and transmission of a packet is like the movement of a worm. Whenever the header of a packet reaches a switch, the remaining portion of the packet is forwarded to the desired outgoing port (if available) as soon as the header is decoded, without waiting for the entire packet to reach the switch. Longer packets can therefore extend over several switches. If the desired outgoing port is not available because it is being used for the transmission of another packet, the header of the packet blocks.
Myrinet switches are perfect, meaning that packets do not conflict at a switch unless they are directed to the same outgoing link. There may be as many packets simultaneously traversing the switch as there are outgoing links. If more than one packet must wait, they are served in round-robin manner.
A simple hop-by-hop STOP/GO flow control mechanism (which acts as backpressure flow control) ensures that a packet blocked at a switch blocks at the upstream switches as well. Since only a small buffer is associated with input ports at each switch, the packet can easily be blocked up to the sender.
In order to streamline the packet processing at switches, source routing is used. A source host determines the route to a destination (a list of switches and output ports) and places it into the header of the packet. When the header arrives at the switch, the router reads the information and determines the desired outgoing port. Then it is forwarded through the specified output port to the next switch.
In conjunction with its flexible point-to-point topology, this results
in a low-cost but scalable networking technology that provides
guaranteed delivery of packets at very high speed and low latency.
Figure 1 shows a snapshot of a wormhole network with
a number of packets in traffic. In this example, the network consists
of six hosts 
, which are connected by nine
switches 
, forming a mesh.
Figure 1: Network with Packets in Transit
In this example, Packet 
is being blocked on the link between
and 
by Packet 
. Packets 
and , on the
other side, do not affect each other, although they use the same
switch 
. This example illustrates also how a packet can be
indirectly blocked by another packet: although and 
do not
directly contend for a link, indirectly blocks by blocking
, which in turn blocks on the link from to .
Once the head of the packet reaches the destination, the remainder can
be sent at potentially full link bandwidth (of 640 Mb/s or 1.28Gb/s in
the case of Myrinet). In order to bound packet delivery delay due to
blocking during path setup, however, proper connection acceptance and
connection management strategies must be devised. In the following,
we assume that connections adhere to a periodic traffic specification.
Each connection is of type 
, where 
specifies the route followed by packets of 
, 
defines the
worst-case message length (in terms of transmission time), and 
specifies the worst-case interarrival time of packets of .
We assume without loss of generality that the packets of Connection
enter the network at Switch 
and are routed along the
sequence of switches 
. For convenience we call the sender host 
and the
receiver host 
. Assuming a round-robin service policy in the
switches, we can determine the worst-case blocking time
experienced by a packet of connection because of
contention for the outgoing link at Switch 
.
The worst case happens when all packets contending for the same output
link at arrive just before the packet of . All these
packets may in turn be blocked at downstream switches. The worst-case
blocking delay at Switch can therefore be defined by
the following recurrence relation:
In the above recurrence relation n is the number of ports of Switch
; 
and 
are the input and output port,
respectively, of Connection at Switch ;
denotes the set of connections that use Port p as
input port and Port q as output port at Switch . To simplify
the notation, in the following we will generally omit the index k for
if it can be deduced from the context.
We say that a connection 
branches in with at Switch
if the two connections use different input ports but share the
same output port at Switch . Using the notation above: 
and 
. The set of all connections
branching in at with at Switch is denoted by 
.
Similarly, a connection is said to branch out from at
Switch if the two connections share the input port but have
different output ports at , i.e., 
, but
. The set of all connections branching out from
at is denoted by 
.
Relation( 1) allows for a very simple (though expensive!)
centralized admission control scheme. With our simple periodic
traffic model we can use the following formula to test whether packets
of connection can successfully be delivered before the end of
the period:
that is, whether for all connections the worst-case blocking time at their entry to the network plus the transmission time does not exceed the period.
For a new connection to be accepted, we centrally determine whether (i) the timing requirements of the new connection can be satisfied and whether (ii) the timing requirements of existing connections are not violated. Since the admission of a new connection can potentially affect all previously established connections, the cost of this operation grows quadratically with the number of accepted connections. Computationally less demanding methods must be devised, in particular for systems with connections that are dynamically established and torn down.
In the following section, we describe a fully distributed admission control scheme that has a time overhead that grows linearly with the diameter of the network.