Internet Draft
     Benchmarking Working Group                                      J. Dunn
                                                                   C. Martin
                                                            SI International
     Expires: August 2005                                  February 14, 2005
     
     
     
           Methodology for Forwarding Information Base (FIB) based Router
                                     Performance
                          draft- -ietf-bmwg-fib-meth-03.txt
     
     
     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,
        and any of which I become aware will be disclosed, in accordance with
        RFC 3668.
     
        This document may only be posted in an Internet-Draft.
     
        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 August 14, 2005.
     
     Copyright Notice
     
           Copyright (C) The Internet Society (2004).  All Rights Reserved.
     
     Abstract
     
     
     
        The forwarding performance of an IP router is highly dependent  on
     the information in its forwarding information base.  This document
     
     
     
     Dunn, et al.             Expires August. 2005                  [Page 1]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
     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.
     
     The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
     "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
     document are to be interpreted as described in RFC-2119 Error! Reference
     source not found..
     
     Table of Contents
     
     
        Introduction......................................................3
        Terms of Reference................................................3
        1. Overview.......................................................4
           1.1. Interface Identifier......................................4
           1.2. Route Optimization........................................4
           1.3. Routing Policies..........................................5
        2. Base Methodology...............................................5
           2.1. Verdict Definitions.......................................6
           2.2. Basic Test Types..........................................6
              2.2.1. Route Addition.......................................6
              2.2.2. Route Deletion.......................................7
              2.2.3. Route Addition.......................................7
           2.3. Baseline Tests............................................7
        3. Test Suite Definition..........................................8
           3.1. Control Plane Test Group..................................8
              3.1.1. Interface Identifier Test Group......................8
              3.1.2. Route Optimization Test Group........................8
                 3.1.2.1. Route Aggregation Test Sub-Group................8
                 3.1.2.2. Route Flap Damping Test Sub-Group...............8
                 3.1.2.3. Route Metrics Test Sub-Group....................8
              3.1.3. Routing Policies Test Group..........................9
                 3.1.3.1. Access Control Lists Test Sub-Group.............9
                 3.1.3.2. Route Filters Test Sub-Group....................9
                 3.1.3.3. Static Routes Test Sub-Group....................9
           3.2. Data Plane Test Group....................................10
              3.2.1. Interface Identifier Test Group.....................10
              3.2.2. Route Optimization Test Sub-Group...................10
                 3.2.2.1. Route Aggregation Test Sub-Group...............10
                 3.2.2.2. Route Flap Damping Test Sub-Group..............10
                 3.2.2.3. Route Metrics Test Sub-Group...................10
              3.2.3. Routing Policies Test Group.........................10
                 3.2.3.1. Access Control Lists Test Sub-Group............10
                 3.2.3.2. Route Filters Test Sub-Group...................11
                 3.2.3.3. Static Routes Test Sub-Group...................11
        4. Security Considerations.......................................11
     
     
     Dunn, et al.             Expires August, 2005                  [Page 2]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
        5. Acknowledgments...............................................11
        6. References....................................................11
           6.1. Normative References.....................................11
        7. Author's Addresses............................................12
        Intellectual Property Statement..................................12
        Disclaimer of Validity...........................................13
        Copyright Statement..............................................13
        Acknowledgment...................................................13
     
          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).  [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.   The purpose of this document is to describe a
        methodology for measuring the impact of FIB generation from a 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 the RIB grows in size and complexity.
     
           This  document  utilizes  the  methodology  described  in
        [METHOD]  for measuring the FIB-dependent throughput, FIB-dependent
        latency  and  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 RIB sizes and compositions.
     
           Terms of Reference
     
           This document utilizes the methodologies for packet throughput,
        latency and loss measurements described in [METHOD].
     
           Definitions unique to this test methodology are covered in [FIB-
        TERM].
     
           The application of methodologies  described  in  this  document
        is  not limited  to  IP  forwarding;  however,  it  is  beyond the
        scope of this document to explicitly describe their application. In
        this document, use of the  term  IP is protocol version independent.
        Traffic, RIB and FIB may be IPv4, IPv6 or both.
     
     
     
     Dunn, et al.             Expires August, 2005                  [Page 3]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
     
     
        1. Overview
     
           The methodology described in this document is based on the precept
        that the FIB is formed from information in the RIB and, possibly,
        other configured variables.  The methodology is independent of the
        particulars associated with populating the RIB or setting these
        variables; however, this SHOULD be done using routing protocols,
        e.g., OSPF [OSPF].  RIB and FIB contents MAY be determined either
        through observing traffic forwarding or management information base
        (MIB)   queries.  For completeness, this determination SHOULD be made
        using both.  Generation of the FIB from the RIB based on three major
        components:
     
        o  Interface Identifier
     
        o  Route Optimization
     
        o  Routing Policies
     
           The following three sub-sections describe these components and
        their effect on FIB generation.
     
                                   1.1. Interface Identifier
     
           The interface identifier entry in the FIB establishes the physical
        path for datagram forwarding.  If the interface not active or down,
        the path is no longer available and the entry SHOULD be removed from
        the FIB.  Descriptions of interface identifiers are contained in
        [MIB-BGP] and [MIB-OSPF].
     
                                   1.2. Route Optimization
     
           Route optimization seeks to minimize the overall effort on the
        part of the  router  to  forward  datagrams.   Optimization has
        three basic components:
     
        o  Route Aggregation
     
        o  Route Flap Damping
     
        o  Route Metrics
     
           Route aggregation  seeks  to  minimize the number of entries in
        the FIB corresponding to a set of reachable address  prefixes.  These
     
     
     
     Dunn, et al.             Expires August, 2005                  [Page 4]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
        prefixes could be contiguous or overlapping.  Methods for route
        aggregation are described in [IDR].
     
           Route flap damping seeks to minimize unnecessary  re-generation
        of  the FIB  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  particular
        routed path.  Descriptions of these metrics are found in [MIB-BGP]
        and [MIB-OSPF].
     
                                   1.3. Routing Policies
     
           Routing policies are administrative restrictions or requirements
        on the FIB.  The take three major forms:
     
        o  Access Control Lists
     
        o  Route Filters
     
        o  Static Routes
     
           Access control lists can be used to explicitly allow or deny
        access to physical interfaces of network prefixes.  This can be done
        either on the basis of individual protocol addresses or entire
        prefixes.
     
           Route filters are a set of protocol addresses or prefixes against
        which a given route will be matched. The resulting action of a match
        will depend on the use of the route filter; however, it is usually an
        allow or deny action.
     
        Static routes are lists of protocol addresses explicitly associated
        with a given interface.  All datagrams with protocol addresses in
        these lists are automatically routed to the specified address.
     
     
     
        2. Base Methodology
     
        The test methodologies described in this document are grouped
        according to a hierarchy based on the effects of routing updates.
        This test hierarchy and nomenclature follow the ISO 9646 [ISO9646]
        formalism.  The basic test hierarchy is:
     
        1. Control Plane Group
     
     
     
     Dunn, et al.             Expires August, 2005                  [Page 5]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
            a. Interface Identifier Group
     
            b. Route Optimization Group
     
            c. Routing Policies Group
     
        2. Data Plane Group
     
            a. Interface Identifier Group
     
            b. Route Optimization Group
     
            c. Routing Policies Group
     
        Each test group or case MUST contain a test purpose.  Test cases MUST
        specify the SUT state, series of stimuli to bring it to that state,
        stimulating datagram and expected datagram.  All required field in
        all datagrams MUST be specified.  Verdicts are PASS, FAIL and
        INCONCLUSIVE. All verdicts MUST have the associated responses
        explicitly specified. The entirety constitutes a test suite.
     
                                   2.1. Verdict Definitions
     
        o  PASS û The required datagram was detected within the required time
           period.
     
        o  FAIL û The required datagram was not detected within the required
           time period.
     
        o  INCONCLUSIVE _ The SUT could not be brought into the specified
           state.
     
                                   2.2. Basic Test Types
     
        This methodology employees three basic test types:
     
        o  Route Addition
     
        o  Route Deletion
     
        o  Route Change
     
     2.2.1. Route Addition
     
        A route addition test case involves advertising a route to the SIT
        not contained in the RIB or FIB.  The test case produces a PASS
     
     
     
     Dunn, et al.             Expires August, 2005                  [Page 6]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
        verdict when the advertised route is reflected in the SUTÆs
        processing of data and control plane datagrams.
     
     2.2.2. Route Deletion
     
        A route addition test case involves ceasing to advertise a route to
        the SIT contained in the RIB or FIB.  The test case produces a PASS
        verdict when the deleted route is reflected in the SUTÆs processing
        of data and control plane datagrams.
     
     2.2.3. Route Addition
     
        A route addition test case involves advertising a route to the SIT
        contained in the RIB or FIB and associated with a different
        interface.  The test case produces a PASS verdict when the advertised
        route is reflected in the SUTÆs processing of data and control plane
        datagrams.
     
                                   2.3. Baseline Tests
     
        Given a FIB in a steady state and populated to a specified percentage
        of its maximum size, a measure of the maximum throughput [RFC 1242]
        constitutes a baseline for all additional measurements.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     Dunn, et al.             Expires August, 2005                  [Page 7]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
     
     
        3. Test Suite Definition
     
        Test Suite Purpose:  Determine the effect of route advertisements on
        the data and control plane responses of the SUT.
     
                                   3.1. Control Plane Test Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages.
     
     3.1.1. Interface Identifier Test Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages to the
        appropriate interface.
     
     3.1.2. Route Optimization Test Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages indicating route
        optimization.
     
     3.1.2.1. Route Aggregation Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages indicating route
        aggregation has been applied to FIB.
     
     3.1.2.2. Route Flap Damping Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages indicating route
        flap damping has been applied to FIB.
     
     3.1.2.3. Route Metrics Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages indicating route
        metrics have been applied to FIB.
     
     
     
     
     
     
     
     
     Dunn, et al.             Expires August, 2005                  [Page 8]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
     3.1.3. Routing Policies Test Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages based on routing
        policies.
     
     3.1.3.1. Access Control Lists Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages indicating access
        control lists have been applied to FIB.
     
     3.1.3.2. Route Filters Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages indicating route
        filters have been applied to FIB.
     
     3.1.3.3. Static Routes Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates with the appropriate control plane messages static routes
        have been applied to FIB.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     Dunn, et al.             Expires August, 2005                  [Page 9]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
     
     
                                   3.2. Data Plane Test Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by appropriately handling IP datagrams.
     
     3.2.1. Interface Identifier Test Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the appropriate interface.
     
     3.2.2. Route Optimization Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the appropriate interface after the
        specified period of time.
     
     3.2.2.1. Route Aggregation Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the aggregated appropriate interface.
     
     3.2.2.2. Route Flap Damping Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the appropriate interface based on the
        damping period.
     
     3.2.2.3. Route Metrics Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the appropriate interface.
     
     
     
     3.2.3. Routing Policies Test Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the appropriate interface based on routing
        policies.
     
     3.2.3.1. Access Control Lists Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the appropriate interface based on routing
        policies.
     
     
     Dunn, et al.             Expires August, 2005                 [Page 10]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
     3.2.3.2. Route Filters Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the appropriate interface based on routing
        policies.
     
     3.2.3.3. Static Routes Test Sub-Group
     
        Test Group Purpose:  Determine whether the SUT responds to route
        updates by routing data to the appropriate interface based on routing
        policies.
     
        4. Security Considerations
     
           As  this  document  is  solely  for the purpose of providing
        performance methodologies  and  describes  neither  a  protocol  nor
        a   protocol's implementation;   therefore,   there   are  no
        security  considerations associated with this document.
     
        5. Acknowledgments
     
          The current authors would like to acknowledge Guy Trotter of
        Agilent Technologies 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.
     
        6. References
     
                                   6.1. Normative References
     
        [IPROC] Bradner, S., "The Internet Standards Process -- Revision 3",
        BCP 9, RFC 2026, October 1996.
     
        [FIB-TERM] Trotter, G., "Terminology for Forwarding Information Base
        (FIB)  based  Router  Performance",  RFC 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.
     
     
     Dunn, et al.             Expires August, 2005                 [Page 11]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
        [IDR] Chen, E., Stewart, J., "A Framework for Inter-Domain Route
        Aggregation," RFC 2519, February 1999.
     
        [BGP-FLAP]  Villamizar, C., Chandra, R., Govindan, R., "BGP Route
        Flap Damping," RFC 2439, November 1998.
     
        [ISO9646] Conformance testing methodology and framework, ISO, 1994.
     
        [RFC 1242] Bradner, S., "Benchmarking Terminology for Network
       Interconnection Devices," RFC 1242, July 1991.
     
     
        7. Author's Addresses
     
        Jeffrey Dunn
        SI International
        12012 Sunset Hills Road
        Suite 800
        Reston, VA 20190-5869 USA
     
        Phone: _1 703 234 6959
        Email: Jeffrey.Dunn@si-intl.com
     
     
        Cynthia Martin
        SI International
        12012 Sunset Hills Road
        Suite 800
        Reston, VA 20190-5869 USA
     
        Phone: +1 703 234 6962
        Email: Cynthia.Martin@si-intl.com
     
     
     Intellectual Property Statement
     
        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.
     
     
     
     
     Dunn, et al.             Expires August, 2005                 [Page 12]


     Internet-Draft     draft-ietf-bmwg-fib-meth-03.txt             Feb 2005
     
     
        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.  By submitting this Internet-Draft, I certify that
        any applicable patent or other IPR claims of which I am aware have
        been disclosed, and any of which I become aware will be disclosed, in
        accordance with RFC 3668.
     
     Disclaimer of Validity
     
        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 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.
     
     Copyright Statement
     
        Copyright (C) The Internet Society (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.
     
     Acknowledgment
     
        Funding for the RFC Editor function is currently provided by the
        Internet Society.
     
     
     
     
     
     
     
     
     
     
     
     
     
     Dunn, et al.             Expires August, 2005                 [Page 13]