Tomographic techniques allow the reconstruction of network topologies with no need for cooperation from internal routers. However, most of such mechanisms adopt a method of node clustering producing trees that reveal only a partial structure of the network. Therefore, we have proposed a novel approach to topology discovery based on packet sandwich probes and decision theory allowing to retrieve a complete picture of the network, which includes the detection of all the internal nodes along with the values of capacities of the interconnecting links. Such an approach, as well as all the standard techniques of topology discovery, reconstructs the spanning tree of the probe sender only. Hence, in this paper a specific technique is presented for merging the spanning trees associated to all different roots, in order to provide a complete representation of the network. Such a method does not require further probing traffic and is specifically designed to merge topology reconstructions where all the nodes of the network (not only the branching nodes) are revealed, along with link capacities. Our algorithm performs quite well on a wide set of both synthetic and realistic topologies, and in many cases provides a picture of the network which is exactly equivalent to the original one.

Merging Spanning Trees in Tomographic Network Topology Discovery

GIORDANO, STEFANO;OPPEDISANO, FRANCESCO;PROCISSI, GREGORIO;VITUCCI, FABIO
2009

Abstract

Tomographic techniques allow the reconstruction of network topologies with no need for cooperation from internal routers. However, most of such mechanisms adopt a method of node clustering producing trees that reveal only a partial structure of the network. Therefore, we have proposed a novel approach to topology discovery based on packet sandwich probes and decision theory allowing to retrieve a complete picture of the network, which includes the detection of all the internal nodes along with the values of capacities of the interconnecting links. Such an approach, as well as all the standard techniques of topology discovery, reconstructs the spanning tree of the probe sender only. Hence, in this paper a specific technique is presented for merging the spanning trees associated to all different roots, in order to provide a complete representation of the network. Such a method does not require further probing traffic and is specifically designed to merge topology reconstructions where all the nodes of the network (not only the branching nodes) are revealed, along with link capacities. Our algorithm performs quite well on a wide set of both synthetic and realistic topologies, and in many cases provides a picture of the network which is exactly equivalent to the original one.
9781424434343
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: http://hdl.handle.net/11568/200821
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact