JP5397167B2 - タイムスロット割り当て方法、プログラム及び装置 - Google Patents

Description

本技術は、有線ネットワークにおいて時分割でデータ転送を行う分野の技術に関する。

例えば、時分割でデータ転送を行う技術として、ＴＤＭ（Time Division Multiplexing）などの技術が知られている。ＴＤＭでは、１フレームを複数のタイムスロットに区切り、タイムスロット毎に別々のデータ転送を行う。

なお、タイムスロット毎にデータ転送を行う場合、利用経路が増えると、その分タイムスロットも多く必要となる。但し、より多くのタイムスロットを設けるためには、１フレームをより細かく区切る必要があり、その結果、１経路当たりの帯域が狭くなってしまう。

特表２００４−５１１９５７号公報 特開平１１−２５２１７１号公報

しかしながら、従来技術では、有線ネットワークにおいて適切な順序でデータ転送経路に対してタイムスロットの割り当てを行うようにはなっておらず、必ずしも効率的ではない。

従って、本技術の目的は、有線ネットワークにおいてデータ転送経路に対して効率的なタイムスロットの割り当てを行うための技術を提供することである。

本タイムスロット割り当て方法は、ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部と、送信元ノード及び宛先ノードの組み合わせ毎に割り当て優先度を格納する優先度格納部と、ネットワークにおけるノード間のリンクの使用状態をタイムスロット毎に格納するリンク情報格納部と、割り当て情報格納部と、記憶装置とにアクセス可能なコンピュータにより実行される方法である。そして、本タイムスロット割り当て方法は、スロット情報格納部に格納されているスロット本数が１以上である、送信元ノード及び宛先ノードの組み合わせの各々について、ノード間のリンクのうちリンク情報格納部において未使用となっているリンクである未使用リンクによって送信元ノードから宛先ノードへの経路を形成し得るタイムスロットが存在するか判断する判断ステップと、上記判断ステップにおいて、未使用リンクによる経路を形成し得るタイムスロットが存在すると判断された組み合わせの各々について、未使用リンクによる経路を形成し得るタイムスロット毎に、未使用リンクによる経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、優先度格納部に格納され且つ当該組み合わせに対応する割り当て優先度と、リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、送信元ノードと宛先ノードと最短経路とタイムスロットの識別情報とに対応付けて記憶装置に格納する評価値算出ステップと、記憶装置に格納された評価値の中から最大評価値を特定し、記憶装置に格納され且つ当該最大評価値に対応する送信元ノード、宛先ノード、最短経路及びタイムスロットの識別情報を含むスロット割り当て情報を割り当て情報格納部に格納するステップとを含む。

有線ネットワークにおいてデータ転送経路に対して効率的なタイムスロットの割り当てを行うことができる。

図１は、本技術の実施の形態の前提となる時分割データ転送方式を説明するための図である。 図２は、時分割データ転送方式において、１フレームを３分割した場合の例を示す図である。 図３は、本実施の形態における管理サーバの機能ブロック図である。 図４は、帯域情報格納部に格納されるデータの一例を示す図である。 図５は、図１に示したネットワーク構成をノード番号で表現した場合の図である。 図６は、パケット送信の流れを可視化した図である。 図７は、優先度格納部に格納されるデータの一例を示す図である。 図８は、リンク情報格納部に格納されるデータの一例を示す図である。 図９は、上り方向のリンクと下り方向のリンクとを別々に表した場合の図である。 図１０は、スロット情報格納部に格納されるデータの一例を示す図である。 図１１は、最小ホップ数格納部に格納されるデータの一例を示す図である。 図１２は、評価値格納部に格納されるデータの一例を示す図である。 図１３は、割り当て情報格納部に格納されるデータの一例を示す図である。 図１４は、タイムスロットの割り当てを行う際の処理フロー（第１の部分）を示す図である。 図１５は、隣接行列の一例を示す図である。 図１６は、評価値算出処理の処理フローを示す図である。 図１７は、評価値の具体的な計算例を説明するための図である。 図１８は、タイムスロットの割り当てを行う際の処理フロー（第２の部分）を示す図である。 図１９は、リンク情報格納部に格納されるデータの一例を示す図である。 図２０は、スロット情報格納部に格納されるデータの一例を示す図である。 図２１は、隣接行列の一例を示す図である。 図２２は、従来手法によってタイムスロットを割り当てた場合の一例を示す図である。 図２３は、本実施の形態に係る手法によってタイムスロットを割り当てた場合の一例を示す図である。 図２４は、本実施の形態に係る手法によるシミュレーションの結果を示す図である。 図２５は、シミュレーション時の第１のネットワーク構成（ツリー型）を示す図である。 図２６は、シミュレーション時の第２のネットワーク構成（ラダー型）を示す図である。 図２７は、シミュレーション時の第３のネットワーク構成（スター型）を示す図である。 図２８は、本技術の第１の態様に係るタイムスロット割り当て方法の処理フローを示す図である。 図２９は、本技術の第２の態様に係るタイムスロット割り当て装置の機能ブロック図を示す図である。 図３０は、コンピュータの機能ブロック図である。

まず、図１及び図２を用いて、本実施の形態の前提となる時分割データ転送方式を簡単に説明する。例えば、図１に示すようなネットワークを想定して説明する。図１において、ルータ１０４はルータ１０５、ルータ１０６及びルータ１０７と接続され、ルータ１０５はルータ１０６及びルータ１０７と接続され、ルータ１０６はルータ１０７と接続されている。さらに、ルータ４はエッジルータ１００と接続され、ルータ１０５はエッジルータ１０１と接続され、ルータ１０６はエッジルータ１０２と接続され、ルータ１０７はエッジルータ１０３と接続されている。なお、エッジルータ１００乃至１０３の各々は、外部ネットワーク（図示せず）に接続されているものとする。また、本実施の形態における主要な処理を実施する管理サーバ２００は各エッジルータと制御線（図示せず）によって接続されている。なお、本実施の形態では、外部ネットワークに接続されていないルータ１０４乃至１０７を中継ルータと呼ぶこともある。また、エッジルータ及び中継ルータについてはノードと呼ぶこともある。なお、これは簡単なネットワークの一例であるから、ネットワーク構成はこれに限定されるものではない。

例えばエッジルータ１００に外部ネットワークからのパケットが到着すると（図１：ステップ（１））、エッジルータ１００は、スロット割り当て要求を管理サーバ２００に送信する（ステップ（２））。例えばこのスロット割り当て要求には、送信元エッジルータ及び宛先エッジルータの指定が含まれる。なお、本実施の形態では、送信元エッジルータを送信元ノードと呼び、宛先エッジルータを宛先ノードと呼ぶことにする。ここでは、エッジルータ１００が送信元ノードとして指定され、エッジルータ１０３が宛先ノードとして指定されたものとする。

そして、管理サーバ２００は、送信元ノード及び宛先ノードの指定を含むスロット割り当て要求をエッジルータ１００から受信すると、指定された送信元ノードから宛先ノードへのパケット送信に対して事前に割り当てておいたタイムスロット（以下、単にスロットと呼ぶ場合もある）の番号をエッジルータ１００に送信する（ステップ（３））。この際、送信元ノードから宛先ノードまでの経路情報も併せて送信する。なお、管理サーバ２００では、送信元ノード及び宛先ノードの組み合わせ毎に、いずれのタイムスロットを使用するかを事前に決定しておく。ここでは、エッジルータ１００からエッジルータ１０３へのパケット送信に対してスロット２が割り当てられていたものとする。

そして、エッジルータ１００は、タイムスロットの番号（すなわち、２）と経路情報とを管理サーバ２００から受信すると、これらを受信した直後のスロット２において、スロット２を予約するための制御パケット（予約パケットとも呼ぶ）を、経路情報に従ってエッジルータ３に送信する（ステップ（４））。この予約パケットを送信することにより、経路上の中継ルータ（図１では、ルータ１０４及びルータ１０７）に、エッジルータ１００からエッジルータ１０３へのパケット送信をスロット２で行うことを知らせる。

そして、以降のスロット２においては、エッジルータ１００からエッジルータ１０３へのパケット送信が行われる（ステップ（５））。例えば、「エッジルータ１００−＞ルータ１０４−＞ルータ１０７−＞エッジルータ１０３」の経路でパケット送信を行う場合、スロット２においては、ルータ１０４は、エッジルータ１００からのパケットを受信すると、従来のルーティング処理を行うことなくルータ１０７に転送する。同様に、スロット２においては、ルータ１０７は、ルータ１０４からのパケットを受信すると、従来のルーティング処理を行うことなくエッジルータ１０３に転送する。

例えば図２に、１フレームを３つのタイムスロットに区切った場合の例を示す。図２の例では、スロット０（図２の時間軸では、ｔ０〜ｔ１、ｔ３〜ｔ４、・・・）において、エッジルータ１００とエッジルータ１０１との間のパケット通信が行われ、スロット１（図２の時間軸上では、ｔ１〜ｔ２、ｔ４〜ｔ５、・・・）において、エッジルータ１００とエッジルータ１０２との間のパケット通信が行われ、スロット２（図２の時間軸上では、ｔ２〜ｔ３、ｔ５〜ｔ６、・・・）において、エッジルータ１０１とエッジルータ１０３との間のパケット通信が行われるようになっている。図２は、パケット通信を行う経路が３つの場合の例を示しており、パケット通信を行う経路が他にもある場合には、１フレームを４つ以上のタイムスロットに区切っておく。

このような時分割データ転送方式によれば、中継ルータにおいて、パケットバッファリング及びルーティングテーブル検索処理を行わなくて済むようになる。従って、パケットバッファリング及びルーティング処理で消費していた電力を削減でき、中継ルータの省電力化が図れる。

しかしながら、例えば、ネットワークの規模が大きくなると、パケット通信を行う経路も増えるため、より多くのタイムスロットが必要となる。但し、より多くのタイムスロットを設けるためには、上で述べたように１フレームをより細かく区切る必要があり、その結果、１経路当たりの帯域が狭くなってしまう。そこで、本実施の形態では、管理サーバ２００において、以下に述べるような処理を実施することにより、パケット通信を行う全ての経路が、なるべく少ないタイムスロットに収まるようにする。以下、本技術の一実施の形態に係る管理サーバ２００について説明する。

図３に、管理サーバ２００の機能ブロック図を示す。管理サーバ２００は、帯域情報格納部２００１と、優先度格納部２００３と、リンク情報格納部２００５と、スロット本数計算部２００７と、スロット情報格納部２００９と、最小ホップ数計算部２０１１と、最小ホップ数格納部２０１３と、評価値算出部２０１５と、評価値格納部２０１７と、割り当て決定部２０１９と、割り当て情報格納部２０２１と、スロット割り当て処理部２０２３とを有する。

なお、スロット本数計算部２００７は、帯域情報格納部２００１に格納されるデータに基づき、送信元ノード及び宛先ノードの各組み合わせについて、送信元ノードから宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットの本数を計算し、スロット情報格納部２００９に格納する。最小ホップ数計算部２０１１は、帯域情報格納部２００１とリンク情報格納部２００５とに格納されるデータに基づき、送信元ノードから宛先ノードまでの最小ホップ数を計算し、最小ホップ数格納部２０１３に格納する。評価値算出部２０１５は、優先度格納部２００３とリンク情報格納部２００５とスロット情報格納部２００９と最小ホップ数格納部２０１３とに格納されるデータに基づき、後で説明する評価値を算出し、評価値格納部２０１７に格納する。また、評価値算出部２０１５は、評価値を算出した後、最大評価値を特定するよう、割り当て決定部２０１９に指示する。割り当て決定部２０１９は、評価値算出部２０１５からの指示に応じて、評価値格納部２０１７に格納されている評価値の中から最大評価値を特定したり、送信元ノードと宛先ノードとスロット番号と経路情報とを含むスロット割り当て情報を生成して割り当て情報格納部２０２１に格納したりする。また、割り当て決定部２０１９は、リンク情報格納部２００５及びスロット情報格納部２００９に格納されるデータを更新し、割り当てが必要な経路が存在する場合には、再度評価値を計算するよう評価値算出部２０１５に指示する。スロット割り当て処理部２０２３は、エッジルータからスロット割り当て要求を受信した場合、スロット割り当て要求で指定された送信元ノード及び宛先ノードに対応するスロット割り当て情報を割り当て情報格納部２０２１から取得し、エッジルータに送信する。

図４に、帯域情報格納部２００１に格納されるデータの一例を示す。図４の例では、帯域情報格納部２００１には、送信元ノード及び宛先ノードの組み合わせ毎に送信元ノードから宛先ノードへのパケット送信に関する通信帯域（単位：Ｍｂｐｓ（megabit per second））の情報が予め格納されるようになっている。なお、以下の説明をわかりやすくするために、図１に示したエッジルータ１００のノード番号は「０」であり、エッジルータ１０１のノード番号は「１」であり、エッジルータ１０２のノード番号は「２」であり、エッジルータ１０３のノード番号は「３」であるものとする。また、ルータ１０４のノード番号は「４」であり、ルータ１０５のノード番号は「５」であり、ルータ１０６のノード番号は「６」であり、ルータ１０７のノード番号は「７」であるものとする。従って、図１に示したネットワーク構成を、ノード番号を用いて表現すると図５のようになる。

例えば、図４では、ノード「０」からノード「２」へ、１０Ｍｂｐｓのパケット送信が行われることを表している。また、ノード「０」からノード「３」へ、５Ｍｂｐｓのパケット送信が行われることを表している。さらに、ノード「１」からノード「２」へ５Ｍｂｐｓのパケット送信が行われることを表している。また、ノード「１」からノード「３」へ１０Ｍｂｐｓのパケット送信が行われることを表している。さらに、ノード「２」からノード「１」へ１０Ｍｂｐｓのパケット送信が行われることを表している。なお、送信元ノード及び宛先ノードの組み合わせのうち、パケット送信が行われない組み合わせについては、通信帯域として「０」が設定される。すなわち、図４では、例えばノード「０」からノード「１」へはパケット送信が行われないことを表している。なお、図４に示した内容を見やすいように図示すると、図６のようになる。図６における矢印は、パケット送信が行われることを表している。このように、本実施の形態では、送信元ノードと宛先ノードとの間で、どのぐらいの通信帯域のパケット送信が行われるか等の情報が事前に与えられ、管理サーバ２００の帯域情報格納部２００１に格納されるものとする。

図７に、優先度格納部２００３に格納されるデータの一例を示す。図７の例では、優先度格納部２００３には、送信元ノード及び宛先ノードの組み合わせ毎に割り当て優先度が格納されるようになっている。なお、図７では、値が小さいほど、割り当て優先度が高いことを示している。すなわち、図７では、送信元ノード「０」及び宛先ノード「２」についての割り当て優先度（＝１）が最も高く、送信元ノード「１」及び宛先ノード「２」についての割り当て優先度（＝５）が最も低くなっている。本実施の形態では、帯域情報格納部２００１に格納される通信帯域が大きいほど、割り当て優先度が高くなるように優先度格納部２００３を設定しておく。なお、帯域情報格納部２００１で「０」が設定されている組み合わせについては、優先度格納部２００３において「−」が設定される。

図８に、リンク情報格納部２００５に格納されるデータの一例を示す。図８の例では、上り方向のリンクの使用状態と下り方向のリンクの使用状態とを別々に管理するようになっている。例えば図５では、上り方向のリンクと下り方向のリンクとをまとめて１本の線で表しているが、これらを別々に図示すると図９のようになる。すなわち、図９における矢印の本数（２０本）分のレコードが、リンク情報格納部２００５に格納される。さらに、図８の例では、リンク情報格納部２００５には、当該リンクの両端ノードのうち始点側ノードの番号（ｓｒｃ）の列と、当該リンクの両端ノードのうち終点側ノードの番号（ｄｓｔ）の列と、スロット０の列と、スロット１の列と、・・・と、スロットｎの列とが含まれる。なお、スロット０からスロットｎまでの各列において、当該スロットで使用済みのリンクについては「１」が設定され、当該スロットで未使用のリンクについては「０」が設定される。

図１０に、スロット情報格納部２００９に格納されるデータの一例を示す。図１０の例では、スロット情報格納部２００９には、送信元ノード及び宛先ノードの組み合わせ毎に送信元ノードから宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットの本数（以下、スロット本数と呼ぶ）が格納される。例えば図１０では、ノード「０」からノード「２」へのパケット送信に対して２本のタイムスロットを割り当てる必要があることを表している。また、ノード「０」からノード「３」へのパケット送信に対して１本のタイムスロットを割り当てる必要があることを表している。さらに、ノード「１」からノード「２」へのパケット送信に対して１本のタイムスロットを割り当てる必要があることを表している。また、ノード「１」からノード「３」へのパケット送信に対して２本のタイムスロットを割り当てる必要があることを表している。さらに、ノード「２」からノード「１」へのパケット送信に対して２本のタイムスロットを割り当てる必要があることを表している。なお、詳細は後で説明するが、帯域情報格納部２００１に格納されるデータを基に、スロット本数が計算され、スロット情報格納部２００９に設定される。

図１１に、最小ホップ数格納部２０１３に格納されるデータの一例を示す。図１１の例では、最小ホップ数格納部２０１３には、送信元ノード及び宛先ノードの組み合わせ毎に送信元ノードから宛先ノードまでの最小ホップ数が格納される。なお、最小ホップ数は、例えばダイクストラ法などにより計算され、最小ホップ数格納部２０１３に設定される。なお、帯域情報格納部２００１で「０」が設定されている組み合わせについては、最小ホップ数格納部２０１３において「−」が設定される。

図１２に、評価値格納部２０１７に格納されるデータの一例を示す。図１２の例では、評価値格納部２０１７には、送信元ノードの列と、宛先ノードの列と、スロット番号の列と、経路の列と、評価値の列とが含まれる。評価値格納部２０１７には、評価値算出部２０１５により算出された評価値と、当該評価値に関連する送信元ノード、宛先ノード、スロット番号及び経路とが格納される。

図１３に、割り当て情報格納部２０２１に格納されるデータの一例を示す。図１３の例では、割り当て情報格納部２０２１には、送信元ノードの列と、宛先ノードの列と、スロット番号の列と、経路の列とが含まれる。割り当て情報格納部２０２１には、送信元ノードから宛先ノードへのパケット送信に対して割り当てられたタイムスロットの番号と、送信元ノードから宛先ノードまでの経路とが格納される。なお、スロット割り当て処理部２０２３は、エッジルータからスロット割り当て要求を受信した場合、割り当て情報格納部２０２１から、スロット割り当て要求で指定された送信元ノード及び宛先ノードに対応するスロット番号及び経路を取得し、エッジルータに送信する

次に、図１４乃至図２１を用いて管理サーバ２００の処理内容について説明する。なお、前提として、帯域情報格納部２００１には図４に示したようなデータが格納され、優先度格納部２００３には図７に示したようなデータが格納されているものとする。また、リンク情報格納部２００５には図８に示したようなレコードが格納され、スロット０からスロットｎまでの各列における値は、全て「０」で初期化されているものとする。

まず、スロット本数計算部２００７が、帯域情報格納部２００１に格納されているデータに基づき、送信元ノード及び宛先ノードの各組み合わせについて、送信元ノードから宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットの本数を計算し、スロット情報格納部２００９に格納する（図１４：ステップＳ１）。具体的には、帯域情報格納部２００１に格納されている通信帯域の最大公約数を算出し、送信元ノード及び宛先ノードの各組み合わせについて、当該組み合わせに対応する通信帯域を最大公約数で除した値を、スロット本数として算出する。例えば図４に示したようなデータが帯域情報格納部２００１に格納されている場合、最大公約数は５となり、通信帯域が１０（Ｍｂｐｓ）であれば、スロット本数は２本（＝１０÷５）となる。また、通信帯域が５（Ｍｂｐｓ）であれば、スロット本数は１本（＝５÷５）となる。なお、通信帯域が０である場合には、スロット本数は０となる。従って、本ステップの処理を実施すると、スロット情報格納部２００９には、図１０に示したようなデータが格納される。このように、最大公約数を基準にスロット本数を決定することで、より無駄のない、タイムスロットの割り当てを行うことができるようになる。なお、スロット１本分の帯域と実際の物理的な帯域とで１スロットの期間が決まる。上の例で物理的な帯域が１０Ｍｂｐｓであれば、１スロット０．５秒であり、物理的な帯域が５Ｍｂｐｓであれば、１スロット１秒となる。

そして、最小ホップ数計算部２０１１が、帯域情報格納部２００１及びリンク情報格納部２００５に格納されているデータに基づき、送信元ノード及び宛先ノードの各組み合わせについて、送信元ノードから宛先ノードまでの最小ホップ数を計算し、最小ホップ数格納部２０１３に格納する（ステップＳ３）。具体的には、送信元ノード及び宛先ノードの各組み合わせについて、リンク情報格納部２００５に格納されているデータから生成される隣接行列を用いてダイクストラ法により、送信元ノードから宛先ノードまでの最短経路を特定し、最短経路におけるホップ数を最小ホップ数として算出する。なお、帯域情報格納部２００１において０が設定されている、送信元ノード及び宛先ノードの組み合わせについては最小ホップ数を計算しなくともよい。例えば図８に示したようなデータがリンク情報格納部２００５に格納されている場合、図１５に示すような隣接行列が生成される。例えば、始点側ノード（ｓｒｃ）をノードｘとし、終点側ノード（ｄｓｔ）をノードｙとした場合に、ノードｘとノードｙとの間にリンクが存在すれば、隣接行列の（ｘ，ｙ）成分には「１」が設定される。一方、ノードｘとノードｙとの間にリンクが存在しなければ、隣接行列の（ｘ，ｙ）成分には「０」が設定される。例えば、図８では、ノード「０」からノード「４」へのリンクが存在しているので、図１５に示した隣接行列の（０，４）成分には「１」が設定されている。なお、ダイクストラ法により最短距離を特定する処理自体は、従来と変わらないので、詳細な説明は省略する。また、ステップＳ１及びステップＳ３については処理順序を入れ替えることが可能であり、並列に実行することも可能である。

その後、評価値算出部２０１５は、スロット情報格納部２００９において送信元ノード及び宛先ノードの組み合わせのうち先頭の組み合わせを処理対象として特定する（ステップＳ５）。ここでは、処理順序が予め定められているものとする。例えば、図１０（スロット情報格納部２００９）において、送信元ノードのノード番号が小さいものから順に処理する場合には、送信元ノード「０」及び宛先ノード「１」の組み合わせ、送信元ノード「０」及び宛先ノード「２」の組み合わせ、送信元ノード「０」及び宛先ノード「３」の組み合わせ、送信元ノード「１」及び宛先ノード「０」の組み合わせ、・・・、送信元ノード「３」及び宛先ノード「１」の組み合わせ、送信元ノード「３」及び宛先ノード「２」の組み合わせという順序となる。この場合、送信元ノード「０」及び宛先ノード「１」の組み合わせが先頭の組み合わせであり、ステップＳ５において処理対象として特定される。また、評価値算出部２０１５は、評価値格納部２０１７にデータが格納されているデータをクリアする（ステップＳ７）。なお、評価値格納部２０１７にデータが格納されていない場合には、本ステップをスキップしてもよい。また、ステップＳ５及びステップＳ７については処理順序を入れ替えることが可能であり、並列に実行することも可能である。

そして、評価値算出部２０１５は、スロット情報格納部２００９において、処理対象の組み合わせに係るスロット本数が０であるか判断する（ステップＳ９）。スロット情報格納部２００９において、処理対象の組み合わせに係るスロット本数が０の場合（ステップＳ９：Ｙｅｓルート）、以下で説明する評価値算出処理（ステップＳ１１）をスキップし、ステップＳ１３の処理に移行する。なお、スロット本数が０に設定されているというのは、タイムスロットの割り当てが不要ということである。

一方、スロット情報格納部２００９において、処理対象の組み合わせに係るスロット本数が１以上の場合（ステップＳ９：Ｎｏルート）、評価値算出部２０１５は、優先度格納部２００３とリンク情報格納部２００５とスロット情報格納部２００９と最小ホップ数格納部２０１３とに格納されているデータを用いて、処理対象の組み合わせについて評価値算出処理を実施する（ステップＳ１１）。なお、評価値算出処理については図１６及び図１７を用いて説明する。

まず、評価値算出部２０１５は、変数ｉを０に設定する（図１６：ステップＳ３１）。なお、以下の処理において、ｉはスロットの番号を表す。そして、評価値算出部２０１５は、リンク情報格納部２００５に格納されているデータに基づき、スロットｉの未使用リンクによって送信元ノードから宛先ノードまでの経路を形成可能であるか判断する（ステップＳ３３）。スロットｉの未使用リンクによって送信元ノードから宛先ノードまでの経路を形成できない場合（ステップＳ３３：Ｎｏルート）、スロットｉを割り当てることはできないと判断し、以下で説明するステップＳ３５乃至ステップＳ３９をスキップし、ステップＳ４１の処理に移行する。

一方、スロットｉの未使用リンクによって送信元ノードから宛先ノードまでの経路を形成可能な場合（ステップＳ３３：Ｙｅｓルート）、評価値算出部２０１５は、スロットｉの未使用リンクによって形成される、送信元ノードから宛先ノードまでの経路のうち最短経路を特定する（ステップＳ３５）。具体的には、リンク情報格納部２００５に格納されているデータから生成される隣接行列を用いてダイクストラ法により、送信元ノードから宛先ノードまでの最短経路を特定する。なお、隣接行列を用いてダイクストラ法により最短経路を特定する処理は、基本的にはステップＳ３で述べた処理と同じである。但し、未使用リンクによって形成される最短経路を特定するためには、使用済みのリンクは存在しないものとみなしてダイクストラ法を適用する必要がある。従って、本ステップでは、スロットｉで既に使用済みのリンクがある場合には、隣接行列内の該当箇所の値を「１」から「０」に置き換える。そして、ダイクストラ法により最短経路を特定する。

そして、評価値算出部２０１５は、最小ホップ数格納部２０１３から処理対象の組み合わせに対応する最小ホップ数を取得し、ステップＳ３５において特定した最短経路におけるホップ数が最小ホップ数＋αより大きいか判断する（ステップＳ３７）。なお、「最小ホップ数＋α」は、許容ホップ数を示しており、本ステップでは、ステップＳ３５において特定した最短経路におけるホップ数が許容ホップ数を超えているか判断する。「α」の値は予め定められているものとする。ステップ３５において特定した最短経路におけるホップ数が最小ホップ数＋αより大きい場合（ステップＳ３７：Ｙｅｓルート）、ステップＳ３９をスキップし、ステップＳ４１の処理に移行する。なお、ステップＳ３５において特定した最短経路におけるホップ数が許容ホップ数を超えている場合、その経路でパケット送信を行うと、遅延時間が大きくなってしまう。従って、本実施の形態では、遅延時間が大きくなってしまうような経路は割り当てないようにする。

一方、ステップＳ３５において特定した最短経路におけるホップ数が最小ホップ数＋α以下の場合（ステップＳ３７：Ｎｏルート）、評価値算出部２０１５は、優先度格納部２００３から処理対象の組み合わせに対応する割り当て優先度を取得する。また、評価値算出部２０１５は、リンク情報格納部２００５において、スロットｉの使用済みリンクの数を計数する。具体的には、リンク情報格納部２００５のスロットｉの列において、「１」が設定されているリンクの数を計数する。

そして、評価値算出部２０１５は、割り当て優先度と、ステップＳ３５において特定した最短経路におけるホップ数と、スロットｉにおける使用済みリンク数とを用いて評価値を算出する（ステップＳ３９）。具体的には、以下の式によって算出する。
評価値 ＝（割り当て優先度の逆数）×（ホップ数）×（使用済みリンク数＋１）

なお、算出された評価値は、送信元ノード、宛先ノード、スロットｉ及び最短経路に対応付けて評価値格納部２０１７に格納される。

例えば、ノード「０」からノード「２」までの経路をスロット０に割り当てようとした場合の計算例を図１７（ａ）を用いて説明する。ここでは、ステップＳ３５において「０−＞４−＞６−＞２」という経路（ホップ数＝３）が最短経路として特定されたものとする。なお、本実施の形態では、ノード番号の系列で経路を表す（以下、同じ）。そして、優先度格納部２００３（図７）において、送信元ノード「０」及び宛先ノード「２」の組み合わせに対応する割り当て優先度は１である。また、リンク情報格納部２００５（図８）において、スロット０の使用済みリンク数は０である。従って、この場合の評価値は、（１／１）×３×（０＋１）＝３となる。なお、送信元ノード「０」と、宛先ノード「２」と、スロット番号「０」と、経路「０−＞４−＞６−＞２」と、評価値「３」とが評価値格納部２０１７に格納される。

上で述べた式は一例であって、必ずしも上で述べた式を用いらなければならないわけではない。上で述べた式では、割り当て優先度が高いほど評価値が大きくなり、ホップ数が大きいほど評価値が大きくなり、使用済みリンク数が大きいほど評価値が大きくなるようにしているが、同じような性質を持つ式であれば、他の式を採用するようにしてもよい。例えば乗算するのではなく加算するような式を採用してもよい。また、各要素（割り当て優先度、ホップ数及び使用済みリンク数）の中で、重要視したい要素に重み付けを行うような式を採用してもよい。

そして、評価値算出部２０１５は、スロットｉが最終スロット（すなわち、ｉ＝ｎ）であるか、又は、スロットｉの使用済みリンク数が０であるか判断する（ステップＳ４１）。スロットｉが最終スロットではなく、スロットｉの使用済みリンク数が０でもなければ（ステップＳ４１：Ｎｏルート）、評価値算出部２０１５は、変数ｉを１インクリメントする（ステップＳ４３）。その後、ステップＳ３３に戻り、上で述べた処理を繰り返す。すなわち、次のスロットについて処理を実施する。

一方、スロットｉが最終スロットの場合、又は、スロットｉの使用済みリンク数が０である場合（ステップＳ４１：Ｙｅｓルート）、評価値算出処理を終了し、元の処理に戻る。なお、本実施の形態では、先頭のタイムスロット（すなわち、スロット０）から順に、割り当て可能であるか判断していくので、スロットｉの使用済みリンク数が０の場合、次のスロットの使用済みリンク数も０となる。この場合、次のスロットについて処理を実施しても、割り当て優先度とホップ数と使用済みリンク数とが全て同じになるため、算出される評価値は今回と同じ値になる。従って、ステップＳ４１では、同じような計算を行わないようにするため、スロットｉの使用済みリンク数が０であるか判断し、スロットｉの使用済みリンク数が０であれば、評価値算出処理を終了する。これにより、処理負荷の削減に繋がる。

以上のような処理を実施することにより、割り当て優先度とホップ数と使用済みリンク数とを考慮した評価値を算出することができる。

図１４の説明に戻って、評価値算出処理（ステップＳ１１）を実施した後、評価値算出部２０１５は、処理対象の組み合わせが最後の組み合わせであるか判断する（ステップＳ１３）。例えば、上で述べたように、送信元ノードのノード番号が小さいものから順に処理する場合には、送信元ノード「３」及び宛先ノード「２」の組み合わせが最後の組み合わせである。処理対象の組み合わせが最後の組み合わせの場合（ステップＳ１３：Ｙｅｓルート）、評価値算出部２０１５は、最大評価値を特定するよう、割り当て決定部２０１９に指示する。その後、処理は端子Ａを介してステップＳ１７（図１８）に移行する。

一方、処理対象の組み合わせが最後の組み合わせでなければ（ステップＳ１３：Ｎｏルート）、評価値算出部２０１５は、予め定められた処理順序に従い、次の組み合わせを処理対象として特定する（ステップＳ１５）。そして、ステップＳ９に戻る。すなわち、予め定められた処理順序で、全ての組み合わせについて処理するまで、上で述べた処理を繰り返す。

例えば、送信元ノード「１」及び宛先ノード「３」の組み合わせが処理対象として特定された場合には、次のような評価値が算出される。ここでは、図１７（ｂ）に示すように、ステップＳ３５（図１６）において「１−＞５−＞７−＞３」という経路（ホップ数＝３）が最短経路として特定されたものとする。なお、優先度格納部２００３（図７）において、送信元ノード「１」及び宛先ノード「３」の組み合わせに対応する割り当て優先度は２である。また、リンク情報格納部２００５（図８）において、スロット０の使用済みリンク数は０である。従って、この場合の評価値は、（１／２）×３×（０＋１）＝１．５となる。なお、送信元ノード「１」と、宛先ノード「３」と、スロット番号「０」と、経路「１−＞５−＞７−＞３」と、評価値「１．５」とが評価値格納部２０１７に格納される。

また、例えば、送信元ノード「２」及び宛先ノード「１」の組み合わせが処理対象として特定された場合には、次のような評価値が算出される。ここでは、図１７（ｃ）に示すように、ステップＳ３５（図１６）において「２−＞６−＞５−＞１」という経路（ホップ数＝３）が最短経路として特定されたものとする。なお、優先度格納部２００３（図７）において、送信元ノード「２」及び宛先ノード「１」の組み合わせに対応する割り当て優先度は３である。また、リンク情報格納部２００５（図８）において、スロット０の使用済みリンク数は０である。従って、この場合の評価値は、（１／３）×３×（０＋１）＝１となる。なお、送信元ノード「２」と、宛先ノード「１」と、スロット番号「０」と、経路「２−＞６−＞５−＞１」と、評価値「１」とが評価値格納部２０１７に格納される。

図１８の説明に移行して、端子Ａの後、割り当て決定部２０１９は、評価値格納部２０１７に評価値が格納されているか判断する（図１８：ステップＳ１７）。評価値格納部２０１７に評価値が格納されていない場合（ステップＳ１７：Ｎｏルート）、割り当て可能なタイムスロットが存在しないと判断し、以下で説明するステップＳ１９乃至ステップＳ２７をスキップし処理を終了する。なお、評価値格納部２０１７に評価値が格納されていないということは、送信元ノードから宛先ノードまでの経路を形成可能なタイムスロットが１つも存在しなかったということである。

一方、評価値格納部２０１７に評価値が格納されている場合（ステップＳ１７：Ｙｅｓルート）、割り当て決定部２０１９は、評価値格納部２０１７に格納されている評価値の中から最大評価値を特定する（ステップＳ１９）。

そして、割り当て決定部２０１９は、評価値格納部２０１７から、最大評価値に対応する送信元ノード、宛先ノード、経路及びスロット番号を抽出する。そして、割り当て決定部２０１９は、抽出した送信元ノード、宛先ノード、経路及びスロット番号を含むスロット割り当て情報を生成し、割り当て情報格納部２０２１に格納する（ステップＳ２１）。例えば、図１２に示したようなデータが評価値格納部２０１７に格納され、評価値「３」が最大評価値として特定された場合には、評価値「３」に対応する送信元ノード「０」、宛先ノード「２」、スロット番号「０」及び経路「０−＞４−＞６−＞２」を含むスロット割り当て情報が生成され、割り当て情報格納部２０２１に格納される。これは、ノード「０」からノード「２」へのパケット送信に対してスロット０を割り当てたことを表し、送信経路として「０−＞４−＞６−＞２」を用いることを意味する。

そして、割り当て決定部２０１９は、リンク情報格納部２００５における、最大評価値に対応するスロット番号の列において、最大評価値に対応する経路に含まれるリンクの使用状態を使用済み（「１」）に設定する（ステップＳ２３）。例えば、最大評価値に対応するスロット番号及び経路としてスロット番号「０」及び経路「０−＞４−＞６−＞２」が抽出された場合に、本ステップの処理を実施すると、リンク情報格納部２００５には図１９に示すようなデータが格納される。図８に示したデータと比較すると、図１９では、リンク情報格納部２００５内のスロット０の列において、始点側ノード「０」及び終点側ノード「４」に係るリンクと、始点側ノード「４」及び終点側ノード「６」に係るリンクと、始点側ノード「６」及び終点側ノード「２」に係るリンクとに対応する値がそれぞれ「１」になっている。

そして、割り当て決定部２０１９は、スロット情報格納部２００９において、最大評価値に対応する送信元ノード及び宛先ノードの組み合わせについてのスロット本数を１デクリメントする（ステップＳ２５）。すなわち、上で説明したステップＳ２１において、送信元ノードから宛先ノードへのパケット送信に対してタイムスロットを割り当てているので、スロット情報格納部２００９内の該当するスロット本数を１減ずる。例えば送信元ノード「０」から宛先ノード「０」へのパケット送信に対してタイムスロットを割り当て、本ステップの処理を実施すると、スロット情報格納部２００９には図２０に示すようなデータが格納される。図１０に示したデータと比較すると、図２０では、送信元ノード「０」及び宛先ノード「２」の組み合わせについてのスロット本数が１本になっている。

そして、割り当て決定部２０１９は、タイムスロットの割り当てが全て完了したか判断する（ステップＳ２７）。具体的には、スロット情報格納部２００９に格納されているスロット本数が全て０になったか判断し、スロット本数が全て０になっている場合には、タイムスロットの割り当てが全て完了したものと判断する。タイムスロットの割り当てが全て完了した場合（ステップＳ２７：Ｙｅｓルート）、処理を終了する。

一方、タイムスロットの割り当てが全て完了していなければ（ステップＳ２７：Ｎｏルート）、端子Ｂを介してステップＳ５（図１４）に戻り、上で述べた処理を繰り返す。なお、端子Ｂを介して図１４の処理に戻った場合、評価値格納部２０１７に格納されているデータは、ステップＳ７においてクリアされる。すなわち、ある経路に対してタイムスロットの割り当てを行った場合、リンクの使用状態を更新し、最新の状態にて評価値を計算し直す。

なお、ステップＳ３５（図１６）で述べたように、スロットｉで既に使用済みのリンクがある場合には、隣接行列内の該当箇所の値を「１」から「０」に置き換える。例えば図１９に示したようなデータがリンク情報格納部２００５に格納され、変数ｉが０の場合には、ステップＳ３５において図２１に示すような隣接行列が生成される。なお、上で述べたように、図１９では、始点側ノード「０」及び終点側ノード「４」に係るリンクと、始点側ノード「４」及び終点側ノード「６」に係るリンクと、始点側ノード「６」及び終点側ノード「２」に係るリンクとに対応する値がそれぞれ「１」（すなわち、使用済み）になっている。そのため、図２１に示す隣接行列内の（０，４）成分、（４，６）成分、（６，２）成分の各々の値は「０」に設定されている。

以上のような処理を実施することにより、割り当て優先度と送信元ノードから宛先ノードまでに必要なホップ数と使用済みリンク数とを考慮した評価値に従ってタイムスロットの割り当てを行うことができる。例えば、送信元ノードから宛先ノードまでに必要なホップ数が大きいほど、評価値も大きくなるので、結果的に、ホップ数の小さい経路よりもホップ数の大きい経路が優先されることとなる。さらに、使用済みリンク数が大きいほど、評価値も大きくなるので、結果的に、使用済みリンク数の小さいタイムスロットよりも、使用済みリンク数の大きいタイムスロットを優先的に割り当てるようになる。これにより、より無駄のない割り当てを行うことができるようになり、パケット通信を行う経路が増えても、なるべく少ないタイムスロットによってパケット通信を実現することができる。

例えば図１０に示したスロット情報格納部２００９におけるスロット本数の合計は８本（＝２＋１＋１＋２＋２）である。ここで、例えば１つのタイムスロットにつき１経路を割り当てた場合には、図２２に示すように８つのタイムスロットが必要となる。なお、図２２において、スロット０及び１の各々には、ノード「０」からノード「２」へのパケット送信が割り当てられている。また、スロット２及び３の各々には、ノード「１」からノード「３」へのパケット送信が割り当てられている。さらに、スロット４及び５の各々には、ノード「２」からノード「１」へのパケット送信が割り当てられている。また、スロット６には、ノード「０」からノード「３」へのパケット送信が割り当てられている。さらに、スロット７には、ノード「１」からノード「２」へのパケット送信が割り当てられている。

一方で、本実施の形態に係る手法によれば、図２３に示すように３つのタイムスロットで済むようになる。図２３において、スロット０及び１の各々には、ノード「０」からノード「２」へのパケット送信と、ノード「１」からノード「３」へのパケット送信と、ノード「２」からノード「１」へのパケット送信とが割り当てられている。なお、ノード間のリンクは上り方向と下り方向とに分かれているため、ノード「０」からノード「２」へのパケット送信と、ノード「２」からノード「１」へのパケット送信とを同一のタイムスロットで行っても衝突は生じない。同様に、ノード「２」からノード「１」へのパケット送信と、ノード「１」からノード「３」へのパケット送信とを同一のタイムスロットで行っても衝突は生じない。また、図２３において、スロット２には、ノード「０」からノード「３」へのパケット送信と、ノード「１」からノード「２」へのパケット送信とが割り当てられている。このように、本実施の形態に係る手法によれば、少ないタイムスロットで済むようになる。

なお、上では簡単なネットワーク構成を例に説明したが、本実施の形態に係る手法によれば、他のネットワーク構成であっても、パケット通信が必要な経路を、少ないタイムスロットに割り当てることができる。例えばツリー型ネットワーク、ラダー型ネットワーク及びスター型ネットワークの各々において、本実施の形態に係る手法に従ってシミュレーションを行った場合のシミュレーション結果の一例を図２４に示す。なお、図２４は、図２５乃至図２７に示すような各ネットワークにおいて、ランダムに送信元ノード及び宛先ノードを選択し、計６４経路を割り当てた場合のシミュレーション結果を示す。

図２４では、シミュレーションを行ったネットワークの形状の列と、各ネットワークにおけるエッジルータ及び中継ルータの総数を示すノード総数の列と、各ネットワークにおけるエッジルータの総数を示すエッジ総数の列と、従来手法の列と、本手法の列とを示している。従来手法の列は、従来手法でタイムスロットの割り当てを行った場合のスロット数を示す。なお、従来手法とは、１タイムスロットにつき１経路を割り当てる方法である。従って、いずれのネットワーク構成においても６４スロットとなっている。また、本手法の列は、本実施の形態に係る手法に従ってシミュレーションを５回行った場合の平均スロット数を示す。

なお、図２５は、ツリー型ネットワークを示す。図２５に示すツリー型ネットワークは、１７台のエッジルータと、６２台の中継ルータとを有する。なお、図２５において、四角はエッジルータを表し、丸は中継ルータを表している（図２６及び図２７において同じ）。図２５では、ツリー部分が２つ存在し、個々のツリー部分は３１台の中継ルータで構成される。また、ツリー部分において根ノードに当たる中継ルータは１のエッジルータと接続されている。また、ツリー部分において葉ノードに当たる１６台の中継ルータは、各々異なる１のエッジルータと接続されている。図２５に示すようなツリー型ネットワークでは、本実施の形態に係る手法によれば、６４経路をおよそ１２．６スロットに割り当てることができる。

また、図２６は、ラダー型ネットワークを示す。図２６に示すラダー型ネットワークは、１６台のエッジルータと、１０台の中継ルータとを有する。図２６では、中継ルータは、２台×５台（縦×横）で配置され、縦方向で隣り合う中継ルータ同士が接続され、横方向で隣り合う中継ルータ同士も接続されている。また、四隅の中継ルータの各々は、４台のエッジルータと接続されている。図２６に示すようなラダー型ネットワークでは、本実施の形態に係る手法によれば、６４経路をおよそ１８．８スロットに割り当てることができる。なお、これは、図２６において、左側のエッジルータから右側のエッジルータまでの任意の３２経路と、右側のエッジルータから左側のエッジルータまでの任意の３２経路との計６４経路を割り当てた場合のシミュレーション結果である。

さらに、図２７に、スター型ネットワークの一例を示す。図２７に示すスター型ネットワークは、１６台のエッジルータと、２台の中継ルータを有する。図２７では、中継ルータ同士が接続されており、各中継ルータは、８台のエッジルータと接続されている。図２７に示すようなスター型ネットワークでは、本実施の形態に係る手法によれば、６４経路をおよそ３２スロットに割り当てることができる。

なお、これは、図２７において、左側のエッジルータから右側のエッジルータまでの任意の３２経路と、右側のエッジルータから左側のエッジルータまでの任意の３２経路との計６４経路を割り当てた場合のシミュレーション結果である。なお、図２７に示すスター型ネットワークでは、中継ルータ間のリンクが他の２つのネットワーク構成に比べて少ないため、スロット数も多く必要となっている。但し、従来手法に比べれば、半分のスロット数で済む。

以上本技術の一実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、上で説明した管理サーバ２００の機能ブロック図は必ずしも実際のプログラムモジュール構成に対応するものではない。

また、上で説明した帯域情報格納部２００１、優先度格納部２００３、リンク情報格納部２００５、スロット情報格納部２００９、最小ホップ数格納部２０１３、評価値格納部２０１７及び割り当て情報格納部２０２１に格納されるデータは一例であって、必ずしも上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。

なお、上で述べた管理サーバ２００は、コンピュータ装置であって、図３０に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。

例えば、ＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたスロット本数計算部２００７、最小ホップ数計算部２０１１、評価値算出部２０１５、割り当て決定部２０１９及びスロット割り当て処理部２０２３といった機能が実現される。また、上で述べた帯域情報格納部２００１のデータ、優先度格納部２００３のデータ、リンク情報格納部２００５のデータ、スロット情報格納部２００９のデータ、最小ホップ数格納部２０１３のデータ、評価値格納部２０１７のデータ及び割り当て情報格納部２０２１のデータは、メモリ２５０１又はＨＤＤ２５０５に格納される。

以上述べた本技術の実施の形態をまとめると以下のとおりになる。

第１の態様に係るタイムスロット割り当て方法は、ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部と、送信元ノード及び宛先ノードの組み合わせ毎に割り当て優先度を格納する優先度格納部と、ネットワークにおけるノード間のリンクの使用状態をタイムスロット毎に格納するリンク情報格納部と、割り当て情報格納部と、記憶装置とにアクセス可能なコンピュータにより実行される方法である。そして、本タイムスロット割り当て方法は、（Ａ）スロット情報格納部に格納されているスロット本数が１以上である、送信元ノード及び宛先ノードの組み合わせの各々について、ノード間のリンクのうちリンク情報格納部において未使用となっているリンクである未使用リンクによって送信元ノードから宛先ノードへの経路を形成し得るタイムスロットが存在するか判断する判断ステップ（図２８のステップＳ１０１）と、（Ｂ）上記判断ステップにおいて、未使用リンクによる経路を形成し得るタイムスロットが存在すると判断された組み合わせの各々について、未使用リンクによる経路を形成し得るタイムスロット毎に、未使用リンクによる経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、優先度格納部に格納され且つ当該組み合わせに対応する割り当て優先度と、リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、送信元ノードと宛先ノードと最短経路とタイムスロットの識別情報とに対応付けて記憶装置に格納する評価値算出ステップ（図２８のステップＳ１０３及びステップＳ１０５）と、（Ｃ）記憶装置に格納された評価値の中から最大評価値を特定し、記憶装置に格納され且つ当該最大評価値に対応する送信元ノード、宛先ノード、最短経路及びタイムスロットの識別情報を含むスロット割り当て情報を割り当て情報格納部に格納するステップ（図２８のステップＳ１０７及びステップＳ１０９）とを含む。

このようにすれば、割り当てが必要な経路毎且つ当該経路に割り当て可能なタイムスロット毎に、割り当て優先度、ホップ数及び使用済みリンク数を考慮した評価値を算出することになる。そして、このような評価値に従ってタイムスロットの割り当てを行うことによって、割り当てが必要な経路を、できるだけ少ないタイムスロットに割り当てることができるようになる。すなわち、効率的なタイムスロットの割り当てを行うことができるようになる。

また、スロット情報格納部において、最大評価値に対応する送信元ノード及び宛先ノードの組み合わせについてのスロット本数を１減ずるステップと、リンク情報格納部において、最大評価値に対応するタイムスロットにおけるリンクのうち、最大評価値に対応する最短経路に含まれるリンクを使用済みに設定するステップと、スロット情報格納部に格納されているスロット本数が全て０になるまで、又は、判断ステップにおいて、全ての組み合わせについて未使用リンクによる経路を形成し得るタイムスロットが存在しないと判断されるまで、上記判断ステップ以降のステップを実行させるステップとをさらに含むようにしてもよい。このようにすれば、例えばある経路に対してタイムスロットの割り当てが行われた場合には、当該タイムスロットにおけるリンクのうち、その経路に含まれるリンクを使用済みに設定し、再度評価値が計算されることになる。これにより、割り当てが必要な全ての経路について、適切な評価値に従ってタイムスロットの割り当てを行うことができる。

さらに、上記コンピュータが、送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に関する通信帯域の情報を格納する帯域情報格納部にさらにアクセス可能な場合もある。そして、上記判断ステップの前に、帯域情報格納部に格納されている帯域の最大公約数を算出し、各組み合わせについて、当該組み合わせに対応する帯域を最大公約数で除した値をスロット本数として算出し、当該組み合わせに対応付けてスロット情報格納部に設定するステップをさらに含むようにしてもよい。このようにすれば、帯域の最大公約数を基準にしてスロット本数を算出するので、より無駄のない割り当てを行うことができるようになる。

また、上記コンピュータが、送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードまでの最小ホップ数を格納する最小ホップ数格納部にさらにアクセス可能な場合もある。そして、上記評価値算出ステップにおいて、最短経路におけるホップ数と最小ホップ数格納部に格納され且つ組み合わせに対応する最小ホップ数との差が所定値以内であるか判断し、当該差が所定値以内の場合に、評価値を算出するようにしてもよい。これにより、例えば遠くを迂回するような経路（すなわち、データ遅延が生ずるような迂回経路）を割り当てることがなくなる。

さらに、上記評価値算出ステップにおいて、ノード間のリンクが全て未使用となっているタイムスロットが複数存在する場合、ノード間のリンクが全て未使用となっているタイムスロットのうちのいずれか１つについて評価値を算出するようにしてもよい。例えばノード間のリンクが全て未使用となっているタイムスロットが複数存在する場合、評価値はどれも同じ値になるため、いずれか１つについて算出すれば足りる。すなわち、処理負荷を削減することができる。

また、上記所定の評価関数が、割り当て優先度が高いほど評価値が大きくなるという性質と、最短経路におけるホップ数が大きいほど評価値が大きくなるという性質と、リンク情報格納部においてタイムスロットで使用済みとなっているリンクが多いほど評価値が大きくなるという性質とのうち少なくともいずれかの性質を有する関数である場合もある。例えば、最短経路におけるホップ数が大きいほど評価値が大きくなるという性質を有する評価関数であれば、より多くのホップ数を必要とする経路が優先されるので、より効率的な割り当てを行うことができるようになる。例えば、使用済みリンク数が大きいほど評価値が大きくなるような評価関数であれば、未割り当てのタイムスロットより、割り当て済みのタイムスロットが優先的に選ばれることとなり、１つのタイムスロットに、より無駄のない割り当てを行うことができるようになる。

第２の態様に係るタイムスロット割り当て装置（すなわち、実施例における管理サーバ２００）は、（Ａ）ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部（図２９の「スロット情報格納部」）と、（Ｂ）送信元ノード及び宛先ノードの組み合わせ毎に割り当て優先度を格納する優先度格納部（図２９の「優先度格納部」）と、（Ｃ）ネットワークにおけるノード間のリンクの使用状態をタイムスロット毎に格納するリンク情報格納部（図２９の「リンク情報格納部」）と、（Ｄ）スロット情報格納部に格納されているスロット本数が１以上である、送信元ノード及び宛先ノードの組み合わせの各々について、ノード間のリンクのうちリンク情報格納部において未使用となっているリンクである未使用リンクによって送信元ノードから宛先ノードへの経路を形成し得るタイムスロットが存在するか判断する判断手段（図２９の「判断部」）と、（Ｅ）上記判断手段により、未使用リンクによる経路を形成し得るタイムスロットが存在すると判断された組み合わせの各々について、未使用リンクによる経路を形成し得るタイムスロット毎に、未使用リンクによる経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、優先度格納部に格納され且つ当該組み合わせに対応する割り当て優先度と、リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、送信元ノードと宛先ノードと最短経路とタイムスロットの識別情報とに対応付けて記憶装置に格納する評価値算出手段（図２９の「評価値算出部」）と、（Ｆ）記憶装置に格納された評価値の中から最大評価値を特定し、記憶装置に格納され且つ当該最大評価値に対応する送信元ノード、宛先ノード、最短経路及びタイムスロットの識別情報を含むスロット割り当て情報を割り当て情報格納部（図２９の「割り当て情報格納部」）に格納する割り当て決定手段（図２９の「割り当て決定部」）とを有する。

なお、上で述べたような処理を管理サーバ２００に実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。また、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。

以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。

（付記１）
ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部と、前記送信元ノード及び前記宛先ノードの前記組み合わせ毎に割り当て優先度を格納する優先度格納部と、前記ネットワークにおけるノード間のリンクの使用状態を前記タイムスロット毎に格納するリンク情報格納部と、割り当て情報格納部と、記憶装置とにアクセス可能なコンピュータにより実行されるタイムスロット割り当て方法であって、
前記スロット情報格納部に格納されている前記スロット本数が１以上である、前記送信元ノード及び前記宛先ノードの前記組み合わせの各々について、前記ノード間のリンクのうち前記リンク情報格納部において未使用となっているリンクである未使用リンクによって前記送信元ノードから前記宛先ノードへの経路を形成し得る前記タイムスロットが存在するか判断する判断ステップと、
前記判断ステップにおいて、前記未使用リンクによる前記経路を形成し得る前記タイムスロットが存在すると判断された前記組み合わせの各々について、前記未使用リンクによる前記経路を形成し得る前記タイムスロット毎に、前記未使用リンクによる前記経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、前記優先度格納部に格納され且つ当該組み合わせに対応する前記割り当て優先度と、前記リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、前記送信元ノードと前記宛先ノードと前記最短経路と前記タイムスロットの識別情報とに対応付けて前記記憶装置に格納する評価値算出ステップと、
前記記憶装置に格納された前記評価値の中から最大評価値を特定し、前記記憶装置に格納され且つ当該最大評価値に対応する前記送信元ノード、前記宛先ノード、前記最短経路及び前記タイムスロットの識別情報を含むスロット割り当て情報を前記割り当て情報格納部に格納するステップと、
を含み、コンピュータにより実行されるタイムスロット割り当て方法。

（付記２）
前記スロット情報格納部において、前記最大評価値に対応する前記送信元ノード及び前記宛先ノードの前記組み合わせについての前記スロット本数を１減ずるステップと、
前記リンク情報格納部において、前記最大評価値に対応する前記タイムスロットにおけるリンクのうち、前記最大評価値に対応する前記最短経路に含まれるリンクを使用済みに設定するステップと、
前記スロット情報格納部に格納されている前記スロット本数が全て０になるまで、又は、前記判断ステップにおいて、全ての前記組み合わせについて前記未使用リンクによる前記経路を形成し得る前記タイムスロットが存在しないと判断されるまで、前記判断ステップ以降のステップを実行させるステップと、
をさらに含む、付記１記載のタイムスロット割り当て方法。

（付記３）
前記コンピュータが、前記送信元ノード及び前記宛先ノードの前記組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に関する通信帯域の情報を格納する帯域情報格納部にさらにアクセス可能となっており、
前記判断ステップの前に、前記帯域情報格納部に格納されている前記帯域の最大公約数を算出し、各前記組み合わせについて、当該組み合わせに対応する前記帯域を前記最大公約数で除した値を前記スロット本数として算出し、当該組み合わせに対応付けて前記スロット情報格納部に設定するステップ
をさらに含む、付記１又は２記載のタイムスロット割り当て方法。

（付記４）
前記コンピュータが、前記送信元ノード及び前記宛先ノードの前記組み合わせ毎に当該送信元ノードから当該宛先ノードまでの最小ホップ数を格納する最小ホップ数格納部にさらにアクセス可能となっており、
前記評価値算出ステップにおいて、前記最短経路におけるホップ数と前記最小ホップ数格納部に格納され且つ前記組み合わせに対応する前記最小ホップ数との差が所定値以内であるか判断し、当該差が所定値以内の場合に、前記評価値を算出する
付記１乃至３のいずれか１つ記載のタイムスロット割り当て方法。

（付記５）
前記評価値算出ステップにおいて、前記ノード間のリンクが全て未使用となっている前記タイムスロットが複数存在する場合、前記ノード間のリンクが全て未使用となっている前記タイムスロットのうちのいずれか１つについて前記評価値を算出する
付記１乃至４のいずれか１つ記載のタイムスロット割り当て方法。

（付記６）
前記所定の評価関数が、前記割り当て優先度が高いほど前記評価値が大きくなるという性質と、前記最短経路におけるホップ数が大きいほど前記評価値が大きくなるという性質と、前記リンク情報格納部において前記タイムスロットで使用済みとなっているリンクが多いほど前記評価値が大きくなるという性質とのうち少なくともいずれかの性質を有する関数である
付記１乃至５のいずれか１つ記載のタイムスロット割り当て方法。

（付記７）
ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部に格納されている前記スロット本数が１以上である、前記送信元ノード及び前記宛先ノードの前記組み合わせの各々について、前記ネットワークにおけるノード間のリンクの使用状態を前記タイムスロット毎に格納するリンク情報格納部において未使用となっているリンクである未使用リンクによって前記送信元ノードから前記宛先ノードへの経路を形成し得る前記タイムスロットが存在するか判断する判断ステップと、
前記判断ステップにおいて、前記未使用リンクによる前記経路を形成し得る前記タイムスロットが存在すると判断された前記組み合わせの各々について、前記未使用リンクによる前記経路を形成し得る前記タイムスロット毎に、前記未使用リンクによる前記経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、前記送信元ノード及び前記宛先ノードの組み合わせ毎に割り当て優先度を格納する優先度格納部に格納され且つ当該組み合わせに対応する前記割り当て優先度と、前記リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、前記送信元ノードと前記宛先ノードと前記最短経路と前記タイムスロットの識別情報とに対応付けて前記記憶装置に格納する評価値算出ステップと、
前記記憶装置に格納された前記評価値の中から最大評価値を特定し、前記記憶装置に格納され且つ当該最大評価値に対応する前記送信元ノード、前記宛先ノード、前記最短経路及び前記タイムスロットの識別情報を含むスロット割り当て情報を前記割り当て情報格納部に格納するステップと、
をコンピュータに実行させるためのタイムスロット割り当てプログラム。

（付記８）
ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部と、
前記送信元ノード及び前記宛先ノードの前記組み合わせ毎に割り当て優先度を格納する優先度格納部と、
前記ネットワークにおけるノード間のリンクの使用状態を前記タイムスロット毎に格納するリンク情報格納部と、
前記スロット情報格納部に格納されている前記スロット本数が１以上である、前記送信元ノード及び前記宛先ノードの前記組み合わせの各々について、前記ノード間のリンクのうち前記リンク情報格納部において未使用となっているリンクである未使用リンクによって前記送信元ノードから前記宛先ノードへの経路を形成し得る前記タイムスロットが存在するか判断する判断手段と、
前記判断手段により、前記未使用リンクによる前記経路を形成し得る前記タイムスロットが存在すると判断された前記組み合わせの各々について、前記未使用リンクによる前記経路を形成し得る前記タイムスロット毎に、前記未使用リンクによる前記経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、前記優先度格納部に格納され且つ当該組み合わせに対応する前記割り当て優先度と、前記リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、前記送信元ノードと前記宛先ノードと前記最短経路と前記タイムスロットの識別情報とに対応付けて記憶装置に格納する評価値算出手段と、
前記記憶装置に格納された前記評価値の中から最大評価値を特定し、前記記憶装置に格納され且つ当該最大評価値に対応する前記送信元ノード、前記宛先ノード、前記最短経路及び前記タイムスロットの識別情報を含むスロット割り当て情報を割り当て情報格納部に格納する割り当て決定手段と、
を有するタイムスロット割り当て装置。

１００，１０１，１０２，１０３ エッジルータ
１０４，１０５，１０６，１０７ 中継ルータ
２００ 管理サーバ
２００１ 帯域情報格納部 ２００３ 優先度格納部
２００５ リンク情報格納部 ２００７ スロット本数計算部
２００９ スロット情報格納部 ２０１１ 最小ホップ数計算部
２０１３ 最小ホップ数格納部 ２０１５ 評価値算出部
２０１７ 評価値格納部 ２０１９ 割り当て決定部
２０２１ 割り当て情報格納部 ２０２３ スロット割り当て処理部

Claims (6)

1. ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部と、前記送信元ノード及び前記宛先ノードの前記組み合わせ毎に割り当て優先度を格納する優先度格納部と、前記ネットワークにおけるノード間のリンクの使用状態を前記タイムスロット毎に格納するリンク情報格納部と、割り当て情報格納部と、記憶装置とにアクセス可能なコンピュータにより実行されるタイムスロット割り当て方法であって、
   前記スロット情報格納部に格納されている前記スロット本数が１以上である、前記送信元ノード及び前記宛先ノードの前記組み合わせの各々について、前記ノード間のリンクのうち前記リンク情報格納部において未使用となっているリンクである未使用リンクによって前記送信元ノードから前記宛先ノードへの経路を形成し得る前記タイムスロットが存在するか判断する判断ステップと、
   前記判断ステップにおいて、前記未使用リンクによる前記経路を形成し得る前記タイムスロットが存在すると判断された前記組み合わせの各々について、前記未使用リンクによる前記経路を形成し得る前記タイムスロット毎に、前記未使用リンクによる前記経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、前記優先度格納部に格納され且つ当該組み合わせに対応する前記割り当て優先度と、前記リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、前記送信元ノードと前記宛先ノードと前記最短経路と前記タイムスロットの識別情報とに対応付けて前記記憶装置に格納する評価値算出ステップと、
   前記記憶装置に格納された前記評価値の中から最大評価値を特定し、前記記憶装置に格納され且つ当該最大評価値に対応する前記送信元ノード、前記宛先ノード、前記最短経路及び前記タイムスロットの識別情報を含むスロット割り当て情報を前記割り当て情報格納部に格納するステップと、
   を含み、コンピュータにより実行されるタイムスロット割り当て方法。
2. 前記スロット情報格納部において、前記最大評価値に対応する前記送信元ノード及び前記宛先ノードの前記組み合わせについての前記スロット本数を１減ずるステップと、
   前記リンク情報格納部において、前記最大評価値に対応する前記タイムスロットにおけるリンクのうち、前記最大評価値に対応する前記最短経路に含まれるリンクを使用済みに設定するステップと、
   前記スロット情報格納部に格納されている前記スロット本数が全て０になるまで、又は、前記判断ステップにおいて、全ての前記組み合わせについて前記未使用リンクによる前記経路を形成し得る前記タイムスロットが存在しないと判断されるまで、前記判断ステップ以降のステップを実行させるステップと、
   をさらに含む、請求項１記載のタイムスロット割り当て方法。
3. 前記コンピュータが、前記送信元ノード及び前記宛先ノードの前記組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に関する通信帯域の情報を格納する帯域情報格納部にさらにアクセス可能となっており、
   前記判断ステップの前に、前記帯域情報格納部に格納されている前記帯域の最大公約数を算出し、各前記組み合わせについて、当該組み合わせに対応する前記帯域を前記最大公約数で除した値を前記スロット本数として算出し、当該組み合わせに対応付けて前記スロット情報格納部に設定するステップ
   をさらに含む、請求項１又は２記載のタイムスロット割り当て方法。
4. 前記コンピュータが、前記送信元ノード及び前記宛先ノードの前記組み合わせ毎に当該送信元ノードから当該宛先ノードまでの最小ホップ数を格納する最小ホップ数格納部にさらにアクセス可能となっており、
   前記評価値算出ステップにおいて、前記最短経路におけるホップ数と前記最小ホップ数格納部に格納され且つ前記組み合わせに対応する前記最小ホップ数との差が所定値以内であるか判断し、当該差が所定値以内の場合に、前記評価値を算出する
   請求項１乃至３のいずれか１つ記載のタイムスロット割り当て方法。
5. ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部に格納されている前記スロット本数が１以上である、前記送信元ノード及び前記宛先ノードの前記組み合わせの各々について、前記ネットワークにおけるノード間のリンクの使用状態を前記タイムスロット毎に格納するリンク情報格納部において未使用となっているリンクである未使用リンクによって前記送信元ノードから前記宛先ノードへの経路を形成し得る前記タイムスロットが存在するか判断する判断ステップと、
   前記判断ステップにおいて、前記未使用リンクによる前記経路を形成し得る前記タイムスロットが存在すると判断された前記組み合わせの各々について、前記未使用リンクによる前記経路を形成し得る前記タイムスロット毎に、前記未使用リンクによる前記経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、前記送信元ノード及び前記宛先ノードの組み合わせ毎に割り当て優先度を格納する優先度格納部に格納され且つ当該組み合わせに対応する前記割り当て優先度と、前記リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、前記送信元ノードと前記宛先ノードと前記最短経路と前記タイムスロットの識別情報とに対応付けて記憶装置に格納する評価値算出ステップと、
   前記記憶装置に格納された前記評価値の中から最大評価値を特定し、前記記憶装置に格納され且つ当該最大評価値に対応する前記送信元ノード、前記宛先ノード、前記最短経路及び前記タイムスロットの識別情報を含むスロット割り当て情報を割り当て情報格納部に格納するステップと、
   をコンピュータに実行させるためのタイムスロット割り当てプログラム。
6. ネットワークにおける送信元ノード及び宛先ノードの組み合わせ毎に当該送信元ノードから当該宛先ノードへのパケット送信に対して割り当てが必要となるタイムスロットのスロット本数を格納するスロット情報格納部と、
   前記送信元ノード及び前記宛先ノードの前記組み合わせ毎に割り当て優先度を格納する優先度格納部と、
   前記ネットワークにおけるノード間のリンクの使用状態を前記タイムスロット毎に格納するリンク情報格納部と、
   前記スロット情報格納部に格納されている前記スロット本数が１以上である、前記送信元ノード及び前記宛先ノードの前記組み合わせの各々について、前記ノード間のリンクのうち前記リンク情報格納部において未使用となっているリンクである未使用リンクによって前記送信元ノードから前記宛先ノードへの経路を形成し得る前記タイムスロットが存在するか判断する判断手段と、
   前記判断手段により、前記未使用リンクによる前記経路を形成し得る前記タイムスロットが存在すると判断された前記組み合わせの各々について、前記未使用リンクによる前記経路を形成し得る前記タイムスロット毎に、前記未使用リンクによる前記経路の中から最短経路を特定し、特定された最短経路におけるホップ数と、前記優先度格納部に格納され且つ当該組み合わせに対応する前記割り当て優先度と、前記リンク情報格納部において当該タイムスロットで使用済みとなっているリンクの数とを所定の評価関数に適用することにより評価値を算出し、前記送信元ノードと前記宛先ノードと前記最短経路と前記タイムスロットの識別情報とに対応付けて記憶装置に格納する評価値算出手段と、
   前記記憶装置に格納された前記評価値の中から最大評価値を特定し、前記記憶装置に格納され且つ当該最大評価値に対応する前記送信元ノード、前記宛先ノード、前記最短経路及び前記タイムスロットの識別情報を含むスロット割り当て情報を割り当て情報格納部に格納する割り当て決定手段と、
   を有するタイムスロット割り当て装置。

Images