Limits of Information Flow in Networks of Two-Way Channels

通信网络在当今技术社会的信息传播中至关重要。 网络优化理论的目标是最有效地利用网络资源，但最近网络编码中的网络已经表明，该理论中流量守恒的标准假设对通信网络的工作施加了人为的限制。 网络信息论考虑了更一般的通信模型，并给出了多个发送者和接收者通信系统中信息传递极限的一些界限，本研究融合了网络优化理论和网络信息论的一些方面，旨在发现和规定通信网络中信息传递的新极限。 研究人员使用来自信息论的双向通道作为通信网络的相邻处理器之间的传输介质的一般模型，并解决与双向通道网络的分析和设计有关的基本优化问题。研究人员寻求在多播设置和网络编码可以或不能改善路由的情况下的广泛分类的最佳路由算法。 调查人员进一步的目的是分类网络的情况下，bidirectedcut set绑定派生使用信息theoreticarguments是紧的，并探索网络信息对应基尔霍夫定律时，bidirectedcut set绑定不紧。 该研究还涉及扩展最小成本流量的概念，这是处理服务质量问题和设计满足信息传输要求的最小成本或容量的网络的初始方法。

Communication networks are critically important in thedissemination of information in today's technologicalsociety. Several academic disciplines have undertakenthe study of various aspects of their operation, butan integrated theory of networking has been elusive.The objective of network optimization theory is tomost effectively use network resources, but recentwork in network coding has demonstrated that a standardassumption of flow conservation from this theory hasimposed artificial restrictions on the workings ofcommunication networks. Network information theoryconsiders more general models of communication andoffers some bound on the limits of information transferin a communication system involving multiple sendersand receivers.This research fuses aspects of network optimizationtheory and network information theory in order to findand specify new limits of information transfer acrossa communication network. The investigators use thetwo-way channel from information theory as a generalmodel of the transmission medium between neighboringprocessors of a communication network and addressfundamental optimization problems pertaining to theanalysis and design of networks of two-way channels.The investigators seek optimal routing algorithms inmulticast settings and a broad classification ofsituations where network coding can or cannot improveupon routing. The investigators further aim tocategorize network scenarios in which a bidirectedcut set bound derived using information theoreticarguments is tight and to explore a network informationcounterpart to Kirchoff's law when the bidirectedcut set bound is not tight. The research alsoinvolves extending the notion of minimal cost flowas an initial approach to treating quality-of-serviceissues and devising networks with least cost orcapacity that meet requirements on information transfer.