摘要
容错路由是目前分布式系统热门的研究课题之一,然而目前大多数容错路由的相关研究,如Mesh、Hypercubes等,大都以mesh架构为主要环境。本论文提出了一个可在蜂窝网络架构上容忍一个错误节点的容错路由算法。若最短路径发生一个节点错误时,仍可以利用该算法找到一条近似最佳路径,它是利用在蜂窝网络的起始点S与终点D两点坐标找出最短路径R,并将此路径以正规表示式表示,然后当发现路径中有节点故障时,则利用算法的caba=ba替换规则,绕过此错误节点。这就是本文在Honeycomb架构下提出的容错路由算法。
The study of fault-tolerant routing is an active research area in distributed systems. Several interesting research topics have been proposed and studies such as mesh and hyper-cubes etc.. They mostly regard mesh structure as the main environment, In this thesis we present a source-oriented fault-tolerant routing algorithm for Honeycomb tori. We propose using regular expression to represent the route between source node S and destination node D, When the routing path encounters a faulty node, the algorithm will use the cabc≡ba rule, where a, b, c denotes the three axises in a Honeycomb torus. We prove that the resulted path is the best alterna- tive route for the original path.
出处
《微计算机信息》
北大核心
2007年第36期133-135,共3页
Control & Automation
关键词
正则表达式
蜂窝网络
容错
路由算法
regular expression, honeycomb networks,fault-tolerant,routing algorithm
