基于變長交換的ISP算法

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

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

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

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

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

系統(tǒng)電路設(shè)計(jì)
OBS接收調(diào)度模塊主要完成以下功能：
1) 接收從OBS核心節(jié)點(diǎn)傳來的突發(fā)(burst)包，并將每個(gè)burst包拆卸成一個(gè)或多個(gè)IP包；
2) 對(duì)所拆卸的IP包進(jìn)行交換，根據(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路獨(dú)立的數(shù)據(jù)必須由兩片F(xiàn)PGA共同處理。又因?yàn)楸疚乃捎迷O(shè)計(jì)方案中每片F(xiàn)PGA所完成的邏輯功能完全一致，所以僅給出一片F(xiàn)PGA的系統(tǒng)實(shí)現(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ù)。下面介紹各子模塊實(shí)現(xiàn)情況。

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

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

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

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