Software Defined Network Measurement and Inference Under Hard Resource Constraints

The optimal design and utilization of networks from different perspectives is achieved by the accurate and timely monitoring of the Internal Attributes of Interest (IAI) of underlying operating network. The IAI, such as per-flow size, delay, throughput or packet-loss, can be directly measured or indirectly inferred.;In large-scale networks, the direct measurement of IAI can be challenging and infeasible due to the limited amount of available network measurement resources including the Ternary Content Addressable Memory (TCAM) entries, processing power, storage capacity and available bandwidth. TCAMs are special computer memories with the capability of real-time and exact-match search which are used for packet matching and classifications in network switches and routers. TCAMs are expensive and consume a lot of power; hence, the number of TCAM entries in network switches and routers are limited. In today's large-scale networks with the exploding volume of traffic, network monitoring infrastructures and devices have also limited processing power and storage capacity for packet processing, classification, and information storing. In addition, in active network monitoring applications, probe packets use part of the available bandwidth of network links to measure particular IAI (e.g. delay, throughput or packet-loss). The available bandwidth is the most important resource in communication systems and networks which is very limited and must be efficiently allocated.;Accordingly, direct network measurement under hard resource constraints, where a limited amount of measurement resources is available for measuring all IAI, is challenging. Therefore, Network Inference (NI) techniques can be leveraged to indirectly estimate various IAI based on partial passive and/or active end-to-end measurements. However, in large-scale networks, applying NI problems is computationally inefficient or infeasible. In addition, the estimation accuracy of network inference problems is limited due to the fact that these problems are typically formulated as Under-Determined Linear Inverse (UDLI) problems which are naturally ill-posed in the sense that the number of measurements is not sufficient to uniquely and accurately determine the solution. In this dissertation, three efficient frameworks are proposed for estimating the internal attributes of interest under hard constraint of measurement resources in large-scale networks.;First, a novel framework for decentralizing large-scale under-determined network inference problems is proposed. In this framework, a large-scale network inference problem is intelligently partitioned into smaller sub-problems that are solved independently and in parallel. The resulting estimates, referred to as multiple descriptions, can then be combined together to compute the global estimate. This Multiple Description and Fusion Estimation (MDFE) framework is applied to three classical problems: traffic matrix estimation, traffic matrix completion, and loss inference. Using real topologies and traffic traces, it is demonstrated that MDFE can speed up computation process without compromising the estimation accuracy, and also, enhances the robustness of the NI process against noise in the measurement process and failures in computational and/or communication infrastructures. It is also shown that MDFE framework is compatible with a variety of existing inference techniques used to solve UDLI problems.;Second, with the advent of Software-Defined-Networking (SDN), where network switches and routers can be adaptively (re)programmed and (re)configured, an intelligent traffic (de)aggregation and measurement paradigm (called iSTAMP) is introduced. Under hard constraints of network flow measurement resources (e.g. TCAM entries and their associated counters), iSTAMP adaptively allocates the available limited TCAM entries of network switches for measuring and routing the existing flows of the operating network. For this purpose, in iSTAMP, TCAM entries of switches/routers are partitioned into two parts to: 1) near-optimally aggregate part of incoming flows for aggregate measurements, and 2) de-aggregate and directly measure the most informative flows for per-flow measurements. iSTAMP then processes these aggregate and per-flow measurements to effectively estimate the size of network flows using a variety of optimization techniques. First, it is shown how to design the near-optimal aggregation matrix for minimizing the flow-size estimation error. Then, a method for designing an efficient-compressive flow aggregation matrix, under hard resource constraints of limited TCAM sizes, is presented. In addition, an intelligent Multi-Armed Bandit based algorithm is proposed to adaptively sample the most "rewarding" flows, whose accurate measurements have the highest impact on the overall flow measurement and estimation performance. The performance of iSTAMP is evaluated using real traffic traces from a variety of network environments and by considering two applications: traffic matrix estimation and heavy hitter detection.;Third, a new framework which is effective for both passive and active network measurement under hard constraints of measurement resources is proposed. This framework (called SNIPER) leverages the flexibility provided by SDN to design a near-optimal observation or measurement matrix that can lead to the best achievable estimation accuracy using Matrix Completion (MC) techniques. In SNIPER, to cope with the complexity of designing large-scale optimal observation matrices, the Evolutionary Optimization Algorithms (EOA) are used to directly target the ultimate estimation accuracy as the optimization objective function. The performance of SNIPER is evaluated using both synthetic and real network measurement traces from different network topologies and by considering two main applications for per-flow size and delay estimations. Our results show that SNIPER can be applied to a variety of network performance measurements under hard resource constraints. For example, by measuring only 8.8% of all per-flow path delays in Harvard network, congested paths can be detected with probability of 0.94.;Finally, we address future works and discuss open/new research directions that can be built on this dissertation work.