optimum routing table size

On 22-jun-04, at 15:25, Masataka Ohta wrote:

> However, it is a lot less expensive if global routing can be
> performed only by looking 13 bits of the address.

> There is no associative memory necessary.

> It's just a memory of 8K entry with no associativity.

> I think it is still reasonable to have an associative memory
> of, say, 1K entry, for local routing.

Most routers don't use associative memory or CAMs for routing table 
lookups, this is mostly done for layer 2 switching.

In addition to using a CAM, obviously any kind of data structure can be 
used to store routing information, such as linked lists (not efficient 
as they must be searched serially), arrays or various types of trees. 
Vendors such as Cisco and Juniper use n-way tries for this, which is 
generally quite efficient even for lookups in very large tables.

(Note though that looking up routes for the purpose of forwarding is 
not the main operational issue with a large routing table, as this 
scales at worst at O(log(n)): the real problem is processing updates, 
which scales at O(log(n)*n), and convergence times after links come up 
or go down, which scale linearly.)

I don't think CAMs are the right solution, as they are very inflexible 
and also very power-hungry. If a more efficient lookup mechanism is 
desired, it would probably make sense to see if it's possible to store 
the routing table in a flat array. This way, looking up a route always 
takes one memory cycle, it doesn't get much better than that. Obviously 
then the routing table must fit in memory, which means the longest 
prefixes that can be looked up this way are in the order of 26 bits. 
This is pretty close to the length of prefixes given out by the RIRs.

In any event, I think putting an artificial limit on the size of the 
routing table is probably more harmful than useful, especially in the 
long run and/or if the limit is quite low such as 8k.

A more fruitful approach would be to look at mechanisms to remove 
unnecessary routing information from routing tables. The obvious way to 
do this would be to take advantage of geographic grouping of prefixes 
where possible.