Unicast Routing Protocols:
RIP, OSPF, and BGP
Objectives
• Distinguish between intra and interdomain routing
• Understand distance vector routing and RIP
• Understand link state routing and OSPF
• Understand path vector routing and BGP
TCP/IP Protocol Suite 1
14.1 INTRA- AND INTERDOMAIN
ROUTING
Routing inside an autonomous system is referred to as intradomain
routing. Routing between autonomous systems is referred to as
interdomain routing.
TCP/IP Protocol Suite 2
Figure 14.1 Autonomous systems
TCP/IP Protocol Suite 3
Figure 14.2 Popular routing protocols
TCP/IP Protocol Suite 4
14.2 DISTANCE VECTOR ROUTING
In distance vector routing, the least cost route between any two nodes is
the route with minimum distance. In this protocol each node maintains a
vector (table) of minimum distances to every node
The topics discussed in this section include:
Initialization
Sharing
Updating
When to Share
Two-Node Loop Instability
Three-Node Instability
TCP/IP Protocol Suite 5
Figure 14.3 Distance vector routing tables
TCP/IP Protocol Suite 6
Figure 14.3 Distance vector routing tables
TCP/IP Protocol Suite 7
Figure 14.3 Distance vector routing tables
TCP/IP Protocol Suite 8
Figure 14.3 Distance vector routing tables
TCP/IP Protocol Suite 9
Note:
In distance vector routing, each node
shares its routing table with its
immediate neighbors periodically and
when there is a change.
TCP/IP Protocol Suite 10
14.3 RIP
The Routing Information Protocol (RIP) is an intradomain routing
protocol used inside an autonomous system. It is a very simple protocol
based on distance vector routing.
The topics discussed in this section include:
RIP Message Format
Requests and Responses
Timers in RIP
RIP Version 2
Encapsulation
TCP/IP Protocol Suite 11
Figure 14.8 Example of a domain using RIP
TCP/IP Protocol Suite 12
Figure 14.9 RIP message format
TCP/IP Protocol Suite 13
Figure 14.10 Request messages
TCP/IP Protocol Suite 14
Figure 14.12 RIP timers
TCP/IP Protocol Suite 15
Example 2
A routing table has 20 entries. It does not receive information
about five routes for 200 s. How many timers are running at
this time?
Solution
The 21 timers are listed below:
Periodic timer: 1
Expiration timer: 20 − 5 = 15
Garbage collection timer: 5
TCP/IP Protocol Suite 16
Figure 14.13 RIP version 2 format
TCP/IP Protocol Suite 17
Figure 14.14 Authentication
TCP/IP Protocol Suite 18
Note:
RIP uses the services of UDP on
well-known port 520.
TCP/IP Protocol Suite 19
14.4 LINK STATE ROUTING
In link state routing, if each node in the domain has the entire topology
of the domain, the node can use Dijkstra’s algorithm to build a routing
table.
The topics discussed in this section include:
Building Routing Tables
TCP/IP Protocol Suite 20
Figure 14.17 Dijkstra algorithm
TCP/IP Protocol Suite 21
Figure 14.15 Concept of link state routing
TCP/IP Protocol Suite 22
Figure 14.15 Concept of link state routing
TCP/IP Protocol Suite 23
Figure 14.15 Concept of link state routing
TCP/IP Protocol Suite 24
Figure 14.15 Concept of link state routing
TCP/IP Protocol Suite 25
14.5 OSPF
The Open Shortest Path First (OSPF) protocol is an intradomain
routing protocol based on link state routing. Its domain is also an
autonomous system.
The topics discussed in this section include:
Areas
Metric
Types of Links
Graphical Representation
OSPF Packets
Link State Update Packet
Other Packets
Encapsulation
TCP/IP Protocol Suite 26
Figure 14.19 Areas in an autonomous system
TCP/IP Protocol Suite 27
Figure 14.20 Types of links
TCP/IP Protocol Suite 28
Figure 14.21 Point-to-point link
TCP/IP Protocol Suite 29
Figure 14.22 Transient link
TCP/IP Protocol Suite 30
Figure 14.23 Stub link
TCP/IP Protocol Suite 31
Figure 14.24 Example of an AS and its graphical representation in OSPF
TCP/IP Protocol Suite 32
Figure 14.25 Types of OSPF packets
TCP/IP Protocol Suite 33
Figure 14.26 OSPF common header
TCP/IP Protocol Suite 34
Figure 14.27 Link state update packet
TCP/IP Protocol Suite 35
Figure 14.28 Link Stat Acknowledgement (LSA) general header
TCP/IP Protocol Suite 36
Figure 14.29 Router link
TCP/IP Protocol Suite 37
Figure 14.30 Router link LSA
TCP/IP Protocol Suite 38
Table 14.2 Link types, link identification, and link data
TCP/IP Protocol Suite 39
Example 3
Give the router link LSA sent by router [Link] in
Figure 14.31.
TCP/IP Protocol Suite 40
Example 3
Solution
This router has three links: two of type 1 (point-to-
point) and one of type 3 (stub network). Figure 14.32
shows the router link LSA.
See Figure 14.32
TCP/IP Protocol Suite 41
Figure 14.32 Solution to Example 3
TCP/IP Protocol Suite 42
Figure 14.33 Network link
TCP/IP Protocol Suite 43
Figure 14.34 Network link advertisement format
TCP/IP Protocol Suite 44
Example 4
Give the network link LSA in Figure 14.35.
Solution.
TCP/IP Protocol Suite 45
Figure 14.36 Solution to Example 4
TCP/IP Protocol Suite 46
Example 5
In Figure 14.37, which router(s) sends out router link LSAs?
See Next Slide
Solution
All routers advertise router link LSAs.
a. R1 has two links, N1 and N2.
b. R2 has one link, N1.
c. R3 has two links, N2 and N3.
TCP/IP Protocol Suite 47
Example 5
See Next Slide
Solution
All routers advertise router link LSAs.
a. R1 has two links, N1 and N2.
b. R2 has one link, N1.
c. R3 has two links, N2 and N3.
TCP/IP Protocol Suite 48
Example 6
In Figure 14.37, which router(s) sends out the network link
LSAs?
Solution
All three network must advertise network links:
a. Advertisement for N1 is done by R1 because it is the only
attached router and therefore the designated router.
b. Advertisement for N2 can be done by either R1, R2, or R3,
depending on which one is chosen as the designated router.
c. Advertisement for N3 is done by R3 because it is the only
attached router and therefore the designated router.
TCP/IP Protocol Suite 49
Figure 14.38 Summary link to network
TCP/IP Protocol Suite 50
Figure 14.39 Summary link to network LSA
TCP/IP Protocol Suite 51
Figure 14.40 Summary link to AS boundary router
TCP/IP Protocol Suite 52
Figure 14.41 Summary link to AS boundary router LSA
TCP/IP Protocol Suite 53
Figure 14.42 External link
TCP/IP Protocol Suite 54
Figure 14.43 External link LSA
TCP/IP Protocol Suite 55
Figure 14.44 Hello packet
TCP/IP Protocol Suite 56
Figure 14.45 Database description packet
TCP/IP Protocol Suite 57
Figure 14.46 Link state request packet
TCP/IP Protocol Suite 58
Figure 14.47 Link state acknowledgment packet
TCP/IP Protocol Suite 59
Note:
OSPF packets are encapsulated in IP
datagrams.
TCP/IP Protocol Suite 60
14.6 PATH VECTOR ROUTING
Path vector routing is similar to distance vector routing. There is at least
one node, called the speaker node, in each AS that creates a routing
table and advertises it to speaker nodes in the neighboring ASs..
The topics discussed in this section include:
Initialization
Sharing
Updating
TCP/IP Protocol Suite 61
Figure 14.48 Initial routing tables in path vector routing
TCP/IP Protocol Suite 62
Figure 14.49 Stabilized tables for four autonomous systems
TCP/IP Protocol Suite 63
14.7 BGP
Border Gateway Protocol (BGP) is an interdomain routing protocol
using path vector routing. It first appeared in 1989 and has gone
through four versions.
The topics discussed in this section include:
Types of Autonomous Systems
Path Attributes
BGP Sessions
External and Internal BGP
Types of Packets
Packet Format
Encapsulation
TCP/IP Protocol Suite 64
Figure 14.50 Internal and external BGP sessions
TCP/IP Protocol Suite 65
Figure 14.51 Types of BGP messages
TCP/IP Protocol Suite 66
Figure 14.52 BGP packet header
TCP/IP Protocol Suite 67
Figure 14.53 Open message
TCP/IP Protocol Suite 68
Figure 14.54 Update message
TCP/IP Protocol Suite 69
Note:
BGP supports classless addressing and
CIDR.
TCP/IP Protocol Suite 70
Figure 14.55 Keepalive message
TCP/IP Protocol Suite 71
Figure 14.56 Notification message
TCP/IP Protocol Suite 72
Table 14.3 Error codes
TCP/IP Protocol Suite 73
Note:
BGP uses the services of TCP
on port 179.
TCP/IP Protocol Suite 74