点对点网络容错路由算法的路径长度分析

用概率性分析方法 ,研究了在结点错误概率性分布的情形下超立方体网络点对点容错路由算法的路径长度 ,得出了算法的路径长度期望值 ,分析表明 :对于结点错误概率 p≤ 10时 ,源点 U到终点 V所在的 k维子立方体的路径长度期望值不超过 1.11* h,比以往通常的长度分析结果 2 * h小得多 .提出一种改进的算法并证明这一新算法所构造的路径长度的期望值不大于 1.11h- 0 .11k 2 ,这大大改进了以前的路径 2 h k 2 ,其中 h为 U与 V的 Ham ming距离 .

Probabilistic Study on Node-to-Node Network Routing Path Length

Based on node failure probability,this paper proposes a new probabilistic analysis method to study the routing path length of network routing algorithms.It used hypercube as our network topology and propose two routing algorithm and strictly analyze their routing path length's conditional expectation.The analysis shows that for very significant node failure probability (can be up to 10%),the length's conditional expectation of a routing path from source node U to the k sub-hypercube of end node V is less than 1.11h is the Hamming distance between node U and node V),which is more less than 2h (2h is our usual result).Based on a new routing algorithm,the paper renews to analyze the routing path length and its conditional expectation.It gets a new expression of routing path length--1.11h-0.11k 2.