A New Framework for the Practice of Wireless Network Coding
We develop a systematic framework called DEDI that is based on differential equations (DE) and differential inclusions (DI) to enable studying the dynamics of network coding in an elegant yet simple manner. DI is a generalization of the dynamical system described by ordinary DEs, allowing them, in particular, to have discontinuous right-hand sides, and they arise extensively in mechanics, electronics and biology. Using both analytical methods and numerical software for solving differential equations and inclusions, this project will investigate the DEDI framework as a:
- Tool for the design and analysis of network coding
- Tool for perturbation and sensitivity analysis of network coding
- Tool for proving theorems related to the power of network coding
- Tool for the study of general and possibly nonlinear forms of network coding
- Tool for crosslayer design in dynamic environments
In the last few years the area of network coding has seen an explosive growth in research activity while being touted as the foundation on which several applications related to the robust operation of both wired and wireless networks can be built. The breadth of areas that have been touched by network coding is vast and includes not only the traditional disciplines of information theory, coding theory and networking, but also topics such as algorithms, combinatorics, distributed storage, network monitoring, content delivery, and security. There has been a rich outpouring of theoretical results for network coding in wireless networks as well as an equally excellent body of work that discusses implementation issues.
In spite of all this excellent progress in this rich area, what has been missing is a simple framework that can allow explaining the evolution of network coding in an arbitrary wireless network. For example, given an arbitrary wireless network and a network coding strategy, a question that remains to be answered is how does the rank/state of the nodes in the network evolve over time. Further, if there are changes in the underlying wireless network either through changes in the PHY layer, MAC layer or due to other factors such as mobility or traffic, how does this impact the evolution of network coding over this arbitrary network? In fact, answering such a question is of paramount importance for network practitioners. Further, is there a tool or framework in existence that can allow predicting this evolution or network behavior? Neither the rich set of theoretical results in this area nor the excellent implementation and system work in this area can provide satisfactory answers to such questions and in this project we set out to establish such a framework that can answer such questions and provide further insights into making network coding a tool closer to the design of real wireless networks.
The approaches taken here have a strong analytical and theoretical focus and are validated as appropriate by simulations. The research agenda is comprehensively developing the DEDI framework to study network coding in arbitrary networks, thereby rendering a tractable design and analysis tool for practitioners of network coding. The results obtained are of great relevance to the anticipated deployment of network coding in a large variety of networking contexts as described earlier. As part of the project, we use numercial DE and DI solvers to develop a software utility that allows analytical insights without having to resort to time consuming simulations. We will make available to the research community at large the software utiltity that we develop using the DEDI framework as an open resource. The use of differential equations and differential inclusions along with associated numerical software also offers an educational opportunity to involve both graduate students and undergraduate students by developing simple yet illustrative modules for studying the evolution of network coding.
Results To Date & Future Work Plan
The results to date have been disseminated through journal and conference papers some of which have already appeared, while others are in the stages of preparation, submission and due to appear. Future directions also include development of radio resource management algorithms and their impact on network coding performance in wireless networks.
Prof. Narayan Mandayam
narayan (AT) winlab (DOT) rutgers (DOT) edu
D. Zhang, N. Mandayam, and S. Parekh, “DEDI: A framework for analyzing rank evolution in random network coding,” IEEE International Symposium on Information Theory, Austin, TX, June 2010.
D. Zhang and N. Mandayam, “Analyzing Multiple Flows in a Wireless Network with Differential Equations and Differential Inclusions, ” IEEE Wireless Network Coding Workshop (WiNC 2010), Boston, MA, June 2010.
D. Zhang and N. Mandayam, “Resource Allocation for Multicast in an OFDMA Network with Random Network Coding,” IEEE International Conference on Computer Communications (INFOCOM), Shanghai, June 2011.
D. Zhang and N. Mandayam, “Analyzing Random Network Coding with Differential Equations and Differential Inclusions,” accepted by IEEE Transactions on Information Theory (to appear in December 2011).