Subject: [arch-d] on design of ASN-based BGP routing table

From: "william(at)elan.net" <[email-masked]>
Date: Sun, 19 Nov 2006 09:55:27 -0800 (PST)

Before several times (and as part of several proposals) it has been
mentioned that we should consider ASN BGP routing table as base and
build on top of that. I want to give some thoughts on advantages of
this and how it could potentially be implemented without radical
routing architecture changes that could come later.

First note that even though you may see several ip blocks right now
being advertised by same network AS, more often then not the routing
policies for those blocks are the same. So imagine that instead of
having full routing entry for each block:
  10.0.1.0/24 <as path to AS65001> <list of communities>
  10.0.2.0/24 <as path to AS65001> <list of communities>
You would have entry like:
  65001 <as path to 65001> <list of communities> <10.0.1.0/24 10.0.2.0/24>

I know it may look like that's almost same space but it actually is not
because there is considerable overhead for each BGP entry due to path
and other attributes and ip blocks can also be compressed and not require 
sending entire 64/128bit+mask for each IPv6 entry. There is also potential 
here to combine both IPv4 and IPv6 into single routing  table (which may 
not be good for some but see below how you can separate routing entries 
by adding suffix to ASN).

Another thing is that some time in the past its been proposed that IPv6
allocations be done by default based on ASN, i.e. there is specific
rule that says that say AS65001 gets ip block <special prefix>::<as number>
If that is done then we'd not even need to include ip block and just
ASN entry would be enough for remote end to know how to reach certain
network using BGP.

As far as design if somebody needs multiple routing policies for their
blocks it could be done so that they add suffix of their choice to make 
full ASN (yeh, it looks more like ip block then...) i.e.:
  65001.1 <as path to 65001> <list1 of communities> <10.0.1.0/24>
  65001.2 <as path to 65001> <list2 of communities> <10.0.2.0/24>
The above is basically equivalent to current situation with how you use
BGP but this is more rare and if you look at routing entries per ASN, 
largest number of them have basically same routing policy information.

There is also potential for small network that want to be multi-homed
but may not be good choice for having its own ASN and ip block to do
it so that their blocks are directly listed by multiple ASNs:
  65001 <as path to 65001> <list of communities> <10.0.1.0/24>
  65002 <as path to 65002> <list of communities> <10.0.1.0/24>
(the above 10.0.1.0/24 would part of ip block from either 65001 or 65002)
The final hop would be some private ASN used between this small network
and 65001 & 65002 which does end up in public BGP.

I know above is not quite a radical change to architecture as some
are suggesting, but I think it can go long way towards managing BGP
table growth. And having ASN-based routing also gives advantages for 
trying different architecture schemes later (for example no public ip 
blocks at all where DNS would point to ASN and for each IP packet, it 
would include URL and when delivered to final note it can use that for 
deciding how to route on local network).

-- 
William Leibzon
Elan Networks
[email-masked]

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

---

From: "Schliesser, Benson" <[email-masked]>
Date: Thu, 23 Nov 2006 12:45:11 -0600

william(at)elan.net [mailto:[email-masked]] wrote:
> So imagine that instead of having full routing entry for each block:

Today's self-described packets use the address, not the ASN, to direct
their forwarding. Thus an AS-based routing system alone isn't adequate:
each router still has to do a lookup against an address space FIB in
order to forward. For AS-based routing to be useful we would have to
have packets indicate their destination AS, too.

However, gateways that do the address->ASN lookup would still need to
manage an address-based table. (This includes a component of routers,
since there are no routers that purely route i.e. routers also have host
stacks for management etc.) So I'm not sure this solves the problem by
itself. It might let core routers forward faster, with MPLS-like
switching, but it doesn't reduce the scale problems for the routers near
the edge. We need to introduce some sort of address
compression/aggregation mechanism to achieve that in an AS-based
architecture.

(And with a good aggregation mechanism would we even need AS-based
routing? Or with a real Loc/ID split would we even need a good
aggregation mechanism?)

Cheers,
-Benson

---

From: "william(at)elan.net" <[email-masked]>
Date: Thu, 23 Nov 2006 12:04:36 -0800 (PST)

On Thu, 23 Nov 2006, Schliesser, Benson wrote:

> Today's self-described packets use the address, not the ASN,

If you notice I brought up old idea of having IPv6 blocks allocated
based on ASN which should work for greater majority of networks.
Some very large ones would still need allocations that are larger,
but considering size of ip6 space available, we can make it a rare
case. The issue still remains how to deal with small multi-homing
networks well without greatly increasing rib.

> to direct
> order to forward.

You can't ever avoid it entirely, but you can make this process
a lot more efficient.

> For AS-based routing to be useful we would have to

That would be optional MPLS-like optimization, which while not required
for such a system would help for core routers processing billions of 
packets.

You do bring interesting general engineering point that one of the
options for new architecture maybe to add some sort of routing header
to all packets leaving edge network and going through global Internet
(of course IETF is full of packet engineers who often take this
approach - in fact is maybe one of those a bit overused... so we'd
have to think if its realy needed). And notice that to add such
a routing header you still need a lookup table available at the
origin - but do note that most systems send quite a larger number
of packets to certain destinations (flows) so once first lookup
is done this can be well hashed - that is in fact how dns works.

-- 
William Leibzon
Elan Networks
[email-masked]