计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2013年
14期
105-108,120
,共5页
方木云%彭慧子%刘辉
方木雲%彭慧子%劉輝
방목운%팽혜자%류휘
无向双环网络%最优路由构图%扩展路由构图%容错路由%故障点封闭区%故障点逃逸区
無嚮雙環網絡%最優路由構圖%擴展路由構圖%容錯路由%故障點封閉區%故障點逃逸區
무향쌍배망락%최우로유구도%확전로유구도%용착로유%고장점봉폐구%고장점도일구
bidirectional double-loop networks%optimum routing graph%extended routing graph%fault-tolerance routing%closing areas of faulty nodes%escaping areas of faulty nodes
在节点出现故障的情况下,如何保证网络节点之间的路由是一个重要的问题。将无向双环网络的节点按照最短路径访问方式映射到直角坐标系形成最优路由构图CG(N;±r、±s);基于该构图根据源节点和目的节点是否位于坐标轴上以及它们周围的故障节点数,提出故障节点封闭区和逃逸区的概念;存在故障逃逸区的情况下,源、目的节点之间仍然可以进行最优路由,针对出现故障节点封闭区而无法进行最优路由的情况下,增加等价节点形成扩展路由构图ECG(N;±r、±s),从而寻找容错路由;给出最优路由构图、扩展路由构图和容错路由的算法,并编程仿真了这些算法。
在節點齣現故障的情況下,如何保證網絡節點之間的路由是一箇重要的問題。將無嚮雙環網絡的節點按照最短路徑訪問方式映射到直角坐標繫形成最優路由構圖CG(N;±r、±s);基于該構圖根據源節點和目的節點是否位于坐標軸上以及它們週圍的故障節點數,提齣故障節點封閉區和逃逸區的概唸;存在故障逃逸區的情況下,源、目的節點之間仍然可以進行最優路由,針對齣現故障節點封閉區而無法進行最優路由的情況下,增加等價節點形成擴展路由構圖ECG(N;±r、±s),從而尋找容錯路由;給齣最優路由構圖、擴展路由構圖和容錯路由的算法,併編程倣真瞭這些算法。
재절점출현고장적정황하,여하보증망락절점지간적로유시일개중요적문제。장무향쌍배망락적절점안조최단로경방문방식영사도직각좌표계형성최우로유구도CG(N;±r、±s);기우해구도근거원절점화목적절점시부위우좌표축상이급타문주위적고장절점수,제출고장절점봉폐구화도일구적개념;존재고장도일구적정황하,원、목적절점지간잉연가이진행최우로유,침대출현고장절점봉폐구이무법진행최우로유적정황하,증가등개절점형성확전로유구도ECG(N;±r、±s),종이심조용착로유;급출최우로유구도、확전로유구도화용착로유적산법,병편정방진료저사산법。
It is important to assure communication among nodes in networks when fault nodes occur. Assigning nodes of bidirec-tional double-loop network to Cartesian coordinates by the minimum distance visiting mode forms an optimum graph CG(N;±r、±s) . By this graph according to whether source node and destination node lie in horizontal or vertical coordinate and the amount of fault nodes around them, the concepts of closing areas and escaping areas of faulty nodes are proposed. When escap-ing areas occur, there exists optimum routing paths from source node to destination node. As for the situation of there exists no optimum routing that arising from closing areas of faulty nodes, adding equivalent nodes to form an extended optimum graph ECG(N;±r、±s) to seek fault-tolerant routing. The algorithms of optimum Cartesian coordinates graph, extended Cartesian coor-dinates graph and fault-tolerant routing are proposed and simulated by programming.