Title :
Detection of Super Sources and Destinations in High-Speed Networks: Algorithms, Analysis and Evaluation
Author :
Zhao, Qi ; Xu, Jun ; Kumar, Abhishek
Author_Institution :
Coll. of Comput., Georgia Inst. of Technol., Atlanta, GA
Abstract :
Detecting the sources or destinations that have communicated with a large number of distinct destinations or sources (i.e., large "fan-out" or "fan-in") during a small time interval is an important problem in network measurement and security. Previous detection approaches are not able to deliver the desired accuracy at high link speeds (10-40 Gb/s). In this work, we propose two novel algorithms that provide accurate and efficient solutions to this problem. Their designs are based on the insight that sampling and data streaming are often suitable for capturing different and complementary regions of the information spectrum, and a close collaboration between them is an excellent way to recover the complete information. Our first solution builds on the standard hash-based flow sampling algorithm. Its main innovation is that the sampled traffic is further filtered by a data streaming module which allows for much higher sampling rate (hence, much higher accuracy) than achievable with standard hash-based flow sampling. Our second solution is more sophisticated but offers higher accuracy. It combines the power of data streaming in efficiently estimating quantities (e.g., fan-out) associated with a given identity, and the power of sampling in collecting a list of candidate identities. The performance of both solutions are evaluated using both mathematical analysis and trace-driven experiments on real-world Internet traffic
Keywords :
Internet; mathematical analysis; sampling methods; telecommunication traffic; data streaming; high-speed network; mathematical analysis; real-world Internet traffic; sources-destination detection; standard hash-based flow sampling algorithm; trace-driven experiment; Algorithm design and analysis; Computer network management; High-speed networks; Information security; Internet; Random access memory; Sampling methods; Statistical distributions; Statistics; Telecommunication traffic; Communication system traffic; computer network performance; computer network security; computer networks; system analysis and design;
Journal_Title :
Selected Areas in Communications, IEEE Journal on
DOI :
10.1109/JSAC.2006.877139