首页 | 官方网站   微博 | 高级检索  
     

双环网络[+1]边优先最短路径及其寻径策略
引用本文:陈忠学,靳蕃.双环网络[+1]边优先最短路径及其寻径策略[J].计算机研究与发展,2001,38(7):788-792.
作者姓名:陈忠学  靳蕃
作者单位:西南交通大学计算机与通信工程学院
摘    要:双环网络是一种非常重要的互联网络结构 .传统的最优寻径方法没有充分利用这一网络中同一节点到不同节点的最短路径之间的关系 ,所给的算法不是最优的 .定义了双环网络的一种最短路径—— + 1]边优先最短路径 ,在此形式下 ,不仅最短路径的形式唯一而且同一源节点到不同目的节点的最短路径之间存在递推关系 .给出了相应的递推公式 ,运用此公式 ,平均不到两次加法运算和一次比较即可找到源节点到所有其它节点的最短路径 .利用所得结果 ,源节点只需存储很少的信息就可以通过简单计算求得到任意其它节点的最短路径 .与传统方法相比 ,本算法提高了系统的寻径效率

关 键 词:双环网络  最短路径  最优寻径  [+1]边优先最短路径  单一[+h]边最短路径
修稿时间:2000年7月3日

ON THE [+1]-LINK-PRIOR SHORTEST PATH AND OPTIMAL ROUTING FOR DOUBLI-LOOP NETWORKS
CHEN Zhong,Xue and JIN Fan.ON THE [+1]-LINK-PRIOR SHORTEST PATH AND OPTIMAL ROUTING FOR DOUBLI-LOOP NETWORKS[J].Journal of Computer Research and Development,2001,38(7):788-792.
Authors:CHEN Zhong  Xue and JIN Fan
Abstract: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.
Keywords:double  loop network  shortest path  optimal routing    link  prior shortest path    single  link shortest path
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号