Subject: [RRG] Revamping BGP?

From: Robin Whittle <[email-masked]>
Date: Sat, 26 May 2007 13:13:23 +1000

In "Re: [RRG] Re: Comments on the Design Goals I-D", Tony Li wrote, in part:

> As I think we've discussed before, it's my personal contention
> based  on my BGP experience that the churn is actually an artifact
> of the  protocol and is not fundamental to the current routing
> architecture.   I believe that the churn can be adequately addressed
> by some  additional implementation sophistication within BGP, and
> I'm actively  and personally working on this topic, albeit at a
> greatly restricted  bandwidth.  Folks interested should stay in
> touch with the IDR  mailing list or drop me a line.

I understand from this that you can foresee significant improvements to
BGP which would reduce the number of updates.

I looked over this year's archives:

  http://www1.ietf.org/mail-archive/web/idr/current/maillist.html

and I couldn't see any discussions related to a significant performance
improvements for BGP.

Earlier this year I proposed optimising DFZ FIBs by using direct memory
lookup, and aligning IPv6 address space to suit this.  My solution
(which I now think should be combined with something like LISP to do
multihoming, TE etc. on single IP addresses and with finer granularity
prefixes than /24) only makes sense with much larger numbers of routes.
 No-one seems to think this is feasible, or at least to the degree which
would substantially cope with projected growth.

Tony, your statement is the first I have seen to the effect that BGP can
be significantly improved.  If you can elaborate here, or offlist, I
would really appreciate it.

Heiner Hummel wrote, in part:

> By aiming for a solution which eliminates the scalability problem
> we would get multiple improvements which you address:
> no convergence time problem, no routing churn, a relaxed situation
> wrt prefix building pressure, no pressure for loc/id-split from the
> scalability problem's point of view (loc/id-split  may have other
> advantages, e.g. like pointing to the right direction of research)
> - and more.

This was what I was trying to do:

  http://www.firstpr.com.au/ip/sram-ip-forwarding/
  http://tools.ietf.org/html/draft-whittle-sram-ip-forwarding-01

- to make the next generation of DFZ routers cope fine with as many /24s
as are possible without a care.  This is flat-routing to /24 granularity
for IPv4, and something similar for IPv6 within a restricted range (a
/10), which would still provide plenty of address space (33 million
/35s) for the next 10 to 15 years.  (Then, with cheaper RAM, double the
amount in the FIB, extend that range to a /9 with the same granularity,
and perhaps change the IPv4 granularity to /25.)  Then we can forget
about route aggregation, which means address space can be assigned more
frequently, in smaller chunks to match short term needs rather than
larger chunks for possible long-term growth.  Then, there will be much
greater actual utilisation of IP addresses, on average, which is vital
for IPv4.

No-one has said that my FIB and address management system wouldn't work.
  Probably current routers such as the M120, MX960 and CRS-1 already
have more than enough RAM.

The stumbling block seems to be that no-one things BGP can cope with 2
million or so routes.  It seems to me that it could, if routers had a
lot more RAM (and maybe 64 bit CPUs to easily address it).  Gigabytes of
RAM is cheap these days.  But it would also be necessary to largely
suppress whatever most router operators deem to be "unnecessary" updates.

The question of the Internet's future routing and addressing
architecture depends entirely on how much BGP and the DFZ routers can be
improved to handle more advertised prefixes.

This seems to mainly depend on the stability of the BGP network, and the
problems with either an unreasonable rate by which some people change
their route advertisements and/or problems in the network causing
oscillations and therefore excessive streams of updates.  I guess there
is also the problem of increased updates when a link or router fails.

Does anyone have hopes or proposals for significantly souping up BGP, or
for replacing it slowly with some backwards-compatible improvement?

  - Robin

--
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: Tony Li <[email-masked]>
Date: Sat, 26 May 2007 01:03:33 -0700

Robin,

> would really appreciate it.

I've just submitted an Internet draft that outlines the directions  
that I'm exploring.  Look for it sometime next week.

Please note that it is at this point VERY informal and calling it  
half-baked would at this point be a gross overstatement.

> suppress whatever most router operators deem to be "unnecessary"  

The problem is that the flux of necessary updates would still kill  
you.  You're talking about scaling up the static portion of the data  
by an order of magnitude.  To scale up the dynamics, you also have to  
scale up the processor and memory speeds by an order of magnitude  
too, divided by whatever savings that we can accomplish.  And even  
then, you're only achieving the same convergence times that we have  
today, which some people deem to be unacceptable.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Sun, 27 May 2007 11:18:48 +0200

On 2007-05-26 10:03, Tony Li wrote:
> I've just submitted an Internet draft that outlines the directions that 
> I'm exploring.  Look for it sometime next week.
> 

What I think will be interesting is to see whether a significant
fraction of today's observed churn will still be there after applying
those "directions". That residual churn could be a target for RRG.

    Brian

---

From: Lixia Zhang <[email-masked]>
Date: Tue, 29 May 2007 13:11:49 -0700

> that I'm exploring.  Look for it sometime next week.

the draft is out now:

http://www.ietf.org/internet-drafts/draft-li-bgp-stability-00.txt

FYI.

---

From: Robin Whittle <[email-masked]>
Date: Fri, 01 Jun 2007 21:00:16 +1000

I have listed some papers which I think are of interest
regarding significant improvements to BGP:

http://www.firstpr.com.au/ip/sram-ip-forwarding/#BGP_improvements

Please suggest any others to add to this list.

  - Robin

BGP Stability Improvements
Tony Li, May 2007

  http://tools.ietf.org/html/draft-li-bgp-stability

BGP-RCN: Improving Convergence through Root Cause Notification
Dan Pei, Matt Azuma, Daniel Massey, and Lixia Zhang.  2005

  http://www.beyondbgp.net/pubs/2005/bbgp_comnet05.pdf

HLP: A Next-generation Interdomain Routing Protocol
Lakshminarayanan Subramanian et al. 2005

  http://www.sigcomm.org/sigcomm2005/paper-SubCae.pdf

Scaling IP Routing with the Core Router-Integrated Overlay
Xinyang Zhang et al. 2006

  http://www.ieee-icnp.org/2006/papers/s4a4.pdf

Differentiated BGP Update Processing for Improved Routing
Convergence
Wei Sun, Zhuoqing Morley Mao and Kang G. Shin  2006

  http://www.eecs.umich.edu/~zmao/Papers/bgp-updates.pdf