基于FPGA的輪詢(xún)合路的設計和實(shí)現

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

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

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

圖1 輸入合路模塊中的輪詢(xún)調度策略

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

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

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

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

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

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

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

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

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

圖3 DRR合路調度單元仿真波形圖

仿真結果顯示這種采用分片輪詢(xún)和欠賬輪詢(xún)的結合的合路調度策略設計可以達到性能需求，確保變長(cháng)分組合路調度的公平性和穩定性。

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

參考文獻：
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邊計年,薛宏熙.用VHDL設計電子線(xiàn)路[M].北京：清華大學(xué)出版社，2000