Abstract
This paper provides compound algorithm for Unrestorable Flow Optimisation (UFO) problem formulated for computer networks protected by p-cycles, created on the base of mathematical model and solution approaches proposed in our complementary paper [1]. Components of the algorithm have been selected carefully and then experimentally tested in order to compose the best final algorithm. Results of the wide computer tests on common benchmarks have been also presented as well as some practical conclusions following from the research made.
Chapter PDF
Similar content being viewed by others
References
Smutnicki, A., Smutnicki, C.: Flow Optimization in Survivable Networks Based on p-Cycles. Submitted for International Conference on Computational Science (ICCS 2009) (2009)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)
Smutnicki, A.: Branch-and-bound Algorithm for Multiple Knapsack Problem in the Unrestorable Flow Optimisation Problem. In: Proceedings of 23rd IAR Workshop on Advanced Control and Diagnosis, Coventry, UK (November 2008)
Pióro, M., Medhi, D.: Routing, Flow, and Capacity Design in Communication and Computer Networks. Elsevier Inc., San Francisco (2004)
Schupke, D.: An ILP for Optimal p-Cycle Selection Without Cycle Enumeration. In: Proceedings of Eighth IFIP Working Conference on Optical Network Design and Modelling (ONDM 2004), Ghent, Belgium (February 2004)
Wu, B., Yeung, K., Xu, S.: ILP Formulation for p-Cycle Construction Based on Flow Conservation. In: Proceedings of Global Telecommunications Conference, 2007. GLOBECOM 2007, Washington, DC, USA, pp. 2310–2314 (November 2007)
Doucette, J., He, D., Grover, W.D., Yang, O.: Algorithmic Approaches for Efficient Enumeration of Candidate p-Cycles and Capacitated p-Cycle Network Design. In: Proceedings of Fourth International Workshop on Design of Reliable Communication Networks, pp. 212–220 (October 2003)
Chang, L., Lu, R.: Finding Good Candidate Cycles for Efficient p-Cycle Network Design. In: Proceedings of 13th International Conference on Computer Communications and Networks, pp. 321–326 (October 2004)
Zhang, H., Yang, O.: Finding Protection Cycles in DWDM Networks. In: Proceedings of IEEE International Conference on Communications, pp. 2756–2760 (2002)
Lo, K., Habibi, D., Rassan, A., Phung, Q.V., Nguyen, H.N., Kang, B.: A Hybrid p-Cycle Search Algorithm for Protection in WDM Mesh Networks. In: Proceedings of ICON 2006. 14th IEEE International Conference on Networks, pp. 1–6 (September 2006)
Grover, W.D.: Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET, and ATM Networking. Prentice Hall PTR, New Jersey (2003)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Pusblishers, Dordrecht (1997)
Orlowski, S., Pióro, M., Tomaszewski, A., Wessäly, R.: SNDlib 1.0 — Survivable Network Design Library. In: Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium (April 2007), http://sndlib.zib.de
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Smutnicki, A. (2009). An Algorithm for Unrestored Flow Optimization in Survivable Networks Based on p-Cycles. In: Allen, G., Nabrzyski, J., Seidel, E., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds) Computational Science – ICCS 2009. Lecture Notes in Computer Science, vol 5544. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01970-8_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-01970-8_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01969-2
Online ISBN: 978-3-642-01970-8
eBook Packages: Computer ScienceComputer Science (R0)