CS8591 – Computer Networks Unit 3
The basic problem of routing is to find the lowest-cost path between any two
nodes, where the cost of a path equals the sum of the costs of all the edges that
make up the path.
This static approach has several problems:
It does not deal with node or link failures.
It does not consider the addition of new nodes or links.
It implies that edge costs cannot change.
For these reasons, routing is achieved by running routing protocols among the
nodes.
These protocols provide a distributed, dynamic way to solve the problem of
finding the lowest-cost path in the presence of link and node failures and
changing edge costs.
UNICAST ROUTING ALGORITHMS
There are three main classes of routing protocols:
1) Distance Vector Routing Algorithm – Routing Information Protocol
2) Link State Routing Algorithm – Open Shortest Path First Protocol
3) Path-Vector Routing Algorithm - Border Gateway Protocol
DISTANCE VECTOR ROUTING (DSR)
ROUTING INFORMATION PROTOCOL (RIP)
BELLMAN - FORD ALGORITHM
Distance vector routing is distributed, i.e., algorithm is run on all nodes.
Each node knows the distance (cost) to each of its directly connected neighbors.
Nodes construct a vector (Destination, Cost, NextHop) and distributes to its
neighbors.
Nodes compute routing table of minimum distance to every other node via
NextHop using information obtained from its neighbors.
Initial State
In given network, cost of each link is 1 hop.
Each node sets a distance of 1 (hop) to its immediate neighbor and
cost to itself as 0.
Distance for non-neighbors is marked as unreachable with value ∞ (infinity).
For node A, nodes B, C, E and F are reachable, whereas nodes D and G
are unreachable.
[Link]
31
CS8591 – Computer Networks Unit 3
The initial table for all the nodes are given below
Each node sends its initial table (distance vector) to neighbors and receives
their estimate.
Node A sends its table to nodes B, C, E & F and receives tables from nodes B,
C, E & F.
Each node updates its routing table by comparing with each of its neighbor's
table
For each destination, Total Cost is computed as:
Total Cost = Cost (Node to Neighbor) + Cost (Neighbor to Destination)
If Total Cost < Cost then
Cost = Total Cost and NextHop = Neighbor
Node A learns from C's table to reach node D and from F's table to reach
node G.
Total Cost to reach node D via C = Cost (A to C) + Cost(C to D)
Cost = 1 + 1 = 2.
Since 2 < ∞, entry for destination D in A's table is changed to (D, 2, C)
Total Cost to reach node G via F = Cost(A to F) + Cost(F to G) = 1 + 1 = 2
Since 2 < ∞, entry for destination G in A's table is changed to (G, 2, F)
Each node builds complete routing table after few exchanges amongst its
neighbors.
[Link]
32
CS8591 – Computer Networks Unit 3
System stabilizes when all nodes have complete routing information, i.e.,
convergence.
Routing tables are exchanged periodically or in case of triggered update.
The final distances stored at each node is given below:
Updation of Routing Tables
There are two different circumstances under which a given node decides to send a
routing update to its neighbors.
Periodic Update
In this case, each node automatically sends an update message every so often,
even if nothing has changed.
The frequency of these periodic updates varies from protocol to protocol, but
it is typically on the order of several seconds to several minutes.
Triggered Update
In this case, whenever a node notices a link failure or receives an update from
one of its neighbors that causes it to change one of the routes in its routing
table.
[Link]
33
CS8591 – Computer Networks Unit 3
Whenever a node’s routing table changes, it sends an update to its neighbors,
which may lead to a change in their tables, causing them to send an update to
their neighbors.
ROUTING INFORMATION PROTOCOL (RIP)
RIP is an intra-domain routing protocol based on distance-vector algorithm.
Example
Routers advertise the cost of reaching networks. Cost of reaching each link is 1
hop. For example, router C advertises to A that it can reach network 2, 3 at cost
0 (directly connected), networks 5, 6 at cost 1 and network 4 at cost 2.
Each router updates cost and next hop for each network number.
Infinity is defined as 16, i.e., any route cannot have more than 15 hops.
Therefore RIP can be implemented on small-sized networks only.
Advertisements are sent every 30 seconds or in case of triggered update.
Command - It indicates the packet type.
Value 1 represents a request packet. Value 2 represents a response packet.
Version - It indicates the RIP version number. For RIPv1, the value is 0x01.
Address Family Identifier - When the value is 2, it represents the IP protocol.
IP Address - It indicates the destination IP address of the route. It can be the
addresses of only the natural network segment.
Metric - It indicates the hop count of a route to its destination.
Count-To-Infinity (or) Loop Instability Problem
Suppose link from node A to E goes down.
Node A advertises a distance of ∞ to E to its neighbors
Node B receives periodic update from C before A’s update
reaches B
Node B updated by C, concludes that E can be reached in 3 hops via C
Node B advertises to A as 3 hops to reach E
[Link]
34