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

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

作　　者：张祖平[1] 陈建二[1] 陈松乔[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《小型微型计算机系统》2004年第11期1904-1907,共4页Journal of Chinese Computer Systems

基　　金：国家杰出青年自然科学基金 (6992 82 0 1)资助;国家自然科学基金(60 3 73 0 83 );长江学者奖励计划

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

关 键 词：互联网络 超立方体网络 容错性 路由算法 路径长度 条件期望值 概率分析 点对点网络 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]