OpenMeasure: Adaptive Flow Measurement and Inference with Online Learning in SDN - eScholarship
Chang Liu, Mehdi Malboubi, Chen‐Nee Chuah · 2016
OpenMeasure: Adaptive Flow Measurement & Inference with Online Learning in SDN Chang Liu, Mehdi Malboubi, Chen-Nee Chuah Dept. of Electrical & Computer Engineering University of California, Davis, USA. {cchliu, mmalboubi, chuah}@ucdavis.edu Abstract—Accurate and efficient network-wide traffic mea- surement is crucial for network management. Recently, Software- defined networking (SDN) has opened up new opportunities in network measurement and inference. In this work, we demon- strate an efficient flow measurement and inference framework which performs adaptive measurement with online learning. Using the reprogrammability of SDN, we assist network inference with online learning predictions and dynamically update the measurement rules network-wide to track and measure the most informative flows. To best utilize the available measurement resources, we leverage the SDN controller (with its global view) to optimally place flow monitoring rules across network switches. Using real-world data, we show that our measurement framework achieves high performance in both estimating the traffic matrix and identifying hierarchical heavy hitters. I. I NTRODUCTION Fine-grained traffic size information provides an essential input for many network design and operation tasks, such as capacity planning, network provisioning, load balancing, and anomaly detection [1]–[3]. Flow size can be measured directly or inferred (indirectly) from sampled statistics. In large-scale networks, direct flow measurement can be challenging due to the exploding traffic volume, limited monitoring resources and the prohibitively large overhead imposed on the network com- ponents. An alternate approach is estimating the traffic matrix (TM) from a set of aggregated/end-to-end measurements using network inference techniques. The emerging software defined networking (SDN) paradigm decouples network control (control plane) from forwarding functions (data plane), enabling the network control to become directly programmable and the underlying infrastructure to be abstracted for applications and network services [4]. The control logic is moved to an external entity, the SDN controller. The logically centralized controller has a global view of network and can dynamically configure the forwarding rules in managed flow tables. In addition, it can also obtain flow statistics from reading the counters of the switch TCAM rules. SDN opens up many new opportunities for addressing network measurement and inference problems. On one hand, it can augment network inference with multi-resolution mon- itoring and online learning. On the other hand, with the global view of the network, the controller can optimize the network-wide allocation of measurement resources. We could dynamically determine what/when/where to measure. While there have been many studies on leveraging SDN in network measurement and inference, the most relevant work is iSTAMP [5]. However, iSTAMP does not take routing and flow aggregation feasibility into account when designing optimal flow aggregates and only focuses on single-switch scenario. While [6] extended iSTAMP framework to multi- switch scenario, the discussion about how to continuously identify large flows and update measurements over time is missing. Different from [5] and [6], in our work, we propose a framework we refer to as OpenMeasure which leverages continuous online learning techniques to perform network- wide adaptive flow measurement and inference. Similar to iSTAMP, OpenMeasure consists of an intelligent flow sampling and network inference engine residing on the SDN controller. However, instead of optimizing the aggrega- tion matrix, OpenMeasure assumes that the aggregation matrix is given based on the underlying routing and flow aggregation rules. As mentioned earlier, our framework employs an online learning algorithm to determine the most informative flows for sampling. By leveraging the global view of SDN controller, it identifies the available monitoring resources and intelligently places flow sampling rules in selected SDN switches. Further- more, this framework is light-weight, compatible with hybrid SDN networks, relies on current capabilities of OpenFlow (OF) switches, and does not impact network routing functions. To summarize, the contributions of our work are three-fold: • We propose OpenMeasure, a network-wide adaptive flow measurement and inference framework with continuous learning capability. We propose two online learning algo- rithms for designing the adaptive flow measurement rules: one algorithm is based on weighted linear prediction and the other adopts the strategy used in multi-armed bandit (MAB) problems [7]. • Leveraging SDN controller’s global view of network, we optimize the allocation of flow monitoring rules among multiple OF switches to increase measurement accuracy. We formulate the problem mathematically and proposes two light-weight heuristic rule allocation algorithms. • We evaluate the performance of OpenMeasure in traffic matrix (TM) estimation as well as hierarchical heavy hitter (HHH) identification. We demonstrate the benefit of continuous learning and update of measurement rules, which is absent in [6]. We also implemented OpenMea- sure on GENI [8] testbed to demonstrate the practical