Network Control Plane

Nov 5, 2023

Data Plane & Control Plane

Network layer only provide best-effort service: it will put as much effort as possible to carry out the transportation of packages (whatever that means).

Network layer can be subdivided into two different planes that perform different tasks:

Data plane: performs the forwarding of the packets,
Control plane: performs the routing of the packets.

Before discussing the duties of those planes, let’s deepen some network-related topics.

Forwarding & Routing

Network layer’s main tasks are forwarding and routing.

When a packet is traveling from a sender host H1 to a receiver host H2, it will pass through many intermediate routers (R₁, R₂, …, R_n). It is said that a packet is forwarded to the subsequent router when it moves from router R_i to router R_i+1. Forwarding is performed by data plane.

Network layer has to determinate the best path that packets need to follow through the network of routers. This task is performed by the control plane using different routing algorithms.

Forwarding is the local action of with which the router moves packets from an input interface to an output interface. It is usually hardware-implemented since it occurs in a very short time period (nanoseconds). Routing is the global action that defines the packages route from source host to destination host. It is usually software-implemented since it occurs in longer time period (seconds).

In order to forward a packet, the router extracts one or more fields from the packet’s header. It puts those values inside the so called forwarding table. This table will tell the router the right output interface to which forward the packet. Which values to insert into the forwarding tables are determinate by the previously mentioned routing algorithms.

Control Plane Approaches

Routers have to integrate both the planes of Network layer. As mentioned before, data plane is usually hardware-implemented. On the other hand, control plane has experienced an “evolution” from hardware to software.

In the traditional approach, the control plane is hardware-implemented and the routing algorithm is implemented in all every router of the network. The routing functions communicate to each other to choose the values to insert within the forwarding tables.

Unlike the traditional approach, in the SDN approach (Software-Defined Network) the control plane is software-implemented. It makes use of a network entity called remote controller, which is physically distinct from the router. The controller evaluates and distributes the forwarding tables to all the routers. The network is “software defined” since the controller is software-implemented. Those implementations are very often open source!

Introduction to Control Plane

Routing Algorithms

The objective of a routing algorithm is to determinate the path from a source host to a destination host, across the routers network. Usually, the best path is the one with the lower cost.

Routing problems are phrased through the use of graphs. Given N nodes and a set of links E, the graph G=(N,E) is the set of nodes where each link connects a pair of nodes from N. Within the context of routing, graph nodes are the routers, and their physical connections are the links.

Each link is associated with a cost due to:

connection physical length,
connection speed,
connection price

For the sake of easiness, given two nodes $x$ and $y$ :

$y$ is a neighbor of $x$ if $(x,y)$ is an link of E,
the links are bi-directionals $(x,y) \equiv (y,x)$
- $(x,y)$ is the link from $x$ to $y$
- $(y,x)$ is the link from $y$ to $x$
the cost will be approximated to an integer scalar: $c(x,y) \in \N$

The link may also be called edge. The cost can also be denoted with $l(x,y) \in \N$ if you approximate the cost to the connection length. A path in a graph is a sequences of nodes such that each pair of nodes is an link that belongs to E. The cost of a path is the sum of the costs of all the links through the path.

Classifications Criteria

The are many classification criteria, which can also overlap to create complex algorithms suitable for different situations. Each algorithm is a cost/performance trade-off that solves optimization problems with cost functions related to: number of hops, bit-rate, overall or local delay, overall or local throughput, actual cost to power repeaters to send information over a node, cost to pass through a radio base/fiber/satellite physical device.

Centralization

A (routing) algorithm is centralized when the minimum cost path is evaluated by having a global and complete knowledge of the network. The evaluation is performed in a single place, like a controller logically centralized, or replicated in every router in the network.

An algorithm is decentralized when the minimum cost path is evaluated in a distribute and iterative way. Nodes only know the connection costs of the neighbor nodes. Nodes iteratively learn information about the state of the network to calculate the route step-by-step (or, rather to say, hop-by-hop).

Static VS Dynamic

An algorithm is static when the path is resolved in advance: the routing table cannot change over time. The path from a given source to the same (given) destination rarely changes, most of the time because of a human interaction.

An algorithm is dynamic when routing changes over time due to changes in terms of network load or network topology. Moreover, other services may cause the routing rules to change. The routing table is periodically modified. Those algorithms are more sensitive to network changes but are more prone to problems such as loop routing.

Load Sensitiveness

An algorithm is load-sensitive when the connection costs dynamically variate according to the congestion level. The first ARPAnet routing algorithms were of this kind.

On the other hand, an algorithm is load-insensitive when the connection costs is not affected by the network congestion level.

Activeness

An algorithm is proactive when the path is resolved when creating the connection. An algorithm is reactive when the path is resolved as needed, packet by packet.

Consistency

An algorithm is uniform when the alert for algorithm management is sent to all nodes. An algorithm is nonuniform when the alert is only sent to a set of nodes (clustering).

Link State

The LS (Link State) algorithm sends to all network nodes a special packet called LSP: Link State Packet. LS uses broadcast to sent that packet to the whole network. LSP contains information about destination and source addresses: the history of all nodes that have transmitted that packet, plus the cost of the various links. It has up-to-date information on existing links. There is a cost/performance trade-off: the faster the LSP is sent, the more up-to-date the network state, but it takes up more of the network’s time to send overhead information in place of actual data.

Dijkstra Algorithm

This algorithm solves the problem of finding the shortest path. Let’s analyze a centralized version from 1959.

$D(v)$ is the overall cost from source $S$ to a generic node $v$ . Given a couple of nodes $x$ and $y$ , the distance between them is denoted with $l(x,y)$ . If there is no connection between them, then $l(x,y) = \infty$ . Lastly, $N$ is the number of nodes the packet go through, $M$ is overall output number of all the $N$ nodes, and $\mathcal{F}$ is the set of nodes selected for the packet transition.

Algorithm steps:

initialization:
- at first, the set of selected nodes is only the source: $\mathcal{F} = \{S\}$
- all the v nodes have their own distances: $\forall v \notin \mathcal{F},\; D(v)=l(S,v)$
among all the nodes not yet selected, let’s choose the one with lower distance from S:
$w\notin \mathcal{F} \; | \; \forall z \notin \mathcal{F},\;z\neq w,\; D(w)\leq D(z)$
selection of node chosen at step 2: $\mathcal{F} = \mathcal{F} \cup \{w\}$
evaluate new distances starting from $w$ : i.e. passing through the nodes of the updated $\mathcal{F}$ set
if $|\mathcal{F}| < M$ go back to step 2, else stop.

Let’s take a sample network and build the distance table starting from node $A$ , such that $S \equiv A$ .

routing sample nodes

The nodes directly connected with A have the following distances:

\begin{equation} \begin{split} D(B)&=l(A,B) = 2,\\ D(D)&=l(A,D) = 4,\\ D(E)&=l(A,E) = 6,\\ \end{split} \end{equation}

Let’s build a table where $\mathcal{F}$ grows progressively until it contains all the nodes in the network.

$\mathcal{F}$	$D(B)$	$D(C)$	$D(D)$	$D(E)$	$D(F)$
$\small \{A\}$	$2 \\ \scriptsize l(A,B)$	$\infty$	$4 \\ \scriptsize l(A,D)$	$6 \\ \scriptsize l(A,E)$	$\infty$
$\small \{A,B\}$	$2$	$11 \\ \scriptsize l(A,B)+l(B,C)$	$4$	$6$	$3 \\ \scriptsize l(A,B) + l(B,F)$
$\small \{A,B,F\}$	$2$	$7 \\ \scriptsize l(A,B)+l(B,F)+l(F,C)$	$4$	$6$	$3$
$\small \{A,B,F,D\}$	$2$	$7$	$4$	$5 \\ \scriptsize l(A,D)+l(D,E)$	$3$
$\small \{A,B,F,D,E\}$	$2$	$7$	$4$	$5$	$3$
$\small \{A,B,F,D,E,C\}$	$2$	$7$	$4$	$5$	$3$

Note that where the path is not specified (under the cost number), it is equal to the above line’s path. Please note that, in the formula $D(D)=4$ , the inner $D$ refers to the node, while the outer $D$ stands for distance from the source. With $n$ nodes all at the same distance, the chosen one is randomly taken.

The graph below shows how to reach all the various nodes as a result of the Dijkstra algorithm calculations.

Routing Sample Resolved

Bellman-Ford Algorithm

B-F routing algorithm is centralized. Unlike Dijkstra, it sets the destination $d$ . Given the node $i$ and the iteration number $h$ , then $D_i^h$ is the distance from node $i$ to destination $d$ at the $h$ -th algorithm iteration. Keep in mind that the path starts from the node $i$ and arrives to the destination $d$ .

Algorithm steps:

initialization:
- $D_d^h =0\;\forall h$
- all distances are infinite: $D_i^0 = +\infty \; \forall i \neq d$
selection of node $i$ within the path from $k$ to $d$
- $D_k^{h+1}=\underset{j}{\text{min}} \big\{D_k^h,l(k,j)+D_j^h \big\}\;\forall k \neq d$
- $i = \underset{k \neq d}{\text{arg min}} \big\{D_k^{k+1}\ \big\}$
if $D_i^{h+1}=D_i^h\;\forall i$ then stop, else go back to step 2

Let’s take the same sample network. Given the destination $d=A$ .

routing sample nodes

Within step 2, you have to take all the $j$ nodes which are at most $h$ jumps away from the destination.

$h$	$D_A^h$	$D_B^h$	$D_C^h$	$D_D^h$	$D_E^h$	$D_F^h$
$\bold{0}$	$0 \\ \scriptsize l(A,A)$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
$\bold{1}$	$0$	$2 \\ \scriptsize l(B,A)$	$\infty$	$4 \\ \scriptsize l(D,A)$	$6 \\ \scriptsize l(E,A)$	$\infty$
$\bold{2}$	$0$	$2$	$10 \\ \scriptsize l(C,E)+l(E,A)$	$4 \\ \small$	$5 \\ \scriptsize l(E,D)+l(D,A)$	$3 \\ \scriptsize l(F,B)+l(B,A)$
$\bold{3}$	$0$	$2$	$7 \\ \scriptsize l(C,F)+l(F,B)+l(B,A)$	$4$	$5$	$3$
$\bold{4}$	$0$	$2$	$7$	$4$	$5$	$3$

The graph below shows how to reach all the various nodes. It has the same result of Dijkstra solution.

Routing Sample Resolved

Distance Vector

D-V is one of the most popular distributed and proactive algorithms. It’s a distributed version of B-F. Each node keeps a routing table with information about:

destination address
next hop: next node address to reach the destination
overall link cost

This information forms a vector of costs (i.e., distances) to all possible destinations: $DV$ . The vector has the information to reach any destination. Locally, nodes make a decision (by exchanging information with neighboring nodes) to decide the path to the destination:

DV: DV^{(i)} = \Big[DV^{(i)}_1, DV^{(i)}_2, \;\dots,\;DV^{(i)}_k,\;\dots \Big]

The algorithm steps are only a couple. At first, all the directly connected nodes (1 hop) exchange each other the distance vectors to node $i$ , i.e. $DV: DV^{(i)}$ . Then, when the node $i$ gets a $DV^{(j)}$ , it checks if it has a better path for each destination $k$ :

l(i,j) + DV^{(j)}_k < DV^{(i)}_k

If this disequation is false, do nothing. If it is true, update the routing table from $i$ to $k$ with:

DV^{(i)}_k = l(i,j) + DV^{(j)}_k

as next hop for $i$ to $k$ : the node $j$ .

Let’s take the same sample network. Consider a subnetwork with $i=A$ . Given the initial state $k$ , the direct links to neighboring nodes are:

$k$	$DV^{(B)}$	$DV^{(D)}$	$DV^{(E)}$
A	$2$	$4$	$6$
B	$0$	$\infty$	$\infty$
C	$9$	$\infty$	$4$
D	$\infty$	$0$	$1$
E	$\infty$	$1$	$0$
F	$1$	$\infty$	$3$

Please Note: NH means next hop. The node A initially has:

$k$	$DV^{(A)}$	$NH^{(A)}$
A	$0$	A
B	$2$	B
C	$\infty$	/
D	$4$	D
E	$6$	E
F	$\infty$	/

Let’s analyze how does $DV^{(A)}$ vary when pieces of information from the other distance vectors are exchanged.

If $DV^{(B)}$ gets into $DV^{(A)}$ , you’ll get:

$k$	$DV^{(A)}$	$NH^{(A)}$
A	$0$	A
B	$2$	B
C	$11$	B
D	$4$	D
E	$6$	E
F	$3$	B

But what if $DV^{(E)}$ gets into $DV^{(A)}$ , intead?

$k$	$DV^{(A)}$	$NH^{(A)}$
A	$0$	A
B	$2$	B
C	$10$	E
D	$4$	D
E	$6$	E
F	$9$	E

There is no a right order for the $DV^{(k)}$ to get into $DV^{(A)}$ . This process is iterative, so now we should progressively add all the other distance vectors (which won’t be done here as a matter of brevity). A distributed algorithm needs to be constantly updated dynamically.

Count to infinity

Let’s analyze a D-V issue.

A \longleftrightarrow B \longleftrightarrow C

Assuming both links have unit cost:

\begin{equation} \begin{split} DV^{(A)}_C &= 2\;;\; NH^{(A)}_C = B \\ DV^{(B)}_C &= 1\;;\; NH^{(B)}_C = C \end{split} \end{equation}

If the link between B and C gets broken, B updates the distance vector:

DV^{(B)}_C = \infty\;;\; NH^{(B)}_C = /

Note that next hopes are evaluated by the nodes themselves. When the distance vector exchange happens:

A gets from B: $DV^{(A)}_C = \infty$ , $NH^{(A)}_C = /$
B gets from A: $DV^{(B)}_C = 3$ , $NH^{(B)}_C = A$

When the exchange happens again:

A gets from B: $DV^{(A)}_C = 4$ , $NH^{(A)}_C = B$
B gets from A: $DV^{(B)}_C = \infty$ , $NH^{(B)}_C = /$

It goes on counting endlessly until a deadlock occurs.