Capacity, stability and flows in large-scale random networks
Christina Peraki, S.D. Servetto · Manufacturing Engineer · 2005
We consider the problem of determining the maximum stable throughput in large-scale random networks under a fairness constraint. The networks are modeled as random unit-disk graphs, and the problem of throughput stability is formulated as one finding the maximum value of a multicommodity flow problem. In this paper, we construct upper and lower bounds on the value of that multicommodity flow problem which, together, provide a tight characterization of an optimal solution to within constants independent of network size. These results contain as a special case those of Gupta and Kumar for random networks, for which an entirely new derivation is provided, using only elementary counting and discrete probability tools.