(57)【要約】【課題】  平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性に優れたネットワーク構造を有するデータ転送ネットワークを提供する。【解決手段】  ある平均中継数性能Ｈに、そのＨ以下の中での最大のネットワーク帯域性能Ｘｅｆｆを対応付け、このような対応付けを、平均中継数性能Ｈが取り得る範囲に結んだものをＨ−Ｘｅｆｆ限界性能という。Ｈ−Ｘｅｆｆ限界性能近傍は、中継数性能もネットワーク帯域性能も良好なものである。Ｈ−Ｘｅｆｆ限界性能近傍のどのようなネットワーク構造でも、コア・エッジ分離構造という構造をとる。コア・エッジ分離構造は、次数１のノードは必ず次数３以上のコアノードと繋がり、一次縮約したネットワークには連結数が１のリンクがない。本発明のデータ転送ネットワークは、コア・エッジ分離構造を適用している。【選択図】      図１０
2011114795.tif 000002
【特許請求の範囲】
【請求項１】
ノード数をＮ、リンク数をＬとしたとき、Ｎ＞１０、Ｎ＜Ｌ＜３Ｎの関係を満足する、３次正則グラフ、４次正則グラフ、５次正則グラフ、二部グラフの構造以外の構造を有する連結されたデータ転送ネットワークにおいて、
以下の条件Ｃ１、Ｃ２及びＣ３の全てを充足していることを特徴とするデータ転送ネットワーク。
（条件Ｃ１）当該ネットワークにおいて、次数１となるノードは、必ず次数３以上のコアノードに連結していて、次数２以下のノードとは連結していない。
（条件Ｃ２）当該ネットワークを一次縮約させたネットワークにおいて、コアノード数Ｎｃｏｒｅは２≦Ｎｃｏｒｅ≦Ｎとなる整数で、一次縮約ネットワークでのＮｃｏｒｅ個のコアノードの平均値Ｋｃｏｒｅの回りの平均相対偏差ｄｋｃｏｒｅがｄｋｃｏｒｅ＜０．６となっている。
（条件Ｃ３）当該ネットワークの平均中継数性能値Ｈとネットワーク帯域性能値Ｘｅｆｆが、平均リンク率をｐ、平均ノード次数をｋ、ｋをノード次数とする仮想的なｃａｇｅグラフ構造のネットワークにおけるｃａｇｅ限界ネットワーク帯域性能値をｃａｇｅＸｅｆｆとしたとき、（Ａ）式の関係を満たすものとなっている。
Ｘｅｆｆ＞（ｃａｇｅＸｅｆｆ／Ｎ−１）（Ｈ＋ｐ−２）
／｛２（１／ｃａｇｅＸｅｆｆ＋ｐ−３）｝＋１      …（Ａ）
【請求項２】
請求項１に記載のデータ転送ネットワークにおいて、
以下の条件Ｃ４を充足していることを特徴とするデータ転送ネットワーク。
（条件Ｃ４）コアノード数Ｎｃｏｒｅが２（Ｌ−Ｎ）の約数となっている。
【請求項３】
請求項１又は２に記載のデータ転送ネットワークにおいて、
以下の条件Ｃ５を充足していることを特徴とするデータ転送ネットワーク。
（条件Ｃ５）コアノード数Ｎｃｏｒｅが、平均ノード次数を有する仮想的なｃａｇｅ構造における最外殻層数ｈｓｈｅｌｌに対する閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）となっている。
【請求項４】
請求項１〜３のいずれかに記載のデータ転送ネットワークにおいて、
以下の条件Ｃ６を充足していることを特徴とするデータ転送ネットワーク。
（条件Ｃ６）０≦Ｓ≦ｍａｘ（０，Ｎ−Ｎｃｏｒｅ−Ｄｍａｘ）の範囲にあるＳが当該ネットワークにおける次数が１となるノードの数となり、かつ、Ｄ＝Ｎ−Ｎｃｏｒｅ−Ｓより求められるＤが当該ネットワークにおける次数が２となるノードの数となっている。
（但し、Ｄｍａｘは、Ｎｃｏｒｅ｛２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２−Ｘ｝／２を超えない最大の整数である）
【請求項５】
請求項１〜４のいずれかに記載のデータ転送ネットワークにおいて、
以下の条件Ｃ７を充足していることを特徴とするデータ転送ネットワーク。
（条件Ｃ７）当該ネットワークにおけるＳ個の次数１のノードを一次縮約ネットワークにおけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個の次数１のノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるという理想的な分配方法を適用したと仮定した場合の結果に、当該ネットワークにおける次数１のノードとコアノードとの繋がり方が一致している。又は、当該ネットワークにおけるＳ個の次数１のノードを一次縮約ネットワークにおけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個の次数１のノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるというように一旦分配した後、低次のコアノードに繋がっている次数１のノードのうちの一部若しくは全てをより高次のコアノードへ移動する分配方法を適用したと仮定した場合の結果に、当該ネットワークにおける次数１のノードとコアノードとの繋がり方が一致している。
【請求項６】
ノード数をＮ、リンク数をＬとしたとき、Ｎ＞１０、Ｎ＜Ｌ＜３Ｎの関係を満足する、３次正則グラフ、４次正則グラフ、５次正則グラフ、二部グラフの構造以外の構造を有する連結されたデータ転送ネットワークの構成方法において、
条件Ｃ１〜Ｃ７のうち、条件Ｃ１〜Ｃ３を含む３以上の条件を充足するようにデータ転送ネットワークを構成したことを特徴とするデータ転送ネットワークの構成方法。
（条件Ｃ１）当該ネットワークにおいて、次数１となるノードは、必ず次数３以上のコアノードに連結していて、次数２以下のノードとは連結していない。
（条件Ｃ２）当該ネットワークを一次縮約させたネットワークにおいて、コアノード数Ｎｃｏｒｅは２≦Ｎｃｏｒｅ≦Ｎとなる整数で、一次縮約ネットワークでのＮｃｏｒｅ個のコアノードの平均値Ｋｃｏｒｅの回りの平均相対偏差ｄｋｃｏｒｅがｄｋｃｏｒｅ＜０．６となっている。
（条件Ｃ３）当該ネットワークの平均中継数性能値Ｈとネットワーク帯域性能値Ｘｅｆｆが、平均リンク率をｐ、平均ノード次数をｋ、ｋをノード次数とする仮想的なｃａｇｅグラフ構造のネットワークにおけるｃａｇｅ限界ネットワーク帯域性能値をｃａｇｅＸｅｆｆとしたとき、（Ａ）式の関係を満たすものとなっている。
Ｘｅｆｆ＞（ｃａｇｅＸｅｆｆ／Ｎ−１）（Ｈ＋ｐ−２）
／｛２（１／ｃａｇｅＸｅｆｆ＋ｐ−３）｝＋１      …（Ａ）
（条件Ｃ４）コアノード数Ｎｃｏｒｅが２（Ｌ−Ｎ）の約数となっている。
（条件Ｃ５）コアノード数Ｎｃｏｒｅが、平均ノード次数を有する仮想的なｃａｇｅ構造における最外殻層数ｈｓｈｅｌｌに対する閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）となっている。
（条件Ｃ６）０≦Ｓ≦ｍａｘ（０，Ｎ−Ｎｃｏｒｅ−Ｄｍａｘ）の範囲にあるＳが当該ネットワークにおける次数が１となるノードの数となり、かつ、Ｄ＝Ｎ−Ｎｃｏｒｅ−Ｓより求められるＤが当該ネットワークにおける次数が２となるノードの数となっている。
（但し、Ｄｍａｘは、Ｎｃｏｒｅ｛２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２−Ｘ｝／２を超えない最大の整数である）
（条件Ｃ７）当該ネットワークにおけるＳ個の次数１のノードを一次縮約ネットワークにおけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個の次数１のノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるという理想的な分配方法を適用したと仮定した場合の結果に、当該ネットワークにおける次数１のノードとコアノードとの繋がり方が一致している。又は、当該ネットワークにおけるＳ個の次数１のノードを一次縮約ネットワークにおけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個の次数１のノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるというように一旦分配した後、低次のコアノードに繋がっている次数１のノードのうちの一部若しくは全てをより高次のコアノードへ移動する分配方法を適用したと仮定した場合の結果に、当該ネットワークにおける次数１のノードとコアノードとの繋がり方が一致している。
【請求項７】
請求項６に記載のデータ転送ネットワークにおいて、
条件Ｃ１〜Ｃ７のうち、条件Ｃ１〜Ｃ３を含む３以上の条件を充足するデータ転送ネットワークを複数候補として構成し、構成された複数の候補の中から、ネットワーク帯域性能及び平均中継数性能の少なくとも一方に基づいた評価値が高いものを選択することを特徴とするデータ転送ネットワークの構成方法。
【請求項８】
請求項６に記載のデータ転送ネットワークにおいて、
条件Ｃ１〜Ｃ７のうち、条件Ｃ１〜Ｃ３を含む３以上の条件を充足するデータ転送ネットワークを仮候補として構成し、
仮候補に対し、乱数を適用してリンクの移動若しくは張り替えを実行すると共に、移動若しくは張り替え後のネットワーク構造を、ネットワーク帯域性能及び平均中継数性能の少なくとも一方に基づいて評価し、仮候補を最適化して最終的なネットワーク構造を決定することを特徴とするデータ転送ネットワークの構成方法。
【請求項９】
請求項６に記載のデータ転送ネットワークにおいて、
条件Ｃ１〜Ｃ７のうち、条件Ｃ１〜Ｃ３を含む３以上の条件を充足するデータ転送ネットワークを複数、遺伝子サンプルとして構成し、構成された遺伝子サンプルに対し、ネットワーク帯域性能及び平均中継数性能の少なくとも一方に基づいた評価値を用いた遺伝的アルゴリズムを適用して、最終的なネットワーク構造を決定することを特徴とするデータ転送ネットワークの構成方法。
【請求項１０】
ノード数をＮ、リンク数をＬとしたとき、Ｎ＞１０、Ｎ＜Ｌ＜３Ｎの関係を満足する連結された評価対象のデータ転送ネットワークを評価するデータ転送ネットワークの評価方法であって、
条件Ｃ１〜Ｃ７のうち、条件Ｃ１〜Ｃ３を含む３以上の条件の充足性に基づいて、評価結果を定めることを特徴とするデータ転送ネットワークの評価方法。
（条件Ｃ１）当該ネットワークにおいて、次数１となるノードは、必ず次数３以上のコアノードに連結していて、次数２以下のノードとは連結していない。
（条件Ｃ２）当該ネットワークを一次縮約させたネットワークにおいて、コアノード数Ｎｃｏｒｅは２≦Ｎｃｏｒｅ≦Ｎとなる整数で、一次縮約ネットワークでのＮｃｏｒｅ個のコアノードの平均値Ｋｃｏｒｅの回りの平均相対偏差ｄｋｃｏｒｅがｄｋｃｏｒｅ＜０．６となっている。
（条件Ｃ３）当該ネットワークの平均中継数性能値Ｈとネットワーク帯域性能値Ｘｅｆｆが、平均リンク率をｐ、平均ノード次数をｋ、ｋをノード次数とする仮想的なｃａｇｅグラフ構造のネットワークにおけるｃａｇｅ限界ネットワーク帯域性能値をｃａｇｅＸｅｆｆとしたとき、（Ａ）式の関係を満たすものとなっている。
Ｘｅｆｆ＞（ｃａｇｅＸｅｆｆ／Ｎ−１）（Ｈ＋ｐ−２）
／｛２（１／ｃａｇｅＸｅｆｆ＋ｐ−３）｝＋１      …（Ａ）
（条件Ｃ４）コアノード数Ｎｃｏｒｅが２（Ｌ−Ｎ）の約数となっている。
（条件Ｃ５）コアノード数Ｎｃｏｒｅが、平均ノード次数を有する仮想的なｃａｇｅ構造における最外殻層数ｈｓｈｅｌｌに対する閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）となっている。
（条件Ｃ６）０≦Ｓ≦ｍａｘ（０，Ｎ−Ｎｃｏｒｅ−Ｄｍａｘ）の範囲にあるＳが当該ネットワークにおける次数が１となるノードの数となり、かつ、Ｄ＝Ｎ−Ｎｃｏｒｅ−Ｓより求められるＤが当該ネットワークにおける次数が２となるノードの数となっている。
（但し、Ｄｍａｘは、Ｎｃｏｒｅ｛２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２−Ｘ｝／２を超えない最大の整数である）
（条件Ｃ７）当該ネットワークにおけるＳ個の次数１のノードを一次縮約ネットワークにおけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個の次数１のノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるという理想的な分配方法を適用したと仮定した場合の結果に、当該ネットワークにおける次数１のノードとコアノードとの繋がり方が一致している。又は、当該ネットワークにおけるＳ個の次数１のノードを一次縮約ネットワークにおけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個の次数１のノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるというように一旦分配した後、低次のコアノードに繋がっている次数１のノードのうちの一部若しくは全てをより高次のコアノードへ移動する分配方法を適用したと仮定した場合の結果に、当該ネットワークにおける次数１のノードとコアノードとの繋がり方が一致している。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ転送ネットワーク、データ転送ネットワークの構成方法法及びデータ転送ネットワークの評価方法に関する。
【背景技術】
【０００２】
複数のノードをリンクによって接続したデータ転送ネットワークは、例えば、一般のインターネットネットワーク、公衆通信網、企業内通信網、ＬＡＮ、コンピュータ網、分散コンピュータ網、分散ルータ網、交換機網、ルータや各種装置内部等で使用される各種スイッチ綱、ＣＰＵやメモリをつなぐデータ通信網、ＣＰＵなどのＬＳＩ内部でのデータ通信網など、今日では多く用いられている。
【０００３】
複数のノードを結合し、ノード処理を分散させる従来のデータ転送ネットワークの構成方式としては、（ア）バスネットワーク、（イ）リングネットワーク、（ウ）ハブネットワーク（スター状ネットワーク）、（エ）完全メッシュネットワーク、（オ）バス及びリングのハイパー拡張（ハイパーキューブ）ネットワークなどのさまざまな規則的なネットワーク構成方法があった。
【０００４】
また、実際に情報通信系ネットワークとして使用されているネットワークの中では、インターネットのネットワーク構造のように複雑系ネットワークと呼ばれるネットワーク構造になっているものがある。
【０００５】
さらに、実用的にはあまり使用されていないが、学術的な観点で、ランダムネットワーク、一般化ランダムネットワークなどがネットワークの構造として盛んに研究されてきた。
【０００６】
これらの様々な形状・構造・構成法（以下、形状・構造・構成法をまとめて単に「構造」と呼ぶ）をとるネットワークは、仮に、同じ性能で同じ数のノードと同じ性能で同じ数のリンクを用いたとしても、その構造の違いにより、ネットワーク全体で処理できるトラフィック総量に違いが生じ、また、同時に平均中継数（平均ホップ数）に関しても違いが生じる（非特許文献１の第２節のシミュレーション結果参照）。
【０００７】
今後、コンピュータＩＴネットワークなどで見られるように、端末数が巨大で、端末速度が現状よりも一段と高速になるデータ転送ネットワークが多数出現する。このような巨大、高速なネットワークについては、ネットワーク全体でトラフィック収容能力を上げると共にネットワーク内の中継数を下げることが重要であり、そのため、ネットワーク構造の最適化・効率化が重要となる。
【０００８】
一般に、同じノード数でリンク数だけを増やしていくと、ネットワーク全体で処理できるトラフィック総量が増えて、平均ホップ数も減るが、リンクに対するコストが増える。そのため、コスト的に最適なノード数と最適なリンク数が存在し、そのような最適なノード数と最適なリンク数を適用したデータ転送ネットワークの中にも、最適なトラフィック総量値と最適な平均ホップ数を達成するものが存在するはずである。
【０００９】
また、ノード数とリンク数が与えられたとき、この条件を満たす最大のトラフィック量ｍａｘＸｅｆｆを示すネットワーク構造が存在する。最大トラフィック量ｍａｘＸｅｆｆを示すネットワークの平均ホップ数（以下、最大ＮＷ平均ホップ数と呼ぶ）ｍａｘＨは比較的大きく、最大トラフィック量ｍａｘＸｅｆｆをとるからと言って、必ずしも実用的には優れているとは限らない。実用的には、与えられたノード数とリンク数を持ったネットワークの中で、平均ホップ数が最大ＮＷ平均ホップ数ｍａｘＨ以下という条件下で、最大のトラフィック量を示すネットワーク構造を明らかにすることが望まれる。
【００１０】
平均ホップ数がＨ以下で最大のトラフィック総量を示すとき、その最大トラフィック総量をＸ（Ｈ）と書くこととし、ＨとＸ（Ｈ）との関係をＨ−Ｘｅｆｆ限界性能と呼ぶこととする。この場合、Ｘ（ｍａｘＨ）＝ｍａｘＸｅｆｆとなる。また、非特許文献２には、ノード数がＮでリンク数がＬとなるネットワークにおいて、最小の平均ホップ数ｍｉｎＨは、ｍｉｎＨ＝２−２＊Ｌ／Ｎ／（Ｎ−１）となることが示されている。今、Ｘ（ｍｉｎＨ）＝ｍｉｎＸｅｆｆとする。
【００１１】
Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）は、横軸にホップ数（平均中継数性能）Ｈ、縦軸にトラフィック量（ネットワーク帯域性能）Ｘｅｆｆをとった２次元座標系に、各ネットワーク構造での平均ホップ数及びトラフィック量に応じてプロットした場合に、（ｍｉｎＨ，ｍｉｎＸｅｆｆ）から（ｍａｘＨ，ｍａｘＸｅｆｆ）に（階段状に）単調増加する関数（ステップファンクション）となっている。
【００１２】
図１８に、Ｎ＝５０、Ｌ＝７５のネットワークを例に、ネットワーク帯域性能Ｘｅｆｆと平均中継数性能Ｈの分布を示している。図１８は、Ｎ＝５０、Ｌ＝７５のあるネットワークについて得たネットワーク帯域性能Ｘｅｆｆと平均中継数性能Ｈとをプロットし、このようなプロットを、Ｎ＝５０、Ｌ＝７５の多数の異なるネットワークについて行ったものである。
【００１３】
図１８において、点ＰＭが（ｍａｘＨ，ｍａｘＸｅｆｆ）の点を表し、点ＰＬが（ｍｉｎＨ，ｍｉｎＸｅｆｆ）の点を表している。（ｍｉｎＨ，ｍｉｎＸｅｆｆ）の点ＰＬから最大点（ｍａｘＨ，ｍａｘＸｅｆｆ）の点までの分布の左端の境界を階段状にしたものが、Ｈ−Ｘｃｆｆ限界性能Ｘ（Ｈ）を表している。
【００１４】
同一の平均中継数性能Ｈをとる複数のネットワークの中では、ネットワーク帯域性能Ｘｅｆｆが最も良いネットワークが好適である。相前後する２つの平均中継数性能Ｈ１、Ｈ２で、大きい方の平均中継数性能Ｈ２におけるネットワーク帯域性能Ｘｅｆｆ２の方が、小さい方の平均中継数性能Ｈ１におけるネットワーク帯域性能Ｘｅｆｆ１より悪いならば、（ｍａｘ１，Ｘｅｆｆ１）のネットワークの方が好適である。このように見た場合、平均中継数性能がｍａｘＨより大きいネットワークに好適なネットワークは存在しない。また、（ｍｉｎＨ，ｍｉｎＸｅｆｆ）から（ｍａｘＨ，ｍａｘＸｅｆｆ）に（階段状に）単調増加するＨ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上に、好適なネットワークが存在する。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】第５回ネットワーク生態学シンポジウム、社団法人情報処理学会ネットワーク生態学研究グループ主催、川原正人、今中規景、伊達正晃、中平佳裕、中井敏久発表、発表用文書「複雑ネットワークとしてのインターネットとそのネットワーク帯域性能」、２００９年３月
【非特許文献２】社団法人電子情報通信学会「複雑系ネットワーク時限研究会発表、発表者川原正人、発表用文書「ネットワーク構造とネットワーク性能−規則的大規模構造、ランダムネットワーク、スケールフリーネットワーク−」、２００７年４月
【発明の開示】
【発明が解決しようとする課題】
【００１６】
実際、Ｎ個のノードをどのように繋げれば、より経済的・省エネ的で大容量・高速のネットワークを構築することができるかという問題は、重要な問題である。
【００１７】
ネットワークの経済性・省エネ性を上げるためには、与えられたノード数Ｎに対して、なるべく少ないリンク数Ｌで平均ホップ数Ｈを小さくしなければならない。平均ホップ数Ｈを下げることによりネットワークの高速性も上がる。同時に、大容量性を上げるためには、ネットワーク構造を、平均ホップ数Ｈで決まる限界性能Ｘ（Ｈ）をもつネットワーク構造にすれば良い。
【００１８】
しかし、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造を、種々の最適化方法を用いて導き出すことは不可能ではないが、かなり時間を要する。実際には、種々の既存制約条件の下で構造を全て決めることは困難である。
【００１９】
そのため、厳密にＨ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造にならなくとも、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造がもつネットワーク帯域性能と平均中継数性能に近い性能を示すネットワーク構造を簡単に導き出すことができれば、実用上非常に有効となる。
【００２０】
本発明は、以上の点に鑑みてなされたものであり、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造が有するネットワーク帯域性能と平均中継数性能に近い性能を示す、そのことを容易に確認できたデータ転送ネットワークを提供しようとしたものである。
【００２１】
また、本発明は、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造が有するネットワーク帯域性能と平均中継数性能に近い性能を示すことを保証し得るデータ転送ネットワークの構成方法を提供しようとしたものである。
【００２２】
さらに、本発明は、評価対象のデータ転送ネットワークが、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造が有するネットワーク帯域性能と平均中継数性能に近い性能を示すか否かを評価し得るデータ転送ネットワークの評価方法を提供しようとしたものである。
【００２３】
なお、３次正則グラフ、４次正則グラフ、５次正則グラフ、二部グラフなどの構造を有するネットワーク構造は、検討するまでもなく、効率的なネットワーク構造になっていることは周知であり、本発明では対象外としている。
【課題を解決するための手段】
【００２４】
第１の本発明は、ノード数をＮ、リンク数をＬとしたとき、Ｎ＞１０、Ｎ＜Ｌ＜３Ｎの関係を満足する、３次正則グラフ、４次正則グラフ、５次正則グラフ、二部グラフの構造以外の構造を有する連結されたデータ転送ネットワークにおいて、以下の条件Ｃ１、Ｃ２及びＣ３の全てを充足していることを特徴とする。
【００２５】
第２の本発明は、ノード数をＮ、リンク数をＬとしたとき、Ｎ＞１０、Ｎ＜Ｌ＜３Ｎの関係を満足する、３次正則グラフ、４次正則グラフ、５次正則グラフ、二部グラフの構造以外の構造を有する連結されたデータ転送ネットワークの構成方法において、条件Ｃ１〜Ｃ７のうち、条件Ｃ１〜Ｃ３を含む３以上の条件を充足するようにデータ転送ネットワークを構成したことを特徴とする。
【００２６】
第３の本発明は、ノード数をＮ、リンク数をＬとしたとき、Ｎ＞１０、Ｎ＜Ｌ＜３Ｎの関係を満足する連結された評価対象のデータ転送ネットワークを評価するデータ転送ネットワークの評価方法であって、条件Ｃ１〜Ｃ７のうち、条件Ｃ１〜Ｃ３を含む３以上の条件の充足性に基づいて、評価結果を定めることを特徴とする。
【００２７】
（条件Ｃ１）当該ネットワークにおいて、次数１となるノードは、必ず次数３以上のコアノードに連結していて、次数２以下のノードとは連結していない。
【００２８】
（条件Ｃ２）当該ネットワークを一次縮約させたネットワークにおいて、コアノード数Ｎｃｏｒｅは２≦Ｎｃｏｒｅ≦Ｎとなる整数で、一次縮約ネットワークでのＮｃｏｒｅ個のコアノードの平均値Ｋｃｏｒｅの回りの平均相対偏差ｄｋｃｏｒｅがｄｋｃｏｒｅ＜０．６となっている。
【００２９】
（条件Ｃ３）当該ネットワークの平均中継数性能値Ｈとネットワーク帯域性能値Ｘｅｆｆが、平均リンク率をｐ、平均ノード次数をｋ、ｋをノード次数とする仮想的なｃａｇｅグラフ構造のネットワークにおけるｃａｇｅ限界ネットワーク帯域性能値をｃａｇｅＸｅｆｆとしたとき、（Ａ）式の関係を満たすものとなっている。
【００３０】
Ｘｅｆｆ＞（ｃａｇｅＸｅｆｆ／Ｎ−１）（Ｈ＋ｐ−２）
／｛２（１／ｃａｇｅＸｅｆｆ＋ｐ−３）｝＋１      …（Ａ）
（条件Ｃ４）コアノード数Ｎｃｏｒｅが２（Ｌ−Ｎ）の約数となっている。
【００３１】
（条件Ｃ５）コアノード数Ｎｃｏｒｅが、平均ノード次数を有する仮想的なｃａｇｅ構造における最外殻層数ｈｓｈｅｌｌに対する閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）となっている。
【００３２】
（条件Ｃ６）０≦Ｓ≦ｍａｘ（０，Ｎ−Ｎｃｏｒｅ−Ｄｍａｘ）の範囲にあるＳが当該ネットワークにおける次数が１となるノードの数となり、かつ、Ｄ＝Ｎ−Ｎｃｏｒｅ−Ｓより求められるＤが当該ネットワークにおける次数が２となるノードの数となっている。
【００３３】
（但し、Ｄｍａｘは、Ｎｃｏｒｅ｛２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２−Ｘ｝／２を超えない最大の整数である）
（条件Ｃ７）当該ネットワークにおけるＳ個の次数１のノードを一次縮約ネットワークにおけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個の次数１のノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるという理想的な分配方法を適用したと仮定した場合の結果に、当該ネットワークにおける次数１のノードとコアノードとの繋がり方が一致している。又は、当該ネットワークにおけるＳ個の次数１のノードを一次縮約ネットワークにおけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個の次数１のノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるというように一旦分配した後、低次のコアノードに繋がっている次数１のノードのうちの一部若しくは全てをより高次のコアノードへ移動する分配方法を適用したと仮定した場合の結果に、当該ネットワークにおける次数１のノードとコアノードとの繋がり方が一致している。
【発明の効果】
【００３４】
第１の本発明によれば、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造が有するネットワーク帯域性能と平均中継数性能に近い性能を示すデータ転送ネットワークを提供できる。
【００３５】
また、第２の本発明によれば、当該構成方法で構成したデータ転送ネットワークが、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造が有するネットワーク帯域性能と平均中継数性能に近い性能を示すことを保証することができる。
【００３６】
さらに、第３の本発明によれば、評価対象のデータ転送ネットワークが、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造が有するネットワーク帯域性能と平均中継数性能に近い性能を示すか否かを評価することができる。
【図面の簡単な説明】
【００３７】
【図１】ノード次数が３のツリー構造のネットワーク構造を示す説明図である。
【図２】ノード数Ｎ＝５０、リンク数Ｌ＝７５における種々のネットワークを３種類に分け、各種類のネットワークの平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性の分布を示す説明図である。
【図３】条件Ｃ１を満たす平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性の分布と、条件Ｃ１を満たさない平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性の分布とを示す説明図である。
【図４】ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワーク中、ネットワーク帯域性能ＸｅｆｆがＨ−Ｘｅｆｆ限界性能値から劣ること１未満の限界性能値近傍のネットワークの、一次縮約ネットワークでのコアノード次数平均値Ｋｃｏｒｅの回りの、平均相対偏差ｄｋｃｏｒｅの出現頻度を示す説明図である。
【図５】平均相対偏差ｄｋｃｏｒｅを４つの領域に分けた場合における、それぞれの領域に含まれた、ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークの平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を示す説明図である。
【図６】ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークにおいて、コアノード数Ｎｃｏｒｅが、条件Ｃ４又はＣ５を満たすことで、平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性で突出した特性を示していることを示す説明図である。
【図７】ノード数Ｎ＝５０で、平均ノード次数ｋが３から９まで、リンク数を変化させたときの、（ｍａｘＨ，ｍａｘＸｅｆｆ）の変化の様子を示している。
【図８】Ｄエッジノードがトラフィック中継に携わることがほんの僅かしかない理由の説明図である。
【図９】コアノードへのＳエッジノードの配分数と、平均中継数性能Ｈ及びネットワーク帯域性能Ｘｅｆｆの平均値の分布を示す説明図である。
【図１０】条件Ｃ１〜Ｃ７の全てを満足する、ノード数Ｎ＝５０、リンク数Ｌ＝７５のデータ転送ネットワークの一実施例におけるネットワーク構造を示す説明図である。
【図１１】ノード数Ｎ＝３００００、リンク数Ｌ＝６１５００のネットワーク構造例を模式的に示す説明図である。
【図１２】条件Ｃ１〜Ｃ７を備えたネットワークがそれぞれ示す平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性のコアノード数ごとの分布を示す説明図である。
【図１３】データ転送ネットワークの構成方法の第１の実施形態である単純試行法の処理の流れを示すフローチャートである。
【図１４】データ転送ネットワークの構成方法の第２の実施形態である試行選択法の処理の流れを示すフローチャートである。
【図１５】データ転送ネットワークの構成方法の第３の実施形態であるランダムリンク張り替え法の処理の流れを示すフローチャートである。
【図１６】データ転送ネットワークの構成方法の第４の実施形態であるＧＡ最適化法の処理の流れを示すフローチャートである。
【図１７】データ転送ネットワークの評価方法における処理の流れを示すフローチャートである。
【図１８】ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークについて、ネットワーク帯域性能Ｘｅｆｆと平均中継数性能Ｈの分布を示す説明図である。
【発明を実施するための形態】
【００３８】
（Ａ）データ転送ネットワークの実施形態
以下、本発明によるデータ転送ネットワークの一実施形態を、図面を参照しながら詳述する。
【００３９】
この実施形態のデータ転送ネットワークは、連結されたネットワークであって、そのノード数をＮ、リンク数をＬとするとき、Ｎ＞１０、Ｎ＜Ｌ＜３Ｎ、４Ｌ２＜Ｎ３の関係を満たし、３次正則グラフ、４次正則グラフ、５次正則グラフ、二部グラフのネットワーク構造以外のネットワーク構造を有し、以下の条件（Ｃ１）〜（Ｃ７）を満たすものである。
【００４０】
（Ｃ１）ネットワークＮＷにおいて、次数１となるノードは、必ず次数３以上のノードに連結していて、次数２以下のノードとは連結していない。
【００４１】
（Ｃ２）ネットワークＮＷを一次縮約させたネットワークＮＷ＊において、コアノード数Ｎｃｏｒｅは２≦Ｎｃｏｒｅ≦Ｎとなる整数で、Ｎｃｏｒｅ個のコアノードの一次縮約ネットワークＮＷ＊での平均値Ｋｃｏｒｅの回りの平均相対偏差ｄｋｃｏｒｅがｄｋｃｏｒｅ＜０．６となっている。
【００４２】
（Ｃ３）ネットワークＮＷの平均中継数性能値Ｈとネットワーク帯域性能値Ｘｅｆｆが、平均リンク率をｐ、平均ノード次数をｋ、ｋをノード次数とする仮想的なｃａｇｅグラフ構造のネットワークにおけるｃａｇｅ限界ネットワーク帯域性能値をｃａｇｅＸｅｆｆとしたとき、（１）式の関係を満たすものとなっている。
【００４３】
Ｘｅｆｆ＞（ｃａｇｅＸｅｆｆ／Ｎ−１）（Ｈ＋ｐ−２）
／｛２（１／ｃａｇｅＸｅｆｆ＋ｐ−３）｝＋１      …（１）
（Ｃ４）コアノード数Ｎｃｏｒｅが２（Ｌ−Ｎ）の約数となっている。
【００４４】
（Ｃ５）コアノード数Ｎｃｏｒｅが、最外殻層数ｈｓｈｅｌｌに対する閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）となっている。
【００４５】
（Ｃ６）０≦Ｓ≦ｍａｘ（０，Ｎ−Ｎｃｏｒｅ−Ｄｍａｘ）の範囲にあるＳがネットワークＮＷにおけるノード次数ｋが１となるノードの数となり、かつ、Ｄ＝Ｎ−Ｎｃｏｒｅ−Ｓより求められるＤがネットワークＮＷにおけるノード次数ｋが２となるノードの数となっている。
【００４６】
（Ｃ７）ネットワークＮＷにおけるＳ個のＳエッジノードを一次縮約ネットワークＮＷ＊におけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個のＳエッジノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるという理想的な分配方法を適用したと仮定した場合の結果に、ネットワークＮＷにおけるＳエッジノードとコアノードとの繋がり方が一致している。又は、ネットワークＮＷにおけるＳ個のＳエッジノードを一次縮約ネットワークＮＷ＊におけるＮｃｏｒｅ個のコアノードに分配すると仮定し、その分配方法として、Ｓ個のＳエッジノードを分配した後のコアノードの次数分布のバラツキが最も小さくなるというように一旦分配した後、低次のコアノードに繋がっているＳエッジノードのうちの一部若しくは全てをより高次のコアノードへ移動する分配方法を適用したと仮定した場合の結果に、ネットワークＮＷにおけるＳエッジノードとコアノードとの繋がり方が一致している。
【００４７】
実施形態のデータ転送ネットワークは、条件Ｃ１〜Ｃ７の全てを充足するものであるが、変形例としては、条件Ｃ１〜Ｃ３だけを満たすもの、条件Ｃ１〜Ｃ３と条件Ｃ４〜Ｃ７のうちの１以上の条件（条件Ｃ１〜Ｃ７の全ての場合を除く）を満たすものを挙げることができる。
【００４８】
Ｎ＞１０を満たすことを前提としたのは、ノード数Ｎがある程度多い大規模なネットワーク構造を対象としようとしたためである。また、Ｎ＜Ｌ＜３Ｎ、４Ｌ２＜Ｎ３の関係を満たすことを前提としたのは、ノード数Ｎに対して少ないリンク数Ｌのネットワーク構造で、効率的なデータ転送ネットワークを定めようとしたためである。なお、ノード数Ｎに対して少ないリンク数Ｌのネットワーク構造を、Ｎ＜Ｌ＜３Ｎの関係だけで規定するようにしても良い。
【００４９】
（Ａ−１）条件Ｃ１〜Ｃ３について
（Ａ−１−１）用語、パラメータの定義
まず、各用語や各パラメータの定義を説明する。
【００５０】
今、ノード数がＮでリンク数がＬとなるネットワークＮＷを考える。ノードにつながるリンクの数を、そのノードの「ノード次数」又は単に「次数」という。
【００５１】
ノード次数が１となるノードをＳエッジノードと呼び、Ｓエッジノードの数をＳと表し、また、ノード次数が２となるノードをＤエッジノードと呼び、Ｄエッジノードの数をＤと表す。ノード次数が３以上のノードをコアノードと呼び、コアノードのノード数をＮｃｏｒｅと表す。このとき、Ｎ＝Ｓ＋Ｄ＋Ｎｃｏｒｅの関係が成り立っている。
【００５２】
ノード次数が３以上のノードをコアノードとして重要するのは、以下の理由による。ノード次数が１となるノードへの経路は、そのノードが直接接続されているノードまでの経路が定まれば一意に決まり、直接接続されているノードとの間で経路の選択の余地がなく、経路の選択性に関し、ノード次数が３以上のノードより重要性が劣るためである。後述する一次縮約ネットワークＮＷ＊を導入しているのも、同様な理由による。また、ノード次数が２となるノードは、トラフィックの入出力ポートが２つであって、一方の入出力ポートから入力されたトラフィックは他方の入出力ポートへ出力し、他方の入出力ポートから入力されたトラフィックは一方の入出力ポートへ出力するので、ノード次数が２となるノードで経路を選択することはできず、経路の選択性に関し、ノード次数が３以上のノードより重要性が劣るためである。
【００５３】
ここで、次数１となるＳ個のノードとその次数１となるノードに繋がっているＳ本のリンクをネットワークから全て取り除いたネットワークを、元のネットワークを一次縮約させたネットワークという。元のネットワークをＮＷと表したとき、一次縮約させたネットワークをＮＷ＊と表す。一次縮約させたネットワーク（以下、一次縮約ネットワークと縮めて呼ぶ）ＮＷ＊には、元のネットワークＮＷでノード次数が２以上のＤ＋Ｎｃｏｒｅ個のノードが含まれている。
【００５４】
一次縮約ネットワークＮＷ＊でのノード次数をＫ（大文字）を用いて表し、元のネットワークＮＷでのノード次数をｋ（小文字）を用いて区別して表す。なお、ｋそのものは、後述するように、ネットワークＮＷでの平均ノード次数を表している。
【００５５】
Ｎｃｏｒｅ個あるコアノードのうち、ｉ番目（ｉは１からＮｃｏｒｅまでの整数）のコアノードの一次縮約ネットワークＮＷ＊でのノード次数をＫｉとする。Ｎｃｏｒｅ個のコアノードの一次縮約ネットワークＮＭ＊でのノード次数Ｋの平均値をＫｃｏｒｅとしたとき、平均値Ｋｃｏｒｅの回りの平均相対偏差ｄｋｃｏｒｅを、以下の（２）式のように定める。但し、（２）式における総和Σはｉが１からＮｃｏｒｅまでについてであり、√｛  ｝は平方根を表している。
【００５６】
ｄｋｃｏｒｅ
＝√｛Σ（Ｋｉ−Ｋｃｏｒｅ）２／（Ｎｃｏｒｅ−１）｝／Ｋｃｏｒｅ  …（２）
また、ネットワークＮＷに対して、平均中継数性能値Ｈ、ネットワーク帯域性能値Ｘｅｆｆ、平均リンク率ｐ、ｃａｇｅ限界ネットワーク帯域性能値ｃａｇｅＸｅｆｆを以下のように定める。
【００５７】
平均中継数性能値Ｈは、全てのノード対間の最短経路ホップ数の平均である。ノードｉからノードｊまでの経路で最短となる経路のホップ数をＨｉ，ｊと表したとき（１≦ｉ＜ｊ≦Ｎ）、平均中継数性能値Ｈは（３）式で表すことができる。但し、（３）式における総和Σは、Ｎ（Ｎ−１）／２個だけあるノード対に対する和である。最短経路のホップ数Ｈｉ，ｊは、ネットワーク構造が定まっていると、ダイクストラ法などで求めることができる。
【００５８】
Ｈ＝ΣＨｉ，ｊ／｛Ｎ（Ｎ−１）／２｝                            …（３）
また、ノードｉからノードｊまでの経路で最短となる経路の数をＳｉ，ｊと表わす。ノード間最短経路数Ｓｉ，ｊもダイクストラ法などを利用して求めることができる。ノード間最短経路数Ｓｉ，ｊを用いて、各ノードｋのノード負荷Ｔｋを（４）式で定義すると共に、（５）式のようにノード負荷Ｔｋの最大値をＹと定める。（４）式における総和Σは、１≦ｉ，ｊ，ｋ≦Ｎで、Ｈｉ，ｊ＝Ｈｉ，ｋ＋Ｈｋ，ｊとなる組み合わせの和である。また、（５）式のｍａｘは１≦ｋ≦Ｎでの最大値である。
【００５９】
Ｔｋ＝ΣＳｉ，ｋ  Ｓｋ，ｊ／Ｓｉ，ｊ                            …（４）
Ｙ＝ｍａｘ（Ｔｋ）                                              …（５）
（４）式で表すノードｋのノード負荷Ｔｋは、ノードｋを通り、ノードｉ，ｋの最短経路となる経路とノードｋ，ｊの最短経路となる経路の全ての組み合わせの、２つのノードｉ，ｊの最短経路となる全ての経路に対する割合を、２つのノードｉ，ｊの全ての対について合成したものである。
【００６０】
ノード負荷Ｔｋの最大値Ｙを用いて、ネットワーク帯域性能Ｘｅｆｆを（６）式で定義する。
【００６１】
Ｘｅｆｆ＝｛Ｎ（Ｎ−１）／２｝／Ｙ                              …（６）
（６）式及び後述する（７）式において、Ｎ（Ｎ−１）／２は、ノード数Ｎの場合において、２個のノードの組み合わせ数になっている。全てのノードの能力が同じ場合において、ノード負荷Ｔｋの最大値Ｙをとるノードがネットワークの処理能力を規定するものとなる。ノードの能力（処理量の上限）は、通信可能な帯域と、１通信当たりの負荷との積に応じている。（６）式は、ノードの能力（処理量の上限）の一定値を「１」としてネットワーク帯域性能Ｘｅｆｆを定義したものであり、このようにしても、ネットワーク構造を評価することができる。
【００６２】
また、平均リンク率ｐを（７）式で定義する。ネットワークＮＷでの平均ノード次数ｋを（８）式で定義する。
【００６３】
ｐ＝２Ｌ／Ｎ／（Ｎ−１）                                      …（７）
ｋ＝２Ｌ／Ｎ                                                  …（８）
１つのリンクには２つのノードが繋がっている。従って、（７）式のように、リンク数Ｌを、２個のノードの組み合わせ数Ｎ（Ｎ−１）／２で割った値を平均リンク率とすることができる（なお、（７）式は、Ｎ（Ｎ−１）／２での割り算を、分子分母を入れ替えた乗算で表している）。上述のように、１つのリンクには２つのノードが繋がっているので、ノードに繋がっているリンクの端部の総数は、リンク数の２倍（２Ｌ）であり、それをノード数で割ることにより、１ノード当たりのリンクの端部数である平均ノード次数を得ることができる。
【００６４】
ネットワークＮＷでの平均ノード次数ｋを用いた、ｈ番目の項がｆｈ（ｋ）となる（９）式に示す数列｛ｆｈ（ｋ）｝と、その１番目の項からｈ番目の和Ｆｈ（ｋ）である（１０）式に示す級数｛Ｆｈ（ｋ）｝を考える。
【００６５】
｛ｆｈ（ｋ）｝＝｛１，ｋ，ｋ（ｋ−１），ｋ（ｋ−１）２，…ｋ（ｋ−１）ｈ−２，…｝
…（９）
｛Ｆｈ（ｋ）｝＝｛１，１＋ｋ，１＋ｋ＋ｋ（ｋ−１），１＋ｋ＋ｋ（ｋ−１）＋ｋ（ｋ−１）２，…｝                                                    …（１０）
図１は、数列｛ｆｈ（ｋ）｝及び級数｛Ｆｈ（ｋ）｝の表している意味合いの説明図であり、平均ノード次数ｋが３である場合の例を示している。図１は、最外殻のノードを除き、他のノードのノード次数がｋ（＝３）であるツリー構造のネットワーク（いわゆるｃａｇｅグラフ構造のネットワーク）を示しており、図１（Ａ）は、ツリー構造のトップノードＮＴから最大で４ホップで到達できるネットワークを示し、図１（Ｂ）は、ツリー構造のトップノードＮＴから最大で５ホップで到達できるネットワークを示している。なお、図１（Ａ）に示すネットワークは、図１（Ｂ）に示すネットワークの一次縮約ネットワークになっている。
【００６６】
ツリー構造のトップノードＮＴに着目すると、０ホップで到達できるノードの数は当該ノードに係る「１」であり、１ホップで到達できるノードの数は当該ノードに繋がっているリンクの数に等しい「ｋ」であり、２ホップで到達できるノードの数は、１ホップで到達できるノードの数ｋに、１ホップで到達できる各ノードから外向きに枝分かれした数（ｋ−１）を乗算した「ｋ（ｋ−１）」であり、３ホップで到達できるノードの数は、２ホップで到達できるノードの数ｋ（ｋ−１）に、２ホップで到達できる各ノードから外向きに枝分かれした数（ｋ−１）を乗算した「ｋ（ｋ−１）２」であり、以下同様に、任意のホップ数で到達できるノードの数を表すことができる。このようなホップ数毎に、到達可能なノードの数を羅列した数列は、（９）式に示す数列｛ｆｈ（ｋ）｝と一致する。
【００６７】
（９）式に示す数列｛ｆｈ（ｋ）｝が上述した意味合いを有するので、（１０）式に示す級数｛Ｆｈ（ｋ）｝の１番目の項は、トップノードＮＴから０ホップで到達できるノードの数「１」を表し、２番目の項は、トップノードＮＴから１ホップ以内で到達できるノードの数「１＋ｋ」を表し、３番目の項は、トップノードＮＴから２ホップ以内で到達できるノードの数「１＋ｋ＋ｋ（ｋ−１）」を表し、４番目の項は、トップノードＮＴから３ホップ以内で到達できるノードの数「１＋ｋ＋ｋ（ｋ−１）＋ｋ（ｋ−１）２」を表し、以下同様である。
【００６８】
Ｆｈ（ｋ）≦Ｎとなる最大の整数をｈとするとき、ｈ−１を、ノード数Ｎ、リンク数Ｌにおけるｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌと呼ぶ。ｈ番目の項は、トップノードＮＴから（ｈ−１）ホップ以内で到達できるノード数を表しているので、ｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌは、この数以下のホップ数で到達できるノード数はノード数（総ノード数）Ｎ以下であるが、この数より１だけ大きいホップ数までで到達できるノード数はノード数（総ノード数）Ｎを超えることを表している。
【００６９】
図１の例の場合、｛Ｆｈ（ｋ）｝は｛１，４，１０，２２，４６，９４，…｝であるので、仮に、ノード数（総ノード数）Ｎが５０であれば、Ｆｈ（ｋ）≦Ｎとなる最大の整数ｈは５であり、ｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌは「４」となる。図１（Ａ）は、このｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌまでのノードを記載したと同様な構造となっており、４６個のノードが記載されている。仮に、ノード数（総ノード数）Ｎが５０であれば、この４６個のノードの外側に４個のノードを設けるようにすることもできる。
【００７０】
今、一般項が（ｈ−１）ｋ（ｋ−１）ｈ−２で表わされる（１１）式に示す数列｛（ｈ−１）ｋ（ｋ−１）ｈ−２｝を考える。
【００７１】
｛（ｈ−１）ｋ（ｋ−１）ｈ−２｝＝｛（１−１）１，（２−１）ｋ，（３−１）ｋ（ｋ−１），（４−１）ｋ（ｋ−１）２，…，（ｈ−１）ｋ（ｋ−１）ｈ−２，…｝    …（１１）
図１に示すようなツリー構造において、トップノードＮＴから、Ｎ個のノードに同一回数ずつ（ここでは１回とする）トラフィックが発生した場合を考えている。（ｈ−１）ｋ（ｋ−１）ｈ−２におけるｋ（ｋ−１）ｈ−２は、図１に示すようなツリー構造において、トップノードＮＴから（ｈ−１）ホップで到達するノードの数を表しており、（ｈ−１）ｋ（ｋ−１）ｈ−２における（ｈ−１）はホップ数を表している。従って、（ｈ−１）ｋ（ｋ−１）ｈ−２は、トップノードＮＴから（ｈ−１）ホップで到達するノード数にそのホップ数を掛けた値であり、（ｈ−１）ホップで到達し得るノードへのホップ数の総和を表している。
【００７２】
ｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌより１だけ大きいホップ数で到達できるノード数は、ノード数Ｎから、ｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌ以下のホップ数で到達できるノード数Ｆｈ（ｋ）を引いたＮ−Ｆｈ（ｋ）である。ｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌより１だけ大きいホップ数で到達できるノードへのホップ数は、当然に、ｃａｇｅｈｓｈｅｌｌ＋１である。
【００７３】
ｃａｇｅ限界平均ホップ数ｃａｇｅｈを、（１２）式に示すように、数列｛（ｈ−１）ｋ（ｋ−１）ｈ−２｝の初項から第ｃａｇｅｈｓｈｅｌｌ＋１番目までの項の和に、（Ｎ−Ｆｈ（ｋ））（ｃａｇｅｈｓｈｅｌｌ＋１）を加えた値を、Ｎ−１で割ることで定義する。Ｎ−１における１は、トップノードＮＴへのホップを考慮しないためである。なお、ｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌは、その定義よりｈ−１で表すことができる。
【００７４】
ｃａｇｅｈ＝｛（１−１）１＋（２−１）ｋ＋（３−１）ｋ（ｋ−１）＋（４−１）ｋ（ｋ−１）２＋…＋（ｈ−１）ｋ（ｋ−１）ｈ−２＋（Ｎ−Ｆｈ（ｋ））（ｃａｇｅｈｓｈｅｌｌ＋１）｝／（Ｎ−１）                                        …（１２）
ｃａｇｅ限界ネットワーク帯域性能値ｃａｇｅＸｅＨは、ｃａｇｅ限界平均ホップ数ｃａｇｅｈを用いて（１３）式に示すように定義する。
【００７５】
ｃａｇｅＸｅｆｆ＝Ｎ／（ｃａｇｅｈ＋１）                    …（１３）
以上のように定めた各種のパラメータ、すなわち、ｃａｇｅ限界ネットワーク帯域性能値ｃａｇｅＸｅｆｆ、平均リンク率ｐ、平均ノード次数ｋ、ｃａｇｅ限界最外殻層数ｃａｇｅｈｓｈｅｌｌ、ｃａｇｅ限界平均ホップ数ｃａｇｅｈは全て、ノード数Ｎ及びリンク数Ｌが定まれば定まり、値を実際に求めることができるものである。
【００７６】
上述した条件Ｃ１〜Ｃ３は、以上説明した各用語や各パラメータによって表現されている。
【００７７】
（Ａ−１−２）条件Ｃ１〜Ｃ３を満たすデータ転送ネットワークの概要
条件Ｃ１〜Ｃ３を満たすデータ転送ネットワークは、ノード数Ｎが１１以上でリンク数ＬがＮ＜Ｌ＜３Ｎとなるリンク数が稀なネットワークにおいて、簡単で、しかもネットワーク帯域性能と平均中継数性能が優れた構成を有するものである。Ｎ＜Ｌ＜３Ｎより、ノード数の割にはリンク数が稀なため、ネットワーク帯域性能と平均中継数性能が上げられれば経済的・省エネ的なネットワークが組めると期待される。
【００７８】
Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）近傍のどのようなネットワーク構造でも、コア・エッジ分離構造という構造をとることを本件発明者が見出した。コア・エッジ分離構造は、Ｓエッジノードは必ずコアノードと繋がり、一次縮約ネットワークＮＷ＊には連結数が１のリンクがないという特徴がある。
【００７９】
このコア・エッジ分離構造の特徴を持つとき、コアノードの一次縮約ネットワークＮＷ＊内での平均次数が２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２となり、逆に一次縮約ネットワークＮＷ＊内でコアノードの平均次数が２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２となればネットワークはコア・エッジ分離構造となる。
【００８０】
このように、ネットワークの構造を見るときＳエッジノード、Ｄエッジノードとコアノードにノードを区別し、ネットワークＮＷを一次縮約させ、一次縮約ネットワークＮＷ＊の中での次数分布をみることにより、簡単にネットワーク帯域性能と平均中継数性能が優れた構成のデータ転送ネットワークを把握することができる。
【００８１】
（Ａ−１−３）条件Ｃ１〜Ｃ３の採用理由
次に、条件Ｃ１〜Ｃ３を採用する理由、裏返せば、条件Ｃ１〜Ｃ３を満たすデータ転送ネットワークにより、得られる効果を説明する。
【００８２】
非特許文献１の第４節の図３に示されているように、Ｎ＜Ｌ＜３Ｎとなる比較的リンクが稀なネットワークでは、インターネットなどの実際のネットワークと比較して、ランダムネットワークの方がはるかにネットワーク帯域性能が優れている。
【００８３】
図２は一つの例として、Ｎ＝５０、Ｌ＝７５における種々のネットワークの平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を示したもので、横軸に平均中継数性能Ｈ、縦軸にネットワーク帯域性能Ｘｅｆｆを示している。図２（Ｂ）は、ランダムネットワークのＨ−Ｘｅｆｆ特性を示し、図２（Ｃ）は、複雑ネットワークのＨ−Ｘｅｆｆ特性を示し、図２（Ａ）は、それら以外のネットワークのＨ−Ｘｅｆｆ特性を示している。
【００８４】
インターネットなどの構造として一般に使用されている複雑ネットワークの構造は、平均中継数性能Ｈは小さいが大きなネットワーク帯域性能Ｘｅｆｆを取れなく、ランダムネットワークは逆により大きなネットワーク帯域性能Ｘｅｆｆはとれるが平均中継数性能Ｈも大きくなる傾向があることが分かる。図２（Ａ）に示す各点（プロット）が現在までＨ−Ｘｅｆｆ特性を調べられた点（ネットワーク）で、これらの左上の境界線が上述したＨ−Ｘｅｆｆ限界性能を示している。Ｈ−Ｘｅｆｆ限界性能上の適切なネットワークを選べば複雑ネットワークやランダムネットワークより平均中継数性能、ネットワーク帯域性能がともに良いネットワークなど優れたネットワークを選ぶことができる。
【００８５】
図３は、図２で調べられたＨ−Ｘｅｆｆ特性上のネットワークで、条件Ｃ１に満たすものと、満たさないものとを示している。図３（Ａ）が条件Ｃ１を満たすものを示し、図３（Ｂ）が条件Ｃ１を満たさないものを示している。
【００８６】
図３から、条件Ｃ１を満たしたネットワークがＨ−Ｘｅｆｆ限界性能の近傍に存在し、条件Ｃ１を満たさないネットワークがＨ−Ｘｅｆｆ限界性能の近傍に存在しないことが分かる。これにより、ネットワークがＨ−Ｘｅｆｆ限界性能近傍の特性値を示すためには、条件Ｃ１が確率統計的にほぼ必要条件となっていることが分かる。
【００８７】
ここでは、Ｎ＝５０、Ｌ＝７５の例で示したが、どのようなノード数Ｎとリンク数Ｌの組み合わせでも同様である。
【００８８】
リンクを、次のように６通りに区別することができ、それぞれのリンク数を区別して表記する。コアノードの間に張られたリンクの数をＬｃｃ、コアノードとＤエッジノードの間に張られたリンクの数をＬｃｄ、コアノードとＳエッジノードの間に張られたリンクの数をＬｃｓ、Ｄエッジノードの間に張られたリンクの数をＬｄｄ、ＤエッジノードとＳエッジノードの間に張られたリンクの数をＬｄｓ、Ｓエッジノードの間に張られたリンクの数をＬｓｓと表す。このとき、各種のノード数と、各種のリンク数との間には、（１４）式〜（１６）式に示す関係がある。
【００８９】
Ｓ＝２Ｌｓｓ＋Ｌｄｓ＋Ｌｃｓ                            …（１４）
２Ｄ＝Ｌｄｓ＋２Ｌｄｄ＋Ｌｃｄ                          …（１５）
Ｌ＝Ｌｃｃ＋Ｌｃｄ＋Ｌｃｓ＋Ｌｄｄ＋Ｌｄｓ＋Ｌｓｓ      …（１６）
ネットワークが全てのノードの間で連結しているために、Ｌｓｓ＝０が一般的に成り立っているため、（１６）式は（１７）式のように変形することができる。
【００９０】
Ｌ＝Ｌｃｃ＋Ｌｃｄ＋Ｌｃｓ＋Ｌｄｄ＋Ｌｄｓ              …（１７）
条件Ｃ１を式で表すとＬｄｓ＝０となるため、（１４）式、（１５）式及び（１７）式はそれぞれ、（１８）式、（１９）式及び（２０）式のように変形することができる。
【００９１】
Ｓ＝Ｌｃｓ                                              …（１８）
２Ｄ＝２Ｌｄｄ＋Ｌｃｄ                                  …（１９）
Ｌ＝Ｌｃｓ＋Ｌｄｄ＋Ｌｃｄ＋Ｌｃｃ                      …（２０）
（１９）式よりＬｄｄ＝Ｄ−Ｌｃｄ／２が得られ、これと、（１８）式を適用すると、（２０）式は、（２１）式のように変形することができる。
【００９２】
Ｌ＝Ｓ＋Ｄ＋（Ｌｃｄ＋２Ｌｃｃ）／２                    …（２１）
Ｎｃｏｒｅ個のコアノードの一次縮約ネットワークＮＷ＊でのノード次数の平均値Ｋｃｏｒｅを用い、一次縮約ネットワークＮＷ＊のコアノードに繋がっているリンクの数の全てのコアノードについて総数を考えると、（２２）式が成立する。また、ノード数に関して、（２３）式が成立する。（２２）式及び（２３）式を（２１）式に適用することにより、（２４）式が得られる。
【００９３】
Ｎｃｏｒｅ・Ｋｃｏｒｅ＝Ｌｃｄ＋２Ｌｃｃ                …（２２）
Ｎ＝Ｎｃｏｒｅ＋Ｓ＋Ｄ                                  …（２３）
Ｌ＝Ｎ−Ｎｃｏｒｅ＋Ｎｃｏｒｅ・Ｋｃｏｒｅ／２          …（２４）
（２４）より、一次縮約ネットワークＮＷ＊におけるノード次数平均値Ｋｃｏｒｅは、（２５）式で表されることが分かる。条件Ｃ１より、一次縮約ネットワークＮＷ＊におけるノード次数の平均値Ｋｃｏｒｅについての（２５）式の条件が得られる。逆に、（２５）式の条件より、条件Ｃ１を導き出すことができるため、条件Ｃ１と、一次縮約ネットワークＮＷ＊におけるノード次数の平均値ＫｃｏｒｅがＫｃｏｒｅ＝２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２となることは全く等価であることが分かる。
【００９４】
Ｋｃｏｒｅ＝２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２                …（２５）
図２から分かるように、複雑ネットワークなどの一般に使用されているネットワークやランダムネットワークと比べて、Ｈ−Ｘｅｆｆ限界性能値近傍のネットワークは、はるかに性能が高く、また、図３からは、その優れた性能のネットワークの中でも、条件Ｃ１を満たしたネットワークがとりわけ優れた性能を持つ傾向があることが分かる。このような優れたネットワークとなるために必要な構造条件が条件Ｃ１であり、ネットワークを一次縮約したときのコアノード数とコアノード次数平均値の間の関係式Ｋｃｏｒｅ＝２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２を満たすことである。
【００９５】
図４は、Ｎ＝５０、Ｌ＝７５を例に、ネットワーク帯域性能ＸｅｆｆがＨ−Ｘｅｆｆ限界性能値から劣ること１未満の限界性能値近傍のネットワークの、一次縮約ネットワークでのコアノード次数平均値Ｋｃｏｒｅの回りの、上述した（２）式で表される平均相対偏差ｄｋｃｏｒｅの出現頻度を示している。図４において、横軸は平均相対偏差ｄｋｃｏｒｅを表しており、曲線ｆｒｅｑは、その平均相対偏差ｄｋｃｏｒｅをとるネットワークの出現頻度であり、曲線ａｃｃｕｍは、出現頻度ｆｒｅｑの累積度数である。
【００９６】
図５は、平均相対偏差ｄｋｃｏｒｅを、（Ｒ１）ｄｋｃｏｒｅ＝０．０、（Ｒ２）０．０＜ｄｋｃｏｒｅ≦０．２、（Ｒ３）０．２＜ｄｋｃｏｒｅ≦０．４、（Ｒ４）０．５＜ｄｋｃｏｒｅ≦０．６という４つの領域Ｒ１〜Ｒ４に分けた場合における、それぞれの領域に含まれたネットワークの平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を示している。図５（Ａ）〜（Ｄ）はそれぞれ、領域Ｒ１〜Ｒ４の平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を示している。
【００９７】
図５から、平均相対偏差ｄｋｃｏｒｅが上述した４つの領域Ｒ１〜Ｒ４に値を持つネットワークのときに、そのネットワークが、Ｈ−Ｘｅｆｆ限界性能値とその近傍に特性を有することが分かる。
【００９８】
一方、上記の４つの領域Ｒ１〜Ｒ４に含まれないｄｋｃｏｒｅを有するネットワークの中には（０．６＜ｄｋｃｏｒｅ）、Ｈ−Ｘｅｆｆ限界性能値とその近傍を取るネットワークは存在していない。
【００９９】
このＮ＝５０、Ｌ＝７５の例に見られるように、平均値Ｋｃｏｒｅの回りの平均相対偏差ｄｋｃｏｒｅの値でｄｋｃｏｒｅ＜０．６のとき、確率統計的に優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を示すことが期待される。これが、上述した条件Ｃ２の根拠である。
【０１００】
図３から分かるように、条件Ｃ１を満たしたからといって、必ずしもＨ−Ｘｅｆｆ限界性能値近傍にあるとは限らない。条件Ｃ２も同様である。
【０１０１】
上述した（１）式を満足することを規定した条件Ｃ３は、必ずＨ−Ｘｅｆｆ限界性能値近傍になる条件である。
【０１０２】
条件Ｃ３が表す領域は、（ｍｉｎＨ，ｍｉｎＸｅｆｆ）と（ｃａｇｅｈ，ｃａｇｅＸｅｆｆ／２）を結ぶ直線より上側の領域となっている。（ｃａｇｅｈ，ｃａｇｅＸｅｆｆ／２）は、ｃａｇｅ限界（ｃａｇｅｈ，ｃａｇｅＸｅｆｆ）の半分のネットワーク帯域性能Ｘｅｆｆの値を持つ点で、ネットワーク帯域性能特性として十分優れている特性を示していて、Ｈ−Ｘｅｆｆ限界性能値近傍になっている。第１の実施形態が対象としているどのようなノード数Ｎ、リンク数Ｌの組み合わせにおいても、限界性能値は条件Ｃ３が表す領域に入っており、条件Ｃ３が表す領域は、Ｈ−Ｘｅｆｆ限界性能値近傍を規定する領域となっている。
【０１０３】
以上説明した理由により、条件Ｃ１〜Ｃ３を採用し、条件Ｃ１〜Ｃ３が満足していることにより、そのデータ転送ネットワークが、をＨ−Ｘｅｆｆ限界性能Ｘ（Ｈ）上のネットワーク構造が有するネットワーク帯域性能と平均中継数性能に近い性能を示すことを保証できるようにした。
【０１０４】
（Ａ−２）条件Ｃ４及びＣ５について
（Ａ−２−１）条件Ｃ４の内容
条件Ｃ１〜Ｃ３を満たすネットワークの中でも、突出した平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を示すためのコアノード数Ｎｃｏｒｅに対する条件が、条件Ｃ４と後述する条件Ｃ５である。
【０１０５】
ノード数Ｎ、リンク数Ｌのネットワークが条件Ｃ１を満たすとき、Ｎｃｏｒｅ個のコアノードの一次縮約ネットワークＮＷ＊でのノード次数Ｋの平均値Ｋｃｏｒｅは、（２５）式に示したように、Ｋｃｏｒｅ＝２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２となっている。一次縮約ネットワークＮＷ＊でのコアノード次数Ｋの平均値Ｋｃｏｒｅの回りでの分布が、条件Ｃ２を満たすｄｋｃｏｒｅ＜０．６となるとき、２≦Ｎｃｏｒｅ≦Ｎとなるどのような整数Ｎｃｏｒｅにおいても、ネットワーク帯域性能と平均中継数性能に優れた性能を示すが、とりわけ、「コアノード数Ｎｃｏｒｅが２（Ｌ−Ｎ）の約数となっている」という条件Ｃ４を満たすとき、さらに優れたネットワーク帯域性能と平均中継数性能が確率統計的に期待される。
【０１０６】
（Ａ−２−２）条件Ｃ５の内容
同様に、条件Ｃ１〜Ｃ３を満たすネットワークでも、とりわけ、「コアノード数Ｎｃｏｒｅが、最外殻層数ｈｓｈｅｌｌに対する閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）となっている」という条件Ｃ５を満たすとき、さらに優れたネットワーク帯域性能と平均中継数性能が確率統計的に期待される。
【０１０７】
ここで、最外殻層数ｈｓｈｅｌｌ及び閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）は、次のように定義されているものである。
【０１０８】
実数ｘに対し、ｈ番目の項がｆｈ（ｘ）となる（２６）式に示す数列｛ｆｈ（ｘ）｝と、その１番目の項からｈ番目の和Ｆｈ（ｘ）である（２７）式に示す級数｛Ｆｈ（ｘ）｝を考える。（２６）式及び（２７）式は、上述した（９）式及び（１０）式と同様な式である。
【０１０９】
｛ｆｈ（ｘ）｝＝｛１，ｘ，ｘ（ｘ−１），ｘ（ｘ−１）２，…ｘ（ｘ−１）ｈ−２，…｝
…（２６）
｛Ｆｈ（ｘ）｝＝｛１，１＋ｘ，１＋ｘ＋ｘ（ｘ−１），１＋ｘ＋ｘ（ｘ−１）＋ｘ（ｘ−１）２，…｝                                                    …（２７）
ここで、それぞれのコアノード数Ｎｃｏｒｅに対し、Ｆｈ｛２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２｝≦Ｎとなる最大の整数ｈを、コアノード数Ｎｃｏｒｅに対応する最外殻層数ｈｓｈｅｌｌと呼ぶ。
【０１１０】
実数ｘが整数のときには、数列｛ｆｈ（ｘ）｝は、ノード次数が全てｘである場合のネットワークにおいて、一つのノードからｈ−１ホップで到達できるノード数の最大値を表している。また、級数｛Ｆｈ（ｘ）｝は、一つのノードからｈ−１ホップまでに到達できるノード数の和の最大値を表している。
【０１１１】
実数ｘが整数でないときには、数列｛ｆｈ（ｘ）｝は、平均ノード次数がｘである場合のネットワークにおいて、一つのノードからｈ−１ホップで到達できるノード数の最大値の期待値を表していると考えられる。また、級数｛Ｆｈ（ｘ）｝は、一つのノードからｈ−１ホップまでに到達できるノード数の和の最大値の期待値を表していると考えられる。
【０１１２】
また、ｆｈ（ｘ）、Ｆｈ（ｘ）、最外殻層数ｈｓｈｅｌｌを元に、次のように閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）を考える。
【０１１３】
２≦Ｎｃｏｒｅ≦Ｎとなるどのような整数Ｎｃｏｒｅにおいても、それぞれのＮｃｏｒｅに対し、上述したように定められた最外殻層数ｈｓｈｅｌｌが対応する。最外殻層数ｈｓｈｅｌｌはコアノード数Ｎｃｏｒｅに対して単調に増加する。最外殻層数ｈｓｈｅｌｌの最大値はＮｃｏｒｅ＝Ｎのときであり、Ｆｈ（２Ｌ／Ｎ）≦Ｎとなる最大整数ｈを求めることで得られる。この最大の最外殻層数ｈｓｈｅｌｌをｍａｘｈｓｈｅｌｌとする。最大の最外殻層数ｍａｘｈｓｈｅｌｌ以下のそれぞれの最外殻層数ｈｓｈｅｌｌにおいて、最外殻層数ｈｓｈｅｌｌが対応する最大のコアノード数Ｎｃｏｒｅを、最外殻層数ｈｓｈｅｌｌに対する閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）と呼ぷ。
【０１１４】
上述した条件Ｃ５は、以上のように定義された最外殻層数ｈｓｈｅｌｌと閉殻コア数Ｎｃｃ（ｈｓｈｅｌｌ）を用いて表現されている。
【０１１５】
（Ａ−２−３）条件Ｃ４及びＣ５の採用理由
次に、条件Ｃ４及びＣ５を採用する理由、裏返せば、条件Ｃ４又はＣ５を満たすデータ転送ネットワークにより、得られる効果を説明する。
【０１１６】
上述したように、条件Ｃ１〜Ｃ３を満たすネットワークの中でも、突出した平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を示すためのコアノード数Ｎｃｏｒｅに対する条件が、条件Ｃ４又はＣ５である。これらの条件Ｃ４及びＣ５は、どちらも独立で、どちらか一方が成り立つこともあれば、両方同時に成り立つこともある。両方同時に成り立つときが、平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性として優れた特性を示すことが一層期待できるときである。
【０１１７】
図６に、ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークを例に、コアノード数Ｎｃｏｒｅが、条件Ｃ４又はＣ５を満たすことで、平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性で突出した特性を示していることを示す。図６の突出部に対応してコアノード数Ｎｃｏｒｅと対応した条件Ｃ４又はＣ５を示す。
【０１１８】
なお、図６でコアノード数Ｎｃｏｒｅ＝５０の最大に突出しているネットワークは、丁度３次の正則グラフのネットワーク構造を有し、本明細書における検討外の構造である。検討外の構造であるが、この最大に突出したネットワークは、条件Ｃ１〜Ｃ３は満たさないものの、条件Ｃ４と条件Ｃ５は満たしている。
【０１１９】
上述したように、Ｈ−Ｘｅｆｆ限界性能Ｘ（Ｈ）値近傍では、ネットワーク構造はコア・エッジ分離構造という構造をとっている。条件Ｃ１を満たすことと、コア・エッジ分離構造をとることは同義である。条件Ｃ１を満たすことにより、一次縮約ネットワークにおけるコアノード次数平均値ＫｃｏｒｅはＫｃｏｒｅ＝２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２となっている。条件Ｃ２は、このコアノード次数の分布が平均値Ｋｃｏｒｅの近くに分布しているものに、優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性のネットワークが多いことを示している。図５に示したように、ネットワーク帯域性能Ｘｅｆｆが大きくコアノード数Ｎｃｏｒｅも大きいときは、コアノード次数は平均値の近くに集中している。コアノード数Ｎｃｏｒｅが小さいところでは、Ｈ−Ｘｅｆｆ限界性能近傍の構造数密度が小さく、コアノード次数が平均値から幾分はなれていても、Ｈ−Ｘｅｆｆ限界性能近傍の特性を示すことが可能と考えられる。条件Ｃ２はコアノード数Ｎｃｏｒｅが小さいところでのコアノード次数の平均値からのずれとして許される許容範囲を示している。
【０１２０】
なぜ、条件Ｃ４又はＣ５を満たすところが、平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性で突出するかを納得するためには、以下に示すことを理解する必要がある。
【０１２１】
ネットワーク帯域性能Ｘｅｆｆを上げるためには、それぞれのノードでのトラフィック処理をなるべく下げる必要がある。特に、ネットワークの中で最大の処理を行っているノードの処理量を下げると、ネットワーク全体のネットワーク帯域性能Ｘｅｆｆが上がる。
【０１２２】
ところで、平均中継数性能Ｈとノード処理量の間には密接な関係がある。それは、ネットワーク全体のノードの処理量の総和が平均中継数性能Ｈに比例する（厳密には、ノードの処理量の総和は、平均中継数性能Ｈに１を足したものに比例する）という関係である。
【０１２３】
ネットワーク帯域性能Ｘｅｆｆは最大ノード処理量で決まり、平均中継数性能Ｈは全ノード処理総量で決まる。このため、同じ平均中継数性能値Ｈならばノード処理量のばらつきをなくしたとき最大のネットワーク帯域性能が得られる。平均処理量は厳密に（Ｈ＋１）／Ｎに比例するため、ネットワーク帯域性能ＸｅｆｆはＮ／（Ｈ＋１）となる。この値は、平均中継数Ｈでノード処理ばらつきをなくせたときのネットワーク帯域性能の最良値であり、一般のネットワークではこの値以下となる。
【０１２４】
因みに、Ｌ≧Ｎ１．５となるリンク数の豊富なネットワークでは、この最良値をとることが容易に可能であるが、本明細書が対象としているＮ＜Ｌ＜３Ｎの領域ではリンクが稀なため、ノード処理のばらつきをなくせず、この最良値を下回る値となる。
【０１２５】
図６に、ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークでのネットワーク帯域性能Ｘｅｆｆの最良値Ｎ／（Ｈ＋１）を示す曲線を示している。ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークにおける（ｍａｘＨ，ｍａｘＸｅｆｆ）の点は、この最良値曲線の極近傍に位置するが、僅かながらノード処理が揃わず、ばらつきが存在するため、この最良値に達することができないことを示している。
【０１２６】
ここで、（ｍａｘＨ，ｍａｘＸｅｆｆ）のネットワークにおけるノード処理のばらつきを少なくする方法を考える。ノード数Ｎの全てのノードでなるべく処理量を揃えて、なおかつ、平均中継数性能Ｈを極力抑えることが必要である。そのため、それぞれのノードの次数はなるべく揃っていた方が、処理量に差がなくなると考えられる。
【０１２７】
２Ｌ／Ｎが整数となるとき、全てのノード次数を揃えることができる。例えば、Ｎ＝５０、Ｌ＝７５では平均ノード次数はちょうど３となり、全てのノード次数を揃えることができる。２Ｌ／Ｎが整数のとき、ネットワークは、「グラフ理論」でいう「正則グラフ」となる。因みに、正則グラフは、「グラフ理論」研究を含めて広い研究分野で研究されていて、多くの構造が既に知られているため、本明細書における対象外としてある。Ｎ＝５０、Ｌ＝７５でも、全てのノード次数が３となっていなくて正則グラフでないものも存在し、本明細書では、このような正則グラフでないものを対象としている。
【０１２８】
図７は、ノード数Ｎ＝５０で、平均ノード次数ｋが３から９まで、リンク数を変化させたときの、（ｍａｘＨ，ｍａｘＸｅｆｆ）の変化の様子を示している。リンク数Ｌが増えるにつれて平均ノード次数が増えて、ｍａｘＨが減りｍａｘＸｅｆｆが増えてゆくが、ｍａｘＸｅｆｆは一様に増えるのではなく、平均ノード次数ｋが整数値のところで極大値をとり、上下に変動しながら増えてゆく。このように、平均ノード次数がちょうど整数値を持つとき、全てのノードの次数が揃い、大きいｍａｘＸｅｆｆをとることが分かる。
【０１２９】
特に、平均ノード次数が整数であり、どのノードから見てもネットワーク全体が同じように見えるような構造（自己同型構造）が存在するならば、全てのノードの処理量は厳密に均等になる。ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークではそのような構造は今までに見出されていない。このような自己同型構造が存在するか存在しないかは、ノード数Ｎとリンク数Ｌの数の組み合わせにより決まり、リンク数Ｌがノード数Ｎに比べて稀であるとなかなか存在しない。自己同型構造は、「グラフ理論」でいうｃａｇｅグラフやＭｏｏｒｅグラフの研究で見いだされており、一例としてＮ＝５０、Ｌ＝１７５という、リンク数Ｌがノード数Ｎに比べて多いとき、次数７の正則グラフであるＨｏｆｆｍａｎ  Ｓｉｎｇｌｅｔｏｎ  ｇｒａｐｈが知られている。
【０１３０】
Ｈｏｆｆｍａｎ  Ｓｉｎｇｌｅｔｏｎ  ｇｒａｐｈでは、どのノードから見ても最近接ノードは７個あり、ホップ数２の第二次近接ノードは４２個となっていて、全てのノード間のホップ数は２以下となっている。なお、これにより、Ｈｏｆｆｍａｎ  Ｓｉｎｇｌｅｔｏｎ  ｇｒａｐｈの平均中継数性能Ｈとネットワーク帯域性能Ｘｅｆｆは、Ｈ＝（１×７＋２×４２）／（Ｎ−１）＝１３／７、Ｘｅｆｆ＝５０／（Ｈ＋１）＝１７．５と簡単に計算される。
【０１３１】
一般のｃａｇｅグラフやＭｏｏｒｅグラフと呼ばれる正則なネットワークで、次数をｋとしたとき、どのようなノードからでも第０ホップ、第１ホップ、第２ホップ、…第ｈホップとホップ数を増やしていった場合に初めて到達することができるノードの数の最大は、それぞれ、上述した（９）式（や（２６）式）に示す数列｛ｆｈ（ｋ）｝の１番目、２番目、３番目、…ｈ＋１番目の項に当たる。
【０１３２】
ノード次数ｋで正則なネットワークで、どのようなノードからでもホップ数ｈで初めて到達することができるノードの数が最大数ｋ（ｋ−１）ｈ−１になっている場合、このネットワーク構造は「ｈ閉殻である」とここではいう。Ｈｏｆｆｍａｎ  Ｓｉｎｇｌｅｔｏｎ  ｇｒａｐｈは２閉殻である。ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークでは、｛１，３，６，１２，２４，４｝となる４閉殻の構造が考えられる。仮に、このような構造が存在するのならば最大ホップ数は５である。ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークでは、このような４閉殻の構造はまだ見つけられていないが、３閉殻の構造は見つけられている。存在する最大の閉殻数をもつ構造を最大閉殻構造という。与えられたノード数Ｎとリンク数Ｌのネットワークの中で、ノード間の最大ホップ数が最小となるネットワークで、その最小値の値を、与えられたノード数Ｎとリンク数Ｌのネットワークにおける最外殻層数ｈｓｈｅｌｌと呼ぶ。ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークにおける最外殻層数ｈｓｈｅｌｌは５である。最外殻層数ｈｓｈｅｌｌで閉殻なものを完全閉殻と呼ぶ。Ｈｏｆｆｍａｎ  Ｓｉｎｇｌｅｔｏｎ  ｇｒａｐｈは完全閉殻である。ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークで４閉殻が存在したとしても完全閉殻でない。完全閉殻とＭｏｏｒｅグラフは同義である。
【０１３３】
ノード次数ｋで正則なネットワークでは閉殻数が大きければ平均中継数Ｈが小さいことが示される。また、閉殻数が大きければノードの対称性が増すために、ノード処理のばらつきも小さくなると考えられる。そのために、２Ｌ／Ｎが整数となるネットワークでは、（ｍａｘＨ，ｍａｘＸｅｆｆ）となるネットワークは、今まで調べた全てのネットワーク構造の中で例外なくの最大閉殻構造となっている。
【０１３４】
２Ｌ／Ｎが整数にならないとき、全てのノード次数を揃えることができず、Ｎｃｏｒｅ＝Ｎと見たときの平均コアノード次数Ｋｃｏｒｅも整数にならない。そのために、厳密には、「正則グラフ」で成り立った議論がそのままでは成り立たない。しかし、実際に、このような平均コアノード次数が整数でないネットワーク構造でも統計的に「正則グラフ」と同じ傾向を示していることが経験されている。
【０１３５】
２Ｌ／Ｎが整数にならず、Ｎｃｏｒｅ＝Ｎと見たときの平均コアノード次数ｋが非整数でも、上述した（９）式（や（２６）式）に示す数列｛ｆｈ（ｋ）｝の１番目、２番目、３番目、…ｈ＋１番目の項は、全てのノードからの第０ホップ、第１ホップ、第２ホップ、…第ｈホップとホップ数を増やしていった場合に初めて到達することができるノードの数の最大値の平均と考えられる。
【０１３６】
２Ｌ／Ｎが整数のとき、最大閉殻構造や完全閉殻の構造をとると、優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を期待することができるように、２Ｌ／Ｎが非整数のときでも、上述した（９）式（や（２６）式）に示す数列が、全てのノードからの第０ホップ、第１ホップ、第２ホップ、…第ｈホップとホップ数を増やしていった場合に初めて到達することができるノードの数の平均値となるような分布を持つとき、同様に、優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を期待することができる。
【０１３７】
以上は（ｍａｘ，ｍａｘＸｅｆｆ）近傍での傾向であるが、Ｈ−Ｘｅｆｆ限界性能近傍におけるネットワークＮＷの一次縮約ネットワークＮＷ＊において、その一次縮約ネットワークＮＷ＊のノード数Ｄ＋Ｎｃｏｒｅと一次縮約ネットワークＮＷ＊における平均ノード次数ｋ＊においても同様な傾向があり、実際に、図６に示したように、ある限られたコア数Ｎｃｏｒｅで平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性が突出している。
【０１３８】
つまり、図７を用いて上述した説明に対応して、一次縮約ネットワークＮＷ＊におけるノード次数ｋ＊が整数となっていると優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を期待することができる。条件Ｃ４は、このような内容に対応する。
【０１３９】
また、一次縮約ネットワークＮＷ＊においてノード数Ｄ＋Ｎｃｏｒｅのそれぞれのノードから、第０ホップ、第１ホップ、第２ホップ、…第ｈホップとホップ数を増やしていった場合に初めて到達することができるノードの数の平均値が、（２８）式に示すように分布しているとき、最大閉殻構造のように、優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を期待することができる。特に、このノード次数を非整数に拡張した場合の完全閉殻の構造が特に期待される。条件Ｃ５は、このような内容に対応する。
【０１４０】
１，ｋ＊，ｋ＊（ｋ＊−１），…，ｋ＊（ｋ＊−１）ｈ−１      …（２８）
（Ａ−３）条件Ｃ６について
（Ａ−３−１）条件Ｃ６の内容
条件Ｃ１〜Ｃ３、条件Ｃ１〜Ｃ４、条件Ｃ１〜Ｃ３、Ｃ５、又は、条件Ｃ１〜Ｃ５を満たすネットワークの中でも、条件Ｃ６を満たすネットワークは、さらに優れたネットワーク帯域性能と平均中継数性能が確率続計的に期待される。
【０１４１】
上述した条件Ｃ１〜Ｃ５は、ノード数Ｎ、リンク数Ｌ、コアノード数Ｎｃｏｒｅなどで定まっており、Ｓエッジノード数ＳやＤエッジノード数Ｄが実際にとる値に依存していない。条件Ｃ１〜Ｃ３、条件Ｃ１〜Ｃ４、条件Ｃ１〜Ｃ３、Ｃ５、又は、条件Ｃ１〜Ｃ５を満たすネットワークの中でも、Ｓ＋Ｄ＝Ｎ−Ｎｃｏｒｅ、０≦Ｓ≦Ｎ−Ｎｃｏｒｅ、０≦Ｄ≦Ｎ−Ｎｃｏｒｅなどの条件の中で任意性があり、どのＳエッジノード数Ｓ及びＤエッジノード数Ｄの組み合わせでも、優れたネットワーク帯域性能と平均中継数性能が確率統計的に期待されるが、さらに、Ｓエッジノード数ＳやＤエッジノード数Ｄについての条件Ｃ６を同時に満たすことにより、さらに優れたネットワーク帯域性能と平均中継数性能が確率統計的に期待される。
【０１４２】
上述した数列｛ｆｈ（ｘ）｝、級数｛Ｆｈ（ｘ）｝、最外殻層数ｈｓｈｅｌｌの考え方を用いて、以下のように考えることができる。
【０１４３】
（２７）式で示した級数｛Ｆｈ（ｘ）｝を用いて、それぞれのコアノード数Ｎｃｏｒｅに対し、Ｆｈ｛２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２｝≦Ｎとなる最大の整数ｈを、コアノード数Ｎｃｏｒｅに対応する最外殻層数ｈｓｈｅｌｌとした。このとき、Ｘ≦２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２でＦｈｍａｘ（Ｘ）＝ＮとなるＸが存在する。このようなＸを用いて、Ｄｍａｘを、Ｎｃｏｒｅ｛２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２−Ｘ｝／２を超えない最大の整数と決める。このようにＤｍａｘは、ノード数Ｎ、リンク数Ｌ、コアノード数Ｎｃｏｒｅより求めることができる。
【０１４４】
このようにして求められたＤｍａｘを用いて、条件Ｃ６が記述されており、優れたネットワーク帯域性能と平均中継数性能を実現できるＳエッジノード数ＳやＤエッジノード数Ｄの範囲が定められている。
【０１４５】
（Ａ−３−２）条件Ｃ６の採用理由
次に、条件Ｃ６を採用する理由、裏返せば、条件Ｃ６を満たすデータ転送ネットワークにより、得られる効果を説明する。
【０１４６】
ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークの中で限界性能を示しているネットワークに関する各種パラメータを、代表的なコアノード数Ｎｃｏｒｅについて、表１に示している。表１の１行には、コアノード数Ｎｃｏｒｅ、コアノード次数分布、Ｄエッジノード数Ｄ、Ｄエッジノード数の取り得る最大値（上限値）Ｄｍａｘ、Ｓエッジノード数Ｓ、充足している条件が記述されている。コアノード次数分布の欄における例えば「１８Ｋ３＋１６Ｋ４」は、「ノード次数３の１８個のコアノードと、ノード次数４の１６個のコアノードの総ノード次数」を表している。
【表１】
2011114795.tif 000003
【０１４７】
コアノード数Ｎｃｏｒｅの大きさに応じて、コアノードの一次縮約ネットワークＮＷ＊での平均値Ｋｃｏｒｅは決定されるが、Ｄエッジノード数Ｄ、Ｓエッジノード数Ｓが取り得る値には任意性がある。上述したように求められた取り得る最大値Ｄｍａｘより、実際のＤエッジノード数Ｄの値は、０≦Ｄ≦Ｄｍａｘの範囲に入っていることが分かる。条件Ｃ６を満たすネットワークの効果はこの表１に示されている。
【０１４８】
表１からも分かるようにＤエッジノード数Ｄは、０か取り得る最大値Ｄｍａｘのどちらかをとる場合が多い傾向がある。
【０１４９】
なぜ、上述のように求めた取り得る最大値Ｄｍａｘにより、Ｄエッジノード数Ｄが取り得る範囲が０≦Ｄ≦Ｄｍａｘと表わされる理由を、以下に説明する。
【０１５０】
この理由を理解するために、次のことを念頭に置く必要がある。
【０１５１】
ネットワークＮＷの中を流れるトラフィックはほとんど、一次縮約ネットワークＮＷ＊の中を通る。例外は、トラフィックの送り出したノードや送り先のノードがＳエッジノードのときだけであり、最初か最後に一回だけ一次縮約ネットワークＮＷ＊上にないリンクを通る。
【０１５２】
Ｓエッジノードがネットワーク全体としてなぜ必要になるかは、Ｄエッジノードも合わせて、自らのノード次数を減らすことにより、より大きいコアノード平均次数Ｋｃｏｒｅを実現するためにある。そのため、ＳエッジノードもＤエッジノードも、ネットワークの中でトラフィック中継に携わることは少なくなる。
【０１５３】
Ｄエッジノードは、Ｓエッジノードとは異なり、一次縮約ネットワークＮＷ＊中のノードであるため、トラフィック中継に携わることもあるが、ほんの僅かしか携わらないと考えられる。ほんの僅かしか携わらない理由を、図８を用いて説明する。
【０１５４】
図８（Ａ）は、一つのＤエッジノードＤ１が一次縮約ネットワークＮＷ＊の中で他のノードと繋がっている様子を示している。この場合、一次縮約ネットワークＮＷ＊は限界性能近傍の性能を示していると考える。ＤエッジノードＤ１が繋がっているノードをｎａとｎｂとしている。ｎａとｎｂが直接リンクされていなければ、少なくともｎａｎｂ間のトラフィック中継にＤエッジノードＤ１は携わっている。ＤエッジノードＤ１が携わっている中継トラフィックを、図８（Ａ）のｆ１で示している。ＤエッジノードＤ１が携わっているトラフィックには、ｆ１以外にも、図８（Ｃ）に示すように、ＤエッジノードＤ１で終端されるトラフィックｆａ、ｆｂが存在する。
【０１５５】
ｆａ、ｆｂのような終端トラフィックより中継トラフィックｆ１が多いときは、図８（Ａ）よりも、図８（Ｂ）の配置などが有利である。逆に、中継トラフィックｆ１が終端トラフィックｆａ、ｆｂより少ないとき、図８（Ａ）の配置が有利となることが分かる。
【０１５６】
このようにＤエッジノードも一次縮約ネットワークＮＷ＊中のノードではあるが、ほとんどトラフィック中継に一般には携わっておらず、ネットワーク中継はもっぱらコアノード間のリンクがなすネットワークにより行われていると一般に考えられる（ここで一般と断ったのは、その例外も、極く少数であるが、存在しているためである）。
【０１５７】
ネットワーク中継はもっぱらコアノード間のリンクがなすネットワークにより行われているため、コアノード間のリンクがなすネットワークがどのような構造を持つかが、ネットワーク全体の平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を決める鍵となる。
【０１５８】
Ｎｃｏｒｅ個のコアノードとＤ個のＤエッジノードからなる、一次縮約ネットワークＮＷ＊における平均ノード次数ｋ＊は、コアノードの平均ノード次数がｋｃｏｒｅでＤエッジノードのノード次数が２のため、（２９）式で表される。
【０１５９】
ｋ＊＝（Ｎｃｏｒｅ・ｋｃｏｒｅ＋２Ｄ）／（Ｎｃｏｒｅ＋Ｄ）      …（２９）
Ｄエッジノード数ＤはＳ＋Ｄ＝Ｎ−Ｎｃｏｒｅ、０≦Ｓ≦Ｎ−Ｎｃｏｒｅ、０≦Ｄ≦Ｎ−Ｎｃｏｒｅなどの条件の中で任意性があるため、（２８）式が（拡張された）完全閉殻の構造の条件になるようにＤを加減して調整することができる。この調整により得られたＤの値が、上述した計算方法で得られるＤｍａｘである。
【０１６０】
数の条件からはＤがちょうどＤｍａｘのとき（拡張された）完全閉殻の構造が得られても良いが、必ずしもそのような構造が実際にあるとは限らない。そのため、最大の閉殻数を得るためには、ＤはＤｍａｘ以下であれば良いので、Ｄの値は０≦Ｄ≦Ｄｍａｘの範囲に入っていることが分かる。
【０１６１】
一般の場合は、上述した議論により、Ｓエッジノードが多いよりも、Ｄエッジノードが多い方が多少なりとも、平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性的に有利と考えられるが、差は僅差であり、実際の構造の条件により、Ｓエッジノードが多い方が有利であったり、Ｄエッジノードが多い方が有利であったりするため、実際のＤエッジノード数Ｄは０≦Ｄ≦Ｄｍａｘの範囲の数で、０かＤｍａｘをとることが多いことが理解される。
【０１６２】
（Ａ−４）条件Ｃ７について
（Ａ−４−１）条件Ｃ７の内容
条件Ｃ１〜Ｃ６のうち、条件Ｃ１〜Ｃ３を含めた３つ以上の条件を満たすネットワークの中でも、条件Ｃ７を満たすネットワークは、さらに優れたネットワーク帯域性能と平均中継数性能が確率続計的に期待される。
【０１６３】
条件Ｃ１〜Ｃ６のうち、条件Ｃ１〜Ｃ３を含めた３つ以上の条件を満たすＳエッジノード数Ｓ、Ｄエッジノード数Ｄ、コアノード数Ｎｃｏｒｅの組み合わせがあった場合、ネットワークＮＷにおけるＳ個のＳエッジノードが、一次縮約ネットワークＮＷ＊におけるＮｃｏｒｅ個のコアノードうちどれに繋げるかには任意性があり、どのような繋げ方であっても、条件Ｃ１〜Ｃ６のうち、条件Ｃ１〜Ｃ３を含めた３つ以上の条件を満たす個数のＳエッジノード、Ｄエッジノード、コアノードで構成されていれば、確率統計的に、ネットワーク帯域性能と平均中継数性能に優れた性能を示すことが期待できる。
【０１６４】
しかし、以下に示す理想的な分配方法に従って、ネットワークＮＷにおけるＳ個のＳエッジノードを一次縮約ネットワークＮＷ＊におけるＮｃｏｒｅ個のコアノードに分配したと仮定した場合、Ｓエッジノードのコアノードの現実の繋がり方が、そのような理想的な分配方法で分配したものと同様であれば、より優れたネットワーク帯域性能と平均中継数性能が確率統計的に期待される。
【０１６５】
「Ｓエッジノードの理想的な分配方法」
一次縮約ネットワークＮＷ＊におけるＮｃｏｒｅ個のそれぞれのコアノードにネットワークＮＷにおけるＳエッジノードを一つずつ順番に繋げていくことを考える。それぞれのコアノードに繋げたＳエッジノードの数をｓとする。
【０１６６】
（ア）ｓは、各コアノードについてＳエッジノードを繋ぎ始めるまでは零である。
【０１６７】
（イ）一次縮約ネットワークＮＷ＊における各コアノードのノード次数をＫとしたとき、Ｋ＋ｓが一番小さいコアノードの中からどれか一つのノードを任意に選んで、それに一つのＳエッジノードを繋げる。この操作により、Ｓエッジノードを繋げたコアノードのｓは１だけ増え、残ったＳエッジノードの数は１つだけ減る。
【０１６８】
（ウ）（イ）の操作を、コアノードに繋げられていないＳエッジノードがなくなるまで繰り返す。
【０１６９】
上記（ア）〜（ウ）の操作を行うことにより、最終的に、ネットワークＮＷにおけるＳ個のＳエッジノードを、一次縮約ネットワークＮＷ＊におけるＮｃｏｒｅ個のコアノードに分配することができる。
【０１７０】
Ｓエッジノードの理想的な分配方法は、全てのＳエッジノードを分配した後のコアノードの次数分布のバラツキが最も小さくなる方法であれば良く、上述した方法に限定されるものではない。
【０１７１】
上述した条件Ｃ７は、ネットワークＮＷにおけるＳ個のＳエッジノードを一次縮約ネットワークＮＷ＊におけるＮｃｏｒｅ個のコアノードに理想的な分配方法を適用して分配したと仮定した結果に、ネットワークＮＷにおけるＳエッジノードとコアノードとの繋がり方が一致しているという条件である。なお、条件Ｃ７は、ネットワークＮＷにおけるＳ個のＳエッジノードを一次縮約ネットワークＮＷ＊におけるＮｃｏｒｅ個のコアノードに理想的な分配方法を適用して一旦分配した後、低次のコアノードに繋がっているＳエッジノードのうちの一部若しくは全てをより高次のコアノードへ移動する分配方法を適用したと仮定した場合の結果に、ネットワークＮＷにおけるＳエッジノードとコアノードとの繋がり方が一致しているも含むものとしている。
【０１７２】
（Ａ−４−２）条件Ｃ７の採用理由
次に、条件Ｃ７を採用する理由、裏返せば、条件Ｃ７を満たすデータ転送ネットワークにより、得られる効果を説明する。以下では、ノード数Ｎ＝５０、リンク数Ｌ＝７５、コアノード数Ｎｃｏｒｅ＝２０のときを例に説明する。
【０１７３】
ノード数Ｎ＝５０、リンク数Ｌ＝７５、コアノード数Ｎｃｏｒｅ＝２０のとき、一次縮約ネットワークＮＷ＊におけるコアノードのノード次数平均値ＫｃｏｒｅはＫｃｏｒｅ＝２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２＝４．５となる。平均値Ｋｃｏｒｅの回りの平均相対偏差をｄｋｃｏｒｅが一番小さくなる平均次数の分布は、ノード次数４のノードが１０個とノード次数５のノードが１０個とでなる分布である。この分布を１０Ｋ４＋１０Ｋ５のように表す。また、Ｄエッジノード数として取り得る最大値Ｄｍａｘは１となっている。なお、この分布を持つネットワークは、条件Ｃ１〜Ｃ３、Ｃ５を満たしており、Ｄエッジノード数Ｄが０か１ならば条件Ｃ４を満たしている。以下では、Ｄ＝０を例にする。このとき、Ｓエッジノード数Ｓは３０となり、Ｓエッジノードをどのようにコアノードに配分するかが問題となる。この場合、コアノードは、ノード次数面からは、１０個ずつの２種類のコアノードがあるため、３０個のＳエッジノードを２種類のコアノードに配分する仕方は、表２に示す３１通りがある。但し、表２において、ＳＫ４はノード次数４のコアノードに接続されたＳエッジノードの数を表し、ＳＫ５はノード次数５のコアノードに接続されたＳエッジノードの数を表している。
【表２】
2011114795.tif 000004
【０１７４】
ノード次数４のノードが１０個とノード次数５のノードが１０個とでなるネットワークも種々あり、平均中継数性能Ｈ及びネットワーク帯域性能Ｘｅｆｆについては平均値を表２に記述している。
【０１７５】
図９は、ノード次数４のコアノードへのＳエッジノードの配分数ＳＫ４と、平均中継数性能Ｈ及びネットワーク帯域性能Ｘｅｆｆの平均値の分布をＨ−Ｘｅｆｆ平面に示したものである。
【０１７６】
図９から分かるように、４次のコアノードにＳエッジノードを２０個、５次のコアノードにＳエッジノードを１０個それぞれ配分する仕方が、ネットワーク全体の平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性から見て優れていることが分かる。この配分方法は、より具体的には、１０個の４次のコアノードにそれぞれＳエッジノードを２個ずつ、かつ、１０個の５次のコアノードにそれぞれＳエッジノードを１個ずつ配分する方法であり、配分後のコアノードの次数は全てのコアノードについて６となる。この配分方法は、上述した「Ｓエッジノードの理想的な分配方法」に一致する。
【０１７７】
また、４次のコアノードへのＳエッジノード分配数（ＳＫ４）が２０未満の配分方法は、２０のときのネットワーク帯域性能Ｘｅｆｆよりは劣るものの、平均中継数性能Ｈで優れていることが分かる。すなわち、ネットワーク帯域性能Ｘｅｆｆに比較して平均中継数性能Ｈのウェイトを大きく捉えるならば、「Ｓエッジノードの理想的な分配方法」に比較し、低次のコアノードへの分配数を少なくし、高次のコアノードへの分配数を多くすれば良い。条件Ｃ７の後半は、このような場合を規定している。
【０１７８】
以上では、ノード数Ｎ＝５０、リンク数Ｌ＝７５、コアノード数Ｎｃｏｒｅ＝２０のときを例に説明したが、他の場合も同様である。
【０１７９】
条件Ｃ４〜Ｃ６を満たすネットワークの効果の説明で行った内容を整理すると、Ｈ−Ｘｅｆｆ限界性能とその近傍のネットワークで、平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性から見て優れたネットワークに見られるネットワーク構造的な特徴を、以下の（ｉ）、（ｉｉ）ようにまとめることができる。
【０１８０】
（ｉ）ネットワークは、ＳエッジノードがＤエッジノードと連結していないネットワーク構造であるコア・エッジ分離構造をとる。一次縮約ネットワークＮＷ＊でのコアノードのノード次数の平均値ＫｃｏｒｅはＫｃｏｒｅ＝２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２となっている。大きいコアノード数Ｎｃｏｒｅでは平均値Ｋｃｏｒｅ小さく、小さなコアノード数Ｎｃｏｒｅでは平均値Ｋｃｏｒｅは大きい。
【０１８１】
（ｉｉ）ネットワーク内を流れるトラフィックは、ほとんどコアノードを経由して中継される。すなわち、Ｓエッジノードはトラフィックを終端するだけでトラフィックを中継せず、Ｄエッジノードはほとんど中継せずに終端が主な機能である。このため、最大処理ノードはコアノードとなり、ネットワーク帯域性能である有効最大ノード数Ｘｅｆｆは、ほぼ最大でＸｅｆｆ〜Ｎｃｏｒｅ／３程度となる。コアノード数Ｎｃｏｒｅが大きければネットワーク帯域性能Ｘｅｆｆが大きく、コアノード数Ｎｃｏｒｅが小さければネットワーク帯域性能Ｘｅｆｆは小さくなる。トラフィックは、第０ホップ、第１ホップ、第２ホップ、…第ｈホップにより、平均して、上述した（２８）式の各項に記述された数のノードを経由して一次縮約ネットワークＮＷ＊内を伝わる。そのため、平均中継数Ｈは（２８）式の第２項目以上で、最大の最外殻層数ｈｓｈｅｌｌまでのホップ数の平均となる。これは、ほぼ最外殻層数ｈｓｈｅｌｌで決まる。一次縮約ネットワークＮＷ＊におけるコアノードのノード次数平均値Ｋｃｏｒｅが小さいと最外殻層数ｈｓｈｅｌｌは大きく、この平均値Ｋｃｏｒｅが大きいと最外殻層数ｈｓｈｅｌｌは小さい。このため、コアノード数Ｎｃｏｒｅが大きいネットワークだと平均中継数Ｈは大きく、コアノード数Ｎｃｏｒｅが小さいと平均中継数Ｈは小さい。
【０１８２】
次数が大きいノードには、確率的にトラフィックが集中する。トラフィック処理が一部のノードに偏るとネットワーク帯域性能Ｘｅｆｆが下がる。その反面、次数が大きいノード間を経由してトラフィックを中継すると、トラフィックの平均的中継数は小さくなる。
【０１８３】
条件Ｃ７が、図９のように、ネットワーク全体の平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性から見て優れている理由は、以下のように考えることができる。
【０１８４】
一次縮約ネットワークＮＷ＊においてノード次数が異なるコアノードがある場合、ノード次数平均値Ｋｃｏｒｅが大きければ大きいほど中継トラフィック量が多くなる傾向がある。このような場合、Ｓエッジノードをうまく配分して、コアノード間の処理量のばらつきをなくして均等化することができる。このような均等化することにより最大のネットワーク帯域性能Ｘｅｆｆを実現することができる。条件Ｃ７の前半部分の条件を満足すると、Ｓエッジノードがうまく配分されてこのノード処理量が均等化されて最大のネットワーク帯域性能Ｘｅｆｆが得られることが分かる。
【０１８５】
この最大のネットワーク帯域性能Ｘｅｆｆを与える配置より、ノード次数が大きいコアノードにＳエッジノードを片寄せることにより、ネットワーク帯域性能Ｘｅｆｆは下がるが、その分、平均中継数性能Ｈが優れたネットワーク構造が得られる。
【０１８６】
（Ａ−５）実施形態のデータ転送ネットワークの効果
実施形態のデータ転送ネットワークによれば、リンク数が稀なネットワークにおいて、少なくとも条件Ｃ１〜Ｃ３を満足しているので、ネットワーク帯域性能と平均中継数性能が優れたものとすることができる。条件Ｃ４〜Ｃ７の１以上を充足していると、ネットワーク帯域性能と平均中継数性能が一段と優れたものになる。
【０１８７】
（Ａ−６）実施形態のデータ転送ネットワークの第１実施例
図１０は、条件Ｃ１〜Ｃ７の全てを満足する、ノード数Ｎ＝５０、リンク数Ｌ＝７５のデータ転送ネットワークの一実施例の非正則なネットワーク構造を示している。
【０１８８】
図１０（Ａ）は、この実施例のネットワークの、Ｈ−Ｘｅｆｆ平面上の位置を表している。
【０１８９】
図１０（Ｃ）は、各コアノードの接続関係を配置図的に記述したものである。図１０（Ｃ）では、Ｓエッジノード、Ｄエッジノードの図示を省略し、全１０個のコアノードと、コアノード間の直接リンク（実線）を示している。図１０（Ｃ）の破線は、破線の両端のコアノード間にＤエッジノードを介した間接リンクがあることを表している。
【０１９０】
図１０（Ｂ）は、各コアノードの接続関係を表で記述したものである。各行は、コアノードの番号と、接続されているＳエッジノードの数と、直接リンクを介して接続している他のコアノードの番号と、間接リンクで接続されている他のコアノードの番号及び間接リンク数の組とからなっている。１番目の行は、番号「１」のコアノードの行であり、１個のＳエッジノードに繋がっており、番号３、７、９、１０のコアノードには直接リンクされており、番号２のコアノードには４本の間接リンクで繋がっており、番号４のコアノードには２本の間接リンクで繋がっており、番号５のコアノードには１本（１本の場合は表記が省略されている）の間接リンクで繋がっていることを表している。
【０１９１】
（Ａ−７）ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークについて
以下、上述の説明で種々用いたノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークについて、上述した条件との関係を整理して説明する。
【０１９２】
表３に、ノード数Ｎ＝５０、リンク数Ｌ＝７５のネットワークにおけるコア・エッジ分離構造の、一次縮約ネットワークＮＷ＊におけるコアノード次数の平均値Ｋｃｏｒｅ、平均相対偏差ｄｋｃｏｒｅを最小とするコアノード次数Ｋの分布、最外殻層数ｈｓｈｅｌｌ、Ｄエッジノード数として取り得る最大値Ｄｍａｘ、最大Ｄ値とそのときのＳ値とを示している。
【表３】
2011114795.tif 000005
【０１９３】
・平均値Ｋｃｏｒｅは２≦Ｎｃｏｒｅ≦Ｎの範囲で、Ｋｃｏｒｅ＝２（Ｌ−Ｎ）／Ｎｃｏｒｅ＋２で与えられる。
【０１９４】
・平均相対偏差ｄｋｃｏｒｅが平均値Ｋｃｏｒｅを中心に０．６以内ならば、条件Ｃ１〜Ｃ３を充足する。表３の平均相対偏差ｄｋｃｏｒｅを最小とするコアノード次数Ｋの分布は、コアノード数Ｎｃｏｒｅが５０（表３の１行目）以外は、全て、条件Ｃ１〜Ｃ３を充足する。
【０１９５】
・コアノード数Ｎｃｏｒｅがノード数Ｎに等しくなく、平均値Ｋｃｏｒｅが整数となれば、条件Ｃ４を充足する。コアノード数Ｎｃｏｒｅが２５、１０、５、２のときが、条件Ｃ４を充足するときである。
【０１９６】
・コアノード数Ｎｃｏｒｅの増加と共に最外殻層数ｈｓｈｅｌｌも増加する。ノード数Ｎ＝５０、リンク数Ｌ＝７５では、最外殻層数ｈｓｈｅｌｌは２から５までの整数値をとる。２から５までのそれぞれの最外殻層数値ｈｓｈｅｌｌで最大のコアノード数Ｎｃｏｒｅの値をもつ場合、条件Ｃ５を充足する。コアノード数Ｎｃｏｒｅが４８、３４、２０、８のときに条件Ｃ５を充足する。
【０１９７】
・Ｄ値がＤｍａｘ値以下の場合に条件Ｃ６を充足する。
【０１９８】
表３のＮｃｏｒｅ値、平均相対偏差ｄｋｃｏｒｅを最小とするコアノード次数Ｋの分布を持ち、Ｄ値がＤｍａｘ値以下の場合は、条件Ｃ１〜Ｃ３、Ｃ６を満たしたネットワーク構造である。
【０１９９】
具体的なネットワーク構造の一例として、コアノード数Ｎｃｏｒｅ＝３４で、コアノード次数Ｋの分布が１８Ｋ３，１６Ｋ４で、Ｄ＝０、Ｓ＝１６のネットワーク構造を２つ示す。前者が、実施形態のデータ転送ネットワークの第２実施例に該当し、後者が実施形態のデータ転送ネットワークの第３実施例に該当する。
【０２００】
［Ｎｃｏｒｅ＝３４、１８Ｋ３，１６Ｋ４、Ｄ＝０、Ｓ＝１６の例（１）］
表４に、各コアノードの番号、コアノードに接続されたＳエッジノードの数、各コアノードが接続している他のコアノードの番号を示している。各行の＃の後の番号がコアノードの番号である。コアノードに接続されたＳエッジノードの数は、コアノードの番号に続く；と：の間の数で表している。表４のような表現方法を、リンクテーブルという。
【表４】
2011114795.tif 000006
【０２０１】
表４のリンクテーブルで、実際のネットワーク構造が規定されている。
【０２０２】
この例のネットワーク構造は、Ｎｃｏｒｅ＝３４、１８Ｋ３，１６Ｋ４、Ｄ＝０、Ｓ＝１６となっている。
【０２０３】
ネットワーク全体の次数の分布は［０，１６，０，２，３２］となっている。ここで、用いられている［０，１６，０，２，３２］などの次数分布の表し方は、０次ノードの数から始まり、次数をひとつずつ増やしたときのノード数の数列で表している。このネットワークのＳエッジノードの配置は、条件Ｃ７の前半部分を充足する配置となっている。
【０２０４】
このネットワークの平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性は、Ｈ＝３．２６２０４０８、Ｘｅｆｆ＝８．９６８８８３で、これまで調べられてきたＮｃｏｒｅ＝３４のネットワークの中でも最大のネットワーク帯域性能Ｘｅｆｆを示す構造である。
【０２０５】
［Ｎｃｏｒｅ＝３４、１８Ｋ３，１６Ｋ４、Ｄ＝０、Ｓ＝１６の例（２）］
表５に、Ｎｃｏｒｅ＝３４、１８Ｋ３，１６Ｋ４、Ｄ＝０、Ｓ＝１６となる、別の構造をリンクテーブルで示す。
【表５】
2011114795.tif 000007
【０２０６】
ネットワーク全体の次数分布も、例（１）と同様に［０，１６，０，２，３２］であり、また、例（１）と同様に、このネットワークのＳエッジノードの配置も、条件Ｃ７の前半部分を充足する。
【０２０７】
このネットワークの平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性は、Ｈ＝３．２３５９１８４、Ｘｅｆｆ＝８．８１２９５０で、これまで調べられてきたＮｃｏｒｅ＝３４のネットワークの中でも最小の平均中継数性能Ｈで、その平均中継数性能Ｈにおいて最大のネットワーク帯域性能Ｘｅｆｆを示す構造である。
【０２０８】
以上、ノード数Ｎ＝５０、リンク数Ｌ＝７５で、Ｎｃｏｒｅ＝３４、１８Ｋ３，１６Ｋ４、Ｄ＝０、Ｓ＝１６となる２つの実施例（第２実施例、第３実施例）を示したが、２つの実施例から分かるように、優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を持った実際のネットワーク構造を見出すためには、条件Ｃ１〜Ｃ７のいくつかを組み合わせて（但し、少なくとも条件Ｃ１〜Ｃ３を含む）、表４や表５のリンクテーブルのＮｃｏｒｅ数、各コアノードのリンク先の数というリンクテーブルの枠組みを決め、その枠組みの中で実際のコアノード間の繋がり方を決めていけば良いことが分かる。このような決定方法については後述する。
【０２０９】
（Ａ−８）ノード数Ｎ＝３００００、リンク数Ｌ＝６１５００のネットワークについて
次に、ノード数Ｎやリンク数Ｌが、インターネット規模と同程度の規模のネットワークについて、上述した条件との関係を説明する。
【０２１０】
インターネットの規模は、ＡＳ（アプリケーションサーバ）レベルでＮ＝３００００、Ｌ＝６１５００となっている。インターネットの構造は、上述した非特許文献１の第４節に示されているように、複雑ネットワークで、平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性はＨ≒３．８、Ｘｅｆｆ≒６程度と見積もられている。
【０２１１】
ノード数Ｎ＝３００００、リンク数Ｌ＝６１５００での上述した表３に当たる表を、表６、表７に分けて示す。表６及び表７は、条件Ｃ４又はＣ５を満たすコアノード数Ｎｃｏｒｅを示したものである。
【表６】
2011114795.tif 000008
【表７】
2011114795.tif 000009
【０２１２】
ここでも、具体的なネットワーク構造の一例として、Ｎｃｏｒｅ＝２５２で、コアノード次数Ｋの分布が２５２Ｋ２５２で、Ｄ＝１２６、Ｓ＝２９６２２のネットワーク構造を示す。
【０２１３】
［Ｎｃｏｒｅ＝２５２、２５２Ｋ２５２、Ｄ＝１２６、Ｓ＝２９６２２の例］
２５２個のコアノードは、２５１本のリンクを用いてフルメッシュを組むことができる。残り一本のリンクは、１２６組の任意のコアノード対の間にＤエッジノードを仲介に張るリンクとして適用する。これで一次縮約ネットワークＮＷ＊の構造が得られる。この一次縮約ネットワークＮＷ＊の構造に対し、Ｓエッジノードをいずれかのコアノードに分配させれば、実際のネットワーク構造が得られる。
【０２１４】
Ｓエッジノードをどのように分配するかによって、平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性に特徴が生まれる。
【０２１５】
ネットワーク帯域性能Ｘｅｆｆの良い構造を得るにはなるべく構造にむらがないように作れば良い。Ｓエッジノードの数２９６２２は、２９６２２＝１１７×１１４＋１１８×（２５２−１１４）と分解されるため、１１４個のコアノードに１１７個のＳエッジノード繋ぎ、残り１３８個のコアノードに１個多い１１８個のＳエッジノードをつなぐことによりネットワークの構造を決めることができる。
【０２１６】
図１１に、このネットワークの構造を模式的に示す。
【０２１７】
図１１（Ａ）は、３００００ノードのうち、２５２個のコアノードを点ＰＣで表し、円形に配置したもので、図１１（Ｂ）は、コアノード間をフルメッシュになるようにリンクしている様子を一つのコアノードを代表させ、簡略して表している。図１１（Ｃ）では、点ＰＤでＤエッジノードを表し、二つおきにコアノードＰＣ間を繋げている。また、図１１（Ｃ）では、一つのコアノードＰＣを代表としてＳエッジノードが複数繋がっている様子を表している。Ｓエッジノードをここでは点ＰＳで表している。この構造では、実際には、１１７個のＳエッジノードが繋がっているコアノードは１１４個あり、残りの１３８個のコアノードには１１８個のＳエッジノードが繋がっている。
【０２１８】
このネットワークの平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性は、Ｈ＝２．９７９２３１６、Ｘｅｆｆ＝１２５．７７３５１５となっている。
【０２１９】
平均中継数性能Ｈがほぼ３となっているのは、コアノード間はフルメッシュのため１ホップでどのコアノード間もトラフィックが行き交うことが可能であるためである。大半のノードはＳエッジノードであるために、トラフィックの多くは、出発のＳエッジノードからコアノードに１ホップを要し、コアノード間に１ホップを使い、コアノードから出口のＳエッジノードに１ホップを要し、最大３ホップで行きつくことができる。それ以下のホップ数で出発ノードから出口ノードまで行きつけるトラフィックも若干あるため平均ホップ数は３より若干低めのＨ＝２．９７９２３１６という値をとると解釈される。
【０２２０】
ネットワーク帯域性能Ｘｅｆｆは、ほぼコアノード数Ｎｃｏｒｅ数２５２の半分である１２６に近い値となっている。Ｎｃｏｒｅ数のほぼ半分がネットワーク帯域性能Ｘｅｆｆになる理由は、ほとんどのトラフィックは、Ｓエッジノード間を行き交うトラフィックで、そのほとんどが、コアノードを２回中継ノードとして使用することによるためである。
【０２２１】
現状のインターネットでは、Ｈ≒３．８、Ｘｅｆｆ≒６程度であったので、図１１に示すネットワーク構造は、現状のインターネットより格段的に性能が良くなっている。すなわち、図１１に示したネットワーク構造は、現状のインターネットとノード数、リンク数が同規模であるが、平均中継数性能Ｈは小さく、なおかつ、ネットワーク帯域性能Ｘｅｆｆは約２０倍のトラフィックを流せる性能である。
【０２２２】
平均ホップ数（平均中継数）はネットワーク性能的に見て、送信遅延や信号品質に影響する。平均ホップ数が小さいとそれだけ、送信遅延が小さく信号品質は高くなる。平均ホップ数はこれらの信号特性以外にも、ネットワーク運用コストやネットワーク消費電力を直接示す指標でもある。
【０２２３】
平均中継数性能Ｈをネットワーク帯域性能Ｘｅｆｆで割ったＨ／Ｘｅｆｆは簡単に単位トラフィック当たりに必要なネットワーク運用コストやネットワーク消費電力を示す指標であり、図１１に示したネットワーク構造の例は、この指標で、現状のインターネットより約２６倍高いと言える。
【０２２４】
（Ｂ）データ転送ネットワークの構成方法の実施形態
次に、本発明によるデータ転送ネットワークの構成方法の４つの実施形態を、図面を参照しながら詳述する。
【０２２５】
各実施形態の構成方法は、上述した条件Ｃ１〜Ｃ７のうち、少なくとも条件Ｃ１〜Ｃ３を含む３個以上の条件を充足するデータ転送ネットワークを構成しようとしたものである。各実施形態の構成方法は、ノード数Ｎやリンク数やコアノード数Ｎｃｏｒｅなどの枠組みを決めた上で、初期状態のネットワーク構造を定め、ネットワーク全体のネットワーク帯域性能値や平均中継数性能値のどちらか一方、又は、両方を指標として最適化することで、最終的に、性能が良いデータ転送ネットワークを構成しようとしたものである。
【０２２６】
枠組みの中でコアノード間の繋げ方の決め方として、例えば、最初にランダムに決める方法が考えられる。ランダムに決めることにより、後述する図１２に示すようなネットワークの分布が得られる。ランダムな方法で得られた繋げ方を少しずつ替えた場合、平均中継数性能Ｈやネットワーク帯域性能Ｘｅｆｆが改善するときに、その繋ぎ替えを実施してゆくという最適化を繰り返す。このような最適化方法を適用することにより、Ｈ−Ｘｅｆｆ限界性能上若しくはＨ−Ｘｅｆｆ限界性能近傍のネットワークを得ることができる。
【０２２７】
条件Ｃ１〜Ｃ７を課す効果は、長時間の最適化作業なしで、後述する図１２に示される程度の優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を持ったネットウーク構造を導き出すことができる点であり、また、最適化方法を適用する場合に、最適化を始める出発点で条件Ｃ１〜Ｃ７のいくつかを満足するネットワーク構造を使用することにより、最適化作業に要する作業量を大幅に短縮できる点にある。これらの効果はノード数Ｎやリンク数Ｌが大きくなるほど大きくなると考えられる。
【０２２８】
ノード数Ｎ＝５０、リンク数Ｌ＝７５のときを例に、最適化方法を適用することによるメリットを具体的に説明する。
【０２２９】
図１２は、条件Ｃ１〜Ｃ７を備えたネットワークがそれぞれ示す平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性の分布を示したものである。図１２は、２≦Ｎｃｏｒｅ≦５０の全てＮｃｏｒｅについて示している。代表的なコアノード数Ｎｃｏｒｅについては、数値を示しており、その数値の下側に、そのコアノード数での分布が上下に伸びている。図１２の分布は、条件Ｃ１〜Ｃ７でそれぞれのノードを無作為に繋げて得られたものである。このような分布上のある位置のネットワーク構造に対し、ネットワーク全体のネットワーク帯域性能値Ｘｅｆｆと平均中継数性能値Ｈを指標として最適化することで、Ｈ−Ｘｅｆｆ限界性能上若しくはＨ−Ｘｅｆｆ限界性能近傍の、優れた平均中継数性能Ｈ−ネットワーク帯域性能Ｘｅｆｆ特性を持ったネットウーク構造を導き出すことができる。
【０２３０】
（Ｂ−１）データ転送ネットワークの構成方法の第１の実施形態
次に、データ転送ネットワークの構成方法の第１の実施形態として、単純試行法を説明する。図１３は、単純試行法の処理の流れを示すフローチャートである。
【０２３１】
例えば、コンピュータに単純試行法を実行するプログラム（単純試行法プログラム）を搭載し、オペレータと単純試行法プログラムの対話によって、単純試行法を実行する。後述する試行選択法、ランダムリンク張り替え法、ＧＡ最適化法も同様である。
【０２３２】
まず、オペレータはノード数Ｎ、リンク数Ｌを決定して入力する（ステップ１００）。ここでは、必要トラフィック総量（トラフィック帯域性能Ｘｅｆｆの下限）、必要ホップ特性（平均中継数性能Ｈの上限）、ネットワーク構築コスト、ネットワーク運用コスト、ネットワーク消費電力などの必要環境条件を満たすかを、トラフィック帯域性能や平均中継数性能を吟味しながら、しかも、使用ノード容量、使用伝送量（リンクの伝送可能な容量）などのネットワーク部材要件と整合するように決定する。この入力ステップでは、コンピュータは、Ｎ＜Ｌ＜３Ｎ、４Ｌ２＜Ｎ３の関係を確認するようにしても良い。
【０２３３】
次に、必要環境条件に係る項目に合わせて、ネットワークのコアノード数Ｎｃｏｒｅの候補を算出する（ステップ１０１）。例えば、ノード数Ｎ、リンク数Ｌ、必要環境項目の値から、コアノード数Ｎｃｏｒｅを算出する算出式を予め決定しておき、コアノード数Ｎｃｏｒｅを算出する。なお、コアノード数Ｎｃｏｒｅをもオペレータが入力するようにしても良い。
【０２３４】
コアノード数Ｎｃｏｒｅの候補が得られると、この候補の近傍に、条件Ｃ４及びＣ５を満たす値があるか否かを判断し、あれば、コアノードの次数分布を定めて、後述するステップ１０３に移行し、条件Ｃ４及びＣ５を満たす値がなければ、近傍と捉える範囲が妥当か、条件Ｃ４及びＣ５を満たさなくても良いかなどの再検討を行い、再検討でも、適切なコアノード数を定められない場合には、上述したステップ１００に戻り、再検討で適切なコアノード数を定めた場合には、コアノードの次数分布を定めて、後述するステップ１０３に移行する（ステップ１０２）。例えば、コアノード数Ｎｃｏｒｅの候補の近傍に、条件Ｃ４及びＣ５を満たす値があるか否かの判断はコンピュータが自動的に実行する。コアノードの次数分布の決定も、コンピュータが自動的に実行するようにしても良い。例えば、ノード数Ｎ、リンク数Ｌで定まる平均ノード次数Ｋを算出した後、その所定倍をコアノードに係る平均ノード次数とし、そのコアノードに係る平均ノード次数を、できるだけ少ない種類のノード次数で達成するようにコアノードの次数分布を決定する。
【０２３５】
以上のようにして、適用するノード数Ｎ、リンク数Ｌ、コアノード数Ｎｃｏｒｅが揃い、コアノードの次数分布が定まると、ノード数Ｎ、リンク数Ｌ、コアノード数Ｎｃｏｒｅから、条件Ｃ６を充足するように、Ｄエッジノード数の上限Ｄｍａｘを決定し、０≦Ｄ≦Ｄｍａｘの範囲内のＤをランダムに定めた後、Ｓエッジノード数をＳ＝Ｎ−Ｄ−Ｎｃｏｒｅで定め、全次数分布を決定する（ステップ１０３）。このステップ１０３以降の処理は、例えば、全てコンピュータが実行する。なお、コアノードの次数分布を決定する際、又は、全次数分布を決定する際には、条件Ｃ２を充足することを確認する。
【０２３６】
次に、Ｓエッジノードを除いたノード（コアノード及びＤエッジノード）について、ノード次数の小さいものから順に、そのノードのリンク先を多重リンクにならないようにランダムに決定することを繰り返し、一次縮約ネットワークを形成する（ステップ１０４）。一次縮約ネットワークの形成中において、多重リンクが生じることを避けることができなくなったり、一次縮約ネットワークが連結されていないものとなったりした場合には、ステップ１０４に戻って、一次縮約ネットワークの形成を最初からやり直す（ステップ１０５）。
【０２３７】
一次縮約ネットワークが形成されると、Ｓ個のＳエッジノードをＮｃｏｒｅ個のコアノードにランダムにリンクさせ、ネットワーク構造を完成させる（ステップ１０６）。ステップ１０６の処理により、条件Ｃ１は充足されることになる。完成されたネットワーク構造について、条件Ｃ３が充足していることを確認する。また、条件Ｃ７の充足も要件としている場合には、完成されたネットワーク構造について、条件Ｃ７が充足していることを確認する。なお、条件Ｃ３やＣ７が充足していない場合には、例えば、ステップ１０４に戻って、一次縮約ネットワークの形成を最初からやり直す。
【０２３８】
（Ｂ−２）データ転送ネットワークの構成方法の第２の実施形態
次に、データ転送ネットワークの構成方法の第２の実施形態として、試行選択法を説明する。図１４は、試行選択法の処理の流れを示すフローチャートであり、上述した図１３との同一、対応ステップには同一符号を付して示している。
【０２３９】
試行選択法において、入力されたノード数Ｎ及びリンク数Ｌからコアノード数Ｎｃｏｒｅを定め、その後、コアノードの次数分布を定めるまでの処理（ステップ１００〜１０２）は、単純試行法と同様である。
【０２４０】
この試行選択法では、ステップ１０３〜１０６でなるネットワーク構造の決定処理を、ループ処理として複数回実行する（ステップ１０７）。そして、得られた複数のネットワーク構造の中から、トラフィック帯域性能及び平均ホップ性能の少なくとも一方を反映させた評価式（例えば、両性能値の重み付け加算値）に基づいて、最良のネットワーク構造を選択する（ステップ１０８）。
【０２４１】
ここで、ステップ１０３〜１０６でなるネットワーク構造の決定処理の繰り返し回数は固定回数であっても良く、また、最良基準以上のネットワーク構造が見つかるまで繰り返す、回数が固定値でないもの（但し、打ち切り回数を設定してあっても良い）であっても良い。後者の場合、新たなネットワーク構造が決定されると、評価値が最良基準以上か否かを判別し、最良基準以上であればそこで繰り返しを終了させ、最良基準未満であれば、今までの中の最良のネットワーク構造とどちらが良好かを判断し、その時点で最も良好なネットワーク構造を定めておく。
【０２４２】
（Ｂ−３）データ転送ネットワークの構成方法の第３の実施形態
次に、データ転送ネットワークの構成方法の第３の実施形態として、ランダムリンク張り替え法を説明する。図１５は、ランダムリンク張り替え法の処理の流れを示すフローチャートであり、上述した図１３との同一、対応ステップには同一符号を付して示している。
【０２４３】
ランダムリンク張り替え法において、入力されたノード数Ｎ及びリンク数Ｌからコアノード数Ｎｃｏｒｅを定め、その後、コアノードの次数分布を定めるまでの処理（ステップ１００〜１０２）は、単純試行法と同様である。
【０２４４】
以上のようにして、適用するノード数Ｎ、リンク数Ｌ、コアノード数Ｎｃｏｒｅが揃い、コアノードの次数分布が定まると、ノード数Ｎ、リンク数Ｌ、コアノード数Ｎｃｏｒｅから、条件Ｃ６を充足するように、Ｄエッジノード数の上限Ｄｍａｘを決定し、０≦Ｄ≦Ｄｍａｘの範囲内のＤをランダムに定めた後、Ｓエッジノード数をＳ＝Ｎ−Ｄ−Ｎｃｏｒｅで定め、全次数分布を決定し、さらに、Ｓ個のＳエッジノードをＮｃｏｒｅ個のコアノードにランダムにリンクさせる（ステップ１５０）。なお、このステップ１５０の処理は、単純試行法と同様に、ステップ１０３とステップ１０６とに分かれていても良い。
【０２４５】
次に、Ｓエッジノードを除いたノード（コアノード及びＤエッジノード）について、ノード次数の小さいものから順に、そのノードのリンク先を多重リンクにならないようにランダムに決定することを繰り返し、一次縮約ネットワークの部分を形成する（ステップ１０４）。一次縮約ネットワークの部分の形成中において、多重リンクが生じることを避けることができなくなったり、一次縮約ネットワークが連結されていないものとなったりした場合には、ステップ１０４に戻って、一次縮約ネットワークの部分の形成を最初からやり直す（ステップ１０５）。
【０２４６】
一次縮約ネットワークの部分が形成されたときには、Ｓ個のＳエッジノードをＮｃｏｒｅ個のコアノードにランダムにリンクさせることが既に実行されているので、ネットワーク構造が完成される。
【０２４７】
ステップ１５０の後段の処理により、条件Ｃ１は充足されることになる。完成されたネットワーク構造について、条件Ｃ３が充足していることを確認する。また、条件Ｃ７の充足も要件としている場合には、完成されたネットワーク構造について、条件Ｃ７が充足していることを確認する。なお、条件Ｃ３やＣ７が充足していない場合には、例えば、ステップ１０４に戻って、一次縮約ネットワークの部分の形成を最初からやり直す。
【０２４８】
ネットワーク構造が完成されると、ステップ１５１〜１５３でなるループ処理を繰り返し実行する（ステップ１５４）。
【０２４９】
すなわち、Ｓエッジノードと繋がっているリンク以外のリンクから、ランダムに一つのリンクを選択して、移動か張り替えのうち、乱数で決まった方を実行する（ステップ１５１）。リンク移動後又はリンク張り替え後の状態が、多重リンクになったり、ネットワーク構造が連結でなくなったりした場合には、そのリンク移動やリンク張り替えを取り止めてステップ１５１に戻る（ステップ１５２）。リンク移動後又はリンク張り替え後のネットワーク構造が、多重リンクを備えず、連結されたものである場合には、トラフィック帯域性能及び平均ホップ性能の少なくとも一方を反映させた評価式に基づいて、リンク移動後又はリンク張り替え後のネットワーク構造が、その移動又は張り替え前のネットワーク構造より改善されたものであるか否かを判別し、改善されていなければ、リンク移動やリンク張り替えを取り止めてステップ１５１に戻り、改善されている場合には、改善されているネットワーク構造をその時点における決定候補とする（ステップ１５２）。ステップ１５３による改善されていないという結果が、所定回数連続して生じたときに、ステップ１５１〜１５３でなるループ処理を終了し、その時点のネットワーク構造の決定候補に、最終的にネットワーク構造を決定する。
【０２５０】
（Ｂ−４）データ転送ネットワークの構成方法の第４の実施形態
次に、データ転送ネットワークの構成方法の第４の実施形態として、ＧＡ（遺伝的アルゴリズム）最適化法を説明する。図１６は、ＧＡ最適化法の処理の流れを示すフローチャートであり、上述した図１５との同一、対応ステップには同一符号を付して示している。
【０２５１】
このＧＡ最適化法において、ステップ１５０までの処理は、ランダムリンク張り替え法と同様である。
【０２５２】
ＧＡ最適化法においては、上述したステップ１０４及びステップ１０５でなる処理を複数回繰り返し実行し、複数のネットワーク構造を形成する（ステップ２００）。このようにして形成されたそれぞれの遺伝子サンプルとする（ステップ２０１）。上述した表４や表５に示したリンクテーブルは、ネットワーク構造を一意に表現するものとなっており、各コアノード番号の接続関係は、各コアノード番号に対応付けられた遺伝子配列と見なすことができる。すなわち、ネットワーク構造を遺伝子サンプルとして用いることができる。
【０２５３】
次に、初期の遺伝子サンプルとして複数の遺伝子サンプルをランダムに選択する（ステップ２０２）。次に、乱数などを用いて、交配、交叉、突然変異などの遺伝子操作によって、新たな遺伝子サンプルを形成させる（ステップ２０３）。このような遺伝子操作は、リンクの移動や張り替えに該当する。なお、遺伝子操作の結果である新たな遺伝子サンプル（ネットワーク構造）が、多重リンクになったり、ネットワーク構造が連結でなくなったりした場合には、ステップ２０３に戻って、新たな遺伝子サンプルを形成させ直す（ステップ２０４）。
【０２５４】
次に、新たな遺伝子サンプルを含めた複数の遺伝子サンプルの中から、トラフィック帯域性能及び平均ホップ性能の少なくとも一方を反映させた評価式に基づいて、最も優秀な遺伝子サンプルを決定し、決定した遺伝子サンプルが、その時点で候補となっている遺伝子サンプルより優秀（改善されたもの）か否かを確認し、優秀になっていれば、決定した遺伝子サンプルを候補の遺伝子サンプルとする（ステップ２０５）。決定した遺伝子サンプルが、その時点で候補となっている遺伝子サンプルより優秀であっても優秀でなくても、比較判断された複数の遺伝子サンプルの中から良好なものを選択すると共に、また、ステップ２０１で遺伝子サンプルとされた中からも選択し、ステップ２０３に戻る。
【０２５５】
最も優秀な遺伝子サンプルと決定された遺伝子サンプルが、その時点で候補となっている遺伝子サンプルより優秀（改善されたもの）でないという結果が、所定回数連続して生じたときに、遺伝的アルゴリズムを終了し、その時点で候補となっている遺伝子サンプル（ネットワーク構造）に、最終的にネットワーク構造を決定する。
【０２５６】
（Ｃ）データ転送ネットワークの評価方法の実施形態
次に、本発明によるデータ転送ネットワークの評価方法の実施形態を、図面を参照しながら詳述する。
【０２５７】
この評価方法では、ネットワーク構造が定まっている評価対象のネットワークを評価するものである。例えば、データ転送ネットワークの評価プログラムをコンピュータに搭載し、上述したリンクテーブルのようにネットワーク構造が記述された評価対象のネットワークの情報をコンピュータに入力することにより、コンピュータが評価プログラムを実行し、評価対象のネットワークを評価する。
【０２５８】
図１７は、実施形態のデータ転送ネットワークの評価方法における処理の流れを示すフローチャートである。
【０２５９】
まず、評価対象のネットワークの情報を取り込む（ステップ２５０）。そして、評価対象のネットワークが評価し得るものであるか否かを判別する（ステップ２５１）。例えば、ノード数Ｎ及びリンク数Ｌの関係が、Ｎ＞１０、Ｎ＜Ｌ＜３Ｎ、４Ｌ２＜Ｎ３の関係を満たしていない場合には、評価し得ないものとする。この場合には、その旨を通知する（ステップ２５２）。
【０２６０】
評価対象のネットワークが評価可能なものであると、上述した条件Ｃ１〜Ｃ７のそれぞれを充足しているか否かを検出する（ステップ２５３）。そして、充足している条件の組み合わせで定まる評価結果を、充足している条件の組み合わせと評価結果とを対応付けたテーブルから取り出し（ステップ２５４）、その評価結果を出力し（ステップ２５５）、一連の処理を終了する。
【０２６１】
例えば、条件Ｃ１〜Ｃ３のいずれか１つでも充足していない場合には、好ましくないネットワーク構造であることを表す評価結果とし、条件Ｃ１〜Ｃ３を満たしたものは、ネットワーク構造として好ましく、しかも、他の条件Ｃ４、…、Ｃ７の充足性が多いものほど、好ましい度合いを大きくした評価結果とする。
【０２６２】
なお、評価結果を点数化や段階化して出力するようにしても良い。また、平均中継数性能Ｈやネットワーク帯域性能Ｘｅｆｆの値を併せて出力するようにしても良い。
【０２６３】
実施形態の評価方法を適用することにより、データ転送ネットワークを、平均中継数性能Ｈやネットワーク帯域性能Ｘｅｆｆの面から評価することができる。
【０２６４】
（Ｄ）他の実施形態
本発明のデータ転送ネットワークの用途は限定されるものではない。リンクも、光信号を通すものであっても良く、また、電気信号を通すものであっても良く、さらに、有線、無線のいずれであっても良い。光ネットワークの場合において、ノードは、光信号を光のままに中継処理するものであっても良く、光信号を一旦電気信号に戻して中継先などを捉えて中継するものであっても良い。
【図１】
2011114795.tif 000010
【図２】
2011114795.tif 000011
【図３】
2011114795.tif 000012
【図４】
2011114795.tif 000013
【図５】
2011114795.tif 000014
【図６】
2011114795.tif 000015
【図７】
2011114795.tif 000016
【図８】
2011114795.tif 000017
【図９】
2011114795.tif 000018
【図１０】
2011114795.tif 000019
【図１１】
2011114795.tif 000020
【図１２】
2011114795.tif 000021
【図１３】
2011114795.tif 000022
【図１４】
2011114795.tif 000023
【図１５】
2011114795.tif 000024
【図１６】
2011114795.tif 000025
【図１７】
2011114795.tif 000026
【図１８】
2011114795.tif 000027