一種星載IP交換機隊列管理器的設計*

王 晶，喬廬峰，陳慶華，鄭 振，李歡歡

(解放軍理工大學 通信工程學院,江蘇 南京 210007)

一種星載IP交換機隊列管理器的設計*

王 晶，喬廬峰，陳慶華，鄭 振，李歡歡

(解放軍理工大學 通信工程學院,江蘇 南京 210007)

針對星載IP交換機中硬件存儲資源使用受限的情況，提出了一種適用于共享存儲交換結構、存儲資源占用少的隊列管理器。通過添加索引的方法，使得所有的單播隊列能夠共享一個指針存儲區(qū)。根據(jù)位圖映射，將組播指針轉化為多個單播指針，即可把組播操作的數(shù)據(jù)流按照單播操作方式寫到相應的邏輯隊列路徑，達到節(jié)約存儲器資源的目的。該隊列管理器通過鏈表數(shù)據(jù)結構的頭部和尾部來控制指針索引的寫入和輸出。最后，在Xilinx的xc6vlx130t FPGA進行了綜合實現(xiàn)，結果顯示，該方案相比基于指針復制的隊列管理器，在8端口的交換機中存儲器資源的使用量要節(jié)約22%以上。

星載IP交換機；隊列管理器；組播；FPGA

0 引 言

由于受到外太空惡劣環(huán)境和航天級器件使用受限的影響，星上交換設備作為衛(wèi)星有效載荷的一部分，其功率消耗、緩存容量和可采用的技術都受到了很大的限制[1]。太空中的空間粒子流對器件的正常工作產生嚴重影響，其中最主要的影響之一是單粒子翻轉問題，即空間粒子流造成的電路邏輯錯誤。采用FPGA進行系統(tǒng)實現(xiàn)時，三模冗余技術是解決單粒子翻轉最主要的方法之一[2]。三模冗余方法在提高電路抗單粒子效應能力的同時，要求一片F(xiàn)PGA的主要資源使用量原則上不能超過總資源量的1/3。這對交換機的硬件資源消耗提出了苛刻的要求。另外，星載IP交換機中可用存儲器也受到了嚴格限制，航天級SRAM、SDRAM和DDR的容量和工作時鐘頻率通常遠低于普通商用級器件。

因此，必須針對其硬件資源使用受限和性能方面的要求，設計出結構簡單、性能良好和可靠性高的星上交換結構。而設計交換結構的一個難點就在于隊列管理器[3](Queue Manager, QM)的設計實現(xiàn)。共享存儲(Shared Memory, SM)交換結構由于具有結構簡單、存儲資源利用率高、低時延的特性[4]，是設計星上交換設備很好的一個選擇。共享存儲交換結構中主流的地址復制隊列(Address Copy Queue，ACQ)需要額外的空間存放復制的地址，會使得QM電路占用過多的存儲資源[5]。

本文提出一種ATQ(Address Transfer Queue)隊列管理器結構，通過添加一個索引存儲區(qū)，配合原有的自由指針隊列(Free Queue, FQ)，使得所有的單播隊列共享一個指針存儲區(qū)，并把組播指針按照位圖映射轉化為多個單播指針以將組播操作轉化成單播操作，這樣就只需一個單獨的組播隊列就可以完成組播操作。通過與當前主流的基于ACQ的QM比較，本文提出的方案存儲資源占用更少，能夠滿足星載IP交換機苛刻的存儲資源要求。

1 基于ACQ的QM結構分析

本文討論基于ACQ的結構并取之作對比。基于ACQ的QM結構框圖如圖1所示。數(shù)據(jù)流進入后根據(jù)單播/組播兩種不同類別的操作，進入到相應的路徑，然后從自由指針存儲區(qū)(FQ_ram)中獲取一個自由指針，該指針就是指向外部共享SRAM的地址[6]。如果是單播請求，則把信元數(shù)據(jù)存儲在外部共享SRAM中緩存起來，指針則根據(jù)隊列號存入相應的隊列控制器(Queue Controller, QC)，QCs的輸出根據(jù)加權輪詢(Weighted Round Robin, WRR)算法[7]實現(xiàn)不同優(yōu)先級的有效調度。如果是組播請求，信元數(shù)據(jù)與單播的數(shù)據(jù)一樣存儲在外部共享SRAM中緩存起來，而組播指針則如圖1所示,通過地址復制電路(Address Copy Circuit, ACC)把指針復制到各個相應的QCs中[8]，然后與單播操作類似，在輸出端取出需要的指針。

在輸出端，對于單播操作，QC中的指針取出后，便根據(jù)該指針向外部共享SRAM取信元數(shù)據(jù)發(fā)送到輸出端口，信元輸出后便把該指針歸還到自由指針隊列中。組播操作時，取出每個組播組的QC中該組播指針時，都從SRAM中取一遍相應的信元數(shù)據(jù)并發(fā)送到對應的輸出端口。當所有組播成員都按照組播指針發(fā)送完其指向的信元數(shù)據(jù)后，才把它歸還到自由指針隊列。

圖1 基于ACQ的QM結構

基于ACQ的QM需要為每個輸出端口建立QC，以用來存儲單播/組播請求的指針，當物理端口數(shù)量很大時，QM也要建立相應數(shù)量的QC來存儲指針。這樣的方式帶來的后果就是會占用過多的存儲資源[9]。文獻[9]在Xilinx的V4sx55 FPGA實現(xiàn)的基于ACQ交換結構在8個端口的情況下的Block RAM/FIFO資源消耗量達到25%，當端口數(shù)量增加到32個端口時，在原有FPGA器件上將無法滿足設計要求。當然，如果換一個存儲量更大的FPGA器件可以解決問題，但隨之而來的問題是，會增加硬件成本，而且當端口數(shù)量再增加時，可能會再次遇到同樣資源不夠用的問題。另一個解決辦法是降低設計電路的資源消耗量，本文提出的方案就是基于該思路，下面將介紹本文提出的隊列管理器。

2 基于ATQ的QM設計

為了克服基于ACQ的QM在特定應用中存儲資源占用過多的問題，本文設計了一種基于ATQ的QM，其整體結構如圖2所示。與基于ACQ的QM不同的是：自由指針不直接建立隊列，索引存儲區(qū)(index_ram)中的索引用于建立隊列，索引指針存儲區(qū)(index_ptr_ram)是以索引為地址，存放的是自由指針；所有的單播隊列共享一個指針存儲區(qū)，所以無需建立多個QCs；組播操作通過位圖映射轉換為單播操作，不再需要ACC模塊，避免了組播操作占用存儲資源過多的問題。

圖2 基于ATQ的QM結構

2.1 ATQ內部隊列操作分析

首先分析單播請求的情況，數(shù)據(jù)流從輸入端進來，信元數(shù)據(jù)存儲在外部共享SRAM中，然后從index_ram中獲取一個索引，同時從FQ_ram獲取一個自由指針，該指針是信元數(shù)據(jù)對應在SRAM中的地址。以獲取的索引為地址，將獲取的自由指針寫入索引指針存儲區(qū)。此時自由指針與索引同步，即與每一個自由指針存儲地址對應著的index_ram中存儲著一個索引。輸出時，根據(jù)索引找到對應的單播隊列，并以索引為地址讀出索引指針存儲區(qū)的自由指針，然后以自由指針為地址取出存儲在SRAM中的信元數(shù)據(jù)，發(fā)送到對應的輸出端口。

組播操作的情況是節(jié)約存儲資源的關鍵所在。圖2中可以看到，本文設計的QM的結構相比圖1中基于ACQ的結構，組播操作做了很大的改變。組播請求時，信元數(shù)據(jù)存儲在外部共享SRAM中，從index_ram中獲取一個索引，同時從FQ_ram獲取一個自由指針，以獲取的索引為地址，將獲取的自由指針添加到index_ptr_ram的鏈表中。此時還需為每次組播操作存儲一個組播計數(shù)器(Multicast Count, MC)[10]，MC值表示當前組播操作要發(fā)送到指定端口的數(shù)量，該值在歸還請求時要用來指定歸還索引的個數(shù)，以確保組播操作的正確性。組播的輸出采用的方式是根據(jù)位圖映射將組播操作按比特位從低位到高位依次轉化為單播操作，位圖映射值中每個為1的比特都需要轉化為1次單播操作，轉化完成后即將該比特置0，直到最后一個為1的比特被置為0。位圖映射值與相應寫入單播隊列號的對應關系如表1所示，其中x表示該比特位不影響映射結果。

表1 位圖映射值與對應寫入單播隊列號

組播操作流程舉例如下，假設位圖映射值為8’b0101_1001，由于位圖映射值的第0比特為1，向index_ram中再獲取一個索引，以它為地址將當前的自由指針寫入索引指針存儲區(qū)，對照表1可知，應該將獲取的索引寫入qnr0隊列鏈表中，此時并把當前位圖映射值置為8’b0101_1000，即把操作完成的那個比特由1置為0。本次操作完成后，跳轉到組播操作開始的狀態(tài)，從低位到高位重復上一步操作，每次要獲取一個新的索引，而自由指針保持不變，最后一次添加索引到qnr6隊列鏈表中，置位圖映射值為8’b0000_0000，位圖映射操作完成。該操作完成后，每個組播隊列成員都獲取了索引，以該索引為地址，組播成員可在指針索引存儲區(qū)中得到相同的自由指針，然后各自以該自由指針為地址從外部SRAM中獲取組播數(shù)據(jù)，發(fā)送到各個組播端口。

歸還請求時，針對單播，索引與自由指針是一起歸還。組播則是先讀取輸入時存儲的MC值，判斷是否為0，若不為0，自由指針暫不歸還，只歸還一個索引，且將MC值減1。然后重新跳轉到歸還請求的狀態(tài)，重復操作，直到判斷出MC值減為0，才能歸還自由指針，歸還自由指針后，此次歸還操作結束。

2.2 數(shù)據(jù)結構操作分析

索引的添加使得所有的隊列能夠共享一個指針存儲區(qū)，本文是通過鏈表來鏈接索引操作的。圖3給出了兩條鏈表邏輯隊列操作過程。存儲區(qū)(ptr_ram)左側存放的是相應的portmap值，位圖映射需要用到該參數(shù)。自由指針不直接建立隊列，而是通過索引來建立，索引鏈表中存儲的是隊列獲取的索引。通過鏈表數(shù)據(jù)結構的頭部(head)和尾部(tail)可以控制索引的寫入和輸出。寫入時，將獲取的索引寫到對應隊列鏈表的tail中，讀出時，從相應隊列鏈表的head處取出要歸還的索引。

圖3 兩條鏈表邏輯隊列

3 仿真結果與分析

本文選用Xilinx的xc6vlx130t FPGA來實現(xiàn)基于ATQ的QM，開發(fā)環(huán)境是Xilinx集成開發(fā)環(huán)境ISE 14.3，核心電路模塊是用Verilog HDL編程實現(xiàn)。仿真工具用的是ModelSim SE 10.0a，下面給出關鍵電路的仿真結果。

3.1 輸入請求仿真與分析

輸入請求時，數(shù)據(jù)統(tǒng)一存入外部共享SRAM，從FQ_ram中獲取自由指針，index_ram中獲取索引。根據(jù)隊列號尋址相應的隊列，將索引加到該隊列鏈表的tail，并將tail指向下一個索引，head值保持不變。圖4是輸入請求時的仿真波形圖，本文仿真了qnr為3、4這兩種單播輸入及qnr為8的組播輸入的情況?？梢钥吹?，輸入請求時，自由指針與索引是同步的，并且每次請求都會在相應的地址寫入MC值，qnr為3、4時，由于是單播，MC寫入值保持為0。qnr為8時，組播操作，MC值一次寫入值為3，另一次寫入值為2，存儲的MC值在歸還請求操作流程中要用到。

圖4 輸入請求仿真波形

3.2 輸出與歸還請求仿真與分析

輸出請求時，根據(jù)隊列號尋址相應的隊列鏈表，然后取出需要的索引、自由指針。當前自由指針操作結束，后級電路釋放該指針后會給ATQ歸還請求，即將操作完成的自由指針寫入FQ_ram，給后續(xù)操作再用，充分利用存儲資源。圖5是輸出請求的仿真波形，圖6給出了歸還請求的仿真波形。

圖5 輸出請求仿真波形

圖6 歸還請求仿真波形

輸出操作是從相應隊列鏈表的head處開始，qnr為3時，head從index_ram的0開始，每次給完請求應答后，head值加1，qnr3操作結束后，head值增加到9，則下一個隊列qnr4的head從9開始，同理qnr為8的時候，head值從17開始,對應的在每次請求應答后加1。head值的遞增是在縮短當前隊列鏈表的長度，后級電路給歸還請求后，這些被釋放的索引、自由指針將會在后續(xù)的輸入請求時再次使用。有一點需要注意的是，組播操作的歸還請求時，先歸還索引，然后判斷MC值是否為0，為0才能歸還自由指針，否則只能歸還索引并將MC值減1。圖6中可以看到，MC值減為2,1,0時，index_ram寫操作執(zhí)行了3次，F(xiàn)Q_ram的寫操作只在MC值為0時執(zhí)行了1次。

3.3 綜合結果對比分析

本文對基于ACQ和基于ATQ兩種模型在Xilinx的xc6vlx130t FPGA進行了實現(xiàn)，使用ISE14.3自帶的綜合工具XST分別進行了綜合，得出了綜合結果。表2是兩種模型綜合結果報告對比，表2中，基于ACQ的QM共占用了2 920個Slice Registers、2 983個Slice LUTs和70個Block RAM/FIFO，而對應本文設計的基于ATQ的QM模型共占用量分別是1 199個、1 625個、13個。顯然，基于ATQ的QM的關鍵源消耗量都低于基于ACQ的QM，特別是Block RAM/FIFO，使用量要少22%。因此，對于海量端口的網(wǎng)絡應用，本文設計的基于ATQ的QM有很大的優(yōu)勢。

表2 兩種模型綜合結果報告對比

兩種結構模型都是實現(xiàn)了8個端口的情況，基于ACQ的結構Block RAM/FIFO資源消耗量達到26%，當端口數(shù)量增加4倍即32個端口時，基于ACQ的QM將無法滿足設計要求，而本文設計的方案，不但能滿足設計要求，而且還有一定的裕量，為今后電路的擴展提供了條件。

4 結 語

本文針對星載IP交換機資源受限的情況，設計實現(xiàn)了一種基于ATQ的QM，分析了它的結構原理及實現(xiàn)方法。整個電路在Xilinx的xc6vlx130t FPGA進行了實現(xiàn)。通過與基于傳統(tǒng)ACQ的QM作對比，充分體現(xiàn)該方案在節(jié)約資源消耗方面的優(yōu)勢，關鍵資源消耗要少22%以上。在星上交換設備中，本文設計實現(xiàn)的基于ATQ的QM是一個非常好的選擇。我們將在未來的工作中搭建實驗平臺，運用該平臺，分析并改善本文提出方案的性能。

[1] Ors T,Sun Z, Evans B G. A Meshed VSAT Satellite Network Architecture Using an On-Board ATM Swith[C]// IEEE International Conference on Performance, Computing, and Communications [Piscataway:IEEE,1997.208-214.

[2] THO Le-Ngoe．Switching for IP-based Multimedia Satellite Communications[J]. IEEE Journal on Selected Areas in Communications，22(3)，2004(4)：318-322.

[3] 高仲合, 田碩. 一種基于負載的公平性主動隊列管理算法[J]. 通信技術, 2011, 44(11): 94-96. GAO Zhong-he， TIAN Shuo.Load-based Fair Active Queue Management Algorithm[J]. Communications Technology,2011,44(11):94-96.

[4] ZHANG Qi, Woods Roger, Marshall Alan. Design and Implementation of a Flexible Queue Manager for Next Generation Networks[C]// 2011 Conference Record of the Forty Fifth Asilomar Conference on IEEE. Signals, Systems and Computers (ASILOMAR),2011:498-502.

[5] Dong Z, Rojas-Cessa R. Throughput Analysis of Shared-Memory Crosspoint Buffered Packet Switches[J]. Communications Iet, 2012, 6(9):1045-1053.

[6] ZHENG Ya-song, XU Yuan-chao, MENG Hai-bo, et al. Optimizing Mapreduce with Low Memory Requirements for Shared-Memory Systems[C]// 2014 15th IEEE/ ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD)IEEE Computer Society,2014:1-6.

[7] Heisswolf J, Konig R, Becker J. A Scalable NoC Router Design Providing QoS Support Using Weighted Round Robin Scheduling[C]// Proceedings of the 2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications IEEE Computer Society,2012:625-632.

[8] Ejlali Mina, Saidi Hossein, Montazeri Mohammad Ali, et al. Design and Implementation of a Shared Memory Switch Fabric[C]// 2012 Sixth International Symposium on IEEE, Telecommunications (IST), 2012:721-727.

[9] 沈澤民，喬廬峰，陳慶華等. 一種多優(yōu)先級變長調度星載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.

[10] LU Qing-mei, HE Li-lin. Research on the Routing Algorithm based Greedy Multicast Algorithm[C]// 2010 International Conference on Computer Application and System Modeling. 2010: 437-439.

Design of Queue Manager in Satellite-Borne IP Switch

WANG Jing，QIAO Lu-feng，CHEN Qing-hua，ZHENG Zhen，LI Huan-huan

(College of Communications Engineering, PLA University of Science and Technology, Nanjing Jiangsu 210007, China)

Aiming at the limited hardware storage resources in the satellite-borne IP switch, a queue manager suitable for shared memory switch structure and with less occupation of storage resources is proposed.Through adding index, all the unicastqueues could share one pointer memory block. Based on bitmap, multicast pointer is translated into several unicasts, that is,the data stream of multicast is written into corresponding logic queue in accordance with the unicast operating mode, so as to save the storage resource. The queue manager controls the write-in and output of index pointer via the head and tail of linked-list data structure.Finally the synthesis and implementation are realized on Xilinx′s xc6vlx130t FPGA, and experiment indicates that, compared with queue manager based on pointer duplication,the proposed scheme could reduce more than 22% of the storage resource in interchanger.

satellite onborad IP switch; queen manager; multicast; FPGA

10.3969/j.issn.1002-0802.2015.10.020

2015-05-17；

2015-09-02 Received date:2015-05-17；Revised date：2015-09-02

TP393.03

A

1002-0802(2015)10-1196-06

王 晶(1989—)，男，碩士研究生，主要研究方向為高性能交換機和路由器相關研究工作；

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

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

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

李歡歡(1990—)，女，碩士研究生，主要研究方向為文本相關的說話人識別。