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

Boian Bonev bbonev at ipacct.com
Wed Aug 20 00:43:07 BST 2014


Hi Daniel,

This change is only relevant when "bgp bestpath as-path multipath-relax" is
active; else it behaves exactly like the old code.

The idea have been proposed long ago by Paul Jakma (
http://patchwork.quagga.net/patch/417/).

The RFC describes path aggregation in terms of few constraints and this way
does not violate them.
The current way of creating aggregate path may produce shorter path (in
case of multipath-relax) which violates the length constraint from the RFC.
See the example in the commit message.

I have discussed this change about 10 months ago with Pradosh Mohapatra, I
think he would also share his (positive by then) opinion here.

With best regards,
b.



On Tue, Aug 19, 2014 at 9:26 PM, Daniel Walton <dwalton at cumulusnetworks.com>
wrote:

> Is this per the RFC?  I looked through section 9.2.2.2 but don't see where
> it calls for this.
>
> Daniel
>
> ----- Original Message -----
> From: "David Lamparter" <equinox at opensourcerouting.org>
> To: "Boian Bonev" <bbonev at ipacct.com>
> Cc: quagga-dev at lists.quagga.net
> Sent: Tuesday, August 19, 2014 1:59:37 PM
> Subject: [quagga-dev 11445] Re: [PATCH] BGP: add aspath_aggregate_mpath
> that preserves path length
>
> On Wed, Jun 25, 2014 at 08:26:44PM +0300, Boian Bonev wrote:
> > 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
>
> The aspath_* functions are one of the few cases where we actually have
> unit tests (!) - therefore, there really should be tests for this new
> function...
>
> -David
>
> >
> > 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
> >
> >
> > _______________________________________________
> > Quagga-dev mailing list
> > Quagga-dev at lists.quagga.net
> > https://lists.quagga.net/mailman/listinfo/quagga-dev
>
> _______________________________________________
> Quagga-dev mailing list
> Quagga-dev at lists.quagga.net
> https://lists.quagga.net/mailman/listinfo/quagga-dev
>
> _______________________________________________
> Quagga-dev mailing list
> Quagga-dev at lists.quagga.net
> https://lists.quagga.net/mailman/listinfo/quagga-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.quagga.net/pipermail/quagga-dev/attachments/20140820/98314056/attachment-0001.html>


More information about the Quagga-dev mailing list