核心路由器中多端口線卡調(diào)度的設計與實現(xiàn)

　　線路接口卡是核心路由器訪問線路與訪問設備間的一種設備接口，主要實現(xiàn)路由器接口上物理層和鏈路層的功能，必須實現(xiàn)無丟包線速處理，是路由器的關鍵部件之一。線卡主要關注以下幾個方面：排隊(如FIFO、Modified Deficit Round Robin)、擁塞控制(如加權隨機早期檢測)及其它特性(如訪問列表、訪問速率、數(shù)據(jù)流統(tǒng)計)。

　　IPv6路由器系統(tǒng)結(jié)構主要由線路接口、多功能轉(zhuǎn)發(fā)處理、高速交換網(wǎng)絡、內(nèi)部通信、主控和網(wǎng)管等部分組成。ATM多端口線卡作為IPv6核心路由器的重要線路接口，需要提供8個雙向的155MbpsATM光接口，支持64個永久虛連接。多端口線卡中多路數(shù)據(jù)的合路與分路需要建立一個良好的調(diào)度機制來保證數(shù)據(jù)包的線速處理與每一路數(shù)據(jù)的公平性。本文對ATM多端口線卡輸入和輸出兩個流向上的數(shù)據(jù)包調(diào)度進行了研究，提出了一種具有一定通用性的多端口線卡調(diào)度策略的設計實現(xiàn)方案。

輸入處理流向的調(diào)度策略

　　在對多端口線卡輸入處理流向調(diào)度策略的分析中，我們以ATM多端口線卡為研究對象。ATM多端口線卡支持8個ATM155M光接口，其中每接口支持 8個永久虛連接。

　　為了保證8路64個虛連接的ATM信元傳送及處理的公平性，滿足路由器整包處理的需求，提出了基于信元的公平分片輪詢調(diào)度(Cell Round Robin Scheduling；CRR)和逐包輪詢調(diào)度(Packet Round Robin Scheduling；PRR)相結(jié)合的調(diào)度策略，如圖1所示。

圖1 輸入鏈路控制電路中的調(diào)度策略

　　采取基于信元的公平分片輪詢調(diào)度主要基于三方面考慮：一是基于信元操作，符合AAL5處理的需求；二是在采用ATM方式時，PM5380內(nèi)部的 FIFO只能夠緩存4個信元，深度有限；三是固定長度包的輪詢調(diào)度，其理論研究較成熟，也較易于實現(xiàn)，相比不定長包調(diào)度可以避免更多的意外情況，能夠確保較好的性能。

　　采取逐包輪詢調(diào)度，是為了解決AAL5中信元的處理機制路由器系統(tǒng)整包處理的機制之間的矛盾。在信元輸入處理時，將信元凈荷按其所屬的虛連接在相應的虛連接FIFO中依次緩存，直到虛連接FIFO中至少有一個完整CPCS-PDU才能被讀取；在虛連接FIFO的輸出側(cè)，采用逐包輪詢調(diào)度的方式對64 個虛連接FIFO進行讀取。在輸入流向的處理中，我們通過信元凈荷在虛連接FIFO中緩存，待完整CPCS-PDU構成后再逐包輪詢調(diào)度輸出的方式解決了上述問題。

　　整個輸入調(diào)度的實現(xiàn)參照圖1，逐個輪詢調(diào)度左側(cè)PM5380內(nèi)部的8個隊列，采用分片輪詢的方式，若輪詢到某一隊列時，其隊列深度大于53個字節(jié) (信元長度)，且對應的虛連接FIFO未滿，則輸出，否則該隊列輪空，切換到下一個隊列；同時輪詢調(diào)度右邊的64個隊列，采用逐包輪詢調(diào)度的方法，在64 個虛連接FIFO的輸出側(cè)進行高速切換讀取數(shù)據(jù)。

　　ATM多端口線卡輸入處理流向的調(diào)度策略具有一定的通用性，可以根據(jù)實際的情況，對于支持的ATM接口和虛連接數(shù)量進行改變：輸入的8個信元流可根據(jù)需要支持的接口數(shù)量由ATM接口中的8個變成16個、32個甚至更多，對更多接口的輸入信元流同樣能夠采用分片輪詢調(diào)度，根據(jù)不同虛連接提取出信元凈荷在虛連接FIFO中進行緩存；而虛連接FIFO的數(shù)量也可以根據(jù)我們需要支持的虛連接數(shù)量進行改變，采用逐包輪詢調(diào)度同樣能夠支持更多的虛連接。

輸出流向的調(diào)度策略

　　在ATM多端口線卡輸出處理流向上，由高速交換網(wǎng)絡送來的數(shù)據(jù)傳送速率最高可達2.5Gbit/s，遠大于線路接口輸出速率1244Mbit/s (8155Mbit/s)。以往的解決方案對這一問題進行了回避，采用“不能處理則丟包”的方法。這樣雖然降低了實現(xiàn)的難度，但對于高速交換網(wǎng)絡滿負荷傳送數(shù)據(jù)的情況，顯得無能為力，無法滿足QoS要求和對實時業(yè)務提供支持。由此可見，緩存管理機制和調(diào)度策略在此的重要性。

我們在以往解決方案的基礎上進行了改進，提出了基于門限的調(diào)度策略(Threshold Based Scheduling Policy；TBSP)、帶有優(yōu)先級的逐包輪詢調(diào)策略(Racket Round Robinwith Priority；PPRR)、分類隨機早期探測機制(Classification Based Random Early Detection；CBRED)和公平分片輪詢調(diào)度策略(Cell Round Robin Scheduling；CRR)相結(jié)合的方案。

　　如圖2所示，圖左側(cè)是輸出緩存中數(shù)據(jù)包隊列，圖右側(cè)是本接口的8個線路接口FIFO，用于存儲去往各個線路接口的數(shù)據(jù)包，數(shù)據(jù)包隊列和線路接口 FIFO中間是調(diào)度機。根據(jù)數(shù)據(jù)包頭所帶的線路接口指示，數(shù)據(jù)包被送往相應的FIFO中。假設輸出緩存隊列隊頭的數(shù)據(jù)包要送往FIFO01，而FIFO1 已滿不讓寫入，就會發(fā)生隊頭阻塞。此時若是采取等待直到FIFO1允

　　(1)在輸出緩存中設置門限T；
(2)當隊列深度小于T時，若發(fā)生隊頭阻塞，數(shù)據(jù)包暫時存放在輸入緩存中；
(3)在隊列深度到達T時若隊頭對應的FIFO滿指示失效，則讀出數(shù)據(jù)包并寫入相應FIFO；
(4)當隊列深度到達T時若隊頭對應的FIFO滿指示依然有效，讀出該數(shù)據(jù)包并丟棄。

圖2 TBSP調(diào)度示意圖

　　以上只是解決了輸出緩存中數(shù)據(jù)包的輸出調(diào)度問題，而處理機過來的協(xié)議包也要經(jīng)過調(diào)度送往不同線路接口。由于協(xié)議包的速度遠遠小于數(shù)據(jù)包的速度，也小于線路接口的傳輸速度，因此不存在丟包問題。但考慮到協(xié)議包要優(yōu)先發(fā)送，我們便提出了帶有優(yōu)先級的逐包輪詢調(diào)度策略(Racket Round Robinwith Priority；PPRR)。

　　完成優(yōu)先輪詢調(diào)度的合路數(shù)據(jù)包需在隊列里進行緩存，而傳統(tǒng)的先進先出(FIFO)隊列管理使用簡單的尾丟棄策略，使得隊列長度成波浪形變化，導致路由器的吞吐量降低和通信的延遲抖動非常大。為避免這種情況發(fā)生，因此輸出緩存管理采用了分類隨機早期探測機制(Classification Based Random Early Detection；CBRED)，其原理如圖3所示。根據(jù)Diff-Serv模型的丟包策略，在多端口線卡中將所有業(yè)務根據(jù)其對包丟失率的要求分為三類，分別為低優(yōu)先級、中優(yōu)先級和高優(yōu)先級。

圖3 分類隨機早期探測(CBRED)原理示意圖

　　在輸出緩存中設立兩個門限M1、M2(M1

圖4 輸出存儲器管理機制與調(diào)度策略

　　整個輸出鏈路控制電路設計采取的存儲器管理機制和調(diào)度策略如圖4所示(隊列0表示輸入緩存中的單播數(shù)據(jù)包，隊列1表示組播數(shù)據(jù)包，隊列2表示協(xié)議包)，其描述如下：

　　(1)隊列0、隊列1或隊列2每讀出一個整包后，優(yōu)先查詢隊列2，其次是隊列0，隊列1的優(yōu)先級最低；
(2)若隊列2有整包指示且相應FIFO滿指示無效，則讀出整包并寫入相應FIFO；
(3)若隊列2有整包指示但相應FIFO滿指示有效，先查詢隊列0狀態(tài)，隊列0的包調(diào)度也采取TBSP策略，如果隊列0仍未被讀取，則查詢隊列1狀態(tài)，隊列1的包調(diào)度同樣采取TBSP策略；
(4)優(yōu)先逐包輪詢調(diào)度后的合路包在輸出緩存中進行緩存，采用分類隨機早期探測機制對緩存進行管理；
(5)輸出鏈路中的8個FIFO與商用芯片之間采用CRR調(diào)度策略。

　　在優(yōu)先逐包輪詢調(diào)度的實現(xiàn)中，我們設置了一系列的組合邏輯來完成上述的功能，如圖5所示。協(xié)議數(shù)據(jù)、單播和組播FIFO的讀取優(yōu)先級由優(yōu)先調(diào)度控制，當協(xié)議FIFO中有完整包時且對應接口FIFO未滿，則輸出該協(xié)議包，直到協(xié)議FIFO中無完整包或?qū)涌贔IFO已滿，將優(yōu)先級交給單播 FIFO；如果單播FIFO內(nèi)有完整包且對應接口FIFO未滿，則輸出一個完整的單播包；如果對應FIFO滿，則由門限設置單元提供的門限T分別與單播 FIFO內(nèi)數(shù)據(jù)深度比較，決定當查詢到單播FIFO時，是否進行讀取或丟包操作。我們采用比較器來實現(xiàn)深度的比較，比較器的輸出為3位，每一位指示一種狀態(tài)，即單播FIFO內(nèi)數(shù)據(jù)深度是大于、小于或等于門限T。如果小于T，對應的接口FIFO滿，則等待，將優(yōu)先級交給組播FIFO；如果大于或等于T，對應接口FIFO滿失效，則輸出該FIFO的一個包，將優(yōu)先級交給組播FIFO，否則丟棄當前的數(shù)據(jù)包，也將優(yōu)先級交給組播FIFO。

對組播FIFO執(zhí)行的操作與單播的情況類似，在這不再贅述。循環(huán)一圈后，優(yōu)先級又交還給協(xié)議FIFO，重新開始上述操作。TBSP門限T的設置需基于兩方面的綜合考慮：網(wǎng)絡中各種包長的分布和本模塊要求的處理時間。在實現(xiàn)中，我們使用了FPGA片內(nèi)的2塊BLOCKSelectRAM組成TBSPFIFO(TBSPFIFO的位寬為36位，深度為1000)，通過實際中多次的單板調(diào)試和系統(tǒng)聯(lián)調(diào)，并對測試結(jié)果進行分析比較后，我們把T的門限設為640，這是隊列深度為1000的時候，實際運行中的最優(yōu)值。

圖5 優(yōu)先逐包輪詢調(diào)度實現(xiàn)流程

　　在分類隨機早期探測機制的具體電路實現(xiàn)中，我們根據(jù)兩級丟包門限M1、M2控制QoSFIFO的寫入操作，以保證更高優(yōu)先級包的可靠傳輸。如圖6所示，我們在對QoSF

圖6 分類隨機早期探測實現(xiàn)示意圖

　　ATM多端口線卡輸出處理流向的調(diào)度策略同樣具有一定的通用性,可以根據(jù)實際的情況,對優(yōu)先逐包調(diào)度隊列數(shù)量和輸出接口數(shù)量進行改變,滿足多種需求。

測試結(jié)果與分析

　　ATM多端口線卡參加了國家863“十五”期間重大課題“高性能IPv6路由器基礎平臺及實驗系統(tǒng)”的系統(tǒng)測試，為高性能IPv6路由器提供ATM信元與IP數(shù)據(jù)包的數(shù)據(jù)格式轉(zhuǎn)換的功能，其吞吐量測試結(jié)果見圖7。根據(jù)測試結(jié)果，當接口平均速率小于1244Mbit/s時，在測試中各種包長的條件下(40byte～1518byte)，ATM多端口線卡實現(xiàn)了無丟包線速處理。

　　ATM多端口線卡的輸入鏈路控制電路中應用并實現(xiàn)了分片輪詢調(diào)度和逐包輪詢調(diào)度相結(jié)合的策略，結(jié)合整個線卡的測試結(jié)果，充分證明這種策略是切實可行的，且能保證效率；輸出鏈路控制電路中將TBSP策略與CBRED機制有機地結(jié)合起來，可以較好提高系統(tǒng)吞吐量和降低丟包率，實現(xiàn)QoS和實時業(yè)務的時延控制，并且在工程上是易于實現(xiàn)的。

小結(jié)

　　本文中，為了保證一定的公平性，滿足整包處理的需要，提出了公平的分片輪詢(CRR)和即時的逐包輪詢(PRR)相結(jié)合的調(diào)度策略；分析了多端口線卡調(diào)度和存儲器管理中存在的問題，提出了一種基于門限的調(diào)度策略(TBSP)，較好地解決了降低系統(tǒng)丟包率和提高吞吐量的問題；為了滿足QoS要求和保證實時業(yè)務的時延特性，將TBSP策略與CBRED機制有機地結(jié)合起來，可以降低系統(tǒng)丟包率，而且能夠在一定程度上滿足不同業(yè)務的QoS要求。本文中存儲器管理機制和調(diào)度策略均在ATM多端口線卡中得以工程實現(xiàn)，且具有通用性，在支持的輸入接口和連接數(shù)量上進行增減，可以滿足多種多端口線卡的調(diào)度需求。