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 imprac-tical 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 recent introduction of SDN allows deploying new centralized network algorithms that dramatically improve network operations. In such algorithms, the centralized controller obtains a network-wide view by merging measurement data from Network Measurement Points (NMPs). A fundamental challenge is that several NMPs may count the same packet, reducing the accuracy of the measurement. Existing solutions circumvent this problem by assuming that each packet traverses a single NMP or that the routing is fixed and known. This work suggests novel algorithms for three fundamental network-wide measurement problems without making any assumptions on the topology and routing and without modifying the underlying traffic. Specifically, this work introduces two algorithms for estimating the number of (distinct) packets or byte volume in the measurement, estimating per-flow packet and byte counts, and finding the heavy hitter flows. Our work includes formal accuracy guarantees and an extensive evaluation consisting of the realistic fat-tree topology and three real network traces. Our evaluation shows that our algorithms outperform existing works and provide accurate measurements within reasonable space parameters.

Network measurement is an essential building block for a variety of network applications such as traffic engineering, quality of service, load-balancing and intrusion detection. Maintaining a per-flow state is often impractical due to the large number of flows, and thus modern systems use complex data structures that are updated with each incoming packet. Therefore, designing measurement applications that operate at line speed is a significant challenge in this domain.

The recent introduction of SDN allows deploying new centralized network algorithms that dramatically improve the network operation. Many of these solutions rely on the assumption that the centralized controller merges data from different Network Monitoring Points (NMP) to obtain a network-wide view. This is far from trivial when the same packet may traverse through several NMPs. Therefore, existing solutions either assume that each packet is measured at exactly one NMP or that the routing of each packet is known. Another approach is to mark the sampled packets so that other NMPs are aware that the packet was already considered.

Real time detection of flow anomalies is a critical part of wide range of management and security applications in many Cloud and NFV systems. Solutions based on per-flow records have become impossible due to the increasing traffic volumes and the limited available resources such as TCAM entries and fast counters. In this paper we study a novel dynamic control mechanism that allows detecting flow anomalies using only a limited number of counters. Starting from the simple observation that it is impossible to guarantee instantaneous detection of flow anomalies with a limited amount of counters, we study the trade-off between the time required to detect the anomaly and the number of available counters. We implemented the scheme in an OpenFlow enabled switch, where the logic is implemented in the controller, and demonstrate that it can be used to detect a single flow anomaly within large real traffic volume. To further reduce the detection time, we also implemented the scheme logic inside the switch and used the controller only for configuration. This implementation indeed yielded a faster detection and lower monitoring communication overhead while not introducing any significant observable costs at the switch itself.