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

有效

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

技術領域

隊列管理是計算機網絡應用(如路由器，交換機和防火墻等核心設備中)的關鍵技術之一。隊列管理的任務是通過相應的體系結構、根據數據包相應的標識信息，實現對數據包的分隊列存儲與輸出，它屬于計算機網絡技術領域。

背景技術

隨著英特網的進一步發展，新的網絡業務不斷涌現。包括語音服務、虛擬專用網絡在內的多種網絡業務對網絡服務質量提出了更高的要求。由于網絡流量的突發特性，采用帶寬的過度預留已經不能有效保證網絡的服務質量。與此同時，網絡服務提供商也希望通過提供有差別的服務來增加收入。

通過對不同的網絡業務執行相應的優先級服務可以實現較好的網絡服務質量。而為了實現優先級服務，就必須實現對數據包的隊列管理，具體又分為排隊存儲和調度輸出。排隊存儲的主要任務是把輸入的數據包根據對應標識(如流號)、區分隊列分別存儲，并在每個隊列內根據數據包到達的先后順序維護FIFO(First?In?First?Out，FIFO)結構。而調度輸出則是根據調度算法得出的服務次序、將指定隊列隊首的數據包送出，并更新相應隊列狀態。

隨著網絡鏈路傳輸速率的快速提高，通過軟件方式實現的隊列管理已經不能滿足要求，而通過硬件實現的隊列管理芯片憑借其巨大的性能優勢逐漸占據高端應用領域。通過設計相應的硬件芯片，配合采用動態隨機存儲器(DynamicRandom?Access?Memory，DRAM)、靜態隨機存儲器(Static?Random?AccessMemory，SRAM)等外存芯片可以實現高速而又廉價的隊列管理系統。這個過程中需要解決的問題是：外存芯片只能根據對應的物理地址實現相應的數據讀寫操作。如何組織相應的數據結構，在外存所提供的線性存儲空間中實現多隊列結構是隊列管理的重要問題之一。這個問題還涉及到外存延遲、存儲開銷等多方面內容。

下面針對上述問題的一般解決方法進行相應說明。

首先是外存芯片的規格化。為了盡可能地簡化硬件操作、實現外存存儲與帶寬的最大化利用，在外存芯片(尤其是DRAM)的使用中，通常將多個存儲單元視為一個大的存儲單元進行集中使用。這種方式可以較好地解決外存芯片使用中的一些問題(如Bank?Conflict，DRAM刷新等)，但是也因此引入了額外的開銷。由于存儲空間劃分的粒度加大，當數據讀寫操作粒度相對較小時，仍然需要對整個大存儲單元進行完整操作。在均衡多方面因素后，一般認為把DRAM的存儲單元按照64字節或者128字節為單位進行使用效果最好。詳細原因在此略過。

通過外存芯片的規格化，外存芯片所包含的存儲空間可視為一連串獨立的大存儲單元。鏈式空間管理可以實現對這些存儲單元較好的管理。其基本思想是利用一個或者多個大存儲單元構造鏈表單元，每個鏈表單元又存儲相應控制信息(如鏈表指針等)，通過串聯多個鏈表單元實現隊列，同時在硬件芯片內部存儲對應隊列的頭尾指針(頭尾鏈表單元對應的外存地址)。這種方式只要額外維護隊列的頭尾指針信息、存儲壓力較小，因而被廣泛采用。但是在具體的實現細節上卻各有不同，效率上也有很大差別。重點體現在鏈表的存儲效率和鏈表操作的效率兩個方面。

之前提到過每個大存儲單元因數據操作的粒度存在利用率問題，鏈表的存儲效率則是指在實際數據操作中有效數據所占的比例。例如，設每個大存儲單元為64字節，在某次數據操作中，只有60字節被用于構造鏈表，而鏈表單元內部又額外存儲了16字節的控制信息(如下一跳指針、當前鏈表單元的有效長度、數據包的分段信息等)。于是，實際鏈表的存儲效率只有(44/64)。

而鏈表的操作效率則是指在某段時間內、對外存的實際數據操作所占時間的比例。由于存在外存延遲，鏈表操作很難連續。例如：在讀取某一隊列隊首鏈表單元時，要先獲取其對應隊首鏈表單元地址，然后讀取對應地址的外存存儲單元，又經過若干周期后才獲得讀出數據，送出數據并等待下次操作請求。這個過程中，只有“獲得讀出數據”這一環節實際占用了外存芯片，于是相應的鏈表操作效率就很低了。

如何提高上述兩種效率是隊列管理的重要研究方向。

針對傳統方法存在的多種問題，本專利申請的技術方法的先進性和新穎性體現在：利用調度輸出過程以數據包為單位這個特點，壓縮存儲鏈表單元中的控制信息，提高了鏈表單元的存儲效率；同時通過SRAM和DRAM構造了數據與控制分離的鏈表單元結構，設計流水線實現多個鏈表單元的并發處理，提高了鏈表的操作效率。它開銷小、擴展性好。

發明內容