基于BBR的NDN拥塞控制算法

黄俊琳,雷 凯,汪 漪

(1.北京大学深圳研究生院 互联网研发中心，广东 深圳 518055；2.南方科技大学，广东 深圳 518055)

0 引 言

命名数据网络(named data networking, NDN)[1]关注于内容分发和获取，是信息中心网络(information centric networking, ICN)[2]的一个被广泛关注的体系构架[3]。

无论是传统的TCP/IP网络还是命名数据网络，拥塞都是不可避免的。网络拥塞的发生，根源在于用户对网络资源的需求大于网络自身所能提供的能力。并且拥塞发生一般会直接导致网络出现数据包丢失、传输时延增加、网络吞吐量下降等现象，如果没有有效的拥塞控制方法进行调控，严重的时候甚至会导致网络崩溃。为了提高网络传输的性能，需要使用拥塞控制算法来解决有限的网络资源的分配问题。在不同的场景下，拥塞控制的优化目标存在不同，现有的NDN拥塞控制算法大多都将提高链路吞吐量作为主要的优化目标，但是，随着5G无线通信技术的快速发展以及自动驾驶、虚拟现实、增强现实和直播等技术与应用的出现，如何在高通量的网络下充分利用带宽以及保障低延时传输成为传输控制的一个新目标。传统的加性增乘性减(additive increase multiplicative decrease，AIMD)的窗口调节思想不再适用于高速网络，保守的线性增加和激进的乘法减小窗口的方法使得链路带宽利用率很低，抑制了NDN在高通量网络下的发展，有必要针对这一特定的场景研究相应的NDN拥塞控制算法。

要设计出适合NDN的拥塞控制算法，必须充分考虑NDN在数据传输上的新的特性[4]。

1)数据传输由接收端驱动。消费者通过向网络发送Interest包去请求内容，中间节点通过内容缓存(content store, CS)、待处理请求表(pending interest table, PIT)以及转发信息表(forwarding information base, FIB)对Interest进行处理和转发，最后由拥有所请求数据的节点返回对应的Data包。接收端驱动的传输模式，是在接收端实现流量控制以及拥塞控制的基础。

2)Interest包和Data包之间是一一对应的关系。一个Interest包只能取回一个Data包，并且对应的Data包沿着Interest包到达的路径原路返回。这种关系是在NDN中实现逐跳流平衡的基础。

3)多数据源。NDN的传输是无连接的，并且内容可以缓存在网络的内部，因此，消费者能够从不同的内容源(生产者或者缓存了对应内容的中间节点)获取数据。

4)多路径传输。NDN的架构天然支持多路径转发。在NDN中，路由节点能够通过Interest包中的内容名和随机数识别并丢弃发生环回的包，同时，因为Data包是沿着Interest包传输的原路径返回的，所以，NDN中不会出现Data包环回的现象。而传统的TCP/IP网络通常使用确定的最优路径来传输以防止数据包发生环回，这使得TCP中的多路径是基于固定的路径。因为NDN的路由和转发是相互分离的，路由节点能够根据数据面的表现来进行多路径转发，所以能实现比TCP/IP更灵活的多路径传输。

尽管NDN在传输模式上与TCP/IP存在区别，但是2种架构下拥塞控制的本质都是对有限的网络资源进行调度以提高网络的传输性能，关注的2个基本问题都是如何预防拥塞的发生以及如何快速感知和响应拥塞。在实现上两者都是基于反馈信息进行的闭环控制，并且端节点以及中间路由节点都是拥塞控制的参与者，例如，两者都可以使用基于窗口的端到端的速率调节方法、中间节点都可以通过队列管理参与到拥塞控制中。这些共性使得TCP的拥塞控制算法能够被引入到NDN中，但是需要针对NDN的特性对算法进行调整。

关注于如何在有一定的丢包率的网络链路上充分利用带宽以及如何降低网络链路上缓存的占用率、减小传输延迟这2个问题，本文分析了基于丢包的NDN拥塞控制方法的不足之处，在基于窗口的端到端拥塞控制算法的基础上，借鉴谷歌最新提出的TCP拥塞控制思想[5]，提出基于瓶颈带宽以及往返时延(bottleneck bandwidth and round-trip time，BBR)的NDN拥塞控制算法，并在ndnSIM实现了所提出的基于BBR的NDN拥塞控制算法。通过已有的ICP(interest control protocol)[6]拥塞控制算法进行对比，验证了所提出的算法的性能。

1 相关研究

TCP拥塞控制的成果为NDN拥塞控制的研究提供了不少的思路。现有的很多的NDN拥塞控制算法都还使用TCP的基于丢包或者基于时延的思路。TCP中的AIMD的窗口调节机制也在NDN得到广泛的应用。但是，NDN和TCP在数据传输模式的差异决定了两者在拥塞控制的具体方法上必然存在差异。

Carofiglio等[6]提出的ICP拥塞控制算法是一种接收端驱动的，基于窗口的端到端Interest包控制协议，窗口调节遵循AIMD的原则。这种方法对拥塞的判断是基于丢包的，即根据超时重传阈值(retransmission timeout, RTO)来判断包传输是否发生超时，以确定是否发生拥塞。ITCP(information centric transport protocol)[7]是一个与ICP类似的基于窗口的接收端驱动的传输协议，实现了与TCP相类似的慢启动、拥塞避免、快重传以及快恢复的机制。以上2个NDN拥塞控制算法是针对单数据源的场景的，没有考虑到NDN能进行灵活的多路径传输的特点。Saino[8]提出了一种维护多个拥塞窗口以及RTO值的NDN拥塞控制算法，以适应NDN多数据源的特点。Carofiglio[9]提出了一个多路径拥塞控制(remote adaptive active queue management，RAAQM)算法，该方法为每条路径设置一个RTO计时器用于判断超时丢包，不同路径的区分依赖于每个节点为返回的Data包附加的节点标识符。

虽然基于丢包的拥塞控制机制在NDN中仍被广泛使用，但是它有2个明显的缺点。

1)基于丢包的拥塞控制算法通过监控数据包是否发生超时来判断是否发生丢包以及拥塞，因此，不能区分拥塞引起的丢包和传输错误引起的丢包。如果丢包是由传输错误引起的，基于丢包的拥塞控制算法所采取的“乘性减小”窗口调节方法将带来不必要的传输窗口的大幅度减小，从而降低了网络带宽的利用率。

2)中间节点的缓存队列可用于吸收网络中数据流量的波动，减少丢包的发生。消费者采用基于丢包的拥塞控制算法时，受限于拥塞感知的方法和时机，为了能够充分探测网络的可用带宽，会向网络注入过量的数据请求包。这导致了中间节点的缓存空间的高占用率，增加了数据包在网络中的排队时延。除此之外，缓存队列过满的现象，降低了节点应对突发流量的能力，在共享该节点进行转发的数据流突然增多时，缓存会被迅速填满而发生丢包。因此，基于丢包的拥塞控制机制虽然能够保证网络以瓶颈带宽进行数据传输，但是却是以高时延以及频繁丢包为代价的。

因为基于丢包的拥塞感知方式存在滞后性并且会导致中间节点的缓存队列过满，所以一些已有的研究工作对拥塞感知方式进行改进。Schneider[10]提出一种路由器通过包排队时间以及局部丢包检测来发现拥塞、通过显式标记包来通知请求端网络发生拥塞、请求端在收到拥塞的信号后调节各个接口的转发比而将原来的拥塞路径的流量分摊到其他路径的多路径NDN拥塞控制算法。Rozhnova[11]提出了一种逐跳控制的Interest包速率控制算法。该算法根据队列占用情况和可用资源调整Interest的转发速率，当中间节点由于拥塞无法向上游转发Interest时，会通过NACK通知下游的节点。此外，该算法还会对转发接口进行标记以及排序以进行多路径适应性转发。

2 算法设计

2.1 算法整体设计思路

如果不考虑中间节点的内容缓存以及多路径传输的影响，NDN的数据传输过程中往返时延(round-trip time,RTT)、传输速率与等待接收的Data包的数据量的关系模型与Leonard Kleinrock提出的模型是基本相符的，本文基于此模型分析NDN中拥塞控制的最佳工作点。

往返时延、传输速率与已发送但未确认的包数的关系如图1所示，基于丢包的拥塞控制机制使得整个网络倾向于工作在带宽限制区域最右侧的点，虽然实现了以瓶颈带宽进行数据传输，但是缓存空间占用率过高，导致用户经历较长的传输延迟以及频繁丢包。

在Leonard Kleinrock提出的模型中，使网络工作在带宽限制区域最左侧的点要优于带宽限制区域最右侧的点。网络工作在Kleinrock最优工作点能够实现最大的传输速率以及最小的传输时延。

基于丢包的NDN拥塞控制方法仅依据返回的Data包以及计算得到的往返时延来判断网络的拥塞状态。然而，仅凭这2个信息无法量化网络当前的可用带宽。为了能够充分利用网络的可用带宽，消费者只能不断地去增加传输的速率直到发生超时丢包。本文从谷歌提出的TCP拥塞控制算法[5]受到启发，在所提出的算法中使用即时带宽以及往返时延这2个量来量化可用带宽以及描述网络的状态，从而实现更准确的控制和调节，避免接收端为了充分探测可用带宽而向网络注入过量的请求包。同时，因为拥塞不是丢包发生的唯一的原因，传输错误也是导致数据包丢失的一个因素。所以，在无法区分这2种丢包的情况下，使用丢包事件作为拥塞的标志显然是不合理的，本算法不再以丢包作为拥塞的标记，而更加关注于网络的瓶颈带宽、物理链路延迟以及由这两者决定的传输链路的容量。

基于BBR的NDN拥塞控制算法，核心是让网络工作在Kleinrock最优工作点的附近，控制用户注入网络的流量，使之匹配网络链路的承载能力，在确保数据以最大的速率传输的同时最小化中间节点的队列长度，从而最小化传输的往返时延。因为NDN中数据传输是由接收端驱动，并且一个Interest包最多只能取回一个Data包，所以，基于BBR的NDN拥塞控制算法通过在接收端控制Interest包的发送速率以及最大发送窗口来控制注入网络中数据流量。这2个参数的计算依赖于估计得到的瓶颈带宽、物理链路延迟的值以及由当前传输所处的状态决定的速率增益、窗口增益。整体设计思路如图2所示。

实现让网络工作在Kleinrock最优工作点，关键在于如何确定链路瓶颈带宽以及物理链路延迟。然而，瓶颈带宽和物理链路延迟是无法同时测量的。要测量瓶颈带宽，就必须保证网络链路带宽被充分利用，中间节点的缓存空间中存在一定数量的数据包，此时，由于排队时延的存在，传输往返时延偏大；要测量物理链路延迟，就必须保证中间节点的缓存空间无队列，此时，网络中的流量不足以占满链路带宽，测得即时带宽偏小。

由于瓶颈带宽和物理链路延迟无法被同时测量，算法采用分时测量的方法，在应用限制区域测量物理链路延迟的值，在带宽限制区域测量瓶颈带宽的值。图1中，在传输的过程中，瓶颈带宽是即时带宽的最大值，物理链路延迟是往返时延的最小值，所以，本算法使用一个固定时间窗口内的即时带宽的最大值和往返时延的最小值作为它们的估计值。

2.2 状态设置

针对数据传输在不同的阶段的特点，本算法设置了4个不同的状态，状态之间的转换由网络反馈的信息进行控制，以此来实现自主的调速机制——主动调节窗口以及周期性地去探测是否有更多的可用带宽等功能。这4个状态分别是快速探索瓶颈带宽(启动状态)、消耗中间节点长队列的低速发送(消耗队列状态)、周期性探测可用带宽的稳定(周期探测状态)、维持低发送窗口以确定最小往返时延(时延更新状态)，状态转移图如图3所示。

图3 算法状态转移示意图Fig.3 State transition diagram of the algorithm

启动状态是传输的初始状态，类似于TCP拥塞控制中的“慢启动”阶段，目的是在一个较短的时间内使数据充满传输链路以探测到瓶颈带宽。在该状态下，通过查找所测量的瓶颈带宽的平台期来确定传输链路是否被充满：如果连续在3个RTT周期内所测量的最大即时带宽只有很小的增长，可以认为已经到达平台期，将此时的即时带宽值视为瓶颈带宽。因为是在一个时间窗口内确定传输速率是否达到瓶颈带宽的，所以在探测到瓶颈带宽后会形成一个较长的队列。

队列消耗状态紧跟在启动状态之后，目的是消除在探测瓶颈带宽的过程中所形成的长队列，使传输往返时延降低到接近物理链路延迟，确保网络能够稳定在Kleinrock最佳工作点附近。当请求的数据量小于或者等于网络链路带宽时延积时，中间节点缓存的队列被完全消耗，且传输链路保持充满，接收端将从队列消耗状态切换到周期探测状态。

周期探测是一个稳定状态，传输过程中绝大部分时间会处于这个状态。在进入周期探测状态时，算法已经确定了当前的瓶颈带宽以及物理链路延迟，并以此来控制Interest包的发送速率以及窗口。此外，周期探测状态下除了进行稳定的传输之外，还有一个重要功能是周期性地去探测是否有更多的可用带宽。

为了实现主动探测，本算法使用了一个简单的序列探测机制。在每一个探测周期进行一次主动探测，每一个周期分为8个阶段，每个阶段持续的时间为测量得到的最小往返时延。阶段之间的最主要的区别是速率增益可能会不同。8个阶段分别对应于下面8个速率增益：a，2-a，1，1，1，1，1，1，其中，a为常数。整个探测周期的平均增益约为1，从而使得一个周期内的平均发送速率约等于可用带宽，实现高带宽利用率的情况下维持一个短的队列。a的取值不能过大或过小，a取值过大时，稳定探测阶段的往返时延的波动幅度会较大；a取值过小时，探测可用带宽的时间会较长，本文在使用不同的a进行实验后选取a=1.25。

在周期探测状态下，状态机不会主动向其他状态转移，但这不意味着状态机停留在周期探测状态直到传输结束。在非时延更新状态下，状态机内部会对估计的物理链路延迟进行监视。状态机发现该值长期没有被更新时，会切换到时延更新状态。在该状态下，接收端使用一个小速率增益去消耗中间节点的缓存队列，直到Interest包的发送窗口被限制在一个较小的值，并保持一段时间，确保探测到当前的物理链路延迟的准确值。

3 实验评测

本文在基于NS-3的NDN通用仿真平台ndnSIM[12]中实现了所提出的基于瓶颈带宽和往返时延的NDN拥塞控制方法，并使用不同的拓扑对该算法进行评估，并与ICP拥塞控制算法进行对比，评价所使用的指标主要有以下4点。

1)网络吞吐量。网络吞吐量是指网络在单位时间内成功传输的数据的数量，是对网络链路带宽利用的一个重要的指标。一个好的拥塞控制算法能够在最大化吞吐量的同时使传输时延最小化。

2)传输时延。传输时延是指从Interest包进入网络到对应的Data包返回到接收端之间的时间间隔，一般由物理链路延迟、数据包在中间节点进行处理(路由和转发)产生的时延以及在中间节点排队所产生的时延组成。其中，数据包在中间节点缓存中的排队时延对传输时延的影响最为明显。

3)路由节点队列长度。路由节点队列长度决定数据包在中间节点的排队时间。

4)收敛时间。收敛时间指的是瓶颈带宽链路的吞吐量收敛到瓶颈带宽所需要的时间，这一指标能够反映出高带宽网络下的小数据量传输的带宽利用效率。

3.1 BBR-NDN算法与ICP-NDN算法的对比

实验的基本设置如下。

1)实验拓扑以及链路参数如图4所示，图4a中，消费者Ci向生产者Pi请求数据，形成4条数据流。选取2条流用于模拟背景流量。在模拟背景流量时，C4以每秒800个Interest包的速率请求数据，持续150 s；C3以每秒500个Interest包的速率请求数据，并且在100 s后停止请求，模拟变化的背景流量；

图4 网络拓扑Fig.4 Network topology

2)Interest包的大小固定为37 Byte，Data包的大小固定为1 024 Byte；

3)网络中间节点不设置内容缓存。

实验结果如图5和图6所示。使用本算法，总流量迅速收敛到瓶颈带宽，并且往返时延稳定在物理链路延迟附近，表明传输基本收敛到Kleinrock最优工作点附近。

图5 存在背景流量场景下BBR-NDN与ICP-NDN吞吐量对比Fig.5 Comparison of throughputs between BBR-NDN and ICP-NDN under scenery with background traffic

图5表明，采用本算法，瓶颈链路的吞吐量收敛到瓶颈带宽所用的时间要明显小于ICP算法。并且在公平分享瓶颈带宽上，使用本算法时，数据流1和数据流2对应的曲线基本上是重合的，而使用ICP算法时，数据流1和数据流2在Data包的接收速率上差别明显，尤其是在背景流量突然减小(100 s时，模拟背景流量的其中一条数据流突然停止请求数据)，重新分配带宽时，不公平性进一步加剧，在图5中表现为数据流2的传输速率约为数据流1的2倍，差距进一步被拉大。

图6表明，本算法的传输往返时延一直很好地被稳定在稍高于理想往返时延处；使用ICP算法时，由于瓶颈链路的缓存长期处于高占用率的状态，传输往返时延明显大于理想往返时延。因此，基于BBR的NDN拥塞控制算法在保障低时延传输上明显优于ICP算法。它克服了基于丢包的拥塞控制算法为了充分利用瓶颈带宽而过度占用缓存、传输时延较长的缺点。

图6 存在背景流量场景下BBR-NDN与ICP-NDN传输往返时延与队列长度对比Fig.6 Comparison of round-trip time and queue length between BBR-NDN and ICP-NDN under scenery with background traffic

更换其他往返时延重复实验，算法的吞吐量以及往返时延的变化曲线的形状没有很大的变化，所以不再一一绘制其他曲线，只将结果展示在表1中。

表1表明，使用本算法时，实际往返时延与理想往返时延的比值都只稍大于1。ICP算法在充分利用带宽的同时对低时延的保障能力明显不如本算法。

基于BBR的NDN拥塞控制算法在高带宽下瓶颈链路吞吐量收敛到瓶颈带宽所需的时间较短，且基本不随往返时延的变化而变化，而ICP算法在同样条件下的收敛时间则随着往返时延的增大而明显增大，并且都大于本算法。这个结果表明，基于BBR的NDN拥塞控制算法在快速收敛到瓶颈带宽上明显优于ICP算法。

表1 BBR-NDN与ICP-NDN在平均往返时延以及收敛时间上对比结果Tab.1 Comparison of average round-trip time and convergence time between BBR-NDN and ICP-NDN

3.2 多瓶颈链路实验

多瓶颈链路实验基本设置如下。

1)实验拓扑以及链路参数如图4b所示，4条数据流的往返时延分别为240 ms，250 ms，250 ms，260 ms；

2)Interest包的大小固定为37 Byte，Data包的大小固定为1 024 Byte；

3)网络中间节点不设置内容缓存。

多瓶颈链路拓扑下的实验结果如图7所示。尽管网络中的数据流的往返时延存在差异，但是本算法仍能保证瓶颈链路的吞吐量能够快速收敛到瓶颈带宽，往返时延也能够稳定在稍高于理想往返时延附近。并且，在共享瓶颈链路带宽时，各流的传输速率在一定的范围内波动，但在平均传输速率上，流与流之间是基本公平的传输的。因此，在增加网络拓扑复杂度以及瓶颈链路的数量时，本算法仍能使数据流快速收敛到公平地共享带宽的状态，并能保障低时延传输。

4 总 结

基于BBR的NDN拥塞控制算法的核心策略是保证注入网络的流量在速率和总量上面能够匹配传输链路的能力。算法通过在接收端使用瓶颈带宽以及物理传输延迟这2个参数来描述传输链路的性能，形成以即时带宽和往返时延作为反馈信息的闭环控制方式，在不同状态下匹配不同的速率增益以及窗口增益，用计算得到的数据传输速率以及发送窗口来控制Interest包的发送速率，从而控制返回的Data包的速率，实现在充分利用网络链路带宽的同时保障低时延传输。

本算法和和传统的基于丢包的NDN拥塞控制算法相比有以下特点。首先，与传统的基于丢包的拥塞控制算法的由丢包事件触发的被动拥塞控制不同，本算法倾向于主动地发现拥塞以及可用带宽；其次，拥塞控制的反馈环传递的信息由即时带宽以及往返时延组成，采用窗口和速率双重控制的方式，两者相互协调，前者控制消费者注入网络的数据总量，后者控制信息流注入网络的速率；此外，本算法根据估算的发送速率以及所请求内容的大小来确定Interest包之间的发送间隔，实现了平滑的数据传输，减少了网络中的突发流量；最后，在不考虑网络内缓存以及多路径传输的情况下，本算法能使网络收敛到Kleinrock模型的最优工作点附近，该工作点能保证网络以瓶颈带宽进行传输的同时，减小中间路由节点的队列长度以及数据包所经历的传输时延。

图7 BBR-NDN在多瓶颈链路拓扑下的传输性能Fig.7 Transmission performance of BBR-NDN under multi-bottleneck link topology

本算法是在接收端实现的，没有引入中间节点的控制，然而中间节点位于网络内部，离拥塞的位置更近，能够更快地感知拥塞的存在以及预见拥塞的发生，对拥塞的调控更为迅速。同时，NDN在架构能够很好地支持逐跳的控制方式。因此，在当前的拥塞控制算法中引入逐跳控制和多路径转发，实现快速反馈以及将拥塞链路的流量分流到其他可用的路径上，是一个值的深入研究的地方。

由于路由器对Data包的缓存以及多路径传输的存在，端主机测量的往返时延存在多样性，难以被准确地估计[13]。由于依赖于测量的往返时延来估计链路的物理链路延迟，所以考虑缓存以及多路径传输的情况下，本算法在估计物理链路延迟的值时会存在较大的误差。因此，针对缓存以及多路径传输的特性对算法进行优化也是未来的一个研究点。

[1] ZHANG L,AFANASYEV A,BURKE J,et al.Named data networking[J].SIGCOMM Comput Commun Rev, 2014, 44(3): 66-73

[2] XYLOMENOS G,VERVERIDIS C,SIRIS V,et al.A Survey of Information-Centric Networking Research[J].IEEE Communications Surveys & Tutorials,2014, 16(2):1024-1049.

[3] KATO T, BANDAI M.Congestion control avoiding excessive rate reduction in named data network[C]//Consumer Communications & NETWORKING Conference.New York:IEEE Press, 2017:108-113.

[4] REN Y,LI J,SHI S, et al.Congestion control in named data networking-A survey[J]. Computer Communications, 2016(86):1-11.

[5] CARDWELL N,CHENG Y,GUNN C S, et al.BBR: Congestion-Based Congestion Control[J].Queue,2016, 14(5): 20-53.

[6] CAROFIGLIO G, GALLO M, MUSCARIELLO L.ICP: Design and evaluation of an Interest control protocol for content-centric networking[C]//Computer Communications Workshops. New York:IEEE Press, 2012:304-309.

[7] SALSANO S, DETTI A, CANCELLIERI M,et al.Transport-layer issues in information centric networks[C]//Edition of the Icn Workshop on Information-Centric NETWORKING.New York:ACM, 2012:19-24.

[8] SAINO L,COCORA C,PAVLOU G.CCTCP: A scalable receiver-driven congestion control protocol for content centric networking[C]//IEEE International Conference on Communications. New York:IEEE Press, 2013:3775-3780.

[9] CAROFIGLIO G,GALLO M,MUSCARIELLO L, et al.Multipath congestion control in content-centric networks[C]//Computer Communications Workshops. New York:IEEE Press, 2013:363-368.

[10] SCHNEIDER K,YI C,ZHANG B, et al.A Practical Congestion Control Scheme for Named Data Networking[C]//ACM Conference on Information-Centric NET WORKING. New York:ACM, 2016:21-30.

[11] ROZHNOVA N,FDIDA S.An extended Hop-by-hop interest shaping mechanism for content-centric networking[C]//Global Communications Conference.New York:IEEE Press, 2014.

[12] MASTORAKIS S, AFANASYEV A,MOISEENKO I,et al.ndnSIM 2: An updated NDN simulator for NS-3, NDN. [EB/OL]. (2016-11-11)[2017-09-22].http://ndnsim.net/2.4/.

[13] LEI K, HOU C, LI L,et al.A RCP-Based Congestion Control Protocol in Named Data Networking[C]//International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery. New York:IEEE Press, 2015:538-541.

(编辑：王敏琦)