流量管理系统中队列调度方法研究

　　传统的IP网络中，转发设备对所有的报文均采用先入先出的策略（First-in and First-out，FIFO）的策略进行处理，尽最大的努力将报文送到目的地，这种方式中所有的报文无区别对待，对报文传送的可靠性、传送延迟等性能不能提供任何保证；但在实际应用中，网络上存在各种各样的问题，比如丢包现象、网络抖动、网络延迟和网络带宽受限等等。随着网络发展和新兴业务的出现，这些问题已经严重影响了网络业务，比如VoIP，IPTV等实时业务，这些业务对传输延迟提出了更高的要求，如果延时过长，用户将不能接受，但相比这些业务，E-Mail等业务对时间延迟却并不敏感；因此传统的对报文无区分的处理方式已经不能满足现代网络的服务质量问题。服务质量（Quality of Service，QoS）技术的出现便致力于解决这个问题。

 

　　在现代数据通信领域，对数据产品的QoS要求越来越高，由此对包处理速率、支持的队列数、带宽、步进粒度等流量管理技术指标提出了更高的要求。

 

　　由于当前流量管理的技术指标越来越高，特别是队列数越来越多的情况下，实现流量管理所使用的缓存资源越来越多。在具体设计实现中，无论是在现场可编程门阵列（Field Programmable Gate Array，FPGA）中实现流量管理功能，还是在集成电路（Application Specific IntegratedCircuit，ASIC）中实现流量管理功能，缓存资源的使用量都是一个衡量可实现性的重要标准。

 

　　本文提供一种队列调度的改进方法，采用此方案后队列链表信息的缓存资源可以大幅度减少，提高流量管理系统的可实现性。

 

　　1 设计思路

 

　　1.1 传统队列调度组件设计方法

 

　　如图1所示，流量管理系统中最重要的组件为队列调度组件。队列调度组件通过队列调度算法，协同其他组件进行出队调度，共同完成流量管理功能。队列调度组件由授权控制队列出队，当获得授权时队列才可以出队，授权的分配由队列调度算法来控制；各个队列在队列调度算法的控制下组成链表；传统的设计中，该链表根据当前是否有效分为活动队列链表和非活动队列链表。

 

 

　　1.2 改进后的队列调度实现方法

 

　　为了解决上述问题，本文提出了将传统设计中的活动队列链表和非活动队列链表合成为一个链表的方法，在该方法下调度队列链表的入队和出队步骤如下。

 

　　1.2.1 入队步骤（见图2）

 

　　当队列入队时，加入到整个链表的尾部。

 

 

　　1.2.2 出队步骤（见图3）

 

　　出队步骤：当队列首次出队执行时，记下当前队列的尾部，标记记为活动队列队尾；队列出队操作执行时，将首指针对应队列出队处理；队列出队操作结束，执行队列转移操作，根据算法的不同，决定将队列插入到活动队列队尾还是直接加入到整个链表尾部。如插入到活动队列队尾，则将之前标记的活动队列队尾改写为当前队列，否则直接加入到整个链表尾部。

 

 

　　2 结语

 

　　如图4所示，传统方法下，需要存储活动队列首指针、活动队列尾指针、非活动队列首指针和非活动队列尾指针，如采用改进后的方法，可以只存储链表首指针、尾指针和活动队列队尾。

 

 

　　本文提供的队列调度方法，在当前通信系统中队列数大大增加的情况下，有效地降低流量管理系统实现时的缓存资源使用量，在保证高性能流量管理的前提下，使流量管理系统更加容易实现，大大提高了高性能流量管理系统的可实现性。

 

　　[参考文献]

 

　　[1]周炯盘，庞沁华.通信原理[M].北京：北京邮电大学出版社，2005.

　　[2]王金明.VerilogHDL程序设计教程[M].北京：人民邮电出版社，2004.