bgpd: add aspath_aggregate_mpath that preserves path length
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>
patchwork #994: http://patchwork.quagga.net/patch/994/
diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c
index 6ab2937..49b65b6 100644
--- a/bgpd/bgp_aspath.c
+++ b/bgpd/bgp_aspath.c
@@ -1099,6 +1099,128 @@
return aspath;
}
+/* Modify as1 using as2 for aggregation for multipath, keeping the
+ * AS-Path length the same, and so minimising change to the preference
+ * of the mpath aggregrate route.
+ */
+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 1311f8a..2f0a519 100644
--- a/bgpd/bgp_aspath.h
+++ b/bgpd/bgp_aspath.h
@@ -69,6 +69,7 @@
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_n (struct aspath *, as_t, unsigned);
diff --git a/bgpd/bgp_mpath.c b/bgpd/bgp_mpath.c
index 8e78aaf..48694c6 100644
--- a/bgpd/bgp_mpath.c
+++ b/bgpd/bgp_mpath.c
@@ -695,7 +695,7 @@
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;