2018/12/02 by Wei, Hao-Ting, Hsieh, Sung-Hsien, Hwang, Wen-Liang +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI)
paper · doi:10.48550/arxiv.1812.00369
When the scale of communication networks has been growing rapidly in the past decades, it becomes a critical challenge to extract fast and accurate estimation of key state parameters of network links, e.g., transmission delays and dropped packet rates, because such monitoring operations are usually time-consuming. Based on the sparse recovery technique reported in [Wang et al. (2015) IEEE Trans. Information Theory, 61(2):1028--1044], which can infer link delays from a limited number of measurements using compressed sensing, we particularly extend to networks with dynamic changes including link insertion and deletion. Moreover, we propose a more efficient algorithm with a better theoretical upper bound. The experimental result also demonstrates that our algorithm outperforms the previous work in running time while maintaining a similar recovery performance, which shows its capability to cope with large-scale networks.