Network coding for next-generation networks

As a discipline at the intersection of information theory and classical stochastic network analysis, network coding promises interesting future applications, and hence presents newer fundamental theoretical problems in the field of network engineering and design. While much research on network coding is concerned with the analysis and construction of capacity achieving codes, our focus in this proposal will be on the impact of Random Linear Coding (RLC) in next generation wireline and wireless networks. We consider two techniques of coding for networks: one where coding is performed at every intermediate node of a network, and the other where only source nodes encode across packets. For either case, we present scenarios where network coding offers significant performance gains. Under network coding at every intermediate node, the previously intractable min-cost multicast problem has been formulated in terms of a convex optimization. Recent work has focused on cooperative decentralized algorithms to solve this, most using primal-dual techniques. Instead, here we formulate a decentralized non-cooperative version of the problem where each user routes greedily to minimize its own cost and study how the resulting user-equilibrium cost compares to the global (social) optimum. Based on our results, simple greedy decentralized algorithms are proposed for distributed min- cost flow adaptation at nodes in the network. In the context of wireless networks, achieving unicast capacity is complicated by wireless broadcast and interference. We note that while much of extant network coding research has been on wireline networks, our understanding of network codes applied to wireless networks is still limited. We abstract broadcast and interference properties in the wireless channel by a finite field addition channel, to arrive at a Broadcast and Additive Interference Network (BAIN) and show that there exists a graph transformation, and a corresponding sample path coupling, to model a BAIN as a regular wireline network with network coding at intermediate nodes. Based on this analysis, we leverage existing results from network coding for wireline networks to arrive at asymptotically tight bounds on unicast capacity for BAINs. Next, we consider network coding at the source, with no buffers at intermediate nodes, as an alternative to traditional buffering of transient packets at intermediate nodes in multi-hop networks, thereby virtually sharing memory between links on a flow path. We call this spatial buffer multiplexing: where buffering and coding implemented at the source alone compensates for packet loss at any downstream bufferless link. Using many-sources large deviations analysis, we show that network coding promises dramatic improvements in resource allocation and buffer sizing in large scale networks with large diameters (such as spatial networks) under comparable network-wide packet drop probabilities (QoS). However, using large buffer large deviations analysis, we show that network coding performs poorly against traditional queueing when it is not possible to have stochastic multiplexing with many other sources at intermediate nodes. Finally, since network coding at the source may be used to dynamically buffer dropped packets at each fixed capacity link due to bursty fixed-rate arrivals at each source, we would like to also examine the dual scenario where the source rate (TCP window size) is controlled to deliver the maximum average throughput in a time-varying noisy wireless link (with varying information theoretic capacity) shared by many TCP connections. We show that network coding at the source promises an orderwise improvement in the mean TCP window size distribution as compared to the case where network coding is not used.