JP2002507366A - 多層ネットワーク要素におけるサービス品質のためのシステムおよび方法 - Google Patents

Abstract

(57)【要約】 サービス品質を使用して受信パケットを入力ポートから１つまたは複数の出力ポート（３８）に中継する多層ネットワーク要素（１２）。出力待ち行列（５４）が待ち行列の容量を下回るしきい値を超えるかまたは一致すると、パケットはランダムに廃棄される。待ち行列が一杯になると、ネットワーク要素はどのフローが待ち行列を一杯にしたかを判断する。そのフローの優先順位は下げられる。マルチキャスト・パケットにおいて、パケットは各出力ポートで異なる優先順位を有することができる。各出力ポートにおける複数の出力待ち行列のスケジューリングは、時間間隔ごとに送信するようにパケットの重み部分を割り振る重みラウンド・ロビン手法を使用する。パケットの送信中に重み部分が満たされた場合であっても、パケットは送信中に割り込みされない。パケットに割り込まない結果として送信された余分のバイト数は、次のラウンドで計算に入れられる。

Description

【発明の詳細な説明】 多層ネットワーク要素におけるサービス品質のためのシステムおよび方法 発明の分野 本発明は、一般には、ネットワーク内におけるパケット中継に関し、詳細には 、多層情報を使用したパケットの中継のためのシステムおよび方法に関する。 発明の背景 コンピュータ間の通信は、個人と企業の両方の環境における日常生活の重要な 要素になっている。ネットワークは、このような通信、さらには、サーバ、パー ソナル・コンピュータ、ワークステーション、メモリ記憶システム、またはネッ トワークとの間でデータの送受信を行うことができるその他のあらゆる構成要素 など、ネットワークに接続された様々なタイプの要素間の通信にとっての媒体と なる。これらの要素は、情報の秩序ある送受信を規定する定義済みプロトコルを 使用して互いに通信する。一般に、これらの要素は、ネットワークを接続対象と なる雲のようなものとみなし、多くの場合、ネットワークがどのように機能して いるかや、どのように実施されているかなど、ネットワーク・アーキテクチャの 詳細を知る必要がない。理想的には、ネットワーク・アーキテクチャは広範囲な 応用分野に対応する必要があり、広範囲な基礎技法を可能にする必要がある。ネ ットワーク・アーキテクチャはまた、非常に大きいネットワークに対してうまく 動作し、小さいネットワークに対して効率的であり、変化するネットワーク条件 に適合すべきである。 ネットワークは一般に、その規模に基づいて区別することができる。小規模な ものはローカル・エリア・ネットワーク（ＬＡＮ）であり、共用媒体に接続され た複数のシステム、高総帯域幅、低遅延、低誤り率、ブロードキャスト機能、限 られた地域、限られた端末数などの特性を有し、一般には郵便、電報、および電 話の規制を受けないネットワークを表す。大規模なものは企業ネットワークであ り、地理的に分散した事業組織内の多用な事業体を接続するワイド・エリア・ネ ットワークおよびＬＡＮの接続を表す。 大規模なネットワーク内の接続を容易にするため、ネットワークは一般にはサ ブネットワークに区分化され、各サブネットワークは、たとえば地理的場所や機 能上の目的などの何らかの共通の特性を共用する。この区分化は、２つの主な目 的を満たす。すなわち、ネットワーク全体を管理しやすい部分に分割し、ネット ワークのユーザを論理的に（または物理的に）グループ化することである。ネッ トワーク・アドレッシング方式は、このような区分化を考慮に入れることができ 、したがって、アドレスはネットワークがどのように区分化されているか、その アドレスがネットワーク階層のどの位置に入るかに関する情報を含むことができ る。 説明と実施の目的のために、ネットワークは、ピア・ツー・ピアプロトコルを 使用して互いに通信する、端末装置が接続された複数の層を有するものとして説 明することができる。周知の開放型システム相互接続（ＯＳＩ）参照モデルは、 ネットワークを７つの層を使用して見る汎用化された方法を提供し、他のモデル と実際の実施システムの機能をマッピングするのに好都合な参照である。所与の モデル内における各層間の区別は明確であるが、所与のモデルの実施、または異 なるモデル間における層のマッピングは不明確である。たとえば、米国電気電子 技術者協会（ＩＥＥＥ）によって発表された標準は、その８０２プロトコルにお いて、ＬＡＮのための標準を定義しており、その定義はＯＳＩモデルの下位２層 と重なり合う。 このようなモデルでは、所与の層は、ネットワークの向こう側のピア端末の同 一層と、またはネットワーク自体内のネットワーク要素の同一層と通信する。１ つの層は、通常は論理的に関連があり、その上の層の動作を可能にする１組の機 能を実施する。 本発明を説明するための関係する層は、ＯＳＩ層第１〜４層を含む。第１層は 物理層であり、構造化されていないビット・パターンを物理リンクを介して送受 信する機能を備える。物理層は、接続のサイズと形状、ビットから電気信号への 変換、ビット・レベルの同期化などの問題に関与する。ネットワーク内には複数 のタイプの物理層が存在可能である。ＩＥＥＥ標準８０２．３とＦＤＤＩ（ファ イバ分散データ・インタフェース）に、２つの一般的なタイプの第１層が記載さ れている。 第２層はデータ・リンク層であり、フレーミング、誤り検出、伝送媒体へのア クセス、および第２層に又はその下に相互接続された末端ステーション間のアド レッシングをサポートする。データ・リンク層は、典型的には、単一のホップの 両端間、すなわち１つの端末から同じサブネットまたはＬＡＮ内の他の端末まで 、情報のパケットを伝送するように作られている。 第３層はネットワーク層であり、端末間アドレッシング、ネットワーク・トポ ロジ情報、ルーティング、パケット断片化などの機能をサポートする。この層は 、その送信元から最終送信先までの最善の「ルート」でパケットを送信するよう に構成することができる。この層の他の特徴は、状況が許す場合、送信元または 送信先のネットワーク輻輳に関する情報を中継する機能である。 第４層はトランスポート層であり、電子メール・プログラムなどのアプリケー ション・プログラムに、そのアプリケーションがデータ・リンク層とインタフェ ースするために使用できる「ポート・アドレス」を供給する。トランスポート層 とそれより下位の各層との重要な相違は、送信元端末上のアプリケーションが、 ネットワーク内の任意の場所にある送信先端末上の類似のアプリケーションと会 話することができるのに対し、下位各層は、ネットワーク内のすぐ隣の端末と会 話を行う点である。第４層プロトコルは、高信頼接続指向サービスもサポートす る。このようなサービスを提供する第４層プロトコルの一例は、伝送制御プロト コル（ＴＣＰ）である。 これらの層で動作するネットワークを実施するための様々なビルディング・ブ ロックが存在する。端末は、ネットワークの端点であり、送信元、送信先、およ びネットワーク要素、または受信データを送信元から送信先まで中継するその他 の中間点として機能することができる。 最も単純なレベルにあるのは、第１層で単にビットを中継するだけの物理層リ レーである、リピータである。 ブリッジは、リピータより上の次のレベルであり、単一のＬＡＮ内でルックア ップ・テーブルを使用してパケットを中継するデータ・リンク層エンティティで ある。ブリッジは、パケットに変更を加えず、送信先に基づいてパケットを中継 するだけである。ほとんどのブリッジは、学習ブリッジである。この種のブリッ ジでは、ブリッジは、送信元を前に学習していた場合、そのパケットをどのポー トに中継すべきかをすでに知っている。ブリッジが送信先からパケットをまだ中 継していない場合、ブリッジは送信先のポートの場所を知らず、そのパケットを 着信ポートを除くすべての非ブロック化出力ポートに中継する。送信元がパケッ トをどのポートに送信しているかという知識を修得する以外には、ブリッジはネ ットワーク・トポロジについての知識を持たない。多くのＬＡＮはブリッジのみ を使用して実施することができる。 ルータは、ＬＡＮ間でパケットを中継することができるネットワーク層エンテ ィティである。ルータは、ルータがネットワークのトポロジを知ることができる ようにする他のルータと交換する情報に基づいて、送信元と送信先との間に存在 する最善のルートを使用する潜在能力を有する。「最善の」ルートに影響を与え る要因としては、コスト、速度、通信料、帯域幅、およびその他の要因がある。 ブルータは、ブリッジとしても動作することができるルータである。ブルータ が知っている第３層プロトコルの場合、ブルータはそのソフトウェアを使用して パケットの中継方法を判断する。その他のパケットについては、ブルータはブリ ッジとして機能する。 スイッチは、スイッチの構成やスイッチが第２層と第３層のいずれを実施する かに関係なく、パケットを中継する汎用ネットワーク要素である。 一般に、ＬＡＮはトポロジ階層を含まないため、ブリッジは端末の協力なしに フラットなネットワーク内でパケットを中継する。ＬＡＮがたとえば第３層の機 能をサポートするように設計されている場合、ルータを使用してＬＡＮ内の相互 接続とパケットの中継を行う。 ブリッジは、トポロジ的意味を含まないメディア・アクセス制御（ＭＡＣ）ア ドレスに基づいて中継の決定を行うため、階層ルーティング・アドレスを使用す ることができない。一般には、ＭＡＣアドレスは製造時に装置に割り当てられる 。端末数が増えるにつれてトラフィック分離、帯域幅、故障検出、および管理面 が困難になり過ぎたり、負担が大きくなり過ぎるため、ブリッジを介して相互接 続可能な端末の数は限られている。 学習ブリッジは自己設定するため、セットアップのために人間の介在を事実上 必要としない「プラグ・アンド・プレイ」エンティティになることができる。し かし、ルータは集約的な設定を必要とし、エンド・ノードにおける設定活動さえ 必要とすることもある。たとえば、ネットワークが伝送制御プロトコル／インタ ーネット・プロトコル（ＴＣＰ／ＩＰ）を使用する場合、各エンド・ノードはそ のアドレスとサブネット・マスクを操作者から手動で受け取らなければならず、 そのような情報がルータに入力されなければならない。 一般に、ネットワークの規模と複雑さが増すにつれて、ネットワークはより上 位の層の機能をより多く必要とする。たとえば、比較的小規模なＬＡＮは、リピ ータやブリッジなどの第１層の要素を使用して実施することができるのに対し、 超大規模ネットワークは、ルータなど第３層までの要素を使用する。 単一のＬＡＮは一般に、組織の要件を満たすのに不十分である。その理由は、 （１）物理層セグメントに接続可能な端末の数の限界と、（２）物理層区分のサ イズの限界と、（３）セグメントの帯域幅をすべての接続端末間で共用しなけれ ばならないために通信量が限られるという本質的な限界にある。これらの制約を 克服するために、他のネットワーク・ビルディング・ブロックが必要である。 上記で簡単に述べたように、ネットワーク内の端末の数が増えた場合、ネット ワークをサブネットワークに区分化することができる。区分化ネットワークにお ける典型的なアドレスは、サブネットワークを示す第１の部分と、サブネットワ ーク内のアドレスを示す第２の部分とを含む。これらのタイプのアドレスは、ア ドレスの第１の部分がネットワークの地理的または論理的部分を規定し、第２の 部分がサブネットワーク部分内の端末を規定するため、トポロジ情報を伝達する 。階層アドレス指定によるルーティングには、２つのステップがある。すなわち 、第１のパケットは送信先のサブネットワークに宛ててルーティングされ、第２ のパケットはサブネットワーク内の送信先に中継される。 端末は、製造時に固有データ・リンク・アドレス（ＭＡＣアドレス）が付与さ れ、それによって端末は重複アドレスを気にせずにブリッジ・ネットワーク内の 任意のＬＡＮに接続することができる。したがって、データ・リンク・アドレス はどのようなトポロジ情報も伝えることができない。ブリッジは、ルータとは異 なり、データ・リンク・アドレスに基づいてパケットを中継し、したがって階層 アドレスを解釈することができない。 現行のインターネットは、増え続けるユーザと、マルチメディア・アプリケー ションの増大する要求に対処することを余儀なくされている。将来のネットワー クは、さらに高い帯域幅とより多くのユーザと、ネットワークによるトラフィッ ク機密区分要件をサポートすることが必要になる。統計的研究によれば、ネット ワーク・ドメインと、ネットワークに接続されているワークステーションの数の 増加速度は今後、さらに速くなることがわかっている。同じ物理リンク上で異な る特性を持つ複数のトラフィック・タイプをサポートする傾向もある。このため 、より多くのネットワーク帯域幅と資源の効率的使用が必要である。必要帯域幅 を満たすために、ネットワーク上の速度は上昇傾向にあり、ギガビットの速度に 達する。 インターネットの成功と、インターネットを使用する製品およびネットワーク の数の増大のために、ネットワーク設計者はＩＳＯ第２層と第３層という特定の １つの組合せを使用することが多い。特に、典型的なインターネット関連ネット ワークでは、設計者はＩＥＥＥ８０２標準（これはＩＳＯ第１層および第２層と 重なり合う）に準拠した実施態様とインターネット・プロトコル（ＩＰ）ネット ワーク層とを組み合わせる。この組合せは、イントラネットなどの企業ネットワ ークでも一般的になりつつある。 第２層ネットワーク要素からネットワークを構築することによってこの組合せ をサポートすれば、パケット中継は高速化されるが、トラフィック分離、冗長ト ポロジ、および待ち行列化と管理（アクセス制御）のための端末間の処理方針に 関する柔軟性が低くなる。第３層の要素だけからこのようなネットワークを構築 すると、第３層のへッダを解析し、必要な場合にはパケットに変更を加えなけれ ばならないことに伴うオーバーヘッドのため、パフォーマンスが犠牲になり、階 層上の観点からも実際的ではない。さらに、第３層の要素だけを使用すると、１ サブネットにつき１台の端末を有し端末間には第２層の接続性がないアドレッシ ング・モデルを余儀なくされる。 現在、第２層と第３層の装置の組合せから構築されたネットワークが使用され ているが、パフォーマンスと柔軟性が不十分になる。特に、トラフィック分散の 変化の増大に伴い（ブラウザを使用するアプリケーションによって「サーバ」の 役割が増大する）、ルータを高速で通過する必要が重大になる。 ブリッジとルータのいずれを選択するかは、典型的に（ブリッジを使用する場 合の機能性とルータを使用する場合の速度との）重要なトレード・オフとなる。 さらに、ネットワーク内での優先順位などのサービス特性は、トラフィック・パ ターンがルータを含むか否かにかかわらず、一般には同質ではなくなっている。 このようなネットワークでは、異なるトラフィック・タイプが存在し、帯域幅、 遅延など、異なるサービス特性を必要とする。 応用分野のトラフィック要件を満たすために、ブリッジ装置は回線速度で動作 する必要がある。すなわち、ブリッジ装置は、装置にパケットに到着する速度ま たはそれより高速で動作するが、パケットをドメイン／サブネットワーク間で中 継することもできなければならない。現在のハイブリッド・ブリッジ／ルータ設 計は適切なネットワーク配信機能を達成することはできても、現在の増大する速 度要件を満たすことはできない。 サブネットワーク内でも他のネットワークに対しても第２層と第３層の両方の パケットを迅速かつ効率的に中継するスイッチまたはネットワーク要素が必要で ある。さらに、第３層パケットをワイヤ・スピード、すなわち、パケットがネッ トワーク要素に入ってくるのと同じ速度で中継することができるネットワーク要 素が必要である。さらに、サブネットワーク内での第２層中継が、第３層ルーテ ィングで使用可能な追加の機能を備えることができるようにし、優先順位や帯域 幅予約など、サブネットワーク内のアプリケーションに一定の品質のサービスを 提供することができるようにするネットワーク要素が必要である。 発明の概要 本発明は、受信パケットを１つまたは複数の適切な出力ポートに中継する多層 ネットワーク要素のためのシステムおよび方法を提供することによって、上記の 問題を実質的に克服することを可能にする。 多層ネットワーク要素の出力ポートにおける輻輳を検出して処理する一実施形 態による装置は、中央処理装置（ＣＰＵ）とスイッチング要素とを含む。スイッ チング要素は、パケットを出力ポートを介してネットワークに出力するように構 成されている。スイッチング要素は、パケット・ポインタの記憶場所を有し、出 力のためにパケットを待ち行列化する、少なくとも１つの可変長出力待ち行列を 含む。各待ち行列には、記憶場所の番号によって決められたように、待ち行列の 先頭の記憶場所を指すポインタを格納する開始レジスタと、待ち行列の終わりの 記憶場所を指すポインタを格納する終了レジスタとが関連付けられている。待ち 行列は、各待ち行列を、次に使用可能な記憶場所を指すポインタを格納する次空 きレジスタにも関連づけし、パケット・ポインタは待ち行列内に開始レジスタに よって指示された場所から始まって記憶され、次に使用可能な記憶場所が２番目 のポインタの方に移動すると次空きレジスタが増分される。各出力待ち行列は、 開始レジスタによって示された場所と終了レジスタによって示された場所との間 の記憶場所を指すしきい値ポインタを格納するプログラム可能しきい値レジスタ とも関連付けられている。 次空きレジスタ内の値が、しきい値レジスタによって指示された場所と終了レ ジスタによって指示された記憶場所を含む場所との間に論理的に位置する記憶場 所を示す場合、しきい値論理回路が輻輳信号を出力する。 この輻輳信号に応答して、ランダム廃棄論理回路が、ランダム・アーリー・デ ィスカード（ＲＥＤ）などのパケット廃棄アルゴリズムを使用して、廃棄するパ ケットをランダムに選択し、それによってしきい値を超えた後は、着信パケット がランダムに廃棄されるようにする。待ち行列が一杯になると、容量論理回路が ＣＰＵに待ち行列満杯信号を出力する。 スイッチング要素は、パケットの中継決定に関する情報を記憶する少なくとも １つのエントリを有するメモリも含む。エントリは、そのエントリに関連づけら れたパケットをカウントすべきか否かを示すように適応化されている。そのエン トリに関連づけられた着信パケットがスイッチング要素に到着すると、メモリ・ アクセス論理回路がそのエントリにアクセスする。エントリがアクセスされた回 数をパケット・カウンタがカウントしてエントリ帯域幅を示し、ＣＰＵに結合さ れたコンピュータ・プログラム機構がパケット・カウンタのカウントを予約ベー スのプロトコルの折衝値と比較し、そのエントリに関連づけられ、出力待ち行列 に入れられることになっている将来のパケットの優先順位を下げる。 本発明の他の実施形態によると、少なくとも２つの出力ポートでネットワーク 要素から出力されるマルチキャスト・パケットの複数の優先順位を扱う装置は、 異なる優先順位を有する少なくとも２つの出力待ち行列と、マルチキャスト・パ ケットのマルチキャスト・アドレスに一部基づくメモリ・アクセスに応答してマ ルチキャスト・パケットに関する中継情報を出力するように構成されたメモリと を含み、この中継情報は、マルチキャスト・パケットが各出力ポートにおけるど の出力待ち行列に宛てて送られるかを示す優先順位情報を含む。 メモリに結合された中央処理装置は、中央処理装置に結合されたコンピュータ ・プログラム機構を使用し、出力ポートの１つを介して送られるパケットの量に 基づいて優先順位情報を変更する。 メモリに結合された中央処理装置はまた、中央処理装置に結合され、ネットワ ーク要素とマルチキャスト・パケットの本来の宛先との間で伝達される情報に基 づいて優先順位情報を変更するように構成された、コンピュータ・プログラム機 構を使用することもできる。 本発明の他の実施形態によると、ネットワーク要素において待ち行列スケジュ ーリングを行う装置は、各パケットが１バイト長を有するパケットを出力するよ うに構成された少なくとも１つの出力ポートを含む。各出力ポートに関連づけら れ、各出力ポートで出力されるパケットを待ち行列化するように構成された、少 なくとも２つの待ち行列もまた用意される。 重みレジスタは各待ち行列に関連づけられ、重み付け基準に基づいて生成され た重み数値が入れられる。各出力ポートにある送信論理回路は、待ち行列選択信 号に従い、完了信号に応答して、各待ち行列内の識別されたパケットを送信する 。各出力ポートにあるスケジューリング論理回路は、待ち行列の１つを選択し、 送信論理回路に送る待ち行列選択信号を生成して、どの待ち行列が送信するかを 示す。各出力ポートにあるカウンタ論理回路は、重みレジスタを送信論理回路に よって送信されたバイト数に等しく減分し、カウンタ内の数値がゼロを表すとゼ ロ論理回路が完了信号を送信するように構成されている。再ロード論理回路は、 完了信号の後に送信されたパケット数を判断し、重み数値から完了信号後に送信 されたパケットの数を引いた値に等しい値を重みレジスタに入れる。 当業者なら以下の詳細な説明を読めば本発明のその他の実施形態も容易にわか るであろう。以下の詳細な説明では、本発明を実施するために企図された最善の 態様の例示としてのみ、本発明の実施形態を示し、説明する。後述の説明でわか るように、本発明は、他の異なる実施形態も可能であり、その詳細のいくつかは 、すべて本発明の主旨および範囲から逸脱することなく様々な明白な点で変更が 可能である。したがって、図面と詳細な説明は、本来例示的なものであり、限定 的なものではない。 図面の簡単な説明 第１図は、本発明による多層ネットワーク要素を組み込んだシステムを示す図 である。 第２図は、第１図の多層ネットワーク要素を示す図である。 第３図は、多層ネットワーク要素のスイッチング要素をより詳細に示す図であ る。 第４図は、スイッチング要素の中継論理回路をより詳細に示す図である。 第５図は、第４図のクラス論理回路をより詳細に示す図である。 第６図は、どの情報が多層ネットワーク要素を通るパケットのルートを指示し ているかを判断するのに用いられるプロセスを示す図である。 第７図は、ネットワーク要素からパケットを中継する方法を判断する際の情報 依存関係を示す図である。 第８図は、出力ポートをより詳細に示す図である。 詳細な説明 第１図に、本発明による多層ネットワーク要素を組み込んだシステムを示す。 このシステムは、多層ネットワーク要素と、様々なネットワークと、端末と、ル ータと、ブリッジとを含む。たとえば、本明細書で大まかに実施し、説明するよ うに、本発明による多層ネットワーク要素１２を組み込んだシステム１０は、ネ ットワーク１４および１６と、端末１８と、ルータ２４と、ブリッジ２６と、ロ ーカル・エリア・ネットワーク（ＬＡＮ）２８とを含む。 ブリッジ２６は、ＬＡＮ２８と端末１８のいくつかをネットワーク１４と、お よび相互に接続する。ブリッジ２６は、従来の学習ブリッジとすることができる 。ブリッジ２６は、ブリッジ２６にポート３０の１つに現れるパケットを送信す る端末１８のアドレスを追跡する。端末１８は、情報のパケットを送信または受 信することができる任意の装置とすることができる。典型的には、端末１８は、 パーソナル・コンピュータ、ワークステーション、プリンタ、サーバ、および／ またはネットワークに接続可能な他の任意の装置とすることができる。 ブリッジ２６は、最初はそのポートのうちのどのポートにパケットの送信先が あるかを知らず、パケットを適切に中継するために着信パケットをすべてのポー トに送出（フラッド）しなければならない。ブリッジ２６がすでに認識している アドレスに宛てられたパケットを受け取った後は、ブリッジ２６はどのポートが 宛先であるかを知り、それによってすべての発信ポート上にパケットを送出する 必要がなくなる。最終的に、ブリッジ２６は、ポート上で必要な送出（フラッド ）量をほとんどなくすのに十分なアドレスを学習する。当然ながら、端末１８が ブリッジ２６上のポートを変更すると随時、ブリッジ２６は端末１８のポートを 学習し直さなければならない。 ブリッジ２６は一般にはパケットに変更を加えず、ネットワーク１４のトポロ ジに関する情報を含まず、パケット・ヘッダのいくつかの部分を検査する。ブリ ッジ２６は、パケットに変更を加えず、送信元の学習と送信先への中継にしか関 与しないため、迅速に動作する。典型的には、ブリッジ２６はルックアップ・テ ーブルを使用して送信元と送信先を検索する。 ルータ２４は、ネットワーク１４をネットワーク１６に接続する。例示として １つのルータ２４しか図示されていないが、他のネットワークまたは端末１８を 接続する多くのルータが存在可能である。ルータ２４は、ネットワーク１４とネ ットワーク１６との間で必要な通信を可能にし、従来のルータであってもよい。 このようなルータは、ルート計算、パケット断片化、輻輳制御を含む、パケット を適切な送信先に中継するための第３層の機能を備える。このタイプのルータは 、たとえば、レイディア・パールマン（Ｒａｄｉａ Ｐｅｒｌｍａｎ）による「Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎｓ： Ｂｒｉｄｇｅｓ ａｎｄ Ｒｏｕｔｅｒｓ 」（Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ発行）に記載されている。ルータ２４は、パ ケットの最善のルートを判断するために、ネットワークのトポロジに関する知識 を有していなければならない。ネットワークに関するルータ２４の知識は、ネッ トワーク１４に接続されている複数のこのようなルータ２４間で受渡しされるト ポロジ情報によって得られる。 ルータ２４上で稼働するソフトウェアが着信パケットを解析し、使用されてい るプロトコルのタイプや、送信元および送信先を含む、パケットに関する様々な 特性を判断する。優先順位や、優先順位および帯域幅予約などのサービス品質（ ＱｏＳ）要素など、パケットの検査に基づくその他の判断も必要な場合がある。 ルータ２４は次に、取り出した情報を使用し、ルータ２４のメモリに記憶されて いるトポロジ情報とルート情報に基づいてパケットの次の送信先を計算する。ル ータ２４は、ＱｏＳ規則と処置も適用する。 次の送信先を計算するルータ２４のプロセスは、メモリへの多くのアクセスと 、その情報からのルートの計算を必要とする。さらに、パケットは典型的にはい ずれかの処理が行われている間に受信され、記憶される。ルータ２４がパケット に対して必要な処置を判断した後、メモリに記憶されるとき、またはルータ２４ から出るときに、パケットに変更が加えられる。ルータ２４は典型的には、ユニ キャスト・パケットのためのパケットの第２層の送信元と送信先を置き換え、パ ケットのチェックサムを更新し、パケットの存続期間に関する問題を処理する必 要がある。 従来のルータ２４が実行する機能を実行するために、ソフトウェアがメモリ記 憶場所を調べ、パケットの変更を加え、いくつかのフィールドの新しい値を計算 する。このような処置は、パケットの最善のルートの判断、ＱｏＳの特徴の提供 など、ブリッジ２６が備えるような単純なパケット中継以上の増強された機能を 実現する。しかし、従来のルータ２４では、このような処置に貴重な時間が費や される。 ネットワーク１４は、ネットワーク１４に接続されているすべての要素に通信 ルートを提供する。第１図の例では、これらの要素には、多層ネットワーク要素 １２、ルータ２４、およびブリッジ２６が含まれる。ネットワーク１４には任意 の数の要素を多くの方法で接続することができる。第１図には、１つの可能な組 合せのみが図示されている。ネットワーク１４に接続されている要素は、ネット ワーク１４が特定の規模または構成であることを必要としない。端末１８および ブリッジ２６にとって、ネットワーク１４のトポロジに関する詳細にな知識は不 要である。 本発明による多層ネットワーク要素１２は、様々な要素をネットワーク１４お よび相互に接続する。例として示すように、多層ネットワーク要素１２は、ＬＡ Ｎ２８、端末１８、およびネットワーク１４を接続する。多層ネットワーク要素 １２は、ブリッジとルータの両方の機能を兼ね備えている。多層ネットワーク要 素１２は、ルータとして機能して、パケットをその送信先にインテリジェントに ルーティングすると同時に、典型的にはルータ２４が備える関連する第３層機能 を実現するために、ネットワーク１４に関するトポロジ情報を含む。多層ネット ワーク要素１２は、ブリッジとして機能して、第２層パケットを中継するための 送信元／ポートの組合せを学習する。多層ネットワーク要素１２は、特定の第３ 層処理がブリッジ２６が備える第２層スイッチング機能と同程度に迅速に行われ るという点で、従来のブリッジ／ルータの組合せとは異なる。 第２図に、第１図の多層ネットワーク要素１２を詳細に示す。本発明の一実施 形態による多層ネットワーク要素１２は、プロセッサ３２と、プロセッサ・メモ ＩＪ３４と、スイッチング要素３６と、複数のネットワーク要素ポート３８と、 中継メモリ４０と、関連メモリ４２と、パケット・バッファ・メモリ４４とを含 む。多層ネットワーク要素１２には、複数のネットワーク要素ポート３８を使用 して端末１８、ＬＡＮ２８、およびネットワーク１４が接続されている。多層ネ ットワーク要素１２には、他の多層ネットワーク要素１２も接続することができ る。 スイッチング要素３６は、プロセッサ３２、中継メモリ４０、関連メモリ４２ 、およびパケット・バッファ・メモリ４４にも接続されている。プロセッサ３２ はメモリ３４にも接続されている。中継メモリ４０と関連メモリ４２は、スイッ チング要素３６だけでなく相互にも接続されている。 スイッチング要素３６は、中継メモリ４０および関連メモリ４２に記憶されて いる、第２層と第３層の両方の情報と、場合によっては第４層の何らかの情報も 使用して、パケット中継機能のほとんどを実行し、すべてのパケットについてル ートの計算や適切な処置の決定を行うためにプロセッサ３２に頼る必要がない。 プロセッサ３２は、スイッチング要素３６がそのための処理機能を備えていな いタスクを実行する。たとえば、新しい第３層ルートを計算しなければならない 場合、プロセッサ３２は、多層ネットワーク要素１２から到達可能なネットワー クのトポロジに関する詳細な情報が入っているプロセッサ・メモリ３４を使用す る。プロセッサ３２は、メモリ３４へのアクセスと共に、主としてソフトウェア ・プログラミング・ユニットを使用して計算を行う。スイッチング要素３６は、 中継メモリ４０と関連メモリ４２を使用して、主としてハードウェアで決定を行 う。中継メモリ４０と関連メモリ４２には、メモリ３４に入っている情報の一部 しか入っておらず、迅速なアクセスと検索のために構成されている。 第３図に、スイッチング要素３６と、そのプロセッサ３２、複数のネットワー ク要素ポート３８ａ〜３８ｎ、中継メモリ４０、関連メモリ４２、およびパケッ ト・バッファ・メモリ４４への接続を示す。スイッチング要素３６は、入力ポー ト５０ａ〜５０ｎと、中継論理回路５２と、パケット・メモリ・マネージャ５４ と、出力ポート５６ａ〜５６ｎとを含む。各入力ポート５０ｉおよび出力ポート ５６ｉは、ネットワーク要素ポート３８ｉに対応している。各入力ポート５０は 、中継論理回路５２とパケット・メモリ・マネージャ５４の両方にも接続されて いる。 所与のｉについて、入力ポート５０ｉがそれぞれの多層ネットワーク要素ポー ト３８ｉからパケットを受け取り、パケットが適正か否かを検査する。パケット の形態が適切でない場合、そのパケットは廃棄される。この初期スクリーニング を通過したパケットは、入力ポート５０ｉによって一時的にバッファリングされ る。入力ポート５０ｉが少なくとも受信パケットの最初の６４バイトをバッファ リングすると、入力ポート５０ｉはヘッダを中継論理回路５２に渡す。 中継論理回路５２は、プロセッサ３２と、中継メモリ４０と、関連メモリ４２ とに接続されている。中継論理回路５２はいくつかの機能を実行する。まず、パ ケットをスクリーニングし、たとえばパケットがサブネットワーク・アクセス・ プロトコル（ＳＮＡＰ）を使用してカプセル化されているか否か、または、パケ ットがたとえば仮想ＬＡＮ（ＶＬＡＮ）識別子によってタグ付けされているか否 かを判断する。パケットがこの２つのタイプのいずれかである場合、中継論理回 路５２はオフセット情報を使用して、さらに処理するために必要な適切な層ヘッ ダ情報を探し出す。 中継論理回路５２はまた、中継メモリ４０を探索して第２層または第３層ある いはその両方の層で一致を探し出す。この探索には、第４層のある種の情報も含 めることができる。好ましい実施形態では、中継メモリ４０は、第２層と第３層 の両方のスイッチングに関する情報が記憶され、第４層のある種の情報も保持可 能なコンテント・アドレッサブル・メモリ（ＣＡＭ）である。一致が見つかった 場合、関連メモリ４２に記憶され、中継メモリ４０内の一致エントリによって指 示されているデータが、パケットを適切な送信先に中継するためにスイッチング 要素３６が行わなければならない処置を規定する役割を果たす。 他の実施形態では、中継メモリ４０は、順次アドレス・ランダム・アクセス・ メモリを使用して実施することができる。この実施形態では、特定のキーについ てハッシュ機能が実行される。その結果のハッシュ値は、事前ハッシュされたキ ーに関連づけられたメモリ４２に入れられるアドレスになる。 他の実施形態では、中継メモリ４０と関連メモリ４２は、単一のランダム・ア クセス・メモリに含めることができる。この単一のランダム・アクセス・メモリ の一実施態様では、エントリには順次にアクセスすることができ、ハッシュ・フ ロント・エンドを必要とする。この単一ランダム・アクセス・メモリの他の実施 態様は、ＣＡＭとすることができる。 パケット・メモリ・マネージャ５４が、パケット・バッファ・メモリ４４と、 入力ポート５０ｉと、出力ポート５６ｉとに接続されている。前述のように、各 出力ポート５６ｉは、複数の多層ネットワーク要素ポート３８ｉのうちの１つに 対応する。図では別々のユニットとして図示されているが、情報はネットワーク 要素ポート３８を通って双方向に流れるため、特定の多層ネットワーク要素ポー ト３８ｉに対応する入力ポート５０ｉと出力ポート５６ｉとは密接に結合されて いる。 中継論理回路５２は、パケットをどのように処理するかを判断した後、その情 報を入力ポート５０ｉに渡す。入力ポート５０ｉがパケットをフィルタリングし ない場合、入力ポートは、パケット・メモリ・マネージャ５４に対して、パケッ ト・バッファ・メモリ４４内の空き記憶場所を指すポインタを要求する。パケッ ト・メモリ・マネージャ５４は、それに応答してパケット・バッファ・メモリ４ ４内の空き記憶空間の場所アドレスを供給する。次に、入力ポート５０ｉは、パ ケットメモリ・マネージャ５４に書込みアクセスを要求し、パケット・メモリ・ マネージャ５４にポインタとデータを送る。 場合によっては、入力ポート５０ｉは、中継論理回路５２からの指示に従って 、パケットに変更を加えなければならない。入力ポート５０ｉは、これらの変更 をパケットがパケット・バッファ・メモリ４４に記憶される前に行う。入力ポー ト５０ｉによって要求されると、パケット・メモリ・マネージャ５４は入力ポー ト５０ｉによって指定された適切なアドレス場所にパケットを入れる。次に、入 力ポート５０ｉはパケットの記憶場所に関する情報を、中継論理回路５２から入 力ポート５０ｉで受け取った情報で判断された適切な出力ポート５６に渡す。 好ましい実施形態では、この適切な出力ポートは、出力ポートを含まないこと も、１つまたは複数の出力ポートを含むこともできる。出力ポート５６ｉは、パ ケット・マネージャ５４にパケットを要求して受け取り、送信のための条件が満 たされている場合、パケットをそれに関連づけられたネットワーク要素ポート３ ８ｉに送る。場合によっては、出力ポート５６ｉはそのＭＡＣアドレスを送信元 アドレスとして送出パケットに入れなければならないことがある。入力ポート５ ０ｉに渡された中継論理回路５２からの結果によってこの状況が指示された場合 、入力ポート５０ｉはそのような指示をパケット・バッファ・メモリ４４に入れ る。出力ポート５６ｉは、この指示を検出し、パケットが出力ポート５６ｉを出 るときにそのアドレスを置き換える。したがって、スイッチング要素３６の出力 側ではパケットにわずかな変更を加えるだけで済む。 上述の実施形態によると、中継メモリ４０に第２層のスイッチングまたは第３ 層のルーティングのための一致エントリが入っている場合、多層ネットワーク要 素１２はワイヤ・スピードで動作する。ワイヤ・スピードは、所与の第１層と第 ２層の組合せがパケットを伝送することができる最大パケット・レートの速度に よって規定される。ネットワークに接続されている要素が、パケットが要素に入 ってくる速度と同じかそれ以上の速度でパケットを処理することができる場合、 その要素はワイヤ・スピードで動作している。 好ましい実施形態では、ネットワーク要素１２は、６４バイトのパケットの一 定したストリームがすべての入力ポート５０に同時に入るという最悪の場合のシ ナリオでパケットを処理する。第３層の情報が中継メモリ４０に入っていない場 合、パケットは第２層の情報を使用して中継され、次に、プロセッサ３２内のソ フトウェアによって従来の第３層の処理に従って処理される。 従来の第３層の処理とは異なり、プロセッサ３２は、新しい第３層のエントリ が学習され、作成されると、そのエントリを入れることによって中継メモリ４０ を更新することができる。新しいエントリと一致するパケットはワイヤ・スピー ドで中継される。すなわち、次のパケットが到着する前にパケットに関する中継 の決定が行われる。 本発明について第２層および第３層と第４層との組合せを使用して説明したが 、中継メモリ４０でのパケットの一部またはそのヘッダ、あるいはその任意の組 合せのためのエントリの探索と作成がこの説明から容易に考えつくことが、当業 者には明らかであろう。したがって、本発明は、ＩＳＯ標準に準拠した層の特定 の実施態様には限定されない。 第４図に、中継論理回路５２を詳細に示す。中継論理回路５２は、クラス論理 回路６０と、第２層（Ｌ２）論理回路６２と、第３層（Ｌ３）論理回路６４と、 マージ論理回路６６とを含む。入力ポート５０ｉは、クラス論理回路６０、Ｌ２ 論理回路６２、Ｌ３論理回路６４、およびマージ論理回路６６に接続する。図を 簡単にするために１つの入力ポート５０ｉしか図示されていないが、すべての入 力ポート５０が同様にして接続される。中継論理回路５２は、各入力ポート５０ ｉごとに重複せず、すべての入力ポート５０が中継論理回路５２へのアクセスを アービトレーションすることが好ましい。 Ｌ２論理回路６２は、中継メモリ４０に接続され、第２層の中継決定のために 中継メモリ４０に記憶されているエントリと突き合わせるキーの作成を行う。中 継メモリ４０の構成に応じて、キーは中継メモリ４０の全部または一部のエント リに対して適用することができる。 動作中、入力ポート５０ｉは多層ネットワーク要素ポート３８ｉからパケット を受け取り、ヘッダと入力ポート５０ｉ識別子を中継論理回路５２に送る。中継 論理回路５２は、まず、中継メモリ４０を探索し、パケットを送信している第２ 層送信元のエントリが中継メモリ４０に入っているか否かを判断する。多層ネッ トワーク要素１２が前に同じ第２層送信元からパケットを受け取っており、接続 先のポートを学習している場合、一致エントリが存在する。一致エントリがない 場合、中継論理回路５２は中継メモリ４０に送信元アドレスを含むエントリを入 れることによって学習機能を実行する。中継論理回路５２は、新しい送信元アド レスを学習したことをプロセッサ３２に通知する。場合によっては、第２層送信 元が中継メモリ４０に存在するが、着信パケットの入力ポート５０ｉとは異なる 入力ポート５０ｉに関連づけられていることがある。一致は第２層送信元と入力 ポート５０ｉの両方に依存するため、この場合、中継メモリ４０には一致エント リはない。 中継論理回路５２は、中継メモリ４０で、送信先アドレスのポートを示すエン トリも探索する。一致が見つからない場合、中継論理回路５２は、入力ポート５ ０ｉに対して、パケットをすべてのアクティブ出力ポート５６に送出するように 指示する。 好ましい実施形態における上述の第２層情報については、中継メモリ４０に送 信元のＭＡＣアドレスの値と関連メモリ４２内の対応するエントリを指すポイン タが入れられる。中継メモリ４０には、タグ付きパケットが使用されている場合 のＶＬＡＮ識別子などの追加の第２層情報も入れることができる。関連メモリ４ ２には、中継メモリ４０内の対応するエントリに関する他の情報も入れられる。 中継メモリ４０内の第２層情報は、第２層探索を行うのに必要な最小限の量の情 報に限定されることが好ましい。第２層探索では、この情報はＭＡＣアドレスと 入力ポート５０ｉのみであることが好ましいが、ＣＡＭにはタグ付きアドレッシ ングに関する任意の情報も入れることができる。 好ましい実施形態では、中継メモリ４０で第２層探索について複数の一致が可 能である。プロセッサ３２は、中継メモリ内にアドレス／ポートの組合せが存在 する場合、そのエントリが選択されるようなエントリの順序になるように保証す る。その特定の送信元／ポートの組合せが見つからない場合、ＶＬＡＮ情報を含 む一致が発生可能であり、それによって、第２層送信先探索で少なくとも、それ ぞれのエントリ中で送出（フラッド）のための出力ポート５６を定義する既知の ＶＬＡＮエントリまたは未知のＶＬＡＮエントリとの一致が見つかることになる 。 Ｌ３論理回路６４は、中継メモリ４０に接続され、第３層中継の決定のために 中継メモリ４０に記憶されているエントリと突き合わせするキーの作成を行う。 Ｌ２探索キーと同様に、Ｌ３キーは中継メモリ４０の全部または一部のエントリ に対して設けることができる。 キーを作成するために、Ｌ３論理回路６４は、パケット・ヘッダと入力ポート ５０ｉ識別子を含む入力ポート５０ｉからの情報と、クラス論理回路６０からの 情報とを使用する。マージ論理回路６６が、クラス論理回路６０、関連メモリ４ ２、パケット・メモリ・マネージャ５４、およびプロセッサ３２に接続されてい る。マージ論理回路６６は、クラス論理回路６０からの情報と、関連メモリ４２ から出力された情報を使用して、入力ポート５０ｉに対してパケットを適切な送 信先に正しく中継するために行うべきことを指示する。場合によっては、適切な 送信先がなく、パケットは廃棄される。また、マージ論理回路６６は、プロセッ サ３２が受信パケットに応答して何らかのタスクを実行しなければならないこと をプロセッサ３２に通知する場合もある。 第３層スイッチングはより複雑ではあるが、第２層スイッチングと類似してい る。中継論理回路５２が、中継メモリ４０で、Ｌ３論理回路６４によって作成さ れた第３層探索キーとの一致エントリを探索する。一致が存在する場合、マージ 論理回路６６が関連メモリ４２内の情報を使用して、入力ポート５０ｉにそのパ ケットをどのように処理すべきかを指示する。探索で一致が見つからない場合、 スイッチング要素３６はブリッジとしてパケットを中継し、パケットの全部また は一部をさらに処理するためにプロセッサ３２に渡すことができる。Ｌ３論理回 路６４は、パケット・ヘッダ、入力ポート５０ｉ、およびクラス論理回路６０か らの情報を使用して、探索キーを作成する。 クラス論理回路６０は、パケット・ヘッダ内の情報を調べて、カプセル化情報 を判断し、第３層の情報のクラスを判断する。クラス論理回路６０は第５図に詳 細に図示されている。クラス論理回路６０は、カプセル化論理回路６８とクラス 処置論理回路７０を含む。カプセル化論理回路６８とクラス処置論理回路７０の 両方に各入力ポート５０ｉが接続されている。クラス処置論理回路７０は、カプ セル化論理回路６８、Ｌ３論理回路６４、およびマージ論理回路６６に接続され ている。 カプセル化論理回路６８は、パケット・ヘッダを調べ、必要であればヘッダに 入れる第３層および第４層の情報のオフセットを判断する。カプセル化論理回路 ６８は、関連情報の場所を識別するためにパケットに入れるオフセットを判断す るクラス・フィルタを含む。好ましい実施形態では、１つのフィルタはＩＥＥＥ Ｅ８０２．３標準イーサネット・ヘッダに準拠した実施態様を認識し、他のフィ ルタはＩＥＥＥ標準８０２１ｑタグ付きイーサネット・ヘッダに準拠した実施態 様を認識し、さらに他のフィルタはＬＣＣ ＳＮＡＰカプセル化を認識する。他 のカプセル化も当業者なら容易にわかるであろうし、追加のカプセル化フィルタ を使用して実施可能である。カプセル化論理回路６８は、カプセル化オフセット をクラス処置論理回路７０に渡し、それによってクラス処置論理回路７０がパケ ット内のどこから適切なフィールド情報を引き出せばよいかを知ることができる ようにする。 クラス処置論理回路７０は、パケットがどのクラスに属するかを判断する。ク ラスは、Ｌ２とＬ３の両方の論理回路が探索を支援するためと、多層ネットワー ク要素１２の機能を追加するために使用する。Ｌ２論理回路６２は、すべての第 ２層探索に単一のクラスを適用する。それに対して、第３層は、複数のプログラ ム可能クラスを有する。 クラスは、クラス・タイプの定義を容易にし、各クラスごとに、Ｌ３論理回路 ６４によって第３層探索キーが作成される際にパケット・ヘッダから使用すべき バイトと、その優先度と、中継メモリ４０内で第３層の一致が発生しなかった場 合にどうすべきかを定義するデフォルト・クラス結果とを定義するのを容易にす る。 好ましい実施形態では、一致がない場合に可能な結果は４通りある。第１に、 ヘッダがプロセッサ３２に送信される。これは、第３層フローを識別する可能性 がある場合に企図される。第２に、パケット全体がプロセッサ３２にコピーされ る。これは、最初にユニキャスト・ルートを設定するとき、または最初に特定の ルートまたはフローを調べることによってファイヤウォール保護を設けるため、 または探索キーを作成するために必要な情報がパケットのどこにあるかが不明な 場合に企図される。第３に、中継のために第２層の結果を使用する。第４に、パ ケットを廃棄する。当業者なら容易にわかるように、ネットワークの構成または 使用されている特定のプロトコルによってはその他の処置も可能である。 クラスが考慮に入れる基準としては、クラスがアドレス依存とアドレス独立の いずれとみなされるかという基準がある。クラス識別子を加えることによって、 スイッチング要素３６は変化するネットワーク状況に応答することができ、中継 メモリ４内の情報の編成と記憶が大幅に単純化される。 クラス論理回路６０によって識別可能なアドレス独立クラスの代表的な例とし ては、アドレス解決プロトコル（ＡＲＰ）、インターネット・グループ管理プロ トコル（ＩＧＭＰ）、逆ＡＲＰ（ＲＡＲＰ）、グループ・アドレス登録プロトコ ル（ＧＡＲＰ）、プロトコル独立プロトコル（ＰＩＭ）、および予約プロトコル （ＲＳＶＰ）がある。アドレス依存クラスの代表例としては、ＴＣＰフロー、非 断片化ＵＤＰフロー、断片化ＵＤＰフロー、ハードウェア・ルータブルＩＰ、お よびＩＰバージョン６がある。当然ながら、その他のプロトコルも同様に認識可 能である。 クラス論理回路６０は、すべての着信パケットについて明白なクラス結果を出 力する。認識されないプロトコルの場合でも、クラス論理回路６０は、クラス結 果を出力するが、そのクラス結果は認識されないプロトコルを示し、そのタイプ のクラスのパケットに対してどのような処置を行うべきかを示す。 一般に、第３層フローはアドレス依存であり、トラフィックの単なるクラス以 上の情報を含む。プロセッサ３２によって中継メモリ４０に追加情報が入れられ ている場合、中継メモリ４０内に特定のクラスのエントリが複数ある場合がある 。プロセッサ３２は、一致したエントリのうち、最も適切なエントリが使用され るエントリになるように保証する。特定のクラス内で実現されるパケットのタイ プに応じて、最も適切な一致に関する基準はクラスごとに異なる。中継メモリ４ ０内に複数の一致エントリがあることによって可能になる柔軟性は、特定のフロ ーに対して最善の一致が得られるように保証することによってさらに強化され、 この特徴のために、同じタイプのクラス内でのパケットに対して異なる処置が可 能になる。 好ましい実施形態では、プロセッサ３２は、新しい第３層を入れるときに、メ モリ内で特定の探索基準について最善の一致が最も早く発生するように、第３層 エントリを順序づけし直す。当業者なら、これと同じ結果を達成するための多く の異なる実施態様がわかるであろう。好ましい一実施形態では、プロセッサ３２ は、特定のクラス内で一致の可能性のある最も長いキーを持つエントリが、メモ リ内の最上位すなわち最も早い場所にくるように保証する。しかし、プロセッサ ３２は、最も長い一致エントリより上位にエントリを配置し、それによって特定 のトラフィック・パターンについて、最も重要な一致が多くのキーと一致するエ ントリとなるようにすることもできる。たとえば、特定のクラスについて、「ｈ ｔｔｐ」などのアプリケーション・ポートに基づき、かつその他の情報にはまっ たく基づかずに一致するエントリは、第４層アプリケーションだけよりも多く一 致する可能性のあるエントリより優先される。他の例は、クラス・タイプ内で特 定の送信元について一致を強制することである。これは、操作者が特定のサーバ から送られるパケットに、送信先または第４層アプリケーションに関係なく高い 優先順位を与えたい場合に行うことができる。 好ましい実施形態では、マージ論理回路６６が入力ポート５０ｉに対してパケ ットに以下の処置のうちの１つを行うように指示する。すなわち、パケットのフ ィルタリング、パケットを第２層で中継、パケットを第３層フローとして中継、 パケットを第３層ルートとして処理、およびパケットをマルチキャスト・ルート として中継する処置である。マージ論理回路６６が入力ポート５０ｉに対してフ ィルタリングするように指示するパケットは、サポートされていないと判断され た特定のヘッダ情報を含むパケットである。パケットが第２層で中継されるクラ スの例としては、断片化ＵＤＰフローと、ヘッダ情報が未知であることを示すク ラスがある。断片化ＵＤＰは、最初のパケットの後、断片化されたパケットが第 ４層ヘッダ情報、たとえばＵＤＰポートからの関係する情報を全部は含んでいな いため、第２層情報を使用して動作する。第２層中継は、特定のクラスに応じて 、アドレス独立クラスの場合は任意選択となる。 マージ論理回路６６は、入力ポート５０ｉに対し、ＴＣＰまたは非断片化ＵＤ Ｐフローに第３層フロー情報を使用するように指示する。フローは、多層ネット ワーク要素１２が接続されているサブネット内で中継されるパケットであり、中 継時にヘッダ変更が不要である。それに対して、ルートは、サブネットの外部の 送信元から送られるパケットまたはサブネットの外のアドレスに宛てられたパケ ットであり、そのために中継の前に多層ネットワーク要素１２によって変更しな ければならない。好ましい実施形態では、パケットがクラス・ハードウェア・ル ータブルＩＰのパケットであることをクラスが示している場合、マージ論理回路 ６６からパケットを第３層ルートとして中継する指示が送られる。言い換えると 、着信パケットの送信先が多層ネットワーク要素１２のクラス論理回路６０によ って認識され、次に多層ネットワーク要素１２はそのパケットを、ルーティング ・プロトコルによって決まる次のホップ送信先に中継しなければならない。当業 者なら、本発明から、このようなタイプの結果が望ましいその他の状況も容易に わかるであろう。 本発明の１つの特徴は、フローをブリッジすることができる機能、すなわち、 中継メモリを使用し、ネットワーク要素１２を介して第２層パケットを第３層の 機能を使用して迅速に中継することができる機能である。ある種のフローはこの タイプの活動に特に適しており、そのようなフローには、静的フロー、自己検出 フロー、およびＲＳＶＰなどの予約プロトコルによってセットアップされたフロ ーが含まれる。静的フローとは、ネットワーク要素１２の操作者によって事前に セットアップされたフローであり、選択された第２層ネットワーク・トラフィッ クのために第３層機能を規定し、経時変化を受けない。自己検出フローは、アプ リケーションのタイプによって変わる。 最初は、一致する第３層エントリがないため、これらのフローは第３層機能を 使用せずにブリッジされる。パケット・ヘッダが検査のためにプロセッサ３２に 送られる。プロセッサ３２は、パケットを分析し、プログラムされたヒューリス ティックに基づいて、中継メモリ４０内にそのパケット・タイプのための第３層 エントリを作成するか否かとその方法を判断する。たとえば、「ピン」パケット は、せいぜい一時的パケットであるため、第３層フローエントリの作成に値しな い。 ＲＳＶＰのようなプロトコルは、ネットワークの特定のサービス機能を予約す るように機能し、いくつかのパケットがそれと同じ経路をたどることを通知する 。この場合、予約プロトコルを使用してアプリケーションにサービスを提供して 第２層で中継するが、多層ネットワーク要素１２を介して必要なクラスのサービ スを保証するための優先順位のような、第３層またはそれ以上の層の機能を追加 する。 第６図に、マージ論理回路６６がクラス論理回路６０と関連メモリ４２からの 情報を使用して生じさせる好ましい結果を示す。現在のところ好ましい結果は、 ３通りあり、（１）第２層中継結果の使用、（２）第３層中継結果の使用、およ び（３）第３層結果を使用すると同時に、第２層トポロジを使用することである 。場合によっては、識別されたクラスがあることもあるが、中継メモリ４０には 一致エントリがなく、その場合、そのクラスのデフォルトの処置が使用される。 第３層のデフォルト結果の使用は、第３層中継結果の使用のサブセットとみなす ことができることに留意されたい。 ファイヤウォール技法によって設けられる保護などの保護を設けるように、あ るクラス・タイプのパケットにデフォルトの結果を設定することができる。ファ イヤウォール・アプリケーションでは、多層ネットワーク要素１２は定義された クラスのパケットを後の処理のためにプロセッサ３２に宛てて送るようにプログ ラムされる。 第６図を参照すると、クラス論理回路６０が、パケットが認識されていないク ラスのパケットであると判断した場合（ステップ１１２）、パケットは第２層の 結果を使用して処理される（ステップ１１４）。パケットのクラスが認識されて おり（ステップ１１２）、関連メモリ４２またはクラス論理回路６０が、第２層 結果が強制されることを示している場合（ステップ１１６）、他のいかなる情報 にも関係なく第２層結果が使用される（ステップ１１８）。 第２層探索の結果として第２層結果が強制されず（ステップ１１６）、第３層 キーとの一致がある場合（ステップ１２０）、第３層情報を調べて第３層情報が 第２層ポートの決定を強制するか否かを判断する（ステップ１２２）。第３層情 報が第２層中継の結果を強制する場合、出力ポートは第２層探索の結果によって 決定されるが、ＱｏＳ要素などの第３層探索の結果内にあるその他の情報が適用 される（ステップ１２４）。第３層結果が、第２層中継結果の強制を要求しない 場合、第３層結果が入力ポート５０ｉに渡される（ステップ１２６）。ステップ １２０で第３層の一致がない場合、クラス論理回路６６によって生成されたその クラスのためのデフォルトの処置が入力ポート５０ｉに渡される（ステップ１２ ８）。Ｌ３クラスのデフォルト処置を使用する場合、パケットが入力ポート５０ ｉによっていずれの出力ポート５６にも中継されずにプロセッサ３２に送られる ことも企図される。 したがって、クラスが認識され、第３層探索で一致エントリがあった場合、第 ２層出力ポートの結果を使用することを意味していたとしても、第３層探索によ って規定された処置が入力ポート５０ｉに対する命令を左右する。それ以外の場 合は、パケットは第２層結果を使用して処理され、所望の場合、パケットまたは パケットのヘッダが後の第３層情報の処理のためにプロセッサ３２に送られる。 関連メモリ４２から送られる第３層一致の情報が強制第２層結果を示している 場合、第２層結果を使用してパケット中継が行われるが、それでもサービス品質 に関係する情報は第２層中継決定に対して実施される。このようにして、多層ネ ットワーク要素１２は、同じサブネットまたはＶＬＡＮ内での第２層ブリッジン グまたはルーティングにサービス品質要素を適用することができるようにするこ とによって、通常の第２層ブリッジ以上の追加の機能を加えることができる。 したがって、入力ポート５０ｉは中継論理回路５２に受信パケットのヘッダと そのポート指定を渡す。中継論理回路５２の出力は、ヘッダ情報と着信ポートに よって異なり、入力ポート５０ｉがパケットメモリ・マネージャ５４と協同して パケットをパケット・バッファ・メモリ４４に記憶すべきか否か、特定の出力ポ ート５６ｉでパケットに優先順位を関連づけるべきか否か、および入力ポート５ ０ｉがパケットをパケット・バッファ・メモリ４４に渡す前にヘッダ置換などの 変更をパケットに加えるべきか否かを示す。したがって、出力ポート５６ｉは、 たとえばユニキャスト・パケットまたはマルチキャスト・パケットをルーティン グする場合にＭＡＣアドレスを挿入することと新しいパケット・チェックサムを 計算することを除き、ヘッダに変更を加える必要がない。 中継メモリ４０内の第２層および第３層の情報は、探索に適用されるときに相 互に独立している。第２層エントリに含まれる情報の中には、第３層エントリで 重複するものがある場合がある。さらに、第３層エントリには、ＵＤＰポートや ＴＣＰポートなどの第４層の何らかの情報が含まれることもある。当業者なら、 他のヘッダ層またはパケット本体からの他の情報を含めることによって追加可能 なその他の機能も容易にわかるであろう。そのような機能も本発明の範囲に入る ものとみなされる。第２層と第３層の両方の探索が完了した後、マージ論理回路 ６６は入力ポート５０ｉがそのパケットにどのような処置を行うべきかを判断す る。 送信元アドレス、またはトポロジの変更の結果として発生する可能性のある変 更の第２層学習は、第２層送信元探索の一部としてプロセッサ３２に伝えられる 。前述のように、第２層情報には、仮想ＬＡＮ（ＶＬＡＮ）情報をサポートする ために使用する情報のようなタグ付き情報を含めることができる。ＶＬＡＮ情報 を使用した場合、第２層の送出を特定のＶＬＡＮまたは特定のタグ付けに関連づ けられたポートのみに制限するのに役立つ。 関連メモリ４２内の各エントリは、以下のような結果に関する情報を含むこと ができる。エントリには、パケットの全部または一部をプロセッサ３２に送るべ きか否かを含めて、パケットの出力ポート５６を示す標識が含まれる。エントリ は、必要なら、たとえばマルチキャスト・アドレッシングをサポートするために 複数のポート５６ｉを指定することができる。エントリは、出力ポート５６にあ る出力待ち行列の数にマップするパケットの優先順位も含む。また、エントリは 、出力ポート５６がパケットを送信する際にベスト・エフォートを使用すべき標 識も含む。ベスト・エフォートは、パケットの送信またはサービス品質に対する 保証が与えられないことを意味する。当業者なら、本発明はその他のサービス品 質にも等しく適用されることが容易にわかるであろう。 エントリは、たとえば、発信パケットに新しいタグを適用すべきか否か、いつ 適用すべきか、ＶＬＡＮ間のルーティングが着信タグとは異なる送出タグを必要 とするか否か、必要であればそのタグはどのようなタグでなければならないかを 示すこともできる。 エントリは、送信元および送信先の経時変化に関する情報も含む。送信元経時 情報は、送信元がアクティブか否かを示す。好ましい実施形態では、この情報は 第２層送信元アドレスが突き合わせされるたびに中継論理回路５２によって更新 される。この情報は、ＩＥＥＥ標準８０２．１ｄタイプのアドレス経時変化に従 って実施される。ネットワーク要素１２における送信先経時変化は、どの第２層 エントリおよび第３層エントリがアクティブであるかを示す。エントリの情報は 、第２層の送信先探索または第３層のエントリの突き合わせサイクルによって、 エントリが突き合わせされるたびに更新される。 エントリは、入力ポート５０ｉによる中継に第２層結果を使用すべきか否かも 示す。前述のように、第２層情報は第３層エントリに対して強制することができ るが、第２層中継情報のほかに、第３層機能を第２層中継に加えることができる 。 エントリは、静的エントリを定義することもできる。静的エントリは、第２層 学習の対象にはならず、決して経時変化しない。 第３層のエントリは、追加の情報を含むことができる。エントリは、最初の６ ４バイトのパケットのみを以降の処理のためにプロセッサ３２に送るべきである ことを示すことができる。エントリは、パケットがマルチキャスト・ルーティン グの一部であるか否かを示すことができる。マルチキャスト・ルーティングの一 部である場合、入力ポート５０ｉはヘッダ・チェックサムを減分し、パケットを 指示された出力ポート５６に中継し、出力ポート５６ｉがパケットの第２層送信 元アドレスを出力ポート５６ｉのＭＡＣアドレスに置き換える必要があることを 示す必要がある。他のタイプのヘッダの変更については、適切なルーティングを 実施する当業者には容易に明らかとなろう。 関連メモリ４２内のエントリは、ユニキャスト・ルーティングにおける着信送 信先を置き換えるために使用する次のホップ送信先アドレスを含むこともできる 。ユニキャスト・ルートでは、着信パケットはその送信先アドレスを多層ネット ワーク要素１２として有している。 マージ論理回路６６は、Ｌ２論理回路６２およびＬ３論理回路６４によって行 われた中継メモリ４０の探索の結果を待たなければならない。好ましい実施形態 では、第２層と第３層の情報は同じ中継メモリ４０に記憶されるが、別々のメモ リに記憶することもできる。前述のように、好ましい実施形態は中継メモリ４０ を、キーのフィールドと一致するＬ２およびＬ３論理回路によって使用される情 報を記憶するように制限させて、中継メモリのサイズを小さくする。したがって 、エントリに関する追加情報は関連メモリ４２に記憶される。中継メモリ４０内 の各エントリは、関連メモリ４２内の対応するエントリを指し、関連メモリ４２ がその内容を中継の決定を行うためにマージ論理回路６６に供給する。 第７図に、中継論理回路５２で行われるステップを示す。第７図は、中継論理 回路５２の動作の好ましい実施形態を示しているが、当業者なら、これと同じタ スクを行う他の同等の方法も容易にわかるであろう。入力ポート５０から中継論 理回路５２で情報を受け取る（ステップ２００）。一方の経路で、Ｌ２論理回路 ６２が第２層探索に必要な情報を判断し、中継メモリ４０に対してその探索を行 う（ステップ２０２）。ステップ２０４で、Ｌ２論理回路６２と中継メモリ４０ が、パケットの送信元の一致エントリがあったかどうかを判断する（ステップ２ ０４）。中継メモリ４０にその送信元アドレスが入っていない場合、その送信元 アドレスが学習される（ステップ２０６）。送信元アドレスを学習するために、 Ｌ２論理回路６２と中継メモリ４０は、中継メモリにエントリを入れることを保 証する。この新しい情報を検査するようにプロセッサ３２に信号が送られる。 その送信元アドレスが中継メモリ４０内にすでにあり、着信入力ポート５０と 一致する場合、Ｌ２論理回路６２は送信先アドレスと中継メモリ４０との突合わ せを試みる（ステップ２０８）。送信元アドレスが中継メモリ４０になかった場 合、または送信元アドレスがメモリに入っていたがポートが異なる場合、ステッ プ２０６でこの送信元アドレスとポートの組合せが学習されてから、ステップ２ ０８で送信先の探索を試みる。 ステップ２００からの他方の経路で、クラス論理回路６０がステップ２１０で クラスを判断する。クラス論理回路６０がクラスを判断し、それをＬ３論理回路 ６２に渡した後、Ｌ３論理回路は第３層エントリについて中継メモリとの突き合 わせを試みる（ステップ２１２）。 ステップ２１４で、マージ論理回路６６がステップ２０８のＬ２探索からの情 報と、ある場合にはステップ２１０からのクラス論理回路の結果と、ステップ２ １２からの第３層探索結果とを使用し、第６図の基準に基づいて適切な中継の決 定を行う。ステップ２１４でマージ論理回路６６が適切な中継決定を行うと、そ の結果が入力ポート５０ｉに渡される（ステップ２１６）。 第７図には、２つの経路を下にたどる流れが示されている。第２層探索と第３ 層探索は独立しているため、実際のメモリ探索以外はすべてパイプライン化され るかまたは並列して行われる。好ましい実施形態では、クラス論理回路６０、Ｌ ２論理回路６２、およびＬ３論理回路６４による処理は、並列またはパイプライ ン方式で進めることができる。ただし、依存関係のためにそのような処理ができ ない場合は除く。たとえば、Ｌ３論理回路６４は、第３層探索のための探索キー を作成するためにクラス論理回路６０からの出力を必要とし、マージ論理回路６ ６は、第６図に従って第２層探索と第３層探索が結果のマージを完了しているこ とを必要とする。 しかし、他の実施形態では、Ｌ２情報とＬ３情報は別々のメモリに入れること ができる。その場合、Ｌ２探索とＬ３探索を同時に行うことができる。 マージ論理回路６６がパケットに対する処置を決定した後、パケットをフィル タリングしない場合、または破棄されない場合、入力ポート５０ｉはパケット・ マネージャ５４に対して書込み要求を行う。入力ポート５０ｉがパケット・マネ ージャ５４に対して書込み要求を行う前にパケット全体を受け取る必要はない。 入力ポート５０ｉは、パケット・マネージャ５４に、パケットの着信部分を記憶 するアドレスと、パケットを出力する出力ポート５６数と、パケットの優先順位 とを渡し、その後、適切な出力ポート５６にポインタを送る。入力ポート５０ｉ は、パケットを入れることができるパケット・バッファ・メモリ４４内の空き記 憶場所を指すポインタを受け取る。入力ポート５０ｉは、書込み要求を行う前に パケット・バッファ・マネージャ５４からポインタを入手していることが好まし い。 出力ポート５６ｉは、ポインタをパケット送信のための出力待ち行列に格納す る。待ち行列が送信のためのポインタを示すと、出力ポート５６ｉはパケット・ マネージャ５４に対してポインタ・アドレスに記憶されている内容を要求し、そ の内容を多層ネットワーク要素１２の対応するネットワーク要素ポート３８から 送信する。パケット・マネージャ５４は、特定のポインタを使用するすべての出 力ポート５６がそのポインタに関連づけられた内容を送信したか否かを追跡し、 送信した場合、メモリ空間が将来の使用のために解放される。 ネットワーク要素１２内のパケットは、パケットが物理媒体を介して次の送信 先または最終送信先に送られる前に各出力ポート５６ｉでバッファリングされる 。入力ポート５０ｉと出力ポート５６ｉの両方での待ち行列化は、ポインタに基 づく。これらの各ポインタは、パケットが記憶されているパケット・バッファ・ メモリ４４内の記憶場所を指す。ポインタは入力ポート５０ｉから適切な出力ポ ート５６に渡される。各出力ポート５６ｉは、パケットが送信されるときに、ポ インタで指された場所の内容をパケット・メモリ・マネージャ５４に要求する。 マルチキャスト・パケットの場合、パケットの１コピーだけが、パケットの送信 先の出力ポート５６数のカウントと共にパケット・バッファ・メモリ４４内に保 持される。 各出力ポート５６ｉは複数の出力待ち行列Ｑｉを有する。好ましい実施形態で は、各出力ポート５６ｉは３個の待ち行列を備える。しかし、本発明で実施され る概念は、特定の数の出力待ち行列には限定されない。当業者なら、ハードウェ ア実施待ち行列が様々な方法で実施可能であることがわかるであろうが、好まし い実施形態は、各出力ポート５６ｉに、単一の物理待ち行列を備え、その物理待 ち行列をｎ個、好ましくは３個の論理待ち行列に分割する。 第８図に、出力待ち行列Ｑｉの論理図を含む出力ポート５６ｉの詳細図を示す 。第８図には、出力待ち行列Ｑ１．．．Ｑｉ．．．Ｑｎが図示されている。各待 ち行列Ｑｉは、指示されると待ち行列Ｑｉによって指示されたパケットを送信す る送信論理回路３００に接続されている。 各待ち行列は、待ち行列の開始と終わりを示す一対のポインタ・レジスタを有 する。各待ち行列Ｑｉごとに、Ｑｉｓｔａｒｔに開始Ｑｉの場所が記憶され、Ｑ ｉｅｎｄに待ち行列Ｑｉの終わりの場所が記憶される。 １出力ポート５６ｉにつき可能なポインタの最大数はハードウェア記憶量によ って制限され、好ましい実施形態では１Ｋである。しかし、本発明で実施される 概念は、特定の記憶場所最大数には限定されない。ポインタ記憶場所の最大数は 特定の実施態様について制限されるが、最大数の記憶場所を共用する待ち行列の サイズは可変である。たとえば、好ましい実施形態では、物理待ち行列内の記憶 場所の数は１Ｋに制限されるが、ｎ個の待ち行列自体のサイズは合計１Ｋになれ ばよい。このようにして、各論理待ち行列Ｑｉは異なるサイズとすることができ る。 論理待ち行列Ｑｉ間での１Ｋの記憶場所の相対的な分散は、出力ポート５６ｉ ごとにプロセッサ３２によってプログラム可能である。相対的分散は、随時プロ セッサ３２によって（トラフィック・フローに応じて）変更することができ、こ の変更は、影響を受ける待ち行列領域が空になってポインタを再割り当てするこ とが可能になるとただちに有効になる。 １出力ポート５６ｉにつき複数の出力待ち行列を設けることによって、トラフ ィックを必要なサービス品質（ＱｏＳ）タイプの機能およびその他の要因に対応 づけることができる。ネットワーク要素１２の待ち行列化の柔軟性は、（１）出 力ポート５６ｉにおける複数の待ち行列Ｑｉへの分類、（２）待ち行列からの送 信のスケジューリング、および（３）輻輳時のＱｉ動作の出力ポート５６ｉごと のプログラム可能性によって得られる。 異なる待ち行列へのパケットの分類は、中継論理回路５２によって入力ポート ５０ｉに出力されるグローバル優先順位情報の結果として行われ、入力ポート５ ０ｉはこのグローバル優先順位情報を出力ポート５６ｉに渡す。グローバル優先 順位情報は各パケットに関連づけられ、関連メモリ４２内に関連づけられたデー タの一部として入れられる。グローバル優先順位情報は、ＶＬＡＮタグ内にある 優先順位情報からマップすることができ、ＩＥＥＥ８０２．１Ｑ標準に基づくこ とになる。 出力ポート５６ｉは、やはり関連メモリ４２内にあってパケットに関連づけら れたＢＥ（ベスト・エフォート）強制情報によってベスト・エフォートによるグ ローバル優先順位情報の無効化を指示されていない限り、このグローバル優先順 位情報を使用して所与のパケットの中継先の待ち行列Ｑｉを判断する。ＢＥ強制 情報が無効化を指示している場合、そのパケットは低優先順位待ち行列に送られ る。ＢＥ強制の実施は、出力ポート５６ｉごとのベスト・エフォートの強制を可 能にする。好ましくは、これは関連メモリ４２内にエントリに関連づけられたＢ Ｅ強制フィールドを備えることによって行われ、このフィールドは各出力ポート ５６ｉの標識を有する。好ましい実施形態では、これは１出力ポート５６ｉにつ き１ビットを使用して実施される。 出力ポート５６ｉ内には、グローバル優先順位情報を入力ポート５０ｉからの ポインタを記憶するための待ち行列選択信号に変換するマッピング論理回路３０ ２が含まれる。 グローバル優先順位情報は、３ビットの関連メモリ４２エントリフィールドに 入れられる。この３ビットはマッピング論理回路３０２に渡され、マッピング論 理回路３０２は待ち行列選択信号を出力する。バッファ・メモリ４４から出力ポ ート５６ｉに入るパケットに関連づけられた３グローバル優先順位ビットは、パ ケットの適切な出力待ち行列を判断するためにマッピング論理回路３０２によっ て２ローカル優先順位ビットにマップされ、次に、マッピング論理回路３０２は 待ち行列選択信号を生成する。このマッピングは、マッピング論理回路３０２内 にある２つのプログラム可能待ち行列優先順位しきい値によって決定される。第 １のプログラム可能優先順位しきい値レジスタＰＴＲ１に第１のしきい値が格納 され、第２のプログラム可能優先順位しきい値レジスタＰＴＲ２に第２のしきい 値が格納される。マッピングは、プロセッサ３２がしきい値レジスタＰＴＲ１、 ＰＴＲ２内の値を変更することによってプログラム可能である。 以下のように、ｎ＝３としてＱ１〜Ｑｎのためのしきい値を使用して３ビット のグローバル優先順位が２ビットのローカル優先順位にマッピングされる。 ｐ＜ＰＴＲ１の場合、グローバル優先順位＝０１ ｐ＞＝ＰＴＲ１かつｐ＜ＰＴＲ２の場合、グローバル優先順位＝１０ ｐ＞＝ＰＴＲ２の場合、グローバル優先順位＝１１ である。上記で、ｐはグローバル優先順位フィールドの値である。 ローカル優先順位は以下のように３つの出力待ち行列にマッピングされる。 ００−−−−−不使用（予約） ０１−−−−−Ｑ１−−−−−＞低優先順位のＢＥ待ち行列 １０−−−−−Ｑ２ １１−−−−−Ｑ３−−−−−＞高優先順位待ち行列 上記で好ましい実施形態のマッピングについて説明したが、当業者なら、パケ ットに関連づけられたグローバル優先順位を出力ポート５６ｉ内の複数の待ち行 列にマッピングするという結果を得る変形態様が容易にわかるであろう。 出力ポート５６ｉはスケジューラ３０４も含む。スケジューラ３０４の目的は 、出力ポート５６ｉ内で送信のための各待ち行列Ｑｉに一定したレートを割り振 ることである。スケジューラ３０４は特定の出力ポート５６ｉに関連づけられて いるため、ネットワーク要素１２は出力ポート５６ｉごとに異なるスケジュール をプログラムすることができる。 好ましい実施形態では、ネットワーク要素１２は厳密な優先順位方式と重み付 きラウンド・ロビン優先順位方式の両方をサポートする。各出力ポート５６ｉ内 の各待ち行列には、３つのプログラム可能レジスタが関連づけられており、それ らのレジスタにはそれぞれの関連する待ち行列に使用される重みが入れられる。 説明を簡単にするために、以下の説明と第８図では、待ち行列Ｑｉの場合の関 係のみを例示した。この説明は、すべての待ち行列にそのまま適用される。また 、この説明全体を通じて、前述のように３つの待ち行列を仮定しているが、この 方式をそれより多くの待ち行列に拡張することは簡単である。 厳密優先順位スケジューリング方式を実施する際には、スケジューラ３０４は 、より高い優先順位の待ち行列にパケットが入っている限り、より低い優先順位 の待ち行列を処理しない。これは、最高優先順位待ち行列によってより低い優先 順位の待ち行列が不利益を被ることを意味する。ネットワーク要素１２はまた、 代替策として重み付きラウンド・ロビン方式を用意している。 重み付きラウンド・ロビン方式では、各待ち行列Ｑｉに重みＷｉが関連づけら れており、この重みは、１ラウンド中に送信されるパケットの数を記憶する関連 づけられた重みレジスタに記憶されている。スケジューラ３０４は、各待ち行列 Ｑｉをポーリングし、Ｗｉ個のパケットを処理してからラウンド内の次の待ち行 列である待ち行列Ｑ（ｉ＋１）を処理する。所与の重みＷｉをパケット数として 例示したが、別法として、Ｗｉをバイト数とすることも考えられる。この方式は 、各待ち行列Ｑｉにそれぞれの重みに比例したレートを与えようとするものであ る。しかし、重みが多いとサービス・サイクル時間が増え、その結果、最悪の場 合にパケット遅延が生じるため、柔軟性と待ち行列Ｑｉに付随するパケット遅延 とはトレードオフの関係にある。 パフォーマンスを向上させるために、スケジューラ３０４はフレーム構造に従 った重み付きラウンド・ロビン方式を実行する。スケジューラ３０４は、１フレ ームを含む数ポーリング・ラウンドにわたってレートの強制を試みる。フレーム 長は、出力ポート５６ｉ内の待ち行列Ｑｉの重みの累積合計よりもはるかに小さ くすることができる。これは、最悪の場合の遅延が少なくなるという利点がある 。 出力ポート５６ｉが３つの待ち行列Ｑｉを含む場合のフレーミング方式の一例 として、待ち行列Ｑ１が重み２を有し、待ち行列Ｑ２が重み４を有し、待ち行列 Ｑ３が重み６を有する場合、通常のラウンドでは待ち行列Ｑ３の６個のパケット を処理し、次に待ち行列Ｑ２の４個のパケットを処理し、最後に待ち行列Ｑ３の ２個のパケットを処理する。フレーム手法を使用して、１ラウンドを２フレーム で構成することができる。したがって、このラウンドでフレーム１、すなわち、 待ち行列Ｑ３の３個のパケットと、待ち行列Ｑ２の２個のパケット、待ち行列Ｑ １の１個のパケットとを処理し、次に、フレーム２、すなわち待ち行列Ｑ３の３ 個のパケットと、待ち行列Ｑ２の２個のパケットと、待ち行列Ｑ１の１個のパケ ットとを処理する。上述のように、フレーム数の選定はプログラム可能であり、 所望の結果に基づく。 パケットは非プリエンプティブに処理される。すなわち、パケットの送信に割 込みがない。各Ｑｉに送信レジスタＴＸｉが付随している。ＴＸｉレジスタは、 フレーミングを使用する場合、現行ラウンド中、またはフレームに当該待ち行列 から送信可能なバイト数を保持する。 スケジューラ３０４は、待ち行列Ｑ１を処理し、伝送されたバイト数に従って 送信レジスタＴＸｉレジスタを、このレジスタの値がゼロまたはゼロ以下になる まで減分する。その後、スケジューラ３０４はラウンド中、またはフレーム中の 待ち行列Ｑ（ｉ＋１）の処理を開始し、処理したばかりの待ち行列ＱｉのＴＸｉ レジスタにＷｉレジスタ内の値によって示されたバイト数を加えることによって 、Ｔｘｉレジスタの更新も行う。Ｔｘｉレジスタは、送信バイト数をパケット境 界に位置合わせするため、ゼロ未満までカウントする。すなわち、パケットの送 信を完了するバイト数によって、ＴＸｉレジスタ内の値がゼロ未満に下がる場合 であっても、待ち行列Ｑｉはパケットの送信を完了することができる。この機構 によって、スケジューラ３０４は後続のラウンド、またはフレーム中の待ち行列 Ｑｉのために、現行ラウンドまたはフレーム中のオーバーランを計算に入れるこ とができる。Ｗｉレジスタ内の値をＴＸｉレジスタ内の値に加えると、待ち行列 Ｑｉが次のラウンドまたはフレーム中に送信可能なパケット数は、待ち行列Ｑｉ が現行ラウンドまたはフレームのための割振り量を超過した量だけ減少する。 パケットのために資源が使用できない場合、ネットワーク要素１２で輻輳が起 こることがある。パケットをスイッチするのに必要な資源には、入力バッファ、 パケット・バッファ・メモリ４４内の空間、出力ポート５６の待ち行列記憶場所 などがある。パケットには、ネットワーク要素１２への着信時に入力バッファが 割り当てられ、パケットを送信のために出力ポートに移動させると出力ポート待 ち行列エントリが割り当てられる。入力ポート５０でパケットを格納するために 入力バッファが使用可能でない場合、またはパケット・バッファ・メモリ44にパ ケットを記憶するために使用可能なポインタがない場合、パケットは廃棄される 。輻輳論理回路３０６が各待ち行列Ｑｉのために出力ポート５６ｉにおける輻輳 を処理する。 出力ポート待ち行列Ｑｉが一杯の場合、パケットは待ち行列Ｑｉにポインタを 格納しないことによって廃棄されるが、他の待ち行列は一杯になっていないこと がある。待ち行列Ｑｉが一杯になるのを待ってからパケットを廃棄すると、末端 廃棄動作になるため望ましくない場合がある。また、待ち行列Ｑｉが一杯のとき にのみパケットが廃棄される場合や、前もって特定のＱｏＳを折衝していた１つ のフローがその折衝済みパラメータを超え、その他のフローは超えない場合、そ の不正な動作のフローが送信されている間に、正常動作パケットが連続して廃棄 される可能性がある。 特定の待ち行列Ｑｉから送出されるすべてのフローのバランスを図るため、パ ケットの廃棄を待ち行列Ｑｉが一杯にならないうちに始めることができる。各待 ち行列Ｑｉには、待ち行列サイズより小さいしきい値を保持する輻輳レジスタＣ ｉが関連づけられている。待ち行列Ｑｉエントリの数がこのしきい値に達すると 、廃棄方式が適用される。さらに、好ましい実施形態では、待ち行列Ｑｉが一杯 になると、「待ち行列満杯」割込みが生成される。 待ち行列Ｑｉはある時点で、ＲＳＶＰなどの折衝サービス・ベースのプロトコ ルを使用してセットアップされたフローなど、複数の折衝済みフローに属するパ ケットを指すポインタを含むことができる。中継メモリ４０および関連メモリ４ ２内のエントリのセットアップの際にプロセッサ３２によって許可制御が適切に 行われている場合、およびすべてのフローが概ねトラフィック仕様に従っている 場合に、待ち行列満杯割込みがあれば、それはフローの１つが不正動作し、それ に関連づけられた予約を超えていることを示している。 不正動作フローを検出するために、待ち行列満杯割込みを生じさせている特定 の待ち行列Ｑｉに宛てられたすべてのフローを一度に１つずつ監視し、それらの フローがそれぞれの予約を確認するように保証する。この方式で、一定期間にわ たってフローの不正動作を検出する。プロセッサ３２は、待ち行列割込みに応答 して、パケットを待ち行列Ｑｉに関連づけられた出力ポート５６ｉに宛てて送る エントリのためのカウント標識を関連メモリ４２内に設定する。プロセッサ３２ は中継メモリ４０と関連メモリ４２の内容に関する知識を使用して、どのフロー 、すなわち関連メモリ４２内のエントリが、待ち行列Ｑｉに宛てられているかを 判断する。あるいは、関連メモリ４２内に複数のエントリのカウント標識を設定 することによって、所望の集合フローをカウントすることもできる。 この標識は、関連メモリ４２内のエントリがアクセスされるたびに、すなわち 、カウント標識が設定されているフローに付随するパケットがネットワーク要素 １２に着信するたびに、（第４図に図示する）共用パケット・カウント・レジス タＰＣＲ６７を増分させる。ＰＣＲはすべての出力ポート５６間で共用される。 単一のＰＣＲ６７によって、パケット・カウントのためにいくつかの選択肢が得 られる。たとえば、関連メモリ４２内の１つのエントリでのみカウント標識を設 定した場合、ＰＣＲ６７はそのエントリと一致するパケットのみをカウントする 。プロセッサ３２は、数エントリのカウント標識を設定することもでき、それに よってＰＣＲ６７は総計、カウント標識によって設定されているエントリ数だけ パケットをカウントする。 プロセッサ３２は、プロセッサ３２が、パラメータを超えるフローまたは待ち 行列Ｑｉを一杯にする可能性のある異常トラフィック・パターンを有するフロー を検出するまで、カウントのためにフローを選択し続ける。不正動作フローが検 出されると、プロセッサ３２は関連メモリ４２内のその特定の出力ポート５６ｉ のエントリに（前述の）ＢＥ強制標識を設定させる。実際には、これによって、 折衝値を超えるフローを罰する（すなわち、不正動作フローにより低い優先順位 を割り当てる）方策が実施され、それによって、出力ポート５６ｉを使用する他 のパケットがその不正動作フローによって悪影響を受けないようにする。不正動 作フローのパケットは最低優先順位待ち行列であるＢＥ待ち行列に送られるため 、そのパケットが廃棄される可能性は高くなる。ベスト・エフォート待ち行列、 すなわち最低優先順位を有する待ち行列Ｑｉが一杯になった場合、それらのパケ ットは廃棄される。 輻輳論理回路３０６は、ランダム・アーリー・ディスカード（ＲＥＤ）アルゴ リズムを使用して、各待ち行列Ｑｉに関連づけられた待ち行列のプログラム可能 しきい値レジスタＣｉと一致するかそれを超えた後で待ち行列Ｑｉに入ろうとす るパケットをランダムに廃棄する。この廃棄方針は、各待ち行列Ｑｉにそれぞれ 適用されることが好ましい。プロセッサ３２は、トラフィック・クラスとフロー に応じて、廃棄アルゴリズムのマーキング確率をプログラムする。待ち行列Ｑｉ で待ち行列化されているパケットの数がレジスタＣｉ内の数値と一致するか超え る場合、待ち行列Ｑｉに入ってくるパケットはランダムに廃棄される。廃棄され たパケットは、プロセッサ３２がその状況を分析する必要があることを示す標識 と共にプロセッサに送ることができる。 同一のフロー内から十分な数のパケットが廃棄されると、そのフローが過剰な トラフィックを送る確率は通常より高い。そのようなフローの優先順位は前述の ＢＥ強制フィールドを介して下げられる。 関連メモリ４２内のＢＥフィールドを介して強制優先順位を設定するほかに、 関連メモリ４２内のエントリを（それらに対応する中継メモリ４０内のエントリ と共に）異なるＱｏＳをサポートするように設定することができる。様々な状況 が所望のＱｏＳ結果を必要とする。一例は、サブネット内またはサブネット間の ある種の第２層トラフィックにより高い優先順位を与えることができるようにす ることである。これは、たとえば高性能サーバからのトラフィックについて行う ことができる。 シグナリング・プロトコル（ＲＳＶＰなど）を使用して、ＱｏＳをアプリケー ション固有トラフィック用に設定することもできる。ネットワーク要素１２は、 インターネット・エンジニアリング・タスク・フォース（ＩＥＴＦ）統合サービ ス作業グループによる定義に従っていくつかのトラフィック・タイプにほぼ類似 したタイプをサポートすることが望ましい。関連づけられた予約またはＱｏＳを 持たないトラフィックまたはフローは、ベスト・エフォート・トラフィックとし て処理される。当業者なら、本発明の概念を他のトラフィック・タイプに適用す る方法が容易にわかるであろう。 好ましい実施形態では、スイッチング要素３６およびそのすべての構成要素と 、中継メモリ４０と、関連メモリ４２とはすべてハードウェアで実施される。 他の好ましい実施形態では、スイッチング要素３６とそのすべての構成要素は 、特定用途向け集積回路上のハードウェアで実施される。スイッチング要素３６ と、その組合せまたは一部、プロセッサ３２、プロセッサ・メモリ３４、中継メ モリ４０、関連メモリ４２、およびパケット・バッファ・メモリ４４のハードウ ェア実施態様を集積回路に含めることも同様に企図される。 高速な第２層ブリッジ・タイプの中継の各機能を組合せ、それを第３層ルーテ ィングの負荷機能およびＱｏＳサポートと組み合わせて装置を形成する多層ネッ トワーク要素と、それを使用して、次のパケットを受け取る前に第２層中継決定 とほとんどの第３層中継決定の両方を行う方法について説明した。 以上の多層ネットワーク要素の好ましい実施形態の説明は、例示と説明のため に示したものである。以上の説明は網羅的なものではなく、本発明を開示の厳密 な態様に限定することを意図したものでもない。上記の教示に照らして変更およ び変形態様も可能であり、開示されている本発明の実施形態から得ることができ る。上記の各実施形態は、当業者が本発明を様々な実施形態に使用できるように し、企図された特定の用途に合わせて様々な変更を加えることができるように、 本発明の原理とその実際の適用を説明するために、選定し、説明した。本発明の 範囲は下記の請求の範囲およびその同等物によって定義されるものと意図される 。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 マーシイ，シュリー アメリカ合衆国・94087・カリフォルニア 州・サニーベイル・クレセント アベニュ ウ・455・アパートメント 45番 (72)発明者 カミシイ，アサド アメリカ合衆国・94555・カリフォルニア 州・フレモント・フェリックス テラス・ 34494

Claims (1)

1. 【特許請求の範囲】 １．多層ネットワーク要素の出力ポートにおいて待ち行列輻輳を検出し、処理す る装置であって、 中央処理装置（ＣＰＵ）と、 前記ＣＰＵに結合され、前記出力ポートを介してネットワークにパケットを出 力するように構成されたスイッチング要素とを含み、 前記スイッチング要素は、 各ポインタが前記ネットワーク上で送信されるパケットの一部を指すように 構成され、前記出力ポートに関連づけられたパケット・ポインタの可変数の記憶 場所を有する少なくとも１つの出力待ち行列と、 前記待ち行列の先頭の記憶場所を指すポインタを格納するように構成された開 始レジスタと、 記憶場所の数によって決まる前記待ち行列の終わりの記憶場所を指すポインタ を格納するように構成された終了レジスタと、 次に使用可能な記憶場所を指すポインタを格納するように構成された次空きレ ジスタであって、パケット・ポインタが前記開始レジスタによって指された記憶 場所から始まって前記出力待ち行列に記憶され、次空きレジスタが、次に使用可 能な記憶場所が第２のポインタに移動すると増分される次空きレジスタと、 前記開始レジスタによって示された記憶場所と前記終了レジスタによって示さ れた記憶場所との間の記憶場所を指すしきい値ポインタを格納するように構成さ れたプログラム可能しきい値レジスタと、 前記次空きレジスタ内の値が前記しきい値レジスタによって指された記憶場所 と前記終了レジスタによって指された記憶場所を含む場所との間に論理的に位置 する記憶場所を示す場合に輻輳信号を出力するように構成されたしきい値論理回 路と、 前記輻輳信号に応答して、周知のアルゴリズムであるランダム・アーリー・デ ィスカードなどのパケット廃棄アルゴリズムを使用してパケットをランダムに選 択し、それによって前記しきい値を超えた後は着信パケットがランダムに廃棄さ れるように構成されたランダム廃棄論理回路と、 前記次空きレジスタ内の値が前記終了レジスタ内の値と等しい場合に前記ＣＰ Ｕに待ち行列満杯信号を出力するように構成された容量論理回路と、 エントリが前記エントリに関連づけられたパケットをカウントすべきか否かを 示すように適応化された、前記パケットの中継決定に関する情報を格納するよう に構成された少なくとも１つのエントリを有するメモリと、 前記スイッチング要素に前記エントリに関連づけられた着信パケットが到着す ると前記エントリにアクセスするように構成されたメモリアタセス論理回路と、 前記エントリがアクセスされた回数をカウントし、エントリ帯域幅を示すよう に構成されたパケット・カウンタとを含み、 前記装置は、 前記エントリに関連づけられ、前記出力待ち行列に宛てられた将来のパケット の優先順位を下げるために前記パケット・カウンタの内容を予約ベースのプロト コル折衝値と比較するように構成され、前記ＣＰＵに結合されたコンピュータ・ プログラム機構を含む装置。 ２．少なくとも２つの出力ポート上でネットワーク要素から出力されるマルチキ ャスト・パケットのための複数の優先順位を処理する装置であって、 第１の出力待ち行列が第２の出力待ち行列より高い優先順位を有する、各出力 ポートにおける少なくとも１つの第１の出力待ち行列と１つの第２の出力待ち行 列と、 前記マルチキャスト・パケットのマルチキャスト・アドレスに一部基づくメモ リ・アクセスに応答して前記マルチキャスト・パケットに関する中継情報を出力 するように構成されたメモリであって、前記中継情報が、各出力ポートにおける 前記マルチキャスト・パケットの宛先の出力待ち行列を示す優先順位情報を含む メモリとを含む装置。 ３．前記メモリに結合された中央処理装置と、 前記中央処理装置に結合され、前記出力ポートのうちの１つの出力ポートを介 して送信されるパケットの量に基づいて前記優先順位情報に変更を加えるように 構成されたコンピュータ・プログラム機構とをさらに含む、請求項２に記載の装 置。 ４．前記メモリに結合された中央処理装置と、 前記中央処理装置に結合され、前記ネットワーク要素と前記マルチキャスト・ パケットの意図された宛先との間で伝達される情報に基づいて前記優先順位情報 に変更を加えるように構成されたコンピュータ・プログラム機構とをさらに含む 、請求項２に記載の装置。 ５．各パケットが１バイト長を有するパケットを出力するように構成された少な くとも１つの出力ポートと、 各出力ポートに関連づけられ、各出力ポートにおいて出力されるパケットを待 ち行列化するように構成された少なくとも２つの待ち行列と、 各待ち行列に関連づけられ、重み数値を表す値を受け取るように適応化された 重みレジスタと、 各待ち行列の重み数値を生成する重み付け論理回路と、 待ち行列選択信号に従い、完了信号に応答して、各待ち行列内の特定されたパ ケットを送信するように構成された、各出力ポートにおける送信論理回路と、 前記待ち行列の１つを選択し、前記送信論理回路に対する待ち行列選択信号を 生成してどの待ち行列が送信されるかを示す、各出力ポートにおけるスケジュー リング論理回路と、 前記カウンタに関連づけられ、前記重みレジスタを前記送信論理回路によって 送信されたバイト数に等しく減分するように構成された、各出力ポートにおける カウンタ論理回路と、 前記カウンタ内の数値がゼロを示す場合に前記完了信号を送信するように構成 されたゼロ論理回路と、 前記完了信号の後に送信されたパケットの数を判断し、前記重み数値から前記 完了信号の後に送信されたパケットの数を引いた値に等しい値を前記重みレジス タに入れるように構成された再ロード論理回路とを含む装置。 ６．前記スケジューリング論理回路が、前記完了信号と前記送信論理回路とに応 答し、次の送信待ち行列を選択するように構成された、請求項５に記載の装置。 ７．前記スケジューリング論理回路が、前記ゼロ論理回路が前記完了信号を生成 する前に次の送信待ち行列を選択するように構成された、請求項５に記載の装置 。 ８．複数の宛先にパケットを送信するように適応化され、予約ベースのプロトコ ルのためのサービスを含む、複数の優先順位を処理するネットワーク要素内の装 置であって、 １つの出力ポートが複数の宛先のうちの各宛先に関連づけられ、各出力ポート が少なくとも１つの第１の出力待ち行列と少なくとも１つの第２の出力待ち行列 とを有し、各出力ポートにおいて前記第１の出力待ち行列が前記第２の出力待ち 行列よりも高い優先順位を有する、少なくとも２つの出力ポートと、 中継情報が、前記パケットが各出力ポートにおけるどの出力待ち行列に宛てら れるかを示す優先順位情報を含む、前記パケットのヘッダに一部基づくメモリ・ アクセスに応答して前記パケットに関する中継情報を出力するように構成された メモリとを含む装置。 ９．前記メモリに結合された中央処理装置と、 前記中央処理装置に結合され、前記出力ポートの１つを介して送信されるパケ ットとの量に基づいて前記優先順位情報に変更を加えるように構成されたコンピ ュータ・プログラム機構とをさらに含む、請求項８に記載の装置。 １０．前記メモリに結合された中央処理装置と、 前記中央処理装置に結合され、前記ネットワーク要素と前記マルチキャスト・ パケットの意図された宛先との間で伝達される予約ベースのプロトコル情報に基 づいて前記優先順位情報に変更を加えるように構成されたコンピュータ・プログ ラム機構とをさらに含む、請求項８に記載の装置。