支持多隊列的共享緩存動態門限早期丟棄裝置的製作方法

2023-10-28 16:51:37 1

專利名稱：支持多隊列的共享緩存動態門限早期丟棄裝置的製作方法
技術領域：
本發明屬於IP技術領域。
背景技術：
當前Internet中間節點設備，如路由器等，通過對其內部的緩存隊列長度的控制，來影響和控制網絡的擁塞情況。目前見諸於設備的傳統的緩存隊列管理機制是尾部丟棄(TailDrop)機制對每個隊列設置一個長度門限，如果隊列長度沒有到達設定門限，接收所有分組進入隊列；否則丟棄到達的分組。該機制實現簡單，但是存在三個嚴重的缺陷(1)持續的滿隊列狀態(Full Queues)；(2)業務流對緩存的死鎖(Lock Out)；(3)業務量的全局同步(Global Synchronization)；目前普遍認可的方法是加入中間節點的增強功能主動隊列管理(AQMActive QueueManagement)。即中間節點需要在網絡進入擁塞情況之前，預先丟棄部分分組，以使得TCP協議響應來減慢源端的發送速率，避免擁塞的發生。在現有的網絡設備中被採用的AQM機制是隨機早期檢測(REDRandom Early Detection)方法。但是該機制的主要缺點是(1)參數的設定困難，而且其性能敏感於參數和網絡情況的變化；(2)需要對每個單隊列設置參數和計算，不利於隊列數目或者網絡流數目擴展的情況；(3)RED算法中有很多乘法運算，需要大量資源，很難用硬體高速實現。

發明內容
本發明的目的在於從硬體的角度提出一種能夠進行高速處理的支持多隊列的共享緩存動態門限早期丟棄裝置。與目前普遍採用的隨機早期檢測(RED)機制相比，本發明包含以下幾個部分的特點和內容(1)動態調整進行分組丟棄的隊列門限值方法。原始的RED算法需設定一對最大、最小隊列長度的門限的參數，當隊列狀態處於這一對門限的範圍中時，按照一定的概率丟棄到達分組。由於參數是預先設定的，很難滿足多變的網絡狀況，因而性能會隨著設定參數和網絡情況的變化而變化。本發明克服RED算法對於參數設置和網絡情況的依賴，動態調整進行分組丟棄的一對門限，即根據每個當前活躍的隊列的平均隊列長度和整個共享緩存區的平均隊列長度來動態調整丟棄控制的閾值。這一機制的基本思想是當網絡擁塞狀況的趨勢增加，即剩餘緩存空間減少時，提前進入分組丟棄的控制階段；而當網絡擁塞狀況的趨勢減弱，即剩餘緩存空間增加時，推遲進入分組丟棄的控制階段。
(2)採用階梯式丟棄曲線方法在硬體中實現分組的丟棄。在動態確定分組丟棄的範圍之後，需要對進入丟棄控制範圍內的到達流的分組進行部分丟棄。對于越靠近最大丟棄門限的流，將丟棄越多的到達分組，相對地，對于越靠近最小丟棄門限的流，將丟棄越少的到達分組。而當該網絡流超過最大丟棄門限時，完全丟棄到達分組。對於位於丟棄範圍內網絡流的隊列，我們採用如圖3所示的階梯式丟棄曲線來計算應該丟棄的分組的比例，從而避免浮點了運算，使得能夠用硬體查表的方式高速實現。
(3)在共享緩存上的多隊列管理機制。隨著目前internet網絡流的數目的增加和對各種網絡流的服務質量要求的提高，在網絡中間節點設備中也要求能夠支持大量的網絡流的單獨排隊和管理。傳統的方法是事先設定好隊列數目和各個隊列的長度。這種方法緩存利用率低，而且不利於隊列數目的擴展。本發明在共享緩存上進行不同分組的緩存。在網絡流到達或者退出中間節點設備時，動態生成或者撤銷隊列。已建立隊列的網絡流的分組到達時，採用(1)、(2)中所述的方法，判斷是否接納該分組。是，則從空閒的緩存中分配空間連接到其所述的隊列中；否，則直接丟棄。
本發明的特徵在於，該裝置是用FPGA晶片實現的，該FPGA晶片中含有IP分組分割電路、空閒塊管理電路、DDR控制器、流單元計數電路、隊列調度電路以及動態門限早期丟棄電路，其中IP分組分割電路，該電路把到達的變長的IP分組按設定的流單元長度進行分割，得到定長的流單元，用cell表示，所述IP分組分割電路含有第1個先進先出存儲器設有IP分組輸入端；計數器，該計數器的計數信號輸入端與所述第1個先進先出存儲器的相應輸出端相連；分路器，該分路器有兩個輸入端一個輸入端與所述第1個先進先出存儲器的IP數據輸出端相連，該分路器的另一個輸入端與所述計數器的計數輸出端相連；IP包頭信息寄存器，該寄存器的IP包頭信息輸入端與所述分路器的相應輸出端相連；流單元頭寄存器，設有流單元輸入端，該輸入端與所述IP包頭信息寄存器的相應輸出端相連；選擇器內設有預定的流單元長度，所述選擇器的流單元頭信息輸入端、IP數據輸入端依次分別與所述流單元頭寄存器、分路器的相應輸出相連；流單元數據寄存器，該寄存器的流單元數據輸入端與所述選擇器的相應輸出端相連；第2個先進先出存儲器，該存儲器的流單元數據輸入端與所述流單元數據寄存器的相應輸出端相連，該先進先出存儲器輸出分割得到的流單元；流單元計數電路，含有加減計數器和磁性隨機存取存儲器，所述的加減計數器設有流單元接納指示信號輸入端，接收片外雙倍數據速率存儲器的流單元；流單元調度指示信號輸入端，接收流單元的調度信號；先前流單元數目輸入端；所述的磁性隨機存取存儲器，用MRAM表示，設有流單元的流號輸入端；當前流單元數目輸入端，該輸入端與所述加減計數器的相應輸出端相連；該MRAM還有先前流單元數輸出端，該輸出端與所述加減計數器的相應輸入端相連；該加減計數器在當一個流單元被接納加入隊列時計數器加1，當一個流單元被調出離開隊列時計數器減1，該加減計數器內還設有隊列權重的值Wq，按下式計算t時刻的平均隊列長度Liavg(t)並輸出Liavg(t)＝(1-Wq)Liavg(told)+WqQi(t)其中，Liavg(told)為t時刻隊列i先前的流單元數；Qi(t)為t時刻隊列i到達的流單元數目，該加減計數器同時設有一個Q(t)輸出端，Q(t)是指t時刻所有隊列長度總和，Q(t)＝ΣiQi(t)；空閒塊管理電路，該電路是一個空閒塊加減計數器，該計數器內設有片外雙倍數據速率存儲器的容量，該加減計數器還設有流單元接納指示信號輸入端和流單元調度指示信號輸入端，當一個流單元被接納加入隊列，或者一個流單元被調出隊列時，該加減計數器依次分別對設定的片外雙倍數據速率存儲器的容量加1或者減1，據此輸出該片雙倍數據速率存儲器的空閒容量；片外雙倍數據速率存儲器的控制器，該控制器連接著一個所述的片外雙倍數據速率存儲器，對該存儲器的存取訪問進行控制；隊列調度電路，該電路設有對所述片外雙倍數據速率存儲器中的流單元進行讀入調度的隊列調度信號輸出端；動態門限早期丟棄電路，該電路設有Liavg(t)寄存器、進行丟棄控制的隊列長度的下限閾值Lmin(t)運算的運算器1、進行丟棄控制的隊列長度的上限閾值Lmax(t)運算的運算器2、比較器和進行丟棄控制的運算器3，其中，運算器1，內置有Lmin(t)冗餘度，用α表示，還置有所述的片外雙倍數據速率存儲器的容量，用B表示，單位是流單元長度，該運算器通過Q(t)信號輸入端接收Q(t)信號並按下式計算Lmin(t)Lmin(t)＝α(B-Q(t))；運算器2，內置有Lmax(t)冗餘度，用β表示，β＞α，還置有所述的片外雙倍數據速率存儲器的容量，用B表示，單位是流單元長度，該運算器通過Q(t)信號輸入端接收Q(t)信號並按下式計算Lmin(t)Lmax(t)＝β(B-Q(t))上述各Q(t)信號輸入端與所述流單元計數電路內的加減計數器的相應輸出端相連；比較器，內置有最大丟棄概率pmax，且該比較器設有Liavg(t)信號輸入端，該輸入端與所述流單元計數電路內的加減計數器的相應輸出端相連，該比較器還設有Lmin(t)信號和Lmax(t)信號共兩個輸入端，該比較器在接收到Liavg(t)、Lmin(t)、Lmax(t)信號後，依次按以下步驟執行
步驟1若Liavg(t)≤Lmin(t)，則接收全部到達的分組，並輸出到達的所有流單元，丟棄值為0；步驟2若Lmin(t)＜Liavg(t)＜Lmax(t)時，則計算丟棄概率pa，並以此概率丟棄到達分組pb=pmax(Liavg(t)-Lmin(t))(Lmax(t)-Lnin(t))]]>pa＝pb/(1-cpb)，設c＝-1；步驟3若Liavg(t)≥Lmax(t)，則丟棄全部分組，c＝0；運算器3，該運算器按所述比較器輸出的流單元丟棄標誌，即所述c的值按下式計算丟棄概率pac＝-1，則pa＝pb/(1+cpb)，丟棄部分到達的分組；c＝0，則pa＝pb，丟棄所有到達的分組。
本發通過測試證明，具有適應性強、緩存利用率高而且支持多流隊列動態管理機制的優點。


圖1基本結構模塊和外部接口關係圖2RED算法丟棄曲線圖3本發明的丟棄機制的階梯式丟棄曲線圖4硬體實現流程5IP分組分割電路(1-1)圖6動態門限早期丟棄電路(1-2)圖7cell計數電路(1-3)圖8空閒塊管理電路(1-4)圖9DDR控制器(1-5)圖10隊列調度電路(1-6)圖11第二段丟棄曲線波形(a)圖12第二段丟棄曲線波形(b)圖13第三段丟棄曲線波形(a)圖14第三段丟棄曲線波形(b)圖15第四段丟棄曲線波形(a)圖16第四段丟棄曲線波形(b)具體實施方式
網際網路工程任務組(IETF)提出了AQM技術並推薦了RED機制。實現RED算法的路由器發現擁塞前兆時，提前隨機丟棄緩衝隊列中的一些分組，而不是等到緩衝區佔滿後丟棄所有新的分組。當網絡中間節點設備的緩存的平均隊列長度超過一個指定的最小門限minth時，就認為出現了擁塞前兆，這時路由器按一定的概率pa丟棄分組，這個概率pa是平均隊列長度avg(t)的函數pb=pmax(avg(t)-minth)(maxth-minth)]]>pa＝pb/(1-cpb)其中pmax為設定的最大丟棄概率，c的取值為一常數。
當平均隊列長度超過一個指定的最大門限maxth時，路由器認為網絡出現了嚴重擁塞，所有的分組都要丟棄。RED算法丟棄曲線如圖2所示。
從上述RED算法的介紹可知，硬體實現RED算法時存在以下幾個問題(1)參數的選擇minth，maxth，maxp和wq等參數的選擇對RED算法有很大影響，但是這些參數是事先設置好的，不能實時反映當前網絡的狀況；(2)RED算法中有很多乘法運算，另外還需要生成隨機數，用硬體高速實現有一定的困難；(3)RED算法採用先進先出的方法，對復用在一個接收隊列中的所有連接的分組進行調度，但不監視每個流的狀態，因此不支持多流多隊列。
本發明在一片FPGA上，用硬體描述語言Verilog HDL編寫實現，其基本結構和外部接口關係如圖1所示，各電路工作流程為當一個IP分組到達該裝置時，由IP分組分割電路(1-1)切分為60位元組的定長的數據單元，稱作cell，然後將其發送給動態門限早期丟棄電路(1-2)。動態門限早期丟棄電路(1-2)模塊根據動態門限早期丟棄方法的策略對cell實施接納和丟棄控制，被接納的cell再加上通過DDR控制器(1-5)寫入片外DDR存儲器(1-7)相應的網絡流緩存隊列中，等待隊列調度電路(1-6)的調度命令。隊列調度電路(1-6)對片外的DDR存儲器中的cell進行調度，從眾多的隊列中選擇某個流的隊列，調度DDR存儲器中的分組離開。cell計數電路(1-3)按照cell的流號，對DDR中的cell進行計數，對每個流都維護一個計數器，當一個cell接納進入隊列時計數器加一，當一個cell被調度離開隊列時計數器減一。空閒塊管理電路(1-4)負責統計片外DDR中的空閒容量，當一個cell被接納進入隊列時，分配一個空閒塊，並且其數目減一；當一個cell被調度離開隊列時，回收一個空閒塊，並且其數目加一。動態門限早期丟棄電路(1-2)依據cell計數電路(1-3)提供的片外DDR存儲器中該流的當前cell數目和空閒塊管理電路(1-4)提供的片外DDR中的當前空閒容量兩個參數對cell實施接納和丟棄控制。
我們規定，以Qi(t)表示t時刻第i個等待隊列的長度；以Q(t)＝∑iQi(t)表示t時刻所有隊列長度總和，即緩存中被佔用部分的大小；以B表示整個共享緩存區的大小；用Lmin(t)，Lmax(t)代表t時刻進行分組丟棄控制的隊列長度的上限和下限閾值。
當每一個分組到達隊列i時，計算t時刻隊列i的平均隊列長度Liavg(t)(Wq)為設定的隊列權重)

重新計算進行丟棄控制的隊列長度的上限和下限閾值Lmin(t)，Lmax(t)(β＞α)

Lmax(t)＝β(B-Q(t)) (3)根據計算得到的上限Lmax(t)和下限Lmin(t)，進行以下的判斷(1)如果Liavg(t)≤Lmin(t)，不作任何控制，接收全部到達的分組；(2)如果Lmin(t)＜Liavg(t)＜Lmax(t)時，則計算丟棄概率pa，並以此概率丟棄到達分組。(pmax為設定的最大丟棄概率)

(3)如果Liavg(t)≥Lmax(t)，則丟棄全部分組，c＝0。
以下給出實現的偽代碼初始化Liavg(t)＝0，c＝-1；時刻t，某一分組到達輸入隊列i用式(1)計算Liavg(t)；用式(2)、(3)計算Lmin(t)和Lmax(t)；if Lmin(t)＜Liavg(t)＜Lmax(t)用公式(4)、(5)計算丟棄概率pa；以概率pa丟棄達到分組；c＝0；else if Liavg(t)≥Lmax(t)丟棄到達分組；c＝0；elsec＝-1；考慮大小為B的緩存區中，當前只有A個隊列處於活躍的狀態。因為各個隊列的長度被控制在Lmax(t)左右，那麼此時緩存區被佔據的最大容量在Q(t)＝ALmax(t)左右，代入式(3)中可以得到Lmax(t)=B1+A,]]>所以緩存區的利用率為=A1+A.]]>從上式中可以看出，與RED算法一樣，本發明也總是預留出一小部分緩存空間，能夠更好地處理突發性。
在利用硬體高速實現時存在兩個困難一是分組丟棄控制門限Lmin(t)和Lmax(t)的計算；二是丟棄概率的計算。本發明通過對算法作以下的設置，就可以利用硬體來高速實現(1)每當有分組到達，由cell計數電路(1-3)給出該流的平均隊列長度，記為C；(2)整個共享緩存區的大小B是所採用的片外DDR的大小；(3)緩存中被佔用部分的大小Q(t)由空閒塊管理電路(1-4)給出，記DDR中空閒緩存大小是R；(4)參數α＝0.5，β＝1.0，則由空閒塊管理電路(1-4)給出的空閒緩存大小R，Lmin(t)＝0.5R，Lmax(t)＝R，其中通過簡單的右移一位就可以得到分組丟棄控制門限Lmin(t)。
由於丟棄是對一個完整的分組進行實施的，因此，在分組的第一個信元到來時，平均隊列長度C和兩個門限值Lmin(t)，Lmax(t)進行比對，決定是丟棄該分組的cell，還是將該分組的cell寫入片外的DDR存儲器。
另外，如果嚴格計算丟棄概率，並按照該概率隨機丟棄到達的分組，需要複雜的偽隨機數生成電路，並且有大量的乘法運算，會佔用大量的FPGA資源，不利於用硬體高速實現。我們可以採用如圖3所示的分段函數逼近丟棄曲線，然後預先計算好分段門限值、剩餘容量和丟棄概率之間的關係，實現時，僅需要通過從空閒塊管理模塊得到的DDR剩餘容量R和從分組計數電路得到該流的當前隊列長度C，通過表1可查表得到分組丟棄概率，然後按照此丟棄概率周期性丟棄到達的分組。比如，當從分組計數電路得到的當前隊列長度0≤C＜0.5R時，所有到達的分組都不丟棄，都通過DDR控制器(1-5)寫入片外的DDR存儲器；當0.5R≤C＜0.75R時，該流每到達8個分組就丟棄一個分組。採用的分段函數逼近丟棄曲線方法以及周期性的丟棄規則，可在FPGA上高速實現，電路工作流程如圖4所示。
表1剩餘容量R、流的隊列長度C和分組丟棄概率的關係

基於FPGA的支持多隊列的共享緩存動態門限早期丟棄裝置採用硬體描述語言Verilog在一片FPGA上實現，並在所開發的路由器線卡上實驗和測試。測試系統由PC機的並行口，通過FPGA的JTAG口，向該線卡上的FPGA下載HDL代碼，再用測試儀向目標板發送特定的IP分組，經FPGA上的模塊處理之後，由測試儀和EDA工具對輸出結果進行統計和記錄，分析所設計的該裝置正確性。
測試中用到的測試儀為Spirent公司的AX/4000。AX/4000是一種模塊化的多埠測試系統，能夠以高達10Gbps的速度同時測試ATM、IP、幀中繼和乙太網等多種傳輸技術。AX/4000測試儀採用模塊化設計，主要模塊由系統控制模塊、發生器模塊、分析器模塊和豐富的接口模塊組成。發生器模塊提供IP源地址和目的地址、多種發包模式；分析器模塊自動提取的流信息，實時地顯示各流的丟包率、丟包統計等信息，並以數據表、線性圖、直方圖等方式顯示。本專利的實驗用AX/4000產生特定的流，並對結果進行統計和分析。
開發和測試中用的EDA工具主要為Altera公司的Quartus軟體，Quartus軟體完成Verilog代碼的編寫、實現和下載，並用其中的Signal Tap分析和記錄時序波形。
基於FPGA的支持多隊列的共享緩存動態門限早期丟棄裝置採用階梯式曲線來逼近RED的丟棄曲線，周期性地丟棄部分分組。由空閒塊管理電路(1-4)得到的DDR剩餘容量R、由cell計數電路(1-3)給出流的隊列長度C和分組丟棄概率的關係可由表1表示。基於FPGA的支持多隊列的共享緩存動態門限早期丟棄裝置的實驗要測試分段函數曲線的每一段。基於FPGA的支持多隊列的共享緩存動態門限早期丟棄裝置中，如果隊列調度電路(1-6)不進調度，該裝置將會經歷分段丟棄曲線的每一段，可在Quartus的Signal Tap中依次設置相應的觸發值，就可以記錄和分析波形。
第一段曲線的測試如果隊列調度電路(1-6)正常調度，該裝置工作在丟棄曲線的第一段，完全接納到達的分組。在測試中，測試儀AX/4000發包模式均為Manually TriggeredBursts，100％BW發包，總的發包數為300000，每次手動觸發時發送300000個分組，再用測試儀AX/4000接收處理後的分組。從表2可以得出，該裝置工作在丟棄曲的第一段時能正確轉發分組，不會丟棄分組。
表2第一段丟棄曲線測試結果

中間段的測試如果隊列調度電路(1-6)不進行調度，該裝置將會經歷分段丟棄曲線的每一段，依次在Signal Tap中設置相應的觸發值，記錄其波形。在測試中，測試儀AX/4000選擇長度為48位元組包，發包模式均為periodic packets，100％BW。在測試中，在Quartus的Signal Tap中添加如下的信號1.C4_slotcycle該裝置的時鐘節拍記數，計數值為0~15；
2.F_first_cell分組的第一個cell的標誌；3.CON_discard_interval每段丟棄曲線的計數上限，比如在0.75R≤C＜R分段區間時，每3個分組丟棄一個，則CON_discard_interval＝3；4.C4_discard在每段丟棄曲線的周期計數器，用於判斷是否該丟棄該分組，比如在0.75R≤C＜R分段區間時，每3個分組丟棄一個，C4_discard為1~3周期計數，當C4_discard＝CON_discard_interval＝3時，丟棄該分組；5.F_range_judge在每段丟棄曲線的周期計數判斷，當C4_discard＝CON_discard_interval時，到達計數上限時，則F_range_judge＝1，表示該分組要丟棄；6.F_IP_discardIP分組丟棄標誌，為1時，丟棄該分組，信號寬度為IP分組的寬度；7.C19_Cellnum當前流的在DDR中緩存的cell數，即隊列長度C；8.C19_RemainDDR當前的剩餘空間，即剩餘容量R；9.F_range_showRED-DT所在丟棄曲線段的指示；在Quartus的Signal Tap中設置F_range_show為觸發條件，依次為00第一段，不丟棄分組；01第二段，每8個分組丟棄一個；10第三段，每3個分組丟棄一個；11第四段，丟棄全部分組；採用上述的測試方法，得到如下的結果(1)設置F_range_shown的觸發值為01，基於FPGA的支持多隊列的共享緩存動態門限早期丟棄裝置工作在分段丟棄曲線的第二段，每8個分組丟棄一個分組，測試波形如圖11、圖12所示。從圖11、圖12可以看出，當F_range_shown＝01時，C＝172031，R＝344063，0.5R≤C＜0.75R，該裝置工作在分段丟棄曲線的第二段，每8個分組丟棄一個分組，當C4_discard＝8時，F_IP_discard和F_range_judge為1，丟棄該分組，測試正確。
(2)設置F_range_shown的觸發值為10，基於FPGA的支持多隊列的共享緩存動態門限早期丟棄裝置工作在分段丟棄曲線的第三段，每3個分組丟棄一個分組，測試波形如圖13、圖14所示。從圖13、圖14可以看出，當F_range_shown＝10時，C＝22183，R＝294911，0.75R≤C＜R，該裝置工作在分段丟棄曲線的第三段，每3個分組丟棄一個分組，當C4_discard＝3時，F_IP_discard和F_range_judge為1，丟棄該分組，測試正確。
(3)設置F_range_shown的觸發值為11，基於FPGA的支持多隊列的共享緩存動態門限早期丟棄裝置工作在分段丟棄曲線的第四段，丟棄全部分組，測試波形如圖15、圖16所示。從圖15、圖16可以看出，當F_range_shown＝11時，C＝258047，R＝258047，C≥R，該裝置工作在分段丟棄曲線的第四段，丟棄全部分組F_IP_discard和F_range_judge始終為1，丟棄該分組，測試正確。
權利要求
1.支持多隊列的共享緩存動態門限早期丟棄裝置，其特徵在於，該裝置是用FPGA晶片實現的，該FPGA晶片中含有IP分組分割電路、空閒塊管理電路、DDR控制器、流單元計數電路、隊列調度電路以及動態門限早期丟棄電路，其中IP分組分割電路，該電路把到達的變長的IP分組按設定的流單元長度進行分割，得到定長的流單元，用cell表示，所述IP分組分割電路含有第1個先進先出存儲器設有IP分組輸入端；計數器，該計數器的計數信號輸入端與所述第1個先進先出存儲器的相應輸出端相連；分路器，該分路器有兩個輸入端一個輸入端與所述第1個先進先出存儲器的IP數據輸出端相連，該分路器的另一個輸入端與所述計數器的計數輸出端相連；IP包頭信息寄存器，該寄存器的IP包頭信息輸入端與所述分路器的相應輸出端相連；流單元頭寄存器，設有流單元輸入端，該輸入端與所述IP包頭信息寄存器的相應輸出端相連；選擇器內設有預定的流單元長度，所述選擇器的流單元頭信息輸入端、IP數據輸入端依次分別與所述流單元頭寄存器、分路器的相應輸出相連；流單元數據寄存器，該寄存器的流單元數據輸入端與所述選擇器的相應輸出端相連；第2個先進先出存儲器，該存儲器的流單元數據輸入端與所述流單元數據寄存器的相應輸出端相連，該先進先出存儲器輸出分割得到的流單元；流單元計數電路，含有加減計數器和磁性隨機存取存儲器，所述的加減計數器設有流單元接納指示信號輸入端，接收片外雙倍數據速率存儲器的流單元；流單元調度指示信號輸入端，接收流單元的調度信號；先前流單元數目輸入端；所述的磁性隨機存取存儲器，用MRAM表示，設有流單元的流號輸入端；當前流單元數目輸入端，該輸入端與所述加減計數器的相應輸出端相連；該MRAM還有先前流單元數輸出端，該輸出端與所述加減計數器的相應輸入端相連；該加減計數器在當一個流單元被接納加入隊列時計數器加1，當一個流單元被調出離開隊列時計數器減1，該加減計數器內還設有隊列權重的值Wq，按下式計算t時刻的平均隊列長度Liavg(t)並輸出Liavg(t)＝(1-Wq)Liavg(told)+WqQi(t)其中，Liavg(told)為t時刻隊列i先前的流單元數；Qi(t)為t時刻隊列i到達的流單元數目，該加減計數器同時設有一個Q(t)輸出端，Q(t)是指t時刻所有隊列長度總和，Q(t)＝∑iQi(t)；空閒塊管理電路，該電路是一個空閒塊加減計數器，該計數器內設有片外雙倍數據速率存儲器的容量，該加減計數器還設有流單元接納指示信號輸入端和流單元調度指示信號輸入端，當一個流單元被接納加入隊列，或者一個流單元被調出隊列時，該加減計數器依次分別對設定的片外雙倍數據速率存儲器的容量加1或者減1，據此輸出該片雙倍數據速率存儲器的空閒容量片外雙倍數據速率存儲器的控制器，該控制器連接著一個所述的片外雙倍數據速率存儲器，對該存儲器的存取訪問進行控制隊列調度電路，該電路設有對所述片外雙倍數據速率存儲器中的流單元進行讀入調度的隊列調度信號輸出端；動態門限早期丟棄電路，該電路設有Liavg(t)寄存器、進行丟棄控制的隊列長度的下限閾值Lmin(t)運算的運算器1、進行丟棄控制的隊列長度的上限閾值Lmax(t)運算的運算器2、比較器和進行丟棄控制的運算器3，其中，運算器l，內置有Lmin(t)冗餘度，用α表示，還置有所述的片外雙倍數據速率存儲器的容量，用B表示，單位是流單元長度，該運算器通過Q(t)信號輸入端接收Q(t)信號並按下式計算Lmin(t)Lmin(t)＝α(B-Q(t))；運算器2，內置有Lmax(t)冗餘度，用β表示，β＞α，還置有所述的片外雙倍數據速率存儲器的容量，用B表示，單位是流單元長度，該運算器通過Q(t)信號輸入端接收Q(t)信號並按下式計算Lmin(t)Lmax(t)＝β(B-Q(t))上述各Q(t)信號輸入端與所述流單元計數電路內的加減計數器的相應輸出端相連；比較器，內置有最大丟棄概率pmax，且該比較器設有Liavg(t)信號輸入端，該輸入端與所述流單元計數電路內的加減計數器的相應輸出端相連，該比較器還設有Lmin(t)信號和Lmax(t)信號共兩個輸入端，該比較器在接收到Liavg(t)、Lmin(t)、Lmax(t)信號後，依次按以下步驟執行步驟l若Lavgi(t)Lmin(t),]]>則接收全部到達的分組，並輸出到達的所有流單元，丟棄值為0步驟2若Lmin(t)Lavgi(t)Lmax(t)]]>時，則計算丟棄概率pa，並以此概率丟棄到達分組pb=pmax(Liavg(t)-Lmin(t))(Lmax(t)-Lmin(t))]]>pa＝pb/(1-cpb)，設c＝-1；步驟3若Lavgi(t)Lmax(t),]]>則丟棄全部分組，c＝0運算器3，該運算器按所述比較器輸出的流單元丟棄標誌，即所述c的值按下式計算丟棄概率pac＝-1，則pa＝pb/(1+cpb)，丟棄部分到達的分組c＝0，則pa＝pb，丟棄所有到達的分組。
全文摘要
本發明提供一種支持多隊列的共享緩存動態門限早期丟棄裝置屬於IP技術領域，並在一片現場可編程門陣列(FPGA)上實現，其特徵在於含有如圖1的電路IP分組分割電路(1－1)；動態門限早期丟棄電路(1－2)；cell計數電路(1－3)；空閒塊管理電路(1－4)；DDR控制器(1－5)；隊列調度電路(1－6)；片外DDR存儲器(1－7)。它能根據每個當前活躍的隊列的平均隊列長度和整個共享緩存區的平均隊列長度來動態調整隨機早期檢測(RED)算法的參數，提出了支持多隊列的共享緩存動態門限早期丟棄方法，其丟包率更小，緩存利用率更高，同時兼顧公平性。支持多隊列的共享緩存動態門限早期丟棄方法保持了RED和動態門限(DT)機制的優點，並且用階梯式丟棄曲線近似，利於在FPGA中實現。
文檔編號H04L12/56GK1777147SQ20051012636
公開日2006年5月24日 申請日期2005年12月9日 優先權日2005年12月9日
發明者胡成臣, 劉斌, 陳雪飛, 陳洪明 申請人:清華大學