Open Shortest Path First Notes
Table of Contents
What is OSPF⌗
Open Shortest Path First (OSPF) is an Open-Standard Interior Gateway Protocol (IGP) routing protocol. Unlike other Routing Protocols such as Routing Information Protocol (RIP), Enhanced Interior Gateway Routing Protocol (EIGRP) or Border Gateway Protocol (BGP), OSPF uses the
Link State Algorithm in conjunction with Edsger W. Dijkstra
Shortest Path First (SPF) algorithm to send out OSPF advertisements, known as
Link-State Advertisements (LSAs), to share its Local
Link-State Database (LSDB) with OSPF enabled devices to create an overall topology of every router, link state and link metric within a network. OSPF is defined in RFC2328:
OSPF is a link-state routing protocol. It is designed to be run internal to a single Autonomous System. Each OSPF router maintains an identical database describing the Autonomous System’s topology. From this database, a routing table is calculated by constructing a shortest-path tree.
OSPF recalculates routes quickly in the face of topological changes, utilizing a minimum of routing protocol traffic. OSPF provides support for equal-cost multipath. An area routing capability is provided, enabling an additional level of routing protection and a reduction in routing protocol traffic. In addition, all OSPF routing protocol exchanges are authenticated.
OSPF advertises and receives LSAs to/from neighbouring routers; these LSAs are stored with the router’s local LSDB. Whenever there is a change in the network new LSA’s will be flooded across the routing domain and all the routers will have to update their LSDB. This is due to the nature of the Link State and SPF Algorithms; essentially all OSPF routers have to same synchronized identical copy of the Link State Database to have a complete loop-free map of the network topology.
OSPF can be described as a two-tier hierarchical structure. This is because you have two main area types:
Backbone Area and
Non-Backbone Areas. The Backbone Area is known as
Area 0 and Non-Backbone Areas are all other Areas. All Non-Backbone Areas MUST connect to Area 0. It is important to note, that OSPF routers in different Areas DO NOT have the same synchronized identical copy of each Link State Database however routers within the same Area will have an identical Link State Database. This is because; Area 0 provides transit for All Non-Backbone Areas. Non-Backbone Areas advertise their routes into Area 0 and Area 0 will advertise all routes learnt to the other Areas, as shown here
Communication between OSPF routers is done, dependent on network type, over IP using it own protocol number 89 sending multicast OSPF packets between each other. There are two multicast addresses that have been defined for OSPF enabled routers/interfaces to dynamically find neighbours. RFC2328 defines them as:
AllSPFRouters: This multicast address has been assigned the value 188.8.131.52. All routers running OSPF should be prepared to receive packets sent to this address. Hello packets are always sent to this destination. Also, certain OSPF protocol packets are sent to this address during the flooding procedure.
AllDRouters: This multicast address has been assigned the value 184.108.40.206. Both the Designated Router and Backup Designated Router must be prepared to receive packets destined to this address. Certain OSPF protocol packets are sent to this address during the flooding procedure.
OSPF Packet Details⌗
As stated above, OSPF has it own dedicated IP protocol as reserved by Internet Assigned Number Authority (IANA) within the protocol, OSPF exchanges 5 types of packets:
|Type||Packet Name||Packet Function|
|2||Database Description (DBD/DDP)||
|3||Link-State Request (LSR)||
|4||Link-State Update (LSU)||
OSPF Hello Messages Details⌗
As stated earlier, an OSPF Packet will be exchanged between routers to allow them to have the same synchronizes OSPF database. For Adjacency discovery and maintenance; an OSPF Hello Message is flooded to all enabled interfaces, two routers that have the same matching hello messages will create an OSPF adjacency. The table below shows all the parameters that are within a Hello Message, with the first eight parameters needing to match for an adjacency to form:
|Hello Interval||Amount of time between hello packets being sent and recieved|
|Dead Interval||How long to wait between hello packets before marking the neighbour as dead, by default the dead interval is 4x the hello interval. Essentially, the router can miss for hello interval before updating that the neighbour is down|
|Area ID||Both neighbour in the same OSPF Area.|
|Subnet Mask||This is for connectivity both neighbours will need to be in the same subnet|
|Stub Area Flag||This is for when the neighbour has been defined as Stub Area. Within OSPF all Areas that have been defined as Stub Areas mark their hello messages with the Stub Flag|
|Authentication||Securing communication between neighbours. This can be configured with None, Clear Text or MD5|
|OSPF Router ID||An unique 32-bit ID number that’s set in dotted-decimal format|
|Maximum Transmission Unit (MTU)||As OSPF doesn’t support packet fragmentation, the MTU must be the same on both side. From my experiences this is only changed if you are using Jumbo Packet sizing|
|Router Priority||Used to determine Designated and Backup Designated Routers|
|Designated Router & Backup Designated Router||The IP addresses of the Designated and Backup Designated Routers|
|Active Neighbours||List of all the neighbours (the router) has recieved a Hello Message from, within the dead interval|
OSPF uses its ALLSPFRouters address to send out hello messages across all OSPF enabled interfaces. It is important to add that if you have an interface that has been set as a passive OSPF interface, this interface will still be advertised into an OSPF routing domain however hello messages ARE NOT sent out. From my experiences this is commonly used on loopback address or external/customer facing interfaces. As you would want to advertise the subnet into OSPF however you wouldn’t want to have start an OSPF Neighbour Relationship between your ISPs or Customers.
The OSPF Router-ID is an important attribute when it comes to identifying a router within the OSPF domain. Each OSPF router has a Router-ID that is associated with the OSPF process, so it is possible to have to have two different processes active on single router with two different Router-IDs. The OSPF Router-ID has to be configured in 32-bit dotted decimal format, this is case whether you are using OSPFv2 (IPv4) or OSPFv3 (IPv4 and IPv6). As discussed in RFC2328
As each router will be getting an ID number, it is important to note, that these IDs have to be unique and no neighbour in the same OSPF domain can have same Router-ID. If two routers were to have same Router-ID, they wouldn’t be able to create a neighbour relationship. Additionally other neighbours peered with the both will have an issues with OSPF updates that come from the same Router-ID however the link-state databases are different, this can cause OSFP Flood War
OSPF Router-ID Selection Process⌗
The process of selecting the Router-ID within OSPF follows this order:
Hard Coding the Router-ID: If the Router-ID manually configured under the OSPF process this take precedence over everything.
This is recommended and best practice
Highest Logical IP Address: This will be the highest loopback address configured on the router
Highest Active Physical IP address: This will be the highest IP address configured on a physical interface on the router
If you don’t hard code the router-id you will need to always remember, when you are making IP address updates on the router if you configure a new loopback or interface IP address that is higher than the currently OSPF Router-ID, it will change the Router-ID and can cause OSPF re-convergence, if the process is cleared or the device is reloaded.
OSPF Neighbour Adjacency Process⌗
With OSPF, unlike, other IGPs has 2 Neighbour Adjacency states:
OSPF Neighbours: OSPF Neighbours are when two routers/devices have stop at the 2-Way neighbour state. At this state the neighbours bidirectional connectivity and all the OSPF parameters match. But it is important to note that the neighbours DO NOT exchange their link-state databases at this state.
OSPF Fully Adjacent Neighbours: OSPF Fully Adjacent Neighbours is when the two routers have the same bidirectional connectivity and all OSPF parameters match, however with Fully Adjacent Neighbours, each router will exchange their full link-state database with its neighbours and advertise the relationship in a link-state update packets.
Within OSPF there are 8 neighbour states that two neighbours can go through to become Fully Adjacent Neighbours. These states are:
|Down||This is the start state of neighbour communications. No Hello Messages have been exchanged|
|Attempt||This state is valid only for Non-Broadcast Multi-Access (NBMA) networks. It is when a hello packet has not been received from the neighbour and the local router is going to send a unicast hello packet to that neighbour within the specified hello interval period.|
|Init||The router has received a Hello Message from a neighbour, but has not received its own Router-ID from the neighbour. This means that Bidirectional communications have not been established yet.|
|2-Way||Bidirectional communication between the neighbours have been established, no Link State information has been exchanged. At this state an OSPF Neighbourship has been created|
|ExStart||This is where the neighbours start the process of becoming Fully Adjacent OSPF Neighbours and exchange Link State Databases|
|Exchange||At this state, Link State Database details has been sent to the adjacent neighbour. At this state, a router is capable to exchange all OSPF routing protocol packets.|
|Loading||At this state, the neighbour has exchanged its own LSDB, however has not fully requested/received LSA’s from its neighbour|
|Full||Both LSDB’s have been exchanged and are fully synchronized. Each neighbour will have the full OSPF Network Topology available now|
Designated Router & Backup Designated Router⌗
OSPF has the concept of Designated and Backup Designated Routers (DR and BDR) for Multi-Access Networks that use technologies such as Ethernet and Frame Relay, as on the LAN you can have more than two OSPF enabled router. By having DR and BDRs, it assists in scalable of an OSPF segment, in addition to reducing OSPF LSA flooring across the network. This is because the other routers (OSPF DROthers) on the LAN, only create a Full OSPF Adjacency with the DR and BDR rather than with other DRothers. The DR is the solely responsible for flooding the LAN with LSA updates during a topology change. The flooring by the DR is controlled, as stated above, by the AllSPFRouters and AllDRouters multicast addresses. DR will flood LSAs to the AllSPFRouters destination address to communicate with other routers on the LAN; and DROthers will communicate their LSAs to DR and BDR using the AllDRouters destination address.
As the name suggests the BDR role is to be the secondary router in case the DR was the fail or be un-contactable, it will take over as the DR and another BDR will be elected. The BDR has a full OSPF Adjacency just like the DROthers with the BR, however unlike them, the BDR can listen on the ALLDRouters address. This means, in a situation of a DR failure, the BDR can take over as DR quicker and there will be less re-convergence across the network, as it already synchronized to the DR and the DROthers as they will all have the same LSDB.
Designated Router Election Method⌗
The DR/BDR Election process is done during the 2-Way State, where bidirectional communications has been established between the routers and have received Hello Messages. OSPF uses Interface Priority and Router-ID to determine, which routers will be elected as DR and BDR. An OSPF router can have its interface priority set between 0-255, (an interface priority set to 0 means it is prohibited from entering DR/BDR election process) with the highest priority taking the role as the DR and the secondary highest priority becoming the BDR. If the priorities are all the same, the highest Router-ID will be used as the tiebreaker.
By default, OSPF’s priority is 1 on Cisco IOS/XR and 128 on Juniper. With Cisco IOS XR, you are able to set the priority for all interface within an area globally and under the interface, whereas Junos and Cisco IOS you can only set priority under the interface.
If an OSPF router receives a Hello Packet with the Router-ID for the DR or BDR isn’t 0.0.0.0, it will assume that DR and BDR have been elected already and will become a DROther.
Depending on what the Layer-2 topology looks like within a network can have affect on the behaviour of OSPF. A Topology that uses Ethernet commonly allow multiple node on a LAN, in this case a Designated Router (DR) and Backup Designated Router (BDR) are used to cut down the OSPF LSA flooding, due to both supporting broadcast domains. Whereas other media such as serial links or Frame Relay don’t support broadcast domains meaning DR/BDR are not needed.
With this in mind OSPF has 5 different network types:
A Broadcast network is where an OSPF router is able to send a single message (broadcast message) that is able to communicate to more than 2 other OSPF routers on the same multi-access segment. i.e. Router A, B and C are connected to a Switch when Router A sends out a Hello Message it will be broadcasted across the segment via the Switch. With in this in mind, the need for DR/BDR will be required to control the LSA flooding across the segment. By default OSPF uses broadcast as the network type when configured on Ethernet LAN. The hello timers by 10/40 by default.
Non-Broadcast Multi-Access (NBMA)⌗
This network type is used on links that do not support broadcast domain, media such as Frame Relay, ATM and X.25, or topologies like a hub and spoke where a router can connect to multiple nodes out of a single interface however isn’t fully meshed. A Non-Broadcast network will need to have DR/BDR configured, as you could have multiple nodes on the segment. However, Non-Broadcast network (as the name would suggest) doesn’t support broadcast or multicast, this means that OSPF’s normal way of sending hellos via the multicast address 220.127.116.11 to flood LAN looking for neighbours will not work. Instead it sends out unicast hello messages to statically configured neighbours. The hello timers are 30/120 by default.
This network type is commonly used when you only have two devices on the segment, ie if you have Router A connected to Router B using /31 or /30 that will be regarded as Point-to-Point (P2P) network. This network type doesn’t require DR/DBR as the two devices only have each other to communication and forming a DR/BDR would be a waste of Router resources. In addition, it important to note that P2P OSPF Adjacency form quicker as DR election is ignored and there is no wait timer. The hello timers by 10/40 by default and it supports OSPF Multicast Hello Messages.
This network is commonly used when in a partially mesh network or hub and spoken network, where the Layer-2 topology doesn’t logically match the Layer-3 topology. I.e. in a hub and spoke or frame-relay network, Router A will be connected to Routers B and C, all on the same subnet, the Layer-3 will assume Routers B and C will be able directly connected on the same LAN, whereas the Layer-2 determines that Router B can only communicate with Router C by going via Router A. By using Point-to-Multipoint, it will advertise all each neighbour as a /32 endpoint forcing the Layer-3 routing to matches the Layer-2 by using Longest prefix match. The hello timers are 30/120 by default, doesn’t require DR/DBR and it supports OSPF Multicast Hello Messages.
This network type is by default enabled on all loopback interfaces and can only be configured on loopback addresses. OSPF will always advertise loopback addresses as /32 route, even if the interface has been configured with a different prefix length. Hello messages, Timers and DR/BDR are not associated with Loopback network types.
The wider a network gets, the wider OSPF domain will become. This can be an issue as all of these routers will need to maintain the same LSDB, and with a larger network more resources will be used processing LSA flooding and running SPF algorithm, which in turn will make the router run inefficient and possible start dropping packets. A way of easing this issue is to introduce OSPF Areas. OSPF Areas are used reduce the amount of the routers in a single area, in turn shrinking the LSDB size, restricts LSA flooding within/between areas, allows route summarization between Areas and increases SPF calculations. This is because routers maintain their own LSDB on a per-area basis. Essentially, Areas hide the their own topology and any LSA flooding or SPF calculations will same local to that area whilst the rest of the network stays unaware. Routers within the same area will have the same synchronized LSDB with Routers with interfaces in multiples area will hold LSDBs.
Along with Area Types, OSPF has 4 different types of roles that an OSPF router could be, and dependent on the topology, multiple types at once. The table below describes the different Router types and you can see where each of these router types could sit within a simple topology here
|Backbone Router||A router that is located and/or has a link(s) within Area 0 is known as a Backbone router. If this router has links to non backbone routers, it can also be known as an Internal router.|
|Internal Router||An internal router is an OSPF router that only have links within a single area. If this router is within Area 0, it will also be known as Backbone Router.|
|Area Border Router (ABR)||An Area Border Router (ABR) is a router that has links between 2 areas. ABRs are role is to inject routes from non-backbone areas into Backbone. For a router to be an ABR, it HAS to have a link to Area 0, if it doesn’t then it wont be an ABR. It is considered a member of all areas it is connected to. An ABR keeps multiple copies of the link-state database in memory, one for each area to which that router is connected.|
|Autonomous System Boundary Router (ASBR)||An OSPF router that learns routes from external routing protocols (BGP, IS-IS, EIGRP, OSPF), Static Routes and/or both and injects them into OSPF via redistribution. ASBRs are special types of routers, as you have can ASBR that isn’t ABR as these ASBR functions are independent to ABR functions, but dependant on the topology, you could have router that is both an ASBR and ABR.|
OSPF Route Types⌗
OSPF has a unique relationship between how routes are exchanged between areas and how these routes are ranked in importance. There’s 3 types of the Routes that are exchanged within OSPF
External Routes, and in regards with the External Routes, you have 2 different types of External Routes:
Intra-Area Routes: these are routes that are learnt from Routers that are within the same area. They are also known as
Inter-Area Routes: these are routes that have been learnt from different areas. These routes have been injected via an ABR. They are also known as
External Routes: are routes that are learnt outside of the OSPF domain. These routes have been learnt via redistribution by an ASBR. External routes have 2 classifications
Type 1 Routes: Type 1 routes, metric value equals the Redistribution Metric + Total Path Metric. This means that the metric values will increase the further the route goes into the network from the injecting ASBR. Type 1 routes are also known as
E1 and N1 External Routes
Type 2 Routes: Type 2 routes, metric value is only the Redistribution Metric. This means that the metric value will stay the same, no matter the how far the route goes into the network (within in 30 hops) from the injecting ASBR. By default, type 2 is the metric type used by OSPF. Type 2 routes are also known as
E2 and N2 External Routes
The order of preference for these route types are as followed:
- External Type 1
- External Type 2
Link-State Advertisement Types⌗
Devices in an OSPF domain use LSAs to build their local areas LSDB. These LSDBs are identical for devices in the same area and different areas and different router types can produce different type of LSAs. There is 11 types of LSAs however typically there are 6 LSAs that are commonly used and that should be known. These are:
Type 1 - Router⌗
Every OSPF Router will advertise Type 1 Router LSA, these LSAs are used to essentially build the LSDB. Type 1 LSAs are entries that describe the interfaces and neighbours of each and every OSPF router within the same area. In addition, these LSAs ARE NOT forward outside its own area, making the intra-area topology invisible to other areas.
Type 2 - Network⌗
A Type 2 Network LSA, are used over Broadcast OSFP domain with a DR. Network LSAs are always advertised by the DR and is used to identify all the routers (BDR and DRothers) across the multi-access segment. As with Type 1 LSAs, Network LSAs ARE NOT advertised outside of its own area, making the intra-area topology invisible to other areas.
Type 3 - Summary⌗
Summary LSAs are the prefixes that are learnt from Type 1 and 2 LSAs and advertised by an ABR into other areas. ABRs DO NOT forward Type 1 and 2 LSAs to other areas, any Network and/or Router LSAs are received by an ABR, it will be converted into Type 3 LSA with Type 1 and 2 information referenced within. If an ABR receives a Type 3 LSA from a Backbone router, it will regenerate a new Type 3 LSA and list itself as the advertising router and forward the new Summary LSA to non-backbone area. This is how inter-area traffic is process via ABR.
Type 5 - External⌗
An External Type 5 LSA are flooded throughout an OSPF domain when route(s) from another routing protocol is Redistributed via an ASBR. These LSAs are not associated to any area and are flooded unchanged to all areas, with the expectation to
Stub and Not-So-Stubby Areas.
Type 4 - Autonomous System Boundary Router (ASBR) Summary⌗
When a Type 5 LSAs is flooded to all areas, the next-hop information may not be available to other areas because the route(s) would have been redistributed from another routing protocol. To solve this ABR will flood the Router ID of the originating ASBR in a Type 4 ASBR Summary LSA. The link-state ID is the router ID of the described ASBR for type 4 LSAs. Essentially, any routes that are redistributed into OSPF, when, the first ABR receives the Type 5 LSA, it will generate and flood a Type 4 LSA.
Type 7 - Not So Stubby Area (NSSA) External⌗
Routers in a Not-so-stubby-area (NSSA) do not receive external LSAs from Area Border Routers, but are allowed to send external redistributed routes to other areas. As ABR DO NOT advertise Type 7 LSAs outside of their local. The ABR will covert the Type 7 LSA into a Type 5 LSA and flood the Type 5 LSA across the OSPF domain, as normal.
In addition to the LSA types above, the other 6 LSA types that are within OSPF are:
- Type 6 - Multicast Extension LSA
- Type 8 - OSPFv2 External Attributes LSA, OSPFv3 Link-Local Only LSA
- Type 9 - OSPFv2 Opaque LSA, OSPFv3 Intra-Area Prefix LSA
- Type 10 - Opaque LSA
- Type 11 - Autonomous System Opaque LSA
Types 9 - 11 are defined in RFC5250 and RFC2370. They are typically used as MPLS Traffic Engineering OSPF Extension. I personally, haven’t looked into as of yet however will update once I have done more reading into them.
OSPF defines several special area types:
As described earlier, the Backbone Area also know as Area 0, this is the most important area in OSPF and there always has to be a Backbone Area. The Backbone Area
MUST connect to all areas, as non-backbone area have to use Area 0 as transit area to communicate to other non-backbone areas. This is because the Backbone has all the routing information inject into it and advertises them out. This design is important to prevent routing loops.
A Stub Area
DOES NOT allow
External Routes to be advertised within the area. This means when an ABR to a Stub Area receives a Type 5 (External) and Type 4 (ASBR Summary) LSAs, the ABR will generate a default route for the area as Type 3 Summary LSA.
Not So Stubby Area (NSSA)⌗
A Not So Stubby Area are similar to Stub Areas as they
DO NOT allow Type 5 External however unlike Stub Areas, Not So Stubby Areas
DO redistributed external routes via an ASBR into the area. As described above when route is redistributed into the NSSA, a Type 7 NSSA External LSA is flooded throughout the area and once an ABR receives the Type 7 LSA, it is converted into a Type 5 LSA and flooded into other areas. It is important to add, by default the NSSA does not advertise a default route automatically when Type 5 or Type 7 LSAs are blocked by an ABR.
Totally Stubby Area (TSA)⌗
A Totally Stubby Area
DOES NOT allow any
Inter-Area or External Routes to advertised with the area. Essentially, if a Type 3 Summary or Type 5 External LSA, by the ABR, it will generate default route and inject it to the area. Totally Stubby Areas only allow
Intra-Area and Default Routes within the area. The only way for traffic to get routed outside of the area is a default route, which is the only Type-3 LSA, advertised into the area.
Totally Not So Stubby Area (TNSSA)⌗
Totally Not So Stubby Areas
DOES NOT permit Type 3 Summary, Type 4 ASBR and Type 5 External LSAs being received into the area. However just like a NSSA, it allows redistributed external routes into the area via an ASBR. Just like NSSA when route is redistributed into the NSSA, a Type 7 NSSA External LSA is flooded throughout the area and once an ABR receives the Type 7 LSA, it is converted into a Type 5 LSA and flooded into other areas, but unlike a NSSA when TNSSA ABR receives a Type 3 LSA from the backbone, it will automatically generate a default route and inject into the area.