doc/guides/prog_guide/fib_lib.rst

   1 ..  SPDX-License-Identifier: BSD-3-Clause
   2     Copyright(c) 2021 Intel Corporation.
   3
   4 FIB Library
   5 ===========
   6
   7 The FIB library provides a fast Longest Prefix Match (LPM) search for 32-bit
   8 keys or 128-bit for IPv6. It can be used in a variety of applications,
   9 the most typical of which is IPv4/IPv6 forwarding.
  10
  11 .. note::
  12
  13    The API and implementation are very similar for IPv4 ``rte_fib`` API and IPv6 ``rte_fib6``
  14    API, therefore only the ``rte_fib`` API will be discussed here.
  15    Everything within this document except for the size of the prefixes is applicable to  the
  16    ``rte_fib6`` API.
  17
  18
  19 FIB API Overview
  20 ----------------
  21
  22 The main configuration struct contains:
  23
  24 * Type of :ref:`dataplane algorithm <fib_dataplane_algorithms>`.
  25
  26 * Default next hop ID.
  27
  28 * The maximum number of routes.
  29
  30 * Settings for the data algorithm (:ref:`will be discussed later <fib_dataplane_algorithms>`).
  31
  32 A FIB rule consists of a prefix and an associated next hop ID. The prefix consists
  33 of an IPv4 network address (``uint32_t``) and the corresponding prefix length.
  34 The prefix serves as the key and the next hop ID as the value while doing an LPM
  35 search within FIB. The size of the next hop ID is variable and must be configured
  36 during initialization.
  37
  38 The main methods within the ``rte_fib`` API are:
  39
  40 * ``rte_fib_add()``: Add a new route with a corresponding next hop ID to the
  41   table or update the next hop ID if the prefix already exists in a table.
  42
  43 * ``rte_fib_delete()``: Delete an existing route from the table.
  44
  45 * ``rte_fib_lookup_bulk()``: Provides a bulk Longest Prefix Match (LPM) lookup function
  46   for a set of IP addresses, it will return a set of corresponding next hop IDs.
  47
  48
  49 Implementation details
  50 ----------------------
  51
  52 Internally FIB contains the ``rte_rib`` data struct to help maintain the dataplane struct.
  53 The dataplane struct is opaque, so that users can add their own algorithm implementations.
  54
  55 .. _fib_dataplane_algorithms:
  56
  57
  58 Dataplane Algorithms
  59 --------------------
  60
  61
  62 Dummy
  63 ~~~~~
  64
  65 This algorithm uses ``rte_rib`` as a dataplane struct. Lookups are relatively slow,
  66 but extra memory isn't used for the dataplane struct. This algorithm should only
  67 be used for testing and debugging purposes.
  68
  69 This algorithm will be used if the ``RTE_FIB_DUMMY`` type is configured as the
  70 dataplane algorithm on FIB creation.
  71
  72
  73 DIR-24-8
  74 ~~~~~~~~
  75
  76 The current implementation of this algorithm uses a variation of the DIR-24-8
  77 algorithm that trades memory usage for improved LPM lookup speed.
  78 This algorithm allows the lookup operation to be performed using only a single
  79 memory read access in most cases. In the statistically rare case where the best
  80 match rule has a depth larger than 24, the lookup operation will require two
  81 memory read accesses.
  82
  83 This algorithm will be used if the ``RTE_FIB_DIR24_8`` type is configured as the
  84 dataplane algorithm on FIB creation.
  85
  86 The main FIB configuration struct stores the dataplane parameters inside ``dir24_8``
  87 within the ``rte_fib_conf`` and it consists of:
  88
  89 * ``nh_sz``: The size of the entry containing the next hop ID.
  90   This could be 1, 2, 4 or 8 bytes long.
  91   Note that all available bits except one are used to store the actual next hop ID.
  92
  93 * ``num_tbl8``: The number of tbl8 groups, each group consists of 256 entries
  94   corresponding to the ``nh_sz`` size.
  95
  96 The main elements of the dataplane struct for the DIR-24-8 algorithm are:
  97
  98 * TBL24: An array with 2\ :sup:`24` entries, corresponding to the ``nh_sz`` size.
  99
 100 * TBL8: An array of ``num_tbl8`` tbl8 groups.
 101
 102 The lookup algorithms logic can be seen in :numref:`figure_dir_24_8_alg`:
 103
 104 .. _figure_dir_24_8_alg:
 105
 106 .. figure:: img/dir_24_8_alg.*
 107
 108    DIR-24-8 Lookup algorithm
 109
 110 The first table ``tbl24``, is indexed using the first 24 bits of the IP address to be looked up,
 111 while the second table(s) ``tbl8``, is indexed using the last 8 bits of the IP address.
 112 This means that depending on the outcome of trying to match the IP address of an incoming packet
 113 to a rule stored in the tbl24 we might need to continue the lookup process in the second level.
 114
 115 Since every entry of the tbl24 can potentially point to a tbl8,
 116 ideally we would have 2\ :sup:`24` tbl8s, which would be the same as having a
 117 single table with 2\ :sup:`32` entries. This is not feasible due to resource restrictions.
 118 Instead, this approach takes advantage of the fact that rules longer than 24 bits are very rare.
 119 By splitting the process into two different tables/levels and limiting the number of tbl8s,
 120 we can greatly reduce memory consumption while maintaining a very good lookup speed.
 121 This method generally results in one memory access per lookup.
 122
 123 An entry in a tbl8 contains the following fields:
 124
 125 * The next hop ID.
 126
 127 * 1 bit indicating if the lookup should proceed inside the tbl8.
 128
 129
 130 Use cases
 131 ---------
 132
 133 The FIB library is useful for any use cases that rely on the Longest Prefix Match (LPM)
 134 algorithm such as IP forwarding or packet classification.
 135
 136 More complex use cases are also possible, as it is possible to have next hop IDs
 137 which are 63 bits long (using ``RTE_FIB_DIR24_8_8B`` as a next hop size).
 138 These use cases could include storing two next hop IDs inside the 63 bits of the next hop.
 139 This may be useful to provide a fallback next hop ID, ASN or forwarding class
 140 corresponding to a given prefix without having to perform an additional lookup.