INTERNET-DRAFT                                               G. Trotter                                                  J. Dunn
Benchmarking Methodology Working Group             Agilent Technologies                        C. Martin
Expires: August 2003                                      February 2003 May 2005                                      SI International
                                                           October 2004

Methodology for Forwarding Information Base (FIB) based Router Performance


Status of this Memo

   "By submitting this Internet-Draft, I certify that any applicable patent
   or other IPR claims of which I am aware have been disclosed, or will  be
   disclosed,  and  any  of  which  I  become  aware  will be disclosed, in
   accordance with RFC 3668."

   This document is an Internet-Draft and is in full conformance  with  all
   provisions of Section 10 of RFC2026 [1]. [IPROC].

   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.

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

   The list of Internet-Draft Shadow Directories can be accessed at


   The forwarding performance of an IP router may be is highly  dependent upon or
    may be linked to the composition and size of  on  the
   information in its forwarding information base installed within a router. base.  This document describes
   the methodology to  be  used  to  determine  the  IP  packet  forwarding
   performance  of  an  IP  router  as a function of the routers ability to
   properly form and optimize its forwarding information base installed within a router.

Table of Contents

    1. Introduction....................................................2
    2. Terms Of Reference..............................................2
    3. Overview........................................................2
    4. Router Setup....................................................3
    5. Test Setup......................................................3
    6. Methodology Of Route Advertisements.............................3
    7. Table Size......................................................4
    8. Table Composition...............................................5
    9. Offered Packet Load.............................................5
    10. Packet Format/Size.............................................6
    11. Determining The Maximum Fib Size...............................6
    12. Methodology....................................................7
    12.1 Baseline Measurements.........................................7
                      FIB-based Router Performance       February, 2003

    12.2 Maximum Fib Size Test.........................................7
    12.3 Fib Size Impact On Packet Forwarding Performance..............8
    13. Security Considerations........................................9
    14. References.....................................................9
    15. Acknowledgments................................................9
    16. Author's Addresses.............................................9 base.

1. Introduction

   This document  covers  the  measurement  of  the  IP  packet  forwarding
   performance  of  IP  routers  on  the  basis  of  the routers ability to
   properly form and optimize its forwarding information base (FIB) installed within a router.  [2] (FIB).  [FIB-
   TERM] describes the terminology associated with this document.

   This  version  of  the document describes a more general approach to the
   determination of  router  performance  than  previous  versions.   As  a
   result,  it  is the intent of the authors that this document serves as a
   catalyst for further discussions concerning the approach outline in this

   draft-ietf-bmwg-fib-meth-02.txt                           October 2004

   draft.   The  purpose  of this document is to describe a methodology for
   measuring the impact of a FIB of generation from a particular size and composition given routing  information
   base  (RIB) on the forwarding performance of a router.  The objective is
   to determine whether a router can maintain performance levels as FIBs
    continue to grow the RIB
   grows in size. size and complexity.

   This  document  utilizes  the  methodology  described  in [3]  [METHOD]  for
   measuring the FIB-dependent throughput, FIB-dependent latency  and
    FIB-dependent  FIB-
   dependent  frame  loss  rate  of  IP packets as they traverse the router
   under test.  The forwarding performance of a router should  be  observed
   under different FIB RIB sizes and compositions.

    In this document, the FIB is modified only when traffic is not
    traversing the router.  The effect of dynamic changes on the
    forwarding performance of a router is outside the scope of this

2. Terms Of Reference

   This  document utilizes the methodologies for packet throughput, latency
   and loss measurements described in [3]. [METHOD].

   Definitions unique to this test methodology are covered in [2].

    This [FIB-TERM].

   The application of methodologies  described  in  this  document covers only IPv4 packets traversing an  is  not
   limited  to  IP router.
    Applicability  forwarding;  however,  it  is  beyond the scope of this
   document to other packet types (such as MPLS-
    prefixed packets or non-IP packets) explicitly describe their application. In this document, use
   of  the  term  IP is not appropriate. protocol version independent.  Traffic, RIB and FIB
   may be IPv4, IPv6 or both.

3. Overview


   The methodology takes into account two key features of a FIB - described in this document is based on the
    FIB size and precept  that
   the  FIB prefix distribution.

    This  is  formed  from  information  in the RIB and, possibly, other
   configured variables.  The methodology does not specify a particular means is independent of the particulars
   associated  with populating a
    FIB - a routing protocol should the RIB or setting these variables; however,
   this SHOULD be used, although a done using routing protocols, e.g., OSPF [OSPF].  RIB and
   FIB could be
    manually entered into a router.  One implication of this is that
    there needs to   contents  MAY  be protocol-independent means for determining when a
    router's FIB has been fully populated (described in 12.2).

                      FIB-based Router Performance       February, 2003

    Once a FIB of a particular size and prefix distribution is entered
    into the router, [3] style measurements are performed in order to
    gauge the effect of the FIB on packet FIB-dependent throughput, FIB-
    dependent latency and FIB-dependent frame loss rate.

4. Router Setup

    This is an out-of-service methodology.  The router should be
    configured realistically.  That is, it should be configured with
    physical interface cards, switching fabrics, and route processors
    providing the basis for realistic product comparisons.

5. Test Setup

    The router is connected to test equipment capable of advertising
    network prefixes into the router under test and generating IP
    packets to these advertised networks.  In the absence of test gear
    capable of advertising network prefixes into the router under test,
    the network prefixes could be manually entered into the router.

    This methodology does not specify  determined  either  through  observing  traffic
   forwarding  or require a particular physical
    interface type: all measurements are performed exclusively on IP

6. Methodology Of Route Advertisements

    It is recommended that routes  management  information   base   (MIB)   queries.    For
   completeness,  this determination SHOULD be advertised into the router under
    test by made using a routing protocol to speed the advertisement both.  Generation
    routes.  Routes may be entered into the FIB manually, but this is
    both tedious, and makes the correlation between entered routes and
    offered traffic awkward (see section 9).

    Routes may be advertised into from the router RIB based on a single interface, or
    over multiple interfaces.  This methodology does not distinguish
    between either method.

6.1 Order of Route Advertisements

    Routes can be advertised into the router in any order three major components:

   - a router may
    organize its FIB to maximize its performance Interface Identifier - the impact of order
    of advertisement cannot be presupposed to have an impact on the
    structure of the FIB.

6.2 Prevention of Route Aggregation

    Routes should be advertised into the router in such a manner as to
    prevent route aggregation.  Routes may be aggregated as follows.  If
    100 routes are advertised on a single interface within a common
    prefix of, Optimization - Routing Policies

   The following three sub-sections describe  these  components  and no other advertisements  their
   effect on any other
    interface have a prefix of, then the router may enter a
    single /16 entry into the FIB, directing all traffic with a prefix to a particular interface.  Care must be taken to
                      FIB-based Router Performance       February, 2003

    prevent this from occurring, as it will result in smaller than
    intended FIBs being entered within the router under test.

    As an example of a means of router advertisement designed to prevent
    route aggregation, consider the advertisement of 16 /16 prefixes
    into a 4-port router in the diagram below:

    1.1,2.1,3.1,4.1 -----|               |----- 1.3,2.3,3.3,4.3
                         |               |
                         |               |
                         |               |
    1.2,2.2,3.2,4.2 -----|               |----- 1.4,2.4,3.4,4.4

    In this example, the router will not be able to aggregate the
    entries from 1.0, since an entry exists on every port - the same
    applies for the entries from 2.0, 3.0 and 4.0.  This method of route
    advertisement into the router must be used.

6.3 Learning time

    A router takes time to "learn" routes.  The overhead associated with
    learning a route may include processing the routing protocol message
    containing a new FIB entry, placing the entry into the FIB, and
    then, in some modern routers, distributing the updated FIB to each
    interface in the router.

    This methodology does not measure or dictate the time that a router
    takes to build a complete FIB.  However, it is vital to the
    execution of this methodology to ensure that a router has completed
    learning routes and building the forwarding information base before
    tests proceed.

    There are two methods that can be taken to ensure that a router has
    learned all routes.  For the first method, the router can be queried
    via an attached console to reveal the current FIB size.  If access
    to the console is not available, then test packets can be sent
    through the router at such rate that packet loss does not ordinarily
    occur.  Test packets should test each entry in the FIB.  No packet
    loss can indicate that the router has learned all routes, and is
    forwarding packets to all advertised destinations.  However, this
    method is not foolproof - a router may instead have filled its FIB,
    and lost packets may indicate that the FIB is full, and not that the
    router is still learning routes.

7. Table Size

    This methodology does not specify FIB sizes to be installed within
    the router under test.  However, it is expected that this
    methodology will be used through to the maximum possible FIB size
    purported to be supported by the router under test.

                      FIB-based Router Performance       February, 2003

    This methodology recommends starting with a small FIB size - a
    single network per physical interface - in order to perform a basic
    performance benchmark on the router under test.  Subsequent tests
    will increase the FIB by size 'N'.  The FIB will be increased
    through to the maximum size possible (see section 11 for a
    discussion of determining the maximum possible FIB size).

8. Table Composition

    The composition of a FIB consists of a number FIB entries, with each
    FIB entry containing a network prefix.  The network prefix length of
    each FIB entry may vary.  These network prefixes typically range, in
    a typical Internet router's FIB, from 8 to 30 bits in length (/8 to
    /30) (this document does not attempt to pre-suppose the composition
    of a typical FIB within a router in the Internet, however).
    Destination address matches within FIBs consisting entirely of 8-bit
    network prefixes may be very rapid (few bits in each destination
    address/network prefix need to be matched), whereas it can be
    expected that destination address matches within a FIB populated
    entirely with 30-bit network prefixes (highly unlikely) will be

9. Offered Packets

    To gauge the impact of a FIB on the performance of a router, IP
    packets must be delivered to the router such that the FIB is fully
    exercised.  That is, packets must be delivered into the router on
    every interface directed to stations whose network prefix is
    advertised on every other interface.

    This method of traffic generation fairly exercises the FIB on the
    router.  Modern routers may maintain a cache of the most frequently
    used routes on a per-interface (or, per-line card) basis, or they
    may maintain a complete copy of the FIB on a per-interface (or per-
    line card) basis.  Generating packets from every interface to every
    advertised network ensures that each copy of the FIB is stressed, as
    well as ensuring that a router's FIB cannot be optimized (i.e. by
    installing summary routes).

    Consider the diagram below:

    1.1,2.1,3.1,4.1 -----|A             C|----- 1.3,2.3,3.3,4.3
                         |               |
                         |               |
                         |               |
    1.2,2.2,3.2,4.2 -----|B             D|----- 1.4,2.4,3.4,4.4

    In this diagram, packets sent into interface A must be directed to a
    destination address present in each network advertised on ports B, C
    and D.  That is, the "transmit packet list" for packets sent into
    port A must be:

                      FIB-based Router Performance       February, 2003

    and then repeated.

    Note that packets are transmitted to destinations on each port in a
    round-robin manner.  That is, A transmits a packet to B, then a
    packet to C and then a packet to D, and then repeats, using the next
    destination advertised on port A, and so on.  This method ensures
    that all aspects of the router (switching fabric, interface cards,
    route processor, etc.) are stressed equally.

    Also note that packets are sent from all interfaces simultaneously,
    again ensuring that all router components are stressed equally.  See
    section 16 in [3].

10. Packet Format/Size

    See [3] for a discussion of packet formats and sizes.

11. Determining The Maximum Fib Size

    In order to determine the maximum FIB size, a method similar to that
    used to determine whether all routes have been learned (see section
    6.3) will be used.

    Without observing the exchange of the routing protocol, it is
    necessary to ascertain the size of the FIB from observation of
    packets sent from the router.

    The most methodical way of discovering the maximum FIB size is to
    advertise network prefixes to the FIB, test the addition of the
    entry by sending packets to the new network, ensure receipt of this
    packet and repeat until packets are no longer forwarded to the newly
    added network.  Care must be taken to ensure that packets continue
    to be forwarded to all advertised networks, even while new networks
    are added - a router may "age-out" old entries in order to ensure
    that its FIB is filled with current entries.

    The absence of packets received at a particular network is
    indicative of entries not being present within the FIB, and thus
    indicates that the FIB has filled.

                      FIB-based Router Performance       February, 2003

    If the approximate FIB size is known in advance, a larger number of
    routes can be advertised into the router, then the maximum table
    size can be found incrementally from this point.

    When using IP packets to discover the maximum sized FIB supported by
    the DUT, IP packets should be sent in at a rate that is
    significantly below that of the maximum measured throughput of the
    router discovered during baseline measurements (see section 12.1).

12. Methodology

    This methodology makes use of the packet forwarding measurements
    described in RFC 2544.

12.1 Baseline Measurements

    Objective:  The objective of the baseline measurement is to
    determine the nominal packet forwarding performance of the router,
    with a minimal sized FIB.

    Procedure:  A route to a single network should be advertised on each
    port of the router under test - a router with 64 ports would thus
    have an installed FIB of 64 entries.

    As described in section 9, packets should be offered to the router
    in order to create a full mesh between all advertised networks.

    Using measurements described in [3] for the throughput, latency,and
    frame loss rates (as per sections 26.1, 26.2, 26.3 and 26.4 in [3]),
    the FIB-dependent throughput, FIB-dependent latency and FIB-
    dependent frame loss rate should be measured and the results duly

    Reporting Format:  Results should be reported as per [3].

12.2 Maximum FIB Size Test

    Objective:  The objective of this test is to determine the maximum
    size of the FIB that can be accommodated within the DUT.  Discovery
    of the maximum limit of the size of the FIB is necessary for the
    establishment of limits in subsequent tests.

    Procedure:  Initially, advertise a single network on every port as
    per section 12.1.  Establish a traffic mesh between all advertised
    networks as per section 9.  Transmit IP packets through the DUT to
    all advertised networks at a rate well below the maximum throughput
    rate of the router, discovered in section 12.1. Ensure that packet
    loss is zero (indicating that packets are being forwarded to all
    advertised networks).

    Repeatedly advertise additional networks into the DUT and add these
    networks into the traffic mesh established through the DUT to the
                      FIB-based Router Performance       February, 2003

    advertised networks.  Stop when packet loss is detected, or when an
    ICMP destination unreachable message with a code value of 0 (network
    unreachable) or 6 (destination network unknown) is received.  This
    will indicate that the FIB has filled (or, that the DUT is unable to
    add additional entries into the FIB).  The test should continue in
    order to establish increasing packet loss as a consequence of
    increasing networks advertised into the DUT.

    Reporting Format:  The results should be reported as a single number
    (the maximum FIB size). generation.

   3.1 Interface Identifier

   The results should be backed up with a
    graph of the packet loss (on  interface identifier entry in the y-axis) versus FIB establishes the networks
    advertised into physical path
   for datagram forwarding.  If the DUT (on interface not active or down, the x-axis).

12.3 FIB Size Impact On Packet Forwarding Performance

    Objective:  The objective of this test  path
   is to evaluate  no  longer  available  and the impact entry SHOULD be removed from the FIB.
   Descriptions of
    FIB size interface identifiers are  contained  in  [MIB-BGP]  and composition upon
   [MIB-OSPF].  3.2 Route Optimization

   Route  optimization  seeks to minimize the packet forwarding performance overall effort on the part of

   draft-ietf-bmwg-fib-meth-02.txt                           October 2004

   the DUT.

    Procedure:  This iterative test changes both  router  to  forward  datagrams.   Optimization  has   three   basic

   - Route Aggregation - Route Flap Damping - Route Metrics

   Route  aggregation  seeks  to  minimize the size and
    composition number of entries in the FIB, and makes performance measurements FIB
   corresponding to a set of reachable address  prefixes.   These  prefixes
   could  be  contiguous or overlapping.  Methods for each
    iteration.  That is, route aggregation are
   described in [IDR].

   Route flap damping seeks to minimize unnecessary  re-generation  of  the
   FIB is set  based  on  unstable  routing  information.   Methods for route flap
   damping are described in [BGP-FLAP].

   Route metrics assign a relative weight or merit to a certain size and
    composition, then performance measurements  particular  routed
   path.   Descriptions  of  these metrics are made for packet
    throughput, latency, found in [MIB-BGP] and packet loss rate.  The FIB is incremented,
    then the tests [MIB-

   3.3 Routing Policies

   Routing policies are repeated, through to the maximum sized FIB
    supported by administrative restrictions or requirements on  the DUT.
   FIB.  The following code segment illustrates this methodology:

        set forward_table_compositions [List 16 22 24 realistic]

        for (forwarding_table_size = num_physical_interfaces;
             Forwarding_table_size <= maximum_forwarding_table_size;
             Forwarding_table_size += increment)
            foreach value forward_table_compositions_
                set_forwarding_table_composition $value
                measure_FIB-dependent_packet loss rate;
                measure_FIB-dependent_back-to-back frames;

    Reporting Format:  Results will take two major forms:

   - Access Control Lists - Route Filters

   Access  control  lists can be reported as a series used to explicitly allow or deny access to
   physical interfaces of [3]-style
    graphs, with a separate set network prefixes.  This can be done either on the
   basis of graphs for each individual FIB size /
    FIB composition test.  Results could be overlaid onto protocol addresses or entire prefixes.

   Route  filters are a single set of graphs.

    It may be useful to create protocol addresses or prefixes against which
   a set of graphs to aid in direct
    interpretation given route will be matched. The resulting  action  of this test.  One recommended graph would be, for a
    particular frame size,  a graph  match  will
   depend on the use of the appropriate metric on route filter.

4.0  Methodology

   The methodologies for determining the y-
                     FIB-based Router Performance       February, 2003

    axis (FIB-dependent throughput, FIB-dependent latency, FIB-dependent
    packet loss) versus effects of the three components of
   FIB size, with overlaid lines generation are still under investigation.  The authors look  to  the
   BMWG for each FIB

13. guidance, suggestions and constructive input.

   draft-ietf-bmwg-fib-meth-02.txt                           October 2004

   5. Security Considerations

   As  this  document  is  solely  for the purpose of providing metric
    methodology performance
   methodologies  and  describes  neither  a  protocol  nor  a   protocol's
   implementation;   therefore,   there   are  no  security  considerations
   associated with this document.


6. Informative References


   [IPROC]  Bradner, S., "The Internet Standards Process  --  Revision  3",
   BCP  9,  RFC 2026, October 1996.
    2  [FIB-TERM]  Trotter, G., " Terminology
   for Forwarding Information Base (FIB)  based  Router  Performance",  RFC 3222, December, 2001.
    3  Bradner, S., McQuaid,
   3222, December, 2001.  [METHOD]  Bradner, S., McQuaid, J., "Benchmarking
   Methodology for Network Interconnect  Devices",  RFC  2544,  March  1999
   [OSPF]   Moy,  J,  "OSPF  Version  2,"  RFC 2328, April 1998.  [MIB-BGP]
   Willis, S., Burrus, J., Chu, J. "Definitions of Managed Objects for  the
   Fourth  Version of the Border Gateway Protocol (BGP-4) using SMIv2," RFC
   1657, July 1994.  [MIB-OSPF] Baker, F.,  Colton,  R.,  "OSPF  Version  2
   Management  Information Base," RFC 1850, November 1995.  [IDR] Chen, E.,
   Stewart, J., "Benchmarking Methodology "A Framework for Network
       Interconnect Devices", Inter-Domain Route Aggregation," RFC 2544, March 1999

15. 2519,
   February  1999.   [BGP-FLAP]  Villamizar, C., Chandra, R., Govindan, R.,
   "BGP Route Flap Damping," RFC 2439, November 1998.

7. Acknowledgements

16. Author's Addresses

   The current authors would like to acknowledge  Guy  Trotter  of  Agilent
   Technologies (Canada) Inc.
    #2500 4710 Kingsway
    Burnaby, British Columbia
    V5H 4M2
    Phone:  for his work on the first edition of this draft.  His work
   has spurred the current authors to consider a broader set of performance
   criteria for FIB generation.

8. Author's Addresses

   Jeffrey  Dunn SI International 12012 Sunset Hills Road Suite 800 Reston,
   VA 20190-5869 USA Ph: +1 604 454 3516

Full Copyright Statement

    "Copyright (C) 703 234 6959 e-mail:

   Cynthia Martin SI  International  12012  Sunset  Hills  Road  Suite  800
   Reston, VA 20190-5869 USA Ph: +1 703 234 6962 e-mail: Cynthia.martin@si-

9.0 Intellectual Property Considerations

   The Internet Society (2002). All Rights Reserved.

    This document and translations IETF takes no position  regarding  the  validity  or  scope  of it may  any
   Intellectual  Property  Rights  or other rights that might be copied and furnished claimed to
    others, and derivative works that comment on or otherwise explain it
    or assist in its
   pertain to the implementation may be prepared, copied, published
    and distributed, in whole or in part, without restriction use of any
    kind, provided that the above copyright notice and this paragraph
    are included on all such copies and derivative works. However, technology described in this
   document itself may  or  the extent to which any license under such rights might or
   might not be modified in available; nor does it  represent  that  it  has  made  any
   independent  effort  to  identify  any way,  such as by removing  rights. Information on the copyright notice or references
   procedures with respect to rights in RFC documents can be found  in  BCP
   78 and BCP 79.

   Copies  of  IPR  disclosures  made  to  the Internet Society  IETF  Secretariat  and  any
   assurances of licenses to be made available, or other
    Internet organizations, except as needed for the purpose result of
    developing Internet standards in which case the procedures an attempt
   made  to  obtain  a  general  license  or permission for
    copyrights defined in the Internet Standards process must use of such

      draft-ietf-bmwg-fib-meth-02.txt                           October 2004

   proprietary  rights  by  implementers  or  users  of  this specification
   can   be
    followed,   obtained   from   the   IETF   on-line   IPR   repository  at

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

   9.1 IPR Disclosure Acknowledgement

   By submitting this Internet-Draft, I certify that any applicable  patent
   or  other than

                      FIB-based Router Performance       February, 2003

    The limited permissions granted above are perpetual IPR claims of which I am aware have been disclosed, and any of
   which I become aware will not be
    revoked by the disclosed, in accordance with RFC 3668.

10. Full Copyright Statement

   Copyright (C) The Internet Society or its successors or assigns. (2004).  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 is are  provided  on  an