Controlling the Maximum Link Estimation Error in Network Performance Tomography

Network performance tomography uses a small number of strategically deployed monitors to infer the link performance in a large network. With the limited number of monitors, however, people usually can only estimate the bound rather than the exact values of network link performance. We aim at developing an effective solution to minimize the maximum error bound (MEB) over all the links in the network. To achieve this, we develop a method that theoretically guarantees (1) the minimum number of monitors required to bring down the MEB over all unidentifiable links, and (2) the best places where these new monitors should be deployed. Using this method repeatedly, we can push down the MEB gradually until the desired level is reached. In addition, we develop a new sequential measurement technique that reduces the number of measurement paths and in the meantime guarantees the tightest link error bound. With extensive simulation over real-world network topology, we demonstrate the effectiveness and robustness of our solution in reducing the maximum link error bound with network performance tomography.