SpaceWire routing switches employ wormhole routing. When a packet starts to arrive at an input port of a router, its destination address is looked at immediately. If the output port that is to be used to forward the packet towards its destination is not currently being used, the head of the packet is sent to that output port straightaway, with the rest of the packet following as it is received at the input port. There is no buffering of complete packets in the router, neither before, nor after switching.
Wormhole routing has a number of advantages over other approaches like store and forward:
- No packet buffering
- Little buffer memory
- Can support packets of arbitrary size
- Rapid switching
Wormhole routing suffers from one main problem, that of blocking. If the output port that the packet is to be forwarded through is not ready or is currently being used, the packet has to wait until it is ready or the packet currently flowing through it has finished. Since the tail of a packet can be spread out through the network, not only is the waiting packet halted, but that packet blocks any other packet in the network that is waiting to use the links that it is currently occupying. This is illustrated in Figure 55.
Figure 55 Packet Blocking
A long packet it being transferred from node 1 to node 5, shown in blue. Another packet, shown in red, wants to go from node 2 to node 5, but since the link from router 2 to node 5 is already in use, the red packet is blocked in router 2. A third packet, shown in yellow, wants to go from node 3 to node 6. This does not use any of the links being occupied by the first packet (blue), but it is blocked by the waiting packet (red) in router 1 since it has to travel over a link from router 1 to router 2. Once there is a blockage its effect can multiply, causing further blockage throughout a network.
Blocking can occur for several reasons:
- A large packet is being sent;
- The destination of the packet is not ready to receive it;
- Something has gone wrong on the network, e.g. a link failure, so that a packet cannot move forward across the failed link.
There are some strategies that help to avoid blocking a network:
- Split large packets up into many smaller ones, e.g. an image could be sent as a series of image lines;
- Make sure that the destination is ready before sending the packet, which can be done using an end-to-end flow control mechanism;
- If the destination is not ready to receive a packet it can simply throw the packet away, this can be combined with a retry mechanism to implement flow control, although it might result in inefficient use of network bandwidth if the destination is often not ready.
- If a packet does get blocked for longer than might be expected, indicating that a fault has occurred, detect this using a watchdog timer and discard the blocked packet.