具有可靠性的k最短路径及其优化问题的研究

发布时间：2024-06-29 14:35

　　k最短路径应用在大数据中心和高性能计算集群网络中具有低延迟,高带宽等优点,因而受到研究人员的广泛关注。为了实现网络节点在k最短路径策略中信息的可靠传递,本文研究链路失效模型下k最短路径的可靠性和期望路径长度问题,主要结论如下:1.本文考虑了节点可靠,链路可能失效的可靠性模型中,k最短路径的等长路径选择问题,并将等长路径的选择问题转化为一个可靠性优化问题。最终提出了精确算法和基于蒙特卡洛模拟的近似算法求解该问题,实例表明了近似算法的有效性。2.本文建立了期望k最短路径长度的参数去衡量网络性能,并证明了广义德布鲁因图的期望k最短路径长度拥有近似最优的性能。仿真结果有效地验证了理论分析。

【文章页数】：41 页

【学位级别】：硕士

【部分图文】：

图２．１可靠性算法示意图间??Ｆｉ．?２．１?Ａｎ?ｉｌｌｕｓｔｒａｔｉｏｎ?ｆｏｒ?ｒｅｌｉａｂｉｌｉｔａｌｏｒｉｔｈｍｓ?Ｊ２３１??

链路??的集合，Ｐ是每条链路独立正常运行的概率。详细假设如下：??（１）网络中的每条链路都以相同的概率９?＝?１－０失效。??（２）网络中的每个节点都是完美的。??（３）所有链路失效都是独立的。??２．２．１料可靠性的精确算法??本文主要研宄的是可靠性（两终端可靠性），即考虑给定....

图２．２因子定理示意图Ｍ??Ｆｉｇ．?２．２?Ａｎ?ｉｌｌｕｓｔｒａｔｉｏｎ?ｆｏｒ?ｆａｃｔｏｒｉｎｇ?ｄｅｃｏｍｐｏｓｉｔｉｏｎ?ａｌｇｏｒｉｔｈｍ?１２３１??

华东理工大学硕士学位论文?第７页??（１）容斥原理算法＿２５］［２６］??容斥原理算法主要利用概率论的相关理论。其中￡；，￡；，．．．，￡：表示《个事件，则??Ｅ＇，Ｅ２，…，瓦中至少有一个事件发生的概率公式：??ＷＧ）?＝?Ｐｒ％?Ｕ?￡＂２?Ｕ?…Ｕ??＝Ｚｋ?ＰＫ＆）?－?....

图２．３网络Ｇ和子网络：Ｇｉ）网络＝?１，＜?＝?４?（的子网络Ｗ?（ｃ）子网络Ｇ／??Ｆｉｇ．?２．３?Ａ?Ｎｅｔｗｏｒｋ?Ｇ?ａｎｄ?ｓｕｂｎｅｔｗｏｒｋｓ：ａ）?Ａ?ｎｅｔｗｏｒｋ?Ｇ?ｗｉｔｈ?ｓ?＝?１?ａｎｄ?ｔ?＝?４（ｂ）Ａ．?ｓｕｂｎｅｔｗｏｒｋ?Ｇ２１?（ｃ）?Ａ?ｓｕｂｎｅｔｗｏｒｋ??

．１?ｔ最短可靠路径??经典的ｔ最短路径问题作为最短路径问题的泛化，通过寻求网络源节点与终端节??点ｆ之间的最短路径，次短路径，次次短路径，．．．，直到找到第＆短的路径，最终形成??灸最短路径集合，提供给用户用于支持决策。经典的Ａ最短路径在选择第／（１ＵＳ幻短路??径的时候，重点....

图３．１?８个节点，点度为３的ＧＤＢＧ?（８，?３）．??Ｆｉｇ．?３．１．?ＧＤＢＧ?（８，?３）?ｗｉｔｈ?８?ｎｏｄｅｓ?ａｎｄ?３?ｄｅｇｒｅｅｓ?ｏｆ?ｅａｃｈ?ｎｏｄｅ．??

期望Ａ最短路径长度的下界。接下来，我们将会考虑广义德布鲁因图的期望ｉｔ最短路径??长度。??３，２．２广义德布鲁因图的期望最短路径长度分析??广义德布鲁因图（Ｇｅｎｅｒａｌｉｚｅｄ?Ｄｅ?Ｂｒｕｉｊｎ?Ｇｒａｐｈ，?ＧＤＢＧ）是一种特殊的有向正则图，??和随机正则图不同，它是一种....

本文编号：3997700