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.
Network verification via routing table queries / Bampas, Evangelos; Bilò, Davide; Drovandi, Guido; Guala', Luciano; Klasing, Ralf; Proietti, Guido. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 81:1(2015), pp. 234-248. [10.1016/j.jcss.2014.06.003]
Network verification via routing table queries
BILÒ, Davide;
2015-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.