summaryrefslogtreecommitdiffstats
path: root/docs/gettingstarted/developers/fib20/routes.rst
diff options
context:
space:
mode:
Diffstat (limited to 'docs/gettingstarted/developers/fib20/routes.rst')
-rw-r--r--docs/gettingstarted/developers/fib20/routes.rst353
1 files changed, 0 insertions, 353 deletions
diff --git a/docs/gettingstarted/developers/fib20/routes.rst b/docs/gettingstarted/developers/fib20/routes.rst
deleted file mode 100644
index 313a86c3af4..00000000000
--- a/docs/gettingstarted/developers/fib20/routes.rst
+++ /dev/null
@@ -1,353 +0,0 @@
-.. _routes:
-
-Routes
-^^^^^^
-
-Basics
-------
-
-The anatomy of a route is crucial to understand:
-
-.. code-block:: console
-
- 1.1.1.0/24 via 10.0.0.1 eth0
-
-A route is composed of two parts; **what** to match against and **how** to forward
-the matched packets. In the above example we want to match packets
-whose destination IP address is in the 1.1.1.0/24 subnet and then we
-want to forward those packet to 10.0.0.1 on interface eth0. We
-therefore want to match the **prefix** 1.1.1.0/24 and forward on the
-**path** to 10.0.0.1, eth0.
-
-Matching on a prefix is the particular task of the IP FIB, matching on
-other packet attributes is done by other subsystems, e.g. matching on
-MPLS labels in the MPLS-FIB, or matching on a tuple in ACL based
-forwarding (ABF), 'matching' on all packets that arrive on an L3
-interface (l3XC). Although these subsystems match on different
-properties, they share the infrastructure on **how** to forward
-matched packets, that is they share the **paths**. The FIB paths (or
-really the path-list) thus provide services to clients, this service
-is to **contribute** forwarding, this, in terms that will be made
-clear in later sections, is to provide the DPO to use.
-
-The prime function of the FIB is to *resolve* the paths for a
-route. To resolve a route is to construct an object graph that fully
-describes how to forward matching packets. This means that the graph
-must terminate with an object (the leaf node) that describes how
-to send a packet on an interface [#f1]_, i.e what encap to add to the
-packet and what interface to send it to; this is the purpose of the IP
-adjacency object. In Figure 3 the route is resolved as the graph is
-complete from *fib_entry_t* to *ip_adjacency_t*.
-
-
-Thread Model
-^^^^^^^^^^^^
-
-The FIB is not thread safe. All actions on the FIB are expected to
-occur exclusively in the main thread. However, the data-structures
-that FIB updates to add routes are thread safe,
-w.r.t. addition/deletion and read, therefore routes can be added
-without holding the worker thread barrier lock.
-
-
-Tables
-------
-
-An IP FIB is a set of prefixes against which to match; it is
-sub-address family (SAFI) specific (i.e. there is one for ipv4 and ipv6, unicast
-and multicast). An IP Table is address family (AFI) specific (i.e. the
-'table' includes the unicast and multicast FIB).
-
-Each FIB is identified by the SAFI and instance number (the [pool]
-index), each table is identified by the AFI and ID. The table's ID is
-assigned by the user when the table is constructed. Table ID 0 is
-reserved for the global/default table.
-
-In most routing models a VRF is composed of an IPv4 and IPv6 table,
-however, VPP has no construct to model this association, it deals only
-with tables and FIBs.
-
-A unicast FIB is comprised of two route data-bases; forwarding and non-forwarding. The
-forwarding data-base contains routes against which a packet will perform a longest
-prefix match (LPM) in the data-plane. The non-forwarding DB contains all the routes
-with which VPP has been programmed. Some of these routes may be
-unresolved, preventing their insertion into the forwarding DB.
-(see section: Adjacency source FIB entries).
-
-Model
------
-
-The route data is decomposed into three parts; entry, path-list and paths;
-
-* The *fib_entry_t*, which contains the route's prefix, is the representation of that prefix's entry in the FIB table.
-* The *fib_path_t* is a description of where to send the packets destined to the route's prefix. There are several types of path, including:
-
- * Attached next-hop: the path is described with an interface and a next-hop. The next-hop is in the same sub-net as the router's own address on that interface, hence the peer is considered to be *attached*
-
- * Attached: the path is described only by an interface. An
- attached path means that all addresses covered by the route's
- prefix are on the same L2 segment to which that router's
- interface is attached. This means it is possible to ARP for any
- address covered by the route's prefix. If this is not the case
- then another device in that L2 segment needs to run proxy
- ARP. An attached path is really only appropriate for a point-to-point
- (P2P) interface where ARP is not required, i.e. a GRE tunnel. On
- a p2p interface, attached and attached-nexthop paths will
- resolve via a special 'auto-adjacency'. This is an adjacency
- whose next-hop is the all zeros address and describes the only
- peer on the link.
-
- * Recursive: The path is described only via the next-hop and table-id.
-
- * De-aggregate: The path is described only via the special all
- zeros address and a table-id. This implies a subsequent lookup
- in the table should be performed.
-
- * There are other path types, please consult the code.
-
-* The *fib_path_list_t* represents the list of paths from which to choose when forwarding. A path-list is a shared object, i.e. it is the parent to multiple fib_entry_t children. In order to share any object type it is necessary for a child to search for an existing object matching its requirements. For this there must be a database. The key to the path-list database is a combined description of all of the paths it contains [#f2]_. Searching the path-list database is required with each route addition, so it is populated only with path-lists for which sharing will bring convergence benefits (see Section: :ref:`fastconvergence`).
-
-.. figure:: /_images/fib20fig2.png
-
-Figure 2: Route data model class diagram
-
-Figure 2 shows an example of a route with two attached-next-hop paths. Each of these
-paths will *resolve* by finding the adjacency that matches the paths attributes, which
-are the same as the key for the adjacency database [#f3]_. The *forwarding information (FI)*
-is the set of adjacencies that are available for load-balancing the traffic in the
-data-plane. A path *contributes* an adjacency to the route's forwarding information, the
-path-list contributes the full forwarding information for IP packets.
-
-.. figure:: /_images/fib20fig3.png
-
-Figure 3: Route object diagram
-
-Figure 3 shows the object instances and their relationships created in order to resolve
-the routes also shown. The graph nature of these relationships is evident; children
-are displayed at the top of the diagram, their parents below them. Forward walks are
-thus from top to bottom, back walks bottom to top. The diagram shows the objects
-that are shared, the path-list and adjacency. Sharing objects is critical to fast
-convergence (see section :ref:`fastconvergence`).
-
-FIB sources
-"""""""""""
-There are various entities in the system that can add routes to the FIB tables.
-Each of these entities is termed a *source*. When the same prefix is added by different
-sources the FIB must arbitrate between them to determine which source will contribute
-the forwarding information. Since each source determines the forwarding information
-using different best path and loop prevention algorithms, it is not correct for the
-forwarding information of multiple sources to be combined. Instead the FIB must choose
-to use the forwarding information from only one source. This choice is based on a static
-priority assignment [#f4]_. The FIB must maintain the information each source has added
-so it can be restored should that source become the best source. VPP has two
-*control-plane* sources; the API and the CLI the API has the higher priority.
-Each *source* data is represented by a *fib_entry_src_t* object of which a
-*fib_entry_t* maintains a sorted vector.
-
-The following configuration:
-
-.. code-block:: console
-
- $ set interface ip address GigabitEthernet0/8/0 192.168.1.1/24
-
-results in the addition of two FIB entries; 192.168.1.0/24 which is connected and
-attached, and 192.168.1.1/32 which is connected and local (a.k.a.
-receive or for-us). A prefix is *connected* when it is applied to a router's interface.
-Both prefixes are *interface* sourced. The interface source has a high priority, so
-the accidental or nefarious addition of identical prefixes does not prevent the
-router from correctly forwarding. Packets matching a connected prefix will
-generate an ARP request for the packets destination address, this process is known
-as a *glean*.
-
-An *attached* prefix also results in a glean, but the router does not have its own
-address in that sub-net. The following configuration will result in an attached
-route, which resolves via an attached path;
-
-.. code-block:: console
-
- $ ip route add table X 10.10.10.0/24 via gre0
-
-as mentioned before, these are only appropriate for point-to-point
-links.
-
-If table X is not the table to which gre0 is bound,
-then this is the case of an attached export (see the section :ref:`attachedexport`).
-
-Adjacency source FIB entries
-""""""""""""""""""""""""""""
-
-Whenever an ARP entry is created it will source a *fib_entry_t*. In this case the
-route is of the form:
-
-.. code-block:: console
-
- $ ip route add table X 10.0.0.1/32 via 10.0.0.1 GigabitEthernet0/8/0
-
-This is a host prefix with a path whose next-hop address is the same host. This route
-highlights the distinction between the route's prefix - a description of the traffic
-to match - and the path - a description of where to send the matched traffic.
-Table X is the same table to which the interface is bound. FIB entries that are
-sourced by adjacencies are termed *adj-fibs*. The priority of the adjacency source
-is lower than the API source, so the following configuration:
-
-.. code-block:: console
-
- $ set interface address 192.168.1.1/24 GigabitEthernet0/8/0
- $ ip arp 192.168.1.2 GigabitEthernet0/8/0 dead.dead.dead
- $ ip route add 192.168.1.2 via 10.10.10.10 GigabitEthernet1/8/0
-
-will forward traffic for 192.168.1.2 via GigabitEthernet1/8/0. That is the route added by the control
-plane is favoured over the adjacency discovered by ARP. The control plane, with its
-associated authentication, is considered the authoritative source. To counter the
-nefarious addition of adj-fibs, through the nefarious injection of adjacencies, the
-FIB is also required to ensure that only adj-fibs whose less specific covering prefix
-is attached are installed in forwarding. This requires the use of *cover tracking*,
-where a route maintains a dependency relationship with the route that is its less
-specific cover. When this cover changes (i.e. there is a new covering route) or the
-forwarding information of the cover is updated, then the covered route is notified.
-Adj-fibs that fail this cover check are not installed in the fib_table_t's forwarding
-table, they are only present in the non-forwarding table.
-
-Overlapping sub-nets are not supported, so no adj-fib has multiple paths. The control
-plane is expected to remove a prefix configured for an interface before the interface
-changes VRF.
-
-Recursive Routes
-""""""""""""""""
-
-Figure 4 shows the data structures used to describe a recursive route. The
-representation is almost identical to attached next-hop paths. The difference
-being that the *fib_path_t* has a parent that is another *fib_entry_t*, termed the
-*via-entry*
-
-.. figure:: /_images/fib20fig4.png
-
-Figure 4: Recursive route class diagram.
-
-In order to forward traffic to 64.10.128.0/20 the FIB must first determine how to forward
-traffic to 1.1.1.1/32. This is recursive resolution. Recursive resolution, which is
-essentially a cache of the data-plane result, emulates a longest prefix match for the
-*via-address" 1.1.1.1 in the *via-table* table 0 [#f5]_.
-
-Recursive resolution (RR) will source a host-prefix entry in the via-table for the
-via-address. The RR source is a low priority source. In the unlikely [#f6]_ event that the
-RR source is the best source, then it must derive forwarding information from its
-covering prefix.
-
-There are two cases to consider:
-
-* The cover is connected [#f7]_. The via-address is then an attached host and the RR source can resolve directly via the adjacency with the key {via-address, interface-of-connected-cover}
-* The cover is not connected [#f8]_. The RR source can directly inherit the forwarding information from its cover.
-
-This dependency on the covering prefix means the RR source will track its cover The
-covering prefix will *change* when;
-
-* A more specific prefix is inserted. For this reason whenever an entry is inserted into a FIB table its cover must be found so that its covered dependents can be informed.
-* The existing cover is removed. The covered prefixes must form a new relationship with the next less specific.
-
-The cover will be *updated* when the route for the covering prefix is modified. The
-cover tracking mechanism will provide the RR sourced entry with a notification in the
-event of a change or update of the cover, and the source can take the necessary action.
-
-The RR sourced FIB entry becomes the parent of the *fib_path_t* and will contribute its
-forwarding information to that path, so that the child's FIB entry can construct its own
-forwarding information.
-
-Figure 5 shows the object instances created to represent the recursive route and
-its resolving route also shown.
-
-.. figure:: /_images/fib20fig5.png
-
-Figure 5: Recursive Routes object diagram
-
-If the source adding recursive routes does not itself perform recursive resolution [#f9]_
-then it is possible that the source may inadvertently programme a recursion loop.
-
-An example of a recursion loop is the following configuration:
-
-.. code-block:: console
-
- $ ip route add 5.5.5.5/32 via 6.6.6.6
- $ ip route add 6.6.6.6/32 via 7.7.7.7
- $ ip route add 7.7.7.7/32 via 5.5.5.5
-
-This shows a loop over three levels, but any number is possible. FIB will detect
-recursion loops by forward walking the graph when a *fib_entry_t* forms a child-parent
-relationship with a *fib_path_list_t*. The walk checks to see if the same object instances
-are encountered. When a recursion loop is formed the control plane [#f10]_ graph becomes
-cyclic, thus allowing the child-parent dependencies to form. This is necessary so that
-when the loop breaks, the affected children and be updated.
-
-Output labels
-"""""""""""""
-
-A route may have associated output MPLS labels [#f11]_. These are labels that are expected
-to be imposed on a packet as it is forwarded. It is important to note that an MPLS
-label is per-route and per-path, therefore, even though routes share paths they do not
-necessarily have the same label for that path [#f12]_. A label is therefore uniquely associated
-to a *fib_entry_t* and associated with one of the *fib_path_t* to which it forwards.
-MPLS labels are modelled via the generic concept of a *path-extension*. A *fib_entry_t*
-therefore has a vector of zero to many *fib_path_ext_t* objects to represent the labels
-with which it is configured.
-
-
-Delegates
-^^^^^^^^^
-
-A common software development pattern, a delegate is a means to
-extend the functionality of one object through composition of
-another, these other objects are called delegates. Both
-**fib_entry_t** and **ip_adjacency_t** support extension via delegates.
-
-The FIB uses delegates to add functionality when those functions are
-required by only a few objects instances rather than all of them, to
-save on memory. For example, building/contributing a load-balance
-object used to forward non-EOS MPLS traffic is only required for a
-fib_entry_t that corresponds to a BGP peer and that peer is
-advertising labeled route - there are only a few of
-these. See **fib_entry_delegate.h** for a full list of delegate types.
-
-
-Tracking
-^^^^^^^^
-
-A prime service FIB provides for other sub-system is the ability to
-'track' the forwarding for a given next-hop. For example, a tunnel
-will want to know how to forward to its destination address. It can
-therefore request of the FIB to track this host-prefix and inform it
-when the forwarding for that prefix changes.
-
-FIB tracking sources a host-prefix entry in the FIB using the 'recusive
-resolution (RR)' source, it exactly the same way that a recursive path
-does. If the entry did not previsouly exist, then the RR source will
-inherit (and track) forwarding from its covering prefix, therefore all
-packets that match this entry are forwarded in the same way as if the
-entry did not exist. The tunnel that is tracking this FIB entry will
-become a child dependent. The benefit to creating the entry, is that
-it now exists in the FIB node graph, so all actions that happen on its
-parents, are propagated to the host-prefix entry and consequently to
-the tunnel.
-
-FIB provides a wrapper to the sourcing of the host-prefix using a
-delegate attached to the entry, and the entry is RR sourced only once.
-. The benefit of this aproach is that each time a new client tracks
-the entry it doesn't RR source it. When an entry is sourced all its
-children are updated. Thus, new clients tracking an entry is
-O(n^2). With the tracker as indirection, the entry is sourced only once.
-
-
-.. rubric:: Footnotes:
-
-.. [#f1] Or terminate in an object that transitions the packet out of
- the FIB domain, e.g. a drop.
-.. [#f2] Optimisations
-.. [#f3] Note it is valid for either interface to be bound to a different table than table 1
-.. [#f4] The engaged reader can see the full priority list in vnet/vnet/fib/fib_entry.h
-.. [#f5] Note it is only possible to add routes via an address (i.e. a/32 or /128) not via a shorter mask prefix. There is no use case for the latter
-.. [#f6] For iBGP the via-address is the loopback address of the peer PE, for eBGP it is the adj-fib for the CE
-.. [#f7] As is the case ofr eBGP
-.. [#f8] As is the case for iBGP
-.. [#f9] If that source is relying on FIB to perform recursive resolution, then there is no reason it should do so itself.
-.. [#f10] The derived data-plane graph MUST never be cyclic
-.. [#f11] Advertised, e.g. by LDP, SR or BGP
-.. [#f12] The only case where the labels will be the same is BGP VPNv4 label allocation per-VRF