OSPF – Sequence numbers are sooo negative
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?
6 thoughts on “OSPF – Sequence numbers are sooo negative”
This was a fun post and made my brain sweat a bit.
Just curious, as I never use the sequence number as a tool.
Is the sequence number something you use for troubleshooting either via cli or pcap?
Hey Will,
Normally it’s sufficient to look at the sequence number for the LSA on the CLI. If you see a rapidly increasing sequence number it can be a sign of a flapping link. In dire situations you can have non-adjacency routers with duplicate RIDs battling to oust each other, by continually flushing the others sequence number. In that case, you’ll normally see a FLOOD-WAR syslog, but the sequence number will increase rapidly.
I’ll do a follow up on post on why sequence numbers are important for a reloading router.
Thank you for explaining this. I’m most of the way through the OSPF section of the ROUTE FLG (which is a total holocaust), and I thought it was a typo when it said the sequence started at 0x8, and finished on 0x7
Hey Stuart, no problem glad I could help. It took me a little while to get my head around it too.
Hi, nice article but I think you got it wrong with the 32bit signed integer representation.
-1 is 0xFFFFFFFF while the smallest negative number used for the first LSA is -2147483647 (0x80000001 in hexadecimal). 0x80000000 is of course reserved.
It all make sense if you know about Two’s complement mathematical operation.
Example: To get the arithmetic negative of 12 00001100b:
1. Invert all bits: 11110011b.
2. Add 1: 11110100b.
Mounir.
Hey John,
Thank you this post is perfect. I was struggling on this concept until I read about the seq_n type.
I have one more question on this topic. When the LSA reaches the maximum seq_n and gets flushed from the DB in the whole area will the network/s described in that LSA be unreachable until the new LSA will be flooded?
Thank you