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

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

2. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

1 引言

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

圖1 輸出排隊交換結(jié)構(gòu)

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

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

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

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

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

本文后面章節(jié)將基于可重構(gòu)緩存的基本原理，深入探討關(guān)鍵技術(shù)，最后給出具體實現(xiàn)方案以及性能分析和實驗驗證結(jié)論。

2 可重構(gòu)緩存及調(diào)度算法

2.1 可重構(gòu)緩存交換結(jié)構(gòu)

基于 FPGA實現(xiàn)的交換結(jié)構(gòu)中，緩存區(qū)由FPGA內(nèi)部的BlockRAM組成，Xilinx公司的FPGA產(chǎn)品基本存儲單元均為 18kbit的 RAM[11]，Altera公司FPGA內(nèi)部的存儲單元則主要是4kbit或者512 bit的RAM塊。為提高抗突發(fā)能力，每個緩存區(qū)均需多個BlockRAM，該存儲區(qū)大小是固定的。

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

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

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

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

2.2 緩存重構(gòu)調(diào)度算法

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

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

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

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

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

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

當檢測到某個緩存塊變?yōu)闈M時，則判斷是否有其可調(diào)用的空閑塊，若無，則將該分組的后續(xù)數(shù)據(jù)丟棄；若有，則找到優(yōu)先級最高的空閑緩存塊（設(shè)其Buffer_Num=Y）分配給隊列X，寫入分組數(shù)據(jù)；同時，向該X端口的緩存結(jié)構(gòu)指示鏈FIFO中寫入Y，并更新位置指針，使得LSP_X=Y。

在接口數(shù)據(jù)選擇輸出端，則根據(jù)緩存結(jié)構(gòu)指示鏈buffer來控制讀順序。

初始狀態(tài)：等待指示鏈FIFO變?yōu)榉强諘r，并從中讀一個數(shù)，即-1，并讀基礎(chǔ)緩存。

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

2.3 抗突發(fā)性能與緩存區(qū)容量的關(guān)系

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

設(shè)系統(tǒng)中每個可調(diào)用的緩存塊的大小一致均為C bit，則緩存容量可用緩存塊的個數(shù)來表示。設(shè)每個基礎(chǔ)緩存被分配K個塊，公共緩存被分配L個塊，則系統(tǒng)所用總存儲塊為S = M K + L 。

考察以下3種情形。

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

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

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

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

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

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

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

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

因?qū)嶋H工程實現(xiàn)需要，本文選取K=1。

3 性能分析以及算法優(yōu)化

3.1 算法實現(xiàn)以及硬件資源分析

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

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

若實現(xiàn)一個4×4的重構(gòu)緩存隊列(RQ, reconfigurable queue)交換系統(tǒng)，則需要的FPGA資源總數(shù)為。

1) 輸出控制部分。4路輸出緩存，每一路占用的資源為：一個 18bit的 BlockRAM，用作基礎(chǔ)緩存區(qū)，一個分布式RAM用作接口緩存區(qū)結(jié)構(gòu)指示buffer；以及一個數(shù)據(jù)復接電路。

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

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

3.2 性能測試與算法優(yōu)化

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

采用安捷倫測試儀作數(shù)據(jù)源，4個端口卡Port1～Port4的輸出連接路由器4個線卡的輸入，交換系統(tǒng)的4個輸出則分別送回給4個端口卡，實現(xiàn)閉環(huán)。測試儀各端口設(shè)置如下。

表1 Port1 4個突發(fā)數(shù)據(jù)流的參數(shù)設(shè)置

表2 單端口突發(fā)流量時的分組丟失率統(tǒng)計

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

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

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

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

表3 系統(tǒng)容納多端口突發(fā)流量時的分組丟失率統(tǒng)計

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

4 結(jié)束語

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

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

[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] 扈紅超.分組交換網(wǎng)交換結(jié)構(gòu)與調(diào)度策略關(guān)鍵技術(shù)研究[D].鄭州:國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,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的網(wǎng)絡路由器報文交換算法及實現(xiàn)[D]. 西安:西北工業(yè)大學, 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.