核心路由器中多端口線卡調(diào)度的設(shè)計(jì)與實(shí)現(xiàn)
加入技術(shù)交流群
線路接口卡是核心路由器訪問線路與訪問設(shè)備間的一種設(shè)備接口，主要實(shí)現(xiàn)路由器接口上物理層和鏈路層的功能，必須實(shí)現(xiàn)無丟包線速處理，是路由器的關(guān)鍵部件之一。線卡主要關(guān)注以下幾個(gè)方面：排隊(duì)(如FIFO、Modified Deficit Round Robin)、擁塞控制(如加權(quán)隨機(jī)早期檢測)及其它特性(如訪問列表、訪問速率、數(shù)據(jù)流統(tǒng)計(jì))。
IPv6路由器系統(tǒng)結(jié)構(gòu)主要由線路接口、多功能轉(zhuǎn)發(fā)處理、高速交換網(wǎng)絡(luò)、內(nèi)部通信、主控和網(wǎng)管等部分組成。ATM多端口線卡作為IPv6核心路由器的重要線路接口，需要提供8個(gè)雙向的155MbpsATM光接口，支持64個(gè)永久虛連接。多端口線卡中多路數(shù)據(jù)的合路與分路需要建立一個(gè)良好的調(diào)度機(jī)制來保證數(shù)據(jù)包的線速處理與每一路數(shù)據(jù)的公平性。本文對ATM多端口線卡輸入和輸出兩個(gè)流向上的數(shù)據(jù)包調(diào)度進(jìn)行了研究，提出了一種具有一定通用性的多端口線卡調(diào)度策略的設(shè)計(jì)實(shí)現(xiàn)方案。
輸入處理流向的調(diào)度策略
在對多端口線卡輸入處理流向調(diào)度策略的分析中，我們以ATM多端口線卡為研究對象。ATM多端口線卡支持8個(gè)ATM155M光接口，其中每接口支持 8個(gè)永久虛連接。
為了保證8路64個(gè)虛連接的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方式時(shí)，PM5380內(nèi)部的 FIFO只能夠緩存4個(gè)信元，深度有限；三是固定長度包的輪詢調(diào)度，其理論研究較成熟，也較易于實(shí)現(xiàn)，相比不定長包調(diào)度可以避免更多的意外情況，能夠確保較好的性能。
采取逐包輪詢調(diào)度，是為了解決AAL5中信元的處理機(jī)制路由器系統(tǒng)整包處理的機(jī)制之間的矛盾。在信元輸入處理時(shí)，將信元凈荷按其所屬的虛連接在相應(yīng)的虛連接FIFO中依次緩存，直到虛連接FIFO中至少有一個(gè)完整CPCS-PDU才能被讀?。辉谔撨B接FIFO的輸出側(cè)，采用逐包輪詢調(diào)度的方式對64 個(gè)虛連接FIFO進(jìn)行讀取。在輸入流向的處理中，我們通過信元凈荷在虛連接FIFO中緩存，待完整CPCS-PDU構(gòu)成后再逐包輪詢調(diào)度輸出的方式解決了上述問題。
整個(gè)輸入調(diào)度的實(shí)現(xiàn)參照圖1，逐個(gè)輪詢調(diào)度左側(cè)PM5380內(nèi)部的8個(gè)隊(duì)列，采用分片輪詢的方式，若輪詢到某一隊(duì)列時(shí)，其隊(duì)列深度大于53個(gè)字節(jié) (信元長度)，且對應(yīng)的虛連接FIFO未滿，則輸出，否則該隊(duì)列輪空，切換到下一個(gè)隊(duì)列；同時(shí)輪詢調(diào)度右邊的64個(gè)隊(duì)列，采用逐包輪詢調(diào)度的方法，在64 個(gè)虛連接FIFO的輸出側(cè)進(jìn)行高速切換讀取數(shù)據(jù)。
ATM多端口線卡輸入處理流向的調(diào)度策略具有一定的通用性，可以根據(jù)實(shí)際的情況，對于支持的ATM接口和虛連接數(shù)量進(jìn)行改變：輸入的8個(gè)信元流可根據(jù)需要支持的接口數(shù)量由ATM接口中的8個(gè)變成16個(gè)、32個(gè)甚至更多，對更多接口的輸入信元流同樣能夠采用分片輪詢調(diào)度，根據(jù)不同虛連接提取出信元凈荷在虛連接FIFO中進(jìn)行緩存；而虛連接FIFO的數(shù)量也可以根據(jù)我們需要支持的虛連接數(shù)量進(jìn)行改變，采用逐包輪詢調(diào)度同樣能夠支持更多的虛連接。
輸出流向的調(diào)度策略
在ATM多端口線卡輸出處理流向上，由高速交換網(wǎng)絡(luò)送來的數(shù)據(jù)傳送速率最高可達(dá)2.5Gbit/s，遠(yuǎn)大于線路接口輸出速率1244Mbit/s (8155Mbit/s)。以往的解決方案對這一問題進(jìn)行了回避，采用“不能處理則丟包”的方法。這樣雖然降低了實(shí)現(xiàn)的難度，但對于高速交換網(wǎng)絡(luò)滿負(fù)荷傳送數(shù)據(jù)的情況，顯得無能為力，無法滿足QoS要求和對實(shí)時(shí)業(yè)務(wù)提供支持。由此可見，緩存管理機(jī)制和調(diào)度策略在此的重要性。
我們在以往解決方案的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了基于門限的調(diào)度策略(Threshold Based Scheduling Policy；TBSP)、帶有優(yōu)先級的逐包輪詢調(diào)策略(Racket Round Robinwith Priority；PPRR)、分類隨機(jī)早期探測機(jī)制(Classification Based Random Early Detection；CBRED)和公平分片輪詢調(diào)度策略(Cell Round Robin Scheduling；CRR)相結(jié)合的方案。
如圖2所示，圖左側(cè)是輸出緩存中數(shù)據(jù)包隊(duì)列，圖右側(cè)是本接口的8個(gè)線路接口FIFO，用于存儲去往各個(gè)線路接口的數(shù)據(jù)包，數(shù)據(jù)包隊(duì)列和線路接口 FIFO中間是調(diào)度機(jī)。根據(jù)數(shù)據(jù)包頭所帶的線路接口指示，數(shù)據(jù)包被送往相應(yīng)的FIFO中。假設(shè)輸出緩存隊(duì)列隊(duì)頭的數(shù)據(jù)包要送往FIFO01，而FIFO1 已滿不讓寫入，就會發(fā)生隊(duì)頭阻塞。此時(shí)若是采取等待直到FIFO1允
(1)在輸出緩存中設(shè)置門限T；
(2)當(dāng)隊(duì)列深度小于T時(shí)，若發(fā)生隊(duì)頭阻塞，數(shù)據(jù)包暫時(shí)存放在輸入緩存中；
(3)在隊(duì)列深度到達(dá)T時(shí)若隊(duì)頭對應(yīng)的FIFO滿指示失效，則讀出數(shù)據(jù)包并寫入相應(yīng)FIFO；
(4)當(dāng)隊(duì)列深度到達(dá)T時(shí)若隊(duì)頭對應(yīng)的FIFO滿指示依然有效，讀出該數(shù)據(jù)包并丟棄。
圖2 TBSP調(diào)度示意圖
以上只是解決了輸出緩存中數(shù)據(jù)包的輸出調(diào)度問題，而處理機(jī)過來的協(xié)議包也要經(jīng)過調(diào)度送往不同線路接口。由于協(xié)議包的速度遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)包的速度，也小于線路接口的傳輸速度，因此不存在丟包問題。但考慮到協(xié)議包要優(yōu)先發(fā)送，我們便提出了帶有優(yōu)先級的逐包輪詢調(diào)度策略(Racket Round Robinwith Priority；PPRR)。
完成優(yōu)先輪詢調(diào)度的合路數(shù)據(jù)包需在隊(duì)列里進(jìn)行緩存，而傳統(tǒng)的先進(jìn)先出(FIFO)隊(duì)列管理使用簡單的尾丟棄策略，使得隊(duì)列長度成波浪形變化，導(dǎo)致路由器的吞吐量降低和通信的延遲抖動非常大。為避免這種情況發(fā)生，因此輸出緩存管理采用了分類隨機(jī)早期探測機(jī)制(Classification Based Random Early Detection；CBRED)，其原理如圖3所示。根據(jù)Diff-Serv模型的丟包策略，在多端口線卡中將所有業(yè)務(wù)根據(jù)其對包丟失率的要求分為三類，分別為低優(yōu)先級、中優(yōu)先級和高優(yōu)先級。
圖3 分類隨機(jī)早期探測(CBRED)原理示意圖
在輸出緩存中設(shè)立兩個(gè)門限M1、M2(M1 整個(gè)輸出鏈路控制電路設(shè)計(jì)采取的存儲器管理機(jī)制和調(diào)度策略如圖4所示(隊(duì)列0表示輸入緩存中的單播數(shù)據(jù)包，隊(duì)列1表示組播數(shù)據(jù)包，隊(duì)列2表示協(xié)議包)，其描述如下： (1)隊(duì)列0、隊(duì)列1或隊(duì)列2每讀出一個(gè)整包后，優(yōu)先查詢隊(duì)列2，其次是隊(duì)列0，隊(duì)列1的優(yōu)先級最低； 在優(yōu)先逐包輪詢調(diào)度的實(shí)現(xiàn)中，我們設(shè)置了一系列的組合邏輯來完成上述的功能，如圖5所示。協(xié)議數(shù)據(jù)、單播和組播FIFO的讀取優(yōu)先級由優(yōu)先調(diào)度控制，當(dāng)協(xié)議FIFO中有完整包時(shí)且對應(yīng)接口FIFO未滿，則輸出該協(xié)議包，直到協(xié)議FIFO中無完整包或?qū)?yīng)接口FIFO已滿，將優(yōu)先級交給單播 FIFO；如果單播FIFO內(nèi)有完整包且對應(yīng)接口FIFO未滿，則輸出一個(gè)完整的單播包；如果對應(yīng)FIFO滿，則由門限設(shè)置單元提供的門限T分別與單播 FIFO內(nèi)數(shù)據(jù)深度比較，決定當(dāng)查詢到單播FIFO時(shí)，是否進(jìn)行讀取或丟包操作。我們采用比較器來實(shí)現(xiàn)深度的比較，比較器的輸出為3位，每一位指示一種狀態(tài)，即單播FIFO內(nèi)數(shù)據(jù)深度是大于、小于或等于門限T。如果小于T，對應(yīng)的接口FIFO滿，則等待，將優(yōu)先級交給組播FIFO；如果大于或等于T，對應(yīng)接口FIFO滿失效，則輸出該FIFO的一個(gè)包，將優(yōu)先級交給組播FIFO，否則丟棄當(dāng)前的數(shù)據(jù)包，也將優(yōu)先級交給組播FIFO。 對組播FIFO執(zhí)行的操作與單播的情況類似，在這不再贅述。循環(huán)一圈后，優(yōu)先級又交還給協(xié)議FIFO，重新開始上述操作。TBSP門限T的設(shè)置需基于兩方面的綜合考慮：網(wǎng)絡(luò)中各種包長的分布和本模塊要求的處理時(shí)間。在實(shí)現(xiàn)中，我們使用了FPGA片內(nèi)的2塊BLOCKSelectRAM組成TBSPFIFO(TBSPFIFO的位寬為36位，深度為1000)，通過實(shí)際中多次的單板調(diào)試和系統(tǒng)聯(lián)調(diào)，并對測試結(jié)果進(jìn)行分析比較后，我們把T的門限設(shè)為640，這是隊(duì)列深度為1000的時(shí)候，實(shí)際運(yùn)行中的最優(yōu)值。 圖5 優(yōu)先逐包輪詢調(diào)度實(shí)現(xiàn)流程 在分類隨機(jī)早期探測機(jī)制的具體電路實(shí)現(xiàn)中，我們根據(jù)兩級丟包門限M1、M2控制QoSFIFO的寫入操作，以保證更高優(yōu)先級包的可靠傳輸。如圖6所示，我們在對QoSF 
圖4 輸出存儲器管理機(jī)制與調(diào)度策略
(2)若隊(duì)列2有整包指示且相應(yīng)FIFO滿指示無效，則讀出整包并寫入相應(yīng)FIFO；
(3)若隊(duì)列2有整包指示但相應(yīng)FIFO滿指示有效，先查詢隊(duì)列0狀態(tài)，隊(duì)列0的包調(diào)度也采取TBSP策略，如果隊(duì)列0仍未被讀取，則查詢隊(duì)列1狀態(tài)，隊(duì)列1的包調(diào)度同樣采取TBSP策略；
(4)優(yōu)先逐包輪詢調(diào)度后的合路包在輸出緩存中進(jìn)行緩存，采用分類隨機(jī)早期探測機(jī)制對緩存進(jìn)行管理；
(5)輸出鏈路中的8個(gè)FIFO與商用芯片之間采用CRR調(diào)度策略。
IFO進(jìn)行寫入整包的之前監(jiān)控QoSFIFO內(nèi)有效數(shù)據(jù)的長度，與門限M1、M2比較，根據(jù)比較的結(jié)果結(jié)合當(dāng)前包內(nèi)部格式頭部的優(yōu)先級字段(包優(yōu)先級由轉(zhuǎn)發(fā)處理提供，并在ATM接口將8個(gè)優(yōu)先級轉(zhuǎn)化為3個(gè)丟包優(yōu)先級)，決定當(dāng)前數(shù)據(jù)包是否寫入QoSFIFO。若當(dāng)QoSFIFO內(nèi)緩存隊(duì)列深度不超過門限M1時(shí)，所有到達(dá)的包均寫入QoSFIFO；當(dāng)緩存隊(duì)列的深度超過門限M1但不超過門限M2時(shí)，丟棄低優(yōu)先級的包，中、高優(yōu)先級的包仍寫入QoSFIFO；若一個(gè)緩存隊(duì)列的深度已超過門限M2，但緩存隊(duì)列未滿時(shí)，丟棄低、中優(yōu)先級的包，高優(yōu)先級的包仍寫入QoSFIFO；一旦緩存隊(duì)列滿時(shí)，丟棄所有包。QoSFIFO的寫使能信號是控制寫入數(shù)據(jù)和丟棄數(shù)據(jù)的關(guān)鍵，我們采用比較結(jié)果和優(yōu)先級字段結(jié)合的方式，由包頭信號同步置位，包尾信號延遲一個(gè)周期同步清零產(chǎn)生一個(gè)數(shù)據(jù)包長的高電平，與寫入判決信號和延遲一個(gè)周期的包尾信號共同產(chǎn)生的寫允許信號相與產(chǎn)生FIFO的寫使能。這樣就實(shí)現(xiàn)了寫入或丟棄的數(shù)據(jù)正好是一個(gè)整包，避免影響對其它數(shù)據(jù)包的正常操作。關(guān)于CBRED機(jī)制的兩個(gè)門限M1和M2，對此僅作定性考慮，結(jié)合工程經(jīng)驗(yàn)，設(shè)置M1= L/2，M2=3L/4，其中L=2000(所選FIFO的深度)。這一結(jié)果是在實(shí)際測試中，通過不斷的分析比較得出的最優(yōu)值。
圖6 分類隨機(jī)早期探測實(shí)現(xiàn)示意圖
ATM多端口線卡輸出處理流向的調(diào)度策略同樣具有一定的通用性,可以根據(jù)實(shí)際的情況,對優(yōu)先逐包調(diào)度隊(duì)列數(shù)量和輸出接口數(shù)量進(jìn)行改變,滿足多種需求。
測試結(jié)果與分析
ATM多端口線卡參加了國家863“十五”期間重大課題“高性能IPv6路由器基礎(chǔ)平臺及實(shí)驗(yàn)系統(tǒng)”的系統(tǒng)測試，為高性能IPv6路由器提供ATM信元與IP數(shù)據(jù)包的數(shù)據(jù)格式轉(zhuǎn)換的功能，其吞吐量測試結(jié)果見圖7。根據(jù)測試結(jié)果，當(dāng)接口平均速率小于1244Mbit/s時(shí)，在測試中各種包長的條件下(40byte～1518byte)，ATM多端口線卡實(shí)現(xiàn)了無丟包線速處理。
ATM多端口線卡的輸入鏈路控制電路中應(yīng)用并實(shí)現(xiàn)了分片輪詢調(diào)度和逐包輪詢調(diào)度相結(jié)合的策略，結(jié)合整個(gè)線卡的測試結(jié)果，充分證明這種策略是切實(shí)可行的，且能保證效率；輸出鏈路控制電路中將TBSP策略與CBRED機(jī)制有機(jī)地結(jié)合起來，可以較好提高系統(tǒng)吞吐量和降低丟包率，實(shí)現(xiàn)QoS和實(shí)時(shí)業(yè)務(wù)的時(shí)延控制，并且在工程上是易于實(shí)現(xiàn)的。
小結(jié)
本文中，為了保證一定的公平性，滿足整包處理的需要，提出了公平的分片輪詢(CRR)和即時(shí)的逐包輪詢(PRR)相結(jié)合的調(diào)度策略；分析了多端口線卡調(diào)度和存儲器管理中存在的問題，提出了一種基于門限的調(diào)度策略(TBSP)，較好地解決了降低系統(tǒng)丟包率和提高吞吐量的問題；為了滿足QoS要求和保證實(shí)時(shí)業(yè)務(wù)的時(shí)延特性，將TBSP策略與CBRED機(jī)制有機(jī)地結(jié)合起來，可以降低系統(tǒng)丟包率，而且能夠在一定程度上滿足不同業(yè)務(wù)的QoS要求。本文中存儲器管理機(jī)制和調(diào)度策略均在ATM多端口線卡中得以工程實(shí)現(xiàn)，且具有通用性，在支持的輸入接口和連接數(shù)量上進(jìn)行增減，可以滿足多種多端口線卡的調(diào)度需求。
評論