[發明專利]使用精確匹配查找引擎轉發具有標識符的分組的系統

有效

• 申請號: 201010109072.1
• 申請日: 2010-02-01
• 公開（公告）號: CN101819580A
• 公開（公告）日: 2010-09-01
• 發明（設計）人: V·L·雅各布森;J·D·索恩頓
• 申請（專利權）人: 帕洛阿爾托研究中心公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L29/12;H04L29/08
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 張濤;李家麟

技術領域

本公開總的涉及促進通過數據網絡的通信。更具體地，本公開涉 及一種用于使精確匹配查找引擎適應于層次結構化可變長度標識符的 方法。

發明內容

一個實施例提供一種用于轉發具有層次結構化可變長度標識符 (HSVLI)的分組的系統，其中計算機包括處理器。在操作期間，該系 統將HSVLI轉換成若干固定長度的地址，其中HSVLI指示一條內容并 且被層次結構化，并且包括從最普通級別到最特定級別排序的連續分 量。另外，各個標識符的長度不是固定的。該系統還通過至少基于固 定長度地址執行多次精確匹配查找來執行有效最長前綴匹配查找。

在對這個實施例的變型中，將HSVLI轉換成若干固定長度地址涉 及生成HSVLI的若干前綴，其中各個前綴指示從處于最普通級別的分 量開始的一個或更多連續分量。該系統還將HSVLI的每個前綴轉換成 至少一個固定長度地址。

在進一步的變型中，轉換每個前綴涉及：用該固定長度地址中的 預定數量的位來指示該前綴中的分量的數量；以及用該固定長度地址 中的其余位來指示從該前綴中導出的散列值。

在進一步的變型中，執行有效最長前綴匹配涉及從最短前綴到最 長前綴迭代地執行以下操作：使用精確匹配查找來確定與各前綴對應 的固定長度地址的轉發信息；以及選擇與具有最多分量的前綴相關聯 的轉發信息，該具有最多分量的前綴已經用精確匹配查找確定。

在進一步的變型中，轉發信息指示至少一個輸出端口。

在進一步的變型中，所述精確匹配查找返回包括以下指示中的一 個或更多的結果：是否發現匹配；是否發現匹配以及針對具有附加分 量的前綴是否可獲得進一步的匹配；為了針對具有附加分量的前綴獲 取進一步的匹配而需要的附加分量的數量；以及與針對該前綴的匹配 對應的字面值(literal?value)，其中所述字面值能夠被加載到該固 定長度地址的若干保留位中，從而促進隨后查找以及減小地址沖突的 機會。

在對這個實施例的變型中，精確匹配查找引擎包括散列表、直接 查找陣列以及二元內容可尋址內存(CAM)中的一個或更多。

在對這個實施例的變型中，HSVLI中的分量包括可全球路由名稱、 組織名稱、版本標識符和摘要中的一個或更多。

附圖說明

圖1說明了依據實施例的示例性網絡，其中分組具有層次結構化 可變長度標識符(HSVLI)。

圖2說明了依據實施例的用于使精確匹配查找引擎適應于HSVLI 的示例性系統的體系結構。

圖3介紹了說明依據本發明一個實施例的使用精確匹配查找引擎 執行HSVLI的有效最長前綴匹配查找的過程的流程圖。

圖4介紹了說明依據實施例的將HSVLI轉換成若干固定長度地址 的過程的流程圖。

圖5介紹了說明依據實施例的轉換各前綴的過程的流程圖。

圖6說明了依據實施例的被轉換成若干固定長度地址的示例性 HSVLI。

圖7介紹了說明依據實施例的使用具有所述若干固定長度地址的 精確匹配查找引擎執行有效的最長前綴匹配的過程的流程圖。

圖8A說明了依據實施例的精確匹配查找引擎的示例性概念視圖。

圖8B說明了依據本發明一個實施例的用于使用查找結果以促進 HSVLI的隨后查找的示例性機構。

圖9說明了依據實施例的用于轉發具有HSVLI的分組的示例性設 備。

在這些圖中，相似的參考數字指代相同的附圖元件。

具體實施方式

在本發明的實施例中，使精確匹配查找引擎適于執行針對可變長 度標識符的最長前綴匹配的問題是通過對所述標識符執行變散列操作 (hash)而成為多個固定長度密鑰來解決的。本發明的實施例涉及使 固定長度地址(諸如以太網MAC地址)的現有精確匹配查找引擎適于 對層次結構化可變長度標識符(HSVLI)執行最長前綴匹配查找。

HSVLI指示一條內容，被層次結構化，并且包括從最普通級別到最 特定級別排序的連續分量。各個HSVLI的長度不是固定的。本發明的 實施例涉及對HSVLI執行變散列操作而成為可與精確匹配引擎一起使 用的多個固定長度密鑰，從而促進通過使用現有網絡設備進行快速轉 發。因此，該系統能夠使用修改的精確匹配交換設備-諸如以太網交 換機-來基于最長前綴匹配轉發具有HSVLI的分組。