基于网络编码的应用层组波路由优化方案研究毕业设计(编辑修改稿)

基于网络编码的应用层组波路由优化方案研究毕业设计(编辑修改稿)内容摘要：

衡以及数据分发路由设计等问题都是目前P2P内容分发所面临的难题。 而在 Peer之间传输经过网络编码的数据块能够有效解决甚至避免这些问题。 2)应用层组播。 P2P技术与覆盖网络 (overlay work)的发展，将组播功能从 P层扩展到了应用层，在 P2P应用层组播系统中， Peer节点对流经的数据除了进行存储转发外，如果 还可以进行额外的网络编码处理，将可以在很大程度上改善应用层组播性能，提高覆盖网络数据吞吐能力。 3)无线传感器网络数据获取。 在无线传感器网络中，传感器节点的数据存储能力十分有限，如何将这些节点采集的信息在最小代价、最小能耗、最大容量等约束下发送给存储节点是当前网络编 8 码在无线通信领域的一个新课题。 4)网络管理。 对于链路被截断等物理故障，传统的解决办法是启用备份链路进行重新路由，而对于采用网络编码的节点，改变编码规则就可以改变其传递给其它节点的信息内容，这同样起到了重新路由的作用，而且这种网络管理 方式的开销非 常小。 5)信息安全。 攻击者恶意篡改网络上传输的数据内容将直接影响接收端的信息接收，这是目前计算机通信网的一个潜在隐患。 采用随机网络编码技术，攻击者对接收端收到的其它编码数据无法进行预知和控制，数据篡改的影响可以降至最低。 9 第三章 一种基于网络编码的应用层组播路由算法 第一节 应用层组播 一、应用层组播的提出 互联网上的大规模媒体存储与发布普遍是基于传统的客户机／服务器 (C／ S)系统架构，这种集中式的分发模型容易造成中央服务器的过量负载，直接导致网络吞吐量的下降，并且一旦中央服务器出现故障将直接导致整个传 输体系瘫痪。 随着视频点播、网络电视、远程教育等多媒体服务飞速发展，中央服务器的带宽瓶颈问题日益凸显，以致集中式的分发模型逐步向基于 P2P覆盖网络 (overlay work)架构的分布式结构过渡。 IP层组播是面向组通信应用的，被认为是大规模数据分发的最佳方法。 然而口组播增加了网络层的复杂性，而且需要对现有网络的底层设备进行巨大改动，因此至今口层组播仍然无法广泛部署。 叠加网 (Overlay Networks)是一个位于一个或多个己知网络上的独立的虚拟网络。 它的主要优点在于它的架构，它不需要改变底层网络的 结构，可以快速部署所需的网络功能。 如果在叠加网的基础上实现组播，可以把组播实现提高到应用层。 端系统实现组播业务的思想是将组播作为一种叠加的业务，实现为应用层的服务，由此构成了应用层组播 (application layer multicast) 应用层组播是在叠加在 m层之上的用于实现组播业务逻辑的功能性网络，应用层组播网络中的节点是由组播中的成员主机构成的，并由它们完成数据路由、复制和转发功能。 因为不再依靠网络层路由器来实现，所以不需要任何网络底层架构的改变，只需改变端系统，便于实现和推广。 图 3． 1对 m组播 和应用层组播的数据传输方式进行了比较： 10 图 3． 1 m组播和应用层组播的数据传输方式比较 图 3． 1中假设 A、 B、 C、 D为四个端系统主机， R1， R2为路由器，箭头方向代表数据包的发送方向。 图 3． 1(a)为 IP组播， A为网络中的源节点，数据包从 A发到 R1，再由 R1转发给 B和 R2， R2再将收到的数据包转发给 C和 D。 图 3． 1(b)为应用层组播， A发送两份相同的数据包分别给 B和 C，再由 C复制一份给 D。 从图 3． 1(b)可以看到应用层组播有以下一些优点： 1．所有数据包都是通过单播传输的，无需路由器的支持，节点只需安 装应用层软件即可，操作方便、易于广泛部署； ，而节点仅需要保存该组少量其它邻近成员的信息，可扩展性好； 3．利用单播，可以有效地采取适合流媒体应用特点的错误恢复、流量控制、拥塞控制等策略，提供端到端的服务质量保证； 4．不但能跨越空间维，还能跨越时间维进行数据传输，可牺牲同步性能来获得更好的服务质量保证； 5．地址可采用层次结构，可有效地扩大地址空间。 但从图 3． 1中可以看出应用层组播存在的一些固有问题，如效率不高，多条覆盖网络上的逻辑链路可能经过物理网络的同一链路；延迟大，两 个节点之间的通讯可能要通过其它节点：同步性能差，所有节点之间很难同步接收数据；可能跨越多个节点，丢包概率增大。 应用层组播的效率比 P组播的效率要低，因为不可避免的会有组播路径重复的经过同一条底层链路，也就必然带来冗余的流量，例如在图 3． 1(b)中 (A， R1)和 (R2， C)这两条链路上有两个相同的数据包重复经过同一条底层链路，而图3． 1(a)的口组播则只有一次。 另外，两个端系统之间的通信，可能要通过中间 11 其他端系统的转发来实现，这也不可避免的造成两个通信节点之间延时的增加。 二 应用层组播路由协议 应用层组播协议 通常都按照两个拓扑结构组织组成员，一个是控制拓扑，一个是数据拓扑，控制拓扑的组成员周期性地交互刷新消息以相互标识身份并从节点失效中恢复。 而数据拓扑通常是控制拓扑的子集，它用于标识组播转发时使用的数据路径。 数据拓扑作为应用层组播协议的重要组成部分，即组播中文件数据的如何路由是本文讨论的重点。 一般来说，组播组用于标识组播转发时用的数据路径通常是一棵组播树。 其中在组播中最基本两种数据转发方式是：建立最短路径树和最小生成树，常见的路由算法为： Bellman— Ford最短路径树算法、 Dijstra 最短路径树算法和 Prim最小生成树算法。 最短路径树是从源节点到所有接收节点的每条路径上链路权值之和最小的组播树。 如果所有的链路的权值都表 1，则为最小跳树。 如果权值代表链路延时，则为最小时延树。 最小生成树是指覆盖所有组成员且权值最小的组播树。 此外，还有基于 Steiner树的问题致力于使组播树的总代价最小，这已经证明了是图论中一个 NP． plete问题。 如果组播树包含了树中所有节点， Stoner树问题转化为最小生成树问题。 一般通过启发式算法求解，典型的启发式算法有：MST、 RS、 KMB[31， 321。 Steiner树问题可 以扩展到包括其它的链路约束。 例如延时、延时抖动或者它们的组合。 通常这些问题是 NP． Complete的，所以也需要采用启发式算法解决。 第二节 基于网络编码的应用层组播路由算法 在日常生活中，我们经常要使用到比较大规模的通信网络，我们都希望通信网络能为我们提供更为安全、快速的网络服务。 于是我们提出了实现在已有通信网络中达到最大数据流的目标。 由前一章可知，网络编码可以实现网络的最大流传输。 网络信息理论的研究指出：在组播通信中，每个接收节点可以以网络拓扑中信源发送点与信宿接收点之间的最大流容量进行信息传递。 然而， 从信源到不同信宿之间的最大流经过的传输路径可能在网络拓扑的链路上形成交叉共享链 12 路，因此采用传统的存储转发模式即 P组播的方式，无法达到最大流最小割的理论上限。 网络编码，作为一种协同工作的理念，将原先分立于物理层和网络层的两个核心概念 —— 编码和路由有机地融为一体，通过在中间节点中进行传递信息的编码组合运算，建立起一种异于传统存储转发的全新网络信息传输模式。 应用层组播是以端系统为基础的逻辑覆盖网 (overlay work)，不同与以往 m层组播中的路由器节点，端系统可以提供更为强大的功能，如能够对数据进行编 码组合运算，这为网络编码在覆盖网络上的应用提供了技术支撑。 本节的主要内容就是建立一种基于网络编码的启发式应用层组播路由算法，目的在于利用网络编码技术在分布式网络中建立数据分发拓扑使得网络传输容量趋于组播容量上限。 在分布式拓扑中运用随机线性网络编码技术，即中间节点对发往不同目的节点的组播数据进行编码组合后再转发，以避开数据流对链路的竞争冲突，提高组播通信的吞吐量。 一、冗余路径 考虑到网络编码在提高网络的吞吐量方面的优点，为了进一步改善应用层组播的性能，从而我们引入了网络编码技术。 但是网络编码不是万能的，不 是所有的网络组播拓扑都能使用。 应用层组播要结合网络编码技术，在路由选择方面必须满足两个条件： (1)网络中存在冗余的路径； (2)具有相同目的节点的路径之间不能存在共用的路径。 13 图 不相交的冗余路径 (对于 Tl而言， S． U1． T1和 SU2． U3U4T1分别是 S． T1的两路不相交路径 ) 图 3． 2我们可以看到对于网络中的目的节点 T1存在两条不相交的路径通向源节点 S，因此目的节点能同时收到多路独立数据流。 所谓不相交路径是指对同～目的节点而言的不同路径之间不存在共用的链路。 不相交性保证了对于发送至同一个 目的节点的不同路径的数据之间不会存在时间上的竞争，它们之间是线性无关的。 此时，对于不同目的节点的路径之间必然存在链路的公用问题而产生的瓶颈链路，网络编码的引入可以很好的解决瓶颈链路的问题。 图 3． 2中，链路 m3，U4)就是目的节点 T1和 T2之间的瓶颈链路，在节点 U3进行网络编码就可以实现网络的最大流传输，达到网络的最大容量 2。 (假设定义网络中链路的带宽均为 l，由最大流最小割定理可以算的图 3． 2所示网络结构的最大流为 2)。 14 这里，多条不相交的数据传输路径的存在使得以往组播。