[quagga-dev 11363] [PATCH] BGP: add aspath_aggregate_mpath that preserves path length

Boian Bonev bbonev at ipacct.com
Wed Jun 25 18:26:44 BST 2014


Issue - when two aspaths are aggregated the result will be with
different length if the two paths do not share common prefix.

E.g.: aggregation of 100 101 400 500 and 200 201 400 500 currently
will result in {100,101,200,201,400,500} which is of much shorter
length and is not ok to be readvertised becase may create shortest
path on the internet and cause infinite flapping.

aspath_aggregate_mpath will construct the followin path for the
above example: {100,200} {101,201} 400 500

Signed-off-by: Boian Bonev <bbonev at ipacct.com>
---
 bgpd/bgp_aspath.c | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 bgpd/bgp_aspath.h |   1 +
 bgpd/bgp_mpath.c  |   2 +-
 3 files changed, 121 insertions(+), 1 deletion(-)

diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c
index e8559be..dcf6c6a 100644
--- a/bgpd/bgp_aspath.c
+++ b/bgpd/bgp_aspath.c
@@ -1078,6 +1078,125 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2)
   return aspath;
 }
 
+/* Modify as1 using as2 for aggregation for multipath. */
+struct aspath *
+aspath_aggregate_mpath (struct aspath *as1, struct aspath *as2)
+{
+  int i;
+  int minlen;
+  int match;
+  int from1,from2;
+  struct assegment *seg1 = as1->segments;
+  struct assegment *seg2 = as2->segments;
+  struct aspath *aspath = NULL;
+  struct assegment *asset;
+  struct assegment *prevseg = NULL;
+
+  match = 0;
+  minlen = 0;
+  aspath = NULL;
+  asset = NULL;
+
+  /* First of all check common leading sequence. */
+  while (seg1 && seg2)
+    {
+      /* Check segment type. */
+      if (seg1->type != seg2->type)
+	break;
+
+      /* Minimum segment length. */
+      minlen = min (seg1->length, seg2->length);
+
+      for (match = 0; match < minlen; match++)
+	if (seg1->as[match] != seg2->as[match])
+	  break;
+
+      if (match)
+	{
+	  struct assegment *seg = assegment_new (seg1->type, 0);
+
+	  seg = assegment_append_asns (seg, seg1->as, match);
+
+	  if (! aspath)
+	    {
+	      aspath = aspath_new ();
+	      aspath->segments = seg;
+	     }
+	  else
+	    prevseg->next = seg;
+
+	  prevseg = seg;
+	}
+
+      if (match != minlen || match != seg1->length
+	  || seg1->length != seg2->length)
+	break;
+
+      seg1 = seg1->next;
+      seg2 = seg2->next;
+    }
+
+  if (! aspath)
+    aspath = aspath_new();
+
+  /* Make as-set using rest of all information. */
+  from1 = from2 = match;
+  while (seg1 || seg2)
+    {
+      if (seg1)
+	{
+	  if (seg1->type == AS_SEQUENCE)
+	    {
+	      asset = aspath_aggregate_as_set_add (aspath, asset, seg1->as[from1]);
+	      from1++;
+	      if (from1 >= seg1->length)
+		{
+		  from1 = 0;
+		  seg1 = seg1->next;
+		}
+	    }
+	  else
+	    {
+	      for (i = from1; i < seg1->length; i++)
+		asset = aspath_aggregate_as_set_add (aspath, asset, seg1->as[i]);
+
+	      from1 = 0;
+	      seg1 = seg1->next;
+	    }
+	  }
+
+      if (seg2)
+	{
+	  if (seg2->type == AS_SEQUENCE)
+	    {
+	      asset = aspath_aggregate_as_set_add (aspath, asset, seg2->as[from2]);
+	      from2++;
+	      if (from2 >= seg2->length)
+		{
+		  from2 = 0;
+		  seg2 = seg2->next;
+		}
+	    }
+	  else
+	    {
+	      for (i = from2; i < seg2->length; i++)
+		asset = aspath_aggregate_as_set_add (aspath, asset, seg2->as[i]);
+
+	      from2 = 0;
+	      seg2 = seg2->next;
+	    }
+	}
+
+      if (asset->length == 1)
+	asset->type = AS_SEQUENCE;
+      asset = NULL;
+    }
+
+  assegment_normalise (aspath->segments);
+  aspath_str_update (aspath);
+  return aspath;
+}
+
 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
    attribute, check the leftmost AS number in the AS_PATH attribute is
    or not the peer's AS number. */ 
diff --git a/bgpd/bgp_aspath.h b/bgpd/bgp_aspath.h
index e8764cc..27dca31 100644
--- a/bgpd/bgp_aspath.h
+++ b/bgpd/bgp_aspath.h
@@ -69,6 +69,7 @@ extern void aspath_finish (void);
 extern struct aspath *aspath_parse (struct stream *, size_t, int);
 extern struct aspath *aspath_dup (struct aspath *);
 extern struct aspath *aspath_aggregate (struct aspath *, struct aspath *);
+extern struct aspath *aspath_aggregate_mpath (struct aspath *, struct aspath *);
 extern struct aspath *aspath_prepend (struct aspath *, struct aspath *);
 extern struct aspath *aspath_filter_exclude (struct aspath *, struct aspath *);
 extern struct aspath *aspath_add_seq (struct aspath *, as_t);
diff --git a/bgpd/bgp_mpath.c b/bgpd/bgp_mpath.c
index 7999d16..29220fb 100644
--- a/bgpd/bgp_mpath.c
+++ b/bgpd/bgp_mpath.c
@@ -666,7 +666,7 @@ bgp_info_mpath_aggregate_update (struct bgp_info *new_best,
   for (mpinfo = bgp_info_mpath_first (new_best); mpinfo;
        mpinfo = bgp_info_mpath_next (mpinfo))
     {
-      asmerge = aspath_aggregate (aspath, mpinfo->attr->aspath);
+      asmerge = aspath_aggregate_mpath (aspath, mpinfo->attr->aspath);
       aspath_free (aspath);
       aspath = asmerge;
 
-- 
1.9.1





More information about the Quagga-dev mailing list