用于多級(jí)交換網(wǎng)絡(luò)的一種高效自尋路技術(shù)

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

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

1 引 言

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

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

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

2 三級(jí)Clos交換網(wǎng)絡(luò)架構(gòu)

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

圖1 三級(jí)Clos交換網(wǎng)絡(luò)架構(gòu)Fig.1 Three-stage Clos network architecture

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

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

3 三級(jí)Clos結(jié)構(gòu)中的新自尋路交換機(jī)制

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

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

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

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

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

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

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

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

表1 二進(jìn)制編碼轉(zhuǎn)換表Table 1 Binary conversion table

對(duì)于任意一個(gè)連續(xù)信元分組,當(dāng)判斷出它的新時(shí)隙號(hào)序列后,會(huì)將原分組包含的所有信元一一順序地分配到新時(shí)隙中。因此,某連續(xù)信元分組經(jīng)間插后,雖然信元不再連續(xù),但該分組包含的所有信元并不亂序,即先后順序依然不變。間插后的交換幀如圖3所示。可以看出,經(jīng)過(guò)間插后,盡量保證了相鄰信元的目的端口不同。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由于 N≥2,且 m ≥1,n≥1,因此 PCellInterleaved≤1/16。當(dāng)N增大時(shí),PCellInterleaved將更小。

通過(guò)以上對(duì)比分析可知,PCellInterleaved

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

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

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

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

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

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

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

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

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

圖8給出了不同交換幀長(zhǎng)度下的信元平均網(wǎng)絡(luò)時(shí)延隨負(fù)載量的變化曲線。可以看出,當(dāng)交換幀長(zhǎng)度增大時(shí),信元平均網(wǎng)絡(luò)時(shí)延逐漸增大。負(fù)載率在90%以上時(shí)尤為明顯。通過(guò)進(jìn)一步仿真研究可以得知,這主要是由交換結(jié)構(gòu)第三級(jí)的時(shí)延引起的:交換幀長(zhǎng)度越長(zhǎng),在同一時(shí)隙下不同輸入端口處的信元,它們的目的輸出端口相同的概率也會(huì)越大。

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

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

仿真配置如下:

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

[1] 戴曉慧.對(duì)十二五期間信息通信業(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] 李輝,王秉睿,黃佳慶,等.負(fù)載均衡自路由交換結(jié)構(gòu)[J].通信學(xué)報(bào),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.