OSPF sequence numbers – why 80 million is smaller than 70 million

So a bit of a specific topic today. Going through Doyle’s Routing TCP/IP Volume 1, I felt my brain melt as he went through explaining sequence numbers in link-state advertisements (in a general sense, not specific to just OSPF). He describes two types of number “spaces” – the range of possible values – to describe how protocols sequence their LSA’s.

Ignoring the historic bits, such as Radia Perlman’s “lollipop space”, which is essentially a combination of cycling numbers with a fixed initialization value (this was part of the first version of OSPF drafts – not relevant for OSPFv2 or anything else), numbering spaces either follow linearly or circular.

In linear spaces, numbers start at x and end at y. The issue with linear space is that you could potentially “run out” of number space. This could cause a link-state protocol to be unable to distinguish between LSA’s that are the most recent from the originating router or just LSA’s being flooded from one router to the next. Link-state protocols, when receiving an LSA with the highest possible sequence number, shut down and age out it’s link-state database (LSDB) to flush all the older LSA’s out. To mitigate this, the designers had to make sure the field for a sequence number was large enough so as to never reasonably hit that highest possible value (y). Both OSPFv2 and IS-IS uses this number space scheme.

Circular number spaces never end – once a maximum value number is reached, it “resets” back to the lower boundary of the space. Since IS-IS and OSPFv2 use linear spaces, this is included for completeness. Perlman’s lollipop scheme used both linear and circular as a combination but these are not included in modern link state protocols.

IS-IS uses a rather simple scheme for it’s number space. A router will originate it’s own directly-connected link states with a sequence number of one (0x00000001), with a maximum sequence number of 4.2 billion (0xFFFFFFFF). This is because the IS-IS field for sequence numbers in its LSP’s (link state packet) uses unsigned 32-bit integers. These values range from 1 – 4294967295 in decimal.

OSPF, on the other hand, uses signed 32-bit integers. While it uses the same scheme for number spaces as IS-IS (linear), the way the values are represented (especially on a router’s database outputs) is…different.

Observe:

Net Link States (Area 1)

Link ID         ADV Router      Age         Seq#       Checksum
192.168.1.112   10.0.0.112      1862        0x80000237 0x00D860
192.168.7.113   10.0.0.113      12          0x80000001 0x00E8F5

So…it starts are 80 000 000?

Obviously, the seq. number is represented in hexadecimal format…but why 0x80000001? Doesn’t that translate to 2 billion decimal? The detail to note is the fact that this field is a signed integer. That means the integers actually range from – 2147483648 to + 2147483648. When processing this field in binary, the CPU needs a way of comparing sequence numbers to determine which one is “higher” – in this case, closer to positive +2147483648.

Programming languages such as C/C++ must pay particular attention to integers declared as signed vs unsigned. Some google- and wiki-fu later, the reason we see sequence numbers starting at 0x80000001 (0x80000000 is reserved via the RFC standard) is because the left-most/most significant bit determines whether a number is represented as a positive value or a negative value. When the MSB is set, the integer is a negative value. When the MSB is not set, it is a positive integer.

 

So…
0x80000001 is 1000 0000 …. 0000 0001 in binary
Since the MSB is set, this is the “first” integer value in a 32-bit signed integer range. It doesn’t make sense to think of these values in decimal values, since this does indeed translate “directly” to 2 billion. These sequence numbers will increment 0x80000002….all the way to 0xFFFFFFFF (-1 in decimal). Incrementing one more time would start the sequence at decimal 0. This is because the MSB must become “unset” for it to represent positive values. The range then continues from 0x00000001 until 0x7FFFFFFE. Again, from the RFC, 0x7FFFFFFF is reserved (actually, an LSA received with this maximum possible sequence number triggers OSPF to flush its LSDB…more nuts and bolts to be expanded on later).

 

The choice of using signed vs unsigned gets kind of blurred between hardware and software. The use of signed integers simplifies ALU designs for CPUs and most (if not all) programming languages implement signedness in their integer data types…Why the IETF chose to use signed integers as part of the OSPFv2 spec? Who knows…

 

Anyways, this really bothered me for a couple days. I feel better now that it’s on paper. Any gross errors or omissions, leave it in the comments!

 

PS: More math-savvy folks will scream at this in regards to two’s complement role here with signed integer binary representation…I just wanted to know and jot down why IOS shows the starting sequence numbers in show ip ospf database as 0x80000001. So there you have it. Further reading for the curious

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: