[Coin] Compute on the Forwarding Node and Semantic Routing

[Adrian Farrel <[e-mail]>]

Finally (honestly ;-) I get to my last thread on Semantic Routing.

This concerns the concept of compute on the forwarding node.

Again (sorry to keep repeating this) we are talking about the IP-layer
forwarding node that has the job of forwarding a packet to the next hop on
the path from one "network component" to the next, or to the final
destination. It is not tasked with determining the next network component to
see the packet, nor with performing the functions of the network component.

Such forwarding nodes may perform semantic routing, as described in the
previous threads. In making the forwarding decisions, the forwarding nodes
may use algorithms to build the forwarding tables, and/or they may use
algorithms that are more sophisticated than keyed lookups to determine the
next forwarding hop for a given packet.

The previous thread on programmability and SDN deals with how the forwarding
table may be installed from a controller, and how the forwarding nodes may
be instructed to extract lookup keys from the packets.

This thread is about the algorithms used on the forwarding nodes since those
algorithms use "programs" and "CPU".

Algorithms that construct forwarding tables may be installed at "build
time". This may mean that they are burnt into silicon, or they may be
pre-installed software. Historically, that is how routers have worked. These
algorithms may also be updated through software updates (often requiring
that the node is restarted, or at east has a "lumpy moment" when the
switchover to the new software is made). All modern routers and whitebox
routers work this way.

Possibly the algorithms to construct forwarding tables are not so
interesting to us in this context. They could be highly dynamic, they could
use ML/AI, they could use a lot of performance data gathered from the
network. But they don't operate on a per-packet basis, and they are not in
the forwarding path for the packets (even though they impinge on those
paths). The "compute in the network" is there (it is there today in deployed
networks!), but it is not performing computation on the packets or their
content.

An interesting existing example of this is the "IGP Flexible Algorithm" work
(https://datatracker.ietf.org/doc/draft-ietf-lsr-flex-algo/).

So we should turn out attention to algorithms that process the information
stored in the packets and determine how to forward them. These algorithms
would, I think, qualify for the description "compute in the network." Jon C
mentioned in an earlier email the work done to experiment with putting
processing instructions in packets so that it could be actioned along the
path, but that may be too radical. The more likely overlap between Semantic
Routing and this type of compute in the network is:
- packets carry markers and information that can be accessed by transit
nodes
- transit nodes are "programmed" with a range of algorithms that they can
use
  to determine the next hop for a packet they are forwarding (such
programming
  could be "in advance" such as build time, or could be more dynamic such as
  through SDN)
- when a packet arrives at a node it uses the default algorithm or picks one
  based on information in the packet
- the chosen algorithm is run on the packet (specifically the Semantic
Routing
  information) and probably on the current network state information, and 
  produces a decision of the next hop on the forwarding path

Again, some of this is already finding its way into the engineering side of
things: witness the use of a Segment Routing SID to identify which
forwarding table to use (i.e., which IGP flex-algo was used to construct the
forwarding table) on a per packet basis. But that example is not really
per-packet compute in the network because the compute is the semi-offline
construction of the forwarding table, not an active decision on how to
forward each packet.

As described in the "challenges" work, one significant concern with this
approach is that it may lead to different network nodes performing different
algorithms that lead to forwarding loops or data sinks. Clearly the
coordination of network programming and the debugging of active networks
becomes quite important.

Some people view the stability risks of an SDN approach to programming this
type of compute in the network as being so high that, no matter how exciting
the possibilities are, there is no point in playing with it until the
coordination and debug issues can be resolved. These people think that such
compute should be more stable, "standardised" (at least as far as objective
functions), and pre-installed in network nodes.

This is, in my opinion, the biggest overlap between Semantic Routing and
COIN. It is definitely NOT the case that all Semantic Routing approaches
would use compute in the network. But it is certainly possible that this
form of forwarding decision-making could use compute in the network.

[Unless you want to count NOP (0x90 for people of my generation) as a
program, in which case everything is compute in the network :-) ]

Cheers,
Adrian