Transcript Slides

Open Shortest Path First Protocol
(OSPF)
Sudarshan Vasudevan
[email protected]
Overview
•
•
•
•
•
Introduction
Motivation
OSPF Basics
Hierarchical Routing in OSPF
Summary
Introduction
•
•
•
•
•
Development began in 1987
OSPF Working Group (part of IETF)
OSPFv2 first established in 1991
Many new features added since then
Updated OSPFv2 specification in RFC 2178
Motivation
•
•
•
•
Original IGP used was RIP
Based on Bellman-Ford Algorithm
Worked well in small systems
Suffered from problems of Distance Vector
Protocol
– Count to Infinity Problem
– Slow Convergence
Motivation
• Problems with Distance Vector Protocol
– Large update packets
– Slow response to topological changes
• Need for a Link State Protocol
• A long list of functional requirements
follows
Functional Requirements of OSPF
• Faster Convergence and less consumption
of network resources
• A more descriptive routing metric
– configurable
– value ranges between 1 and 65,535
– no restriction on network diameters
• Equal-cost multipath
– a way to do load balancing
Functional Requirements(contd.)
• Routing Hierarchy
– support large routing domains
• Separate internal and external routes
• Support of flexible subnetting schemes
– route to arbitrary [address,mask] combinations
using VLSMs
• Security
• Type of Service Routing
OSPF Basics
the essence
• Distributed, replicated database model
– describes complete routing topology
• Link state advertisements
– carry local piece of routing topology
• Distribution of LSAs using reliable flooding
• Link state database
– identical for all the routers
Link State Advertisements(LSAs)
LS Age
Options
LS Type
Link State ID
Advertising Router
LS Sequence Number
LS Checksum
Length
0
16
LSA Header
LSAs contd.
• Identifying LSAs
– LS type field
– Link State ID field
• mostly carries addressing information
• e.g. IP address of externally reachable network
– Advertising Router field
• originating router’s OSPF router ID
LSAs contd.
• Identifying LSA instances
– needed to update self-originated LSAs
– LS Sequence Number field
•
•
•
•
32 bit values
monotonically increasing until some max value
600 years to roll over!
LSA checksum and LS Age guard against potential
problems
LSAs contd.
• Verifying LSA contents
– LS Checksum field
• computed by the originating router and left
unchanged thereafter
• LS age field not included in checksum
• Removing LSAs from databases
– LS Age field
• ranges from 0 to 30 min.
• Max Age LSAs used to delete outdated LSAs
LSAs contd.
• Other LSA Header fields
– Options field
• sometimes used to give special treatment during
flooding or routing calculations
– Length field
• includes LSA header and contents
• ranges from 20-65535 bytes
Sample Router LSA
10.1.1.1
10.1.1.2
10.1.1.3
10.1.1.4
10.1.1.5
10.1.1.6
Sample Router LSA contd..
LS Age
Options
LS Type
0 seconds
E-bit,LS Type 1
Link State ID
10.1.1.1
Advertising Router
10.1.1.1
LS Sequence Number
LS Checksum
Length
Router Type
0x9b47
60 bytes
0
# of links
Link 1
Link Type
0x80000006
0 (ordinary)
3
Link ID
10.1.1.3
Link Data
Ifindex 2 (unnumbered link)
#TOS Metrics
Metric
1(point to point), 0
5
Link State Database
•
•
•
•
•
Collection of all OSPF LSAs
databases exchanged between neighbors
synchronization thru reliable flooding
gives the complete routing topology
each OSPF router has identical link-state
database
Link State Database contd..
• Example of a link state database
LS Type
Router LSA
…..
Link State ID
10.1.1.1
…...
Adv Router
10.1.1.1
…..
LS Checksum
0x9b47
…..
LS Seq No
0x80000006
….
LS Age
0
…...
Communication between OSPF Routers
• OSPF packets encapsulated in IP packets
–
–
–
–
–
–
standard 24 byte header
OSPF packet type field
OSPF router ID of sender
Packet checksum
Authentication fields
OSPF Area ID
Neighbor Discovery and Maintenance
•
•
•
•
•
•
OSPF Hello Protocol
Hello packets sent out every 10 seconds
helps to detect failed neighbors
RouterDeadInterval (default 40 seconds)
also ensures that link is bidirectional
neighboring routers agree on intervals
– hello interval set so that a link is not accidentally
brought down
Database Synchronization
• Crucial to ensure correct and loop free routing
• must be done before 2 neighbors start
communication
• also whenever new LSAs are introduced
– uses reliable flooding
• each router sends LSA headers to its neighbor
when connection comes up
• requests only those LSAs which are recent
Database Exchange
• Neighboring routers first exchange hellos
• a database description packet packet establishes
the sequence number
• the other router sends LSA headers
• sequence number incremented for every pair od
database description packets
– implicit acknowledgement for the previous pair
• after examining LSA headers explicit request sent
for complete LSAs
Reliable Flooding
• Starts when a router wants to update selforiginated LSAs
• Link State Update packets
• Neighbor installs more recent LSAs into its
database
• floods out on all interfaces except the one on
which it arrived
• reliability-retransmissions until acks received
Reliable Flooding (contd..)
10.1.1.1
10.1.1.2
10.1.1.4
Time T1
u
u
10.1.1.3
u
10.1.1.5
10.1.1.6
Reliable Flooding (contd..)
10.1.1.1
Time T2
u
10.1.1.2
u
10.1.1.4
10.1.1.6
u
u
u
10.1.1.3
10.1.1.5
Reliable Flooding (contd..)
10.1.1.1
10.1.1.2
10.1.1.4
u
Time T3
u
10.1.1.3
10.1.1.5
10.1.1.6
Reliable Flooding (contd..)
10.1.1.1
10.1.1.2
10.1.1.4
10.1.1.6
Time T3+
ack
ack
ack
10.1.1.3
ack
10.1.1.5
ack
Reliable Flooding(contd..)
• Robustness
– updates flooded over all the links , so failure of any link
doesn’t affect database synchronization
– LSAs refreshed every 30 minutes
– LSA checksum field detects corruption
– flooding loops avoided by LS Age field
– MinLSInterval limits rate of LSA origination
– Receivers can refuse to accept LSA updates if they
received an update less than a second ago
Routing Calculations
•
•
•
•
•
Link costs configurable by administrator
Smaller values for more preferred links
must make sense to add link costs
different costs for each link direction possible
Dijkstra’s shortest path algorithm
– incrementally calculates tree of shortest paths
– each link in the network examined once
– computes multiple shortest paths (equal-cost multipath)
Hierarchical Routing
• Technique used to build large networks
• minimizes consumption of network resources such
as
– router memory
– router computing resources
– link bandwidth
• with flat routing linear increase in routing table
size
• with hierarchical, size increases logarithmically
an example
10.3.3
10.3
10.0.0.0/8
10.3.1
10.1.3
10.1.1
10.3.2
10.2.3
10.1
10.1.2
10.2
10.2.1
10.2.2
example contd..
• Consider a router in 10.1.1
• assume 16 entries in each of the first level
partitions
• with flat routing, 9*16 = 144 entries/router
• with 3 level hierarchy, the router has 16 entries
within 10.1.1.0/24 + entries for 10.1.2.0/24,
10.1.3.0/24,10.1.0.0/16 for a total of 19 entries.
• Marked reduction in routing table size
• but might lead to suboptimal routing
OSPF Areas
• Two-level hierarchical routing scheme through the
use of areas
• areas identified by 32-bit id
• each area has its own link state database which is a
collection of network-LSAs and router-LSAs
• area’s topology hidden from all other areas
• interconnection of areas through area border
routers (ABRs)
• ABR leaks IP addressing information to other
areas through summary LSAs
Sample Area Configuration
Area 0.0.0.1
10.2.1.0/24
1
10.2.2.0/24
3
I
1
J
3
3
B
C
Area 0.0.0.2
Area 0.0.0.3
10.1.2.0/24
1
G
1
2
3
1
AA
E
2
Area 0.0.0.0
3
H
3
1
10.3.7.0/24
D
3 10.8.2.0/24
1
10.1.1.0/24
1
1
3
F
1
OSPF Areas contd..
• Example of Summary LSA(router B)
LS Age
Options
0
LS Type
Link State ID
Advertising Router
LS Sequence Number
0x2, Type 3(summary-LSA)
10.2.0.0
Router B’s router ID
0x80000001
LS Checksum
Length
Network Mask
TOS
Metric
28 bytes
255.255.0.0
TOS 0 (normal)
Cost of 7
OSPF Areas contd..
• Reduction in link state databases of an area
• reduction in amount of flooding traffic needed for
synchronization
• reduction in the cost of the shortest path
calculations
• increased robustness
• routing protection
• Hidden prefixes
Area Organization
• All the areas are connected to area 0.0.0.0 also
called the backbone area
• need not have a direct physical connection though
– virtual links provide logical link to backbone
– summary LSAs tunneled across non backbone areas
• exchange of routing information between areas
using Distance Vector Protocol
– absence of redundant paths between areas
– not subject to convergence problems
Incorporating external routing information
• Special routers called AS boundary routers at the
edge of OSPF domain
• ASBRs originate AS-External LSAs
• only routes for which the choice of an ASBR
makes sense are imported
• otherwise default routes are used
• AS external LSAs similar to Summary LSAs with
2 additional fields
– Forwarding address
– external route tag
Interaction with areas
• AS-External LSAs flooded across borders
• ASBR summary LSAs used to know the location
of the originator of AS-External LSA
• Link State ID of ASBR Summary LSA set to the
OSPF router ID of the ASBR whose location is
advertised
• similar to summary LSA in all other respects
OSPF Area Types
• Restrict the amount of external routing
information within an area
• used when resources especially router memory is
very limited
• two types of restricted areas
– Stub Areas
– NSSAs or Not-So-Stubby-Areas
OSPF Area Types
• Stub Areas
– don’t support ASBRs and hence no AS-External-LSAs
– routing to external destinations based on default routes
originated by the area’s border routers
– summary LSAs also made optional
– must lie on the edge of OSPF routing domain
– inter-area routing may also be based on default routes
– improved scaling
– but not preferred due to the possibility of suboptimal
routes
OSPF Area Types contd..
• NSSAs
– import small amount of routing information
– this information flooded to other areas by the NSSA
Border router
– Use Type-7 LSAs to import external routing
information
– translated into AS-External-LSA at the NSSA Border
– one-way filter
Summary
• Why OSPF is needed in the Internet?
• The basics of the protocol
– The Link state Advertisements
– Neighbor Discovery (Hello Protocol)
– Database Synchronization and reliable flooding
• Hierarchical Routing in OSPF
– OSPF Areas and Area Organization
– Interaction with External Routing Information
– OSPF Area Types viz. Stub Areas and NSSAs
Issues not covered
• OSPF Network Types
– Broadcast subnets
– NBMA Subnets
•
•
•
•
OSPF Extensions
Multicast Routing using OSPF (MOSPF)
OSPF Management
and a whole lot of others!
Further Reading
• John T. Moy, OSPF - An Anatomy of an Internet
Routing Protocol
• Christian Huitema, Routing in the Internet
• RFC 2178
Concluding Remark
Thank You!