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: Alexei Roudnev
  • Date: Wed Oct 26 01:52:19 2005

Vice versa. DDOS attack will never work by this way, because this router
will (de facto) prioritize
long established streams vs. new and random ones, so it will not notice DDOS
attack at all - just some DDOS packets will be delayed or lost.

You do not need to forward 100% packets on line card rate; forwarding 95%
packets on card rate and have other processing (with possible delays) thru
central CPU can work good enough.

It is all about tricks and optimizations - fast routing is not state of art
and can be optimized by many ways.
For now, it was not necessary; when it became necessary - it will be done in
1/2 year.

----- Original Message ----- 
From: "Rubens Kuhl Jr." <[email protected]>
To: <[email protected]>
Sent: Tuesday, October 25, 2005 9:21 PM
Subject: Re: Scalability issues in the Internet routing system

Assume you have determined that a percentage (20%, 80%, whatever) of
the routing table is really used for a fixed time period. If you
design a forwarding system that can do some packets per second for
those most used routes, all you need to DDoS it is a zombie network
that would send packets to all other destinations... rate-limiting and
dampening would probably come into place, and a new arms race would
start, killing operator's abilities to fast renumber sites or entire
networks and new troubleshooting issues for network operators.

Isn't just simpler to forward at line-rate ? IP look ups are fast
nowadays, due to algorithmic and architecture improvements... even
packet classification (which is n-tuple version of the IP look up
problem) is not that hard anymore. Algorithms can be updated on
software-based routers, and performance gains far exceed Moore's Law
and projected prefix growth rates... and routers that cannot cope with
that can always be changed to handle IGP-only routes and default
gateway to a router that can keep up with full routing.
(actually, hardware-based routers based on limited size CAMs are more
vulnerable to obsolescence by routing table growth than software ones)

Let's celebrate the death of "ip route-cache", not hellraise this fragility.


On 10/24/05, Alexei Roudnev <[email protected]> wrote:
> One question - which percent of routing table  of any particular router is
> REALLY used, say, during 1 week?
> I have a strong impression, that answer wil not be more than 20% even in
> biggerst backbones, and
> will be (more likely) below 1% in the rest of the world. Which makes a
> space for optimization.
> ----- Original Message -----
> From: "Daniel Senie" <[email protected]>
> To: <[email protected]>
> Sent: Tuesday, October 18, 2005 9:50 AM
> Subject: Re: Scalability issues in the Internet routing system
> >
> > At 11:30 AM 10/18/2005, Andre Oppermann wrote:
> >
> > >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
> scalability
> > >issues:
> > >
> > >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.
> >
> > Moore will keep up reasonably with both the CPU needed to keep BGP
> > perking, and with memory requirements for the RIB, as well as other
> > non-data-path functions of routers.
> >
> >
> >
> > >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...
> >
> > Several items regarding FIB lookup:
> >
> > 1) The design of the FIB need not be the same as the RIB. There is
> > plenty of room for creativity in router design in this space.
> > Specifically, the FIB could be dramatically reduced in size via
> > aggregation. The number of egress points (real or virtual) and/or
> > policies within a router is likely FAR smaller than the total number
> > of routes. It's unclear if any significant effort has been put into
> >
> > 2) Nothing says the design of the FIB lookup hardware has to be
> > longest match. Other designs are quite possible. Again, some
> > creativity in design could go a long way. The end result must match
> > that which would be provided by longest-match lookup, but that
> > doesn't mean the ASIC/FPGA or general purpose CPUs on the line card
> > actually have to implement the mechanism in that fashion.
> >
> > 3) Don't discount novel uses of commodity components. There are fast
> > CPU chips available today that may be appropriate to embed on line
> > cards with a bit of firmware, and may be a lot more cost effective
> > and sufficiently fast compared to custom ASICs of a few years ago.
> > The definition of what's hardware and what's software on line cards
> > need not be entirely defined by whether the design is executed
> > entirely by a hardware engineer or a software engineer.
> >
> > Finally, don't discount the value and performance of software-based
> > routers. MPLS was first "sold" as a way to deal with core routers not
> > handling Gigabit links. The idea was to get the edge routers to take
> > over. Present CPU technology, especially with good embedded systems
> > software design, is quite capable of performing the functions needed
> > for edge routers in many circumstances. It may well make sense to
> > consider a mix of router types based on port count and speed at edges
> > and/or chassis routers with line cards that are using general purpose
> > CPUs for forwarding engines instead of ASICs for lower-volume sites.
> > If we actually wind up with the core of most backbones running MPLS
> > after all, well, we've got the technology so use it. Inter-AS routers
> > for backbones, will likely need to continue to be large, power-hungry
> > boxes so that policy can be separately applied on the borders.
> >
> > I should point out that none of this really is about scalability of
> > the routing system of the Internet, it's all about hardware and
> > software design to allow the present system to scale. Looking at
> > completely different and more scalable routing would require finding
> > a better way to do things than the present BGP approach.
> >
> >