The OSPF (Open Shortest Path First) is a link-state routing algorithm used in the network layer for intra-(autonomous system) routing. OSPF uses the Internet Protocol directly. Each router will flood OSPF link-state advertisements to all routers in the AS. There are multiple link cost metrics possible (bandwidth, delay). Each router has information of the full network topology, and thus it uses Dijkstra’s algorithm under the hood.
OSPF also has a few modern features:
- Security — all OSPF messages are authenticated (to prevent malicious intrusion).
- Multiple paths are allowed for load balancing.
- For each link, there may be multiple costs assigned to it simultaneously in the routing tables for a different type-of-service (different costs for different traffic).
- For example, a satellite link cost could be set “low” for a best-effort link, and high for a real-time link.
- i.e., this is based on a field in the IP header that indicates what kind of traffic is being sent.
- There is integrated unicast and multicast support.
- Hierarchical OSPF in large domains.
- Scalable by breaking a large network into areas.
- Allows virtual networks that abstract the details of physical connections.
- Allows routers to exchange routing information learned from other sites.
There is a two-level hierarchy consisting of a local area and a backbone. Link-state advertisements are flooded only within an area or within a backbone. This basically limits the scope of how much topological information that flows among the routers.
Each node will have a detailed knowledge of the topology within its area or within its backbone. It only knows the direction to reach other destinations.
Message specification
OSPF messages are formatted as follows. Some key things to remember:
- As mentioned before, OSPF runs directly on IP with protocol number 89.
- The common header is 24-bytes long.
- The source router IP address is the address of the router sending the message.
Additionally, the types can take a few different values:
- Hello (used to test reachability)
- Database description (network topology)
- Link status request
- Link status update
- Link status acknowledgement
Hello message
It’s worth taking a look at the hello message in a bit more depth. Hello messages are generated periodically and sent to all neighbour nodes. If it isn’t received within an interval, the link is declared broken (much like a Keep-Alive message in ZooKeeper). This is only during normal operations, i.e., after adjacent routers have been connected.
To connect, hello messages function as a greeting to allow routers to discover other adjacent routers on local links and networks. These establish relationships between neighbouring devices, and also communicate some key parameters about how OSPF is to be used in the autonomous system or area.
The message packet is as follows. This comes after the common header with type = 1.
Database description
This conveys a description of the topology of the autonomous system in a link-state database (or LSDB). OSPF will build a graph of routers and networks. Hidden networks have to be explicitly advertised by the router.
Link state advertisements
The last 3 types (link state {request, update, ack}) relate to how OSPF handles link-state advertisements (LSA).
- LSR messages are used to request updated information about a portion of the LSDB from another router. The message will specify all the links for which a requesting device wants more current information.
- LSU messages contain the updated information requested by an LSR message. They’re also broadcast by routers on a regular basis.
- LSA messages add reliability to the link-state exchange process by explicitly acknowledging the receipt of a LSU message.
A few kind of important links:
Of course, there are a few types of LSAs:
- Router links are between point-to-point, transient, stub, or virtual links. A router will use this LSA to announce the cost of all its links in an area.
- Network links are sent by a designated router that contains the list of routers connected to the network.
- Summary links describe either:
- Routes to networks. It is sent by area border routers to inform routers of networks outside their area in autonomous systems.
- Or routes to AS border router. This is used to give the cost to the AS border router.
- External links are used to inform routers of outside networks of the self AS.
