(57)【要約】【課題】受信したパケットを処理するパイプライン化されたパケット処理アーキテクチャを有するパケット交換ノードを提供すること。【解決手段】受信して決定されたパケットフレームタイプに固有の、パケットアドレス情報を含むパケットヘッダフィールド値を選択的に抽出し、それがパケットについて実行される初期アクションを決め、パケット交換ノードによって追跡されるパケット交換情報を、パケットアドレス情報に基づいて探索し、パケットを複数のパケットフローの1つに分類し、分類されたパケットフロー、および入力ポートに対応するデフォルトポートアクションのうちの1つに基づいて、初期交換応答を変更し、パケットヘッダを変更し、交換応答に基づいてパケットを処理する。本発明の利点は、不適当なパケットに関して処理の残りを簡略化できるパイプライン化パケット処理から得られる。【選択図】図１
2006020317.tif 000002
【特許請求の範囲】
【請求項１】
複数のパケット交換ノード送信元ポートを介して受信するパケットを処理するためのパイプライン化されたパケット処理アーキテクチャを有するパケット交換ノードであって、
a.前記パケットが受信された前記送信元ポートと、先に決定されたパケットフレームタイプとの一方に基づいて、各パケットによって運ばれる複数のパケットヘッダフィールド値から、パケットヘッダフィールド値を選択的に抽出するパケットヘッダフィールド値抽出器と、
b.一致タイプを前記パケットに割り当てる手段であって、前記一致タイプは、パケットフレームのフォーマットには無関係に、前記抽出されたパケットヘッダフィールド値に基づいて、前記パケットを事前分類する手段と、
c.前記パケットについての初期交換応答を定式化するため、抽出されたパケットヘッダフィールド値、前記一致タイプ、および前記送信元ポートのうちの1つに基づいて、前記パケット交換ノードによって追跡されるパケット交換情報、パケットルーティング情報、およびプロトコル仮想ローカルエリアネットワーク情報のうちの1つを探索する手段と、
d.送信元ポート識別子、前記初期交換応答、抽出されたパケットヘッダフィールド値、および前記一致タイプのうちの1つに基づいて、前記パケットを複数のパケット処理フローの1つに分類するパケット分類器とを含むパケット交換ノード。
【請求項２】
各受信パケットの前記パケットフレームタイプを決定する手段であって、前記フレームタイプは、パケットフレームのフォーマットに基づいて前記パケットを事前分類する手段をさらに含む、請求項1に記載のパケット交換ノード。
【請求項３】
前記パケットフレームタイプを決定する前記手段が、
a.パケットヘッダビット値を検査するためのハードウェアロジックと、標準化パケットヘッダビットパターンを認識するためのハードウェアロジックとを有するハードウェアフレームタイプ識別エンジンと、
b.パケットヘッダフィールド値を複数の規則に連続的に条件付きで従わせるためのハードウェアロジックを有する連続フレームタイプ除去エンジンと、
c.パケットヘッダ領域との比較のための複数のパケットヘッダテンプレートを含むテンプレート照合フレームタイプ識別エンジンとのうちの1つ含む、請求項2に記載のパケット交換ノード。
【請求項４】
前記連続フレームタイプ除去エンジンが、
a.送信元ポートごとのディシジョンツリー解析エンジンと、
b.各ディシジョンテーブルが、複数のディシジョンテーブルレコードを有し、各ディシジョンテーブルレコードは、フレームタイプ識別ビットパターンのパケットヘッダオフセット、フレームタイプ識別テストビットパターン、および後続ディシジョンテーブルレコードのディシジョンテーブル行インデックスを指定するジャンプ命令とフレームタイプ識別子との一方を指定する、送信元ポートごとのディシジョンテーブルとの一方を含む、請求項3に記載のパケット交換ノード。
【請求項５】
前記ハードウェアフレームタイプ識別エンジンと、前記連続フレームタイプ除去エンジンと、前記テンプレート照合フレームタイプ識別エンジンとのうちの少なくとも2つが、異なるフレームタイプを識別した場合、フレームタイプを選択するためのフレームタイプ選択器をさらに含む、請求項3に記載のパケット交換ノード。
【請求項６】
前記ヘッダフィールド値抽出器が、各々がパケットヘッダフィールドオフセットを指定する、フレームタイプでインデックスされる複数の抽出テーブルレコードを有する抽出検索テーブルをさらに含む、請求項1に記載のパケット交換ノード。
【請求項７】
一致タイプを割り当てる前記手段が、各抽出テーブルレコード用の一致タイプ指定子を含む、請求項6に記載のパケット交換ノード。
【請求項８】
前記ヘッダフィールド値抽出器が、前記パケットについて実行される初期アクションを決める手段をさらに含み、各抽出テーブルレコードが、初期アクション指定子をさらに含む、請求項7に記載のパケット交換ノード。
【請求項９】
前記ヘッダフィールド値抽出器が、前記パケットに関して実行される初期アクションを決める手段をさらに含む、請求項1に記載のパケット交換ノード。
【請求項１０】
パケット交換情報、パケットルーティング情報、およびプロトコル仮想ローカルエリアネットワーク情報のうちの1つを探索する手段が、
a.交換情報データベースと対話するレイヤ2探索エンジンと、
b.ルーティング情報データベースと対話するレイヤ3探索エンジンと、
c.仮想エリアネットワークテーブルと対話する仮想ローカルエリアネットワーク探索エンジンとを含む、請求項1に記載のパケット交換ノード。
【請求項１１】
前記パケット分類器が、分類規則エントリを有する分類規則テーブルをさらに含み、各分類規則エントリは、一致タイプに固有のフォーマットを有し、各分類規則エントリは、前記エントリで指定された条件が満たされた場合、条件付きで前記パケットに関連づけられる処理フロー識別子を指定し、各分類規則エントリは、前記規則エントリの優先権を指定する規則重みを任意選択で指定する、請求項1に記載のパケット交換ノード。
【請求項１２】
a.前記送信元ポート、前記フレームタイプ、および前記処理フロー分類のうち1つに基づいて、とるべきアクションを決定する手段と、
b.前記アクションに基づいて、前記初期交換応答を選択的に変更する交換応答変更器と、
c.前記アクションに基づいて、前記パケットヘッダを選択的に変更するパケットヘッダ変更器と、
d.前記交換応答に基づいて、前記パケットを処理する手段とをさらに含む、請求項1に記載のパケット交換ノード。
【請求項１３】
パイプライン化されたパケット処理アーキテクチャを有するパケット交換ノードの複数の送信元ポートを介して受信するパケットを処理するための方法であって、
a.前記パケットが受信された前記送信元ポートと、先に決定されたパケットフレームタイプとの一方に基づいて、各パケットによって運ばれる複数のパケットヘッダフィールド値から、パケットヘッダフィールド値を選択的に抽出するステップと、
b.パケットフレームのフォーマットには無関係に、前記抽出されたパケットヘッダフィールド値に基づいて、前記パケットを事前分類し、前記パケットに一致タイプを割り当てるステップと、
c.前記パケットについての初期交換応答を定式化するため、抽出されたパケットヘッダフィールド値、前記一致タイプ、および前記送信元ポートのうちの1つに基づいて、前記パケット交換ノードによって追跡されるパケット交換情報、パケットルーティング情報、およびプロトコル仮想ローカルエリアネットワーク情報のうちの1つを探索するステップと、
d.送信元ポート識別子、前記初期交換応答、抽出されたパケットヘッダフィールド値、および前記一致タイプのうちの1つに基づいて、前記パケットを複数のパケット処理フローの1つに分類するステップとを含む方法。
【請求項１４】
パケットフレームのフォーマットに基づいて、各受信パケットを事前分類する事前ステップと、フレームタイプを前記パケットに割り当てる事前ステップとをさらに含む、請求項13に記載の方法。
【請求項１５】
a.パケットヘッダビット値を検査し、標準化パケットヘッダビットパターンを認識するステップと、
b.パケットヘッダフィールド値を複数の規則に連続的に条件付きで従わせるステップと、
c.パケットヘッダ領域をパケットヘッダテンプレートと比較するステップとのうちの1つによって、前記パケットのフレームタイプを決定するステップをさらに含む、請求項14に記載の方法。
【請求項１６】
パケットヘッダフィールド値を複数の規則に連続的に条件付きで従わせるステップで、
a.ディシジョンテーブルに保存された複数のディシジョンテーブルレコードで指定されるパケットヘッダオフセットに基づいてパケットヘッダから抽出されたパケットヘッダフィールド値を、前記ディシジョンテーブルレコードで指定されるフレームタイプ識別テストビットパターンに従わせるステップと、
b.確定的なフレームタイプ決定に達しなかった場合、前記複数のディシジョンテーブルレコードから後続ディシジョンテーブルレコードを選択的に選択し、それ以外の場合、前記ディシジョンテーブルレコードで指定されるフレームタイプを割り当てるステップとをさらに含む、請求項15に記載の方法。
【請求項１７】
パケットヘッダビット値を検査し、標準化パケットヘッダビットパターンを認識するステップと、パケットヘッダフィールド値を複数の規則に連続的に条件付きで従わせるステップと、パケットヘッダ領域をパケットヘッダテンプレートと比較するステップとのうちの少なくとも2つが、異なるフレームタイプを生じさせる場合、フレームタイプを選択するステップをさらに含む、請求項15に記載の方法。
【請求項１８】
各パケットによって運ばれる複数のパケットヘッダフィールド値から、パケットヘッダフィールド値を選択的に抽出するステップの後で、前記パケットに関して実行される初期アクションを決めるステップをさらに含む、請求項13に記載の方法。
【請求項１９】
前記パケット交換ノードによって追跡されるパケット交換情報、パケットルーティング情報、およびプロトコル仮想ローカルエリアネットワーク情報のうちの1つを探索するステップで、
a.交換情報データベースに問い合せを行うステップと、
b.ルーティング情報データベースに問い合せを行うステップと、
c.仮想エリアネットワークテーブルに問い合せを行うステップをそれぞれ含む、請求項13に記載の方法。
【請求項２０】
前記パケットを複数のパケット処理フローの1つに分類するステップで、複数の分類規則エントリの1つで指定される条件に基づいて、条件付きで前記パケットに処理フロー識別子を関連づけるステップをさらに含む、請求項13に記載の方法。
【請求項２１】
a.前記送信元ポート、前記フレームタイプ、および前記処理フロー分類のうち1つに基づいて、とるべきアクションを決定するステップと、
b.前記アクションに基づいて、前記初期交換応答を選択的に変更するステップと、
c.前記アクションに基づいて、前記パケットヘッダを選択的に変更するステップと、
d.前記交換応答に基づいて、前記パケットを処理するステップとをさらに含む、請求項13に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット交換通信に関し、詳細には、結合パイプライン化探索および分類方法および装置に関する。
【背景技術】
【０００２】
パケット交換通信の分野では、通信ネットワークに関与する送信元ネットワークノードと宛先ネットワークノードの間で伝送される内容は、転送のためにパケットに区分化される。パケットは、パケットヘッダと内容ペイロードを含む構造を有する。交換ネットノードなどの、ただし、これに限定されない、送信元ネットワークノードと宛先ネットワークノードの間の経路上の通信ネットワークノードは、パケットヘッダ内で指定される情報に基づいて、各パケットを受信し、蓄積し、検査し、処理し、転送する。このような動作モードは、非決定論的な蓄積および転送パケット交換として知られている。
【０００３】
交換ネットワークノードは、複数のポートをもつネットワークノードである。入力ポートを介して受信した各蓄積パケットの処理には、蓄積パケットを送り出すのに用いる少なくとも1つの出力ポートを決定することが含まれる。少なくとも1つの出力ポートを決定し、その後、決定された少なくとも1つの出力ポートを介して実際に転送を行うことは、パケット交換として知られている。一般的な交換ネットワークノードの重要な特性、および通信ネットワークのコアで利用される交換ネットワークノードの要件として、出力帯域が許すのであれば、蓄積および転送パケット交換は、処理を進めながら、着信の回線/ワイヤ速度で実行されるというものがある。このような要件はもっともなものではあるが、実際上、当技術分野における昨今の数々の技術進歩にもかかわらず、また数々の技術進歩のせいで、達成することは難しい。
【０００４】
パケット交換通信の歴史および開発は、非常に多岐にわたり、有線、無線、光物理転送など、物理レイヤ1における複数の技術の使用、イーサネット（登録商標）技術を含む、データリンクレイヤ2における複数のカプセル化技術の使用、インターネットプロトコル(IP)、インターネット制御メッセージプロトコル(ICMP)などを含む、ネットワークレイヤ3における複数の伝送プロトコルの使用が含まれる。IPオーバーイーサネット（登録商標）技術が、最も広く普及している。
【０００５】
例えば、標準的なIP/イーサネット（登録商標）は、非決定論的なベストエフォートのパケット転送を提供する。非決定論的な特性は、障害を起こした通信ネットワークインフラストラクチャを回避する自立的な経路変更を提供するが、ベストエフォートの特性は、送信元ネットワークノードと宛先ネットワークノードの間でパケットを(タイミングを外さず)確実に転送することに関して何ら保証を与えない。消失パケットを識別し、消失パケットの再送を要求する手段を提供するには、伝送制御プロトコル(TCP)がさらに利用される。タイムリーなパケット転送は、トラフィック/サービスの区別化によって対処され、送信元ネットワークノードと宛先ネットワークノードの間の中間通信ネットワークノードにおける優先的パケット処理を通じて提供される。
【０００６】
回線/ワイヤ速度でパケット交換を持続的に行うことに関する上記の問題のすべてに対処することは難しい。この件についての理論的発展は、そのような交換ネットノードが構成できることを保証しているが、それを実際に実施するとなると、高い開発、実装、および検証コストが足枷となるばかりか、様々な実装上の複雑さも妨げとなる。当技術分野の発展が速いため、交換ネットワークノードは、マルチプロトコルの最短長パケットを処理しながら、回線/ワイヤ速度で動作する必要があるだけでなく、将来の技術発展を考慮し、装置が時代遅れになることを遅らせるために、適度な柔軟性を備えることも望まれる。
【０００７】
2002年5月9日に公衆に利用可能となった、公開番号2002/54604 A1の「Network Switching Architecture with Fast Filtering Processor」と題する従来技術の米国特許出願において、Kadambiらは、入力ポートを介して受信したパケットをフィルタリングする方法および装置について説明している。パケットを廃棄するかどうかの決定に達するパケット処理は、パケットフィルタリングとして知られている。Kadambiらは、別々の開発が可能なようにモジュール化された交換ネットワークノード機能をシングルチップ上に実装することについて教示しているが、各ポートで実施されるフィルタリングは、ポートモジュール間の内部通信を提供する、複雑な調停の対象となる3つで1組のチャネルを必要とするので、説明されている実装は、複雑で扱いが難しい。パケットフィルタリング自体は、パケット交換を行わず、不必要なパケット処理を減らす手段を提供するだけである。いくつかのセキュリティ上の事柄も、パケットフィルタリングによって対処され、それが、パケットフィルタリングのまた別の重要性となっている。ポートベースのフィルタリングは、回線/ワイヤ速度でのパケットフィルタリングを非常にうまく行うことができるが、フィルタリングだけでは、交換ネットワークノードにおけるパケット処理に関する上述したその他の問題に対処できない。
【０００８】
2004年2月24日にYikら(うち何人かは本明細書に発明者として挙名されている)に付与され、参照により本明細書に組み込まれる、「High Speed MAC Address Search Engine」と題する、同時譲渡された米国特許第6697873 B1号は、交換ネットワークノードなどの通信ネットワークノードにおいて、ネットワークノードアドレスを保存し、探索するための装置および方法について説明している。この装置は、MACアドレスを保存し、探索するための媒体アクセス制御(MAC)アドレステーブルを2つ備えている。プライマリMACアドレステーブルは、MACアドレスに対応する圧縮された値を指定するレコードを保存し、各レコードは、ハッシュMACアドレス値をインデックスに使用して参照される記憶ロケーションに保存される。複数のMACアドレスが同一インデックスにハッシュされ、その結果、プライマリMACアドレステーブルの同一ロケーションに割り当てられることから生じ得る探索衝突に対処するため、プライマリMACアドレステーブルの各レコードはさらに、セカンダリMACアドレステーブルに保存された対応するレコードのチェーンにリンク付けされる。セカンダリMACアドレステーブルのレコードは、すべてのMACアドレスを指定する。交換ネットワークノードにおけるMACアドレスの保存は、パケットを交換するのに必要な処理を減らすうえで重要であり、MACアドレステーブルのレコードは、同じアドレスをもつパケットについて以前決定された出力ポートも含んでいる。MACアドレステーブルからMACアドレスレコードを高速に取り出すことは、高速パケット交換を達成するうえで重要である。Yikらによって説明される実施では、MACアドレス検索テーブルの実装コストとMACアドレス探索の速度とが、うまくバランスしている。
【０００９】
2003年12月31日にBarrakら(うち何人かは本明細書に発明者として挙名されている)によって出願され、参照により本明細書に組み込まれる、「High Speed MAC Address Search Engine」と題する、同時係属中の同時譲渡された米国特許出願第10/750445号は、交換ネットワークノードなどの通信ネットワークノードにおいて、ネットワークノードアドレスを保存し、探索するための改良装置および方法について説明している。この装置は、MACアドレスを保存し、探索するための媒体アクセス制御(MAC)アドレステーブルを2つ備えている。パケット交換プロセッサの外部に存在するプライマリMACアドレステーブルは、MACアドレスに対応する圧縮された値を指定するレコードを保存し、2以上のレコードが、ハッシュMACアドレス値をインデックスに使用して参照される記憶ロケーションに保存される。プライマリMACアドレステーブルを外部記憶装置とすることで、広大な記憶域を提供する既製品のメモリを使用することが可能になり、これによって、交換プロセッサと外部メモリの間のデータ転送に伴うオーバーヘッドは埋め合わされる。複数のMACアドレスが同一インデックスにハッシュされることから生じ得る探索衝突に対処するため、プライマリMACアドレステーブルの各レコードはさらに、セカンダリMACアドレステーブルに保存された対応するレコードのチェーンにリンク付けされる。セカンダリMACアドレステーブルのレコードは、セカンダリMACアドレステーブルがパケット交換プロセッサと同じマイクロチップダイ上に実装される場合には特に、セカンダリMACアドレステーブルの記憶要件を最低限に抑えるために、圧縮されたMACアドレスを指定する。
【特許文献１】米国特許出願第2002/54604 A1号
【特許文献２】米国特許第6697873 B1号
【特許文献３】米国特許出願第10/750445号
【特許文献４】米国特許出願第10403110号
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上で説明した交換性能を改善するための開発は大きな進歩ではあるが、特により高いポート密度をサポートしながら、交換性能をさらに改善するには、上で述べた問題にまだ対処していく必要がある。
【課題を解決するための手段】
【００１１】
本発明の一態様によれば、柔軟なヘッダ解析方式が提供され、その方式では、最大回線/ワイヤ速度で着信するパケットの特定のパケットヘッダビットパターンの検査に基づいて、様々なフレームタイプを決定するために、3つのヘッダ解析エンジンが並列に利用される。3つのヘッダ解析エンジンを利用することで、柔軟性が提供され、ハードウェアエンジンは、標準的なよく知られたフレームタイプ用の高速フレームタイプ識別を提供し、構成可能ディシジョンツリー解析エンジンは、連続フレームタイプ除去プロセスを通じてフレームタイプを決定し、構成可能テンプレート照合エンジンは、ビットテンプレートの比較を実行する。
【００１２】
本発明の別の態様によれば、最低限かつ高速の前処理を確保するフレームタイプ決定の後、パケットヘッダフィールド値が、パケットヘッダから抽出される。ユーザ構成可能フィールド抽出器が利用される。フレームタイプ毎に、抽出フィールドのオフセットを指定することができる。パケットタイプによっては、パイプラインのこの早期ステージで、パケット処理アクションを決定することができる。
【００１３】
本発明のまた別の態様によれば、レイヤ2の送信元および宛先MACアドレスと、レイヤ3の送信元および宛先IPアドレスとを、アドレステーブルを探索する際に使用される内部インデックスにマッピングすることによって、実施コストが削減される。結合L2およびL3探索エンジンは、抽出されたネットワークアドレスフィールド値を、短いビット長のインデックスにマッピングするため、ハッシュベースの探索方式を利用する。
【００１４】
本発明のさらに別の態様によれば、仮想ローカルエリアネットワーク識別子(VLAN ID)挿入、VLAN再マッピング、サービスタイプ(TOS)再マッピング、サービス品質(QoS)実施、フィルタリング、転送、およびヘッダ変更を含むが、これらに限定されない、最終アクションは、パケットがどのタイプに分類されたかによる。
【００１５】
本発明の一態様によれば、パイプライン化されたパケット処理アーキテクチャを有するパケット交換ノードが提供される。パケット交換ノードは、パケット交換ノードの入力ポートを介して受信したパケットのパケットフレームタイプを決定する手段と、パケットフレームタイプに固有のパケットヘッダフィールド値を選択的に抽出する手段であって、抽出されたパケットヘッダフィールド値がパケットアドレス情報を含む手段と、パケットについて実行される初期アクションをパケットに基づいて決める手段と、抽出されたパケットアドレス情報に基づいて、パケット交換ノードによって追跡されるパケット交換情報を探索する手段と、パケットについての初期交換応答を定式化する手段とを含む。パケット分類器は、パケットを複数のパケットフローの1つに分類する。交換応答変更器は、初期アクション、パケットが分類されたパケットフロー、および入力ポートに対応するデフォルトポートアクションのうちの1つに基づいて、初期交換応答を変更する。パケットヘッダ変更器は、初期アクション、パケットフロー、およびデフォルトポートアクションのうちの1つに基づいて、パケットヘッダを変更する。パケット交換ノードはさらに、交換応答に基づいて、パケットを処理する手段を含む。
【００１６】
本発明の別の態様によれば、パケット交換ノードで入力ポートを介して受信されるパケットを処理する方法が提供される。受信パケットのパケットフレームタイプが決定される。パケットフレームタイプに固有のパケットヘッダフィールド値が、選択的に抽出され、抽出されたパケットヘッダフィールド値は、パケットアドレス情報を含む。パケットについて実行される初期アクションは、パケットに基づいて決められる。パケット交換ノードによって追跡されるパケット交換情報は、抽出されたパケットアドレス情報に基づいて探索される。初期交換応答が定式化される。パケットは、複数のパケットフローの1つに分類される。初期交換応答は、初期アクション、パケットが分類されたパケットフロー、および入力ポートに対応するデフォルトポートアクションのうちの1つに基づいて変更される。パケットヘッダは、初期アクション、パケットフロー、およびデフォルトポートアクションのうちの1つに基づいて変更される。パケットは、交換応答に基づいて処理される。
【００１７】
本発明のまた別の態様によれば、多数のパケット交換ノード送信元ポートを介して受信されたパケットを処理するための、パイプライン化されたパケット処理アーキテクチャを有するパケット交換ノードが提供される。パケット交換ノードは、パケットが受信された送信元ポートと、先に決定されたパケットフレームタイプとの一方に基づいて、各パケットによって搬送される多数のパケットヘッダフィールド値からパケットヘッダフィールド値を選択的に抽出するためのパケットヘッダフィールド値抽出器を含む。パケット交換ノードはさらに、一致タイプをパケットに割り当てる手段を含み、一致タイプは、パケットフレームのフォーマットには無関係に、抽出されたパケットヘッダフィールド値に基づいて、パケットを事前分類する。パケット交換ノードはさらに、パケットについての初期交換応答を定式化するため、抽出されたパケットヘッダフィールド値、一致タイプ、および送信元ポートのうちの1つに基づいて、パケット交換ノードによって追跡されるパケット交換情報、パケットルーティング情報、およびプロトコル仮想ローカルエリアネットワーク情報のうちの1つを探索する手段を含む。パケット分類器は、送信元ポート識別子、初期交換応答、抽出されたパケットヘッダフィールド値、および一致タイプのうちの1つに基づいて、パケットを多数のパケット処理フローの1つに分類する。
【００１８】
本発明のさらに別の態様によれば、パイプライン化されたパケット処理アーキテクチャを有するパケット交換ノードの複数の送信元ポートを介して受信されるパケットを処理する方法が提供される。パケットが受信された送信元ポートと、先に決定されたパケットフレームタイプとの一方に基づいて、パケットヘッダフィールド値が、各パケットによって搬送される複数のパケットヘッダフィールド値から選択的に抽出される。パケットは、パケットフレームのフォーマットには無関係に、抽出されたパケットヘッダフィールド値に基づいて事前分類され、一致タイプが、パケットに割り当てられる。パケットについての初期交換応答を定式化するため、パケット交換ノードによって追跡されるパケット交換情報、パケットルーティング情報、およびプロトコル仮想ローカルエリアネットワーク情報のうちの1つが、抽出されたパケットヘッダフィールド値、一致タイプ、および送信元ポートのうちの1つに基づいて探索される。パケットは、送信元ポート識別子、初期交換応答、抽出されたパケットヘッダフィールド値、および一致タイプのうちの1つに基づいて、複数のパケット処理フローの1つに分類される。
【００１９】
本発明の利点は、パケット処理パイプラインの残りを簡略化できるパイプライン化パケット処理と、よく知られたフレームタイプについては高速でありながら、新しいフレームタイプのサポートを柔軟に提供して、特定の実装が時代遅れとなるのを遅らせる柔軟なフレームタイプ決定と、後で後続ステージによって精緻化される処理アクションの早期決定と、ネットワークアドレステーブル記憶要件を緩め、ネットワークアドレステーブルのアクセスにはより少ないデータ転送帯域しか必要とせず、外部プライマリネットワークアドレステーブルには多数のハッシュエントリを、内部セカンダリネットワークアドレステーブルには比較的多数のエントリを保存できるようにする、短いビット長でインデックスされるレイヤ2およびレイヤ3ネットワークアドレスに対して動作する、結合レイヤ2およびレイヤ3ネットワークアドレス探索エンジンと、交換応答の早期決定と、パケット分類ベースの交換応答変更およびパケットヘッダ変更とから得られる。
【００２０】
本発明の特徴および利点は、添付の図面を参照しながら行われる、例示的な実施形態についての以下の詳細な説明から、より明らかとなるであろう。
【００２１】
添付の図面では、同様の特徴には同じ符号が付されていることに留意されたい。
【発明を実施するための最良の形態】
【００２２】
本発明の例示的な一実施形態によれば、フィルタリング、請求書送付、およびサービス品質提供など区別化されたサービスに対するサポートを可能にする、結合パイプライン化パケット分類およびアドレス探索エンジンが提供される。
【００２３】
本発明の例示的な実施形態によれば、パケット分類器の機能の1つは、一般に複数のパケットヘッダフィールド値を検査することによって、パケットをパケットフローに分類することである。パケット分類器によって使用される規則は、どのフィールド値が検査され、どのような値が期待されるかを定める。同じ規則と一致するパケットは、本発明を実施する装置内で、同じパケットフローに属するものとして分類される。そのようなパケットの処理では、パケットを処理する際に同じパケット処理アクションが実行され、それらのアクションは、一般にパケット交換を含む。
【００２４】
本発明の例示的な実施形態によれば、パケット分類と、レイヤ2およびレイヤ3ネットワークアドレス探索は、図1に示すようなステージ化パイプラインアーキテクチャ100を利用して統合される。
【００２５】
本発明の例示的な実施形態によれば、パケットフレームタイプ決定は、パケットヘッダフィールド抽出の前のステージ1によって実行され、パケット処理前のパケットフレーム決定は、パケットヘッダからフィールド値を抽出する際の処理を必要最低限まで少なくする。受信パケットのフレームタイプを識別するため、3つのパケットフレームタイプ決定エンジンが、並列に利用される。本発明の例示的な実施形態の例示的な実施によれば、少なくとも256種のパケットフレームタイプを互いに区別することができるが、本発明はそのように限定されるものではない。パケットフレームタイプ決定エンジンは、各受信パケットの各パケットヘッダ102の部分を検査し、以下のエンジンを含む。
【００２６】
ハードウェアフレームタイプ決定エンジン104は、参照により本明細書に組み込まれる、インターネットエンジニアリングタスクフォース(IETF)によって公表されたIEEE802x規格など、広く受け入れられている規格で標準的に定められたパケットフレームフォーマット用の、非常に高速なパケットフレームタイプ識別を提供する。ハードウェアエンジン104の動作は、ハードウェア設計および製造時に最適化されるが、本発明はそのように限定されるものではない。ハードウェアエンジン104は、一般に一チップ上にハードウェアロジックとして実装されるが、実行時カスタマイズもいくらかは可能である。大幅な実行時カスタマイズは、非常に高速なパケットフレームタイプ決定と、所定のパケットフレームタイプ決定に伴う遅延の抑制とを優先するので行えない。大部分のパケットトラフィックは、標準的なパケットを含み、一般に少なくとも112種のパケットフレームタイプを、最低限の遅延および処理オーバーヘッドしか要さずに識別することができるが、本発明はそのように限定されるものではない。
【００２７】
本発明の例示的な一実施によれば、ハードウェアエンジン104は、例えば、そのフォーマットを以下に示す、VLANタグ付きイーサネット（登録商標）IIカプセル化TCP/IPパケットのパケットフレームタイプなど、標準的なパケットフレームタイプを決定する。
【００２８】
【表１】
2006020317.tif 000003
【００２９】
ハードウェアフレームタイプ決定エンジン104は、以下のように指定されたオフセット(位置)でヘッダフィールド値を照合することによって、VLANタグ付きイーサネット（登録商標）IIカプセル化TCP/IPパケットを識別する。
-第12バイトの値=0x81
-第13バイトの値=0x00
-第16バイトの値=0x08
-第17バイトの値=0x00
-第27バイトの値=0x11
【００３０】
所定のパターンと合致するパケットヘッダフィールド値が見つかった場合、対応するフレームタイプ値が、パケットに関連づけられる。
【００３１】
規格が変更になったり、時代遅れになったりすることがあり得るが、あまりにも早く時代遅れになる可能性に対処する1つの方法は、後で本明細書で説明するように、構成可能フレームタイプ決定エンジン106/108からのフレームタイプ出力を、ハードウェアエンジン104よりも優先することである。
【００３２】
あまりにも早く時代遅れになる可能性に対処する別の方法は、ハードウェアエンジン104の対応するハードウェアロジック部分を無効にすることによって、旧い標準フレームタイプと一致しないようにすることである。このようにすることで、処理オーバーヘッドが必要最低限まで減らされる。しかし、衝突が発生しないのであれば、下位互換性があることは一般に望ましいので、ハードウェアエンジン104のハードウェアロジック部分は、旧い標準フレームタイプ識別が望ましい動作を妨害する場合にだけ、無効にすることができる。
【００３３】
連続フレームタイプ除去プロセスが、ディシジョンツリー解析エンジン106によって実行される。連続フレームタイプ除去によってフレームタイプを区別するのに最適なフレームタイプ間の関係は、「タイプオブ(type-of)」関係である。当技術分野でよく知られているように、レイヤ3のデータグラム(プロトパケット)は、レイヤ2のデータグラム内にカプセル化される。簡単な例として、ディシジョンツリー解析エンジン106は、レイヤ3のヘッダフォーマットは異なるが、レイヤ2のヘッダフォーマットは同じパケットフレームタイプを区別する。したがって、フィールドにおけるディシジョンツリー解析エンジン106の動作をカスタマイズするためにタイプオブ関係を再指定する際、いくらかの柔軟性が提供される。例示的な実施は、ハードウェアエンジン104によって検出されるフレームタイプに加えて、さらに128種までのフレームタイプをサポートすることができるが、本発明はそのように限定されるものではない。
【００３４】
本発明の例示的な実施形態の例示的な実施によれば、フレームタイプ間のタイプオブ関係は、ディシジョンツリーのノード202として例示的に指定される。例示的な2分ディシジョンツリー200が、図2に概略的に示されている。各事前定義されたパケットフレームフォーマットは、特定のシーケンスのテストを適用することによって識別され、シーケンスは、ディシジョンツリー200ノード202間の関係によって指定される。実際に実施されたノード202は、ディシジョンテーブル210のレコード212を含み、各レコード212は、ディシジョンテーブルの行インデックスと関連づけられ、フレームタイプ識別ビットパターンのパケットヘッダオフセット、フレームタイプ識別テストビットパターン、およびジャンプ命令を含む。少なくとも1つのパケットヘッダフィールドに対応するパケットヘッダフィールド値ビットが、特定の無視すべきビットをマスクしたうえで、期待値に等しいかどうかを決定するため、フレームタイプ識別テストビットパターンは、ビットマスク、ビット値、および比較バイナリ値を含むことができる。ジャンプ命令は、連続フレームタイプ除去プロセスが完了したかどうかを指定し、完了していない場合は、ビットパターン照合テストが肯定的結果か、否定的結果かに応じて、次にディシジョンテーブルのどの行インデックスにジャンプすべきかを指定する指定子を含む。本発明の例示的な実施形態の例示的な実施による、以下に示すレコード212の仕様は、各レコード212が保有する例示的な情報を表す。
【００３５】
【表２】
2006020317.tif 000004
【００３６】
記憶空間の効率化は、典型的には、フレームタイプ決定レコード212の終端でフレームタイプ指定に再使用されるジャンプ命令フィールドの場合のように、レコードフィールドを多目的に再使用することによって達成される。
【００３７】
ディシジョンツリー解析エンジン106は、ハードウェアエンジン104と比較した場合、パケットフレームタイプを識別する際に、処理遅延が所定のものとならないことがあるが、タイプオブ関係の指定は、フレームタイプ定義に最低限の記憶域しか必要とせず、ディシジョンツリー解析エンジン106を実施する交換装置の製造後に開発/修正された規格のための、追加/修正標準フレームフォーマットに対するサポートを提供する。
【００３８】
ディシジョンツリー解析エンジン106は、受信パケットのフレームタイプを識別するのに、比較的長い時間を費やすことがあり得る。パケットはヘッダから最初に受信されると仮定して、最小サイズのパケットペイロードを受信するのにかかる時間内で、ディシジョンツリー解析エンジン106が、受信パケットのフレームタイプを識別できるのであれば、ディシジョンツリー解析エンジン106を1つ利用すればよい。ヘッダとペイロードからなる最小サイズのイーサネット（登録商標）パケットは、プリアンブルを考慮した20バイトのフレーム間ギャップを含む64バイトである。回線/ワイヤ速度でのパケット処理を保証するには、比較的少数のディシジョンツリーノード202を調べるだけで、フレームタイプが決定されるように、ディシジョンツリー200を構成しなければならないが、あるいは複数のディシジョンツリー解析エンジン106を利用することもできる。フレームタイプを識別するためにディシジョンツリー解析エンジン106を実施する装置をどう使うつもりかに応じて、平均して、平均パケット到着速度でフレームタイプ決定を完了できれば十分なこともある。
【００３９】
本発明の例示的な実施形態の例示的な実施によれば、ディシジョンツリー解析エンジン106のマイクロコードロジックは、クロックティック当たり1つのテスト(202/204/212/214)を実行することができる。
【００４０】
本発明の例示的な実施形態の例示的な実施によれば、ディシジョンツリー解析エンジン106は、ディシジョンツリー解析器206およびディシジョンテーブル210のマイクロコード実装を含む。
【００４１】
実施に応じて、送信元ポート識別子112が、パイプライン100の第1ステージに提供され、フレームタイプ決定エンジン104、106、108のいずれかが、送信元ポート指定にのみ基づいて決定されるフレームタイプ指定114を提供することができる。特定のポートを介して受信されるパケットのフレームタイプが事前に分かっているときは、送信元ポート識別子ベースのフレームタイプ決定を利用することができる。
【００４２】
本発明の例示的な実施形態の例示的な実施によれば、ディシジョンツリー解析エンジン106はさらに、ポートベースのフレームタイプ決定を実施する。ディシジョンテーブル210はさらに、ディシジョンツリー解析エンジン106を実施する交換装置の入力ポートに対応する行214を含む。本発明の例示的な実施形態の例示的な実施によれば、最初のN個のディシジョンテーブルレコード214は、ディシジョンツリーノード204(複数の開始ポイント)を実装するために利用され、Nは、ディシジョンツリー解析エンジン106を実施する交換システムの入力ポート数に相当する。有利には、パケットが受信される入力ポートに対応する送信元ポート識別子112は、ディシジョンテーブルレコード214を中間処理なしに取り出す際のインデックスとして直接使用することができる。本発明はこの実施に限定されるものではないが、各入力ポート識別子112は、ディシジョンテーブルの行インデックスに、1対1または多対1にマッピングすることができる。
【００４３】
次にディシジョンツリー解析器206は、送信元ポート識別子112(およびヘッダ102)が、パイプラインのステージ1で利用可能になったとき、対応するディシジョンテーブルレコード214を最初に取り出し、ディシジョンツリー解析器206は、その中で指定されるテストを適用する。有利には、連続フレームタイプ除去プロセス用の、入力ポート毎に別々の開始ポイントを表す各ディシジョンツリーノード204について、少なくとも1つのディシジョンテーブルレコード214を、送信元ポート識別子112だけに基づいて早期フレームタイプ決定を提供するフィールド値によって構成することができる。ディシジョンツリーレコード204は、対応する入力ポートにおいて、受信パケットを記述するのに特定のフレームタイプだけが期待される場合、フレームタイプを指定するためにユーザによって構成することができる。トランクポートとって、また特に標準外のパケットフレームフォーマット用の高速フレームタイプ決定を提供するうえで、利点は明らかである。
【００４４】
複数のフレームフォーマットタイプを有するパケットが、入力ポートを介して受信されると予想される場合に、連続フレームタイプ除去プロセスをスピードアップさせるさらなる性能向上は、ディシジョンツリー200の異なるサブツリーを指示するジャンプ命令を指定する際に提供される柔軟性を介して達成される。そのような例示的な実施の1つは、集中アプリケーションがデータおよび音声サービスを同時に提供する、通信ネットワークの縁において利用される交換ノードを含み、交換装置の転送/プロバイダ側では、データと音声は異なるポートで受信される(非常に妥当性のある実施)。ダウンリンク方向に搬送され、VoIPトランクポートを介して受信されるパケットのIPパケットヘッダを識別するボイスオーバーIP(VoIP)ソリューションに関して、フレームタイプの決定は、トランクポートを介して受信されたパケットの場合、ディシジョンツリー200の同じサブツリーに直接ジャンプすることによって優先的に行うことができる。サブツリーの解析は、VoIPパケットが、普通のイーサネット（登録商標）パケットであるか、またはVLANヘッダをもつイーサネット（登録商標）パケットであるかを決定するため、依然として必要とされることもある。アップリンク方向に通信ネットワークノードを通過するパケットに関して、一般にデータパケットと音声パケットは、顧客に関連づけられた同じ配布側入力ポートを介して受信されるが、データパケットと音声パケットは、例えば、異なるサービスタイプ(TOS)パケットヘッダ値指定によって識別される、別々の「仮想コネクション」を介して搬送することもできる。ディシジョンツリー200を指定する際に提供される柔軟性は、入力ポート識別子112だけに基づいて早期決定に達することはできないにもかかわらず、ユーザが対応するディシジョンツリーレコード214を記述して、ディシジョンツリー200の特定のサブツリーへの特定のジャンプを介して、フレームタイプ決定プロセスが最初にサービスタイプ決定を考えるように指定できることを考えれば、さらに明らかである。
【００４５】
ディシジョンツリー解析器206の例示的な循環動作(300)が、図4に示されており、ディシジョンツリー解析器206は、レコード212をディシジョンテーブル210から取り出し312、レコード212のフィールド内で指定されるオフセット(およびビット長)を有するパケットヘッダビット値をパケットヘッダから取り出す314。取り出されたバイナリ値は、ビットマスクで指定される無視すべきビットをマスクした期待バイナリ値と照合される316。照合316の結果に応じて、レコード212の「一致」または「不一致」フィールドが考えられる。一致終了に達したかどうかに応じて318、フレームタイプ出力が提供されて、プロセス300が別の受信パケットに関して新たに開始されるか、またはディシジョンテーブル210内の次のレコード212を取り出すため312、ジャンプ命令が使用される。
【００４６】
本発明の例示的な実施形態によれば、抽出されたパケットヘッダビットを、ビットマスクでマスクされた/またはされない指定された比較値と比較できるので、本発明の例示的な実施形態の例示的な実施は、ビット値の範囲照合を可能にする3値照合機能を提供する。
【００４７】
本発明の例示的な実施形態によれば、複数のヘッダフィールドが短いビット長をもち、互いに比較的近くに位置している場合、ディシジョンツリー200のノード202は、複数のパケットヘッダフィールドのテストを同時に実行することができる。
【００４８】
ハードウェアエンジン104で事前にコード化されておらず、またはディシジョンツリー200を介して認識可能なパケットフレームタイプのタイプオブとしても表現できないパケットフレームタイプを有するパケットの処理をサポートするため、テンプレート照合エンジン108が利用される。テンプレート照合エンジン108は、受信パケットヘッダとのパターン照合用のパケットヘッダフォーマットテンプレートを指定する際に、完全な柔軟性を提供する。例示的な実施は、ハードウェアエンジン104およびディシジョンツリー解析エンジン106によって検出されるフレームタイプに加えて、さらに少なくとも16種のユーザ指定フレームタイプに対するサポートを提供する。
【００４９】
本発明の例示的な実施形態の例示的な実施によれば、テンプレート照合エンジン108は、3値内容参照可能メモリ(TCAM)を利用する。当技術分野における3値内容参照可能メモリの例示的な利用については、2003年3月31日にRayChin Luによって出願され、参照により本明細書に組み込まれる、「Configurable Ternary Content Addressable Memory」と題する、本発明の譲受人に譲渡された米国特許出願第10/403110号に説明されている。パケットヘッダテンプレートは、マスクおよびビットパターンを含み、それらは共に、ユーザ構成可能であって、任意のフレームフォーマットに対するサポートを提供する。上で説明したように、テンプレート照合はビットのマスクによって調整できるので、複数のフレームタイプを識別することができる。最初のテンプレート照合で適切な照合が行われるように、テンプレートを順序づけることができる。したがって、テンプレート照合エンジン108は、照合されるパケットヘッダフォーマットパターンを指定する際に、完全な柔軟性を提供する。テンプレート照合エンジン108はまた、それを実施する通信ネットワークノードが時代遅れになるのを遅らせることにも貢献する。
【００５０】
3つのフレームタイプ決定エンジン104、106、108が並列に動作するので、複数のフレームタイプ出力が、パイプライン100による各パケットの処理で利用されるフレームタイプ指定114を選択するフレームタイプ出力選択器110に提供される。一般に、構成可能なエンジンからのフレームタイプ出力指定114は、構成可能度の低いエンジンの出力より高い優先度を与えられる。テンプレート照合エンジン108のフレームタイプ出力には、一般にディシジョンツリー解析エンジン106のフレームタイプ出力よりも高い優先度が与えられ、ディシジョンツリー解析エンジン106のフレームタイプ出力には、ハードウェアエンジン104のフレームタイプ出力よりも高い優先度が与えられる。
【００５１】
例えば、新規格のパケット、サポートができなくなった/打ち切りになった旧規格のパケットタイプ、または形式外のパケットが送られてきたなどの理由で、3つのフレームタイプ決定エンジンのすべてが、受信パケットのフレームタイプを認識できないこともあり得る。パイプライン100の所望の動作に応じて、フレームタイプが決定できないパケットを、パイプライン100によってそれ以上処理せず、廃棄したり、宛先を変更したり、または存在するならば管理プロセッサに送ったりするが、本発明はそのように限定されるものではなく、それによって、そのような受信パケットの不必要な処理に対するパイプライン100の残りの部分の関わりを小さくする。本発明の例示的な実施形態の例示的な実施によれば、フレームタイプが決定できない受信パケットには、照合が失敗したフレームタイプのために予約されているフレームタイプ識別子(例えば、16進値の0xFF)が割り当てられる。
【００５２】
図1を参照すると、パイプライン100のステージ2には、送信元ポート識別子112、パケットヘッダ102、および割り当てられたフレームタイプ114が提供される。
【００５３】
抽出テーブル124のフレームタイプでインデックスされるレコード122に指定された抽出命令に基づいて、パケットヘッダ102からパケットヘッダフィールド値を抽出するため、パケットヘッダフィールド値抽出器120が利用される。各フレームタイプ114について、対応するレコード122が、フィールド値の抽出を可能にする適切なパケットヘッダフィールドオフセットを指定する。パケットヘッダフォーマットフィールド関連性は、一群の有効フレームフォーマットビットを介して指定される。上で述べたように、本発明の例示的な実施によれば、パイプライン100のステージ1は、少なくとも256種のフレームタイプを区別することができ、したがって、抽出テーブル124は、256個の対応するレコード122のエントリを含むことができるが、本発明はそのように限定されるものではない。
【００５４】
以下は、フレームタイプでインデックスされる例示的な情報抽出レコード122を表したものである。
【００５５】
【表３】
2006020317.tif 000005
【００５６】
簡単に述べると、ヘッダフィールド値抽出器120は、フレームタイプでインデックスされるレコード122を調べて、対応するオフセットで始まる、各有効フレームフォーマットビットセットに対応するパケットヘッダフィールド値を抽出する。以下は、対応する特定のフレームタイプ114について有効であるならば、受信パケットヘッダから抽出されるフィールド値の例示的なリストである。
-宛先MAC(6バイト)
-送信元MAC(6バイト)
-DSAP(1バイト)
-SSAP(1バイト)
-イーサネット（登録商標）タイプ(2バイト)
-VLAN ID(12ビット)
-802.1p優先度(3ビット)
-TOS(1バイト)
-TTL(1バイト)
-プロトコルID(1バイト)
-IPチェックサム(2バイト)
-SRC_IP(4バイト)
-DES_IP(4バイト)
-SRC L4ポート(2バイト)
-宛先L4ポート(2バイト)
-UDP/TCPチェックサム(2バイト)
-ユーザ定義/TCPフラグ(1バイト)
抽出テーブル124のレコード122は、各フレームタイプについて有効フィールドだけ指定し、各有効フィールドについては、オフセットだけが指定されることは明らかであろう。しかし、上に列挙したパケットヘッダフィールドには、括弧で括ってフィールド長も示されている。有効フィールドのフィールド長指定をレコード122に含めるかどうかは、設計時の選択に任されているが、レコード122でフィールド長を指定すれば、格納領域が必要になる一方で、パケットヘッダフィールド抽出器120は、パケットヘッダフィールドの長さに関して仮定することができる。
【００５７】
本発明の例示的な実施形態の別の例示的な実施によれば、パケットヘッダフィールド抽出器120は、パケットヘッダフィールドからフィールド値を物理的に抽出はせず、それらをパケットヘッダ102とは別個のレジスタに再び格納するだけである。パケットヘッダ102は、パイプライン100のすべてのステージから利用可能であり続けるので、パケットヘッダフィールド抽出器120は、フレームタイプ114またはMtype126に基づいて、「ポインタテンプレート」を各受信パケットに関連づけ、パケットヘッダ、ポインタテンプレート、Mtypeの三つ組を、パイプライン100の後続ステージに提供する。後続ステージのモジュールおよび/またはプロセスは、パケットヘッダフィールド値を検査する必要があるので、処理対象の各パケットに関連づけられたポインタテンプレートを調べて、パケットヘッダフィールド値を直接検査する。例示的なポインタテンプレートは、パケットヘッダ102の先頭を指すメモリアドレスポインタと、対応する抽出レコード122で指定される有効オフセット値を含む。このような実施の利点として、パケットヘッダ情報は一度しか格納されないので、領域を節約できることなどが挙げられる。
【００５８】
本発明の例示的な実施形態によれば、各レコード122はさらに、パケット分類用の一致タイプ(Mtype)を指定する。フレームタイプ指定114は、パケットヘッダ値を抽出する目的のため、パケットのフォーマットに関連するが、一方、一致タイプ指定126は、パケット分類のために使用される。複数のフレームタイプ114を、単一の一致タイプ126にマッピングすることができる。
【００５９】
本発明の例示的な実施形態によれば、各レコード122はさらに、特定のフレームタイプに関して、デフォルトパケット処理アクション128を実行すべきかどうかを指定する。
00:デフォルトポートアクションを使用する(デフォルト)。
01:CPUに転送する。
10:フィルタ:パケットを廃棄する。
11:(無効/予備)
【００６０】
本発明の例示的な実施形態の例示的な実施によれば、デフォルトポートアクション128は、入口ポートごとにレジスタで指定される。例示的なデフォルトポートアクション128は、以下のものを含む。
00:L2/L3探索結果を使用する(デフォルト)。
01:CPUに転送する。
10:フィルタ:パケットを廃棄する。
11:(無効/予約)
【００６１】
抽出されたフィールド値130は、一致タイプ126および初期アクション128と共に、L2およびL3探索のために、パイプライン100のステージ3に提供される。初期アクションは、パイプライン100の後続ステージによって変更することができる。
【００６２】
ステージ3は、典型的には、L2探索、プロトコルVLAN探索、およびL3探索という異なる探索タスクを実行する3つの探索エンジンを含む。
【００６３】
L2探索エンジン132は、2004年2月24日にYikら(うち何人かは本明細書に発明者として挙名されている)に付与され、その特許証が参照により本明細書に組み込まれる、「High Speed MAC Address Search Engine」と題する、上で述べた、本発明の譲受人に譲渡された米国特許第6697873 B1号で説明されている、ハッシュ探索アルゴリズムを利用する。要約すると、L2探索エンジン132は、以下の機能を提供する。
【００６４】
送信元MAC ADDR学習:抽出された送信元MAC ADDR130単独、または送信元MAC ADDRとVLAN IDの組合せ(130)をキーとして使用して、米国特許第6697873号で説明されているハッシュ方式によってL2交換データベースのL2交換テーブルで検索を実行する。
-検索によって対応するエントリが識別されなかった場合、L2交換データベースエントリがL2交換テーブルに作成される(学習MAC ADDRを管理プロセッサに報告することもできる)。
-検索によって対応するエントリが識別された場合、エントリに関連するエージングビット更新する。
【００６５】
宛先ポート探索は、米国特許第6697873号で説明されているハッシュ方式によってL2交換データベースのL2交換テーブルで検索を実行するためのキーとして使用される、抽出された宛先MAC ADDR130、または宛先MAC ADDRとVLAN IDの組合せ(130)に基づいて実行される。
-検索によって対応するエントリが識別されなかった場合、受信パケットはすべてのポートに送信される。受信パケットが関連するVLAN IDを有する場合、送信は、同じVLANドメインに関連するポートに限定され、同じVLANドメインに関連するポートは、VLANテーブルによって指定される。
-検索が成功した場合、パケットは正しいポートにだけ送信される。パケットが関連するVLAN IDを有する場合、該当するポートは、同じVLANドメインに関連するポートである。
【００６６】
L2交換データベースは、以下の例示的なフォーマットを有するエントリを含む。
【００６７】
【表４】
2006020317.tif 000006
【００６８】
L2探索エンジン132は、L2交換データベースから交換情報を取り出し/取得し、交換情報は、出口ポートビットマップ、受信パケットに割り当てられたVLAN ID、VLAN IDに固有の処理アクション(挿入、置換、削除、無視など)を指定するビットマップ、送信優先度、ドロップ優先度、マルチキャストまたはユニキャスト転送指定などを含むが、本発明はそのように限定されるものではなく、交換情報は、受信パケットを処理するためのパケット処理応答を定式化する際に利用される。
【００６９】
マルチキャストパケットの場合、L2探索エンジン132は、典型的には以下に示すような31ビットのエントリによってグループメンバーシップを指定する、典型的にはグループIDでインデックスされるエントリを有するマルチキャストグループテーブルで検索を実行することによって、グループIDに対応する出口ポート指定を取得する必要がある。
【００７０】
【表５】
2006020317.tif 000007
【００７１】
マルチキャストグループテーブルは、少なくとも256のエントリを含むことができるが、本発明はそのように限定されるものではない。
【００７２】
送信元および宛先MAC ADDRは、L2探索エンジン132によって、対応する送信元MAC_IDXおよび宛先MAC_IDX指定子にマッピングされ、それらは、ステージ4においてパケット分類器エンジン142によって使用される。
【００７３】
本発明の例示的な実施形態によれば、ステージ3はさらに、L3探索エンジン134を含む。L2探索エンジン132とL3探索エンジン134は、並列に動作する。L3探索エンジン134は、抽出された宛先IPアドレスをキーとして使用して、L3交換データベースでネクストホップルータ情報を検索することによって、レイヤ3の探索動作を実行する。L3交換データベースは、L3 IP交換テーブルと、範囲照合テーブルとを含む。L3交換データベースの検索中に取り出された情報は、抽出された送信元IP ADDRおよび宛先IP ADDRを、ステージ4に提供されて分類器142によって使用されるインデックス値にマッピングする際に利用される。
【００７４】
L3交換データベース検索は、受信パケットに関するルーティング情報を決定するために実行される。L3交換データベース検索は、正確な一致を取得するための探索と、範囲一致を取得するための探索との2種類の探索の実行を含む。
【００７５】
正確な一致の探索については、2003年12月31日にBarrakら(うち何人かは本明細書に発明者として挙名されている)によって出願され、参照により本明細書に組み込まれる、「High Speed MAC Address Search Engine」と題する、本発明の譲受人に譲渡された米国特許出願第10/750445号で説明されている。要約すると、L3探索を実行する際、宛先IP ADDRは、ハッシュインデックスにハッシュされる。ハッシュインデックスは、L3交換データベースでエントリを参照するのに使用される。
【００７６】
各L3交換データベースエントリは、以下の例示的な情報を含む。
【００７７】
【表６】
2006020317.tif 000008
【００７８】
L3交換データベースを探索する際、IP ADDRが、対応するインデックスで指示されるエントリに格納されたIP ADDRと比較される。
【００７９】
一致するIP ADDRが見つかった場合、L3探索は完了し、以下のアクションが実行される。
-対応するネクストホップルーティング情報を取得する。
-ステージ5でL3送信カウンタを更新するためにL3カウンタインデックスが提供される。
-エントリが最近使用されたことを示すL3交換データベースエントリのエージングビットが更新される。
-ステージ4でパケット分類のために一致エントリがIP_IDXとして使用される。
【００８０】
一致するIP ADDRが見つからなかった場合、それは、複数のIP ADDRが同一のハッシュインデックスにハッシュされていることを意味する。その場合、L3交換データベースエントリは、エントリのリストの第1エントリへの有効リンクポインタを有する。一致を見つけるため、そのリストが解析される。
【００８１】
リストに一致するIP ADDRが含まれていない場合、正確な照合の失敗に関する表示が提供される。正確な一致が見つけられなかった場合、L3範囲照合の結果が考慮される。
【００８２】
L3範囲探索は、最長プレフィックス一致方式を模倣する。L3交換データベースのIP範囲照合テーブルのエントリは、IP ADDR指定、およびIP ADDR範囲に関連するIPマスクを含む。IPマスクは、比較用のIP範囲(一般にIPサブネット)を指定する。
【００８３】
【表７】
2006020317.tif 000009
【００８４】
L3交換データベースのIP範囲照合テーブルは、64のエントリを含むことができ、適用例に応じて必要であるならば、より多くのエントリを使用することもできるが、本発明はそのように限定されるものではない。
【００８５】
抽出された宛先IP ADDRのビットが、L3交換データベースのエントリに格納されたIP ADDRのビットと比較され、その結果が、IPマスクでマスクされる。マスクは関連ビットを指定し、関連ビットが一致した場合、範囲照合は成功である。
【００８６】
L3範囲一致が見つかった場合、L3正確一致に関して実行されるのと同じアクションが適用される。どのエントリも一致しなかった場合、L3範囲照合は失敗したと言われる。
【００８７】
L3正確照合とL3範囲照合が共に成功した場合、正確一致のほうが、範囲一致よりも高い優先度をもつ。一致が見つからなかった場合、ルーティングされるパケットは、さらなる処理のため、一般に管理プロセッサに転送される。
【００８８】
上の説明では、L3ルーティングパケットのための交換応答を解決する宛先IP探索について説明した。本発明の例示的な実施形態によれば、ルーティングパケットおよびブリッジパケットを含むすべてのIPパケットについて、L3探索エンジン134は、32ビットのIPアドレスを(12または14ビットなど)一般によりビット数の少ないIP_IDXにマッピングするため、送信元IP ADDRを探してL3交換データベースの探索も試みる。対応するIP_IDXへのIP ADDRのマッピングは、分類ステージ4の実施コストを削減するために利用される。
【００８９】
本発明の例示的な実施形態によれば、VLANタグをパケットプロトコル指定に関連づけるのに関して選択肢が提供され、プロトコルは、パケットヘッダのイーサタイプまたはDSAP/SSAPフィールドの値によって識別される。プロトコルVLAN探索エンジン136は、イーサネット（登録商標）IIおよびSNAP受信パケットのイーサタイプ、またはその他の論理リンク制御(LLC)パケットのDSAP/SSAPを決定する。本発明の例示的な実施形態によれば、少なくとも16の構成可能イーサタイプまたはDSAP/SSAPを、それぞれVLAN IDに関連づけることができる。プロトコルVLAN探索エンジン136は、抽出パケットヘッダフィールド値に基づいて、抽出フィールド値と既知のパターンとの照合を含む動作を実行する。
-受信パケットについて一致が見つからない場合、それはパケットがVLANタグ/関連を有していないことを意味し、どのようなアクションもとられない。本発明の例示的な実施形態によれば、一致が見つからない場合、デフォルトVLAN IDを割り当てることができる。
-一致が見つかった場合、受信パケットには、関連する一致エントリから取得した指定に対応するVLAN IDXが割り当てられる。
-発信VLANタグを決定するためにプロトコルVLANテーブルに問い合せをする際、インデックスおよびポートID112が検索キーとして使用される。
-一致の場合、VLAN ID(タグ)が置き換えられる。
【００９０】
例示的なプロトコルVLANテーブルは、以下を含む。
【００９１】
【表８】
2006020317.tif 000010
【００９２】
VLAN IDXとVLANとのマッピングは、入口ポート毎に提供されることに留意されたい。したがって、同じプロトコルについて、異なるVLAN IDは、異なるポートに割り当てることができる。
【００９３】
本発明の例示的な実施形態によれば、L2およびL3探索エンジン132、134は共同して、一致した交換データベースエントリからの交換情報を提供して、受信パケットの少なくとも初期交換応答140の定式化をサポートする。ステージ4の処理が完了した後に利用可能な情報が、入口ポートID、抽出パケットヘッダ情報、L2交換データベースから抽出された交換情報、L3交換データベースから抽出された交換情報、およびプロトコルVLANテーブルから取得される情報に基づく交換応答の定式化をサポートする。交換応答で指定される例示的な情報は、以下を含む。
【００９４】
【表９】
2006020317.tif 000011
【００９５】
交換応答内の情報は、ステージ5の後で受信パケットを処理する転送エンジン(別の箇所で説明)に、パケットをどのように処理するかについて指示するのに使用することができる。
【００９６】
本発明の例示的な実施形態によれば、ステージ4は、複数の抽出フィールドに分類規則を適用することによって、パケットをパケットフローに分類する。分類規則は、テスト値および関連テストマスクとして実施することができる。
【００９７】
ステージ2が、受信パケットのヘッダから複数のフィールド値を抽出し、異なるフレームフォーマットタイプ114に対しては、異なるフィールド値が抽出されることを思い出されたい。本発明の例示的な実施形態によれば、パケット分類規則は、異なるパケットフレームフォーマットタイプに対して、異なるようにフィールド/フィールド値を組み合わせる。分類規則は、分類規則テーブル144のエントリ146で指定され、規則テーブルのフィールドは、各規則に関連づけられたMtype126に応じて、異なる意味を有することができる。例えば、Mtype=1が、イーサネット（登録商標）II/IP/TCPパケットに対応し、Mtype=2が、イーサネット（登録商標）II/IP/ICMPパケットに対応する場合、Mtype=1のパケット分類は、例示的には、Mtype=1、送信元ポートID(112)、送信元MAC ADDR、宛先MAC ADDR、送信元IP ADDR、宛先IP ADDR、TCP送信元ポート、TCP宛先ポートといったフィールドに基づいて実行することができ、一方、Mtype=2のパケット分類は、例示的には、Mtype=2、送信元ポートID(112)、送信元MAC ADDR、宛先MAC ADDR、送信元IP ADDR、宛先IP ADDR、ICMPコード、ICMPタイプといったフィールドに基づいて実行することができる。本発明の例示的な実施形態の例示的な実施によれば、分類規則エントリフィールドは、TCP送信元ポートとICMPコードの例のように、異なる意味を有することができるが、分類規則に照らしたテストは対応するMtypeの値によって識別されるので、混乱が起きることはない。
【００９８】
以下は、分類規則テーブルエントリ146のフォーマットの例である。
【００９９】
【表１０】
2006020317.tif 000012
【０１００】
動作について、パケット分類器142は、抽出フィールド値を対応するテストマスクでマスクされた分類規則で指定された期待テスト値と比較することによって、パケットに関連するMtype126に関連づけられた分類規則で指定された抽出パケットヘッダフィールドの少なくともサブセットを分類規則に照らしてテストする。本発明の例示的な実施形態の例示的な実施によれば、分類規則一致が見つかった場合、分類規則テーブル144の分類規則エントリ146のインデックスが、パケットフローIDとして使用される。
【０１０１】
本発明の例示的な実施形態によれば、重みが各分類規則に関連づけられる。複数の規則が一致した場合、パケット分類器142に関連づけられたフローID選択器148は、最高の重みをもつ分類規則に従って、受信パケットを分類する。同じ重みをもつ複数のエントリ146が一致した場合、対象パケットのフローIDを決定する際、最高の分類規則テーブルインデックスをもつ最高のエントリが選択される。
【０１０２】
本発明の例示的な実施形態によれば、パケット用の交換応答140に達するため、可能な限り、ステージ2と同じくらい早期に、初期アクション128が受信パケットに関連づけられる。例えば、初期アクション128は、ステージ2において入口ポートに基づくことができ、その場合、初期アクションは、L2探索エンジン132によってL2交換データベースから、またL3探索エンジン134によってL3交換データベースから取得された交換情報に基づいて、ステージ3において変更される。
【０１０３】
L3ルーティング機能は、L3探索エンジン134によって提供される。しかし、パケット分類器142では、柔軟性を提供して、IP範囲一致によるL3ルーティングを提供する。したがって、IP範囲一致の性能は、パケット分類器142によって拡張される。
【０１０４】
本発明の例示的な実施形態の例示的な実施によれば、Mtype指定126は、照合フィールドの異なる意味に基づいて規則を区別するために、L3ルーティングのIP範囲照合で利用される。この状況に対処するための1つの方法は、Mtype+4を新しいMtypeに指定することである。すなわち、L3探索エンジン134が、L3交換データベースでルートを見つけることができず、パケット分類器142を利用して、L3探索機能を実行することを決定した場合、L3探索エンジン134は、Mtypeの値に4を加算し、それを宛先IP ADDRと共に、パケット分類器142に提供する。本発明の例示的な実施形態によれば、パケット分類器142は、新しいMtypeに基づいて規則を照合するために、IPインデックスを使用する代わりに、完全な宛先IP ADDRを利用することができる。
【０１０５】
本発明の例示的な実施形態によれば、アクション128が、パイプライン100のステージ5で実行される。受信パケットに関するすべてのアクション128は、パケット処理パイプライン100の異なるステージで受信パケットに割り当てられる、デフォルトポートアクション、フレームタイプアクション、L2/L3アクション、およびフローアクションに分類することができる。交換応答も、受信パケットに関連づけることができる。アクション128の実行は、図5の500で例示的に示されるような優先規則に従う。
【０１０６】
フローアクションに最高の優先権が与えられる。ステージ4において、パケット分類器142が受信パケットの分類502に成功した場合、パケットにフローIDが割り当てられる。フローIDは、アクションテーブル154でフローアクションを検索するのに使用される。適切なフローアクションと対応するフローアクションパラメータが、アクションテーブル154から取り出されたら、パケットおよび/またはパケットヘッダに関して、フローアクションが実行504される。
【０１０７】
有効なフローアクションを受信パケットに関連づけられなかった場合、ステージ2において、上で説明したように抽出テーブル124のレコード122から取得される有効なフレームタイプアクション128が受信パケットに関連づけられたならば、フレームタイプアクションに優先権が与えられる。受信パケットに関連づけられたフレームタイプアクションは、ステップ512で決定される。フレームタイプアクション128は、CPUへの受信パケットの転送514、および受信パケットの廃棄516を含む。
【０１０８】
フレームタイプアクションコード"00"が、受信パケットに関連づけられる場合、優先権は、パケットが受信された送信元ポートに基づいて(SPort ID 112に基づいて)、デフォルトポートアクションに与えられる。ステップ522で確かめられる、受信パケットに関連づけられた有効なポートアクションコードは、CPUへの受信パケットの転送524、および受信パケットの廃棄526を含む。実施に応じて、デフォルトポートアクションは、受信パケットに基づいて決めることができ、またはポートごとに、少なくとも1つのデフォルトポートアクションレジスタで指定することもできる。
【０１０９】
デフォルトポートアクションコード"00"が、受信パケットに関連づけられる場合、パケットは、L2/L3探索結果アクション128に基づいて処理532される。
【０１１０】
図6には、パイプライン100のステージ5の例示的なアーキテクチャの詳細が示されている。パケットに対応するフローID 150、および初期アクション128は、アクションテーブル154を調べて、パケットについて実行されるアクションを決定する際に利用される。おそらく宛先ポートID指定152を含む初期交換応答140が、交換応答変更器156に提供される。交換応答変更器156は、アクションテーブル154で指定される情報から取得される命令に従って動作して、フレームエンジン162に確定した交換応答140を提供する。パケットヘッダ102が、パケットヘッダ変更器に提供される。パケットヘッダ変更器158は、アクションテーブル154で指定される情報から取得される命令に従って、パケットヘッダ102を変更する。パケットヘッダ102が変更されると、パケット再構成モジュール164が、出力ポートを介して送信される、パケットペイロードと変更されたパケットヘッダ102を含む新しいパケットを定式化する。
【０１１１】
フローアクションテーブル154の各エントリは、以下の例示的な情報を含む。
-パケット/パケットヘッダについてどのアクションを実行するかを指定するアクションコード。
-パケットヘッダVLAN IDの置換を可能にするのに使用されるVLAN ID置換可能指定。
-VLAN ID置換を可能にしたときに使用されるVLAN ID指定。
-アクションコードに基づいて複数の意味をもつ転送INDX/DEST BIT MAPフィールド。
i. 宛先ポートビットマップ表示。
ii. アクションがIPおよびMACヘッダの再マッピングを含む場合、IPおよびMAC情報への前方インデックスを示す。
iii. アクションがハートビート検出を含む場合、ハートビートフィールド表示。
-XP再マップ可能指定は、送信優先度およびドロップ優先度の置換を指定する。
-XPフィールドは、新しい送信優先度を指定する。
-DPフィールドは、新しいドロップ優先度を指定する。
-スヌープ可能は、スヌープポートへのパケット転送を指定する。
-スヌープポートIDフィールドは、スヌープポートを指定する。
-TOS/DSCP再マップ可能指定子は、IPヘッダでのTOS/DSCPフィールドの置換を指定する。
-TOS/DSCPフィールドは、置換するTOS/DSCP値を指定する。
-802.1p再マップ可能指定子は、パケットヘッダでの802.1p(VLAN優先度)フィールドの置換を指定する。
-802.1pフィールドは、802.1pフィールド値を置換する際に使用されるVLAN優先度値を指定する。
-測定可能指定子は、フロー用の測定関数を使用可能にするのに使用される。
-カウント可能指定子は、フロー用のカウント関数を使用可能にするのに使用される。
-測定/カウンタインデックス指定子は、測定またはカウンタIDを示す。
【０１１２】
以下は、6つの排他的なフローアクションの例示的な詳細である。
【０１１３】
L2/L3転送(アクションコード000)は、パラメータとして宛先ビットマップを利用し、パイプライン100のステージ3で提供された初期交換応答140で指定された宛先ポートビットマップを上書きする。パケットが(上で説明したように)L2/L3探索結果に基づいて変更されたのと同じ方法で、パケットヘッダが変更される。
【０１１４】
CPUポートへの転送(アクションコード001)は、宛先ビットマップを変更して、CPUポートへのパケットの転送を指定する。
【０１１５】
パケットフィルタ(アクションコード010)は、パラメータとして命令を利用して、ドロップされたパケットのカウントを実施するフィルタリングカウンタを更新することができる。初期交換応答140が変更されて、フィルタビットがオンに設定される。パケットはドロップされる。
【０１１６】
ハートビート検出(アクションコード011):ハートビートパケットを受信した場合、セッションID、タイプ、およびモードが、フェイルオーバモジュールに送られて、処理される(フェイルオーバモジュールの動作については別の箇所で説明する)。初期交換応答140が変更されて、フェイルオーバパケットビットがオンに設定され、これによって、パケットがハートビートパケットであることが示される。その他の変更には、宛先ポートマップ指定の置換が含まれ、パケットは、さらなる処理のためにフェイルオーバモジュール(図示せず)に転送される。
【０１１７】
MAC ADDR再マッピング、IP ADDR再マッピング、およびL3再マッピングのフローアクションは、ADDR再マップテーブル166として実施される、図6に示される同じデータベースを共用するが、以下本明細書では、状況に応じてMAC ADDR再マッピングデータベース166、IP ADDR再マッピングデータベース166、およびL3再マッピングデータベース166と呼ばれる。ADDR再マップテーブル166のエントリには、宛先IP ADDR指定、宛先ビットマップ、VLAN"タグアウト"ビットマップ指定(上記のTポートベクトルを参照)、VLAN ID指定、および宛先MAC ADDRが含まれる。
【０１１８】
MAC ADDR再マッピング(アクションコード100)は、パラメータとして、フェイルオーバデータフロー(以下を参照)へのインデックスと、MACおよびIP再マッピング用に使用可能なフェイルオーバを定義する3つのFLOVビットとを利用する。フェイルオーバ機能可能ビットFLOVF-Eは、CPUによって設定されて、フェイルオーバ機能を起動する。ハードウェア可能ビットFLOVE-Hは、セッション失敗がフェイルオーバモジュール(別の箇所で説明する)によって検出されたときに設定される。ソフトウェア可能ビットFLOVE-Sは、CPUがセッション失敗を検出したときに、CPUによって設定される。フェイルオーバ/再マップがオンとは、FLOVF-E=1かつ(FLOVE-HまたはFLOVE-S)=1であることを意味する。フェイルオーバ/再マップがオフならば、初期交換応答140は変更されない。しかし、フェイルオーバ/再マップがオンならば、MAC再マッピングデータベース166で検索を実行して、宛先ビットマップ置換、VLAN IDおよびVLAN優先度置換、ならびに発信VLANタグビットマップ置換などの情報を取り出し、再マッピングテーブルを形成するために、インデックスが使用される。初期交換応答140に対する変更には、宛先ビットマップの置換、VLAN IDの置換、VLAN優先度の置換、VLAN"タグアウト"ビットマップ(上記のTポートベクトルを参照)の置換、およびCRCの再計算が含まれる。パケットヘッダに対する変更には、宛先MAC ADDRの置換が含まれる。
【０１１９】
フェイルオーバブロック170によって提供されるフェイルオーバ機能に関して、着信パケットが、アドレス再マッピングを必要とするフローID 150に関連づけられ、かつそのフローID 150について失敗が検出および記録された場合、パケットを異なる宛先アドレスに転送することを含む、失敗がない場合とは異なるパケットの転送が行われる。FLOVビットが、失敗が生じたかどうかを識別するために使用される。失敗がない場合、普通に転送が行われる。失敗が生じた場合、フローアクションテーブル154の対応する行に格納されたインデックスを、再マッピングテーブル166の使用される代替転送情報を含んだ行を指示するポインタとして使用する。
【０１２０】
IP ADDR再マッピング(アクションコード101)は、パラメータとして、フェイルオーバデータフローへのインデックスと、上記の3つのフェイルオーバビットとを利用する。フェイルオーバ/再マップがオンならば、IP再マッピングデータベース166で検索を実行して、宛先ビットマップ、ネクストホップ宛先MAC ADDR、VLAN ID/タグ、発信VLANタグビットマップ、および宛先IPアドレスなどの、初期交換応答140およびパケットヘッダ102を変更するのに使用される情報を取り出すために、インデックスが使用される。パケットタイプに応じて、パケットヘッダ102および初期交換応答140を変更するための4つの異なるシナリオが存在し、それらを以下の表に要約する。
【０１２１】
【表１１】
2006020317.tif 000013
【０１２２】
ただし、IPルーティングパケットとは、L3ルータで処理されるパケットのことである。一般に、L3ルーティングでは、フローアクションテーブル154で指定されるインデックスが、L3ルーティングを提供する際にルーティングテーブルのエントリをポイントするために利用することができる。
【０１２３】
L3ルーティング(アクションコード110)は、パラメータとして、ルーティングエントリへのインデックスを利用する。インデックスを使用して、宛先ビットマップ、宛先MAC ADDR、ネクストホップ宛先MAC ADDR、およびVLAN情報を抽出し、再マッピングテーブル166を形成する。初期交換応答140に対する変更には、宛先ビットマップの置換、VLAN IDの置換、VLAN優先度の置換、VLAN"タグアウト"ビットマップの置換、およびCRCの再計算が含まれる。パケットヘッダに対する変更には、ネクストホップ宛先MAC ADDRによる宛先MAC ADDRの置換、TTLを1だけ減らすこと、およびIPチェックサムの更新が含まれる。
【０１２４】
以下のアクションは、互いに共存することができ、上記のフローアクションとも共存することができる。
【０１２５】
XPおよびドロップ優先度(DP)置換:XPおよびDPは、フローごとにCPUによって再定義することができる。XP置換が1に設定される場合、初期交換応答140が変更されて、XPおよびDP値が置換される。
【０１２６】
スヌーピング: 初期交換応答140が変更されて、スヌーピングポートに対応する宛先ビットマップのビットをオンにすることによって、パケットが転送される出力ポートの1つとしてスヌープポートが追加される。パケットを転送する際に、マルチキャストビットが設定されることも保証される。
【０１２７】
TOS/COS再マッピング: 提供されるTOS/DSCP値に基づいてTOS/COSフィールドを置換することによって、パケットヘッダ102が変更される。パケットヘッダ102が変更されたので、CRCおよびIPチェックサムを再計算しなければならない。
【０１２８】
802.1P再マッピング: 初期交換応答140が新しいVLANタグで変更される場合の802.1pフィールド。CRCも再計算しなければならない。
【０１２９】
802.1Q VLAN ID置換: 初期交換応答の802.1Q VLAN IDが、802.1Q VLAN ID値で置換される。CRCも再計算しなければならない。
【０１３０】
図7を参照すると、速度測定とパケットカウントは、独立に起動し、停止させることができる。
【０１３１】
速度測定: 測定インデックスが、測定モジュール168に提供される。測定モジュール168は、測定インデックスに基づいて、トラフィックフローを追跡する。トラフィックフローが指定されたピーク速度を超えた場合、測定モジュール168は、赤色状態を報告する。トラフィックフローが指定された平均速度を下回った場合、測定モジュール168は、緑色状態を報告する。それ以外の場合、黄色状態が報告される。初期交換応答140は、測定モジュール168によって報告された色指定に基づいて変更される。赤色("10")の場合、廃棄されるパケットを効果的に指標づけるフィルタビットが設定される。黄色("01")の場合、ドロップ優先権が設定され、その結果、パケットは優先権規則に従ってドロップされる。緑色("00")の場合、対応する初期交換応答の変更は行われない。
【０１３２】
カウント: 測定モジュール168に測定インデックスを提供することによって、カウントも可能になる。フローが赤色状態でなければ、送信パケット数および送信バイト数に対応するカウンタの値が増やされる。フローが赤色状態の場合、廃棄カウンタの値が増やされる。
【０１３３】
フロー測定およびカウントブロック168の詳細な機能は以下を含む。
【０１３４】
本発明の例示的な実施形態の例示的な実施によれば、IETF規格である2レート3色マーカ(trTCM)方式を使用して、フローごとにトラフィックを測定する。本発明の例示的な実施形態によれば、この方式は、典型的には、フローピーク情報速度(PIR)および最大ピークバーストサイズと、認定情報速度(CIR)(平均速度)および最大平均バーストサイズとにそれぞれ基づく、2つのリーキーバケットを使用して実施される。
【０１３５】
フロー測定を必要とするあらゆるパケットについて、フロー測定モジュール168は、測定インデックスを使用して、対応するフローリーキーバケットカウンタを更新する。測定モジュールは、
トラフィックフローがPIRを超えれば、赤色、
トラフィックフローがCIRを超えるが、PIRを超えなければ、黄色、
トラフィックフローがCIRを超えなければ、緑色というように、フローの緑色、黄色、または赤色状態を返す。
【０１３６】
フロー別カウンタは、典型的には、測定インデックスでインデックスされるテーブルのエントリ内に保有され、各エントリは、受信パケットカウンタ、受信バイトカウンタ、送信または赤色パケットカウンタ、送信または赤色バイトカウンタ、およびパケット破棄カウンタを有する。"送信"カウンタは、L3アクションに基づいて処理されるL3交換パケットをカウントするために使用され、一方、"赤色"カウンタは、決定されたフローID 150に従って処理される分類パケットのために使用される。
【０１３７】
上で説明したように、フローID 150に関連づけられないパケットは、L3探索結果に従って処理することができる。その場合、フロー測定およびカウントモジュール168には、L3探索エンジンによって、送信元カウンタインデックスおよび宛先カウンタインデックスが提供される。フロー測定およびカウントモジュール168は、送信元インデックスを使用して、対応する受信カウンタを更新し、一方、宛先インデックスを使用して、送信カウンタを更新する。交換応答140のフィルタビットが設定されている場合、送信カウンタの代わりに、廃棄カウンタが更新される。
【０１３８】
L3探索エンジン134は、L3交換データベース内に送信元IPアドレスを見つけられないことがあり、そのため、送信元カウンタIDXを提供できないことがあることを思い出されたい。本発明の例示的な実施形態によれば、そのようなパケットの場合、送信元ポートがインデックスとして使用されて、L3デフォルト送信元ポートカウンタを更新する。
【０１３９】
フローカウンタ更新は、パケットフローに関してパケットが分類されるときに実行され、フローアクションも、カウンタビットを設定することによるカウンタ更新を必要とする。測定およびカウンタモジュール168は、フローカウンタインデックスを使用して、関連するRXカウンタを更新する。
【０１４０】
測定およびカウントモジュール168はまた、入口速度測定のため、赤色(廃棄)パケット数を追跡する。色が赤の場合、測定およびカウントモジュール168は、(上で説明したように、空間効率を高めるために送信カウンタと同じフィールドを共用する)パケット廃棄カウンタも更新する。
【０１４１】
フローカウンタコード000は、ルーティングパケット用のL3アクションと同じであることを思い出されたい。そのようなパケットについて、以下の処理を実行する必要がある。パケットヘッダ102は、変更される必要があり、宛先MAC ADDRは、L3探索エンジン134によって取得される宛先MAC ADDRであるネクストホップルータのMACアドレスで置換され、パケットがパケット分類器142によってフローID 150に関連づけられる場合、さらにネクストホップルータのMACアドレスを、MAC ADDR再マッピングテーブル166から取得される宛先MAC ADDRによって上書きすることができる。TTLが1だけ減らされ、IPチェックサムが更新される。初期交換応答140に対する変更には、L2 CRC再計算フラグの設定、およびVLAN ID指定の上書きが含まれる。TTL>1ならばパケットが廃棄され、初期交換応答140の送信元MAC ADDR置換ビットが設定されるというL3アクションは、L3探索エンジン134によって実行されることに留意されたい。
【０１４２】
本発明の例示的な実施形態によれば、柔軟性のあるヘッダ解析方式が提供され、最大回線速度で着信するパケットの指定されたパケットヘッダビットパターンの検査に基づいて様々なフレームタイプを決定するために、3つのヘッダ解析エンジンが並列に利用される。標準的なよく知られたフレームタイプの高速フレームタイプ識別を提供するハードウェアエンジン、ディシジョンツリー解析エンジン、および構成可能テンプレート照合エンジンの3つのヘッダ解析エンジンを利用することで柔軟性が提供される。
【０１４３】
本発明の例示的な実施形態によれば、最低限かつ高速の前処理を保証するフレームタイプ決定の後、パケットヘッダフィールド値が、パケットヘッダから抽出される。各フレームタイプに関して少なくとも1つのフィールドのオフセットを指定できる、ユーザ構成可能フィールド抽出器が利用される。パケットタイプの中には、パイプラインのこの早期ステージで、パケット処理アクションを決定できるものもある。
【０１４４】
本発明の例示的な実施形態によれば、レイヤ2送信元および宛先MACアドレス、ならびにレイヤ3送信元および宛先IPアドレスを、アドレステーブルを探索する際に使用される内部インデックスにマッピングすることによって、実施コストが削減される。結合L2およびL3探索エンジンは、ハッシュベースの探索を利用して、抽出ネットワークアドレスフィールド値を、ビット長が短いインデックスにマッピングする。
【０１４５】
本発明の例示的な実施形態によれば、仮想ローカルエリアネットワーク識別子(VLAN ID)挿入、VLAN再マッピング、サービスタイプ(TOS)再マッピング、サービス品質(QoS)実施、フィルタリング、転送、およびヘッダ変更を含むが、これらに限定されない、アクションは、パケットがどのタイプに分類されたかによる。
【０１４６】
本明細書で述べたデータベース、テーブル、リスト、エントリ、フィールド、およびレジスタそれぞれのサイズが、関連するメモリ記憶装置空間要件を有することは理解されよう。データベース、テーブル、リスト、エントリ、フィールド、およびレジスタのサイズは、必要な記憶空間を提供することに関連するコストを考慮に入れた設計時の選択に任されている。
【０１４７】
提示された実施形態は例示的なものに過ぎず、当業者であれば、本発明の主旨から逸脱することなく、上で説明した実施形態に変更を施し得ることが理解できよう。本発明の範囲は、添付の特許請求の範囲によってのみ確定される。
【図面の簡単な説明】
【０１４８】
【図１】本発明の例示的な実施形態による、パケット交換環境用の結合パイプライン化探索および分類エンジンを実施する要素を示した概略図である。
【図２】本発明の例示的な実施形態による、概念化された連続フレームタイプ除去を示した概略図である。
【図３】本発明の例示的な実施形態による、ディシジョンツリー解析エンジンの例示的な要素を示した概略図である。
【図４】本発明の例示的な実施形態による、連続フレームタイプ除去プロセスの循環的ステップを示したフローチャートである。
【図５】本発明の例示的な実施形態の例示的な実施による、例示的なパケット処理パイプラインのステージ5によって典型的にはどのアクションが実行されるかについての例示的な優先度を示す図である。
【図６】本発明の例示的な実施形態による、例示的なパケット処理パイプラインのステージ5の例示的な実施の詳細を示した図である。
【図７】本発明の例示的な実施形態による、測定およびカウントモジュール実施のさらなる詳細を示した図である。
【符号の説明】
【０１４９】
104  ハードウェアエンジン
106  連続フレームタイプ除去エンジン
108  テンプレート照合エンジン
110  フレームタイプ選択器
120  ヘッダフィールド値抽出器
132  L2探索エンジン
134  L3探索エンジン
136  プロトコルVLAN探索エンジン
142  パケット分類器
148  フローID選択器
154  アクションテーブル
156  交換応答変更器
158  ヘッダ変更器
162  フレームエンジン
164  パケット再構成モジュール
168  フロー測定およびカウントモジュール
200  ディシジョンツリー
210  ディシジョンテーブル
170  フェイルオーバブロック
【図１】
2006020317.tif 000014
【図２】
2006020317.tif 000015
【図３】
2006020317.tif 000016
【図４】
2006020317.tif 000017
【図５】
2006020317.tif 000018
【図６】
2006020317.tif 000019
【図７】
2006020317.tif 000020