CaltechAUTHORS
  A Caltech Library Service

Counter-intuitive throughput behaviors in networks under end-to-end control

Tang, Ao and Wang, Jiantao and Low, Steven H. (2006) Counter-intuitive throughput behaviors in networks under end-to-end control. IEEE/ACM Transactions on Networking, 14 (2). pp. 355-368. ISSN 1063-6692. http://resolver.caltech.edu/CaltechAUTHORS:TANiatnet06

[img]
Preview
PDF
See Usage Policy.

519Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:TANiatnet06

Abstract

It has been shown that as long as traffic sources adapt their rates to aggregate congestion measure in their paths, they implicitly maximize certain utility. In this paper we study some counter-intuitive throughput behaviors in such networks, pertaining to whether a fair allocation is always inefficient and whether increasing capacity always raises aggregate throughput. A bandwidth allocation policy can be defined in terms of a class of utility functions parameterized by a scalar a that can be interpreted as a quantitative measure of fairness. An allocation is fair if alpha is large and efficient if aggregate throughput is large. All examples in the literature suggest that a fair allocation is necessarily inefficient. We characterize exactly the tradeoff between fairness and throughput in general networks. The characterization allows us both to produce the first counter-example and trivially explain all the previous supporting examples. Surprisingly, our counter-example has the property that a fairer allocation is always more efficient. In particular it implies that maxmin fairness can achieve a higher throughput than proportional fairness. Intuitively, we might expect that increasing link capacities always raises aggregate throughput. We show that not only can throughput be reduced when some link increases its capacity, more strikingly, it can also be reduced when all links increase their capacities by the same amount. If all links increase their capacities proportionally, however, throughput will indeed increase. These examples demonstrate the intricate interactions among sources in a network setting that are missing in a single-link topology.


Item Type:Article
ORCID:
AuthorORCID
Tang, Ao0000-0001-6296-644X
Low, Steven H.0000-0001-6476-3048
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Manuscript received October 21, 2004; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor N. Shroff. [Posted online: 2006-04-18] The authors thank G. Varghese of UCSD for a helpful discussion that motivated the work on throughput–fairness tradeoff, and L. Li and W. Luo of Caltech for helpful discussions.
Subject Keywords:Fairness, flow control, optimization, throughput
Issue or Number:2
Record Number:CaltechAUTHORS:TANiatnet06
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:TANiatnet06
Alternative URL:http://dx.doi.org/10.1109/TNET.2006.872552
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7698
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:22 Mar 2007
Last Modified:13 Mar 2018 21:12

Repository Staff Only: item control page