(57)【要約】【課題】並列処理・ノード分散型の重み付きグラフの最小経路計算方法における伝播遅延による計算誤り及び計算時間を減少すること。【解決手段】リンクを介して近傍の他のノード装置から送信され受信した信号を当該リンクに対応する所定の停止時間遅延させ、最初に入力された信号のみをリンクを介して近傍の更に他のノード装置へ送信するノード装置において、近傍の他のノード装置から送信された信号を受信した時刻と、当該信号に含まれる前記他のノード装置で送信された時刻との差を計算し、当該ノード装置における停止時間から前記差を差し引いた時間を新たな停止時間として算出する停止時間再計算部１１を設けることにより、リンクにおける伝播遅延による計算誤り及び計算時間を減少する。【選択図】図７
2008160392.tif 000002
【特許請求の範囲】
【請求項１】
入力端及び出力端をそれぞれ少なくとも１つ有する複数の節点と、該複数の節点のうち任意の節点の入力端及び当該任意の節点を除く他の任意の節点の出力端を１対１で接続する枝と、枝毎に与えられる数値情報である重みとで構成される重み付きグラフにおいて、任意の出発節点から任意の目的節点へ到達可能な経路のうち通過する枝の重みが最小となる経路を求める最小経路問題に則って、リンクを介して接続された複数のノード装置からなる通信ネットワークにおける任意の出発ノード装置から任意の目的ノード装置へ信号を転送させる際の最適パスを求めるのに当たり、目的ノード装置において信号を発生させ、目的ノード装置を含む全てのノード装置が自身とリンクを介して接続された他の全てのノード装置へ当該信号を送信し、この際、リンクを介して接続されたノード装置のいずれかにおいて当該リンクにおける伝送時間に対応する時間分、信号を遅延させ、各ノード装置において最も早く信号が到達したリンクの情報を最小経路の一部として保存させることにより求めるノード装置であって、
近傍の他のノード装置から送信された信号を受信した時刻と、当該信号に含まれる前記他のノード装置で送信された時刻との差を計算し、当該ノード装置における停止時間から前記差を差し引いた時間を新たな停止時間として算出する停止時間再計算手段と、
前記新たな停止時間が正であれば当該新たな停止時間だけ遅延させた後に、また、負であれば直ちに信号を出力する遅延手段と、
前記遅延手段から出力されて入力される信号のうち最初に入力された信号のみを、その送信時刻を現在時刻に書き換えた後、近傍の更に他のノード装置へリンクを介して出力する出力決定手段と、
前記出力決定手段において最初に入力されたと判定された信号に対応するリンクの情報を、出発ノード装置から目的ノード装置へ信号を転送させる際の最適パスの一部分として保存するパス保存手段とを備えた
ことを特徴としたノード装置。
【請求項２】
請求項１に記載のノード装置において、
前記遅延手段から出力されて入力される信号のうち最初に入力された信号のみを、その送信時刻を当該送信時刻に当該ノード装置における停止時間を加えた時刻に書き換えた後、近傍の更に他のノード装置へリンクを介して出力する出力決定手段を備えた
ことを特徴としたノード装置。
【請求項３】
入力端及び出力端をそれぞれ少なくとも１つ有する複数の節点と、該複数の節点のうち任意の節点の入力端及び当該任意の節点を除く他の任意の節点の出力端を１対１で接続する枝と、枝毎に与えられる数値情報である重みとで構成される重み付きグラフにおいて、任意の出発節点から任意の目的節点へ到達可能な経路のうち通過する枝の重みが最小となる経路を求める最小経路問題に則って、リンクを介して接続された複数のノード装置からなる通信ネットワークにおける任意の出発ノード装置から任意の目的ノード装置へ信号を転送させる際の最適パスを求めるのに当たり、目的ノード装置において信号を発生させ、目的ノード装置を含む全てのノード装置が自身とリンクを介して接続された他の全てのノード装置へ当該信号を送信し、この際、リンクを介して接続されたノード装置のいずれかにおいて当該リンクにおける伝送時間に対応する時間分、信号を遅延させ、各ノード装置において最も早く信号が到達したリンクの情報を最小経路の一部として保存させることにより求めるノード装置であって、
近傍の他のノード装置から送信された信号を受信した時刻と、当該信号に含まれる前記他のノード装置で送信された時刻との差を計算し、当該ノード装置における停止時間から前記差を差し引いた時間を新たな停止時間として算出する停止時間再計算手段と、
前記新たな停止時間後の時刻が最も早い信号のみを出力する棄却判定手段と、
前記棄却判定手段において最も早いと判定された信号に対応するリンクの情報を、出発ノード装置から目的ノード装置へ信号を転送させる際の最適パスの一部分として保存するパス保存手段と、
前記棄却判定手段において最も早いと判定された信号を、前記新たな停止時間が０または負となるまで遅延させた後に出力する遅延手段と、
前記遅延手段から出力されて入力される信号を、その送信時刻を現在時刻に書き換えた後、近傍の更に他のノード装置へリンクを介して出力する出力手段とを備えた
ことを特徴としたノード装置。
【請求項４】
請求項３に記載のノード装置において、
前記遅延手段から出力されて入力される信号を、その送信時刻を当該送信時刻に当該ノード装置における停止時間を加えた時刻に書き換えた後、近傍の更に他のノード装置へリンクを介して出力する出力手段とを備えた
ことを特徴としたノード装置。
【請求項５】
コンピュータを、請求項１乃至４のいずれかに記載のノード装置として機能させるためのプログラム。
【請求項６】
入力端及び出力端をそれぞれ少なくとも１つ有する複数の節点と、該複数の節点のうち任意の節点の入力端及び当該任意の節点を除く他の任意の節点の出力端を１対１で接続する枝と、枝毎に与えられる数値情報である重みとで構成される重み付きグラフにおいて、任意の出発節点から任意の目的節点へ到達可能な経路のうち通過する枝の重みが最小となる経路を求める最小経路問題に則って、リンクを介して接続された複数のノード装置からなる通信ネットワークにおける任意の出発ノード装置から任意の目的ノード装置へ信号を転送させる際の最適パスを求めるのに当たり、目的ノード装置において信号を発生させ、目的ノード装置を含む全てのノード装置が自身とリンクを介して接続された他の全てのノード装置へ当該信号を送信し、この際、リンクを介して接続されたノード装置のいずれかにおいて当該リンクにおける伝送時間に対応する時間分、信号を遅延させ、各ノード装置において最も早く信号が到達したリンクの情報を最小経路の一部として保存させることにより求める計算システムであって、
近傍の他のノード装置から送信された信号を受信した時刻と、当該信号に含まれる前記他のノード装置で送信された時刻との差を計算し、当該ノード装置における停止時間から前記差を差し引いた時間を新たな停止時間として算出する停止時間再計算手段と、
前記新たな停止時間が正であれば当該新たな停止時間だけ遅延させた後に、また、負であれば直ちに信号を出力する遅延手段と、
前記遅延手段から出力されて入力される信号のうち最初に入力された信号のみを、その送信時刻を現在時刻に書き換えた後、近傍の更に他のノード装置へリンクを介して出力する出力決定手段と、
前記出力決定手段において最初に入力されたと判定された信号に対応するリンクの情報を、出発ノード装置から目的ノード装置へ信号を転送させる際の最適パスの一部分として保存するパス保存手段とを備えたノード装置を用いる
ことを特徴とする最小経路計算システム。
【請求項７】
入力端及び出力端をそれぞれ少なくとも１つ有する複数の節点と、該複数の節点のうち任意の節点の入力端及び当該任意の節点を除く他の任意の節点の出力端を１対１で接続する枝と、枝毎に与えられる数値情報である重みとで構成される重み付きグラフにおいて、任意の出発節点から任意の目的節点へ到達可能な経路のうち通過する枝の重みが最小となる経路を求める最小経路問題に則って、リンクを介して接続された複数のノード装置からなる通信ネットワークにおける任意の出発ノード装置から任意の目的ノード装置へ信号を転送させる際の最適パスを求めるのに当たり、目的ノード装置において信号を発生させ、目的ノード装置を含む全てのノード装置が自身とリンクを介して接続された他の全てのノード装置へ当該信号を送信し、この際、リンクを介して接続されたノード装置のいずれかにおいて当該リンクにおける伝送時間に対応する時間分、信号を遅延させ、各ノード装置において最も早く信号が到達したリンクの情報を最小経路の一部として保存させることにより求める計算システムであって、
近傍の他のノード装置から送信された信号を受信した時刻と、当該信号に含まれる前記他のノード装置で送信された時刻との差を計算し、当該ノード装置における停止時間から前記差を差し引いた時間を新たな停止時間として算出する停止時間再計算手段と、
前記新たな停止時間後の時刻が最も早い信号のみを出力する棄却判定手段と、
前記棄却判定手段において最も早いと判定された信号に対応するリンクの情報を、出発ノード装置から目的ノード装置へ信号を転送させる際の最適パスの一部分として保存するパス保存手段と、
前記棄却判定手段において最も早いと判定された信号を、前記新たな停止時間が０または負となるまで遅延させた後に出力する遅延手段と、
前記遅延手段から出力されて入力される信号を、その送信時刻を現在時刻に書き換えた後、近傍の更に他のノード装置へリンクを介して出力する出力手段とを備えたノード装置を用いる
ことを特徴とする最小経路計算システム。
【請求項８】
入力端及び出力端をそれぞれ少なくとも１つ有する複数の節点と、該複数の節点のうち任意の節点の入力端及び当該任意の節点を除く他の任意の節点の出力端を１対１で接続する枝と、枝毎に与えられる数値情報である重みとで構成される重み付きグラフにおいて、任意の出発節点から任意の目的節点へ到達可能な経路のうち通過する枝の重みが最小となる経路を求める最小経路問題に則って、リンクを介して接続された複数のノード装置からなる通信ネットワークにおける任意の出発ノード装置から任意の目的ノード装置へ信号を転送させる際の最適パスを求めるのに当たり、目的ノード装置において信号を発生させ、目的ノード装置を含む全てのノード装置が自身とリンクを介して接続された他の全てのノード装置へ当該信号を送信し、この際、リンクを介して接続されたノード装置のいずれかにおいて当該リンクにおける伝送時間に対応する時間分、信号を遅延させ、各ノード装置において最も早く信号が到達したリンクの情報を最小経路の一部として保存させることにより求める計算方法であって、
停止時間再計算手段と、遅延手段と、出力決定手段と、パス保存手段とを備えたノード装置を用い、
停止時間再計算手段により、近傍の他のノード装置から送信された信号を受信した時刻と、当該信号に含まれる前記他のノード装置で送信された時刻との差を計算し、当該ノード装置における停止時間から前記差を差し引いた時間を新たな停止時間として算出し、
遅延手段により、前記新たな停止時間が正であれば当該新たな停止時間だけ遅延させた後に、また、負であれば直ちに信号を出力し、
出力決定手段により、前記遅延手段から出力されて入力される信号のうち最初に入力された信号のみを、その送信時刻を現在時刻に書き換えた後、近傍の更に他のノード装置へリンクを介して出力し、
パス保存手段により、前記出力決定手段において最初に入力されたと判定された信号に対応するリンクの情報を、出発ノード装置から目的ノード装置へ信号を転送させる際の最適パスの一部分として保存する
ことを特徴とする最小経路計算方法。
【請求項９】
入力端及び出力端をそれぞれ少なくとも１つ有する複数の節点と、該複数の節点のうち任意の節点の入力端及び当該任意の節点を除く他の任意の節点の出力端を１対１で接続する枝と、枝毎に与えられる数値情報である重みとで構成される重み付きグラフにおいて、任意の出発節点から任意の目的節点へ到達可能な経路のうち通過する枝の重みが最小となる経路を求める最小経路問題に則って、リンクを介して接続された複数のノード装置からなる通信ネットワークにおける任意の出発ノード装置から任意の目的ノード装置へ信号を転送させる際の最適パスを求めるのに当たり、目的ノード装置において信号を発生させ、目的ノード装置を含む全てのノード装置が自身とリンクを介して接続された他の全てのノード装置へ当該信号を送信し、この際、リンクを介して接続されたノード装置のいずれかにおいて当該リンクにおける伝送時間に対応する時間分、信号を遅延させ、各ノード装置において最も早く信号が到達したリンクの情報を最小経路の一部として保存させることにより求める計算方法であって、
停止時間再計算手段と、棄却判定手段と、パス保存手段と、遅延手段と、出力手段とを備えたノード装置を用い、
停止時間再計算手段により、近傍の他のノード装置から送信された信号を受信した時刻と、当該信号に含まれる前記他のノード装置で送信された時刻との差を計算し、当該ノード装置における停止時間から前記差を差し引いた時間を新たな停止時間として算出し、
棄却判定手段により、前記新たな停止時間後の時刻が最も早い信号のみを出力し、
パス保存手段により、前記棄却判定手段において最も早いと判定された信号に対応するリンクの情報を、出発ノード装置から目的ノード装置へ信号を転送させる際の最適パスの一部分として保存し、
遅延手段により、前記棄却判定手段において最も早いと判定された信号を、前記新たな停止時間が０または負となるまで遅延させた後に出力し、
出力手段により、前記遅延手段から出力されて入力される信号を、その送信時刻を現在時刻に書き換えた後、近傍の更に他のノード装置へリンクを介して出力する
ことを特徴とする最小経路計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、重み付きグラフにおける最小経路を計算する方法に則って、通信ネットワークにおける最適パスを求める技術に関する。
【背景技術】
【０００２】
光通信ネットワークでは、光ファイバの広帯域性を活用したＷＤＭ技術の導入が行われている。基幹部またはバックボーンネットワークといった従来のＷＤＭの適用分野においては、目的のノードへ伝送する信号を伝達するために他のどのノードを経由するかというパスの更新は秒〜分という比較的遅いものである。これに対し、ＬＡＮやメトロといった、よりユーザに近いネットワークでは目的ノードが異なる確率が高く、ＩＰ電話に代表されるリアルタイム通信で許容できる転送遅延は２０〜１００ミリ秒以下と言われてる（例えば、非特許文献１参照）。より高頻度に目的ノードが変化するネットワークにおいて、通信網を効率的に利用するためには従来より高速にパスの更新を行う必要がある。
【０００３】
従来、パス更新のために用いられている計算アルゴリズムの１つとして、並列処理型がある（例えば、特許文献１参照）。この方式では複数の基本演算素子が並列動作することにより、計算量を減少させることが可能である。
【０００４】
一般に最適パスを求めるアルゴリズムは、対象となるネットワークを（１）節点、（２）節点間を結ぶ枝、（３）枝についた重みで構成される重み付きグラフに対応させ、この重み付きグラフにおける単一節点から複数節点、または全節点から全節点へ到達するために通過する枝の重みの和の最小を求める。図１に重み付きグラフの例を示す。この例では４つの節点Ａ，Ｂ，Ｃ，Ｄと、４つの枝と、各枝の重みとでグラフを構成している。
【０００５】
前記特許文献１に開示された計算アルゴリズムを以下に示す。
【０００６】
このアルゴリズムは複数の節点から１つの節点への最小経路を求めるものである。目標となる節点（目的節点）から枝で繋がっている近傍の節点へ信号を伝達する。信号を受信した節点は枝の重みｗijに対応する時間ステップ動作を停止し、その後に近傍の節点へと信号を伝達する。より早く信号が伝達する経路が最適パスとなる。この動作のフローチャートを図２に示す。並列処理型は節点に対応する基本演算素子が並列に動作することにより計算量を減少させている。
【０００７】
このアルゴリズムにおける基本演算素子の配置法に関しては２つの方法、即ち１箇所に集中する方法と、通信ノード（ノード装置）毎に分散する方法とが提案されている。集中型は近傍の基本演算素子との信号の授受を高速にできるため、計算速度を速めることが可能である。ノード装置毎に分散する方法は、計算速度は遅くなるが、計算のために必要なパラメータを１箇所に送信する、計算結果が全ノード装置に行き渡ったことを確認してから計算結果を反映させる、といった必要がないため、計算結果の反映も含めたトータルの計算・更新時間を短くすることが可能である。
【０００８】
ノード分散型の構成要素と構成例を図３、図４に示す。各ノード装置は図３に示すように遅延部、出力決定部及びパス保存部で構成される。各部の動作は図２のフローチャート内に示した通りである。図１のグラフをこのノード分散型で構成した例を図４に示す。ノード装置同士の入力と出力が伝送路（リンク）を介して互いに接続される。
【特許文献１】特開２００６−２４６１０５号公報
【非特許文献１】佐藤健一、他「広帯域光ネットワーキング技術−フォトニックネットワーク−」電子情報通信学会、平成１５年３月２５日発行、１４３〜１４７頁
【発明の開示】
【発明が解決しようとする課題】
【０００９】
この並列処理・ノード分散型の計算方法において、特許文献１では基本演算素子間の信号授受に伴う伝播遅延の影響を考慮していないが、実際には伝播遅延時間がある。このため、経由するノード装置の数（ホップ数）が多いほど伝播遅延が加算される。この影響を図５、図６を用いて説明する。
【００１０】
図５は重み付きグラフの他の例を示すもので、そのタイムチャートを図６に示す。図６において、□は信号の受信を表し、○は信号の送信を表す。□及び○の中の文字はその信号が直前のどの節点からきたものかを表す。
【００１１】
まず、伝播遅延を考慮しない場合を図６（ａ）に示す。時刻０に節点Ａから信号が発行されると、同時刻に節点Ｂ，Ｃに到達する。その後、各節点において重みに対応する時間ＴAB，ＴAC停止してから信号を発行する。この例ではＴAB＋ＴBC＜ＴACであるため、節点Ｃにおける信号の発行は節点Ｂからきた信号である。これにより節点Ｃから節点Ａに向かう最適パスは節点Ｂへ向かう方向ということがわかる。
【００１２】
次に伝播遅延を考慮した場合を図６（ｂ）に示す。信号を発行してから受信されるまでの伝播遅延をｄとする。本来、伝播遅延は様々に変化するものであるが、ここでは簡単のため一定とする。先ほどと同様、ＴAB＋ＴBC＜ＴACを満たしているが、伝播遅延を考慮すると、ｄAB＋ＴAB＋ｄBC＋ＴBC＞ｄAC＋ＴACとなっている。このため、節点Ｃから節点Ａに向かう最適パスは節点Ａへ向かう方向となり、計算結果が異なることがわかる。このように伝播遅延を含めると通過する節点数が多いパスが不利になり、正確な計算が行えない。
【００１３】
この伝播遅延の影響を抑えるために、停止時間を大きく取る方法が考えられる。伝播遅延の最悪値をｄmaxとすると、停止時間の最小単位Ｔminをｄmaxよりも十分大きく取れば良い。どの程度大きくとれば良いかはネットワークの規模により変わってくる。ネットワークのノード数が多くなると通過する節点数が多くなるため、伝播遅延の総和は大きくなる。そのためＴminをより大きく取らなければ伝播遅延の影響が大きくなり、正しい計算結果とならない。節点数Ｎのグラフに対して、通過する節点数をｆ（Ｎ）とする。ｆは単調増加関数である。この時、伝播遅延総和の最悪値は
ｆ（Ｎ）×ｄmax
となる。この最悪値よりもＴminを大きくとるので
Ｔmin＝ａ×ｆ（Ｎ）×ｄmax
ａ＞１
この時、節点における平均の停止ステップ数をＳと置くと、１節点での平均停止時間Ｔcalは
Ｔcal＝Ｓ×Ｔmin
＝ｆ（Ｎ）×Ｓ×ａ×ｄmax
となる。ｆはトポロジーにより変化するが、従来のネットワークでは１次関数的に増加するため、計算時間がノード数の二乗で増加する。
【課題を解決するための手段】
【００１４】
そこで、本発明は伝播遅延による計算誤りの減少及び計算時間の減少を目的とする。各ノード装置では、近傍のノード装置へ信号を送る際に信号送信時のタイムスタンプを書き込んで送る。信号を受信したノード装置は受信時刻と信号送信時のタイムスタンプとの差を取って伝播遅延時間を算出し、本来の停止時間から伝播遅延時間を引いたものを新しい停止時間として遅延をかける。
【発明の効果】
【００１５】
本発明によれば、並列処理・ノード分散型の最小経路計算方法において、ホップ数に依存した誤差を抑制し、計算時間を減少することが可能である。
【発明を実施するための最良の形態】
【００１６】
＜実施の形態１＞
図７は本発明のノード装置の第１の実施の形態を示すもので、本ノード装置１０は、停止時間再計算部１１、遅延部１２、出力決定部１３及びパス保存部１４から構成されている。
【００１７】
停止時間再計算部１１は、リンクを介して接続された近傍の他のノード装置から送信され受信した信号より当該他のノード装置において送信された時刻（送信時刻）を表すタイムスタンプを読み取り、受信時刻（現在時刻）と前記送信時刻との差である伝播遅延時間ｄを計算し、さらに当該リンクにおける伝送時間に対応して予め設定された停止時間Ｔから伝播遅延時間ｄを差し引いて新たな停止時間Ｔ’を算出する。
【００１８】
遅延部１２は、停止時間再計算部１１で算出された新たな停止時間Ｔ’が正（プラス）であるか負（マイナス）であるかを判定し、正であれば当該新たな停止時間Ｔ’だけ遅延させた後に、また、負（０を含む）であれば直ちに信号を出力する。
【００１９】
なお、停止時間再計算部１１及び遅延部１２は、実際にはそれぞれリンクを介して接続された他のノード装置の数だけ有り、伝播遅延時間ｄ、停止時間Ｔ及び新たな停止時間Ｔ’もリンク毎にそれぞれ異なる。
【００２０】
出力決定部１３は、遅延部１２から出力されて入力される信号のうち最初に入力された信号のみを、そのタイムスタンプを現在時刻に書き換えた後、近傍の他のノード装置へリンクを介して出力する。
【００２１】
パス保存部１４は、出力決定部１３において最初に入力されたと判定された信号に対応するリンク（当該信号を送信したノード装置と自ノード装置とを結ぶリンク）の情報を、出発ノード装置から目的ノード装置へ信号を転送させる際の最適パス（最小経路）の一部分として保存する。
【００２２】
前述したノード装置における動作のフローチャートを図８に示す。なお、図８中の「タイムスタンプ書き換え」処理については、その詳細を図１６（ａ）に示す。
【００２３】
図９は本実施の形態に係るノード装置による通信ネットワークの構成例を示すものであり、リンク２０を介して各ノード装置１０の停止時間再計算部１１と出力決定部１３とが接続されている。
【００２４】
任意の出発ノード装置１０から任意の目的ノード装置１０へ信号を転送させる際の最適パスを求める場合、まず、任意の目的ノード装置１０（の図示しない初期信号発生部）においてタイムスタンプ（送信時刻）を含む最適パス探索用の信号、例えば前記タイムスタンプとともに目的ノード装置及び出発ノード装置（のアドレス等）をそれぞれ送信元及び送信先として含むパケット信号を生成し、その出力決定部１３からリンク２０を介して接続された他のノード装置１０に送信する。
【００２５】
各ノード装置１０では前記信号を受信する（ｓ１）と、その停止信号再計算部１１において信号中からタイムスタンプ（送信時刻）を読み取り（ｓ２）、現在時刻と前記送信時刻との差である伝播遅延時間ｄを計算し（ｓ３）、さらに予め設定された停止時間Ｔから伝播遅延時間ｄを差し引いて新たな停止時間Ｔ’を算出する（ｓ４）。また、各ノード装置１０では、その遅延部１２において前記新たな停止時間Ｔ’の正負が判定され（ｓ５）、正であれば前記新たな停止時間Ｔ’遅延させた上で出力し（ｓ６）、また、負（０を含む）であれば直ちに出力する。
【００２６】
さらに、各ノード装置１０では、その出力決定部１３において、遅延部１２から出力されて入力される信号が最初に入力された信号（厳密には、送信元及び送信先が同一の最適パス探索用の信号のうち、最初に入力された信号）であれば（ｓ７）、そのタイムスタンプを現在時刻に書き換えた（ｓ９）後、近傍の他のノード装置へリンク２０を介して出力し（ｓ１０）、最初に入力された信号でなければ何もせず、入力待ち状態に復帰する。
【００２７】
また、この際、各ノード装置１０のパス保存部１４には、出力決定部１３において最初に入力されたと判定された信号に対応するリンク２０の情報が、当該信号中の送信先を出発ノード装置、送信元を目的ノード装置として信号を転送させる際の最適パスの一部分として保存される（ｓ８）。
【００２８】
なお、各ノード装置１０の出力決定部１３は、より詳細には、送信元及び送信先が同一の最適パス探索用の信号について一度出力すると、その後、一定期間（通常、最適パスの更新周期よりやや短い期間）出力しないよう構成されている。あるいは、任意の目的ノード装置１０（の図示しない初期信号発生部）において、前述した情報とともに当該信号を生成した時刻である信号生成時刻も含む最適パス探索用の信号を生成させるようにしておき、各ノード装置１０の出力決定部１３では、送信元及び送信先が同一の最適パス探索用の信号についてはその信号生成時刻が異なる場合しか出力しない、つまり送信元及び送信先が同一の最適パス探索用の信号について一度出力すると、信号生成時刻が新しい信号が来るまで出力しないように構成しても良い。
【００２９】
前述した図５のグラフの各節点Ａ，Ｂ，Ｃが本実施の形態に係るノード装置により構成されている場合のタイムチャートを図１０に示す。
【００３０】
時刻０に節点Ａから発行された信号は、伝播遅延時間ｄAB，ｄAC後に節点Ｂ，Ｃへ到達する。節点Ｂでは本来の停止時間ＴABと伝播遅延時間ｄABとの差Ｔ’ABを計算し、新しい停止時間とする。この新しい停止時間Ｔ’ABだけ停止した後、近傍の節点Ｃへと信号を発行する。節点Ｃでも同様に節点Ａと節点Ｂのそれぞれから来た信号に対し、本来の停止時間と伝播遅延時間との差を新しい停止時間とする。新しい遅延時間が負となる場合、即ち本来の停止時間よりも伝播遅延時間が大きい場合には、停止時間を置かずに直ちに近傍の節点へ信号を発行する。
【００３１】
＜実施の形態２＞
ところで、第１の実施の形態の構成では、停止時間ＴABや伝播遅延時間ｄABが時間とともに変化する場合、１つの遅延部における信号の入力順と出力順が異なる可能性が出てくる。このため１つの遅延部は実際には複数の遅延回路で構成される。
【００３２】
図１１は本発明のノード装置の第２の実施の形態、ここでは前述した遅延部の回路規模の増大の問題を解決可能とする形態を示すもので、本ノード装置３０は、停止時間再計算部３１、棄却判定部３２、パス保存部３３、遅延部３４及び出力部３５から構成されている。
【００３３】
停止時間再計算部３１は、第１の実施の形態における停止時間再計算部１１と同一である。なお、第１の実施の形態の場合と同様、停止時間再計算部３１は、実際にはそれぞれリンクを介して接続された他のノード装置の数だけ有り、伝播遅延時間ｄ、停止時間Ｔ及び新たな停止時間Ｔ’もリンク毎にそれぞれ異なる。
【００３４】
棄却判定部３２は、停止時間再計算部１１で算出された新たな停止時間Ｔ’を現在時刻に加算して当該新たな停止時間Ｔ’後の時刻、即ち遅延部３４を経て出力部３５に信号が到達する（予定の）時刻を求め、前記停止時間再計算部３１から出力されて入力される信号のうち、この時刻が最も早い信号のみを出力し、それ以外の信号を破棄する。
【００３５】
パス保存部３３は、棄却判定部３２において最も早いと判定された信号に対応するリンク（当該信号を送信したノード装置と自ノード装置とを結ぶリンク）の情報を、出発ノード装置から目的ノード装置へ信号を転送させる際の最適パスの一部分として保存する。
【００３６】
遅延部３４は、棄却判定部３２において最も早いと判定された信号を、前記停止時間再計算部１１で算出された新たな停止時間Ｔ’が０または負（マイナス）となるまで遅延させた後に出力する。
【００３７】
出力部３５は、前記遅延部３４から出力されて入力される信号を、そのタイムスタンプを現在時刻に書き換えた後、近傍の他のノード装置へリンクを介して出力する。
【００３８】
前述したノード装置における動作のフローチャートを図１２に示す。なお、図１２中の「タイムスタンプ書き換え」処理については、その詳細を図１６（ａ）に示す。
【００３９】
図１３は本実施の形態に係るノード装置による通信ネットワークの構成例を示すものであり、リンク２０を介して各ノード装置３０の停止時間再計算部３１と出力部３５とが接続されている。
【００４０】
任意の出発ノード装置３０から任意の目的ノード装置３０へ信号を転送させる際の最適パスを求める場合、まず、任意の目的ノード装置３０（の図示しない初期信号発生部）においてタイムスタンプ（送信時刻）を含む最適パス探索用の信号、例えば前記タイムスタンプとともに目的ノード装置及び出発ノード装置（のアドレス等）をそれぞれ送信元及び送信先として含むパケット信号を生成し、その出力部３５からリンク２０を介して接続された他のノード装置３０に送信する。
【００４１】
各ノード装置３０では前記信号を受信する（ｓ１１）と、その停止信号再計算部３１において信号中からタイムスタンプ（送信時刻）を読み取り（ｓ１２）、現在時刻と前記送信時刻との差である伝播遅延時間ｄを計算し（ｓ１３）、さらに予め設定された停止時間Ｔから伝播遅延時間ｄを差し引いて新たな停止時間Ｔ’を算出する（ｓ１４）。
【００４２】
また、各ノード装置３０では、その棄却判定部３２において停止時間再計算部３１から出力されて入力される信号が、新たな停止時間Ｔ’後の時刻が最も早い信号（厳密には、送信元及び送信先が同一の最適パス探索用の信号のうち、新たな停止時間Ｔ’後の時刻が最も早い信号）であれば出力し（ｓ１５）、そうでなければ何もせず、入力待ち状態に復帰する。
【００４３】
また、この際、各ノード装置３０のパス保存部３３には、棄却判定部３２において最も早いと判定された信号に対応するリンク２０の情報が、当該信号中の送信先を出発ノード装置、送信元を目的ノード装置として信号を転送させる際の最適パスの一部分として保存される（ｓ１６）。
【００４４】
また、各ノード装置３０では、その遅延部３４において、棄却判定部３２において最も早いと判定された信号を、前記新たな停止時間Ｔ’が０または負となるまで遅延させた後に出力、詳細には新たな停止時間Ｔ’の正負を判定し（ｓ１７）、正であれば所定の停止時間の最小値Ｔmin分遅延させ、前記新たな停止時間Ｔ’から当該所定の停止時間の最小値Ｔminを減算した（ｓ１８）上で再度正負の判定を繰り返し、０または負であれば直ちに出力する。
【００４５】
さらに、各ノード装置３０では、その出力部３５において、棄却判定部３２において最も早いと判定された信号を、そのタイムスタンプを現在時刻に書き換えた（ｓ１９）後、近傍の他のノード装置へリンク２０を介して出力する（ｓ２０）。
【００４６】
なお、各ノード装置３０の棄却判定部３２は、より詳細には、送信元及び送信先が同一の最適パス探索用の信号について一度出力すると、その後、一定期間（通常、最適パスの更新周期よりやや短い期間）出力しないよう構成されている。あるいは、任意の目的ノード装置１０（の図示しない初期信号発生部）において、前述した情報とともに当該信号を生成した時刻である信号生成時刻も含む最適パス探索用の信号を生成させるようにしておき、各ノード装置３０の棄却判定部３２では、送信元及び送信先が同一の最適パス探索用の信号についてはその信号生成時刻が異なる場合しか出力しない、つまり送信元及び送信先が同一の最適パス探索用の信号について一度出力すると、信号生成時刻が新しい信号が来るまで出力しないように構成しても良い。
【００４７】
前述した第１及び第２の実施の形態において、伝播遅延時間と本来の停止時間との差が誤差となる。この誤差を発生させないためには、停止時間の最小値Ｔminが伝播遅延時間の最大値ｄmax以上であれば良い。つまり、Ｔmin≧ｄmaxを満たす必要がある。このとき、ノード装置における平均の停止ステップ数をＳと置くと、１ノードでの平均停止時間Ｔcalは
Ｔcal＝Ｓ×Ｔmin≧Ｓ×ｄmax
を満たせば良い。
【００４８】
以上より、従来技術が節点における計算時間がグラフの節点数に依存して増加するのに対し、本発明のアルゴリズムは、各節点における計算時間がノード数に依存せず、しかもその計算時間が従来技術よりも常に少ないことがわかる。
【００４９】
＜実施の形態３＞
第１及び第２の実施の形態では、停止時間の最小時間を伝播遅延時間の最大値よりも大きくする必要があった。その理由を図１４を用いて説明する。図１４（ａ）のようなグラフにおいて、節点Ａから信号を発行し、節点Ｂ，Ｃへと伝播する状態を考える。このとき、伝播遅延を考慮しない場合と考慮した場合のタイムチャートを図１４（ｂ）に示す。時刻０に節点Ａから信号を発行したとき、伝播遅延が存在しない場合には、時刻ＴAB＋ＴBCに節点Ｃから信号を発行する。
【００５０】
しかしながら、伝播遅延が存在しかつその伝播遅延が停止時間よりも大きい場合に誤差が発生する。この例では、節点ＡＢ間での伝播遅延ｄABが節点Ｂにおける停止時間ＴABよりも大きいと仮定する。このとき、節点Ｂでは信号受信時に直ちに節点Ｃへ信号を送る。しかしながら、伝播遅延ｄABと停止時間ＴABとの差である誤差ＥABが、そのまま残り続ける。
【００５１】
そこで、この誤差を減少させるために、信号受信時に既に誤差が存在する場合には、新しい停止時間は本来の停止時間から伝播遅延時間と誤差を引いたものとする。
【００５２】
この方式における図１４（ａ）と同じグラフにおけるタイムチャートを図１５に示す。節点Ｂでは停止時間よりも伝播遅延時間が大きいため誤差が発生している。節点Ｃにおいては、受信した信号に時間誤差が存在するので、停止時間ＴBCから伝播遅延時間ｄBCと誤差ＥABを引いたものを新しい停止時間Ｔ’BCとする。これにより、誤差の拡大を防ぐことが可能となる。
【００５３】
この実施の形態に係るノード装置の構成は、基本的に第１または第２の実施の形態と基本的に同一であるが、出力決定部１３または出力部３５におけるタイムスタンプ書き換え処理の内容が異なる。即ち、第１または第２の実施の形態では、受信信号中のタイムスタンプを当該ノード装置における実際の送信時刻、即ち信号を受信した時刻に新たな停止時間Ｔ’を加えた時刻に書き換えていたが、この実施の形態では、受信信号中のタイムスタンプを当該ノード装置における理想的な送信時刻、即ち受信信号中の送信時刻（タイムスタンプ）（＝前のノード装置での送信時刻）に本来の停止時間Ｔを加えた時刻に書き換える。
【００５４】
第１及び第２の実施の形態に対応するタイムスタンプ書き換え処理を図１６（ａ）に、また、本実施の形態に対応するタイムスタンプ書き換え処理を図１６（ｂ）にそれぞれ示す。
【００５５】
なお、本発明のノード装置は、周知のコンピュータに媒体もしくは通信回線を介して、図７、図１１の構成図に示された機能を実現するプログラムあるいは図８、図１２及び図１６のフローチャートに示された手順を備えるプログラムをインストールすることによっても実現可能である。
【図面の簡単な説明】
【００５６】
【図１】重み付きグラフの一例を示す説明図
【図２】従来の重み付きグラフの最小経路の計算方法を示すフローチャート
【図３】従来のノード装置の一例を示す構成図
【図４】従来のノード装置による通信ネットワークの一例を示す構成図
【図５】重み付きグラフの他の例を示す説明図
【図６】伝播遅延時間の影響を示すタイムチャート
【図７】本発明のノード装置の第１の実施の形態を示す構成図
【図８】図７のノード装置における動作のフローチャート
【図９】図７のノード装置による通信ネットワークの一例を示す構成図
【図１０】本発明により伝播遅延時間の影響を排除した場合のタイムチャート
【図１１】本発明のノード装置の第２の実施の形態を示す構成図
【図１２】図１１のノード装置における動作のフローチャート
【図１３】図１１のノード装置による通信ネットワークの一例を示す構成図
【図１４】伝播遅延時間が停止時間より長い場合の誤差を説明するためのグラフ及びタイムチャート
【図１５】第３の実施の形態における動作を説明するためのタイムチャート
【図１６】タイムスタンプ書き換え処理の詳細を示す図
【符号の説明】
【００５７】
１０，３０：ノード装置、１１，３１：停止時間再計算部、１２，３３４：遅延部、１３：出力決定部、１４，３３：パス保存部、３２：棄却判定部、３５：出力部、２０：リンク。
【図１】
2008160392.tif 000003
【図２】
2008160392.tif 000004
【図３】
2008160392.tif 000005
【図４】
2008160392.tif 000006
【図５】
2008160392.tif 000007
【図６】
2008160392.tif 000008
【図７】
2008160392.tif 000009
【図８】
2008160392.tif 000010
【図９】
2008160392.tif 000011
【図１０】
2008160392.tif 000012
【図１１】
2008160392.tif 000013
【図１２】
2008160392.tif 000014
【図１３】
2008160392.tif 000015
【図１４】
2008160392.tif 000016
【図１５】
2008160392.tif 000017
【図１６】
2008160392.tif 000018