The OSPF Routing Protocol

1.- OSPF overview

1.1- Common terms

Before going further in the presentation of OSPF protocol, we need to define few commonly used terms :

Neighbouring routers : Two routers that have interfaces to a common network.

• Autonomous System (AS) : Group of routers exchanging routing information via a common protocol. It usually corresponds to the company branch internal network.

• Router ID : A 32-bit integer assigned to each router running OSPF and identifying it uniquely in the Autonomous System. This could be the smallest router’s interface’s IP for example.

• Multi-access networks : Physical network attached to more than two routers. On these network each pair of router is assumed to be able to communicate directly.

• Interface : Connection between a router and one of its attached network.

• Neighbouring routers : Two routers that have interfaces to a common network.
  

• Adjacency : Relationship between two neighbouring routers exchanging routing information.

  Neighbouring routers : Two routers that have interfaces to a common network.
  

• Link State Advertisement : Description of the local state of a router or network, which includes interfaces and adjacencies. The reunion of all routers and networks link state advertisements forms the protocol’s topological database.

• Designated router : On a multi-access network, router in charge of among other things generating the network link state advertisements.

• Point-to-point network : Network that joins a single pair of routers.

• Broadcast network : Multi-access network that supports the emission of broadcast messages.

• Non-broadcast network : Multi-access network denying the use of broadcasts.

1.2.- Defining areas

OSPF protocol allows the definition of areas to group networks and/or hosts. Each area thus defined will run a separate copy of the routing protocol. It means that the local topological database will not be propagated to other areas. Then is defined the notion of backbone. It consists of all the network and routers not fully included in an area. Actually it is the network binding all the area together and its own topology is also invisible to each of the area.
Therefore a few new terms needs to be defined : 

• Intra-area routing : Routing inside an area

• Inter-area routing : Routing between areas

• Internal routers : Routers fully included in an area.

• Area border routers : Routers having interfaces in several areas. A separate copy of the protocol is run for each area plus one for the backbone.

• Backbone routers : Any router having an interface to the backbone (it may be an area border router).

• AS boundary routers : Routers exchanging information with other autonomous systems. Route to these routers are known by every router in the AS.

1.3.- Managing IP Type Of Services

OSPF is able to compute routes according to the IP TOS field. Different path costs can be configured depending on TOS value. Then the route to a single destination can vary depending on the type of service carried. A cost for TOS 0 must always be specified. In case no proper route can be found for a particular TOS, the TOS 0 route would be used.

1.4.- Learning external routes

From an other area in the AS

Each area border summarizes the topological information of its attached networks and then provides backbone routers (and then other area border routers) with this information. Meanwhile it receives the summaries from other areas. It can then compute paths to all destinations out of its attached areas and finally advertise them in its attached areas As a result internal routers can choose the best route (and then the best area border router) when forwarding traffic to other areas.

From other autonomous system

Each router receiving information regarding other AS can flood them throughout the AS. Every participating routers should know the route to AS boundary routers. So they can calculate routes to destinations out of the AS. In fact OSPF support two types of external metrics : 

• Type 1 metrics : are equivalent to link state metrics. The new path cost would be computed by adding the external path cost advertised and the path cost to the AS boundary router.

• Type 2 metrics : are greater than any path cost internal to the AS. That means the cost of the route to the AS boundary router is negligible when computing path costs to devices external to the AS

2.- OSPF functioning

2.1.- Building adjacencies

OSPF uses adjacency to determine which routers are involved in routing packets within the area. Protocol information (link state advertisement) will only be exchanged between those routers. Afterwards topological database will be synchronized between any router pairs forming an adjacency. Adjacencies are built up through the use of the Hello Protocol. When a router comes up it sends Hello packet to all his neighbouring routers. On a broadcast network, it may use the multicast address AllSPFRouters (224.0.0.5). On non-broadcast networks it first needs to know the list of routers in the area. On multi access networks the Hello protocol is also used to determine the Designated and the Backup Designated Router. Thus routers discover their neighbours. They can also list the routers with whom a two-way communication was established by examining received Hello packets (their own IP address will appear in the remote router’s neighbours list). Those routers are promoted to the level of 2-Way routers. Then the router can decide if an adjacency if should be built with each 2-Way routers, that is when :

• the underlying network type is point to point

• the underlying network is virtual link

• the router itself is the designated router

• the router itself is the backup designated router
  

• the neighbouring router is the designated router
  

• the neighbouring router is the backup designated router
  

fig 1 - The standard OSPF header

Version : Version number of OSPF protocol. Currently version 2. 1-byte
Type : Type of the OSPF packet. 1-byte

Table1 - Type of OSPF Packet

Packet length : Length of the total OSPF packet — 2 bytes.
Router ID : Identifying of the source router — 4 bytes.
Area ID : Identifying the area the packet belongs to — 4 bytes.
Checksum : The standard IP checksum of the entire contents of the packet, excluding the 64-bit authentication field. This checksum is calculated as the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming – 2 bytes.
Autype : Type of authentication. — 2 bytes. 

Table2 - Type of OSPF Authentication

Authentication : 8 bytes

fig 2 - The Hello packet

HelloInt : number of seconds before reemitting a hello packet.
Rtr Pri : Router’s priority used when electing designated router.
Deadint : The number of seconds before declaring a silent router down.
Designated router : Designated router from the advisor point of view.
Backup Designated Router : Backup designated router from the advisor point of view.
Neighbour : List of router IDs from whom the router has received Hello packet in the last Deadint seconds.
Options : Optional capabilities of the router. 

fig 3 - The Option field

• T-bit :This describes the router's TOS capability. If the T-bit is reset, then the router supports only a single TOS (TOS 0). Such a router is also said to be incapable of TOS-routing. The absence of the T-bit in a router links advertisement causes the router to be skipped when building a non-zero TOS shortest-path tree. In other words, routers incapable of TOS routing will be avoided as much as possible when forwarding data traffic requesting a non-zero TOS. The absence of the T-bit in a summary link advertisement or an AS external link advertisement indicates that the advertisement is describing a TOS 0 route only.

• E-bit : AS external link advertisements are not flooded into/through OSPF stub areas. The E-bit ensures that all members of a stub area agree on that area's configuration. The E-bit is meaningful only in OSPF Hello packets. When the E-bit is reset in the Hello packet sent out a particular interface, it means that the router will neither send nor receive AS external link state advertisements on that interface (in other words, the interface connects to a stub area). Two routers will not become neighbours unless they agree on the state of the E-bit.

The designated routers

The designated and backup designated routers are supposed to be those routers having the highest priority. In case of a tie the highest Router_ID is chosen (See 1.1). However if a designated router has already been elected when a new router with a higher priority is connected to the network, then this new router does not become the new designated router. Initially the corresponding fields are set to 0.0.0.0 to signify that no designated router have been chosen yet. The designated router is in charge of advertising the list of all routers currently attached to the network. As adjacent to all other routers in the network it is the centre of the synchronization process. The backup designated router is provided to reduce transition time, and then loss of network connectivity, if the designated router happens to fail. This router obviates the need to compute adjacencies again. Yet it does not generate network link advertisement to reduce database size. 

2.2.- Exchanging database

As soon as an adjacency is about to be brought up, the two routers making this adjacency begins trying to synchronize their database. During the exchange the router experience several states
Neighbour states : 

• Down : Initial state of a neighbour. It indicates no recent information were received from this destination.
  

• Attempt : Only valid on non-broadcast network. It indicates no recent information were received from this destination but that special efforts should be made trying to contact it.
  

• Init : Hello packets have recently been seen from this source, but bi-directional communication has not been established yet.
  

• 2-Way : Router with whom a bi-directional communication has been established.
  

• ExStart : First step of the adjacency. This state allows adjacent routers to determine a master and a slave for this adjacency.
  

• Exchange : The router is providing its entire link state database. Information exchanged at this step may already be flooded through the network
  

• Loading : The router is requesting for more recent advertisements that have been discovered.
  

• Full : The neighbouring routers are fully adjacent.
  

fig 4 - Database description paket 

0 fields : reserved. Must be kept to 0
I-bit : Init bit. When set to 1, it indicates this packet is the first in the sequence of database descriptions.
M-bit : More Bit. When set to 1 it, it indicates that more database descriptions follow.
MS-bit : The Master/Slave bit. When set to 1, it indicates the router is the master. When set to 0, it indicates the router is the slave.
DD : Sequence number. Identify uniquely each database description packets during the complete database description.
Rest of the packet : Made of link state advertisements in the topological database. This information allows the receiving router to ask later for specified link state advertisements. This list may be incomplete. Database description packets are accepted only up from the ExStart level.

ExStart level

At the ExStart level, the Options field from the neighbouring router is recorded and the packet treated if : 

• I, M and MS bits are set, the packet are empty and the Router ID is greater than the receiving router’s own. The receiving router is then the slave, and the sequence number set to the one specified by the master.

• I and MS bits are off and the packet’s sequence number equals the router’s own sequence number (this indicates an acknowledgement) and the router ID is smaller than the receiving router’s own. In that case the router is the master.

Exchange level

The MS bit must remain consistent during the exchange. Otherwise a Seq Number Mismatch is generated. Assuming this condition is satisfied : 

• if I bit is set, a Seq Number Mismatch will be generated and the packet processing stopped
  

• if the packet’s option field is different from the previously recorded option field, a Seq Number Mismatch will be generated are the packet processing stopped
  

• if the router is the master and the sequence number received equals the router’s own, the sequence number is increased
  

• if the router is the slave and the packet’s sequence number is one more than the router’s own, the sequence number is updated and a database description packet is sent.
  

• if the router is the master and the sequence number is one less than the router’s own, the packet is a duplicate and is discardedif the router is the slave and the packet sequence number is equal to the router’s own, the packet is a duplicate. The slave must repeat its last database description packet.
  

• else a Seq Mismatch Number is sent and the processing of the packet is stopped.
  

Master packets, which are not acknowledged, are repeated.

Loading or full state

The entire database has been sent and received and the only packets accepted are repeated packets. Routers may notice part of their database is no more up to date and may request for more recent information through the use of link state request packet.

Link state advertisement header

All link state advertisement begins with a common 20 bytes header. 

fig 5 - Link State Advertisement Header

LS age : Time in seconds since the link advertisement was generated
Options: Optional capabilities supported by the described portion of the routing domain
LS type : Type of the link state advertisement 

Table 3 - Type of link state advertisement

Link State ID : Identifies the portion of the network described by the link advertisement.
Advertising router : The router ID of the router, which has generated the link advertisement.
LS sequence number : Identifies this particular advertisement in a sequence.
LS checksum : The Fletcher checksum of the complete link advertisement.
Length : Total length in bytes of the link advertisement.

The link state request packet

This is the OSPF type 3 packet. It is accepted only by routers in Exchange, Loading or Full state. 

fig 6 - Link State request packet

LS type, link State ID and Advertising router uniquely define the advertisement but not its instance. Therefore this request is always understood as a request for the most recent instance available.

The link state update packet

These are OSPF type 4 packets. They implement the flooding of Link State advertisements. Each of these packets carries the update one hop further.
They are multicasted when possible and always acknowledge. In case a retransmission is necessary it is always done in unicast. 

fig 7 - Link State Update packet

#advertisements : Number of link state advertisements included in this update

Link state acknowledgment packet

These are type 5 OSPF packets provided to make link advertisements reliable. Their format is similar to data description packet. 

fig 8 - Link State Acknowledgement packet

Router links advertisements

These are type 1 link state advertisements. 

fig 10 - Router Link State Advertisement

bit E : When set the router is an AS boundary router.
bit B : When set the router is a area border router.
#links : The number of links describe in this advertisement. This must be the total collection of router links to the area.
Type : Defines the type of the router link. Host route are considered as route to a stub network with a 0xFFFFFFFF mask. 

Table 4 - Type of OSPF link

Link ID : Identifies the object the router is connected to. Its value depend on the type of link

Table 5 - Type of OSPF link ID

Link Data : Content depends on the link type. For stub network, it is the network mask. For other link it is the IP address of the router’s interface.
#metrics : The number of TOS metrics given for this link, not counting the required metrics for TOS 0.
TOS : IP type of service the metric refers to (D=delay, T=throughput, R=reliability). They must be sorted by increasing number order.

Table 6 - Representing TOS in OSPF

metric : The cost of using this outbound router link for the specified TOS.

Network links advertisements

These are type 2 link state advertisements. They are originated by the designated router for all transit network in the area and gives the list of all routers attached to the network. 

fig 10 - Network Link State Advertisement

The link State ID corresponds here to the network’s designated router’s IP address.
Network mask : The IP address mask for the network.
Attached router : Router ID of all routers in the area and which are adjacent to the designated router, plus the designated router itself.

Summary link advertisements

These are type 3 and type 4 link state advertisements. They are originated by area border routers. There is one link state per destination known to the router in the AS but outside the area. Type 3 are used for networks, whereas type 4 are used for AS boundary routers. 

fig 11 - Summary Link State Advertisement

Link State ID : Either the IP network address or the AS boundary router’s Router ID.
Network mask : IP network mask for type 3 link state. Must be set to 0 for type 4.
TOS : Type of service concerned by the following metrics.
metrics : Cost of this route.

AS external link advertisements

These type 5 link state advertisement are generated by AS boundary routers. A separate advertisement is made for each destination known of the router outside the AS. 

fig 12 - AS external Link State Advertisement

Link state ID : Here the IP address of the network advertised.
Network mask : IP network mask.
TOS : Type of service concerned by the following information.
bit E : Type of external metric used (see 2.1.4).
metric : Cost of the route for the specified TOS.
Forwarding address : Data traffic for the advertised destination will be forwarded to the specified IP address. If it is set to 0.0.0.0, data traffic will be
forwarded to the responsible AS boundary router.
External route flag : A 32-bit field attached to each external routes. It is not used by OSPF protocol itself. But may be used by AS boundary routers to communicate information. It is not defined by the OSPF specification. 

2.3.- Routing packets

Computing routing tables

The process can be divided in several step.
The present routing table is invalidated. It is saved for comparison and a new table is built from scratch. This happens each time an upgrade in the topological database occurs.
The intra-area routes are calculates through the shortest path tree algorithm. First only links between routers and transit network are considered. Stub networks are only incorporated at the end as leafs of the tree.
The inter-area routes are calculated for all the area on which the router has no interface connected. This is done by examining summery link advertisements and using the shortest path tree algorithm.
For each entry whose next hop is a virtual link, a physical next hop is computed.
Routes to external destination are calculated through the examination of AS external link advertisements.
These five steps will be executed for each IP type of service supported. Then inter-area summary links advertisements may be generated.
The shortest path tree is calculated with the router itself as root and the Dijkstra algorithm.

fig 13 - Shortest Path Tree algorithmThe routing table

The routing table includes :

• Destination type : Either Network, Area border router or AS boundary router. In fact only the network type is used when forwarding packets. Other types are used to compute the routing table 

• Destination ID : The destination identifier name. For network it is the associated IP address. For other destination type it is the corresponding Router ID.
  

• Address mask : Only defined for network.
  

• Optional capabilities : When the destination is a router this field gives the destination router capabilities.
  

• Type of service : Each type of service may be associated to a dedicated route.
  

• Area : Table entry associated area. This field is empty for AS external path.
  

• Path type : Either intra-area, inter-area, type 1 external or type 2 external.
  

• Cost : cost to the destination. This is the total path cost for all non-type 2 external paths. For type 2 external paths, it represents the internal portion of the cost.
  

• Type 2 cost : Only valid for type 2 external paths. It represents the external type 2 path cost.
  

• Link state origin : Valid only for intra-area path. It indicates the link state advertisement that directly reference the destination.
  

• Next hop : interface to use when forwarding packets to the destination.
  

• Advertising router : Valid only for inter-area routing. It indicates the source of the summary or AS external link advertisements for this destination.
  

Routing table lookup

When an IP packet is to be routed, the most specific match in the routing table is used. Therefore the matches are pruned using the following criteria (in this order) : 

1. the most suitable path type (e.g. if the destination may belong either to the local area or to an other, intra area path type is preferred).
   

2. the most restrictive address mask
   

3. possibly filter on the IP type of service
   

If multiple paths remain, they are used indifferently.