Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well

摘要

Maximal flows reach at least a 1/2 approximation of the maximum flow in client-server networks. By adding only 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 / achieves an approximationrnto the maximum flow of min{l, △~2-δ/2△~2-δ△-△}, and this result is sharp for any given integers S and A. 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.