Session 3: Routing Protocols Fundamentals

Question 1

A router must determine where to send a packet based on header information such as the destination IP-address. Any router will try to choose the next-hop such that the packet will traverse the shortest path in the network. What are the approaches used to enable a router to choose the optimal next destination?

Answer 1

Almost all routing strategies represent the network as an undirected graph where the routers are the vertices, the edges are the links, and the weight of an edge represents its cost (how difficult/time consuming it is to transmit over that link) There are three general approaches:

1. Centralized - Requires a collection of the graph structure at one location in the network. This allows for the usage of standard graph algorithms. The results found at the node collecting the graph must be communicated to the rest of the network. Such a configuration is only considered suitable in a network with a stable topology during the collection and dissemination phases.
2. Link-state - Similar to centralized with the sole exception that each node is responsible for collecting information on the network and computing the shortest paths. This results in every node having its own routing table.
3. Distance Vector - No single node has a copy of the entire graph. Instead, routing tables are constructed iteratively and information is sent to neighbours. A node will only update a neighbour once a local link changes or a distance vector update is received from another neighbour.

Question 2

What are some of the shortest path algorithms used in routing?

Answer 2

1. Bellman-Ford (Used in Distance Vector routing)

2. Djikstra (Link state Protocols)

Question 3

What are the characteristics of the DV protocol Routing Information Protocol?

Answer 3

The Routing Information Protocol is a part if the BSD Unix distribution and is a simple DV protocol.

The protocol limits the network size to 16 hops, which means a packet can only traverse 16 nodes in total. Theoretically this implies that the network can only contain 16!/14!= 240 nodes.

When a node detects a link node change which affects the shortest path, its neighbours are notified.

The protocol uses split horizon with poison reverse. Horizon split is best explained with an example. Suppose node X transmits to Z through Y. Split horizon is used when X does not advertise its route to X to Y. This is then combined with poisoned reverse where X tells Y that the distance between them is infinite. The results from these two techniques is that the communication going from Z to X will traverse a different path. Inn short, split horizon with poison reverse is used for improved robustness and spreading of load.

RIP also performs periodic updates every 30s.