Combinatorial and Algorithmic Aspects of Network Coding

网络编码的组合和算法方面

• 批准号: 0729102
• 负责人: Robert Kleinberg
• 金额: $ 25万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0729102&HistoricalAwards=false
• 关键词: Combinatorial; Algorithmic; Aspects; Network; Coding

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.

带宽的有效利用将是决定下一代互联网可扩展性的关键因素。研究人员研究的问题是，通过赋予节点在传输过程中对信息进行编码和解码的能力，在网络中获得多大的效率，这是一种称为网络编码的范式。这项研究的目的是更全面地了解网络编码在结构复杂的网络中的能力和局限性，利用算法、组合优化和计算复杂性的理论工具来实现。这项研究描述了算法和组合优化理论在网络编码研究中的作用，结合了诸如近似算法和原始-对偶技术等核心概念。在特殊类别的网络编码问题中寻找用于计算可达速率区域的准确算法，最显著的是用于无向图中的多个单播会话。人们为一般的图寻找近似算法；很可能非平凡的近似算法将突出网络编码问题的纯结构特征(例如，简明的不可行证书)，这将促进该领域的进一步发展。网络编码率和其他图参数之间的关系，包括最大并发多种商品流率和基于边割的参数，将被探索。最后，研究了节点具有有限存储空间的网络编码问题的可达速率域。