1.. SPDX-License-Identifier: BSD-3-Clause 2 Copyright(c) 2021 Intel Corporation. 3 4Forwarding Information Base (FIB) Library 5========================================= 6 7The FIB library provides a fast Longest Prefix Match (LPM) search for 32-bit 8keys or 128-bit for IPv6. It can be used in a variety of applications, 9the 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 19FIB API Overview 20---------------- 21 22The 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 32A FIB rule consists of a prefix and an associated next hop ID. The prefix consists 33of an IPv4 network address (``uint32_t``) and the corresponding prefix length. 34The prefix serves as the key and the next hop ID as the value while doing an LPM 35search within FIB. The size of the next hop ID is variable and must be configured 36during initialization. 37 38The 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 49Implementation details 50---------------------- 51 52Internally FIB contains the ``rte_rib`` data struct to help maintain the dataplane struct. 53The dataplane struct is opaque, so that users can add their own algorithm implementations. 54 55.. _fib_dataplane_algorithms: 56 57 58Dataplane Algorithms 59-------------------- 60 61 62Dummy 63~~~~~ 64 65This algorithm uses ``rte_rib`` as a dataplane struct. Lookups are relatively slow, 66but extra memory isn't used for the dataplane struct. This algorithm should only 67be used for testing and debugging purposes. 68 69This algorithm will be used if the ``RTE_FIB_DUMMY`` type is configured as the 70dataplane algorithm on FIB creation. 71 72 73DIR-24-8 74~~~~~~~~ 75 76The current implementation of this algorithm uses a variation of the DIR-24-8 77algorithm that trades memory usage for improved LPM lookup speed. 78This algorithm allows the lookup operation to be performed using only a single 79memory read access in most cases. In the statistically rare case where the best 80match rule has a depth larger than 24, the lookup operation will require two 81memory read accesses. 82 83This algorithm will be used if the ``RTE_FIB_DIR24_8`` type is configured as the 84dataplane algorithm on FIB creation. 85 86The main FIB configuration struct stores the dataplane parameters inside ``dir24_8`` 87within 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 96The 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 102The 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 110The first table ``tbl24``, is indexed using the first 24 bits of the IP address to be looked up, 111while the second table(s) ``tbl8``, is indexed using the last 8 bits of the IP address. 112This means that depending on the outcome of trying to match the IP address of an incoming packet 113to a rule stored in the tbl24 we might need to continue the lookup process in the second level. 114 115Since every entry of the tbl24 can potentially point to a tbl8, 116ideally we would have 2\ :sup:`24` tbl8s, which would be the same as having a 117single table with 2\ :sup:`32` entries. This is not feasible due to resource restrictions. 118Instead, this approach takes advantage of the fact that rules longer than 24 bits are very rare. 119By splitting the process into two different tables/levels and limiting the number of tbl8s, 120we can greatly reduce memory consumption while maintaining a very good lookup speed. 121This method generally results in one memory access per lookup. 122 123An 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 130Use cases 131--------- 132 133The FIB library is useful for any use cases that rely on the Longest Prefix Match (LPM) 134algorithm such as IP forwarding or packet classification. 135 136More complex use cases are also possible, as it is possible to have next hop IDs 137which are 63 bits long (using ``RTE_FIB_DIR24_8_8B`` as a next hop size). 138These use cases could include storing two next hop IDs inside the 63 bits of the next hop. 139This may be useful to provide a fallback next hop ID, ASN or forwarding class 140corresponding to a given prefix without having to perform an additional lookup. 141