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

David Lamparter equinox at opensourcerouting.org
Tue Aug 19 19:54:46 BST 2014


On Tue, Aug 19, 2014 at 11:26:34AM -0700, Daniel Walton wrote:
> Is this per the RFC?  I looked through section 9.2.2.2 but don't see where it calls for this.

The behaviour is specifically designed for multipath/ecmp BGP, the best
available reference I could find is:
http://tools.ietf.org/html/draft-bhatia-ecmp-routes-in-bgp-02#section-15


-David

> ----- 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




More information about the Quagga-dev mailing list