doc/guides/prog_guide/rib_lib.rst

   1 ..  SPDX-License-Identifier: BSD-3-Clause
   2     Copyright(c) 2021 Intel Corporation.
   3
   4 RIB Library
   5 ===========
   6
   7 The Routing Information Base (RIB) library provides a data store for routing information.
   8 This library is intended for use in control or management plane applications.
   9 There are more suitable libraries for use in data plane applications such as
  10 :doc:`lpm_lib` or :doc:`fib_lib`.
  11
  12
  13 Implementation details
  14 ----------------------
  15
  16 RIB implements a key-value store for routing information.
  17
  18 Routing information is represented by a prefix (key) and a next hop ID (value).
  19 The 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.
  21 Next 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
  30 Internally 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
  38 The 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
  45 RIB API Overview
  46 ----------------
  47
  48 RIB 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
  55 The 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
  69 Given a RIB structure with the routes depicted in :numref:`figure_rib_internals`,
  70 here 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
  78 This 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
  86 This 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
  92 This 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
 104 This returns 3 ``rte_rib_node`` nodes pointing to ``10.0.0.0/29``, ``10.0.0.160/27``
 105 and ``10.0.0.128/25``.
 106
 107
 108 Extensions usage example
 109 ------------------------
 110
 111 Extensions can be used for a wide range of tasks.
 112 By default, an ``rte_rib_node`` node contains only crucial information such as the prefix and
 113 next hop ID, but it doesn't contain protocol specific information such as
 114 metrics, administrative distance and other routing protocol information.
 115 These examples are application specific data and the user can decide what to keep
 116 and how it is stored within the extension memory region in each ``rte_rib_node``.
 117
 118 It is possible to implement a prefix independent convergence using the RIB extension feature.
 119 If the routing daemon can provide a feasible next hop ID along with a best (active) next hop ID,
 120 it is possible to react to a neighbour failing relatively fast.
 121 Consider a RIB with a number of routes with different next hops (A and B) as
 122 shown in :numref:`figure_rib_pic`. Every route can have a feasible next hop
 123 provided by the routing daemon.
 124
 125 .. _figure_rib_pic:
 126
 127 .. figure:: img/rib_pic.*
 128
 129    RIB prefix independent convergence
 130
 131 In case of a next hop failure, we need to replace an active failed next hop with a
 132 feasible next hop for every corresponding route without waiting for the routing daemon
 133 recalculation process to complete.
 134 To achieve this we can link all existing routes with the same active next hop in a linked list,
 135 saving 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);