（信号与信息处理专业论文）网络编码若干问题的研究.pdf

、茸-1， 北京邮电大学 博士学位论文 网络编码若干问题的研究 ( 申请北京邮电大学工学博士学位) 培养单位： 专业： 研究生： 指导教师： 北京邮电大学信息与通信工程学院 信号与信息处理 李大霖 吴伟陵 二零零九年五月 谚f。一，。 d o c t o r a ld i s s e r t a t i o no fb e i ji n g u n i v e r s i t yo f p o s t sa n dt e l e c o m m u n i c a t i o n s r e s e a r c hi ns o m e a s p e c t s o fn e t w o r k c o d i n gt h o e r y ( s u b m i t t e dt ob e i ji n gu n i v e r s i t yo fp o s t sa n d ，一 j 1 e l e c o m m u n l c a t l o n s f o rt h ed e g r e eo fd o c t o ro fe n g i n e e r i n g ) b y d a l i nl i d i s s e r t a t i o ns u p e r v i s o r ：p r o f w uw e i l i n g m a jo r ：s i g n a la n d i n f o r m a t i o np r o c e s s i n g m a y 2 0 0 9 1ll 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位 本人签名 处，本人承担一切相关责任。 日期l 也啦= 竺 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 絮k 。r日期：垒竺么：皇：竺 日期：2 鲤2 么：f l l_11l 北京邮电人学博r 上论文 摘要 摘要 2 0 0 0 年，a h l s w e d e 等首先提出了网络信息流( n e t w o r ki n f o r m a t i o nf l o w ) 的 模型，在此模型下，可以假定节点间的连接是点到点的，链路上是无噪声的。在 此基础上a h l s w e d e 等研究了组播网络通信的容量问题，并提出了网络编码 ( n e t w o r ke o d i n g ) 的概念。通常的网络通信中，中间节点只担当数据转发的作 用，而不对数据进行处理。在网络编码的模型下，中间节点对接收到的数据流进 行编码处理，然后再发送，在接收端对接收到的已编码数据流进行解码处理。采 用网络编码可以有效地利用网络资源，并且要实现达到网络容量的通信，采用网 络编码是必要的。网络编码理论是近年网络信息论领域的重大突破，引发了广泛 的研究兴趣。 本文对网络编码若干相关的问题进行了研究。在介绍了网络编码的背景，基 本概念和理论后，主要研究了如下几个方面的内容。 网络编码的安全性。安全性是现代网络研究和设计需要考虑的一个重要方 面。本文第3 章首先引入若干辅助数学结果，建立了应用线性网络编码时，线性 独立性和统计独立性的等价性，在此基础上提出了实现信息论意义上安全的充分 必要条件。为保证信源信息的安全性，引入随机密钥信息与信源信息进行编码是 必要的。本文研究了在一种应用网络编码特殊的组播通信情况下，需要引入密 钥信息率的一个下边界。 网络编码的弱安全性。为了保证系统的安全性，通常不得不引入密钥信息， 这就必然会降低通信的有效性。在某些情况下，信息论意义下的安全标准可以适 当的放松以换取传输率的提升。在第4 章中研究了网络编码的弱安全性，提出了 两种弱安全标准的定义，并对其进行了初步的讨论。 网络编码与网络流控。在现代通信网络中，流控( f l o we o n 仃0 1 ) 是保证网络 高效和可靠运行不可或缺的重要组件。特别是在基于分组的网络中，流控机制可 以消除拥塞，提高吞吐，减小时延，以及确保不同数据流间的公正性( f a i m e s s ) 等等。在本文第5 章研究了基于网络编码组播的流控设计问题。首先由k e l l y 等 提出的用效用函数( u t i l i t yr u n i o n ) 描述设计目标和用优化分解获得分布式算法 的方式为研究网络相关问题提供了新的理论工具，更进一步c h i a n g 等提出用优 化分解的方式架构网络为网络研究提供了严格的数学语言。我们把上述网络效用 最大化的研究方式引入到基于网络编码组播通信的流控设计中，采用阶梯分解的 北京邮电人学博：j ：论文摘要 方式( h i e r a r c h i c a ld e c o m p o s i t i o n ) ，提出了一种架构方案，并给出了分布式的流 控算法。 本文的第6 章总结了本文的工作和不足，指出了仍需进一步深入研究的地 方。 网络编码理论为理解网络，设计网络，以及解决网络相关的问题提供了新的 思路，已有的研究成果证明其重要的理论和实际价值。本文在此背景下对网络编 码的若干问题做了初步的研究。本文的工作得到9 7 3 项目和国家重点科技攻关项 目的支持。 关键字：网络编码随机线性网络编码网络安全性网络流控网络效用最 大化优化分解对偶分解网络架构 北京邮电大学博二b 论文英文摘要 a b s t r a c t i n2 0 0 0 ，a h l s w e d ee ta li n t r o d u c e dt h en e t w o r ki n f o r m a t i o nf l o w m o d e l ，w h e r ei t w a sa s s u m e dt h a ta l ln o d e sa r ec o n n e c t e di nt h e p o i n t - t o p o i n tm a n n e ra n dt h el i n k sa ren o i s e l e s s b a s e do nt h em o d e l ， a h l s w e d ee ta lg a v ead e e pi n v e s t i g a t i o no ft h en e t w o r kc a p a c i t yi s s u e a n di n t r o d u c e dt h ec o n c e p to f n e t w o r kc o d i n g i nt r a d i t i o n a ld a t a c o m m u n i c a t i o nn e t w o r k ，s w i t c hn o d e sf o r w a r dr e c e i v e d d a t aw i t h o u t p r o c e s s i n gt h e m w h e nn e t w o r kc o d i n gi su s e d ，as w i t c hn o d ee n c o d i n g r e c e i v e dd a t af l o wb e f o r es e n d i n gt h e m ，a n dt h e nt h er e c e i v e rn o d e s d e c o d i n gr e c e i v e dd a t aa n d r e c o v e rt h es o u r c ei n f o r m a t i o n i ti sp r o v e d t h a tn e t w o r kc o d i n gc a ni m p r o v en e t w o r kr e s o u r c eu t i l i z a t i o na n d g e n e r a l l y i ti s n e c e s s a r yt o u s en e t w o r kc o d i n gt oa c h i e v en e t w o r k c a p a c i t y n e t w o r kc o d i n gt h e o r yi sa ni m p o r t a n tb r e a k t h r o u g hi nt h ef i e l d o fn e t w o r ki n f o r m a t i o nt h e o r yi nr e c e n ty e a r s ，w h i c hr i s e sg r e a ti n t e r e s t o fr e s e a r c h e r sa r o u n dt h ew o r l d t h i sw o r kg i v e sa ni n v e s t i g a t i o no fs o m ea s p e c t so fn e t w o r kc o d i n g t h e o r y a f t e rac o n c i s ei n t r o d u c t i o nt on e t w o r kc o d i n g sb a c k g r o u n d ， c o n c e p t ，a n d b a s i ct h e o r y , o u rm a i nw o r ki sa sf o l l o w s s e c u r i t yo fn e t w o r kc o d i n g s e c u r i t yi sa ni m p o r t a n ta s p e c to fr e s e a r c h a n dd e s i g no fm o d e mn e t w o r k i nc h a p t e r3 ，w ef i r s ti n t r o d u c es o m e a u x i l i a r y m a t h e m a t i c a lr e s u l t sw h i c hs h o wt h e e q u i v a l e n c eb e t w e e n l i n e a r i n d e p e n d e n c e a n ds t a t i s t i c a l i n d e p e n d e n c e i nt h ec o n t e x to f n e t w o r kc o d i n g b a s e do nt h o s e r e s u l t s ，w eg i v e an e c e s s a r ya n d s u f f i c i e n tc o n d i t i o nf o rs e c u r i t yo fl i n e a rn e t w o r kc o d i n g t oa c h i e v e i n f o r m a t i o n - t h e o r e t i cs e c u r i t y , i ti sg e n e r a l l yn e c e s s a r yt oa d ds e c r e tk e y i n f o r m a t i o nt or a n d o m i z es o u r c ei n f o r m a t i o n w ep r o p o s eal o w e rb o u n d o fs e c r e tk e yi n f o r m a t i o nr a t ef o rn e t w o r kc o d i n gi nas p e c i a lm u l t i c a s t c o m m u n i c a t i o n w e a ks e c u r i t yo fn e t w o r kc o d i n g f o rs e c u r i t yo fs y s t e m ，i ti s n e c e s s a r y t oa d ds e c r e tk e yi n f o r m a t i o n ，w h i c hw i l ld e c r e a s et h e c o m m u n i c a t i o n e f f i c i e n c y o ft h e s y s t e m i n s o m e c a s e s ，t h e i n f o r m a t i o n t h e o r e t i c s e c u r i t y c a nb el o o s e n e dt oa c h i e v e h i g h e r t r a n s m i s s i o ne f f i c i e n c y i nc h a p t e r4 ，w eg i v et w od e f i n i t i o n so fw e a k s e c u r i t yc r i t e r i af o rn e t w o r kc o d i n ga n dg i v es o m e e x a m i n a t i o n 北京邮电大学博1 ：论文 英文摘要 n e t w o r kc o d i n ga n dn e t w o r kf l o wc o n t r 0 1 i nm o d e mn e t w o r k ，f l o w c o n t r o li sa ni n d i s p e n s a b l ec o m p o n e n tf o rr e l i a b i l i t ya n de 衢c i e n c y e s p e c i a l l y i n p a c k e tn e t w o r k ，f l o wc o n t r o l i sn e e d e dt oc o n t r o l c o n g e s t i o n ，i m p r o v et h r o u g h p u t ，r e d u c ed e l a y , a n de n s u r ef a i r n e s sa m o n g d i f f e r e n tu s e r s i nc h a p t e r5 ，w ed i s c u s sf l o wc o n t r o li s s u ef o rn e t w o r k c o d i n gb a s e dm u l t i c a s t f o l l o w i n gt h en e t w o r ku t i l i t ym a x i m i z a t i o n f r a m e w o r k ，w eg i v eah i e r a r c h i c a ld e c o m p o s i t i o nt ot h ep r i m a lp r o b l e m a n daf u n c t i o n a l i t ya l l o c a t i o nf o rn e t w o r kc o d i n gb a s e dm u l t i c a s t w i t h t h ed e c o m p o s i t i o na p p r o a c h ，ad i s t r i b u t e df l o wc o n t r o l a l g o r i t h mi s o b t a i n e d i nc h a p t e r6 ，t h ec o n t r i b u t i o no ft h i sw o r ki ss u m m a r i z e d t h i sw o r ki ss u p p o r t e db yn a t i o n a lb a s i cr e s e a r c hp r o g r a mo fc h i n a ( 9 7 3p r o g r a m ) 2 0 0 7 c b 3 10 6 0 4 & 2 0 0 9 c b 3 2 0 4 01a n dn a t i o n a l k e y s c i e n t i f i ca n d t e c h n o l o g i c a lp r o j e c to fc h i n a2 0 0 8 z x 0 3 0 0 3 0 0 5 k e y w o r d s ：n e t w o r kc o d i n g ，r a n d o ml i n e a rn e t w o r kc o d i n g ，n e t w o r k s e c u r i t y , n e t w o r kf l o w c o n t r o l ，n e t w o r ku t i l i t y m a x i m i z a t i o n ， o p t i m i z a t i o nd e c o m p o s i t i o n ，d u a ld e c o m p o s i t i o n ，n e t w o r ka r c h i t e c t u r e 一 1 北京邮电大学博十论文目录 目录 第l 章绪论 1 1 1 网络编码的背景1 1 2网络编码的概念。2 1 3 网络编码的现状2 1 4 本文的组织结构3 1 5 参考文献4 第2 章网络编码的基本概念6 2 1引言6 2 2网络编码的起源7 2 3 图论相关概念和术语7 2 4 网络编码和组播网络的容量9 2 5 线性网络编码1 0 2 5 1 线性网络编码的模型1 0 2 5 2 线性网络编码的编码方式1 2 2 5 3 线性网络编码的边界1 3 2 6随机网络编码13 2 7纠错网络编码15 2 8网络编码的实际问题1 7 2 9 d 、结18 2 1 0参考文献18 第3 章网络编码的安全性2 0 3 1引言2 0 3 2网络编码安全性的数学描述2 2 3 2 1 一般描述2 2 3 2 2 代数描述2 3 3 2 3 信息测度的代数描述2 8 3 2 4 线性编码安全性的充分必要条件2 9 3 3安全网络编码的一个必要条件2 9 3 3 1 一种特殊情况网络编码条件下的安全性2 9 3 3 2s h a n n o n 保密系统3 0 3 3 3s h a m i r 的秘密共享机制3l 3 3 4 安全网络编码的一个必要条件3 2 3 3 5 例子和分析：3 3 3 4 小结3 4 3 5参考文献3 5 第4 章网络编码的弱安全性3 6 4 1 引。言3 6 4 2一种弱安全性的定义3 6 4 3另一种弱安全性的定义4 l 4 4 _ 、结4 2 v 北京邮电火学博：l ：论文日录 4 5参考文献4 2 第5 章网络编码与网络流控4 4 5 1 引言4 4 5 2网络流控基本问题4 5 5 2 1 实现网络流控的意义4 5 5 2 2 网络流控的模型4 6 5 2 3 拥塞控制4 8 5 2 4 时延控制4 9 5 2 5 网络资源分配的公正性控制4 9 5 3 t c p 流控4 9 5 3 1t c p 的端到端( e n d t o e n d ) 流控4 9 5 3 2 接收端的流控5 0 5 3 3t c p 的拥塞控制5 0 5 4 基于优化的网络流控设计5 5 5 4 1 优化理论的数学准备5 5 5 4 2 基于优化理论流控的基本原理6 0 5 4 3 优化分解与网络架构6 6 5 4 4 用优化理论理解t c p 流控。7 0 5 5 基于网络编码的组播通信中的流控7 0 5 5 1 流控问题的数学描述7 0 5 5 2 阶梯分解方式7 3 5 5 3 其它阶梯分解方式7 7 5 6网络流控设计与实现的再思考7 9 5 6 1 网络研究的方法7 9 5 6 2 网络研究的微观和宏观视角。8 1 5 6 3 数学理论的工程化8 1 5 6 4 网络的构建原则8 3 5 6 5 网络复杂度的分配8 3 5 7 小结8 3 5 8参考文献8 3 第6 章总结和展望8 7 6 1本文工作的总结8 7 6 2本文不足及进一步工作8 7 符号对照表8 9 攻读学位期间获得的研究成果9 0 致谢9 1 v i 北京邮电大学博上论文第1 章绪论 第1 章绪论 1 1 网络编码的背景 源于s h a n n o n 理论 1 的信息论为通信的研究和发展提供了有力的理论工具。 当通信进入网络时代，研究者们一直希望有相应的适用于网络研究的理论工具。 但是网络信道的复杂性使网络信息论一直局限于几种特殊的网络信道，如双路信 道，广播信道，多接入信道等等。即便如此，其研究成果仍然是不完善的，如离 散无记忆广播信道的容量问题一直是未解的公开难题。 以i n t e r n e t 为代表的分层网络体系结构的成功应用，使人们可以从另外一个 角度来理解网络和理解通信。原来网络信息论都是对物理信道建模，即符号是受 信道随机噪声干扰的。在分层架构模型下，随着底层传输技术的提高，纠错机制 的完善，可以看作底层可以为上层提供透明的，无错误的数据传输。因此可以将 网络看作是由具备无错误传输能力的链路和节点构成，这大大降低了网络建模的 复杂度。 在这样的模型下，自然引发的一个问题就是：网络的传输极限是多少1 7 现 有的数据网络中，中间节点担当的职责是数据的转发，即将接收端的数据包转发 到另一输出端，而对数据包的内容不做处理。如果对中间节点的功能做更一般化 的推广，使输出端数据的内容是输入端数据的函数( 见图1 1 ) ，那么会不会提高 网络资源的利用率，甚至达到网络传输的极限? x ( o y ( 1 ) x ( 1 吣妒y 1 ) 转发 编码 图1 1 数据在中间节点处理方式示意图 a h l s w e d e 等【2 】提出的网络编码( n e t w o r kc o d i n g ) 研究了无噪声链路情况下， 网络的传输极限( 容量) 问题，并且研究了网络编码( 中间节点对接收到的数据 编码处理后发送) 方式对提高网络资源利用率的作用。网络编码理论是近年信息 论领域的重要成果，引发广泛了的研究兴趣。 1 当然，给定网络，只有在确定发送端和接收端时，所谓的传输极限才有意义。 北京邮i u 人学博：t ：论文第1 章绪论 1 2 网络编码的概念 网络编码的概念可以由如下图1 2 这个典型例子( 取自 2 】) 说明。 xy x 图1 2 网络编码的典型例子 在图中所示的网络中，各个链路上的容量为1b i t 。要实现节点s 到厂和g 的 组播通信。无论以何种方式( 转发或编码) ，j 到厂和g 的传输率都要受限于j 到 厂和g 的最大流( 分别是2b i t ) 。按照如图所示的编码方案，在链路( c ，e ) 上对数 据进行模2 加法，终端节点厂和g 通过反向运算，就都可以收到来自源端的符号 x 和y ，组播率达到了2b i t 。因此这种编码方式，可以充分利用网络资源。若采 用转发的方式，则不能达到此传输率。可见，采用网络编码可以获得比无编码方 式更高的网络资源利用率。 更为复杂的编码方式将在下一章介绍。 1 3 网络编码的现状 从a h l s w e d e 等 2 的工作开始，网络编码引发了的广泛的研究兴趣。主要有 两方面的研究： ( 1 ) 信息论方面的研究。这方面的研究着眼于： 网络容量边界的研究，主要是多源组播情况，如【3 】； 网络编码的构造方式，主要是线性编码，随机编码的构造算法，构造线 性网络编码的有限域的边界等，如【4 7 】，【9 】( 上边界) 和 1 0 】( 下边 界) 等； 2 北京邮电大学博士论文第1 章绪论 网络编码的复杂度，如 1 l 】； 安全网络编码，如 1 2 1 4 等； 纠错网络编码，女n 1 5 ，1 6 等； ( 2 ) 应用方面的研究。 网络编码与内容发布( c o n t e n td i s t r i b u t i o n ) 。文件发布是i n t e m e t 所支撑 的重要业务内容之一，p 2 p 的发布模式以其高吞吐量的优点而得到广泛 研究和应用。o k a n t s i d i s 等的一系列文献 1 7 1 9 研究了用随机网络编码实 现内容发布的问题，并将研究成果应用于m i c r o s o f t 公司a v a l a n c h e 文件 发布系统的实现。与流行的b i t t o r r e n t 协议不同，参与文件发布的节点， 对所收的数据块要进行随机编码后再向网络中其它节点发布。【1 7 】中通过 仿真表明采用网络编码文件发布的性能( 以下载时间度量) 比未编码的 情况要提高2 3 倍。 网络编码与分布式存储。独立磁盘冗余阵列( r a ) 的管理采用的是分 布式的存储管理技术，如何提高信息的提取效率，降低读写操作通信开 销，是分布式存储所面临的主要问题。d i m a k i s 【2 0 等对采用随机线性网 络编码机制的分布式存储做了研究，并对其与传统的擦除码( e r a s u r e c o d e s ) ，喷泉码( f o u n t a i nc o d e s ) 等作了比较。较新的更为广泛的关于 网络编码与分布式存储的研究参见 2 1 】。 网络编码同样在无线网络的领域有广泛的应用，如m e s h 网络，传感器网 络和a dh o c 网络等因文献 2 2 】已有综述，这里不再做介绍。 1 4 本文的组织结构 全文组织如下： 第二章介绍网络编码相关的基础知识； 第三章研究网络编码的安全性。首先给出了基于网络编码组播安全性的一般 数学描述。然后给出了线性网络编码条件下安全性的代数描述，将信息论问 题转化为代数问题，并用代数重新表述了网络编码安全性的充要条件。在本 章单独开辟一节讨论了要实现s h a n n o n 意义安全性，网络编码所需密钥信息 率的必要条件。 第四章在前一章的基础上，初步讨论了弱安全性的若干问题。 第五章讨论基于网络编码组播通信的流控问题。为了方便后面的讨论，首先 介绍了网络流控的相关问题，特别是t c p 的拥塞控制，这些是流控的传统设 3 北京邮电大学博1 j 论文第1 章绪论 计方式，其视角是“微观的”，即关注于数据包一级的行为。然后介绍了基 于“网络效用最大化”的流控设计方法，其视角是“宏观的 ，即关注数据 “流一级的行为。而后用“网络效用最大化”和优化分解的方法，研究了 基于网络编码组播通信的流控设计问题。本章的最后讨论了网络研究的若干 一 问题。 第六章总结不足及展望未来工作。 1 5 参考文献 1 2 1 3 1 4 1 5 s h a n n o n ，c e am a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n t h eb e l ls y s t e m t e c h n i c a lj o u r n a l 19 4 8 2 7 a h l s w e d e 。r ，e ta 1 ，n e t w o 庸i n f o r m a t i o nf l o w i e e et r a n s a c t i o n so n i n f o r m a t i o nt h e o r y , 2 0 0 0 4 6 ( 4 ) ：p 1 2 0 4 1 2 1 6 r w ：y e u n g , s - yr l i ，n i n gc a ia n dz h e nz h a n g ，n e t w o 船c o d i n gt h e o r y ( f o u n d a t i o n sa n dt r e n d s 纽，切c o m m u n i c a t i o n sa n di n f o r m a t i o nt h e o r y ) 2 0 0 6 ：n o wp u b l i s h e r si n e h o ，t ，e ta 1 砀pb e n e f i t so fc o d i n go v e rr o u t i n g 觑ar a n d o m i z e ds e t t i n g i n i e e ei n t e r n a t i o n a ls y m p o s i u mo ni n f o r m a t i o nt h e o r y - p r o c e e d i n g s 2 0 0 3 y o k o h a m a , j a p a n h o ，t ，e ta 1 ，ar a n d o ml i n e a rn e t w o 庸c o d i n ga p p r o a c ht om u l t i c a s t i e e e t r a n s a c t i o n so ni n f o r m a t i o nt h e o r y , 2 0 0 6 5 2 ( 1 0 ) ：p 4 4 1 3 4 4 3 0 k o e t t e r , r a n dm m e d a r d ，a na l g e b r a i ca p p r o a c h t on e t w o r kc o d i n g i e e e a c mt r a n s a c t i o n so nn e t w o r k i n g ，2 0 0 3 1 l ( 5 ) ：p 7 8 2 7 9 5 “，s 一yr ，r w ：y e u n g , a n dn c m ，l i n e a rn e t w o r kc o d i n g i e e e t r a n s a c t i o n so ni n f o r m a t i o nt h e o r y , 2 0 0 3 4 9 ( 2 ) ：p 3 71 3 81 k o e t t e r , r a n dm m e d a r d ，a na l g e b r a i ca p p r o a c h t on e t w o r kc o d i n g i e e e a c mt r a n s a c t i o n so nn e t w o r k i n g , 2 0 0 3 1 l ( 5 ) ：p 7 8 2 j a g g i ，s ，e ta 1 ，p o l y n o m i a lt i m ea l g o r i t h m sf o rm u l t i c a s tn e t w o r kc o d e c o n s t r u c t i o n i e e et r a n s a c t i o n so ni n f o r m a t i o nt h e o r y , 2 0 0 5 5 1 ( 6 ) ：p 19 7 3 f e d e r , m ，d r o n ，a n da t a v o r y b o u n d so nl i n e a rc o d e sf o rn e t w o r k m u l t i c a s t i ne l e c t r o n i cc o l l o q u i u mo nc o m p u t a t i o n a lc o m p l e x i t y 2 0 0 3 l e h m a n ，a r ，l e h m a n ，e ，c o m p l e x i t yc l a s s i f i c a t i o no f n e t w o r ki n f o r m a t i o n f 1 0 wp r o b l e m s i n4 1 s ta n n u a la l l e r t o nc o n f e r e n c eo nc o m m u n i c a t i o n c o n t r o la n dc o m p u t i n g 2 0 0 3 n c a i ，r w y e u n g ，s e c u r en e t w o 成c o d i n g , i nz s ! ，z2 0 0 2 k b h a t t a d ，k r n a r a y a n a n ，w e a k l ys e c u r en e t w o r kc o d i n g , i nn e t c o d2 0 0 5 2 0 0 5 j f e l d m a n ，t m a l k i n ，c s t e i n ，r a s e r v e d i o ，o nt h ec a p a c i t yd 厂s e c u r e n e t w o 麻 c o d i n g , i np m c 4 2 n da n n u a la l l e r t o n c o n f e r e n c e o n c o m m u n i c a t i o n , c o n t r o l , a n dc o m p u t i n g 2 0 0 4 y e u n g ，r w a n dn c a i ，n e t w o 成e r r o rc o r r e c t i o n ，p a r t b a s i c c o n c e p t sa n d u p p e rb o u n d s c o m m u n i c a t i o n si ni n f o r m a t i o na n ds y s t e m s ，2 0 0 6 6 ( 1 ) ：p 4 支 & z & 殳 m n 一 北京邮电大学博士论文 第1 章绪论 1 6 1 7 1 8 1 9 2 0 2 1 2 2 1 9 - 3 6 c 矗。n a n dr ，y e u n g , n e t w o r ke r r o rc o r r e c t i o n p n r ti i ：l o w e rb o u n d s c o m m u n i c a t i o n si ni n f o r m a t i o na n ds y s t e m s ，2 0 0 6 6 ( 1 ) ：p 3 7 - 5 4 g k a n t s i d i s c a n dp r r o d r i g u e z n e t w o r kc o d i n gf o rl a r g e $ c a z pc o n t e n t d i s t r i b u t i o n 2 0 0 5 m i a m i ，f l ，u n i t e ds t a t e s ：i n s t i t u t eo fe l e c t r i c a la n d e l e c t r o n i c se n g i n e e r si n e ，p i s c a t a w a y , n j0 8 8 5 5 1 3 3 1 ，u n i t e ds t a t e s g k a n t s i d i s ，c ，j m i l l e r , a n dp r o d r i g u e z c o m p r e h e n s i v ev i e wo fal i v e n e t w o r kc o d i n gp 2 ps y s t e m 2 0 0 6 r i od ej a n e r i r o 。b r a z i l ：a s s o c i a t i o nf o r c o m p u t i n gm a c h i n e r y , n e wy o r k , n y 10 0 3 6 5 7 0 1 u n i t e ds t a t e s g k a n t s i d i s ，c a n dp r o d r i g u e z c o o p e r a t i v es e c u r i t yf o rn e t w o r kc o d i n g f t l ed i s t r i b u t i o n i ni n f o c o m2 0 0 6 2 0 0 6 d i m a k i s ，a g ，vp r a b h a k a r a n , a n dk r a m c h a n d r a n , d e c e n t r a l i z e de r a s u r e c o d e s 届厂d i s t r i b u t e dn e t w o r k e ds t o r a g e i e e et r a n s a c t i o n so ni n f o r m a t i o n t h e o r y , 2 0 0 6 5 2 ( 6 ) ：p 2 8 0 9 d i m