单源多径路由网络拥塞链路识别

潘胜利; 杨析儒; 张志勇; 钱峰; 胡光岷

doi:10.11999/JEIT150058

单源多径路由网络拥塞链路识别

doi: 10.11999/JEIT150058

1.
(电子科技大学通信与信息工程学院成都 611731) ②(中国移动通信集团四川有限公司广安分公司广安 638000)

基金项目:

国家自然科学基金(61171091, 61201127)和中央高校基本科研业务费(ZYGX2012J005)

计量
- 文章访问数: 608
- HTML全文浏览量: 57
- PDF下载量: 428
- 被引次数: 0
出版历程
- 收稿日期: 2015-01-12
- 修回日期: 2015-05-11
- 刊出日期: 2015-09-19

Congestion Link Identification under Multipath Routing for Single-source Networks

1.
(School of Communication and Information Engineering, University of Electronic Science and Technology of China,
2.
(Guangan Branch, Sichuan Co., Ltd, China Mobile Group, Guang&rsquo

摘要

摘要: 针对多径路由带来的端到端测量路径不确定性以及布尔模型不能很好地解决多拥塞链路的问题，该文在识别端到端测量路径的基础上，提出一种基于扩展状态空间的网络拥塞链路识别算法。首先基于探测流时延相关性进行自适应聚类，进而得到各路径与探测流之间的映射关系。其次采用多门限的方式，将具有不同丢包程度的拥塞路径赋予不同的拥塞状态。最后将拥塞链路识别问题转化为一个约束最优化问题，并提出基于扩展状态空间的拥塞链路识别算法(ESSCLI)算法求解该问题。仿真结果表明，ESSCLI算法能够在多种不同网络场景下取得比当前算法更高的拥塞链路检测率。
- 网络测量 /
- 拥塞链路识别 /
- 网络层析成像 /
- 多径路由 /
- 最优化
Abstract: Regarding the uncertainty introduced by load balancing when determining which end-to-end path is measured and that the classical Boolean model is not well developed for the scenario of multiple congestion links, this paper bases on the identification of end-to-end probing paths and proposes an enlarged state space based congestion link identification algorithm. Firstly, the mapping relationship between the probing flows and the measured paths is obtained after performing adaptive clustering on the probing flows with their delay correlation measures. Secondly, with multiple thresholds, it is able to assign a path with a different congestion state according to its different loss rate levels. Lastly, the issue of the congestion link identification is modeled as a constrained optimization problem, and is solved with Enlarged State Space based Congestion Link Identification (ESSCLI) algorithm. The simulation results demonstrate that ESSCLI can achieve a better detection rate of the congestion link in various network scenarios compared with existing algorithms.
- Network measurement /
- Congestion link identification /
- Network tomography /
- Multipath routing /
- Optimization

HTML全文

参考文献(16)

[1]	Castro R, Coates M, Liang G, et al.. Network tomography: recent developments[J]. Statistical Science, 2004, 19(3): 499-517.
[2]	Duffield N and Presti F. Network tomography from measured end-to-end delay covariance[J]. IEEE/ACM Transactions on Networking, 2004, 12(6): 978-992.
[3]	Duffield N, Presti F, Paxson V, et al.. Inferring link loss using striped unicast probes[C]. Proceedings of IEEE INFOCOM, Anchorage, 2001, 2: 915-923.
[4]	Coates M, Castro R, Nowak R, et al.. Maximum likelihood network topology identification from edge-based unicast measurements[C]. Proceedings of ACM SIGMETRICS, Marina Del Rey, 2003: 11-20.
[5]	Malekzadeh A and MacGregor M. Network Topology inference from end-to-end measurements[C]. the 27th IEEE Advanced Information Networking and Applications Workshops, Barcelona, 2013: 1101-1106.
[6]	Wei W, Wang B, Towsley D, et al.. Model-based
[7]	identification of dominant congested link[J]. IEEE/ACM Transactions on Networking, 2011, 19(2): 456-469.
[8]	Duffield N. Network tomography of binary network performance characteristics[J]. IEEE Transactions on Information Theory, 2006, 52(12): 5373-5388.
[9]	Matsuda T, Nagahara M, and Hayashi K. Link quality classifier with compressed sending based on optimization[J]. IEEE Communications Letters, 2011, 15(10): 1117-1119.
[10]	Ma L, He T, Leung K, et al.. Monitor placement for maximal identifiability in network tomography[C]. Proceedings of IEEE INFOCOM, Toronto, 2014: 1447-1455.
[11]	Eriksson B, Dasarathy G, Barford P, et al.. Efficient network tomography for Internet topology discovery[J]. IEEE/ACM Transactions on Networking, 2012, 20(3): 931-943.
[12]	Ghita D, Argyraki K, and Thiran P. Toward accurate and practical network tomography[J]. ACM SIGOPS Operating Systems Review, 2013, 47(1): 22-26.
[13]	Dhamdhere A, Teixeira R, and Dovrolis C, et al.. NetDiagnoser: troubleshooting network unreachabilities using end-to-end probes and routing data[C]. Proceedings of ACM CoNEXT, New York, 2007: 18.
[14]	Augustin B, Friedman T, and Teixeira R. Measuring multipath routing in the Internet[J]. IEEE/ACM Transactions on Networking, 2011, 19(3): 830-840.
[15]	Pan S, Zhang Z, Yu F, et al.. End-to-end measurements for network tomography under multipath routing[J]. IEEE Communications Letters, 2014, 18(5): 881-884.
[16]	Pelleg D and Moore A. X-means: extending k-means with efficient estimation of the number clusters[C]. Proceedings of ICML, Stanford, 2000: 727-734.

相关文章(20)

[1]	孟洛明, 孙康, 韦磊, 郭少勇, 徐思雅. 一种面向电力无线专网的虚拟资源优化分配机制, 电子与信息学报. doi: 10.11999/JEIT161043
[2]	曹龙, 赵杭生, 鲍丽娜, 张建照. 分层认知无线电网络中基于稳定匹配的资源分配算法, 电子与信息学报. doi: 10.11999/JEIT151460
[3]	张冰尘, 王万影, 毕辉, 赵曜, 洪文. 基于压缩多信号分类算法的森林区域极化SAR层析成像, 电子与信息学报. doi: 10.11999/JEIT140584
[4]	伊鹏, 钱坤, 黄万伟, 王晶, 张震. 基于抽样流长与完全抽样阈值的异常流自适应抽样算法, 电子与信息学报. doi: 10.11999/JEIT141379
[5]	潘甦, 曹跑跑, 刘胜美. 一种多无线电系统中基于公平性和精细化带宽分配的资源分配算法, 电子与信息学报. doi: 10.11999/JEIT140339
[6]	侯颖, 黄海, 兰巨龙, 李鹏, 朱圣平. 基于自适应超时计数布鲁姆过滤器的流量测量算法, 电子与信息学报. doi: 10.11999/JEIT140820
[7]	王晶, 汪斌强, 张校辉. 基于可重构测量模型的网络测量任务部署算法, 电子与信息学报. doi: 10.11999/JEIT141336
[8]	王聪, 张凤荔, 王瑞锦, 李敏, 杨晓翔. 一种网络时延矩阵分布式自适应重建算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00960
[9]	杨京礼, 孙超, 姜守达, 魏长安. 基于层次分解的网络链路时延分布快速推测算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01455
[10]	王聪, 张凤荔, 杨晓翔, 李敏, 王瑞锦. 支持入侵容忍的网络距离选举计算模型, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01402
[11]	张福博, 刘梅. 基于频域最小二乘APES的非均匀多基线SAR层析成像算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.01184
[12]	左勇, 刘学勇, 刘海洋, 陈杰. 基于对偶分解的OFDMA系统资源分配算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00326
[13]	杨京礼, 许永辉, 姜守达. 基于最小覆盖集的高精度链路丢包率测量方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00924
[14]	顾然, 邱雪松, 乔焰, 李娟, 孟洛明. 基于非线性规划的链路丢包率推理算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.01052
[15]	张志勇, 胡光岷. 一种新的故障链路识别算法RPI, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.01224
[16]	费高雷, 胡光岷. 基于k阶马尔可夫链的单播网络丢包层析成像, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.00814
[17]	费高雷, 胡光岷, 钱峰. 一种非平稳网络链路丢包率层析成像方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2009.00186
[18]	刘永广, 叶梧, 冯穗力. 一种基于信道阻力的Ad hoc网络多路径路由算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2007.01584
[19]	刘湘雯, 于宏毅, 侯惠峰, 胡捍英. 基于概率可通链路的无线传感器网络栅格路由, 电子与信息学报. doi: 10.3724/SP.J.1146.2007.00337
[20]	刘红, 白栋, 丁炜. 一种MPLS网络拥塞最小化的全局路由优化算法, 电子与信息学报.