JP4369892B2 - Signal transferable time zone calculation method, signal transferable time zone calculation device, signal transferable time zone calculation program, and computer-readable recording medium - Google Patents
Signal transferable time zone calculation method, signal transferable time zone calculation device, signal transferable time zone calculation program, and computer-readable recording medium Download PDFInfo
- Publication number
- JP4369892B2 JP4369892B2 JP2005090939A JP2005090939A JP4369892B2 JP 4369892 B2 JP4369892 B2 JP 4369892B2 JP 2005090939 A JP2005090939 A JP 2005090939A JP 2005090939 A JP2005090939 A JP 2005090939A JP 4369892 B2 JP4369892 B2 JP 4369892B2
- Authority
- JP
- Japan
- Prior art keywords
- signal
- time
- edge device
- edge
- passage
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Small-Scale Networks (AREA)
- Optical Communication System (AREA)
Description
本発明は、複数のノードと、２つのノード間を接続する部分パスとを有するツリー構造のネットワークの端部に配置されたノードである所定のエッジ装置が他のエッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出方法、信号転送可能時間帯算出装置、信号転送可能時間帯算出プログラムおよびコンピュータ読み取り可能な記録媒体に関する。 The present invention transfers a signal output from a predetermined edge device, which is a node arranged at the end of a tree-structured network having a plurality of nodes and a partial path connecting two nodes, to another edge device. The present invention relates to a signal transferable time zone calculation method, a signal transferable time zone calculation device, a signal transferable time zone calculation program, and a computer-readable recording medium.
近年、データトラフィックの増加に伴い、大容量の光伝送方式への需要が高まっている。これらの種類として、ＷＤＭ（Wavelength Division Multiplexing）などの波長多重方式や光ＴＤＭ（Time Division Multiplexing）などの時分割多重方式、光バーストスイッチングや光パケットスイッチングなどのパケット多重方式が提案されている。その中で、ブロードキャスト型の光伝送方式として、ＧＥＰＯＮ（Gigabit Ethernet（登録商標）-Passive Optical Network）が知られている（例えば非特許文献１参照）。 In recent years, with an increase in data traffic, there is an increasing demand for large-capacity optical transmission systems. As these types, wavelength division multiplexing such as WDM (Wavelength Division Multiplexing), time division multiplexing such as optical TDM (Time Division Multiplexing), and packet multiplexing such as optical burst switching and optical packet switching have been proposed. Among them, GEPON (Gigabit Ethernet (registered trademark) -Passive Optical Network) is known as a broadcast-type optical transmission system (see, for example, Non-Patent Document 1).
このＧＥＰＯＮはループのないツリー状のネットワーク上で実現される。ネットワークの分岐点には光信号を分岐するカプラが設けられている。また、ＧＥＰＯＮでは、光信号を送信する装置として、ＯＮＵ（Optical Network Unit）とＯＬＴ（Optical Line Terminal）が存在している。ＯＬＴの下流にはユーザが利用するＯＮＵが配置されており、ＯＬＴは、ユーザから送られるデータを光信号に変換して他のＯＮＵに送信する役割を果たす。つまり、ＯＮＵから送られた光信号は一度ＯＬＴにより終端され、他のＯＮＵに送られるのである。このとき、複数のＯＮＵから同時に光信号がＯＬＴに送信されると、ネットワーク内で信号同士が衝突するため、ＯＮＵから送信（出力）される信号の転送タイミングを調整することが必要となる。ＧＥＰＯＮでは、ＯＬＴがＯＮＵに対し、光信号の転送開始時刻および転送終了時刻を通知することでこの調整を行っている。 This GEPON is realized on a tree-like network without a loop. A coupler that branches an optical signal is provided at a branch point of the network. In GEPON, there are ONU (Optical Network Unit) and OLT (Optical Line Terminal) as devices for transmitting optical signals. An ONU used by a user is arranged downstream of the OLT, and the OLT plays a role of converting data sent from the user into an optical signal and transmitting it to another ONU. That is, the optical signal sent from the ONU is once terminated by the OLT and sent to another ONU. At this time, if optical signals are simultaneously transmitted from a plurality of ONUs to the OLT, the signals collide with each other in the network. Therefore, it is necessary to adjust the transfer timing of the signals transmitted (output) from the ONUs. In GEPON, the OLT performs this adjustment by notifying the ONU of the transfer start time and transfer end time of the optical signal.
ＧＥＰＯＮの問題点は、ＯＮＵが出力する光信号が、ネットワークを構成する光ファイバにより物理的に接続されているＯＮＵすべてに到達することである。ＯＮＵから出力された光信号はＯＬＴからＯＮＵに転送される際、ネットワークの分岐点であるカプラで信号レベルが減衰する。この減衰量は、カプラの分岐数に依存するため、カプラの先に存在するＯＮＵ数が増加するのに従って増加することになる。この問題を解決するため、分岐点での分岐数を制限することが可能なMultipoint-to-Multipoint型光パスを利用した光伝送方式を用いることが考えられる。この光伝送方式は、光信号を送信するエッジ装置、光信号を分岐して信号の宛先へと誘導するスイッチ装置および光ファイバからなるネットワーク上で光伝送を行う技術である。 The problem with GEPON is that the optical signal output by the ONU reaches all ONUs that are physically connected by the optical fiber that forms the network. When the optical signal output from the ONU is transferred from the OLT to the ONU, the signal level is attenuated by a coupler which is a branch point of the network. Since this attenuation amount depends on the number of branches of the coupler, it increases as the number of ONUs existing ahead of the coupler increases. In order to solve this problem, it is conceivable to use an optical transmission system using a multipoint-to-multipoint type optical path that can limit the number of branches at a branch point. This optical transmission system is a technology for performing optical transmission on a network composed of an edge device that transmits an optical signal, a switch device that branches the optical signal and guides it to the destination of the signal, and an optical fiber.
この場合、ネットワークの分岐点として、カプラだけではなく、スイッチ装置を利用することで、光信号を送りたいところのみ信号を通過させることができる。そして、各エッジ装置はこの光信号を用いて信号の届くほかのエッジ装置に対してデータを送信する。この光伝送方式を用いれば、光信号の減衰量が低下し、光信号をより長い区間で送信することができる。また、光信号を通すファイバ数を少なくすることで、同一波長をもつ光信号を別の光ファイバを利用して送信することが可能となり、ネットワーク全体での光信号の利用効率が向上する。
しかしながら、Multipoint-to-Multipoint型光パスを用いた光伝送方式でも、ＧＥＰＯＮで発生していた信号の衝突現象は起こりうるという問題がある。
そこで、信号の衝突を回避するために、各エッジ装置から送信された信号が光ファイバを通過する時刻（通過時刻）を取得し、２つ以上の信号が同位置を同時刻に通過しないことを条件に通過時刻を割り当てることが考えられる。例えば、この条件ですべてのエッジ装置が予め決められた順番に従って光信号を送信し終わったときに（一巡したときに）、最初に光信号を送信したエッジ装置から同じ順番で光信号を送信することが考えられる。この場合、順番によっては送信順が一巡するまでに要する時間がかかり過ぎるという問題が生じる。
However, even in an optical transmission system using a multipoint-to-multipoint type optical path, there is a problem that a signal collision phenomenon that has occurred in GEPON may occur.
Therefore, in order to avoid signal collision, the time (passing time) when the signal transmitted from each edge device passes through the optical fiber is acquired, and two or more signals do not pass through the same position at the same time. It is conceivable to assign a passage time to the condition. For example, when all edge devices have finished transmitting optical signals according to a predetermined order under this condition (when one cycle has been completed), the optical signals are transmitted in the same order from the edge device that first transmitted the optical signals. It is possible. In this case, depending on the order, there is a problem that it takes too much time to complete the transmission order.
そこで、本発明では、前記した問題を解決し、信号の衝突を防止することのできる信号転送可能時間帯算出方法、信号転送可能時間帯算出装置、信号転送可能時間帯算出プログラムおよび記録媒体を提供することを目的とする。
また、本発明は、転送対象とする信号が一巡するまでに要する時間を低減できる信号転送可能時間帯算出方法、信号転送可能時間帯算出装置、信号転送可能時間帯算出プログラムおよび記録媒体を提供することを他の目的とする。
Therefore, the present invention provides a signal transferable time zone calculation method, a signal transferable time zone calculation device, a signal transferable time zone calculation program, and a recording medium that can solve the above-described problems and prevent signal collision. The purpose is to do.
The present invention also provides a signal transferable time zone calculation method, a signal transferable time zone calculation device, a signal transferable time zone calculation program, and a recording medium that can reduce the time required for a signal to be transferred to make a round. For other purposes.
前記課題を解決するため、請求項１に記載の信号転送可能時間帯算出方法は、複数のノードとノード間を接続するリンクとを備えてループのないツリー状のネットワークにおいて、前記ノードは、このネットワークの端部に配置された複数のエッジ装置と、前記複数のエッジ装置間のMultipoint-to-Multipoint型光パスを実現するために前記リンクが部分パスとして３つ以上接続されたスイッチ装置を示す複数の分岐ノードと、前記各エッジ装置が前記光パスにより別の前記エッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出装置とを含み、前記信号転送可能時間帯算出装置による信号転送可能時間帯算出方法であって、前記信号が前記光パスの各部分パスを通過する際に遅延する時間を示す遅延時間と、前記各部分パスの接続状態を示す接続情報と、前記複数のエッジ装置から選択された第１のエッジ装置が前記信号を出力する時間を示す信号出力時間とを取得する情報取得ステップと、この情報取得ステップで取得された遅延時間、接続情報および信号出力時間に基づいて、前記第１のエッジ装置から出力される信号が前記分岐ノードを通過する際の信号通過開始時刻および信号通過終了時刻を算出する通過時刻算出ステップと、この通過時刻算出ステップで算出された信号通過開始時刻および信号通過終了時刻と前記信号出力時間とに基づいて、前記第１のエッジ装置以外に選択された前記エッジ装置を示す第２のエッジ装置から出力される信号の信号通過開始時刻に所定の時間間隔を加算した時刻が、前記第１のエッジ装置から出力される信号の信号通過終了時刻に連続するような部分パスを１つ以上設けるように、かつ、前記第１のエッジ装置として選択できるすべての前記エッジ装置から出力される信号が、前記各部分パス上の同方向かつ同位置を同時刻に通過しないように、前記信号通過開始時刻に加算する所定の時間間隔を算出することにより、前記各エッジ装置における信号出力タイミングを算出するタイミング算出ステップと、を含んで実行し、前記タイミング算出ステップが、前記第２のエッジ装置から出力される信号の通過する前記部分パスにおいて、前記第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記信号通過開始時刻に加算する所定の時間間隔との和の最大値が最小となるように、当該所定の時間間隔を算出することを特徴とする。
To solve the above problems, the signal transfer time zone calculation method according to
請求項７に記載の信号転送可能時間帯算出装置は、複数のノードとノード間を接続するリンクとを備えてループのないツリー状のネットワークにおいて、前記ノードが、このネットワークの端部に配置された複数のエッジ装置と、前記複数のエッジ装置間のMultipoint-to-Multipoint型光パスを実現するために前記リンクが部分パスとして３つ以上接続されたスイッチ装置を示す複数の分岐ノードと、前記各エッジ装置が前記光パスにより別の前記エッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出装置とを含み、前記ネットワークにおける信号転送可能時間帯算出装置であって、前記信号が前記光パスの各部分パスを通過する際に遅延する時間を示す遅延時間と、前記各部分パスの接続状態を示す接続情報と、前記複数のエッジ装置から選択された第１のエッジ装置が前記信号を出力する時間を示す信号出力時間とに基づいて、前記第１のエッジ装置から出力される信号が前記分岐ノードを通過する際の信号通過開始時刻および信号通過終了時刻を算出する通過時刻算出手段と、この通過時刻算出手段で算出された信号通過開始時刻および信号通過終了時刻と前記信号出力時間とに基づいて、前記第１のエッジ装置以外に選択された前記エッジ装置を示す第２のエッジ装置から出力される信号の信号通過開始時刻に所定の時間間隔を加算した時刻が、前記第１のエッジ装置から出力される信号の信号通過終了時刻に連続するような部分パスを１つ以上設けるように、かつ、前記第１のエッジ装置として選択できるすべての前記エッジ装置から出力される信号が、前記各部分パス上の同方向かつ同位置を同時刻に通過しないように、前記信号通過開始時刻に加算する所定の時間間隔を算出することにより、前記各エッジ装置における信号出力タイミングを算出するタイミング算出手段と、を備え、前記タイミング算出手段が、前記第２のエッジ装置から出力される信号の通過する前記部分パスにおいて、前記第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記信号通過開始時刻に加算する所定の時間間隔との和の最大値が最小となるように、当該所定の時間間隔を順次算出することとした。
Signal transfer time zone calculating apparatus according to
請求項１に示す方法または請求項７に示す装置によれば、各エッジ装置から出力される信号の出力時間と、各部分パスを通過する時刻とに基づいて、各エッジ装置から出力される信号が部分パス上の同方向かつ同位置を同時刻に通過することのないように、各エッジ装置から出力される信号が所定の時間間隔をずらして転送される。したがって、各エッジ装置から出力される信号が部分パス上において衝突することを防止することができる。
According to the method shown in
ここで、部分パスは、例えば光ファイバによって構成され、分岐ノードは、エッジ装置から出力される信号を宛先へ誘導するスイッチ装置から構成される。また、信号通過開始時刻および信号通過終了時刻は、例えばネットワーク上の所定の地点に関連付けて計算される。また、各エッジ装置が信号を出力する時間を示す信号出力時間は、例えば、信号出力継続時間や、信号出力開始時刻および信号出力終了時刻等である。
また、請求項１に示す方法または請求項７に示す装置によれば、第１のエッジ装置から出力される信号に対して、第２のエッジ装置から出力される信号を所定の時間間隔だけずらして転送する際に、第２のエッジ装置から出力される信号の信号通過終了時刻と所定の時間間隔との和について、部分パスによる相違を考慮することができる。そして、この和の最大値を最小とするので、信号通過開始時刻に加算する所定の時間間隔は、第２のエッジ装置から出力される信号に対して最も小さいものとすることができる。したがって、転送対象とする信号が一巡するまでの時間を低減し、各信号の転送効率を向上させることができる。
Here, the partial path is configured by, for example, an optical fiber, and the branch node is configured by a switch device that guides a signal output from the edge device to a destination. The signal passage start time and the signal passage end time are calculated in association with a predetermined point on the network, for example. The signal output time indicating the time for which each edge device outputs a signal is, for example, a signal output duration, a signal output start time, a signal output end time, or the like.
According to the method of
請求項２に記載の信号転送可能時間帯算出方法は、請求項１に記載の信号転送可能時間帯算出方法において、前記通過時刻算出ステップにおいて、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号出力側の部分パスの始点に関連付けて算出することを特徴とする。
The signal transferable time zone calculation method according to
請求項８に記載の信号転送可能時間帯算出装置は、請求項７に記載の信号転送可能時間帯算出装置において、前記通過時刻算出手段が、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号出力側の部分パスの始点に関連付けて算出することを特徴とする。
The signal transferable time zone calculation device according to
請求項２に示す方法または請求項８に示す装置によれば、接続情報として、部分パス同士の接続関係さえわかればよいので、部分パスがどのノードと接続しているかを示す情報を省略できるので、取得すべき接続情報を簡略化することができる。
According to the method shown in
請求項３に記載の信号転送可能時間帯算出方法は、請求項１に記載の信号転送可能時間帯算出方法において、前記通過時刻算出ステップにおいて、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号入力側の部分パスの終点に関連付けて算出することを特徴とする。
The signal transferable time zone calculation method according to
請求項９に記載の信号転送可能時間帯算出装置は、請求項７に記載の信号転送可能時間帯算出装置において、前記通過時刻算出手段が、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号入力側の部分パスの終点に関連付けて算出することを特徴とする。
The signal transferable time zone calculation device according to
請求項３に示す方法または請求項９に示す装置によれば、接続情報として、部分パス同士の接続関係さえわかればよいので、部分パスがどのノードと接続しているかを示す情報を省略できるので、取得すべき接続情報を簡略化することができる。また、部分パスの始点に関連付けて信号通過開始時刻および信号通過終了時刻を算出する場合と比較して、対象とする部分パスにおける遅延時間をそのまま利用することができるので、その分だけ計算手順を省略化することができる。
According to the method shown in
請求項４に記載の信号転送可能時間帯算出方法は、請求項１に記載の信号転送可能時間帯算出方法において、前記通過時刻算出ステップにおいて、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに関連付けて算出することを特徴とする。
The signal transferable time zone calculation method according to
請求項１０に記載の信号転送可能時間帯算出装置は、請求項７に記載の信号転送可能時間帯算出装置において、前記通過時刻算出手段が、前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに関連付けて算出することを特徴とする。
The signal transferable time zone calculation device according to
請求項４に示す方法または請求項１０に示す装置によれば、部分パスにおいて信号通過開始時刻および信号通過終了時刻を算出する場合と比較して、部分パスにおける信号通過方向（上り、下り）を考慮する必要がないので、計算量を低減することができる。
According to the method shown in
請求項５に記載の信号転送可能時間帯算出方法は、請求項１ないし請求項４のいずれか一項に記載の信号転送可能時間帯算出方法において、前記タイミング算出ステップは、前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、ランダムに２つのエッジ装置を、前記第１のエッジ装置および第２のエッジ装置として組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となるようにした後、前記両エッジ装置以外のエッジ装置との組み合わせを順次選択することを特徴とする。
The signal transferable time zone calculation method according to
請求項１１に記載の信号転送可能時間帯算出装置は、請求項７ないし請求項１０のいずれか一項に記載の信号転送可能時間帯算出装置において、前記タイミング算出手段が、前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、ランダムに２つのエッジ装置を、前記第１のエッジ装置および第２のエッジ装置として組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となるようにした後、前記両エッジ装置以外のエッジ装置との組み合わせを順次選択することを特徴とする。
The signal transferable time zone calculation device according to
請求項５に示す方法または請求項１１に示す装置によれば、第１のエッジ装置から出力される信号と、第２のエッジ装置から出力される信号との組み合わせがランダムに選択されるので、計算量を必要最小限に抑制して、転送可能時間帯を迅速に算出することができる。
According to the apparatus shown in method or claim 11 illustrated in
請求項６に記載の信号転送可能時間帯算出方法は、請求項１ないし請求項４のいずれか一項に記載の信号転送可能時間帯算出方法において、前記タイミング算出ステップは、前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、前記第１のエッジ装置を前記第２のエッジ装置とそれぞれ仮に組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となる第２のエッジ装置を組み合わせることを決定した後、組み合わせることを決定された両エッジ装置以外のエッジ装置との組み合わせを同様に決定することを特徴とする。
The signal transferable time zone calculation method according to
請求項１２に記載の信号転送可能時間帯算出装置は、請求項７ないし請求項１０のいずれか一項に記載の信号転送可能時間帯算出装置において、前記タイミング算出手段が、前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、前記第１のエッジ装置を前記第２のエッジ装置とそれぞれ仮に組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となる第２のエッジ装置を組み合わせることを決定した後、組み合わせることを決定された両エッジ装置以外のエッジ装置との組み合わせを同様に決定することを特徴とする。
The signal transferable time zone calculation device according to claim 12 is the signal transferable time zone calculation device according to any one of
請求項６に示す方法または請求項１２に示す装置によれば、第１のエッジ装置から出力される信号と、第２のエッジ装置から出力される信号との組み合わせとして、すべての組み合わせの中で最適な組み合わせを抽出してから、さらに別のエッジ装置から出力される信号を選択するので、すべてのエッジ装置を最適に組み合わせることができる。したがって、転送対象とする信号が一巡するまでの時間を最も低減することができ、各信号の転送効率を向上することができる。
According to the apparatus shown in method or claim 12 illustrated in
請求項１３に記載の信号転送可能時間帯算出プログラムは、請求項１乃至請求項６のいずれか一項に記載の信号転送可能時間帯算出方法をコンピュータに実行させるためのプログラムである。このように構成されることにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。 A signal transferable time zone calculation program according to a thirteenth aspect is a program for causing a computer to execute the signal transferable time zone calculation method according to any one of the first to sixth aspects. By being configured in this way, a computer in which this program is installed can realize each function based on this program.
請求項１４に記載のコンピュータ読み取り可能な記録媒体は、請求項１３に記載の信号転送可能時間帯算出プログラムが記録されたことを特徴とする。このように構成されることにより、この記録媒体を読み取り可能な情報処理装置は、このプログラムに基づいた各機能を実現することができる。 A computer-readable recording medium according to a fourteenth aspect is characterized in that the signal transferable time zone calculating program according to the thirteenth aspect is recorded. With this configuration, the information processing apparatus that can read the recording medium can realize each function based on the program.
本発明によれば、各エッジ装置から出力される信号と、その信号が各部分パスを通過する時刻とに基づいて、各エッジ装置から出力される信号が所定の時間間隔をずらして転送される。したがって、各エッジ装置から出力される信号が部分パス上において衝突することを防止することができる。
また、本発明は、所定のエッジ装置から出力される信号に対して、別のエッジ装置から出力される信号を所定の時間間隔だけずらして転送する際に、信号通過終了時刻と前記所定の時間間隔との和について、部分パスによる相違を考慮したので、転送対象とする信号が一巡するまでの時間を低減し、各信号の転送効率を向上させることができる。
According to the present invention, based on the signal output from each edge device and the time when the signal passes through each partial path, the signal output from each edge device is transferred at a predetermined time interval. . Therefore, it is possible to prevent the signals output from the edge devices from colliding on the partial path.
Further, the present invention relates to a signal passing end time and the predetermined time when transferring a signal output from another edge device by shifting a signal output from another edge device by a predetermined time interval. Since the difference between the partial paths is taken into consideration with respect to the sum with the interval, it is possible to reduce the time until the signal to be transferred makes a round and improve the transfer efficiency of each signal.
（第１の実施形態）
［信号転送可能時間帯算出装置の構成］
以下、本発明の第１の実施形態に係る信号転送可能時間帯算出装置の構成を図１乃至図３を参照して説明する。図１は本発明の第１の実施形態に係る信号転送可能時間帯算出装置を含むネットワークシステムの構成図であり、図２は図１に示した信号転送可能時間帯算出装置の構成を示すブロック図であり、図３は図１に示した信号転送可能時間帯算出装置に記憶された情報テーブルを示す説明図である。
(First embodiment)
[Configuration of signal transferable time zone calculation device]
Hereinafter, the configuration of the signal transferable time zone calculation apparatus according to the first embodiment of the present invention will be described with reference to FIGS. 1 to 3. FIG. 1 is a configuration diagram of a network system including a signal transferable time zone calculation device according to the first embodiment of the present invention, and FIG. 2 is a block diagram showing a configuration of the signal transferable time zone calculation device shown in FIG. FIG. 3 is an explanatory diagram showing an information table stored in the signal transferable time zone calculation apparatus shown in FIG.
ネットワークシステム１００は、図１に示すように、複数のノード１１０，１２０，１３０と、２つのノード（１１０，１２０，１３０のいずれか）間を接続する部分パス（リンク）ｅとを有するループのないツリー構造のネットワークである。ノード１１０〜１３０は、機能が異なり、以下の説明では、それぞれエッジ装置１１０と、分岐ノード１２０と、信号転送可能時間帯算出装置１３０として説明する。なお、図１に示したノードと部分パスの個数は一例であって、本発明はこれに限定されるものではない。
As shown in FIG. 1, the
エッジ装置１１０は、ネットワークシステム１００のツリー構造の端部に配置されている。このエッジ装置１１０は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、通信インターフェースおよびハードディスクドライブ（ＨＤＤ）などを含んで構成されるパーソナルコンピュータであり、所定の信号を他のエッジ装置１１０に出力すると共に、他のエッジ装置１１０から出力された信号が入力するものである。この所定の信号は例えば光信号であり、部分パスｅ（図１に示した例ではｅ０，ｅ１，ｅ２，ｅ３，ｅ４，ｅ５）は、例えば上り方向の光信号と下り方向の光信号とを分離して伝送する光ファイバである。ここで、複数のエッジ装置１１０を識別するために識別変数としてｒ（図１に示した例ではｒ＝１〜４）を導入し、特に区別しないときにはエッジ装置１１０を単にエッジ装置ｒと呼ぶことにする。
The
分岐ノード１２０は、部分パスｅが３つ以上接続されたノードであり、１つの部分パスｅから入力した信号を他の部分パスｅ′にそれぞれ出力するスイッチ装置である。ここで、複数の分岐ノード１２０を識別するために識別変数としてｎ（図１に示した例ではｎ＝１０，１１）を導入し、特に区別しないときには分岐ノード１２０を分岐ノードｎと呼ぶ。なお、このｎはノード全般（１１０，１２０，１３０）に使用することもある。
The
信号転送可能時間帯算出装置１３０は、例えば、ネットワークシステム１００のツリー構造の端部に配置され、各エッジ装置ｒから出力される信号が各部分パスｅ上で衝突しないように、各エッジ装置ｒから出力される信号の転送時間帯を算出し、各エッジ装置ｒにおける信号出力タイミング（信号転送時間帯）を割り当てるものである。この信号転送可能時間帯算出装置１３０は、図２に示すように、入出力手段２１０と、ＲＡＭ２２０と、ＨＤＤ２３０と、ＣＰＵ２４０とを備えている。
The signal transferable time
入出力手段２１０は、部分パスｅを介して、各エッジ装置ｒから入力される情報（信号出力時間など）をＨＤＤ２３０に出力すると共に、各エッジ装置ｒに割り当てた信号転送時間帯を示す情報を各エッジ装置ｒに出力するためのインタフェースである。この入出力手段２１０は、外部装置から入力される情報（遅延時間、接続情報など）をＨＤＤ２３０に出力する。
ＲＡＭ２２０は、半導体メモリや磁気メモリなどの書き換え可能な記憶手段であり、ＣＰＵ２４０による演算処理等に利用される。
The input /
The
ＨＤＤ２３０は、入出力手段２１０を介して取得した遅延時間２３１、接続情報２３３および信号出力時間２３５や、ＣＰＵ２４０の処理結果等を記憶するものである。
遅延時間２３１は、エッジ装置ｒから出力される信号が各部分パスｅを通過する際に遅延する時間を示すものである。なお、個々の遅延時間２３１を遅延時間ｄ（ｅ）と表記する。
接続情報２３３は、各部分パスｅの接続状態を示すものであり、例えば、各部分パスｅの両端が接続しているノードｎに関する情報や、各部分パスｅの両端が接続している別の部分パスｅ′に関する情報である。
信号出力時間２３５は、各エッジ装置ｒが信号を出力する時間を示し、例えば信号出力継続時間や、信号出力開始時刻および終了時刻等である。なお、個々の信号出力時間２３５を信号出力時間ｓ（ｒ）と表記する。
The
The
The
The
ここで、遅延時間２３１と接続情報２３３の具体例を図１および図３を参照して説明する。図３に示した情報テーブル３００では、例えば部分パスｅ１の遅延時間ｄ（ｅ１）は「１」となっている。また、情報テーブル３００では、接続情報２３３は、各部分パスｅの両端（端点１，端点２）が接続している部分パスｅを示している。例えば、部分パスｅ１は、端点１の接続情報が「ｎｕｌｌ（空白）」となっており、端点１には、別の部分パスｅ′が接続されていないことを示している。一方、端点２には、部分パスｅ２，ｅ３が接続されていることが示されている。なお、ここでは部分パスｅ０を考慮しないものとする。これらの部分パスｅのうち、部分パスｅ２に接続されている部分パスｅを求めるには、部分パスｅ２の端点１を参照することになる。この場合には、部分パスｅ２の端点１の接続情報は「ｎｕｌｌ（空白）」なので、この先には、別の部分パスｅが接続されていないことがわかる。一方、部分パスｅ１から部分パスｅ３に進んだときに、その先に接続されている部分パスｅを求めるには、部分パスｅ３の端点１を参照することになる。この場合には、部分パスｅ３の端点１の接続情報は「ｅ４，ｅ５」なので、この先には、別の部分パスｅ４，ｅ５が接続されていることがわかる。つまり、図３に示した情報テーブル３００では、部分パスｅを連結したルートを探索する際には、「端点２」→「端点１」→「端点２」…のように端点１と端点２とを交互に参照する。例えば「着目している部分パスｅの端点２」、「この端点２に接続された部分パスｅの端点１」、「この端点１に接続された部分パスｅの端点２」のような順序で参照することになる。
Here, specific examples of the
図２に戻って、信号転送可能時間帯算出装置１３０の構成の説明を続ける。
ＣＰＵ２４０は、前記した入出力手段２１０、ＲＡＭ２２０およびＨＤＤ２３０を制御すると共に、各エッジ装置ｒから出力される信号の転送時間帯を算出し、各エッジ装置ｒに信号出力タイミングを割り当てて入出力手段２１０に出力するものである。このために、ＣＰＵ２４０は、図２に示すように、通過時刻算出手段２４１と、タイミング算出手段２４３と、転送制御手段２４５とを含んで構成されている。
Returning to FIG. 2, the description of the configuration of the signal transferable time
The
通過時刻算出手段２４１は、詳細は後記するが、ＨＤＤ２３０に記憶された遅延時間２３１と、接続情報２３３と、信号出力時間２３５とに基づいて、分岐ノードｎを、各エッジ装置ｒから出力される信号が通過する際の信号通過開始時刻Ｃ（ｒ）および信号通過終了時刻Ｄ（ｒ）を算出し、タイミング算出手段２４３に出力するものである。
Although details will be described later, the passage
タイミング算出手段２４３は、詳細は後記するが、通過時刻算出手段２４１で算出された信号通過開始時刻Ｃ（ｒ）および信号通過終了時刻Ｄ（ｒ）に基づいて、選択された所定のエッジ装置ｒとは別のエッジ装置ｒ′から出力される信号の信号通過開始時刻Ｃ（ｒ′）と所定の時間間隔β（ｒ′）との和である時刻が、所定のエッジ装置ｒから出力される信号の信号通過終了時刻Ｄ（ｒ）に連続するような部分パスｅを１つ以上設けるように、時間間隔β（ｒ′）を算出するものである。このタイミング算出手段２４３は、前記した時間間隔β（ｒ′）を算出する際に、すべてのエッジ装置ｒから出力される信号が、各部分パスｅ上の同方向かつ同位置を同時刻に通過しないように、時間間隔β（ｒ′）を算出する。そして、このようにして求めた時間間隔β（ｒ′）と信号出力時間２３５とに基づいて、各エッジ装置ｒにおける信号出力タイミングを算出し、転送制御手段２４５に出力する。
Although details will be described later, the
転送制御手段２４５は、タイミング算出手段２４３によって算出された転送タイミングを入出力手段２１０を介して各エッジ装置ｒに通知することにより、各エッジ装置ｒから出力される信号の転送を制御するものである。
The
［信号転送可能時間帯算出装置の動作］
次に、本発明の第１の実施形態に係る信号転送可能時間帯算出装置１３０の動作について図４を参照（適宜図２参照）して説明する。図４は、図２に示した信号転送可能時間帯算出装置１３０のＣＰＵ２４０の処理を示すメインフローチャートである。
まず、ＣＰＵ２４０は、入出力手段２１０によって、外部装置から遅延時間２３１および接続情報２３３を取得すると共に、部分パスｅ０を介して各エッジ装置ｒから信号出力時間ｓ（ｒ）を取得し（ステップＳ１：情報取得ステップ）、取得した各情報をＨＤＤ２３０に格納する。
[Operation of signal transferable time zone calculation device]
Next, the operation of the signal transferable time
First, the
次に、ＣＰＵ２４０は、通過時刻算出手段２４１によって、後記する通過時刻算出処理を実行する（ステップＳ２：通過時刻算出ステップ）。ここで、通過時刻算出手段２４１は、各エッジ装置ｒから出力される信号が通過する部分パスｅの始点において、信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）を求め、タイミング算出手段２４３に出力する。
Next, the
続いて、ＣＰＵ２４０は、タイミング算出手段２４３によって、信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）と、ステップＳ１で取得した信号出力時間ｓ（ｒ）とに基づいて、後記するタイミング算出処理を実行する（ステップＳ３：タイミング算出ステップ）。ここで、タイミング算出手段２４３は、各エッジ装置ｒから出力される信号の信号転送時間帯を決定し、転送制御手段２４５に出力する。
最後に、ＣＰＵ２４０は、転送制御手段２４５によって、信号転送時間帯に基づいて、各エッジ装置ｒに信号出力タイミングを通知する（ステップＳ４）。
Subsequently, the
Finally, the
次に、前記したステップＳ２の通過時刻算出処理について図５を参照（適宜図２および図３参照）して説明する。図５は、図４に示した通過時刻算出処理を示すフローチャートである。ここで、説明を簡便にするため、以下では、信号出力時間２３５は、信号出力継続時間とし、すべてのエッジ装置ｒの個々の信号出力時間ｓ（ｒ）はすべて「１」とする。
Next, the passage time calculation process in step S2 described above will be described with reference to FIG. 5 (see FIGS. 2 and 3 as appropriate). FIG. 5 is a flowchart showing the passage time calculation process shown in FIG. Here, in order to simplify the description, hereinafter, the
まず、ＣＰＵ２４０の通過時刻算出手段２４１は、エッジ装置ｒを選択する（ステップＳ１１）。そして、通過時刻算出手段２４１は、選択したエッジ装置ｒを始点（例えば端点１）とする部分パスｅの終点（例えば端点２）を始点（例えば端点２）とする部分パスを「ｅ′」とする（ステップＳ１２）。そして、通過時刻算出手段２４１は、部分パスｅ′の始点に関連付けて信号通過開始時刻Ｃ（ｒ，ｅ′）および信号通過終了時刻Ｄ（ｒ，ｅ′）を次式（１）および（２）で求める（ステップＳ１３）。
Ｃ（ｒ，ｅ′）＝ｄ（ｅ） …（１）
Ｄ（ｒ，ｅ′）＝ｄ（ｅ）＋ｓ（ｒ） …（２）
なお、部分パスｅ′が複数ある場合にはそれぞれ求める。
First, the passage
C (r, e ′) = d (e) (1)
D (r, e ') = d (e) + s (r) (2)
If there are a plurality of partial paths e ′, each is obtained.
続けて、通過時刻算出手段２４１は、部分パスｅ′の終点を始点とする部分パスｅ″が存在するか否かを判定する（ステップＳ１４）。部分パスｅ″が存在する場合（ステップＳ１４：Ｙｅｓ）、通過時刻算出手段２４１は、部分パスｅ″の始点に関連付けて信号通過開始時刻Ｃ（ｒ，ｅ″）および信号通過終了時刻Ｄ（ｒ，ｅ″）を次式（３）および（４）で求める（ステップＳ１５）。
Ｃ（ｒ，ｅ″）＝Ｃ（ｒ，ｅ′）＋ｄ（ｅ′） …（３）
Ｄ（ｒ，ｅ″）＝Ｄ（ｒ，ｅ′）＋ｄ（ｅ′） …（４）
なお、部分パスｅ″が複数ある場合にはそれぞれ求める。
Subsequently, the passage
C (r, e ″) = C (r, e ′) + d (e ′) (3)
D (r, e ″) = D (r, e ′) + d (e ′) (4)
Note that, when there are a plurality of partial paths e ″, each is obtained.
続けて、通過時刻算出手段２４１は、部分パスｅ″の終点を始点とする部分パスが存在するか否かを判定する（ステップＳ１６）。部分パスｅ″の終点を始点とする部分パスが存在する場合（ステップＳ１６：Ｙｅｓ）、通過時刻算出手段２４１は、ｅ′：＝ｅ″として（ステップＳ１７）、ステップＳ１４に戻る。なお、「ｅ′：＝ｅ″」は、これまでの部分パス「ｅ″」をあらためて部分パス「ｅ′」に置き換えて取り扱うことを意味する。 Subsequently, the passage time calculation means 241 determines whether or not there is a partial path starting from the end point of the partial path e ″ (step S16). A partial path starting from the end point of the partial path e ″ exists. If so (step S16: Yes), the passage time calculation means 241 sets e ': = e "(step S17) and returns to step S14. Note that" e': = e "" indicates the partial path so far. This means that “e ″” is newly replaced with a partial path “e ′”.
一方、部分パスｅ″の終点を始点とする部分パスが存在しない場合（ステップＳ１６：Ｎｏ）、および、部分パスｅ″が存在しない場合（ステップＳ１４：Ｎｏ）、通過時刻算出手段２４１は、すべてのエッジ装置ｒを選択したか否かを判定する（ステップＳ１８）。すべてのエッジ装置ｒを選択した場合（ステップＳ１８：Ｙｅｓ）、通過時刻算出手段２４１は、通過時刻算出処理を終了し、各エッジ装置ｒから出力される信号の各部分パスｅの始点における信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）をタイミング算出手段２４３に出力する。一方、すべてのエッジ装置ｒを選択していない場合（ステップＳ１８：Ｎｏ）、通過時刻算出手段２４１は、ステップＳ１１に戻る。
On the other hand, when there is no partial path starting from the end point of the partial path e ″ (step S16: No) and when the partial path e ″ does not exist (step S14: No), all the passage time calculation means 241 It is determined whether or not the edge device r is selected (step S18). When all the edge devices r have been selected (step S18: Yes), the passage
次に、前記したステップＳ２の通過時刻算出処理を、図１に示したネットワークシステム１００に適用した処理結果を図６を参照（適宜図１および図３参照）して説明する。図６は、図５に示した通過時刻算出処理の処理結果を示す説明図であり、（ａ）はエッジ装置（ｒ＝１）のスロットパターン、（ｂ）はエッジ装置（ｒ＝２）のスロットパターン、（ｃ）はエッジ装置（ｒ＝３）のスロットパターン、（ｄ）はエッジ装置（ｒ＝４）のスロットパターンを示している。
Next, processing results obtained by applying the passing time calculation processing in step S2 described above to the
エッジ装置１１０（ｒ＝１）のスロットパターンを示した図６の（ａ）を参照して説明する。この表は、各部分パスｅの始点における信号通過開始時刻Ｃ（１，ｅ）および信号通過終了時刻Ｄ（１，ｅ）を示すものである。この表には、縦に、各部分パスｅの上り方向および下り方向を示すスロット６０１が示されており、横に、時間ｔを示すフレーム６０２が示されている。なお、フレーム６０２内の数値はフレーム右端の数値を示している。例えばスロットが「１→１０」、フレームが「ｔ＝０〜１」の場合、この表には「１」が記載されている（信号出力時間ｓ（ｒ）＝１なので実際には「１１１１」と記載）。これは、エッジ装置（ｒ＝１）が出力した光信号が、部分パスｅ１の始点において、エッジ装置（ｒ＝１）から分岐ノード（ｎ＝１０）に向けた方向で、「ｔ＝０〜１」の間で出力されたことを示している。
This will be described with reference to FIG. 6A showing the slot pattern of the edge device 110 (r = 1). This table shows the signal passage start time C (1, e) and the signal passage end time D (1, e) at the start point of each partial path e. In this table, a
また、スロットが「１０→２」、フレームが「ｔ＝１〜２」の場合、表中に「１」が記載されている。これは、エッジ装置（ｒ＝１）が出力した光信号が、部分パスｅ２の始点において、分岐ノード（ｎ＝１０）からエッジ装置（ｒ＝２）に向けた方向で、「ｔ＝１〜２」の間で通過したことを示している。このとき、この光信号が部分パスｅ１を通過する際に遅延時間ｄ（ｅ１）＝１が生じている。この遅延時間ｄ（ｅ１）が表中の矢印６０３で示されている。
When the slot is “10 → 2” and the frame is “t = 1 to 2”, “1” is described in the table. This is because the optical signal output by the edge device (r = 1) is in the direction from the branch node (n = 10) to the edge device (r = 2) at the start point of the partial path e2, “t = 1 to 2 ". At this time, a delay time d (e1) = 1 occurs when the optical signal passes through the partial path e1. This delay time d (e1) is indicated by an
さらに、スロットが「１０→１１」、フレームが「ｔ＝１〜２」の場合、表中に「１」が記載されており、これは、分岐ノード（ｎ＝１０）で光信号が分岐ノード（ｎ＝１１）に向けて分岐したことを表している。分岐ノード（ｎ＝１１）に向けて分岐した光信号が部分パスｅ３を通過する際に遅延時間ｄ（ｅ３）＝１．５が生じる。この遅延時間ｄ（ｅ３）が表中の矢印６０４で示されている。したがって、例えばスロットが「１１→３」、フレームが「ｔ＝２．５〜３．５」の場合に記載されている「１」は、エッジ装置（ｒ＝１）から出力された光信号が部分パスｅ４の始点において、信号通過開始時刻Ｃ（１，ｅ４［11→3]）＝２．５と、信号通過終了時刻Ｄ（１，ｅ４［11→3］）＝３．５とを有することを示す。なお、ｅ［→］は部分パスｅにおける方向を示す。
Further, when the slot is “10 → 11” and the frame is “t = 1 to 2”, “1” is described in the table. This is a branch node (n = 10) and the optical signal is a branch node. It shows that it branched toward (n = 11). When an optical signal branched toward the branch node (n = 11) passes through the partial path e3, a delay time d (e3) = 1.5 occurs. This delay time d (e3) is indicated by an
図６の（ｂ）、（ｃ）および（ｄ）は、それぞれのエッジ装置（ｒ＝２，３，４）から出力される光信号の各部分パスｅにおける信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）を示すものである。各エッジ装置ｒはｔ＝０で光信号の出力を開始する。また、「２（２２２２）」，「３（３３３３）」，「４（４４４４）」は、それぞれｒ＝２，３，４のエッジ装置が出力する光信号を示している。 (B), (c), and (d) of FIG. 6 show the signal passage start time C (r, e) in each partial path e of the optical signal output from each edge device (r = 2, 3, 4). ) And signal passing end time D (r, e). Each edge device r starts outputting an optical signal at t = 0. Further, “2 (2222)”, “3 (3333)”, and “4 (4444)” indicate optical signals output from the edge devices with r = 2, 3, and 4, respectively.
次に、図４に示した信号転送可能時間帯算出装置１３０のＣＰＵ２４０の処理におけるステップＳ３のタイミング算出処理について図７を参照（適宜図１および図２参照）して説明する。図７は、図４に示したタイミング算出処理を示すフローチャートである。
まず、ＣＰＵ２４０のタイミング算出手段２４３は、第１のエッジ装置ｒを選択し、他のエッジ装置と組み合わせることを決定し（以下、選択決定と呼ぶ）、選択決定した第１のエッジ装置ｒのタイミング変数Ａ（ｒ），Ｂ（ｒ）を次式（５）および（６）で求める（ステップＳ２１）。ここで、第１のエッジ装置ｒは、例えば一様分布などの確率分布、または、予め定められている重みｈ（ｒ）に従って選択される。また、タイミング変数Ａ（ｒ），Ｂ（ｒ）は、それぞれ、各エッジ装置ｒにおける信号出力開始時刻および信号出力終了時刻（信号出力タイミング）を示すものである。
Ａ（ｒ）＝０ …（５）
Ｂ（ｒ）＝ｓ（ｒ）…（６）
Next, the timing calculation processing in step S3 in the processing of the
First, the timing calculation means 243 of the
A (r) = 0 (5)
B (r) = s (r) (6)
そして、タイミング算出手段２４３は、第１のエッジ装置ｒを選択決定したときと同様に、例えば一様分布などの確率分布、または、予め定められている重みｈ（ｒ）に従って、まだ選択決定していない別のエッジ装置ｒ′を選択決定する（ステップＳ２２）。
そして、タイミング算出手段２４３は、後記する時間間隔算出処理を実行する（ステップＳ２３）。これにより、ステップＳ２２で選択決定したエッジ装置ｒ′から出力される信号の信号通過開始時刻Ｃ（ｒ′）に所定の時間間隔β（ｒ′）を加算した時刻が、ステップＳ２２の前にすでに選択決定されているエッジ装置ｒから出力される信号の信号通過終了時刻Ｄ（ｒ）に連続するような部分パスｅを１つ以上設けるように、かつ、選択決定されたすべてのエッジ装置ｒから出力される信号が、各部分パスｅ上の同方向かつ同位置を同時刻に通過しないように、所定の時間間隔β（ｒ′）が算出される。
Then, the timing calculation means 243 still selects and determines according to a probability distribution such as a uniform distribution or a predetermined weight h (r), as in the case of selecting and determining the first edge device r. Another edge device r 'that has not been selected is selected and determined (step S22).
And the timing calculation means 243 performs the time interval calculation process mentioned later (step S23). As a result, the time obtained by adding the predetermined time interval β (r ′) to the signal passage start time C (r ′) of the signal output from the edge device r ′ selected and determined in step S22 is already set before step S22. One or more partial paths e that are continuous with the signal passage end time D (r) of the signal output from the selected edge device r are provided, and from all the selected edge devices r. A predetermined time interval β (r ′) is calculated so that the output signal does not pass the same direction and the same position on each partial path e at the same time.
そして、タイミング算出手段２４３は、信号通過開始時刻Ｃ（ｒ′，ｅ）および信号通過終了時刻Ｄ（ｒ′，ｅ）を次式（７）および（８）に従って書き換えると共に、エッジ装置ｒ′のタイミング変数Ａ（ｒ′），Ｂ（ｒ′）を次式（９）および（１０）で求める（ステップＳ２４）。
Ｃ（ｒ′，ｅ）：＝Ｃ（ｒ′，ｅ）＋β（ｒ′） …（７）
Ｄ（ｒ′，ｅ）：＝Ｄ（ｒ′，ｅ）＋β（ｒ′） …（８）
Ａ（ｒ′）＝β（ｒ′） …（９）
Ｂ（ｒ′）＝ｓ（ｒ′）＋β（ｒ′）…（１０）
これにより、すでに選択決定されたエッジ装置ｒから出力される光信号同士は、各部分パスｅ上の同方向かつ同位置を同時刻に通過することがなくなる。
The timing calculation means 243 rewrites the signal passage start time C (r ′, e) and the signal passage end time D (r ′, e) according to the following equations (7) and (8) and Timing variables A (r ′) and B (r ′) are obtained by the following equations (9) and (10) (step S24).
C (r ′, e): = C (r ′, e) + β (r ′) (7)
D (r ′, e): = D (r ′, e) + β (r ′) (8)
A (r ′) = β (r ′) (9)
B (r ′) = s (r ′) + β (r ′) (10)
As a result, the optical signals output from the edge devices r that have already been selected and determined do not pass through the same direction and the same position on each partial path e at the same time.
そして、タイミング算出手段２４３は、すべてのエッジ装置ｒを選択決定したか否かを判定する（ステップＳ２５）。すべてのエッジ装置ｒを選択決定していない場合（ステップＳ２５：Ｎｏ）、タイミング算出手段２４３は、ステップＳ２２に戻る。一方、すべてのエッジ装置ｒを選択決定した場合（ステップＳ２５：Ｙｅｓ）、タイミング算出手段２４３は、ステップＳ２１で選択決定した第１のエッジ装置ｒをあらためてｒ′として選択決定する（ステップＳ２６）。
Then, the
そして、タイミング算出手段２４３は、再び、時間間隔算出処理を実行し（ステップＳ２７）、求めた所定の時間間隔β（ｒ′）をΔとする（ステップＳ２８）。これにより、すべてのエッジ装置ｒから、信号出力時間ｓ（ｒ）の光信号を時間間隔Δを周期として連続して出力可能とする信号転送可能時間帯を決定することができる。
そして、タイミング算出手段２４３は、すべてのエッジ装置ｒのＡ（ｒ）、Ｂ（ｒ）、Ｃ（ｒ，ｅ）、Ｄ（ｒ，ｅ）およびΔを転送制御手段２４５およびＨＤＤ２３０に出力する（ステップＳ２９）。
そして、転送制御手段２４５は、すべてのエッジ装置ｒのＡ（ｒ）、Ｂ（ｒ）、Ｃ（ｒ，ｅ）、Ｄ（ｒ，ｅ）およびΔに基づいた転送タイミングを入出力手段２１０を介して各エッジ装置ｒに通知する。各エッジ装置ｒは、通知された転送タイミングをそれぞれ記憶して、記憶された転送タイミングに基づいて光信号を出力することとなる。
Then, the
Then, the
Then, the transfer control means 245 sends the transfer timing based on A (r), B (r), C (r, e), D (r, e) and Δ of all edge devices r to the input / output means 210. To each edge device r. Each edge device r stores the notified transfer timing and outputs an optical signal based on the stored transfer timing.
次に、前記したステップＳ２３およびステップＳ２７の時間間隔算出処理について図８を参照（適宜図２および図７参照）して説明する。図８は、図７に示した時間間隔算出処理を示すフローチャートである。
まず、タイミング算出手段２４３は、この時間間隔算出処理の前に選択決定したエッジ装置ｒ′について、次式（１１）で表される時間間隔と、すでに選択決定されているすべてのエッジ装置ｒに関する次式（１２）で表される時間間隔との重なりが、すべての部分パスｅで生じないように所定時間間隔β（ｒ′）を求める（ステップＳ３１）。
｛Ｃ（ｒ′，ｅ）＋β（ｒ′）｝≦ｔ≦｛Ｄ（ｒ′，ｅ）＋β（ｒ′）｝ …（１１）
Ｃ（ｒ，ｅ）≦ｔ≦Ｄ（ｒ，ｅ） …（１２）
Next, the time interval calculation processing in steps S23 and S27 described above will be described with reference to FIG. 8 (refer to FIGS. 2 and 7 as appropriate). FIG. 8 is a flowchart showing the time interval calculation process shown in FIG.
First, for the edge device r ′ selected and determined before this time interval calculation processing, the timing calculation means 243 relates to the time interval represented by the following equation (11) and all the edge devices r that have already been selected and determined. The predetermined time interval β (r ′) is obtained so that the overlap with the time interval represented by the following equation (12) does not occur in all the partial paths e (step S31).
{C (r ′, e) + β (r ′)} ≦ t ≦ {D (r ′, e) + β (r ′)} (11)
C (r, e) ≦ t ≦ D (r, e) (12)
次に、タイミング算出手段２４３は、エッジ装置ｒ′に関して信号通過開始時刻Ｃ（ｒ′，ｅ）および信号通過終了時刻Ｄ（ｒ′，ｅ）を仮に次式（１３）および（１４）によって変更する。
Ｃ（ｒ′，ｅ）＋β（ｒ′） …（１３）
Ｄ（ｒ′，ｅ）＋β（ｒ′） …（１４）
そして、この仮に変更された信号通過開始時刻｛Ｃ（ｒ′，ｅ）＋β（ｒ′）｝と、すでに選択決定されているいずれかのエッジ装置ｒの信号通過終了時刻Ｄ（ｒ，ｅ）とが等しくなる部分パスｅが存在するときの時間間隔β（ｒ′）を抽出する。この抽出された時間間隔β（ｒ′）のうち、仮に変更された信号通過終了時刻｛Ｄ（ｒ′，ｅ）＋β（ｒ′）｝の最大値が最小となる時間間隔β（ｒ′）を求める（以上ステップＳ３２）。
Next, the timing calculation means 243 temporarily changes the signal passing start time C (r ′, e) and the signal passing end time D (r ′, e) for the edge device r ′ by the following equations (13) and (14). To do.
C (r ′, e) + β (r ′) (13)
D (r ′, e) + β (r ′) (14)
The temporarily changed signal passage start time {C (r ′, e) + β (r ′)} and the signal passage end time D (r, e) of any edge device r that has already been selected and determined. The time interval β (r ′) when there is a partial path e with equal to is extracted. Among the extracted time intervals β (r ′), the time interval β (r ′) at which the maximum value of the changed signal passing end time {D (r ′, e) + β (r ′)} is minimized. (Step S32).
次に、図７に示したタイミング算出処理の処理過程および処理結果の具体例について図９および図１０を参照（適宜図６乃至図８参照）して説明する。図９は図８に示した時間間隔算出処理の処理過程を示す説明図であり、図１０は図７に示したタイミング算出処理の処理結果を示す説明図である。 Next, a specific example of the process and result of the timing calculation process shown in FIG. 7 will be described with reference to FIGS. 9 and 10 (refer to FIGS. 6 to 8 as appropriate). FIG. 9 is an explanatory diagram showing a process of the time interval calculation process shown in FIG. 8, and FIG. 10 is an explanatory diagram showing a processing result of the timing calculation process shown in FIG.
図９に示す表では、タイミング算出手段２４３がエッジ装置ｒ′をランダムに選択し、（ｒ＝２）、（ｒ＝３）、（ｒ＝１）、（ｒ＝４）の順番に選択決定して、図６の（ａ）〜（ｄ）に示したスロットパターンが重ならないようにずらして配置した状態が示されている。 In the table shown in FIG. 9, the timing calculation means 243 randomly selects the edge device r ′ and selects and determines in the order of (r = 2), (r = 3), (r = 1), (r = 4). 6 shows a state where the slot patterns shown in FIGS. 6A to 6D are arranged so as not to overlap each other.
まず、エッジ装置（ｒ＝２）が選択決定されており、図８のステップＳ３２におけるＤ（ｒ，ｅ）の候補が探索される。次に、エッジ装置（ｒ＝３）が選択決定されており、ステップＳ３２における｛Ｃ（ｒ′，ｅ）＋β（ｒ′）｝の候補が探索される。この場合、β（３）＝−０．２５とすれば、次式（１５）が成り立つ部分パスｅ（ｅ１）が存在することになる。
Ｃ（３，ｅ）＋β（３）＝Ｄ（２，ｅ） …（１５）
First, the edge device (r = 2) is selected and determined, and the candidate for D (r, e) in step S32 in FIG. 8 is searched. Next, the edge device (r = 3) is selected and determined, and a candidate for {C (r ′, e) + β (r ′)} in step S32 is searched. In this case, if β (3) = − 0.25, there is a partial path e (e1) that satisfies the following expression (15).
C (3, e) + β (3) = D (2, e) (15)
すなわち、図９において矢印９０１で指し示すポイントでは、スロット「１０→１」において、エッジ装置（ｒ＝２）から出力される光信号「２」と、エッジ装置（ｒ＝３）から出力される光信号「３」とが連続して配置されることになる。同様にして、ｒ＝１、ｒ＝４のエッジ装置のスロットパターンを続けてずらして重ね、その結果の最左端をフレーム１（ｔ＝０）に合わせると図９に示した状態となる。
That is, at the point indicated by the
これによれば、符号９０２で示したスロット「１→１０」における光信号「１」、符号９０３で示したスロット「３→１１」における光信号「３」、符号９０４で示したスロット「２→１０」における光信号「２」、符号９０５で示したスロット「４→１１」における光信号「４」を、表に示されたフレームタイミングで通過させれば、各光信号は、各部分パスｅ上の同方向かつ同位置を同時刻に通過することがないことが理解される。
According to this, the optical signal “1” in the slot “1 → 10” indicated by the
さらに、タイミング算出手段２４３がエッジ装置ｒをすべて選択決定した後、再び、最初に選択決定したｒ＝２のエッジ装置をｒ′として選択決定してβ（ｒ′）＝Δを求め、エッジ装置ｒのＡ（ｒ）、Ｂ（ｒ）と共に出力した結果を、図１０の表に示す。
図１０に示すように、符号１００１で示されるスロット「１→１０」において、符号１００２で示されるフレーム「ｔ＝０〜１」で光信号「１」が出力されている。
Further, after the timing calculation means 243 selects and decides all the edge devices r, the edge device of r = 2 that was initially selected and decided again is selected and decided as r ′ to obtain β (r ′) = Δ. The results output together with A (r) and B (r) of r are shown in the table of FIG.
As shown in FIG. 10, the optical signal “1” is output in the frame “t = 0 to 1” indicated by the
一方、時間間隔算出処理（ステップＳ２７）においてΔ＝６であることが分かるので、符号１００１で示されるスロット「１→１０」において、符号１００３で示されるフレーム「ｔ＝６〜７」で光信号「１」が出力される。
すべてのタイミング算出処理結果をまとめると、エッジ装置（ｒ＝１）は、式（１６）で示される時刻ＴSに光信号の出力を開始し、式（１７）で示される時刻ＴEに光信号の出力を終了すればよいこととなる。
ＴS（１）＝Ａ（１）＋ｋΔ （ｋ＝０，１，２，…） …（１６）
ＴE（１）＝Ｂ（１）＋ｋΔ （ｋ＝０，１，２，…） …（１７）
さらに、式（１６）および式（１７）を、すべてのエッジ装置ｒに対して一般化すると、式（１８）および式（１９）が得られる。
ＴS（ｒ）＝Ａ（ｒ）＋ｋΔ （ｋ＝０，１，２，…） …（１８）
ＴE（ｒ）＝Ｂ（ｒ）＋ｋΔ （ｋ＝０，１，２，…） …（１９）
On the other hand, since Δ = 6 is found in the time interval calculation process (step S27), in the slot “1 → 10” indicated by the
When all the timing calculation processing results are put together, the edge device (r = 1) starts outputting an optical signal at time T S represented by equation (16), and light at time T E represented by equation (17). It suffices to end the signal output.
T S (1) = A (1) + kΔ (k = 0, 1, 2,...) (16)
T E (1) = B (1) + kΔ (k = 0, 1, 2,...) (17)
Furthermore, generalizing equation (16) and equation (17) for all edge devices r yields equation (18) and equation (19).
T S (r) = A (r) + kΔ (k = 0, 1, 2,...) (18)
T E (r) = B (r) + kΔ (k = 0, 1, 2,...) (19)
なお、信号転送可能時間帯算出装置１３０は、一般的なコンピュータに、前記した各ステップを実行させるための信号転送可能時間帯算出プログラムを実行することで実現することもできる。この信号転送可能時間帯算出プログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体に書き込んで配布することも可能である。この記録媒体を読み取り可能な情報処理装置は、信号転送可能時間帯算出プログラムに基づいた各機能を実現することができる。
The signal transfer time
第１の実施形態の信号転送可能時間帯算出装置１３０によれば、各エッジ装置ｒから出力される光信号が相互干渉することがないので、信号の衝突を防止することができる。また、信号転送可能時間帯算出装置１３０が記憶する接続情報として、部分パスｅ同士の接続関係のみを用いたので、どのノードｎを通過するかに関する情報を省略して記憶データ量を低減できる。また、タイミング算出手段２４３は、選択すべきエッジ装置ｒをランダムに選択するので、計算量を抑制し、転送可能時間帯を迅速に算出できる。
According to the signal transferable time
（第２の実施形態）
前記した第１の実施形態では、通過時刻算出手段２４１の実行する通過時刻算出処理において、信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）を部分パスｅの始点に関連付けることとしたが、関連付けるポイントは部分パスｅの始点に限定されるものではない。以下に、部分パスｅの終点に関連付ける実施形態を第２の実施形態として説明する。
(Second Embodiment)
In the first embodiment described above, in the passage time calculation process executed by the passage time calculation means 241, the signal passage start time C (r, e) and the signal passage end time D (r, e) are used as the starting points of the partial path e. However, the associated point is not limited to the starting point of the partial path e. Hereinafter, an embodiment associated with the end point of the partial path e will be described as a second embodiment.
第２の実施形態の信号転送可能時間帯算出装置は、通過時刻算出処理（図５参照）のアルゴリズムが異なる点を除いて、図２に示した信号転送可能時間帯算出装置１３０と同じ構成なので、図面を省略し、図２と同じ構成には同じ符号を付して説明を省略する。
次に、本発明の第２の実施形態に係る信号転送可能時間帯算出装置の行う通過時刻算出処理について図１１を参照して説明する。図１１は、本発明の第２の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行する通過時刻算出処理を示すフローチャートである。なお、信号出力時間２３５は、信号出力継続時間とし、すべてのエッジ装置ｒの信号出力時間ｓ（ｒ）はすべて「１」とする。
The signal transferable time zone calculation device of the second embodiment has the same configuration as the signal transferable time
Next, a passage time calculation process performed by the signal transferable time zone calculation apparatus according to the second embodiment of the present invention will be described with reference to FIG. FIG. 11 is a flowchart showing passage time calculation processing executed by the CPU of the signal transferable time zone calculation device according to the second embodiment of the present invention. The
まず、ＣＰＵ２４０の通過時刻算出手段２４１は、エッジ装置ｒを選択する（ステップＳ４１）。そして、通過時刻算出手段２４１は、選択したエッジ装置ｒを始点とする部分パスｅ′の終点に関連付けて信号通過開始時刻Ｃ（ｒ，ｅ′）および信号通過終了時刻Ｄ（ｒ，ｅ′）を前記した式（１）および（２）で求める（ステップＳ４２）。
なお、部分パスｅ′が複数ある場合にはそれぞれ求める。
First, the passage
If there are a plurality of partial paths e ′, each is obtained.
続けて、通過時刻算出手段２４１は、部分パスｅ′の終点を始点とする部分パスｅ″が存在するか否かを判定する（ステップＳ４３）。部分パスｅ″が存在する場合（ステップＳ４３：Ｙｅｓ）、通過時刻算出手段２４１は、部分パスｅ″の終点に関連付けて信号通過開始時刻Ｃ（ｒ，ｅ″）および信号通過終了時刻Ｄ（ｒ，ｅ″）を次式（２０）および（２１）で求める（ステップＳ４４）。
Ｃ（ｒ，ｅ″）＝Ｃ（ｒ，ｅ′）＋ｄ（ｅ″） …（２０）
Ｄ（ｒ，ｅ″）＝Ｄ（ｒ，ｅ′）＋ｄ（ｅ″） …（２１）
なお、部分パスｅ″が複数ある場合にはそれぞれ求める。
Subsequently, the passage
C (r, e ″) = C (r, e ′) + d (e ″) (20)
D (r, e ″) = D (r, e ′) + d (e ″) (21)
Note that, when there are a plurality of partial paths e ″, each is obtained.
続けて、通過時刻算出手段２４１は、部分パスｅ″の終点を始点とする部分パスが存在するか否かを判定する（ステップＳ４５）。部分パスｅ″の終点を始点とする部分パスが存在する場合（ステップＳ４５：Ｙｅｓ）、通過時刻算出手段２４１は、これまでの部分パス「ｅ″」をあらためて部分パス「ｅ′」に置き換え（ステップＳ４６）、ステップＳ４３に戻る。 Subsequently, the passage time calculation means 241 determines whether or not there is a partial path starting from the end point of the partial path e ″ (step S45). A partial path starting from the end point of the partial path e ″ exists. If so (step S45: Yes), the passage time calculation means 241 replaces the partial path “e ″” so far with the partial path “e ′” (step S46), and returns to step S43.
一方、部分パスｅ″の終点を始点とする部分パスが存在しない場合（ステップＳ４５：Ｎｏ）、および、部分パスｅ″が存在しない場合（ステップＳ４３：Ｎｏ）、通過時刻算出手段２４１は、すべてのエッジ装置ｒを選択したか否かを判定する（ステップＳ４７）。すべてのエッジ装置ｒを選択した場合（ステップＳ４７：Ｙｅｓ）、通過時刻算出手段２４１は、通過時刻算出処理を終了し、各エッジ装置ｒから出力される信号の各部分パスｅの終点における信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）をタイミング算出手段２４３に出力する。一方、すべてのエッジ装置ｒを選択していない場合（ステップＳ４７：Ｎｏ）、通過時刻算出手段２４１は、ステップＳ４１に戻る。
On the other hand, when there is no partial path starting from the end point of the partial path e ″ (step S45: No) and when the partial path e ″ does not exist (step S43: No), all the passage time calculation means 241 It is determined whether or not the edge device r is selected (step S47). When all the edge devices r have been selected (step S47: Yes), the passage
次に、図１２を参照して第２の実施形態の効果を説明する。図１２は、図１１に示したフローチャートを説明するための説明図であり、（ａ）は比較例、（ｂ）は第２の実施形態を示している。図１２では、図１に示したネットワークシステム１００が簡略化されて示されている。図１２の（ａ）に示した比較例では、信号通過開始時刻Ｃ（ｒ，ｅ）および信号通過終了時刻Ｄ（ｒ，ｅ）を部分パスｅの始点に関連付けることを特徴とし、一方、図１２の（ｂ）に示した第２の実施形態では、部分パスｅの終点に関連付けることを特徴としている。本発明では、ツリー構造のネットワークについて、基準とする部分パスｅに接続している部分パスｅ′を新たに見つけた場合、その新たな部分パスｅ′をあらためて基準とする部分パスｅに置き換えて利用することにより、経路探索を実行することとしている。このとき、部分パスｅにおける遅延時間ｄ（ｅ）を考慮すると、図１２の（ａ）の比較例では、変数として、ｅ，ｅ′，ｅ″の３種類が必要となる。一方、図１２の（ｂ）の第２の実施形態では、変数として、ｅ′，ｅ″の２種類で済むこととなる。
Next, the effect of the second embodiment will be described with reference to FIG. FIG. 12 is an explanatory diagram for explaining the flowchart shown in FIG. 11, (a) shows a comparative example, and (b) shows a second embodiment. In FIG. 12, the
（第３の実施形態）
前記した第１の実施形態では、タイミング算出手段２４３の実行するタイミング算出処理において、所定のエッジ装置ｒに対して別のエッジ装置ｒ′をランダムに選択決定した状態で所定の時間間隔β（ｒ′）を求める（以下、ランダム方式という）こととしたが、所定のエッジ装置ｒに対して別のエッジ装置ｒ′を選択決定する方式は、ランダム方式に限定されるものではない。以下に、最適な組み合わせを見つける方式（以下、ｇｒｅｅｄｙ方式という）を第３の実施形態として説明する。
(Third embodiment)
In the first embodiment described above, in the timing calculation process executed by the
第３の実施形態の信号転送可能時間帯算出装置は、タイミング算出処理（図７参照）のアルゴリズムが異なる点を除いて、図２に示した信号転送可能時間帯算出装置１３０と同じ構成なので、図面を省略し、図２と同じ構成には同じ符号を付して説明を省略する。
次に、本発明の第３の実施形態に係る信号転送可能時間帯算出装置の行うタイミング算出処理について図１３を参照（適宜図２参照）して説明する。図１３は、本発明の第３の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行するタイミング算出処理を示すフローチャートである。
The signal transferable time zone calculation device of the third embodiment has the same configuration as the signal transferable time
Next, timing calculation processing performed by the signal transferable time zone calculation apparatus according to the third embodiment of the present invention will be described with reference to FIG. 13 (refer to FIG. 2 as appropriate). FIG. 13 is a flowchart showing timing calculation processing executed by the CPU of the signal transferable time zone calculation apparatus according to the third embodiment of the present invention.
まず、ＣＰＵ２４０のタイミング算出手段２４３は、第１のエッジ装置ｒを選択決定し、選択決定した第１のエッジ装置ｒのタイミング変数Ａ（ｒ），Ｂ（ｒ）を前記した式（５）および式（６）で求める（ステップＳ５１）。ここで、第１のエッジ装置ｒは、例えば一様分布などの確率分布、または、予め定められている重みｈ（ｒ）に従って選択される。
そして、タイミング算出手段２４３は、第１のエッジ装置ｒを選択決定する際と同様に、例えば一様分布などの確率分布、または、予め定められている重みｈ（ｒ）に従って、まだ選択決定していない別のエッジ装置ｒ′を選択する（選択決定はしない）（ステップＳ５２）。
First, the timing calculation means 243 of the
Then, the timing calculation means 243 still selects and determines according to a probability distribution such as a uniform distribution or a predetermined weight h (r), as in the case of selecting and determining the first edge device r. Another edge device r 'that has not been selected is selected (no selection is determined) (step S52).
そして、タイミング算出手段２４３は、前記した時間間隔算出処理を実行する（ステップＳ５３）。これにより、ステップＳ５２で選択したエッジ装置ｒ′から出力される信号の信号通過開始時刻Ｃ（ｒ′，ｅ）に所定の時間間隔β（ｒ′）を加算した時刻が、ステップＳ５２の前にすでに選択決定されているエッジ装置ｒから出力される信号の信号通過終了時刻Ｄ（ｒ，ｅ）に連続するような部分パスｅを１つ以上設けるように、かつ、選択決定されたすべてのエッジ装置ｒから出力される信号が、各部分パスｅ上の同方向かつ同位置を同時刻に通過しないように、所定の時間間隔β（ｒ′）が算出される。
Then, the
次に、タイミング算出手段２４３は、まだ選択決定していない別のエッジ装置ｒ′をすべて選択したか否かを判定する（ステップＳ５４）。まだ選択決定していない別のエッジ装置ｒ′をすべて選択していない場合（ステップＳ５４：Ｎｏ）、タイミング算出手段２４３は、ステップＳ５２に戻る。一方、まだ選択決定していない別のエッジ装置ｒ′をすべて選択した場合（ステップＳ５４：Ｙｅｓ）、タイミング算出手段２４３は、ステップＳ５５に進む。
Next, the
このステップＳ５５に進んだ状態では、すでに選択決定されているエッジ装置ｒに対して、選択決定されていないすべての別のエッジ装置ｒ′が組み合わせる候補として挙げられていることになる。そして、前記した式（１３）および（１４）に示されるように、信号通過開始時刻Ｃ（ｒ′，ｅ）および信号通過終了時刻Ｄ（ｒ′，ｅ）を仮に変更している。また、β（ｒ′）も候補の数だけ存在している。
そこで、タイミング算出手段２４３は、求めた時間間隔β（ｒ′）のうち、仮に変更された信号通過終了時刻｛Ｄ（ｒ′，ｅ）＋β（ｒ′）｝の最大値が最小となるエッジ装置ｒ′を選択決定する。このとき、タイミング算出手段２４３は、選択決定したエッジ装置ｒ′に対して、仮変更だった信号通過開始時刻Ｃ（ｒ′，ｅ）および信号通過終了時刻Ｄ（ｒ′，ｅ）を前記した式（７）および（８）に従って書き換える（正式に変更する）と共に、エッジ装置ｒ′のタイミング変数Ａ（ｒ′），Ｂ（ｒ′）を前記した式（９）および（１０）で求める。
これにより、すでに選択決定されたエッジ装置ｒから出力される光信号同士は、各部分パスｅ上の同方向かつ同位置を同時刻に通過することがなくなる。
In the state of proceeding to step S55, all the other edge devices r ′ that have not been selected and determined are listed as candidates to be combined with the edge device r that has already been selected and determined. Then, as shown in the equations (13) and (14), the signal passage start time C (r ′, e) and the signal passage end time D (r ′, e) are temporarily changed. In addition, there are as many β (r ′) candidates as possible.
Therefore, the timing calculation means 243 has an edge that minimizes the maximum value of the signal passing end time {D (r ′, e) + β (r ′)} that is temporarily changed in the obtained time interval β (r ′). The device r 'is selected and determined. At this time, the timing calculation means 243 described the signal passing start time C (r ′, e) and the signal passing end time D (r ′, e), which were temporarily changed, for the selected edge device r ′. In addition to rewriting (formally changing) according to the equations (7) and (8), the timing variables A (r ′) and B (r ′) of the edge device r ′ are obtained by the equations (9) and (10) described above.
As a result, the optical signals output from the edge devices r that have already been selected and determined do not pass through the same direction and the same position on each partial path e at the same time.
ステップＳ５５に続けて、タイミング算出手段２４３は、すべてのエッジ装置ｒを選択決定したか否かを判定する（ステップＳ５６）。すべてのエッジ装置ｒを選択決定していない場合（ステップＳ５６：Ｎｏ）、タイミング算出手段２４３は、ステップＳ５２に戻る。一方、すべてのエッジ装置ｒを選択決定した場合（ステップＳ５６：Ｙｅｓ）、タイミング算出手段２４３は、ステップＳ５７〜ステップＳ６０の処理を実行する。このステップＳ５７〜ステップＳ６０の処理は、前記したステップＳ２６〜ステップＳ２９の処理と同一なので説明を省略する。
Subsequent to step S55, the
次に、前記したタイミング算出処理（図１３参照）の処理過程および処理結果の具体例について図１４乃至図１６を参照（適宜図６参照）して説明する。ここでは、図１３のフローチャートにおけるステップＳ５１で、タイミング算出手段２４３は、第１のエッジ装置ｒとして、ｒ＝１のエッジ装置を選択決定したものとする。この状態を図１４の（ａ）に示す。そして、タイミング算出手段２４３は、図１３のステップＳ５２〜ステップＳ５４を繰り返し実行することによって、ｒ′＝２，３，４を順次選択し、それぞれをｒ＝１のエッジ装置と仮に組み合わせる。このときの仮の組み合わせを、図１４の（ｂ），（ｃ）および（ｄ）にそれぞれ示す。
Next, a specific example of the process and result of the timing calculation process (see FIG. 13) will be described with reference to FIGS. 14 to 16 (see FIG. 6 as appropriate). Here, it is assumed that in step S51 in the flowchart of FIG. 13, the
例えばｒ′＝２のエッジ装置をｒ＝１のエッジ装置と仮に組み合わせた場合、図１４の（ｂ）に示すように、所定間隔β（２）＝０．７５となる。また、Ｄ（２，ｅ）とβ（２）との和の最大値は、符号１４０１で示すように「４．５」となる。
また、ｒ′＝４のエッジ装置をｒ＝１のエッジ装置と仮に組み合わせた場合、図１４の（ｃ）に示すように、所定間隔β（４）＝０となる。また、Ｄ（４，ｅ）とβ（４）との和の最大値は、符号１４０２で示すように「３．５」となる。
同様に、ｒ′＝３のエッジ装置をｒ＝１のエッジ装置と仮に組み合わせた場合、図１４の（ｄ）に示すように、所定間隔β（３）＝０となる。また、Ｄ（３，ｅ）とβ（３）との和の最大値は、符号１４０３で示すように「３．５」となる。
For example, when an edge device with r ′ = 2 is combined with an edge device with r = 1, as shown in FIG. 14B, the predetermined interval β (2) = 0.75. Also, the maximum value of the sum of D (2, e) and β (2) is “4.5” as indicated by
When the edge device with r ′ = 4 is combined with the edge device with r = 1, as shown in FIG. 14C, the predetermined interval β (4) = 0. Further, the maximum value of the sum of D (4, e) and β (4) is “3.5” as indicated by
Similarly, when an edge device with r ′ = 3 is combined with an edge device with r = 1, the predetermined interval β (3) = 0 as shown in FIG. Further, the maximum value of the sum of D (3, e) and β (3) is “3.5” as indicated by
これらをまとめると、Ｄ（ｒ′，ｅ）とβ（ｒ′）との和の最大値（４，５，３．５，３．５）のうち、最小となるのは「３．５」の場合である。このようになるのは、ｒ′＝３のエッジ装置の場合と、ｒ′＝４のエッジ装置の場合がある。どちらでも同等なので、ここでは、ｒ′＝３のエッジ装置を選択決定することとする。なお、このとき、ｒ′＝３のエッジ装置に対して、前記した式（７）〜（１０）が適用される。 In summary, among the maximum values (4, 5, 3.5, 3.5) of the sum of D (r ′, e) and β (r ′), the minimum is “3.5”. This is the case. This is the case for edge devices with r '= 3 and for edge devices with r' = 4. Since both are equal, here, the edge device of r ′ = 3 is selected and determined. At this time, the above equations (7) to (10) are applied to the edge device of r ′ = 3.
この状態では、すべてのエッジ装置ｒのうち、２つのエッジ装置（ｒ＝１，３）が選択決定されたこととなるので、次に選択決定すべきエッジ装置ｒ′の候補を探索すべく同様な操作（ステップＳ５２〜ステップＳ５５）を実行する。すなわち、図１５の（ａ）に示す状態を基本にして、ｒ′＝２，４を順次選択し、それぞれをｒ＝１，３のエッジ装置と仮に組み合わせる。このときの仮の組み合わせを、図１５の（ｂ）および（ｃ）にそれぞれ示す。 In this state, of all the edge devices r, two edge devices (r = 1, 3) have been selected and determined. Therefore, the same search is performed for a candidate for the edge device r ′ to be selected and determined next. Operations (steps S52 to S55) are executed. That is, on the basis of the state shown in FIG. 15A, r ′ = 2 and 4 are sequentially selected, and each is temporarily combined with the edge devices of r = 1 and 3. The temporary combinations at this time are shown in FIGS. 15B and 15C, respectively.
例えばｒ′＝２のエッジ装置をｒ＝１，３のエッジ装置と仮に組み合わせた場合、図１５の（ｂ）に示すように、所定間隔β（２）＝２．２５となる。また、Ｄ（２，ｅ）とβ（２）との和の最大値は、符号１５０１で示すように「６」となる。
また、ｒ′＝４のエッジ装置をｒ＝１，３のエッジ装置と仮に組み合わせた場合、図１５の（ｃ）に示すように、所定間隔β（４）＝２．５となる。また、Ｄ（４，ｅ）とβ（４）との和の最大値は、符号１５０２で示すように「６」となる。
For example, when an edge device of r ′ = 2 is combined with an edge device of r = 1, 3, a predetermined interval β (2) = 2.25 as shown in FIG. Further, the maximum value of the sum of D (2, e) and β (2) is “6” as indicated by
Further, when the edge device of r ′ = 4 is combined with the edge device of r = 1, 3 as shown in FIG. 15C, the predetermined interval β (4) = 2.5. The maximum value of the sum of D (4, e) and β (4) is “6” as indicated by
つまり、Ｄ（ｒ′，ｅ）とβ（ｒ′）との和の最大値（６，６）のうち、最小となるのは「６」の場合である。このようになるのは、ｒ′＝２のエッジ装置の場合と、ｒ′＝４のエッジ装置の場合がある。どちらでも同等なので、ここでは、ｒ′＝２のエッジ装置を選択決定することとする。なお、このとき、ｒ′＝２のエッジ装置に対して、前記した式（７）〜（１０）が適用される。 That is, among the maximum values (6, 6) of the sum of D (r ′, e) and β (r ′), the minimum is “6”. This is the case for edge devices with r ′ = 2 and for edge devices with r ′ = 4. Since both are equal, here, the edge device of r ′ = 2 is selected and determined. At this time, the above equations (7) to (10) are applied to the edge device of r ′ = 2.
この状態では、すべてのエッジ装置ｒのうち、３つのエッジ装置（ｒ＝１，３，２）が選択決定されたこととなるので、次に選択決定すべきエッジ装置は、ｒ′＝４のエッジ装置である。これに対して同様な操作（ステップＳ５２〜ステップＳ５５）を実行した場合には、図１６の（ａ）に示すように、所定間隔β（４）＝２．５となる。また、Ｄ（４，ｅ）とβ（４）との和の最大値は、６となる。 In this state, among all the edge devices r, three edge devices (r = 1, 3, 2) are selected and determined. Therefore, the edge device to be selected and determined next is r ′ = 4. Edge device. On the other hand, when a similar operation (step S52 to step S55) is executed, the predetermined interval β (4) = 2.5 as shown in FIG. The maximum value of the sum of D (4, e) and β (4) is 6.
図１６の（ａ）に示すように、符号１６０１で示したスロット「１→１０」における光信号「１」と、符号１６０２で示したスロット「３→１１」における光信号「３」とをｔ＝０のタイミングで、符号１６０３で示したスロット「２→１０」における光信号「２」をｔ＝２．２５で、符号１６０４で示したスロット「４→１１」における光信号「４」をｔ＝２．５のタイミングでそれぞれ出力させれば、各光信号は、各部分パスｅ上の同方向かつ同位置を同時刻に通過することがないことが理解される。
As shown in FIG. 16A, the optical signal “1” in the slot “1 → 10” indicated by
さらに、第１のエッジ装置ｒとして選択決定した、ｒ＝１のエッジ装置を次に選択すべきエッジ装置ｒ′と置き換えて、時間間隔算出処理（ステップＳ５８）を実行すると、図１６の（ｂ）に示すように、所定間隔β（１）＝Δ＝５となる。また、Ｄ（１，ｅ）とβ（１）との和の最大値は「６」となる。 Furthermore, when the edge device of r = 1 that is selected and determined as the first edge device r is replaced with the edge device r ′ to be selected next and the time interval calculation process (step S58) is executed, (b) of FIG. ), The predetermined interval β (1) = Δ = 5. In addition, the maximum value of the sum of D (1, e) and β (1) is “6”.
図１６の（ｂ）に示すように、符号１６０１で示されるスロット「１→１０」において、符号１６０５で示されるフレーム「ｔ＝０〜１」で光信号「１」が出力される。一方、時間間隔算出処理（ステップＳ５８）においてΔ＝５であることが分かるので、符号１６０１で示されるスロット「１→１０」において、符号１６０６で示されるフレーム「ｔ＝５〜６」で光信号「１」が出力される。なお、すべてのエッジ装置ｒは、前記した式（１８）で示される時刻ＴS（ｒ）に光信号の出力を開始し、前記した式（１９）で示される時刻ＴE（ｒ）に光信号の出力を終了する。
As shown in FIG. 16B, in the slot “1 → 10” indicated by
第３の実施形態によれば、タイミング算出処理を実行する際に、最適な組み合わせを抽出してエッジ装置ｒ′を選択決定するので、各エッジ装置ｒから出力される光信号の転送時間帯を最も効率よいものとすることができる。つまり、この方式（ｇｒｅｅｄｙ方式）の処理結果（Δ＝５）によれば、図１０に示したランダム方式の処理結果（Δ＝６）と比較して、Δを短くすることが可能である。 According to the third embodiment, when the timing calculation process is executed, the optimum combination is extracted and the edge device r ′ is selected and determined. Therefore, the transfer time zone of the optical signal output from each edge device r is determined. It can be the most efficient. That is, according to the processing result (Δ = 5) of this method (greedy method), Δ can be shortened as compared with the processing result (Δ = 6) of the random method shown in FIG.
（第４の実施形態）
前記した第１乃至第３の実施形態では、通過時刻算出手段２４１の実行する通過時刻算出処理において、信号通過開始時刻Ｃ（ｒ）および信号通過終了時刻Ｄ（ｒ）を部分パスｅに関連付けることとした。以下に、ノードｎに関連付ける実施形態を第４の実施形態として説明する。
(Fourth embodiment)
In the first to third embodiments, the signal passage start time C (r) and the signal passage end time D (r) are associated with the partial path e in the passage time calculation process executed by the passage
第４の実施形態の信号転送可能時間帯算出装置は、通過時刻算出処理（図５参照）のアルゴリズムが異なる点を除いて、図２に示した信号転送可能時間帯算出装置１３０と同じ構成なので、図面を省略し、図２と同じ構成には同じ符号を付して説明を省略する。
次に、本発明の第４の実施形態に係る信号転送可能時間帯算出装置の行う通過時刻算出処理について図１７を参照して説明する。図１７は、本発明の第４の実施形態に係る信号転送可能時間帯算出装置のＣＰＵが実行する通過時刻算出処理を示すフローチャートである。なお、信号出力時間２３５は、信号出力継続時間とし、すべてのエッジ装置ｒの信号出力時間ｓ（ｒ）はすべて「１」とする。
The signal transferable time zone calculation device of the fourth embodiment has the same configuration as the signal transferable time
Next, a passage time calculation process performed by the signal transferable time zone calculation apparatus according to the fourth embodiment of the present invention will be described with reference to FIG. FIG. 17 is a flowchart showing passage time calculation processing executed by the CPU of the signal transferable time zone calculation device according to the fourth embodiment of the present invention. The
まず、ＣＰＵ２４０の通過時刻算出手段２４１は、エッジ装置ｒを選択する（ステップＳ７１）。そして、通過時刻算出手段２４１は、選択したエッジ装置ｒを始点とする部分パスｅの終点であるノードをｎとする（ステップＳ７２）。そして、通過時刻算出手段２４１は、ノードｎに関連付けて信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）を次式（２２）および（２３）で求める（ステップＳ７３）。
Ｃ（ｒ，ｎ）＝ｄ（ｅ） …（２２）
Ｄ（ｒ，ｎ）＝ｄ（ｅ）＋ｓ（ｒ） …（２３）
First, the passage
C (r, n) = d (e) (22)
D (r, n) = d (e) + s (r) (23)
続けて、通過時刻算出手段２４１は、ノードｎを始点とする部分パスｅ′が存在するか否かを判定する（ステップＳ７４）。部分パスｅ′が存在する場合（ステップＳ７４：Ｙｅｓ）、通過時刻算出手段２４１は、部分パスｅ′の終点のノードをｎ′として（ステップＳ７５）、ノードｎ′に関連付けて信号通過開始時刻Ｃ（ｒ，ｎ′）および信号通過終了時刻Ｄ（ｒ，ｎ′）を次式（２４）および（２５）で求める（ステップＳ７６）。
Ｃ（ｒ，ｎ′）＝Ｃ（ｒ，ｎ）＋ｄ（ｅ′） …（２４）
Ｄ（ｒ，ｎ′）＝Ｄ（ｒ，ｎ）＋ｄ（ｅ′） …（２５）
なお、ノードｎ′が複数ある場合にはそれぞれ求める。
Subsequently, the passage
C (r, n ′) = C (r, n) + d (e ′) (24)
D (r, n ′) = D (r, n) + d (e ′) (25)
In addition, when there are a plurality of nodes n ′, each is obtained.
続けて、通過時刻算出手段２４１は、ノードｎ′を始点とする部分パスが存在するか否かを判定する（ステップＳ７７）。ノードｎ′を始点とする部分パスが存在する場合（ステップＳ７７：Ｙｅｓ）、通過時刻算出手段２４１は、これまでのノード「ｎ′」をあらためてノード「ｎ」に置き換え（ステップＳ７８）、ステップＳ７４に戻る。
Subsequently, the passage
一方、ノードｎ′を始点とする部分パスが存在しない場合（ステップＳ７７：Ｎｏ）、および、ノードｎを始点とする部分パスｅ′が存在しない場合（ステップＳ７４：Ｎｏ）、通過時刻算出手段２４１は、すべてのエッジ装置ｒを選択したか否かを判定する（ステップＳ７９）。すべてのエッジ装置ｒを選択した場合（ステップＳ７９：Ｙｅｓ）、通過時刻算出手段２４１は、通過時刻算出処理を終了し、各エッジ装置ｒから出力される信号の各ノードｎにおける信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）をタイミング算出手段２４３に出力する。一方、すべてのエッジ装置ｒを選択していない場合（ステップＳ７９：Ｎｏ）、通過時刻算出手段２４１は、ステップＳ７１に戻る。
On the other hand, when there is no partial path starting from the node n ′ (step S77: No) and when there is no partial path e ′ starting from the node n (step S74: No), the passage time calculation means 241 Determines whether all edge devices r have been selected (step S79). When all the edge devices r have been selected (step S79: Yes), the passage
なお、前記した通過時刻算出処理のフローチャートにおいて、ステップＳ７１において選択したエッジ装置の識別変数「ｒ」を便宜上、ノードの識別変数「ｎ」に読み替えると共に、Ｃ（ｒ，ｎ）＝０，Ｄ（ｒ，ｎ）＝ｓ（ｒ）としてもよい。この場合の例えばＣ（ｒ，ｎ）の表記では、Ｃ（ｒ，ｎ）のカッコ内の「ｒ」は信号を出力するエッジ装置の識別変数、同じくカッコ内の「ｎ」は、部分パスｅの始点としてのノードの変数をそれぞれ示している。そして、このときの「ｎ」を始点とする部分パスｅの終点であるノードを「ｎ′」と読み替えることとする。この場合には、ノードｎ′に関連付けて信号通過開始時刻Ｃ（ｒ，ｎ′）および信号通過終了時刻Ｄ（ｒ，ｎ′）を前記した式（２４）および（２５）に代えて次式（２６）および（２７）で求めることができる。
Ｃ（ｒ，ｎ′）＝Ｃ（ｒ，ｎ）＋ｄ（ｅ） …（２６）
Ｄ（ｒ，ｎ′）＝Ｄ（ｒ，ｎ）＋ｄ（ｅ） …（２７）
In the flow chart of the passage time calculation process described above, the identification variable “r” of the edge device selected in step S71 is replaced with the identification variable “n” of the node for convenience, and C (r, n) = 0, D ( r, n) = s (r). In this case, for example, in the notation of C (r, n), “r” in parentheses of C (r, n) is an identification variable of an edge device that outputs a signal, and “n” in parentheses is a partial path e. Each node variable is shown as a starting point. The node that is the end point of the partial path e starting from “n” at this time is read as “n ′”. In this case, the signal passage start time C (r, n ′) and the signal passage end time D (r, n ′) are associated with the node n ′ in place of the above equations (24) and (25), and (26) and (27).
C (r, n ′) = C (r, n) + d (e) (26)
D (r, n ′) = D (r, n) + d (e) (27)
次に、前記した通過時刻算出処理（図１７参照）を、図１に示したネットワークシステム１００に適用した処理結果を図１８を参照（適宜図１参照）して説明する。図１８は、図１７に示した通過時刻算出処理の処理結果を示す説明図であり、（ａ）はｒ＝１のスロットパターン、（ｂ）はｒ＝２のスロットパターン、（ｃ）はｒ＝３のスロットパターン、（ｄ）はｒ＝４のスロットパターンを示している。
Next, processing results obtained by applying the above passage time calculation process (see FIG. 17) to the
エッジ装置（ｒ＝１）のスロットパターンを示した図１８の（ａ）を参照して説明する。この表は、各ノードｎ（エッジ装置、分岐ノードを含む）における信号通過開始時刻Ｃ（１，ｎ）および信号通過終了時刻Ｄ（１，ｎ）を示すものである。この表には、縦に、各ノードｎを示すスロット１８０１が示されており、横に、時間ｔを示すフレーム１８０２が示されている。例えばスロットが「１」、フレームが「ｔ＝０〜１」の場合、表中に「Ｘ」が記載されている（信号出力時間ｓ（ｒ）＝１なので実際には「ＸＸＸＸ」と記載）。これは、エッジ装置（ｒ＝１）が出力した光信号が、エッジ装置（ｒ＝１）において、「ｔ＝０〜１」の間で出力されたことを示している。
Description will be made with reference to FIG. 18A showing the slot pattern of the edge device (r = 1). This table shows the signal passage start time C (1, n) and the signal passage end time D (1, n) at each node n (including edge devices and branch nodes). In this table, a
また、符号１８０３で示すスロット「１０」、符号１８０４で示すフレーム「ｔ＝１〜２」の場合、表中に「１」が記載されている（実際には「１１１１」と記載）。これは、エッジ装置（ｒ＝１）が出力した光信号が、部分パスｅ１を通過する際に遅延時間ｄ（ｅ１）＝１が生じたことを示している。同様に、スロットが「１１」、フレームが「ｔ＝２．５〜３．５」の場合、表中に「１」が記載されており、これは、エッジ装置（ｒ＝１）が出力した光信号が、部分パスｅ３を通過する際に遅延時間ｄ（ｅ３）＝１．５が生じたことを示している。
In the case of the slot “10” indicated by
図１８の（ｂ）、（ｃ）および（ｄ）は、それぞれのエッジ装置（ｒ＝２，３，４）から出力される光信号の各ノードｎにおける信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）を示すものである。なお、各エッジ装置ｒはｔ＝０で光信号「Ｘ（ＸＸＸＸ）」の出力を開始し、「２（２２２２）」，「３（３３３３）」，「４（４４４４）」は、それぞれｒ＝２，３，４のエッジ装置が出力する光信号に遅延時間を含めて示すものである。
(B), (c), and (d) of FIG. 18 show the signal passing start time C (r, n) at each node n of the optical signal output from each edge device (r = 2, 3, 4). And a signal passing end time D (r, n). Each edge device r starts outputting the optical signal “X (XXXX)” at t = 0, and “2 (2222)”, “3 (3333)”, and “4 (4444)” are r = The optical signals output from the
次に、図１８に示した信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）を用いたタイミング算出処理を説明する。
ランダム方式（図７参照）を適用する場合、図７に示すステップＳ２４のＣ（ｒ′，ｅ）をＣ（ｒ′，ｎ）に置き換えると共に、図８に示すステップＳ３１およびステップＳ３２のＣ（ｒ′，ｅ）およびＤ（ｒ′，ｅ）を、Ｃ（ｒ′，ｎ）およびＤ（ｒ′，ｎ）にそれぞれ置き換えた処理を実行することになる。
Next, timing calculation processing using the signal passage start time C (r, n) and the signal passage end time D (r, n) shown in FIG. 18 will be described.
When the random method (see FIG. 7) is applied, C (r ′, e) in step S24 shown in FIG. 7 is replaced with C (r ′, n), and C (r) in step S31 and step S32 shown in FIG. Processing in which r ', e) and D (r', e) are replaced with C (r ', n) and D (r', n), respectively, is executed.
また、ｇｒｅｅｄｙ方式（図１３参照）を適用する場合、図１３に示すステップＳ５５のＣ（ｒ′，ｅ）をＣ（ｒ′，ｎ）に置き換えると共に、図８に示すステップＳ３１およびステップＳ３２のＣ（ｒ′，ｅ）およびＤ（ｒ′，ｅ）を、Ｃ（ｒ′，ｎ）およびＤ（ｒ′，ｎ）にそれぞれ置き換えた処理を実行することになる。 When the greedy method (see FIG. 13) is applied, C (r ′, e) in step S55 shown in FIG. 13 is replaced with C (r ′, n), and in steps S31 and S32 shown in FIG. Processing is performed in which C (r ′, e) and D (r ′, e) are replaced with C (r ′, n) and D (r ′, n), respectively.
次に、ランダム方式（図７参照）またはｇｒｅｅｄｙ方式（図１３参照）を適用した場合の処理結果を図１９を参照して説明する。図１９は、図１８に示した通過時刻算出処理の結果を用いてタイミング算出処理を実行した場合の処理結果を示す説明図であり、（ａ）はランダム方式、（ｂ）はｇｒｅｅｄｙ方式を示している。 Next, processing results when the random method (see FIG. 7) or the greedy method (see FIG. 13) is applied will be described with reference to FIG. FIGS. 19A and 19B are explanatory diagrams illustrating processing results when the timing calculation processing is executed using the results of the passage time calculation processing illustrated in FIG. 18. FIG. 19A illustrates a random method, and FIG. 19B illustrates a greedy method. ing.
ランダム方式では、タイミング算出手段２４３はエッジ装置ｒ′をランダムに選択し、この例では（ｒ＝２）、（ｒ＝３）、（ｒ＝１）、（ｒ＝４）の順番に選択決定して、すべて選択決定した後、再び、ｒ＝２のエッジ装置ｒを選択決定してΔを求める。このときの処理結果を、図１９の（ａ）に示す。この図１９の（ａ）に示すように、符号１９０１で示されるスロット「１」において、符号１９０２で示されるフレーム「ｔ＝０〜１」で光信号「Ｘ」が出力されている。同様に、スロット「３」において、ｔ＝０．５のタイミングで光信号「Ｘ」が出力され、スロット「２」において、ｔ＝０．７５のタイミングで光信号「Ｘ」が出力され、スロット「４」において、ｔ＝３．５のタイミングで光信号「Ｘ」が出力されている。すなわち、エッジ装置ｒは、ｒ＝２，３，１，４の順番で光信号を出力する。
また、時間間隔算出処理（図８参照）においてΔ＝６であることが分かるので、符号１９０１で示されるスロット「１」において、符号１９０３で示されるフレーム「ｔ＝６〜７」で光信号「Ｘ」が出力される。
In the random method, the
In addition, since it is understood that Δ = 6 in the time interval calculation process (see FIG. 8), in the slot “1” indicated by
また、ｇｒｅｅｄｙ方式では、タイミング算出手段２４３はエッジ装置ｒ′を最適に選択して、（ｒ＝１）、（ｒ＝３）、（ｒ＝２）、（ｒ＝４）の順番に選択決定して、すべて選択した後、再び、ｒ＝１のエッジ装置ｒを選択決定してΔを求める。このときの処理結果を、図１９の（ｂ）に示す。この図１９の（ｂ）に示すように、符号１９０１で示されるスロット「１」において、符号１９０２で示されるフレーム「ｔ＝０〜１」で光信号「Ｘ」が出力されると共に、同じタイミングでスロット「３」において光信号「Ｘ」が出力される。同様に、スロット「２」において、ｔ＝２．２５のタイミングで光信号「Ｘ」が出力され、スロット「４」において、ｔ＝２．５のタイミングで光信号「Ｘ」が出力されている。すなわち、エッジ装置ｒは、ｒ＝１，３，２，４の順番で光信号を出力する。
また、時間間隔算出処理（図８参照）においてΔ＝５であることが分かるので、符号１９０１で示されるスロット「１」において、符号１９０４で示されるフレーム「ｔ＝５〜６」で光信号「Ｘ」が出力されると共に、同じタイミングでスロット「３」において光信号「Ｘ」が出力される。
In the greedy method, the
In addition, since it can be seen that Δ = 5 in the time interval calculation process (see FIG. 8), in the slot “1” indicated by
第４の実施形態によれば、通過時刻算出処理を実行する際に、部分パスｅに代えてノードｎを信号通過開始時刻Ｃ（ｒ，ｎ）および信号通過終了時刻Ｄ（ｒ，ｎ）に関連付けることとしたので、部分パスｅにおける上り方向と下り方向を考慮する必要がない。これにより、計算を簡略化することができる。 According to the fourth embodiment, when the passage time calculation process is executed, the node n is replaced with the signal passage start time C (r, n) and the signal passage end time D (r, n) instead of the partial path e. Since the association is made, it is not necessary to consider the up direction and the down direction in the partial path e. Thereby, calculation can be simplified.
以上、本発明の各実施形態について説明したが、本発明はこれらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、各実施形態では、信号転送可能時間帯算出装置１３０は、計算機能（通過時刻算出処理およびタイミング算出処理等）と、メモリ機能（各エッジ装置ｒのＡ（ｒ）、Ｂ（ｒ）、Ｃ（ｒ，ｅ）、Ｄ（ｒ，ｅ）およびΔを記憶する機能）とを両方備えるものとしたが、信号転送可能時間帯算出装置１３０に計算機能だけを付与し、１つ以上の別のエッジ装置１１０にメモリ機能を付与するような構成としてもよい。
また、各実施形態では、信号転送可能時間帯算出装置１３０を他のエッジ装置１１０（ｒ）とは別に独立して設けるものとして説明したが、複数のエッジ装置１１０のうちの１つ以上が信号転送可能時間帯算出装置１３０の各機能を備えるように構成してもよい。
As mentioned above, although each embodiment of this invention was described, this invention is not limited to these, It can implement in the range which does not change the meaning. For example, in each embodiment, the signal transferable time
In each of the embodiments, the signal transferable time
１００ ネットワークシステム
１１０ エッジ装置（ノード）
１２０ 分岐ノード（ノード）
１３０ 転送可能時間帯算出装置（ノード）
ｅ 部分パス
２００ バス
２１０ 入出力手段
２２０ ＲＡＭ
２３０ ＨＤＤ
２３１ 遅延時間
２３３ 接続情報
２３５ 信号出力時間
２４０ ＣＰＵ
２４１ 通過時刻算出手段
２４３ タイミング算出手段
２４５ 転送制御手段
100
120 branch node
130 Transferable time zone calculation device (node)
e Partial path 200
230 HDD
231
241 Passing time calculation means 243 Timing calculation means 245 Transfer control means
Claims (14)
前記ノードは、このネットワークの端部に配置された複数のエッジ装置と、前記複数のエッジ装置間のMultipoint-to-Multipoint型光パスを実現するために前記リンクが部分パスとして３つ以上接続されたスイッチ装置を示す複数の分岐ノードと、
前記各エッジ装置が前記光パスにより別の前記エッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出装置とを含み、
前記信号転送可能時間帯算出装置による信号転送可能時間帯算出方法であって、
前記信号が前記光パスの各部分パスを通過する際に遅延する時間を示す遅延時間と、前記各部分パスの接続状態を示す接続情報と、前記複数のエッジ装置から選択された第１のエッジ装置が前記信号を出力する時間を示す信号出力時間とを取得する情報取得ステップと、
この情報取得ステップで取得された遅延時間、接続情報および信号出力時間に基づいて、前記第１のエッジ装置から出力される信号が前記分岐ノードを通過する際の信号通過開始時刻および信号通過終了時刻を算出する通過時刻算出ステップと、
この通過時刻算出ステップで算出された信号通過開始時刻および信号通過終了時刻と前記信号出力時間とに基づいて、前記第１のエッジ装置以外に選択された前記エッジ装置を示す第２のエッジ装置から出力される信号の信号通過開始時刻に所定の時間間隔を加算した時刻が、前記第１のエッジ装置から出力される信号の信号通過終了時刻に連続するような部分パスを１つ以上設けるように、かつ、前記第１のエッジ装置として選択できるすべての前記エッジ装置から出力される信号が、前記各部分パス上の同方向かつ同位置を同時刻に通過しないように、前記信号通過開始時刻に加算する所定の時間間隔を算出することにより、前記各エッジ装置における信号出力タイミングを算出するタイミング算出ステップと、
を含んで実行し、
前記タイミング算出ステップは、
前記第２のエッジ装置から出力される信号の通過する前記部分パスにおいて、前記第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記信号通過開始時刻に加算する所定の時間間隔との和の最大値が最小となるように、当該所定の時間間隔を算出することを特徴とする信号転送可能時間帯算出方法。 In a tree-like loop-free network and a link for connecting the plurality of nodes and node,
In the node, three or more of the links are connected as partial paths in order to realize a multipoint-to-multipoint type optical path between the plurality of edge devices arranged at the end of the network and the plurality of edge devices. A plurality of branch nodes indicating the switching device,
Wherein and a respective edge device transfer time zone signal transfer time zone calculator for calculating a for transferring the signal to be output to another of the edge device by the light path,
A signal transferable time zone calculation method by the signal transferable time zone calculation device ,
A delay time indicating the time delay in the signal passes through each partial path of the optical path, connection information indicating the connection status of each of the partial path, a first edge which is selected from the plurality of edge devices An information acquisition step of acquiring a signal output time indicating a time at which the apparatus outputs the signal;
Based on the delay time, connection information, and signal output time acquired in this information acquisition step, the signal passing start time and the signal passing end time when the signal output from the first edge device passes through the branch node. Passing time calculating step for calculating
From the second edge device indicating the edge device selected other than the first edge device based on the signal passage start time and the signal passage end time calculated in the passage time calculation step and the signal output time. One or more partial paths are provided such that a time obtained by adding a predetermined time interval to the signal passing start time of the output signal is continuous with the signal passing end time of the signal output from the first edge device. and signals outputted from all of the edge device can be selected as the first edge device, the same direction and the same position on the respective partial path so as not to pass through at the same time, the signal passage start time by calculating the predetermined time interval to be added, the timing calculation step of calculating a signal output timing of the respective edge device,
The run Nde including,
The timing calculation step includes:
A predetermined time interval to be added to the signal passing end time and the signal passing start time of the signal output from the second edge device in the partial path through which the signal output from the second edge device passes; A signal transferable time zone calculation method, characterized in that the predetermined time interval is calculated so that the maximum value of the sum of the values is minimized .
前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号出力側の部分パスの始点に関連付けて算出することを特徴とする請求項１に記載の信号転送可能時間帯算出方法。 In the passing time calculating step,
2. The signal transferable time zone calculation method according to claim 1, wherein the signal passage start time and the signal passage end time are calculated in association with a start point of a partial path on the signal output side connected to the branch node.
前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号入力側の部分パスの終点に関連付けて算出することを特徴とする請求項１に記載の信号転送可能時間帯算出方法。 In the passing time calculating step,
2. The signal transferable time zone calculation method according to claim 1, wherein the signal passage start time and the signal passage end time are calculated in association with an end point of a partial path on the signal input side connected to the branch node.
前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに関連付けて算出することを特徴とする請求項１に記載の信号転送可能時間帯算出方法。 In the passing time calculating step,
2. The signal transferable time zone calculation method according to claim 1, wherein the signal passage start time and the signal passage end time are calculated in association with the branch node.
前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、ランダムに２つのエッジ装置を、前記第１のエッジ装置および第２のエッジ装置として組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となるようにした後、前記両エッジ装置以外のエッジ装置との組み合わせを順次選択することを特徴とする請求項１ないし請求項４のいずれか一項に記載の信号転送可能時間帯算出方法。 The timing calculation step includes:
In selecting a first edge device, a combination of the second edge device, the two edge device randomly, in combination as the first edge device and the second edge device, the combined After the maximum value of the sum of the signal passing end time of the signal output from the second edge device and the predetermined time interval is minimized, the combination with edge devices other than the two edge devices is performed. 5. The signal transferable time zone calculation method according to claim 1 , wherein selection is performed sequentially.
前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、前記第１のエッジ装置を前記第２のエッジ装置とそれぞれ仮に組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となる第２のエッジ装置を組み合わせることを決定した後、組み合わせることを決定された両エッジ装置以外のエッジ装置との組み合わせを同様に決定することを特徴とする請求項１ないし請求項４のいずれか一項に記載の信号転送可能時間帯算出方法。 The timing calculation step includes:
When the combination of the first edge device and the second edge device is selected, the first edge device is temporarily combined with the second edge device, and the combined second edge Both edge devices determined to be combined after determining to combine the second edge device that minimizes the maximum value of the sum of the signal passing end time of the signal output from the device and the predetermined time interval The signal transfer available time zone calculation method according to any one of claims 1 to 4, wherein a combination with other edge devices is similarly determined.
前記ノードは、このネットワークの端部に配置された複数のエッジ装置と、前記複数のエッジ装置間のMultipoint-to-Multipoint型光パスを実現するために前記リンクが部分パスとして３つ以上接続されたスイッチ装置を示す複数の分岐ノードと、
前記各エッジ装置が前記光パスにより別の前記エッジ装置に出力する信号を転送するための転送可能時間帯を算出する信号転送可能時間帯算出装置とを含み、
前記ネットワークにおける信号転送可能時間帯算出装置であって、
前記信号が前記光パスの各部分パスを通過する際に遅延する時間を示す遅延時間と、前記各部分パスの接続状態を示す接続情報と、前記複数のエッジ装置から選択された第１のエッジ装置が前記信号を出力する時間を示す信号出力時間とに基づいて、前記第１のエッジ装置から出力される信号が前記分岐ノードを通過する際の信号通過開始時刻および信号通過終了時刻を算出する通過時刻算出手段と、
この通過時刻算出手段で算出された信号通過開始時刻および信号通過終了時刻と前記信号出力時間とに基づいて、前記第１のエッジ装置以外に選択された前記エッジ装置を示す第２のエッジ装置から出力される信号の信号通過開始時刻に所定の時間間隔を加算した時刻が、前記第１のエッジ装置から出力される信号の信号通過終了時刻に連続するような部分パスを１つ以上設けるように、かつ、前記第１のエッジ装置として選択できるすべての前記エッジ装置から出力される信号が、前記各部分パス上の同方向かつ同位置を同時刻に通過しないように、前記信号通過開始時刻に加算する所定の時間間隔を算出することにより、前記各エッジ装置における信号出力タイミングを算出するタイミング算出手段と、
を備え、
前記タイミング算出手段は、
前記第２のエッジ装置から出力される信号の通過する前記部分パスにおいて、前記第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記信号通過開始時刻に加算する所定の時間間隔との和の最大値が最小となるように、当該所定の時間間隔を順次算出する、
ことを特徴とする信号転送可能時間帯算出装置。 In a tree-like loop-free network and a link for connecting the plurality of nodes and node,
In the node, three or more of the links are connected as partial paths in order to realize a multipoint-to-multipoint type optical path between the plurality of edge devices arranged at the end of the network and the plurality of edge devices. A plurality of branch nodes indicating the switching device,
Wherein and a respective edge device transfer time zone signal transfer time zone calculator for calculating a for transferring the signal to be output to another of the edge device by the light path,
A signal transferable time zone calculation device in the network ,
A delay time indicating the time delay in the signal passes through each partial path of the optical path, connection information indicating the connection status of each of the partial path, a first edge which is selected from the plurality of edge devices Based on a signal output time indicating a time during which the device outputs the signal, a signal passage start time and a signal passage end time when the signal output from the first edge device passes through the branch node are calculated. Passage time calculation means;
From the second edge device indicating the edge device selected other than the first edge device based on the signal passage start time and the signal passage end time calculated by the passage time calculation means and the signal output time. One or more partial paths are provided such that a time obtained by adding a predetermined time interval to the signal passing start time of the output signal is continuous with the signal passing end time of the signal output from the first edge device. and signals outputted from all of the edge device can be selected as the first edge device, the same direction and the same position on the respective partial path so as not to pass through at the same time, the signal passage start time by calculating the predetermined time interval to be added, the timing calculating means for calculating the signal output timing of the respective edge device,
Equipped with a,
The timing calculation means includes
A predetermined time interval to be added to the signal passing end time and the signal passing start time of the signal output from the second edge device in the partial path through which the signal output from the second edge device passes; Sequentially calculate the predetermined time interval so that the maximum value of the sum of
A signal transferable time zone calculation apparatus characterized by the above.
前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号出力側の部分パスの始点に関連付けて算出することを特徴とする請求項７に記載の信号転送可能時間帯算出装置。 The passage time calculation means includes
8. The signal transferable time zone calculation device according to claim 7, wherein the signal passage start time and the signal passage end time are calculated in association with a start point of a partial path on a signal output side connected to the branch node.
前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに接続された信号入力側の部分パスの終点に関連付けて算出することを特徴とする請求項７に記載の信号転送可能時間帯算出装置。 The passage time calculation means includes
8. The signal transferable time zone calculation device according to claim 7, wherein the signal passage start time and the signal passage end time are calculated in association with an end point of a partial path on the signal input side connected to the branch node.
前記信号通過開始時刻および信号通過終了時刻を前記分岐ノードに関連付けて算出することを特徴とする請求項７に記載の信号転送可能時間帯算出装置。 The passage time calculation means includes
8. The signal transferable time zone calculating apparatus according to claim 7, wherein the signal passing start time and the signal passing end time are calculated in association with the branch node.
前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、ランダムに２つのエッジ装置を、前記第１のエッジ装置および第２のエッジ装置として組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となるようにした後、前記両エッジ装置以外のエッジ装置との組み合わせを順次選択することを特徴とする請求項７ないし請求項１０のいずれか一項に記載の信号転送可能時間帯算出装置。 The timing calculation means includes
In selecting a first edge device, a combination of the second edge device, the two edge device randomly, in combination as the first edge device and the second edge device, the combined After the maximum value of the sum of the signal passing end time of the signal output from the second edge device and the predetermined time interval is minimized, the combination with edge devices other than the two edge devices is performed. 11. The signal transferable time zone calculating apparatus according to claim 7 , wherein the signal transferable time zone calculating apparatus according to any one of claims 7 to 10 is selected sequentially.
前記第１のエッジ装置と、前記第２のエッジ装置との組み合わせを選択する際に、前記第１のエッジ装置を前記第２のエッジ装置とそれぞれ仮に組み合わせて、前記組み合わされた第２のエッジ装置から出力される信号の前記信号通過終了時刻と前記所定の時間間隔との和の最大値が最小となる第２のエッジ装置を組み合わせることを決定した後、組み合わせることを決定された両エッジ装置以外のエッジ装置との組み合わせを同様に決定することを特徴とする請求項７ないし請求項１０のいずれか一項に記載の信号転送可能時間帯算出装置。 The timing calculation means includes
When the combination of the first edge device and the second edge device is selected, the first edge device is temporarily combined with the second edge device, and the combined second edge Both edge devices determined to be combined after determining to combine the second edge device that minimizes the maximum value of the sum of the signal passing end time of the signal output from the device and the predetermined time interval 11. The signal transferable time zone calculation apparatus according to claim 7 , wherein a combination with other edge devices is similarly determined.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2005090939A JP4369892B2 (en) | 2005-03-28 | 2005-03-28 | Signal transferable time zone calculation method, signal transferable time zone calculation device, signal transferable time zone calculation program, and computer-readable recording medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2005090939A JP4369892B2 (en) | 2005-03-28 | 2005-03-28 | Signal transferable time zone calculation method, signal transferable time zone calculation device, signal transferable time zone calculation program, and computer-readable recording medium |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2006279169A JP2006279169A (en) | 2006-10-12 |
| JP4369892B2 true JP4369892B2 (en) | 2009-11-25 |
Family
ID=37213505
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2005090939A Expired - Fee Related JP4369892B2 (en) | 2005-03-28 | 2005-03-28 | Signal transferable time zone calculation method, signal transferable time zone calculation device, signal transferable time zone calculation program, and computer-readable recording medium |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP4369892B2 (en) |
-
2005
- 2005-03-28 JP JP2005090939A patent/JP4369892B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2006279169A (en) | 2006-10-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP2461629B1 (en) | Route search and wavelength allocation method in an optical network and device thereof | |
| JP5586597B2 (en) | Link diversity and load balancing across digital and optical express-thru nodes | |
| JP5141455B2 (en) | Network design apparatus, network design program, and network design method | |
| CN109327409B (en) | Data center network DCN, method and switch for transmitting traffic in DCN | |
| CN114885236B (en) | Optical network path planning method and device | |
| CN114302267A (en) | Spectrum allocation method and system for dedicated protection of space division multiplexing optical network in data center | |
| JP5509322B2 (en) | Wavelength division multiplexing network path search method and system | |
| JPH08307439A (en) | Transmission system for protection control signal | |
| CA2743466A1 (en) | Path calculation order deciding method, program and calculating apparatus | |
| JP4369892B2 (en) | Signal transferable time zone calculation method, signal transferable time zone calculation device, signal transferable time zone calculation program, and computer-readable recording medium | |
| WO2006048414A1 (en) | Optical path routing in an optical communications network | |
| JP4819440B2 (en) | Optical switch device, optical access network, optical switch method and program | |
| WO2024240234A1 (en) | Identification method for branch ports of optical distribution network, and optical distribution network | |
| JP7736084B2 (en) | Optical path design device, optical path design method and program | |
| CN101783974A (en) | All-optical packet switching method, edge node and core nodes | |
| CN107105356A (en) | The heavy route method and system of space division multiplexing optical-fiber network | |
| JP5282048B2 (en) | Switch, interface information creation method and program thereof | |
| JP3877745B2 (en) | Optical transmission equipment | |
| JP2011146819A (en) | Switch, interface information creation method, and program thereof | |
| JP3600221B2 (en) | Optical switching method and device | |
| JP4024255B2 (en) | Optimal path location search device and optimal path location search method | |
| JP6234915B2 (en) | Network system and control method thereof | |
| JP2007110366A (en) | Transmission system | |
| JP4076171B2 (en) | Optical TDM network management method, optical TDM network management program, storage medium storing the program, and optical TDM network management apparatus | |
| JP4382068B2 (en) | Optical transmission equipment |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20070213 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20081224 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20090113 |
|
| RD13 | Notification of appointment of power of sub attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7433 Effective date: 20090225 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090313 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A821 Effective date: 20090227 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20090825 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20090828 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 4369892 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120904 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130904 Year of fee payment: 4 |
|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| LAPS | Cancellation because of no payment of annual fees |