[發明專利]IPv6地址存儲和查找方法及相關設備

有效

• 申請號: 201010212943.2
• 申請日: 2010-06-30
• 公開（公告）號: CN101945139A
• 公開（公告）日: 2011-01-12
• 發明（設計）人: 胡松;黃友俊;李星;吳建平;郭志強
• 申請（專利權）人: 賽爾網絡有限公司
• 主分類號: H04L29/12
• 分類號: H04L29/12
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 趙偉

技術領域

本發明涉及下一代互聯網領域，更具體地，涉及一種IPv6地址存儲和查找方法及相關設備。

背景技術

眾所周知，IPv6地址長度是128比特，而IPv4地址長度是32比特。就地址長度而言，IPv6比IPv4擴大了4倍；就容量而言，則擴大了2⁹⁶倍。由于IPv6地址容量的急劇增長，因此需要一種高效可行的IPv6地址存儲和查找方式。

發明內容

本發明提出了一種IPv6地址存儲和查找方法及相關設備，可以在使用有限內存的情況下實現IPv6地址的高速查找。

根據本發明的一個方面，提供了一種IPv6地址存儲方法，包括：判斷IPv6地址的網絡前綴的長度是否為128比特；如果是，則將IPv6地址存儲在第一存儲區域中；否則，將IPv6地址存儲在第二存儲區域中。

優選地，將IPv6地址存儲在第一存儲區域中的步驟包括：對IPv6地址進行散列運算并存儲到第一存儲區域中，第一存儲區域具有由散列結構和紅黑樹rbtree結構形成的混合結構。

優選地，將IPv6地址存儲在第二存儲區域中的步驟包括：將IPv6地址分為第一部分和第二部分，并分別存儲到第二存儲區域的第一部分和第二部分中，第二存儲區域具有變步長多分支trie樹結構。

優選地，第二存儲區域的第一部分和第二部分分別存儲IPv6地址的前64比特和后64比特，第二存儲區域的第一部分的步長為16比特，第二存儲區域的第二部分的步長為8比特。

優選地，該方法還包括：在配置128比特的IPv6地址訪問權限屬性時，如果IPv6地址的訪問權限屬性與所屬網段的訪問權限屬性相同，則對IPv6地址進行散列運算，在對應的紅黑樹rbtree結構中查找對應節點，并且如果找到該對應節點，則將其刪除。

根據本發明的另一方面，提供了一種IPv6地址查找方法，包括：判斷IPv6地址的網絡前綴的長度是否為128比特；如果是，則在第一存儲區域中查找該IPv6地址；否則，在第二存儲區域中查找該IPv6地址。

優選地，第一存儲區域具有由散列結構和紅黑樹rbtree結構形成的混合結構，第二存儲區域具有變步長多分支trie樹結構。

更優選地，第二存儲區域包括具有第一步長的第一部分和具有第二步長的第二部分，第二存儲區域的第一部分和第二部分分別存儲IPv6地址的前64比特和后64比特，第二存儲區域的第一部分的步長為16比特，第二存儲區域的第二部分的步長為8比特。

根據本發明的又一方面，提供了一種IPv6接入控制網關，包括：存儲單元，用于存儲IPv6地址，所述存儲單元具有第一存儲區域和第二存儲區域；以及地址處理單元，判斷IPv6地址的網絡前綴的長度是否為128比特，如果是，則在存儲單元的第一存儲區域中對IPv6地址進行存儲或查找；否則，在存儲單元的第二存儲區域中對IPv6地址進行存儲或查找。

優選地，第一存儲區域具有由散列結構和紅黑樹rbtree結構形成的混合結構，第二存儲區域具有變步長多分支trie樹結構，第二存儲區域包括具有第一步長的第一部分和具有第二步長的第二部分，第二存儲區域的第一部分和第二部分分別存儲IPv6地址的前64比特和后64比特，第二存儲區域的第一部分的步長為16比特，第二存儲區域的第二部分的步長為8比特。

與現有技術相比，本發明的優點主要在于：可以在使用有限內存下實現地址的高速查找。通過對IPv6地址網絡前綴長度的不同進行分級存儲，采用hash+rbtree以及變步長多分支trie樹存儲結構，可以在有效減少存儲容量的同時提高查找效率。

附圖說明

通過下面結合附圖說明本發明的實施例，將使本發明的上述及其它目的、特征和優點更加清楚，其中：

圖1示出了本發明中的IPv6地址存儲方法中的A存儲區域的示意圖；

圖2示出了本發明中的IPv6地址存儲方法中的B存儲區域的示意圖；

圖3示出了根據本發明的IPv6地址存儲方法的流程圖；

圖4示出了圖3中所示的IPv6地址存儲方法中在A存儲區域中進行存儲的方法的詳細流程圖；以及

圖5示出了根據本發明一個實施例的IPv6接入控制網關的框圖。

具體實施方式

為了清楚詳細的闡述本發明的實現過程，下面給出了一些本發明的具體實施例。參照附圖對本發明的實施例進行詳細說明，在描述過程中省略了對于本發明來說是不必要的細節和功能，以防止對本發明的理解造成混淆。

本說明書中所涉及的技術術語的定義：

A存儲區域----