4 Next hop tracking is an optimization feature that reduces the processing time
5 involved in the BGP bestpath algorithm by monitoring changes to the routing
11 Recursive routes are of the form:
16 [Ex: 1.1.0.0/16 --> 2.2.2.2]
18 where 'n' itself is resolved through another route as follows:
23 [Ex: 2.2.2.0/24 --> 3.3.3.3, eth0]
25 Usually, BGP routes are recursive in nature and BGP nexthops get resolved
26 through an IGP route. IGP usually adds its routes pointing to an interface
27 (these are called non-recursive routes).
29 When BGP receives a recursive route from a peer, it needs to validate the
30 nexthop. The path is marked valid or invalid based on the reachability status
31 of the nexthop. Nexthop validation is also important for BGP decision process
32 as the metric to reach the nexthop is a parameter to best path selection
35 As it goes with routing, this is a dynamic process. Route to the nexthop can
36 change. The nexthop can become unreachable or reachable. In the current BGP
37 implementation, the nexthop validation is done periodically in the scanner run.
38 The default scanner run interval is one minute. Every minute, the scanner task
39 walks the entire BGP table. It checks the validity of each nexthop with Zebra
40 (the routing table manager) through a request and response message exchange
41 between BGP and Zebra process. BGP process is blocked for that duration. The
42 mechanism has two major drawbacks:
44 - The scanner task runs to completion. That can potentially starve the other
45 tasks for long periods of time, based on the BGP table size and number of
48 - Convergence around routing changes that affect the nexthops can be long
49 (around a minute with the default intervals). The interval can be shortened
50 to achieve faster reaction time, but it makes the first problem worse, with
51 the scanner task consuming most of the CPU resources.
53 The next-hop tracking feature makes this process event-driven. It eliminates
54 periodic nexthop validation and introduces an asynchronous communication path
55 between BGP and Zebra for route change notifications that can then be acted
61 Stating the obvious, the main goal is to remove the two limitations we
62 discussed in the previous section. The goals, in a constructive tone,
65 - **Fairness**: the scanner run should not consume an unjustly high amount of
66 CPU time. This should give an overall good performance and response time to
67 other events (route changes, session events, IO/user interface).
69 - **Convergence**: BGP must react to nexthop changes instantly and provide
70 sub-second convergence. This may involve diverting the routes from one
74 ------------------------
76 The changes are in both BGP and Zebra modules. The short summary is
79 - Zebra implements a registration mechanism by which clients can
80 register for next hop notification. Consequently, it maintains a
81 separate table, per (VRF, AF) pair, of next hops and interested
82 client-list per next hop.
84 - When the main routing table changes in Zebra, it evaluates the next
85 hop table: for each next hop, it checks if the route table
86 modifications have changed its state. If so, it notifies the
89 - BGP is one such client. It registers the next hops corresponding to
90 all of its received routes/paths. It also threads the paths against
91 each nexthop structure.
93 - When BGP receives a next hop notification from Zebra, it walks the
94 corresponding path list. It makes them valid or invalid depending
95 on the next hop notification. It then re-computes best path for the
96 corresponding destination. This may result in re-announcing those
97 destinations to peers.
105 The core design introduces an "nht" (next hop tracking) module in BGP
106 and "rnh" (recursive nexthop) module in Zebra. The "nht" module
107 provides the following APIs:
109 +----------------------------+--------------------------------------------------+
110 | Function | Action |
111 +============================+==================================================+
112 | bgp_find_or_add_nexthop() | find or add a nexthop in BGP nexthop table |
113 +----------------------------+--------------------------------------------------+
114 | bgp_find_nexthop() | find a nexthop in BGP nexthop table |
115 +----------------------------+--------------------------------------------------+
116 | bgp_parse_nexthop_update() | parse a nexthop update message coming from zebra |
117 +----------------------------+--------------------------------------------------+
119 The "rnh" module provides the following APIs:
121 +----------------------------+----------------------------------------------------------------------------------------------------------+
122 | Function | Action |
123 +============================+==========================================================================================================+
124 | zebra_add_rnh() | add a recursive nexthop |
125 +----------------------------+----------------------------------------------------------------------------------------------------------+
126 | zebra_delete_rnh() | delete a recursive nexthop |
127 +----------------------------+----------------------------------------------------------------------------------------------------------+
128 | zebra_lookup_rnh() | lookup a recursive nexthop |
129 +----------------------------+----------------------------------------------------------------------------------------------------------+
130 | zebra_add_rnh_client() | register a client for nexthop notifications against a recursive nexthop |
131 +----------------------------+----------------------------------------------------------------------------------------------------------+
132 | zebra_remove_rnh_client() | remove the client registration for a recursive nexthop |
133 +----------------------------+----------------------------------------------------------------------------------------------------------+
134 | zebra_evaluate_rnh_table() | (re)evaluate the recursive nexthop table (most probably because the main routing table has changed). |
135 +----------------------------+----------------------------------------------------------------------------------------------------------+
136 | zebra_cleanup_rnh_client() | Cleanup a client from the "rnh" module data structures (most probably because the client is going away). |
137 +----------------------------+----------------------------------------------------------------------------------------------------------+
141 The next hop registration control flow is the following:
145 <==== BGP Process ====>|<==== Zebra Process ====>
147 receive module nht module | zserv module rnh module
148 ----------------------------------------------------------------------
151 main() | bgp_find_or_add_ | |
156 | | | zebra_add_rnh()
160 The next hop notification control flow is the following:
164 <==== Zebra Process ====>|<==== BGP Process ====>
166 rib module rnh module | zebra module nht module
167 ----------------------------------------------------------------------
170 process() | zebra_evaluate_ | |
173 | | bgp_read_nexthop_ |
176 | | | nexthop_update()
180 zclient message format
181 ^^^^^^^^^^^^^^^^^^^^^^
183 ZEBRA_NEXTHOP_REGISTER and ZEBRA_NEXTHOP_UNREGISTER messages are
184 encoded in the following way:
189 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
190 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
192 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
198 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
200 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
203 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
206 ``ZEBRA_NEXTHOP_UPDATE`` message is encoded as follows:
211 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
212 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
214 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
215 . Nexthop prefix getting resolved .
217 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
219 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
221 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
223 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
224 . resolving Nexthop details .
226 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
228 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
230 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
231 . resolving Nexthop details .
232 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
241 /\ struct bgp_node: a BGP destination/route/prefix
244 [ ] struct bgp_path_info: a BGP path (e.g. route received from a peer)
247 (_) struct bgp_nexthop_cache: a BGP nexthop
252 +--[ ]--[ ]--[ ]--> NULL
276 struct route_entry *state;
277 struct list *client_list;
278 struct route_node *node;
281 User interface changes
282 ^^^^^^^^^^^^^^^^^^^^^^
290 Client list: bgp(fd 12)
292 resolved via connected
293 is directly connected, swp2
294 Client list: bgp(fd 12)
296 resolved via connected
297 is directly connected, swp4
298 Client list: bgp(fd 12)
302 Client list: bgp(fd 12)
304 frr# show ip bgp nexthop
305 Current BGP nexthop cache:
306 3.3.3.3 valid [IGP metric 0], #paths 3
307 Last update: Wed Oct 16 04:43:49 2013
309 11.0.0.10 valid [IGP metric 1], #paths 1
310 Last update: Wed Oct 16 04:43:51 2013
312 11.0.0.18 valid [IGP metric 1], #paths 2
313 Last update: Wed Oct 16 04:43:47 2013
315 11.11.11.11 valid [IGP metric 0], #paths 1
316 Last update: Wed Oct 16 04:43:47 2013
319 frr# show ip bgp nexthop detail
330 - Verify that a change in IGP cost triggers NHT
331 + shutdown the r1-r4 and r2-r4 links
332 + no shut the r1-r4 and r2-r4 links and wait for OSPF to come back
334 + We should be back to the original nexthop via r4 now
335 - Verify that a NH becoming unreachable triggers NHT
336 + Shutdown all links to r4
337 - Verify that a NH becoming reachable triggers NHT
338 + no shut all links to r4
343 - route-policy for next hop validation (e.g. ignore default route)
344 - damping for rapid next hop changes
345 - prioritized handling of nexthop changes ((un)reachability vs. metric
347 - handling recursion loop, e.g::
349 11.11.11.11/32 -> 12.12.12.12
350 12.12.12.12/32 -> 11.11.11.11
351 11.0.0.0/8 -> <interface>