Subject: [Idr] Question about RFC4893

From: Benjamin April <[email-masked]>
Date: Fri, 09 Oct 2009 12:56:18 -0400

Greetings,

I find myself in the process of updating one of our BGP
data-collectors to support 4-octet ASNs. I did my best to follow
RFC-4893, however I have a nagging feeling that I don't understand
one element. I hope you folks can point me in the right direction here.

The language in question is in section 4.2.3. The passages of
particular concern to me are:

Under certain conditions, it may not be possible to reconstruct the
entire AS path information from the AS_PATH and the AS4_PATH
attributes of a route.  This occurs when two or more routes that
carry the AS4_PATH attribute are aggregated by an OLD BGP speaker,
and the AS4_PATH attribute of at least one of these routes carries
at least one 4-octet AS number (as oppose to a 2-octet AS number
that is encoded in 4 octets).  Depending on the implementation,
either the AS4_PATH attribute would be lost during route
aggregation, or both the AS_PATH attribute and the AS4_PATH
attribute would contain valid, partial information that cannot be
combined seamlessly, resulting in incomplete AS path information in
these cases.

and

In order to construct the AS path information, it would be necessary
to first calculate the number of AS numbers in the AS_PATH and
AS4_PATH attributes using the method specified in Section 9.1.2.2
[BGP] and [RFC3065] for route selection. If the number of AS numbers
in the AS_PATH attribute is less than the number of AS numbers in
the AS4_PATH attribute, then the AS4_PATH attribute SHALL be
ignored, and the AS_PATH attribute SHALL be taken as the AS path
information.

If the number of AS numbers in the AS_PATH attribute is larger than
or equal to the number of AS numbers in the AS4_PATH attribute, then
the AS path information SHALL be constructed by taking as many AS
numbers and path segments as necessary from the leading part of the
AS_PATH attribute, and then prepending them to the AS4_PATH
attribute so that the AS path information has an identical number of
AS numbers as the AS_PATH attribute.

Forgive me, but this all sounds like an awful lot of hand-waving to
me. Has anything been done since this RFC was published to better
describe in a more formal way the procedure a BGP speaker should
follow to re-construct an accurate AS_PATH from the AS4_PATH and
AS_PATH attributes? Based on this description I can see more than
one way to implement this. I would like to do so correctly, but I
need to know what is correct first.

Thanks
Ben

TREND MICRO EMAIL NOTICE
The information contained in this email and any attachments is confidential and may be subject to copyright or other intellectual property protection. If you are not the intended recipient, you are not authorized to use or disclose this information, and we request that you notify us by reply mail or telephone and delete the original message from your mail system.

---

From: Enke Chen <[email-masked]>
Date: Fri, 09 Oct 2009 10:12:21 -0700

Ben,

1) RFC 4893 has been revised by the following document:

     http://www.ietf.org/id/draft-ietf-idr-rfc4893bis-01.txt

2) Sect. 4.2.3 presents a complete, and precise algorithm for 
constructing the as-path:

----------------------------------

   A NEW BGP speaker should also be prepared to receive the
   AS4_AGGREGATOR attribute along with the AGGREGATOR attribute from an
   OLD BGP speaker.  When both the attributes are received, if the AS
   number in the AGGREGATOR attribute is not AS_TRANS, then:

      -  the AS4_AGGREGATOR attribute and the AS4_PATH attribute SHALL
         be ignored,

      -  the AGGREGATOR attribute SHALL be taken as the information
         about the aggregating node, and

      -  the AS_PATH attribute SHALL be taken as the AS path
         information.

   Otherwise,

      -  the AGGREGATOR attribute SHALL be ignored,

      -  the AS4_AGGREGATOR attribute SHALL be taken as the information
         about the aggregating node, and

      -  the AS path information would need to be constructed, as in all
         other cases.

   In order to construct the AS path information, it would be necessary
   to first calculate the number of AS numbers in the AS_PATH and
   AS4_PATH attributes using the method specified in Section 9.1.2.2
   [RFC4271] and [RFC5065] for route selection.

   If the number of AS numbers in the AS_PATH attribute is less than the
   number of AS numbers in the AS4_PATH attribute, then the AS4_PATH
   attribute SHALL be ignored, and the AS_PATH attribute SHALL be taken
   as the AS path information.

   If the number of AS numbers in the AS_PATH attribute is larger than
   or equal to the number of AS numbers in the AS4_PATH attribute, then
   the AS path information SHALL be constructed by taking as many AS
   numbers and path segments as necessary from the leading part of the
   AS_PATH attribute, and then prepending them to the AS4_PATH attribute
   so that the AS path information has an identical number of AS numbers
   as the AS_PATH attribute.  Note that a valid AS_CONFED_SEQUENCE or
   AS_CONFED_SET path segment SHALL be prepended if it is either the
   leading path segment or adjacent to a path segment that is prepended.
-----------------------

Please let us know which part of the algorithm that you think is not clear.

Regards,   -- Enke

Benjamin April wrote:
> _______________________________________________
> Idr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/idr
>

---

From: Enke Chen <[email-masked]>
Date: Fri, 09 Oct 2009 10:22:43 -0700

Ben,

A correction here:   RFC 4893 is being revised (instead of "has been 
revised") by rfc4893bis.

Thanks to an IDR member who pointed out the difference.

-- Enke

Enke Chen wrote:
>> The information contained in this email and any attachments is 
>> confidential and may be subject to copyright or other intellectual 
>> property protection. If you are not the intended recipient, you are 
>> not authorized to use or disclose this information, and we request 
>> that you notify us by reply mail or telephone and delete the original 
>> message from your mail system.

---

From: "Samita Chakrabarti" <[email-masked]>
Date: Fri, 9 Oct 2009 11:07:42 -0700

Hi Ben,

Please see below:

> If the number of AS numbers in the AS_PATH attribute is larger than or
equal
> to the number of AS numbers in the AS4_PATH attribute, then the AS path
> information SHALL be constructed by taking as many AS numbers and path
> segments as necessary from the leading part of the AS_PATH attribute, and
> then prepending them to the AS4_PATH attribute so that the AS path
> information has an identical number of AS numbers as the AS_PATH
attribute.
> 
> 
> 
> Forgive me, but this all sounds like an awful lot of hand-waving to me.
Has
> anything been done since this RFC was published to better describe in a
more
> formal way the procedure a BGP speaker should follow to re-construct an
> accurate AS_PATH from the AS4_PATH and AS_PATH attributes? Based on this
> description I can see more than one way to implement this. I would like to
> do so correctly, but I need to know what is correct first.
> 
> Thanks
> Ben
> 
[SC>] 

I agree with you completely this handwaving portion in rfc 4893 is very
problematic to the implementers who were not directly involved in the making
of RFC 4893. I was not one of them.  In 2008, I wrote a draft pointing out
some of the problems we faced during implementation and to request an update
of the RFC for future interoperability. Also presented the draft at WG in
Spring 2008 IETF. Rfc4893-bis has considered some of the problems mentioned
in the draft + others discussed in the working group alias.
http://wattle.apnic.net/ietf/idref/draft-chakrabarti-idr-rfc4893-mod/

The following interpretation has been made in our implementation after
talking with some other implementers.
I believe rfc4893-bis now has the similar text:
1.	If the number of ASNs in AS_PATH is less than the number of ASNs in
AS4_PATH, then NBGP ignores AS4_PATH  information.
Example:
AS_PATH:   2 23456
AS4_PATH: 70000 70001 70002

2.	If the number of ASNs in AS_PATH attribute is greater than number of

         ASNs in AS4_PATH attribute, then there must be a few AS_TRANS 
        numbers in AS_PATH.  Reconstruct AS_PATH based on the AS4_PATH 
       items corresponding to  AS_TRANS numbers 
      Examples:
      AS_PATH: 2,3,6, 8, 23456, 10, 23, 23456
      AS4_PATH: 65356, 77777
3.	If the number of ASNs in AS_PATH and AS4_PATH attributes is same
then it most likely means that all the AS numbers are AS4-byte unmappable
numbers.  Check the count of AS_TRANS numbers in AS_PATH and count of AS
numbers in AS4_PATH.  If they are the same then reconstruct AS information
from AS4_PATH only (note this case is for AS num == AS4 num). If number of
AS_TRANS in AS_PATH is less than the number in AS4_PATH values, then there
is something wrong done by previous speakers. However, take the non-AS_TRANS
AS values from AS_PATH  and then prepend them with the AS4 values. Some
examples will clarify this case:
AS_PATH:   23456, 23456,  23456
AS4_PATH: 777777, 66666, 88888
Or
AS_PATH: 2, 3, 4, 23456
AS4_PATH: 88888, 99999, 70000, 80000

Thanks,
-Samita

---

From: Enke Chen <[email-masked]>
Date: Fri, 09 Oct 2009 11:58:15 -0700

Samita:

We can argue about the presentation style and other portions in 
RFC4893.  However,  IMO the specific
merge algorithm is complete, and precise,  as I pointed out to Ben.

Please see my comments inlined.

> AS4_PATH: 70000 70001 70002

RFC 4893 has the following text in Sect. 4.2.3:

--------------------------------------------

I am wondering why this portion needed "interpretation" in your 
implementation.

>       AS_PATH: 2,3,6, 8, 23456, 10, 23, 23456

So what exactly is the problem with following RFC 4893 in this case?   
The (AS_PATH, AS4_PATH) is
not really consistent here -- that is, 65356 is not represented in 
AS_PATH, and there is an extra 23456 in
the middle.  Most likely this is a crafted, lab scenario in which there 
is no single "correct" answer.

> AS4_PATH: 777777, 66666, 88888

So the merged as-path would consist of the valid AS numbers 777777, 
66666, 88888 based on RFC 4893.
This seems fine.  Isn't it?

> AS4_PATH: 88888, 99999, 70000, 80000

This again is another inconsistent, artificially crafted scenario.  
Possibly there are more than one "correct"
solutions, some more "correct" than others - depending on how the 
inconsistency was generated. As
the as-path length must be maintained during the merge, no solution can 
possibly include all the valid AS
numbers contained in AS_PATH / AS4_PATH.

RFC 4893 would yield 88888, 99999, 70000, 80000 as the merged one.  Why 
wouldn't it be good enough?

Thanks.    -- Enke

---

From: "Samita Chakrabarti" <[email-masked]>
Date: Fri, 9 Oct 2009 12:04:45 -0700

Hi Enke,

I am OK with the current text in rfc4893-bis that you already pointed out.

I provided some additional examples for clarification and for the purpose of
discussion.

Cheers,
-Samita
> -----Original Message-----
> From: Enke Chen [mailto:[email-masked]]
> Sent: Friday, October 09, 2009 11:58 AM
> To: Samita Chakrabarti
> Cc: [email-masked]; [email-masked]; Enke Chen
> Subject: Re: [Idr] Question about RFC4893
> 
> Samita:
> 
> We can argue about the presentation style and other portions in RFC4893.
> However,  IMO the specific merge algorithm is complete, and precise,  as I
> pointed out to Ben.
> 
> >> or
> >> to the number of AS numbers in the AS4_PATH attribute, then the AS
> >> path information SHALL be constructed by taking as many AS numbers
> >> and path segments as necessary from the leading part of the AS_PATH
> >> attribute, and then prepending them to the AS4_PATH attribute so that
> >> the AS path information has an identical number of AS numbers as the
> >> AS_PATH
> >>
> > attribute.
> >
> >>
> >> formal way the procedure a BGP speaker should follow to re-construct
> >> an accurate AS_PATH from the AS4_PATH and AS_PATH attributes? Based
> >> on this description I can see more than one way to implement this. I
> >> would like to do so correctly, but I need to know what is correct
first.
> >>
> >> Thanks
> >> Ben
> >>
> >>
> > [SC>]
> >
> > I agree with you completely this handwaving portion in rfc 4893 is
> > very problematic to the implementers who were not directly involved in
> > the making of RFC 4893. I was not one of them.  In 2008, I wrote a
> > draft pointing out some of the problems we faced during implementation
> > and to request an update of the RFC for future interoperability. Also
> > presented the draft at WG in Spring 2008 IETF. Rfc4893-bis has
> > considered some of the problems mentioned in the draft + others
discussed
> in the working group alias.

---

From: Enke Chen <[email-masked]>
Date: Fri, 09 Oct 2009 12:10:32 -0700

BTW,  based on the on-line IETF track tool, there has been no change in 
the merge algorithm (Sect 4.2.3) from RFC 4893 to rfc4893bis-00.txt and 
to rfc4893bis-01.txt:

http://tools.ietf.org/rfcdiff?difftype=--hwdiff&url2=draft-ietf-idr-rfc4893bis-00.txt
          
http://tools.ietf.org/rfcdiff?difftype=--hwdiff&url2=draft-ietf-idr-rfc4893bis-01.txt

Regards,   -- Enke

Enke Chen wrote:
>>          ASNs in AS4_PATH attribute, then there must be a few 
>> AS_TRANS         numbers in AS_PATH.  Reconstruct AS_PATH based on 
>> the AS4_PATH        items corresponding to  AS_TRANS numbers       
>> Examples:
> the middle.  Most likely this is a crafted, lab scenario in which 
> there is no single "correct" answer.
>
> the as-path length must be maintained during the merge, no solution 
> can possibly include all the valid AS
> RFC 4893 would yield 88888, 99999, 70000, 80000 as the merged one.  
> Why wouldn't it be good enough?
>
> Thanks.    -- Enke
>
>

---

From: "Samita Chakrabarti" <[email-masked]>
Date: Fri, 9 Oct 2009 12:29:04 -0700

Hi Enke,

You are right in pointing out that there is no change from RFC4893 merging
text into the bis versions . I replied too fast. It's been a long time since
we implemented this, but I remember it was not clear at that time and we had
to do some interpretation of the text in RFC.

Below, you have discussed the merged AS-PATH examples with the sample
scenarios I provided.
Do you think you can include some of those examples in the text for
clarification? That might be helpful for the future implementations for
clarity. Just a suggestion...

Thanks,
-Samita

> Sent: Friday, October 09, 2009 12:11 PM
> To: Samita Chakrabarti
the
> merge algorithm (Sect 4.2.3) from RFC 4893 to rfc4893bis-00.txt and to
> rfc4893bis-01.txt:
> 
> 
> > RFC4893.  However,  IMO the specific merge algorithm is complete, and
> > precise,  as I pointed out to Ben.
> >
> >>> attribute, and then prepending them to the AS4_PATH attribute so
> >>> that the AS path information has an identical number of AS numbers
> >>> as the AS_PATH
> >>>
> >> attribute.
> >>
> >>>
me.
> >> very problematic to the implementers who were not directly involved
> >> in the making of RFC 4893. I was not one of them.  In 2008, I wrote a
> >> draft pointing out some of the problems we faced during
> >> implementation and to request an update of the RFC for future
> >> interoperability. Also presented the draft at WG in Spring 2008 IETF.
> >> Rfc4893-bis has considered some of the problems mentioned in the
> >> draft + others discussed in the working group alias.
> >> The following interpretation has been made in our implementation
> >> after talking with some other implementers.
> > AS_PATH, and there is an extra 23456 in the middle.  Most likely this
> > is a crafted, lab scenario in which there is no single "correct"
> > answer.
> >
> >> then it most likely means that all the AS numbers are AS4-byte
> >> unmappable numbers.  Check the count of AS_TRANS numbers in AS_PATH
> >> and count of AS numbers in AS4_PATH.  If they are the same then
> >> reconstruct AS information from AS4_PATH only (note this case is for
> >> AS num == AS4 num). If number of AS_TRANS in AS_PATH is less than the
> >> number in AS4_PATH values, then there is something wrong done by
> >> previous speakers. However, take the non-AS_TRANS AS values from
> >> AS_PATH  and then prepend them with the AS4 values. Some examples
> >> will clarify this case:
> > inconsistency was generated. As the as-path length must be maintained
> > during the merge, no solution can possibly include all the valid AS

---

From: Enke Chen <[email-masked]>
Date: Fri, 09 Oct 2009 18:24:31 -0700

Hi, Samita:

> clarity. Just a suggestion...

If we agree that the merge algorithm described in the document is 
applicable for
these examples (mostly with crafted, inconsistent data), then I am not 
sure if there
is still value in including them in rfc4893bis.

Regards,   -- Enke

---

From: John Leslie <[email-masked]>
Date: Sat, 10 Oct 2009 07:52:52 -0400

Enke Chen <[email-masked]> wrote:
> applicable for these examples (mostly with crafted, inconsistent
> data), then I am not sure if there is still value in including them
> in rfc4893bis.

   I see great value in including such examples in a Security
Considerations section pointing out that such things could be observed
due to "buggy" coding or less-than-trustworthy policy application, and
that some implementors have attempted to mitigate the damage caused by
such cases.

--
John Leslie <[email-masked]>

---

From: Benjamin April <[email-masked]>
Date: Mon, 12 Oct 2009 12:00:20 -0400

Enke,
	Thanks for the quick reply.

>     http://www.ietf.org/id/draft-ietf-idr-rfc4893bis-01.txt

As a member of the general public and not being connected to idr how
am I supposed to know about this document? The first 3 pages of
google results for "RFC4893" or "RFC 4893" say nothing about bis-01,
also searching at IETF this link is likewise absent.

> constructing the as-path:

Am I mistaken or does this fail to address the case where a non-NEW
speaker aggregates routes advertised to it by a new speaker? In such
a case you would not have an AS4_AGGREGATOR but you would have an
AS4_PATH attribute. By using the AS4_AGGREGATOR as the decision
trigger the AS4_AGGREGATOR and thus AS4_PATH gets ignored.

>   as the AS path information.

Is there an expected causes for this case? Just dropping all of that
 nice AS4_PATH goodness on the floor seems to me a rather careless
action. One would hope that such a structured protocol would
complain about such oddities unless they originated from a known
mostly-harmless source.

>   leading path segment or adjacent to a path segment that is prepended.

Sorry for the delayed reply. Busy weekend.

Thanks
Ben

TREND MICRO EMAIL NOTICE

---

From: Enke Chen <[email-masked]>
Date: Mon, 12 Oct 2009 18:48:28 -0700

Ben,

> also searching at IETF this link is likewise absent.

I would think that the introductory books on BGP should have pointers to 
IETF / ROUTING / IDR.

> trigger the AS4_AGGREGATOR and thus AS4_PATH gets ignored.

In that case the AS4_PATH attribute would appear as an unrecognized, 
optional, transitive attribute to the aggregator (an OLD speaker).   
Certainly I am not aware of any implementation that would preserve such 
an attribute during aggregation.  (Even if it were preserved, the 
AS_PATH and AS4_PATH would most likely inconsistent, and why bother with 
doing anything different?)

BTW, irrespective of 4byte AS, it is pretty common for the as-path info 
to be truncated during aggregation.

> complain about such oddities unless they originated from a known

It is not a realistic scenario.   That paragraph in the spec is mainly 
for the sake of completeness.

Sure, one could craft it in the lab.   When AS_PATH and AS4_PATH are 
inconsistent, it is subject to debate whether we should favor the latest 
info (AS_PATH), or the oldest info (AS4_PATH).  We have to specify one.

Some of the discussions occurred several years ago on IDR.  You might be 
able to dig them up in the IDR archives.

Regards,   -- Enke