DocumentCode :
2494793
Title :
Loss Tomography in General Topologies with Network Coding
Author :
Gjoka, Minas ; Fragouli, Christina ; Sattari, Pegah ; Markopoulou, Athina
Author_Institution :
UC Irvine, Irvine
fYear :
2007
fDate :
26-30 Nov. 2007
Firstpage :
381
Lastpage :
386
Abstract :
Network tomography infers internal network characteristics by sending and collecting probe packets from the network edge. Traditional tomographic techniques for general topologies typically use a mesh of multicast trees and/or unicast paths to cover the entire graph, which is suboptimal from the point of view of bandwidth efficiency and estimation accuracy. In this paper, we investigate an active probing method for link loss inference in a general topology, where multiple sources and receivers are used and intermediate nodes are equipped with network coding, in addition to unicast and multicast, capabilities. With our approach, each link is traversed by exactly one packet, which is in general a linear combination of the original probes. The receivers infer the loss rate on all links by observing not only the number but also the contents of the received probes. In this paper: (i) we propose an orientation algorithm that creates an acyclic graph with the maximum number of identifiable edges (ii) we define probe combining coding schemes and discuss some of their properties and (iii) we present simulation results over realistic topologies using Belief-Propagation (BP) algorithms.
Keywords :
encoding; network topology; tomography; Belief Propagation algorithms; active probing; general topologies; link loss inference; loss tomography; network coding; Bandwidth; Galois fields; Monitoring; Multicast algorithms; Network coding; Network topology; Probes; Tomography; Tree graphs; Unicast;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE
Conference_Location :
Washington, DC
Print_ISBN :
978-1-4244-1042-2
Electronic_ISBN :
978-1-4244-1043-9
Type :
conf
DOI :
10.1109/GLOCOM.2007.78
Filename :
4410988
Link To Document :
بازگشت