Why locally-fair maximal flows in client-server networks perform well

Kenneth A. Berman () and Chad Yoshikawa ()
Additional contact information
Kenneth A. Berman: University of Cincinnati
Chad Yoshikawa: University of Cincinnati

Journal of Combinatorial Optimization, 2011, vol. 22, issue 3, No 9, 426-437

Abstract: Abstract Maximal flows reach at least a 1/2 approximation of the maximum flow in client-server networks. By adding 1 additional time round to any distributed maximal flow algorithm we show how this 1/2-approximation can be improved on bounded-degree networks. We call these modified maximal flows ‘locally fair’ since there is a measure of fairness prescribed to each client and server in the network. Let N=(U,V,E,b) represent a client-server network with clients U, servers V, network links E, and node capacities b, where we assume that each capacity is at least one unit. Let d(u) denote the b-weighted degree of any node u∈U∪V, Δ=max {d(u)|u∈U} and δ=min {d(v)|v∈V}. We show that a locally-fair maximal flow f achieves an approximation to the maximum flow of $\min\{1,\frac{\varDelta^{2}-\delta}{2\varDelta^{2}-\delta\varDelta-\varDelta}$ }, and this result is sharp for any given integers δ and Δ. This results are of practical importance since local-fairness loosely models the steady-state behavior of TCP/IP and these types of degree-bounds often occur naturally (or are easy to enforce) in real client-server systems.

Keywords: Distributed flow algorithms; Oblivious routing; Network algorithms; Maximal flow (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9321-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:22:y:2011:i:3:d:10.1007_s10878-010-9321-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9321-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().