ZHOU Aiping, LIU Lijun, ZHU Huisheng, ZHU Chen'gang, CHEN Lin. Parallel Sketch Based Super Node Detection with Traceability[J]. Chinese Journal of Electronics, 2018, 27(6): 1133-1140. doi: 10.1049/cje.2018.08.009
Citation: ZHOU Aiping, LIU Lijun, ZHU Huisheng, ZHU Chen'gang, CHEN Lin. Parallel Sketch Based Super Node Detection with Traceability[J]. Chinese Journal of Electronics, 2018, 27(6): 1133-1140. doi: 10.1049/cje.2018.08.009

Parallel Sketch Based Super Node Detection with Traceability

doi: 10.1049/cje.2018.08.009
Funds:  This work is supported by Open Project Foundation of Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, China (No.K93-9-2017-01), Fund for "Integration of Cloud Computing and Big Data, Innovation of Science and Education", Ministry of Education, China (No.2017B06109), Natural Science Foundation of Jiangsu, China (No.BRA2015212, No.BK20141307), Scientific Research Foundation for Advanced Talents of Taizhou University, China (No.QD2016027), and Technology Support Project of Taizhou, China (No.TS201633).
  • Received Date: 2016-09-30
  • Rev Recd Date: 2017-10-23
  • Publish Date: 2018-11-10
  • Traffic measurement and monitoring is crucial for network applications, such as network security, network management and so on. One central problem is to detect super nodes, which have significant change of connection degree between consecutive measurement periods. Due to weakness in massive network traffic processing for the centralized algorithm and low detection accuracy, space efficiency for super node detection algorithm based on flow sampling, we propose Parallel sketch based super node detection with traceability (PSD). It constructs parallel sketch and estimates connection degree of nodes by probabilistic counting approach, so that super nodes are identified using connection degree change between consecutive measurement periods. Moreover, IP addresses of super nodes are reconstructed by simple computing to trace attacker or victims. The experimental results illustrate that the proposed method outperforms the Compact spread estimator (CSE) and Data streaming and sampling (DSS) in terms of detection accuracy and storage utilization.
  • loading
  • G. Cheng, J. Gong, W. Ding, et al., “Adaptive sampling algorithm for detection of superpoints”, Science in China Series F: Information Sciences, Vol.51, No.11, pp.1804-1821, 2008. (in Chinese)
    S. Yao, J. Guan, H. Pan, et al., “Modeling and analysis for Network Survivability of APT Latent Attack”, Acta Electronica Sinica, Vol.44, No.10, pp.2415-2422, 2016. (in Chinese)
    Q. Xiao, Y. Qiao, M. Zhen, et al., “Estimating the persistent spreads in high-speed networks”, Proceedings of the IEEE 22nd International Conference on Network Protocols, Raleigh, USA, pp.131-142, 2014.
    P. Wang, X. Guan, D. Towsley, et al., “Virtual indexing based methods for estimating node connection degrees”, Computer Networks, Vol.56, No.12, pp.2773-2787, 2012.
    G. Cheng and Y. Tang, “Line speed accurate superspreader identification using dynamic error compensation”, Computer Communications, Vol.36, No.13, pp.1460-1470, 2013.
    S. Venkataraman, D. Song, P.B. Gibbons, et al., “New streaming algorithms for fast detection of superspreaders”, Proceedings of the Network and Distributed System Security Symposium, San Diego, USA, pp.1-18, 2005.
    Q. Zhao, J. Xu and A. Kumar, “Detection of super sources and destinations in high-speed networks: Algorithms, analysis and evaluation”, IEEE Journal on Selected Areas in Communications, Vol.24, No.10, pp.1840-1852, 2006.
    M.K. Yoon, T. Li, S. Chen, et al., “Fit a compact spread estimator in small high-speed memory”, IEEE/ACM Transactions on Networking, Vol.19, No.5, pp.1253-1264, 2011.
    P. Wang, X. Guan, T. Qin, et al., “A data streaming method for monitoring host connection degrees of high-speed links”, IEEE Transactions on Information Forensics and Security, Vol.6, No.3, pp.1086-1098, 2011.
    S. Shin, E. Im and M. Yoon, “A grand spread estimator using a graphics processing unit”, Journal of Parallel and Distributed Computing, Vol.74, No.2, pp.2039-2047, 2014.
    S. Das, S. Antony, D. Agrawal, et al., “Thread cooperation in multicore architectures for frequency counting over multiple data streams”, Proceedings of the VLDB Endowment, Vol.2, No.1, pp.217-228, 2009.
    C. Estan, G. Varghese and M. Fisk, “Bitmap algorithms for counting active flows on high speed links”, Proceedings of the 3rd ACM SIGCOMM Conference on Internet measurement, Miami Beach, USA, pp.153-166, 2003.
    M. Chen and S. Chen, “Counter Tree: A scalable counter architecture for per-flow traffic measurement”, Proceedings of the IEEE 23rd International Conference on Network Protocols, San Francisco, USA, pp.111-122, 2005.
    Q. Xiao, S. Chen, M. Chen, et al., “Hyper-compact virtual estimators for big network data based on register sharing”, ACM SIGMETRICS Performance Evaluation Review, Vol.43, No.1, pp.417-428, 2015.
    W. Liu, W. Qu, J. Gong, et al., “Detection of superpoints using a vector bloom filter”, IEEE Transactions on Information Forensics and Security, Vol.11, No.3, pp.514-527, 2016.
    Q. Huang and P.P.C. Lee, “A hybrid local and distributed sketching design for accurate and scalable heavy key detection in network data streams”, Computer Networks, Vol.91, pp.298-315, 2015.
    K.Y. Whang, B.T. Vander-Zanden and H.M. Taylor, “A lineartime probabilistic counting algorithm for database applications”, ACM Transactions on Database Systems, Vol.15, No.2, pp.208-229, 1990.
    T.H. Cormne, C.E. Leiserson, R.L. Rivest, et al., Introduction to Algorithms, MIT Press, Cambridge, USA, pp. 950-954, 2009.
    Cernet dataset. http://iptas.edu.cn. 2016.
    Caida dataset. http://www.caida.org. 2016.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (170) PDF downloads(251) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint