基於多量級線卡的FIB表分解方法與流程

2023-05-15 10:51:16

本發明涉及路由器技術領域，具體涉及一種多量級線卡的fib表分解方法。

背景技術：

核心路由器的轉發表項產生了爆炸式擴增，而傳統路由器中的路由條目採取各塊線卡分別完全存儲全部路由表項的存儲策略，一方面對硬體的存儲空間造成浪費，另一方面給路由器轉發功能的實現帶來極大負擔。傳統模型下，路由器的多塊線卡能容納的路由條目數完全相同。

部分存儲相對於完全存儲，是將全部路由條目有序的分成若干組，分別存儲在多塊線卡上，每塊線卡上只存儲完整路由表的一部分。dsf存儲模型依據ip前綴若干bit位進行轉發表分解存儲，將完整路由表分解成若干組存儲在多個線卡中，從而達到路由表的部分存儲。這種存儲方式將全部路由條目按照線卡個數分配，但由於條目前綴的前幾位不一定均衡，所以dsf也存在各個線卡存儲條目不一定均勻的缺陷。

技術實現要素：

本發明旨在至少解決上述技術問題之一。

為此，本發明的目的在於提出一種多量級線卡的fib表分解方法。

為了實現上述目的，本發明的實施例公開了一種多量級線卡的fib表分解方法，包括以下步驟：s110：獲取所有線卡的飽和度，選擇飽和度最低的線卡為選定線卡；s120：根據設定的存儲允許範圍計算所述選定線卡的剩餘可存儲條目；s130：層序遍歷路由生成樹以獲取與所述選定線卡的剩餘可存儲條目相等的節點；s140；將選定子樹移至所述選定線卡中進行存儲，並刪除所述路由生成樹中已經存儲的子樹；s150：重複s110-s140，直至將所述路由生成樹的全部節點分解存儲在多個線卡中。

根據本發明實施例的多量級線卡的fib表分解方法，通過分解存儲完整路由表的一部分，達到完整fib表的分解存儲，以減少由於傳統路由器中各塊線卡分別完全存儲全部路由表項的存儲策略造成對硬體的存儲空間的浪費；同時降低路由器轉發的負擔。

另外，根據本發明上述實施例的基於多量級線卡的fib表分解方法，還可以具有如下附加的技術特徵：

進一步地，各個線卡的存儲容量各不相同，其中，定義線卡存儲飽和度linecardsauration(ls)，即所述線卡存儲飽和度為單獨線卡存儲量佔容量的百分比。

進一步地，對於任一線卡的存儲條件為，初始路由表條目n限制：1<n<c*tls，其中，tls表示預設的線卡存儲閾值，c表示線卡存儲容量；任意線卡的存儲可允許飽和度範圍ls<n/c*100％。

進一步地，所述存儲允許範圍收斂於用於表示線卡存儲限度的存儲閾值。

本發明的附加方面和優點將在下面的描述中部分給出，部分將從下面的描述中變得明顯，或通過本發明的實踐了解到。

附圖說明

本發明的優點結合下面附圖對實施例的描述將變得明顯和容易理解，其中：

圖1是本發明一個實施例的基於多量級線卡的fib表分解方法的流程圖；

圖2是本發明一個實施例的路由生成樹的示意圖；

圖3是本發明一個實施例的多個線卡當前存儲容量的示意圖；

圖4是本發明一個實施例的更新後的路由生成樹的示意圖；

圖5是本發明一個實施例的更新後的多個線卡當前存儲容量的示意圖。

具體實施方式

下面詳細描述本發明的實施例，所述實施例的示例在附圖中示出，其中自始至終相同或類似的標號表示相同或類似的元件或具有相同或類似功能的元件。下面通過參考附圖描述的實施例是示例性的，僅用於解釋本發明，而不能理解為對本發明的限制。

在本發明的描述中，需要理解的是，術語「第一」、「第二」僅用於描述目的，而不能理解為指示或暗示相對重要性。

參照下面的描述和附圖，將清楚本發明的實施例的這些和其他方面。在這些描述和附圖中，具體公開了本發明的實施例中的一些特定實施方式，來表示實施本發明的實施例的原理的一些方式，但是應當理解，本發明的實施例的範圍不受此限制。相反，本發明的實施例包括落入所附加權利要求書的精神和內涵範圍內的所有變化、修改和等同物。

以下結合附圖描述本發明。

圖1是本發明實施例的基於多量級線卡的fib表分解方法的流程圖。如圖1所示，一種基於多量級線卡的fib表分解方法，包括以下步驟：

s110：獲取所有線卡的飽和度，選擇飽和度最低的線卡為選定線卡。

s120：根據設定的存儲允許範圍計算選定線卡的剩餘可存儲條目。s130：層序遍歷路由生成樹以獲取與選定線卡的剩餘可存儲條目相等的節點。

s140：將選定子樹移至所述選定線卡中進行存儲，並刪除所述路由生成樹中已經存儲的子樹。

s150：重複s110-s140，直至將路由生成樹的全部節點分解存儲在多個線卡中。

在本發明的一個實施例中，在所有線卡中，各個線卡的存儲容量各不相同。其中，為了以相同的標準表示不同線卡的已存儲量，定義線卡存儲飽和度linecardsauration(ls)，即單獨線卡存儲量佔容量的百分比。。

在本發明的一個實施例中，對於任一線卡的存儲條件為：

初始路由表條目n限制：1<n<c*tls，其中，tls表示預設的線卡存儲閾值，c表示線卡存儲容量；

任意線卡的存儲可允許飽和度範圍ls<n/c*100％。

在本發明的一個實施例中，存儲允許範圍收斂於表示線卡存儲限度的存儲閾值。

在本發明的一個實施例中，當n超過tls*c時，採取終端路由聚合的方式使n控制在範圍之內。

為使本領域技術人員進一步理解本發明，將通過以下實施例進行詳細說明。

圖2是本發明一個實施例的路由生成樹的示意圖。如圖2所示，其中灰色節點為表項中真實存在的節點，白色節點是為了使生成樹完整而構建的虛擬節點。

圖3是本發明一個實施例的多個線卡當前存儲容量的示意圖。如圖3所示，巡查所有線卡的飽和度，尋找飽和度最小的線卡lc，即選擇飽和度為40％的線卡進行分解存儲。若有若干塊線卡的飽和度相等則默認令lc為硬體餘量大的線卡。

經過計算使m為lc的剩餘可存儲條目，其中m＝lc總條目*lsperlc-lc存量，即不超過臨界值的餘量。

層序遍歷路由生成樹尋找m值，找不到就將m＝m-1重新遍歷生成樹。

假設m＝5尋找到的樹節點，將找到的子樹移至線卡lc，更新線卡lc的存儲值、ls以及路由生成樹。更新後的多個線卡當前存儲容量和路由生成樹的狀態分別如圖4和圖5所示。

重複巡查所有線卡的飽和度至更新線卡之間的步驟，直至將路由生成樹的全部節點分解存儲在多個線卡中。

本發明實施例的基於多量級線卡的fib表分解方法相對於現有技術，存在以下優點：

通過一定分解存儲算法令各個線卡分別存儲完整路由表的一部分，達到完整fib表的分解存儲。

為了進一步達到節能、維持路由表可控的目標，路由器會被設置一個線卡存儲閾值，用以表示線卡存儲可達到的限度。存儲過程中，線卡的存儲飽和度將維持在閾值之下，由此使得每塊線卡即不會過度存儲，也不會浪費過多空間，讓線卡達到特殊情況下的分解均衡。

另外，本發明實施例的多量級線卡的fib表分解方法和系統的其它構成以及作用對於本領域的技術人員而言都是已知的，為了減少冗餘，不做贅述。

在本說明書的描述中，參考術語「一個實施例」、「一些實施例」、「示例」、「具體示例」、或「一些示例」等的描述意指結合該實施例或示例描述的具體特徵、結構、材料或者特點包含於本發明的至少一個實施例或示例中。在本說明書中，對上述術語的示意性表述不一定指的是相同的實施例或示例。而且，描述的具體特徵、結構、材料或者特點可以在任何的一個或多個實施例或示例中以合適的方式結合。

儘管已經示出和描述了本發明的實施例，本領域的普通技術人員可以理解：在不脫離本發明的原理和宗旨的情況下可以對這些實施例進行多種變化、修改、替換和變型，本發明的範圍由權利要求及其等同限定。