[Iccrg] Proposal for ICCRG operations

[Xiaoliang (David) Wei]

Thanks, all. About the benchmark, I have been thinking about a few questions 
that might be interesting in the process of designing a benchmark:

1. Who is expected to use the benchmark?
    My understanding is that there may be different groups of users that are 
interested in different properties of a congestion control algorithm.
    For example, distributed computation applications would prefer a low 
latency of the worst flow (this is max-min fairness). Data transfer users 
may emphasize on a higher average throughput. Media servers would like to 
have stable delay... As Linux allows users to select their preferred 
congestion control algorithm, network administrator is capable to select 
different algorithms in their private network, based on the major 
applications they have. In this case, I think it make sense to provide a few 
different metrics for different users.
    If the benchmark is to be used to identify a TCP candidate for 
standardization, we probably need to consider even more: incremental 
deployability (interaction with Reno), the impact of the algorithm to the 
network (link loss rate, queue fluctuation) and etc. In this case, we may 
also want to measure the realistic workload in Internet and feed it back to 
the benchmark.

2. Who will perform the benchmark tests, and how?
    As the e2e mailing list talking on some strange behaviors in NCSU's 
performance evaluation due to some buggy implementation, it brings up the 
problem that the same congestion control algorithm may perform very 
different because of a bug in the implementation, or even a hardware defect 
in the testbed.
    I think it will be better if we can have a standard hardware testbed 
that can repeatedly evaluate an implementation of congestion control 
algorithm. So, the protocol designers can iterate the process of 
design->implementation->testing and make sure that their algorithms are 
correctly evaluated. In this issue, I think WAN-in-Lab may help (at least 
partially) as a standard testing platform, if we can build a automatic 
testing system based on it.

just my 2 cents.

-David

Xiaoliang (David) Wei             Graduate Student in CS at Caltech
http://www.davidwei.org
====================================================
----- Original Message ----- 
From: "Lachlan Andrew" <lachlan.andrew at gmail.com>
To: "Michael Welzl" <michael.welzl at uibk.ac.at>
Cc: "Aaron Falk" <falk at isi.edu>; "Steven Low" <slow at caltech.edu>; "Lachlan 
Andrew" <lachlan at cs.caltech.edu>; "iccrg" <iccrg at cs.ucl.ac.uk>; "Pei Cao" 
<cao at theory.stanford.edu>; "David Wei" <weixl at cs.caltech.edu>; 
<tmrg-interest at icsi.berkeley.edu>
Sent: Friday, February 03, 2006 3:57 PM
Subject: Re: [Iccrg] Proposal for ICCRG operations


Greetings all,

On 03 Feb 2006 09:32:27 +0100, Michael Welzl <michael.welzl at uibk.ac.at> 
wrote:
> So, the index should contain:
>
> * normalized throughput
> * loss
> * fairness (let's use the Jain Fairness Index)
>
> It could then look something like this:
>
> WI = (T*t + L*l + F*f) / 3
>
> where WI is "Welzl Index" (tm)   ;-)
> T is normalized throughput
> L is normalized loss
> F is the Jain fairness index (which is already a value
> in the 0..1 range)

A good way to summarise throughput and fairness is just to take the
*harmonic* mean of the flows' throughputs instead of the arithmetic
mean (or equivalently, the aggregate througput).  That corresponds to
measuring the mean time to transfer a given number of bytes, which is
the quantity actually observed by an application.

This metric avoids the arbitraryness both of using a sum or product,
with the problem of  selecting weightings, and also of Jain's index.
(If one flow out of many is starved, Jain's index can still report
high "fairness", but the harmonic mean of rates goes to zero
highlighting the problem.)  Similarly, if one flow (or protocol) is
unable to achieve a high rate, Jain's index says it is "unfair" for
another to out-perfom it.  The harmonic mean correctly indicates that
rates  0.5 and 1  are better than rates 0.5 and 0.5 (but less good
than 0.75 and 0.75).

(Trying to maximise the harmonic mean of the rates is just a special
case of "utility maximisation", using  alpha=2 in Mo and Walrand's
alpha-fairness framework.  It could be argued that this utility
function is itself arbitrary, but it seems less so than summing
thoughput and "fairness".)

Combining throughput and fairness of throughput can be done
systematically, since they both just reflect the average rates.  A
bigger challenge is incorporating loss/delay and the other metrics
Wesley Eddy mentioned (stability, convergence time etc).  For file
transfers, it could be argued that these only matter insofar as they
affect the total transfer times.  This applies to both long- and
short-lived flows (but not to real-time flows).  However, there is
still a problem of how to weight the times:  The transfer time of each
short flow should get less weight than a long flow, but weighting them
in proportion to the amount of data may put too little weight on them.

Cheers,
Lachlan

--
Lachlan Andrew  Dept of Computer Science, Caltech
Phone: +1 (626) 395-8820    Fax: +1 (626) 568-3603