Open Access


Algorithms to Calculate the Most Reliable Maximum Flow in Content Delivery Network

Baili Zhang1, Keke Ling1,*, Pei Zhang2,3, Zhao Zhang2,3, Mingjun Zhong4
1 School of Computer Science and Engineering, Southeast University, Nanjing, 211189, China
2 State Key Laboratory of Smart Grid Protection and Control, Nanjing, 211106, China
3 Nari Group Corporation, Nanjing, 211106, China
4 Department of Computing Science, University of Aberdeen, Aberdeen, AB243UE, UK
* Corresponding Author: Keke Ling. Email:

Computer Systems Science and Engineering 2022, 41(2), 699-715.

Received 13 May 2021; Accepted 13 August 2021; Issue published 25 October 2021


Calculating the most reliable maximum flow (MRMF) from the edge cache node to the requesting node can provide an important reference for selecting the best edge cache node in a content delivery network (CDN). However, SDBA, as the current state-of-the-art MRMF algorithm, is too complex to meet real-time computing needs. This paper proposes a set of MRMF algorithms: NWCD (Negative Weight Community Deletion), SCPDAT (Single-Cycle Preference Deletion Approximation algorithm with Time constraint) and SCPDAP (Single-Cycle Preference Deletion Approximation algorithm with Probability constraint). NWCD draws on the “flow-shifting” algorithm of minimum cost and maximum flow, and further defines the concept of negative weight community. This algorithm continuously deletes the negative weight communities, which can increase reliability while keeping the flow constant in the residual graph. It is proven that when all negative weight communities are deleted, the corresponding maximum flow is the MRMF. SCPDAT tries to approach the optimal solution to the greatest extent possible within the limited time, while SCPDAP tries to reach the probability threshold in the shortest amount of time. Both of these adopt the strategy of first deleting single-cycle communities (which contribute more to the reliability with lower time cost). Experiments show that, compared with SDBA, NWCD combined with the probabilistic pruning achieves an order of magnitude improvement in time cost, while SCPDAT and SCPDAP demonstrate better time performance and increased applicability.


Content delivery network; uncertain graph; maximum flow; flow reliability

Cite This Article

B. Zhang, K. Ling, P. Zhang, Z. Zhang and M. Zhong, "Algorithms to calculate the most reliable maximum flow in content delivery network," Computer Systems Science and Engineering, vol. 41, no.2, pp. 699–715, 2022.

This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 726


  • 385


  • 0


Share Link

WeChat scan