(57)【特許請求の範囲】
【請求項１】
半導体基板と、
Ｎ＞１であるものとして、前記基板上で製造されたＮ個の処理ユニットと、
前記Ｎ個の処理ユニットからアクセス可能な情報を保管するための、前記基板上で製造された第１内部データ・メモリと、
前記Ｎ個の処理ユニットの１つとの間で入力情報単位を受け取り、送出するための、前記Ｎ個の処理ユニットに機能的に結合されたディスパッチャと、
前記ディスパッチャに結合されたクラシファイヤ（分類装置）であって、前記クラシファイヤが、比較ユニットを含み、前記比較ユニットが、入力情報単位のデータ・フォーマットを判定するため、および、前記入力情報単位の前記データ・フォーマットおよび前記入力情報単位に係る命令メモリ内における開始アドレスを示す入力情報単位出力インジケータに関する出力インジケータを生成し、前記内部データ・メモリに保管するためのものであり、インジケータおよび前記開始アドレスが、前記入力情報単位の処理中に前記Ｎ個の処理ユニットの前記１つから使用可能であり、前記入力情報単位の前記処理に使用される、クラシファイヤと、
前記半導体基板に担持され、前記Ｎ個の処理ユニットに機能的に結合された、前記Ｎ個の処理ユニットの前記１つによって処理された前記情報単位を受け取る完了ユニットと
を含む装置。
【請求項２】
前記比較ユニットが、前記入力情報データに含まれる仮想ローカル・エリア・ネットワーク・フィールドのテストを含み、前記生成される出力が、前記入力情報単位内の前記仮想ローカル・エリア・ネットワーク・フィールドの存在を識別するインジケータを含む、請求項１に記載の装置。
【請求項３】
前記クラシファイヤが、前記基板内に形成された複数のハードウェア・デバイスを含む、請求項１または２に記載の装置。
【請求項４】
前記出力インジケータが、入力情報単位のタイプおよびそのレイヤ２カプセル化技法を識別するインジケータを含む、請求項１、２、または３に記載の装置。
【請求項５】
前記インジケータが、デフォルト・コード・エントリ・ポイントを含む、請求項１、２、３、または４に記載の装置。
【請求項６】
前記クラシファイヤが、前記クラシファイヤによって判定される入力情報単位の前記タイプおよびそのカプセル化技法に基づいてコード・エントリ・ポイントを判定するシステムを含む、請求項１ないし５のいずれか一項に記載の装置。
【請求項７】
前記クラシファイヤが、デフォルト・コード・エントリ・ポイントおよび入力情報単位の前記タイプに基づくコード・エントリ・ポイントを判定するシステムを含む、請求項１ないし６のいずれか一項に記載の装置。
【請求項８】
前記装置が、さらに、前記デフォルト・コード・エントリ・ポイントおよび入力情報単位の前記タイプに基づく前記コード・エントリ・ポイントから選択するセレクタを含む、請求項７に記載の装置。
【請求項９】
さらに、仮想ローカル・エリア・ネットワーク情報が前記入力情報単位に含まれるかどうかを識別するシステムを含む、請求項８に記載の装置。
【請求項１０】
さらに、前記インジケータが、さらに、前記Ｎ個の処理ユニットのうちで前記入力情報単位が割り当てられた１つの識別を含む、請求項１ないし９のいずれか一項に記載の装置。
【請求項１１】
前記処理された情報単位が受け取られた順序で前記処理された情報単位が前記基板から伝送されることを示すフラグをさらに含み、前記完了ユニットが、処理された情報単位が前記Ｎ個の処理ユニットの１つによって完了される際にそれらをディスパッチするために前記フラグに応答する、請求項１０に記載の装置。
【請求項１２】
前記クラシファイヤが、入力情報単位ごとにそのデータ・フローを示す識別子を生成し、前記内部データ・メモリ内に保管し、同一のデータ・フローからの後の情報単位を前記同一のデータ・フローからの前の情報単位にリンクするシステムを含み、前記プロセッサ内の前記前の情報単位が、特定のデータ・フロー内の第１情報単位として識別され、前記処理ユニットからの情報単位の前記伝送が、前記特定のデータ・フローの前記第１情報単位として識別された情報単位に制限される、請求項１１に記載の装置。
【請求項１３】
前記ディスパッチ・ユニットが、さらに、各情報単位の識別子および前記情報単位が処理のためにディスパッチされた前記処理ユニットの識別を、キューに順次保管し、
前記完了ユニットが、さらに、前記順次キューに結合され、処理された情報単位を前記情報単位が受け取られたのと同一の順序で組み立てるために、前記ディスパッチャによって割り当てられた情報単位のそれぞれの前記識別子および前記情報単位がディスパッチされた前記処理ユニットの前記識別を使用する
請求項１ないし１２のいずれか一項に記載の装置。
【請求項１４】
前記装置が、さらに、前記順序をオーバーライドし、前記情報単位が完了された順序で処理された情報単位を前記ネットワークに転送する信号を含む、請求項１３に記載の装置。
【請求項１５】
入力情報単位を処理する方法であって、
ディスパッチャで前記入力情報単位を受け取るステップと、
前記ディスパッチャから複数のプロセッサの１つへ処理のために前記入力情報単位を送るステップと、
前記情報単位が前記ディスパッチャから前記複数のプロセッサの前記１つに送られつつある間に、前記入力情報単位から選択されたビットを読み取るステップと、
前記入力情報単位のタイプおよびプロトコルを識別するか、前記入力情報単位が入力情報単位のタイプの所定の識別タイプに合致しないことを識別するために、前記入力情報単位から読み取られたビットを、入力情報単位の所定のタイプを識別する既知のインジケータに対してテストするステップと、
前記入力情報単位からのビットの前記テストの結果に基づいて、入力情報単位の前記タイプのインジケータおよびその入力情報単位に関する他の情報を保管するステップと、
複数の処理ユニットの前記１つで、前記入力情報単位の処理において前記保管されたインジケータおよび前記入力情報単位に関する前記他の保管された情報を使用するステップと
を含む方法。
【請求項１６】
前記インジケータを生成し、前記インジケータを保管するステップが、前記入力情報単位が前記複数のプロセッサの１つに送られつつある間に行われ、その結果、前記複数のプロセッサの前記１つが、前記入力情報単位を処理する時に、前記インジケータおよび前記他の情報が、決定され、保管されており、前記複数のプロセッサの前記１つが、前記入力情報単位を処理する際に、その入力情報単位に関する前記インジケータおよび他の情報を使用する、請求項１５に記載の方法。
【請求項１７】
さらに、前記入力情報単位の内容に基づいて、前記入力情報単位のさらなる処理のための命令メモリ内における開始アドレスを生成するステップを含み、前記複数の処理ユニットの前記１つで前記保管されたインジケータを使用する前記ステップが、前記開始アドレスを使用することを含む、請求項１５または１６に記載の方法。
【請求項１８】
読み取り、テストする前記ステップが、ハードウェアで達成される、請求項１５、１６、または１７に記載の方法。
【請求項１９】
入力情報単位に関するテストおよびインジケータの保管の前記ステップが、前記複数の処理ユニットの１つで前記ディスパッチャから前記入力情報単位を受け取る前記ステップとオーバーラップする、請求項１８に記載の方法。
【請求項２０】
前記入力情報単位の識別子を生成し、保管するステップと、
前記識別子に関連して、前記情報単位が割り当てられた前記処理ユニットの識別を保管するステップと、
処理された情報単位をそれらが受け取られた順序で伝送するために、前記識別子および前記情報単位が割り当てられた前記処理ユニットの前記識別を使用するステップと
をさらに含む、請求項１５ないし１９のいずれか一項に記載の方法。
【請求項２１】
さらに、フレームに対するラベルなしフラグを含めることによって、処理ユニットによって生成された前記フレームに応答するステップを含む、請求項２０に記載の方法。
【請求項２２】
前記システムが、前記フレームをそれ以上のストレージなしで前記ネットワークに渡すことによって、ラベルなしフラグを有するフレームに応答する、請求項２１に記載の方法。
【請求項２３】
さまざまなプロトコルおよびカプセル化を有する情報のフレームを分析し、そのフレームを処理するための開始位置およびそのフレームを処理するための初期命令へのポインタを提供する装置であって、
前記フレームの所定のバイトを調べ、これらのバイトが長さまたはプロトコルを示すかどうかを判定する比較器と、
前記フレームのプロトコルおよびカプセル化システムを判定する論理と、
前記フレームの処理の開始位置および前記フレームを処理するための初期命令へのポインタを判定する論理と、
を含む装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、さまざまなタイプおよび能力を有する情報処理システムまたはコンピュータを一緒にリンクするために使用されるものなど通信ネットワーク装置と、そのような装置でデータ処理するためのコンポーネントおよび方法に関する。具体的には、本発明は、複数の独立のプロセッサによって同時に処理することができ、入力情報単位がさまざまな異なるプロトコルの１つを有することができる、複数の入力情報単位（「パケット（packet）」または「フレーム（frame）」とも称する）を処理する方法およびシステムを含む、データ伝送ネットワークに結合された処理装置内でのデータの流れを管理する改良されたシステムおよび方法に関する。
【０００２】
【従来の技術】
本発明は、以下の文書に関連し、これらのすべてが、本発明の譲受人に譲渡されている。
本明細書でネットワーク処理装置特許またはＮＰＵ特許と呼称する、米国特許出願第０９／３８４６９１号。
インターフェース特許とも呼ばれる、米国特許第５７２４３４８号。
リンク特許とも呼ばれる米国特許出願第０９／３３０９６８号。
「ＭＳＳ」とも呼ばれるマルチプロトコル・スイッチング・サービス（multiprotocol switching service）に関する、そのうちのいくつかで発明人としてCedric Alexanderが含まれる、ＭＳＳ特許とも呼ばれる、ＩＢＭ社に譲渡されたさまざまな特許および特許出願。
【０００３】
以下の本発明の実施形態の説明は、読者がネットワーク・データ通信と、そのようなネットワーク通信に有用なルータ（router）およびスイッチの基本知識を有するという前提に基づく。具体的に言うと、この説明では、ネットワーク動作を層に分割するネットワーク・アーキテクチャの国際標準化機構（ＩＳＯ）モデルに精通していることが前提になっている。ＩＳＯモデルに基づく典型的なアーキテクチャは、信号が上に渡される物理パスまたは物理媒体であるレイヤ１（「Ｌ１」とも称する）から、レイヤ２（または「Ｌ２」）、３（または「Ｌ３」）などを介して、ネットワークにリンクされたコンピュータ・システム内に常駐するアプリケーション・プログラミングの層であるレイヤ７（または「Ｌ７」）まで延びる。この文書全体を通じて、Ｌ１、Ｌ２、Ｌ３などのレイヤに対する言及は、ネットワーク・アーキテクチャの対応するレイヤを指すことが意図されている。この説明は、ネットワーク通信に使用される、パケットまたはフレームと称するビット・ストリングの基本的な理解も前提とする。
【０００４】
帯域幅（bandwidth）の考慮事項（または、１単位の時間でシステムが処理できるデータの量）が、現在のネットワーク動作に関してますます重要になりつつある。ネットワーク・トラフィックは、主にインターネット（ワールド・ワイド・ウェブとも称する疎にリンクされたコンピュータの公衆ネットワーク）の爆発的成長と、より少ない範囲ではあるが、私的データ伝送ネットワークまたはイントラネットの人気の高まりとによって推進されて、最近劇的に増加した。インターネットおよびイントラネットには、情報および新しいアプリケーションへのリモート・アクセスの常に増加する必要を満足するためにリモート・ロケーション間での大量の情報の伝送が含まれる。インターネットは、地理的に分散した地域の多数のユーザが爆発的な量のリモート情報を利用できるようにし、e-commerceなどのさまざまな新しいアプリケーションを可能にし、その結果、ネットワークの負荷が増加し、常に増加し続けている。電子メール、ファイル転送、およびデータベース・アクセスなどの他のアプリケーションが、さらに、ネットワークに負荷を追加し、その一部は、高レベルのネットワーク・トラフィックに起因して、すでに酷使されている。
【０００５】
ネットワーク上のトラフィックは、ますます多様にもなりつつある。かつては、一部のネットワークが、電話網上の音声およびデータ伝送ネットワーク上のディジタル・データなど、主にあるタイプの通信トラフィックに使用された。もちろん、音声信号のほかに、電話網は、限られた量の「データ」（ルーティングおよび請求のための発呼番号、被呼番号など）も搬送したが、一部のネットワークの主な用途は、ある時点で、実質的に同種類のパケットであった。
【０００６】
しかし、現在、音声トラフィックおよびデータ・トラフィックが、同一のネットワークにますます集束しつつある。インターネットの膨張が続き、信頼性およびセキュリティなどの領域で技術が改善されるにつれて、音声およびデータなどの異なるタイプの情報の混合物を含む多数の異なる種類の情報を相対的に同時に伝送する機会が提示された。
【０００７】
データは、現在、インターネット上で（インターネット・プロトコルまたはＩＰを介して）無料で伝送され、音声トラフィックは、通常、最低のコストのパスに従う。voice over IP（ＶｏＩＰ）およびvoice over asynchronous transfer modeまたはATM（ＶｏＡＴＭ）またはvoice over frame relay（ＶｏＦＲ）などの技術が、現在の環境での音声トラフィックの伝送に関するコスト効率のよい代替物である。これらのサービスに移行する際に、産業界は、変化するコスト構造と、プロセッサ間の情報の伝送におけるサービスのコストとサービス品質（quality of service）の間のトレード・オフなどの問題に関する関心事に対処する。
【０００８】
サービス品質の諸態様に、容量または帯域幅、応答時間（１フレームを処理するのにかかる時間）、および処理の柔軟性（異なるカプセル化（encapsulation）方法またはフレーム・ヘッダ方法などの異なるプロトコルおよびフレーム構成に応答するかどうか）が含まれる。リソースを使用する側は、提示される情況に依存するトレードオフを伴う、サービス品質ならびにサービスのコストを考慮する。
【０００９】
データ・パケットをルーティングするいくつかの従来技術のシステムは、パケットが、単一プロトコルまたは単一フォーマットであるか、限られた数の許容されるプロトコルまたはフォーマットの１つであることを必要とする。そのようなシステムは、許容されるプロトコルに合わせてシステムを調整することができるので、１つのタイプのプロトコル（または限られた数のプロトコル）だけのパケットがシステム内に見られる時の設計の相対的な単純さのゆえに、高められた速度および応答性という長所を有する。データ伝送システム全体が、単一のエンティティの制御下にあった時には、制御するエンティティがユーザに単一の標準伝送プロトコルを強制することが簡単であった（ユーザが、許容されるプロトコルに従うか、ネットワークを使用しないのいずれかになった。というのは、ネットワークが、指定されたプロトコルだけに適応するようにプログラムされ、些細な変動に見える場合であっても、プロトコルの変動を処理できなかったからである）。
【００１０】
しかし、イーサネット（Ethernet）（登録商標）などの通信「標準規格」からのフレームでさえ、複数のプロトコルの１つを使用してフォーマットすることができ、異なるカプセル化技法を使用してメッセージにカプセル化することができる。これらの異なるプロトコルおよびカプセル化技法は、通常はフレームの先頭と、Ｌ３メッセージの先頭などの他のキー情報の前に、変化する量のデータをもたらす。したがって、イーサネット・フレームからのキー情報は、イーサネットＬ３プロトコルまたは、存在する場合にイーサネットおよびカプセル化技法の形態に応じて、フレーム内の異なる場所に配置される可能性がある。Ｌ３メッセージの処理を提供するシステムは、まずそれを見つける必要があり、それが、マルチプロトコル・システムの課題になる可能性がある。したがって、たとえば、Ethernet DIX Version 2は、Ethernet 802.3と異なり、IPX over Ethernetは、IPX over Ethernet 802.3と異なり、IPX over Ethernet 802.3自体は、３つの異なるフォーマット（Novell独自、ＬＬＣ、およびＳＮＡＰ）を有する。さらに、ＩＰＸの各バージョンは、いわゆるIEEE 802.1q標準規格を使用する仮想ＬＡＮ（またはＶＬＡＮ）をサポートする場合とそうでない場合があり、IEEE 802.1q標準規格も、フレームのフォーマットを変更し、したがってＬ３メッセージの位置を変更するという影響を有する。
【００１１】
多数のプロトコルのフレームがサポートされる、これらの従来技術のシステムでは、時には、プロトコルを識別し、フレームをあるプロトコルから別のプロトコルに変換するか、フレームから不要な情報（カプセル化情報など）を除去するために、かなりの量のオーバーヘッド（時には比較命令と分岐命令を伴う百行を超えるコードを含むコンピュータ・プログラミングなど）を設ける必要があった。そのような複数プロトコル処理は、時間がかかり、さらに、しばしば、プロトコルを識別するのに変化する長さの時間を要した。そのようなシステムが、プロトコルを識別し、必要な処理を提供するのに変化する長さの時間を必要とする時に、システムは、必要な（ワースト・ケースを処理するために）最長の時間を許容するように構成されなければならず、すべてのフレームの処理がワースト・ケースまで遅くなるか、一部のフレームが、カテゴリー化に許容される時間のうちに処理されない可能性が生じた。
【００１２】
ほとんどのプロセッサは、命令セットの共通の先頭（すべてのデータについて同一の場所）から処理を開始し、どこに行ってどの命令を実行するかを決定する必要がある時にプロセッサが選択的に読み取るフラグをセットする。したがって、多くのプロセッサの実行では、そのプロセッサがどの種類のデータを有し、本質的な処理をどこから開始するかを決定するために多数のテストが実行され、これらのテストには、多数のサイクルが伴い、大量の処理が伴う可能性がある。
【００１３】
データの厳格な先入れ先出し処理を使用する、データを処理するためのマルチプロセッサ・システムが、従来技術で既知である。これは、処理が型にはまった形で発生する時によく機能するが、そのようなシステムは、１つの入力の処理が遅れた時に、束縛され、機能を停止する。１つの入力の処理の遅れが、他の処理の停止という影響を有する。
【００１４】
処理中に入力メッセージ単位を記憶する、他の従来技術のシステムが既知である。これらのシステムは、各情報単位がシステム内のどこにあるかを記憶するために、かなりの量の処理能力を振り向けなければならないという制限および短所を有し、いくつかのシステムは、新しいデータ・フローまたは内部的に生成されるメッセージなどからの、追加の入力情報単位に対応しない。
【００１５】
したがって、データ・パケットを処理する従来技術のシステムは、システムの適応性またはシステムが動作できる速度のいずれかもしくはその両方に影響する、望ましくない短所および制限を有した。従来技術のシステムの他の短所および制限は、本発明の以下の説明に鑑みて、当業者に明白になるであろう。
【００１６】
【発明が解決しようとする課題】
本発明の目的は、データ処理用のシステムでのフレーム・プロトコル分類および処理（たとえばデータ・パケットまたはフレームのスイッチングまたはルーティング）のシステムおよび方法を提供することである。
【００１７】
【課題を解決するための手段】
本発明のこの実施形態は、複数の異なる許容されるメッセージ・プロトコルの１つを使用して作成され、仮想ローカル・エリア・ネットワーク（またはＶＬＡＮ）システムを使用してもしなくてもよい、フレームまたはパケットのネットワークを介するデータ・フローを管理する、単純でありながら効率的な方法を提供することによって、従来技術のシステムの短所および制限を克服する。各パケットまたはフレームを素早く効率的な形で分析することによって、フレームのタイプおよびフレームのキー特性を、判定でき、たとえば上で参照したＮＰＵ特許に記載されたタイプのネットワーク・プロセッサ内での、そのフレームに関する将来の参照および処理のために保管することができる。
【００１８】
異なるプロトコルを有するパケットの処理において素早く効率的であり、パケットのより高速で簡単な処理を提供し、システム全体がフレーム処理の高い速度で動作できるようにすることが、この実施形態の長所である。
【００１９】
この実施形態は、ルータまたはスイッチが、特定のフレームまたはパケットがどのフォーマットで作成されたかを前もって知ることなく、変化するフォーマットの連続するパケットまたはフレームを処理できるようにする。この実施形態には、メッセージまたはパケットのレイヤ２（Ｌ２）カプセル化フォーマットを識別することと、その後、Ｌ２カプセル化と、Ｌ３プロトコルと、仮想ローカル・エリア・ネットワーク（ＶＬＡＮ）の存在とを識別するために、保管された規則を適用することが含まれる。そのような判定の結果として、プロセッサが、開始命令アドレスで実行する準備ができる。すなわち、プロセッサは、フレームの識別に基づく命令の開始アドレスを用いて事前条件付け（precondition）される。したがって、プロセッサは、開始命令アドレス、ならびにフレームのデータ部分内のＬ３ヘッダの先頭へのポインタ、ならびにプロトコル、ＶＬＡＮ存在、およびカプセル化フォーマットを示すフラグを有する。
【００２０】
この実施形態は、パケットの初期処理中にパケットに関するキー情報をセット・アップし、保管し、その後、パケットまたはフレームに関する保管された情報を、後に有利に処理に使用することができ、たとえばＮＰＵ特許に記載のネットワーク処理ユニット複合体による、後のステージでのパケットのより素早く効率的な処理が可能になるという長所を有する。
【００２１】
この実施形態は、単一のデータ・フローからの入力パケットまたはフレームを、処理のために複数の独立のプロセッサの１つに割り当てることができ、その後、出力される（処理された）パケットまたはフレームを、入力パケットまたはフレームが受け取られたのと同一の順序に再組立することができるという長所を有する。
【００２２】
この実施形態は、複数のデータ・フローを、お互いに影響せずに処理でき、あるデータ・フローが他のデータ・フローをブロックしないという長所を有する。すなわち、あるデータ・フローの処理が、その一部の処理の完了を待って一時停止された時に、他のデータ・フローの処理を継続することができる。
【００２３】
この実施形態では、望むならば、受け取った順序で各データ・フローを処理するという通常動作をオーバーライドして、順序に無関係に、システムをフラッシュするか完了したフレームを即座にディスパッチすることもできる。
【００２４】
この実施形態は、バッファおよびストレージ・デバイスの使用において効率的であり、素早く動作し、その結果、処理の速度が、データ・フロー管理のオーバーヘッドによって遅くならないという長所も有する。
【００２５】
この実施形態では、この実施形態をネットワーク・プロセッサのアレイおよびそれに関連するストレージ・コンポーネントとして同一の半導体基板上で実施でき、コンポーネント間の高速データ伝送を可能にすることが企図されている。
【００２６】
この実施形態は、ソフトウェアではなくハードウェアで実施することもでき、必要なフォーマット・テストを、フォーマットに無関係に、フォーマットまたはカプセル化技法を判定する前に行わなければならない比較の数に無関係に、均一の時間で完了することができる。示される設計では、２クロック・サイクル以内に、どの種類のフレームが存在するか（たとえば、どのカプセル化技法とどのレイヤ３プロトコルが使用されたか）と、仮想ＬＡＮ（またはＶＬＡＮ）がサポートされるかどうか、ならびにフレームに関するキー情報を示すように必要なインジケータをセットして、フレームの分類を完了することができる。同一の２サイクル中に、フレームを、ディスパッチャによってアイドルのネットワーク処理ユニットにルーティングすることができる（上で参照したＮＰＵ特許に記載のように）。プロトコルおよびカプセル化方法を判定するためのフレームの処理の結果として、プロセッサの開始アドレスを判定し、プロセッサに渡すことができ、その結果、プロセッサが、開始アドレス（関連する命令ストレージへのポインタ）およびその処理に関する他の関連情報をプリロードされて、フレームに対する作業を開始できるようになる。この処理に関する開始アドレスのプロセッサへのプリロードを、時々、プロセッサの事前条件付けと称し、これによってプロセッサ効率が可能にされる、すなわち、多数のテスト命令およびテストの結果に基づくジャンプ命令を全部実行する必要がなく、その代わりに、提示されたメッセージの特定のフォーマット用の開始アドレスから開始する。
【００２７】
この実施形態のシステムは、フレームの分類および前処理を、ネットワーク処理複合体へのそのフレームの分配と並列に行えるという長所も有する。この並列処理によって、フレームのより効率的な処理が可能になり、システムがより高速に動作できるようになる。
【００２８】
この実施形態の使用を介して、複数の処理ユニットを、互いに独立とすることができ、なおかつ、これらの処理ユニットが、諸部分を異なる望ましくない順序にさせずに同一のデータ・フローを処理することができる。所与のデータ・フローの処理されたパケットまたはフレームの出力は、フラッシュ・コマンドによってオーバーライドされない限り、システムがそのデータ・フローから入力パケットまたはフレームを受け取ったのと同一の順序になる。
【００２９】
最後に、この実施形態を用いると、ネットワークから受け取るデータ・フローの順序を維持する処理に影響せずに、システムによる新しいデータ・フローの挿入およびパケットまたはフレームの作成が可能になる。
【００３０】
この実施形態の１つの機能強化を用いると、プロセッサの事前条件付け（第１命令のアドレスの保管）だけではなく、後の実行のために命令の追加アドレスを保管することも可能になる。この形で、プロセッサは、第１命令のアドレスと、後の分岐（またはｆｏｒｋ）点の命令のアドレスを有し、コードの実行中の不要なテスト（ｉｆ  条件、ｔｈｅｎ  ｇｏ  ｔｏ  命令＃１  ｏｔｈｅｒｗｉｓｅ  ｇｏ  ｔｏ  命令＃２）が回避される。これによって、コードをより効率的に実行できるようになる。
【００３１】
この実施形態の他の目的および長所は、添付図面および請求項とあわせた好ましい実施形態の以下の説明に鑑みて、当業者に明白になる。
【００３２】
従来技術の制限および短所の一部と、本発明の目的および長所の一部を示したが、他の目的および長所は、改良されたルーティングのシステムおよび方法という本発明を示す図面の以下の説明に鑑みて、当業者に明白になる。
【００３３】
【発明の実施の形態】
以下の好ましい実施形態の説明では、発明者に現在既知の本発明の実践の最善の実施形態を、ある程度具体的に説明する。しかし、特に、当業者が、これらの図面に図示され、図面に関して説明される特定の構造および動作に対する多数の変形形態および変更を認識するので、この説明は、特定の実施形態での本発明の概念の広義の一般的な教示として意図されており、本発明をこの実施形態に示されたものに制限することを意図されてはいない。
【００３４】
図１は、パケットまたは情報単位（時には、本明細書において交換可能に使用される用語であるフレームとも称する）の形でデータを受け取り、処理し、ネットワークに再送出するデータ伝送ネットワークへの取付けに適する処理システムの機能ブロック図である。図１からわかるように、このデータ処理用のシステムには、複数のサブアセンブリが含まれ、これらのサブアセンブリは、ＮＰＵ特許に記載されているように、単一の基板に有利に集積することができる。アセンブリ全体の単一の基板への集積によって、システムのさまざまなコンポーネントのより密なパッキングと、コンポーネント間の通信に必要な時間の短縮と、したがってシステムが動作できる速度の向上が可能になる。複数のプロセッサとサポートする論理およびメモリに関する単一基板の使用は、相互接続に起因する障害の発生を減らし、ネットワーク内のデータ伝送を破壊する可能性があるノイズまたは他の漂遊信号に対する抵抗を増やすこともできる。
【００３５】
基板１０に取り付けられたサブアセンブリは、上側（upside）構成および下側（downside）構成に配置され、「上側」構成（時々「入（ingress）」とも称する）は、データ伝送ネットワークからチップへのインバウンドな（チップまでまたはチップ内へ）データに関するコンポーネントを指し、「下側」（時々「出（egress）」とも称する）は、その機能がチップからデータ伝送ネットワークに向かってアウトバウンドの形で（チップから出るかネットワークに入る）データを送出することであるコンポーネントを指す。データ・フローは、上側構成および下側構成のめいめいの配置に従う。したがって、図１のシステムに、上側データ・フローと下側データ・フローがある。上側または入の構成エレメントには、エンキュー−デキュー−スケジューリング（Enqueue-Dequeue-Scheduling）ＵＰ（ＥＤＳ−ＵＰ）論理１６、複数の多重化されたＭＡＣのＵＰ（ＰＭＭ−ＵＰ）１４、スイッチ・データ・ムーバ（Switch Data Mover）−ＵＰ（ＳＤＭ−ＵＰ）１８、システム・インターフェース（ＳＩＦ）２０、データ位置合せ直列リンク（Data Align Serial Link）Ａ（ＤＡＳＬ−Ａ）２２、およびデータ位置合せ直列リンクＢ（ＤＡＳＬ−Ｂ）２４が含まれる。データ・リンクは、上で参照したリンク特許に詳細に記載されており、システムのこの部分のよりよい理解のためにその文書を参照されたい。本発明の好ましい実施形態では、その特許に詳細に記載されたデータ・リンクを使用するが、本発明が、好ましい実施形態に使用されるデータ・リンクなどの特定の補助デバイスに制限されないので、特に比較的高いデータ・フローおよびシステム要件をサポートするものなどの他のシステムを、本発明と共に有利に使用することができることを理解されたい。
【００３６】
システムの下側（出）に描かれたコンポーネントには、データ・リンクＤＡＳＬ−Ａ２６およびＤＡＳＬ−Ｂ２８と、システム・インターフェースＳＩＦ３０と、スイッチ・データ・ムーバＳＤＭ−ＤＮ３２と、エンキュー−デキュー−スケジューラＥＤＳ−ＤＮ３４と、出の複数の多重化されたＭＡＣ  ＰＭＭ−ＤＮ３６が含まれる。基板１０には、上で参照したＮＰＵ特許に詳細に記載されている、複数の内部スタティック・ランダム・アクセス・メモリ（static random access memory）コンポーネント（Ｓ−ＲＡＭ）と、トラフィック管理スケジューラ（TRAFFIC MGT SCHEDULER）４０と、組み込みプロセッサ複合体（embedded processor complex）１２も含まれる。インターフェース・デバイス３８が、めいめいのＤＭＵバスによってＰＭＭ１４および３６に結合される。インターフェース・デバイス３８は、この両方が周知であり一般にこの目的で商業的に入手可能であるデバイスの例である、イーサネット物理（ＥＮＥＴ  ＰＨＹ）デバイスまたは非同期転送モード（asynchronous transfer mode）フレーミング機器（ＡＴＭ  ＦＲＡＭＥＲ）などのＬ１回路に接続するのに適当な装置とすることができる。インターフェース・デバイスのタイプおよびサイズは、少なくとも部分的に、このチップおよびそのシステムが接続されるネットワーク媒体によって決定される。複数の外部ダイナミック・ランダム・アクセス・メモリ（dynamic random access memory）デバイス（Ｄ−ＲＡＭ）およびＳ−ＲＡＭが、チップによる使用のために使用可能である。
【００３７】
本明細書では、関連するスイッチング・デバイスおよびルーティング・デバイスの外部の一般的なデータ・フローが、建物の中に設置されたワイヤおよびケーブルなどの電気導体を介して渡される、ネットワークについて具体的に開示されるが、本発明では、ネットワーク・スイッチおよびそのコンポーネントを、無線環境でも使用できることが企図されている。たとえば、本明細書で開示されるメディア・アクセス制御（media access control、ＭＡＣ）要素を、シリコン・ゲルマニウム技術から作られるものなどの、開示されるデバイスの無線ネットワークへの直接接続をもたらす適当なラジオ周波数デバイスによって置換することができる。そのような技術が適当に使用される場合に、当業者が、そのラジオ周波数要素を、本明細書に開示されたＶＬＳＩ構造に集積することができる。その代わりに、赤外線（ＩＲ）応答デバイスなどのラジオ周波数または他の無線応答デバイスを、本明細書に開示された他の要素と共にブレード（blade）に取り付けて、無線ネットワーク装置に関して有用なスイッチ装置を達成することができる。
【００３８】
矢印は、図１に示されたインターフェース・システム内でのデータの一般的なフローを示す。ＥＮＥＴ  ＰＨＹブロック３８からＤＭＵバスを介してイーサネットＭＡＣ１４から受け取られたデータのフレームまたはメッセージは、ＥＤＳ−ＵＰデバイス１６によって内部データ・ストア・バッファ１６ａに置かれる。フレームを、通常のフレームまたは案内されるフレーム（guided frame）のいずれかとして識別することができ、これが、複数のプロセッサ内での後続処理の方法および位置に関係する。
【００３９】
図２は、本発明を有利に使用することができる処理システム１００のブロック図である。この図２では、複数の処理ユニット１１０が、ディスパッチャ（dispatcher）ユニット１１２および完了（completion）ユニット１１４の間に配置される。各着信（incoming）フレームＦ（このデータ処理システムに接続された、図示されていないネットワークからの）が、受け取られ、ＵＰデータ・ストア１１６に保管され、ＵＰデータ・ストア１１６は、インターフェースＵＰ  ＤＳ  ｉ／ｆ１１７を介して処理ユニット１１０に接続され、インターフェースＵＰ  ＤＳ  ｉ／ｆ１１７は、データを読み取り、データ・ストアに書き込む能力を有する。フレームは、ディスパッチャ１１２によって順次除去され、処理ユニットがフレームの処理に使用可能であるというディスパッチャ１１２による判定に基づいて、複数の処理ユニット１１０の１つに割り当てられる。この表示は、フレームＦが割り当てられる１つの処理ユニットが、その特定の処理ユニットがアイドルであり、作業に使用可能であることを示す信号をディスパッチャ１１２に送ったこととすることができるが、作業を割り当てる代替の方法（ラウンドロビン割振りまたはＬＲＵ（least recently used）アルゴリズムなど）を、本システムで有利に使用することもできる。具体的には処理ユニット１１０、一般的には処理システムの構造および機能に関する詳細は、上で参照したＮＰＵ特許にある。ディスパッチャ１１２と複数の処理ユニット１１０の間に入れられているのが、ハードウェア・クラシファイヤ補助機構（hardware classifier assist）１１８であり、これについては、後にこの文書で、特に図２３および２４に関して詳細に説明する。やはり複数の処理ユニット１１０に関連するのが、命令ストレージ１２２（図２３に図示）であり、ここに、複数の異なる命令セットが、個々の処理ユニット１１０による取出および実行のために保管される。後で説明するように、命令ストレージ１２２内の開始命令は、ハードウェア・クラシファイヤ補助機構１１８によって決定される、メッセージのタイプ（そのプロトコルおよびカプセル化方法）に基づくアドレスに従ってアドレッシングされる。
【００４０】
完了ユニット１１４は、機能的に、複数のプロセッサ１１０と、下エンキュー・システム（符号DN Enqueue、図１の要素３４）ならびにＵＰエンキュー・システム（図１の要素１６）の間に結合される。DN Enqueueシステム３４は、処理されたフレームを、処理複合体からその処理複合体が接続されたネットワークまたは他のシステムへ送るのに使用され、ＵＰエンキュー・システム１６は、処理されたフレームをスイッチ・ファブリックに送るのに使用される。各フレームおよびそのフレームを処理するために割り当てられた処理ユニットに関連する識別情報を割り当て、保管するように、ディスパッチャ１１２を設計することができる。そのような識別情報を、その後、完了ユニット１１４によって使用して、単一のデータ・フローを構成する処理されたフレームが、受け取られた順序で転送されることを保証することができる。本発明のこの態様は、後にこの明細書で詳細に説明する。
【００４１】
図３から２２に、この処理システムが受け入れ、処理するようにプログラムされる複数のメッセージ・フォーマット（コンポーネントおよびイーサネット・メッセージ・フォーマットに対する変形形態）を示すが、メッセージまたはフレーム・フォーマットの範囲は、検討中のシステムの環境に合わせるために当業者が変更できるものである。このシステムは、将来に設計されるメッセージ・フォーマットおよび変形形態を含む、他のメッセージ・フォーマットを受け入れるように再設計することもできる。したがって、図３のメッセージ・フォーマットは、異なるプロトコルおよびカプセル化タイプを有するフレームの異なるフォーマットを例示する目的のものであり、本発明は、さまざまな異なるプロトコルおよびカプセル化フォーマットを受け入れ、カプセル化およびプロトコルのタイプへのポインタを提供することによってこれらのフレームの処理に対する補助機構を提供し、所与のフレームを処理するプロセッサに命令ストレージ内の開始アドレスを提供するように設計された柔軟なシステムである。
【００４２】
図３に、時々Ethernet Version 2.0/DIXと呼ばれる包括的なまたは基本的なイーサネット・メッセージ・フォーマットを示す。これは、メッセージに、宛先アドレス（destination address）ＤＡ、ソース・アドレス（source address）ＳＡ、メッセージのタイプを示すブロック（Type）、メッセージ・テキストまたはデータ、およびメッセージ保全性検証用の巡回冗長検査（cyclical redundancy checking）またはＣＲＣのトレーラ（trailer）が含まれる、メッセージ・フォーマットである。宛先アドレスＤＡおよびソース・アドレスＳＡの両方が、６バイト（４８ビット）として指定され、Typeを示すブロックが、２バイトとして指定され、ＣＲＣトレーラは、４バイトとして指定される。一般に、メッセージの残り（Data）は、１５００バイトまでの任意の長さとすることができるが、後でわかるように、いくつかのタイプのイーサネットで、他の長所を達成するためにこの柔軟性に対する制限が設けられている。ソース・アドレスＳＡは、メッセージが、ネットワーク上の１ノードの単一のネットワーク・アドレスに宛てられた個別のメッセージであること、もしくは、メッセージがマルチキャスト・メッセージまたはブロードキャスト・メッセージであること、のいずれかを示すことができる。マルチキャスト・メッセージは、ネットワーク上のノードのグループに向けられ、ブロードキャストは、すべてのステーションに向けられる。Typeを示すブロックは、１６ビットであり、これによって、使用される上位層プロトコルが識別される。登録されたイーサネット・プロトコルのそれぞれに、一意のタイプ・コードが与えられ、このタイプ・コードの値は、必ず、諸フィールドが共存できるようにするために、Ethernet 802.3 lengthフィールドの長さフィールドの最大値より大きい。データ・フィールドは、通常は、データをＭＡＣ層に渡す前に４６バイトの最小フィールド長さが満たされることを上位層が保証すると仮定して、４６から１５００バイトの長さである。フレームの許容される長さより長いメッセージは、データ・フィールドの最大の許容される長さより短い複数のメッセージに分割されなければならない。
【００４３】
図４に、IEEE 802.3 Ethernetフォーマットと称する、一般的なイーサネット・スタイルに対する変形形態を示す。これは、図１の包括的なイーサネット・メッセージ・フォーマットのフォーマットに類似しているが、タイプ・フィールドが、長さフィールドＬＥＮに置換されていることが異なり、この長さフィールドＬＥＮは、すべての埋込み（pad）を除く、それに続くデータ・フィールドの長さを示す１６ビットである。この標準規格では、パケットの最小サイズ長さが６４バイトとして強制され、したがって、データ・フィールドDataが、少なくとも４６バイトでなければならない。データ・フィールドDataの実際のデータが４６バイト未満の場合には、ＭＡＣ層が、パケットをネットワークに送る前に、プレース・セーバ（place saver）（埋込み文字）をＬＬＣデータ・フィールドに追加して、最小サイズにしなければならない。しかし、長さフィールドは、埋込み文字を含まない長さであり、これによって、受取り側システムが、追加された埋込み文字を識別し、破棄することができるようになっている。
【００４４】
図５に、特にＩＥＥＥ標準規格８０２．１ｑに関する、イーサネット・メッセージのTag Control Information Formatを示す。これには、３ビットのユーザ優先順位（user priority）、１ビットのCanonical Format IndicatorまたはＣＦＩ、および１２ビットのＶＩＤまたは仮想ＬＡＮ（またはＶＬＡＮ）識別子からなる。仮想ＬＡＮまたは仮想ローカル・エリア・ネットワークは、ＶＬＡＮを構成するものとしてアドレスを定義することによって仮想ローカル・エリア・ネットワークとして識別されたノードのグループの識別であり、これによって、物理的に関連しないノードを論理的に関連付け、個別にではなくグループとしてアドレッシングできるようになる。
【００４５】
図６に、やはりＩＥＥＥ標準規格８０２．１ｑに従う、いくつかのイーサネット・プロトコル・メッセージ・フォーマットで使用されるEmbedded RIF（またはＥ−ＲＩＦ）フォーマットを示す。このフォーマットでは、ルート・タイプＲＴが、最初の３ビットによって示され、長さＬＴＨが、次の５ビットによって示され（Ｅ−ＲＩＦルート制御およびE-RIF Route Descriptorを含むＥ−ＲＩＦ部分全体のバイト単位の長さを示す）、ルート記述子方向Ｄが、１ビットによって示される（通常は、ルート記述子を順方向にトラバースすることを示す「０」であるが、特別な形でルーティングされるフレームの場合に、ルート記述子が逆順であることを示すために「１」になる）。Ｅ−ＲＩＦフォーマットには、６ビットの最長フレーム・インジケータおよび１ビットのNon Canonical Format Indicator（ＮＣＦＩ）が含まれる。ルート・タイプＲＴは、フレームが、特別にルーティングされるフレーム（specially routed frame）、透過的フレーム（transparent frame）、全ルート・エクスプローラ・フレーム（all route explorer frame）、またはスパニング・ツリー・エクスプローラ・フレーム（spanning tree explorer frame）のどれであるかを示すために、それぞれ００Ｘ、０１Ｘ、１０Ｘ、または１１Ｘのいずれかになる。最長フレームＬＦフィールドは、IEEE 802.3 Standard for Ethernetによれば、１４７０バイト以下である。ＮＣＦＩは、指定されたＭＡＣアドレスが、非正規形式（non-canonical form）（０の場合）と正規形式（canonical form）（１の場合）のいずれであるかを示す。
【００４６】
図７に、１２ビットのローカル・エリア・ネットワーク識別子ＬＡＮ  ＩＤと４ビットのブリッジ番号（Bridge#）を含むものとしてE-RIF Route Descriptor Formatを示す。E-RIF Route Descriptor Formatフィールドは、当業界で周知でもあり、これの使用法は、そのようなフィールドに関する標準規格に従う。
【００４７】
図８および図９に、図８の８０２．２  ＬＰＤＵフォーマットおよび図９のGeneric SNAPフォーマットを含む、イーサネット・メッセージで使用されるＬＬＣフォーマットのコンポーネントを示す。図８のＬＰＤＵフォーマットには、１バイトのDestination Service Access Point  ＤＳＡＰ（８ビット）と、１バイトのSource service access point  ＳＳＡＰと、コマンド、応答、シーケンス番号、およびポーリング／最終ビット（poll/final bit）を含む１から２バイトの制御フィールドControlが含まれる。これに関して、サービス・アクセス・ポイントは、６ビットと、１つのＵビットと、最終ビット（宛先サービス・アクセス・ポイントの場合に個々のＩビット、ソースの場合にコマンド／応答インジケータのＣビット）である。図９に、組織を示す３バイト（Organizationally Unique IdentifierまたはＯＵＩ）と、Internet Standard 0002の下でフォーマットに割り当てられたタイプを識別する２バイトを含む、ＳＮＡＰフォーマットを示す。このタイプ・フィールドの例が、ＩＰの０８００、ＩＰＸの８１３７、ＡＲＰの０８０６、ＲＡＲＰの８０３５、８０２．１ｑ  ＶＬＡＮの８１００、ＩＰｖ６の８６ＤＤ、Appletalkの８０ＤＢ、およびAppletalk AARPの８０Ｆ３である。
【００４８】
図１０に、イーサネットＭＡＣヘッダおよびＩＰＸヘッダを含み、イーサネットＭＡＣヘッダがそれぞれ６バイトのソース・アドレスＳＡおよび宛先アドレスＤＡを有し、その後にこのフレームがＩＰＸフォーマットであることを示す８１３７の２バイト・タイプが続く、IPX over Ethernetフォーマットのメッセージのフォーマットを示す。その後のＩＰＸヘッダに、図示のコンポーネントすなわち、チェック・サムの２バイト、パケット長の２バイト、ＴＣの１バイト、ＰＴの１バイト、宛先ネットワークの４バイト、宛先ノードの６バイト、宛先ソケットの２バイト、ソース・ネットワークの４バイト、ソース・ノードの６バイト、およびソース・ソケットの２バイトが含まれる。
【００４９】
図１１に、メッセージの長さが第３フィールドで指定される（図１０に示されたIPX over Ethernetのタイプではなく）Ethernet 802.3 MACヘッダを含むEthernet 802.3の独自版の上でのＩＰＸ（時々Novellフォーマットと称する）のメッセージ・フォーマットを示す。このフォーマットのチェック・サムには、そのプロトコルに従って「ＦＦＦＦ」がセットされる。
【００５０】
図１２に、メッセージに、８０２．２のＬＬＣ  ＬＰＤＵフィールドによって分離されたＭＡＣヘッダおよびＩＰＸヘッダ（図１０に示されたものに似る）が含まれる、IPX over Ethernet 802.3 with 802.2を示す。
【００５１】
図１３に、図１２に関して説明したフォーマットに似て、メッセージに８０２．３  ＭＡＣヘッダが含まれ、その後にＬＬＣ  ＬＰＤＵフィールドが続き、ＩＰＸヘッダで終わる、IPX frame over 802.3 with SNAPのフォーマットを示す。ＬＬＣ  ＬＰＤＵ部分とＩＰＸヘッダの間に、ＯＵＩおよび８１３７のEtypeを示すＳＮＡＰフィールドが配置されている。
【００５２】
図１４に、タイプ・フィールドが８１００として示され、ＶＬＡＮパケットがイーサネットＭＡＣヘッダとＩＰＸヘッダの間に配置される（ＩＰＸヘッダは、図１０、１２、および１３に関して上で説明したものと同一のフォーマットである）IPX over Ethernet with 802.1q VLAN supportのフォーマットを示す。ＶＬＡＮパケットには、２バイトのＴＣＩフィールドと２バイトの長さＬＥＮまたはe-typeフィールドが含まれ、その後、１つのe-rif制御フィールドと変化する個数のe-rif記述子フィールドが含まれ、e-rif記述子フィールドの数は、式（ＬＥＮ−２）／２によって示される。
【００５３】
図１５に、８０２．１ｑ  ＶＬＡＮサポートを使用するIPX over Ethernet 802.3（独自）のフォーマットを示す。タイプ・フィールドが８１００であり、ＶＬＡＮパケットは、前の図１４のＶＬＡＮの例に類似する。ＩＰＸヘッダは、前の図１１の８０２．３独自フレームに示されたものに類似し、チェックサム・フィールドが「ＦＦＦＦ」と等しくなるようにセットされる。
【００５４】
図１６に、ＶＬＡＮサポートを伴うIPX over Ethernet 802.3を使用するフレームのフレーム配置を示す。これには、ＶＬＡＮパケットの存在を示す８１００のタイプを有する（図１５に類似する）８０２．３  ＭＡＣヘッダと、ＶＬＡＮパケット（やはり図１５に似たフォーマット）、ＬＬＣ  ＬＰＤＵ（図１２に関して図示し、説明したものに類似する）、およびＩＰＸヘッダ（図１０に示されたもの）が含まれる。
【００５５】
図１７に、８０２．１ｑを使用する、ＳＮＡＰおよびＶＬＡＮサポートを伴うIPX over Ethernet 802.3のメッセージの構成またはフォーマットを示す。これは、図１６のフォーマットに類似し、ＬＬＣ  ＬＰＤＵフィールドとＩＰＸヘッダの間にＳＮＡＰフィールドが追加されている。
【００５６】
図１８に、メッセージにイーサネットＭＡＣヘッダおよびＩＰｖ４ヘッダが含まれるIPv4 over Ethernetのフォーマットを示す。フィールドのそれぞれの長さが、この図に示されている。
【００５７】
図１９に、ＭＡＣヘッダとそれに続くＬＬＣ  ＬＰＤＵ、その後に続くＩＰｖ４ヘッダを示す、IPv4 over Ethernet 802.3 with 802.2のメッセージ・フォーマットを示す。
【００５８】
図２０に、８０２．３  ＭＡＣヘッダにＬＬＣ  ＬＰＤＵが続き、その後にＩＰｖ４ヘッダ（および、適用可能な場合にはＵＤＰまたはＴＣＰの任意選択のトレーラ）が続く、ＳＮＡＰを伴うEthernet 802.3上のＩＰｖ４フレームのメッセージ・フォーマットを示す。
【００５９】
図２１に、８０２．１ｑ  ＶＬＡＮサポートを伴うIPv4 over Ethernetのメッセージ・フォーマットを示す。このフォーマットは、ＩＰｖ４の特徴ならびに８０２．１ｑ  ＶＬＡＮサポートの他の例に見られるＶＬＡＮパケットの特徴を有する。
【００６０】
図２２に、IPv4 over 802.3 with 802.2の属性とＶＬＡＮパケットのメッセージ特性を組み合わせた、８０２．１ｑ  ＶＬＡＮサポートを有するIPv4 over Ethernet 802.3（with 802.2）のメッセージ・フォーマットを示す。
【００６１】
図１０から２２のそれぞれで、最下行は、フレームまたはメッセージのレイヤ３（またはＬ３）部分を表し、メッセージのＬ３部分の前にある材料のサイズの変動のゆえに、メッセージのＬ３部分は、メッセージのタイプすなわちプロトコルおよびカプセル化方法に依存して、異なる場所から開始される。Ｌ３メッセージの処理が望まれる（カプセル化を無視する）が、マルチプロトコル、マルチカプセル化システムで、Ｌ３メッセージの先頭を見つけることが困難になる可能性がある。さらに、フレームに対して複数のプロセッサ１１０の１つによって実行される命令が、フレーム・プロトコルおよびカプセル化方法のタイプに依存するので、何か（この場合ではハードウェア・クラシファイヤ補助機構１１８）が、命令メモリ１２２内のプロセッサ用の正しい開始命令へのポインタを提供することが望ましい。
【００６２】
図２３に、命令メモリ１２２の選択された部分および複数の処理ユニット１１０の１つと共に、図２の要素１１８として示されたクラシファイヤ・ハードウェア補助機構のブロック図を示す。クラシファイヤ・ハードウェア補助機構１１８は、入力情報単位（またはフレーム）に関連する１２８ビット・セグメントを操作し、この１２８ビット・セグメントは、時々「ＦＩＳＨ」と呼ばれ、ディスパッチャ１１２からクラシファイヤ・ハードウェア補助機構１１８（ならびに個々の処理ユニット１１０の１つ）によって受け取られる。この分類機能は、最初の３つまでのＦＩＳＨ（または、フレームに関連する最初の３８４ビット、あるＦＩＳＨを別のＦＩＳＨから区別するために時々ＦＩＳＨ１、ＦＩＳＨ２、およびＦＩＳＨ３と呼ばれる）を操作する。最初のＦＩＳＨ（ＦＩＳＨ１）は、実際には受け取られたフレームではなく、どのポートからフレームが来たか、デフォルト・コード・エントリ・ポイント（default code entry point）２９１、および本発明のハードウェア・クラシファイヤを使用するフレーム分類をイネーブルするかどうかのインジケータ２９２（yesまたはno）などの、そのフレームに関連する情報の組である。
【００６３】
ブロック２１０で、イーサネットのタイプを、フレーム内の変化する場所で比較して、フィールドが、前に構成されたプロトコル、たとえば第１イーサネット・バージョン（たとえばＩＰｘ）または第２イーサネット・バージョン（たとえばＩＰｖ４）と一致するかどうかを判定する。ブロック２２０で、ＳＡＰ（サービス・アクセス・ポイント、service access point）フィールドが、やはりレジスタ内で指定される（たとえば、プロトコルのタイプを示す特定の保管された値）、現在構成されているプロトコルと一致するかどうかを判定する。このシステムは、異なるタイプのカプセル化を表すＳＮＡＰフィールドが存在するかどうかも判定する。ブロック２４０内の「ＡＡＡＡ０３」などの指定されたフィールド、および、ブロック２５０でメッセージ内の仮想ローカル・エリア・ネットワーク（ＶＬＡＮ）使用の存在を検出する。ブロック２６０は、分類制御であり、これは、イネーブル分類２９２によってイネーブルされる時に、フレームに関連するパラメータを保管し、プロトコル・タイプ、レイヤ３ポインタ、および分類フラグを示す出力を信号線２７０、２７２、および２７４に供給する責任を負う。
【００６４】
各メッセージの制御エントリ・ポイント（処理の開始、命令メモリ１２２内の最初の命令のアドレス）を、定義されたフォーマットのそれぞれについて事前に判定し、テーブル２８０に保管することができる。すなわち、ＥＴＹＰＥ＝０かつＶＬＡＮなしの場合に、制御エントリ・ポイント（開始アドレス）が、命令メモリ内のアドレス１２２ａになり、ＥＴＹＰＥ＝１かつＶＬＡＮなしの場合に、制御エントリ・ポイントがアドレス１２２ｂになる。同様に、ＥＴＹＰＥ＝０かつＶＬＡＮあり、およびＥＴＹＰＥ＝１かつＶＬＡＮありの場合に、めいめいの制御エントリ・ポイント（実際のメッセージの処理が開始される場所）が、それぞれ命令１２２ｃおよび１２２ｄになる。ＥＲＩＦフィールドを伴うフレームの場合には、処理が命令１２２ｅで開始され、プロトコルまたはカプセル化方法が見つからない、デフォルト・プログラムの場合に、処理が命令１２２ｆで開始される。
【００６５】
どの場合でも、デフォルト制御エントリ・ポイントが、メッセージのＦＩＳＨ１に含まれ、ブロック２９０で読み取られる。その後、ブロック２９５によって、デフォルト制御エントリ・ポイントを使用するかどうかが判定される、すなわち、信号線２９２でハードウェア分類がイネーブルされ、テーブル２８０から異なる制御エントリ・ポイントが判定されない場合には、デフォルト・エントリが使用され、そうでない場合には、テーブル２８０からの制御エントリ・ポイントが使用される。
【００６６】
ハードウェア・クラシファイヤ補助機構１１８からの信号線２７０および２７２（分類フラグおよびＬ３ベース・アドレスが、それぞれハードウェア・クラシファイヤ補助機構１１８によって決定される）が、フレームを処理するために割り当てられた個々のプロセッサ１１０に供給され、データ・メモリ１１０ｂに保管されたフレームを処理する１つの処理ユニットに関連する汎用レジスタ１１０ａに保管される。デバイス２９５からの出力線２７６は、フレームの特定のタイプに関する命令メモリ１２２の開始アドレスを供給し、そのデータが、命令制御論理１１０ｃに保管される。ＡＬＵ（演算論理装置、arithmetic/logic unit）が、処理ユニット１１０の一部である。プロセッサ１１０は、命令制御論理１１０ｃ内の命令カウンタを使用して、命令メモリ１２２から命令を取り出す。この形で、ハードウェア・クラシファイヤ補助機構１１８によって判定されたプロトコルおよびカプセル化方法に基づいて、処理ユニット１１０が、処理されるフレームに適当な命令セットの開始アドレスを用いて事前条件付けされ、フレームのタイプを示す適当なフラグが、正しい命令を使用するフレームの処理をプロセッサ１１０が開始できるようにするためにセットされる。
【００６７】
図２４に、メッセージフォーマットのカテゴリ化を決定するのに使用される論理を示す。これは、ブロック３１０で開始され、ここでＦＩＳＨ２が選択され、ブロック３２０で、フレームのバイト１３から１４（６バイトの宛先アドレスＤＡおよび６バイトのソース・アドレスＳＡとその後のタイプを含むフレーム内のタイプ情報を含むはずの２バイト）をテストする。これらのバイトが、ＥＴＹＰＥ０またはＥＴＹＰＥ１のいずれかの内容と一致する場合には、ブロック３２３で、適当なフラグをセットすることによってプロトコル情報を識別し、ブロック３２５で処理を終了する。そうではなく、タイプ・ブロックが０６００Ｈ（１６進）未満の場合には、このフレームは、Ethernet 802.3フレーム・フォーマットであってEthernet V2.0DIXフォーマットではなく、このフィールドは、タイプ・フィールドではなく長さフィールドであり、図２４の図の左側で処理される。このタイプ・ブロックが８１００である場合には、このフレームは、８０２．１ｑ  ＶＬＡＮサポートを使用するフレーム（たとえば、図１４、１５、１６、１７、２１、および２２を参照されたい）であり、図２４の図の右側で処理される。タイプ・フィールドが他の何かである場合には、制御をブロック３２５に渡し、ここで、このフレームが明らかに未知のプロトコルであるから、プロトコル情報を一切記録せずに、分類が完了したとみなす。
【００６８】
ブロック３２０で、バイト１３から１４が０６００Ｈ未満であると判定された場合には、ブロック３２２で、バイト１５から１７を分析して、それがＳＡＰフィールドとして知られるものであるか、タイプのＬＬＣまたは論理リンク制御フィールド（たとえば図１３で使用されるＡＡＡＡ０３）であるかを判定する。このフィールドが、ＳＡＰフィールドの１つとして認識される場合には、ＳＡＰフィールドをセットし、ブロック３２３で、プロトコル情報を保存し、その後、ブロック３２５で、分類が完了したとみなす。これがＬＬＣフィールドである場合には、制御がブロック３２４で継続され、ここで、ＦＩＳＨ３を入手し、そのバイト２から６を、認識されたＥＴＹＰＥについて分析する。ＥＴＹＰＥが認識される場合には、ブロック３２３でプロトコル情報を保存し、その後、ブロック３２５で終了する。
【００６９】
ブロック３２０で、バイト１３から１４が８０１１と等しく、これがＩＥＥＥ標準規格８０２．１ｑで指定される仮想ローカル・エリア・ネットワーク（ＶＬＡＮ）であることが示される場合には、ブロック３３０でＶＬＡＮの存在を保管し、その後、ブロック３４０で、ＣＦＩフィールドの存在を検査する。それが存在する場合には、分類が完了しており、制御をブロック３２５に渡す。そうでない場合には、ブロック３５０で、ＦＩＳＨ３のバイト１から２をテストして、既知のＥＴＹＰＥ（ブロック３２０のテストのように）または長さ（０６００Ｈ未満）が提供されるかどうかを判定する。ＥＴＹＰＥが提供される場合には、ブロック３２３でプロトコル情報を保管し、制御をブロック３２５に渡し、ここで、分類が完了したとみなされる。ブロック３５０で、フィールドがＥＴＹＰＥとして認識されない場合には、ブロック３２５で、分類処理が完了したとみなす。ブロック３５０のテストで長さが提供される（０６００Ｈ未満）場合には、ブロック３６０で、既知のＳＡＰについてバイト３から５をテストする。それがＡＡＡＡ０３である場合には、制御をブロック３７０に渡して、既知のＥＴＹＰＥについてバイト６から１０を判定する。
【００７０】
図２５に、具体的には図２３の要素のハードウェア・クラシファイヤの改良された版を示す。この図２５では、ハードウェア・クラシファイヤに、単一の開始アドレスではなく、命令スタック１１０ｄに保管された一連のアドレスを含む命令制御論理１１０ｃに対する改良と共に、図２３の要素が含まれる。この命令スタックには、初期命令アドレスと、その後の、後の分岐でのテスト・ステートメントまたは条件ステートメントを回避するための、プロセッサがｆｏｒｋまたは分岐に達した時に必要な他のアドレスが含まれる。これらの開始アドレスは、スタック内に順番に保管され、分岐命令が必要な時にスタックから除去される。
【００７１】
さまざまなプロトコルまたはカプセル化技法のイーサネット・メッセージの定義的内容に関するさらなる情報については、イーサネット・フレーム構成に関する適当な標準規格または参考案内を参照されたい。イーサネット・プロトコルおよびカプセル化技法と、それに関係する標準規格およびオプションとの理解に役立つ可能性がある一般に入手可能な文書が、ISO/IEC Final CD 15802-3, IEEE P802.1D/D15, １９９７年１１月２４日, Annex Cと、IEEE Draft Standard 802.1Q/D9、１９９８年２月２０日付と、RFC 1700 - Assigned Numbers by J. Reynolds and J. Postel, １９９４年１０月（http://www/isi.edu/rfc-editor/rfc.htmlでも入手可能な文書）と、IBM Token Ring Network Architecture Referenceと、IBM LAN Bridge and Switch Summary. Publication Number SG24-5000-00, Version 1.3, １９９６年１月、特にChapter 1.1.1である。
【００７２】
ハードウェア・クラシファイヤは、ハードウェア（またはシリコン基板上の実際の実施形態）構成での論理設計の設計および製造用のさまざまな一般的に入手可能なソフトウェア・ツールの１つの使用を介することを含むさまざまな形で設計でき、また、論理設計者による手による従来の設計によって設計することができる。この例では、所望のテストが、ＶＨＳＩＣハードウェア・ディスクリプション言語または短縮形で（ＶＨＤＬ）と称するソフトウェア言語を使用してプログラムされ、その後、既知のソフトウェア（ＩＢＭ社によって販売されているものまたはSynopsis社によって販売されているものなど）にかけて、所望のテストをハードウェアの形で達成するのに必要なゲートおよびロジックを有する設計を作成する。他の類似する設計システムが、存在し、有利に使用することができ、その結果、論理の設計者が、ゲートの構造またはその位置を知る必要がなく、所望の入力およびテストおよび出力の論理機能だけを知れば十分になる。
【００７３】
上で述べたように、いくつかのシステムでは、各フレームを処理するために割り当てられるプロセッサから独立に、フレームが受け取られた順序でデータ・フレームの処理済みのフレームを転送する機能を本発明の処理システムに含めることが望ましい場合がある。そのよなシステムでは、ディスパッチャ１１２が、使用可能な処理ユニットを識別し、受け取ったフレームを処理のために処理ユニットに割り当てた後に、フレームとそのフレームが割り当てられた処理ユニットの識別情報を作成し、保管する。
【００７４】
フレームは、通常は、メッセージ番号（時々ＭＡＣと称する）などの識別情報と、フレームのソースのアドレス（時々ＳＡと指定される）および宛先のアドレス（時々ＤＡと指定される）と共に到着する。そのような情報の位置および内容は、メッセージのフォーマットおよびカプセル化技法に応じて変化する可能性があるが、この情報を用いると、メッセージ全体が単一のフレームより長い場合であっても、フレームを、このシステムとスイッチおよびルータを介して宛先に正しくルーティングでき、正しい順序で完全なメッセージを再組立できるようになる。通常、メッセージのコンポーネントを、データ・フローと称し、データ・フローの各部分に、同一の識別情報（ＭＡＣ、ＳＡ、およびＤＡなど）が含まれる。ディスパッチャ１１２ユニットによって入力フレームに割り当てられる実際のラベル（または識別情報）は、ＭＡＣ−ＳＡ＋ＤＡ、または他のメッセージ・フォーマットのＬＩＤフィールドとＭＩＤフィールドの排他的論理和をとることによるなど、さまざまな形で作成することができる。
【００７５】
図２６に示されているように、３つのリストまたはキュー内のストレージを、フレームごとに作成することができる。まず、処理されたフレームのキュー４００が、完了した作業（所与のフレームを処理するプロセッサから受け取られる、出力または処理されたフレーム）を保持するために定義され、これは、フレーム０からフレームＮとして示された、プロセッサごとの少なくとも１つの完了したフレームのためのバッファまたはメモリ・スペースを必要とし、ＮＰＵ−０からＮＰＵ−Ｎとして識別されるプロセッサが、めいめいのフレームに結合される。ディスパッチャ１１２は、フレームを処理ユニットに送る時に、第２メモリまたはキュー４１０にそのフレームの識別子を送り、第２メモリまたはキュー４１０には、めいめいのネットワーク処理ユニットＮＰＵ−０からＮＰＵ−Ｎに対応するストレージ・ロケーション０からｎが含まれる。識別子またはラベルｍを有するフレームがＮＰＵ−０に送られる時に、ＮＰＵ−０のラベルに対応するメモリ０に、識別されたｍが保管のために送られ、ＮＰＵ−０が、識別子がｍである入力情報単位を処理しようとしていることが示される。同一の識別子ｍを有する後のフレームが、同一のデータ・フローに属し、異なる識別子またはラベルを有するフレームが、異なるデータ・フローを表すことを想起されたい。したがって、０のラベルを有する入力情報単位が、受け取られ、ＮＰＵ−１にディスパッチされる場合に、０が、ＮＰＵ−１に対応するストレージ１に記録される。その後、同一のデータ・フローからの第２入力単位（やはり０のラベルを有する）が、ディスパッチャ１１２によって受け取られ、プロセッサＮＰＵ−Ｎに割り当てられる場合に、メモリＮにも、プロセッサＮに割り当てられた情報単位を表す０のラベルが保管される。
【００７６】
第３メモリ４２０には、ｎ個の処理ユニットによって現在処理されつつあるラベルのそれぞれのストレージが含まれる。ラベルのそれぞれについて、割り当てられたプロセッサの識別子が、保管され、リスティングが順次式に行われるので、特定のメッセージ・フローに最初に割り当てられたプロセッサが、メモリ内で最初に現れる。この例では、ラベルｍについて、メモリ４２２内の項目０によって、ＮＰＵ−０がそのフローからのラベル０に関する入力情報単位を処理しつつあることが示され、第１単位は、メモリ４２４によって示されるように、プロセッサＮＰＵ−Ｎによって処理されつつあり、第２単位は、メモリ４２６によって示されるように、プロセッサＮＰＵ−１によって処理されつつある。所与のフローについて、入力情報単位がディスパッチャに到着する順序が、維持され、その結果、同一のデータ・フローの後続の伝送を、それが受け取られたのと同一の順序で行えるようになり、したがって、ラベル・メモリ４２４および４２６が、入力フレームがネットワークから受け取られ、Ｎ個のプロセッサにディスパッチされた順序でリストされたＮＰＵまたは処理ユニットを有することがわかる。
【００７７】
図２７に、入力フレームを処理し、本明細書で説明するデータ管理技法を使用する際に使用される、完了ユニット１１４のより詳細な構造を示す。この実施形態の、図示の完了ユニット１１４は、図２３に図示されていない、処理ユニットの出力（たとえば処理された情報単位）を分配するために、複数のラウンド・ロビン・デバイスと通信する。複数のラウンド・ロビン・デバイスには、アップラウンド・ロビン４５０および２つのダウン・ラウンド・ロビン・デバイス、ターゲット・ポート（特別にアドレッシングされる少数の頻繁に使用されるポート）用の４６０として識別される１つのラウンド・ロビン、および一般分配（特別にアドレッシングされるターゲット・ポート以外のポートにアドレッシングされた処理済み情報）用の１つのラウンド・ロビン４７０が含まれる。
【００７８】
論理ＡＮＤゲート４５２、４６２、および４７２が、それぞれ、ラウンド・ロビン４５０、４６０、および４７０のゲーティングを提供する。ＵＰラウンド・ロビン４５０にフレームを供給するＡＮＤゲート４５２について、入力は、それをＵＰフレームにするもの（Ready FCBページ５１０に関連するブロックＵＰから）、フレームを有効なフレームにするもの（それが有効なフレームであり、伝送の準備ができていることを示すインジケータＶＦ）、ラベル・フィールドを関連するフレーム・ラベル・フィールド（Ｍ０１からＭ９２）で有効にするもの、およびラベルをデータ・フローのヘッド（または最も早い）フレームに関連付けるものである。
【００７９】
ディスパッチャ１１２は、フレームが所与のプロセッサにディスパッチされる時に、２つの情報をラベル・エンキュー４８０に供給する。すなわち、信号線４８２のフレームのラベルと、信号線４８４の、フレームが割り当てられたプロセッサの識別である。フレームのラベルによって、そのフレームが属するデータ・フローが識別され、このラベルは、好ましい実施形態では、ＭＡＣにソース・アドレスを加え、宛先アドレスを引いたものに基づき、各データ・フローに一意の識別子を与える目的は、同一のデータ・フローからのフレームが、同一のラベルを有し、異なるデータ・フローからのフレームが、異なるラベルまたは識別子を有するようにすることである。
【００８０】
図２８に、Ｎ個のプロセッサのそれぞれに関連する情報を保管するラベル・フィールド要素５００のフォーマットを示す。Ｎ個のプロセッサのそれぞれが、２つのこのようなラベル・フィールドを関連付けられ、その一方は、処理されつつあるフレーム用であり、他方は、処理済みであり、処理複合体からの転送を待っているフレーム用である。転送の準備ができている処理済みのフレームは、時々Ready FCB Pageと称するメモリまたはストレージ５１０に保持され、これらのストレージの１つが、Ｎ個のプロセッサのそれぞれについて存在する。
【００８１】
ラベル・フィールド要素５００には、ラベルＬ、ヘッド・フィールドＨ、有効フィールドＶ、テール・フィールドＴ、および次フィールドＮが含まれる。ラベルＬは、メッセージ内容から導出され、データ・フローのそれぞれの一意の識別子を表す。ヘッド・フィールドＨは、現在Ｎ個の処理ユニットによって処理されつつあるデータ・フローまたは関連するフレームのチェインの先頭を、処理されつつある作業または処理複合体からの転送を待っている処理済みフレームのいずれかとして識別する。Ｎ個のプロセッサの処理複合体で処理されつつあるデータ・フローのそれぞれが、Ｎ個のプロセッサのどこかにヘッドまたは先頭（またはそのデータ・フローについて最初に受け取られたフレーム）を有し、その先頭が、それに関連するラベル・フィールド要素のヘッド・フィールドＨの１によって、その「ヘッド」として識別される。同様に、プロセッサ内の各データ・フローは、現在Ｎ個のプロセッサ内にある最終フレームも有し、その最終フレームが、テール・フィールドＴの１によってテールとして識別される。
【００８２】
有効フィールドＶは、プロセッサが、有効フィールドの１によって示される実際のデータを含む（処理からそうなるように）か、有効フィールドＶの０によって示されるように実際のデータを含まないかを示す。処理が最初に開始される時には、実際のデータまたは有効なデータが、システムに存在せず、したがって、有効フィールドＶに、システムの初期化の一部として０がセットされる。後に、データが所与のプロセッサのReady FCBページ５１０から読み取られる時に、そのプロセッサFCB Pageに対応する有効フィールドＶに、０がセットされ、そのプロセッサが、もはやそのラベルに対応する有効な情報を有しないことが示される（FCBページの情報が、すでにラウンド・ロビンに渡されているので；ただし、プロセッサ自体が異なるフレームに対して作業している可能性があるので、プロセッサが、そのプロセッサに関連する他のラベル・フィールドに有効な情報を有する場合がある）。次フィールドＮは、同一のデータ・フロー内の次のフレームに関連するラベル・フィールドすなわち、Ｎ個のプロセッサに関連する２Ｎ個のラベル・フィールドの他の１つを示す。ラベル・エンキュー４８０は、情報入力単位またはフレームのそれぞれについて、所与のフレームがディスパッチされたことを示すメッセージを、データ・フローおよびのフレームがディスパッチされたプロセッサの識別子と共に、ディスパッチャから受け取る。
【００８３】
図２９に、図２７のラベル・エンキュー４８０のフローを示す。フレームが、ディスパッチャ１１２からｎ個のプロセッサの１つにディスパッチされる時に、ブロック６００で、入力情報単位またはフレームのラベルが、信号線４８２上でラベル・エンキュー４８０に送られ、ｎ個のプロセッサのどれがそのフレームを処理しているかの識別が、信号線４８４上で送られる。ラベル・エンキュー４８０による最初の処理は、ブロック６０２で、最初のラベル・フィールドがポイントする１つのストレージについて有効フィールドＶが１であるかどうかを判定することである。有効フィールドＶが１である場合には、ポイントされたストレージが占有されており、ブロック６０６によって示されるように他のストレージにデータを保管しなければならず、そうでない場合には、ブロック６０４で、ポイントされたストレージを使用しなければならない。次に、ステップ６５０で、適当なストレージの有効フィールドＶに１をセットして、有効なデータがそのストレージに保管されていることを示し、ブロック６４０で、現行のストレージ・ロケーションのテール・インジケータＴをセットして、これが現行データ・ストリームの最後であることを示す（同一のデータ・フローの次のフレームが受け取られるまで。その時点でテール・フィールドＴがリセットされる）。次に、ブロック６１０で、ラベルを、どれであれプロセッサによって処理されつつある現行ラベル（もちろん、有効フィールドＶが１であり、それが有効なフレームであることが示されるものでなければならない）と比較する。この比較の結果は、現行ラベルが既に処理中のものと等しい（この場合には制御がブロック６７０に渡される）か、現在処理中のどのラベルとも等しくない（この場合には制御がブロック６３０に渡される）のいずれかである。現行ラベルの１つとの一致がある場合には、そのフレームは、既存のデータ・フローの一部であり、したがって、ブロック６７０で、データ・フローの前の末尾のテール・フィールドＴをリセットし（したがってＴ＝０になる）、そのラベル・フィールドの次フィールド・ポインタを、現行フレームのロケーションをポイントするようにセットする。その後、ブロック６８０で、ヘッド・フィールドＨに０をセットして、現行フレームがデータ・フローのヘッドでないことを示す。現行フレームのラベルが、現在保管されているどのラベルとも等しくない場合には、現行フレームが、新しいデータ・フローであり、現行フレームが、その先頭であり、したがって、ブロック６３０で、ヘッド・フィールドＨに１をセットして、その状況を示す。適当なフラグ、特にヘッド・フィールドＨをセット・アップするためのブロック６３０またはブロック６８０の処理の後に、既存データ・フローへのリンクおよびフィールドまたはフラグのセット・アップの処理が終了する。
【００８４】
図３０に、プロセッサからフレームを出す処理または分配する処理を示す。まず、ブロック７１０で、第１フィールド・インジケータを反転し、その結果、ポインタが、プロセッサについて第１フィールドまたは次フィールドとして他のストレージをポイントするようにする。次に、ブロック７２０で、有効フィールドＶを０にリセットし、データがもはや有効でない（フレームがディスパッチされ、データが、現在処理されつつあるフレームを表さない）ことを示す。ブロック７２５で、テール・フィールドＴがセットされ（Ｔ＝１）、これが特定のデータ・フローの最終フレームであることが示されるかどうかをテストする。そうである場合には、制御を、処理の終了を示すブロック７４０に移す。そうでない場合には、ブロック７３０で、連続する次のフレームを突き止め（次フィールドのポインタによって）、そのヘッド・ビットまたはフラグＨをセットして、それが現在プロセッサ内にあるデータ・フローの最初のフレームであることを示す。その後、ブロック７３０から、フラグのセットが、ブロック７４０によって示されるように終了する。
【００８５】
図３１に、図２９の論理に関して上で説明した完了ユニットによって複数のデータ・フローに対処できる方法を示す例によって本発明のシステムを示す。Ｎ個のプロセッサが、ディスパッチャ１１２および完了ユニットと共にしばらく作業しており、したがって、図３１は、完了ユニットの一部、特にラベル・ストレージに関して保管されたデータのスナップショットを表す。この図からわかるように、ラベル・エンキューが、Ｎ個のプロセッサごとに２つの、複数のラベル・メモリに結合される。プロセッサのそれぞれは、図示の３つのラウンド・ロビンへの伝送を待っている処理済みフレーム用の出力バッファ（時々Ready FCB Pageと称する）にも関連付けられる。ラベル・メモリの対のそれぞれに関連するのが、どのラベル・メモリが先に受け取られたかを示す第１ラベル・メモリである（両方のラベル・メモリが有効である時に、第１ラベルが、Ready FCB Pageバッファ内にあるものを表し、第２のまたは後に受け取られたラベルが、めいめいのプロセッサ内で現在処理されつつあるものを表す）。５つの別々のデータ・フローが、この図に示されているが、任意の所与の時点で進行中であるデータ・フローの数は、システム（特にそのサイズおよびネットワーク・トラフィック）に依存し、経時的に変化する可能性がある。この例では、１０個のプロセッサが、プロセッサ０から９として識別され、ラベル・メモリが、プロセッサ０用のメモリＭ０１およびＭ０２から、プロセッサ９用のラベル・メモリＭ９１およびＭ９２として識別されるが、プロセッサの数は、設計選択であり、望まれる場合に変更の対象になる。識別子Ａを有する第１データ・フローが、ラベル・メモリＭ０１（およびプロセッサ０への対応する参照）がチェーンまたはデータ・フローのヘッドを表すことの表示（Ｈ＝１）によって示されるように、ラベル・メモリＭ０１で開始される。ラベル・メモリＭ０１の次フィールドＮは、ラベル・メモリＭ２１をポイントして、プロセッサ２がこのデータ・フローに関連する次の情報単位を処理していることを示す。ラベル・メモリＭ２１の次フィールドは、ラベル・メモリＭ５２をポイントし、これは、プロセッサ５がこのデータ・フローの次の部分を有することを示す。ラベル・メモリＭ５２のセットされたテール・フィールドによって、これがＮ個のプロセッサで現在処理されつつあるこのデータ・フローの最後の部分であることが示される。この例のデータ・フロー・シーケンスは、ラベル・メモリＭ０１からラベル・メモリＭ２１をポイントする矢印Ａ１およびラベル・メモリＭ２１からラベル・メモリＭ５２をポイントする矢印Ａ２によって示されて、データ・フローの要素間の論理接続が示される（矢印は、次フィールドのポインタを論理的に表すのであって、実際の実施形態に物理的に存在するわけではない）。同様に、ラベル・メモリＭ０２からラベル・メモリＭ１１へのデータ・フローは、矢印Ａ３によって、同一のデータ・フロー内の順序を示す（ただし、説明されたものと異なるデータが、ラベル・メモリＭ０１、Ｍ２１、およびＭ５２に関する）。第３のデータ・フローが、ラベル・メモリＭ３１およびＭ４２に関する矢印Ａ４によって示され、第４のデータ・フローが、ラベル・メモ��Ｍ７１およびＭ７２の間の矢印Ａ５によって示される。最後に、第５のデータ・フローが、ラベル・メモリＭ４１に示されているが、これは、現在単一のラベル・メモリだけが含まれるデータ・フローなので、このデータ・フローは矢印を有しない。このラベル・メモリＭ４１は、データ・フローのヘッドとテールの両方であり、次フィールドを有しない。というのは、このデータ・フローに関連する他のラベル・メモリがないからである。
【００８６】
単一のプロセッサに関連する２つのラベル・メモリがある時に、ラベル・メモリの一方が、バッファに保管された、完了したまたは処理された情報単位を表し、時々Ready FCB Pageと呼ばれ、処理複合体からの伝送（場合に応じてアップまたはダウンのいずれか）のために適当なラウンド・ロビン・ユニットへの転送の準備ができており、転送アップについて、それがインターフェース・デバイスに転送され、転送ダウンについて、それがデータ伝送ネットワークに向かって転送されることが示されることを記憶されたい。この例では、プロセッサ０、プロセッサ４、およびプロセッサ７に、関連するラベル・メモリの両方にデータが含まれる。各Ready FCB Pageに関連するのが、UPフィールド（これがアップ・ページとダウン・ページのどちらであるかを示す）、ならびに、これがダウン・ページである場合に、フレームがターゲット・ポートまたは一般ポートのどちらにアドレッシングされるのかに関するインジケータであり、このインジケータによって、ダウン・ページをダウン・ターゲット・ポート・ラウンド・ロビンまたは一般ポート・ラウンド・ロビンのどちらに転送するのかが決定される。プロセッサ０の前に受け取ったフレームが、ラベル・メモリＭ０２であり、それが、あるデータ・フレームのヘッドであり、プロセッサ複合体およびそのバッファからの次の転送のためにアップ・ラウンド・ロビン・デバイスによって選択されたアップ・フレームでもある場合には、FCB Pageおよび関連するデータ・フィールドが、Ready FCB Pageから除去され、その情報がアップ・ラウンド・ロビンに転送される。その後、第１ラベル・インジケータをトグルして、プロセッサ１の他方のラベル・メモリＭ０１が現在は第１ラベル・メモリであることを示し、ラベル・メモリＭ０２の有効フィールドＶに０をセットして、このラベル・メモリがもはやアクティブでも有効でもないことを示し、関連するＦＣＢページの有効フィールドＶＦを、０にリセットする。
【００８７】
本発明は、既存のデータ・フローを妨げず、前もって新しいデータ・フローについて知る必要なしに、新しいデータ・フローをサポートする。新しいデータ・フローを表すパケット（たとえば、処理ユニットの１つからの、その状況に関するメッセージ）は、単純に、その識別データと共に保管され、別のデータ・フローへの参照はない。この識別子がないことは、「ラベルなし」フィールドをセットされた、いつでも進行できるメッセージである既存のデータ・フローのどれの識別子にも一致しない。
【００８８】
本発明は、ラベル・フィールドのチェーニング（次ポインタと、フレームを転送するラウンド・ロビン・デバイスへのアクセスを有する前に所与のフレームがヘッドであるという要件）を無視して、システムが、完了したフレームが受け取られた順序で完了したフレームを処理できるようにすることによって、フラッシュ・コマンドによってめいめいの順序でのデータ・フローの処理をオーバーライドできるようにもする。これは、FCB Pageの「ラベルなしフィールド」を強制することによって達成することができる。
【００８９】
単一のデータ・フローは、データ・フローのヘッドが処理されるまでブロックされたままになる。というのは、通常の動作（フラッシュ代替物なし）で、メッセージ・フローのヘッドであるフレームだけが、完了ユニットによるラウンド・ロビンへの送出に関して検討されるからである。しかし、各データ・フローは、それ自体のヘッドを有し、したがって、あるデータ・フローがブロックされる可能性はあるが、他のデータ・フローは、割込みまたは妨害なしに、介入なしに、処理および完了した情報単位のラウンド・ロビンへの送出を継続することができる。これは、他のデータ・フローが停止されないので、単一のデータ・フローが停止された（たとえば、プロセッサが障害を発生したか、単一のデータ・フローの１つの要素を処理できない）場合に特に有用である。そうでない場合には、単一のデータ・フローのブロックが除かれるまで、処理全体が停止するはずである。
【００９０】
もちろん、添付図面と共に検討される好ましい実施形態の前述の説明に鑑みて、本発明の多数の修正形態が、当業者に明白になる。たとえば、クラシファイヤを実施するハードウェアの実際のタイプは、多数の設計選択の対称であり、説明した特定の選択は、メッセージ内容、メッセージ・カプセル化の方法、および行われる処理に依存する。本発明の趣旨から逸脱せずに、システム実施形態およびシステムが処理できるメッセージ構成に対する多数の修正を行うことができる。保管されるラベルは、メッセージ内容に基づかない他の形で生成することができ、また、単に、ディスパッチャによって識別されるデータ・フローの連続番号とすることができる。本発明の趣旨から逸脱せずに、本発明のシステムに対する多数の他の修正および適応を、有利に使用することができ、他の関連する特徴の対応する使用なしで、本発明の長所の一部を達成することができる。したがって、好ましい実施形態の前述の説明は、本発明の原理を例示するのみとみなされなければならず、本発明の制限ではない。
【図面の簡単な説明】
【図１】  ＮＰＵ特許に記載され、本発明を実践するのに有用な、組み込みプロセッサ複合体を含むインターフェース・デバイスのブロック図である。
【図２】  本発明に有用なクラシファイヤ・ハードウェア補助機構を伴う、図１に示されたタイプの組み込みプロセッサ複合体のブロック図である。
【図３】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図４】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図５】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図６】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図７】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図８】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図９】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１０】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１１】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１２】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１３】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１４】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１５】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１６】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１７】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１８】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図１９】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図２０】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図２１】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図２２】  本発明のハードウェア・クラシファイヤで使用されるさまざまなイーサネット・プロトコル・フォーマットを示す図である。
【図２３】  本発明でフレーム部分を処理するためにクラシファイヤによって使用される論理を示す、本発明のクラシファイヤ・ハードウェア補助機構の流れ図である。
【図２４】  本発明のクラシファイヤを示す機能図である。
【図２５】  第１命令のアドレスのほかに、一連のアドレスをスタックに保管できるようにする、図示の任意選択の機能強化を有する本発明のハードウェア・クラシファイヤの代替実施形態を示す図である。
【図２６】  各フレームに関連するキューの概略図である。
【図２７】  Ｎ個のプロセッサのそれぞれについて２つのラベル・ストアを有する、本発明の完了ユニットの詳細図である。
【図２８】  Ｎ個のプロセッサのそれぞれによって処理されるデータ・フローを記憶するラベル・ストアのフォーマットを示す概略図である。
【図２９】  新しいフレームが処理ユニットの１つにディスパッチされたことの表示を受け取り、処理する際に完了ユニットによって実行される論理を示す流れ図である。
【図３０】  フレームの処理が完了したことのレポートを処理する時に完了ユニットによって実行される論理処理を示す流れ図である。
【図３１】  好ましい実施形態での完了ユニットの動作を示すデータを含む、図２７の完了ユニットのもう１つの図である。
【図１】
0004095802.tif 000002
【図２】
0004095802.tif 000003
【図３】
0004095802.tif 000004
【図４】
0004095802.tif 000005
【図５】
0004095802.tif 000006
【図６】
0004095802.tif 000007
【図７】
0004095802.tif 000008
【図８】
0004095802.tif 000009
【図９】
0004095802.tif 000010
【図１０】
0004095802.tif 000011
【図１１】
0004095802.tif 000012
【図１２】
0004095802.tif 000013
【図１３】
0004095802.tif 000014
【図１４】
0004095802.tif 000015
【図１５】
0004095802.tif 000016
【図１６】
0004095802.tif 000017
【図１７】
0004095802.tif 000018
【図１８】
0004095802.tif 000019
【図１９】
0004095802.tif 000020
【図２０】
0004095802.tif 000021
【図２１】
0004095802.tif 000022
【図２２】
0004095802.tif 000023
【図２３】
0004095802.tif 000024
【図２４】
0004095802.tif 000025
【図２５】
0004095802.tif 000026
【図２６】
0004095802.tif 000027
【図２７】
0004095802.tif 000028
【図２８】
0004095802.tif 000029
【図２９】
0004095802.tif 000030
【図３０】
0004095802.tif 000031
【図３１】
0004095802.tif 000032