FIB redesign

Development archive
#1

Hi Martin,

thanks for the initial wiki input on the topic (i.e. https://github.com/RIOT-OS/RIOT/wiki/Rough-sketch-of-a-possible-FIB-modularization).

I briefly scanned though it, and I have two quick questions for starters:

  • the way I read it, the current content aims at some sort of list of requirements, and a description the current FIB design in RIOT, right?

  • more in particular: it does not contain so far any concrete proposal for a FIB redesign. Am I correct?

Best,

Emmanuel

#2

Hi Emmanuel, hi all,

  • the way I read it, the current content aims at some sort of list of requirements, and a description the current FIB design in RIOT, right? right, somehow. It figures the problematic areas that have to be handled for a clean interaction as sketched in the diagram.
  • more in particular: it does not contain so far any concrete proposal for a FIB redesign. Am I correct? Yes and no, the diagram at the bottom should give a conceptual overview how the interaction of the FIB in the RIOT context finally could be. It does not reflect anything present RIOT. I didn’t wanted to go to much into possible implementation details, as long as the concept is not considered as sane.

The FIB itself will be a lightweight “interface” providing access and manipulation decoupling the data, i.e. FIB tables, from the routing protocols (or RIB). The FIB table will provide a generalized data management/structure. I updated the page with a concept of a FIB table data overview. This should allow to take advantage of non IP addressing. The access functions as sketched from RIB and RIOT processes will provide a KISS and clean interface. For instance just add(...) remove(...) and update(...) from RIB side and get_next_hop(...) from a RIOT process. The dispatching on FIB table entries and weight of them over others on collisions happens behind the FIB-“wall”.

If this sounds sane, I could provide some code till mid/end of this week reflecting the FIB tables and FIB-“wall”.

Best Regards, Martin

#3

Hi, I finally came to it to read your suggestions, too. Regarding the fact that you keep 6LoWPAN header compression in mind, too: Are you planning to only consider stateless compression (Prefix is assumed link-local) or also stateful compression (Prefix is determined by a 4-bit context ID [1], disseminated through the PAN via the context identifier option in RS [2]). Since Neighbor Cache [3], Prefix Information [4], Forwarding information, and Context Information are all very related, and we may want to save memory, we might want to consider to put those information into the same data structure (so the later of my 2 suggestions above would be). Keep in mind though, that both Prefix Information Base and Context information Base have their own lifecycles (see regarding RFCs).

Also: have you considered Mesh-under routing [5]? (Do we have to consider this here I wonder myself? We don’t have support for it anyways, so far.) [6] states some requirements for this.

Hope this was more helpful, than confusing ;-).

Cheers, Martine

[1] https://tools.ietf.org/html/rfc6282#section-3.1.2 [2] https://tools.ietf.org/html/rfc6775#section-4.2 [3] http://tools.ietf.org/html/rfc4861#section-5.1

#4

Hi Martine,

thx for the input :slight_smile:

> Are you planning to only consider stateless compression (Prefix is assumed link-local) or also stateful compression (Prefix is determined by a 4-bit context ID [1] ...

I plan to make it more generic, e.g. allow for providing even proprietary "solutions" for FIB table entry compression. LOWPAN_IPHC provides wonderful mechanisms to save bytes in transmissions, but there are probably (most likely) more possibilities to save bytes on the individual nodes RAM when maintaining a FIB table. Eventually the FIB will "resolve" the applied compression to provide the type required by a `get_next_hop()` request.

>... we might want to consider to put those information into the same data structure (so the later of my 2 suggestions above would be)

Indeed, that would by great. That's the reason I want to outsource the "Generic address" from the FIB table entry. These blobs can be shared among processes, e.g. FIB, routing protocol and ND. Liftime invalidation and such is controlled by the individual process. For instance, an expired FIB table entry would mark its internal structure as invalid and decrease the usecount of the "Generic address".

> Also: have you considered Mesh-under routing [5]? (Do we have to consider this here I wonder myself? We don't have support for it anyways, so far.) [6] states some requirements for this.

No, I only considered to "play" at the network layer level for now. But I will have a look.

Best Regards, Martin

Hi, I finally came to it to read your suggestions, too. Regarding the fact that you keep 6LoWPAN header compression in mind, too: Are you planning to only consider stateless compression (Prefix is assumed link-local) or also stateful compression (Prefix is determined by a 4-bit context ID [1], disseminated through the PAN via the context identifier option in RS [2]). Since Neighbor Cache [3], Prefix Information [4], Forwarding information, and Context Information are all very related, and we may want to save memory, we might want to consider to put those information into the same data structure (so the later of my 2 suggestions above would be). Keep in mind though, that both Prefix Information Base and Context information Base have their own lifecycles (see regarding RFCs).

Also: have you considered Mesh-under routing [5]? (Do we have to consider this here I wonder myself? We don't have support for it anyways, so far.) [6] states some requirements for this.

Hope this was more helpful, than confusing ;-).

Cheers, Martine

[1] https://tools.ietf.org/html/rfc6282#section-3.1.2 [2] https://tools.ietf.org/html/rfc6775#section-4.2 [3] http://tools.ietf.org/html/rfc4861#section-5.1 [4] https://tools.ietf.org/html/rfc4861#section-4.6.2 [5] https://tools.ietf.org/html/rfc4944#section-11 [6] http://tools.ietf.org/html/rfc6606

Attached Message Part (135 Bytes)

#5

Hi all,

I started a prototype implementation [1] under consideration of the diagram on the wiki page [2].

  • It provides a generic address handling and access
  • a basic FIB table management (add, remove, update)
  • collision detection for next_hops and resolving the conflict based on a preference table
  • reactive RP signalling using msg_send_receive()

This prototype is not included between any RP and the get_next_hop() right now.

Best regards, Martin

[1] git pull add_fib [2]

#6

Hi Martine & Martin,

following a personal discussion, the approach of multiple FIB tables (per IF / protocol) is off the table, now. There will and can be only one FIB.

Important for the next steps are discussion and conclusion about a viable (internal) data structure for the FIB ... it seems there are trade-offs between memory and processing constraints. Marin shall present proposals for a thorough review discussion soon.

Cheers,

Thomas

#7

Hi Martin, now that I’m in the refactoring of IPv6 I have some suggestions/considerations:

  • considering the current refactoring of the network stack to PID-based identification of a network layer / protocol shouldn’t iface_id in https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/include/fib/fib.h#L80 et.al be of type kernel_type_t? Interface IDs as with the current net_if module will still be available, since they are “useful waste” from my reworked ipv6_if implementation (they are the indices of the buffer array where I store the (mac_pid, IP addresses) tuples), but maybe we don’t want to use those in the future publicly anymore. … On the other hand, if we find that a single-threaded network stack is superior to our current approach (part of my master thesis ;-)), we might have to rethink that again, hmmmm. Sorry, this bullet point is more loud thinking than suggesting ^^"
  • Shouldn’t https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/include/fib/fib.h#L119 return the iface_id too? The IP layer needs to now which MAC layer it has to give the packet and this information is not encoded in the address. If I find more, I’ll let you know

Cheers,

Martine

#8

Hi Martine,

I will change the interface and protocol IDs to kernel_type_t as you suggested. For the FIB handling perspective this seems also to be the best (and easiest) way to have the IDs unique on one RIOT/node.

Shouldn’t https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/include/fib/fib.h#L119 return the iface_id too?.. absolutely. It just slipped through somehow.

thx for your input.

Best regards, Martin

#9

Hi Martin,

#10

Hi Martine,

… Except you mean the routing protocol by this. yes, the prot_id is the actual used (running) protocol, i.e. RPL. This identifier must be unique for the running RIOT on the node, i.e. arbitrary but fixed for the lifetime.

The “binding” of FIB table entries to a specific (running) protocol is necessary only for updates on them.

Probably kernel_pid_t for the would be a waste of one byte for each FIB table entry. I will keep it uint8_t for now, but test a bit with kernel_pid_t.

Best regards, Martin

#11

Hi, it’s me again, dumping my latest brainstorm into the thread :D.

Don’t we need some kind of priorities for the routing protocols, too? Or how does the FIB decide which next hop to choose if more than routing protocol made an entry pointing to it?

Cheers, Martine

#12

Hi Martine,

a FIB always only provides unique forwarding rules. So there are no priorities attached to FIB entries. Priorities of routes may occur in RIBs associated with routing protocols ... and a significant question is of course how to deal with competing routing protocols that feed the FIB. (Typically, these routing protocols split horizon according to IP address ranges.)

Still, a routing protocol either overrides FIB entries or it doesn't.

Cheers,

Thomas

#13

Hi all,

> a significant question is of course how to deal with competing routing protocols Form my understanding we have two distinct directions we can choose to approach the problem:

1. We strictly push it away from the FIB, i.e. only allowing to have unique entries for each global prefix.      pro: no handling needed here, the process, e.g. routing protocol, adding next hops to the FIB must care about this.      con: we loose the possibility to take link/topology/interface capabilities into account to forward a packet

2. We allow competing entries and apply (sort of) policies to always return a unambiguous next hop from the FIB.      pro: we are able to direct data and control plane flows, taking the routing protocol capabilities into account.      con: to have a preference on one FIB entry over another competing entry, requires a valuing weighting              and decision mechanism. This creates overhead and lowers the lookup/response time on next hop requests.

> Typically, these routing protocols split horizon according to IP address ranges Using a separation on IP address ranges would shift the problem away from the FIB to the RIB. This approach is definitely useful on non-moving routers with an organized and static hierarchy and a good argument for following 1.

But I think in some IoT scenarios with moving routers, this approach might have a poor performance when the connected networks between the IoT routers periodically change.

> how does the FIB decide which next hop to choose if more than routing protocol made an entry pointing to it? I've built in [1] to the FIB to provide an entry point to handle such conflicts.

Best Regards, Martin

[1] https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/network_layer/fib/fib.c#L260

#14

Hi again,

I included the FIB to `RIOT/net/sixlowpan/ip` replacing `ip_get_next_hop()` by the FIB one. Additionally I edited RPL to feed/update the FIB with the preferred parent. (I set `23` arbitrary for the protocol ID and 0 for the interface.)

Best regards, Martin

[1] https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/network_layer/fib/fib.c#L354