Extended DragonDeBrujin Topology Synthesis Method

Full Text (PDF, 429KB), PP.23-36

Views: 0 Downloads: 0


Artem Volokyta 1,* Heorhii Loutskii 2 Pavlo Rehida 2 Artem Kaplunov 2 Bohdan Ivanishchev 2 Oleksandr Honcharenko 2 Dmytro Korenko 2

1. National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”/ Department of computer engineering, Kyiv, 03056, Ukraine

2. National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”/ Department of computer engineering, Department of information systems and technologies, Kyiv, 03056, Ukraine

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2022.06.03

Received: 28 Apr. 2022 / Revised: 17 Jul. 2022 / Accepted: 27 Oct. 2022 / Published: 8 Dec. 2022

Index Terms

Dragonfly, De Bruijn, Multilevel Topological Organization


Scaling high performance computer systems needs increasing the fault tolerance at the design stage of a topology. There are several approaches of designing simple fast routing with fault tolerance. One of effective approach is to ensure fault tolerance at the topology level. This article discusses two methods for optimizing topologies synthesized using Dragonfly and Excess De Brujin. Methods of topology saturation are discusses, which allow to increase the dimension of the system without deterioration of topological characteristics due to the optimization of the synthesis method. Three scaling constraint methods are also proposed to reduce the topology dimension to the desired performance.

Cite This Paper

Artem Volokyta, Heorhii Loutskii, Pavlo Rehida, Artem Kaplunov, Bohdan Ivanishchev, Oleksandr Honcharenko, Dmytro Korenko, "Extended DragonDeBrujin Topology Synthesis Method", International Journal of Computer Network and Information Security(IJCNIS), Vol.14, No.6, pp.23-36, 2022. DOI:10.5815/ijcnis.2022.06.03


[1]Alverson, Robert, Duncan Roweth, and Larry Kaplan. "The gemini system interconnect." In 2010 18th IEEE Symposium on High Performance Interconnects, pp. 83-87. IEEE, 2010.
[2]Kim, John, Wiliam J. Dally, Steve Scott, and Dennis Abts. "Technology-driven, highly-scalable dragonfly topology." In 2008 International Symposium on Computer Architecture, pp. 77-88. IEEE, 2008.
[3]Ajima, Yuichiro, Shinji Sumimoto, and Toshiyuki Shimizu. "Tofu: A 6D mesh/torus interconnect for exascale computers." Computer 11 (2009): 36-40.
[4]Guan K. C., Chan V. W. S. Cost-efficient fiber connection topology design for metropolitan area WDM networks //IEEE/OSA Journal of Optical Communications and Networking. – 2009. – Т. 1. – №. 1. – С. 158-175.
[5]Yasir Arfat, Fathy Elbouraey Eassa,"A Survey on Fault Tolerant Multi Agent System", International Journal of Information Technology and Computer Science, Vol.8, No.9, pp.39-48, 2016.
[6]A. A. Atallah, G. B. Hamad and O. A. Mohamed, "Fault-Resilient Topology Planning and Traffic Configuration for IEEE 802.1Qbv TSN Networks," 2018 IEEE 24th International Symposium on On-Line Testing And Robust System Design (IOLTS), 2018, pp. 151-156, doi: 10.1109/IOLTS.2018.8474201.
[7]Ganesan, Elango, and Dhiraj K. Pradhan. "The hyper-debruijn networks: Scalable versatile architecture." IEEE Transactions on parallel and distributed systems 4.9 (1993): 962-978.
[8]Dürr, F. (2016). A Flat and Scalable Data Center Network Topology Based on De Bruijn Graphs. arXiv preprint arXiv:1610.03245.
[9]Kamal, Md Sarwar, et al. "De-Bruijn graph with MapReduce framework towards metagenomic data classification." International Journal of Information Technology 9.1 (2017): 59-75.
[10]Peng, G., Ji, P. & Zhao, F. A novel codon-based de Bruijn graph algorithm for gene construction from unassembled transcriptomes. Genome Biol 17, 232 (2016). https://doi.org/10.1186/s13059-016-1094-x
[11]Olexandr G., Rehida P., Volokyta A., Loutskii H., Thinh V.D. (2020) Routing Method Based on the Excess Code for Fault Tolerant Clusters with InfiniBand. Advances in Computer Science for Engineering and Education II. ICCSEEA 2019. Advances in Intelligent Systems and Computing, vol 938. Springer, Cham
[12]Oleksandr Honcharenko, Artem Volokyta, Heorhii Loutskii. Fault-tolerant topologies synthesis based on excess code usign the latin square. The International Conference on Security, Fault Tolerance, Intelligence ICSFTI2019, Ukraine, Kyiv, 14-15 May, 2019, pp. 72-81 (2019).
[13]Loutskii, H., Volokyta, A., Rehida, P.,Goncharenko, O. (2019). Using excess code to design fault-tolerant topologies. Technical sciences and technologies, 1 (15), 134–144.; DOI - https://dx.doi.org/DOI: 10.25140/2411-5363-2019-1(15)-134-144.
[14]Loutskii H., Volokyta A., Rehida P., Honcharenko O., Thinh V.D. (2021) Method for Synthesis Scalable Fault-Tolerant Multi-level Topological Organizations Based on Excess Code. In: Hu Z., Petoukhov S., Dychka I., He M. (eds) Advances in Computer Science for Engineering and Education III. ICCSEEA 2020. Advances in Intelligent Systems and Computing, vol 1247. Springer, Cham. https://doi.org/10.1007/978-3-030-55506-1_32
[15]H. Loutskii, A. Volokyta, P. Rehida, O. Honcharenko, B. Ivanishchev and A. Kaplunov, "Increasing the fault tolerance of distributed systems for the Hyper de Bruijn topology with excess code," 2019 IEEE International Conference on Advanced Trends in Information Theory (ATIT), Kyiv, Ukraine, 2019, pp. 1-6, doi: 10.1109/ATIT49449.2019.9030487.
[16]Loutskii, H., Volokyta, A., Rehida, P., Kaplunov, A., Ivanishchev, B., Honcharenko, O., Korenko, D. (2021, January). Topology Synthesis Method Based on Excess De Bruijn and Dragonfly. In International Conference on Computer Science, Engineering and Education Applications (pp. 315-325). Springer, Cham. https://doi.org/10.1007/978-3-030-80472-5_27