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

　　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的不同可归结于：
　　
　　①信元长度固定，调度事件发生间隔固定。
　　
　　②系统虚时间可以在每次调度时更新。
　　
　　其中②依据①和文献［4］中的结论，这充分利用了信元输出时间固定的特点。文献［4］介绍了一种只在分组离开时更新V（t）的方法，而信元输出的时刻是固定的并且间隔相等，那么对于基于信元的WFQ，我们只需要在间隔相等的固定时刻采用文献［3］的技术就可以实现。
　　
　　3　模型建立
　　根据以上的分析，仿真模型采用简单的固定时间驱动的方法实现。模型建立的几点假设［3］：
　　
　　（1）一个信元传输的时间称为一个时隙。
　　
　　（2）各输入端信元的到达过程相互独立。
　　
　　（3）信元只在每个时隙开始时到达，输出队列容量足够大。
　　
　　（4）模型建立和仿真研究都基于单播数据流。一个具有N个输入／输出端口的WFQ模型的框图如图1所示。
　　
　　该模型是由信元产生器、交换结构、输出队列组成，其中输出队列包含用于存储各个会话的信元的缓存和WFQ调度器。根据假设（1），在仿真模型中，信元的产生、交换和调度输出都将在一个时隙内同时进行。本文使用模块化的设计思路实现该模型，基于两点考虑：一是模型各主要组成部分交互关系简单、直接；二是方便模型的改进和扩展。图2表示了模型的工作流程。
　　 　
　　 　
　　我们使用标准C语言在Linux下实现了该模型。 进行仿真时，各模块的参数全部放在一个配置文件内，在初始化步骤中对WFQ模型设置参数，仿真结果可以输出到屏幕上，也可以输出到文件中，不支持图形输出。
　　
　　3．1　信元产生器
　　
　　信元产生器负责生成信元，是模型的数据源，在每个时隙到来时最先运行。根据假设（2），每个端口的信元产生器相互独立的工作，依据各个会话负载参数p（0≤p≤1），主要产生服从独立同分布的贝努利到达过程信元：每个时隙内产生信元的数目服从p的0～1二项式分布。产生的信元如果均匀地分配给各个会话，称为均匀独立同分布的贝努利过程；否则称为非均匀独立同分布的贝努利过程。
　　
　　在模型中，信元的产生只是生成一个复杂的数据结构，并没有类似现实的信元的具体内容，释放这个数据结构的过程模拟了信元的输出过程。
　　
　　3．2　交换结构
　　
　　交换结构主要负责信元的传送，完成输入与输出端之间的连接。本模型提供一种逻辑的支持输出排队的交换结构，当输入端产生信元后，负责将信元传送到正确的目的地，即把产生的信元元素转移到输出缓存中。
　　
　　此外，交换结构还负责为每个到达的信元计算时间标签，与式（1）不同的是，这里只为会话i维护2个时间标签：会话i当前等待调度的信元的服务结束时间标签F（i）和会话i的服务结束时间标签SF（i）（会话最后一个信元的服务结束时间标签），并不需要为每个信元记录时间标签。和“WFQ调度器”协助工作，共同完成信元的调度输出。
　　
　　3．3　输出队列
　　
　　由于信元在输出端发生输出竞争，为了缓解拥塞，需要设置输出队列用于缓存信元，并负责队列的管理。模型中输出队列包含2部分：输出缓存和WFQ调度器。
　　
　　输出缓存用于存储等待发送的信元，每个逻辑独立的输出缓存只为一个会话服务。每个输出队列中只包含N个输出缓存，每个输出缓存对应一个输入端。输出缓存使用双向链表实现，链表的数据项为信元。如上所述，每个输出端维护N个这样的链表。
　　
　　WFQ调度器负责按SFF策略调度并输出信元，同时更新系统虚时间函数。WFQ调度器每个时隙执行一次。具体形式化描述见文献［4］。
　　
　　4　仿真结果
　　本节主要对基于信元的WFQ模型进行仿真研究，分析了带宽分配公平性性能，并与FIFO做了比较。为绘图清晰，假设每个输出端有4个会话，对于输出端1，4个会话分别标示为flow（1，1），flow（2，1），flow（3，1）和flow（4，1），预约归一化带宽为0．4，0．3，0．2，0．1，并且每个会话负载是相同的。
　　
　　在上述数据流到达情况下，图3和图4分别表示在FIFO和WFQ调度下带宽的分配。
　　
　　（1）当各会话负载p≤0．25时，输出队列能满足他们的带宽需求，因此在FIFO和WFQ分配给各会话所需的带宽。
　　
　　（2）当p＞0．25时，FIFO不考虑各会话的预约，将带宽平均分配给4个会话，这违背了文献［1］中的公平性原则。也就是说，FIFO不具备公平排队的能力。而对于WFQ，我们从图4中可以看出，当p＞0．4时，各个会话带宽需求都超出他们的预约，WFQ则按预约带宽分配给相应的会话。当0．25≤p≤0．4时，WFQ仍然是公平的。
　　 　
　　
　　5　结　语
　　本文主要对基于固定长度的信元排队的WFQ进行了建模和仿真研究。首先分析了基于信元排队的WFQ和实现的方法，该方法充分利用信元输出时间固定的特点，在间隔相等的固定时刻更新系统虚时间函数。这种方法特别适合使用固定时间驱动的方法实现，具有高效、简单的特点。这些为模型的建立奠定了基础。接着提出了基于信元排队的WFQ模型，并分析了各个组成部分。最后对基于信元的WFQ模型进行了仿真研究，从带宽分配公平性指标与FIFO做了比较。仿真结果表明：基于信元排队的WFQ适用于高速路由器／交换机中。