Fibbing: OSPF-Based Traffic Engineering with Laurent Vanbever

You might be familiar with the idea of using BGP as an SDN tool that pushes forwarding entries into routing and forwarding tables of individual devices, allowing you to build hop-by-hop path across the network (more details in Packet Pushers podcast with Petr Lapukhov).

Researchers from University of Louvain, ETH Zürich and Princeton figured out how to use OSPF to get the same job done and called their approach Fibbing. For more details, listen to Episode 45 of Software Gone Wild podcast with Laurent Vanbever (one of the authors), visit the project web site, or download the source code.

5 comments:

  1. This is really awesome. The fact that there is an implementation on github to start tinkering with makes it even better!

    For anyone a little lost about the "local lies" - the actual implementation on Cisco IOS is using secondary addresses on the interfaces to be used for fibbing. During the podcast, there was mention of static routes being used for this - but after looking at the code and github examples, they seem to be using secondary addresses for this purpose.
    Replies
    1. Thanks for having a look at it! Hopefully we'll release the mentionned mininet-based labs in the upcoming days.
      The implementation clearly deserves more documentation, and we're working on it, feel free to mail us if you have questions.

      For the local lies, the goal is to have this:
      - One distinct address per router interface
      - Only the routers adjacent to that interface can use it as next-hop.
      - In order to be 'fibbed', adjacent routers need to learn about the reachability of that address through OSPF (T5/7 forwarding addresses must be resolvable in the OSPF domain to be used).

      We first wanted to rely on AD but that didn't work as it does not affect the OSPF decision process. We then thought about static routes, but this was creating recursive routes and as such not producing the effect we wanted.
      Instead, we settled for the following approach:
      - Assign a private range for these 'private' addresses, e.g. 10.0.0.0/8
      - Assign as many extra addresses as wanted on each interface, 1 being the minimum, more being useful to setup uneven load balancing (e.g. add 4 routes on the left and 1 on the right to achive 20-80 load balancing requires 4 secondary IPs per interface) -- Can be directly done on JunOS, doing it on IOS requires to setup the secondary address with a bigger netmask then adding loopbacks.
      - Configure the OSPF daemons with a single ACL - the same for every router - such that the OSPF routes towards any of these 'private addresses' do not get installed in the FIBs (the distribute list in our example lab).
      The result is that when we flood a T5 LSA with one of these address as FA, only the routers adjacent to that address can use it, as they are the only one that can resolve the FA both in their OSPF RIB and in their FIB -- through the directly connected routes.

      The end result is thus that we can change the nexthop of any router to any other router, without affecting the others. By chaining this, we can thus setup arbitrary routes in the network. This is the 'last resort' technique if we are not able to find a 'standard' T5 LSA with the proper metric value to move only the routers that we want, as it is more expensive wrt. the number of LSAs needed to change a route.
  2. It a nice hack. And I applaud all experimentation with routing systems. Really cool.

    However, if I look at this objectively, I find it a pretty ugly solution. I think the main benefit is that this does not require any support from vendors. It should work with any decent OSPF-router.

    But the way this is done is very inefficient. If I understand correctly, you basically build a new routing table for every router in the network. And then for every routing entry in every routing table for every router, you create a type-5 LSA. And flood all of those into the network. So suppose you have 100 routers in your network. And 300 routes that matter. It means you have to create 100 x 300 = 30k LSAs. And then you flood all those 30k LSAs to every router in the network.

    Just thinking of this makes me cry. :/
    (I once wrote flooding code for an OSPF implementation. It was my goal to allow as many LSAs in the network as possible. It requires a lot of effort to make that work. By doing this, I hoped to allow people to build larger single-area networks, without the complexity of multiple areas. Or, when not injecting large amounts of LSAs, the network would converge quicker. There are all kinds of benefits if the code works nicely. But never had I expected people to inject tens of thousands of extra LSAs, just to get a little traffic engineering).

    The BGP-solution has the benefit that you send all "traffic-engineered routes" only to the 1 router that needs to use those routes. And those routes don't spread further across the network. You also don't need to configure extra secondary IP-addresses on each interface or other stuff. It's also clear what TE-routes are advertised to what routers. With fibbing, you inject a LSA for prefix X, forwarding-address Y, but it is actually used only by router Z. I can see how troubleshooting fibbing can become a nightmare rather quickly.

    I prefer the BGP way. Or create a simple new protocol to do this. (Is the IETF really so slow, and vendors so unwilling, that this is not an option anymore ?). But in the mean time, I applaud all the experimentation with fibbing.
    Replies
    1. I agree with you that this is far from being perfect, and we're actually looking into what protocol extensions would be needed to make this much more efficient. We consider this more as an experiment to showcase that if you are able to manipulate the topology instead of the weights in a link-state protocol, you have a complete control on the used paths.

      Regarding the example about the number of LSA used, it is worth precising that you add these extra LSAs only for the prefixes that need to diverge from the original shortest-path tree.
      Then, only for these routers, you try to maximize the use of what we call the global lies (through e.g. the Merger algorithm in the paper), which enables you to change the selected next-hop for multiple routers at once with a single LSA -- all you need is to compute the metric for that LSA appropriately.
      And finally you use the locally scoped ones as last resort measure for the cases where using a global LSA (a T5 LSA with a forwarding address that is resolvable by everyone) can not be done without affecting neighbors as well.
      The best way to get a grasp of it is to run the algorithms with your requirements on a particular topology. The number of LSAs to flood is one of the reasons why we are looking into a protocol extension, as there are huge gains that can be made with simple changes (e.g. advertize mutliple prefixes in a single LSA, but without requiring these to be of different TOS classes as it is done with T5 LSAs).

      Finally, wrt. the BGP solution, our main difference is that since we are flooding the LSAs in the network we can change multiple next-hops through a single LSA, without directly connecting to the router itself. The 'clarity' is indeed something that can be disorienting, however all the Fibbing LSAs have the router-id set to the one of the Fibbing controller, so it's actually pretty easy to figure out if the router has been fibbed or not.
  3. Every clever idea implemented in the network adds extra time for debugging future issues :) Okay, to be fair, this applies to BGP-based solution(s) as well.

    I definitely love the flexibility of the solution, and the fact that the proposal could be implemented without modifying the existing protocol. However, the is still some hackery involved, not to mention the amount of state injected in the network. Being clever and original most often is a bad thing in production systems :( Does not sound like fun, but that's how it is...

    Alas, the idea only works for OSPF (btw we briefly discussed this with Laurent), which limits the applications. In my memory, OSPF implementations usually were the buggiest among generally known routing protocols too, but YMMV. BGP/RCP based models could apply to practically any existing network, since BGP is so widespread these days (OK, maybe except the home routers lol).

    And regardless of the underlying implementation, one better be 110% sure the centralized backend is well tested and has good tooling ecosystem around it... :P
Add comment
Sidebar