0 引言

    Crossbar交換結(jié)構(gòu)由于具有簡單及內(nèi)部無阻塞的特性，成為現(xiàn)代交換機(jī)系統(tǒng)的核心組成部分^[1]。傳統(tǒng)的crossbar內(nèi)部無緩存，只在輸入端或輸出端設(shè)置緩存隊列，各輸入輸出端口的數(shù)據(jù)傳輸應(yīng)相互同步。因此，在處理變長包時需要使用切分-重組（SAR）機(jī)制，在輸入端將數(shù)據(jù)包切割成定長信元進(jìn)行交換，再在輸出端將信元重組為原始的數(shù)據(jù)包。目前，一種內(nèi)部帶緩存的crossbar交換結(jié)構(gòu)—CICQ（Combined Input Crosspoint Queued）通過在crossbar內(nèi)交叉點(diǎn)設(shè)置少量緩存來提高調(diào)度效率，已成為更具優(yōu)勢的交換結(jié)構(gòu)^[2]。CICQ的一個特點(diǎn)是能夠直接交換變長數(shù)據(jù)包^[3]，不需要SAR機(jī)制。然而，直接變長交換存在兩方面限制：與定長交換相比，硬件實(shí)現(xiàn)相對復(fù)雜；交叉點(diǎn)緩存至少需要一個最大包長的空間來存放數(shù)據(jù)，限制交換機(jī)端口數(shù)的擴(kuò)展。因此，對于CICQ中變長數(shù)據(jù)包的處理，仍然需要采用高效的數(shù)據(jù)包切分方法將其切分以便于交換。 

    目前已有的數(shù)據(jù)包切分方法包括：定長單包切分、定長多包切分^[4]、變長單包切分^[5]和變長多包切分(Variable-size Multipacket Segments，VMS)^[6]。定長單包切分，對單個數(shù)據(jù)包進(jìn)行處理，切分為定長信元。然而最后一個切片通常包含無用的填充字節(jié)，需要crossbar內(nèi)部加速來補(bǔ)償填充字節(jié)引起的帶寬利用率損失。由于信元較小，需要較高的調(diào)度速率，對調(diào)度算法的要求也較高。定長多包切分屬于同一數(shù)據(jù)流的數(shù)據(jù)包合并起來進(jìn)行切分。切片長度增加，能夠緩解調(diào)度速率，同時填充字節(jié)減少可以提高帶寬利用率。缺點(diǎn)是隊尾的部分?jǐn)?shù)據(jù)需要保持在隊列中直到能夠填滿一個切片，增加數(shù)據(jù)包的延遲。變長單包切分對單個數(shù)據(jù)包進(jìn)行切分，最后一個切片不需要填充開銷。但是，由于在單個數(shù)據(jù)包內(nèi)進(jìn)行切片，調(diào)度速率不會減小。變長多包切分對相鄰的數(shù)據(jù)包合并起來進(jìn)行切分，切片大小的增加緩解調(diào)度速率，而且不需要額外的填充字節(jié)，性能優(yōu)于其他三種切分方法。然而，在對延遲性能要求較高的實(shí)時業(yè)務(wù)流量中，實(shí)時的小數(shù)據(jù)包會因?yàn)檩^大切片的阻擋而導(dǎo)致延遲增加，從而影響其交換效率及公平性。

    針對傳統(tǒng)切分方法的不足，本文在變長多包切分[7]的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種新的基于CICQ交換機(jī)的高效自適應(yīng)數(shù)據(jù)包切分機(jī)制(Adaptive Multipacket Segments，AMS)。該機(jī)制根據(jù)輸入端的隊列狀態(tài)實(shí)時地調(diào)整切片長度，以適應(yīng)動態(tài)變化的網(wǎng)絡(luò)流量以及不同數(shù)據(jù)包長度。切片長度靈活可變，使得隊列中的大型數(shù)據(jù)包和實(shí)時小數(shù)據(jù)包都能得到有效服務(wù)，不會影響實(shí)時小數(shù)據(jù)包的交換效率。CICQ結(jié)構(gòu)采用新的數(shù)據(jù)包切分機(jī)制，在不同的網(wǎng)絡(luò)流量模型下都表現(xiàn)有良好的時延性能，且明顯優(yōu)于變長多包切分機(jī)制。

1 CICQ交換結(jié)構(gòu)和基本數(shù)據(jù)包切分模型

    圖1所示為帶SAR機(jī)制的N×N CICQ交換結(jié)構(gòu)，主要包括N個輸入端、N個輸出端、虛擬輸出隊列（VOQ）、帶緩存的crossbar、輸入切分機(jī)制以及輸出重組機(jī)制。數(shù)據(jù)包到達(dá)輸入端時，首先切分機(jī)制將變長數(shù)據(jù)包切割為定長信元，存入相應(yīng)的VOQ隊列中。然后，信元經(jīng)過帶緩存的crossbar進(jìn)行交換。最后，在輸出端通過重組機(jī)制將信元重組為原始的數(shù)據(jù)包并發(fā)送。為了分析切分機(jī)制，采用如圖2所示的定長單包切分模型。假設(shè)數(shù)據(jù)包到達(dá)過程為服從參數(shù)為λ的Poisson過程，令數(shù)據(jù)包的長度為X，以s為標(biāo)準(zhǔn)切片大小對數(shù)據(jù)包進(jìn)行切分，則每個數(shù)據(jù)包切分為ceil(X/s)個信元，其中ceil為標(biāo)準(zhǔn)的上取整函數(shù)。若包長X不能被s整除，則剩下的數(shù)據(jù)添加填充字節(jié)構(gòu)成標(biāo)準(zhǔn)信元。此外，每個信元還需要添加信元頭，以指示該信元在數(shù)據(jù)包中的位置。令數(shù)據(jù)包切分成長度為s的信元個數(shù)為隨機(jī)變量Y，則Y與X的關(guān)系為：

    切分過程中每個信元添加的無用填充字節(jié)會消耗系統(tǒng)帶寬，為了保證CICQ結(jié)構(gòu)能夠以線速率交換經(jīng)切分后的信元，crossbar內(nèi)部需要一定的加速比f：

    分析上式得出，平均包長E(X)一定，切片長度s為影響CICQ交換性能的主要因素。隨著切片長度s的增加，CICQ所需的內(nèi)部加速比f增大。這是因?yàn)樘畛渥止?jié)在所有傳輸數(shù)據(jù)中所占的比例增加，交換填充字節(jié)引起的帶寬利用率損失更嚴(yán)重，需要更大的加速比以線速轉(zhuǎn)發(fā)數(shù)據(jù)。

2 自適應(yīng)數(shù)據(jù)包切分

2.1 變長多包切分模型

    圖3所示為變長多包切分模型，不同陰影部分代表輸入VOQ隊列中不同的數(shù)據(jù)包。相鄰數(shù)據(jù)包合在一起進(jìn)行切分，以s為標(biāo)準(zhǔn)切片大小。每個切片中可能包括一個或多個數(shù)據(jù)包，隊列中最后剩余的數(shù)據(jù)若不能被s整除，則直接構(gòu)成變長切片s′，無需用填充字節(jié)填滿。對于這種方法，采用不同的切片長度s，系統(tǒng)的交換性能有顯著差異。隨著s的增大，信元頭的整體開銷減少，使得帶寬利用率和時延性能都進(jìn)一步提高。然而，若切片長度s太大，在實(shí)時性要求較高的網(wǎng)絡(luò)業(yè)務(wù)流量中，小數(shù)據(jù)包會因大切片的阻擋而導(dǎo)致包延遲增加，其交換效率及公平性會大大降低。同時，切片過大會降低硬件電路的利用率。

2.2 自適應(yīng)數(shù)據(jù)包切分機(jī)制

    在實(shí)際的網(wǎng)絡(luò)流量中，進(jìn)入交換機(jī)的數(shù)據(jù)包長度具有隨機(jī)性，VMS機(jī)制采用固定切片長度靈活性較差，無法適應(yīng)動態(tài)變化的流量。針對VMS機(jī)制靈活性差和交換效率低的問題，本節(jié)提出一種高效的自適應(yīng)數(shù)據(jù)包切分機(jī)制（AMS）。其基本思想是根據(jù)輸入VOQ隊列的狀態(tài)信息動態(tài)地調(diào)整切片長度，使其適應(yīng)實(shí)時變化的流量和數(shù)據(jù)包長度，同時保證良好的交換性能。具體切分時將VOQ隊列中相鄰的數(shù)據(jù)包合并起來進(jìn)行切片。完整的自適應(yīng)數(shù)據(jù)包切分機(jī)制描述如下：

    對于一個N×N CICQ交換機(jī)，輸入端有數(shù)據(jù)包到達(dá)時直接存放到對應(yīng)VOQ隊列中。假設(shè)LV_ij為輸入VOQ_ij的隊列長度，LC_ij為crossbar交叉點(diǎn)緩存CB_ij的隊列長度，C表示交叉點(diǎn)緩存的最大容量，其中1≤i≤N，1≤j≤N。有效VOQ_ij：VOQ_ij滿足一定的條件，即對應(yīng)交叉點(diǎn)緩存CB_ij包括能夠容納一個切片大小的空間。每個輸入端i，在每個調(diào)度周期按以下步驟執(zhí)行：

    (1)自適應(yīng)切片長度S_i生成。計算N個VOQ隊列中所有數(shù)據(jù)包包長的平均值為S_i=(LV_i1+LV_i2+…+LV_iN)/N。

    (2)確定VOQ_ij的實(shí)際切片長度S_ij。若VOQ_ij的隊列長度LV_ij大于S_i，則實(shí)際切片長度S_ij=S_i；否則，S_ij=LV_ij。

    (3)輸入調(diào)度。按照一定的調(diào)度規(guī)則從所有輸入VOQ中選擇一個有效VOQ_ik(S_ik+LC_ik<C)進(jìn)行服務(wù)。

    (4)數(shù)據(jù)包切分。對輸入調(diào)度選中的VOQ_ik隊列，按照步驟(2)確定的對應(yīng)實(shí)際切片長度S_ik，相鄰的數(shù)據(jù)包合并起來進(jìn)行切分，并將切片發(fā)送到crossbar交叉點(diǎn)緩存。

    自適應(yīng)數(shù)據(jù)包切分機(jī)制的特點(diǎn)如下：實(shí)時跟蹤當(dāng)前調(diào)度周期內(nèi)輸入VOQ的狀態(tài)，確定合適的切片長度。如果各VOQ隊列長度之和較大，說明VOQ隊列整體占用率較高，則選擇較大的切片長度進(jìn)行數(shù)據(jù)包切分，保證盡快服務(wù)滯留的數(shù)據(jù)包，以提高排隊系統(tǒng)的性能和穩(wěn)定性；相反，隊列長度之和較小時，表示隊列擁塞情況較輕，采用對應(yīng)的小切片長度，以保證小數(shù)據(jù)包不被長期阻擋，能夠得到有效服務(wù)，從而提高交換效率和公平性。

2.3 自適應(yīng)數(shù)據(jù)包切分機(jī)制的實(shí)現(xiàn)

    自適應(yīng)數(shù)據(jù)包切分機(jī)制的實(shí)現(xiàn)如圖4所示，主要包括切片長度產(chǎn)生模塊、輸入調(diào)度器、信用值管理模塊和切片傳輸控制模塊。

    切片長度產(chǎn)生模塊根據(jù)每個VOQ_ij對應(yīng)的計數(shù)器記錄的隊列長度信息，計算產(chǎn)生輸入端i的自適應(yīng)切片長度S_i，并按照步驟(2)確定每個VOQ_ij可能的實(shí)際切片長度S_ij。

    輸入調(diào)度器根據(jù)切片長度產(chǎn)生模塊提供的切片長度信息S_ij，以及信用值管理模塊的當(dāng)前crossbar交叉點(diǎn)隊列信息LC_ij，判斷每個VOQ_ij是否為有效隊列；按照一定的調(diào)度規(guī)則仲裁選擇出一個隊列VOQik進(jìn)行服務(wù)。調(diào)度完成后將調(diào)度決策送到切片傳輸控制模塊。

    信用值管理模塊接收crossbar返回的交叉點(diǎn)信用值信息，并根據(jù)下一個將被服務(wù)隊列VOQ_ik的切片長度信息，實(shí)時更新crossbar各交叉點(diǎn)的信用值，即交叉點(diǎn)緩存的占用情況，以防止交叉點(diǎn)隊列溢出而導(dǎo)致數(shù)據(jù)丟失。切片傳輸控制模塊，根據(jù)輸入調(diào)度器的調(diào)度決策，控制對應(yīng)VOQ_ik中的切片數(shù)據(jù)發(fā)送到crossbar交叉點(diǎn)緩存中。

3 性能評估

3.1 仿真環(huán)境和流量模型

    本節(jié)對提出的自適應(yīng)數(shù)據(jù)包切分機(jī)制（AMS）和已有變長多包切分（VMS）進(jìn)行時延性能的仿真分析比較。變長多包切分機(jī)制主要考慮5種情況，切片長度分別為64 B、128 B、256 B、512 B和1 024 B。時延是指數(shù)據(jù)包從進(jìn)入交換機(jī)的輸入隊列到發(fā)送至輸出端的時間間隔，以微秒(μs)為單位。性能評估基于16×16的CICQ交換機(jī)，運(yùn)行具有低復(fù)雜度、高性能的RR-LQD調(diào)度算法^[7]，端口線速率設(shè)為1 Gb/s，crossbar交叉點(diǎn)緩存的最大容量為一個切片信元，仿真時間為1 s。仿真實(shí)驗(yàn)中采用Poisson和馬爾科夫調(diào)制的Poisson過程(MMPP)^[8]兩種典型的流量模型。

    Poisson流量到達(dá)過程中，數(shù)據(jù)包的包間隔時間t服從指數(shù)分布。MMPP模型^[8]能很好地模擬真實(shí)網(wǎng)絡(luò)流量的突發(fā)特性。MMPP過程為ON和OFF兩種狀態(tài)交替進(jìn)行，p為ON狀態(tài)轉(zhuǎn)換到OFF狀態(tài)的概率，q為OFF跳轉(zhuǎn)到ON的概率。ON狀態(tài)是包到達(dá)率為λ_ON的Poisson過程，OFF狀態(tài)時無數(shù)據(jù)包到達(dá)。

    數(shù)據(jù)包長度為[40，1 500]B范圍內(nèi)的IMIX^[9]分布模型。IMIX混合模型是一種常用的模擬真實(shí)Internet流量的測試模型，包括3種包長：40 B占58.33%，576 B占33.33%，1 500 B占8.33%，數(shù)據(jù)包平均長度為340.26 B。數(shù)據(jù)包目的端口服從均勻分布，即到達(dá)所有輸出端口的概率相同。

3.2 不同負(fù)載下時延性能分析

    圖5所示為Poisson-IMIX流量模型下，基于不同切分方法的CICQ交換機(jī)的平均時延性能。仿真結(jié)果說明，對于變長多包切分機(jī)制，切片長度越小，平均時延性能越差。VMS-64B，即切片長度為64 B，在負(fù)載高于90%時就出現(xiàn)不穩(wěn)定現(xiàn)象，這是由于高負(fù)載下隨著隊列中數(shù)據(jù)包的積聚，需要交換的內(nèi)部信元頭開銷增加，導(dǎo)致帶寬利用率大大降低。VMS-512B和VMS-1024B，當(dāng)負(fù)載大于95%時平均延遲開始迅速增長。而AMS性能最優(yōu)，在高負(fù)載情況下都能夠保持良好的時延性能和穩(wěn)定性。

    在MMPP-IMIX的突發(fā)流量模型下，平均時延性能如圖6所示。由于突發(fā)特性的影響，各種切分方法的平均延遲都隨著輸入負(fù)載的增加而逐漸增大。VMS-64B表現(xiàn)最差，自適應(yīng)數(shù)據(jù)包切分機(jī)制與其他變長多包切分性能接近，在不同負(fù)載下平均延遲都低于VMS-64B。

    圖7表示在Poisson-IMIX流量模型下所有40 B大小的數(shù)據(jù)包的平均延遲，可以看出對于這種情況，AMS機(jī)制明顯優(yōu)于VMS機(jī)制，即使在99%的負(fù)載下都能夠保持穩(wěn)定，表現(xiàn)出理想的時延性能。而幾種VMS機(jī)制在高負(fù)載下出現(xiàn)不同程度的不穩(wěn)定現(xiàn)象。在負(fù)載大于90%時，VMS-64B機(jī)制下40 B包的平均延遲隨輸入負(fù)載增加而急劇惡化。變長多包切分中相對較好的VMS-1024B，平均延遲從負(fù)載95%就開始快速增長。

    圖8為MMPP-IMIX流量模型下40 B數(shù)據(jù)包的平均延遲結(jié)果。與圖6顯示的總體時延性能表現(xiàn)相似，由于MMPP過程的突發(fā)性，40 B包的平均延遲都隨著輸入負(fù)載的增加而增長。AMS表現(xiàn)最好，在不同負(fù)載下40 B包的平均延遲都低于其他變長多包切分機(jī)制。VMS-64B表現(xiàn)最差。

    實(shí)驗(yàn)結(jié)果說明，提出的AMS機(jī)制能夠有效發(fā)揮作用，在兩種模擬真實(shí)Internet流量的模型下都表現(xiàn)出良好的延遲性能。而且，根據(jù)輸入端隊列的狀態(tài)實(shí)時調(diào)整切片長度，靈活適應(yīng)動態(tài)變化的網(wǎng)絡(luò)流量以及不同的數(shù)據(jù)包長度。通過分析40 B數(shù)據(jù)包的時延結(jié)果得到，與VMS相比，AMS機(jī)制能有效降低小數(shù)據(jù)包的延遲。原因在于切片長度隨輸入隊列信息靈活改變的策略，保證隊列中大型數(shù)據(jù)包和實(shí)時小數(shù)據(jù)包都能得到有效服務(wù)。在對時延要求較高的實(shí)時業(yè)務(wù)中，不會出現(xiàn)較大切片將小數(shù)據(jù)包長期阻擋而導(dǎo)致阻塞延遲，從而有效確保交換效率和公平性。因此，AMS比VMS更有優(yōu)勢。

4 結(jié)論

    本文首先介紹了CICQ交換結(jié)構(gòu)和基本的數(shù)據(jù)包切分模型，然后針對傳統(tǒng)變長多包切分機(jī)制交換效率低、靈活性較差的問題，提出了一種新的CICQ交換機(jī)自適應(yīng)數(shù)據(jù)包切分機(jī)制（AMS）。該機(jī)制基于實(shí)時可變的切片長度，采用相鄰數(shù)據(jù)包結(jié)合的方式進(jìn)行數(shù)據(jù)包切分，自適應(yīng)動態(tài)變化的網(wǎng)絡(luò)流量和數(shù)據(jù)包長度。通過仿真實(shí)驗(yàn)比較了采用AMS機(jī)制和傳統(tǒng)VMS機(jī)制的CICQ結(jié)構(gòu)的交換性能，結(jié)果表明提出的自適應(yīng)數(shù)據(jù)包切分機(jī)制在不同流量下具有比VMS機(jī)制更優(yōu)的時延性能，且能夠更好地滿足實(shí)時性業(yè)務(wù)流量的要求，是一種更高效的數(shù)據(jù)包切分方法，適用于高性能CICQ交換機(jī)的設(shè)計實(shí)現(xiàn)。

參考文獻(xiàn)

[1] CHAO H J，LIU B.High performance switches and routers[M].Hoboken，New Jersey：Wiley-IEEE Press，2007.

[2] YOSHIGOE K，CHRISTENSEN K J.An evolution to crossbar switches with virtual output queuing and buffered cross points[J].IEEE Network，2003，17(5)：48-56.

[3] KATEVENIS M，PASSAS G，SIMOS D，et al.Variable packet size buffered crossbar(CICQ) switches[C].Proc of IEEE International Conference on Communications.Paris，F(xiàn)rance：IEEE，2004：1090-1096.

[4] CHRISTENSEN K，YOSHIGOE K，ROGINSKY A.Performance evaluation of packet-to-Cell segmentation schemes in input buffered packet switches[C].Proc of IEEE International Conference on Communications.Paris，F(xiàn)rance：IEEE，2004：1097-1102.

[5] STEPHENS D，ZHANG H.Implementing distributed packet fair queueing in a scalable switch qrchitecture[C].Proc of IEEE INFOCOM’98 Conference.San Francisco，CA：IEEE，1998：282-290.

[6] KATEVENIS M，PASSAS G.Variable-size multipacket segments in buffered crossbar(CICQ) architectures[C].Proc of IEEE International Conference on Communications，2005：999-1004.

[7] 彭來獻(xiàn)，惲姿，趙文棟，等.一種基于最長隊列預(yù)測的CICQ交換結(jié)構(gòu)調(diào)度算法[J].電子與信息學(xué)報，2010，32（6）：1457-1462.

[8] PAN D，YANG Y.Localized independent packet scheduling for buffered crossbar switches[J].IEEE Transactions on Computers，2009，58(2)：260-274.

[9] Agilent Technologies，JTC 003：Mixed packet size throughput[EB/OL].The Journal of Internet Test Methodologies.Agilent Technologies，2007.