INTERNET-DRAFT                                                  J. Dunn
     Internet Draft
     Benchmarking Methodology Working Group                                      J. Dunn
                                                                   C. Martin
Expires: May 2005
                                                            SI International
                                                           October 2004
     Expires: August 2005                                  February 14, 2005

           Methodology for Forwarding Information Base (FIB) based Router
                                     Performance

                     draft-ietf-bmwg-fib-meth-02.txt
                          draft- -ietf-bmwg-fib-meth-03.txt

     Status of this Memo

   "By

        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." 3668.

        This document is an Internet-Draft and is may only be posted in full conformance  with  all
   provisions of Section 10 of RFC2026 [IPROC]. 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.

        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.
             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
     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
        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]  [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 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  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.

2.

           Terms Of 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]. [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.

3.

        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.

   3.1

                                   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].  3.2

                                   1.2. Route Optimization

           Route optimization seeks to minimize the overall effort on the
        part of

   draft-ietf-bmwg-fib-meth-02.txt                           October 2004 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
        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].

   3.3 [MIB-OSPF].

                                   1.3. Routing Policies

           Routing policies are administrative restrictions or requirements
        on the FIB.  The take two 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.

4.0  Methodology

   The methodologies for determining the effects of the three components filter; however, it is usually an
        allow or deny action.

        Static routes are lists of
   FIB generation protocol addresses explicitly associated
        with a given interface.  All datagrams with protocol addresses in
        these lists are still under investigation.  The authors look automatically routed to the
   BMWG for guidance, suggestions and constructive input.

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

   5. Security Considerations

   As specified address.

        2. Base Methodology

        The test methodologies described in this document  is  solely  for are grouped
        according to a hierarchy based on the purpose effects of providing performance
   methodologies routing updates.
        This test hierarchy and  describes  neither  a  protocol  nor nomenclature follow the ISO 9646 [ISO9646]
        formalism.  The basic test hierarchy is:

        1. Control Plane Group
            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   protocol's
   implementation;   therefore,   there 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  no  security  considerations PASS, FAIL and
        INCONCLUSIVE. All verdicts MUST have the associated with this 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
        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.

        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.

     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.

                                   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.

     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. Informative 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 "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. 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, F.,Colton, R., "OSPF Version 2 Management
        Information Base," RFC 1850, November 1995.

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

7. Acknowledgements

   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

        [ISO9646] Conformance testing methodology and framework, ISO, 1994.

        [RFC 1242] Bradner, S., "Benchmarking Terminology for FIB generation.

8. 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 Ph: +1

        Phone: _1 703 234 6959 e-mail: jeffrey.dunn@si-intl.com
        Email: Jeffrey.Dunn@si-intl.com

        Cynthia Martin
        SI International
        12012 Sunset Hills Road
        Suite 800
        Reston, VA 20190-5869 USA Ph:

        Phone: +1 703 234 6962 e-mail: Cynthia.martin@si-
   intl.com

9.0
        Email: Cynthia.Martin@si-intl.com

     Intellectual Property Considerations 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.

        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

      draft-ietf-bmwg-fib-meth-02.txt                           October 2004 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.

   9.1 IPR Disclosure Acknowledgement
        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.

10. Full 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.

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