Hostname: page-component-848d4c4894-r5zm4 Total loading time: 0 Render date: 2024-06-15T13:54:32.524Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal Multicommodity Flow Through the Complete Graph with Random Edge Capacities

Part of: Graph theory

Published online by Cambridge University Press:  14 July 2016

Mustafa Khandwawala  and
Rajesh Sundaresan
Mustafa Khandwawala*
Affiliation:
Indian Institute of Science
Rajesh Sundaresan*
Affiliation:
Indian Institute of Science
*
∗Postal address: Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore 560012, India.
∗Postal address: Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore 560012, India.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a multicommodity flow problem on a complete graph whose edges have random, independent, and identically distributed capacities. We show that, as the number of nodes tends to infinity, the maximum utility, given by the average of a concave function of each commodity flow, has an almost-sure limit. Furthermore, the asymptotically optimal flow uses only direct and two-hop paths, and can be obtained in a distributed manner.

Keywords

Complete graphfairnessmulticommodity flowrouteingutility

MSC classification

Secondary: 05C21: Flows in graphs 05C80: Random graphs 90C25: Convex programming
Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 1 , March 2010 , pp. 201 - 215
Copyright
Copyright © Applied Probability Trust 2010 

References

[1] Aldous, D. J., McDiarmid, C. and Scott, A. (2009). Uniform multicommodity flow through the complete graph with random edge-capacities. Operat. Res. Lett. 37, 299–302.Google Scholar
[2] Chayes, J. T. and Chayes, L. (1986). Bulk transport properties and exponent inequalities for random resistor and flow networks. Commun. Math. Phys. 105, 133–152.Google Scholar
[3] Georgiadis, L., Neely, M. J. and Tassiulas, L. (2006). Resource allocation and cross-layer control in wireless networks. Foundations Trends Networking 1, 1–144.Google Scholar
[4] Grimmett, G. and Kesten, H. (1984). First-passage percolation, network flows and electrical resistances. Z. Wahrscheinlichkeitsth. 66, 335–366.Google Scholar
[5] Grimmett, G. R. and Stirzaker, D. R. (1992). Probability and Random Processes, 2nd edn. Clarendon Press, Oxford.Google Scholar
[6] Kapoor, S. and Vaidya, P. M. (1996). Speeding up Karmarkar's algorithm for multicommodity flows. Math. Program. A 73, 111–127.Google Scholar
[7] Kelly, F. P., Maulloo, A. K. and Tan, D. K. H. (1998). Rate control for communication networks: shadow prices, proportional fairness and stability. J. Operat. Res. Soc. 49, 237–252.Google Scholar
[8] Leighton, T. et al. (1995). Fast approximation algorithms for multicommodity flow problems. J. Comput. System Sci. 50, 228–243.Google Scholar
[9] Megiddo, N. (1974). Optimal flows in networks with multiple sources and sinks. Math. Program. 7, 97–107.Google Scholar
[10] Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networking 8, 556–567.Google Scholar
[11] Zhang, Y. (2000). Critical behavior for maximal flows on the cubic lattice. J. Statist. Phys. 98, 799–811.Google Scholar