通信装置、通信システムおよび経路割当方法
【課題】通信効率の向上を図る。
【解決手段】通信装置１０は、経路算出部１１と経路割当制御部１２を備える。経路算出部１１は、ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２は、データ衝突が起きないように、かつネットワーク運用時に経路をより多く通信スロットに割当てられるような、通信スロットへの経路の割当てを行う。また、経路割当制御部１２は、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当てを選択する。
【解決手段】通信装置１０は、経路算出部１１と経路割当制御部１２を備える。経路算出部１１は、ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２は、データ衝突が起きないように、かつネットワーク運用時に経路をより多く通信スロットに割当てられるような、通信スロットへの経路の割当てを行う。また、経路割当制御部１２は、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当てを選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ通信を行う通信装置、通信システムおよび経路割当を行う経路割当方法に関する。
【背景技術】
【０００２】
インターネット等によるマルチメディアサービスの拡大に伴い、ネットワーク上を流れる情報量は飛躍的に増大し、情報通信ネットワークを流れるトラフィックは大きく増加している。
【０００３】
トラフィックが増加すると、例えば、ネットワークを構成するルータの内部では、同時に到着するパケット数が増えて、パケットのバッファリング回数が増えたり、またはルーティングテーブルにもとづく経路計算の制御にかかる負荷が増大したりすることになる。
【０００４】
このため、ルータ内には、パケットバッファに用いるための大容量メモリや、経路計算に用いるための高速メモリといった、消費電力の大きなメモリデバイスが配置されていた。
【０００５】
近年になって、省電力ネットワークの構築を望む声は多いが、上記のように、ネットワーク全体の消費電力は、特にルータにおける消費電力が大きく影響しており、ルータの消費電力をいかに低減するかがネットワーク省電力化の鍵といえる。
【０００６】
従来技術として、複数のネットワークの静的および動的な情報にしたがって適切なネットワークを選択する技術が提案されている（特許文献１）。また、パス経路設定の際に、当該リンクを通過することが見込まれるパス数をパラメータとする評価関数を用いてパスの経路設定を行う技術が提案されている（特許文献２）。さらに、パケットに書き込まれている希望帯域情報にしたがって仮想的に帯域割当を行って帯域不足を解消する技術が提案されている（特許文献３）。さらにまた、各ノードが最良隣接ノードの情報をやりとりし、最良隣接ノードの情報をネットワークコアへ近づくための情報に用いてコアへ向かう通信路を作る技術が提案されている（特許文献４）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００１−２１７８７０号公報
【特許文献２】特開２００７−１４２６０９号公報
【特許文献３】特開平９−１４９０３８号公報
【特許文献４】特表２００７−５２３５４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
省電力ネットワークを構築する場合、ネットワークの管理を行うサーバ側で、送信すべきパケットのスロット（タイムスロット）をあらかじめ割当てて、時分割ベースでパケット転送を行う通信方式が考えられる。
【０００９】
これは、サーバが、どの時間で、どこの送信元からどこの宛先へ行くのかといったパケット転送のスケジューリングをしておいてから、パケット送出を行うものである。
このような制御を行うことにより、例えば、ルータに複数パケットが同時に到着するといった状態の発生頻度を低減させることができ、バッファリング回数を減少させることができる。このため、パケットバッファとして使用されていた消費電力の大きな大容量メモリをルータから排除することが可能になる。
【００１０】
また、例えば、ルータ自身が、従来行われていたような経路計算を実行せずに済むので、経路計算に要する負荷の軽減を図ることもでき、このため、経路計算時に使用されていた消費電力の大きな高速メモリを不要とすることが可能になる。なお、上記では、ルータの消費電力に注目して説明したが、ネットワークを構成するスイッチの消費電力についても同様の理由で低減可能である。
【００１１】
上記のようなパケット経路の割当によるスケジューリングを行うことにより、ルータの消費電力の低減化が可能になり、延いてはネットワーク全体の省電力化が可能になる。
一方、スケジューリングを行う場合に、帯域の有効活用を図ろうとして、少ないスロットにできるだけ多くの経路を割当てるといったスケジューリングを行うことが考えられる。
【００１２】
しかし、ネットワークの運用中は、トラフィックは常に変動するので、運用前のスケジューリングで用意した経路を上回る経路利用要求が発生する可能性がある。
すると、上記のようなスケジューリングでスタティックに決定されたスロットにもとづく帯域では、パケットを転送しきれないおそれがあり、さらに、トラフィック変動に伴って増加した経路に対応するために、あらためてスケジューリングをやり直さなければならなくなる。
【００１３】
このように、トラフィック変動に伴う経路の増加を想定せずに、スロットに多くの経路を単に詰め込むとしたスケジューリングでは、経路が増加したような場合には対応することができず、またスケジューリングをやり直すことになって非効率的であった。
【００１４】
本発明はこのような点に鑑みてなされたものであり、通信効率の向上を図った通信装置を提供することを目的とする。
また、本発明の他の目的は、通信効率の向上を図った通信システムを提供することを目的とする。
【００１５】
さらに、本発明の他の目的は、経路変動を想定したスロット割当のスケジューリングを行って、通信効率の向上を図った経路割当方法を提供することである。
【課題を解決するための手段】
【００１６】
上記課題を解決するために、通信装置が提供される。この通信装置は、ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、通信スロットに前記経路を割当てる経路割当制御部とを備える。また、経路割当制御部は、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当てを選択する。
【発明の効果】
【００１７】
通信効率の向上を図ることが可能になる。
【図面の簡単な説明】
【００１８】
【図１】通信装置の構成例を示す図である。
【図２】ネットワーク構成例を示す図である。
【図３】経路テーブルを示す図である。
【図４】スロットが使用している経路を示す図である。
【図５】スロットが使用している経路を示す図である。
【図６】スロットが使用している経路を示す図である。
【図７】期待値の計算フローを示す図である。
【図８】ネットワークの構成例を示す図である。
【図９】Min帯域デマンドのテーブルおよび最大公約数で割った値のテーブルを示す図である。
【図１０】経路テーブルとパステーブルを示す図である。
【図１１】最短ホップ数が記載されたテーブルを示す図である。
【図１２】リンクの使用状態／未使用状態が記載されたテーブルを示す図である。
【図１３】経路割当アルゴリズムの全体動作を示すフローチャートである。
【図１４】最大期待値算出の動作を示すフローチャートである。
【図１５】ネットワークトポロジを示す図である。
【図１６】ネットワークトポロジを示す図である。
【図１７】期待値計算結果を示す図である。
【図１８】通信装置の構成例を示す図である。
【図１９】グループ化されたネットワークを示す図である。
【図２０】グループ間を跨ぐスロット割当を示す図である。
【図２１】グループ間を跨ぐスロット割当の問題点を説明するための図である。
【図２２】パケット伝送の流れを示す図である。
【図２３】宛先アドレスと宛先ノードとの対応テーブルを示す図である。
【図２４】宛先アドレスと宛先ノードとの対応テーブルを示す図である。
【図２５】パケットバッファを示す図である。
【図２６】パケット伝送の流れを示す図である。
【図２７】通信システムの構成例を示す図である。
【図２８】パケット伝送の流れを示す図である。
【図２９】動作を示すフローチャートである。
【図３０】動作を説明するための図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態を図面を参照して説明する。図１は通信装置の構成例を示す図である。通信装置１０は、経路算出部１１と経路割当制御部１２を備える。通信装置１０は、例えば、ネットワークの管理サーバなどに設置される。
【００２０】
経路算出部１１は、ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２は、ネットワーク運用前に通信スロットへの経路の割当てを行う。この場合、データ衝突が起きないように、かつ経路変動に対応できるようにネットワーク運用時にも経路をより多く通信スロットに割当てられるような、通信スロットへの経路の割当てを行う。
【００２１】
ここで、経路割当制御部１２は、複数の通信スロットに経路を割当てる際に、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当てを選択する。
【００２２】
このような構成を有することにより、例えば、ネットワークのトラフィック変動に伴って経路が増加したような場合であっても、ネットワーク運用中に経路を割当てることができ、柔軟に対応することが可能になる。
【００２３】
また、経路割当のスケジューリングをやり直す必要がなく、通信効率の向上を図ることが可能になる。なお、以降の説明では、通信スロットを単にスロットと呼ぶ。また、スロットに経路を割当てることを、経路を埋め込むといった表現も使用する。
【００２４】
次に“スロット”、“経路”および“パス”の用語について説明する。“スロット”とは、パケットを送るための一定長の時間間隔のことで、フレームの中で、一定範囲の固定した時間間隔を占める。ある特定番号のスロットは、フレーム内に１つあり、フレームは周期的に繰り返されるため、その中にある特定番号のスロットも同じ周期で繰り返される。
【００２５】
“経路”とは、発エッジノードと着エッジノードの組合せとして定義される（通常、発着ノード間の中継ノードは意識しない）。また、経路に対しては、所望帯域としての帯域デマンドが与えられる。さらに、経路は（帯域に合わせて割当てられた）１つ以上のパスを含む。
【００２６】
“パス”とは、１つのスロット内で発エッジノードから着エッジノードに至るリンク（ノード間を結ぶ伝送路）の組合せとして定義される。１つのパスの帯域は、帯域割当ての最小単位であり、（リンク速度／スロット数）である。
【００２７】
次に期待値（経路埋め込み期待値）について説明する。期待値は、スロットへの経路の割当可能数の指標となるもので、１スロット当り、全経路の何％を埋め込めるかを表す。
ここで、スロットの最大数をＳ、経路数をＣ、ノード間のリンク速度をｖ、１スロットの帯域をｂとし、ｎ（＝ｖ／ｂ）個のスロットに割当可能な経路の総和をｋとした場合に、期待値は、以下の式（１）で定義する。
【００２８】
期待値＝（Σスロットｎに埋め込み可能な経路数）／（経路数×最大スロット数）
＝ｋ／（Ｃ×Ｓ）・・・（１）
期待値は、０〜１の範囲の値をとり、０の場合は、これ以上経路を埋める余裕がないことを示し、１の場合は、最大まで経路を埋める余裕があることを示す。
【００２９】
期待値の大きい方が、トラフィック変動に伴う経路変化にとって好ましい状態であると見なす（期待値が大きいことは、経路埋め込み余裕度が大きいということなので、経路増加要求があっても、運用中において、経路をスロットにダイナミックに埋め込むことができる）。
【００３０】
次に経路数の算出および期待値の計算例について図２〜図５を用いて説明する。図２はネットワーク構成例を示す図である。以降では、エッジノードを四角枠で示し、中継ノードを丸枠で示す。
【００３１】
ネットワークＮ１は、エッジノード１〜４および中継ノード５、６を含む。エッジノード１と中継ノード５が接続し、エッジノード２と中継ノード５が接続し、エッジノード３と中継ノード６が接続し、エッジノード４と中継ノード６が接続する。また、中継ノード５と中継ノード６が接続する。
【００３２】
ネットワークＮ１において、エッジノード間をフルメッシュで結ぶと経路数は１２となる（エッジ間を結ぶ途中の中継ノードも示すと、1→5→2、1→5→6→3、1→5→6→4、2→5→1、2→5→6→3、2→5→6→4、3→6→5→1、3→6→5→2、3→6→4、4→6→5→1、4→6→5→2、4→6→3の計１２経路）。
【００３３】
図３は経路テーブルを示す図である。始点エッジノードから終点エッジノードへの経路に番号を振ったテーブルＴ０を示している。あるスロット（スロットｓ１とする）が仮に未使用の場合、スロットｓ１には、テーブルＴ０のどの経路でも１つは埋めることが可能である。すなわち、「スロットｓ１に埋め込み可能な経路数」は１２となる。
【００３４】
図４はスロットが使用している経路を示す図である。図４に示す太矢印の経路（１）の1→5→2のルートが、スロットｓ１に現在埋め込まれていたとする。この状態に対して、あとどれだけの経路を経路（２）〜（１２）の中から選んで埋め込むことができるかを考える。
【００３５】
ここで、“埋め込む”、“埋め込めない”とは、すでにスロットに埋め込まれている経路に対し、その経路のリンクと、データ転送方向が同じリンクを共有しない経路であればデータ衝突が起きず、そのスロットに該当経路を埋め込むことができる。
【００３６】
また、すでにスロットに埋め込まれている経路に対し、その経路のリンクと、データ転送方向が同じリンクを共有するようなリンクを含んでいる経路は、データ衝突が生じるため、そのスロットには該経路を埋め込むことができない。
【００３７】
図４に示すように、エッジノード１から中継ノード５へのデータ転送方向のリンクをリンクＬ１、中継ノード５からエッジノード２へのデータ転送方向のリンクをリンクＬ２とする。
【００３８】
例えば、経路（２）の1→5→6→3のルートを見た場合、リンクＬ１が経路（１）と経路（２）で共有することになるので、経路（１）がすでに埋め込まれているスロットｓ１に対しては、経路（２）は埋め込めない。
【００３９】
これに対し、経路（９）の3→6→4のルートは、リンクＬ１、Ｌ２を共有しないので、経路（９）は、スロットｓ１に埋め込むことができる。また、経路（４）の2→5→1のルートでは、リンクＬ１、Ｌ２のデータ転送方向とは逆方向にデータを転送するので、リンクＬ１、Ｌ２を共有していることにはならず、経路（４）は、スロットｓ１には埋め込むことができる。
【００４０】
このような考え方で、経路（１）がすでに埋め込まれているスロットｓ１に埋め込み可能な経路を見つけると、この例の場合、経路（４）、（５）、（６）、（７）、（９）、（１０）、（１２）の７つある。したがって、経路（１）がすでに埋め込まれているスロットｓ１に対し、「スロットｓ１に埋め込み可能な経路数」は７となる。
【００４１】
図５、図６はスロットが使用している経路を示す図である。スロットが全部で４（＝ｎ）つあるとし（スロットｓ１〜ｓ４）、スロットｓ１〜ｓ４のそれぞれには図５、図６に示すような利用状況で経路が現在埋め込まれているとする。
【００４２】
すなわち、図５に対し、スロットｓ１、ｓ２には、経路（１）が埋め込まれ、図６に対し、スロットｓ３には、経路（２）が埋め込まれており、スロットｓ４には、経路は何も埋め込まれていないとする。
【００４３】
この場合、スロットｓ１〜ｓ４に埋め込み可能な経路数を上述したような考え方で求めると、スロットｓ１に対してさらに埋め込み可能な経路数は７、スロットｓ２に対してさらに埋め込み可能な経路数は７となる。また、スロットｓ３に対してさらに埋め込み可能な経路数は６、スロットｓ４に対して埋め込み可能な経路数は１２となる。
【００４４】
したがって、スロットｓ１〜ｓ４に埋め込み可能な経路数の総和は、（７＋７＋６＋１２）であり、ネットワークＮ１の全経路数は１２であり、最大スロット数は４であるので、式（１）から期待値は、（７＋７＋６＋１２）÷（１２×４）＝０．６７となる。
【００４５】
このことは、ネットワークＮ１の経路１２個を１００％とした場合、およそ６７％に相当する経路がスロットｓ１〜ｓ４にまだ埋め込むことが可能であることを示していることになる。
【００４６】
次に期待値の計算フローについて説明する。図７は期待値の計算フローを示す図である。なお、１つ目のパス（発エッジノード→着エッジノード）に関して、スロットｓに収容する経路のリンクの組み合わせは、例えば、ダイクストラ法（Dijkstra法：最短経路問題を解くための汎用的な計算アルゴリズム）で求められているとする。
【００４７】
〔Ｓ１〕経路カウンタのカウント値ｋに０を代入し、スロット番号ｓに１を代入する。
〔Ｓ２〕経路番号ｒに１を代入する。
〔Ｓ３〕スロットｓに経路ｒが埋め込み可能であり、かつ最短ホップ数＋α以上のホップ数を持つ経路であるか否かを判断する（α＝１、２、３、・・・）。最短ホップ数＋α以上の経路であればステップＳ４へいき、最短ホップ数＋α未満の経路であればステップＳ５へいく。
【００４８】
〔Ｓ４〕経路カウンタのカウント値ｋを増加する。
〔Ｓ５〕経路番号ｒを増加する。
〔Ｓ６〕経路番号ｒが最大経路数Ｒを超えたか否かを判断する。超えた場合はステップＳ７へいき、超えない場合はステップＳ３へ戻る。
【００４９】
〔Ｓ７〕スロット番号ｓを増加する。
〔Ｓ８〕スロット番号ｓが最大スロット数Ｓを超えたか否かを判断する。超えた場合はステップＳ９へいき、超えない場合はステップＳ２へ戻る。
【００５０】
〔Ｓ９〕期待値を計算する（期待値＝経路カウント値ｋ／（最大経路数Ｒ×最大スロット数Ｓ））。
ここで、ステップＳ３の処理について説明する。例えば、発ノードＡから着ノードＢへの経路として、経路＃１１〜＃１４があり、経路＃１１〜＃１４は、スロットｓに現在埋め込まれている経路のリンクとデータ転送方向が同一でないリンクを有しているとする（すなわち、どれも埋め込み可能な経路である）。また、経路＃１１のホップ数が１０、経路＃１２のホップ数が１１、経路＃１３ホップ数が１２、経路＃１４のホップ数が１３であったとする。
【００５１】
このとき、上限値αを３とすると、最短ホップ数は１０であるので、ホップ数が１３（＝１０＋３）となる経路である経路＃１４は、ステップＳ３の判断処理により、該当スロットに埋め込まれないことになる（経路＃１１〜＃１３までがスロットに割当てられる）。
【００５２】
すなわち、経路＃１１〜＃１４は、スロットｓに現在埋め込まれている経路のリンクとデータ転送方向が同一でないリンクを有しているので、この条件だけなら、現状のスロットｓに全部を埋め込むことができる。しかし、ステップＳ３に示すようなホップ数の制約条件も付加することにより、発着間のホップ数が許容範囲を超えるものは除外するということである。
【００５３】
このように、上限値αを設けて、最短ホップ数＋α以上のホップ数を持つ経路は、スロットにすでに埋め込まれている経路とデータ転送方向が同一のリンクを有していない経路であっても除外するようにした。これにより、迂回路が多く存在するネットワークトポロジの場合に、ホップ数の長い経路がパケット転送の通信路に選択されるといったことを防ぐことが可能になる。
【００５４】
次に図５、図６に示したスロット割当状態を例にして、図７に示したフローを使った期待値の計算動作について説明する。なお、期待値計算フローのステップＳ８からステップＳ２へ戻るループを外側ループ、ステップＳ６からステップＳ３へ戻るループを内側ループと呼ぶ。
【００５５】
全スロットが４つあるので、外側ループは４回回り、スロット番号ｓは１→４と変化する。また、とりうる経路数が１２個あるので、外側ループ毎に経路番号ｒは１→１２へと変化する。
【００５６】
（外側ループの１回目処理）
ステップＳ１によりｓ＝１、ｋ＝０であり、ステップＳ２によりｒ＝１から開始する。
内側ループの１回目では、スロットｓ１に経路（１）は埋め込むことができないので、ステップＳ３の判断がnoであり、ステップＳ５でｒ＝２となる。また、ステップＳ６の判断がnoであるため、ステップＳ３へ戻る（ｋ＝０）。
【００５７】
内側ループの２回目では、スロットｓ１に経路（２）は埋め込むことができないので、ステップＳ３の判断がnoであり、ステップＳ５でｒ＝３となる。また、ステップＳ６の判断がnoであるため、ステップＳ３へ戻る（ｋ＝０）。
【００５８】
内側ループの３回目では、スロットｓ１に経路（３）は埋め込むことができないので、ステップＳ３の判断がnoであり、ステップＳ５でｒ＝４となる。また、ステップＳ６の判断がnoであるため、ステップＳ３へ戻る（ｋ＝０）。
【００５９】
内側ループの４回目では、スロットｓ１に経路（４）を埋め込むことができるので、ステップＳ３の判断がyesであり、ステップＳ４でｋ＝１となる。また、ステップＳ５でｒ＝５となり、ステップＳ６の判断がnoなので、ステップＳ３へ戻る（ｋ＝１）。
【００６０】
内側ループの５回目では、スロットｓ１に経路（５）を埋め込むことができるので、ステップＳ３の判断がyesであり、ステップＳ４でｋ＝２となる。また、ステップＳ５でｒ＝６となり、ステップＳ６の判断がnoなので、ステップＳ３へ戻る（ｋ＝２）。
【００６１】
以降同様にして、内側ループの１１回目では、スロットｓ１に経路（１１）は埋め込むことができないので、ステップＳ３の判断がnoであり、ステップＳ５でｒ＝１２となる。また、ステップＳ６の判断がnoであるため、ステップＳ３へ戻る（ｋ＝６）。
【００６２】
内側ループの１２回目では、スロットｓ１に経路（１２）を埋め込むことができるので、ステップＳ３の判断がyesであり、ステップＳ４でｋ＝７となる。また、ステップＳ５でｒ＝１３となり、ステップＳ６の判断がyesとなるので、ステップＳ７へいく。ステップＳ７によりｓ＝２となり、ステップＳ８はnoなので、ステップＳ２へ戻る。
【００６３】
（外側ループの２回目処理）
ｓ＝２、ｋ＝７から開始する。内側ループ１回目（ｒ＝１）では、スロットｓ２には経路（１）は埋め込めない（ｋ＝７）。以降同様にして、内側ループ１２回目（ｒ＝１２）では、スロットｓ２には経路（１２）を埋め込めるのでｋ＝１４となる。
【００６４】
（外側ループの３回目処理）
ｓ＝３、ｋ＝１４から開始する。内側ループ１回目（ｒ＝１）では、スロットｓ３には経路（１）は埋め込めない（ｋ＝１４）。以降同様にして、内側ループ１２回目（ｒ＝１２）では、スロットｓ３には経路（１２）は埋め込めない（ｋ＝２０）。なお、スロットｓ３は経路（４）、（７）、（８）、（９）、（１０）、（１１）を埋め込むことができる。
【００６５】
（外側ループの４回目処理）
ｓ＝４、ｋ＝２０から開始する。内側ループ１回目（ｒ＝１）では、スロットｓ４には経路（１）は埋め込めるのでｋ＝２１となる。以降同様にして、内側ループ１２回目（ｒ＝１２）では、スロットｓ４には経路（１２）は埋め込めるのでｋ＝３２となる。なお、スロットｓ４は、経路（１）〜（１２）のどれでも埋め込むことができる。
【００６６】
上記のようなループ処理を繰り返した後に、ステップＳ９により、期待値はｋ÷Ｒ÷Ｓ＝３２÷１２÷４＝０．６７と求まる。
次にスロットに経路を割当てる経路割当アルゴリズムの手順について説明する。なお、以下の［１］の内容は、主に経路算出部１１の動作に該当し、［２］の内容は、主に経路割当制御部１２の動作に該当する。
【００６７】
［１］全経路の最小帯域デマンド（Min帯域デマンド）を、その最大公約数（１スロットの帯域）で割算し、各経路に必要なパス数を求める。あわせて、スロット数を（リンク速度／１スロットの帯域）で決定する。なお、全経路数をＬ、全パス数をＭ、スロット数をｎとする。
【００６８】
［２］Ｍ個のパスを、下記手順（ａ）〜（ｇ）による期待値の演算・比較により、ｎ個のスロットに割当てる。
（ａ）１つ目のパス（発エッジノード→着エッジノード）を取り出し、スロットに収容するリンクの組合せを例えばDijkstra法で求める。
【００６９】
（ｂ）得られた組合せのホップ数が、「最短経路＋上限値」内に収まっているか判定する。
（ｃ）収まっていれば、当該パスを収容した時のスロットの期待値を求める。また、全経路に対し、これらがDijkstra法により収容可能か否かを判定し、収容可能な経路をカウントして、期待値を算出する。
【００７０】
（ｄ）（ａ）〜（ｃ）の手順を、任意のパスの任意のスロットに対して行う（Ｍ×Ｎ回の総当り演算）。
（ｅ）（ｄ）までの結果で得られた最大Ｍ×Ｎの演算の期待値を比較し、一番大きな値のものを確定パス（または確定経路）として決定し登録する。
【００７１】
（ｆ）割当てるべきパス（Ｍ個）から、（ｅ）で決定したパスを除き、このパス（残りＭ−１個のパス）の集合に対して、（ａ）〜（ｅ）の手順を行う。
（ｇ）（ａ）〜（ｆ）の手順を、割当てるべきパスがなくなるまで繰り返す。
【００７２】
次に例を示しながら経路割当アルゴリズムの動作について説明する。図８はネットワークの構成例を示す図である。ネットワークＮ２は、エッジノード０〜３および中継ノード４〜７を含む。エッジノード０と中継ノード４が接続し、エッジノード１と中継ノード５が接続し、エッジノード２と中継ノード６が接続し、エッジノード３と中継ノード７が接続する。また、中継ノード４、５が接続し、中継ノード５、７が接続し、中継ノード７、６が接続し、中継ノード６、４が接続する。
【００７３】
ネットワークＮ２における各経路のMin帯域デマンドを、0→2の経路が10Mbps、0→3の経路が5Mbps、1→3の経路が10Mbps、1→2の経路が5Mbps、2→1の経路が10Mbpsとする。
図９はMin帯域デマンドのテーブルおよび最大公約数で割った値のテーブルを示す図である。テーブルＴ１は、Min帯域デマンドをテーブル化したものである。また、テーブルＴ２は、Min帯域デマンドをその最大公約数（１スロットの帯域に該当）で割った値をテーブル化したものである。この例では、Min帯域デマンドの最大公約数は５であるので、割り算を行うとテーブルＴ２に示される値となる。
【００７４】
ここで、各経路のMin帯域デマンドに必要なパス数は、テーブルＴ２の数値をすべて合計した値となるので、全パス数Ｍは、Ｍ＝８（=2+1+1+2+2）となる（すなわち、0→2の経路のパス数は２、0→3の経路のパス数は１、1→2の経路のパス数は１、1→3の経路のパス数は２、2→1の経路のパス数は２であるので計８個）。
【００７５】
また、全経路数Ｌは、テーブルＴ２の０以外の数値が記された項目欄の数であり、５個あるのでＬ＝５となる。さらにスロット最大数ｎは、例えば、リンク速度が100Mbpsであり、１スロットの帯域を５とすると、１００／５＝２０となり、ｎ＝２０スロットとなる。
【００７６】
図１０は経路テーブルとパステーブルを示す図である。上記で求めた経路とパスに番号を付けてテーブルを作成すると、経路テーブルＴ１１およびパステーブルＴ１２となる。経路テーブルＴ１１は、５個の経路に番号＃１〜＃５を付けて作成したテーブルである。パステーブルＴ１２は、８個のパスに番号を付けて作成したテーブルである。
【００７７】
図１１は最短ホップ数が記載されたテーブルを示す図である。テーブルＴ３は、利用する経路が最短で何ホップで接続できるかのホップ数を示している。ネットワークＮ２のノード接続構成により、0→2、0→3、1→3、1→2、2→1のすべての経路に対し、最短ホップ数は３である。
【００７８】
図１２はリンクの使用状態／未使用状態が記載されたテーブルを示す図である。テーブルＴ４は、送信元ノード（ｓｒｃ）から宛先ノード（ｄｓｔ）を結ぶリンクごとに、すでにスロットに割当てられた使用済みのリンクを１、スロットに割当てられていない未使用のリンクに０を登録するテーブルである。このようなテーブルＴ４で、リンクの使用状態／未使用状態を管理して、１を書き込んだリンクを除外できるようにする。
【００７９】
なお、テーブルＴ４は、ｓｒｃ／ｄｓｔのペアの代わりに隣接行列（adjacency matrix）で保持してもよい。この場合、隣接行列を複数持ち、元の行列の１だった箇所に０を書き込むことで経路の除外を表現する。
【００８０】
次にテーブルＴ２に記載される経路（計５経路）について期待値を計算していく。経路は、テーブルＴ４で未使用となっているリンクを使って作ることができる最短経路を用いる。
【００８１】
スロットｓ０〜ｓ１９に対する経路＃１〜＃５割当の期待値の計算として例えば、経路＃１（0→2）をスロットｓ０に埋め込んだ場合の期待値はａ１となる（経路＃１をスロットｓ１に埋め込んだ場合に、あとどれぐらいの経路を埋め込むことができるかの指標がａ１となる）。経路＃１（0→2）をスロットｓ１に埋め込んだ場合の期待値はａ２となる。以降同様にスロットｓ１９まで期待値を計算する。
【００８２】
次の経路の期待値計算として、経路＃２（0→3）をスロットｓ０に埋め込んだ場合の期待値はｂ１となる。経路＃２（0→3）をスロットｓ１に埋め込んだ場合の期待値はｂ２となる。以降同様にスロットｓ１９まで期待値を計算する。
【００８３】
次の経路の期待値計算として、経路＃３（1→2）をスロットｓ０に埋め込んだ場合の期待値はｃ１となる。経路＃３（1→2）をスロットｓ１に埋め込んだ場合の期待値はｃ２となる。以降同様にスロットｓ１９まで期待値を計算し、以下同様にして経路＃５までの期待値を計算する。
【００８４】
このように、すべての経路＃１〜＃５に対して、すべてのスロットｓ０〜ｓ１９に仮に割当てた場合の期待値を計算する。そして、期待値を計算し終えたら、その中で最も期待値の大きいものを選択する（値の大きさが同じものがある場合はどれを選択してもよいが、例えば、スロット番号の小さいものを選択する）。
【００８５】
ここで、経路がＭ個（経路＃１〜＃Ｍ）あり、所定数のスロットに対して上記のような期待値計算をしたとする。そして例えば、経路＃２をスロットｓ０に埋め込んだ期待値が最も大きくなったとすると、この経路＃２を確定経路と呼び、確定経路を除いた（Ｍ−１）個の経路に対して、再び上記と同様な期待値計算を行うことになる。このような処理を繰り返して、結果的にＭ個の確定経路を求めることになる。
【００８６】
なお、経路決定に使用したリンクは、テーブルＴ４の該当箇所を１に登録し、使用済みにして以後の経路探索対象から除外する。
次に経路割当アルゴリズムの動作フローについて説明する。図１３は経路割当アルゴリズムの全体動作を示すフローチャートである。
【００８７】
〔Ｓ１１〕テーブルＴ２を作成する（Min帯域デマンドをその最大公約数で割った値をテーブル化する）。
〔Ｓ１２〕テーブルＴ３を作成する（各経路の最短ホップ数を求めてテーブル化する）。
【００８８】
〔Ｓ１３〕テーブルＴ２の参照位置（ａ、ｂ）をａ＝０、ｂ＝０に設定する。
〔Ｓ１４〕テーブルＴ２の参照位置（ａ、ｂ）の値が０か否かを判断する。０でなければステップＳ１５へいき、０ならばステップＳ１６へいく。
【００８９】
〔Ｓ１５〕経路が未使用のスロットが出てくるまで、すべてのスロットにおけるノードａから出発してノードｂに到達する最短経路を求めて、期待値をすべて算出する。
〔Ｓ１６〕テーブルＴ２の参照位置（ａ、ｂ）を１つ進める。
【００９０】
〔Ｓ１７〕テーブルＴ２の参照をすべて終えた場合はステップＳ１８へいき、終えていない場合はステップＳ１３へ戻る。
〔Ｓ１８〕期待値が最大の経路を選び、経路が利用するリンクについてテーブルＴ４の該当スロットの部分に１を書き込む。
【００９１】
図１４は最大期待値算出の動作を示すフローチャートである。
〔Ｓ２０〕スロット試行位置を０に設定する（すなわち、スロットｓ０からスタートする）。
【００９２】
〔Ｓ２１〕テーブルＴ４の該当箇所を参照して、ノードａから出発してノードｂに到達する最短経路をDijkstra法で求める。
〔Ｓ２２〕経路が求まらないか、テーブルＴ３の最短経路＋αよりも長い経路になってしまうかを判断する。経路が求まらない、またはテーブルＴ３の最短経路＋αよりも長い経路になってしまう場合はステップＳ２４へいく。また、経路が求まり、テーブルＴ３の最短経路＋αよりも長い経路にならない場合はステップＳ２３へいく。
【００９３】
〔Ｓ２３〕ａ、ｂ、スロット番号、期待値、経路を計算して保存する。
〔Ｓ２４〕スロット試行位置を１増やす。
〔Ｓ２５〕１つ前のスロットが完全未使用スロットかを判断する（テーブルＴ４の項目がすべて０かを判断する）。完全未使用スロットの場合はステップＳ２６へいき、そうでない場合はステップＳ２１へ戻る。
【００９４】
〔Ｓ２６〕保存したもののうちでもっとも期待値の高いものを選択する。
次に効果について説明する。図１５、図１６はネットワークトポロジを示す図である。ネットワークＮ１１は、スター型のトポロジであり、ネットワークＮ１２は、ツリー型のトポロジである。また、ネットワークＮ１３は、ラダー型のトポロジであり、ネットワークＮ１４は、簡易ラダー型のトポロジである。
【００９５】
図１７は期待値計算結果を示す図である。上記の４種類の基本的なトポロジにおいて、１０スロットの空きスロットに対して、フルメッシュの経路割当を行った場合の期待値を算出する。
【００９６】
スロットに経路を割当てる際の評価として、例えば、ランダムに割当てる場合、ホップ数の短い経路を優先的に割当てる場合、ホップ数の長い経路を優先的に割当てる場合、および本発明による割当てを行う場合があり、それぞれの場合において１００回ずつ試行して平均の期待値を算出した。
【００９７】
図１７に示すように、通信装置１０で実行する期待値計算がすべてのトポロジにおいて最大となる。すなわち、通信装置１０における経路割当制御を実行することにより、後から追加する経路数をより多く割当てることが可能になる。
【００９８】
次にグループ間を跨いでスロット割当を行って、パケット通信を行う通信装置および通信システムについて説明する。なお、送信すべきパケットに対して、経路が埋め込まれた、あるスロット（タイムスロット）のタイミングを割当てることを、そのパケットに対してのスロット割当と呼ぶ。
【００９９】
例えば、パケットｐ１をスロットｓ１（ｓ１はスロットに付与されるスロット番号）のタイミングで送信する場合、パケットｐ１にはスロットｓ１が割当てられるといった表現をする。
【０１００】
図１８は通信装置の構成例を示す図である。通信装置３０は、パケットにスロットを割当てるスロット割当部３１と、パケットバッファ３２とを備える。
スロット割当部３１は、直前のグループで割当てられたスロットで送信されたパケットを受信すると、直前のグループで割当てられた該スロットのスロット番号を、自グループに対応する番号である自通信スロット番号（自スロット番号）に変換する。また、パケットバッファ３２は、自スロット番号と、パケットとを対にして格納する。
【０１０１】
ここで、スロット割当部３１は、パケット送信時には、パケットをパケットバッファ３２から取り出し、自スロット番号を選択し、自スロット番号を持つスロットをパケットに割当てる。
【０１０２】
また、自スロット番号を選択しない場合は、自スロット番号よりも時間的に後で、かつ自スロット番号に対して最も時間差の小さなスロット番号を選択し、選択したスロット番号を持つスロットをパケットに割当てる。
【０１０３】
なお、スロット割当部３１とパケットバッファ３２とは、上記では、１台の装置に含まれる構成としたが、各機能が分離してもよい。例えば、スロット割当部３１がネットワークの運用管理を行う管理サーバに配置され、パケットバッファ３２がネットワーク内のノードに配置されるような構成にしてもよい。
【０１０４】
以下、通信装置３０の機能を適用したグループネットワークについて詳しく説明する。図１９はグループ化されたネットワークを示す図である。エッジノードＥ１〜Ｅ４がシリアルに接続し、中継ノードＲ１がエッジノードＥ１、Ｅ２の間に配置し、中継ノードＲ２がエッジノードＥ２、Ｅ３の間に配置し、中継ノードＲ３がエッジノードＥ３、Ｅ４の間に配置している。
【０１０５】
また、グループＧ１は、エッジノードＥ１、Ｅ２、中継ノードＲ１および管理サーバ２０−１を含み、グループＧ２は、エッジノードＥ２、Ｅ３、中継ノードＲ２および管理サーバ２０−２を含み、グループＧ３は、エッジノードＥ３、Ｅ４、中継ノードＲ３および管理サーバ２０−３を含む。
【０１０６】
グループ境界においてエッジノードが配置され、グループ間はエッジノードを通じて接続される。グループＧ１〜Ｇ３内の管理サーバ２０−１〜２０−３は、グループ内のエッジノードや中継ノードと通信を行い、各グループは独立して稼働する。
【０１０７】
エッジノードＥ１〜Ｅ４は、パケットの宛先IPアドレスと宛先エッジノードが対応した宛先対応テーブルと、宛先エッジノードと使用スロット番号が対応したスロット番号対応テーブルとを備える。
【０１０８】
エッジノードＥ１〜Ｅ４に、宛先対応テーブルに存在する宛先のパケットが到着した場合は、そのパケットにはすでにスロット割当済みであるので、管理サーバとの通信は行わずに、割当済みのスロットを使用する。これにより、管理サーバの負担削減およびスロット消費量の低減を図る。
【０１０９】
また、宛先対応テーブルに存在しない宛先のパケットが到着した場合は、そのパケットにはスロットが割当てられていないので、該パケットを受信したエッジノードは、エッジノードと通信する管理サーバに対して、スロット番号割当の要求を行う。
【０１１０】
図２０はグループ間を跨ぐスロット割当を示す図である。入側の最初のグループＧ１は、期待値が最も高いスロットを選ぶ。続いて、隣接する次段のグループは、１つ前のグループのタイムスロットに時間的に最も近いスロットを選ぶ。
【０１１１】
ここで、グループ間には時間差があるので、グループ境界に位置するエッジノードには、時間調整のためのバッファが備えられる。ただし、大容量のバッファを備えるのものではないため、パケットが留まる時間を少なくする必要がある。
【０１１２】
そのためには、１つ前のグループのタイムスロットに時間的に最も近いスロットを選ぶことになる。すなわち、後段のグループでは、隣接する前段のグループで割当てられたスロットと同じ時間、または後の時間に出現するスロットに最も近い時間のスロットを選択することになる。
【０１１３】
例えば、グループＧ１でスロットｓ１が割当てられた場合、グループＧ２では、スロットｓ１またはスロットｓ２を選択する。グループＧ１、Ｇ２で時間差がなく同一タイミングで稼働していた場合は、スロットｓ１が最良であり、このときは、ほとんどバッファリングせずに通過させることができる。
【０１１４】
また例えば、グループ間に時間差があって、グループＧ１のスロットｓ１に相当する時間では、グループＧ２ではスロットｓ５に相当していたとする。このとき、グループＧ１でスロットｓ１に割当てられたパケットは、グループＧ２ではスロットｓ５に割当てることが、バッファリングに要する時間が最も少なく、最も早く通過させる。
【０１１５】
しかし、スロットｓ５を使って送信するパケットが満杯のとき、この場合のバッファリング時間が最小となる最良のスロットは、スロットｓ５の直後のスロットｓ６を選択する。したがって、グループＧ２では、該パケットに対して、スロットｓ６の割当を行って通過させることになる。
【０１１６】
上記のような、グループ間でのスロット割当を行うことにより、エッジノードに大容量のバッファが不要となり、高速にパケット伝送を行うことが可能になる。
図２１はグループ間を跨ぐスロット割当の問題点を説明するための図である。グループＧ１〜Ｇ３がシリアルに接続し、グループＧ２とグループＧ４が接続する。グループＧ１は、エッジノードＥ１、Ｅ２、中継ノードＲ１、Ｒ２および管理サーバ２０−１を含み、グループＧ２は、エッジノードＥ２、Ｅ３、Ｅ５、中継ノードＲ３、Ｒ４および管理サーバ２０−２を含む。
【０１１７】
グループＧ３は、エッジノードＥ３、Ｅ４、中継ノードＲ５、Ｒ６および管理サーバ２０−３を含み、グループＧ４は、エッジノードＥ５、Ｅ６、中継ノードＲ７、Ｒ８および管理サーバ２０−４を含む。
【０１１８】
このようなネットワーク構成において、パケットｐ１は、白抜き矢印の経路ｍ１で伝送され、パケットｐ２は、黒塗り矢印の経路ｍ２で伝送されるとする。グループＧ１は、入側グループであるため、最初に到着したパケットｐ１に対して、最も期待値の高いスロットｓ１０を割当てる。
【０１１９】
また、グループＧ１〜Ｇ３は、同一タイミングで稼働しているとすると、グループＧ２もパケットｐ１にスロットｓ１０を割当てて経路ｍ１で送信し、グループＧ３もパケットｐ１にスロットｓ１０を割当てて経路ｍ１で送信する。
【０１２０】
一方、パケットｐ１の次にパケットｐ２がグループＧ１に到達した場合を考える。グループＧ１では、宛先対応テーブルに、到着したパケットの宛先があれば、すでにスロット割当済みなので、管理サーバ２０−１との通信を行わずに、パケットｐ２に対して割当済みのスロットを使用する。
【０１２１】
ここでは、エッジノードＥ１に到着したパケットの宛先は、エッジノードＥ２であり、経路ｍ１と経路ｍ２は同経路なので、パケット宛先は、既知であり、テーブル登録されている。
【０１２２】
したがって、グループＧ１内では、エッジノードＥ１は、管理サーバ２０−１との通信を行って、パケットｐ２に対してあらたなスロット割当を要求するといった制御はせずに、スロットｓ１０をそのまま使用して、エッジノードＥ２へパケットｐ２を伝送する。
【０１２３】
パケットｐ２は、グループＧ２のエッジノードＥ２に到着する。エッジノードＥ２において、経路ｍ１、ｍ２が分岐し、経路ｍ２は既知の経路ではないので、グループＧ２においてスロット割当が施される。この場合、パケットｐ２にとってグループＧ２は、入側のグループに相当するから、グループＧ２では、グループＧ２における最も期待値の大きなスロット割当を行うことになる。
【０１２４】
すなわち、パケットｐ２は、グループＧ１でスロットｓ１０が割当てられているが、スロットｓ１０とは関係のない、グループＧ２の中で最も期待値の大きなスロットが割当てられることになる。
【０１２５】
例えば、スロットｓ１０で到着したパケットｐ２に対し、グループＧ２内で最も期待値の大きなスロットｓ５０が割当てられる場合もある。このような場合、スロットｓ５０のタイミングでパケットｐ２を送信するには、スロットｓ１０からスロットｓ５０までの時間分を、エッジノードＥ２でバッファリングすることになり、遅延が増大することになる。
【０１２６】
上記のように、複数グループをパケットが通過する際、他グループでスロットが割当てられたパケットが到着した場合、該他グループで割当てられたスロット番号を無視したスロット割当を行って、パケット伝送が行われてしまうおそれがあり、遅延が増大してしまう。したがって、このような状況において、遅延低減を図ったスロット割当を行うことが必要である。
【０１２７】
次に上記課題を解決する通信装置３０の機能を適用したグループネットワークについて説明する。図２２はパケット伝送の流れを示す図である。宛先アドレス（10.0.3.1）のパケットｐ１が最初にグループＧ１に到着したときのパケット伝送の流れを示している。
【０１２８】
また、図２３、図２４に宛先アドレスと宛先ノードとの対応テーブルを示す。図２３に示すテーブルＴ１１は、図２２に示すエッジノードＥ１に含まれ、図２４に示すテーブルＴ１２は、図２２に示すエッジノードＥ２に含まれる。
【０１２９】
〔Ｓ３１〕宛先アドレス（10.0.3.1）のパケットｐ１がグループＧ１に到着する。エッジノードＥ１は、テーブルＴ１１にもとづき、宛先アドレスからグループＧ１内の宛先ノード番号Ｅ２を取得する。
【０１３０】
〔Ｓ３２〕エッジノードＥ１は、エッジノードＥ１から宛先ノードＥ２へ向かう経路がこの時点ではまだ存在せず見つからないため、管理サーバ２０−１にノード番号を通知して経路割当を依頼する。
【０１３１】
〔Ｓ３３〕管理サーバ２０−１は、最も期待値の高いスロットに経路を埋め込み、そのスロット(スロットｓ１０とする)をエッジノードＥ１へ通知する。
〔Ｓ３４〕エッジノードＥ１は、スロットｓ１０のタイミングを使ってパケットｐ１を送信する（スロットｓ１０を割当てたパケットｐ１を送信する）。
【０１３２】
〔Ｓ３５〕エッジノードＥ２は、事前に計算しておいたグループＧ１とグループＧ２とのスロット時間差をもとに、グループＧ１で割当てられたスロット番号を、グループＧ２での時間的に一番近い、グループＧ２に対応するスロット番号に変換する。この例では、時間差０と仮定すると、一番近いスロットは、グループＧ１と同じスロットｓ１０であり、スロットｓ１０に変換したとする。
【０１３３】
図２５にパケットバッファを示す。パケットバッファ３２は、各エッジノードに配置され、受信パケットのパケット内容と自スロット番号の２つの情報が保存される。また、本技術のスロット割当が行われない通常のIPネットワークから送信されたパケットも、エッジノードにおいて受信するので、これらのネットワークに関するパケット内容もパケットバッファ３２で保存される。
【０１３４】
エッジノードＥ２の例では、グループＧ１とグループＧ２とのスロット時間差をもとに計算された、グループＧ２での時間的に一番近いスロット番号（スロットｓ１０）と、そのスロット番号のタイミングで送信されるパケットｐ１の内容とが格納される。
【０１３５】
〔Ｓ３６〕エッジノードＥ２は、テーブルＴ１２にもとづき、宛先アドレスからグループＧ１内の宛先ノード番号Ｅ３を取得する。
〔Ｓ３７〕エッジノードＥ２は、エッジノードＥ２から宛先ノードＥ３へ向かう経路がこの時点ではまだなく見つからないため、管理サーバ２０−２にノード番号を通知して経路割当を依頼する。このとき、パケットバッファ３２に保存しておいた、自グループＧ２内での最適なスロット番号を取得し、このスロット番号（スロットｓ１０）も管理サーバ２０−２へ送る。
【０１３６】
〔Ｓ３８〕管理サーバ２０−２は、通知されたスロット番号に最も近い番号で、かつ空いているスロットを検出する。そして、検出した該スロットに経路を埋め込み、経路が埋め込まれたスロット番号（この例では、グループＧ１〜Ｇ３は時間差がほぼないとしているので、スロットｓ１０となる）をエッジノードＥ２へ通知する。
【０１３７】
〔Ｓ３９〕エッジノードＥ２は、通知されたスロットｓ１０でパケットｐ１を宛先エッジノードＥ３へ送信する。以降、上記のような制御をグループの出口に到達するまで続ける。
【０１３８】
図２６はパケット伝送の流れを示す図である。パケットｐ１の次に宛先アドレス（10.0.4.1）のパケットｐ２がグループＧ１に到着したときのパケット伝送の流れを示している。
【０１３９】
〔Ｓ４１〕宛先アドレス（10.0.4.1）のパケットｐ２がグループＧ１に到着する。エッジノードＥ１は、テーブルＴ１１にもとづき、宛先アドレスからグループＧ１内の宛先ノード番号Ｅ２を取得する。
【０１４０】
〔Ｓ４２〕エッジノードＥ１は、エッジノードＥ１からエッジノードＥ２へ向かう経路はすでに割当てられているため、パケットｐ２を先のスロットｓ１０のタイミングで送信する。
【０１４１】
〔Ｓ４３〕エッジノードＥ２は、ステップＳ３５と同じ制御を行い、グループＧ１で割当てられたスロット番号を自グループのスロット番号に変換する。ここでは、スロットｓ１０に変換するので、パケットバッファ３２には、パケットｐ２のパケット内容とグループＧ２で最も近いスロット番号（ｓ１０）の２つの情報を保存しておく。
【０１４２】
〔Ｓ４４〕エッジノードＥ２は、テーブルＴ１２にもとづき、宛先アドレスからグループＧ２内の宛先ノード番号Ｅ４を取得する。
〔Ｓ４５〕エッジノードＥ２は、エッジノードＥ２から宛先ノードＥ４に対応する経路が見つからないので、管理サーバ２０−２にノード番号を通知して経路割当を依頼する。このとき、パケットバッファ３２に保存しておいた、自グループＧ２内での最適なスロット番号を取得し、このスロット番号（スロットｓ１０）も管理サーバ２０−２へ送る。
【０１４３】
〔Ｓ４６〕管理サーバ２０−２は、通知されたスロット番号に最も近い番号で、かつ空いているスロットを検出する。そして、検出した該スロットに経路を埋め込み、経路が埋め込まれたスロット（スロットｓ１０はすでに割当てられているので、スロットｓ１０に最も近いスロットｓ１１となる。なお、スロットｓ１１もすでに割当てられているような場合には、例えば、スロットｓ１２となる。）をエッジノードＥ２へ通知する。
【０１４４】
〔Ｓ４７〕エッジノードＥ２は、通知されたスロットｓ１１でパケットｐ２を宛先エッジノードＥ４へ送信する。以降、上記のような制御をグループの出口に到達するまで続ける。
【０１４５】
以上説明したように、上記の構成によれば、直前のグループで割当てられたスロットで送信されたパケットを受信すると、直前のグループで割当てられたスロットのスロット番号を、自グループに対応する番号である自スロット番号に変換して、パケットと対にしてパケットバッファに格納する。
【０１４６】
そして、パケット送信時には、パケットをパケットバッファから取り出し、自スロット番号を持つスロットをパケットに割当てる。また、自スロット番号が使用することができないような場合は、自スロット番号よりも時間的に後で、かつ自スロット番号に対して最も時間差の小さなスロット番号を選択する。そして、選択したスロット番号を持つスロットをパケットに割当てる。
【０１４７】
これにより、複数グループをパケットが通過する際、他グループでスロットが割当てられたパケットが到着した場合でも、該他グループで割当てられたスロット番号に近いスロット番号を割当ててパケット伝送を行うので、遅延を低減することができ、伝送品質の向上を図ることが可能になる。
【０１４８】
次に他の実施の形態について説明する。上記のグループ間を跨ぐスロット割当では、１つの入力に対して複数出力する１：ＮのグループネットワークのＮ出力部分（例えば、図２６におけるエッジノードＥ２の部分）に関するスロット割当について説明した。以降では、複数入力に対して複数出力するＮ：ＭのグループネットワークのＮ入力部分に関するスロット割当について説明する。
【０１４９】
図２７は通信システムの構成例を示す図である。通信システム４は、通信装置４１（第１の通信装置）と、通信装置４２（第２の通信装置）を備える。通信装置４１は、グループＧ１内に位置し、通信装置４２は、グループＧ２内に位置する。
【０１５０】
通信装置４１は、スロット割当部４１ａとリスト作成部４１ｂを含む。スロット割当部４１ａは、パケットに第１のスロットを割当てる。リスト作成部４１ｂは、割当てた第１のスロットのスロット番号をリストに登録し、次段のグループへ送信する。
【０１５１】
通信装置４２は、スロット割当部４２ａとリスト作成部４２ｂを含む。スロット割当部４２ａは、パケットに第２のスロットを割当てる。リスト作成部４２ｂは、割当てた第２のスロットのスロット番号をグループＧ１から送信されたリストに登録する。
【０１５２】
このような構成により、各グループで割当てたスロット番号のリストが後段グループへ通知されて、リストにもとづいて、後段グループでスロット割当を行うことにより、複数グループが接続されるネットワークにおいても、各グループでのスロット割当を効率よく実施することが可能になる。
【０１５３】
なお、スロット割当部とリスト生成部とは、上記では、１台の装置に含まれる構成としたが、各機能が分離してもよい。例えば、スロット割当部がネットワークの運用管理を行う管理サーバに配置され、リストを生成して次段グループへリストを送信するリスト作成部がネットワーク内のノードに配置されるような構成にしてもよい。
【０１５４】
次に動作について詳しく説明する。図２８はパケット伝送の流れを示す図である。グループＧ１〜Ｇ３がシリアルに接続する。グループＧ１は、エッジノードＥ１、Ｅ２、Ｅ５、中継ノードＲ１、Ｒ２および管理サーバ２０−１を含む。グループＧ２は、エッジノードＥ２、Ｅ３、中継ノードＲ３、Ｒ４および管理サーバ２０−２を含む。グループＧ３は、エッジノードＥ３、Ｅ４、Ｅ６、中継ノードＲ５、Ｒ６および管理サーバ２０−３を含む。
【０１５５】
このようなネットワーク構成において、すでに白抜き矢印方向の経路ｍ１が確立しているとする。この場合、後から黒塗り矢印方向の経路ｍ２を生成するときは、グループＧ３（エッジノードＥ３）において、上述したようなスロット割当の制御が行われる。
【０１５６】
ここで、グループＧ１（エッジノードＥ５）におけるスロット割当について考える。黒塗り矢印の方向の経路ｍ２を通じて、グループＧ１へ向けてパケットが送信される際、複数のグループ群Ｇ１０を経て、グループＧ１にパケットが到着するものとする。
【０１５７】
グループＧ（ｎ）のスロット割当は、上述したように、１つ前のグループＧ（ｎ−１）で割当てられたスロットを元に決定するので、グループＧ１に達するまでに、グループＧ１の前段側にあるグループ群Ｇ１０の各グループでそれぞれのスロット割当が行われる。
【０１５８】
したがって、グループＧ１においても、前段側にある複数のグループ群Ｇ１０で割当てられたスロットにもとづいてスロット割当を行うことになる。しかし、グループＧ１で割当てようとするスロットが、経路ｍ１で割当て済みのスロットと大きな時間差を持っていたりするおそれがある。
【０１５９】
例えば、経路ｍ１にスロットｓ１０が割当てられているとする。グループ群Ｇ１０では、各グループにおいて、・・・スロットｓ４０、スロットｓ４８、スロットｓ４９・・・と割当てられ、グループＧ１に到達したとする。
【０１６０】
この場合、グループ群Ｇ１０のスロット割当にもとづいて、グループＧ１ではスロットｓ５０を割当てるとすると、エッジノードＥ２ではスロットｓ１０をすでに割当てているので、エッジノードＥ２において、スロットｓ５０とスロットｓ１０との時間差のバッファリングを行うことになってしまう。このため、最短時間の経路を生成することができず、伝送品質の低下につながる。
【０１６１】
グループＧ（ｎ）のスロット割当を行う際に、１つ前のグループＧ（ｎ−１）で割当てられたスロットを元に決定するといったアルゴリズムで、終端点に到達するならば問題はない。しかし、途中のグループにおいて、該アルゴリズムによるスロット割当を行うと、上記のように最短時間で経路を生成できない場合がある。通信システム４による機能では、このような状況を改善するものである。
【０１６２】
図２９は動作を示すフローチャートである。
〔Ｓ５１〕開始グループでは、期待値の高いスロットを仮割当し、スロットの候補リストを作成して、隣接グループへ送信する。
【０１６３】
〔Ｓ５２〕隣接グループがスロット割当済みでなければ、該隣接グループにおける小さい時差で、割当可能なスロットを仮割当する。そして、そのスロットを候補リストに加えて隣接グループへ流す。
【０１６４】
〔Ｓ５３〕ステップＳ５１、Ｓ５２の動作を行い、スロット割当済みの経路が存在せず、終端のグループまで到達した場合は、仮割当してきたスロットで確定する。
〔Ｓ５４〕ステップＳ５１、Ｓ５２の動作を行って、スロット割当済みのグループが途中に存在した場合は、そこで候補リストを破棄し、スロット割当済みのグループが使用しているスロット番号を遡って返送する。返送されたスロット番号を受信したグループは、そのスロット番号に近いスロットを割当てる。
【０１６５】
図３０は動作を説明するための図である。基本的なネットワーク構成は図２８と同じである。グループ群Ｇ１０にはグループＧ１０−１、Ｇ１０−２が含まれる。グループＧ１０−１は、エッジノードＥ７と管理サーバ２０−４を含み、グループＧ１０−２は、エッジノードＥ８と管理サーバ２０−５を含む。また、経路ｍ１にスロットｓ１０が割当てられているとする。
【０１６６】
〔Ｓ６１〕グループ群Ｇ１０内のグループＧ１０−１の管理サーバ２０−４は、スロットｓ４８を仮割当する。エッジノードＥ７は、スロットｓ４８を候補リストに追加して、隣接するグループＧ１０−２へ送信する。
【０１６７】
〔Ｓ６２〕グループＧ１０−２の管理サーバ２０−５は、スロットｓ４９を仮割当する。エッジノードＥ８は、スロットｓ４９を候補リストに追加して、隣接するグループＧ１へ送信する。
【０１６８】
〔Ｓ６３〕グループＧ１の管理サーバ２０−１では、スロット割当済みのスロットｓ１０があるので、グループＧ１０−２から送信された候補リストを破棄する。
〔Ｓ６４〕グループＧ１の管理サーバ２０−１は、現在使用中のスロット番号ｓ１０をグループＧ１０−２に返送する。
【０１６９】
〔Ｓ６５〕グループＧ１０−２の管理サーバ２０−５は、受信したスロット番号ｓ１０から、スロット番号ｓ１０に最も近い番号を割当てる。例えば、スロットｓ９を割当てるとする。そして、スロット番号ｓ９をグループ１０−１へ返送する。
【０１７０】
〔Ｓ６６〕グループＧ１０−１の管理サーバ２０−４は、受信したスロット番号ｓ９をから、スロット番号ｓ９に最も近い番号を割当てる。例えば、スロットｓ８を割当てるとする。そして、スロット番号ｓ８を前段のグループへ返送する。以降同様な動作が開始点のグループまで遡って行われる。
【０１７１】
以上説明したように、グループＧ（ｎ）に、スロットが割当済みの経路が存在しない場合、グループＧ（ｎ−１）の管理サーバ（第１のスロット割当部）では、グループＧ（ｎ−１）内で、所定時間経路で送信するためのスロットを仮割当てし、グループＧ（ｎ−１）のエッジノード（第１のリスト作成部）は、割当てられたスロットのスロット番号を候補リストに登録してグループＧ（ｎ）へ送信する。
【０１７２】
同様に、グループＧ（ｎ）の管理サーバ（第２のスロット割当部）は、グループＧ（ｎ）内で、所定時間経路で送信するためのスロットを仮割当てし、グループＧ（ｎ）のエッジノード（第２のリスト作成部）は、割当てられたスロットのスロット番号を候補リストに登録する。
【０１７３】
ここで、グループＧ（ｎ）に次段グループＧ（ｎ＋１）が接続していれば、グループＧ（ｎ）のエッジノードは、グループＧ（ｎ＋１）へ候補リストを中継送信する。また、グループＧ（ｎ）が終端グループであれば、グループＧ（ｎ−１）、Ｇ（ｎ）の各管理サーバは、仮割当てしたスロットで確定する。すなわち、仮割当てしたスロットでパケットに対してスロット割当を行う。これにより、複数グループが接続されるネットワークにおいて、各グループでのスロット割当を効率よく実施することが可能になる。
【０１７４】
一方、グループＧ（ｎ）に、スロットが割当済みの経路がすでに存在している場合、グループＧ（ｎ）の管理サーバは、グループＧ（ｎ−１）から送信された候補リストを破棄する。そして、グループＧ（ｎ）ですでに割当済みのスロットのスロット番号を前段のグループＧ（ｎ−１）返送するための制御を行う。
【０１７５】
また、グループＧ（ｎ−１）の管理サーバは、返送されたスロットのスロット番号に対して、最も時間差の小さなスロット番号を選択し、選択したスロット番号を持つスロットをパケットに割当てる。そして、前段のグループＧ（ｎ−２）に対して、グループＧ（ｎ−１）で選択したスロット番号を遡って返送する。以降同様な動作が開始グループに達するまで遡って行われる。
【０１７６】
このように、複数のスロット候補を隣接するグループの管理サーバへ通知し、最終的に終端の管理サーバが最も短い時間で割当て可能なものを選択するまでの間にスロット割当て済みのグループが存在した場合は、最初の割当て候補を破棄して割当て済みのスロットに近いスロットを割当てる構成とした。これにより、最短時間の経路を開始グループから終端グループまで生成することができ、伝送品質の向上を図ることが可能になる。
【０１７７】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。
【符号の説明】
【０１７８】
１０ 通信装置
１１ 経路算出部
１２ 経路割当制御部
【技術分野】
【０００１】
本発明は、データ通信を行う通信装置、通信システムおよび経路割当を行う経路割当方法に関する。
【背景技術】
【０００２】
インターネット等によるマルチメディアサービスの拡大に伴い、ネットワーク上を流れる情報量は飛躍的に増大し、情報通信ネットワークを流れるトラフィックは大きく増加している。
【０００３】
トラフィックが増加すると、例えば、ネットワークを構成するルータの内部では、同時に到着するパケット数が増えて、パケットのバッファリング回数が増えたり、またはルーティングテーブルにもとづく経路計算の制御にかかる負荷が増大したりすることになる。
【０００４】
このため、ルータ内には、パケットバッファに用いるための大容量メモリや、経路計算に用いるための高速メモリといった、消費電力の大きなメモリデバイスが配置されていた。
【０００５】
近年になって、省電力ネットワークの構築を望む声は多いが、上記のように、ネットワーク全体の消費電力は、特にルータにおける消費電力が大きく影響しており、ルータの消費電力をいかに低減するかがネットワーク省電力化の鍵といえる。
【０００６】
従来技術として、複数のネットワークの静的および動的な情報にしたがって適切なネットワークを選択する技術が提案されている（特許文献１）。また、パス経路設定の際に、当該リンクを通過することが見込まれるパス数をパラメータとする評価関数を用いてパスの経路設定を行う技術が提案されている（特許文献２）。さらに、パケットに書き込まれている希望帯域情報にしたがって仮想的に帯域割当を行って帯域不足を解消する技術が提案されている（特許文献３）。さらにまた、各ノードが最良隣接ノードの情報をやりとりし、最良隣接ノードの情報をネットワークコアへ近づくための情報に用いてコアへ向かう通信路を作る技術が提案されている（特許文献４）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００１−２１７８７０号公報
【特許文献２】特開２００７−１４２６０９号公報
【特許文献３】特開平９−１４９０３８号公報
【特許文献４】特表２００７−５２３５４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
省電力ネットワークを構築する場合、ネットワークの管理を行うサーバ側で、送信すべきパケットのスロット（タイムスロット）をあらかじめ割当てて、時分割ベースでパケット転送を行う通信方式が考えられる。
【０００９】
これは、サーバが、どの時間で、どこの送信元からどこの宛先へ行くのかといったパケット転送のスケジューリングをしておいてから、パケット送出を行うものである。
このような制御を行うことにより、例えば、ルータに複数パケットが同時に到着するといった状態の発生頻度を低減させることができ、バッファリング回数を減少させることができる。このため、パケットバッファとして使用されていた消費電力の大きな大容量メモリをルータから排除することが可能になる。
【００１０】
また、例えば、ルータ自身が、従来行われていたような経路計算を実行せずに済むので、経路計算に要する負荷の軽減を図ることもでき、このため、経路計算時に使用されていた消費電力の大きな高速メモリを不要とすることが可能になる。なお、上記では、ルータの消費電力に注目して説明したが、ネットワークを構成するスイッチの消費電力についても同様の理由で低減可能である。
【００１１】
上記のようなパケット経路の割当によるスケジューリングを行うことにより、ルータの消費電力の低減化が可能になり、延いてはネットワーク全体の省電力化が可能になる。
一方、スケジューリングを行う場合に、帯域の有効活用を図ろうとして、少ないスロットにできるだけ多くの経路を割当てるといったスケジューリングを行うことが考えられる。
【００１２】
しかし、ネットワークの運用中は、トラフィックは常に変動するので、運用前のスケジューリングで用意した経路を上回る経路利用要求が発生する可能性がある。
すると、上記のようなスケジューリングでスタティックに決定されたスロットにもとづく帯域では、パケットを転送しきれないおそれがあり、さらに、トラフィック変動に伴って増加した経路に対応するために、あらためてスケジューリングをやり直さなければならなくなる。
【００１３】
このように、トラフィック変動に伴う経路の増加を想定せずに、スロットに多くの経路を単に詰め込むとしたスケジューリングでは、経路が増加したような場合には対応することができず、またスケジューリングをやり直すことになって非効率的であった。
【００１４】
本発明はこのような点に鑑みてなされたものであり、通信効率の向上を図った通信装置を提供することを目的とする。
また、本発明の他の目的は、通信効率の向上を図った通信システムを提供することを目的とする。
【００１５】
さらに、本発明の他の目的は、経路変動を想定したスロット割当のスケジューリングを行って、通信効率の向上を図った経路割当方法を提供することである。
【課題を解決するための手段】
【００１６】
上記課題を解決するために、通信装置が提供される。この通信装置は、ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、通信スロットに前記経路を割当てる経路割当制御部とを備える。また、経路割当制御部は、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当てを選択する。
【発明の効果】
【００１７】
通信効率の向上を図ることが可能になる。
【図面の簡単な説明】
【００１８】
【図１】通信装置の構成例を示す図である。
【図２】ネットワーク構成例を示す図である。
【図３】経路テーブルを示す図である。
【図４】スロットが使用している経路を示す図である。
【図５】スロットが使用している経路を示す図である。
【図６】スロットが使用している経路を示す図である。
【図７】期待値の計算フローを示す図である。
【図８】ネットワークの構成例を示す図である。
【図９】Min帯域デマンドのテーブルおよび最大公約数で割った値のテーブルを示す図である。
【図１０】経路テーブルとパステーブルを示す図である。
【図１１】最短ホップ数が記載されたテーブルを示す図である。
【図１２】リンクの使用状態／未使用状態が記載されたテーブルを示す図である。
【図１３】経路割当アルゴリズムの全体動作を示すフローチャートである。
【図１４】最大期待値算出の動作を示すフローチャートである。
【図１５】ネットワークトポロジを示す図である。
【図１６】ネットワークトポロジを示す図である。
【図１７】期待値計算結果を示す図である。
【図１８】通信装置の構成例を示す図である。
【図１９】グループ化されたネットワークを示す図である。
【図２０】グループ間を跨ぐスロット割当を示す図である。
【図２１】グループ間を跨ぐスロット割当の問題点を説明するための図である。
【図２２】パケット伝送の流れを示す図である。
【図２３】宛先アドレスと宛先ノードとの対応テーブルを示す図である。
【図２４】宛先アドレスと宛先ノードとの対応テーブルを示す図である。
【図２５】パケットバッファを示す図である。
【図２６】パケット伝送の流れを示す図である。
【図２７】通信システムの構成例を示す図である。
【図２８】パケット伝送の流れを示す図である。
【図２９】動作を示すフローチャートである。
【図３０】動作を説明するための図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態を図面を参照して説明する。図１は通信装置の構成例を示す図である。通信装置１０は、経路算出部１１と経路割当制御部１２を備える。通信装置１０は、例えば、ネットワークの管理サーバなどに設置される。
【００２０】
経路算出部１１は、ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２は、ネットワーク運用前に通信スロットへの経路の割当てを行う。この場合、データ衝突が起きないように、かつ経路変動に対応できるようにネットワーク運用時にも経路をより多く通信スロットに割当てられるような、通信スロットへの経路の割当てを行う。
【００２１】
ここで、経路割当制御部１２は、複数の通信スロットに経路を割当てる際に、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当てを選択する。
【００２２】
このような構成を有することにより、例えば、ネットワークのトラフィック変動に伴って経路が増加したような場合であっても、ネットワーク運用中に経路を割当てることができ、柔軟に対応することが可能になる。
【００２３】
また、経路割当のスケジューリングをやり直す必要がなく、通信効率の向上を図ることが可能になる。なお、以降の説明では、通信スロットを単にスロットと呼ぶ。また、スロットに経路を割当てることを、経路を埋め込むといった表現も使用する。
【００２４】
次に“スロット”、“経路”および“パス”の用語について説明する。“スロット”とは、パケットを送るための一定長の時間間隔のことで、フレームの中で、一定範囲の固定した時間間隔を占める。ある特定番号のスロットは、フレーム内に１つあり、フレームは周期的に繰り返されるため、その中にある特定番号のスロットも同じ周期で繰り返される。
【００２５】
“経路”とは、発エッジノードと着エッジノードの組合せとして定義される（通常、発着ノード間の中継ノードは意識しない）。また、経路に対しては、所望帯域としての帯域デマンドが与えられる。さらに、経路は（帯域に合わせて割当てられた）１つ以上のパスを含む。
【００２６】
“パス”とは、１つのスロット内で発エッジノードから着エッジノードに至るリンク（ノード間を結ぶ伝送路）の組合せとして定義される。１つのパスの帯域は、帯域割当ての最小単位であり、（リンク速度／スロット数）である。
【００２７】
次に期待値（経路埋め込み期待値）について説明する。期待値は、スロットへの経路の割当可能数の指標となるもので、１スロット当り、全経路の何％を埋め込めるかを表す。
ここで、スロットの最大数をＳ、経路数をＣ、ノード間のリンク速度をｖ、１スロットの帯域をｂとし、ｎ（＝ｖ／ｂ）個のスロットに割当可能な経路の総和をｋとした場合に、期待値は、以下の式（１）で定義する。
【００２８】
期待値＝（Σスロットｎに埋め込み可能な経路数）／（経路数×最大スロット数）
＝ｋ／（Ｃ×Ｓ）・・・（１）
期待値は、０〜１の範囲の値をとり、０の場合は、これ以上経路を埋める余裕がないことを示し、１の場合は、最大まで経路を埋める余裕があることを示す。
【００２９】
期待値の大きい方が、トラフィック変動に伴う経路変化にとって好ましい状態であると見なす（期待値が大きいことは、経路埋め込み余裕度が大きいということなので、経路増加要求があっても、運用中において、経路をスロットにダイナミックに埋め込むことができる）。
【００３０】
次に経路数の算出および期待値の計算例について図２〜図５を用いて説明する。図２はネットワーク構成例を示す図である。以降では、エッジノードを四角枠で示し、中継ノードを丸枠で示す。
【００３１】
ネットワークＮ１は、エッジノード１〜４および中継ノード５、６を含む。エッジノード１と中継ノード５が接続し、エッジノード２と中継ノード５が接続し、エッジノード３と中継ノード６が接続し、エッジノード４と中継ノード６が接続する。また、中継ノード５と中継ノード６が接続する。
【００３２】
ネットワークＮ１において、エッジノード間をフルメッシュで結ぶと経路数は１２となる（エッジ間を結ぶ途中の中継ノードも示すと、1→5→2、1→5→6→3、1→5→6→4、2→5→1、2→5→6→3、2→5→6→4、3→6→5→1、3→6→5→2、3→6→4、4→6→5→1、4→6→5→2、4→6→3の計１２経路）。
【００３３】
図３は経路テーブルを示す図である。始点エッジノードから終点エッジノードへの経路に番号を振ったテーブルＴ０を示している。あるスロット（スロットｓ１とする）が仮に未使用の場合、スロットｓ１には、テーブルＴ０のどの経路でも１つは埋めることが可能である。すなわち、「スロットｓ１に埋め込み可能な経路数」は１２となる。
【００３４】
図４はスロットが使用している経路を示す図である。図４に示す太矢印の経路（１）の1→5→2のルートが、スロットｓ１に現在埋め込まれていたとする。この状態に対して、あとどれだけの経路を経路（２）〜（１２）の中から選んで埋め込むことができるかを考える。
【００３５】
ここで、“埋め込む”、“埋め込めない”とは、すでにスロットに埋め込まれている経路に対し、その経路のリンクと、データ転送方向が同じリンクを共有しない経路であればデータ衝突が起きず、そのスロットに該当経路を埋め込むことができる。
【００３６】
また、すでにスロットに埋め込まれている経路に対し、その経路のリンクと、データ転送方向が同じリンクを共有するようなリンクを含んでいる経路は、データ衝突が生じるため、そのスロットには該経路を埋め込むことができない。
【００３７】
図４に示すように、エッジノード１から中継ノード５へのデータ転送方向のリンクをリンクＬ１、中継ノード５からエッジノード２へのデータ転送方向のリンクをリンクＬ２とする。
【００３８】
例えば、経路（２）の1→5→6→3のルートを見た場合、リンクＬ１が経路（１）と経路（２）で共有することになるので、経路（１）がすでに埋め込まれているスロットｓ１に対しては、経路（２）は埋め込めない。
【００３９】
これに対し、経路（９）の3→6→4のルートは、リンクＬ１、Ｌ２を共有しないので、経路（９）は、スロットｓ１に埋め込むことができる。また、経路（４）の2→5→1のルートでは、リンクＬ１、Ｌ２のデータ転送方向とは逆方向にデータを転送するので、リンクＬ１、Ｌ２を共有していることにはならず、経路（４）は、スロットｓ１には埋め込むことができる。
【００４０】
このような考え方で、経路（１）がすでに埋め込まれているスロットｓ１に埋め込み可能な経路を見つけると、この例の場合、経路（４）、（５）、（６）、（７）、（９）、（１０）、（１２）の７つある。したがって、経路（１）がすでに埋め込まれているスロットｓ１に対し、「スロットｓ１に埋め込み可能な経路数」は７となる。
【００４１】
図５、図６はスロットが使用している経路を示す図である。スロットが全部で４（＝ｎ）つあるとし（スロットｓ１〜ｓ４）、スロットｓ１〜ｓ４のそれぞれには図５、図６に示すような利用状況で経路が現在埋め込まれているとする。
【００４２】
すなわち、図５に対し、スロットｓ１、ｓ２には、経路（１）が埋め込まれ、図６に対し、スロットｓ３には、経路（２）が埋め込まれており、スロットｓ４には、経路は何も埋め込まれていないとする。
【００４３】
この場合、スロットｓ１〜ｓ４に埋め込み可能な経路数を上述したような考え方で求めると、スロットｓ１に対してさらに埋め込み可能な経路数は７、スロットｓ２に対してさらに埋め込み可能な経路数は７となる。また、スロットｓ３に対してさらに埋め込み可能な経路数は６、スロットｓ４に対して埋め込み可能な経路数は１２となる。
【００４４】
したがって、スロットｓ１〜ｓ４に埋め込み可能な経路数の総和は、（７＋７＋６＋１２）であり、ネットワークＮ１の全経路数は１２であり、最大スロット数は４であるので、式（１）から期待値は、（７＋７＋６＋１２）÷（１２×４）＝０．６７となる。
【００４５】
このことは、ネットワークＮ１の経路１２個を１００％とした場合、およそ６７％に相当する経路がスロットｓ１〜ｓ４にまだ埋め込むことが可能であることを示していることになる。
【００４６】
次に期待値の計算フローについて説明する。図７は期待値の計算フローを示す図である。なお、１つ目のパス（発エッジノード→着エッジノード）に関して、スロットｓに収容する経路のリンクの組み合わせは、例えば、ダイクストラ法（Dijkstra法：最短経路問題を解くための汎用的な計算アルゴリズム）で求められているとする。
【００４７】
〔Ｓ１〕経路カウンタのカウント値ｋに０を代入し、スロット番号ｓに１を代入する。
〔Ｓ２〕経路番号ｒに１を代入する。
〔Ｓ３〕スロットｓに経路ｒが埋め込み可能であり、かつ最短ホップ数＋α以上のホップ数を持つ経路であるか否かを判断する（α＝１、２、３、・・・）。最短ホップ数＋α以上の経路であればステップＳ４へいき、最短ホップ数＋α未満の経路であればステップＳ５へいく。
【００４８】
〔Ｓ４〕経路カウンタのカウント値ｋを増加する。
〔Ｓ５〕経路番号ｒを増加する。
〔Ｓ６〕経路番号ｒが最大経路数Ｒを超えたか否かを判断する。超えた場合はステップＳ７へいき、超えない場合はステップＳ３へ戻る。
【００４９】
〔Ｓ７〕スロット番号ｓを増加する。
〔Ｓ８〕スロット番号ｓが最大スロット数Ｓを超えたか否かを判断する。超えた場合はステップＳ９へいき、超えない場合はステップＳ２へ戻る。
【００５０】
〔Ｓ９〕期待値を計算する（期待値＝経路カウント値ｋ／（最大経路数Ｒ×最大スロット数Ｓ））。
ここで、ステップＳ３の処理について説明する。例えば、発ノードＡから着ノードＢへの経路として、経路＃１１〜＃１４があり、経路＃１１〜＃１４は、スロットｓに現在埋め込まれている経路のリンクとデータ転送方向が同一でないリンクを有しているとする（すなわち、どれも埋め込み可能な経路である）。また、経路＃１１のホップ数が１０、経路＃１２のホップ数が１１、経路＃１３ホップ数が１２、経路＃１４のホップ数が１３であったとする。
【００５１】
このとき、上限値αを３とすると、最短ホップ数は１０であるので、ホップ数が１３（＝１０＋３）となる経路である経路＃１４は、ステップＳ３の判断処理により、該当スロットに埋め込まれないことになる（経路＃１１〜＃１３までがスロットに割当てられる）。
【００５２】
すなわち、経路＃１１〜＃１４は、スロットｓに現在埋め込まれている経路のリンクとデータ転送方向が同一でないリンクを有しているので、この条件だけなら、現状のスロットｓに全部を埋め込むことができる。しかし、ステップＳ３に示すようなホップ数の制約条件も付加することにより、発着間のホップ数が許容範囲を超えるものは除外するということである。
【００５３】
このように、上限値αを設けて、最短ホップ数＋α以上のホップ数を持つ経路は、スロットにすでに埋め込まれている経路とデータ転送方向が同一のリンクを有していない経路であっても除外するようにした。これにより、迂回路が多く存在するネットワークトポロジの場合に、ホップ数の長い経路がパケット転送の通信路に選択されるといったことを防ぐことが可能になる。
【００５４】
次に図５、図６に示したスロット割当状態を例にして、図７に示したフローを使った期待値の計算動作について説明する。なお、期待値計算フローのステップＳ８からステップＳ２へ戻るループを外側ループ、ステップＳ６からステップＳ３へ戻るループを内側ループと呼ぶ。
【００５５】
全スロットが４つあるので、外側ループは４回回り、スロット番号ｓは１→４と変化する。また、とりうる経路数が１２個あるので、外側ループ毎に経路番号ｒは１→１２へと変化する。
【００５６】
（外側ループの１回目処理）
ステップＳ１によりｓ＝１、ｋ＝０であり、ステップＳ２によりｒ＝１から開始する。
内側ループの１回目では、スロットｓ１に経路（１）は埋め込むことができないので、ステップＳ３の判断がnoであり、ステップＳ５でｒ＝２となる。また、ステップＳ６の判断がnoであるため、ステップＳ３へ戻る（ｋ＝０）。
【００５７】
内側ループの２回目では、スロットｓ１に経路（２）は埋め込むことができないので、ステップＳ３の判断がnoであり、ステップＳ５でｒ＝３となる。また、ステップＳ６の判断がnoであるため、ステップＳ３へ戻る（ｋ＝０）。
【００５８】
内側ループの３回目では、スロットｓ１に経路（３）は埋め込むことができないので、ステップＳ３の判断がnoであり、ステップＳ５でｒ＝４となる。また、ステップＳ６の判断がnoであるため、ステップＳ３へ戻る（ｋ＝０）。
【００５９】
内側ループの４回目では、スロットｓ１に経路（４）を埋め込むことができるので、ステップＳ３の判断がyesであり、ステップＳ４でｋ＝１となる。また、ステップＳ５でｒ＝５となり、ステップＳ６の判断がnoなので、ステップＳ３へ戻る（ｋ＝１）。
【００６０】
内側ループの５回目では、スロットｓ１に経路（５）を埋め込むことができるので、ステップＳ３の判断がyesであり、ステップＳ４でｋ＝２となる。また、ステップＳ５でｒ＝６となり、ステップＳ６の判断がnoなので、ステップＳ３へ戻る（ｋ＝２）。
【００６１】
以降同様にして、内側ループの１１回目では、スロットｓ１に経路（１１）は埋め込むことができないので、ステップＳ３の判断がnoであり、ステップＳ５でｒ＝１２となる。また、ステップＳ６の判断がnoであるため、ステップＳ３へ戻る（ｋ＝６）。
【００６２】
内側ループの１２回目では、スロットｓ１に経路（１２）を埋め込むことができるので、ステップＳ３の判断がyesであり、ステップＳ４でｋ＝７となる。また、ステップＳ５でｒ＝１３となり、ステップＳ６の判断がyesとなるので、ステップＳ７へいく。ステップＳ７によりｓ＝２となり、ステップＳ８はnoなので、ステップＳ２へ戻る。
【００６３】
（外側ループの２回目処理）
ｓ＝２、ｋ＝７から開始する。内側ループ１回目（ｒ＝１）では、スロットｓ２には経路（１）は埋め込めない（ｋ＝７）。以降同様にして、内側ループ１２回目（ｒ＝１２）では、スロットｓ２には経路（１２）を埋め込めるのでｋ＝１４となる。
【００６４】
（外側ループの３回目処理）
ｓ＝３、ｋ＝１４から開始する。内側ループ１回目（ｒ＝１）では、スロットｓ３には経路（１）は埋め込めない（ｋ＝１４）。以降同様にして、内側ループ１２回目（ｒ＝１２）では、スロットｓ３には経路（１２）は埋め込めない（ｋ＝２０）。なお、スロットｓ３は経路（４）、（７）、（８）、（９）、（１０）、（１１）を埋め込むことができる。
【００６５】
（外側ループの４回目処理）
ｓ＝４、ｋ＝２０から開始する。内側ループ１回目（ｒ＝１）では、スロットｓ４には経路（１）は埋め込めるのでｋ＝２１となる。以降同様にして、内側ループ１２回目（ｒ＝１２）では、スロットｓ４には経路（１２）は埋め込めるのでｋ＝３２となる。なお、スロットｓ４は、経路（１）〜（１２）のどれでも埋め込むことができる。
【００６６】
上記のようなループ処理を繰り返した後に、ステップＳ９により、期待値はｋ÷Ｒ÷Ｓ＝３２÷１２÷４＝０．６７と求まる。
次にスロットに経路を割当てる経路割当アルゴリズムの手順について説明する。なお、以下の［１］の内容は、主に経路算出部１１の動作に該当し、［２］の内容は、主に経路割当制御部１２の動作に該当する。
【００６７】
［１］全経路の最小帯域デマンド（Min帯域デマンド）を、その最大公約数（１スロットの帯域）で割算し、各経路に必要なパス数を求める。あわせて、スロット数を（リンク速度／１スロットの帯域）で決定する。なお、全経路数をＬ、全パス数をＭ、スロット数をｎとする。
【００６８】
［２］Ｍ個のパスを、下記手順（ａ）〜（ｇ）による期待値の演算・比較により、ｎ個のスロットに割当てる。
（ａ）１つ目のパス（発エッジノード→着エッジノード）を取り出し、スロットに収容するリンクの組合せを例えばDijkstra法で求める。
【００６９】
（ｂ）得られた組合せのホップ数が、「最短経路＋上限値」内に収まっているか判定する。
（ｃ）収まっていれば、当該パスを収容した時のスロットの期待値を求める。また、全経路に対し、これらがDijkstra法により収容可能か否かを判定し、収容可能な経路をカウントして、期待値を算出する。
【００７０】
（ｄ）（ａ）〜（ｃ）の手順を、任意のパスの任意のスロットに対して行う（Ｍ×Ｎ回の総当り演算）。
（ｅ）（ｄ）までの結果で得られた最大Ｍ×Ｎの演算の期待値を比較し、一番大きな値のものを確定パス（または確定経路）として決定し登録する。
【００７１】
（ｆ）割当てるべきパス（Ｍ個）から、（ｅ）で決定したパスを除き、このパス（残りＭ−１個のパス）の集合に対して、（ａ）〜（ｅ）の手順を行う。
（ｇ）（ａ）〜（ｆ）の手順を、割当てるべきパスがなくなるまで繰り返す。
【００７２】
次に例を示しながら経路割当アルゴリズムの動作について説明する。図８はネットワークの構成例を示す図である。ネットワークＮ２は、エッジノード０〜３および中継ノード４〜７を含む。エッジノード０と中継ノード４が接続し、エッジノード１と中継ノード５が接続し、エッジノード２と中継ノード６が接続し、エッジノード３と中継ノード７が接続する。また、中継ノード４、５が接続し、中継ノード５、７が接続し、中継ノード７、６が接続し、中継ノード６、４が接続する。
【００７３】
ネットワークＮ２における各経路のMin帯域デマンドを、0→2の経路が10Mbps、0→3の経路が5Mbps、1→3の経路が10Mbps、1→2の経路が5Mbps、2→1の経路が10Mbpsとする。
図９はMin帯域デマンドのテーブルおよび最大公約数で割った値のテーブルを示す図である。テーブルＴ１は、Min帯域デマンドをテーブル化したものである。また、テーブルＴ２は、Min帯域デマンドをその最大公約数（１スロットの帯域に該当）で割った値をテーブル化したものである。この例では、Min帯域デマンドの最大公約数は５であるので、割り算を行うとテーブルＴ２に示される値となる。
【００７４】
ここで、各経路のMin帯域デマンドに必要なパス数は、テーブルＴ２の数値をすべて合計した値となるので、全パス数Ｍは、Ｍ＝８（=2+1+1+2+2）となる（すなわち、0→2の経路のパス数は２、0→3の経路のパス数は１、1→2の経路のパス数は１、1→3の経路のパス数は２、2→1の経路のパス数は２であるので計８個）。
【００７５】
また、全経路数Ｌは、テーブルＴ２の０以外の数値が記された項目欄の数であり、５個あるのでＬ＝５となる。さらにスロット最大数ｎは、例えば、リンク速度が100Mbpsであり、１スロットの帯域を５とすると、１００／５＝２０となり、ｎ＝２０スロットとなる。
【００７６】
図１０は経路テーブルとパステーブルを示す図である。上記で求めた経路とパスに番号を付けてテーブルを作成すると、経路テーブルＴ１１およびパステーブルＴ１２となる。経路テーブルＴ１１は、５個の経路に番号＃１〜＃５を付けて作成したテーブルである。パステーブルＴ１２は、８個のパスに番号を付けて作成したテーブルである。
【００７７】
図１１は最短ホップ数が記載されたテーブルを示す図である。テーブルＴ３は、利用する経路が最短で何ホップで接続できるかのホップ数を示している。ネットワークＮ２のノード接続構成により、0→2、0→3、1→3、1→2、2→1のすべての経路に対し、最短ホップ数は３である。
【００７８】
図１２はリンクの使用状態／未使用状態が記載されたテーブルを示す図である。テーブルＴ４は、送信元ノード（ｓｒｃ）から宛先ノード（ｄｓｔ）を結ぶリンクごとに、すでにスロットに割当てられた使用済みのリンクを１、スロットに割当てられていない未使用のリンクに０を登録するテーブルである。このようなテーブルＴ４で、リンクの使用状態／未使用状態を管理して、１を書き込んだリンクを除外できるようにする。
【００７９】
なお、テーブルＴ４は、ｓｒｃ／ｄｓｔのペアの代わりに隣接行列（adjacency matrix）で保持してもよい。この場合、隣接行列を複数持ち、元の行列の１だった箇所に０を書き込むことで経路の除外を表現する。
【００８０】
次にテーブルＴ２に記載される経路（計５経路）について期待値を計算していく。経路は、テーブルＴ４で未使用となっているリンクを使って作ることができる最短経路を用いる。
【００８１】
スロットｓ０〜ｓ１９に対する経路＃１〜＃５割当の期待値の計算として例えば、経路＃１（0→2）をスロットｓ０に埋め込んだ場合の期待値はａ１となる（経路＃１をスロットｓ１に埋め込んだ場合に、あとどれぐらいの経路を埋め込むことができるかの指標がａ１となる）。経路＃１（0→2）をスロットｓ１に埋め込んだ場合の期待値はａ２となる。以降同様にスロットｓ１９まで期待値を計算する。
【００８２】
次の経路の期待値計算として、経路＃２（0→3）をスロットｓ０に埋め込んだ場合の期待値はｂ１となる。経路＃２（0→3）をスロットｓ１に埋め込んだ場合の期待値はｂ２となる。以降同様にスロットｓ１９まで期待値を計算する。
【００８３】
次の経路の期待値計算として、経路＃３（1→2）をスロットｓ０に埋め込んだ場合の期待値はｃ１となる。経路＃３（1→2）をスロットｓ１に埋め込んだ場合の期待値はｃ２となる。以降同様にスロットｓ１９まで期待値を計算し、以下同様にして経路＃５までの期待値を計算する。
【００８４】
このように、すべての経路＃１〜＃５に対して、すべてのスロットｓ０〜ｓ１９に仮に割当てた場合の期待値を計算する。そして、期待値を計算し終えたら、その中で最も期待値の大きいものを選択する（値の大きさが同じものがある場合はどれを選択してもよいが、例えば、スロット番号の小さいものを選択する）。
【００８５】
ここで、経路がＭ個（経路＃１〜＃Ｍ）あり、所定数のスロットに対して上記のような期待値計算をしたとする。そして例えば、経路＃２をスロットｓ０に埋め込んだ期待値が最も大きくなったとすると、この経路＃２を確定経路と呼び、確定経路を除いた（Ｍ−１）個の経路に対して、再び上記と同様な期待値計算を行うことになる。このような処理を繰り返して、結果的にＭ個の確定経路を求めることになる。
【００８６】
なお、経路決定に使用したリンクは、テーブルＴ４の該当箇所を１に登録し、使用済みにして以後の経路探索対象から除外する。
次に経路割当アルゴリズムの動作フローについて説明する。図１３は経路割当アルゴリズムの全体動作を示すフローチャートである。
【００８７】
〔Ｓ１１〕テーブルＴ２を作成する（Min帯域デマンドをその最大公約数で割った値をテーブル化する）。
〔Ｓ１２〕テーブルＴ３を作成する（各経路の最短ホップ数を求めてテーブル化する）。
【００８８】
〔Ｓ１３〕テーブルＴ２の参照位置（ａ、ｂ）をａ＝０、ｂ＝０に設定する。
〔Ｓ１４〕テーブルＴ２の参照位置（ａ、ｂ）の値が０か否かを判断する。０でなければステップＳ１５へいき、０ならばステップＳ１６へいく。
【００８９】
〔Ｓ１５〕経路が未使用のスロットが出てくるまで、すべてのスロットにおけるノードａから出発してノードｂに到達する最短経路を求めて、期待値をすべて算出する。
〔Ｓ１６〕テーブルＴ２の参照位置（ａ、ｂ）を１つ進める。
【００９０】
〔Ｓ１７〕テーブルＴ２の参照をすべて終えた場合はステップＳ１８へいき、終えていない場合はステップＳ１３へ戻る。
〔Ｓ１８〕期待値が最大の経路を選び、経路が利用するリンクについてテーブルＴ４の該当スロットの部分に１を書き込む。
【００９１】
図１４は最大期待値算出の動作を示すフローチャートである。
〔Ｓ２０〕スロット試行位置を０に設定する（すなわち、スロットｓ０からスタートする）。
【００９２】
〔Ｓ２１〕テーブルＴ４の該当箇所を参照して、ノードａから出発してノードｂに到達する最短経路をDijkstra法で求める。
〔Ｓ２２〕経路が求まらないか、テーブルＴ３の最短経路＋αよりも長い経路になってしまうかを判断する。経路が求まらない、またはテーブルＴ３の最短経路＋αよりも長い経路になってしまう場合はステップＳ２４へいく。また、経路が求まり、テーブルＴ３の最短経路＋αよりも長い経路にならない場合はステップＳ２３へいく。
【００９３】
〔Ｓ２３〕ａ、ｂ、スロット番号、期待値、経路を計算して保存する。
〔Ｓ２４〕スロット試行位置を１増やす。
〔Ｓ２５〕１つ前のスロットが完全未使用スロットかを判断する（テーブルＴ４の項目がすべて０かを判断する）。完全未使用スロットの場合はステップＳ２６へいき、そうでない場合はステップＳ２１へ戻る。
【００９４】
〔Ｓ２６〕保存したもののうちでもっとも期待値の高いものを選択する。
次に効果について説明する。図１５、図１６はネットワークトポロジを示す図である。ネットワークＮ１１は、スター型のトポロジであり、ネットワークＮ１２は、ツリー型のトポロジである。また、ネットワークＮ１３は、ラダー型のトポロジであり、ネットワークＮ１４は、簡易ラダー型のトポロジである。
【００９５】
図１７は期待値計算結果を示す図である。上記の４種類の基本的なトポロジにおいて、１０スロットの空きスロットに対して、フルメッシュの経路割当を行った場合の期待値を算出する。
【００９６】
スロットに経路を割当てる際の評価として、例えば、ランダムに割当てる場合、ホップ数の短い経路を優先的に割当てる場合、ホップ数の長い経路を優先的に割当てる場合、および本発明による割当てを行う場合があり、それぞれの場合において１００回ずつ試行して平均の期待値を算出した。
【００９７】
図１７に示すように、通信装置１０で実行する期待値計算がすべてのトポロジにおいて最大となる。すなわち、通信装置１０における経路割当制御を実行することにより、後から追加する経路数をより多く割当てることが可能になる。
【００９８】
次にグループ間を跨いでスロット割当を行って、パケット通信を行う通信装置および通信システムについて説明する。なお、送信すべきパケットに対して、経路が埋め込まれた、あるスロット（タイムスロット）のタイミングを割当てることを、そのパケットに対してのスロット割当と呼ぶ。
【００９９】
例えば、パケットｐ１をスロットｓ１（ｓ１はスロットに付与されるスロット番号）のタイミングで送信する場合、パケットｐ１にはスロットｓ１が割当てられるといった表現をする。
【０１００】
図１８は通信装置の構成例を示す図である。通信装置３０は、パケットにスロットを割当てるスロット割当部３１と、パケットバッファ３２とを備える。
スロット割当部３１は、直前のグループで割当てられたスロットで送信されたパケットを受信すると、直前のグループで割当てられた該スロットのスロット番号を、自グループに対応する番号である自通信スロット番号（自スロット番号）に変換する。また、パケットバッファ３２は、自スロット番号と、パケットとを対にして格納する。
【０１０１】
ここで、スロット割当部３１は、パケット送信時には、パケットをパケットバッファ３２から取り出し、自スロット番号を選択し、自スロット番号を持つスロットをパケットに割当てる。
【０１０２】
また、自スロット番号を選択しない場合は、自スロット番号よりも時間的に後で、かつ自スロット番号に対して最も時間差の小さなスロット番号を選択し、選択したスロット番号を持つスロットをパケットに割当てる。
【０１０３】
なお、スロット割当部３１とパケットバッファ３２とは、上記では、１台の装置に含まれる構成としたが、各機能が分離してもよい。例えば、スロット割当部３１がネットワークの運用管理を行う管理サーバに配置され、パケットバッファ３２がネットワーク内のノードに配置されるような構成にしてもよい。
【０１０４】
以下、通信装置３０の機能を適用したグループネットワークについて詳しく説明する。図１９はグループ化されたネットワークを示す図である。エッジノードＥ１〜Ｅ４がシリアルに接続し、中継ノードＲ１がエッジノードＥ１、Ｅ２の間に配置し、中継ノードＲ２がエッジノードＥ２、Ｅ３の間に配置し、中継ノードＲ３がエッジノードＥ３、Ｅ４の間に配置している。
【０１０５】
また、グループＧ１は、エッジノードＥ１、Ｅ２、中継ノードＲ１および管理サーバ２０−１を含み、グループＧ２は、エッジノードＥ２、Ｅ３、中継ノードＲ２および管理サーバ２０−２を含み、グループＧ３は、エッジノードＥ３、Ｅ４、中継ノードＲ３および管理サーバ２０−３を含む。
【０１０６】
グループ境界においてエッジノードが配置され、グループ間はエッジノードを通じて接続される。グループＧ１〜Ｇ３内の管理サーバ２０−１〜２０−３は、グループ内のエッジノードや中継ノードと通信を行い、各グループは独立して稼働する。
【０１０７】
エッジノードＥ１〜Ｅ４は、パケットの宛先IPアドレスと宛先エッジノードが対応した宛先対応テーブルと、宛先エッジノードと使用スロット番号が対応したスロット番号対応テーブルとを備える。
【０１０８】
エッジノードＥ１〜Ｅ４に、宛先対応テーブルに存在する宛先のパケットが到着した場合は、そのパケットにはすでにスロット割当済みであるので、管理サーバとの通信は行わずに、割当済みのスロットを使用する。これにより、管理サーバの負担削減およびスロット消費量の低減を図る。
【０１０９】
また、宛先対応テーブルに存在しない宛先のパケットが到着した場合は、そのパケットにはスロットが割当てられていないので、該パケットを受信したエッジノードは、エッジノードと通信する管理サーバに対して、スロット番号割当の要求を行う。
【０１１０】
図２０はグループ間を跨ぐスロット割当を示す図である。入側の最初のグループＧ１は、期待値が最も高いスロットを選ぶ。続いて、隣接する次段のグループは、１つ前のグループのタイムスロットに時間的に最も近いスロットを選ぶ。
【０１１１】
ここで、グループ間には時間差があるので、グループ境界に位置するエッジノードには、時間調整のためのバッファが備えられる。ただし、大容量のバッファを備えるのものではないため、パケットが留まる時間を少なくする必要がある。
【０１１２】
そのためには、１つ前のグループのタイムスロットに時間的に最も近いスロットを選ぶことになる。すなわち、後段のグループでは、隣接する前段のグループで割当てられたスロットと同じ時間、または後の時間に出現するスロットに最も近い時間のスロットを選択することになる。
【０１１３】
例えば、グループＧ１でスロットｓ１が割当てられた場合、グループＧ２では、スロットｓ１またはスロットｓ２を選択する。グループＧ１、Ｇ２で時間差がなく同一タイミングで稼働していた場合は、スロットｓ１が最良であり、このときは、ほとんどバッファリングせずに通過させることができる。
【０１１４】
また例えば、グループ間に時間差があって、グループＧ１のスロットｓ１に相当する時間では、グループＧ２ではスロットｓ５に相当していたとする。このとき、グループＧ１でスロットｓ１に割当てられたパケットは、グループＧ２ではスロットｓ５に割当てることが、バッファリングに要する時間が最も少なく、最も早く通過させる。
【０１１５】
しかし、スロットｓ５を使って送信するパケットが満杯のとき、この場合のバッファリング時間が最小となる最良のスロットは、スロットｓ５の直後のスロットｓ６を選択する。したがって、グループＧ２では、該パケットに対して、スロットｓ６の割当を行って通過させることになる。
【０１１６】
上記のような、グループ間でのスロット割当を行うことにより、エッジノードに大容量のバッファが不要となり、高速にパケット伝送を行うことが可能になる。
図２１はグループ間を跨ぐスロット割当の問題点を説明するための図である。グループＧ１〜Ｇ３がシリアルに接続し、グループＧ２とグループＧ４が接続する。グループＧ１は、エッジノードＥ１、Ｅ２、中継ノードＲ１、Ｒ２および管理サーバ２０−１を含み、グループＧ２は、エッジノードＥ２、Ｅ３、Ｅ５、中継ノードＲ３、Ｒ４および管理サーバ２０−２を含む。
【０１１７】
グループＧ３は、エッジノードＥ３、Ｅ４、中継ノードＲ５、Ｒ６および管理サーバ２０−３を含み、グループＧ４は、エッジノードＥ５、Ｅ６、中継ノードＲ７、Ｒ８および管理サーバ２０−４を含む。
【０１１８】
このようなネットワーク構成において、パケットｐ１は、白抜き矢印の経路ｍ１で伝送され、パケットｐ２は、黒塗り矢印の経路ｍ２で伝送されるとする。グループＧ１は、入側グループであるため、最初に到着したパケットｐ１に対して、最も期待値の高いスロットｓ１０を割当てる。
【０１１９】
また、グループＧ１〜Ｇ３は、同一タイミングで稼働しているとすると、グループＧ２もパケットｐ１にスロットｓ１０を割当てて経路ｍ１で送信し、グループＧ３もパケットｐ１にスロットｓ１０を割当てて経路ｍ１で送信する。
【０１２０】
一方、パケットｐ１の次にパケットｐ２がグループＧ１に到達した場合を考える。グループＧ１では、宛先対応テーブルに、到着したパケットの宛先があれば、すでにスロット割当済みなので、管理サーバ２０−１との通信を行わずに、パケットｐ２に対して割当済みのスロットを使用する。
【０１２１】
ここでは、エッジノードＥ１に到着したパケットの宛先は、エッジノードＥ２であり、経路ｍ１と経路ｍ２は同経路なので、パケット宛先は、既知であり、テーブル登録されている。
【０１２２】
したがって、グループＧ１内では、エッジノードＥ１は、管理サーバ２０−１との通信を行って、パケットｐ２に対してあらたなスロット割当を要求するといった制御はせずに、スロットｓ１０をそのまま使用して、エッジノードＥ２へパケットｐ２を伝送する。
【０１２３】
パケットｐ２は、グループＧ２のエッジノードＥ２に到着する。エッジノードＥ２において、経路ｍ１、ｍ２が分岐し、経路ｍ２は既知の経路ではないので、グループＧ２においてスロット割当が施される。この場合、パケットｐ２にとってグループＧ２は、入側のグループに相当するから、グループＧ２では、グループＧ２における最も期待値の大きなスロット割当を行うことになる。
【０１２４】
すなわち、パケットｐ２は、グループＧ１でスロットｓ１０が割当てられているが、スロットｓ１０とは関係のない、グループＧ２の中で最も期待値の大きなスロットが割当てられることになる。
【０１２５】
例えば、スロットｓ１０で到着したパケットｐ２に対し、グループＧ２内で最も期待値の大きなスロットｓ５０が割当てられる場合もある。このような場合、スロットｓ５０のタイミングでパケットｐ２を送信するには、スロットｓ１０からスロットｓ５０までの時間分を、エッジノードＥ２でバッファリングすることになり、遅延が増大することになる。
【０１２６】
上記のように、複数グループをパケットが通過する際、他グループでスロットが割当てられたパケットが到着した場合、該他グループで割当てられたスロット番号を無視したスロット割当を行って、パケット伝送が行われてしまうおそれがあり、遅延が増大してしまう。したがって、このような状況において、遅延低減を図ったスロット割当を行うことが必要である。
【０１２７】
次に上記課題を解決する通信装置３０の機能を適用したグループネットワークについて説明する。図２２はパケット伝送の流れを示す図である。宛先アドレス（10.0.3.1）のパケットｐ１が最初にグループＧ１に到着したときのパケット伝送の流れを示している。
【０１２８】
また、図２３、図２４に宛先アドレスと宛先ノードとの対応テーブルを示す。図２３に示すテーブルＴ１１は、図２２に示すエッジノードＥ１に含まれ、図２４に示すテーブルＴ１２は、図２２に示すエッジノードＥ２に含まれる。
【０１２９】
〔Ｓ３１〕宛先アドレス（10.0.3.1）のパケットｐ１がグループＧ１に到着する。エッジノードＥ１は、テーブルＴ１１にもとづき、宛先アドレスからグループＧ１内の宛先ノード番号Ｅ２を取得する。
【０１３０】
〔Ｓ３２〕エッジノードＥ１は、エッジノードＥ１から宛先ノードＥ２へ向かう経路がこの時点ではまだ存在せず見つからないため、管理サーバ２０−１にノード番号を通知して経路割当を依頼する。
【０１３１】
〔Ｓ３３〕管理サーバ２０−１は、最も期待値の高いスロットに経路を埋め込み、そのスロット(スロットｓ１０とする)をエッジノードＥ１へ通知する。
〔Ｓ３４〕エッジノードＥ１は、スロットｓ１０のタイミングを使ってパケットｐ１を送信する（スロットｓ１０を割当てたパケットｐ１を送信する）。
【０１３２】
〔Ｓ３５〕エッジノードＥ２は、事前に計算しておいたグループＧ１とグループＧ２とのスロット時間差をもとに、グループＧ１で割当てられたスロット番号を、グループＧ２での時間的に一番近い、グループＧ２に対応するスロット番号に変換する。この例では、時間差０と仮定すると、一番近いスロットは、グループＧ１と同じスロットｓ１０であり、スロットｓ１０に変換したとする。
【０１３３】
図２５にパケットバッファを示す。パケットバッファ３２は、各エッジノードに配置され、受信パケットのパケット内容と自スロット番号の２つの情報が保存される。また、本技術のスロット割当が行われない通常のIPネットワークから送信されたパケットも、エッジノードにおいて受信するので、これらのネットワークに関するパケット内容もパケットバッファ３２で保存される。
【０１３４】
エッジノードＥ２の例では、グループＧ１とグループＧ２とのスロット時間差をもとに計算された、グループＧ２での時間的に一番近いスロット番号（スロットｓ１０）と、そのスロット番号のタイミングで送信されるパケットｐ１の内容とが格納される。
【０１３５】
〔Ｓ３６〕エッジノードＥ２は、テーブルＴ１２にもとづき、宛先アドレスからグループＧ１内の宛先ノード番号Ｅ３を取得する。
〔Ｓ３７〕エッジノードＥ２は、エッジノードＥ２から宛先ノードＥ３へ向かう経路がこの時点ではまだなく見つからないため、管理サーバ２０−２にノード番号を通知して経路割当を依頼する。このとき、パケットバッファ３２に保存しておいた、自グループＧ２内での最適なスロット番号を取得し、このスロット番号（スロットｓ１０）も管理サーバ２０−２へ送る。
【０１３６】
〔Ｓ３８〕管理サーバ２０−２は、通知されたスロット番号に最も近い番号で、かつ空いているスロットを検出する。そして、検出した該スロットに経路を埋め込み、経路が埋め込まれたスロット番号（この例では、グループＧ１〜Ｇ３は時間差がほぼないとしているので、スロットｓ１０となる）をエッジノードＥ２へ通知する。
【０１３７】
〔Ｓ３９〕エッジノードＥ２は、通知されたスロットｓ１０でパケットｐ１を宛先エッジノードＥ３へ送信する。以降、上記のような制御をグループの出口に到達するまで続ける。
【０１３８】
図２６はパケット伝送の流れを示す図である。パケットｐ１の次に宛先アドレス（10.0.4.1）のパケットｐ２がグループＧ１に到着したときのパケット伝送の流れを示している。
【０１３９】
〔Ｓ４１〕宛先アドレス（10.0.4.1）のパケットｐ２がグループＧ１に到着する。エッジノードＥ１は、テーブルＴ１１にもとづき、宛先アドレスからグループＧ１内の宛先ノード番号Ｅ２を取得する。
【０１４０】
〔Ｓ４２〕エッジノードＥ１は、エッジノードＥ１からエッジノードＥ２へ向かう経路はすでに割当てられているため、パケットｐ２を先のスロットｓ１０のタイミングで送信する。
【０１４１】
〔Ｓ４３〕エッジノードＥ２は、ステップＳ３５と同じ制御を行い、グループＧ１で割当てられたスロット番号を自グループのスロット番号に変換する。ここでは、スロットｓ１０に変換するので、パケットバッファ３２には、パケットｐ２のパケット内容とグループＧ２で最も近いスロット番号（ｓ１０）の２つの情報を保存しておく。
【０１４２】
〔Ｓ４４〕エッジノードＥ２は、テーブルＴ１２にもとづき、宛先アドレスからグループＧ２内の宛先ノード番号Ｅ４を取得する。
〔Ｓ４５〕エッジノードＥ２は、エッジノードＥ２から宛先ノードＥ４に対応する経路が見つからないので、管理サーバ２０−２にノード番号を通知して経路割当を依頼する。このとき、パケットバッファ３２に保存しておいた、自グループＧ２内での最適なスロット番号を取得し、このスロット番号（スロットｓ１０）も管理サーバ２０−２へ送る。
【０１４３】
〔Ｓ４６〕管理サーバ２０−２は、通知されたスロット番号に最も近い番号で、かつ空いているスロットを検出する。そして、検出した該スロットに経路を埋め込み、経路が埋め込まれたスロット（スロットｓ１０はすでに割当てられているので、スロットｓ１０に最も近いスロットｓ１１となる。なお、スロットｓ１１もすでに割当てられているような場合には、例えば、スロットｓ１２となる。）をエッジノードＥ２へ通知する。
【０１４４】
〔Ｓ４７〕エッジノードＥ２は、通知されたスロットｓ１１でパケットｐ２を宛先エッジノードＥ４へ送信する。以降、上記のような制御をグループの出口に到達するまで続ける。
【０１４５】
以上説明したように、上記の構成によれば、直前のグループで割当てられたスロットで送信されたパケットを受信すると、直前のグループで割当てられたスロットのスロット番号を、自グループに対応する番号である自スロット番号に変換して、パケットと対にしてパケットバッファに格納する。
【０１４６】
そして、パケット送信時には、パケットをパケットバッファから取り出し、自スロット番号を持つスロットをパケットに割当てる。また、自スロット番号が使用することができないような場合は、自スロット番号よりも時間的に後で、かつ自スロット番号に対して最も時間差の小さなスロット番号を選択する。そして、選択したスロット番号を持つスロットをパケットに割当てる。
【０１４７】
これにより、複数グループをパケットが通過する際、他グループでスロットが割当てられたパケットが到着した場合でも、該他グループで割当てられたスロット番号に近いスロット番号を割当ててパケット伝送を行うので、遅延を低減することができ、伝送品質の向上を図ることが可能になる。
【０１４８】
次に他の実施の形態について説明する。上記のグループ間を跨ぐスロット割当では、１つの入力に対して複数出力する１：ＮのグループネットワークのＮ出力部分（例えば、図２６におけるエッジノードＥ２の部分）に関するスロット割当について説明した。以降では、複数入力に対して複数出力するＮ：ＭのグループネットワークのＮ入力部分に関するスロット割当について説明する。
【０１４９】
図２７は通信システムの構成例を示す図である。通信システム４は、通信装置４１（第１の通信装置）と、通信装置４２（第２の通信装置）を備える。通信装置４１は、グループＧ１内に位置し、通信装置４２は、グループＧ２内に位置する。
【０１５０】
通信装置４１は、スロット割当部４１ａとリスト作成部４１ｂを含む。スロット割当部４１ａは、パケットに第１のスロットを割当てる。リスト作成部４１ｂは、割当てた第１のスロットのスロット番号をリストに登録し、次段のグループへ送信する。
【０１５１】
通信装置４２は、スロット割当部４２ａとリスト作成部４２ｂを含む。スロット割当部４２ａは、パケットに第２のスロットを割当てる。リスト作成部４２ｂは、割当てた第２のスロットのスロット番号をグループＧ１から送信されたリストに登録する。
【０１５２】
このような構成により、各グループで割当てたスロット番号のリストが後段グループへ通知されて、リストにもとづいて、後段グループでスロット割当を行うことにより、複数グループが接続されるネットワークにおいても、各グループでのスロット割当を効率よく実施することが可能になる。
【０１５３】
なお、スロット割当部とリスト生成部とは、上記では、１台の装置に含まれる構成としたが、各機能が分離してもよい。例えば、スロット割当部がネットワークの運用管理を行う管理サーバに配置され、リストを生成して次段グループへリストを送信するリスト作成部がネットワーク内のノードに配置されるような構成にしてもよい。
【０１５４】
次に動作について詳しく説明する。図２８はパケット伝送の流れを示す図である。グループＧ１〜Ｇ３がシリアルに接続する。グループＧ１は、エッジノードＥ１、Ｅ２、Ｅ５、中継ノードＲ１、Ｒ２および管理サーバ２０−１を含む。グループＧ２は、エッジノードＥ２、Ｅ３、中継ノードＲ３、Ｒ４および管理サーバ２０−２を含む。グループＧ３は、エッジノードＥ３、Ｅ４、Ｅ６、中継ノードＲ５、Ｒ６および管理サーバ２０−３を含む。
【０１５５】
このようなネットワーク構成において、すでに白抜き矢印方向の経路ｍ１が確立しているとする。この場合、後から黒塗り矢印方向の経路ｍ２を生成するときは、グループＧ３（エッジノードＥ３）において、上述したようなスロット割当の制御が行われる。
【０１５６】
ここで、グループＧ１（エッジノードＥ５）におけるスロット割当について考える。黒塗り矢印の方向の経路ｍ２を通じて、グループＧ１へ向けてパケットが送信される際、複数のグループ群Ｇ１０を経て、グループＧ１にパケットが到着するものとする。
【０１５７】
グループＧ（ｎ）のスロット割当は、上述したように、１つ前のグループＧ（ｎ−１）で割当てられたスロットを元に決定するので、グループＧ１に達するまでに、グループＧ１の前段側にあるグループ群Ｇ１０の各グループでそれぞれのスロット割当が行われる。
【０１５８】
したがって、グループＧ１においても、前段側にある複数のグループ群Ｇ１０で割当てられたスロットにもとづいてスロット割当を行うことになる。しかし、グループＧ１で割当てようとするスロットが、経路ｍ１で割当て済みのスロットと大きな時間差を持っていたりするおそれがある。
【０１５９】
例えば、経路ｍ１にスロットｓ１０が割当てられているとする。グループ群Ｇ１０では、各グループにおいて、・・・スロットｓ４０、スロットｓ４８、スロットｓ４９・・・と割当てられ、グループＧ１に到達したとする。
【０１６０】
この場合、グループ群Ｇ１０のスロット割当にもとづいて、グループＧ１ではスロットｓ５０を割当てるとすると、エッジノードＥ２ではスロットｓ１０をすでに割当てているので、エッジノードＥ２において、スロットｓ５０とスロットｓ１０との時間差のバッファリングを行うことになってしまう。このため、最短時間の経路を生成することができず、伝送品質の低下につながる。
【０１６１】
グループＧ（ｎ）のスロット割当を行う際に、１つ前のグループＧ（ｎ−１）で割当てられたスロットを元に決定するといったアルゴリズムで、終端点に到達するならば問題はない。しかし、途中のグループにおいて、該アルゴリズムによるスロット割当を行うと、上記のように最短時間で経路を生成できない場合がある。通信システム４による機能では、このような状況を改善するものである。
【０１６２】
図２９は動作を示すフローチャートである。
〔Ｓ５１〕開始グループでは、期待値の高いスロットを仮割当し、スロットの候補リストを作成して、隣接グループへ送信する。
【０１６３】
〔Ｓ５２〕隣接グループがスロット割当済みでなければ、該隣接グループにおける小さい時差で、割当可能なスロットを仮割当する。そして、そのスロットを候補リストに加えて隣接グループへ流す。
【０１６４】
〔Ｓ５３〕ステップＳ５１、Ｓ５２の動作を行い、スロット割当済みの経路が存在せず、終端のグループまで到達した場合は、仮割当してきたスロットで確定する。
〔Ｓ５４〕ステップＳ５１、Ｓ５２の動作を行って、スロット割当済みのグループが途中に存在した場合は、そこで候補リストを破棄し、スロット割当済みのグループが使用しているスロット番号を遡って返送する。返送されたスロット番号を受信したグループは、そのスロット番号に近いスロットを割当てる。
【０１６５】
図３０は動作を説明するための図である。基本的なネットワーク構成は図２８と同じである。グループ群Ｇ１０にはグループＧ１０−１、Ｇ１０−２が含まれる。グループＧ１０−１は、エッジノードＥ７と管理サーバ２０−４を含み、グループＧ１０−２は、エッジノードＥ８と管理サーバ２０−５を含む。また、経路ｍ１にスロットｓ１０が割当てられているとする。
【０１６６】
〔Ｓ６１〕グループ群Ｇ１０内のグループＧ１０−１の管理サーバ２０−４は、スロットｓ４８を仮割当する。エッジノードＥ７は、スロットｓ４８を候補リストに追加して、隣接するグループＧ１０−２へ送信する。
【０１６７】
〔Ｓ６２〕グループＧ１０−２の管理サーバ２０−５は、スロットｓ４９を仮割当する。エッジノードＥ８は、スロットｓ４９を候補リストに追加して、隣接するグループＧ１へ送信する。
【０１６８】
〔Ｓ６３〕グループＧ１の管理サーバ２０−１では、スロット割当済みのスロットｓ１０があるので、グループＧ１０−２から送信された候補リストを破棄する。
〔Ｓ６４〕グループＧ１の管理サーバ２０−１は、現在使用中のスロット番号ｓ１０をグループＧ１０−２に返送する。
【０１６９】
〔Ｓ６５〕グループＧ１０−２の管理サーバ２０−５は、受信したスロット番号ｓ１０から、スロット番号ｓ１０に最も近い番号を割当てる。例えば、スロットｓ９を割当てるとする。そして、スロット番号ｓ９をグループ１０−１へ返送する。
【０１７０】
〔Ｓ６６〕グループＧ１０−１の管理サーバ２０−４は、受信したスロット番号ｓ９をから、スロット番号ｓ９に最も近い番号を割当てる。例えば、スロットｓ８を割当てるとする。そして、スロット番号ｓ８を前段のグループへ返送する。以降同様な動作が開始点のグループまで遡って行われる。
【０１７１】
以上説明したように、グループＧ（ｎ）に、スロットが割当済みの経路が存在しない場合、グループＧ（ｎ−１）の管理サーバ（第１のスロット割当部）では、グループＧ（ｎ−１）内で、所定時間経路で送信するためのスロットを仮割当てし、グループＧ（ｎ−１）のエッジノード（第１のリスト作成部）は、割当てられたスロットのスロット番号を候補リストに登録してグループＧ（ｎ）へ送信する。
【０１７２】
同様に、グループＧ（ｎ）の管理サーバ（第２のスロット割当部）は、グループＧ（ｎ）内で、所定時間経路で送信するためのスロットを仮割当てし、グループＧ（ｎ）のエッジノード（第２のリスト作成部）は、割当てられたスロットのスロット番号を候補リストに登録する。
【０１７３】
ここで、グループＧ（ｎ）に次段グループＧ（ｎ＋１）が接続していれば、グループＧ（ｎ）のエッジノードは、グループＧ（ｎ＋１）へ候補リストを中継送信する。また、グループＧ（ｎ）が終端グループであれば、グループＧ（ｎ−１）、Ｇ（ｎ）の各管理サーバは、仮割当てしたスロットで確定する。すなわち、仮割当てしたスロットでパケットに対してスロット割当を行う。これにより、複数グループが接続されるネットワークにおいて、各グループでのスロット割当を効率よく実施することが可能になる。
【０１７４】
一方、グループＧ（ｎ）に、スロットが割当済みの経路がすでに存在している場合、グループＧ（ｎ）の管理サーバは、グループＧ（ｎ−１）から送信された候補リストを破棄する。そして、グループＧ（ｎ）ですでに割当済みのスロットのスロット番号を前段のグループＧ（ｎ−１）返送するための制御を行う。
【０１７５】
また、グループＧ（ｎ−１）の管理サーバは、返送されたスロットのスロット番号に対して、最も時間差の小さなスロット番号を選択し、選択したスロット番号を持つスロットをパケットに割当てる。そして、前段のグループＧ（ｎ−２）に対して、グループＧ（ｎ−１）で選択したスロット番号を遡って返送する。以降同様な動作が開始グループに達するまで遡って行われる。
【０１７６】
このように、複数のスロット候補を隣接するグループの管理サーバへ通知し、最終的に終端の管理サーバが最も短い時間で割当て可能なものを選択するまでの間にスロット割当て済みのグループが存在した場合は、最初の割当て候補を破棄して割当て済みのスロットに近いスロットを割当てる構成とした。これにより、最短時間の経路を開始グループから終端グループまで生成することができ、伝送品質の向上を図ることが可能になる。
【０１７７】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。
【符号の説明】
【０１７８】
１０ 通信装置
１１ 経路算出部
１２ 経路割当制御部
【特許請求の範囲】
【請求項１】
ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
通信スロットに前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当てを選択する、
ことを特徴とする通信装置。
【請求項２】
前記経路割当制御部は、前記通信スロットの最大数をＳ、前記経路の数をＣ、ノード間のリンク速度をｖ、１つの前記通信スロットの帯域をｂとし、（ｖ／ｂ）個の前記通信スロットに割当可能な前記経路の総和をｋとした場合に、前記期待値を、
期待値＝ｋ／（Ｃ×Ｓ）
で算出することを特徴とする請求項１記載の通信装置。
【請求項３】
前記経路割当制御部は、前記経路に含まれるリンクの組み合わせを求め、前記リンクの組み合わせのホップ数が、最短経路のホップ数に上限値を加算した値以上となるリンクの組み合わせを持つ前記経路に対しては、前記通信スロットへの割当から除外することを特徴とする請求項１記載の通信装置。
【請求項４】
経路割当方法において、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
通信スロットに前記経路を割当てる場合に、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当てを選択する、
ことを特徴とする経路割当方法。
【請求項５】
グループ間に跨ってパケット通信を行う通信装置において、
パケットに通信スロットを割当てるスロット割当部と、
パケットバッファと、
を備え、
前記スロット割当部は、直前のグループで割当てられた通信スロットで送信された前記パケットを受信すると、直前のグループで割当てられた通信スロットの通信スロット番号を、自グループに対応する番号である自通信スロット番号に変換し、
前記パケットバッファは、前記自通信スロット番号と、前記パケットとを対にして格納し、
前記スロット割当部は、パケット送信時には、前記自通信スロット番号を選択し、前記自通信スロット番号を持つ通信スロットを前記パケットに割当て、
前記自通信スロット番号を選択しない場合は、前記自通信スロット番号よりも時間的に後で、かつ前記自通信スロット番号に対して最も時間差の小さな通信スロット番号を選択し、選択した通信スロット番号を持つ通信スロットを前記パケットに割当てる、
ことを特徴とする通信装置。
【請求項６】
グループ間に跨ってパケット通信を行う通信システムにおいて、
パケットに第１の通信スロットを割当てる第１のスロット割当部と、割当てた前記第１の通信スロットの通信スロット番号をリストに登録し、次段のグループへ送信する第１のリスト作成部とを含み、第１のグループ内に位置する第１の通信装置と、
パケットに第２の通信スロットを割当てる第２のスロット割当部と、割当てた前記第２の通信スロットの通信スロット番号を、前記第１のグループから送信された前記リストに登録する第２のリスト作成部とを含み、前記第１のグループに接続する第２のグループ内に位置する第２の通信装置と、
を有することを特徴とする通信システム。
【請求項７】
前記第２のグループに、前記第２の通信スロットが割当済みの経路が存在しない場合、
前記第１のスロット割当部は、前記第１のグループ内で、所定時間経路で送信するための前記第１の通信スロットを前記パケットに仮割当てし、
前記第１のリスト作成部は、割当てられた前記第１の通信スロットの通信スロット番号を前記リストに登録して前記第２のグループへ送信し、
前記第２のスロット割当部は、前記第２のグループ内で、所定時間経路で送信するための前記第２の通信スロットを前記パケットに仮割当てし、
前記第２のリスト作成部は、割当てられた前記第２の通信スロットの通信スロット番号を前記リストに登録し、
前記第２のグループに次段グループがあれば、前記第２のリスト作成部は、前記次段グループへ前記リストを中継送信し、
前記第２のグループが終端グループであれば、前記第１のスロット割当部は、仮割当てした前記第１の通信スロットを確定し、前記第２のスロット割当部は、仮割当てした前記第２の通信スロットで確定する、
ことを特徴とする請求項６記載の通信システム。
【請求項８】
前記第２のグループに、前記第２の通信スロットが割当済みの経路がすでに存在している場合、
前記第２のスロット割当部は、
前記第１のグループから送信された前記リストを破棄し、
前記第２の通信スロットの通信スロット番号を前記第１のグループへ返送し、
前記第１のスロット割当部は、返送された前記第２の通信スロットの通信スロット番号に対して、最も時間差の小さな通信スロット番号を選択し、選択した通信スロット番号を持つ通信スロットを前記パケットに割当て、
前記選択した通信スロット番号を前段のグループへ遡って返送する、
ことを特徴とする請求項６記載の通信システム。
【請求項１】
ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
通信スロットに前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当てを選択する、
ことを特徴とする通信装置。
【請求項２】
前記経路割当制御部は、前記通信スロットの最大数をＳ、前記経路の数をＣ、ノード間のリンク速度をｖ、１つの前記通信スロットの帯域をｂとし、（ｖ／ｂ）個の前記通信スロットに割当可能な前記経路の総和をｋとした場合に、前記期待値を、
期待値＝ｋ／（Ｃ×Ｓ）
で算出することを特徴とする請求項１記載の通信装置。
【請求項３】
前記経路割当制御部は、前記経路に含まれるリンクの組み合わせを求め、前記リンクの組み合わせのホップ数が、最短経路のホップ数に上限値を加算した値以上となるリンクの組み合わせを持つ前記経路に対しては、前記通信スロットへの割当から除外することを特徴とする請求項１記載の通信装置。
【請求項４】
経路割当方法において、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
通信スロットに前記経路を割当てる場合に、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当てを選択する、
ことを特徴とする経路割当方法。
【請求項５】
グループ間に跨ってパケット通信を行う通信装置において、
パケットに通信スロットを割当てるスロット割当部と、
パケットバッファと、
を備え、
前記スロット割当部は、直前のグループで割当てられた通信スロットで送信された前記パケットを受信すると、直前のグループで割当てられた通信スロットの通信スロット番号を、自グループに対応する番号である自通信スロット番号に変換し、
前記パケットバッファは、前記自通信スロット番号と、前記パケットとを対にして格納し、
前記スロット割当部は、パケット送信時には、前記自通信スロット番号を選択し、前記自通信スロット番号を持つ通信スロットを前記パケットに割当て、
前記自通信スロット番号を選択しない場合は、前記自通信スロット番号よりも時間的に後で、かつ前記自通信スロット番号に対して最も時間差の小さな通信スロット番号を選択し、選択した通信スロット番号を持つ通信スロットを前記パケットに割当てる、
ことを特徴とする通信装置。
【請求項６】
グループ間に跨ってパケット通信を行う通信システムにおいて、
パケットに第１の通信スロットを割当てる第１のスロット割当部と、割当てた前記第１の通信スロットの通信スロット番号をリストに登録し、次段のグループへ送信する第１のリスト作成部とを含み、第１のグループ内に位置する第１の通信装置と、
パケットに第２の通信スロットを割当てる第２のスロット割当部と、割当てた前記第２の通信スロットの通信スロット番号を、前記第１のグループから送信された前記リストに登録する第２のリスト作成部とを含み、前記第１のグループに接続する第２のグループ内に位置する第２の通信装置と、
を有することを特徴とする通信システム。
【請求項７】
前記第２のグループに、前記第２の通信スロットが割当済みの経路が存在しない場合、
前記第１のスロット割当部は、前記第１のグループ内で、所定時間経路で送信するための前記第１の通信スロットを前記パケットに仮割当てし、
前記第１のリスト作成部は、割当てられた前記第１の通信スロットの通信スロット番号を前記リストに登録して前記第２のグループへ送信し、
前記第２のスロット割当部は、前記第２のグループ内で、所定時間経路で送信するための前記第２の通信スロットを前記パケットに仮割当てし、
前記第２のリスト作成部は、割当てられた前記第２の通信スロットの通信スロット番号を前記リストに登録し、
前記第２のグループに次段グループがあれば、前記第２のリスト作成部は、前記次段グループへ前記リストを中継送信し、
前記第２のグループが終端グループであれば、前記第１のスロット割当部は、仮割当てした前記第１の通信スロットを確定し、前記第２のスロット割当部は、仮割当てした前記第２の通信スロットで確定する、
ことを特徴とする請求項６記載の通信システム。
【請求項８】
前記第２のグループに、前記第２の通信スロットが割当済みの経路がすでに存在している場合、
前記第２のスロット割当部は、
前記第１のグループから送信された前記リストを破棄し、
前記第２の通信スロットの通信スロット番号を前記第１のグループへ返送し、
前記第１のスロット割当部は、返送された前記第２の通信スロットの通信スロット番号に対して、最も時間差の小さな通信スロット番号を選択し、選択した通信スロット番号を持つ通信スロットを前記パケットに割当て、
前記選択した通信スロット番号を前段のグループへ遡って返送する、
ことを特徴とする請求項６記載の通信システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【公開番号】特開２０１１−１９９８４０（Ｐ２０１１−１９９８４０Ａ）
【公開日】平成２３年１０月６日（２０１１．１０．６）
【国際特許分類】
【出願番号】特願２０１０−２６８９７０（Ｐ２０１０−２６８９７０）
【出願日】平成２２年１２月２日（２０１０．１２．２）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度、総務省、「低消費電力型通信技術等の研究開発（エコインターネットの実現）」研究開発委託契約に基づく開発項目「簡素化ルータを用いた省電力フォワーディング技術」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年１０月６日（２０１１．１０．６）
【国際特許分類】
【出願日】平成２２年１２月２日（２０１０．１２．２）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度、総務省、「低消費電力型通信技術等の研究開発（エコインターネットの実現）」研究開発委託契約に基づく開発項目「簡素化ルータを用いた省電力フォワーディング技術」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]