Subject: [RAM] Paper on FIB structures

From: Robin Whittle <[email-masked]>
Date: Fri, 13 Apr 2007 20:22:02 +1000

A list member told me of a "Stanford paper which covers some very
elegant FIB structures, and describes some of the others that are
considered.  These papers talk about the trade-offs in number of
look ups, amount of memory, etc..."

He couldn't point me to it and I couldn't find mention of it looking
in the archives.  Does anyone recall such a paper?

   - Robin

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

---

From: Robin Whittle <[email-masked]>
Date: Fri, 20 Apr 2007 12:45:07 +1000

> look ups, amount of memory, etc..."

  Algorithms for Packet Classification
  Pankaj Gupta and Nick McKeown
  IEEE Network, March 2001

http://tiny-tera.stanford.edu/~nickm/papers/classification_tutorial_01.pdf

I was happy - and not surprised - to find a much earlier proposal
similar to my SRAM-forwarding idea.  In 1998, Nick McKeown and
colleagues suggested using the to 24 IPv4 address to directly access
RAM:

  Routing Lookups in Hardware at Memory Access Speeds.
  Pankaj Gupta, Steven Lin and Nick McKeown
  IEEE INFOCOM April 1998, Vol 3, pp. 1240-1247.

  http://tiny-tera.stanford.edu/~nickm/papers/Infocom98_lookup.pdf

Nick McKeown's site has a large number of papers and presentations:

  http://tiny-tera.stanford.edu/~nickm/

  - Robin