基于多源的NDN端节点拥塞控制算法

沈越欣 王兴伟 李洁 曾荣飞

摘   要：文章以NDN网络现存拥塞控制算法的端节点拥塞信号获取不准确为研究问题，提出一种基于端节点的拥塞控制算法。这种算法从源头上控制拥塞，并依据多个拥塞信号进行端节点速率调整，以更贴近全局网络状态的方式进行端速率调整以保证吞吐量。文章考虑NDN多源特性，结合累积排队时延信息，设计端节点重传定时策略，避免过多重传加重网络拥塞，进而确保网络的稳定性。

关键词：命名数据网络;多源;端节点拥塞控制;累积排队时延;重传定时策略

1 引言

随着网络应用类型的多样化和用户数据的爆炸式增长，以内容为中心的网络流量逐渐占据主要位置[1]。以内容为中心的命名数据网络（Named Data Networking，NDN）也成为了研究热点[2，3]。随着网络流量的不断增加，拥塞控制对网络中的内容成功获取、稳定性和服务质量等具有举足轻重的作用。NDN体系结构支持流量平衡（One-interest-one-data），其基于接收端驱动（Receiver-driven）和多源（Multi-source）、多路径（Multipath）的特性，更是给NDN拥塞控制機制的设计增添了难度。随着命名、缓存、路由机制的不断成熟，针对NDN拥塞控制机制[4]的研究已引起广泛关注。

NDN拥塞控制面临着众多挑战。由于NDN中没有类似于TCP中的重复ACK，且因为NDN的多源特性，通过重传超时（Retransmission Time-Out，RTO）来判断拥塞并不准确，故适用于TCP/IP的拥塞控制策略如依据RTO、重复ACK确认的拥塞检测等均不能直接应用于NDN中。

本文利用NDN独有的优势和特点进行端节点拥塞控制算法（End-node Based Congestion Control，EBCC）的设计与实现：（1）针对NDN多源性，设计了三种拥塞信号，基于这些拥塞信号反馈进行相应的速率调整保证网络吞吐量;（2）通过准确地获取拥塞信号并经过中间节点逐跳累积，反映网络全局信息;拥塞信息的反馈利用数据包“捎带”的方法，不会增加过多额外负载;（3）在端节点设计了重传定时机制，具有很好的适应性，避免过多重传加重网络拥塞，确保网络稳定性。

2  相关工作

现有拥塞控制策略可以分为单源拥塞控制、多源拥塞控制。单源拥塞控制中[5，6]，通过在请求方调整兴趣包的发送速率来控制拥塞。文献[5]提出了一个端节点兴趣控制协议（Interest Control Protocol，ICP），设置在请求方的AIMD 控制器会根据当前网络的拥塞状况来调整发送窗口的大小，并通过为每个兴趣流维护历史往返时延RTT值来计算RTO，以此来判断拥塞。文献[6]提出基于端节点的自调整兴趣速率控制机制，该机制利用数据包的到达时间间隔差，来调整兴趣包的发送时间间隔差，以此来控制兴趣包的发送速率。文献[5，6]是基于单源的假设，这在NDN中往往不能成立，一些考虑多源特性的端节点拥塞控制算法被提出，如文献[7～9]。

文献[7]提出根据往返时延来设置超时值是不可靠的，并提出一个基于隐式反馈的接收方驱动拥塞控制策略。但它假设端节点知道内容源的位置，且在传输过程中不会改变，这在实际场景中并不太可能。文献[8，9]分别提出为每个路径、内容储存库（Content Store，CS）维护一个RTO。文献[8，9]都是基于将多源问题转化成多个单源问题，存在两个弊端：其一，对于拥塞的判断依然依靠RTO，由于RTO的测量存在不准确性，造成对网络拥塞状况的评估不准确，不能保证很好的网络稳定性;其二，在端节点需要对每个流、内容源或路径等维护多倍的信息，这会造成高昂的成本，且可扩展性很低。

本文提出的端节点拥塞算法在AIMD与CoDel的基础上进行改进，依据数据包携带的累积排队时延、NACK包和数据包超时等不同的拥塞信号，进行不同的窗口调整。

3 问题描述

3.1 模型设计

NDN网络模型可以抽象为一个无向连通图G =（C，R，E）。其中，C代表网络中的端节点集合;R代表网络中的中间节点集合;E代表考虑了时延（传输时延和排队时延）、链路带宽等参数的物理链路集合。

为实现拥塞控制，中间节点在转发处理的过程中，记录网络拥塞信号，通过数据包“捎带”的方式，将网络拥塞信号逐跳更新直至反馈回端节点;端节点会根据用户内容请求生成兴趣包，且会根据收到的具体拥塞信号作出适合当前网络状态的速率调整;若数据包没有在预定时间内成功返回，端节点根据当前是否仍需要该内容选择是否对兴趣包重传，具体流程如图1所示。

为实现上述通信过程，网络中运行三种包：兴趣包、数据包和NACK包。其中，NACK包只是在兴趣包的基础上添加了错误码（Error Code）字段信息，其他字段信息与原兴趣包相同，当下游节点收到NACK包，会为此NACK包重新寻找接口进行转发。如果当前节点无法找到满足速率限制的可用接口，该兴趣包会以NACK包的形式回溯到上一跳。

针对NDN多源性，将基于超时与窗口调整的传统拥塞控制对于端节点速率变化的影响进行如下分析。

NDN的通信特性使现有的适用于传统网络的拥塞控制策略不能直接迁移使用，NDN中的窗口调整需要重点考虑：（1）仅仅依靠超时作为拥塞信号容易造成对拥塞反应不够有效，即如何选择适合NDN的拥塞反馈信号，从而能够准确迅速地对拥塞作出反应并保证网络吞吐量;（2）由于NDN多源的特性[7，8，11]，对于端节点的请求，其内容提供者并不固定造成超时值计算不准确的问题，即如何准确地计算NDN中超时值，如何设置端节点超时重传策略以保证网络稳定性。

接口限速分析：本文队列占用的计算不是基于整个路由器缓冲区，而是针对具体某个接口。设t时刻接口k的当前兴趣包转发速率，t时刻接口k的兴趣包速率限制记为，为接口k的队列阈值，为前缀prefix对应的流的队列占用，N（t）为t时刻流的个数，数据包大小记为D_pktsize;Link_capk为接口k对应的链路容量。

第一个速率上限为数据包返回速率，如公式（1）所示，单位为包/秒，其中为控制参数。

第二个速率限制为不同流之间的公平速率，针对每个“前缀接口对”（prefix，k）进行公平速率计算，考虑了接口容量、接口队列占用以及对应接口链路容量，如公式（2）所示，其中h为控制参数。

最终该接口的限制速率不能超过以上两个限制，若超过，则该接口不可用，需要选择次优接口，并重新进行判断，接口速率限制如公式（3）所示。不满足速率限制的接口将会设为不可用。

4 基于多源的端节点拥塞控制算法

为了解决NDN中拥塞检测不准确等问题，本文提出了一种基于多源的端节点拥塞控制算法EBCC。首先在中间节点进行拥塞信息维护与传递更新，并设定超时重传，然后设计了三种拥塞信号及相应控制处理。

4.1 拥塞信息维护与传递更新

每当数据包返回至当前节点vi时，均携带其邻居节点vj的拥塞信息，包括“本地拥塞信息”（Local Congestion Information，LCI）和“非本地拥塞信息”（Nonlocal Congestion Information，NCI），故每个节点需要维护两种拥塞信息。

4.2 超时重传设定

超时重传值作为拥塞信号，若计算值过小会导致拥塞误判，降低链路资源利用率，而过早的超时重传也会为网络注入额外的流量，浪费网络资源，反之若计算值过大会降低用户服务质量。在TCP/IP中端节点超时重传值ReTimerend的计算一般采用公式（8）和（9）进行计算。

其中，为往返时延的线性移动平均值，为往返时延的线性偏差，m为一固定常数，为未更新之前的往返时延线性移动平均值，为当前的往返时延，为时延平滑参数。由于NDN多源特性导致这种通过时延平均值计算超时值的方式不准确，因此在公式（8）和（9）的基础上，HR-ICP[12]采用公式（10）计算ReTimerend，并证明了其稳定性。

其中，为一固定常数，RTTmax为历史最大往返时延，RTTmin历史最小往返时延也被认为是传输时延，故RTTmax-RTTmin被认为是最大排队时延的估计值，其基本思想是主要利用瓶颈链路排队时延值来控制端节点调整窗口。但是这种方式，并没有真正考虑到NDN网络多源的特性，RTTmax和RTTmin的测量包含了到所有内容源的时延记录，无法反映当前网络拥塞程度。

中间节点在包中记录了排队时延信息，且排队时延逐跳累积，形成到达端节点的累积排队时延AccumQD，AccumQD经过逐跳累积可以较好的反映全局网络状态，且记录的是当前内容源到端节点的排队时延，不会受多源网络场景影响准确性。综合以上分析，本文的超时重传值采用公式（11）进行计算。

其中 为调整参数，AccumQDcur表示当前累积排队时延，AccumQDmax代表历史最大累积排队时延，由公式（13）可以看出，ReTimerend受历史时延和当前网络拥塞状况影响，如果AccumQDcur较大，表示网络拥塞较严重，则ReTimerend也会较大，反之，较小。

4.3 拥塞信号设计

针对NDN多源性，本文的端节点拥塞控制共设计了三种拥塞信号。

（1）成功返回数据包信号D_pktSuc：当收到D_pktSuc时，可以从D_pktSuc获取到达端节点vend时的累积排队时延AccumQD。通过排队时延反映拥塞状况已被很多研究者使用。在此基础上，考虑NDN多源场景，本文提出累积排队时延作为拥塞信号之一来对兴趣包的速率进行调整。NDN网络中请求的内容以数据包的形式原路返回，只需在返回的数据包中增加一个记录排队时延的字段，不会增加过多额外的负载;通过累积排队时延依概率减小拥塞窗口，可以起到预防拥塞的作用。由于到达端节点的AccumQD通过逐跳累积得到，其计算公式即为公式（6）。

（2）错误应答兴趣包信号I_pktNACK：NDN多个内容源可产生多条路径，每个中间节点的FIB表记录了内容前缀和对应的一系列可用接口，由于对于每个前缀有不止一个可用接口，若当前接口已经过度拥塞，则可以寻找下一可用接口进行转发，利用多条路径分流的思想来避免拥塞。如果当前节点无法找到可用接口，那么兴趣包会被添加NACK头部，以I_pktNACK的形式回溯到上一跳，如果上一跳依然无法找到可用接口，兴趣包会再次回溯到上一跳。假定网络拥塞状况十分严重，所有节点都无法找到可用接口，则I_pktNACK会最终回溯到端节点，端节点收到I_pktNACK时，可以判断此时的网络状况较为拥塞，从而减少兴趣包发送速率来对拥塞作出反应。因此I_pktNACK可以作为一个网络拥塞较为严重的拥塞信号。

（3）数据包超时信号D_pktTimeout：数据包未在预定超时重传时间ReTimerend前成功返回，视为D_pktTimeout信号。D_pktTimeout的判定依赖于ReTimerend的计算。具体而言，每收到一个数据包，在端节点维护其时延RTT，对维护的N（N默认设为30）个历史往返时延样本RTT_samples={RTT1，RTT2，…，RTTN}，有历史最小时延RTTmin=min{RTT1，RTT2，…，RTTN}，类似的，对于端节点维护的N个历史累积排队时延样本，有AccumQD_samples={AccumQD1，AccumQD2，…，AccumQDN}，有歷史最大累积排队时延AccumQDmax={AccumQD1，AccumQD2，…，AccumQDN}，代入公式（11），可以计算出ReTimerend。

4.4 拥塞控制处理

端节点拥塞控制主要是基于不同的拥塞信号反馈进行相应的速率调整，针对上述三种不同的信号，拥塞处理方法有三种。

（1）收到成功返回数据包D_pktSuc拥塞信号的处理：AccumQD通过数据包携带返回，可以直接从D_pktSuc中获取，由于AccumQD是累积值，通过多个链路汇聚所得，因此在一定程度上反映了全局网络状态。为了避免仅依赖超时作为拥塞信号的窗口调整对时延过于敏感，导致窗口急剧减小，且存在滞后性，本文采用根据AccumQD依概率减小拥塞窗口，如果需要执行窗口减小，则C_window变为C_window*α。由图2所示为窗口减小的概率图，其中 、 分别为设定的累积排队时延最小、最大阈值，概率计算为公式（12）。

D_pkt的成功返回，表示当前网络状况相对较良好，因此若没有执行依概率窗口减小，则对窗口进行“和式增加”以充分利用链路资源，保证吞吐量。采用这种方式，可以根据累计排队时延提前对拥塞进行控制，起到了一定的预防拥塞的作用，且依概率进行的方式，使得拥塞控制更为“温和”。

（2）收到错误应答兴趣包I_pktNACK拥塞信号的处理：I_pktNACK通过中间节点逐跳回溯才能最终返回到端节点，表示整条路径上的节点接口可能都已超过了速率限制，因此应当在端节点减小请求速率，将C_window变为C_window*β。

（3）收到数据包超时D_pktTimeout信号的处理：当收到D_pktTimeout时，表明当前路径较为拥塞，将C_window变为C_window*γ，并根据端节点是否仍有获取该内容的需求来决定是否进行端节点重传。由于本文根据累计排队时延已经依概率减小窗口，因此当收到I_pktNACK或D_pktTimeout时，窗口不会进行减半而是采用一個较大的参数，其中，避免了对时延“敏感”的拥塞控制。

通过上述分析，本文提出了端节点拥塞控制算法，伪代码描述如表1所示。

5 性能评价

5.1 拓扑用例

本文采用的网络拓扑为哑铃型拓扑和多路径拓扑。哑铃型拓扑结构如图3所示，含有11个节点，两条瓶颈链路，包含4个兴趣请求者，3个路由器和4个内容提供者;多路径拓扑结构如图4所示，含有16个节点，包含3个兴趣请求者，4个路由器和9个内容提供者。实线连接线代表常规链路，虚线连接线代表瓶颈链路。

5.2 基准机制

本文选取被广泛认可的HR-ICP以及ARMN[14]作为基准算法进行对比分析。

5.3 评价指标

（1）平均时延兴趣包从请求者发送的时刻记为Timesent，数据包返回的时间记为Timereturned，则从兴趣包发出到收到相应数据包的往返时延Delay为：

（13）令Delayi表示第i个兴趣包的往返时延，网络当前共发送了k个包，则平均往返时延为：

（14）（2）丢包率丢包率的计算如公式（15）。其中，Numdrop为网络传输过程中丢失的包个数，Numtotal为请求者请求的兴趣包总数。

（15）（3）吞吐量吞吐量定义为单位时间Timeunit内处理的数据量Dataprocessing，

5.4 端节点拥塞控制算法性能评价

为了验证本文提出的端节点拥塞控制算法的性能，在两种网络拓扑下，将本文设计的端节点拥塞控制算法（下文图中用EBCC表示）和两种基准机制分别进行仿真实验。在网络初始化阶段后，收集全网500～5000个兴趣请求对应的平均时延、丢包率和吞吐量三个指标。

（1）平均时延

由图5和图6所示为平均时延随请求数变化的情况，当兴趣请求个数大于1500时，三种算法逐渐体现出不同性能。EBCC在端节点设置了基于多种拥塞信号的窗口调整机制，根据累积排队时延依概率调整窗口，可以提前控制拥塞，故始终保持最低的平均时延，相比基准算法减少了18.1%～27.2%。HR-ICP在其端节点设置基于RTT的窗口调整策略，可以在一定程度上在端节点控制往返时延，因此时延低于ARMN;在ARMN中，其端节点仅以NACK包作为拥塞信号进行窗口调整，由于NACK包需要通过逐跳回溯才能到达端节点，端节点无法及时获取网络状态进行速率调整，导致时延很大。

（2）丢包率

由图8和图9所示为丢包率随请求数变化的情况，在两种拓扑中丢包率随兴趣请求个数的变化趋势大体相似，在兴趣请求个数为500～2500范围内丢包率随兴趣请求个数的增大变化相对较为平稳;当兴趣请求个数逐渐增大后，三种拥塞控制算法逐渐体现出不同的性能。其中，EBCC在端节点设置了基于多种拥塞信号的速率调整机制，对拥塞信号的反应更加灵敏也更加贴合网络实际状态，且在端节点设置了基于NDN多源网络场景的超时定时机制，因此丢包率最低，相比于基准算法减少了14.8%～15.1%。HR-ICP在以RTO作为拥塞信号，当发生数据包超时时，则认为发生拥塞，并将拥塞窗口乘性减小，一定程度上控制了丢包率;ARMN在端节点仅以NACK包作为拥塞信号进行窗口调整，由于NACK包需要通过逐跳回溯才能到达端节点，端节点无法及时获取网络状态进行速率调整，导致丢包率最大。

（3）吞吐量

由图10和图11所示为吞吐量随请求数变化的情况。在兴趣请求个数较小时，吞吐量随兴趣请求个数增加而增加的趋势较为明显;当兴趣请求个数大于2500之后，吞吐量受兴趣请求个数影响不再明显，不同机制逐渐体现出不同的性能。HR-ICP在其端节点采用的ICP的调整机制主要是依据RTT，当RTT过大时会急剧减小窗口，导致端口队列常处于较小的状态，最终端节点的吞吐量也较低;ARMN利用了多路径转发的思想，对NACK包重新寻找接口而不是延迟转发保证了吞吐量;EBCC在端节点根据多个拥塞信号进行窗口调整，且拥塞信号的选择能够较好地反映全局网络状态，且由于可以根据累积排队时延依概率对拥塞窗口进行调整，避免时延敏感，其速率调整也能更好地利用网络资源，始终保持较高的吞吐量，相比于基准算法提升了13.2%～15.8%。

4 结束语

针对NDN拥塞控制中端节点拥塞信号获取不准确等问题，本文通过对NDN现有的拥塞控制算法进行分析，提出了一种基于多源的端节点拥塞控制算法EBCC。该算法考虑并设计不同的拥塞信号，可以依据不同的拥塞信号进行端节点速率调整，并在端节点对超时进行重新设定，避免时延敏感，保证吞吐量。在下一步研究中，将分析具体缓存策略对拥塞控制的影响，并将NDN中间节点的转发、缓存与拥塞控制三者综合考虑，使拥塞控制更为有效。