摘?? 要: 提出了一種硬件實現的優先隊列算法,可以在常量時間內完成插入和解壓操作,達到OC3072線速要求。

　　關鍵詞: 常量時間的優先隊列? OC3072線速? QoS

?

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

1? 相關工作

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

2? B-Heap的工作原理

2.1 基本操作

　　硬件B-Heap的操作特點是在各個分層之間使用流水線工作,插入元素的同時也完成了解壓元素的操作。這一點和P-Heap有所不同,雖然P-Heap也是流水線工作,但需要隔層操作。假設插入的元素序列為{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所示,對應前8個元素;有空閑情況下的插入解壓過程如圖2所示,對應最后8個元素,說明流量減小時插入占位數據-1的過程;255是-1的一種表達方式,其中涉及到比較模式切換問題,中間8個元素的插入解壓類似于圖1的無空閑情況下的操作。上述3個過程雖然各自代表實際操作中的各種情況,但是三者之間設計成連續的,便于觀察。元素從下向上流經該結構,方框代表針對堆結構每一層的數據寄存器,最下端的寄存器為插入輸入,灰色寄存器為解壓輸出。

?

?

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

2.2 最小路徑查找

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

?

?

　　內部邏輯類似于前綴樹,實際上是在前綴樹結構基礎上簡化了一半的狀態耗費。定義每個二叉樹節點的左、右子節點的比較結果為b,稱為路徑選擇變量。b是一個布爾量,為0表示左手子節點的值小于右手子節點的值,為1則恰好相反。從二叉樹的根開始,判斷路徑選擇變量,如果為1,則選擇左子樹;如果為0,則選擇右子樹。照此向下推進,直到葉節點為止,所形成的路徑就是需要尋找的最小路徑。路徑選擇變量存儲在寄存器中,每個變量占用1bit。因為第一層并不需要該變量,所以路徑選擇變量總共占有n/2bit,使用m個寄存器,其中m=? 。為了區別每一層的數據寄存器數組T,這m個寄存器稱為路徑選擇寄存器。

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

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

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

3? 性能評估和合并隊列

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

4? 結束語

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

?

參考文獻

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)