[oclug] Scalability question

[David F. Skoll]

On Wed, 14 Mar 2001, Taavi Burns wrote:

> Diverging a bit...how would one connect a few thousand PPP interfaces to
> one computer?  PPPoE?

Could be... :-)

> Perhaps a tree would be in order (e.g. up to 253 leaves connect to a local
> coalater; up to 253 coalaters connect up to another....etc). e.g. one
> server per class C network.  Then routing is relatively easy; never more
> than 254 route for each server to remember.

Unfortunately, we have very stringent constraints on hardware.  It's got
to be one box (or at most a few; too few to do what you suggest.)

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.

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

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

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

--
David.