交換結(jié)構(gòu)到達(dá)分組可選輸出端口個數(shù)的研究

摘 要:針對目前單一路徑路由交換機(jī)制的問題，引出多下一跳路由交換機(jī)制，并在路由交換協(xié)同設(shè)計的基礎(chǔ)上分析討論了到達(dá)分組可選輸出端口個數(shù)k的取值，基本思路是路由層面分析路由表轉(zhuǎn)發(fā)表對k，取值要求特點(diǎn)，交換層面基于Mp-iSLIP匹配算法對比不同k取值下時延丟包率的仿真結(jié)果，綜合兩方面結(jié)果得出當(dāng)k=3時，路由實(shí)現(xiàn)難度與交換性能提高得到較好的折中。

關(guān)鍵詞:多下一跳路由; 調(diào)度; 匹配算法; 多輸出端口

中圖分類號:TP393文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2009)09-3490-03

doi:10.3969/j.issn.1001-3695.2009.09.82

Research on number of cell’s output port for switches

ZHENG De-ren1， WANG Ke-ren1， YI Peng1， LI Hui2

(1. National Digital Switch System Engineering Technological R D Center， Zhengzhou 450002， China; 2. Shenzhen Graduate School， Peking University， Shenzhen Guangdong 518055， China)

Abstract:Aiming at resolving the shortcomings of traditional single routing and switching scheme， this paper put forwards multi-hop routing and switching scheme. From the view point of the cooperation with routing and switching， this thesis discussed the numerical value of k which was the number of arriving cell’s output port. First analyzed the character of the router table and forward table to k， then simulated the delay andloss performance based on the Mp-iSLIP for IQ switches. Both results show that it can get the tradeoff of routing implement difficulty and switching performance when k is 3.

Key words:multi-hop route; scheduling; matching algorithm; multiple output ports

0 引言

傳統(tǒng)的輸出排隊(duì)(OQ)[1]、輸入排隊(duì)(IQ)[2] 、聯(lián)合輸入輸出排隊(duì)(CIOQ)[3]和基于帶緩存交叉開關(guān)構(gòu)建的聯(lián)合輸入交叉節(jié)點(diǎn)排隊(duì)(CICQ)[4]交換結(jié)構(gòu)都是基于到達(dá)分組具有惟一輸出端口的交換機(jī)制。隨著網(wǎng)絡(luò)需求量的不斷增加，這種機(jī)制是影響、制約路由交換設(shè)備和網(wǎng)絡(luò)性能的瓶頸，主要表現(xiàn)為:分組僅有惟一輸出端口，相同端口的爭用極易引發(fā)交換擁塞，直接導(dǎo)致設(shè)備時延性能惡化，不利于支持實(shí)時業(yè)務(wù);為解決交換擁塞，需要采用內(nèi)部加速或復(fù)雜的調(diào)度，而且需要配合以高速大容量緩存，這些已成為高速路由交換設(shè)備的實(shí)現(xiàn)瓶頸;單一路徑的路由機(jī)制使得當(dāng)前網(wǎng)絡(luò)的抗毀性能較差，單個網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)生故障會對網(wǎng)絡(luò)業(yè)務(wù)性能產(chǎn)生較大影響。

目前所有交換結(jié)構(gòu)由于都是基于到達(dá)分組僅具有惟一輸出端口的準(zhǔn)則，在網(wǎng)絡(luò)突發(fā)業(yè)務(wù)條件下極易因?yàn)檩敵龆丝跔幱枚l(fā)生擁塞，而且這種擁塞無法通過交換結(jié)構(gòu)和調(diào)度算法的優(yōu)化設(shè)計來避免，即便是在提供服務(wù)質(zhì)量保障方面最具性能優(yōu)勢的輸出排隊(duì)交換結(jié)構(gòu)也無能為力。以一個4×4交換結(jié)構(gòu)為例，如圖1所示，傳統(tǒng)路由交換機(jī)制由于報文僅有惟一的輸出端口，一旦四個輸入端口到達(dá)業(yè)務(wù)均具有相同的輸出端口時，僅有其中一個輸入端口的報文可以獲得調(diào)度輸出，其余輸入端口的報文被阻塞。由此可見，基于單一輸出端口的交換機(jī)制在存在端口爭用時的實(shí)時吞吐量很低，對于發(fā)生輸出端口爭用的重負(fù)載業(yè)務(wù)，其擁塞程度還會不斷加劇。

為了從根源上解決問題，國家“863”課題一種基于多下一跳路由的動態(tài)均衡路由交換機(jī)制通過基于聚合等價類的路由策略得到具有多條下一跳路由信息的路由表[5]，從而使進(jìn)入路由交換設(shè)備的分組具有多個可選的輸出端口，進(jìn)而通過新型交換機(jī)制的研究實(shí)現(xiàn)分組基于多個可選輸出端口動態(tài)均衡的路由交換。基于多個可選輸出端口的交換機(jī)制可以有效緩解輸出端口爭用，從根源上消除重度擁塞帶來的弊端。同樣以一個4×4交換結(jié)構(gòu)為例，如圖2所示，假定每個分組具有兩個可選輸出端口，當(dāng)四個輸入端口到達(dá)業(yè)務(wù)存在輸出端口爭用時，可以通過靈活的交換調(diào)度機(jī)制動態(tài)地選取其他可選輸出端口，因此比傳統(tǒng)交換機(jī)制能夠獲得更高的吞吐量，避免輸出帶寬資源浪費(fèi)，從而可以大大減輕擁塞所引發(fā)的弊端。

對于多下一跳路由，其跳數(shù)k的取值范圍嚴(yán)重影響路由選擇的復(fù)雜度及其實(shí)現(xiàn)難度。到目前為止，并沒有針對多下一跳跳數(shù)k的具體研究。本文以路由交換協(xié)同設(shè)計思想為指導(dǎo)，從路由交換兩個層面對k取值進(jìn)行了分析討論。

1 路由與轉(zhuǎn)發(fā)表特點(diǎn)

路由表是路由器中重要的數(shù)據(jù)單元，是路由查找轉(zhuǎn)發(fā)的依據(jù)。由于安全、費(fèi)用和帶寬等因素，路由器需要為某些數(shù)據(jù)流做負(fù)載平衡和策略路由，在路由表中為一些目的網(wǎng)絡(luò)保存多個下一跳信息，路由表中存在著相當(dāng)數(shù)量的多下一跳路由。

圖3是對5個BGP路由表下一跳信息的統(tǒng)計[5]，圖中按照多下一跳路由的下一跳個數(shù)不同分別作了統(tǒng)計。其中具有2個下一跳的路由所占路由表比例較大，具有4個以上下一跳的路由所占比例較小(Mae-West最大，為2.61%)。5個路由表中，Mae-West的多下一跳路由所占比例最大，接近50%;Aads的多下一跳路由所占比例最小，但也達(dá)到了19%。由此可見，多下一跳路由在路由表中的存在是不能忽視的，在進(jìn)行路由查找算法設(shè)計時，多下一跳路由的查找應(yīng)該被考慮進(jìn)來;絕大部分多下一跳路由的下一跳個數(shù)均不大于4，在5個路由表中具有4個以上下一跳的路由所占路由表的比例都是很小的。其中Aads和Pacific Bell最小為0，Mae-West最大，為2.61%。

傳統(tǒng)的基于單一路由機(jī)制的轉(zhuǎn)發(fā)表僅需[log2 N]比特即可滿足單播輸出端口的標(biāo)志要求。當(dāng)采用聚合等價類的多下一跳路由機(jī)制時，假定對每個分組維護(hù)k個下一跳路由，則單播轉(zhuǎn)發(fā)表需要min(K「log2 N」，N)比特才能滿足輸出端口標(biāo)志要求，這對于轉(zhuǎn)發(fā)表的存儲、查找、維護(hù)和更新方面均引入了新的需要研究的問題。轉(zhuǎn)發(fā)表輸出端口標(biāo)志長度的增加，將引發(fā)諸如轉(zhuǎn)發(fā)表表項(xiàng)存儲空間不足、線速表項(xiàng)查找難度加大和表項(xiàng)實(shí)時維護(hù)困難等新問題。在需要維護(hù)的目的端口數(shù)目較大的情形下，轉(zhuǎn)發(fā)表輸出標(biāo)簽長度的增加將導(dǎo)致新生成IP包的標(biāo)簽部分占用過多的內(nèi)部傳輸帶寬，降低帶寬利用效率。 此外，由于新的轉(zhuǎn)發(fā)表反映的是多個下一跳路由，其更新頻率必然將大大增加，從而將進(jìn)一步加深轉(zhuǎn)發(fā)表表項(xiàng)實(shí)時維護(hù)的難度。轉(zhuǎn)發(fā)表查表、管理、維護(hù)以及壓縮極大地限制了多下一跳個數(shù)的取值，要求多下一跳k的取值越小越好。

2 Mp-iSLIP調(diào)度算法

交換層面到達(dá)分組多個可選輸出端口的數(shù)值等于路由層面的多下一跳的數(shù)值，也用k來表示。MP-iSLIP調(diào)度算法由相互獨(dú)立執(zhí)行的入隊(duì)機(jī)制和調(diào)度策略組成，入隊(duì)機(jī)制通過對到達(dá)分組的k個可選輸出端口對應(yīng)的k個VOQ進(jìn)行隊(duì)長的比較，選擇進(jìn)入隊(duì)列中緩存分組最少的VOQ;調(diào)度策略則根據(jù)iSLIP迭代算法的請求回應(yīng)匹配機(jī)制決定要調(diào)度離去的分組。下文描述都是基于N×N規(guī)模IQ交換結(jié)構(gòu)，VOQij標(biāo)志輸入緩存單元源端口為i目的端口為j的虛擬輸出隊(duì)列;Lij標(biāo)志VOQij的隊(duì)列長度即緩存隊(duì)列中的分組個數(shù);Cq為VOQ隊(duì)列容量;k標(biāo)志每個到達(dá)分組具有的可選輸出端口個數(shù)。

1)入隊(duì)機(jī)制設(shè)計 基于惟一輸出端口的分組根據(jù)其輸出端口進(jìn)入相應(yīng)的VOQ，例如輸入端口為i輸出端口為j的分組調(diào)度進(jìn)入VOQij。基于k個可選輸出端口的分組需要對k個VOQ中緩存分組計數(shù)比較選取隊(duì)列長度最短的VOQ調(diào)度進(jìn)入，動態(tài)均衡各個輸入端口虛擬輸出隊(duì)列的長度。

2)調(diào)度策略設(shè)計 調(diào)度策略不受前級入隊(duì)的影響，從N個VOQ中輪詢選擇一個VOQ與輸出端口匹配。在每一個時隙三步迭代與SLIP算法基本相同[6]，具體描述如下:

a)請求(request)。每一個未獲得匹配的輸入端口i向該端口中非空VOQ對應(yīng)的輸出端口發(fā)送服務(wù)請求。

b)允許(grant)。如果未獲得匹配的輸出端口j收到一個或多個輸入端口的服務(wù)請求，輸出端口的允許指針gj從當(dāng)前位置以固定循環(huán)優(yōu)先級方式選擇最接近輸出端指針的輸入端口，發(fā)送允許信號至該輸入端口，并根據(jù)c)的結(jié)果修改指針gj。若在c)中該允許信號被相應(yīng)輸入端i接收，則輸出端指針gj更新指向輸入端口i的下一個位置，否則指針gj不變。

c)接收(accept)。如果輸入端口i收到多個輸出端口的服務(wù)允許信號，則輸入端口從ai當(dāng)前位置以循環(huán)優(yōu)先級方式選擇最接近輸入端指針ai的輸出端口j，發(fā)送接收信息至該輸出端口j，并將該輸入端口的指針ai更新指向輸出端口j的下一個位置，并將找到的輸入—輸出匹配用于配置交換陣列。

3 性能仿真

本文采用改進(jìn)的交換系統(tǒng)性能仿真評價系統(tǒng)SPES[7]。此仿真系統(tǒng)是以時隙的方法來運(yùn)行，采用了模塊化的設(shè)計，包括業(yè)務(wù)源模型、調(diào)度算法、排隊(duì)機(jī)制、交換結(jié)構(gòu)等模塊，改進(jìn)了業(yè)務(wù)源模型用于產(chǎn)生具有多個可選輸出端口的分組。仿真基于N×N大小IQ交換結(jié)構(gòu)對不同可選輸出端口k取值的MP-iSLIP調(diào)度算法進(jìn)行時延與丟包率的仿真比較，N分別取16、32。仿真器工作在時隙粒度且仿真時間為100 000時隙，分組大小為64 Byte，每個輸入端口的輸入緩沖大小為10 240分組，VOQ的長度為10 240/N。分組到達(dá)采用貝努利和突發(fā)兩模型[7]。其中評估平均突發(fā)長度為20。

假定ρ∈(0，1]為歸一化的流量負(fù)載。本文采用如下常用的流量分布模型:

a)均勻分布模型。輸入的分組到各個輸出端口的概率是相等的。λij=ρ/N，i，j。λij指輸入端口i到輸出端口j的流量。

b)非均勻分布模式(線性傾斜)[8]。流量分布滿足關(guān)系:λi|i+d|=ρ(N-d)/(N(N+1)/2)，d=0，1，…，N-1也就是λi|j+1|與λij相比流量減少ρ/(N(N-1)/2)。

k個可選輸出端口的產(chǎn)生是獨(dú)立同分布的，即對均勻分布模型，每個分組的k個輸出端口相互獨(dú)立采用均勻模型產(chǎn)生;對非均勻分布模型，每個分組的k個輸出端口相互獨(dú)立采用非均勻模型產(chǎn)生。

3.1 均勻分布業(yè)務(wù)源

在貝努利業(yè)務(wù)源均勻分布的情況下，由于MP-iSLIP調(diào)度算法能夠達(dá)到100%的吞吐量，丟包率恒為零，只能觀察分組的平均時延性能的變化;在突發(fā)業(yè)務(wù)源均勻分布的情況下，MP-iSLIP調(diào)度算法的丟包率如圖4、5所示，當(dāng)K>1時丟包率為零，故也可以通過觀察分組的平均時延性能變化討論k的取值。如圖6～9所示，可以看出無論N取16還是32，K取值的選擇對交換結(jié)構(gòu)大小變化并不敏感。隨著k取值的增大，分組的輸出時延性能均有改善，并且改善的幅度越來越小，當(dāng)k>3時分組平均時延性能改善得并不明顯。

3.2 非均勻分布業(yè)務(wù)

在貝努利與突發(fā)業(yè)務(wù)源非均勻分布的情況下，由于MP-iSLIP調(diào)度算法對非均勻業(yè)務(wù)不能實(shí)現(xiàn)100%的吞吐量，存在分組的丟失，丟包率不恒為零，此時分組的平均時延性能并不能完全說明問題， 不同k值所帶來的差別主要體現(xiàn)在丟包率上，故只觀察分組丟包率的變化，如圖10～13所示。從這四個圖的丟包率可以看出，無論對不同大小的交換結(jié)構(gòu)還是對不同的到達(dá)業(yè)務(wù)源，當(dāng)k>3時分組丟包率改善得并不明顯。

4 結(jié)束語

多輸出端口數(shù)k值的選擇確定主要從實(shí)現(xiàn)難度和性能改進(jìn)效果兩方面進(jìn)行折中，實(shí)現(xiàn)難度隨著k的增大而成倍增長，改進(jìn)效果卻在k>3時隨k的增大，在時延和丟包率方面改進(jìn)并不明顯。所以，本文以路由表的特點(diǎn)為基礎(chǔ)，綜合路由層面實(shí)現(xiàn)難度與交換層面的性能改善得出k=3。

多輸出端口數(shù)k的選擇不只是交換的問題，它還包括路由層面的各方面問題，隨著網(wǎng)絡(luò)需求量的不斷增長，多下一跳路由必將引領(lǐng)新一代革新，而下一跳跳數(shù)的取值范圍以及多跳在路由和交換中的處理則是極為重要的研究熱點(diǎn)，因此多輸出端口數(shù)k的選擇急需數(shù)學(xué)理論的分析。

參考文獻(xiàn):

[1]KESIDIS G， McKEOWN N. Output-buffer ATM packet switching for integrated-services communication networks[C]// Proc of IEEE ICC.1997.

[2]McKEOWN N. Scheduling algorithms for input-queued cell switches[D].Berkeley， CA: University California， Dept. Electronic Engineering Computer Science， 1995.

[3]CHUANG S T， GOEL A， McKEOWN N， et al. Matching output queueing with a combined input output queued switch[J]. IEEE Journal Selected Areas in Communications， 1999， 17(12):1030-1039.

[4]JAVIDI T， MAGILL R， HRABIK T. A high-throughput scheduling algorithm for a buffered crossbar switch fabric[C]// Proc of IEEE ICC. 2001:1581-1587.

[5]梁志勇， 徐恪. 支持壓縮和多下一跳查找的路由查找方案[J]. 軟件學(xué)報， 2004，15(4):550-560.

[6]McKEOWN N. The iSLIP scheduling algorithm for input-queued switches[J]. IEEE/ACM Trans on Networking， 1999， 7(2):188-201.

[7]扈紅超，伊鵬.高性能交換與調(diào)度仿真平臺的設(shè)計與實(shí)現(xiàn)[J].軟件學(xué)報，2008， 19(4):1037-1050.

[8]BIANCO A， GIACCONE P， LCONARDI E. A framework for differential frame-based matching algorithms in input queued switches[C]// Proc of IEEE INFOCOM. 2004: 1147-1157.