Subject: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology from the BMWG Goals

From: Kevin Dubray <[email-masked]>
Date: Wed, 21 Jan 2004 11:53:47 -0500

This is an action item from the BMWG meeting at the 58th IETF.

When originally undertaken, the FIB performance benchmarking effort was 
considered a critical,
constituent component of the convergence benchmarking body of work.

Subsequent WG support for the FIB benchmarking methodology document has 
been underwhelming.
The last known state of the FIB Benchmarking Methodology draft can be 
found here:

    http://www.watersprings.org/pub/id/draft-ietf-bmwg-fib-meth-01.txt

Commentary from its most recent last call can be found here:
 
http://www1.ietf.org/mail-archive/working-groups/bmwg/current/msg00477.html

Please voice your opinion as to whether or not you feel it is critical 
for the BMWG to support
this work.  Send your comments to this list or to the 
chairs.([email-masked], [email-masked])

If you would like serve as the editor for this effort, please indicate 
your desire to the
chairs.

This WG Last Call period will extend through 02 Feb 04.  At the end of 
the period, the chairs
will make a recommendation to the ADs, based on the WG's input AND the 
ability to identify
a document editor.

_______________________________________________
bmwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/bmwg

---

From: [email-masked]
Date: Wed, 21 Jan 2004 13:52:32 -0500

Kevin,

I think a FIB Benchmarking standard to measure FIB scaling would be very
useful to industry.  This specific methodology  may have low interest
because it is rather narrow in test coverage, having only 3 test cases as
follow:
1. Baseline Measurements.  
2. Maximum FIB Size Test
3. FIB Size Impact On Packet Forwarding Performance

Test 1 is less preferred in practice to the already defined Forwarding Rate
test and Test 3 has been obviated by the architecture of modern routers.
Test 2 is the one very useful to industry.  I recommend that a small team be
formed to determine if there are a number of interesting test cases around
Test 2 that could be developed in order to resurrect this work.

Scott

-----Original Message-----
From: Kevin Dubray [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 11:54 AM
To: [email-masked]
Cc: Bert Wijnen; david.kessens
Subject: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

---

From: [email-masked]
Date: Wed, 21 Jan 2004 13:52:32 -0500

Kevin,

Scott

-----Original Message-----
From: Kevin Dubray [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 11:54 AM
To: [email-masked]
Cc: Bert Wijnen; david.kessens
Subject: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

---

From: "Allan Sand" <[email-masked]>
Date: Wed, 21 Jan 2004 17:04:53 -0500

I'm new to this forum, so excuse me if I have breached protocol.  I would
like to add the following for consideration.

Ideally a route update should have no impact on the forwarding plane except
as pertains to the prefix(es) being updated (added, withdrawn or modified).
The ideal behaviour is the router should continue to forward traffic to all
'other' prefixes. In practice, the behaviour of routers is far from ideal
and the affect of a route update (on the forwarding plane) is characterized
by the number of unavailable prefixes and the duration of the 'impact'.
Unavailable here means not being able to forward to a prefix. 

The factors affecting the number of unavailable prefixes and the duration of
that state can be grouped between those related to control plane
implementation and those impacted by forwarding plane implementation.
Control plane implementation focuses on control traffic throughput (i.e.
processing control messages that determine convergence time) under normal,
high and overload states (for control messages). Hence the control plane
networking algorithms include different implementations of hold-off timers
and rate controls and SPF speedup algorithms.  

The factors affecting the number of prefixes impacted (i.e. unavailable for
forwarding) and duration of impact is more of a forwarding plane
implementation byproduct; the main engineering issues being prefix lookup
speed and maximum prefix size.  In most forwarding plane implementations,
the number of prefixes impacted is determined by the type of prefix lookup
algorithm. One common algorithm is a Patricia Tree (PT), a form of trie data
base. Another common algorithm is prefix hashing.

Prefixes are listed in a PT as nodes and branches. A route update which
results in a branch type prefix being added to the FIB has no impact on
looking up other prefixes. In other words, a route update which adds a new
network prefix will have no impact on forwarding to other prefixes. However,
a route update which adds a node type prefix, may result in an inability to
forward to that node prefix and all its branches for the period of time it
takes to rearrange that particular node/branch hierarchy in the PT. 2nd
generation routers using PT come in at 20 prefixes/ms update rate.  

In addition, routers use clever techniques in the control plane to reduce
the number of prefixes that eventually need to be sent (updated) to the FIB.
One such technique is prefix incremental updates. With this technique only
changed prefixes are updated, rather than say a wholesale dump of the RIB.
Another technique is to use a 2 stage lookup scheme in the FIB. This
technique reduces the number of prefixes to 1, when N prefixes share a
common alternate next hop.

In summary, FIB benchmark tests should include a measure of the impact
(number of unavailable prefixes and duration) resulting form route updates.
The test cases (i.e. what prefixes end up getting changed as a result of the
route update) need to be carefully designed not to favour any one router
control and forwarding plane implementation. But rather should be designed
to mimic real network configurations and scenarios.  

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Wednesday, January 21, 2004 1:53 PM
To: [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

Kevin,

Scott

-----Original Message-----
From: Kevin Dubray [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 11:54 AM
To: [email-masked]
Cc: Bert Wijnen; david.kessens
Subject: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology from
the BMWG Goals

---

From: "Allan Sand" <[email-masked]>
Date: Wed, 21 Jan 2004 17:04:53 -0500

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Wednesday, January 21, 2004 1:53 PM
To: [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

Kevin,

Scott

-----Original Message-----
From: Kevin Dubray [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 11:54 AM
To: [email-masked]
Cc: Bert Wijnen; david.kessens
Subject: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology from
the BMWG Goals

---

From: [email-masked]
Date: Wed, 21 Jan 2004 17:26:38 -0500

<http://www.ietf.org/internet-drafts/draft-ietf-bmwg-conterm-05.txt> Allan,
 
The BMWG already has adopted the following work items for Route Convergence:
 
Terminology for Benchmarking BGP Device Convergence in the Control Plane
(66758 bytes)
 
<http://www.ietf.org/internet-drafts/draft-ietf-bmwg-ospfconv-intraarea-07.t
xt> Benchmarking Basic OPSF Single Router Control Plane Convergence (30710
bytes)
 
<http://www.ietf.org/internet-drafts/draft-ietf-bmwg-ospfconv-applicability-
03.txt> Benchmarking Applicability for Basic OSPF Convergence (21766 bytes)
 
<http://www.ietf.org/internet-drafts/draft-ietf-bmwg-igp-dataplane-conv-meth
-01.txt> Benchmarking Methodology for IGP Data Plane Route Convergence
(31086 bytes)
 
<http://www.ietf.org/internet-drafts/draft-ietf-bmwg-igp-dataplane-conv-term
-02.txt> Terminology for Benchmarking IGP Data Plane Route Convergence
(61350 bytes)
 
<http://www.ietf.org/internet-drafts/draft-ietf-bmwg-igp-dataplane-conv-app-
01.txt> Benchmarking Applicability for IGP Data Plane Route Convergence
(12280 bytes)
 
The intention of the FIB Performance work item was to benchmark FIB Scaling
and Forwarding Performance with the FIB scaled.
 
Scott

-----Original Message-----
From: Allan Sand [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 5:05 PM
To: [email-masked]'; [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

-----Original Message----- 
From: [email-masked] [ mailto:[email-masked]
<mailto:[email-masked]> ] 
Sent: Wednesday, January 21, 2004 1:53 PM 
To: [email-masked]; [email-masked] 
Cc: [email-masked]; [email-masked] 
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals 

Kevin, 

follow: 

Scott 

-----Original Message----- 
From: Kevin Dubray [ mailto:[email-masked] <mailto:[email-masked]>
] 
Sent: Wednesday, January 21, 2004 11:54 AM 
To: [email-masked] 
Cc: Bert Wijnen; david.kessens 
Subject: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology from
the BMWG Goals 

    http://www.watersprings.org/pub/id/draft-ietf-bmwg-fib-meth-01.txt
<http://www.watersprings.org/pub/id/draft-ietf-bmwg-fib-meth-01.txt>  

http://www1.ietf.org/mail-archive/working-groups/bmwg/current/msg00477.html
<http://www1.ietf.org/mail-archive/working-groups/bmwg/current/msg00477.html

_______________________________________________ 
bmwg mailing list 
[email-masked] 
https://www1.ietf.org/mailman/listinfo/bmwg
<https://www1.ietf.org/mailman/listinfo/bmwg>  

_______________________________________________ 
bmwg mailing list 
[email-masked] 
https://www1.ietf.org/mailman/listinfo/bmwg
<https://www1.ietf.org/mailman/listinfo/bmwg>

---

From: [email-masked]
Date: Wed, 21 Jan 2004 17:26:38 -0500

Scott

-----Original Message-----
From: Allan Sand [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 5:05 PM
To: [email-masked]'; [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

-----Original Message----- 

Kevin, 

follow: 

Scott

---

From: [email-masked]
Date: Thu, 22 Jan 2004 19:13:31 -0500

Allan,
 
Are you suggesting that we add an additional test case to
<http://www.ietf.org/internet-drafts/draft-ietf-bmwg-igp-dataplane-conv-meth
-01.txt> Benchmarking Methodology for IGP Data Plane Route Convergence that
has a defined distribution of subnets?

Scott

-----Original Message-----
From: Allan Sand [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 6:41 PM
To: [email-masked]'
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

Thanks Scott
I had a quick read.  I did not find a definition for the various reference
networks which included a discussion of the relationship between network,
path and node convergence time as it related to network address themes. The
term addressing themes refers to various arrangements of subnetting. As I
noted in my discussion routers have incorporated special speedup techniques
which sometimes favour a particular addressing theme. Can you point to that
discussion.
Thanks
Allan 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Wednesday, January 21, 2004 5:27 PM
To: Sand, Allan [CAR:0S03:EXCH]; [email-masked];
[email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

 

 

 
 
Scott

-----Original Message-----
From: Allan Sand [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 5:05 PM
To: [email-masked]'; [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

-----Original Message----- 

Kevin, 

follow: 

Scott

---

From: [email-masked]
Date: Thu, 22 Jan 2004 19:13:31 -0500

Allan,

Scott

-----Original Message-----
From: Allan Sand [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 6:41 PM
To: [email-masked]'
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

Thanks Scott

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Wednesday, January 21, 2004 5:27 PM
To: Sand, Allan [CAR:0S03:EXCH]; [email-masked];

 

 

 
 
Scott

-----Original Message-----
From: Allan Sand [mailto:[email-masked]]
Sent: Wednesday, January 21, 2004 5:05 PM
To: [email-masked]'; [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [bmwg] WG Last Call: Removal of FIB Benchmarking Methodology
from the BMWG Goals

-----Original Message----- 

Kevin, 

follow: 

Scott