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.