【作者】 陶少国；

【导师】 杨宗凯；

【作者基本信息】 华中科技大学 ， 信息与通信工程， 2008， 博士

【摘要】 大规模的数据分发有着广泛的应用背景。在现有网络条件下,如何更有效利用网络资源并实现高质量的数据分发,已成为网络信息流研究领域的重要课题之一。近些年来提出的网络编码为实现这一目标提供了新的解决方案。网络编码的核心思想是允许通信网络中的节点对传输的信息进行处理和操作(如有限域中的运算等),而不再限于存储和转发。网络编码革命性地拓展了现有的基于存储和转发的数据分发模式,被认为是进入21世纪后信息处理和信息传输理论研究领域上的重大突破,具有重要的理论价值和广泛的应用前景。国内外许多知名大学、科研机构和公司等都积极投入对网络编码的研究,并取得了一些重要的研究成果。已经证明,网络编码能显著改善数据分发系统的性能,如提升网络吞吐量,节约传输带宽和均衡网络负载等。然而,与基于存储和转发操作的路由传输机制相比,网络编码系统中的节点需要执行频繁的编码和译码操作,这必将消耗额外的计算资源(如I/O和CPU等),从而增加了在实际网络中部署和实施网络编码的成本和代价。因此,对面向数据分发的网络编码传输过程进行优化,减少网络编码操作所需的额外计算消耗,以此来实现低代价网络编码数据分发,对进一步提升数据分发系统的性能并促进网络编码的大规模应用有重要的指导意义。本文以降低网络编码操作所需的额外计算消耗为出发点,研究能实现更高效的基于网络编码的数据分发模式。研究主要从以下几个方面展开:(1)基于信息流向量的网络编码传输模型的研究;(2)基于关键链路的低代价网络编码实现算法的研究;(3)基于分簇网络编码的传输策略与相关算法的研究。本文的研究工作得到了国家自然科学基金“无线Mesh网络流媒体分发研究”(No. 60773193),华为公司高科技基金“面向P2P的网络编码研究”(No. HW200606301254),湖北省智能互联网技术重点实验室开放基金(No. HSIT-200605)和华中科技大学电信系基础理论研究基金(2008)的资助。本文的研究成果包含以下几个方面:1)基于信息流向量的网络编码传输模型:将数据分发系统中传输的信息建模为网络信息流,提出了一种具有线性复杂性的描述网络信息流的方法:信息流向量。结合信息流向量,分析了网络编码系统中存在的信息流向量约束,提出了反映网络编码操作数的指标:代价函数,并构建了最小代价的网络编码传输模型。该模型将网络编码数据分发系统的优化问题转化为数学规划问题,因此能够利用数学规划的相关理论求解并确定出最小代价的网络编码数据分发模式。此外,为考虑一些特殊网络中网络编码操作执行效率的问题,提出了一种基于效用折中的网络编码传输模型。该模型对在实际网络中,构建具有最小代价的,基于网络编码的数据分发系统具有重要的理论指导意义。2)低代价网络编码实现算法的研究:通过分析网络编码的本质特性,将网络编码区分于传统的基于存储和转发的数据分发模式并显著提升数据分发系统性能的根本原因归结为构建的传输路径上存在“关键”链路。为实现给定网络中数据分发系统的理论吞吐量,关键链路必须传输编码信息。编码信息能够在信宿节点通过合适的译码操作加以“区分”。因此,在构建网络编码数据分发系统的传输路径时,如果能够保证形成较少的关键链路,就能在一定程度上减少系统中网络编码操作的执行次数,从而降低网络编码所需的额外计算消耗,进而降低网络编码的实施成本和代价,并构建低代价的基于网络编码的数据分发模式。基于该思想,提出了一种基于关键链路的低代价网络编码实现算法,并对该算法进行了分布式实现。3)基于分簇网络编码的传输策略与相关算法研究。虽然网络编码源于IP组播,并被证明能提升组播网络中的数据分发性能,但由于技术和非技术上的挑战,IP组播并没有在现有互联网上得到大规模的部署和应用。作为一种替代的解决方案,基于对等网的协作式数据分发模型及其系统近年来得到了长足的发展,并被广泛应用。网络编码与基于对等网的协作式数据分发模型相结合,是网络编码应用研究领域的热点。然而,由于网络编码固有的特点,即节点需要执行编码和译码操作,一些学者对网络编码究竟能在多大程度上提升协作式数据分发系统的性能表示怀疑。以此为研究背景,以降低节点执行编码和译码操作的复杂性为目标,提出了分簇网络编码的思想。基于分簇网络编码,提出了随机性选择和相关性检测等机制来保证在降低网络编码复杂性的前提下,进一步提升数据分发系统的性能。更多还原

【Abstract】 Many applications based on Internet need to use the large-scale data delivery mechanism, such as IP multicast and P2P cooperative content distribution, to deliver information to a large number of users. How to obtain the better delivery performance with the limited network resources has become a“hot spot”in the research community of network information flow. To achieve the goal, network coding, as one of the most important breakthroughs on the theory of information processing and transmission, was proposed in recent years. The main principle behind network coding is that the relay (intermediate) nodes in the communication network make encoding and decoding operations to the data bits. Network coding generalizes the traditional data delivery mechanism where the data bits can only be stored and forwarded. With network coding,the communication network can achieve better transmission performance, such as higher network throughput and lower bandwidth consumption etc. Due to its significant potentials, network coding has received much concern in both the research and industrial community. Lots of famous universities and research agencies have put much attention on the research of network coding and finished some important works.It can be proved from the theoretical aspects that network coding can enhance the performance of a given data network to a large extent. However, compared with the traditional data delivery mechanism based on storing and forwarding, the nodes in network coding system need to perform encoding and decoding operations such that the system based on network coding takes additional computational overheads (such as I/O and CPU consumption), which will bring high cost (computational and non-computational) to deploy network coding in real data networks. Hence, it is better to find out an optimal network coding scheme in which the additional computational overheads caused by network coding is as lower as possible. To address this issue, this thesis investigates the optimization technologies of network coding from the theoretical and practical interests respectively. The content of this thesis includes three aspects: 1) Information flow vector-based optimal network coding model; 2) Key links-based low-cost network coding algorithm and its distributed implementation; 3) Clustered network coding-based cooperative content distribution scheme and algorithms.The works in this thesis have been supported by the National Science Foundation of China“Wireless Mesh Network-based Stream Media Distribution”(No. 60773193), High-Tech Foundation of Huawei Corporation (China)“Peer to Peer Oriented Network Coding”(No.YJCB2006049RE), the Foundation of Hubei Provincial Key Laboratory of Smart Internet Technology (HSIT-200605) and the Research Foundation of Department of Electronics and Information Engineering, Huazhong University of Science and Technology (2008).The contributions of this thesis contain:1. Information flow vector-base optimal network coding model. By modeling the information transmitted in the data delivery network as network information flow, we present a simple but effective approach to describe the information flow on each link in the data delivery system, referred to information flow vector. We analyze the properties of information flow vector, and conclude some requirements the information flow vector should meet with, and then construct an optimal network coding model. With the model, the problem of reducing the additional computational overheads of network coding operations can be converted into a programming formulation. Therefore, we can find out the optimal network coding-based data delivery scheme with minimal computational overheads by solving the model. Moreover, we consider some special cases and proposed a utility tradeoff-based network coding model in which the utility and computational overheads are considered together.2. Key link-based low-cost network coding algorithm and its distributed implementation. From the viewpoint of practical interests, we analyze the inherent characteristics of network coding and show that the essence of network coding is that there are some key links shared by deferent paths between the source and multi-receivers when we establish the transmission paths for the data delivery network. To achieve the maximal throughput of the network, network coding is needed and the key links should carry encoded information. Since the additional computational overheads in network coding system are caused by the network coding operations, an effective way of reducing additional computational overheads and realizing a low-cost network coding transmission scheme is to reduce the number of key links while constructing transmission paths. Following this idea, we present a key links-based algorithm for low-cost network coding and propose its distribution implementation.3. Cluster network coding-based content distribution scheme. Due to the technical and non-technical reasons, the IP multicast based data delivery system which the network coding original proposed for has not been widely implemented in the network till now. As a scable solution to deliver content to a large number of end-users, the overlay network based P2P cooperative data delivery scheme and systems have been widely used recently. Borrowing the idea of network coding, a novel data delivery scheme which is based on network coding was proposed. However, some reaserchers think the performance of such novel scheme be less optimistics due to the additional computational overheads caused by network coding operations. To optimize the data delivery scheme and enhance the performance further, we proposed some new mechanisms, such as clustered network coding, random choice-based strategy and independence checking algorithm etc. Based on the proposed mechanisms, we construct an improved network coding-based data delivery scheme. Compare to the common used data delivery scheme, the improved scheme can reduce the additional computational consumptions of network coding operations to a large extent, and improve the performance of data delivery system significantly.更多还原