Wired networks consist of a series of point-to-point links that are connected as a communication graph. We are interested in several fundamental questions that span from achievable rate bounds to algorithms and coding techniques for network information flow. Our research program is especially focused on new fundamental questions and approaches that arise from and feed to application areas.

Traditionally network coding is employed for information dissemination (multicats), but new applications give rise to different traffic demands which are non-uniform. We have shown that using ideas from network coding one can develop algorithms for satisfying non-uniform demands that give significant rate advantage over traditional methods when groups of users have different graph min-cuts. We are investigating the use of network coding techniques for a variety of traffic demand scenatios. These form fundamental questions that will also impact application areas like multimedia delivery.

Delay and processing complexity are important considerations in network information delivery. We have examined communication through a cascade of L identical discrete memoryless channels, where the source and destination node of this cascade are allowed to use coding schemes of arbitrary complexity, but the intermediate (relay) nodes are restricted by delay considerations to process only blocks of a fixed length. We showed that the intermediate nodes need only process blocks of length greater than log(L) to achieve the min-cut capacity even asymptotically in L. At the other extreme, if the intermediate nodes can only process constant block-lengths, we can show that the only rate that can be sent is the zero-error capacity of the DMC. This result immediately opens up questions on the role of finite processing for other networks, and on whether the throughput-delay trade off has a similar characterization. We have also developed rateless codes for packet erasure networks with finite intermediate node processing and memory capabilities. These are sparse, linear codes specifically tailored to line networks (or single paths), but give intrigying suggestions for generalization to arbitrary networks.

The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N>1 receivers can also be achieved using packets of length log N bits, if the operations the intermediate nodes perform are deterministally known at the receivers. In a recent work, we calculated the capacity in the case where these operations are unknown, and characterize how the capacity depends on the min-cut value and the packet length.

Finally, there are natural connections between network coding and combinatorics that we are exploring. Our studies in network information flow revealed structural properties of the graph through a method we developed termed subtree decomposition. This decomposition allowed us to show that very different networks are equivalent from the coding point of view, facilitating code design and providing for several cases sharp bounds on the alphabet size needed for achieving the min-cur bound in network coding. These ideas also revealed a connection between graph coloring and alphabet size in network coding. In our examination of average throughput benefits of network coding, we demonstrated that the throughput gains over routing can be the average throughput gap between plain routing and network coding can be quantified in terms of the integrality gap of a standard formulation of the Steiner tree problem. We believe several more intricate connects between combinatorics and network coding are still to be discovered which will have an important influence on fundamental questions of network information flow.

Wireless networks are characterized by limited resources (energy, bandwdith) and complex signal interactions due to the wireless broadcasting nature. Our approach utilizes the broadcasting capabilities to advantage for network coding rather than mitigating it. For example, we have shown that network coding can inherently use the broadcast nature to make every transmission maximally useful in reciprocated communications. This property can be realized though decentralized algorithms suitable for even dynamically changing networks. These ideas for information exchange naturally lead to questions about other traffic demand patterns and connect due to the increased energy efficiency they offer to sensor networks. The use of feedback with broadcast network codes can significantly reduce delay in delivery, and offer mechanisms to achieve fairness among competing users. Therefore the role of feedback with wireless network coding is a topic that we plan to explore further.

The deterministic approach proposed by Avestimehr, Diggavi and Tse shows that a simple linear deterministic model approximately captures the interference limited regime of wireless networks. Using this approach they proved an information theoretic min-cut max-flow result using exponential complexity processing at network nodes. We have developed a Ford-Fulkerson like polynomial time algorithm that provably achieves the capacity \cite{soda09}. The impact of this algorithm is to develop provably computationally efficient wireless network information flow algorithms. Translating these ideas to noisy Gaussian networks using lattice codes is part of our ongoing work. We plan to extend these combinatorial methods for other wireless network flow instances of relay-interference networks \cite{allerton08}. These ideas open up fundamentally new network algorithm questions which are both rich in theoretical questions as well as practical insights.

Sensor networks are transforming the way we deal with the physical world with applications ranging from enviromental monitoring to security and health-care. Each application has different requirements and constraints which have to be carefully designed for. However, three broad needs are common to most sensor networks: energy efficiency, speed of data collection and reliability, for example to node failures or malicious attacks. Our research program addresses these broad neds by developping fundamentally new techniqes. We are currently validating these ideas in a testbed of Tinyos sensor nodes.

In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit. For instance, sensors used for monitoring whether and at what location an environmental hazardous situation may occur need to send their location and very few bits, albeit at very short time intervals, to convey as fast as possible the alarm information. We are interested in addressing the question of how should communication happen in such identity-aware sensor networks. To do so, we need to re-examine the traditional source-identity/message separation and propose a scheme for jointly encoding the two, through a specifically designed coding scheme. We have recently developed a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks—for instance, node failures, or large numbers of nodes where only few are active during each reporting round. We are planning to extend these ideas to sensor networks that convey GSM (location) information, to infrastracture sensor networks for transportation networks.

In many situations, what one does not say conveys information, just as what one might say. This idea can be used in wireless sensor networks by utilizing silence to convey information and thereby reducing the energy used. We explored this in the context of function computation in wireless sensor networks. We develop provable protocols that allow information to be inferred by the fact that nodes remain silent. We thus use silence and time to minimize the amount of communication required to compute various functions. We investigate the time-complexity trade-off such protocols offer, in a communication-complexity framework. We focus our attention on symmetric functions (where the ordering of the variables do not matter), that include most statistical functions and functions of interest for sensor networks. For such functions we develop methods that are optimal (worst case and average communication complexity). We believe that these ideas are very promising for health-monitoring sensor networks (for example, on-the-body sensors), where minimizing the number of node transmissions can also reduce health risks, and this is a direction we plan to further pursue.

Multipath diversity techniques in sensor networks construct multiple paths from each node sensor to the sink, allowing more freedom in route selection, and thus achieving higher reliability; less intuitively, under certain circumstances, they even achieve lower energy consumption. Network coding allows to achieve the benefits of multipath diversity, namely, increased reliability, by opportunistically taking advantage of broadcasting, at a significant savings of the network resources. Our first proposed techniques are currently being deployed in a TinyOs prototype at EPFL. We plan to continue working both on the theoretical foundations as well as prototype implementations of these ideas, as we believe they can have a significant impact in future sensor networks.

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.