1.. SPDX-License-Identifier: BSD-3-Clause 2 Copyright(c) 2021 Intel Corporation. 3 4Routing Information Base (RIB) Library 5====================================== 6 7The Routing Information Base (RIB) library provides a data store for routing information. 8This library is intended for use in control or management plane applications. 9There are more suitable libraries for use in data plane applications such as 10:doc:`lpm_lib` or :doc:`fib_lib`. 11 12 13Implementation details 14---------------------- 15 16RIB implements a key-value store for routing information. 17 18Routing information is represented by a prefix (key) and a next hop ID (value). 19The prefix type depends on the address family. IPv4 addresses are represented by 20``uint32_t`` values. IPv6 addresses are represented as ``uint8_t[16]`` values. 21Next hop IDs are represented by ``uint64_t`` values. 22 23.. note:: 24 25 The API and implementation are very similar for IPv4 ``rte_rib`` API and IPv6 ``rte_rib6`` 26 API, therefore only the ``rte_rib`` API will be discussed here. 27 Everything within this document except for the size of the prefixes is applicable to the 28 ``rte_rib6`` API. 29 30Internally RIB is represented as a binary tree as shown in :numref:`figure_rib_internals`: 31 32.. _figure_rib_internals: 33 34.. figure:: img/rib_internals.* 35 36 RIB internals overview 37 38The binary tree consists of two types of nodes: 39 40* Actual Routes. 41 42* Intermediate Nodes which are used internally to preserve the binary tree structure. 43 44 45RIB API Overview 46---------------- 47 48RIB has two configuration parameters: 49 50* The maximum number of nodes. 51 52* The size of the extension block within each node. This space is used to store 53 additional user defined data. 54 55The main methods within the ``rte_rib`` API are: 56 57* ``rte_rib_insert()``: Add new routes. 58 59* ``rte_rib_remove()``: Delete an existing route. 60 61* ``rte_rib_lookup()``: Lookup an IP in the structure using longest match. 62 63* ``rte_rib_lookup_exact()``: Lookup an IP in the structure using exact match. 64 65* ``rte_rib_lookup_parent()``: Find a parent prefix within the structure. 66 67* ``rte_rib_get_nxt()``: Traverse a subtree within the structure. 68 69Given a RIB structure with the routes depicted in :numref:`figure_rib_internals`, 70here are several usage examples: 71 72* The best route for ``10.0.0.1`` can be found by calling: 73 74.. code-block:: c 75 76 struct rte_rib_node *route = rte_rib_lookup(rib, RTE_IPV4(10,0,0,1)); 77 78This returns an ``rte_rib_node`` pointing to the ``10.0.0.0/29`` prefix. 79 80* To find an exact match route: 81 82.. code-block:: c 83 84 struct rte_rib_node *route = rte_rib_lookup_exact(rib, RTE_IPV4(10,0,0,128), 25); 85 86This returns an ``rte_rib_node`` pointing to the ``10.0.0.128/25`` prefix. 87 88.. code-block:: c 89 90 struct rte_rib_node *route = rte_rib_lookup_exact(rib, RTE_IPV4(10,0,0,0), 24); 91 92This returns ``NULL`` as no exact match can be found. 93 94* To retrieve a group of routes under the common prefix ``10.0.0.0/24`` 95 (yellow triangle in :numref:`figure_rib_internals`): 96 97.. code-block:: c 98 99 struct rte_rib_node *route = NULL; 100 do { 101 route = rte_rib_get_nxt(rib, RTE_IPV4(10,0,0,0), 24, route, RTE_RIB_GET_NXT_ALL); 102 } while (route != NULL) 103 104This returns 3 ``rte_rib_node`` nodes pointing to ``10.0.0.0/29``, ``10.0.0.160/27`` 105and ``10.0.0.128/25``. 106 107 108Extensions usage example 109------------------------ 110 111Extensions can be used for a wide range of tasks. 112By default, an ``rte_rib_node`` node contains only crucial information such as the prefix and 113next hop ID, but it doesn't contain protocol specific information such as 114metrics, administrative distance and other routing protocol information. 115These examples are application specific data and the user can decide what to keep 116and how it is stored within the extension memory region in each ``rte_rib_node``. 117 118It is possible to implement a prefix independent convergence using the RIB extension feature. 119If the routing daemon can provide a feasible next hop ID along with a best (active) next hop ID, 120it is possible to react to a neighbour failing relatively fast. 121Consider a RIB with a number of routes with different next hops (A and B) as 122shown in :numref:`figure_rib_pic`. Every route can have a feasible next hop 123provided by the routing daemon. 124 125.. _figure_rib_pic: 126 127.. figure:: img/rib_pic.* 128 129 RIB prefix independent convergence 130 131In case of a next hop failure, we need to replace an active failed next hop with a 132feasible next hop for every corresponding route without waiting for the routing daemon 133recalculation process to complete. 134To achieve this we can link all existing routes with the same active next hop in a linked list, 135saving the feasible next hop ID and a pointer inside the extension space of each ``rte_rib_node``. 136 137.. code-block:: c 138 139 struct my_route_ext { 140 struct rte_rib_node *next; 141 uint64_t feasible_nh; 142 }; 143 144 struct rte_rib_conf conf; 145 conf.ext_sz = sizeof(struct my_route_ext); 146 rib = rte_rib_create("test", 0, &conf); 147 ... 148 /* routing daemon task */ 149 struct rte_rib_node *route = rte_rib_insert(rib, RTE_IPV4(192,0,2,0), 24); 150 rte_rib_set_nh(route, active_nh_from_rd); 151 struct my_route_ext *ext = rte_rib_get_ext(route); 152 ext->feasible_nh = feasible_nh_from_rd; 153 list_insert(nh_table[active_nh_from_rd].list_head, route); 154 ... 155 /* dataplane monitoring thread */ 156 /* nexthop id fail_nh fails */ 157 route = NULL; 158 do { 159 route = get_next(nh_table[fail_nh].list_head, route); 160 uint32_t ip; 161 uint8_t depth; 162 rte_rib_get_ip(route, &ip); 163 rte_rib_get_depth(route, &depth); 164 ext = rte_rib_get_ext(route); 165 uint64_t new_nh = ext->feasible_nh; 166 /* do update to the dataplane, for example to the fib */ 167 rte_fib_add(fib, ip, depth, new_nh); 168 /* update nexthop if necessary */ 169 rte_rib_set_nh(route, new_nh); 170 } while (route != NULL); 171