Development and analysis of the diacoptic method of interdomain routing with load balancing in a telecommunication network

Authors

DOI:

https://doi.org/10.30837/pt.2018.1.01

Abstract

In this paper, the diacoptical method of inter-area routing with load balancing in a telecommunication network was proposed. The method allows to increase the scalability of routing solutions in comparison with the centralized approach without reducing the efficiency of the network, estimated by the maximum value of link load threshold. The method involves the decomposition of the general routing problem in a multi-area network into several routing subtasks of smaller size that can be solved for each individual area followed by combining the solutions obtained for the whole telecommunication network. The foundation of the method is a flow-based routing model based on the implementation of the concept of Traffic Engineering and focused on minimizing the maximum value of link load threshold. The results of the analysis confirmed the operability of the method on a variety of numerical examples and demonstrated the full correspondence of the efficiency of the obtained diacoptical routing solutions to the centralized approach. The advantage of the proposed method is also the absence of the need to coordinate routing solutions received on subnetworks, which positively affects both the time of solving the set task and the amount of service traffic circulated in the network associated with the transfer of data on the state of network areas and coordinating information.

Author Biographies

Oleksandr Vitalijovych Lemeshko, Kharkiv National University of Radio Electronics

Andrii Yevhenovych Ilіashenko, Kharkiv National University of Radio Electronics

Olena Serhiivna Nevzorova, Kharkiv National University of Radio Electronics

References

VEGESHNA, SH. Kachestvo obsluzhivanija v setjah IP. Per. s anlg. [Quality of service on IP networks]. M.: Iz-datel'skij dom «Vil'jams», 2003. (In Russian)

BARREIROS, M.; LUNDQVIST, P. QOS-Enabled Networks: Tools and Foundations. Wiley Series on Communications Networking & Distributed Systems, 2nd Edition, Wiley, 2016.

HALABI, S. Internet Routing Architectures (2nd Edition). Cisco Press, 2000.

MEDHI, D.; RAMASAMY, K. Network Routing, Second Edition: Algorithms, Protocols, and Architectures, (The Morgan Kaufmann Series in Networking) 2nd Edition. Cambridge, MA, USA: Elsevier Inc., 2018. 1018 p.

GOL'DSHTEJN, A.B.; GOL'DSHTEJN, B.S. Tehnologija i protokoly MPLS. [MPLS technology and protocols]. SPb.: BHV, 2005. (In Russian).

OLIFER, V.G.; OLIFER, N.A. Komp'juternye seti. Principy, tehnologii, protokoly: uchebnik dlja vuzov. 3-e izd. [Computer networks. Principles, technologies, protocols: a textbook for universities. 3rd ed]. SPb.: Piter, 2006. (In Russian).

CISCO NETWORKING ACADEMY. Routing Protocols Companion Guide. Pearson Education. Cisco press, 2014.

MISRA, S.; GOSWAMI, S. Network Routing: Fundamentals, Applications, and Emerging Technologies 1st Edition. Wiley, 2017.

POPOVSKIJ, V.V.; LEMESHKO, A.V.; MEL'NIKOVA, L.I.; ANDRUSHKO, D.V. “Obzor i sravnitel'nyj analiz osnovnyh modelej i algoritmov mnogoputevoj marshrutizacii v mul'tiservisnyh telekommunikacionnyh setjah [Overeview and comparative analysis of the main models and algorithms for multipath routing in multiservice telecommunication networks] // Prikladnaja radiojelektronika, tom.4., vyp. № 4, p. 372-382. (In Russian).

LEE, G.M.; CHOI, J.S. “A survey of multipath routing for traffic engineering,” Springer-Verlag, p. 635-661, 2005. URI:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.9976&rep=rep1&type=pdf

SEGALL, A. “The Modeling of Adaptive Routing in Data Communication Networks,” IEEE Transactions on Communications, vol. 25, p. 85–95, january 1977. DOI: https://doi.org/10.1109/TCOM.1977.1093715.

RAK, J. Resilient Routing in Communication Networks (Computer Communications and Networks), 1st edition. Springer, 2015.

LEMESHKO, O.V.; YEREMENKO, O.S. “Dynamics Analysis of Multipath QoS-Routing Tensor Model with Support of Different Flows Classes,” 2016 International Conference on Smart Systems and Technologies (SST), 12-14 Oct. 2016, Josip Juraj Strossmayer University of Osijek, Croatia, p. 225-230. DOI: 10.1109/SST.2016.7765664.

LEMESHKO, O.; YEREMENKO, O. “Dynamic presentation of tensor model for multipath QoS-routing,” 2016 13th International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET), 23-26 Feb. 2016, Lviv, Ukraine. 2016, p. 601-604. URI: http://openarchive.nure.ua/handle/document/2147.

LEMESHKO, O.V.; YEREMENKO, O.S. “Dinamіchna model' marshrutizacії pri zabezpechennі jakostі obslugovuvannja za pokaznikom jmovіrnostі svoєchasnoї dostavki paketіv [Dynamic routing model while maintaining quality of service on the indicator of the probability of timely delivery of packages],” XІ Mіzhnarodna naukovo-tehnіchna konferencіja "Problemi telekomunіkacіj" PT-2017: Zbіrnik materіalіv konferencії, 2017, K.: KPІ іm. Іgorja Sіkors'kogo. 2017, p. 285-287. URI: http://conferenc.its.kpi.ua/proc/article/viewFile/101570/96782. (In Ukrainian).

LEMESHKO, О.; DROBOT, O. “A Mathematical Model of Multipath QoS-based Routing in Multiservice Networks,” Proceedings of International conference Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET), 28 Feb.-4 March 2006, Lviv-Slavsko. IEEE, 2006, p. 72-74. DOI: https://doi.org/10.1109/TCSET.2006.4404448.

LIN, S.C.; AKYILDIZ, I.F.; WANG, P.; LUO, M. “QoS-aware Adaptive Routing in Multi-layer Hierarchical Software Defined Networks: A Reinforcement Learning Approach,” 2016 IEEE International Conference on Services Computing (SCC), 27 June-2 July 2016, San Francisco, CA, USA. IEEE, 2016, p. 25-33. DOI: https://doi.org/10.1109/SCC.2016.12.

ROMANOV, O.I.; NESTERENKO, M.M.; VERES, L.A.; HORDASHNYK, Y.S. “IMS: Model and calculation method of telecommunication network's capacity,” 2017 IEEE International Conference on Information and Telecommunication Technologies and Radio Electronics (UkrMiCo), 11-15 Sept. 2017, Odessa, Ukraine. IEEE, 2017, p. 1-4. DOI: https://doi.org/10.1109/UkrMiCo.2017.8095412.

WRIGHT, B. Inter-area routing, path selection and traffic engineering. white paper. Data Connection Limited, 2003.

VUTUCURY, S. Multipath routing mechanisms for traffiv engineering and quality of service in the Internet. PhD dissertation, University of California, USA, 2001.

VUTUKURY, S.; GARCIA-LUNA-ACEVES, J.J. “A traffic engineering approach based on minimum-delay routing,” 2000 IEEE Ninth International Conference on Computer Communications and Networks, 16-18 Oct. 2000, Las Vegas, USA. IEEE, 2000, p. 42-47. DOI: https://doi.org/10.1109/ICCCN.2000.885468.

SEOK, Y.; LEE, Y.; CHOI, Y.; KIM, C. “Dynamic Constrained Traffic Engineering for Multicast Routing,” Information Networking: Wired Communications and Management, vol. 2343, p. 278-288, Sept. 2002. DOI: https://doi.org/10.1007/3-540-45803-4_26.

WANG, Y.; WANG, Z. “Explicit routing algorithms for Internet Traffic Engineering,” Proceedings Eight International Conference Computer Communications and Networks, 11-13 Oct. 1999, Boston, USA. IEEE, 1999, p. 582-588. DOI: https://doi.org/10.1109/ICCCN.1999.805577.

LEMESHKO, O.; VAVENKO, T.; OVCHINNIKOV, K. “Design of multipath routing scheme with load balancing in MPLS-network,” 2013 IEEE XIIth International Conference THE EXPERIENCE OF DESIGNING AND APPLICATION OF CAD SYSTEMS IN MICROELECTRONICS, 19-23 February 2013, Polyana-Svalyava-(Zakarpattya), UKRAINE. IEEE, 2013, p. 211-213.

MERSNI, A.; ILYASHENKO, A.; VAVENKO, T. “Complex Optimality Criterion for Load Balancing with Multipath Routing in Telecommunications Networks of Nonuniform Topology,” 14th International Conference The Experience of Designing and Application of CAD System in Microelectronic (CADSM), 21-25 February 2017, Polyana-Svalyava (Zakarpattya), Ukraine. IEEE, 2017, p. 100-104. DOI: https://doi.org/10.1109/CADSM.2017.7916095.

MERSNI, A.; ILYASHENKO, A. E. “Complex criterion of load balance optimality for multipath routing in telecommunication networks of nonuniform topology,” Telecommunications and Radio Engineering, vol. 76, issue 7, p. 579-590, 2017. DOI: https://doi.org/10.1615/TelecomRadEng.v76.i7.20.

LEMESHKO, O.; YEREMENKO, O.; NEVZOROVA, O. “Hierarchical Method of Inter-Area Fast Rerouting,” Transport and Telecommunication Journal, vol. 18, n. 2, p. 155-167, June 2017. DOI: https://doi.org/10.1515/ttj-2017-0015.

YEVSYEYEVA, O.JU. “Reshenie zadachi ierarhichesko-koordinacionnoj marshrutizacii v telekommunikacionnyh setjah metodom predskazanija vzaimodejstvija [Solution of the problem of hierarchical coordination routing in telecommunication networks using the interaction prediction method],” Otkrytye informacionnye i komp'juternye integrirovannye tehnologii, vyp. 21, p. 102-111, 2003. (In Russian).

YEREMENKO, O.; LEMESHKO, O.; NEVZOROVA, O.; HAILAN, A.M. “Method of hierarchical QoS routing based on network resource reservation,” 2017 IEEE First Ukraine Conference on electrical and computer engineering (UKRCON), 29 May-2 June 2017, Kyiv, Ukraine. IEEE, 2017, p. 971-976. DOI: https://doi.org/10.1109/UKRCON.2017.8100393.

LEMESHKO, A.V.; HAJLAN, A.M.; SEMENJAKA, M.V. “Model' i metod ierarhicheskoj marshrutizacii na osnove rezervirovanija resursov v seti IP/IntSev [Model and method of hierarchical routing based on the resource reservation in the IP/IntSev network],” Radiotehnika: Vseukr. mezhved. nauch.-tehn. sb., vyp. 163, p. 79-84, 2010. (In Russian).

NEVZOROVA, YE.S.; AROUS, K.M.; SALAKH, M.T.R. “Method for hierarchical coordinated multicast routing in a telecommunication network,” Telecommunication and Radio Engineering, vol. 75, p. 1137-1151, 2016. DOI: https://doi.org/10.1615/TelecomRadEng.v75.i13.10.

LEMESHKO, A.V.; HAJLAN, A.M. “Mnogourovnevoe upravlenie trafikom v seti MPLS–TE DiffServ na osnove koordinacionnogo principa prognozirovanija vzaimodejstvij [Multi-level traffic management in the MPLS-TE DiffServ network based on the coordination principle of interaction prediction],” Problemy telekomunіkacіj, n.1(1), p. 35–44, 2010. URI: http://pt.journal.kh.ua/2010/1/1/101_lemeshko_traffic.pdf. (In Russian).

YEVSYEYEVA, O. “Diakoptical approach in telecommunication engineering,” 2010 IEEE Modern problems of radio engineering, telecommunication and computer science (TCSET’2010), 23-27 Feb. 2010, Lviv, Ukraine. IEEE, 2010, p. 29.

KRON, G. Diakoptics; the piecewise Solution of Large-Scale System. London: MacDonald, 1963.

Пристатейна бібліографія

Вегешна Ш. Качество обслуживания в сетях IP / Пер. С анлг. – М.: Из-дательский дом «Вильямс», 2003. – 368 с.

Barreiros M., Lundqvist P. QOS-Enabled Networks: Tools and Foundations. – Wiley Series on Communications Networking & Distributed Systems, 2nd Edition, Wiley, 2016. – 254 p.

Halabi S. Internet Routing Architectures (2nd Edition). – Cisco Press, 2000. – 521 p.

Medhi D., Ramasamy K. Network Routing, Second Edition: Algorithms, Protocols, and Architectures, (The Morgan Kaufmann Series in Networking) 2nd Edition. – Cambridge, MA, USA: Elsevier Inc., 2018. – 1018p.

Гольдштейн А.Б., Гольдштейн Б.С. Технология и протоколы MPLS. – СПб.: БХВ, 2005. – 304 с.

Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы: учебник для вузов. 3-е изд. – СПб.: Питер, 2006. – 958 с.

Cisco Networking Academy. Routing Protocols Companion Guide. Pearson Education. Cisco press, 2014. – 756 p.

Misra S., Goswami S. Network Routing: Fundamentals, Applications, and Emerging Technologies 1st Edition. – Wiley, 2017. – 536 p.

Поповский ВВ., Лемешко А.В., Мельникова Л.И., Андрушко Д.В. Обзор и сравнительный анализ основных моделей и алгоритмов многопутевой маршрутизации в мультисервисных телекоммуникацион-ных сетях // Прикладная радиоэлектроника. – 2005. – Том.4. Вып. № 4. – C. 372-382.

Lee G.M., Choi J.S. A survey of multipath routing for traffic engineering // Springer-Verlag. – 2005. – P. 635-661.

Segall A. The Modeling of Adaptive Routing in Data Communication Networks // IEEE Transactions on Communications. – January 1977. – Vol. 25. – P. 85–95.

Rak J. Resilient Routing in Communication Networks (Computer Communications and Networks), 1st edition. – Springer, 2015.

Lemeshko O. V., Yeremenko O. S. Dynamics Analysis of Multipath QoS-Routing Tensor Model with Support of Different Flows Classes // 2016 International Conference on Smart Systems and Technologies (SST). – Josip Juraj Strossmayer University of Osijek, Croatia, 12-14 Oct. 2016. – P. 225-230.

Lemeshko O., Yeremenko O. Dynamic presentation of tensor model for multipath QoS-routing // 2016 13th International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET). – Lviv, Ukraine, 23-26 Feb. 2016. – P. 601-604.

Лемешко О.В., Єременко О.С. Динамічна модель маршрутизації при забезпеченні якості обслуговування за показником ймовірності своєчасної доставки пакетів // XІ Міжнародна науково-технічна конференція "Проблеми телекомунікацій" ПТ-2017: Збірник матеріалів конференції. К.: КПІ ім. Ігоря Сікорського, 2017. – С. 285-287.

Lemeshko О., Drobot O. A Mathematical Model of Multipath QoS-based Routing in Multiservice Networks // Proceedings of International conference Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET). – Lviv-Slavsko, 2006. – P. 72-74.

Lin S. C., Akyildiz I. F., Wang P., Luo M. QoS-aware Adaptive Routing in Multi-layer Hierarchical Software Defined Networks: A Reinforcement Learning Approach // 2016 IEEE International Conference on Services Computing (SCC). – San Francisco, CA, USA, 27 June-2 July 2016. – P. 25-33.

Romanov O.I., Nesterenko M.M., Veres L.A., Hordashnyk Y.S. IMS: Model and calculation method of telecommunication network's capacity // 2017 IEEE International Conference on Information and Telecommunication Technologies and Radio Electronics (UkrMiCo), Odessa, Ukraine, 11-15 Sept. 2017. – P. 1-4.

Wright B. Inter-area routing, path selection and traffic engineering. white paper. – Data Connection Limited, 2003. – 42 p.

Vutucury S. Multipath routing mechanisms for traffiv engineering and quality of service in the Internet. – PhD dissertation, University of California, USA 2001. – 152 p.

Vutukury S., Garcia-Luna-Aceves J.J. A traffic engineering approach based on minimum-delay routing // 2000 IEEE Ninth International Conference on Computer Communications and Networks. – Las Vegas, 16-18 Oct. 2000. – P. 42-47.

Seok Y., Lee Y., Choi Y., Kim C. Dynamic Constrained Traffic Engineering for Multicast Routing // Information Networking: Wired Communications and Management. – Sept. 2002. – Vol. 2343. – P. 278-288.

Wang Y., Wang Z. Explicit routing algorithms for Internet Traffic Engineering // Proceedings Eight International Conference Computer Communications and Networks. – Boston, USA, 11-13 Oct. 1999. – P. 582-588.

Lemeshko O., Vavenko T., Ovchinnikov K. Design of multipath routing scheme with load balancing in MPLS-network // 2013 IEEE XIIth International Conference THE EXPERIENCE OF DESIGNING AND APPLICATION OF CAD SYSTEMS IN MICROELECTRONICS. – Polyana-Svalyava-(Zakarpattya), UKRAINE, 19-23 February 2013. – P. 211-213.

Mersni A., Ilyashenko A., Vavenko T. Complex Optimality Criterion for Load Balancing with Multipath Routing in Telecommunications Networks of Nonuniform Topology // 14th International Conference The Experience of Designing and Application of CAD System in Microelectronic (CADSM). – Polyana-Svalyava (Zakarpattya), Ukraine, 21-25 February 2017. – P. 100-104.

Mersni A., Ilyashenko A. E. Complex criterion of load balance optimality for multipath routing in telecommunication networks of nonuniform topology // Telecommunications and Radio Engineering. – 2017. – Vol. 76, Issue 7. – P. 579-590.

Lemeshko O., Yeremenko O., Nevzorova O. Hierarchical Method of Inter-Area Fast Rerouting // Transport and Telecommunication Journal. – June 2017. – Vol. 18, No. 2. – P. 155-167.

Евсеева О.Ю. Решение задачи иерархическо-координационной маршрутизации в телекоммуникационных сетях методом предсказания взаимодействия // Открытые информационные и компьютерные интегрированные технологии. – 2003. – Вып.21. – С. 102-111.

Yeremenko O., Lemeshko O., Nevzorova O., Hailan A.M. Method of hierarchical QoS routing based on network resource reservation // 2017 IEEE First Ukraine Conference on electrical and computer engineering (UKRCON). – Kyiv, Ukraine, 29 May-2 June 2017. – P. 971-976.

Лемешко А.В., Ахмад М. Хайлан, Семеняка М.В. Модель и метод иерархической маршрутизации на основе резервирования ресурсов в сети IP/IntSev // Радиотехника: Всеукр. межвед. науч.-техн. сб. – 2010. – Вып. 163. – С. 79-84.

Nevzorova Ye.S., Arous K.M., Salakh M.T.R. Method for hierarchical coordinated multicast routing in a telecommunication network // Telecommunication and Radio Engineering. – 2016. – Vol. 75. – P. 1137-1151.

Лемешко А.В., Хайлан А.М. Многоуровневое управление трафиком в сети MPLS–TE DiffServ на основе координационного принципа прогнозирования взаимодействий // Проблеми телекомунікацій. – 2010. – № 1 (1). – С. 35 – 44.

Yevsyeyeva O. Diakoptical approach in telecommunication engineering // 2010 IEEE Modern problems of radio engineering, telecommunication and computer science (TCSET’2010). – Lviv, Ukraine, 2010. – P. 29.

Kron G. Diakoptics; the piecewise Solution of Large-Scale System. – MacDonald, London, 1963. – 166 p.

Проблеми телекомунікацій № 1(22) (2018)

Downloads

Published

2018-12-11

Issue

No. 1(22) (2018)

Section

Articles

License

Copyright (c) 2019 Problemi telekomunìkacìj

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Authors who publish with this journal agree to the following terms:
  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).