From Network Inference Errors to Utility Suboptimality: How Much Is the Impact?

作     者：Li, Shijing Lan, Tian 

作者机构：George Washington Univ Washington DC 20052 USA 

出 版 物：《IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING》 (IEEE Trans. Netw. Sci. Eng.)

年 卷 期：2022年第9卷第6期

页      面：4075-4086页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 

主　　题：Inference algorithms Heuristic algorithms Optimization Tomography Routing Network topology Knowledge engineering Network inference network optimization utility optimization 

摘      要：Accurate and timely network inference, known as network tomography, is a vital ingredient in efficient network operation, supporting more sophisticated and ambitious traffic optimization algorithms. In practice, however, precise knowledge of the dynamic internal network bottlenecks/states can be impossible to obtain under restricted network visibility on network edge where only end-to-end measurements are available without cooperation of internal network components. In this paper, we acknowledge that network tomography on the edge is often imperfect, leading to dynamic, time-varying inference errors that could change from iteration to iteration on the same time-scale as distributed network optimization algorithms. We quantify the impact of such imperfect bottleneck/state inference on algorithm convergence and optimality. In particular, we show that under arbitrary, bounded inference errors (belonging to three common classes including absent and incorrect bottlenecks, and inaccurate capacity), the solution of the distributed optimization algorithm still converges to a bounded neighborhood of the optimal solution. The resulted optimality gap is quantified in closed form and shown to be proportional to average inference errors. These results are evaluated using extensive network simulations and on real-world IoT data sets. The work provide a theoretical support for understanding the impact of imperfect inference on distributed network optimization.