[發明專利]基于鏈表的交換網絡中隊列緩沖管理方法

有效

• 申請號: 200910084278.0
• 申請日: 2009-05-20
• 公開（公告）號: CN101594299A
• 公開（公告）日: 2009-12-02
• 發明（設計）人: 林棟;劉斌
• 申請（專利權）人: 清華大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;G06F17/30
• 代理公司: 北京眾合誠成知識產權代理有限公司
• 代理人: 朱 琨

1.基于鏈表的交換網絡中隊列緩沖管理方法，其特征在于，所述方法是一種基于鏈表的交換網絡中多隊列緩沖管理的方法，是在一種隊列緩沖管理系統中依次按以下步驟實現的：

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

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

隊列管理模塊設有：數據包輸入端口和數據包輸出端口，

片內存儲器MRAM，與所述隊列管理模塊互連，

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

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

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

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

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

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

分段信息Seg.Info，其中包括：四種狀態：“01”表示數據包頭，“00”表示數據包中段，“10”表示數據包尾，“11”表示獨立數據包，

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

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

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

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

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

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

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