BGP TTL

[Joe Abley]

On Wednesday, March 20, 2002, at 03:48 , Geoff Huston wrote:

> At 3/21/2002 07:16 AM, Andrew Partan wrote:
>> However even a setting of (say) 10 would limit the count-to-infinity
>> problem - see, e.g.: the current 6bone & their *very* long AS paths.
>> [As the 6bone today is mostly full of mutual-transit peerings, you
>> can get some very long count-to-infinity paths.]
>
> max AS path length in the V4 BGP world  ppears to be somewhere between 
> 11 and 22 (http://www.potaroo.net//bgp2/as6447/bgp-max-aspath-
> length.html)
>
> and if you keep AS path prepending the number is between 25 and 32 
> (http://www.potaroo.net//bgp2/as6447/bgp-max-p-aspath-length.html)
>
> (This view uses the route-views data)

A histogram of number of paths vs. ASN hops might also be interesting. I 
just tried to do a "show ip bgp path" on route-views, but it kicked me 
out before it was complete (probably fair enough; there are LOTS of 
paths on that router) but here's a histogram from AS6461:

   1 ASNs (0.01%) are 0 AS-hops away
   565 ASNs (4.57%) are 1 AS-hops away
   7373 ASNs (59.62%) are 2 AS-hops away
   3369 ASNs (27.24%) are 3 AS-hops away
   798 ASNs (6.45%) are 4 AS-hops away
   229 ASNs (1.85%) are 5 AS-hops away
   29 ASNs (0.23%) are 6 AS-hops away
   2 ASNs (0.02%) are 7 AS-hops away
   1 ASNs (0.01%) are 8 AS-hops away

Similar histograms based on path info from other prominent ISPs (Level3, 
Verio, UU) have a similar-shaped distribution.

This suggests that a TTL-style knob would be a fairly coarse control if 
applied from 6461; by the time a route has propagated into three ASes 
you have already inflicted it upon 91% of the ASes in the network.

I suspect the general spike seen around 2-3 AS hops above is going to be 
common to the view from most networks, so a less-central AS still 
doesn't get much control (it goes "nobody sees it, a few people see it, 
a few more people, a few more, woah, half the internet sees it, most of 
the other half also sees it," and trails off from there).

I like the TTL idea; Ben Black scribbled something similar on the back 
of an envelope after the IDR meeting in Minneapolis last time. But I 
don't think it's going to be useful while the network is so centralised 
on a relatively dense central mesh of ASes.


Joe

(awk script to generate the output above follows; pipe the output of 
"show ip bgp path" on a cisco into it)

#!/usr/bin/awk -f

/^0x/ {
   cl = 0;
   asn = "";
   for (i = 5; i < NF; i++) {
     if (cl == 0) {
       asn = $i;
       cl++;
     } else {
       if (asn != $i) {
         asn = $i;
         cl++;
       }
     }
   }

   if (shortest[asn] > cl || shortest[asn] == "")
     shortest[asn] = cl;
}

END {
   t = 0;
   for (n in shortest) {
     hist[shortest[n]]++;
     t++;
   }
   for (n in hist)
     printf "%d ASNs (%2.2f%%) are %d AS-hops away\n", hist[n], 
100*hist[n]/t, n;
}