一種高效自適應的CICQ交換機數(shù)據(jù)包切分機制

王曉婷，王憶文，李　平

（電子科技大學 電子薄膜與集成器件國家重點實驗室，四川 成都 610054）

一種高效自適應的CICQ交換機數(shù)據(jù)包切分機制

王曉婷，王憶文，李平

（電子科技大學 電子薄膜與集成器件國家重點實驗室，四川 成都 610054）

為了有效處理 CICQ （Combined Input Crosspoint Queued）交換機中的變長數(shù)據(jù)包，通常采用切分-重組（Segmentation and Reassembly，SAR）機制將變長包切分為定長信元進行交換。針對目前已有切分方法在不同網(wǎng)絡流量下交換效率低、靈活性差的問題，設計了一種基于CICQ交換機的高效自適應數(shù)據(jù)包切分機制。新機制的主要思想是根據(jù)輸入端的隊列狀態(tài)實時改變切片大小，并采用相鄰數(shù)據(jù)包合并切分的方式進行切片，以自適應網(wǎng)絡環(huán)境中的不同流量和數(shù)據(jù)包長度。仿真結(jié)果表明，提出的數(shù)據(jù)包切分機制較傳統(tǒng)切分方法有顯著優(yōu)勢，與已有方法中表現(xiàn)最好的變長多包切分相比，在不同的流量下能獲得更優(yōu)的時延性能和系統(tǒng)穩(wěn)定性。

CICQ交換機；切分機制；自適應

0　引言

Crossbar交換結(jié)構(gòu)由于具有簡單及內(nèi)部無阻塞的特性，成為現(xiàn)代交換機系統(tǒng)的核心組成部分[1]。傳統(tǒng)的 crossbar內(nèi)部無緩存，只在輸入端或輸出端設置緩存隊列，各輸入輸出端口的數(shù)據(jù)傳輸應相互同步。因此，在處理變長包時需要使用切分-重組（SAR）機制，在輸入端將數(shù)據(jù)包切割成定長信元進行交換，再在輸出端將信元重組為原始的數(shù)據(jù)包。目前，一種內(nèi)部帶緩存的crossbar交換結(jié)構(gòu)—CICQ（Combined Input Crosspoint Queued）通過在 crossbar內(nèi)交叉點設置少量緩存來提高調(diào)度效率，已成為更具優(yōu)勢的交換結(jié)構(gò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結(jié)構(gòu)采用新的數(shù)據(jù)包切分機制，在不同的網(wǎng)絡流量模型下都表現(xiàn)有良好的時延性能，且明顯優(yōu)于變長多包切分機制。

圖1　帶切分-重組(SAR)機制的N×N CICQ交換結(jié)構(gòu)

圖2　基本數(shù)據(jù)包切分模型

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

圖1所示為帶SAR機制的N×N CICQ交換結(jié)構(gòu)，主要包括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é)構(gòu)成標準信元。此外，每個信元還需要添加信元頭，以指示該信元在數(shù)據(jù)包中的位置。令數(shù)據(jù)包切分成長度為s的信元個數(shù)為隨機變量Y，則Y與X的關系為：

假設數(shù)據(jù)包長度X為服從參數(shù)為μ的指數(shù)分布，其累積分布函數(shù)F(x)為：

由式(4)可知，變量 Z服從參數(shù) p為 e-μs，q為 1-e-μs的幾何分布，P(Z=k)=qkp。Z的均值為：

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

式中，E(X)為數(shù)據(jù)包長度X（服從指數(shù)分布）的均值為1/μ，h為每個信元頭的大小。

將式(6)代入式(7)，可得

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

圖3　變長多包切分模型

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

2.1變長多包切分模型

圖3所示為變長多包切分模型，不同陰影部分代表輸入VOQ隊列中不同的數(shù)據(jù)包。相鄰數(shù)據(jù)包合在一起進行切分，以s為標準切片大小。每個切片中可能包括一個或多個數(shù)據(jù)包，隊列中最后剩余的數(shù)據(jù)若不能被s整除，則直接構(gòu)成變長切片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隊列中。假設LVij為輸入 VOQij的隊列長度，LCij為 crossbar交叉點緩存 CBij的隊列長度，C表示交叉點緩存的最大容量，其中 1≤i≤N，1≤j≤N。有效 VOQij：VOQij滿足一定的條件，即對應交叉點緩存CBij包括能夠容納一個切片大小的空間。每個輸入端i，在每個調(diào)度周期按以下步驟執(zhí)行：

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

(2)確定 VOQij的實際切片長度 Sij。若 VOQij的隊列長度 LVij大于 Si，則實際切片長度 Sij=Si；否則，Sij=LVij。

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

(4)數(shù)據(jù)包切分。對輸入調(diào)度選中的 VOQik隊列，按照步驟(2)確定的對應實際切片長度 Sik，相鄰的數(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ù)每個 VOQij對應的計數(shù)器記錄的隊列長度信息，計算產(chǎn)生輸入端i的自適應切片長度 Si，并按照步驟(2)確定每個 VOQij可能的實際切片長度 Sij。

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

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

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

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)轉(zhuǎn)換到OFF狀態(tài)的概率，q為OFF跳轉(zhuǎn)到 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交換機的平均時延性能。仿真結(jié)果說明，對于變長多包切分機制，切片長度越小，平均時延性能越差。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)定性。

圖5　Poisson-IMIX流量下的平均時延

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

圖6　MMPP-IMIX流量下的平均時延

圖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ù)包的平均延遲結(jié)果。與圖6顯示的總體時延性能表現(xiàn)相似，由于MMPP過程的突發(fā)性，40 B包的平均延遲都隨著輸入負載的增加而增長。AMS表現(xiàn)最好，在不同負載下40 B包的平均延遲都低于其他變長多包切分機制。VMS-64B表現(xiàn)最差。

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

圖7　Poisson-IMIX流量下40 B數(shù)據(jù)包的平均時延

圖8　MMPP-IMIX流量下40 B數(shù)據(jù)包的平均時延

4　結(jié)論

本文首先介紹了CICQ交換結(jié)構(gòu)和基本的數(shù)據(jù)包切分模型，然后針對傳統(tǒng)變長多包切分機制交換效率低、靈活性較差的問題，提出了一種新的CICQ交換機自適應數(shù)據(jù)包切分機制（AMS）。該機制基于實時可變的切片長度，采用相鄰數(shù)據(jù)包結(jié)合的方式進行數(shù)據(jù)包切分，自適應動態(tài)變化的網(wǎng)絡流量和數(shù)據(jù)包長度。通過仿真實驗比較了采用AMS機制和傳統(tǒng)VMS機制的CICQ結(jié)構(gòu)的交換性能，結(jié)果表明提出的自適應數(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交換結(jié)構(gòu)調(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.

A novel efficient adaptive packet segmentation scheme in CICQ switches

Wang Xiaoting，Wang Yiwen，Li Ping
(School of Microelectronics and Solid-State Electronics，State Key Laboratory of Electronic Thin Films and Integrated Devices，Chengdu 610054，China)

In order to operate on variable-size packets in CICQ(Combined Input Crosspoint Queued)switch effectively,segmentation and reassembly(SAR)is generally used to segment packets into cells to be switched.Existing packet segmentation schemes have the disadvantage of low switching efficiency and poor flexibility in dynamic network traffic.In this paper,a novel efficient adaptive packet segmentation scheme for CICQ switch is proposed.The main idea is modifying the segment size flexibly according to the status of input queues,and performing packet segmentation based on cell-merging,to adapt different traffic flows and packet lengths in network environments.Simulation results show that the proposed packet segmentation scheme is can exhibit excellent delay performance and system stability superior to existing variable-size multipacket segments scheme under various traffic models.

CICQ switch；segmentation scheme；adaptive

TP393

A

10.16157/j.issn.0258-7998.2016.02.031

（2015-10-15）

王曉婷（1987-），女，博士研究生，主要研究方向：高性能交換機架構(gòu)設計、調(diào)度算法設計、SOC實現(xiàn)。

王憶文（1966-），通信作者，男，博士，教授，主要研究方向：高性能交換機技術、可重構(gòu) SOC架構(gòu)，指紋識別等，E-mail：yiwen@uestc.edu.cn。

李平（1957-），男，碩士，教授，博導，主要研究方向：FPGA設計與測試、SOC設計與驗證。

中文引用格式：王曉婷，王憶文，李平.一種高效自適應的 CICQ交換機數(shù)據(jù)包切分機制[J].電子技術應用，2016，42 (2)：114-117，121.

英文引用格式：Wang Xiaoting，Wang Yiwen，Li Ping.A novel efficient adaptive packet segmentation scheme in CICQ switches[J]. Application of Electronic Technique，2016，42(2)：114-117，121.