计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (7): 295-306.doi: 10.11896/jsjkx.240400170

• 计算机网络 • 上一篇    下一篇

基于星图的互连网络分支可靠性分析

刘文飞1,2, 刘佳飞1,2,3, 王琦1,2, 吴璟莉1,2,3, 李高仕1,2,3   

  1. 1 广西师范大学教育区块链与智能技术教育部重点实验室 广西 桂林 541004
    2 广西师范大学广西多源信息挖掘与安全重点实验室 广西 桂林 541004
    3 广西师范大学广西应用数学中心 广西 桂林 541004
  • 收稿日期:2024-04-24 修回日期:2024-08-07 发布日期:2025-07-17
  • 通讯作者: 刘佳飞(liujiafei@gxnu.edu.cn)
  • 作者简介:(liuwenfei@stu.gxnu.edu.cn)
  • 基金资助:
    国家自然科学基金(62302107,62366007);广西高校中青年教师科研基础能力提升项目(2023KY0063);广西应用数学中心基地项目(桂科AD21220114)

Component Reliability Analysis of Interconnected Networks Based on Star Graph

LIU Wenfei1,2, LIU Jiafei1,2,3, WANG Qi1,2, WU Jingli1,2,3, LI Gaoshi1,2,3   

  1. 1 Key Lab of Education Blockchain and Intelligent Technology, Ministry of Education, Guangxi Normal University, Guilin, Guangxi 541004, China
    2 Guangxi Key Lab of Multi-Source Information Mining and Security, Guangxi Normal University, Guilin, Guangxi 541004, China
    3 The Center for Applied Mathematics of Guangxi, Guangxi Normal University, Guilin, Guangxi 541004, China
  • Received:2024-04-24 Revised:2024-08-07 Published:2025-07-17
  • About author:LIU Wenfei,born in 2000,postgra-duate,is a member of CCF(No.T9399G).His main research interests include algorithm design,interconnect network and fault-tolerance computing.
    LIU Jiafei,born in 1993,Ph.D,lecturer,is a member of CCF(No.82823M).His main research interests include parallel and distributed system,interconnect network and fault-tolerance computing.
  • Supported by:
    National Natural Science Foundation of China(62302107,62366007),Basic Ability Enhancement Program for Young and Middle-Aged Teachers of Guangxi,China(2023KY0063) and Science and Technology Project of Guangxi(Guike AD21220114).

PDF (PC)

24

摘要： 随着数据中心、超级计算、云计算等技术领域的迅猛发展,互连网络作为这些技术的基础之一,其规模在不断扩大。然而,随着网络规模的增加,网络中服务器发生故障的情形不可避免。一旦互连网络因故障而瘫痪,将影响人类正常的工作和生活。因此,如何降低故障单元对整个网络拓扑产生的负面影响是一个非常有意义的问题。通常,剩余网络中最大的连通分支称为功能子系统,它量化了故障网络中处理器之间的通信能力和效率。这种量化可靠性的研究有助于更好地理解和管理互连网络的稳定性。文中从基于星图的互连网络出发,首先确定了当故障点集|F|≤5n－15时,Sn－F中的小分支H满足|V(H)|≤4;当|F|≤6n－19时,Sn－F中的小分支H满足|V(H)|≤5;其次重点讨论了星型网络Sn(n≥6)中移除数量不超过6n－19的子集时,网络中剩余分支的情形;最后提出了一种求解故障网络中小分支最小邻居数的近似算法,通过仿真实验证明了星型网络具有良好的鲁棒性和容错能力。这些结果对于理解和设计高可靠性的互连网络具有重要意义。

关键词: 星图, 互连网络, 分支可靠性, 鲁棒性

Abstract: With the rapid development of data centers,supercomputing,cloud computing and other technology areas,interconnected networks as one of the foundations of these technologies,are expanding in size.However,as the scale of the network increases,it is inevitable that servers in the network will fail.Once the interconnected network is paralyzed by failures,the normal work and life of human beings will be seriously affected.Therefore,how to minimize the negative impact of faulty units on the entire network topology is a very meaningful topic.Usually,the largest connected component in the remaining network is called the functional subsystem,which quantifies the communication capability and efficiency between processors in the faulty network.This study of quantitative reliability helps us to better understand and manage the stability of interconnected networks.Starting from a star graph-based interconnection network,this paper determines that a small component H in Sn－F satisfies |V(H)|≤4 when the set of fault nodes |F|≤5n－15,and when |F|≤6n－19,the small components H in Sn－F satisfy |V(H)|≤5.In addition,it focuses on the remaining components of a star network Sn(n≥6)when faulty vertices up to 6n－19 are removed from the network.Finally,an approximation algorithm for solving the minimum number of neighbours of small components in a faulty network is proposed,and by simulation experiments,the star network possesses good robustness and fault tolerance.These results are significant for understanding and designing highly reliable interconnection networks.

Key words: Star graph, Interconnection network, Component Reliability, Robustness

中图分类号: 

  • TP393.02
[1]CHENG E,LIPMAN M J.Increasing the Connectivity of the Star Graphs[J].Networks,2010,40(3):165-169.
[2]ZHOU S,DONG Q F.Reliability Analysis of MultiprocessorSystems[M].Beijing:Science Press,2020.
[3]YANG X,EVANS D J,CHEN B,et al.On the Maximal Con-nected Component of Hypercube with Faulty Vertices[J].International Journal of Computer Mathematics,2004,81(5):515-525.
[4]YANG X,EVANS D J,MEGSON G M.On the Maximal Connected Component of a Hypercube with Faulty Vertices III[J].International Journal of Computer Mathematics,2006,83(1):27-37.
[5]YANG X,EVANS D J,MEGSON G M.On the Maximal Connected Component of Hypercube with Faulty Vertices(II)[J].International Journal of Computer Mathematics,2007,81(10):1175-1185.
[6]YANG X,MEGSON G M,TANG Y Y,et al.Largest Connected Component of a Star Graph with Faulty Vertices[J].International Journal of Computer Mathematics,2008,85(12):1771-1778.
[7]LIN L,HUANG Y,HSIEH S Y,et al.Strong Reliability of Star Graphs Interconnection Networks[J].IEEE Transactions on Reliability,2022,71(3):1241-1254.
[8]ZHU Q,GUO G,WANG D.Relating Diagnosability,Strong Diagnosability and Conditional Diagnosability of Strong Networks[J].IEEE Transactions on Computers,2014,63(7):1847-1851.
[9]LIU J,ZHOU S,ZHANG H,et al.Vulnerability Analysis of Multiprocessor System Based on Burnt Pancake Networks[J].Discrete Applied Mathematics,2022,314:304-320.
[10]WANG Y,MENG J,FAN J.Reliabilities for Two Kinds ofGraphs with Smaller Diameters[J].Applied Mathematics and Computation,2023,446:127874.
[11]ZHOU Q,LIU H,CHENG B,et al.Fault Tolerance of Recursive Match Networks Based ong-good-neighbor Fault Pattern[J].Applied Mathematics and Computation,2024,461:128318.
[12]ZHANG H,HAO R X,QIN X W,et al.The High Faulty Tolerant Capability of the Alternating Group Graphs[J].IEEE Transactions on Parallel and Distributed Systems,2023,34(1):225-233.
[13]FAN W,XIAO F,FAN J,et al.Fault-Tolerant Routing WithLoad Balancing in LeTQ Networks[J].IEEE Transactions on Dependable and Secure Computing,2023,20(1):68-82.
[14]LI X,CHENG B,FAN J,et al.Parallel Construction of Edge-Independent Spanning Trees in Augmented Cubes[J].Computer Science,2024,51(9):346-356.
[15]LIU X,ZHOU S,LIU J,et al.Reliability Analysis of the Cactus-Based Networks Based on Subsystem[J].The Computer Journal,2024,67(1):142-152.
[16]YANG Y,ZHANG M,MENG J.Link Fault Tolerance of BCNetworks and Folded Hypercubes on h-extrar-component Edge Connectivity[J].Applied Mathematics and Computation,2024,462:128343.
[17]SABIR E,FAN J,MENG J,et al.Structure Fault-TolerantHamiltonian Cycle and Path Embeddings in Bipartite k-Ary n-Cube Networks[J].IEEE Transactions on Reliability,2024,73(1):257-269.
[18]LIU X,MENG J,SABIR E.Component Connectivity of the Data Center Network DCell[J].Applied Mathematics and Computation,2023,444:127822.
[19]HUANG Y,LIN L,XU L,et al.Probabilistic Reliability via Subsystem Structures of Arrangement Graph Networks[J].IEEE Transactions on Reliability,2024,73(1):279-289.
[20]ZHANG N,ZHU Q.Two Important Parameters of HPMCModel[J].Theoretical Computer Science,2022,905:10-17.
[21]ZHANG H,ZHOU S.Characterization of Matroidal Connectivity of Regular Networks[J].Journal of Parallel and Distributed Computing,2024,186:104818.
[22]XU J.Combinatorial Theory in Networks[M].Beijing:Science Press,2013.
[23]XU J.Graph Theory and Its Applications[M].Hefei:University of Science and Technology of China Press,2010.
[24]AKERS S B,KRISHNAMURTHY B.A Group-theoretic Model for Symmetric Interconnection Networks[J].IEEE Transactions on Computers,1989,38(4):555-566.
[25]CHENG E,LIPMAN M J,LIPTÁK L.Strong Structural Properties of Unidirectional Star Graphs[J].Discrete Applied Mathematics,2008,156(15):2939-2949.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发