交換結構中的可重構緩存機制

黃慧群，劉勤讓，卜佑軍，張風雨

（1. 解放軍信息工程大學 信息工程學院，河南 鄭州 450002;

2. 國家數字交換系統工程技術研究中心，河南 鄭州 450002）

1 引言

基于分組的交換系統是實現路由器交換和大規模系統擴展的重要單元，交換結構按照排隊緩存所在位置的不同，可分為輸入排隊（IQ，input queue）和輸出排隊（OQ，output queue）。輸出排隊交換結構中，到達各輸入端口的分組直接經由交換單元到達輸出端口，并在每個輸出端口進行排隊，如圖1所示。輸入排隊則將到達分組在輸入端口進行排隊和緩存，經調度后由交換矩陣交換到系統輸出端口[1,2]。文獻[3]從分組丟失率、鏈路速率等性能需求入手，研究了核心路由器的緩存需求問題，并給出了核心路由器緩存設置法則。文獻[4]重點針對路由器內部交換中采用簡單FIFO算法產生的線頭（HOL, head of line）阻塞現象，結合虛擬輸出隊列（VOQ, virtual output queue）機制，給出了一種消除數據轉發過程中出現線頭阻塞的iSLIP改進算法。文獻[5]基于 TCP協議模型對經驗法則、斯坦福緩存法則和基于分組丟失率的緩存法則等各種緩存容量設計研究成果進行了比較分析。文獻[6～10]給出了可重構路由器軟硬件模型、ForCES協議及體系結構方面的介紹。

圖1 輸出排隊交換結構

大量研究集中在路由器對緩存區容量設置的理論需求上。可重構路由器則注重研究和實現有限資源高效利用的方法，也是可重構緩存機制研究的出發點。該機制在交換結構緩存隊列中引入按需分配思想，將隊列中閑置存儲單元分配給有較大突發流量、需要更多緩存的端口，避免系統有大量緩存區空閑時仍有一些端口因較大突發流量而大量分組丟失。該機制可普遍適用于輸入排隊和輸出排隊2種交換結構，為使問題分析更加直觀，以輸出排隊的交換結構為例。

從任一個輸入端口進入交換矩陣的數據分組，其輸出方向可能是輸出端口1～m中的任意一個。設輸出端口i的帶寬是iP，當輸出方向為i的輸入分組的總和小于iP時，所有該類數據分組均可無阻塞地送出；但是，事實上，由于網絡中數據分組的隨機性，目的端口為i的分組的總流量在某些時間段可能會大于其輸出帶寬。此時，則需要將未能及時送出的分組緩存在輸出隊列中。

如果目的端口為 i的數據流持續大于其輸出帶寬，則輸出隊列中緩存數據持續增長，當超過其隊列長度時，最終分組丟失無法避免。但對于突發的短時流量，只要在一個時間段內需求總帶寬小于iP，輸出緩存將暫時未能送出的數據緩存，則有效地避免了分組丟失。顯然，輸出緩存區的大小與其抗突發流量的能力成正比，即緩存區越大，抗突發能力越強。同時，由于突發流量的發生不局限于每一個輸出端口，因而，只好將每一個緩存區均設置為一個較大的值，以此來防御可能發生的突發流量。

但是，事實上，相對于輸出到某一個端口的突發流量，一個交換矩陣輸入的總流量是固定的，則輸出到所有端口 i的流量的總和等于輸入流量（且不大于輸入帶寬），這樣，當某一個輸出端 Pi有突發大流量時，相對地，送到其他輸出端Pj( j ≠i)的流量就會變少，其需要的緩存區也就較小，而緩存區域是事先設置好的，這樣， Pi端口之外的其他緩存區大部分處于閑置狀態。由于這個 Pi是隨機的，不可能預知從而減小其他輸出端緩存的容量，系統設計時就必須為每一個輸出端均設置一個較大的緩存區，從而造成巨大的存儲資源浪費。

為削減這些閑置存儲單元，本文為交換系統提出一種可重構緩存，首先將固定分配給每個輸出端口的存儲單元“公共化”，然后，根據系統實際流量特征以及相應的需求，將公共存儲單元按需分配，實現了存儲單元的實時重構，避免在大量緩存區空閑時仍有一些端口因較大突發流量而大量分組丟失，從而大大提升了資源利用率。

本文后面章節將基于可重構緩存的基本原理，深入探討關鍵技術，最后給出具體實現方案以及性能分析和實驗驗證結論。

2 可重構緩存及調度算法

2.1 可重構緩存交換結構

基于 FPGA實現的交換結構中，緩存區由FPGA內部的BlockRAM組成，Xilinx公司的FPGA產品基本存儲單元均為 18kbit的 RAM[11]，Altera公司FPGA內部的存儲單元則主要是4kbit或者512 bit的RAM塊。為提高抗突發能力，每個緩存區均需多個BlockRAM，該存儲區大小是固定的。

可重構緩存的目的是在同等抗突發能力的前提下，盡量減少緩存隊列實際所需的存儲資源數目，節省FPGA內部寶貴的存儲資源。其基本指導思想是打破存儲區依不同端口而專門設置的私有模式，通過引入大容量的公共緩存實現主要存儲資源的按需分配。具體方法是，為每個端口設置一個較小的基礎緩存，該緩存主要用于完成數據處理、輸出控制等功能，屬于各端口的“私有緩存”；同時將大量的存儲資源塊設置為公共緩存區，當流向某一個輸出接口的突發流量超過其基礎緩存時，向公共存儲區申請得到更多緩存資源。

該機制的合理性在于，由于單播交換系統輸入的總流量不大于其總帶寬，當某個或者某些輸出端口有大量突發流量時，其他端口流量則較小，只有那些具有突發流量的端口申請到公共緩存區，流量較小的端口則不需要大緩存區，以此實現緩存區的按需分配，使得緩存資源得以高效利用。

可重構緩存對應的交換結構如圖2(a)。每一個輸出端口的緩存隊列均包括緩存調度、基礎緩存以及輸出控制 3個基本單元，公共緩存塊(Gbuffer,global buffer)可被每一個緩存隊列調用。其中，緩存調度決定將待進入輸出排隊隊列的分組寫入哪個緩存塊，輸出控制則根據緩存重構的結構來控制讀緩存順序并將數據選擇輸出。

如圖 2(b)所示，每個基礎緩存(Bbuffer, basic buffer)由2部分組成，即：數據緩存區以及緩存結構指示鏈FIFO，前者為本端口的數據緩存區，后者則指明本端口的輸出緩存順序地由哪些緩存塊組成，用作數據輸出時的讀順序控制以及數據復接時的使能。

2.2 緩存重構調度算法

緩存調度是可重構緩存的核心控制單元，本文給出一種對輸出端口公平、對公共緩存塊預設優先級的緩存重構調度算法。一個重構的緩存隊列（也可視作一個邏輯緩存隊列）由1個基礎緩存和多個公共緩存塊組成，當其中2個以上可選擇調用時，選擇最高優先級緩存塊。所有緩存塊的優先級預先設定，并應遵循以下2條原則：

1) 與公共緩存相比，基礎緩存總是具有高優先級，以使盡量多的公共緩存塊用于需要的地方；

2) 公共緩存塊的優先級，可按照易于硬件實現的升序或者降序來指定。

為算法描述方便，對于任意一個邏輯緩存隊列X，定義其本地位置指針LSP_X為：已寫入最新數據所調用的緩存塊的編號。位置指針可能指向本地基礎緩存或者所有公共緩存，因而二者統一編號，記為Buffer_Num，以-1表示本地基礎緩存，0～( 1)n- 為公共緩存編號，其中，n為公共緩存塊的個數。預設優先級的緩存重構調度算法如下。初始時，LSP_X設為-1。

運行過程中，每來一個新的目的端口為X的分組，則：

首先讀取邏輯隊列X的當前位置指針LSP_X，并判斷該緩存是否已滿，若未滿，則將新到來數據寫入；同時，判斷LSP_X指向的緩存塊是否為空，若是，則向緩存指示鏈FIFO中寫入LSP_X，否則不變。

當檢測到某個緩存塊變為滿時，則判斷是否有其可調用的空閑塊，若無，則將該分組的后續數據丟棄；若有，則找到優先級最高的空閑緩存塊（設其Buffer_Num=Y）分配給隊列X，寫入分組數據；同時，向該X端口的緩存結構指示鏈FIFO中寫入Y，并更新位置指針，使得LSP_X=Y。

在接口數據選擇輸出端，則根據緩存結構指示鏈buffer來控制讀順序。

初始狀態：等待指示鏈FIFO變為非空時，并從中讀一個數，即-1，并讀基礎緩存。

運行過程中：當檢測到當前緩存塊讀空時，若指示鏈buffer未空，則從指示鏈FIFO中讀取下一個緩存指示，然后根據該指示使能相關存儲塊的讀控制，并將該存儲塊的輸出送出。

2.3 抗突發性能與緩存區容量的關系

每個端口的輸出帶寬相等，均為P，輸入端口總帶寬為F。目的端口為i的流量速度記為 Fi。并定義端口i的突發流量BFi為一段時間Δt內超出輸出端口i輸出帶寬的流量的總和，記為則系統在Δt內的突發流量為

設系統中每個可調用的緩存塊的大小一致均為C bit，則緩存容量可用緩存塊的個數來表示。設每個基礎緩存被分配K個塊，公共緩存被分配L個塊，則系統所用總存儲塊為S = M K + L 。

考察以下3種情形。

1) 單個輸出端口的重構隊列獲得最大突發流量的情形：只有一個輸出端有突發流量，當其基礎緩存以及所有公共緩存塊均滿時達到最大值

2）系統容納最多突發流量的情形：只有一個輸出端流量小于輸出帶寬 P，其他 M -1個端口均有大于P的流量，則當這 M - 1個端口的基礎緩存以及所有公共緩存塊均為滿時，系統容納突發流量達到最大值，此時

3) 系統可容納突發流量最少的情形：考慮某一時刻t開始，有流向端口j的突發流量Flow_j，并且此時所有公共緩存塊均已被t時刻之前的突發流量占用，則Flow_j進入基礎緩存區Bbuffer_j等待，在Bbuffer_j變為滿之后，若還沒有可用的Gbuffer，則后續流量將被丟棄直到有被釋放的Gbuffer為止。t時刻之前被占用的 Gbuffer中，最先被釋放的是對應的 Fi在時刻t被調用的存儲塊。

因： F1+ F2+, … ,+ Fm≤F =MP

等式右邊 M -1項中最大的那一項將首先釋放緩存塊從而使得Flow_j獲得可用緩存，但最壞情況下，這 M -1項均相等，即有

且t時刻所有端口 i = { i|i ≠ j,i ∈ [1 ,M ]}的輸出隊列當前正輸出的是其基礎緩存區的數據，則為獲得第一個空閑 GBuffer，Flow_j在基礎緩存滿之后需要等待的時間為max(Twait)

在max(Twait)到來之前的一刻，系統獲得最少可容納突發流量

考察式(1)、式(2)和式(4)，K越小則突發流量容納性能越強；根據式(3)，K越小，最壞情形下分組丟失時間則越短。當K達到最大值K = S M時，即為不使用重構緩存的情況。

因實際工程實現需要，本文選取K=1。

3 性能分析以及算法優化

3.1 算法實現以及硬件資源分析

以Xilinx公司的FPGA產品系列為例，其基本存儲單元為BlockRAM，每一個均為18kbit。通過上述分析可知，基礎緩存區只要不小于一個公共緩存塊的容量，其本身的大小對于抗突發流量性能無影響，因而基礎緩存只需一個BlockRAM即可。

輸出接口緩存區結構指示buffer只需要按順序記錄當前該接口占用的公共存儲單元序號或者自有基礎緩存，若公共存儲單元為 N個，則需區分N+ 1個緩存塊，需log(N + 1 )bit，并且其深度不超過 N + 1 ，因而容量為(N + 1 )log(N + 1 )bit，當 N =15時，該值為64bit，可以用分布式RAM來實現。

若實現一個4×4的重構緩存隊列(RQ, reconfigurable queue)交換系統，則需要的FPGA資源總數為。

1) 輸出控制部分。4路輸出緩存，每一路占用的資源為：一個 18bit的 BlockRAM，用作基礎緩存區，一個分布式RAM用作接口緩存區結構指示buffer；以及一個數據復接電路。

2) 緩存調度部分，具體到FPGA實現中。事實上是N個公共緩存塊以及4個基礎緩存塊的寫控制電路。

本文在現有的4×4交換系統上實現了上述可重構的緩存。綜合結果顯示，上述邏輯電路占用的資源很有限，不足1 000個LUT，而這些資源卻是FPGA所富余的。FPGA內緊張的存儲資源，卻可用于提高系統性能。本系統中，設置的公共緩存塊個數為8。

3.2 性能測試與算法優化

使用固定緩存的交換系統FQ(fixed queue)，所使用緩存塊總數與 RQ相等，其輸出隊列長度為 3個BlockRAM，即54kbit。依據可重構緩存算法升級的交換系統，已應用到自主研發的可重構路由器中。為便于比較二者的抗突發性能，本文設計了如下測試方案。

采用安捷倫測試儀作數據源，4個端口卡Port1～Port4的輸出連接路由器4個線卡的輸入，交換系統的4個輸出則分別送回給4個端口卡，實現閉環。測試儀各端口設置如下。

表1 Port1 4個突發數據流的參數設置

表2 單端口突發流量時的分組丟失率統計

對Port1，設置6個突發數據流，參數設置如表1所示。各數據流的五元組均不相同，并通過路由器對轉發表的配置來規定其目的輸出端口。突發流的模式為周期性突發，分組長為固定的128byte， 突發長度以及分組速率設置如表1所示。

對于 Port2～Port4，分別設置數據流 Flow1～Flow3，對應的目的端口分別為 port2～Port4，分組長均為均勻分布，帶寬均為90%。

表2反映了系統容納單端口突發流量的能力對比。在flow1～flow3同時發送的條件下，表中序號1～4分別表示突發流量為Bflow1～Bflow4的情形。與FQ相比，重構緩存的交換系統，容納單端口突發流量的能力大大增加。

將Bflow2和Bflow3設置為與Bflow1相同，同時發送 flow1～flow3以及 Bflow1～Bflow3，即3個端口均有突發流量時的分組丟失率如表3所示。表3分別給出了突發長度為40個分組和50個分組時的統計數據，由于這 3組數據流的分組丟失率相同，表中不再區分各數據流。由表可見，容納多端口突發流量的能力RQ比FQ仍略有改善。

表3 系統容納多端口突發流量時的分組丟失率統計

由于存儲單元數目畢竟是有限的，當超過其存儲能力時分組丟失率將瞬時大大增加，造成鏈路的不穩定。

4 結束語

通常，交換系統通過增加輸出緩存隊列容量的方式來獲得更好的容納突發流量性能，為每個輸出隊列設置一個固定的大緩存區將耗費大量寶貴的存儲資源。然而，由于系統輸入總帶寬有限，在某些端口有突發流量需要大量緩存、并因緩存不足而大量分組丟失時，另外那些端口則流量不足，設定的緩存處于閑置狀態，造成嚴重的資源浪費。

目前，在路由器緩存區設置的問題上，大量研究集中在容量與性能的理論分析，而未有試圖從實現機制上減少資源浪費來提高系統性能。可重構緩存機制從提高資源利用率的角度出發，在以FPGA實現的交換結構中引入緩存塊的按需分配思想，打破交換結構中端口對緩存單元的私有獨占，按各端口的實際緩存需求量來實時重構各緩存區大小，使FPGA中有限的緩存資源得以充分利用，避免在有緩存區空閑時仍有一些端口因較大突發流量而大量分組丟失。采用可重構緩存技術的交換系統，為獲得同樣的抗突發流量性能需要的存儲單元數目大大下降，或者說，同樣數目的存儲單元可獲得更好的抗突發流量性能。

[1] KAROL M J, HLUCHYJ M G, MORGAN S P. Input versus output queuing on a space-division packet switch[J]. IEEE Trans Com, 1987,35(12): 1347-1356.

[2] 扈紅超.分組交換網交換結構與調度策略關鍵技術研究[D].鄭州:國家數字交換系統工程技術研究中心,2010.HU H C. Key Technology Research on Swith Fabric and Scheduling Policy of Packet Switching Network[D]. Zhengzhou: China National Digital Switching System Engineering & Technological R&D Center,2010.

[3] 李春泉. 路由器緩存需求的研究[D].長沙:中南大學,2009.LI C Q. Rsearch on Need for Buffer of Router[D]. Changsha:Central South University,2009.

[4] 樊曉椏. 基于FPGA的網絡路由器報文交換算法及實現[D]. 西安:西北工業大學, 2007.FAN X Y. Message Exchange Algorithm and Realizaing of Network Router Based On FPGA[D]. Xi’an: Northwestern Polytechnical University, 2007.

[5] 張博,顏金堯.路由器緩存容量的分析[J].中國傳媒大學學報自然科學版, 2009, 16(4):44-50.ZHANG B, YAN J Y. Analysis and study on router buffer sizeing[J].Journal of Communication University of China Science and Technology, 2009, 16(4):44-50.

[6] 張小平,劉振華,趙有健.可擴展路由器[J].軟件學報, 2008, 19(2):1452-1464.ZHANG X P, LIU Z H, ZHAO Y J. Scalable router[J]. Journal of Software, 2008, 19(2): 1452-1464.

[7] WANG W M, LIGANG D, BIN Z. Analysis and implementation of an open programmable router based on forwarding and control elements separation[J]. Journal of Computing Science and Technology, 2008,23(5): 769-779.

[8] FERREIRA R, LOURE M, BECK A C, et al. A low cost and adaptable routing network for reconfigurable systems[A]. IPDPS 2009[C]. Rome,Italy, 2009. 1-8.

[9] YUAN F M, DONG L G, LI C H. Service mapping in open and reconfigurable routing and switch node[A]. Proc of Computer Science and Information Technology (ICCSIT). 2010 3rd IEEE International Conference[C]. Chengdu, China, 2010. 199-203.

[10] ZHANG L, ESTRIN D, BURKE J, et al. Named Data Networking(NDN) Project[R]. Research Techmcal Report, 2010.

[11] Virtex-5 family overview[EB/OL]. http://www.xilinx.com/support/documentation/ data_sheets/ds100.pdf.