How many OSPF routers can be deployed in one area ?

This question fits in the same category as “How long is a piece of string ?”. The answer is of course, “it depends”.

Back in 1998 whilst working for a router vendor, I was helping design a backbone network for a European ISP. Our web site was recommending a maximum of 40 – 60 routers per OSPF area, but the customer was designing for 180 in a single backbone area. The network was deployed and went live fine. I was curious as to how it would perform over the long term, so 6 months later I contacted the customers operations team for an update. (If you want to verify a network design, then there are few better ways than asking the Operations team. If there have been problems at 2am, you will definitely get some candid feedback). The customers operations team said the network was stable, and were happy with its performance. So the “official” 40 – 60 routers per area recommendation looked pretty conservative.

Today, if you google the title of this blog, the top hit says an area should have no more than 50 routers. That is from a design guide written in 2011. So over the 13 years from 1998 to 2011 the recommendation had surprisingly not increased. Now it’s almost 2020. 22 years later, what can we expect ?

Networking in 2020

Being a Link State protocol OSPF will consume as much CPU and Bandwidth as it needs until the network is converged. After that, whilst the network is stable, a good implementation will sit idle except for sending periodic hello’s to its neighbours. So (WAN) link stability will have a large impact on how well OSPF scales. We can probably assume that WAN links today are more stable than WAN links in 1998 [citation needed]. Anyway lets be conservative and assume they are no worse.

The critical resources OSPF needs are CPU to run the SPF algorithm, and CPU / Bandwidth to flood the LSA’s. Back in 1998 the Route Processors in the customers network used a 667 MHz Power PC CPU and the WAN links were either 2.5G (STM-16) or 10G (STM-64).

Over the 22 years from 1998-2020, Moore’s law states the CPU transistor count doubles every 2 years. Due to the increased transistor count the performance is expected to double around every 18 months. So the performance should have doubled around 14 times. In terms of CPU we should be able to support 180 x 2^14 = ~~3 million routers per area !

The lowest bandwidth link in the customer network in 1998 was 2.5G. In 2020 we can expect ISP backbones to be provisioned at 40G and 100G. So this is a much more modest 40/2.5 = 16X speedup. In terms of bandwidth for flooding LSA’s we should be able to support 180 x 16 = ~~3000 routers per area.

So in 2020, in theory you can have up to 3000 routers in a single area, in practice maybe not so much. Complex systems scale in surprising ways that are hard to model. But in 2020 OSPF should easily be able to scale to the 100’s of routers per area.

What if ?

  • What if we created a modern implementation of OSPF, developed with 21st Century Hardware in mind ?
  • What if the SPF Algorithm, the Link State Database and the Flood Queues used cache friendly data structures, so the CPU spends less time idling waiting for data ?
  • What if all incoming signalling was processed before running SPF and servicing the LSA flood queues ?
  • What if the OSPF route table remembered all the paths it has computed, rather than just the best ?
  • What if you could transfer 10,000 routes from OSPF to the RIB by moving an 8 byte pointer, rather than copying a gadzillion bytes between processes using IPC ?
  • What if the RIB only signalled the forwarding plane when a route had really changed, rather than when some route meta data had changed that the forwarding plane has no interest in ?
  • What if I stopped asking all these annoying “what if” questions and got to the point ?

In 1Q 2020 Flock Networks are shipping Routing Suite v20.0. If you would like to:

  • Be part of the early field trials.
  • Deploy over 1000 routers in a single OSPF area and not have the expected result being your vendor saying “You did what ?”
  • Save power by running a routing suite that mostly sleeps once the network is converged.
  • Gain observability into your existing OSPF network using a Read-Only JSON API.

Then please email eft@flocknetworks.com.

In the mean time here’s wishing everyone a Happy Solstice and a converged and stable 2020. If you are short of gift ideas I can highly recommend the book what if ?

Nick

Moving from C to Rust

I have spent many years systems programming in C. I have been playing around with Rust since 2015 and this year I decided to switch to primarily programming in Rust. This blog post is an attempt to explain why I have made this decision.

Although I have a background in Computer Science, at heart I’m a Developer / Network Engineer who just wants to “get stuff done” ™. I’ve played with many languages over the years and for me it was C and Python that stuck. I’m still a big fan of both of those languages.

When I first started playing with Rust, all my initial projects were checking how it felt as a systems programming language. That is, could I layout structures in memory as required ? How easy was it to call into C libraries using FFI ? And in particular how easy was it to interface with the Linux Kernel and put IP packets ‘on the wire’ ? I found Rust a good fit for this, probably because it is a C like language, so looked and felt familiar. As an aside, many developers who try Rust initially end up “fighting the borrow checker” that is built into the compiler. [In very rough terms the borrow checker makes sure that your code either has a single pointer to a mutable object, or multiple pointers to an immutable object, but never both]. If you are coming from programming in C then you can quite quickly work out why it’s complaining. However, it really makes you think hard about your data model, and who really owns each allocation of data. This can be painful if you are just trying to prototype something, but it is time well spent on anything that will end up in production.

My two compelling reasons for moving to Rust

Having decided that Rust was a capable systems programming language, I found there were 2 compelling reasons to make the move to Rust.

The first reason is that Rust is memory safe at compile time. This means you can say goodbye to the runtime memory corruption bugs you get in C. In safe Rust there is no ‘reading of’ or ‘writing to’ an invalid pointer. As I said earlier, I like C as a language, but hitting memory corruption bugs in production code is not fun. The worst part is that the point at which the program terminates, say due to a segfault to an invalid address, is likely to be thousands or millions of instructions after the code with the bug has executed. This makes finding the offending code difficult. I once spent over 3 weeks fixing a memory corruption bug in some IP Router software. That’s not something I’m proud of, but nor is it something I’m ashamed of. We could only reproduce the corruption when the device was running in production, and with all logging turned off. Fixing the bug came down to reasoning about 100,000’s of lines of C code. Eventually we came up with a theory about what was happening, wrote a ‘fix’ and the problem was never seen again. Whether we actually fixed the issue, or just changed some timing of events, I will never know. As an engineer this feels wholly inadequate.

The second reason is that Rust is data race free at compile time. As discussed above, memory corruption in single threaded code can be very hard to debug. Memory corruption in multi-threaded code is an order of magnitude more complicated. In my experience, it is possible to write reliable multi-threaded C, but you need to be very conservative and keep the threading model very simple (no bad thing), but refactoring the code is a major undertaking. In multi-threaded code there is such an explosion of event sequences that can happen, it is not possible to have exhaustive testing in place. With CPU frequencies levelling off and being replaced by multiple cores, the future of systems programming will need to be multi-threaded.

Drawbacks of moving to Rust

Rust certainly has some drawbacks when compared to C. For me the main one is the size of the executable produced by the compiler. In my experience of writing similar applications in C and in Rust, Rust release binaries tend to be around 5x larger than C release binaries. This is a combination of the fact that the Rust compiler optimises for speed not size and Rust projects suffer from dependency bloat. The Rust binary can be made smaller, and the dependency bloat problem actually comes from the advantage that you can so easily reuse other people’s libraries. But with Rust there is an extra step you need to take before releasing code, and that is to audit what is contributing to the binary size and is it a reasonable trade off? In the same way performance needs to be benchmarked between releases, with Rust binary size also needs to be tracked, to catch and investigate any large increases.

Rust also currently suffers from long compile times, and IDE support using RLS is slow and a CPU hog.

Moving a development team from C to Rust

Moving a development team from implementing in language A to language B is always going to be a hard sell if they do not already know language B. The team will have years / decades of experience in language A. Rust is a new language so it is likely a team of C programmers will not know Rust.

On top of this, Rust tends to pay back during the final stages of the development life cycle. I would guess that a team that knows both C and Rust, who started working on a new project, would be able to ship the first version of the software earlier if they wrote it in C rather than Rust. Rust tends to catch bugs earlier, at compile time rather than run time, which delays the production of the next binary. Rust forces the developer to iterate over the data model, until it is clean, before the code gets too complex, again delaying the production of the next binary. With Rust the team will probably implement Unit tests and Integration tests as they develop because all the infrastructure is in hand. With C the team may choose to produce the binary first and then possibly wrap some testing around it after. The QA teams will hit runtime panics in Rust that are hidden in C, again pushing out the date that the project ships.

So the sales pitch to management would go something like this. We have a team of highly skilled C developers. I suggest our new product “The IP packet mangler” should be written in Rust. On one hand if we write it in C we will ship it earlier and bring in revenue earlier. On the other hand Rust is shiny and new and would look good on our CV’s. Also the Rust compiler gives very pleasant error messages.

But wait, by catching bugs early, Rust gives you a huge payback in the long term. The C team have shipped a release with more bugs than the Rust team. Customers will be hitting bugs in the C product that don’t exist in the Rust product. As each team is working on the v1.1 features the C team will be interrupted more on bug fixes. This will cause frustration as most bug fixes are more important than implementing new features. The C development team will be getting more randomly timed, high level interrupts of various length, stopping them doing the ‘real work’ of implementing the new features.

Maybe the v1.1 C and Rust versions will ship around the same time. After that the Rust team will pull ahead, as the bug backlog for both teams will now cover multiple releases. The Rust team will probably ship v1.2 and all subsequent releases earlier and to a higher quality.

Obviously there is a lot of conjecture in the above argument, and it is slightly tongue in cheek. However I think the main point stands that it is preferable to pay your development costs upfront and as early as possible.

In summary

You might be able to prototype faster in C, but I believe you will reach production quality faster in Rust. Also with Rust, keeping that production quality high going forward will be easier.

And that is why I have moved from C to Rust.

Rust in 2020: A User’s Perspective

I’m a Rust user rather than a Rust developer. I have been writing Rust code since just before the 1.0 release, and have followed the development of the language since then. I believe the future of systems programming is likely to be in Rust. I am certainly invested in the Rust language. Last month I resigned from my job writing embedded C, so I could start my own company, producing IP Networking software in Rust.

The “Rust 2018” theme was Productivity, and there is still work to be done there. In my day to day programming the much mentioned “long compile times” and “RLS performance” have the most immediate impact. But the trend on both of these looks good.

I feel having frequent (3 yearly) releases is beneficial as it makes the upgrade between releases a moderate piece of work. I moved from 2015 to 2018 when I had a spare couple of hours. I did not plan the upgrade, I just had some time free so decided to do it. (The upgrade was flawless, thanks to all involved). If releases are infrequent, then the task becomes > 1 day, and its never going to be the highest priority work.

If there is to be a “Rust 2021” then I think the theme should be along the lines of “scoping”. That is, what is part of the Rust language now, what might become part of it, and what will never be part of it. A similar exercise could cover the Rust standard libraries.

I have spent many years programming in C and (despite carrying around the loaded gun) I’ve enjoyed it. I like C as a language, it is fast, compact, portable. You can look at C code and have some idea what Assembly will be produced (as long as optimizations are off!). You can predict roughly how it will perform. For me Rust 2018 is already a drop in replacement for C, and at the moment I can reason about Rust programs in roughly the same way.

As languages mature there is a tendency to add more and more features as each users needs are unique. Often it is easier to just say yes to a new feature to keep everyone happy, and well why not ? But the language gets bloated, the language loses a coherent style, and the subset of the language used starts to vary greatly between projects.

So could “Rust 2021” draw a periphery around the Rust language ? If an RFC wants to add a feature outside of this area then it should be held to a higher standard.

One thing that I hope won’t change in Rust going forward is the open constructive technical discussions that take place. The Rust core teams seem to be full of highly skilled engineers who are also humble and genuinely want to find the best technical solution, regardless of where it originated. This is a very productive and healthy culture, but easily lost, so long may it continue. Hopefully new members to the core teams will share similar traits. Sorry couldn’t resist finishing on a pun.

Nick