基于變長交換的ISP算法

基于變長交換的ISP算法

傳統(tǒng)的crossbar采用簡單的先進先出(First In First Out, FIFO)輸入隊列技術，從而不可避免地產(chǎn)生了對頭阻塞(Head Of Line, HOL)現(xiàn)象。HOL極大地降低了crossbar的吞吐量。例如當分組到達服從獨立同分布的貝努里過程，N趨近于無窮時，crossbar的吞吐量只有58.6%，對于burst分組到達，利用率更低[2]。

與傳統(tǒng)的ISP算法不同，本文設計方案提出的ISP算法是面向變長交換的，該算法具體過程如下：

1) 初始化：將RRi置全0，S置全1，其中RRi 表示第i個輸入端口中優(yōu)先級最高的VOQ；S表示輸出端口狀態(tài)向量，為0表示輸出端口i已經(jīng)分配給某個輸入端口，為1表示該端口還沒有被分配。

2) Ar[k,i]表示第k次調(diào)度中的第i次仲裁，其中一次調(diào)度迭代N次，每次迭代稱為一次仲裁，一次仲裁只為一個輸入端口選擇輸出端口。每次Ar[k,i]包括如下步驟：
(1) 輪詢輸入端口Pin [i]= (k＋i) mod N；
(2) 判斷S∩reqi(第i個輸入端口的請求向量 reqi)，若為空集則將i加1，并返回(1)進行下一次迭代，否則進入步驟(3)；

(3) 根據(jù)RRi，reqi以及S為當前輸入端口Pin[i]選擇輸出端口Pout[j]，并輸出In∕Out 端口集合Ω＝{< i,j>，0對于S，若輸出端口Pout [t](t＝0，1，…，N－1)中的數(shù)據(jù)已傳送完畢，則釋放Pout [t]，置S [t]為1。

系統(tǒng)電路設計
OBS接收調(diào)度模塊主要完成以下功能：
1) 接收從OBS核心節(jié)點傳來的突發(fā)(burst)包，并將每個burst包拆卸成一個或多個IP包；
2) 對所拆卸的IP包進行交換，根據(jù)其目的地址將其分配到不同的端口上；
3) 把已經(jīng)完成交換的IP包封裝成以太網(wǎng)幀，并將其傳送到用戶端(以太網(wǎng)卡接口)。
本文所使用的現(xiàn)場可編程門陣列芯片(Field Programmable Gate Array, FPGA)內(nèi)嵌于現(xiàn)場可編程系統(tǒng)芯片(Field Programmable System Chips, FPSC)中。由于每片F(xiàn)PSC僅提供4路數(shù)據(jù)通道，因此6路獨立的數(shù)據(jù)必須由兩片F(xiàn)PGA共同處理。又因為本文所采用設計方案中每片F(xiàn)PGA所完成的邏輯功能完全一致，所以僅給出一片F(xiàn)PGA的系統(tǒng)實現(xiàn)框圖。
如圖1所示，每片F(xiàn)PGA處理4路數(shù)據(jù)，其中3路為突發(fā)包數(shù)據(jù)，另一路數(shù)據(jù)是另1片F(xiàn)PGA傳來的IP分組。因此兩片F(xiàn)PGA可以相互通信，并協(xié)同處理六路突發(fā)包數(shù)據(jù)。下面介紹各子模塊實現(xiàn)情況。

圖1 OBS接收調(diào)度系統(tǒng)硬件框圖
2.1 時鐘提取與串并轉(zhuǎn)換模塊
OBS網(wǎng)絡中的數(shù)據(jù)流是突發(fā)的，而不是連續(xù)傳送的。這種突發(fā)性要求接收端必須快速地從輸入數(shù)據(jù)流中恢復時鐘信號。具體來講，本文設計方案中需要進行時鐘提取的鎖相環(huán)的鎖定時間保持在納秒數(shù)量級。因此，為了保證突發(fā)接收的高效率，在突發(fā)包進入后續(xù)操作以前必須經(jīng)過一個高速鎖相環(huán)來獲得發(fā)送端時鐘信號，從而做到收發(fā)同步。另外，目前的FPGA無法處理1.25 Gb/s的串行高速信號，所以必須通過串并轉(zhuǎn)換將高速串行信號變成低速并行信號才能實現(xiàn)FPGA內(nèi)部操作。時鐘提取與串并轉(zhuǎn)換模塊的功能便是從OBS數(shù)據(jù)流中恢復出頻率為1 250 MHz的發(fā)端時鐘，然后進行1:40串并轉(zhuǎn)換產(chǎn)生40 b的低速數(shù)據(jù)流并送往對齊模塊。
3.2 突發(fā)包對齊(alignment)模塊
鑒于突發(fā)包到達接收端口時刻的隨機性，burst分組在進入拆包模塊之前必須進行對齊，否則會極大地增加后續(xù)設計的復雜性，降低工作頻率。突發(fā)包對齊(alignment)模塊實際上是一個序列檢測器，一旦檢測到前導碼(見圖2突發(fā)包格式)便將其放置于40 b數(shù)據(jù)單元的最高8 b上，即對齊突發(fā)包。

圖3 調(diào)度器硬件實現(xiàn)框圖輸入端口輪詢RR指針產(chǎn)生器當前請求產(chǎn)生器微仲裁器(ma)輸出端口0狀態(tài)控制器輸出端口3狀態(tài)控制器輸出端口1狀態(tài)控制器輸出端口2狀態(tài)控制器current_portreq0req1req2req3rrcrrdengnts1s3s2s0S &matched_portfree 1free 3free 0free 2start_end0start_end1start_end2start_end3current_port
封裝模塊按照以太網(wǎng)幀的格式將IP包封裝成以太網(wǎng)幀。由于以太幀頭為22字節(jié)，僅為16 b而不是芯片內(nèi)部數(shù)據(jù)交換寬度32 b的整數(shù)倍，所以存在一個高16位是以太幀頭，而低16 b是IP分組的數(shù)據(jù)單元, 因此用寬度圍32 b的FIFO是無法正確產(chǎn)生這一數(shù)據(jù)單元的。本設計方案把完成調(diào)度的32 b數(shù)據(jù)分成高16位和低16位，并分別將它們存入兩個寬度為16位的FIFO中，通過控制兩個FIFO的讀信號來產(chǎn)生這個數(shù)據(jù)單元，從而解決了這一問題。
3.4 VOQ與crossbar
VOQ用于存放不同輸出端口的IP包，所以VOQ的長度與丟包率有直接關系(長度越長丟包率越小)。因為突發(fā)包的最小長度為12.5 k字節(jié)，每一個輸入端口對應3個或4個VOQ，每3個或4個VOQ競爭一個輸出端口，那么在帶寬利用率為90％的情況下，平均每個VOQ的最小長度為8.44 k字節(jié)。crossbar由4個帶使能的多路選擇器(Multiplexer, MUX)組成。其中有3個4×1多路選擇器，1個3×1多路選擇器。
3.5 基于變長交換的ISP調(diào)度器
圖3是變長交換ISP調(diào)度器的實現(xiàn)框圖。它主要由輸入端口輪循﹑RR指針產(chǎn)生器﹑當前請求產(chǎn)生器﹑微仲裁器以及輸出端口狀態(tài)控制器組成。具體實現(xiàn)過程如下。
3.5.1 輸入端口輪詢
輸入端口輪循模塊相當于一個時序發(fā)生器，產(chǎn)生本次仲裁所輪循的輸入端口。它由兩個模4計數(shù)器cnt1和cnt2組成。cnt2表示每次調(diào)度中迭代的次數(shù)，每4個時鐘周期加1。cnt1表示當前迭代應首先輪詢的端口。當cnt2等于3時, cnt1加1。cnt1+ cnt2表示當前迭代應輪詢的端口號。
3.5.2 RR指針產(chǎn)生器
RR指針產(chǎn)生器由4個兩位的RR指針寄存器以及一個4×1多路選擇器構成。4×1MUX根據(jù)當前迭代端口號選擇相應的RR指針送微仲裁器。當?shù)螖?shù)為0時，RR指針產(chǎn)生器根據(jù)輸入∕輸出匹配結果，按照ISP算法修改相應的RR指針。
3.5.3 當前請求產(chǎn)生器
當前請求產(chǎn)生器根據(jù)從VOQ傳來的請求信號(re)﹑當前輪詢端口信(rr)及輸出端口的狀態(tài)信息(s)產(chǎn)生該次仲裁的請求信號(cr)。同時通過微仲裁器發(fā)來的仲裁信號(gnt)和輸出端口狀態(tài)控制器給出的釋放信號(free)，修改In∕Out端口狀態(tài)和匹配信號(s & matched port)，并控制相應VOQ的讀使能信號(rden)。信號(cr)有效的條件是req與s均有效。s有效(輸出端口空閑)的條件是free有效而gnt無效。而當gnt有效時輸出端口忙，s無效。
3.5.4 微仲裁器
微仲裁器主要根據(jù)rr與cr信號實現(xiàn)函數(shù)ma，從而產(chǎn)生gnt。本文設計方案使用了一種叫溫度計編碼的編碼器[3]，這種編碼器對最高優(yōu)先級作特殊的編碼，并以此預處理輸入請求，從而巧妙地消除了可編程優(yōu)先級編碼器的優(yōu)先級可編程性，并且硬件實現(xiàn)簡單，節(jié)約資源。
3.5.5 輸出端口狀態(tài)控制器
前面已經(jīng)提到，本文設計方案使用了一種類似于幀定界的方法，它利用拆包模塊發(fā)送的一個名為start_end的信號來標志IP分組的起始與結束。當start_end為“10”時狀態(tài)控制器開始工作；當start_end為“01”時表明IP包傳送完畢，此時發(fā)送free信號釋放相應的輸出端口。這種做法實際上替代了變模計數(shù)器的作用，同時簡化了邏輯，提高了工作頻率。
3.5.6 性能分析及仿真結果
文獻[2]指出，對于keep full到達過程，ISP算法的交換帶寬利用率為100％；在獨立同分布或burst到達條件下，ISP算法的延時和信元延遲的均方差小于其他算法。這說明ISP在帶寬利用率﹑延時和公平性方面都是優(yōu)秀的，特別是在輕負荷和端口數(shù)較小的情況下，ISP性能最優(yōu)。圖4為本文設計方案中調(diào)度器模塊布局的布線后仿真波形圖。

圖4 調(diào)度器布局布線后仿真時序圖

OBS邊緣節(jié)點接收調(diào)度模塊的硬件實現(xiàn)