网络编码只是概述ppt课件

1、School of Computer and Communication Degui XiaoDegui Xiao CN 1网络编码知识概述网络编码知识概述报告人：后学知报告人：后学知 导师：张大方导师：张大方 何施茗何施茗School of Computer and Communication Degui XiaoDegui Xiao大纲大纲 一一 研讨背景研讨背景 二二 问题论述问题论述 三三 我的任务我的任务 四四 详细算法详细算法 五五 仿真结果仿真结果 六六 参考文献参考文献 CN 2School of Computer and Communication Degui XiaoDeg

2、ui Xiao研讨背景研讨背景 近年来，随着对无线网络的逐渐普及，对于无线网络的近年来，随着对无线网络的逐渐普及，对于无线网络的性能的研讨也越来越频繁。性能的研讨也越来越频繁。 CN 3School of Computer and Communication Degui XiaoDegui Xiao研讨背景研讨背景 网络编码网络编码(Network Coding) 是进入是进入21 世纪后通讯领域的一项艰苦世纪后通讯领域的一项艰苦突破突破,它交融了编码和路由的概念它交融了编码和路由的概念,经过允许对来自不同链路的信息经过允许对来自不同链路的信息进展编码组合进展编码组合,使得网络节点既实现路由功

3、能又实现编码功能。在使得网络节点既实现路由功能又实现编码功能。在这种全新的体系构造下这种全新的体系构造下,网络性能可以到达最大流传输的实际极限网络性能可以到达最大流传输的实际极限。 下面是几种很经典的网络编码算法下面是几种很经典的网络编码算法 CN 4School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 copesc CN 5School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 COPE主要包括主要包括3种主要技术种主要技术 (a) Opp

4、ortunistic Listening 1 无线网络是广播信道无线网络是广播信道 2 每个节点都有时机偷听到包并在一个有限的时间内每个节点都有时机偷听到包并在一个有限的时间内进展保管进展保管 3 保管包后，每个节点广播接纳报告给它邻居节点保管包后，每个节点广播接纳报告给它邻居节点 CN 6School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 7 CN 7 (b) Opportunistic CodingSchool of Computer and Communication Degui XiaoDegui X

5、iao详细算法详细算法 ANCAnalog Network Coding CN 8School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 9 (b) Opportunistic Coding 多重单播流在一同编码，但是解码时会分成不同流多重单播流在一同编码，但是解码时会分成不同流 算法保证一切编码得包的下一跳节点可以解码相对的原算法保证一切编码得包的下一跳节点可以解码相对的原始包始包 设有设有n个包个包p1, ., pn到到n个下一跳个下一跳r1, ., rn，一个节点，一个节点可以可以XORn个包前提是每个下一

6、跳个包前提是每个下一跳ri有有n 1 个包个包pj 且且 j = iSchool of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 10 (c) Learning Neighbor State 由于网络拥塞，接纳报告能够丧失或者延时，当接纳报由于网络拥塞，接纳报告能够丧失或者延时，当接纳报告到达时也许节点曾经做出了非最正确选择告到达时也许节点曾经做出了非最正确选择 我们改动无线路由协议来采用猜测的方法来估计对方节我们改动无线路由协议来采用猜测的方法来估计对方节点有什么包点有什么包 当节点计算错误而无法解码包时那么相关的未

7、编码包重当节点计算错误而无法解码包时那么相关的未编码包重新发送。新发送。School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 11 Coding Gain定义定义 不用不用COPE传送的次数与用传送的次数与用COPE传送的次数的比值传送的次数的比值。实际上最大值为实际上最大值为2实践由于时机编码，传输丧失，过大的头使实践值小于实践由于时机编码，传输丧失，过大的头使实践值小于2School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN

8、12 CN 12School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 13 CN 13 Coding+MAC Gain 带宽平均分配，因此瓶颈链路的包被丢弃。带宽平均分配，因此瓶颈链路的包被丢弃。 Coding+MAC的最大值无限。的最大值无限。School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 14 Packet Coding Algorithm (1) 我们遵照包从不延时的实际，在节点队列头的包检我们遵照包从不延时的实际，

9、在节点队列头的包检测能否有可以异或的包有那么异或，没有也不等待这样测能否有可以异或的包有那么异或，没有也不等待这样的包到来。的包到来。 (2) COPE优先选择异或长度相近的包优先选择异或长度相近的包 (3) COPE不会把具有一样下一跳的包编码在一同，因不会把具有一样下一跳的包编码在一同，因此我们只需思索具有不同下一跳的包。此我们只需思索具有不同下一跳的包。School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 15 保证找到适宜的包关键在于维持一大一小两个虚拟队保证找到适宜的包关键在于维持一大一小两个虚拟队列

10、。从虚拟队列的头开场找以免乱序列。从虚拟队列的头开场找以免乱序 乱序问题需求减少。主要有两个缘由乱序问题需求减少。主要有两个缘由 1 我们编码要找适宜的包。这个影响其实很小。我们编码要找适宜的包。这个影响其实很小。 2包丧失导致重传，这个为主要缘由。包丧失导致重传，这个为主要缘由。 我们处理这个问题在接纳端。我们处理这个问题在接纳端。 最后要保证邻居节点可以解码出他的未编码的包。最后要保证邻居节点可以解码出他的未编码的包。School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 16 每个节点维持以下的数据构造每个

11、节点维持以下的数据构造 1 每个节点输出队列按照先入先出转发数据。每个节点输出队列按照先入先出转发数据。 2 对于每个邻居，每个节点维持两个虚拟电路，一个为对于每个邻居，每个节点维持两个虚拟电路，一个为大包，一个为小包大包，一个为小包 3每个节点维持一个哈希表，阐明每个节点拥有包的能每个节点维持一个哈希表，阐明每个节点拥有包的能够性。够性。School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 17 Packet Decoding 每个每个节点维持一个包池，用来保管每个未编码包的每个每个节点维持一个包池，用来保管

12、每个未编码包的复制件。复制件。 当一个节点收到一个由当一个节点收到一个由N各未编码的包组成的编码包，各未编码的包组成的编码包，然后一个一个检查然后一个一个检查ID，然后再包池了检查相应的包。，然后再包池了检查相应的包。 最后进展异或运算得到原始包。最后进展异或运算得到原始包。School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 18 Pseudo-broadcast COPE不用不用broadcast方式由于可靠性差并且短少回方式由于可靠性差并且短少回退机制退机制 我们选用我们选用pseudo-broadcas

13、t来处理这个问题，它借来处理这个问题，它借用了单播的可靠性和回退机制。用了单播的可靠性和回退机制。 这个方法根据目的节点这个方法根据目的节点MAC地址和地址和XOR头来鉴定包头来鉴定包的下一跳能否是本节点，假设不是并且没收到源节的下一跳能否是本节点，假设不是并且没收到源节点会重发直至确认或者超时点会重发直至确认或者超时School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 19 Hop-by-hop ACKs and Retransmissions (a) Why hop-by-hop acks 1包有几个下一跳

14、在其中一些下一跳能够丧失包有几个下一跳在其中一些下一跳能够丧失 2 COPE没有足够的信息来获取下一跳的信息来没有足够的信息来获取下一跳的信息来解码解码School of Computer and Communication Degui XiaoDegui Xiao详细算法详细算法 CN 20 (b) Asynchronous Acks and Retransmissions 同步确认对于编码得包来说效率低下同步确认对于编码得包来说效率低下 COPE对于编码包采用异步确认。一旦确认丧失进展重对于编码包采用异步确认。一旦确认丧失进展重传。传。School of Computer and Comm

15、unication Degui XiaoDegui Xiao详细算法详细算法 CN 21 Preventing TCP Packet Reordering 异步确认会导致包乱序，使被异步确认会导致包乱序，使被TCP以为是拥塞的信号。以为是拥塞的信号。 COPE采用一个顺序代理来处理乱序问题采用一个顺序代理来处理乱序问题 代理检查序号假设是延续的那么让包进入传输层，假设代理检查序号假设是延续的那么让包进入传输层，假设序号有裂痕那么保管这个区域直到重发的包把序号填满序号有裂痕那么保管这个区域直到重发的包把序号填满，直到延时，直到延时School of Computer and Communicat

16、ion Degui XiaoDegui Xiao详细算法详细算法 CN 22 CN 22Packet FormatSchool of Computer and Communication Degui XiaoDegui Xiao CN 23 CN 23Control FlowSchool of Computer and Communication Degui XiaoDegui Xiao CN 24详细算法详细算法 ZigZag Decoding24APAliceBobPa 1 3Pa 1 3Pb2 4Pb42121- 21st collision2nd collision0Can recon

17、struct both packets Pa and Pb!School of Computer and Communication Degui XiaoDegui Xiao CN 25Collision!AliceBobSchool of Computer and Communication Degui XiaoDegui Xiao CN 26AliceBobMore Collisions!RetransmissionsCant get any useful connectionsSchool of Computer and Communication Degui XiaoDegui Xia

18、o CN 27 发生碰撞时，发生碰撞时，ZIGZAG能到达鱼不碰撞时一样的性能，而没能到达鱼不碰撞时一样的性能，而没有碰撞时有碰撞时ZIGZAG表现像经典的表现像经典的802.11的接纳者。的接纳者。802.111协议中用户在没收到确认或超时的前提下重新发送数据包协议中用户在没收到确认或超时的前提下重新发送数据包很能够再次碰撞。很能够再次碰撞。2用户每次发送阅历个随机时间，因此碰撞在开场于一个随用户每次发送阅历个随机时间，因此碰撞在开场于一个随机的机的bit位。位。School of Computer and Communication Degui XiaoDegui Xiao CN 28Sc

19、hool of Computer and Communication Degui XiaoDegui Xiao CN 2912PaPbPaPbSchool of Computer and Communication Degui XiaoDegui Xiao CN 301211 2 1School of Computer and Communication Degui XiaoDegui Xiao CN 31212111 2 School of Computer and Communication Degui XiaoDegui Xiao CN 322122131 2 School of Com

20、puter and Communication Degui XiaoDegui Xiao CN 3321241331 2 School of Computer and Communication Degui XiaoDegui Xiao CN 34212441351 2 School of Computer and Communication Degui XiaoDegui Xiao CN 352161355241 2 School of Computer and Communication Degui XiaoDegui Xiao CN 3621661243571 2 School of C

21、omputer and Communication Degui XiaoDegui Xiao CN 3721681243577School of Computer and Communication Degui XiaoDegui Xiao CN 38 ZIGZAG用一种新颖的方法处理了干涉问题。用一种新颖的方法处理了干涉问题。School of Computer and Communication Degui XiaoDegui Xiao CN 39但是但是zigzag却可以在最正确发送速率下发送包。却可以在最正确发送速率下发送包。经过实验证明采用经过实验证明采用ZIGZAG的算法，在部分或

22、全部发生隐藏的算法，在部分或全部发生隐藏终端的情况下丢包率从终端的情况下丢包率从72.6%下降到下降到0.7%。School of Computer and Communication Degui XiaoDegui Xiao CN 40School of Computer and Communication Degui XiaoDegui Xiao CN 41School of Computer and Communication Degui XiaoDegui Xiao CN 421 如何发现发生碰撞？如何发现发生碰撞？TimeAP received signalPackets start with known preambleCorrelateAP correlates known preamble with signalCorrelationTimePreamble Correlation Detect collision and the value of Works despite interference because correlation with an independent sign