(57)【要約】  一のスイッチ又は連結された複数スイッチのネットワーク内における輻輳管理方法を提供する。  ここで、前記一のスイッチ又は複数スイッチの夫々が複数のイングレスポート及び複数のイーグレスポートを有している。この輻輳管理方法は、輻輳が第１イングレス又はイーグレスポートで検出される際、前記イングレス又はイーグレスポートに接続された第１アップストリームポートに、特定のポートにおいて輻輳が発生したことを示すメッセージを送信し、前記ポートに向かうことになっている複数のデータパケットを前記アップストリームポートで格納することを要求する工程と、前記アップストリームポートで格納される、前記輻輳ポートに向かうことになっているデータパケット量に従って、前記アップストリームポートから更に上流のポートに、前記輻輳ポートにおける当該輻輳を前記更に上流のポートに知らせるメッセージを送信する工程であって、前記更に上流のポートは前記輻輳ポートに向かうことになっている複数のデータパケットを当該ポートに格納する工程と、を備える。
2007526706.tif 000002
【特許請求の範囲】
【請求項１】
一のスイッチ内又は連結された複数スイッチのネットワーク内における、前記一のスイッチ又は複数スイッチの夫々が複数のイングレスポート及び複数のイーグレスポートを有しているところの輻輳管理方法であって、
輻輳が第１イングレス又はイーグレスポートで検出される際、前記第1イングレス又はイーグレスポートに接続されたアップストリームポートに、特定のポートにおいて輻輳が発生したことを示すメッセージを送信し、前記ポートに向かうことになっている複数のデータパケットを前記アップストリームポートで格納することを要求する工程と、
前記アップストリームポートで格納される、前記輻輳ポートに向かうことになっているデータパケット量に従って、前記アップストリームポートから更に上流のポートに、前記輻輳ポートにおける当該輻輳を前記更に上流のポートに知らせるメッセージを送信する工程であって、前記更に上流のポートは前記輻輳ポートに向かうことになっている複数のデータパケットを当該更に上流のポートに格納する工程と、
を備えることを特徴とする輻輳管理方法。
【請求項２】
前記アップストリームポートにおいて、前記輻輳ポートに向かうことになっている複数のデータパケット用に取りのけキュー(set aside queue)として用いることに、メモリを割り当てる工程を備えることを特徴とする請求項１に記載の輻輳管理方法。
【請求項３】
前記アップストリームポートにおいて、前記特定のポートで輻輳が発生したことを示すメモリにおけるエントリを作成する工程と、
前記メモリにおけるエントリに対して前記アップストリームポートで続いて受信する複数のパケットを確認し、一のパケットが前記輻輳ポートに向かう場合に、当該パケットを対応する前記取りのけキューに格納する工程と、
を備えることを特徴とする請求項２に記載の輻輳管理方法。
【請求項４】
前記アップストリームポート内に、前記第１ポートから受信するメッセージに従って、一又は複数の取りのけキューを割り当てる工程を備えることを特徴とする請求項１から３のいずれかに記載の輻輳管理方法。
【請求項５】
前記アップストリームポート内に、前記輻輳に従って、前記取りのけキューへ流れ込む、又は前記取りのけキューから流れ出るデータフローを制御する工程を更に備えることを特徴とする請求項４に記載の輻輳管理方法。
【請求項６】
一又は複数の基準に従って、前記一又は複数の取りのけキューを割り当て解除する工程を備えることを特徴とする請求項５に記載の輻輳管理方法。
【請求項７】
前記一又は複数の基準は、前記取りのけキューにおけるデータ量を含むことを特徴とする請求項６に記載の輻輳管理方法。
【請求項８】
一の取りのけキューの構築を要求するメッセージは、当該要求で識別される前記輻輳が、本来の輻輳よりも更に下流にある場合に、前記アップストリームポートにより廃棄されることを特徴とする請求項２に記載の輻輳管理方法。
【請求項９】
前記輻輳が発生したことを示すメッセージは、前記アップストリームポートを輻輳木(congestion tree)内における葉ポートとして識別するために、前記アップストリームポートにより保持されるべきトークン信号を含むことを特徴とする請求項１から８のいずれかに記載の輻輳管理方法。
【請求項１０】
前記輻輳木の各スイッチに、当該輻輳木の葉の数に関するデータを格納する工程を含むことを特徴とする請求項９に記載の輻輳管理方法。
【請求項１１】
一の取りのけキューが割り当て解除される際、前記葉トークン信号は前記アップストリームスイッチにより、隣接するダウンストリームスイッチに戻され、
葉トークン信号を戻した複数の葉スイッチに関連する記録を維持する工程を備えることを特徴とする請求項９又は１０に記載の輻輳管理方法。
【請求項１２】
次のパケットが前記アップストリームポートにより受信される際、当該パケットが前記輻輳へ向かうことになっている場合は、前記パケットを前記取りのけキューに格納し、前記輻輳へ向かうことになっていない場合は、前記アップストリームポートにおけるコールドキュー(cold queue)に格納する工程を備えることを特徴とする請求項１から１１のいずれかに記載の輻輳管理方法。
【請求項１３】
前記輻輳に向かうことになっている一のパケットが前記アップストリームポートで受信される際、前記コールドキューに既に存在する前記輻輳に向かうことになっている複数のパケットに対して、前記輻輳行きのパケットを受信した順序を示すマーカーを前記コールドキューに格納する工程を備えることを特徴とする請求項１２に記載の輻輳管理方法。
【請求項１４】
前記メモリを、連想メモリ(associative memory)として備えることを特徴とする請求項３から１３のいずれかに記載の輻輳管理方法。
【請求項１５】
ある場合には、一の取りのけキューの形成要求のためであって前記連想メモリのコンテンツに対して最短照合動作を行い、また一のデータパケットを既存の取りのけキューに割り当てる場合には、前記連想メモリのコンテンツに対して最長照合動作を行うサーチロジックを採用するように機能するバイナリコマンドベクトルを、前記連想メモリが有することを特徴とする請求項１４に記載の輻輳管理方法。
【請求項１６】
前記アップストリームスイッチによる一の取りのけキューの構築メッセージの受信を追跡する工程を備えており、その結果生じた、現在のスイッチネットワーク位置と最終輻輳ネットワーク目的地との間のパスを表すバイナリベクトルは、前記現在のスイッチ位置の指標にそろえられ、且つ、連想メモリ要素における格納以前の輻輳目的地への経路を描くビットフィールドの大きさであるマスクを有することを特徴とする請求項１４に記載の輻輳管理方法。
【請求項１７】
前記連想メモリのサーチレジスタに適用するデータは、ネットワークにおける現在のスイッチ位置で前記連想メモリ要素をサーチする以前に、前記現在のスイッチ位置の指標にそろえられ、且つ、前記格納された連想メモリの要素と比較するためのマスクを有することを特徴とする請求項１６に記載の輻輳管理方法。
【請求項１８】
一対の追加反転ビットは、ターンプール(turnpool)におけるアクティブ部分の開始及び終了位置を描くために用いられ、標準サイズのマスクを生成することを特徴とする請求項１７に記載の輻輳管理方法。
【請求項１９】
複数スイッチのネットワーク内における輻輳を管理するシグナリングプロトコルであって、
輻輳が検出される第１ポートから、当該第１ポートに接続されたアップストリームポートに送信するための第１メッセージを備え、
当該第１メッセージは、輻輳源に向かうことになっている前記アップストリームスイッチにより受信される複数のデータパケットを格納する一の取りのけキューを、前記アップストリームポートにおいて構築することを要求し、
前記第１メッセージは、前記アップストリームポートによる格納のためのトークン信号を含むことを特徴とするシグナリングプロトコル。
【請求項２０】
前記要求された取りのけキューの構築を確認するために、前記アップストリームポートから前記第１ポートに送信するためのアクノリッジメントメッセージを備えることを特徴とする請求項１９に記載のシグナリングプロトコル。
【請求項２１】
前記第１ポートにおける輻輳に関するデータを含む、前記アップストリームポートから前記第１ポートに送信するためのフロー制御メッセージを備えることを特徴とする請求項２０に記載のシグナリングプロトコル。
【請求項２２】
取りのけキューが要求されなくなった場合、前記取りのけキューの割り当て解除を前記第１ポートに知らせる、前記アップストリームポートから前記第１ポートに送信するための通知を備えることを特徴とする請求項１９から２１のいずれかに記載のシグナリングプロトコル。
【請求項２３】
前記アップストリームポートが一の旧取りのけキューを割り当て解除したことを、前記第１ポートに知らせるためのメッセージを備えることを特徴とする請求項１９から２２のいずれかに記載のシグナリングプロトコル。
【請求項２４】
前記アップストリームポートに、特定されたダウンストリーム取りのけキューへのパケット送信の速度（rate）を調節するように指示する、前記第１ポートから前記アップストリームポートへ送信するためのメッセージを備えることを特徴とする請求項１９から２３のいずれかに記載のシグナリングプロトコル。
【請求項２５】
ある量のデータパケットが前記アップストリームポートにおける前記取りのけキュー内に格納される際、トークン信号を含むメッセージが、前記アップストリームポートによって更に上流のポートに送信され、輻輳が検出された前記第１ポートへ向かうことになっている複数のデータパケットを格納する前記更に上流のポートで、取りのけキューの構築を要求することを特徴とする請求項１９から２４のいずれかに記載のシグナリングプロトコル。
【請求項２６】
複数スイッチネットワークで用いるためのスイッチであって、
二以上のイングレスポートと、
二以上のイーグレスポートと、
前記イングレスポートの一又は複数のイングレスポートから前記イーグレスポートの一又は複数のイーグレスポートで受信される複数のデータパケットを選択的に結合させるスイッチファブリックと、
ダウンストリーム輻輳ポートへ向かうことになっている複数のデータパケットの格納要求に応じて、選択されたデータパケットを格納するストレージと、
前記パケットの検出された所望の目的地に従って、受信したデータパケットを前記ストレージへ選択的に送る選択手段と、
閾値量の複数のデータパケットが前記ストレージに格納される際、前記輻輳ポートへ向かうことになっている複数のデータパケットを前記更に上流のポートで格納することを要求するために、更に上流のポートへ要求を送信するように配列された要求生成手段と、
を備えることを特徴とするスイッチ。
【請求項２７】
前記選択手段は、コンテントアドレッサブルメモリを備えることを特徴とする請求項２６に記載のスイッチ。
【請求項２８】
複数の基準のうち一又は複数の基準が満たされる場合に、一の取りのけキューが前記要求に応じて形成されるだけであることを特徴とする請求項２６又は２７に記載のスイッチ。
【請求項２９】
複数スイッチネットワークで用いるためのスイッチであって、
複数のデータパケットを受信する複数のイングレスポートと、
複数のデータパケットを送信する出力ポートと、
前記イングレスポートの一又は複数のイングレスポートから前記イーグレスポートの一又は複数のイーグレスポートで受信される複数のデータパケットを選択的に送る制御手段と、
を備え、
前記複数のイングレスポート又はイーグレスポートの少なくとも一つは、使用中の前記スイッチが設けられる少なくとも三つの連結ポートを備える輻輳木の詳細を格納するためのストレージを備えることを特徴とするスイッチ。
【請求項３０】
前記複数のイングレス又はイーグレスポートの少なくとも一つは、前記輻輳木における一のポートへ向かうことになっている複数の受信データパケットを格納するための取りのけキューを生成する手段を備えることを特徴とする請求項２９に記載のスイッチ。
【請求項３１】
前記複数のイングレス又はイーグレスポートの少なくとも一つは、ダウンストリームポートにおける輻輳に関する情報を含む、前記イングレス又はイーグレスポートにより受信される要求に応じて、取りのけキューを生成することに利用可能であり、前記要求は前記スイッチと前記ダウンストリームポートとの間の輻輳経路に関する情報を含むことを特徴とする請求項２９又は３０に記載のスイッチ。
【請求項３２】
前記複数のイングレス又はイーグレスポートの少なくとも一つは、
データパケットを受信し、
当該データパケットから、その最終目的地を決定し、
前記データパケットが輻輳ポートに向かうことになっている場合には、当該パケットを前記取りのけキューに格納し、非輻輳ポートに向かうことになっている場合には、当該パケットを前記非輻輳ポートに送信するためのコールドキューに格納する
ことに利用可能なイングレス又はイーグレスエンジンを備えることを特徴とする請求項２９から３１のいずれかに記載のスイッチ。
【請求項３３】
前記イングレス又はイーグレスエンジンは、コンテントアドレッサブルメモリにおいて具体化されることを特徴とする請求項３２のいずれかに記載のスイッチ。
【請求項３４】
前記スイッチは、請求項１から１８のいずれかに記載の輻輳管理方法を実施するために、複数スイッチネットワークで接続される際、制御可能であることを特徴とする請求項３２のいずれかに記載のスイッチ。
【請求項３５】
トポロジーで接続されている相互接続スイッチのネットワークであって、
複数のスイッチを備え、
該複数のスイッチのうち少なくとも二つが、請求項２６から３４のいずれかに記載のスイッチであることを特徴とするネットワーク。
【請求項３６】
複数スイッチのネットワーク内における輻輳を管理するシグナリングプロトコルであって、
輻輳が検出される第１ポートから、当該第１ポートに接続されたアップストリームポートに送信するための第１メッセージであって、前記輻輳ポートへ向かうことになっている前記アップストリームポートにより受信される複数のデータパケットの格納を要求する第１メッセージと、
前記輻輳ポートに向かうことになっている閾値量のデータパケットが、前記アップストリームポートにより受信され格納された際、更に上流のポートへ前記アップストリームポートにより送信される第２メッセージであって、前記更に上流のポートにより受信される前記輻輳ポートへ向かうことになっている複数のデータパケットの格納を要求する第２メッセージと、
を備えることを特徴とするシグナリングプロトコル。
【請求項３７】
前記輻輳ポートからのメッセージ、又は前記アップストリームポートからのメッセージのいずれかにより格納が要求される際、前記アップストリームポート及び前記更に上流のポートは、前記輻輳ポートに向かうことになっている複数のデータパケットを格納するための取りのけキューを、前記アップストリームポート又は前記更に上流のポートにおいて割り当てるように夫々制御されることを特徴とする請求項３６に記載のシグナリングプロトコル。
【請求項３８】
前記アップストリームポート及び前記更に上流のポートのいずれか一方又は両方における前記取りのけキューが空になった場合に、前記取りのけキューは割り当て解除されてよいことを特徴とする請求項３７に記載のシグナリングプロトコル。
【請求項３９】
相互接続スイッチネットワークで使用するエンドステーションであって、
使用中の前記エンドステーションが接続されているネットワークから複数のデータパケットを受信するイングレスポートと、
使用中の前記エンドステーションが接続されているネットワークに複数のデータパケットを提供するイーグレスポートと、
を備え、
前記イーグレスポート手段は、使用時に、ダウンストリームポートからメッセージを受信するよう機能し、前記メッセージは、輻輳ポートダウンストリームに関するデータと、前記輻輳ポートダウンストリームへ向かうことになっている複数のデータパケットにストレージを設ける要求とを含むことを特徴とするエンドステーション。
【請求項４０】
使用時に、前記ネットワークから受信したメッセージに応じて、前記輻輳ポートへ向かうことになっている複数のデータパケットを格納するための取りのけキューを割り当てるよう機能する制御装置を備えることを特徴とする請求項３９に記載のエンドステーション。
【請求項４１】
請求項１９から２５及び３６から３８のいずれかに記載のシグナリングプロトコル内での使用に適していることを特徴とする請求項３９又は４０に記載のエンドステーション。
【請求項４２】
前記輻輳ポートへ向かうことになっている複数のデータパケットを前記アップストリームポートで格納することを要求する工程は、前記複数のデータパケットを格納するための取りのけキューの構築を要求する工程を備え、
前記更に上流のポートで格納された複数のデータパケットは、前記輻輳ポートへ向かうことになっている複数のデータパケットを格納するための取りのけキューに格納されて、本来の輻輳木を構築し、
複数のパケットを格納するための次の要求が、前記本来の輻輳木の根よりも更に下流のポートにおける輻輳について、前記本来の輻輳木における前記複数ポートのいずれかにおいて受信される際、前記更に下流のポートへ向かうことになっている複数のデータパケットが、前記要求を受信したポートで格納されるように、当該ポートで前記要求を受理し、前記輻輳木をダウンストリームに伸ばす、
ことを特徴とする請求項１から７のいずれかに記載の輻輳管理方法。
【請求項４３】
前記本来の輻輳木における前記いずれかのポートで、取りのけキューの構築要求を受信する際、前記ポートにおいて、特定のポートで輻輳が発生したことを示すメモリにおけるエントリを作成する工程と、
前記メモリにおけるエントリに対して、前記ポートで順次受信される複数のデータパケットを確認し、一のデータパケットが前記輻輳ポートに向かう場合に、当該データパケットを対応する取りのけキューに格納し、一のデータパケットが前記又は他の輻輳ポートに向かわない場合に、当該データパケットを前方へ送信するためのコールドキューに格納する工程と
を備えることを特徴とする請求項４２に記載の輻輳管理方法。
【請求項４４】
前記ポートで受信される取りのけキューの構築要求に毎回応じて、取りのけキューを構築する工程を備え、当該新たに構築された取りのけキューは、既存の取りのけキューと同時に存在することを特徴とする請求項４３に記載の輻輳管理方法。
【請求項４５】
前記本来の輻輳木の根よりも更に下流のポートについて、一の要求が取りのけキューの構築のためである場合には、後に前記新たに構築された取りのけキューを活性化させるために、既存の取りのけキューにリンクを設ける工程を備えることを特徴とする請求項４４に記載の輻輳管理方法。
【請求項４６】
前記本来の輻輳木の根よりも更に下流のポートについて、一の要求が取りのけキューの構築のためである場合には、最短の既存取りのけキューの上に、新たに構築された取りのけキューを書き込む工程と、
前記コールドキューに、前記新たに構築された取りのけキューへのリンクを設ける工程と、
を備えることを特徴とする請求項４３に記載の輻輳管理方法。
【請求項４７】
前記本来の輻輳木の根よりも更に下流のポートについて、一の要求が取りのけキューの構築のためである場合には、最短の取りのけキューの上に、前記受信された要求に対応する新たに構築された取りのけキューを書き込む工程と、
最長の取りのけキューであって、且つ前記新たに構築された取りのけキューよりは短い前記既存の取りのけキューに、前記新たに構築された取りのけキューへのリンクを設ける工程と、
を備えることを特徴とする請求項４６に記載の輻輳管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一のスイッチ又は連結スイッチのネットワーク内における輻輳管理方法に関する。また本発明は、スイッチネットワーク内における輻輳管理のためのスイッチ、エンドステーション、ネットワークにも関する。
【０００２】
実施例において、本発明は、単一スイッチ内又は連結スイッチネットワーク内の対応エンドポイントを含む輻輳管理方法に関する。また実施例において、本発明は、一又は複数のスイッチのネットワーク内における輻輳管理のためのスイッチアーキテクチャ及びシグナリングプロトコルにも関する。
【背景技術】
【０００３】
スイッチネットワーク内のトラフィックが飽和状態に近づくにつれ、大抵のネットワークでは、ネットワーク上のトラフィックのスループットが著しく低下することが観察され知られている。従って、複数スイッチ及びリンクバンド幅を、コスト的に効率よく用いるためには、ネットワークが飽和に近い状態でも安定して動作しつつ、スループットの低下を防ぐような効率的な輻輳管理が必要とされている。
【０００４】
ネットワーク内の競合（コンテンション）は、ネットワークを横断する幾つかのデータフローが、ネットワーク内の一のスイッチにおいて同じイーグレスポートへのアクセスを争奪する場合に起こる。イーグレスポートによるバンド幅が、それからなる要求のすべてを可能にするほど十分高くない場合は、競合は輻輳（混雑状態）となる。転送不可能なデータパケットは、待ち行列（キュー）でバッファリングされる。輻輳が続く場合、これらのキューはいっぱいになる。いっぱいになった又はブロックされたキューの形成を防止できない場合、或いは、それらが形成されてもその詰まりを緩和するために何の処置もとられない場合は、これが、連結されたスイッチの間のネットワークを通じて急速に広がりうる輻輳を引き起こすことなり、いわゆる輻輳木（congestion tree)を形成する。これにより、大きなネットワークにおいては、かなり非効率になり、結果として、全ファブリックの崩壊を引き起こしてしまいかねない。
【０００５】
上述した非効率性に対する主な理由は、ＨＯＬ(Head Of Line、行頭)ブロッキングとして知られる効果のためである。これは、ネットワークエンドステーション、並びに任意のサイズ及びトポロジーである複数スイッチのファブリックにおいて起こる。ＨＯＬブロッキングは、キュー（待ち行列）が異なる目的地に対してデータパケットを格納し、目的地がパケット受け入れ不可能であるためにそのキューの先頭のパケットの転送が妨げられている場合は、いつでも起こる。通常、これはいくつかのフローがネットワーク内の一のスイッチにおいて同じイーグレスポートへのアクセスを争奪することによる結果である。これら凝集効果は、一のスイッチ内部と、一のファブリックの複数スイッチ間とに適用される。ブロックされたキューの続くパケット、即ち行頭以降のパケットは、パケット受け入れ可能な異なる目的地に対するものであってよいが、これらのパケットは、ブロックされたパケットによって行頭で転送不可能とされている。その結果、スループットが著しく低下するおそれがある。
【０００６】
この問題を解決するために、二つの独立した解決方法群がこれまでに提案されている。これらの解決方法群は、非常に異なる状態で作用する。第１群は、エンドステーション機器がどのように複数のパケットスイッチ又はスイッチネットワークにトラフィックを注入するかを変形するものである。この群の解決方法は、通常、パケットをネットワークに注入する速度を変更するものであり、ネットワーク管理制御、輻輳制御、又は注入制限技術と称される。第２の解決方法群は、異なるフローに対して別個のバッファを備える、又は行頭でパケットを待たないように余分のハードウェアパスを備えることで、ＨＯＬブロッキングを直接的に回避する技術を含む。
【０００７】
残念なことに、先に提案されたいずれの解決方法も、あまり拡張可能（スケーラブル）ではない。スイッチファブリックサイズが大きくなると、第１解決法群を用いる場合は、システムが発振しはじめる。これは、遅延ループと、トラフィックをネットワークに注入するエンドステーションが、非常に無秩序な転送作用の効果において非常に制限された視認性しか持たないこととに起因する。
【０００８】
輻輳管理は、ＴＣＰ／ＩＰプロトコルで広範囲にわたり検討されてきており、多くの解決法が利用可能である。しかしながら、これらの解決法は、すべて、輻輳が検出される場合にパケットを廃棄(drop)することに基づくものである。従って、これらの解決方法は、システムエリアネットワーク（ＳＡＮ：System Area Network）、クラスタ相互接続、及び並列コンピュータ相互接続として用いられるファブリックの場合と同様、パケット廃棄が可能ではないスイッチファブリックにはふさわしくない。
【０００９】
ＨＯＬブロッキング問題に対してよく知られている解決方法は、仮想出力キューイング（ＶＯＱ：Virtual Output Queuing）である。通常、別個のキュー（待ち行列）は、一のスイッチのイングレスで保持され、これらのキューが、通常、ポートを通る個々のトラフィックフローの夫々に対してスイッチイーグレスポート毎に維持される。マルチステージ（多段）ファブリックにおいて、複数のキューが、全ファブリックにおける中間又は最終のイーグレスポートに対して維持されたならば、キューの数は、ステージ数とともに指数関数的に増大するために、急速に非常に大きくなるであろう。従って複数のＶＯＱは、通常、個々のスイッチイーグレスポートに対してのみ維持され、ファブリックの全ステップで各スイッチ内を流れる。この制限により、ＨＯＬブロッキング効果が生じ、ファブリックにおけるパケットスイッチングステップ間における輻輳が広がることとなる。
【００１０】
その他の公知の解決方法では、多段相互接続ネットワーク（ＭＩＮ：Multi-stage Interconnection Network）における一のホップ（ｈｏｐ）又はステップにおいてのみ、ＨＯＬブロッキングを緩和する。これは、アップストリームスイッチにおいて、多くのキューを構築することにより実現され、そのキューは、次のダウンストリームスイッチのイーグレスポートに対してパケットを格納するために、通常、何らかの固定された方法で、予め割り当てられる。この解決方法では、状態基準フロー制御を提供するために採用される、フローダウンストリームスイッチとアップストリームスイッチとの間のシグナリング手段が必要とされる。この単一ステージの制限により、再び、ＨＯＬブロッキング効果が、フロー制御情報に対応するスイッチから上流で生じ、またファブリックにおいてスイッチングステージを横断して輻輳が広がることとなる。
【００１１】
ネットワークへのトラフィックの管理を試みる方法は、ネットワークのあるポイントにおいて何らかの方法で輻輳を検出し、その後、輻輳に寄与する入力元にメッセージを戻して、トラフィックインジェクションの速度を低下させるように指示することで行われる。残念ながら、これがネットワークの利用を極めて不安定とし、また多くの場合、ネットワークの効率性が、飽和状態と利用中状態との間で揺れ動くことになる。これは、閉じたループ制御システムに有限の時間遅延があるからであり、また、速度低下要求の対象となるネットワーク入力を選択するという、避けられない不確定性によるものである。加えて、これらのような解決方法は、長い通知遅延(long notification delays)や、その遅延がスイッチファブリックの大きさに依存するために、非常に調整（即ち、加工パラメーターを調整する）が難しい。
【発明の開示】
【課題を解決するための手段】
【００１２】
本発明の第１の態様によれば、一のスイッチ内又は連結された複数スイッチのネットワーク内における、前記一のスイッチ又は複数スイッチの夫々が複数のイングレスポート及び複数のイーグレスポートを有しているところの輻輳管理方法であって、輻輳が第１イングレス又はイーグレスポートで検出される際、前記第1イングレス又はイーグレスポートに接続されたアップストリームポートに、特定のポートにおいて輻輳が発生したことを示すメッセージを送信し、前記ポートに向かうことになっている複数のデータパケットを前記アップストリームポートで格納することを要求する工程と、前記アップストリームポートで格納される、前記輻輳ポートに向かうことになっているデータパケット量に従って、前記アップストリームポートから更に上流のポートに、前記輻輳ポートにおける当該輻輳を前記更に上流のポートに知らせるメッセージを送信する工程であって、前記更に上流のポートは前記輻輳ポートに向かうことになっている複数のデータパケットを当該更に上流のポートに格納する工程と、を備えることを特徴とする輻輳管理方法を提供する。
【００１３】
好ましくは、当該輻輳管理方法は、前記アップストリームポートにおいて、前記特定のポートで輻輳が発生したことを示す、例えば、連想メモリ又はコンテントアドレッサブルメモリ（ＣＡＭ）の制御メモリにおけるエントリを作成する工程と、前記メモリにおけるエントリに対して前記アップストリームポートで続いて受信する複数のパケットを確認し、一のパケットが前記輻輳ポートに向かう場合に、当該パケットを対応する前記取りのけキュー(set aside queue)、即ち、輻輳ポートへ向かうことになっている複数のデータパケット用のキューに格納する工程と、を備える。
【００１４】
好ましくは、当該輻輳管理方法は、前記アップストリームポートにおいて、前記輻輳ポートに向かうことになっている複数のデータパケット用に取りのけキューとして用いることに、メモリを割り当てる工程を備える。
【００１５】
好ましくは、当該輻輳管理方法は、一又は複数の基準に従って、前記一又は複数の取りのけキューを割り当て解除する工程を備える。
【００１６】
一の具体例では、前記輻輳木における前記複数ポートのいずれかで受信される、複数のパケットの格納要求が、前記輻輳木の根よりも更に下流のポートにおける輻輳に関する場合には、前記更に下流のポートへ向かうことになっている複数のデータパケットが前記要求を受信したポートで格納されるように、前記要求が受理される。
【００１７】
本発明の第２の態様によれば、複数スイッチのネットワーク内における輻輳を管理するシグナリングプロトコルであって、輻輳が検出される第１ポートから、当該第１ポートに接続されたアップストリームポートに送信するための第１メッセージを備え、当該第１メッセージは、輻輳源に向かうことになっている前記アップストリームスイッチにより受信される複数のデータパケットを格納する一の取りのけキューを、前記アップストリームポートにおいて構築することを要求し、前記第１メッセージは、前記アップストリームポートによる格納のためのトークン信号を含むことを特徴とするシグナリングプロトコルを提供する。
【００１８】
本発明の第３の態様によれば、複数スイッチネットワークで用いるためのスイッチであって、二以上のイングレスポートと、二以上のイーグレスポートと、前記イングレスポートの一又は複数のイングレスポートから前記イーグレスポートの一又は複数のイーグレスポートで受信される複数のデータパケットを選択的に結合させるスイッチファブリックと、ダウンストリーム輻輳ポートへ向かうことになっている複数のデータパケットの格納要求に応じて、選択されたデータパケットを格納するストレージと、前記パケットの検出された所望の目的地に従って、受信したデータパケットを前記ストレージへ選択的に送る選択手段と、閾値量の複数のデータパケットが前記ストレージに格納される際、前記輻輳ポートへ向かうことになっている複数のデータパケットを前記更に上流のポートで格納することを要求するために、更に上流のポートへ要求を送信するように配列された要求生成手段と、を備えることを特徴とするスイッチを提供する。
【００１９】
本発明の第４の態様によれば、トポロジーで接続されている相互接続スイッチのネットワークであって、複数のスイッチを備え、該複数のスイッチのうち少なくとも二つが、本発明の第３の態様に係るスイッチであることを特徴とするネットワークを提供する。
【００２０】
本発明の第５の態様によれば、複数スイッチネットワークで用いるためのスイッチであって、複数のデータパケットを受信する複数のイングレスポートと、複数のデータパケットを送信する出力ポートと、前記イングレスポートの一又は複数のイングレスポートから前記イーグレスポートの一又は複数のイーグレスポートで受信される複数のデータパケットを選択的に送る制御手段と、を備え、前記複数のイングレスポート又はイーグレスポートの少なくとも一つは、使用中の前記スイッチが設けられる少なくとも三つの連結ポートを備える輻輳木の詳細を格納するためのストレージを備えることを特徴とするスイッチを提供する。
【００２１】
実施例において、本発明は、輻輳管理問題に対する解決法を提供する。ある実施例では、本発明は、ネットワーク進入を管理し、任意のトポロジーを有するＭＩＮの幾つかのホップにまたがるＨＯＬブロッキング効果による輻輳の広がりを減らす又はなくすための一組の手段と方法とを備える。これは、ＨＯＬブロッキングが形成されるのを防ぐことにより達成される。本発明は、ネットワークエンドステーション及び一段スイッチをして、それらの待ち行列源(queuing resources)をより効率良く使用ならしめ、また多段スイッチファブリックに、あたかも大きな一段スイッチかのように概して振舞わすことができる。
【００２２】
本発明の第６の態様によれば、複数スイッチのネットワーク内における輻輳を管理するシグナリングプロトコルであって、輻輳が検出される第１ポートから、当該第１ポートに接続されたアップストリームポートに送信するための第１メッセージであって、輻輳ポートへ向かうことになっている前記アップストリームポートにより受信される複数のデータパケットの格納を要求する第１メッセージと、前記輻輳ポートに向かうことになっている閾値量のデータパケットが、前記アップストリームポートにより受信され格納された際、更に上流のポートへ前記アップストリームポートにより送信される第２メッセージであって、前記更に上流のポートにより受信される前記輻輳ポートへ向かうことになっている複数のデータパケットの格納を要求する第２メッセージと、を備えることを特徴とするシグナリングプロトコルを提供する。
【００２３】
好ましくは、当該シグナリングプロトコルにおいて、前記輻輳ポートからのメッセージ、又は前記アップストリームポートからのメッセージのいずれかにより格納が要求される際、前記アップストリームポート及び前記更に上流のポートは、前記輻輳ポートに向かうことになっている複数のデータパケットを格納するための取りのけキューを、前記アップストリームポート又は前記更に上流のポートにおいて割り当てるように夫々制御される。
【００２４】
本発明の第７の態様によれば、相互接続スイッチネットワークで使用するエンドステーションであって、使用中の前記エンドステーションが接続されているネットワークから複数のデータパケットを受信するイングレスポートと、使用中の前記エンドステーションが接続されているネットワークに複数のデータパケットを提供するイーグレスポートと、を備え、前記イーグレスポート手段は、使用時に、ダウンストリームポートからメッセージを受信するよう機能し、前記メッセージは、輻輳ポートダウンストリームに関するデータと、前記輻輳ポートダウンストリームへ向かうことになっている複数のデータパケットにストレージを設ける要求と、を含むことを特徴とするエンドステーションを提供する。
【００２５】
実施例において、本発明は、輻輳管理問題に対する拡張可能な解決方法を提供する。ある実施例では、本発明は、ネットワーク進入を管理し、任意のトポロジーを有する多段相互接続ネットワーク（ＭＩＮ）の幾つかのホップにまたがるＨＯＬブロッキング効果による輻輳の広がりを減らす又はなくすための一組の手段と方法とを備える。これは、ＨＯＬブロッキングが形成されるのを防ぐことにより達成される。本発明は、ネットワークエンドステーション及び一段スイッチに、それらの待ち行列源(queuing resources)をより効率良く使用ならしめ、また多段スイッチファブリックに、あたかも大きな一段スイッチかのように概して振舞わすことができる。
【００２６】
実施例において、本発明は、ＨＯＬブロッキングの原因となるトラフィックを除外することで、そうしなかったならばブロックされたトラッフィックによってスイッチ又はネットワークを介した流れが妨げられるであろうトラッフィックが、そのスイッチを通って、ブロックされていないネットワーク経路を流れ続けることを可能にする手段を用いる。その手段は、キュー（待ち行列）の行頭におけるトラフィックを除外するために、スイッチネットワークの全域で低バンド幅シグナリング方法を含むことが好ましい。この方法は、有効スイッチネットワークバンド幅を必要としない。好ましくは、この方法は、輻輳トラフィックが急速に拡大して、全スイッチネットワークが動かなくなることがない程度に、迅速に応答可能である。複数のＶＯＱに基づく解決方法とは異なり、ある特定の実施例において、本発明は、スイッチファブリックの大きさにかかわらず、各スイッチのイングレス／イーグレスポートで、固定量の制御メモリを用いる。
【００２７】
本発明は、ネットワークエンドステーション、並びに、段階（ステージ）間の規則的及び不規則的相互接続パターンを含み、且つ任意のサイズ及びトポロジーのファブリックに対する、一段スイッチ要素、並びに複数スイッチにおける多段相互接続ネットワークに適用可能である。
【００２８】
本発明は、輻輳管理問題に対して、拡張可能で費用効率の高い解決法を提供する。一の実施例では、固定量の予備バッファ資源を特定の方法で用いることで、拡張可能にＨＯＬブロッキング問題を解決する。故に、ＨＯＬブロッキングの回避はするが、拡張性問題の導入はしないような解決方法によりもたらされる利益のすべてが供与される。また本発明は、ネットワーク利用の変動効果を回避しながら、ネットワークアドミッションコントロールのグループでの解決方法の利益、も提供する。
【００２９】
本発明は、エンドステーションが、一段又は多段相互接続ネットワーク（ＭＩＮ）において、ユーザーにより特定されたネットワーク進入策に適切に応答することを可能にする。動作時には、エンドステーションが、程よく協調、安定した方法で、すべての目的地に対してトラフィックを注入する速度を管理可能にするために必要な情報のすべてが提供される。
【００３０】
当然のことながら、ネットワークにおける特定のポートで格納するために、あるデータパケットを選択する際、アウトオブオーダー効果（ＯＯＯ：Out Of Order）が発生するおそれがある。例えば、同じ輻輳ポートへ向かうことになっている一連のデータパケットがアップストリームポートに到着する場合、またその輻輳ポートへ向かうことになっているデータパケットのうちの第１及び第２データパケットが到着する間に輻輳が消失する場合には、第１のデータパケット以前に、第２のデータパケットが、現在輻輳ではないポートに送信されることがありうる。この問題に取り組むために、好ましい要件は、取りのけキューの構築要求が、あるポートで受信され、その要求が、最も下流にある既に輻輳が発生しているポートよりも更に下流のポートに関する場合は、この要求は無視される。
【００３１】
この、最も下流にある既に輻輳が発生しているポートよりも更に下流の輻輳ポートに関するポートで取りのけキューを構築する要求を無視するという規定は、アウトオブオーダー効果が発生しないことを確実にする役目を果たす。実際には、この要求が実行される場合とは、輻輳木が一旦構築されると、輻輳木の根を下流に移動させることができない、という意味である。これは大抵の用途に通用する。例えば、ネットワーク内において、ポート１、２、３、及び４から構成される輻輳木がある場合、ポート２へ向かうことになっているデータパケットが、ポート３よりも更に下流のポート４にも輻輳があるということを知る必要はない。
【００３２】
図１は、相互接続スイッチのネットワークの一例を示している。そのネットワークは、三段スイッチネットワーク（ステージＡ、Ｂ、及びＣ）に接続されたインプット装置Ｄ０からＤ７を備えている。このネットワークは、装置Ｄ０からＤ７の夫々が、装置ＤＡ又はＤＢのいずれか、又は両方の装置にデータを送信するように構成されている。ある用途では、すべてのイングレス装置Ｄ０からＤ７の状態を同時に保存することが必要である。図１に示す例では、イングレス装置Ｄ０からＤ７からのある時点での状態データがすべて装置ＤＡに送信されうる。
【００３３】
すべてのイングレス装置が同時にデータパケットをＤＡに送信開始すると、先ず、（競合に起因する）輻輳が、Ａ段スイッチのイーグレスポート０、即ちＡ００、Ａ１０、Ａ２０及びＡ３０で発生するであろう。上述の輻輳管理方法を用いて、例えば、各インプット装置が５０％のリンク容量で装置ＤＡにデータの送信のみ行うように、この競合をイングレス装置に信号で伝える。
【００３４】
次の輻輳ポートは、Ｂ段スイッチＢ０及びＢ１の夫々におけるポート０であろう。これらのスイッチは、順に、ポート０が輻輳であるような夫々のＡ段スイッチに、信号を戻すであろう。その後、Ａ段スイッチは、ダウンストリームスイッチポートＢ００及びＢ１０が輻輳であることを、各々のイングレス装置に信号で伝えるであろう。ここで、イングレス装置Ｄ０からＤ７は夫々、例えば、２５％のリンク容量でＤＡに向かうことになっているデータパケットを送信するのみであってよい。この状況は、ポートＣ０でも繰り返され、そのため、ＤＡへの効率的な送信容量は、約１２％のリンク容量に制限される。
【００３５】
Ａ段スイッチのイーグレスポート０が輻輳の根であると考えられる場合は、データパケットが、ポートＢ１０の代わりに、非輻輳のポートＢ１１に向かうことになっていたとしても、ポートＡ２０を単に通過したデータパケットは、スイッチＡ２におけるスイッチＢ１のポートに対する取りのけキューに割り当てられるであろう。言い換えれば、最も下流にある既存の輻輳ポートよりも更に下流の輻輳ポートに向かうことになっているデータパケットに対する取りのけキューの構築要求が受理されないことを確実にすることにより、その他の非輻輳ポート間で用いられるリンク容量は、不必要に減らされる可能性がある。
【００３６】
これに取り組むために、好ましくは、本発明の第１の態様に係る輻輳管理方法において、前記輻輳ポートへ向かうことになっている複数のデータパケットを前記アップストリームポートで格納することを要求する工程は、前記複数のデータパケットを格納するための取りのけキューの構築を要求する工程を備え、前記更に上流のポートで格納された複数のデータパケットは、前記輻輳ポートへ向かうことになっている複数のデータパケットを格納するための取りのけキューに格納されて、本来の輻輳木を構築し、複数のパケットを格納するための次の要求が、前記本来の輻輳木の根よりも更に下流のポートにおける輻輳について、前記本来の輻輳木における前記複数ポートのいずれかにおいて受信される際、前記更に下流のポートへ向かうことになっている複数のデータパケットが、前記要求を受信したポートで格納されるように、当該ポートで前記要求を受理し、前記輻輳木をダウンストリームに伸ばす。
【００３７】
この例では、本発明は、輻輳木の根を下流に移動可能な手段を提供する。従って、図１に示すようなネットワークにおいては、ネットワークは最大限に利用される。この点に関して、本発明は、輻輳木の根を下流に移動可能とすること、又はむしろ既存の根よりも更に下流の輻輳木が、既存の木と同時に存在することが必要である用途に対する輻輳管理方法を提供する。
【００３８】
上述のように、既存の輻輳木の根よりも更に下流の取りのけキューの構築要求が受理される場合に、アウトオブオーダー効果が生じる可能性がある。
【００３９】
好ましくは、本発明の輻輳管理方法は、一又は複数のリンクを更に下流のポートに向かうことになっているデータパケットの取りのけキューと、輻輳木におけるその他の複数の輻輳ポートのうちの一又は複数のポートに向かうことになっているデータパケットの取りのけキューとの間に構築する工程を備える。
【００４０】
一例では、本発明の輻輳管理方法は、取りのけキューの構築要求のすべてを受理する工程を備え、前記輻輳木の根よりも更に下流のポートについて、前記要求が取りのけキューの構築のためである場合には、後に前記新たに形成された取りのけキューを活性化させるために、既存の取りのけキューのうちの一又は複数の取りのけキューにリンクを設ける工程を備える。
【００４１】
別の例では、本発明の輻輳管理方法は、前記本来の輻輳木の根よりも更に下流のポートについて、一の要求が取りのけキューの構築のためである場合には、最短の既存取りのけキューの上に、新たに構築された取りのけキューを書き込む工程と、前記コールドキューに、前記新たに構築された取りのけキューへのリンクを設ける工程と、を備える。
【００４２】
或いは、前記本来の輻輳木の根よりも更に下流のポートについて、一の要求が取りのけキューの構築のためである場合には、最短の取りのけキューの上に、前記受信された要求に対応する新たに構築された取りのけキューを書き込む工程と、最長の取りのけキューであって、且つ前記新たに構築された取りのけキューよりは短い前記既存の取りのけキューに、前記新たに構築された取りのけキューへのリンクを設ける工程と、を備える。
【００４３】
一の取りのけキューから別の取りのけキューにリンクを設けることにより、アウトオブオーダー効果を回避しつつ、同時に輻輳木の根を更に下流へ移動可能にできる。
【発明を実施するための最良の形態】
【００４４】
本発明に係る実施例の例を添付の図面を参照して詳述する。
【００４５】
図２は、スイッチ２及び４のネットワークを示す模式図である。スイッチ２及び４は、夫々、複数のイングレスポートＡからＣと、複数のイーグレスポート０から２とを有する。通常の使用では、即ち、輻輳がない場合は、データパケットは、スイッチのイングレスポートＡからＣで受信され、スイッチ２及び４の出力ポート０から２のいずれか一つに送られる。ネットワークは、ＬＥＣＮ（Local Explicit Congestion Notification)プロトコルを動作させて、例えば、スイッチ４上のポートが輻輳状態になった場合に、スイッチ４は、その詰まりをなくすために、上流側のデータ送信中のスイッチのポートに対して、一時的に送信を停止、又は何らかの方法で送信を変化させるように、信号を送信する。この例では、スイッチ４のポート０からスイッチ２のポート０へ、一時的に送信を停止するように指示する信号が送られる。スイッチ４のポート０へ向かうデータは、スイッチ２のポート０で、取りのけキュー(ＳＡＱ：set aside queue)に入れられる。その他の可能なデータ経路、例えば、スイッチ２のポート０からスイッチ４のポート１までのデータ経路は、影響を受けない。
【００４６】
図３は、図２を参照して説明したようなＬＥＣＮプロトコルを用いる、スイッチ６、８及び１０の従来型ネットワークの一例を示す。この場合、スイッチ１０のポート０で輻輳が検出されると、スイッチ１０のポート０に向かうことになっているデータの送信を停止する旨の通知が、スイッチ８のポート０に送信される。スイッチ８のポート０がその後に輻輳状態になった場合、同様の通知を、例えば、スイッチ８のポート０向けのスイッチ６の全入力ポートＡからＣからくるデータをブロックするスイッチ６のポート０に送信する。ここで、この輻輳に無関係のデータ、例えばスイッチ６のポートＢから、スイッチ６及び８の夫々のポート０を介してスイッチ１０のポート１へ向かうデータについても、ブロックされている。従ってＨＯＬブロッキングが生じ、輻輳木が成長する。説明したように、輻輳木の作成は、全ネットワークの動作に対して深刻な影響をもたらすおそれがある。
【００４７】
図４Ａは、本発明の実施例に係るある特定種類のスイッチの一例を示す模式図である。このスイッチは、複数のイングレスポート３と複数のイーグレスポート５を備える。イングレスポート３は、ネットワーク内のその他のスイッチからデータパケットを受信するように設定されている。イーグレスポート５は、一又は複数のイングレスポート３からデータパケットを受信し、データパケットに前方へ進む経路を提供するように設定されている。スイッチアーキテクチャ７を設けて模式的に示すが、スイッチアーキテクチャ７は、一又は複数のイングレスポート３から、選択された一又は複数のイーグレスポート５へ向かうデータパケットの結合を制御可能とする、任意の適切な種類のアーキテクチャであってよい。
【００４８】
イングレスエンジン９は、各イングレスポート３に設けられる。イーグレスエンジン１１は、各イーグレスポート５に設けられる。以下に説明するように、イングレスエンジン９は、イングレスポート３へ入力するデータパケットを検出し、そのデータパケットを、イングレスポート３内部の輻輳状態ではない仮想出力キュー、即ちコールドキュー１３を介して特定のイーグレスポートへ送るように、或いは、ある状況では、受信したデータパケットを、イングレスポート３内部のＳＡＱ１５を介して選択的に送るように作動する。
【００４９】
同様に、イーグレスエンジン１１は、イングレスポートから入力されるデータパケットを検出し、そのデータパケットを、イーグレスポート５内部のコールドキュー１７へ送るように、又はイーグレスポート５内部のＳＡＱ１９に送るように作動する。イングレスエンジン９及びイーグレスエンジン１１の動作は、詳細に後述する。
【００５０】
当然のことながら、図３に示すような複数スイッチのネットワークにおいて、複数スイッチ間のリンクは、デュプレックスリンクである、即ち、データは、二つの直接連結されたスイッチ間で、双方向に直接受け渡しが可能である。よって、図４Ａにおいて、データパケットと制御データは、イングレス及びイーグレスポート間の十字形として模式的に示されたスイッチファブリック（コア）により、スイッチ内部のイングレス及びイーグレスポート間で受け渡しされる。
【００５１】
以下に説明するように、受信したデータパケットのルーティングを決定する等のイングレスエンジン９又はイーグレスエンジン１１として、任意の適切な手段が設けられてよい。本発明の好適な実施例において、イングレスエンジン９とイーグレスエンジン１１は、コンテントアドレッサブルメモリ（ＣＡＭ: Content Addressable Memory）によって提供される。これは、ハードウェアにより実装可能であり、従って、高速で動作可能であるという利点を有する。通常、機構は、数百ギガビットまでのリンク又はポートビットレートに対処しなければならない。複数スイッチのネットワークにおいては、数テラビットの全スループットを実現可能であろう。
【００５２】
ここで、イングレスエンジン９及びイーグレスエンジン１１の動作をより詳細に説明する。イーグレスエンジン１１を参照すると、イーグレスポート５は、ネットワーク内部のスイッチのダウンストリームイーグレスポートから、その対応するリンクイングレスポートを介して要求を受け取る。その要求は、ＳＡＱ１９を構築する要求等である。その要求は、多数の必要条件に対して考慮及び確認され、またその必要条件にあうならば、イーグレスエンジンは、ＳＡＱ１９を構築する。ＳＡＱ１９が一旦構築されると、イーグレスエンジンは、一又は複数のイングレスポートから受信される入力データパケットの目的地を決定し、そのデータパケットをイーグレスポート５内部のコールドキュー１７又はＳＡＱ１９のいずれかに選択的に送るように作動する。
【００５３】
イングレスポート３は、同等の特性を含み、イーグレスポート５の動作と同様に動作する。しかしながら、ＳＡＱの構築の要求は、イーグレスポートＳＡＱで閾値に達する際、イーグレスポートにより、イングレスポートに送信されるのみである。従って、ＳＡＱの使用及び通知トラフィックは最小化される。イングレスポート３及びイーグレスポート５に関する上記の説明は、もちろん、簡潔な説明である。ここで、イングレス及びイーグレスポートが動作するプロトコルについて、より詳細に説明する。
【００５４】
図４Ｂは、本発明の実施例に係るスイッチ５０の一例におけるイングレスポート及びイーグレスポートを示す模式図である。この例では、スイッチ５０は、（Ｎ＋１）個のイングレスポートと（Ｎ＋１）個のイーグレスポートを備える。図に、イングレスポート０及びイーグレスポート０のみが詳細に示されている。イーグレスポート０を参照すると、イーグレスエンジン１１は、図４Ａを参照して説明したように設けられている。イーグレスエンジン１１は、コンテントアドレッサブルメモリ（ＣＡＭ）６２との通信に適しており、接続されたダウンストリームスイッチのポートからイングレスポートを介して受け取った要求に応じて、複数のＳＡＱ６４を生成するように作動する。
【００５５】
エンジン１１は、複数のコールドキュー５６との通信も行うように設定されている。ＣＡＭ６２は、複数のＳＡＱ６４と、葉トークン信号に設けられたストレージ６６と通信するように設定されている。この目的を以下に詳述する。一般に、イーグレスポート０が、ダウンストリームポートへ向かうデータパケットを格納するアップストリームポートにおけるＳＡＱの構築を要請する要求をアップストリームポートに送信する場合、葉トークン信号が、その要求とともに送信され、これがストレージ又はトークンメモリ６６に記録される。この要求がポートで受信されると、トークン信号は、アップストリームスイッチのイングレスポートにフラグとして格納される。トークン信号を有しているので、以下により詳細に説明するように、ある条件が満たされる場合にＳＡＱが崩壊することになる。
【００５６】
相互接続した複数スイッチのネットワーク内部におけるスイッチに対する一般的な適用性と同様に、一の可能な実施例では、本発明は、ネットワーク内部のエンドステーションにも関する。図４Ｃは、本発明の実施例に係るエンドステーションの例を示す模式図である。この例では、エンドステーションは、単一のイングレスポート７０と、イーグレスエンジン７４を含む単一のイーグレスポート７２とを備える。エンドステーションは、イングレスポート及びイーグレスポート間にデータパケットの選択的ルーティングがないこと以外は、本願で詳述したスイッチと同様に動作する。
【００５７】
ＳＡＱの構築の要求が、ダウンストリームスイッチからイングレスポート７０で受信されると、その要求はイーグレスポート７２内部のイーグレスエンジン７４へ受け渡される。イーグレスエンジンは、図４Ａ及び図４Ｂを参照して上述したイーグレスエンジンと同様に機能する。言い換えれば、データパケットが、要求元である下流の輻輳ポートに向かっているか否かに応じて、複数のＳＡＱを構築するように機能し、また、コールドキュー又はエンドステーション内部のＳＡＱに対するデータパケットの選択的ルーティングを可能とするために、ＣＡＭにおけるエントリを割り当てるように機能する。
【００５８】
図５は、本発明の実施例に係るスイッチネットワークの例を示す図である。図２及び図３を参照して例示及び説明したネットワークとは対照的に、図５に示すネットワークでは、図２及び図３のネットワークに用いられ、それらを参照して説明されたＬＥＣＮプロトコルに加えて、ＲＥＣＮ（Regional Explicit Congestion Notification)プロトコルが用いられる。
【００５９】
この例では、ネットワークは、三つのスイッチ７６、７８及び８０を備える。各スイッチは、三つのイングレスポートＡからＣと、三つのイーグレスポート０から２とを備える。一のスイッチ又は複数スイッチのネットワークにトラフィックを注入するエンドステーション、又は、例えばスイッチ７６のスイッチ、並びに個々のスイッチ要素に、図４Ａから４Ｃを参照して説明したように、動的に割り当てられ且つ連想的に位置づけられた複数のＳＡＱのプール（集まり）が設けられる。エンドステーション内部、又は単一ステージスイッチ要素７６において、これらのキューは、ＲＥＣＮプロトコルに応じた方法で作動する。ＲＥＣＮシグナリングプロトコルは、持続的輻輳状態であるフローによって、複数のＳＡＱの割り当て、集団、割り当て解除を管理するために、複数スイッチ間及び複数スイッチを通ってＭＩＮのエンドステーションへと作動する。このような輻輳にさらされるフローは、ホットフローとして知られており、その他のタイプのフローは、コールドフローと称される。
【００６０】
コールドフローは、その目的地にかかわらず、図４Ａから図４Ｃを参照して説明したイングレス又はイーグレスポート内部に形成されるコールドキューに常に位置づけされる。よって、バッファ要求は最小化される。このストラテジは、重要なＨＯＬブロッキングを導入しない。コールドフローがブロックされないからである。輻輳が検出されると、次のことが起きる可能性がある。例えば、特定のポートのコールドキューである閾値に達する場合、輻輳ポートに関する情報を含む通知が上流に送信される。
【００６１】
通知がアップストリームイングレス又はイーグレスポートで受信されると、輻輳ポートに関する情報は、ＣＡＭにより、先に格納された通知と比較される。一の実施例では、その情報は、無関係の場合のみ又は先に格納された通知よりも一般的である場合のみ、受理される。さもなければ、その通知は廃棄される。通知が受理されると、それを示すコンテントアドレッサブルメモリ等のメモリ内のラインが割り当てられる。加えて、対応するＳＡＱが割り当てられる。
【００６２】
アップストリームスイッチへの入力パケットが分析され、それらの対象のパスは、ＣＡＭラインに対して比較される。対等の場合、パケットは、ホットフローに属するものとして知られ、複数のＳＡＱがどこに構築されたかに応じて、イングレスポート又はイーグレスポートのいずれかの対応するＳＡＱに格納されるであろう。よって、このパケットが導入してしまいかねない任意の潜在的ＨＯＬブロッキングは除去される。
【００６３】
ポートにおけるＳＡＱが満たされるにつれ、いっぱいになる時間、又は少なくともある閾値レベルまで満たされる時間がくるであろう。この点において、パケットがポートで受信され、例えばＳＡＱがイーグレスポート内部にある場合は、特定のイーグレスポートから一又は複数のイングレスポートまで、通知が送信される。言い換えれば、通知は、イーグレスポートのＳＡＱで閾値が達成される際にイングレスポートに送信されるのみであり、そのＳＡＱ用の入力パケットが受信される。このように、ＳＡＱの使用と通知トラフィックは最小化される。通知が受理されるたびに、それは、要求を受信するポートによって要求を送信したポートに対して送られたメッセージにより確認される。ＣＡＭラインＩＤは、その応答に含まれる。そのようにすることで、フロー制御は複数のＳＡＱ間で容易に実施される。
【００６４】
一例では、フロー制御は、Ｘｏｎ及びＸｏｆｆ、即ち、スイッチのＯＮ及びＯＦＦメッセージのアップストリームノードに対する送信に基づいてよい。
【００６５】
好適な例では、通知は、トークン信号を上流に広める。このトークン信号は、輻輳木における葉ノード、即ち、輻輳木内部のあるスイッチのポートを識別する。また、（要求の送信元である）すべてのイーグレスポートにおいて、現スイッチ内部のアップストリームイングレスポートへ送信したトークン信号数を追跡するために、記録が維持される。
【００６６】
輻輳が消え、ある時間周期の間割り当てられていた所与のＳＡＱが空になると、対応するポートがトークン信号を有する場合には、割り当て解除される。関連するＣＡＭラインも割り当て解除される。割り当て解除は、ダウンストリームポート又はスイッチへ通知され、葉ノードの割り当て解除されたＳＡＱが有するトークン信号は、ダウンストリームスイッチに向かって戻される。
【００６７】
所与のイングレスポートは、割り当て解除通知を受信すると、葉トークン信号の所有者となり、従って葉ノードとなる。所与のイーグレスポートは、葉ノードになる前に戻ってきたすべてのアップストリームトークン信号を有していなければならない。そのときになってようやく、対応するＣＡＭラインは、それ自体で割り当て解除機構を開始することができ、特定のスイッチポートが輻輳木の根ではない限り、割り当て解除通知をダウンストリームスイッチのポートへ伝えることになる。
【００６８】
以上の説明において、ＲＥＣＮプロトコルの動作を管理するために複数のＣＡＭを用いている。当然のことながら、複数のＣＡＭは、ハードウェアの使用とともに実施可能であり、従ってＲＥＣＮプロトコルにおいて非常に早いステップの制御が可能である。もちろん、その他の手段を用いて、このような制御を行ってもよい。実際、入力パケットから輻輳ポートへ向かっているのか否かを識別可能であり、よってＳＡＱ又はコールドキューのいずれかに対するルーティングを可能とする任意の手段が用いられてよい。
【００６９】
図６は、ネットワークにおけるスイッチのポートに設けられたコールドキュー及びＳＡＱの模式図である。図に示すように、コールドキューは、データパケットが送信されるポートにより識別されるデータパケットの表を含む。ＣＡＭは、複数のライン０から２を含み、各ラインは、ＳＡＱＣＡＭラインの細部にあるパケットの表示を含む（図示しない）。コールドキューは、例えばＡ０、Ｂ０及びＣ０のパケットに加えて、複数のマーカーＬＢ及びＬＣを備える。これらは、データパケットの発生順を維持するために、コールドキュー内部のリンクとして作用する。マーカーは、関連するスケジューラに対してＳＡＱを視認可能とするように作用する。
【００７０】
データパケットは、スイッチに到着すると、ＣＡＭにより処理される。ＣＡＭは、その目的地を、格納している下流の輻輳に関する情報と比較する。パケットが、輻輳状態だと分かっているポートへ向かっていると判断した場合は、パケットは対応するＳＡＱに向かい、対応するポートのコールドキューにマーカーが設けられる。しかしながら、パケットが、輻輳状態だと分かっているポートへ向かっていないと判断した場合は、パケットは、対応するＳＡＱに向かわず、むしろポートのコールドキューに直接送られる。
【００７１】
一般に、データパケットを複数スイッチネットワーク内部で送る二つの方法がある。これらは、ダイレクトネットワークアドレス指定方法(direct network addressing methods)と、ターンプールルーティングとして知られる決定論的ソースルーティング(deterministic source routing)である。ダイレクトネットワークアドレス指定方法では、パケットは、その出発点で、最終目的地を知らされる。パケットが、目的地への途中で、複数のスイッチによって受信されると、スイッチ内のルックアップテーブルが参照され、このルックアップテーブルから、パケットが目的地への経路を継続したままとなるような適切なイーグレスポートが決定される。
【００７２】
一方、決定論的ソースルーティングでは、最初に、バイナリ指示がパケットに出される。この指示は、出発点から目的地までの、パケットに対する全経路を含む。本発明では、ルーティング動作を可能とする速度が増加するため、決定論的ソースルーティング、即ちターンプールの使用が好ましい。
【００７３】
ターンプールは、パケットヘッダにおける一組の連続可変サイズフィールドと、ポインタとからなる。ポインタは、ソースエンドポイントにより初期化され、イングレスポートに関連して、第１ダウンストリームスイッチにおけるイーグレスポートのアドレスを特定する、ターンプールにおける第１有効フィールドをアドレス指定する。フィールドのサイズは、スイッチにおける全ポートに対する上記のアドレス指定動作を可能とするのに十分な大きさである。パケットがファブリックを横断すると、即ち、連結スイッチのネットワークを移動すると、ポインタは、次のダウンストリームスイッチにおけるポートのアドレスとなる、ターンプールにおける次のフィールドをアドレス指定するために、各スイッチにおいて変更される。パケットが適切なエンドポイントに到達するとき、ターンプールに残存フィールドがあってはならない。
【００７４】
ＣＡＭアドレス指定動作で参照されるマスクサイズ機構は、ＣＡＭをアドレス指定するのに用いられるターンプールフィールドのサイズ（又は範囲）を限定する手段、及び／又は、格納データにおけるフィールドのサイズ（又は範囲）識別する手段と、を備える。ファブリックは、ターンプールサイズ（３１ビットに限定される）により可能とされる最大サイズよりも小さい一連の連結スイッチから構成することができる。或いは、ネットワーク内部の任意の場所で輻輳は発生可能である。従って、根ノード及び葉ノード間のスイッチをアドレス指定するのに必要なターンプール内部のフィールドのみが、ＣＡＭ動作に関連しており、これらは各ＣＡＭで決定されなければならない。
【００７５】
不規則ネットワークを通るパスが、その他のパスよりも長い／短い、即ち、特定するのにより多くの／少ないターンプールビットをとるので、配置動作は必要である。よって、ターンプール内部にある既知の現在位置は、配列の比較に用いなければならない。
【００７６】
例えば、順に１６個のポート、８個のポート、及び４個のポートを有する３個のスイッチのネットワークの例を考える。これらのスイッチは、夫々、ターンプールにおいて、４ビットフィールド、３ビットフィールド、及び２ビットフィールドを必要とする。これらは、ターンプールにおいて、ビット８から５、４から２、及び１から０に配列するであろう。輻輳が真ん中のスイッチで発生する場合、複数のＣＡＭで用いられるターンプールフィールドは、ビット２から上位であろう（４に向かって、その後この場合は８に向かうが、最大ファブリックにおいてビット３０に向かうであろう）。
【００７７】
このように、ＣＡＭは、データパケットの迅速な処理、即ち、ＳＡＱ又はコールドキューにおける位置決めを、その目的地に応じて行うために使用できる手段の一例である。ＣＡＭは、ダウンストリームポートから受信したＳＡＱ形成要求を処理でき、アップストリームポートから受信したデータパケットに対するデータパケット割り当てを処理できる。一例では、ＣＡＭは、受信した要求がＣＡＭの既存する任意のエントリよりも特異であるかを決定するように設置される。これは、任意の既存のエントリが新たな要求と部分的に一致するかを検出することにより達成される。部分的に一致する場合は、新たな要求は、ＣＡＭの既存する任意のエントリよりも特異である。一の実施例では、ポートが位置する輻輳木の根よりも更に下流にあるポートが参照されるので、このような要求は拒絶される。以下に説明するように、これは、アウトオブオーダー効果を引き起こすおそれがある。
【００７８】
ＣＡＭの更なる特性は、ターンプールビットに対するライン配置構造である。一の実施例では、輻輳ポートに対するすべてのダウンストリームスイッチ用のアクティブターンプールビットは、ＣＡＭにおいて左詰めでなければならない。これにより、パケットの目的地を正しく決定できる。
【００７９】
ここで、ＲＥＣＮプロトコルについて詳細に説明する。この例において、ＲＥＣＮプロトコルは、４つのメッセージで構成されている。それらは、以下の通りである。
１．ＳＡＱの構築要求
２．アクノリッジメント（確認）
３．フロー制御
４．割り当て解除
はじめに、ポートで輻輳が検出されると、ＲＥＣＮプロトコルに従って動作しているポートは、輻輳ポートにデータパケットを送信しているアップストリームポート（どこで輻輳が発生したかに応じて、イングレスポート又はイーグレスポートでありうる）に、ＳＡＱの構築を要求する要求メッセージを送信する。
【００８０】
一旦、この要求がアップストリームポートにより受信され、ある基準が満たされ、ＳＡＱが構築されると、アップストリームポートは、ＳＡＱが構築された旨をダウンストリームポートに知らせるアクノレッジメントメッセージを、要求が発生したダウンストリームポートに送信するよう制御される。
【００８１】
次に、ＳＡＱから輻輳が発生した（又は輻輳が発生した点に一段階（ステージ）近い）ポートへのデータパケットの流れを制御するために、フロー制御メッセージが、ダウンストリームポートにより、ＳＡＱが構築されたアップストリームポートに向けて送信される。フロー制御メッセージは、例えば、送信停止、送信開始、及び送信の調整等の複数の指示のうちのいずれか一つを含んでよい。ＲＥＣＮプロトコルの最終メッセージは、アップストリームポートにより、ダウンストリームポートに向けて送信される、ＳＡＱが割り当て解除されている旨をダウンストリームポートに知らせる割り当て解除メッセージである。これには、多くの理由が考えられる。例としては、ＳＡＱが空になった、その他のデータパケットがＳＡＱに受信されないまま所定の時間が過ぎた等が挙げられる。
【００８２】
一例では、ＳＡＱの構築要求メッセージが、あるポートによりアップストリームポートに送信されるたびに、トークン信号がその要求メッセージとともに送信される。トークン信号は、上述のように、輻輳木における葉ポートを識別する。従って、輻輳木におけるすべての葉は、トークン信号を含むであろう。加えて、ネットワークにおける複数スイッチ内部の全イーグレスポートにおいて、輻輳木の異なる複数の枝を介してアップストリームポートへ送信したトークン信号数を追跡するために、記録が維持される。
【００８３】
所与のイーグレスポートは、割り当て解除通知を受信すると、アップストリームに向けて先に送信したトークン信号のすべてを受信するまで待機する。そのときになってようやく、対応するＳＡＱとＣＡＭラインは、割り当て解除メッセージを開始させることができ、スイッチ自身が輻輳木の根ではない限り、割り当て解除通知をダウンストリームスイッチへ伝えることになる。これにより、ＳＡＱの割り当て解除が可能か否かをポートが知る手段が提供される。
【００８４】
ここで、図７及び図８を参照する。図７は、本発明の実施例に係るネットワークの例を示す模式図である。この例では、複数のＳＡＱがスイッチイーグレスポート０に位置する。またこの図は、ダウンストリームスイッチポート又はネットワークのエンドポイントを参照するＣＡＭエントリも示す。ＣＡＭライン０は、輻輳源Ｃ０に対するコンテンツを示す。ＣＡＭライン１は、輻輳源Ｅ１に対するコンテンツを示す。
【００８５】
図８は、類似の配置を示しているが、この場合、各スイッチは２個のイングレスポートと２個のイーグレスポートを有するだけである。先ず、輻輳がエンドポイントＥ１で発生すると、ＬＥＣＮプロトコルを用いて、スイッチＣのイーグレスポート０でＳＡＱが構築される。続いて、複数のＳＡＱが上述のＲＥＣＮプロトコルを用いて構築される。この例では、ＣＡＭライン０は、輻輳源Ｃ０に関連し、ＣＡＭライン１は、輻輳源Ｅ１に関連する。スイッチが輻輳源から遠く離れるにつれて、ＣＡＭラインにおけるエントリがより特異的になり、輻輳木の根に至るまでの輻輳木内部で、最も上流のポートで複数のパケットを識別するために使用できる。
【００８６】
ここで、複数スイッチのネットワーク内部における輻輳管理方法の二つの更なる例について詳細に説明する。これらの例では、輻輳木の根の下流への移動が実現される。好ましくは、これはアウトオブオーダー効果の回避を確保しながら実現される。両方の場合において、既存する「本来の」輻輳木における任意のポートで受信されるデータパケットの格納要求が、その本来の輻輳木の根よりも更に下流のポートにおける輻輳に関する場合、その要求は、その更に下流のポートに向かうことになっているデータパケットを、その要求が受信されるポートで格納するように受理される。言い換えれば、輻輳木の根は、下流に移動する。
【００８７】
上述のように、あるポートにおける取りのけキューの構築要求が受信される際、その特定の（更に下流の）ポートで輻輳が発生した旨のエントリをメモリで作成することが好ましい。データパケットは、そのポートで受信されると、メモリにおける一又は複数のエントリに対して確認される。仮にデータパケットが輻輳ポートに向けられている場合、そのデータパケットは、対応する取りのけキューに格納される。
【００８８】
図１を参照して説明したように、輻輳木の根が下流に移動可能とすることが望ましい特定のネットワーク構成があることが好まれている。本発明の一例では、これは、複数のＳＡＱの構築要求が、既に存在する最も下流のポートよりも更に下流の輻輳ポートに関するものであったとしても、その要求のすべてを受理することにより達成される。これにより、ＲＥＣＮ通信プロトコルの利益を得ながら、同時にネットワークのバンド幅の利用を最大化することが可能となる。
【００８９】
図９は、ＣＡＭと、当該ＣＡＭにおけるエントリに基づき形成された複数のＳＡＱ８４、８６、８８及び９０の表示８２である。ＣＡＭに４個のエントリがあり、夫々、ＣＡＭの行０から３に設けられていることが分かる。
【００９０】
ＣＡＭのＡ１Ｂ１Ｃ１に基づき形成されたＳＡＱ９０は、この例において、複数のＳＡＱのうちの「最長」ＳＡＱと称されてよい。この「最長」とは、ＳＡＱに格納されたデータパケットの数を参照するものではないが、それを生じさせたＣＡＭエントリは最長である、即ち、最高数のステージを有するという事実を参照するものである。同様に、ＳＡＱ８８は、最低数のステージ（唯一のステージ）を有するので、この例で、「最短」ＳＡＱと称されてよい。
【００９１】
一のＳＡＱ８４は、経路Ａ１／Ｂ１に沿ってポートＢ１に向かうことになっているデータパケットを格納するように形成される。別のＳＡＱ８６は、経路Ａ１／Ｂ２に沿ってポートＢ２に向かうことになっているデータパケットを格納するように形成される。別のＳＡＱ８８は、ポートＡ１に向かうことになっているが、経路Ａ１／Ｂ１又はＡ１／Ｂ２のいずれにも向かうものではないデータパケットを格納するように形成される。最後に、ＳＡＱ９０は、ポートＡ１及びＢ１を介してポートＣ１に向かうことになっているデータパケットを格納するように形成される。
【００９２】
ＳＡＱ９０がＳＡＱ８４の後に形成される場合、ＳＡＱ９０の構築前に到着したＳＡＱ８４のデータパケットがあることが好ましい。これらのデータパケットがＳＡＱ９０の構築後に到着した場合は、ＳＡＱ８４ではなくＳＡＱ９０に格納されていたであろう。この例では、ＳＡＱ８４に格納されているデータパケットＡ１Ｂ１Ｃ１が、ＳＡＱＳＡＱ９０の構築後に到着した場合は、ＳＡＱ８４ではなくＳＡＱ９０に格納されていたであろう。
【００９３】
これが、アウトオブオーダー効果に遭遇する場合である。この問題に取り組む一の方法は、既存の輻輳ポート（この場合Ｂ１）よりも更に下流の（ポートこの場合Ｃ１）に関するＳＡＱの構築要求が受信される場合に、その要求を無視することを規定することである。言い換えれば、アウトオブオーダー効果を回避するために、本来の輻輳木の根を下流に移動させることはできないと決定される。
【００９４】
輻輳木の根を下流に移動させることが要求される場合にも、依然アウトオブオーダー効果を回避することができる。これを実現しうる一の方法は、ＳＡＱ構築の要求をすべて受理し、且つ参照する輻輳の位置に関係なく受信された新たなＳＡＱ形成要求の夫々に対して、新たなＣＡＭライン（及び対応するＳＡＱ）を形成することによる。これには、本来の輻輳木の根よりも更に下流のポートに向かうことになっているデータパケットに対する複数のＳＡＱ構築要求が含まれる。この場合、アウトオブオーダー効果が回避されるべきであれば、後に新たに形成されたＳＡＱをアクティブにするために、既存の一又は複数のＳＡＱにリンクが設けられる。リンクは、それが指し示すＳＡＱを、スケジューラに対して視認可能とするように作用する。
【００９５】
図１０は、ネットワークのポートにおけるデータパケットの到着順序、及びそのポートに形成される複数のＳＡＱを示す図である。この図は、コールドキューに配列されるデータパケットと複数のＳＡＱを示している。図を参照すると、データパケット０から４４は、ポートに到着すると示されている。各データパケットが到着すると、その所望の目的地がＣＡＭのエントリに対して確認される。ＣＡＭに対応するエントリがある場合、データパケットは、対応するＳＡＱに置かれる。ＣＡＭに対応するエントリがない場合、データパケットは、コールドキューに置かれる。
【００９６】
明確にするために、そのデータパケットの表に多数のデータパケットを含めていない。例えば、５から９、１５から１９、２５から２９等のデータパケットが示されていない。先ず、データパケット０、Ａ１Ｂ１Ｃ１、即ち、ポートＡ１及びＢ１を介してポートＣ１に向かうことになっているデータパケットがポートに到着することが分かる。次に、データパケットＡ１Ｂ１Ｃ２が続く。パケット４の到着後、要求Ａ１Ｂ１がポートに到着する。これは、ポートＡ１を介してポートＢ１に向かうことになっているデータパケットに対するＳＡＱの構築要求である。経路Ａ１Ｂ１を、すべての又は一部の指定経路として有するデータパケットのすべてが、このステージに他にＳＡＱが存在しない場合に、ＳＡＱ  Ａ１Ｂ１に格納されるであろう。例えば、経路Ａ１Ｂ１Ｃ１、Ａ１Ｂ１Ｃ２、及びＡ１Ｂ１Ｃ３等を有するデータパケットは、ＳＡＱ  Ａ１Ｂ１に格納されるであろう。ＳＡＱ  Ａ１Ｂ１が構築され、要求に応じて構築されたＳＡＱ  Ａ１Ｂ１にコールドキューをリンクするアクティブリンク（Ｒ／Ｌ  Ａ１Ｂ１）が、ポートのコールドキューに設けられる。
【００９７】
パケット１０及び１１（Ａ１Ｂ１Ｃ１及びＡ１Ｂ１Ｃ２）が到着し、これらが構築されたＳＡＱ  Ａ１Ｂ１に設けられる。パケット１２から１４は、それらが向かう経路Ａ１Ｂ２Ｃ１、Ａ１Ｂ２Ｃ２及びＡ１Ｂ３Ｃ１のいずれにも現在ＳＡＱが存在しないので、コールドキューに格納される。パケット１４の後に、ポートＡ１に向かう又は介したすべてのデータパケットに対するＳＡＱの構築要求が受信される。この要求は、ＳＡＱが既に存在するポートよりも、当該要求を受信するポートにより近いポート（即ち、より少ない状態で分離しているステージ）に関するものである。それは、「あまり特異的ではない」要求である。ＣＡＭラインＡ１は、対応するＳＡＱのように形成される。ＳＡＱ  Ａ１へのリンクは、コールドキューに設けられる。順に到着するパケット２２から２４は、各パケットがポートＡ１を介するが、その後ポートＢ１は介さないように設定されているので、ＳＡＱ  Ａ１に置かれる。
【００９８】
パケット２４の後に、経路Ａ１Ｂ１Ｃ１に向かうことになっているデータパケットに対するＳＡＱ構築のための要求Ａ１Ｂ１Ｃ１が到着する。これは、既に存在する最も下流の輻輳ポートよりも更に下流の輻輳、即ち、既存又は本来の輻輳木の根よりも更に下流の輻輳に関する要求である。この要求は、いずれの既存の複数ＳＡＱ（Ａ１Ｂ１及びＡ１）よりも「より特異的」と表現してよい。従って、対応する新たなＳＡＱ  Ａ１Ｂ１Ｃ１が構築され、その新たなＳＡＱ  Ａ１Ｂ１Ｃ１用のアクティブリンクが、可能なアウトオブオーダー効果を回避するために、既存のＳＡＱに設けられる。リンクは、最長の既存ＳＡＱ、即ち、最大数のステージを含むＣＡＭエントリに対応するが、新たなＳＡＱより少ないステージを含むＳＡＱに設けられる。言い換えれば、この場合、ＳＡＱ  Ａ１Ｂ１Ｃ１へのリンクが、ＳＡＱ  Ａ１ではなく、ＳＡＱ  Ａ１Ｂ１に設けられる。
【００９９】
ここで、続いて到着するパケット３０は、ＳＡＱ  Ａ１Ｂ１Ｃ１に置かれる。しかしながら、既にＳＡＱ  Ａ１Ｂ１内にあるパケット１０及び２０の後に送信されるのみであるので、アウトオブオーダー効果のおそれはない。より特異的なＳＡＱ要求を受理することにより、輻輳木の根を下流に移動させることが好ましい。
【０１００】
ここで、アウトオブオーダー効果を回避しつつ、輻輳木の根を更に下流に移動させることができる方法の別の例を説明する。この例では、新たな要求が到着する際にＣＡＭラインが上書きされ、その新たな要求は、既存のＣＡＭラインにより既定される経路の全ステージを含むか、もしくは既存のＣＡＭラインよりもあまり特異的ではない。
【０１０１】
要約すれば、この例は以下のことを必要とする。
【０１０２】
（ａ）新たなＳＡＱの構築要求が、既存の根ポートよりも更に上流にある根ポートに関する場合、最短の、即ち最も特異的でない既存ＣＡＭライン及びその対応するＳＡＱが上書きされる。上書きされたＣＡＭラインに対応する新たなＳＡＱに対してコールドキューにリンクが設けられ、本来の（今上書きされている）ＳＡＱに対するコールドキュー内の任意の既存アクティブリンクが無効とされる。
【０１０３】
（ｂ）ＳＡＱ構築の新たな要求が、既存の根ポートよりも更に下流にある根ポートに関する場合、最短の（最も特異的でない）既存ＳＡＱが上書きされ、上書きされたＳＡＱは、コールドキューの終端部にリンクされる。即ち、実際には、最も特異的でない既存ＳＡＱにおけるすべてのエントリが、コールドキューの終端部に設けられる。アクティブリンクは、最長の（最も特異的な）残存ＳＡＱに、又はＳＡＱが存在しない場合は、コールドキューに設けられる。
【０１０４】
ここで、図１１を参照してこの例を説明する。図１１は、連結スイッチネットワークにおける一つのスイッチのポートで形成された複数のＳＡＱとコールドキューを示す図である。図１０に示す例と同様に、明確且つ簡潔にするため、多数のデータパケットが示されていない。図１１を参照すると、先ず、データパケット０から４が到着し、すべてコールドキューに格納される。パケット４の後に、経路Ａ１Ｂ１に向かうことになっているパケットを格納するＳＡＱの構築要求Ａ１Ｂ１が到着する。既存のＳＡＱがないので、Ａ１Ｂ１用のＳＡＱが構築される。Ａ１Ｂ１  ＳＡＱへのアクティブリンク（Ｒ／Ｌ  Ａ１Ｂ１）がコールドキューに設けられる。続いて到着するパケット１０及び１１は、ＳＡＱ  Ａ１Ｂ１に置かれる。パケット１２から１４が続いて到着し、コールドキューに格納される。
【０１０５】
パケット１４の後に、要求Ａ１Ｂ２が到着する。要求Ａ１Ｂ２が抵触する既存のＳＡＱがない、即ち、ＳＡＱ  Ａ１Ｂ２が形成されていないので、ＳＡＱ  Ａ１Ｂ２が形成される。ＳＡＱ  Ａ１Ｂ２へのアクティブリンク（Ｒ／Ｌ  Ａ１Ｂ２）は、コールドキューに設けられる。続いて、パケット２０から２３が到着し、それに応じて、これらがＳＡＱ  Ａ１Ｂ１とＡ１Ｂ２に置かれる。
【０１０６】
パケット２４の到着後、要求Ａ１が到着する。これは、幾つかの既存の複数ＳＡＱ（即ち、Ａ１Ｂ１とＡ１Ｂ２）よりもあまり特異的ではない要求である。この例に従って、ＳＡＱ  Ａ１Ｂ１とＡ１Ｂ２に対応するＣＡＭラインの一つが、上書きされる。即ち、新たなＣＡＭラインＡ１と置き換わる。アウトオブオーダー効果を回避するために、最短の既存ＳＡＱが、上書き用に選択される。即ち、最小数のステージを有するＣＡＭラインエントリに対応するＳＡＱである。仮に、この場合と同様に、最短ＳＡＱがない場合は、任意に（この場合、どちらかが）既に存在するより短いＳＡＱから選ばれてよい。新たなＳＡＱは、上書きされている既存のＳＡＱよりも短いので、既存のＳＡＱに既に割り付けられているデータパケットは、移動する必要はない。この理由は、新たなより短いＳＡＱのみが存在するときにデータパケットが到着した場合は、そのデータパケットは、どのみち、そのより短いＳＡＱに置かれたであろうからである。
【０１０７】
この場合、ＣＡＭエントリＡ１Ｂ２は、ＳＡＱ  Ａ１Ｂ２において任意のパケットを移動させる要求無く上書きされる。Ａ１  ＳＡＱへのリンク（Ｒ／Ｌ  Ａ１）は、コールドキューに設けられる。既存のリンクＡ１Ｂ２は、コールドキューに依然存在している場合、ここで無視されるはずである。これは、リンクにシーケンス番号を与えて、最高に一致するリンクのみがＳＡＱを活性化できるようにすることで達成される。
【０１０８】
パケット３０から３４が続いて到着し、それに応じてこれらがＳＡＱ  Ａ１Ｂ１とＡ１に置かれる。即ち、パケット３０及び３１は、ＳＡＱ  Ａ１Ｂ１に置かれ、パケット３２から３４は、ＳＡＱ  Ａ１に置かれる。
【０１０９】
パケット３４の到着後、要求Ａ１Ｂ１Ｃ１が到着する。これは、すべての既存のＣＡＭラインやＳＡＱよりも特異的な要求である。再び、ＳＡＱに対応する既存のＣＡＭラインのうちの一つが、上書きされる。最短ＳＡＱが選択される。この場合、それはＳＡＱ  Ａ１である。アウトオブオーダー効果を回避するために、既存のＡ１  ＳＡＱはコールドキューにリンク９２を介してリンクされる。実際には、ＳＡＱ  Ａ１に格納されているデータパケットは、コールドキューの終端部に移動される。これが行われない場合、新たなデータパケットＡ１Ｂ２Ｃ１、例えばパケット番号４２、ＳＡＱ  Ａ１に格納されているパケットＡ１Ｂ２Ｃ１（パケット２２及び３２）よりも前に、スケジューラによりポートからの送信用に選択されてよい。もちろん、ＳＡＱ  Ａ１は、先にＳＡＱ  Ａ１Ｂ２に割り付けられたすべてのパケットを含む。
【０１１０】
ＳＡＱ  Ａ１Ｂ１Ｃ１へのアクティブリンク９４は、次の最長ＳＡＱである既存のＳＡＱに設けられる。この場合、それはＳＡＱ  Ａ１Ｂ１である。パケット４０及び４１が続いて到着し、これらが対応するＳＡＱ（夫々、Ａ１Ｂ１Ｃ１及びＡ１Ｂ１）に置かれる。
【０１１１】
上述の例によると、一又は複数のＳＡＱ内部に、その他の複数のＳＡＱへのリンクがあることが好ましい。この例では、これはアウトオブオーダー効果を回避するために必要である。そうしなければ、より詳細な要求の受理によりアウトオブオーダー効果が発生しうるからである。
【０１１２】
本願に記載の方法は、輻輳が発生しうる複数スイッチの任意のネットワークに適用可能である。
【０１１３】
特に説明した例に関連して、本発明の実施例を説明したが、本発明の範囲内で、記載の例に対し、多数の変更及び変形が行われてもよい。
【図面の簡単な説明】
【０１１４】
【図１】スイッチネットワークの例を示す図である。
【図２】従来のスイッチネットワークを示す模式図である。
【図３】従来のスイッチネットワークの更なる例を示す図である。
【図４Ａ】本発明の実施例に係るスイッチの一例を示す模式図である。
【図４Ｂ】本発明の実施例に係るスイッチの一例におけるイングレスポート及びイーグレスポートを示す模式図である。
【図４Ｃ】本発明の実施例に係るエンドステーションの例を示す模式図である。
【図５】本発明の実施例に係るスイッチネットワークの例を示す図である。
【図６】スイッチに形成されたキューの例である。
【図７】本発明の実施例に係るネットワークの例を示す模式図である。
【図８】本発明の実施例に係るネットワークの例を示す模式図である。
【図９】コンテントアドレッサブルメモリと取りのけキューの数を示す図である。
【図１０】スイッチネットワークにおける一のスイッチのポートにおける複数のデータキューを示す図である。
【図１１】スイッチネットワークにおける一のスイッチのポートにおける複数のデータキューを示す図である。
【符号の説明】
【０１１５】
６、８、１０  スイッチ
０、１、２  出力ポート
Ａ、Ｂ、Ｃ  入力ポート
【図１】
2007526706.tif 000003
【図２】
2007526706.tif 000004
【図３】
2007526706.tif 000005
【図４Ａ】
2007526706.tif 000006
【図４Ｂ】
2007526706.tif 000007
【図４Ｃ】
2007526706.tif 000008
【図５】
2007526706.tif 000009
【図６】
2007526706.tif 000010
【図７】
2007526706.tif 000011
【図８】
2007526706.tif 000012
【図９】
2007526706.tif 000013
【図１０】
2007526706.tif 000014
【図１１】
2007526706.tif 000015
【国際調査報告】
2007526706.tif 000016
2007526706.tif 000017
2007526706.tif 000018