Network verification via routing table queries

•Any network of n nodes needs Ω(log⁡log⁡n)Ω(log⁡log⁡n) queries to be verified.•Constant diameter networks need Ω(log⁡n)Ω(log⁡n) queries.•There is no o(log⁡n)o(log⁡n)-approximation algorithm for diameter 2 networks, unless P=NPP=NP.•We give an O(log⁡n)O(log⁡n)-approximation algorithm for diameter 2 networks.•We give exact linear-time algorithms for paths, trees, and cycles of even length.

The network verification problem is that of establishing the accuracy of a high-level description of its physical topology, by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes to be queried so as to univocally identify the graph. This problem has been studied with respect to different 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.