OSPF
• Open Shortest Path First protocol
defined in RFC 2328
• OSPF is classified as an Interior
Gateway Protocol (IGP).
• Developed by the OSPF working group
of the Internet Engineering Task Force
(IETF).
Evolution of OSPF
• OSPF version 1, published as Request for
Comments (RFC) 1131 in October 1989 by
John T. Moy and the OSPF Working
Group.
• Between that time and the release of this
RFC in July of 1991, OSPF version 2 was
developed
• OSPF made use of the famous Dijkstra
Algorithm.
OSPF evolution timeline.
Dijkstra Algorithm
• This algorithm was not new and had not
been created specifically to fill the demand
of the networking community. In reality,
this mathematical formula was initially
created to demonstrate the ARMAC
computer in 1956, over 30 years before
OSPF was ever considered!
Edsger W. Dijkstra
• Edsger W. Dijkstra was born in 1930 in the city of
Rotterdam in the Netherlands. Born into a
scientifically oriented family, he quickly excelled
and achieved his Ph.D. in Computer Science in
1959 from the University of Amsterdam, Holland.
By the time he was 32, he had achieved a full
professorship in mathematics at the Eindhoren
University. His achievement remains extremely
impressive to this day.
OSPF Terminology
Interfaces
Token
Ring
OSPF Terminology
Neighbors
Interfaces
Token
Ring
OSPF Terminology
Neighbors
Interfaces
Cost = 10
Token
Ring
Cost = 1785 Cost = 6
OSPF Terminology
Neighbors
Interfaces
Area 1 Cost = 10
Area 0
Token
Ring
Cost = 1785 Cost = 6
OSPF Terminology
Autonomous System
Neighbors
Interfaces
Area 1 Cost = 10
Area 0
Token
Ring
Cost = 1785 Cost = 6
OSPF Terminology
Autonomous System
Neighbors
Interfaces
Area 1 Cost = 10
Area 0
Token
Ring
Cost = 1785 Cost = 6
Neighborship
Database
Lists Neighbors
OSPF Terminology
Autonomous System
Neighbors
Interfaces
Area 1 Cost = 10
Area 0
Token
Ring
Cost = 1785 Cost = 6
Neighborship Topology
Database Database
Lists Neighbors Lists All Routes
OSPF Terminology
Autonomous System
Neighbors
Interfaces
Area 1 Cost = 10
Area 0
Token
Ring
Cost = 1785 Cost = 6
Neighborship Topology Routing
Database Database Table
Lists Neighbors Lists All Routes Lists Best Routes
AREA
OSPF allows collections of contiguous
networks and hosts to be grouped
together. Such a group, together with
the routers having interfaces to any one
of the included networks, is called an
area.
Characteristics of an OSPF Area
• Areas contain a group of contiguous hosts and
networks
• Routers have a per area topological database
and run the same SPF algorithm
• Each area is connected to the backbone area
known as area 0
• Virtual links can be used
• Allows for inter-area routing
Types of Areas
• Backbone Area
• Non-Backbone
• Stub Area
• Totally Stubby Area
• NSSA
Types of Areas
Types of Areas
Backbone
Area 0
Interconnects
areas;
accepts all
LSAs.
Types of Areas
Stub Area Backbone
Area 0
Interconnects
Does not accept
areas;
external LSAs.
accepts all
LSAs.
Types of Areas
Stub Area Backbone Totally Stubby
Area 0 Area
Interconnects
Does not accept Does not accept
areas;
external LSAs. external or
accepts all
LSAs. summary LSAs.
Backbone Area
A backbone area is the logical and physical structure
for the Autonomous System and is attached to
multiple areas.
The backbone is responsible for distributing routing
information between non-backbone areas.
The backbone must be contiguous, but it need not be
physically contiguous; backbone connectivity can be
established and maintained through virtual links.
Using Stub and Totally
Stubby Areas
RIP
Area 50—Stub Area 0 Area 1—Totally Stubby
Internal ABR1 ASBR BBone ABR2 Internal
Non-Cisco
Router
afadjfjorqpoeru afadjfjorqpoeru afadjfjorqpoeru
afadjfjorqpoeru 39547439070713 39547439070713
39547439070713 39547439070713
Summary Summary Summary Default
afadjfjorqpoeru afadjfjorqpoeru afadjfjorqpoeru afadjfjorqpoeru
39547439070713 39547439070713 39547439070713 39547439070713
Default External External Default
Stub area
• An area could be referred to as a stub area
when there is a single exit point from that
area, or if external routing to outside of the
area does not have to take an optimal path.
• Routing from these areas to the outside
world is based on a default route. They do
contain inter-area and intra-area routes.
• Stub areas should have one Area Border
router.
Stub Area Restrictions
• Stub areas cannot be used as a transit area for virtual links.
• An ASBR cannot be internal to a stub area.
• OSPF allows certain areas to be configured as stub areas.
• External networks, such as those redistributed from other protocols into
OSPF, are not allowed to be flooded into a stub area.
Note
All OSPF routers inside a stub area have to be configured as stub routers
because whenever an area is configured as stub, all interfaces that belong to
that area will start exchanging hello packets with a flag that indicates that
the interface is stub. Actually this is just a bit in the hello packet (“E” bit)
that gets set to 0. All routers that have a common segment have to agree on
that flag. If the routers don’t agree, then they will not become neighbors and
routing will not take effect.
Stub and Totally
Stubby Area Restrictions
Area 2
[Link]
R3
R4
Single Exit Point
X
External
AS
– Typically a single exit point into area; if multiple exit points,
suboptimal paths may be selected
– An ASBR cannot be internal to stub
– Area is not the backbone Area 0
– Virtual links are not allowed
Area Design Rules
• A backbone area must be present
• All areas must have a connection to backbone,
even stub areas
• The backbone area must be contiguous
Router ID
• Every OSPF Router must be identified by a
unique Router ID.
• Manually configured IP Address
• Highest IP Address of any Interface
• If no interface exists, then Router ID is set
to [Link]
Basic OSPF Configuration
• Enable OSPF
• Add Network to be advertised
• Add an area
• Verify the configuration
OSPF Timers
• Hello Interval - 10 Seconds - Broadcast
Multi Access
• Poll Interval - 120 Seconds - Non -
Broadcast Multi Access
• LSA Retransmit Interval - 5 Seconds
• Dead Interval - 40 Seconds
Types of OSPF Routers
Area 1 Backbone Area 0 Area 2
External
AS
Types of OSPF Routers
Area 1 Backbone Area 0 Area 2
Internal
Routers
Internal
Routers
External
AS
Types of OSPF Routers
Area 1 Backbone Area 0 Area 2
Backbone/
Internal
Internal Routers
Routers
Internal
Routers
External
AS
Types of OSPF Routers
Area 1 Backbone Area 0 Area 2
ABR and
Backbone
Router Backbone/
Internal
Internal Routers
Routers
Internal
Routers
ABR and
Backbone
Router
External
AS
Types of OSPF Routers
Area 1 Backbone Area 0 Area 2
ABR and
Backbone
Router Backbone/
Internal
Internal Routers
Routers
Internal
Routers
ASBR and ABR and
Backbone Backbone
Router Router
External
AS
Types of OSPF Routers
• Internal Routers (IRs) are routers whose
directly connected networks all belong to
the same OSPF area. These types of routers
will have a single link-state database
because they only belong to one area.
Types of OSPF Routers
• ABRs are attached to multiple OSPF areas, so there
can be multiple ABRs within a network. ABRs will
have multiple copies of the link-state database
because of this. The router will run one database for
each area that will be summarized, and then it will
be presented to the backbone for distribution to
other areas.
• ABR only sends summarized information to the
backbone area, and in order to be considered an
ABR the router must be connected to the backbone.
Types of OSPF Routers
• ASBRs are connected to more than one
Autonomous System and exchange routing
information with routers in another autonomous
system. ASBRs advertise the exchanged external
routing information throughout their autonomous
system. Every router within an autonomous
system will know how to get to each ASBR with
its AS. ASBRs run both OSPF and another routing
protocol, such as RIP or BGP.
Types of OSPF Routers
• BRs typically have an interface to the
backbone area and two other OSPF areas.
Backbone Routers do not have to have
ABRs. Routers that only have interfaces
connecting them to the backbone are also
considered BRs.
Operations of OSPF
• OSPF speaking router sends hello packets out of all OSPF
enabled interface. If any other router on OSPF enable
interface is also running OSPF agrees certain parameter
specified in hello packet then they becomes neighbor. This
relationship is known as adjacencies.
• Each router sends LSAs over all adjacencies. Each LSAs
describes router’s link_id, state of link & cost of link. The links
may be stub, to other OSPF routers, to networks in another
areas, or to external networks. OSPF defines multiple LSA
types.
• Each OSPF running router receives LSA from neighbor records
the LSA in LSDB, & sends a copy of same LSA to all of its
neighbor on another data link segment. By flooding LSAs within
the area, all OSPF routers in single area have identical LSDB.
• After adding LSA to database OSPF router runs SPF algorithm to
calculate a loop free with shortest path to every known
destination, with itself in the root. After passing from SPF
algorithm routes are installed in global routing table.
Neighbor
Adjacency States
Adjacency States
• Down
• Attempt
• Init
• 2-way
• Exstart
• Exchange
• Loading
• Full
Exchange Process
[Link]/24 [Link]/24
A B
E0 E1
Down State
Exchange Process
[Link]/24 [Link]/24
A B
E0 E1
Down State
I am router ID [Link] and I see no one.
Init State
Router B
Neighbors List
[Link]/24, int E1
Exchange Process
[Link]/24 [Link]/24
A B
E0 E1
Down State
I am router ID [Link] and I see no one.
Init State
Router B
Neighbors List
[Link]/24, int E1
I am router ID [Link], and I see [Link].
Exchange Process
[Link]/24 [Link]/24
A B
E0 E1
Down State
I am router ID [Link] and I see no one.
Init State
Router B
Neighbors List
[Link]/24, int E1
I am router ID [Link], and I see [Link].
Router A
Neighbors List
[Link]/24, int E0
Two-Way State
Discovering Routes
DR
E0 E0
[Link] [Link]
afadjfjorqpoeru
Exstart State
39547439070713
Hello I will start exchange because I have router ID [Link].
afadjfjorqpoeru
No, I will start exchange because I have a
39547439070713
higher router ID. Hello
Discovering Routes
DR
E0 E0
[Link] [Link]
afadjfjorqpoeru
Exstart State
39547439070713
Hello I will start exchange because I have router ID [Link].
afadjfjorqpoeru
No, I will start exchange because I have a
39547439070713
higher router ID. Hello
Exchange State afadjfjorqpoeru
39547439070713
Here is a summary of my link-state database.
DBD
afadjfjorqpoeru
39547439070713
DBD Here is a summary of my link-state database.
Discovering Routes
DR
E0 E0
[Link] [Link]
afadjfjorqpoeru
39547439070713
afadjfjorqpoeru
39547439070713
LSAck Thanks for the information!
LSAck
Discovering Routes
DR
E0 E0
[Link] [Link]
afadjfjorqpoeru
39547439070713
afadjfjorqpoeru
39547439070713
LSAck Thanks for the information!
LSAck
afadjfjorqpoeru
39547439070713
Loading State
LSR I need the complete entry for network [Link]/24.
afadjfjorqpoeru
39547439070713
Here is the entry for network [Link]/24. LSU
afadjfjorqpoeru
39547439070713
LSAck Thanks for the information!
Discovering Routes
DR
E0 E0
[Link] [Link]
afadjfjorqpoeru
39547439070713
afadjfjorqpoeru
39547439070713
LSAck Thanks for the information!
LSAck
afadjfjorqpoeru
39547439070713
Loading State
LSR I need the complete entry for network [Link]/24.
afadjfjorqpoeru
39547439070713
Here is the entry for network [Link]/24. LSU
afadjfjorqpoeru
39547439070713
LSAck Thanks for the information!
Full State
Adjacency States :Down
• Down: The initial state of a neighbor
conversation indicates that no Hellos have
been heard from the neighbor in the last
RouterDeadInterval.
• Hellos are not sent to down neighbors
unless those neighbors are on NBMA
networks; in this case, Hellos are sent
every PollInterval.
• If a neighbor transitions to the Down state
from some higher state, the link state
Retransmission, Database Summary, and
Link State Request lists are cleared.
Adjacency States :Attempt
• Attempt: This state applies only to
neighbors on NBMA networks, where
neighbors are manually configured. A
DR-eligible router transitions a neighbor
to the Attempt state when the interface
to the neighbor first becomes Active or
when the router is the DR or BDR.
• A router sends packets to a neighbor in
Attempt state at the HelloInterval
instead of the PollInterval.
Adjacency States :Init
• Init: This state indicates that a Hello
packet has been seen from the neighbor
in the last RouterDeadInterval, but two-
way communication has not yet been
established.
• A router includes the Router IDs of all
neighbors in this state or higher in the
Neighbor field of the Hello packets.
Adjacency States :2-Way
• 2-Way This state indicates that the router
has seen its own Router ID in the Neighbor
field of the neighbor's Hello packets, which
means that a bidirectional conversation has
been established.
• On multi-access networks, neighbors must
be in this state or higher to be eligible to be
elected as the DR or BDR.
• The reception of a Database Description
packet from a neighbor in the init state also
causes a transition to 2-Way.
Adjacency States :ExStart
• ExStart In this state, the router and its
neighbor establish a master/slave
relationship and determine the initial
DD sequence number in preparation for
the exchange of Database Description
packets.
• The neighbor with the highest Router ID
becomes the master.
Adjacency States :Exchange
• Exchange The router sends Database
Description packets describing its entire
link-state database to neighbors that
are in the Exchange state.
• The router may also send Link State
Request packets, requesting more
recent LSAs, to neighbors in this state.
Adjacency States :Loading
• Loading The router sends Link
State Request packets to
neighbors that are in the Loading
state, requesting more recent LSAs
that have been discovered in the
Exchange state but have not yet
been received.
Adjacency States :Full
• Full Neighbors in this state are
fully adjacent, and the adjacencies
appear in Router LSAs and
Network LSAs.
OSPF Header
OSPF packet encapsulations
OSPF Header and packet
Types
All OSPF protocol packets share a
common protocol header.
There are several OSPF packet types
– Hello Packet
– Database Description Packet
– Link-State Request Packet
– Link-State Update Packet
– Link-State Acknowledgment Packet
OSPF Common Packet
Header
OSPF Packet Header
Version (1 octet) This field details the current version
of OSPF used by the local router. It is set to a value of 2,
the default value.
Type (1 octet) This field specifies the type of OSPF
packet. Possible values include:
1- Hello packet
2- Database descriptor
3- Link-state request
4- Link-state update
5- Link-state acknowledgment
Packet Length (2 octets) This field displays the total
length, in octets, of the OSPF packet.
.
OSPF Packet Header
Router ID (4 octets) The router ID of the advertising
router appears in this field.
Area ID (4 octets) This field contains the 32-bit area ID
assigned to the interface used to send the OSPF packet.
Checksum (2 octets) This field displays a standard IP
checksum for the entire OSPF packet, excluding the 64-
bit authentication field.
Authentication Type (2 octets) The specific type of
authentication used by OSPF is encoded in this field.
Possible values are:
0-Null authentication
1-Simple password
2-MD5 cryptographic authentication
Authentication (8 octets) This field displays the authentication data to
verify the packet's integrity.
OSPF Hello Packet
Hello Packet
• Hello is sent to establish and maintain a neighbor
relationship
• Hello packets are sent out all configured interfaces
and await a response
• Hello packet, type code 1, is addressed to the
AllSPFRouters multicast address of [Link] for
broadcast and point-to-point connections
• All other type networks unicast Hello.
OSPF Hello Packet
OSPF Hello Packet
• Version. Identifies the OSPF version running on the
router originating the hello packet
• Packet length. Provides the total length of the hello
packet
• Router ID. Contains the originating router identification
number of the appropriate interface
• Area ID. Contains the area number to which the
originating router belongs
• Checksum. This section is, of course, used to ensure the
packets integrity has not been comprised during
transmission.
• Network Mask (4 octets) This field contains the subnet
mask of the advertising OSPF interface. Unnumbered point-
to-point interfaces and virtual links set this value to [Link].
• Hello Interval (2 octets) This field displays the value of the
hello interval requested by the advertising router. Possible
values range from 1 to 255, with a default value of 10
seconds.
OSPF Hello Packet
Options (1 octet) The local router advertises its capabilities in
this field. Each bit in the Options field represents a different
function. The various bit definitions are:
Bit 7 The DN bit is used for loop prevention in a Virtual Private Network (VPN) environment.
An OSPF router receiving an update with the bit set does not forward that update.
Bit 6 The O bit indicates that the local router supports opaque LSAs.
Bit 5 The DC bit indicates that the local router supports Demand Circuits.
Bit 4 The EA bit indicates that the local router supports the External Attributes LSA for carrying
BGP information in an OSPF network.
Bit 3 The N/P bit describes the handling and support of not-so-stubby LSAs.
Bit 2 The MC bit indicates that the local router supports multicast OSPF LSAs.
Bit 1 The E bit describes the handling and support of external LSAs.
Bit 0 The T bit indicates that the local router supports TOS routing functionality.
OSPF Hello Packet
• Router Priority (1 octet) This field contains the priority of the local router.
The value is used in the election of the designated router and backup
designated router. Possible values range from 0 to 255, with a default value
of 128.
• Router Dead Interval (4 octets) This field shows the value of the dead
interval requested by the advertising router. Possible values range from 1 to
65,535.
• Designated Router (4 octets) The interface address of the current
designated router is displayed in this field. A value of [Link] is used when
no designated router has been elected.
• Backup Designated Router (4 octets) The interface address of the current
backup designated router is displayed in this field. A value of [Link] is used
when no backup designated router has been elected.
• Neighbor (Variable) This field displays the router ID of all OSPF routers
for which a hello packet has been received on the network segment.
LSA
LSA Header
LSA fields
• Age is the time, in seconds, since the
LSA was originated. As the LSA is
flooded, the age is incremented by
InfTransDelay seconds at each router
interface it exits. The age is also
incremented in seconds as it resides in
a link-state database.
• Options In the LSA header specifies the
optional capabilities supported by the
portion of the OSPF domain described
by the LSA.
LSA fields
• Type is the LSA type.
• Link State ID identifies the
portion of the OSPF domain being
described by the LSA. The specific
usage of this field varies according
to the LSA type; the descriptions of
each LSA include a description of
how the LSA uses this field.
LSA fields
• Advertising Router is the router ID of
the router that originated the LSA.
• Sequence Number is incremented
each time a new instance of the LSA is
originated, so that other routers can
identify the most recent instance of the
LSA.
LSA fields
• Checksum is the Fletcher checksum of
the complete contents of the LSA
except for the Age field. If the Age field
were included, the checksum would
have to be recalculated every time the
age was incremented.
• Length is the number of octets of the
LSA, including the header.