North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: Scalability issues in the Internet routing system

  • From: Andre Oppermann
  • Date: Tue Oct 18 12:57:47 2005

Patrick W. Gilmore wrote:
On Oct 18, 2005, at 11:30 AM, Andre Oppermann wrote:
2. The number of longest match prefixes in the forwarding table

This problem scales with the number of prefixes and the number of
packets per second the router has to process under full or expected
load.  The required capacity for a routers forwarding plane is:

 capacity = prefixes * packets / second

This one is much harder to cope with as the number of prefixes and
the link speeds are rising.  Thus the problem is multiplicative to

Here I think Moore's law doesn't cope with the increase in projected
growth in longest prefix match prefixes and link speed.  Doing longest
prefix matches in hardware is relatively complex.  Even more so for
the additional bits in IPv6.  Doing perfect matches in hardware is
much easier though...
You are mistaken in one of your assumptions. The FIB is generated asynchronously to packets being forwarded, and usually not even by the same processor (at least for routers "in the core"). Therefore things like pps / link speed are orthogonal to longest match. (Unless you are claiming the number of new prefixes is related to link speed. But I don't think anyone considers a link which has nothing but BGP updates on it a realistic or useful metric.
I'm not talking about BGP here but the actual forwarding on the line
card or wherever it happens for any particular architecture.  The ASIC
thingie.  It has to do longest-match lookups for every packet that comes
in to figure out the egres interface.