[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