[oclug] Scalability question
greg at cr1004769-a.slnt1.on.wave.home.com
Thu Mar 15 11:32:32 EST 2001
>>>>> "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.
More information about the OCLUG