Scalability issues in the Internet routing system

Tue Oct 18 16:05:18 UTC 2005

On Oct 18, 2005, at 11:30 AM, Andre Oppermann wrote:

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

Especially since this does not have to be done in real time.  BGP  
updates can take many seconds to process without end users thinking  
anything is amiss.

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

-- 
TTFN,
patrick