交叉節點緩存crossbar交換結構設計

周延鵬，張興明

（國際數字交換系統工程技術研究中心 河南 鄭州450002）

交叉節點緩存crossbar交換結構設計

周延鵬，張興明

（國際數字交換系統工程技術研究中心 河南 鄭州450002）

針對傳統交換結構調度復雜且時間開銷大的問題，采用交叉點緩存（Buffered Crossbar）交換結構和改進的輪詢調度算法，在輸出端設置按一定的緩存順序輸出，并通過verilog代碼實現了8*8的CICQ交換結構。極大地緩解了傳統Crossbar交換結構存在的輸入輸出端口沖突問題，有效避免了隊頭阻塞問題。采用算法復雜度為O（1）的輪詢調度算法，硬件實現簡單。可以達到100%的吞吐效率，實現了最快3個時鐘周期的高速度低延時交換。

crossbar；交換結構；調度算法；輪詢

Abstract:The traditional exchange structure is complicated and time scheduling overhead problem.Using a modified round-robin scheduling algorithm，at the output buffer is set according to a certain order of output，and by verilog code to achieve the 8*8 CICQ switch fabric.Greatly reducing the conflict of input and output ports of traditional crossbar switch fabric，effectively avoiding HOL blocking problem.Using an algorithm complexity is O（1） of the round-robin scheduling algorithm，hardware implementation simple.It can achieve 100%throughput efficiency，to achieve the fastest speed three clock cycles low latency switching.

Key words:crossbar；switch fabric； scheduiingaigorithm； round-robin

當前，大容量、高性能的交換設備所采用的核心交換技術通常為交換結構（Switch Fabric）[1-3]和調度算法（Schedule Algorithm）[1，4]兩個部分。 交換結構負責的是報文高速轉，它的結構和性能直接決定了交換機設備的應用性能，因此，交換結構的設計對網絡核心交換機的研制有著十分重要的意義。對于支持高鏈路帶寬和多端口的交換設備而言，其調度器的仲裁時間越短越好，這就需要調度算法所使用的仲裁時間盡量的短，也就是說調度算法的實現復雜度要盡可能的低。因此，在交叉開關交換結構上尋求低復雜度、高吞吐量的調度算法具有非常重要的意義。常用的單Crossbar交換結構可以分為輸入排隊[5-6]、輸出排隊[5-6]、聯合輸入輸出排隊和交叉緩存交換結構[7，14]，目前大容量高速交換通常采用聯合輸入輸出排隊和交叉緩存（CICQ）[10]交換結構。在做了理論分析的基礎上，設計實現了CICQ交換結構和輪詢調度算法，該結構能實現低延時的高速數據傳輸[15-17]。

1 CICQ交換結構設計

CICQ是在CICQ交換結構的基礎上增加了輸出緩存隊列設計。根據設計思路把CICQ交換結構的組成可以分為3個部分：輸入端，交換單元，輸出端3部分組成。

CICQ交換結構工作流程可分為4步，

第一步：包到達過程，即包進入輸入端口后按照包信息緩存到對應端口的對應VOQ[1-9][11-12]緩存隊列；

第二步：輸入虛擬緩存隊列到交叉點緩存的調度過程，采用能夠用有效避免端口餓死的輪訓調度算法；

第三步：交叉節點到輸出緩存的調度過程，同樣采用輪訓調度算法[11-13]。

第四步：輸出緩存讀出過程，按一定優先級進行輸出過程；

圖1 CICQ結構框圖

1.1 輸入端口

根據8*8 CROSSBAR交換結構的需求，從上圖整體設計可以看出需要8個輸入端口，每個輸輸入端口設置8個VOQ虛擬緩存隊列分貝對應8個不同的輸出端口。采用VOQ虛擬緩存能有效的避免交換結構的對頭阻塞（HOL，Head of Line blocking）[8]問題。VOQ緩存采用深度為16，位寬為32的同步fifo設計下面對一個輸入端口進行詳細介紹；

數據進入交換結構在輸入端口虛擬緩存在非滿狀態下根據要去往的輸出端口緩存至對應的VOQ隊列，如圖2所示，r0_bus_data_i、r0_req_i均有效。r0_dest_port=8’b10000011時，數據就緩存在 VOQ0、VOQ1、VOQ7 中。

圖2 輸入端VOQ

1.2 交叉端

交叉端要完成的任務是從根據輸入調度算法從輸入端的虛擬緩存隊列中讀出數據并緩存到交叉點；

1）監測輸入端VOQ虛擬緩存中是否有數據

2）監測交叉點緩存（RN_CXB）是否為滿，即交叉點可以接受輸入端數據

3）當滿足以上兩個條件時，根據輪訓調度算法，依次從8個輸入端讀入數據緩存至交叉點緩存調度算法的實現將在后文詳細介紹。

1.3 輸出端

輸出端要完成的任務是根據輸出調度算法從交叉點緩存讀出數據至輸出緩存，在輸出緩存采先到先出的原則進行讀出。以要從輸出端口一輸出為例，做如下介紹

1） 監測 R0_CXB0、R1_CXB0、 到 RN_CXB3、中是否有數據；

2）監測對應輸出端緩存是否為滿，即輸出是否可以接收檢查點的數據；

3）當滿足以上兩個條件時，根據輪訓調度算法，依次從8個交叉點讀入數據緩存至輸出端緩存；

4）當輸出緩存中有數據時按先到先出原則讀出數據；

2 調度算法設計

CICQ交換結構采用的分布式調度，即輸入端到交叉點的輸入調度算法和交叉點到輸出端的輸出調度算法。本文采用的輸入和輸出調度算法核心都是輪訓調度，實現方式類似。在此只對輸入調度進行詳細介紹。

2.1 輸入調度

輸入調度流程如圖3所示。

圖3 輸入調度流程

調度算法流程：

1）監測輸入端VOQ虛擬緩存中是否有數據，、監測交叉點緩存（RN_CXB）是否為滿，即交叉點可以接受輸入端數據；

2）產生需要仲裁的端口請求信號備用；

3）第一次仲裁按照端口優先級順序，即0到7依次降低的順序，假設第一次0端口有請求，就從0端口開始，仲裁結果就是0，并將請求緩存至“上一次請求寄存器”跳至步驟6）；

4）第一次讀出數據以后產生仲裁請求備用；

5）根據仲裁騎牛和當前仲裁端口信息以及緩存寄存器信息產生仲裁結果；

6）根據仲裁結果從沖輸入VOQ緩存中讀出數據；

7）讀出數據緩存至交叉點緩存

8）結束。

2.2 輸出調度

輸出調度和輸入調度均采用輪詢算法，區別主有兩點

1）輸出調度中的進入數據時緩存在輸出端口相同的交叉點緩存 （假設輸出端口為0，對應的是R0_CBX0、R1_CBX0 到 R7_CBX0）；

2）數據輸出的緩存隊列不同于輸入調度的多個CBX緩存，而是多個CBX緩存至一個輸出緩存。

3 仿真驗證

仿真驗證環境為linux下的Vivado套件，由于仿真驗證工作繁瑣，所以只列出輸入調度、輸出調度、以及整體的仿真信息。

測試激勵說明：

對8個輸入端口全部進行多播[7]形式數據寫入，這樣可以更全面地測試輸入和輸出調度以及數據輸出是否按照預期輪詢依次輸出。

3.1 調度仿真

輸入調度：

輸入調度做作用綜合考慮輸入緩存和交叉點緩存以及上一次調度結果，產生ib_grant仲裁信號。從圖4可以看出ib_grant能夠正常移位進行輪詢調度。

圖4 輸入調度仿真

輸出調度：

輸出調度做作用綜合考慮交叉點緩存和輸出緩存以及上一次調度結果，產生ob_grant仲裁信號。從圖5可以看出ob_grant能夠正常移位進行輪詢調度。

圖5 輸出調度仿真

3.2 系統仿真

系統及仿真主要體現輸入數據能否正常到達目標端口，從圖6可以看出輸出信號能夠依次輸出，需要說明的是第一個輸出信號延遲較長，后邊達到流水輸出后就能夠達到最短3個時鐘延遲的告訴輸出。

圖6 系統仿真

3.3 硬件開銷

硬件開銷如圖7所示。

圖7 硬件開銷

4 結 論

本文主要研究了一種基于CICQ的crossbar交換結構和基于輪訓的調度算法，并通過Verilog編碼實現，在vivado工具下進行了仿真和基本功能驗證以及網標綜合，均達到設計要求。實現了流水輸出，最短輸出時間延遲為3個時鐘周期，該交換結構和角度算法可以應當前很多交換設備在硬件電路設計和功能驗證方面具有一定的理論意義和應用價值。

[1]王俊芳，張思東.通用高速分組交換調度算法[J].電子科技大學學報，2010（1）：69-73.

[2]韓永，姚念民，蔡紹濱，等.iSCSI虛擬交換機包轉發調度算法 FC-WFQ[J].電子學報，2013，41 （3）:587-592.

[3]蔣泳波，高速交換結構多播技術研究[D].西安：西安電子科技大學，2013.

[4]高雅，邱智亮，張茂森，等.一種支持單組播混合交換的 Clos網絡及調度算法 [J].西安電子科技大學學報：自然科學版，2013，40（1）:48-52.

[5]徐寧，余少華，汪學舜.一種新型的負載均衡－交叉點緩沖交換結構 [J].電子學報，2012，40（12）:2360-2366.

[6]戴藝，蘇金樹，孫志剛.高性能新型交換結構綜述[J].電子學報，2010，38（10）:2389-2399.

[7]Divakaran D M，AnhaltF，Altman E.Size-based flow scheduling in a CICQ switch[A].Dallas，USA:IEEE 2010.

[8]Rojas-Cessa， Roberto，Dong， Ziqian.Load-Balanced Combined Input-Crosspoint Buffered Packet Switches[J].IEEE Transactions on Communications 2011，5（5）.

[9]倪杰.用于三級Clos網絡的一種高效自尋路交換機制研究[D].成都：電子科技大學，2013.

[10]鄭若鹢.CICQ交換結構的調度算法分析[J].電腦與信息技術，2010（6）：20-22.

[11]Lin D，Jiang Y，and M.Hamdi.Selective Request Round-Robin Scheduling for VOQ Packet Switch Architecture[C]//Proceedings of IEEE International Conference on Communications （ICC），2011:1-5.

[12]任濤，蘭巨龍，扈紅超.并行分組交換研究綜述[J].計算機工程與設，2012（1）：47-50.

[13]LaMaire R O，Serpanos D N.Two dimensional round-robin schedulers for packet switches with multipleinputqueues[J].IEEE/ACMTrans.Networking，Oct.2010，2（5）:471-482.

[14]Jeroen Famaey，Frederic Iterbeke，Tim Wauters，et al.Towards a predictive cache replacement strategy formultimedia content [J].Journalof Network and Computer Applications 2013，1（1）.

[15]張亞夫，宣二勇.高速交換矩陣調度器的FPGA設計[J].無線電工程， 2013（6）：4-5.

[16]朱謙，蔣林，蔡龍.分組交換技術在光傳輸網中的研究與設計[J].電子科技，2013（6）:1-3.

[17]邱春婷，劉紅彥，齊靜.一種改進的Canny邊緣檢測方法[J].紡織高校基礎科學學報，2014，27（3）：380-384.

The design of buffered crossbar switches

ZHOU Yan-peng，ZHANG Xing-ming
（National Digital Switching System Engineering and Technological R&D Center， Zhengzhou450002，China）

TN4

A

1674－6236（2017）19-0141-04

2016-08-02稿件編號201608010

周延鵬（1990—），男，河南洛陽人，碩士研究生，講師。研究方向：芯片設計。