计算机工程 ›› 2015, Vol. 41 ›› Issue (1): 92-95.doi: 10.3969/j.issn.1000-3428.2015.01.017

• 移动互联与通信技术 • 上一篇    下一篇

有向双环网络最优路由算法

刘辉,张珍,彭慧子,方木云   

  1. 安徽工业大学计算机科学与技术学院,安徽 马鞍山 243002
  • 收稿日期:2014-01-09 修回日期:2014-03-26 出版日期:2015-01-15 发布日期:2015-01-16
  • 作者简介:刘 辉(1979-),男,副教授,主研方向:数据处理;张 珍、彭慧子,硕士;方木云,教授、博士。
  • 基金项目:
    国家自然科学基金资助项目(61003311);安徽省教育厅基金资助重点项目(KJ2012A262,KJ2013A058)

Optimal Routing Algorithm for Unidirectional Double Loop-network

LIU Hui,ZHANG Zhen,PENG Huizi,FANG Muyun   

  1. School of Computer Science and Technology,Anhui University of Technology,Maanshan 243002,China
  • Received:2014-01-09 Revised:2014-03-26 Online:2015-01-15 Published:2015-01-16

摘要: 最优路由的研究对于网络节点的传输具有重要意义,但关于有向双环网络节点的最优路由研究,目前尚无统一的算法。现有有向双环网络的最优路由算法,主要集中在单位步长双环网络及一些特殊双环网络上,对于为数较多的非单位步长有向双环网络最优路由的研究较少。已知有向双环网络的MDD图形为L形瓦,基于L形瓦参数设计提出一种通用的有向双环网络最优路由算法。该算法适用于单位步长和非单位步长有向双环网络。仿真结果表明,与基于[+h]边优先路由及基于二叉树的最优路由算法相比,该算法无需建造竹筏及二叉树的空间,执行效率明显提高。

关键词: 有向双环网络, 路由算法, 最优路由, 最短路径, L形瓦, 对称

Abstract: Research on the optimal routing is significant for the transmission between network nodes,and there is no clear unified,efficient algorithms for the research on the optimal routing of Double-loop Network(DLN).Currently,research focuses on the optimal routing of the unit-step and some kind of special DLN,has little work on the non-unit step Unidirectional Double-loop Network(UDLN) which have a greater number.This paper gives general optimal routing algorithm between any two nodes for UDLN on the four parameters of L-shape tile since the Minimum Distance Diagram (MDD) of UDLN is known as L-shape tile,which is suitable for both unit-step and non-unit step UDLN,achieving the unity of optimal routing of directed double-loop network algorithm.Specially,the optimal algorithm for unit-step UDLN is improved based on the general routing algorithm.Compared with [+h] link prior routing algorithm and bintree optimal routing algorithm,the algorithm doesnot need space to build bamboo raft or bintree and efficiency of the algorithm is better than other algorithms.Simulation experiments show the validity of the algorithm.

Key words: unidirectional Double-loop Network(DLN), routing algorithm, optimal routing, shortest paths, L-shape tile, symmetry

中图分类号: