We address the problem of verifying the accuracy of a map of a network by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph G = (V,E), and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes of G to be queried so as to univocally identify G. This problem has been faced w.r.t. a couple of query models assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. First, we show that any network of n nodes needs Ω(loglogn) queries to be verified. Then, we prove that there is no o(logn)-approximation algorithm for the problem, unless \sf P=\sf NP , even for networks of diameter 2. On the positive side, we provide an O(logn)-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees, and cycles of even length.

Network Verification via Routing Table Queries / Bampas, Evangelos; Bilò, Davide; Drovandi, Guido; Gualà, Luciano; Klasing, Ralf; Proietti, Guido. - 6796:(2011), pp. 270-281. (Intervento presentato al convegno 18th International Colloquium on Structural Information and Communication Complexity nel 26-29 Giugno 2011) [10.1007/978-3-642-22212-2_24].

Network Verification via Routing Table Queries

BILÒ, Davide;
2011-01-01

Abstract

We address the problem of verifying the accuracy of a map of a network by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph G = (V,E), and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes of G to be queried so as to univocally identify G. This problem has been faced w.r.t. a couple of query models assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. First, we show that any network of n nodes needs Ω(loglogn) queries to be verified. Then, we prove that there is no o(logn)-approximation algorithm for the problem, unless \sf P=\sf NP , even for networks of diameter 2. On the positive side, we provide an O(logn)-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees, and cycles of even length.
2011
978-3-642-22211-5
Network Verification via Routing Table Queries / Bampas, Evangelos; Bilò, Davide; Drovandi, Guido; Gualà, Luciano; Klasing, Ralf; Proietti, Guido. - 6796:(2011), pp. 270-281. (Intervento presentato al convegno 18th International Colloquium on Structural Information and Communication Complexity nel 26-29 Giugno 2011) [10.1007/978-3-642-22212-2_24].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11388/70723
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact