Annals of Computer Science and Information Systems, Volume 20

DOI: http://dx.doi.org/10.15439/2019F85

Citation: Communication Papers of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 20, pages 29–36 (2019)

Full text

Abstract. 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.

References

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.