双环网络并行最优寻径策略及宽直径的研究

doi:10.3969/j.issn.1000-436x.2014.08.009

Abstract

Abstract:

A new method to research optimal parallel routing of unidirectional double-loop networks (DLN) is presented based on Cartesian coordinates. Firstly, the ditributed model of copy nodes is obtained under the research on the distrib-uted rules of the copy nodes of nodes on both X axis and Y axis in the minium distance diagram(MDD). Using this ditrib-uted model of copy nodes, the optimal parallel routing method is provided, as well as calculating method of wide diame-ter of DLN. Secondly, the parallel distance diagram(PDD) of DLN which is expanded by MDD is designed and simulated. Based on the PDD, a method to find two shortest parallel pathes quickly without any repeating node was proposed. At last, the simulation of the distribution of wide diameter of DLN is given. The result of simulation indicates that the character-istic of wide diameter distribution is reposeful undulation. Compared with traditional routing method, optimal parallel routing method improved the transition efficiency of DLN obviously based on the simulation results.

Key words: double-loop networks, parallel routing, parallel distance diagram, wide diameter

Hui LIU,Zhen ZHANG,Mu-yun FANG,GXiao ZHEN,Ye-bin CHEN. Research on optimal parallel routing and wide diameter of unidirectional double-loop networks[J]. Journal on Communications, 2014, 35(8): 63-70.

Figures/Tables 11

References 14

[1]	方木云，赵保华，屈玉贵 . 双环网络的[+h]边优先寻径策略[J]. 计算机学报， 2008,31(3):536-542. FANG M Y , ZHAO B H , QU Y G . [+h]-link prior routing strategy for dou-ble-loop network[J]. Chinese Journal of Computers, 2008,31(3):536-542.
[2]	陈协彬 . 步长有限制的双环网络的最优路由算法[J]. 计算机学报， 2004,27(5):596-603. CHEN X B . An optimal routing algorithm for double loop networks with restricted steps[J]. Chinese Journal of Computers, 2004,27(5): 596-603.
[3]	HWANG F K . A survey on multi-loop networks[J]. Computer Science, 2003 107-121.
[4]	HWANG F K . A complementary survey on double-loop networks[J]. Theoretical Computer Science, 2001,263: 211-229.
[5]	徐俊明 . 计算机互联双环网络的最优设计[J]. 中国科学(E 辑, 1999,42(5): 462-469. XU J M . Designing of optimal double loop networks[J]. Science in China(Series E), 1999,42(5): 462-469.
[6]	陈业斌，李颖，郑啸等. 关于有向环网平均直径的研究[J]. 通信学报， 2013,34(2):138-146. CHEN Y B , LI Y , ZHENG X et al. On the average diameter of di-rected loop networks[J]. Journal on Communications, 2013,34(2):138-146.
[7]	徐俊明，谢歆 . 关于图的容错直径和宽直径[J]. 中国科学技术大学学报， 2002,32(2):135-139. XU J M , XIE X . On fault-tolerant diameter and wide diameter of graphs[J]. Journal of University of Science and Technology of China, 2002,32(2):135-139.
[8]	HSU D F . et al. On container width and length in graphs, groups, and net-works[J]. IEICE Transaction on Fundamentals of Electronics, Com-munications and Computer Science, 1994,77(4): 668-680.
[9]	陈宝兴，杜妮，周书明 . 有向双环网络的宽直径公式[J]. 厦门大学学报(自然科学版)， 2008,47(6):782-786. CHEN B X , DU N , ZHOU S M . The wide diameter formula of a di-rected double loop network[J]. Journal of Xiamen University(Natural Science), 2008,47(6):782-786.
[10]	CHEN Y B , LI Y , WANG J K . On the wide diameter of directed dou-ble-loop networks[J]. Journal of Network and Computer Applications, 2011,34(1): 692-696.
[11]	刘辉，方木云 . 直角坐标系下无向双环网络 G(N;±1,±s)的直径研究[J]. 通信学报， 2011,32(1):138-143. LIU H , FANG M Y . Research on the diameter of bidirectional dou-ble-loop networks G(N; ±1, ±s) in Cartesian coordinates[J]. Journal on Communications. 2011,32(1):138-143.
[12]	WONG C K , COPPERHMITH D , . combinatorial problem related to multi-module memory organizations[J]. Journal of Association for Computing Machinery, 1974,21(3): 392-402.
[13]	刘焕平，杨义先，杨放春 . 双环网 G(N;s1,s2)的直径[J]. 系统工程理论与实践， 1999,19(2):58-61. LIU H P , YANG Y X , YANG F C . The diameter of double-loop net-works G(N; s1, s2)[J]. System Engineering Theory ＆ Practice, 1999,19(2):58-61.
[14]	CHEN C Y , HWANG F K . The minimum distance diagram of dou-ble-loop networks[J]. IEEE Transactions on Computers, 2000,49(9): 977-979.

Metrics

Recommended 0

No Suggested Reading articles found!

序号	N	r	h	直径	平均距离	宽直径
1	500	1	2	250	125	251
2	500	1	3	167	83.832	168
3	500	1	4	127	63.5	128
4	500	1	5	103	51.5	104
5	500	1	6	87	43.66	88
6	500	1	7	76	38.204	77
7	500	1	8	68	34.236	69
8	500	1	35	37	20.6	38
9	500	1	44	37	20.612	38
10	500	1	93	37	20.612	38
11	500	1	408	37	20.612	38
12	500	1	457	37	20.612	38
13	500	1	466	37	20.6	38

Research on optimal parallel routing and wide diameter of unidirectional double-loop networks

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 14

Related Articles 3

Metrics

Recommended 0

[1]	. Research on optimal parallel routing and wide diameter of unidirectional double-loop networks [J]. Journal on Communications, 2014, 35(8): 9-70.
[2]	Ye-bin CHEN,Ying LI,Xiao ZHENG,Tao CHEN. On the average diameter of directed loop networks [J]. Journal on Communications, 2013, 34(2): 138-146.
[3]	Hui LIU,Mu-yun FANG,Xiao ZHENG,Ting-ting HANG. Research on the diameter of bidirectional double-loop networks G(N;±1,±s)in cartesian coordinates [J]. Journal on Communications, 2011, 32(1): 138-143.