摘 要:Clos網(wǎng)絡是多端口的路由器和交換機中經(jīng)常采用的交換網(wǎng)絡，其優(yōu)點在于它是一個結(jié)構(gòu)全對稱的網(wǎng)絡。比較了多級Clos網(wǎng)絡分布式調(diào)度算法中定長分組和變長分組交換的特點;給出一種基于變長分組交換的MSM型三級Clos交換網(wǎng)絡結(jié)構(gòu)和相應的ACBS調(diào)度算法;消除了分組負載分配的不公平性。分析表明該調(diào)度算法優(yōu)于傳統(tǒng)算法，并通過仿真實驗驗證了算法的有效性。

關(guān)鍵詞:Clos; 交換網(wǎng)絡; 變長分組; 調(diào)度算法

中圖分類號:TN915; TP393 文獻標識碼:A 文章編號:1004-373X(2010)14-0105-04

Research on Varied Length Packet Mechanism and Scheduling Algorithm in Clos Switched Network

LIU Wei1， DU Juan2， YANG Shuai1

(1. The PLA Commanding Communications Academy， Wuhan 430010， China;

2. Chongqing Communication College， Chongqing 400035， China)

Abstract: Clos network is widely used in multi-port router and switch device， due to its holosymmetric network structure. The properties of fixed length cell and varied length packet switch in multi-level Clos network distributed scheduling algorithm are compared in this paper. A three-stage MSM Clos network structure based on varied length packet and correspongding ACBS scheduling algorithm are proposed， which eliminates the unfair load-allotment in the packet switch mechanism. The analysis shows that the scheduling algorithm is superior to the traditional algorithm. The simulation proves the efficiency of the proposed algorithm.

Keywords: Clos; switched network; varied length packet; scheduling algorithm

目前大容量交換結(jié)構(gòu)采用的分組交換技術(shù)主要是基于信元的(cell-based)，即在變長分組如IP進行交換前，先切割為定長的信元(cell)，通過交換結(jié)構(gòu)(switch fabric)后再在出端口重組為原變長分組[1-2]。這種技術(shù)可帶來很高的交換容量和吞吐率，如對于輸入緩存的縱橫開關(guān)(crossbar)單級交換結(jié)構(gòu)[3]，應當采用較高的內(nèi)部交換加速因子和優(yōu)良的交換調(diào)度算法時，可達到近Tb/s的交換容量和100%的系統(tǒng)吞吐率。本文首先比較了多級Clos網(wǎng)絡[4]的定長分組和變長分組交換的特點，然后給出了一種基于變長分組交換的MSM型三級Clos交換網(wǎng)絡結(jié)構(gòu)和相應的調(diào)度算法，并對算法性能進行了分析和仿真。

1 定長分組與變長分組交換的特點

雖然就交換結(jié)構(gòu)本身而言，基于信元的交換技術(shù)已發(fā)展的相當完善，但從系統(tǒng)的角度看它仍存在一些問題。首先，由于交換結(jié)構(gòu)在入端口需要對變長分組切割、在出端口需要對信元重組，從而引入了較大的交換時延;其次，在分組切割為信元的過程中還存在n+1問題;此外，多級交換網(wǎng)絡中采用定長信元交換，除了在單Crossbar中的缺點外，還會引起信元的亂序。信元間亂序會使交換網(wǎng)絡為了重排序而付出很大代價，所以在多級網(wǎng)絡中要盡量避免信元間的亂序。

開展對變長分組交換技術(shù)的研究是對現(xiàn)有交換技術(shù)的完善和補充，變長交換技術(shù)實際上就是在交換結(jié)構(gòu)中直接處理變長分組，而不將分組切割為信元再來傳輸。在數(shù)據(jù)通道上，當某個入端口開始交換一個分組到出端口時，這條入端口一出端口的數(shù)據(jù)通道一直保持暢通，直到整個變長分組被傳送到出端口才釋放該通道。為了提高變長交換的效率，解決分組切割和重組帶來的缺陷，降低網(wǎng)絡實現(xiàn)的成本和難度，通常在變長分組到達入端口時，并不采取真正的物理上的切割分組，而是邏輯的切割分組為定長信元，對定長信元背靠背傳輸，因此在傳輸?shù)倪^程中以及到達出端口處收到的分組仍然是完整的，從而避免了重組分組的操作。將每一個分組從邏輯上分割為多個信息單元，一個信息單元的長度是交換網(wǎng)絡一個時隙轉(zhuǎn)發(fā)信息的數(shù)量(為了簡單起見，也將其稱之為信元)。分割后只在第一個信元加上分組標識，在最后一個信元加分組結(jié)束標志，其他的中間信元不需要加任何開銷(這種交換方式類似于直接連接網(wǎng)絡中的Virtual Cut-Through交換方式)。

2 基于變長分組交換的MSM型三級Clos結(jié)構(gòu)

2.1 改進的MSM型三級Clos結(jié)構(gòu)

為了更好地支持交換結(jié)構(gòu)的可擴展性[5]，這里改進了MSM型的三級Clos結(jié)構(gòu)，在輸入增加了隊列管理器，輸出增加了令牌發(fā)生器和輸出調(diào)度器，如圖1所示。

圖1 改進的MSM型三級Clos結(jié)構(gòu)

在這個三級結(jié)構(gòu)中，將這三級分為輸入級模塊(ingress module，IM)、中間級和輸出級(egress module)。每一級都有多個模塊 (Modules)，每個模塊又有多個入端(inport，IP)和出端(outport，OP)。這里只有中間級是純粹的Crossbar交換結(jié)構(gòu)，沒有緩存器件;而輸入級和輸出級模塊中都含有緩存隊列。 輸入級包含VOQ以消除HOL阻塞，輸出級的輸出隊列用于當多個數(shù)據(jù)包競爭同一輸出端口和信元重組的緩存。在輸出級當中，每個輸出端口都擁有一個輸出端口調(diào)度器(output scheduler，OS)。

另外，實際交換機應該是N×N的對稱結(jié)構(gòu)，所以規(guī)定三級結(jié)構(gòu)中輸入級和輸出級模塊的個數(shù)是相等的，并且每個輸入模塊的輸入端口數(shù)和每個輸出模塊的輸出端口數(shù)也應該是相等的。而中間級crossbar模塊個數(shù)和每個模塊的端口數(shù)是可以調(diào)整的，但應該是輸入端和輸出端相等的“方形”結(jié)構(gòu)，如圖2所示。

輸入級的作用:去往特定目的端口的數(shù)據(jù)包在輸入端的VOQ中排隊，等待發(fā)送;VOQ 避免了隊頭阻塞;隊列控制器將隊列的狀態(tài)通知相應輸出端口的輸出調(diào)度器(當隊列長度超過了一定的門限值時，輸入級向輸出調(diào)度器發(fā)送隊列狀態(tài)信息);根據(jù)輸出調(diào)度器返回的信息發(fā)送存儲的數(shù)據(jù)包。

輸出級的作用:解決數(shù)據(jù)包在輸出級的沖突;用于對分段數(shù)據(jù)包的重組;根據(jù)調(diào)度算法和收到的隊列狀態(tài)信息發(fā)放令牌，分配輸出 端口的帶寬(帶寬的分配即可按隊列長度劃分可按隊列的服務等級來劃分)。

中間級的作用:在MSM結(jié)構(gòu)中，中間級無緩存，由Crossbar組成，中間級與輸入級、輸出級采用了全互連的方式連接。中間級的主要作用是為從輸入級轉(zhuǎn)發(fā)出來的數(shù)據(jù)包提供多條路徑。

隊列管理器:在每一個輸入級模塊中，都需要有一個隊列管理器來管理VOQ的狀態(tài)，并根據(jù)當前狀態(tài)及時向位于輸出端口的輸出調(diào)度器發(fā)出隊列狀態(tài)信息來請求輸出帶寬。每當隊列狀態(tài)發(fā)生變化時，隊列管理器就向輸出調(diào)度器發(fā)送信息，通知調(diào)度器及時更新隊列數(shù)據(jù)庫。為了減少控制信息的流量，以避免控制信息過多地占用數(shù)據(jù)通道，我們設定，每當隊列的長度超過一個事先設置好的門限時，才進行發(fā)送隊列信息的操作。

輸出調(diào)度器:接收來自輸入級隊列管理器的隊列狀態(tài)信息，并根據(jù)所維護的隊列狀態(tài)數(shù)據(jù)庫中的隊列屬性，按照一定的調(diào)度算法來進行調(diào)度，并將自己從令牌發(fā)生器處獲得的令牌分配給滿足條件的隊列。

令牌發(fā)生器:令牌是由專門的令牌發(fā)生器產(chǎn)生的，每個輸出級擁有一個令牌發(fā)生器，它根據(jù)各個輸出端口的帶寬來產(chǎn)生令牌，并把令牌分配到各輸出端口供輸出調(diào)度器調(diào)配。

圖2 改進的三級結(jié)構(gòu)詳細示意圖

優(yōu)點:

經(jīng)過改進的三級結(jié)構(gòu)可以構(gòu)造出任意大小的交換機而沒有性能的損失，它只需要提供出足夠的用于互連的交換單元即可，系統(tǒng)還可以增加其他速率的端口或?qū)河卸丝诘闹赜脕碓黾映跏紩r的系統(tǒng)速率。同時，集中式調(diào)度算法的復雜度與端口數(shù)量有關(guān)，增加端口數(shù)量將進一步加大調(diào)度器的實現(xiàn)難度，而分布式的輸出調(diào)度器放置，增加了交換結(jié)構(gòu)的可擴展性?？傊倪M的交換結(jié)構(gòu)具有較強的可擴展性，可以任意增加交換單元的數(shù)目和端口速率來擴展交換容量[6-8]。

2.2 ACBS算法調(diào)度過程

根據(jù)上述的多級Clos交換網(wǎng)絡結(jié)構(gòu)，設計相應的ACBS(asynchronous credit-based scheduling)算法，ACBS與傳統(tǒng)用于多級結(jié)構(gòu)的調(diào)度算法區(qū)別在于:調(diào)度器分布在各個輸出端口，是一種分布式的調(diào)度算法;各個輸入級獨立發(fā)送數(shù)據(jù)包，支持第一級鏈路的負載均衡;摒棄了傳統(tǒng)的“兩次匹配”的調(diào)度過程，采用一次調(diào)度;調(diào)度算法的成功實現(xiàn)要依賴于令牌的分配和發(fā)放。

在該結(jié)構(gòu)中，一個輸入隊列象征著一個用戶流，同時對應著一個輸入端口、輸出端口和服務屬性。一個輸出調(diào)度器與一個目的端口相連，調(diào)度器通過將輸出端口帶寬分配給所有競爭的隊列來控制數(shù)據(jù)從輸入隊列中“拉”出。當隊列某一狀態(tài)發(fā)生變化時，隊列管理器立刻向調(diào)度器發(fā)出隊列狀態(tài)改變信息，調(diào)度器將自己從令牌發(fā)生器獲得的令牌分配出去，令牌經(jīng)過交換結(jié)構(gòu)被送往輸入級，如圖3所示。輸入級積累一定的令牌，用來發(fā)送數(shù)據(jù)包給交換結(jié)構(gòu)。收到輸出調(diào)度器返回的令牌之后，隊列管理器將數(shù)據(jù)包從隊列中移出并向交換結(jié)構(gòu)轉(zhuǎn)發(fā)[9]。

圖3 基于流的調(diào)度過程

2.2.1 ACBS輸入級算法步驟

ACBS輸入級算法步驟如下:

步驟1: 收到來的數(shù)據(jù)包，讀取其目的地址并將其分往相對應的VOQ(i，j，h)中。由于在每個輸入級當中，n個輸入端口共用同一組VOQ，因此，當多個輸入端口同時將數(shù)據(jù)送往同一個VOQ時，采取隨機選取方式解決沖突。當輸入流具有不同的相對優(yōu)先級時，則根據(jù)優(yōu)先級等級個數(shù)來增加VOQ的組數(shù)。

步驟2: 隊列管理器負責監(jiān)控隊列狀態(tài)，當VOQ(i，j，h)隊列狀態(tài)發(fā)生改變的時候，立刻把隊列狀態(tài)消息status_msg(i，j，h)送到輸出調(diào)度器OS(j，h)處。但是由于控制信息的發(fā)送仍然是占用數(shù)據(jù)通道，因此，為了減小控制信息的流量，采取了每隔一定的時間發(fā)送隊列狀態(tài)信息的方法。該算法中，將時間間隔定義為VOQ(i，j，h)的隊列長度Queue_L(i，j，h)超過了門限值Threshold，隊列控制器才發(fā)送:status_msg(i，j，h):Queue_L(I，j，h)≥Threshold。

步驟3: 接收令牌Credit(i，j，h)。為了方便地管理每個隊列，隊列管理器為每個VOQ維持了一個令牌計數(shù)器CC(i，j，h)。當令牌從輸出調(diào)度器OS(j，h)返回給輸入級IM(i)時，隊列控制器作出以下操作:CC′(i，j，h)=CC(i，j，h)+1。

步驟4: 輸入級IM(i)將CC(i，j，h)最大的VOQ中的數(shù)據(jù)包從隊列中取出，如果處理的對象為定長分組，就直接將其分發(fā)到第一級的所有鏈路上;如果需要交換的是變長分組，則先將其切分為相同長度的分組，再逐一轉(zhuǎn)發(fā)到第一級的所有鏈路上。同時，將CC(i，j，h)減去分組長度對應比例(比例設為1個令牌可以發(fā)送長度為所有數(shù)據(jù)包平均長度Avrg_L的分組)的令牌，更新CC(i，j，h)。當鏈路空閑后，重復步驟4，直到IM(i)中所有CC(i，j，h)<0。

2.2.2 ACBS輸出級算法步驟

ACBS輸出級算法步驟如下:

步驟1: 輸出調(diào)度器OS(j，h)維持了輸入級所有請求本端口帶寬的VOQ的隊列狀態(tài)數(shù)據(jù)庫。它實時接收來自輸入級的隊列狀態(tài)信息status_msg(i，j，h)，并同時更新隊列狀態(tài)數(shù)據(jù)庫。

步驟2: 輸出級EM(j)的令牌發(fā)生器按照各輸出端口帶寬以一定速率產(chǎn)生令牌，并將令牌定時分配給各輸出端口。目前討論的交換結(jié)構(gòu)所有輸出端口帶寬相同，因此，所有輸出端口獲得相同的令牌。

步驟3: 輸出調(diào)度器OS(j，h)根據(jù)隊列狀態(tài)數(shù)據(jù)庫對輸入級的VOQ進行調(diào)度，給有資格獲得輸出帶寬的VOQ返回令牌。在本算法中，為了簡化調(diào)度過程，定義隊列長度最長的VOQ(i，j，h)可以獲得令牌。輸出調(diào)度器OS(j，h)根據(jù)其隊列長度Queue_L(i，j，h)的比例減去已發(fā)送的令牌值;若此時OS(j，h)的令牌有剩余，則重復步驟3將余下的令牌分發(fā)給其他VOQ。

步驟4: 接收從中間級到來的信元，將信元放入輸出隊列中等待重組轉(zhuǎn)發(fā)。

3 ACBS調(diào)度算法及性能分析

在仿真實驗中首先檢驗了ACBS算法在變長分組交換體制下的性能，圖4給出了仿真性能，在變長分組交換體制下，當輸入負載在0.5以下時，ACBS算法能獲得良好的時延特性。

圖4 ACBS算法在變長分組交換體制下的仿真

圖5 ACBS算法和CRRD-PM調(diào)度算法的性能比較

同時，也將ACBS算法和CRRD-PM調(diào)度算法進行了比較，由圖5可以看出ACBS能有效地降低分組的端到端時延，這是因為在ACBS中，采用1次調(diào)度的方式進行輸入/輸出端的匹配;而且數(shù)據(jù)交互實時進行，有效地降低了分組在VOQ中的配對時間。而CRRD采用輪詢的方式進行二次調(diào)度，當輸入負載接近100%時，會引起分組的積壓，增加了總的交換時延。

4 結(jié) 語

通過性能分析和比較，對三級Clos網(wǎng)絡中交換機制選擇可以得出如下結(jié)論:采用變長分組交換不需要將分組分割的ISM模塊和信元重組的ORM模塊，可以降低成本，同時，變長分組交換較定長信元交換節(jié)省開銷，可以充分利用交換網(wǎng)絡資源;更為重要的是在多級網(wǎng)絡中，變成分組交換不會引起同一分組信元間的亂序，不需要引入了輸出重排序緩存或負載的防止信元亂序算法，降低了交換網(wǎng)絡調(diào)度算法的實現(xiàn)難度;但是變 長分組交換對輸入業(yè)務的適應性不如定長信元交換，在變長分組交換中，交換網(wǎng)絡的性能和分組到達以及分組長度分布具有很大的關(guān)系;而在定長信元交換中，對分組長度分布的依賴性不是很強;同時，網(wǎng)絡負載較大時，變長分組交換方式性能不如定長信元交換[10];ACBS算法屬于流調(diào)度算法，采用分布式的調(diào)度方式，通過輸出調(diào)度器將數(shù)據(jù)包從輸入端口“拉”向輸出端口。在ACBS中，輸入/輸出之間采用異步交互控制信息的方式進行分布式的一次調(diào)度算法。仿真表明，它能考慮業(yè)務特性和輸出帶寬進行調(diào)度，降低數(shù)據(jù)包的平均時延，能方便地支持負載均衡。

參考文獻

[1]FIROIU V，L E BOUDEC J Y， TOWSLEY D， et al.Theories and models for internet quality of service[J] . Proceedings of the IEEE， 2002， 90 (9): 1565-1591.

[2]王重鋼，隆克平，龔向陽，等.分組交換網(wǎng)絡中隊列調(diào)度算法的研究及其展望[J].電子學報，2001，29(4):43-48.

[3]JINOO Joung，JONGTAE Song，SOONSEOK Lee. Flow-based QoS management architectures for the next generation network[J]. ETRI Journal， 2008， 30(2):238-248.

[4]WANG F，ZHU Wen-qi，HAMDI M.The central-stagebuffered Clos-network to emulate an OQ switch[C]//IEEE Globecom Proceedings. California: [ s.n.] ， 2006:4244-4257.

[5]楊君剛，劉增基，顧華璽，等.混合交換機制三級Clos網(wǎng)絡分布式調(diào)度算法[J].西安電子科技大學學報，2008，35(4):581-585.

[6]NICT.New generation network architecture[M/OL].[ S.l.] : [ s.n.] ， [ 2007-10-08] . http://akari-project.nict.go.jp/eng/.October 2007.

[7]GANJALI Y， KESHAVARZIAN A， SHAH D. Input queued switches: cell switching vs.packet switching[C]//IEEE INFOCOM’03. San Francisco: [ s.n.] ， 2003: 1651-1658.

[8]ZHONG Hakhan， XU Du， ZHU Zhen-yu.A parallel packet switch supporting variable-length packets[C]//International Conference on Communications， Circuits and Systems Proceedings. Hong Kong: [ s.n.] ， 2005: 613-617.

[9]GOUDREAU M W. Scheduling algorithms for input-queued switches:Randomized techniques and experimental evaluation[C]//IEEE INFOCOM’00.TelAviv: [ s.n.] ， 2000: 1624-1643.

[10]SHI Lei， LI Wen-jie. Flow mapping in the load balancing parallel packet switches[C]//Workshop on High Performance Switching and Routing.Hong Kong: [ s.n.] ， 2005: 254-258.