What is the Open Shortest Path First (OSPF) routing protocol?OSPF is a complex routing protocol:
- OSPF is an intra-domain routing protocol
- OSPF must run over IP, because it uses IP multicast addresses 126.96.36.199 or FF02::5 and 188.8.131.52 or FF02::6 to send messages to other routers. As OSPF depends on the multicast addresses, two different versions of OSPF must be used for IPv4 (OSPFv2) and IPv6 networks (OSPFv3). OSPF does not use a TCP/IP transport protocol (UDP, TCP), but is encapsulated directly in IP datagrams with protocol number 89.
How does the Open Shortest Path First (OSPF) work?
- OSPF is a link-state protocol.
- If you do not know what being a link-state routing protocol means, have a look at my post on the 3 routing protocol categories.
- Link state protocols rely on Dijkstra's algorithm: I have written a post that explains Dijkstra's algorithm on an example and another post to show you how to implement it in Python.
- Being a link state protocol, OSPF associates costs to links and prefers the path with the lowest cost (sum of the costs of its links). As it does not make sense to add apples to oranges, OSPF supports 4 main types of cost metrics:
- Intra-area cost
- Inter-area cost
- External Type 1: the sum of and external path cost to the destination prefix and the internal path costs to the AS border router that advertises the route,
- External Type 2: the external path cost to the destination prefix
- When an OSPF learns about a topology change (e.g., an interface goes down, a neighbor stops sending keepalive messages, or the router receives an update from another router), it spreads the news to its neighbors.
- To avoid that too many routers recalculate their routing tables at the same time (calculation overhead), OSPF divides networks into areas. The backbone area is area number 0 and interconnects all areas.
- To avoid that too many routers spread the routing update, Designated Routers (DR) and Backup Designated Routers (BDR) are used in networks supporting broadcast messages.
- When DR and BDR are used, OSPF routers form adjacencies with the DR and BDR only. So, the DR and BDR must be connected to all OSPF routers. Every time a router sends an update, it sends it to the DR and BDR on the multicast address 184.108.40.206. The DR will then send the update out to all other routers in the area, to the multicast address 220.127.116.11. This way all the routers do not have to constantly update each other, and can rather get all their updates from a single source.
What message types does the Open Shortest Path First (OSPF) support?
- OSPF uses two multicast addresses to ease the communication to other OSPF routers:
- 18.104.22.168 or FF02::5 to send messages to all OSPF routers (e.g., hello)
- 22.214.171.124 or FF02::6 to send messages to Designated Routers and Backup Designated Routers only (e.g., Link State Advertisements)
- OSPF uses a few message types:
- hello (keep alive messages) - to 126.96.36.199 or to the router unicast address if the layer 2 does not support broadcast. They describe the router parameters for the interface linking it to the other router: area identifier, network mask, interval between two consecutive hello message, security parameters. It's a way for two neighbor router to see if they agree to exchange routes: in OSPF it is called establishing a forwarding adjacency.
- Database Description - These messages contain descriptions of the topology of the AS or area (the link state database (LSDB)). It lists the routes without all their attributes: if the destination router does not have some routes, it will request more information with the Link State request message.
- Link State Request: These messages are used by one router to request updated information about a portion of the LSDB from another router. The message specifies exactly which link(s) about which the requesting device wants more current information.
- Link State Update: They are the responses to a Link State Request message, and also broadcasted or multicasted by routers on a regular basis. Their contents are used to update the information in the LSDBs of routers that receive them.
- Link State Acknowledgments: These messages provide the required reliability to the link-state exchange process as OSPF does not run on TCP. These messages explicitly acknowledge the reception of a Link State Update message.
What types of roles do router play with Open Shortest Path First (OSPF)?
- There are 4 types of OSPF routers, as depicted in the picture below (from Cisco's website):
- Area border router (ABR) - connects several areas
- Autonomous system boundary router (ASBR) - connects several ASes
- Internal router (IR) - all interfaces are in the same area
- Backbone router (BR) - some interfaces are in the area 0
- Type 1 - Router LSA - the router announces its presence and lists the links to other routers or networks in the same area, together with the metrics to them. Type 1 LSAs are flooded across their own area only.
- Type 2 - Network LSA - the designated router (DR) on a broadcast segment (e.g. Ethernet) lists which routers are joined together by the segment. Type 2 LSAs are flooded across their own area only.
- Type 3 - Summary LSA - an Area Border Router (ABR) takes information it has learned on one of its attached areas and summarizes it before sending it out on other areas it is connected to.
- Type 4 - ASBR-Summary LSA - an Area Border Router floods the route information for an Autonomous System Boundary Router
- Type 5 - External LSA - these LSAs contain information imported into OSPF from other routing processes. They are flooded to all areas unchanged (except stub and NSSA areas). For "External Metric Type 1" LSAs routing decisions are made using the Type 1 metric cost sent, as the total cost to get to the external destination and includes the cost to the ASBR; while for "External Type 2" LSAs the metric sent is the cost from the ASBR to the External destination network and must be added to the OSPF cost to the ASBR advertising the Type 5.
Where can I learn more about OSPF and routing protocols?
Any question or comment? Feel free to comment this post!
An MPLS network (Credit: Wikipedia)