Lesson 39 - OSPF Fundamentals Part2 - Hello Packets

Following the previous post, let's continue to look at OSPF basic operation. In this lesson we will focus our attention on the exchange of OSPF Hello packets in order to reach the state allowing LSA exchange.

If these two posts (38 and 39) are a bit too much for you, try to read them again and next week look at my youtube channel. I should have some video published there showing you these things again but this time in on the command line interface.

Before OSPF routers distribute the routing information among their neighbors, they will go through certain stages of operation as explained in Lesson 38. OSPF packets are utilized to take a router from the DOWN state all the way up to the FULL state of operation. We must then, take a closer look at OSPF packets, especially at the Hello packet without which this magic would not be possible.

OSPF uses five types of packets to communicate (explanation of OSPF packet type can be found in my previous post). They are encapsulated in the OSPF header. The whole packet looks like shown in pic. 1.

Pic. 1 - OSPF Packet Encapsulation.

Icons designed by: Andrzej Szoblik - http://www.newo.pl

OSPF header contains the following pieces of information:

Pic. 2 - OSPF Header.

Icons designed by: Andrzej Szoblik - http://www.newo.pl

Version - The OSPF version, currently used version is 2. Version 3 is OSPF for IPv6.

Type - The type of OSPF packet (type 1 through type 5).

• Type 1 - Hello
• Type 2 - Database Description
• Type 3 - Link State Request
• Type 4 - Link State Update
• Type 5 - Links State Acknowledgement

Packet Length - The length of the protocol in bytes including the standard OSPF header.

Router ID - The router identifier in OSPF .

Area ID - The 32 bit number representing the area in which the interface operates.

Checksum - The number used to check the integrity of the packet including the header (excluding authentication).

AuType - The type of OSPF packet authentication.

• 0 - no authentication
• 1 - simple password (clear text) authentication
• 2 - MD5 authentication

Authentication - The 64 bit field used for authentication

Hello Packet

In order for OSPF routers to exchange their routing databases, they must first discover themselves using so called Hello protocol and agree on a number of parameters. Hello packet (OSPF Type 1 packet) is used to discover the neighbors and exchange these initial parameters.

The purpose of Hello protocol can be summarized as follows:

• Hello packets are used to discover OSPF neighbors.
• Hello packets advertise certain parameters (some of the must match in order to become the router's neighbor).
• On Broadcast or NBMA networks Hello packets are used to elect DR/BDR roles.
• Hello packets are used as a keepalive mechanism. If the router does not hear the neighbors' Hello packets in a given time (DeadInterval), it considers it down and invalidates information obtained from it.
• Hello packets ensure bidirectional communication. The router must see its own RouterID in the 'neighbor' field of the Hello packet it receives.

Before I explain what must match in the Hello packets for the routers to reach so called 2-way state, let's take a look at the Hello packet structure.

Pic. 3 - OSPF Hello Packet.

Icons designed by: Andrzej Szoblik - http://www.newo.pl

Network Mask - The network mask of the originating interface.

Hello Interval - How often Hello packets are going to be sent.

Options - OSPF options. One of them is a 1 bit flag called: E-bit which denotes the type of area in which the interface operates (1=normal, 0=stub).

Router Priority - Used on Broadcast and NBMA networks to elect DR/BDR. The higher the number, the more likely for the router to become DR and the second highest number becomes BDR. After the election has been accomplished, the number is no longer used to influence DR/BDR role (non-preemptive).

Router Dead Interval - The maximum time before a silent router is declared down (no Hello packet from it in this time).

Designated Router - DR is elected in Broadcast and NBMA network. This field in the Hello packet carries the IP address of the DR on the common subnet (only Broadcast and NBMA networks).

Backup Designated Router - BDR is elected in Broadcast and NBMA network. This is the IP address of DR on the common subnet (only Broadcast and NBMA networks).

Neighbor - The router IDs from which valid Hello packet was received in the last DeadInterval time.

2-way State
OSPF-enabled router is a bit picky when it comes to its operation and choosing its neighbors. In order for the OSPF routers to exchange LSAs (information about network reachability), they must reach the 2-way state first which indicates that some mandatory parameters in their Hello packets are identical between them. The OSPF header encapsulates the Hello packet. Below picture shows this encapsulation and the light-red dots indicate the parameters that must match between the neighbors.

Pic. 4 - Hello Packet Encapsulation.

Icons designed by: Andrzej Szoblik - http://www.newo.pl

So, in a nutshell, the following conditions must be met for the two routers to become neighbors:

1. The routers must be on common subnet (it's true for all IGP routing protocols).
2. The Hello and DeadInterval timers must be identical between the neighbor candidates.
3. The area ID, where the OSPF-enabled interfaces of both neighbors operate, must be identical.
4. The type of area where the two neighbors must be identical (either normal or stub area).
5. The type and authentication password (if used) must match between neighbors.

Only if the routers agree on the parameters mentioned above (exact match) and their router IDs are listed in the neighbor's Hello packet '(neighbor' field in the Hello packet) can they reach the2-way state and proceed to ExStart, Exchange, Loading and finally Full state. I will show you the process of going through all phases in the next post using 'debug ip ospf adj' command.

After achieving bidirectional communication between the routers (2-way), they will enter the ExStartstate. During this phase the routers are going to elect the Master and Slave roles to perform the database synchronization in an orderly fashion. During the ExStart state they will also check their MTU size. If it does not match, they will not go any further (no LSA exchange is possible). This is generally not a problem between routers, but if you create configuration between a multilayer switch and a router, this might be a problem if the switch uses larger MTU size than 1500 bytes.

Routers typically use MTU=1500 bytes. On a multilayer switch running OSPF you can check it by issuing the following command:

Switch#show system mtu

If MTU is not 1500 bytes, you can disable MTU check on the interfaces in question:

Router(config-if)#ip ospf mtu-ignore

If all is good, they will eventually reach the Full state.

Before I finish this post I must mention that there are two multicast IP addresses reserved for OSPF communication:
224.0.0.5 = All OSPF speaking routers
224.0.0.6 = AllDRouters (DR/BDR listen on this address).

Unfortunately, sometimes these multicast addresses cannot be used on certain types of media (X.25, Frame-Relay, ATM, which are NBMA types of networks). In such situations, by default, unicast transmission must be used to send OSPF packets (the 'neighbor' statement under OSPF process changes mutlicast into unicast transmissions)

Wrapping things up, I need to add that some states require a bit more explanation (for instance, DR/BDR election on Broadcast/NBMA networks), but it will be easier to show it practically in my next post which is going to be about implementation of OSPF on two types of network: Broadcast and Point-to-Point. Running OSPF on these types of network fall under CCNA level of expertise.

Lesson 38 - OSPF Fundamentals Part1 - Terminology

Open Shortest Path First is the dynamic routing protocol based a link-state algorithm. In the upcoming few posts I will attempt to explain the basics of OSPF operation. Cisco CCNA level of expertise assumes that the candidates know how to implement it in a single area. In my OSPF related posts I will go a bit beyond CCNA requirements but not too much, just enough to help you appreciate this fascinating solution and put OSPF into practice.

Link-state algorithm is faster and more accurate in selecting the best path compared to distance vector approach. The latter algorithm allows routers to know how far the destinations are (distance) and the next-hop router(s) the packets should be sent to (vector). Thus, the routers do not know the topology of the network.

Routers using link-state algorithm create "a map" of the network which allows them to choose paths more accurately. Even though they are more demanding hardware-wise (CPU and RAM memory) they supersede distance vector based solutions.

OSPF Basic Operation

OSPF is a very complex routing protocol but its fundamental operation is quite simple. The steps of operation might be pictured as follows:

1. Each router sends so called hello packets out of all OSPF-enabled interfaces. This way, the OSPF-enabled router discovers directly connected routers which also run OSPF. If certain parameters in the hello packets match between the neighboring routers, they form the relationship called the adjacency. It is a sort of virtual communication between them. 
2. Then, each router exchanges special packets called Link State Advertisements (LSAs) with its neighbors (adjacent routers). In OSPF terminology the word link is the same as the interface. LSAs contain details such as: addresses/network masks configured on the links (interfaces running OSPF of course), the metric, the state of the link (which is its relation to the rest of the network), list of neighbors connected to the link.
3. Each router stores the LSAs in its Link State Database (LSDB). These LSAs are then flooded (advertised) to all OSPF neighbors. As a result of the LSA flooding, all routers in the area have identical LSDBs. An analogy would be having the same road map of a given country which all drivers use. Their journey's starting point is different but the map is still the same.
4. Each router runs Dijkstra's algorithm to select the best path from this topological database (LSDB). This way, each router creates loop free graph indicating the shortest (best) path to each network/subnet advertised. The best paths end up in the routing table.

OSPF Network Types

OSPF distinguishes between two major types of networks:

• Transit Networks - Networks which have two or more attached routers. The packets might be originated or passing through this type of network.
• Stub Networks - Networks which have only one router attached (one exit point). Packets are either originated or destined to these types of networks. A loopback interface is a type of stub network as well. The loopbacks are by default advertised as /32 prefixes (255.255.255.255). If you want to advertise loopbacks with their real network mask length, you must change the OSPF mode of operation to point-to-point (presented in the upcoming posts).

More specifically OSPF defines five different types of networks it can operate on. These are:

• Broadcast - such as Ethernet, Token-Ring
• Non Broadcast Multiple Access (NBMA) - such as Frame-Relay, ATM, X.25 (they may but do not have to be fully meshed)
• Point-To-Multipoint - such as Frame-Relay but treated as point-to-point links (Hub and Spoke)
• Point-to-Point - such as using PPP, HDLC protocols
• Virtual Links - used in special situations if the OSPF area 0 (backbone area) is partitioned or if an OSPF area cannot be connected to the area 0 directly

There are some differences in OSPF operation, depending on what type of network it runs on. I will explain the relevant details in the upcoming posts. 

OSPF routers will go through multiple states with their neighbors before they are ready to route the packets. Some of them will be used on all type of the networks but others only on specific types of networks listed above. 

OSPF Neighbor State Machine

All possible states between the neighbors are shown in pic. 1. They are also referred to as Neighbor State Machine.

Pic. 1 - OSPF Neighbor States.

Icons designed by: Andrzej Szoblik - http://www.newo.pl

Down

In this state, a router has not heard a hello packet from any OSPF neighbor yet.

Attempt

This state is applied only on NBMA networks in which the neighbors are not discovered dynamically but must be configured manually ('neighbor' statement in the config-router context).

Init

A router has heard a hello packet from its neighbor(s), which among other parameters the Router IDs of all the neighbors are listed  (look at hello packet structure in the next post).

2-Way

A router has seen its own Router ID in the hello packet from the neighbor(s). This means that bidirectional communication has been established between the routers.

ExStart

In this state the master/slave relationship is established necessary to exchange Database Description Packets. Since all the packets have their sequence number allowing routers to detect more recent information, initial numbers are negotiated in this state. The router with the highest Router ID becomes the master.

Exchange

The routers will send Database Description packets (description of the LDSB). Link State Request packets to request more recent LSAs are also sent in this state.

Loading

The Link State Request packets are sent to neighbors in the loading state. They request more recent LSAs discovered in the Exchange state. Link State Updates are sent in response to LSRs.

Full

OSPF neighbors are fully adjacent. All information about networks/subnets have been exchanged and acknowledged. 

OSPF Packet Types

In the Neighbor State Machine description, a few types of OSPF packets were mentioned. OSPF uses five types of packets for communication. Take a look at them (pic. 2):

Pic. 2 - OSPF Packet Types.

Icons designed by: Andrzej Szoblik - http://www.newo.pl

Type 1 - Hello

This packet type is used to discover neighbors and maintain the adjacencies between them. More details regarding a hello packet will be presented in the next post.

Type 2 - Database Description

It is used to describe the LSAs so that the receiving router (neighbor) can determine if all LSAs have been synchronized between them (all routers in the area must have the same LSDB). It is accomplished by exchanging the headers of LSAs (Database Description packets aka DD packets) with the neighbor(s). The receiving router will check if it has a match for all LSAs in its local database. If not, LSR packets are sent to retrieve the missing LSAs.

Type 3 - Link State Request

During the exchange state the router creates a list of all missing or older LSAs in the so called Link State Request List. Then, it sends one or more LSR packets asking the neighbor for the copy of all these LSAs.

Type 4 - Link State Update

It is the response to LSR packets. Contains one or more LSAs which are sent to the neighbor which sent LSR. Upon receiving them the router is flooding them to all its neighbors in order to maintain the same LSDB within the OSPF area.

Type 5 - Link State Acknowledgment

Each LSA the router receives must be acknowledged in order to synchronize the LSDB with neighbors reliably. This packet is used to acknowledge the reception of all LSAs.

This lesson's terminology should make it easier for you to understand some details of OSPF operation presented in the upcoming lessons.

In my next post, I will focus in on the process of building adjacency between OSPF routers.