0 引言

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

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

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

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

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

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

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

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

2.1 變長多包切分模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 性能評估

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

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

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

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

3.2 不同負載下時延性能分析

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

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

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

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

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

4 結論

    本文首先介紹了CICQ交換結構和基本的數(shù)據(jù)包切分模型，然后針對傳統(tǒng)變長多包切分機制交換效率低、靈活性較差的問題，提出了一種新的CICQ交換機自適應數(shù)據(jù)包切分機制（AMS）。該機制基于實時可變的切片長度，采用相鄰數(shù)據(jù)包結合的方式進行數(shù)據(jù)包切分，自適應動態(tài)變化的網(wǎng)絡流量和數(shù)據(jù)包長度。通過仿真實驗比較了采用AMS機制和傳統(tǒng)VMS機制的CICQ結構的交換性能，結果表明提出的自適應數(shù)據(jù)包切分機制在不同流量下具有比VMS機制更優(yōu)的時延性能，且能夠更好地滿足實時性業(yè)務流量的要求，是一種更高效的數(shù)據(jù)包切分方法，適用于高性能CICQ交換機的設計實現(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] 彭來獻，惲姿，趙文棟，等.一種基于最長隊列預測的CICQ交換結構調(diào)度算法[J].電子與信息學報，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.