Communication Networks

UNIT III ROUTING

Routing Algorithms
 Session Meta Data

Author [Link]

Reviewer

Version Number 1

Release Date 01 July 2019

2 v1
 Revision History

Revision Date Details Version

no.

3 v1
 Session Objectives
• Introduce Routing concepts
• Study network layer services and network layer protocols

4 v1
 Session Outcomes
• At the end of this session, students will be able to
– Explain the working of routing algorithms in network layer

5 v1
 Agenda
• Network layer protocols
– Introduction
– Internet as a Graph
– Least cost routing

6 v1
 Introduction
• Unicast routing in the Internet, with a large
number of routers and a huge number of
hosts, can be done only by using
hierarchical routing: routing in several
steps using different routing algorithms.
• In this section, we first discuss the general
concept of unicast routing in the internet.
• After the routing concepts and algorithms
are understood, we show how we can
apply them to the Internet

7 v1
 General idea
• In unicast routing, a packet is routed, hop
by hop, from its source to its destination by
the help of forwarding tables.
• The source & destination host needs no
forwarding table.
• Only the routers that glue together the
networks in the internet need forwarding
tables.
• Routing a packet from source to destination
is routing it from source router to
destination default router.
8
• There are several routes that a packet can
v1
 An Internet as a Graph
• To find the best route, the internet can be
modeled as a graph.
• A graph here is a set of nodes and edges
(lines) that connect the nodes.
• Each router as node and each network
between pair of nodes as edges.
• The Internet is modeled as a weighted
graph, in which each edge is associated
with a cost.
• The cost of an edge has a different
interpretation in different routing
9 protocols. v1
 An internet and its graphical representation

10
20.10
 Least- Cost routing
• When an internet is modeled as a
weighted graph, one of the ways to
interpret the best route from the source
router to the destination router is to find
the least cost between the two.

• In other words, the source router chooses

a route to the destination router in such a
way that the total cost for the route is the
least cost among all possible routes.
11
 Least cost trees
• If there are N routers in the internet, there are (N-1)
paths from each router to any other router.
• We need N x (N-1) least cost paths for the whole
internet.
• A better way to see all of these paths is to combine
them in a least-cost tree.
• A least-cost tree – is a tree with a source router as
the root that spans the whole graph. The path
between root and any other node is the shortest.
• In this way we can find one shortest –path tree for
each node

12
Least-cost trees for nodes in the internet

13
 Routing algorithms
• Several routing algorithms have been designed in the
past.
• The differences between these methods are in the way
they interpret the least cost and the way they create the
least-cost tree for each node.
• We discuss the common algorithms; later we show how
a routing protocol in the Internet implements one of
these algorithms.

14 v1
 Routing Table
• For a simple network, we can calculate all
shortest paths and load them into some
nonvolatile storage on each node.
• A routing table can be either static or
dynamic.
• A static table is one with manual entries.
• A dynamic table is one that is updated
automatically when there is a change
somewhere in the Internet.
• A routing protocol is a combination of
rules and procedures that lets routers in
the Internet inform each other of changes
 Routing Table
• Such a static approach has several
shortcomings
• 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
• What is the solution?
• Need a distributed and dynamic
routing protocol
• Two main classes of protocols
 Intra- and Interdomain Routing
• One routing protocol cannot handle the task
of updating the routing tables of all routers in
Internet is so large that. For this reason, an
internet is divided into autonomous systems.
• An autonomous system (AS) is a group of
networks and routers under the authority of
a single administration.
• Routing inside an autonomous system is
referred to as intradomain routing.
• Routing between autonomous systems is
referred to as interdomain routing.
• Each autonomous system can choose one or
more intradomain routing protocols to handle
routing inside the autonomous system.
Routing Table
 Distance-Vector Routing
• In distance-vector routing, the first thing
each node creates is its own least-cost
tree with the rudimentary information it
has about its immediate neighbors.
• The incomplete trees are exchanged
between immediate neighbors to make
the trees more and more complete and to
represent the whole internet.
• We can say that in distance-vector
routing, a router continuously tells all of
its neighbors what it knows about the
19
whole internet (although the knowledge
 Distance Vector
• Each node constructs a one dimensional
array (a vector) containing the “distances”
(costs) to all other nodes and distributes
that vector to its immediate neighbors
• Starting assumption is that each node
knows the cost of the link to each of its
directly connected neighbors

20 v1
 Stages in DVR
• There are 3 stages in Distance Vector
Routing

Initialization

Sharing

21
Updatin
v1
 1. Initialization
Each node
Consider thecreates an initialization
given example network
table with the cost to reach all other
nodes. Since they do not know about
all the nodes, they create only for
the neighboring node.

22 v1
 2. Sharing
Thus by
From the given sharing
network NodeAA’s
Node doTable to Node
not know C , Node E
about
Node
but Node CC
learns
knowsabout
aboutNode
NodeD.E.
By sharing
Similarly Node CNode C’s know
do not Table to NodeNode
about A, D
butNode
NodeAAlearns
knowsabout Node
about Node ED

23 v1
 3. The receiving node
3. Updating
compares each row of in
its3old tabletable
with from
the
Each and
2. Receiving everyUpdating
node in process
the happens
network updates steps
its own
[Link] several
nodenode
Receiving have
sharing
to and
need add updates
the
to add
modified name process
of between
the cost
table. the sending
all nodes node
in(A)
itself the
to
and
each
network
rownext the table
asbecomes
third received
column.
stableThis
and from
acts
knowsthe neighbor
asthen
the
aboutnext nodes.
If the nodesending
entry node(C).
is different,(Cost Athe
ofthe node
Cpath
is 2)information
receiving tonode
reach any
whennode
thethe
chooses table
onlowest
the
is network.
updated
value.
If the there is a tie, then old value is maintained

24 v1
 Distance Vector
• The distance vector routing algorithm is
sometimes called as Bellman-Ford
algorithm. Because the heart of DVR is the
Bellman Ford equation. This equation is to
find the least cost distance between a
source node x and destination node y
through some intermediary nodes (a,b,c..).
Provided if the cost of all the paths are
given.

• Every T seconds each router sends its

table to its neighbor each router then
25 updates its table based on the new
v1
 Distance Vector

• When a node detects a link failure

• F detects that link to G has failed
• F sets distance to G to infinity and
sends update to A
• A sets distance to G to infinity since it
uses F to reach G
• A receives periodic update from C
with 2-hop path to G
• A sets distance to G to 3 and sends
26 update to F v1
 Distance Vector Routing
• Slightly different circumstances can prevent
the network from stabilizing
– Suppose the link from A to E goes down
– In the next round of updates, A advertises a
distance of infinity to E, but B and C advertise a
distance of 2 to E
– Depending on the exact timing of events, the
following might happen
• Node B, upon hearing that E can be reached
in 2 hops from C, concludes that it can reach
E in 3 hops and advertises this to A
• Node A concludes that it can reach E in 4
hops and advertises this to C
• Node C concludes that it can reach E in 5
27 hops; and so on.v1
 Two-node instability – what can happen with
distance vector routing
Both A and B know
where X is.

Link between A and X

fails. A updates its
table immediately.

But before A can tell B,

B sends its info to A!

A, using B’s info, up-

dates its table (error!).
Then A send its table
to B and B updates its
table (more error).

Both routers keep up-

dating tables, event-
ually hitting infinity. In
28 the meantime,
28 chaos!
 Possible Solutions to two-node
instability
1. Define infinity Use some relatively small
number as an approximation of infinity -
to be a much smaller value. Then it
doesn’t take too long to become stable.

2. Split Horizon – instead of flooding entire

table to each node, only part of its table is
sent. More precisely, if node B thinks that
the optimum router to reach X is via A, then
B does not need to advertise this piece of
info to A – the info has already come from A.

29 v1
 Possible Solutions to two-node
instability
3. Split Horizon and Poison Reverse –
Normally, the distance vector protocol uses
a timer. If there is no news about a route,
the node deletes the route from its table. So
when A never hears from B about the route
to X, it deletes it. Instead, Node B still
advertises the value for X, but if the source
of info is A, it replaces the distance with
infinity, saying “Do not use this value; what
I know about this route comes from you.”

30 v1
 Three-node instability – no
solutions here!

31 31
 Summary
• Discussed
– Least cost route
– Distance vector routing
– Bellman Ford algorithm
– Count to infinity problem

32 v1
 Test your understanding
1. What is the goal of DVR?
2. What is two node instability problem ?

33 v1
 References
• Behrouz A. Forouzan, ―Data communication and Networking‖, Fifth Edition, Tata McGraw – Hill,
2013

34 v1