B-Neck: A Distributed and Quiescent Max-Min Fair Algorithm

Mozo Velasco, Alberto and López Presa, Jose Luis and Fernández Anta, Antonio (2011). B-Neck: A Distributed and Quiescent Max-Min Fair Algorithm. In: "The 10th IEEE International Symposium on Network Computing and Applications 2011", 25/08/2011 - 27/08/2011, Cambridge, Massachusetts USA. ISBN 978-1-4577-1052-0.

Description

Title: B-Neck: A Distributed and Quiescent Max-Min Fair Algorithm
Author/s:
  • Mozo Velasco, Alberto
  • López Presa, Jose Luis
  • Fernández Anta, Antonio
Item Type: Presentation at Congress or Conference (Article)
Event Title: The 10th IEEE International Symposium on Network Computing and Applications 2011
Event Dates: 25/08/2011 - 27/08/2011
Event Location: Cambridge, Massachusetts USA
Title of Book: Proceedings of the 10th IEEE International Symposium on Network Computing and Applications 2011
Date: 2011
ISBN: 978-1-4577-1052-0
Subjects:
Freetext Keywords: Max-mix fairness , distributed algorithm , quiescence
Faculty: E.U. de Informática (UPM)
Department: Arquitectura y Tecnología de Computadores [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (221kB) | Preview

Abstract

The problem of fairly distributing the capacity of a network among a set of sessions has been widely studied. In this problem, each session connects via a single path a source and a destination, and its goal is to maximize its assigned transmission rate (i.e., its throughput). Since the links of the network have limited bandwidths, some criterion has to be defined to fairly distribute their capacity among the sessions. A popular criterion is max-min fairness that, in short, guarantees that each session i gets a rate λi such that no session s can increase λs without causing another session s' to end up with a rate λs/ <; λs. Many max-min fair algorithms have been proposed, both centralized and distributed. However, to our knowledge, all proposed distributed algorithms require control data being continuously transmitted to recompute the max-min fair rates when needed (because none of them has mechanisms to detect convergence to the max-min fair rates). In this paper we propose B-Neck, a distributed max-min fair algorithm that is also quiescent. This means that, in absence of changes (i.e., session arrivals or departures), once the max min rates have been computed, B-Neck stops generating network traffic. Quiescence is a key design concept of B-Neck, because B-Neck routers are capable of detecting and notifying changes in the convergence conditions of max-min fair rates. As far as we know, B-Neck is the first distributed max-min fair algorithm that does not require a continuous injection of control traffic to compute the rates. The correctness of B-Neck is formally proved, and extensive simulations are conducted. In them, it is shown that B-Neck converges relatively fast and behaves nicely in presence of sessions arriving and departing.

More information

Item ID: 11653
DC Identifier: http://oa.upm.es/11653/
OAI Identifier: oai:oa.upm.es:11653
Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6038580&contentType=Conference+Publications&sortType%3Dasc_p_Sequence%26filter%3DAND(p_IS_Number%3A6038577)%26rowsPerPage%3D50
Deposited by: Memoria Investigacion
Deposited on: 29 Nov 2012 09:32
Last Modified: 20 Apr 2016 19:40
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM