Subject: [RAM] TIDR using the IDENTIFIERS attribute

From: [email-masked]
Date: Thu, 19 Apr 2007 14:06:28 +0200

Hi all,

I am sending you the mail I promised on Monday. 

I think we have mainly two problems to solve: 
(1) scalability of the global BGP table,
(2) BGP churn.

(1) SCALABILITY OF THE ROUTING TABLE 
We have several thousands of autonomous systems in the
Internet, and we treat all of them in the same way whether
they are transit or non-transit AS-es. But we shouldn´t
forget that only 1/6 are transit AS-es. And most likely
this fraction is decreasing over time (any figures?).

In the draft on "Tunneled Inter-domain Routing (TIDR)"
I presented a push method based on the use of tunnels
which are announced using the LOCATOR attribute. It is
the presence of the LOCATOR attribute what permits to
say whether a prefix is a "locator prefix" or an
"identifier prefix". This separation will allows us to
treat these two types of prefixes differently.

But this separation can be achieved either using the
LOCATOR attribute to assign locators to identifiers,
or by using the IDENTIFIERS attribute to specify which
identifiers can be reached through the locator specified
in the NLRI of the BGP update. 

In TIDR, scalability of the routing table is achieved
because whereas "locator prefixes" are still stored in
the RIB, "identifier prefixes" are moved to the TIB.
As a consequence of this, the RIB eventually will
only store the "locator prefixes" of the transit AS-es.

(2) BGP CHURN
As Heiner Hummel pointed out "with Hierarchical Routing
the routing churn rate will dramatically be reduced". 

I think he is right, because with hierarchical routing not
all parts of the network are equally important. So that,
an announcement or withdrawal of an "identifier prefix"
will be far less important than that of a "locator prefix".

The addition of a new attribute to BGP (LOCATOR, IDENTIFIERS,
or both) obviously increases the amount of information that
must be flooded by BGP. But in my opinion, the main problem
is not this increase in the amount of information but the
fact that a change in a leaf AS using PI addressing implies
to modify the RIB and FIB of all the routers in the DFZ.

In other words, the problem is not to force every router in
the entire DFZ to carry an advertisement for site X's
PI-prefix. The most important problem is that it has to use
this announcement for routing, i.e. it has to install it in
the RIB and download it into the FIB. With TIDR things
improve because this announcement will not modify the RIB
but only the TIB.

Therefore, if we want to reduce the effect of the route churn
on the BGP convergence we will have to modify BGP so that a
change in the identifier-locator map will not affect the
interdomain routing system (more specifically the RIB of
DFZ routers) but only the TIB. So, we need two types of
BGP updates: "routing updates" and "mapping updates".

Let's use for example the block 240.0.0.0/8 to assign
"locator prefixes" to transit AS-es so that, for instance,
AS1 will use the block 240.0.1.0/24 for "locator prefixes".

Please notice that this is just an example to explain
the inner workings of my proposal. I think it is very
important to use a specific range of IP addresses for
TIDR routing so that a transit AS is assigned an address
block easy to identify.

The ORIGIN attribute is a mandatory attribute that must
be always present in any BGP update. At present this
attribute can have one of the following values:
  - IGP: the NLRI is interior to the originating AS
  - EGP: NLRI learned via the EGP protocol
  - Incomplete: NLRI learned by some other means

The ORIGIN=EGP value is no longer used. Therefore I
propose to reinterpret this value as EXTERNAL (to keep
the first letter the same), or to define a fourth value
for the ORIGIN attribute, whatever is simpler. If the
latter is simpler we could define ORIGIN=MAPPING to
indicate that the BGP update is just for ID-LOC mapping.

Bearing this in mind we proceed to distinguish the two
aforementioned types of BGP updates:
  - "routing updates": these are the current type of
    updates. They carry ORIGIN IGP or INCOMPLETE.
    They are used to modify the RIB.
  - "mapping updates": they carry ORIGIN EXTERNAL or
    MAPPING, and are used to modify the TIB. They
    carry the IDENTIFIERS attribute to specify the
    set of "identifier prefixes" that can be reached
    through the locator specified in the NLRI of the
    update. They will be treated with a priority
    lower than "routing updates".

With these two types of BGP updates we separate routing
events (those affecting the interdomain infrastructure)
from those updates caused by changes in the ID-LOC mapping.

Following the above example, AS1 will generate "routing
updates" to announce prefix 240.0.1.0/24 or even longer
prefixes that will remain inside the interdomain routing
infrastructure. What means that transit AS-es will never
propagate these announcements to their leaf customers,
for they are outside the interdomain infrastructure.

And AS1 will also generate "mapping updates" to specify 
within the IDENTIFIERS attribute which "identifier prefixes"
can be accessed by sending tunneled traffic to the locator
which is specified in the NLRI.

Notes:
a) I have continued to use LOCATOR as the name of the first
   new attribute that I proposed in the TIDR draft, but
   notice that this attribute can be used to store several
   locators. Therefore the name can be changed to LOCATORS.
b) When I say PI-prefix I also mean a deaggregated PA-prefix.

Any comments?.

Regards,
Juanjo

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: Simon Leinen <[email-masked]>
Date: Thu, 19 Apr 2007 17:08:33 +0200

> this fraction is decreasing over time (any figures?).

You could look at

http://bgp.potaroo.net/index-bgp.html

and, for one or three suitable ASes, check out the history files of
terminal, transit-only, and mixed ASes, e.g.:

http://bgp.potaroo.net/1239/bgp-as-term.txt
http://bgp.potaroo.net/1239/bgp-transit.txt
http://bgp.potaroo.net/1239/bgp-mixedas.txt

I wrote a quick Perl script (attached) and ran it on the AS1239 files.
The results suggest that the ratio of transit (-only and mixed) ASes
to total has remained pretty stable over the past years (modulo a
dot-com-bubble/burst bump :-).  According to this definition, the
ratio is more like 29%, not the 1/6 you claim.

: leinen@diotima[ram]; perl hack.pl | awk '{ print $6, $5 }' | uniq -1
30.85% 1998
31.87% 1999
27.96% 2000
28.73% 2001
28.15% 2002
27.07% 2003
27.84% 2004
28.68% 2005
28.50% 2006
29.14% 2007

(uniq -1 drops all but the first measurement for a given year, so
these are the respective ~January 1 numbers.)

Maybe your definition of a transit AS differs from Geoff's?
-- 
Simon.
#!/usr/local/bin/perl -w

use strict;

my @classes = qw(as-term transit mixedas);

my %by_date = ();

foreach my $class (@classes) {
    my $file = "bgp-$class.txt";
    open FILE, $file or die "Cannot open $file: $!";
    while (<FILE>) {
	next if /^-1 \d+$/;
	die "Malformed line: $_" unless /^(\d+) (\d+)$/;
	$by_date{$1}->{$class} = $2;
    }
    close FILE or die "Cannot close $file: $!";
}
foreach my $date (sort { $a <=> $b } keys %by_date) {
    my $by_class = $by_date{$date};
    my $term = $by_class->{'as-term'};
    my $transit_only = $by_class->{'transit'};
    my $mixed = $by_class->{'mixedas'};
    next if !defined $term or !defined $transit_only or !defined $mixed;
    print scalar localtime $date;
    my $transit = $transit_only + $mixed;
    printf " %5.2f%%", ($transit*100.0) / ($transit + $term);
    print "\n";
}
1;
_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: "Ricardo V. Oliveira" <[email-masked]>
Date: Thu, 19 Apr 2007 12:17:44 -0700

Yes, our measurements also confirm Simon numbers. Roughly speaking,  
about 1/3 of ASes are transit, but they originate 2/3 of the prefixes.

--Ricardo

---

From: [email-masked]
Date: Fri, 20 Apr 2007 11:50:54 +0200

Ricardo, Simon:

Thank you for your comments. Please see below.

> > ratio is more like 29%, not the 1/6 you claim.

The last RIS Statistics Report provided by RIPE
(http://www.ris.ripe.net/weekly-report/reports/20070409-20070416.html)
shows the following: 

Distribution of AS number wrt Leaf, Transit. 

                 RIS     rrc00   rrc01   rrc02   rrc03   rrc04   rrc05 
Leaf           21120     21197   21132    5012   21153   19944   21252 
Transit         4122      3971    3900     522    3916    3518    3801 
Transit-only     142       136     133     963     133     193     132 
Total          25384     25304   25165    6497   25202   23655   25185 

If we take the first column we have:

25384 / (4122 + 142) = 5.95

Therefore, roughly speaking, transit AS-es are 1/6 of the total.

> > Maybe your definition of a transit AS differs from Geoff's?

I think this definition is the same for all of us, isn't it?.
Am I missing something?.

At first sight one should think that 1/3 are too many transit AS-es
but reality always has the last word.

Regards,
Juanjo