The efficient use of bandwidth will be a critical factor in determining the scalability of the next-generation Internet. The investigator studies the question of how much efficiency is gained in a network by giving nodes the capability to encode and decode information in the process of transmitting it, a paradigm known as network coding. The research aims for a more complete understanding of the capabilities and limitations of network coding in structurally complex networks, to be achieved using tools from the theory of algorithms, combinatorial optimization, and computational complexity.
The research delineates a role for the theory of algorithms and combinatorial optimization within the study of network coding, incorporating core notions such as approximation algorithms and primal-dual techniques. Exact algorithms for computing the achievable rate region are sought in special classes of network coding problems, most notably for multiple unicast sessions in undirected graphs. Approximation algorithms are sought for general graphs; it is likely that non-trivial approximation algorithms will highlight purely structural features of network coding problems ( e.g. succinct certificates of infeasibility) which will spur further progress in the area. The relationship between network coding rates and other graph parameters, including the maximum concurrent multicommodity flow rate and parameters based on edge cuts, will be explored. Finally, the research investigates the achievable rate region for network coding problems in which nodes have bounded storage.
