Subject: [RAM] Some Relevant Presentations at the recent NANOG

From: Marshall Eubanks <[email-masked]>
Date: Thu, 8 Feb 2007 14:01:25 -0500

Here is a list of presentations from this week's meeting that I think  
might be relevant to this effort. In each case, it is title, followed  
by html abstract followed by presentation(s).

Pushing the FIB limits, perspectives on pressures confronting modern  
routers.
http://www.nanog.org/mtg-0702/jaeggli.html
http://www.nanog.org/mtg-0702/presentations/fib-editorial.pdf
http://www.nanog.org/mtg-0702/presentations/fib-hankins.pdf
http://www.nanog.org/mtg-0702/presentations/fib-desilva.pdf
http://www.nanog.org/mtg-0702/presentations/fib-ryan.pdf
http://www.nanog.org/mtg-0702/presentations/fib-scudder.pdf  (2  
million routes!)
http://www.nanog.org/mtg-0702/presentations/fib-atkinson.pdf

Abstract: R-BGP: Ensuring Connectivity During BGP Convergence
http://www.nanog.org/mtg-0702/kushman.html
http://www.nanog.org/mtg-0702/presentations/Kushman.pdf

Abstract: Introduction to Fast Convergence with Bidirectional  
Forwarding Detection (BFD)
http://www.nanog.org/mtg-0702/akhter.html
http://www.nanog.org/mtg-0702/presentations/akhter.pdf

Regards
Marshall Eubanks

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: Jari Arkko <[email-masked]>
Date: Tue, 13 Feb 2007 09:48:44 +0200

Thanks for posting these, they were indeed useful.
I found John Scudder's presentation particularly
interesting. The interesting part wasn't really the
current number of routes, but rather what he said
about how this tracks hardware component development.
I think he said 10M route entries could be reached
with current design, merely by adding more DRAM.
My understanding is that similar designs based more
on commodity hardware components such as DRAMs
exist also from other vendors. Of course, this
does not mean that there are no issues; bottlenecks
may still exist elsewhere in the system, and upgrading
to new product architectures will be costly for the
providers.

The other part that I found interesting was that
multiple vendors talked about compression mechanisms
that make the FIB fit a smaller memory. Some of
the providers were worried about such techniques.
It was unclear to me if the techniques were so
aggressive that they might change the behaviour,
or if it was merely an issue of an algorithmic
conversion to an equal but smaller size table.
The latter seems workable, the former could
lead to loops etc.

One presentation that you did not mention below was
http://www.nanog.org/mtg-0702/presentations/smith-lightning.pdf
This discusses the growth of de-aggregation, and argues
that there is more de-aggregation in the "newer" parts
of the network, such as in Asia and Africa, with some
ASNs having many prefixes (up to 1000) that
could perhaps be saved with better BGP practices...

Jari

---

From: Tony Li <[email-masked]>
Date: Tue, 13 Feb 2007 00:14:05 -0800

> The latter seems workable, the former could

Jari,

Having worked on this in a previous life, there are plenty of  
techniques that (if properly implemented ;-), will provide  
semantically identical tables.  This has been tested and shown to  
work.  It has also been shown to be somewhat CPU intensive, so there  
are some side effects.  It's just another time/space tradeoff at our  
disposal...

Tony

---

From: Jari Arkko <[email-masked]>
Date: Tue, 13 Feb 2007 10:26:52 +0200

Tony,
> are some side effects.  It's just another time/space tradeoff at our

Right. I would expect the stuff to be reasonably easy to
get right and test. Not a very hard thing in comparison
many other things that we do with computers. Are the
side effects what the providers are worried about? Or bugs,
the inability to predict how well compression works for the
given FIB memory size, or have people used non-semantically
identical tables?

Are there papers that analyze typical compression ratios
in the current Internet?

Jari

---

From: Tony Li <[email-masked]>
Date: Tue, 13 Feb 2007 01:21:25 -0800

> given FIB memory size, or have people used non-semantically

Without having spoken to them, I would assume that their first  
concern is bugs.  Vendors have shown a remarkable ability to  
distribute flaws.  Yours truly is one well-known perpetrator  
thereof.  ;-)

> Are there papers that analyze typical compression ratios

I haven't seen any, but we were seeing 30% pretty easily.

Tony

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 13 Feb 2007 10:43:08 +0100

On 13-feb-2007, at 9:26, Jari Arkko wrote:

[FIB compression]

> Are the

What I'm worried about is that this would introduce a measure of non- 
determinism. I.e., everything is working fine, FIB is compressed by  
30% and 90% of the FIB space is in use. But then a few very  
unfortunate prefixes are added, compression goes down the toilet and  
we're at 105% of available FIB space...

---

From: Mark Townsley <[email-masked]>
Date: Tue, 13 Feb 2007 10:57:09 +0100

My very rough guess is that for designs based on a DRAM FIB, the benefit 
of compression vs. cost would be fairly low. On SRAM based systems, 
perhaps it is more advantageous. One thing that the set of NANOG 
presentations make very clear is that there are different architectures 
out there, each with different tradeoffs.

- Mark

Iljitsch van Beijnum wrote:
> What I'm worried about is that this would introduce a measure of 
> non-determinism. I.e., everything is working fine, FIB is compressed 
> by 30% and 90% of the FIB space is in use. But then a few very

---

From: Elwyn Davies <[email-masked]>
Date: Tue, 13 Feb 2007 11:29:29 +0000

[FIB Compression]
>  Are the side effects what the providers are worried about? Or bugs,
>
>   
Another major issue with clever FIB schemes whether compressed or 
otherwise is the cost/possibility of incremental updates.  I haven't 
been involved with big router design for a while but a significant 
bottleneck was getting a large FIB out to each of a largish number of 
interface cards from the central controller and then updating it.  If 
you end up with the need to replace the whole FIB (or even a significant 
chunk of it) to do an update this is bad news, and obviously gets worse 
as the FIB grows.

As I understand it the gold standard for IP lookup algorithms at the 
moment is the Tree Bitmap  algorithm (Eatherton, Varghese and Dittia) 
described in
http://www.cs.cornell.edu/courses/cs419/2005sp/tree-bitmap.pdf.
This uses a trie based structure with a kind of 'compression' into 
bitmaps that allows for incremental updates and is well matched to wide 
data path synchronous DRAM operations.  According to Varghese's web page 
Cisco have confirmed that this algorithm is used in the CRS-1.
This set of lecture notes is alleged to help explain how it works (but I 
am not so sure that it helps):
http://www.cs.cornell.edu/courses/cs419/2005sp/419-sp05-06-fast-lookup-v0.pdf

This paper http://www.arl.wustl.edu/~todd/fipl.pdf describes a research 
hardware implementation of the tree bitmap algorithm.

This paper from 2001 covers most of the algorithms predating the tree 
bitmap algorithm (including its immediate ancestor the Lulea algorithm) 
and gives theoretical and practical comparisons of their performance 
both in lookups and updates:
http://www.eurecom.fr/util/publidownload.en.htm?file=/homesdocs/publications/htdocs/ce/bierer-010301.pdf

Regards,
Elwyn