JP4369892B2 - 信号転送可能時間帯算出方法、信号転送可能時間帯算出装置、信号転送可能時間帯算出プログラムおよびコンピュータ読み取り可能な記録媒体 - Google Patents

Description

本発明は、複数のノードと、２つのノード間を接続する部分パスとを有するツリー構造のネットワークの端部に配置されたノードである所定のエッジ装置が他のエッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出方法、信号転送可能時間帯算出装置、信号転送可能時間帯算出プログラムおよびコンピュータ読み取り可能な記録媒体に関する。

近年、データトラフィックの増加に伴い、大容量の光伝送方式への需要が高まっている。これらの種類として、ＷＤＭ（Wavelength Division Multiplexing）などの波長多重方式や光ＴＤＭ（Time Division Multiplexing）などの時分割多重方式、光バーストスイッチングや光パケットスイッチングなどのパケット多重方式が提案されている。その中で、ブロードキャスト型の光伝送方式として、ＧＥＰＯＮ（Gigabit Ethernet（登録商標）-Passive Optical Network）が知られている（例えば非特許文献１参照）。

このＧＥＰＯＮはループのないツリー状のネットワーク上で実現される。ネットワークの分岐点には光信号を分岐するカプラが設けられている。また、ＧＥＰＯＮでは、光信号を送信する装置として、ＯＮＵ（Optical Network Unit）とＯＬＴ（Optical Line Terminal）が存在している。ＯＬＴの下流にはユーザが利用するＯＮＵが配置されており、ＯＬＴは、ユーザから送られるデータを光信号に変換して他のＯＮＵに送信する役割を果たす。つまり、ＯＮＵから送られた光信号は一度ＯＬＴにより終端され、他のＯＮＵに送られるのである。このとき、複数のＯＮＵから同時に光信号がＯＬＴに送信されると、ネットワーク内で信号同士が衝突するため、ＯＮＵから送信（出力）される信号の転送タイミングを調整することが必要となる。ＧＥＰＯＮでは、ＯＬＴがＯＮＵに対し、光信号の転送開始時刻および転送終了時刻を通知することでこの調整を行っている。

ＧＥＰＯＮの問題点は、ＯＮＵが出力する光信号が、ネットワークを構成する光ファイバにより物理的に接続されているＯＮＵすべてに到達することである。ＯＮＵから出力された光信号はＯＬＴからＯＮＵに転送される際、ネットワークの分岐点であるカプラで信号レベルが減衰する。この減衰量は、カプラの分岐数に依存するため、カプラの先に存在するＯＮＵ数が増加するのに従って増加することになる。この問題を解決するため、分岐点での分岐数を制限することが可能なMultipoint-to-Multipoint型光パスを利用した光伝送方式を用いることが考えられる。この光伝送方式は、光信号を送信するエッジ装置、光信号を分岐して信号の宛先へと誘導するスイッチ装置および光ファイバからなるネットワーク上で光伝送を行う技術である。

この場合、ネットワークの分岐点として、カプラだけではなく、スイッチ装置を利用することで、光信号を送りたいところのみ信号を通過させることができる。そして、各エッジ装置はこの光信号を用いて信号の届くほかのエッジ装置に対してデータを送信する。この光伝送方式を用いれば、光信号の減衰量が低下し、光信号をより長い区間で送信することができる。また、光信号を通すファイバ数を少なくすることで、同一波長をもつ光信号を別の光ファイバを利用して送信することが可能となり、ネットワーク全体での光信号の利用効率が向上する。
「ＦＴＴＨの最新技術を知る」、日経NETWORK、日経BP社、2004年６月、p.43−61

しかしながら、Multipoint-to-Multipoint型光パスを用いた光伝送方式でも、ＧＥＰＯＮで発生していた信号の衝突現象は起こりうるという問題がある。
そこで、信号の衝突を回避するために、各エッジ装置から送信された信号が光ファイバを通過する時刻（通過時刻）を取得し、２つ以上の信号が同位置を同時刻に通過しないことを条件に通過時刻を割り当てることが考えられる。例えば、この条件ですべてのエッジ装置が予め決められた順番に従って光信号を送信し終わったときに（一巡したときに）、最初に光信号を送信したエッジ装置から同じ順番で光信号を送信することが考えられる。この場合、順番によっては送信順が一巡するまでに要する時間がかかり過ぎるという問題が生じる。

そこで、本発明では、前記した問題を解決し、信号の衝突を防止することのできる信号転送可能時間帯算出方法、信号転送可能時間帯算出装置、信号転送可能時間帯算出プログラムおよび記録媒体を提供することを目的とする。
また、本発明は、転送対象とする信号が一巡するまでに要する時間を低減できる信号転送可能時間帯算出方法、信号転送可能時間帯算出装置、信号転送可能時間帯算出プログラムおよび記録媒体を提供することを他の目的とする。

前記課題を解決するため、請求項１に記載の信号転送可能時間帯算出方法は、複数のノードとノード間を接続するリンクとを備えてループのないツリー状のネットワークにおいて、前記ノードは、このネットワークの端部に配置された複数のエッジ装置と、前記複数のエッジ装置間のMultipoint-to-Multipoint型光パスを実現するために前記リンクが部分パスとして３つ以上接続されたスイッチ装置を示す複数の分岐ノードと、前記各エッジ装置が前記光パスにより別の前記エッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出装置とを含み、前記信号転送可能時間帯算出装置による信号転送可能時間帯算出方法であって、前記信号が前記光パスの各部分パスを通過する際に遅延する時間を示す遅延時間と、前記各部分パスの接続状態を示す接続情報と、前記複数のエッジ装置から選択された第１のエッジ装置が前記信号を出力する時間を示す信号出力時間とを取得する情報取得ステップと、この情報取得ステップで取得された遅延時間、接続情報および信号出力時間に基づいて、前記第１のエッジ装置から出力される信号が前記分岐ノードを通過する際の信号通過開始時刻および信号通過終了時刻を算出する通過時刻算出ステップと、この通過時刻算出ステップで算出された信号通過開始時刻および信号通過終了時刻と前記信号出力時間とに基づいて、前記第１のエッジ装置以外に選択された前記エッジ装置を示す第２のエッジ装置から出力される信号の信号通過開始時刻に所定の時間間隔を加算した時刻が、前記第１のエッジ装置から出力される信号の信号通過終了時刻に連続するような部分パスを１つ以上設けるように、かつ、前記第１のエッジ装置として選択できるすべての前記エッジ装置から出力される信号が、前記各部分パス上の同方向かつ同位置を同時刻に通過しないように、前記信号通過開始時刻に加算する所定の時間間隔を算出することにより、前記各エッジ装置における信号出力タイミングを算出するタイミング算出ステップと、を含んで実行し、前記タイミング算出ステップが、前記第２のエッジ装置から出力される信号の通過する前記部分パスにおいて、前記第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記信号通過開始時刻に加算する所定の時間間隔との和の最大値が最小となるように、当該所定の時間間隔を算出することを特徴とする。

請求項７に記載の信号転送可能時間帯算出装置は、複数のノードとノード間を接続するリンクとを備えてループのないツリー状のネットワークにおいて、前記ノードが、このネットワークの端部に配置された複数のエッジ装置と、前記複数のエッジ装置間のMultipoint-to-Multipoint型光パスを実現するために前記リンクが部分パスとして３つ以上接続されたスイッチ装置を示す複数の分岐ノードと、前記各エッジ装置が前記光パスにより別の前記エッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出装置とを含み、前記ネットワークにおける信号転送可能時間帯算出装置であって、前記信号が前記光パスの各部分パスを通過する際に遅延する時間を示す遅延時間と、前記各部分パスの接続状態を示す接続情報と、前記複数のエッジ装置から選択された第１のエッジ装置が前記信号を出力する時間を示す信号出力時間とに基づいて、前記第１のエッジ装置から出力される信号が前記分岐ノードを通過する際の信号通過開始時刻および信号通過終了時刻を算出する通過時刻算出手段と、この通過時刻算出手段で算出された信号通過開始時刻および信号通過終了時刻と前記信号出力時間とに基づいて、前記第１のエッジ装置以外に選択された前記エッジ装置を示す第２のエッジ装置から出力される信号の信号通過開始時刻に所定の時間間隔を加算した時刻が、前記第１のエッジ装置から出力される信号の信号通過終了時刻に連続するような部分パスを１つ以上設けるように、かつ、前記第１のエッジ装置として選択できるすべての前記エッジ装置から出力される信号が、前記各部分パス上の同方向かつ同位置を同時刻に通過しないように、前記信号通過開始時刻に加算する所定の時間間隔を算出することにより、前記各エッジ装置における信号出力タイミングを算出するタイミング算出手段と、を備え、前記タイミング算出手段が、前記第２のエッジ装置から出力される信号の通過する前記部分パスにおいて、前記第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記信号通過開始時刻に加算する所定の時間間隔との和の最大値が最小となるように、当該所定の時間間隔を順次算出することとした。

請求項１に示す方法または請求項７に示す装置によれば、各エッジ装置から出力される信号の出力時間と、各部分パスを通過する時刻とに基づいて、各エッジ装置から出力される信号が部分パス上の同方向かつ同位置を同時刻に通過することのないように、各エッジ装置から出力される信号が所定の時間間隔をずらして転送される。したがって、各エッジ装置から出力される信号が部分パス上において衝突することを防止することができる。

ここで、部分パスは、例えば光ファイバによって構成され、分岐ノードは、エッジ装置から出力される信号を宛先へ誘導するスイッチ装置から構成される。また、信号通過開始時刻および信号通過終了時刻は、例えばネットワーク上の所定の地点に関連付けて計算される。また、各エッジ装置が信号を出力する時間を示す信号出力時間は、例えば、信号出力継続時間や、信号出力開始時刻および信号出力終了時刻等である。
また、請求項１に示す方法または請求項７に示す装置によれば、第１のエッジ装置から出力される信号に対して、第２のエッジ装置から出力される信号を所定の時間間隔だけずらして転送する際に、第２のエッジ装置から出力される信号の信号通過終了時刻と所定の時間間隔との和について、部分パスによる相違を考慮することができる。そして、この和の最大値を最小とするので、信号通過開始時刻に加算する所定の時間間隔は、第２のエッジ装置から出力される信号に対して最も小さいものとすることができる。したがって、転送対象とする信号が一巡するまでの時間を低減し、各信号の転送効率を向上させることができる。

請求項２に記載の信号転送可能時間帯算出方法は、請求項１に記載の信号転送可能時間帯算出方法において、前記通過時刻算出ステップにおいて、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号出力側の部分パスの始点に関連付けて算出することを特徴とする。

請求項８に記載の信号転送可能時間帯算出装置は、請求項７に記載の信号転送可能時間帯算出装置において、前記通過時刻算出手段が、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号出力側の部分パスの始点に関連付けて算出することを特徴とする。

請求項２に示す方法または請求項８に示す装置によれば、接続情報として、部分パス同士の接続関係さえわかればよいので、部分パスがどのノードと接続しているかを示す情報を省略できるので、取得すべき接続情報を簡略化することができる。

請求項３に記載の信号転送可能時間帯算出方法は、請求項１に記載の信号転送可能時間帯算出方法において、前記通過時刻算出ステップにおいて、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号入力側の部分パスの終点に関連付けて算出することを特徴とする。

請求項９に記載の信号転送可能時間帯算出装置は、請求項７に記載の信号転送可能時間帯算出装置において、前記通過時刻算出手段が、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号入力側の部分パスの終点に関連付けて算出することを特徴とする。

請求項３に示す方法または請求項９に示す装置によれば、接続情報として、部分パス同士の接続関係さえわかればよいので、部分パスがどのノードと接続しているかを示す情報を省略できるので、取得すべき接続情報を簡略化することができる。また、部分パスの始点に関連付けて信号通過開始時刻および信号通過終了時刻を算出する場合と比較して、対象とする部分パスにおける遅延時間をそのまま利用することができるので、その分だけ計算手順を省略化することができる。

請求項４に記載の信号転送可能時間帯算出方法は、請求項１に記載の信号転送可能時間帯算出方法において、前記通過時刻算出ステップにおいて、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに関連付けて算出することを特徴とする。

請求項１０に記載の信号転送可能時間帯算出装置は、請求項７に記載の信号転送可能時間帯算出装置において、前記通過時刻算出手段が、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに関連付けて算出することを特徴とする。

請求項４に示す方法または請求項１０に示す装置によれば、部分パスにおいて信号通過開始時刻および信号通過終了時刻を算出する場合と比較して、部分パスにおける信号通過方向（上り、下り）を考慮する必要がないので、計算量を低減することができる。

請求項５に記載の信号転送可能時間帯算出方法は、請求項１ないし請求項４のいずれか一項に記載の信号転送可能時間帯算出方法において、前記タイミング算出ステップは、前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、ランダムに２つのエッジ装置を、前記第１のエッジ装置および第２のエッジ装置として組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となるようにした後、前記両エッジ装置以外のエッジ装置との組み合わせを順次選択することを特徴とする。

請求項１１に記載の信号転送可能時間帯算出装置は、請求項７ないし請求項１０のいずれか一項に記載の信号転送可能時間帯算出装置において、前記タイミング算出手段が、前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、ランダムに２つのエッジ装置を、前記第１のエッジ装置および第２のエッジ装置として組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となるようにした後、前記両エッジ装置以外のエッジ装置との組み合わせを順次選択することを特徴とする。

請求項５に示す方法または請求項１１に示す装置によれば、第１のエッジ装置から出力される信号と、第２のエッジ装置から出力される信号との組み合わせがランダムに選択されるので、計算量を必要最小限に抑制して、転送可能時間帯を迅速に算出することができる。

請求項６に記載の信号転送可能時間帯算出方法は、請求項１ないし請求項４のいずれか一項に記載の信号転送可能時間帯算出方法において、前記タイミング算出ステップは、前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、前記第１のエッジ装置を前記第２のエッジ装置とそれぞれ仮に組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となる第２のエッジ装置を組み合わせることを決定した後、組み合わせることを決定された両エッジ装置以外のエッジ装置との組み合わせを同様に決定することを特徴とする。

請求項１２に記載の信号転送可能時間帯算出装置は、請求項７ないし請求項１０のいずれか一項に記載の信号転送可能時間帯算出装置において、前記タイミング算出手段が、前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、前記第１のエッジ装置を前記第２のエッジ装置とそれぞれ仮に組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となる第２のエッジ装置を組み合わせることを決定した後、組み合わせることを決定された両エッジ装置以外のエッジ装置との組み合わせを同様に決定することを特徴とする。

請求項６に示す方法または請求項１２に示す装置によれば、第１のエッジ装置から出力される信号と、第２のエッジ装置から出力される信号との組み合わせとして、すべての組み合わせの中で最適な組み合わせを抽出してから、さらに別のエッジ装置から出力される信号を選択するので、すべてのエッジ装置を最適に組み合わせることができる。したがって、転送対象とする信号が一巡するまでの時間を最も低減することができ、各信号の転送効率を向上することができる。

請求項１３に記載の信号転送可能時間帯算出プログラムは、請求項１乃至請求項６のいずれか一項に記載の信号転送可能時間帯算出方法をコンピュータに実行させるためのプログラムである。このように構成されることにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。

請求項１４に記載のコンピュータ読み取り可能な記録媒体は、請求項１３に記載の信号転送可能時間帯算出プログラムが記録されたことを特徴とする。このように構成されることにより、この記録媒体を読み取り可能な情報処理装置は、このプログラムに基づいた各機能を実現することができる。

本発明によれば、各エッジ装置から出力される信号と、その信号が各部分パスを通過する時刻とに基づいて、各エッジ装置から出力される信号が所定の時間間隔をずらして転送される。したがって、各エッジ装置から出力される信号が部分パス上において衝突することを防止することができる。
また、本発明は、所定のエッジ装置から出力される信号に対して、別のエッジ装置から出力される信号を所定の時間間隔だけずらして転送する際に、信号通過終了時刻と前記所定の時間間隔との和について、部分パスによる相違を考慮したので、転送対象とする信号が一巡するまでの時間を低減し、各信号の転送効率を向上させることができる。

（第１の実施形態）
［信号転送可能時間帯算出装置の構成］
以下、本発明の第１の実施形態に係る信号転送可能時間帯算出装置の構成を図１乃至図３を参照して説明する。図１は本発明の第１の実施形態に係る信号転送可能時間帯算出装置を含むネットワークシステムの構成図であり、図２は図１に示した信号転送可能時間帯算出装置の構成を示すブロック図であり、図３は図１に示した信号転送可能時間帯算出装置に記憶された情報テーブルを示す説明図である。

ネットワークシステム１００は、図１に示すように、複数のノード１１０，１２０，１３０と、２つのノード（１１０，１２０，１３０のいずれか）間を接続する部分パス（リンク）ｅとを有するループのないツリー構造のネットワークである。ノード１１０〜１３０は、機能が異なり、以下の説明では、それぞれエッジ装置１１０と、分岐ノード１２０と、信号転送可能時間帯算出装置１３０として説明する。なお、図１に示したノードと部分パスの個数は一例であって、本発明はこれに限定されるものではない。

エッジ装置１１０は、ネットワークシステム１００のツリー構造の端部に配置されている。このエッジ装置１１０は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、通信インターフェースおよびハードディスクドライブ（ＨＤＤ）などを含んで構成されるパーソナルコンピュータであり、所定の信号を他のエッジ装置１１０に出力すると共に、他のエッジ装置１１０から出力された信号が入力するものである。この所定の信号は例えば光信号であり、部分パスｅ（図１に示した例ではｅ０，ｅ１，ｅ２，ｅ３，ｅ４，ｅ５）は、例えば上り方向の光信号と下り方向の光信号とを分離して伝送する光ファイバである。ここで、複数のエッジ装置１１０を識別するために識別変数としてｒ（図１に示した例ではｒ＝１〜４）を導入し、特に区別しないときにはエッジ装置１１０を単にエッジ装置ｒと呼ぶことにする。

分岐ノード１２０は、部分パスｅが３つ以上接続されたノードであり、１つの部分パスｅから入力した信号を他の部分パスｅ′にそれぞれ出力するスイッチ装置である。ここで、複数の分岐ノード１２０を識別するために識別変数としてｎ（図１に示した例ではｎ＝１０，１１）を導入し、特に区別しないときには分岐ノード１２０を分岐ノードｎと呼ぶ。なお、このｎはノード全般（１１０，１２０，１３０）に使用することもある。

信号転送可能時間帯算出装置１３０は、例えば、ネットワークシステム１００のツリー構造の端部に配置され、各エッジ装置ｒから出力される信号が各部分パスｅ上で衝突しないように、各エッジ装置ｒから出力される信号の転送時間帯を算出し、各エッジ装置ｒにおける信号出力タイミング（信号転送時間帯）を割り当てるものである。この信号転送可能時間帯算出装置１３０は、図２に示すように、入出力手段２１０と、ＲＡＭ２２０と、ＨＤＤ２３０と、ＣＰＵ２４０とを備えている。

入出力手段２１０は、部分パスｅを介して、各エッジ装置ｒから入力される情報（信号出力時間など）をＨＤＤ２３０に出力すると共に、各エッジ装置ｒに割り当てた信号転送時間帯を示す情報を各エッジ装置ｒに出力するためのインタフェースである。この入出力手段２１０は、外部装置から入力される情報（遅延時間、接続情報など）をＨＤＤ２３０に出力する。
ＲＡＭ２２０は、半導体メモリや磁気メモリなどの書き換え可能な記憶手段であり、ＣＰＵ２４０による演算処理等に利用される。

ＨＤＤ２３０は、入出力手段２１０を介して取得した遅延時間２３１、接続情報２３３および信号出力時間２３５や、ＣＰＵ２４０の処理結果等を記憶するものである。
遅延時間２３１は、エッジ装置ｒから出力される信号が各部分パスｅを通過する際に遅延する時間を示すものである。なお、個々の遅延時間２３１を遅延時間ｄ（ｅ）と表記する。
接続情報２３３は、各部分パスｅの接続状態を示すものであり、例えば、各部分パスｅの両端が接続しているノードｎに関する情報や、各部分パスｅの両端が接続している別の部分パスｅ′に関する情報である。
信号出力時間２３５は、各エッジ装置ｒが信号を出力する時間を示し、例えば信号出力継続時間や、信号出力開始時刻および終了時刻等である。なお、個々の信号出力時間２３５を信号出力時間ｓ（ｒ）と表記する。

ここで、遅延時間２３１と接続情報２３３の具体例を図１および図３を参照して説明する。図３に示した情報テーブル３００では、例えば部分パスｅ１の遅延時間ｄ（ｅ１）は「１」となっている。また、情報テーブル３００では、接続情報２３３は、各部分パスｅの両端（端点１，端点２）が接続している部分パスｅを示している。例えば、部分パスｅ１は、端点１の接続情報が「ｎｕｌｌ（空白）」となっており、端点１には、別の部分パスｅ′が接続されていないことを示している。一方、端点２には、部分パスｅ２，ｅ３が接続されていることが示されている。なお、ここでは部分パスｅ０を考慮しないものとする。これらの部分パスｅのうち、部分パスｅ２に接続されている部分パスｅを求めるには、部分パスｅ２の端点１を参照することになる。この場合には、部分パスｅ２の端点１の接続情報は「ｎｕｌｌ（空白）」なので、この先には、別の部分パスｅが接続されていないことがわかる。一方、部分パスｅ１から部分パスｅ３に進んだときに、その先に接続されている部分パスｅを求めるには、部分パスｅ３の端点１を参照することになる。この場合には、部分パスｅ３の端点１の接続情報は「ｅ４，ｅ５」なので、この先には、別の部分パスｅ４，ｅ５が接続されていることがわかる。つまり、図３に示した情報テーブル３００では、部分パスｅを連結したルートを探索する際には、「端点２」→「端点１」→「端点２」…のように端点１と端点２とを交互に参照する。例えば「着目している部分パスｅの端点２」、「この端点２に接続された部分パスｅの端点１」、「この端点１に接続された部分パスｅの端点２」のような順序で参照することになる。

図２に戻って、信号転送可能時間帯算出装置１３０の構成の説明を続ける。
ＣＰＵ２４０は、前記した入出力手段２１０、ＲＡＭ２２０およびＨＤＤ２３０を制御すると共に、各エッジ装置ｒから出力される信号の転送時間帯を算出し、各エッジ装置ｒに信号出力タイミングを割り当てて入出力手段２１０に出力するものである。このために、ＣＰＵ２４０は、図２に示すように、通過時刻算出手段２４１と、タイミング算出手段２４３と、転送制御手段２４５とを含んで構成されている。

通過時刻算出手段２４１は、詳細は後記するが、ＨＤＤ２３０に記憶された遅延時間２３１と、接続情報２３３と、信号出力時間２３５とに基づいて、分岐ノードｎを、各エッジ装置ｒから出力される信号が通過する際の信号通過開始時刻Ｃ（ｒ）および信号通過終了時刻Ｄ（ｒ）を算出し、タイミング算出手段２４３に出力するものである。

タイミング算出手段２４３は、詳細は後記するが、通過時刻算出手段２４１で算出された信号通過開始時刻Ｃ（ｒ）および信号通過終了時刻Ｄ（ｒ）に基づいて、選択された所定のエッジ装置ｒとは別のエッジ装置ｒ′から出力される信号の信号通過開始時刻Ｃ（ｒ′）と所定の時間間隔β（ｒ′）との和である時刻が、所定のエッジ装置ｒから出力される信号の信号通過終了時刻Ｄ（ｒ）に連続するような部分パスｅを１つ以上設けるように、時間間隔β（ｒ′）を算出するものである。このタイミング算出手段２４３は、前記した時間間隔β（ｒ′）を算出する際に、すべてのエッジ装置ｒから出力される信号が、各部分パスｅ上の同方向かつ同位置を同時刻に通過しないように、時間間隔β（ｒ′）を算出する。そして、このようにして求めた時間間隔β（ｒ′）と信号出力時間２３５とに基づいて、各エッジ装置ｒにおける信号出力タイミングを算出し、転送制御手段２４５に出力する。

転送制御手段２４５は、タイミング算出手段２４３によって算出された転送タイミングを入出力手段２１０を介して各エッジ装置ｒに通知することにより、各エッジ装置ｒから出力される信号の転送を制御するものである。

［信号転送可能時間帯算出装置の動作］
次に、本発明の第１の実施形態に係る信号転送可能時間帯算出装置１３０の動作について図４を参照（適宜図２参照）して説明する。図４は、図２に示した信号転送可能時間帯算出装置１３０のＣＰＵ２４０の処理を示すメインフローチャートである。
まず、ＣＰＵ２４０は、入出力手段２１０によって、外部装置から遅延時間２３１および接続情報２３３を取得すると共に、部分パスｅ０を介して各エッジ装置ｒから信号出力時間ｓ（ｒ）を取得し（ステップＳ１：情報取得ステップ）、取得した各情報をＨＤＤ２３０に格納する。

次に、ＣＰＵ２４０は、通過時刻算出手段２４１によって、後記する通過時刻算出処理を実行する（ステップＳ２：通過時刻算出ステップ）。ここで、通過時刻算出手段２４１は、各エッジ装置ｒから出力される信号が通過する部分パスｅの始点において、信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）を求め、タイミング算出手段２４３に出力する。

続いて、ＣＰＵ２４０は、タイミング算出手段２４３によって、信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）と、ステップＳ１で取得した信号出力時間ｓ（ｒ）とに基づいて、後記するタイミング算出処理を実行する（ステップＳ３：タイミング算出ステップ）。ここで、タイミング算出手段２４３は、各エッジ装置ｒから出力される信号の信号転送時間帯を決定し、転送制御手段２４５に出力する。
最後に、ＣＰＵ２４０は、転送制御手段２４５によって、信号転送時間帯に基づいて、各エッジ装置ｒに信号出力タイミングを通知する（ステップＳ４）。

次に、前記したステップＳ２の通過時刻算出処理について図５を参照（適宜図２および図３参照）して説明する。図５は、図４に示した通過時刻算出処理を示すフローチャートである。ここで、説明を簡便にするため、以下では、信号出力時間２３５は、信号出力継続時間とし、すべてのエッジ装置ｒの個々の信号出力時間ｓ（ｒ）はすべて「１」とする。

まず、ＣＰＵ２４０の通過時刻算出手段２４１は、エッジ装置ｒを選択する（ステップＳ１１）。そして、通過時刻算出手段２４１は、選択したエッジ装置ｒを始点（例えば端点１）とする部分パスｅの終点（例えば端点２）を始点（例えば端点２）とする部分パスを「ｅ′」とする（ステップＳ１２）。そして、通過時刻算出手段２４１は、部分パスｅ′の始点に関連付けて信号通過開始時刻Ｃ（ｒ，ｅ′）および信号通過終了時刻Ｄ（ｒ，ｅ′）を次式（１）および（２）で求める（ステップＳ１３）。
Ｃ（ｒ，ｅ′）＝ｄ（ｅ） …（１）
Ｄ（ｒ，ｅ′）＝ｄ（ｅ）＋ｓ（ｒ） …（２）
なお、部分パスｅ′が複数ある場合にはそれぞれ求める。

続けて、通過時刻算出手段２４１は、部分パスｅ′の終点を始点とする部分パスｅ″が存在するか否かを判定する（ステップＳ１４）。部分パスｅ″が存在する場合（ステップＳ１４：Ｙｅｓ）、通過時刻算出手段２４１は、部分パスｅ″の始点に関連付けて信号通過開始時刻Ｃ（ｒ，ｅ″）および信号通過終了時刻Ｄ（ｒ，ｅ″）を次式（３）および（４）で求める（ステップＳ１５）。
Ｃ（ｒ，ｅ″）＝Ｃ（ｒ，ｅ′）＋ｄ（ｅ′） …（３）
Ｄ（ｒ，ｅ″）＝Ｄ（ｒ，ｅ′）＋ｄ（ｅ′） …（４）
なお、部分パスｅ″が複数ある場合にはそれぞれ求める。

続けて、通過時刻算出手段２４１は、部分パスｅ″の終点を始点とする部分パスが存在するか否かを判定する（ステップＳ１６）。部分パスｅ″の終点を始点とする部分パスが存在する場合（ステップＳ１６：Ｙｅｓ）、通過時刻算出手段２４１は、ｅ′：＝ｅ″として（ステップＳ１７）、ステップＳ１４に戻る。なお、「ｅ′：＝ｅ″」は、これまでの部分パス「ｅ″」をあらためて部分パス「ｅ′」に置き換えて取り扱うことを意味する。

一方、部分パスｅ″の終点を始点とする部分パスが存在しない場合（ステップＳ１６：Ｎｏ）、および、部分パスｅ″が存在しない場合（ステップＳ１４：Ｎｏ）、通過時刻算出手段２４１は、すべてのエッジ装置ｒを選択したか否かを判定する（ステップＳ１８）。すべてのエッジ装置ｒを選択した場合（ステップＳ１８：Ｙｅｓ）、通過時刻算出手段２４１は、通過時刻算出処理を終了し、各エッジ装置ｒから出力される信号の各部分パスｅの始点における信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）をタイミング算出手段２４３に出力する。一方、すべてのエッジ装置ｒを選択していない場合（ステップＳ１８：Ｎｏ）、通過時刻算出手段２４１は、ステップＳ１１に戻る。

次に、前記したステップＳ２の通過時刻算出処理を、図１に示したネットワークシステム１００に適用した処理結果を図６を参照（適宜図１および図３参照）して説明する。図６は、図５に示した通過時刻算出処理の処理結果を示す説明図であり、（ａ）はエッジ装置（ｒ＝１）のスロットパターン、（ｂ）はエッジ装置（ｒ＝２）のスロットパターン、（ｃ）はエッジ装置（ｒ＝３）のスロットパターン、（ｄ）はエッジ装置（ｒ＝４）のスロットパターンを示している。

エッジ装置１１０（ｒ＝１）のスロットパターンを示した図６の（ａ）を参照して説明する。この表は、各部分パスｅの始点における信号通過開始時刻Ｃ（１，ｅ）および信号通過終了時刻Ｄ（１，ｅ）を示すものである。この表には、縦に、各部分パスｅの上り方向および下り方向を示すスロット６０１が示されており、横に、時間ｔを示すフレーム６０２が示されている。なお、フレーム６０２内の数値はフレーム右端の数値を示している。例えばスロットが「１→１０」、フレームが「ｔ＝０〜１」の場合、この表には「１」が記載されている（信号出力時間ｓ（ｒ）＝１なので実際には「１１１１」と記載）。これは、エッジ装置（ｒ＝１）が出力した光信号が、部分パスｅ１の始点において、エッジ装置（ｒ＝１）から分岐ノード（ｎ＝１０）に向けた方向で、「ｔ＝０〜１」の間で出力されたことを示している。

また、スロットが「１０→２」、フレームが「ｔ＝１〜２」の場合、表中に「１」が記載されている。これは、エッジ装置（ｒ＝１）が出力した光信号が、部分パスｅ２の始点において、分岐ノード（ｎ＝１０）からエッジ装置（ｒ＝２）に向けた方向で、「ｔ＝１〜２」の間で通過したことを示している。このとき、この光信号が部分パスｅ１を通過する際に遅延時間ｄ（ｅ１）＝１が生じている。この遅延時間ｄ（ｅ１）が表中の矢印６０３で示されている。

さらに、スロットが「１０→１１」、フレームが「ｔ＝１〜２」の場合、表中に「１」が記載されており、これは、分岐ノード（ｎ＝１０）で光信号が分岐ノード（ｎ＝１１）に向けて分岐したことを表している。分岐ノード（ｎ＝１１）に向けて分岐した光信号が部分パスｅ３を通過する際に遅延時間ｄ（ｅ３）＝１．５が生じる。この遅延時間ｄ（ｅ３）が表中の矢印６０４で示されている。したがって、例えばスロットが「１１→３」、フレームが「ｔ＝２．５〜３．５」の場合に記載されている「１」は、エッジ装置（ｒ＝１）から出力された光信号が部分パスｅ４の始点において、信号通過開始時刻Ｃ（１，ｅ４［11→3]）＝２．５と、信号通過終了時刻Ｄ（１，ｅ４［11→3］）＝３．５とを有することを示す。なお、ｅ［→］は部分パスｅにおける方向を示す。

図６の（ｂ）、（ｃ）および（ｄ）は、それぞれのエッジ装置（ｒ＝２，３，４）から出力される光信号の各部分パスｅにおける信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）を示すものである。各エッジ装置ｒはｔ＝０で光信号の出力を開始する。また、「２（２２２２）」，「３（３３３３）」，「４（４４４４）」は、それぞれｒ＝２，３，４のエッジ装置が出力する光信号を示している。

次に、図４に示した信号転送可能時間帯算出装置１３０のＣＰＵ２４０の処理におけるステップＳ３のタイミング算出処理について図７を参照（適宜図１および図２参照）して説明する。図７は、図４に示したタイミング算出処理を示すフローチャートである。
まず、ＣＰＵ２４０のタイミング算出手段２４３は、第１のエッジ装置ｒを選択し、他のエッジ装置と組み合わせることを決定し（以下、選択決定と呼ぶ）、選択決定した第１のエッジ装置ｒのタイミング変数Ａ（ｒ），Ｂ（ｒ）を次式（５）および（６）で求める（ステップＳ２１）。ここで、第１のエッジ装置ｒは、例えば一様分布などの確率分布、または、予め定められている重みｈ（ｒ）に従って選択される。また、タイミング変数Ａ（ｒ），Ｂ（ｒ）は、それぞれ、各エッジ装置ｒにおける信号出力開始時刻および信号出力終了時刻（信号出力タイミング）を示すものである。
Ａ（ｒ）＝０ …（５）
Ｂ（ｒ）＝ｓ（ｒ）…（６）

そして、タイミング算出手段２４３は、第１のエッジ装置ｒを選択決定したときと同様に、例えば一様分布などの確率分布、または、予め定められている重みｈ（ｒ）に従って、まだ選択決定していない別のエッジ装置ｒ′を選択決定する（ステップＳ２２）。
そして、タイミング算出手段２４３は、後記する時間間隔算出処理を実行する（ステップＳ２３）。これにより、ステップＳ２２で選択決定したエッジ装置ｒ′から出力される信号の信号通過開始時刻Ｃ（ｒ′）に所定の時間間隔β（ｒ′）を加算した時刻が、ステップＳ２２の前にすでに選択決定されているエッジ装置ｒから出力される信号の信号通過終了時刻Ｄ（ｒ）に連続するような部分パスｅを１つ以上設けるように、かつ、選択決定されたすべてのエッジ装置ｒから出力される信号が、各部分パスｅ上の同方向かつ同位置を同時刻に通過しないように、所定の時間間隔β（ｒ′）が算出される。

そして、タイミング算出手段２４３は、信号通過開始時刻Ｃ（ｒ′，ｅ）および信号通過終了時刻Ｄ（ｒ′，ｅ）を次式（７）および（８）に従って書き換えると共に、エッジ装置ｒ′のタイミング変数Ａ（ｒ′），Ｂ（ｒ′）を次式（９）および（１０）で求める（ステップＳ２４）。
Ｃ（ｒ′，ｅ）：＝Ｃ（ｒ′，ｅ）＋β（ｒ′） …（７）
Ｄ（ｒ′，ｅ）：＝Ｄ（ｒ′，ｅ）＋β（ｒ′） …（８）
Ａ（ｒ′）＝β（ｒ′） …（９）
Ｂ（ｒ′）＝ｓ（ｒ′）＋β（ｒ′）…（１０）
これにより、すでに選択決定されたエッジ装置ｒから出力される光信号同士は、各部分パスｅ上の同方向かつ同位置を同時刻に通過することがなくなる。

そして、タイミング算出手段２４３は、すべてのエッジ装置ｒを選択決定したか否かを判定する（ステップＳ２５）。すべてのエッジ装置ｒを選択決定していない場合（ステップＳ２５：Ｎｏ）、タイミング算出手段２４３は、ステップＳ２２に戻る。一方、すべてのエッジ装置ｒを選択決定した場合（ステップＳ２５：Ｙｅｓ）、タイミング算出手段２４３は、ステップＳ２１で選択決定した第１のエッジ装置ｒをあらためてｒ′として選択決定する（ステップＳ２６）。

そして、タイミング算出手段２４３は、再び、時間間隔算出処理を実行し（ステップＳ２７）、求めた所定の時間間隔β（ｒ′）をΔとする（ステップＳ２８）。これにより、すべてのエッジ装置ｒから、信号出力時間ｓ（ｒ）の光信号を時間間隔Δを周期として連続して出力可能とする信号転送可能時間帯を決定することができる。
そして、タイミング算出手段２４３は、すべてのエッジ装置ｒのＡ（ｒ）、Ｂ（ｒ）、Ｃ（ｒ，ｅ）、Ｄ（ｒ，ｅ）およびΔを転送制御手段２４５およびＨＤＤ２３０に出力する（ステップＳ２９）。
そして、転送制御手段２４５は、すべてのエッジ装置ｒのＡ（ｒ）、Ｂ（ｒ）、Ｃ（ｒ，ｅ）、Ｄ（ｒ，ｅ）およびΔに基づいた転送タイミングを入出力手段２１０を介して各エッジ装置ｒに通知する。各エッジ装置ｒは、通知された転送タイミングをそれぞれ記憶して、記憶された転送タイミングに基づいて光信号を出力することとなる。

次に、前記したステップＳ２３およびステップＳ２７の時間間隔算出処理について図８を参照（適宜図２および図７参照）して説明する。図８は、図７に示した時間間隔算出処理を示すフローチャートである。
まず、タイミング算出手段２４３は、この時間間隔算出処理の前に選択決定したエッジ装置ｒ′について、次式（１１）で表される時間間隔と、すでに選択決定されているすべてのエッジ装置ｒに関する次式（１２）で表される時間間隔との重なりが、すべての部分パスｅで生じないように所定時間間隔β（ｒ′）を求める（ステップＳ３１）。
｛Ｃ（ｒ′，ｅ）＋β（ｒ′）｝≦ｔ≦｛Ｄ（ｒ′，ｅ）＋β（ｒ′）｝ …（１１）
Ｃ（ｒ，ｅ）≦ｔ≦Ｄ（ｒ，ｅ） …（１２）

次に、タイミング算出手段２４３は、エッジ装置ｒ′に関して信号通過開始時刻Ｃ（ｒ′，ｅ）および信号通過終了時刻Ｄ（ｒ′，ｅ）を仮に次式（１３）および（１４）によって変更する。
Ｃ（ｒ′，ｅ）＋β（ｒ′） …（１３）
Ｄ（ｒ′，ｅ）＋β（ｒ′） …（１４）
そして、この仮に変更された信号通過開始時刻｛Ｃ（ｒ′，ｅ）＋β（ｒ′）｝と、すでに選択決定されているいずれかのエッジ装置ｒの信号通過終了時刻Ｄ（ｒ，ｅ）とが等しくなる部分パスｅが存在するときの時間間隔β（ｒ′）を抽出する。この抽出された時間間隔β（ｒ′）のうち、仮に変更された信号通過終了時刻｛Ｄ（ｒ′，ｅ）＋β（ｒ′）｝の最大値が最小となる時間間隔β（ｒ′）を求める（以上ステップＳ３２）。

次に、図７に示したタイミング算出処理の処理過程および処理結果の具体例について図９および図１０を参照（適宜図６乃至図８参照）して説明する。図９は図８に示した時間間隔算出処理の処理過程を示す説明図であり、図１０は図７に示したタイミング算出処理の処理結果を示す説明図である。

図９に示す表では、タイミング算出手段２４３がエッジ装置ｒ′をランダムに選択し、（ｒ＝２）、（ｒ＝３）、（ｒ＝１）、（ｒ＝４）の順番に選択決定して、図６の（ａ）〜（ｄ）に示したスロットパターンが重ならないようにずらして配置した状態が示されている。

まず、エッジ装置（ｒ＝２）が選択決定されており、図８のステップＳ３２におけるＤ（ｒ，ｅ）の候補が探索される。次に、エッジ装置（ｒ＝３）が選択決定されており、ステップＳ３２における｛Ｃ（ｒ′，ｅ）＋β（ｒ′）｝の候補が探索される。この場合、β（３）＝−０．２５とすれば、次式（１５）が成り立つ部分パスｅ（ｅ１）が存在することになる。
Ｃ（３，ｅ）＋β（３）＝Ｄ（２，ｅ） …（１５）

すなわち、図９において矢印９０１で指し示すポイントでは、スロット「１０→１」において、エッジ装置（ｒ＝２）から出力される光信号「２」と、エッジ装置（ｒ＝３）から出力される光信号「３」とが連続して配置されることになる。同様にして、ｒ＝１、ｒ＝４のエッジ装置のスロットパターンを続けてずらして重ね、その結果の最左端をフレーム１（ｔ＝０）に合わせると図９に示した状態となる。

これによれば、符号９０２で示したスロット「１→１０」における光信号「１」、符号９０３で示したスロット「３→１１」における光信号「３」、符号９０４で示したスロット「２→１０」における光信号「２」、符号９０５で示したスロット「４→１１」における光信号「４」を、表に示されたフレームタイミングで通過させれば、各光信号は、各部分パスｅ上の同方向かつ同位置を同時刻に通過することがないことが理解される。

さらに、タイミング算出手段２４３がエッジ装置ｒをすべて選択決定した後、再び、最初に選択決定したｒ＝２のエッジ装置をｒ′として選択決定してβ（ｒ′）＝Δを求め、エッジ装置ｒのＡ（ｒ）、Ｂ（ｒ）と共に出力した結果を、図１０の表に示す。
図１０に示すように、符号１００１で示されるスロット「１→１０」において、符号１００２で示されるフレーム「ｔ＝０〜１」で光信号「１」が出力されている。

一方、時間間隔算出処理（ステップＳ２７）においてΔ＝６であることが分かるので、符号１００１で示されるスロット「１→１０」において、符号１００３で示されるフレーム「ｔ＝６〜７」で光信号「１」が出力される。
すべてのタイミング算出処理結果をまとめると、エッジ装置（ｒ＝１）は、式（１６）で示される時刻Ｔ_Sに光信号の出力を開始し、式（１７）で示される時刻Ｔ_Eに光信号の出力を終了すればよいこととなる。
Ｔ_S（１）＝Ａ（１）＋ｋΔ （ｋ＝０，１，２，…） …（１６）
Ｔ_E（１）＝Ｂ（１）＋ｋΔ （ｋ＝０，１，２，…） …（１７）
さらに、式（１６）および式（１７）を、すべてのエッジ装置ｒに対して一般化すると、式（１８）および式（１９）が得られる。
Ｔ_S（ｒ）＝Ａ（ｒ）＋ｋΔ （ｋ＝０，１，２，…） …（１８）
Ｔ_E（ｒ）＝Ｂ（ｒ）＋ｋΔ （ｋ＝０，１，２，…） …（１９）

なお、信号転送可能時間帯算出装置１３０は、一般的なコンピュータに、前記した各ステップを実行させるための信号転送可能時間帯算出プログラムを実行することで実現することもできる。この信号転送可能時間帯算出プログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体に書き込んで配布することも可能である。この記録媒体を読み取り可能な情報処理装置は、信号転送可能時間帯算出プログラムに基づいた各機能を実現することができる。

第１の実施形態の信号転送可能時間帯算出装置１３０によれば、各エッジ装置ｒから出力される光信号が相互干渉することがないので、信号の衝突を防止することができる。また、信号転送可能時間帯算出装置１３０が記憶する接続情報として、部分パスｅ同士の接続関係のみを用いたので、どのノードｎを通過するかに関する情報を省略して記憶データ量を低減できる。また、タイミング算出手段２４３は、選択すべきエッジ装置ｒをランダムに選択するので、計算量を抑制し、転送可能時間帯を迅速に算出できる。

（第２の実施形態）
前記した第１の実施形態では、通過時刻算出手段２４１の実行する通過時刻算出処理において、信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）を部分パスｅの始点に関連付けることとしたが、関連付けるポイントは部分パスｅの始点に限定されるものではない。以下に、部分パスｅの終点に関連付ける実施形態を第２の実施形態として説明する。

第２の実施形態の信号転送可能時間帯算出装置は、通過時刻算出処理（図５参照）のアルゴリズムが異なる点を除いて、図２に示した信号転送可能時間帯算出装置１３０と同じ構成なので、図面を省略し、図２と同じ構成には同じ符号を付して説明を省略する。
次に、本発明の第２の実施形態に係る信号転送可能時間帯算出装置の行う通過時刻算出処理について図１１を参照して説明する。図１１は、本発明の第２の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行する通過時刻算出処理を示すフローチャートである。なお、信号出力時間２３５は、信号出力継続時間とし、すべてのエッジ装置ｒの信号出力時間ｓ（ｒ）はすべて「１」とする。

まず、ＣＰＵ２４０の通過時刻算出手段２４１は、エッジ装置ｒを選択する（ステップＳ４１）。そして、通過時刻算出手段２４１は、選択したエッジ装置ｒを始点とする部分パスｅ′の終点に関連付けて信号通過開始時刻Ｃ（ｒ，ｅ′）および信号通過終了時刻Ｄ（ｒ，ｅ′）を前記した式（１）および（２）で求める（ステップＳ４２）。
なお、部分パスｅ′が複数ある場合にはそれぞれ求める。

続けて、通過時刻算出手段２４１は、部分パスｅ′の終点を始点とする部分パスｅ″が存在するか否かを判定する（ステップＳ４３）。部分パスｅ″が存在する場合（ステップＳ４３：Ｙｅｓ）、通過時刻算出手段２４１は、部分パスｅ″の終点に関連付けて信号通過開始時刻Ｃ（ｒ，ｅ″）および信号通過終了時刻Ｄ（ｒ，ｅ″）を次式（２０）および（２１）で求める（ステップＳ４４）。
Ｃ（ｒ，ｅ″）＝Ｃ（ｒ，ｅ′）＋ｄ（ｅ″） …（２０）
Ｄ（ｒ，ｅ″）＝Ｄ（ｒ，ｅ′）＋ｄ（ｅ″） …（２１）
なお、部分パスｅ″が複数ある場合にはそれぞれ求める。

続けて、通過時刻算出手段２４１は、部分パスｅ″の終点を始点とする部分パスが存在するか否かを判定する（ステップＳ４５）。部分パスｅ″の終点を始点とする部分パスが存在する場合（ステップＳ４５：Ｙｅｓ）、通過時刻算出手段２４１は、これまでの部分パス「ｅ″」をあらためて部分パス「ｅ′」に置き換え（ステップＳ４６）、ステップＳ４３に戻る。

一方、部分パスｅ″の終点を始点とする部分パスが存在しない場合（ステップＳ４５：Ｎｏ）、および、部分パスｅ″が存在しない場合（ステップＳ４３：Ｎｏ）、通過時刻算出手段２４１は、すべてのエッジ装置ｒを選択したか否かを判定する（ステップＳ４７）。すべてのエッジ装置ｒを選択した場合（ステップＳ４７：Ｙｅｓ）、通過時刻算出手段２４１は、通過時刻算出処理を終了し、各エッジ装置ｒから出力される信号の各部分パスｅの終点における信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）をタイミング算出手段２４３に出力する。一方、すべてのエッジ装置ｒを選択していない場合（ステップＳ４７：Ｎｏ）、通過時刻算出手段２４１は、ステップＳ４１に戻る。

次に、図１２を参照して第２の実施形態の効果を説明する。図１２は、図１１に示したフローチャートを説明するための説明図であり、（ａ）は比較例、（ｂ）は第２の実施形態を示している。図１２では、図１に示したネットワークシステム１００が簡略化されて示されている。図１２の（ａ）に示した比較例では、信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）を部分パスｅの始点に関連付けることを特徴とし、一方、図１２の（ｂ）に示した第２の実施形態では、部分パスｅの終点に関連付けることを特徴としている。本発明では、ツリー構造のネットワークについて、基準とする部分パスｅに接続している部分パスｅ′を新たに見つけた場合、その新たな部分パスｅ′をあらためて基準とする部分パスｅに置き換えて利用することにより、経路探索を実行することとしている。このとき、部分パスｅにおける遅延時間ｄ（ｅ）を考慮すると、図１２の（ａ）の比較例では、変数として、ｅ，ｅ′，ｅ″の３種類が必要となる。一方、図１２の（ｂ）の第２の実施形態では、変数として、ｅ′，ｅ″の２種類で済むこととなる。

（第３の実施形態）
前記した第１の実施形態では、タイミング算出手段２４３の実行するタイミング算出処理において、所定のエッジ装置ｒに対して別のエッジ装置ｒ′をランダムに選択決定した状態で所定の時間間隔β（ｒ′）を求める（以下、ランダム方式という）こととしたが、所定のエッジ装置ｒに対して別のエッジ装置ｒ′を選択決定する方式は、ランダム方式に限定されるものではない。以下に、最適な組み合わせを見つける方式（以下、ｇｒｅｅｄｙ方式という）を第３の実施形態として説明する。

第３の実施形態の信号転送可能時間帯算出装置は、タイミング算出処理（図７参照）のアルゴリズムが異なる点を除いて、図２に示した信号転送可能時間帯算出装置１３０と同じ構成なので、図面を省略し、図２と同じ構成には同じ符号を付して説明を省略する。
次に、本発明の第３の実施形態に係る信号転送可能時間帯算出装置の行うタイミング算出処理について図１３を参照（適宜図２参照）して説明する。図１３は、本発明の第３の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行するタイミング算出処理を示すフローチャートである。

まず、ＣＰＵ２４０のタイミング算出手段２４３は、第１のエッジ装置ｒを選択決定し、選択決定した第１のエッジ装置ｒのタイミング変数Ａ（ｒ），Ｂ（ｒ）を前記した式（５）および式（６）で求める（ステップＳ５１）。ここで、第１のエッジ装置ｒは、例えば一様分布などの確率分布、または、予め定められている重みｈ（ｒ）に従って選択される。
そして、タイミング算出手段２４３は、第１のエッジ装置ｒを選択決定する際と同様に、例えば一様分布などの確率分布、または、予め定められている重みｈ（ｒ）に従って、まだ選択決定していない別のエッジ装置ｒ′を選択する（選択決定はしない）（ステップＳ５２）。

そして、タイミング算出手段２４３は、前記した時間間隔算出処理を実行する（ステップＳ５３）。これにより、ステップＳ５２で選択したエッジ装置ｒ′から出力される信号の信号通過開始時刻Ｃ（ｒ′，ｅ）に所定の時間間隔β（ｒ′）を加算した時刻が、ステップＳ５２の前にすでに選択決定されているエッジ装置ｒから出力される信号の信号通過終了時刻Ｄ（ｒ，ｅ）に連続するような部分パスｅを１つ以上設けるように、かつ、選択決定されたすべてのエッジ装置ｒから出力される信号が、各部分パスｅ上の同方向かつ同位置を同時刻に通過しないように、所定の時間間隔β（ｒ′）が算出される。

次に、タイミング算出手段２４３は、まだ選択決定していない別のエッジ装置ｒ′をすべて選択したか否かを判定する（ステップＳ５４）。まだ選択決定していない別のエッジ装置ｒ′をすべて選択していない場合（ステップＳ５４：Ｎｏ）、タイミング算出手段２４３は、ステップＳ５２に戻る。一方、まだ選択決定していない別のエッジ装置ｒ′をすべて選択した場合（ステップＳ５４：Ｙｅｓ）、タイミング算出手段２４３は、ステップＳ５５に進む。

このステップＳ５５に進んだ状態では、すでに選択決定されているエッジ装置ｒに対して、選択決定されていないすべての別のエッジ装置ｒ′が組み合わせる候補として挙げられていることになる。そして、前記した式（１３）および（１４）に示されるように、信号通過開始時刻Ｃ（ｒ′，ｅ）および信号通過終了時刻Ｄ（ｒ′，ｅ）を仮に変更している。また、β（ｒ′）も候補の数だけ存在している。
そこで、タイミング算出手段２４３は、求めた時間間隔β（ｒ′）のうち、仮に変更された信号通過終了時刻｛Ｄ（ｒ′，ｅ）＋β（ｒ′）｝の最大値が最小となるエッジ装置ｒ′を選択決定する。このとき、タイミング算出手段２４３は、選択決定したエッジ装置ｒ′に対して、仮変更だった信号通過開始時刻Ｃ（ｒ′，ｅ）および信号通過終了時刻Ｄ（ｒ′，ｅ）を前記した式（７）および（８）に従って書き換える（正式に変更する）と共に、エッジ装置ｒ′のタイミング変数Ａ（ｒ′），Ｂ（ｒ′）を前記した式（９）および（１０）で求める。
これにより、すでに選択決定されたエッジ装置ｒから出力される光信号同士は、各部分パスｅ上の同方向かつ同位置を同時刻に通過することがなくなる。

ステップＳ５５に続けて、タイミング算出手段２４３は、すべてのエッジ装置ｒを選択決定したか否かを判定する（ステップＳ５６）。すべてのエッジ装置ｒを選択決定していない場合（ステップＳ５６：Ｎｏ）、タイミング算出手段２４３は、ステップＳ５２に戻る。一方、すべてのエッジ装置ｒを選択決定した場合（ステップＳ５６：Ｙｅｓ）、タイミング算出手段２４３は、ステップＳ５７〜ステップＳ６０の処理を実行する。このステップＳ５７〜ステップＳ６０の処理は、前記したステップＳ２６〜ステップＳ２９の処理と同一なので説明を省略する。

次に、前記したタイミング算出処理（図１３参照）の処理過程および処理結果の具体例について図１４乃至図１６を参照（適宜図６参照）して説明する。ここでは、図１３のフローチャートにおけるステップＳ５１で、タイミング算出手段２４３は、第１のエッジ装置ｒとして、ｒ＝１のエッジ装置を選択決定したものとする。この状態を図１４の（ａ）に示す。そして、タイミング算出手段２４３は、図１３のステップＳ５２〜ステップＳ５４を繰り返し実行することによって、ｒ′＝２，３，４を順次選択し、それぞれをｒ＝１のエッジ装置と仮に組み合わせる。このときの仮の組み合わせを、図１４の（ｂ），（ｃ）および（ｄ）にそれぞれ示す。

例えばｒ′＝２のエッジ装置をｒ＝１のエッジ装置と仮に組み合わせた場合、図１４の（ｂ）に示すように、所定間隔β（２）＝０．７５となる。また、Ｄ（２，ｅ）とβ（２）との和の最大値は、符号１４０１で示すように「４．５」となる。
また、ｒ′＝４のエッジ装置をｒ＝１のエッジ装置と仮に組み合わせた場合、図１４の（ｃ）に示すように、所定間隔β（４）＝０となる。また、Ｄ（４，ｅ）とβ（４）との和の最大値は、符号１４０２で示すように「３．５」となる。
同様に、ｒ′＝３のエッジ装置をｒ＝１のエッジ装置と仮に組み合わせた場合、図１４の（ｄ）に示すように、所定間隔β（３）＝０となる。また、Ｄ（３，ｅ）とβ（３）との和の最大値は、符号１４０３で示すように「３．５」となる。

これらをまとめると、Ｄ（ｒ′，ｅ）とβ（ｒ′）との和の最大値（４，５，３．５，３．５）のうち、最小となるのは「３．５」の場合である。このようになるのは、ｒ′＝３のエッジ装置の場合と、ｒ′＝４のエッジ装置の場合がある。どちらでも同等なので、ここでは、ｒ′＝３のエッジ装置を選択決定することとする。なお、このとき、ｒ′＝３のエッジ装置に対して、前記した式（７）〜（１０）が適用される。

この状態では、すべてのエッジ装置ｒのうち、２つのエッジ装置（ｒ＝１，３）が選択決定されたこととなるので、次に選択決定すべきエッジ装置ｒ′の候補を探索すべく同様な操作（ステップＳ５２〜ステップＳ５５）を実行する。すなわち、図１５の（ａ）に示す状態を基本にして、ｒ′＝２，４を順次選択し、それぞれをｒ＝１，３のエッジ装置と仮に組み合わせる。このときの仮の組み合わせを、図１５の（ｂ）および（ｃ）にそれぞれ示す。

例えばｒ′＝２のエッジ装置をｒ＝１，３のエッジ装置と仮に組み合わせた場合、図１５の（ｂ）に示すように、所定間隔β（２）＝２．２５となる。また、Ｄ（２，ｅ）とβ（２）との和の最大値は、符号１５０１で示すように「６」となる。
また、ｒ′＝４のエッジ装置をｒ＝１，３のエッジ装置と仮に組み合わせた場合、図１５の（ｃ）に示すように、所定間隔β（４）＝２．５となる。また、Ｄ（４，ｅ）とβ（４）との和の最大値は、符号１５０２で示すように「６」となる。

つまり、Ｄ（ｒ′，ｅ）とβ（ｒ′）との和の最大値（６，６）のうち、最小となるのは「６」の場合である。このようになるのは、ｒ′＝２のエッジ装置の場合と、ｒ′＝４のエッジ装置の場合がある。どちらでも同等なので、ここでは、ｒ′＝２のエッジ装置を選択決定することとする。なお、このとき、ｒ′＝２のエッジ装置に対して、前記した式（７）〜（１０）が適用される。

この状態では、すべてのエッジ装置ｒのうち、３つのエッジ装置（ｒ＝１，３，２）が選択決定されたこととなるので、次に選択決定すべきエッジ装置は、ｒ′＝４のエッジ装置である。これに対して同様な操作（ステップＳ５２〜ステップＳ５５）を実行した場合には、図１６の（ａ）に示すように、所定間隔β（４）＝２．５となる。また、Ｄ（４，ｅ）とβ（４）との和の最大値は、６となる。

図１６の（ａ）に示すように、符号１６０１で示したスロット「１→１０」における光信号「１」と、符号１６０２で示したスロット「３→１１」における光信号「３」とをｔ＝０のタイミングで、符号１６０３で示したスロット「２→１０」における光信号「２」をｔ＝２．２５で、符号１６０４で示したスロット「４→１１」における光信号「４」をｔ＝２．５のタイミングでそれぞれ出力させれば、各光信号は、各部分パスｅ上の同方向かつ同位置を同時刻に通過することがないことが理解される。

さらに、第１のエッジ装置ｒとして選択決定した、ｒ＝１のエッジ装置を次に選択すべきエッジ装置ｒ′と置き換えて、時間間隔算出処理（ステップＳ５８）を実行すると、図１６の（ｂ）に示すように、所定間隔β（１）＝Δ＝５となる。また、Ｄ（１，ｅ）とβ（１）との和の最大値は「６」となる。

図１６の（ｂ）に示すように、符号１６０１で示されるスロット「１→１０」において、符号１６０５で示されるフレーム「ｔ＝０〜１」で光信号「１」が出力される。一方、時間間隔算出処理（ステップＳ５８）においてΔ＝５であることが分かるので、符号１６０１で示されるスロット「１→１０」において、符号１６０６で示されるフレーム「ｔ＝５〜６」で光信号「１」が出力される。なお、すべてのエッジ装置ｒは、前記した式（１８）で示される時刻Ｔ_S（ｒ）に光信号の出力を開始し、前記した式（１９）で示される時刻Ｔ_E（ｒ）に光信号の出力を終了する。

第３の実施形態によれば、タイミング算出処理を実行する際に、最適な組み合わせを抽出してエッジ装置ｒ′を選択決定するので、各エッジ装置ｒから出力される光信号の転送時間帯を最も効率よいものとすることができる。つまり、この方式（ｇｒｅｅｄｙ方式）の処理結果（Δ＝５）によれば、図１０に示したランダム方式の処理結果（Δ＝６）と比較して、Δを短くすることが可能である。

（第４の実施形態）
前記した第１乃至第３の実施形態では、通過時刻算出手段２４１の実行する通過時刻算出処理において、信号通過開始時刻Ｃ（ｒ）および信号通過終了時刻Ｄ（ｒ）を部分パスｅに関連付けることとした。以下に、ノードｎに関連付ける実施形態を第４の実施形態として説明する。

第４の実施形態の信号転送可能時間帯算出装置は、通過時刻算出処理（図５参照）のアルゴリズムが異なる点を除いて、図２に示した信号転送可能時間帯算出装置１３０と同じ構成なので、図面を省略し、図２と同じ構成には同じ符号を付して説明を省略する。
次に、本発明の第４の実施形態に係る信号転送可能時間帯算出装置の行う通過時刻算出処理について図１７を参照して説明する。図１７は、本発明の第４の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行する通過時刻算出処理を示すフローチャートである。なお、信号出力時間２３５は、信号出力継続時間とし、すべてのエッジ装置ｒの信号出力時間ｓ（ｒ）はすべて「１」とする。

まず、ＣＰＵ２４０の通過時刻算出手段２４１は、エッジ装置ｒを選択する（ステップＳ７１）。そして、通過時刻算出手段２４１は、選択したエッジ装置ｒを始点とする部分パスｅの終点であるノードをｎとする（ステップＳ７２）。そして、通過時刻算出手段２４１は、ノードｎに関連付けて信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）を次式（２２）および（２３）で求める（ステップＳ７３）。
Ｃ（ｒ，ｎ）＝ｄ（ｅ） …（２２）
Ｄ（ｒ，ｎ）＝ｄ（ｅ）＋ｓ（ｒ） …（２３）

続けて、通過時刻算出手段２４１は、ノードｎを始点とする部分パスｅ′が存在するか否かを判定する（ステップＳ７４）。部分パスｅ′が存在する場合（ステップＳ７４：Ｙｅｓ）、通過時刻算出手段２４１は、部分パスｅ′の終点のノードをｎ′として（ステップＳ７５）、ノードｎ′に関連付けて信号通過開始時刻Ｃ（ｒ，ｎ′）および信号通過終了時刻Ｄ（ｒ，ｎ′）を次式（２４）および（２５）で求める（ステップＳ７６）。
Ｃ（ｒ，ｎ′）＝Ｃ（ｒ，ｎ）＋ｄ（ｅ′） …（２４）
Ｄ（ｒ，ｎ′）＝Ｄ（ｒ，ｎ）＋ｄ（ｅ′） …（２５）
なお、ノードｎ′が複数ある場合にはそれぞれ求める。

続けて、通過時刻算出手段２４１は、ノードｎ′を始点とする部分パスが存在するか否かを判定する（ステップＳ７７）。ノードｎ′を始点とする部分パスが存在する場合（ステップＳ７７：Ｙｅｓ）、通過時刻算出手段２４１は、これまでのノード「ｎ′」をあらためてノード「ｎ」に置き換え（ステップＳ７８）、ステップＳ７４に戻る。

一方、ノードｎ′を始点とする部分パスが存在しない場合（ステップＳ７７：Ｎｏ）、および、ノードｎを始点とする部分パスｅ′が存在しない場合（ステップＳ７４：Ｎｏ）、通過時刻算出手段２４１は、すべてのエッジ装置ｒを選択したか否かを判定する（ステップＳ７９）。すべてのエッジ装置ｒを選択した場合（ステップＳ７９：Ｙｅｓ）、通過時刻算出手段２４１は、通過時刻算出処理を終了し、各エッジ装置ｒから出力される信号の各ノードｎにおける信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）をタイミング算出手段２４３に出力する。一方、すべてのエッジ装置ｒを選択していない場合（ステップＳ７９：Ｎｏ）、通過時刻算出手段２４１は、ステップＳ７１に戻る。

なお、前記した通過時刻算出処理のフローチャートにおいて、ステップＳ７１において選択したエッジ装置の識別変数「ｒ」を便宜上、ノードの識別変数「ｎ」に読み替えると共に、Ｃ（ｒ，ｎ）＝０，Ｄ（ｒ，ｎ）＝ｓ（ｒ）としてもよい。この場合の例えばＣ（ｒ，ｎ）の表記では、Ｃ（ｒ，ｎ）のカッコ内の「ｒ」は信号を出力するエッジ装置の識別変数、同じくカッコ内の「ｎ」は、部分パスｅの始点としてのノードの変数をそれぞれ示している。そして、このときの「ｎ」を始点とする部分パスｅの終点であるノードを「ｎ′」と読み替えることとする。この場合には、ノードｎ′に関連付けて信号通過開始時刻Ｃ（ｒ，ｎ′）および信号通過終了時刻Ｄ（ｒ，ｎ′）を前記した式（２４）および（２５）に代えて次式（２６）および（２７）で求めることができる。
Ｃ（ｒ，ｎ′）＝Ｃ（ｒ，ｎ）＋ｄ（ｅ） …（２６）
Ｄ（ｒ，ｎ′）＝Ｄ（ｒ，ｎ）＋ｄ（ｅ） …（２７）

次に、前記した通過時刻算出処理（図１７参照）を、図１に示したネットワークシステム１００に適用した処理結果を図１８を参照（適宜図１参照）して説明する。図１８は、図１７に示した通過時刻算出処理の処理結果を示す説明図であり、（ａ）はｒ＝１のスロットパターン、（ｂ）はｒ＝２のスロットパターン、（ｃ）はｒ＝３のスロットパターン、（ｄ）はｒ＝４のスロットパターンを示している。

エッジ装置（ｒ＝１）のスロットパターンを示した図１８の（ａ）を参照して説明する。この表は、各ノードｎ（エッジ装置、分岐ノードを含む）における信号通過開始時刻Ｃ（１，ｎ）および信号通過終了時刻Ｄ（１，ｎ）を示すものである。この表には、縦に、各ノードｎを示すスロット１８０１が示されており、横に、時間ｔを示すフレーム１８０２が示されている。例えばスロットが「１」、フレームが「ｔ＝０〜１」の場合、表中に「Ｘ」が記載されている（信号出力時間ｓ（ｒ）＝１なので実際には「ＸＸＸＸ」と記載）。これは、エッジ装置（ｒ＝１）が出力した光信号が、エッジ装置（ｒ＝１）において、「ｔ＝０〜１」の間で出力されたことを示している。

また、符号１８０３で示すスロット「１０」、符号１８０４で示すフレーム「ｔ＝１〜２」の場合、表中に「１」が記載されている（実際には「１１１１」と記載）。これは、エッジ装置（ｒ＝１）が出力した光信号が、部分パスｅ１を通過する際に遅延時間ｄ（ｅ１）＝１が生じたことを示している。同様に、スロットが「１１」、フレームが「ｔ＝２．５〜３．５」の場合、表中に「１」が記載されており、これは、エッジ装置（ｒ＝１）が出力した光信号が、部分パスｅ３を通過する際に遅延時間ｄ（ｅ３）＝１．５が生じたことを示している。

図１８の（ｂ）、（ｃ）および（ｄ）は、それぞれのエッジ装置（ｒ＝２，３，４）から出力される光信号の各ノードｎにおける信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）を示すものである。なお、各エッジ装置ｒはｔ＝０で光信号「Ｘ（ＸＸＸＸ）」の出力を開始し、「２（２２２２）」，「３（３３３３）」，「４（４４４４）」は、それぞれｒ＝２，３，４のエッジ装置が出力する光信号に遅延時間を含めて示すものである。

次に、図１８に示した信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）を用いたタイミング算出処理を説明する。
ランダム方式（図７参照）を適用する場合、図７に示すステップＳ２４のＣ（ｒ′，ｅ）をＣ（ｒ′，ｎ）に置き換えると共に、図８に示すステップＳ３１およびステップＳ３２のＣ（ｒ′，ｅ）およびＤ（ｒ′，ｅ）を、Ｃ（ｒ′，ｎ）およびＤ（ｒ′，ｎ）にそれぞれ置き換えた処理を実行することになる。

また、ｇｒｅｅｄｙ方式（図１３参照）を適用する場合、図１３に示すステップＳ５５のＣ（ｒ′，ｅ）をＣ（ｒ′，ｎ）に置き換えると共に、図８に示すステップＳ３１およびステップＳ３２のＣ（ｒ′，ｅ）およびＤ（ｒ′，ｅ）を、Ｃ（ｒ′，ｎ）およびＤ（ｒ′，ｎ）にそれぞれ置き換えた処理を実行することになる。

次に、ランダム方式（図７参照）またはｇｒｅｅｄｙ方式（図１３参照）を適用した場合の処理結果を図１９を参照して説明する。図１９は、図１８に示した通過時刻算出処理の結果を用いてタイミング算出処理を実行した場合の処理結果を示す説明図であり、（ａ）はランダム方式、（ｂ）はｇｒｅｅｄｙ方式を示している。

ランダム方式では、タイミング算出手段２４３はエッジ装置ｒ′をランダムに選択し、この例では（ｒ＝２）、（ｒ＝３）、（ｒ＝１）、（ｒ＝４）の順番に選択決定して、すべて選択決定した後、再び、ｒ＝２のエッジ装置ｒを選択決定してΔを求める。このときの処理結果を、図１９の（ａ）に示す。この図１９の（ａ）に示すように、符号１９０１で示されるスロット「１」において、符号１９０２で示されるフレーム「ｔ＝０〜１」で光信号「Ｘ」が出力されている。同様に、スロット「３」において、ｔ＝０．５のタイミングで光信号「Ｘ」が出力され、スロット「２」において、ｔ＝０．７５のタイミングで光信号「Ｘ」が出力され、スロット「４」において、ｔ＝３．５のタイミングで光信号「Ｘ」が出力されている。すなわち、エッジ装置ｒは、ｒ＝２，３，１，４の順番で光信号を出力する。
また、時間間隔算出処理（図８参照）においてΔ＝６であることが分かるので、符号１９０１で示されるスロット「１」において、符号１９０３で示されるフレーム「ｔ＝６〜７」で光信号「Ｘ」が出力される。

また、ｇｒｅｅｄｙ方式では、タイミング算出手段２４３はエッジ装置ｒ′を最適に選択して、（ｒ＝１）、（ｒ＝３）、（ｒ＝２）、（ｒ＝４）の順番に選択決定して、すべて選択した後、再び、ｒ＝１のエッジ装置ｒを選択決定してΔを求める。このときの処理結果を、図１９の（ｂ）に示す。この図１９の（ｂ）に示すように、符号１９０１で示されるスロット「１」において、符号１９０２で示されるフレーム「ｔ＝０〜１」で光信号「Ｘ」が出力されると共に、同じタイミングでスロット「３」において光信号「Ｘ」が出力される。同様に、スロット「２」において、ｔ＝２．２５のタイミングで光信号「Ｘ」が出力され、スロット「４」において、ｔ＝２．５のタイミングで光信号「Ｘ」が出力されている。すなわち、エッジ装置ｒは、ｒ＝１，３，２，４の順番で光信号を出力する。
また、時間間隔算出処理（図８参照）においてΔ＝５であることが分かるので、符号１９０１で示されるスロット「１」において、符号１９０４で示されるフレーム「ｔ＝５〜６」で光信号「Ｘ」が出力されると共に、同じタイミングでスロット「３」において光信号「Ｘ」が出力される。

第４の実施形態によれば、通過時刻算出処理を実行する際に、部分パスｅに代えてノードｎを信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）に関連付けることとしたので、部分パスｅにおける上り方向と下り方向を考慮する必要がない。これにより、計算を簡略化することができる。

以上、本発明の各実施形態について説明したが、本発明はこれらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、各実施形態では、信号転送可能時間帯算出装置１３０は、計算機能（通過時刻算出処理およびタイミング算出処理等）と、メモリ機能（各エッジ装置ｒのＡ（ｒ）、Ｂ（ｒ）、Ｃ（ｒ，ｅ）、Ｄ（ｒ，ｅ）およびΔを記憶する機能）とを両方備えるものとしたが、信号転送可能時間帯算出装置１３０に計算機能だけを付与し、１つ以上の別のエッジ装置１１０にメモリ機能を付与するような構成としてもよい。
また、各実施形態では、信号転送可能時間帯算出装置１３０を他のエッジ装置１１０（ｒ）とは別に独立して設けるものとして説明したが、複数のエッジ装置１１０のうちの１つ以上が信号転送可能時間帯算出装置１３０の各機能を備えるように構成してもよい。

本発明の第１の実施形態に係る信号転送可能時間帯算出装置を含むネットワークシステムの構成図である。 図１に示した信号転送可能時間帯算出装置の構成を示すブロック図である。 図１に示した信号転送可能時間帯算出装置に記憶された情報テーブルを示す説明図である。 図２に示した信号転送可能時間帯算出装置のＣＰＵの処理を示すメインフローチャートである。 図４に示した通過時刻算出処理を示すフローチャートである。 図５に示した通過時刻算出処理の処理結果を示す説明図であり、（ａ）はエッジ装置（ｒ＝１）のスロットパターン、（ｂ）はエッジ装置（ｒ＝２）のスロットパターン、（ｃ）はエッジ装置（ｒ＝３）のスロットパターン、（ｄ）はエッジ装置（ｒ＝４）のスロットパターンを示している。 図４に示したタイミング算出処理を示すフローチャートである。 図７に示した時間間隔算出処理（ランダム方式）を示すフローチャートである。 図８に示した時間間隔算出処理の処理過程を示す説明図である。 図７に示したタイミング算出処理の処理結果を示す説明図である。 本発明の第２の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行する通過時刻算出処理を示すフローチャートである。 図１１に示したフローチャートを説明するための説明図であり、（ａ）は比較例、（ｂ）は第２の実施形態を示している。 本発明の第３の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行する時間間隔算出処理（ｇｒｅｅｄｙ方式）を示すフローチャートである。 図１３に示した時間間隔算出処理の処理過程を示す説明図であり、（ａ）はエッジ装置（ｒ＝１）のスロットパターン、（ｂ）はエッジ装置（ｒ＝２）のスロットパターンを選択した場合、（ｃ）はエッジ装置（ｒ＝３）のスロットパターンを選択した場合、（ｄ）はエッジ装置（ｒ＝４）のスロットパターンを選択した場合を示している。 図１４に示した時間間隔算出処理の処理過程の続きを示す説明図であり、（ａ）はエッジ装置（ｒ＝３）のスロットパターンを選択決定した状態、（ｂ）はエッジ装置（ｒ＝２）のスロットパターンを選択した場合、（ｃ）はエッジ装置（ｒ＝４）のスロットパターンを選択した場合を示している。 図１５に示した時間間隔算出処理の処理過程の続きを示す説明図であり、（ａ）はエッジ装置（ｒ＝２）およびエッジ装置（ｒ＝４）のスロットパターンを続けて選択決定した状態、（ｂ）は処理結果を示している。 本発明の第４の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行する通過時刻算出処理を示すフローチャートである。 図１７に示した通過時刻算出処理の処理結果を示す説明図である。 図１８に示した処理結果を用いてタイミング算出処理を実行した場合の処理結果を示す説明図であり、（ａ）はランダム方式、（ｂ）はｇｒｅｅｄｙ方式を示している。

符号の説明

１００ ネットワークシステム
１１０ エッジ装置（ノード）
１２０ 分岐ノード（ノード）
１３０ 転送可能時間帯算出装置（ノード）
ｅ 部分パス
２００ バス
２１０ 入出力手段
２２０ ＲＡＭ
２３０ ＨＤＤ
２３１ 遅延時間
２３３ 接続情報
２３５ 信号出力時間
２４０ ＣＰＵ
２４１ 通過時刻算出手段
２４３ タイミング算出手段
２４５ 転送制御手段

Claims (14)

1. 複数のノードとノード間を接続するリンクとを備えてループのないツリー状のネットワークにおいて、
   前記ノードは、このネットワークの端部に配置された複数のエッジ装置と、前記複数のエッジ装置間のMultipoint-to-Multipoint型光パスを実現するために前記リンクが部分パスとして３つ以上接続されたスイッチ装置を示す複数の分岐ノードと、
   前記各エッジ装置が前記光パスにより別の前記エッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出装置とを含み、
   前記信号転送可能時間帯算出装置による信号転送可能時間帯算出方法であって、
   前記信号が前記光パスの各部分パスを通過する際に遅延する時間を示す遅延時間と、前記各部分パスの接続状態を示す接続情報と、前記複数のエッジ装置から選択された第１のエッジ装置が前記信号を出力する時間を示す信号出力時間とを取得する情報取得ステップと、
   この情報取得ステップで取得された遅延時間、接続情報および信号出力時間に基づいて、前記第１のエッジ装置から出力される信号が前記分岐ノードを通過する際の信号通過開始時刻および信号通過終了時刻を算出する通過時刻算出ステップと、
   この通過時刻算出ステップで算出された信号通過開始時刻および信号通過終了時刻と前記信号出力時間とに基づいて、前記第１のエッジ装置以外に選択された前記エッジ装置を示す第２のエッジ装置から出力される信号の信号通過開始時刻に所定の時間間隔を加算した時刻が、前記第１のエッジ装置から出力される信号の信号通過終了時刻に連続するような部分パスを１つ以上設けるように、かつ、前記第１のエッジ装置として選択できるすべての前記エッジ装置から出力される信号が、前記各部分パス上の同方向かつ同位置を同時刻に通過しないように、前記信号通過開始時刻に加算する所定の時間間隔を算出することにより、前記各エッジ装置における信号出力タイミングを算出するタイミング算出ステップと、
   を含んで実行し、
   前記タイミング算出ステップは、
   前記第２のエッジ装置から出力される信号の通過する前記部分パスにおいて、前記第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記信号通過開始時刻に加算する所定の時間間隔との和の最大値が最小となるように、当該所定の時間間隔を算出することを特徴とする信号転送可能時間帯算出方法。
2. 前記通過時刻算出ステップにおいて、
   前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号出力側の部分パスの始点に関連付けて算出することを特徴とする請求項１に記載の信号転送可能時間帯算出方法。
3. 前記通過時刻算出ステップにおいて、
   前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号入力側の部分パスの終点に関連付けて算出することを特徴とする請求項１に記載の信号転送可能時間帯算出方法。
4. 前記通過時刻算出ステップにおいて、
   前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに関連付けて算出することを特徴とする請求項１に記載の信号転送可能時間帯算出方法。
5. 前記タイミング算出ステップは、
   前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、ランダムに２つのエッジ装置を、前記第１のエッジ装置および第２のエッジ装置として組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となるようにした後、前記両エッジ装置以外のエッジ装置との組み合わせを順次選択することを特徴とする請求項１ないし請求項４のいずれか一項に記載の信号転送可能時間帯算出方法。
6. 前記タイミング算出ステップは、
   前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、前記第１のエッジ装置を前記第２のエッジ装置とそれぞれ仮に組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となる第２のエッジ装置を組み合わせることを決定した後、組み合わせることを決定された両エッジ装置以外のエッジ装置との組み合わせを同様に決定することを特徴とする請求項１ないし請求項４のいずれか一項に記載の信号転送可能時間帯算出方法。
7. 複数のノードとノード間を接続するリンクとを備えてループのないツリー状のネットワークにおいて、
   前記ノードは、このネットワークの端部に配置された複数のエッジ装置と、前記複数のエッジ装置間のMultipoint-to-Multipoint型光パスを実現するために前記リンクが部分パスとして３つ以上接続されたスイッチ装置を示す複数の分岐ノードと、
   前記各エッジ装置が前記光パスにより別の前記エッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出装置とを含み、
   前記ネットワークにおける信号転送可能時間帯算出装置であって、
   前記信号が前記光パスの各部分パスを通過する際に遅延する時間を示す遅延時間と、前記各部分パスの接続状態を示す接続情報と、前記複数のエッジ装置から選択された第１のエッジ装置が前記信号を出力する時間を示す信号出力時間とに基づいて、前記第１のエッジ装置から出力される信号が前記分岐ノードを通過する際の信号通過開始時刻および信号通過終了時刻を算出する通過時刻算出手段と、
   この通過時刻算出手段で算出された信号通過開始時刻および信号通過終了時刻と前記信号出力時間とに基づいて、前記第１のエッジ装置以外に選択された前記エッジ装置を示す第２のエッジ装置から出力される信号の信号通過開始時刻に所定の時間間隔を加算した時刻が、前記第１のエッジ装置から出力される信号の信号通過終了時刻に連続するような部分パスを１つ以上設けるように、かつ、前記第１のエッジ装置として選択できるすべての前記エッジ装置から出力される信号が、前記各部分パス上の同方向かつ同位置を同時刻に通過しないように、前記信号通過開始時刻に加算する所定の時間間隔を算出することにより、前記各エッジ装置における信号出力タイミングを算出するタイミング算出手段と、
   を備え、
   前記タイミング算出手段は、
   前記第２のエッジ装置から出力される信号の通過する前記部分パスにおいて、前記第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記信号通過開始時刻に加算する所定の時間間隔との和の最大値が最小となるように、当該所定の時間間隔を順次算出する、
   ことを特徴とする信号転送可能時間帯算出装置。
8. 前記通過時刻算出手段は、
   前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号出力側の部分パスの始点に関連付けて算出することを特徴とする請求項７に記載の信号転送可能時間帯算出装置。
9. 前記通過時刻算出手段は、
   前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号入力側の部分パスの終点に関連付けて算出することを特徴とする請求項７に記載の信号転送可能時間帯算出装置。
10. 前記通過時刻算出手段は、
    前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに関連付けて算出することを特徴とする請求項７に記載の信号転送可能時間帯算出装置。
11. 前記タイミング算出手段は、
    前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、ランダムに２つのエッジ装置を、前記第１のエッジ装置および第２のエッジ装置として組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となるようにした後、前記両エッジ装置以外のエッジ装置との組み合わせを順次選択することを特徴とする請求項７ないし請求項１０のいずれか一項に記載の信号転送可能時間帯算出装置。
12. 前記タイミング算出手段は、
    前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、前記第１のエッジ装置を前記第２のエッジ装置とそれぞれ仮に組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となる第２のエッジ装置を組み合わせることを決定した後、組み合わせることを決定された両エッジ装置以外のエッジ装置との組み合わせを同様に決定することを特徴とする請求項７ないし請求項１０のいずれか一項に記載の信号転送可能時間帯算出装置。
13. 請求項１乃至請求項６のいずれか一項に記載の信号転送可能時間帯算出方法をコンピュータに実行させるための信号転送可能時間帯算出プログラム。
14. 請求項１３に記載の信号転送可能時間帯算出プログラムが記録されたコンピュータ読み取り可能な記録媒体。

Images