Afficher la notice abrégée

Network Verification via Routing Table Queries

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBAMPAS, Evangelos
hal.structure.identifierUniversità degli Studi di Sassari = University of Sassari [Sassari] [UNISS]
dc.contributor.authorBILÒ, Davide
hal.structure.identifierNational Research Council of Italy | Consiglio Nazionale delle Ricerche [CNR]
dc.contributor.authorDROVANDI, Guido
hal.structure.identifierUniversità degli Studi di Roma Tor Vergata [Roma, Italia] = University of Rome Tor Vergata [Rome, Italy] = Université de Rome Tor Vergata [Rome, Italie]
dc.contributor.authorGUALÀ, Luciano
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKLASING, Ralf
hal.structure.identifierDipartimento di Informatica [Italy] [DI]
hal.structure.identifierIstituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti” [IASI]
dc.contributor.authorPROIETTI, Guido
dc.date.accessioned2024-04-15T09:46:32Z
dc.date.available2024-04-15T09:46:32Z
dc.date.issued2011
dc.date.conference2011-06
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198016
dc.description.abstractEnWe 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.
dc.language.isoen
dc.title.enNetwork Verification via Routing Table Queries
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-22212-2_24
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page270--281
bordeaux.volume6796
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleSIROCCO 2011
bordeaux.countryPL
bordeaux.conference.cityGdańsk
bordeaux.peerReviewedoui
hal.identifierhal-00647362
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00647362v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2011&rft.volume=6796&rft.spage=270--281&rft.epage=270--281&rft.au=BAMPAS,%20Evangelos&BIL%C3%92,%20Davide&DROVANDI,%20Guido&GUAL%C3%80,%20Luciano&KLASING,%20Ralf&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée