一种对等网络中动态随机中继节点路由算法

系统仿真学报 ›› 2016, Vol. 28 ›› Issue (3): 711-719.

一种对等网络中动态随机中继节点路由算法

张成伟, 程文青, 黑晓军

华中科技大学电子与信息工程系,湖北武汉 430074

收稿日期:2014-06-28 修回日期:2014-10-28 发布日期:2020-07-02
作者简介:张成伟(1979-),男,湖北武汉,博士生,讲师,研究方向为覆盖网络路由及优化、网络测量;程文青(1964-),女,湖北武汉,教授,博导,研究方向为高速通信网络,教育信息化标准等。
基金资助:
国家自然科学基金(61370231);华中科技大学自主创新基金(HUST:2014TS099)

Dynamic Stochastic Relay Selection Algorithm in Peer-to-Peer Networks

Zhang Chengwei, Cheng Wenqing, Hei Xiaojun

Department of Electronics and Information Engineering, HuaZhong University of Science and Technology, Wuhan 430074, China

Received:2014-06-28 Revised:2014-10-28 Published:2020-07-02

摘要/Abstract

摘要： 提出了一种对等网络中继节点选择的随机路由算法,该算法应用随机规划框架,通过权衡本地路径真实时延以及非本地网络路径的时延统计分布,从而选择端到端期望时延最短的中继节点完成流量传输。随机中继路由算法可分布式实现,通过相邻节点动态更新路由的统计测量信息,相比于经典的静态路由算法能够获得更低的时延性能。为了更好地测量非本地网络覆盖路径的统计时延分布,路由算法拟合覆盖链路上的历史时延测量数据,并通过仿真实验表明,基于本算法建立的中继单路径/多路径可有效减少端到端路径时延和丢包率。

关键词: 随机中继路由, 网络测量, 对等网络, 覆盖路由

Abstract: A stochastic routing algorithm for selecting appropriate relay nodes in peer-to-peer networks was proposed. This algorithm was constructed using a stochastic programming framework by leveraging the actual delay of local links and the statistical delay distributions of non-local overlay links. In order to approximate the statistical delay distribution of non-local overlay links, the historical delay values of each link were utilized to approximate the link delay distribution. This algorithm was fully distributed and the stochastic link measurement data could be updated between neighboring nodes at a longer time granularity to reduce routing overhead. This algorithm and two other traditional algorithms were evaluated to find single and multiple overlay paths via relays between two end-hosts using simulation experiments. The experiment results demonstrate that this algorithm may achieve significant stochastic gain in terms of shorter delay and smaller packet loss than two routing algorithms including the deterministic shortest path algorithm and the minimum hop routing algorithm.

Key words: stochastic relay routing, network measurement, peer-to-peer network, overlay routing

中图分类号:

TP393.4

张成伟, 程文青, 黑晓军. 一种对等网络中动态随机中继节点路由算法[J]. 系统仿真学报, 2016, 28(3): 711-719.

Zhang Chengwei, Cheng Wenqing, Hei Xiaojun. Dynamic Stochastic Relay Selection Algorithm in Peer-to-Peer Networks[J]. Journal of System Simulation, 2016, 28(3): 711-719.

参考文献

[1] J Kurian, K Sarac.A Survey on the Design, Applications, and Enhancements of Application-layer Overlay Networks[J]. ACM Computing Surveys (S0360-0300), 2010, 43(1): 1-34.
[2] Y Cao, Z Sun.Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges[J]. IEEE Communications Surveys and Tutorials (S1553-877X). 2013, 1(2): 654-677.
[3] N Vastardis, K Yang.Mobile Social Networks: Architectures, Social Properties, and Key Research Challenges[J]. IEEE Communications Surveys and Tutorials (S1553-877X), 2013, 15(3): 1355-1371.
[4] P Dhungel, K W Ross, M Steiner, et al.Xunlei: Peer Assisted Download Acceleration on a Massive Scale[C]// Proc. of the 13th Int’l Conf. on Passive and Active Measurement (PAM)(S0302-9743), Vienna, Austria: LNCS, 2012.
[5] C Lumezanu, R Baden, N Spring, et al.Triangle Inequality and Routing Policy Violations in the Internet[C]// Proc. of the 9th Int’l Conf. on Passive and Active Measurement (PAM)(S03029743), Berlin Heidelberg, Germany: Springer, 2009: 45-54.
[6] V Bui, W Zhu, L T Bui.Optimal Relay Placement for Maximizing Path Diversity in Multipath Overlay Networks [C]// IEEE Global Telecommunications Conference (GLOBECOM) (S1930-529X), New Orleans, LA, USA: IEEE Press, 2008: 1544-1549.
[7] X Hei, H Song.Stochastic Relay Routing in Peer-to-Peer Networks [C]// Proc. of 2006 IEEE International Conference on Communications (ICC) (S0536-1486), Istanbul, Turkey. USA: IEEE Press, 2006: 1065-1070.
[8] C Zhang, X Hei, W Liu, et al.On Improving Dynamic Stochastic Routing Algorithms in Overlay Networks [C]// Proc. of the 18th IEEE Int’l Conf. on Networks (ICON) (S1556-6463), USA: IEEE Press, 2012: 447-452.
[9] A Vakili, J Gregoire.Accurate One-Way Delay Estimation: Limitations and Improvements[J]. IEEE Transactions on Instrumentation and Measurement (S0018-9456), 2012: 61(9): 2428-2435.
[10] IKR. University of Stuttgart, IKR Simlib Library 2.6. [EB/OL]. (2013-05-10) [2014-04-20]. http://www.ind. uni-stuttgart.de/INDSimLib/.
[11] T Nguyen, A Zakhor.Path Diversity with Forward Error Correction (pdf) System for Packet Switched Networks [C]// Proc. of IEEE INFOCOM (S0743-166X), San Francisco California, USA: IEEE Press, 2003: 663-672.
[12] A Mukherjee.On the Dynamics and Significance of Low Frequency Components of Internet Load[J]. Internet- working: Research and Experience (S1049-8915), 1992, 5(4): 163-205.