星载Clos网络的全分布式容错调度算法

刘凯; 晏坚; 高晓琳; 陆建华

doi:10.11999/JEIT150944

星载Clos网络的全分布式容错调度算法

doi: 10.11999/JEIT150944

2.
(清华大学电子工程系北京 100084) ②(清华大学宇航中心北京 100084) ③(清华大学深圳研究生院深圳 518055) ④(北京航天飞行控制中心北京 100094)

基金项目:

国家自然科学基金(91338108, 91438206)，中国电子科技集团校企合作基金(空间互联网关键技术)

计量
- 文章访问数: 1508
- HTML全文浏览量: 117
- PDF下载量: 415
- 被引次数: 0
出版历程
- 收稿日期: 2015-08-19
- 修回日期: 2016-01-20
- 刊出日期: 2016-06-19

Fully Distributed Fault Tolerant Scheduling for Onboard Clos-network Switching

2.
(Department of Electronic Engineering, Tsinghua University, Beijing 100084, China)

Funds:

The National Natural Science Foundation of China (91338108, 91438206), China Electronics Technology Group School-Enterprise Cooperation Foundation (Key Technology of Space Internet)

摘要

摘要: 针对星载交换结构受空间辐射影响造成的可靠性严重下降问题，该文提出了一种支持全分布式调度的三级Clos网络及其全分布式容错(Fully Distributed Fault Tolerant, FDFT)调度算法，以提高星载交换结构在交叉点故障下的容错能力。该Clos网络的中间级和输出级采用联合输入交叉点队列，以支持Clos网络和交换单元内部的全分布式调度。FDFT采用一种分布式故障检测算法获得交叉点故障信息。基于对交叉点故障影响范围的分析，FDFT在输入级采用一种容错信元分发算法，实现无故障路径的负载均衡。理论分析证明，当任一输入/输出级交换单元故障个数不超过(m-n)或所有中间级交换单元故障个数不超过(m-n)时，其中m, n分别为输入级交换单元输入、输出端口数，FDFT能够达到100%吞吐率。仿真结果进一步验证，故障随机发生情况下，FDFT能够抵抗比故障任意发生情况下更多的故障，且在不同的业务场景下具有良好的吞吐率和时延性能。
- 星载交换 /
- Clos网络 /
- 全分布式 /
- 容错调度 /
- 负载均衡
Abstract: For an onboard switching, serious decline in the reliability is induced by the harsh space radiation environment. In this paper, a 3-stage Clos-network supporting fully distributed scheduling and a Fully Distributed Fault Tolerant (FDFT) scheduling algorithm are proposed to improve fault-tolerant ability of an onboard switching. Combined input and output queued architecture is employed in the central and output stages of the proposed Clos-network to support fully distributed scheduling in both the network and switching elements. In FDFT, a distributed fault detection algorithm is employed to obtain the crosspoint fault information. Based on the analysis of the influence of the faults, a fault-tolerant cell dispatching algorithm is proposed in the input stage which achieves load-balancing to fault-free paths. Theoretical analysis demonstrates that 100% throughput is achieved when no more than(m-n) crosspoint faults occur in any input/output module or in all central modules, where m and n are the number of inputs and outputs of input module, respectively. Furthermore, simulation results indicate that, in the case of faults occurring randomly, FDFT tolerates much more faults, and exhibits a good performance in terms of throughput and average cell delay under different traffic scenarios.
- Onboard switching /
- Clos-network /
- Fully distributed /
- Fault-tolerant scheduling /
- Load balancing

HTML全文

参考文献(19)

BOTTA A and PESCAPE A. On the performance of new generation satellite broadband internet services[J]. IEEE Communications Magazine, 2014, 52(6): 202-209. doi: 10.1109/MCOM.2014.6829965.

JAFF E, PILLAI P, and HU Y. IP multicast receiver mobility support using PMIPv6 in a global satellite network[J]. IEEE Communications Magazine, 2015, 53(3): 30-37. doi: 10.1109/ MCOM.2015.7060479.

COURVILLE N, BISCHI H, and ZENG J. Critical issues of onboard switching in DVB-S/RCS broadband satellite networks[J]. IEEE Wireless Communications, 2005, 12(5): 28-36. doi: 10.1109/MWC.2005.1522101.

SIEGLE F, VLADIMIROVA T, ILSTAD J, et al. Mitigation of radiation effects in SRAM-based FPGAs for space applications[J]. ACM Computing Surveys, 2015, 47(2): 37:1-37:34. doi: 10.1145/2671181.

张茂森, 邱智亮, 高雅, 等. 星上Clos 交换网络的分治调度算法[J]. 电子与信息学报, 2012, 34(11): 2734-2740. doi: 10.3724/SP.J.1146.2012.00553.

ZHANG M, QIU Z, GAO Y, et al. Divide-and-conquer dispatching scheme for satellite clos-network switches[J]. Journal of Electronics Information Technology, 2012, 34(11): 2734-2740. doi: 10.3724/SP.J.1146.2012.00553.

KAO Y H and CHAO H J. Design of a bufferless photonic clos network-on-chip architecture[J]. IEEE Transactions on Computers, 2014, 63(3): 764-776. doi: 10.1109/TC.2012.250.

YANG Y and WANG J. A fault-tolerant rearrangeable permutation network[J]. IEEE Transactions on Computer, 2004, 53(4): 414-426. doi: 10.1109/TC.2004.1268399.

GAO Y, QIU Z, ZHANG M, et al. Distributed weight matching dispatching scheme in MSM clos-network packet switches[J]. IEEE Communications Letters, 2013, 17(3): 580-583. doi: 10.1109/LCOMM.2013.012213.122552.

高雅, 邱智亮, 张茂森, 等. 基于帧填补的MMM Clos 网络按序分组交换算法[J]. 电子与信息学报, 2012, 34(11): 2715-2720. doi: 10.3724/SP.J.1146.2012.00617.

GAO Y, QIU Z, ZHANG M, et al. Padded-frame based in-sequence dispatching scheme for memory-memory-memory (MMM) clos-network[J]. Journal of Electronics Information Technology, 2012, 34(11): 2715-2720. doi: 10. 3724/SP.J.1146.2012.00617.

杨君刚, 刘增基, 雒晓卓. 一种新型的三级Clos网络分布式容错调度机制[J]. 解放军理工大学学报: 自然科学版, 2011, 12(3): 217-222.

YANG J, LIU Z, and LUO X. New distributed fault tolerance scheduling algorithm in three-stage clos network[J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2011, 12(3): 217-222.

LI X, ZHOU Z, and HAMDI M. Space-memory-memory architecture for clos-network packet switches[C]. Proceedings of IEEE International Conference on Communications, Seoul, 2005, (2): 1031-1035. doi: 10.1109/ICC.2005.1494505.

YU H, RUEPP S, and BERGER M S. Out-of-sequence prevention for multicast input-queuing space-memory- memory clos-network[J]. IEEE Communications Letters, 2011, 15(7): 761-763. doi: 10.1109/LCOMM.2011.051011. 102535.

KLEBAN J and SUSZYNSKA U. Static dispatching with internal backpressure scheme for SMM clos-network switches [C]. Proceedings of IEEE Symposium on Computers and Communications, Madeira, 2013: 654-658. doi: 10.1109/ ISCC.2013.6755022.

ZHANG M, QIU Z, and GAO Y. Space-memory-memory clos-network switches with in-sequence service[J]. IET Communications, 2014, 8(16): 2825-2833. doi: 10.1049/iet- com.2013.0844.

ROJAS-CESSA R, OKI E, JING Z, et al. CIXB-1: combined input-one-cell-crosspoint buffered switch[C]. Proceedings of IEEE Workshop on High Performance Switching and Routing, Dallas, 2001: 324-329. doi: 10.1109/HPSR.2001.923655.

MCKEOWN N. The iSLIP scheduling algorithm for input- queued switches[J]. IEEE/ACM Transactions on Networking, 1999, 7(2): 188-201. doi: 10.1109/90.769767.

施引文献

资源附件(0)

访问统计