一种面向数据中心网络编码的交换机/路由器缓存队列管理方法

摘要

本发明公开了一种面向数据中心网络编码的交换机/路由器缓存队列管理方法。当交换机或者路由器收到数据报文时，判断其缓存队列中是否存在编码报文。若此时缓存队列中没有编码报文，则将该数据报文追加存储在缓存队列队尾；否则，则将该数据报文覆盖缓存队列中的编码报文。当收到编码报文时，则将该编码报文存储在缓存队列队尾。本发明避免了编码报文增加数据报文的缓存排队延迟，同时又利用了编码报文恢复乱序或者丢失的数据报文，最终提升了数据中心的网络性能。

权利要求

1.一种面向数据中心网络编码的交换机/路由器缓存队列管理方法，其特征在于，包括以下步骤：步骤一：设置交换机/路由器缓存队列中的开始覆盖位置K；

步骤二：交换机/路由器在收到新报文后，判断该新报文的类型，其中类型包括数据报文和编码报文；若为数据报文，转步骤三；否则，转步骤四；

步骤三：交换机/路由器判断其缓存队列中第K个报文之后是否有编码报文；若有，则将该新报文替换最后一个编码报文存储至缓存队列中；否则，转步骤四；

步骤四：交换机/路由器判断其缓存队列是否已满，若未满则把该新报文存储至缓存队列队尾，否则丢弃该新报文。

2.根据权利要求1所述的面向数据中心网络编码的交换机/路由器缓存队列管理方法，其特征在于，所述步骤一中，若交换机/路由器的出口带宽为1Gbps，将K设置为20，若交换机/路由器的出口带宽为10Gbps，将K设置为65，若交换机/路由器的出口带宽为其它值，则将K设置为交换机/路由器的带宽时延积的1/7。

3.根据权利要求1所述的面向数据中心网络编码的交换机/路由器缓存队列管理方法，其特征在于，所述步骤二中，交换机/路由器收到新报文后，通过解析新报文头部的协议字段判断报文的类型。

4.根据权利要求1所述的面向数据中心网络编码的交换机/路由器缓存队列管理方法，其特征在于，所述步骤三中，交换机/路由器从前往后遍历其缓存队列，判断是否是编码报文；若最后一个编码报文在其缓存队列中的位置大于K，则使用新报文替换该编码报文。

5.根据权利要求1所述的面向数据中心网络编码的交换机/路由器缓存队列管理方法，其特征在于，在执行步骤三/步骤四后，继续判断后续是否还有新报文，若有，则返回步骤二，否则结束。

说明书

一种面向数据中心网络编码的交换机/路由器缓存队列管理

方法

技术领域

[0001] 本发明涉及一种面向数据中心网络编码的交换机/路由器缓存队列管理方法。

背景技术

[0002] 现代数据中心网络，使用了很多负载均衡控制方法来避免网络拥塞和在多个等价路径中均衡网络流量。其中，ECMP(等价多路径)技术对流的五元组进行哈希运算，目的是把不同流映射到与它对应的等价路径上，从而在流这个级别实现了负载均衡。但是ECMP这种粗粒度流级别的负载均衡容易产生哈希碰撞，从而负载均衡效果较差。而RPS(随机包散射)技术则是把一条流中所有数据包随机的散射到所有可用路径上，在包这个级别实现了负载均衡，达到了最佳的负载均衡效果，可以实现最细粒度的包级别负载均衡，从而可以使得网络具有更高的利用率和更加均衡的流量。然而，包级别的负载均衡算法，在非对称网络下面很容易遇到丢包或者某些包延迟到达，从而产生包乱序的问题。一旦包乱序发生，那么发送端就得重新发送这些乱序了的包，这样就会降低传输速率，增大了流的完成时间，最终降低了用户的体验。

[0003] 人们提出了很多方法来解决包散射负载均衡方法出现的乱序和丢包问题。其中，Juggler使用中间层来缓存到达的数据包。当在缺失的乱序报文到达接收端或者定时器超时之后，Juggler会把缓存中的报文提交给上层，从而减少上层的乱序概率。目前，最有效果的方法是发送方通过使用纠错码对数据报文进行冗余编码(后面将冗余编码得到的报文称为编码报文，以区别于数据报文)，接收端收到足够的编码报文之后，可以恢复乱序了的报文。如TCP/NC(TCP Network Coding)使用了前向纠错编码技术对数据报文进行冗余编码，它在收到一定数量的编码报文之后会进行解码，从而恢复那些乱序了的数据报文；CAPS对数据中心网络中的短流使用了前向纠错编码技术，并且使用RPS技术对编码报文进行散射，从而增加了短流的汇聚吞吐率，减少了它们的完成时间。但利用冗余编码来恢复乱序报文的方法会产生冗余的编码报文，增加额外的网络流量，因此，该方法在交换机/路由器现有的缓存队列管理方法下会遇到一个棘手的问题，即在动态变化的数据中心网络流量中选择一个合适的冗余率来产生编码报文。对于所有的编码方法，较低的冗余率则会限制它的解码恢复能力，而较高的冗余率则会产生过多的额外网络流量，使已经拥塞的网络变得更加拥塞，从而更进一步的增加缓存队列长度，使得数据中心网络中本来就不大的交换机缓存变得更加捉襟见肘，在现有的队尾丢弃缓存队列管理方法下，容易产生丢包或者超时，严重的影响了数据中心网络的性能。

[0004] 因此，有必要设计一套交换机/路由器缓存队列管理方法来减少冗余报文带来的影响。

发明内容

[0005] 本发明所解决的技术问题是，针对现有技术的不足，提供一种面向数据中心网络编码的交换机/路由器缓存队列管理方法，避免了编码报文增加数据报文的缓存排队延迟，同时又利用了编码报文恢复乱序或者丢失的数据报文，最终提升了数据中心的网络性能。

[0006] 本发明的技术方案包括以下步骤：

[0007] 一种面向数据中心网络编码的交换机/路由器缓存队列管理方法，包括以下步骤：

[0008] 步骤一：设置交换机/路由器缓存队列中的开始覆盖位置K；

[0009] 步骤二：交换机/路由器在收到新报文后，判断该新报文的类型，其中类型包括数据报文和编码报文；若为数据报文，转步骤三；否则，转步骤四；

[0010] 步骤三：交换机/路由器判断其缓存队列中第K个报文之后是否有编码报文；若有，则将该新报文替换最后一个编码报文存储至缓存队列中；否则，转步骤四；

[0011] 步骤四：交换机/路由器判断其缓存队列是否已满，若未满则把该新报文追加存储至缓存队列队尾，否则丢弃该新报文。

[0012] 进一步地，所述步骤一中，若交换机/路由器的出口带宽(交换机/路由器出口连接的链路的带宽)为1Gbps，将K设置为20，若交换机/路由器的出口带宽为10Gbps，将K设置为65，若交换机/路由器的出口带宽为其它值，则将K设置为交换机/路由器的带宽时延积(交换机/路由器出口连接的链路的带宽时延积)的1/7。

[0013] 进一步地，所述步骤二中，交换机/路由器收到新报文后，通过解析新报文头部的协议字段判断报文的类型。本发明中报文均为网络层的IP报文。

[0014] 进一步地，所述步骤三中，交换机/路由器从前往后遍历其缓存队列，判断是否是编码报文；若最后一个编码报文在其缓存队列中的位置大于K，则使用新报文替换该编码报文。

[0015] 进一步地，在执行步骤三/步骤四后，继续判断后续是否还有新报文，若有，则返回步骤二，否则结束。

[0016] 有益效果：

[0017] 为了解决上述数据中心网络中使用网络编码所产生的解决包乱序和产生的额外网络流量可能导致拥塞更加严重之间的矛盾，本发明提供了一种普遍适用于任何系统编码方法的数据中心负载均衡方法，并与之配套的缓存队列管理方法。使用本方法的交换机或者路由器，适时把已经进入缓存队列的编码报文替换为要入队的正常数据报文。在网络负载较轻的时候，覆盖较少的编码报文，使得接收端能从这些到达的编码报文恢复乱序了的或者未到的报文，减少在随机包散射这种负载均衡方法下产生包乱序和丢包的情况。同时，在网络负载较重时，由于覆盖机制，编码报文产生额外的网络流量不会对正常数据报文产生影响，从而避免了使用网络编码导致拥塞更加严重的情况。由于网络流量更加均衡，同时减少了乱序和额外的网络流量，该方法最终达到减少流完成时间的目的，减少了用户的等待时间。

附图说明

[0018] 图1为本发明的流程图。

[0019] 图2为测试床拓扑图。

[0020] 图3为模拟测试拓扑图。

[0021] 图4为在测试床环境中，不同方法的平均流完成时间柱状图。其中为OPER方法采用了随机包散射进行负载均衡，利用冗余编码解决乱序问题，且交换机/路由器加载了本发明的缓存队列管理方法。图4(a)为背景流占用10Mbps带宽时的平均流完成时间图，图4(b)为背景流占用30Mbps带宽时的平均流完成时间图，图4(c)为背景流占用50Mbps带宽时的平均流完成时间图。

[0022] 图5为本发明和其他方法在模拟实验测试环境中，流完成时间随网络规模增大的变化图。

[0023] 图6为在模拟实验测试环境中，在不同数据中心应用模式工作量下，流完成时间和吞吐率的变化图。图6(a)为不同方法在数据挖掘、网页搜索、缓存追随和网页服务四种工作模式下，短流的平均流完成时间的变化图；图6(b)为不同方法在上述四种工作模式下，短流的95％分位数的流完成时间变化图；图6(c)为不同方法在上述四种工作模式下，短流的99％分位数的流完成时间变化图；图6(d)为不同方法在数据挖掘、网页搜索和缓存追随三种工作模式下的长流的平均吞吐率。

具体实施方式

[0024] 下面结合附图对本发明作进一步的说明。参见图1，图1为本发明的流程图。本发明过程如下：

[0025] 首先交换机或者路由器根据出口带宽，设置开始覆盖位置K。若出口带宽为1Gbps则K值为20，若出口带宽为10Gbps则K值为65。若出口带宽为其它值，则K值为1/7带宽时延积大小。

[0026] 其次，当交换机或者路由器接收到新报文时，通过解析IP头部的协议字段对报文类型进行判断。

[0027] 最后，在使用该方法的交换机或者路由器收到新的数据报文时，从前往后遍历缓存队列中报文的IP头部协议字段，通过该字段的取值判断是否是编码报文，并且记录当前遍历的报文在缓存队列中的位置。若最后一个编码报文在缓存中的位置大于K，则使用新的数据报文替换该编码报文；反之，则在缓存队列未满的时候把新报文追加存储至缓存队列队尾，否则丢弃该新报文；若收到的新报文为编码报文，则直接在缓存队列未满的时候把新报文追加存储至缓存队列队尾，否则丢弃该编码报文。交换机或者路由器在收到后续新报文后，重复上述操作。

[0028] 以下利用NS2.35网络仿真平台，和真实的测试床对其性能进行了测试。NS网络模拟器是一种通用的多协议网络模拟软件，它是互联网上公开发布的(网址：http://www.isi.edu/nsnam/ns)，目前已被网络研究者广泛使用。NS2.35是它的版本之一。

[0029] 分别采用图2和图3两种拓扑结构，在测试床和模拟测试两种不同的测试环境下面测试本发明的性能。在如图2所示的拓扑中，左边的架顶交换机(ToR Switch)出口链路带宽设置为100Mbps。没有排队延迟的逐跳往返延时为100微秒且报文大小和和超时时间分别设置为1.5KB和200毫秒。所有机器运行了ubuntu 12.04操作系统。而如图3所示的拓扑中，每台和主机相连的架顶交换机都连接到了图片上方的所有的核心交换机。并且发送端到架顶交换机和架顶交换机到核心交换机的链路带宽分别为1Gbps和10Gbps。交换机的缓存大小设置为250个报文大小，无队列时的往返延时为100微秒，报文大小为1.5KB。

[0030] 1、测试床下的性能提升度

[0031] 该实验测试本发明在不同程度的非对称网络情况下的性能。该实验使用了测试床环境来进行测试。在对OPER方法进行测试时，在如图2所示的拓扑中左边的架顶交换机(ToR Switch)加载了本发明的缓存队列管理方法。在该测试中，发送端会同时发送复数条流给接收端。这些流的报文，会在经过左边的架顶交换机时被随机的散射到两条路径上。但是其中一条路径存在一条UDP背景流，在不同的实验场景下，分别占用10、30和50Mbps的带宽。发送端同时发送的流个数，会从4条翻倍增加到64条。从图4可以看到，随着并行流个数的增加和背景流占用带宽的增加，网络负载逐渐增重，但是相比较于其他数据中心常见的负载均衡方法，OPER方法仍然能够减少最多50.3％的平均流完成时间。

[0032] 2、模拟实验测试环境测试结果

[0033] 除了以上给出的测试床的局部性能测试，为了全面比较该发明的高效性，进一步测试了在复杂拓扑结构情况下，该发明的各项性能指标，包括了：平均流完成时间，95分位数流完成时间和99分位数流完成时间以及平均吞吐率。实验场景包括了增大Leaf-Spine拓扑规模和四种常见的数据中心应用模式。测试的负载均衡机制包括了：ECMP、RPS、Juggler、CAPS、OPER和OPER-MQ。其中ECMP是基于流的负载均衡方法，RPS和Juggler是基于包级别的负载均衡控制方法，CAPS和OPER以及OPER-MQ(与OPER方法区别在于，交换机/路由器使用基于优先级的缓存队列管理方法)为使用网络编码进行包级别的负载均衡控制方法。

[0034] (1)图5给出了不同机制在增大网络拓扑规模时的测试结果。在该测试中，固定网络负载为50％并且逐步增加网络中的机架个数。图5统计了在不同拓扑规模下，不同方法的平均流完成时间。从图5中可以看到，OPER方法一直都具有最小的平均流完成时间，并且随着网络规模的变大还基本保持完成时间不变。可见本发明在不同网络拓扑规模模拟测试环境下，性能指标要明显优于其它方法。

[0035] (2)图6给出了不同机制在不同数据中心应用模式下的测试结果。在该测试中网络负载被固定为80％，且流大小服从给定的分布。如图6(a)、(b)和(c)所示，无论是那种应用模式，OPER方法对于短流可以保持最低的平均、95分位数和99分位数的流完成时间。对于长流，比较了他们的平均吞吐率。图6(d)给出了实验结果。在三种不同的应用模式下面，OPER方法都保持了最高的吞吐率。

[0036] 从以上实验数据看来，本发明方法在以上几个方面具有比其他方法更优秀的性能。这是因为本方法既使用了网络编码，来保证最好的负载均衡效果的同时，又避免了网络编码所带来的过多网络负载的问题。而由于本发明的所有组成部分都是模块化的，因此可以很容易的组合到现有的网络中，保证了本发明的普及性。