On generalized max-min rate allocation and distributed convergence algorithm for packet networks

Y. Thomas Hou, Shivendra S. Panwar, Henry H.Y. Tzeng

Research output: Contribution to journalArticle

Abstract

This paper considers the fundamental problem of bandwidth allocation among flows in a packet-switched network. The classical max-min rate allocation has been widely regarded as a fair rate allocation policy. But, for a flow with a minimum rate requirement and a peak rate constraint, the classical max-min policy no longer suffices to determine rate allocation since it is not capable of supporting either the minimum rate or the peak rate constraint from a flow. In this paper, we generalize the theory of the classical max-min rate allocation with the support of both the minimum rate and peak rate constraints for each flow. Additionally, to achieve generalized max-min rate allocation in a fully distributed packet network, we present a distributed algorithm that uses a feedback-based flow control mechanism. Our design not only offers a fresh perspective on flow marking technique, but also advances the state-of-the-art flow marking technique favored by other researchers. We provide proof that such a distributed algorithm, through asynchronous iterations, will always converge to the generalized max-min rate allocation under any network configuration and any set of link distances. We use simulation results to demonstrate the fast convergence property of the distributed algorithm.

Original languageEnglish (US)
Pages (from-to)401-416
Number of pages16
JournalIEEE Transactions on Parallel and Distributed Systems
Volume15
Issue number5
DOIs
StatePublished - May 2004

Keywords

  • Centralized algorithm
  • Convergence
  • Distributed algorithm
  • Flow control
  • Max-min rate allocation
  • Minimum rate
  • Packet networks
  • Peak rate

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On generalized max-min rate allocation and distributed convergence algorithm for packet networks'. Together they form a unique fingerprint.

  • Cite this