Name
Abstract | ||
|---|---|---|
Solving network flow problems is a fundamental component of traffic engineering and many communications applications, such as content delivery or multi-processor scheduling. While a rich body of work has addressed network flow problems in \"deterministic networks\" finding flows in \"stochastic networks\" where performance metrics like bandwidth and delay are uncertain and solely known by a probability distribution based on historical data, has received less attention. The work on stochastic networks has predominantly been directed to developing single-path routing algorithms, instead of addressing multi-path routing or flow problems. In this paper, we study constrained maximum flow problems in stochastic networks, where the delay and bandwidth of links are assumed to follow a log-concave probability distribution, which is the case for many distributions that could represent bandwidth and delay. We formulate the maximum-flow problem in such stochastic networks as a convex optimization problem, with a polynomial (in the input) number of variables. When an additional delay constraint is imposed, we show that the problem becomes NP-hard and we propose an approximation algorithm based on convex optimization. Furthermore, we develop a fast heuristic algorithm that, with a tuning parameter, is able to balance accuracy and speed. In a simulation-based evaluation of our algorithms in terms of success ratio, flow values, and running time, our heuristic is shown to give good results in a short running time. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/ICNP.2014.63 | Network Protocols |
Keywords | Field | DocType |
approximation theory,computational complexity,multipath channels,optimisation,processor scheduling,telecommunication network routing,NP-hard problem,approximation algorithm,constrained maximum flow,content delivery,convex optimization problem,heuristic algorithm,less attention,log-concave probability distribution,maximum flow problems,multipath routing,multiprocessor scheduling,network flow problems,performance metrics,single-path routing,stochastic networks,traffic engineering,Convex optimization,Maximum flow,QoS,Stochastic networks | Flow network,Approximation algorithm,Mathematical optimization,Stochastic optimization,Computer science,Stochastic neural network,Maximum flow problem,Multi-commodity flow problem,Minimum-cost flow problem,Drift plus penalty | Conference |
ISSN | Citations | PageRank |
1092-1648 | 1 | 0.34 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fernando A. Kuipers | 1 | 715 | 44.47 |
| yang song | 2 | 51 | 11.56 |
| Stojan Trajanovski | 3 | 78 | 7.09 |
| Ariel Orda | 4 | 2595 | 351.94 |