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

CCIE or bust! And other going-on’s

The time has come…

I’ve finally made the committed decision to pursue my number for CCIE Routing and Switching. Like most folks in networking, I’ve gotten to the point where I’m feeling quite confident in my skills; solid foundations with just a few cobwebs here and there to knock out (mostly due to re-focusing). This decision has come to me after moving on from my VAR support job, which covered the entire breadth of Cisco but prevented my skills from becoming specialized, to a network engineer doing implementation for a financial org. Since I’m settling in to the new job, I’ve come to realize that all the nitty-gritty routing and switching bits are what interest me the most. Sure, I’ve done a bit of this and a bit of that in other areas (mostly in wireless and data center) but I’m an R&S guy.

Which brings me to my next bit of personal news – I’ve now gone from support to implementation. For those in the NOC’s or VAR’s, I would highly recommend it as a next step after you’ve gotten your feet wet in the trenches of support. It’s nice to learn what happens when things break and how to resolve issues, however, in my humble opinion, in order to have that deep understanding, you have to be there to know *why* something is configured or designed a certain way. Delving into the world of real-world business challenges and requirements, as well as ITIL and change management (ugh, how I loathe thee…a “necessary evil” some may say), I know get to make decisions on how my network looks and how it functions to accomplish a certain goal. Whatever those goals may be, such as a new project or business requirement. For those who are looking to move up in the world of networking, implementation is required experience.

So, while I haven’t been blogging much here (seriously, just so much to learn and write about…some may say too much!), I will be focusing on hitting the books and lab prep. I’m shooting for a Q2 2014 target. Wish me luck!

PS: There are so many good blogs out there with CCIE “notes” – however, I could start banging out tidbits here and there for things that stump me or just bother me…More to come.