Fault-tolerant switching method of Benes network and its applications

Qin Mengyuan; Liu Hongwei; Hao Qinfen

doi:10.11959/j.issn.1000-0801.2026111

您当前的位置：

首页 >

文章列表页 >

Fault-tolerant switching method of Benes network and its applications

Research and Development | 更新时间：2026-04-08

- Fault-tolerant switching method of Benes network and its applications
- Telecommunications Science Vol. 42, Issue 3, Pages: 19-32(2026)
- 作者机构：
  
  1.中国科学院计算技术研究所，北京 100095
  2.中国科学院大学，北京 100049
- 作者简介：
- 基金信息：
  
  The National Key Research and Development Program of China(2022YFB4401501);The Key Research and Development Program of Jiangsu Province(BE2023006-4)
- DOI：10.11959/j.issn.1000-0801.2026111
  CLC： TP302.2;TN256
- Received：24 July 2025，
  
  Revised：2025-10-20，
  
  Accepted：29 October 2025，
  
  Published：20 March 2026
- 稿件说明：
移动端阅览
秦梦远,刘宏伟,郝沁汾.Benes网络容错交换方法及其应用[J].电信科学,2026,42(03):19-32.

Qin Mengyuan,Liu Hongwei,Hao Qinfen.Fault-tolerant switching method of Benes network and its applications[J].Telecommunications Science,2026,42(03):19-32.
秦梦远,刘宏伟,郝沁汾.Benes网络容错交换方法及其应用[J].电信科学,2026,42(03):19-32. DOI： 10.11959/j.issn.1000-0801.2026111.

Qin Mengyuan,Liu Hongwei,Hao Qinfen.Fault-tolerant switching method of Benes network and its applications[J].Telecommunications Science,2026,42(03):19-32. DOI： 10.11959/j.issn.1000-0801.2026111.

摘要

Benes网络能够实现高交换基数下较低的构建成本和理论高吞吐量，但现有Benes网络对应的路由求解算法不保证网络内部开关单元失效时的可重排无阻塞特性。提出一种非平衡Benes网络，其在特定条件下拥有和Benes网络相同的可重排无阻塞特性。提出一种由Benes网络裁剪获得非平衡Benes网络的方法，可以此法屏蔽Benes网络中发生故障的开关单元，实现网络的容错交换。当用于处理开关阵列生产良率问题时，该方案可重排无阻塞交换规模比传统容错方案平均提升56.05%，最高提升93.75%；当用于处理开关阵列的高可靠容错交换时，在容许最多3个开关单元出现故障前提下，比传统容错方案交换规模提升12.5%至21.9%。提出针对非平衡Benes网络的快速路由求解算法，并使用FPGA验证，验证结果表明，该求解算法不会成为交换系统的性能瓶颈。基于裁剪法，研究同样实现了Benes网络的可控局部重构，使其支持像Crossbar网络那样以局部重构为主的使用方式。

Abstract

Benes network can achieve low construction costs and high throughput on high-radix-switching scenarios. However

existing route-resolving algorithms corresponding to Benes network do not guarantee rearrangeable non-blocking (RNB) switching when suffering failure of some of its internal switch units. An unbalanced Benes network was proposed and its RNB switching trait could be guaranteed in certain conditions. A trimming method to convert a Benes network to unbalanced Benes network was proposed

through which failed switching units could be blocked

and fault-tolerant switching was achieved. When solving yield rate problems of the switch array

the trimming method demonstrated advantages over the conventional method on RNB switching radix

with 56.05% in average and 93.75% in maximum. When solving high reliability switching problems of the switch array

the trimming method had 12.5% to 21.9% higher switching radix when tolerating maximum 3 faulty switch units. Moreover

a fast route-resolving method for unbalanced Benes network was proposed and verified via field programmable gate array (FPGA)

and the result shows that it doesn’t become the bottleneck of the system. Furthermore

through the trimming method

controllable partial reconfiguration of Benes network can be achieved

so Crossbar-like switching form based on partial reconfiguration is also supported by Benes network.

关键词

Keywords

references

Beneš V E . Permutation groups, complexes, and rearrangeable connecting networks [J ] . Bell System Technical Journal , 1964 , 43 ( 4 ): 1619 - 1640 .

Clos C . A study of non-blocking switching networks [J ] . Bell System Technical Journal , 1953 , 32 ( 2 ): 406 - 424 .

Shen L , Lu L J , Guo Z Z , et al . Silicon optical filters reconfigured from a 16 × 16 Benes switch matrix [J ] . Optics Express , 2019 , 27 ( 12 ): 16945 - 16957 .

Tunesi L . Integrated Benes optical switches: an automated bottom-up design implementation [D ] . Torino : Politecnico di Torino , 2021 .

Chu T , Qiao L , Tang W J , et al . Fast, high-radix silicon photonic switches [C ] // Proceedings of the 2018 Optical Fiber Communications Conference and Exposition (OFC) . Piscataway : IEEE Press , 2018 : 1 - 3 .

Wang B , Liu L B , Deng C C , et al . Exploration of benes network in cryptographic processors: a random infection countermeasure for block ciphers against fault attacks [J ] . IEEE Transactions on Information Forensics and Security , 2017 , 12 ( 2 ): 309 - 322 .

Runge A , Kolla R . Using benes networks at fault-tolerant and deflection routing based network-on-chips [C ] // Proceedings of the 2016 Tenth IEEE/ACM International Symposium on Networks-on-Chip (NOCS) . Piscataway : IEEE Press , 2016 : 1 - 8 .

Wang Y , Qin Y B , Deng D Z , et al . A 28nm 27.5TOPS/W approximate-computing-based transformer processor with asymptotic sparsity speculating and out-of-order computing [C ] // Proceedings of the 2022 IEEE International Solid-State Circuits Conference (ISSCC) . Piscataway : IEEE Press , 2022 : 1 - 3 .

Ghandriz Z S , Zeinali E K . A new routing algorithm for a three-stage clos interconnection networks [J ] . International Journal of Computer Science Issues (IJCSI) , 2011 , 8 ( 5 ): 309 .

Wang L K , Ye T , Lee T T . A parallel route assignment algorithm for fault-tolerant clos networks in OTN switches [J ] . IEEE Transactions on Parallel and Distributed Systems , 2019 , 30 ( 5 ): 977 - 989 .

Waksman A . A permutation network [J ] . Journal of the ACM , 1968 , 15 ( 1 ): 159 - 163 .

Nassimi , Sahni . A self-routing benes network and parallel permutation algorithms [J ] . IEEE Transactions on Computers , 1981 , C-30( 5 ): 332 - 340 .

Lee K Y . A new benes network control algorithm [J ] . IEEE Transactions on Computers , 1987 , C-36( 6 ): 768 - 772 .

Nikolaidis D , Groumas P , Kouloumentas C , et al . Novel Benes network routing algorithm and hardware implementation [J ] . Technologies , 2022 , 10 ( 1 ): 16 .

Jiang Y , Yang M . Hardware implementation of parallel algorithm for setting up Benes networks [C ] // Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA) . The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp) , 2016 : 10 .

Koloko L , Matsumoto T , Obara H . Design and implementation of fast and hardware-efficient parallel processing elements to set full and partial permutations in Beneš networks [J ] . The Journal of Engineering , 2021 ( 6 ): 312 - 320 .

秦梦远 , 刘宏伟 , 郝沁汾 . 高性能Benes网络路由求解算法及硬件加速器 [J ] . 计算机工程与应用 , 2025 , 61 ( 14 ): 163 - 175 .

Qin M Y , Liu H W , Hao Q F . High-performance route-resolving algorithm and hardware accelerator for benes network [J ] . Computer Engineering and Applications , 2025 , 61 ( 14 ): 163 - 175 .

Jahanshahi M , Bistouni F . Improving the reliability of the Benes network for use in large-scale systems [J ] . Microelectronics Reliability , 2015 , 55 ( 3/4 ): 679 - 695 .

Dong Y , Wang J . Fault tolerance study on large scale Benes switches [C ] // Proceedings of the HPSR . 2005 Workshop on High Performance Switching and Routing . Piscataway : IEEE Press , 2005 : 197 - 201 .

Dong Y , Wang J . Fault tolerance design for large-scale optical switches [J ] . Optical Switching and Networking , 2008 , 5 ( 1 ): 51 - 58 .

Hwang I S , Tseng W D , Huang I F . Integrated fault tolerant connections-scheduling for dilated Benes network [J ] . IEE Proceedings - Communications , 2005 , 152 ( 3 ): 343 .

Tseng W , Hwang I , Lee L , et al . Clique‐partitioning connections‐scheduling with faulty switches in dilated benes network [J ] . Journal of the Chinese Institute of Engineers , 2009 , 32 ( 6 ): 853 - 860 .

张金花 , 武保剑 , 邱昆 . 扩张型Benes光交换芯片未满配置情形下的约束链路路由算法 [J ] . 激光与光电子学进展 , 2019 , 56 ( 21 ): 211301 .

Zhang J H , Wu B J , Qiu K . Constrained link routing algorithm for dilated benes optical switching chips under non-full configuration [J ] . Laser & Optoelectronics Progress , 2019 , 56 ( 21 ): 211301 .

冯斐玲 . Benes网的寻径控制及容错分析 [J ] . 计算机学报 , 1994 , 17 ( S ): 26 - 34 .

Feng F L . Routing control and fault-tolerance analysis of benes network [J ] . Chinese Journal of Computers , 1994 , 17 ( S ): 26 - 34 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰