Subject: [RRG] a backwards compatible FIB scaling approach

From: Paul Francis <[email-masked]>
Date: Thu, 6 Mar 2008 13:35:48 -0500

Gang,

Lately my student Hitesh Ballani and I (and more recently another student
Tuan Cao) have been working on a way to scale FIBs without requiring any
changes to routers or routing protocols, and without requiring and
coordination between ISPs.  Rather, it can all be done through configuration.
The basic idea is to split the IP address space into virtual prefixes, and
then run each prefix as a kind of VPN.  As far as we can tell, an ISP can
realistically get 5x to 10x reduction in FIB size with very little (a few
precentage) increase in load and latency.  (Or, looked at another way, an ISP
can extend the lifetime of its routers by many years without any real
performance hit.)

We've written up a short informal description of the idea, posted at
http://www.cs.cornell.edu/people/francis/va-wp.pdf.

This work doesn't have all the capabilities that I know the RRG is going
after (mobility, traffic engineering), but nevertheless I thought folks would
be interested.

Any comments appreciated.

PF

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: "William Herrin" <[email-masked]>
Date: Thu, 6 Mar 2008 18:02:58 -0500

>  http://www.cs.cornell.edu/people/francis/va-wp.pdf.

Hi Paul,

Can you read the following and let me know if I've grasped your basic
idea? If not, what am I missing?

1. Make the MPLS label reflect the neighbor's entry router and
protocol instead of our egress router and protocol. This allows us to
drop the BGP table from our egress routers.

2. Move the MPLS labelers to a handy location or set of locations away
from the entrance so that entry routers can drop the BGP table as
well. The entry routers then send packets towards the routes in the
IGP. The IGP default route will, of course, lead to a nearby labeler.

3. Parallelize the MPLS labelers and instead of announcing a default
route into the IGP, have each labeler announce the specific very short
CIDR blocks (generally /8 or shorter) for which they will encode
traffic. Every time you double the number of labelers, you halve both
the traffic to each labeler and halve the number of entries each
labeler carries in its FIB.

4. The parallel labelers need not be at the same site. You could, for
example, place all of the labelers for the APNIC region /8's near your
Pacific link and place the labelers for the RIPE region /8's near your
Atlantic link. In most networks this will still produce something
close to the optimal route.

5. This means you probably move the full RIB off the routers entirely
and on to cheap COTS systems (your "conduit routers" that don't
forward packets). The labelers then get feeds of only those portions
of the RIB for which they will apply labels.

Questions:

a. How do we generate labels for the neighbor's first hop instead of
our last hop? Can we do this now or would it take new software?

b. How does one of the labelers go about deciding that it is in good
enough working order with reasonable BGP and label feeds to offer an
aggregate route into the IGP? Without aggregation the function is
implicit, but once you add aggregation the traffic will head your way
whether you have a label to send it to or not.

Regards,
Bill Herrin

-- 
William D. Herrin                  [email-masked]  [email-masked]
3005 Crane Dr.                        Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: Paul Francis <[email-masked]>
Date: Thu, 6 Mar 2008 19:55:33 -0500

Reply inline

-----Original Message-----
From: [email-masked] 代理 William Herrin
Sent: 3/6/2008 (木) 6:02 午後
To: Paul Francis
Cc: [email-masked]; Hitesh Ballani; caotuan
Subject: Re: [RRG] a backwards compatible FIB scaling approach

Hi Paul,

YES

It will be BGP that delivers the packet to the labeler, but otherwise
correct.

Sounds right.

Maybe, but we haven't looked at this style of optimization.  Our perf numbers
are based simply on putting a couple labelers for each virtual prefix (i.e.
/8) in each large POP.

The conduit routers are off-the-shelf route reflectors.  My understanding is
that in practice these tend to be router vendor products as well, but they
don't need all the line cards and such.

Questions:

Everything in the paper can be done with existing product.  You basically
statically configure the neighbor's /32 into OSPF, carry that around with
OSPF, and use LDP to establish the MPLS tunnels.

Through configuration, route reflectors know which routers (labelers) do
aggregation for which virtual prefixes (i.e. /8's).  When the route reflector
feeds the appropriate prefix to the labeler, it also feeds the next hop (the
neighbor router /32).  Because we fed the neighbor /32 addresses into OSPF,
every router has an MPLS tunnel to every neighbor router.

PF

Regards,
Bill Herrin