路由器緩存管理算法之比較研究

摘要:緩存管理是高性能路由器需要解決的技術難題之一，一個好的緩存管理算法可提高路由器的緩存資源利用率并降低分組丟失率#65377;簡要介紹了路由器中緩存管理的發展過程，列舉了緩存管理一些最主流的算法，并對它們的性質#65380;優缺點作了較為深刻的比較研究#65377;最后利用試驗仿真對四種緩存管理算法進行了緩存利用率和分組丟失率方面的評價，并對緩存管理算法的發展作了展望#65377;

關鍵詞:緩存管理算法; 靜態閾值策略; 推出法策略; 動態策略; 多優先級策略

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2007)04-0307-04

網絡應用和通信技術的飛速發展，將互聯網上的核心設備——路由器推到了網絡技術的焦點位置，路由器的性能制約著互聯網的發展#65377;如何使路由器的轉發速率跟上底層傳輸鏈路的速率，從而滿足Internet的發展需求，是路由器需要解決的主要技術問題#65377;近年來在路由器體系結構和內部的交換結構方面的研究均已取得了較大的突破#65377;隨著多媒體數據流需求迅速增長，緩存管理成為制約路由器尤其是高性能路由器進一步發展的瓶頸#65377;

基本的緩存管理算法是分配給每個傳輸流一定數量的緩存空間，當該傳輸流的分組用盡了分配的空間后，它的新到達分組將被丟棄#65377;更復雜的緩存管理方法是為分組指定優先級，將緩存中的低優先級分組丟棄騰出空間給剛到達的高優先級分組使用^[1]#65377;緩存管理技術和分組調度技術是分組交換設備控制資源的兩種主要機制#65377;本文主要介紹幾種常用的緩存管理算法，通過模擬仿真對多種算法的性能加以分析比較，為尋求更好的緩存管理算法指明了方向#65377;

1緩存管理算法的發展概況

1.1緩存管理模型與假設

緩存管理是基于共享緩存交換結構的，緩存管理在其中的模型如圖1所示#65377;一般假設整個緩存空間是M，由N個端口共享使用#65377;有些緩存算法將共享的緩存劃分成N部分，大小分別為mi，i=1，2，…，N，則有∑Ni=1mi=M#65377;

根據排隊論知識，可以將緩存管理看做服務模型，每個端口分組到達的平均速率是λi，端口輸出的速率是μi，若用M/M/1服務模型，分組到達速率為λi的隊列的平均忙期為1/(1-λi)#65377;如果使用Qi(t)表示t時刻輸出端口i的隊列長度，那么所有隊列長度總和為Q(t)=∑Ni=1Qi(t)#65377;實際網絡中有不同類型的傳輸流，它們的優先級不同，可以假設到達的每個端口的分組有P個優先級，分別為0(級別最高)，…，P-1(級別最低)#65377;定義QPi(t)為時刻t端口i的優先級為P的分組數量，P=0，…，P-1;那么端口i所有優先級隊列長度和為Qi(t)=∑p-1pQPi(t)，各個端口優先級為P的分組所占緩存數量總和QP(t)=∑Ni=1QPi(t)，系統中所有隊列長度為Q(t)=∑ni=1∑p-1p=0QPi(t)#65377;顯然以上的Q(t)≤M#65377;

1.2緩存管理算法

路由器緩存管理策略可分為靜態閾值策略(Static Threshold，ST)#65380;PushOut策略(PO)#65380;動態閾值策略(Dynamic Threshold，DT)及多優先級的緩存管理策略#65377;

1.2.1靜態閾值策略

靜態閾值策略在20世紀70年代后期成為研究熱點^[2]#65377;它包括完全分占#65380;完全共享#65380;最大隊列長度共享#65380;最小分配共享和最大隊列最小分配共享方案#65377;

(1)完全共享與分占#65377;完全共享(Complete Sharing，CS)和完全分占(Complete Partitioning，CP)兩個方案是最簡方案#65377;在CS中每個端口共享整個緩存空間M，如果空余緩存，剛到達的分組就可以被接收#65377;CP方案則相反，全部緩存空間M始終劃分給N個端口，為每個端口分配的緩存之和等于總的緩存，實際上CP并沒有提供共享#65377;在適當的均衡傳輸負載條件下CS丟失率低#65377;也就是說，為了實現一個給定的丟失率，CS使用的緩存空間比CP更少#65377;這也是共享內存結構在交換系統中很流行的重要原因#65377;在不均衡負載條件下CP中各個端口的緩存完全分立，可以隔離不同負載端口的相互影響#65377;它們的缺點也很明顯:CP會浪費緩存資源，因為當端口處于不活躍狀態(端口排隊分組小于某個值時的狀態)時，分配給它的緩存也不能為活躍的端口使用，降低了緩存使用效率;CS的公平性較差，若某個端口的工作負載(到達端口傳輸的分組數量)很重，那么它將占用絕大部分緩存空間，這對于其他端口來說是不公平的#65377;

(2)緩存共享的限制與保護#65377;

為了獲得共享緩存的優勢，同時又避免重負載鏈路獨占緩存的情況，有必要進行有限制的緩存共享，這就是所謂的最大隊列長度共享方案(Sharing with Maximum Queue Lengths，SMXQ)#65377;該方案就是對每個端口分配的緩存數量引入一個最大限制(所有限制值的和可以大于整個共享內存空間)，以限制各個隊列的長度#65377;雖然SMXQ限制了各個隊列的長度，但是當活躍端口較多時，仍會占用全部緩存#65377;另外，該方案沒有解決如何在共享緩存環境中為不同優先級傳輸流保證服務#65377;為了解決這一問題，采用了最小內存分配共享方案(Sharing with a Minimum Allocation，SMA)，為端口預留一定數量的緩存#65377;將兩者結合起來就是最大隊列長度最小內存分配共享(SMQMA)方案，端口可以擁有一個最小值的分配空間，同時每個端口的隊列長度都受到限制#65377;Cisco的Lightstream1010交換機就使用了這種緩存管理策略^[3]#65377;

1.2.2PushOut策略

Thareja和Agrawala^[4]提出了延遲決定策略(Delayed Resolution Policy，DRP)#65377;DRP直到緩存空間沒有空余時才決定是否丟棄分組，丟棄的對象可能是剛到達的分組也可能是已接收到緩存中的分組，這由緩存占用狀態或不同的優先級決定#65377;文獻[5]提出了按要求丟棄(Drop on Demand，DoD)，在緩存滿時丟棄緩存中隊列最長的分組#65377;這兩種策略都是將已接收的分組從緩存中刪除，可以稱為PushOut策略#65377;

在多輸出端口共享緩存結構中，PO的性能是非常出色的#65377;首先，它是公平的，可以縮短長隊列允許短隊列增長;其次，它不會在緩存有空余時就丟棄分組，可以充分利用緩存空間，提高整體吞吐率;并且它也是自適應的，能根據當前的傳輸情況變化#65377;下面介紹兩種最典型的PO策略#65377; (1)閾值PushOut#65377;不同類型的傳輸流有不同的QoS需求，需要提供不同優先級的傳輸服務，為此文獻[6]提出了虛擬劃分完全共享#65377;它與閾值PushOut(PO with Threshold，POT)基本思想一致#65377;POT將緩存虛擬劃分成N個部分，對應N個端口#65377;當緩存不滿時，到達的分組都接收#65377;當緩存滿時有兩種可能:①如果到達的分組類型如i使用的空間小于分配的空間mi，那么緩存中至少有一種類型的分組超過其分配空間，如mj#65377;此時從類型j隊列中刪除一個分組，接收這個類型為i的分組#65377;②如果新到達的分組對應類型的隊列超過了其分配空間，就丟棄該分組#65377;可見在緩存未滿面時POT的操作同CS;在重負載條件下則趨向CP管理#65377;因此，POT能夠適應網絡傳輸負載的變化#65377;

在各種策略中，POT的傳輸性能是最佳的#65377;假設分組到達是泊松過程#65380;端口服務時間呈指數分布，可以證明POT具有最低的分組丟失率^[12]#65377;由于實際的分組到達具有自相關性，可以假設分組到達是獨立同分布的貝努利過程，或相關的離散批到達馬爾可夫過程(DBMAP)，那么能夠嚴格證明對于2×2端口的輸入/輸出鏈路，POT也具有最低的分組丟失率#65377;

(2)最大忙期策略#65377;上述的POT是靜態的，其參數需要預先設定好#65377;為了能適應網絡的變化，采用了最大忙期策略(Maximum Busy Period，MBP)#65377;因為分組丟棄發生在輸出端口處于空閑狀態，MBP盡可能保持所有端口的忙期，并從期望等待時間最長的隊列中刪除分組#65377;對于M/G/1隊列，忙期的平均長度由1/(1-λi)× Qi(t)估計，參見圖1#65377;可見MBP考慮了分組到達速率也考慮了當前排隊的分組數量#65377;筆者通過試驗模擬比較，MBP的性能要好于靜態的POT策略#65377;

雖然PO策略的性能是最好的，但在高速網絡中PO策略實現困難，因為它刪除分組的操作需要耗時很多#65377;不過在區分服務策略中，PO可以結合隊列管理機制，為多媒體傳輸流提供較好的QoS保證#65377;

1.2.3動態策略

MBP策略實際上是一種動態緩存管理策略，所以能動態適應網絡傳輸變化#65377;文獻[4]設計了啟發式的自適應控制系統，在各種傳輸負載條件下統計傳輸到達的速率，隨時改變資源的分配#65377;但統計網絡傳輸并不容易^[5，6]#65377;Choudhury和Hahne^[7]提出了動態閾值策略，此后又有人根據其缺點提出了相應的動態策略#65377;

(1)動態閾值策略#65377;該策略(DT)的基本思想是:任何時候，端口的隊列長度閾值與當前交換機中未使用的緩存數量成比例:

T(t)=α×(M-Q(t))

其中，常數α被稱為閾值因子，若輸出端口隊列長度等于或者超過當前閾值，到達這個端口的分組將被丟棄#65377;

當負載變化時，系統經歷一個瞬時變遷#65377;例如一個輕負載輸出端口忽然變得活躍時，其隊列變長，整個緩存使用增加，控制閾值減少，超過閾值的隊列暫時阻塞到達的分組直到隊列變短，為新的活躍隊列釋放更多的緩存#65377;DT的主要優點是動態適應傳輸負載的變化#65377;

(2)最佳DT#65377;DT緩存管理算法比較簡單并且適應網絡變化，但是浪費一定數量的未用緩存，雖然這塊空間的數量很小#65377;Ruixue Fan等人提出了最佳動態閾值緩存管理算法#65377;其目標是最大限度提高緩存利用率，并保證緩存分配公平#65377;在圖1中，當端口i的分組到達速率和輸出服務速率變化時Qi(t)會隨之而變化，最佳DT算法的端口隊列閾值T(t)依據式(1)動態調整大小:

其中，ΔT是閾值變化量，若以分組數量計算則ΔT=1;Tm表示最小緩存閾值，初始時設定:Q0=βM表示可用緩存數量，0≤β≤1一般可取0.9以上#65377;

上式說明，當所有隊列長度Q(t)小于Q0時，到達的分組總能被接收，閾值T更新為當前的最大隊列長度值;當Q(t)大于或等于Q0時，T將以分組到達的速率減少#65377;最佳DT算法本身不要求預留緩存，并且允許超負載的端口隊列在緩存未滿時占用更多的空間，算法的緩存利用率要高于DT#65377;

(3)和諧算法#65377;該算法是按照隊列的大小順序給各個端口分配緩存^[8]，大小為第i個的隊列獲得1/i比例的內存(所以稱為和諧策略)#65377;這個方案限制了各個隊列的長度與隊列子集合的所有隊列長度和#65377;筆者認為，緩存管理方案通過約束公式表達出來#65377;如果接收一個分組不會破壞這些約束條件，那么這個分組被接收;否則被拒絕#65377;和諧策略的約束公式為

其中，s(i)是第i長的輸出端口隊列(全局排列);Ti是端口獲得緩存的閾值;Ri是為端口i保留的緩存大小;Mk=(M∑Ki=11/i)/(ln(N)+1)是前K個最長隊列和的閾值#65377;

使用ON/OFF傳輸模型模擬和諧策略性能表明:當重負載鏈路增加負載時，DT策略會出現問題，增加其輸入量，其輸出量保持不變#65377;而和諧方案在這種情況下表現比較好#65377;

1.2.4多優先級策略

為了向不同類型的網絡流提供不同優先級的QoS保證，必須對每個傳輸流或者一組傳輸流使用的資源數量加以控制，這需要緩存管理算法必須具有多優先級特性#65377;

(1)多優先級DT#65377;Choudhury和Hahne將他們的DT緩存管理算法擴展到多丟失優先級情況，并且闡述了原理，給出了性能分析的理論值和試驗值^[9]#65377;

按圖1的模型和DT算法的閾值公式，將新到來分組的丟失優先級與閾值Qi

①將因子α變為αP，p=0，1，…，P-1，按照優先級進行分組:α0>α1>…>αp-1#65377;

②將閾值T(t)與QPi(t)或者∑k377;

③將M按照不同優先級劃分為M=M0>M1>…>Mp=0;Mp表示對應優先級為P的有效緩存大小#65377;

④將Q(t)替換為∑k

筆者研究了上述所有情況，根據為每個端口分配緩存情況的不同，有三種結果:根據某個控制參數按比例分配緩存和輸出負載，以保證每個優先級端口都得到不同的資源;將大部分資源分配給高優先級;在極度擁塞情況下，只給高優先級分配緩存資源，可以根據控制原則和管理目標取哪一種模式進行相應的緩存管理控制#65377;

(2)多優先級最佳DT#65377;

可以將最佳DT擴展到多優先級情況#65377;該算法繼承了最佳DT的優點:緩存利用率高#65380;閾值抖動小#65380;分組丟失率小#65377;如圖1模型，參照式(1)，當端口的隊列長度變化時，優先級為P的隊列的閾值按下式調整:

式(2)中說明，當所有的隊列長度Q(t)等于或者大于βM時，優先級為P的隊列的閾值將以分組到達的速率減少;當Q(t)小于βM時，到達的分組總能被接收，閾值Tp更新到當前的最大隊列長度值#65377;為了模擬更真實的網絡環境，筆者建立了自相似特性分組傳輸模型，模擬了多優先級最佳DT算法的性能#65377;模擬結果表明該算法要好于多優先級DT算法的性能#65377;

(3)流水線區間#65377;

在最近的研究中，有人提出了新的優先級緩存管理算法，分別是流水線區間(Pipelined Sections，PS)和模糊優先級控制(Fuzzy Priority Control，FPC)#65377;PS結構如圖2所示#65377;

PS算法的基本原理如下:

①將緩存空間分成N個不同優先級區間，在每個區間中為每個需要QoS保證的數據流分配一些緩存#65377;

②首先到達的傳輸流進入最后區間，其傳輸優先級最高#65377;

③當最后區間的保留緩存用盡時，新到達的分組再進入其他區間#65377;

④輸出端口只能從最后區間取出分組進行發送，其他區間用于緩存和組織分組#65377;

⑤當最后區間中的所有分組被傳輸完時，區間被旋轉:較低優先級區間的分組移到臨近的高優先級區間#65377;

⑥PS緩存管理方法適用任何分組調度機制#65377;

PS算法的平均復雜性是O(1)#65377;文獻[9]證明了當傳輸流f被漏桶(σ，ρ)(σ是burst大小，ρ是漏桶的token速率)限制速率時PS可以提供分組無損失的服務#65377;性能模擬結果顯示，PS很容易識別出非一致性傳輸流(Nonconformant Flow)的過載分組#65377;PS原理簡單#65380;延遲和抖動低，具有很好的擴展性，并且能夠提供速率保證#65377;

(4)模糊優先級控制#65377;面對分組交換網絡中的不同優先級的網絡流，使用模糊邏輯進行緩存管理，這就是模糊優先級控制(FPC)#65377;FPC模型如圖3所示#65377;

FPC模糊系統的輸入變量:高優先級傳輸流的丟失率CLRH和緩存占用狀態(緩存中分組數量N和隊列長度變化量ΔN)#65377;它們的述語集如下:

①CLRH:{Low，Medium，High，Very High}#65377;

②N:{Low，Medium，High，Very High}#65377;

③ΔN:{Neg.Big，Neg.Small，Zero，Pos.Small，Pos.Big}#65377;

輸出變量ACTION的術語是:{Strong Discard(SD)，Discard(D)，Marginal Discard(MD)，Marinal Admit(MA)，Admit(A)，Strong Adimt(SA)}#65377;

FPC關系函數的參數是高優先級傳輸流的信元(或分組)丟失率最大值CLRRH和緩存大小Q#65377;因為兩者都不是統計參數，所以FPC非常簡單靈活#65377;

由輸入變量術語集元素個數可知模糊規則有80個#65377;最典型的規則如下:

當CLRH是Low#65380;N是Low并且ΔN是negative時，輸出ACTION是Strong Admit(SA)#65377;

PushOut和閾值策略均存在這樣問題:低優先級的傳輸流增加時會增加高優先級傳輸流的丟失率#65377;而FPC保證高優先級傳輸流QoS需求的能力優于PushOut策略，同時FPC也允許低優先級的傳輸流占用未用的緩存#65377;

2緩存管理算法比較研究

2.1比較標準

本文對緩存管理算法給出評定的標準，一個好的緩存管理算法應該滿足如下性質:

(1)緩存利用率#65377;訪問緩存的概率，只有較高的緩存利用率才有好的緩存管理算法#65377;

(2)丟失分組數#65377;數據傳輸過程是按某個概率丟失分組的過程，分組丟失的多少也是衡量緩存管理算法的一個重要標準#65377;

(3)吞吐量#65377;它是量度網絡分組傳輸快慢的物理量，在路由器組成的網絡中，一個好的緩存管理算法勢必有好的吞吐量#65377;

(4)鏈路利用率#65377;它是路由器在傳輸數據中鏈路利用的效率，緩存管理算法的好壞影響著鏈路利用率的高低#65377;

2.2仿真試驗環境和試驗設計

(1)分組長度的分布#65377;

統計結果表明，廣域網上的分組長度分布具有相對穩定的特點#65377;在試驗中認為:64#65380;512和1 500 Bytes的分組大約各占總分組個數的40%#65380;20%和40%#65377;其余長度的分組以小概率出現#65377;

(2)分組源模型#65377;

分組的產生采用自相似過程，用基于Pareto調制的Poisson過程模擬網絡數據流#65377;Burst以參數為λ的Poisson過程到達#65377;Burst流產生以后，要對分組作進一步處理，即將所有的分組按照時間先后排序#65377;此外，雖然從路由器外部來看，分組的到達是以Burst流的形式進入的，但是路由器工作時的對象單元仍然是分組，而且本文主要涉及緩存管理算法的性能，所以文中進行試驗結果分析時，仍以分組為對象，不考慮某個時刻的分組究竟屬于哪個Burst流#65377;

2.3算法模擬結果比較

仿真試驗的網絡拓撲結構如圖4所示#65377;其中兩個路由器之間是網絡瓶頸，帶寬為1.5 MBps，延時為20 ms#65377;在瓶頸鏈路路由器上分別選用的緩存管理算法為:靜態閾值策略選用SMQMA算法;PushOut策略選用MBP算法;動態策略選用最佳DT算法;多優先級策略選用PS算法#65377;緩存資源為1.0 MB，試驗的分組為一萬四千多個，四個端口的分組到達概率相等均是0.25，輸入負載為平衡負載#65377;

圖5是四種緩存管理算法的緩存利用率比較曲線，從緩存利用率圖5中容易看出，PS的緩存利用率較高，DT次之，SMQMA最差#65377;

圖6是四種緩存管理算法的丟失分組數比較#65377;從圖6可以看出對于SMQMA算法的丟失率最高，對于DT算法與BMP算法的丟失率較低，而PS最低，這是它充分利用緩存資源的結果#65377;

圖7是四種緩存管理算法關于網絡吞吐量的比較#65377;從圖7中可以看出，對于同一時刻，PS與DT的吞吐量比較接近，SMQMA與MBP的吞吐量比較接近，PS的吞吐量最高，SMQMA的吞吐量最低#65377;

2.4緩存管理算法比較分析

靜態閾值策略包括CS#65380;CP#65380;SMXQ#65380;SMA和SMQMA是比較早期提出來的緩存管理算法，它們非常簡單，易于實現，在早期實際應用中也很多#65377;但是靜態閾值策略缺乏動態適應網絡傳輸情況的變化能力，因此監視傳輸流負載#65380;更新閾值參數的思想應運而生#65377;PO策略是一種自適應的方案，它公平，能夠達到很高的傳輸率;但是PO需要刪除已經接收到緩存中的分組所以實現起來太復雜#65377;動態閾值策略雖不能達到PO的性能，但是它應付負載變化比ST更靈活，而實現起來比PO更容易#65377;此外，最佳DT算法最大限度地利用緩存資源，提高了傳輸性能;而和諧策略在整體分組傳輸率方面表現得很好#65377;

分組交換設備一般有多個輸入/輸出端口，同時網絡中需要QoS保證的傳輸越來越普遍，這就需要多優先級的緩存管理策略#65377;DT算法的多優先級擴展有多種模式，可以根據控制原則和管理目標選擇哪一種模式進行緩存管理控制#65377;多優先級的最佳DT算法則繼承了最佳DT算法的優點，減少了預留緩存，提高了吞吐率#65377;最近提出的PS方案被證明可以提供速率保證#65377;FPC基于模糊邏輯，不需要統計參數，它在保證高優先級傳輸方面表現出色#65377;

3結束語

緩存管理是輸入控制機制，它根據當前的緩存占用情況決定是否接收剛到達的分組#65377;如果沒有緩存管理，在輸入時也沒有準入控制，惡意的傳輸流會用盡全部緩存空間，出現拒絕服務的情況，此時分級調度的性能也會下降#65377;所以，緩存管理對于控制系統資源的使用#65380;為流量提供QoS保證起著重要的作用#65377;

對傳輸流的排隊分析不斷發生著轉變，原來認為它有隨時性，后來認為具有突發性，現在經過對不同類型網絡傳輸流的大量測量表明，傳輸流體現出統計自相似的特性，即長范圍相關特性#65377;在自相似傳輸條件下已有的緩存管理方法能否保持很好的性能，還需要進一步研究#65377;

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。