Re: optimum routing table size

[Masataka Ohta <mohta@necom830.hpcl.titech.ac.jp>]

Iljitsch;

>> 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.

It is because CAM is not large enough for the global routing table.

Let's assume that the number of local route is smaller
than CAM size.

> 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.

1K CAM is very fast.

> (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)):

Note that the amount of hardware is O(n).

Note that it costs more than O(log(n)) times to make already fast
memory O(log(n)) times faster.

Note that, with planar layout, there is O(sqrt(n)) factor.

> 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.)

Yup.

> I don't think CAMs are the right solution, as they are very inflexible 

Consider a router on a chip, which is very inflexible, anyway.

A router in a chip is a lot more faster than a router on two chips.

> 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.

TLA addresses are supposed to be accessed so.

> 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.

Large memory is slow. Note also your comment on BGP convergence.

> 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.

Why do you think 8k quite low?

> 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.

Then, how may route, do you think, is enough?

							Masataka Ohta