Abstract
Within the formalism of the multicommodity flow model, changes in the functional characteristics of a multiuser network after a damage are studied. To analyze the original limiting capabilities of the system, the maximum flow is calculated for each pair of vertices independently of other pairs. All edges of the corresponding minimum cut are removed, and the maximum possible flows for all origin–destination pairs are found in the damaged network and compared with their initial values. The detriment is evaluated for various cuts (structural damages). The influence of structural damages on the attainable values of the flow for each pair of vertices is investigated. This makes it possible to rank the origin–destination pairs by their susceptibility to the influence of damages from a given class. Ranking is performed on the basis of a bi-criteria detriment evaluation model. This approach is used for analyzing the vulnerability of large territory distributed systems, including telecommunication systems, communication and control systems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
A. A. Assad, “Multicommodity network flows: A survey,” Networks 8 (1), 37–91 (1978).
L. R. Ford and D. R. Fulkerson, Flows in Networks (Princeton Univ. Press, Princeton, 1962; Mir, Moscow, 1966).
P. A. Jensen and J. W. Barnes, Network Flow Programming, Wiley, New York, 1980.
Yu. E. Malashenko, I. A. Nazarova, and N. M. Novikova, “Vulnerability analysis of multi-polar networks after structural damages,” Inform. Primen. 13 (1), 56–71 (2019).
Yu. B. Germeier, Introduction to the Theory of Operations Research (Nauka, Moscow, 1971) [in Russian].
J. O. Royset and R. K. Wood, “Solving the bi-objective maximum-flow network-interdiction problem,” INFORMS J. Comput. 19 (2), 175–184 (2007).
M. Lalou, M. A. Tahraoui, and H. Kheddouci, “The critical node detection problem in networks: A survey,” Comput. Sci. Rev. 28, 92–117 (2018).
T. Gomes, C. Esposito, D. Hutchison, F. Kuipers, J. Rak, and M. Tornatore, “A survey of strategies for communication networks to protect against large-scale natural disasters,” Int. Workshop on Reliable Networks Design and Modeling (RNDM), 2016, pp. 11–22.
J. Ros and W. K. Tsai, “A lexicographic optimization framework to the flow control problem,” IEEE Trans. Inf. Theory 56, 2875–2886 (2010).
W. Ogryczak, H. Luss, M. Pioro, D. Nace, and A. Tomaszewski, “Fair optimization and networks: A survey,” J. Appl. Math. 25, 1–25 (2014).
R. A. Collado and D. Papp, “Network interdiction – models, applications, unexplored directions,” Rutcor Research Report, RRR 4–2012. Rutgers Center for Operations Research, Rutgers University, 2012.
J. Walteros and P. Pardalos, “Selected topics in critical element detection,” Optim. Its Appl. 71, 9–26 (2012).
T. N. Dinh snd M. T. Thai, “Assessing attack vulnerability in networks with uncertainty,” IEEE Conference on Computer Communications (INFOCOM), 2015, pp. 2380–2388.
A.Veremyev, O. A. Prokipyev, and E. L. Pasiliao, “Critical nodes for distance-based connectivity and related problems in graphs,” Networks 66 (3), 170–195 (2015).
P. Zhang and N. Fan, “Analysis of budget for interdiction on multicommodity network flows,” J. Glob. Opt. 67, 495–525 (2017).
Y. P. Aneja and X. Ke, “Multicommodity disconnecting set problem,” Int. J. Oper. Res. 4 (3), 165–171, (2007).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Translated by A. Klimontovich
Rights and permissions
About this article
Cite this article
Malashenko, Y.E., Nazarova, I.A. & Novikova, N.M. An Approach to the Analysis of Possible Structural Damages in Multicommodity Network Systems. Comput. Math. and Math. Phys. 59, 1562–1574 (2019). https://doi.org/10.1134/S0965542519090136
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542519090136