Exact and approximation algorithms for joint routing and flow rate optimization

• Autorzy: Junosza-Szaniawski Konstanty , Nogalski Dariusz

Identyfikatory

DOI

10.15439/2019F85

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

This paper addresses comparison of algorithms for a version of the NUM problem. The joint formulation of routing and transmission rate control within the multi-user and single-path setting is assumed within the NUM. Since problem is NP-hard, the efficient heuristics are designed, implemented and compared experimentally with other existing heuristics and exact linear programming solver. The linear approximation is applied for nonlinear utility function. The results of experiments demonstrate a trade-off between computing time and precision of goal value.

Słowa kluczowe

EN

mathematical programming; network optimization; problem; network utility maximization; rate allocation; congestion control; multi-rate computer networks; routing; NP-hard problem; heuristic algorithm

PL

programowanie matematyczne; optymalizacja sieci; problem; narzędzia sieciowe; alokacja stawek; kontrola zatorów; sieć komputerowa; problem NP-trudny; algorytm heurystyczny

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 20
• Strony: 29--36
• Opis fizyczny: Bibliogr. 19 poz.,

Twórcy

autor

Junosza-Szaniawski Konstanty

• Warsaw University of Technology, Faculty of Mathematics and Information Science, ul. Koszykowa 75, 00-662 Warszawa, Poland

autor

Nogalski Dariusz

• Military Communication Institute, C4I Systems Department, ul. Warszawska 22A, 05-130 Zegrze, Poland

Bibliografia

• 1. A. Amokrane, R. Langar, R. Boutaba, and G. Pujolle. Flow-based management for energy efficient campus networks. IEEE Transactions on Network and Service Management, 12(4):565–579, Dec 2015. 10.1109/TNSM.2015.2501398.
• 2. A.P. Bianzino, L. Chiaraviglio, M. Mellia, and J.L. Rougier. Grida: Green distributed algorithm for energy-efficient ip backbone networks. Computer Networks, 56(14):3219–3232, September 2012. https://doi.org/10.1016/j.comnet.2012.06.011.
• 3. M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle. Layering as optimization decomposition: A mathematical theory of network architectures. Proceedings of the IEEE, 95(1):255–312, Jan 2007. 10.1109/JPROC.2006.887322.
• 4. M. Drwal. Approximation algorithms for utility-maximizing network design problem. In Henry Selvaraj et al., editor, Progress in Systems Engineering: Proceedings of the Twenty-Third International Conference on Systems Engineering, volume 366 of Advances in Intelligent Systems and Computing. Springer International Publishing, Cham, 2015. https://doi.org/10.1007/978-3-319-08422-0-60.
• 5. S. Even, A. Itai, and A. Shamir. On the complexity of time table and multi-commodity flow problems. In IEEE, editor, 16th Annual Symposium on Foundations of Computer Science 13-15 October 1975, October 1975. 10.1109/SFCS.1975.21.
• 6. L. K. Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pages 24–31, Oct 1999. 10.1109/SFFCS.1999.814573.
• 7. N. Garg and J. Konemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 300–309, Nov 1998. 10.1109/SFCS.1998.743463.
• 8. X. Huang, T. Yuan, and M. Ma. Utility-optimized flow-level band-width allocation in hybrid sdns. IEEE Access, 6:20279–20290, 2018. 10.1109/ACCESS.2018.2820682.
• 9. P. Jaskóła, P. Arabas, and A. Karbowski. Simultaneous routing and flow rate optimization in energy-aware computer networks. International Journal of Applied Mathematics and Computer Science, 26(1):231–243, 2016. 10.1515/amcs-2016-0016.
• 10. F.P. Kelly, A.K. Maulloo, and D.K.H. Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49(3):237–252, March 1998. https://doi.org/10.1057/palgrave.jors.2600523.
• 11. J.W. Lee, M. Chiang, and R. A. Calderbank. Jointly optimal congestion and contention control based on network utility maximization. IEEE Communications Letters, 10(3):216–218, March 2006. 10.1109/LCOMM.2006.1603389.
• 12. T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787–832, November 1999.
• 13. M. Macit, V. C. Gungor, and G. Tuna. Comparison of qos-aware single-path vs. multi-path routing protocols for image transmission in wireless multimedia sensor networks. Ad Hoc Networks, 19:132 – 141, 2014. https://doi.org/10.1016/j.adhoc.2014.02.008.
• 14. J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking, 8(5):556–567, Oct 2000. 10.1109/90.879343.
• 15. M. E. Pfetsch and Ch. Liebchen. Multicommodity flows and column generation. In Lecture Notes. Zuse Institute Berlin, 2006.
• 16. P. R. Satav and P. M. Jawandhiya. Review on single-path multi-path routing protocol in manet: A study. In 2016 International Conference on Recent Advances and Innovations in Engineering (ICRAIE), pages 1–7, Dec 2016. 10.1109/ICRAIE.2016.7939514.
• 17. J. Wang, L. Li, S.H. Low, and J.C. Doyle. Cross-layer optimization in tcp/ip networks. IEEE/ACM Transactions on Networking, 13(3):582–595, June 2005. 10.1109/TNET.2005.850219.
• 18. M. Wang, C. W. Tan, W. Xu, and A. Tang. Cost of not splitting in routing: Characterization and estimation. IEEE/ACM Transactions on Networking, 19(6):1849–1859, Dec 2011. 10.1109/TNET.2011.2150761.
• 19. W. Wang, M. Palaniswami, and S. H. Low. Application-oriented flow control: Fundamentals, algorithms and fairness. IEEE/ACM Transactions on Networking, 14(6):1282–1291, Dec 2006. 10.1109/TNET.2006.886318.

Uwagi

1. Track 1: Artificial Intelligence and Applications

2. Technical Session: 12th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).