(57)【特許請求の範囲】
【請求項１】
スイッチ装置と、前記スイッチ装置に接続される他のスイッチ装置とを有する情報処理システムにおいて、
前記スイッチ装置は、
フローに含まれるパケットをそれぞれ送信する複数のポート部と、
前記複数のポート部に対応してそれぞれ設けられ、パケットをそれぞれ格納する複数のキュー部と、
前記複数のキュー部の各々に格納されたパケットの量に基づき、前記複数のポート部のいずれかにおける輻輳状態を検出する検出部と、
前記検出部が前記複数のポート部のいずれかにおける輻輳状態を検出した場合、前記複数のポート部のうち、前記輻輳状態が検出されたポート部の前記輻輳状態に関する輻輳情報を、前記他のスイッチ装置に接続するスイッチ装置間ポート部を介して当該他のスイッチ装置に通知する通知部と、
前記他のスイッチ装置から通知された他の輻輳情報に基づき、前記他のスイッチ装置を介した迂回路を使用できるかを判断する判断部と、
前記複数のキュー部のうち、迂回路として使用されるポート部のキュー部にパケットが格納されていないフロー集合を、対象フロー集合として選択する選択部と、
前記選択部が選択した対象フロー集合を特定するフロー集合特定情報を記憶する記憶部と、
前記判断部が、前記他のスイッチ装置を介した迂回路を使用できると判断した場合、前記フロー集合特定情報に基づき、前記対象フロー集合に含まれるフローに属するパケットを、前記スイッチ装置間ポート部を介して前記他のスイッチ装置に送出させる制御部と
を有することを特徴とする情報処理システム。
【請求項２】
前記輻輳状態が解除されると、前記対象フロー集合に含まれるフローのパケットが前記他のスイッチ装置を介した迂回路において使用されるポート部のキュー部に格納されていないときに、迂回を解除する解除部をさらに有することを特徴とする請求項１記載の情報処理システム。
【請求項３】
前記検出部は、前記複数のキュー部にキューの長さをカウントするためにそれぞれ設けられたキュー長カウンタの値と所定の閾値を比較することで前記輻輳状態を検出することを特徴とする請求項１又は２記載の情報処理システム。
【請求項４】
フロー集合毎にキュー部にパケットが格納されているか否かを記憶するパケット有無記憶部をさらに有し、
前記選択部は、パケット有無記憶部を用いて対象フロー集合を選択することを特徴とする請求項１、２又は３記載の情報処理システム。
【請求項５】
前記記憶部は、キュー部に格納されているパケットの数をカウントするカウンタとフローのパケットを迂回するか否かを示す情報とをフロー集合毎に記憶することを特徴とする請求項１〜４のいずれか１つ記載の情報処理システム。
【請求項６】
前記スイッチ装置及び前記他のスイッチ装置はスパインであり、リーフであるスイッチ装置をさらに有し、
前記通知部は、前記検出部が前記複数のポート部のいずれかにおける輻輳状態を検出した場合、検出されたいずれかのポート部の輻輳状態に関する輻輳情報を、リーフであるスイッチ装置に通知し、
リーフであるスイッチ装置は、
前記スイッチ装置から通知された他の輻輳情報に基づき、前記他のスイッチ装置を介した迂回路を使用できるかを判断する迂回判断部
を有することを特徴とする請求項１〜５のいずれか１つ記載の情報処理システム。
【請求項７】
他のスイッチ装置に接続されるスイッチ装置において、
フローに含まれるパケットをそれぞれ送信する複数のポート部と、
前記複数のポート部に対応してそれぞれ設けられ、パケットをそれぞれ格納する複数のキュー部と、
前記複数のキュー部の各々に格納されたパケットの量に基づき、前記複数のポート部のいずれかにおける輻輳状態を検出する検出部と、
前記検出部が前記複数のポート部のいずれかにおける輻輳状態を検出した場合、前記複数のポート部のうち、前記輻輳状態が検出されたポート部の前記輻輳状態に関する輻輳情報を、前記他のスイッチ装置に接続するスイッチ装置間ポート部を介して当該他のスイッチ装置に通知する通知部と、
前記他のスイッチ装置から通知された他の輻輳情報に基づき、前記他のスイッチ装置を介した迂回路を使用できるかを判断する判断部と、
前記複数のキュー部のうち、迂回路として使用されるポート部のキュー部にパケットが格納されていないフロー集合を、対象フロー集合として選択する選択部と、
前記選択部が選択した対象フロー集合を特定するフロー集合特定情報を記憶する記憶部と、
前記判断部が、前記他のスイッチ装置を介した迂回路を使用できると判断した場合、前記フロー集合特定情報に基づき、前記対象フロー集合に含まれるフローに属するパケットを、前記スイッチ装置間ポート部を介して前記他のスイッチ装置に送出させる制御部と
を有することを特徴とするスイッチ装置。
【請求項８】
フローに含まれるパケットをそれぞれ送信する複数のポート部と前記複数のポート部に対応してそれぞれ設けられるとともにパケットをそれぞれ格納する複数のキュー部とを備えるスイッチ装置と、前記スイッチ装置に接続される他のスイッチ装置とを有する情報処理システムの制御方法において、
前記スイッチ装置が有する検出部が、前記複数のキュー部の各々に格納されたパケットの量に基づき、前記複数のポート部のいずれかにおける輻輳状態を検出し、
前記検出部が前記複数のポート部のいずれかにおける輻輳状態を検出した場合、前記スイッチ装置が有する通知部が、前記複数のポート部のうち、前記輻輳状態が検出されたポート部の前記輻輳状態に関する輻輳情報を、前記他のスイッチ装置に接続するスイッチ装置間ポート部を介して当該他のスイッチ装置に通知し、
前記スイッチ装置が有する判断部が、前記他のスイッチ装置から通知された他の輻輳情報に基づき、前記他のスイッチ装置を介した迂回路を使用できるかを判断し、
前記スイッチ装置が有する選択部が、前記複数のキュー部のうち、迂回路として使用されるポート部のキュー部にパケットが格納されていないフロー集合を、対象フロー集合として選択し、
前記スイッチ装置が有する記憶部が、選択された対象フロー集合を特定するフロー集合特定情報を記憶し、
前記判断部が、前記他のスイッチ装置を介した迂回路を使用できると判断した場合、前記スイッチ装置が有する制御部が、前記フロー集合特定情報に基づき、前記対象フロー集合に含まれるフローに属するパケットを、前記スイッチ装置間ポート部を介して前記他のスイッチ装置に送出させることを特徴とする情報処理システムの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム、スイッチ装置及び情報処理システムの制御方法に関する。
【背景技術】
【０００２】
複数の情報処理装置を複数のスイッチで接続して構築される情報処理システムでは、レイヤ２の冗長化技術としてＬＡＧ（Link  Aggregation）が利用されている。図２４は、ＬＡＧを説明するための図である。図２４では、S#0〜S#3で表される４台の情報処理装置２がSwitch#0及びSwitch#1で表される２台のスイッチ９０で接続される。
【０００３】
２台のスイッチ９０は４つの物理リンク９０ａで接続されるが、ＬＡＧでは、４つの物理リンク９０ａは１つの論理リンクとみなされる。ＬＡＧをサポートしたＬ２スイッチ（レイヤ２スイッチ）間の経路は、全てアクティブな経路（通信可能な経路）として扱われるため、スイッチは複数経路を有効活用することができる。さらに、ケーブル切断時には迂回路（バックアップ）によるフェールオーバーが可能であり可用性が向上する。
【０００４】
複数経路を選択するためのアルゴリズムとしては、単純なラウンド・ロビン方式（パケット単位）は、パケットの順序逆転が起こるため、適当でない。ＩＰ（Internet  Protocol）アドレスやＭＡＣ（Media  Access  Control）アドレス等パケットの情報を元にハッシュ値を算出して、ハッシュ値に基づいてパケットの送出先の物理リンクを選択するのが一般的である。これにより、トラフィックはフロー単位で分散されるため順序反転は生じないが、物理回線数が多くなると経路選択がフロー毎のトラフィック偏りの影響を受けやすくなることが知られている。
【０００５】
なお、ＬＡＧにおいて、受信パケットのハッシュ値と優先度を保持しておき、ハッシュ値と優先度と受信パケットのバッファリング状態とに基づいて受信パケットの出力先を制御して、フロー単位でパケットを順序入れ替えを行うことなく振り分ける技術がある。
【０００６】
また、複数の回線カードに跨ってＬＡＧグループが形成されている場合であっても、ＬＡＧグループ単位の帯域制御レートをＬＡＧグループを構成する全リンクの物理帯域の合計レートまで拡大する技術がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１２−２０５０４８号公報
【特許文献２】特開２００９−２００９０５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＬＡＧでは、トラフィックの偏りにより経路で輻輳が発生した場合に、経路を変更するとパケットの順序逆転が生じるという問題がある。パケットの順序逆転は、ＴＣＰ（Transmission  Control  Protocol）の性能低下を引き起こす。
【０００９】
本発明は、１つの側面では、輻輳が発生した場合に、迂回によるパケットの順序逆転を防ぐとともに、効率の良い迂回制御を行うことを目的とする。
【課題を解決するための手段】
【００１０】
本願の開示する情報処理システムは、１つの態様において、スイッチ装置と、前記スイッチ装置に接続される他のスイッチ装置とを有する。前記スイッチ装置は、複数のポート部と、複数のキュー部と、検出部と、通知部と、判断部と、選択部と、記憶部と、制御部とを有する。前記ポート部は、フローに含まれるパケットをそれぞれ送信する。前記キュー部は、前記複数のポート部に対応してそれぞれ設けられ、パケットをそれぞれ格納する。前記検出部は、前記複数のキュー部の各々に格納されたパケットの量に基づき、前記複数のポート部のいずれかにおける輻輳状態を検出する。前記通知部は、輻輳状態が検出された場合、前記複数のポート部のうち、前記輻輳状態が検出されたポート部の前記輻輳状態に関する輻輳情報を、前記他のスイッチ装置に接続するスイッチ装置間ポート部を介して当該他のスイッチ装置に通知する。前記判断部は、前記他のスイッチ装置から通知された他の輻輳情報に基づき、前記他のスイッチ装置を介した迂回路を使用できるかを判断する。前記選択部は、前記複数のキュー部のうち迂回路として使用されるポート部のキュー部にパケットが格納されていないフロー集合を対象フロー集合として選択する。前記記憶部は、前記選択部が選択した対象フロー集合を特定するフロー集合特定情報を記憶する。前記制御部は、前記判断部が他のスイッチ装置を介した迂回路を使用できると判断した場合、前記フロー集合特定情報に基づき、前記対象フロー集合に含まれるフローに属するパケットを、スイッチ装置間ポート部を介して他のスイッチ装置に送出して迂回させる。
【発明の効果】
【００１１】
１実施態様によれば、輻輳が発生した場合に、迂回によるパケットの順序逆転を防ぐとともに、効率の良い迂回制御を行うことができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、実施例１に係るスイッチによる経路変更を説明するための図である。
【図２】図２は、実施例１に係るスイッチの構成を示す図である。
【図３】図３は、輻輳検出通知部による輻輳状態の検出及び通知を説明するための図である。
【図４】図４は、フローグループカウンタを説明するための図である。
【図５】図５は、迂回路の使用可否判断を説明するための図である。
【図６】図６は、迂回するフローの選択を説明するための図である。
【図７】図７は、迂回するフローの記録を説明するための図である。
【図８】図８は、輻輳状態解除時の迂回解除判断を説明するための図である。
【図９】図９は、スイッチがパケットを受信したときの処理のフローを示すフローチャートである。
【図１０】図１０は、ＬＡＧトラフィック制御部による迂回フロー選択の処理のフローを示すフローチャートである。
【図１１】図１１は、ＬＡＧトラフィック制御部によるフロー迂回解除の処理のフローを示すフローチャートである。
【図１２】図１２は、ＭＬＡＧを説明するための図である。
【図１３】図１３は、実施例２に係るスイッチによる経路変更を説明するための図である。
【図１４】図１４は、実施例２に係るスイッチの構成を示す図である。
【図１５】図１５は、スパイン間の制御メッセージを示す図である。
【図１６】図１６は、迂回路の使用可否判断を説明するための図である。
【図１７】図１７は、迂回するフローの記録を説明するための図である。
【図１８】図１８は、制御メッセージの送信処理のフローを示すフローチャートである。
【図１９】図１９は、制御メッセージの受信処理のフローを示すフローチャートである。
【図２０】図２０は、実施例２に係るＬＡＧトラフィック制御部による迂回フロー選択の処理のフローを示すフローチャートである。
【図２１】図２１は、実施例３に係るスイッチによる経路変更を説明するための図である。
【図２２Ａ】図２２Ａは、実施例３に係るＬＡＧトラフィック制御部による迂回フロー選択の処理のフローを示す第１のフローチャートである。
【図２２Ｂ】図２２Ｂは、実施例３に係るＬＡＧトラフィック制御部による迂回フロー選択の処理のフローを示す第２のフローチャートである。
【図２３】図２３は、実施例３に係るＬＡＧトラフィック制御部によるフロー迂回解除の処理のフローを示すフローチャートである。
【図２４】図２４は、ＬＡＧを説明するための図である。
【発明を実施するための形態】
【００１３】
以下に、本願の開示する情報処理システム、スイッチ装置及び情報処理システムの制御方法の実施例を図面に基づいて詳細に説明する。なお、実施例は開示の技術を限定するものではない。
【実施例１】
【００１４】
まず、実施例１に係るスイッチによる経路変更について説明する。図１は、実施例１に係るスイッチによる経路変更を説明するための図である。図１に示すように、実施例１に係る情報処理システム１は、S#0〜S#3で表される４台の情報処理装置２とSwitch#0及びSwitch#1で表される２台のスイッチ１０を有し、４台の情報処理装置２が２台のスイッチ１０で接続される。情報処理装置２は、情報処理を行う装置であり、スイッチ１０は、情報処理装置間の通信を中継する装置である。
【００１５】
スイッチ１０は、P#0〜P#5で表される６つのポートを有する。P#0及びP#1は、情報処理装置２に接続する。P#2〜P#5は、他のスイッチ１０に接続する。２台のスイッチ１０はP#2〜P#5を用いて４つの物理リンク１０ａで接続されるが、ＬＡＧにより、２台のスイッチ１０は１つの論理リンクで接続される。なお、図１では、説明の便宜上、４つの物理リンク１０ａで１つの論理リンクを構成するが、より多くの物理リンク１０ａでＬＡＧを構成してもよい。
【００１６】
Switch#0は、輻輳状態を検出すると、他のポートの経路の利用率等に基づいて迂回先の候補を選択する。そして、Switch#0は、迂回先の候補が輻輳していないことを確認し、迂回先の候補を迂回先として選択する。そして、Switch#0は、迂回元のキュー情報を基に経路を変更するフローを選択し、選択したフローの経路を迂回元から迂回先に変更する。また、Switch#0は、迂回元の輻輳状態が解除されると、迂回先のキュー情報を確認し、迂回しているフローの経路をもとに戻す。
【００１７】
図１では、P#5で輻輳状態が検出され、P#5からパケットが送信されるフローのうち選択されたフローの経路が迂回先へ変更される。そして、P#5の輻輳状態が解除されると、迂回先へ変更されたフローの経路がP#5の経路に戻される。
【００１８】
次に、実施例１に係るスイッチ１０の構成について説明する。図２は、実施例１に係るスイッチ１０の構成を示す図である。図２に示すように、スイッチ１０は、受信ポートＩＳＬ（Inter  Switch  Link）で表される受信ポート１１ａと、受信ポート#0〜受信ポート#31で表される３２個の受信ポート１１ｂを有する。また、スイッチ１０は、送信ポートＩＳＬで表される送信ポート１２ａと、送信ポート#0〜送信ポート#31で表される３２個の送信ポート１２ｂを有する。また、スイッチ１０は、ＣＰＵ１３（Central  Processing  Unit）と、メモリ１４と、スイッチングモジュール２０とを有する。
【００１９】
受信ポート１１ａは、スイッチ１０がＭＬＡＧ（Multi-Chassis  ＬＡＧ）のスパイン（Spine）として用いられる場合にＩＳＬを介して他のスパインから送信されるパケットを受信するポートである。なお、ＭＬＡＧ及びスパインについては、実施例２で説明する。受信ポート１１ｂは、接続される情報処理装置２又はスイッチ１０から送信されたパケットを受信するポートである。
【００２０】
送信ポート１２ａは、スイッチ１０がＭＬＡＧのスパインとして用いられる場合に他のスパインへパケットを送信するポートである。送信ポート１２ｂは、接続される情報処理装置２又は他のスイッチ１０にパケットを送信するポートである。送信ポート１２ａ及び送信ポート１２ｂは、出力キュー１２ｃを有する。出力キュー１２ｃは、スイッチ１０が出力するパケットを格納するキューである。
【００２１】
ＣＰＵ１３は、メモリ１４からプログラムを読み出して実行する中央処理装置である。ＣＰＵ１３は、プログラムを実行することにより、ＬＡＧトラフィック制御部３１の機能を実現する。ＬＡＧトラフィック制御部３１は、送信ポート１２ｂの輻輳情報及び出力キュー１２ｃの格納状態に基づいてトラフィックの経路を制御する。なお、ＬＡＧトラフィック制御部３１の詳細については後述する。メモリ１４は、プログラム、プログラム実行の途中結果等を記憶するＲＡＭ（Random  Access  Memory）である。
【００２２】
スイッチングモジュール２０は、受信ポート１１ａ及び受信ポート１１ｂが受信したパケットをパケットの宛先に基づいて送信ポート１２ａ及び送信ポート１２ｂに振り分ける。スイッチングモジュール２０は、パケット受信部２１と、ＦＤＢ（Forwarding  Database）記憶部２２と、ＦＤＢ制御部２３と、ハッシュ計算部２４と、パケット振り分け部２５とを有する。また、スイッチングモジュール２０は、輻輳検出通知部２６と、ローカル輻輳ベクタ２７と、フローグループカウンタ２８と、ローカルフローベクタ２９とを有する。
【００２３】
パケット受信部２１は、受信ポート１１ａ及び受信ポート１１ｂが受信したパケットを受信する。ＦＤＢ記憶部２２は、パケットの宛先からパケットを出力する論理ポートを検索するためのデータベースを記憶し、ＭＡＣアドレス及びＶＬＡＮ番号と論理ポート番号との対応を記憶する。ＦＤＢ制御部２３は、ＦＤＢ記憶部２２が記憶するＦＤＢを検索してパケットを出力する論理ポートを取得する。なお、以下の説明では、３２個の送信ポート１２ｂがＬＡＧにより１つの論理送信ポートであり、他のスイッチ１０の３２個の受信ポート１１ｂに各々物理リンク１０ａで接続するとする。
【００２４】
ハッシュ計算部２４は、５タプルからパケットのハッシュ値を計算する。ここで、５タプルとは、送信元ＩＰアドレス、送信先ＩＰアドレス、送信元ポート番号、宛先ポート番号及びプロトコルである。パケット振り分け部２５は、ハッシュ計算部２４により計算されたハッシュ値を送信ポート１２ｂにマッピングすることで、送信するパケットを送信ポート１２ｂのいずれかに振り分ける。
【００２５】
輻輳検出通知部２６は、送信ポート１２ｂの輻輳状態を検出し、ＬＡＧトラフィック制御部３１に通知するとともに、ローカル輻輳ベクタ２７を設定する。ローカル輻輳ベクタ２７は、送信ポート１２ｂ毎に、輻輳状態を記憶する。送信ポート１２ｂが輻輳状態になると、ローカル輻輳ベクタ２７の対応するビットが１に設定される。
【００２６】
図３は、輻輳検出通知部２６による輻輳状態の検出及び通知を説明するための図である。図３に示すように、送信ポート１２ｂは、出力キュー１２ｃの他に、出力キュー１２ｃの長さをカウントするキュー長カウンタ１２ｄを有する。キュー長カウンタ１２ｄは、出力キュー１２ｃにパケットが入力されると加算され、出力キュー１２ｃからパケットが出力されると減算される。
【００２７】
輻輳検出通知部２６は、輻輳検出の閾値を示す輻輳しきい値２６ａを記憶し、キュー長カウンタ１２ｄの値を輻輳しきい値２６ａと比較する比較部２６ｂを送信ポート１２ｂ毎に有する。そして、輻輳検出通知部２６は、比較部２６ｂの比較結果に基づいて、出力キュー１２ｃのキュー長が輻輳しきい値２６ａを超えると、ローカル輻輳ベクタ２７の対応するビットを１に設定する。また、輻輳検出通知部２６は、出力キュー１２ｃのキュー長が輻輳しきい値２６ａを超え、ＴＣＰセッション要求を受信した場合に、輻輳検出をポート番号とハッシュ値とともにＬＡＧトラフィック制御部３１に通知する。
【００２８】
また、輻輳検出通知部２６は、輻輳状態が解除されると、輻輳解除をＬＡＧトラフィック制御部３１に通知するとともに、ローカル輻輳ベクタ２７の対応するビットを０に設定する。
【００２９】
フローグループカウンタ２８は、ハッシュ値が共通するフローをグループ化したフローグループ（フロー集合）に属するパケットの出力キュー１２ｃ内の数をカウントするカウンタである。図４は、フローグループカウンタ２８を説明するための図である。図４に示すように、フローグループカウンタ２８は、フローグループ毎にエントリを有する。図４では、フローグループカウンタ２８は、group  counter#0〜group  counter#255の２５６のエントリを有する。
【００３０】
パケットの５タプルから計算されたハッシュ値の下位８ビットに基づいてフローはグループ化される。そして、出力キュー１２ｃにパケットが入力されると対応するgroup  counter#n（０≦n≦２５５）が加算され、出力キュー１２ｃからパケットが出力されると対応するgroup  counter#nが減算される。
【００３１】
なお、図４では、出力キュー１２ｃの数とフローグループカウンタ２８のエントリの数の関係は１対２５６であるが、出力キュー１２ｃの数とフローグループカウンタ２８のエントリの数の関係は整数Ｍ及びＮに関してＭ対Ｎでよい。また、図４では、パケット数に基づいてカウンタの値を増減するが、パケット長に基づいてカウンタの値を増減してもよい。また、フローグループカウンタ２８は、後述する図７に示すように、各エントリに対応付けて、フローグループが迂回されているか否かを示すビット、迂回先のポート番号を有する。
【００３２】
ローカルフローベクタ２９は、フローグループカウンタ２８の状態を示す２５６ビットのベクトルである。ローカルフローベクタ２９のビットｎは、group  counter#nの値が０の場合に０に設定され、group  counter#nの値が０以外の場合に１に設定される。すなわち、ローカルフローベクタ２９のビットｎが０であることは、対応するフローグループに属するパケットが出力キュー１２ｃにないことを示す。
【００３３】
次に、ＬＡＧトラフィック制御部３１の詳細について説明する。ＬＡＧトラフィック制御部３１は、迂回路の使用可否判断、迂回するフローの選択、迂回するフローの記録、及び輻輳状態解除時の迂回解除判断を行う。
【００３４】
図５は、迂回路の使用可否判断を説明するための図である。ＬＡＧトラフィック制御部３１は、ローカル輻輳ベクタ２７を用いて迂回路の輻輳状態を確認し、迂回路の使用可否を判断する。ＬＡＧトラフィック制御部３１は、迂回路として使用する他の送信ポート１２ｂを示す３２ビットのＣＶマスクベクタを生成し、ローカル輻輳ベクタ２７とマスクベクタのＡＮＤをとり、全て０であれば迂回路が使用可能と判断する。
【００３５】
図６は、迂回するフローの選択を説明するための図である。図６に示すように、ＬＡＧトラフィック制御部３１は、ローカルフローベクタ２９を用いて、出力キュー１２ｃにパケットがキューイングされていないフローを迂回するフローとして選択する。
【００３６】
具体的には、ＬＡＧトラフィック制御部３１は、新たにセッションを開始するＴＣＰフローについて、ＳＹＮパケットの５タプルから計算したハッシュ値の下位８ビットに基づいて２５６ビットのＦＶマスクベクタを生成する。そして、ＬＡＧトラフィック制御部３１は、ローカルフローベクタ２９とＦＶマスクベクタのＡＮＤを取り、全て０であれば、ハッシュ値の下位８ビットに対応するフローグループに含まれるフローを迂回するフローとして選択する。
【００３７】
このように、ＬＡＧトラフィック制御部３１は、新たにセッションを開始するＴＣＰフローを対象として迂回を行うことによって、ＣＰＵの負荷を増やさず、パケットの受信順序の逆転を防ぐことができる。また、ＬＡＧトラフィック制御部３１は、既に出力キュー１２ｃにキューイングされているフローグループのフローは迂回せず、キューイングされていないフローグループのフローを迂回する。したがって、ＬＡＧトラフィック制御部３１は、新たにセッションを開始するＴＣＰフロー以外で迂回されるフローグループに属するフローでパケットの受信順序が逆転することを防ぐことができ、効率の良い迂回制御を行うことができる。
【００３８】
図７は、迂回するフローの記録を説明するための図である。図７に示すように、ＬＡＧトラフィック制御部３１は、迂回するフローグループを選択すると、フローグループカウンタ２８の対応するエントリに迂回する旨を記録する。具体的には、ＬＡＧトラフィック制御部３１は、迂回を示すビットを１にし、迂回先のポート番号を記録する。例えば、図７では、group  counter#0に対応するフローグループに属するフローが迂回され、迂回先は送信ポート#2である。その後、迂回されたフローグループに含まれるフローに属するパケットは迂回される。
【００３９】
図８は、輻輳状態解除時の迂回解除判断を説明するための図である。図８に示すように、ＬＡＧトラフィック制御部３１は、迂回しているフローについて、ローカルフローベクタ２９で迂回先の送信ポート１２ｂの出力キュー１２ｃの空きを確認した後に、迂回を解除する。具体的には、ＬＡＧトラフィック制御部３１は、迂回しているフローグループに対応するビットを１に設定した２５６ビットのＦＶマスクベクタを生成し、ローカルフローベクタ２９とＦＶマスクベクタのＡＮＤをとり、全て０であれば迂回の解除が可能と判断する。
【００４０】
次に、スイッチ１０がパケットを受信したときの処理のフローについて説明する。図９は、スイッチ１０がパケットを受信したときの処理のフローを示すフローチャートである。図９に示すように、パケット受信部２１は、パケットを受信したか否かを判定する（ステップＳ１）。受信していない場合には、パケット受信部２１は、パケットの受信を待つ。
【００４１】
一方、受信した場合には、ＦＤＢ制御部２３が、宛先ＭＡＣアドレスでＦＤＢを検索し、パケットを送信する論理ポート（１以上の物理ポートで構成されるＬＡＧに対応する論理ポート）を特定する（ステップＳ２）。そして、ハッシュ計算部２４がパケットの５タプルでハッシュ計算を行い（ステップＳ３）、ハッシュ値に基づいてパケット振り分け部２５が送信ポート（パケットを送信する物理ポート）１２ｂを特定する（ステップＳ４）。
【００４２】
そして、輻輳検出通知部２６が、送信ポート１２ｂが輻輳しているか判定し（ステップＳ５）、輻輳していない場合には、ステップＳ９へ制御を移す。一方、輻輳している場合には、輻輳検出通知部２６は、オーバレイネットワークか否か判定する（ステップＳ６）。オーバレイネットワークである場合には、元のＴＣＰフレームがＵＤＰのアウターヘッダでカプセル化されるため、輻輳検出通知部２６は、パケットがＴＣＰコネクション要求か否かを判定できないので、ステップＳ９へ制御を移す。
【００４３】
一方、オーバレイネットワークでない場合には、輻輳検出通知部２６は、パケットがＴＣＰコネクション要求か否か判定し（ステップＳ７）、ＴＣＰコネクション要求でない場合は、ステップＳ９へ進む。一方、ＴＣＰコネクション要求の場合は、輻輳検出通知部２６は、輻輳検出通知（輻輳している送信ポート１２ｂの番号とパケットのハッシュ値）をＬＡＧトラフィック制御部３１に送る（ステップＳ８）。
【００４４】
そして、パケット振り分け部２５が、ハッシュ値に対応するフローグループカウンタ２８の迂回情報を参照し、迂回するフローか否かを判定する（ステップＳ９）。迂回するフローである場合は、パケット振り分け部２５は、迂回路を送信ポート１２ｂに変更し（ステップＳ１０）、迂回するフローでない場合には、ステップＳ１１へ進む。
【００４５】
そして、パケット振り分け部２５は、送信ポート１２ｂのフローグループカウンタ２８の対応するgroup  counterをインクリメントし（ステップＳ１１）、パケットを送信ポート１２ｂの出力キュー１２ｃに入れる（ステップＳ１２）。そして、送信ポート１２ｂは、パケットを出力キュー１２ｃから取り出し（ステップＳ１３）、送信ポート１２ｂのフローグループカウンタ２８の対応するgroup  counterをデクリメントする（ステップＳ１４）。そして、送信ポート１２ｂは、パケットを送信ポート１２ｂから送信する（ステップＳ１５）。
【００４６】
このように、輻輳検出通知部２６が、パケットがＴＣＰコネクション要求である場合に輻輳検出通知をＬＡＧトラフィック制御部３１に送信することによって、スイッチ１０は、新たなフローが発生したタイミングでパケットの迂回を行うことができる。
【００４７】
次に、ＬＡＧトラフィック制御部３１による迂回フロー選択の処理のフローについて説明する。図１０は、ＬＡＧトラフィック制御部３１による迂回フロー選択の処理のフローを示すフローチャートである。図１０に示すように、ＬＡＧトラフィック制御部３１は、輻輳検出通知部２６から輻輳検出通知を受信したか否かを判定する（ステップＳ２１）。受信していない場合には、ＬＡＧトラフィック制御部３１は、輻輳検出通知の受信を待つ。
【００４８】
一方、受信した場合には、ＬＡＧトラフィック制御部３１は、迂回路の候補となる他の送信ポート１２ｂがあるか否かを判定する（ステップＳ２２）。迂回路の候補がない場合の例として、同一ＬＡＧに属する他の送信ポート１２ｂが全てリンクダウンしている場合などがある。迂回路の候補となる他の送信ポート１２ｂがない場合には、ＬＡＧトラフィック制御部３１は、ステップＳ２１に戻って次の輻輳検出通知の受信を待つ。
【００４９】
一方、迂回路の候補となる他の送信ポート１２ｂがある場合には、ＬＡＧトラフィック制御部３１は、ＣＶマスクベクタのビットの中で迂回路に対応するビットを１に設定する（ステップＳ２３）。そして、ＬＡＧトラフィック制御部３１は、ＣＶマスクベクタと迂回路のローカル輻輳ベクタ２７とのビット毎のＡＮＤをとり（ステップＳ２４）、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ２５）。Ａｌｌ  ０でない場合には、ＬＡＧトラフィック制御部３１は、ステップＳ２１に戻って次の輻輳検出通知の受信を待つ。
【００５０】
一方、Ａｌｌ  ０である場合には、ＬＡＧトラフィック制御部３１は、ＦＶマスクベクタのビットの中で迂回の対象となる対象フローの属するフローグループに対応するビットを１に設定する（ステップＳ２６）。そして、ＬＡＧトラフィック制御部３１は、ＦＶマスクベクタと迂回元送信ポート１２ｂのローカルフローベクタ２９とでビット毎のＡＮＤをとり（ステップＳ２７）、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ２８）。
【００５１】
Ａｌｌ  ０である場合には、ＬＡＧトラフィック制御部３１は、対象フローを迂回するフローとして、フローグループカウンタ２８の対応するエントリに記録し（ステップＳ２９）、ステップＳ２１に戻る。一方、演算結果がＡｌｌ  ０でない場合には、ＬＡＧトラフィック制御部３１は、所定時間ウエイトし（ステップＳ３０）、所定回数に到達しているか否かを判定する（ステップＳ３１）。
【００５２】
所定回数に到達していない場合には、ＬＡＧトラフィック制御部３１は、ステップＳ２７に戻って、再度、ＦＶマスクベクタと迂回元送信ポート１２ｂのローカルフローベクタ２９とでビット毎のＡＮＤをとる。一方、所定回数に到達した場合には、ＬＡＧトラフィック制御部３１は、ステップＳ２１に戻る。
【００５３】
このように、ＬＡＧトラフィック制御部３１は、迂回元送信ポート１２ｂのローカルフローベクタ２９を参照することで、出力キュー１２ｃにパケットが格納されていないフローグループに属するフローを迂回することができる。
【００５４】
次に、ＬＡＧトラフィック制御部３１によるフロー迂回解除の処理のフローについて説明する。図１１は、ＬＡＧトラフィック制御部３１によるフロー迂回解除の処理のフローを示すフローチャートである。図１１に示すように、ＬＡＧトラフィック制御部３１は、輻輳検出通知部２６から輻輳解除通知を受信したか否かを判定する（ステップＳ４１）。受信していない場合には、ＬＡＧトラフィック制御部３１は、輻輳解除通知の受信を待つ。
【００５５】
一方、受信した場合には、ＬＡＧトラフィック制御部３１は、対応する送信ポート１２ｂのフローグループカウンタ２８を参照して迂回フローを検索し（ステップＳ４２）、迂回フローがあるか否かを判定する（ステップＳ４３）。迂回フローがない場合には、ＬＡＧトラフィック制御部３１は、処理を終了する。
【００５６】
一方、迂回フローがある場合には、ＬＡＧトラフィック制御部３１は、ＦＶマスクベクタの該当ビットを１に設定し（ステップＳ４４）、ＦＶマスクベクタと迂回先のローカルフローベクタ２９とのビット毎のＡＮＤをとる（ステップＳ４５）。そして、ＬＡＧトラフィック制御部３１は、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ４６）。
【００５７】
Ａｌｌ  ０でない場合には、ＬＡＧトラフィック制御部３１は、ステップＳ４５に戻り、Ａｌｌ  ０である場合には、迂回しないフローとして、フローグループカウンタ２８の対応するエントリに記録する（ステップＳ４７）。
【００５８】
このように、ＬＡＧトラフィック制御部３１は、迂回先のローカルフローベクタ２９を参照することで、出力キュー１２ｃにパケットが格納されていないときに迂回を解除する。したがって、スイッチ１０は、迂回の解除に伴うパケットの到着順序の逆転を防ぐことができる。
【００５９】
上述してきたように、実施例１では、輻輳検出通知部２６は、輻輳状態でＴＣＰセッション要求を受信した場合に、輻輳検出をＬＡＧトラフィック制御部３１に通知する。したがって、ＬＡＧトラフィック制御部３１は、新たなフローが発生したときにフローを迂回することができ、ＣＰＵの負荷を増やさず、他のスイッチ１０でパケットの受信順序が逆転することを防ぐことができる。
【００６０】
また、実施例１では、ＬＡＧトラフィック制御部３１は、ローカルフローベクタ２９を参照して、出力キュー１２ｃにパケットが格納されていないフローグループに属するフローを迂回する。したがって、スイッチ１０は、既に他のスイッチ１０にパケットを送信済みのフローだけを迂回するので、他のスイッチ１０でパケットの受信順序が逆転することを防ぐことができる。
【００６１】
また、実施例１では、ＬＡＧトラフィック制御部３１は、ローカルフローベクタ２９を参照して、出力キュー１２ｃにパケットが格納されていないときに迂回を解除する。したがって、スイッチ１０は、既に他のスイッチ１０にパケットを送信済みのときだけ迂回を解除するので、他のスイッチ１０でパケットの受信順序が逆転することを防ぐことができる。
【００６２】
また、実施例１では、輻輳検出通知部２６が、キュー長カウンタ１２ｄの値が輻輳しきい値２６ａを超えると、輻輳を検知してＬＡＧトラフィック制御部３１に通知する。したがって、スイッチ１０は、輻輳を確実に検知することができる。
【００６３】
また、実施例１では、フローグループカウンタ２８の各group  counterが０であるか否かは、ローカルフローベクタ２９に反映される。したがって、スイッチ１０は、ローカルフローベクタ２９を用いて出力キュー１２ｃの状態を確認することができる。
【００６４】
また、実施例１では、フローグループ毎に、出力キュー１２ｃにパケットが格納されているかを確認する。フローグループカウンタは、出力キュー１２ｃの数とフローグループカウンタ２８のエントリの数の関係を選択することにより、所望のハードウェア規模に抑えることができる。したがって、スイッチ１０は、フローグループ毎に迂回の可否を判断することができ、フロー毎に迂回の可否を判断する場合と比較して、スイッチ１０のハードウェア量を減らすことができる。
【実施例２】
【００６５】
実施例１ではＬＡＧの場合について説明したが、実施例２ではＭＬＡＧの場合について説明する。ここで、ＭＬＡＧとは、複数の装置により実現されるＬＡＧである。図１２は、ＭＬＡＧを説明するための図である。図１２に示すように、実施例２に係る情報処理システム３は、S#0〜S#7で表される８台の情報処理装置２と、Leaf#0〜Leaf#3及びSpine#0〜Spine#1で表される６台のスイッチ４０とを有する。ここで、リーフ（Leaf）は、情報処理装置２に直接接続するスイッチ４０であり、スパイン（Spine）はLeaf以外のスイッチ４０である。スイッチ４０は、情報処理装置間の通信を中継する装置である。
【００６６】
各リーフは、スパインと接続するための２つのポートUP#0及びUP#1を有する。UP#0は、Spine#0と接続し、UP#1は、Spine#1と接続する。各スパインは、リーフと接続するための４つのポートDP#0〜DP#3を有する。DP#0はLeaf#0と接続し、DP#1はLeaf#1と接続し、DP#2はLeaf#2と接続し、DP#3はLeaf#3と接続する。
【００６７】
各リーフは、Spine#0を経由して他のリーフと通信する経路と、Spine#1を経由して他のリーフと通信する経路を有し、ＭＬＡＧを構成する。例えば、S#6からS#0宛のパケットは、Leaf#3のUP#0とUP#1のいずれかから送出される。Speine#0-Leaf#0間のリンクがダウンすると、UP#0から送出されたパケットはSpine#0→Spine#1→DP#0経由でLeaf#0に届く。このように、リーフから見てＭＬＡＧを実現するSpine#0及びSpine#1は、１つのドメインを構成する。
【００６８】
なお、ＩＳＬを用いたスパイン間通信の帯域は、スパイン−リーフ間の通信の帯域と比較すると狭い。また、図１２では、説明の便宜上、２つのスパインでドメインを構成する場合を示したが、より多くのスパインでドメインを構成してもよい。
【００６９】
次に、実施例２に係るスイッチ４０による経路変更について説明する。図１３は、実施例２に係るスイッチ４０による経路変更を説明するための図である。図１３に示すように、実施例２に係る情報処理システム３は、同一ドメインに属するSpine#0とSpine#1との間で、ＦＤＢだけでなく輻輳情報も共有する。そして、Spine#0は、リーフへのいずれかの経路で輻輳状態を検出すると、Spine#1の経路が輻輳していないことを確認してＩＳＬを経由する迂回路を使用する。例えば、Spine#0は、DP#0の輻輳状態を検知すると、Spine#1のDP#0が輻輳していないことを確認してSpine#1のDP#0を迂回路として使用する。
【００７０】
また、Spine#0は、DP#0のキュー情報を基に迂回路を使用するフローを選択し、選択したフローをSpine#1経由で迂回する。その後、Spine#0は、DP#0の輻輳状態が解除されると、Spine#1のDP#0の出力キュー１２ｃの情報を確認し、出力キュー１２ｃに迂回したフローのパケットが格納されていないときに迂回しているフローの経路を元に戻す。
【００７１】
このように、Spine#0は、Spine#1と輻輳情報を共有し、Spine#1の経路が輻輳していないことを確認して迂回路を使用することによって、効率の良い経路変更を行うことができる。
【００７２】
次に、実施例２に係るスイッチ４０の構成について説明する。図１４は、実施例２に係るスイッチ４０の構成を示す図である。なお、ここでは説明の便宜上、図２に示した各部と同様の役割を果たす機能部については同一符号を付すこととしてその詳細な説明を省略する。
【００７３】
図１４に示すように、スイッチ４０は、図２と比較してスイッチングモジュール２０の代わりにスイッチングモジュール５０を有する。スイッチングモジュール５０は、フローグループカウンタ２８の代わりにフローグループカウンタ５８を有する。フローグループカウンタ５８は、フローグループカウンタ２８と異なり、迂回先を記憶しない。その理由は、実施例２では、迂回元と迂回先でスパインは異なるが送信ポート１２ｂの番号は同じであるためである。
【００７４】
ＣＰＵ１３は、プログラムを実行することにより、ＬＡＧトラフィック制御部４１と制御メッセージ送受信部４２の機能を実現する。制御メッセージ送受信部４２は、他のスパインと制御メッセージを用いて輻輳情報を送受信し、受信した輻輳情報をメモリ１４にリモート輻輳ベクタ４３及びリモートフローベクタ４４として格納する。ここで、リモートとは、他のスイッチ４０を表す。これに対して、ローカルは、自スイッチ４０を表す。
【００７５】
図１５は、スパイン間の制御メッセージを示す図である。図１５に示すように、制御メッセージには、Ｄｓｔ  ＭＡＣと、Ｓｒｃ  ＭＡＣと、ＣＶ（Congestion  Vector）と、ＦＶ（Flow  Vector）とが含まれる。Ｄｓｔ  ＭＡＣは、ＰＤＵ（Protocol  Data  Unit）のリザーブＭＡＣアドレスであり、０１：８０：Ｃ２：００：００：０ｆである。Ｓｒｃ  ＭＡＣは、制御メッセージを送信するスイッチ４０のＭＡＣアドレスである。ＣＶは、３２個の送信ポート１２ｂのローカル輻輳ベクタ２７である。ＦＶは、３２個の送信ポート１２ｂの２５６ビットのローカルフローベクタ２９である。
【００７６】
輻輳状態の共有のために使用される情報量は、ＣＶについては、１ビット（輻輳状態）×３２（ポート）＝３２ビット＝４バイトであり、ＦＶについては、１ビット（空状態）×２５６（フローグループ）×３２（ポート）＝８Ｋビット＝１Ｋバイトである。したがって、例えば１０Ｇ（ギガ）のリンクでの帯域使用率は、メッセージ間隔を１００μｓとすると、（１Ｋバイト×８ビット／１００μｓ）／１０Ｇｂｐｓ＝０．００８であるので、約０．８％にすぎない。
【００７７】
ＬＡＧトラフィック制御部４１は、ＬＡＧトラフィック制御部３１と同様の機能を有するが、迂回路の使用可否を判断する場合に、ローカル輻輳ベクタ２７の代わりにリモート輻輳ベクタ４３を用いる。図１６は、迂回路の使用可否判断を説明するための図である。図５と比較すると、図１６では、リモート輻輳ベクタ４３とＣＶマスクベクタとの間でビット毎のＡＮＤがとられている。
【００７８】
また、ＬＡＧトラフィック制御部４１は、迂回先のポート番号をフローグループカウンタ５８に記録しない。図１７は、迂回するフローの記録を説明するための図である。図１７に示すように、ＬＡＧトラフィック制御部４１は、迂回するフローグループを選択すると、フローグループカウンタ５８の対応するエントリの迂回を示すビットを１にするが、迂回先のポート番号は記録しない。
【００７９】
また、ＬＡＧトラフィック制御部４１は、輻輳状態が解除された場合に、ローカルフローベクタ２９の代わりにリモートフローベクタ４４を用いて迂回先の出力キュー１２ｃの空きを確認した後、迂回を解除する。
【００８０】
次に、制御メッセージ送受信部４２による制御メッセージ送受信処理のフローについて説明する。図１８は、制御メッセージの送信処理のフローを示すフローチャートであり、図１９は、制御メッセージの受信処理のフローを示すフローチャートである。
【００８１】
図１８に示すように、制御メッセージ送受信部４２は、所定時間が経過したか否かを判定し（ステップＳ１０１）、経過していない場合には、所定時間が経過するのを待つ。一方、所定時間が経過した場合には、制御メッセージ送受信部４２は、ローカル輻輳ベクタ２７及びローカルフローベクタ２９の値を輻輳情報として取得し（ステップＳ１０２〜ステップＳ１０３）、輻輳情報を含む制御メッセージを送信する（ステップＳ１０４）。
【００８２】
また、制御メッセージ送受信部４２は、図１９に示すように、輻輳情報を含む制御メッセージを受信したか否かを判定し（ステップＳ１１１）、受信していない場合には、輻輳情報を含む制御メッセージの受信を待つ。
【００８３】
一方、輻輳情報を含む制御メッセージを受信した場合には、制御メッセージ送受信部４２は、リモート輻輳ベクタ４３及びリモートフローベクタ４４の値をメモリ１４に格納する（ステップＳ１１２〜ステップＳ１１３）。
【００８４】
このように、制御メッセージ送受信部４２が輻輳情報を含む制御メッセージを送受信することによって、スパインは他のスパインと輻輳情報を共有することができる。
【００８５】
次に、実施例２に係るＬＡＧトラフィック制御部４１による迂回フロー選択の処理のフローについて説明する。図２０は、実施例２に係るＬＡＧトラフィック制御部４１による迂回フロー選択の処理のフローを示すフローチャートである。図２０に示すように、ＬＡＧトラフィック制御部４１は、輻輳検出通知部２６から輻輳検出通知を受信したか否かを判定する（ステップＳ１４１）。受信していない場合には、ＬＡＧトラフィック制御部４１は、輻輳検出通知の受信を待つ。
【００８６】
一方、受信した場合には、ＬＡＧトラフィック制御部４１は、ＣＶマスクベクタのビットの中でローカル輻輳ポートに対応するビットを１に設定する（ステップＳ１４２）。そして、ＬＡＧトラフィック制御部４１は、ＣＶマスクベクタとリモート輻輳ベクタ４３とのビット毎のＡＮＤをとり（ステップＳ１４３）、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ１４４）。Ａｌｌ  ０でない場合には、ＬＡＧトラフィック制御部４１は、ステップＳ１４１に戻って次の輻輳検出通知の受信を待つ。
【００８７】
一方、Ａｌｌ  ０である場合には、ＬＡＧトラフィック制御部４１は、ＦＶマスクベクタのビットの中で迂回の対象となる対象フローの属するフローグループに対応するビットを１に設定する（ステップＳ１４５）。そして、ＬＡＧトラフィック制御部４１は、ＦＶマスクベクタと迂回元送信ポート１２ｂのローカルフローベクタ２９とでビット毎のＡＮＤをとり（ステップＳ１４６）、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ１４７）。
【００８８】
Ａｌｌ  ０である場合には、ＬＡＧトラフィック制御部４１は、対象フローを迂回するフローとして、フローグループカウンタ５８の対応するエントリに記録し（ステップＳ１４８）、ステップＳ１４１に戻る。一方、演算結果がＡｌｌ  ０でない場合には、ＬＡＧトラフィック制御部４１は、所定時間ウエイトし（ステップＳ１４９）、所定回数に到達しているか否かを判定する（ステップＳ１５０）。
【００８９】
所定回数に到達していない場合には、ＬＡＧトラフィック制御部４１は、ステップＳ１４６に戻って、再度、ＦＶマスクベクタと迂回元送信ポート１２ｂのローカルフローベクタ２９とでビット毎のＡＮＤをとる。一方、所定回数に到達した場合には、ＬＡＧトラフィック制御部４１は、ステップＳ１４１に戻る。
【００９０】
このように、ＬＡＧトラフィック制御部４１は、リモート輻輳ベクタ４３を参照することで、迂回先の輻輳状態を判定することができる。
【００９１】
上述してきたように、実施例２では、制御メッセージ送受信部４２が輻輳情報を含む制御メッセージを送受信してリモート輻輳ベクタ４３及びリモートフローベクタ４４としてメモリ１４に書込むことで、スパイン間で輻輳情報を共有する。そして、ＬＡＧトラフィック制御部４１が、リモート輻輳ベクタ４３を用いて迂回先の輻輳状態を確認した後、迂回を行う。また、ＬＡＧトラフィック制御部４１は、ローカルフローベクタ２９を参照して出力キュー１２ｃのパケットが格納されていないフローを迂回するフローとして選択する。したがって、スイッチ４０は、迂回によるパケットの到達順序の逆転を防ぐとともに、効率良く迂回を行うことができる。実施例２では、輻輳状態が解除した場合に迂回路を使用しないようにフローの迂回を解除する。したがって、スイッチは、帯域の狭いＩＳＬを使用することなく、効率の良いパケット中継を行うことができる。
【実施例３】
【００９２】
実施例２ではスパイン間で輻輳情報を共有する場合について説明したが、実施例３ではリーフもスパインの輻輳情報を共有する場合について説明する。図２１は、実施例３に係るスイッチによる経路変更を説明するための図である。なお、図２１では、実施例３に係るスイッチをスイッチ６０と表す。
【００９３】
図２１に示すように、Spine#0及びSpine#1は、Leaf#0〜Leaf#3とも輻輳情報を共有する。そして、各リーフは、Spine#0の経路で輻輳状態を検知したら、リーフの他のポートとSpine#1の経路が輻輳していないことを確認して経路を変更する。
【００９４】
例えば、Leaf#3は、Spine#0の経路で輻輳状態を検知したら、UP#1とSpine#1のDP#0とが輻輳していないことを確認して経路を変更する。そして、Leaf#3は、自身のキュー情報を基に、経路を変更するフローを選択して、フローを迂回する。その後、Spine#0の輻輳状態が解除されると、Leaf#3は、迂回路で使用している自身及びSpine#1のキュー情報を確認し、迂回しているフローの経路を元に戻す。
【００９５】
図２２Ａ及び図２２Ｂは、実施例３に係るＬＡＧトラフィック制御部による迂回フロー選択の処理のフローを示すフローチャートである。ここで、実施例３に係るＬＡＧトラフィック制御部は、リーフが有するＬＡＧトラフィック制御部である。図２２Ａに示すように、ＬＡＧトラフィック制御部は、輻輳検出通知を受信したか否かを判定する（ステップＳ２４１）。受信していない場合には、ＬＡＧトラフィック制御部は、輻輳検出通知の受信を待つ。
【００９６】
一方、受信した場合には、ＬＡＧトラフィック制御部は、迂回路の候補となる他の送信ポート１２ｂがあるか否かを判定する（ステップＳ２４２）。迂回路の候補となる他の送信ポート１２ｂがない場合には、ＬＡＧトラフィック制御部は、ステップＳ２４１に戻って次の輻輳検出通知の受信を待つ。
【００９７】
一方、迂回路の候補となる他の送信ポート１２ｂがある場合には、ＬＡＧトラフィック制御部は、ＣＶマスクベクタのビットの中でスパインの輻輳ポートに対応するビットを１に設定する（ステップＳ２４３）。そして、ＬＡＧトラフィック制御部は、ＣＶマスクベクタと他のスパインのリモート輻輳ベクタ４３とのビット毎のＡＮＤをとり（ステップＳ２４４）、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ２４５）。Ａｌｌ  ０でない場合には、ＬＡＧトラフィック制御部は、ステップＳ２４１に戻って次の輻輳検出通知の受信を待つ。
【００９８】
一方、Ａｌｌ  ０である場合には、ＬＡＧトラフィック制御部は、迂回路のＣＶマスクベクタの該当ビットを１に設定する（ステップＳ２４６）。そして、ＬＡＧトラフィック制御部は、ＣＶマスクベクタと迂回路のローカル輻輳ベクタ２７とでビット毎のＡＮＤをとり（ステップＳ２４７）、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ２４８）。
【００９９】
Ａｌｌ  ０でない場合には、ＬＡＧトラフィック制御部は、所定時間ウエイトし（ステップＳ２４９）、所定回数に到達しているか否かを判定する（ステップＳ２５０）。所定回数に到達していない場合には、ＬＡＧトラフィック制御部は、ステップＳ２４７に戻って、再度、ＣＶマスクベクタと迂回路のローカル輻輳ベクタ２７とでビット毎のＡＮＤをとる。一方、所定回数に到達した場合には、ＬＡＧトラフィック制御部は、ステップＳ２４１に戻る。
【０１００】
一方、ステップＳ２４８において、演算結果がＡｌｌ  ０である場合には、図２２Ｂに示すように、ＬＡＧトラフィック制御部は、ＦＶマスクベクタのビットの中で迂回の対象となる対象フローの属するフローグループに対応するビットを１に設定する（ステップＳ２５１）。そして、ＬＡＧトラフィック制御部は、ＦＶマスクベクタと迂回元送信ポート１２ｂのローカルフローベクタ２９とでビット毎のＡＮＤをとり（ステップＳ２５２）、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ２５３）。
【０１０１】
Ａｌｌ  ０である場合には、ＬＡＧトラフィック制御部は、対象フローを迂回するフローとして、フローグループカウンタ５８の対応するエントリに記録し（ステップＳ２５４）、ステップＳ２４１に戻る。一方、演算結果がＡｌｌ  ０でない場合には、ＬＡＧトラフィック制御部は、所定時間ウエイトし（ステップＳ２５５）、所定回数に到達しているか否かを判定する（ステップＳ２５６）。
【０１０２】
所定回数に到達していない場合には、ＬＡＧトラフィック制御部は、ステップＳ２５２に戻って、再度、ＦＶマスクベクタと迂回元送信ポート１２ｂのローカルフローベクタ２９とでビット毎のＡＮＤをとる。一方、所定回数に到達した場合には、ＬＡＧトラフィック制御部は、ステップＳ２４１に戻る。
【０１０３】
図２３は、実施例３に係るＬＡＧトラフィック制御部によるフロー迂回解除の処理のフローを示すフローチャートである。図２３に示すように、ＬＡＧトラフィック制御部は、輻輳解除通知を受信したか否かを判定する（ステップＳ２６１）。受信していない場合には、ＬＡＧトラフィック制御部は、輻輳解除通知の受信を待つ。
【０１０４】
一方、受信した場合には、ＬＡＧトラフィック制御部は、輻輳が解除されたスパインのポートに対応する送信ポート１２ｂのフローグループカウンタ５８を参照し、迂回フローを検索する（ステップＳ２６２）。そして、ＬＡＧトラフィック制御部は、迂回フローがあるか否かを判定する（ステップＳ２６３）。迂回フローがない場合には、ＬＡＧトラフィック制御部は、処理を終了する。
【０１０５】
一方、迂回フローがある場合には、ＬＡＧトラフィック制御部は、ＦＶマスクベクタの該当ビットを１に設定し（ステップＳ２６４）、ＦＶマスクベクタとスパインの迂回先のリモートフローベクタ４４とのビット毎のＡＮＤをとる（ステップＳ２６５）。そして、ＬＡＧトラフィック制御部は、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ２６６）。
【０１０６】
ＬＡＧトラフィック制御部は、Ａｌｌ  ０でない場合には、ステップＳ２６５に戻り、Ａｌｌ  ０である場合には、ＦＶマスクベクタと自身の迂回先のローカルフローベクタ２９とのビット毎のＡＮＤをとる（ステップＳ２６７）。そして、ＬＡＧトラフィック制御部は、演算結果がＡｌｌ  ０であるか否かを判定する（ステップＳ２６８）。
【０１０７】
ＬＡＧトラフィック制御部は、Ａｌｌ  ０でない場合には、ステップＳ２６７に戻り、Ａｌｌ  ０である場合には、迂回しないフローとして、フローグループカウンタ５８の対応するエントリに記録する（ステップＳ２６９）。
【０１０８】
上述してきたように、実施例３では、スパインの輻輳情報をリーフが共有するので、スパインで輻輳が発生するとリーフが迂回路に変更する。したがって、スイッチ６０は、帯域の狭いＩＳＬを使用することなく、効率の良い迂回を行うことができる。
【符号の説明】
【０１０９】
１，３    情報処理システム
２    情報処理装置
１０，４０，６０，９０    スイッチ
１０ａ，９０ａ    物理リンク
１１ａ，１１ｂ    受信ポート
１２ａ，１２ｂ    送信ポート
１２ｃ    出力キュー
１２ｄ    キュー長カウンタ
１３    ＣＰＵ
１４    メモリ
２０，５０，６０    スイッチングモジュール
２１    パケット受信部
２２    ＦＤＢ記憶部
２３    ＦＤＢ制御部
２４    ハッシュ計算部
２５    パケット振り分け部
２６    輻輳検出通知部
２６ａ    輻輳しきい値
２６ｂ    比較部
２７    ローカル輻輳ベクタ
２８，５８    フローグループカウンタ
２９    ローカルフローベクタ
３１，４１    ＬＡＧトラフィック制御部
４２    制御メッセージ送受信部
４３    リモート輻輳ベクタ
４４    リモートフローベクタ
【図１】
0006511875.tif 000002
【図２】
0006511875.tif 000003
【図３】
0006511875.tif 000004
【図４】
0006511875.tif 000005
【図５】
0006511875.tif 000006
【図６】
0006511875.tif 000007
【図７】
0006511875.tif 000008
【図８】
0006511875.tif 000009
【図９】
0006511875.tif 000010
【図１０】
0006511875.tif 000011
【図１１】
0006511875.tif 000012
【図１２】
0006511875.tif 000013
【図１３】
0006511875.tif 000014
【図１４】
0006511875.tif 000015
【図１５】
0006511875.tif 000016
【図１６】
0006511875.tif 000017
【図１７】
0006511875.tif 000018
【図１８】
0006511875.tif 000019
【図１９】
0006511875.tif 000020
【図２０】
0006511875.tif 000021
【図２１】
0006511875.tif 000022
【図２２Ａ】
0006511875.tif 000023
【図２２Ｂ】
0006511875.tif 000024
【図２３】
0006511875.tif 000025
【図２４】
0006511875.tif 000026