[1] Cheng Guang, Qiang Shiqing,. Super point detection based on sampling and data streaming algorithms [J]. Journal of Southeast University (English Edition), 2009, 25 (2): 224-227. [doi:10.3969/j.issn.1003-7985.2009.02.017]

Copy

Super point detection based on sampling and data streaming algorithms()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

25

Issue:

2009 2

Page:

224-227

Research Field:

Computer Science and Engineering

Publishing date:

2009-06-30

Info

Title:

Super point detection based on sampling and data streaming algorithms

Author(s):

Cheng Guang;  Qiang Shiqing

School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
Key Laboratory of Computer and Network Technology of Jiangsu Province, Southeast University, Nanjing 210096, China

Keywords:

super point;  flow sampling;  data streaming

PACS:

TP393.08

DOI:

10.3969/j.issn.1003-7985.2009.02.017

Abstract:

In order to improve the precision of super point detection and control measurement resource consumption, this paper proposes a super point detection method based on sampling and data streaming algorithms(SDSD), and proves that only sources or destinations with a lot of flows can be sampled probabilistically using the SDSD algorithm. The SDSD algorithm uses both the IP table and the flow bloom filter(BF)data structures to maintain the IP and flow information. The IP table is used to judge whether an IP address has been recorded. If the IP exists, then all its subsequent flows will be recorded into the flow BF; otherwise, the IP flow is sampled. This paper also analyzes the accuracy and memory requirements of the SDSD algorithm, and tests them using the CERNET trace. The theoretical analysis and experimental tests demonstrate that the most relative errors of the super points estimated by the SDSD algorithm are less than 5%, whereas the results of other algorithms are about 10%. Because of the BF structure, the SDSD algorithm is also better than previous algorithms in terms of memory consumption.

References:

[1] Moore D, Paxson V, Savage S, et al.Inside the slammer worm [J].Security and Privacy Magazine, 2003, 1(4):33-39.
[2] Roesch M.Snort—lightweight intrusion detection for networks [C]//Proceedings of the 13th USENIX Conference on Systems Administration.Berkeley, CA, USA:USENIX Association, 1999:229-238.
[3] Plonka D.Flowscan:a network traffic flow reporting and visualization tool [C]//Proceedings of the 14th USENIX Conference on Systems Administration. Berkeley, CA, USA:USENIX Association, 2000:305-317.
[4] Venkataraman S, Song D, Gibbons P, et al.New streaming algorithms for fast detection of superspreaders [C]//Proceedings of the 12th Annual Network and Distributed System Security Symposium.San Diego, California, USA, 2005.
[5] Zhao Qi, Kumar Abhishek, Xu Jun.Joint data streaming and sampling techniques for detection of super sources and destinations [C]//Proceedings of the 5th ACM SIGCOMM Conference on Internet Measurement. Berkeley, CA, USA:USENIX Association, 2005:77-90.
[6] Kamiyama Noriaki, Mori Tatsuya, Kawahara Ryoichi.Simple and adaptive identification of superspreaders by flow sampling[C]//Proceeding of the 26th IEEE International Conference on Computer Communications.Anchorage, AK, USA:IEEE INFOCOM, 2007:2481-2485.
[7] Kumar Abhishek, Xu Jun, Li Li, et al.Space-code BF for efficient traffic flow measurement [J].IEEE Journal on Selected Areas in Communications, 2006, 24(12):2327-2339.
[8] Key Laboratory of Computer and Network Technology of Jiangsu Province.IP trace[EB/OL].(2009-02)[2009-03].http://ntds.njnet.edu.cn/home/intro.php.(in Chinese)

Memo

Memo:

Biography: Cheng Guang(1973—), male, doctor, associate professor, gcheng@njnet.edu.cn.
Foundation items: The National Basic Research Program of China(973 Program)(No.2009CB320505), the Natural Science Foundation of Jiangsu Province(No.BK2008288), the Excellent Young Teachers Program of Southeast University(No.4009001018), the Open Research Program of Key Laboratory of Computer Network of Guangdong Province(No.CCNL 200706).
Citation: Cheng Guang, Qiang Shiqing.Super point detection based on sampling and data streaming algorithms[J].Journal of Southeast University(English Edition), 2009, 25(2):224-227.

Common functions