关于有向环网平均直径的研究

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

摘要/Abstract

摘要：

摘要：根据有向双环网络平均直径与其最小路径图（L-型瓦）4个几何参数（a、b、p和q）之间的关系，提供了平均直径的计算公式，并提供了快速计算平均直径的算法。提供了构造有向三环网络的最小路径图（等价树）的新方法，研究了三环网络的任意2点之间的最短路径与等价树的层之间的关系，给出了三环网络平均直径的计算公式和算法。实验结果表明：同一网络的平均直径约为直径的一半；在一个无限族中，直径达到最小值时平均直径不一定为最小值，但平均直径为最小值时直径一定为最小值。研究表明平均直径比直径更能准确地反映环网的传输效率，所以平均直径应成为设计最优网络重要的依据之一。

关键词: 平均直径, 直径, 双环网络, 三环网络, L-型瓦, 最短路径, 最小路径图

Abstract:

The formula of average diameter about directed double-loop networks was presented according to the relationship between average diameter and four geometric parameters (a,b,p and q) of its minimum distance diagram (L-shaped tile)，and a rapid algorithm to compute the average diameter was presented.A novel method to construct the minimum distance diagram (equivalent tree) of triple loop networks was presented,and the relationships between the layer of the equivalent tree and the shortest path of any two points in triple loop networks was studied,and a formula and a algorithm to compute its average diameter was provided.The experimental results show that average diameter approaches to a half of the diameter at the same network,in one infinite family,the diameter must obtain minimum value when average diameter obtains minimum value,but the inverse is not.Studies show that average diameter is the better parameter to measure transmission efficiency about loop networks instead of diameter,so average diameter should become one of important bases to design the optimal networks.

Key words: average diameter, diameter, double-loop networks, triple-loop networks, L-shaped tile, shortest path, minimum distance diagram

陈业斌,李颖,郑啸,陈涛. 关于有向环网平均直径的研究[J]. 通信学报, 2013, 34(2): 138-146.

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.

图/表 6

图1

图2

图3

表1

G(50;1,s)和G(50;1,s,49)的直径和平均直径对照"

s		d₂(50)		${\bar{d}}_{2} (50)$		d₃(50)		${\bar{d}}_{3} (50)$
	2		25		12.5		17		8.7
	3		17		8.82		13		6.9
	4		14		7.22		11		5.8
	5		13		6.5		10		5.2
	6		12		6.1		9		4.9
	7		12		6.02		9		4.7
	8		12		6.02		8		4.5
	9		12		6.1		9		4.6
	10		13		6.5		8		4.5
	11		13		6.5		9		4.6
	12		12		6.1		8		4.7
	13		14		7.22		9		4.7
	14		11		6.06		8		4.5
	15		11		5.9		9		4.7
	16		13		6.5		10		5.2
	17		11		8.82		10		5.2
	18		14		7.22		9		4.9
	19		11		5.9		9		4.6
	20		13		6.5		8		4.4
	21		13		6.5		9		4.6
	22		11		5.9		8		4.6
	23		11		6.06		10		5.2
	24		14		7.22		13		6.9
25		25		12.5		13		6.9

表1

图4

图5

参考文献 18

[1]	WONG C K , COPPERSMITH D . A combinatorial problem related to multimodule organizations[J]. J Assoc Computer, 1974,21(3): 392-402.
[2]	CHEN C Y , HWANG F K . The minimum distance diagram of double-loop networks[J]. IEEE Transactions on Computers, 2000,49(9): 977-979.
[3]	CHEN C Y , JAMES K L , TANG W H . An efficient algorithm to find a double-loop network that realizes a given L-shape[J]. Theoretical Computer Science , 2006,359(1-3): 69-76.
[4]	AGUILO F , FIOL M A . An efficient algorithm to find optimal double loop networks[J]. Discrete Mathematics, 1995,138(1-3): 15-29.
[5]	CHEN B X , XIAO W J . Optimal designs of directed double-loop networks[A]. Lecture Notes in Computer Science (LNCS)[C]. Berlin,Germany: Springer Verlag, 2004. 19-24.
[6]	周建钦 . 关于 K 紧优双环网络[J]. 中国科学技术大学学报, 2005,35(6): 738-742. ZHOU J Q . On K-tight optimal double-loop networks[J]. Journal of University of Science and Technology of China, 2005,35(6): 738-742.
[7]	方木云, 赵保华, 屈玉贵 . 双环网络G(N;1,s)的L形瓦仿真算法[J]. 系统仿真学报. 2005,17(4): 914-916. FANG M Y , ZHAO B H , QU Y G . An algorithm to simulate the L-shaped tile of double-loop networks G(N;1,s)[J]. Journal of System Simulation, 2005,17(4): 914-916.
[8]	GOMEZ D , GUTIERREZ J , IBEAS A . Optimal routing in double loop networks[J]. Theoretical Computer Science, 2007,381(1-3): 68-85.
[9]	CHEN Y B , LI Y , WANG J K . On the wide diameter of directed double-loop network[J]. Journal of Network and Computer Applications, 2011,34(2): 692-696.
[10]	DHARMASENA , HETTEHE P , XIN Y . An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks[J]. IEEE Transactions on Parallel ＆ Distributed Systems, 2005,16(9): 841-852.
[11]	陈业斌, 王建堃, 李颖 . 有向双环网络的容错路由及容错直径[J]. 华中科技大学学报（自然科学版）, 2010,38(2): 12-15. CHEN Y B , WANG J K , LI Y . Fault-tolerant routing and diameters of directed double-loop networks[J]. Journal of Huazhong University of Science and Technology（Natural Science Edition）, 2010,38(2): 12-15.
[12]	方木云, 汤红霞 . 非单位步长双环网络平均直径的研究[J]. 华中科技大学学报（自然科学版）, 2009,37(6): 12-15. FANG M Y , TANG H X . A survey on the average diameter of double-loop networks with non-unit step[J]. Journal of Huazhong University of Science and Technology（Natural Science Edition）, 2009,37(6): 12-15.
[13]	边琼芳, 姜太平, 刘辉 ,等. 双环网络平均直径的研究[J]. 安徽工业大学学报（自然科学版）, 2011,28(3): 277-281. BIAN Q F , JIANG T P , LIU H ,et al. Survey on the average diameter of double-loop networks[J]. J of Anhui University of Technology（Natural Science）, 2011,28(3): 277-281.
[14]	AGUILO F , FIOL M A , GARCIA C . Triple-loop networks with small transmission delay[J]. Discrete Math, 1997,15(4): 3-16.
[15]	CHEN C Y , HUNG C S , TANG W S . On the existence of hyper-L triple-loop networks[J]. Discrete Math, 2006,306(12): 1132-1138.
[16]	邰伟鹏, 方木云, 徐宏 . 三环网络 TL(N;1,s,s+1)超 L-型瓦仿真算法[J]. 华中科技大学（自然科学版）, 2010,38(8): 50-52. TAI W P , FANG M Y , XU H . Algorithm to simulate the hyper L-shaped tile for triple-loop networks TL(N;1,s,s+1)[J]. Journal of Huazhong University of Science and Technology（Natural Science Edition）, 2010,38(8): 50-52.
[17]	侯新民, 王天明 . 分布式三环网络传输延迟[J]. 大连理工大学学报, 2002,42(1): 9-12. HOU X M , WANG T M . On the transmission delay of distributed triple loop networks[J]. Journal of Dalian University of T hnology, 2002,42(1): 9-12.
[18]	陈业斌 . 基于二叉树的有向双环网络最短路径算法[J]. 华中科技大学学报（自然科学版）, 2009,37(4): 78-81. CHEN Y B . Bintree-based shortest path algorithm of directed double-loop networks[J]. Journal of Huazhong University of Science and Technology（Natural Science Edition）, 2009,37(4): 78-81.