无标度网络局部信息的动态路由算法

韩定定; 柳康; 唐明

doi:10.3969/j.issn.1000-5641.2019.02.008

无标度网络局部信息的动态路由算法

doi: 10.3969/j.issn.1000-5641.2019.02.008

1.
复旦大学信息科学与工程学院, 上海 200433
2.
华东师范大学信息科学技术学院, 上海 200241

基金项目:

国家自然科学基金 11875133

详细信息

作者简介:
韩定定, 女, 教授, 博士生导师, 研究方向为复杂网络与智能信息处理.E-mail:ddhan@fudan.edu.cn

中图分类号: TP393
计量
- 文章访问数: 120
- HTML全文浏览量: 53
- PDF下载量: 156
- 被引次数: 0
出版历程
- 收稿日期: 2018-03-02
- 刊出日期: 2019-03-25

Dynamic routing algorithm based on local information in a free-scale network

1.
School of Information Science and Technology, Fudan University, Shanghai 200433, China
2.
School of Information Science and Technology, East China Normal University, Shanghai 200241, China

摘要

摘要: 提出了一个在无标度网络上基于局部信息的数据包路由算法，该路由算法引入两个可调参数α和β，分别调节度值与队列长度的路由偏好.通过调节这两个参数来改变网络的传输容量，并找到了该算法的最佳参数组合.对其他动态特性包括平均路由时间和流量负载也进行了相应研究.模拟仿真研究表明，该路由算法较传统的局部路由算法，不仅降低了网络的丢包率，而且提高了网络的传输能力.实证研究证明，基于局部信息的无标度网络动态路由算法对大规模通信网络的拥塞有一定的改善作用.
- 无标度网络 /
- 动态路由算法 /
- 局部信息 /
- 传输容量 /
- 拥塞
Abstract: We proposed a packet routing algorithm with two tunable parameters, α and β, which control the routing preference of degree and queue length, respectively, based on local information in a scale-free network. By adjusting the parameters to change network transmission capability, we found an optimal combination of the two parameters.Other dynamic properties, including average packet travel time and traffic load were also studied. Simulation research showed that the proposed algorithm not only reducedpacket loss rates, but also improved transmission capability and alleviated traffic congestion. We also compared the algorithm with other classical routing algorithms, based on real networks, and the proposed algorithm also displayed good results.
- scale-free network /
- dynamic routing algorithm /
- local information /
- transmission capability /
- congestion

HTML全文

图 1 网络的近邻与次近邻示意图

Fig. 1 Diagram of nearest-neighbor node and next-nearest-neighbor node

下载: 全尺寸图片幻灯片

图 2 DRNNN算法中数据包在网路传输的流程图

Fig. 2 Flow chart of data packet transmission in network based on DRNNN

下载: 全尺寸图片幻灯片

图 3 在不同$\alpha $与$\beta $参数下, 有序参量$\eta $和数据包生产率$R$之间的关系, 其中, $C=10$, $N=1~000$

Fig. 3 The order parameter $\eta $ as a function of the generating rate $R$ for different values of $\alpha $ and $\beta $, other parameters are $C=10$ and $N=1~000$

下载: 全尺寸图片幻灯片

图 4 不同$\alpha $, $\beta $参数组合下系统容量的分布图

Fig. 4 Distribution of the network capacity, $R$c, for different values of $\alpha $ and $\beta $

下载: 全尺寸图片幻灯片

图 5 系统中的数据包数目$W(t)$随时间$t$的变化, 其中$\alpha =-2$, $\beta=-1.6$

Fig. 5 Numbers of packets $W(t)$ in the system vs. time step $t$, here, $\alpha =-2$, $\beta =-1.6$

下载: 全尺寸图片幻灯片

图 6 在$\alpha =-2$, $\beta =-1.6$的情况下平均传输时间$T$随$R$的变化情况

Fig. 6 Average transmission time $T$ versus $R$ with $\alpha =-2$, $\beta =-1.6$

下载: 全尺寸图片幻灯片

图 7 度值$k$与平均队列长度(load)的关系, 这里$\alpha =-2$, $\beta =-1.6$

Fig. 7 The queue length of the nodes, load as a function of their degree $k$ with $\alpha=-2$, $\beta=-1.6$ for different $R$

下载: 全尺寸图片幻灯片

图 8 几种路由算法有序参量$\eta $的比较

Fig. 8 Comparing order parameter $\eta $ versus $R$ for different routing strategies

下载: 全尺寸图片幻灯片

表 1 不同网络平均度下丢包率

Tab. 1 Packet loss rate vs. average degree of network

$k$ PLR/%

4 74.3

6 36.5

8 12.6

10 3.3

下载: 导出CSV

表 2 不同网络平均度($k$)下不同路由算法丢包率的比较

Tab. 2 Packet loss rate on different average degree of network for different routing strategies ($k$)

$k$ PLR/%

传统的局部路由算法 DRNNN算法

10 3.3 0

8 12.6 0.00274

6 36.5 0.418

4 74.3 13.99

下载: 导出CSV

参考文献(15)

[1]	韩定定, 钱江海, 马余刚.实证研究复杂网络的拓扑与动力学行为[M].北京:北京大学出版社, 2012.
[2]	QIAN J H, CHEN Q, HAN D D, et al. Origin of Gibrat law in internet:Asymmetric distribution of the correlation[J]. Physical Review E, 2014, 89(6):062808. doi: 10.1103/PhysRevE.89.062808
[3]	FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On power-law relationships of the internet topology[J]. ACM Sigcomm Computer Communication Review, 1999, 29(4):251-262. doi: 10.1145/316194
[4]	SIGANOS G, FALOUTSOS M, FALOUTSOS P, et al. Power laws and the AS-level internet topology[J]. IEEE/ACM Transactions on Networking, 2003, 11(4):514-524. doi: 10.1109/TNET.2003.815300
[5]	CHEN Q, QiIAN J H, HAN D D. Non-Gaussian behavior of the internet topological fluctuations[J]. International Journal of Modern Physics C, 2014, 25(5):1440012. doi: 10.1142/S0129183114400129
[6]	韩定定, 柳康, 陈超, 等.基于空间活跃度网络的搜索算法研究[J].复杂系统与复杂性科学, 2017, 14(2):103-109. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=fzxtyfzxkx201702015
[7]	CHEN Q, QIAN J H, ZHU L, et al. Optimal temporal path on spatial decaying networks[J]. Journal of Applied Analysis & Computation, 2016, 6(1):30-37. http://www.irgrid.ac.cn/handle/1471x/1119342?mode=full&submit_simple=Show+full+item+record
[8]	CHEN Q, QIAN J H, ZHU L, et al. Optimal transport in time-varying small-world networks[J]. Physical Review E, 2016, 93(3):032321. doi: 10.1103/PhysRevE.93.032321
[9]	GUIMERÀ R, ARENAS A, DÍAZGUILERA A, et al. Dynamical properties of model communication networks[J]. Physical Review E, 2002, 66(2 Pt 2):026704. https://www.ncbi.nlm.nih.gov/pubmed/12241315
[10]	ZHAO L, LAI Y C, PARK K, et al. Onset of traffic congestion in complex networks[J]. Physical Review E, 2005, 71(2):026125. doi: 10.1103/PhysRevE.71.026125
[11]	KRIOUKOV D, FALL K, YANG X. Compact routing on internet-like graphs[C]//IEEE Conference on Computer Communications. IEEE, 2004: 209-219.
[12]	WANG W X, WANG B H, YIN C Y, et al. Traffic dynamics based on local routing protocol on a scale-free network[J]. Physical Review E, 2006, 73(2):026111. doi: 10.1103/PhysRevE.73.026111
[13]	WANG W X, YIN C Y, YAN G, et al. Integrating local static and dynamic information for routing traffic[J]. Physical Review E, 2006, 74(2):016101. doi: 10.1103-PhysRevE.74.016101/
[14]	BARABÁSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 5439(286):509-512. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_cond-mat%2f0001459
[15]	TAN F, WU J, XIA Y, et al. Traffic congestion in interconnected complex networks[J]. Physical Review E, 2014, 89(6):062813. doi: 10.1103/PhysRevE.89.062813