交換結(jié)構(gòu)中的可重構(gòu)緩存機(jī)制

黃慧群，劉勤讓，卜佑軍，張風(fēng)雨

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

可重構(gòu)緩存對應(yīng)的交換結(jié)構(gòu)如圖2(a)。每一個輸出端口的緩存隊(duì)列均包括緩存調(diào)度、基礎(chǔ)緩存以及輸出控制 3個基本單元，公共緩存塊(Gbuffer,global buffer)可被每一個緩存隊(duì)列調(diào)用。其中，緩存調(diào)度決定將待進(jìn)入輸出排隊(duì)隊(duì)列的分組寫入哪個緩存塊，輸出控制則根據(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ù)復(fù)接時的使能。

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

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

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

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

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

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

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

當(dāng)檢測到某個緩存塊變?yōu)闈M時，則判斷是否有其可調(diào)用的空閑塊，若無，則將該分組的后續(xù)數(shù)據(jù)丟棄；若有，則找到優(yōu)先級最高的空閑緩存塊（設(shè)其Buffer_Num=Y）分配給隊(duì)列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ǔ)緩存。

運(yùn)行過程中：當(dāng)檢測到當(dāng)前緩存塊讀空時，若指示鏈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)隊(duì)列獲得最大突發(fā)流量的情形：只有一個輸出端有突發(fā)流量，當(dāng)其基礎(chǔ)緩存以及所有公共緩存塊均滿時達(dá)到最大值

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文在現(xiàn)有的4×4交換系統(tǒng)上實(shí)現(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相等，其輸出隊(duì)列長度為 3個BlockRAM，即54kbit。依據(jù)可重構(gòu)緩存算法升級的交換系統(tǒng)，已應(yīng)用到自主研發(fā)的可重構(gòu)路由器中。為便于比較二者的抗突發(fā)性能，本文設(shè)計(jì)了如下測試方案。

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

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

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

對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，對應(yīng)的目的端口分別為 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)計(jì)數(shù)據(jù)，由于這 3組數(shù)據(jù)流的分組丟失率相同，表中不再區(qū)分各數(shù)據(jù)流。由表可見，容納多端口突發(fā)流量的能力RQ比FQ仍略有改善。

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

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

4 結(jié)束語

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

目前，在路由器緩存區(qū)設(shè)置的問題上，大量研究集中在容量與性能的理論分析，而未有試圖從實(shí)現(xiàn)機(jī)制上減少資源浪費(fèi)來提高系統(tǒng)性能?？芍貥?gòu)緩存機(jī)制從提高資源利用率的角度出發(fā)，在以FPGA實(shí)現(xiàn)的交換結(jié)構(gòu)中引入緩存塊的按需分配思想，打破交換結(jié)構(gòu)中端口對緩存單元的私有獨(dú)占，按各端口的實(shí)際緩存需求量來實(shí)時重構(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].長沙:中南大學(xué),2009.LI C Q. Rsearch on Need for Buffer of Router[D]. Changsha:Central South University,2009.

[4] 樊曉椏. 基于FPGA的網(wǎng)絡(luò)路由器報(bào)文交換算法及實(shí)現(xiàn)[D]. 西安:西北工業(yè)大學(xué), 2007.FAN X Y. Message Exchange Algorithm and Realizaing of Network Router Based On FPGA[D]. Xi’an: Northwestern Polytechnical University, 2007.

[5] 張博,顏金堯.路由器緩存容量的分析[J].中國傳媒大學(xué)學(xué)報(bào)自然科學(xué)版, 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] 張小平,劉振華,趙有健.可擴(kuò)展路由器[J].軟件學(xué)報(bào), 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.