(57)【特許請求の範囲】
【請求項１】
コンピュータに、
複数のスイッチを収容するループ構造を含むネットワークを介して通信を行う通信装置間に設定した通信量から求まる前記スイッチ間の各リンクの通信量に基づいて、各スイッチに搭載された入力ポートと該入力ポートに対向する出力ポートとの組合せで定義されるターン毎に各ターンの通信量をそれぞれ計算する計算手順と、
前記計算手順により計算された各ターンの通信量に基づいて、パケットの転送に使用しない禁止ターンを決定する決定手順と
を実行させることを特徴とする禁止ターン決定プログラム。
【請求項２】
前記決定手順は、Ｕｐ／ｄｏｗｎ法を用いて前記複数のスイッチのそれぞれを頂点としたときの仮禁止ターンをそれぞれ決定し、各仮禁止ターンの通信量の合計値をそれぞれ計算して、各仮禁止ターンの中で該合計値が最小となるときの仮禁止ターンを前記禁止ターンに決定することを特徴とする請求項１に記載の禁止ターン決定プログラム。
【請求項３】
前記決定手順は、ＴＰ法を用いて禁止ターンを決定する場合に、前記スイッチごとに該スイッチを経由して形成されるターンの通信量の合計値をそれぞれ計算し、該合計値が最小となるスイッチを順に選択することを特徴とする請求項１に記載の禁止ターン決定プログラム。
【請求項４】
コンピュータに、
複数のスイッチと該スイッチ間を接続するリンクとを含むループ構造を含むネットワークのモデルであるネットワークグラフを生成し、該ネットワークグラフ上に該ネットワークを介して通信を行う通信装置間の通信経路を設定し、該通信経路上のスイッチに搭載された入力ポートと該入力ポートに対向する出力ポートとの組合せで定義されるターンを一つずつ順に追加し、追加されたターンによりループが形成されたときの当該ターンをパケットの転送に使用しない禁止ターンに決定する決定手順を実行させ、
前記コンピュータに、
前記ネットワークを介して通信を行う通信装置間に設定した通信量から求まる前記スイッチ間の各リンクの通信量に基づいて前記ターン毎に各ターンの通信量をそれぞれ計算する計算手順をさらに実行させ、
前記決定手順は、前記計算手順により計算された各ターンの通信量のうち通信量の高いターンから順に追加することを特徴とする禁止ターン決定プログラム。
【請求項５】
前記コンピュータに、
前記決定手順により前記禁止ターンが決定された場合に、所定の条件に従って、該禁止ターンを除外した通信経路を再設定するか否かを判定する判定手順をさらに実行させ、
前記計算手順は、前記判定手順により前記通信経路の再設定を行うものと判定された場合には、該禁止ターンを除外した通信経路を再設定して前記ターンの通信量を再計算し、
前記決定手順は、前記計算手順により再計算された各ターンの通信量のうち通信量の高いターンから順に追加することを特徴とする請求項４に記載の禁止ターン決定プログラム。
【請求項６】
複数のスイッチを収容するループ構造を含むネットワークを介して通信を行う通信装置間に設定した通信量から求まる前記スイッチ間の各リンクの通信量に基づいて、各スイッチに搭載された入力ポートと該入力ポートに対向する出力ポートとの組合せで定義されるターン毎に各ターンの通信量をそれぞれ計算する計算部と、
前記計算部により計算された各ターンの通信量に基づいて、パケットの転送に使用しない禁止ターンを決定する決定部と
を有することを特徴とする禁止ターン決定装置。
【請求項７】
複数のスイッチと該スイッチ間を接続するリンクとを含むループ構造を含むネットワークのモデルであるネットワークグラフを生成し、該ネットワークグラフ上に該ネットワークを介して通信を行う通信装置間の通信経路を設定し、該通信経路上のスイッチに搭載された入力ポートと該入力ポートに対向する出力ポートとの組合せで定義されるターンを一つずつ順に追加し、追加された各ターンによりループが形成されたときの追加ターンをパケットの転送に使用しない禁止ターンに決定する決定部と、
前記ネットワークを介して通信を行う通信装置間に設定した通信量から求まる前記スイッチ間の各リンクの通信量に基づいて前記ターン毎に各ターンの通信量をそれぞれ計算する計算部と
を有し、
前記決定部は、前記計算部により計算された各ターンの通信量のうち通信量の高いターンから順に追加することを特徴とする禁止ターン決定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、禁止ターン決定プログラムおよび禁止ターン決定装置に関する。
【背景技術】
【０００２】
ループ構造を含むネットワークでは、パケットを循環させることができなくなる、いわゆるデットロックが発生する場合がある。デットロックは、ネットワーク内に収容されるスイッチに搭載されたバッファの依存性を原因として引き起こされる。
【０００３】
図４１は、デットロック発生のメカニズムを説明するための図である。図４１に示すＳ１、Ｓ２、Ｓ３、Ｓ４はスイッチに該当する。図４１に示すＢ１、Ｂ２、Ｂ３、Ｂ４はバッファに該当する。図４１に示すＰａ１、Ｐａ２、Ｐａ３、Ｐａ４はパケットに該当する。例えば、図４１に示すネットワークにおいて、各スイッチから、それぞれ対角線上のスイッチへ時計回りの経路でパケットを転送する場合を考える。この場合、例えば、各スイッチから同時にパケットが送信されると、それぞれのスイッチの時計回り方向に１つ隣にあるスイッチのバッファにパケットが格納される。例えば、スイッチＳ１からスイッチＳ３をあて先として送出されるパケットＰａ２は、スイッチＳ２のバッファＢ２に格納される。また、スイッチＳ２からスイッチＳ４をあて先として送出されるパケットＰａ３は、スイッチＳ３のバッファＢ３に格納される。また、スイッチＳ３からスイッチＳ１をあて先として送出されるパケットＰａ４は、スイッチＳ４のバッファＢ４に格納される。また、スイッチＳ４からスイッチＳ２をあて先として送出されるパケットＰａ１は、スイッチＳ１のバッファＢ１に格納される。
【０００４】
ここで、スイッチＳ３のバッファＢ３にはスイッチＳ２からスイッチＳ４をあて先として送出されるパケットＰａ３が格納されてしまっている。スイッチＳ２がスイッチＳ３にパケットＰａ２を転送するためには、スイッチＳ３のバッファＢ３が空きの状態である必要がある。このため、スイッチＳ２は、スイッチＳ３をあて先としてスイッチＳ１から送出されるパケットＰａ２をスイッチＳ３に転送することができない。同様にして、スイッチＳ１、スイッチＳ３、スイッチＳ４にもパケットを転送できないという現象が起こり、図４１に示すネットワークがパケット転送不能の状態、すなわちデットロックに陥ってしまう。このように、パケット転送先のスイッチに搭載されているバッファが空いているかどうかに依存してパケットの転送の可否が決定されることをバッファの依存性と称する。そして、図４１に示すように、バッファの依存性を原因として、ネットワークがパケット転送不能の状態に陥ってしまうことをバッファの依存性循環という。
【０００５】
また、上述してきたバッファ依存性をターンという概念で表現することもできる。ターンとは、入力パケットをあて先へ転送するスイッチに搭載されているポートの組合せで定義される。例えば、パケットを入力した入力ポートと、入力パケットを転送先へ出力する出力ポートとの組合せで定義される。例えば、図４１に示すスイッチＳ２の入力ポートと出力ポートとの組合せであるターンを「Ｓ１→Ｓ２→Ｓ３」と定義する。スイッチＳ２がスイッチＳ３にパケットＰａ２を転送するためには、スイッチＳ３のバッファＢ３が空いている必要があるというバッファ依存性と、「Ｓ１→Ｓ２→Ｓ３」とは１対１の対応関係にあるといえる。
【０００６】
図４２は、バッファの依存性循環とターンのループとの対応関係を示す図である。図４２に示す４２−１はバッファの依存性循環を表す。図４２の４２−１に示す（１）は、スイッチＳ２がパケットを転送するためにはバッファＢ３が空いている必要があるというバッファ依存性を表す。図４２の４２−１に示す（２）は、スイッチＳ３がパケットを転送するためにはバッファＢ４が空いている必要があるというバッファ依存性を表す。図４２の４２−１に示す（３）は、スイッチＳ４がパケットを転送するためにはバッファＢ１が空いている必要があるというバッファ依存性を表す。図４２の４２−１に示す（４）は、スイッチＳ１がパケットを転送するためにはバッファＢ２が空いている必要があるというバッファ依存性を表す。そして、図４２の４２−１に示すように、バッファの依存性（１）〜（４）がネットワーク内を循環している。
【０００７】
図４２に示す４２−２はターンのループを表す。図４２の４２−２に示す（１）は、スイッチＳ１から入力したパケットをスイッチＳ３へ出力するスイッチＳ２が形成するターンを表す。図４２の４２−２に示す（２）は、スイッチＳ２から入力したパケットをスイッチＳ４へ出力するスイッチ３が形成するターンを表す。図４２の４２−２に示す（３）は、スイッチＳ３から入力したパケットをスイッチＳ１に出力するスイッチＳ４が形成するターンを表す。図４２の４２−２に示す（４）は、スイッチＳ４から入力したパケットをスイッチＳ２に出力するスイッチＳ１が形成するターンを表す。そして、図４２の４２−２に示すように、各ターン（１）〜（４）をつなぎ合わせればネットワーク内を時計回りに一周するループを形成している。
【０００８】
よって、バッファ依存性とターンとは１対１の対応関係にあるといえるので、図４２の４２−１に示す（１）と図４２の４２−２に示す（１）とは１対１の対応関係にある。さらに、図４２の４２−１に示す（２）と図４２の４２−２に示す（２）とは１対１の対応関係にある。同様に、図４２の４２−１に示す（３）と図４２の４２−２に示す（３）とは１対１の対応関係にあり、図４２の４２−１に示す（４）と図４２の４２−２に示す（４）とは１対１の対応関係にある。よって、図４２の４２−１に示すバッファの依存性循環と、図４２の４２−２に示すターンのループとは等価の概念であるといえる。
【０００９】
上述したデットロックは、バッファの依存性循環、言い換えればターンのループを原因として発生する。そこで、デットロックを回避するために、パケットの転送方向に制限を加える技術が存在する。例えば、「Ｕｐ／ｄｏｗｎ法」や「ＴＰ（Ｔｕｒｎ  Ｐｒｏｈｉｂｉｔｉｏｎ）法」は、パケットの転送を制限する禁止ターンを決定し、禁止ターンが除かれたルーティングでパケットの転送を行うことにより、デットロックを回避する。
【００１０】
図４３を用いて、Ｕｐ／ｄｏｗｎ法による禁止ターンの決定について説明する。図４３は、Ｕｐ／ｄｏｗｎ法による禁止ターンの決定の流れを示す図である。図４３に示すように、Ｕｐ／ｄｏｗｎ法は、まず、ネットワークに収容される各スイッチと、各スイッチを接続するリンクとを含むネットワークグラフ上で頂点となるスイッチを決定する（ステップＳ１０１）。スイッチの決定方法としては、最小ＩＤが割り当てられたスイッチを選択する方法やランダムにスイッチを選択する方法、あるいはエンドノードからの距離が均等なスイッチを選択する方法などがある。続いて、図４３に示すように、Ｕｐ／ｄｏｗｎ法は、ポップ数を算出し（ステップＳ１０２）、Ｕｐ方向を決定する（ステップＳ１０３）。そして、図４３に示すように、Ｕｐ／ｄｏｗｎ法は、禁止ターンを決定する（ステップＳ１０４）。例えば、Ｕｐ／ｄｏｗｎ法は、入力パケットの転送方向がｄｏｗｎ方向からＵｐ方向へ向かう場合には、この転送方向を制限するように、この転送方向に対応する該当ターンを禁止ターンに決定する。
【００１１】
図４４は、Ｕｐ／ｄｏｗｎ法による禁止ターンの決定動作を説明するための図である。上述した図４３に示すステップＳ１０２では、次のようにして各スイッチのポップ数を算出する。すなわち、図４４に示すように、ステップＳ１０２では、ステップＳ１０１により頂点に決定されたスイッチのポップ数を「０」とする。さらに、図４４に示すように、ステップＳ１０２では、ポップ数が「０」である頂点のスイッチに接続されたスイッチのポップ数を「１」とする。さらに、図４４に示すように、ステップＳ１０２では、ポップ数が「１」であるスイッチに接続されたスイッチのポップ数を「２」とする。また、ステップＳ１０２では、ポップ数が「２」であるスイッチに接続されたスイッチのポップ数を「３」とする。また、ステップＳ１０３では、ポップ数の大きいスイッチからポップ数の小さいスイッチへ向かう方向をＵｐ方向として決定する。反対に、Ｕｐ方向と逆向きの方向をｄｏｗｎ方向とする。なお、同一のポップ数を有するスイッチではいずれかの方向をＵｐ方向とし、逆向きをｄｏｗｎ方向とする。そして、図４４に示すように、ｄｏｗｎ方向からＵｐ方向への転送方向をなすターンＴ１、Ｔ２、Ｔ３、Ｔ４を禁止ターンに決定する。なお、ターンＴ１、Ｔ２、Ｔ３、Ｔ４の矢印が示す両転送方向が禁止ターンとなる。
【００１２】
図４５を用いて、ＴＰ法による禁止ターンの決定について説明する。図４５は、ＴＰ法による禁止ターンの決定の流れを示す図である。図４５に示すように、ＴＰ法は、ネットワークグラフ上で次数、つまり接続リンク数が最小のスイッチを選択し（ステップＳ２０１）、禁止ターンを決定した後（ステップＳ２０２）、ステップＳ２０１で選択したスイッチを削除する（ステップＳ２０３）。そして、ＴＰ法は、上述したステップＳ２０１に戻り、スイッチ削除後のネットワークグラフ上で接続リンク数が最小のスイッチを選択し、上述してきた動作を行う。ＴＰ法は、ターンを形成するスイッチがなくなるまで図４５に示す動作を繰り返し実行する。
【００１３】
図４６は、ＴＰ法による禁止ターンの決定動作を説明するための図である。図４６の４６−１に示すように、ＴＰ法は、接続リンク数が最小であるスイッチＮ７を選択し、スイッチＮ７により形成されるターンは存在しないので、そのままスイッチＮ７を削除する。続いて、図４６の４６−２に示すように、ＴＰ法は、接続リンク数が最小であるスイッチＮ６を選択し、禁止ターンＴ１を決定した後、スイッチＮ６を削除する。続いて、図４６の４６−３に示すように、ＴＰ法は、接続リンク数が最小であるスイッチＮ３を選択し、スイッチＮ３により形成されるターンは存在しないので、そのままスイッチＮ３を削除する。続いて、図４６の４６−４に示すように、ＴＰ法は、接続リンク数が最小であるスイッチＮ２およびＮ４の中からスイッチＮ２を一つ選択し、禁止ターンＴ２を決定した後、スイッチＮ２を削除する。続いて、図４６の４６−５に示すように、ＴＰ法は、接続リンク数が最小であるスイッチＮ１、Ｎ４およびＮ５の中からスイッチＮ５を一つ選択し、禁止ターンＴ３を決定した後、スイッチＮ５を削除する。続いて、図４６の４６−６に示すように、ＴＰ法は、接続リンク数が最小であるスイッチＮ１およびＮ４の中からスイッチＮ４を一つ選択し、スイッチＮ４により形成されるターンは存在しないので、そのままスイッチＮ４を削除する。以上で、スイッチＮ１だけが残され、ターンを形成するスイッチがないので、ＴＰ法は禁止ターンの決定動作を終了し、ターンＴ１、Ｔ２、Ｔ３を禁止ターンに決定する。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】「Autonet：A  High-speed，Self-Configuring  Local  Area  Network  Using  Point-to-Point  Links」  Michael  D．Schroeder，Andrew  D．Birrell，Michael  Burrows，Hal  Murray，Roger  M．Needham，Thomas  L.  Rodeheffer，Edwin  H．Satterthwaite，Charles  P．Thacker，IEEE  JOURNAL  ON  SELECTED  AREAS  IN  COMMUNICATIONS，VOL．9，NO．8，OCTOBER  1991
【非特許文献２】「Application  of  network  calculus  to  general  topologies  using  turn-prohibition」，David  Starobinski，Mark  Karpovsky，Lev  A．Zakrevski，IEEE／ACM  Transactions  on  Networking（TON）  archive  Volume11，Issue3（June  2003）table  of  contents，Pages：411-421，Year  of  Publication：2003，ISSN：1063-6692
【発明の概要】
【発明が解決しようとする課題】
【００１５】
ところで、上述したパケットの転送方向に制限を加える技術では、禁止ターンを考慮したルーティングを行った場合に、各リンクを経由する通信量が必ずしも効率的に分散されていないという問題があった。
【００１６】
図４７は、ネットワークを形成する各リンクの通信量の一例を示す図である。図４７に示すように、スイッチＳ２を時計回りに経由するターンの通信量が「１０」であるときの当該ターンに対応する各リンクの通信量がそれぞれ「１１」であることを表す。また、図４７に示すように、スイッチＳ３を時計回りに経由するターンの通信量が「１」であるときの当該ターンに対応する各リンクの通信量がそれぞれ「１１」であることを表す。また、図４７に示すように、スイッチＳ４を時計回りに経由するターンの通信量が「１０」であるときの当該ターンに対応する各リンクの通信量がそれぞれ「１１」であることを表す。また、図４７に示すように、スイッチＳ１を時計回りに経由するターンの通信量が「１」であるときの当該ターンに対応する各リンクの通信量がそれぞれ「１１」であることを表す。
【００１７】
図４８は、禁止ターンの違いに応じた各リンクの通信量の比較図である。図４８に示す４８−１は、スイッチＳ３を時計回りに経由するターンＢＴ１を禁止ターンとし、この禁止ターンを反時計回りに迂回させるルーティングを行った場合の各リンクの通信量を表す。言い換えれば、スイッチＳ３を時計回りに経由するターン「Ｓ２→Ｓ３→Ｓ４」を禁止ターンとし、この禁止ターンを反時計回りに迂回させるターン「Ｓ２→Ｓ１→Ｓ４」でルーティングした場合の各リンクの通信量を表す。図４８に示す４８−２は、スイッチＳ２を時計回りに経由するターンＢＴ２を禁止ターンとし、この禁止ターンを反時計回りに迂回させるルーティングを行った場合の各リンクの通信量を表す。言い換えれば、スイッチＳ３を時計回りに経由するターン「Ｓ１→Ｓ２→Ｓ３」を禁止ターンとし、この禁止ターンを反時計回りに迂回させるターン「Ｓ１→Ｓ４→Ｓ３」でルーティングした場合の各リンクの通信量を表す。
【００１８】
図４９は、禁止ターンを迂回させるルーティングを行った後の各リンクの通信量の内訳を示す図である。図４９に示す４９−１は図４８に示す４８−１に対応する。図４９に示す４９−２は図４８に示す４８−２に対応する。図４８の４８−１または図４９の４９−１に示すように、禁止ターンＢＴ１を反時計回りに迂回させるルーティングを行った場合には、各リンクの通信量は「１２」もしくは「１０」となる。図４８の４８−２または図４９の４９−２に示すように、禁止ターンＢＴ２を反時計回りに迂回させるルーティングを行った場合には、各リンクの通信量は「２１」もしくは「１」となる。よって、図４８に示す４８−１の方が、図４８に示す４８−２によりも、禁止ターンを迂回させる別のターンでルーティングした後の各リンクの通信量が分散されていることが分かる。しかしながら、上述したＵｐ／ｄｏｗｎ法やＴＰ法などのように、禁止ターンを決定してパケットの転送方向を制限する技術では、各リンクの通信量が分散されるターンを狙って禁止ターンを決定することができない。このようなことから、パケットの転送方向を制限する技術では、ネットワーク内のデットロックを回避するためのルーティングを行う場合に、通信量を上手く分散できないという問題があった。
【００１９】
１側面では、本発明は、ネットワーク内に収容されるスイッチ間を接続する各リンクの通信量が効率的に分散されたルーティングを得ることが可能な禁止ターン決定プログラムおよび禁止ターン決定装置を提供することを目的とする。
【課題を解決するための手段】
【００２０】
１つの態様では、コンピュータに、通信量計算手順と、禁止ターン決定手順とを実行させる。通信量計算手順は、ループ構造を含むネットワークに収容される複数のスイッチ間を接続する複数のリンクの通信量に基づいてターンの通信量をそれぞれ計算する。ターンは、通信装置間の通信経路上のスイッチに搭載された入力ポートと該入力ポートに対向する出力ポートとの組合せで定義される。禁止ターン決定手順は、通信量計算手順により計算された各ターンの通信量に基づいて、パケットの転送に使用しない禁止ターンを決定する。
【発明の効果】
【００２１】
本発明の１つの態様によれば、ネットワーク内に収容されるスイッチ間を接続する各リンクの通信量が効率的に分散されたルーティングを得ることができる。
【図面の簡単な説明】
【００２２】
【図１】図１は、実施例１に係る禁止ターン決定装置の構成を示す機能ブロック図である。
【図２】図２は、初期経路の決定方法を説明するための事例１を示す図である。
【図３】図３は、初期経路の決定方法を説明するための事例１を示す図である。
【図４】図４は、初期経路の決定方法を説明するための事例１を示す図である。
【図５】図５は、初期経路の決定方法を説明するための事例１を示す図である。
【図６】図６は、初期経路の決定方法を説明するための事例１を示す図である。
【図７】図７は、初期経路の決定方法を説明するための事例２を示す図である。
【図８】図８は、初期経路の決定方法を説明するための事例２を示す図である。
【図９】図９は、初期経路の決定方法を説明するための事例２を示す図である。
【図１０】図１０は、初期経路の決定方法を説明するための事例２を示す図である。
【図１１】図１１は、実施例１に係るＵｐ／ｄｏｗｎ法を応用した禁止ターンの決定方法を説明するための図である。
【図１２】図１２は、実施例１に係るＵｐ／ｄｏｗｎ法を応用した禁止ターンの決定方法を説明するための図である。
【図１３】図１３は、実施例１に係るＴＰ法を応用した禁止ターンの決定方法を説明するための図である。
【図１４】図１４は、実施例１に係る各リンクの通信量を示す図である。
【図１５】図１５は、実施例１に係る各ターンの通信量を示す図である。
【図１６】図１６は、実施例１に係るスイッチＡを頂点とした場合の禁止ターンの通信量を示す図である。
【図１７】図１７は、実施例１に係るスイッチＣを頂点とした場合の禁止ターンの通信量を示す図である。
【図１８】図１８は、実施例１に係るスイッチＧを頂点とした場合の禁止ターンの通信量を示す図である。
【図１９】図１９は、実施例１に係る最終経路の各リンクの通信量を示す図である。
【図２０】図２０は、実施例１に係るスイッチＡを頂点として禁止ターンを決定した場合の通信経路の各リンクの通信量を示す図である。
【図２１】図２１は、実施例１に係るスイッチＣを頂点として禁止ターンを決定した場合の通信経路の各リンクの通信量を示す図である。
【図２２】図２２は、実施例１に係る処理の流れを示す図である。
【図２３】図２３は、実施例１に係るＵｐ／ｄｏｗｎ法を応用した禁止ターン決定処理の流れを示す図である。
【図２４】図２４は、実施例１に係るＴＰ法を応用した禁止ターン決定処理の流れを示す図である。
【図２５】図２５は、Ｕｐ／ｄｏｗｎ法によるトーラスネットワークについての禁止ターン決定例を示す図である。
【図２６】図２６は、ＴＰ法によるトーラスネットワークについての禁止ターン決定例を示す図である。
【図２７】図２７は、実施例２に係る禁止ターン決定装置の構成を示す機能ブロック図である。
【図２８】図２８は、実施例２に係る禁止ターンの決定方法を説明するための図である。
【図２９】図２９は、実施例２に係るパケットの到達性を説明するための図である。
【図３０】図３０は、実施例２に係るパケットの到達性を説明するための図である。
【図３１】図３１は、実施例２に係るパケットの到達性を説明するための図である。
【図３２】図３２は、実施例２に係る禁止ターン決定処理の流れを示す図である。
【図３３】図３３は、実施例２に係る方法による禁止ターンの決定例を示す図である。
【図３４】図３４は、各リンクの通信量の変動係数とスイッチ数との関係を示す図である。
【図３５】図３５は、リンクの最大通信量とスイッチ数との関係を示す図である。
【図３６】図３６は、実施例３に係る禁止ターン決定装置の構成を示す機能ブロック図である。
【図３７】図３７は、実施例３に係る禁止ターン決定処理の流れを示す図である。
【図３８】図３８は、実施例４に係る禁止ターン決定装置の構成を示す機能ブロック図である。
【図３９】図３９は、実施例４に係る禁止ターン決定処理の流れを示す図である。
【図４０】図４０は、禁止ターン決定プログラムを実行するコンピュータの一例を示す図である。
【図４１】図４１は、デットロック発生のメカニズムを説明するための図である。
【図４２】図４２は、バッファの依存性循環とターンのループとの対応関係を示す図である。
【図４３】図４３は、Ｕｐ／ｄｏｗｎ法による禁止ターンの決定の流れを示す図である。
【図４４】図４４は、Ｕｐ／ｄｏｗｎ法による禁止ターンの決定動作を説明するための図である。
【図４５】図４５は、ＴＰ法による禁止ターンの決定の流れを示す図である。
【図４６】図４６は、ＴＰ法による禁止ターンの決定動作を説明するための図である。
【図４７】図４７は、ネットワークを形成する各リンクの通信量の一例を示す図である。
【図４８】図４８は、禁止ターンの違いに応じた各リンクの通信量の比較図である。
【図４９】図４９は、禁止ターンを迂回させるルーティングを行った後の各リンクの通信量の内訳を示す図である。
【発明を実施するための形態】
【００２３】
以下に、図面を参照しつつ、本願の開示する禁止ターン決定プログラムおよび禁止ターン決定装置の一実施形態について詳細に説明する。なお、本願の開示する禁止ターン決定プログラムおよび禁止ターン決定装置の一実施形態として後述する実施例により、本願が開示する技術が限定されるものではない。
【実施例１】
【００２４】
［禁止ターン決定装置の構成（実施例１）］
図１は、実施例１に係る禁止ターン決定装置の構成を示す機能ブロック図である。図１に示すように、禁止ターン決定装置３００は、複数のスイッチ１００を収容するネットワーク１に接続される。禁止ターン決定装置３００は、ネットワーク１内に収容される複数のスイッチ１００間でパケットをやり取りするためのルーティングを決定するに際して、パケットのやり取りを行わない禁止ターンを決定する。なお、複数のサーバ２００は、ネットワーク１に接続され、ネットワーク１を介して相互に通信を行う。
【００２５】
図１に示すように、禁止ターン決定装置３００は、入力部３１０と、出力部３２０と、ネットワークインターフェース３３０と、記憶部３４０と、制御部３５０とを有する。なお、禁止ターン決定装置３００として、通信インターフェースを実装したパーソナルコンピュータやサーバなどを利用できる。
【００２６】
入力部３１０は、ユーザから各種情報の入力を受け付ける。例えば、入力部３１０は、ルーティング決定の処理開始指示の入力をユーザから受け付ける。入力部３１０は、例えば、キーボードやマウス、タッチパッドなどの入力デバイスを有する。
【００２７】
出力部３２０は、各種情報を出力表示する。例えば、出力部３２０は、後述する制御部３５０により導出された最終的なルーティングの内容を出力表示する。出力部３２０は、モニタやディスプレイなどの出力デバイスを有する。なお、入力部３１０が入力デバイスとしてマウスを有する場合には、出力部３２０が出力デバイスとして有するモニタと協働して、ポインティングデバイス機能を実現できる。また、入力部３１０が入力デバイスとしてタッチパッドなどの他の入力デバイスを有する場合にも、マウスの場合と同様にポインティングデバイス機能を実現できる。
【００２８】
ネットワークインターフェース３３０は、複数のスイッチ１００との間でメッセージの送受信を行うためにネットワーク１との接続を行う。
【００２９】
記憶部３４０は、制御部３５０による各種処理に必要なデータおよびプログラムなどを記憶する。例えば、記憶部３４０は、図１に示すように、ネットワーク情報記憶部３４１を有する。ネットワーク情報記憶部３４１は、ネットワーク１内に収容されたスイッチ１００の台数や、ネットワーク１を介して他のサーバ２００と相互に通信を行うために各サーバ２００に予め設定された通信量の情報など、ネットワーク１に関する各種情報を記憶する。
【００３０】
制御部３５０は、所定の制御プログラムや各種の処理手順などを規定したプログラム、所要データを格納するための内部メモリを有し、内部メモリに所定のプロセスを展開することにより種々の処理を実行する。例えば、制御部３５０は、図１に示すように、生成部３５１と、計算部３５２と、決定部３５３と、算出部３５４とを有する。
【００３１】
生成部３５１は、ネットワーク１の構造をモデル化したネットワークグラフを生成する。例えば、生成部３５１は、入力部３１０を介して、禁止ターン決定処理の開始指示の入力が受け付けられると、ネットワーク情報記憶部３４１からネットワーク１に関する各種情報を取得する。そして、生成部３５１は、ネットワーク１に関する各種情報を用いて、複数のスイッチ１００とスイッチ１００間を接続するリンクとを含むネットワーク１の構造がモデル化されたネットワークグラフを生成する。
【００３２】
計算部３５２は、ネットワークを介して相互に通信を行うサーバ２００間に設定された通信系路上の各スイッチ１００に形成されるターンの通信量をそれぞれ計算する。ここで、ターンとは、スイッチ１００に搭載された入力ポートと、この入力ポートに対向する出力ポートとの組合せで定義される。言い換えれば、パケットを入力した入力ポートと入力パケットを転送先へ出力する出力ポートとの組合せで定義される。まず、計算部３５２は、ネットワーク１に関する各種情報をネットワーク情報記憶部３４１から取得する。続いて、計算部３５２は、ネットワーク１を介して相互に通信を行うサーバ２００の組合せ（以下、通信ペアと表記する）ごとに、通信を行うための初期経路を決定する。このとき、計算部３５２は、スイッチ１００間を接続する各リンクの通信量ができるだけ分散するような通信経路を導出し、導出した通信経路を初期経路に決定する。
【００３３】
以下、図２〜図９を用いて、計算部３５２による初期経路の決定方法を説明する。図２〜図６は、初期経路の決定方法を説明するための事例１を示す図である。図７〜図１０は、初期経路の決定方法を説明するための事例２を示す図である。
【００３４】
まず、図２〜図６に示す事例１を用いて、初期経路の決定方法を説明する。図２〜図６に示す「ｓ」、「ａ」〜「ｄ」は、相互に通信を行う通信装置、いわゆるエンドノードに相当する。図２〜図６に示す「Ａ」〜「Ｇ」は、「ｓ」⇔「ａ」、「ｓ」⇔「ｂ」、「ｓ」⇔「ｃ」、「ｓ」⇔「ｄ」との間でやり取りされるパケットを転送するスイッチに相当する。図２に示す２−１、図３に示す３−１、図４に示す４−１、図５に示す５−１、図６に示す６−１は、ネットワークグラフの一例である。
【００３５】
図２は、最短経路選択前の最初の状態に相当する。計算部３５２は、図２の２−１に示すように、まず、スイッチ「Ａ」〜「Ｇ」間を接続するリンクの通信量を「０．０」とする。なお、図２の２−２に示すように、「ｓ」と「ａ」、「ｓ」と「ｂ」、「ｓ」と「ｃ」、「ｓ」と「ｄ」との間で通信を行う通信経路が確定した際には、通信量「１．０」で通信を行うように予め設定されているものとする。
【００３６】
まず、計算部３５２は、「ｓ」と「ａ」とが通信を行う場合の最短経路を決定する。図３の３−２に示すように、計算部３５２は、「ｓ」と「ａ」とが通信を行う場合の最短経路として、（１）Ａ→Ｂ→Ｄ→Ｅ→Ｇ、（２）Ａ→Ｂ→Ｄ→Ｆ→Ｇ、（３）Ａ→Ｃ→Ｄ→Ｅ→Ｇ、（４）Ａ→Ｃ→Ｄ→Ｆ→Ｇを列挙する。ここで、図３の３−２に示すように、「ｓ」⇔「ａ」について列挙した最短経路（１）〜（４）の最大通信量は全て「０．０」となる。よって、計算部３５２は、現時点では、「ｓ」⇔「ａ」について列挙した最短経路（１）〜（４）の最大通信量は同一であるので、列挙した最短経路（１）〜（４）の中から、例えば最短経路（２）を任意に選択する。そして、計算部３５２は、「ｓ」⇔「ａ」の通信量は「１．０」に設定されているので、図４の４−１に示すように、選択した最短経路（２）を形成するリンクに通信量「１．０」をそれぞれ展開する。
【００３７】
続いて、計算部３５２は、図４の４−２に示すように、「ｓ」と「ｂ」とが通信を行う場合の最短経路として、（１）Ａ→Ｂ→Ｄ→Ｅ→Ｇ、（２）Ａ→Ｂ→Ｄ→Ｆ→Ｇ、（３）Ａ→Ｃ→Ｄ→Ｅ→Ｇ、（４）Ａ→Ｃ→Ｄ→Ｆ→Ｇを列挙する。ここで、図４の４−２に示すように、「ｓ」⇔「ｂ」について列挙した最短経路（１）〜（４）の最大通信量は、「１．０」もしくは「０．０」となる。よって、計算部３５２は、最大通信量が最も小さい最短経路（４）を選択する。そして、計算部３５２は、「ｓ」⇔「ａ」の通信量は「１．０」に設定されているので、図５の５−１に示すように、選択した最短経路（４）を形成するリンクに通信量「１．０」をそれぞれ展開する。
【００３８】
続いて、計算部３５２は、図５の５−２に示すように、「ｓ」と「ｃ」とが通信を行う場合の最短経路として、（１）Ａ→Ｂ→Ｄ→Ｅ→Ｇ、（２）Ａ→Ｂ→Ｄ→Ｆ→Ｇ、（３）Ａ→Ｃ→Ｄ→Ｅ→Ｇ、（４）Ａ→Ｃ→Ｄ→Ｆ→Ｇを列挙する。ここで、図５の５−２に示すように、「ｓ」⇔「ｃ」について列挙した最短経路（１）〜（４）の最大通信量は全て「１．０」となる。よって、計算部３５２は、現時点では、「ｓ」⇔「ｃ」について列挙した最短経路（１）〜（４）の最大通信量は同一であるので、列挙した最短経路（１）〜（４）の中から、例えば最短経路（３）を任意に選択する。そして、計算部３５２は、「ｓ」⇔「ｃ」の通信量は「１．０」に設定されているので、図６の６−１に示すように、選択した最短経路（３）を形成するリンクに通信量「１．０」をそれぞれ展開する。
【００３９】
続いて、計算部３５２は、図６の６−２に示すように、「ｓ」と「ｄ」とが通信を行う場合の最短経路として、（１）Ａ→Ｂ→Ｄ→Ｅ→Ｇ、（２）Ａ→Ｂ→Ｄ→Ｆ→Ｇ、（３）Ａ→Ｃ→Ｄ→Ｅ→Ｇ、（４）Ａ→Ｃ→Ｄ→Ｆ→Ｇを列挙する。ここで、図６の６−２に示すように、「ｓ」⇔「ｄ」について列挙した最短経路（１）〜（４）の最大通信量は、「１．０」もしくは「２．０」となる。よって、計算部３５２は、最大通信量が最も小さい最短経路（２）を選択する。そして、計算部３５２は、「ｓ」⇔「ｄ」の通信量は「１．０」に設定されているので、上述した他の最短経路を選択した場合と同様に、選択した最短経路（２）を形成するリンクに通信量「１．０」をそれぞれ展開する。
【００４０】
また、図７〜図１０に示す事例２を用いて、初期経路の決定方法を説明する。図７〜図１０に示す「ｓ」、「ａ」〜「ｃ」は、相互に通信を行う通信装置、いわゆるエンドノードに相当する。図７〜図１０に示す「Ａ」〜「Ｇ」は、「ｓ」⇔「ａ」、「ｓ」⇔「ｂ」、「ｓ」⇔「ｃ」との間でやり取りされるパケットを転送するスイッチに相当する。図７に示す７−１、図８に示す８−１、図９に示す９−１、図１０に示す１０−１は、ネットワークグラフの一例である。
【００４１】
図７は、最短経路選択前の最初の状態に相当する。計算部３５２は、図７の７−１に示すように、まず、スイッチ「Ａ」〜「Ｇ」間を接続するリンクに通信量「０．０」とする。なお、図７の７−２に示すように、「ｓ」と「ａ」、「ｓ」と「ｂ」、「ｓ」と「ｃ」との間で通信を行う通信経路が確定した際には、通信量「１．０」、「１．５」、「１．０」で通信を行うように予め設定されているものとする。
【００４２】
まず、計算部３５２は、「ｓ」と「ａ」とが通信を行う場合の最短経路を決定する。図８の８−２に示すように、計算部３５２は、「ｓ」と「ａ」とが通信を行う場合の最短経路として、（１）Ａ→Ｂ→Ｄ→Ｅ→Ｇ、（２）Ａ→Ｂ→Ｄ→Ｆ→Ｇ、（３）Ａ→Ｃ→Ｄ→Ｅ→Ｇ、（４）Ａ→Ｃ→Ｄ→Ｆ→Ｇを列挙する。ここで、図８の８−２に示すように、「ｓ」⇔「ａ」について列挙した最短経路（１）〜（４）の最大通信量は全て「０．０」となる。よって、計算部３５２は、現時点では、「ｓ」⇔「ａ」について列挙した最短経路（１）〜（４）の最大通信量は同一であるので、列挙した最短経路（１）〜（４）の中から、例えば最短経路（１）を任意に選択する。そして、計算部３５２は、「ｓ」⇔「ａ」の通信量は「１．０」に設定されているので、図９の９−１に示すように、選択した最短経路（１）を形成するリンクに通信量「１．０」をそれぞれ展開する。
【００４３】
続いて、計算部３５２は、図９の９−２に示すように、「ｓ」と「ｂ」とが通信を行う場合の最短経路として、（１）Ａ→Ｂ→Ｄ、（２）Ａ→Ｃ→Ｄを列挙する。ここで、図９の９−２に示すように、「ｓ」⇔「ｂ」について列挙した最短経路（１）、（２）の最大通信量は、「１．０」、「０．０」となる。よって、計算部３５２は、最大通信量が最も小さい最短経路（２）を選択する。そして、計算部３５２は、「ｓ」⇔「ｂ」の通信量は「１．５」に設定されているので、上述した他の最短経路を選択した場合と同様に、選択した最短経路（２）を形成するリンクに通信量「１．０」をそれぞれ展開する。
【００４４】
続いて、計算部３５２は、図１０の１０−２に示すように、「ｓ」と「ｃ」とが通信を行う場合の最短経路として、（１）Ａ→Ｂ→Ｄ→Ｅ→Ｇ、（２）Ａ→Ｂ→Ｄ→Ｆ→Ｇ、（３）Ａ→Ｃ→Ｄ→Ｅ→Ｇ、（４）Ａ→Ｃ→Ｄ→Ｆ→Ｇを列挙する。ここで、図１０の１０−２に示すように、「ｓ」⇔「ｃ」について列挙した最短経路（１）および（２）の最大通信量は、「１．０」、最短経路（３）および（４）の最大通信量は「１．５」となる。そこで、計算部３５２は、まず、最大通信量が低い方の最短経路（１）および（２）を取得する。続いて、計算部３５２は、取得した最短経路（１）および（２）の２番目のリンクの最大通信量を比較する。比較の結果、最短経路（１）および（２）の２番目のリンクの最大通信量は共に「１．０」なので、続いて、３番目のリンクの最大通信量を比較する。比較の結果、最短経路（２）の３番目のリンクの最大通信量「０．０」の方が、最短経路（１）の３番目のリンクの最大通信量「１．０」よりも小さいので、最短経路（２）を選択する。そして、計算部３５２は、「ｓ」⇔「ｃ」の通信量は「１．０」に設定されているので、上述した他の最短経路を選択した場合と同様に、選択した最短経路（２）を形成するリンクに通信量「１．０」をそれぞれ展開する。
【００４５】
このようにして、計算部３５２は、ネットワークグラフ上に、スイッチ１００間を接続する各リンクの通信量ができるだけ分散するような通信ペア間の初期経路を決定する。
【００４６】
通信ペアごとの初期経路を決定後、計算部３５２は、通信ペア間に設定された通信量に基づいて、ネットワークグラフ上に決定した初期経路で形成される各ターンの通信量をそれぞれ計算する。ここで、計算部３５２は、初期経路でターンが重複する箇所については、重複するターンの通信量を加算する。
【００４７】
決定部３５３は、計算された各ターンの通信量に基づいて、パケット通信を行わない禁止ターンを決定する。例えば、決定部３５３は、生成部３５１により生成されたネットワークグラフ上に、計算部３５２により計算された各ターンの通信量を展開し、Ｕｐ／ｄｏｗｎ法またはＴＰ法を応用して禁止ターンを決定する。
【００４８】
決定部３５３は、例えば、Ｕｐ／ｄｏｗｎ法を応用する場合、次のようにして禁止ターンを決定する。まず、決定部３５３は、各スイッチ１００を頂点としたときの禁止ターンを仮決定する。続いて、決定部３５３は、仮決定した禁止ターンごとに、禁止ターンの通信量の合計値を計算する。そして、決定部３５３は、ターン通信量の合計値が最小となる仮禁止ターンを最終的な禁止ターンに決定する。このようにして、決定部３５３は、Ｕｐ／ｄｏｗｎ法を応用して禁止ターンを決定する。
【００４９】
また、決定部３５３は、例えば、ＴＰ法を応用する場合、次のようにして禁止ターンを決定する。まず、決定部３５３は、ネットワークグラフ上のスイッチ１００ごとに、該当スイッチ１００が形成するターンの通信量の合計値を計算する。言い換えれば、決定部３５３は、ネットワークグラフ上のスイッチ１００ごとに、該当スイッチ１００の入力ポートと対向する出力ポートとの組合せを介して入出力されるパケットの通信量の合計値を計算する。
【００５０】
続いて、決定部３５３は、各ターンの通信量の合計値が最小である該当スイッチを経由するターンを禁止ターンに決定する。続いて、決定部３５３は、該当スイッチ１００および該当スイッチ１００に接続されるリンクを削除し、残りの各スイッチについてターンの通信量を計算部３５２に再計算させる。そして、決定部３５３は、上述したのと同様に、再び、各ターンの通信量の合計値を計算し、合計値が最小である該当スイッチを経由するターンを禁止ターンに決定する。決定部３５３は、ネットワークグラフ上に形成されるターンがなくなるまで、同処理を繰り返し行う。このようにして、決定部３５３は、ＴＰ法を応用して禁止ターンを決定する。
【００５１】
以下、図１１〜図１３を参照しつつ、決定部３５３による禁止ターンの決定方法を説明する。まず、図１１および図１２を参照しつつ、Ｕｐ／ｄｏｗｎ法を応用した禁止ターンの決定方法について説明する。図１１および図１２は、実施例１に係るＵｐ／ｄｏｗｎ法を応用した禁止ターンの決定方法を説明するための図である。図１１は、シンプルなネットワークグラフについてＵｐ／ｄｏｗｎ法を応用した場合の禁止ターンの決定方法を示す。図１２は、図１１よりも複雑なネットワークグラフについてＵｐ／ｄｏｗｎ法を応用した場合の禁止ターンの決定方法を示す。
【００５２】
図１１について説明する。図１１に示すＳ１〜Ｓ４はスイッチに相当する。図１１の示すスイッチＳ１〜Ｓ４を経由する各矢印はターンを表し、矢印に併記される数字はターン通信量を表す。図１１の１１−１は、Ｕｐ／ｄｏｗｎ法により、スイッチＳ１を頂点とした場合に決定される仮禁止ターンがスイッチＳ１の対角線上にあるスイッチＳ３を経由する矢印となることを表している。図１１の１１−２は、Ｕｐ／ｄｏｗｎ法により、スイッチＳ４を頂点とした場合に決定される仮禁止ターンがスイッチＳ４の対角線上にあるスイッチＳ２を経由する矢印となることを表している。図１１の１１−３は、Ｕｐ／ｄｏｗｎ法により、スイッチＳ２を頂点とした場合に決定される仮禁止ターンがスイッチＳ２の対角線上にあるスイッチＳ４を経由する矢印となることを表している。図１１の１１−４は、Ｕｐ／ｄｏｗｎ法により、スイッチＳ３を頂点とした場合に決定される仮禁止ターンがスイッチＳ３の対角線上にあるスイッチＳ１を経由する矢印となることを表している。
【００５３】
図１１の１１−１に表すように、スイッチＳ１を頂点とした場合に決定される仮禁止ターンのターン通信量は「１」である。また、図１１の１１−２に表すように、スイッチＳ４を頂点とした場合に決定される仮禁止ターンのターン通信量は「１０」である。また、図１１の１１−３に表すように、スイッチＳ２を頂点とした場合に決定される仮禁止ターンのターン通信量は「１０」である。また、図１１の１１−４に表すように、スイッチＳ３を頂点とした場合に決定される仮禁止ターンのターン通信量は「１」である。図１１に示す場合では、スイッチＳ１またはスイッチＳ３を頂点とした場合に決定される仮禁止ターンのターン通信量が「１」で最小となる。よって、決定部３５３は、スイッチＳ１またはスイッチＳ３を頂点とした場合に決定される仮禁止ターンのいずれか一方を最終的な禁止ターンに決定する。
【００５４】
次に、図１２について説明する。図１２に示すＳ５〜Ｓ１１はスイッチに相当する。図１２の示すスイッチＳ５〜Ｓ１１を経由する各矢印はターンを表し、矢印に併記される数字はターン通信量を表す。図１２の１２−１は、Ｕｐ／ｄｏｗｎ法により、スイッチＳ５を頂点とした場合に決定される仮禁止ターンが矢印となることを表している。図１２の１２−２は、Ｕｐ／ｄｏｗｎ法により、スイッチＳ６を頂点とした場合に決定される仮禁止ターンが矢印となることを表している。図１２の１２−３は、Ｕｐ／ｄｏｗｎ法により、スイッチＳ７を頂点とした場合に決定される仮禁止ターンが矢印となることを表している。
【００５５】
図１２の１２−１に表すように、スイッチＳ５を頂点とした場合に決定される仮禁止ターンのターン通信量の合計値は「１７」である。また、図１２の１２−２に表すように、スイッチＳ６を頂点とした場合に決定される仮禁止ターンのターン通信量の合計値は「６」である。また、図１２の１２−３に表すように、スイッチＳ７を頂点とした場合に決定される仮禁止ターンのターン通信量の合計値は「１０」である。このように、決定部３５３は、各スイッチＳ５〜Ｓ１１を頂点とした場合に決定される仮禁止ターンのターン通信量の合計値を算出し、合計値が最小となるときの仮禁止ターンを最終的な禁止ターンに決定する。
【００５６】
続いて、図１３を参照しつつ、ＴＰ法を応用した禁止ターンの決定方法について説明する。図１３は、実施例１に係るＴＰ法を応用した禁止ターンの決定方法を説明するための図である。図１３に示すＳ５〜Ｓ１１はスイッチに相当する。図１３の示すスイッチＳ５〜Ｓ１１を経由する各矢印はターンを表し、スイッチＳ５〜Ｓ１１内に表記される数字は該当スイッチを経由する各ターンの通信量の合計値を表す。なお、図１３に示す１３−１から１３−６へ向かって、ＴＰ法を応用した禁止ターンの決定が進む。
【００５７】
図１３の１３−１に表すように、スイッチＳ５を経由する各ターンの通信量の合計値が「１」で最小となっている。よって、決定部３５３は、スイッチＳ５を経由するターンを禁止ターンに決定する。
【００５８】
続いて、図１３の１３−２に表すように、スイッチＳ５およびスイッチＳ５に隣接して接続されるリンクを削除後、スイッチＳ６およびスイッチＳ１０を経由する各ターンの通信量の合計値がそれぞれ「２」で最小となっている。よって、決定部３５３は、スイッチＳ６か、スイッチＳ１０のいずれか一方、図１３ではスイッチＳ１０を経由するターンを禁止ターンに決定する。
【００５９】
続いて、図１３の１３−３に表すように、スイッチＳ１０およびスイッチＳ１０に隣接して接続されるリンクを削除後、スイッチＳ９およびスイッチＳ１１を経由する各ターンの通信量の合計値がそれぞれ「０」で最小となっている。よって、決定部３５３は、スイッチＳ９か、スイッチＳ１１のいずれか一方、図１３ではスイッチＳ９を経由するターンを禁止ターンに決定する。
【００６０】
続いて、図１３の１３−４に表すように、スイッチＳ９およびスイッチＳ９に隣接して接続されるリンクを削除後、スイッチＳ１１を経由する各ターンの通信量の合計値が「０」で最小となっている。よって、決定部３５３は、スイッチＳ１１を経由するターンを禁止ターンに決定する。
【００６１】
続いて、図１３の１３−５に表すように、スイッチＳ１１およびスイッチＳ１１に隣接して接続されるリンクを削除後、スイッチＳ６を経由する各ターンの通信量の合計値が「２」で最小となっている。よって、決定部３５３は、スイッチＳ６を経由するターンを禁止ターンに決定する。そして、図１３の１３−６に表すように、スイッチＳ６およびスイッチＳ６に隣接して接続されるリンクを削除後、ネットワークグラフ内に形成されるターンがなくなるので、決定部３５３は、禁止ターンの決定を完了する。
【００６２】
図１に戻り、算出部３５４は、ネットワーク１を介して相互に通信を行う通信ペアについて、決定部３５３により決定された禁止ターンを避けた最終的な通信経路、いわゆるルーティングを算出する。算出部３５４は、図２〜図６、図７〜図１０を用いて上述した初期経路の決定方法と同様の方法を用いて、最終的なルーティングを決定する。例えば、ある通信ペアについて、禁止ターンを避けた最短経路を列挙する。続いて、算出部３５４は、この通信ペアについて列挙した複数の最短経路の中から、経路内の最大通信量が最も小さい最短経路を選択する。そして、選択された経路で使用されるリンクの通信量を求め、次の通信ペアについて最短経路を列挙する。以上の処理を全ての通信ペアについて実行することにより最終的なルーティング、言い換えれば、実際に通信を行う場合の最終的な通信経路を算出する。
【００６３】
ここで、図１４〜１９を参照しつつ、あるネットワーク形態について、Ｕｐ／ｄｏｗｎ法を応用した禁止ターンの決定方法を説明する。図１４は、実施例１に係る各リンクの通信量を示す図である。図１４は、あるネットワーク形態をモデル化したネットワークグラフを表している。図１４に示す「Ａ」〜「Ｇ」はスイッチに相当する。図１４に示す「ａ」〜「ｔ」は、並列処理を行うサーバ群に相当し、「ａ」〜「ｌ」でグループ１を形成し、「ｍ」〜「ｔ」でグループ２を形成する。また、図１４に示す「Ｓｖ」は、ファイルの入出力を行うサーバに相当する。
【００６４】
図１４に示すグループ１の「ａ」〜「ｌ」、および図１４に示すグループ２の「ｍ」〜「ｔ」は、それぞれ同一グループ内で密に通信を行い、グループ間での通信は行わない。また、図１４に示すグループ１の「ａ」〜「ｌ」、および図１４に示すグループ２の「ｍ」〜「ｔ」は、図１４に示す「Ｓｖ」とは通信を行う。また、図１４に示す「Ｓｖ」は、図１４に示すグループ１の「ａ」〜「ｌ」、または図１４に示すグループ２の「ｍ」〜「ｔ」からファイルの入出力処理を受け付けて応答を返す。また、図１４に示す「Ｓｖ」は、他の「Ｓｖ」との間で通信を行う。
【００６５】
図１４に示すネットワークにおける通信量を次のように定義する。パケットの送信元となるサーバグループに属する一つのサーバが、パケットの受信先となるサーバグループに属する全サーバに送信する場合の通信量を定義する。さらに、受信した通信量と同一の通信量を応答として返信するものとし、送信通信量と応答通信量の合計値を通信量として定義する。
【００６６】
例えば、図１４に示すグループ１に属するサーバグループ内で通信を行う場合の通信量、および図１４に示すグループ２に属するサーバグループ内で通信を行う場合の通信量を共に「０．９」に設定する。ここで、グループ１に属するサーバグループとは、図１４に示す「ａ」〜「ｄ」、「ｅ」〜「ｈ」、「ｉ」〜「ｌ」のいずれかに該当し、グループ２に属するサーバグループとは、図１４に示す「ｍ」〜「ｐ」、「ｑ」〜「ｔ」のいずれかに該当する。また、図１４に示すグループ１に属するサーバ「ａ」〜「ｌ」または図１４に示すグループ２に属するサーバ「ｍ」〜「ｔ」と、ファイルの入出力を行うサーバ「Ｓｖ」とが通信を行う場合の通信量を「０．１」に設定する。また、ファイルの入出力を行うサーバ「Ｓｖ」間で通信を行う場合の通信量を「０．１」に設定する。このとき、図１４の１４−１に示すリンクの通信量は「２．６」、図１４の１４−２に示すリンクの通信量は「２．１」である。
【００６７】
図１４において、計算部３５２は、例えば、図２〜図６、図７〜図１０を用いて上述した初期経路の決定方法を用いて、通信を行う通信ペアについて初期経路を決定する。そして、計算部３５２は、初期経路におけるターン通信量を計算する。例えば、以下では、図１４に示すグループ１の「ａ」〜「ｄ」とグループ１内の「ｅ」および「ｇ」との間で密に通信を行い、図１４に示すグループ１の「ｅ」〜「ｈ」とグループ１内の「ａ」および「ｃ」との間で密に通信を行う場合について説明する。
【００６８】
まず、図１４に示すグループ１の「ａ」とグループ１内の「ｅ」、「ｇ」との間で通信を行う場合のターン通信量について説明する。「ａ」と「ｅ」、「ａ」と「ｇ」が通信を行う場合の初期経路としてスイッチ「Ａ」を経由するルートが決定されたものとすると、スイッチ「Ａ」を経由するターンが形成される。例えば、「ａ」から「ｅ」へ送信されたパケットが、スイッチ「Ａ」を経由してスイッチ「Ｃ」からスイッチ「Ｄ」に転送される際のターンが形成されるが、このターンを便宜上ターンＣＡＤとする。そして、「ｅ」から「ａ」へ返信された応答パケットが、スイッチ「Ａ」を経由してスイッチ「Ｄ」からスイッチ「Ａ」に転送される際のターンが形成されるが、このターンを便宜上ターンＤＡＣとする。ここで、グループ１内の通信量は「０．９」に設定されているので、「ａ」と「ｅ」との間で通信を行う場合の通信量は、０．９を１２で除算して「０．０７５」と求められる。よって、ターンＣＡＤおよびターンＤＡＣのターン通信量はそれぞれ「０．０７５」となる。
【００６９】
また、「ａ」と「ｅ」との間で通信を行う場合と同様に、「ａ」から「ｇ」へ送信されたパケットが、スイッチ「Ａ」を経由してスイッチ「Ｃ」からスイッチ「Ｄ」に転送される際に形成されるターンは、上述したターンＣＡＤである。そして、「ｇ」から「ａ」へ返信された応答パケットが、スイッチ「Ａ」を経由してスイッチ「Ｄ」からスイッチ「Ａ」に転送される際に形成されるターンは、上述したターンＤＡＣとなる。ここで、「ａ」と「ｇ」との間で通信を行う場合の通信量は、「ａ」と「ｅ」との間で通信を行う場合と同様に「０．０７５」となるので、ターンＣＡＤおよびターンＤＡＣのターン通信量はそれぞれ「０．０７５」となる。よって、グループ１の「ａ」とグループ１内の「ｅ」、「ｇ」との間で通信を行う場合のターン通信量は「０．１５０」となる。
【００７０】
また、図１４に示すグループ１の「ｂ」とグループ１内の「ｅ」、「ｇ」との間で通信を行う場合のターン通信量も「０．１５０」となる。また、図１４に示すグループ１の「ｃ」とグループ１内の「ｅ」、「ｇ」との間で通信を行う場合のターン通信量も「０．１５０」となる。また、図１４に示すグループ１の「ｄ」とグループ１内の「ｅ」、「ｇ」との間で通信を行う場合のターン通信量も「０．１５０」となる。よって、図１４に示すグループ１の「ａ」〜「ｄ」とグループ１内の「ｅ」、「ｇ」との間で通信を行う場合のターン通信量の合計は「０．６００」となる。
【００７１】
続いて、図１４に示すグループ１の「ｅ」〜「ｈ」とグループ１内の「ａ」、「ｃ」との間で通信を行う場合のターン通信量について説明する。グループ１の「ｅ」〜「ｈ」とグループ１内の「ａ」、「ｃ」との間で通信を行う場合のターン通信量も、グループ１の「ａ」〜「ｄ」とグループ１内の「ｅ」、「ｇ」との間で通信を行う場合と同様にして求められる。よって、グループ１の「ｅ」〜「ｈ」とグループ１内の「ａ」、「ｃ」との間で通信を行う場合のターン通信量の合計は「０．６００」となる。したがって、上述したターンＣＡＤおよびターンＤＡＣのターン通信量は「１．２」となる。
【００７２】
このように、ターンＣＡＤおよびターンＤＡＣのターン通信量の計算方法を同様に適用することにより、図１５に示すように、初期経路におけるターン通信量が計算される。図１５は、実施例１に係る各ターンの通信量を示す図である。図１５に示す矢印はターンを表し、矢印に併記される数値はターンの通信量を表す。
【００７３】
計算部３５２により初期経路における各ターンの通信量の計算が完了すると、決定部３５３は、各ターンの通信量を考慮して禁止ターンを決定する。以下、図１６〜図１８を用いて、決定部３５３による禁止ターンの決定について説明する。図１６は、実施例１に係るスイッチＡを頂点とした場合の禁止ターンの通信量を示す図である。図１７は、実施例１に係るスイッチＣを頂点とした場合の禁止ターンの通信量を示す図である。図１８は、実施例１に係るスイッチＧを頂点とした場合の禁止ターンの通信量を示す図である。
【００７４】
図１６の矢印に示すように、決定部３５３は、Ｕｐ／ｄｏｗｎ法を用いて、スイッチ「Ａ」を頂点と選択した場合の禁止ターンを決定する。続いて、決定部３５３は、図１７の矢印に示すように、Ｕｐ／ｄｏｗｎ法を用いて、スイッチ「Ｃ」を頂点と選択した場合の禁止ターンを決定する。続いて、決定部３５３は、図１８の矢印に示すように、Ｕｐ／ｄｏｗｎ法を用いて、スイッチ「Ｇ」を頂点と選択した場合の禁止ターンを決定する。このようにして、決定部３５３は、全スイッチを頂点としたときの禁止ターンをそれぞれ決定し、禁止ターンの通信量の合計値が最も小さいものを最終的な禁止ターンに決定する。仮に、スイッチ「Ｇ」を頂点として選択した場合に決定された禁止ターンの通信量の合計値が最小である場合には、決定部３５３は、スイッチ「Ｇ」を頂点として選択した場合に決定された禁止ターンを最終的な禁止ターンに決定する。
【００７５】
決定部３５３による禁止ターンの決定後、算出部３５４は、決定部３５３により決定された禁止ターンを避けた最終的なルーティング、言い換えれば、実際に通信を行う場合の最終的な通信経路を算出する。図１９は、実施例１に係る最終経路の各リンクの通信量を示す図である。図１９は、例えば、スイッチ「Ｇ」を頂点として選択したときの禁止ターンを避けて算出された最終的な通信経路における各リンクの通信量を表す。例えば、図１９に示すように、１９−１に示す各リンクの通信量は「２．６」となり、１９−２に示す各リンクの通信量は「２．００」となり、１９−３に示す各リンクの通信量は「２．２０」となる。なお、最終的な通信経路における各リンクの通信量の平均値は「２．４０」、最大値は「２．６０」、標準偏差は「０．２６０」となる。
【００７６】
ここで、例えば、図２０および図２１を参照しつつ、スイッチ「Ｇ」を頂点として禁止ターンを決定した場合の各リンクの通信量と、スイッチ「Ｇ」以外のスイッチを頂点として禁止ターンを決定した場合の各リンクの通信量とを比較する。図２０は、実施例１に係るスイッチＡを頂点として禁止ターンを決定した場合の通信経路の各リンクの通信量を示す図である。図２１は、実施例１に係るスイッチＣを頂点として禁止ターンを決定した場合の通信経路の各リンクの通信量を示す図である。
【００７７】
図２０に示すように、２０−１に示す各リンクの通信量は「５．００」となり、２０−２に示す各リンクの通信量は「３．９０」となり、２０−３に示す各リンクの通信量は「０．２０」となり、２０−４に示す各リンクの通信量は「０．３０」となる。なお、最終的な通信経路における各リンクの通信量の平均値は「２．４０」、最大値は「５．００」、標準偏差は「２．２５０」となる。
【００７８】
また、図２１に示すように、２１−１に示す各リンクの通信量は「２．８０」となり、２１−２に示す各リンクの通信量は「２．６０」となり、２１−３に示す各リンクの通信量は「２．００」となる。なお、最終的な通信経路における各リンクの通信量の平均値は「２．４０」、最大値は「２．８０」、標準偏差は「０．３４４」となる。
【００７９】
ここで、図１９に示すように、スイッチ「Ｇ」を頂点として禁止ターンを決定した場合の各リンクの通信量の標準偏差は「０．２６０」である。また、図２０に示すように、スイッチ「Ａ」を頂点として禁止ターンを決定した場合の各リンクの通信量の標準偏差は「２．２５０」である。また、図２１に示すように、スイッチ「Ｃ」を頂点として禁止ターンを決定した場合の各リンクの通信量の標準偏差は「２．２５０」である。このように、スイッチＧを頂点として禁止ターンを決定した場合の方が、スイッチ「Ａ」やスイッチ「Ｃ」を頂点として禁止ターンを決定する場合よりも、最終的な通信経路における各リンクの通信量がより分散されることがわかる。
【００８０】
上述した制御部３５０が内部的に有するメモリは、例えば、ＲＡＭ（Random  Access  Memory）やフラッシュメモリ(flash  memory)などの半導体メモリ素子に該当する。また、制御部３５０の生成部３５１、計算部３５２、決定部３５３および算出部３５４は、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路を有する。また、生成部３５１、計算部３５２、決定部３５３および算出部３５４は、ＣＰＵやＭＰＵの代わりに、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ(Field  Programmable  Gate  Array)などの集積回路を用いてもよい。
【００８１】
［禁止ターン決定装置による処理（実施例１）］
図２２〜２４を用いて、実施例１に係る禁止ターン決定装置による処理の流れを説明する。図２２は、実施例１に係る処理の流れを示す図である。図２３は、実施例１に係るＵｐ／ｄｏｗｎ法を応用した禁止ターン決定処理の流れを示す図である。図２４は、実施例１に係るＴＰ法を応用した禁止ターン決定処理の流れを示す図である。
【００８２】
まず、図２２を用いて、禁止ターン決定装置３００による処理の流れを説明する。図２２に示すように、ルーティング決定の処理開始指示があると（ステップＳ３０１，Ｙｅｓ）、生成部３５１は、ネットワーク１の構造をモデル化したネットワークグラフを生成する（ステップＳ３０２）。なお、生成部３５１は、処理開始指示があるまで、ステップＳ３０１の判定結果を「Ｎｏ」として、同判定を繰り返す。
【００８３】
続いて、計算部３５２は、スイッチ１００およびスイッチ１００に隣接して接続される各リンクにより形成される各ターンの通信量をそれぞれ計算する（ステップＳ３０３）。続いて、決定部３５３は、各ターンの通信量に基づいて、パケット通信を行わない禁止ターン決定処理を実行する（ステップＳ３０４）。なお、禁止ターン決定処理については図２３および図２４を用いて後述する。そして、算出部３５４は、禁止ターンを避けた最終的な通信経路を算出し（ステップＳ３０５）、処理を終了する。
【００８４】
次に、図２３を用いて、Ｕｐ／ｄｏｗｎ法を応用した禁止ターン決定処理の流れを説明する。決定部３５３は、Ｕｐ／ｄｏｗｎ法を応用する場合、次のようにして禁止ターンを決定する。図２３に示すように、決定部３５３は、まず、ネットワークグラフ上で頂点となるスイッチを一つ選択し（ステップＳ４０１）、禁止ターンを仮決定する（ステップＳ４０２）。続いて、決定部３５３は、仮決定した禁止ターンの合計通信量を計算する（ステップＳ４０３）。
【００８５】
そして、決定部３５３は、全てのスイッチを頂点として選択して禁止ターンの仮決定を行う処理を完了しているか否かを判定する（ステップＳ４０４）。判定の結果、処理を完了していない場合には（ステップＳ４０４，Ｎｏ）、決定部３５３は、上述したステップＳ４０１に戻り、残りのスイッチの中から頂点とするスイッチを一つ選択し、ステップＳ４０２〜ステップＳ４０４の処理を実行する。
【００８６】
ここで、ステップＳ４０４の説明に戻る。判定の結果、処理を完了している場合には（ステップＳ４０４，Ｙｅｓ）、決定部３５３は、仮決定した各禁止ターンの合計通信量のうち、合計通信量が最小のものを最終的な禁止ターンに決定する（ステップＳ４０５）。以上で、決定部３５３は、Ｕｐ／ｄｏｗｎ法を応用した禁止ターン決定処理を完了する。
【００８７】
次に、図２４を用いて、ＴＰ法を応用した禁止ターン決定処理の流れを説明する。決定部３５３は、ＴＰ法を応用する場合、次のようにして禁止ターンを決定する。図２４に示すように、決定部３５３は、まず、各ターンの合計通信量を計算する（ステップＳ５０１）。続いて、決定部３５３は、合計通信量が最小となるターンを禁止ターンに決定し（ステップＳ５０２）、禁止ターンの対応箇所のスイッチをネットワークグラフから削除する（ステップＳ５０３）。
【００８８】
そして、決定部３５３は、ネットワークグラフ内にターンを形成するスイッチが残っているか否かを判定する（ステップＳ５０４）。判定の結果、ターンを形成するスイッチがある場合には（ステップＳ５０４，Ｙｅｓ）、決定部３５３は、上述したステップＳ５０１に戻り、再び、各ターンの合計通信量を計算する。そして、決定部３５３は、ステップＳ５０２〜ステップＳ５０４の処理を実行する。
【００８９】
ここでステップＳ５０４の説明に戻る。決定部３５３は、判定の結果、ネットワークグラフ内にターンを形成するスイッチがない場合には（ステップＳ５０４，Ｎｏ）、ＴＰ法を応用した禁止ターン決定処理を完了する。
【００９０】
［実施例１による効果］
上述してきたように、実施例１に係る禁止ターン決定装置３００は、通信ペア、すなわち、ネットワーク１を介して相互に通信を行うサーバ２００のペアごとに、スイッチ１００間を接続する各リンクの通信量ができるだけ分散するような初期経路を決定する。続いて、禁止ターン決定装置３００は、通信ペアであるエンドノード間に設定された通信量に基づいて、初期経路内に形成される各ターンの通信量をそれぞれ計算する。続いて、禁止ターン決定装置３００は、各ターンの通信量に基づいて、Ｕｐ／ｄｏｗｎ法またはＴＰ法により、パケット通信を行わない禁止ターンを決定する。そして、禁止ターン決定装置３００は、禁止ターンを避けた最終的なルーティングを決定する。このように、禁止ターン決定装置３００は、各ターンの通信量を考慮して禁止ターンを決定し、この禁止ターンを避けるように最終的なルーティングを決定する。上述したように、図１９と、図２０および図２１との比較結果が示すように、各ターンの通信量を考慮して禁止ターンを決定する方が、最終的な通信経路のリンク間の通信量がより分散されている。このようなことから、実施例１によれば、ネットワーク１内に収容されるスイッチ１００間を接続する各リンクの通信量が効率的に分散されたルーティングを得ることができる。
【００９１】
また、実施例１によれば、Ｕｐ／ｄｏｗｎ法またはＴＰ法を利用して禁止ターンを決定するので、新たな処理機能部を必要最小限準備するだけで、各リンクの通信量が効率的に分散されたルーティングを得ることができる。
【実施例２】
【００９２】
Ｕｐ／ｄｏｗｎ法またはＴＰ法では、ネットワークグラフが持つ幾何学的性質を利用して禁止ターンを決定することによりターンのループを除去する。しかしながら、ネットワークグラフの幾何学的性質を利用するために、例えば、図２５や図２６に示すように、一部のスイッチに禁止ターンが集中する場合がある。
【００９３】
図２５は、Ｕｐ／ｄｏｗｎ法によるトーラスネットワークについての禁止ターン決定例を示す図である。図２５に示す２５−１と同一の図形はスイッチを表し、図２５に示す２５−２は頂点として選択されたスイッチを表す。Ｕｐ／ｄｏｗｎ法を用いて、図２５に示すようなトーラスネットワークの禁止ターンを決定すると、図２５の２５−３に示すように、一部のスイッチに禁止ターンが集中してしまう場合がある。
【００９４】
図２６は、ＴＰ法によるトーラスネットワークについての禁止ターン決定例を示す図である。図２６に示す２６−１と同一の図形はスイッチを表す。ＴＰ法を用いて、図２６に示すようなトーラスネットワークの禁止ターンを決定すると、図２６の２６−２に示すように、一部のスイッチに禁止ターンが集中してしまう場合がある。
【００９５】
図２５や図２６に示すように、一部のスイッチに禁止ターンが集中してしまうと、最終的に決定されたルーティングにおいて、各リンクの通信量が上手く分散されないという事態が発生することも考えられる。
【００９６】
そこで、実施例２では、Ｕｐ／ｄｏｗｎ法またはＴＰ法を利用することなく禁止ターンを決定することにより、各リンクの通信量が効率的に分散されたルーティングを得ることができる禁止ターン決定装置の一実施形態について説明する。
【００９７】
［禁止ターン決定装置の構成（実施例２）］
図２７は、実施例２に係る禁止ターン決定装置の構成を示す機能ブロック図である。図２７に示すように、禁止ターン決定装置４００は、複数のスイッチ１００を収容するネットワーク１に接続される。禁止ターン決定装置４００は、ネットワーク１内に収容される複数のスイッチ１００間でパケットをやり取りするためのルーティングを決定するに際して、パケットのやり取りを行わない禁止ターンを決定する。なお、複数のサーバ２００は、ネットワーク１に接続され、ネットワーク１を介して相互に通信を行う。
【００９８】
図２７に示すように、禁止ターン決定装置４００は、入力部４１０と、出力部４２０と、ネットワークインターフェース４３０と、記憶部４４０と、制御部４５０とを有する。なお、図２７に示す禁止ターン決定装置４００は、制御部４５０の処理機能の一部が、上述した図１に示す禁止ターン決定装置３００の制御部３５０と異なる。そこで、以下では、この異なる部分について説明する。
【００９９】
制御部４５０は、所定の制御プログラムや各種の処理手順などを規定したプログラム、所要データを格納するための内部メモリを有し、内部メモリに所定のプロセスを展開することにより種々の処理を実行する。例えば、制御部４５０は、図２７に示すように、生成部４５１と、決定部４５２と、算出部４５３とを有する。
【０１００】
決定部４５２は、生成部４５１により生成されたネットワークグラフにターンを一つずつ順に追加し、追加された各ターンによりループが形成されたときの追加ターンをパケットの転送に使用しない禁止ターンに決定する。なお、ターンとは、上述した実施例１と同様に、スイッチ１００に搭載された入力ポートと、この入力ポートに対向する出力ポートとの組合せで定義される。言い換えれば、パケットを入力した入力ポートと入力パケットを転送先へ出力する出力ポートとの組合せで定義される。以下、図２８を参照しつつ、決定部４５２による禁止ターンの決定方法について説明する。
【０１０１】
図２８は、実施例２に係る禁止ターンの決定方法を説明するための図である。図２８に示す２８ｓと同様の形状を有する図形はスイッチを表す。図２８に示す２８−１〜２８−９はターンが一つずつ追加された時のネットワークグラフを表し、２８−１から２８−９の順にターンが一つずつ追加されるものとする。図２８に示す２８Ｔ１〜２８Ｔ９はターンを表す。決定部４５２は、図２８の２８−１に示すように、ネットワークグラフにターン２８Ｔ１を一つ追加する。そして、決定部４５２は、ターン２８Ｔ１を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。ここで、ターンとは、パケットの入力ポートと、このパケットの出力ポートとの組合せで定義される概念であり、スイッチに入力されたパケットが、このスイッチを経由して宛先のスイッチへ転送される場合の転送方向に対応する。ターンのループとは、各ターンが途切れることなく接続され、ネットワーク内を周回する状態となることをいう。
【０１０２】
判定の結果、ネットワークグラフにターンのループは形成されないので、決定部４５２は、ターン２８Ｔ１を許可ターンに決定してネットワークグラフに残す。続いて、決定部４５２は、図２８の２８−２に示すように、ターン２８Ｔ２をネットワークグラフにさらに一つ追加する。そして、決定部４５２は、ターン２８Ｔ２を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。判定の結果、ネットワークグラフにターンのループは形成されないので、決定部４５２は、ターン２８Ｔ２を許可ターンに決定する。続いて、決定部４５２は、図２８の２８−３に示すように、ターン２８Ｔ３をネットワークグラフにさらに一つ追加する。そして、決定部４５２は、ターン２８Ｔ３を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。
【０１０３】
判定の結果、ネットワークグラフにターンのループは形成されないので、決定部４５２は、ターン２８Ｔ３を許可ターンに決定する。続いて、決定部４５２は、図２８の２８−４に示すように、ターン２８Ｔ４をネットワークグラフにさらに一つ追加する。そして、決定部４５２は、ターン２８Ｔ４を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。判定の結果、ネットワークグラフにターンのループは形成されないので、決定部４５２は、ターン２８Ｔ４を許可ターンに決定する。続いて、決定部４５２は、図２８の２８−５に示すように、ターン２８Ｔ５をネットワークグラフにさらに一つ追加する。そして、決定部４５２は、ターン２８Ｔ５を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。
【０１０４】
判定の結果、ネットワークグラフにターンのループが形成されるので、決定部４５２は、ネットワークグラフにターンのループが形成されることとなった追加ターン２８Ｔ５を禁止ターンに決定する。続いて、決定部４５２は、図２８の２８−６に示すように、ターン２８Ｔ６をネットワークグラフにさらに一つ追加する。そして、決定部４５２は、ターン２８Ｔ６を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。判定の結果、ネットワークグラフにターンのループは形成されないので、決定部４５２は、ターン２８Ｔ６を許可ターンに決定する。続いて、決定部４５２は、図２８の２８−７に示すように、ターン２８Ｔ７をネットワークグラフにさらに一つ追加する。そして、決定部４５２は、ターン２８Ｔ７を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。
【０１０５】
判定の結果、ネットワークグラフにターンのループは形成されないので、決定部４５２は、ターン２８Ｔ７を許可ターンに決定する。続いて、決定部４５２は、図２８の２８−８に示すように、ターン２８Ｔ８をネットワークグラフにさらに一つ追加する。そして、決定部４５２は、ターン２８Ｔ８を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。判定の結果、ネットワークグラフにターンのループは形成されないので、決定部４５２は、ターン２８Ｔ８を許可ターンに決定する。続いて、決定部４５２は、図２８の２８−９に示すように、ターン２８Ｔ９をネットワークグラフにさらに一つ追加する。そして、決定部４５２は、ターン２８Ｔ９を追加することによりネットワークグラフにターンのループが形成されるか否かを判定する。
【０１０６】
判定の結果、ネットワークグラフにターンのループが形成されるので、決定部４５２は、ネットワークグラフにターンのループが形成されることとなった追加ターン２８Ｔ９を禁止ターンに決定する。ここで、ネットワークグラフへのターンの追加が完了するので、言い換えれば、ネットワークに追加可能なターンが残っていないので、決定部４５２は、禁止ターンの決定を完了する。
【０１０７】
なお、算出部４５３は、決定部４５２により決定された禁止ターンを避けて、許可ターンで構築する最終的な通信経路、いわゆるルーティングを算出する。
【０１０８】
次に、図２９〜図３１を用いて、図２８を参照しつつ説明した方法で決定部４５２により禁止ターンを決定した場合のパケットの到達性について説明する。図２９〜図３１は、実施例２に係るパケットの到達性を説明するための図である。
【０１０９】
例えば、図２９は、１つの禁止ターンを含むリングネットワーク上に存在するスイッチ間でパケットをやり取りする場合を示す。図２９に示す２９ｓと同一の図形はスイッチを表し、図２９に示す２９Ｔと同様の線はターンを表す。また、図２９に示す２９ＢＴは禁止ターンを表し、図２９に示す２９ｓｓはパケットの送信元スイッチを表し、図２９に示す２９ｄｓはパケットの送信先スイッチを表す。図２９に示す２９ｓｓのスイッチから２９ｄｓのスイッチへ送出されたパケットは、２９ＢＴの禁止ターンが存在しても、図２９に示す２９Ｒのルートで２９ｄｓのスイッチへ到達する。
【０１１０】
例えば、図３０は、禁止ターンを１つ含むリングネットワークが２つ組み合わされたネットワークで、同一のリングネットワーク上に存在しないスイッチ間でパケットをやり取りする場合を示す。図３０に示す３０ｓと同一の図形はスイッチを表し、図３０に示す３０Ｔと同様の線はターンを表す。また、図３０に示す３０ＢＴ１および３０ＢＴ２は禁止ターンを表し、図３０に示す３０ｓｓはパケットの送信元スイッチを表し、図３０に示す３０ｄｓはパケットの送信先スイッチを表す。図３０に示す３０ｓｓのスイッチから３０ｄｓのスイッチへ送出されたパケットは、３０ＢＴ１および３０ＢＴ２の禁止ターンが存在しても、図３０に示す３０Ｒのルートで３０ｄｓのスイッチへ到達する。
【０１１１】
例えば、図３１は、禁止ターンを１つ含むリングネットワークが３つ組み合わされたネットワークで、同一のリングネットワーク上に存在しないスイッチ間でパケットをやり取りする場合を示す。図３１に示す３１ｓと同一の図形はスイッチを表し、図３１に示す３１Ｔと同様の線はターンを表す。また、図３１に示す３１ＢＴ１、３１ＢＴ２および３１ＢＴ３は禁止ターンを表し、図３１に示す３１ｓｓはパケットの送信元スイッチを表し、図３１に示す３１ｄｓはパケットの送信先スイッチを表す。図３１に示す３１ｓｓのスイッチから３１ｄｓのスイッチへ送出されたパケットは、３１ＢＴ１、３１ＢＴ２および３１ＢＴ３の禁止ターンが存在しても、図３１に示す３１Ｒのルートで３１ｄｓのスイッチへ到達する。
【０１１２】
図２９〜図３１に示すように、同一のリングネットワーク上に存在するスイッチ間は必ず連続する許可ターンが存在するので、どのスイッチから送出されたパケットでも宛先のスイッチへ到達可能である。異なるリングネットワーク上に存在するスイッチ間であっても、各リングネットワーク内に連続する許可ターンが存在し、かつネットワークは有限であるので、どのスイッチから送出されたパケットでも宛先のスイッチへ到達可能である。よって、決定部４５２により決定された禁止ターンを１つ含むリングネットワーク上に存在するスイッチ間でパケットがやり取りされる場合、パケットの到達性は保証される。
【０１１３】
［禁止ターン決定装置による処理（実施例２）］
続いて、図３２を参照しつつ、実施例２に係る禁止ターン決定装置による処理の流れを説明する。図３２は、実施例２に係る禁止ターン決定処理の流れを示す図である。
【０１１４】
図３２に示すように、ルーティング決定の処理開始指示があると（ステップＳ６０１，Ｙｅｓ）、生成部４５１は、ネットワーク１の構造をモデル化したネットワークグラフを生成する（ステップＳ６０２）。なお、生成部４５１は、処理開始指示があるまで、ステップＳ３０１の判定結果を「Ｎｏ」として、同判定を繰り返す。
【０１１５】
続いて、決定部４５２は、生成部４５１により生成されたネットワークグラフにターンを一つずつ順に追加する（ステップＳ６０３）。そして、決定部４５２は、ターンを追加することによりネットワークグラフ内にターンのループが形成されるか否かを判定する（ステップＳ６０４）。判定の結果、ループが形成される場合には（ステップＳ６０４，Ｙｅｓ）、決定部４５２は、追加ターンを禁止ターンに決定する（ステップＳ６０５）。一方、判定の結果、ループが形成されない場合には（ステップＳ６０４，Ｎｏ）、決定部４５２は、追加ターンを許可ターンに決定する（ステップＳ６０６）。
【０１１６】
そして、決定部４５２は、ネットワークグラフへのターンの追加が完了したか否かを判定する（ステップＳ６０７）。判定の結果、ターンの追加が完了している場合には（ステップＳ６０７，Ｙｅｓ）、決定部４５２は処理を完了する。一方、判定の結果、ターンの追加が完了していない場合には（ステップＳ６０７，Ｎｏ）、決定部４５２は、上述したステップＳ６０３に戻り、ステップＳ６０７までの処理を実行する。
【０１１７】
［実施例２による効果］
上述してきたように、実施例２に係る禁止ターン決定装置４００は、ネットワークグラフにターンを一つずつ順に追加し、追加された各ターンによりループが形成されたときの追加ターンをパケットの転送に使用しない禁止ターンに決定する。このようなことから、実施例２によれば、一部のスイッチに禁止ターンが集中してしまう事態を回避しつつ、各リンクの通信量が効率的に分散されたルーティングを得ることができる。
【０１１８】
例えば、図３３は、実施例２に係る方法による禁止ターンの決定例を示す図である。図３３に示すように、実施例２に係る方法、つまり、図２８を参照しつつ説明した方法によれば、一部のスイッチに禁止ターンが集中することがない。
【０１１９】
また、図３４は、各リンクの通信量の変動係数とスイッチ数との関係を示す図である。図３４に示す３４−１は、Ｕｐ／ｄｏｗｎ法により決定された禁止ターンに基づくルーティングのリンクの通信量の変動係数とスイッチ数との関係を示す。図３４に示す３４−２は、実施例２に係る方法により決定された禁止ターンに基づくルーティングのリンクの通信量の変動係数とスイッチ数との関係を示す。図３４に示す３４−３は、禁止ターンを設けない、すなわちターンを制限しないルーティングのリンクの通信量の変動係数とスイッチ数との関係を示す。図３４に示すように、実施例２に係る方法により決定された禁止ターンに基づくルーティングのリンクの通信量の方が、Ｕｐ／ｄｏｗｎ法により決定された禁止ターンに基づくルーティングのリンクの通信量よりも分散されることが分かる。そして、実施例２に係る方法によるリンクの通信量の方が、Ｕｐ／ｄｏｗｎ法によるリンクの通信量よりも、ターンを制限しないルーティングのリンクの通信量の分散に近づくことが分かる。図３４の３４−３に示すターンを制限しないルーティングを行った場合、実際には禁止ターンが発生するので使用することはできないが、リンクの通信量が最も効率的に分散されている状態に相当する。したがって、実施例２に係る方法によるリンクの通信量の方が、Ｕｐ／ｄｏｗｎ法によるリンクの通信量よりも、リンクの通信量の分散の程度を最も効率的な分散の程度に近づけられることが分かる。
【０１２０】
また、図３５は、リンクの最大通信量とスイッチ数との関係を示す図である。図３５に示す３５−１は、Ｕｐ／ｄｏｗｎ法により決定された禁止ターンに基づくルーティングのリンクの最大通信量とスイッチ数との関係を示す。図３５に示す３５−２は、実施例２に係る方法により決定された禁止ターンに基づくルーティングのリンクの最大通信量とスイッチ数との関係を示す。図３５に示す３５−３は、禁止ターンを設けない、すなわちターンを制限しないルーティングのリンクの最大通信量とスイッチ数との関係を示す。図３５に示すように、Ｕｐ／ｄｏｗｎ法により決定された禁止ターンに基づくルーティングのリンクの最大通信量よりも、実施例２に係る方法により決定された禁止ターンに基づくルーティングのリンクの最大通信量の方が低く抑えられることが分かる。図３４の３４−３に示すターンを制限しないルーティングを行った場合、実際には禁止ターンが発生するので使用することはできないが、リンクの最大通信量が最も低く抑えられている状態に相当する。したがって、実施例２に係る方法によるリンクの最大通信量の方が、Ｕｐ／ｄｏｗｎ法によるリンクの最大通信量よりも、リンクの最大通信量を最も低く抑えられている状態により近づけられることが分かる。
【実施例３】
【０１２１】
上述した実施例２において、各ターンの通信量を計算し、通信量が多いターンから順番に選択してネットワークグラフに追加することにより禁止ターンを決定するようにしてもよい。
【０１２２】
［禁止ターン決定装置の構成（実施例３）］
図３６は、実施例３に係る禁止ターン決定装置の構成を示す機能ブロック図である。図３６に示すように、禁止ターン決定装置４００は、計算部４５４を有する点が実施例２とは異なる。
【０１２３】
すなわち、計算部４５４は、ネットワークグラフ内の各ターンの通信量をそれぞれ計算する。なお、計算部４５４は、実施例１で説明した禁止ターン決定装置３００の計算部３５２と同様の方法で各ターンの通信量を計算する。例えば、計算部４５４は、生成部４５１により生成されたネットワークグラフ上で、スイッチ間を接続する各リンクの通信量ができるだけ分散するような通信ペア間の初期経路を決定する。そして、通信ペア、いわゆるエンドノードごとの初期経路を決定後、計算部４５４は、エンドノード間に設定された通信量に基づいて、ネットワークグラフ上に決定した初期経路内のスイッチで形成されるターンの通信量をそれぞれ計算する。
【０１２４】
決定部４５２は、計算部４５４により計算された各ターンの通信量の中から通信量が最も多いターンを一つ選択し、ネットワークグラフへ追加する。そして、上述した実施例２と同様に、ネットワークグラフにターンのループが形成されるか否かを判定する。
【０１２５】
［禁止ターン決定装置による処理（実施例３）］
続いて、図３７を参照しつつ、実施例３に係る禁止ターン決定装置による処理の流れを説明する。図３７は、実施例３に係る禁止ターン決定処理の流れを示す図である。なお、実施例３に係る禁止ターン決定装置による処理は、図３７に示すステップＳ７０３およびステップＳ７０４が、上述した実施例２に係る禁止ターン決定装置による処理と異なる。
【０１２６】
すなわち、計算部４５４は、生成部４５１により生成されたネットワークグラフ上に、スイッチ間を接続する各リンクの通信量ができるだけ分散するような通信ペア間の初期経路を決定し、初期経路で形成される各ターンの通信量を計算する（ステップＳ７０３）。
【０１２７】
続いて、決定部４５２は、計算部４５４により計算された各ターンの通信量の中から通信量が最も多いターンを一つ選択し、ネットワークグラフへ追加する（ステップＳ７０４）。以後のステップＳ７０５〜ステップＳ７０８の処理は、上述した実施例２に係る禁止ターン決定装置による処理、すなわち図３２に示すステップＳ６０４〜ステップＳ６０７と同様である。
【０１２８】
［実施例３による効果］
上述してきたように、実施例３に係る禁止ターン決定装置４００は、通信量が多いターンから順番に選択してネットワークグラフに追加することにより禁止ターンを決定する。このようなことから、実施例３によれば、より通信量の高いターンを許可ターン、通信量が少ないターンを禁止ターンにすることができ、結果的に、各リンクの通信量が効率的に分散されたルーティングを得ることができる。
【実施例４】
【０１２９】
上述した実施例３において、禁止ターンを決定するたびに通信経路を再計算するか否かを判定し、通信経路を再計算した場合には、再計算された通信経路について禁止ターンを決定するようにしてもよい。
【０１３０】
［禁止ターン決定装置の構成（実施例４）］
図３８は、実施例４に係る禁止ターン決定装置の構成を示す機能ブロック図である。図３８に示すように、禁止ターン決定装置４００は、判定部４５５を有する点が実施例３とは異なる。
【０１３１】
すなわち、判定部４５５は、決定部４５２により禁止ターンが決定された場合に、各通信経路を再計算するか否かを判定する。判定部４５５には、通信経路を再計算するか否かを判定するための条件として、例えば、以下の条件（１）〜（４）を予め設定されているものとする。
（１）常に再計算を行う。
（２）常に再計算を行わない。
（３）禁止ターンがｎ個決定されるたびに再計算を行う。
（４）禁止ターンの累積通信量が所定の閾値を超えた場合に再計算を行う。
【０１３２】
判定部４５５は、決定部４５２により禁止ターンが決定されると、予め設定された条件を参照する。そして、判定部４５５は、予め設定された条件に合致する場合には、通信経路を再計算するものと判定する。通信経路を再計算するものと判定した場合には、判定部４５５は、禁止ターンを避けた通信経路を再計算し、再計算した通信経路内に禁止あるいは許可の判定が行われていない未判定のターンが含まれるか否かを判定する。判定の結果、未判定のターンが含まれる場合には、判定部４５５は、再計算した通信経路内の各ターンの通信量を再計算するように計算部４５４に指示する。一方、未判定のターンが含まれていない場合には、通信経路は全て許可ターンで形成されていることとなるので、判定部４５５は、再計算した通信経路に含まれない未判定のターンを全て禁止ターンとして処理を終了する。
【０１３３】
［禁止ターン決定装置による処理（実施例４）］
続いて、図３９を参照しつつ、実施例４に係る禁止ターン決定装置による処理の流れを説明する。図３９は、実施例４に係る禁止ターン決定処理の流れを示す図である。なお、実施例４に係る禁止ターン決定装置による処理は、図３９に示すステップＳ８０８〜ステップＳ８１０が、上述した実施例２に係る禁止ターン決定装置による処理と異なる。
【０１３４】
すなわち、判定部４５５は、ステップＳ８０６において禁止ターンが決定された場合に、所定の条件に従って、通信経路を再計算するか否かを判定する（ステップＳ８０８）。判定の結果、通信経路を再計算するものと判定した場合には（ステップＳ８０８，Ｙｅｓ）、判定部４５５は、再計算した通信経路内に禁止あるいは許可の判定が行われていない未判定のターンが含まれるか否かを判定する（ステップＳ８０９）。判定の結果、未判定のターンが含まれる場合には（ステップＳ８０９，Ｙｅｓ）、計算部４５４に各ターンの通信量を再計算するように指示する。計算部４５４は、禁止ターンを考慮して、各ターンの通信量を再計算する（ステップＳ８１０）。一方、判定の結果、未判定のターンが含まれていない場合には（ステップＳ８０９，Ｎｏ）、判定部４５５は、再計算した通信経路に含まれない未判定のターンを全て禁止ターンとして処理を終了する。
【０１３５】
ここでステップＳ８０８の説明に戻る。判定の結果、通信経路を再計算しないものと判定した場合には（ステップＳ８０８，Ｎｏ）、判定部４５５は、ステップＳ８１１の処理に移行して、上述した実施例３に係る禁止ターン決定装置による処理と同様の処理を行う。すなわち、図３７に示すステップＳ７０８と同様に、ターンの追加が完了したか、言い換えれば、ネットワークに追加可能なターンが残っているか否かを判定する。
【０１３６】
［実施例４による効果］
上述してきたように、実施例４に係る禁止ターン決定装置４００は、禁止ターンを決定するたびに各ターンの通信量を再計算するか否かを判定し、各ターンの通信量を再計算した場合には、再計算された各ターンの通信量を用いて禁止ターンを決定する。このようなことから、実施例４によれば、各リンクの通信量が効率的に分散されるだけでなく、より適切なルーティングを得ることができる。
【実施例５】
【０１３７】
以下、本願の開示する禁止ターン決定プログラムおよび禁止ターン決定装置の他の実施形態を説明する。
【０１３８】
（１）装置構成等
例えば、上述した図１に示す禁止ターン決定装置３００、あるいは、上述した図２７、図３６、図３８に示す禁止ターン決定装置４００の構成は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。例えば、図１に示す禁止ターン決定装置３００の決定部３５３と算出部３５４とを機能的または物理的に統合してもよい。例えば、図２７に示す禁止ターン決定装置４００の決定部４５２と算出部４５３とを機能的または物理的に統合してもよい。このように、禁止ターン決定装置３００または禁止ターン決定装置４００の全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１３９】
（２）禁止ターン決定プログラム
また、上述の実施例にて説明した禁止ターン決定装置により実行される各種の処理は、例えば、あらかじめ用意されたプログラムをパーソナルコンピュータやサーバなどの電子機器で実行することによって実現することもできる。
【０１４０】
そこで、以下では、図４０を用いて、上述の実施例にて説明した禁止ターン決定装置により実行される処理と同様の機能を実現する禁止ターン決定プログラムを実行するコンピュータの一例を説明する。図４０は、禁止ターン決定プログラムを実行するコンピュータの一例を示す図である。
【０１４１】
図４０に示すように、禁止ターン決定装置により実行される各種処理を実現するコンピュータ５００は、各種演算処理を実行するＣＰＵ（Central  Processing  Unit）５１０を有する。また、図４０に示すように、コンピュータ５００は、例えば、ユーザから各種データの入力を受け付ける入力装置５２０、および各種データを出力する出力装置５３０を有する。
【０１４２】
なお、入力装置５２０は、例えば、キーボードやマウスなどに該当する。また、出力装置５３０は、モニタやディスプレイなどに該当する。なお、入力装置５２０がマウスを有する場合には、出力装置５３０が有するモニタと協働して、ポインティングデバイス機能を実現することもできる。また、入力装置５２０がタッチパッドなどの他の入力デバイスを有する場合にも、マウスの場合と同様にポインティングデバイス機能を実現できる。
【０１４３】
また、コンピュータ５００は、図４０に示すように、記憶媒体からプログラム等を読取る媒体読取装置５４０と、ネットワークを介して他のコンピュータとの間でデータの授受を行うネットワークインターフェース装置５５０を有する。また、コンピュータ５００は、図４０に示すように、各種情報を一時記憶するＲＡＭ（Random  Access  Memory）５６０と、ハードディスク装置５７０とを有する。そして、各装置５１０〜５７０は、バス５８０に接続される。
【０１４４】
なお、コンピュータ５００は、ＣＰＵ５１０の代わりに、ＭＰＵ（Micro  Processing  Unit）などの電子回路、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ(Field  Programmable  Gate  Array)などの集積回路を用いることもできる。また、コンピュータ５００は、ＲＡＭ５６０の代わりに、フラッシュメモリ(flash  memory)などの半導体メモリ素子を用いることもできる。
【０１４５】
ハードディスク装置５７０には、上述の実施例にて説明した禁止ターン決定装置の機能と同様の機能を発揮する禁止ターン決定プログラム５７１および禁止ターン決定用データ５７２が記憶されている。なお、この禁止ターン決定プログラム５７１を適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【０１４６】
そして、ＣＰＵ５１０が、禁止ターン決定プログラム５７１をハードディスク装置５７０から読み出してＲＡＭ５６０に展開することにより、図４０に示すように、禁止ターン決定プログラム５７１は禁止ターン決定プロセス５６１として機能する。禁止ターン決定プロセス５６１は、ハードディスク装置５７０から読み出した禁止ターン決定用データ５７２等の各種データを適宜メモリ５６０上の自身に割当てられた領域に展開し、この展開した各種データに基づいて各種処理を実行する。
【０１４７】
なお、禁止ターン決定プロセス５６１は、例えば、図１に示す禁止ターン決定装置３００の制御部３５０にて実行される処理、上述した図２２〜図２４に示す処理に該当する。また、例えば、図２７に示す禁止ターン決定装置４００の制御部４５０にて実行される処理、上述した図３２に示す処理に該当する。また、例えば、図３６示す禁止ターン決定装置４００の制御部４５０にて実行される処理、上述した図３７に示す処理に該当する。また、例えば、図３８に示す禁止ターン決定装置４００の制御部４５０にて実行される処理、上述した図３９に示す処理に該当する。
【０１４８】
なお、禁止ターン決定プログラム５７１については、必ずしも最初からハードディスク装置５７０に記憶させておく必要はない。例えば、コンピュータ５００が読み取り可能なフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ５００がこれらの媒体から各プログラムを読み出して実行するようにしてもよい。
【０１４９】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介して、コンピュータ５００が通信可能な「他のコンピュータ（またはサーバ）」などの装置に各プログラムを記憶させておく。そして、コンピュータ５００がこれらの装置から各プログラムを読み出して実行するようにしてもよい。
【０１５０】
上述してきた実施例では、外部からネットワーク１に接続可能な禁止ターン決定装置により、ネットワーク１に収容されるスイッチ１００間を接続する各リンクの通信量が分散されるように、禁止ターンを決定する場合を説明した。これに限定されるものではなく、例えば、ネットワーク１に収容されるスイッチ１００のいずれかに上述した禁止ターン決定プログラムを実装させ、このスイッチ１００を禁止ターン決定装置として機能させてもよい。
【符号の説明】
【０１５１】
１  ネットワーク
１００  スイッチ
２００  サーバ
３００  禁止ターン決定装置
３１０  入力部
３２０  出力部
３３０  ネットワークインターフェース
３４０  記憶部
３４１  ネットワーク情報記憶部
３５０  制御部
３５１  生成部
３５２  計算部
３５３  決定部
３５４  算出部
４００  禁止ターン決定装置
４１０  入力部
４２０  出力部
４３０  ネットワークインターフェース
４４０  記憶部
４４１  ネットワーク情報記憶部
４５０  制御部
４５１  生成部
４５２  決定部
４５３  算出部
４５４  計算部
４５５  判定部
５００  コンピュータ
５１０  ＣＰＵ
５２０  入力装置
５３０  出力装置
５４０  媒体読取装置
５５０  ネットワークインターフェース装置
５６０  ＲＡＭ
５６１  禁止ターン決定プロセス
５７０  ハードディスク装置
５７１  禁止ターン決定プログラム
５７２  禁止ターン決定用データ
【図１】
0005552938.tif 000002
【図２】
0005552938.tif 000003
【図３】
0005552938.tif 000004
【図４】
0005552938.tif 000005
【図５】
0005552938.tif 000006
【図６】
0005552938.tif 000007
【図７】
0005552938.tif 000008
【図８】
0005552938.tif 000009
【図９】
0005552938.tif 000010
【図１０】
0005552938.tif 000011
【図１１】
0005552938.tif 000012
【図１２】
0005552938.tif 000013
【図１３】
0005552938.tif 000014
【図１４】
0005552938.tif 000015
【図１５】
0005552938.tif 000016
【図１６】
0005552938.tif 000017
【図１７】
0005552938.tif 000018
【図１８】
0005552938.tif 000019
【図１９】
0005552938.tif 000020
【図２０】
0005552938.tif 000021
【図２１】
0005552938.tif 000022
【図２２】
0005552938.tif 000023
【図２３】
0005552938.tif 000024
【図２４】
0005552938.tif 000025
【図２５】
0005552938.tif 000026
【図２６】
0005552938.tif 000027
【図２７】
0005552938.tif 000028
【図２８】
0005552938.tif 000029
【図２９】
0005552938.tif 000030
【図３０】
0005552938.tif 000031
【図３１】
0005552938.tif 000032
【図３２】
0005552938.tif 000033
【図３３】
0005552938.tif 000034
【図３４】
0005552938.tif 000035
【図３５】
0005552938.tif 000036
【図３６】
0005552938.tif 000037
【図３７】
0005552938.tif 000038
【図３８】
0005552938.tif 000039
【図３９】
0005552938.tif 000040
【図４０】
0005552938.tif 000041
【図４１】
0005552938.tif 000042
【図４２】
0005552938.tif 000043
【図４３】
0005552938.tif 000044
【図４４】
0005552938.tif 000045
【図４５】
0005552938.tif 000046
【図４６】
0005552938.tif 000047
【図４７】
0005552938.tif 000048
【図４８】
0005552938.tif 000049
【図４９】
0005552938.tif 000050