华东师范大学学报（自然科学版） >

2019 , Vol. 2019 >Issue 2: 69 - 76,96

DOI: https://doi.org/10.3969/j.issn.1000-5641.2019.02.008

计算机科学

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

  • 韩定定 ,
  • 柳康 ,
  • 唐明
展开
  • 1. 复旦大学 信息科学与工程学院, 上海 200433;
    2. 华东师范大学 信息科学技术学院, 上海 200241
韩定定,女,教授,博士生导师,研究方向为复杂网络与智能信息处理.E-mail:ddhan@fudan.edu.cn.

收稿日期: 2018-03-02

  网络出版日期: 2019-03-27

基金资助

国家自然科学基金（11875133）

收起

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

  • HAN Ding-ding ,
  • LIU Kang ,
  • TANG Ming
Expand
  • 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

Received date: 2018-03-02

  Online published: 2019-03-27

Fold

摘要

提出了一个在无标度网络上基于局部信息的数据包路由算法，该路由算法引入两个可调参数α和β，分别调节度值与队列长度的路由偏好.通过调节这两个参数来改变网络的传输容量，并找到了该算法的最佳参数组合.对其他动态特性包括平均路由时间和流量负载也进行了相应研究.模拟仿真研究表明，该路由算法较传统的局部路由算法，不仅降低了网络的丢包率，而且提高了网络的传输能力.实证研究证明，基于局部信息的无标度网络动态路由算法对大规模通信网络的拥塞有一定的改善作用.

关键词： 无标度网络; 动态路由算法; 局部信息; 传输容量; 拥塞

本文引用格式

韩定定 , 柳康 , 唐明 . 无标度网络局部信息的动态路由算法[J]. 华东师范大学学报（自然科学版）, 2019 , 2019(2) : 69 -76,96 . DOI: 10.3969/j.issn.1000-5641.2019.02.008

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.

Key words： scale-free network; dynamic routing algorithm; local information; transmission capability; congestion

参考文献

[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.
[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.
[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.
[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.
[6] 韩定定, 柳康, 陈超, 等. 基于空间活跃度网络的搜索算法研究[J]. 复杂系统与复杂性科学, 2017, 14(2):103-109.
[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.
[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.
[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.
[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.
[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.
[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.
[14] BARABÁSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 5439(286):509-512.
[15] TAN F, WU J, XIA Y, et al. Traffic congestion in interconnected complex networks[J]. Physical Review E, 2014, 89(6):062813.
Options
文章导航

/

〈 〉