论文部分内容阅读
摘 要：对基于GPS模型的WFQ和VC算法研究，针对WFQ算法容易产生与GPS模型较大的偏差，影响系统的公平性，VC算法对于相关量的计算较复杂，对流的“突发性”容忍程度低，从面对“突发性”时的资源利用率的角度对VC算法改进，提出了相对公平的VC算法模型（RFVC Relatively-Fair Virtual Clock），仿真实现并与VC算法比较，结果显示，该算法可以极大的减少系统开销，提高效率。
关键词：分组调度；VC；WFQ；RFVC；服务质量
1.引言
网络服务质量QoS（Quality of Service）是互连网络所必须考虑的一个的重要问题。网络的流量控制和拥塞处理都是在路由器中得以实现。在高速路由器技术研究中，核心部分之一是路由器中分组调度算法。如何提高网络可靠性和QoS恢复能力已成为网络研究的重要课题[1]。目前，具有公平性和QoS保证的分组调度算法已成为调度领域里的研究热点。
2.相关研究
研究者们针对各种网络的特点提出了多种分组调度算法以提高网络传输性能。其中Abhay.KParekh于1992年在其博士论文中提出的基于比特流的理想模型GPS[5]成为分组调度的公平性参考基础，其分组化的WFQ算法己被IETF采用。
文献[3，2]提出了WFQ算法是对GPS的一种较好的逼近模拟，WFQ和WF2Q是目前性能最优越的PGPS算法，它们的公平性由绝对公平的GPS模型的调度机制保证。
文献[4]提出了虚拟时钟VC算法，也是基于GPS模型的算法。虚拟时钟算法思想最初来源于时分复用系统（Time Division Multiple- xing，TDM），具体的说，虚拟时钟算法的主要功能是控制随机数据流的平均传输速率，根据用户要求指定的平均速率保证用户的资源使用，并在每个流之间实施隔离，其最大特点就是通过引入虚拟时钟使得可以用一个根据虚拟时间排队的队列来模拟公平队列调度中的多个队列[5]。
通过对调度算法的综合比较发现，在分组交换网络分组调度算法中，VC和WFQ算法是两种比较典型的调度模型。文献[6]从理论和仿真结果表明了它的高效性、可行性和该算法的良好的可扩展性，本文就是在VC和WFQ存在的缺点和不足，从改进算法效率和资源使用率角度对VC算法进行了改进，提出了一种相对公平的VC算法RFVC（Relatively-Fair Virtual Clock）算法。以达到有效提高算法对流的速率的容忍程度的问题，可以在网络带宽不足的情况下，利用有限的带宽来保证QoS的时延要求，同时，RFVC算法也在一定程度上拥有与WFQ一样的公平性。
3.算法设计
3.1RFVC算法设计
RFVC算法改善VC算法和WFQ算法的不足，以达到有效提高算法对流的速率的容忍程度的问题，可以在网络带宽不足的情况下，利用有限的带宽来保证QoS的时延要求，同时，RFVC算法也在一定程度上拥有与WFQ一样的公平性。
RFVC算法定义了虚拟时间函数，并为每个流确定了其虚拟开始时间和虚拟结束时间：
从各会话队列的队首分组中选取虚拟时间最小者进行调度，通过检测最大流量 ，当分组数目达到最大流量者就停止为其服务，以其缓冲区的溢出为超速的代价。
3.2RFVC调度算法的描述
RFVC算法与VC算法的最主要区别是为每个流单独分配了一个会话队列来进行检测，其流程图如图3-1所示
3.3RFVC调度算法的分析
通过对每个流进行隔离控制，每个流拥有自己的缓存队列，当某个流超过自己预定资源量时，随着其 逐渐增大，系统对其服务量也越来越少，直到最后将几乎停止为其服务。在带宽不足的情况下，首先保证了正常速率流的延时需要，尽可能满足实时业务的QoS的要求，这种类似与WFQ算法的带宽分配方法，在一定程度上保证了各业务之间的公平程度。
下图为改进的RFVC算法调度模型：
3.4RFVC算法模拟分析
下面是模拟过程中得到的记录文件（也称trace文件）tr1.tr的片断，它把模拟过程中所有的事件都记录了下来：
r 0.7716 0 1 cbr 40 ------- 2 0.1 1.3 118 285
- 0.7744 0 1 cbr 40 ------- 0 0.2 1.1 48 290
+ 0.7744 0 1 cbr 40 ------- 1 0.0 1.2 121 291
d 0.7744 0 1 cbr 40 ------- 1 0.0 1.2 121 291
+ 0.7744 0 1 cbr 40 ------- 2 0.1 1.3 121 292
r 0.7748 0 1 cbr 40 ------- 1 0.0 1.2 71 171
- 0.7776 0 1 cbr 40 ------- 2 0.1 1.3 121 292
r 0.778 0 1 cbr 40 ------- 2 0.1 1.3 119 287
- 0.7808 0 1 cbr 40 ------- 1 0.0 1.2 73 176
+ 0.7808 0 1 cbr 40 ------- 1 0.0 1.2 122 293
+ 0.7808 0 1 cbr 40 ------- 2 0.1 1.3 122 294
r 0.7812 0 1 cbr 40 ------- 1 0.0 1.2 72 173
trace文件的格式规定如下：
其中，src_addr和dst_addr的格式为：node.port（如 3.0，表示3节点的0端口），event的各种符号代表的事件如下： r：目标节点收到一个分组
+：在队列中插入一个分组
-：调度一个分组出队列
d：丢弃一个分组
接下来就在上述改进方案进行了仿真，试验仿真的网络拓扑结构如图4-5所示：
拓扑结构如图4-5所示：
在我们设计的RFVC调度算法中，是不同源端流去向同一个输出端口，对资源竞争条件下的调度。因此在这里我们让所有的源端流都经过一个路由器E1（这里实际上它的作用是一个FLITER过滤器），让那些目的地为SINK0～SINK2的分组通过，到达SCHEDULER（RFVC调度器），进行调度。这些输入分组在SCHEDULER中进行调度，对输出端口进行竞争，以获得被转发出去的可能，因此在仿真模型中主要是通过在SCHEDULER来自流的分组进行合理的调度，最终将输出分组再按照其各自的目的节点的不同，转发到其目的分析节点，以便我们来进行参数统计分析。通过仿真，来比较RFVC算法与VC算法的性能差异，验证RFVC算法的可行性。
4.仿真结果及分析
在仿真试验中，我们首先让流0，2在预留链路带宽的情况下，流1在超出预留带宽的情况下，利用VC和RFVC分组队列调度策略来进行仿真，下面是仿真结果及按照分组丢弃情况、流量以及延迟性能进行比较分析。
（1）分组丢弃情况
当流1的速率超出预留资源的情况下，我们对两种调度策略进行比较时发现，在VC策略种，由于各流互相影响，互相强占带宽，导致不仅“恶意流”出现了分组丢弃的情况，连正常流也因受其影响也出现了分组丢弃现象，也就是恶意流强占了正常流的带宽。而在RFVC算法中丢弃了VC算法中的单队列采用多个流排列，正常运行的流的带宽不受超速流的影响，使每个流之间的隔离性能增强，突发流超出预留带宽的数据对其他正常工作的流的影响非常小，每个流基本可以保持以预留带宽来获得路由器所提供的服务。即使突发流在一段时间内发送多余的数据，这时只能使自己的预留缓存溢出而丢弃后续到达的分组受得调度服务器的惩罚。而在原VC中只有一个队列，并没有隔离各个流，而使得突发流对其他正常速率的流影响很大大，甚至出现突发流抢占正常流资源的情况。
（2）分组延迟情况
对于调度算法的性能研究，延迟是一个非常重要的指标。因为我们研究目的就是要找到一个能提供Qos保证的分组队列调度算法。而延迟则是网络中提供实时保障的关键因素。由下图RFVC算法的延迟情况和VC算法的延迟情况可以看出，在VC算法下，由于流1的影响，使得各流的端到端延迟都急剧增加。不能保证有较高其他正常流的分组得到要求的服务。而在RFVC调度策略下，由于事先对每个流的预留带宽进行了限制，因此恶意流的延迟受其缓存的影响，当超速时延迟会增大，而在丢弃一定分组后，其延迟不会无限增大，而是维持一定的稳定。其他正常流则不会受恶意流的影响，其端到端延迟几乎为0。
在前面的仿真过程中，通过对调度算法的分组丢弃率、分组延迟性能的比较，可以看出，RFVC算法很好的改进了原VC算法，加强了各流之间的隔离，是综合性能较佳的算法，是一种系统效率较高、能够有效满足服务速率保证、时延保证和流隔离监视的调度算法。
5.结论及下一步的工作
分析显示该算法保持原VC的优点，在具有与原VC相同的端到端时延特性的前提下，通过减少系统中分组排序处理，使得原VC中系统处理分组排序的复杂度由原来的 降为RFVC下的 ，极大的减小了系统开销，提高了效率，节省了系统资源，使得系统设计简化，为高速路由器的设计开发提供了新的思路。
RFVC中各个流的隔离性加强，恶意流超额数据对其他正常流的影响非常小，各流基本保持以预留速率获得服务，即使恶意流发送较多的数据，也会使自己缓存溢出而丢弃过多分组保持以预留速率获得服务而受得惩罚。而且，RFVC中每个流的分组延迟也不受其他流的影响，恶意流的延迟由于受其缓存大小影响在丢弃一定的分组后基本保持稳定，正常流分组队列延迟几乎为零，恶意流的实际分组丢失率接近于理论计算的分组丢失率，原VC中受恶意流影响，各个流的队列延迟都非常大，各个流的端到端延迟亦同样。RFVC中各流不受恶意流的影响，而原VC中由于各流相互影响，使得正常流也出现分组丢失现象，恶意流抢占正常流的资源。
系统处理分组排序的复杂度由原来VC的 降为RFVC算法下的 ，所以改进算法很好的达到了改进目的，加强了流的隔离和保护，减小了系统开销。
RFVC算法当中对于一些突发恶意流的处理是采用了将各流保持预留速率以获取服务，恶意流在发送较多的数据时，是以自己的缓存溢出丢失分组为代价的，而对于一些变速流（如视频流），RFVC算法则很难满足其需要。
参考文献：
[1]DAS A，MARTEL C， MUKHERJEE B， et al. A better approach to reliable Multi-path provisioning[A]. IEEE Global Communications Conferences（GLOBECOM）[C].2007.2724-2728.
[2]Abhay， K Parekh.A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks： The Multiple Node Case[C]，INFOCOM'92， 1992，IEEE Computer Society Press.1992：915-924.
[3]A.Demers， S. Keshav， and S. Shenkar. Analysis and Simulation of A Fair Queueing Algorithm[C]. In Proceeding of SIGCOMM’89， Austin， Texas.1989：46-67.
[4]L. Zhang.Virtual Clock：A New Traffic Control Algorithm for Packet Switching Networks，In Proceedings of ACM[C].Philadelphia，SIGCOMM’90，1990：19 -29.
[5]高文宇，陈松乔.虚拟时钟调度算法研究.计算机应用与软件，2005；22（6）：127-130.
[6]G. Xie， S. Lam. Delay Guarantee of Virtual Clock Service Discipline， IEEE/ACM Transactions on Networking[J].1995，3（6）：683-689.
关键词：分组调度；VC；WFQ；RFVC；服务质量
1.引言
网络服务质量QoS（Quality of Service）是互连网络所必须考虑的一个的重要问题。网络的流量控制和拥塞处理都是在路由器中得以实现。在高速路由器技术研究中，核心部分之一是路由器中分组调度算法。如何提高网络可靠性和QoS恢复能力已成为网络研究的重要课题[1]。目前，具有公平性和QoS保证的分组调度算法已成为调度领域里的研究热点。
2.相关研究
研究者们针对各种网络的特点提出了多种分组调度算法以提高网络传输性能。其中Abhay.KParekh于1992年在其博士论文中提出的基于比特流的理想模型GPS[5]成为分组调度的公平性参考基础，其分组化的WFQ算法己被IETF采用。
文献[3，2]提出了WFQ算法是对GPS的一种较好的逼近模拟，WFQ和WF2Q是目前性能最优越的PGPS算法，它们的公平性由绝对公平的GPS模型的调度机制保证。
文献[4]提出了虚拟时钟VC算法，也是基于GPS模型的算法。虚拟时钟算法思想最初来源于时分复用系统（Time Division Multiple- xing，TDM），具体的说，虚拟时钟算法的主要功能是控制随机数据流的平均传输速率，根据用户要求指定的平均速率保证用户的资源使用，并在每个流之间实施隔离，其最大特点就是通过引入虚拟时钟使得可以用一个根据虚拟时间排队的队列来模拟公平队列调度中的多个队列[5]。
通过对调度算法的综合比较发现，在分组交换网络分组调度算法中，VC和WFQ算法是两种比较典型的调度模型。文献[6]从理论和仿真结果表明了它的高效性、可行性和该算法的良好的可扩展性，本文就是在VC和WFQ存在的缺点和不足，从改进算法效率和资源使用率角度对VC算法进行了改进，提出了一种相对公平的VC算法RFVC（Relatively-Fair Virtual Clock）算法。以达到有效提高算法对流的速率的容忍程度的问题，可以在网络带宽不足的情况下，利用有限的带宽来保证QoS的时延要求，同时，RFVC算法也在一定程度上拥有与WFQ一样的公平性。
3.算法设计
3.1RFVC算法设计
RFVC算法改善VC算法和WFQ算法的不足，以达到有效提高算法对流的速率的容忍程度的问题，可以在网络带宽不足的情况下，利用有限的带宽来保证QoS的时延要求，同时，RFVC算法也在一定程度上拥有与WFQ一样的公平性。
RFVC算法定义了虚拟时间函数，并为每个流确定了其虚拟开始时间和虚拟结束时间：
从各会话队列的队首分组中选取虚拟时间最小者进行调度，通过检测最大流量 ，当分组数目达到最大流量者就停止为其服务，以其缓冲区的溢出为超速的代价。
3.2RFVC调度算法的描述
RFVC算法与VC算法的最主要区别是为每个流单独分配了一个会话队列来进行检测，其流程图如图3-1所示
3.3RFVC调度算法的分析
通过对每个流进行隔离控制，每个流拥有自己的缓存队列，当某个流超过自己预定资源量时，随着其 逐渐增大，系统对其服务量也越来越少，直到最后将几乎停止为其服务。在带宽不足的情况下，首先保证了正常速率流的延时需要，尽可能满足实时业务的QoS的要求，这种类似与WFQ算法的带宽分配方法，在一定程度上保证了各业务之间的公平程度。
下图为改进的RFVC算法调度模型：
3.4RFVC算法模拟分析
下面是模拟过程中得到的记录文件（也称trace文件）tr1.tr的片断，它把模拟过程中所有的事件都记录了下来：
r 0.7716 0 1 cbr 40 ------- 2 0.1 1.3 118 285
- 0.7744 0 1 cbr 40 ------- 0 0.2 1.1 48 290
+ 0.7744 0 1 cbr 40 ------- 1 0.0 1.2 121 291
d 0.7744 0 1 cbr 40 ------- 1 0.0 1.2 121 291
+ 0.7744 0 1 cbr 40 ------- 2 0.1 1.3 121 292
r 0.7748 0 1 cbr 40 ------- 1 0.0 1.2 71 171
- 0.7776 0 1 cbr 40 ------- 2 0.1 1.3 121 292
r 0.778 0 1 cbr 40 ------- 2 0.1 1.3 119 287
- 0.7808 0 1 cbr 40 ------- 1 0.0 1.2 73 176
+ 0.7808 0 1 cbr 40 ------- 1 0.0 1.2 122 293
+ 0.7808 0 1 cbr 40 ------- 2 0.1 1.3 122 294
r 0.7812 0 1 cbr 40 ------- 1 0.0 1.2 72 173
trace文件的格式规定如下：
其中，src_addr和dst_addr的格式为：node.port（如 3.0，表示3节点的0端口），event的各种符号代表的事件如下： r：目标节点收到一个分组
+：在队列中插入一个分组
-：调度一个分组出队列
d：丢弃一个分组
接下来就在上述改进方案进行了仿真，试验仿真的网络拓扑结构如图4-5所示：
拓扑结构如图4-5所示：
在我们设计的RFVC调度算法中，是不同源端流去向同一个输出端口，对资源竞争条件下的调度。因此在这里我们让所有的源端流都经过一个路由器E1（这里实际上它的作用是一个FLITER过滤器），让那些目的地为SINK0～SINK2的分组通过，到达SCHEDULER（RFVC调度器），进行调度。这些输入分组在SCHEDULER中进行调度，对输出端口进行竞争，以获得被转发出去的可能，因此在仿真模型中主要是通过在SCHEDULER来自流的分组进行合理的调度，最终将输出分组再按照其各自的目的节点的不同，转发到其目的分析节点，以便我们来进行参数统计分析。通过仿真，来比较RFVC算法与VC算法的性能差异，验证RFVC算法的可行性。
4.仿真结果及分析
在仿真试验中，我们首先让流0，2在预留链路带宽的情况下，流1在超出预留带宽的情况下，利用VC和RFVC分组队列调度策略来进行仿真，下面是仿真结果及按照分组丢弃情况、流量以及延迟性能进行比较分析。
（1）分组丢弃情况
当流1的速率超出预留资源的情况下，我们对两种调度策略进行比较时发现，在VC策略种，由于各流互相影响，互相强占带宽，导致不仅“恶意流”出现了分组丢弃的情况，连正常流也因受其影响也出现了分组丢弃现象，也就是恶意流强占了正常流的带宽。而在RFVC算法中丢弃了VC算法中的单队列采用多个流排列，正常运行的流的带宽不受超速流的影响，使每个流之间的隔离性能增强，突发流超出预留带宽的数据对其他正常工作的流的影响非常小，每个流基本可以保持以预留带宽来获得路由器所提供的服务。即使突发流在一段时间内发送多余的数据，这时只能使自己的预留缓存溢出而丢弃后续到达的分组受得调度服务器的惩罚。而在原VC中只有一个队列，并没有隔离各个流，而使得突发流对其他正常速率的流影响很大大，甚至出现突发流抢占正常流资源的情况。
（2）分组延迟情况
对于调度算法的性能研究，延迟是一个非常重要的指标。因为我们研究目的就是要找到一个能提供Qos保证的分组队列调度算法。而延迟则是网络中提供实时保障的关键因素。由下图RFVC算法的延迟情况和VC算法的延迟情况可以看出，在VC算法下，由于流1的影响，使得各流的端到端延迟都急剧增加。不能保证有较高其他正常流的分组得到要求的服务。而在RFVC调度策略下，由于事先对每个流的预留带宽进行了限制，因此恶意流的延迟受其缓存的影响，当超速时延迟会增大，而在丢弃一定分组后，其延迟不会无限增大，而是维持一定的稳定。其他正常流则不会受恶意流的影响，其端到端延迟几乎为0。
在前面的仿真过程中，通过对调度算法的分组丢弃率、分组延迟性能的比较，可以看出，RFVC算法很好的改进了原VC算法，加强了各流之间的隔离，是综合性能较佳的算法，是一种系统效率较高、能够有效满足服务速率保证、时延保证和流隔离监视的调度算法。
5.结论及下一步的工作
分析显示该算法保持原VC的优点，在具有与原VC相同的端到端时延特性的前提下，通过减少系统中分组排序处理，使得原VC中系统处理分组排序的复杂度由原来的 降为RFVC下的 ，极大的减小了系统开销，提高了效率，节省了系统资源，使得系统设计简化，为高速路由器的设计开发提供了新的思路。
RFVC中各个流的隔离性加强，恶意流超额数据对其他正常流的影响非常小，各流基本保持以预留速率获得服务，即使恶意流发送较多的数据，也会使自己缓存溢出而丢弃过多分组保持以预留速率获得服务而受得惩罚。而且，RFVC中每个流的分组延迟也不受其他流的影响，恶意流的延迟由于受其缓存大小影响在丢弃一定的分组后基本保持稳定，正常流分组队列延迟几乎为零，恶意流的实际分组丢失率接近于理论计算的分组丢失率，原VC中受恶意流影响，各个流的队列延迟都非常大，各个流的端到端延迟亦同样。RFVC中各流不受恶意流的影响，而原VC中由于各流相互影响，使得正常流也出现分组丢失现象，恶意流抢占正常流的资源。
系统处理分组排序的复杂度由原来VC的 降为RFVC算法下的 ，所以改进算法很好的达到了改进目的，加强了流的隔离和保护，减小了系统开销。
RFVC算法当中对于一些突发恶意流的处理是采用了将各流保持预留速率以获取服务，恶意流在发送较多的数据时，是以自己的缓存溢出丢失分组为代价的，而对于一些变速流（如视频流），RFVC算法则很难满足其需要。
参考文献：
[1]DAS A，MARTEL C， MUKHERJEE B， et al. A better approach to reliable Multi-path provisioning[A]. IEEE Global Communications Conferences（GLOBECOM）[C].2007.2724-2728.
[2]Abhay， K Parekh.A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks： The Multiple Node Case[C]，INFOCOM'92， 1992，IEEE Computer Society Press.1992：915-924.
[3]A.Demers， S. Keshav， and S. Shenkar. Analysis and Simulation of A Fair Queueing Algorithm[C]. In Proceeding of SIGCOMM’89， Austin， Texas.1989：46-67.
[4]L. Zhang.Virtual Clock：A New Traffic Control Algorithm for Packet Switching Networks，In Proceedings of ACM[C].Philadelphia，SIGCOMM’90，1990：19 -29.
[5]高文宇，陈松乔.虚拟时钟调度算法研究.计算机应用与软件，2005；22（6）：127-130.
[6]G. Xie， S. Lam. Delay Guarantee of Virtual Clock Service Discipline， IEEE/ACM Transactions on Networking[J].1995，3（6）：683-689.