Rough sketch of a possible FIB modularization

Possible future FIB modularization concept for RIOT

##- things to handle - Reactive Routing Protocols
Unlike proactive routing protocols like OSPF, Reactive RPs (RRP) need to be signaled to start filling its routing tables and eventually the FIB on demand, whenever a route to a destination is required.
All nodes store the individual next hop information corresponding to each flow for data packet transmission.

A further reactive approach for routing in the wireless ad-hoc network category is the Dynamic Source Routing (DSR). DSR does not require routing tables on all intermediate nodes for creating routes. It uses source routing to set a route to a given destination.
If a node learns a route to a destination, it caches the complete path, i.e. all intermediate next hop node addresses, to it. This may require a large amount of information to be stored for an active route on each node. In addition, the learned "next hops" do not represent the neighbours of the node, so the learned information should not be stored in a FIB requested for next hops by the OS. Hence, a FIB table structure marked for a specific data flow transmission can be used to represent the cache for the DSR node.

The conceptual design of the interacting RIB and FIB components has no sufficient entry points to embed RRPs. The design suits proactive protocols, where the RP individually discovers routes to provide the FIB with learned next hops.
To embed a RRP into this structure, the concept and the OS has to be enhanced with a feedback line to signal the embedded RRP whenever the FIB cannot provide a next hop towards a destination. The signaling will cause the RRP to start a route discovery and fill the FIB with an appropriate next hop.

FIB tables
As IoT nodes are assumed to provide a certain amount of mobility, letting the node to allocate memory dynamically for FIB entries during runtime amplifies the risk of resulting in insufficient remaining RAM for operating. The maximum amount of provided memory for FIB must be set during compile time by the developer to prevent risky situations.
Additionally mechanisms to reduce the number of bytes for FIB table entries must be applied, for instance as can be found in the 6LoWPAN header compression mechanism LOWPAN_IPHC. LOWPAN_IPHC provides a full set of mechanisms for reducing packet header sizes for 6LoWPAN transmissions, where some parts can be adopted and enhanced to reduce the required RAM for a FIB entry, e.g. eliding the network prefix using the Link Local address prefix.

While providing for compression mechanisms for FIB table entries using common shared properties like applied by LOWPAN_IPHC, distant unique and "non-compressable" entries, e.g. individual Internet hosts behind border routers, must be still address and reachable. When assuming a small number of such required routes to destinations, an extra FIB table for these entries with raw represented addresses and properties might be reasonable.

Multiple Interfaces
IoT nodes may provide a number of transmission IFs. The routing concept using RIB and FIB must provide a distinction on multiple IFs for transmissions and the possibility to merge/exploit all available communication mediums, e.g. to provide load balancing or efficient distinction on control and payload transmissions.

Mutiple Routing Protocols
Providing multiple RPs at the same time on a node could be used in combination with using all IFs to perform an efficient load balancing and energy saving transmission strategy. Choosing the routes and protocols in favor of others on preferences calculated on OS tracked quality observations may rise the performance of the overall network using multiple and distinct topologies.

An adoption of a Policy Based Routing (PRB) scheme could be applied to handle multiple protocols. Using PBR enables to set specific rules to be applied to find a route to a given destination.
An encapsulation of the next hop request with a PBR like rule based selection mechanism could resolve conflicting next hop results, whenever multiple RP/IF provide for a next hop to the requested destination.

(This is handled outside the FIB, i.e. by the RIB or a specific routing protocol)

Uncommon (generic) Address Types
All the above named properties and obstacles found in the combination of IoT node and FIB has been discussed on the background of IP based routing. The FIB for IoT nodes must implement robust and flexible interfaces to provide for non IP based address types.

The situation in RIOT
Currently RIOT directly accesses an registered RP to request a next hop for a destination. A differentiation of conceptual borders representing RIB/FIB are not present and the RP must provide all functionality of the components at once.
When initiating the RP, it registers a callback function in sys/net/network_layer/sixlowpan/ip.c::ipv6_iface_set_routing_provider().
This callback is used by the IPv6 process to request a next hop for a destination. The RP is responsible for all routing mechnisms including the memory management and FIB operation.

The following diagram sketches a conceptual overview of (most of) the introduced problem areas sperated into interacting modules with conceptual competence borders.

+------------------------------------------------------------------------------------------------------------+
|                                                                                                      Node  |
| +-+--------------------------------+---------------------------------------------------------------------+ |
| | +--------------------------------+                                              Operating System (OS)  | |
| | |    |                           |                                               O               +     | |
| | |    | Reactive Routing Protocol |                                               |               |     | |
| | |    |          (RRP)            |                                               |               |     | |
| | |    |                           |                                               |               |     | |
| | |    +---------------------------+                                Reply next hop |               |     | |
| | |    |                           |                                address        |               |     | |
| | |    |     Routing Protocol      |                                or unreachable |               |     | |
| | |    |           (RP)            |                                               |               |     | |
| | |    |                           |                                               |               |     | |
| | |    +---------------------------+                                               |               |     | |
| | |                                |                                               |               |     | |
| | |    Routing Information Base    |                                               |               |     | |
| | |              (RIB)             |   +-------------------------------------------+               |     | |
| | |                                |   |                                                           |     | |
| | +--+------------------------+----+   |                                                           |     | |
| |    |          signal RRP to ^        |                                                           |     | |
| |    |         discover route |        |                                                           |     | |
| |    |                        |        |                                                           |     | |
| |    |                        |        |                                                           |     | |
| |    |                        |        |                                                           |     | |
| |    |                        |        |                                                           |     | |
| |    |                        |        |                                                           |     | |
| |    | add/remove/update      |        |                                                           |     | |
| |    | next hop               |        | request next hop                                          |     | |
| |    V                        |        V                                                           |     | |
| |  +--------------------------+---------------------------------+                                  |     | |
| |  |                                                            |                                  |     | |
| |  |                 Forwarding Information Base                |                                  |     | |
| |  |                            (FIB)                           |                                  |     | |
| |  |                                                            |                                  |     | |
| |  +-----------------------------+------------------------------+                                  |     | |
| |                                |                                                                 |     | |
| |                                |                                                                 |     | |
| |                                |                                                                 |     | |
| |                                |                                                                 |     | |
| |                                V                                                                 |     | |
| |      +-------------------------+------------------------------+                   Send packet to |     | |
| |      |                      FIB table                         |                   next hop       |     | |
| |      +-------------+-----------+----------+--------+----------+              +-------------------+     | |
| |      | protocol ID | interface | lifetime | prefix | next hop |              |                   |     | |
| |      +--------------------------------------------------------+              |                   |     | |
| |      |             |           |          |        |          |              |                   |     | |
| |      |             |           |          |        |          |              |                   |     | |
| |      +             +           +          +        +          +              |                   |     | |
| |                                                                              V                   V     | |
| |                                                                 +----------------+   +---------------+ | |
| |                                                                 |                |   |               | | |
| +-----------------------------------------------------------------+  Interface 0   +---+  Interface 1  +-+ |
|                                                                   |     (IF 0)     |   |     (IF 1)    |   |
+-------------------------------------------------------------------+----------------+---+---------------+---+
                                                                                                              
                                                                                                              
Legend:                                                                                                       
-----> signal or request operation                                                                            
o----> request operation from -> to reply back to o-                                                          

FIB table - conceptual overview

As sketched above FIB tables are operated through the FIB "Interface" separating the data access from direct interaction from other conceptual modules. The following diagram sketches a possible data representation of a FIB table providing generic address types.

+--------------------------------------------------------------------------------+
|                                     FIB Table                                  |
+--------------------------------------------------------------------------------+
|    +---------------------+---------          ------+---------------------+     |
|    | FIB table entry 1   |                         | FIB table entry n   |     |
|    +---------------------+                         +---------------------+     |
|    | Protocol ID         |                         | Protocol ID         |     |
|    | Interface ID        |                         | Interface ID        |     |
|    | Lifetime            |                         | Lifetime            |     |
|    | global Type/Flags   |           ...           | global Type/Flags   |     |
| +--+ global address*     |                         | global address*     |     |
| |  | next hop Type/Flags |                         | next hop Type/Flags |     |
| |  | next hop address*   +--------+                | next hop address*   +--+  |
| |  +---------------------+---------          ------+---------------------+  |  |
| |                                 |                                         |  |
+--------------------------------------------------------------------------------+
  |                                 |                                         |   
  |                                 |                                         |   
  |                                 |                                         |   
  |  +---------------------+        |  +---------------------+                |   
  +->+ Generic address     |        +->+ Generic address     +<---------------+   
     +---------------------+           +---------------------+                    
     | Use count           |           | Use count           |                    
     | Address data length |           | Address data length |                    
     | address pointer*    +--+     +--+ address pointer*    |                    
     +---------------------+  |     |  +---------------------+                    
                              |     |                                             
                              |     |                                             
                              |     |                                             
                              |     |       +----------------+                    
                              |     |       | Address blob   |                    
                              |     |       +----------------+                    
                              |     +------>+ address data 1 |                    
                              |             +----------------+                    
                              +------------>+ address data 2 |                    
                                            +                +                    
                                                                                  
                                                                                  
                                            +                +                    
                                            |                |                    
                                            | address data n |                    
                                            +----------------+                    

The relationships are form top to bottom:

• The FIB table entries contain:
  • the Protocol ID identifying the protocol which recorded this entry,
  • the Interface ID identifying to which interface this entry belongs,
  • the Lifetime telling when this entry invalidates,
  • a Type/Flags field with information how the global address is being represented
  • the global address pointer to a structure containing the generic address data
  • a Type/Flags field with information how the next hop address is being represented
  • the next hop address pointer to a structure containing the generic address data
• The pointed Generic address structure(s) represent(s) an uniform Generic address type. This structure is available for being used by multiple sources, e.g. FIB, RIB and PR. Each "registration" on this generic type is saved by the Use count to keep track if the entry can be deleted/freed or marked as reusable data section.
• Additionally, it provides the Address data length of the used memory for the address data, and an address pointer pointing to the real data.