计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2014年
6期
997-1004
,共8页
曹继军%郑义%王克非%肖立权
曹繼軍%鄭義%王剋非%肖立權
조계군%정의%왕극비%초립권
胖树%原路返回%路由算法%无死锁%负载均衡%确定性能比率
胖樹%原路返迴%路由算法%無死鎖%負載均衡%確定性能比率
반수%원로반회%로유산법%무사쇄%부재균형%학정성능비솔
fat-tree%back-track%routing algorithm%deadlock freedom%load balance%oblivious performance ratio
胖树是最重要的互连网络拓扑结构之一.针对胖树拓扑结构,已经提出了多种路由算法,其中OSRM被证明是一种最优化的路由算法,但是所有算法都忽略了网络链路故障的易诊断性.为此,提出一种对OSRM改进的新型路由算法BT-OSRM.该算法定义了节点间的大小关系并通过比较节点大小而从OSRM路由路径与其反向路径中选择路由路径.此外,还针对常用的2级和3级胖树结构,分别详细给出了BT-OSRM2和BT-OSRM3路由算法.理论分析表明,BT-OSRM路由算法不但继承了OSRM路由算法无死锁、负载均衡和性能最优等优点,而且保证了任意两节点间的路由路径具有原路返回特性,从而提高了网络故障链路的易诊断性.
胖樹是最重要的互連網絡拓撲結構之一.針對胖樹拓撲結構,已經提齣瞭多種路由算法,其中OSRM被證明是一種最優化的路由算法,但是所有算法都忽略瞭網絡鏈路故障的易診斷性.為此,提齣一種對OSRM改進的新型路由算法BT-OSRM.該算法定義瞭節點間的大小關繫併通過比較節點大小而從OSRM路由路徑與其反嚮路徑中選擇路由路徑.此外,還針對常用的2級和3級胖樹結構,分彆詳細給齣瞭BT-OSRM2和BT-OSRM3路由算法.理論分析錶明,BT-OSRM路由算法不但繼承瞭OSRM路由算法無死鎖、負載均衡和性能最優等優點,而且保證瞭任意兩節點間的路由路徑具有原路返迴特性,從而提高瞭網絡故障鏈路的易診斷性.
반수시최중요적호련망락탁복결구지일.침대반수탁복결구,이경제출료다충로유산법,기중OSRM피증명시일충최우화적로유산법,단시소유산법도홀략료망락련로고장적역진단성.위차,제출일충대OSRM개진적신형로유산법BT-OSRM.해산법정의료절점간적대소관계병통과비교절점대소이종OSRM로유로경여기반향로경중선택로유로경.차외,환침대상용적2급화3급반수결구,분별상세급출료BT-OSRM2화BT-OSRM3로유산법.이론분석표명,BT-OSRM로유산법불단계승료OSRM로유산법무사쇄、부재균형화성능최우등우점,이차보증료임의량절점간적로유로경구유원로반회특성,종이제고료망락고장련로적역진단성.
