Routing Protocols
1
McGraw-Hill © The McGraw-Hill Companies, Inc., 2000
Recap…..
Layers of TCP/IP Model
Functionalites of Network Layer
IP Addressing
Subnetting
Routing
Routers
Routing Table
22.2
Introduction
An internet is a combination of networks connected
by routers
How to pass a packet from source to destination ?
Which of the available pathways is the optimum pathway
?
Depends on the metric
Metric: a cost assigned for passing through a network
A router should choose the route with the smallest metric
Introduction (Cont.)
The metric assigned to each network depends on
the type of protocol
RIP (Routing Information Protocol)
Treat each network as equal
The cost of passing through each network is the same: one
hop count
Open Shortest Path First (OSPF)
Allow administrator to assign a cost for passing
through a network based on the type of serviced
required
For example, maximum throughput or minimum delay
Border Gateway Protocol (BGP)
The criterion is the policy, which can be set by the
administrator
Introduction (Cont.)
Routing table can be static or dynamic
An internet needs dynamic routing tables
Dynamic routing table is achieved by the
routing protocols
Figure 13-2
Autonomous
Systems
The McGraw-Hill Companies, Inc.,
2000
Example
R1, R2, R3 and R4 use an intradomain and
an interdomain routing protocol
Solid thin lines
intradomain routing protocol
Broken thick lines
interdomain routing protocol
Interior and Exterior Routing
An internet can be so large
One routing protocol cannot handle the task
of updating routing table of all routers
Thus, an internet is divided into
autonomous systems (AS)
AS is a group of networks and routers under
the authority of a single administration
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.
Figure 13-1
Popular Routing Protocols
The McGraw-Hill Companies, Inc.,
2000
Intradomain Routing Algorithms
Distance-vector routing algorithm
Classical Distributed Bellman-Ford algorithm
RIP (Routing Information Protocol)
Link-state routing algorithm
Centralized version of the shortest path
computation
Every router has the whole “picture” of
the internet
OSPF (Open Shortest Path First)
Figure 22.14 Distance vector routing tables
22.12
Initialization
At the beginning
Each node can know only the distance
between itself and its immediate neighbors
We assume each node can send a message to
the immediate neighbors and find the
distance
Figure 22.15 Initialization of tables in distance vector routing
22.14
Sharing
Idea of distance vector routing
Sharing of information between neighbors
In distance vector routing, each node shares
its routing table with its immediate
neighbors periodically and when there is a
change
How much of the table must be shared ?
Send the entire table but contains only the
first two columns
The third column must be changed
Updating
Receipt: a two-column table from a neighbor
Add the cost between itself and the sending node
to each value in the second column
Repeat the following steps for each
advertised destination
If (destination not in the routing table)
Add the advertised information to the table
Else
If (next-hop field is the same)
Replace retry in the table with the new
advertised one
Else
If (advertised hop count smaller than one in the
table)
Replace entry in the
routing table
Updating in Distance
Vector Routing
Reach A via
C
Note
In distance vector routing, each node shares its routing table with its
immediate neighbors periodically and when there is a change.
22.18
Figure 22.19 Example of a domain using RIP
22.19
Figure 22.22 Dijkstra algorithm
22.20
Figure 22.23 Example of formation of shortest path tree
22.21
Table 22.2 Routing table for node A
22.22
