NDN逐跳拥塞控制

NDN网络中==逐跳拥塞==控制机制综述

NDN传输机制：接收方驱动(消费者端，下游)，一兴趣一数据，中心节点缓存，多源，多路径。

在NDN体系结构中，数据包是拥塞的主要原因，因为它们比兴趣包更大。为了避免拥塞，之前的方法分为三类：

• 基于接收器的方法；
• 逐跳法；
• 混合方法。

NDN拥塞控制的优势：可以使用中间节点来控制拥塞，中间路由器可以通过管理PIT的大小来处理流量负载，因此，NDN体系结构很容易实现逐跳拥塞控制机制。通过调节发送兴趣包的速率来控制接收方返回数据包的速率

逐跳控制的基本思想是，每个中间节点检测拥塞并调整其兴趣包发送速率，以调整返回数据包的传输速率。主要有两种方式：==基于速率的逐跳拥塞控制==和==基于窗口的逐跳拥塞控制==。

A：基于速率的机制

基于速率的机制允许用户和路由器根据本地信息（如链路带宽）控制发送兴趣包的速率。下图显示了基于速率的逐跳控制的基本思想。中间节点Ri通过监视传入数据队列的长度来确定其拥塞状态。路由器根据拥塞状态决定成形速率是增加还是减少。

主要的考量因素：队列占有率，队列长度，队列滞留时间

HoBHIS：使用数据队列占用率来计算成形率，通过计时器过期定期把过期的兴趣包清除，降低队列占有率和成形率(队列占有率)

HIS：使用中间路由器来监控传入兴趣包，并根据最佳预期兴趣包与实际传入兴趣包速率之间的差异来调整兴趣包发送率。

HBH：监视每个中间节点的传出队列的占用情况，以识别拥塞。如果队列大小达到其指定的最小或最大阈值，将向路由器和下游消费者发送明确通知（指定增加或减少速率）

PCON：使用CoDel AQM[11]检测拥塞。CoDel测量数据包队列时间，并通过显式标记某些数据包将此状态发送给消费者。PCON通过将后续兴趣包部分转移到其他非拥堵路线来应对拥堵，而消费者则通过降低兴趣包速率来应对拥塞。

CC：消除了连续NACK数据包导致的兴趣包速率过度降低。该方法设计用于在拥塞速率降低后，直到速率降低有效为止，不修改NACK数据包的兴趣包速率。

B：基于窗口的机制

基于窗口的机制允许使用者在窗口大小的限制内连续发送兴趣包。而窗口的大小必须根据带宽和往返时间（RTT）确定。这种方法的一个示例如[3]所示，其中介绍了==使用H-ACK进行每跳兴趣传输的窗口大小控制==，以及在窗口关闭时存储兴趣包的队列。这种方法允许您根据与每个流和RTT链路相关联的兴趣发送率来确定特定流的兴趣窗口的大小，从而允许数据分组利用其最大链路带宽。

Fi. 3.说明了一个典型的基于窗口的模型。首先，router i − 1以其窗口的大小连续发送兴趣包。当 router i 获得这些兴趣包时，它会将它们保存在兴趣队列中，因为它的router i + 1 的窗口被关闭。接下来，router i 在router i + 1处获取一个H-ACK包，并在窗口大小内发送排队的兴趣包。以这种方式，每个路由器将发送感兴趣的数据包，以便数据包将使用最大链路带宽 [3]。

总结：

基于速率的方法通过监视兴趣或数据包的队列长度来检测拥塞，而基于窗口的方法通过每个流的每跳中的兴趣窗口大小来检测拥堵。

总的来说，基于窗口的机制的吞吐量小于基于速率的机制的吞吐率。因此，==基于速率的方法被认为适用于NDN==。

机制	拥塞检测方法	优点	缺点
HOBHIS[6]	监控数据队列长度	它通过在向上游转发之前调整路由器的兴趣来防止拥塞。	与公平性问题和拥塞处理时间相关的缺陷。
HIS[8]	监控传入兴趣包速率	避免拥塞并优化网络资源的使用。	不考虑未知链路带宽的可能性，并未说明这种情况下的行为。
NACK[7]	监控发送兴趣队列	可以在管理黑洞劫持、链路故障和网络拥塞方面提供高性能。	由于NACK分组的传播延迟，兴趣发送速率被过度降低。
HWCC[3]	每个流的每跳的兴趣窗口大小	数据分组可以有效地利用网络带宽。 达到高吞吐量性能。因此，最大限度地提高了公平性，同时有效地避免了拥塞。	为每个流分离窗口大小。忽略队列大小。
PCON[10]	测量分组排队时间	达到更高的总吞吐量，可以适应IP隧道和无线链路的演进容量。	花更多时间将传输百分比调整到最佳水平，以确定最合适的接口。
HBH[4]	每个路由器监视其输出队列	对于NDN节点，它避免了兴趣输出面的拥塞，并在所有活动输入面之间公平地共享兴趣输出链路容量。	消除响应延迟参数，不考虑多生产者。
IRNA[5]	监控传出兴趣队列占用率	它可以在缓冲区达到其极限之前防止拥塞，确保每个输入面的公平分配，并为同时使用的用户提供正确的带宽利用率	消除响应延迟参数，不考虑多生产者。
CC[9]	监控发送兴趣队列	消除了由连续的否定确认分组导致的利率的过度降低，并实现了高吞吐量。	与公平性相关的缺陷

PCON：一种实用的命名数据网络拥塞控制方案

0. 摘要：

传统的拥塞控制机制是为端到端连接设计的，不适合命名数据网络（NDN）体系结构，在NDN体系结构中，可以从多个源和通过多个路径检索内容。为了充分利用NDN架构，拥塞控制方案必须考虑网络内缓存、多路径转发和多播数据传递的影响。此外，解决方案不得假设已知==链路带宽或数据包大小==。

PCON基于CoDel AQM（通过测量数据包排队时间）扩展的主动队列管理（AQM）方案检测其本地链路上的拥塞。然后监控输出链路上的队列，通过显式标记某些数据包向消费者发送信号，以便下游路由器可以选择其他路径或者降低兴趣包发送速率。

CoDel CoDel的意思解释|CoDel是什么意思 -我酷百科 (wosku.com)

1. 背景：

传统的TCP拥塞控制基于两个端点之间建立的连接。发送方通过测量往返时间（RTT）或分组丢失来检测拥塞，然后相应地调整其发送速率。由于NDN的多径，多源特性，基于RTT的超时成为不可靠的拥塞指标

之前的很多研究都是假设已知或可预测的链路带宽和数据块大小，但实际这些参数可能不知道。本文的方法不需要已知或可预测的链路带宽和数据块大小。

2. 设计原理

考量的因素：NDN相较IP的独特特性

1. 多个路径和端点

消除了两个端点之间连接的概念。不知道下一个数据包来自何处，这导致了三个问题：

• 第一次之后到达的兴趣（也就是之前请求过的兴趣）看到的RTT短，这样可能设置的RTO(恢复时间目标，超过这个时间就重传)设置（meanRTT+4\*varRTT）的也短。这样导致发送速率降低，重传增加。

  解决方法：设置更高的最小RTO，但这也增加了检测数据包丢失的时间

  PCON通过将高的最小RTO与用于快速反应的显式拥塞信令相结合，避免了这种困境。

• 消费者的最佳拥塞窗口（定义为带宽延迟乘积–BDP）可能会因缓存多样性而变化。如果从较远的缓存获取数据，此路径有较低的BDP(带宽延时积)，兴趣包可能溢出队列

  解决方法：通过使缓冲区足够大以处理临时流量突发，并在缓冲区达到其极限之前使用CoDel AQM方案检测和发送拥塞信号来缓解此问题

• 消费者不能再使用接收到的数据包（无序传送）的序列号间隔作为数据包丢失的标志来判断拥塞，因为无序到达可能是由于从不同缓存或沿多条路径接收数据造成的。

2. 基于拉动的数据检索和HBH流量平衡。

NDN采用兴趣包拉动数据包的机制。PCON使用==分组排队时间==[14]和==本地链路丢失检测==（第3.5节）作为更可靠的拥塞指标，而不是试图估计链路带宽或预期负载。

3. 不同的部署场景

4.流语义和公平性

流语义指的是需要对内容对象的定义达成全局协议，比如层编码视频，是将整个视频看作一个整体，还是每一部分看作一块内容。

3. 系统设计

基本原则：1）通过采用AQM进行早期拥塞检测，2）显式拥塞信令，3）利用多径转发，4）特别考虑IP覆盖和无线链路。

如图1所示，PCON由五个组件组成：

• 拥塞检测（3.1）：每个节点通过监控其输出队列来本地检测拥塞。
• 拥塞信令（3.2）：在检测到拥塞后，节点标记数据包以通知下游路由器和消费者。
• 消费者兴趣包速率调整（3.3）：终端消费者通过调整其兴趣包的发送率对拥堵信号作出反应。
• 多径转发（3.4）：下游路由器通过调整流量分配比对拥塞信号做出反应。
• 本地链路丢失检测（3.5）：在无线和IP覆盖链路上，我们本地检测数据包丢失，并使用NACK将其发送回。

3.1 拥塞检测

我们通过监测==每个路由器的输出队列==来检测拥塞，而不是像IP试图通过监测数据包丢失或往返时间来推断消费者的拥塞

采用AQM(主动队列管理)的CoDel方案。CoDel测量每个数据包在其输出链路上的排队延迟（“停留时间”）。如果一段时间内（默认：100ms）的最小停留时间超过阈值（默认：5ms），则认为该链路拥塞。

优点：队列延迟隐含地考虑了链路带宽（对于固定队列大小，较高的带宽导致较低的队列延迟）

缺点：这种方式不易实现，测量队列长度的方法更好实现，且更精准。

我们通过监测本地链路上的数据包丢失来推断拥塞级别，数据包丢失导致越来越大的PIT，可能会溢出路由器的内存。

解决方法：可以向下游发送过度增长的PIT状态信号，以减少传入兴趣的数量，这个是创新点，就是检测PIT的大小是否超过设定阈值，超过了就通知消费端降速。

3.2 拥塞信令

在路由器检测到其一个出站端口链路拥塞后，它会向消费者和路径上的所有路由器发出信号。通过标记NDN数据包表示拥塞。==标记数越多，标记间隔时间越短==(标记间隔从1.1*码间隔（110ms）开始，并与标记数的平方根成反比减少)

一个标记的数据包会分支到每个请求它的消费者，这将降低他们的速率。

3.3 消费者兴趣包速率调整

在未标记数据包上增加发送速率；而在收到标记数据包、NACK和超时状况时应减少发送兴趣的速率。我们通过应用“基于TCP SACK的保守丢失恢复算法”[3]来防止这种过度调整（参见算法1）：消费者每RTT最多执行一个窗口减少。对于IP底层网络中的超时（由缓冲区溢出引起）和缓冲区溢出导致的NACK采取这种方法。

窗口减少不仅由超时触发(超时可能是由于队列溢出)，还由包标记（类似于TCP ECN标记）和NACK触发。

3.4 多路径转发

设计多径转发策略的目标是最大化最终用户吞吐量，同时尽可能降低网络成本。

• 如果最短路径可以满足需求，则不应在其他路径上分割流量。
• 如果需求超过最短路径的容量，则应在下一条最短路径上递增分布。
• 如果需求超过所有可用链路容量之和，则应以完全占用带宽的方式进行拆分，而不考虑路径长度。

基于接收到的拥塞标记设计转发自适应：

对于每个FIB前缀，PCON保持每个接口的转发百分比，对于最短路径（由路由协议给出）初始化为100%，对于所有其他路径初始化为0%。然后，对于每个标记的数据包，它减少传入接口的转发百分比，同时将所有其他接口的转发百分比增加到相等的量：

fwPerc（F）是当前面的转发百分比，CHANGE_PERC是一个固定参数，它在将转发比率调整到最佳值的速度（越高越好）和围绕该值振荡的程度（越低越好）之间进行权衡。

P1是最短路径，P3是最长路径

对于多路径转发，靠近内容存储库的路由器比靠近消费者的路由器看到更少的拥塞标记，因为后者看到来自更多链路的标记。为了避免这些路由器的过度调整，并解决更靠近发生拥塞的地方的拥塞，我们在远离拥塞链路的路由器上调整转发比：f（距离）≥ 1

实际上就是上游路由器f（距离）设置的大，对应的reduction小，阻塞调控程度小。越靠近消费者，对拥塞反应越强烈

对于PCON，消费者对每个拥塞标记的反应比路由器更强烈（例如，通过将cwnd减半），

3.5本地链路丢失检测

到目前为止所描述的设计假设网络中数据包丢失的唯一原因是路由器缓冲区溢出

3.6高度拥挤的路段

在某些情况下，PCON无法防止特定链路上的拥塞：拥塞可能是由无响应的消费者、IP交叉流量、软件故障、PIT入口溢出或硬件限制引起的。即使在这些情况下我们无法避免拥塞，我们仍然可以通过在转发策略中禁用这些“高度拥塞”的链路来避免使用它们。

基于队列大小反馈的有效NDN拥塞控制

0. 摘要

在NDN-QSF中，转发器估计上行带宽并使用队列大小作为拥塞反馈，以通知下行路由器限制感兴趣的传输速率。

1. 背景

数据多播、网络缓存和多路径转发是提高计算机网络中数据对象检索性能的理想功能。

当多个消费者请求相同数据时，数据多播和网络内缓存减少了网络流量，多路径转发探索并利用所有可用的网络资源以进一步提高吞吐量。

NDN自动支持数据多播（通过兴趣聚合）和网络缓存。

当数据传输不再沿着单一路径进行时，TCP/IP拥塞控制中使用的单一路径的“排队延迟”和“带宽延迟积”等概念不再适用

本工作旨在为NDN转发器设计==具有拥塞控制的多路径转发==，1）利用多个转发路径最大化网络吞吐量，2）控制拥塞，并具有低排队延迟。这两个目标都应该在存在网络内缓存和多路径转发的情况下实现。

模拟侧重于一个或多个消费者获取相同数据对象的场景，评估指标衡量消费者吞吐量和网络拥塞水平。

本文贡献：

• 使用模拟研究来调查网络内缓存和多路径转发对终端测量的影响，并观察到这两个特性使得终端消费者难以准确检测网络拥塞。

• 设计了一种拥塞控制算法NDN-QSF，该算法==使用上游队列大小作为拥塞反馈==，并逐跳控制拥塞，以有效控制NDN中的拥塞。

• 为了使多径转发决策适应网络负载，我们扩展了NDN-QSF，以基于上游拥塞反馈做出多径转发决定。

• 我们将NDN-QSF实施为NFD的转发策略(NDN有多种转发策略)，并通过ndnSIM模拟对其进行评估。

2. 相关工作

MIRCC：该设计基于瓶颈转发器检测拥塞并为每个消费者分配每流发送速率的思想，消费者按照分配的速率发送每个流的兴趣。

VIP：使用队列大小信息作为对邻居的反馈，以检测拥塞并做出多路径转发决策。

NDN-QSF：与PCON和VIP类似，将队列大小相关信息作为拥塞反馈发送给消费者。与MIRCC分享了直接控制兴趣包速率和 使用智能转发器与哑巴消费者 的想法。

NDN-QSF是逐跳拥塞检测，避免了需要知道网络中哪一个端点可以满足数据的假设。

3 NDN影响消费者的本地拥塞测量

NDN难以像IP使用本地RTT和速率测量来检测网络拥塞。

3.1 多路径转发发影响

消费者可以使用受多路径转发影响的平均RTT，但是不精准。当定向到长延迟路径的流量部分增加时，消费者实际吞吐量低于其兴趣包发送速率。

3.2 网络内缓存对消费者测量的影响

消费者2最初将由缓存满足，并最终耗尽缓存，并由生产者满足，因为它比消费者1更快地请求数据。

当C2从向缓存请求数据到向Consumer请求数据的转变中，RTT增大，可能导致错误的拥塞检测。

3.3 误读测量时错误检测拥塞

NDN消费者无法基于其本地RTT和数据到达率测量可靠地检测拥塞。相反，我们需要使用转发器可以提供的信息来推断拥塞。因此使用转发器的==本地排队信息作为下游拥塞信号==。

4.缓存存在时的有效拥塞控制

所提出的转发过程基于现有的NDN转发管道，添加了按名称前缀的==兴趣排队(Interest Queue)、速率限制(Rate Limit Calculation)、测量(Measurement)、以及拥塞反馈模块(Feedback)==。

在设计中，

• 每个转发器的兴趣和数据队列大小作为拥塞反馈发送到下游。(Queue-Size Feedback Update)
• 每个转发器保持对生产者可用带宽的每个上行估计。(Upstream Measurement Update)
• 从下游接收的具有相同名称前缀的所有感兴趣分组被放入兴趣包队列(Interest Queue)。从上游的估计带宽和特定名称前缀的队列大小计算名称前缀朝向上游的速率限制。(Rate Limit Calculation)
• 当上游拥塞反馈显示大队列时，应降低速率限制以耗尽上游队列。然后，转发策略向上游转发兴趣包队列中的兴趣，同时确保遵守兴趣包限制。(Queue-Size Feedback Update)

4.1 队列和队列大小反馈

==队列大小==反馈作为拥塞信号向下游传递。反馈通过在每个数据包上进行背负来传输。

队列大小反馈的值由当前转发器处的兴趣队列和数据队列大小以及与数据分组相对应的兴趣分组是否命中高速缓存或被聚集来确定

兴趣包未命中缓存或被聚集，对应的数据包将具有拥塞反馈值。

兴趣包命中缓存或被聚集，反馈下游的数据队列大小。

由于队列大小反馈被背负在每个数据包上，转发器保持最小的兴趣包发送速率，以保持上游队列大小的最新视图。

4.2 估计上行带宽

每个转发器估计通过每个上游到生产者的带宽。使用每个上游的数据到达率和队列大小反馈来估计该带宽。

利用每个上游的队列大小和数据到达率信息，上游的带宽被估计为其队列建立时上游的数据到达率。(感觉就是最大的数据到达速率所谓带宽估计值)

• 如果队列大小 > queue_THRESHOLD，则将估计带宽设置为当前数据到达率。
• 如果数据到达速率 > 估计带宽，则将带宽设置为当前数据到达速率。

4.3 限制速率的计算

转发代理对向上游发包的速率限制进行定期调整。ROUND_LENGTH参数用于定义调整周期。

此文用网络RTT作为ROUND_LENGTH，u应该对应的是一条upstream路径，queueSize是上游队列的大小

4.3.1 拥塞控制

通过调整速率限制，逐跳控制拥塞。检测上游队列的大小是否高于阈值。如果是，就限制向上游发送的速率。

QUEUE_THRESHOLD参数表示稳态队列大小的预期数量，5效果最好

每一轮，上游队列被耗尽bandwidth × round_length × (1 − MD_FACTOR)

拥塞控制触发时，想拥塞上游发送的兴趣包速率降低，下游兴趣包可能排队导致下游阻塞，此时应该告知消费者减慢发包速率。

4.3.2 速率探测

允许转发器通过以高于其估计带宽的速率向上游发送来校正其低估的上游带宽，（在queueSize(u) < QUEUE_THRESHOLD这个分支）

当上游已经拥塞时，当前数据到达率应该是其带宽的最新估计，（进入前面的else分支，rate_limit[u] <-- bandwidth[u]

4.4 用户拥塞控制

本文使用了一个天真的消费者，在第一跳转发器处保持了一个大队列

4.5 通过公平排队

公平排队可以是一个有用的原语，与NDN-QSF一起使用，以提供公平性。

5多路径转发

使用“上游队列大小反馈”的NDN-QSF在多径转发下是有效的。此外拥塞控制算法估计的带宽可用于指导多路径之间的流量分割。因此可以扩展算法，做出多路径转发决策

• 对于转发到多条路径的流量，估计每个上游的带宽，并计算每个上游的速率限制，以便在控制拥塞的同时向多条路径分割感兴趣的分组。( congestion control )
• 转发器通过增加其速率限制来探测上游，直到探测的上游具有高于阈值的队列大小。( rate_limit * 1.05 )
• 当被探测的上游已建立队列时，将选择另一个没有大队列的上游进行后续调整。(selectUpstream2Probe)
• 后续调整对应Avoid Unnecessary Contentions，选出来的Upstream2Probe调大rate_limit，没选出来的也就是队列长的减小rate_limit

此方法与之前的Rate-Limit算法有些不同。

5.2 转发策略

转发策略负责将输入兴趣队列中的兴趣分割到不同的上游转发器，同时遵守每个上游的速率限制。

6 仿真

存在缓存时的拥塞控制，存在多路径转发时的拥塞控制，共享同一瓶颈链路的多个转发路径，多路径转发的吞吐量最大化，高速缓存和多路径转发下的拥塞控制，具有公平排队的多个消费者。

7 讨论

NDN拥塞控制需要网络反馈。NDN的网络内缓存和多路径转发有助于扩展数据传输并最大化整体网络吞吐量。

8 结论

本文研究了多路径转发和网络内缓存对拥塞控制的影响，使用转发器的本地队列大小作为对下游的拥塞反馈。

设计了一个拥塞控制解决方案，NDN-QSF，它可以在存在网络缓存的情况下工作。拥塞控制设计是逐跳的，转发器的本地队列大小作为对下游的拥塞反馈。转发器通过其上行链路测量可用带宽，并基于估计的上行带宽和拥塞反馈来限制兴趣包传输速率。然后将NDN-QSF应用到多路径转发环境中，并将其扩展为多路径转发。