diff options
Diffstat (limited to 'docs/gettingstarted/developers/fib20/fastconvergence.rst')
| -rw-r--r-- | docs/gettingstarted/developers/fib20/fastconvergence.rst | 576 |
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. - - - |