[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(
)
基于抽样和数据流算法的超点检测
)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.
- 为了提高超点检测的精度并控制测量资源的使用, 提出了一种基于抽样和数据流算法的超点检测方法. 该方法通过抽样从概率上保证发送或接收大量流的节点能被检测, 同时采用数据流技术建立了IP table和流 BF(BF)两个数据结构. 其中IP table结构用于判断IP是否已经被创建, 如果已经被创建, 则将属于该IP的所有后续的流记录在流BF结构中;如果IP table结构中不存在该IP记录, 则对属于该IP的流进行抽样.对提出方法的精度和内存需求从理论上进行了分析, 并采用CERNET数据进行验证.理论分析和实验测试表明, 提出的超点检测算法的测量误差基本控制在5%以内, 而其他算法的误差在10%左右.另外, 由于使用BF数据结构, 提出的算法在使用空间上也优于其他算法.
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.