Network Tomography

A critical network engineering functionality is to monitor the health of a network and adapt its use to the demands of the end users. To do this we need control mechanisms to infer network characteristics efficiently and accurately. Active network tomography aims at inferring internal network characteristics by sending and collecting probe packets from the edge of the network. Passive tomography infers network information from passive observations of regular network traffic. Such information is an important input to various control and traffic engineering decisions, both at the network and at the application layers, and thus there is a significant body of work dedicated to this problem. In our work, we re-visit the problem of active and passive tomography in networks that have network coding capabilities.

In active link loss tomography the characteristics of interest is the loss rate of individual links. We are interested in designing a set of novel techniques that leverage network coding functionalities. Our preliminary results show significant improvement in several aspects, including the identifiability of links, the tradeoff between accuracy of estimation and bandwidth efficiency, and the complexity of probe path selection. We are currently extending these ideas in active topology monitoring.

In another line of work, we focus our attention to systems that employ randomized network coding techniques for information dissemination, such as peer-to-peer networks. Such systems rely on the use of coding vectors to convey to the receivers the linear combinations of the source packets. In our work, by developing properties of randomly selected subspaces over finite fields, we show that the coding vectors implicitly carry topological information about the network and its state that can be passively collected. We leverage this information towards a number of applications that are interesting in their own merit, and range from topology inference, to peer-initiated bottleneck discovery in P2P systems, and locating the position of malicious Byzantine attackers in a network.

We believe and have shown through our preliminary work that, equipping networks with network coding capabilities, apart from well-documented benefits in information transfer, can also have a significant impact in a number of network management and control applications. We plan in this line of work to further explore these ideas and their impact in practical networks.

Publications

A PHP Error was encountered

Severity: Warning

Message: Creating default object from empty value

Filename: gettext/gettext.inc

Line Number: 195

  1. P. Sattari, A. Markopoulou and C. Fragouli, Multiple source multiple destination topology inference using network coding, in Network Coding, Theory, and Applications, 2009. NetCod '09. Workshop on, 2009
    Download:  
    Citation: BibTeX RIS
    In this paper, we combine network coding and tomographic techniques for topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. We combine and extend two ideas that have been developed independently. On one hand, network coding introduces topology-dependent correlation, which can then be exploited at the receivers to infer the topology. On the other hand, it has been shown that a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem can be decomposed into multiple two source, two receiver subproblems. Our first contribution is to show that, when intermediate nodes perform network coding, topological information contained in network coded packets allows to accurately distinguish among all different 2-by-2 subnetwork components, which was not possible with traditional tomographic techniques. Our second contribution is to use this knowledge to merge the subnetworks and accurately reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.
  2. M. Jafari Siavoshani, C. Fragouli and S. N. Diggavi, On Locating Byzantine Attackers, Network Coding Workshop: Theory and Applications, 2008
    Download:  
    Citation: BibTeX RIS
    We examine networks that employ network coding, and are subject to Byzantine attacks. We consider systems where an appropriate network error correcting scheme is employed that is able to correct (up to a certain number of) Byzantine errors. Given this setup, we formulate the problem of locating these malicious nodes that insert errors. We utilize the subspace properties of (randomized) network coding to develop algorithms to locate the Byzantine attackers.
  3. M. Jafari Siavoshani, C. Fragouli, S. N. Diggavi and C. Gkantsidis, Bottleneck discovery and overlay management in network coded Peer-to-Peer systems, SIGCOMM INM, 2007
    Download:  
    Citation: BibTeX RIS
    The performance of peer-to-peer (P2P) networks depends critically on the good connectivity of the overlay topology. In this paper we study P2P networks for content distribution (such as Avalanche) that use randomized network coding techniques. The basic idea of such systems is that peers randomly combine and exchange linear combinations of the source packets. A header appended to each packet specifies the linear combination that the packet carries. In this paper we show that the linear combinations a node receives from its neighbors reveal structural information about the network. We propose algorithms to utilize this observation for topology management to avoid bottlenecks and clustering in network-coded P2P systems. Our approach is decentralized, inherently adapts to the network topology, and reduces substantially the number of topology rewirings that are necessary to maintain a well connected overlay. Moreover, this is done passively during the normal content distribution. This work demonstrates another value of using network coding and complements previous work that showed network coding achieves high utilization of the network resources.
  4. M. Gjoka, C. Fragouli, P. Sattari and A. Markopoulou, Loss Tomography in General Topologies with Network Coding, IEEE GLOBECOM, 2007
    Download:  
    Citation: BibTeX RIS
    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.
  5. C. Fragouli, A. Markopoulou, R. Srinivasan and S. N. Diggavi, Network monitoring: it depends on your points of view, ITA, 2007
    Download:  
    Citation: BibTeX RIS
    End-to-end active network monitoring infers network characteristics by sending and collecting probe packets from the network edge, while probes traverse the network through multicast trees or a mesh of unicast paths. Most reported methods consider given source and receiver locations and study the path selection and the associated estimation algorithms. In this paper, we show that appropriately choosing the number of sources and receivers, as well as their location, may have a significant effect on the accuracy of the estimation; we also give guidelines on how to choose the best ``points of view'' of a network for link loss monitoring purposes. Though this observation applies across all monitoring methods, we consider, in particular, networks where nodes are equipped with network coding capabilities; our framework includes as special cases the scenarios of pure multicast and network coding. We show that, in network-coding enabled networks, multiple source active monitoring can exploit these capabilities to estimate link loss rates more efficiently than purely tomographic methods. To address the complexity of the estimation problem for large networks, we also propose efficient algorithms, including the decomposition into smaller multicast inference problems, belief-propagation, and a MINC-like algorithm.
  6. M. Jafari Siavoshani, C. Fragouli and S. N. Diggavi, Subspace properties of randomized network coding, in IEEE Information Theory Workshop (ITW), 2007
    Download:  
    Citation: BibTeX RIS
    Randomized network coding has network nodes randomly combine and exchange linear combinations of the source packets. A header appended to the packet, called coding vector, specifies the exact linear combination that each packet carries. The main contribution of this work is to investigate properties of the subspacesspanned by the collected coding vectors in each network node. We use these properties to exhibit the relationship between the network topology and the subspaces collected at the nodes. This allows us to passively infer the network topology for a general class of graphs.
  7. C. Fragouli, A. Markopoulou and S. N. Diggavi, Topology inference using network coding, Allerton, 2006
    Download:  
    Citation: BibTeX RIS
    The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network using multiple sources and observations at the edges of the network. In particular, we consider networks where multiple sources send probes and intermediate nodes locally combine probe packets (perform XOR-operations in incoming links). In previous works (e.g., Ratnasamy \& McCanne '99; Duffield et al '02), the correlation between the observed packet loss patterns is used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among multiple probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from end-host observations. Preliminary numerical results illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).
  8. C. Fragouli and A. Markopoulou, A Network Coding Approach to Network Monitoring, Allerton, 2005
     
    Citation: BibTeX RIS
    Network Monitoring is a challenging problem that has received a lot of attention in the Internet community, particularly in the context of overlay networks. Independently, recent advances in Network Coding have shown that it is possible to increase network capacity and better share the available resources by allowing intermediate nodes to perform processing operations, in addition to just forwarding packets. In this work, we propose the use of Network Coding techniques to improve Network Monitoring. As a specific application, we use our approach for the well-known problem of network tomography, and in particular for inferring link loss rates from end-to-end measurements. We demonstrate that our approach can decrease the bandwidth used by probes, improve the accuracy of estimation, and decrease the complexity of selecting paths or trees to send probes. Overall, we argue that the use of Network Coding techniques shows great promise for improving several aspects of monitoring in overlay networks.

research/tomography.txt · Last modified: 2011/04/24 11:43 by lokeller
© ARNI/EPFL, 1015 Lausanne
webmaster