AL-bitmap: Monitoring network traffic activity graphs on high speed links

Monitoring traffic activity graphs (TAGs) is important for traditional networks and software defined networks. However, it is challenging to compute TAGs on high speed links in realtime by using routers' very fast but expensive static RAM (SRAM). In this paper, we develop a new method, AL-bitmap (AL stands for “adaptive length”), to build an accurate yet compact traffic summary. Compared to previous bitmap methods, AL-bitmap generates a bitmap with adaptive length for each host, that is, the bitmap's length automatically increases with the number of hosts that the host connects to. This enables us to accurately measure the statistics of TAGs with a small memory usage of SRAM. We evaluate our methods on publicly available real network traffic, and the experimental results show that AL-bitmap is computational and memory efficient for monitoring traffic on high speed routers, and it is significantly more accurate than state-of-the-art methods.