Abstract
The network discovery (verification) problem asks for a minimum subset Q ⊆ V of queries in an undirected graph G = (V,E) such that these queries discover all edges and non-edges of the graph. In the distance query model, a query at node q returns the distances from q to all other nodes in the graph. In the on-line network discovery problem, the graph is initially unknown, and the algorithm has to select queries one by one based only on the results of previous queries. We give a randomized on-line algorithm with competitive ratio \(O(\sqrt{n\log{n}})\) for graphs on n nodes. We also show lower bounds of \(\Omega(\sqrt{n})\) and Ω(logn) on the competitive ratio of deterministic and randomized on-line algorithms, respectively. In the off-line network verification problem, the graph is known in advance and the problem is to compute a minimum number of queries that verify all edges and non-edges. We show that the problem is \(\mathcal{NP}\)-hard and present an O(logn)-approximation algorithm.
Work partially supported by European Commission – Fet Open project DELIS IST-001907 Dynamically Evolving Large Scale Information Systems, for which funding in Switzerland is provided by SBF grant 03.0378-1.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Achlioptas, D., Clauset, A., Kempe, D., Moore, C.: On the bias of traceroute sampling; or, power-law degree distributions in regular graphs. In: Proc. 37th Ann. ACM Symp. Theory of Computing (STOC 2005), pp. 694–703 (2005)
Aggarwal, V., Bender, S., Feldmann, A., Wichmann, A.: Methodology for estimating network distances of Gnutella neighbors. In: Proceedings of the Workshop on Algorithms and Protocols for Efficient Peer-to-Peer Applications, INFORMATIK 2004 (2004)
Barford, P., Bestavros, A., Byers, J., Crovella, M.: On the marginal utility of deploying measurement infrastructure. In: Proc. ACM SIGCOMM Internet Measurement Workshop (November 2001)
Beerliová, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihaľák, M., Ram, L.S.: Network discovery and verification. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 127–138. Springer, Heidelberg (2005)
Clip2. The Gnutella protocol specification v0.4 (2001), http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf
Dall’Asta, L., Alvarez-Hamelin, I., Barrat, A., Vázquez, A., Vespignani, A.: Statistical theory of internet exploration. Physical Review E 71 (2005)
Dall’Asta, L., Alvarez-Hamelin, I., Barrat, A., Vázquez, A., Vespignani, A.: Exploring networks with traceroute-like probes: theory and simulations. Theoretical Computer Science (to appear, 2006)
Di Battista, G., Erlebach, T., Hall, A., Patrignani, M., Pizzonia, M., Schank, T.: Computing the types of the relationships between autonomous systems. IEEE/ACM Transactions on Networking (submitted, 2005)
DIMES. Mapping the Internet with the help of a volunteer community, http://www.netdimes.org/
Erlebach, T., Hall, A., Mihal’ák, M., Hoffmann, M.: Network discovery and verification with distance queries. Research Report CS-06-002, Department of Computer Science, University of Leicester (March 2006)
Gao, L.: On inferring autonomous system relationships in the internet. IEEE/ACM Transactions on Networking 9(6), 733–745 (2001)
Govindan, R., Reddy, A.: An analysis of internet inter-domain topology and route stability. In: Proc. IEEE INFOCOM 1997 (April 1997)
Govindan, R., Tangmunarunkit, H.: Heuristics for Internet map discovery. In: Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000, pp. 1371–1380 (2000)
Internet Mapping Project. Lucent Bell Labs, http://www.cs.bell-labs.com/who/ches/map/
Oregon RouteViews Project. University of Oregon, http://www.routeviews.org
Subramanian, L., Agarwal, S., Rexford, J., Katz, R.: Characterizing the internet hierarchy from multiple vantage points. In: Proc. IEEE INFOCOM 2002 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Erlebach, T., Hall, A., Hoffmann, M., Mihaľák, M. (2006). Network Discovery and Verification with Distance Queries. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_10
Download citation
DOI: https://doi.org/10.1007/11758471_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34375-2
Online ISBN: 978-3-540-34378-3
eBook Packages: Computer ScienceComputer Science (R0)