Subject: Re: [arch-d] It's the routing, people!

From: "Schliesser, Benson" <[email-masked]>
Date: Sat, 11 Nov 2006 14:19:15 -0600

>> I don't see routing melting today.
> I'm only here because other people seem to think
> it's coming, and want to get
> moving on a solution.

I don't want to derail the broader architectural discussion, which I think is valuable. But let me point out something directly related to the engineering problem we face in the routing system: Of the approx 23k ASs in the global routing system, only 3k are transit ASs. The other 20k systems are basically end networks that multihome. (Yes, there are exceptions, and these numbers are generated from a particular perspective in the network that might not represent all perspectives accurately, but they capture a rough picture that's good enough for this discussion, I think.) Of the de-aggregated and PI space that exists as routes in the global tables, a significant part of it, and the most difficult part to address through education and policy, is in support of these 20k end networks. They need de-aggregates and/or PI in order to maintain redundant connectivity, because there isn't a better technical solution. (Unless they use NAT and don't mind connection resets on failIovers, etc.). If we can come up with a good solution to multihoming that removes the need for these end networks to participate in global routing etc, and change policy so that it reflects this in turn, it seems to me that we can materially reduce table size and rate of growth. (Geoff, it was said you spend all of your time studying this; would you agree?)

Yes, the way I envision this it would be far from a new architecture. But if it solves the immediate problem then those of us running networks can keep the network working, and this mailing list can continue to function as a forum for architectural discussion.  ;)

Cheers,
-Benson
(Sent from my Blackberry... Sorry for thumb-typos)

-----Original Message-----
From: Noel Chiappa
To: [email-masked]
CC: [email-masked]
Sent: Sat Nov 11 12:15:49 2006
Subject: Re: [arch-d] It's the routing, people!

    > From: Geoff Huston <[email-masked]>

    > I don't see routing melting today.

I'm only here because other people seem to think it's coming, and want to get
moving on a solution. If there is no problem, then this whole discussion is
moot, no?

    > I don't necessarily accept that FIB meltdown is only prevented by
    > changing the routing paradigm, as I still don't accept that FIB = RIB.
    > I see that if per packet performance is critical, and that appears to
    > be the case, then the lookup performed per packet should be fast. But I
    > don't accept that this necessarily implies that you have to perform
    > this lookup over the equivalent of the RIB stuffed into a fast lookup
    > data structure to derive an answer that is of the same order as the
    > number of physical egress choices on the box.

I'm not the person to be discussing that point with. You need to talk to the
people who made the case at the IAB workshop. Apparently they convinced the
people at the workshop, but maybe you see something they don't. I read
through the slides from the workshop, and the conclusions seemed reasonable,
but again, perhaps you see something that changes things.

Do you have some approach in mind that works differently? If so, could you
at least sketch it out for us briefly - a full-blown writeup isn't necessary.

    > I suspect that a better understanding of the semantics of addresses,
    > and the distinction .. about what are the characteristics of the
    > packet's source and destination tag, and the relationship of these two
    > tags to the forwarding path across the network are useful in
    > understanding the relationship to the problem being presented here and
    > the degrees of freedom in the symbol space that we can manipulate to
    > provide mitigation

I'm not sure I fully see what you are getting at here, but this kind of
discussion, about not just the semantics of addresses, but about how those
semantics relate to the computation of paths across the connectivity graph,
would be OK, but I didn't hear that happening.

Again, something with a bit more information as to some new scheme which you
might have in mind would make it possible to examine these issues you raise
above, because at this level of abstraction it's hard to draw any definite
conclusions.

	Noel

_______________________________________________
Architecture-discuss mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/architecture-discuss
_______________________________________________
Architecture-discuss mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/architecture-discuss

---

From: Fred Baker <[email-masked]>
Date: Sat, 11 Nov 2006 14:05:31 -0800

On Nov 11, 2006, at 12:19 PM, Schliesser, Benson wrote:

> I don't want to derail the broader architectural discussion, which  
> I think is valuable. But let me point out something directly  
> related to the engineering problem we face in the routing system:  
> Of the approx 23k ASs in the global routing system, only 3k are  
> transit ASs. The other 20k systems are basically end networks that  
> multihome.

actually, I asked Geoff about this, and he told me that ~15K AS's had  
only one upstream AS, meaning that only ~8K have more than one  
(multihome at the BGP level) and (per you) only ~3K of those have  
"many" peer and upstream AS's.

> If we can come up with a good solution to multihoming that removes  
> the need for these end networks to participate in global routing  
> etc, and change policy so that it reflects this in turn, it seems  
> to me that we can materially reduce table size and rate of growth.  
> (Geoff, it was said you spend all of your time studying this; would  
> you agree?)
>
> Yes, the way I envision this it would be far from a new  
> architecture. But if it solves the immediate problem then those of  
> us running networks can keep the network working, and this mailing  
> list can continue to function as a forum for architectural  
> discussion.  ;)

I would generally agree, and the interesting thing is that one  
doesn't really need a pitch-it-all-and-redo architecture change to  
accomplish that. It means that you either want a model in which every  
upstream assigns a part of its own prefix to each of its downstreams  
and every host on every interface has an address from each of the  
relevant ISPs (which is a characteristic of both shim6 and GSE,  
although they are implemented very differently), or that somehow a  
prefix is assigned to an agreeable set of edge networks that can use  
that prefix across multiple ISPs (which is a characteristic of Metro).

http://tools.ietf.org/html/draft-baker-v6ops-l3-multihoming-analysis  
tries to do something of an analysis of those from a technical  
perspective based on RFC 3582. Bottom line, if one does an analysis  
of the approach and can enumerate the number of prefixes in the  
backbone and comes up with a number on the order of 10^4 or 10^5, we  
have accomplished something important. The one thing we know for sure  
is that PI addressing doesn't do that.

This is why I keep asking for that analysis. I think it's important  
enough to not be hand-waved.

What I have concluded from various discussions is that the entire  
requirements set isn't on the table, though. I hear a lot about  
traffic engineering, for example, but don't see an RFC-3582-like set  
of assertions on that topic.

---

From: "Tony Li" <[email-masked]>
Date: Sat, 11 Nov 2006 14:15:44 -0800

> only one upstream AS, 

Only one that Geoff could see from his vantage point?  Or only one
period?

If the latter, that would be an indication that RIR's and others are
being conned into giving out ASNs and prefixes for PI purposes for
singly homed customers.  ;-(

Tony

---

From: Fred Baker <[email-masked]>
Date: Sat, 11 Nov 2006 14:25:35 -0800

> Only one that Geoff could see from his vantage point?  Or only one

Geoff would have to answer that...

---

From: Geoff Huston <[email-masked]>
Date: Sun, 12 Nov 2006 09:27:13 +1100

>singly homed customers.  ;-(

Its a property of BGP that you can't see a 'private" peer BGP 
connection unless you look from the vantage point of  both of the 
peering AS's or see the table from the perspectives of a customer 
of  both entities. These "no upstream transit" peering arrangements 
are simply occluded from the view of everyone else.

Now Fred described this as something subtly different - he said 
"upstream AS". i.e. transit AS, and this is indeed something you can 
look at and measure a subset of and look over the longer term and 
make a reasonable estimate on what is missing. I'll stand by the 
measured numbers quoted above as being very close to whats out there 
for transit upstream.

But transit upstream is not the same as AS-to-AS peering, and the 
numbers relating to AS-to-AS eBGP peering on any basis, including but 
not limited to transit upstream are probably higher. but unless you 
release a pervasive router bot that sends you back local RIB 
snapshots, it becomes a bit of a challenge to gather the raw data 
that would substantiate any number in any more reliable way than any 
other number!.

    Geoff

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sat, 11 Nov 2006 23:37:07 +0100

> transit ASs. The other 20k systems are basically end networks that  

[...]

> to me that we can materially reduce table size and rate of growth.

How can that be true? There are some 200k prefixes in the global  
table. If there are indeed 20k multihomers, that means only 10% of  
the global routing table can be attributed to multihoming, as  
multihoming functionality only requires a single prefix per  
multihomed AS. (Please note that my statement doesn't preclude people  
from announcing more prefixes for other reasons once they're  
multihomed.)

So _today_ the majority of the routing table size/growth is not the  
result of multihoming. However, this doesn't mean that it couldn't be  
in the future, as other factors that contribute to large routing  
tables will become less important over time and/or in IPv6.

---

From: Fred Baker <[email-masked]>
Date: Sat, 11 Nov 2006 15:05:27 -0800

On Nov 11, 2006, at 2:37 PM, Iljitsch van Beijnum wrote:

> multihomed AS. (Please note that my statement doesn't preclude  
> people from announcing more prefixes for other reasons once they're  
> multihomed.)
>
> result of multihoming.

The "BGP Update Report" I received a few days ago told me that  
roughly half of the prefixes advertised in the backbone are longer  
than their allocation length. That tells me one of two things, both  
of which are probably true to some extent. Some percentage of these  
prefixes derive from multihoming, some percentage from traffic  
engineering, and some percentage from errors and incompetence. If I  
were betting money, I would put it on multihoming and traffic  
engineering, not stupidity.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 12 Nov 2006 00:39:45 +0100

On 12-nov-2006, at 0:05, Fred Baker wrote:

> prefixes derive from multihoming,

How does multihoming follow from prefixes longer than the allocation  
size being advertised?

> some percentage from traffic engineering, and some percentage from  
> errors and incompetence. If I were betting money, I would put it on  
> multihoming and traffic engineering, not stupidity.

Well, I guess it's not stupidity if the offenders know better but  
just can't be bothered... But in what twisted universe does the  
following make sense? This AS is singlehandedly responsible for more  
than 1% of the global routing table, and from where I'm sitting,  
there is no evidence of them doing any kind of traffic engineering.

    Network          Next Hop            Metric LocPrf Weight Path
*>i64.134.0.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.0.0/17    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.0.0/16    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.1.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.2.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.3.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.4.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.5.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.6.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.7.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.8.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.9.0/24    212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.11.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.12.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.13.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.14.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.15.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.16.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.20.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.22.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.23.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.24.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.26.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.27.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.28.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.29.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.30.0/23   212.72.45.57             0    100      0 3356  
14654 i
    Network          Next Hop            Metric LocPrf Weight Path
*>i64.134.32.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.35.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.36.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.38.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.39.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.40.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.41.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.42.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.44.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.47.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.48.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.49.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.50.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.52.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.53.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.54.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.55.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.58.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.59.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.60.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.61.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.62.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.64.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.65.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.66.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.68.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.69.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.70.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.71.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.72.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.73.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.74.0/24   212.72.45.57             0    100      0 3356  
14654 i
    Network          Next Hop            Metric LocPrf Weight Path
*>i64.134.75.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.76.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.78.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.79.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.80.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.81.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.82.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.83.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.84.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.85.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.87.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.90.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.91.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.92.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.93.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.94.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.95.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.96.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.97.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.98.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.99.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.101.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.102.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.103.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.104.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.105.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.106.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.108.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.109.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.110.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.115.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.116.0/24  212.72.45.57             0    100      0 3356  
14654 i
    Network          Next Hop            Metric LocPrf Weight Path
*>i64.134.117.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.118.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.119.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.120.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.121.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.122.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.123.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.124.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.125.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.126.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.127.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.129.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.130.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.131.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.132.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.133.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.134.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.135.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.136.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.137.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.140.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.141.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.142.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.143.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.144.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.145.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.149.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.150.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.151.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.152.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.154.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.155.0/24  212.72.45.57             0    100      0 3356  
14654 i
    Network          Next Hop            Metric LocPrf Weight Path
*>i64.134.156.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.158.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.159.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.160.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.161.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.162.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.163.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.166.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.170.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.172.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.174.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.175.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.176.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.177.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.178.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.179.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.180.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.181.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.182.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.183.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.184.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.186.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.187.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.189.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.190.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.192.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.196.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.199.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.200.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.201.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.202.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.203.0/24  212.72.45.57             0    100      0 3356  
14654 i
    Network          Next Hop            Metric LocPrf Weight Path
*>i64.134.204.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.206.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.207.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.209.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.210.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.211.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.212.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.214.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.215.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.216.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.217.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.218.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.220.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.221.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.223.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.224.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.225.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.227.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.228.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.229.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.230.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.231.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.232.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.233.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.234.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.237.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.238.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.240.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.241.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.243.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.244.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.245.0/24  212.72.45.57             0    100      0 3356  
14654 i
    Network          Next Hop            Metric LocPrf Weight Path
*>i64.134.248.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.251.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i64.134.252.0/24  212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.192.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.192.0/19   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.192.0/18   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.193.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.194.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.195.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.196.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.197.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.198.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.199.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.200.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.201.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.202.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.203.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.204.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.205.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.206.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.207.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.208.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.210.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.214.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.215.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.218.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.221.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.222.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.224.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.224.0/19   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.225.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.226.0/24   212.72.45.57             0    100      0 3356  
14654 i
    Network          Next Hop            Metric LocPrf Weight Path
*>i65.74.227.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.228.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.237.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.239.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.240.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.241.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.242.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.243.0/24   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.244.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.250.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i65.74.252.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.0.0/16    212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.12.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.24.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.28.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.32.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.40.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.44.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.48.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.51.0      212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.52.0      212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.53.0      212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.54.0      212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.55.0      212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.56.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.58.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.60.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.64.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.72.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.79.0      212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.84.0/22   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.92.0/22   212.72.45.57             0    100      0 3356  
14654 i
    Network          Next Hop            Metric LocPrf Weight Path
*>i206.59.96.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.98.0/23   212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.100.0/22  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.104.0/22  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.120.0/22  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.130.0     212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.132.0/22  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.144.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.232.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.234.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.236.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.238.0/23  212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.241.0     212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.242.0     212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.243.0     212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.244.0     212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.245.0     212.72.45.57             0    100      0 3356  
14654 i
*>i206.59.247.0     212.72.45.57             0    100      0 3356  
14654 i
*>i216.12.224.0/19  212.72.45.57             0    100      0 3356  
14654 i
*>i216.12.227.0     212.72.45.57             0    100      0 3356  
14654 i
*>i216.12.250.0/23  212.72.45.57             0    100      0 3356  
14654 i

---

From: Tom Vest <[email-masked]>
Date: Sat, 11 Nov 2006 19:17:00 -0500

On Nov 11, 2006, at 5:15 PM, Tony Li wrote:

>> actually, I asked Geoff about this, and he told me that ~15K
>> AS's had only one upstream AS,
>>
>

This issue is not unknown, and plausibly (personal speculation only)  
is one of the reasons behind the ARIN "policy reinterpretation" of 12  
Feb 2006:

http://www.arin.net/announcements/archives/20060222.html

The issue has troubled me for some time also. No doubt some of the  
apparent single-homers have private AS adjacencies that don't show  
up, e.g., in Route Views. Hard to imagine this explaining away close  
to 15k ASes -- all but about 225 of which post-date RFC 1930, the  
RIRs, et al.

Casual inquiries with the three old RIRs suggest that "very few" ASNs  
have been allocated on the basis of RFC 2270...

Tom Vest

---

From: "Tony Li" <[email-masked]>
Date: Sat, 11 Nov 2006 16:26:32 -0800

> multihomed AS.

Interestingly, multihoming was about 10% of the routing table in 1992,
as well.  It would seem to me that if we could reduce the growth due to
a) TE, b) multihoming, and c) fraudulent PI allocations, then we would
have an impact on the growth rate.

Tony

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 12 Nov 2006 14:45:32 +0100

On 12-nov-2006, at 1:33, Fred Baker wrote:

> On Nov 11, 2006, at 3:39 PM, Iljitsch van Beijnum wrote:

>> This AS is singlehandedly responsible for more than 1% of the  
>> global routing table

Ugh, it's only 0.13% or so. Sorry.

> OK, so here's a proposed fix. Every *other* ISP ponies up $10 and  
> hands some money to this ISP's upstreams to, in their routing  
> policies, accept whatever prefixes from this jerk they are going to  
> accept, and then consider the advertisement of any combination of  
> subsets of an allocated prefix to be a single advertisement of the  
> entire prefix - and collapse said 1% of the route table into a very  
> few routable prefixes.

I'm not sure I understand, but I'm pretty sure it's unworkable...

What about we all give our favorite vendors some $$ and they build in  
some aggregation magic that makes all of this disappear?

---

From: "Tony Li" <[email-masked]>
Date: Sun, 12 Nov 2006 12:20:02 -0800

> some aggregation magic that makes all of this disappear?

Proxy aggregation was rejected by the operational community long ago,
primarily due to the global traffic engineering effects.  The knobs for
doing this manually are already there.

Tony

---

From: Tom Vest <[email-masked]>
Date: Sun, 12 Nov 2006 15:33:07 -0500

On Nov 11, 2006, at 5:15 PM, Tony Li wrote:

> Only one that Geoff could see from his vantage point?

I compiled the data below from the Route Views Archive / OIX ribs  
data I'm using for my dissertation, so the vantage point varies over  
time as new peers / data contributors joined RV. I derived the  
adjacency counts using the CAIDA toolset:

http://www.caida.org/funding/routing/atoms/download/rv2atoms-0.4/

> Or only one period?

Data reflects (only) a single snapshot for each year, the first  
"apparently" complete OIX rib file in each November.

> singly homed customers.  ;-(

Given the caveats above, It looks like the singlehomer phenomenon is  
not as large as originally assumed; and the 15k number may reflect  
the historical total rather than the number of nonconforming ASes at  
any given time. Still if the numbers are accurate, it appears that  
the phenomenon may be growing again as a share of the total. Perhaps  
not surprising now (since 2004) that some large operators have added  
an explicit AS adjacency count to their settlement-free peering  
requirements....

If there is interest, it shouldn't take too much time to determine  
how many singlehomers became multihomers (e.g., vs. simply  
disappearing) in each successive year.

Tom

Year	1997	1998	1999	2000	2001	2002	2003	2004	2005
Benchmark:
Originate>1	Edge=Any							
	2958	4237	6017	8973	11968	14001	16087	18374	20943
Originate>1	Edge=1								
Nov-97	518	297	218	164	128	111	86	77	72
Nov-98		606	434	297	223	189	154	135	123
Nov-99			752	556	394	320	258	229	212
Nov-00				1080	710	540	428	372	341
Nov-01					1740	1172	899	762	680
Nov-02						1824	1385	1159	1035
Nov-03							2101	1740	1512
Nov-04								2741	2360
Nov-05									4127
Singlehomer share	17.51%	14.30%	12.50%	12.04%	14.54%	13.03%	13.06%	 
14.92%	19.71%

---

From: Tom Vest <[email-masked]>
Date: Sat, 11 Nov 2006 19:15:27 -0500

The issue has troubled me for some time also. No doubt some of the  
apparent single-homers have private AS adjacencies that don't show  
up, e.g., in Route Views. Hard to imagine this explaining away close  
to 15k ASes -- all but about 225 of which post-date the RFC 1930, the  
RIRs, et al.

Tom Vest

---

From: Tom Vest <[email-masked]>
Date: Sat, 11 Nov 2006 19:15:27 -0500

Tom Vest

---

From: Fred Baker <[email-masked]>
Date: Mon, 13 Nov 2006 08:44:24 -0800

Both the RIB and the FIB are important, although of course the FIB is  
a more expensive type of memory.

if the raw data in the RIB doesn't scale well, the smartest algorithm  
in the FIB isn't going to be able to make it compact. Yes, good  
algorithms are a good thing. We came here to find a way to make the  
raw data in Internet routing scale.

On Nov 13, 2006, at 8:29 AM, <[email-masked]> wrote:

> I thought the proposal was to not put all that redundant data on  
> your HW
> forwarding path, even if that existed on the BGP routing table. Some
> local aggregation magic within a router.
>
> The issue was  running out of this expensive special memory  
> searched at
> line speeds, not the memory used for BGP protocol operation.
>
> We would not be witnessing this discussion if the solution was to
> utilize smarter algorithms to transform BGP FIB into a next-hop
> forwarding database for a router having fixed set of next hops, right?
>
> 	Jarno
>
>> From: ext Tony Li [mailto:[email-masked]]
>> Sent: 12 November, 2006 22:20
>> To: 'Iljitsch van Beijnum'; 'Fred Baker'
>> Cc: [email-masked]
>> Subject: RE: [arch-d] It's the routing, people!
>>
>>
>>
>> Proxy aggregation was rejected by the operational community
>> long ago, primarily due to the global traffic engineering
>> effects.  The knobs for doing this manually are already there.
>>
>> Tony
>>
>>
>>

---

From: <[email-masked]>
Date: Mon, 13 Nov 2006 18:29:09 +0200

I thought the proposal was to not put all that redundant data on your HW
forwarding path, even if that existed on the BGP routing table. Some
local aggregation magic within a router.

The issue was  running out of this expensive special memory searched at
line speeds, not the memory used for BGP protocol operation.

	Jarno

---

From: Chris Morrow <[email-masked]>
Date: Tue, 14 Nov 2006 01:17:41 -0500

On Nov 11, 2006, at 7:33 PM, Fred Baker wrote:

> policies, accept whatever prefixes from this jerk they are going

oh, this is late, but... 14654 == wayport == airport/hotel/blah  
wireless access provider. I'd imagine they have many hundreds (many  
atleast) seperate links all over creation, they MAY prefer a single  
provider (L3 in the clipped example) or that may just be the view in  
this instance. They may NOT want to have another AS originate their  
covering /16 for some business reasons, their individual sites may be  
multi-homed...

In any case, this has drifted some from architecture I think, eh? If  
you want a interested example try: AS4755  which tops out at 1032  
prefixes which could get aggregated to 66...

-Chris