�ݺ�ߣ

+
Dynamic Routing Protocols
part2

+
CH2 Outline
Dynamic Routing
Protocols
Distance Vector
Dynamic Routing
Link-State
Dynamic Routing
RIP
OSPF

+ CH2 p3 Outline
 Link State Routing Protocols
 Link-State Routing Process
 Advantages and disadvantages of link state routing protocols
 OSPF Routing Protocol
 Components of OSPF
 OSPF Terminologies
 OSPF Operation
 OSPF Operational State
 Dijkstra’s Algorithm

+ Link-State Routing Protocols
 In contrast to distance vector routing protocol
operation, a router configured with a link-state routing
protocol can create a complete view or topology of the
network by gathering information from all of the other
routers.
 A link-state router uses the link-state information to
create a topology map and to select the best path to
all destination networks in the topology

+
Link and Link-State
The first step in the link-state routing process is that each router
learns about its own links, its own directly connected networks.

+ Say Hello
The second step in the link-state routing process is that each
router is responsible for meeting its neighbors on directly
connected networks.

+ Link State Updates
The third step in the link-state routing process is that each router
builds a link-state packet (LSP) containing the state of each
directly connected link.

+ Flooding the LSP and
Building the Link-State Database
The fourth step in the link-state routing process is that each router
floods the LSP to all neighbors, who then store all LSPs received
in a database.

+
Computing the Best Path
The final step in the link-state routing process is that each router
uses the database to construct a complete map of the topology
and computes the best path to each destination network.

+Adding Routes to the Routing Table
• The best paths are inserted into the routing table

+Why Use Link-State Protocols?
Disadvantages compared to distance vector
routing protocols:
• Memory Requirements
• Processing Requirements
• Bandwidth Requirements

+Protocols that Use Link-State
Only two link-state routing protocols:
 Open Shortest Path First (OSPF)
• most popular
• two current versions
• OSPFv2 - OSPF for IPv4 networks
• OSPFv3 - OSPF for IPv6 networks
 IS-IS
• was designed by ISO
• popular in provider networks

+
OSPF Routing Protocol
Components of OSPF
OSPF Terminologies
OSPF Operation
OSPF Operational State
Dijkstra’s Algorithm

+
OSPF
 OSPF is an IGP routing protocol.
 It is a Link State routing Protocol based on SPF technology.
 OSPF has fast convergence
 OSPF supports VLSM and CIDR
 Cisco’s OSPF metric is based on bandwidth
 OSPF only sends out changes when they occur.
 periodic updates (link-state refresh) every 30 minutes.
 OSPF also uses the concept of areas to implement hierarchical
routing

+
Link State Routing
 In link state routing, each router shares its knowledge about its
neighborhood with every router in the area.
 The three features:
 Sharing knowledge about the neighborhood.
 Sharing with every other router.
 Sharing when there is a change.

+
Components of OSPF
• OSPF Routers Exchange Packets
• These packets are used to discover neighboring routers and
also to exchange routing information to maintain accurate
information about the network.

+
Components of OSPF
• OSPF Routers run Dijkstra’s Algorithm to compute the best path
to each destination network.

+
Components of OSPF
OSPF Terminologies
OSPF Operation
Dijkstra’s Algorithm
Link, Link State and
LSDB.
Area.
OSPF Route Types
OSPF Routers
Classifications.
OSPF Packets

+
Link and Link State
 Link: Interface on a router
 Link state: Description of an interface and of its relationship to its
neighboring routers, including:
 IP address/mask of the interface,
 The type of network it is connected to
 The routers connected to that network
 The metric (cost) of that link
The collection of all the link-states would form a link-state database
(LSDB).

+
Networks Supported by OSPF
 OSPF supports the following types of physical networks

+
Area
 OSPF allows the grouping of routers into a set, called an area.
 An area is a collection of networks, hosts, and routers all
contained within an AS.
 An AS can be divided into many different areas.
 All networks inside area must be connected.

+
Area
 Routers inside an area flood the area with routing information.
 This technique minimizes the routing traffic required for the
protocol.

+
Area
 The topology of an area is hidden from the rest of the AS
 Inside an area, each router has an identical LSDB.
 Each area has its own copy of the topological database.
 At the border of an area, special routers called area border routers
summarize the information about the area and send it to other areas.

+
Area
 Among the areas inside an AS is a special area called the
backbone.
 All the areas inside an AS must be connected to the backbone.
 The routers inside the backbone are called the backbone
routers.
 Note that a backbone router can also be an area border router.

+
Area
 Each area has an area identification.
 The area identification of the backbone is zero.

+
Area
 With multiarea, routing within the AS takes place on two levels,
depending on whether the route to the destination lies entirely
within an area (intra-area routing) or in another area (inter-area
routing).
 When a packet must be routed between two areas, the
backbone is used.

+
OSPF Routers Classifications
 OSPF routers can be classified into four overlapping types:
 Internal routers,
 Area Border routers,
 Backbone routers, and
 Autonomous system boundary routers
Area 0
Area 2 Area 3
IR
ABR/BR
To another AS
ASBR

+
OSPF Routers Classifications

+
Types of OSPF Packets
 OSPF routers exchange packets.

+
OSPF Operation
 To maintain routing information, OSPF routers complete the
following generic link-state routing process to reach a state of
convergence
Exchanging
Hello
packets
Exchanging
LSAs
Creating
SPF Tree
Updating
routing table
1 2 3 and 4 5

+
1. Establish Neighbor Adjacencies
 An OSPF-enabled router
sends Hello packets out all
OSPF-enabled interfaces to
determine if neighbors are
present on those links.
 If a neighbor is present, the
OSPF-enabled router
attempts to establish a
neighbor adjacency with that
neighbor.

+
Establish Neighbor Adjacencies
 OSPF creates adjacencies between neighboring routers.
 The reason for forming adjacencies is to exchange topological
information.
 Not every router needs to become adjacent to every other router.
 Adjacencies are established and maintained with hello packets.
 These packets are sent periodically.

+
2- Exchanging Link State Advertisements
 LSAs contain the state and
cost of each directly
connected link.
 Routers flood their LSAs to
adjacent neighbors.
 Adjacent neighbors receiving
the LSA immediately flood the
LSA to other directly
connected neighbors, until all
routers in the area have all
LSAs.

+
3. Build the Topology Table
 After LSAs are received,
OSPF-enabled routers build
the topology table (LSDB)
based on the received LSAs.
 This database eventually holds
all the information about the
topology of the network.

+
4. Execute the SPF Algorithm
 Routers then execute the SPF algorithm that creates the SPF tree.

+
5- Updating routing table
 From the SPF tree, the best paths are inserted into the routing
table.

+
Components of OSPF
OSPF Terminologies
OSPF Operation
Route calculation and Dijkstra’s
Algorithm

+
OSPF Operational States
• When an OSPF router is initially
connected to a network, it attempts
to:
 Create adjacencies with
neighbors
 Exchange routing information
 Calculate the best routes
 Reach convergence
• OSPF router progresses through
several states while attempting
to reach convergence.

+
Establish Neighbor Adjacencies
 OSPF-enabled routers must form adjacencies with their
neighbor before they can share information with that
neighbor.
 When OSPF is enabled on an interface, the router must
determine if there is another OSPF neighbor on the link.
 To accomplish this, the router forwards a Hello packet that
contains its router ID out all OSPF-enabled interfaces to
determine whether neighbors are present on those links.
 If a neighbor is present, the OSPF-enabled router attempts
to establish a neighbor adjacency with that neighbor.

+
Establishing Neighbor Adjacencies
 An OSPF adjacency is established in several steps and
OSPF router goes through the following states:

+
Down State
 This is the first OSPF neighbor adjacency state.
 It means that no information (Hellos) has been received,
but Hello packets can still be sent to the neighbor in this
state.

+
Down to Init State
 In the first step, routers that intend to establish an OSPF
neighbor adjacency exchange a Hello packets.
* A Cisco router includes the Router IDs of all neighbors in the init (or higher) state in its Hello
packets.

+
Init State
 When a router receives a Hello packet with a router ID
that is not within its neighbor list, the receiving router
attempts to establish an adjacency with the initiating
router.
1- adds the R1 router ID to its neighbor list
2- sends a Hello packet to R1

+
A router transit to
Init State when
It is in Down state
and it starts
sending Hello
packet
It receives a Hello
packet with a
router ID that is not
within its neighbor
list

+
Init State
Init state specifies that the router has received a Hello packet
from its neighbor, but the receiving router's ID was not
included in the hello packet.

+
2-Way State
 When the router sees its own router ID in the Hello packet
received from the neighbor, it will transit to the 2-Way state.
 This means that bidirectional communication with the neighbor
has been established.
1- adds the R2 Router ID in its list of OSPF neighbors.
2- its own Router ID in the Hello packet

+
When a router
receives a Hello
packet with
its Router ID listed in
the list of neighbors,
it will transit from the
Init state to the Two-
Way state
its Router ID not
listed in the list of
neighbors, it will
transit to the Init
state
*The transtion to 2-Way state happens if the router is in the Init state

+
2-Way State
 The action performed in Two-Way state depends on the
type of inter-connection between the adjacent routers:
 If the link is a point-to-point link, then they immediately transition from
the Two-Way state to the database synchronization phase.
 If the routers are interconnected over a multiaccess network, then a
designated router(DR) and a backup designated router (BDR) must
be elected.

+
Why a DR and a BDR
 Multiaccess networks can create two challenges :
 Creation of multiple adjacencies
 Extensive flooding of LSAs

+
Why a DR and a BDR
 The solution to managing the number of adjacencies and the
flooding of LSAs on a multiaccess network is the DR.
 On multiaccess networks, OSPF elects a DR to be the
collection and distribution point for LSAs sent and received.
 A BDR is also elected in case the DR fails.
 All other routers become DROTHERs. A DROTHER is a router
that is neither the DR nor the BDR.

+
DR and BDR
 The DR and BDR act as a central point of contact for link-state
information exchange on a multiaccess network.
 Each router must establish a full adjacency with the DR and the
BDR only.
 Each router, rather than exchanging LSA with every other
router on the segment, sends the LSA to the DR and BDR only.

+
DR and BDR
DR router performs the following tasks:
 Network Links Advertisement
 The DR originates the network LSA for the network.
 Managing LSDB synchronization:
 The DR and BDR ensure that the other routers on the network have
the same link-state information about the common segment.

+
DR and BDR
 When the DR is operating, the BDR does not perform any DR
functions.
 Instead, the BDR receives all the information, but the DR
performs the LSA forwarding and LSDB synchronization tasks.
 The BDR performs the DR tasks only if the DR fails.
 When the DR fails, the BDR automatically becomes the new
DR, and a new BDR election occurs.

+
Synchronizing OSPF Databases
• After the Two-Way state, routers transition to database
synchronization states.

+
Synchronizing OSPF Databases
 While the Hello packet was used to establish neighbor
adjacencies, the other four types of OSPF packets are used
during the process of exchanging and synchronizing LSDBs.

+
ExStart state
 In the ExStart state, a master and slave relationship is created
between each router and its adjacent DR and BDR.
 The router with the higher router ID acts as the master for the
Exchange state.

+
Exchange state
 In the Exchange state, the master and slave routers exchange
one or more DBD packets.
 DBD packets is an abbreviated list of the sending router’s
LSDB and is used by receiving routers to check against the
local LSDB.
 The LSDB must be identical on all OSPF routers within an area
to construct an accurate SPF tree.

+
Loading State
 When a router receives a DBD packet, it compares the
information received with the information it has in its own
LSDB.
 If the DBD packet has a more current LSA or has an LSA that is
not in its LSDB, the router transitions to the Loading state.

+
Loading State
 In this state, the actual exchange of link state information
occurs.
 Based on the information provided by the DBDs, routers send
link-state request (LSR) packets.
 The neighbor then provides the requested link-state information
in link-state update (LSU) packets.
 During the adjacency, if a router receives an outdated or
missing LSA, it requests that LSA by sending a LSR packet.
 All link-state update packets are acknowledged.

+
Full State
 After all LSRs have been satisfied for a given router, the
adjacent routers are considered synchronized (have identical
LSDBs ) and in a full state.

I am router id 172.16.5.2, and I see 172.16.5.1
I am router id 172.16.5.1, and I see no one
B
A
172.16.5.1/24
172.16.5.2/24
hello
To 224.0.0.5
Down state
Initial State
Port1
Port2
Router B neighbor List
172.16.5.1/24,in Port2
hello
Router A neighbor List
172.16.5.2/24,in Port1
Two-way State
Unicast to A
Establishing Bidirectional Communication

Here is a summary of my LSDB
No, I’ll start exchange because I have a higher RID
I will start exchange because I have router id 172.16.5.1
B
A
172.16.5.1/24
172.16.5.2/24
DBD
Exstart state
exchange State
Port1
Port2
DBD
Discovering the Network Routes
Here is a summary of my LSDB
DBD
DBD

Thanks for the information!
B
A
172.16.5.1/24
172.16.5.2/24
LSAck
Loading state
Full State
Port1
Port2
Adding the Link-State Entries
LSAck
I need complete entry for network 172.16.6.0/24
LSR
Here is the entry for network 172.16.6.0/24
LSU
LSAck
Thanks for the information!

+
From CH2 p3 A �ݺ�ߣs
Next slides
Previous slides

+
Dijkstra Animated Example
C C C

+
C
C
C
C
C

+
C
C C
C C

+
C
C
C
C C
B

�ݺ�ߣ

ch2_p3_ospf.pptx

Recommended

More Related Content

Similar to ch2_p3_ospf.pptx (20)

Recently uploaded (20)

ch2_p3_ospf.pptx

Editor's Notes