Abstract
Double-loop networks are widely used in computer networks for its simplicity, symmetry and scalability. In this paper, we focus on optimal routing of Bidirectional Double-loop Network (BDLN) using coordinates embedding and transforming. First, we get the lower bound both of diameter and average distance of BDLN by embedding BDLN into Cartesian coordinates. Then, we find nodes distribution regularity on the embedding graph of tight optimal BDLNs that achieve the lower bound both in diameter and average distance. On the basis of nodes distribution regularity in tight optimal BDLNs, we present on demand optimal message routing algorithms which do not require routing tables and are highly efficient requiring very little computation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chen, Y., Li, Y., Chen, T.: Optimal fault-tolerant routing algorithm and fault-tolerant diameter in directed double-loop networks. Theoret. Comput. Sci. 468, 50–58 (2013)
Dharmasen, H.P., Yan, X.: An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks. IEEE Trans. Parallel Distrib. Syst. 16(9), 841–952 (2005)
Zhou, J.Q., Xu, X.R.: On infinite families of optimal double-loop networks with non-unit steps. Ars Combinatoria 97(10), 81–95 (2010)
Mukhopadhyaya, K., Sinha, B.P.: Fault-tolerant routing in distributed loop networks. IEEE Trans. Comput. 44, 1452–1456 (1995)
Wong, C.K., Coppersmith, D.: A combinatorial problem related to multi-module memory organizations. Assoc. Comput. Mach. 21, 392–402 (1974)
Fang, M., Zhao, B.: Method to calculate the diameter of undirected double-loop networks G(N; ± 1, ± s). J. Commun. 28(2), 124–129 (2007)
Li, Y., Chen, Y.: The algorithm to calculate the diameter of undirected double-loop networks G(N; ± r, ± s) based on tree. J. Huazhong Univ. Sci. Technol. (Nat. Sci. Ed.) 37(6), 8–11 (2009)
Lu, J., Cai, Z., Wang, X., Zhang, L., Li, P., He, Z.: User social activity based routing for cognitive radio networks. Pers. Ubiquit. Comput. 22(3), 471–487 (2018)
Cai, Z., Goebel, R., Lin, G.: Size-constrained tree partitioning: approximating the multicast k-tree routing problem. Theoret. Comput. Sci. 412(3), 240–245 (2011)
Cai, Z., Chen, Z., Lin, G.: A 3.4713-approximation algorithm for the capacitated multicast tree routing problem. Theoret. Comput. Sci. 410(52), 5415–5424 (2009)
Cai, Z., Lin, G., Xue, G.: Improved approximation algorithms for the capacitated multicast routing problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 136–145. Springer, Heidelberg (2005). https://doi.org/10.1007/11533719_16
Boesch, F.T., Wang, J.F.: Reliable circulant networks with minimum transmission delay. IEEE Trans. Circuits Syst. 32(12), 1286–1291 (1985)
Acknowledgment
This work has been supported by the National Natural Science Foundation of China (No. 61772080).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Hui, L., Wang, S. (2019). Optimal Routing of Tight Optimal Bidirectional Double-Loop Networks. In: Biagioni, E., Zheng, Y., Cheng, S. (eds) Wireless Algorithms, Systems, and Applications. WASA 2019. Lecture Notes in Computer Science(), vol 11604. Springer, Cham. https://doi.org/10.1007/978-3-030-23597-0_48
Download citation
DOI: https://doi.org/10.1007/978-3-030-23597-0_48
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-23596-3
Online ISBN: 978-3-030-23597-0
eBook Packages: Computer ScienceComputer Science (R0)