[發(fā)明專利]基于鏈表的交換網(wǎng)絡(luò)中隊列緩沖管理方法

有效

• 申請?zhí)枺?/td>: 200910084278.0
• 申請日: 2009-05-20
• 公開（公告）號: CN101594299A
• 公開（公告）日: 2009-12-02
• 發(fā)明（設(shè)計）人: 林棟;劉斌
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: H04L12/56
• 分類號: H04L12/56;G06F17/30
• 代理公司: 北京眾合誠成知識產(chǎn)權(quán)代理有限公司
• 代理人: 朱 琨

1.基于鏈表的交換網(wǎng)絡(luò)中隊列緩沖管理方法，其特征在于，所述方法是一種基于鏈表的交換網(wǎng)絡(luò)中多隊列緩沖管理的方法，是在一種隊列緩沖管理系統(tǒng)中依次按以下步驟實現(xiàn)的：

步驟(1).構(gòu)建一個用于所述交換網(wǎng)絡(luò)中多隊列緩沖管理的隊列管理系統(tǒng)，所述系統(tǒng)含有：FPGA芯片、緩存數(shù)據(jù)包DRAM和緩存數(shù)據(jù)包描述控制信息用的SRAM，其中：

FPGA芯片含有：隊列管理模塊和片內(nèi)存儲器，其中

隊列管理模塊設(shè)有：數(shù)據(jù)包輸入端口和數(shù)據(jù)包輸出端口，

片內(nèi)存儲器MRAM，與所述隊列管理模塊互連，

緩存數(shù)據(jù)包DRAM，與所述隊列管理模塊互連，所述緩存數(shù)據(jù)包DRAM是一種延遲壓縮式的RLDRAM，以16個周期為讀寫操作的最小時間單位，實際配置為64B×512K，擁有讀/寫分離的數(shù)據(jù)總線，但讀寫復(fù)用一套地址及控制總線，

緩存數(shù)據(jù)包描述控制信息用的SRAM，型號為CY7C1370C，擁有一套讀寫復(fù)用的數(shù)據(jù)和控制總線，實際配置為32bits×512K；

步驟(2).把所選RLDRAM和SRAM共同組成一個“數(shù)據(jù)域和控制域分離”的鏈表單元，所述的每個鏈表單元包含一個64B的數(shù)據(jù)域和一個32bits的控制域，由擁有相同高位地址的所述RLDRAM和SRAM組成，

步驟(3).在所述FPGA中建立一個鏈表空間管理結(jié)構(gòu)實現(xiàn)的512K個所述鏈表單元的管理：在該FPGA的片內(nèi)存儲器MRAM中額外維護每個邏輯隊列的頭尾指針，以對應(yīng)于頭尾鏈表單元對應(yīng)的外存地址，再通過一個存有空閑鏈表頭尾指針的獨立隊列Freelist，實現(xiàn)對空閑鏈表單元的管理，

步驟(4).把所述交換網(wǎng)絡(luò)中多隊列緩沖的控制信息進行最大限度的壓縮后得到：流號Flow?No，占16bits，分段信息Seg.Info占2bits，信元長度length占5bits，數(shù)據(jù)包總長度Total?Length占9bits，其中：

流號Flow?No，高位表示目的線卡號Card?No，

分段信息Seg.Info，其中包括：四種狀態(tài)：“01”表示數(shù)據(jù)包頭，“00”表示數(shù)據(jù)包中段，“10”表示數(shù)據(jù)包尾，“11”表示獨立數(shù)據(jù)包，

然后，在第一個鏈表單元中存儲所述16bits流號和9bits數(shù)據(jù)包總長度信息，在后繼鏈表單元的后繼信元中存儲所述分段信息Seg.Info，以便在對所述DRAM進行操作的同時讀取所述SRAM中下一鏈表單元的控制信息，

步驟(5).按以下步驟對到達的4個信元A、B、C、D依次進行流水線操作以便等效于在16個周期內(nèi)處理一個信元：

步驟(5.1).所述隊列管理模塊在4個周期內(nèi)讀取入隊信元A，并獲取該信元A的流號信息，

步驟(5.2).所述隊列管理模塊在4個周期內(nèi)，對所述片內(nèi)存儲器MRAM進行一次讀操作，查詢步驟步驟(5.1)中獲取的流號所屬當(dāng)前隊列的隊尾指針，同時，在8個周期內(nèi)對所述的SRAM進行一次讀操作，以查詢當(dāng)前空閑鏈表，申請一個新鏈表單元，獲取當(dāng)前空閑鏈表的下一跳指針，用來更新空閑鏈表，再在發(fā)出所述查詢當(dāng)前空閑鏈表一個周期后，用5個周期的時間對所述SRAM進行一次寫操作，修改所述當(dāng)前隊列隊尾鏈表的下一跳指針，使它指向所述新申請的鏈表，同時讀取到達信元B的流號信息，在該步驟(5.2)中所執(zhí)行的所有操作在16個周期內(nèi)完成，去處理所述A和B兩個信元，

步驟(5.3).所述隊列管理模塊對所述MRAM進行一次寫操作，修改所述信元A中的隊尾指針信息，同時，在11個周期內(nèi)對所述RLDRAM進行一次寫操作，所述信元A寫入到對應(yīng)所述RLDRAM的鏈表單元的數(shù)據(jù)域，與此同時，獲取所述信元C的流號信息，在該步驟(5.3)中所執(zhí)行的所有操作在16個周期內(nèi)完成，同時處理所述A、B、C三個信元，

步驟(5.4).在每個所述的鏈表單元為64B的情況下，所述隊列管理模塊再耗時16個周期，結(jié)束所述信元A的寫入，同時對所述信元B，在4個周期內(nèi)執(zhí)行對所述MRAM的寫操作，修改隊列的隊尾指針信息，在11個周期內(nèi)，對所述的RLDRAM執(zhí)行寫操作，寫入所述信元B，同時獲取所述信元D的流號信息，在該步驟(5.4)中的執(zhí)行的所有操作在16個周期內(nèi)完成，去處理所述A、B、C、D共4個信元，

步驟(5.5).把所述信元C的RLDRAM寫入操作、所述信元D的查詢當(dāng)前流號所述當(dāng)前隊列的隊尾指針的對所述MRAM的讀操作，以及查詢當(dāng)前空閑鏈表的對所述SRAM的讀操作、移入到下一階段4個16周期內(nèi)E、F、G、H四個信元來臨時的第一個16周期內(nèi)進行，以此類推。