Routing Protocols

Routing Protocols
• Organizing routers into autonomous systems (ASs),
with each AS consisting of a group of routers that
are typically under the same administrative control
(e.g., operated by the same ISP or belonging to the
same company network).

• Routers within the same AS all run the same routing

algorithm (for example, an LS or DV algorithm)
 Routing Protocols
• The routing algorithm running within an autonomous
system is called an intra autonomous system routing
protocol.

• It will be necessary, of course, to connect ASs to each

other, and thus one or more of the routers in an AS
will have the added task of being responsible for
forwarding packets to destinations outside the AS;
these routers are called gateway routers.
 Routing Protocols
• The inter-AS routing protocol involves
communication between two ASs, the two
communicating ASs must run the same inter-
AS routing protocol (BGP)
An example of interconnected autonomous systems
 Popular routing protocols

TCP/IP Protocol Suite 6

 Intra-AS Routing
Also known as interior gateway protocols (IGP).
most common intra-AS routing protocols:
 RIP: Routing Information Protocol
 OSPF: Open Shortest Path First

• An intra-AS routing protocol is used to determine how

routing is performed within an autonomous system (AS).

• Intra-AS routing protocols are also known as interior

gateway protocols.

Network Layer 4-7

 RIP

• RIP was one of the earliest intra-AS Internet

routing protocols and is still in widespread use
today.

• RIP is a distance-vector protocol that operates

in a manner very close to the DV protocol.
 RIP
• The RIP (and also in OSPF), costs are actually
from source router to a destination subnet.

• RIP uses the term hop, which is the number of

subnets traversed along the shortest path
from source router to destination subnet,
including the destination subnet.
 RIP

• The maximum cost of a path is limited to 15, thus

limiting the use of RIP to autonomous systems that
are fewer than 15 hops in diameter.

• Recall that in DV protocols, neighboring routers

exchange distance vectors with each other.

• The distance vector for any one router is the current

estimate of the shortest path distances from that
router to the subnets in the AS.
 RIP ( Routing Information Protocol)
• distance vector algorithm
– distance metric: # hops (max = 15 hops), each link has cost 1
– DVs exchanged with neighbors every 30 sec in response message.
– each advertisement: list of up to 25 destination subnets

from router A to destination subnets:

u v subnet hops
w u 1
A B
v 2
w 2
x x 3
z C D y 3
y z 2
Network Layer 4-11
RIP: example

z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
z B 7
x -- 1
…. …. ....
Network Layer 4-12
RIP: example
A-to-D advertisement
dest next hops
w - 1
x - 1
z C 4
…. … ... z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
A 5
z B 7
x -- 1
…. …. ....
Network Layer 4-13
 RIP
• In RIP, routing updates are exchanged between
neighbors approximately every 30 seconds using a
RIP response message.

• The response message sent by a router or host

contains a list of up to 25 destination subnets within
the AS, as well as the sender’s distance to each of
those subnets.

• Response messages are also known as RIP

advertisements.
 RIP: link failure, recovery

if no advertisement heard after 180 sec -->

neighbor/link declared dead

 routes via neighbor invalidated

 new advertisements sent to neighbors
 neighbors in turn send out new advertisements
(if tables changed)
 link failure info quickly (?) propagates to entire net

Network Layer 4-15

 RIP table processing
RIP routing tables managed by application-level
process called route-d (daemon)
advertisements sent in UDP packets, periodically
repeated
routed routed

transport transprt
(UDP) (UDP)
network forwarding forwarding network
(IP) table table (IP)
link link
physical physical

4-16
 RIP
• A router can also request information about its
neighbor’s cost to a given destination using RIP’s
request message.

• Routers send RIP request and response messages

to each other over UDP using port number 520.

• The UDP segment is carried between routers in a

standard IP datagram.
 RIP

• The fact that RIP uses a transport-layer protocol

(UDP) on top of a networklayer protocol (IP) to
implement network-layer functionality (a routing
algorithm)
 OSPF (Open Shortest Path First)

• “open”: publicly available

• Uses link state algorithm
– LS packet dissemination
– topology map at each node
– route computation using Dijkstra’s algorithm
• OSPF advertisement carries one entry per neighbor
• advertisements flooded to entire AS
– carried in OSPF messages directly over IP (rather than TCP
or UDP

Network Layer 4-19

 OSPF (Open Shortest Path First)
• OSPF is a link-state protocol that uses flooding of link-state
information and a Dijkstra least-cost path algorithm.

• With OSPF, a router constructs a complete topological map

(that is, a graph) of the entire autonomous system.
 OSPF (Open Shortest Path First)
• With OSPF, a router broadcasts routing information to all
other routers in the autonomous system, not just to its
neighboring routers.

• A router broadcasts link state information whenever there is a

change in a link’s state (for example, a change in cost ).

• It also broadcasts a link’s state periodically (at least once every

30 minutes), even if the link’s state has not changed.
 OSPF Messages
• There are 5 types of messages in OSPF:
– Hello messages
• Allow routers to test if a node is reachable
– Link State Advertisement (LSA)
• Topology information from a router (i.e. LSPs)
– Link status request (LSR)
• Requests send to another router to determine the status of one or
more links
– Link status update (LSU)
• Responses to a link status request message
– Link status acknowledgement
• Used to indicate that the LSU was received (reliable transfer)
 OSPF “advanced” features (not in RIP)

• security: all OSPF messages authenticated (to

prevent malicious intrusion)

• multiple same-cost paths allowed (only one path in

RIP)

• integrated unicast- and multicast support:

– Multicast OSPF (MOSPF) uses same topology data base as
OSPF.

• hierarchical OSPF in large domains.

Network Layer 4-23

Hierarchical OSPF
boundary router
backbone router

backbone
area
border
routers

area 3

internal
area 1 routers

area 2

Network Layer 4-24

 Hierarchical OSPF

• two-level hierarchy: An OSPF autonomous system can be

configured hierarchically into areas.

– link-state advertisements only in area

– each nodes has detailed area topology; only know direction
(shortest path) to nets in other areas.
• area border routers: “summarize” distances to nets in
own area, advertise to other Area Border routers.
• backbone routers: run OSPF routing limited to
backbone. Performs routing with in the backbone.
• boundary routers: connect to other AS’s. A boundary
router exchange routing information with routers
belonging to other AS.
Network Layer 4-25
 Inter-AS Routing: BGP

• It handles how paths are determined for source-destination pairs that

span multiple ASs.
• The Border Gateway Protocol version 4, is the de facto standard inter-AS
routing protocol in today’s Internet.
• It is commonly referred to as BGP4 or simply as BGP.
• As an inter-AS routing protocol BGP provides each AS a means to
• 1. Obtain subnet reachability information from neighboring ASs.
• 2. Propagate the reachability information to all routers internal to the AS.
• 3. Determine “good” routes to subnets based on the reachability
information and on AS policy.
• Most importantly, BGP allows each subnet to advertise its existence
to the rest of the Internet.
• A subnet screams “I exist and I am here,” and BGP makes sure that all
the ASs in the Internet know about the subnet and how to get there.
• If it weren’t for BGP, each subnet would be isolated—alone and
unknown by the rest of the Internet.
BGP Basics
• BGP is extremely complex;
• In BGP, pairs of routers exchange routing information over semipermanent TCP connections
using port 179.
• There is typically one such BGP TCP connection for each link that directly connects two
routers in two different ASs;
• There is a TCP connection between gateway routers 3a and 1c and another TCP connection
between gateway routers 1b and 2a.
• There are also semipermanent BGP TCP connections between routers within an AS.
• A common configuration of one TCP connection for each pair of routers internal to an AS,
creating a mesh of TCP connections within each AS.
• For each TCP connection, the two routers at the end of the connection are called BGP
peers, and the TCP connection along with all the BGP messages sent over the connection is
called a BGP session.
• Furthermore, a BGP session that spans two Ass is called an external BGP (eBGP) session,
and a BGP session between routers in the same AS is called an internal BGP (iBGP) session.
• BGP allows each AS to learn which destinations are reachable via its
neighboring ASs. In BGP, destinations are not hosts but instead are
CIDRized prefixes, with each prefix representing a subnet or a
collection of subnets.
• Thus, for example, suppose there are four subnets attached to AS2:
138.16.64/24, 138.16.65/24, 138.16.66/24, and 138.16.67/24.
• Then AS2 could aggregate the prefixes for these four subnets and use
BGP to advertise the single prefix to 138.16.64/22 to AS1.
Internet inter-AS routing: BGP
• BGP (Border Gateway Protocol): the inter-domain
routing protocol
• “glue that holds the Internet together”
• BGP provides each AS a means to:
• eBGP: obtain subnet reachability information from
neighboring ASs.
• iBGP: propagate reachability information to all AS-
internal routers.
• determine “good” routes to other networks based on
reachability information and policy.
• allows subnet to advertise its existence to rest of
Internet: “I am here”
Network Layer 4-31
 BGP basics
 BGP session: two BGP routers (“peers”) exchange BGP
messages:
 advertising paths to different destination network prefixes (“path vector”
protocol)
 exchanged over semi-permanent TCP connections

• when AS3 advertises a prefix to AS1:

• AS3 promises it will forward datagrams towards that prefix
• AS3 can aggregate prefixes in its advertisement

3c
BGP
3a message
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d
Network Layer 4-32
BGP basics: distributing path information
using eBGP session between 3a and 1c, AS3 sends prefix
reachability info to AS1.
 1c can then use iBGP do distribute new prefix info to all routers in AS1
 1b can then re-advertise new reachability info to AS2 over 1b-to-2a
eBGP session
when router learns of new prefix, it creates entry for prefix in its
forwarding table.

eBGP session
3a iBGP session
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d
Network Layer 4-33
Path attributes and BGP routes

• advertised prefix includes BGP attributes

• prefix + attributes = “route”

• Two important attributes:

AS_PATH. This defines the list of autonomous systems
through which the destination can be reached.
• NEXT-HOP, which defines the next router to which the
data packet should be sent.

Network Layer 4-34

BGP route selection
• router may learn about more than 1 route to
destination AS, selects route based on:

1. local preference value attribute: policy decision. Routes are

assigned a local preference value as one of their attributes.
The local preference of a route could have been set by the
router or could have been learned by another router in the
same
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria

Network Layer 4-35

BGP messages
• BGP messages exchanged between peers over TCP connection
• BGP messages:

• OPEN: opens TCP connection to peer and authenticates

sender
• UPDATE: advertises new path (or withdraws old)
• KEEPALIVE: keeps connection alive in absence of UPDATES;
also ACKs OPEN request
• NOTIFICATION: reports errors in previous msg; also used to
close connection

Network Layer 4-36

Broadcast and Multicast Routing

• In broadcast routing, the network layer provides a

service of delivering a packet sent from a source
node to all other nodes in the network.
• multicast routing enables a single source node to
send a copy of a packet to a subset of the other
network nodes.
Multicast
• A number of emerging network applications require the
delivery of packets from one or more senders to a group of
receivers.
• These applications include bulk data transfer (for example,
the transfer of a software upgrade from the software
developer to users needing the upgrade),
• streaming continuous media (for example, the transfer of
the audio, video, and text of a live lecture to a set of
distributed lecture participants),
• shared data applications (for example, a whiteboard or
teleconferencing application that is shared among many
distributed participants),
• data feeds (for example, stock quotes),
• Web cache updating, and interactive gaming (for example,
distributed interactive virtual environments or multiplayer
• In multicast communication, we are immediately faced with two
problems—
• how to identify the receivers of a multicast packet and how to
address a packet sent to these receivers.
• In the case of unicast communication, the IP address of the receiver
(destination) is carried in each IP unicast datagram and identifies the
single recipient; in the case of broadcast, all nodes need to receive
the broadcast packet, so no destination addresses are needed.
• But in the case of multicast, we now have multiple receivers.
• A multicast packet is addressed using address indirection.
• That is, a single identifier is used for the group of receivers, and a
copy of the packet that is addressed to the group using this single
identifier is delivered to all of the multicast receivers associated with
that group.
• In the Internet, the single identifier that represents a group of
receivers is a class D multicast IP address.
• The group of receivers associated with a class D address is referred to
as a multicast group.
• Here, four hosts are associated with the multicast group
address of 226.17.30.197 and will receive all datagrams
addressed to that multicast address.
• While the multicast group abstraction is simple, it raises a
set of questions.
• How does a group get started and how does it terminate?
• How is the group address chosen?
• How are new hosts added to the group (either as senders or
receivers)?
• Can anyone join a group (and send to, or receive from, that
group) or is group membership restricted and, if so, by
whom?
• Do group members know the identities of the other group
members as part of the network-layer protocol?
• How do the network nodes interoperate with each other to
deliver a multicast datagram to all group members?
• For the Internet, the answers to all of these questions
involve the Internet Group Management Protocol.