双环网络[+1]边优先最短路径及其寻径策略

ON THE [+1]-LINK-PRIOR SHORTEST PATH AND OPTIMAL ROUTING FOR DOUBLI-LOOP NETWORKS

双环网络是一种非常重要的互联网络结构 .传统的最优寻径方法没有充分利用这一网络中同一节点到不同节点的最短路径之间的关系 ,所给的算法不是最优的 .定义了双环网络的一种最短路径—— [+ 1]边优先最短路径 ,在此形式下 ,不仅最短路径的形式唯一而且同一源节点到不同目的节点的最短路径之间存在递推关系 .给出了相应的递推公式 ,运用此公式 ,平均不到两次加法运算和一次比较即可找到源节点到所有其它节点的最短路径 .利用所得结果 ,源节点只需存储很少的信息就可以通过简单计算求得到任意其它节点的最短路径 .与传统方法相比 。

Double loop network is one of the most important topologies used in interconnection networks. The traditional methods of optimal routing for this topology are not optimal because they have not considered the relationship of shortest paths which have the same source node. A new concept, the link prior shortest path, is defined first. In this way, the shortest path between any two nodes is one and only. Also the link prior shortest paths which have the same source node can be expressed by a formula and can be calculated easily. In practice, a source node can record and store those 'abnormal' nodes, which link prior shortest path from that source node can't be obtained by adding one link to its next node's link prior shortest path from the same source node, and their link prior shortest paths. Using these results, a source node can find the link prior shortest path to any target node with much fewer arithmetic operations than traditional ways.