Active BGP Probing
Last update: Sun 26 Jan 2019
Papers
- L. Colitti, G. Di Battista, M. Patrignani, M. Pizzonia and M. Rimondini, Investigating prefix propagation through active BGP probing, in Proceedings of IEEE ISCC 2006. [pdf] [ps.gz]
Relevant Documents
For in-depth information, please read the following documents.
- Technical report:
pdf
ps
ps.gz
- RIPE50 Presentation:
pdf
(Note: see errata on router behaviour below)
Latest results
2005-06-24: Diffusion of large AS-sets in the Internet.
Description of our techniques
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:
- Equipment tests
- Juniper routers seem to have no problems with long AS-paths; the M7i we tested had no problems receiving and propagating AS-sets containing up to 255 ASes, the maximum length permitted by the BGP packet format.
- Cisco routers reset the BGP session when the AS-path more than 512 bytes long, which corresponds to about 254 ASes. Cisco is aware of this issue and is in the process of fixing it, but in all the topologies we tested, our algorithms never needed to announce AS-sets more than 50 elements long, which is well within the limit. In any case, our techniques limit the length of the AS-sets announced to a suitable number to account for propagation.
- 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.
- Observation
- Longer AS-sets (123 and 124 elements) and longer AS-paths have been observed in the wild with no ill effects that we know of.
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.
Errata
Router behaviour in the presence of long AS-paths
Note: the RIPE 50 presentation says that Juniper and old Cisco routers
reset the BGP session when they received an AS-path with more than 125 ASes.
Further testing has shown that this is incorrect:
- As far as we can see, Junipers do not seem to have problems with long AS-paths at all.
- Cisco routers reset the session when they receive an AS-path more
than 512 bytes long. Cisco is aware of this issue and is in the process of
fixing it.