JP3800546B2 - Ｔｃａｍを使用するデータフローの選択的なルーティング方法 - Google Patents

Description

【０００１】
１．技術分野
本発明は、ＴＣＡＭ（ternary content addressable memory）を用いるネットワーク通信に関し、特に、たとえば、ＭＰＬＳ（マルチプロトコル・ラベル・スイッチング）、インターネットプロトコル（ＩＰ）−仮想プライベートネットワーク（ＶＰＮ）データパケット、およびポリシーベースルーティングデータパケットのような、複数のデータフローの選択的なルーティングに関する。
【０００２】
発明の背景
ネットワークプロバイダは、ユーザの要求を満たす集中ネットワークサービスの提供に関心がある。ＩＰのサービス品質（ＱｏＳ）、ＭＰＬＳ（マルチプロトコル・ラベル・スイッチング）、およびサービス変換技術（非ＩＰサービスをＩＰに変換）における最新の技術を利用することによって、サービスプロバイダは、別々のサービス固有ネットワークを二者択一的に操作するように、マルチサービスネットワークアーキテクチャに専用のＩＰインフラを展開できる。
【０００３】
ＭＰＬＳは、ネットワークトラフィックフローの速度を上げ、その管理をより容易にする規格認可の技術である。ＭＰＬＳは、与えられたパケット順序のために特別なパス（道）を組み立てる。これによって、ルータが次のノードのアドレスを調べるために必要な時間を節約できる。各パケットは、パケットごとに付されたラベルによって識別される。ＭＰＬＳは、インターネットプロトコル（ＩＰ）、非同期転送モード（ＡＴＭ）、およびフレームリレーネットワークプロトコルと共に機能するので、マルチプロトコルと呼ばれている。ＭＰＬＳによって、大部分のパケットは、標準の開放型システム間相互接続（ＯＳＩ）のレイヤ３（ルーティング）レベルよりレイヤ２（スイッチング）レベルでフォワーディングされる。ＭＰＬＳは、全体的により速くトラフィックを移動することに加えて、サービス品質（ＱｏＳ）のためのネットワーク管理を容易にする。この技術は、ネットワークがより多くて異なる混合物のトラフィックを運び始めても、容易に採用できると期待されている。
【０００４】
ＭＰＬＳの本質は、短い固定長の「ラベル」の生成である。ラベルは、ＩＰパケットのヘッダの記号表示として作用し、パケットの進路決定のために使用される。一般的に、ＩＰデータパケットは、一連のルータを通じて、送信元から行き先まで送信される。ルータは、ＩＰデータパケットを受信し、その送信元および／またはあて先アドレスを読んで、ＩＰデータパケットを該ＩＰデータパケットに含まれるＩＰ行き先アドレスによって示される行き先か、ＩＰデータパケットが行き先アドレスに到達するまでＩＰデータパケットをフォワーディングする他のルータのいずれかに転送する。これを、ホップバイホップ・ルーティングという。ＩＰパケットヘッダは、ＩＰ送信元および／または行き先アドレスのための領域を有する。ルーティングインフォメーションプロトコル（ＲＩＰ）や、ＯＳＰＦ（Open Shortest Path First）のようなルーティングプロトコルは、パケットがその行き先に進められる際の「次のホップ（ｎｅｘｔ ｈｏｐ）」における他のマシンを、各マシンが理解することを可能とする。
【０００５】
ＩＰパケットは、自身がネットワークに入ると遭遇する最初のＭＰＬＳ装置によって、ラベルと共にカプセル化される。ＭＰＬＳエッジルータは、ＩＰヘッダの内容を分析し、パケットにカプセル化する適当なラベルを選ぶ。従来のＩＰルーティングとは対照的に、ＩＰヘッダで運ばれる行き先アドレスだけよりも多くの情報に基づいて、ルータ解析が行われる。ネットワーク内の全ての後続のノードでは、ＩＰヘッダではなく、ＭＰＬＳラベルがパケットのフォワーディングの決定に使用される。ＭＰＬＳラベルが付されたパケットは、ネットワークから離れる際、他のエッジルータによりラベルを削除される。ＭＰＬＳ用語で、パケットを操作するノードまたはルータを、ラベル・スイッチ・ルータ（ＬＳＲ）と呼ぶ。ＭＰＬＳルータは、ＭＰＬＳラベルに基づいて、スイッチングを決定し、パケットをフォワーディングする。ＬＳＲには、２つの広いカテゴリがある。高性能なパケットのクラス分けを行い、ネットワークの端で必要なラベルの貼り付け（および引き剥がし）をするＭＰＬＳエッジルータと、極めて高いバンド幅でラベルが付けられたパケットを処理できるコア（Ｃｏｒｅ）ＬＳＲとである。
【０００６】
従来のルーティング解法は、ＩＰアドレス指定の効率的な利用のため、ＩＰアドレスの記憶にＣＡＭ（content addressable memory）装置を利用していた。ＣＡＭは、記憶装置であり、その連想ＣＡＭアレイに記憶されるデータと特定の被比較データパターンとを比較するように指示される。全てのＣＡＭアレイまたはそのセグメントは、被比較データとのマッチングのために並列に検索される。マッチする場合、ＣＡＭ装置は、マッチフラグを立てることによって、そのマッチを示す。マッチが多数ある場合は、多数のマッチフラグを立てることにより示される。ＣＡＭ装置は、一般的に、高い優先順位のマッチングロケーションをマッチアドレスまたはＣＡＭインデックスに換算するプライオリティエンコーダを含む。一般に速いＣＡＭの並行探索能力は、ルータおよびネットワーク機器におけるアドレスフィルタリングおよびルックアップ、ポリシーベースルータにおける施行、暗号化／解読および圧縮／伸長アプリケーションのためのパターン認識、および他のパターン認識アプリケーションを含む多くのアプリケーションに役立つことが証明されている。
【０００７】
バイナリＣＡＭセルは、情報の２つの状態、すなわち、論理１状態、論理０状態の２つの状態を記憶することが可能である。バイナリＣＡＭセルは、概してＲＡＭセルおよび比較回路を含む。その比較回路は、被比較データをＲＡＭセルに記憶したデータと比較し、マッチするときに、所定の状態にマッチラインを駆動する。バイナリＣＡＭセルのカラムは、一つ以上の大域マスクレジスタに記憶されるマスクデータによって、グローバルにマスクされてもよい。ターナリＣＡＭ（ＴＣＡＭ）セルは、比較操作のために、情報の３つの状態を効果的に記憶するマスク・パー・ビット（mask-per-bit）セルである。情報の３つの状態とは、すなわち、論理１状態、論理０状態、および注意しない状態（don't care state）である。ターナリＣＡＭセルは、概して、各ターナリＣＡＭセルのためのローカルマスクデータを記憶する第２のＲＡＭを含む。ローカルマスクデータは、比較結果がマッチラインに影響をしないように、被比較データと第１のＲＡＭセルに記憶されたデータとの比較結果をマスクする。ターナリＣＡＭセルは、エントリ・パー・エントリ（entry-per-entry）基準で決定することについて、ユーザに柔軟性を提供する。エントリ・パー・エントリ基準のワード中のビットは、比較操作の間マスクされる。
【０００８】
米国特許第６，２３７，０６１号は、最長のプリフィックスを有するＣＡＭエントリが最高の数のアドレスまたはインデックスに配置されるように、ＣＩＤＲ（Classless Inter-Domain Routing）アドレスが予めソートされ、ターナリＣＡＭに読み込まれているシステムを開示している。ＣＩＤＲアドレスのプリフィックスの部分は、比較操作の間、各ＣＡＭエントリに関連付けられるマスクセルを設定するために使用される。各ＣＡＭエントリのマスクが外されたプリフィックス部分だけが、ＣＡＭ探索キーとして記憶されている行き先アドレスと比較される。各ＣＡＭエントリは、ネットワークＩＤ領域に対応してもよい。各ＣＡＭエントリは、関連するプリフィックス値に従ってマスクされ、ＴＣＡＭは、最長マッチング・プリフィックスを有するＣＡＭエントリの位置を決めるために、たった一回の検索操作を要求する。
【０００９】
他の若干のネットワークサービスは、地理的に分散する顧客サイトを相互に連結させるためのインターネットプロトコル（ＩＰ）−仮想プライベートネットワーク（ＶＰＮ）を含んで、ネットワークプロバイダにより提供される。ＶＰＮは、ネットワーク・インフラ・シェアリングを通じて、プライバシーおよびコスト効率を提供する。米国特許第６，２０５，４８８号は、共有ＭＰＬＳネットワークに接続された複数のルータを含む仮想プライベートネットワークを開示している。共有ＭＰＬＳネットワークは、共有ＭＰＬＳネットワークを渡る、動的に供給されたＶＰＮ情報により形成される。
【００１０】
ポリシーベース・ルーティングサービスは、顧客が選択的にパケットに異なるパスをとらせられることも述べられている。ポリシーベース・ルーティングの従来のアプリケーションは、以下を含む。（１）ポリシールータを横切る異なるインターネット接続を介する、異なるユーザの組からトラフィック発信をルーティングするための、ソースベース・トランジット・プロバイダ選択と、（２）サービスのタイプに基づいてトラフィックに優先順位をつけるためのサービス品質（ＱＯＳ）と、（３）低帯域幅、低コスト相手固定パスおよび高帯域幅、高コスト、スイッチングパス間のトラフィックを分散するためのコスト削減とを含む。
【００１１】
データトラフィックおよびルート・ルックアップの複数のタイプをクラス分けするためのＴＣＡＭの使用を通じて、速い検索能力を有する方法とシステムを提供することが望まれている。
【００１２】
発明の要約
本発明は、ＴＣＡＭを利用するルータにおける複数のデータフローを支援する方法およびシステムに関する。ここで、ＴＣＡＭへのアクセス数は、更新処理および後続ののルックアップの効率を改良するために最適化される。複数のデータフローに対応するために、ＴＣＡＭは、２つのパーティションに仕切られ、第１パーティションが高い優先順位を有するインデックスを含み、第２パーティションが低い優先順位を有するインデックス含む。たとえば、マルチプロトコル・ラベル・スイッチング（ＭＰＬＳ）フローおよびＩＰ仮想プライベートネットワーク（ＶＰＮ）フローは、第１パーティションに加えられ、ポリシーベース・ルーティングフローは、第２パーティションに加えられる。入力パケットの所定のプリフィックスに基づく後続のＴＣＡＭルックアップの間、ＭＰＬＳまたはＩＰ−ＶＰＮフローは、いかなるマッチング・ポリシーベース・ルーティングフローも包含する。マッチング・ポリシーベース・ルーティングフローとは、たとえば、アクセスコントロールリストまたはトラフィック管理フローによりクラス分けされるフローである。
【００１３】
ＭＰＬＳフローおよびＩＰ−ＶＰＮフローの場合、接続インデックス（ＣＩＸ）および行き先ＩＰアドレス（ＤＡ）によりクラス分けされるフロー、および、ＣＩＸだけによってクラス分けされるフローは、ＴＣＡＭの第１パーティションのトップから加えられ、ＤＡだけによってクラス分けされるフローは、第１パーティションのボトムから加えられる。この取り決めは、高いインデックスでＣＩＸアンドＤＡフローおよびＣＩＸオンリーフローがＤＡオンリーフローを包含する点、および、新たなフローを追加するときに必要なスワップ数の最適化のために、ＣＩＸアンドＤＡフローおよびＣＩＸオンリーフローが、ＤＡオンリーフローから切り離されている点で有利である。ＴＣＡＭへの書き込み回数を低減するために、フローインデックス・スペースは、ＴＣＡＭスペースに対応するエントリを有して使用される。スワップはインデックススペースにおいて実行され、変更されたエントリだけがＴＣＡＭに書き込まれる。
【００１４】
本発明は、以下の図面を参照することで、より完全に説明される。
【００１５】
図面の簡単な説明
図１は、本発明の教示に従ってルータのフローをクラス分けするためのシステムアーキテクチャを示す高水準機能ブロック図である。
【００１６】
図２は、フロー分級機およびフローマネージャの実行を示す概要図である。
【００１７】
図３は、ＴＣＡＭフローエントリを示す概要図である。
【００１８】
図４Ａは、接続インデックス（ＣＩＸ）によりクラス分けされるフローを記憶するためのプリフィックス・ツリーを示す概要図である。
【００１９】
図４Ｂは、行き先アドレス（ＤＡ）によりクラス分けされるフローを記憶するためのプリフィックス・ツリーを示す概要図である。
【００２０】
図５Ａは、ＤＡフローがない場合、フロー追加前に、ＣＩＸアンドＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２１】
図５Ｂは、ＤＡフローがない場合、フロー追加後に、ＣＩＸアンドＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２２】
図５Ｃは、ＤＡフローがある場合、フロー追加前に、ＣＩＸアンドＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２３】
図５Ｄは、ＤＡフローがある場合、フロー追加後に、ＣＩＸアンドＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２４】
図６Ａは、ＣＩＸ、ＤＡまたはＣＩＸフローが提供されていない場合、フロー追加前に、ＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２５】
図６Ｂは、ＣＩＸ、ＤＡまたはＣＩＸフローが提供されていない場合、フロー追加後に、ＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２６】
図６Ｃは、ＣＩＸ、ＤＡまたはＣＩＸフローが提供されている場合、フロー追加前に、ＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２７】
図６Ｄは、ＣＩＸ、ＤＡまたはＣＩＸフローが提供されている場合、フロー追加後に、ＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２８】
図７は、ポリシーベース・ルーティングフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【００２９】
詳細な説明
より詳細に本発明の好適な実施形態を以下に説明し、その実施例を添付図面内に図示する。図面および説明を通じて、可能な場合には、同じものまたは似ている部分の参照に、同じ参照番号を使用する。
【００３０】
図１を参照すると、本発明の教示に従ってルータ１０におけるフローのクラス分けおよびルーティングするためのシステムアーキテクチャを示す高水準機能ブロック図が示されている。フローは、データパケットのパケットヘッダ領域の内容から識別されるルールまたはポリシーに従うデータパケットの組である。パケットヘッダ領域は、たとえば、ソースＩＰアドレス、行き先ＩＰアドレス、ソースポート、行き先ポート、プロトコル識別、サービスのタイプ（ＴＯＳ）、接続インデックス（ＣＩＸ）、および、他の領域を含む。アーキテクチャは、三大要素、すなわち、制御プレーン１２、データプレーン１３、および、レイヤ２インタフェース１４を備えている。さまざまな要素間の相互作用は、対応する要素間の矢印の連続により示される。ソフトウェアにおいて実行される制御プレーン１２は、フローマネージャ１５と、データプレーン制御インタフェース１６と、フローコア制御１７と、ＩＰ、ユーザデータグラムプロトコル（ＵＤＰ）、および伝送制御プロトコル（ＴＣＰ）１８とを含む。ハードウェアにおいて実行されるデータプレーン１３は、フロー分級機２０、ＩＰフォワーダ（IP forwarder）２１、およびラベルフォワーダ（label forwarder）２２を含む。ＩＰトラフィックおよびＩＰ制御トラフィック２３は、フロー分級機２０で受信される。フロー分級機２０は、ＭＰＬＳフローの場合、ラベルフォワーダ２２により、または、ＭＰＬＳフローでない場合、ＩＰフォワーダ２１により、ルーティングＩＰトラフィックおよびＩＰ制御トラフィック２３をクラス分けし、行き先ルートを加えるために、フローマネージャ１５およびフローコア制御１７と相互に作用する。フローコア制御１７は、例えば、ＴＥＰ、レッドマネージャ（red manager）、ラベルマネージャ、ルートウォッチ、ルーティングマネージャおよびＦＩＢ、およびＩＰルーティングデータベースのようなソフトウェアモジュールを含む。本願明細書に述べられるように、本発明は、詳しくはアンバーネットワーク（AmberNetwork） ＡＳＲ２０００およびＡＳＲ２０２０の装置の用途に、極めて適すると共に、それは、類似する能力および機能を有する他のルータの用途にも同様に適している。アンバーネットワークＡＳＲ２０００およびＡＳＲ２０２０の技術マニュアルについては、完全な記述に代えて、参照によって本願明細書に引用したものとする。
【００３１】
図２は、フロー分級機２０およびフローマネージャ１５の本実施形態の実行を示す概要図である。本実施例では、フロー分級機２０は、フローＴＣＡＭ（ternary content addressable memory）３０を含む。フローＴＣＡＭ３０は、ハードウェアメモリー素子であり、ＴＣＡＭ内の全てのエントリが入力されたパケットヘッダ領域に対して並列に比較され、最初のマッチ・エントリが単一のクロックサイクルにおいて選ばれる。適切なＴＣＡＭは、この出願に参照により組み込まれる米国米国特許第６，０８１，４４０号で説明されるように、ララテクノロジー社により、サンホゼ、カリフォルニアで製造される。各フローＴＣＡＭ３０のエントリは、インデックス３２によって、アドレスが与えられ、インデックスが付けられる。インデックス３２は、インデックスまたは数字で表したアドレスである。インデックス３２は、最も低いインデックス３２ａから、最も高いインデックス３２ｎまで、最も低いインデックス３２ａで優先順位が最も高く、また、最も高いインデックス３２ｎで優先順位が最も低くなるように、編成される。
【００３２】
図３は、フローＴＣＡＭ３０に記憶される代表的なＴＣＡＭフローエントリ３３を示す。ローカルマスク３４は、フローＴＣＡＭルックアップ操作に対して論理０、論理１、または注意しない（don't care）状態のいずれの場合でも、効果的にフローＴＣＡＭに記憶されるために、各ＴＣＡＭフローエントリ３３と関連付けられている。たとえば、ローカルマスク３４のビットが論理１である場合、対応するＴＣＡＭフローエントリ３３のビットは、後続のフローＴＣＡＭのルックアップ操作の間、対応する入力データパケットのビットと比較される。逆にいえば、ローカルマスク３４が論理０である場合、対応するＴＣＡＭフローエントリ３３のビットは、後続のフローＴＣＡＭのルックアップ操作の間、比較されない。あるいは、本発明の他の実施形態では、マスクビットスキーマは論理１に等しくなるように変換され、ＴＣＡＭフローエントリの対応するビットはマスクされ、マスクビットが論理１である場合、ＴＣＡＭフローエントリの対応するビットが比較される。プリフィックスは、フローＴＣＡＭ３０内でマッチングされるためのパケットヘッダの行き先ＩＰアドレスのビット番号を示すための、行き先ＩＰアドレスのように、フローＴＣＡＭエントリ３３内で１以上の領域が連合してなる。後続のフローＴＣＡＭルックアップ操作において、マスクが外されたフローＴＣＡＭエントリと、入力パケットヘッダビットに対応する所定のプリフィックスとの間にマッチングがある場合、フローＴＣＡＭ３０、またはＳＲＡＭのような連携される外部メモリに記憶されるルーティングデータと同様に、マッチングするＴＣＡＭフローエントリ２２のインデックスは出力として提供される。
【００３３】
フローマネージャ１５は、フローＴＣＡＭ３０のデータ構造機構を提供するために使用される。図２を参照すると、フローマネージャ１５は、インデックス３２を一つ以上の論理的パーティションに仕切ることができる。フローは、フローのタイプに対して望ましい優先順位に従い、パーティションに割り当てられる。本実施例において、インデックス３２は、最も低いインデックス３２ａを含むパーティション３６ａと、最も高いインデックス３６ｎを含むパーティション３６ｂとに仕切られる。ＦＴＣＡＭ＿Ｐａｒｔｉｔｉｏｎインデックスは、パーティション３６ａおよびパーティション３６ｂの間に位置する。図２に示す本実施例において、ＭＰＬＳおよびＩＰ−ＶＰＮフローは、最も高い優先順位を有することが決められ、パーティション３６ａに割り当てられる。ポリシーベース・ルーティングフローは、低い優先順位を有することが決められ、パーティション３６ｂに割り当てられる。ポリシーベース・ルーティングフローは、アクセス制御リスト（ＡＣＬ）フローおよびトラフィックマネージャ（ＴＥ）フローによりクラス分けされるデータを包含できる。したがって、より高い優先順位を割り当てられたＭＰＬＳフローおよびＩＰ−ＶＰＮフローは、低い優先順位が割り当てられたＡＣＬフローおよびＴＥフローよりも先に、後続のフローＴＣＡＭ３０内のルックアップにおいて見つけられる。ＭＰＬＳフローまたはＩＰ−ＶＰＮフローは、ＴＣＡＭ３０のいかなるＡＣＬフローおよびＴＥフローのマッチングも含む。
【００３４】
フローインデックス・スペース３８は、フローＴＣＡＭ３０のデータ構成に対応するためにフローマネージャ１５に維持される。全てのフロースワッピングは、フローインデックス・スペース３８において実行され、変更エントリだけはフローＴＣＡＭ３０に書き込まれる。
【００３５】
本発明の実施形態において、ポインタおよびプリフィックス・ツリーのアレイは、図４Ａおよび４Ｂに示すように、フローインデックス・スペース３８にＭＰＬＳおよびＩＰ−ＶＰＮフローを記憶するために使われる。パケットヘッダの接続インデックスＣＩＸおよび行き先ＩＰアドレス（ＤＡ）領域によりクラス分けされるフローは、ＣＩＸプリフィックス・ツリー４０に記憶される。各接続インデックス（ＣＩＸ１〜ＣＩＸ１６Ｋ）は、プリフィックス・ツリー４０のノード４１ａ〜４１ｎを伴う。行き先ＩＰアドレスベースのルックアップは、それぞれのノード４１ａ〜４１ｎに記憶されるプリフィックスで最長マッチ（ｌｏｎｇｅｓｔ ｍａｔｃｈ）を見つけるために実行される。フローは、フローＴＣＡＭ３０ルックアップの間、正しいフローにマッチするために維持される。可変ｇＭａｘＣｉｘＤａＦｉｘは、フローインデックス・スペース３８において使用され、ＣＩＸアンドＤＡフロー、およびＣＩＸオンリーフローの最大のＴＣＡＭインデックスを示す。行き先ＩＰアドレスだけによりクラス分けされるフローは、ＤＡプリフィックス・ツリー４２に記憶される。各ＤＡは、プリフィックス・ツリー４２のノード４４を伴う。
【００３６】
可変ｇＭｉｎＤａＯｎｌｙＦｉｘは、フローインデックス・スペース３８において使用され、ＤＡオンリーフローのための最小のフローＴＣＡＭインデックスを示す。
【００３７】
ソフトウェアモジュールは、ＴＣＡＭ３０のＭＰＬＳおよびＩＰ−ＶＰＮフロー構築のために、フローマネージャ１５において実行される。代表的なソフトウェアモジュールを、テーブル１に例示する。
【００３８】
【表１】

【００３９】
図５Ａ−５Ｄは、ＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭ３０のデータ構成の実施例を示す。フローは、フローＴＣＡＭ３０ルックアップの間、正しいフローにマッチさせるために維持される。パーティション３６ａは、低いインデックス部分５０ａおよび高いインデックス部分５０ｂに分割される。低いインデックス部分５０ａは、低いインデックスまたはアドレス範囲に対応し、高いインデックス部分５０ｂは高いインデックスまたはアドレス範囲に対応する。パケットヘッダの接続インデックス（ＣＩＸ）および行き先ＩＰアドレス（ＤＡ）領域（ＣＩＸ、ＤＡとして示す）によりクラス分けされるフローは、低いインデックス部分５０ａに割り当てられる。パケットヘッダのＣＩＸだけによりクラス分けされるフローも、低いインデックス部分５０ａに割り当てられる。パケットヘッダのＤＡだけによりクラス分けされるフローは、高いインデックス部分５０ｂに割り当てられる。ローカルマスク３４は、フローＴＣＡＭ３０の比較操作に使用する特定の種類のデータフロー、たとえば、上記のＣＩＸ、ＤＡフロー、ＣＩＸだけのフロー、およびＤＡだけのフローを効果的に記憶するために、各フローＴＣＡＭエントリ３３に適用できる。例えば、ＤＡのローカルマスクビットが「０」で、ＣＩＸのローカルマスクビットが全て「１」である場合、ＣＩＸだけのフローが発生する。
【００４０】
ＣＩＸ、ＤＡ、またはＣＩＸだけによりクラス分けされるフローのＴＣＡＭ３０への追加の間、ＴＣＡＭ３０内の自由エントリ（ｆｒｅｅ ｅｎｔｒｙ）は、低いインデックス部分５０ａの低いインデックス３２ａから検索される。自由エントリは、Ｆｉｘとして示す。ＤＡフローとしてクラス分けされるフローの追加の間、ＴＣＡＭ３０の自由エントリは、最も高いインデックス部分５０ｂの最も高いインデックス３２ｂから検索される。最も低いインデックス部分５０ａの最大値に対応するインデックスは、ｇＭａｘＣｉｘＤａＦｉｘとして確立され、最も高いインデックス部分５０ｂの最小値に対応するインデックスは、ｇＭｉｎＤａＯｎｌｙＦｉｘとして確立される。この意味で、空きスペース５４は、最大で、低いインデックス部分５０ａおよび高いインデックス部分５０ｂの間に設けられる。それによって、ＣＩＸ、ＤＡフローおよびＣＩＸオンリーフローを一緒に、および、ＤＡオンリーフローを一緒に維持することができる。また、ＤＡフローからＣＩＸ、ＤＡフローおよびＣＩＸオンリーフローを分けて、維持することができる。ＴＣＡＭ３０からＣＩＸ、ＤＡまたはＣＩＸだけによりクラス分けされるフローを削除する際、対応するインデックス３２のエントリは、フロースペース３８において無効にされる。その後、後続のＣＩＸ、ＤＡフローおよびＣＩＸだけによってクラス分けされたフローの追加の際、無効にされたエントリは、自由エントリの検索中に低いインデックス部分５０ａの最も低いインデックス３２ａから見つけられ、以前に無効にされたエントリを再利用するために追加される。ＴＣＡＭ３０が実質的に容量の限界である場合だけ、ＣＩＸ、ＤＡフローまたはＣＩＸオンリーフローを挿入するためにＤＡオンリーフローをスワップし、または、ＤＡオンリーフローを挿入するためにＣＩＸ、ＤＡフローまたはＣＩＸオンリーフローをスワップする必要がある。
【００４１】
図５Ａ、５Ｂは、ＤＡオンリーフローが存在せず、または、自由ＴＣＡＭエントリ（Ｆｉｘ）がｇＭｉｎＤａＯｎｌｙＦｉｘよりも低いインデックス値でＤＡオンリーフロー以上である場合の、ＣＩＸ、ＤＡフローおよびＣＩＸオンリーフローの割り当てを示す。ｇＭａｘＣｉｘＤａＦｉｘインデックスエントリは、Ｆｉｘに対応するインデックスの直後に設定される。図５Ｃ−５Ｄは、現在ＤＡオンリーフローがあり、または、自由ＴＣＡＭエントリ（Ｆｉｘ）がＤＡオンリーフローの間にある場合の、ＣＩＸ、ＤＡ、およびＣＩＸだけのフローの割り当てを示す。本実施例において、ＴＣＡＭ３０はほぼ一杯である。最小のインデックス３２ａからｇＭａｘＣｉｘＤａＦｉｘおよびｇＭｉｎＤａＯｎｌｙＦｉｘインデックスを超えて、自由エントリは存在しない。したがって、ｇＭａｘＣｉｘＤａＦｉｘおよびｇＭｉｎＤａＯｎｌｙＦｉｘインデックスは、近接したインデックスである。自由エントリは、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスおよび最も高いインデックス３２ｂの間で利用可能である。例えば、自由エントリは、ＤＡフローの先行する削除によって、Ｄａフロースペース内に発生する。ＣＩＸ、ＤＡ、またはＣＩＸだけによりクラス分けされるフローのために、自由エントリ（Ｆｉｘ）を使用するために、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスのＤＡフローは、Ｆｉｘに移され、それによって、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスを利用可能にする。ＣＩＸ、ＤＡ、またはＣＩＸだけによりクラス分けされるフローは、ｇＭｉｎＤａＯｎｌｙＦｉｘ用の現在のインデックスに書き込まれる。ｇＭａｘＣｉｘＤａＦｉｘインデックスは、ＣＩＸ、ＤＡまたはＣＩＸだけによりクラス分けされるフローのために、ＴＣＡＭエントリの書き込み時に設定され、ｇＭｉｎＤａＯｎｌｙＦｉｘエントリは、ＴＣＡＭエントリの書き込み直後に設定される。ＴＣＡＭ３０内の最も低いインデックス３２ａとｇＭａｘＣｉｘＤａＯｎｌｙＦｉｘとの間の他のＣＩＸ、ＤＡ、およびＣＩＸオンリーフローは、適当な順番で含まれるように調整される。ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスと最も高いインデックス３２ｂとの間の他のＤＡだけのフローは、適当な順番で含まれるように調整される。
【００４２】
ソフトウェアモジュールは、ＴＣＡＭ３０にＣＩＸ、ＤＡフローおよびＣＩＸオンリーフローを追加するために、フローマネージャ１５において実行される。現在のフローに対するポインタを、ｐｆｌｏｗという。自由エントリに対するポインタを、ｆｉｘという。ＴＣＡＭフローエントリ３３は、ＡｄｊｕｓｔＡｎｄＷｒｉｔｅＣｉｘＤＡ（ｐｆｌｏｗ、ｆｉｘ）機能によってフローＴＣＡＭ３０に書き込まれる。後述するその機能は、同じＣＩＸ内の他のＤＡのローカルマスク３４に基づいて、フローＴＣＡＭ３０へのＴＣＡＭフローエントリ３３の書き込みを調整するものである。代表的なソフトウェアモジュールを、テーブル２に例示する。
【００４３】
【表２】

【００４４】
ＣＩＸ、ＤＡフロー、ＣＩＸオンリーフロー、およびＤＡオンリーフローの挿入の間、フローＴＣＡＭ３０内のフローは調整される。この調整では、最も低いインデックスまたは最も低い数値であり、最も高い優先順位を有するインデックスに配置される最長プリフィックスを伴うＴＣＡＭエントリと、最も高いインデックスまたは最も高い数値であり、もっとも低い優先順位を有するインデックスに配置される最短のプリフィックスを伴うプリフィックス値の減少により続くＴＣＡＭエントリとを有するように、フローＴＣＡＭ３０が整理される。テーブル３および４は、フローマネージャ１５において、ＤＡオンリーフローの調整および書き込みや、ＦｉｘアンドＤＡフローの調整および書き込みが実行されるそれぞれのソフトウェアモジュールを示す。それらのモジュールは、テーブル１に示すソフトウェアモジュールにおいて使用される。
【００４５】
テーブル３
１．ＡｄｊｕｓｔＡｎｄＷｒｉｔｅＤＡ（ｐＦｌｏｗ）機能を開始する。
２．フローの行き先ＩＰアドレスのマスク長を用いて、最初に、プリフィックス・ツリー４２内の短いプリフィックスフローを修正（ｆｉｘ）する。より短いプリフィックスノードが＜ＤＡ＞オンリープリフィックス・ツリー４２内で見つけられ、見つけられたノードのインデックスがｐＦｌｏｗノードのインデックスより小さい場合、その２つのフローをスワップし、その２番目に小さいフローだけをフローＴＣＡＭ３０に書き込む。そして、包含されるルータの位置を決めるために、移動されたフローを用いて検索を続行する。
３．最後の最も小さいフローをその正しい場所に書き込む。後で再書き込みされてはならないのでこれを記憶しておく。
４．この時点で、ｐＦｌｏｗは、最短のプリフィックスフローを指示することとなる。最短のプリフィックスフローのインデックスは、最長のプリフィックスマッチ（ＬＰＭ）プロパティに続くように調整され、フローＴＣＡＭ３０に挿入されるべきオリジナルのフローとマッチングされなくてはならない
５．ＴＣＡＭ３０内の長いプリフィックスフローを修正する。マスク長３２から開始し、現在のマスク長から短くしていき、包含される最大のフローインデックスフローを見つける。
６．見つけられたフローのフローインデックスが現在のフローのインデックスより大きい場合、同じ宛先に対するより長いプリフィックスを有するフローは、より短いプリフィックスを有する現在のものより前のものであることを意味する。この場合、ＴＣＡＭ３０のその２つのフローを交換し、フロー内のインデックス値を修正する。２番目に大きいフローをＴＣＡＭ３０へ書き込む。
７．最後の最も大きいフローを、その正しい場所に書き込む。これが上記ステップ３で既に書き込まれたフローと同じであれば、ＴＣＡＭ３０は再度書き込まれることはない。
８．ＡｄｊｕｓｔＡｎｄＷｒｉｔｅＤＡ（ｐＦｌｏｗ）機能を終了する。
【００４６】
テーブル４
１．ＡｄｊｕｓｔＡｎｄＷｒｉｔｅＣｉｘＤＡ機能を開始する（ｐＦｌｏｗ、Ｆｉｘ）。
２．そのフローの行き先ＩＰアドレスのマスク長を使用する。最初にプリフィックス・ツリー４０内の短いプリフィックスフローを修正する。より短いプリフィックスノードが見つけられ、見つけたノードのインデックスがｐＦｌｏｗノードよりも小さい場合、その２つのノードを交換し、２番目に小さいフローだけをフローＴＣＡＭ３０に書き込む。そして、包含されるルータの位置を決めるために、移動されたフローを用いて検索を続行する。
３．最後の最も小さいフローをその正しい場所に書き込む。後で再書き込みされてはならないのでこれを記憶しておく。
４．この時点で、ｐＦｌｏｗは、最短のプリフィックスフローを指示する。最短のプリフィックスフローのインデックスは、ＬＰＭプロパティに続くように調整され、フローＴＣＡＭ３０に挿入されるべきオリジナルのフローとマッチングされる。
５．ＴＣＡＭ３０の長いプリフィックスフローを修正する。マスク長３２から開始し、現在のマスク長から短くして、包含される最大のフローインデックスフローを見つける。
６．見つけられたフローのフローインデックスが現在のフローのインデックスより大きい場合、それは、同じ宛先に対するより長いプリフィックスを有するフローは、より短いプリフィックスを有する現在のものより前のものであることを意味する。この場合、ＴＣＡＭ３０のその２つのフローを交換し、フロー内のインデックス値を修正する。２番目に大きいフローをＴＣＡＭ３０へ書き込む。
７．最後の最も大きいフローを、その正しい場所に書き込む。これが上記ステップ３で既に書き込まれたフローと同じであれば、ＴＣＡＭ３０は再度書き込まれることはない。
８．ＡｄｊｕｓｔＡｎｄＷｒｉｔｅＣＩＸ、ＤＡ（ｐＦｌｏｗ、Ｆｉｘ）を終了する。
【００４７】
図６Ａ〜６Ｂは、第１の自由ＴＣＡＭエントリ（Ｆｉｘ）が、ＣＩＸ、ＤＡフローおよびＣＩＸオンリーフローのいずれもの後に配置される場合、または、ＣＩＸ、ＤＡフローがない場合の、ＤＡオンリーフローの割り当てを示す。ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスエントリは、Ｆｉｘに対応するインデックスに設定される。図６Ｃ〜６Ｄは、第１の自由ＴＣＡＭエントリ（Ｆｉｘ）がＣＩＸ、ＤＡまたはＣＩＸだけのフローの間にある場合の、ＤＡフローの割り当てを示す。本実施形態において、ＴＣＡＭ３０はほぼ満ちている。最も高いインデックス３２ｂからｇＭｉｎＤａＯｎｌｙＦｉｘインデックスおよびｇＭａｘＣｉｘＤａＦｉｘインデックスまでに、自由エントリは存在しない。したがって、ｇＭａｘＣｉｘＤａＦｉｘインデックスおよびｇＭｉｎＤａＯｎｌｙＦｉｘインデックスは、隣接している。自由エントリは、ｇＭａｘＣｉｘＤａＦｉｘインデックスおよび最も低いインデックス３２ａの間で利用可能である。たとえば、自由エントリは、ＣＩＸ、ＤＡフローまたはＣＩＸオンリーフローの先の削除により、ＣＩＸ、ＤＡおよびＣＩＸオンリーフロースペースにおいて発生できる。ＤＡだけによりクラス分けされるフローのために、自由なエントリ（Ｆｉｘ）を使用するために、ｇＭａｘＣｉｘＤａＦｉｘインデックスのＣＩＸ、ＤＡフローまたはＣＩＸオンリーフローがＦｉｘに移され、それによって、利用可能なｇＭａｘＣｉｘＤａＦｉｘインデックスを作る。ＤＡによりクラス分けされるフローは、ｇＭａｘＣｉｘＤａＦｉｘ用の現在のインデックスに書き込まれる。ｇＭｉｎＤａＯｎｌｙＦｉｘエントリは、ＴＣＡＭエントリの書き込み時に設定され、ｇＭａｘＣｉｘＤａＦｉｘエントリはＴＣＡＭエントリの書き込み直前に設定される。最も高いインデックス３２ｂおよびｇＭｉｎＤａＯｎｌｙＦｉｘインデックス間の他のＤＡフローは、適当な順番で含まれるように調整される。ｇＭａｘＣｉｘＤａＦｉｘおよび最も低いインデックス３２ａ間のその他のＣＩＸ、ＤＡおよびＣＩＸオンリーフローは、適当な順番で含まれるように調整される。
【００４８】
ソフトウェアモジュールは、ＤＡフローをＴＣＡＭ３０に加えるために、フローマネージャ１５において実行される。テーブル５に、代表的なソフトウェアモジュールを示す。
【００４９】
【表３】

【００５０】
インタフェースが落ちた場合、フローマネージャ１５のクライアントは、ＴＣＡＭ３０のフローを削除する責任がある。フローマネージャ１５は、アプリケーション操作に基づいて、ルートを取り下げるためにアプリケーションプログラミングインタフェース（ＡＰＩ）を提供する。たとえば、ＩＰ回路が落ちた場合、接続マネージャは、ＩＰタスクに知らせ、ＶＰＮマネージャは、このアラームを受信する。ＶＰＮマネージャは、回路識別子に基づいて、順番にルートをフローＴＣＡＭ３０から取り戻す。
【００５１】
ソフトウェアモジュールは、ＴＣＡＭ３０のフローを削除するフローマネージャ１５において実行される。テーブル６に代表的なソフトウェアモジュールを示す。
【００５２】
テーブル６
１．フローＩＤが制限範囲内であることをチェックする。
２．フローＩＤに対応するフローを取得する。ｐＦｌｏｗ＝ＧｅｔＦｌｏｗＡｔＩｎｄｅｘ（ｆｌｏｗＩｄ）
３．正しいツリーでノードを見つける。ｐＦｌｏｗがＣｉｘを有する場合、このＣｉｘのためのプリフィックス・ツリー４０を検索し、その他の場合、プリフィックス・ツリー４２を検索する。
４．見つけたノードを削除し、それぞれのツリーを調整し、ノードメモリを解放する。
５．フロースペース・インデックスエントリを解放する。
６．フローＩＤ＝＝ｇＭａｘＣｉｘＤａＦｉｘまたはフローＩＤ＝＝ｇＭｉｎＤａＯｎｌｙＦｉｘである場合、これらの変数を変更する。ｇＭａｘＣｉｘＤａＦｉｘインデックスのフローが削除されている場合、それが、有効な＜Ｃｉｘ、ＤＡ＞または＜Ｃｉｘ＞オンリーフローのインデックスになるまで、ｇＭａｘＣｉｘＤａＦｉｘを減少する。ＧＭｉｎＤａＯｎｌｙＦｉｘインデックスのフローが削除されている場合、それが、有効な＜ＤＡ＞だけのフローのインデックスになるまで増加する。
７．フローメモリを解放し、ＴＣＡＭ３０のフローを無効にする。
【００５３】
図７に示すように、ＡＣＬフローおよびトラフィックマネージャ（ＴＥ）フローは、フローマネージャ１５によって、フローＴＣＡＭに対応するフローインデックス・スペースに内部記憶される。そのＡＣＬフローおよびＴＥフローは、アクセスコントロールリスト（ＡＣＬ）を形成するコマンドラインインタフェース（ＣＬＩ）に基づいて、厳密に整列される。ＡＣＬは、特定種類のネットワークトラフィックを許可または否定するために、一般にネットワークインターフェースに適用される。特定のＡＣＬフローにマッチしている全てのパケットは、通過を許可され、ネットワークルートが決定される。ＡＣＬフローにマッチしていない全てのパケットは廃棄され、または、サービスタイプ（ＴＯＳ）の警備または成形の操作がそのパケット上で実行される。グローバルアクセスリストは、全てのインタフェースで使われる。
【００５４】
フローＴＣＡＭ３０に追加されるとき、ＡＣＬおよびＴＥフローは適切に維持される。フローは、パーティション３６ｂのトップ６０から始まっているフローＴＣＡＭ３０内に位置する次の利用可能なインデックスエントリに加えられる。パーティション３６ｂは、さらに、部分６２ａおよび６２ｂに再分割される。部分６２ａは、インタフェースに適用されるＡＣＬに使用され、部分６２ｂは、他のＡＣＬがマッチしない場合、グローバルＡＣＬのために使用される。ＧＡＣＬ＿ＰＡＲＴＩＴＩＯＮ変数は、部分６２ａおよび６２ｂのパーティションサイズを定義するために使用できる。ｇＭａｘＡＣＬＦｉｘ変数は、部分６２ａのＡＣＬおよびＴＥフローのための最大フローＴＣＡＭインデックスを定義する。ｇＧｌｏｂａｌＡＣＬＦｉｘ変数は、部分６２ｂのグローバルＡＣＬおよびＴＥフローのための最大フローＴＣＡＭインデックスを定義する。
【００５５】
ポリシーベースＡＣＬおよびＴＥフローは、ｇＭａｘＡＣＬＦｉｘ変数の場所で追加され、該ｇＭａｘＡＣＬＦｉｘ変数はインクリメントされる。ｇＭａｘＡＣＬＦｉｘがＧＡＣＬ＿ＰＡＲＴＩＴＩＯＮ変数に等しくなる場合、部分６２ｂはいっぱいで、どれかフローが削除されるまで、これ以上ＡＣＬフローを追加できない。ＡＣＬフローは、ソースまたは行き先ポートの範囲を明示できる。ソースまたは行き先ポートの範囲を明示するＡＣＬフローは、一部の範囲をカバーするローカルマスク３４と共に、複数フローにマップされる。したがって、異なるマスクを有する最適ナンバーのフローは、明示された範囲をカバーするために決定される。ＴＣＡＭの複数フローにマップされるフローのために、アプリケーションプログラミングインタフェース（ＡＰＩ）は、割り当てられたローカルマスク３４を有するピアフローを生成し、親フローと共にピアフローをフローＴＣＡＭ３０に加える。そのフローは、フローマネージャ１５によって管理される。グローバルＡＣＬフローは、ｇＧｌｏｂａｌＡＣＬＦｉｘ変数で加えられ、それから、ｇＧｌｏｂａｌＡＣＬＦｉｘ変数はインクリメントされる。ｇＧｌｏｂａｌＡＣＬＦｉｘ変数がＦＭ＿ＭＡＸ＿ＦＩＸ変数に等しくなる場合、どれかフローが削除されるまで、これ以上のグローバルＡＣＬフローを追加できない。
【００５６】
フローマネージャ１５は、ＴＣＡＭ３０からフローを削除するためのソフトウェアモジュールを含む。単一のフローの削除のために、そのフローは、フローインデックス・スペース３８から削除され、フローＴＣＡＭ３０において、無効にされる。第一に、ＡＰＩ６６は、ＴＣＡＭ３０から単一のフローを削除するために使われる。単一のフローがピアフローを有する場合、全てのピアもまた、削除される。フローＴＣＡＭ３０内に留まるフローは、空のフロースペースを充填するために直ちに圧縮（ｃｏｍｐａｃｔ）される。削除されたフローの後の全てのフローは、一つのインデックスに移され、ＴＣＡＭ３０に書き込まれる。ｇＭａｘＡＣＬＦｉｘ変数の値は、適宜調整される。
【００５７】
複数フロー削除のために、フローリストに供給された全フローは、削除され、それから、残留するフロー上で圧縮が実行される。第２のＡＰＩ６７は、ＴＣＡＭ３０から複数フローを削除するために、フローのリストを削除するために使用される。第一の空のフロースペースは、次の利用可能な占有フローによって、最初に充填され、これは全フローが小型化されるまで繰り返される。ｇＭａｘＡＣＬＦｉｘ変数までの全空フロースペースが満たされる。したがって、ｇＭａｘＡＣＬＦｉｘ変数の値は調整される。
【００５８】
前述の説明からみて、本発明の多数の修正および他の実施形態は、当業者にとって明らかである。特定の典型的なコンピュータコードが様々な言語の様々な方法で実行されることができると明らかに理解されなければならない。そして、それは様々な多くのハードウェアプラットホームに等しく適している。
【００５９】
上述の実施形態は、多くの可能な実施形態のほんの一実例であると理解される。それは、本発明の原理のアプリケーションを代表するものである。多数の様々な他の変更は、本発明の精神と範囲から逸脱することなく、当業者によって、これらの原理に従って直ちに発明されることができる。
【図面の簡単な説明】
【図１】 図１は、本発明の教示に従ってルータのフローをクラス分けするためのシステムアーキテクチャを示す高水準機能ブロック図である。
【図２】 図２は、フロー分級機およびフローマネージャの実行を示す概要図である。
【図３】 図３は、ＴＣＡＭフローエントリを示す概要図である。
【図４】 図４Ａは、接続インデックス（ＣＩＸ）によりクラス分けされるフローを記憶するためのプリフィックス・ツリーを示す概要図である。
図４Ｂは、行き先アドレス（ＤＡ）によりクラス分けされるフローを記憶するためのプリフィックス・ツリーを示す概要図である。
【図５】 図５Ａは、ＤＡフローがない場合、フロー追加前に、ＣＩＸアンドＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
図５Ｂは、ＤＡフローがない場合、フロー追加後に、ＣＩＸアンドＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
図５Ｃは、ＤＡフローがある場合、フロー追加前に、ＣＩＸアンドＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
図５Ｄは、ＤＡフローがある場合、フロー追加後に、ＣＩＸアンドＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【図６】 図６Ａは、ＣＩＸ、ＤＡまたはＣＩＸフローが提供されていない場合、フロー追加前に、ＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
図６Ｂは、ＣＩＸ、ＤＡまたはＣＩＸフローが提供されていない場合、フロー追加後に、ＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
図６Ｃは、ＣＩＸ、ＤＡまたはＣＩＸフローが提供されている場合、フロー追加前に、ＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
図６Ｄは、ＣＩＸ、ＤＡまたはＣＩＸフローが提供されている場合、フロー追加後に、ＤＡによりクラス分けされるＭＰＬＳおよびＩＰ−ＶＰＮフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【図７】 図７は、ポリシーベース・ルーティングフローのためのフローＴＣＡＭのデータ構成を示す概要図である。
【符号の説明】
１０…ルータ、
１２…制御プレーン、
１３…データプレーン、
１４…インタフェース、
１５…フローマネージャ、
１６…データプレーン制御インタフェース、
１７…フローコア制御、
２０…フロー分級機、
２１…フォワーダ、
２２…ラベルフォワーダ、
２３…制御トラフィック、
３０…フローＴＣＡＭ、
３２、３２ａ〜ｎ…インデックス、
３３…フローエントリ、
３４…ローカルマスク、
３６ａ、ｂ…パーティション、
３８…フローインデックス・スペース、
４０…プリフィックス・ツリー、
４２…オンリープリフィックス・ツリー、
５０ａ、ｂ…インデックス部分。

Claims (67)

1. ルータ内の複数のデータフローをクラス分けするための方法であって、
   ＴＣＡＭ（ternary content addressable memory）を少なくとも第１のパーティションと第２のパーティションに仕切る工程と、
   所定の順番で、前記第１のパーティションに、前記複数のデータフローの最初の一つ以上の第１フローＴＣＡＭエントリを読み込む工程と、
   所定の順番で、前記第２のパーティションに、前記複数のデータフローの２番目の一つ以上の第２フローＴＣＡＭエントリを読み込む工程と、
   前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのビットのそれぞれが複数のマスクにより個々にマスクされるように、前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのそれぞれに対して、対応する前記マスクのビット値を設定する工程と、
   前記一つ以上の第１ＴＣＡＭエントリのマッチングが前記一つ以上の第２ＴＣＡＭエントリのいかなるマッチングも包含するように、入力されるパケットの所定のパケットヘッダ情報を含むプリフィックスを、読み込まれた一つ以上の前記第１ＴＣＡＭエントリおよび一つ以上の前記第２ＴＣＡＭエントリと比較する工程と、
   を有し、
   前記第１のパーティションは、最も低いインデックスからパーティションインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
   前記第２のパーティションは、最も高いインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含むＴＣＡＭを用いたデータフローの選択的ルーティング方法。
2. 複数の前記第１データフローは、ＭＰＬＳフローまたはＩＰ−ＶＰＮフローである請求項１に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
3. 複数の前記第２データフローは、ポリシーベースのルーティングフローである請求項１に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
4. 前記ポリシーベースのルーティングフローは、アクセスコントロールリスト（ＡＣＬ）フローである請求項３に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
5. 前記ポリシーベースのルーティングフローは、トラフィックマネージャフローである請求項３に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
6. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する工程と、
   一つ以上の前記第１ＴＣＡＭエントリを読み込む工程および一つ以上の前記第２ＴＣＡＭエントリを読み込む工程の前に、前記フローインデックス・スペースにおける、前記第１ＴＣＡＭエントリの前記所定の順番および前記第２ＴＣＡＭの前記所定の順番を決定する工程と、
   をさらに含む請求項１に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
7. 前記ＭＰＬＳまたはＩＰ−ＶＰＮフローは、接続インデックス（ＣＩＸ）および行き先アドレス（ＤＡ）、ＣＩＸだけ、またはＤＡだけによってクラス分けされる請求項２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
8. 前記第１パーティションは、第１部分および第２部分に分割され、前記第１部分は、前記最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスの範囲で最も高い優先順位を有するインデックスを含み、前記第２部分は、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含み、ＣＩＸおよびＤＡ、並びにＣＩＸだけによってクラス分けされる前記フローは、前記第１部分に割り当てられ、ＤＡだけによりクラス分けされる前記フローは、前記第２部分に割り当てられる請求項７に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
9. ＣＩＸおよびＤＡによってクラス分けされる前記フロー、およびＣＩＸだけによりクラス分けされる前記フローは、前記ｇＭａｘＣｉｘＤａＦｉｘインデックスから始まる前記第１部分に読み込まれ、前記ＤＡだけによってクラス分けされるフローは、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから始まる前記第２部分に読み込まれる請求項８に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
10. 前記第１パーティションは、第１部分および第２部分に分割され、前記第１部分は、最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２部分は、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスまでの範囲で最も低い優先順位を有するインデックスと、前記第２部分の前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスに隣接して設けられる前記ｇＭａｘＣｉｘＤａＦｉｘインデックスと、該第２部分内で前記ｇＭｉｎＤａＯｎｌｙＦｉｘより下に配置されるフリーエントリとを含み、
    （ａ） 前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスでＤＡだけによりクラス分けされるフローを、前記フリーエントリに移動する工程と、
    （ｂ） 工程（ａ）に続いて、ＣＩＸおよびＤＡ、または、ＣＩＸだけによりクラス分けされるフローを、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスに割り当てる工程と、
    （ｃ） 工程（ｂ）においてＣＩＸおよびＤＡ、または、ＣＩＸだけによりクラス分けされた前記フローに割り当てられた前記インデックスで、ｇＭａｘＣｉｘＤａＦｉｘインデックスを設定する工程と、
    （ｄ） 工程（ｂ）においてＣＩＸおよびＤＡ、または、ＣＩＸだけによりクラス分けされた前記フローに割り当てられた前記インデックスの直後に、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスを設定する工程と、
    をさらに含む請求項９に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
11. 順番を含むために、前記最も低いインデックスおよび前記ｇＭａｘＣｉｘＤａＯｎｌｙＦｉｘインデックスの間にある、ＣＩＸおよびＤＡ、または、ＣＩＸだけによりクラス分けされた一つ以上の前記フローを整列する工程と、
    順番を含むために、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスおよび前記パーティションインデックスの間にある、ＤＡだけによりクラス分けされ読み込まれた一つ以上の前記フローを整列する工程と、
    をさらに含む請求項１０に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
12. 前記第１パーティションは、第１部分および第２部分に分割され、
    前記第１部分は、前記最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２部分は、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスまでの範囲で最も低い優先順位を有するインデックスと、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスに隣接して設けられる前記ｇＭａｘＣｉｘＤａＦｉｘインデックスと、前記第２部分内で前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスより上に配置されるフリーエントリと、を含み、
    （ａ） 前記フリーエントリでＣＩＸおよびＤＡ、またはＣＩＸだけによりクラス分けされるフローを、前記ｇＭａｘＣｉｘＤａＦｉｘに移動する工程と、
    （ｂ） 工程（ａ）に続いて、ＤＡだけによってクラス分けされるフローを、前記ｇＭａｘＣｉｘＤａＦｉｘインデックスに割り当てる工程と、
    （ｃ） 工程（ｂ）においてＤＡだけによりクラス分けされた前記フローに割り当てられた前記インデックスで、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスを設定する工程と、
    （ｄ） 工程（ｂ）においてＤＡだけによってクラス分けされたインデックスの直前にｇＭａｘＣｉｘＤａＦｉｘエントリを設定する工程と、
    をさらに含む請求項９に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
13. 順番を含むために、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスの間にある、ＤＡだけによりクラス分けされ読み込まれる一つ以上の前記フローを整列する工程と、
    順番を含むために、前記前記最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスの間にある、ＣＩＸおよびＤＡ、またはＣＩＸだけによりクラス分けされ読み込まれる一つ以上の前記フローを整列する工程と、
    をさらに含む請求項１２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
14. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する工程と、
    ＣＩＸおよびＤＡ、およびＣＩＸだけによりクラス分けされる前記フローを、ＣＩＸプリフィックス・ツリーに、割り当てる工程と、
    をさらに含む請求項７に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
15. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する工程と、
    ＤＡだけによりクラス分けされる前記フローを、ＤＡプリフィックス・ツリーに、割り当てる工程と、
    をさらに含む請求項７に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
16. 前記フローインデックス・スペース内で前記対応するエントリを解放することによって、前記ＴＣＡＭ内でフローを削除し、前記対応するＴＣＡＭエントリを無効にする工程をさらに含む請求項７に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
17. 前記第１パーティションの所定の順番は、最も低い優先順位を有するインデックスで最短のプリフィックスを伴うプリフィックス値を減少することによって次にくる最も高い優先順位を有するインデックスに配置される最長のプリフィックスを伴う前記ＴＣＡＭエントリの一つを有する請求項１に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
18. 前記第２パーティションは、第１部分と第２部分とに分割され、
    前記第１部分は、前記第２パーティションの最も低いインデックスからＧＡＣＬ−パーティションインデックスまでの範囲で、最も高い優先順位を有するインデックスを含み、
    前記第２部分は、前記ＧＡＣＬ−パーティションから前記最も高いインデックスまでの範囲で最も低い優先順位を有するインデックスを含み、
    前記ＡＣＬフローが前記第１部分に割り当てられ、グローバルアクセスリストフローが前記第２部分に割り当てられる請求項３に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
19. 前記ＡＣＬフローは、ソースまたは行き先ポートの範囲を示し、
    前記ＴＣＡＭにおいて、前記ＡＣＬフローを多数のフローにマッピングする工程をさらに有し、
    ここで、前記多数のフローの各フローに対するマスクは、前記ソースまたは行き先ポートの範囲の部分をカバーし、前記範囲の前記部分をカバーするための多くのフローを最適に決定する請求項１８に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
20. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する工程をさらに有する請求項１８に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
21. 前記フローインデックス・スペース内の前記対応するエントリを解放することによって前記ＴＣＡＭ内のフローを削除し、対応する前記ＴＣＡＭエントリを無効にする工程と、
    残っている前記各ＴＣＡＭエントリを一つのインデックスに移動することによって、前記ＴＣＡＭ内の前記フローを小型化する工程と、
    をさらに有する請求項２０に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
22. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する工程をさらに有する請求項１９に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
23. 前記フローインデックス・スペース内の前記対応するエントリを解放することによって前記ＴＣＡＭ内の前記多数のフローを削除し、前記ＴＣＡＭエントリ内の対応するエントリを無効にする工程と、
    残っている前記各ＴＣＡＭエントリを一つ以上のインデックスに移動することによって、前記ＴＣＡＭ内の前記フローを小型化する工程と、
    をさらに有する請求項２２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング方法。
24. ルータ内の複数のデータフローをクラス分けするための方法であって、
    ＴＣＡＭ（ternary content addressable memory）を少なくとも第１のパーティションと第２のパーティションに仕切る工程と、
    所定の順番で、前記第１のパーティションに、前記複数のデータフローの中から最初の一つ以上の第１フローＴＣＡＭエントリを読み込む工程と、
    所定の順番で、前記第２のパーティションに、前記複数のデータフローの中から２番目の一つ以上の第２フローＴＣＡＭエントリを読み込む工程と、
    前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのビットのそれぞれが複数のマスクにより個々にマスクされるように、前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのそれぞれに対して、対応する前記マスクのビット値を設定する工程と、
    前記一つ以上の第１ＴＣＡＭエントリのマッチングが前記一つ以上の第２ＴＣＡＭエントリのいかなるマッチングも包含するように、入力されるパケットの所定のパケットヘッダ情報を含むプリフィックスを、読み込まれた一つ以上の前記第１ＴＣＡＭエントリおよび一つ以上の前記第２ＴＣＡＭエントリと比較する工程と、
    を含み、
    前記第１のパーティションは、最も低いインデックスからパーティションインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２のパーティションは、最も高いインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含み、
    複数の前記第１データフローは、ＭＰＬＳまたはＩＰ−ＶＰＮフローであり、複数の前記第２データフローは、ポリシーベースのルーティングフローであるＴＣＡＭを用いたデータフローの選択的ルーティング方法。
25. ルータ内の複数のデータフローをクラス分けするための方法であって、
    ＴＣＡＭ（ternary content addressable memory）を少なくとも第１のパーティションと第２のパーティションに仕切る工程と、
    所定の順番で、前記第１のパーティションに、前記複数のデータフローの中から第１データフローの一つ以上の第１フローＴＣＡＭエントリを読み込む工程と、
    所定の順番で、前記第２のパーティションに、前記複数のデータフローの中から第２データフローの一つ以上の第２フローＴＣＡＭエントリを読み込む工程と、
    前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのビットのそれぞれが複数のマスクにより個々にマスクされるように、前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのそれぞれに対して、対応する前記マスクのビット値を設定する工程と、
    前記一つ以上の第１ＴＣＡＭエントリのマッチングが前記一つ以上の第２ＴＣＡＭエントリのいかなるマッチングも包含するように、入力されるパケットの所定のパケットヘッダ情報を含むプリフィックスを、読み込まれた一つ以上の前記第１ＴＣＡＭエントリおよび一つ以上の前記第２ＴＣＡＭエントリと比較する工程と、
    前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する工程と、
    一つ以上の前記第１ＴＣＡＭエントリを読み込む工程の前に、フローインデックス・スペースにおける、前記第１ＴＣＡＭエントリの前記所定の順番および前記第２ＴＣＡＭの前記所定の順番を決定する工程と、
    を含み、
    前記第１のパーティションは、最も低いインデックスからパーティションインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２のパーティションは、最も高いインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含むＴＣＡＭを用いたデータフローの選択的ルーティング方法。
26. ルータ内の複数のデータフローをクラス分けするシステムであって、
    ＴＣＡＭ（ternary content addressable memory）を少なくとも第１のパーティションと第２のパーティションに仕切る手段と、
    所定の順番で、前記第１のパーティションに、前記複数のデータフローの中から最初の一つ以上の第１フローＴＣＡＭエントリを読み込む手段と、
    所定の順番で、前記第２のパーティションに、前記複数のデータフローの中から２番目の一つ以上の第２フローＴＣＡＭエントリを読み込む手段と、
    前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのビットのそれぞれが複数のマスクにより個々にマスクされるように、前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのそれぞれに対して、対応する前記マスクのビット値を設定する手段と、
    入力されるパケットの所定のパケットヘッダ情報を含むプリフィックスを、読み込まれた一つ以上の前記第１ＴＣＡＭエントリおよび一つ以上の前記第２ＴＣＡＭエントリと比較する手段と、
    を有し、
    前記第１のパーティションは、最も低いインデックスからパーティションインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２のパーティションは、最も高いインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含み、
    前記一つ以上の第１ＴＣＡＭエントリのマッチングは、前記一つ以上の第２ＴＣＡＭエントリのいかなるマッチングも包含するＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
27. 前記複数の第１データフローは、ＭＰＬＳまたはＩＰ−ＶＰＮフローである請求項２６に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
28. 複数の前記第２データフローは、ポリシーベースのルーティングフローである請求項２６に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
29. 前記ポリシーベースのルーティングフローは、アクセスコントロールリスト（ＡＣＬ）フローである請求項２８に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
30. 前記ポリシーベースのルーティングフローは、トラフィックマネージャフローである請求項２８に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
31. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段と、
    前記フローインデックス・スペースにおける、前記第１ＴＣＡＭエントリの前記所定の順番および前記第２ＴＣＡＭの前記所定の順番を決定する手段と、
    をさらに含む請求項２６に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
32. 前記ＭＰＬＳまたはＩＰ−ＶＰＮフローは、接続インデックス（ＣＩＸ）および行き先アドレス（ＤＡ）、ＣＩＸだけ、またはＤＡだけによってクラス分けされる請求項２６に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
33. 前記第１パーティションは、第１部分および第２部分に分割され、
    前記第１部分は、前記最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２部分は、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含み、
    ＣＩＸおよびＤＡ、並びにＣＩＸだけによってクラス分けされる前記フローは、前記第１部分に割り当てられ、ＤＡだけによりクラス分けされる前記フローは、前記第２部分に割り当てられる請求項３２に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
34. ＣＩＸおよびＤＡによってクラス分けされる前記フロー、およびＣＩＸだけによりクラス分けされる前記フローは、前記ｇＭａｘＣｉｘＤａＦｉｘインデックスから始まる前記第１部分に読み込まれ、前記ＤＡだけによってクラス分けされるフローは、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから始まる前記第２部分に読み込まれる請求項３３に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
35. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持し、前記ＣＩＸおよびＣＩＸのみによりクラス分けされた前記フローをＣＩＸプリフィックス・ツリーに割り当てる手段をさらに有する請求項３２に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
36. 前記第１パーティションは、第１部分および第２部分に分割され、
    前記第１部分は、最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２部分は、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスまでの範囲で最も低い優先順位を有するインデックスと、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスに隣接して設けられる前記ｇＭａｘＣｉｘＤａＦｉｘインデックスと、前記第２部分の前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスより下に配置されるフリーエントリとを含み、
    前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスでＤＡだけによりクラス分けされるフローを、前記フリーエントリに移動する手段と、
    ＣＩＸおよびＤＡ、または、ＣＩＸだけによりクラス分けされるフローを、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスに割り当てる手段と、
    ＣＩＸおよびＤＡ、または、ＣＩＸだけによりクラス分けされた前記フローに割り当てられた前記インデックスで、ｇＭａｘＣｉｘＤａＦｉｘインデックスを設定する手段と、
    ＣＩＸおよびＤＡ、または、ＣＩＸだけによりクラス分けされた前記フローに割り当てられた前記インデックスの直後に、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスを設定する手段と、
    をさらに含む請求項３２に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
37. 順番を含むために前記最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスの間にある、ＣＩＸおよびＤＡ、またはＣＩＸだけによりクラス分けされ読み込まれる一つ以上の前記フローを整列する手段と、
    順番を含むために前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスの間にある、ＤＡだけによりクラス分けされ読み込まれる一つ以上の前記フローを整列する手段と、
    をさらに含む請求項３６に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
38. 前記第１パーティションは、第１部分および第２部分に分割され、
    前記第１部分は、前記最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２部分は、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスまでの範囲で最も低い優先順位を有するインデックスと、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスに隣接して設けられる前記ｇＭａｘＣｉｘＤａＦｉｘインデックスと、前記第２部分の前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスよりも上に配置されるフリーエントリとを含み、
    前記ｇＭｉｎＤａＯｎｌｙＦｉｘでＣＩＸおよびＤＡ、または、ＣＩＸだけによりクラス分けされるフローを、フリーエントリに移動する手段と、
    ＤＡだけによりクラス分けされるフローを、前記ｇＭｉｎＤａＯｎｌｙＦｉｘに割り当てる手段と、
    ＤＡだけによりクラス分けされた前記フローに割り当てられた前記インデックスで、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスを設定する手段と、
    ＤＡだけによりクラス分けされた前記フローに割り当てられた前記インデックスの直後に、ｇＭａｘＣｉｘＤａＦｉｘエントリを設定する手段と、
    をさらに含む請求項３２に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
39. 前記第１パーティションは、第１部分および第２部分に分割され、
    前記第１部分は、前記最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２部分は、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスまでの範囲で最も低い優先順位を有するインデックスと、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスに隣接して設けられる前記ｇＭａｘＣｉｘＤａＦｉｘインデックスと、前記第２部分の前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスよりも上に配置されるフリーエントリとを含み、
    前記ｇＭａｘＣｉｘＤａＦｉｘでＣＩＸおよびＤＡ、またはＣＩＸだけによりクラス分けされたフローを、前記フリーエントリに移動する手段と、
    ＤＡだけによりクラス分けされたフローを、前記ｇＭａｘＣｉｘＤａＦｉｘインデックスに割り当てる手段と、
    前記ＤＡだけによりクラス分けされた前記フローに割り当てられた前記インデックスで、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスを設定する手段と、
    前記ＤＡだけによりクラス分けされた前記フローに割り当てられた前記インデックスの直前にｇＭａｘＣｉｘＤａＦｉｘエントリを設定する手段と、
    をさらに含む請求項３８に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
40. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段と、
    ＤＡだけによりクラス分けされる前記フローを、ＤＡプリフィックス・ツリーに、割り当てる手段と、
    をさらに含む請求項３２に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
41. 前記フローインデックス・スペース内の前記対応するエントリを解放することによって、前記ＴＣＡＭ内のフローを削除し、前記対応するＴＣＡＭエントリを無効にする手段をさらに含む請求項４０に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
42. 前記第１パーティションの所定の順番は、最も低い優先順位を有するインデックスで最短のプリフィックスを伴うプリフィックス値を減少することによって次にくる最も高い優先順位を有するインデックスに配置される最長のプリフィックスを伴う前記ＴＣＡＭエントリの一つを有する請求項２６に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
43. 前記第２パーティションは、第１部分と第２部分とに分割され、
    前記第１部分は、前記第２パーティションにおいて最も低いインデックスからＧＡＣＬ−パーティションインデックスまでの範囲で、最も高い優先順位を有するインデックスを含み、
    前記第２部分は、前記ＧＡＣＬ−パーティションから前記最も高いインデックスまでの範囲で最も低い優先順位を有するインデックスを含み、
    前記ＡＣＬフローが前記第１部分に割り当てられ、グローバルアクセスリストフローが前記第２部分に割り当てられる請求項２８に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
44. 前記ＡＣＬフローは、ソースまたは行き先ポートの範囲を示し、
    前記ＴＣＡＭにおいて、前記ＡＣＬフローを多数のフローにマッピングする手段をさらに有し、
    ここで、前記多数のフローの各フローに対するマスクは、前記ソースまたは行き先ポートの範囲の部分をカバーし、前記範囲の前記部分をカバーするための多くのフローを最適に決定する請求項４３に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
45. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段をさらに有する請求項４３に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
46. 前記フローインデックス・スペース内の前記対応するエントリを解放することによって前記ＴＣＡＭ内のフローを削除し、対応する前記ＴＣＡＭエントリを無効にする手段と、
    残っている前記各ＴＣＡＭエントリを一つ以上のインデックスに移動することによって、前記ＴＣＡＭ内の前記フローを小型化する手段と、
    をさらに有する請求項４５に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
47. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段をさらに有する請求項４４に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
48. 前記フローインデックス・スペース内の前記対応するエントリを解放することによって前記ＴＣＡＭ内の前記多数のフローを削除し、前記ＴＣＡＭエントリ内の対応するエントリを無効にする手段と、
    残っている前記各ＴＣＡＭエントリを一つ以上のインデックスに移動することによって、前記ＴＣＡＭ内の前記フローを小型化する手段と、
    をさらに有する請求項４７に記載のＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
49. ルータ内の複数のデータフローをクラス分けするシステムであって、
    ＴＣＡＭ（ternary content addressable memory）を少なくとも第１のパーティションと第２のパーティションに仕切り、
    所定の順番で、前記第１のパーティションに、前記複数のデータフローの最初の中の一つ以上の第１フローＴＣＡＭエントリを読み込む手段と、
    所定の順番で、前記第２のパーティションに、前記複数のデータフローの２番目の一つ以上の第２フローＴＣＡＭエントリを読み込む手段と、
    前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのビットのそれぞれが複数のマスクにより個々にマスクされるように、前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのそれぞれに対して、対応する前記マスクのビット値を設定する手段と、
    一つ以上の前記ＴＣＡＭエントリのマッチングが、一つ以上の前記ＴＣＡＭエントリのいかなるマッチングも含むように、入力されるパケットの所定のパケットヘッダ情報を含むプリフィックスを、読み込まれた一つ以上の前記第１ＴＣＡＭエントリおよび一つ以上の前記第２ＴＣＡＭエントリと比較する手段と、
    を有し、
    前記第１のパーティションは、最も低いインデックスからパーティションインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２のパーティションは、最も高いインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含み、
    複数の前記第１データフローは、ＭＰＬＳまたはＩＰ−ＶＰＮフローであり、複数の前記第２データフローはポリシーベースのルーティングフローであるＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
50. ルータ内の複数のデータフローをクラス分けするシステムであって、
    ＴＣＡＭ（ternary content addressable memory）を少なくとも第１のパーティションと第２のパーティションに仕切る手段と、
    所定の順番で、前記第１のパーティションに、前記複数のデータフローの最初の一つ以上の第１フローＴＣＡＭエントリを読み込む手段と、
    所定の順番で、前記第２のパーティションに、前記複数のデータフローの２番目の一つ以上の第２フローＴＣＡＭエントリを読み込む手段と、
    前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのビットのそれぞれが複数のマスクにより個々にマスクされるように、前記第１ＴＣＡＭエントリおよび前記第２ＴＣＡＭエントリのそれぞれに対して、対応する前記マスクのビット値を設定する手段と、
    前記一つ以上の第１ＴＣＡＭエントリのマッチングは、前記一つ以上の第２ＴＣＡＭエントリのいかなるマッチングも包含するように、入力されるパケット内の所定のパケットヘッダ情報を含むプリフィックスを、読み込まれた一つ以上の前記第１ＴＣＡＭエントリおよび一つ以上の前記第２ＴＣＡＭエントリと比較する手段と、
    前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段と、
    一つ以上の前記第１ＴＣＡＭエントリを読み込む前に、前記フローインデックス・スペース内において、前記第１ＴＣＡＭエントリの前記所定の順番、および前記第２ＴＣＡＭの前記所定の順番を決定する手段と、
    を有し、
    前記第１のパーティションは、最も低いインデックスからパーティションインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２のパーティションは、最も高いインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含むＴＣＡＭを用いたデータフローの選択的ルーティングシステム。
51. ルーティングシステムにおいて複数のデータフローのクラス分けする装置であって、
    ＴＣＡＭ（ternary content addressable memory）と、
    前記ＴＣＡＭを、少なくとも、最も低いインデックスからパーティションインデックスまでの範囲で最も高い優先順位を有するインデックスを含む第１のパーティションと、最も高いインデックスから前記パーティションインデックスの範囲で最も低い優先順位を有するインデックスを含む第２のパーティションとに区切るパーティションアルゴリズムと、
    前記データフローの最初の一つ以上の第１フローＴＣＡＭエントリと、一つ以上の第２フローＴＣＡＭエントリを組み立てるために、それぞれのマスク値を選択し、前記第２パーティションに、前記それぞれのマスク値をロードするロードアルゴリズムと、
    前記一つ以上の第１ＴＣＡＭエントリのマッチングが前記一つ以上の第２フローＴＣＡＭエントリのマッチングを含むように、所定の順番で前記第１パーティションに入れられる複数のデータフローの最初に読み込まれた前記一つ以上の第１フローＴＣＡＭおよび前記一つ以上の第２フローＴＣＡＭエントリに対して、入力されたパケットの所定のパケットヘッダ情報を含むプリフィックスを結合的に比較するサーチアルゴリズムと、
    を有するＴＣＡＭを用いたデータフローの選択的ルーティング装置。
52. 複数の前記第１データフローは、ＭＰＬＳまたはＩＰ−ＶＰＮフローである請求項５１に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
53. 複数の前記第２データフローは、ポリシーベースのルーティングフローである請求項５１に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
54. 前記パーティションアルゴリズムおよび前記ローディングアルゴリズムは、前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペース内で実行され、前記第１ＴＣＡＭエントリの前記所定の順番および前記第２ＴＣＡＭエントリの所定の順番は、前記フローインデックス・スペース内に示される請求項５１に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
55. 前記ＭＰＬＳまたはＩＰ−ＶＰＮフローは、接続インデックス（ＣＩＸ）および行き先アドレス（ＤＡ）、ＣＩＸだけ、または、ＤＡだけによりクラス分けされる５２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
56. 前記第１のパーティションは、第１部分および第２部分に分割され、
    前記第１部分は、前記最も低いインデックスからｇＭａｘＣｉｘＤａＦｉｘインデックスの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２部分は、ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから前記パーティションインデックスまでの範囲で最も低い優先順位を有するインデックスを含み、
    ＣＩＸおよびＤＡ、および、ＣＩＸだけによりクラス分けされる前記フローは、前記第１部分に割り当てられ、
    ＤＡだけによりクラス分けされる前記フローは、第２部分に割り当てられる請求項５５に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
57. ＣＩＸおよびＤＡによりクラス分けされる前記フロー、およびＣＩＸによりクラス分けされる前記フローは、前記ＴＣＡＭから始まり前記ｇＭａｘＣｉｘＤａＦｉｘインデックスに終わる第１部分にロードされ、
    前記ＤＡだけによりクラス分けされる前記フローは、前記ｇＭｉｎＤａＯｎｌｙＦｉｘインデックスから始まる第２部分にロードされる請求項５６に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
58. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段と、
    ＣＩＸによりクラス分けされた前記フローを、ＣＩＸプリフィックス・ツリーに割り当てる手段と、
    をさらに有する請求項５２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
59. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段と、
    ＤＡだけによりクラス分けされた前記フローをＤＡプリフィックス・ツリーに割り当てる手段と、
    をさらに有する請求項５２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
60. 前記ＴＣＡＭ内のフローを、前記フローインデックス・スペース内の対応する前記エントリを解放することによって削除し、対応する前記ＴＣＡＭエントリを無効にする手段をさらに有する請求項５９に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
61. 前記第１パーティションの所定の順番は、最も低い優先順位を有するインデックスで最短のプリフィックスを伴うプリフィックス値を減少することによって次にくる最も高い優先順位を有するインデックスに配置される最長のプリフィックスを伴う前記ＴＣＡＭエントリの一つを有する請求項５２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
62. 前記第２のパーティションは、第１部分および第２部分に分割され、
    前記第１部分は、前記第２パーティションの最も低いインデックスからＧＡＣＬパーティションインデックスまでの範囲で最も高い優先順位を有するインデックスを含み、
    前記第２部分は、前記ＧＡＣＬパーティションインデックスから前記第２パーティション内の前記最も高いインデックスまでの範囲で最も低い優先順位を有するインデックスを含み、
    前記ＡＣＬフローは、前記第１部分に割り当てられ、グローバルアクセスリストフローは、前記第２部分に割り当てられる請求項５３に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
63. 前記ＡＣＬフローは、ソースまたは行き先ポートの範囲を示し、
    前記ＡＣＬフローを前記ＴＣＡＭ内の多数のフローにマッピングする手段をさらに有し、
    前記多重フローのそれぞれのための前記マスクは、ソースまたは行き先ポートの前記範囲を一部をカバーする請求項６２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
64. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段をさらに有する請求項６２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
65. 前記フローインデックス・スペース内の対応するエントリを解放することによって、前記ＴＣＡＭ内のフローを移動し、対応する前記ＴＣＡＭエントリを無効にする手段と、
    残っている前記ＴＣＡＭエントリを一つのインデックスに移動することによって、前記ＴＣＡＭ内の前記フローを小型化する手段と、
    をさらに有する請求項６４に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
66. 前記ＴＣＡＭに対応するエントリを有するフローインデックス・スペースを維持する手段をさらに有する請求項６２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。
67. 前記フローインデックス・スペース内の対応する前記エントリを解放することによって、前記ＴＣＡＭ内の前記多重フローを移動し、前記ＴＣＡＭエントリ内の対応するエントリを無効にする手段と、
    残っている各前記ＴＣＡＭエントリを一つ以上のインデックスに移動することによって、前記ＴＣＡＭ内の前記フローを小型化する手段と、
    をさらに有する請求項６２に記載のＴＣＡＭを用いたデータフローの選択的ルーティング装置。

Images