信息中心网络内数据重传算法的优化

辛营营 刘晓娟 方春林 罗欢

摘 要：对于信息中心网络（ICN）中原始数据恢复机制的网络带宽利用率低下的问题，提出一种基于网络编码的实时数据重传（NC-RDR）算法。首先，根据网络的实时状态对网络中丢失的数据包进行统计;然后，将网络编码结合到信息中心网络中，对统计的丢失的数据包进行组合编码;最后，将编码后的数据包重传发送给接收端。对提出的方案进行分析，仿真结果表明，与基于网络编码的多播数据恢复（NC-MDR）算法相比，在传输带宽（平均传输次数）方面，降低了约30%，因此，在信息中心网络中，该算法能有效地减少网络重传次数，提高网络传输效率。

关键词：信息中心网络;网络编码;多播传输;数据重传;基于网络编码的实时數据重传算法

中图分类号： TP393.01

文献标志码：A

文章编号：1001-9081（2019）03-0829-05

Abstract： Aiming at the problem of low network bandwidth utilization rate of the original data recovery mechanism in Information Centric Networking （ICN）， a Network Coding based Real-time Data Retransmission （NC-RDR） algorithm was proposed. Firstly， the lost data packets in the network were counted according to the real-time status of the network. Then， network coding was combined into Information Centric NetworkingICN， and the statistical lost data packets were combinatorially coded. Finally， the encoded data packets were retransmitted to the receiver. The simulation results show that compared with NC-MDR （Network Coding based Multicast Data Recovery） algorithm， in the transmission bandwidth aspect， the average number of transmissions was reduced by about 30%. In ICN， the proposed algorithm can effectively reduce the number of data re-transmissions， improveing network transmission efficiency， and enhance network transmission performance.

Key words： Information Centric Networking （ICN）; network coding; multicast transmission; data retransmission; Network Coding based Real-time Data Retransmission algorithm （NC-RDR）

0 引言

随着网络应用的不断发展，人们越来越关注如何高效、快速地获得网络内容，这种变化使得一种新的以内容为中心的网络构架——信息中心网络（Information Centric Networking， ICN）[1]被催生。最近很多国家的研究项目都在关注以信息为中心的网络来探讨未来互联网的研究，其中有欧洲的PSIRP（Publish-Subscribe Internet Routing Paradigm）[2]、4WARD[3]、PURSUIT（PUblish-SUbscribe Internet Technologies）[4]和SAIL（Scalable and Adaptive Internet solutions）[5]，以及美国的DONA（Data-Oriented Network Architecture）[6]、TRIAD（Translating Relaying Internet Architecture integrating active Directories）[7]、CCN（Content-Centric Networking）[8]和NDN（Named Data Networking）[9]。如今，信息中心网络已引起广泛关注，成为研究热潮。

信息中心网络越来越受到关注，并且一些人员已经开始从事其多播方面的研究，但他们基本没有研究到该网络多播传输过程中数据重传的问题。又因为网络编码[10]在传统网络中对宽带利用率的提升非常明显，而且也有论文提到“ICN 天然支持多播”[11-12]，所以在其中引入网络编码非常合适。文献[1]提出一种基于网络编码的多播数据恢复（Network Coding based Multicast Data Recovery， NC-MDR）算法，其将网络编码引入ICN中对传输数据包进行编码，利用网络编码可以消除数据之间的差异性这一特点，来降低汇聚节点重传次数，提高重传效率;但是该算法假设了可靠控制分组交换机制这一条件，没有考虑到网络的实时状态，因此针对该问题提出一种基于网络编码的实时数据重传算法，即根据重传过程中的实时网络状态动态地形成编码分组。对该方案进行了相应的理论性能分析，并进行仿真，表明该方案能很好地提高传输效率。

1 网络编码

1.1 网络编码起源

网络编码（Network Coding， NC）最早提出于2000年。多用于多播网络，以提高网络的传输效率。

1.2 网络编码的基本原理

NC利用中间节点对收到的数据进行线性或非线性的处理，之后将被处理的信息转发出去，以此减少传输次数[13]。

为了更直观地理解，本文以图1为例，通过和原始路由的性能进行比较，来对其基本原理进行描述。

在图1（a）网络中每条链路只能通过1bit的数据、并且没有时延也没有链路丢包。图1（b）中和图1（c）中均采用传统路由传输，且链路WX不能同时通过数据c和d（数据c和d均为1bit）。图1（b）中链路WX传输的是数据c，所以节点Y只收到数据c，节点Z收到数据c和d。故图1（b）中的平均网络吞吐量为（2+1）bit/2=3/2bit/节点。同上，图1（c）的平均网络吞吐量也为3/2bit/节点。图1（d）采用网络编码，节点W在收到上游节点转发的数据c和d时，对其进行编码（c⊕d），后将编码数据转给节点X。故节点Y和Z进行译码后均会收到两种数据c和d，故图1（d）的平均网络吞吐量为2bit/节点。综上所述，采用网络编码，整个网络的吞吐量要明显大于采用路由时的情况。

1.3 网络编码的分类

与传统的路由传输方式相比，采用网络编码可有效地均衡网络流量，提高带宽利用率，提升网络的吞吐量。为了选择合适的网络编码，将对下列三种编码方式进行比较。

喷泉码[14]具有很高的效率，对于那种对时延非常敏感的易错网络非常适用;但编码包的随机性较大，并且在译码时会有一定的几率失败，它采用的次优译码算法[15]，该算法在降低解码复杂度的同时减小了译码正确率。

系統码[16]的特点为可以直接在原始数据后面添加检验数据，若成功接收则不需再对校验数据进行解码，若出现错误则通过可以校验位进行数据恢复;其解码操作需要耗费一定的时间。

线性网络编码[17]的提出具有很大的意义。它的原理是：消费者接收的编码数据包是线性组合包，此组合的系数是一个编码向量。若向量确定，即称其确定性网络编码;否则（即从某个有限域随机选取系数）称其为随机线性网络编码[18]。

对比分析可知，喷泉码比随机线性网络编码冗余数据量大，浪费带宽多，而随机线性网络编码比系统码会以更小的概率发生反馈风暴，故选择随机线性网络编码与信息中心网络相结合。

2 数据重传的基本原理

ICN是一类以信息内容本身为中心的未来互联网体系机构的统称。其中CCN为目前较为主流的研究对象，故本文以CCN为例阐述网络中的多播数据重传机制。

内容中心网络（CCN）的通信由内容消费者驱动，数据可以进行块级传输。网络中传输的包类型有两种：兴趣包（Interest）和数据包（Data）。其中，Interest包包含了内容消费者所请求内容的名字，Data包包含了消费者所请求的内容。图2为CCN的节点模型[8]示意图。

如图2所示，CCN的节点包含内容仓库（Content Store， CS）、转发请求表（Pending Interest Table， PIT）和转发信息表（Forwarding Information Base， FIB）。其中：CS用于缓存数据;PIT包含当前节点已经发送出去但尚未收到反馈的Interest包，并记录内容的名字和发送的接口，以及时间等信息;而FIB用来记录不同前缀的转发接口。CCN的数据请求转发机制如图3所示。

如图3所示，当一个兴趣包到达，路由器根据兴趣包中的内容名字，查找内容仓库，若命中则响应该请求，并丢弃此兴趣包;否则查找转发请求表，若命中则在条目中增加接口，并丢弃该兴趣包;否则查找转发信息表，若命中，则按照查找到的所有接口转发兴趣包，并记录在转发请求表中，否则丢弃该兴趣包。

如图4所示，当数据包到达，路由器根据数据包的名字，在内容仓库中查找，若命中，则丢弃它;否则查找转发请求表，若命中，则根据查找的接口转发出去，然后缓存在内容仓库中;否则丢弃该数据包。

CCN天然支持多播，当内容响应所有请求时，由于链路丢包的存在，此多播响应过程容易发生数据丢失，进行多播的汇聚节点需要对丢失的数据重传恢复。CCN中原始的数据恢复机制使得每次丢失数据的请求端受益较少，在一定程度上降低了CCN的传输性能。文献[1]中作者提出一种NC-MDR算法来解决这个问题，此作者假设了一个可靠控制分组机制（使重传数据全部被消费者接收成功），但是网络状态实时变化，此假设不太符合实际网络状态。对此，本文提出一种针对网络实时变化的链路状态的数据恢复算法，即基于网络编码的实时数据重传算法（NC-RDR）。

3 数据重传的算法设计

3.1 CCN模型建立

为了节约请求的数量，节点处会有一个PIT表记录请求相同数据的兴趣包，相同的请求在转发节点处进行汇聚而只转发一个请求出去，当数据返回时，该汇聚节点将返回的数据发送给所有请求该数据的节点，这样就形成一个多播场景。但由于链路不稳定，请求数据可能会在传输中丢失，且各个请求端丢失的数据可能不尽相同，故为了恢复丢失的数据，汇聚节点需根据每个请求端反馈的丢失信息制定重传策略来进行数据的重传。上述CCN的多播传输如图5所示。

在本文的多播传输网络模型中有一个生产者、一个汇聚节点和M个消费者（R1，R2，…，RM）。M个消费者同时请求同一内容，汇聚节点汇聚收到的来自M个消费者的兴趣包后，向上游节点只转发一个兴趣包。当被请求内容沿请求径返回时，汇聚节点会将此内容多播发送给M个消费者。

为了更清楚地描述提出的方案，本文作出以下定义。

定义1 缓冲矩阵T。它是根据来自消费者的反馈信息形成的，表示多播过程中每个消费者接收每个数据包的状态。在此矩阵中，第i行表示第i个消费者（1≤i≤M）接收每个数据包的情况，第j列表示第j个数据包（1≤j≤N）在每个消费者处的接收情况。当消费者每成功接收到一个数据包时，缓冲矩阵T中相应的位置将被标记为1;否则标记为0。

定义2 传输带宽η。它定义为将一个内容块成功传送到所有消费者处的平均传输次数。

定义3 原始数据传输阶段。使用N个时隙发送N个原始数据包（将一个内容块划分为N个数据包进行传输）。

定义4 编码数据传输阶段。根据网络状态发送编码数据包，直到所有消费者成功解码出原始数据为止。

3.2 NC-RDR算法

在所提出的方案中，汇聚节点首先执行原始数据传输阶段，即在N个时隙中同时给M个消费者发送N个原始数据包。在此阶段结束时所有消费者都已向汇聚节点反馈信息以显示网络的网络状态。汇聚节点在信息反馈的同时根据反馈回来的信息制作一个列表，以形成一个缓冲矩阵T。矩阵T记录信息以显示各个数据包是否被某个消费者丢失。在完成原始数据传输阶段后，根据缓冲矩阵T，将丢失的原始数据包动态组合在一起形成新的编码包。故，如何组合这些丢失的原始数据包是关键。以下给出详细的组合方案：

1）首先，汇聚节点寻找对应于缓冲矩阵T中的每一行中首0元素的原始数据包，将这些数据包通过随机线性编码方法组合成一个新的编码包，并立刻将缓冲矩阵T中的这些“0”更改为“1”。

2）汇聚节点发送在步骤1）中形成的新编码包。如果一些消费者又丢失了编码包，它们会将信息再次反馈给汇聚节点，将矩阵T中与之对应每一行的元素再次更改为“0”。

3）根据更新后的矩阵T，汇聚节点将检查T中是否还有“0”元素。若还存在“0”元素，汇聚节点将重复上述步骤，直到矩阵T中没有“0”元素为止。

为了便于理解提出的方案，本节以一个例子为例进行详细的解释。本实例中包含6个请求端（R1，R2，R3，R4，R5，R6），每个内容块再细分为10个数据包（a1，a2，a3，a4，a5，a6，a7，a8，a9，a10）。如图6所示，图中显示是一个具有6行（M=6消费者）和10列（N=10数据包）的缓冲矩阵T。如果消费者成功接收到一个原始数据包，则T中相应的元素标记为“1”;否则，丢失的数据包相应元素标记为“0”。

图6显示了各个消费者各自的丢失数据包的情况以及在编码数据传输阶段中哪些原始数据包应该参与线性组合的情况。在矩阵中，有4种不同的底纹图案（深灰色、灰色、浅灰色（包括一个横纹底纹单元格）和一个竖纹底纹单元格）。每种底纹图案都包含“0”元素，红色深灰色底纹包含第一组被编码的“0”元素，即每一行的首个“0”元素。与“0”元素对应的原始数据包（同一个颜色的）将被组合在一起，形成一个新的编码包。在此之后，汇聚节点将按照形成的顺序发送这些编码包。

值得注意的是，图6中有一个有着横纹底纹的“0”元素是第3个编码分组和第4个编码分组的重叠，它意味着第3个蓝色浅灰色分组被消费者R3丢失，因此，有横纹底纹的元素将被再次更改为“0”，而a10将被记录在紫色有竖纹的编码分组里，以生成第4个编码包。总之，有4个编码的数据包将按以下顺序发送：

其中βij是从有限域随机抽取的网络编码系数，与传统的将所有原始数据包组合在一起的随机网络编码方法不同，本文提出的方案是根据实时网络状态动态地组合原始数据包。它也不同于XOR方案，这种XOR方案中，如果一个XOR包丢失，生产者必须重新发送同一包，直到所有消费者都能正确地接收它。本文提出的方案是将丢失的原始数据包与每一次传输的随机系数结合起来，因此，根据线性代数理论，消费者只需要获得足够的编码包来解码，就可以获得比XOR更高的效率。

下面是基于网絡编码的实时数据重传算法（NC-RDR）的伪代码流程：

4 算法的性能分析

4.1 算法的理论分析

4.2 仿真结果与性能分析

本节将对NC-RDR算法进行性能分析，在ndnSIM上对算法进行仿真。在仿真过程中，PIT的使用是永久性的，且在仿真中，将我们的本文方案与文献[1]中的方案进行对比，用“方案1”表示文献[1]中提出的方案。在仿真实验中，进行传输的数据包的数量设置为N= 1000，并设置以下3个场景进行仿真：

场景1 假设在仿真模型中消费者的数量M= 8并且每个消费者的丢包率pi（i=1，2，…，8）的值的范围设置为0.02～0.24。仿真对比分析丢包率对传输带宽的影响。

图7所示传输带宽η的理论推导和仿真，从图中可以看出，在传输带宽方面，本文方案明显低于方案1，同时可以看出，本文方案的仿真曲线和理论推导曲线保持了很好的一致性。除此之外，还可以得出：所有方案的传输带宽均随着丢包率的增大而增大。然而，随着丢包率的增大，本文方案与方案1相比差距也越来越大，说明对于更高的丢包率来说，本文方案传输性能更好。

场景2 研究消费者的数量对于传输带宽的影响，假设在仿真模型中所有消费者的丢包率均为0.12，而消费者的数目为2，3，4，5，6，7，8，9，10，11，12。图8所示为传输带宽的理论推导和仿真曲线。

从图8中可以看出：随着消费者数量的增加，传输带宽也在增大，但本文方案的传输带宽始终比方案1的低。最重要的是，当消费者数目较大时，本文方案与方案1之间的差距更大，说明在消费者数量较大时，本文提出的方案传输性能更好。还可以发现，本文方案的仿真结果和理论结果吻合度很高。

场景3 研究在最大丢包率pi=0.24和最小丢包率pi=0.12下两种方案在不同消费者数量下的传输带宽，假设在仿真模型中每个消费者的丢包率相同。实验结果仿真如图9所示。

從图9中可以看出：无论信道质量是好是坏，本文提出的方案总是比方案1更好一些，并且在最大丢包率或最多消费者的情况下，本文提出的方案比方案1具有更高的传输效率。证明本文提出的方案更适用于信道质量较差的传输。

5 结语

针对信息中心网络中原始多播数据恢复效率低下的问题，本文提出一种NC-RDR算法，来降低网络的传输带宽，以此来提高网络的传输效率。该算法根据实时的网络状态，通过随机线性编码对丢失的数据包进行动态组合，并进行了理论推导和实验仿真，证明了该算法在降低重传次数和提升传输性能上有效性，并且与方案1的重传方案相比具有明显的优越性。

参考文献 （References）

[1] 赖永芳.未来网络传输性能优化研究[D].北京：北京邮电大学，2015：1-2.（LAI Y F. Research on the optimization of network transmission performance in the future [D]. Beijing： Beijing University of Posts and Telecommunications， 2015： 1-2.）

[2] LAGUTIN D， VISALA K， TARKOMA S. Publish/subscribe for Internet： PSIRP perspective [C]// Proceedings of the 2010 International Conference on Towards the Future Internet - Emerging Trends from European Research. Trier： DBLP， 2010： 75-84.

[3] NIEBERT N， BAUCKE S， El-KHAYAT I， et al. The way 4WARD to the creation of a future Internet [C]// Proceedings of the 2008 IEEE 19th International Symposium on Personal， Indoor and Mobile Radio Communications. Piscataway， NJ： IEEE， 2008： 1-5.

[4] FOTIOU N， NIKANDER P， TROSSEN D， et al. Developing information networking further： from PSIRP to PURSUIT [C]// Proceedings of the 2010 International Conference on Broadband Communications， Networks and Systems. Berlin： Springer， 2010： 1-13.

[5] BRUNNER M. Scalable and Adaptive Internet Solutions （SAIL） [Z]. [S.l.]： Future Internet Assembly， 2010.

[6] KOPONEN T， CHAWLA M， CHUN B G， et al. A data-oriented （and beyond） network architecture [J]. ACM SIGCOMM Computer Communication Review， 2007， 37（4）： 181-192.

[7] GRITTER M， CHERITON D R. TRIAD： a new next-generation Internet architecture [J]. Computer Science Dept， Stanford University， 2001.

GRITTER M， CHERITON D R. TRIAD： a new next-generation Internet architecture [EB/OL]. [2018-04-15]. http：//citeseerx.ist.psu.edu/viewdoc/download;jsessionid=E1DC2A617FB7A41A6A47973B45236638？doi=10.1.1.33.5878&rep=rep1&type=pdf.

[8] JACOBSON V， SMETTERS D K， THORNTON J D， et al. Networking named content [C]// Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies. New York： ACM， 2009： 1-12.

[9] ZHANG L X， AFANASYEV A， BURKE J， et al. Named Data Networking （NDN） project [J]. ACM SIGCOMM Computer Communication Review， 2014， 44（3）： 66-73.

[10] GKANTSIDIS C， RODRIGUEZ P R. Network coding for large scale content distribution [C] // Proceedings of the 24th International Conference on Annual Joint Conference of the IEEE Computer and Communications Societies. Washington， DC： IEEE Computer Society， 2005，4： 2235-2245.

[11] MANGILI M， MARTIGNON F， PARIS S， et al. Efficient joint bandwidth and cache leasing in information centric networks [C]// Proceedings of the 2013 International Conference on Global Communications Conference. Piscataway， NJ： IEEE， 2013： 2223-2229.

[12] FRANGOUDIS P， POLYZOS G C， RUBINO G. Content dissemination in wireless networks exploiting relaying and information-centric architectures [C]// Proceedings of the 2015 International Conference on Heterogeneous Networking for Quality， Reliability， Security and Robustness. Piscataway， NJ： IEEE， 2015：169-173.

[13] 冀向陽. 未来网络传输协议设计与实现[D]. 北京：北京邮电大学， 2015：11-12.（JI X Y. Design and implementation of future network transmission protocol [D]. Beijing： Beijing University of Posts and Telecommunications， 2015： 11-12.）

[14] BYERS J W， LUBY M， MITZENMACHER M. A digital fountain approach to asynchronous reliable multicast [J]. IEEE Journal on Selected Areas in Communications， 2002， 20（8）： 1528-1540.

[15] 王静，刘景美，王新梅，等.一种网络编码的多播路由算法[J].西安电子科技大学学报（自然科学版），2008，35（1）：71-75.（WANG J， LIU J M， WANG X M， et al. Multicast routing algorithm for network coding [J]. Journal of Xidian University （Natural Science Edition）， 2008， 35（1）： 71-75.）

[16] MASSEY J L， COSTELLO D J. Nonsystematic convolutional codes for sequential decoding in space applications [J]. IEEE Transactions on Communication Technology， 1971， 19（5）： 806-813.

[17] LI S Y R， YEUNG R W， CAI N. Linear network coding [J].IEEE Transactions on Information Theory， 2003， 49（2）： 371-381.

[18] HO T， MEDARD M， KOETTER R， et al. A random linear network coding approach to multicast [J]. IEEE Transactions on Information Theory， 2006， 52（10）： 413- 430.