Subject: [rrg] Odd BGP AS Path

From: Heath Jones <[email-masked]>
Date: Wed, 22 Sep 2010 14:25:00 +0100

Hi all,

Probably a silly question, but can anyone explain to me this: 3561
3356 9031 {35821,35821,35821,35821} i

To explain it a bit better, I'm looking at real routing information
from routeviews (#3).

According to RFC 4271 (9.2.2.2 Aggregating Routing Information):
> For the purpose of aggregating AS_PATH attributes, we model
> each AS within the AS_PATH attribute as a tuple <type, value>,
> where "type" identifies a type of the path segment the AS
> belongs to (e.g., AS_SEQUENCE, AS_SET), and "value" identifies
> the AS number.
> ...
> No tuple of type AS_SET with the same value SHALL appear
> more than once in the aggregated AS_PATH.

Am I misreading things, or is this path information out of spec?

ps. Is this the best list to post to for this type of thing, or can
someone recommend a better one?
Cheers
Heath

---

From: "Stephen D. Strowes" <[email-masked]>
Date: Wed, 22 Sep 2010 14:39:23 +0100

Hi,

> 3356 9031 {35821,35821,35821,35821} i

AS9031 has aggregated multiple prefixes advertised by 35821 into one
prefix. The _odd_ thing is repeating the same aggregated AS in the set.
Could this be bad configuration, or a bug?

> Am I misreading things, or is this path information out of spec?

I read it as saying no identical AS set shall be repeated. There is only
one AS set in the path above. Ergo, complaint, albeit odd.

> someone recommend a better one?

I'm sure many here can answer the question better than I. If you want a
more interesting response, somebody subscribed to NANOG ought to be able
to give a good answer.

Cheers,
-S.

---

From: Christopher Morrow <[email-masked]>
Date: Wed, 22 Sep 2010 09:44:14 -0400

>> 3356 9031 {35821,35821,35821,35821} i

what if the path was (before exit to 3356, say):

3561 3356 9031 {35821, 65532, 65533, 65534} i

and this probably doesn't belong on a research-group list, it sounds
like an ops question.

-chris

---

From: Marshall Eubanks <[email-masked]>
Date: Wed, 22 Sep 2010 09:47:23 -0400

> 3356 9031 {35821,35821,35821,35821} i

Isn't this just AS prepending ?

http://home.ie.cuhk.edu.hk/~dmchiu/tnsm.pdf

(You can easily find info on this for your router of choice with any search engine.)

> someone recommend a better one?

I would try NANOG.

Regards
Marshall

> Cheers
> Heath
> _______________________________________________
> rrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/rrg
>

---

From: "Stephen D. Strowes" <[email-masked]>
Date: Wed, 22 Sep 2010 14:59:22 +0100

> Isn't this just AS prepending ?

If it were simply prepending, then 35821 would indeed appear multiple
times in the AS path, but not as part of a set.

-S.

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Wed, 22 Sep 2010 10:36:14 -0400

Recenly 

http://www.antd.nist.gov/~ksriram/AS_SET_Aggregator_Stats.pdf

K. Sriram
+1 301 975 3793
http://www.antd.nist.gov/~ksriram/

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of Heath Jones
> Sent: Wednesday, September 22, 2010 9:25 AM
> To: RRG
> Subject: [rrg] Odd BGP AS Path
> 
> Hi all,
>

---

From: Heath Jones <[email-masked]>
Date: Wed, 22 Sep 2010 15:45:04 +0100

> 3561 3356 9031 {35821, 65532, 65533, 65534} i
Thats an interesting possibility.. I think though 38521 are doing
prepending on a bunch of advertisments (can see that from other routes
from 38521), and 9031 has included the prepended path and not filtered
correctly. Bug..?

> and this probably doesn't belong on a research-group list, it sounds

Cheers. I'll better direct my queries next time :)

---

From: [email-masked] (Sandy Murphy)
Date: Wed, 22 Sep 2010 10:44:47 -0400 (EDT)

>> someone recommend a better one?

As this is a protocol spec question, you might also consider asking
the idr group in the IETF ([email-masked]), which has responsibility
for the BGP spec and so has many who know the spec and implementations.

--Sandy

P.S.  As the AS_SET is intended to retain enough AS information from
aggregated UPDATEs to maintain loop detection, the presence of multiple
identical ASs in the AS_SET does no harm.  Unless of course it stressees
another implementation's parsing of the AS_PATH in ways that are bad.  :-)

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Wed, 22 Sep 2010 10:47:38 -0400

Please excuse the previous incomplete email.
Accidentally got sent out while composing!

Recently, we did some measurements on AS_SETs
in the context of some SIDR WG questions
pertaining to origin validation in BGP updates.
There are fewer than 0.1% BGP updates or RIB entries that 
have AS_SETs in them.   
What you observed is correct. Within the few such updates,
you would often find the same AS repeated multiple times
inside the AS_SET (although not illustrated in my slides)!
Please see slides 3 and 4 at this link; the general stats related to
AS_SETs may be of interest.  
http://www.antd.nist.gov/~ksriram/AS_SET_Aggregator_Stats.pdf

K. Sriram
+1 301 975 3793

---

From: Heath Jones <[email-masked]>
Date: Wed, 22 Sep 2010 15:54:32 +0100

> for the BGP spec and so has many who know the spec and implementations.

Thanks - I'm very new to this part of town, so still getting a feel
for who/what/where.

> another implementation's parsing of the AS_PATH in ways that are bad.  :-)

I agree - it probably doesn't make much operational difference.
I've only come across is because I'm parsing mrt data from routeviews
and building an AS peering table from path information - which means
dealing with every strange AS path out there..

Cheers

---

From: Heath Jones <[email-masked]>
Date: Wed, 22 Sep 2010 16:08:22 +0100

> http://www.antd.nist.gov/~ksriram/AS_SET_Aggregator_Stats.pdf

Thankyou very much for the link (it's not working at the moment from
here, but i'll give it another try later).

I'm actually looking into aggregation of prefixes within a tcam and
using this data to find out which AS's would be most heavily impacted
if they implemented such aggregation.

There are many papers around about this and a fairly heavy argument
towards any aggregation creating non-determinism with regards to
required tcam size. (how can you know how much space you will need
free, given you cannot predict the removal of some aggregated
prefixes). I have not seen a paper that uses real world data as yet
though..

Any thoughts you might have are appreciated!

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Wed, 22 Sep 2010 11:38:13 -0400

My slides sent to you separately as a pdf file.
For the FIB aggregation work, you may wish to look up work by
Lixia Zhang, Zartash Uzmi, Paul Francis at previous IETF GROW WG meetings.

A couple of recent links (there is much more work reported, of course):
http://tools.ietf.org/agenda/76/slides/grow-5.pdf

http://www.ietf.org/proceedings/78/slides/grow-2/grow-2.htm

Sriram

> From: Heath Jones [mailto:[email-masked]]
> Sent: Wednesday, September 22, 2010 11:08 AM
> To: Sriram, Kotikalapudi
> Cc: RRG
> Subject: Re: [rrg] Odd BGP AS Path
>

---

From: Heath Jones <[email-masked]>
Date: Wed, 22 Sep 2010 16:41:02 +0100

Thanks for your valuable help!

Also on nanog, i've just been directed to this:
http://tools.ietf.org/html/draft-wkumari-deprecate-as-sets-00

---

From: "John G. Scudder" <[email-masked]>
Date: Wed, 22 Sep 2010 11:43:41 -0400

> Isn't this just AS prepending ?

If so, it's broken prepending.  RFC 4271, 9.1.2.2:

      a) Remove from consideration all routes that are not tied for
         having the smallest number of AS numbers present in their
         AS_PATH attributes.  Note that when counting this number, an
         AS_SET counts as 1, no matter how many ASes are in the set.

Generating an AS_SET like the one depicted seems to be pointless, albeit harmless as well.

--John

---

From: "Stephen D. Strowes" <[email-masked]>
Date: Wed, 22 Sep 2010 18:29:03 +0100

> dealing with every strange AS path out there..

Do you have code available for this? This must be an oft-repeated task,
and it would be good to share.

I have some scripts which do similar:
http://svn.sdstrowes.co.uk//bgp%20scripts/

Namely, bgpToUniqPaths.mrt.sh, and pathsToLinks.sh. The former takes an
MRT table dump and strips out unique BGP paths, the latter takes those
BGP paths and generates a list of pairs of ASes connected to each other.

However, the latter script removes AS Sets: they appear in a very small
proportion of paths, and I cannot say anything of the internal
connectivity of that set.

If you want to make the scripts fly, they rely on a couple of pieces of
Scala code located in http://svn.sdstrowes.co.uk//util/

Cheers,
-S.

---

From: Tony Li <[email-masked]>
Date: Wed, 22 Sep 2010 19:09:42 -0700

Hi folks,

This thread is wholly inappropriate to RRG.  Could we please take it somewhere else, please?

Thanks,
Tony

---

From: Heath Jones <[email-masked]>
Date: Thu, 23 Sep 2010 09:30:31 +0100

Hi Tony - sure thing, my apologies.

Cheers