用于多級交換網(wǎng)絡的一種高效自尋路技術

倪 杰,張子為,陳志云,許 都

(1.電子科技大學寬帶光纖傳感與通信教育部重點實驗室,成都 611731;2.華為技術有限公司,廣東 深圳 518129)

1 引 言

隨著網(wǎng)絡業(yè)務量的日益增長,網(wǎng)絡承載的帶寬需求漸漸提高。IP技術作為承載網(wǎng)的必然選擇,需要滿足高帶寬的傳輸與交換壓力[1]。為此,大容量可擴展交換設備的設計受到越來越多的重視。目前,業(yè)界對可擴展交換結構的研究主要集中在多級交換結構[2],如三級Clos[3]網(wǎng)絡結構?；贑los網(wǎng)絡的調(diào)度算法有很多,包括傳統(tǒng)的RD(Random Dispatching)算法、CRRD(Concurrent Round-Robin Dispatching)[4]算法等。但在高速、高負載量環(huán)境下,采用這類算法仍存在一些不足之處,比如CRRD等算法,需采取一定的仲裁策略及多次匹配過程,復雜度較高[5],這大大影響了交換性能。

采用自尋路技術則無需復雜的仲裁機制,交換過程簡單易處理。然而,自尋路交換容易造成網(wǎng)絡內(nèi)部阻塞,尤其當網(wǎng)絡負載量增大、突發(fā)業(yè)務增多時,阻塞概率也會隨之增大,網(wǎng)絡性能隨之降低。為了減少連續(xù)沖突,進一步提升網(wǎng)絡性能,本文基于三級Clos交換網(wǎng)絡,提出了一種新的高效自尋路機制。該機制通過在交換網(wǎng)絡前端采取“信元間插”策略,保證業(yè)務被均勻地發(fā)送至網(wǎng)絡中,大大減輕了網(wǎng)絡內(nèi)部的連續(xù)阻塞,從而減少了信元交換的端到端時延;同時,通過在第一級采取一定的負載均衡分發(fā)策略,進一步提升了網(wǎng)絡性能。

本文第3節(jié)詳細描述了三級Clos網(wǎng)絡中的新自尋路交換機制,包括“信元間插”的具體策略、第一級交換單元的負載均衡分發(fā)方式,以及第二、三級交換單元的自尋路交換,并從理論上分析解釋了“信元間插”可以提升網(wǎng)絡性能的原因;第4節(jié)給出了新自尋路交換機制下的Clos網(wǎng)絡性能詳細測試結果,將其與傳統(tǒng)的CRRD算法進行了仿真對比,進一步證明了該機制的高效性;最后對全文進行了總結。

2 三級Clos交換網(wǎng)絡架構

新自尋路交換機制下的三級Clos網(wǎng)絡架構主要由流量管理模塊和交換結構兩部分組成,如圖1所示。圖中,IM(Input Module)表示輸入級,CM(Central Module)表示中間級,OM(Output Module)表示輸出級,OQ(Output Queue)表示輸出端緩存隊列。

圖1 三級Clos交換網(wǎng)絡架構Fig.1 Three-stage Clos network architecture

圖1中,流量管理模塊的主要功能是將待交換業(yè)務進行“信元間插”,保證業(yè)務被均勻地發(fā)送至交換結構。

交換結構是整個網(wǎng)絡架構的主要組成部分,它采用三級Clos結構,一/三級共r個交換單元;第二級共m個交換單元;第一級的每個交換單元均有 n個輸入端口;第三級的每個交換單元均有 n個輸出端口。每個交換單元的輸出端口處均有一定大小的緩存空間,當數(shù)據(jù)發(fā)生端口爭用時,可在此處進行排隊。在第一級,每個交換單元設有一組“邏輯指示器”,用來為輸入端口處的數(shù)據(jù)選取合適的第二級交換單元,盡量保證第二級單元的負載均衡。到達第二級交換單元的信元,將基于自尋路技術,判斷信元對應的目的模塊(即第三級交換單元),然后選擇相應路徑交換到第三級[6]。到達第三級交換單元的信元,將通過自尋路,選擇相應的目的端口輸出。

3 三級Clos結構中的新自尋路交換機制

目前很多交換結構采用的分組交換技術是基于信元的(Cell-Based)[7],即對變長分組如IP數(shù)據(jù)包進行交換前,先切割為多個定長信元。交換結構發(fā)送一個信元的時間稱為一個“時隙”。本文提出的自尋路機制中,便將采用這種基于信元的交換技術。

3.1 新自尋路交換機制中的“信元間插”策略

在對交換網(wǎng)絡調(diào)度算法的研究中,一般會假設輸入端口到所有輸出端口的流量是均衡的,且輸出端口的流量是均衡地來自所有的輸入端口,這種業(yè)務成為均勻業(yè)務。但在實際網(wǎng)絡環(huán)境中,可能有多個輸入端口的流量是去往同一個輸出端口的,此時就會出現(xiàn)輸出端口競爭沖突現(xiàn)象。在競爭過程中,只有一個信元能夠順利到達對應的輸出端口,其他競爭失敗的信元需在交換結構的輸入端或輸出端進行緩沖排隊,等待下一個時隙被交換。若網(wǎng)絡負載量較大,輸入端口處的連續(xù)信元較多,則可能導致長時間的流量沖突而影響交換網(wǎng)絡性能。

新自尋路交換機制中,信元進入Clos交換結構參與交換之前,將首先在流量管理器中緩存,緩存一定的時間間隔后,流量管理器將對所有已緩存信元進行間插。通過“信元間插”策略,可以將每個輸入端口處的連續(xù)數(shù)據(jù)包“打散”,使得目的端口相同的業(yè)務在時間軸上離散分布,然后均勻地進入交換結構,從而減少各信元在輸出端口的連續(xù)沖突,減輕網(wǎng)絡內(nèi)部阻塞,提升網(wǎng)絡性能。

信元序列準隨機化處理的方法有多種,在此采用簡單的可硬件快速實現(xiàn)的二進制編碼轉換策略進行信元間插。每個輸入端均有若干待交換的信元,每個信元均對應一個時隙號。對于具有同一目的端口的某連續(xù)信元分組,將其對應的所有時隙號的二進制表示逆向讀出后,將得到一個新的時隙號序列。將該分組包含的所有信元分配到新的時隙位置上,即可成功地將該連續(xù)信元分組在時間軸上均勻地分散開來。下面以包含8個信元的交換幀為例進行說明。

圖2表示間插前的某交換幀,A、B、C分別表示信元的目的端口。時隙0、1、2中的3個連續(xù)信元,其目的端口均為A;時隙3、4中的兩個連續(xù)信元,其目的端口均為 B;時隙5、6、7中的3個連續(xù)信元,其目的端口均為 C。對目的端口為A的連續(xù)信元分組進行分析:0號時隙位對應的二進制表示為0002,反向讀出后仍為0002,則新時隙號仍為0;1號時隙位對應的二進制表示為0012,反向讀出后為1002,則新時隙號為 4;2號時隙位對應的二進制表示為0102,反向讀出后仍為0102,則新時隙號為2。那么,新時隙號序列即為0、2、4。原本處于時隙0、1、2上的信元A1、A2、A3,將被分別分配到時隙0、2、4上。

圖2 間插前的交換幀示意圖Fig.2 The frame before interleaved

根據(jù)表1類推,B1、B2分別分配到時隙1、6上,C1、C2、C3分別分配到隙 3、5、7 上,這樣每個連續(xù)分組中的信元都可被均勻分散在時間軸上。

表1 二進制編碼轉換表Table 1 Binary conversion table

對于任意一個連續(xù)信元分組,當判斷出它的新時隙號序列后,會將原分組包含的所有信元一一順序地分配到新時隙中。因此,某連續(xù)信元分組經(jīng)間插后,雖然信元不再連續(xù),但該分組包含的所有信元并不亂序,即先后順序依然不變。間插后的交換幀如圖3所示?？梢钥闯?經(jīng)過間插后,盡量保證了相鄰信元的目的端口不同。

圖3 間插后的交換幀示意圖Fig.3 The frame after interleaved

業(yè)務經(jīng)過信元間插后才能進入交換結構參與交換,交換時長稱為一個“交換周期”,記為 TSwitching。在該 TSwitching時間的交換過程中,流量管理器仍然不斷地接收前端業(yè)務請求,并將它們進行緩存,待該次交換過程結束,便可對新緩存好的業(yè)務進行間插,進入下一次交換。一般來講,業(yè)務的間插所用的時間相對于整個處理過程來說是很短的。在一個交換周期中未能交換完成的業(yè)務將在下一個交換周期中繼續(xù)交換,將每個交換周期平均分成多個時隙。從整體上看,交換結構逐時隙地進行交換調(diào)度。

3.2 “信元間插”策略的理論分析

本節(jié)將從理論上解釋“信元間插”策略可以減少流量沖突的原因。

圖4為一個 N×N(N表示輸入/輸出端口總數(shù),N≥2)的交換網(wǎng)絡,“IP”表示輸入端口(Input Port);“OP”表示輸出端口(Output Port);“t”表示第 t個時隙;m(n)表示該處有m(n)個連續(xù)信元。

圖4 交換網(wǎng)絡中的沖突示意圖Fig.4 Conflicts in switching network

圖4中,在任意“t”時隙,任意兩個輸入端口 a和b處的信元目的端口均為x,那么此時,OP“x”處即會產(chǎn)生沖突。假設在“t”時刻,輸入端口 a處的當前數(shù)據(jù)包連續(xù)長度為m個信元(m≥1),入端口b處當前的數(shù)據(jù)包連續(xù)長度n個信元(n≥1)。在“t+1”時隙,事件“輸入端口a和b處的信元再次基于輸出端口`x'產(chǎn)生沖突”相當于“入端口 a處的數(shù)據(jù)包連續(xù)長度La,在這段時間內(nèi)需滿足La≥m+1;且入端口b處的數(shù)據(jù)包連續(xù)長度Lb,在這段時間內(nèi)需滿足 Lb≥n+1”。

不同輸入端口的數(shù)據(jù)產(chǎn)生情況,可以被認為是相互獨立的事件。因此,事件“輸入端口a和b處的信元在t+1時隙再次基于輸出端口`x'產(chǎn)生沖突”的概率P可以表示為

下面,我們將對交換網(wǎng)絡是否采用“信元間插”這兩種情況進行對比分析。

(1)直接交換:即未預先采用“信元間插”策略。業(yè)務到來并被切割為信元后,交換網(wǎng)絡會根據(jù)其目的端口,直接發(fā)送。若發(fā)生沖突,信元將排隊輸出。

從長期看來,每個輸入端口處產(chǎn)生的數(shù)據(jù)包長度L可以看作是服從(μ,σ)的正態(tài)分布(L>0,μ為數(shù)據(jù)包長度L的均值)。

正態(tài)分布概率密度函數(shù)為

正態(tài)分布的累積分布函數(shù)為

由正態(tài)分布曲線的對稱性可知

在上述理論基礎上,事件“輸入端口a和b處的信元在t+1時隙再次基于輸出端口`x'產(chǎn)生沖突”的概率PDirectSwitching滿足:

顯然,如果 m<μ,n<μ,那么

也就是說,在某時刻“t”,只要入端口a處的當前數(shù)據(jù)包連續(xù)長度La和入端口b處的當前數(shù)據(jù)包連續(xù)長度Lb的值尚未到達μ,那么,在下一個時隙“t+1”,這兩個端口基于出端口“x”再次產(chǎn)生沖突的概率滿足 PDirectSwitching≥1/4。

(2)“信元間插”后再交換:即數(shù)據(jù)被發(fā)送至交換網(wǎng)絡之前,需預先對其進行“信元間插”。輸入端口處的數(shù)據(jù)包經(jīng)過“信元間插”后,可以被認為是離散分布的。即每個時隙每個信元之間是相互獨立的,每個信元的目的端口OP為“x”的概率均為1/N。這種情況下,事件“入端口 a和b處的信元在t+1時隙再次基于輸出端口`x'產(chǎn)生沖突”的概率PCellInterleaved滿足:

由于 N≥2,且 m ≥1,n≥1,因此 PCellInterleaved≤1/16。當N增大時,PCellInterleaved將更小。

通過以上對比分析可知,PCellInterleaved

3.3 第一級交換單元中的“負載均衡分發(fā)”

信元經(jīng)間插后,交換結構會逐時隙讀取輸入端口處的信元。在某一時隙下,某輸入級交換單元的所有輸入端口處的信元,按照目的模塊的不同,將被視為屬于不同的業(yè)務流[8]。每個第一級交換單元均設有一組“邏輯指示器”,用來指示該單元入端口處的信元應選擇的輸出端口。分發(fā)過程如圖5所示。

圖5 第一級交換單元內(nèi)部示意圖Fig.5 The first-stage switching unit

信元進入第一級后,交換單元首先判斷該信元所屬業(yè)務流,然后查詢該業(yè)務流對應的指示器數(shù)值,最后將該信元發(fā)往指示器對應的輸出端口處進行排隊輸出。每處理完一個信元,指示器數(shù)值加一,并基于該交換單元輸出端口總數(shù)做取模運算。

在每個周期的初始時刻,該交換單元中所有指示器的值都將進行一次初始化處理,不同指示器的初始值是不同的:第一級模塊i中,業(yè)務流j對應的指示器初始值為(i+j)mod m。其中,i為該第一級交換單元的編號(0≤i≤r-1,r為第一級交換單元總數(shù));j為業(yè)務流編號(0≤j≤r-1,r為第一級交換單元總數(shù));m為一個第一級交換單元的輸出端口總數(shù)(即中間交換單元總數(shù))。

第一級的信元按照指示器選取輸出端口后,相當于選取好了第二級交換單元。采用這樣的分發(fā)策略可以在一定程度上保證第二級交換單元的負載均衡。

3.4 第二/三級交換單元中的“自尋路交換”

第二級和第三級交換單元的每個輸出端口處均有一個緩存隊列。到達第二級交換單元的信元,將采用自尋路技術,即首先判斷信元將去往的目的模塊(即第三級交換單元),然后選取對應的出端口緩存隊列,排隊交換到第三級。第三級交換單元對于到來的信元,將基于自尋路方式,首先判斷信元將去往的目的端口,然后選取對應的緩存隊列排隊輸出。

4 仿真分析

基于本文第3節(jié)描述的新自尋路交換機制,我們利用C++語言對圖1所示的三級Clos交換網(wǎng)絡架構進行了多種配置下的仿真。

注意:仿真中的分組長度等參數(shù)設置并不完全代表真實網(wǎng)絡情況,只是為了突出算法的性能而選取的特殊值,但這并不影響對新機制性能本身的考察。仿真結果中的時延指信元進入交換網(wǎng)絡第一級,到離開交換網(wǎng)絡第三級所用的時間,時間計量單位為“時隙”,一個信元對應一個時隙。

(1)本部分對是否預先采用“信元間插”策略的三級Clos網(wǎng)絡時延性能進行仿真對比。

仿真基本配置如下:網(wǎng)絡規(guī)模為m=n=r=8;分組長度以1 024 byte為均值正態(tài)分布,定長信元長度為64 byte,一個交換周期包含2 048個時隙,即將每2 048個信元作為一幀;負載量為10%～98%。

圖6給出了兩種情況下的信元平均網(wǎng)絡時延隨網(wǎng)絡負載量的變化曲線?？梢钥闯?在預先經(jīng)過信元間插處理的情況下,信元平均時延明顯減小。這正是由于“將業(yè)務打散再分發(fā)”這種處理策略使得前端信元在交換周期中離散分布,大大減少了網(wǎng)絡內(nèi)部阻塞,從而保證了流信元端到端的低時延交換。

圖6 新自尋路機制中“信元間插”對網(wǎng)絡時延的影響Fig.6 Average delay with andwithout“cell interleaving”in the new self-routed switching scheme

(2)本部分通過改變分組的平均長度(即信元的平均連續(xù)長度),考察了新自尋路交換機制在分組平均長度不同情況下,信元平均網(wǎng)絡時延隨負載量的變化情況。

分組長度分別以512 byte和1 024 byte為均值正態(tài)分布,其余配置與(1)相同。通過圖7可以得知,當分組長度變化,新的自尋路交換方式仍能較好地將業(yè)務均勻分散開來。

圖7 新自尋路機制中分組長度對平均網(wǎng)絡時延的影響Fig.7 Average delay under different configurations of packet length in the new self-routed scheme

(3)第3節(jié)中指出,“交換周期”的大小是可配置的。當分組平均長度一定時,“交換周期”大小不同,信元平均網(wǎng)絡時延也不同。本部分考察了“交換周期”的設置對網(wǎng)絡時延的影響。

交換周期分別設為 512、1 024、2 048、4 096 個時隙,即分別以每 512、1 024、2 048或4 096個信元為一個交換幀,其余參數(shù)配置與(1)相同。

圖8給出了不同交換幀長度下的信元平均網(wǎng)絡時延隨負載量的變化曲線?？梢钥闯?當交換幀長度增大時,信元平均網(wǎng)絡時延逐漸增大。負載率在90%以上時尤為明顯。通過進一步仿真研究可以得知,這主要是由交換結構第三級的時延引起的:交換幀長度越長,在同一時隙下不同輸入端口處的信元,它們的目的輸出端口相同的概率也會越大。

圖8 新自尋路機制中“交換幀”長度對平均網(wǎng)絡時延的影響Fig.8 Average delay under different configurations of switching frame length in the new self-routed scheme

(4)為了進一步體現(xiàn)新自尋路機制對網(wǎng)絡性能的影響,本部分將其與傳統(tǒng)的CRRD算法進行了對比。

仿真配置如下:

“CRRD”:m=n=r=8。分組長度以1 024 byte為均值正態(tài)分布,定長信元長度為64 byte,匹配迭代次數(shù)為1,網(wǎng)絡負載量為10%～98%。

“新自尋路交換機制”:m=n=r=8。分組長度以1 024 byte為均值正態(tài)分布,定長信元長度為64 byte,一個交換周期包含2 048個時隙,每2 048個信元被看做一個交換幀,然后進行信元間插;網(wǎng)絡負載量為10%～98%。

圖9給出了兩種機制下,交換網(wǎng)絡中的信元平均時延隨負載量的變化。對比可以看出,新自尋路交換機制下,交換結構中的信元時延性能相比于CRRD有明顯優(yōu)勢(注意:為了更好顯示對比結果,曲線圖采用了半對數(shù)坐標,即縱坐標采用了基數(shù)為10的對數(shù)刻度,橫坐標仍為普通的等距刻度)。

圖9 CRRD和新自尋路機制下的信元平均網(wǎng)絡時延Fig.9 Average delay of CRRD and the new self-routed scheme

5 結束語

多級交換網(wǎng)絡調(diào)度算法的設計會直接影響網(wǎng)絡性能,因此對大容量調(diào)度算法的研究是很有必要的。本文提出的新自尋路交換機制可通過在交換網(wǎng)絡前端采取“信元間插”策略,重新為信元合理分配時隙,大大減輕網(wǎng)絡內(nèi)部的連續(xù)沖突;同時,通過在第一級設置邏輯指示器,為不同的業(yè)務流選取合適的交換單元,一定程度上保證了第二級負載均衡。

理論分析和仿真實驗表明,在平均分組長度或交換幀長度變化的情況下,新自尋路交換機制均有良好的網(wǎng)絡時延表現(xiàn)。相比于CRRD等傳統(tǒng)交換調(diào)度算法,該機制在網(wǎng)絡性能上優(yōu)勢明顯。新自尋路交換機制中的“信元間插”策略,不僅可以應用于三級Clos交換網(wǎng)絡,對其他多級交換網(wǎng)絡的工程實踐同樣具有一定的參考價值。

本文提出的交換機制是通過間插將輸入端的業(yè)務在“時間軸”上打散,那么是否可以用類似的思想,通過將業(yè)務在“空間”上均勻打散來減少網(wǎng)絡沖突,獲得較好的網(wǎng)絡性能,這可以作為下一步的研究方向。

[1] 戴曉慧.對十二五期間信息通信業(yè)發(fā)展的思考[EB/OL].2010-12-22[2012-09-04].www.ccidcom.com/html/yaowen/201012/22-12/132044.html.DAI Xiao-hui.Reflections on the development of information and communication industry during the second five[EB/OL].2010-12-22[2012-09-04].www.ccidcom.com/html/yaowen/201012/22-12/132044.html.(in Chinese)

[2] Chao H J,Park J,Artan S,et al.True Way:a highly scalable multi-plane multi-stage buffered packet switch.Workshop onHigh Performance Switching and Routing[C]//Proceedings of 2005 IEEE Workshop on High Performance Switching and Routing.Hong Kong:IEEE,2005.

[3] Clos C.A study of non-blocking switching networks[J].Bell System Tech Journal,1953,32(2):406-424.

[4] PunK,Hamdi M.Dispatching schemes for Closnetwork switches[J].Computer Networks,2004,44(5):667-679.

[5] Lei Wen,Xu Du.Asynchronous credit-based scheduling scheme for a multi-stage network[C]//Proceedings of 2005 International Conference on Communications,Circuits and Systems.Hong Kong:IEEE,2005:668-672.

[6] 李輝,王秉睿,黃佳慶,等.負載均衡自路由交換結構[J].通信學報,2009,30(5):1-8.LI Hui,WANG Bing-rui,HUANG Jia-qing,et al.Load-balanced self-routing switching structure[J].Journalon Communications,2009,30(5):1-8.(in Chinese)

[7] Ganjali Y,Keshavarzian A,Shah D.Input Queued Switches:Cell switching vs.packet switching[C]//Proceedings of the Twenty-Second Annual Joint Conference on Computer and Communications.[S.l.]:IEEE,2003:1651-1658.

[8] Smiljani A.Rate and delay guarantees provided by Clos packet switches with load balancing[J].IEEE/ACM Transactions on Networking,2008,16(1):170-181.