[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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.