On Definitions: Whatever is Forwarding Information?

After last week’s, a reader left a comment noting “I2RS doesn’t manipulate forwarding data.” If I2RS isn’t “manipulating forwarding data,” then what, precisely, is it doing? I thought it’s worth a post to try and help folks understand the definitions in this space—except, as you’ll soon discover, there are no definitions here. In fact, it’s almost impossible to create a single set of definitions that will clarify the issues involved in understanding the various sorts of state in a network device. The following illustration might be helpful in trying to understand the vagaries of the various kinds of state, and the confusion that results from the various names used in different places.

device-model-definitions

It would be “nice” to say something like: information held in the forwarding table, that’s actually used to forward traffic through the router, is the only real “forwarding data.” This makes for a nice clean definition that clearly separates, say, what the RIB does and what the FIB does in most of the hardware based switching devices produced today. There are two problems with this clean definition, however.

First, there are, and always will be, devices produced that simply don’t have a forwarding table. Instead of a forwarding table, such devices use the routing table directly to look up forwarding information. A cardinal instance is a software based mobile device that simply doesn’t forward enough traffic to justify a separate hardware set for switching packets. The WiFi router in your house is probably an example.

Well… We could just say, “these devices have a faux FIB, kindof embedded in the RIB.” But is this really useful? Now devices with hardware forwarding have a FIB, and devices without have a virtual FIB that’s there just to make our definition work all the time. This suddenly doesn’t seem very clean.

Second, what is IS-IS doing if it’s not carrying forwarding information? We could say it’s just a link state distribution protocol, but it’s doing more than just distributing information—it’s also calculating shortest/loop free paths through the topology to specific reachable destinations. That changing the protocol can change the shortest/loop free paths illustrates that the protocol isn’t just carrying information. Rather, it’s actually building at least part of the information needed to forward packets—the shortest path isn’t calculated in the RIB.

Third, this definition sets up a nice clean separation between the RIB and the FIB, but it produces a lot of ambiguity between the routing protocols and the various configurations held in other places in the system. The canonical case is the humble static route: is this configuration, or is it forwarding state? Should information sent to an I2RS agent located on a device be processed through the device configuration manager because “it’s just like a static route?” I would argue this is a huge mistake, but what justification could I give if the only true forwarding state on a device is the FIB (which doesn’t, remember, actually exist on all forwarding devices)?

We’ve run into a thicket, as we normally do when trying to create nice clean definitions. How can we resolve these problems?

The problem here is a set description issue—we’re trying to describe self contained sets in imprecise terms. Does “forwarding data” mean only and all the data used to actually forward packets? Is the BGP table, or the IS-IS LSDB, for instance, somehow related to the forwarding of packets?

There is really only one solution here: narrow the definition of a normally broader term, creating a “technical term” that has a narrower meaning in a specific context. There is no clean way to do this, of course, because everyone has a different model in their heads, everyone has a different way of looking at the problem, and there will always be cases that just don’t fit.

But—for the sake of this blog (and for my sanity! 🙂 ), I’m going to use the terms like this:

  • forwarding state: The information carried in the forwarding table actually used to switch packets. This would normally be in the FIB, but could sometimes (in some implementations) be in the RIB, as well. There is no “virtual FIB” anyplace, there are just devices without FIBs that keep their forwarding state mixed with their routing state (see below).
  • routing state: The set of (hopefully) loop free paths resulting after arbitration by the RIB across the routing information injected by routing protocols, static configuration (like static routes), and other information sources (as supported by any individual implementation).
  • forwarding information: Any information which contributes to the building of the routing and/or forwarding state, as defined above. This would include information injected by I2RS, a distributed routing protocol of any sort, etc.

The differentiation between state and information is an artificial one that cannot be defended from the raw meanings of the words; hence everyone might not agree with the definitions I’ve outlined here. But—and this is a huge but—we must be able to differentiate between these various kinds of information/data/state if we’re going to have a discussion around how control planes and forwarding devices actually work. If we fail too connect the loop free paths a routing protocol calculates—no matter how it calculates said paths—to the creation of routing state, and hence to forwarding state, then we have missed a crucial piece of the overall system, and I2RS itself will be difficult to understand (or rather, will end up being “just another configuration protocol”—precisely the problem the working group faces on a regular basis).

Again, these aren’t perfect, but I think them useful. There is still a term that means, “this is what is actually used to forward the packet,” but there is also still a term that means, “this information is not configuration (though it might be derived from configuration), but is used primarily for the purpose of calculating forwarding state.”

Next time I’ll return the main series, specifically considering the answer to the question I left of with last time—the speed question.

6 Comments

  1. David on 5 September 2016 at 2:33 pm

    Lightweight devices might not have dedicated FIB implemented in hardware but they are still not using the RIB to forward the packets. They are going to use the kernel which we could argue acts as a sort of software FIB. That is if they are using Linux but who is not using it nowadays? 🙂



  2. Russ on 6 September 2016 at 9:29 am

    David — thanks for stopping by! I know of devices that are very light weight that do not, in fact, use Linux, but rather custom operating systems designed just for that device, and hence forward directly out of the RIB. Think smaller, as in IoT and handheld radio sorts of devices. If you turn off fast cache in an older software only Cisco router, and even in old Wellfleet and others, or look at the “process switched path” in many devices, they hit the RIB directly for forwarding information as well.

    Even if there are no devices anywhere without a FIB of some sort, this still doesn’t mean the RIB no longer holds information about destinations and next hops — in essence, forwarding information of some sort. The problem I see is once you kick the RIB out of “forwarding information,” there’s no way to describe what’s in there. A database? But this describes the FIB as well as the RIB, and every other table in the device; describing what it is, is different than describing what it contains.

    This isn’t an easy problem; our language is too imprecise in this area to differentiate between “information actually used to forward a packet,” and “information used to build the information that’s used to forward the packet.”

    🙂

    Russ



  3. Jeff Tantsura on 6 September 2016 at 3:01 pm

    The reader strikes back 😉

    First of all – For sake of this discussion, I don’t think presence of HW FIB on a device makes any difference, RIB and FIB are functional blocks, not pieces of HW, if it is a bottom part of RIB with some metadata indicating that those prefixes with their attributes are to be used for forwarding, so be it.
    E.g – ovs keeps its FIB in ovs-vswitchd memory space, how is it different from LC CPU or NPU?

    Routing protocols don’t distribute forwarding state, but link state, if I apply Steiner rather than Dijkstra on the same dataset (distributed by a routing protocol) my forwarding would look different.

    So why don’t we use 10+ years old definition:
    RIB – holds best routes from every source and is responsible for the arbitration in case there are more than 1, it might also be the place where additional metadata is added, ie backup routes/etc
    FIB – holds the best route to a destination (or more complicated data structure in case of src/dst routing)

    Let’s take ECMP as an example:
    RIB (often implemented as a radix) would have dst reachable over n paths of equal cost, however not how different flows toward the dst will be placed
    FIB (often implemented as mtrie) would have forwarding context, ie how a flow (key hashed) would be placed, ie src1->dst is different that src2->dst (or whatever key it uses for hashing)

    Hope this makes sense and clarifies my previous points (and you know – how much I love arguing with you :-))

    P.S the world has really changed since IOS’s “creating the fib” story 😉

    Yours



    • Russ on 6 September 2016 at 10:55 pm

      Jeff — I figured the reader would strike back. 🙂 Let me first say this — this isn’t a matter of disagreement, but of what we call things… We all agree there are tables of this sort and that, etc., the only real question is what to call them. So I would say that to some degree we’re discussing the meanings of words, and the solution is always going to turn out to be arbitrary to at least some degree.

      Now, to respond specifically — “Routing protocols don’t distribute forwarding state, but link state, if I apply Steiner rather than Dijkstra on the same dataset (distributed by a routing protocol) my forwarding would look different.” Two points — last I looked, BGP, EIGRP, OSPF (ABR-ABR), BABEL, and many others are still “routing protocols,” even though they don’t carry “link state information.” Second, last I looked, Dijkstra is actually specified in the IS-IS and OSPF protocol specifications to find the shortest path to a destination — not just through a graph. The shortest path to a destination is, in fact, information on how to forward through the network, not just a “database entry.”

      The problem here is that you’re trying to define the terms based on what they are actually used for right now, and I’m trying to point out that the intent of the information is important, as well. A credit card number doesn’t magically become a credit card number “only when I use it as such;” it is always a credit card number. Sometimes it’s used, and sometimes it’s not. This is why I use the terms “state” and “information:” this is what is being used right now (state),” “this is what this information is intended to be used for (information).” Again, it’s not perfect, but it’s better than saying, “a RIB entry has no intent or meaning until it’s used to actually forward packets.”

      The ECMP example is illustrative, in fact, because in many systems the actual placement of the flow is calculated using a hash across fields in the packet itself as the packet is being switched. If we use this example, the FIB isn’t forwarding information, either, because packets cannot be forwarded based on the FIB alone. Instead, the actual forwarding state is calculated on the fly as packets are switched, and doesn’t survive once the switching process is completed. Hence, in the strict application of the definition “forwarding information/state/data only exists when it’s used to forward a packet, and at no other time,” there is not “table” or “base” of forwarding information in any device that does ECMP — it’s all ephemeral, computed on the fly during the switching process. Here the FIB is no more “forwarding information” than the RIB.

      Clearly this definition doesn’t work — we need something that describes both what the information is intended to be used for, and something to describe which information is actually being used. I’ve proposed “information” and “state” to differentiate between these two sets of meanings — I know they’re not perfect, but it’s a start.

      🙂

      Russ



  4. Jeff Tantsura on 7 September 2016 at 3:34 am

    Russ,
    Sure, it is always the terminology. Going to to the original topic – I2RS, I think we need a better name than “forwarding data manipulation”, I presume – we both agree that it is not what it does, perhaps partially.

    Looking forward to meeting you later this week

    Jeff



    • Russ on 7 September 2016 at 9:54 am

      Jeff —

      Hmmm… It’s inserting forwarding stuff into the RIB that’s supposed to/potentially can impact forwarding… And it can do so in response to changes in the topology, existing routes, etc. I guess you could say “inserting routing information,” but a “route” is a “forwarding path,” so I don’t know if that’s any better. I would say I2RS deals with/manages forwarding information, rather than forwarding state — as forwarding state is calculated for each device (whether remotely or locally) on a per device basis…

      It’s tough to put words on this — but I’ll try to be careful to use “forwarding information” or “routing information” rather than “forwarding state” here when discussing I2RS.

      🙂

      Russ