From 96450faf3385a6ed9f4dd5c2c58776c4a664a8da Mon Sep 17 00:00:00 2001 From: Josh Bailey Date: Wed, 20 Jul 2011 20:45:12 -0700 Subject: bgpd: Adds equal-paths check to path comparison. Paths that are 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/bgp_route.c | 113 ++++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 92 insertions(+), 21 deletions(-) (limited to 'bgpd/bgp_route.c') diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c index 5c516f02..718e25ff 100644 --- a/bgpd/bgp_route.c +++ b/bgpd/bgp_route.c @@ -54,6 +54,7 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA #include "bgpd/bgp_advertise.h" #include "bgpd/bgp_zebra.h" #include "bgpd/bgp_vty.h" +#include "bgpd/bgp_mpath.h" /* Extern from bgp_dump.c */ extern const char *bgp_origin_str[]; @@ -316,7 +317,8 @@ bgp_med_value (struct attr *attr, struct bgp *bgp) /* Compare two bgp route entity. br is preferable then return 1. */ static int -bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist) +bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist, + int *paths_eq) { u_int32_t new_pref; u_int32_t exist_pref; @@ -331,6 +333,9 @@ bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist) int internal_as_route = 0; int confed_as_route = 0; int ret; + uint32_t newm, existm; + + *paths_eq = 0; /* 0. Null check. */ if (new == NULL) @@ -454,18 +459,32 @@ bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist) return 0; /* 8. IGP metric check. */ - if (new->extra || exist->extra) - { - uint32_t newm = (new->extra ? new->extra->igpmetric : 0); - uint32_t existm = (exist->extra ? exist->extra->igpmetric : 0); - - if (newm < existm) - return 1; - if (newm > existm) - return 0; - } + newm = (new->extra ? new->extra->igpmetric : 0); + existm = (exist->extra ? exist->extra->igpmetric : 0); + if (newm < existm) + ret = 1; + if (newm > existm) + ret = 0; /* 9. Maximum path check. */ + if (newm == existm) + { + if ((peer_sort (new->peer) == BGP_PEER_IBGP)) + { + if (aspath_cmp (new->attr->aspath, exist->attr->aspath)) + *paths_eq = 1; + } + else if (new->peer->as == exist->peer->as) + *paths_eq = 1; + } + else + { + /* + * TODO: If unequal cost ibgp multipath is enabled we can + * mark the paths as equal here instead of returning + */ + return ret; + } /* 10. If both paths are external, prefer the path that was received first (the oldest one). This step minimizes route-flap, since a @@ -1267,7 +1286,9 @@ struct bgp_info_pair }; static void -bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, struct bgp_info_pair *result) +bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, + struct bgp_maxpaths_cfg *mpath_cfg, + struct bgp_info_pair *result) { struct bgp_info *new_select; struct bgp_info *old_select; @@ -1275,7 +1296,13 @@ bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, struct bgp_info_pair * struct bgp_info *ri1; struct bgp_info *ri2; struct bgp_info *nextri = NULL; - + int paths_eq, do_mpath; + struct list mp_list; + + bgp_mp_list_init (&mp_list); + do_mpath = (mpath_cfg->maxpaths_ebgp != BGP_DEFAULT_MAXPATHS || + mpath_cfg->maxpaths_ibgp != BGP_DEFAULT_MAXPATHS); + /* bgp deterministic-med */ new_select = NULL; if (bgp_flag_check (bgp, BGP_FLAG_DETERMINISTIC_MED)) @@ -1299,7 +1326,7 @@ bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, struct bgp_info_pair * || aspath_cmp_left_confed (ri1->attr->aspath, ri2->attr->aspath)) { - if (bgp_info_cmp (bgp, ri2, new_select)) + if (bgp_info_cmp (bgp, ri2, new_select, &paths_eq)) { bgp_info_unset_flag (rn, new_select, BGP_INFO_DMED_SELECTED); new_select = ri2; @@ -1341,14 +1368,58 @@ bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, struct bgp_info_pair * bgp_info_unset_flag (rn, ri, BGP_INFO_DMED_CHECK); bgp_info_unset_flag (rn, ri, BGP_INFO_DMED_SELECTED); - if (bgp_info_cmp (bgp, ri, new_select)) - new_select = ri; + if (bgp_info_cmp (bgp, ri, new_select, &paths_eq)) + { + new_select = ri; + + if (do_mpath && !paths_eq) + { + bgp_mp_list_clear (&mp_list); + bgp_mp_list_add (&mp_list, ri); + } + } + + if (do_mpath && paths_eq) + bgp_mp_list_add (&mp_list, ri); } - result->old = old_select; - result->new = new_select; - return; + /* + * TODO: Will add some additional filtering later to only + * output debugs when multipath state for the route changes + */ + if (BGP_DEBUG (events, EVENTS) && do_mpath) + { + struct listnode *mp_node; + struct bgp_info *mp_info; + char buf[2][INET_ADDRSTRLEN]; + + prefix2str (&rn->p, buf[0], sizeof (buf[0])); + zlog_debug ("%s bestpath nexthop %s, %d mpath candidates", + buf[0], + (new_select ? + inet_ntop(AF_INET, &new_select->attr->nexthop, + buf[1], sizeof (buf[1])) : + "None"), + listcount (&mp_list)); + for (mp_node = listhead (&mp_list); mp_node; + mp_node = listnextnode (mp_node)) + { + mp_info = listgetdata (mp_node); + if (mp_info == new_select) + continue; + zlog_debug (" candidate mpath nexthop %s", + inet_ntop(AF_INET, &mp_info->attr->nexthop, buf[0], + sizeof (buf[0]))); + } + } + + bgp_mp_list_clear (&mp_list); + + result->old = old_select; + result->new = new_select; + + return; } static int @@ -1422,7 +1493,7 @@ bgp_process_rsclient (struct work_queue *wq, void *data) struct peer *rsclient = rn->table->owner; /* Best path selection. */ - bgp_best_selection (bgp, rn, &old_and_new); + bgp_best_selection (bgp, rn, &bgp->maxpaths[afi][safi], &old_and_new); new_select = old_and_new.new; old_select = old_and_new.old; @@ -1483,7 +1554,7 @@ bgp_process_main (struct work_queue *wq, void *data) struct peer *peer; /* Best path selection. */ - bgp_best_selection (bgp, rn, &old_and_new); + bgp_best_selection (bgp, rn, &bgp->maxpaths[afi][safi], &old_and_new); old_select = old_and_new.old; new_select = old_and_new.new; -- cgit v1.2.1