Transcript Grace Deng

Open Shortest Path First
OSPF


OSPF Overview
OSPF Operation
By Grace Deng Oct.16.2003
1
OSPF Overview
History



Development began 1987 by IETF
Goal—a link state protocol more efficient
and scaleable than RIP
Latest revision is RFC 2328
April 1998
2
OSPF Overview
OSPF versus RIP

OSPF

RIP



Link state
Efficient routing updates
(sends changes only)
No hop count limit
Fast Convergence

Supports VLSM


Path selection based on
bandwidth
Distance vector
Copies entire routing
table
Hop count limit of 15
Hold-down timers to
prevent routing loops
Does not advertise subnet masks
Uses only hop count as
metric






3
OSPF Overview
Concepts



OSPF is a Link-State Routing Protocol
Uses IP as transport, IP protocol 89
Uses multicast addresses in neighbor
maintenance and flooding of LSAs



224.0.0.5 – All OSPF Routers
224.0.0.6 – All DRouters
Employs Dijkstra’s Shortest Path First (SPF)
algorithm to calculate the path tree
4
OSPF Overview
Concepts – (cont.)




Uses Metrics—path cost
Typically faster convergence than DVRPs
Support for CIDR, VLSM, Authentication,
Multi-path and IP unnumbered
Relatively low steady state bandwidth
requirements
5
OSPF Overview
Terminology
6
OSPF Overview
Terminology







Link
Link state
Link State (LS) or topological database
Area
OSPF Metric Cost
Routing table
Adjacencies database
7
OSPF Overview
Topology/Link State Database

A router has a separate Link State (LS) or
topological database for each area to which
it belongs

All routers belonging to the same
area should have identical databases
SPF calculation is performed independently
for each area
LSA flooding is bounded by area


8
OSPF Overview
Areas


OSPF uses a 2 level hierarchical model
Areas labeled with a 32-bit number




Can be defined using single decimal or IP
address format value
(i.e. Area 0.0.0.0 or Area 0)
Area 0 reserved for the backbone area
All areas must connect to area 0
9
10
OSPF Overview
OSPF Metric





Cost applied on all router link paths
16-bit positive number 1–65,535
The lower the more desirable
Relevant going out an interface only
Route decisions made on total cost of path
11
OSPF Overview
OSPF Packet Types
OSPF
Packet
format
12
OSPF Packet Types (cont.)
13
OSPF Overview
Router ID

Routers are identified by a unique 32-bit ID

RID: highest IP address configured on any
active loopback interface

RID: if no loopback exists, highest IP address
configured on any active physical interface

RID can be configured with

router-id <ip address>
14
OSPF Overview
OSPF Hello Packets



Multicast 224.0.0.5 on all router interfaces
Hello interval 10 sec. LAN, 30 sec. NBMA
Used to form adjacencies between routers
15
OSPF Overview
Database Descriptor Packets (DDP)



Contain link state database headers
Describe the current LS database
Exchange stage
DD seq=x+1,M
DD seq=x+1,S
•
•
•
DD seq=x+n,M
DD seq=x+n,S
16
OSPF Overview
Link State Request & Update Packets



Request for specific parts of database
Send only database updates requested
Loading Stage, labeled Full when complete
Link State Request
Link State Update
Link State Request
Link State Update
17
OSPF Operation

Network changes generate link-state
advertisements (LSA)


Cost change to an interface
Link being added or deleted from topology

All routers exchange LSAs to build and
maintain a consistent database

The protocol remains relatively quiet during
steady-state conditions.
18
OSPF Operation
Steps to OSPF Operation
1.
2.
3.
4.
5.
Establishing router adjacencies
Electing DR and BDR
Discovering Routes
Choosing Routes
Maintaining Routing Information
19
OSPF Operation
OSPF States
OSPF router interfaces can be in one of
seven states:







Down State
Init State
Two-way State
ExStart State
Exchange State
Loading State
Full Adjacency State
20
OSPF Operation
Steps to OSPF Operation with OSPF States
1. Establishing router adjacencies
 Down State
 Init State
 Two-way State
 (ExStart State unless DR/BDR election
needed)
2. Electing DR and BDR
 ExStart State with DR and BDR
 Two-way State with all other routers
21
OSPF Operation
Steps to OSPF Operation with OSPF States
3. Discovering Routes
 ExStart State
 Exchange State
 Loading State
 Full State
4. Choosing Routes
5. Maintaining Routing Information
22
OSPF Operation
1. Establishing Adjacencies (1)

Initially, an OSPF router interface is in
the down state.not exchanged
information with any neighbor.
23
OSPF Operation
1. Establishing Adjacencies (2)
Init State
 Init State - OSPF routers send Type 1
Hello packets at regular intervals (10
sec.) to establish neighbors.
 When a router receives its first Hello
packet, it enters the init state, meaning
the router is ready to take the
relationship to the next level.
24
OSPF Operation
1. Establishing Adjacencies (3)
From init state to the two-way state
 RTB receives Hello packets from RTA and
RTC (its neighbors), and sees its own
Router ID (10.6.0.1) in the Neighbor ID field.

RTB declares takes the relationship to a
new level, and declares a two-way state
between itself and RTA, and itself and RTC.
25
OSPF Operation
1. Establishing Adjacencies (4)
Two-way state to ExStart state?

RTB now decides who to establish a full adjacency with
depending upon the type of network that the particular
interfaces resides on.

If the interface is on a point-to-point link, the routers
becomes adjacent with its sole link partner (aka “soul
mates”), and take the relationship to the next level by
entering the ExStart state.

If the interface is on a multi-access link (Ethernet,
Frame Relay, …) RTB must enter an election process
to see who it will establish a full adjacency with, and
remains in the two-way state. (Next!)
26
OSPF Operation
Designated Router

Reduce OSPF traffic on multiaccess links




Routers form FULL adjacencies with DR/BDR
Store and distribute neighbors LSDBs
Backup DR for redundancy
OSPF priority used in DR selection


Range 1–255 default 1, 0 for non-candidate.
Priority carried in Hello packet
ip ospf priority <value>
27
OSPF Operation
Function of DR/BDR
DR
Flood Link change
224.0.0.5
AllOSPFRouters
224.0.0.6
AllDRrouters
BDR
28
OSPF Operation
2.Electing a DR and BDR (1)


On point-to-point links
adjacencies are established
with all neighbors, because
there is only one neighbor.
On multi-access
networks,OSPF elects a DR
and BDR to limit the number
of adjacencies.
 Reduce routing update
traffic
29
OSPF Operation
2.Electing a DR and BDR (2)





DR - Designated Router
BDR – Backup Designated Router
DR’s serve as collection points for Link
State Advertisements (LSAs)
A BDR back ups the DR.
If the IP network is multi-access, the
OSPF routers will elect 1 DR and 1 BDR
(unless there is only 1 router on the
network).
30
OSPF Operation
2.Electing a DR and BDR (3)

The formation of an adjacency between
every attached router would create many
unncessary LSA (Link State
Advertisements), n(n-1)/2 adjacencies.

Flooding on the network itself would be
chaotic.

To prevent this problem, a Designated
Router is elected on multi-access networks.
31
OSPF Operation
2.Electing a DR and BDR (4)

All other routers, “DRother”, establish
adjacencies with only the DR and BDR.

DRother routers multicast LSAs to only the DR
and BDR
 (224.0.0.6 - all DR routers)

DR sends LSA to all adjacent neighbors
 (224.0.0.5 - all OSPF routers)
32
OSPF Operation
2.Electing a DR and BDR (5)

Once a DR is established, a new router that enters
the network with a higher priority or router id will
NOT become the DR or BDR. (Bug in early IOS
12.0)

If DR fails, BDR takes over as DR and selection
process for new BDR begins.

State of the relationship
 DRothers enter ExStart state with DR and BDR
and two-way state with all other routers
33
OSPF Operation
2.Electing a DR and BDR (6)
DR - Summary
DR Election

Router with the highest interface priority
(priority = 0 cannot become DR or BDR)


Router with the highest router ID.
 Loopback address used first
 IP Address on active interface used
second
BDR is the second highest
34
OSPF Operation
2.Electing a DR and BDR (7)
DR - Summary
Adjacencies and multicasting
 All other routers, DRother, establish
adjacencies with only the DR and BDR.
 All routers continue to multicast Hello
packets to AllSPFRouters (224.0.0.5) so they
can track neighbors.
 But updates (LSAs) are multicast to DR and
BDR only (224.0.0.6 - AllDRrouters) and in
turn
 DR floods updates (LSAs) to all adjacent
neighbors (224.0.0.5 - AllSPFRrouters)
35
OSPF Operation
2.Electing a DR and BDR (8)
BDR-summary




Listens, but doesn’t act.
If LSA is sent, BDR sets a timer.
If timer expires before it sees the reply from
the DR, it becomes the DR and takes over
the update process.
The process for a new BDR begins.
36
OSPF Operation
3. Discovering Routes and reaching Full State
37
OSPF Operation
4. Choosing routes (1)
Dijkstra - Shortest Path First (SPF) Algorithm

Link state database


TENT database


Tentative triples (ID, path cost, direction)
PATH database


Created with Link State Packets (LSPs) from
each router
Best path triples (ID, path cost, direction)
Forwarding database

The Routing Table
38
OSPF Operation
4. Choosing routes (2)
Dijkstra (SPF) Overview (Cont.)





All routers exchange Link State Packets (LSPs)
Each router starts with itself as root
Tent is built from LSPs
Path is created by examining and comparing
TENT triples
Once path is final the forwarding table is
populated
39
OSPF Operation
4. Choosing routes (3)
Link State Packet (LSP) Data
A
B
C
D
E
F
G
B/4
A/4
B/1
C/4
C/2
E/2
A/2
G/2
C/1
D/4
E/1
D/1
G/2
F/2
E/2
4
D
1
F/2
C
2
1
B
4
A
2
E
2
F
2
G
Lowest cost best
40
OSPF Operation
5. Maintaining Router
routes
2, Area 1
Router 1, Area 1

..
LSA
ACK


Every router in
area receives the
new LSA via
flooding
Each router
computes
shortest path
routing table
when a link
changes State.
Link State Table
Dijkstra Algorithm
Old Routing Table
New Routing Table
41
Issues with large OSPF nets

Large routing table

Large link-state table

Frequent SPF calculations
42
reference








RFC 1403, "BGP OSPF Interaction", K. Varadhan, 1993.
RFC 1584, "Multicast Extensions to OSPF", J. Moy, March 1994.
RFC 1850, "OSPF Version 2 Management Information Base", F.
Baker and R. Coltun, Nov 1995.
RFC 2328, "OSPF Version 2", J. Moy, April 1998, also STD 54.
RFC 2370, "The OSPF Opaque LSA Option", R. Coltun, July 1998.
http://www2.rad.com/networks/1995/ospf/ospf.htm, “OSPF”, B.
Daniel, B. Omer, R. Carmel.
Internetworking with TCP/IP (Vol I) - Comer
www.et.fnt.hvu.nl/docenten/cuiterwijk/ccnp/guides,“The Technology
Innovation Centre Brimingham”.
43