size of the routing table is a big deal, especially in IPv6
Tony Li
tony.li at tony.li
Tue Nov 30 04:14:27 UTC 2004
Daniel Senie wrote:
>> There are basically two issues: the forwarding table and BGP
>> processing. Information in the forwarding table needs to be found
>> *really* fast. Fortunately, it's possible to create datastructures
>> where this is possible, to all intends and purposes, regardless of the
>> size of the table. However, memory is a concern here, as you only have
>> a few hundred nanoseconds to look up something in the routing table at
>> 10 Gbps speeds.
>
>
> This is a solvable problem. Hardware lookups are quite sufficient.
> Forwarding bases stored in line cards can be aggregated to the extent
> the data permits. Any router with 10GigE interfaces that's going to care
> about actually filling such pipes will have advanced hardware forwarding
> technology and a price tag to support the development of same.
The bottom line in this discussion is all about cost. Technology can be
had to do many things that are physically possible, but as you get
closer to the limits of the physics, the costs go up. Further, the
marginal costs (i.e., $/packet per second) go up quite rapidly. If the
size of the FIB exceeds Moore's law (and BTW, for memory it's more like
2x every 3 years), then the costs go nuts as you have to scale up from
hardware parts that can't keep up. That also adds complexity.
All of these costs end up factored into the cost of routers, which the
ISPs must in turn factor into the costs of providing service if they are
to stay in business. The problem is that the decisions to advertise a
global prefix must be paid by users around the globe.
If there was a way that these costs were reallocated to the site that
decided to be multihomed, then the economics of the situation would
balance. Imagine paying US $10K/yr to advertise a single prefix and you
would get to a point where people would make some more rational
decisions that didn't pollute the global table.
> Even 10 years ago it was evident the routing table structures chosen by
> different manufacturers had significantly different performance
> characteristics. As there is no single data structure to define the
> storage of this information, it may follow that there is no singular
> formula for the impact of scaling.
In fact, almost all implementations now use some form of radix trie.
> Over the past several years, the CPUs in routers have been considerably
> below the speediest on the market. I suspect there's a fair bit of
> headroom at present between the route processing engines in core routers
> and the fastest CPUs presently offered for sale. As such, I have to
> wonder just how much growth we could handle instantaneously, and still
> stay within the CPU capabilities of today's available processors. Also
> consider that CPU power is far from the only issue. Higher speed memory
> continues to be developed along with higher speed bus architectures.
> System performance is made up of many factors.
Do you really want to keep all routers in the world on the CPU growth
curve? Do you really want the cost of replacing all of that hardware
every time Intel comes out with a new processor? Again, yes, this is
technically possible, but it comes with a cost.
In an ideal world, the cost of running the routing subsystem would be
linear only in the amount of transit bandwidth at each hop.
Unfortunately, the reality is that table growth and prefix flap drive
costs up faster than that and ISPs are being squeezed between costs and
prices. In the long run, these costs will be passed on to the end user,
or all of the ISPs will end up out of business.
> Lookout above! The sky is falling.
Not at all. It will be propped up by router prices. ;-)
>> I'm just saying we should be very conservative in allowing
>> unreversible changes in unscalable aspects of IPv6.
>
>
> I'd sure like to see a lot more thorough analysis than what you provided
> above before reaching that conclusion. History has certainly not sided
> with you. Back in the mid-1990s, we were told routers wouldn't scale, so
> we needed MPLS. While MPLS has found useful roles in the network, it
> wasn't needed as a replacement for IPv4 routing in the core. Several
> companies, including some startups, figured out ways to route packets
> quite quickly.
>
> In the long run, I'd rather provide the ability to offer the services
> needed. This permits the companies looking for those services to
> flourish and help the economies of the world. While there are challenges
> to be addressed, I belive those challenges will be well met by the
> equipment marketplace, and that innovation also will help the economies
> of the world. Artificial restraint does not result in expanded services
> or product innovations. If I had a way to vore on this, I'd vote to let
> the markets work.
Letting the markets work is a fine thought, but there are a few issues
that will not be addressed. The global DFZ routing table is a common
resource, shared and polluted equally by everyone around the world. In
a purely free market world, Adam Smith suggests that everyone will act
in their own best interests and pollute until the environment is no
longer useful. This is frequenly known as the "tragedy of the commons".
In such situations, we normally install other mechanisms to ensure
that pollution is constrained, either economically or through regulation.
If you take a look at the way that the phone network works, for example,
adding a new area code to the NANP is painful because it means that all
of the phone switches have to be updated and so the phone network
routing table is a regulated entity.
In the decentralized world of the Internet, we have a bigger problem in
that we do not have a clear entity that impose the necessary regulatory
pressures and there is no commercial pressure. All we can do is to ask
people to be good Internet citizens and to act locally for the global
good. The challenge, of course, is that this is in almost no one's
immediate best interest.
My preferred solution at this point is for the UN to take over
management of the entire Internet and for them to issue a policy of one
prefix per country. This will have all sorts of nasty downsides for
national providers and folks that care about optimal routing, but it's
the only way that I can see that will allow the Internet to continue to
operate over the long term.
Tony
More information about the NANOG
mailing list