- link state protocol
- Dijkstra algorithm to calculate the
shortest path tree
Ø fast convergence
Ø larger internetwork
Ø open standard
Ø mature
~> ideal
in multi vendor network
IP protocol
number: 89
Properties:
1. speed of convergence
2. VLSM support and CIDR support
3. dimensionless
4. equal-cost load balancing
5. virtually no reachability limitations
6. BW friendly: multicast link-state updates
& send these updates only when there is a change + send updates every 30
min.
7. area: efficient CPU & memory usage
8. method of path selection: uses cost value
based on the speed of the connection
9. route authentication
10. route tagging for tracking of external routes
OSPF
Terminology:
1.
interface: connection between the router & one of its attached networks
2. link
state: status of link between 2 routers
<~ a
router’s interface and its relationship to its neighborsing routers
<~ link
state are advertised to other router in special packets: link-state
advertisements (LSA)
3. cost:
value assign to a link
4.
autonomous system: group of routers exchanging routing info using a common
routing protocol
5. area: a
collection of networks & routers that have the same area ID
6.
neighbors: 2 routers that have interface on a common network
7. hello:
protocol used by OSPF to establish & maintain neighbor relationship
8.
neighborship db: a listing of all neighbors to which a router has established
bi-directional communication
9. link
state db (topology db): a list of link-state entries of all router in the
network
<~ show
network topology
<~ all
routers within an area have identical link-state db
10. routing-table: generated when shortest path
first (SPF) alg (Dijkstra) in run on the
link-state db.
OSPF
Operation:
1. send Hello packet
2. adjacencies are formed between some
neighbors
3. each router send link state advertisement
(LSA)
4. each router receiving an LSA from neighbor,
records the LSA in its link state db ~> send a copy of the LSA to all
neighbors è flood LSA throughout an area
5. all routers will build identical dbs
6. when dbs is completed ~[SPFalg]~>
calculate loop-free graph
7. builds its route table from its SPF tree
Hello
Protocol
- the mean
by which neighbors are discovered
- advertise
several parameters on which two routers must agree before the can become
neighbors
- act as
keepalives
- ensure
bi-directional communication between neighbors
- elect
Designated Routers (DRs) and Backup Designated Routers (BDRs) on Broadcast and
Nonbroadcast Multipleaccess (NBMA) networks
HelloInterval
default: 10 secs (30 secs on NBMA)
cmd: ip ospf
hello-interval
Hello packet
contain:
1. Router ID
2. Area ID
3. address
mask of the originating interface
4.
authentication type & authentication info
5.
HelloInterval
6.
RouterDeadInterval
7. Router
Priority
8. DR &
BDR
9. flag bits
signifying optional capabilities
10. Router
Ids of the originating router’s neighbors
If a router
has not heard a Hello from a neighbor within a period of time (RouterDeadInterval),
it will declare the neighbor down
RouterDeadInterval
default: 4x HelloInterval
cmd: ip ospf
dead-interval
When a
router receives a Hello packet from a
neighbor, it will verify:
1. Area ID
2.
Authentication
3. Network
mask
4.
HelloInterval
5.
RouterDeadInterval
6. Options
values
If
everything matches
-> Hello
packet is declared valid
->
RouterDeadInterval time is reset (if the ID is already listed)
-> ID is
added to the neighbor table (if ID is not listed)
If they do
not match
-> packet
is dropped and no adjacency is established
When a
router send a Hello, it includes Router IDs of all neighbors for the link on
which the packet is to be transmitted
If a router
receive a valid Hello in which it finds its own Router Ids: the router knows
that two-way communication has been established
Once two-way
communication has been established, adjacencies may be established
<~ not
all neighbors will become adjacent, depends on the type of network
Neighbors
& Adjacencies
Before any
LSAs can be sent, OSPF routes must discover their neighbors and establish
adjacencies.
neighbors
will be recorded in a neighbor table
tracked
using Router ID (by default router choose the numerically highest IP addresses
of its loopback interface, or other interface if loopback is not available)
5 OSPF
Network Topologies:
1. Point-to point networks
2. Broadcast networks
3. Non-broadcast Multi-access (NBMA) networks
4. Point-to-multipoint networks
5. Virtual links
1. Point-to point networks:
dst addr:
AllSPFRouters (224.0.0.5)
ex: T1
2. Broadcast networks:
will elect a
DR and a BD
hello
packets are multicast: AllSPFRouters (224.0.0.5, MAC addr: 0100.5E00.0005)
all other
routers will multicast link state update and link state acknowledgement
packets: AllDRouters (224.0.0.6, MAC addr: 0100.5E00.0006)
ex:
Ethernet, Token Ring, FDDI
3. Non-broadcast Multi-access (NBMA) networks:
connecting
more than but have no broadcast
capability
will elect a
DR and a BDR
all OSPF
packets are unicast
ex: X.25,
Frame Relay, ATM
4. Point-to-multipoint networks:
do not elect
a DR and a BDR
OSFP packets
are multicast
5. Virtual links:
as
unnumbered point-to-point networks
all OSFP
packets are unicast
all networks
fall into one of two more-general type:
1. Transit networks
have two or
more attached routers
carry
packets that are “just passing through”
2. Stub networks
have only a
single attached router
either a src
or a dst addr belonging to the network
DR & BDR
Two problems
on multi-access networks:
1. n^2 LSA originating from the network
2. many copies of the same LSA on the same
network
Solution:
Designated Router (DR) & Backup Designated Router (BDR) with duties:
1. represent the multi-access network and its
attached routers
2. manage flooding process
Each routers
on the network forms an adjacency with the DR and BDR
Only the DR
will send LSAs to the rest of the internetwork
If DR fails,
BDR becomes the new DR.
DR & BDR
Election process:
if there is
no BDR ~> router with the highest priority becomes BDR
if there is
not DR ~> BDR is promoted to DR, a new election is held for the BDR
(i) priority
can influence an election but will not override an active DR or BDR
DRothers:
other routes (not DR/BRD) <~ establish adjacency with DR and BDR only
How it
works:
all routers:
multicast Hellos to AllSPFRouters (224.0.0.5)
DRothers:
multicast updates to AllDRouters (224.0.0.6) <~ only DR and BDR will listen
DR will
flood updates to DRothers on (224.0.0.5)
OSPF Packet
Types
Type
Packet name
Protocol functuion
1
Hello
discover/maintain neighbors
2
Database Description (DD)
summarize database contents
3
Link State Request (LSR)
database download
4
Link State Update (LSU)
database upload
5
Link State Ack (LSAck)
flooding acknowledgment
OSPF Packet
Header Format (man how I love sniffing packets ;):
All OSPF
packets share a common 24-octet header
Version (1
octet)
- Version of
OSPF
- default: 2
Type (1
octet)
- Specifies
the type of OSPF packet:
1 - Hello
2 - Database Descriptor
3 - Link-State Request
4 - Link-State Update
5 - Link-State Aknowledgment
Packet
Length (2 octets)
-Total
length of OSPF packet
Router ID (4
octets)
- router ID
of the advertising router
Area ID (4
octets)
- 32-bit
area ID
Checksum (2
octets)
- IP
checksum of the entire OSPF packet, excluding the 64-bit authentication field.
Authentication
Type (2 octets)
- Type of
authentication, possible values:
0 – Null authentication
1 – Simple password
2 – MD5 cryptographic authentication
Authentication
(8 octets)
-
Authentication data to verify the
packet’s integrity
Hello
packets
Type code 1
To establish
and maintain a neighbour relationship
Router sends
OSPF hello packet out all configured interface and awaits a response
Addressed to
AllSPFRouters mcast addr 224.0.0.5 for broadcast and point-to-point network.
Network Mask
(4 octets)
- Contain
the subnet mask of the advertising OSPF interface
- Unnumbered
point-to-point interface and virtual link set this value to 0.0.0.0
Hello
Interface (2 octets)
- Hello
interval requested
- Possible
values: 1 - 255, default value: 10 secs
Option (1
octet)
- Advertises
its capabilities
- Each
options field represents a different functions:
Bit 7: DN bit: for loop prevention in VPN
environment. An OSPF router receving an update with the bit set does not
forward that update
Bit 6: O bit: indicates that the local router
support opaque LSAs
Bit 5: DC bit: indicates that the local
router supports Demand Circuits (not support by JunOS)
Bit 4: EA bit: indicates that the local
router support External Attributes LSA for carrying BGP information in a OSPF
net, (not supported by JunOS)
Bit 3: N/P bit: describe the handling and
support of NSSA LSAs.
Bit 2: MC bit: indicates that the local
router supports mcast OSPF LSA (not supported by JunOS, IOS, AlliedWare)
Bit 1: E bit: describes the handling and
support of external LSAs
Bit 0: T bit: indicates that the local router
supports TOS routing functionality (not supported by JunOS, IOS)
Router
Priority (1 octet)
- Priority
of the local router
- Used in
the election of the DR & BDR
- Possible
values: 1 - 255, default: 128
Router Dead
Interval (4 octets)
- Value of
Dead Interval
- Possible values:
1 – 65535, default: 40 sec (hello X 4)
Designated
Router, DR (4 octets)
- interface
addr of the current DR
- when no
DR: 0.0.0.0
Backup
Designated Router, BDR (4 octets)
- interface
addr of the current BDR
- when no
BDR: 0.0.0.0
Neighbor
(Variable)
- Display
the router ID of all OSPF routers for which a hello packet has been received.
Database
Description packet
Type code 2
After
discovering its neighbours, the local router begins to form an adjacency with
each neighbor.
This
adjacency process requires that each router advertise its local database
information. OSPF router uses the Database Description (DD) packet for this
purpose.
Summarizes
the local database by sending LSA headers to the remote router. The remote
router analyzes these headers to determine whether it lacks any information
within its own copy of link-state database.
Interface
MTU (2 octets)
- MTU value,
in octets, of the outgoing interface
- Virtual
link interface set value to 0x0000
Options (1
octet)
- Advertises
its capabilities, same bit definition as Hello packet
Flag (1
octet)
- Provides
an OSPF router with the capability to exchange multiple DD packets with a
neighbor during an adjacency formation:
Bit 3 – 7:
currently undefined and must be set to 0
Bit 2: I bit
/ Initial bit: designates whether this DD packet is the first in a series of
packets. The first has a value of 1, while the subsequent packets have a value
of 0
Bit 1: M bit
/ More bit: informs the remote router whether the DD packet is the last in a
series. The last packet has a value of 0, while the previous packets have
values of 1
Bit 0: MS
bit / Master/Slave bit: indicates which OSPF router is in control of the
database synchronization process. The master router uses a value of 1, the
slave uses value of 0
DD Sequence
Number (4 octets)
- Guarantees
that all DD packets are received and processed during the synchronization
process through use of a sequence number
- The Master
router initializes this field to a unique value in the first DD packet, with
each packets being incremented by 1
LSA Headers
(variable)
- Carries
the LSA headers describing the local router’s database information
- Each
header is 20 octets in length and uniquely identifies each LSA in the database
- Each DD
packet may contain multiple LSA headers
Link State
Request packet
Type code 3
During the
database synchronization process, the local router may find that it is missing
information or that its local copy is out of date. The local router acquires
the needed database information by sending link-state request packet to its
neighboring router. The packet contain identifiers that uniquely describe the
requested LSA. An individual link-state request packet may contain a single set
of identifiers or multiple sets to request multiple LSAs.
Link-State
Type (4 octets)
- Display
the type of LSA being requested
- Possible
type code:
1- Router LSA
2 - Network LSA
3 - Network Summary LSA
4 - ASBR Summary LSA
5 - AS external LSA
6 - Group membership LSA
7 - NSSA external LSA
8 - External attribute LSA
9 - Opaque LSA (link-local scope)
10 - Opaque LSA (area scope)
11 - Opaque LSA (AS scope)
Link-State
ID (4 octets)
- Encodes
information specific to the LSA
- Each
different type of advertisement places different info here
Advertising
Router (4 octets)
- Router ID
of the OSPF router that first originated the LSA
Link State
Update packet
Type code 4
Information
in the link-state database is populated through a LSA.
Each LSA
contain routing, metric, and topology info to describe a portion of the OSPF
net. The local router advertise LSAs within a link-state update packet. This
packet is reliably flooded throughout the net until each router has a copy.
Local router
advertise a link-state update in response to a link-state request for info.
Number of
LSAs (4 octets)
- Display
the number of LSAs carried within packet
Link-State
Advertisements (variable)
- Complete
LSA is encoded within this variable-length field.
- Each type
of LSA has a common header format along with specific data fields to describe
its information.
- May
contain a single or multiple LSAs.
Link State
Acknowledgment packet
The
reliability of OSPF arises from the fact that each router is required to
acknowledge the receipt of each LSA.
Simply
contain the common OSPF header followed by a list of LSA headers.
May contain
a single or multiple header LSAs.
OSPF
Interfaces:
Interface
Data Structure (cmd: show ip ospf interaface):
1. IP addr
2. area ID
3. process ID (Cisco specific)
4. router ID
5. network type
6. cost
7. InfTransDelay
8. State
9. Router priority
10. DR
11. BDR
12. HelloInterval
13. RouterDeadInterval
14. wait timer
15. RxmtInterval
16. hello timer
17. neighboring routers
18. AuType
19. authentication key
Interface
State Machine:
1. down
2. point-to-point
3. waiting
4. DR
5. BRD
6. Drother
7. loopback
OSPF
Neighbors
4 phase
adjacency establishment:
1. neighbor discovery
2. bi-directional communication
3. database synchronization
4. full adjacency
Hellos:
broadcast
net, point-to-point net: multicast
Hellos to AllSPFRouters (224.0.05)
NBMA net,
point-to-multipoint net, virtual
link net: unicast Hellos
Neighbor
Data Structure (cmd: show ip ospf neighbor)
1. neighbor ID
2. neighbor IP addr
3. area ID
4. interface
5. neighbor priority
6. state
7. PollInterval
8. neighbor options
9. inactivity timer
10. DR
11. BDR
12. Master/Slave
13. DD sequence number
14. last received DD packet
15. link state restransmission list
16. database summary list
17. link state request list
Neighbor
State Machine:
1. Down
2. Attempt (only NBMA)
3. Init: hello has been seen
4. 2-way: has seen its own ID
5. ExStart: established M/S relation
6. Exchange: sends DD
7. Loading: sends link state request
8. Full: full adjacent
Building
Adjacency:
~>
point-to-point net, point-to-multipoint, virtual link net: always become
adjacent
~>
broadcast net, NBMA net: DR & BDR become adjacent will all neighbors, but
no adjacencies will exist between DRothers
Adjacency
building process uses three OSPF packet types:
1. Database Description (DD) packets (type 2)
2. Link State Request packets (type 3)
3. Link State Update packets (type 4)
Three flags
in the DD packets:
1. the I-bit: Intial bit <~ indicates the
first DD packet sent
2. the M-bit: More bit <~ indicates that
this is not the last DD packet to be sent
3. the MS-bit: Master/Slave bit <~ set in
the DD packets originated by the master
~~~~~ExStart
LSA may be
acknowledge by either:
1. Explicit Acknowledgement
2. Implicit Acknowledgement
Flooding:
Entire OSPF
topology may be depicted as a group of routers, or nodes, interconnected not by
physical links but by logical adjacencies
<~ each node must posses an identical map of the OSPF topology
database = link state database.
To make sure
all nodes have identical link state database: flooding LSAs.
Flooding use
2 OSPF packet types:
1. Link State Update (type 4)
2. Link State Acknowledgement (type 5)
~ each
packets may carry multiple LSAs.
~ Update
& Acknowledgement packets travel
only between 2 nodes across an adjacency!
>
point-to-point net: Updates are sent to multicast address AllSPFRouters
(224.0.0.5)
>
point-to-multipoint & virtual link net: Updates are sent to interface
unicast address
>
broadcast net: Updates are sent to multicast address AllDRouters (224.0.0.6)
<~ DRothers form adjacency only with DR & BDR, DR in turn multicast
Update to all adjacent routers, AllSPFRouters.
> NBMA
net: LSAs unicast from DRothers to DR & BDR, and the DR unicast a copy of
the LSA to all adjacent neighbors.
To guarantee
reliability, LSA Update must be acknowledged.
Acknowledgment
->
Implicit acknowledgment: by including a duplicate of the LSA in an update of
the LSA in an update back to the originator
->
Explicit acknowledgement: by sending a Link State Acknowledgment packet <~ a
single Link State Acknowledgement packet can acknowledge multiple LSAs.
-> delayed
acknowledgement: by delaying, so more LSAs can be acknowledged in a single Link
State Acknowledgement packets.
-> direct
acknowledgement: sent immediately.
Reliable
Flooding is based on 3 values that that are contained within each LSAs
1. sequence number : 32-bit, each new instance
of LSA, the router increment by one
2. checksum: 16-bit, calculated over entire
LSA except Age field
3. age: 16-bit, in seconds range 0 – 3600,
router that originates and LSA set the age to 0, as the flooded LSA transit a
router, age is incremented by InfTransDelay seconds. (cmd: ip ospf
transmit-delay).
When LSA
reaches MaxAge: LSA is reflooded and then flushed from the database.
When
multiple instances of the same LSA are received, to determines the most recent:
1. compare the seq number: higher = more
recent
2. compare the check sum: higher = more recent
3. compare the age, if only one of the LSAs
has an age of MaxAge (3600 sec), it’s considered more recent, else:
4. if the ages of the LSA differ by more than
15 min: LSA with the lower age is more recent
5. if none of the preceding conditions are
met: the 2 LSAs are considered identical.
OSPF area:
surprise
surprise SPF algorithm is not particularly processor intensive, but flooding
and database maintenance that consume CPU power…
So OSPF uses
area to reduce the problem:
area:
logical grouping of OSPF routers and links that divide OSFP domain into
sub-domain.
the
benefits:
- the
smaller the size of area -> less memory needed
- the
smaller link state database -> less impact on CPU
- the
smaller the size of area -> limited flooding inside area
Area ID:
- 32-bit
- expressed as a decimal number or dotted
decimal
- Area ID 0 (0.0.0.0) is reserved for
backbone
3 types of
traffic related to areas:
1. Intra-area: between routers within a single
area
2. Inter-area: between routers in different
areas
3. External: between a router within OSPF
domain and router within another AS
6 Area
Types:
1. Backbone
Area:
- area 0
-
responsible for summarizing the topographies of each to every other area
- all
inter-area traffic must pass through the backbone, a special area that can
always act as transit area between other areas, between this OSPF AS and
external networks, or even between external networks
2. Regular
Area:
- connect to
the backbone area.
- routers
see Type 1 & 2 LSAs
- use Type 3
LSAs to learn how to route to dst in other area
- use Type 5
& 6 LSAs when routing to dst outside OSPF net
* all other
area are modification of regular area
3. Stub
Area:
- cannot
make connections to ext net via a stub area
- see
detailed routing info an all other areas, but only summary info about netwokrs
outside of the AS
- ABR
connecting to a stub area summarizes routes to ext network outside of the AS
<- all ext routes are reduced to a single summary
- ,most
useful when there are may ext routes
4. Totally
Stub Area (aka stub no-summary area):
- summarize
not only ext routs, but aslo routes from other areas (int routes)
- only see
routing info local to their area + a default route pointing to the ABR
- useful in
WAN setup
5. Not So
Stubby Area (NSSA):
- RFC 1586
- a variant
of stub area that is able to connect to ext net
- use Type 7
LSA that is used within area to carry ext routs that originate /w ASBRs
connected to this area <- ABR summarizes only those ext routes that are
received from other areas, ext routes from ASBR inside the area are not
summarized
6 Totally
Stubby Not So Stubby Area
- the
weirdest name area ;)
- combines
the best of NSSA and totally stub area, by summarizing info from all other
area, but handling ext routes like NSSA
4 Router
Types:
1. Internal Routers: whose all interfaces
belong to the same area
2. Area Border Routers (ABRs): connect one or
more areas to the backbone & act as a gateway for inter-area traffic <-
at least one interface that belong to the backbone & must maintain a
separate link state database for each of its connected areas
3. Backbone Routers: at least one interface
attached to the backbone. Not all Backbone Routers are ABRs <- i.e. internal
router whose interfaces all belong to area 0.
4. Autonomous System Boundary Routers (ASBRs):
gateways for external traffic, injecting routes into the OSPF domain.
Partitioned
Areas: area in which a link failure causes one part of the area to become
isolated.
Virtual
links: link to the backbone through a non-backbone area
used for:
- to link an area to the backbone through a
non-backbone area
- to connect the 2 parts of partitioned
backbone through a non-backbone area
rules
for virtual links:
- must be configured between two ABRs.
- area through which the virtual link is
configured, transit area, must have full routing info
- transit area cannot be a stub area
Link State
Database
All valid
LSAs received are stored in link state database
cmd: show ip
ospf database
LSAs are
aged as they reside in the link state database, if they reach MaxAge (1 hour),
they are flushed.
to prevent
legitimate LSAs from reaching MaxAge:
every 30
minutes: router that originated LSA will flood a new copy of the LSA with
incremented sequence number and an age of zero <- link state refresh
upon
receipt: the other router will replace the old copy of LSA and begin aging the
new copy
group pacing:
associating
individual timer for each LSA avoid all LSAs expire all at once ->
reflooding will be spread out in a semirandom pattern causing bandwidth is used inefficiently
to solve
this problem: LSA group pacing <~ each LSA has its own refresh timer, but as
the individual refresh timers expire, a delay is introduced before the LSA are
flooded. By delaying more LSAs can be grouped together before being flooded :
Update packets are carrying a large number of LSAs
cmd: timers
lsa-group-pacing (10 – 1800 secs).
If the
database is very large: decreasing the group pacing interval is beneficial.
If the
database is small: increasing the interval can be useful.
LSA Types
Type Code
Description
1
2
3
4
5
6
7
8
9
10
11
Router LSA
Network LSA
Network
Summary LSA
ASBR Summary
LSA
AS External
LSA
Group
Membership LSA
NSSA
External LSA
External
Attributes LSA
Opaque LSA
(link-local scope)
Opaque LSA
(area-local scope)
Opaque LSA
(AS scope)
1 Router LSA
- produced
by every router
- most
fundamental LSA
- list all
router’s links / interfaces + cost
- flooded
only within the area in which they are originated
cmd: show ip
ospf database router
2 Network
LSA
- produced
by the DR
- list all
attached routers
- Network
LSA represents a pseudonode just as Router LSA represents a single physical
router
-flooded
only within the originating area
cmd: show ip
ospf database network
3 Network
Summary LSA
- originated
by ABRs
- sent into
a single area to advertise destinations outside that area
<~ tells
the Internal Router of an attached area what destinations the ABR can reach.
- ABR also
advertise within its attached areas into the backbone with Network Summary LSAs
- default routes external to the area but
internal to the OSPF AS are also advertise by this LSA type
- ABR will
originate only a single Network Summary LSA for each destination even if it
knows of multiple routes (the lowest cost)
- when outer
router receives a Network Summary LSA, it doesn’t run SPF alg, simply adds the
cost of the route to the ABR and the cost included in the LSA.
<~ while
OSPF is a link state protocol within an area, it uses a distance vector alg to
find inter-area routes.
cmd: show ip
ospf database summary
4 ASBR
Summary LSA
- originated
by ASBRs
- identical
to Network Summary LSAs except that the destination they advertise in an ASBR
cmd: show ip
ospf database asbr-summary
5 AS
External LSA
- originated
by ASBRs
- advertise
either a destination external to the OSPF AS or default route external to the
OSPF AS
cmd: show ip
ospf database external
6 Group
Membership LSA
- used in
Multicast OSPF (MOSPF)
7 NSSA
External LSA
- originated
by ASBRs within not-so-stubby areas
(NSSAs)
- almost
identical to an AS External LSA
- unlike AS
External LSAs, which are flooded throughout an OSPF AS, NSSA external LSAs are
flooded only within the not-so-stubby area in which it was originated
cmd: show ip
ospf database nssa-external
8 External
Attributes LSA
- proposed
as an alternative to running Internal BGP (iBGP) in order to transport BGP
information across an OSPF domain
9, 10, 11
Opaque LSA (link-local scope, area-local scope, AS scope)
- proposed
class of LSAs that consist of a standard LSA header followed by
application-specific information
LSA types
allowed per area type:
Area Type
1 & 2
3 &4
5
7
Backbone
(area 0)
Non-backbone,
non-stub
Stub
Totally
stubby
Not-so-stubby
* except for
a single type 3 LSA per ABR, advertising the default route
LS Type Description
___________________________________
1 Router-LSAs
2 Network-LSAs
3 Summary-LSAs (IP network)
4 Summary-LSAs (ASBR)
5 AS-external-LSAs
