FIB - Forwarding Information Base - Routes are organized in routing tables - For "fib_hash" algorithm routing tables have 33 zones (for prefix lengths 0..32), routing lookup walks them from 32 to 0 to find a node containing all routing information - Zones are implemented as hash tables where nodes are hashed by key (prefix=network) because there can be lots of prefixes in a zone. - Nodes can be stored with other methods, eg. trie, where nodes are searched (we hope faster) by prefix and length, no zones are used in this case - Nodes have a list of aliases (tos+type+scope+fib_info ptr) sorted by decreasing TOS because TOS=0 must be a last hit when looking for route, TOS 0 matches packet with any TOS. type is unicast, local, prohibit, etc. scope is host, link, etc. Additionally, aliases with same TOS are sorted by fib_info priority (ascending). - fib_info is a structure containing protocol (kernel, boot, zebra, etc), prefsrc, priority (metric), metrics, nexthop(s). Fallback routes have higher value for priority, they are used if more priority routes disappear or their nexthops are dead. - fib_info structures are organized in 2 global hash tables, one keyed by prefsrc and another by nexthop_count+protocol+prefsrc+priority - fib_info is a shared structure, different aliases can point to same fib_info, even aliases from different prefixes, from different routing tables. By this way if fib_info contains multipath route then many aliases share same route path scheduling context. - Nexthop contains gateway, output device, scope and weight. Weight is used for path scheduling where nexthops have relative priority compared to other nexthops in multipath route. - There can be many aliases with same tos, there can be alternative routes (aliases) with same tos and priority (metric) but only one alias with particular tos, type, scope and fib_info can exist to avoid duplicate alternative routes. - The operation to replace route includes replacing of alias. The alias in node (table -> prefix/len) is matched by tos and fib_info priority and they can not be changed. The parameters that are changed are type, scope and fib_info (except priority). - The 'ip' tool maps route operations to NLM_F_* flags as follows: - ip route add -> NLM_F_CREATE | NLM_F_EXCL - add unique route - ip route change -> NLM_F_REPLACE - change existing route - ip route replace -> NLM_F_CREATE | NLM_F_REPLACE - change existing route or create new route - ip route prepend -> NLM_F_CREATE - create new alternative route as first - ip route append -> NLM_F_CREATE | NLM_F_APPEND - create new alternative route as last - ip route test -> NLM_F_EXCL - check if route exists - By default, 'ip route add' adds no more than one route for particular prefix/len, tos and fib_info priority. This is guaranteed by the NLM_F_EXCL flag. Extension to this rule is the support for alternative routes where 'ip route prepend' and 'ip route append' which avoid the NLM_F_EXCL flag and allow many routes for prefix/len, tos and fib_info priority to be added. Still, there should be no more than one alternative route with same prefix/len, tos and all remaining fib_info parameters. - As for the 'route' tool, it works just like 'ip route prepend' which allows alternative routes to be created. - Additionally, the IP stack can automatically add local or broadcast 'proto kernel' routes when IP address is added and unicast subnet route when primary IP address for subnet is added. The routes are created in the 'ip route append' way in local or main table. FIB tree: * routing table * node (prefix/len) * alias (tos, type, scope) -> fib_info (priority, protocol, prefsrc, metrics) * nexthop (gateway, outdev, scope, weight) - one or many routing tables with fast access to multiple nodes, each node has list with aliases with unique parameters sorted by decreasing tos and increasing priority.