CaltechAUTHORS
  A Caltech Library Service

Optimization flow control -- I: Basic algorithm and convergence

Low, Steven L. and Lapsley, David E. (1999) Optimization flow control -- I: Basic algorithm and convergence. IEEE/ACM Transactions on Networking, 7 (6). pp. 861-874. ISSN 1063-6692. http://resolver.caltech.edu/CaltechAUTHORS:LOWieeeacmtn99

[img]
Preview
PDF
See Usage Policy.

351Kb

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

Abstract

We propose an optimization approach to flow control where the objective is to maximize the aggregate source utility over their transmission rates. We view network links and sources as processors of a distributed computation system to solve the dual problem using a gradient projection algorithm. In this system, sources select transmission rates that maximize their own benefits, utility minus bandwidth cost, and network links adjust bandwidth prices to coordinate the sources' decisions. We allow feedback delays to be different, substantial, and time varying, and links and sources to update at different times and with different frequencies. We provide asynchronous distributed algorithms and prove their convergence in a static environment. We present measurements obtained from a preliminary prototype to illustrate the convergence of the algorithm in a slowly time-varying environment. We discuss its fairness property.


Item Type:Article
Additional Information:© Copyright 1999 IEEE. Reprinted with permission. Manuscript received December 7, 1998; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor S. Keshav. This work was supported by Melbourne IT, Melbourne, Victoria 3052, Australia. The work of S.H. Low was supported by the Australian Research Council under Grant S499705 and Grant A49930405. The work of D.I.E. Lapsley was supported by the Australian Commonwealth Government and ATERB under scholarships. The authors are grateful to F. Kelly, D. Mitra, J. Tsitsiklis, and A. Weiss for very helpful discussions. The first author would also like to thank B. Doshi and Y.T. Wang of Bell Laboratories, Lucent Technologies, for their hospitality during a visit in 1997 where part of this work was done.
Subject Keywords:Asynchronous algorithm, congestion pricing, convergence, gradient projection, optimization flow control
Record Number:CaltechAUTHORS:LOWieeeacmtn99
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:LOWieeeacmtn99
Alternative URL:http://dx.doi.org/10.1109/90.811451
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8579
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:21 Aug 2007
Last Modified:26 Dec 2012 09:40

Repository Staff Only: item control page