(57)【要約】【課題】リンク帯域を効率的に利用するタイムスロット割り当てを行う。【解決手段】リング１周の伝搬遅延時間Ｄ、回線容量の分割数Ｍ、各パスへの帯域要求行列Ｔ、周期倍数Ｐを入力する。フレーム周期Ｆ＝Ｍ×Ｄ×Ｐとし、ＦとＤに基づき、周回数がＭ×ＰとなっているＤ本のタイムスロットサイクルを導出する。要求帯域行列Ｔの要素をＰ倍にしたパスに、タイムスロットサイクルのタイムスロットを割り当てる。【選択図】図１
2016010073.tif 000002
【特許請求の範囲】
【請求項１】
光アドドロップスイッチを備えた複数のノードを、光ファイバで成る複数のリンクにより結んでおり、複数の前記リンクでのフレームの開始タイミングが同期していると共に、リング１周の伝搬遅延時間Ｄがタイムスロットの整数倍になっている光ＴＤＭリング網において、任意のノード間で伝送されるパスに必要な要求タイムスロット数に対して、必要数のタイムスロットを周期的に割り当てる光ＴＤＭリング網のタイムスロット割り当て方法であって、
前記伝搬遅延時間Ｄと、タイムスロットをパスに割り当てるときに前記リンクの回線容量を分割する分割数Ｍと、前記要求タイムスロット数を要素とする要求帯域行列Ｔを入力する工程と、
周期倍数Ｐとして任意の自然数を入力する工程と、
フレーム周期Ｆを、Ｆ＝Ｍ×Ｄ×Ｐの演算をすることにより求める工程と、
求めた前記フレーム周期Ｆと前記伝搬遅延時間Ｄを基に、ＦとＤの最大公約数であるタイムスロットサイクルの本数Ｋ＝Ｄと、ＦをＫで割ったタイムスロットサイクルの周回数ｋ＝Ｍ×Ｐを求める工程と、
前記要求帯域行列Ｔの要求タイムスロット数をＰ倍した数のパス数のトラヒックを求め、前記トラヒックのパスに対して、周回数ｋ＝Ｍ×ＰとなっているＫ＝Ｄ本の前記タイムスロットサイクルのタイムスロットを割り当てる工程と、
を有することを特徴とする光ＴＤＭリング網のタイムスロット割り当て方法。
【請求項２】
請求項１において、
前記トラヒックのパスに対して、周回数ｋ＝Ｍ×ＰとなっているＫ＝Ｄ本の前記タイムスロットサイクルのタイムスロットを割り当てる前記工程は、
未割り当てパスの中から任意のパスを一つ選び、このパスをノードＮｉからノードＮｊへのパス（ｉ，ｊ）とする第１の手順と、
未割り当てのタイムスロットサイクルを一つ選び、これを割り当て中のタイムスロットサイクルｙとし、タイムスロットサイクルｙ上でパス（ｉ，ｊ）に対するタイムスロットを割り当て、この割り当て後にノードＮｉからノードＮｊへの要求タイムスロット数Ｔijを１減じ、未割り当てのタイムスロットサイクルがなければ手順を終了する第２の手順と、
未割り当てパスの中から、できるだけノードＮｊに近いノードから始まるパスを一つ選び、選んだパスを新たにパス（ｉ，ｊ）とし、未割り当てパスが見つからなければ手順を終了する第３の手順と、
割り当て中のタイムスロットサイクルｙにおいて、直前に割り当てたタイムスロットの次のタイムスロットから順にたどり、空きタイムスロットが見つかれば、この空きタイムスロットに前記第３の手順で見つかった新たなパス（ｉ，ｊ）を割り当て、この割り当て後に前記要求タイムスロット数Ｔijを１減じ、その後に前記第３の手順に進み、空きタイムスロットが見つからなければ前記第２の手順に進む第４の手順と、
を有することを特徴とする光ＴＤＭリング網のタイムスロット割り当て方法。
【請求項３】
光アドドロップスイッチを備えた複数のノードを、光ファイバで成る複数のリンクにより結んでおり、複数の前記リンクでのフレームの開始タイミングが同期していると共に、リング１周の伝搬遅延時間Ｄがタイムスロットの整数倍になっている光ＴＤＭリング網において、任意のノード間で伝送されるパスに必要な要求タイムスロット数に対して、必要数のタイムスロットを周期的に割り当てる光ＴＤＭリング網のタイムスロット割り当て方法であって、
前記伝搬遅延時間Ｄと、タイムスロットをパスに割り当てるときに前記リンクの回線容量を分割する分割数Ｍと、前記要求タイムスロット数を要素とする要求帯域行列Ｔを入力する工程と、
周期倍数Ｐとして任意の自然数を入力する工程と、
フレーム周期Ｆを、Ｆ＝Ｍ×Ｄ×Ｐ＋１の演算をすることにより求める工程と、
求めた前記フレーム周期Ｆと前記伝搬遅延時間Ｄを基に、ＦとＤの最大公約数であるタイムスロットサイクルの本数Ｋ＝１と、ＦをＫで割ったタイムスロットサイクルの周回数ｋ＝Ｍ×Ｄ×Ｐ＋１を求める工程と、
前記要求帯域行列Ｔの要求タイムスロット数をＰ×Ｄ倍した数のパス数のトラヒックを求め、前記トラヒックのパスに対して、周回数ｋ＝Ｍ×Ｄ×Ｐ＋１となっているＫ＝１本の前記タイムスロットサイクルのタイムスロットを割り当てる工程と、
を有することを特徴とする光ＴＤＭリング網のタイムスロット割り当て方法。
【請求項４】
請求項３において、
前記トラヒックのパスに対して、周回数ｋ＝Ｍ×Ｄ×Ｐ＋１となっているＫ＝１本の前記タイムスロットサイクルのタイムスロットを割り当てる前記工程は、
未割り当てパスの中から任意のパスを一つ選び、このパスをノードＮｉからノードＮｊへのパス（ｉ，ｊ）とする第１の手順と、
１本の前記タイムスロットサイクルを割り当て中のタイムスロットサイクルｙとし、タイムスロットサイクルｙ上でパス（ｉ，ｊ）に対するタイムスロットを割り当て、この割り当て後にノードＮｉからノードＮｊへの要求タイムスロット数Ｔijを１減じる第２の手順と、
未割り当てパスの中から、できるだけノードＮｊに近いノードから始まるパスを一つ選び、選んだパスを新たにパス（ｉ，ｊ）とし、未割り当てパスが見つからなければ手順を終了する第３の手順と、
割り当て中のタイムスロットサイクルｙにおいて、直前に割り当てたタイムスロットの次のタイムスロットから順にたどり、空きタイムスロットが見つかれば、この空きタイムスロットに前記第３の手順で見つかった新たなパス（ｉ，ｊ）を割り当て、この割り当て後に前記要求タイムスロット数Ｔijを１減じ、その後に前記第３の手順に進む第４の手順と、
を有することを特徴とする光ＴＤＭリング網のタイムスロット割り当て方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、省電力の全光網の実現に向け、光スイッチの同期制御によりタイムスロットを周期的に割り当てることにより任意帯域のパスの伝送を柔軟に実現する光ＴＤＭ（Time Division Multiplexing：時分割多重化）リング網に関するものであり、任意の条件の光ＴＤＭリング網において、光ファイバの帯域を１００％近く効率的に利用するためのタイムスロットの割り当て方法を明らかにするものである。
【背景技術】
【０００２】
片方向光ＴＤＭリング網は、複数のノードを、光信号を送る方向が一方向に決まっている光ファイバ（以下では説明上、リンクとも呼ぶ）で結んだものである。各ノードは、内部に光スイッチ（光アドドロップスイッチ）を備えており、光ファイバ上の情報を次ノードへ転送したり、光ファイバへの情報アド（add）をしたり、光ファイバからの情報ドロップ（drop）をしたりする動作を、周期的に行うものである。
光信号を正方向に送る片方向光ＴＤＭリング網と光信号を逆方向に送る片方向光ＴＤＭ
リング網を組み合わせると、光信号を双方向に送ることができる双方向の光ＴＤＭリング網を実現できる。このため、片方向光ＴＤＭリング網を実現する技術は、一般的な光ＴＤＭリング網の基本的技術となっている。
【０００３】
図３は、４つのノードを光ファイバｆで接続した片方向光ＴＤＭリング網の例を示している。各ノードはＮ０からＮ３までの番号づけがされている。またノードＮ０からノードＮ１、ノードＮ１からノードＮ２、ノードＮ２からノードＮ３、ノードＮ３からノードＮ０、に向かう片方向の通信で利用される光ファイバｆを、それぞれ、リンクＬ０−１、リンクＬ１−２、リンクＬ２−３、リンクＬ３−０と呼ぶ。
また、リンクＬ３−０には、リングの１周の伝搬遅延時間がタイムスロットの整数倍となるように調整するための遅延調整用光ファイバｆｄが挿入されている。図３の例では、リング１周の伝搬遅延時間は２タイムスロットに調整されているものとする。
【０００４】
また、図４は、各ノードでの光スイッチ（光アドドロップスイッチ）ＳＷの動作例を示している。図４（ａ）は、前ノードから到着した情報αを次ノードに転送する動作を示している。図４（ｂ）は、前ノードから到着した情報βを、当該ノードでドロップ（抜出）し、同時に、当該ノードから次ノードに向けて情報γをアド（追加）する動作を示している。
【０００５】
それぞれの情報転送は、タイムスロットと呼ばれる固定長の時間を単位として行われる。各リンク上ではタイムスロットを単位とした情報転送が行われる。このため、各ノード間の通信に対して、このタイムスロットを周期的に必要数だけ割り当てることにより、ノード間に必要とされる通信帯域を実現する。
具体的には、リンクの回線容量をＣ（ｂｐｓ）とし、パス割り当ての単位速度をｖ（ｂｐｓ）とするとき、Ｍ＝（Ｃ／ｖ）個のタイムスロットを、周期的割り当ての単位として考える。ここでＭは整数とし、周期的タイムスロット割り当ての単位となるＭ個のタイムスロットを、フレームと呼ぶこととする。逆に言えば、１つのフレームは、Ｍ個のタイムスロットを有している。
【０００６】
一つのノード間の通信に、１フレーム周期中のすべてのタイムスロットを割り当てると、全回線容量Ｃを割り当てたことに相当する。また、一つのノード間の通信に、１フレーム周期中の１つのタイムスロットのみを割り当てると、回線容量Ｃの１／Ｍの帯域を割り当てることになる。
例えば、リンク上で１０Ｇｂｐｓの伝送を行うリング網において、各パスに１Ｇｂｐｓを単位とした帯域割り当てを行う場合、Ｍ＝１０／１＝１０である。フレーム周期の値は、リング内のすべてのノードで共通の値を利用する。
【０００７】
また、各ノードは高精度で相互に同期しているタイマーを備えており、かつ、各ノードのタイマーには、ノードＮ０からの信号伝搬遅延に相当するオフセットが加えられているものとする。これにより、ノードＮ０のフレームの先頭タイムスロットで送信した光信号が各ノードを通過する時刻に合わせて、各ノードのフレームの先頭がちょうどスタートするような動作を行うことができる。
【０００８】
図３では、Ｍ＝４としたときの各リンク上での周期的タイムスロットの割り当ての具体例も併せて示している。各リンク上のタイムスロットには、フレーム内の位置として♯０から♯３の番号が繰り返し付けられている。それぞれのタイムスロット内には、そのタイムスロットを利用するように割り当てられたパスが記載されている。空白のタイムスロットは、まだどのパスも割り当てられていない。
ここで、周期的なタイムスロット割り当てを行っているため、各リンク上の同じ番号のタイムスロットには同じ通信が割り当てられている。
【０００９】
具体例として、ノードＮ０からノードＮ３へのパス（図３中では、このパスを「０→３」により示している）を割り当てる場合を考えると、このパスはリンクＬ０−１、リンクＬ１−２、リンクＬ２−３を経由する必要がある。そこで、図３の例では、これらのリンクＬ０−１，Ｌ１−２，Ｌ２−３のタイムスロット♯０とタイムスロット♯２を、ノードＮ０からノードＮ３へのパスに割り当てている。
【００１０】
同様にノードＮ３からノードＮ２への通信については、リンクＬ３−０のタイムスロット♯３及びリンクＬ０−１、リンクＬ１−２のタイムスロット♯１が割り当てられている。
ここで、リンクＬ３−０とリンクＬ０−１でタイムスロットの番号が変わっているのは、リング１周の伝搬遅延時間が２タイムスロット分であるため、リンクＬ３−０上のタイムスロットは、リンクＬ０−１上では、タイムスロット番号が２つ大きいタイムスロットに転送されるためである。
ただし、タイムスロット番号はフレームを周期としているため、♯３のタイムスロットから２タイムスロット分シフトさせたタイムスロット番号は、（３＋２）÷４の除算演算により求められる剰余である♯１に移ることになる。
【００１１】
同様に、ノードＮ２からノードＮ１に向けた通信には、リンクＬ２−３、リンクＬ３−０のタイムスロット♯１及びリンクＬ０−１のタイムスロット♯３が割り当てられる。
【００１２】
このように、任意のノード間の通信要求が与えられたときに、他の通信との衝突がないように考慮しながら、フレーム周期内のタイムスロットをできるだけ効率的に割り当てることは、片方向光ＴＤＭリング網の運用における重要課題である。
後述するように、本発明は、このようなタイムスロット割り当てにおいて、非常に効率のよいタイムスロット割り当てを行う方法である。
【００１３】
先行技術文献である非特許文献１には次のことが示されている。即ち、リング１周の伝搬遅延時間がＤとなっている片方向光ＴＤＭリングにおいて、フレーム周期Ｆ＝Ｍ（但しＭ≧Ｄとする）のタイムスロット割り当てを行う場合には、下記（ａ）と（ｂ）が等価であることが示されている。
（ａ）ノード間の任意の通信にタイムスロットの割り当てを行うこと。
（ｂ）リング１周分の長さに対してＭ／Ｋ周分の長さを持つ、Ｋ本の、「タイムスロットサイクル」と呼ばれる、タイムスロットが連続した領域において、タイムスロットの割り当てを行うこと。
ここで、ＫはＤとＭの最大公約数である。なお前述したように、Ｍは整数であり、伝搬遅延時間Ｄはタイムスロットの数により規定している。このタイムスロットサイクルは、周期的なタイムスロット割り当てを行うことから生じる論理的構成である。
【００１４】
また、先行技術文献である非特許文献２は、非特許文献１に示されている考えを、双方向光ＴＤＭリング網に拡張したものを示している。
なお、非特許文献１及び非特許文献２の文献名等は、後に記している。
【００１５】
以下では、非特許文献１に示されたタイムスロット割り当て方法の概要を示す。
図５（ａ）〜図５（ｃ）は、図３に示した各リンクのタイムスロットを縦にそろえて並べた上で、情報を送信した各タイムスロットと、送信された情報が次に通過するタイムスロットとを矢印で結んだものである。
【００１６】
図５（ａ）は、リング１周の伝搬遅延時間Ｄが２タイムスロットであるときの状態を、図５（ｂ）は、リング１周の伝搬遅延時間Ｄが３タイムスロットであるときの状態を、図５（ｃ）は、リング１周の伝搬遅延時間Ｄが４タイムスロットであるときの状態を示している。
【００１７】
まず図５（ａ）の状態を説明する。
前述のように各リンクにおけるフレームの開始タイミングが同期しているため、リンクＬ０−１からリンクＬ１−２、リンクＬ２−３、リンクＬ３−０までは、各タイムスロットの情報は、次のリンク上の同番号のタイムスロットを通過する。
【００１８】
しかし、リング１周の伝搬遅延時間Ｄが２タイムスロット分であるため、リンクＬ３−０のタイムスロット♯ｉ（ｉ＝０、１、２、３）で送信した情報は、リンクＬ０−１のタイムスロット♯（(ｉ＋２)mod ４）を通過することになる。具体的にはタイムスロット♯０は♯２にずれ、♯１は♯３にずれ、♯２は♯０にずれ、♯３は♯１にずれていくことになる。
この結果、図５（ａ）を見ると、タイムスロット♯０の列と♯２の列が相互につながって形成されたタイムスロットサイクルと、タイムスロット♯１の列とタイムスロット♯３の列が相互につながって形成されたタイムスロットサイクルという、２つのタイムスロットサイクルができていることが分る。
【００１９】
なお「mod」とは、「除数」を意味するものである。従って、（(ｉ＋２)mod ４）は、（ｉ＋２）÷４の除算演算により求められる「余り」＝「剰余」を意味するものである。
【００２０】
別の例として、リング１周の伝搬遅延時間Ｄ＝３タイムスロットであった場合を考えると、リンクＬ３−０上のタイムスロットは、リンクＬ０−１上の３タイムスロット分シフトしたタイムスロットにつながるため、同様のタイムスロットの連続関係を図にすると図５（ｂ）のようになる。
この場合、タイムスロット♯０の列はタイムスロット♯３の列につながり、その後、タイムスロット♯２、タイムスロット♯１を経てタイムスロット♯０に戻ることになり、一つの連続したタイムスロットサイクルになっていることが分る。
【００２１】
さらに別の例として、リング１周の伝搬遅延時間Ｄ＝４タイムスロットであった場合を考えると、各リンクＬ３−０上のタイムスロットは、リンクＬ０−１上の４タイムスロット分シフトしたタイムスロットにつながるため、同じタイムスロットに戻ってくることとなり、図５（ｃ）のようになり、４つの独立したタイムスロットサイクルになる。
【００２２】
一般的に、周期的なタイムスロット割り当てを行う光ＴＤＭリングでは、ノードＮ０のタイムスロット♯ｉ（ｉ＝０、１、・・・Ｍ−１）から送り出された情報をどのノードにおいてもドロップせずに転送を続けたとき、次の周ではノードＮ０のタイムスロット♯（（ｉ＋Ｄ）mod Ｍ）を通過する。さらに、ｋ周後（ｋ≧１）にはノードＮ０のタイムスロット♯（（ｉ＋ｋ・Ｄ）mod Ｍ）を通過する。
【００２３】
そこで、この情報が元のタイムスロット♯ｉに初めて戻ってくるときの条件を考えると（（ｉ＋ｋ・Ｄ）mod Ｍ）＝ｉより、（ｋ・Ｄ mod Ｍ）＝０となる。これは、ｋ・Ｄが、ＤとＭの最小公倍数になることを意味している。そこで、ＫをＤとＭの最大公約数とすると、ｋ＝Ｍ／Ｋのときに上述の条件が成り立つことが分かる。
【００２４】
従って、図５に示したようなタイムスロットサイクルの周回数ｋは（Ｍ／Ｋ）である。このとき、タイムスロットサイクルの本数はＫ本となることが知られている。
実際、図５（ａ），（ｂ），（ｃ）のそれぞれの場合、ＭとＤの最大公約数がそれぞれ、Ｋ＝２、１、４となり、タイムスロットサイクルの数がＫとなっており、タイムスロットサイクルの周回数ｋがそれぞれ４／２、４／１、４／４となっていることが確認できる。
【００２５】
この状態を表に示すと次のようになる。
【表１】
2016010073.tif 000003
【００２６】
非特許文献１では、このような周期的タイムスロット割り当てに伴う論理的なタイムスロットサイクルの構造を理解した上で、任意のノード間を伝送するパスへの帯域要求が与えられた時のタイムスロット割り当ての方法が示されている。図６に、従来のタイムスロット割り当ての手順を示す。
【００２７】
まず、リング網のリング１周の伝搬遅延時間Ｄ（タイムスロットの数により規定した時間）、タイムスロットをパスに割り当てるときにリンクの回線容量を分割する分割数Ｍ、
および各ノードＮｉからノードＮｊへのパスに対する帯域タイムスロット数（要求タイムスロット数）Ｔijを要素とする要求帯域行列Ｔを入力する（図６のステップ１，２，３）。
【００２８】
次に、前述の算出方法を用いて、フレーム周期Ｆ＝Ｍとし、フレーム周期Ｆ、伝搬遅延時間Ｄとしたときのタイムスロットサイクルの周回数ｋ（＝（Ｍ／Ｋ））、およびタイムスロットサイクルの数Ｋ（＝ＭとＤの最大公約数）を導出する（図６のステップ４，５）。
【００２９】
次に、この導出されたタイムスロットサイクルに基づき、以下の手順でタイムスロットを各パスに割り当てる（図６のステップ６）。
【００３０】
（手順１）
全てのタイムスロットは未割り当ての状態とする。ノードＮｉからノードＮｊへの要求タイムスロット数はＴijで与えられるものとする。ここで、未割り当てパスの中から任意のパスを一つ選び、このパスをノードＮｉからノードＮｊへのパス（ｉ，ｊ）とする。
【００３１】
（手順２）
未割り当てのタイムスロットサイクルを一つ選び、これを割り当て中のタイムスロットサイクルｙと呼ぶ。未割り当てのタイムスロットサイクルがなければ、手順を終了する。
タイムスロットサイクルｙ上でパス（ｉ，ｊ）に対するタイムスロットを割り当てる。ここで、未割り当てのタイムスロットサイクルについては、任意の一本のパスは必ず割り当てることができる。
また、タイムスロットサイクルｙの一つのタイムスロットを一本のパス（ｉ，ｊ）に割り当てた後に、Ｔij＝Ｔij−１とする。つまり要求タイムスロット数を１減じる。
【００３２】
（手順３）
未割り当てパスの中から、できるだけノードＮｊに近いノードから始まるパスを一つ選ぶ。具体的には、未割り当てパスの中から、まずノードＮｊから始まるパスを探し、見つからなければ、ノードＮｊ＋１から始まるパス、それでも見つからなければノードＮｊ＋２から始まるパスというように、順にパスの開始ノードをずらしながら、未割り当てパスの探索を行う。パスが見つかれば、これを新たにパス（ｉ，ｊ）とする。また、未割り当てパスが見つからなければ、手順を終了する。
【００３３】
（手順４）
手順３で見つかったパス（ｉ，ｊ）を、現在、割り当て中のタイムスロットサイクルｙにおいて、直前に割り当てたタイムスロットの次のタイムスロットから順にたどり、空きタイムスロットが見つかれば、手順３で見つかったパスを割り当てる。その上で、Ｔij＝Ｔij−１とした上で、手順３に進む。また、空きタイムスロットが見つからなければ手順２に進む。
【００３４】
上記の手順が終了したときに、未割り当てのパスがなければ、全てのパスに対してタイムスロットが割り当てられたことになる。また、未割り当てのパスが残っていれば、それは、上記の手順では割り当てることができなかったパスとなる。
【００３５】
上述の手順により、図６に示した手順が実行され、タイムスロットの割り当てが完了する。
【００３６】
具体例として、ノード間の要求タイムスロット数Ｔijが、Ｔ０３＝２、Ｔ１０＝１、Ｔ２１＝１、Ｔ３２＝１、その他は全て０というパス要求を考え、上述の手順を用いて、図５（ａ），（ｂ），（ｃ）に示したタイムスロットサイクルに基づきパスの割り当てを行った結果を図７（ａ），（ｂ），（ｃ）に示す。ここでは、いずれの場合においてもパス（０，３）を最初に選び、リンクＬ０−１のタイムスロット♯０からの割り当てを行った場合を示している。
【００３７】
なお、例えばＴ０３＝２は、ノードＮ０からノードＮ３へ伝送されるパスに必要なタイムスロットの数（要求タイムスロット数）が２であることを表している。また、例えばパス（０，３）は、ノードＮ０からノードＮ３へ伝送されるパスを表しており、図７中では、このパスを「０→３」により示している。
【００３８】
例えば図７（ａ）では、まずパス（０，３）をリンクＬ０−１のタイムスロット♯０から割り当て、次にパス（３，２）へのタイムスロットをリンクＬ３−０のタイムスロット♯０から割り当てた。
【００３９】
次にパス（２，１）の割り当てを行うとき、タイムスロット♯０と♯２から成るタイムスロットサイクルでは、リンクＬ２−３，Ｌ３−０，Ｌ０−１で続いたタイムスロットを確保できないため、タイムスロット♯１とタイムスロット♯３から成る２つ目のタイムスロットサイクルにパス（２，１）を割り当てる。
【００４０】
続いてパス（１，０）をリンクＬ１−２のタイムスロット♯３から割り当てた後は、残りの空きタイムスロットでは、パス（０，３）を連続して割り当てることができないまま、手続が終了となる。
【００４１】
一方、Ｄ＝３の場合は、一つのタイムスロットサイクルに、全てのパスの要求を続けて割り当てることができている（図７（ｂ）参照）。
【００４２】
また、Ｄ＝４の場合は、タイムスロットサイクルがそれぞれ１周の短いタイムスロットサイクルであるため、いずれのタイムスロットサイクルにも一本ずつのパスしか収容できていない（図７（ｃ）参照）。このため、パス（０，３）の２つ目のタイムスロット割り当てができていないまま、手続が終了となっている。
【００４３】
上記の例に見られるように、タイムスロットサイクルがＤ＝３の場合のように、全ての利用可能なタイムスロットが一本になっている場合には、それぞれのパスへのタイムスロットを連続して無駄なく割り当てていくことが可能である（図７（ｂ）参照）。
しかし、Ｄ＝２やＤ＝４の場合のようにタイムスロットサイクルが複数に分割していると、異なるタイムスロットサイクルにいくつかのタイムスロットが分散して空いていても、これを連続したタイムスロットとしてパスに割り当てることができないため、タイムスロットを有効に利用できないことが分る（図７（ａ），（ｃ）参照）。
【先行技術文献】
【非特許文献】
【００４４】
【非特許文献１】A. Chen, C.−T.Lea, and A.K.−S.Wong, "A New Optical TDM Ring Architecture," IEEE Trans. Commun., vol. 55, no. 11, pp. 2134−2141, Nov. 2007.
【非特許文献２】A. Chen, A.K.−S.Wong, and C.−T.Lea, "On the Space Reuse Efficiency of TSI−free OTDM Rings," IEEE Commun., Lett., vol. 12, no. 4, pp. 322−324, Apr., 2008.
【発明の概要】
【発明が解決しようとする課題】
【００４５】
上述のように、周期的なタイムスロット割り当てを行う光ＴＤＭリング網では、リング１周の伝搬遅延時間Ｄ（タイムスロットの数により規定した時間）と、タイムスロットをパスに割り当てるときの回線容量の分割数Ｍによって、タイムスロットサイクルの周回数と本数が定まり、このタイムスロットサイクルの本数に依存して、任意のパスの帯域要求に対して効率のよい割り当てが行えない場合があることが課題となっている。
伝搬遅延時間Ｄはリング網の利用する光ファイバの長さ等の物理的条件から定まるものであり、タイムスロットをパスに割り当てるときの回線容量の分割数Ｍはリング網の回線容量をどのように活用するかという運用ポリシーで定められるものであるため、それぞれ自由な値に設定することが困難である。
【００４６】
このような状況において、与えられたＤとＭの値の組み合わせが悪く大きな最大公約数を持つような場合には、そのリング網では常に効率の悪いタイムスロット割り当てしか行えないことになる。
前述のように例えば、Ｄ＝Ｍであった場合には、タイムスロットサイクルが１周の短いサイクルとなるため（図５（ｃ），図７（ｃ）参照）、一つのタイムスロットサイクルに割り当てられるパス数が少なく、非常に非効率的なタイムスロット割り当てしかできないことになる。
【００４７】
本発明は、上記従来技術に鑑み、光ＴＤＭリング網における回線容量の分割数Ｍとリング１周の伝搬遅延時間Ｄが任意の値であっても、常に効率のよいタイムスロットの割り当てを行うことができる、光ＴＤＭリング網のタイムスロット割り当て方法を提供することを目的とする。
【課題を解決するための手段】
【００４８】
上記課題を解決する本発明は、
光アドドロップスイッチを備えた複数のノードを、光ファイバで成る複数のリンクにより結んでおり、複数の前記リンクでのフレームの開始タイミングが同期していると共に、リング１周の伝搬遅延時間Ｄがタイムスロットの整数倍になっている光ＴＤＭリング網において、任意のノード間で伝送されるパスに必要な要求タイムスロット数に対して、必要数のタイムスロットを周期的に割り当てる光ＴＤＭリング網のタイムスロット割り当て方法であって、
前記伝搬遅延時間Ｄと、タイムスロットをパスに割り当てるときに前記リンクの回線容量を分割する分割数Ｍと、前記要求タイムスロット数を要素とする要求帯域行列Ｔを入力する工程と、
周期倍数Ｐとして任意の自然数を入力する工程と、
フレーム周期Ｆを、Ｆ＝Ｍ×Ｄ×Ｐの演算をすることにより求める工程と、
求めた前記フレーム周期Ｆと前記伝搬遅延時間Ｄを基に、ＦとＤの最大公約数であるタイムスロットサイクルの本数Ｋ＝Ｄと、ＦをＫで割ったタイムスロットサイクルの周回数ｋ＝Ｍ×Ｐを求める工程と、
前記要求帯域行列Ｔの要求タイムスロット数をＰ倍した数のパス数のトラヒックを求め、前記トラヒックのパスに対して、周回数ｋ＝Ｍ×ＰとなっているＫ＝Ｄ本の前記タイムスロットサイクルのタイムスロットを割り当てる工程と、
を有することを特徴とする。
【００４９】
また本発明は、
前記のタイムスロット割り当て方法において、
前記トラヒックのパスに対して、周回数ｋ＝Ｍ×ＰとなっているＫ＝Ｄ本の前記タイムスロットサイクルのタイムスロットを割り当てる前記工程は、
未割り当てパスの中から任意のパスを一つ選び、このパスをノードＮｉからノードＮｊへのパス（ｉ，ｊ）とする第１の手順と、
未割り当てのタイムスロットサイクルを一つ選び、これを割り当て中のタイムスロットサイクルｙとし、タイムスロットサイクルｙ上でパス（ｉ，ｊ）に対するタイムスロットを割り当て、この割り当て後にノードＮｉからノードＮｊへの要求タイムスロット数Ｔijを１減じ、未割り当てのタイムスロットサイクルがなければ手順を終了する第２の手順と、
未割り当てパスの中から、できるだけノードＮｊに近いノードから始まるパスを一つ選び、選んだパスを新たにパス（ｉ，ｊ）とし、未割り当てパスが見つからなければ手順を終了する第３の手順と、
割り当て中のタイムスロットサイクルｙにおいて、直前に割り当てたタイムスロットの次のタイムスロットから順にたどり、空きタイムスロットが見つかれば、この空きタイムスロットに前記第３の手順で見つかった新たなパス（ｉ，ｊ）を割り当て、この割り当て後に前記要求タイムスロット数Ｔijを１減じ、その後に前記第３の手順に進み、空きタイムスロットが見つからなければ前記第２の手順に進む第４の手順と、
を有することを特徴とする。
【００５０】
また本発明は、
光アドドロップスイッチを備えた複数のノードを、光ファイバで成る複数のリンクにより結んでおり、複数の前記リンクでのフレームの開始タイミングが同期していると共に、リング１周の伝搬遅延時間Ｄがタイムスロットの整数倍になっている光ＴＤＭリング網において、任意のノード間で伝送されるパスに必要な要求タイムスロット数に対して、必要数のタイムスロットを周期的に割り当てる光ＴＤＭリング網のタイムスロット割り当て方法であって、
前記伝搬遅延時間Ｄと、タイムスロットをパスに割り当てるときに前記リンクの回線容量を分割する分割数Ｍと、前記要求タイムスロット数を要素とする要求帯域行列Ｔを入力する工程と、
周期倍数Ｐとして任意の自然数を入力する工程と、
フレーム周期Ｆを、Ｆ＝Ｍ×Ｄ×Ｐ＋１の演算をすることにより求める工程と、
求めた前記フレーム周期Ｆと前記伝搬遅延時間Ｄを基に、ＦとＤの最大公約数であるタイムスロットサイクルの本数Ｋ＝１と、ＦをＫで割ったタイムスロットサイクルの周回数ｋ＝Ｍ×Ｄ×Ｐ＋１を求める工程と、
前記要求帯域行列Ｔの要求タイムスロット数をＰ×Ｄ倍した数のパス数のトラヒックを求め、前記トラヒックのパスに対して、周回数ｋ＝Ｍ×Ｄ×Ｐ＋１となっているＫ＝１本の前記タイムスロットサイクルのタイムスロットを割り当てる工程と、
を有することを特徴とする。
【００５１】
また本発明は、
前記のタイムスロット割り当て方法において、
前記トラヒックのパスに対して、周回数ｋ＝Ｍ×Ｄ×Ｐ＋１となっているＫ＝１本の前記タイムスロットサイクルのタイムスロットを割り当てる前記工程は、
未割り当てパスの中から任意のパスを一つ選び、このパスをノードＮｉからノードＮｊへのパス（ｉ，ｊ）とする第１の手順と、
１本の前記タイムスロットサイクルを割り当て中のタイムスロットサイクルｙとし、タイムスロットサイクルｙ上でパス（ｉ，ｊ）に対するタイムスロットを割り当て、この割り当て後にノードＮｉからノードＮｊへの要求タイムスロット数Ｔijを１減じる第２の手順と、
未割り当てパスの中から、できるだけノードＮｊに近いノードから始まるパスを一つ選び、選んだパスを新たにパス（ｉ，ｊ）とし、未割り当てパスが見つからなければ手順を終了する第３の手順と、
割り当て中のタイムスロットサイクルｙにおいて、直前に割り当てたタイムスロットの次のタイムスロットから順にたどり、空きタイムスロットが見つかれば、この空きタイムスロットに前記第３の手順で見つかった新たなパス（ｉ，ｊ）を割り当て、この割り当て後に前記要求タイムスロット数Ｔijを１減じ、その後に前記第３の手順に進む第４の手順と、
を有することを特徴とする。
【発明の効果】
【００５２】
本発明の光ＴＤＭリング網のタイムスロット割り当て方法では、光ＴＤＭリング網における回線容量の分割数Ｍとリング１周の伝搬遅延時間Ｄが任意の値であっても、常に効率のよいタイムスロットの割り当てを可能とすることができる。
従って、ＭやＤの値が、利用するリング網の環境や、リング網の運用ポリシー等で定められ、ＭやＤの値を都合のよい任意の値に調整することができない場合であっても、本発明を用いることで、非常に効率のよいリング網の利用が可能となる。
【図面の簡単な説明】
【００５３】
【図１】本発明の実施例１に係る、光ＴＤＭリング網のタイムスロット割り当て方法を示すフローチャート。
【図２】本発明の実施例２に係る、光ＴＤＭリング網のタイムスロット割り当て方法を示すフローチャート。
【図３】片方向光ＴＤＭリング網の構成及び各リンクでのタイムスロット割り当ての状態を示す構成図。
【図４】光アドドロップスイッチの動作例を示す構成図。
【図５】タイムスロットサイクルの形成状態を示す説明図。
【図６】従来技術に係る、光ＴＤＭリング網のタイムスロット割り当て方法を示すフローチャート。
【図７】タイムスロットサイクルに基づき、タイムスロットの割り当てを行う状態を示す説明図。
【発明を実施するための形態】
【００５４】
本発明の実施の形態を以下に説明する。
上述の図７に示した例から見られるように、タイムスロットサイクルが長いと（タイムスロットサイクルの周回数ｋが多いと）、効率的なタイムスロット割り当てが可能となることから（図７（ｂ）参照）、回線容量の分割数Ｍとリング１周の伝達遅延時間Ｄが与えられたときに、タイムスロットサイクルを長くする条件を考える。
具体的には、フレーム周期Ｆの値として、従来のＭとするのではなく、Ｍ×Ｄの整数倍の値、あるいは、Ｍ×Ｄの整数倍に１を加えた値を用いることとする。
つまり従来ではフレーム周期Ｆ＝Ｍとしていたが、本実施の形態ではフレーム周期Ｆ＝Ｍ×Ｄ×整数や、フレーム周期Ｆ＝Ｍ×Ｄ×整数＋１とした。
【００５５】
まず、周期倍数Ｐを任意の自然数（０を除く自然数）とするとき、フレーム周期Ｆを、ＭではなくＭ×Ｄ×Ｐとした場合のタイムスロットサイクルを求める。
【００５６】
このとき、フレーム周期Ｆは、ＭやＰによらず、Ｄの整数倍になっているため、フレーム周期Ｆとリング伝搬遅延時間Ｄの最大公約数はＤとなる。従って、このとき、タイムスロットサイクルの周回数ｋはＭ×Ｐ周期の長さとなり、タイムスロットサイクルの本数ＫはＤ本となる。
【００５７】
ここの議論をまとめると、フレーム周期Ｆ（＝Ｍ×Ｄ×Ｐ）とリング伝搬遅延時間Ｄとの最大公約数が、タイムスロットサイクルの本数Ｋである。したがって上記のように、本実施の形態では、タイムスロットサイクルの本数Ｋ＝Ｄとなる。ちなみに従来ではＫは、ＭとＤの最大公約数である。
またフレーム周期Ｆ（＝Ｍ×Ｄ×Ｐ）を、タイムスロットサイクルの本数Ｋ（＝Ｄ）で除算したものが、タイムスロットサイクルの周回数ｋである。上記のように、本実施の形態では、タイムスロットサイクルの周回数ｋ＝ＭＰとなる。ちなみに従来ではｋ＝Ｍ／Ｋである。
【００５８】
ここでノードＮｉからノードＮｊへのパスに必要な要求タイムスロット数が要求帯域行列Ｔ＝｛Ｔij｝で与えられたとき、この各要素をＰ倍したトラヒックを考え、これを上述のＭ×Ｐ周の長さのタイムスロットサイクルに対して割り当てる。そして、残りのＤ−１本の他のタイムスロットサイクルに対しても、この割り当てと同様の割り当てを行うこととする。
【００５９】
その結果、一つのパスについて、各タイムスロットサイクルに対してＰ個のタイムスロットが割り当てられ、それがＤ本分割り当てられていることになるため、フレーム周期Ｆ＝Ｍ×Ｄ×Ｐの中で、Ｐ×Ｄ個のタイムスロットが割り当てられたことになる。
【００６０】
従って、元々のフレーム周期Ｆ＝Ｍに対して１個のタイムスロットを割り当てた場合と同様の比率でのタイムスロットの割り当てが行えるため、リング網の利用効率としては、当初の目的を達成していると考えられる。また、タイムスロットサイクルの長さ（周回数）が、従来ではＭ／Ｋとなっていたものに対して、Ｍ×Ｐと長くなっているため、パスへのトラックを効率よく割り当てることが可能である。
【００６１】
一方、フレーム周期Ｆを、ＭではなくＭ×Ｄ×Ｐ＋１とした場合についてここで考えると、ＦとＤの最大公約数は１となる。この場合、タイムスロットサイクルの本数Ｋは１本で、タイムスロットサイクルの周回数ｋはＭ×Ｄ×Ｐ＋１となる。従って、ＭやＤによら
ず、非常に長い周期のタイムスロットサイクルを実現することができる。
【００６２】
ここの議論をまとめると、フレーム周期Ｆ（＝Ｍ×Ｄ×Ｐ＋１）とリング伝搬遅延時間Ｄとの最大公約数が、タイムスロットサイクルの本数Ｋである。したがって上記のように、本実施の形態では、タイムスロットサイクルの本数Ｋ＝１となる。ちなみに従来ではＫは、ＭとＤの最大公約数である。
またフレーム周期Ｆ（＝Ｍ×Ｄ×Ｐ＋１）を、タイムスロットサイクルの本数Ｋ（＝１）で除算したものが、タイムスロットサイクルの周回数ｋである。上記のように、本実施の形態では、タイムスロットサイクルの周回数ｋ＝Ｍ×Ｄ×Ｐ＋１となる。ちなみに従来ではｋ＝Ｍ／Ｋである。
【００６３】
ここで、割り当てるトラヒックについては、元々のトラヒックをＤ×Ｐ倍したものを算出し、これをＭ×Ｄ×Ｐ＋１周の長いタイムスロットサイクルに割り当てていくことになる。このようなタイムスロットの割り当てでは、タイムスロットサイクルが非常に長いため、効率的なタイムスロット割り当てが可能となる。
【００６４】
上記２つの実施の形態の状態を表に示すと次のようになる。
【表２】
2016010073.tif 000004
【実施例】
【００６５】
以下、本発明に係る、光ＴＤＭリング網のタイムスロット割り当て方法を、実施例に基づき詳細に説明する。
なお以下の実施例では、リング１周の伝搬遅延時間Ｄ、回線容量の分割数Ｍ、要求帯域行列Ｔ、周期倍数Ｐを制御装置に入力して、それぞれの演算処理をして、パスへのタイムスロット割り当てを行うものである。但し、制御装置等のハードウエアは通常の技術であるため、ハードウエアの説明は省略し、データ処理手順のみを説明する。
【００６６】
［実施例１］
本発明の実施例１に係るタイムスロット割り当て方法を図１に示す。
図１に示す実施例１は、図６に記載した従来の手順に対して、
（１）周期倍数Ｐとして任意の自然数（０を除く自然数）を入力する手順（図１のステップ１４）と、
（２）リング伝搬遅延Ｄと回線容量の分割数Ｍと周期倍数Ｐから、フレーム周期をＦ＝Ｍ×Ｄ×Ｐを算出する手順（図１のステップ１５）と、
（３）要求帯域行列Ｔの要素（要求タイムスロット数Ｔij）をＰ倍する手順（図１のステップ１７）と、を加えたものである。
【００６７】
このような手順により、前述のようなフレーム周期ＦをＭ×Ｄ×Ｐとした制御を行うこととなり、各パスへの要求帯域の割り当てを、Ｄ本の周回数ｋがＭ×Ｐのタイムスロットサイクルを利用しながら行うことになる。
【００６８】
ここで、Ｍ×Ｐのタイムスロットサイクルに対して、元々の要求タイムスロット数のＰ倍に拡大したものを割り当てることとなる。
また、Ｄ本のタイムスロットサイクルのそれぞれに対して、同様に割り当てを行うため、トータルとしてはフレーム周期Ｍ×Ｄ×Ｐに対してＰ×Ｄ倍のトラヒックを割り当てることが可能となる。
【００６９】
次に、実施例１に係るタイムスロット割り当て方法について、更に詳述する。
【００７０】
まず、リング網のリング１周の伝搬遅延時間Ｄ（タイムスロットの数により規定した時間）、タイムスロットをパスに割り当てるときにリンクの回線容量を分割する分割数Ｍ、
および各ノードＮｉからノードＮｊへのパスに対する帯域タイムスロット数（要求タイムスロット数）Ｔijを要素とする要求帯域行列Ｔを入力する（図１のステップ１１，１２，１３）。
【００７１】
次に、周期倍数Ｐとして任意の自然数を入力する（図１のステップ１４）。
つづいて、フレーム周期Ｆ＝Ｍ×Ｄ×Ｐの演算を行う（図１のステップ１５）。
【００７２】
フレーム周期Ｆ（＝Ｍ×Ｄ×Ｐ）と伝搬遅延時間Ｄに基づき、タイムスロットサイクルの周回数ｋがＭ×Ｐとなっている、Ｄ本のタイムスロットサイクルを演算する（図１のステップ１６）。
【００７３】
要求帯域行列Ｔに与えられている、ノードＮｉからノードＮｊへのパスに必要な要求タイムスロット数（要素）Ｔijを、Ｐ倍に拡大する（図１のステップ１７）。
【００７４】
このように各要素をＰ倍したトラヒックを考え、これを上述のＭ×Ｐ周の長さのタイムスロットサイクルに対して割り当てる。そして、残りのＤ−１本の他のタイムスロットサイクルに対しても、この割り当てと同様の割り当てを行う（図１のステップ１８）。
【００７５】
図１のステップ１８は、下記の手順１１から手順１３に従って行う。
【００７６】
（手順１１）
全てのタイムスロットは未割り当ての状態とする。ノードＮｉからノードＮｊへの要求タイムスロット数はＴijで与えられるものとする。ここで、未割り当てパスの中から任意のパスを一つ選び、このパスをノードＮｉからノードＮｊへのパス（ｉ，ｊ）とする。
【００７７】
（手順１２）
未割り当てのタイムスロットサイクルを一つ選び、これを割り当て中のタイムスロットサイクルｙと呼ぶ。未割り当てのタイムスロットサイクルがなければ、手順を終了する。
タイムスロットサイクルｙ上でパス（ｉ，ｊ）に対するタイムスロットを割り当てる。ここで、未割り当てのタイムスロットサイクルについては、任意の一本のパスは必ず割り当てることができる。
また、タイムスロットサイクルｙの一つのタイムスロットを一本のパス（ｉ，ｊ）に割り当てた後に、Ｔij＝Ｔij−１とする。つまり要求タイムスロット数を１減じる。
【００７８】
（手順１３）
未割り当てパスの中から、できるだけノードＮｊに近いノードから始まるパスを一つ選ぶ。具体的には、未割り当てパスの中から、まずノードＮｊから始まるパスを探し、見つからなければ、ノードＮｊ＋１から始まるパス、それでも見つからなければノードＮｊ＋２から始まるパスというように、順にパスの開始ノードをずらしながら、未割り当てパスの探索を行う。パスが見つかれば、これを新たにパス（ｉ，ｊ）とする。また、未割り当てパスが見つからなければ、手順を終了する。
【００７９】
（手順１４）
手順１３で見つかったパス（ｉ，ｊ）を、現在、割り当て中のタイムスロットサイクルｙにおいて、直前に割り当てたタイムスロットの次のタイムスロットから順にたどり、空きタイムスロットが見つかれば、手順１３で見つかったパスを割り当てる。その上で、Ｔij＝Ｔij−１とした上で、手順１３に進む。また、空きタイムスロットが見つからなければ手順１２に進む。
【００８０】
上記の手順が終了したときに、未割り当てのパスがなければ、全てのパスに対してタイムスロットが割り当てられたことになる。
【００８１】
上述の手順により、図１に示した手順が実行され、タイムスロットの割り当てが完了する。
【００８２】
［実施例２］
本発明の実施例２に係るタイムスロット割り当て方法を図２に示す。
図２に示す実施例２は、図６に記載した従来の手順に対して、
（１）周期倍数Ｐとして任意の自然数（０を除く自然数）を入力する手順（図２のステップ２４）と、
（２）リング伝搬遅延Ｄと回線容量の分割数Ｍと周期倍数Ｐから、フレーム周期Ｆ＝Ｍ×Ｄ×Ｐ＋１を算出する手順（図２のステップ２５）と、
（３）要求帯域行列Ｔの要素（要求タイムスロット数Ｔij）をＰ×Ｄ倍する手順（図２のステップ２７）と、を加えたものである。
【００８３】
このような手順により、前述のようなフレーム周期ＦをＭ×Ｄ×Ｐ＋１とした制御を行うこととなり、各パスへの要求帯域の割り当てを、１本の周回数ｋがＭ×Ｄ×Ｐ＋１のタイムスロットサイクルを利用しながら行うことになる。
【００８４】
ここで、Ｍ×Ｄ×Ｐ＋１のタイムスロットサイクルに対して、元々の要求タイムスロット数のＰ×Ｄ倍に拡大したものを割り当てることとなる。
【００８５】
従来のＭ周期に１タイムスロットの割り当てが、回線容量の１／Ｍの帯域を割り当てたことに相当したが、実施例２の割り当てにおいては、Ｍ×Ｄ×Ｐ＋１周期にＤ×Ｐ個のタイムスロットが割り当てられることになるため、この場合の回線容量は（Ｐ×Ｄ）／（Ｍ×Ｄ×Ｐ＋１）ということで、１／Ｍよりも少し小さな値になっている。しかし、非常に大きな連続タイムスロットサイクルを利用して、パスへのタイムスロット割り当てを行うため、非常に効率的な手法として効果が大きいと考えられる。
【００８６】
次に、実施例２に係るタイムスロット割り当て方法について、更に詳述する。
【００８７】
まず、リング網のリング１周の伝搬遅延時間Ｄ（タイムスロットの数により規定した時間）、タイムスロットをパスに割り当てるときにリンクの回線容量を分割する分割数Ｍ、
および各ノードＮｉからノードＮｊへのパスに対する帯域タイムスロット数（要求タイムスロット数）Ｔijを要素とする要求帯域行列Ｔを入力する（図２のステップ２１，２２，２３）。
【００８８】
次に、周期倍数Ｐとして任意の自然数を入力する（図２のステップ２４）。
つづいて、フレーム周期Ｆ＝Ｍ×Ｄ×Ｐ＋１の演算を行う（図２のステップ２５）。
【００８９】
フレーム周期Ｆ（＝Ｍ×Ｄ×Ｐ＋１）と伝搬遅延時間Ｄに基づき、タイムスロットサイクルの周回数ｋがＭ×Ｄ×Ｐ＋１となっている、１本のタイムスロットサイクルを演算する（図２のステップ２６）。
【００９０】
要求帯域行列Ｔに与えられている、ノードＮｉからノードＮｊへのパスに必要な要求タイムスロット数（要素）Ｔijを、Ｐ×Ｄ倍に拡大する（図２のステップ２７）。
【００９１】
このように各要素をＰ×Ｄ倍したトラヒックを考え、これを上述のＭ×Ｄ×Ｐ＋１周の長さの１本のタイムスロットサイクルに対して割り当てる。（図２のステップ２８）。
【００９２】
図２のステップ２８は、下記の手順２１から手順２３に従って行う。
【００９３】
（手順２１）
全てのタイムスロットは未割り当ての状態とする。ノードＮｉからノードＮｊへの要求タイムスロット数はＴijで与えられるものとする。ここで、未割り当てパスの中から任意のパスを一つ選び、このパスをノードＮｉからノードＮｊへのパス（ｉ，ｊ）とする。
【００９４】
（手順２２）
１本のタイムスロットサイクルを、割り当て中のタイムスロットサイクルｙと呼ぶ。
このタイムスロットサイクルｙ上でパス（ｉ，ｊ）に対するタイムスロットを割り当てる。
また、タイムスロットサイクルｙの一つのタイムスロットを一本のパス（ｉ，ｊ）に割り当てた後に、Ｔij＝Ｔij−１とする。つまり要求タイムスロット数を１減じる。
【００９５】
（手順２３）
未割り当てパスの中から、できるだけノードＮｊに近いノードから始まるパスを一つ選ぶ。具体的には、未割り当てパスの中から、まずノードＮｊから始まるパスを探し、見つからなければ、ノードＮｊ＋１から始まるパス、それでも見つからなければノードＮｊ＋２から始まるパスというように、順にパスの開始ノードをずらしながら、未割り当てパスの探索を行う。パスが見つかれば、これを新たにパス（ｉ，ｊ）とする。また、未割り当てパスが見つからなければ、手順を終了する。
【００９６】
（手順２４）
手順２３で見つかったパス（ｉ，ｊ）を、タイムスロットサイクルｙにおいて、直前に割り当てたタイムスロットの次のタイムスロットから順にたどり、空きタイムスロットが見つかれば、手順２３で見つかったパスを割り当てる。その上で、Ｔij＝Ｔij−１とした上で、手順２３に進む。
【００９７】
上記の手順が終了したときに、未割り当てのパスがなければ、全てのパスに対してタイムスロットが割り当てられたことになる。
【００９８】
上述の手順により、図２に示した手順が実行され、タイムスロットの割り当てが完了する。
【産業上の利用可能性】
【００９９】
本発明は、片方向光ＴＭＤリング網や双方向光ＴＭＤリング網において、タイムスロットを割り付ける場合に利用することができる。
【符号の説明】
【０１００】
Ｎ０，Ｎ１，Ｎ２，Ｎ３  ノード
Ｌ０，Ｌ１，Ｌ２，Ｌ３  リンク
ｆ  光ファイバ
ｆｄ  遅延調整用光ファイバ
ＳＷ  光アドドロップスイッチ
【図１】
2016010073.tif 000005
【図２】
2016010073.tif 000006
【図３】
2016010073.tif 000007
【図４】
2016010073.tif 000008
【図５】
2016010073.tif 000009
【図６】
2016010073.tif 000010
【図７】
2016010073.tif 000011