本书以信息容错传输过程中的容错性分析作为研究背景，聚焦于以互连网络为拓扑结构的一般网络环境，以及常用的正则网络结构模型，系统探讨它们在不同节点故障模型下的连通性保持能力与容错性能。通过综合运用图论与组合优化方法设计有效算法，构建满足性能约束的多路径传输结构，以提高网络可靠性。同时，针对网络中动态变化的故障场景，研究网络在不同故障模型下的故障可诊断性，为随时进行故障定位与故障隔离提供理论依据与技术支持，确保系统在复杂环境下稳定运行。
本书以严谨的数学推导与模型构建为基础，希望可以为从事互连网络容错性研究及网络结构设计的学者和工程技术人员提供理论支撑和可行的优化方案。

1.聚焦网络容错核心痛点，针对互连网络故障频发、稳定性需求迫切的行业现状，系统覆盖容错路径设计与故障可诊断性两大核心领域，提供从理论到实践的完整解决方案。
2.内容架构清晰全面，既涵盖多信道无线网络、数据中心网络、超立方体网络等主流应用场景，又深入探讨不同故障模型下的技术突破，兼顾学术深度与行业适配性。
3.融合图论与组合优化前沿方法，提出CoNE启发式算法、FPTAS近似算法等创新技术，数学推导严谨，实验验证充分，为相关算法设计提供重要参考。
4.聚焦实际工程需求，解决路径时延约束、信道资源有限、故障动态变化等实际问题，成果可直接应用于通信、数据中心等对网络稳定性要求极高的领域。
5.作者深耕该领域多年，汇聚大量原创研究成果，内容兼具理论创新性与实践指导性，是高校科研人员、网络技术工程师的优质参考读物。

近年来，随着计算机应用的不断深入，人们对速度更快、性能更高的计算机系统的需求愈发迫切，这推动了并行和分布式系统研究领域的开辟。特别是数据中心网络以及信息网络技术的应用和发展，使得提升网络稳定性、实时进行稳定高效的信息传输成为技术发展的主要瓶颈之一。
各类信息传输系统中元件之间的连接模式称为该系统的互连网络，简称网络。毫无疑问，并行和分布式系统功能的实现，在很大程度上依赖于该系统的互连网络结构，以及网络中信息传输路径方案的优化设计。
随着网络在各行业和学科的逐步渗透，网络化带来的负面冲击也逐步凸显。比如，网络病毒攻击、线路老化、电力短缺、信号干扰以及地形和环境的变化等，都会对网络节点的正常工作产生直接影响，甚至破坏和改变网络连接方式。随着未来网络结构日趋复杂，网络故障成为一个不可避免的不稳定因素。而且，日益扩张的网络规模使得故障出现的概率迅速增大，一旦发生故障，可能会造成不可估量的损失，特别是在银行、军事、地质和交通等行业，其破坏力惊人。所以，研究和提升网络容错性，确保网络在一定故障规模下仍具备主要功能，提供有最低质量保证的网络服务，成为迫切需要解决的问题。
首先，网络中通信路径的设计和优化一直是网络应用面临的主要问题之一。特别是设计具有良好容错性的路径方案，在发生故障后仍能保证传输性能，成为研究的关键。此外，信息传输过程中故障发生后，网络具备大规模故障自诊断能力，发现并修正故障节点，是保证网络持续有效运行的重要保障。所以，网络容错路径设计以及故障诊断性分析是网络容错性研究的两个主要领域。作者近年来一直从事相关研究工作，查阅了本领域大量文献资料，取得了一些有意义的研究成果，故将其整理归纳并撰写成书。
本书的基本结构如下：第1章首先介绍网络容错路径设计以及故障诊断分析的研究背景和进展，并给出本书将要用到的图论领域的术语和记号。第2～4章对网络中满足性能约束的容错路径进行研究。其中，第2章着重考虑在网络节点应用工作时刻表的环境下，当边不交路径公共点满足信息加工时刻表的时间差约束时，低延迟路径的优化设计；第3章以多信道网络为研究场景，结合信道资源的有限性，提出信息容错路径并给出设计算法；第4章考虑数据中心网络中的容错点不交路径对，当存在预先指定的每条路径必须服务的节点区域时，给出覆盖全网节点的不交路径设计方案。第5～7章围绕网络故障可诊断性展开研究，根据网络存在的不同故障模型和实际应用需求，设计不同故障模型，并提出相应的故障可诊断性概念，进一步分析超立方体网络或一般网络的该故障可诊断能力。其中，第5章研究了分支故障模型下的故障可诊断性，该模型更符合大规模故障存在的应用环境；第6章考虑了限制局部可诊断性，从连通分支节点数的角度提出约束条件，着眼于通过网络局部结构构建，应用局部诊断信息，设计故障诊断算法，从而有效节约算力、提高诊断效率，并为网络结构设计提供方案；第7章从故障结构的角度定义结构故障可诊断性，并给出了超立方体中常见故障结构下的结构故障可诊断性。
感谢书末参考文献中列出的作者，正是他们出色的工作推动了本领域研究的不断发展。感谢单珊珊、郭慧铃、何雨佳和李坪，他们为本书收录的部分研究成果做出了突出贡献。最后感谢太原理工大学数学学院图论研究团队，以及负责人杨卫华教授对本书出版的支持。
由于时间仓促，书中疏漏之处恳请读者批评指正。
作者

张淑蓉，太原理工大学数学学院副教授，硕导，图论及其应用-网络优化方向团队负责人，入选省三晋英才支持计划。研究方向围绕与网络容错性分析、故障诊断、路由QoS优化设计等相关的组合优化问题。曾主持国家自然科学基金项目1项、山西省自然科学基金项目2项，相关研究成果在国内外重要期刊共发表SCI、EI收录论文25篇。现为中国工业与应用数学学会信息和通讯技术领域的数学专委会委员。博士就读于山西大学基础数学专业，2013年7月至今任职于太原理工大学数学学院，期间两次作为访问学者受邀赴巴黎第十一大学进行学术访问。主讲本科生公共专业课线性代数和概率论与数理统计，山西省级一流课程数学建模实训案例课程负责人，主编出版教材1种。

第1章 绪论1
1.1 容错路径设计/1
1.2 网络故障可诊断性/3
第2章 公共点约束下不交路径对的设计优化 5
2.1 问题模型/5
2.2 辅助时间有向图/ 7
2.2.1 G?中的点/7
2.2.2 G?中的弧/8
2.2.3 G?中的权函数/ 9
2.2.4 等价问题模型/10
2.3 启发式算法/12
2.3.1 CoNE的框架/12
2.3.2 关于P(I,H)问题P?的设计和重构/13
2.3.3 P?的构建/16
2.3.4 冲突点集/18
2.3.5 分而治之策略/ 22
2.4 实验结果/ 24
2.4.1 随机网络中的仿真实验/ 24
2.4.2 实际网络中的仿真实验/30
2.5 本章小结/32
第3章 多信道无线网络中性能约束下的容错路径优化 33
3.1 准备工作/33
3.2 受限最小和k-DPDC问题/36
3.2.1 当c(e)N+时的受限min-sum k-DPDC问题/36
3.2.2 FPTAS/39
3.3 限制min-max k-DPDC问题/ 41
3.3.1 当c(e)N+时的限制min-max k-DPDC问题/41
3.3.2 FPTAS/ 44
3.4 本章小结/45
第4章 数据中心网络中经过指定点集的不交路覆盖46
4.1 相关概念和结果/ 46
4.1.1 基本符号/46
4.1.2 HSDC,的定义/47
4.1.3 逻辑图Hn/ 47
4.1.4 k-元n一立方体Q的定义/49
4.2 t阶2-不交路可覆盖/50
4.3 {x,u,y,v}CV(Hn-1)时S九-1中的路径展开算法/51
4.4 路径重构算法/52
4.5 H中的2-不交路覆盖/56
4.6 本章小结/75
第5章 超立方体网络的分支故障可诊断性 76
5.1 准备工作/76
5.2 分支连通性/ 77
5.3 Qn的(g+1)-分支可诊断性(1gn1)/78
5.4 含有至多n²/2+n/23故障点的Qn的连通分支/81
5.5 Qn的(n+1)-分支可诊断性/ 90
5.6 本章小结/92
第6章 互连网络限制局部可诊断性及诊断算法93
6.1 准备工作/93
6.2 限制局部可诊断性的定义/94
6.3 在PMC模型下的限制局部诊断算法/95
6.3.1 在PMC模型下的限制局部可诊断性/ 95
6.3.2 诊断结构T(v;h)/966.3.3 限制局部诊断算法/99
6.4 仿真实验/102
6.5本章小结/103
第7章 超立方体网络的结构故障可诊断性105
7.1准备工作/105
7.2 PMC模型和MM*模型下的H-结构可诊断度/106
7.2.1 Qn的K1,1一结构可诊断度/106
7.2.2 Qn的K1,2-结构可诊断度/110
7.2.3 Qn的K1,3-结构可诊断度/113
7.2.4 Qn的C?-结构可诊断度/122
7.3本章小结/124
参考文献125