(57)【要約】入来するデータパケットをブロッキングすることなく、イーサネット（Ｒ）（ＩＥＥＥ８０２．３）ネットワークにおいてレイヤ２およびレイヤ３スイッチングを行なうよう構成されるネットワークスイッチは、フィルタ（すなわち、パケット分類子モジュール）を有するネットワークスイッチポートを含む。フィルタは、入来するデータパケットを、ネットワークスイッチポートで受信するとすぐに、瞬時に評価するよう構成される。フィルタは、データパケットの入来するデータストリームと、それぞれのデータプロトコルを識別するよう構成される多数のテンプレートとの間で同時の比較を行なう。各テンプレートは、複数の最小項からなり、各最小項は入来するデータパケットの選択データバイト内で予め規定された比較動作を指定する。テンプレートはユーザによってプログラム可能であり、内部の最小項メモリに記憶され得る。さらに、多数の同時比較により、ネットワークスイッチはネットワークスイッチ内でブロッキングすることなく、１００Ｍｂｐｓおよびギガビットネットワークに対してレイヤ３スイッチングを行なえるようになる。
2004507158.tif 000002
【特許請求の範囲】
【請求項１】
入来するデータパケットをネットワークスイッチポートで評価する方法であって、
それぞれのデータ形式を識別するよう構成される複数のテンプレートを記憶するステップを含み、各テンプレートは対応の予め規定された値と、入来するデータパケットの対応の選択バイトとを比較するよう構成される、少なくとも１つの最小項を有し、さらに
選択バイトがネットワークスイッチポートで受けられると瞬時に、選択バイトと選択バイトに対応する最小項とを同時に比較するステップと、
最小項と、ネットワークスイッチポートにより受けられたパケット全体のデータバイトとの比較に基づいて、入来するデータパケットを識別する比較結果を生成するステップと、
ネットワークスイッチポートでデータパケットの最後のビットが受けられるとすぐに、比較結果に基づいたフレームタグを生成するステップとを含む、方法。
【請求項２】
同時に比較するステップは、
第１のデータバイトに対応する最小項を最小項生成器にローディングするステップと、
最小項生成器にローディングされた最小項と第１のデータバイトとを並行に比較するステップと、
最小項生成器にローディングされた最小項に対する比較結果を評価コアに出力するステップとを含む、請求項１に記載の方法。
【請求項３】
同時に比較するステップは、第１のデータバイトに連続する第２のデータバイトに対応する最小項を最小項生成器にローディングするステップをさらに含む、請求項２に記載の方法。
【請求項４】
対応のフレームタグに基づいて入来するデータパケットを選択的にスイッチングするよう構成されるスイッチファブリックにフレームタグを出力するステップをさらに含む、請求項１に記載の方法。
【請求項５】
記憶するステップは、各最小項をテーブルエントリとしてメモリに記憶するステップを含み、各テーブルエントリは、入来するデータパケット内の対応の選択バイトの位置に基づくメモリ内の位置を有し、テーブルエントリは対応の予め規定された値および比較オペランドを指定する最小項表現部分と、対応の最小項を用いるテンプレートを指定するテンプレート識別子フィールドとを含む、請求項１に記載の方法。
【請求項６】
生成するステップは、
最小項と入来するデータパケットの選択バイトとの比較結果を一時的に記憶するステップと、
最小項の比較の結果に基づいて、複数のテンプレートから少なくとも１つのマッチングするテンプレートを検出するステップと、
検出された少なくとも１つのマッチングするテンプレートに基づいて、比較結果を生成するステップとを含む、請求項５に記載の方法。
【請求項７】
２つ以上のテンプレートが入来するデータパケットにマッチングした場合、テンプレートの優先性を１つの最終的なフレームタグに決定するステップをさらに含む、請求項６に記載の方法。
【請求項８】
第１のデータバイトは予め規定された形式を有するパケットの第１のデータバイトに対応し、同時に比較するステップは、選択データバイトを、予め規定された形式を有するパケットの開始に対して評価するステップを含む、請求項５に記載の方法。
【請求項９】
予め規定された形式はインターネットプロトコル（ＩＰ）形式である、請求項８に記載の方法。
【請求項１０】
検出された少なくとも１つのマッチングするテンプレートに基づいて比較結果を生成するステップは、
入来するデータパケットと比較される最小項ごとに、対応の方程式を識別するステップを含み、各方程式はテンプレートの選択された群に対する固有の結果を指定し、さらに
検出された少なくとも１つのマッチングするテンプレートを有する方程式によって比較結果を生成するステップを含む、請求項６に記載の方法。
【請求項１１】
入来するデータパケットを評価するよう構成されるネットワークスイッチポートフィルタであって、
最小項値を記憶するよう構成される最小項メモリを含み、各最小項値は、比較のための入来するデータパケットの対応の選択バイトの位置と、対応の比較動作を指定する表現部分と、対応の最小項を使用するテンプレートを指定するテンプレート識別子フィールドとに基づいて記憶され、さらに
入来するデータバイトが受けられると瞬時に、入来するデータパケットのバイトと、受けたバイトに対応する最小項とを比較し、かつそれぞれの最小項比較結果を生成する、最小項生成器と、
テンプレートに対する最小項比較結果に基づいて入来するデータパケットを識別するフレームタグを生成するよう構成される方程式コアとを含む、ネットワークスイッチポートフィルタ。
【請求項１２】
レイヤ２パケットの種類を識別するよう構成されるフレーム識別子をさらに含み、入来するデータパケットの選択バイトはレイヤ２パケットの識別された種類に基づいて判断される、請求項１１に記載のフィルタ。
【請求項１３】
各記憶される最小項値の位置は、レイヤ２パケット内のＩＰフレームの開始に関連する、請求項１２に記載のフィルタ。
【請求項１４】
最小項を、入来するデータパケット内のＩＰフレームの選択バイトに対応する最小項メモリからフェッチするよう構成される、最小項コントローラをさらに含む、請求項１３に記載のフィルタ。
【請求項１５】
方程式コアは、入来するデータパケットのワイヤレートで、かつ入来するデータパケットの終了前に、フレームタグを生成する、請求項１１に記載のフィルタ。
【請求項１６】
２つ以上のテンプレートが入来するデータパケットにマッチングする場合、テンプレートの優先性を１つの最終的なフレームタグ値に決定するよう構成されるタグ優先性装置をさらに含む、請求項１１に記載のフィルタ。
【発明の詳細な説明】
【０００１】
この発明は、サブネットワーク間でデータパケットをスイッチングするよう構成されるノンブロッキングネットワークスイッチにおけるデータパケットのレイヤ２およびレイヤ３スイッチングに関する。
【０００２】
【背景技術】
ローカルエリアネットワークは、ネットワークケーブルまたは他のメディアを用いてネットワーク上のステーションをリンクする。各ローカルエリアネットワークアーキテクチャは、メディアアクセス制御（ＭＡＣ）を用いて各ネットワークノードにおけるネットワークインターフェイス装置がネットワークメディアにアクセスできるようにする。
【０００３】
イーサネット（Ｒ）プロトコルＩＥＥＥ８０２．３は、データパケットの伝送のための半二重メディアアクセス機構と全二重メディアアクセス機構とを指定するよう発展した。全二重メディアアクセス機構は、２つの要素間の、たとえばネットワークノードとスイッチングされるハブとの間の、二方向のポイントツーポイント通信リンクを提供する。
【０００４】
スイッチ型ローカルエリアネットワークは、より高速な接続性、より柔軟なスイッチング性能、およびより複雑なネットワークアーキテクチャに対処する能力をますます要求されている。たとえば、本発明の譲受人に譲渡された米国特許第５，９５３，３３５号は、異なったネットワークノード間のレイヤ２タイプイーサネット（Ｒ）（ＩＥＥＥ８０２．３）データパケットをスイッチングするよう構成されるネットワークスイッチを開示する。受信したデータパケットは、別のサブネットワーク（ルータを介する）または予め規定されるステーションの群を指定するＩＥＥＥ８０２．１ｑプロトコルに従ってＶＬＡＮ（仮想ＬＡＮ）タグ付けされたフレームを含み得る。スイッチングはレイヤ２レベルで生じるので、ルータは典型的にはデータパケットをサブネットワーク間で転送することが必要である。
【０００５】
レイヤ３（たとえば、インターネットプロトコル）処理を含むよう、ネットワークスイッチのスイッチング性能を向上させる努力は、深刻な不利点を有し得るが、これは現在のレイヤ２スイッチは好ましくはノンブロッキングモードで動作するよう構成されるからであり、この場合データパケットはデータパケットが受信されるのと同じ速度でスイッチから出力され得る。１００Ｍｂｐｓまたはギガビットネットワークのようなより高速なネットワークに対して、より高速なスイッチが、レイヤ２スイッチングおよびレイヤ３スイッチング能力の両方を提供できることを確実にする、より新しい設計が必要とされている。
【０００６】
しかしながら、そのような設計要件はネットワークスイッチのノンブロッキング特徴を失うリスクを有するが、これはネットワークスイッチのスイッチングファブリックがワイヤレート（すなわち、ネットワークデータレート）でレイヤ３処理を行なえることがさますます難しくなってきているからである。
【０００７】
従来のルータおよびハイエンドスイッチは、集中化ソフトウェアベースのＣＰＵ集約方式を用いて、分類のためにデータパケットを調べ、かつ、クラスまたはパケットのスイッチング／ルーティングのための優先性を判断する。図１は、データパケットが従来のネットワークスイッチポートに到着してから（Ｔ１）出力ポートでネットワークスイッチを出るまで（Ｔ１０）の、データパケットのタイムシーケンスを示す。パケットが（Ｔ３で）プロセッサに送られ、次いで（Ｔ５−Ｔ６で）プロセッサによって分類されなければならないので、レイテンシ（第１のビットが入ってから第１のビットが出ていくまで）は高く、Ｓ１＋Ｓ２＋Ｓ３＋Ｓ４で表すことができる。レイテンシが高いのは、パケットがすべて受信されるまではその処理が始まりさえしないからである（Ｔ２の後）。
【０００８】
【発明の要約】
データパケットをブロッキングすることなく、ネットワークスイッチが１００Ｍｂｐｓおよびギガビットリンクに対するレイヤ２スイッチングおよびレイヤ３スイッチング能力を提供することを可能にする構成に対する必要性がある。
【０００９】
また、ネットワークスイッチが、スイッチングされるデータパケットのレイテンシに影響を与えるおそれのあるネットワーク内のバッファリングを最小限にして、レイヤ２スイッチングおよびレイヤ３スイッチング能力を提供することを可能にする構成に対する必要性もある。
【００１０】
ネットワークスイッチが異なった種類のレイヤ３データパケットを区別するよう、簡単にプログラムすることを可能にして、サービス品質（ＱｏＳ）を達成する構成に対する必要性もある。
【００１１】
また、ネットワークスイッチが瞬時に入来するデータパケットを評価してレイヤ３またはそれ以上のプロトコルを判断し、関連のスイッチファブリックに、入来するデータパケットを検出されたプロトコルに従って処理するのに十分な時間を提供することを可能にする構成に対する必要性もある。
【００１２】
これら、および他の必要性は、ネットワークスイッチポートにおいて、データパケットの最後のビットがネットワークスイッチポートで受信されるとすぐに、データパケットの全体の評価に基づいてフレームタグが生成される、この発明によって満たされる。
【００１３】
この発明の１局面は、入来するデータパケットをネットワークスイッチポートで評価する方法を提供する。方法は、それぞれのデータ形式を識別するよう構成される複数のテンプレートを記憶するステップを含み、各テンプレートは対応の予め規定された値と、入来するデータパケットの対応の選択バイトとを比較するよう構成される、少なくとも１つの最小項を有する。選択バイトに対応する最小項は選択バイトがネットワークスイッチポートで受けられると瞬時に、選択バイトと比較される。最小項と、ネットワークスイッチポートにより受けられたデータパケット全体のデータバイトとの比較に基づいて、入来するデータパケットを識別する比較結果が生成される。ネットワークスイッチポートでデータパケットの最後のビットが受けられるとすぐに、比較結果に基づいたフレームタグが生成される。
【００１４】
この発明のさらなる利点、および新規な特徴は、一部は以下の説明に記載され、一部は当業者においては以下を読むことにより明らかとなるか、発明を実施することにより理解されるであろう。この発明の利点は、特に前掲の特許請求の範囲に示される手段および組み合わせによって実現され、達成され得る。
【００１５】
添付の図面を参照するが、同様の参照符号を有する要素は、図面を通して同様の要素を示す。
【００１６】
【発明を実行するためのベストモード】
図２は、イーサネット（Ｒ）（ＩＥＥＥ８０２．３）ネットワークのような、パケット交換網１０を示すブロック図である。パケット交換網は、ネットワークステーション１４の間でデータパケットの通信を可能にする統合（すなわち、シングルチップ）マルチポートスイッチ１２を含む。各ネットワークステーション１４、たとえばクライアントワークステーションは、典型的にはＩＥＥＥ８０２．３プロトコルに従って１０Ｍｂｐｓまたは１００Ｍｂｐｓでデータパケットを送受信するよう構成される。各統合マルチポートスイッチ１２は、イーサネット（Ｒ）リンク１６によって相互接続され、サブネットワーク１８ａ、１８ｂ、および１８ｃの間のデータパケットの転送が可能である。よって、各サブネットワークはスイッチ１２と、関連のネットワークステーションの群１４とを含む。
【００１７】
各スイッチ１２は、スイッチポート２０を含み、これはメディアアクセス制御（ＭＡＣ）モジュール２２およびパケット分類子モジュール２４を含む。ＭＡＣモジュール２２は、ＩＥＥＥ８０２．３ｕプロトコルに従って、１０／１００Ｍｂｐｓ物理層（ＰＨＹ）トランシーバ（図示せず）をわたってデータパケットを関連のネットワークステーション１４に送受信する。各スイッチ１２はまた、受取ったデータパケットに対してフレーム転送判断をするよう構成されるスイッチファブリック２５をも含む。特に、スイッチファブリック２５は、イーサネット（Ｒ）（ＩＥＥＥ８０２．３）ヘッダ内のソースアドレス、デスティネーションアドレス、およびＶＬＡＮ情報に基づいてレイヤ２スイッチング判断をするよう構成される。スイッチファブリック２５はまた、イーサネット（Ｒ）パケット内のＩＰデータパケットの評価に基づいた選択的レイヤ３スイッチング判断に対しても構成される。
【００１８】
図２に示されるように、各スイッチ１２は関連のホストＣＰＵ２６と、たとえばＳＳＲＡＭのようなバッファメモリ２８とを含む。ホストＣＰＵ２６は、スイッチファブリック２５のプログラミングを含む対応のスイッチ１２の全体動作を制御する。バッファメモリ２８は、スイッチファブリック２５が受取ったデータパケットに対する転送判断を処理している間に、対応のスイッチ１２によって用いられてデータフレームを記憶する。
【００１９】
上述のように、スイッチファブリック２５は、レイヤ２スイッチング判断およびレイヤ３スイッチング判断を行なうよう構成される。レイヤ３スイッチング判断が利用可能であることは、サブネットワーク１８ａ内のエンドステーション１４が、サブネットワーク１８ｂ、１８ｃ、またはそれら両方内の選択されたネットワークステーションにｅメールメッセージを送ることを所望する場合に特に有効である。レイヤ２スイッチング判断しか利用可能でなければ、スイッチ１２ａのスイッチファブリック２５は特定のデスティネーションアドレス情報なしにｅメールメッセージをスイッチ１２ｂおよび１２ｃに送り、スイッチ１２ｃおよびスイッチ１２ｃのすべてのポートを溢れさせるであろう。そうでなければ、スイッチ１２ａのスイッチファブリック２５は、ｅメールメッセージをルータ（図示せず）に送る必要があるが、これはさらなる遅延をもたらす。スイッチファブリック２５によるレイヤ３スイッチング判断の利用は、スイッチファブリック２５が先取り転送判断を含めてどのようにパケットを扱うか、およびビデオまたは音声のようなレイテンシに対して繊細なアプリケーションに対する、高優先性パケットであると考慮すべきかどうかに及ぶ、知的な判断が行なえるようになる。スイッチファブリック２５によるレイヤ３スイッチング判断の利用はまた、スイッチ１２ａのホストＣＰＵ２６が、別のスイッチ、たとえばスイッチ１２ｂに、スイッチ１２ｂのＩＰアドレスに対応するＩＰアドレスを有するメッセージを送ることにより、スイッチ１２ｂを遠隔的にプログラムすることを可能にする。スイッチ１２ｂは、スイッチ１２ｂに宛先決めされたメッセージの検出に応答して、スイッチ１２ｂのプログラミングのために対応のホストＣＰＵ２６にメッセージを転送することができる。
【００２０】
図３は、ペイロードデータとしてＩＰパケット３２を搬送するイーサネット（Ｒ）（ＩＥＥＥ８０２．３）パケット３０を示す図である。特定的には、イーサネット（Ｒ）パケット３０は、スタートフレームデリミタ（ＳＦＤ）３４、イーサネット（Ｒ）ヘッダ３６、ＩＰパケット３２、および周期遅延チェック（ＣＲＣ）またはフレームチェックシーケンス（ＦＣＳ）フィールド３８を含む。よって、レイヤ３スイッチング判断に対して構成されるスイッチファブリック２５は、受取ったイーサネット（Ｒ）フレーム３０内でＩＰパケット３２をすばやく処理して、フレームのスイッチ内でのブロッキングを防ぐことができる必要がある。
【００２１】
図４は、入来するデータパケットに対して行なわれるであろう、レイヤ３処理タイプの例を示すフロー図である。図３のフロー図は、従来的にソフトウェアで実現され、ステップ５０において入来するデータパケットがハイパーテキスト転送プロトコル（ＨＴＴＰ）パケットであるかどうか、ステップ５２においてＳＮＭＰパケットであるかどうか、またステップ５４において高優先性パケットであるかどうかを調べることにかかわり得る。次いで、ステップ５６、５７、５８または６０において、パケットを識別する適切なタグが割当てられる。
【００２２】
しかしながら、図４の構成は、１００Ｍｂｐｓまたはギガビットネットワークに対するノンブロッキングスイッチを提供するであろう態様では、ハードウェアでは実務的な見地からは実現できない。特に、図３における判断プロセスの逐次的性質は、入来するデータパケットに対して過度の遅延をもたらすであろう。
【００２３】
開示される実施例に従うと、図２のパケット分類子モジュール２４は、入来するデータストリームと、入来するデータストリームのデータ形式を識別するテンプレートとの間での多数の同時の比較に対して構成される。特定的には、ホストプロセッサ２６のユーザは、特定のＩＰプロトコルを有するデータパケットがスイッチファブリック２５によってどのように扱われるべきかを定義するポリシーを指定する。これらのポリシーは、対応のＩＰプロトコルタイプごとに１組のフレーム転送判断をスイッチファブリック２５にローディングすることにより実現される。よって、スイッチファブリック２５は、１組のＨＴＴＰパケットに対するフレーム転送命令、別の組のＳＮＭＰパケットに対するフレーム転送命令、および別の組の高優先性パケット（たとえば、ビデオまたは音声など）に対するフレーム転送命令を含み得る。
【００２４】
図５は、この発明の実施例に従うパケット分類子モジュール２４を示すブロック図である。図５に示されるように、ネットワークスイッチポート２０はＭＡＣ２２、受信ＦＩＦＯバッファ２７、ヘッダ変更子２９、およびパケット分類子モジュール２４を含む。ネットワークスイッチポートフィルタとも呼ばれるパケット分類子モジュール２４は、ネットワークスイッチポート２０で入来するデータパケットを識別（すなわち評価）し、かつ受信されるデータパケットの種類に基づいてデータパケットに行なうべき動作を指定するタグをスイッチファブリック２５に供給するよう構成される。特定的には、図９に示されるように、パケット分類子モジュール２４は、データがスイッチポート２０で受信されるとすぐに、入来するデータパケットと、それぞれのデータ形式を識別するよう構成される複数のテンプレートとを、比較する。入来するデータパケットと複数のテンプレートとの比較に基づいて、パケット分類子モジュール２４は、スイッチファブリック２５に提供されるべきタグを指定する、実行されるべき方程式を識別する。図９に示されるように、パケットはスイッチポート２０で受信されるとすぐに分類されるので、パケットが有効であるかどうかにかかわらず、レイテンシＳ１＋Ｓ２＋Ｓ３は、図１を参照して説明されたレイテンシに比べて減じられている。
【００２５】
特定的には、パケット分類子モジュール２４は、複数のテンプレートの中から少なくとも１つのマッチングするテンプレートを検出することにより、入来するデータパケットを識別する比較結果を生成する。パケット分類子モジュール２４は次いで、どの方程式がマッチングしたテンプレートを含むかを識別し、方程式によって指定されるタグを生成する。
【００２６】
図６Ａおよび図６Ｂは、パケット分類子モジュール２４による、方程式の２つのテンプレートの同時処理を示す図である。図６Ａは、以下の方程式のパケット分類子モジュール２４による論理評価を示す。
【００２７】
Ｅｑ１＝Ｍ１＊Ｍ２＊Ｍ３＊Ｍ４＊（Ｍ５＋Ｍ６＋Ｍ７＋Ｍ８）
図６Ｂは、実際にどのように方程式Ｅｑ１が最小項メモリ７０に記憶され得るかを示す。方程式Ｅｑ１は、４つのテンプレート６２ａ、６２ｂ、６２ｃおよび６２ｄを含む。テンプレート６２ａは、最小項Ｍ１、Ｍ２、Ｍ３、Ｍ４およびＭ５を含む。テンプレート６２ｂは最小項Ｍ１、Ｍ２、Ｍ３、Ｍ４およびＭ６を含む。テンプレート６２ｃは最小項Ｍ１、Ｍ２、Ｍ３、Ｍ４およびＭ７を含む。テンプレート６２ｄは最小項Ｍ１、Ｍ２、Ｍ３、Ｍ４およびＭ８を含む。各テンプレート６２は、ＩＰデータパケット３２のヘッダに基づいて認識可能である特定のＩＰデータ形式に対応する。たとえば、テンプレート６２ａおよび６２ｃはＨＴＴＰパケットを識別するよう構成され、テンプレート６２ｂおよび６２ｄはＳＮＭＰパケットを識別するよう構成され得る。特定的には、ＩＰｖ４形式であり、ＩＰにおけるｔｉｍｅ ｔｏ ｌｉｖｅフィールドが１より大きく、ＩＰヘッダにおけるプロトコルフィールドがＴＣＰであり、ヘッダチェックサムが正しく、ソースＴＣＰポートが８０、またはデスティネーションＴＣＰポートが８０であれば、ＨＴＴＰパケットが識別される。ＩＰｖ４形式であり、ＩＰにおけるｔｉｍｅ ｔｏ ｌｉｖｅフィールドが１より大きく、ＩＰヘッダにおけるプロトコルフィールドがＴＣＰであり、ヘッダチェックサムが正しく、ソースＴＣＰポートが２５、またはデスティネーションＴＣＰポートが２５であれば、ＳＮＭＰパケットが識別される。
【００２８】
よって、すべての上述の基準を表わすよう、以下の最小項が確立され得る。
Ｍ１＝パケットはＩＰｖ４形式である
Ｍ２＝ＩＰにおけるｔｉｍｅ ｔｏ ｌｉｖｅフィールドは１よりも大きい
Ｍ３＝ＩＰヘッダにおけるプロトコルフィールドはＴＣＰである
Ｍ４＝ヘッダチェックサムは正しい
Ｍ５＝ソースＴＣＰポートは８０である
Ｍ６＝デスティネーションＴＣＰポートは８０である
Ｍ７＝ソースＴＣＰポートは２５である
Ｍ８＝デスティネーションＴＣＰポートは２５である
よって、テンプレート６２ａおよび６２ｃは、ＨＴＴＰパケットを識別し、テンプレート６２ｂおよび６２ｄはＳＮＭＰパケットを識別する。こうして、方程式１（Ｅｑ１）は、テンプレート６２ａ、６２ｂ、６２ｃまたは６２ｄのいずれかが真であれば特定の結果（たとえば特定の値を有するタグ）がスイッチファブリック２５に出力されるべきことを指定する。
【００２９】
さらに、最小項Ｍ１…Ｍ８は、入来するデータストリーム内のデータバイトの相対的な位置に対応する予め規定された順序で関連のテンプレート６２ａおよび／または６２ｂ内に配置される。図７に示されるように、最小項Ｍ１はＩＰパケット３２の第１のバイト（Ｂ１）との比較のために構成され、最小項Ｍ２はＢ１に続く、ＩＰパケット３２の後のバイト（Ｂ２）との比較のために構成され、最小項Ｍ３はＢ２に続く、後のバイト（Ｂ３）との比較のために構成され、以下同様である。よって、入来するデータストリーム内のデータバイトの相対的な位置に基づいた順序で最小項を有するテンプレート６２を用いると、入来するデータストリームと最小項との間で多数の同時比較が可能になる。よって、入来するデータパケットは多数のテンプレートと比較されて、入来するデータパケットのデータ形式を判断するだけでなく、スイッチファブリック２５がどのような動作を行なうべきかも判断する。
【００３０】
図５に示されるように、ネットワークスイッチポートフィルタとも呼ばれるパケット分類子２４は、以下に説明するように、図８に示される最小項値（たとえばＭ１、Ｍ２など）を記憶するための最小項メモリ７０を含む。パケット分類子２４はまた、受取るレイヤ２フレームの種類を識別するよう構成されるフレーム識別子７２をも含む。特定的には、受取ったレイヤ２フレームの種類（たとえばイーサネット（Ｒ）ＩＥＥＥ８０２から３など）を識別すると、レイヤ２パケット３０内のＩＰパケット３２の開始位置６４を識別することを可能にする。パケット分類子２４はまた、最小項コントローラ７４、最小項生成器７６、方程式コア７８、および評価結果メモリ８０を含む。プロセッサインターフェイスモジュール（ｐｉ＿ ｍｏｄ）８２は、ホストＣＰＵ２６から最小項メモリ７０に生成された最小項を転送するために用いられる。
【００３１】
最小項コントローラ７４は、ＩＰフレーム３２の選択バイトに対応する最小項を最小項メモリ７０からフェッチするよう構成される。最小項コントローラ７４はまた、レイヤ２フレームの種類を指定するフレーム識別子７２からのフレームタイプ（ｆｒｍ＿ｔｙｐｅ）信号に応答して、開始位置６４の実際のバイト位置（ｂｙｔｅ＿ｌｏｃａｔｉｏｎ）を指定するよう構成される位置コンバータを含む。よって、最小項コントローラ７４は、ＩＰパケットの開始の検出に応答して、ＩＰパケット３２の第１のバイト（Ｂ１）と比較されるべきすべての最小項、たとえば図７における方程式Ｅｑ１、Ｅｑ２、およびＥｑ３に対する最小項Ｍ１、Ｍ９、およびＭ１４をフェッチする。次いで最小項コントローラ７４は、最小項値（Ｍ＿　ＳＴＲＵ　ＩＮＦＯ）を、最小項生成器７６および方程式コア７８に転送する。
【００３２】
最小項生成器７６は、最小項コントローラによってフェッチされた最小項と、入来するデータストリームの選択バイトとの実際の最小項比較を行なう。たとえば、最小項生成器７６は図７において、入来するデータバイトＢ１と最小項Ｍ１、Ｍ９およびＭ１４とを同時に比較し、最小項比較結果（ｍｔ＿ ｒｅｓｕｌｔ）を方程式コア７８に与える。次の比較サイクルの間に、最小項生成器７６は入来するデータバイトＢ２と最小項Ｍ２、Ｍ１０およびＭ１５とを同時に比較する。開示される実施例に従うと、最小項生成器は入来するデータストリームと８つまでの最小項とを比較するよう構成される。
【００３３】
方程式コア７８は、関連のテンプレート６２に対する、最小項生成器７６から受取った最小項比較結果に基づいてフレームタグを生成するよう構成される。たとえば、方程式コア７８は、方程式生成器から結果が供給されるにつれて、最小項結果を逐次的に評価することにより、図１に示される方程式１を評価する。たとえば、もし最小項Ｍ１、Ｍ２、Ｍ３、Ｍ４、Ｍ５およびＭ６ごとの比較結果が真の条件をもたらすと、これを以下に図８を参照して説明するが、方程式１において終了条件がマッチングし、よって方程式コア７８は方程式１に対して指定される条件に対応するタグを生成する。フレームタグは入来するデータパケットの性質、およびスイッチファブリック２５によって行なわれるべき動作を識別する。
【００３４】
よって、パケットがスイッチポート２０に到着すると、パケット分類子２４はすぐにプログラム可能な量（バイトワード、ダブルワードなど）の境界で、到着するデータをテンプレート内の適切なフィールドに対して調べる。マッチングが見つかれば、パケット分類子２４はどのテンプレートがマッチングしたかの記録をとり、入来するパケットフィールドの残りの検査を到着順に続ける。途中で、パケットにマッチングしなかったテンプレートはさらなる比較から除かれる。パケットの最後に、または完全にマッチングしたテンプレートに、パケット分類子２４の方程式コア７８は、マッチングしたテンプレートに関連するタグをパケットにつける。パケットに１つ以上のテンプレートがマッチングする場合もある。そのような場合には、タグ優先性決定装置８１がユーザによって定義される優先性に基づく判断を行ない、それによりフレームの最後またはその近傍において、単一のフレームタグ値が選択されスイッチファブリック２５に送られる。
【００３５】
図８は、最小項メモリ７０における最小項構造のデータ形式を示す図である。開示される実施例によると、最小項は、比較されるべきデータバイトの相対的位置に対応する順序で最小項メモリ７０内に記憶される。よって、第１のデータバイトと比較されるべきすべての最小項は、最小項メモリの第１の部分にともに記憶され、その後に第２のデータバイトと比較されるべき最小項が続き、以下同様である。
【００３６】
これに代えて、最小項は、ＩＰヘッダ内の関連の情報および比較されるべきデータバイトの相対的位置に基づいた順序で記憶され得る。よって、最小項は、ソースＩＰアドレスと、デスティネーションＩＰアドレスと、ソースおよびデスティネーションポートとを提供するデータバイトのシーケンスを比較するための順序で記憶され得る。この場合、ＩＰフレームの開始での関連のないデータバイトは最小項メモリ７０の開始に記憶される関連の最小項を有さず、さらに最小項メモリ７０の効率性を高める。
【００３７】
各テーブルエントリ９０は最小項部分と評価部分とを含む。最小項部分はマスクフィールド（ＭＡＳＫ）９４と、予想されるデータフィールド（ＥＸＰ　ＤＡＴＡ）９６と、オペレータフィールド（ＯＰＥＲＡＴＯＲ）９８とを含む。最小項メモリ７０内のテーブルエントリ９０の位置に基づいて、最小項コントローラ７４は、ＩＰパケット３２のどのバイトが、ＩＰパケットの開始６４に対して、対応の最小項と比較されねばならないかを判断することができる。マスクフィールド９４は、比較を行なうために最小項生成器７６によって用いられるマスクである。もしマスクが１に設定されるビットを有し、かつもしマスク値がフィールド内にゼロを有すれば、比較はドントケアである。予想されるデータフィールド９６は、ＩＰパケット３２の関連のデータバイトと比較されるべき期待されるデータを指定する。オペレータフィールド９８は、最小項生成器によって行なわれるべき比較の種類を指定する。たとえば、未満、以下、等しい、よりも大きい、以上、等しくない、である。
【００３８】
評価部分は、分岐部分１００、最小項部分の比較が真であった場合のための応答部分（ＲＩＮＰ１）１０２、最小項部分の比較が偽であった場合のための第２の応答部分（ＲＩＮＰ０）１０６、および方程式識別子１１０を含む。分岐部分１００は方程式内のＯＲ項の順序を指定する。たとえば、図６および図７に示す最小項Ｍ１の分岐部分は００００　１１１１に設定され得るが、これは方程式フィールド１１０で指定される方程式の最初の４つの分岐が対応の最小項を含むべきことを示す。分岐部分に８つのビットが用いられているので、所与の方程式内に最大８つの分岐が含まれることが推定される。
【００３９】
応答部分１０２は、最小項部分が比較されるデータバイトに対して真であると評価された場合に行なわれるべき動作を指定する。特に、完了ビット（ＦＩＮ）は、方程式の結果が最小項結果は真であると判断する場合、１に設定される。初期に戻る（ＢＩＮＩＴ）は、最小項結果が真であれば評価プロセスは初期状態（ｉｎｉｔ）に戻るべきであれば１に設定される。たとえば、最小項Ｍ１の場合、ＲＩＮＰ１のＦＩＮビットおよびＢＩＮＩＴビットはゼロに設定されるが、これはもし最小項結果が真であればさらなる比較が必要なためである。最小項Ｍ５、Ｍ６、Ｍ７およびＭ８の場合には、ＲＩＮＰ１のＦＩＮビットは１に設定されるがこれは「真」結果である比較結果が、図６に示すように評価の終了をもたらすからである。
【００４０】
応答部分１０６は、最小項部分が比較されるデータバイトに対して偽であると評価された場合に行なわれるべき動作を指定する。特に、完了ビット（ＦＩＮ）は方程式の結果が最小項結果が偽であると判断する場合、１に設定される。最初に戻る（ＢＩＮＩＴ）は評価プロセスが最小項結果が偽である場合に初期状態（ｉｎｉｔ）に戻るべきであれば１に設定される。たとえば、最小項Ｍ１の場合、ＦＩＮビットはゼロに設定され、ＲＩＮＰ１のＢＩＮＩＴビットは１に設定され、よって図６に示すように最小項Ｍ１が偽であればＩＮＩＴ状態に戻るようにする。
【００４１】
方程式識別子フィールド１１０は、最小項が対応する方程式（または、方程式に１つのテンプレートしかなければテンプレート）を識別する。
【００４２】
よって、方程式コア７８は任意の指定される方程式が、入来するデータストリームとマッチングするテンプレート６２を有するかどうかを判断する。入来するデータストリームと多数のテンプレート６２との多数の同時比較に基づいて、方程式コア７８はマッチングする方程式を識別することができ、スイッチングファブリック２５でのフレーム転送判断のためにマッチングした方程式に対応する適切なタグを生成する。所望であれば、コア７８は、データをスイッチに転送する前に、レイヤ２ヘッダ、レイヤ３ヘッダ、またはそれら両方を修正するためにヘッダ変更子２９にコマンドを出力する。
【００４３】
開示される実施例に従うと、ネットワークスイッチポートは、入来するデータパケットのデータストリームと、対応のプロトコルを識別するよう構成される多数のテンプレートとの多数の同時比較を行なうことが可能であるフィルタを含む。パケット分類子モジュール２４はＩＰフレーム３２のどのバイトをも処理できるので、、パケット分類子モジュール２４はレイヤ３からレイヤ７プロトコルまでの、ＩＰパケット３２におけるすべてのヘッダ情報を解釈することができる。さらに、多数の同時比較により、ネットワークスイッチ１２がネットワークスイッチ内でブロッキングすることなく１００Ｍｂｐｓおよびギガビットネットワークに対するレイヤ３スイッチングを行なうことが可能になる。最後に、データが受取られた順序での多数の同時比較により、処理を始める前にヘッダ全体を受信することを必要とするプログラマブルロジックアレイ（ＰＬＡ）のような代替的な方式とは対照的に、リアルタイムの比較を行なうことを可能にする。
【００４４】
よって、開示される実施例に従うと、パケット分類および関連のスイッチ制御属性の決定は、パケットの最後のビットがスイッチポートに到着するとすぐに生じ、それにより全体的なスイッチレイテンシが減じられる。こうして、パケット分類子は、ＩＳＯモデルのどのレイヤのものでも、どのようなプロトコルにも基づいて、ワイヤ速度でパケットを転送するよう構成され得る。
【００４５】
この発明を、現在最も実際的な好ましい実施例であると考えられる実施例について説明してきたが、この発明は開示される実施例に限定されるものではなく、反対に、さまざまな修正および等価な構成を、前掲の特許請求の範囲の精神および範囲に含むことが意図されることを理解されたい。
【図面の簡単な説明】
【図１】従来のネットワークスイッチポートにパケットが到着してからパケットがポートを出るまでの時間で規定される、データパケットのレイテンシを示す図である。
【図２】この発明の実施例に従った、それぞれのサブネットワーク間でデータパケットをスイッチングするための、多数のネットワークスイッチを含むパケット交換網のブロック図である。
【図３】レイヤ３インターネットプロトコル（ＩＰ）パケットを担持する従来のレイヤ２イーサネット（Ｒ）タイプのデータパケットを示す図である。
【図４】ＩＰパケットを評価する従来の（先行技術）方法を示すフロー図である。
【図５】この発明の実施例に従った、ネットワークスイッチポートフィルタを含む、図２のネットワークのネットワークスイッチポートを示すブロック図である。
【図６Ａ】図５の最小項生成器による方程式の４つのテンプレートの同時処理を示す図である。
【図６Ｂ】図５の最小項生成器による方程式の４つのテンプレートの同時処理を示す図である。
【図７】図５の最小項生成器による最小項の同時処理のさらなる詳細を示す図である。
【図８】この発明の実施例に従った、図５の最小項メモリ内の最小項のテーブルエントリを示す図である。
【図９】ネットワークスイッチポートにパケットが到着してからパケットがポートを出るまでの時間で規定される、この発明の実施例のデータパケットのレイテンシを示す図である。
【図１】
2004507158.tif 000003
【図２】
2004507158.tif 000004
【図３】
2004507158.tif 000005
【図４】
2004507158.tif 000006
【図５】
2004507158.tif 000007
【図６Ａ】
2004507158.tif 000008
【図６Ｂ】
2004507158.tif 000009
【図８】
2004507158.tif 000010
【図９】
2004507158.tif 000011
【国際公開パンフレット】
2004507158.tif 000012
2004507158.tif 000013
2004507158.tif 000014
2004507158.tif 000015
2004507158.tif 000016
2004507158.tif 000017
2004507158.tif 000018
2004507158.tif 000019
2004507158.tif 000020
2004507158.tif 000021
2004507158.tif 000022
2004507158.tif 000023
2004507158.tif 000024
2004507158.tif 000025
2004507158.tif 000026
2004507158.tif 000027
2004507158.tif 000028
2004507158.tif 000029
2004507158.tif 000030
2004507158.tif 000031
2004507158.tif 000032
2004507158.tif 000033
【国際公開パンフレット（コレクトバージョン）】
2004507158.tif 000034
2004507158.tif 000035
【手続補正書】
【提出日】平成14年9月30日(2002.9.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】パケット分類のための装置および方法


【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入来するデータパケット（３２）をネットワークスイッチポート（２０）で評価する方法であって、該方法はネットワークスイッチポート（２０）により受けられたデータバイトと対応の予め規定された値との比較に基づいて比較結果を生成し、かつ比較結果に基づいてフレームタグを生成する方法であって、該方法は
それぞれのデータ形式を識別するよう構成される複数のテンプレート（６２ａ−ｄ）を記憶するステップを含み、各テンプレート（６２）は対応の予め規定された値と、入来するデータパケット（３２）の対応の選択バイトとを比較するよう構成される、少なくとも１つの最小項（Ｍ１−Ｍ８）を有し、さらに
選択バイトがネットワークスイッチポート（２０）で受けられると瞬時に、選択バイトと選択バイトに対応する最小項（Ｍ１−Ｍ８）とを同時に比較するステップと、
最小項（Ｍ１−Ｍ８）と、ネットワークスイッチポート（２０）により受けられたパケット（３２）全体のデータバイトとの比較に基づいて、入来するデータパケット（３２）を識別する前記比較結果を生成するステップと、
ネットワークスイッチポート（２０）でデータパケット（３２）の最後のビットが受けられるとすぐに、比較結果に基づいた前記フレームタグを生成するステップとを含むことを特徴とする、方法。
【請求項２】
同時に比較するステップは、
第１のデータバイトに対応する最小項（Ｍ１−Ｍ８）を最小項生成器（７６）にローディングするステップと、
最小項生成器（７６）にローディングされた最小項（Ｍ１−Ｍ８）と第１のデータバイトとを並行に比較するステップと、
最小項生成器（７６）にローディングされた最小項（Ｍ１−Ｍ８）に対する比較結果を評価コア（７８）に出力するステップとを含む、請求項１に記載の方法。
【請求項３】
同時に比較するステップは、第１のデータバイトに連続する第２のデータバイトに対応する最小項（Ｍ１−Ｍ８）を最小項生成器（７６）にローディングするステップをさらに含む、請求項２に記載の方法。
【請求項４】
対応のフレームタグに基づいて入来するデータパケット（３２）を選択的にスイッチングするよう構成されるスイッチファブリック（２５）にフレームタグを出力するステップをさらに含む、請求項１、請求項２または請求項３に記載の方法。
【請求項５】
記憶するステップは、各最小項（Ｍ１−Ｍ８）をテーブルエントリ（９０）としてメモリ（７０）に記憶するステップを含み、各テーブルエントリ（９０）は、入来するデータパケット（３２）内の対応の選択バイトの位置に基づくメモリ（７０）内の位置を有し、テーブルエントリ（９０）は対応の予め規定された値および比較オペランドを指定する最小項表現部分と、対応の最小項を用いるテンプレートを指定するテンプレート識別子フィールドとを含む、請求項１、請求項２、請求項３または請求項４に記載の方法。
【請求項６】
生成するステップは、
最小項（Ｍ１−Ｍ８）と入来するデータパケット（３２）の選択バイトとの比較結果を一時的に記憶するステップと、
最小項（Ｍ１−Ｍ８）の比較の結果に基づいて、複数のテンプレート（６２ａ−ｄ）から少なくとも１つのマッチングするテンプレート（６２）を検出するステップと、
検出された少なくとも１つのマッチングするテンプレート（６２）に基づいて、比較結果を生成するステップとを含む、請求項５に記載の方法。
【請求項７】
２つ以上のテンプレート（６２）が入来するデータパケット（３２）にマッチングした場合、テンプレートの優先性を１つの最終的なフレームタグに決定するステップをさらに含む、請求項６に記載の方法。
【請求項８】
第１のデータバイトは予め規定された形式を有するパケットの第１のデータバイトに対応し、同時に比較するステップは、選択データバイトを、予め規定された形式を有するパケットの開始に対して評価するステップを含む、請求項５、請求項６、または請求項７に記載の方法。
【請求項９】
予め規定された形式はインターネットプロトコル（ＩＰ）形式である、請求項８に記載の方法。
【請求項１０】
検出された少なくとも１つのマッチングするテンプレート（６２）に基づいて比較結果を生成するステップは、
入来するデータパケット（３２）と比較される最小項（Ｍ１−Ｍ８）ごとに、対応の方程式を識別するステップを含み、各方程式はテンプレートの選択された群に対する固有の結果を指定し、さらに
検出された少なくとも１つのマッチングするテンプレート（６２）を有する方程式によって比較結果を生成するステップを含む、請求項６または請求項７に記載の方法。
【請求項１１】
入来するデータパケット（３２）を評価するよう構成されるネットワークスイッチポートフィルタ（２４）であって、
最小項値（Ｍ１−Ｍ８）を記憶するよう構成される最小項メモリ（７０）を含み、各最小項値は、比較のための入来するデータパケット（３２）の対応の選択バイトの位置と、対応の比較動作を指定する表現部分と、対応の最小項を使用するテンプレート（６２）を指定するテンプレート識別子フィールドとに基づいて記憶され、さらに
入来するデータバイトが受けられると瞬時に、入来するデータパケット（３２）のバイトと、受けたバイトに対応する最小項（Ｍ１−Ｍ８）とを比較し、かつそれぞれの最小項比較結果を生成する、最小項生成器（７０）と、
テンプレート（６２）に対する最小項比較結果に基づいて入来するデータパケット（３２）を識別するフレームタグを生成するよう構成される方程式コア（７８）とを含み
方程式コア（７８）は、入来するデータパケット（３２）のワイヤレートで、かつ入来するデータパケット（３２）の終了前に、フレームタグを生成する、ネットワークスイッチポートフィルタ。
【請求項１２】
レイヤ２パケットの種類を識別するよう構成されるフレーム識別子をさらに含み、入来するデータパケット（３２）の選択バイトはレイヤ２パケットの識別された種類に基づいて判断される、請求項１１に記載のフィルタ。
【請求項１３】
各記憶される最小項（Ｍ１−Ｍ８）値の位置は、レイヤ２パケット内のＩＰフレームの開始に関連する、請求項１２に記載のフィルタ。
【請求項１４】
最小項（Ｍ１−Ｍ８）を、入来するデータパケット（３２）内のＩＰフレームの選択バイトに対応する最小項メモリ（７０）からフェッチするよう構成される、最小項コントローラ（７４）をさらに含む、請求項１３に記載のフィルタ。
【請求項１５】
２つ以上のテンプレート（６２）が入来するデータパケット（３２）にマッチングする場合、テンプレート（６２）の優先性を１つの最終的なフレームタグ値に決定するよう構成されるタグ優先性装置をさらに含む、請求項１１、請求項１２、請求項１３、または請求項１４に記載のフィルタ。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００２
【補正方法】変更
【補正の内容】
【０００２】
【背景技術】
ＷＯ−Ａ−９８／３５４８０は、ネットワークノードで入来するデータパケットを処理してデータパケットの種類を判断するための、メディアアクセス制御マイクロ−ＲＩＳＣストリームプロセッサを記載する。プロセッサは、パケットが上層にストリームライン化される前に、データパケットについての情報を含むデータ構造をデータパケットに添付する。マイクロ−ＲＩＳＣストリームプロセッサによって実現される方法は、前掲の請求項１のプリアンブルの特徴を含む。
ローカルエリアネットワークは、ネットワークケーブルまたは他のメディアを用いてネットワーク上のステーションをリンクする。各ローカルエリアネットワークアーキテクチャは、メディアアクセス制御（ＭＡＣ）を用いて各ネットワークノードにおけるネットワークインターフェイス装置がネットワークメディアにアクセスできるようにする。


【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
この発明を、現在最も実際的な好ましい実施例であると考えられる実施例について説明してきたが、この発明は開示される実施例に限定されるものではなく、反対に、さまざまな修正および等価な構成を、前掲の特許請求の範囲に含むことが意図されることを理解されたい。




【国際調査報告】
2004507158.tif 000036
2004507158.tif 000037