Online Algorithm for Finding Top Spreaders in High Speed Network
- Summary
- Efficiently and accurately identifying hosts who are spreading the largest amount of flows during an interval, so called top spreaders, is very important for managing a network and studying host behaviors on application level. No previous work has been able to efficiently and accurately identify those top spreaders at very high link speed, for example, 10 to 40 Gbps. In this work, we propose a novel online algorithm to not only accurately identify the top spreaders, but also accurately estimate their spreading out cardinality (that is the flow number of each identified top spreader), and the host and flow identifiers can be any combination of fields in packet headers. The insight of our solution is to combine sampling and streaming algorithms, and combine deterministic and randomized algorithms, where they can effectively help each other to reduce memory usage and increase accuracy. The algorithm is evaluated using both synthetic data and real world traffic traces.
- Application No.
- 08/ENG/299 Patent Status: US Patent Pending Licensing Status: Available for licensing
- Others
- Inventor(s): Professor Dah Ming CHIU, Department of Information Engineering
- Country/Region
- Hong Kong
For more information, please click Here
