Data Communication &

Computer Networks
9. Routing Protocols
Presented by: Abdul Khaliq
 Routing protocols

• An internet needs dynamic routing tables

• Routing protocols have been created in response to this
demand
• A routing protocols is a combination of rules and
procedures that let routers in the internet inform each
other of changes
• They also include procedures for combining received
routing information

Dr. Manzoor 2
 Routing protocols

• routers receive and forward packets

• make decisions based on knowledge of topology and
traffic/delay conditions
• use dynamic routing algorithm
• distinguish between:
– routing information - about topology & delays
– routing algorithm - that makes routing decisions
based on information

Dr. Manzoor 3
 Unicast communication
• 1 source and 1 destination
– One-to-one relationship btw source and
destination
• Both SA and DA in IP datagram are unicast
addresses

Dr. Manzoor 4
 Unicast routing

• In unicast routing, the router forwards the received

packet through only one of its interfaces.
– The interface is selected according to the optimum
path defined in routing table
• Router may discard the packet if it can’t find the
destination in its routing table

Dr. Manzoor 5
 Metric

• A metric is a cost assigned for passing through a

network
• Router chooses the route with smallest metric
• Metric assignment depends on the routing protocol
– RIP: cost of all networks is same (1 hop)
– OSPF: Admin can assign costs

Dr. Manzoor 6
 Autonomous Systems (AS)

• AS is a group of routers and networks managed by

single organization

• It consists of a group of routers exchanging

information via a common routing protocol

Dr. Manzoor 7
 Why need the concept of AS?
• Routing algorithms are not efficient enough to deal
with the size of the entire Internet
• Different organizations may want different internal
routing policies
• Allow organizations to hide their internal network
configurations from outside
• Allow organizations to choose how to route across
multiple organizations (BGP)
• Basically, easier to compute routes, more flexibility,
more autonomy/independence

Dr. Manzoor 8
 Interior & Exterior Routing
• interior router protocol (IRP)
– passes routing information between routers within AS
– can be tailored to specific applications
– needs detailed model of network to function
• may have more than one AS in internet
– routing algorithms & tables may differ between them
• routers need info on networks outside own AS
• use an exterior router protocol (ERP) for this
– supports summary information on AS reachability

Dr. Manzoor 9
 Application of IRP and ERP

Dr. Manzoor 10
 Popular routing protocols
• Interior routing = Intra-domain routing
• Exterior routing = Inter-domain routing

Dr. Manzoor 11
 Distance vector routing
• Each router periodically shares its knowledge with its
neighbours
– Shares knowledge about entire AS
– Shares only with neighbours
– Shares at regular intervals

Dr. Manzoor 12
 Distance vector routing

• Examples of Distance Vector routing protocols:

– Routing Information Protocol (RIP)
– Interior Gateway Routing Protocol (IGRP)
– Enhanced Interior Gateway Routing Protocol
(EIGRP)

Dr. Manzoor 13
 Distance vector routing

• Distance Vector Technology - the Meaning of Distance

Vector
– A router using distance vector routing protocols
knows 2 things:
• Distance to final destination
• Vector, or direction, traffic should be directed

Dr. Manzoor 14
 Distance vector routing table
• One entry for each dest. network known
• Other info = subnet mask, time etc.

Hop Next
Destination Other information
Count Router

[Link] 7 [Link]

[Link] 5 [Link]

[Link] 4 [Link]

[Link] 6 [Link]

Dr. Manzoor 15
 RIP

• Routing Information Protocol

• Interior routing protocol

• Uses distance vector routing

– Uses Bellman-Ford algorithm for calculating the
routing table

Dr. Manzoor 16
 RIP updating algorithm
Receive: a response RIP message
1. Add one hop to the hop count for each advertised destination.
2. Repeat the following steps for each advertised destination:
1. If (destination not in the routing table)
Add the advertised information to the table.
2. Else
1. If (next-hop field is the same)
Replace entry in the table with the advertised one.
2. Else
1. If (advertised hop count smaller than one in the table)
Replace entry in the routing table.
3. Return.

Dr. Manzoor 17
 Updating a routing table

Dr. Manzoor 18
 When to share routing tables?
• Periodic update
– A node sends its routing table, normally every 30s.
(depends on protocol)
• Triggered update
– A node sends its routing table to its neighbors
anytime there is a change in its routing table.

Dr. Manzoor 19
 Problem: Routing Loop
Two-node instability

Dr. Manzoor 20
 Solutions

1. Defining Infinity

2. Split Horizon

3. Split Horizon and Poison Reverse

Dr. Manzoor 21
 1. Defining Infinity

• Redefine infinity to a smaller number

– system will become stable in fewer updates
– Most distance-vector protocols define the distance
between each node to be 1 and define 16 as
infinity.
• Smaller infinity value limits the size of the network as
well

Dr. Manzoor 22
 2. Split Horizon

• each node sends only part of its table through each

interface
• routing information is not sent back in the direction
from which it was received
• If B has learnt a piece of information from A, it does
not need to advertise this information to A (A already
knows)

Dr. Manzoor 23
 3. Split Horizon with Poison
Reverse
• E.g. X goes down
• A initiates route poisoning by advertising X to be
unreachable
• B receives route poisoning from router A, it sends
an update, called a poison reverse, back to
router A
• Both Poison reverse with split horizon create a much
more resilient and dependable distance-vector
network

Dr. Manzoor 24
 Problem: Routing Loop
Three-node instability

Dr. Manzoor 25
 Link-State Routing
• The shortest path to a
destination is not
necessarily the path
with the least number
of hops

Dr. Manzoor 26
Hashmani
 Link-State Routing Process
• How routers using Link State Routing Protocols reach convergence
– Each router learns about its own directly connected networks
– Link state routers exchange hello packet to “meet” other directly
connected link state routers
– Each router builds its own Link State Packet (LSP) which includes
information about neighbors such as neighbor ID, link type, &
bandwidth
– After the LSP is created the router floods it to all neighbors who then store
the information and then forward it until all routers have the same
information
– Once all the routers have received all the LSPs, the routers then
construct a topological map of the network which is used to determine
the best routes to a destination

Dr. Manzoor 27
 Link-State Routing
• Directly Connected
Networks
• Link
– This is an interface on
a router
• Link state
– This is the information
about the state of the
links

Dr. Manzoor 28
Hashmani
 Link-State Routing

• Sending Hello Packets to Neighbors

– Link state routing protocols use a hello protocol
– Purpose of a hello protocol:
• To discover neighbors (that use the same link
state routing protocol) on its link

Dr. Manzoor 29
 Link-State Routing
• Sending Hello Packets to
Neighbors
– Connected interfaces that
are using the same link state
routing protocols will
exchange hello packets
– Once routers learn it has
neighbors they form an
adjacency
• 2 adjacent neighbors will
exchange hello packets

Dr. Manzoor 30
 Link-State Routing

• Building the Link State Packet (LSP)

– Each router builds its own Link State Packet (LSP)
– Contents of LSP:
• State of each directly connected link
• Includes information about neighbors such as
neighbor ID, link type, & bandwidth

Dr. Manzoor 31
 Link-State Routing

• Flooding LSPs to Neighbors

– Once LSPs are created they are forwarded out to
neighbors
– After receiving the LSP the neighbor continues to
forward it throughout routing area

Dr. Manzoor 32
 Link-State Routing
• LSPs are sent out under the following conditions:
– 1: Initial router start up or routing process
– 2: When there is a change in topology

Dr. Manzoor 33
Hashmani
 Link-State Routing

• Constructing a link state data base

– Routers use a database to construct a topology
map of the network

Dr. Manzoor 34
 Link-State Routing

Dr. Manzoor 35
 Link-State Routing
• Determining the shortest
path
– The shortest path to a
destination determined
by adding the costs &
finding the lowest cost

Dr. Manzoor 36
Hashmani
 Link-State Routing
• Once the SPF algorithm has determined the shortest
path routes, these routes are placed in the routing table

Dr. Manzoor 37
 A Link State Routing Algorithm
Dijkstra’s algorithm Notations
• Net topology, link costs known • c(i,j): link cost from node i to j;
cost infinite if not direct neighbors
to all nodes
• D(v): current value of cost of
– Accomplished via “link state path from source to node v
flooding” • p(v): predecessor node along
– All nodes have same info path from source to v, that is next
• Compute least cost paths from to v
one node (‘source”) to all other • P(v): path from source to v
nodes • T: set of nodes whose least cost
• Repeat for all sources path definitively known

Dr. Manzoor 38
Hashmani
 Dijkstra’s Algorithm
• finds shortest paths from given source node S to all
other nodes
• by developing paths in order of increasing path
length
• algorithm runs in stages (next slide)
– each time adding node with next shortest path
• algorithm terminates when all nodes processed by
algorithm (in set T)

Dr. Manzoor 39
 Dijsktra’s Algorithm
1 Initialization:
2 T = {S}; // S = source
3 for all nodes v
4 if v adjacent to S
5 then D(v) = c(S,v);
6 else D(v) = ;
7
8 Loop
9 find w not in T such that D(w) is a minimum;
10 add w to T;
11 update D(v) for all v adjacent to w and not in T:
12 D(v) = min( D(v), D(w) + c(w,v) );
// new cost to v is either old cost to v or known
// shortest path cost to w plus cost from w to v
13 until all nodes in T;
Dr. Manzoor 40
Hashmani
 Example: Dijkstra’s Algorithm
Step Start T D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A  
1
2
3
4
5

5 1 Initialization:
2 T = {A};
B 3 C 3 for all nodes v
2 5
4 if v adjacent to A
A 2 1 F 5 then D(v) = c(A,v);
3
1 2 6 else D(v) = ;
D E …
1

Dr. Manzoor 41
Hashmani
 Example: Dijkstra’s Algorithm
Step Start T D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A  
1 AD 4,D 2,D 
2
3
4
5
…
5 8 Loop
3 9 find w not in T s.t. D(w) is a minimum;
B C 10 add w to T;
2 5
11 update D(v) for all v adjacent
A 2 1 F
3 to w and not in T:
1 2 12 D(v) = min( D(v), D(w) + c(w,v) );
D E 13 until all nodes in T;
1

Dr. Manzoor 42
Hashmani
 Example: Dijkstra’s Algorithm
Step Start T D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A  
1 AD 4,D 2,D 
2 ADE 3,E 4,E
3
4
5
…
5
8 Loop
3 9 find w not in T s.t. D(w) is a minimum;
B C
2 5 10 add w to T;
A 11 update D(v) for all v adjacent
2 1 F
3 to w and not in T:
1 2 12 D(v) = min( D(v), D(w) + c(w,v) );
D E
1 13 until all nodes in T;

Dr. Manzoor 43
Hashmani
 Example: Dijkstra’s Algorithm
Step Start T D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A  
1 AD 4,D 2,D 
2 ADE 3,E 4,E
3 ADEB
4
5
…
5
8 Loop
3 9 find w not in T s.t. D(w) is a minimum;
B C
2 5 10 add w to T;
A 11 update D(v) for all v adjacent
2 1 F
3 to w and not in T:
1 2 12 D(v) = min( D(v), D(w) + c(w,v) );
D E
1 13 until all nodes in T;

Dr. Manzoor 44
Hashmani
 Example: Dijkstra’s Algorithm
Step Start T D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A  
1 AD 4,D 2,D 
2 ADE 3,E 4,E
3 ADEB
4 ADEBC
5
…
5
8 Loop
3 9 find w not in T s.t. D(w) is a minimum;
B C
2 5 10 add w to T;
A 11 update D(v) for all v adjacent
2 1 F
3 to w and not in T:
1 2 12 D(v) = min( D(v), D(w) + c(w,v) );
D E
1 13 until all nodes in T;

Dr. Manzoor 45
Hashmani
 Example: Dijkstra’s Algorithm
Step Start T D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A  
1 AD 4,D 2,D 
2 ADE 3,E 4,E
3 ADEB
4 ADEBC
5 ADEBCF
…
5
8 Loop
3 9 find w not in T s.t. D(w) is a minimum;
B C
2 5 10 add w to T;
A 11 update D(v) for all v adjacent
2 1 F
3 to w and not in T:
1 2 12 D(v) = min( D(v), D(w) + c(w,v) );
D E
1 13 until all nodes in T;

Dr. Manzoor 46
Hashmani
 Example 2: Dijkstra’s Algorithm

Dr. Manzoor 47
 Example 2: Dijkstra’s Algorithm
Iter T D(2) Path D(3) Path D(4) Path D(5) Path D(6) Path
0 {1} 2 1–2 5 1-3 1 1–4  -  -

1 {1,4} 2 1–2 4 1-4-3 1 1–4 2 1-4–5  -

2 {1, 2, 4} 2 1–2 4 1-4-3 1 1–4 2 1-4–5  -

3 {1, 2, 4, 2 1–2 3 1-4-5–3 1 1–4 2 1-4–5 4 1-4-5–6

5}

4 {1, 2, 3, 2 1–2 3 1-4-5–3 1 1–4 2 1-4–5 4 1-4-5–6

4, 5}

5 {1, 2, 3, 2 1-2 3 1-4-5-3 1 1-4 2 1-4–5 4 1-4-5-6

4, 5, 6}

Dr. Manzoor 48
Hashmani
 Link State vs. Distance Vector

Routing Builds Router can A periodic/ Use

protocol Topological independently Convergence event driven of
map determine the routing updates LSP
shortest path to
every network.

Distance No No Slow Generally No No

vector

Link State Yes Yes Fast Generally Yes Yes

Dr. Manzoor 49
 OSPF

• Open Shortest Path First

• Interior routing protocol

• Uses link state routing

Dr. Manzoor 50
 OSPF areas
• For routing efficiency OSPF divides an autonomous
system (AS) into areas

Dr. Manzoor 51
 OSPF areas

• Routers inside an area flood the area with routing

information.
• At the border of an area, area border routers (ABR)
summarize the information about the area and send
it to other areas.
• All areas inside an AS must be connected to the
backbone area (Area 0).

Dr. Manzoor 52
 OSPF Metric
• The OSPF protocol allows the administra- tor to
assign a cost, called the metric, to each route.

• The metric can be based on a type of service (min

delay, max throughput etc)

Dr. Manzoor 53
 Link types

• In OSPF terminology, a connection is called a link.

• Four types of links have been defined:

Dr. Manzoor 54
 Point-to-point link

• A point-to-point link connects two routers without any

other host or router in between.
• In other words, each router has only one neighbor at the
other side of the link.

Dr. Manzoor 55
 Transient link
• A transient link is a • The data can enter
network with several through any of the
routers attached to it. routers and leave
• Each router has many through any router.
neighbors.

Dr. Manzoor 56
Hashmani
 Transient link

• To reduce the amount of info exchange, a router is

elected as designated router (DR), and another
router as a backup designated router (BDR).
• Every router exchanges information with the DR and
BDR.
• The DR relays the information to everybody else.

Dr. Manzoor 57
 Stub link
• A stub link is a network that is connected to only
one router.
• The data packets enter the network through this
single router and leave the network through this
same router.

Dr. Manzoor 58
 Virtual link

• An administrator can create a virtual link between two

routers that may pass through several routers but
appear like a single link

Dr. Manzoor 59
 Graphical representation

Dr. Manzoor 60
 Link state advertisement (LSA)
• Routers share information about their neighbours by
distributing LSAs
• Five types of LSAs:

Dr. Manzoor 61
 Router link advertisement
• A router uses this advertisement
to advertise information about its
links and neighbours

• Distributed within an area

Dr. Manzoor 62
 Network link advertisement
• It defines the links of a network
• A designated router distributes
this LSA on behalf of the transient
network
• Distributed within an area

Dr. Manzoor 63
 Summary link to network
• This type of LSA is used by area border routers to
flood routing information of one area into another
area

Dr. Manzoor 64
Hashmani
 Summary link to
AS Boundary Router
• If a router in an area wants to send packets outside its
AS, it needs route/address to AS boundary router
• This type of LSA provides this info.

Dr. Manzoor 65
Hashmani
 External link advertisement
• It advertises routing information about networks
outside an AS
• Each advertisement carries routing info about only
one external network

Dr. Manzoor 66
Hashmani
 Path Vector Routing

Dr. Manzoor 67
 Initial routing tables in path vector routing

Dr. Manzoor 22.68

Hashmani
 Stabilized tables for three autonomous systems

Dr. Manzoor 22.69

Hashmani
 Internal and external BGP sessions

Dr. Manzoor 22.70

Hashmani
Path vector routing table

Network Next Router Path

N01 R01 AS14, AS23, AS67

N02 R05 AS22, AS67, AS05, AS89

N03 R06 AS67, AS89, AS09, AS34

N04 R12 AS62, AS02, AS09

Dr. Manzoor 71
Hashmani
 Path vector messages

Dr. Manzoor 72
Hashmani
 Types of BGP messages

Dr. Manzoor 73
Hashmani
Thank you