计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2003年
15期
49-52，59
,共5页
王国军%张祖平%陈建二%陈松乔
王國軍%張祖平%陳建二%陳鬆喬
왕국군%장조평%진건이%진송교
概率分析方法%互联网络%超立方体网络%路由算法%容错性
概率分析方法%互聯網絡%超立方體網絡%路由算法%容錯性
개솔분석방법%호련망락%초립방체망락%로유산법%용착성
该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率.针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法[1],该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径.该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数.
該文提齣瞭一種新的概率分析方法來研究在給定結點錯誤概率的情況下超立方體網絡彊容錯路由算法的容錯性的概率.針對文中提齣的基于新的跼部連通性網絡容錯模型的高效的彊容錯路由算法[1],該文首次嚴格證明瞭一箇具有1024箇結點的10維超立方體網絡能夠容許多達4.7%的錯誤結點而具有99%的概率確保找到正確結點組成的路徑,而如果結點的錯誤概率不超過0.1%,則所有實際規模的超立方體網絡能夠具有99.9%的概率確保找到正確結點組成的路徑.該算法的時間性能是最優的,且該算法構造的路徑的長度不超過源結點和目的結點之間海明距離的兩倍加上一箇很小的常數.
해문제출료일충신적개솔분석방법래연구재급정결점착오개솔적정황하초립방체망락강용착로유산법적용착성적개솔.침대문중제출적기우신적국부련통성망락용착모형적고효적강용착로유산법[1],해문수차엄격증명료일개구유1024개결점적10유초립방체망락능구용허다체4.7%적착오결점이구유99%적개솔학보조도정학결점조성적로경,이여과결점적착오개솔불초과0.1%,칙소유실제규모적초립방체망락능구구유99.9%적개솔학보조도정학결점조성적로경.해산법적시간성능시최우적,차해산법구조적로경적장도불초과원결점화목적결점지간해명거리적량배가상일개흔소적상수.
