1 Centralised (!) Routing - Fibbing (see fibbing paper for more details - esp. figure 9/10 on failure/recovery modes) - in particular, fail-open and fail-close is used in the paper to refer to the persistence of a path made up by fibbing in the event of a controller failure where in some cases this is needed, and in others it needs to be removed! [1,2]
2 Stateful Routing - MPLS. Multi-protocol label switching has a long history (probably started in Cambridge!). It simplifes switch/router design in terms of forwarding, at the cost of increasing complexity in the control plane -- possibly in routing, but more crucially, signaling. Signaling protocols have a very long history (from railways over 200 years ago). One interesting computer science dimension that arose from signaling is the concept of mutual exclusion. The first algorithms for avoiding contention for a limited resource are direct descendents of the P and V flags used to prevent two trains entering the same section of track....
In a sense, these two ideas (central and stateful) can be reconciled via "soft state" protocols (see final lecture).
Note also: MLPS involves a "shim" layer between IP and lower levels. Segment routing may use that, or may just use IP6 routing options directly. Recall layering from IB networking course. It is often not a pure picture - IP tunnels are another example of extra layers between this and that. MPLS can also simplify switch & router port processing (and possibly, if switch is "cell switched" scheduling forwarding packets across the switch fabric - again, recall router architecure from IB networking course). Segment Routing is a re-think of MPLS, which can use IPv6 routing options as labels, and then use IP routing updates to distribute the label information to ( amongst others, upstream) neighbours. There's a nice slidepack SR explainer from CERN which shows the interaction with routing... Note segment routing with IPv6 dispenses with the potential hardware speedup of having 20 bit MLPS labels for forwarding, so one assumes router NICs and Processors may have ASIC support for v6 header processing!
So fibbing refines routing by adding FIBs which splits traffic into different paths, but MPLS coarsens it by bundling flows into the same forwarding paths/treatments.
Optional background reading...
2. Another dimension of signaling is that it requires a level of accesss control authentication and authorisation not typically present in pure datagram networks like traditional IP. For a measure of how bad it can get, look no further than the old digital telephone network signaling system number 7 (SS7) which is more complex than the whole TCP/IP regular data stack (see report on vulnerabilities in SS7). RSVP (serves similar function for signaling for MPLS if you don't just rely on routing!) is about as bad.
1. Further work was done based on the fibbing idea
https://sites.uclouvain.be/defo/
The core family of algorithms that could run in the controller.
Basically, it leverages FIBbing-like mechanisms to optimize (oblivious) TE in IP networks.
This paper is about the hardness of configuring ECMP for TE. This is actually based on a very cute hardness amplification proof technique.
Good question asked about stochastic & multipath routing - yes, you can do stochastic unipath (i.e. keep changing the route based on statisitcs) but it is more common load balancing/multipath scenarious...
Mneahile, back to MPLS - (and see later under differentiated services) - we have the idea of a packet flow, identified by some fields in the IP or possibly IP and TCP (or UDP or UDP/QUIC) Headers - between one packet and the next in the same forwarding equivalence class, some fields remain unchanged - a handy way to look at this comes from a completely different source, that of TCP/IP header compression! here's the key fields (shaded stay same):
From:
https://mirrors.ircam.fr/pub/rfc/rfc1144.pdf
A simple type of Fowarding Equivalence Class is one end-to-end flow, which can uniquely be identified (at a given time) by the 5-tuple of source+destination IP addresses, TCP (or UDP) ports and protocol id - i.e 2*32 bit fields, 2*16 bit fields and one 8 bit field.
We can also use an IP ToS field called the DS byte for an even coarser grain grouping of packets, but using the above gives us an individual end-to-end packet flow....of course we could also wild card some fields (e.g. source address) to group all the packets/flows to a given destination, or use IP prefixes (not all 32 bits of the IP destination address) to get all the packets to some particular network, rather than specific host.
Question: Why are MPLS labels local only? Answer - this lets them be small number of bits (order the numner of overall flows through a given router, rather than the number of possible flows in the world ever, which is what the 5-tuple would represent). BUt because it is local, we need to distribute the mapping from each hop to previous hop.
