i’ve been thinking more about what it actually takes to change a running network. choosing a better route is one problem. getting traffic onto that new route, while the network is still carrying packets is whole different ball game. i hadn’t given that second part much thought until lately.

my first instinct was pretty straightforward: calculate the new routes, check that they work, and push the forwarding rules to the switches. this instinct was without consideration that the switches probably won’t all apply those rules at the same time, and while they’re updating, packets are still moving between them.

coming at this problem from a distributed systems approach, the first part feels familiar. different participants can be at different stages of an update. what makes the networking version interesting is that a packet keeps moving through those participants, picking up a forwarding decision from each one. so the question i raised is: if the old routes work, and the new routes also work, can changing between them still break the network?

turns out, you only need two forwarding switches to cause tradgedy.

two working configs

suppose we have network switches A and B, and some destination D. the switches can forward packets to each other, and each has a direct link to D. to be concrete, we’re talking about layer 3 switches performing IP routing here: each switch looks at the packet’s destination IP address and decides where to send it next.

say all the links are healthy, and we’re making a planned routing change, and, for now, assume every link has enough capacity.

these are the rules before and after the change:

switch	old rule for destination D	new rule for destination D
A	send to B	send directly to D
B	send directly to D	send to A

under the old config, a packet arriving at A takes A -> B -> D, and a packet starting at B goes straight to D. under the new config, the arrangement flips, a packet arriving at B takes B -> A -> D, and a packet arriving at A goes directly to D. both of these configs deliver the packets, and neither contains a loop.

updating the wrong switch first

say B applies its new rule before A does, it’s trivial to see that this’ll create a A -> B -> A -> B ... pattern. nothing crashed, neither switch misinterpreted its instructions, we just combined two individually valid pieces of different configs, and now we have a loop!

the loop’s gonna last until the rules change again; an individual IP packet can also exhaust its TTL or hop limit and get dropped. either way, the fact that the network will eventually settle on a working config doesn’t help a packet caught in the transition.

what i’ve just described is a small example of a transient forwarding loop. the failure lives in the intermediate state, which means checking only the initial and final configs misses it completely.

naturally, at this point, you should also be able to see that “push both switching table updates at once” is a pretty unsatisfying answer to this problem – sending two requests doesn’t make thier effects simulatenous, B can still finish first.

let’s fix this by giving the update an order

for this update, the obvious fix is to update A first. once A sends directly to D, we can safely let B start sending to A. the sequence then becomes the table below:

switch	A sends to	B sends to
before the update	B	D
after updating A	D	D
after updating B	D	A

if we take a snapshot at any of these stages and follow the installed rules, we reach D.

the dependency here is quite trivial, before B relies on A to get packets to the destination, A needs to stop relying on B. this is the basic idea behind ordered forwarding-table updates: constrain the sequence so that incompatible rules don’t create a transient loop. in a larger network, figuring out those dependencies becomes part of the update algorithm.

there’s already an implementation detail hiding in “update A first.” it has to mean that A’s forwarding behaviour has actually changed before we change B. putting A’s request first in the controller’s send queue doesn’t establish that. even if we get the order right, there’s another thing to account for.

the packet doesn’t see a snapshot

going back to the old config, A has just sent a packet toward B. before B processes that packet, we perform our carefully ordered update: A changes first, then B changes. perhaps the packet is waiting in a queue while this happens – here’s what the packet could experience:

1. at A, the old rule sends it to B.
2. the updates complete: first A, then B.
3. at B, the new rule sends it back to A.
4. at A, the new rule sends it to D.

the complete path now is: A -> B -> A -> D. sure it gets delivered, but it has a revisited switch, and that traversed path belongs to neither config. every installed snapshot was free of cycles, yet this packet crossed between snapshots while moving through the network.

this kinda hints at the fact that the packet’s history matters too. in this tiny example, we could update A, wait for packets sent along the A -> B path to clear B, and only then update B. this requires a way to know they’ve cleared, or some defensible upper bound on how long that takes.

let the packet carry the version

per-packet consistency gives that requirement a name: each packet should be processed according to the old config or the new one throughout its journey.

one general way to provide it is to attach a config version to packets as they enter the network. switches match on that version as well as the destination.

concretely, for our example, the rules become:

switch	packet marked v1	packet marked v2
A	send to B	send to D
B	send to D	send to A

now, consider the packet that was already travelling from A to B. say it carries v1. even after we start admitting v2 traffic, B will still send those particular v1 packets to D.

a new v2 packet entering at B takes B -> A -> D. the point i’m trying to make here is that transit switches don’t end up relabelling packets just because their default for newly entering traffic has changed.

so, the versioned update process might look something like this:

1. install the new version’s rules everywhere they’re needed, alongside the old rules. confirm they’re active before admitting new-version traffic.
2. change the network’s entry points to label arriving packets with the new version. different entry points can change at different times because both versions are supported.
3. once the old-version admission has stopped (and those packets have drained), remove the old rules.

applying the steps above to our example: we first add the v2 column, without touching v1. then, incoming traffic starts selecting v2. finally, when no v1 packets remain, that column can disappear.

what versioning asks from the network

versioning solves the transition by keeping both configs available at the same time. that is also its main cost. in our example, the switches temporarily hold four forwarding entries instead of two. a real update may reuse rules that haven’t changed, but any affected old and new rules still need to coexist. not to forget, packets also need somewhere to carry the version and the switches need to be able to match on it.

installing the new version creates another requirement. before the network admits a single v2 packet, every switch it might encounter must have its complete v2 rules installed. this is where atomic updates at an individual switch can help. for example, P4Runtime’s optional DATAPLANE_ATOMIC mode allows a packet processed by one switch to see its forwarding table either before or after a batch of changes, rather than somewhere in the middle. that guarantee is local to the switch. versioning solved a different problem: it preserve’s the packet’s choice of configuration as the packet travels between switches. we need both ideas to hold at their respective boundaries – the new rules must be installed cleanly at each switch, and the packet’s version must select the same configuration across all of them.

we also can’t consider the update to be finished when the entry points begin marking new packets as v2. old v1 packets may still be moving through the network. if we immediately delete B’s v1 entry, a packet already travelling toward B can arrive and find that the rule it depends on no longer exists. this reminded me of read-copy-update: publishing a replacement and knowing that nobody is still using the previous version are separate events. here, the packets are the outstanding users of the old forwarding rules – only after those packets have drained can we remove the old rules, recover the table space, and eventually reuse the version identifier.

and it still doesn’t solve everything

per-packet consistency makes one narrow promise: a packet follows one complete forwarding configuration.

it does not promise that the new routes have enough capacity either. we assumed every link could carry the traffic placed on it. removing that assumption means an update could remain perfectly consistent while temporarily congesting a link. versioning prevents packets from being stranded between two configurations. packet ordering, congestion, and the performance of the transition are separate problems.

turns out calculating a new route is the easy part. teaching a running network how to change its mind mid-air without dropping traffic is where things get fun.

~ a.k