OSPF Packet Level Understanding

Posted by

OSPF Packet level reading

The concept of a consistent database is a core requirement for link-state protocols and allows the protocols to ensure a loop-free topology. Since no loops exist, each router then makes consistent forwarding decisions for user data packets. Ensuring the proper advertisement of link-state updates and propagating these updates correctly are the only barriers to preventing loops

OSPF Packet Types

Common Packet Header

All OSPF packets share a common 24-octet header. This header allows the receiving router to determine whether the packet is valid and should be processed. OSPF header includes the following:

Version (1 octet) This field details the current version of OSPF used by the local router.  It is set to a value of 2, the default value (OSPFv2 – version 2).

Type (1 octet) This field specifies the type of OSPF packet.

Possible values include:

  1 – Hello packet  The data contained in a Hello packet will be a list of neighbors.
  2 – Database descriptor  — will contain list of LSA
  3 – Link-state request  will contain a series of fields describing the requested LSAs
  4 – Link-state update  will contain a list of LSAs,
  5 – Link-state acknowledgment  — will contain list of LSA

Packet Length (2 octets) This field displays the total length, in octets, of the OSPF packet.

Router ID (4 octets) The router ID of the advertising router appears in this field.

Area ID (4 octets) This field contains the 32-bit area ID assigned to the interface used to send the OSPF packet.

Checksum (2 octets) This field displays a standard IP checksum for the entire OSPF packet, excluding the 64-bit authentication field.

Authentication Type (2 octets) The specific type of authentication used by OSPF is encoded in this field. Possible values are:

0—Null authentication
1—Simple password
2—MD5 cryptographic authentication

Authentication (8 octets) This field displays the authentication data to verify the packet’s integrity.
Screen Shot 2018-04-07 at 6.21.56 PM.png

Observations:

– Version field is by default 2
– Message type is Type 1 – “Hello Packet”
– Packet Length is 48 Bytes
– Source OSPF Router is router-id of router originated this LSA. Router-id remains same in OSPF header while each node re-encapsulates it and floods it further.
– Area ID is 0
– Checksum. Sequence number is exempted from checksum calculation so that sequence number can be increased without recalculating checksum value.
– Authentication Type could 0,1,2 – Null, Plain text or MD5. Here it is Null
– Authentication Data is blank since no password is being used and Auth Type is 0
– Fields to be matched from OSPF header
– Version
– Area ID
– Authentication

Details of each OSPF packet type

1 – Hello packet
Screen Shot 2018-04-07 at 6.22.44 PM.png

Observations:

  • This is OSPF Hello packet. Used to discover and maintain OSPF neighborship.
  • Fields to be matched for neighborship are :
    • Network Mask
    • Hello interval
    • Dead interval
  • Carries information for DR and BDR and after Two-Way state plays role in DR/BDR election.
  • Carries list of Active neighbors

2 – Database descriptor

Screen Shot 2018-04-07 at 6.23.33 PM.png

Observations:

  • It is used to send OSPF database summary (only headers) to neighboring router for OSPF database synchronization.
  • Before exchanging database summary, both routers send empty DD packet for master/slave election and then Master router decides sequence number that is used reliable packet exchange.
  • If this is first DBD packet then Init bit will be set
  • More bit is set if further messages are there to exchange
  • Initially both routers announce themselves as Master and thus Master bit is set.
  • Router picks any random sequence number and increments it by 1 whenever generates new LSA.

Reliable packet exchange : Master sends DD packet with sequence X then slave sends DD packet with same sequence X that confirms to master that slave has received DD packet with seq X. Master increments it by 1 and sends another DD packet. When Master has nothing to send but has not received DD packet from slave with M-bit=0, it sends empty DD packet by increasing sequence by 1. When slave receives packet with seq X+1, it confirms that DD packet has been delivered to Master properly. Till the time delivery is not confirmed both routers put those DD packets in Retransmit queue and running timer RxmtInterval (Retransmit Interval that is 5 sec by default).

Window size is 1. That means only one packet is allowed outstanding at one time (unacknowledged).

Since it is slave that would confirm the completion of exchange first, Slave generates ExchangeDone event always before Master.

Screen Shot 2018-04-07 at 6.24.05 PM.png

OSPF Acknowledgement packet is also similar but that does not contain part related to Master/Slave negotiation (Interface MTU, I/M/MS) and DD sequence number

3 – Link-state request 

Screen Shot 2018-04-07 at 6.24.38 PM.png

  • After receiving DD packets from neighbor, Router maintains “Link state request list” for all missing LSA or for more recent LSA.
  • Router sends LSA request packet that contains a series of fields describing the requested LSAs
  • This contains only header like Link State ID and Advertising Router
  • Router waits for Links State Update in return from neighboring router

Reliable packet exchange: LSR is acknowledged by LSU. If router does not receive LSU for requested LSA, it sends LSR again after RxmtInterval period.

Screen Shot 2018-04-07 at 6.25.38 PM.png

4 – Link-state update

Screen Shot 2018-04-07 at 6.26.16 PMScreen Shot 2018-04-07 at 6.26.24 PM

  • In response to LSR, router sends LSU
  • If not acknowledged within RxmtInterval, router retransmits LSU.

Reliable delivery : Since after Link State Update no further information to be exchanged, this packet is acknowledged explicitly by Link State Acknowledgment packet. It can be implicitly acknowledged by sending complete update back on same interface also. (Implicit ack is used in broadcast segment where DR sends same update to all SPFRouters). Else sending complete update back is unnecessary extra overhead and sending only LSA header is sufficient via LS Ack packets. 

5 – Link-state acknowledgment

Screen Shot 2018-04-07 at 6.27.07 PMScreen Shot 2018-04-07 at 6.27.16 PM

Many acknowledgments may be grouped together into a single LinkState Acknowledgment packet. Such a packet is sent back out the interface which received the LSAs.

The packet can be sent in one of two ways:

1. delayed and sent on an interval timer, or
2. sent directly to a particular neighbor.

The particular acknowledgment strategy used depends on the circumstances surrounding the receipt of the LSA. Sending delayed acknowledgments accomplishes several things:

  1. It facilitates the packaging of multiple acknowledgments in a single Link State Acknowledgment packet.
  2. It enables a single Link State Acknowledgment packet to indicate acknowledgments to several neighbors at once (through multicasting) and
  3. It randomizes the Link State Acknowledgment packets sent by the various routers attached to a common network.

The fixed interval between a router’s delayed transmissions must be short(less than RxmtInterval) or needless retransmissions will ensue. Delayed acknowledgments must be delivered to all adjacent routers associated with the interface. On broadcast networks, this is accomplished by sending the delayed Link State Acknowledgment packets as multicasts. The Destination IP address used depends on the state of the interface. If the interface state is DR or Backup, the destination AllSPFRouters is used. In all other states, the destination AllDRouters is used. On non-broadcast networks, delayed Link State Acknowledgment packets must be unicast separately over each adjacency (i.e., neighbor whose state is >= Exchange).

Direct acknowledgments are sent directly to a particular neighbor in response to the receipt of duplicate LSAs. Direct acknowledgments are sent immediately when the duplicate is received. On multi-access networks, these acknowledgments are sent directly to the neighbor’s IP address (Unicast).

The sequence number prevents “replay attacks,” in which OSPF packets are captured, modified, and retransmitted to a router.

Because the checksum calculation includes the sequence number, and because the sequence numbers may be different, the checksums will also be different.

Screen Shot 2018-04-07 at 6.28.07 PM.png

OSPF packets destination : Unicast or Multicast :

As per RFC 2328:

The IP destination address for the packet is selected as follows. 

  • On physical point-to-point networks, the IP destination is always set to the address AllSPFRouters. 
  • On all other network types (including virtual links), the majority of OSPF packets are sent as unicast, i.e., sent directly to the other end of the adjacency.  In this case, the IP destination is just the Neighbor IP address associated with the other end of the adjacency.
  • The only packets not sent as unicast are on broadcast networks; on these networks Hello packets are sent to the multicast destination AllSPFRouters, the Designated Router and its Backup send both Link State Update.

Hello Packet

Hello packets are generally sent to multicast address but Immediate Hello is sent to unicast address.

OSPF – Immediate hellos

Unicast Hello packets

Screen Shot 2018-04-07 at 6.28.49 PM.png

Immediate Hello

The general idea here is that once you see a hello from a neighbor you should immediately reply to it, rather than waiting for your next hello timer interval.  By reducing the time-to reach 2-WAY state, this mechanism speeds up convergence

DBD Packet

As per RFC on point to point link it should be sent to ALLSPFRouters but on Cisco it is sent as unicast

Screen Shot 2018-04-07 at 6.29.31 PM.png

LS Request Packet

Screen Shot 2018-04-07 at 6.30.01 PM.png

LS Update Packet

Screen Shot 2018-04-07 at 6.30.26 PM.png

LS Acknowledge Packet

Depending on the state of the sending interface and the sender of the corresponding Link State Update packet, a Link State Acknowledgment packet is sent either to the multicast address AllSPFRouters, to the multicast address AllDRouters, or as a unicast.

Screen Shot 2018-04-07 at 6.31.18 PM.png

Retransmit Interval

Screen Shot 2018-04-07 at 6.31.53 PM.png

R2 sends 3 LS Update messages that total contains 4 LSA header with sequence 0x80000001, 0x80000005, 0x80000006 and 0x80000016.

R1 acknowledges 0x80000001, 0x80000005, and 0x80000016 but not 0x80000006.

R2 retransmits that LSA after 5 sec (09:48:21 , 09:48:26) but this time it is unicast packet.

OSPF Neighborship

  • Down
  • Init
  • Two-way
  • exStart
  • Exchange
  • Loading
  • Full

Down

The initial state of a neighbor conversation indicates that no Hellos have been heard from the neighbor in the last RouterDeadInterval. Hellos are not sent to down neighbors unless those neighbors are on NBMA networks; in this case, Hellos are sent every PollInterval. If a neighbor transitions to the Down state from some higher state, the link state Retransmission List, Database Summary List, and link state request list are cleared.

Attempt

This state applies only to neighbors on NBMA networks, where neighbors are manually configured. A DR-eligible router will transition a neighbor to the Attempt state when the interface to the neighbor first becomes Active or when the router is the DR or BDR. A router will send packets to a neighbor in Attempt state at the HelloInterval instead of the PollInterval.

Init

This state indicates that a Hello packet has been seen from the neighbor in the last RouterDeadInterval, but 2-Way communication has not yet been established. A router will include the Router IDs of all neighbors in this state or higher in the Neighbor field of the Hello packets.

2-Way

This state indicates that the router has seen its own Router ID in the Neighbor field of the neighbor’s Hello packets, which means that a bidirectional conversation has been established. On multi-access networks, neighbors must be in this state or higher to be eligible to be elected as the DR or BDR. The reception of a Database Description packet from a neighbor in the init state will also cause a transition to 2-Way.

ExStart

In this state, the router and its neighbor establish a master/slave relationship and determine the initial DD sequence number in preparation for the exchange of Database Description packets. The neighbor with the highest interface address becomes the master.

Exchange

The router sends Database Description packets describing its entire link state database to neighbors that are in the Exchange state. The router may also send Link State Request packets, requesting more recent LSAs, to neighbors in this state.

Loading

The router will send Link State Request packets to neighbors that are in the Loading state, requesting more recent LSAs that have been discovered in the Exchange state but have not yet been received.

Full

Neighbors in this state are fully adjacent, and the adjacencies will appear in Router LSAs and Network LSAs.

DR/BDR Election:

Requirement : In a LAN environment, multiple routers are connected on same segment and if each router would have adjacency to remaining routers then it would be N(N-1)/2 adjacencies and too many LSA flooding while all nodes would share same LSA as all part of same area and contains same database. To avoid this, one of routers is elected as Designated Router and all others can have adjacency to this DR. To avoid single point of failure, there could be Backup Designated Router that can take over once active DR fails. All DROTHER nodes would have adjacency with both DR and BDR.

Conditions:

  1. In a stable LAN if a new router turns up, it should not disturb the established adjacencies thus should not replace the active DR however it can replace the BDR.
  2. There is a requirement of user configurable field to control DR election and in case of tie, one unique tie-breaker option.
  3. DR should not be preemptive that means if active DR fails, backup DR takes over and becomes active DR but when previous DR comes back up it should preempt the DR role. This is related to 1st condition.
  4. When DR fails, BDR should become DR. BDR election should start after that only and router that has become DR can not participate in BDR election.

Router priority: This is user configurable value 8-bit unsigned value. That means minimum value is 0. This is used for DR election purpose and highest priority takes precedence. Default value is 1. Range is 0 to 255. Nodes, with DR priority of 0, are not eligible for DR election.

DR election happens on each router individually only between neighbors who are in Two-Way or higher OSPF state. DR priority field is available in OSPF Hello packet and thus a router known DR priority for any node that is in Two-Way or higher OSPF state. In case of same priority, router-id is tie breaker.

After completing DR/BDR election, each router advertises its result in sub-sequent Hello packets in DR and BDR fields.

Screen Shot 2018-04-07 at 6.32.38 PM.png

DR election algorithm would remain same always and we have to meet 1st condition as well. Thus any new router in LAN can participate in BDR election but not DR election and this is followed even when first time DR/BDR election starts for that LAN.

  1. First BDR gets elected and routers only who have not declared themselves as DR (that means existing BDR and DROTHER) are eligible for this election.
  2. Router with highest priority wins, in case of tie router will highest router-id wins election among sub-set as mentioned in point 1.
  3. Once BDR gets elected, router starts DR election and routers who have declared themselves as DR are eligible here. Same winning rule applies in this sub-set as well.
  4. If no router advertising itself as DR then elected BDR will be declared as BDR.

The reason behind the election algorithm’s complexity is the desire for an orderly transition from Backup Designated Router to Designated Router, when the current Designated Router fails. This orderly transition is ensured through the introduction of hysteresis: no new Backup Designated Router can be chosen until the old Backup accepts its new Designated Router responsibilities.

exStart State:

– Master/Slave decision by exchanging initial DBD packets (I bit, M bit and MS bit set)

Exchange State:

  • Each router describes its entire links state database by sending DD packets.
  • Each DD packet has a sequence number and it is explicitly acknowledged.
  • Window size is one. That means only one packet is allowed outstanding at one time (unacknowledged).
  • LSA can be requested by using LS request packet if LSA is missing or more recent LSA.

Neighborship gets stuck in ExStart/Exchange

RFC-2328:

“If the Interface MTU field in the Database Description packet indicates an IP datagram size that is larger than the router can accept on the receiving interface without fragmentation, the Database Description packet is rejected.”

RFC does not say that MTU should match but it says advertised MTU should not be higher than the interface MTU that means if advertised MTU is lower than interface MTU then DD packet can be accepted.

During Master/Slave election, both routers advertises I,M,MS bit and node with highest interface IP address becomes master and other node follow DD sequence of master.

If slave has higher MTU than Master, it can accept the DD packet and starts sending LSA header (further DD packets with M bit) and moves to Exchange state. But if slave has lower MTU than Master, it would not accept the DD from master and keep sending DD packet with (I,M and MS) packet and will remain in ExStart state. And master router also remains in ExStart state.

Example:

Case-1: IP mtu on R1 is 1500 and on R2 1400

R1#show ip ospf neighbor
Neighbor ID     Pri   State           Dead Time   Address         Interface
2.2.2.2           1   EXCHANGE/BDR    00:00:38    172.31.12.2     FastEthernet0/0

R2#show ip ospf nei
Neighbor ID     Pri   State           Dead Time   Address         Interface
1.1.1.1           1   EXSTART/DR      00:00:37    172.31.12.1     FastEthernet0/0

Case-2: IP mtu on R1 is 1400 and on R2 1500

R1#show ip ospf neighbor
Neighbor ID     Pri   State           Dead Time   Address         Interface
2.2.2.2           1   EXSTART/BDR     00:00:35    172.31.12.2     FastEthernet0/0

R2#show ip ospf nei
Neighbor ID     Pri   State           Dead Time   Address         Interface
1.1.1.1           1   EXSTART/DR      00:00:38    172.31.12.1     FastEthernet0/0

OSPF Sequence number and its significance

OSPF sequence number is signed 32-bit integer. That means it can have positive and negative values. Routing protocols use Lollipop sequence numbering. In this numbering scheme, sequence numbers start at a negative value, increase until they reach zero, then cycles through a finite set of positive numbers indefinitely.

In OSPF it starts with -2^31 +1 (0x80000001) and goes till 2^31 – 1 (0x7fffffff).

It is used to detect old and duplicate LSAs.

Two type of sequence numbers in OSPF packets

   1. Sequence number in DBD packets – DD sequence number (random number)
   2. Sequence number in LSA update – LSA sequence number (starts with 0x80000001)

OSPF Reliable flooding

Out of 5 OSPF packets, OSPF Hello and OSPF Acknowledgement packet need not to be acknowledged. 

All LSDB – Link State Database in all routers participating in OSPF domain need to be exactly the same. That is main assumption of SPF Dijkstra’s Algorithm and using that argument SPF is able to calculate Shortest Path Tree to all destinations in domain.

That is why the most important role depend from correct LSA flooding in domain.

Each individual LSA generated by any routers need to be acknowledged. This may be accomplished by either an :

1) Implicit ack
2) Explicit ack

What is Implicit Ack and Explicit Ack:

Implicit ACK is sending same LSA back in LS update message.

Explicit ACK is sending only LSA header in OSPF Type 5 packet (LSA Acknowledgement) packet.

Example:

  1. A non-DR router on an Ethernet segment detects a topology change and needs to inform other routers about it. It sends the LSU packet to the DR and BDR using the 224.0.0.6 destination IP address.
  2. Both DR and BDR receive the packet. Normally, you would expect that the DR would send an LSAck acknowledging the successful receipt of the LSU. However, the DR needs to propagate the LSU back to the segment using the 224.0.0.5 destination IP address anyway, so it just does exactly that, without sending a standalone LSAck.
  3. The original router receives the same update from the DR it sent it a moment ago, and it considers it as an implicit acknowledgement. No further LSAck from the DR is expected.
  4. Other routers on the segment receive the LSU and acknowledge its receipt via an explicit LSAck message back to the DR. This is an explicit form of acknowledgement.

In TCP also we use reliable delivery and done by ACK. TCP use sequence number to ACK the data. Only sequence number in ACK is sufficient to confirm that all data before that is received.  TCP is generally used to send bulk data and to improve throughout, we use windowing method. Sender can send number of bytes equal to window, max is 65535 that means Sender can send 65535 bytes at a time without waiting for ACK.

In OSPF, receiver sends LSA header back to ack the LSA update and not sequence number. Window size is 1 always that means Sender can not send further LS update until it is acknowledged. If LSA is not acknowledged within a fix time, router retransmits the LSA. This is called Rxmt Interval and it is 5 sec by default.

  • All duplicate LSA is received from a neighbor possibly indicating that it has not yet received an ack. That is why router put that LSA into Link State Retransmission list of every neighbor to which it was sent. If router  doesn’t receive ack it will retransmit its LSA every Rxmt Internal.
  • LSA contains 3 values : seq number, checksum and age. All of them are responsible for keeping all LSDB (Link State Database) in whole OSPF domain updated and exactly the same. 
  • OSPF uses 32-bit signed, linear seq number from Initial Sequence Number  to Max Sequence Number. When router send his first LSA it sets the value for Initial Sequence Number and increments the seq number by one.

If the present seq number is MaxSeqNr and a new instance must be created the router must first flush the old LSA from all databases in the area. It sets the age to Maxage = 3600 sec and refloods it to everyone.

Only the router that has originated the LSA can permanently age it or modify it!

There is also mechanism which is preventing legitimate from reaching MaxAge. In brief if nothing is happening on the network, there are no faults we don’t have flush whole OSPF LSDB every 1 hour. That is why Link State Refresh is set up for 30 mins. Each half an hour known as LSRefresh Time the router that originate LSA flood a new copy of the LSA with and increment seq number and age of zero.

OSPF LSAs

Screen Shot 2018-04-07 at 6.33.32 PM.png

Type-1 LSA

Screen Shot 2018-04-07 at 6.34.06 PM.png

It is identified by router-id (Advertising Router). It is mentioned total number of links and then for each link we have details like :

  • Link ID — IP address on the link
  • Link Data — Network mask on the link
  • Link Type — one of 4 as mentioned in below table
  • Metric — OSPF cost on the link

Type-1 LSA describes all links connected to the router.

Screen Shot 2018-04-07 at 6.34.58 PM

Type-2 LSA

Screen Shot 2018-04-07 at 6.35.52 PM.png

This is originated by DR router and it contains list of all attached routers in that broadcast segment + Interface IP and mask. No Metric information, this just describes connectivity of routers via one LAN segment.

Type-3 LSA

Screen Shot 2018-04-07 at 6.36.27 PM.png

This is generated by ABR routers to convert Type-1 LSA to Type-3 LSA. It contains information only about IP/mask and metric from ABR. This provides reachability information and no topology information. This is kind of distance vector since routers in other areas need to believe on links state and cost information provided by ABR router.

Type-4 LSA

Screen Shot 2018-04-07 at 6.37.19 PM.png

This is ASBR summary LSA, generated by ABR router. Carries information only about ASBR router-id and its metric from ABR.

Type-5 LSA

Screen Shot 2018-04-07 at 6.37.48 PM.png

This is External LSA, generated by ASBR. This contains only prefix (IP/mask), external type, default cost and Forwarding address information. If router is advertising external LSA on same LAN where next-hop of route belongs then router can set forwarding address to inform all routers in LAN to send traffic directly to next-hop instead of it first.

Screen Shot 2018-04-07 at 6.38.30 PM.png

Optional OSPF capabilities

The OSPF protocol defines several optional capabilities. A router indicates the optional capabilities that it supports in its

  • OSPF Hello packets — mismatch can prevent neighbor relationship from forming
  • Database Description packets — mismatch would result in only a subset of the link state database being exchanged between two neighbors.
  • LSAs — can affect building routing table and router incapable of certain functions can be avoided when building the shortest path tree.

This enables routers supporting a mix of optional capabilities to coexist in a single Autonomous System. Some capabilities must be supported by all routers attached to a specific area. In this case, a router will not accept a neighbor’s Hello Packet unless there is a match in reported capabilities (i.e., a capability mismatch prevents a neighbor relationship from forming). An example of this is the ExternalRoutingCapability. Other capabilities can be negotiated during the Database Exchange process. This is accomplished by specifying the optional capabilities in Database Description packets. A capability mismatch with a neighbor in this case will result in only a subset of the link state database being exchanged between the two neighbors. The routing table build process can also be affected by the presence/absence of optional capabilities. For example, since the optional capabilities are reported in LSAs, routers incapable of certain functions can be avoided when building the shortest path tree.

Hello Packet Option field

Screen Shot 2018-04-07 at 6.39.03 PM

DD Packet Option field

Screen Shot 2018-04-07 at 6.39.44 PM.png

LSA update packet Option field

Screen Shot 2018-04-07 at 6.40.13 PM.png

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s