)]}' { "log": [ { "commit": "60cc95921ae663de325ca3e76e8c05d8224986ab", "tree": "7d78102aa9650da4bba1355b2a6601135d687b37", "parents": [ "4feb0d02c029e2e4f229f6283f579b8673b0ac11" ], "author": { "name": "Pradosh Mohapatra", "email": "pmohapat@cumulusnetworks.com", "time": "Mon Nov 09 20:21:41 2015 -0500" }, "committer": { "name": "Paul Jakma", "email": "paul.jakma@hpe.com", "time": "Tue Sep 13 10:36:44 2016 +0100" }, "message": "bgpd, doc, lib, zebra: nexthop-tracking in zebra\n\n0. Introduction\n\nThis is the design specification for next hop tracking feature in\nQuagga.\n\n1. Background\n\nRecursive routes are of the form:\n\n p/m --\u003e n\n [Ex: 1.1.0.0/16 --\u003e 2.2.2.2]\n\nwhere \u0027n\u0027 itself is resolved through another route as follows:\n\n p2/m --\u003e h, interface\n [Ex: 2.2.2.0/24 --\u003e 3.3.3.3, eth0]\n\nUsually, BGP routes are recursive in nature and BGP nexthops get\nresolved through an IGP route. IGP usually adds its routes pointing to\nan interface (these are called non-recursive routes).\n\nWhen BGP receives a recursive route from a peer, it needs to validate\nthe nexthop. The path is marked valid or invalid based on the\nreachability status of the nexthop. Nexthop validation is also\nimportant for BGP decision process as the metric to reach the nexthop\nis a parameter to best path selection process.\n\nAs it goes with routing, this is a dynamic process. Route to the\nnexthop can change. The nexthop can become unreachable or\nreachable. In the current BGP implementation, the nexthop validation\nis done periodically in the scanner run. The default scanner run\ninterval is one minute. Every minute, the scanner task walks the\nentire BGP table. It checks the validity of each nexthop with Zebra\n(the routing table manager) through a request and response message\nexchange between BGP and Zebra process. BGP process is blocked for\nthat duration. The mechanism has two major drawbacks:\n\n(1) The scanner task runs to completion. That can potentially starve\n the other tasks for long periods of time, based on the BGP table\n size and number of nexthops.\n\n(2) Convergence around routing changes that affect the nexthops can be\n long (around a minute with the default intervals). The interval\n can be shortened to achieve faster reaction time, but it makes the\n first problem worse, with the scanner task consuming most of the\n CPU resources.\n\n\"Next hop tracking\" feature makes this process event-driven. It\neliminates periodic nexthop validation and introduces an asynchronous\ncommunication path between BGP and Zebra for route change notifications\nthat can then be acted upon.\n\n2. Goal\n\nStating the obvious, the main goal is to remove the two limitations we\ndiscussed in the previous section. The goals, in a constructive tone,\nare the following:\n\n- fairness: the scanner run should not consume an unjustly high amount\n of CPU time. This should give an overall good performance and\n response time to other events (route changes, session events,\n IO/user interface).\n\n- convergence: BGP must react to nexthop changes instantly and provide\n sub-second convergence. This may involve diverting the routes from\n one nexthop to another.\n\n3. Overview of the changes\n\nThe changes are in both BGP and Zebra modules. The short summary is\nthe following:\n\n- Zebra implements a registration mechanism by which clients can\n register for next hop notification. Consequently, it maintains a\n separate table, per (VRF, AF) pair, of next hops and interested\n client-list per next hop.\n\n- When the main routing table changes in Zebra, it evaluates the next\n hop table: for each next hop, it checks if the route table\n modifications have changed its state. If so, it notifies the\n interested clients.\n\n- BGP is one such client. It registers the next hops corresponding to\n all of its received routes/paths. It also threads the paths against\n each nexthop structure.\n\n- When BGP receives a next hop notification from Zebra, it walks the\n corresponding path list. It makes them valid or invalid depending\n on the next hop notification. It then re-computes best path for the\n corresponding destination. This may result in re-announcing those\n destinations to peers.\n\n4. Design\n\n4.1. Modules\n\nThe core design introduces an \"nht\" (next hop tracking) module in BGP\nand \"rnh\" (recursive nexthop) module in Zebra. The \"nht\" module\nprovides the following APIs:\n\nbgp_find_or_add_nexthop() : find or add a nexthop in BGP nexthop table\nbgp_find_nexthop() : find a nexthop in BGP nexthop table\nbgp_parse_nexthop_update() : parse a nexthop update message coming\n from zebra\n\nThe \"rnh\" module provides the following APIs:\n\nzebra_add_rnh() : add a recursive nexthop\nzebra_delete_rnh() : delete a recursive nexthop\nzebra_lookup_rnh() : lookup a recursive nexthop\n\nzebra_add_rnh_client() : register a client for nexthop notifications\n against a recursive nexthop\n\nzebra_remove_rnh_client(): remove the client registration for a\n recursive nexthop\n\nzebra_evaluate_rnh_table(): (re)evaluate the recursive nexthop table\n (most probably because the main routing\n table has changed).\n\nzebra_cleanup_rnh_client(): Cleanup a client from the \"rnh\" module\n data structures (most probably because the\n client is going away).\n\n4.2. Control flow\n\nThe next hop registration control flow is the following:\n\n\u003c\u003d\u003d\u003d\u003d BGP Process \u003d\u003d\u003d\u003d\u003e|\u003c\u003d\u003d\u003d\u003d Zebra Process \u003d\u003d\u003d\u003d\u003e\n |\nreceive module nht module | zserv module rnh module\n----------------------------------------------------------------------\n | | |\nbgp_update_ | | |\n main() | bgp_find_or_add_ | |\n | nexthop() | |\n | | |\n | | zserv_nexthop_ |\n | | register() |\n | | | zebra_add_rnh()\n | | |\n\nThe next hop notification control flow is the following:\n\n\u003c\u003d\u003d\u003d\u003d Zebra Process \u003d\u003d\u003d\u003d\u003e|\u003c\u003d\u003d\u003d\u003d BGP Process \u003d\u003d\u003d\u003d\u003e\n |\nrib module rnh module | zebra module nht module\n----------------------------------------------------------------------\n | | |\nmeta_queue_ | | |\n process() | zebra_evaluate_ | |\n | rnh_table() | |\n | | |\n | | bgp_read_nexthop_ |\n | | update() |\n | | | bgp_parse_\n | | | nexthop_update()\n | | |\n\n4.3. zclient message format\n\nZEBRA_NEXTHOP_REGISTER and ZEBRA_NEXTHOP_UNREGISTER messages are\nencoded in the following way:\n\n/*\n * 0 1 2 3\n * 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\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * | AF | prefix len |\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * . Nexthop prefix .\n * . .\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * . .\n * . .\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * | AF | prefix len |\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * . Nexthop prefix .\n * . .\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n */\n\nZEBRA_NEXTHOP_UPDATE message is encoded as follows:\n\n/*\n * 0 1 2 3\n * 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\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * | AF | prefix len |\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * . Nexthop prefix getting resolved .\n * . .\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * | metric |\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * | #nexthops |\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * | nexthop type |\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * . resolving Nexthop details .\n * . .\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * . .\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * | nexthop type |\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n * . resolving Nexthop details .\n * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n */\n\n4.4. BGP data structure\n\nLegend:\n\n/\\ struct bgp_node: a BGP destination/route/prefix\n\\/\n\n[ ] struct bgp_info: a BGP path (e.g. route received from a peer)\n\n _\n(_) struct bgp_nexthop_cache: a BGP nexthop\n\n /\\ NULL\n \\/--+ ^\n | :\n +--[ ]--[ ]--[ ]--\u003e NULL\n /\\ :\n \\/--+ :\n | :\n +--[ ]--[ ]--\u003e NULL\n :\n _ :\n (_).............\n\n4.5. Zebra data structure\n\nrnh table:\n\n O\n / \\\n O O\n / \\\n O O\n\n struct rnh\n {\n u_char flags;\n struct rib *state;\n struct list *client_list;\n struct route_node *node;\n };\n\n5. User interface changes\n\nquagga# show ip nht\n3.3.3.3\n resolved via kernel\n via 11.0.0.6, swp1\n Client list: bgp(fd 12)\n11.0.0.10\n resolved via connected\n is directly connected, swp2\n Client list: bgp(fd 12)\n11.0.0.18\n resolved via connected\n is directly connected, swp4\n Client list: bgp(fd 12)\n11.11.11.11\n resolved via kernel\n via 10.0.1.2, eth0\n Client list: bgp(fd 12)\n\nquagga# show ip bgp nexthop\nCurrent BGP nexthop cache:\n 3.3.3.3 valid [IGP metric 0], #paths 3\n Last update: Wed Oct 16 04:43:49 2013\n\n 11.0.0.10 valid [IGP metric 1], #paths 1\n Last update: Wed Oct 16 04:43:51 2013\n\n 11.0.0.18 valid [IGP metric 1], #paths 2\n Last update: Wed Oct 16 04:43:47 2013\n\n 11.11.11.11 valid [IGP metric 0], #paths 1\n Last update: Wed Oct 16 04:43:47 2013\n\nquagga# show ipv6 nht\nquagga# show ip bgp nexthop detail\n\nquagga# debug bgp nht\nquagga# debug zebra nht\n\n6. Sample test cases\n\n r2----r3\n / \\ /\n r1----r4\n\n- Verify that a change in IGP cost triggers NHT\n + shutdown the r1-r4 and r2-r4 links\n + no shut the r1-r4 and r2-r4 links and wait for OSPF to come back\n up\n + We should be back to the original nexthop via r4 now\n- Verify that a NH becoming unreachable triggers NHT\n + Shutdown all links to r4\n- Verify that a NH becoming reachable triggers NHT\n + no shut all links to r4\n\n7. Future work\n\n- route-policy for next hop validation (e.g. ignore default route)\n- damping for rapid next hop changes\n- prioritized handling of nexthop changes ((un)reachability vs. metric\n changes)\n- handling recursion loop, e.g.\n 11.11.11.11/32 -\u003e 12.12.12.12\n 12.12.12.12/32 -\u003e 11.11.11.11\n 11.0.0.0/8 -\u003e \u003cinterface\u003e\n- better statistics\nAddresses upstream comments.\n\n\"show ip bgp nexthop detail\" couldn\u0027t display multiple NHs due to a bug.\nFix that.\n\nFix reference counts for the nexthop cache entries\n\nSigned-off-by: Pradosh Mohapatra \u003cpmohapat@cumulusnetworks.com\u003e\nSigned-off-by: Daniel Walton \u003cdwalton@cumulusnetworks.com\u003e\nSigned-off-by: Dinesh Dutt \u003cddutt@cumulusnetworks.com\u003e\nSigned-off-by: Donald Sharp \u003csharpd@cumulusnetworks.com\u003e\nSigned-off-by: Vivek Venkatraman \u003cvivek@cumulusnetworks.com\u003e\n\nFix reference counts for the nexthop cache entries.\n\nSigned-off-by: Vivek Venkatraman \u003cvivek@cumulusnetworks.com\u003e\n\nEdited-by: Paul Jakma \u003cpaul.jakma@hpe.com\u003e\n- Fix nexthop_ipv6_add defs in rib.h not having been modified with rib_ prefix.\n- Remove rib_lookup_and_pushup, appears not to be used except for\n !HAVE_NETLINK \u0026\u0026 HAVE_STRUCT_IFALIASREQ case of ioctl.c::if_set_prefix,\n so it\u0027s not being used at all on platform with most testing of RIB.\n" }, { "commit": "aef4650851cf0f74d944466d50e26bb8f8635c3d", "tree": "0fa32e61bc3c9d715247091fd3003690b3e056a1", "parents": [ "bb01bdd740339b0c07d8ed0786811801b2a79192" ], "author": { "name": "Stas Nichiporovich", "email": "stas@iptel.by", "time": "Tue Apr 26 08:14:36 2016 +0000" }, "committer": { "name": "Donald Sharp", "email": "sharpd@cumulusnetworks.com", "time": "Fri Apr 29 19:46:16 2016 -0400" }, "message": "zebra: fix crash caused by using route-map with \"set src\"\n\nSigned-off-by: Stas Nichiporovich \u003cstas@iptel.by\u003e\nTested-by: NetDEF CI System \u003ccisystem@netdef.org\u003e\n" }, { "commit": "9099f9b2a66e86f8a90d7fe18f61bd2bb1bc6744", "tree": "1ce5d2e4ecff6b57eb00d40b1a91b3f363ff35fe", "parents": [ "954c7d6bcd04c2cf037965adda0f9d11afdcd165" ], "author": { "name": "Paul Jakma", "email": "paul.jakma@hpe.com", "time": "Mon Jan 18 10:12:10 2016 +0000" }, "committer": { "name": "Paul Jakma", "email": "paul.jakma@hpe.com", "time": "Fri Feb 26 14:11:46 2016 +0000" }, "message": "*: use an ifindex_t type, defined in lib/if.h, for ifindex values\n" }, { "commit": "8970f74ec77f93eb862ab8803d9d7c76c7128940", "tree": "9659720ad515d0aea454ab42bc424ea34150f7b9", "parents": [ "1885d0a5274cd78e46ad6c22171a5240a2f27f64" ], "author": { "name": "Feng Lu", "email": "lu.feng@6wind.com", "time": "Fri May 22 11:40:05 2015 +0200" }, "committer": { "name": "David Lamparter", "email": "equinox@opensourcerouting.org", "time": "Tue Jun 02 07:48:34 2015 +0200" }, "message": "zebra: lookup the address in all VRFs when set the route-map rule \"set src\"\n\nWhen configuring the route-map rule \"set src A.B.C.D\", it checked\nwhether the source address exists on some interface.\n\nNow it checks the source address throughout all VRFs.\n\nSigned-off-by: Feng Lu \u003clu.feng@6wind.com\u003e\nReviewed-by: Alain Ritoux \u003calain.ritoux@6wind.com\u003e\nSigned-off-by: Nicolas Dichtel \u003cnicolas.dichtel@6wind.com\u003e\nAcked-by: Vincent JARDIN \u003cvincent.jardin@6wind.com\u003e\nSigned-off-by: David Lamparter \u003cequinox@opensourcerouting.org\u003e\n" }, { "commit": "1885d0a5274cd78e46ad6c22171a5240a2f27f64", "tree": "acaf9496dcdd722400d5634e58180f17350cc0b6", "parents": [ "4364ee5b6f65008fe19225f05e489ad8257a7df8" ], "author": { "name": "Feng Lu", "email": "lu.feng@6wind.com", "time": "Fri May 22 11:40:04 2015 +0200" }, "committer": { "name": "David Lamparter", "email": "equinox@opensourcerouting.org", "time": "Tue Jun 02 07:48:34 2015 +0200" }, "message": "zebra: let the route-map rule \"match interface\" work for VRFs\n\nIntroduce a new \"struct nexthop_vrfid\" to specify a nexthop together\nwith the VRF ID it belongs to.\n\nThus in route_match_interface(), we can lookup the interface from\nthe correct VRF.\n\nSigned-off-by: Feng Lu \u003clu.feng@6wind.com\u003e\nReviewed-by: Alain Ritoux \u003calain.ritoux@6wind.com\u003e\nSigned-off-by: Nicolas Dichtel \u003cnicolas.dichtel@6wind.com\u003e\nAcked-by: Vincent JARDIN \u003cvincent.jardin@6wind.com\u003e\nSigned-off-by: David Lamparter \u003cequinox@opensourcerouting.org\u003e\n" }, { "commit": "6b0655a25194c7c0331154edaa6124cf783e5e5e", "tree": "c0c7d479f2684531249668210da27a60322ba395", "parents": [ "fdb913aedb5a9807ad60715e8badb4f25d57acea" ], "author": { "name": "David Lamparter", "email": "equinox@opensourcerouting.org", "time": "Wed Jun 04 06:53:35 2014 +0200" }, "committer": { "name": "David Lamparter", "email": "equinox@opensourcerouting.org", "time": "Wed Jun 04 06:58:02 2014 +0200" }, "message": "*: nuke ^L (page feed)\n\nQuagga sources have inherited a slew of Page Feed (^L, \\xC) characters\nfrom ancient history. Among other things, these break patchwork\u0027s\nXML-RPC API because \\xC is not a valid character in XML documents.\n\nNuke them from high orbit.\n\nPatches can be adapted simply by:\n\tsed -e \u0027s%^L%%\u0027 -i filename.patch\n(you can type page feeds in some environments with Ctrl-V Ctrl-L)\n\nSigned-off-by: David Lamparter \u003cequinox@opensourcerouting.org\u003e\n" }, { "commit": "fa713d9ee5ed30dedd0a290be9aaff780a2896be", "tree": "1d263cce70c341f3f2a73a47d4b1cd5a38b09129", "parents": [ "bfac8dcd2fe7ed099a679b5c8245599c6d0312ed" ], "author": { "name": "Christian Franke", "email": "chris@opensourcerouting.org", "time": "Fri Jul 05 15:35:37 2013 +0000" }, "committer": { "name": "David Lamparter", "email": "equinox@opensourcerouting.org", "time": "Thu Sep 19 18:04:40 2013 +0200" }, "message": "zebra: rework recursive route resolution\n\nChange the datastructure for recursive routes. This brings the following\nbenefits:\n\nBy using struct nexthop also to store nexthops obtained by recursive\nresolution, we can get rid of quite a bit of code duplication in the fib\nmanagement. (rt_netlink, rt_socket, ...)\n\nWith the new datastructure we can make use of all available paths when\nrecursive routes are resolved with multipath routes.\n\nSigned-off-by: Christian Franke \u003cchris@opensourcerouting.org\u003e\nSigned-off-by: David Lamparter \u003cequinox@opensourcerouting.org\u003e\n" }, { "commit": "8dd1a8daae0b15065d54c46f82d44d21aa7a2320", "tree": "b14e8ed07f1a6ee97de84262bb85cd0a50f9c250", "parents": [ "fdbc8e77c88f751924299d0bc752371d5cc31116" ], "author": { "name": "Paul Jakma", "email": "paul@quagga.net", "time": "Mon Apr 11 16:33:20 2011 +0100" }, "committer": { "name": "Paul Jakma", "email": "paul@quagga.net", "time": "Wed Apr 13 15:13:33 2011 +0100" }, "message": "zebra: trivial warning fix\n\n* zebra_routemap.c: (route_set_src) get rid of the dummy family variable.\n" }, { "commit": "093033144658c5d914429fad5b0a6cf952f20943", "tree": "02e4c24a9ca95a37bb3995bdc6e0f7e3222f2b87", "parents": [ "7ab62c5319bd86a3cfda32351bc4103cf9517f26" ], "author": { "name": "Andrew J. Schorr", "email": "ajschorr@alumni.princeton.edu", "time": "Wed May 30 20:10:34 2007 +0000" }, "committer": { "name": "Andrew J. Schorr", "email": "ajschorr@alumni.princeton.edu", "time": "Wed May 30 20:10:34 2007 +0000" }, "message": "[zebra] Trivial patches so we can compile when IPv6 is not enabled\n\n2007-05-30 Andrew J. Schorr \u003cajschorr@alumni.princeton.edu\u003e\n\n\t* zebra_routemap.c: (route_set_src_compile) Use \u0027#ifdef HAVE_IPV6\u0027\n\t as needed.\n\t* zebra_vty.c: (vty_show_ip_route_detail, vty_show_ip_route) Use\n\t \u0027#ifdef HAVE_IPV6\u0027 as needed.\n\t (show_ip_protocol) Move function definition outside of\n\t \u0027#ifdef HAVE_IPV6\u0027 section.\n" }, { "commit": "5921ef9aae3b5d6ff8663298f649fb9d76594acd", "tree": "5164adafc18404f698563fb9044a11780927926c", "parents": [ "7514fb7739f74311830e9ddd1381d0d228224f61" ], "author": { "name": "Paul Jakma", "email": "paul.jakma@sun.com", "time": "Fri May 04 20:13:20 2007 +0000" }, "committer": { "name": "Paul Jakma", "email": "paul.jakma@sun.com", "time": "Fri May 04 20:13:20 2007 +0000" }, "message": "[zebra] Add zebra_routemap.c\n\n\t* zebra_routemap.c should have been in the commit of Steven\u0027s\n\t routemap patch.\n" } ] }