單源多徑路由網(wǎng)絡擁塞鏈路識別
doi: 10.11999/JEIT150058
-
1.
(電子科技大學通信與信息工程學院 成都 611731) ②(中國移動通信集團四川有限公司廣安分公司 廣安 638000)
基金項目:
國家自然科學基金(61171091, 61201127)和中央高校基本科研業(yè)務費(ZYGX2012J005)
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
-
摘要: 針對多徑路由帶來的端到端測量路徑不確定性以及布爾模型不能很好地解決多擁塞鏈路的問題,該文在識別端到端測量路徑的基礎上,提出一種基于擴展狀態(tài)空間的網(wǎng)絡擁塞鏈路識別算法。首先基于探測流時延相關性進行自適應聚類,進而得到各路徑與探測流之間的映射關系。其次采用多門限的方式,將具有不同丟包程度的擁塞路徑賦予不同的擁塞狀態(tài)。最后將擁塞鏈路識別問題轉化為一個約束最優(yōu)化問題,并提出基于擴展狀態(tài)空間的擁塞鏈路識別算法(ESSCLI)算法求解該問題。仿真結果表明,ESSCLI算法能夠在多種不同網(wǎng)絡場景下取得比當前算法更高的擁塞鏈路檢測率。
-
關鍵詞:
- 網(wǎng)絡測量 /
- 擁塞鏈路識別 /
- 網(wǎng)絡層析成像 /
- 多徑路由 /
- 最優(yōu)化
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. -
Castro R, Coates M, Liang G, et al.. Network tomography: recent developments[J]. Statistical Science, 2004, 19(3): 499-517. 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. 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. 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. 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. Wei W, Wang B, Towsley D, et al.. Model-based identification of dominant congested link[J]. IEEE/ACM Transactions on Networking, 2011, 19(2): 456-469. Duffield N. Network tomography of binary network performance characteristics[J]. IEEE Transactions on Information Theory, 2006, 52(12): 5373-5388. 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. 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. 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. Ghita D, Argyraki K, and Thiran P. Toward accurate and practical network tomography[J]. ACM SIGOPS Operating Systems Review, 2013, 47(1): 22-26. 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. Augustin B, Friedman T, and Teixeira R. Measuring multipath routing in the Internet[J]. IEEE/ACM Transactions on Networking, 2011, 19(3): 830-840. 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. 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. -
計量
- 文章訪問數(shù): 1252
- HTML全文瀏覽量: 115
- PDF下載量: 442
- 被引次數(shù): 0