一类有向双环网络的最优单播路由算法

J4 ›› 2014, Vol. 36 ›› Issue (03): 458-462.

一类有向双环网络的最优单播路由算法

刘王飞,陈宝兴,岳昊

（漳州师范学院计算机科学与工程系，福建漳州 363000）

收稿日期:2012-09-24 修回日期:2012-12-19 出版日期:2014-03-25 发布日期:2014-03-25
基金资助:
国家自然科学基金资助项目（60973150）；福建省自然科学基金资助项目（2010J01354）

An optimal routing algorithm for a class of directed double loop network

LIU Wangfei，CHEN Baoxing，YUE Hao

（Department of Computer Science and Engineering,Zhangzhou Normal University,Zhangzhou 363000,China）

Received:2012-09-24 Revised:2012-12-19 Online:2014-03-25 Published:2014-03-25

摘要/Abstract

摘要：

有向双环网络G(N;1,h)(N是节点数，1和h是步长)是重要的互联网络结构。给出了有向双环网络G(N;1,h)的若干性质。作为这些性质的两个应用，给出一类有向双环网络的直径公式，以及这类有向双环网络的单播路由算法，这个算法是简单且最优的。

关键词: 有向双环网络, 最优路由, 非平常节点

Abstract:

Directed double loop network G(N;1,h), where N is the number of its nodes, 1 and h are its steps, is an important interconnection network. Some properties of G(N;1,h) are given. As two applications of these properties, a diameter formula for this network is given. An optimal and simple routing algorithm for a class of directed double loop network is also obtained.

Key words: directed double loop network;optimal routing, abnormal node

刘王飞,陈宝兴,岳昊. 一类有向双环网络的最优单播路由算法[J]. J4, 2014, 36(03): 458-462.

LIU Wangfei，CHEN Baoxing，YUE Hao. An optimal routing algorithm for a class of directed double loop network [J]. J4, 2014, 36(03): 458-462.

参考文献

［1］Li Qiao, Xu Junming, Zhang Zhongliang. Infinite families of optimal double loop networks［J］. Science in China, Series A, 1993, 23(9):979992. (in Chinese)
［2］Xu Junming. Designing of optimal double loop networks ［J］. Science in China, Series E, 1999, 29(3):272278. (in Chinese)
［3］Chen Yebin, Li Ying, Li Zhongkui. Methods to find optimal doubleloop networks［J］. Journal of System Simulation, 2011, 23(5):941943. (in Chinese)
［4］Chen Zhongxue, Jin Fan. On the ［+1］linkprior shortest path and optimal routing for doubleloop networks［J］. Journal of Computer Research and Development, 2001, 38(7):788792. (in Chinese)
［5］Fang Muyun, Qu Yugui, Zhao Baohua. ［+h］link prior routing strategy for doubleloop network［J］. Chinese Journal of Computers, 2008, 31(3):536542. (in Chinese)
［6］Feng Feiling, Jin Lingang. Characteristics analysis and routing control for a class of doubleloop networks［J］. Chinese Journal of Computers, 1994, 17(11):859865. (in Chinese)
［7］Chen B X, Xiao W J. A diameter formula for an undirected doubleloop network［J］. Ars Combinatoria, 2009, 90:395404.
附中文参考文献：
［1］李乔, 徐俊明, 张忠良. 最优双环网络的无限族［J］. 中国科学, A辑, 1993, 23(9):979992.
［2］徐俊明. 计算机互连双环网络的最优设计［J］. 中国科学, E辑, 1999, 29(3):272278.
［3］陈业斌, 李颖, 李中奎. 寻找紧优有向双环网络的方法［J］. 系统仿真学报, 2011, 23 (5):941943.
［4］陈忠学, 靳蕃. 双环网络［+1］边优先最短路径及其寻径策略［J］. 计算机研究与发展, 2001, 38(7):788792.
［5］方木云, 屈玉贵, 赵保华. 双环网络的［+h］边优先寻径策略［J］. 计算机学报, 2008, 31(3):536542.
［6］冯斐玲, 金林钢. 一类双环网的特征分析及寻径控制［J］. 计算机学报, 1994, 17(11):859865.