why not AS number based prefixes aggregation
Hi, everyone: For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme. -yang
On 9/09/2008, at 1:20 AM, yangyang. wang wrote:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
I expect you'll see something similar to this in IPv6 long term - most ASes will likely not need to originate more than their RIR 'block' (I can never figure out whether to call it an assignment or an allocation, and whenever I do I seem to get it wrong). Note that many ASes are expected to intentionally de-aggregate their prefixes. We've so far expected to see this for traffic engineering purposes (ie. to control sharing of load across several different links), however we might see intentional de-aggregation by people attempting to minimise BGP prefix hijacking? Who knows. That's a pretty scary though when considering IPv6.. There was a Cisco slide somewhere (I think originally by Tony Hain?) that had info about that, ie. actual numbers. It's slide 24 (and several slides leading up to it) in the following slide pack by Vince Fuller, but it was old in Feb 2007 when this was put together, so it's even older now - anyone have anything more recent. Anyway, enjoy: http://www.apricot2016.info/apricot2007/presentation/apia-future-routing/api... -- Nathan Ward
Excerpts from yangyang. wang on Mon, Sep 08, 2008 09:20:38PM +0800:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
-yang
It might be the right level of granularity for policy but is too coarse for routing. You want to be able to route on prefixes (even if not everyone does it) for flexibility/TE. Also, ASNs are not aggregatable so we can't use them to represent a large number of independently routed networks.
On Sep 8, 2008, at 6:46 AM, Scott Brim wrote:
Excerpts from yangyang. wang on Mon, Sep 08, 2008 09:20:38PM +0800:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
-yang
It might be the right level of granularity for policy but is too coarse for routing. You want to be able to route on prefixes (even if not everyone does it) for flexibility/TE. Also, ASNs are not aggregatable so we can't use them to represent a large number of independently routed networks.
An AS is a collection of networks with a common routing policy. If you are subdividing into multiple routing policies for TE purposes, you, theoretically, need separate ASNs for each routing policy. BTW, if you have multiple unique routing policies, it is perfectly valid to justify multiple ASNs on that basis. Owen
Thank you, Scott. TE is a key reason for using specific prefixes. I think that most TEs are deployed in intra-domain, and the inter-domain TEs applied to downstream AS multihomed to many different upstream ASes could be made thru AS number based aggregation. The TE between two ASes with many links (for load balance) may be implemented by layer-2 filter list staticly configured. 2008/9/8 Scott Brim <swb@employees.org>
Excerpts from yangyang. wang on Mon, Sep 08, 2008 09:20:38PM +0800:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
-yang
It might be the right level of granularity for policy but is too coarse for routing. You want to be able to route on prefixes (even if not everyone does it) for flexibility/TE. Also, ASNs are not aggregatable so we can't use them to represent a large number of independently routed networks.
If I understand you right, what you're suggesting is that, in place of a MED or a localpref, I deploy a layer 2 filter on all of my devices for every prefix I want to touch the policy for at a level more granular than AS. This does not improve the scalability of BGP, it destroys that scalability and merely trades hardware capacity used for routing updates for capacity used for manual filters. At any rate, you cannot aggregate somebody else's announcements. Doing so destroys policy information (like more specific announcements, MEDs, and communities) and creates implementation nightmares (like handling route withdrawls.) yangyang. wang wrote:
Thank you, Scott. TE is a key reason for using specific prefixes. I think that most TEs are deployed in intra-domain, and the inter-domain TEs applied to downstream AS multihomed to many different upstream ASes could be made thru AS number based aggregation. The TE between two ASes with many links (for load balance) may be implemented by layer-2 filter list staticly configured.
2008/9/8 Scott Brim <swb@employees.org>
Excerpts from yangyang. wang on Mon, Sep 08, 2008 09:20:38PM +0800:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the
shortest
paths are calculated based on traversed AS numbers. The prefixes in the
same
AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
-yang
It might be the right level of granularity for policy but is too coarse for routing. You want to be able to route on prefixes (even if not everyone does it) for flexibility/TE. Also, ASNs are not aggregatable so we can't use them to represent a large number of independently routed networks.
On Mon, September 8, 2008 09:46, Scott Brim wrote:
Also, ASNs are not aggregatable so we can't use them to represent a large number of independently routed networks.
Scott, I'm not sure an Autonomous System would want to be aggregated. By its nature it is capable of having arbitrary connectivity. On the other hand, addresses can be aggregated. An ASN-based address system would support a more efficient form of aggregation than we have today. And routing (including TE) could be supported by attributes, rather than by address/prefix-len. *shrug* Yang, As somebody pointed out already, LISP provides approximately the same sort of mechanism. Though it uses a list of Locators (backbone/core IP addresses) rather than ASNs to identify an Endpoint's site, relying on a lightweight form of tunneling through the core to support endpoint communication. This allows it to preserve both IPv4/v6 and existing global routing protocols (and thus deployed support). The downside is that it requires a more dynamic mapping mechanism than a theoretical ASN-based approach. You can learn more at http://www.lisp4.net/, and discuss it on the lisp-interest@lists.civil-tongue.net mailing list. Cheers, -Benson
On Mon, Sep 8, 2008 at 9:20 AM, yangyang. wang <wyystar@gmail.com> wrote:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
Yang, Two reasons: 1. The AS# alone is insufficiently granular to support traffic engineering for inbound traffic. 2. It would overload a location function on the existing identity function. The AS# presently identifies the entity announcing the routes. Routes from the same AS# come from the same entity. If we routed by AS#, the AS# would also serve to specify the entity's location in the network graph. One of the implications of the research in the RRG is that this identity + location functional overloading is the root cause of our route table problems. Specifically, the IP address both provides a node identity for use by the layer-4 protocols and a layer-3 location within the network graph. Had the IP protocol separated the two functions, it would be almost as trivial to expand the routing system as it is to expand the DNS system because the location part effectively aggregates by topology while the identity part has a nasty habit of changing locations. Unfortunately that realization doesn't appear to have left any corrective actions which are both clean and compatible with the existing system. Regards, Bill Herrin -- William D. Herrin ................ herrin@dirtside.com bill@herrin.us 3005 Crane Dr. ...................... Web: <http://bill.herrin.us/> Falls Church, VA 22042-3004
On Mon, Sep 8, 2008 at 9:20 AM, yangyang. wang <wyystar@gmail.com> wrote:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
you might look at LISP, which is sort of like 'route by asn', with some other benefits added as well. <http://www.nanog.org/mtg-0706/Presentations/lightning-farinacci.pdf> -Chris
Christopher Morrow wrote:
On Mon, Sep 8, 2008 at 9:20 AM, yangyang. wang <wyystar@gmail.com> wrote:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
you might look at LISP, which is sort of like 'route by asn', with some other benefits added as well.
<http://www.nanog.org/mtg-0706/Presentations/lightning-farinacci.pdf>
NANOG site changed, thus that is now: http://www.nanog.org/meetings/nanog40/presentations/lightning-farinacci.pdf and: http://www.nanog.org/meetings/nanog41/presentations/lisp-nanog-abq.pdf Also check http://www.lisp4.net/ as they are actually testing this in live environments :) Greets, Jeroen
Topological aggregation based on ASN is often too course granularity, see this paper: http://www.cs.ucla.edu/~rveloso/papers/giro.pdf specifically Fig4 is a good example, and sec 4C. Cheers, --Ricardo On Sep 8, 2008, at 6:20 AM, yangyang. wang wrote:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
-yang
This thread begs an interesting question: what is the right amount of granularity for load balance? Folks here are saying that one-entry-per-AS is too course...an AS wants to influence load on incoming links, and so it needs multiple entries. On the other hand, it is hard to imagine that we need hundreds of entries per AS, or even dozens. So I'm curious...if we could wave a magic wand and control the exact number of entries any AS needs to advertise, what would folks consider to be roughly the right number of entries? Thanks, PF
-----Original Message----- From: Ricardo Oliveira [mailto:rveloso@cs.ucla.edu] Sent: Monday, September 08, 2008 1:11 PM To: nanog@merit.edu Subject: Re: why not AS number based prefixes aggregation
Topological aggregation based on ASN is often too course granularity, see this paper: http://www.cs.ucla.edu/~rveloso/papers/giro.pdf specifically Fig4 is a good example, and sec 4C. Cheers,
--Ricardo
On Sep 8, 2008, at 6:20 AM, yangyang. wang wrote:
Hi, everyone:
For routing scalability issues, I have a question: why not deploy AS number based routing scheme? BGP is path vector protocol and the shortest paths are calculated based on traversed AS numbers. The prefixes in the same AS almost have the same AS_PATH associated, and aggregating prefixes according to AS will shrink BGP routing table significantly. I don't know what comments the ISPs make on this kind of routing scheme.
-yang
Paul Francis wrote:
AS, or even dozens. So I'm curious...if we could wave a magic wand and control the exact number of entries any AS needs to advertise, what would folks consider to be roughly the right number of entries?
Wouldn't this greatly depend on the span/breath of your network ? If you are a large nationwide (or even international) ISP/network, then you want to be able to distribute your network so that someone on west coast trying to reach one of your west coast IP addresses will have a pretty direct route into your west coast infrastructure instead of funnelling all traffic into one central location. But a smaller ISP based in only one city would not need to distribute traffic through different entry points since traffic from each transit provider would end up on the same router. So I am not sure one could draw any "right number of entries".
Sorry, my question was not clear. By "entries" I meant "routes" or "prefixes". For instance, some ISPs today deaggregate in order to load-balance, so they advertise multiple prefixes or routes instead of one. Of course, the "right" number would vary from ISP to ISP (as someone already pointed out to me), but I'm not even sure what the criteria would be for how many routes one needs to load balance...i.e. depends on the number of AS neighbors?, depends on the number of depends on the number of BGP neighbors?, depends on your load balancing mechanism (MEDs versus path prepending versus ....???)? The point is this...BGP seems to give use two tools...a machete (AS numbers) and a scalpel (prefixes). If I want to cut a steak (load balance), the machete is too coarse, the scalpel is too fine. What's the right tool??? PF
-----Original Message----- From: Jean-François Mezei [mailto:jfmezei@vaxination.ca] Sent: Monday, September 08, 2008 10:21 PM To: nanog@nanog.org Subject: Re: why not AS number based prefixes aggregation
Paul Francis wrote:
AS, or even dozens. So I'm curious...if we could wave a magic wand and control the exact number of entries any AS needs to advertise, what would folks consider to be roughly the right number of entries?
Wouldn't this greatly depend on the span/breath of your network ? If you are a large nationwide (or even international) ISP/network, then you want to be able to distribute your network so that someone on west coast trying to reach one of your west coast IP addresses will have a pretty direct route into your west coast infrastructure instead of funnelling all traffic into one central location.
But a smaller ISP based in only one city would not need to distribute traffic through different entry points since traffic from each transit provider would end up on the same router.
So I am not sure one could draw any "right number of entries".
participants (12)
-
Benson Schliesser -
Christopher Morrow -
Dave Israel -
Jean-François Mezei -
Jeroen Massar -
Nathan Ward -
Owen DeLong -
Paul Francis -
Ricardo Oliveira -
Scott Brim -
William Herrin -
yangyang. wang