星載IP交換機中變長調度Clos交換結構的設計

鄭　振，喬廬峰，陳慶華，邵世雷，張俊俊

(中國人民解放軍理工大學 通信工程學院，江蘇 南京 210007)

?

星載IP交換機中變長調度Clos交換結構的設計

鄭振，喬廬峰，陳慶華，邵世雷，張俊俊

(中國人民解放軍理工大學 通信工程學院，江蘇 南京 210007)

針對星載設備對體積、硬件資源消耗等嚴格限制的情況，為提高IP交換機的吞吐性能，同時盡可能地降低硬件開銷與時延等，設計了一種用于星載IP交換機中的三級Clos交換結構。該結構可支持多個優先級，并采用變長分組調度機制，能夠直接處理IP分組。該結構還對原有的三級Clos結構進行改進，將中間級部分整合為一個模塊完成，便于在中間級實行集中調度，從而避免了在輸出級模塊中形成阻塞，同時簡化了交換結構的實現過程，降低了硬件資源耗費。使用Xilinx xc5vlx330t FPGA實現了完整的16×16的八優先級變長調度交換結構，其峰值吞吐率可達16 Gb/s。綜合結果顯示，整個交換結構占用slice register 80352個、block RAM 252塊，滿足星載交換機的設計需求。

星載交換機；交換結構；Clos結構；變長調度；FPGA

0　引　言

信息技術的快速發展在大大方便人們工作、生產和生活的同時，也在不斷產生海量的通信數據，這給當前的衛星網絡帶來了嚴峻的挑戰。而網絡的核心是路由器和交換機等節點設備，它們的性能直接影響網絡的時延、吞吐量等重要參數。因此，研制高性能的星載交換機對于衛星網絡來說顯得尤為重要。

當前大多數交換設備所使用的是單級crossbar交換結構。這種結構因其簡單、靈活等優點而得到廣泛的研究和優化[1]，然而由于受單個芯片端口數量和速率等的限制，該結構的性能已經逐漸到達極限[2]。同時，星載設備對體積、功耗等有著苛刻的限制，加上太空電磁環境惡劣，關鍵電路還需要使用備份來克服單粒子效應等帶來的不良影響，這對星上交換電路的硬件資源消耗提出了更嚴格的要求。

此外，目前在星載交換設備中已經得到廣泛應用的是ATM交換技術，而IP交換機在地面網的普及使得可以實現直接傳輸IP包的星載IP交換機成為研究熱點[3-4]。

本文針對星載IP交換機設計并實現了一種改進的變長調度三級Clos交換結構，該結構可支持優先級服務，并具有可直接處理IP分組、結構模塊化且占用邏輯電路資源少等優點。

1　交換結構的構成

Clos結構最早由Chales Clos于1953年提出[5]，目前最常用的是三級Clos結構，其一般由k個輸入級模塊(Input Module, IM)、m個中間級模塊(Central Module, CM)、k個輸出級模塊(Output Module, OM)排列而成，每一個交換模塊和相鄰級任一交換模塊通過唯一路徑相連。

在三級Clos交換結構中，人們使用最多的是存儲器-空分-存儲器(Memory-Space-Memory, MSM)結構，它曾被成功地用在ATLANTA交換機中[6]，后來又不斷得到應用和改進[7-8]。該結構在輸入級和輸出級模塊中設置緩存，而在中間級模塊中采用無緩存的交叉開關(crossbar)結構。相比于全空分結構，這種結構在調度上更簡單，而相比于全緩存結構，它又有更低的時延和更少的資源消耗。

考慮到MSM型交換結構一般采用分布式調度算法，各個中間級模塊之間的調度過程相互獨立，且其調度算法較為簡單，保持原有調度機制而集成到一個芯片上并不會增加算法復雜度，同時，無緩存的中間級模塊結構簡單，在端口數量不太多的情況下完全可以由一個模塊代替，因此，本文提出了一種針對星載交換機改進的三級Clos交換結構，如圖1所示。在滿足電路性能要求的基礎上，這種設計便于在中間級模塊采取集中調度、有利于簡化輸出級電路，從而降低了交換結構的實現復雜度，同時還盡可能地降低了交換電路的體積、硬件資源耗費等。

圖1　改進的三級Clos交換結構

1.1輸入級模塊

IM的結構如圖2所示，每個IM都有n個輸入端口、m條連接到中間級模塊的輸出鏈路、k個隊列控制器(Queue Controller, QC)和一個輸入級調度器等。

圖2　輸入級模塊的結構

其中，k個QC分別用來管理去往不同輸出級模塊的虛擬輸出隊列(Virtual Output Queue, VOQ)，每個QC中容納pn個虛擬輸出隊列(p為優先級數，n為每個輸出級模塊的輸出端口數)。一個QC內含有兩個RAM、n個權重調度器和一個輸出調度器，其中兩個RAM分別作為指針隊列存儲器和隊列信息存儲器，n個權重調度器分別為各自相應的輸出端口提供優先級服務，輸出調度器則可以在不同輸出端口的虛擬輸出隊列之間平衡獲得接入的機會。

輸入級調度器的作用是與中間級調度器協作，在公平的前提下，最大化地將已到達的輸入請求分配到m條輸出鏈路。

此外，為了節約存儲資源，在每個IM中還設有一個SRAM作為數據存儲器集中存放到達的數據、一個空閑地址管理器用以維護SRAM內的空閑指針信息。當有IP包到達，首先會從空閑地址管理器中讀取空閑指針，根據指針位置將包存入SRAM中，然后根據數據包的目的端口和優先級將該指針以鏈表的形式在對應的QC中進行排隊，隊列存放在指針隊列存儲器中，每個鏈表隊列的頭指針、長度等信息存于隊列信息存儲器中。如果有一個包要去往多個目的端口，就將該包所存放的地址指針復制到各目的端口對應的隊列中去，同時在多播計數管理器中計數。這種指針復制的多播實現方式也能有效地減少資源消耗。

1.2中間級模塊

交換結構的中間級模塊結構如圖3所示，有mk條輸入鏈路和輸出鏈路、一個中間級調度器和一個mk×mk的crossbar。其中，中間級調度器的工作是協助k個輸入級調度器完成鏈路的有效分配并避免發生沖突。mk×mk的Crossbar用來提供從輸入級模塊到輸出級模塊的無阻塞連接，可以直接將到達的數據轉發出去。

圖3　中間級模塊的結構

1.3輸出級模塊

輸出級模塊的結構較為簡單，有m條來自中間級模塊的輸入鏈路、n個輸出端口和(m+n)個先入先出緩存(First Input First Output, FIFO)。其中每個FIFO各對應一個輸入或輸出端口，用來作為該端口的緩存，從而保證數據在輸出端得到完整有序的輸出。

2　交換結構的隊列模型

在ATM網絡中，數據都是被封裝進固定大小的單元中，被稱為信元。但是在IP網絡中卻不同，長度可變的IP分組最大可以支持65 535字節。為了能夠在ATM交換技術的基礎上傳輸IP分組，當前廣泛使用的是通過分段重組來實現變長調度的信元交換模型。如圖4所示，這種模型在每個輸入端口都需要一個輸入分段模塊(Input Segmentation Module, ISM)把每個變長IP分組分割成多個長度固定的內部信元，然后在交換結構中以每個內部信元為單位進行調度傳輸。另外在每個輸出端口采用一個輸出重組模塊(Output Reassembly Module, ORM)，把來自不同輸入端口的不同數據包進行重組復原，同時還要為每個數據流設置一個FIFO進行緩存[9]。

圖4　基于分段重組的信元交換模型

這種模型雖然較為方便地實現了IP分組的傳輸，但是存在一些缺點。首先，當端口數量較多或者設有多個優先級時，信元的分段重組部分會消耗很多的硬件資源；其次，分段和重組的過程引入了一定的交換時延；此外，對于三級Clos等多級交換結構，信元間還會產生亂序，這樣為信元重排要付出更大的代價。

針對資源消耗的問題，以nk×nk的三級Clos交換結構來計算，由于要在每個輸出端口為來自不同輸入端口的數據流各設一個緩存隊列，所以需要(nk)2個隊列，考慮到還要支持p個優先級服務，則共需p(nk)2個隊列。而在相同的條件下，如果直接變長調度傳輸IP分組而不需要在輸出端重組，那么將只需為每個輸出端口設置一個緩存隊列，即共nk個隊列。顯然，變長調度的方式可以有效降低輸出級模塊的電路資源消耗及設計復雜度。

然而，如果直接以IP分組為單位進行調度傳輸，由于IP分組長度的不確定性，在大規模交換結構中，這種純分組交換的調度器將會復雜得難以實現[10]。因此，本設計采用了另一種以邏輯切分的方式實現變長調度的分組交換模型，如圖5所示。這種方法并不是對IP分組采取真正的物理切割，而是在邏輯上將分組分成長度為64字節的定長信元，但屬于同一個分組的信元在調度傳輸上仍然是按序連續的。當交換結構為一個信元建立輸入輸出連接后，該連接會一直保持直到來自該分組的最后一個信元傳輸完畢，這樣在輸出端就可以直接得到完整的分組。

圖5　分組交換模型

3　交換結構內的調度器

3.1輸入級調度器與中間級調度器

對于MSM型的三級Clos交換結構，為了避免內部阻塞和輸出端口競爭等，人們先后提出了隨機分配(Random Dispatching, RD)[6]、并發輪詢分配(Concurrent Round-Robin-Based Dispatching, CRRD)[11]、并發主從輪詢分配(Concurrent Master-Slave Round-Robin Dispatching, CMSD)[11]等調度算法。這些算法大多采用協議匹配的方式，一般為兩次匹配過程，一次先是在輸入級內部，由VOQ與輸入級模塊輸出鏈路之間的匹配，第二次是輸入級與中間級之間的匹配。這樣的兩次匹配需要輸入級與中間級模塊共同完成，因此在每個輸入級模塊中都需要一個輸入級調度器，中間級模塊還需一個中間級調度器。

在一般的三級Clos交換結構中，RD算法并不能很好地解決內部阻塞問題，而CRRD算法在非均勻流量下可能會引起一定的內部沖突。因此有人提出了一些改進的算法，如：分布式正交路由算法[7]、主動授權并發輪詢調度算法[12]等。這些算法較好地提高了交換結構在多種業務流下的吞吐性能，然而實現起來相對復雜，且難以滿足提供多優先級服務、支持變長調度等需求。而本文中改進的三級Clos交換結構由于其只使用一個中間級模塊，其內部采用16×16的crossbar結構，且調度過程中在中間級可以由一個模塊集中仲裁，已經盡可能地減少了一般三級Clos交換結構的內部沖突問題，因此完全可以參考CRRD算法完成調度器設計。

輸入級調度器的作用是將該輸入級模塊中的至多nk個非空VOQ與m個輸出鏈路之間通過“請求-允許-接受”的握手方式相互匹配建立連接，并且多次迭代以確保輸出鏈路能得到充分使用。匹配的建立過程由nk個VOQ仲裁器和m個輸出鏈路仲裁器共同完成。每個仲裁器都維護著一個輪詢指針，根據指針的位置來選擇建立連接的對象。

一個非空VOQ與輸出鏈路匹配完成后，輸入級調度器還需要向中間級調度器發送一個匹配請求，匹配的目標是與該VOQ的目的輸出級模塊相連的中間級輸出鏈路。中間級調度器就根據各個輸出鏈路所收到的請求，各選擇其中一個確認匹配，選擇的過程同樣遵循各自的輪詢指針。

兩次匹配完成之后，從VOQ到輸出級模塊的通路便建立成功，該VOQ開始發送隊首的信元。為了實現變長調度對同一分組的信元連續調度的需求，當一條通路建立完成后，輸入級調度器和中間級調度器便要保持該通路的兩個匹配狀態，直到同一個分組的所有信元都按照順序地傳輸完成才能斷開連接再重新匹配。

基于CRRD算法的輸入級調度器和中間級調度器結構簡單，匹配的工作全部由采用輪詢機制，實現較為容易。此外，通過保持匹配狀態來完成單次傳輸整個分組，效率高并且有效降低了資源消耗。

3.2輸入級模塊內的其他調度器

考慮到在一個輸入級模塊內單次只能有一個輸出接口訪問片外存儲器，即一次只能有一個隊列獲得輸出機會，另外，在進行變長調度時，不同的隊列中分組的長度可能會有較大差異，且不同端口所經過的流量特征也會有不同，為了在滿足一定吞吐性能的同時盡可能保證公平性，還需要設置多個調度器。

首先是在每個QC內，為了在調度中實現對不同優先級隊列的區分服務，設置了n個權重調度器，分別對應n個輸出端口。在每次輸出時，每個權重調度器要從p個優先級不同的隊列中選擇一個進行輸出。本設計采用權重輪詢(Weighted Round Robin, WRR)算法[13]實現，通過更改不同優先級在輪詢列表中出現的頻率來控制帶寬分配，優先級越高則輪詢的頻率越高，該優先級對應的隊列也就更容易得到輸出機會。

其次是在QC與輸入級模塊輸出接口之間，以及每個QC的輸出端都有一個輸出調度器，用來保證在去往不同端口的隊列之間調度的公平性。在每次輸出時，首先由QC與輸出接口之間的輸出調度器從k個QC中選擇一個，然后在選中的QC內，再由輸出調度器從n個權重調度器中選擇一個進行輸出。本設計采用輪詢(Round Robin, RR)算法實現，每個輸出調度器都通過簡單輪詢的方式選擇輸出對象，從而達到對每個輸出端口的公平調度。

以上采用的WRR調度器和RR調度器結構簡單、易于實現，能夠盡可能地減少硬件資源消耗，同時，也能夠在實現優先級調度的情況下保證各端口的公平。

4　仿真結果與分析

本文基于上述設計實現了一個16×16的八優先級變長調度三級Clos交換結構(n=k=4，p=8)。交換結構的具體電路設計使用Verilog HDL語言完成，并在Xilinx的xc5vlx330t FPGA上進行了實現。設計過程采用ISE Design Suite 14.3開發環境，并且用Modelsim SE 10.0a對整個電路完成了仿真。以下是一些關鍵電路的仿真結果。

4.1輸入級調度器與中間級調度器工作仿真

圖6所示的仿真波形是在一個輸入級調度器內進行的匹配過程。圖中①處表示在該輸入級模塊中，有四個輸出請求，分別來自VOQ0、VOQ4、VOQ8和VOQ12，其中VOQ12要輸出的是一個單信元分組，該分組長度不足64字節而只需用一個內部信元傳輸，VOQ8要輸出的是一個分組內的首個信元，該分組由不止一個內部信元組成，而VOQ0和VOQ4要輸出的則是各自分組的最后一個信元，并且該分組之前已經輸出了一部分。可以看到在圖中②處，輸出鏈路0和輸出鏈路1維持了之前已經分別跟VOQ0和VOQ4達成的匹配關系，而輸出鏈路2和3則與VOQ8和12開始了新的匹配。經過兩次迭代，該輸入級模塊內匹配全部完成，4個輸出鏈路向中間級發送輸出請求，如圖中③處所示。

圖6　輸入級調度器工作仿真波形

圖7是中間級調度器參與調度過程的仿真波形。以圖中豎線游標處為例，中間級調度器收到了8個來自輸入級的請求，其中4個IM的輸出鏈路0都請求與CM輸出鏈路4建立匹配、4個IM的輸出鏈路1都請求與CM輸出鏈路0建立匹配。可以看到CM輸出鏈路4選擇IM0的輸出鏈路0回應了允許，CM輸出鏈路0選擇了IM0的輸出鏈路1回應了允許。這樣，兩條連接就建立完成。另外，從整個仿真結果來看，中間級調度器中收到的各個請求都得到了較為公平的匹配機會。

圖7　中間級調度器工作仿真波形

4.2輸入級隊列的調度過程仿真

本文實現的交換結構中有4個IM，每個IM中有4個QC，而每個QC中包含去往4個不同輸出端口的共計32個隊列。輸入級內的各個調度器就是要保證所有隊列都能得到公平的輸出。

圖8是針對優先級為0的條件下，各個IM中要去往輸出端口0、4、8和12的4個隊列的深度變化情況仿真結果。圖中的數值表示各自隊列中當前正在排隊的分組數。由圖可見，在優先級相同的情況下，各個隊列都能得到均衡的調度機會，較好地保證了公平性。

圖8　部分隊列的深度變化仿真時序

4.3綜合結果分析

使用Xilinx XST綜合工具，對整個電路在xc5vlx330t FPGA上進行的綜合，得到的綜合結果報告如表1所示。該16×16的八優先級變長調度三級Clos交換結構設計共占用80 352個Slice Register、100 629個Slice LUTs和252塊Block RAM，資源占用比率相對較少。因此該設計完全可以在一個芯片內實現，方便了三級交換結構在實現過程中的接口調試等工作，此外，使用兩片FPGA即可實現整個電路的備份，滿足星載交換設備的設計要求。

表1　器件資源使用情況報告

考慮到該交換結構的吞吐率主要與輸入級模塊內部數據存儲器的訪問帶寬有關，而設計使用的SRAM數據位寬為128位、時鐘頻率為125 MHz，且一次讀或寫操作占用兩個時鐘周期，則SRAM讀寫帶寬為8 Gb/s。因此在對SRAM讀寫操作均衡的條件下，每個輸入級模塊的吞吐率最高可達4 Gb/s，則該16×16交換結構的峰值吞吐率可達16 Gb/s。

5　結　語

本文針對星載IP交換機，設計并實現了一種支持多優先級的變長調度三級Clos交換結構。相比于文獻[9]中實現的基于共享緩存的單級交換結構，本結構不僅可以擴展交換端口的規模，還大大提升了交換結構的吞吐性能。而相較于文獻[7]中提出的中間級交換模塊數目可變的Clos網絡結構，本文實現的結構將多個中間級交換單元整合為單個中間級模塊，簡化了交換結構，不需要動態調整中間級模塊的數目，降低了調度算法的復雜度，且占用更少的硬件資源，滿足了高性能星載交換機的設計需求。下一步將要研究交換結構的進一步優化方法，以及對應的更加高效的調度算法。

[1]戴藝, 蘇金樹, 孫志剛. 高性能新型交換結構綜述[J]. 電子學報, 2010, 38(10): 2389-2399.DAI Yi, SU Jin-shu and SUN Zhi-gang. A Survey on High Performance Switch Architecture[J]. Acta Electronica Sinica,2010,38(10):2389-2399.(in Chinese)

[2]夏羽. 高性能大容量多級交換結構與調度算法研究[D]. 成都: 西南交通大學, 2012: 3-5.

XIA Yu. Research on Multi-Satge Switch Fabric and Scheduling Algorithms for High-Performance and High-Capacity Switches[D]. Chengdu: Southwest Jiaotong University, 2012: 3-5. (in Chinese)

[3]王晶, 喬廬峰, 陳慶華等. 一種星載 IP 交換機隊列管理器的設計[J]. 通信技術, 2015, 48(10):1196-1201.

WANG Jing, QIAO Lu-feng, CHEN Qing-hua, et al. Design of Queue Manager in Satellite-Borne IP Switch[J]. Communications Technology, 2015, 48(10): 1196-1201.(in Chinese)

[4]Buster D. Towards IP for Space-based Communications Systems: A Cisco Systems Assessment of a Single Board Router[C]//MILCOM. 2005, 5: 2851.

[5]Clos C. A Study of Non-Blocking Switching Networks[J]. Bell System Technical Journal,1953,32(2):406-424.

[6]Chiussi F M, Kneuer J G, Kumar V P. Low-Cost Scalable Switching Solutions for Broadband Networking: the ATLANTA Architecture and Chipset[J]. Communications Magazine, IEEE, 1997, 35(12): 44-53.

[7]陶淑婷. 三級Clos交換網絡結構及其調度算法研究[D]. 西安: 西安電子科技大學, 2010: 25-44.TAO Shu-ting. Research on Switching Structure and Scheduling Algorithm for Three-Stage Clos Networks[D]. Xi’an: Xidian University,2010:25-44.(in Chinese)

[8]高雅, 邱智亮, 張茂森等. 一種支持單組播混合交換的Clos網絡及調度算法[J]. 西安電子科技大學學報, 2013, 40(01):48-52.

GAO Ya, QIU Zhi-liang, ZHANG Mao-sen, et al. Integrating Unicast and Multicast Traffic Scheduling in Clos-Network Switches[J]. Journal of Xidian University, 2013, 40(01): 48-52. (in Chinese)

[9]沈澤民，喬廬峰，陳慶華等. 一種多優先級變長調度星載IP交換機交換結構的設計[J]. 電子學報，2014, 42(10):2045-2049.

SHEN Ze-min, QIAO Lu-feng, CHEN Qing-hua,et al. Design of Switch Fabric in Satellite Onboard IP Switch based on a Multi-Priority Variable-Length Packets Scheduling[J]. Acta Electronica Sinica, 2014, 42(10): 2045-2049.(in Chinese)

[10]GAN Ja-li, Keshavarzian A and Shah D. Input Queued Switches: Cell Switching vs. Packet Switching[C] //IEEE INFOCOM 2003. San Francisco: IEEE Press, 2003: 1651-1658.

[11]Oki E, Jing Z, Rojas-Cessa R, et al. Concurrent Round-Robin-based Dispatching Schemes for Clos-Network Switches[J]. IEEE/ACM Transactions on Networking, 2002, 10(6): 830-844.

[12]劉曉鋒, 趙有健, 陳果. 一種面向MSM型Clos交換結構的啟發式并發調度算法[J]. 軟件學報, 2015, 26(10): 2644-2655.

LIU Xiao-feng, ZHAO You-jian and CHEN Guo. Heuristic Concurrent Dispatching Algorithm for MSM Clos-Network Switches[J]. Journal of Software, 2015,26(10):2644-2655. (in Chinese)

[13]ZHANG Y, Harrison P G. Performance of a Priority-Weighted Round Robin Mechanism for Differentiated Service Networks[C]//IEEE Computer Communications and Networks 2007. Honolulu:IEEE Press,2007:1198-1203.

鄭振(1992—)，男，碩士研究生，主要研究方向為高性能交換機和路由器相關技術；

喬廬峰(1971—)，男，博士，教授，主要研究方向為通信和計算機網絡中關鍵芯片和電路技術；

陳慶華(1976—) ，男，講師，主要研究方向為交換技術和計算機網絡；

邵世雷(1966—)，男，博士，教授,主要研究方向為智能網絡、通信網軟件與系統開發；

張俊俊(1991—)，男，碩士研究生，主要研究方向為高性能交換機和路由器相關技術。

Design of Clos-Network Switch Fabric with Variable-Length Packets Scheduling for Satellite Onboard IP Switches

ZHENG Zhen，QIAO Lu-feng，CHEN Qing-hua，SHAO Shi-lei，ZHANG Jun-jun

(Institute of Communication Engineering, PLA University of Science and Technology,Nanjing Jiangsu 210007,China)

Aiming at the strict restraints of volume and hardware resource consumption, and in order to improve the throughput of satellite onboard IP switches while reducing as possible the hardware overhead and time delay, a three-stage Clos-network switch fabric is designed and implemented, which could support multiple priorities and with variable-length packets scheduling, directly transmit IP packets. Benefiting from the modification of three-stage Clos network, this newly-designed fabric with one central module could easily implement centralized scheduling in middle stage and avert the blocking in last stage. Meanwhile, the switch fabric is simplified in implementation and decreased in resource consumption. Finally, a 16×16 three-stage Clos-network switch with 8 priorities is implemented in a Xilinx xc5vlx330t FPGA, and the throughput is up to 16Gbps. Overall results indicate that the whole fabric occupies 80352 slice registers and 252 block RAMs, and could satisfy the requirements of satellite onboard switches.

satellite onboard switch; switch fabric; Clos network; variable-length packets scheduling; FPGA

10.3969/j.issn.1002-0802.2016.03.021

2015-10-10；

2016-01-22Received date:2015-10-10；Revised date：2016-01-22

TP393; TN915.05

A

1002-0802(2016)03-0361-07