Shortest Path Algorithm (Networking), RIP

Some general routing issues to consider:

• We may need to forward out on the correct interface towards the destination
• Use (create): The Routing Table

Here in this possible path between two devices (in red), we may want to optimize:

• Hop count (smaller is better)
• Shortest distance
• Speed (some cables may be higher speeds)
• Bandwidth
• ...
  For all of these, we generate a cost using these factors. For each router, we'll calculate the shortest path (in terms of cost) to each destination. Each router will have their own Routing Table and calculate their own cost.

A routing decision is made on every single packet, so each IP Addressing (IP Protocol) datagram is processed, and we search for an existing destination IP in the Routing Table. Where is this done? On every router.

The routing goal is to find the least cost route from the source to the destination. In effect, it creates a logical shortest path tree Network Topologies over the physical topology (ie: it's a minimum cost spanning tree). We'll look at Dijkstra's and Bellman-Ford.

Process to Develop the Routing Table

We'll make an Adjacency Matrix that describes the number of edges between two points on the graph. For now, assume we only care about hop count (so no weights on the edges yet):

Then for this example network we have:

Then you can run Dijkstra's algorithm, taking powers of this adjacency matrix to get the cost of taking a path from any vertex to another.

If you wanted to add in the weights you could:

You can also add make the graph directed. You just consider the in-degree using those weights (using the in-vertex on the rows, out-vertex on the columns; really the order doesn't matter as you'll get the transpose if you do it the other way).

Distance Vector Routing

The distance vector routing protocol only considers hop count, and nothing else. It generates a next hop count table:

1. Collect the Hop Count Data
2. Process
3. Generate Hop Count Table AND the Routing Table.

Consider the example from before again. The routers that are neighbors will only share their hop count table with each other. So $A$ will only share with $B,C$, and vice versa.

Hop count table for $A$:

Next is the traffic for these requests get forwarded, so for the example below $A$ shares the $B$ traffic to it's neighbor $C$:

GIving the following tables:

$A$:

Note that:

• Each neighbor shares their entire hop count table with each other, and only with each other.
• One negative is that $A$ only has a local view of the graph. If there are loops (ex: due to a wire that's gone down) then you'll get invalid hop counts ($A$ counts to $B$ and vice versa for forever). This is known as the count to infinity problem

To fix this we have different methods:

• Set $\mathrm{\infty }$ (the max count) to 16 (so we only look at the nearest 16 hops)
• You can also just have $A$ (in the example above) if it it sees a count that refers to itself via the next hop, to ignore that (ie: it should only allow outgoing hops, not inward hops).

Distant Vector Routing (ex: RIP)

So this uses "Bellman-Ford's" shortest path algorithm, where each router will only have a local view of the network. We have two sample implementations:

• RIP - Router Information Protocol
• RIP2

Some issues include:

• Scalability (you can only see so many next hops, and you get exponentially more traffic doing this as that count increases)
• Count to Infinity problem (loops)