Weitere Artikel dieser Ausgabe durch Wischen aufrufen
Solving the shortest path and min-cut problems are key in achieving high-performance and robust communication networks. Those problems have often been studied in deterministic and uncorrelated networks both in their original formulations as well as in several constrained variants. However, in real-world networks, link weights (e.g., delay, bandwidth, failure probability) are often correlated due to spatial or temporal reasons, and these correlated link weights together behave in a different manner and are not always additive, as commonly assumed.
In this paper, we first propose two correlated link weight models, namely (1) the deterministic correlated model and (2) the (log-concave) stochastic correlated model. Subsequently, we study the shortest path problem and the min-cut problem under these two correlated models.
We prove that these two problems are NP-hard under the deterministic correlated model, and even cannot be approximated to arbitrary degree in polynomial time. However, these two problems are solvable in polynomial time under the (constrained) nodal deterministic correlated model, and can be solved by convex optimization under the (log-concave) stochastic correlated model.
Cui W, Stoica I, Katz RH. Backup path allocation based on a correlated link failure probability model in overlay networks. In: Proceedings of IEEE ICNP; 2002. pp. 236–45.
Kuipers FA, Dijkstra F. Path selection in multi-layer networks. Comput Commun. 2009;32(1):78–85. CrossRef
Savage S, Collins A, Hoffman E, Snell J, Anderson T. The end-to-end effects of internet path selection. ACM SIGCOMM Comput Commun Rev. 1999;29:289–99. CrossRef
Kostić D, Rodriguez A, Albrecht J, Vahdat A. Bullet: high bandwidth data dissemination using an overlay mesh. ACM SIGOPS Oper Syst Rev. 2003;37:282–97. CrossRef
Kim K, Venkatasubramanian N. Assessing the impact of geographically correlated failures on overlay-based data dissemination. In: Proceedings of IEEE GLOBECOM; 2010. pp. 1–5.
Trajanovski S, Kuipers FA, Ilic A, Crowcroft J, Van Mieghem P. Finding critical regions and region-disjoint paths in a network. IEEE/ACM Trans Netw. 2015;23(3):908–21. CrossRef
Kuipers F, Beshir A, Orda A, Van Mieghem P. Impairment-aware path selection and regenerator placement in translucent optical networks. In: Proceedings of the 18th IEEE international conference on network protocols (ICNP); 2010. pp. 11–20.
Buldyrev SV, Parshani R, Paul G, Stanley HE, Havlin S. Catastrophic cascade of failures in interdependent networks. Nature. 2010;464(7291):1025–8. CrossRef
Strand J, Chiu AL, Tkach R. Issues for routing in the optical layer. IEEE Commun Mag. 2001;39:81–7. CrossRef
Dantzig G, Fulkerson DR. On the max-flow min-cut theorem of networks. Linear Inequal Relat Syst. 2003;38:225–31.
Lorenz DH, Orda A. QoS routing in networks with uncertain parameters. IEEE/ACM Trans Netw. 1998;6(6):768–78. CrossRef
Guérin RA, Orda A. Qos routing in networks with inaccurate information: theory and algorithms. IEEE/ACM Trans Netw. 1999;7(3):350–64. CrossRef
Papagiannaki K, Moon S, Fraleigh C, Thiran P, Tobagi F, Diot C. Analysis of measured single-hop delay from an operational backbone network. Proc IEEE INFOCOM. 2002;2:535–44.
Mohtashami Borzadaran GR, Mohtashami Borzadaran HA. Log-concavity property for some well-known distributions. Surv Math Appl. 2011;6:203–19. MathSciNet
Kuipers FA, Yang S, Trajanovski S, Orda A. Constrained maxmum flow in stochastic networks. In: Proceedings of IEEE ICNP, North Carolina, USA; 2014. pp. 397–408.
Yuan S, Varma S, Jue JP. Minimum-color path problems for reliability in mesh networks. Proc IEEE INFOCOM. 2005;4:2658–69.
Garey MR, Johnson DS. Computers and intractability: a guide to the theory of np-completeness. New York: W. H. Freeman & Co.; 1979. MATH
Van Mieghem P, Kuipers FA. Concepts of exact QoS routing algorithms. IEEE/ACM Trans Netw. 2004;12(5):851–64. CrossRef
Van Mieghem P. Paths in the simple random graph and the Waxman graph. Probab Eng Inf Sci. 2001;15(04):535–55. MATH
Cormen TH, Stein C, Rivest RL, Leiserson CE. Introduction to algorithms. 2nd ed. Cambridge: MIT Press; 2001. MATH
Tamir A. Polynomial formulations of min-cut problems. Manuscript. Department of Statistic and Operations Research, Tel Aviv University, Israel; 1994.
Kuipers FA, Van Mieghem P. The impact of correlated link weights on QoS routing. Proc IEEE INFOCOM. 2003;2:1425–34.
Lee H-W, Modiano E, Lee K. Diverse routing in networks with probabilistic failures. IEEE/ACM Trans Netw. 2010;18(6):1895–907. CrossRef
Yang S, Kuipers FA. Traffic uncertainty models in network planning. IEEE Commun Mag. 2014;52(2):172–7. CrossRef
Chekuri CS, Goldberg AV, Karger DR, Levine MS, Stein C. Experimental study of minimum cut algorithms. In: Proceedings of the eighth annual ACM-SIAM symposium on discrete algorithms (SODA); 1997. p. 324–33.
- Optimization problems in correlated networks
Fernando A. Kuipers
- Springer International Publishing
Neuer Inhalt/© ITandMEDIA