Routing protocols

N.Jagadish kumar
Assistant Professor-IT
ROUTING

2
11.1 Introduction11.1 Introduction
11.2 Intra- and Inter-Domain11.2 Intra- and Inter-Domain
RoutingRouting
11.3 Distance Vector Routing11.3 Distance Vector Routing
11.4 RIP11.4 RIP
11.5 Link State Routing11.5 Link State Routing
11.6 OSPF11.6 OSPF
11.7 Path Vector Routing11.7 Path Vector Routing
11.8 BGP11.8 BGP

An internet is a combination of networks connected
by routers. When a datagram goes from a source to
a destination, it will probably pass through many
routers until it reaches the router attached to the
destination network.

INTER- AND INTRA-DOMAIN ROUTING
Today, an internet can be so large that one routing
protocol cannot handle the task of updating the
routing tables of all routers. 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 called intra-domain routing. Routing
between autonomous systems is called inter-domain
routing

DISTANCE VECTOR ROUTING
Today, an internet can be so large that one routing
protocol cannot handle the task of updating the
routing tables of all routers. 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 called intra-domain routing. Routing
between autonomous systems is called inter-domain
routing

Updating Routing Table
If the next-node entry is different
The receiving node chooses the row with the smaller cost
If there is a tie, the old one is kept
If the next-node entry is the same
i.e. the sender of the new row is the provider of the old
entry
The receiving node chooses the new row, even though
the new value is infinity.

When to Share
Periodic Update
A node sends its routing table, normally 30 seconds, in a
periodic update
Triggered Update
A node sends its routing table to its neighbors any time
when there is a change in its routing table
1. After updating its routing table, or
2. Detects some failure in the neighboring links

Example 11.2
Net4 , 1
3
Net5 , 1
4
Net2 , 1
2

RIP
The Routing Information Protocol (RIP) is an intra-
domain (interior) routing protocol used inside an
autonomous system.
It is a very simple protocol based on distance vector
routing. RIP implements distance vector routing
directly with some considerations.

Topics Discussed in the SectionTopics Discussed in the Section
 RIP Message Format
 Request and Response
Timers in RIP
 RIP Version 2
 Encapsulation

RIP messages
Request
A request message is sent by a router that has just come
up or by a router that has some time-out entries
A request can ask about specific entries or all entries
Response
A response can be either solicited or unsolicited (30s or
when there is a change in the routing table)

RIP Timers
Periodic timer
It controls the advertising of regular update message (25 ~ 30 sec)
Expiration timer
It governs the validity of a route (180 sec)
The route is considered expired and the hop count of the route is set
to 16
Garbage collection timer
A invalid route is not purged from the routing table until this
timer expires (120 sec)

RIPv2 vs. RIPv1
Classless Addressing
Authentication
Multicasting
RIPv1 uses broadcasting to send RIP messages to every
neighbors. Routers as well as hosts receive the packets
RIPv2 uses the all-router multicast address to send the RIP
messages only to RIP routers in the network

LINK STATE ROUTING
Link state routing has a different philosophy from
that of distance vector routing.
In link state routing, if each node in the domain has
the entire topology of the domain—the list of nodes
and links, how they are connected including the
type, cost (metric), and the condition of the links (up
or down)—the node can use the Dijkstra algorithm to
build a routing table.

Building Routing Tables
Creation of the states of the links by each node, called the
link state packets (LSP)
Dissemination of LSPs to every other routers,
called flooding (efficiently)
Formation of a shortest path tree for each node
Calculation of a routing table based on the
shortest path tree

Creation of LSP
LSP data: E.g. the node ID, the list of links, a
sequence number, and age.
LSP Generation
When there is a change in the topology of the
domain
On a periodic basis
There is no actual need for this type of LSP, normally
60 minutes or 2 hours

Forming shortest path three for router A in a graph

OSPF
The Open Shortest Path First (OSPF) protocol is an
intra-domain routing protocol based on link state
routing. Its domain is also an autonomous system.

Area in OSPF (1)
A collection of networks with area ID
Routers inside an area flood the area with routing
information
Area border routers summarize the information about the
area and send it to other areas
Backbone area and backbone routers
All of the area inside an AS must be connected to the
backbone

Area in OSPF (2)
Virtual link
If, because of some problem, the connectivity
between a backbone and an area is broken, a
virtual link between routers must be created
by the administration to allow continuity of the
functions of the backbone as the primary area

Example of an AS and its graphical representation in OSPF

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.

Topics Discussed in the SectionTopics Discussed in the Section
 Types of Autonomous Systems
 Path Attributes
 BGP Sessions
 External and Internal BGP
 Types of Packets
 Packet Format
 Encapsulation

Internal and external BGP sessions
A speaker node advertises the
path, not the metric of the
nodes, in its AS or other ASs.

Path Vector Routing (1)
• Sharing
– A speaker in an AS shares its table with
immediate neighbors
• Updating
– Adding the nodes that are not in its
routing table and adding its own AS and
the AS that sent the table
– The routing table shows the path
completely

• Loop prevention
– A route checks to see if its AS is in the
path list to the destination
• Policy routing
– If one of the ASs listed in the path is
against its policy, it can ignore that path
and that destination
– It does not update its routing table with
the path, and it does not send this
message to its neighbors

• Optimum path
– Problem: each AS that is included in the
path may use a different criteria for
the metric
– The optimum path is the path that fits
the organization
– For Fig. 14-49, the author chose the one
that had the smaller number of ASs
– Other criteria: security, safety,
reliability, etc.

Types of AS
• Stub AS
– Only one connection to another AS (only
a source or sink for data traffic)
• Multihomed AS
– More than one connection to other AS,
but it is still only a source or sink for
data traffic
• Transit AS
– Multihomed AS that also allows
transient traffic

BGP packet header
Open message

Unicasting
In unicasting, the router forwards the received
packet through only one of its interfaces

Multicasting
In multicast routing, the router may forward the
received packet through several of its interfaces.
Broadcasting is a special case of multicasting

Multicasting
In multicast routing, the router may forward the received packet
through several of its interfaces.
Broadcasting is a special case of multicasting

Multicasting Applications
Access to distributed databases
Information dissemination
Dissemination of news
Teleconferencing
Distance learning

Multicast tree
Objectives of multicasting:
• Every member of the group should receive one, and only one, copy
of the multicast packet. Nonmember must not receive a copy
• There must be no loops in routing
• The path traveled from source to each destination must be optimal
In a source-based tree approach, the combination of source and group
determines the tree (DVMRP, MOSPF, PIM-DM)
In the group-shared tree approach, the group determines the tree
(CBT, PIM-SM)

Multicast Routing
Optimal routing: Shortest path trees
Unicast Routing
Each router in the domain has a table that defines a shortest path
tree to possible destinations

Shortest Path Tree
 Multicast Routing
Each involved router needs to construct a shortest path tree for each group
 Source-Based Tree and Group-Shared Tree
 In the source-based tree approach, each router needs to have one shortest path
tree for each group

Shortest Path Tree
In the group-shared tree approach, only the core router, which has
a shortest path tree for each group, is involved in multicasting

Multicast Link State Routing: MOSPF
Multicast link state routing uses the source-based tree approach
n (the number of group) topologies and n shortest path trees made
Each router has a routing table that represents as many shortest
path trees as there are groups
MOSPF is an extension of the OSPF protocol that uses multicast
link state routing to create source-based trees
MOSPF requires a new link state update packet to associate the
unicast address of a host with the group address or addresses the
host is sponsoring
MOSPF is a data-driven protocol; the first time an MOSPF router
see a datagram with a given source and group address, the router
constructs the Dijkstra shortest path tree

Multicast Distance Vector: DVMRP
Multicast distance vector routing uses the source-based trees, but
the router never actually makes a routing table
Multicast routing does not allow a router to send its routing table
to its neighbors. The idea is to create a table from scratch by using
the information from the unicast distance vector tables
Process based on four decision-making strategies. Each strategy is
built on its predecessor
Flooding
Reverse Path Forwarding (RPF)
Reverse Path Broadcasting (RPB)
Reverse Path Multicasting (RPM)

DVMRP: Strategies
Flooding broadcasts packets, but creates loops in the systems
Reverse path forwarding: RPF eliminates the loop in the flooding
process

DVMRP: Strategies
Reverse path broadcasting: RPB creates a shortest path broadcast
tree from the source to each destination. It guarantees that each
destination receives one and only one copy of the packet
Problem with RPF

DVMRP: Strategies
Reverse path multicasting: RPM adds pruning and grafting to RPB
to create a multicast shortest path tree that supports dynamic
membership changes

Core-Based Tree (CBT)
CBT is a group-shared protocol that uses a core as the root of the tree
AS is divided into regions, and core (center router or rendezvous
router) is chosen for each region
Each router sends a unicast join message to rendezvous router
When the rendezvous router has received all join messages from every
member of the group, the tree is formed

Sending Multicast Packets
The source sends the multicast packet (encapsulated in a unicast
packet) to the core router. The core router decapsulates the packet
and forwards it to all interested hosts. Each router that receives the
multicast packet, in turn, forwards it to all interested ports

Protocol Independent Multicast (PIM)
PIM-DM (Dense Mode) and PIM-SM (Sparse Mode)
PIM-DM is used in a dense multicast environment, such as a LAN
PIM-DM is a source-based tree routing protocol that uses RPF and
pruning and grafting strategies for multicasting. However, it is
independent of the underlying unicast protocol.
PIM-SM is used in a sparse multicast environment such as a WAN
PIM-SM is a group-shared routing protocol that has a rendezvous
point as the source of the tree
PIM-SM is similar to CBT but uses a simpler procedure.

Routing protocols

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Similar to Routing protocols

Similar to Routing protocols (20)

More from N.Jagadish Kumar

More from N.Jagadish Kumar (18)

Recently uploaded

Recently uploaded (20)

Routing protocols