一种基于网络编码的新型TCP协议传输系统

admin

一. 理论基础
          本项目针对现有TCP协议在丢失率较高的网络环境下所表现出的糟糕性能，提出基于网络编码的改造，以TCP-Vegas为基础通过修改其源代码（逻辑上在TCP层与IP层之间加入全新的网络编码层）实现在发送方对原始TCP报文段编码，在接收方解码，并针对网络实时丢失率调整编码报文段的发送冗余，以达到向TCP层掩盖丢失的目的；同时加入处理器共享技术，该技术旨在用一个合适的初始速率来代替TCP的慢启动过程。最终提高网络吞吐量和可靠性，缩短数据流完成时间。
           
          1.网络编码：
          2000年，以香港中文大学信息工程系为主的研究人员针对通讯网络的瓶颈问题，提出了网络编码理论，以网络编码器取代路由器，在网络中传输包的线性组合，在接收端通过解码恢复出原始数据包。
          
          网络编码的概念可以通过蝴蝶拓扑图来进行简单的说明，如图1-1所示：
           

       

        图1-1 网络编码的基本原理

         

          假设上图中每条路径单位时间内只能传输1比特，则采用路由方式，UV链路会成为传输瓶颈，即只能传输a和b中的一个信息。若UV链路传输消息b，则信宿P能收到消息a和b，而信宿Q只能收到消息b；若UV链路传输消息a，则信宿Q能收到消息a和b，而信宿P只能收到消息a。两者情况下，平均每个信宿节点的吞吐量为1.5比特。
           
          同样的条件下，若采用网络编码，即UV链路上传输的是消息a和b的编码，则信宿P可以接受消息a且译码出消息b，信宿Q可以接受消息b且译码出消息a。这样，平均每个信宿节点的吞吐量为2比特。
           
          从中可以得出，网络编码可以达到多播网络的最大容量，而路由却可能达不到。
           
          网络编码自诞生以来，得到了迅速的发展。短短几年，发表了几百篇学术论文，并对许多相关学科产生了深远的影响，NC的理论研究范围包括信息论及通信的几乎每个领域，如随机编码，线性编码，非线性编码，静态码，群码，卷积码，Alphabet码，算法协议，码构建，有环网络，链路失效及其网络管理，无向网络，分离理论，密码学，错误检测和纠错码，多信源编码，Cost Criteria，多-单播编码，非均匀需求，最大流/刮集界，关联信源编码，叠加编码，网络互连，路由寻找，无线及卫星网络，Ad hoc网络，传感网络，数据存储及分布，矩阵理论，复杂性理论，图论，随机图论，，多种物流（Multicommodity flow），游戏理论，矩阵胚理论（Matriod theory），信息论不等式，排队论分析，树装箱（Tree Packing）率失真（rate-distortion）可逆网络，多用户信道，联合网络信道编码，P2P网络等。
           
          国外多所著名大学如普林斯顿大学、麻省理工、瑞士EPFL 学院等和多家IT 公司的研究中心,包括微软研究院、贝尔实验室、AT &T 的香农信息实验室等都在积极开展对网络编码理论和应用的研究。最近国内学者也开始研究网络编码，如清华大学、西安电子科大、电子科技大学、北京邮电大学、中国科学技术大学、复旦大学、上海大学等。
           
          2.TCP协议：
          传输控制协议（TCP）是一种面向连接的、可靠的、基于字节流的运输层（Transport layer）通信协议。在简化的计算机网络OSI模型中，它完成第四层传输层所指定的功能。
           
          TCP使用端口号，提供进程到进程的通信，是一种面向流的协议（如图1-2）。它把在每一个方向传送的数据字节都进行编号。编号不一定从0开始，而是在 之间产生一个随机数作

       

        图1-2 流的传输

         

          为第一个字节的号码。当字节都被编上号后，TCP就给每一个报文段指派一个序号（该序号为报文段中第一个字节数据的编号，见图1-3）。接收方接到报文后，要使用确认号对它已收到的字节进行确认，确认号是累计的，在数值上等于期望接收的下一个字节的编号。
           

       

        图1-3 报文段序号

         

          在实际传输中，为了避免信道拥塞，我们完全可以只发送一个字节的数据，然后在发送下一个字节之前等待确认。但如果信源和信宿之间的距离很大，那么信源就要在等待确认时一直处于空闲状态，信道吞吐率很低。为了完成流量控制，TCP使用滑动窗口协议。
           
          滑动窗口如图1-4所示，它可以展开、合拢和收缩，但这三种运动受接收端而不是发送端控制。

       

        图1-4 滑动窗口

        展开窗口表示窗口右沿向右移动，允许从缓存中发送更多新的字节。合拢窗口表示窗口左沿向右移动，某些字节已经被确认，发送端可以不必再保留。缩回窗口表示窗口右沿向左移动，一般在现实情况中不被允许。
           
          在现实情况中，常常会遇到报文段丢失，为了重传丢失的报文段，TCP使用了重传计时器，来处理重传超时。当TCP发送一个报文段时，它就创建这个特定报文段的重传计时器。这可能会发生两种情况[1]：
           
          若计时器截止时间到之前收到了对这个特定报文段的确认，则撤销这个计时器。
           
          若在收到了对这个特定报文段的确认之前计时器截止期到，则重传这个报文段，并把计时器复位。
           
          TCP处理拥塞的一般策略是基于三个阶段：慢开始，拥塞避免和拥塞检测。在慢开始阶段，发送端从非常慢的发送速率开始，但很快就把速率增大到一个门限。当到达门限时，数据率的增长就放慢以避免拥塞。最后如果检测到拥塞，发送端就又回到慢开始或拥塞避免阶段。
           
          3.FPGA及Linux系统：
          Spartan-6具有USB2 port，VGA，10/100 Ethernet端口和设备，满足本项目对网络环境设置的要求。
            
          Linux操作系统具有开源、高效、移植性强等特点，可以通过修改其源码把新型的TCP协议潜入其中，最终通过硬件实验直观的展现新协议的优点。
           
          二. 项目可行性分析
          本项目团队成员具有长时间的网络编码研究经验，并各有所长，分别精通用户界面设计、Linux源码开发、FPGA与嵌入式系统设计，因此具备了人员基础。指导老师李挥教授是网络编码理论研究的专家，在整个项目过程中会给我们悉心指导。
           
          1.理论条件：
          本项目组在网络编码与TCP协议融合方面已有了一定的研究基础，形成了自己的一套理论，并已经在NS-2仿真平台上进行了初步试验。Linux操作系统的独特优点可以把理论运用到实际的点到点传输环境中。
           
          2.软硬件条件：
          实验室已具备相关软硬件条件：
          NS-2仿真平台；
          装载CentOS 5.5操作系统的主机若干台；
          NetFPG若干；
          网线；
          USB-UART数据线；
           
          三. 设计原理
          本项目研究对象为点对点网络通信，主要创新点为采用了网络编码和新型的TCP传输协议，最终目标是实现网络传输在数据丢失情况下的高可靠性和高吞吐量。项目的整理架构如下（图3-1）。

         

       

        图3-1 项目整理架构

         

          两台主机分别充当通信系统的信源和信宿，其中的传输协议已改为新型的TCP协议。界面会显示相应的网络传输参数以及直观的展现传输数据（如视屏）的效果。传输网络由FPGA组搭建而成，主要实现网络丢失环境设置，数据存储转发，信号显示等任务。
           
          1.网络编码层设计：
          网络编码层设计是本项目的核心，是整个系统的灵魂。

       

        图3-2 网络编码层

        各模块说明如下：

        报文段仲裁器1

        位于TCP与NC层之间的仲裁器。具备判断2种类型数据的能力：

        1.来自TCP的数据报文段；

        2.来自TCP的用于连接等控制信号的报文段。

        如果是1，则将其放入输入缓存；如果是2则直接送往IP层。

         

        报文段仲裁器2

        位于IP与NC层之间的仲裁器。具备判断3种类型数据的能力：

        1.来自IP的已编码报文段；

        2.来自IP的用于连接等控制信号的报文段；

        3. NC_ACK信号。

        如果是1，则将其放入输入缓存；如果是2则直接送往TCP层；如果是3，则交由NC_ACK判决器。

         

        编码模块

        NC_ACK判决器

        用于判决NC_ACK信号，告诉编码窗口应删除哪一个或哪几个原始报文段，同时其负责“伪造”ACK发给上层TCP。

         

        输入缓存

        保存来自TCP的数据报文段，因为编码窗口每次仅读取一个原始报文段，输入缓存用来保存还未来得及处理的原始报文段。

         

        编码窗口

        保存原始报文段，每次从输入缓存读取一个原始报文段，收到NC_ACK判决器发来的信号后即删除相应报文段。

         

        随机数产生器

        产生0~255的随机系数，不过在使用时应避免0。

          

        编码器

        利用随机数产生器产生的随机系数对编码窗口中存在的报文段编码，若当前编码窗口只有一个报文段，则直接交给合成器，不进行编码。

         

        合成器

        将包头产生器传来的NC包头和已编码的报文段合成一个完整的NC层报文段，交给输出缓存。

         

        输出缓存

        接收合成器传来的NC报文段，在此处设置输出缓存也可起到控制发送速率的作用。

         

        系数表

        收发双方在建立连接时由发送方传递给接收方的系数表，整个会话过程中系数表不变。根据系数偏移读出相应的系数。

         

        包头添加模块

        报文段编码情况

        即本次有多少报文段参与了编码，这个在解码时必须知道。

         

        系数偏移

        指示本次所使用的系数在系数表中开始的位置。

         

        包头产生器

        将报文段编码情况模块和编码系数模块传来的信息封装成规定格式的NC包头，再由合成器与相应已编码报文段组成NC报文段。

         

        解码模块

        输入缓存

        保存来自IP的数据报文段。

         

        包头处理

        将包头和负载分离，通过包头中的系数偏移和编码情况恢复出编码系数。

          

        系数缓存

        存放编码系数，并执行高斯消元，确定新看见的报文段，若发现新的报文段则向NC_ACK产生器发送信号，否则丢弃这一组编码系数并通知解码缓存及报文段编码模块一并删除这一组数据。

         

        报文段编码情况

        和包头添加模块中一样，存储报文段参与的信息。

         

        解码缓存

        存放编码报文段数据，执行与系数缓存相同的高斯消元，在解码时从报文段编码情况模块获取报文段编码情况信息。

         

        NC_ACK产生器

        NC层独有的ACK，收到系数缓存传来的信号，便产生一个ACK并把它传递给编码模块的输出缓存，用来告知发送方自己所看到的报文段情况，同时向ACK产生器发送信号。

         

        输出缓存

        解码的报文段按原来的顺序存放在这里，然后传给TCP，同样可以进行速率控制。

           
          2.处理器共享技术的融合：

        对于短流持续时间比其所需时间更长的情况，处理器共享（Processor Sharing）机制可以很好应对，它的核心思想就是模拟处理器的资源在各线程间公平分配的特点，把路由器每个线卡的输出链路带宽平均分配给那些正在进行的所有信息流。在建立连接时，每一跳路由根据当前线卡使用情况及发送方的期望发送速率分配给其一个合适的初始速率，缩短以慢启动方式达到合理共享速率的时间。