(57)【特許請求の範囲】
【請求項１】
ネットワーク装置において、共通の仮想ローカルエリアネットワーク（ＶＬＡＮ）内における異なるエンドユーザに対して異なる仮想ルータを提示する方法であって、当該方法は、
前記共通のＶＬＡＮを識別するＶＬＡＮフィールド及び少なくとも１つの付加的なパケットフィールドを有する入力パケットを受信するステップと、
前記ＶＬＡＮフィールド及び前記少なくとも１つの付加的なパケットフィールドからキーを形成するステップと、
前記キーを、前記入力パケットの１つまたは複数のパケットフィールドに対応して決定されたキータイプを用いてマスクするステップと、
前記マスクされたキーを仮想ルータ識別子（ＶＲＩＤ）にマッピングするステップであって、前記仮想ルータ識別子は、複数の可能な仮想ルータ設定の中から１つの仮想ルータ設定を識別するものである、ステップと、
前記入力パケットを転送するのに使用され、前記仮想ルータ識別子により識別された前記仮想ルータ設定を特徴付けるルーティングテーブルを選択することにより、前記仮想ルータ識別子によって識別された前記１つの仮想ルータ設定を提示するように前記ネットワーク装置を構成するステップと、
前記仮想ルータ識別子により識別された前記仮想ルータ設定を特徴付ける前記選択されたルーティングテーブルを用いて前記入力パケットを転送するステップであって、異なるエンドユーザに対して提示される可能な仮想ルータの数は、前記ネットワーク装置に対するインデックス値の適当な設定を通じて、多くの異なるキー値を同一の仮想ルータ識別子にマッピングすることにより増加する、ステップと、
を有する方法。
【請求項２】
前記キータイプは、前記入力パケットの入口ポートフィールドをルックアップテーブルに入力することにより決定される、請求項１に記載の方法。
【請求項３】
前記キータイプは、前記キーを形成するのに用いられるフィールドの中のどれがワイルドカードであるか、すなわち、その後の処理で無視されるかと、前記キーを形成するのに用いられるフィールドの中のどれが、その後の処理で使用されるかを示すことにより、マスクとして機能する、請求項１に記載の方法。
【請求項４】
前記キーの形成に用いられる前記フィールドのそれぞれは、独立して、ワイルドカード又は非ワイルドカードとなりうる、請求項３に記載の方法。
【請求項５】
前記少なくとも１つの付加的なパケットフィールドは、前記共通のＶＬＡＮを識別する前記ＶＬＡＮフィールドとは異なる仮想メトロポリタンネットワーク（ＶＭＡＮ）フィールドを備える、請求項１に記載の方法。
【請求項６】
前記ＶＬＡＮフィールドおよび前記少なくとも１つの付加的なパケットフィールドから形成される前記キーは、前記ＶＬＡＮフィールドを超える大きさを有し、さらに前記ＶＬＡＮフィールドを仮想ルーティング目的のために使用することを可能にし、
提示されることが可能な仮想ルータの数は、パケットの検索を実行し、パケットの転送決定に達するのに使用されるメモリの大きさに制限され、さらに、提示されることが可能な前記仮想ルータの数は、前記ＶＬＡＮフィールドの大きさには依存しない、請求項１に記載の方法。
【請求項７】
前記ＶＬＡＮフィールドは１２ビットに制限され、最大で４Ｋの異なるルーティングテーブルを識別し、前記ＶＬＡＮフィールドおよび前記少なくとも１つの付加的なパケットフィールドより形成される前記キーが、前記ＶＬＡＮフィールドを超える大きさを備える、請求項６に記載の方法。
【請求項８】
前記ＶＬＡＮフィールドは、拡張又はスーパーＶＬＡＮである、請求項６に記載の方法。
【請求項９】
前記入力パケットを転送するのに使用され、前記仮想ルータ識別子により識別された前記仮想ルータ設定を特徴付けるルーティングテーブルを選択することにより、前記仮想ルータ識別子によって識別された前記１つの仮想ルータ設定を提示するように前記ネットワーク装置を構成するステップは、
各々がコンテンツ値とインデックス値を備える複数のエントリを含むテーブルにアクセスするステップと、
前記マスクされたキーに合致するコンテンツ値を持つエントリを検索するステップと、
関連データ格納要素を用いて、前記合致しているエントリのインデックス値を前記仮想ルータ識別子にマッピングするステップと、
前記テーブルの前記合致しているエントリのインデックス値に一致するインデックス値を有する関連データ格納要素のエントリを選択するステップであって、前記関連データ格納要素からの前記エントリは、前記仮想ルータ識別子である、または前記仮想ルータ識別子を含む、ステップと、を含む、請求項１に記載の方法。
【請求項１０】
共通のＶＬＡＮ内における異なるエンドユーザに対して異なる仮想ルータを提示するために、１以上のコマンド、命令、又は状態遷移を実行することが可能なパケット・プロセッサを有するネットワーク装置であって、１以上のコマンド、命令、又は状態遷移を実行することは、前記ネットワーク装置に対して、さらに、
−前記共通のＶＬＡＮを識別するＶＬＡＮフィールド及び少なくとも１つの付加的なパケットフィールドを有する入力パケットを受信させ、
−前記ＶＬＡＮフィールド及び前記少なくとも１つの付加的なパケットフィールドからキーを形成させ、
−前記ネットワーク装置に、前記入力パケットの１以上のパケットフィールドに応じて決定されるキータイプを用いて前記キーをマスクさせ、
−前記マスクされたキーを、複数の可能な仮想ルータ設定の中から１つの仮想ルータ設定を識別する仮想ルータ識別子（ＶＲＩＤ）にマッピングさせ、
−前記入力パケットを転送するのに使用され、前記仮想ルータ識別子により識別された前記仮想ルータ設定を特徴付けるルーティングテーブルを選択することにより、前記仮想ルータ識別子によって識別された前記１つの仮想ルータ設定を提示するように前記ネットワーク装置を構成させ、
−前記仮想ルータ識別子により識別された前記仮想ルータ設定を特徴付ける前記選択されたルーティングテーブルを用いて前記入力パケットを転送させ、
異なるエンドユーザに対して提示される可能な仮想ルータの数は、前記ネットワーク装置に対するインデックス値の適当な設定を通じて、同一の仮想ルータ識別子に多くの異なるキー値をマッピングすることにより増加する、ネットワーク装置。
【請求項１１】
前記キータイプは、前記キーを形成するのに用いられるフィールドの中のどれがワイルドカードであるか、すなわち、その後の処理で無視されるかと、前記キーを形成するのに用いられるフィールドの中のどれが、その後の処理で使用されるかを示すことにより、マスクとして機能し、前記キーの形成に用いられる前記フィールドのそれぞれは、独立して、ワイルドカード又は非ワイルドカードとなりうる、請求項１０に記載のネットワーク装置。
【請求項１２】
前記少なくとも１つの付加的なパケットフィールドは、前記共通のＶＬＡＮを識別する前記ＶＬＡＮフィールドとは異なるＶＭＡＮフィールドを備える、請求項１０に記載のネットワーク装置。
【請求項１３】
前記ＶＬＡＮフィールドおよび前記少なくとも１つの付加的なパケットフィールドから形成される前記キーは、前記ＶＬＡＮフィールドを超える大きさを有し、さらに前記ＶＬＡＮフィールドを仮想ルーティング目的のために使用することを可能にし、
提示されることが可能な仮想ルータの数は、パケットの検索を実行し、パケットの転送決定に達するのに使用されるメモリの大きさに制限され、さらに、提示されることが可能な前記仮想ルータの数は、前記ＶＬＡＮフィールドの大きさには依存しない、請求項１０に記載のネットワーク装置。
【請求項１４】
前記１以上のコマンド、命令、又は状態遷移を実行することは、前記ネットワーク装置に、
各々がコンテンツ値とインデックス値を備える複数のエントリを含むテーブルにアクセスし、
前記マスクされたキーに合致するコンテンツ値を持つエントリを検索し、
関連データ格納要素を用いて、前記合致しているエントリのインデックス値を前記仮想ルータ識別子にマッピングし、
前記テーブルの前記合致しているエントリのインデックス値に一致するインデックス値を有する関連データ格納要素のエントリを選択するように構成させ、
前記関連データ格納要素からの前記エントリは、前記仮想ルータ識別子である、または前記仮想ルータ識別子を含む、請求項１０に記載のネットワーク装置。
【請求項１５】
前記テーブルは、連想メモリ（ＣＡＭ）に格納されており、
前記マスクされたキーに合致するコンテンツ値を持つエントリを検索することは、前記ＣＡＭを検索して前記ＣＡＭ内の前記エントリを探し出すことを含む、請求項１４に記載のネットワーク装置。
【請求項１６】
１以上のコマンド、命令、又は状態遷移を実行することが可能なパケット・プロセッサを有するネットワーク装置であって、
由来のＶＬＡＮを識別するＶＬＡＮフィールド及び少なくとも１つの付加的なパケットフィールドを有する入力パケットを前記ネットワーク装置において受信する手段と、
前記ＶＬＡＮフィールド及び前記少なくとも１つの付加的なパケットフィールドからキーを形成する手段と、
前記キーを、前記入力パケットの１つまたは複数のパケットフィールドに対応して決定されたキータイプを用いてマスクする手段と、
前記マスクされたキーを仮想ルータ識別子（ＶＲＩＤ）にマッピングする手段であって、前記仮想ルータ識別子は、前記ネットワーク装置内において複数の可能な仮想ルータ設定の中から１つの仮想ルータ設定を識別する手段と、  
前記仮想ルータ識別子により識別された前記１つの仮想ルータ設定を提示するように前記ネットワーク装置を構成する手段と、
前記仮想ルータ識別子により識別された前記１つの仮想ルータ設定を用いて前記入力パケットを転送する手段と、
を備え、
異なるエンドユーザに対して前記ネットワーク装置により提示される可能な仮想ルータの数は、前記ネットワーク装置に対するインデックス値の適当な設定を通じて、同一の仮想ルータ識別子に多くの異なるキー値をマッピングすることにより増加する、ネットワーク装置。
【請求項１７】
前記キータイプは、前記キーを形成するのに用いられるフィールドの中のどれがワイルドカードであるか、すなわち、その後の処理で無視されるかと、前記キーを形成するのに用いられるフィールドの中のどれが、その後の処理で使用されるかを示すことにより、マスクとして機能し、前記キーの形成に用いられる前記フィールドのそれぞれは、独立して、ワイルドカード又は非ワイルドカードとなりうる、請求項１６に記載のネットワーク装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、一般にネットワーク装置に関し、特に、仮想ルータ機能を提供するように、すなわち、異なるエンドユーザ、サービスの種類、又はパケットに対して、異なる仮想ルータ設定を提示する装置を構成する方法に関する。
【背景技術】
【０００２】
仮想ルータ機能は、異なるエンドユーザ、所望のサービスの種類、又はパケットに対して、異なる仮想ルータ設定を提示する同一の物理的ネットワーク装置の能力である。この能力により、同一の物理的装置は、複数の異なる仮想ルータに見える。この能力を実行するため、現在のルータは、直接、関心のあるパケットフィールド、一般的にはＶＬＡＮフィールドを、特定のルーティングテーブルの識別子にマッピングし、その特定のルーティングテーブルを使用してパケットを伝送する。ＶＬＡＮフィールドは仮想ＬＡＮ、及びＯＳＩ第２層（OSI Layer two）のルーティング／スイッチング目的のための同一ＬＡＮの一部と考えられるように、物理的に異なるが論理的に関連するネットワーク要素の集まりを指定する。例えば、特定のＶＬＡＮ内の全てのネットワーク要素は、ＯＳＩ第２層で、ＶＬＡＮ内の他の要素からのブロードキャストを受信する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
入力パケットのＶＬＡＮが直接ルーティングテーブルの識別子にマッピングされるこのアプローチは、異なるエンドユーザがオーバーラップしていないＶＬＡＮを用いている限りは、うまく動作する。そのため、ＶＬＡＮを用いて、異なる仮想ルータを異なるエンドユーザに提示することができた。しかし、ＶＬＡＮの使用が激増するにつれ、異なるエンドユーザはＶＬＡＮのオーバーラップしている設定を使用し始めるため、ＶＬＡＮを用いて異なる仮想ルータを異なるエンドユーザに提示することがもはやできなくなった。
【０００４】
他の問題として、実行できる仮想ルータの数がＶＬＡＮフィールドの大きさにより制限されることがある。例えば、１２ビットのＶＬＡＮは、４Ｋの異なるルーティングテーブルしか識別せず、あるアプリケーションにとっては十分でない。
【０００５】
第３の問題は、このアプローチは柔軟性に欠けているということである。例えば、ネットワークの利用が進化し又はネットワークの規格が変化して、ＶＬＡＮの種類又はフォーマットが変化した場合、このアプローチは特定のＶＬＡＮの種類及びフォーマットに結びつけられているため、陳腐化した状態となる。
【０００６】
第４の問題は、適応する必要がある仮想ルータの数が増加するにつれて、このアプローチは拡張性に欠けるということである。例えば、このアプローチでは、仮想ルータを増加させるためにＶＬＡＮフィールドの大きさを増加させると、維持する必要があるルーティングテーブルの数が正比例して増える。
【０００７】
本発明は、異なるエンドユーザ、サービスの種類、又はパケットに対して、異なる仮想ルータを提示する方法を提供する。その方法は、どのネットワーク装置で実行されてもよく、装置が仮想ルータ機能を実現することを可能にする。
【課題を解決するための手段】
【０００８】
方法は、ＶＬＡＮフィールドと少なくとも１つの付加的なフィールドを有するパケットが受信されるときに開始する。パケットが受信されるとき、ＶＬＡＮフィールドと、少なくとも１つの付加的なパケットフィールド、例えばＶＭＡＮフィールドとから、キーが形成される。
【０００９】
それから、キーは、間接マッピングプロセスを用いて、仮想ルータ識別子（ＶＲＩＤ）にマッピングされる。この間接マッピングプロセスによれば、各々がコンテンツ値とインデックス値を備える複数のエントリを含むテーブルがアクセスされ、キーに合致するコンテンツ値を持つエントリが探し出される。それから、合致するエントリのインデックス値が、関連データ格納要素を用いて、ＶＲＩＤにマッピングされる。その結果が、特定の仮想ルータ設定を複数の可能な仮想ルータ設定から識別する仮想ルータ識別子である。
【００１０】
本発明の他のシステム、方法、特徴、及び利点が、下記の図面及び詳細な説明を考察することにより、当業者には明らかである又は明らかとなる。全てのこのような追加のシステム、方法、特徴、及び利点は、この明細書に含まれ、本発明の範囲内であり、添付の特許請求の範囲により保護される。
【図面の簡単な説明】
【００１１】
【図１】間接マッピングプロセスが１以上のパケットフィールドから生成されたキーをＶＲＩＤにマッピングするのに使用されることを特徴とする一実施形態における、仮想ルータ識別子（ＶＲＩＤ）を生成するのに使用される、方法のステップ、データ構造、及び論理素子を示すブロック図
【図２ａ】キーのフォーマットの例を示す図
【図２ｂ】キーのフォーマットを構成するフィールドのうち、種々のフィールドをワイルドカードにするキータイプの様々な例を示す図
【図２ｃ】キーのフォーマットを構成するフィールドのうち、種々のフィールドをワイルドカードにするキータイプの様々な例を示す図
【図２ｄ】キーのフォーマットを構成するフィールドのうち、種々のフィールドをワイルドカードにするキータイプの様々な例を示す図
【図２ｅ】キーのフォーマットを構成するフィールドのうち、種々のフィールドをワイルドカードにするキータイプの様々な例を示す図
【図３】ネットワーク装置がＶＲＩＤに応じて構成され、構成された装置に従ってパケットが送信されることを特徴とする一実施形態の方法のステップを示すフローチャート
【図４】特許請求の範囲に記載の方法及びシステムを具体化又は利用する特定のスイッチ構造を示す図
【図５】仮想ルータ機能をサポートするのに用いられる複数のルーティングテーブルを示す図
【図６ａ】入ってくるパケット内で検出されるＶＬＡＮフィールドのタイプに従って適用される、代替のデータタイプの例を示す図
【図６ｂ】入ってくるパケット内で検出されるＶＬＡＮフィールドのタイプに従って適用される、代替のデータタイプの例を示す図
【図６ｃ】入ってくるパケット内で検出されるＶＬＡＮフィールドのタイプに従って適用される、代替のデータタイプの例を示す図
【発明を実施するための形態】
【００１２】
本発明は、以下の図面を参照することにより、よりよく理解されうる。図面の構成要素は、必ずしも縮尺、強調したものではなく、本発明の原理を図示するときに配置されたものである。さらに、図において、同一の参照符号は、異なる図において対応する部分を示している。
【００１３】
図１を参照すると、ブロック図に、ネットワーク装置において実行され、異なるエンドユーザ、サービスの種類、又はパケットに対して、異なる仮想ルータを提示する方法１００のステップが示されている。また、本方法の実行に使用されるデータ構造と、本方法のステップを実行する論理要素が、図示されている。この特定の実施形態において、本方法は、パケットがパケットパーサ１０４により解析された後、装置内で実行される。これにより、ＶＬＡＮ１０６、ＶＭＡＮ１０８、及び入口ポート１１０を含む、パーサ１０４による解析が成功した特定パケットフィールドが、本方法により利用可能となる。本方法は、必ずしも限定されないが、ルータ、スイッチ、又はルータとスイッチの組み合わせを含む、ＯＳＩ第３層（OSI layer three）又はそれ以上でパケットを転送又は分類することが可能ないずれのネットワーク装置でも実行されうる。この明細書では、「仮想ルータ」は、「軽量級（lightweight）」仮想ルータ、すなわち、ＯＳＩ第３層で事実上転送するルータと、「重量級（heavyweight）」仮想ルータ、すなわち、ＯＳＩ第３層で事実上転送するルータの両方を含み、さらに、仮想ルータ当たり、別個のＯＳＩ第２層の機能を実行する。さらに、この明細書では、単数形の用語「装置（device）」又は「ルータ（router）」は、複数の装置又はルータをそれぞれ含む。
【００１４】
先に説明したように、ＶＬＡＮフィールド１０６は、仮想ＬＡＮ、及びＯＳＩ第２層のルーティング／スイッチング目的のための同一ＬＡＮの一部と考えられるように、物理的に異なるが論理的に関連するネットワーク要素の集まりを指定する。現在、ＶＬＡＮの用語は、ＶＭＡＮ（下記参照）内で、論理的に関連するエンドユーザの装置を一意的に識別するために主に使用される。
【００１５】
ＶＭＡＮフィールド１０８は、仮想メトロポリタンネットワークを示し、同一のネットワークの一部と考えられるように、物理的に異なるが論理的に関連するネットワーク要素の集まりを指定する。用語は、本来は、メトロポリタンネットワークのみに適用されるけれども、現在では、メトロポリタンやメトロポリタンでない、いずれのネットワークをも示すのに用いられるように、その用法は発展している。実際、ＶＭＡＮの使われ方は増加しており、用語は、現在、サービスプロバイダにより主に使用され、論理的に関連する基盤装置を示している。同時に、ＶＬＡＮの用語は、上述したように、現在、主に、ＶＭＡＮ内で論理的に関連するエンドユーザの装置を一意的に識別するのに用いられる。有意に、ＶＬＡＮ値は、ＶＭＡＮ内でＶＬＡＮを一意的に識別し、同一のＶＬＡＮ値がＶＭＡＮ内で異なるエンドユーザの装置を参照するのに使用されることはない。
【００１６】
入口ポートの番号１１０は、装置でパケットが受信された物理的なポートの識別子である。
【００１７】
図１に戻り、本方法の目的は、入力パケットに対応して、仮想ルータ識別子（ＶＲＩＤ）１０２を決定することである。仮想ルータ識別子１０２は、複数の可能な仮想ルータ設定から特定の仮想ルータ設定を識別する。
【００１８】
本方法は、キー生成ロジック１１２が、ＶＬＡＮ１０６、ＶＭＡＮ１０８、及び入口ポート１１０のフィールドからキーを形成するときに、開始する。図示された特定の実施形態では、キーは、これらの３つのフィールドを共に連結することにより、形成される。しかし、当然のことながら、キーを形成する他の方法が可能である。よって、例えば、一実施形態では、入口ポート「Ｘ」を介して受信され、「Ｙ」のＶＬＡＮと「Ｚ」のＶＭＡＮを持つ入力パケットは、図２ａで示されるように、３つの連結されたフィールド、すなわち、入口ポート「Ｘ」を保持する第１のフィールド２０２、ＶＬＡＮ「Ｙ」を保持する第２のフィールド２０４、及びＶＭＡＮ「Ｚ」を保持する第３のフィールド２０６でフォーマットされたキー２００を有する。
【００１９】
同時に、一実施形態では、入口ポート１１０は、キータイプ１１６を決定するルックアップテーブル１１４に入力される。この実施形態では、キータイプは、キーの３つのフィールドの中のどれがワイルドカードであるか、すなわち、その後の処理で無視されるかと、どれが使用されるかを示すことにより、マスクとして機能する。この特定の実施形態では、３つのフィールドのそれぞれが、独立して、ワイルドカード又は非ワイルドカードとなりうる。例えば、図２ｂは、入口ポートフィールド及びＶＭＡＮフィールドがワイルドカードであり（対応するフィールドに現れる×により示されている。）、ＶＬＡＮフィールドのみが次の処理で使用されるという、キータイプを示している。同様に、図２ｃは、入口ポートフィールドがワイルドカードであり、ＶＬＡＮフィールド及びＶＭＡＮフィールドが次の処理で使用されるという、キータイプを示している。図２ｄは、ＶＬＡＮフィールドがワイルドカードであり、入口ポートフィールド及びＶＭＡＮフィールドが次の処理で使用されるキーを示している。図２ｅは、ＶＭＡＮフィールドがワイルドカードであり、入口ポートフィールド及びＶＬＡＮフィールドが次の処理で使用されるキーを示している。
【００２０】
図１に示す実施形態では、キータイプ１１６は、ルックアップテーブル１１４への入力を形成する入口ポートフィールド１１０に応じて決定される。テーブル１１４は複数のエントリを含む。各エントリは、例えば、図２ｂ〜図２ｅに示されるような、特定のキータイプを指定するインデックス値とコンテンツ値を備える。ルックアップは、入口ポートフィールド１１０を特定のインデックスにマッピングし、そのインデックスを持つエントリを探し、キータイプをそのエントリのコンテンツ値に設定することにより、発生する。他の実施形態では、キータイプは、他のパケットフィールドと１以上のパケットフィールドとに応じて、決定されてもよい。
【００２１】
図６ａは、キータイプがキーに付加される３ビットフィールド（符号６０２で識別される。）である場合の実施を示している。図６ａは、キーのフォーマットと、キーのどのフィールドがワイルドカードであるかの両方を示している。例えば、キー６０４のキータイプは、キーが９ビットであることと、ＶＬＡＮフィールド及びＶＭＡＮフィールドがワイルドカードであることを示し、キー６０６のキータイプは、キーが１５ビットであることと、入口ポートフィールド及びＶＭＡＮフィールドがワイルドカードであることを示し、キー６０８のキータイプは、キーが１５ビットであることと、入口ポートフィールド及びＶＬＡＮフィールドがワイルドカードであることを示し、キー６１０のキータイプは、キーが２１ビットであることと、ＶＭＡＮフィールドがワイルドカードであることを示し、キー６１２のキータイプは、キーが２７ビットであることと、入口ポートフィールドがワイルドカードであることを示し、キー６１４のキータイプは、キーが３３ビットであることと、ワイルドカードのフィールドがないことを示している。
【００２２】
さらに、以下により詳細に説明するように、三値連想メモリ（Ternary ＣＡＭ）が間接マッピングプロセスを実行するのに用いられる場合、キーは間接的に仮想ルータ識別子にマッピングされる。三値連想メモリエントリに対応するコンテンツ値の個々のフィールドはワイルドカードでありうる、すなわち、値を気にしないように設定されているため、説明したキータイプの生成とキーのマスキングのプロセスは不要である。二値連想メモリ（Binary ＣＡＭ）が間接マッピングプロセスを実行するのに使用される場合は、説明したキータイプの生成とキーのマスキングのプロセスは、一般的に保持されるべきである。
【００２３】
再度、図１を参照すると、場合によってはマスクされ又はマスクされていないキー１１８は、ロジック１２６により実行される２段階間接マッピングプロセスを用いて、仮想ルータ識別子１０２にマッピングされる。第１の段階では、図示されるように、テーブル１２０がアクセスされる。テーブルは、複数のエントリ１２０ａ、１２０ｂ、１２０ｃを有する。各エントリは、コンテンツ値とインデックス値を含む。キーに合致するコンテンツ値を有するエントリが探し出される。図１において、エントリ１２０ｂのコンテンツ値が、キー１１８に合致するように示されている。符号１２２で特定される、合致するエントリのインデックス値は、プロセスの第２の段階への入力を形成する。
【００２４】
第２の段階では、合致するエントリ１２０ｂのインデックス値１２２は、関連データ格納要素１２４を用いて、仮想ルータ識別子１０２にマッピングされる。関連データ格納要素１２４は複数のエントリ１２４ａ、１２４ｂを含み、各エントリはインデックス値とコンテンツ値を有する。一実施形態において、マッピングは、テーブル１２０内の合致するエントリのインデックス値１２２と合致するインデックス値を持つ関連データ格納要素１２４内のエントリを選択することにより、実行される。図１に示される特定の例では、エントリ１２４ｂがこの条件を満たす。このエントリのコンテンツ値は、仮想ルータ識別子１０２である、又は仮想ルータ識別子１０２を含む。
【００２５】
一実行において、テーブル１２０はＣＡＭ上に格納される。二段階プロセスの第１の段階は、キー１１８に合致するコンテンツ値を持つエントリ１２０ｂをＣＡＭに検索させることにより、発生する。ＣＡＭが二値連想メモリ、すなわち、エントリのコンテンツ値の各ビットが二値の「０」及び「１」のみを取るＣＡＭである場合、先に述べたキータイプの生成とマスキングのプロセスは、これらの機能がＣＡＭにより利用できないため、一般的に実行されるべきである。しかし、ＣＡＭが三値連想メモリ、すなわち、エントリのコンテンツ値の各ビットが二値の「０」及び「１」と「無関心（don't care）」値とを取るＣＡＭの場合、先に述べたキータイプの生成とマスキングのプロセスは、これらの機能がＣＡＭエントリのコンテンツ値の適当な設定により、実行されうるため、任意である。
【００２６】
第２の実行において、テーブル１２０はＲＡＭに格納される。二段階プロセスの第１の段階は、ハッシュ関数をキー１１８に適用し、開始エントリのテーブルインデックスを決定し、それからテーブル１２０の検索を開始エントリから始めて、キー１１８に合致するコンテンツ値を持つエントリ１２０ｂを探し出すことにより、発生する。
【００２７】
ロジック１２８は、ＶＲＩＤ１０２に従って装置を構成する。その後、構成された装置がパケットを転送する。一実施形態において、より詳細を後述するように、ロジック１２８は、ＶＲＩＤ１０２に応じてＣＡＭ検索キーを選択又は生成する。ＣＡＭ検索キーは、パケットの分類と転送決定を行うために使用される。ＶＲＩＤ１０２に応じた分類及び転送の処理中に使用されるキーを設定することにより、ロジック１２８は、パケットを発送するのに使用されるルーティングテーブルを事実上選択する。
【００２８】
上述の実施形態は、仮想ルータ機能を提供する従来のアプローチで最初に特定される問題を克服する。第１に、キーがＶＬＡＮ及びＶＭＡＮフィールドの組み合わせから形成され、且つＶＬＡＮが特定のＶＭＡＮ内で唯一の識別子であるため、実施形態によれば、ＶＬＡＮを仮想ルーティング目的のために再度使用することが可能となる。
【００２９】
第２に、本実施形態は可能な仮想ルータの数を著しく増加させる。例えば、テーブル１２０がＣＡＭ上に格納されている場合、提示されうる仮想ルータの数は、ＣＡＭの大きさによりのみ制限される。ＶＬＡＮフィールドの大きさは支持されるというよりも、もはや仮想ルータの数を制限しなくなる。
【００３０】
第３に、本実施形態は順応性があり、ネットワークの利用法又は規格の変化に容易に適応する。例えば、スーパーワイド（super-wide）（２４ビット）ＶＬＡＮフィールド、すなわち、ＥＳＩＤフィールドが、最近、許容されるイーサタイプ（Ethertypes）のリストに追加されたことを考える。これは、ルックアップテーブル１１４内で新しいキータイプを定義することにより、簡単に取り扱われる。例えば、標準のデータタイプが、図６ｂに示すフォーマット、すなわち、ＶＬＡＮフィールドとＶＭＡＮフィールドのそれぞれに１２ビットと入口ポートフィールドに６ビットを持つ場合、スーパーワイドＶＬＡＮ（ＥＳＩＤ）が検出されたとき、データタイプ１１６は、図６ｃに示されるフォーマット、すなわち、６ビットの入口ポートフィールドの後に２４ビットのＥＳＩＤフィールドが続くフォーマットを有することができる。図６ｃのキータイプに遭遇したとき、図１のロジック１１２は、パケットパーサ（packet parser）からのフィールド１０６、１０８、及び１１０に応じてこの図に示されるようにキーをフォーマットする、すなわち、ＶＬＡＮフィールド１０６を２４ビットのＥＳＩＤフィールドと想定する。
【００３１】
第４に、本実施形態は拡張性があり、可能な仮想ルータの数が増加しても、保持されるルーティングテーブルの数の比例した増加を必ずしも必要としない。代わりに、多くの異なるキー値が、テーブル１２０のエントリ１２０ａ、１２０ｂ、１２０ｃに関連付けられたインデックス値の適当な設定により、同一のＶＲＩＤにマッピングされる。例えば、図１において、エントリ１２０ｂ及び１２０ｃのインデックス値が同一のＶＲＩＤにマッピングすることが望まれた場合、エントリ１２０ｂ及び１２０ｃのインデックス値は、同一の値に設定される。
【００３２】
図３は、全方法の一実施形態において実行されるステップを要約している。ステップ３０２は、図１のロジック１１２により実行されるキー生成ステップを含む。ステップ３０４は、ルックアップテーブル１１２にアクセスすることにより決定されるキータイプを用いた、図１のロジック１１２により実行される任意のキータイプの生成とマスキングのプロセスを含む。この明細書において、用語「ロジック」は、ハードウェア、ソフトウェア、又はハードウェアとソフトウェアの組み合わせにおける実施を言う。
【００３３】
ステップ３０６は、二段階間接マッピングプロセスを含む。第１の段階は、ＣＡＭ上に格納されている又は格納されていないテーブル１２０により検索し、又は検索を実行し、キー１１８に合致するコンテンツ値を持つエントリ１２０ｂを見つけ出すことを含む。第２の段階は、テーブル１２０内の合致するエントリのインデックス値１２２と合致するインデックス値を持つ、関連データ格納１２４内、典型的にはＲＡＭ内のエントリ１２４ｂを探すことを含む。ステップ３０８は、仮想ルータ識別子（ＶＲＩＤ）１０２を出力することを含む。図１において、このステップは、テーブル１２０の合致するエントリのインデックス値１２２に合致するインデックス値を持つエントリ１２４ｂのコンテンツ値又はコンテンツ値の指定されたフィールドを出力することを含む。
【００３４】
ステップ３０６とステップ３０８は、ロジック１２６（図１に示される。）がテーブル１２０と関連データ要素１２４とに、これらの要素間の点線の矢印で示されるように、適切にアクセスすることにより、実行される。
【００３５】
ステップ３１０は、仮想ルータ識別子により識別される特定の設定を有するように装置を構成することを含む。一実施形態において、このステップは、ロジック１２８（図１に示される。）により、パケットの分類及び転送決定を行うのに用いられるＣＡＭ検索キーを選択又は生成するときに、実行される。分類及び転送のプロセスで使用されるキーを設定することにより、ロジック１２８は、パケットを転送するのに使用するため、複数のルーティングテーブルからルーティングテーブルを一つ実質的に選択する。概念的に、そのプロセスは図５に示されている。図５は、ＶＲＩＤに応じて、複数の可能なルーティングテーブル５０２、５０４、５０６から一つのルーティングテーブル、例えばテーブル５０４を選択し、選択されたルーティングテーブルを用いて、関心のあるパケットを転送する準備をすることを示している。
【００３６】
図３に戻ると、ステップ３１２は、構成された装置に従ってパケットを転送することを含む。一実施形態において、このステップは、装置内のパケットプロセッサにより実行される。この明細書で、用語「プロセッサ」は、１以上のコマンド、命令、又は状態遷移を実行することが可能な装置のことを言い、限定されないが、汎用又は専用のマイクロプロセッサ、有限状態機械、コントローラ、コンピュータ、及びデジタルシグナルプロセッサ（ＤＳＰ）などを含む。
【００３７】
図４は、上述した方法が作動する特定のルータ構成の実施形態４００を示す。図示されるように、この実施形態では、ルータは、パケット分類／転送システム４０２とパケット変更システム４０４とを含む、パケット処理システムとして構築されている。パケット分類／転送システム４０２は、入口部４０６と出口部４０８とを備えている。入ってくる（ネットワーク側）パケットは、入口部４０６及び出口部４０８を通って、パケット分類／転送システム４０２に出入りする。同様に、パケット変更システム４０４は、入口部４１０と出口部４１２とを備えている。出て行く（スイッチ側）パケットは、入口部４１０及び出口部４１２を通って、パケット変更システム４０４に出入りする。
【００３８】
パケット分類／転送システム４０２の入口部４０６は、インターフェース４１８により、１以上のネットワーク側装置４１４に接続されており、パケット分類／転送システム４０２の出口部４０８は、インターフェース４２０により、１以上のスイッチ側装置４１６に接続されている。同様に、パケット変更システム４０４の入口部４１０は、インターフェース４２２により、１以上のスイッチ側装置４１６に接続されており、パケット変更システム４０４の出口部４１２は、インターフェース４２３により、１以上のネットワーク側装置４１４に接続されている。
【００３９】
パケット分類システム４０２は、入口部４０６及び出口部４０８に加え、第１のパケットパーサ１０４（図１に示されている同一のパケットパーサ１０４）とパケットプロセッサ４２８をさらに有する。
【００４０】
パーサ１０４は、入ってくるパケットを解析し、パケット層の先頭へのコンテキストポインタ（context pointers）、例えば、ＯＳＩ第２，３，及び４層の先頭へのポインタを提供するように、構成される。
【００４１】
パケットプロセッサ４２８は、パーサ１０４により提供されるコンテキストポインタに応じて、パケットを分類し転送するように構成される。
【００４２】
連想メモリ（Content Addressable Memory（ＣＡＭ））４４２は、パケット分類／転送システム４０２により、パケットの検索を実行し、パケットの分類／転送決定に達するのに、使用される。ＣＡＭ４４２は、三値、二値、又は二値と三値の組み合わせであってもよい。
【００４３】
関連ＲＡＭ（associated ＲＡＭ（ＡＲＡＭ））４４４ａ、４４ｂは、ＣＡＭ４４２内の各エントリについての関連データを提供する。ＡＲＡＭ４４４ａ、４４４ｂは、検索動作の結果、ＣＡＭ４４２により返されるアドレス（インデックス値）を用いてアクセスされる。ＡＲＡＭ４４４ａ、４４４ｂのエントリデータは、パケットの最後の分類／転送決定を行うのに、パケットプロセッサ４２８により使用されるパケットの中間の分類／転送情報を供給するために使用される。
【００４４】
ＣＡＭ上に格納されている又は格納されていないテーブル１２０と、まとめてＶＲＩＭ（Virtual Router Indirection Mapper）と呼ばれる関連データ格納１２４は、図１に関して先に説明した、同じ構成要素である。
【００４５】
パケット変更システム４０４は、入口部４１０及び出口部４１２に加えて、出て行くパケットを解析する第２のパケットパーサ４３０、変更プロセッサ４３２、フラグメントプロセッサ４３６、第３のパケットパーサ４３６、ＡＣＬ（Access Control Logic）４３８ａ、及びＬ３／Ｌ４チェックサムロジック４３８ｂをさらに有する。
【００４６】
パーサ４３０は、出て行くパケットを解析し、パケット層の先頭へのコンテキストポインタ、例えば、ＯＳＩ第２，３，及び４層の先頭へのポインタを提供するように、構成されている。
【００４７】
変更プロセッサ４３２は、パケットを断片に分解する処理において、パーサ４３０により提供されるコンテキストポインタに応じて、出て行くパケットのいくつか又は全てを変更する。フラグメントプロセッサ４３６は、断片化されたパケットを再度組み立てる。
【００４８】
変更ＲＡＭ（modification ＲＡＭ（ＭＲＡＭ））４４８ａ、４４８ｂは、変更プロセッサ４３２ａ、４３２ｂにより実行されるパケット変更動作のためのデータと制御構造を提供する。
【００４９】
パーサ４３６は、再度組み立てられたパケットを解析し、パケット層の先頭へのコンテキストポインタ、例えば、ＯＳＩ第２，３，及び４層の先頭へのポインタを提供するように構成されている。
【００５０】
ＡＣＬロジック４３８ｂは、パーサ４３６により提供される解析されたパケット層に応答して、ＣＰＵコピー、ミラーコピー、及び消す（kill）などの、パケットに関するＡＣＬ決定に達する。ＣＰＵコピーの動作では、システムに接続されたホスト４３８にパケットのコピーを転送する。ミラーコピーの動作では、出口ミラーリング機能を実行する。出口ミラーリング機能では、パケットのコピーがミラーＦＩＦＯ４４０に転送され、それからパケット分類／転送システム４０２の出口部４０８に転送される。消す動作では、パケットを消すか、又はダウンストリームＭＡＣ（Medium Access Control）プロセッサにより消すための印をパケットに付ける。
【００５１】
Ｌ３／Ｌ４チェックサムロジック４３８ｂは、変更されたパケットについてチェックサムを計算するように構成されている。一実施形態において、ロジック４３８ｂは、第３層（ＩＰ層）及び第４層（ＴＣＰ／ＵＤＰ層）チェックサムを独立して計算するように構成される。
【００５２】
一実行において、インターフェース４１８、４２０、４２２、４２４と、１以上の（特定されないが）ＣＡＭ、ＶＲＩＭ、ＡＲＡＭ、又はＭＲＡＭインターフェースは、２００３年９月４日に提出の米国特許出願第１０／６５５，７４２号（参照することにより、全て説明するかのようにここに完全に組み込まれる。）に記載されているＱＤＲ又はＤＤＲタイプのインターフェースであってもよい。
【００５３】
一実施形態において、図１に示す論理要素は、図４のルータに、転送分類システム４０２内のパケットパーサ１０４のすぐ下流で且つパケットプロセッサ４２８と並列に組み込まれる。この実施形態において、図１のロジック１１２は、パーサ１０４により提供される解析されたパケットデータに応じて、図３のキー生成ステップ３０２を実行する。また、ロジック１１２は、三値連想メモリがＶＲＩＭ１２０、１２４に含まれず、間接マッピングプロセス３０６の一部として使用されない場合、任意のキータイプの生成とマスキングのステップ３０４を実行する。三値連想メモリがＶＲＩＭ１２０、１２４に含まれ、間接マッピングプロセス３０６の一部として使用される場合は、キータイプの生成とマスキングのステップ３０４はこのＣＡＭにより実行されてもよい。ロジック１２６は、ＶＲＩＭ１２０、１２４の要素と連結して、間接マッピングプロセス３０６と、ＶＲＩＤ出力ステップ３０８とをさらに実行する。
【００５４】
パケットプロセッサ４２８は、ＣＡＭ４４２への開始キーとして、ＶＲＩＤを用いることにより、図３の構成装置ステップ３１０を実行する。パケットプロセッサ４２８は、パケットプロセッサ３０６により実行される一連のコマンドの開始アドレスを決定し、入ってくるパケットの分類及び転送決定を行う。ＣＡＭ４４２への開始キーとしてＶＲＩＤを用いることにより、パケットプロセッサ４２８は、図５に示される複数の可能なルーティングテーブルから一つのルーティングテーブルを暗黙的に選択する。
【００５５】
また、パケットプロセッサ４２８は、少なくとも最初に、ＶＲＩＤ１０２に応じて決定されたキーで実行されるＣＡＭ検索プロセスに対応して、入ってくるパケットを分類及び転送することにより、ステップ３１２を実行する。
【００５６】
本発明の様々な実施形態が説明されたけれども、当業者によれば、本発明の範囲内にあるさらに多くの実施形態と実行が可能であることは明らかである。よって、本発明は、添付の特許請求の範囲及びそれと同等のものに照らすことを除いて、限定されない。
【図１】
0005567641.tif 000002
【図２ａ】
0005567641.tif 000003
【図２ｂ】
0005567641.tif 000004
【図２ｃ】
0005567641.tif 000005
【図２ｄ】
0005567641.tif 000006
【図２ｅ】
0005567641.tif 000007
【図３】
0005567641.tif 000008
【図４】
0005567641.tif 000009
【図５】
0005567641.tif 000010
【図６ａ】
0005567641.tif 000011
【図６ｂ】
0005567641.tif 000012
【図６ｃ】
0005567641.tif 000013