Cited By
View all- Ohta S(2023)Necessary Conditions and Empirical Observations for Rearrangeable Banyan-Type NetworksWSEAS TRANSACTIONS ON CIRCUITS AND SYSTEMS10.37394/23201.2023.22.2122(180-194)Online publication date: 31-Dec-2023
On the Existence of Unknown Rearrangeable Banyan-type Networks
Authors: 
Satoru Ohta, Naoki TsujiAuthors Info & Claims
Pages 153 - 158
Abstract
A banyan-type network is a multistage switching network, made up of unit switches with two inputs and two outputs. The network has been used as a component of various communication and computer systems. Banyan-type networks are categorized into blocking and rearrangeable networks. A rearrangeable network is significant for some applications because it can connect inputs and outputs for any request without blocking. However, previous studies have not completely defined and categorized the class of rearrangeable banyan-type networks. This study presents a systematic scheme for discovering previously unreported rearrangeable banyan-type networks. The presented scheme uses the conjunctive normal form–satisfiability (CNF–SAT) modeling of connection routing to test the rearrangeability. In addition, to find truly new rearrangeable networks, networks found to be rearrangeable are compared with known rearrangeable networks by a graph isomorphism algorithm. The scheme applies these processes to networks generated exhaustively by assigning link configuration rules expressed as bit permutations to interstage links. New rearrangeable networks will be discovered if they exist by performing the scheme. The results of performing the scheme are also presented. The result reveals previously unknown networks, which are highly probably rearrangeable and are not isomorphic to any known rearrangeable networks.
References
[1]
Alok Das, Guowu Zhang, Hassan Rahbardar Mojaver, and Odile Liboiron-Ladouceur. 2020. Low loss 8 × 8 silicon photonic banyan switch. In Proceedings of 2020 IEEE Photonics Conference (IPC 2020). IEEE, Vancouver, BC, Canada, 1-2. https://doi.org/10.1109/IPC47351.2020.9252474
[2]
Qixiang Cheng, Yishen Huang, Hao Yang, Meisam Bahadori, Nathan Abrams, Xiang Meng, Madeleine Glick, Yang Liu, Michael Hochberg, and Keren Bergman. 2020. Silicon photonic switch topologies and routing strategies for disaggregated data centers. IEEE J. of Selected Topics in Quantum Electronic 26, 2 (March-April 2020), 8302010. https://doi.org/10.1109/JSTQE.2019.2960950
[3]
Suwen Song, Hangxuan Cui, and Zhongfeng Wang. 2022. A universal efficient circular-shift network for reconfigurable quasi-cyclic LDPC decoders. IEEE Trans. on Very Large Scale Integration (VLSI) Systems 30, 10 (October 2022), 1553-1557. https://doi.org/10.1109/TVLSI.2022.3190317
[4]
Yun Chen, Jimin Wang, Shixian Li, Jinfou Xie, Qichen Zhang, Keshab K. Parhi, and Xiaoyang Zeng. 2021. A reconfigurable 74-140Mbps LDPC decoding system for CCSDS standard. IEICE Trans. on Fundamentals of Elec., Communs. and Computer Sciences E104-A, 11 (November 2021), 1509-1515. https://doi.org/ 10.1587/transfun.2020KEP0006
[5]
Louis Rodney Goke and G. Jack Lipovsky. 1973. Banyan networks for partitioning multiprocessor systems. In Proceedings of the 1st Annual Symposium on Computer Architecture (ISCA ‘73). ACM, Gainesville, FL, USA, 21-28. https://doi.org/10.1145/800123.803967
[6]
Chuan-Lin Wu and Tse-Yun Feng. 1980. On a class of multistage interconnection networks. IEEE Trans. on Computers C-29, 8 (August 1980), 694-702. https://doi.org/10.1109/TC.1980.1675651
[7]
Duncan H. Lawrie. 1975. Access and alignment of data in an array processor. IEEE Trans. on Computers C-24, 12 (December 1975), 1145-1155. https://doi.org/10.1109/T-C.1975.224157
[8]
Harold S. Stone. 1971. Parallel processing with the perfect shuffle. IEEE Trans. on Computers C-20, 2 (February 1971), 153-161. https://doi.org/10.1109/T-C.1971.223205
[9]
Joseph Y. Hui and Edward Arthurs. 1987. A broadband packet switch for integrated transport. IEEE J. of Selected Areas in Communs. SAC-5, 8 (October 1987), 1264-1273. https://doi.org/10.1109/JSAC.1987.1146650
[10]
Jonathan S.Turner. 1988. Design of a broadcast packet switching network. IEEE Trans. on Communs. 36, 6 (June 1988), 734-743. https://doi.org/10.1109/26.2794
[11]
Joseph Y. Hui and Lingie Li. 2010. First-fit scheduling for multi-stage packet switching networks. J. of Communs., 5, 3 (March 2010), 205-210. https://doi.org/10.4304/jcm.5.3.205-210
[12]
Frank K. Hwang. 2004. The Mathematical Theory of Nonblocking Switching Networks (2nd. ed.), World Scientific, Singapore.
[13]
Václav E. Beneš. 1965. Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York.
[14]
Václav E. Beneš. 1975 Proving the rearrangeability of connecting networks by group calculations. Bell System Technical J. 54, 2 (February 1975), 421–434.
[15]
Hung Quang Ngo and Ding-Zhu Du. 2001. Remarks on Beneš conjecture. In Switching Networks: Recent Advances. Ed. Ding-Zhu Du and Hung Quang Ngo. Kluwer Academic Publishers, Dordrecht. 257–258.
[16]
Hao Dai and Xiaojun Shen. 2008. Rearrangeability of 7-stage 16×16 shuffle exchange networks. Frontiers of Electrical and Electronic Engineering in China 3, 4 (September 2008), 440-458.
[17]
Shuo-Yen Robert Li and Xuesong Jonathan Tan. 2009. On rearrangeability of tandem connection of banyan-type networks. IEEE Trans. on Communs. 57, 1 (January 2009), 164-170. https://doi.org/10.1109/TCOMM.2009.0901.060347
[18]
Xuesong Tan and Shuo-Yen Robert Li. 2007. Rearrangeability of tandem cascade of banyan-type networks. IEICE Trans. on Information and Systems E90-D, 1 (January 2007), 67-74.
[19]
Satoru Ohta. 2021. CNF-SAT modelling for banyan-type networks and its application for assessing the rearrangeability. In Proceedings of 10th International Conference on Mathematical Modeling in Physical Sciences (IC-MSQUARE 2021), Journal of Physics Conference Series 2090, 012133. https://doi.org/10.1088/1742-6596/2090/1/012133
[20]
Brendan D. McKay and Adolfo Piperno. 2013. Practical graph isomorphism, II. J. of Symbolic Computation 60, (September 2013), 94-112. https://doi.org/10.1016/j.jsc.2013.09.003
[21]
Koen Claessen, Niklas Een, Mary Sheeran, Niklas Sörensson, Alexey Voronov, and Knut Åkesson. 2009. SAT-solving in practice, with a tutorial example. Discrete Event Dynamic Systems 19, (December 2009), 495–524.
[22]
Weiwei Gong and Xu Zhou. 2017. A survey of SAT solver. In Proceedings of the 1st International Conference on Applied Mathematics and Computer Science, AIP, Rome, Italy, 020059. https://doi.org/10.1063/1.4981999
[23]
Armin Biere. 2019. CaDiCaL at the SAT Race 2019. In Proceeding of SAT RACE 2019 Solver and Benchmark Descriptions, University of Helsinki, Lisbon, Portugal, 8-9.
[24]
Brendan D. McKay and Adolfo Piperno. 2021. nauty and Traces User's Guide (Version 2.7). Retrieved October 16, 2022 from https://pallini.di.uniroma1.it/Guide.html
Index Terms
- On the Existence of Unknown Rearrangeable Banyan-type Networks
Recommendations
A novel design of self-routing strictly nonblocking switching networks
Optical communications with photonic switching are promising to provide high bandwidth and low error bit. Self-routing strictly nonblocking networks are always favoured to be used as switching networks due to their simple routing mechanisms and ...
Rearrangeability of Tandem Cascade of Banyan-Type Networks
The cascade of two baseline networks in tandem is a rearrangeable network. The cascade of two omega networks appended with a certain interconnection pattern is also rearrangeable. These belong to the general problem: for what banyan-type network (i.e., ...
A Three-Stage One-Sided Rearrangeable Polygonal Switching Network
This paper proposes a three-stage rearrangeable polygonal switching network (PSN) for interconnecting one-sided input-output terminals. In comparing our PSN with a three-stage one-sided Clos switching network of the same size and with the same number of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2023
316 pages
ISBN:9798400700002
DOI:10.1145/3592307
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 August 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ICECC 2023
ICECC 2023: 2023 The 6th International Conference on Electronics, Communications and Control Engineering
March 24 - 26, 2023
Fukuoka, Japan
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 20Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)1
Reflects downloads up to 05 Jan 2025
Other Metrics
Citations
Cited By
View all- Ohta S(2023)Necessary Conditions and Empirical Observations for Rearrangeable Banyan-Type NetworksWSEAS TRANSACTIONS ON CIRCUITS AND SYSTEMS10.37394/23201.2023.22.2122(180-194)Online publication date: 31-Dec-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format