一种基于网络编码的多路并行传输方案

摘要

本发明提出了一种基于网络编码的多路并行传输方案，解决在无线网络中进行多路并行传输时，由于无线网络的不可靠性引起的频繁丢包和多路径的差异性引起的失序问题。引入网络编码，打破传统可靠有序传输中按序接收的限制，关注接收数据包的个数而非顺序。根据丢包率添加冗余数据包，主动补偿传输过程中可能发生的丢包，避免重传。以组为单位进行传输管理，保证拥塞窗口的快速充分增长，增强系统对超时和丢包的容忍度。采用基于网络编码的多路并行传输方案进行无线多媒体数据传输，能够主动预防并适应无线异构网络的动态性和不可靠性，隐藏失序和丢包问题，大大减少重传，有效提高吞吐量，提供高效优质的无线多媒体传输服务。

说明书

技术领域

本发明涉及通讯技术领域，通讯数据传输技术。具体涉及在流控制传输协 议上结合网络编码的多路并行传输的实现。

背景技术

随着社会的发展，人们对于高质量、高效率和方便的多媒体无线传输服务 的需求越来越高。世界各地很多城市都已经为实时视频流建立了城市网络，例 如车载无线网络。随着无处不在的宽带移动网络接入技术的流行，多路并行传 输CMT（Concurrent Multipath Transfer）成为增强多媒体传输的最可取的方 式之一。目前，CMT的实现主要基于流控制传输协议SCTP（Stream Control  Transmission Protocol），研究表明，SCTP能够有效实现多路并行传输。SCTP  CMT拥有较好的带宽聚合能力、容错性以及负载平衡能力，这些特点使其能够为 多媒体内容分发提供有效的数据传输服务。

然而，CMT在有一个非常严重数据包重排缺陷。由于多路径具有较大的路径 差异（如带宽、时延和丢包率），数据包失序到达接收端，接收端需要一边缓存 较快路径上已到达的数据包，一边等待较慢路径上延迟的数据包，进行数据包 重排，保证数据包的有序交付。当数据包失序严重且移动终端的缓存受限时， CMT的性能会受到缓存阻塞的限制，导致连接进入空闲状态。目前有很多研究工 作都致力于减缓数据重排，其主要挑战是如何在确定的路径评估下进行数据调 度。这些研究都遵从严格的有序数据接收，其传输性能仍然被动地受到接收缓 存中的数据重排的影响。

另一个需要关心的问题是，无线信道的不可靠性导致丢包和重传经常发生。 为了达到可靠数据传输的目的，有时对于同一个数据包需要进行不止一次的重 传。在这种情况下，判断丢包原因是拥塞或者无线错误是非常重要的。一些研 究工作试图加强CMT的可靠性，节省重传的开销。这些研究考虑单个数据包的 唯一性，进行数据包的丢失检测。然而，这几乎不能减少重传。

近年来，对于网络编码的研究显示，传输层网络编码可以提供一种简单的 方法打破数据包和传输序列号TSN之间的强约束关系。虽然这种约束在可靠有 序传输中是非常重要的，但实际上传输层的最终目的是进行可靠的数据传输。 这样，接收端只关心数据包到达的数量，而不关心数据包到达的顺序，不需要 进行重排序。再者，当发生丢包时，编码包可以互相替代和补充，不需要重传 特定的数据包。在TCP或SCTP中，编译码计算会给确认的回复带来较大延迟， 引起自动重传请求ARQ（Automatic Repeat reQuest）和拥塞控制的性能下降。 Online ACK机制的提出可以解决该问题，使得网络编码能与TCP兼容且有效执 行。随后，网络编码以及online ACK机制被应用到MPTCP中，可以提高多路径 网络的吞吐量。然而，由于MPTCP是一个较新的将SCTP CMT移植到TCP上的想 法，并没有形成标准。再者，MPTCP并不具有SCTP的全部特性，例如灵活的多 块数据包格式，心跳机制和选择确认，这些特性都能与网络编码合作，优化其 性能。同时现有研究也没有涉及优化拥塞控制和区分无线环境中的丢包原因。

发明内容——权利要求书部分

有鉴于此，本发明提出了一种基于网络编码的多路并行传输方案，在流控 制传输协议的多路并行传输过程中，结合网络编码，打破按序接收的传统可靠 传输思想，消除数据包的唯一性，提供高性能的多媒体数据传输服务。本发明 定义了一个基于组的网络编码运算，根据一个组内的原始数据包生成网络编码 包；采用了一个混合快速数据分发策略，选取具有最大容纳空间的路径进行数 据分配，并按需添加冗余；提出了一个组传输管理机制，进行拥塞控制、重传 等管理。本发明能够有效地避免数据包重排，补偿丢失的数据包，解决因路径 差异性和移动终端存储限制而引起的缓存阻塞，主动适应无线网络的动态性， 为移动用户提供高效的多媒体传输。

1、一种基于网络编码的多路并行传输方案，其步骤包括：

a)基于组的网络编码运算。利用带宽和丢包率确定组数目，对一个组内的 数据包进行线性组合网络编码；

b)混合快速数据分发策略。选择具有最大容纳空间的路径进行数据分配， 每分配完一组数据，都在路径缓存末尾添加一定冗余数据包；

c)组传输管理机制。以组为单位进行传输管理，包括拥塞控制、必要的重 传以及丢包率的记录更新。

2、如权利要求1所述的基于组的网络编码运算，其特征在于：

a)往返时间RTT测量：发送HEARTBEAT获取RRTT，对比SRTT，当RRTT与 SRTT接近时，选择SRTT的值作为路径的RTT；当RRTT与SRTT差距较大时，选 择RRTT作为路径的RTT；

b)带宽BW估计：由测量时间间隔内数据的发送量和测量时间的比值得到 带宽样本，再进行平滑处理得到带宽估计值；

c)组数目更新：利用往返时间RTT、带宽BW以及丢包率pe确定组数目；

d)网络编码包生成：根据组数目划分组，对一个组内的数据包进行线性组 合编码，并在数据包中插入相应编码信息。

3、如权利要求1所述混合快速数据分发策略，其特征在于：

a)路径选择：选择具有最大容纳空间的路径进行数据分配，其中最大容纳 空间是指，在某一时刻路径允许发送的数据量与已发送但尚未确认的数据量的 差值再乘以成功发送率；

b)添加冗余：根据某组分配到某路径上的数据包个数以及丢包率进行冗余 度计算，添加冗余数据包，保证该独立路径上能够成功到达接收端的数据包数 量不小于其分配的数据包个数。

4、如权利要求1所述的组传输管理机制，其特征在于：

a)基于组的拥塞控制：对于当前指向的组GC，如果SACK确认GC中一个新 的TSN，执行慢开始或者拥塞避免算法；若GC的丢失报告到达三次以上，根据 丢包原因执行相应快速重传算法；若超时GTO，则进行与标准SCTP类似的超时 重传算法；

b)丢包率pe计算：对于当前最后完成传输的组GP，记录GP在各路径上按 发送数据包的总数和成功接收的数据包，计算各路径的丢包率。

本发明具有如下技术效果：

1、在本发明中，以组为单位进行网络编码并混合发送编码包或者原始数据 包。不管数据包有没有进行编码，都可以看做是经过线性组合的编码包。这样， 每一个编码包仅仅代表了组的一个关系，编码包不是独立和唯一的，任何丢失 的编码包都可以用属于该组的其他编码包代替，同时同一个组内的编码包之间 没有顺序。接收端只要收到足够数目的编码包，就能译出原始数据，不必考虑 数据包失序问题，恰当的冗余度也能大大减少甚至避免重传。

2、在本发明中，以组为单位进行传输控制。发送端关注属于一个组的确认 消息，而不是某一个数据包的确认消息。只要SACK中确认了属于当前组的TSN， cwnd就能进行相应增长；SACK连续三次以上没有确认任何属于当前组的TSN时， 就执行快速重传；GTO超时，执行超时重传。以组为单位的拥塞控制，保证了 cwnd的告诉增长，同时对于对包以及超时的容忍性大大增强。

附图说明

图1为本发明的系统整体框架；

图2为多路径网络编码原理图；

图3为组数目更新算法流程图；

图4为网络编码包包格式示意图；

图5为快速数据分发算法流程图；

图6为路径缓存占用情况示意图；

图7为组传输管理算法流程图。

具体实施方式

为使本发明的技术手段、创作特征、达成目的与功效便于理解，下面将结 合附图及具体实施例对本发明进行详细阐述。

1、系统整体框架图

为了解决在SCTP CMT中，由于路径的多样性引发数据重排序和丢包，最终 导致传输性能下降的问题，本发明提出了一种基于网络编码的多路并行传输方 案。如图1所示，即为本发明的系统整体框架，包括发送端，接收端和无线网 络上的多路径。

BW&RTT估计模块计算带宽BW和往返时间RTT，传输管理模块计算丢包率pe。 由带宽BW、往返时间RTT以及丢包率pe决定每次对多少数据包（用N表示）进 行编码。这一组携带数据块DATA chunks且TSN连续的数据包被称为组（Group） （图1中蓝色方框所示）。携带其他块（例如控制）的数据包不进行分组和编码， 仅仅按照往常方式发送。

混合数据分发模块将数据包分组并自适应地选择路径进行数据传输。网络 编码器随机选择数据包进行网络编码，这样在路径缓存里混合了原始数据包（白 色）和编码包（黄色）。为了能够正确快速解码，这两个模块需要附加一些冗余 数据包。虽然设置冗余会增加发送数据包的数量，但是考虑到恰当的冗余能保 证足够的数据包到达接收端，从而大量减少重传，所以添加冗余数据包是值得 的。同时，传输管理模块接收SACKs以获取数据包接收状态，维护拥塞控制， 并判断是否有必要进行重传。其传输管理是基于组而不是像标准SCTP那样以数 据包为单位。

在接收端，数据包先保存在接收缓存中，然后递交给网络译码器进行译码， 恢复原始数据包。接着，这些数据包将被组装并交付给应用层。最后，接收端 回复SACK。

2、多路径网络编码原理

多路径网络编码的原理如图2所示。发送端将原始数据包S1-S4划分为一个 组，用G表示，并进行线性组合编码。不管是发送原始数据包还是编码包，他 们都包含了编码系数。这使得发送的数据包所携带的不再是应用层数据，而是 代表了原始数据之间的关系。因此，接收端没有必要严格按序接收数据包，只 需要缓存这些数据包并提取它们之间的关系（系数）。此外，各数据包之间等价， 这些信息之间可以进行互换，任何丢失的数据包都能由其他的数据包补充。这 样，只要接收端收集到足够数量的数据包（理论上4个），就能够通过高斯消元 法正确译码出原始数据包，同时也不需要考虑其他丢失的数据包或者重传。总 的来说，通过网络编码，数据包不再由他们的TSN唯一决定，接收端不再需要 重新排序，同时发送端也大量减少了重传。

3、基于组的网络编码运算

设计网络编码的首要问题是每个组需要包含多少数据包，即组数目N。为了 达到较低的缓存需求但同时保证能够进行充分的乱序补偿，组数目需要适当高 于失序数据包的数量。当发生重传时，说明组数目已经滞后于多路径环境的变 化，则根据时延、带宽和丢包率更新N。

时延即BW&RTT估计模块测量的RTT时间。由于SCTP CMT允许在与相应数 据包不同的路径上回复SACK，普通的SRTT（Smoothed RTT）测量方式可能会不 准确。SCTP为路径探测提供了心跳机制，其要求HEARTBEAT_ACK在与HEARTBEAT 相同的路径上回复。当需要更新组数目时，发送两个HEARTBEATs，等待两个 HEARTBEAT_ACKs都成功接收，这样就能获得这两个HEARTBEATs的RTT时间并选 择其中的较小值作为路径的RRTT（Reference RTT）。如果SRTT和RRTT接近， 说明很有可能SACK的回复路径与数据包的发送路径是相同的，或者其前向和反 向路径具有相同的时延，此时，考虑到SRTT的估计是基于大量样本的，其结果 更为准确，我们选择SRTT作为路径RTT；反之，SRTT和RRTT差距较大，则选 择RRTT作为路径RTT。对于路径i，我们通过下式确定路径的RTT：

${\mathrm{RTT}}_i=\left(\begin{array}{cc}{\mathrm{SRTT}}_i(\mathrm{if}{\mathrm{SRTT}}_i\in [a*{\mathrm{RRTT}}_i,b*{\mathrm{RRTT}}_i\left]\right)& \\ {\mathrm{RRTT}}_i& \left(\mathrm{otherwise}\right)\end{array}\right)---\left(1\right)$

其中a<1和b>1为RTT边界因子。

带宽BW同样由BW&RTT估计模块测量。将带宽的概念转化为：可用带宽的 值等于数据发送量和发送时间的比值。当组数目需要更新时，根据下式收集路 径i的带宽样本：

${\mathrm{BWsample}}_i=\frac{{\mathrm{sendsize}}_i}{{\mathrm{Tl}}_i-{\mathrm{Te}}_i}---\left(2\right)$

其中sendsize_i是从最后一次抽样结束到此刻的数据发送量，Tl_i和Te_i分别为在 这段时间内最后一个数据包离开路径i缓存和第一个数据包进入该缓存的时间。 为了消除波动，对带宽样本进行平滑处理，得到估计结果：

$\left(\begin{array}{c}{\mathrm{BW}}_i=[1-\exp \left(\frac{-({\mathrm{Tl}}_i-{\mathrm{Te}}_i)}{T_0}\right)]*{\mathrm{BWsample}}_i\\ +\exp \left(\frac{-({\mathrm{Tl}}_i-{\mathrm{Te}}_i)}{T_0}\right)*{\mathrm{BWprevious}}_i\end{array}\right)---\left(3\right)$

其中T₀为带宽平滑因子，BWprevious_i为上一个估计结果。

丢包率由传输管理模块提供，这将在后续内容中提及。最后，我们按照下 式更新组数目：

其中pe_j为路径j的丢包率，MTU为最大传输单元，通常假设所有路径的MTU都 是一样的。

如图3所示，为组数目更新的算法流程图：

1）当发生重传时，对于每条路径，重复步骤1-4。

2）发送两个HEARTBEATs，等待HEARTBEAT_ACK，若超时则重传，直到接收 到两个HEARTBEAT_ACKs。获取两个HEARTBEATs的RTT时间，选择其中较小值作 为RRTT，根据式（1）确定路径的RTT。

3）根据式（2）提取带宽样本，根据式（3）计算带宽，并更新BWprevious。

4）从传输管理模块获得丢包率pe。

5）根据式（4）更新组数目N。

确定组数目之后，混合数据分发模块划出具有连续序列号S₁-S_N的N个数据 包交给网络编码器。当网络编码器要生成一个编码包时，从有限域GF(2⁸)中随 机抽取N个参数a₁，a₂，…，a_N，形成一个S₁-S_N的线性组合编码包T。由于每个 参数a_i(1<i<N)可以表示为一个字节，每个数据包也是由一串字节组成， 生成编码包的计算实际为字节之间的加法和乘法，若把S₁-S_N看做字节向量，则：

T＝a₁S₁+a₂S₂+...+a_NS_N       （5）

如图4所示，对于所有的数据包，不管是原始数据包还是编码包，我们都 在DATA块之前插入一个携带编码信息的NC块，其中包括组的范围和编码系数。 这个NC块能告知接收端如何处理这些数据包。这样，在这个组中，提供给用户 数据的总的负载空间就会减少

4、混合快速数据分发策略

由于网络编码避免了组内的数据包重排序，所以这里并不需要调度机制。 需要做的是分配最大的数据量到路径缓存上并且尽可能快地发送数据。一种简 单的解决方法是尽可能填满有效窗口（effective window）。有效窗口决定了某 一时刻允许发送的数据量。路径i上的有效窗口被定义为：

effwnd_i＝min{cwnd_i,arwnd}      （6）

其中cwnd_i为路径i的拥塞窗口，arwnd为最新SACK中通知的接收窗口。路径i 上最大容纳空间为：

space_i＝(effwnd_i-outstanding_i)(1-pe_i)      （7）

其中outstanding_i为路径i上已发送但还未收到确认的数据量。最后，将数据 包分配给具有最大空间的路径。重复寻找具有最大space的路径并分配数据包， 直到分配完一个组的数据。

如图5所示，为快速数据分发的算法流程图：

1）当有数据需要传输时，根据式（7）计算每条活动路径的最大容纳空间， 并选取具有最大容纳空间的路径j（当存在多个最大容纳空间时选择其中带宽最 大的路径）。

2）如果j为空值，等待某路径释放缓存，并在该路径上分发数据。否则， 在路径j上分发数据。

为了保证可解码性以及减少重传，需要添加冗余数据包。在分配完一个组 的N个数据包之后，我们在每条有数据分配的路径缓存末尾加入一些冗余数据 包。冗余包的产生和编码包的产生相同，也包含了整个组的信息。冗余数据包 与在其之前的数据包具有相同的TSN，可以在SACK中通过重复TSN域进行确认。

假设在一个包含N个数据包的组中，分配到路径i上的数据包为M_i，则路 径i上的冗余度应该设置为：

其中$N=\underset{i}{\Sigma }{M}_i---\left(8\right)$

由于路径i上数据成功接收率为1–pe_i，该冗余度的设置可以保证在该 独立路径i上最终能够有M_i个数据包到达接收端。这样，所有路径上总共能够 有N个数据包到达接收端。图6显示了路径缓存中的占用情况。我们可以看到 在大多数情况下，在每条路径上只有一个冗余数据包，这是因为快速数据分发 算法会在丢包率较低的路径上分配更多的数据包，使得冗余度稳定在最低值。

5、组传输管理机制

根据以上的编码设计，包括拥塞控制、必要重传和路径丢包率记录等传输 管理最好能以组的单位进行。这些管理都在传输管理模块中进行。定义组超时 GTO（Group Time-Out）为该组第一个数据包的重传超时RTO（Retransmission  Time-Out）。定义两个组指针GC和GP。

GC表示当前尚未被接收端成功解码、最早发送的组，该组数据包保存在路 径缓存的最前端等待确认。GC与标准SCTP中的outstanding数据包在拥塞控制 中具有相同的用处。也就是说，如果SACK确认了GC中的一个新的TSN，则执行 慢开始算法或者拥塞避免算法；如果GC的丢失报告到达三次以上，则执行快速 重传；如果到达GTO，则执行GC的超时重传。需要指出的是，因为拥塞控制是 以一个组而不是以独立数据包为单位，所以cwnd的更新得到加强，同时对丢包 和SACK超时的容忍性也大大增强了。故而，cwnd能够快速增长到足够的值，重 传也得到大大的减少。

发生快速重传时，我们选择拥有属于GC的outstanding数据包最多的路径 p进行相应判断。比较BW_p和cwnd_p/RTT_p之间的大小判断丢包原因：如果 cwnd_p/RTT_p＜BW_p，表明路径并没有发生拥塞，判断丢包是由无线错误引起的， 不修改cwnd_p；否则，把丢包归结于拥塞，减小cwnd_p：

ssthresh_p＝max(BW_p*RTT_p,cwnd_p/2,4*MTU)      （9）

${\mathrm{cwnd}}_p=\left(\begin{array}{cc}{\mathrm{cwnd}}_p& (\mathrm{if}{\mathrm{cwnd}}_p/{\mathrm{RTT}}_p<{\mathrm{BW}}_i)\\ \min ({\mathrm{cwnd}}_p,{\mathrm{ssthresh}}_p)\left(\mathrm{otherwise}\right)& \end{array}\right)---\left(10\right)$

其中ssthresh_p为路径p的慢开始门限值，考虑到带宽，它需要考虑多一个因素 BW_p*RTT_p。同时重传一个GC的编码包。

发生超时重传时，同标准SCTP一样执行拥塞窗口和门限值的调整操作。同 时重传包的个数为GC的组数目N与当前已被接收端确认的GC数据包数目之间 的差值。

所有重传的数据包都同样进行网络编码，并拥有与该组中最后一个数据包 (S_N)相同的TSN号，这同样能通过SACK中重复确认的TSN域进行辨别。最后， 选择BW_q(1-pe_q)最大的路径，尽快进行数据包重传。

GP是在GC之前的、最近的成功译码的组，其数据包已经从缓存中释放，但 其接收状态仍然被保留。GP用于进行丢包率(pe)的计算。通过SACK，GP可以记 录在各路径上发送的数据包总数（包括了冗余包和重传包）以及成功接收的数 据包。当GC完成译码时，传输管理模块收集GP在每条路径上未确认数据包与 总数据包的比值，作为一个丢包率样本，利用置信区间统计更新路径的丢包率。 最后，传输管理模块将每条路径的丢包率反馈给混合数据分发模块。GC和GP分 别指向下一个组，重复算法。

如图7所示，为组传输管理的算法流程图：

1）如果在一个GTO内收到SACK，执行步骤2-4，否则执行步骤5。

2）初始化minGroup和maxGroup的值。

3）对于SACK中的每一个新的或者重复的TSN x，进行如下操作：找出x所 属组G，G的组接收计数器count计数，G的组丢失报告计数器missing_report 置零，释放x；更新minGroup和maxGroup；如果G为当前组GC，更新发送x 的路径的拥塞窗口，同时如果GC的组计数器值大于等于GC的组数目，释放所 有GC的数据包，更新丢包率，更新GC和GP。

4）对于每一个在minGroup和maxGroup之间的组G，进行如下操作：如果 SACK中没有属于G的确认，G的组丢失报告计数器计数，同时如果G的组报告 计数器的值大于3，进行快速重传。

5）对于GC中超时TSN所在的各路径，进行超时重传。