新型互连网络的嵌入性与容错性研究

Embeddability and fault tolerance are two important indexes to measure the quality of the interconnection network,which are important research topics in interconnection networks.The main contents of this project include:the evaluation of the embedding efficiency on embedding hypercube network into super locally twisted cube network,embedding star network into locally twisted cube,embedding the exchanged hypercube network to double-loop networks,to analysis the following four parameters：load, dilation, expansion,congestion,to make the optimization of the embedding performance parameters in order to improve these networks' embedding capacity;the research of fault-tolerant properties for super locally twisted cube network, locally twisted cube network, exchanged hypercube network, double-loop networks,vague sets theory is applied to fault-tolerant computing of the regular networks, the corresponding fault-tolerant routing algorithm is presented for these regular networks with nodes and linkes true failure/ nodes and linkes false failure /nodes and linkes uncertain failure.The research on the fault-tolerant embedding problems of super locally twisted cube network,locally twisted cube network and double-loop networks.

可嵌入性和容错性是衡量互连网络质量的两个重要指标，都是互连网络研究中的重要课题。本课题的主要内容包括：对超立方体网络到超级局部扭立方体网络、星型网络到局部扭立方体网络、交换超立方体网络到双环网络进行嵌入效率的评价：分别对负载、扩张率、 膨胀率、 拥塞度四个参数进行分析，并进一步研究如何使得这几个嵌入性能参数最优化，以提高网络嵌入能力;研究超级局部扭立方体网络、局部扭立方体网络、交换超立方网和双环网络的容错性能，将Vague集理论应用到这些网络的容错性计算中，具体给出在结点和链路真失效和假失效及不确定失效的情况下，相应的容错路由算法。研究超级局部扭立方网、局部扭立方网络、双环网络的容错嵌入问题。

随着大规模集成技术的快速发展，多处理品系统可能含有成千上百万的处理器（结点), 这些处理器通过互连网络来进行通信和交换信息。长时间工作后，多处理器系统出现处理器发生故障是不可避免的。 为了保证可靠性，对系统进行容错性分析是很有必要的。另一方面，网络通用性的常常可以用模拟其他网络的能力来度量， 网络的模拟实际上就是网络图的嵌入问题。因此，开展网络的嵌入问题的研究也是很有必要和重要的意义。本项目的主要内容包括：（1）双二叉树，交换超立方体网络，超立方体网络到局部扭立方体网络的嵌入；（2）星型网络到交换超立方体网络的嵌入；（3）一些重要的规则网络的t/s故障诊断度；（4） 间歇性故障诊断度。经过四年的研究，我们主要取得了下面的重要结果： (i)提出并证明了PMC模型下脆三环网络系统是间歇性t-可诊断的充分必要条件， 提出并证明了BMG模型下一般网络系统是间歇性t-可诊断的充分必要条件，并把永久性情形下的基于比较模型的t-可诊断的充分必要条件推广到间歇性故障情形；(ii)星型网络和超立方体网络在PMC模型下的t/s故障诊断度；(iii) 提出一个从星型网络到超立方体网络的低扩展率嵌入映射；（iv)提出了一个应用于哈密顿网络的高效的五环诊断算法。此外，在人才培养方面，利用本项目这一平台，我们培养了2名博士，8名硕士。