Route selection algorithms utilizing the property of the ZDD for compressed sensing-based transmissive network tomography

When something abnormal suddenly occurs in a network, for instance, an unknown link is disconnected or give an extremely long delay, we need to immediately identify the abnormal link to remediate it. Compressed sensing-based network tomography can efficiently identify such abnormal links, by measuring packet transmission behaviors over fewer end-to-end routes. Its performance largely depends on pre-selection of measurement routes, so some algorithms have been proposed. However, when the network size is large, it takes enormous time for conventional route selection algorithms to list a huge number of all routes between transmitter and receiver nodes and select adequate measurement routes out of them. In this paper, we propose some route selection algorithms for compressed sensing-based transmissive network tomography. The proposed algorithms make efficient use of the property of the Zero-Suppressed Binary Decision Diagram (ZDD) used in the SIMPATH algorithm, so they can efficiently not only list a limited number of measurement route candidates but also select adequate measurement routes out of them. Computer simulation results reveal that, for given networks, the proposed algorithms can efficiently select measurement routes and the delay-difference tomography schemes using the selected measurement routes can effectively identify abnormal links.