Subject: Routing Table Impact on Forwarding Performance of Routers

From: Kevin Dubray <[email-masked]>
Date: Fri, 17 Mar 2000 16:59:11 -0500

Workplan Proposal: Routing Table Impact on Forwarding Performance of Routers

Guy Trotter, Agilent Technologies

March 2000

This memo proposes the development of a standard practice designed to measure
the forwarding performance of a router as a function of the routing table
installed within the router.  It is proposed to develop both terminology and
methodology documents for these tests.  Both documents shall be prepared in
collaboration with the Benchmarking Methodology Working Group (bmwg) of the
Internet Engineering Task Force (IETF).

This effort is proposed as being an incremental way to quickly develop a
methodology to measure one aspect of a router's performance.  Subsequent
incremental methodologies could add a methodology to examine the impact of
route flaps on routers, table convergence time and so on.

1. Effort's Motivation

High performance routers are both being shipped and developed by a large
number of equipment manufacturers.  These routers support many high bandwidth
pipes; the ability to forward packets at wire-speed; and the ability to support
extremely large routing tables.  Routing tables supported on these routers
range far beyond the typical 65,000 to 70,000 routes found on routers within
the Internet today: possible table sizes may extend into the hundreds of
thousand of routes.

When a router forwards packets, it performs a longest length prefix match
between the destination address contained within the received IP packet and
against the entries within the routing table.  Numerous algorithms and
hardware implementations have been developed to speed this lookup process -
ranging from distributed routing tables through to route caches.  The speed
of the route lookup process is dependent upon both the absolute number of
network prefixes within the routing table as well as the distribution of
network prefixes through the range of prefix lengths.  It is critical that
the impact of routing tables upon the forwarding performance of a router is
measured by ensuring that traffic is delivered to the router that fully
exercises the routing table.

Measurements of routers has found a direct correlation between the forwarding
performance of a router and both the size and distribution of network
prefixes within these routing tables.  

There does not currently exist a standard methodology for measuring the
performance of a router dependent upon the routing table installed within the
router.  The lack of a standardized methodology makes the comparison between
different routers difficult.

2. Effort's Goals

The objective of this work is to create a methodology document describing how
the packet forwarding performance of a router can be measured on the basis of
the size and structure of the routing table installed within the router.  The
work will describe how routing tables should be constructed within the router
under test, the type of traffic to transmit through the router that will
effectively exercise the routing table, and how performance measurements on
this traffic can be made.

It is anticipated that the performance measurements can be leveraged from the
work already documented within RFC 2544.

An accompanying terminology document will be developed in advance of the
methodology document.

3. Plan and Milestones

As mentioned, the goal will be to produce both a terminology document and
methodology document.

3.1 Terminology Document  

As with all efforts taking place within the bmwg, a terminology document will
be initially created, with a methodology document to follow.  The terminology
document will describe the terms or concepts related to the test methodology.
Some of the terms that will be described will be:

        - routing table
        - network prefix
        - prefix length
        - routing table size

These terms are commonly used within the router testing community, but may need
to be defined to specify their precise application within this testing context.

Other terms that may be defined:

        - route-loaded throughput

                Packet throughput based upon the size and structure of a
                routing table.

        - route-loaded latency

                Packet latency based upon the size and structure of a
                routing table.

        - route-loaded packet loss

                Packet loss based upon the size and structure of a
                routing table.

The terminology document will follow the framework established in RFC 1242,
including for each term a definition, discussion, measurement units, issues,
and list of related terms.

3.1.1 Terminology Milestones

The following timetable is proposed:

    April, 2000   - First draft of terminology document submitted to the bmwg
    August, 2000  - Working group last call on benchmarking terminology
                    Internet Draft

3.2 Methodology Documents

Upon completion of the terminology document, work will progress to create the
methodology document.  The same general layout as RFC 2544 will be used as a
format for the methodology document.  Test procedures defined within RFC 2544
will be leveraged or referenced where necessary or appropriate.

3.2.1 Methodology Milestones

The following timetable is proposed:

    July, 2000      - first draft of methodology document submitted to the bmwg
    December, 2000  - working group last call on benchmarking methodology
                      Internet Draft