摘 要：交換結(jié)構(gòu)是交換機(jī)的核心，決定著交換機(jī)的性能。MSM型Clos交換結(jié)構(gòu)是一種高性能交換結(jié)構(gòu)，為有效仿真分析該交換結(jié)構(gòu)建立了一種OPNET仿真模型。該模型將交換系統(tǒng)抽象為一個星型網(wǎng)絡(luò)，其邊緣節(jié)點對應(yīng)交換結(jié)構(gòu)輸入和輸出，中心節(jié)點對應(yīng)MSM型Clos交換結(jié)構(gòu)；并使用此模型仿真分析了3種典型算法的性能。該模型為交換結(jié)構(gòu)性能的仿真分析提供了一種有效途徑。

關(guān)鍵詞：MSM；Clos；OPNET建模；調(diào)度算法；交換結(jié)構(gòu)

中圖分類號：TP274文獻(xiàn)標(biāo)識碼：B文章編號：1004373X(2008)1902504

OPNET Modeling and Simulation of MSM Clos Switch Fabric and Algorithm with OPNET

HUYAN Lang，ZHOU Quan

(National Key Laboratory，Xi′an Institute of Space Radio Technology，Xi′an，710000，China)

Abstract：Switching fabric is the core of switch and determines the performance of switching system.MSM Clos switching fabric is a high performance switching fabric.In order to analyze and simulate the switching fabric efficiently，a simulation modelis presented with OPNET.Switching system is modeled as a star network in which the center node and periphery node correspond to MSM Clos switching fabric，and input/output respectively.The performance of three classical algorithms is simulated with the model which provides an efficient approach for simulation and analysis of the performance of switching fabric.

Keywords：MSM;Clos;OPNET modeling;scheduling algorithm;switching fabric

1 引 言

交換設(shè)備的核心是交換結(jié)構(gòu)，也是制約其性能的關(guān)鍵因素之一。三級Clos網(wǎng)絡(luò)具有模塊化設(shè)計，容量大及可擴(kuò)展性強(qiáng)等優(yōu)點，是一種高性能交換結(jié)構(gòu)，近年來以Clos網(wǎng)絡(luò)為基礎(chǔ)提出了多種交換結(jié)構(gòu)，如：如S3型^［1］、MSM型^［2，3］、MMM型^［4］、MmM型^［5］和SMM^［6］型等。在文獻(xiàn)中研究最多的是S3型和MSM型。對應(yīng)各種結(jié)構(gòu)又提出了多種調(diào)度算法，如對應(yīng)MSM型結(jié)構(gòu)有RD^［2］算法CRRD^［3］、CMSD^［3］和SRRD^［7］等算法。

可是如何來衡量這些結(jié)構(gòu)和算法的性能呢？目前只有一些簡單交換結(jié)構(gòu)及特定算法建立了數(shù)學(xué)模型， MSM型Clos交換結(jié)構(gòu)及其調(diào)度算法在文獻(xiàn)中尚未見到有數(shù)學(xué)模型，雖然沒有數(shù)學(xué)模型，但可以通過計算機(jī)仿真來研究其性能。OPNET是一款網(wǎng)絡(luò)仿真軟件^［8］，它具有包通信機(jī)制、有限狀態(tài)機(jī)、離散事件推進(jìn)機(jī)制、三層建模等特點，適合交換結(jié)構(gòu)及調(diào)度算法仿真。本文以O(shè)PNET為平臺建立了交換結(jié)構(gòu)及調(diào)度算法仿真模型。

2 MSM 型Clos交換網(wǎng)絡(luò)

MSM型三級Clos交換網(wǎng)絡(luò)結(jié)構(gòu)模型如圖1所示，輸入級單元為共享緩存方式，中間級單元采用Crossbar結(jié)構(gòu)，輸出級單元采用輸出緩存方式。

圖1 64×64 MSM型Clos交換結(jié)構(gòu)(m=n=k=8)

圖1中標(biāo)記如下：IM(i)為第i+1個輸入級交換單元；CM(r)為第r+1個中間級交換單元；OM(j)為第j+1個輸出級交換單元；IP(i，g)為IM(i)的第g+1個輸入端口；OP(j，h)為OM(j)的第h+1個輸出端口；LI(i，r)為IM(i)和CM(r)之間的連接；LC(r，j)為CM(r)和OM(j)之間的連接；VOQ(i，j，h)為IM(i)中存儲到OP(j，h)的信元的隊列；VOQG(i，j)為存儲從IM(i)到OM(j)信元的k個VOQ。與LI(i，r)對應(yīng)指針為PI(i，r)(0≤i≤k-1，0≤r≤m-1)，與LC(r，j)對應(yīng)指針為PC(r，j)(0≤r≤m-1，0≤j≤k-1)和與VOQ(i，v)(v=hk+j，0≤h≤n-1，0≤j≤k-1，0≤v≤nk-1)對應(yīng)的指針為PV(i，v)。

3 MSM 型Clos交換網(wǎng)絡(luò)中的典型算法

交換結(jié)構(gòu)只是信元交換的硬件載體，為實現(xiàn)信元交換還必須有調(diào)度算法。MSM型三級Clos交換結(jié)構(gòu)的典型算法有CRRD，CMSD和SRRD三種。

CRRD算法使用以下兩次匹配。

模塊內(nèi)匹配：

Step1:請求，未匹配的非空VOQ向所有輸出端口發(fā)送請求；

Step2:授權(quán)，如果未匹配輸出端口收到多個請求，則輸出端口仲裁器從指針PI(i，r)所指位置開始以輪詢方式選擇一個VOQ請求；

Step3:允許，如果VOQ收到多個輸出端口的授權(quán)，則VOQ仲裁器從指針PV(i，v)所指位置開始以輪詢方式選擇一個授權(quán)。

級間匹配：

Step1:請求，IM(i)內(nèi)匹配完成后，如果IM(i)的第r個輸出端口匹配則LI(i，r)向CM(r)的輸出端口發(fā)送請求；

Step2:授權(quán)，CM(r)的輸出端口接收到多個請求，則CM(r)輸出端口仲裁器以輪詢方式選擇一個請求。

CMSD算法和CRRD算法僅在IM(i)內(nèi)匹配不同，級間匹配完全相同，CMSD算法在IM(i)輸出端口設(shè)置兩組仲裁器，分別稱為主仲裁器和從仲裁器，分別記作ML(i，r)(0≤r≤m)和SL(i，j，r)(0≤j≤k，0≤r≤m)。主從仲裁器對應(yīng)的指針分別記作PML(i，r)和PSL(i，j，r)，VOQ(i，j，h)對應(yīng)的指針記作PV(i，j，h)。

模塊內(nèi)匹配：

Step1:請求，非空VOQ(i，j，h)向VOQG(i，j)內(nèi)所有SL(i，j，r)發(fā)送請求；至少有一個非空VOQ的VOQG(i，j)向所有未匹配的ML(i，r)發(fā)送請求，稱為組請求；

Step2:授權(quán)，ML(i，r)從指針PML(i，r)所指位置開始以輪詢方式選擇一個組請求并發(fā)送授權(quán)給SL(i，j，r)；同時，SL(i，j，r)從指針PSL(i，j，r)所指位置開始選擇一個VOQ，如果SL(i，j，r)收到授權(quán)信息則發(fā)送授權(quán)給所選擇VOQ，否則不發(fā)送授權(quán)；

Step3:接受，VOQ(i，j，h)如果收到授權(quán)則從指針PV(i，j，h)所指位置開始以輪詢方式選擇一個授權(quán)，并發(fā)送接受信息給授權(quán)主從仲裁器。

Static Round-Robin Dispatching(SRRD)算法在初始化時將各個指針初始化為不同的值，每個時隙完成后，無論匹配與否都更新指針，這樣使得各各個指針一直處于“異步化”狀態(tài)。SRRD算法與CMSD算法僅在指針初始化和更新方式不同。

4 OPNET仿真模型

OPNET是一款專業(yè)網(wǎng)絡(luò)仿真軟件，本文中使用OPNET Modeler模塊。OPNET是離散事件驅(qū)動的仿真軟件，它提供了網(wǎng)絡(luò)層、節(jié)點層以及進(jìn)程層的三層建模機(jī)制，使建模層層深入，條理清晰。OPNET最大的特點是基于包的通信機(jī)理，大部分的通信是靠包以及包所承載的信息來完成，該軟件適合交換結(jié)構(gòu)仿真。

在建立仿真模型前首先給出幾點假設(shè)：

(1) 輸入端口的到達(dá)過程是獨立同分布過程；

(2) 各個輸入端口到達(dá)速率相同；

(3) 到達(dá)各個輸入端口的信元定長；

(4) 信元從進(jìn)入輸入端口到從輸出端口輸出的時間為一個信元時隙；

(5) 每個時隙每個輸入端口最多只有一個信元到達(dá)，每個輸出端口最多只有一個信元輸出。

在建立模型時，交換結(jié)構(gòu)及仿真所采用的信源可以抽象為如圖2所示的星形網(wǎng)絡(luò)，中心節(jié)點對應(yīng)交換結(jié)構(gòu)，周邊節(jié)點對應(yīng)信源，二者之間的連線代表輸入輸出端口。

圖2 交換模型

4.1 節(jié)點層模型

仿真模型中有兩類節(jié)點，一類為交換結(jié)構(gòu)節(jié)點，另一類為源節(jié)點。信源節(jié)點產(chǎn)生仿真中所需的業(yè)務(wù)，交換結(jié)點是信元交換的硬件載體。

仿真中一般采用兩種業(yè)務(wù)模型^［9］，一種為均勻業(yè)務(wù)模型，另一種為突發(fā)業(yè)務(wù)模型。建立均勻業(yè)務(wù)模型時，各個輸入端口獨立且產(chǎn)生信元速率相同，故其到達(dá)過程是獨立同分布過程。信元產(chǎn)生之后，再產(chǎn)生均勻分布在(0，N)之間的正整數(shù)作為信元目的地址。

突發(fā)過程模型使用兩狀態(tài)(ON狀態(tài)和OFF狀態(tài))的離散馬爾科夫鏈來構(gòu)建，當(dāng)模型處于ON狀態(tài)時發(fā)送信元，OFF狀態(tài)時不發(fā)送信元。ON/OFF長度由以下公式產(chǎn)生。

LengthON=0L=0

ln(u)ln(1-p1)0

LengthOFF=∞ L=0

ln(u)ln(1-p2)0

0L=1

其中，p(Sn+1=OFF|Sn=ON)=p1，p(Sn+1=ON|Sn=OFF)=p2為狀態(tài)轉(zhuǎn)移概率，L為負(fù)載。

由于MSM型Clos結(jié)構(gòu)的輸入級采用共享緩存方式，輸出級采用輸出緩存方式，故在建模時輸入級和輸出級都采用了隊列模塊，而中間級是一個Crossbar結(jié)構(gòu)，故在中間級采用了進(jìn)程模塊。圖3給出了兩類節(jié)點模型。

信源OPNET模型如圖3(a)所示。信源節(jié)點包含4個模塊，即源模塊(src)、處理模塊(proc)、接收機(jī)(rcv)和發(fā)送機(jī)(xmt)。各個模塊作用如下：

源模塊(src)：按固定時隙產(chǎn)生信元，作為處理模塊的觸發(fā)源；處理模塊(proc)：當(dāng)處理模塊接收到源模塊的信元以后，產(chǎn)生不同類型的業(yè)務(wù)，此模塊另一個作用就是處理從接收機(jī)來的信元；發(fā)送機(jī)(xmt)：將處理模塊產(chǎn)生的信元發(fā)送到交換節(jié)點；接收機(jī)(rcv)：接收從交換節(jié)點來的信元。

由于篇幅有限這里只給出16×16的交換節(jié)點，如圖3(b)所示，64×64的交換結(jié)構(gòu)可用相同方法建立，圖中有九類模塊，以下分別介紹各類模塊的作用。

調(diào)度模塊(scheduler)：調(diào)度算法根據(jù)隊列狀態(tài)信息完成信元調(diào)度，并將調(diào)度結(jié)果發(fā)送給各個隊列；時間源模塊(timer)：按照固定時隙產(chǎn)生觸發(fā)信元；同步模塊(synchronization)：在每個時隙開始時刻，發(fā)送同步信號給各個隊列，以便各個隊列同時將隊列狀態(tài)信息發(fā)送給調(diào)度模塊；輸入模塊：Clos結(jié)構(gòu)中的輸入級交換單元；中間模塊：Clos結(jié)構(gòu)中的中間級交換單元；輸出模塊：Clos結(jié)構(gòu)中的輸出級交換單元；統(tǒng)計模塊(statistic)：收集參數(shù)數(shù)據(jù)。

圖3 節(jié)點層模型

4.2 關(guān)鍵進(jìn)程模型

圖4是關(guān)鍵進(jìn)程模型。節(jié)點內(nèi)部除發(fā)送模塊和接收模塊之外，每個模塊內(nèi)都采用一個進(jìn)程來實現(xiàn)不同功能。在信源節(jié)點模型中處理模塊按照仿真需求產(chǎn)生各類業(yè)務(wù)，可以通過改變該模塊內(nèi)的進(jìn)程來實現(xiàn)業(yè)務(wù)的更換，因此該模塊是該節(jié)點內(nèi)的關(guān)鍵模塊。在交換節(jié)點內(nèi)部各個模塊中調(diào)度模塊用來實現(xiàn)調(diào)度，Clos結(jié)構(gòu)的各個輸入模塊將隊列狀態(tài)信息發(fā)送給該模塊，其根據(jù)不同的調(diào)度算法來仲裁各個隊列的優(yōu)先級，因此該模塊是交換節(jié)點的關(guān)鍵模塊。目前針對MSM型Clos結(jié)構(gòu)的典型算法有CRRD，CMSD和SRRD三種，在設(shè)計調(diào)度進(jìn)程模型時考慮進(jìn)程模型的通用性，使得進(jìn)程模型適合3種典型算法。圖4(a)是源節(jié)點處理模塊進(jìn)程，該進(jìn)程包含兩個狀態(tài)，初始狀態(tài)(init)和空閑狀態(tài)(idle)，各個狀態(tài)說明如下：init狀態(tài)為初始化狀態(tài)，在進(jìn)程啟動時為系統(tǒng)配置相關(guān)參數(shù)；idle狀態(tài)為空閑狀態(tài)，如果沒有中斷發(fā)生則進(jìn)程停留在該狀態(tài)，如果有源信元到則通過函數(shù)xmt()為其配置好業(yè)務(wù)類型并將其發(fā)送出去；如果接收到交換出的信元則將其銷毀，以節(jié)省存儲空間。

圖4(b)是調(diào)度進(jìn)程模型，該進(jìn)程模型包含四個狀態(tài)，分別介紹如下：wait狀態(tài)為等待狀態(tài)，進(jìn)程初始化之后就轉(zhuǎn)移到該狀態(tài)等待隊列信息到達(dá)，如果隊列狀態(tài)信息到達(dá)，則轉(zhuǎn)入matchfirst狀態(tài)；matchfirst狀態(tài)為模塊內(nèi)匹配狀態(tài)，如果有隊列狀態(tài)信息到達(dá)則進(jìn)行第一次匹配，之后則停留在該狀態(tài)繼續(xù)等待其他輸入級模塊隊列狀態(tài)信息到達(dá)，直到所有輸入級交換單元都匹配完成之后轉(zhuǎn)入matchsecond狀態(tài)。matchsecond狀態(tài)為級間匹配狀態(tài)，第一次匹配結(jié)束之后進(jìn)程轉(zhuǎn)移到該狀態(tài)進(jìn)行級間匹配，之后將匹配結(jié)果發(fā)送給相應(yīng)輸入交換單元，然后轉(zhuǎn)移到Wait狀態(tài)，等待下個時隙匹配。

圖4 關(guān)鍵進(jìn)程模型

5 算法仿真

本文在建立OPNET模型后，仿真了64×64的MSM型Clos交換結(jié)構(gòu)(m=n=k=8)的3種典型算法。信源到達(dá)過程為獨立同分布貝努利過程和突發(fā)過程。仿真時間為200 000個時隙。由于在實際應(yīng)用中突發(fā)業(yè)務(wù)比較多，故仿真了3種典型算法在突發(fā)業(yè)務(wù)下的信元丟失率，如圖5所示，從該圖可以看出，3種算法中SRRD算法的信元丟失率性能最好。分別在獨立同分布貝努利業(yè)務(wù)和突發(fā)業(yè)務(wù)下仿真了3種算法的時延特性，如圖6所示。從圖6可以看出在貝努利業(yè)務(wù)下3種算法中SRRD算法時延性能最好，同時，也說明突發(fā)業(yè)務(wù)對時延性能的影響。這是因為在SRRD算法中去掉了指針同步現(xiàn)象，每個時隙匹配數(shù)目增加所致。

圖5 突發(fā)業(yè)務(wù)下信元丟失率

圖6 兩種業(yè)務(wù)下的時延曲線圖

6 結(jié) 語

本文分析了MSM型三級Clos交換結(jié)構(gòu)模型及幾種經(jīng)典調(diào)度算法，在此基礎(chǔ)上使用OPNET建立三級Clos交換結(jié)構(gòu)及其調(diào)度算法模型的方法和步驟，并給出了該交換結(jié)構(gòu)模型及各個節(jié)點關(guān)鍵進(jìn)程模型。該模型將交換系統(tǒng)抽象為一個星型網(wǎng)絡(luò)，使其具有通用性。為了驗證模型的正確性，仿真了3種典型調(diào)度算法在貝努利業(yè)務(wù)和突發(fā)業(yè)務(wù)下的時延性能，同時也仿真了突發(fā)業(yè)務(wù)下3種典型調(diào)度算法的信元丟失率性能。通過對經(jīng)典算法的仿真可知該模型正確地描述了MSM型Clos交換結(jié)構(gòu)及其調(diào)度算法。該模型的建立為Clos交換結(jié)構(gòu)及其調(diào)度算法性能的研究提供了一個高效簡潔的途徑。

參考文獻(xiàn)

［1］Jonathan H Chao，Jing Zhigang，Soung Y Liew.Matching Algorithms for Three-stage Bufferless Clos Network Switches［J］.IEEE Communications Magazine，2003，41:46-54.

［2］Chiussi F M，Kneuer J G，Kumar V P.Low-cost Scalable Switching Solutions for Broadband Networking:The ATLANTA Architecture and Chipset［J］.IEEE Communication Magazine，1997，35(3):44-53.

［3］Oki E，Jing Z，Rojas-Cessa R，et al.Concurrent Round-robin Dispatching Scheme in a Clos-network Switch［J］.IEEE ICC2001，2001，1:830-844.

［4］Moo-Kyung Kang，ChongMin Kyung.Three-stage Clos-Network Switch Architecture with Buffered Center Stage For Multi-Class Traffic［J］.Journal of Circuits，Systems，and Computers，2005.

［5］楊帆，邱智亮，劉增基，等.一種新的輸入緩存Clos結(jié)構(gòu)及其路由/調(diào)度算法［J］.西安電子科技大學(xué)學(xué)報:自然科學(xué)版，2007，34(1):63-67.

［6］Li Xin，Zhou Zhen，Hamdi M.Space-memory Architecture for Clos Network Packet Switches［C］.2005 IEEE International Conference，2005:1 031-1 035.

［7］Pun K，Hamdi M.Static Round-robin Dispatching Schemes for Clos-network Switches.IEEE HPSR2002，Hong Kong University，2002.

［8］陳敏.OPNET網(wǎng)絡(luò)仿真［M］.北京:清華大學(xué)出版社，2004.

［9］張怡，周詮.分組交換機(jī)的極大匹配調(diào)度算法的仿真與比較［J］.現(xiàn)代電子技術(shù)，2007，30(2):145-148.

作者簡介

呼延烺 男，1981年出生，陜西人，碩士研究生。主要研究方向為衛(wèi)星數(shù)據(jù)傳輸與處理。

周 詮 男，1965年出生，陜西人，博士，研究員，通信與信息系統(tǒng)、飛行器設(shè)計專業(yè)碩士生導(dǎo)師、博士生導(dǎo)師，空間微波技術(shù)國家級重點實驗室副主任。主要研究方向為衛(wèi)星數(shù)據(jù)傳輸與處理、航天器通信技術(shù)。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文