summaryrefslogtreecommitdiffstats
path: root/bgpd/bgp_mpath.h (follow)
Commit message (Collapse)AuthorAgeFilesLines
* bgpd: Rename various variable names to something more appropriateDonald Sharp2018-10-091-2/+2
| | | | | | | | | ri -> pi bi -> bpi info -> path info -> rmap_path ( for routemap applications ) Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* bgpd: Convert all bgp_info_XXX functions to bgp_path_XXX functionsDonald Sharp2018-10-091-18/+21
| | | | | | Rename all bgp_info_XXX functions to bgp_path_XXX functions Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* bgpd: Convert `struct bgp_info` to `struct bgp_path_info`Donald Sharp2018-10-091-18/+21
| | | | | | | | | | | | Do a straight conversion of `struct bgp_info` to `struct bgp_path_info`. This commit will setup the rename of variables as well. This is being done because `struct bgp_info` is not descriptive of what this data actually is. It is path information for routes that we keep to build the actual routes nexthops plus some extra information. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* *: use C99 standard fixed-width integer typesQuentin Young2018-03-271-4/+4
| | | | | | | | | | | | | | | | | | | | | | The following types are nonstandard: - u_char - u_short - u_int - u_long - u_int8_t - u_int16_t - u_int32_t Replace them with the C99 standard types: - uint8_t - unsigned short - unsigned int - unsigned long - uint8_t - uint16_t - uint32_t Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* *: reindentreindent-master-afterwhitespace / reindent2017-07-171-31/+30
| | | | | | indent.py `git ls-files | pcregrep '\.[ch]$' | pcregrep -v '^(ldpd|babeld|nhrpd)/'` Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* *: make consistent & update GPLv2 file headersDavid Lamparter2017-05-151-4/+3
| | | | | | | | | | | The FSF's address changed, and we had a mixture of comment styles for the GPL file header. (The style with * at the beginning won out with 580 to 141 in existing files.) Note: I've intentionally left intact other "variations" of the copyright header, e.g. whether it says "Zebra", "Quagga", "FRR", or nothing. Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* build: remove $Format tagsDavid Lamparter2016-12-201-2/+1
| | | | Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* bgpd: Convert BGP_MAXIMUM_MAXPATHS to MULTIPATH_NUMDonald Sharp2015-12-081-3/+0
| | | | | | | There is no point in allowing more BGP_MAXIMUM_MAXPATHS than MULTIPATH_NUM. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* bgpd: Use actual MULTIPATH_NUM as the limitorDonald Sharp2015-12-081-3/+0
| | | | | | | BGP uses a second #define that is equal to MULTIPATH_NUM. There is no point in having a different #define. Just consolidate. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* Quagga default: BGP enable "maximum-paths 64"Daniel Walton2015-11-131-1/+1
| | | | | | | Signed-off-by: Daniel Walton <dwalton@cumulusnetworks.com> Reviewed-by: Donald Sharp <sharpd@cumulusnetworks.com> Ticket: CM-8099
* bgp may add multiple path entries with the same nexthopDaniel Walton2015-11-121-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Signed-off-by: Daniel Walton <dwalton@cumulusnetworks.com> Reviewed-by: Donald Sharp <sharpd@cumulusnetworks.com> Ticket: CM-8129 - We have 14 paths for each prefix, 7 are from ipv4 peers and 7 are from ipv6 peers - There are 7 unique nexthops - When comparing the exact same path from an v4 peer vs. a v6 peer the path from the v4 peer wins. This is due to the "lowest neighbor IP" check in the decision algorithm. For example below we learn NEXTHOP 210.2.4.2 from 210.2.4.2 and 2001:20:4::2 but only the one from the v4 peer is flagged as multipath. - The problem is when our bestpath is from a v6 peer, 2001:20:2::2 in this case (see line 85). 2001:20:2::2 sent us 210.2.2.2 so we will install that nexthop because it is from our bestpath, the problem is we flag the path from 210.2.2.2 (line 37) as multipath which causes us to install two paths with nexthop 210.2.2.2 1 superm-redxp-05# show ip bgp 2.23.24.192/28 2 BGP routing table entry for 2.23.24.192/28 3 Paths: (14 available, best #14, table Default-IP-Routing-Table) 4 Advertised to non peer-group peers: 5 210.2.0.2 210.2.1.2 210.2.2.2 210.2.3.2 210.2.4.2 210.2.5.2 210.2.6.2 210.4.1.4 2001:20::2 2001:20:1::2 2001:20:2::2 2001:20:3::2 2001:20:4::2 2001:2 6 205 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 7 210.2.4.2 from 210.2.4.2 (10.0.0.2) 8 Origin IGP, localpref 100, valid, external, multipath 9 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 10 Last update: Wed Nov 11 20:54:57 2015 11 12 204 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 13 210.2.3.2 from 210.2.3.2 (10.0.0.2) 14 Origin IGP, localpref 100, valid, external, multipath 15 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 16 Last update: Wed Nov 11 20:54:57 2015 17 18 202 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 19 210.2.1.2 from 210.2.1.2 (10.0.0.2) 20 Origin IGP, localpref 100, valid, external, multipath 21 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 22 Last update: Wed Nov 11 20:54:57 2015 23 24 206 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 25 210.2.5.2 from 2001:20:5::2 (10.0.0.2) 26 Origin IGP, localpref 100, valid, external 27 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 28 Last update: Wed Nov 11 20:54:57 2015 29 30 205 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 31 210.2.4.2 from 2001:20:4::2 (10.0.0.2) 32 Origin IGP, localpref 100, valid, external 33 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 34 Last update: Wed Nov 11 20:54:57 2015 35 36 203 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 37 210.2.2.2 from 210.2.2.2 (10.0.0.2) 38 Origin IGP, localpref 100, valid, external, multipath 39 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 40 Last update: Wed Nov 11 20:54:57 2015 41 42 202 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 43 210.2.1.2 from 2001:20:1::2 (10.0.0.2) 44 Origin IGP, localpref 100, valid, external 45 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 46 Last update: Wed Nov 11 20:54:57 2015 47 48 201 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 49 210.2.0.2 from 210.2.0.2 (10.0.0.2) 50 Origin IGP, localpref 100, valid, external, multipath 51 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 52 Last update: Wed Nov 11 20:54:57 2015 53 54 206 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 55 210.2.5.2 from 210.2.5.2 (10.0.0.2) 56 Origin IGP, localpref 100, valid, external, multipath 57 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 58 Last update: Wed Nov 11 20:54:57 2015 59 60 207 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 61 210.2.6.2 from 2001:20:6::2 (10.0.0.2) 62 Origin IGP, localpref 100, valid, external 63 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 64 Last update: Wed Nov 11 20:54:57 2015 65 66 207 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 67 210.2.6.2 from 210.2.6.2 (10.0.0.2) 68 Origin IGP, localpref 100, valid, external, multipath 69 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 70 Last update: Wed Nov 11 20:54:57 2015 71 72 201 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 73 210.2.0.2 from 2001:20::2 (10.0.0.2) 74 Origin IGP, localpref 100, valid, external 75 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 76 Last update: Wed Nov 11 20:54:57 2015 77 78 204 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 79 210.2.3.2 from 2001:20:3::2 (10.0.0.2) 80 Origin IGP, localpref 100, valid, external 81 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 82 Last update: Wed Nov 11 20:54:57 2015 83 84 203 200 300 790 90 80 2334 544 56 67 889 3111 777 8 879 900 88 7654 3211 113 43434 666 343 4534 667 7688 85 210.2.2.2 from 2001:20:2::2 (10.0.0.2) 86 Origin IGP, localpref 100, valid, external, multipath, best 87 Community: 0:100 0:200 0:300 0:324 0:2938 0:3344 0:3545 0:4466 0:5445 0:5754 88 Last update: Wed Nov 11 20:54:57 2015 89 90 superm-redxp-05# Here you can see the two paths with nexthop 210.2.2.2 superm-redxp-05# show ip route 2.23.24.192/28 Routing entry for 2.23.24.192/28 Known via "bgp", distance 20, metric 0, best Last update 00:32:12 ago * 210.2.2.2, via swp3 * 210.2.0.2, via swp1 * 210.2.1.2, via swp2 * 210.2.2.2, via swp3 * 210.2.3.2, via swp4 * 210.2.4.2, via swp5 * 210.2.5.2, via swp6 * 210.2.6.2, via swp7 superm-redxp-05# superm-redxp-05# The fix is to not flag a path as multipath if it has the same nexthop as the bestpath
* bgpd: bgpd-table-map.patchDonald Sharp2015-05-201-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | COMMAND: table-map <route-map-name> DESCRIPTION: This feature is used to apply a route-map on route updates from BGP to Zebra. All the applicable match operations are allowed, such as match on prefix, next-hop, communities, etc. Set operations for this attach-point are limited to metric and next-hop only. Any operation of this feature does not affect BGPs internal RIB. Supported for ipv4 and ipv6 address families. It works on multi-paths as well, however, metric setting is based on the best-path only. IMPLEMENTATION NOTES: The route-map application at this point is not supposed to modify any of BGP route's attributes (anything in bgp_info for that matter). To achieve that, creating a copy of the bgp_attr was inevitable. Implementation tries to keep the memory footprint low, code comments do point out the rationale behind a few choices made. bgp_zebra_announce() was already a big routine, adding this feature would extend it further. Patch has created a few smaller routines/macros whereever possible to keep the size of the routine in check without compromising on the readability of the code/flow inside this routine. For updating a partially filtered route (with its nexthops), BGP to Zebra replacement semantic of the next-hops serves the purpose well. However, with this patch there could be some redundant withdraws each time BGP announces a route thats (all the nexthops) gets denied by the route-map application. Handling of this case could be optimized by keeping state with the prefix and the nexthops in BGP. The patch doesn't optimizing that case, as even with the redundant withdraws the total number of updates to zebra are still be capped by the total number of routes in the table. Signed-off-by: Vipin Kumar <vipin@cumulusnetworks.com> Reviewed-by: Pradosh Mohapatra <pmohapat@cumulusnetworks.com>
* cluster-id length equality for multipathDonald Sharp2015-05-201-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | A fat tree topology running IBGP gets into two issues with anycast address routing. Consider the following topology: R9 R10 x x R3 R4 R7 R8 x x R1 R2 R5 R6 | | | | 10/8 10/8 10/8 S Let's remind ourselves of BGP decision process steps: 1. Highest Local Preference 2. Shortest AS Path Length 3. Lowest Origin Type 4. Lowest MED (Multi-Exit Discriminator) 5. Prefer External to Internal 6. Closest Egress (Lowest IGP Distance) 7. Tie Breaking (Lowest-Router-ID) 8. Tie Breaking (Lowest-cluster-list length) 9. Tie Breaking (Lowest-neighbor-address) Without any policies, steps 1-6 will almost always evaluate identically for all paths received on any router in the above topology. Let's assume that the router-ids follow the following inequality: R1 < R2 < R5 < R6. Owing to the 7th step above, all routers will now choose R1's path as the best. This is undesirable. As an example, traffic from S to 10/8 will follow the path S -> R6 -> R7 -> R9 -> R4 -> R2 -> 10/8 instead of S -> R6 -> R7 -> R5 -> 10/8. Furthermore, once R7 (& R8) chooses R1's path as the best, it would withdraw its path learned through (R5, R6) from (R9, R10). This leads to inefficient load balancing - e.g. R9 can't do ECMP across all available egresses - (R1, R2, R5). The patch addresses these issues by noting that that cluster list is always carried along with the routes and its length is a good indicator of IBGP hops. It thus makes sense to compare that as an extension to metric after step 6. That automatically ensures correct multipath computation. Unfortunately a partial deployment of this in a generic topology (note: fat-tree/clos topologies work fine) may lead to potential loops. It needs to be looked into. Signed-off-by: Pradosh Mohapatra <pmohapat@cumulusnetworks.com> Reviewed-by: Dinesh G Dutt <ddutt@cumulusnetworks.com>
* bgpd: When advertising a multipath route, the attribute set to beJosh Bailey2011-07-211-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | advertised is based on the bestpath attribute set, but the following attributes are aggregated from the attribute sets of the multipath constituents: - AS_PATH - ORIGIN - COMMUNITIES - EXTENDED COMMUNITIES In addition the route is advertised with the NEXT_HOP set to the router's interface IP address, instead of the NEXT_HOP of the best path. This is to ensure that traffic will go to this router so it can be fanned out via the multipath route. * bgpd/ecommunity.c * ecommunity_uniq_sort(): Make this function externally accessible * bgpd/ecommunity.h * Add external declaration for ecommunity_uniq_sort() * bgpd/bgp_mpath.c * bgp_info_nexthop_cmp(): Replace calls to bgp_attr_extra_get() to avoid unwanted memory allocation * bgp_info_mpath_free(): Free aggregate attribute for multipath * bgp_info_mpath_attr(): Lookup aggregate attribute of a multipath route * bgp_info_mpath_attr_set(): Set aggregate attribute of a multipath route * bgp_info_mpath_aggregate_update(): Update the aggregate attribute of a multipath route * bgpd/bgp_mpath.h * bgp_info_mpath: Add pointer to hold aggregate attribute of a multipath * Add external declarations for new functions * bgpd/bgp_route.c * bgp_announce_check(): Use aggregate attribute when announcing multipath route * bgp_announce_check_rsclient(): Use aggregate attribute when announcing multipath route * bgp_best_selection(): After updating multipath set, update the multipath aggregate attribute
* bgpd: For deterministic MED build a multipath set for each peer AS as theJosh Bailey2011-07-211-0/+1
| | | | | | | | | | | | | | | | | | | | | | | first stage of the best path calculation. The second stage then selects a winner from each peer AS's best path. In the second stage we clear multipath set of the non-selected best paths via bgp_mp_dmed_deselect(). Since the multipath set is already marked up for the winning path, we don't call bgp_info_mpath_update() after the second stage calculation. * bgpd/bgp_mpath.c * bgp_mp_dmed_deselect(): New function to cleanup the multipath markup if a DMED selected path loses in stage 2 of the best path calculation * bgpd/bgp_mpath.h * Add external declaration of bgp_mp_dmed_deselect() * bgpd/bgp_route.c * bgp_best_selection(): If multipath is enabled, build up the mp_list for the current peer AS, and do the RIB markup the best path from that AS. In the second stage, clear the RIB markup for the DMED selected path if it is not selected as best. Only call bgp_info_mpath_update() in the second stage when not doing deterministic MED.
* bgpd: Adds support to mark up the BGP rib table entry with multipathJosh Bailey2011-07-211-0/+32
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | information based on the multipath list (mp_list) generated during the best path calculation. Display "multipath" for paths that are multipath and also on bestpath if the route is multipath. Flag a best path with the BGP_INFO_MULTIPATH_CHG if the multipath set has changed since the last update. This can be used to trigger updates to zebra and peers. The multipath markup is a lazily allocated bgp_info_mpath structure that is added to the best path and any multipaths. The mpath structures are linked together with the best path element at the head and the other elements ordered by nexthop and then by peer address. This markup scheme is updated by calling bgp_info_mpath_update() and passing in a new mp_list the the current multipath set. There are additional API's for walking the multipath set, querying the count of multipaths, and for cleaning up the multipath markup information when freeing path information. * bgpd/bgp_mpath.c * bgp_info_mpath_new(): Allocation of new mpath element * bgp_info_mpath_free(): Release memory for mpath element * bgp_info_mpath_get(): Access mpath element of path. Allocate memory on-demand * bgp_info_mpath_enqueue(): Enqueue a path onto the multipath list * bgp_info_mpath_dequeue(): Remove a path from the multipath list * bgp_info_mpath_first(): Return first path on the multipath list * bgp_info_mpath_next(): Return next path on the multipath list * bgp_info_mpath_count(): Return the number of paths on the multipath list * bgp_info_mpath_count_set(): Set the number of paths on the multipath list * bgp_info_mpath_update(): Update multipath markup on bgp route table entry and flag any changes. Emit 'debug bgp event' output on any multipath change. * bgpd/bgp_mpath.h * struct bgp_info_mpath: Information added to a bgp_info path to record multipath information * External declarations for new functions in bgp_mpath.c * bgpd/bgp_route.c * bgp_info_free(): Free mpath memory when freeing path information * bgp_info_reap(): Dequeue path from multipath queue before deleting it * bgp_best_selection(): Calls bgp_info_mpath_update() with latest mp_list to mark-up rib table entry * bgp_vty_out_detail(): Add display of multipath flag for a path. Also display 'multipath' for bestpath if it is a multipath route * bgpd/bgp_route.h * struct bgp_info: Add pointer to bgp_info_mpath information * Add flags to mark a path as multipath (BGP_INFO_MULTIPATH) and to mark bestpath if multipath information has changed (BGP_INFO_MULTIPATH_CHG) * lib/memtypes.c * Add MTYPE_BGP_MPATH_INFO for allocating memory for bgp_info_mpath * tests/bgp_mpath_test.c * Add test case for bgp_info_mpath_update() and supporting functions
* bgpd: Adds equal-paths check to path comparison. Paths that areJosh Bailey2011-07-211-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | equal to the best path are accumulated onto an ordered list (mp_list) if maximum-paths is configured. A future commit will add the multipath markup to the BGP rib table based on the mp_list. Add unit test for the added mp_list functions. Deterministic MED is not supported in this commit, it will be added later. * bgpd/bgp_aspath.c * Make aspath_cmp() an external symbol so it can be used in equivalent paths check * bgpd/bgp_aspath.h * Add extern declaration of aspath_cmp() * bgpd/bgp_mpath.c * bgp_info_nexthop_cmp(): Compares nexthops of two paths * bgp_info_mpath_cmp(): Compare function to order multipaths by nexthop and then by peer address * bgp_mp_list_init(): Initialize a list with the multipath order function * bgp_mp_list_clear(): Clear out the mp_list * bgp_mp_list_add(): Add a multipath to mp_list * bgpd/bgp_mpath.h * External declarations for above added functions in bgp_mpath.c * bgpd/bgp_route.c * bgp_info_cmp(): Add equivalent paths result (paths_eq). If eBGP paths are equal down to IGP metric check, flag as equal if peer AS matches. Similarly for iBGP paths but compare full AS_PATH. * bgp_best_selection(): If multipath is enabled, accumulate equivalent paths in mp_list. Add debug bgp event output to see result (will be filtered later to display only when change occurs) * bgp_process_rsclient(): Pass multipath config to bgp_best_selection() * bgp_process_main(): Pass multipath config to bgp_best_selection() * tests/bgp_mpath_test.c * Add unit test case for bgp_mp_list functions
* bgpd: Add new configuration cli for eBGP and iBGP multipath.Josh Bailey2011-07-211-0/+34
There is support to configure this for each (AFI,SAFI), but currently this configuration is only present for IPv4 unicast: maximum-paths [ibgp] <1-255> no maximum-paths [ibgp] [<1-255>] * bgpd/Makefile.am * Add bgp_mpath.h and bgp_mpath.c to build * bgpd/bgp_mpath.h * New file for bgp multipath declarations * define BGP_DEFAULT_MAXPATHS * bgpd/bgp_mpath.c * bgp_maximum_paths_set(): Configure maximum paths for the given afi, safi and bgp instance * bgp_maximum_paths_unset(): Return maximum paths configuration to the default setting for the given afi, safi and bgp instance * bgpd/bgp_vty.c * Define command strings for above CLI * bgp_config_write_maxpaths(): Outputs configuration for the given afi, safi and bgp instance * Install command elements for IPv4 unicast * bgpd/bgp_zebra.h * bgp_config_write_maxpaths(): External declaration * bgpd/bgpd.c * bgp_create(): Initialize bgp instance to default maximum paths setting * bgp_config_write_family(): Output maximum paths configuration for the given address family * bgp_config_write(): Output maximum paths configuration for IPv4 unicast address family * bgpd/bgpd.h * struct bgp: Add storage for maximum paths configuration for each afi, safi
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-02 16:29:39 +0100