Internet DRAFT - draft-whittle-sram-ip-forwarding

draft-whittle-sram-ip-forwarding






Network Working Group                                         R. Whittle
Internet-Draft                                          First Principles
Intended status: Experimental                             March 30, 2007
Expires: October 1, 2007


   SRAM-based IP Forwarding Eliminates the Need for Route Aggregation
                draft-whittle-sram-ip-forwarding-01.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on October 1, 2007.

Copyright Notice

   Copyright (C) The IETF Trust (2007).














Whittle                  Expires October 1, 2007                [Page 1]

Internet-Draft          SRAM-based IP Forwarding              March 2007


Abstract

   I propose a simple, low-cost, low-power, Static RAM (SRAM) based
   architecture for the Forwarding Information Base (FIB) function of
   transit and border routers in the Default Free Zone (DFZ) of the
   Internet.  This will provide direct hardware forwarding irrespective
   of the size of the "global BGP routing table", within the current
   IPv4 convention of limiting advertised prefixes to no longer than
   /24.  Routers with this or a similar architecture provide the only
   elegant hardware solution to the problem of route disaggregation,
   which is unavoidable due to increasing numbers of ISPs and Autonomous
   System (AS) end-users who need to advertise their prefixes on
   topologically diverse parts of the network, for purposes including
   multihoming and traffic engineering.

   Router hardware limitations with respect to route disaggregation
   could also be eliminated for IPv6, by adding further SRAMs or, on a
   more limited basis, by using spare space in the SRAM which is
   required for IPv4.  Two additional SRAMs and a reallocation of the
   existing 2000::/3 global unicast allocations to a smaller range - for
   instance 2000::/10 - would provide for Provider Independent (PI) /32
   allocations to 4 million ISPs and multihomed end-users.  Each /32
   assignment could be advertised as up to eight /35 prefixes - each of
   which provides 8192 /48 user networks.  A less disruptive alternative
   to reallocating existing IPv6 global unicast addresses would be to
   define a /10 prefix - inside or outside 2000::/3 - for new PI
   assignments to ISPs and AS end-users with the long-term assurance of
   rapid SRAM-based forwarding for prefixes as short as /35, without
   concern for route aggregation or network topology.  It may be
   feasible, for a decade or more, to handle IPv6 without an addition
   SRAM chip.  Unused space in the IPv4 chip (or two chips for larger
   routers) would map 2,097,152 /35 prefixes - for instance to support
   PI assignments of /32 prefixes to 262,144 ISPs and AS end-users.
   This would provide 17 billion /48 prefixes - the standard assignment
   for non-AS end-users.
















Whittle                  Expires October 1, 2007                [Page 2]

Internet-Draft          SRAM-based IP Forwarding              March 2007


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  Summary  . . . . . . . . . . . . . . . . . . . . . . . . . . .  6
   3.  Route Aggregation and FIB Technologies . . . . . . . . . . . .  8
     3.1.  Route aggregation  . . . . . . . . . . . . . . . . . . . .  8
     3.2.  Route disaggregation . . . . . . . . . . . . . . . . . . .  9
     3.3.  The Default Free Zone  . . . . . . . . . . . . . . . . . .  9
     3.4.  Routing Information Base (RIB) . . . . . . . . . . . . . . 10
     3.5.  Forwarding Information Base (FIB)  . . . . . . . . . . . . 11
     3.6.  Forwarding Equivalent Class (FEC)  . . . . . . . . . . . . 11
     3.7.  Linear search list implementation of the FIB . . . . . . . 12
     3.8.  Tree-structured implementation of the FIB  . . . . . . . . 12
     3.9.  TCAM implementation of the FIB . . . . . . . . . . . . . . 13
       3.9.1.  TCAM devices . . . . . . . . . . . . . . . . . . . . . 13
       3.9.2.  TCAM and SRAM produce FEC  . . . . . . . . . . . . . . 15
       3.9.3.  TCAM power consumption and other problems  . . . . . . 15
       3.9.4.  TCAM capacity is driven by route disaggregation  . . . 16
     3.10. Proposed SRAM architecture for the FIB . . . . . . . . . . 17
   4.  The Crisis in Routing and Addressing . . . . . . . . . . . . . 19
     4.1.  Scalability  . . . . . . . . . . . . . . . . . . . . . . . 19
     4.2.  Addressing, Topology and Rekhter's Law . . . . . . . . . . 19
     4.3.  IPv6 - Future Routing Swamp? . . . . . . . . . . . . . . . 20
     4.4.  Costs, Benefits and IETF Policy  . . . . . . . . . . . . . 20
     4.5.  Multihoming is mandatory for ISPs and many users . . . . . 20
     4.6.  Who, Where and extending the TCP/IP protocols  . . . . . . 20
     4.7.  Moore's Law  . . . . . . . . . . . . . . . . . . . . . . . 21
     4.8.  Power consumption and heat dissipation . . . . . . . . . . 21
     4.9.  Incremental changes  . . . . . . . . . . . . . . . . . . . 21
   5.  SRAM-based FIB for IPv4  . . . . . . . . . . . . . . . . . . . 23
     5.1.  The SRAM chip  . . . . . . . . . . . . . . . . . . . . . . 23
     5.2.  Encoding FEC . . . . . . . . . . . . . . . . . . . . . . . 24
     5.3.  IPv4 usage and policy  . . . . . . . . . . . . . . . . . . 26
     5.4.  BGP performance and stability  . . . . . . . . . . . . . . 26
     5.5.  Alternative arrangements for IPv4  . . . . . . . . . . . . 27
   6.  SRAM-based FIB and addressing changes for IPv6 . . . . . . . . 28
     6.1.  Impractical with current global unicast allocations  . . . 28
     6.2.  Reallocating IPv6 global unicast addresses . . . . . . . . 28
     6.3.  Defining a separate IPv6 prefix for SRAM-based
           forwarding . . . . . . . . . . . . . . . . . . . . . . . . 30
     6.4.  Minimal memory space for IPv6  . . . . . . . . . . . . . . 31
       6.4.1.  Using free space in the IPv4 SRAM  . . . . . . . . . . 32
       6.4.2.  Using a smaller SRAM for IPv6  . . . . . . . . . . . . 34
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 36
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 37
   9.  Informative References . . . . . . . . . . . . . . . . . . . . 38
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 40
   Intellectual Property and Copyright Statements . . . . . . . . . . 41



Whittle                  Expires October 1, 2007                [Page 3]

Internet-Draft          SRAM-based IP Forwarding              March 2007


1.  Introduction

   The purpose of this Internet Draft is to argue that future designs of
   high-end routers used in the Internet's Default Free Zone (DFZ) be
   equipped with a Static RAM (SRAM) based hardware architecture to
   achieve single clock cycle Forwarding Information Base (FIB)
   classification of incoming packets.  This architecture would be
   tailored to current global administrative arrangements regarding IPv4
   address management and routing.  An extension to this architecture
   for IPv6 would match a proposed compact reallocation of IPV6 global
   unicast addresses.

   Based on a single 1.4 watt, USD$70 72 Mbit SRAM, this system can
   classify 250M IPv4 packets/sec to be forwarded by one of 14
   interfaces.  By mapping destination address bits 31 to 8 to the SRAM
   address, the correct interface number can be read in 4ns, and can be
   different for each of the 14.6 million /24 prefixes in which the IPv4
   address space could be separately advertised.  This system can be
   extended with a second SRAM to routers with up to 510 interfaces.

   I propose that by carefully coordinating global policies for address
   allocation and BGP prefix advertisement with a new standard of router
   hardware optimised for the Internet's DFZ, that one of the major
   threats to Internet communications can be eliminated.  This is the
   growth in what is often referred to as the "global BGP routing
   table", which is projected to overwhelm the hardware capabilities of
   transit and border routers in the next five or so years.

   Part of the problem of routing table growth is the increased BGP
   traffic and the stability, memory and CPU utilisation problems this
   entails.  The other part of the problem is that the current
   generation of routers will soon be unable to support full line-speed
   packet rates with a sufficiently large number of FIB entries.
   Efforts to constrain routing table growth are likely to fail because
   a growing number of ISPs and end-users can only achieve their
   robustness and performance imperatives by separately advertising
   prefixes for purposes including multihoming and traffic engineering.

   This looming crisis was the subject of a two day IAB Routing and
   Addressing Workshop, held in Amsterdam, Netherlands, in October 2006.
   [I-D.iab-raws-report] [IAB-RAWS-website] .  The participants foresaw
   no solution to the problems.  They were unable to see how routing
   efficiency could be maintained with the growing advertisement of
   prefixes at locations where network topology largely prevents them
   from being aggregated.  Yet the needs of multihomed organisations for
   stable, provider independent (PI) IP addresses with multiple
   topologically diverse upstream connections necessarily results in
   many advertised prefixes not aggregating with neighbouring prefixes,



Whittle                  Expires October 1, 2007                [Page 4]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   except perhaps to distant routers.

   I first review the problems related to routing, including the
   hardware forwarding, routing table management in routers, the BGP
   protocol and how address allocation has to date been constrained by
   the need for route aggregation.  I then describe the scope of the
   proposed upgrade to routers.  I present a single-chip design for IPv4
   for small router - those with 14 or fewer interfaces - and discuss
   its expansion for larger routers.  I then propose an IPv6
   implementation with a particular set of constraints on IPv6 global
   unicast allocation.  Following this is a discussion of some other
   options which might be considered now and for the future.  Finally, I
   suggest a timeline by which the proposed changes to policy might be
   made to give router manufacturers and their customers confidence,
   firstly in the continued routability of the Internet and secondly in
   the capacity of a new generation of routers to handle the demands of
   growing Internet traffic for longer than the current typical 5 year
   lifespan.  In Appendix 1 I discuss some low-level hardware details of
   how the proposed architecture could be implemented with currently
   available SRAMs.































Whittle                  Expires October 1, 2007                [Page 5]

Internet-Draft          SRAM-based IP Forwarding              March 2007


2.  Summary

   In order to gather together the main points of this Internet Draft
   near the beginning, here is a summary of the major points, stripped
   of most of the details and qualifications.

   SRAM table-based FIBs were never considered practical because they
   couldn't handle the full range of router functionality.  As a result,
   it is widely believed that the only way to route packets is with a
   small enough number of rules to fit into TCAM (Ternary Content
   Addressable Memory) or iterative tree-structured FIB systems.  This
   has lead to two decades of apparently absolute belief in the
   requirement for route aggregation - a position perhaps strengthened
   by various unsuccessful attempts to find alternatives by introducing
   new elements into the TCP/IP protocols.

   There are a rapidly growing number of ISPs and end-users who
   absolutely require multihoming (of entire networks, not just
   individual nodes as SHIM6 is intended to provide) and who also
   strongly desire or need some traffic engineering capacity.  These can
   only be provided by this increasing number of users having an
   increasing number of prefixes which they advertise in topologically
   diverse ways - which is completely at odds with the requirement of
   route aggregation.

   The Internet routing system is shared global resource - since all
   users depend upon it, burden it with traffic and pay for it
   indirectly.  So there has been an increasing concern about the future
   of the Internet, manifesting in calls for greater pressure or
   constraints to be placed upon ISPs and end-users to curtail their
   multihoming and prefix-splitting ways.  In the absence of any
   constraints to route disaggregation and assuming that router
   technology does not change in principle, then the capacity of routers
   in the DFZ to handle traffic in the future clearly depends on
   continued purchases of new routers.  An attempt has been made to
   secure IPv6 routability by banning end-users from having Provider
   Independent (PI) addresses.  This places the custodians of the
   Internet (RIRs and whoever acts to protect the interests of operators
   of routers in the DFZ) in opposition with the immediate interests of
   most large ISPs and other AS operators.  Being the Fun-Police in the
   global Internet is a thankless - and probably futile - task.

   Fortunately, modern SRAM chips - which are far beyond what could have
   been imagined when IPv4 or even IPv6 was designed - are a perfect fit
   for a fast, low-power, elegant, simple and easy-to-program hardware-
   based FIB system for existing IPv4 usage in the DFZ.  An SRAM-based
   FIB needs to be an adjunct to existing TCAM etc. architectures,
   rather then replacing them, because these systems are capable of many



Whittle                  Expires October 1, 2007                [Page 6]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   important tasks the SRAM system can't perform.  However, for most or
   all of the traffic of transit routers - and for the upstream traffic
   of border routers - the SRAM-based FIB is sufficient for almost all
   packets.  An SRAM-based system needs to be able to map particular
   prefixes to be handled by the traditional TCAM etc.  FIB
   architecture, for instance to handle packets which match a small
   number of longer prefixes.

   It is difficult or impossible to imagine an easier hardware solution
   than this SRAM-based architecture for simple IP forwarding in the
   DFZ.  It is faster and simpler than MPLS, and requires no changes to
   current IPv4 usage.  The cost of implementing this or a similar
   approach for IPv4 will be far less than not implementing it and
   having to pay much higher prices for routers with power-hungry, over-
   complex TCAM or other types of FIB, scaled up for the larger routing
   tables of the near future.  Nonetheless, border and transit routers
   will typically require some TCAM or other more flexible systems to
   cope with MPLS and/or the few prefixes which are longer than /24.

   By prompting discussion of this architecture now, I hope to hasten
   its arrival for IPv4.  I also suggest that this SRAM FIB architecture
   is the only way IPv6 traffic can be globally routed if and when it
   becomes widely adopted.  So I argue that urgent consideration be
   given to a new, standardised, SRAM-based FIB architecture for routers
   in the DFZ and to new arrangements for IPv6 global unicast addresses.
   Initially, I discuss the re-allocation of IPv6 global unicast
   addresses to suit this architecture, but a less disruptive
   alternative is to define a specific subset of global unicast space
   which future routers will handle with SRAM-based forwarding, and so
   which can be assigned to ISPs and AS end-users without concern about
   route disaggregation.

   Assuming BGP and FIB software can be made stable and responsive with
   much larger numbers of prefixes and updates, I propose that the new
   FIB architecture will enable a much more extensive splitting up of
   the IPv4 address space into freely advertisable and generally small
   PI prefixes.  This would be anathema to route aggregation principles
   which prevail in the absence of an SRAM-based FIB architecture - but
   should enable a much more flexible and efficient use to be made of
   the IPv4 address space, while enabling ISPs and end-users to split
   and advertise their prefixes freely.










Whittle                  Expires October 1, 2007                [Page 7]

Internet-Draft          SRAM-based IP Forwarding              March 2007


3.  Route Aggregation and FIB Technologies

   This section begins with basic principles which will be well
   understood by all readers who are familiar with the crisis.  However,
   this section introduces a new approach to thinking about forwarding
   and therefore routing.  This new approach is the basis of the SRAM
   FIB architecture and of my suggestion for aligning address allocation
   and BGP management policies with a router architecture optimised to
   solve the biggest problem the Internet faces today.

3.1.  Route aggregation

   In the absence of a hardware FIB architecture such as proposed here,
   it seems that all participants - ISPs, major end-users, protocol
   designers, address administrators and router manufacturers - will
   continue to act as if it is impractical to route packets on the
   global Internet unless the forces which lead to 'route
   disaggregation' are strictly controlled.  Full route aggregation
   occurs when each topological branch of the Internet carries only IP
   addresses which are part of a given prefix, and where each other
   branch carries addresses within another non-overlapping prefix.  This
   means that if there were four 'first level' branches from the
   notional 'centre' of the Internet, all the sub-branches of branch A
   would contain only IP addresses within a prefix 'a' and likewise all
   the sub-branches of branch B would contain only IP addresses within a
   second prefix 'b', which is not a subset of prefix 'a'.  Then, a
   router at the junction of these four first-level branches could have
   a very simple routing table.

   This centre router would have four interfaces, one connecting to each
   branch, which I will also name A, B, C and D. (An "Interface" in this
   context means an Ethernet, ADSL, SDH/SONET fibre connection etc.
   This is commonly referred to as a "port" of the router, but I will
   use "interface" to avoid confusion with "ports" in the context of
   TCP, UDP and SCTP.)  When a packet arrives at any of the four
   interfaces, the routing table contains rules by which it should be
   forwarded to one of these four interfaces.  Simply testing the
   packet's destination address against these four rules will lead to it
   either being forwarded to one of the four interfaces, or being
   dropped.  (For simplicity, I am ignoring the fact that the router
   itself must have some IP addresses outside the four prefixes a, b, c
   and d.)  This example of complete route aggregation leads to a tree-
   structured network, without redundant paths to cope with failure of
   links or routers.







Whittle                  Expires October 1, 2007                [Page 8]

Internet-Draft          SRAM-based IP Forwarding              March 2007


3.2.  Route disaggregation

   An example of complete route disaggregation would be a situation in
   which 256 separate prefixes were allocated to users, and these users
   were connected to various branches and sub-branches, with no
   discernable pattern in the addresses of these prefixes with respect
   to their location in the network topology.  In this instance, the
   router at the centre would need as many rules about forwarding as
   there were prefixes, except for the rare occasion in which two
   prefixes with adjacent address ranges could be accessed by the one
   interface.  In that case, a single rule covering the total range of
   the two prefixes would work just as well as a separate rules for
   each.

3.3.  The Default Free Zone

   A router within a network which uses a small proportion of the
   Internet's address space needs only to maintain rules for the
   prefixes in that address space, with one final rule as the default to
   be followed when a packet's destination address does not match any of
   the other rules.  The default rule forwards packets to whichever
   interface leads towards the "rest of the Internet".  For instance, a
   border router which has a single connection to an ISP on interface D,
   has a series of rules for each of the network's prefixes, followed by
   the final default rule: to direct all non-matching packet to the ISP,
   where they will be routed to their destinations on the rest of the
   Internet.  In internal router will have its default rule to forward
   packets to whichever interface is the best route to the border
   router.

   There are two primary types of router which are considered to be in
   the "Default Free Zone", by virtue of them not being able to rely on
   a single default rule to forward all the packets which do not match
   any one of a relatively short list of rules.  The first type is a
   border router with two links to two or more separate ISPs (or peering
   points, or routers of other systems) where both links carry outgoing
   packets to the rest of the Internet.  Such a border router needs
   rules for every globally advertised BGP prefix, because the best path
   for some prefixes will be to one link and the best for the others
   will be to another.  The second type of router in the DFZ is a
   "transit router", which is not serving a local network, but connects
   to two or more other routers handling general Internet traffic.  As
   with the multihomed (two links to ISPs) border router, the transit
   router needs to participate in the global BGP routing system and
   maintain separate rules for which interface to forward packets to,
   for each of the tens of thousands of advertised prefixes.

   The proposed SRAM-based FIB architecture is only required for routers



Whittle                  Expires October 1, 2007                [Page 9]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   in the DFZ.  Internal routers and those with a single outgoing link
   do not need an RIB and FIB with separate entries for each advertised
   BGP prefix, so conventional router architectures are perfectly
   adequate.  Nonetheless, it is possible that economies of scale and
   the desire for flexibility may result in the SRAM-based approach
   becoming standard in all high-end routers, including those which are
   not initially deployed in the DFZ.

3.4.  Routing Information Base (RIB)

   The Routing Information Base (RIB) is the body of data maintained by
   each router which contains these rules.  The RIB's rules may be
   manually configured, or some mixture of manual and automatically
   generated rules.  For our discussion of the problems faced by routers
   in the Internet's DFZ, most of the rules are generated automatically
   by the router's software running a Border Gateway Protocol (BGP)
   agent which communicates with other similar routers, so that each
   router can decide the best interface to forward packets to, depending
   on their destination address.  In this Internet Draft, we are only
   concerned with the external BGP (eBGP) interaction between transit
   routers and the border routers of Autonomous Systems (ASes).  The
   border routers of some ASes also communicate via an internal BGP
   (iBGP) system.

   For the purpose of this discussion, the action of "forwarding" refers
   to directing a packet to one of the interfaces, to dropping it, or
   perhaps to subjecting it to some other processing.  For the main body
   of payload traffic (as distinct from administrative traffic) the
   action of forwarding must be performed very quickly.  Because the
   major problem faced by transit and border routers is the task of
   simply forwarding packets, rather than doing anything more complex
   with them such as queuing them in the output interface, I will
   consider "forwarding" to be simply making the first, and usually the
   only, decision regarding the packet: which interface to send it to,
   if any.

   Typically, the RIB is processed by software in the router to generate
   a simpler body of data more suitable for rapid classification of
   packets.  This body of is known as the 'Forwarding Information Base'
   (FIB), but I will also use this term to refer to the hardware and
   software which processes the packets according to this body of data.

   Routers may use some combination of software, specialised hardware
   and software, or purely hardware (without any conventional CPU or
   software) to classify the packets regarding which interface they
   should be forwarded to.  Originally, routers had a central design
   with relatively "dumb" interfaces.  All high-end routers now place an
   FIB system on each interface.  This is for several reasons.  Firstly,



Whittle                  Expires October 1, 2007               [Page 10]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   the total data rate of the router exceeds that of any single FIB.
   Secondly, funnelling packets to a central point when some of them
   might be sent back to the ingress interface is inefficient.  Thirdly,
   local processing in the interface enables the interface to decide,
   without any per-packet central involvement, which interface to send
   it to via the router's "backplane" or "switching fabric" - a fast,
   any-to-any interconnect between all the interfaces.

   The RIB is traditionally structured as a list of prefixes, each of
   which has an associated body of data.  One entry in the RIB may refer
   to an entire /8 prefix - which in IPv4 covers 16,777,216 IP
   addresses.  Another may cover a /24 or longer prefix, covering 256 or
   less IPv4 addresses.  This organisation reflects the way routing
   information is structured in BGP and in most other contexts.

   The RIB of a DFZ router is used for more than simply generating an
   FIB.  Firstly, the router uses the RIB to store some of the
   information it receives from its peers - other transit and border
   routers which participate in the global BGP system.  Secondly, the
   RIB is used to generate BGP messages sent to these peers.  Often, the
   RIB is processed to generate a similar, simplified and separate body
   of data on which the BGP outgoing messages are based.

3.5.  Forwarding Information Base (FIB)

   Traditionally, the FIB is structured similarly to the RIB - as a set
   of rules, each applying to a particular prefix.  Where two rules A
   and B refer to prefixes a and b respectively, and where prefix b is a
   subnet of a, then the FIB must be structured so that packets whose
   destination address is within prefix b are subject to rule B rather
   than rule A. Rule A is applied to all packets within a but not within
   b.  This algorithm of giving precedence to the routing rule with the
   "most specific" address match is known as "longest prefix match".
   For instance, rule A is for a subnet with addresses such as "0110
   01xx" (where 'x' means the address bits can be 0 or 1).  This is a
   prefix fixing 6 bits.  Rule B is for addresses in the range "0110
   010x" - a 7 bit long prefix.

3.6.  Forwarding Equivalent Class (FEC)

   For simplicity, in what follows, I will use the term "FEC" to refer
   to a numeric value which the router interface needs to compute
   rapidly for each incoming packet.  This value controls whether the
   packet will be dropped, forwarded out the same interface, forwarded
   to another interface or subjected to further analysis and processing.
   In practice there may be other aspects of FEC which can be derived
   from other attributes of the packet, such as the DiffServ Code Points
   which are used to select which output queue the packet is sent to on



Whittle                  Expires October 1, 2007               [Page 11]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   the output interface.  However, for this discussion, I will consider
   "FEC" to be simply a binary number created by the input interface's
   FIB, based solely on the packet's destination address.

3.7.  Linear search list implementation of the FIB

   The simplest software approach to forwarding involves an iterative,
   linear search through the FIB's list of rules, comparing each rule
   with the packet's destination address.  In this approach, the FIB's
   rules are either the same as those in the RIB or are a somewhat
   simplified version, such as by combining two rules with the same
   forwarding outcome (the same drop, process or deliver to a particular
   interface information) which have adjacent and aggregatable address
   ranges.  For instance, if the same rule applies to "0010 000x" and
   "0010 001x" then this can be replaced by a single rule for "0010
   00xx".  Likewise "0010 001x" and "0010 0xxx" can be combined into
   "0010 0xxx" if their rules have the same forwarding outcome.

   While the order of rules in the RIB may not be important, in the FIB
   the order must follow the "longest prefix match" principle.  Any
   longer prefix must appears before the shorter prefix which
   encompasses its address range.  For instance Rule B in the previous
   example, with its longer prefix "b", must be found by the search
   algorithm before it finds rule A.

   Each rule contains a number which directs the router to forward the
   packet to a particular interface, to drop it, or to subject it to
   further processing.  There is no other absolute requirement about the
   ordering of the rules, but shorter processing times would be achieved
   by placing those rules at the front of the FIB which match the
   largest proportion of packets in the current traffic environment.
   This linear search algorithm could also be implemented in hardware,
   or by a micro-programmed processor specifically designed for the
   task.

3.8.  Tree-structured implementation of the FIB

   Where the number of rules exceeds a few dozen, it would typically be
   faster to find the correct rule for each packet by structuring the
   rules in a tree-like manner in memory, so software or dedicated
   hardware could locate the correct rule in a limited number of
   iterated cycles.  For instance, an algorithm might first select one
   of two first level branches in the FIB depending on the state of bit
   31 of an IPv4 address.  Then it selects between two second level
   branches from whichever first level branch it chose in the first
   cycle.  This process continues, potentially for 32 cycles, until it
   finds a leaf - a node in the tree which is the longest prefix match
   for this address, and so has no further branches leading from it.



Whittle                  Expires October 1, 2007               [Page 12]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   This is an onerous task with IPv4 in the DFZ, because a significant
   number of packets need to be matched to prefixes 15 to 24 bits long.
   The average length of longest prefixes matched would depend on the
   specific location of the router and the type of traffic.  Processing
   speed is boosted firstly by switching initially on the most
   significant 8 bits, since all routing rules have prefixes at least
   this long, and by more sophisticated approaches to the tree
   structure.  For instance some chains of such a tree have many levels
   and no branches, which increases the time to reach the end node and
   the storage requirements.  A "Patricia trie" is an improvement on the
   standard binary radix tree which solves this problem.  Detailed
   explanations of routing and forwarding approaches can be found at
   Pankaj Gupta's site [Gupta] - in particular Chapter 2 of his thesis.
   Trees can also be made with more than two branches per node.  For
   instance a 16-way branch handles 4 address bits per node traversal
   operation, potentially reducing the search time, but this raises
   problems with memory storage efficiency.

3.9.  TCAM implementation of the FIB

   In high-end routers, the most common technique for classifying
   incoming packets is dedicated hardware based on Ternary Content
   Addressable Memory (TCAM) chips.  "Ternary" means that each
   functional cell of the TCAM has three states: "match 0", "match 1"
   and "don't care".  TCAM is always used in routers, rather than the
   simple "CAM", in which each functional cell has only two states:
   "match 0" and "match 1".  Nonetheless, the term "TCAM" is sometimes
   loosely shortened to "CAM" in discussions about routers.  Ethernet
   switches need to match every bit of a 48 bit MAC address, so they use
   true CAM (Content Addressable Memory), but routers need to be more
   flexible, and be able to ignore the state of many bits.

   While TCAM and some highly optimised iterative techniques are the
   fastest approaches for the very broad general purpose nature of
   router functionality, they do not scale easily - or perhaps at all -
   to handling millions of prefixes, each with a potentially different
   "Forwarding Equivalent Class" (FEC).

3.9.1.  TCAM devices

   The large, fast, TCAM chips needed for high-end routers are exotic,
   complex, power-hungry devices.  Data is written into the memory cells
   (usually Static RAM flip-flops) by the CPU of the router or of the
   interface card on which the FIB resides.  There is more to a complete
   FIB than one or more TCAMS, but in this explanation we will consider
   the use of a single TCAM and a second, conventional, SRAM chip,
   solely for determining the FEC of each incoming packet.  I will
   describe a TCAM and its associated SRAM in some detail, because this



Whittle                  Expires October 1, 2007               [Page 13]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   technology is the most likely one to be scaled up in order to cope
   with the routing table explosion, unless a direct SRAM-based
   technique such as I am proposing is employed.

   I will describe a simple, imaginary, TCAM with 32 addresses and 8
   data bits.  Each "cell" consists of two flip-flops, and all the cells
   in our example have previously been written by the router's CPU to
   implement the currently required rules for classifying packets to
   create the proper FEC for each one.  The TCAM is the first and most
   demanding part of the process.  This example FIB can contain up to 32
   rules, and in this example will be working from an 8 bit destination
   address of a packet.  The 8 "data" input signals enter at the top of
   the device, and each one is split into two lines which run vertically
   to the bottom edge.  For instance, for bit 0, there is a true bit 0
   line and an inverted bit 0 line.  So there are 16 lines which may
   change state every time some new "data" is presented to the chip.
   The 32 "addresses" are implemented as 32 horizontal rows.  Each
   intersection of an "address" row and a pair of "data" lines contains
   two memory cells, as just described, and two comparators.  The
   outputs of all the 16 comparators in an "address" row can pull down a
   horizontal line I will call the "match" line for this address.

   Each pair of flip-flops and their associated comparators implements
   the ternary comparison function.  When both flip-flops are low, the
   cell does not care about the state of the true and inverted data
   lines which pass downwards across it.  When the left flip flop is set
   to "1", its comparator will pull down the match line if the true data
   line is low.  Similarly, when the right flip flop is set to "1", its
   comparator will pull down the match line if the inverted data line is
   low.  Further details can be found in [Taylor-Spitznagel], where
   power dissipation figures of 20 to 30 watts are quoted for 2002
   technology TCAMs of 18Mbit capacity.

   In our example, the first address row at the top - address 31 - has
   its cells set to match the following pattern of address bits, where
   "x" means "don't care": "0110 1xxx".  (In these examples, the most
   significant bit is on the left.)  Address 30 is set to match "0001
   111x" address 29 is set to match "100x xxxx".  It can easily be seen
   how a TCAM can, in a single clock cycle, compare the address bits of
   an incoming packet, which are driven to the "data" pins of the TCAM,
   with the rules which have previously been stored inside the device.

   Along the right edge of the example device, the 32 match lines enter
   a priority encoder, which is a simple arrangement of logic gates so
   that a 5 bit binary number emerges from output pins, corresponding to
   the highest numbered match line which remains high.  (The term "pin"
   refers to physical electrical connections of an integrated circuit,
   despite most large chips now being in packages which use solder balls



Whittle                  Expires October 1, 2007               [Page 14]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   rather than pins.)

   At the start of the cycle, all match lines and all the true and
   inverted "data" lines are pulled high.  When the true and inverted
   data lines are set according to the packet's address, none, one or
   multiple match lines will remain high.  In this example, the packet's
   address bits are "1000 1101" so the match line of address row 29
   remains high.  Other lower numbered match lines may be high as well,
   but the priority encoder ignores them.  The TCAM chip produces an
   output (on its five "address" pins) of the binary number for "29".

   There is some specialised terminology for TCAMs.  They are sometimes
   marketed as "network search engines".  When performing their
   comparison function, the input, to the "data" pins in this example,
   is known as the "key" and the output is called the "address".  A
   recent paper describing TCAM usage in IP packet classification, with
   a particular emphasis on optimising the speed of rewriting the cells
   when a routing withdrawal or addition occurs, is: Gesan Wang and
   Nian-Feng Tzeng 2006 [Wang-Tzeng].

3.9.2.  TCAM and SRAM produce FEC

   In the example, the TCAM output 29 does not tell the router which
   interface to send the packet to.  This information is stored in a
   standard SRAM chip, which has its address inputs driven by the output
   of the TCAM.  The router's software has previously written, to each
   location in the SRAM, the correct FEC data for each rule in the TCAM.

   More complex processing can be achieved by extending this
   architecture to involve analysing a packet with one set of TCAM
   rules, with the data read out from the SRAM determining whether the
   packet will be matched against further rules, or whether the result
   of the previous operation contains sufficient information to
   determine the packet's fate.  In this way, complex multi-cycle
   programs of analysis can be performed on packets.

3.9.3.  TCAM power consumption and other problems

   A TCAM is a sophisticated, flexible, massively parallel comparison
   system.  TCAM chips are relatively exotic devices - since they are
   primarily used only in routers and networking equipment.  Some
   reasons for their high power consumption include that each "bit"
   really consisting of two flip-flops and two comparators, and that in
   every comparison cycle, all the match lines are precharged high,
   after which most or all of them will be pulled low.

   TCAM's power consumption and limited capacity are significant
   problems.  The devices are often partitioned so only certain sections



Whittle                  Expires October 1, 2007               [Page 15]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   are active for a particular "search" cycle.  Modern devices, such as
   the Renesas R8A20211BG operate at high rates, such as 133M "searches"
   per second for a 72 bit key with 262144 address rows.  No power
   consumption figures are available for this device [Renesas].  Its
   sample cost in 2005 was about USD$175.

   Another major problem is that updates to the routing table often
   require significant rewriting of the contents of the TCAM and the
   SRAM, since rules may be added and deleted.  The order of rules is
   crucial, since the order determines which of multiple true "match"
   lines will be recognised by the priority encoder.  When a change to
   the RIB occurs, implementing the required change in the FIB (in this
   case consisting of the data in the TCAM and the SRAM) may involve
   many rules being rewritten to other locations in order to fit the
   newly structured list of rules into the available space.  While the
   data is being rewritten, the FIB cannot be used to classify packets,
   so packets may be dropped.  Devavrat Shah and Pankaj Gupta, in 2001,
   considered optimisations for the way data is structured to improve
   upon occasional worst-case rewrites involving 64k locations, at 50MHz
   cycle time, which would hold up packet processing for 1.2ms
   [Shah-Gupta].  The SRAM would require the same demanding pattern of
   writes by the router's CPU when large numbers of rules are moved in
   the TCAM.

3.9.4.  TCAM capacity is driven by route disaggregation

   TCAMs are a necessary part of most router architectures.  However,
   when an ISP or end-user adds another prefix to the global routing
   table and when (as is often the case) the prefix is advertised in a
   location such that from the point of view of a subset of transit and
   border routers, packets addressed to this prefix must be forwarded to
   a different interface from those addressed to the neighbouring
   prefixes, then TCAM-based routers in this subset will need to use
   another address line of their TCAMs.

   This adds directly to the costs of thousands of routers, and directly
   contributes to their energy consumption.  TCAM memory is often
   difficult or impossible to expand.  In order to ensure routers can
   handle whatever expansion of the "global BGP routing table" that may
   occur in their 5 or more year projected service life, network
   operators typically need to pay up front for this expensive hardware
   in every interface, and the router software to manage it.

   If no single TCAM chip can store the required number of rules, they
   may be used sequentially or in parallel arrays.  Both these
   approaches slow down processing and add power consumption.





Whittle                  Expires October 1, 2007               [Page 16]

Internet-Draft          SRAM-based IP Forwarding              March 2007


3.10.  Proposed SRAM architecture for the FIB

   I propose simple implementation of the FIB, which involves the
   router's CPU processing the RIB to create a 4 to 9 bit word
   (depending on the number of interfaces the router has) for the FEC of
   every prefix of a certain size.  For IPv4, this is the /24 prefix.
   2^24 of these must be calculated and stored in one or more SRAM
   chips.  Then, destination address bits 31 to 24 are used to drive the
   address pins of the SRAM, in read mode, with the output being the FEC
   for this packet.  There are no complex algorithms for ordering rules,
   or requirements to move other rules as new rules are added.  The most
   common update, which is either the withdrawal of a /24 or a change in
   its FEC, involves a single write operation.  The hardware multiplexes
   access to the address lines of the SRAM so that CPU write cycles can
   be interspersed with read cycles for packet classification.  Appendix
   1 contains further low level details of how this might be done.

   Here I describe a practical approach to implementing this
   architecture with currently available memory chips.  There may be
   other approaches, including extending existing router architectures
   with additional SRAM to achieve the same functionality.  In practice,
   this architectural block would be part of the larger FIB function,
   with packets first being handled by the SRAM system.  Address ranges
   for packets which require further processing by TCAM or other
   techniques will have the SRAM data for the /24 prefixes in each range
   set to a values which selects this further processing.

   The SRAM would be driven by hard-wired, FPGA or micro-coded systems
   which firstly determine the nature of the packet, such as IPv4, IPv6
   or MPLS.  Although it would be possible to map the 1M MPLS label
   space into unused parts of an SRAM which is used for IPv4, MPLS
   requires other functions and data storage, including the storage of a
   20 bit new label value to write to the packet, and possibly
   information about how to prioritise it in one of the potentially
   multiple output queues in the interface which sends it to the next
   hop.  In this section, I will consider only IPv4 packets.

   Certain conditions must be met for the system to be effective.
   Firstly, the vast majority of packets - essentially all user traffic
   packets - must have their FEC defined in a single cycle of this SRAM-
   based FIB.  Secondly, the system must be able to cope reliably, but
   not necessarily as quickly, with the smaller number of packets which
   need to be matched to prefixes longer than /24.

   The third requirement is a fast, simple method of updating the FIB
   when the RIB changes.  The SRAM design provides this, unless a very
   short prefix is changed, which would require writing thousands or
   hundreds of thousands of locations.  Fortunately, while such an



Whittle                  Expires October 1, 2007               [Page 17]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   extensive rewrite of the locations covered by this prefix was taking
   place, it could be interspersed with accesses for packet
   classification.  During this time, some of the /24 prefixes within
   the larger prefix being updated would have the old FEC value and
   others would have the new.  This would result in some packets being
   sent to the wrong interface, but it is the interface they were
   previously sent to.  During the rewrite, there is no impact on
   packets outside the range being changed.  Changing an entire /8 would
   take 64k cycles, which might take a few milliseconds.  Worst-case
   TCAM updates may take this long, but the TCAM generally cannot be
   used while its contents are being rewritten.

   In terms of simplicity, low power consumption and compact size, the
   SRAM approach could only be bettered, perhaps, by use of less
   expensive DRAM.  However, DRAM cycle times are much longer than
   SRAMs, which can typically produce their read results in a nanosecond
   or so, and complete a read or write cycle in 4 nanoseconds.  Whereas
   TCAMs and iterative search approaches are complex, in need of many
   optimisations and so are the subject of much academic research, there
   is little to write about using a simple SRAM chip except that it is a
   straightforward engineering solution which is easy to understand and
   program.

   The greatest single benefit of the SRAM approach is that its
   performance is optimal no matter how many rules are contained in the
   RIB.  This includes the worst-case situation of complete route
   disaggregation, in which packets addressed to every successive /24
   are forwarded to a different interface.  Implementing this
   architecture in all the Internet's DFZ routers would remove all
   hardware-based pressure to achieve route aggregation.

   In sections below discuss specific hardware and BGP policy proposals
   for both IPv4 and IPv6.


















Whittle                  Expires October 1, 2007               [Page 18]

Internet-Draft          SRAM-based IP Forwarding              March 2007


4.  The Crisis in Routing and Addressing

   The report and presentations from the October 2006 IAB Routing and
   Addressing Workshop in October 2006 is the best reference for the
   problem I am addressing [I-D.iab-raws-report] [IAB-RAWS-website].
   Below, I quote some of the key statements of the report and
   presentations.

4.1.  Scalability

   From the report: "While several scalability features of the routing
   and addressing systems were discussed, most related to the size of
   the DFZ routing table (frequently referred to as the Routing
   Information Base, or RIB) and its implications.  Those implications
   included (but were not limited to) the sizes of the DFZ RIB and FIB
   (the Forwarding Information Base), the cost of recomputing the FIB,
   concerns about the BGP convergence times in the presence of growing
   RIB and FIB sizes, and the costs and power (and hence heat
   dissipation) properties of the hardware needed to route traffic in
   the core of the Internet."

4.2.  Addressing, Topology and Rekhter's Law

   Yakov Rekhter's "Rekhter's Law" was cited as one of the fundamental
   assumptions underlying the scalability of routing systems:
   "Addressing can follow topology or topology can follow addressing.
   Choose one."  I can find no mention of new hardware FIB designs which
   are not impacted by the route disaggregation which "Rekhter's Law" is
   intended to prevent.  However, this assumption of the apparent
   futility of hoping for such an approach is noted in the following
   paragraph:

   "A refinement to Rekhter's Law, then, is that for a routing system to
   scale, the locator part of IP address must be assigned in such a way
   that it is congruent with the Internet's topology.  However, as
   identifiers are typically assigned based upon organizational (not
   topological) structure and have stability as a desirable property, a
   'natural incongruence' arises.  As a result, it is difficult (if not
   impossible) to make a single number space serve both purposes
   efficiently.  Of course this conclusion assumes, as mentioned above,
   that no effective 'non-topological routing system' exists."

   The purpose of this Internet Draft is to suggest that a simple
   hardware forwarding system does exist which is not impacted by
   address assignments which have no correlation with topology.






Whittle                  Expires October 1, 2007               [Page 19]

Internet-Draft          SRAM-based IP Forwarding              March 2007


4.3.  IPv6 - Future Routing Swamp?

   Regarding IPv6: "The primary issue with IPv6 deployment was that, in
   the absence of a scalable routing strategy, IPv6 has the potential to
   exacerbate today's problems simply by the virtue of its much larger
   address space." and "Thus the opportunity exists to create a "swamp"
   (unaggregatable address space) that can be many orders of magnitude
   larger than what we faced with IPv4."

4.4.  Costs, Benefits and IETF Policy

   Regarding the impact of activities such as multihoming by ISPs and
   end-users on the costs of purchasing and running transit and border
   routers, "the workshop participants felt that the costs and benefits
   in today's routing system are misaligned.  While the IETF does not
   typically consider the "business model" impacts various technology
   choices directly, many participants felt that perhaps the time has
   come to review that philosophy."  The high cost of renumbering an
   end-user network was acknowledged together with the observation that
   "no strong disincentive exists to discourage the increasing use of
   Provider Independent address space".

4.5.  Multihoming is mandatory for ISPs and many users

   Multihoming for end-user organisations was recognised as being "in
   some circumstances, mandatory due to contract or law."  Uses of
   Traffic Engineering were recognised as being mandatory - for goals
   including load balancing, low-cost path selection, maintaining
   peering agreements and for ensuring that packets must follow, or not
   follow, certain paths.  There is also a statement to the effect that
   ARIN has been allocating Provider Independent IPv6 /48 prefixes for
   end users, but my understanding of the policy statements at the ARIN
   site is that this is only for "infrastructure providers", such as
   Internet exchanges.

4.6.  Who, Where and extending the TCP/IP protocols

   Section 2.2 of the report discusses how the two-layer domain name /
   IP address split has become overloaded with functions, since the IP
   address which rightfully specifies "where" (in contrast to the DNS
   text name's "who") is no longer a direct function of "where" the node
   is within the network's topology.  There is a review of various
   approaches to inserting a third layer into IP protocols, where a
   middle level, reasonably stable "locator" is mapped in real-time to
   one or more relatively unstable "identifiers", enabling higher level
   protocols to function as usual while the physical location of nodes
   changes.




Whittle                  Expires October 1, 2007               [Page 20]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   The first part of David Wheeler's aphorism is cited: "There is no
   problem in computer science that cannot be solved by an extra level
   of indirection,", but not the second: "but that usually will create
   another problem."

4.7.  Moore's Law

   There was considerable debate about the ability of Moore's Law to
   keep up with the growth in the size of the global BGP routing table.
   Concerns were raised about the chips used in high-end routers being
   low volume devices with very high design costs, which only benefited
   marginally from the spectacular leading edge of semiconductor
   development which is focused on mass market CPUs and memory.

4.8.  Power consumption and heat dissipation

   The report's paragraphs on heating and power appear in full below:

   "Transistors consume power both when idle ("leakage current") and
   when switching.  The smaller the transistors, the larger the leakage
   current.  The overall power consumption is not linear with the
   density increase.  Thus, as the need for more powerful routers
   increases, cooling technology grows more taxed.  At present, the
   existing air cooling system is starting to be a limiting factor for
   scaling high-performance routers.

   "A key metric for system evaluation is now the unit of forwarding
   bandwidth per Watt-- [(Mb/s)/W].  About 60% of the power goes to the
   forwarding engine circuits, with the rest divided between the
   memories, route processors, and interconnect.  Using parallelization
   to achieve higher bandwidths can aggravate the situation, due to
   increased power and cooling demands.

   "[Editor's note: Many in the community have commented that heat power
   utilization and the attendant heat dissipation, along with size
   limitations of fabrication processes are the current limiting
   factors.]"

   I note that a 2006 report [Gartner] states "Gartner roughly estimates
   that during operation, today's servers and PCs account for about
   0.75% of global carbon dioxide emissions (based on direct power
   consumption, not including cooling)."

4.9.  Incremental changes

   In Section 8, Criteria for Solution Development, the report states:
   "In the routing system itself, the solutions must allow incremental
   changes from the current operational Internet.  The solutions should



Whittle                  Expires October 1, 2007               [Page 21]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   be backward compatible with the routing protocols in use today,
   including BGP, OSPF, IS-IS, and others, possibly with incremental
   enhancements.  The data path should support IPv4 and IPv6."

   I believe this SRAM-based FIB proposal for IPv4 meets all these
   criteria.  For IPv6, some changes will be necessary.  I initially
   discuss a complete reallocation of current global unicast space into
   a smaller prefix.  However a more attractive alternative may be to
   define a smaller prefix for SRAM-based forwarding, which still has a
   vast addressing capacity, either inside or outside the currently
   allocated 2000::/3 prefix.  Provider Independent use of addresses in
   that prefix, and of all IPv4 addresses, could then proceed as long as
   the longest advertised prefixes remained within the defined limits:
   /24 for IP4 and perhaps /35 for IPv6.

   For both IPv4 and IPv6, the success of these proposals depends on all
   transit routers and multihomed border routers being able to handle
   the increased number of BGP advertised routes (without any
   requirement for route aggregation) which the proposal enables and
   encourages.  I expect this would occur over three to five years, as
   part of the natural replacement cycle of routers, provided that a new
   standard for routers can be devised, based on stable, agreed,
   administrative limits to the bits which vary in the inter-AS user
   traffic of the Internet.  The creation of such a standard, the
   growing deployment of SRAM-FIB-equipped routers and the freedom from
   constraints regarding route aggregation would lead to an increased
   rate of growth in the total number of advertised prefixes, above that
   which would occur without these proposals.  This would hasten the
   pressure to deploy new routers, as older ones with conventional FIB
   technologies reach the limits of their capacity.  These proposals are
   disruptive in the sense that they would accelerate growth in the
   number of advertised routes, requiring earlier replacement of non-
   SRAM-equipped routers - but this is still an incremental change.

   I expect the SRAM IPv4 FIB approach would naturally be implemented by
   router manufacturers without any work prompted by this Internet
   Draft.  My aim is to bring this development forward for both IPv4 and
   IPv6 in a standardised manner, by prompting discussion and hopefully
   agreement on the BGP and address assignment policies for both
   protocols.  I envisage the IPv6 solution involving either a compact
   reallocation of the global unicast address space before it is more
   widely used, or by the long-term growth of most IPv6 traffic
   occurring between addresses within a standardised prefix for which
   the next generation of routers will perform SRAM-based forwarding.







Whittle                  Expires October 1, 2007               [Page 22]

Internet-Draft          SRAM-based IP Forwarding              March 2007


5.  SRAM-based FIB for IPv4

   In this section, I propose a hardware design an IPv4 FIB function,
   based on a specific already mass-produced Static RAM (SRAM) device,
   the 4ns cycle time, 8M x 9 bit, Samsung K7R640982M [Samsung SRAM].
   While I will not discuss all technical details of this device, I will
   provide enough to enable readers to envisage the physical
   implementation of the system I am proposing.  There are a number of
   other devices, including those of other manufacturers, which could
   provide the same functions, but this particular device is currently
   the best for explaining the design.  My aim is to show that this
   solution is practical and elegant.  By the time the system is built
   into routers, there are likely to be further choices in how to
   implement it.

5.1.  The SRAM chip

   The K7R640982M is part of a "Quad Data Rate II" (QDRII) family of
   devices.  The electrical and physical specifications for this family
   are standardised by the Quad Data Rate Consortium [QDR Consortium],
   of which Samsung is a member.  None of the other members - Cypress,
   Renesas, IDT and NEC - currently make a device with the K7R640982M's
   features: 72 megabits with 9 bit wide data inputs and outputs.  Other
   family members, such as with 18 bit inputs and outputs, could be used
   for the FIB system, but the 9 bit device is probably most convenient.

   The SRAM measures 17 x 15 x 1.3mm when soldered flat to the printed
   circuit boards via its 165 solder balls.  The price I was quoted by
   Samsung, in February 2007, for sample quantities was USD$70.  The
   maximum power dissipation is 1.45 watts, but actual power dissipation
   is likely to be less, since even with a 40Gbps stream of packets, the
   device will not be running at its maximum 250 million memory cycles
   per second.  A single such device holds a 4 bit FEC value for every
   unique IPv4 /24 prefix.

   The device has 9 data in and 9 data out pins.  This separation of
   input and output pins is convenient since the router's CPU only needs
   to write (except for memory test purposes) and the FIB function only
   needs to read.  I will present the device as if it has 23 address
   pins, but in fact it has 22, corresponding to A22 through A1.  A0 is
   generated internally, in each cycle, and two 9 bit bytes are read on
   every 4ns read cycle.  I will not discuss the straightforward low-
   level arrangements for using this 9 bit plus 9 bit read or write
   memory cycle and will portray it as a simple "8M x 9 bit" SRAM chip,
   with 23 address lines, reading or writing 9 bits of data.






Whittle                  Expires October 1, 2007               [Page 23]

Internet-Draft          SRAM-based IP Forwarding              March 2007


5.2.  Encoding FEC

   The address pins of the SRAM system need to be driven by either the
   FIB hardware - by bits 32 through 24 of an IPv4 packet's destination
   address - or by an address presented by the router's CPU.  At first,
   I will describe the FIB read cycle for a router with up to 14
   interfaces.  The FIB function is implemented identically on every
   interface, with the same data being written to each SRAM, assuming
   there is no need for different interfaces to forward IPv4 packets
   differently.  Relatively straightforward hardware detects the IPv4
   packet, switches its address bits to the SRAM, collects either the
   low 4 bits of the 9 bit read operation or the high 4 bits (one bit is
   unused in this design) and then uses those four bits to determine
   where to switch the packet to for forwarding.  Thus, for each of the
   16,677,216 /24 prefixes, the SRAM reads out a specific value of FEC.

   Table 1 shows an example of the meanings of the values of a 4 bit
   FEC.

                 Example of functions of 4 bit FEC values

              +-----------+--------------------------------+
              | FEC value | Action                         |
              +-----------+--------------------------------+
              |         0 | Drop packet                    |
              |           |                                |
              |         1 | Analyse packet by other means  |
              |           |                                |
              |         2 | Forward packet to interface 0  |
              |           |                                |
              |         3 | Forward packet to interface 1  |
              |           |                                |
              |       ... | ...                            |
              |           |                                |
              |        14 | Forward packet to interface 12 |
              |           |                                |
              |        15 | Forward packet to interface 13 |
              +-----------+--------------------------------+

                                  Table 1

   Where the router has more than 14 interfaces, or where there is a
   requirement to use more of these values to select alternative methods
   of processing, the next obvious option with currently available
   memory chips is to use 9 bits.  This provides for up to 510 output
   interfaces and requires two of the currently available 8M x 9 bit
   chips, with a little hardware to select one or the other as the
   active device.



Whittle                  Expires October 1, 2007               [Page 24]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   It may be attractive to fix the meaning of "2" to be "forward the
   packet by this interface", but that would require different data to
   be written into the SRAMs of each of the router's interfaces.
   Probably, the writing would be done by the interface's CPU rather
   than a central CPU, to allow full flexibility.

   For a "small" router - one with 14 or fewer interfaces - A31 to A9 of
   the packet's destination address drives the SRAM itself (A22 through
   A0) and A8 of the destination address is used by the hardware to
   select the high or low 4 bit nybble from the 9 read data pins.  For a
   large router, two chips would be needed, in parallel, with packet
   address bit A8 selecting one chip or the other to perform a read
   operation.  This yields a 9 bit FEC value.

   If every packet was known to be an IPv4 packet and all prefixes in
   the routing table were known to be /24 or shorter, then the above
   arrangement would be sufficient.  In practice, some elaborations
   would be necessary.

   Firstly, hardware would probably detect packets addressed to
   224.0.0.0/4 (broadcast) or 240.0.0.0/4 (reserved), although the
   latter range is a candidate for global routing in the future.

   Secondly, the router needs to be able to cope quickly with the main
   volume of AS to AS traffic, which will be forwarded according to
   prefixes of /24 to /8, while also being capable of correctly
   forwarding packets which match longer prefixes.  This can be achieved
   by making the SRAM FIB the first stage for all IPv4 packets, with a
   packet being sent to the TCAM section if its FEC result is 1, meaning
   "Analyse packet by other means.".  For instance, if any /24 prefix
   includes a longer prefix which has different FEC than the rest of the
   /24, then all packets addressed to this /24's address range should be
   analysed by the conventional TCAM etc. based packet classification
   system.

   The routing table for transit routers (and I assume multihomed border
   routers) such as that prepared daily by Geoff Huston [GIH BGP
   prefixes] have a small number of prefixes longer than /24.  These
   prefixes are analysed and listed separately, for each prefix length,
   at [RW BGP prefixes analysis].  These are presumably routes for
   connecting to routers themselves, rather than for handling Internet
   user traffic.  The small number of routes of this nature and the
   relatively small traffic volumes, primarily BGP updates, carried on
   these routes, should not tax the storage capacity or the speed of
   TCAM or of other approaches to forwarding.






Whittle                  Expires October 1, 2007               [Page 25]

Internet-Draft          SRAM-based IP Forwarding              March 2007


5.3.  IPv4 usage and policy

   This proposal requires no change in IPv4 usage or in the current
   policy of accepting /24 prefixes into the global BGP routing system
   and rejecting longer prefixes.  As far as I know, this is not a
   formal policy, but is widely adopted by all network operators.
   (There is provision for RIRs requiring limits on the size of prefixes
   added to routing tables in section 4.5 of [RFC3177].)  Ideally, to
   give router manufacturers and purchasers confidence, the proposed
   SRAM FIB approach, or its functional equivalent, would be
   standardised together with some kind of standard or agreement that
   this /24 limit would be retained for a long time, such as fifteen
   years or more.

   This proposal would be more attractive if it was accompanied by broad
   agreement about how IPv4 addresses are to be allocated to ISPs and
   other users with Autonomous Systems, particularly regarding what, if
   any, expectations there would be regarding how the ISPs and other
   users would split and separately advertise their address space.  The
   proposal is intended to facilitate an explosion in the number of IPv4
   BGP routes, to enable a greater number of users to make more
   efficient use of their address space.  However, this will only be
   practical after a number of years in which the SRAM-equipped routers
   replace those which cannot handle the growing number of RIB entries.

5.4.  BGP performance and stability

   If this proposal is implemented, and the expected growth of
   advertised BGP prefixes occurs, all participating routers will be
   required to handle a much greater number of routes and routing
   changes.  It may be expected that improved router CPU speed and
   memory capacity will be able to cope with this, with suitable
   planning.  However it cannot be assured that the global BGP system
   will remain stable and responsive enough under this increased load.
   The volume of data transacted as part of the BGP protocols and the
   time delays in transferring it are unlikely to be prohibitive.
   However, the time it takes for the increasing number of routers to
   collectively settle after a change in advertised prefixes is likely
   to be a major challenge.

   Perhaps the regular /24 boundaries of the new hardware architecture,
   and the likely increased advertisement of /24 prefixes, will enable
   BGP communication to be optimised in terms of network efficiency or
   to achieve faster convergence and greater stability.

   If this proposal is implemented, there will probably need to be
   changes to the BGP protocol and to administrative standards for
   advertising prefixes (there are few, if any, at present) in order to



Whittle                  Expires October 1, 2007               [Page 26]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   cope with the greater tasks imposed on the global BGP routing system.
   At present, a great deal of the BGP protocol traffic concerns long
   prefixes (small numbers of addresses) which change relatively often.
   This is documented in the "Adds and Wdls per Prefix Length" section
   of Geoff Huston's CIDR report [GIH CIDR Report].

   If there were disincentives to such rapid changes in advertised
   routes - implemented in the configuration of routers, in RIP
   guidelines and rules, and/or in the BGP protocol itself, then the
   changes which are advertised would be more constrained to those which
   are "most necessary".  This value judgement needs to be according to
   the interests of the majority of operators of DFZ routers, who
   directly bear the burden of each BGP change.  An example of BGP
   changes which might be deemed unreasonable in this framework is the
   multiple changes per day generated by an ISP who uses BGP multihoming
   to achieve traffic engineering, for instance for load balancing as
   traffic moves from a business-hours pattern to a residential pattern.

   Disincentives could be imposed on the ISPs and other AS users who
   make changes which are deemed to be excessive.  For instance, if a
   user often changed how they advertised a prefix - whether
   deliberately or due to instability in their network, then beyond some
   kind of limit, this prefix would have longer periods of
   unreachability due to some or many routers giving this prefix's
   changes a low priority.  I understand that this is already
   implemented within many routers, primarily to improve stability by
   not propagating fluctuating changes too rapidly.

5.5.  Alternative arrangements for IPv4

   For the sake of discussion, if the proposed changes are accepted as
   desirable, we might ask how could they be improved or extended,
   either initially or at some time in the future.

   The most obvious option would be to double the SRAM requirement in
   each interface of each DFZ router and extend the BGP prefix length
   limit to /25.  This would have advantages, including enabling a finer
   use of IP address space, such as allowing ISPs and AS users who only
   require a handful of IP addresses to be multihomed to do so with
   smaller allocations of address space.

   It is my impression [RW BGP prefixes analysis] that there is so much
   unused, or very sparsely used, IPv4 address space at present that the
   changes proposed in this Internet Draft would be sufficient to enable
   much better use of address space.  Assuming IPv4 is widely used in
   the decades to come, a long-range plan might be made in the future to
   allow advertisement of /25 prefixes - once the cost and power
   dissipation of the required SRAM is much lower than it is today.



Whittle                  Expires October 1, 2007               [Page 27]

Internet-Draft          SRAM-based IP Forwarding              March 2007


6.  SRAM-based FIB and addressing changes for IPv6

6.1.  Impractical with current global unicast allocations

   Current IPv6 address management policy [IPv6-Policies] [RFC3177]
   [RFC4291] provides for allocation of global unicast addresses within
   the prefix 2000::/3, which fixes the most significant three bits of
   the address to "001".  In general, a /48 prefix will be assigned to
   each end user. 45 bits - 124 to 80 inclusive - vary in this scheme.
   If the longest prefix admitted to the global BGP IPv6 routing system
   is a /32 (as, I think, is current practice) then this still requires
   routers to classify packets based on 29 bits - bits 124 to 96
   inclusive.

   In principle an SRAM system could be used to map these 29 bits
   directly to four or nine bits of FEC data.  However, for a small
   router (one with up to 14 interfaces) this would require 32 72Mb SRAM
   chips.  This is impractical in terms of cost, space and power
   consumption, unless perhaps the one set could be used for the entire
   router, rather than on each interface.  I think it is unlikely that
   this amount of RAM would be practical to install in each interface of
   tens of thousands of routers in the next ten years - or perhaps at
   any time in the future.

6.2.  Reallocating IPv6 global unicast addresses

   This section suggests a complete reallocation of the current 2000::/3
   prefix of global unicast addresses.  The following section suggests a
   less disruptive and more attractive alternative: maintaining current
   allocations, by defining a small prefix to be handled with SRAM-based
   forwarding, either within or outside 2000::/3.  Further sections
   below discuss the use of smaller amounts of memory, initially, for
   the IPv6 SRAM-based FIB function, including the use of no extra
   memory chips by applying 2 million spare locations in the SRAM which
   is needed for IPv4.

   Assuming the /32 limit is maintained, an SRAM-based FIB architecture
   would be practical if it could be known that all global unicast
   addresses would fall within a smaller range than is currently the
   case.  A router would first process an IPv6 packet to determine
   whether its destination address was within the restricted range
   covered by the SRAM system, and if so use that system to determine
   its FEC.  As with the IPv4 proposal, one value from the SRAM would
   cause the packet to be dropped, another would cause it to be
   processed by conventional (TCAM etc.) techniques and the rest of the
   possible values would specify which interface the packet should be
   forwarded to.




Whittle                  Expires October 1, 2007               [Page 28]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   There are several options for RAM size and the range within which all
   global unicast addresses must be constrained to.  I propose the
   decision be based on ensuring a long-lasting standard, with hardware
   implementation costs which are practical in the short term.  In the
   event that this space becomes overly restrictive at some time in the
   future, such as in one or two decades, a decision could be made to
   double the address space and therefore the SRAM requirements for
   routers.

   One option is to devote two 72Mb SRAMs for small routers and four for
   larger routers - those with between 15 and 510 interfaces - to the
   IPv6 global unicast FIB function.  If IPv6 global unicast addresses
   were reallocated to 2000::10, this would provide direct hardware
   support for 33,554,432 /35 prefixes, each of which provides 8192 /48
   user networks.  This scheme would support 4,194,304 /32 allocations
   to each ISP or AS end-user - each of which could be broken into eight
   independently advertisable /35 prefixes.

   To halve the amount of RAM, several changes could be made to this
   scheme.  One is halving the total global unicast space so that
   2,097,152 /32 allocations could be made.  This might be a reasonable
   choice, if it could be shown that that this would probably cover
   demand for 15 years or so.  Another approach would be to map /34
   prefixes, rather than /35.  This reduces the maximum number of
   separately advertisable subnets in each /32 from eight to four.
   Larger organisations would then be required to use more than one /32,
   for instance to robustly multihome more than one site.

   Reallocating currently allocated IPv6 global unicast addresses to a
   range 1/128 the size of their current spread raises some
   difficulties.  Firstly, it would require almost all current users to
   renumber their networks.  However, RIRs have long insisted that all
   users, other than large ISPs, should renumber their networks whenever
   they change their connection to the IPv6 Internet - so it does not
   seem unreasonable to expect the RIRs and ISPs to undergo a once-only
   renumbering at this early stage of IPv6 adoption.

   The second change will need to be in the minds of users and
   administrators, who formerly saw the vast spaces of IPv6 as an asset.
   The goal of address aggregation was seen as being somewhat easier to
   achieve with a vast and uncluttered address space, because even a
   tiny fraction of the total space provides billions of public IP
   addresses.  The trouble with this approach is that it precludes the
   use of SRAM based FIB techniques, leaving IPv6 routing to costly,
   power-hungry, unwieldy techniques such as TCAMs.

   By a stroke of luck, the number of bits in play in IPv4 addressing
   neatly matches mid-2000s SRAM capacities.  The extra 7 or so bits in



Whittle                  Expires October 1, 2007               [Page 29]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   flux within the current IPv6 allocations precludes the use of SRAM -
   the only cost-effective, power-efficient, hardware routing technology
   which currently seems to be available.  IPv6's current address spread
   in bits 124 to 118 might therefore be considered harmful to the long-
   term routability of the Internet.  Fortunately, even if these bits
   are fixed to zero to enable the SRAM FIB architecture, the vast
   capabilities of bits 0 to 92 should not result in shortages of IP
   addresses or inflexibility in usage for many decades, or perhaps
   forever.

6.3.  Defining a separate IPv6 prefix for SRAM-based forwarding

   As a less disruptive alternative to the above suggestion, it may be
   desirable to continue all existing global unicast allocations (to
   RIRs) and assignments (from RIRs to ISPs) and to define a particular
   prefix, such as a /10, either within or outside 2000::/3, for which
   future routers will use SRAM-based forwarding.

   The long-term goal would remain the same: for most or all global IPv6
   traffic to be handled by future routers with SRAM-based techniques,
   so that the space could be split and advertised down to a defined
   granularity, such as /35 prefixes, with fast SRAM-based forwarding
   and no requirement for route aggregation.  In the discussion which
   follows, the "/10" refers to the prefix for which future high-end
   routers will use SRAM-based forwarding, to a granularity of (for
   instance) /35.  A final decision on the size of both prefixes would
   require consideration of long-term IPv6 development goals and of the
   costs of SRAM and the other changes which would be required in
   routers.

   As with the previous suggestion of complete reallocation, the
   definition of the /10 would need to result from agreement involving
   router manufacturers, network operators, RIRs and the IETF/IANA.
   However, since no reallocation is required, consensus may be much
   easier to achieve.  RIRs would be able to assign address space within
   the /10 without regard to network topology or route aggregation.
   This means that space within the /10 could be allocated to RIRs
   without such concerns.  It would be no concern if neighbouring /32
   prefixes were allocated to ISPs and AS end-users in France, Nigeria,
   New Zealand and Ukraine.  This would enable smaller allocations to
   RIRs, or enable RIRs to assign space to ISPs and AS end-users from a
   common pool.

   Prefixes within the new /10 could be assigned to any ISP or end-user
   organisation with an AS number, on the basis that both ISPs and AS
   end-users could, in the long term (when suitable SRAM-FIB routers
   become ubiquitous), advertise their space down to /35 prefixes with
   complete freedom in terms of network topology.  This does not



Whittle                  Expires October 1, 2007               [Page 30]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   necessarily mean that they would be encouraged or allowed to rapidly
   change these advertisements, because the load and stability problems
   such changes place on the global BGP routing system remains a burden
   on the entire network.

   If the /10 was located within 2000::/3, then the administrative
   changes would involve a subset of the space currently being allocated
   to RIRs.  Non-SRAM-based (hereafter referred to as "conventional")
   routers would handle packets addressed to the /10 using conventional
   TCAM etc. techniques.  In the future, when the number of advertised
   prefixes within this /10 grows to exceed the capacity of conventional
   routers, then conventional routers which are still being used as
   transit routers or as multihomed border routers will not be able to
   handle all the traffic addressed to the /10.  Given the slow pace of
   IPv6 adoption, this could be quite some time in the future - enough
   time for SRAM-based routers to be very widely deployed.  I assume
   that irrespective of any initiatives resulting from this Internet
   Draft, SRAM-based FIB architectures will widely implemented in high-
   end routers in the 2010 to 2015 timeframe, since this is the
   simplest, most "future-proof" method of handling the continual growth
   in the number of IPv4 BGP routes.  It is possible that this expected
   change to router architecture for IPv4 would be extended to cover
   IPv6, probably with one or two extra SRAM chips for this purpose.
   (Below, I discuss handling IPv6, initially, in spare space inside the
   IPv4 SRAM.)  However, this would probably only occur if there was a
   formal agreement or technical standard defining a small subset of
   IPv6 space where SRAM-based forwarding and freedom from route
   aggregation concerns would apply.

   If an industry-wide agreement was reached about SRAM-based forwarding
   for IPv4 and IPv6 in the next few years, then a /10 inside the
   current 2000::/3 would be minimally disruptive.  If the /10 was
   defined outside 2000::/3, then this would more clearly distinguish
   the new space, with its need for SRAM-based routers to be widely once
   users advertise so many routes in this space that conventional
   routers can no longer cope.  I expect conventional routers would have
   no difficulty handling global unicast traffic outside the current
   2000::/3 prefix.  At most, I imagine a firmware or configuration
   change would be required.

6.4.  Minimal memory space for IPv6

   The above proposals for IPv6 are intended to cope with a very large
   number of ISPs and AS end-users.  The amount of memory required for
   SRAM-based IPv4 forwarding depends on only two factors: the
   granularity - which I suggest will remain fixed at /24 - and the
   width of bits required to specify the FEC for the number of
   interfaces in each particular router.  With IPv4, the granularity and



Whittle                  Expires October 1, 2007               [Page 31]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   total address range have already been defined.

   Despite IPv6's long pedigree, and the destruction of end-to-end
   connectivity caused by the widespread deployment of NAT firewalls in
   IPv4, there remain profound doubts about whether IPv6 will ever be
   practical for most existing Internet users, whether it will be
   profitable for ISPs and whether its promised benefits will be worth
   the effort.  (Perhaps, IPv6 will be so poorly adopted, and IPv4 can
   be kept workable for long enough, that a whole new approach to
   networking will be developed - with conceptual and functional
   improvements which would make a wholesale changeover worthwhile.)
   NATs will never be eliminated from IPv4 usage, and an increasing
   number of protocols are being equipped with their own, or separate,
   NAT traversal capabilities.  The IT industry has a long history of
   failing to make non-backward-compatible transitions.  I believe that
   SRAM-based forwarding in DFZ routers, combined with the freedom this
   brings for splitting and advertising smaller chunks of address space,
   will enable a vastly more efficient use of IPv4 address space.  This
   may extend IPv4's useful life for decades, so there may be a
   relatively slow growth in IPv6 traffic volumes and number of BGP
   advertised prefixes.

   When discussing the prospect of building significant additional
   hardware into each interface of every future DFZ router, it may be
   argued that the ten-year outlook for widespread IPv6 adoption is too
   uncertain to justify substantial expense.  If the installation of a
   second 72 Mbit SRAM chip on every router interface (for "small"
   routers with up to 14 interfaces) - in addition to the chip required
   for IPv4 - could not be justified for foreseeable IPv6 traffic
   requirements, there is an alternative involving no extra expense.
   The previous suggestions for a /10 to provide 2^25 separately mapped
   /35 prefixes assume the use of two 72 Mbit SRAM chips per router
   interface.  This is arguably overkill for the next decade or so, but
   I suggested this in the knowledge that IPv4 SRAM requirements are
   essentially fixed, and that it would be desirable to set a technical
   standard for IPv6 which would last for several decades.

   The two chip IPv6 system (meaning 3 chips per interface in total for
   "small" routers and 6 for routers with more than 14 interfaces)
   applies each chip as if it had 24 address lines and 4 data lines.  So
   each chip maps each of 16,777,216 prefixes to 16 possible values of
   FEC.  Two chips for IPv6 could map, for instance, 33,554,432 /35s -
   providing 4,194,304 /32 prefixes for ISPs and AS end-users.

6.4.1.  Using free space in the IPv4 SRAM

   In the event that a second SRAM cannot be justified for IPv6, here is
   a proposal to apply the unused space in the IPv4 chip.  Since IPv4



Whittle                  Expires October 1, 2007               [Page 32]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   addresses above 224.0.0.0 are never likely to be used for traffic,
   this leaves 1/8 of the SRAM unused.  This means there are 2,097,152
   memory locations which can be applied to IPv6 without any additional
   hardware cost.

   One way of using this is to retain the /35 granularity of the "two
   additional chips" proposal, with eight /35s for every /32 assignment
   to an ISP or AS end-user.  This provides for 262,144 such /32
   assignments within a /14 prefix.  Each /35 contains 8192 /48 prefixes
   - the typical assignment of address space to a non-AS end user.  Such
   end users may be a home or office with a DSL line, the router of a
   larger company, or perhaps a single mobile device.  Each /48 provides
   65536 user networks - such as LANs - each of which can contain an
   essentially unlimited number of hosts, all with unique public global
   unicast addresses.  While this is 1/16 the amount of address space of
   the first, two-chip, proposal, it could be argued that it is an
   adequate number of freely advertisable prefixes to support IPv6 for
   the lifetime of the next generation of routers.  (I expect that these
   proposals will mean that the current 5 year or less lifetime of high
   end routers be extended to 10 or so years, as long as they are
   handling about the same traffic volumes.)

   It may seem odd to think of a spare 1/8 of an SRAM as an adequate
   medium-term construct on which to base IPv6 routing, but the
   2,097,152 /35 prefixes it provides should go a long way.  It is
   probably not necessary to assign this space in larger chunks than /32
   in order that each ISP (or AS end-user) will have a large contiguous
   block to populate with customers at some later date - because there
   is no problem with ISPs or AS end-users requesting more /32s as they
   need them.  The SRAM-based FIB architecture does not require /32
   assignments to ISPs - it only requires that the granularity be set in
   the long term, such as to /35, and that the address range for the
   system be specified for the next ten to fifteen years. 2,097,152
   separately routable /35 prefixes may be considered an adequate amount
   for the foreseeable future, since it provides 17 billion /48s, each
   of which supports 65536 LANs, each with essentially an unlimited
   number of hosts.  Utilisation of this address space, in terms of how
   many /48s are connected to a customer's site as a proportion of the
   8,192 /48s in each /35 prefix, could be relatively high because there
   should be no problem nearly filling up most or all of the /35s in a
   /32, before requesting another /32.

   An alternative to this scheme would be to fix the IPv6 SRAM-based
   forwarding granularity at /34, providing four /34s per /32, with
   524,288 PI /32s contained in an initial /13 prefix for SRAM-based
   forwarding.  This results in each /32 being somewhat less flexible
   since it can only be separately advertised in four pieces, rather
   than eight.  Each piece contains twice the number of /48s (16,384),



Whittle                  Expires October 1, 2007               [Page 33]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   and the system covers twice the number of /32s than in the previous
   arrangement.

   This "spare-space, 2 million /35s" proposal would not involve
   reallocating current global unicast address space into the relatively
   small /14.  It would make most sense with a /14 established either
   inside or beyond 2000::/3.  Wherever the /14 is established, the
   space above it should be available for future SRAM-based IPv6
   forwarding, once the exhaustion of that /14 space prompts the
   production of a new generation of routers with greater IPv6
   capabilities - with either two 72 Mbit chips, or a single 144 Mbit
   chip.  (These chips are part of the Quad Data Rate architecture, but
   are not yet in production.)

6.4.2.  Using a smaller SRAM for IPv6

   Another alternative to providing IPv6 SRAM-based forwarding at
   minimal expense might be to define a hardware architecture and
   addressing plan based on one, or even two, 72 Mbit chips ultimately
   being dedicated to IPv6 forwarding, but in the initial years of
   deployment to populate the boards of routers with less expensive 36
   Mbit or 18 Mbit chips.  These are surface-mount chips which are
   soldered in place.  Unless they were mounted on plug-in boards (which
   are costly, bulky and introduce electrical and reliability concerns)
   it is not practical to design routers with plug-in SRAM for this FIB
   function.  These chips are all "pin-compatible", so the circuit board
   design of the router's interfaces remain the same.  The actual amount
   of memory installed is determined at the printed circuit board
   assembly stage.

   An 18 Mbit chip would map 4,194,304 prefixes, and could be combined
   with the 2,097,152 prefixes which can be mapped using the spare space
   in the IPv4 SRAM chip.  Thus an 18 Mbit chip would provide 6,291,456
   /35s, for instance to provide eight /35s for 786,432 ISPs and AS end-
   users, each using a /32.

   It would be straightforward to devise an addressing plan with several
   stages of expansion for IPv6.  Stage 0 would be for SRAM mapping of
   2,097,152 /35 prefixes (or whatever granularity was chosen) - using
   spare space in the IPv4 SRAM.  Stage 1 would use an 18 Mbit SRAM (or
   a 36 Mbit SRAM for larger routers) to map a total of 6,291,456
   prefixes.  Stage 2 would use a 36 Mbit SRAM to map 10,485,760
   prefixes etc.  Probably by the time this was necessary, chip costs
   would be lower still and probably a single 144 Mbit chip would be
   installed, mapping 16,777,216 prefixes, or 18,874,368 if the spare
   space in the IPv4 half of the chip was also used.

   Routers could be designed with a place for an IPv6 SRAM, beside the



Whittle                  Expires October 1, 2007               [Page 34]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   72 Mbit SRAM for IPv4.  This half postage stamp sized space of 18 x
   16mm would remain empty until such time as new routers were expected
   to need to cope with traffic addressed to beyond the range of Stage
   0.  It may seem strange to base the architecture and administration
   of the Internet on the physical characteristics and costs of
   particular memory chips, but I believe that unless this is done, the
   Internet will become unroutable except through inefficient and
   uncoordinated application of expensive electronics, with the costs
   being passed on to all Internet users.










































Whittle                  Expires October 1, 2007               [Page 35]

Internet-Draft          SRAM-based IP Forwarding              March 2007


7.  Security Considerations

   None.
















































Whittle                  Expires October 1, 2007               [Page 36]

Internet-Draft          SRAM-based IP Forwarding              March 2007


8.  IANA Considerations

   If this proposal, or something like it, is adopted for IPv6, then
   significant changes will need to be made to the IPv6 Address
   Allocation and Assignment Policy [IPv6-Policies].  Section 3.4,
   concerning address aggregation, would no longer apply to the /10 (for
   instance) prefix for which routers will perform SRAM-based
   forwarding.

   These proposals for an SRAM-based FIB architecture for IPv4 may not
   require any changes to Internet usage or IANA standards.  However,
   once implemented globally, the requirement to distribute addresses
   hierarchically to facilitate routing scalability, as expressed in
   section 1.2 of [RFC2050] would no longer apply.  This RFC, in
   November 1996, anticipated improved routing technologies in the
   future: "In the event that routing or router technology develops to
   the point that adequate routing aggregation can be achieved by other
   means or that routers can deal with larger routing and more dynamic
   tables, it may be appropriate to review these constraints."
































Whittle                  Expires October 1, 2007               [Page 37]

Internet-Draft          SRAM-based IP Forwarding              March 2007


9.  Informative References

   [GIH BGP prefixes]
              Huston, G., "Geoff Huston's BGP prefixes.txt", March 2007.

   [GIH CIDR Report]
              Huston, G., "CIDR Report", March 2007.

   [Gartner]  Mingay, S., "The IT Industry Is Part of the Climate Change
              and Sustainability Problem", November 2006.

   [Gupta]    Gupta, P., "Pankaj Gupta's thesis and other material on
              routing and forwarding", August 2006.

   [I-D.iab-raws-report]
              Meyers, D., "Report from the IAB Workshop on Routing and
              Addressing", draft-iab-raws-report-01 (work in progress),
              February 2007.

   [IAB-RAWS-website]
              Meyers, D., "IAB Workshop on Routing and Addressing -
              resources and presentations", December 2006.

   [IPv6-Policies]
              IANA, "IPv6 Allocation and Assignment Policy", June 2005.

   [QDR Consortium]
              QDR Consortium, "QDR Consortium", March 2007.

   [RFC2050]  Hubbard, K., Kosters, M., Conrad, D., Karrenberg, D., and
              J. Postel, "INTERNET REGISTRY IP ALLOCATION GUIDELINES",
              BCP 12, RFC 2050, November 1996.

   [RFC3177]  IAB and IESG, "IAB/IESG Recommendations on IPv6 Address
              Allocations to Sites", RFC 3177, September 2001.

   [RFC4291]  Hinden, R. and S. Deering, "IP Version 6 Addressing
              Architecture", RFC 4291, February 2006.

   [RW BGP prefixes analysis]
              Whittle, R., "Probing the density of ping-responsive-hosts
              in each /8 IPv4 prefix and in different sizes of BGP
              advertised prefix", March 2007.

   [Renesas]  Renesas, "R8A20210BG data sheet", February 2005.

   [Samsung SRAM]
              Samsung, "72Mb QDRII data sheets", February 2006.



Whittle                  Expires October 1, 2007               [Page 38]

Internet-Draft          SRAM-based IP Forwarding              March 2007


   [Shah-Gupta]
              Shah, D. and P. Gupta, "Fast incremental updates on
              Ternary-CAMs for routing lookups and packet
              classification", January 2001.

   [Taylor-Spitznagel]
              Taylor, D. and E. Spitznagel, "On using content
              addressable memory for packet classification", March 2005.

   [Wang-Tzeng]
              Wang, G. and N. Tzeng, "TCAM-Based Forwarding Engine with
              Minimum Independent Prefix Set (MIPS) for Fast Updating",
              February 2006.






































Whittle                  Expires October 1, 2007               [Page 39]

Internet-Draft          SRAM-based IP Forwarding              March 2007


Author's Address

   Robin Whittle
   First Principles

   Email: rw@firstpr.com.au
   URI:   http://www.firstpr.com.au/ip/












































Whittle                  Expires October 1, 2007               [Page 40]

Internet-Draft          SRAM-based IP Forwarding              March 2007


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Whittle                  Expires October 1, 2007               [Page 41]