North American Network Operators Group

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

RE: Scalability issues in the Internet routing system - #2

  • From: Susan Hares
  • Date: Tue Oct 18 13:01:56 2005


#2 FIBs doesn't have to be impacted by Moore's law. 

In certain times of routing technology people "cooked" routing tables in
order to solve #2.  The key there is to run through the proposed FIB
Generated by a routing table and cook it for FIB insertion.  You can
summarize (from the viewpoint of a particular router) all the routes
a manageable set of FIB entries.

The issue is how much fluctuation.  10% (actually 8-14% but 10% is
average)  of the Internet (see route-views, etc).  FIB hardware can
allow you to split
the prefix load and the next-hops. So, you load prefixes that fluctuate
only break the prefix-next-hop when they fluctuate.  

.. bottom line.. I don't think we will be limited by Moore's law for
If we utilize existing technology existing in Hw and software
we can change the game on #2.

Sue Hares

PS - My answers tend to be brief - glad to expand in private or public.
     Your choice.

-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf Of
Andre Oppermann
Sent: Tuesday, October 18, 2005 11:31 AM
To: [email protected]
Subject: Scalability issues in the Internet routing system

I guess it's time to have a look at the actual scalability issues we
face in the Internet routing system.  Maybe the area of action becomes
a bit more clear with such an assessment.

In the current Internet routing system we face two distinctive

1. The number of prefixes*paths in the routing table and interdomain
    routing system (BGP)

This problem scales with the number of prefixes and available paths
to a particlar router/network in addition to constant churn in the
reachablility state.  The required capacity for a routers control
plane is:

  capacity = prefix * path * churnfactor / second

I think it is safe, even with projected AS and IP uptake, to assume
Moore's law can cope with this.

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