0 引言

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

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

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

1 CICQ交換結構和基本數據包切分模型

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

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

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

2 自適應數據包切分

2.1 變長多包切分模型

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

2.2 自適應數據包切分機制

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

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

    (1)自適應切片長度S_i生成。計算N個VOQ隊列中所有數據包包長的平均值為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)輸入調度。按照一定的調度規則從所有輸入VOQ中選擇一個有效VOQ_ik(S_ik+LC_ik<C)進行服務。

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

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

2.3 自適應數據包切分機制的實現

    自適應數據包切分機制的實現如圖4所示，主要包括切片長度產生模塊、輸入調度器、信用值管理模塊和切片傳輸控制模塊。

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

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

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

3 性能評估

3.1 仿真環境和流量模型

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

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

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

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

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

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

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

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

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

4 結論

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

參考文獻

[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，France：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，France：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交換結構調度算法[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.