Subject: Re: [RAM] Re: LISP etc. is not the only path to scalable routing

From: [email-masked] (Noel Chiappa)
Date: Wed, 4 Apr 2007 08:26:20 -0400 (EDT)

> From: Robin Whittle <[email-masked]>

    > I think the result will be simpler, cheaper and less power-hungry than
    > continuing to make larger versions of the current architecture for the
    > next 10 to 20 years. 

I am reliably informed (i.e. by someone who builds them for a living) that
the vast majority (I don't recall the specific number, but it's on the order
of 75% or so) of the gates (and heat/power) in contemporary large routers are
consumed by the forwarding, and in particular things like access controls.
The RIB and/or FIB are not the issue.

    > More CPU and RAM thrust is required for the RIB and BPG traffic
    > .. but CPUs and SRAM/DRAM are commodity devices and are continually
    > getting cheaper and faster - probably outpacing the current growth in
    > the routing table.

No, not really. For one, I am told that it takes a core router (i.e. one with
complete routing table) a significant fraction of an hour to load the current
complete routing table (via BGP) when it restarts; this clearly indicates
poor dynamic response.

And as other people have already mentioned, but this discussion doesn't seem
to be taking on board, the most troubling issue with routing is not the
static situation (i.e. table size when things are quiet), but the dynamic
situation (i.e. how promptly the routing responds, *and stabilizes*, when
there's a topology change).

The following presentation might be helpful in terms of making this point:

  Quaking Tables: The Taiwan Earthquakes and the Internet Routing Table
  http://www.nanog.org/mtg-0702/presentations/underwood.pdf

The summary on the slide labelled "Timeline (2)" is particularly instructive.

    > However, I expect SRAM-based flat routing would lead to greater rates
    > of growth than in recent years.

In light of the above, this statement is particularly problematic.

	Noel

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: Robin Whittle <[email-masked]>
Date: Mon, 09 Apr 2007 22:05:55 +1000

Noel Chiappa wrote:

> I am reliably informed (i.e. by someone who builds them
> for a living) that  the vast majority (I don't recall the
> specific number, but it's on the order of 75% or so) of
> the gates (and heat/power) in contemporary large routers
> are consumed by the forwarding, and in particular things
> like access controls.  The RIB and/or FIB are not the issue.

Routers are called upon to do many things, so there are complex
requirements for classifying packets which are best handled with
TCAM (Ternary Content Addressable Memory) or some other
general-purpose system which can analyze any and all aspects of
various types of packet, of which IPv4 or IPv6 are only two types.

With transit routers, I understand that none of this sophistication
is required for handling the main Internet traffic.  The only task
for the forwarding system of each interface (once the packet checks
OK and its TTL is updated and found to be > 0) is to decide which
interface to forward the packet to, or to drop it.  Multihomed
border routers may need to use all sorts of fancy techniques for
packets addressed to local prefixes, but for outgoing packets
(addressed to the prefixes outside those of the organisation) I
understand that the task is the same as just described.

The problem in routing and addressing is not that there is great
complexity in the handling of Internet traffic - it is the number of
prefixes which need to be considered, and the fact that the traffic
volume requires that this be done very quickly - ideally in a single
operation, rather than iterating through a tree-structured set of rules.

Without a new design such as what I am suggesting, the current
forwarding architectures, which are flexible, expensive and
power-hungry, need to be extended linearly to handle the growing
number of BGP routes.  Broadly speaking, every new advertised prefix
requires a new line in TCAM memory in every DFZ router.

My proposal is to add a RAM chip which handles the analysis of all
the Internet traffic (for a border router, all traffic not addressed
to a local prefix).  This means that there is no need to dedicate a
TCAM line to each BGP prefix.  For each local prefix or any range of
addresses where TCAM etc. analysis was required, the SRAM would
contain a value, such as '1', meaning "Handle this packet with TCAM
etc."  For IPv4, each SRAM location applies to a /24 - and every /24
with the local prefixes could be flagged in this way.  The result
will be that no matter how many global BGP prefixes are advertised,
no TCAM resources are required for outgoing Internet traffic in a
border router, or for the main traffic of a transit router.

The SRAM power consumption, size, cost and complexity is small
compared to the rest of the router, but it means that the router can
handle any number of BGP routes, to /24 granularity.  Extending TCAM
to match the growth in the number of routes would add incrementally
to the already high cost and power consumption of routers.  The SRAM
approach is a small step in cost, complexity, etc. and makes such
extensions to TCAM etc. unnecessary.  Border routers of large ISPs
and AS end-users may well need a lot of TCAM etc.  But that will
only be for local prefixes, and not depend on the number of global
BGP routes.

RW > More CPU and RAM thrust is required for the RIB and BPG traffic
RW > .. but CPUs and SRAM/DRAM are commodity devices and are
RW > continually getting cheaper and faster - probably outpacing
RW > the current growth in the routing table.

> No, not really. For one, I am told that it takes a core router
> (i.e. one with complete routing table) a significant fraction of
> an hour to load the current complete routing table (via BGP)
> when it restarts; this clearly indicates poor dynamic response.

Perhaps the reloading and propagation of changes within BGP could be
optimised by giving priority to shorter prefixes.  If each such
prefix provides, on average, connectivity to a greater number of
actively used IP addresses, then this would enable most of the of
connectivity to be established earlier in the reload cycle.  There
are potential problems in this - for instance it could encourage
people to keep advertising large prefixes to "jump the queue", even
though they don't have many active IP addresses within that prefix.

Since the main proposal currently under consideration is LISP, which
requires some major changes to at least some routers, with a new
protocol, new headers, new centralised database of mapping
information (LISP 1.5+), I think it is worth investigating how BGP
could be enhanced, with faster CPUs and more RAM, to cope with the
increased number of advertised routes my proposal would allow and
encourage.  But the system I am proposing is not intended to cope
with generally frequent changes in BGP routes - no more than is
necessary for coping with outages and the slow development of
network topology.  There is a paper on a proposed new routing
protocol HLP, which might be helpful.  I haven't read it yet:

  http://www.cs.ucl.ac.uk/staff/M.Handley/papers/hlpsigcomm.pdf

> And as other people have already mentioned, but this discussion
> doesn't seem to be taking on board, the most troubling issue
> with routing is not the static situation (i.e. table size when
> things are quiet), but the dynamic situation (i.e. how promptly
> the routing responds, *and stabilizes*, when there's a topology
> change).
>
> The summary on the slide labeled "Timeline (2)" is particularly
> instructive.

Thanks for pointing me to this paper.  I wonder how much of the
longer-term instability is not related to the BGP routing system as
such, but to operators trying to manually optimize their networks
after this major disruption.  Many of the prefixes may have been
/24s, but these, in general cover only a tiny percentage (0.23%) of
advertised space.  For instance, on page 10, which is for a
North-East American power outage in 2003, 70% of the prefixes
affected were /24s.

I am not sure that LISP would produce a better result.  While there
would be a lower proportion of the total routes actually part of the
BGP system, all the LISP encapsulated traffic has to be carried by
routes.  Also, the LISP system, such the ability to communicate with
and maintain a central database of EID to Locator mappings, would be
disrupted by the failure of routes in the BGP system.  So a new
layer of complexity and dependence on centralised resources would
add a new set of problems when there is a major disruption.

  - Robin