摘?? 要: 提出了一種硬件實(shí)現(xiàn)的優(yōu)先隊(duì)列算法,可以在常量時(shí)間內(nèi)完成插入和解壓操作,達(dá)到OC3072線速要求。

　　關(guān)鍵詞: 常量時(shí)間的優(yōu)先隊(duì)列? OC3072線速? QoS

?

　　隨著網(wǎng)絡(luò)的高速發(fā)展,用戶對網(wǎng)絡(luò)質(zhì)量的需求也越來越高,調(diào)查顯示用戶對網(wǎng)絡(luò)的抱怨主要體現(xiàn)為速度慢,質(zhì)量沒有保證。要解決這個(gè)問題需要對網(wǎng)絡(luò)路由節(jié)點(diǎn)進(jìn)行QoS(Quality of Service)改造,完善已有的QoS功能,用新的具有QoS能力的路由器逐步替代老一代產(chǎn)品。目前IETF等組織提出的QoS方案有2類,即路由器節(jié)點(diǎn)的QoS和路由器網(wǎng)絡(luò)的QoS(如MPLS和Traffic Engineering)。路由器節(jié)點(diǎn)的QoS還可以細(xì)分為公平的需求和不公平的需求。前者主要包括各種公平調(diào)度算法,后者包括公平調(diào)度算法的不公平配置、BES、RVSP、IS和DS算法。節(jié)點(diǎn)QoS中的很多算法(如調(diào)度算法和DS算法)最終都?xì)w結(jié)為傳統(tǒng)的優(yōu)先隊(duì)列算法。由于純軟件實(shí)現(xiàn)的優(yōu)先隊(duì)列算法不能滿足高速路由器的需求,本文提出了一種硬件支持的常量時(shí)間的優(yōu)先隊(duì)列存取算法,能夠達(dá)到OC3072(即160Gbps)線速要求。

1? 相關(guān)工作

　　目前有2類常量時(shí)間的優(yōu)先隊(duì)列算法:(1)基于通用內(nèi)存的算法,如P-Heap算法。(2)基于專用內(nèi)存的算法,這種算法起源于vEB(van Emde Boas)優(yōu)先隊(duì)列結(jié)構(gòu),一般被稱作STT(Split Tagged Tree)算法。P-Heap算法提出了一種稱之為P-Heap的數(shù)據(jù)結(jié)構(gòu):每次插入和解壓至少經(jīng)過3次內(nèi)存操作,而且它使用流水線隔行工作,相當(dāng)于進(jìn)行6次內(nèi)存操作才能獲得1次結(jié)果。這種機(jī)制是提高效率的主要瓶頸,最高支持OC192(即10Gbps)線速。STT算法得益于vEB提出的優(yōu)秀結(jié)構(gòu),它的速度足夠支持OC768(即40Gbps),但它必須采用專門定制的內(nèi)存,這種內(nèi)存因?yàn)楫a(chǎn)量很小而導(dǎo)致成本無法降低。受到P-Heap的啟發(fā),提出一種B-Heap結(jié)構(gòu),單一隊(duì)列可以實(shí)現(xiàn)OC768線速。如果把4個(gè)B-Heap優(yōu)先隊(duì)列組合起來,則可以滿足OC3072線速的要求。

2? B-Heap的工作原理

2.1 基本操作

　　硬件B-Heap的操作特點(diǎn)是在各個(gè)分層之間使用流水線工作,插入元素的同時(shí)也完成了解壓元素的操作。這一點(diǎn)和P-Heap有所不同,雖然P-Heap也是流水線工作,但需要隔層操作。假設(shè)插入的元素序列為{0,3,4,2,

6,8,1,9,1,7,5,3,2,8,0,-1,-1,-1,-1,2,-1,5,3,9},則初始階段的插入解壓過程如圖1所示,對應(yīng)前8個(gè)元素;有空閑情況下的插入解壓過程如圖2所示,對應(yīng)最后8個(gè)元素,說明流量減小時(shí)插入占位數(shù)據(jù)-1的過程;255是-1的一種表達(dá)方式,其中涉及到比較模式切換問題,中間8個(gè)元素的插入解壓類似于圖1的無空閑情況下的操作。上述3個(gè)過程雖然各自代表實(shí)際操作中的各種情況,但是三者之間設(shè)計(jì)成連續(xù)的,便于觀察。元素從下向上流經(jīng)該結(jié)構(gòu),方框代表針對堆結(jié)構(gòu)每一層的數(shù)據(jù)寄存器,最下端的寄存器為插入輸入,灰色寄存器為解壓輸出。

?

?

　　主要的工作機(jī)制是每次操作選擇一條最小路徑,每一次操作按最小路徑進(jìn)行,比較后進(jìn)行流水線上移。這里的最小路徑是指從上到下依次選擇上層入選節(jié)點(diǎn)的子節(jié)點(diǎn)中較小的元素所構(gòu)成的路徑。其中有2種特殊情況:(1)最上面一層只有一個(gè)節(jié)點(diǎn),因此入選。(2)如果子節(jié)點(diǎn)中元素大小相等則左手子節(jié)點(diǎn)入選。每一層所對應(yīng)的寄存器作為該層的比較輸入,與該層最小路徑上的元素作比較,將較小者放入上一層寄存器的緩沖器。每層寄存器都包括一個(gè)寄存器的緩沖器。寄存器讀取前打開,寫入前關(guān)閉,以滿足流水線操作時(shí)的同步要求。規(guī)定當(dāng)前沒有輸入時(shí)用-1模擬1個(gè)輸入,即所謂的空閑情況。對最下面一層的輸入寄存器為-1的狀態(tài)需要進(jìn)行一次特殊的操作,即結(jié)構(gòu)中所有比較器進(jìn)行模式切換,將-1認(rèn)為是與255進(jìn)行比較,這樣有助于空閑情況下將原來元素按從小到大的順序解壓出來。在具體實(shí)現(xiàn)中將-1認(rèn)為是255的模式切換很容易辦到,因?yàn)閷τ谝粋€(gè)有符號字節(jié)-1,如果用無符號字節(jié)對其進(jìn)行識別就是255。有了這種機(jī)制,在空閑情況下也可以保證空閑之前進(jìn)入堆中的數(shù)據(jù)能夠正常流出。輸出結(jié)果顯示,圖中的B-Heap結(jié)構(gòu)實(shí)現(xiàn)了排隊(duì)空間n=8的在線優(yōu)先隊(duì)列。

2.2 最小路徑查找

　　通過觀察可以發(fā)現(xiàn),每次操作都需要查找最小路徑,這一環(huán)節(jié)是B-Heap算法進(jìn)行高速處理的關(guān)鍵。查找的最小路徑如圖3所示。結(jié)構(gòu)中每一層節(jié)點(diǎn)的地址可以表示為從0開始的二進(jìn)制數(shù),例如從上向下第4層的每一次操作的輸入地址可表示為000,001,010,011,100,101,110,111。B-Heap的狀態(tài)可以表示為X|XX|XXXX|……,其中X為0或1。0表示左手節(jié)點(diǎn)小于右手節(jié)點(diǎn),1表示左手節(jié)點(diǎn)大于右手節(jié)點(diǎn),|為層分隔符,區(qū)別從上到下每一層的狀態(tài)。則圖3中B-Heap的狀態(tài)可表示為,每次操作在每一層中最多修改1bit。查找最小路徑即求出從狀態(tài)到每一層輸入地址的轉(zhuǎn)換結(jié)構(gòu)。下面介紹如何設(shè)計(jì)該轉(zhuǎn)換:由于每一層使用不同的內(nèi)存,屬于并行操作,因此可以在上一次操作結(jié)束時(shí)得到所有的狀態(tài)位,而每次僅僅修改1bit,這樣不會造成較大的總線寬度硬件耗費(fèi)。要從狀態(tài)中找出最小路徑可以通過一個(gè)以狀態(tài)為輸入。多層地址為輸出的地址編碼器來完成。如果采用ASIC,則可以使用足夠的寄存器存儲狀態(tài),從而完全在片內(nèi)實(shí)現(xiàn)編碼器,對外只保留很小的總線寬度,能滿足每層只修改1bit即可。

?

?

　　內(nèi)部邏輯類似于前綴樹,實(shí)際上是在前綴樹結(jié)構(gòu)基礎(chǔ)上簡化了一半的狀態(tài)耗費(fèi)。定義每個(gè)二叉樹節(jié)點(diǎn)的左、右子節(jié)點(diǎn)的比較結(jié)果為b,稱為路徑選擇變量。b是一個(gè)布爾量,為0表示左手子節(jié)點(diǎn)的值小于右手子節(jié)點(diǎn)的值,為1則恰好相反。從二叉樹的根開始,判斷路徑選擇變量,如果為1,則選擇左子樹;如果為0,則選擇右子樹。照此向下推進(jìn),直到葉節(jié)點(diǎn)為止,所形成的路徑就是需要尋找的最小路徑。路徑選擇變量存儲在寄存器中,每個(gè)變量占用1bit。因?yàn)榈谝粚硬⒉恍枰撟兞?所以路徑選擇變量總共占有n/2bit,使用m個(gè)寄存器,其中m=? 。為了區(qū)別每一層的數(shù)據(jù)寄存器數(shù)組T,這m個(gè)寄存器稱為路徑選擇寄存器。

　　使用ASIC實(shí)現(xiàn)時(shí),判斷路徑選擇變量并選擇一條分支的時(shí)間耗費(fèi)t是門級,目前的硬件工藝可以做到十幾到幾十個(gè)皮秒(ps)。整條路徑選擇的時(shí)間耗費(fèi)大約為t的倍。一般情況下<20,所以整條路徑選擇的時(shí)間實(shí)現(xiàn)不會超過1ns。輸出的每一層的地址是可以復(fù)用的,如圖3的狀態(tài)字中最小路徑對應(yīng)每一層節(jié)點(diǎn)地址為{0,0,01,011,0111,……},上層的地址是下層地址的前綴。由此可知第一層不需要地址,因此所有輸出數(shù)據(jù)的地址位數(shù)= 。

　　綜上所述,B-Heap算法的一次存取要完成以下步驟。

　　(1)根據(jù)每一層的比較地址找到比較節(jié)點(diǎn),打開數(shù)據(jù)寄存器數(shù)組T中每個(gè)寄存器的緩存,刷新寄存器。(2)取出比較節(jié)點(diǎn)的值和本層數(shù)據(jù)寄存器中的值相比較,其中較小值寫入上一層數(shù)據(jù)寄存器的緩存,較大值寫入該節(jié)點(diǎn)。同時(shí),輸入寄存器和輸出寄存器中都有了最新值。(3)將較大值和比較節(jié)點(diǎn)的兄弟節(jié)點(diǎn)進(jìn)行比較,如果左節(jié)點(diǎn)大于右節(jié)點(diǎn),則b=1;反之,b=0。將結(jié)果寫入路徑選擇寄存器的相應(yīng)位置。(4)將路徑選擇寄存器的值輸入路徑選擇模塊以選擇一條最小路徑。這一步由ASIC實(shí)現(xiàn),輸入n/2位,輸出位。輸出中含有所有層的下一次比較地址。

3? 性能評估和合并隊(duì)列

　　由于路徑選擇的時(shí)間在總的時(shí)間耗費(fèi)中不占很大比重,因此B-Heap插入和解壓的時(shí)間耗費(fèi)約為P-Heap的1/4。其中逐行操作比隔行操作快一倍,插入和解壓的同步進(jìn)行比分別進(jìn)行快一倍。所以按照P-Heap分析所依據(jù)的內(nèi)存和ASIC工藝水平,B-Heap可以達(dá)到OC768線速。同時(shí),可以使用4片B-Heap擴(kuò)展排隊(duì)長度和操作速度,對4片子優(yōu)先隊(duì)列進(jìn)行RR(Round Robin)調(diào)度可以達(dá)到OC3072線速。

4? 結(jié)束語

　　本文提出了一種硬件輔助的優(yōu)先隊(duì)列算法B-Heap,通過特殊的結(jié)構(gòu)和操作策略可以達(dá)到OC3072線速,在使用普通內(nèi)存的方法中優(yōu)于P-Heap算法。B-Heap算法的主要不足是排隊(duì)長度受到寄存器的限制,例如一個(gè)1024排隊(duì)長度的B-Heap需要16個(gè)寄存器,目前的工藝完全可以承受。但是如果排隊(duì)長度按幾何比例增長,則B-Heap的實(shí)現(xiàn)依賴于能夠集成的寄存器數(shù)目。

?

參考文獻(xiàn)

1?? Xipeng X,Lionel M N.Internet QoS:A Big Picture.IEEE Network,1999;(4)

2?? Bhagwan R,Lin B.Fast and Scalable Priority Queue?Architecture for Highspeed Network Switches.IEEE?Infocom,2000;(3)

3?? Brodnik A.Worst Case Constant Time Priority Queue.WCCTPQ,2000;(3)