-
Notifications
You must be signed in to change notification settings - Fork 2k
Rough sketch of a possible FIB modularization
##- 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.
Uncommon Addressing 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) | |
| | | Signal RRP to discover route to o | | | |
| | | unreachable destination | | | | |
| | V Reply next hop | | | | |
| | +----+--------------+------------+ address | | | | |
| | | | | or unreachable | | | | |
| | | | Reactive Routing Protocol | | | | | |
| | | | (RRP) | | | | | |
| | | | | | | | | |
| | | +---------------------------+ | | | | |
| | | | | | | | | |
| | | | Routing Protocol | +-------------------------------------------+ | | | |
| | | | (RP) | | | | | |
| | | | | | | | | |
| | | +---------------------------+ | | | | |
| | | | | | | | |
| | | Routing Information Base | | | | | |
| | | (RIB) | | Value RP | | | |
| | | | | Request decision favorites | | | |
| | +--+-----------------------------+ | on collision V | | |
| | | | +-------------------+-+ | | |
| | | Insert most profitable | +-------->+ RP Preference Table | | | |
| | | next hops | Request next hop | +---+-----------------+ | | |
| | V V o | 1 | RP | | | |
| | +-+---------------------------------+----------------------+-+ +---------------------+ | | |
| | | | | 2 | RRP | | | |
| | | Forwarding Information Base | +---------------------+ | | |
| | | (FIB) | | | | | | |
| | | | | | | | | |
| | +--------------+------------------------------------+--------+ | | |
| | | | | | |
| | | Maintain individual FIB tables | | | |
| | V V | | |
| | +--------------+----------------+ +---------------+---------------+ | | |
| | | FIB table RP IF 0 | | FIB table RRP IF 1 | | | |
| | +------+-------------+----------+ +------+-------------+----------+ Send packet to | | |
| | | IP 6 | Link Local | Lifetime | | IP 6 | Link Local | Lifetime | 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-