Subject: [Ans-research] Comments on primary metrics (Section 2.2)

From: Bozidar Radunovic <[email-masked]>
Date: Mon, 1 Dec 2003 16:51:31 +0100

Hello everyone,

We have some comments on the definitions of primary metrics, as stated in
Section 2.2 of draft-irtf-ans-scalability-notes-01.txt. We would like to
focus primarily on the rate based metrics. There are several rate based
primary metrics mentioned in Section 2.2: hop-by-hop throughput of a flow,
end-to-end throughput of a flow, throughput of the entire network, minimum
throughput over all flows and average throughput over all flows. We consider
here the latter three since they reflect the performance of a network as a
whole, unlike the first two metrics that reflect the performance of a single
flow.

THE MAIN POINTS:

We start by briefly introducing our main findings (originally presented in 
[7]), and then we describe them in details:

- Fairness is an important issue in network design and should be addressed
through an appropriate performance metric;

- Total, average and minimum rate metric do not account for fairness;
transport capacity also does not account for fairness

- Unlike the wired case, max-min fairness is not an appropriate metric for
wireless networks due to its inefficiency.

- Proportional fairness is the metric that evaluates both efficiency and
fairness; it makes a robust trade-off between efficiency and fairness, and it
is a standard metric in the scope of wired networking. It is thus an ideal
candidate for a primary performance metric.

UNFAIRNESS OF THE EXISTING PRIMARY METRICS:

As it is well known in the scope of wired networking, the above mentioned
throughput metrics do not guarantee fairness of rates. The most simple
example is the parking lot scenario (c.f. [1]), where it is easy to see that
the long flow will get zero rate when the objective is to maximize the total 
or the average throughput of a network. A striking consequence of this 
property is that using total or average throughput of a network as a metric 
may favor network protocols that yields to gross unfairness, and zero rates 
to flows with worse conditions. We have shown in [7] that the same property 
holds in wireless networks, regardless of the choice of physical interface.

The minimum throughput metric will not remedy fairness, since it takes into
account only the rate of the smallest flow. A simple example is again the
parking lot scenario, with an additional, independent link, that has a zero
rate. Since this independent link has the minimal rate in the system, the
rates of other links are irrelevant for the minimum rate metric, which leads
to the poor performance of the metric.

Transport capacity [8] is another well known throughput based performance 
metric that is not mentioned in Section 2.2. We show in [7] that this metric 
also suffers from unfairness, as it may yield to zero throughput of longer 
flow. Therefore, it is also not an appropriate metric from the fairness point 
of view.

To summarize the above, we believe that none of the primary metrics proposed 
in Section 2.2 are able to capture fairness property of network protocols. 
Since we believe fairness is a very important property, we would like to 
discuss more on this issue.

STATE OF THE ART IN FAIRNESS METRICS:

The two most well known metrics, originally defined in the scope of wired
networks, that incorporate fairness and efficiency, are max-min fairness [2],
and proportional fairness [3] (also known as a special case of utility
fairness). These metrics have already been used in design of contemporary
wireless protocols. In fact, it is shown in [4] and [7] that 802.11 terminals
achieve max-min fair rate allocation when accessing base-station in DCF mode.
Max-min fairness is also used in other wireless networking protocols, such as
[5,6], and it is often viewed as an appropriate performance metrics for
wireless networks that incorporate the aspect of fairness.

INEFFICIENCY OF MAX-MIN FAIRNESS:

However, as noticed in [4], max-min fairness leads to gross inefficiency in
802.11 networks. Namely, in the case of a network with a base-station and
several terminals connected to it, all nodes will have the equal rates, that
is the rate of the smallest flow. This is a phenomenon that does not occur in
wired networks, and is certainly not a desired property of a network. In [7]
we have analyzed the performance of max-min fairness on a generic model of
the physical layer of a wireless network that incorporate 802.11 networks,
but also other physical interfaces, such as CDMA or UWB (802.15.3a). We have
shown that this efficiency anomaly of max-min fairness is a consequence of the
wireless nature and not of the specific implementation of the physical
interface, hence it remains regardless of the underlying physical layer. The
conclusion is that max-min fairness is not an appropriate performance metric
for wireless networks.

PROPORTIONAL FAIRNESS:

In [7], we have also analyzed the performance of proportional fairness on
wireless networks. By inspecting numerous network topologies, we have shown
that proportional fairness maintains satisfactory level of both efficiency
and fairness of the resulting rate allocation. Therefore, we believe it is an
important candidate for a primary metric.

Bozidar Radunovic
Jean-Yves Le Boudec

EPFL - LCA/IC
1015-Lausanne
Switzerland

[1] J. Y. Le Boudec, "Rate adaptation, congestion control and fairness: a
tutorial", http://ica1www.epfl.ch/PS_files/LEB3132.pdf

[2] Bertsekas, Gallager, "Data Networks"

[3] F.P.Kelly, "Charging and rate control for elastic traffic", European
Transactions on Telecommunications, volume 8 (1997) pages 33-37.

[4] Berger-Sabbatel, Rousseau, Heusse, Duda, "Performance anomaly of
 802.11b", INFOCOM'03

[5] L. Tassiulas and S. Sarkar, "Max-min Fair Scheduling in Wireless
Networks", INFOCOM'02

[6] X. Huang and B. Bensaou, "On Max-min Fairness and Scheduling in Wireless
Ad-Hoc Networks: Analytical Framework and Implementation", MobiHoc'01

[7] Radunovic, Le Boudec, "Rate Performance Objectives of Multi-hop Wireless
Networks", to appear on INFOCOM'04,
http://lcawww.epfl.ch/Publications/Radunovic/TR03045.pdf

[8] Gupta, Kumar, "The Capacity of Wireless Networks", IEEE Trans. on
Information Theory, March 2000.

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

---

From: "[email-masked]" <[email-masked]>
Date: Mon, 1 Dec 2003 11:34:59 -0500 (EST)

Dear All,

Based on the input from the last meeting in Minneapolis, we have revised 
the
	draft-irtf-ans-scalability-definition-01.txt
and submitted to the IETF depository. You can access the revised version 
at:

http://wnl.ece.cornell.edu/Publications/draft-irtf-ans-scalability-definition-01.txt

Any future changes will go into -02 version.

Best,

Zygmunt.
==--==-===
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
Prof. Zygmunt J. Haas                    http://people.ece.cornell.edu/haas 
Wireless Networks Laboratory		 http://wnl.ece.cornell.edu
School of Electrical Engineering         
Cornell University			 tel: +1-607-255-3454
323 Frank Rhodes Hall			 fax: +1-607-255-9072
Ithaca, NY 14853			 e-mail: [email-masked]
U.S.A                             
	WNL web page: http://wnl.ece.cornell.edu
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-