[oclug] Scalability question

[Greg Franks]

>>>>> "David" == David F Skoll <dfs at roaringpenguin.com> writes:
    David> Also, On Wed, 14 Mar 2001, Greg Franks wrote:

    >> Hmmm -- sounds like a router to me.  Forwarding is the killer
    >> (i.e., the routing tables).  Routers use hardware.  Look up
    >> references to "ternary CAM".  From there, you can find
    >> references to forwarding performance.

    David> Yes, if the routes are scanned sequentially, it's ugly.
    David> But the routing table will be such that there will be many
    David> host routes.  So instead of scanning sequentially, is the
    David> kernel smart enough to hash destination addresses and look
    David> up the route that way?  If you use a proper hash table
    David> implementation, looking up a host route should have an
    David> expected complexity of O(1).

The kernel is probably using a B-Tree.  Nobody in their right mind
scans a forwarding table sequentially.  (A table of only 1000 entries
would require, on average 500 lookups, by which time the packet
transit time is blown...).  I think default-free tables are on the
order of 50,000 entries now.

If you try be clever with the ordering of the table, bear in mind that
route inserts and deletes can be frequent, and if those operations
take a lot of time, your forwarding performance is affected.

    David> (A host route has netmask 255.255.255.255, so the
    David> destination address must match exactly, which facilitates
    David> the use of a hash table.)

    David> I might have to hack the kernel for this special case, I
    David> guess.  It seems that a routing algorithm which first tries
    David> an exact match on a host address using hashing, falling
    David> back to the usual algorithm (scan sequentially, pick
    David> most-specific matched route) on a miss, is pretty easy to
    David> implement and can probably be used even in mainstream
    David> kernels without a penalty.

Look up references for "router performance" (there wre some timely
articles in a recent IEEE Micro/Network magazine).  In almost every
case, router performance means forwarding speed.  Forwarding speed is
highly dependent on next-hop lookup.

Software forwarding is a "well known problem" (relatively speaking).
You can proably get the code out of the BSD kernel.
-- 
   __@               Greg Franks              <|       _~@ __O 
 _`\<,_         Ottawa, Ontario, Canada        |O\   -^\<;^\<, 
(*)/ (*)                                       (*)--(*)%---/(*)
          "Where do you want to go today?"   Outside.