Network Information Flow

OO~ posted @ 2013年10月20日 15:13 in 存储编码 , 1470 阅读

  这篇文章是 Rodolf Ahlswede 等人在 2000 年发表的一篇关于网络编码的论文。之所以把这篇论文作为我存储编码模块的第一篇论文,主要是它给我的触动还是蛮大的,真正 fire on my enthusiast for my major。

  文中在摘要中指出本文真正要解决的问题以及意义。一个新的问题 network information flow(下面简称NIF) inspired by computer network apps.,那么,基于该 NIF,如何特征化可容许的 coding rate region?所以本文针对这个问题,做了一系列分析,并且最后对一个 source node 的 NIF 得到了一个简单的 coding rate region,也可以描述成 max-flow min-cut 理论。本文最大的贡献是给出并证明了通过在节点编码,也即网络编码,网络带宽能被减少。

  跳过文中的铺垫,直接切入主题。当 NIF 中任一(源节点只有一个,sink 节点可以有多个) max-flow min-cut 大于等于信息源节点的信息率时,此时编码是可行的。从下面几个图以及直观的例子可以作了解(文中图 6 对该理论做了一个解释)。

  当 sink 节点只有一个时,如下图。从源 s 发送 bits 至 sink 节点,终结点知道哪个 bit 是从哪个边传过来的,故可以很好的进行恢复。此时不需要编码就可以达到最优,每个 bit 会被当做一个 entity。

  

  当终结点不止是一个节点时,要实现最优,网络编码也即在节点处的处理转换时不可避免的。

  上图中给出了两个 sink 节点的情况,其中源节点到终结点 t1、t2 的 max-flow min-cut 都是 2,从源节点发送两个 bit 至终结点,在 node3 处必须又一次转换,才能最优的传送这两个节点到达终结点。

  上图给出了网络编码的优势,接下来的图我们可以量化分析网络编码的优势。下图中,源节点到每个终结点的 max-flow min-cut 均为 2,此时将两个 bit 都传给这些终结点。综合分析,网络带宽为 9(边加起来),如果不用编码的方法传输,则至少还要还要一个额外的带宽才能将两个 bit 都传达给终结点,所以,最后通过使用网络编码,整体的传输带宽可以节省 10%。

  接着文章将上述结论进一步特征化,且给出一系列复杂证明(略),最后用一个 example 对特征化作了说明。而多个源节点的情况比较复杂(这类情况更加符合 P2P 网络),文章只是作了简要说明,指出要获得最优化的传输带宽,可能需要将几个源节点合并起来一起编码,不同于单个源节点的情况。

  结论部分,作者重申本文的贡献(多播网络使用的传统技术并不是最优的)以及前面的 max-flow min-cut 理论。展望未来里,作者提到 multisource multisink problem 是一个非常有挑战的问题;单源节点网络中仍然存在很多问题亟待解决;带权重的图问题,我们应该多一些关注和研究(随着信息技术的发展,这确实在现今的生活中会有很大的应用,譬如一些消息是紧急的,所以较一些非紧急的消息必须有更优先的发送权,在路径的选择上,我们是否也应该专门设置一条权值较大的路?等等一系列问题)。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter