星图Sn理论及其在网络安全中的应用

星图Sn理论及其在网络安全中的应用
摘要
随着并行计算机互联网络规模的发展，网络中出现处理机故障或处理机间链路故障的可能性越来越大，这使得并行计算机互联网络的容错性及其研究变得越来越重要。由于具有正则性、对称性、可嵌入性、并行性、短直径和可扩展性等优良特性，星图（Star Graph）互联网络受到了研究者们的广泛关注，成为并行计算机互联网络中的重要拓扑结构。
到目前为止，人们已经对星图互联网络的拓扑特性、无错路径模型、容错模型与容错路由算法方面分别进行了深入研究，但是仍有许多问题有待解决。本文研究星图互联网络的升位方法及n维星图的无错误最短路径结构，并改进Floyd算法解决容错路由选择。
针对星图互联网络的拓扑特性，本文对星图升位规律进行研究，得到了相邻阶数间的升位规律，并给出n维星图的升位方法。
对于星图的路由性能，目前较有效的算法是基于安全向量的定义来设计的，然而，这些算法必须基于无错路径结构才能进行。针对该问题本文对Sheng-I Yeh等人提出的无错误路由规则进行研究，得出模式变换的3个重要引理，并推导出构造任意n维星图最短路径结构的两个重要定理，给出具体的算法步骤，从而得到构建任意n维星图最短路径结构的方法。
在对星图的容错路由模型与容错路由算法方面，利用安全系数及安全向量的概念来解决路由寻找算法的缺点是可能出现死锁问题。本文提出改进图论中的Floyd算法来解决容错路由的路径选择，很好地避免了死锁的出现。当然，它仍存在某些缺点，如存储空间较大，只适用于阶数较小或者阶数较大但存在大量错误结点的模型。

关键词：互联网络，星图，升位，无错路由规则，最短路径结构，Floyd算法

*若需了解更多与协助请咨询↓→[电脑QQ][手机QQ]【数据协助】