Security-aware beacon based network monitoring

The active beacon based network monitoring tries to estimate the transfer delay of a link e by the difference of round-trip times from a beacon host to the two endpoints of e. For efficiency, we consider the problem of placing a minimum set of beacons to monitor all links of a given TCP/IP network e.g., the Internet. We propose an idea called L-beacon, i.e., a beacon can monitor only links within L hops. We show it generalizes previous studies for the so-called simple beacon (Kumar and Kaur ¿06) with L = 0 and the locally flexible beacon with L = 1 (Horton and Lopez-Ortiz ¿03). We observe that a larger L results in a smaller number of beacons but has higher security risk. Thus finding an L of good trade-off is important. For this, we studied a number of networks including real ISP networks (the Rocketfuel data) and small-world scale-free networks, and found that, surprisingly enough, a small L = 5 seems a good choice. Efficient algorithms for this NP-hard problem are also provided.