Network engineering and tomography

Network topology inference and management: We are exploring the application of the network coding paradigm to topology inference and management. Our goal was to infer the topology of a network using multiple sources and observations in the network and manage the topology to be suitable for given applications. We have explored several aspects of this problem including using subspace properties for topology inference, rewiring algorithms for peer-to-peer content delivery networks and end-to-end topology inference methods for network coded systems.

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 subspaces spanned 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.

The performance of peer-to-peer (P2P) networks depends critically on the good connectivity of the overlay topology. 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. 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, it is integrated in the normal content distribution.

We consider networks where multiple sources send probes and intermediate nodes locally combine probe packets (perform XOR-operations on incoming links). In previous work 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. 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).

Link loss monitoring: 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. We consider networks where nodes are equipped with network coding capabilities and 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.

Spatio-temporal traffic matrix modeling: One hurdle in spatio-temporal traffic characterization is the traffic measurement infrastructure. However, recent progress has shown that there could be efficient ways to infer the overall n x n traffic matrix between n nodes. Therefore, we are presented with an opportunity to analyze these measured/inferred traffic matrices and infer whether there are fundamental structural properties in the network traffic flow. We study spatio-temporal structural properties of network traffic through an empirical study as well as understanding the relationship of traffic flow and the underlying network topology. Such models could have significant impact on network engineering in applications ranging from network provisioning to anomaly detection (using spatio-temporal fingerprints).