›› 2016, Vol. 31 ›› Issue (2): 350-358.doi: 10.1007/s11390-016-1631-9

Special Issue: Data Management and Data Mining

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

Identify Congested Links Based on Enlarged State Space

Sheng-Li Pan1, Student Member, IEEE, Zhi-Yong Zhang1,2, Member, IEEE, Ying-Jie Zhou1,3, Member, IEEE Feng Qian1, and Guang-Min Hu1*, Member, IEEE   

  1. 1 School of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731, China;
    2 School of Computer and Communication Sciences, Swiss Federal Institute of Technology Lausanne, Lausanne 1015 Switzerland;
    3 College of Computer Science, Sichuan University, Chengdu 610065, China
  • Received:2015-03-09 Revised:2015-09-10 Online:2016-03-05 Published:2016-03-05
  • Contact: Guang-Min Hu E-mail:hgm@uestc.edu.cn
  • About author:Sheng-Li Pan received his B.E. degree in communication engineering in 2011 from University of Electronic Science and Technology of China (UESTC), Chengdu, and in the same year, he became a Ph.D. candidate in the School of Communication and Information Engineering at UESTC. His research interests include computer networks, network measurements, network tomography, and network topology inferences. He is a student member of IEEE.
  • Supported by:

    This work was partly supported by the National Natural Science Foundation of China under Grant Nos. 61171091 and 91438120, the Young Scientists Fund of the National Natural Science Foundation of China under Grant No. 61201127, the Fundamental Research Funds for Central Universities of China under Grant Nos. ZYGX2012J005 and 2014SCU11013, and the Science and Technology on Communication Security Laboratory under Grant No. 9140C110503140C11054.

PDF

795

When paths share a common congested link, they will all suffer from a performance degradation. Boolean tomography exploits these performance-level correlations between different paths to identify the congested links. It is clear that the congestion of a path will be distinctly intensive when it traverses multiple congested links. We adopt an enlarged state space model to mirror different congestion levels and employ a system of integer equations, instead of Boolean equations, to describe relationships between the path states and the link states. We recast the problem of identifying congested links into a constraint optimization problem, including Boolean tomography as a special case. For a logical tree, we propose an up-to-bottom algorithm and prove that it always achieves a solution to the problem. Compared with existing algorithms, the simulation results show that our proposed algorithm achieves a higher detection rate while keeping a low false positive rate.

[1] Chitsaz M, Woo C S. Software agent with reinforcement learning approach for medical image segmentation. Journal of Computer Science and Technology, 2011,26(2): 247-255.

[2] Castro R, Coates M, Liang G, Nowak R, Yu B. Network tomography: Recent developments. Statistical Science, 2004, 19(3): 499-517.

[3] Shih M F, Hero A O. Hierarchical inference of unicast network topologies based on end-to-end measurements. IEEE Trans. Signal Processing, 2007, 55(5): 1708-1718.

[4] Duffield N G. Network tomography of binary network performance characteristics. IEEE Trans. Information Theory, 2006, 51(12): 5373-5388.

[5] Tachibana A, Ano S, Tsuru M. Selecting measurement paths for efficient network monitoring on a user-cooperative scheme. In Proc. the 2013 IFIP/IEEE International Symposium on Integrated Network Management, May 2013, pp.736-739.

[6] Krishnamurthy A, Singh A. Robust multi-source network tomography using selective probes. In Proc. the 31st IEEE International Conference on Computer Communications, March 2012, pp.1629-1637.

[7] Nguyen H X, Thiran P. Using end-to-end data to infer lossy links in sensor networks. In Proc. the 25th IEEE International Conference on Computer Communications, April 2006.

[8] Dhamdhere A, Teixeira R, Dovrolis C, Diot C. NetDiagnoser: Troubleshooting network unreachabilities using endto- end probes and routing data. In Proc. the 3rd ACM International Conference on Emerging Networking Experiments and Technologies, December 2007, Article No. 18.

[9] Zarifzadeh S, Gowdagere M, Dovrolis C. Range tomography: Combining the practicality of Boolean tomography with the resolution of analog tomography. In Proc. the 12th ACM Internet Measurement Conference, November 2012, pp.385-398.

[10] Nguyen H X, Thiran P. The Boolean solution to the congested IP link location problem: Theory and practice. In Proc. the 26th IEEE International Conference on Computer Communications, May 2007, pp.2117-2125.

[11] Ghita D, Argyraki K, Thiran P. Toward accurate and practical network tomography. ACM SIGOPS Operating Systems Review, 2013, 47(1): 22-26.

[12] Chen J, Qi X, Wang Y. An efficient solution to locate sparsely congested links by network tomography. In Proc. the 2014 IEEE International Conference on Communications, January 2014, pp.1278-1283.

[13] Matsuda T, Nagahara M, Hayashi K. Link quality classifier with compressed sensing based on ?1-?2 optimization. IEEE Communications Letters, 2011, 15(10): 1117-1119.

[14] Letchford N, Lodi A. Primal cutting plane algorithms revisited. Mathematical Methods of Operations Research, 2002, 56(1): 67-81.

[15] Padmanabhan V, Qiu L, Wang H. Server-based inference of Internet link lossiness. In Proc. the 22nd IEEE International Conference on Computer Communications, Mar. 30-Apr. 3, 2003, pp.145-155.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved