Internet路由器随机建模与收敛性分析

周军; 张健; 杨顺枫

doi:10.21656/1000-0887.420026

Internet路由器随机建模与收敛性分析

doi: 10.21656/1000-0887.420026

周军^{1, 2,},
张健¹,
杨顺枫^1, ,

1.
西南林业大学数理学院，昆明 650224
2.
东华大学信息科学与技术学院，上海 201620

基金项目: 云南省基础研究计划（202001AT070112）

详细信息

作者简介:
周军（1980—），男，讲师，博士（E-mail：zhouchaos@126.com）

杨顺枫（1982—），男，讲师，博士（通讯作者. E-mail：yangshunfeng@126.com）

中图分类号: TP393
计量
- 文章访问数: 787
- HTML全文浏览量: 233
- PDF下载量: 28
- 被引次数: 0
出版历程
- 收稿日期: 2021-01-27
- 录用日期: 2021-01-27
- 修回日期: 2021-05-26
- 网络出版日期: 2022-01-10
- 刊出日期: 2022-02-01

Stochastic Modeling and Convergence Analysis of Internet Routers

ZHOU Jun^{1, 2
,},
ZHANG Jian¹,
YANG Shunfeng^{1
, ,}

1.
School of Mathematics and Physics, Southwest Forestry University, Kunming 650224, P.R.China
2.
College of Information Science and Technology, Donghua University, Shanghai 201620, P.R.China

摘要

摘要:
目前建立的路由收敛模型大部分都是确定性模型，而路由器在收敛过程中存在丢包、链路噪声、互连拓扑结构突变等现象。针对这些随机问题，该文引入Bernoulli白序列分布、Wiener过程、Markov过程，提出了一种新的随机动力系统模型，应用随机微分方程理论和随机分析方法得出其路由收敛的充分条件，结果证明，随机环境下路由状态收敛与路由器连接拓扑的Laplace矩阵、Markov切换的平稳分布、网络中数据包的成功传输率以及噪声强度息息相关。最后通过一个数值实例验证了相关结论的有效性。
- 路由收敛 /
- Gauss白噪声 /
- Laplace矩阵 /
- Markov切换 /
- Itô 公式
Abstract:
The existent route convergence models are mainly deterministic ones, and various phenomena, such as packet losses, link noises, and sudden changes in interconnecting topology will occur in the route convergence process. Aimed at these random problems, a new stochastic dynamic system model was proposed by means of the Bernoulli white sequence distribution, the Wiener process and the Markov process. Based on the stochastic differential equation theory and the stochastic analysis methods, the sufficient conditions for the route convergence were given. The results prove that, the convergence of the routing state in a random environment is closely related to the Laplacian matrix of the router connection topology, the smooth distribution of the Markov switching, the successful transmission rate of the data packets, and the noise intensity in the network. Finally, a numerical example illustrates the effectiveness of the results.
- route convergence /
- white Gaussian noise /
- Laplacian matrix /
- Markov switching /
- Itô formula

HTML全文

图 1 路由设备网络连接拓扑图

Figure 1. The router connection topology

下载: 全尺寸图片幻灯片

图 2 2-状态Markov链

Figure 2. The 2-state Markov chain

下载: 全尺寸图片幻灯片

图 3 5个路由器路由状态第1个分量

Figure 3. The 1st element of the 5-router state

下载: 全尺寸图片幻灯片

图 4 5个路由器路由状态第2个分量

Figure 4. The 2nd element of the 5-router state

下载: 全尺寸图片幻灯片

图 5 5个路由器路由状态第3个分量

Figure 5. The 3rd element of the 5-router state

下载: 全尺寸图片幻灯片

参考文献(15)

[1]	GRIFFIN T G, SHEPHERD F B, WILFONG G. The stable paths problem and interdomain routing[J]. IEEE/ACM Transactions on Networking, 2002, 10(2): 232-243. doi: 10.1109/90.993304
[2]	张微, 吴建平, 徐恪, 等. 边界网关协议BGP4路由收敛问题研究进展[J]. 小型微型计算机系统, 2006, 27(5): 818-824. (ZHANG Wei, WU Jianping, XU Ke, et al. Research progress of convergence problem of border gateway protocol 4 (BGP4)[J]. Mini-Micro Systems, 2006, 27(5): 818-824.(in Chinese) doi: 10.3969/j.issn.1000-1220.2006.05.012
[3]	LABOVITZ C, AHUJA A, WATTENHOFER R, et al. The impact of Internet policy and topology on delayed routing convergence[C]//Proceedings IEEE INFOCOM 2001 Conference on Computer Communications. 2001.
[4]	赵金晶, 朱培栋, 周丽涛. 域间路由协议BGP收敛时间的定量分析及预测[J]. 计算机工程与科学, 2007, 29(9): 56-57. (ZHAO Jinjing, ZHU Peidong, ZHOU Litao. Analysis and prediction on the BGP convergence time[J]. Computer Engineering and Science, 2007, 29(9): 56-57.(in Chinese) doi: 10.3969/j.issn.1007-130X.2007.09.016
[5]	张昕, 赵海, 李超. 一种基于多项复杂特征的Internet 路由级拓扑建模方法[J]. 电子学报, 2008, 36(1): 57-63. (ZHANG Xin, ZHAO Hai, LI Chao. A model for router-level topology of Internet based on complex characters[J]. Acta Electronica Sinica, 2008, 36(1): 57-63.(in Chinese) doi: 10.3321/j.issn:0372-2112.2008.01.010
[6]	李鹤帅, 朱俊虎, 王清贤, 等. Internet建模的关键: 研究AS间路由器级连接[J]. 计算机科学, 2016, 43(9): 135-139. (LI Heshuai, ZHU Junhu, WANG Qingxian, et al. Key of Internet modeling-looking inside inter-AS router-level connection[J]. Computer Science, 2016, 43(9): 135-139.(in Chinese) doi: 10.11896/j.issn.1002-137X.2016.09.026
[7]	PIETRABISSA A, CELSI L R. Discrete-time selfish routing converging to the wardrop equilibrium[J]. IEEE Transactions on Automatic Control, 2019, 64(3): 1288-1294. doi: 10.1109/TAC.2018.2847602
[8]	SUN G, BIN S. Router-level Internet topology evolution model based on multi-subnet composited complex network model[J]. Journal of Internet Technology, 2017, 18(6): 1-8.
[9]	ABDULKADHIM M. Routing protocols convergence activity and protocols related traffic simulation with it’s impact on the network[J]. International Journal of Computer Science Engineering and Technology, 2015, 5(3): 40-43.
[10]	RABBANI H, BEYGI L, GHOSHOONI S, et al. Quality of transmission aware optical networking using enhanced Gaussian noise model[J]. Journal of Lightwave Technology, 2019, 37(3): 831-838. doi: 10.1109/JLT.2018.2881607
[11]	赵玮, 任凤丽. 基于牵制控制的多智能体系统的有限时间与固定时间一致性[J]. 应用数学和力学, 2021, 42(3): 299-307. (ZHAO Wei, REN Fengli. Finite-time and fixed-time consensus for multi-agent systems via pinning control[J]. Applied Mathematics and Mechanics, 2021, 42(3): 299-307.(in Chinese)
[12]	ZHOU J, CAI T T, ZHOU W N, et al. Master-slave synchronization for coupled neural networks with Markovian switching topologies and stochastic perturbation[J]. International Journal of Robust and Nonlinear Control, 2018, 28(6): 2249-2263. doi: 10.1002/rnc.4013
[13]	NI W, CHEN D. Leader-following consensus of multi-agent systems under fixed and switching topologies[J]. System and Control Letters, 2010, 59(3/4): 209-217.
[14]	MAO X R, YUAN C G. Stochastic Differential Equations With Markovian Switching[M]. London: Imperial College Press, 2006.
[15]	马丽, 马瑞楠. 一类随机泛函微分方程带随机步长的EM逼近的渐近稳定[J]. 应用数学和力学, 2019, 40(1): 97-107. (MA Li, MA Ruinan. Almost sure asymptotic stability of the Euler-Maruyama method with random variable stepsizes for stochastic functional differential equations[J]. Applied Mathematics and Mechanics, 2019, 40(1): 97-107.(in Chinese) doi: 10.1007/s10483-019-2403-6