Routing Algorithms (Distance Vector, Link State) Study Notes

• Once the pathway to destination has been selected, the router sends all packets for that destination along that one route.
• The routing decisions are not made based on the condition or topology of the network. 
• Examples: Centralized, Isolated, and Distributed Algorithms

Adaptive Routing

• A router may select a new route for each packet (even packets belonging to the same transmission) in response to changes in condition and topology of the networks.
• Examples: Flooding, and Random Walk.

• Links between routers have a cost associated with them. In general, it could be a function of distance, bandwidth, average traffic, communication cost, mean queue length, measured delay, router processing speed, etc.
• The shortest path algorithm just finds the least expensive path through the network, based on the cost function.
• Examples: Dijkstra's algorithm

• In this routing scheme, each router periodically shares its knowledge about the entire network with its neighbours.
• Each router has a table with information about the network. These tables are updated by exchanging information with the immediate neighbours.
• It is also known as Belman-Ford or Ford-Fulkerson Algorithm.
• It is used in the original ARPANET, and in the Internet as RIP.
• Neighbouring nodes in the subnet exchange their tables periodically to update each other on the state of the subnet (which makes this a dynamic algorithm). If a neighbour claims to have a path to a node which is shorter than your path, you start using that neighbour as the route to that node.
• Distance vector protocols (a vector contains both distance and direction), such as RIP, determine the path to remote networks using hop count as the metric. A hop count is defined as the number of times a packet needs to pass through a router to reach a remote destination.
• For IP RIP, the maximum hop is 15. A hop count of 16 indicates an unreachable network. Two versions of RIP exist version 1 and version 2.
• IGRP is another example of a distance vector protocol with a higher hop count of 255 hops.
• Periodic updates are sent at a set interval. For IP RIP, this interval is 30 seconds.
• Updates are sent to the broadcast address 255.255.255.255. Only devices running routing algorithms listen to these updates.
• When an update is sent, the entire routing table is sent.

• The following sequence of steps can be executed in the Link State Routing.
• The basis of this advertising is a short packed called a Link State Packet (LSP).
• OSPF (Open shortest path first) and IS-IS are examples of Link state routing.
• Link State Packet(LSP) contains the following information:
  1. The ID of the node that created the LSP;
  2. A list of directly connected neighbours of that node, with the cost of the link to each one;
  3. A sequence number;
  4. A time to live(TTL) for this packet.
• When a router floods the network with information about its neighbourhood, it is said to be advertising.
  1. Discover your neighbours
  2. Measure delay to your neighbours
  3. Bundle all the information about your neighbours together
  4. Send this information to all other routers in the subnet
  5. Compute the shortest path to every router with the information you receive
  6. Each router finds out its own shortest paths to the other routers by using Dijkstra's algorithm.
• In link-state routing, each router shares its knowledge of its neighbourhood with all routers in the network.
• Link-state protocols implement an algorithm called the shortest path first (SPF, also known as Dijkstra's Algorithm) to determine the path to a remote destination.
• There is no hop-count limit. (For an IP datagram, the maximum time to live ensures that loops are avoided.)
• Only when changes occur, It sends all summary information every 30 minutes by default. Only devices running routing algorithms listen to these updates. Updates are sent to a multicast address.
• Updates are faster and convergence times are reduced. Higher CPU and memory requirements to maintain link-state databases.
• Link-state protocols maintain three separate tables:
  • Neighbour table: It contains a list of all neighbours, and the interface each neighbour is connected off of. Neighbours are formed by sending Hello packets.
  • Topology table (Link- State table): It contains a map of all links within an area, including each link’s status.
  • Routing table: It contains the best routes to each particular destination

• It is a non-adaptive algorithm or static algorithm.
• When a router receives a packet, it sends a copy of the packet out on each line (except the one on which it arrived).
• To prevent from looping forever, each router decrements a hop count contained in the packet header.
• As soon as the hop count decrements to zero, the router discards the packet.

• It is a non-adaptive routing algorithm.
• It takes into account both the topology and the load in this routing algorithm;
• We can estimate the flow between all pairs of routers.
• From the known average amount of traffic and the average length of a packet, you can compute the mean packet delays using queuing theory.
• Flow-based routing then seeks to find a routing table to minimize the average packet delay through the subnet.
• Given the line capacity and the flow, we can determine the delay. It needs to use the formula for delay time T.

• Where, μ = Mean number of arrivals in packet/sec, 1/μ = The mean packet size in the bits, and c = Line capacity (bits/s).