Network inference (or tomography) problems, such as traffic matrix estimation or completion and link loss inference, have been studied rigorously in different networking applications. These problems are often posed as under-determined linear inverse (UDLI) problems and solved in a centralized manner, where all the measurements are collected at a central node, which then applies a variety of inference techniques to estimate the attributes of interest. This paper proposes a novel framework for decentralizing these large-scale under-determined network inference problems by intelligently partitioning it into smaller subproblems and solving them independently and in parallel. The resulting estimates, referred to as multiple descriptions, can then be fused together to compute the global estimate. We apply this Multiple Description and Fusion Estimation (MDFE) framework to three classical problems: traffic matrix estimation, traffic matrix completion, and loss inference. Using real topologies and traces, we demonstrate how MDFE can speed up computation while maintaining (even improving) the estimation accuracy and how it enhances robustness against noise and failures. We also show that our MDFE framework is compatible with a variety of existing inference techniques used to solve the UDLI problems.

We have previously introduced Multiple Description Fusion Estimation (MDFE) framework that partitions a large-scale Under-Determined Linear Inverse (UDLI) problem into smaller sub-problems that can be solved independently and in parallel. The resulting estimates, referred to as multiple descriptions, can then be fused together to compute the global estimate [1]. In this paper, we extend MDFE framework to make it compatible with Compressive Sensing (CS) network inference, where the attributes of interests (i.e. unknowns) are fluctuating rapidly over time and/or space. For this purpose, we propose a new clustering based technique to intelligently divide a large-scale compressive sensing problem into smaller sub-problems where observations between sub-spaces contain redundancy. We apply this new framework, referred to as Compressive Sensing MDFE (CS-MDFE), to three classical inference problems in networking: traffic matrix estimation, traffic matrix completion, and loss inference. Using real topologies and traces, we demonstrate how CS-MDFE can improve the estimation accuracy and speed up computation time, and how it enhances robustness against noise and failures. We also show that this framework is compatible with different CS inference techniques.

Two forms of network inference (or tomography) problems have been studied rigorously: (a) traffic matrix estimation or completion based on link-level traffic measurements, and (b) link-level loss or delay inference based on end-to-end measurements. These problems are often posed as underdetermined linear inverse (UDLI) problems and solved in a centralized manner, where all the measurements are collected at a central node, which then applies a variety of inference techniques to estimate the attributes of interest. This paper proposes a novel framework for decentralizing these large-scale UDLI network inference problems by intelligently partitioning it into smaller sub-problems and solving them independently and in parallel. The resulting estimates, referred to as multiple descriptions, can then be fused together to compute the global estimate. We apply this Multiple Description and Fusion Estimation (MDFE) framework to three classical problems: traffic matrix estimation, traffic matrix completion, and loss inference. Using real topologies and traces, we demonstrate how MDFE can speed up computation time while maintaining (even improving) the estimation accuracy and how it enhances robustness against noise and failures. We also show that our MDFE framework is compatible with a variety of existing inference techniques used to solve the UDLI problems.