An on-chip network moves 256-byte packets across four routers. Its first version took 72 cycles per packet with the network idle, three times what the designers expected from the wire and router delays. Every router was fast. The time went into waiting for something that does not need to be waited for.

When may a router start sending a packet on, and what does the choice cost?

The obvious answer, and why it breaks

The obvious design receives a whole packet, checks it, and only then forwards it. That is simple and safe: the router knows the packet is complete and intact before passing it on. But every router then pays the full time to receive the packet, its serialisation time, and over many hops those add up. A router only needs the header to decide where a packet goes; the rest can follow.

The idea: three switching modes

With H hops, a packet of L flits at one flit per cycle, and r cycles of routing per router, the latencies with no contention are:

Store-and-forward pays the serialisation L at every hop; cut-through and wormhole pay it once. With no contention, cut-through and wormhole behave identically. They differ only in what happens when a packet is blocked: cut-through needs room for the whole packet in each router so it can collect it there, while wormhole saves that buffering and leaves the packet strung across the path, holding links that other packets may need.

Build it: latency of each mode

The model evaluates both formulas for a 256-byte packet of sixteen 16-byte flits across four hops, with two cycles of routing per router.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

"""Latency of a 256-byte packet across 4 hops under three switching modes.

Links carry 16 bytes per cycle (one flit per cycle). Each router adds 2 cycles to make
its routing decision. Illustrative numbers.
  store-and-forward: each router waits for the whole packet before sending it on
  cut-through:       a router forwards as soon as the header arrives (buffers a whole
                     packet only if blocked)
  wormhole:          like cut-through, but a blocked packet stays spread across routers,
                     holding a few flit buffers in each
With no contention, cut-through and wormhole have the same latency; they differ in buffering.
"""
P, F, HOPS, T_ROUTER = 256, 16, 4, 2
flits = P // F                                   # cycles to serialise the packet on one link
saf = HOPS * (T_ROUTER + flits)
ct = HOPS * T_ROUTER + flits
print(f"packet: {P} B = {flits} flits; {HOPS} hops; {T_ROUTER} cycles per router")
print(f"store-and-forward: {saf} cycles")
print(f"cut-through:       {ct} cycles")
print(f"wormhole:          {ct} cycles (no contention); buffers per router: a few flits, not a packet")
assert saf == HOPS * (T_ROUTER + flits) and ct < saf
print("PASS: store-and-forward pays the packet's serialisation at every hop; cut-through pays it once")

It prints:

packet: 256 B = 16 flits; 4 hops; 2 cycles per router
store-and-forward: 72 cycles
cut-through:       24 cycles
wormhole:          24 cycles (no contention); buffers per router: a few flits, not a packet
PASS: store-and-forward pays the packet's serialisation at every hop; cut-through pays it once

At four hops, 72 cycles against 24: store-and-forward spends 64 of its 72 cycles receiving the same packet four times. At one hop the two are equal, which is why the difference only matters in multi-hop networks.

The design space

How real systems chose

• On-chip networks almost always use wormhole switching with virtual channels: lowest latency with the least buffer area, and the deadlock risk handled by routing rules and channel classes.

• Network switches offer store-and-forward and cut-through: store-and-forward can drop corrupted frames before forwarding them; cut-through gives lower latency where that matters.

What breaks

The opening network (illustrative) used store-and-forward routers because they were simple to verify. Moving to wormhole cut the idle latency from 72 to 24 cycles, and then the first heavy-traffic simulation deadlocked: two long packets, each strung across several routers, each waited for a link the other held. Wormhole's saving in buffers had turned a blocked packet from a local wait into a chain of held links. The design added virtual channels and a deadlock-free routing rule, the subject of Part 9.

Key takeaways

• Store-and-forward pays the packet's serialisation at every hop: H(r + L). Cut-through and wormhole pay it once: Hr + L.

• Cut-through keeps a packet of buffer per router for blocked packets; wormhole keeps a few flits and leaves blocked packets strung across routers.

• On-chip networks favour wormhole with virtual channels; the deadlock plan is part of the choice.

Related topics

• Part 4 overview: Flow Control

• Architecture course: Credit Flow Control and Buffers