命名数据网络中的一种主动拥塞控制机制研究

王亚东，张 悦，陈延祥，张 宇

1 引言

随着业务模式的快速发展，基于TCP/IP的体系结构逐渐暴露出诸多问题，比如可扩展性差、动态性差、安全可控性差等[1]。为了解决这些问题，命名数据网络(Named Data Networking，NDN)被提出并成为广泛研究的未来互联网体系架构[2]。NDN在处理封包是依据数据内容而非位置来命名，通过利用名称寻址并加入内容存储器结构，将内容和位置分离开，从根本上解决了当今TCP/IP网络中以主机为中心的通信模式和用户以内容为中心的网络需求之间的矛盾[3]。

空间网络不同于地面通信网，具有拓扑动态变化大、链路间歇性连接、高传输时延、传输数据率低、信道不对称等特点。目前空间容迟容断网络(Delay/Disruption Tolerant Networking， DTN)仍然使用单播协议进行端到端的传输，这样的传输方式无法满足载人航天探测任务中对数据传输实时性、数据量大、内容共享等需求，空间网络需要一种不同的网络架构来解决这些问题。而NDN按名字寻址，完全不依赖位置，路由请求和转发只依赖数据自身，请求者和提供者之间无需一直保持连接状态。这使得NDN有着极好的网络扩展性和对动态网络的适应性，能够为载人深空探测任务提供更安全有效、更可靠的通信服务；同时NDN引入节点缓存，使得卫星网络中因位置变化导致的传输中断无需重新建立连接，可以从临近节点匹配获取资源，原生支持网络多播和信息共享，有效节省数据传输开销，充分利用卫星网络资源。

空间网络对网络的可靠性要求较高，因此拥塞控制极为重要。拥塞的发生与网络自身的体系架构密切联系。拥塞控制机制的提出以特定的网络为前提。相比于TCP/IP网络，NDN中的节点设有持久性缓存，允许多路径传播和多播传播，这使得拥塞控制变得复杂[4]。在TCP/IP网络中拥塞控制机制是为端对端连接设计的，通过重复确认字符(Acknowledgement，ACK)和超时机制检测拥塞，通过基于滑动窗口的和式增加，积式减少(Additive Increase Multiplicative Decrease，AIMD)减小客户端注入网络的流量。而NDN中包的传播是多路径的，兴趣包对应的数据包可能会从不同节点返回，这些节点的远近会对返回数据的往返时延(Round-Trip Time，RTT)造成很大的影响。因此，在NDN中，无法对一个数据包设置一个合适的RTT值，单纯的超时机制无法满足NDN中拥塞检测及控制需求，需要更加准确的网络层控制算法来支持拥塞控制。

目前，现有NDN拥塞控制算法存在对先验知识的依赖，对网络状态的变化不够敏感，难以适用于空间网络这种拓扑高度动态，链路延迟大、误码率高等情况。基于这种现象，本文研究基于强化学习的NDN拥塞控制机制。已有一些研究将强化学习方法应用于传统TCP/IP网络的拥塞控制。王春茹等[5]运用强化学习的智能化控制方法设计了网络拥塞控制器，可以调节源端发送数据的速率，使可能发生拥塞的交换机缓冲区队列长度逼近设定值，从而减少了拥塞的发生。李鑫[6]基于强化学习理论中的Q-学习方法设计了主动队列管理算法。控制器学习TCP/IP网络中状态-动作对所对应的Q-函数值，并利用反映了Q-函数值与当前网络状态联系紧密程度的可信度值来调节学习率。

本文针对NDN体系架构，以最小时延为目标，在考虑NDN中的网内缓存、多路径转发，并不对链路容量或数据包大小做任何假设的情况下，结合强化学习中的 Sarsa(λ)算法，充分利用NDN中路由节点的计算和学习能力，设计智能的动态转发策略，以实现对NDN的拥塞控制功能。

2 基于强化学习的NDN拥塞控制方法设计

良好的转发策略可以自主选择合适的链路进行数据转发，能在很大程度上预先规避拥塞链路，并在拥塞现象发生后有效地缓解拥塞。本文从转发策略的角度出发，讨论容迟容断命名数据网络中的拥塞控制问题。在考虑网内缓存、多路径转发，并不对链路容量或数据包大小做任何假设的情况下，将NDN中路由节点选择端口转发兴趣包的过程，建模为强化学习中一个状态选择执行动作转移到另一个状态的过程，设计更加实际可行的转发策略。针对NDN应用的特殊网络环境，本文选择最小时延为目标，结合强化学习中的Sarsa(λ)算法，在原有转发策略的基础上设计智能的转发策略，以实现拥塞控制的目的。

2.1 模型的建立与分析

在考虑缓存及多路径路由因素下，网络拥塞模型难以建立，而时序差分学习无需模型，直接从经验中学习。时序差分(Temporal Difference，TD)算法中应用较广的有Q-learning和Sarsa策略[7]。然而结合资格迹后，由于Watkins[8]的Q(λ)算法具有截断有效序列的问题，而改进的 Peng的Q(λ)算法[9]很难实现，本文使用Sarsa(λ)算法实现NDN中网络包的智能转发。

将路由节点转发兴趣包到相应数据包返回该节点的时间记为响应时间RTTr。需要注意的是，RTTr越小越好，因此计算Q值时，将-RTTr作为即时回报。在NDN环境中，节点选择Q值最大的链路，一方面可以在总体上减少用户收到需求内容的时间，提高用户体验；另一方面实现了主动避免拥塞，路由节点转发兴趣包时优先选择网络时延短的，即非拥塞的链路，避免再向拥塞链路注入更多的流量。本文将Q值为转发策略的依据，采用结合资格迹的Sarsa算法——Sarsa(λ)算法求解最佳策略。

所述模型建立方法如下：

1)利用NDN中路由节点的学习和计算能力，将路由节点看作智能体agent；

2)将路由节点向不同的端口转发兴趣包的过程作为agent选择执行动作的过程，多个可转发的端口对应多个可执行的动作；

3)将兴趣包从一个路由节点通过选择端口转发到另一个路由节点的过程，映射为agent将兴趣包从一个状态通过选择相应的动作转移到另一个状态的过程；

4)NDN中原有的数据包结构如图1所示。本文在原有结构基础上，扩展了时间戳字段，如图2所示。每个路由节点选择一个端口转发兴趣包后，由兴趣包发出到对应数据包返回的时间差RTTr得到反馈给 agent的立即回报值 r(s，a)，RTTr通过相应的数据包返回时携带的时间戳信息计算得到。时间戳通过向数据包结构中添加新的字段项以实现携带。路由节点的FIB表中每一个前缀对应一个条目，条目中的每一个端口都有一个度量条目(如链路开销等)，可以存储标准化的度量信息。本文将Q值加入原有的度量条目中，修改后的FIB条目如图3所示；

5)记状态空间为 S={St0，St0+1，…，ST-1，ST}，其中，ST表示T时刻agent的状态，状态指节点将兴趣包从当前节点发送到存储相应数据的节点；记动作集 A={At0，At0+1，…，AT-1，AT}， 表示不同状态下所选择的动作；一个状态的动作集记为A(s)={a1，a2...，an-1，an}， 表示兴趣包到达一个路由节点后可选的n个转发端口；路由节点为每一个前缀下的每一个转发端口维护一个动作值Q(s，a)， 动作值更新公式见式(1)、式(2)[7]。

图1 原有数据包结构Fig.1 Original data packet structure

图2 修改后的数据包结构Fig.2 Modified data packet structure

图3 修改后的FIB表项Fig.3 Modified FIB table entries

其中，s为agent的当前状态，a为当前状态下选择的动作，β为学习速率，δt为误差，r(s，a)为回报值，γ为折扣率，λ为迹衰减参数，St为t时刻agent的状态，At表示t时刻agent的动作，Qt(s，a)为 t时刻状态-动作对 (s，a) 的动作值，Et(s，a) 为 t时刻状态-动作对 (s，a) 的资格迹，资格迹的使用可以提升算法的效率。

2.2 包转发策略的实现

采用结合资格迹的Sarsa算法——Sarsa(λ)算法求解最佳策略。在更新策略的方法上，采用针对现有动作值的贪婪策略：ε-greedy策略，即，以1-ε的概率选择最佳动作，以ε的概率选择其他非贪婪动作[10]。转发策略分为初始化阶段和应用及持续探索阶段。

1)初始化阶段：获得初始Q值。当路由节点收到兴趣包后，向所有可转发的端口发送兴趣包，获得每个端口的初始Q值；

2)应用及持续探索阶段：根据初始化阶段得到的初始Q值，按照贪婪策略进行探索并持续更新Q值。当得到初始Q值后，路由节点依据ε-greedy策略进行探索。路由节点向端口转发兴趣包，以1-ε的概率选择最佳Q值端口，以ε的概率选择其他端口以保证持续性探索，在数据包返回的过程中不断更新Q值。当端口超时后，将公式(1)中的δt设置为一个不小于108的常量，这样Q值会很大，作为超时的惩罚机制。

包转发策略的具体实施流程如下(图4)：

1)路由节点判断接收的包类型，若为兴趣包，转步骤2，若为数据包，转步骤7；

2)检查自身缓存中是否有与该兴趣包匹配的数据，若存在，则从该兴趣包到达的接口返回与之匹配的数据包，结束；否则直接转步骤3；

3)在FIB中查找可能的下一跳，若无下一跳，返回 NACK-NOROUTE(查找路由失败)，结束；有则转步骤4；

4)判断当前状态，若为初始化阶段，转步骤5；若为应用即持续探索阶段，则转步骤6；

5)向所有可转发的端口发送兴趣包，获得每个端口的初始Q值，结束；

6)依据ε-greedy策略随机选择是否贪婪，贪婪则选择可能的下一跳中Q值最小的节点转发兴趣包，结束；不贪婪则在可能的下一跳中随机选择除Q值最小以外的节点转发兴趣包，结束；

7)查询PIT表，若无对应条目，则丢弃该数据包，结束；否则根据NDN数据包的转发流程转发数据包，转步骤8；

8)从数据包中提取信息并更新对应端口的Q值，结束。

图4 转发策略流程图Fig.4 Flow chart of forwarding strategy

采用上述方法应用于NDN中，能够在很大程度上避免网络拥塞的发生。

3 仿真与结果

本文提出的拥塞控制机制在Linux操作系统下，基于ns-3的ndnSIM仿真平台进行性能测试[11]。网络拓扑结构如图5所示。仿真设置中，共有9个网路节点，其中包括4个内容请求者(Consumer)、4个路由器为中间转发节点(Router)和1个内容生产者(Producer)。其中每条链路的带宽和延迟设置如表1所示。由表1可以看出，Router1和Router2分别有一条相对较好和相对较差的输出链路：Router1-Router4为较好的输出链路，相较Router1-Router3来说，此链路具有更大的带宽和更小的延迟，单位时间传输的数据更多。Router2对应的2条输出链路同理，但总体上优于Router1的输出链路。

图5 拓扑结构Fig.5 Topological structure

表1 链路设置表Table 1 Link setting table

本文将提出的智能转发策略与最佳路由算法(Best Route)、多路径转发算法(Multicast)以及请求转发算法(Request Forwarding)进行对比。仿真硬件为ubuntu16.04LTS操作系统、内存为15.6 GB，Inter Core i7-4749 CPU@3.60GHz∗8，硬盘为500 GB的SSD。仿真在ndnSIM2.6环境下进行，依次将上述算法记为 Sarsa(λ)、BestRoute、Multicast和 RFStrategy。 在 Sarsa(λ)算法中，设学习速率β=0.6，折扣率γ=0.5，迹衰减参数 λ=0.5，概率 ε=0.05，仿真实验的运行时间为100 s。

3.1 数据包交付率

数据包交付率指消费者发出的兴趣请求被数据包响应的比例。设消费者发送兴趣包的速率为100 Packets/s，交付率随链路误码率的变化结果如图6所示。可以看出，随着链路误码率增大，4种转发策略的交付率都会降低，这是因为误码率增大导致网络丢包增多，一部分数据包无法回到消费者。其中，Best Route根据最小跳数选择最佳路径，无法根据链路的实际情况进行调整选择，整体性能最差。Multicast算法会将兴趣包转发到所有记录的端口，只要有一条较好的链路，就可以完成交付任务，对链路误码率不敏感，因此整体交付性能最好；但这种算法没有拥塞控制机制，会大量消耗链路带宽。基于Sarsa(λ)的转发策略和RF算法都是动态转发策略：RF算法基于每个端口的等待响应的兴趣包个数为端口分配权重，再根据权重随机选择转发端口，考虑了数据包是否返回和返回的比例；基于Sarsa(λ)的转发策略不仅考虑了数据包返回的情况，还隐性地考虑到了链路状态，交付性能优于RF算法。

图6 数据包交付率随链路误码率的变化结果Fig.6 Changes of packet delivery rate with BER

设链路误码率为0.3，数据包交付率随负载的变化结果如图7所示。负载越大，网络中的流量越大，大量的网包会加重网络负荷，导致网络拥塞的发生，此时所有算法的性能都会下降。Multicast多端口转发兴趣包，第一个数据包从某条链路返回后，其他链路仍然会返回数据包，而这些重复的数据包会被丢弃，造成带宽的极大浪费；Multicast算法也因此对链路可用带宽较敏感。网络中数据包的不断增多可以等价为链路可用带宽的减小，此时，Multicast的性能会下降。从图7中可看出，当负载较小时，Multicast的性能优于Sarsa(λ)，当负载不断增大时，Multicast的性能下降较快，落于 Sarsa(λ)之后。RF的交付率排在Multicast之后，Best Route交付率最低。

图7 数据包交付率随负载的变化结果Fig.7 Changes of packet delivery rate with load

3.2 丢包率

网络层的丢包率可以直接反应网络数据传输的可靠性。丢包率随误码率的变化结果如图8所示，随负载的变化结果如图9所示。可见，虽然Multicast的数据交付率很高，其丢包率也非常高，没有任何拥塞控制的机制。基于Sarsa(λ)的转发策略和RF能主动避开拥塞和故障的链路，从而极大减小了链路丢包数量，但Sarsa(λ)的丢包率更小。Best Route丢包率低于Multicast，但由于无法感知链路的状态，可能会选择拥塞较严重的端口转发兴趣包，丢包数量较多。

图8 丢包率随误码率的变化结果Fig.8 Changes of packet loss rate with BER

3.3 平均时延

图9 丢包率随负载的变化结果Fig.9 Changes of packet loss rate with load

平均时延即消费者发送兴趣包后，接收到数据包的平均响应时间，是网络服务质量的重要指标之一。平均时延随误码率的变化结果如图10所示，随负载的变化结果如图 11所示。基于Sarsa(λ)的转发策略以最小时延为目标，选择传输时延最小的路径转发兴趣包，使得最终的平均时延最小。图10中，Multicast的平均时延最优，同数据包交付性能，只要有一条链路可用，数据包就可以返回，因此减小了用户的响应时间。但图11中，负载增大后，由于网络中数据包的大量增加，Multicast性能下降，其平均时延也增长较迅速，Sarsa(λ)的平均时延在整体上变为最优。RF在其选择端口的标准中，主要考虑数据包返回的比例而不是快慢，平均时延较高。Best Route不考虑链路时延的问题，时延最大。

由以上对比可知，本文提出的智能转发策略能有效增加网络的数据递交率，减少丢包数量和网络平均时延，除在平均时延随误码率变化的效果上略低于Multicast算法外，在其他方面整体均优于其他3种算法。

图10 平均时延随误码率的变化结果Fig.10 Changes of average delay variation with BER

图11 平均时延随负载的变化结果Fig.11 Changes of average delay variation with load

4 结论

1)本文将强化学习算法应用到NDN的转发策略中，实现智能的动态转发策略，以主动避免和缓解拥塞。将资格迹与在线时序差分策略结合，以最小时延为目标，提出了基于Sarsa(λ)的转发策略；

2)在 ndnsim平台上仿真，与已有的 Best route算法、Multicast算法和RF算法进行比较，仿真结果表明，该算法能有效增加网络的数据递交率，减小丢包数量和网络平均时延，除在平均时延随误码率变化的效果上略低于Multicast算法外，在其他方面整体均优于其他3种算法；

3)本文提出的转发策略很大程度上避免网络拥塞的发生，并在拥塞发生时及时地发现问题链路，选择链路状态良好的路径转发数据，有效地减少拥塞。