summaryrefslogtreecommitdiff
path: root/bgpd/bgp_mpath.c
diff options
context:
space:
mode:
authorJosh Bailey <joshb@google.com>2011-07-20 20:45:12 -0700
committerJosh Bailey <joshb@google.com>2011-07-20 20:45:12 -0700
commit96450faf3385a6ed9f4dd5c2c58776c4a664a8da (patch)
tree26c56a71548686a7d6797b79377ccc5e25730186 /bgpd/bgp_mpath.c
parent42ea68512fc4d04b500def45e8f899321f4081e7 (diff)
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
Diffstat (limited to 'bgpd/bgp_mpath.c')
-rw-r--r--bgpd/bgp_mpath.c119
1 files changed, 119 insertions, 0 deletions
diff --git a/bgpd/bgp_mpath.c b/bgpd/bgp_mpath.c
index 56c703f6..09b46951 100644
--- a/bgpd/bgp_mpath.c
+++ b/bgpd/bgp_mpath.c
@@ -24,8 +24,14 @@
#include <zebra.h>
#include "command.h"
+#include "prefix.h"
+#include "linklist.h"
+#include "sockunion.h"
#include "bgpd/bgpd.h"
+#include "bgpd/bgp_table.h"
+#include "bgpd/bgp_route.h"
+#include "bgpd/bgp_attr.h"
#include "bgpd/bgp_mpath.h"
/*
@@ -81,3 +87,116 @@ bgp_maximum_paths_unset (struct bgp *bgp, afi_t afi, safi_t safi,
return 0;
}
+
+/*
+ * bgp_info_nexthop_cmp
+ *
+ * Compare the nexthops of two paths. Return value is less than, equal to,
+ * or greater than zero if bi1 is respectively less than, equal to,
+ * or greater than bi2.
+ */
+static int
+bgp_info_nexthop_cmp (struct bgp_info *bi1, struct bgp_info *bi2)
+{
+ struct attr_extra *ae1, *ae2;
+ int compare;
+
+ ae1 = bgp_attr_extra_get (bi1->attr);
+ ae2 = bgp_attr_extra_get (bi2->attr);
+
+ compare = IPV4_ADDR_CMP (&bi1->attr->nexthop, &bi2->attr->nexthop);
+
+ if (!compare && ae1 && ae2 && (ae1->mp_nexthop_len == ae2->mp_nexthop_len))
+ {
+ switch (ae1->mp_nexthop_len)
+ {
+ case 4:
+ case 12:
+ compare = IPV4_ADDR_CMP (&ae1->mp_nexthop_global_in,
+ &ae2->mp_nexthop_global_in);
+ break;
+#ifdef HAVE_IPV6
+ case 16:
+ compare = IPV6_ADDR_CMP (&ae1->mp_nexthop_global,
+ &ae2->mp_nexthop_global);
+ break;
+ case 32:
+ compare = IPV6_ADDR_CMP (&ae1->mp_nexthop_global,
+ &ae2->mp_nexthop_global);
+ if (!compare)
+ compare = IPV6_ADDR_CMP (&ae1->mp_nexthop_local,
+ &ae2->mp_nexthop_local);
+ break;
+#endif /* HAVE_IPV6 */
+ }
+ }
+
+ return compare;
+}
+
+/*
+ * bgp_info_mpath_cmp
+ *
+ * This function determines our multipath list ordering. By ordering
+ * the list we can deterministically select which paths are included
+ * in the multipath set. The ordering also helps in detecting changes
+ * in the multipath selection so we can detect whether to send an
+ * update to zebra.
+ *
+ * The order of paths is determined first by received nexthop, and then
+ * by peer address if the nexthops are the same.
+ */
+static int
+bgp_info_mpath_cmp (void *val1, void *val2)
+{
+ struct bgp_info *bi1, *bi2;
+ int compare;
+
+ bi1 = val1;
+ bi2 = val2;
+
+ compare = bgp_info_nexthop_cmp (bi1, bi2);
+
+ if (!compare)
+ compare = sockunion_cmp (bi1->peer->su_remote, bi2->peer->su_remote);
+
+ return compare;
+}
+
+/*
+ * bgp_mp_list_init
+ *
+ * Initialize the mp_list, which holds the list of multipaths
+ * selected by bgp_best_selection
+ */
+void
+bgp_mp_list_init (struct list *mp_list)
+{
+ assert (mp_list);
+ memset (mp_list, 0, sizeof (struct list));
+ mp_list->cmp = bgp_info_mpath_cmp;
+}
+
+/*
+ * bgp_mp_list_clear
+ *
+ * Clears all entries out of the mp_list
+ */
+void
+bgp_mp_list_clear (struct list *mp_list)
+{
+ assert (mp_list);
+ list_delete_all_node (mp_list);
+}
+
+/*
+ * bgp_mp_list_add
+ *
+ * Adds a multipath entry to the mp_list
+ */
+void
+bgp_mp_list_add (struct list *mp_list, struct bgp_info *mpinfo)
+{
+ assert (mp_list && mpinfo);
+ listnode_add_sort (mp_list, mpinfo);
+}