Distance Vector Routing(DVR)
Anoop R S
What is Distance Vector Routing?
● DVR is an Intra-domain routing mechanism.
● In distance vector routing, each node shares its routing table with
its immediate neighbors periodically and when there is a change.
● DVR is a dynamic routing protocol where each router maintains a
routing table and exchanges this information with its neighbors to
build a complete picture of the network.
● Routers periodically send their "distance vector" (their routing
table) to their neighbors, who then use this information to update
their own tables to find the shortest or least-cost path to every
destination in the network
Anoop R S
Anoop R S
Anoop R S
Initialization
a) At the beginning, each node know the cost of itself and
its immediate neighbor. [those node directly connected to
it.]
b) Assume that each node send a message to the
immediate neighbors and find the distance between itself
and these neighbors.
c) The distance of any entry that is not a neighbor is
marked as infinite (unreachable).
Anoop R S
Sharing
● Idea is to share the information between neighbors.
● The node A does not know the distance about E, but node C does.
● If node C share it routing table with A, node A can also know how to
reach node E.
● On the other hand, node C does not know how to reach node D, but
node A does.
● If node A share its routing table with C, then node C can also know how
to reach node D.
● Node A and C are immediate neighbors, can improve their routing tables
if they help each other.
Anoop R S
Sharing Continued…
● The third column of the table(next hop) is not useful for the
neighbor.
● When the neighbor receives a table, this column needs to
be replaced with the sender’s name.
● If any of the rows can be used, the next node column filled
with sender of the table.
● Therefore, a node can send only the first two columns of its
table to any neighbor.
Anoop R S
Updation
When a node receives a two-column table from a neighbor, it
needs to update its routing table. Updating takes three steps:
The receiving node needs to add the cost between itself and
the sending node to each value in the second column. The
logic is clear. If node C claims that its distance to a
destination is x mi, and the distance between A and C is
y mi, then the distance between A and that destination, via
C, is x+y mi.
Anoop R S
● The receiving node needs to add the name of the sending node to
each row as the third column if the receiving node uses
information from any row. The sending node is the next node in
the route.
● The receiving node needs to compare each row of its old table with
the corresponding row of the modified version of the received
table.
a. If the next-node entry is different, the receiving node
chooses the row with the smaller cost. If there is a tie, the old
one is kept.
b. If the next-node entry is the same, the receiving node
chooses the new row.
Anoop R S
a) Periodic Update: A node sends its table, normally every 30s, in a
periodic update, it depends on the protocol that is using DVR.
b) Triggered Update: A node sends its two-column routing table to
its neighbors anytime there is a change in its routing table.
c) This is called triggered update the change can result from the
following:
✓ A node receives a table from a neighbor, resulting in changes
in its own table after updating.
✓ A node detects some failure in the neighboring links which
results in a distance change to infinity.
Anoop R S
Two node Instability
Anoop R S
● At the beginning, both nodes A and B know how to reach node X.
But suddenly, the link between A and X fails. Node A changes its
table. IfA can send its table to B immediately, everything is fine.
However, the system becomes unstable if B sends its routing table
to A before receiving A's routing table.
● Node A receives the update and, assuming that B has found a way
to reach X, immediately updates its routing table. Based on the
triggered update strategy, A sends its new update to B. Now B
thinks that something has been changed around A and updates its
routing table. The cost of reaching X increases gradually until it
reaches infinity.
Anoop R S
Defining infinity
● Most implementations of the distance vector protocol
define the distance between each node to be 16 as infinity.
● However, this means that the distance vector routing cannot
be used in large systems.
● The size of the network, in each direction, can not exceed
15 hops.
Anoop R S
Split Horizon
● Split Horizon prevents routing loops by ensuring a router does not
advertise a route back to the neighbor from which it learned that
route.
● B learns a route to X from A.
● When B sends its routing update to A, it omits the route to X. It says
nothing about X to A.
● When the connection to X fails, A marks its own route as down.
● A asks B, "How do you get to X?"
● Because of Split Horizon, B has never advertised the X route back to
A. So B says nothing about X.
● A correctly concludes that B also has no path to X, and both routers
quickly agree that X is unreachable. No loop.
Split Horizon with Poison Reverse
● Poison Reverse is a more forceful version of Split Horizon.
● Instead of just omitting the route, it actively advertises the route with an
"infinite" metric (like a hop count of 16, meaning "unreachable") back to
the neighbor it learned it from.
● Example:
● Router B learns about network X from Router A with a metric of 2.
● When B sends its routing update to A, it explicitly states: "Network X is a
distance of infinity (16) from me."
● This "poisons" the route, giving A a definitive statement that B does not
have a valid path through anyone else. If A's direct path fails, it knows B's
path is invalid.
Anoop R S
Anoop R S
Anoop R S