基于緩解HoL堵塞的單組播混合調度算法

2019-03-05 03:37:26袁龍熊慶旭蕭翰

北京航空航天大學學報 2019年2期

袁龍，熊慶旭，蕭翰

(北京航空航天大學電子信息工程學院, 北京 100083)

隨著網絡應用的發展，網絡所承載的業務類型從單一類型逐漸向多元化發展，交換機不僅需要支持純單播業務或純組播業務分組轉發，還需要有效調度單組播混合業務。

輸出排隊(Output Queued,OQ)結構的通過率為100%，可提供QoS確保功能，但存在N倍加速比，不易于擴展[1]。輸入排隊(Input Queued,IQ)結構加速比為1，可擴展性強，但需采用虛擬輸出排隊(Virtual Output Queuing,VOQ)[2]結構克服頭分組(Head of Line,HoL)堵塞[3]問題。對于單播業務只需在每個輸入端口配置N個虛擬隊列，但組播業務分組扇出類型多達2N-1種，則需要在每個輸入端口放置2N-1個隊列[4]，難以在大規模交換機中實用化。目前的研究通常配置k(1

隨著集成電路技術的發展，聯合輸入交叉排隊(Combined Input and Crossbar Queued，CICQ)被普遍認為最值得期待的高性能分組交換結構,但 CICQ結構單組播混合業務調度算法研究不多。早期主要以單播調度或組播調度為主，在單播調度中[5-7]，文獻[7]提出的交叉緩存隊列均衡(Crossbuffer Queue Balance,CQB)算法從定量的角度出發，以交換機實現work-conserving狀態為追求目標，使交換機的性能得到顯著提升。在組播調度中，Mhamdi和Hamdi提出了組播交叉結點輪詢(Multicast Cross-Points Round Robin,MXRR)算法[8]，由于輸入端口中僅采用單FIFO(First In First Out)隊列，存在嚴重的HoL堵塞問題。文獻[9]提出了輪詢(Round Robin,RR)、最小扇出優先(Minimum Residue First,MRF)、最大服務優先(Maximum Service First,MSF)以及最大服務率優先(Maximum Ratio of Service First,MRSF)等調度算法，并在輸入端口采用多個組播隊列，從結構上緩解了組播HoL堵塞，提高了交換機的通過率降低了平均分組時延。為了滿足單播組播混合業務調度的需求，Mhamdi和Vassiliadis提出了單組播輪詢調度(Multicast and Unicast Round robin Scheduling,MURS)算法[10]，采用不同的優先級輪詢調度單組播業務。雖然算法復雜度低，但整體性能欠佳。Yi等提出的低代價組播調度(Low-Cost Multicast Scheduling,LCMS)算法[11]，考慮了單組播業務之間的差異性，基于權重裁決單組播之間的競爭，算法的性能有一定提升，但輸入端口僅采用一個組播隊列，導致了較嚴重的HoL堵塞。梁佳誠等提出的均衡交叉節點緩存單組播調度(Multicast and Unicast Crossbuffer Balance,MUCB)算法[12]，與以往基于輪詢或者基于權重的調度算法不同，而是采用了均衡交叉節點緩存占用的思路，使交換機最大程度地逼近work-conserving狀態。雖然MUCB算法使交換機的性能有了較好的改善，但沒有采取有效機制以緩解HoL堵塞。

為了緩解組播HoL堵塞問題，通常在輸入端口配置k個組播隊列。因此，新到達分組需要按照一定的入隊策略選擇合適的隊列入隊。在已有研究中，多數基于三大準則[9]提出相應的入隊策略，主要分為2類：

1) 靜態入隊策略，如文獻[13]提出Module入隊策略，利用分組扇出數取余的方法選擇隊列，即：i=Fmodk；實現簡單，但扇出數目相同卻不相關的分組會進入同一緩存隊列，且對于小扇出分組均衡性差。文獻[14]提出加權取模(Weighted Module,WM)入隊策略改善了Module中小扇出組播均衡效果差的問題。文獻[15]提出特征向量法(vector)選擇分組扇出與隊列特征向量距離最小的隊列入隊，增加了頭分組扇出差異性，但負載均衡的效果一般。

2) 動態入隊策略，如文獻[9]提出的面向分組輪詢分配(Cell oriented Round-Robin Assignment,CRRA)、面向突發輪詢分配(Burst oriented Round-Robin Assignment,BRRA)、面向最短隊列分組優先(Cell oriented Shortest Queue First,CSQF)和面向最短突發隊列優先(Burst oriented Shortest Queue First,BSQF)等入隊策略，存在分組失序問題。

本文通過研究HoL堵塞與work-conserving之間的關系，基于CICQ結構提出一種新的單組播混合調度算法, 即單組播低HoL堵塞(Multicast and Unicast with Low HoL Blocking,MULHB)算法，其基本思想就是以緩解HoL堵塞為目標，使交換機逼近work-conserving狀態。同時，為了進一步緩解HoL堵塞，本文提出一種新的組播分組入隊策略, 即動態組播分組入隊(Dynamic Muticast Queuing,DMQ) 策略，使新到達分組根據緩存隊列的狀態可以動態選擇合適的隊列入隊。

本文首先對CICQ結構單組播混合調度中的主要問題進行了分析；然后，具體說明了DMQ策略以及MULHB算法；最后，給出了本文提出算法的仿真結果，并和當前主流的單組播混合調度算法進行比較和分析。

1 問題分析

本文討論的CICQ交換結構如圖1所示。每個輸入端口分別配置N個單播隊列和k(1

CICQ結構work-conserving狀態是指，任一時隙中若交換機中存在去往某個輸出端口的分組，則該時隙必有分組離開該輸出端口。由于輸入端口中組播隊列的數目受到限制，因此，在調度過程中，屬于同一組播隊列的分組扇出去向不完全一致。此時，若組播隊列的后續分組中存在使交換機滿足work-conserving狀態的扇出去向，而頭分組中不存在，則發生了由HoL堵塞引起的非work-conserving問題。由于考慮整個組播隊列中全部后續分組的扇出過于復雜，本文算法中僅考慮頭分組對次分組的堵塞造成的影響。

為了盡量解決由HoL堵塞引起的非work-conserving狀態，在每一時隙中，分組入隊后、輸入調度前，應使所有輸入端口中存在若干不屬于同一端口的頭分組的扇出去向可以完全覆蓋所有傳輸需求但對應節點緩存列為空的輸出端口。為了達到上述條件，首先，可以通過入隊策略動態調整新到達分組在隊列排隊狀態。已有實用的靜態入隊策略由于選擇隊列的方式固定，分組入隊后，相同扇出類型的分組不能根據調度的需求重新選擇合適的隊列入隊。同時，仿真統計發現在調度過程中，輸入端口內的緩存隊列出現大量為空的狀態。因此，入隊策略應當使新到達分組根據當前緩存隊列的狀態動態選擇合適的隊列入隊，尤其存在可選的空隊列時，應充分選擇空隊列入隊，使輸入端口中頭分組的扇出差異性增大。其次，為了使交換機達到高通過率及低時延的目標，應盡可能使交換機處于work-conserving狀態。從文獻[7]中給出交換機實現work-conserving的條件可知，在輸入調度之后，所有的有傳輸需求的輸出端口對應節點緩存列均不為空，從而使得輸出端口總有分組離開。在此基礎上，輸入調度后，應使有助于交換機逼近work-conserving狀態的次分組盡快成為頭分組。最后，輸出調度應盡快調度節點緩存中可能導致發生HoL堵塞的分組離開交換機。

圖1 CICQ交換結構Fig.1 CICQ switch architecture

此外，在輸入端口中采用的緩存配置方式對單播和組播分組進行隔離處理。由于2種業務之間存在一定的差異性，當輸入調度在選擇分組進入節點緩存內時，需要采用一定的裁決機制解決單、組播分組之間的競爭問題，以避免“餓死”現象發生。

2 DMQ-MULHB調度算法

由第1節分析可知，為使交換機避免發生由HoL堵塞引起的非work-conserving狀態，本文采用新的入隊策略控制分組入隊，同時結合相應的輸入輸出調度算法使交換機盡可能在分組入隊后、輸入調度前，所有輸入端口中存在若干不屬于同一端口的頭分組的扇出去向可以完全覆蓋有傳輸需求但對應節點緩存列為空的輸出端口。本節將從入隊策略、輸入調度和輸出調度等環節詳細分析DMQ-MULHB調度算法的設計。

2.1 入隊策略

當輸入端口i有組播分組到達時，選擇入隊隊列的具體步驟如下：

1) 分組到達時，若H[p]≠0,選擇隊列號等于F[p]值的隊列入隊，入隊結束；否則進入步驟2)。

2) 若存在空隊列，選擇分組扇出與隊列特征向量差異最小的隊列，進入步驟5)；否則進入步驟3)。

3) 若存在隊長為1的隊列，選擇分組與頭分組扇出差異最小的隊列，進入步驟5)；否則進入步驟4)。

4) 選擇分組與隊尾分組扇出差異最小的隊列；若存在多個，則選擇最短隊列。

5)F[p]更新為所選隊列序號，H[p]加1，選擇F[p]對應隊列入隊，入隊結束。當索引值為p的頭分組在輸入端口完全扇出時，H[p]減1。

由上述步驟可知，首先，步驟1)限定了新到達分組重新選擇隊列入隊的條件，只有當該輸入端口中相同扇出類型的分組緩存數目為零時，才能重新選擇隊列入隊，該機制避免發生亂序；其次，步驟2)允許可重新選擇隊列的新到達組播分組進入空隊列增加端口中頭分組扇出差異，使隊列頭分組獲得更多調度機會，以緩解了HoL堵塞，使交換機盡量逼近work-conserving狀態。最后，步驟3)～步驟5)對于緩存分組具有均衡作用，同時盡量減少相鄰分組間的扇出差異，當前一分組成為頭分組時，可以緩解頭分組對次分組造成的HoL堵塞。

2.2 MULHB調度算法

本文提出MULHB算法，在輸入調度過程中，首先，找出有傳輸需求且對應節點緩存列為空的輸出端口；其次，找出扇出去向包含上述輸出端口且頭分組扇出去向類型數最少的輸入端口；再次，從上述輸入端口中找出滿足工作保持狀態的頭分組；最后，從中優先選擇可以完全扇出且對應次分組有助于交換機逼近work-conserving狀態的頭分組進行傳輸。在輸入調度中盡量使交換機既在當前時隙實現work-conserving狀態，又使輸入端口中頭分組扇出在后續時隙盡可能覆蓋所有有傳輸需求的輸出端口，從而避免交換機發生由HoL堵塞引起的非work-conserving狀態。另外，在裁決單、組播分組之間的競爭時，組播分組的權重以頭、次分組扇出、節點緩存狀態以及頭分組等待時間作為權重因子，單播分組的權重以等待時間作為權重因子。基于權重比較完成，避免“餓死”現象發生。在輸出調度過程中，輸出調度優先選擇其次分組有助于交換機在后續時隙逼近work-conserving狀態的頭分組對應的節點緩存中的分組進行輸出。

輸入調度算法：

1) 初始化集合O包含所有輸出端口，集合I包含所有輸入端口。

2) 若集合O為空，則結束該時隙輸入調度。

3) 從集合O的第1個元素開始，找出max{yj}對應輸出端口j，若max{yj}=0，進入步驟11)。

4) 若集合J為空，從集合O中剔除輸出端口j，回到步驟2)。

5) 從J的第1個元素開始，選擇其中min{Di}對應輸入端口i；找出輸入端口i中存在扇出去向包含輸出端口j且可完全扇出的組播頭分組，進入下一步；否則，進入步驟8)。

6) 若步驟5)找出的頭分組中存在次分組滿足Sik>0，則選擇max{Sik}對應的組播隊列，進入步驟9)；否則，進入步驟7)。

10) 從集合I中剔除輸入端口i，更新U、J、Y，回到步驟3)。

11) 若集合I為空，該時隙輸入調度結束。

12) 從集合I的第1個元素開始，若Mi中存在可完全扇出的頭分組，進入步驟13)，否則，進入步驟15)。

13) 若Mi中存在次分組滿足Sik>0，則選擇max{Sik}對應的組播隊列，進入步驟16)；否則，進入步驟14)。

輸出調度算法：

1) 初始化集合O包含全部輸出端口，集合I包含全部輸入端口。

2)若集合O為空，則結束該時隙輸出調度。

3) 從O的第1個元素開始，從輸入端口中找出所有包含輸出端口j扇出去向且狀態不為空的Xij對應的隊列；若存在，進入下一步；否則進入步驟7)。

4) 若步驟3)中找出的隊列中存在次分組滿足Sik>0，則選擇max{Sik}對應的組播隊列；否則，進入步驟6)。

6) 輸出Xij中分組，從集合O中剔除輸出端口j，回到步驟2)。

3 仿真及對比分析

本節將基于CICQ交換結構對DMQ-MULHB算法進行仿真并對其性能進行評估。仿真采用Bernoulli和ON-OFF兩種業務作為業務源模型。交換結構的端口規模為16×16，仿真時間為100萬個時隙，每個輸入端口設有8個組播隊列。其中ON-OFF業務的平均突發長度為16。為了方便對性能進行分析，同時給出了最大扇出優先和最大服務比率優先(Maxfanout First and Maximum Ratio of Service First,MF-MRSF)算法、MUCB算法以及OQ調度的仿真結果進行對比，其中MF-MRSF算法、MUCB算法均采用Module入隊策略。