Backtracking Routing Mechanism for Improving Link Failure Recovery

作     者：WU Jing ZHOU Jianguo YANG Jianfeng YAN Puliu JIANG Hao 

作者机构：School of Electronic Information Wuhan University Wuhan 430072 Hubei China 

出 版 物：《Wuhan University Journal of Natural Sciences》 (武汉大学学报（自然科学英文版）)

年 卷 期：2007年第12卷第3期

页      面：462-466页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Supported by the National Natural Science Foundation of China (60502028) 

主　　题：failure insensitive routing (FIR) shortest path tree (SPT) backtracking routing mechanism network survivability network usability 

摘      要：Failure-insensitive routing is a good mechanism to avoid packet dropping and disconnection of forwarding when some links fail, but multiple failure links may bring routing loop for the mechanism. Backtracking routing algorithm based on inverse shortest path tree rooted at destination is presented. The feasible restoration routing is obtained through searching from the start of the failure link and tracing back to the leaves of the shortest path tree with the destination as the root. The packets are forwarded from the mounted point with smaller sequence to the mount point with bigger sequence to decrease the possible of loop in case of multi-failures. The simulations and analysis indicate that backtracking routing algorithm improves the network survivability especially for large network, at the cost of the computation complexity in the same order as failure insensitive routing.