Parametric synthesis of the frequency ranges distribution plan using heuristic search algorithms

The development of the telecommunication systems leads to the need of solving frequencies ranges distribution problems for the used communication channels, considering the network throughput. The non-even distribution of the traffic, as well as the dependence of the throughput on the used frequency ranges should be considered. The requirements to the quality of service require dynamic tuning of the network parameters, and not only the redistribution of data flows in it, but also the redistribution of available frequency ranges, as well as their number. The aim of this study is to develop the algorithms of frequency ranges distribution synthesis, considering the target requests and the structure of the telecommunication network. For this an algorithm for determining the minimum number of different communication channels is implemented, which works by coloring the graph, and the flows on the edges of the graph are determined using greedy gradient algorithm, which optimizes the delay time and throughput coefficient. Moreover, the genetic algorithm for fine-tuning the initially designed frequency distribution plan is implemented. The performed computational experiments have shown the ability of the developed algorithm to find solutions for networks with up to 1000 nodes at a reasonable time. For networks of small dimension it is shown, that the genetic algorithm is able to improve the found solutions in terms of network throughput.

1. Yan D., Guo J., Wang L., Zhan P. SADR: Network status adaptive QoS dynamic routing for satellite networks. In: 2016 IEEE 13th International Conference on Signal Processing, 06–10 November 2016, Chengdu, China. IEEE; 2016. P. 1186–1190. https://doi.org/10.1109/ICSP.2016.7878015

2. Kasan H., Kim J. The case for dynamic bias in global adaptive routing. IEEE Computer Architecture Letters. 2021;20(1):38–41. https://doi.org/10.1109/LCA.2021.3061408

3. Bertsekas D.P., Gallager R.G. Data Networks. London: Prentice-Hall; 1992. 556 p.

4. Yen J.Y. Finding the k shortest loopless paths in a network. Management Science. 1971;17(11):712–716. https://doi.org/10.1287/mnsc.17.11.712

5. Arbelaez A., Mehta D., O’Sullivan B., Quesada L. A Constraint-Based Local Search for Edge Disjoint Rooted Distance-Constrained Minimum Spanning Tree Problem. In: Integration of AI and OR Techniques in Constraint Programming, 18–22 May 2015, Barcelona, Spain. Cham: Springer; 2015. P. 31–46. https://doi.org/10.1007/978-3-319-18008-3_3

6. Kuipers F., Van Mieghem P., Korkmaz T., Krunz M. An overview of constraint-based path selection algorithms for QoS routing. IEEE Communications Magazine. 2002;40(12):50–55. https://doi.org/10.1109/MCOM.2002.1106159

7. Taft-Plotkin N., Bellur B., Ogier R. Quality-of-service routing using maximally disjoint paths. In: 1999 Seventh International Workshop on Quality of Service, 31 May – 04 June 1999, London, UK. IEEE; 1999. P. 119–128. https://doi.org/10.1109/iwqos.1999.766485

8. Huang G.M., Zhu Sh. A fast distributed optimal routing algorithm for multicommodity large data networks. In: Proceedings of 9th International Parallel Processing Symposium, 25–28 April 1995, Santa Barbara, CA, USA. IEEE; 1995. P. 551–555. https://doi.org/10.1109/IPPS.1995.395985

9. Jain A., Chaudhari N.S. Genetic algorithm for optimizing network load balance in MPLS network. In: 2012 Fourth International Conference on Computational Intelligence and Communication Networks, 03–05 November 2012, Mathura, India. IEEE; 2012. P. 122–126. https://doi.org/10.1109/cicn.2012.119

10. Zhu Sh., Huang G.M. A new packet-loss minimization routing algorithm for ATM high-speed data networks. In: Proceedings of 35th IEEE Conference on Decision and Control, 13 December 1996, Kobe, Japan. IEEE; 2012. P. 287–292. https://doi.org/10.1109/CDC.1996.574317

11. Gaipov K., Tausnev D., Khodenkov S., et al. Heuristic Greedy-Gradient Route Search Method for Finding an Optimal Traffic Distribution in Telecommunication Networks. Algorithms. 2024;17(1):7. https://doi.org/10.3390/a17010007

12. Karakostas G. Faster approximation schemes for fractional multicommodity flow problems. ACM Transactions on Algorithms. 2008;4(1):13. https://doi.org/10.1145/1328911.1328924

13. Stanovov V., Akhmedova Sh., Semenkin E. Genetic Algorithm with Success History based Parameter Adaptation. In: Proceedings of the 11th International Joint Conference on Computational Intelligence, 17–19 September 2019, Vienna, Austria. SciTePress; 2019. P. 180–187. https://doi.org/10.5220/0008071201800187

14. Diestel R. Graph Theory. Berlin, Heidelberg: Springer; 2025. 455 p.