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
diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c
index 5c516f0..718e25f 100644
--- a/bgpd/bgp_route.c
+++ b/bgpd/bgp_route.c
@@ -54,6 +54,7 @@
#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 @@
/* 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 @@
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 @@
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 @@
};
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 @@
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 @@
|| 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_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 @@
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 @@
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;