可擴展網絡交換調度系統的分布式迭代算法
2008-12-31 00:00:00胡慶生徐植仲建鋒
計算機應用研究 2008年7期
摘 要：提出了一種最長隊列優先的分布式迭代算法。與現有算法不同的是，該算法針對可擴展網絡交換調度結構的特點，為處于最高優先級的調度器安排了兩次迭代。其中的第一次迭代實現最長虛擬輸出隊列(VOQ)的查找，并且在最高優先級時隙之前的一個時隙完成，以縮短信號的處理時間。仿真結果表明，本算法與現有算法相比，在大流量的uniform流量模式下，延時性能與吞吐率獲得了明顯的提高；同時，該算法的硬件代價小，有效地實現了性能和復雜度的良好折中。
關鍵詞：輸入隊列交換； 可擴展; 分布式迭代; 虛擬輸出隊列
中圖分類號：TP301.6；TP393 文獻標志碼：A
文章編號：1001-3695(2008)07-2115-03
Distribute iteration algorithm for fair scalable scheduling architectures
HU Qing-sheng， XU Zhi， ZHONG Jian-feng
(Institute of RF- OE-ICs， Southeast University， Nanjing 210096， China)
Abstract:This paper represented a new distributed iteration algorithm.Different from existing algorithms， the proposed algorithm distributed the multi-iterations in sequent cell times. In the first iteration the longest queue was picked out and saved as the scheduling result in the cell time just before the highest priority cell time in order to reduce the scheduling time.The new algorithm achieved better performance on average delay and throughput under heavy load of uniform traffic model compared to the existing algorithms.Meanwhile， this proposed algorithm is fairly easy for hardware implementation.Key words：input-queued switch; scalable; distributed iteration; VOQ
近年來，網絡節點的交換技術已經取代信道傳輸技術，成為制約網絡發展的新瓶頸。有效的高速交換技術是構建高性能網絡的基礎。構建高性能的網絡，除了需要提供更大的容量和更多的接口之外，還需要在交換的延遲、吞吐率和公平性等性能指標上實現優化。
目前，已經有單片的交換機和調度器的集成電路芯片在產，但是這種單片的集成電路芯片交換容量和調度容量都非常有限，通常只能實現32個端口之間的交換或調度。要想在單片集成電路上實現更大規模的交換和調度功能(如256×256)十分困難。因此，有必要進一步提升可擴展調度結構的性能以滿足下一代網絡交換所需的多端口、大容量的要求。
基于輸入隊列交換和基于輸出隊列交換是兩種常見的網絡交換體系結構。相對輸出隊列來說，輸入隊列更易于物理實現，而且可以有效地解決線頭阻塞（HOL blocking）問題。所以，國際國內對輸入隊列的調度算法開展了廣泛的研究，已提出了多種基于輸入隊列交換的調度方法。例如，屬于最大權匹配(MWM)的LQF(最長隊列優先)算法[1]和屬于最大尺寸匹配(MSM)的iSLIP[2]、RDSRR[3]算法。文獻[4，5]分別提出了一種隨機性算法和隊列長度加權服務的調度算法，在吞吐率和平均延時等性能指標上均取得良好的效果，但是其硬件復雜度與iSLIP等MSM算法相比仍顯復雜。總的來說，MSM算法相對于MWM算法復雜度相對較低，硬件實現也相對容易，但性能與MWM算法尚有一定差距。
可擴展調度是指通過將較小規模的調度器級聯實現大容量多端口調度的調度方法，主要解決單片調度器規模和輸入／輸出端口數受限的問題[6]。對于可擴展的調度系統來說，目前國內外已開展了一定的研究，如M. Kumagai等人[7]提出了一種只適用于小容量交換的多個調度器級聯的方法，其中每個調度器只與一個輸入端口相連，各調度器采用順序工作方式，這種方式的缺點是端口數增多時會導致交換效率的降低。F. M. Chiussi等人[8]又提出了DFDA這種可用于可擴展的調度算法，該算法采用全分布式結構，對于可擴展網絡工作良好。文獻[6]中提出的端口和規模可擴展的高速網絡交換調度系統，通過多個容量較小的調度器協同工作完成多端口大容量的交換調度任務，不僅速度高，而且規模可擴展。在實際應用中，可根據需要配置成不同容量和端口數的調度器，從根本上解決單個調度器容量和端口受限的問題。為了進一步提高可擴展調度系統的性能，本文在文獻[6]的基礎上，對公平可擴展網絡交換調度算法進行了深入研究，通過對調度時隙的充分利用，有效地降低了網絡交換的時延特性、提高了調度器的性能，而硬件資源的增加卻十分有限。
1 公平可擴展調度系統FSSA
可擴展調度結構是將若干容量較小的調度器(本文稱為子調度器)串聯起來完成大容量調度任務。其中子調度器實現的是一組輸入端口與輸出端口之間的IQ交換調度。圖1以32×32的調度為例給出了公平可擴展調度系統FSSA(fair scalable scheduling architecture)的實現框圖。圖中四個8×32的子調度器環形連接，每個子調度器與八個端口處理器PP(port processor)相連，在中心控制器CC(central controller)的作用下，四個子調度器順序工作就可以實現32×32的調度功能。子調度器的環形連接方式保證了調度的公平性，AOP(available output port)信號表示子調度器調度后的有效輸出端口，這些有效輸出端口可用于下一個子調度器的調度。
若進行N×N的調度，子調度器的個數為M，為了更好地說明FSSA的工作原理，下面先給出本文用到的一些術語：
a)調度周期，子調度器完成一輪完整調度所需的時間，即N/M個時隙；
b）第i輪調度(i=1，2，…， M)，每個時隙中，不同的子調度器完成不同輪的調度；
c)第i輪調度開始和結束，每輪調度開始的那個時隙稱為調度開始，每輪調度的最后一個時隙稱為調度結束；
d)調度優先級，衡量不同時隙子調度器可用輸出端口數的多少，可用端口數越多，優先級越高。處于調度開始的子調度器的優先級最高(為M)；隨著調度的進行，可供調度的輸出端口逐漸減少，處于調度結束的子調度器的優先級最低(為1)。
圖2說明了FSSA的工作原理。圖中1~4分別表示第1~4輪調度；①~④分別表示第1~4輪調度的開始。從圖中可以看出，第一個調度周期之后總共可以得到4輪調度結果；之后，每個時隙均可以得到一個完整的調度結果。例如，時隙5可以得到第3輪調度結果，時隙6可以得到第4輪調度結果。另外，由于每個時隙包到達的分布是均衡的，采用圖2的優先級分配方式，目的是盡量使子調度器的優先級之和在一個調度周期的各個時隙間平均分配。
以圖2中的第一個調度周期為例，在時隙1，所有子調度器的優先級之和為12，時隙2則為11，第3個時隙的優先級之和為8，第4個時隙也為8。這樣做的好處是通過均衡分配每個時隙的有效輸出端口的數量，提高調度器的延遲特性。
2 基于隊列長度的分布式迭代算法
研究表明要提高交換效率，可以采取下面兩個措施：a)通過增加迭代次數提高輸入/輸出匹配對的數量；b)通過選擇權重較大的VOQ提高每次匹配的權重。
對于措施a)，如果直接在每個時隙中增加迭代次數，無疑會增加整個系統的延遲。然而，注意到在FSSA的每個調度周期中，各子調度器均有一次最高優先級的調度機會，處于最高優先級的子調度器可以在輸入端口和任意一個輸出端口之間進行調度，因此適當增加該時隙的迭代次數有可能產生匹配數多、匹配權重大的調度結果。
對于措施b)，要想有效地提高調度匹配的權重，應該在保證一定匹配尺寸的前提下盡量挑選出長度較長的VOQ進行匹配。由于一個子調度器在兩次最高優先級調度時隙之間有三個時隙的間隔，而相鄰時隙包的緩存情況變化不大。為了不增加整個系統的延遲時間，可以考慮將選擇長VOQ的任務提前到最高優先級時隙的前一個時隙完成，這樣做既實現了多次迭代又節省了信元的處理時間。
綜合考慮a)和b），本文提出了基于隊列長度的分布式迭代算法FSSA_DI(FSSA using distributed iteration)。該算法的基本思想是對于每個子調度器，在最高優先級時隙之前的一個時隙，用簡單的查找法挑選出最長的VOQ(和次長的VOQ)并將其作為最高優先級時隙的第一次迭代結果；在最高優先級時隙再用DSRR算法進行第二次迭代。這樣，在最高優先級時隙就可以在保證匹配尺寸的前提下增加匹配的權重。對于其他時隙，均采用一次迭代的DSRR算法進行調度。
FSSA_DI算法的具體描述如下：
/* i: number of inputs; j: number of outputs*/
/*iteration phase */
if(prior highest priority) { /*最高優先級時隙之前的一個時隙*/
for (all i and j){
selectMax(i，j);/*找出最長的VOQ*/
matchMax[i，j]=1;/*作為第一次迭代結果保留*/
}}
if（highest priority）{/*最高優先級時隙*/
for all(j){
if (matchMax[i，j] = 1)
match[i，j]=1;/* 采用第一次迭代結果*/
}}
/*request phase */
for(all i)request (i){
for(all j) {
if((num_cells[i，j]>0) (match[i，j]!=1)
{request(i，j);} /*輸入端口i向輸出端口j發出請求*}
}}
/*grant phase*/
for(all j) grant(j){
if ( num_request[j]>0){/*收到了請求*/
i=output_pointer(j);/*根據round-Robin規則決定grant */
grant_request(i，j);
}} /* 應答請求i */
/*accept phase*/
for (all i ) accept(i){
if(num_grant[i] > 0){/*收到了grant */
j=input_pointer(i);/*根據Round-Robin規則決定accept*/
accept_grant(i，j);/*接受grant(j)*/
match[i，j] = 1;
}}
圖3說明了FSSA_DI的工作原理。以子調度器2為例，它在時隙4的調度優先級最高。為了提高該時隙的匹配權重，在時隙３先進行第４輪調度的第一次迭代，找出最長的VOQ（或同時找出次長的VOQ），緊接著在時隙4用DSRR算法進行第４輪調度的第二次迭代。這樣，二次迭代的結果有望產生權重較大的匹配。
3 仿真結果分析
本文針對32×32的交換進行了仿真，分別對單個調度器和高效公平可擴展調度結構進行仿真。其中的可擴展結構用四個8×32子調度器實現。仿真的輸入流量為uniform模式和非uniform的對角線(diagonal)模式。
圖4和5為輸入流量為uniform時的延遲和平均隊列長度的仿真結果。其中：iSLIP、LQF、DSRR分別表示采用單個調度器時這三種算法的仿真結果；FSSA_DSRR則表示采用可擴展結構FSSA、子調度算法為DSRR時的調度結果。FSSA_DI和FSSA_DI2則表示采用本文提出的分布式迭代算法時的調度結果；其中：FSSA_DI為選取一個最長VOQ時的結果；FSSA_DI2為選取最長VOQ和次長VOQ時的結果。
可以看出，流量低時基于FSSA的調度器延遲性能接近于一個常量，該常量與采用的子調度器個數有關，子調度器越多，該值越大。流量高時，FSSA_DI、FSSA_DI2及FSSA_DSRR的延遲性能優于ISLIP和DSRR算法的性能。而同樣都是基于FSSA、FSSA_DI和FSSA_DI2的性能又優于FSSA_DSRR；FSSA_DI和FSSA_DI2相比，后者比前者略好。當然，這幾種算法中，LQF算法的性能最優，但其硬件實現復雜，很難實際應用。
Diagonal模式下的仿真結果如圖6和7所示，其輸入流量可以表示為λii = 2p/3，i， λii+1=p/3，λij=0(其余情況)。可以看出，采用FSSA_DI及FSSA_DI2后，系統不穩定時的負載流量從0.72增加到0.78，因此，延遲和平均隊列長度性能均比FSSA_DSRR有所提高。
通過上面的分析，可以得出以下結論：在uniform和diagonal模式下，流量高時基于FSSA的調度算法的性能明顯優于單調度器的iSLIP、DSRR算法。同時，與FSSA_DSRR算法相比，FSSA_DI及FSSA_DI2算法的性能在流量高時也明顯得到了提高。本文提出的分布式迭代算法是有效的。
4 硬件復雜度分析
由于DSRR算法是一種常用的三相調度算法，即請求—應答—接受，實現FSSA_DI算法時，每個子調度器中需要與DSRR算法相對應的三個模塊，即請求模塊、應答仲裁器模塊和接受仲裁器模塊，分別完成相應的調度任務。例如，一個8×32的子調度器中有32個應答仲裁器、8個接受仲裁器和1個調度信息生成器，如圖8所示。在每個調度時隙開始時，子調度器首先接收來自上一級子調度器的輸入信號AOPin，該信號用于控制應答仲裁器的工作。當AOPin的相應位為“0”時，與之對應的應答仲裁器被激活，開始應答操作；當為“1”時，由于對應的輸出端口已被占用，與之對應的仲裁器將不工作。因此，每次執行應答操作時，并不是所有的32個仲裁器都工作，只有與32位AOP信號中的“1”相對應的應答仲裁器才工作，這種方式可大大減少了電路的功耗。
除此之外，為了實現FSSA_DI還需要增加比較器用來查找最長的VOQ。分析DSRR算法的請求—應答—接受的三相操作后發現，在一個調度時隙中，應答和接受操作花費的時間最多。如8×32子調度器進行應答操作時，最差情況下應答仲裁器指針需要轉動一周即32個時鐘周期才能找出非空隊列；同樣，接受仲裁器指針在最壞情況下也需要轉動8個時鐘周期才能找到應答信號，再加上信號的輸入、輸出等其他操作所需的時間，一個調度時隙大約需要50個時鐘周期。而子調度器中VOQ的數量為8×32=256，為了在有限的時間里挑選出最長的VOQ，可以采用多個比較器同時進行比較，只要將整個查找的延遲控制在一個時隙之內即可。因此，本文提出的分布式迭代算法只需增加有限的硬件資源即可實現調度器性能明顯改善。
5 結束語
本文提出了一種可用于公平可擴展網絡交換調度系統的分布式迭代算法，通過對最高優先級時隙的分布式多次迭代，以較小的硬件代價實現了系統性能的明顯提高，取得了性能與復雜度的良好折中。仿真結果表明，在uniform流量下，延時性能和平均隊列長度性能均有明顯提高，在diagonal等其他流量模式下性能也有一定改善。值得指出的是該分布式迭代思想對單調度器也同樣適用。
參考文獻：
［1］MEKKITTIKUI A，McKEOUN N. A starvation-free algorithm for achieving 100% throughput in input-queued switches[C]//Proc of IEEE International Conference on Computer Communications and Networks.Rockville:IEEE Communications Society，1996:226-231.
[2]MCKEOWN N. The iSLIP scheduling algorithm for input-queued switches[J].IEEE Trans on Networking，1999，7(2):188-201.
[3]JIANG Ying，HAMDI M. A fully desynchronized round-robin matching scheduler for a VOQ packet switch architecture[C]//Proc of IEEE Workshop on High Performance Switching Routing.2001:407-411.[4]GIACCONE P，PRABHAKAR B， SHAH D. Towards simple， high-performance schedulers for high-aggregate bandwidth switches[C]//Proc of the 21st Annual Joint Conference on Computer and Communication Societies.2002:1160-1169.
[5]孫書韜，賀思敏，鄭燕峰，等.隊列長度加權服務的輸入排隊交換結構匹配算法[J].計算機學報，2006，29(6):875-883.
[6]LIU Jing，HAMDI M，HU Qing-sheng， et al. Scalable scheduling architecture for high-performance crossbar-based switches[C]//Proc of IEEE Workshop on High Performance Switching Routing.2004: 104-110.
[7]KUMAGAI M，NOJIMA S，TOMONAGA H.IP router for next generation network[J]. FUJITSU Scientific Technical Journal， 2001，37(1):31-41.
[8]CHIUSSI F M， FRANCINI A， GALANTE G， et al. A novel highly-scalable matching policy for input-queued switches with multiclass traffic[C]//Proc of IEEE Global Telecommunications Conference.2002:2281-2286.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
