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 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{{\Delta }^2‐\delta }{2{\Delta }^2‐\delta \Delta ‐\Delta }\}$ , 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.