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

Re: optimum routing table size

Masataka,

On 22-jun-04, at 21:44, Masataka Ohta wrote:

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.

Hm, is there a reason why CAMs can't be made big enough for this?

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.

Of course. The trouble with CAMs is that they use a lot of power and run very hot. Regular memory searches are more efficient and usually also fast enough.

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

Just the memory; most of the other stuff is O(r) where r = number of routers or number of linecards.

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

Certainly. But as long as the increase in bandwidth is equal or lower than the log of the increase in memory speed, we're ok. Relative to the memory speed requirements to read and write packets at a certain bandwidth, the memory speed requirements for looking in the routing table is probably not a big issue. (Although the former may be done using small amounts of expensive memory while storing a very big routing table in such expensive memory isn't much fun for the people who have to pay the bill.)

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

What do you mean?

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.

Hm, but what problem are we solving here? There are two reasons for having very fast routers: either because you aggregate a lot of traffic, or because you have a lot of traffic going in / coming out of a single place. In the former case speed is only useful if it's affordable: if a 40 Gbps router is 3 times more expensive than 4 10 Gbps routers, ISPs will redesign their networks to use a larger number of smaller routers. In the other case, it may very well be possible to build routers that take advantage of the application scenario. I.e., many packets are going to go in the same direction, so a flow/destination cache based forwarding path would be appropriate here. (Note that this is deadly in an ISP environment where there are many thousands of new flows per second.)

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.

Slow memory is still pretty fast! At 10 Gbps you can do 14.8 million packets per second. With today's RAM it's possible to transfer over 500 MB per second so that compares quite favorably, although this speed is for serial access rather than random access of course.

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?

There are already 135k IPv4 routes out there, but more importantly, 30k AS numbers assigned and 15k in use. So at 8k routes half the ASes that are globally visible in v4 today would have "disappear".

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?

Hard to say. But I really wouldn't want to decide on a fixed number. Rather, I would like the IPv6 internet to "work" with a low number of highly aggregated routes, at least in the core were speed is everything. However, in places where routers can accommodate larger routing tables, it would be beneficial to do controlled deaggregation to take advantage of better optimized paths.

I once did some experimenting and if I remember correctly, 75% of traffic used only 10% of all routes. So it might make sense to build a fast core with only 10% of the global routing table in it which can then take care of this 75% of traffic. The remaining traffic can then be tunneled or routed over an auxilary network. On the other hand, if routers can take a full routing table it wouldn't be smart to go through all this hassle. So we need to be flexible.