summaryrefslogtreecommitdiffstats
path: root/docs/gettingstarted/developers/fib20/fastconvergence.rst
diff options
context:
space:
mode:
Diffstat (limited to 'docs/gettingstarted/developers/fib20/fastconvergence.rst')
-rw-r--r--docs/gettingstarted/developers/fib20/fastconvergence.rst576
1 files changed, 0 insertions, 576 deletions
diff --git a/docs/gettingstarted/developers/fib20/fastconvergence.rst b/docs/gettingstarted/developers/fib20/fastconvergence.rst
deleted file mode 100644
index b07e08cea6d..00000000000
--- a/docs/gettingstarted/developers/fib20/fastconvergence.rst
+++ /dev/null
@@ -1,576 +0,0 @@
-.. _fastconvergence:
-
-Fast Convergence
-------------------------------------
-
-This is an excellent description of the topic:
-
-'FIB <https://tools.ietf.org/html/draft-ietf-rtgwg-bgp-pic-12>'_
-
-but if you're interested in my take keep reading...
-
-First some definitions:
-
-- Convergence; When a FIB is forwarding all packets correctly based
- on the network topology (i.e. doing what the routing control plane
- has instructed it to do), then it is said to be 'converged'.
- Not being in a converged state is [hopefully] a transient state,
- when either the topology change (e.g. a link failure) has not been
- observed or processed by the routing control plane, or that the FIB
- is still processing routing updates. Convergence is the act of
- getting to the converged state.
-- Fast: In the shortest time possible. There are no absolute limits
- placed on how short this must be, although there is one number often
- mentioned. Apparently the human ear can detect loss/delay/jitter in
- VOIP of 50ms, therefore network failures should last no longer than
- this, and some technologies (notably link-free alternate fast
- reroute) are designed to converge in this time. However, it is
- generally accepted that it is not possible to converge a FIB with
- tens of millions of routes in this time scale, the industry
- 'standard' is sub-second.
-
-Converging the FIB quickly is thus a matter of:
-
-- discovering something is down
-- updating as few objects as possible
-- to determine which objects to update as efficiently as possible
-- to update each object as quickly as possible
-
-we'll discuss each in turn.
-All output came from VPP version 21.01rc0. In what follows I use IPv4
-prefixes, addresses and IPv4 host length masks, however, exactly the
-same applies to IPv6.
-
-
-Failure Detection
-^^^^^^^^^^^^^^^^^
-
-The two common forms (we'll see others later on) of failure detection
-are:
-
-- link down
-- BFD
-
-The FIB needs to hook into these notifications to trigger
-convergence.
-
-Whenever an interface goes down, VPP issues a callback to all
-registerd clients. The adjacency code is such a client. The adjacency
-is a leaf node in the FIB control-plane graph (containing fib_path_t,
-fib_entry_t etc). A back-walk from the adjacnecy will trigger a
-re-resolution of the paths.
-
-FIB is a client of BFD in order to receive BFD notifications. BFD
-comes in two flavours; single and multi hop. Single hop is to protect
-a specific peer on an interface, such peers are modelled by an
-adjacency. Multi hop is to protect a peer on an unspecified interface
-(i.e. a remote peer), this peer is represented by a host-prefix
-**fib_entry_t**. In both case FIB will add a delegate to the
-**ip_adjacency_t** or **fib_entry_t** that represents the association
-to the BFD session. If the BFD session signals up/down then a backwalk
-can be triggered from the object to trigger re-resolution and hence
-convergence.
-
-
-Few Updates
-^^^^^^^^^^^
-
-In order to talk about what 'a few' is we have to leave the realm of
-the FIB as an abstract graph based object DB and move into the
-concrete representation of forwarding in a large network. Large
-networks are built in layers, it's how you scale them. We'll take
-here a hypothetical service provider (SP) network, but the concepts
-apply equally to data center leaf-spines. This is a rudimentary
-description, but it should serve our purpose.
-
-An SP manages a BGP autonomous system (AS). The SP's goal is both to
-attract traffic into its network to serve its customers, but also to
-serve transit traffic passing through it, we'll consider the latter here.
-The SP's network is all devices in that AS, these
-devices are split into those at the edge (provider edge (PE) routers)
-which peer with routers in other SP networks,
-and those in the core (termed provider (P) routers). Both the PE and P
-routers run the IGP (usually OSPF or ISIS). Only the reachability of the devices
-in the AS are advertised in the IGP - thus the scale (i.e. the number
-of routes) in the IGP is 'small' - only the number of
-devices that the SP has (typically not more than a few 10k).
-PE routers run BGP; they have external BGP sessions to devices in
-other ASs and internal BGP sessions to devices in the same AS. BGP is
-used to advertise the routes to *all* networks on the internet - at
-the time of writing this number is approaching 900k IPv4 route, hopefully by
-the time you are reading this the number of IPv6 routes has caught up ...
-If we include the additional routes the SP carries to offering VPN service to its
-customers the number of BGP routes can grow to the tens of millions.
-
-BGP scale thus exceeds IGP scale by two orders of magnitude... pause for
-a moment and let that sink in...
-
-A comparison of BGP and an IGP is way way beyond the scope of this
-documentation (and frankly beyond me) so we'll note only the
-difference in the form of the routes they present to FIB. A routing
-protocol will produce routes that specify the prefixes that are
-reachable through its peers. A good IGP
-is link state based, it forms peerings to other devices over these
-links, hence its routes specify links/interfaces. In
-FIB nomenclature this means an IGP produces routes that are
-attached-nexthop, e.g.:
-
-.. code-block:: console
-
- ip route add 1.1.1.1/32 via 10.0.0.1 GigEthernet0/0/0
-
-BGP on the other hand forms peerings only to neighbours, it does not
-know, nor care, what interface is used to reach the peer. In FIB
-nomenclature therefore BGP produces recursive routes, e.g.:
-
-.. code-block:: console
-
- ip route 8.0.0.0/16 via 1.1.1.1
-
-where 1.1.1.1 is the BGP peer. It's no accident in this example that
-1.1.1.1/32 happens to be the route the IGP advertised... BGP installs
-routes for prefixes reachable via other BGP peers, and the IGP install
-the routes to those BGP peers.
-
-This has been a very long winded way of describing why the scale of
-recursive routes is therefore 2 orders of magnitude greater than
-non-recursive/attached-nexthop routes.
-
-If we step back for a moment and recall why we've crawled down this
-rabbit hole, we're trying to determine what 'a few' updates means,
-does it include all those recursive routes, probably not ... let's
-keep crawling.
-
-We started this chapter with an abstract description of convergence,
-let's now make that more real. In the event of a network failure an SP
-is interested in moving to an alternate forwarding path as quickly as
-possible. If there is no alternate path, and a converged FIB will drop
-the packet, then who cares how fast it converges. In other words the
-interesting convergence scenarios are the scenarios where the network has
-alternate paths.
-
-PIC Core
-^^^^^^^^
-
-First let's consider alternate paths in the IGP, e.g.;
-
-.. code-block:: console
-
- ip route add 1.1.1.1/32 via 10.0.0.2 GigEthernet0/0/0
- ip route add 1.1.1.1/32 via 10.0.1.2 GigEthernet0/0/1
-
-this gives us in the FIB:
-
-.. code-block:: console
-
- DBGvpp# sh ip fib 1.1.1.1/32
- ipv4-VRF:0, fib_index:0, flow hash:[src dst sport dport proto ] epoch:0 flags:none locks:[adjacency:1, default-route:1, ]
- 1.1.1.1/32 fib:0 index:15 locks:2
- API refs:1 src-flags:added,contributing,active,
- path-list:[23] locks:2 flags:shared, uPRF-list:22 len:2 itfs:[1, 2, ]
- path:[27] pl-index:23 ip4 weight=1 pref=0 attached-nexthop: oper-flags:resolved,
- 10.0.0.2 GigEthernet0/0/0
- [@0]: ipv4 via 10.0.0.2 GigEthernet0/0/0: mtu:9000 next:3 001111111111dead000000000800
- path:[28] pl-index:23 ip4 weight=1 pref=0 attached-nexthop: oper-flags:resolved,
- 10.0.1.2 GigEthernet0/0/1
- [@0]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
-
- forwarding: unicast-ip4-chain
- [@0]: dpo-load-balance: [proto:ip4 index:17 buckets:2 uRPF:22 to:[0:0]]
- [0] [@5]: ipv4 via 10.0.0.2 GigEthernet0/0/0: mtu:9000 next:3 001111111111dead000000000800
- [1] [@5]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
-
-There is ECMP across the two paths. Note that the instance/index of the
-load-balance present in the forwarding graph is 17.
-
-Let's add a BGP route via this peer;
-
-.. code-block:: console
-
- ip route add 8.0.0.0/16 via 1.1.1.1
-
-in the FIB we see:
-
-
-.. code-block:: console
-
- DBGvpp# sh ip fib 8.0.0.0/16
- ipv4-VRF:0, fib_index:0, flow hash:[src dst sport dport proto ] epoch:0 flags:none locks:[adjacency:1, recursive-resolution:1, default-route:1, ]
- 8.0.0.0/16 fib:0 index:18 locks:2
- API refs:1 src-flags:added,contributing,active,
- path-list:[24] locks:2 flags:shared, uPRF-list:21 len:2 itfs:[1, 2, ]
- path:[29] pl-index:24 ip4 weight=1 pref=0 recursive: oper-flags:resolved,
- via 1.1.1.1 in fib:0 via-fib:15 via-dpo:[dpo-load-balance:17]
-
- forwarding: unicast-ip4-chain
- [@0]: dpo-load-balance: [proto:ip4 index:20 buckets:1 uRPF:21 to:[0:0]]
- [0] [@12]: dpo-load-balance: [proto:ip4 index:17 buckets:2 uRPF:22 to:[0:0]]
- [0] [@5]: ipv4 via 10.0.0.2 GigEthernet0/0/0: mtu:9000 next:3 001111111111dead000000000800
- [1] [@5]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
-
-the load-balance object used by this route is index 20, but note that
-the next load-balance in the chain is index 17, i.e. it is exactly
-the same instance that appears in the forwarding chain for the IGP
-route. So in the forwarding plane the packet first encounters
-load-balance object 20 (which it will use in ip4-lookup) and then
-number 17 (in ip4-load-balance).
-
-What's the significance? Let's shut down one of those IGP paths:
-
-.. code-block:: console
-
- DBGvpp# set in state GigEthernet0/0/0 down
-
-the resulting update to the IGP route is:
-
-.. code-block:: console
-
- DBGvpp# sh ip fib 1.1.1.1/32
- ipv4-VRF:0, fib_index:0, flow hash:[src dst sport dport proto ] epoch:0 flags:none locks:[adjacency:1, recursive-resolution:1, default-route:1, ]
- 1.1.1.1/32 fib:0 index:15 locks:4
- API refs:1 src-flags:added,contributing,active,
- path-list:[23] locks:2 flags:shared, uPRF-list:25 len:2 itfs:[1, 2, ]
- path:[27] pl-index:23 ip4 weight=1 pref=0 attached-nexthop:
- 10.0.0.2 GigEthernet0/0/0
- [@0]: arp-ipv4: via 10.0.0.2 GigEthernet0/0/0
- path:[28] pl-index:23 ip4 weight=1 pref=0 attached-nexthop: oper-flags:resolved,
- 10.0.1.2 GigEthernet0/0/1
- [@0]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
-
- recursive-resolution refs:1 src-flags:added, cover:-1
-
- forwarding: unicast-ip4-chain
- [@0]: dpo-load-balance: [proto:ip4 index:17 buckets:1 uRPF:25 to:[0:0]]
- [0] [@5]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
-
-
-notice that the path via 10.0.0.2 is no longer flagged as resolved,
-and the forwarding chain does not contain this path as a
-choice. However, the key thing to note is the load-balance
-instance is still index 17, i.e. it has been modified not
-exchanged. In the FIB vernacular we say it has been 'in-place
-modified', a somewhat linguistically redundant expression, but one that serves
-to emphasise that it was changed whilst still be part of the graph, it
-was never at any point removed from the graph and re-added, and it was
-modified without worker barrier lock held.
-
-Still don't see the significance? In order to converge around the
-failure of the IGP link it was not necessary to update load-balance
-object number 20! It was not necessary to update the recursive
-route. i.e. convergence is achieved without updating any recursive
-routes, it is only necessary to update the affected IGP routes, this is
-the definition of 'a few'. We call this 'prefix independent
-convergence' (PIC) which should really be called 'recursive prefix
-independent convergence' but it isn't...
-
-How was the trick done? As with all problems in computer science, it
-was solved by a layer of misdirection, I mean indirection. The
-indirection is the load-balance that belongs to the IGP route. By
-keeping this object in the forwarding graph and updating it in place,
-we get PIC. The alternative design would be to collapse the two layers of
-load-balancing into one, which would improve forwarding performance
-but would come at the cost of prefix dependent convergence. No doubt
-there are situations where the VPP deployment would favour forwarding
-performance over convergence, you know the drill, contributions welcome.
-
-This failure scenario is known as PIC core, since it's one of the IGP's
-core links that has failed.
-
-iBGP PIC Edge
-^^^^^^^^^^^^^
-
-Next, let's consider alternate paths in BGP, e.g:
-
-.. code-block:: console
-
- ip route add 8.0.0.0/16 via 1.1.1.1
- ip route add 8.0.0.0/16 via 1.1.1.2
-
-the 8.0.0.0/16 prefix is reachable via two BGP next-hops (two PEs).
-
-Our FIB now also contains:
-
-.. code-block:: console
-
- DBGvpp# sh ip fib 8.0.0.0/16
- ipv4-VRF:0, fib_index:0, flow hash:[src dst sport dport proto ] epoch:0 flags:none locks:[adjacency:1, recursive-resolution:2, default-route:1, ]
- 8.0.0.0/16 fib:0 index:18 locks:2
- API refs:1 src-flags:added,contributing,active,
- path-list:[15] locks:2 flags:shared, uPRF-list:11 len:2 itfs:[1, 2, ]
- path:[17] pl-index:15 ip4 weight=1 pref=0 recursive: oper-flags:resolved,
- via 1.1.1.1 in fib:0 via-fib:15 via-dpo:[dpo-load-balance:17]
- path:[15] pl-index:15 ip4 weight=1 pref=0 recursive: oper-flags:resolved,
- via 1.1.1.2 in fib:0 via-fib:10 via-dpo:[dpo-load-balance:12]
-
- forwarding: unicast-ip4-chain
- [@0]: dpo-load-balance: [proto:ip4 index:20 buckets:2 uRPF:11 to:[0:0]]
- [0] [@12]: dpo-load-balance: [proto:ip4 index:17 buckets:1 uRPF:25 to:[0:0]]
- [0] [@5]: ipv4 via 10.0.0.2 GigEthernet0/0/0: mtu:9000 next:3 001122334455dead000000000800
- [1] [@5]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
- [1] [@12]: dpo-load-balance: [proto:ip4 index:12 buckets:1 uRPF:13 to:[0:0]]
- [0] [@5]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
-
-The first load-balance (LB) in the forwarding graph is index 20 (the astute
-reader will note this is the same index as in the previous
-section, I am adding paths to the same route, the load-balance is
-in-place modified again). Each choice in LB 20 is another LB
-contributed by the IGP route through which the route's paths recurse.
-
-So what's the equivalent in BGP to a link down in the IGP? An IGP link
-down means it loses its peering out of that link, so the equivalent in
-BGP is the loss of the peering and thus the loss of reachability to
-the peer. This is signaled by the IGP withdrawing the route to the
-peer. But "Wait wait wait", i hear you say ... "just because the IGP
-withdraws 1.1.1.1/32 doesn't mean I can't reach 1.1.1.1, perhaps there
-is a less specific route that gives reachability to 1.1.1.1". Indeed
-there may be. So a little more on BGP network design. I know it's like
-a bad detective novel where the author drip feeds you the plot... When
-describing iBGP peerings one 'always' describes the peer using one of
-its GigEthernet0/0/back addresses. Why? A GigEthernet0/0/back interface
-never goes down (unless you admin down it yourself), some muppet can't
-accidentally cut through the GigEthernet0/0/back cable whilst digging up the
-street. And what subnet mask length does a prefix have on a GigEthernet0/0/back
-interface? it's 'always' a /32. Why? because there's no cable to connect
-any other devices. This choice justifies there 'always' being a /32
-route for the BGP peer. But what prevents there not being a less
-specific - nothing.
-Now clearly if the BGP peer crashes then the /32 for its GigEthernet0/0/back is
-going to be removed from the IGP, but what will withdraw the less
-specific - nothing.
-
-So in order to make use of this trick of relying on the withdrawal of
-the /32 for the peer to signal that the peer is down and thus the
-signal to converge the FIB, we need to force FIB to recurse only via
-the /32 and not via a less specific. This is called a 'recursion
-constraint'. In this case the constraint is 'recurse via host'
-i.e. for ipv4 use a /32.
-So we need to update our route additions from before:
-
-.. code-block:: console
-
- ip route add 8.0.0.0/16 via 1.1.1.1 resolve-via-host
- ip route add 8.0.0.0/16 via 1.1.1.2 resolve-via-host
-
-checking the FIB output is left as an exercise to the reader. I hope
-you're doing these configs as you read. There's little change in the
-output, you'll see some extra flags on the paths.
-
-Now let's add the less specific, just for fun:
-
-
-.. code-block:: console
-
- ip route add 1.1.1.0/28 via 10.0.0.2 GigEthernet0/0/0
-
-nothing changes in resolution of 8.0.0.0/16.
-
-Now withdraw the route to 1.1.1.2/32:
-
-.. code-block:: console
-
- ip route del 1.1.1.2/32 via 10.0.0.2 GigEthernet0/0/0
-
-In the FIB we see:
-
-.. code-block:: console
-
- DBGvpp# sh ip fib 8.0.0.0/32
- ipv4-VRF:0, fib_index:0, flow hash:[src dst sport dport proto ] epoch:0 flags:none locks:[adjacency:1, recursive-resolution:2, default-route:1, ]
- 8.0.0.0/16 fib:0 index:18 locks:2
- API refs:1 src-flags:added,contributing,active,
- path-list:[15] locks:2 flags:shared, uPRF-list:13 len:2 itfs:[1, 2, ]
- path:[15] pl-index:15 ip4 weight=1 pref=0 recursive: oper-flags:resolved, cfg-flags:resolve-host,
- via 1.1.1.1 in fib:0 via-fib:15 via-dpo:[dpo-load-balance:17]
- path:[17] pl-index:15 ip4 weight=1 pref=0 recursive: cfg-flags:resolve-host,
- via 1.1.1.2 in fib:0 via-fib:10 via-dpo:[dpo-drop:0]
-
- forwarding: unicast-ip4-chain
- [@0]: dpo-load-balance: [proto:ip4 index:20 buckets:1 uRPF:13 to:[0:0]]
- [0] [@12]: dpo-load-balance: [proto:ip4 index:17 buckets:2 uRPF:27 to:[0:0]]
- [0] [@5]: ipv4 via 10.0.0.2 GigEthernet0/0/0: mtu:9000 next:3 001122334455dead000000000800
- [1] [@5]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
-
-the path via 1.1.1.2 is unresolved, because the recursion constraints
-are preventing the the path resolving via 1.1.1.0/28. the LB index 20
-has been updated to remove the unresolved path.
-
-Job done? Not quite! Why not?
-
-Let's re-examine the goals of this chapter. We wanted to update 'a
-few' objects, which we have defined as not all the millions of
-recursive routes. Did we do that here? We sure did, when we
-modified LB index 20. So WTF?? Where's the indirection object that can
-be modified so that the LBs for the recursive routes are not
-modified - it's not there.... WTF?
-
-OK so the great detective has assembled all the suspects in the
-drawing room and only now does he drop the bomb; the FIB knows the
-scale, we talked above about what the scale **can** be, worst case
-scenario, but that's not necessarily what it is in this hypothetical
-(your) deployment. It knows how many recursive routes there are that
-depend on a /32, it can thus make its own determination of the
-definition of 'a few'. In other words, if there are only 'a few'
-recursive prefixes that depend on a /32 then it will update them
-synchronously (and we'll discuss what synchronously means a bit more later).
-
-So what does FIB consider to be 'a few'. Let's add more routes and
-find out.
-
-.. code-block:: console
-
- DBGvpp# ip route add 8.1.0.0/16 via 1.1.1.2 resolve-via-host via 1.1.1.1 resolve-via-host
- ...
- DBGvpp# ip route add 8.63.0.0/16 via 1.1.1.2 resolve-via-host via 1.1.1.1 resolve-via-host
-
-and we see:
-
-.. code-block:: console
-
- DBGvpp# sh ip fib 8.8.0.0
- ipv4-VRF:0, fib_index:0, flow hash:[src dst sport dport proto ] epoch:0 flags:none locks:[adjacency:1, recursive-resolution:4, default-route:1, ]
- 8.8.0.0/16 fib:0 index:77 locks:2
- API refs:1 src-flags:added,contributing,active,
- path-list:[15] locks:128 flags:shared,popular, uPRF-list:28 len:2 itfs:[1, 2, ]
- path:[17] pl-index:15 ip4 weight=1 pref=0 recursive: oper-flags:resolved, cfg-flags:resolve-host,
- via 1.1.1.1 in fib:0 via-fib:15 via-dpo:[dpo-load-balance:17]
- path:[15] pl-index:15 ip4 weight=1 pref=0 recursive: oper-flags:resolved, cfg-flags:resolve-host,
- via 1.1.1.2 in fib:0 via-fib:10 via-dpo:[dpo-load-balance:12]
-
- forwarding: unicast-ip4-chain
- [@0]: dpo-load-balance: [proto:ip4 index:79 buckets:2 uRPF:28 flags:[uses-map] to:[0:0]]
- load-balance-map: index:0 buckets:2
- index: 0 1
- map: 0 1
- [0] [@12]: dpo-load-balance: [proto:ip4 index:17 buckets:2 uRPF:27 to:[0:0]]
- [0] [@5]: ipv4 via 10.0.0.2 GigEthernet0/0/0: mtu:9000 next:3 001122334455dead000000000800
- [1] [@5]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
- [1] [@12]: dpo-load-balance: [proto:ip4 index:12 buckets:1 uRPF:18 to:[0:0]]
- [0] [@3]: arp-ipv4: via 10.0.1.2 GigEthernet0/0/0
-
-
-Two elements to note here; the path-list has the 'popular' flag and
-there is a load-balance map in the forwarding path.
-
-'popular' in this case means that the path-list has passed the limit
-of 'a few' in the number of children it has.
-
-here are the children:
-
-.. code-block:: console
-
- DBGvpp# sh fib path-list 15
- path-list:[15] locks:128 flags:shared,popular, uPRF-list:28 len:2 itfs:[1, 2, ]
- path:[17] pl-index:15 ip4 weight=1 pref=0 recursive: oper-flags:resolved, cfg-flags:resolve-host,
- via 1.1.1.1 in fib:0 via-fib:15 via-dpo:[dpo-load-balance:17]
- path:[15] pl-index:15 ip4 weight=1 pref=0 recursive: oper-flags:resolved, cfg-flags:resolve-host,
- via 1.1.1.2 in fib:0 via-fib:10 via-dpo:[dpo-load-balance:12]
- children:{entry:18}{entry:21}{entry:22}{entry:23}{entry:25}{entry:26}{entry:27}{entry:28}{entry:29}{entry:30}{entry:31}{entry:32}{entry:33}{entry:34}{entry:35}{entry:36}{entry:37}{entry:38}{entry:39}{entry:40}{entry:41}{entry:42}{entry:43}{entry:44}{entry:45}{entry:46}{entry:47}{entry:48}{entry:49}{entry:50}{entry:51}{entry:52}{entry:53}{entry:54}{entry:55}{entry:56}{entry:57}{entry:58}{entry:59}{entry:60}{entry:61}{entry:62}{entry:63}{entry:64}{entry:65}{entry:66}{entry:67}{entry:68}{entry:69}{entry:70}{entry:71}{entry:72}{entry:73}{entry:74}{entry:75}{entry:76}{entry:77}{entry:78}{entry:79}{entry:80}{entry:81}{entry:82}{entry:83}{entry:84}
-
-64 children makes it popular. The number is fixed (there is no API to
-change it). Its choice is an attempt to balance the performance cost
-of the indirection performance degradation versus the convergence
-gain.
-
-Popular path-lists contribute the load-balance map, this is the
-missing indirection object. Its indirection happens when choosing the
-bucket in the LB. The packet's flow-hash is taken 'mod number of
-buckets' to give the 'candidate bucket' then the map will take this
-'index' and convert it into the 'map'. You can see in the example above
-that no change occurs, i.e. if the flow-hash mod n chooses bucket 1
-then it gets bucket 1.
-
-Why is this useful? The path-list is shared (you can convince
-yourself of this if you look at each of the 8.x.0.0/16 routes we
-added) and all of these routes use the same load-balance map, therefore, to
-converge all the recursive routs, we need only change the map and
-we're good; we again get PIC.
-
-OK who's still awake... if you're thinking there's more to this story,
-you're right. Keep reading.
-
-This failure scenario is called iBGP PIC edge. It's 'edge' because it
-refers to the loss of an edge device, and iBGP because the device was
-a iBGP peer (we learn iBGP peers in the IGP). There is a similar eBGP
-PIC edge scenario, but this is left for an exercise to the reader (hint
-there are other recursion constraints - see the RFC).
-
-Which Objects
-^^^^^^^^^^^^^
-
-The next topic on our list of how to converge quickly was to
-effectively find the objects that need to be updated when a converge
-event happens. If you haven't realised by now that the FIB is an
-object graph, then can I politely suggest you go back and start from
-the beginning ...
-
-Finding the objects affected by a change is simply a matter of walking
-from the parent (the object affected) to its children. These
-dependencies are kept really for this reason.
-
-So is fast convergence just a matter of walking the graph? Yes and
-no. The question to ask yourself is this, "in the case of iBGP PIC edge,
-when the /32 is withdrawn, what is the list of objects that need to be
-updated and particularly what is the order they should be updated in
-order to obtain the best convergence time?" Think breadth v. depth first.
-
-... ponder for a while ...
-
-For iBGP PIC edge we said it's the path-list that provides the
-indirection through the load-balance map. Hence once all path-lists
-are updated we are converged, thereafter, at our leisure, we can
-update the child recursive prefixes. Is the breadth or depth first?
-
-It's breadth first.
-
-Breadth first walks are achieved by spawning an async walk of the
-branch of the graph that we don't want to traverse. Withdrawing the /32
-triggers a synchronous walk of the children of the /32 route, we want
-a synchronous walk because we want to converge ASAP. This synchronous
-walk will encounter path-lists in the /32 route's child dependent list.
-These path-lists (and thier LB maps) will be updated. If a path-list is
-popular, then it will spawn a async walk of the path-list's child
-dependent routes, if not it will walk those routes. So the walk
-effectively proceeds breadth first across the path-lists, then returns
-to the start to do the affected routes.
-
-Now the story is complete. The murderer is revealed.
-
-Let's withdraw one of the IGP routes.
-
-.. code-block:: console
-
- DBGvpp# ip route del 1.1.1.2/32 via 10.0.1.2 GigEthernet0/0/1
-
- DBGvpp# sh ip fib 8.8.0.0
- ipv4-VRF:0, fib_index:0, flow hash:[src dst sport dport proto ] epoch:0 flags:none locks:[adjacency:1, recursive-resolution:4, default-route:1, ]
- 8.8.0.0/16 fib:0 index:77 locks:2
- API refs:1 src-flags:added,contributing,active,
- path-list:[15] locks:128 flags:shared,popular, uPRF-list:18 len:2 itfs:[1, 2, ]
- path:[17] pl-index:15 ip4 weight=1 pref=0 recursive: oper-flags:resolved, cfg-flags:resolve-host,
- via 1.1.1.1 in fib:0 via-fib:15 via-dpo:[dpo-load-balance:17]
- path:[15] pl-index:15 ip4 weight=1 pref=0 recursive: cfg-flags:resolve-host,
- via 1.1.1.2 in fib:0 via-fib:10 via-dpo:[dpo-drop:0]
-
- forwarding: unicast-ip4-chain
- [@0]: dpo-load-balance: [proto:ip4 index:79 buckets:1 uRPF:18 to:[0:0]]
- [0] [@12]: dpo-load-balance: [proto:ip4 index:17 buckets:2 uRPF:27 to:[0:0]]
- [0] [@5]: ipv4 via 10.0.0.2 GigEthernet0/0/0: mtu:9000 next:3 001122334455dead000000000800
- [1] [@5]: ipv4 via 10.0.1.2 GigEthernet0/0/1: mtu:9000 next:4 001111111111dead000000010800
-
-the LB Map has gone, since the prefix now only has one path. You'll
-need to be a CLI ninja if you want to catch the output showing the LB
-map in its transient state of:
-
-.. code-block:: console
-
- load-balance-map: index:0 buckets:2
- index: 0 1
- map: 0 0
-
-but it happens. Trust me. I've got tests and everything.
-
-On the final topic of how to converge quickly; 'make each update fast'
-there are no tricks.
-
-
-