# 50.012 Lecture 14
## Control Plane
Recall: There are 2 approaches to structuring network control plane:
* Per-router control (traditional)
Individual routing algorithm components in each and every router interact with each other in control plane to compute forwarding table.

* Logically centralized control (software defined networking)
A distinct (typically remote) controller interacts with local control agents (CAs) in routers to compute forwarding tables.

### Routing Protocols
The goal of a routing protocol is to determine "good" paths (routes) from sending hosts to receiving host, through
network of routers.

Path is defined as the sequence of routers packets will traverse in going from given initial source host to given final destination host.

"Good" can be defined as least "cost", "fastest", or "least congested".

### Graph Abstraction of Network


In this model, graph is modeled as undirected (i.e. cost from u to v = cost from v to u). However, in real life, cost from u to v might be different from cost from v to u depending on the traffic.

### Routing Algorithm Classification

#### Global vs Decentralized
**Global**
All routers have complete topology, link cost info. These algorithms are also known as "link state" algorithms.
All routers will broadcast to all routers in the same domain.

**Decentralized**
Router knows physically-connected neighbours, link costs to neighbours. It is also able to get information from its neighbours.
These algorithms are also known as "distance vector" algorithms.
The computation process is an iterative, exchange of information with neighbours.

#### Static vs Dynamic
**Static**
Routes change slowly over time.

**Dynamic**
Routes change more quickly, with periodic update in response to link cost changes.

## Link State Routing Algorithm

### Dijkstra's algorithm
Assuming the whole topology is known, calculate the shortest path from one given node to all other nodes.
Then, calculate the forwarding table.

#### Notations
c(x,y): link cost from node x to y; = ∞ if not direct neihgbours
D(v): current value of cost of path from source to destination v.
p(v): predecessor node along the path from source to v.
N': set of nodes whose least cost path definitively known (e.g. to self). This set grows as the number of iteration increases.
#### Algorithm
There can be more than one shortest path. In such case, this algorithm will just return either one.
#### Example
**Example 1**

**Example 2**

#### Discussion

**Oscillations are possible:**

Suppose link cost equals to the amount of carried traffic. The first routing decision will be as shown.
B to A will now carry the traffic of Traffic(C,B) + Traffic(B,A) = 1+e.
The routers will update this information.

The routers will recalculate the shortest path again.

Next iteration.

Next iteration.

As a result, the routing decisions will continue to oscillate. This is despite all the routers having global information.

Although all routers have global information, there is no synchronization (communication among the routers to determine the routing decision)

## Distance Vector Algorithm
Unlike link state, there is no broadcasting of information to all routers. Instead, each router will only communicate with its neighbors.

### Bellman-Ford Algorithm
Let d~x~(y) := cost of least-cost path from x to y.
Then,
$d_x(y)=min_v\{c(x,v)+d_v(y)\}$, where
* min~v~ is the minimum taken over all neighbors v of x.
* c(x,v) is the cost to neighbor v.
* d~v~(y) is the cost from neighbor v to destination y.

Each node sends its own distance vector estimate to its neighbors.
EWhen x receives new DV estimate from its neighbor, it updates its own DV using the BF equation:
$D_x(y) \leftarrow min_v\{c(x,v) + D_v(y)\}$ for each node y ∈ N.

Under minor, natural conditions, the estimate D~x~(y) converge to the actual least cost d~x~(y).

#### Properties
**Iterative, asynchronous**
Each local iteration is caused by:
* local link cost change
* DV update message from neighbor.

**Distributed**
* Each node notifies nieghbors only when its DV changes. Neighbors then notify their neighbors if necessary.

Each node:
* Waits for change in the local link cost or message from neighbor
* Recomputes estimates
* If DV to any destination has changed, notify neighbors.
#### Example
**Example 1**

**Example 2**