Active BGP Probing and large AS-sets

Hi,

our announcement on nanog a few months ago of experiments involving BGP 
updates containing large AS-sets [1] caused a few flames. Now we have an 
in-depth document with results on the subject and would like to explain 
what we intended to do.

We have presented our techniques at RIPE 50, and there is a Web page on 
the project, with links to the full report and the slides, up at:

http://www.dia.uniroma3.it/~compunet/bgp-probing/

What follows is a brief summary of what we do, why we believe it is 
safe, and why it shouldn't cause problems to current operational 
practices. For more details, see the presentation and the report.

We will be happy to answer any further questions you might have.


Regards,
Lorenzo Colitti

---

                          Active BGP Probing
                          ==================

What we do
----------

Existing topology discovery techniques are good at discovering topology 
but bad at discovering policy. However, to predict the effect of network 
faults, perform effective traffic engineering, develop peering 
strategies, and evaluate the quality of upstreams, it would be useful 
for ISPs to to know how their announcements can be propagated and how 
the policies of other ASes in the Internet affect their prefixes. No 
operational tools exist to do this.

The principle is the following: an AS using our probing techniques can 
announce one of its prefixes with AS-paths including the numbers of 
other ASes. Due to loop detection, these "prohibited" ASes will not use 
or propagate the announcement. To avoid influencing AS-path length, the 
prohibited ASes are placed in an AS-set at the end of the path.

Thus, to stop its announcement from being propagated by ASes 1, 2, and 
3, an AS (say AS12654) might announce one of its prefixes with an 
AS-path of 12654 {1,2,3}. This allows AS 12654 to discover who 
propagates its announcements, find backup paths, and deduce the policies 
of other ASes with respect to its prefixes.

To collect data it is possible to the RIS or ORV route collectors. 
However, since our methods operate in steady state, the results are 
visible from any looking glass on the Internet.


Why it is safe
--------------

We are confident that such announcements are safe, provided that the 
length of the AS-set announced is limited. We say this based on:

1. Equipment tests. Juniper routers seem to have no problems with long 
AS-paths, while Cisco routers reset the BGP session when the AS-path 
more than 512 bytes long (about 254 ASes). Cisco is aware of this issue 
and is in the process of fixing it; in any case, our techniques limit 
the length of the AS-sets announced to a suitable number to account for 
propagation (obviously, much smaller than 254).

2. IPv6 tests. We started testing our techniques on the IPv6 backbone in 
November. No problems were reported. The first report (of only two) we 
got of someone even noticing the unusually long paths arrived at the end 
of February.

3. Observation. Longer AS-sets (123 [2] and 124 [3] elements) and longer 
AS-paths have been observed in the wild with no ill effects that we know 
of -- at least, we know of no operators who reported problems.


Why it doesn't impact routers
-----------------------------

Route flap dampening limits our probing to the order of one update per 
hour. This is negligible compared to the over 15,000 updates/hour a 
typical Tier-1 router might receive. As regards impact on memory, the 
amount of RAM to store a 100-element AS-set for one prefix is of the 
order of hundreds of bytes, which is irrelevant for core routers which 
are already using tens of megabytes of memory for BGP.


Why it doesn't hamper debugging
-------------------------------

Prepending other AS numbers is to a certain extent already done today. 
Our techniques are similar, but foreign ASes are only in the AS-set at 
the end of the path, so it's immediately obvious which path the 
announcement has taken. Due to the size of the AS-set, we doubt that 
anyone seeing such an announcement would believe it was due to one of 
the ASes in the set, but would probably look at the first AS before the 
set. Furthermore, the prefix immediately identifies the source of the 
announcements. Finally, the routes can also be tagged with communities 
to help identify them.

[1] http://www.merit.edu/mail.archives/nanog/2005-03/msg00029.html
[2] http://www.ripe.net/projects/ris/Talks/0101_RIPE38_AA/sld003.html
[3] http://www.ripe.net/maillists/ncc-archives/ris-users/2002/msg00044.html


-- 
RIPE NCC        Roma Tre Computer Networks research group
www.ripe.net                www.dia.uniroma3.it/~compunet
lorenzo at ripe.net                  colitti at dia.uniroma3.it