高速路由器的公平排队仿真模型的研究与实现

　　1　引　言

　　宽带网络的发展要求一个通信网络要能同时支持多种不同的业务特性的流量，也即能提供不同的服务质量保证，具体表现在满足带宽、时延、时延抖动等方面的不同需求。因此网络本身必须具有提供不同服务质量的能力，其中，分组公平队列调度算法是提供服务质量保证的重要机制之一。近年来，基 于GPS(Generalized Processor Share)[1]的分组公平排队调度算法得到了广泛的研究，其中最重要 的是WFQ[2]。WFQ考虑的不定长度分组的排队和调度，因此，对WFQ的仿真通常使用事件驱动的方式，模型需要维护的信息量 大，开销较大。另外，对硬件的实现也是一种挑战。

　　但在当今许多高速路由器/交换机中，为了提高传输效率，通常采用定长交换技术，处理数据单元 为固定长度的“信元”。对于不同长度的IP分组，可以在交换前划分成信元，在输出端重组后再发送到链路上去。那么，基于固定长度的信元排队和调度的WFQ的实现也随之而来，这也是WFQ的一种特例。在这种情况下，固然可以采用事件驱动的方式来仿真WFQ，但本文 提出了一种更有效的仿真模型，他利用了信元输出时间固定的特性，采用固定时间驱动的方式，从而简化了仿真流程和减小了系统开销。此外，对硬件的设计和实现也有指导意义。

　　本文提出WFQ的仿真模型简单、高效，在研究单个交换节点的性能时，为研究者提供了一种仿真工具。本文主要对基于信元排队的 WFQ进行了建模和仿真，并从带宽分配的公平性方面与FIFO(许多路由器/交换机采用仍采用的排队方式)进行了性能比较，仿真结果表明基于信元排队的 WFQ适用于高速路由器/交换机中。

　　2　基于信元排队的WFQ

　　在提出仿真模型之前，首先介绍WFQ 和基于信元排队的WFQ，这是模型建立的理论基础和模型实现中的关键部分。因此，单独提出并做简单介绍。

　　文献[2]定义的WFQ基于：

　　(1)系统维持一个全局函数V(t)，称为系统虚时间函数，用以记录WFQ已经提供的服务量。V(t)也就是GPS系统中系统虚时间。WFQ利用系统虚 时间函数为每个分组计算其相应的开始时间标签和完成时间 标签如式(1)所示：

　　φi表示赋予会话i的任一正实数，这里可以理解 为会话i预约的归一化带宽ri。其中系统虚时间的维护是WFQ实现的关键，按文献[2]中的实现方法，V(t)更新的时刻不固定，随时都有可能必须使用事件驱动的方式实现。

　　(2)执行分组选择策略，WFQ遵循最小完成时间标签优选(SFF，Smallest Finishing time First)。

　　基于信元排队的WFQ与分组WFQ的不同可归结于：