Ph.D Thesis

Ph.D StudentMoraney Jalil
SubjectEfficient Resource-Constrained Monitoring
DepartmentDepartment of Computer Science
Supervisor PROF. Dan Raz
Full Thesis textFull thesis text - English Version


Monitoring network traffic is an important building block for various management and security systems. Typically, the number of active flows in a network node is much larger than the number of available monitoring resources, making it impractical to maintain a “per-flow” state at the node. This situation gave rise to the recent interest in streaming algorithms where complex data structures are used to perform monitoring tasks efficiently. However, these solutions often require complicated “per-packet” operations, which are not feasible in current devices line-rate. Even when the amortized (expected average) complexity is $O(1)$ operations per-packet, some packets may experience a much longer delay, which again is impractical. In this dissertation we study three important monitoring problems (that were recently studied in the context of streaming algorithms) and for each of them we present practical, efficient resource-constrained algorithms.

The first problem is identifying the top-$k$ flows flowing through a network node. We present a novel approach to this problem by studying the ability to perform monitoring tasks using efficient built-in counters available in current network devices. We show that by applying non-trivial control algorithms that change the filter assignments of these counters at a fixed time interval, regardless of packet arrival-rate, we can get accurate monitoring information. We provide an analytical study of the problem and show, using extensive emulation over recent real traffic, that our algorithm can perform at least as well as the best-known streaming algorithms without using complex data structure or performing expensive “per-packet” operations.

The second problem we address is the detection of Heavy Hitter (HH) flows in a network device. In this problem, a flow is considered a HH flow if its portion from the total traffic surpasses a given threshold.

For this problem, we present a practical HH detection algorithm that requires a constant amount of memory (not related to the number of flows or packets) and performs at most $O(1)$ operations per-packet to keep with line-rate. We present an analysis of the algorithm's expected errors and compare it to state-of-the-art monitoring solutions, showing a superior performance when the allocated memory is less than $1MB$. In particular, we are able to detect more HH flows with lower false positive rate than state-of-the-art without increasing the ``per-packet" processing time.

The last problem is the hierarchical heavy hitters (HHH) problem, where one needs to identify the most frequent network IP-prefixes hierarchically. For this problem, we take a similar approach

as the one in top-$k$ flows detection and use a sophisticated control mechanism for the built-in counters. We develop a constant-time algorithm for detecting the HHH that does not have any convergence requirements and achieves comparable results to state-of-the-art.

Most importantly, our algorithm uses only efficient built-in counters available in current network devices, making it deployable on commercially off-the-shelf network gear.

We provide an analytical study of the problem and show, using emulation over real traffic, that our algorithm performs at least as well as the best-known streaming algorithms without performing expensive ``per-packet" operations or requiring convergence periods.