楊敏華

（中興通訊股份有限公司，江蘇 南京 210012）

流量管理系統(tǒng)中隊(duì)列調(diào)度方法研究

楊敏華

（中興通訊股份有限公司，江蘇 南京 210012）

文章介紹了一種流量管理系統(tǒng)中的隊(duì)列調(diào)度實(shí)現(xiàn)方法，該方法適用于通信領(lǐng)域。采用此方案可以減少系統(tǒng)中緩存資源的使用量，一定程度上解決緩存資源需求過(guò)大導(dǎo)致流量管理系統(tǒng)難以實(shí)現(xiàn)的問(wèn)題。

流量管理；隊(duì)列調(diào)度；緩存

傳統(tǒng)的IP網(wǎng)絡(luò)中，轉(zhuǎn)發(fā)設(shè)備對(duì)所有的報(bào)文均采用先入先出的策略（First-in and First-out，F(xiàn)IFO）的策略進(jìn)行處理，盡最大的努力將報(bào)文送到目的地，這種方式中所有的報(bào)文無(wú)區(qū)別對(duì)待，對(duì)報(bào)文傳送的可靠性、傳送延遲等性能不能提供任何保證；但在實(shí)際應(yīng)用中，網(wǎng)絡(luò)上存在各種各樣的問(wèn)題，比如丟包現(xiàn)象、網(wǎng)絡(luò)抖動(dòng)、網(wǎng)絡(luò)延遲和網(wǎng)絡(luò)帶寬受限等等。隨著網(wǎng)絡(luò)發(fā)展和新興業(yè)務(wù)的出現(xiàn)，這些問(wèn)題已經(jīng)嚴(yán)重影響了網(wǎng)絡(luò)業(yè)務(wù)，比如VoIP，IPTV等實(shí)時(shí)業(yè)務(wù)，這些業(yè)務(wù)對(duì)傳輸延遲提出了更高的要求，如果延時(shí)過(guò)長(zhǎng)，用戶將不能接受，但相比這些業(yè)務(wù)，E-Mail等業(yè)務(wù)對(duì)時(shí)間延遲卻并不敏感；因此傳統(tǒng)的對(duì)報(bào)文無(wú)區(qū)分的處理方式已經(jīng)不能滿足現(xiàn)代網(wǎng)絡(luò)的服務(wù)質(zhì)量問(wèn)題。服務(wù)質(zhì)量（Quality of Service，QoS）技術(shù)的出現(xiàn)便致力于解決這個(gè)問(wèn)題。

在現(xiàn)代數(shù)據(jù)通信領(lǐng)域，對(duì)數(shù)據(jù)產(chǎn)品的QoS要求越來(lái)越高，由此對(duì)包處理速率、支持的隊(duì)列數(shù)、帶寬、步進(jìn)粒度等流量管理技術(shù)指標(biāo)提出了更高的要求。

由于當(dāng)前流量管理的技術(shù)指標(biāo)越來(lái)越高，特別是隊(duì)列數(shù)越來(lái)越多的情況下，實(shí)現(xiàn)流量管理所使用的緩存資源越來(lái)越多。在具體設(shè)計(jì)實(shí)現(xiàn)中，無(wú)論是在現(xiàn)場(chǎng)可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）中實(shí)現(xiàn)流量管理功能，還是在集成電路（Application Specific Integrated Circuit，ASIC）中實(shí)現(xiàn)流量管理功能，緩存資源的使用量都是一個(gè)衡量可實(shí)現(xiàn)性的重要標(biāo)準(zhǔn)。

本文提供一種隊(duì)列調(diào)度的改進(jìn)方法，采用此方案后隊(duì)列鏈表信息的緩存資源可以大幅度減少，提高流量管理系統(tǒng)的可實(shí)現(xiàn)性。

1　設(shè)計(jì)思路

1.1傳統(tǒng)隊(duì)列調(diào)度組件設(shè)計(jì)方法

如圖1所示，流量管理系統(tǒng)中最重要的組件為隊(duì)列調(diào)度組件。隊(duì)列調(diào)度組件通過(guò)隊(duì)列調(diào)度算法，協(xié)同其他組件進(jìn)行出隊(duì)調(diào)度，共同完成流量管理功能。

隊(duì)列調(diào)度組件由授權(quán)控制隊(duì)列出隊(duì)，當(dāng)獲得授權(quán)時(shí)隊(duì)列才可以出隊(duì)，授權(quán)的分配由隊(duì)列調(diào)度算法來(lái)控制；各個(gè)隊(duì)列在隊(duì)列調(diào)度算法的控制下組成鏈表；傳統(tǒng)的設(shè)計(jì)中，該鏈表根據(jù)當(dāng)前是否有效分為活動(dòng)隊(duì)列鏈表和非活動(dòng)隊(duì)列鏈表。

1.2改進(jìn)后的隊(duì)列調(diào)度實(shí)現(xiàn)方法

為了解決上述問(wèn)題，本文提出了將傳統(tǒng)設(shè)計(jì)中的活動(dòng)隊(duì)列鏈表和非活動(dòng)隊(duì)列鏈表合成為一個(gè)鏈表的方法，在該方法下調(diào)度隊(duì)列鏈表的入隊(duì)和出隊(duì)步驟如下。

1.2.1入隊(duì)步驟（見圖2）

當(dāng)隊(duì)列入隊(duì)時(shí)，加入到整個(gè)鏈表的尾部。

圖2　入隊(duì)流程圖

1.2.2出隊(duì)步驟（見圖3）

出隊(duì)步驟：當(dāng)隊(duì)列首次出隊(duì)執(zhí)行時(shí)，記下當(dāng)前隊(duì)列的尾部，標(biāo)記記為活動(dòng)隊(duì)列隊(duì)尾；隊(duì)列出隊(duì)操作執(zhí)行時(shí)，將首指針對(duì)應(yīng)隊(duì)列出隊(duì)處理；隊(duì)列出隊(duì)操作結(jié)束，執(zhí)行隊(duì)列轉(zhuǎn)移操作，根據(jù)算法的不同，決定將隊(duì)列插入到活動(dòng)隊(duì)列隊(duì)尾還是直接加入到整個(gè)鏈表尾部。如插入到活動(dòng)隊(duì)列隊(duì)尾，則將之前標(biāo)記的活動(dòng)隊(duì)列隊(duì)尾改寫為當(dāng)前隊(duì)列，否則直接加入到整個(gè)鏈表尾部。

圖3　出隊(duì)流程圖

2　結(jié)語(yǔ)

如圖4所示，傳統(tǒng)方法下，需要存儲(chǔ)活動(dòng)隊(duì)列首指針、活動(dòng)隊(duì)列尾指針、非活動(dòng)隊(duì)列首指針和非活動(dòng)隊(duì)列尾指針，如采用改進(jìn)后的方法，可以只存儲(chǔ)鏈表首指針、尾指針和活動(dòng)隊(duì)列隊(duì)尾。

圖4　傳統(tǒng)實(shí)現(xiàn)方法和改進(jìn)后的實(shí)現(xiàn)方法

本文提供的隊(duì)列調(diào)度方法，在當(dāng)前通信系統(tǒng)中隊(duì)列數(shù)大大增加的情況下，有效地降低流量管理系統(tǒng)實(shí)現(xiàn)時(shí)的緩存資源使用量，在保證高性能流量管理的前提下，使流量管理系統(tǒng)更加容易實(shí)現(xiàn)，大大提高了高性能流量管理系統(tǒng)的可實(shí)現(xiàn)性。

[1]周炯槃，龐沁華.通信原理[M].北京：北京郵電大學(xué)出版社，2005.

[2]王金明.VerilogHDL程序設(shè)計(jì)教程[M].北京：人民郵電出版社，2004.

Research on queue scheduling method in traffic management system

Yang Minhua
（ZTE Communications Share Co., Ltd., Nanjing 210012, China）

In this paper, a method of queue scheduling in traffic management system is introduced. The method is suitable for the communication field. Using this scheme can reduce the amount of cache resources, and solve the problem that the demand of the cache resources is too large to realize the traffic management system.

traffic management; queue scheduling; cache

楊敏華（1980— ），女，江蘇常州，碩士，工程師；研究方向：數(shù)據(jù)通信。