OSPF Sequence Numbers
When an OSPF router originates an LSA for the first time, it will choose the sequence number 0x80000001. The 0x prefix means it’s a hexadecimal number, where each hex character represents a four bit binary word. This post discusses why the OSPF sequence number begins with 0x8, and some quirks when counting with signed numbers.
Why begin with 0x8?
The OSPF 32-bit sequence number is a 32-bit integer, yielding 4,294,967,296 separate sequence numbers. However, this OSPF sequence number is a signed integer. This means that half of those sequence numbers are negative numbers and half of the sequence numbers are positive.
The reason the sequence number starts with that funny 0x8 is because we need to steal the most significant bit (MSB) from the 32-bit binary number, to flag the number as positive or negative. An MSB of ‘1‘ means denotes a negative number, and an MSB of ‘0‘ denotes a positive number.
So 0x80000001 is the smallest possible negative 32-bit number. This is -1 in decimal. The OSPF standards call this number the ‘InitialSequenceNumber’.
Hex 0x8 0 0 0 0 0 0 1 Binary 1000 0000 0000 0000 0000 0000 0000 0001
On the other end of the scale, the maximum possible number in a signed 32-bit space is 0x7FFFFFFF, or +2147483648 in decimal. This is the ‘MaxSequenceNumber’
Hex 0x7 F F F F F F F Binary 0111 1111 1111 1111 1111 1111 1111 1111
Section 12.1.6 of RFC 2328 explains this in great detail, but unfortunately it assumes that you know the format of a signed integer.
What….0x80000001 is lower than 0x7FFFFFFF ?
I’ve seen a couple of posts on the interwebs trying to figure out how 0x80000001 could possible be lower than 0x7FFFFFFF.
It seems weird at first, but the sequence number starts at -1 and increments up to -2147483648. The next update increments the sequence number to 0, and the numbers become positive. The sequence number then continues incrementing until it reaches the maximum sequence number of +2147483648. At this point the LSA is flushed and is re-originated with a sequence number of -1 or 0x80000001.
So 0x7FFFFFFF > 0x00000000 > 0x80000001.
This is all a little academic because we rarely see such large sequence numbers. A process would have to be up hundreds of years before the sequence number becomes positive. In John Moys book ‘Anatomy of a routing protocol’, he says it could take up to 600 years for the sequence number to rollover. And that is conservative as he assumes that an update was sent every 5 seconds, rather than every 30 minutes on LS Refresh.
Why start at a negative number?
Oooh, that’s a tough question. The answer is I just don’t know.
My first guess is that is legacy from OSPFv1. When OSPFv1 used a lollipop sequence number space, having a negative number space made a lot of sense, but OSPF v2 uses a linear rather than lollipop numbering scheme.
Jeff Doyle describes this stuff in depth in the dynamic routing protocols chapter of “Routing TCP/IP Volume 1”. The best I could get from reading Jeff’s material is that the negative number space is still useful when deciding the age of a number which is close to MaxSequenceNumber.
Any readers have a good insight on the benefits of negative sequence numbers in OSPFv2?