基于FPGA的輪詢合路的設(shè)計(jì)和實(shí)現(xiàn)

摘 要：針對(duì)高密度接口設(shè)計(jì)中基于字節(jié)處理和整包處理的轉(zhuǎn)換問題，本文提出了分片輪詢調(diào)度和改進(jìn)式欠賬輪詢調(diào)度相結(jié)合的調(diào)度策略，該策略在很大程度上保證了公平性和穩(wěn)定性。仿真結(jié)果顯示，該設(shè)計(jì)完全符合要求。
關(guān)鍵詞：調(diào)度 分片輪詢 欠賬輪詢 FPGA

1、引言
4X2.5G線路接口卡是T比特路由器的一種重要接口，屬于高密度線路接口，這種接口是當(dāng)前路由器設(shè)計(jì)中的一個(gè)重點(diǎn)和難點(diǎn)。所謂高密度，指的是在一塊繞路接口卡上提供多個(gè)接口。之所以出現(xiàn)高密度線路接口的需求，是因?yàn)榛ヂ?lián)網(wǎng)的規(guī)模不斷的擴(kuò)大，對(duì)路由器的接入能力提出了日益增大的需求，如果還沿用單板單接口的設(shè)計(jì)方法將導(dǎo)致路由器的物理規(guī)模不斷的擴(kuò)大，不符合現(xiàn)代設(shè)備發(fā)展的趨勢(shì)。在4X2.5G線路接口卡的設(shè)計(jì)中，筆者采用單片多路的SDH處理芯片S19202集中完成物理層的處理，然后根據(jù)整體設(shè)計(jì)方案在其后端進(jìn)行數(shù)據(jù)的技術(shù)處理。針對(duì)多路報(bào)文在送往轉(zhuǎn)發(fā)單元時(shí)的公平性和穩(wěn)定性需求，以及SDH芯片S19202的特點(diǎn)，提出了輸入報(bào)文合路采用分片輪詢(Cell Round Robin Scheduling;CRR)和改進(jìn)的欠賬式輪詢調(diào)度(Defect Round Robin Scheduling;DRR)相結(jié)合的調(diào)度策略。這種調(diào)度策略保證了4路POS接口之間的公平性和整包處理的穩(wěn)定性，并且在工程上易于實(shí)現(xiàn)。本文第2節(jié)詳細(xì)闡述了該調(diào)度策略的設(shè)計(jì)與實(shí)現(xiàn)過程，第3節(jié)對(duì)全文進(jìn)行了總結(jié)。

2、輪詢調(diào)度的設(shè)計(jì)與實(shí)現(xiàn)
在4X2.5G線路接口卡的設(shè)計(jì)中，采用了AMCC公司的SDH處理芯片S19202進(jìn)行鏈路層數(shù)據(jù)處理，該芯片的特點(diǎn)是4個(gè)接口共享同一組接收總線和同一組發(fā)送總線，另外提供通道選擇信號(hào)來指示當(dāng)前工作的線路接口號(hào)，其輸入端每個(gè)接口的緩存大小最大只有1k字節(jié)，根本不足以緩存一個(gè)長的整包(最長包可達(dá)到1500字節(jié))。針對(duì)這個(gè)特點(diǎn)，設(shè)計(jì)中使用了在S19202后端的FPGA進(jìn)行分片輪詢和整包接收的處理，保證了4個(gè)接口的公平性和穩(wěn)定性；針對(duì)4個(gè)接口的報(bào)文共享一條到轉(zhuǎn)發(fā)的通路時(shí)，由于各接口的報(bào)文長度差異，可能造成的不公平和不穩(wěn)定，提出了一種改進(jìn)式欠賬輪詢的調(diào)度策略。通過分片輪詢和改進(jìn)式欠賬輪詢的結(jié)合使用，保證了4個(gè)接口合路的公平性和穩(wěn)定性。

圖1 輸入合路模塊中的輪詢調(diào)度策略

輸入合路模塊中聯(lián)合調(diào)度策略的原理如圖1所示，對(duì)SDH芯片S19202送出的4路數(shù)據(jù)進(jìn)行分片逐個(gè)輪詢，并緩存進(jìn)相應(yīng)通道的整包接收FIFO，相應(yīng)通道若沒有數(shù)據(jù)則輪空，轉(zhuǎn)入下一通道；整包輪詢合路調(diào)度則逐個(gè)輪詢4個(gè)整包FIFO，若該FIFO有整包，則在每一輪詢周期發(fā)送一個(gè)整包，否則輪空。

在該聯(lián)合調(diào)度策略中，分片輪詢調(diào)度比較容易實(shí)現(xiàn)，僅需在FPGA實(shí)現(xiàn)的最前端設(shè)計(jì)一個(gè)輪詢機(jī)，利用SDH芯片S19202提供的通道指示信號(hào)(在FPGA設(shè)計(jì)用SRX_CHANNEL表示)對(duì)每個(gè)通道進(jìn)行固定的輪詢?cè)L問，有數(shù)據(jù)則存入相應(yīng)的通道整包接收FIFO即可。而整包調(diào)度是使每個(gè)通道得到服務(wù)的公平性和穩(wěn)定性的關(guān)鍵，它直接決定著接收服務(wù)的通道所得到的服務(wù)帶寬、時(shí)延以及時(shí)延抖動(dòng)等性能指標(biāo)，因此本文把研究重點(diǎn)放在了整包調(diào)度的設(shè)計(jì)與實(shí)現(xiàn)上。

目前，在整包調(diào)度上，主要的調(diào)度算法有先到先服務(wù)(FCFS)、逐包調(diào)度(PRR)、公平排隊(duì)、虛時(shí)鐘、加權(quán)循環(huán)服務(wù)(WRR)等多種策略。由于多數(shù)調(diào)度方式在包長不定的IP網(wǎng)絡(luò)中實(shí)現(xiàn)時(shí)遇到了困難，為此，M.Sheedhar等提出了適用于IP網(wǎng)絡(luò)的欠帳式循環(huán)調(diào)度(DRR)，該算法由于其較低的實(shí)現(xiàn)復(fù)雜度、良好的公平性及穩(wěn)定性而被經(jīng)常采用。

但是，DDR算法直接用于高密度線卡設(shè)計(jì)中會(huì)有一定的問題。首先，DRR算法是針對(duì)集成服務(wù)網(wǎng)絡(luò)中不同業(yè)務(wù)需求而提出的，在一般應(yīng)用中由于隊(duì)列數(shù)較多，所以需要減小隊(duì)列數(shù)，而在我們的設(shè)計(jì)中只有4個(gè)隊(duì)列，所以不需要減小隊(duì)列數(shù)；其次，在線卡設(shè)計(jì)中合路報(bào)文的包長無法直接給出，如果一定要加上包長則需用多加一級(jí)緩存，這就增大了設(shè)計(jì)復(fù)雜度也提高了成本；同樣由于經(jīng)典DDR算法嚴(yán)格要求儲(chǔ)蓄計(jì)數(shù)器值大于隊(duì)頭包長才輸出，這種不允許帶寬透支只允許盈余的要求會(huì)導(dǎo)致出現(xiàn)有包但是無法輸出的現(xiàn)象。

根據(jù)4X2.5G線路接口的實(shí)際情況和DDR算法的思想，我們可以給出如下適合高密度POS接口使用的改進(jìn)式欠賬式循環(huán)調(diào)度策略：
1) 逐包輪詢；

采用這種改進(jìn)的DRR算法下，可以保證在變長包的情況下，各個(gè)接口的整包緩存隊(duì)列在報(bào)文合路時(shí)公平的帶寬，確保合路調(diào)度的穩(wěn)定運(yùn)行。

DRR整包輪詢合路的基本工作過程為：輪詢4個(gè)整包緩存隊(duì)列，每讀取一個(gè)整包都判斷該包是否是協(xié)議包，如果是協(xié)議包，則按照上交CPU報(bào)文格式送協(xié)議FIFO，如果是需要轉(zhuǎn)發(fā)的報(bào)文，則按照轉(zhuǎn)發(fā)報(bào)文格式送數(shù)據(jù)報(bào)文FIFO。

調(diào)度機(jī)輪詢到某個(gè)隊(duì)列時(shí)，為該隊(duì)列的儲(chǔ)蓄計(jì)數(shù)器加上40；然后判斷該隊(duì)列是否為空，如果為空，則馬上轉(zhuǎn)向下一個(gè)隊(duì)列；如果非空，則判斷當(dāng)前該隊(duì)列是否有整包，如果當(dāng)前該隊(duì)列無整包，則轉(zhuǎn)到下一個(gè)隊(duì)列；否則，如果該隊(duì)列目前有整包則輸出該隊(duì)列的隊(duì)頭包到合路隊(duì)列，同時(shí)該路的儲(chǔ)蓄計(jì)數(shù)器的值要減去輸出報(bào)文的長度；然后重復(fù)上述過程，直到該隊(duì)列無整包或者隊(duì)列的儲(chǔ)蓄計(jì)數(shù)器的值小于40時(shí)跳轉(zhuǎn)到下一隊(duì)列服務(wù)，其詳細(xì)工作流程如圖2 所示：

圖2 改進(jìn)的DRR合路調(diào)度流程圖
DRR合路調(diào)度單元已在ALTERA公司的quartusII4.1環(huán)境下用VHDL編程實(shí)現(xiàn)，其仿真波形如圖3所示：

圖3 DRR合路調(diào)度單元仿真波形圖

仿真結(jié)果顯示這種采用分片輪詢和欠賬輪詢的結(jié)合的合路調(diào)度策略設(shè)計(jì)可以達(dá)到性能需求，確保變長分組合路調(diào)度的公平性和穩(wěn)定性。

3、結(jié)束語
根據(jù)SDH芯片的S19202的特點(diǎn)和性能要求，通過在FPGA內(nèi)部編程實(shí)現(xiàn)分片輪詢和改進(jìn)式欠賬輪詢結(jié)合的調(diào)度策略，保證了4X2.5G線路接口卡輸入端各個(gè)接口合路的公平性和穩(wěn)定性。經(jīng)測(cè)試該設(shè)計(jì)性能穩(wěn)定，整個(gè)工作流程簡單實(shí)用，符合設(shè)計(jì)要求。

參考文獻(xiàn)：
1 stratix_GX_datasheet. Altera公司，2003
2 Stratix Device Handbook. Altera公司，2004
3 s19202cbi30_ganges_prod_rev3.1_cust. AMCC公司，2004
4 S3485_DS0181_v4_03. AMCC公司，2004
5邊計(jì)年,薛宏熙.用VHDL設(shè)計(jì)電子線路[M].北京：清華大學(xué)出版社，2000