基于變長交換的ISP算法

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

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

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

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

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

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

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

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

圖4 調度器布局布線后仿真時序圖

OBS邊緣節點接收調度模塊的硬件實現