Scalable and Flexible Network-wide Traffic Measurement

This thesis addresses the challenges and problems in network-wide traffic measurement. Network-wide traffic measurement faces two main challenges: how to improve local measurement accuracy under limited resources, and how to coordinate distributed monitors for global monitoring purposes. We first consider global iceberg detection as a measurement case study. We propose to combine uniform sampling and distributed sketches to detect and estimate both local elephants and global icebergs. Our observations and results provide a strong motivation for developing a scalable and flexible network-wide measurement framework that can best utilize the distributed monitors in the networks. To address these challenges, we propose, model, and analyze measurement-aware routing schemes which combines traffic measurement and routing.;In the first part of dissertation we address the problem of global iceberg detection in distributed streams. While previous work has concentrated on measuring icebergs in the non-distributed streaming case or in the non-streaming distributed case, we present a general framework that allows for distributed processing across multiple streams of data. We compare several of the state-of-the-art streaming algorithms for estimating local elephants in the individual streams. However, since an iceberg may be hidden by being distributed across many different streams, we add a sampling component to handle such cases. We provide a novel taxonomy of current sketches and perform a thorough analysis of the strengths and weaknesses of each scheme under various QoS metrics, using both real and synthetic Internet trace data. We also discuss the implications for the future sketch design.;In the second part of dissertation we propose MeasuRouting, a framework which combines routing and measurement. Previous research in network-wide traffic measurement focused on deriving a placement of monitors in order to maximize the monitoring utility under a fixed traffic routing. However, both traffic characteristics and measurement objectives can dynamically change over time, rendering a previously optimal placement strategy suboptimal. In contrary, MeasuRouting strategically routes traffic flows for better measurement. The main challenge for MeasuRouting is to work within the constraints of existing intra-domain traffic engineering operations. To solve it, MeasuRouting differentially routes components of an aggregate flow while ensuring that the aggregate routing is compliant to original traffic engineering objectives. We present the theoretical framework for MeasuRouting, and showcase the utility enhancement for both synthetic and practical monitoring applications.;The third part of dissertation presents MMPR (Measurement-aware Monitor Placement and Routing) framework that jointly optimizes monitor placement and MeasuRouting strategy. Neither MeasuRouting nor monitor placement problem alone suffices in real measurement scenarios, since not only the number of deployed monitors is limited, but also the traffic characteristics and measurement objectives are constantly changing. The main challenge of MMPR is to decouple the relevant decision variables and adhere to the traffic engineering constraints. We formulate it as an MILP (Mixed Integer Linear Programming) problem and propose several heuristic algorithms to approximate the optimal solution and reduce the computation complexity. Through experiments using real traces and topologies, we show that our heuristic solutions can achieve measurement gains that are quite close to the optimal solutions, while significantly reducing the computation times.;Lastly, we discuss how MeasuRouting can be implemented on OpenFlow testbed and address practical deployment issues. Implementing DMR (Dynamic Measurement-aware Routing) in practice is riddled with three major challenges: (1) How to dynamically assess the importance of traffic flows? (2) How to aggregate flows (and hence take a common action for them) in order to conserve routing table entries? and (3) How to achieve traffic routing/rerouting in a manner that is least disruptive to normal network performance while maximizing the measurement utility? We take a closer look at these challenges and discuss how they manifest for different types of networks. Through an OpenFlow prototype, we show how DMR can be applied in enterprise networks. Using global iceberg detection & capture as a driving application, we demonstrate how our solutions successfully route suspected iceberg flows to a DPI box for further processing, while preserving a balanced load distribution in the overall network.;The contribution of this thesis to network traffic measurement are two folds. First, we study one specific application, global iceberg detection in distributed streams, to illustrate real-world problems which request "network-wide" traffic measurement. The proposed combination of local sketch and uniform sampling can better capture global iceberg. Secondly, we extensively study MeasuRouting, a framework that utilizes "routing" for better traffic measurement. The framework, along with its extension MMPR and implementation DMR, opens another direction for network-wide traffic measurement.