(57)【要約】      （修正有）【課題】送信元ノードのみで測定可能な同時接続ユーザフロー数と使用帯域のみから各経路上のユーザパス通信品質を均等に維持できる通信経路を決定し、また、新たなパスを張りたい場合にも、対応して通信経路を決定する。【解決手段】発信元ノード１０は、経路ｉ上のボトルネックリンク容量Ｃｉを予め記憶し、τ毎に経路ｉへ送信される転送レートＤｉと平均同時接続ユーザフロー数Ｎｉを測定し、Ｄｉの平均レートａｖｇＤｉを更新し、経路ｉの１ユーザ当り使用帯域Ｕｉを更新し、経路ｉ上にパスｊの転送レートＤｉ，ｊと平均同時接続ユーザフロー数Ｎｉ，ｊを測定し、その平均レートａｖｇＤｉ，ｊを更新し、パスｊの１ユーザ当りの使用帯域Ｕｉ，ｊを更新し、Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めたパラメータβ，δ１を用いてｍｉｎ｛Ｕｉ／Ｃｉ｝＜β、かつ（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＞δ１ならば品質劣化パスが存在すると判定する。【選択図】        図１
2004215006.tif 000002
【特許請求の範囲】
【請求項１】
通信網内の発信元ノードと着信先ノードの間に経路がＭ本存在し、経路ｉ上にｎｉ本の論理パスが張られ、発信元ノードは各経路の通信状態を一定周期ごとに観測し、ある経路において品質劣化が検出されたならば該経路を通るパスの通信経路変更先を決定する通信経路決定方法において、
該発信元ノードは、経路ｉ（ｉ＝１，・・，Ｍ）上のボトルネックリンク容量Ｃｉを予め記憶しておき、一定周期τ毎に経路ｉへ送信される転送レートＤｉ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉを測定し、Ｄｉの平均レートであるａｖｇＤｉをａｖｇＤｉ←（１−γ）ａｖｇＤｉ＋γＤｉにより更新し、経路ｉにおける１ユーザ当りの使用帯域ＵｉをＵｉ←（１−α）Ｕｉ＋αＤｉ／Ｎｉにより更新し、同じく経路ｉ上のパスｊ（ｊ＝１，・・，ｎｉ）における転送レートＤｉ，ｊおよび平均同時接続ユーザフロー数Ｎｉ，ｊを測定し、その平均レートａｖｇＤｉ，ｊをａｖｇＤｉ，ｊ←（１−γ）ａｖｇＤｉ，ｊ＋γＤｉ，ｊにより更新し、パスｊにおける１ユーザ当りの使用帯域Ｕｉ，ｊをＵｉ，ｊ←（１−α）Ｕｉ，ｊ＋αＤｉ，ｊ／Ｎｉ，ｊにより更新し、Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めたパラメータβ，δ１を用いてｍｉｎ｛Ｕｉ／Ｃｉ｝＜βかつ（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＞δ１ならば品質劣化パスが存在すると判定し、ε１，ε２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅを満たす経路を品質劣化経路とし、Ｕｋの値で該経路を昇順に並び替え、そのときのｊ番目の該経路を品質劣化経路ｋｊ（ｋ１〜ｋＫ）とし、また、Ｕｍ＞（１＋ε２）×Ｕａｖｅを満たす経路を品質維持経路とし、Ｕｍの値で該経路を降順に並び替え、そのときのｊ番目の経路を品質維持経路ｍｊ（ｍｊ＝ｍ１〜ｍＭ）とし、品質劣化経路ｋｊから品質維持経路ｍｊへ移動すべきトラヒック量ｄｊをｄｊ＝｛（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ａｖｅＤｋｊ×δ｝（δは予め定めた係数）により算出し、品質劣化経路ｋｊのパス１のＵｋ，ｌを昇順に並び替え、ａｖｇＤｋ，１＋ａｖｇＤｋｊ，２＋・・・＋ａｖｇＤｋｊ，１＊＜ｄｊ＜ａｖｇＤｋｊ，１＋ａｖｇＤｋｊ，２＋・・・＋ａｖｇＤｋｊ，１＊＋ａｖｇＤｋｊ，（１＊＋１）を満たす１＊を求め、パス１から１＊までを経路ｋｊから経路ｍｊへ変更し、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行い、時間Ｔ（＞τ）が経過するまでの間、ＵｉおよびａｖｇＤｉおよびａｖｇＤｉ，ｊ，Ｕｉ，ｊの更新はτ毎に行い、時間Ｔを経過したなら、（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＜δ２あるいはｍｉｎ｛Ｕｉ／Ｃｉ｝＞βとなっているかを確認し、そうであれば、経路変更は終了し、そうでなければ経路変更を再度行うことを特徴とする通信経路決定方法。
【請求項２】
通信網内の発信元ノードと着信先ノードの間に論理パスがＭ本存在し、発信元ノードは各パスの通信状態を一定周期ごとに観測し、あるパスにおいて品質劣化が検出されたならば該パスの通信経路変更先を決定する通信経路決定方法において、
該発信元ノードは、パスｉ（ｉ＝１，・・，Ｍ）上のボトルネックリンク容量Ｃｉを予め記憶しておき、一定周期τ毎にパスｉへ送信される転送レートＤｉ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉを測定し、パスｉにおける１ユーザ当りの使用帯域ＵｉをＵｉ←（１−α）Ｕｉ＋αＤｉ／Ｎｉにより更新し、Ｄｉの平均レートであるａｖｇＤｉをａｖｇＤｉ←（１−γ）ａｖｇＤｉ＋γＤｉにより更新し、Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めたパラメータβ，δ１を用いてｍｉｎ｛Ｕｉ／Ｃｉ｝＜βかつ（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＞δ１ならば品質劣化パスが存在すると判定し、ε１，ε２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅを満たすパスを品質劣化パスｋとし、Ｕｋの値で該パスを昇順に並び替え、そのときのｊ番目の該パスを品質劣化パスｋｊ（ｋ１〜ｋＫ）とし、また、Ｕｍ＞（１＋ε２）×Ｕａｖｅを満たすパスを品質維持パスｍとし、品質劣化パスｋｊに対し、｛Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）｝＞（１−ε１）×Ｕａｖｅを満たす品質維持パスｍを検索し、見つかったら品質劣化パスｋｊの経路を品質維持パスｍと同じ経路に変更し、見つからなければ、該発信元ノードと着信先ノード間に現在トラヒックが流れていない予備の経路に変更し、その後、一時的にＵｍの値をＵｍ←｛Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）｝に更新し、ａｖｇＤｍ←ａｖｇＤｍ＋ａｖｇＤｋｊに更新し、以上の操作をｊ＝１〜Ｋに対して行い、その後、Ｕｍ，ａｖｇＤｍの値が一時的に更新されたパスに関しては、それらの値を元に戻し、時間Ｔ（＞τ）が経過するまでの間、Ｕｉ，ａｖｇＤｉの更新はτ毎に行い、時間Ｔが経過したなら、（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＜δ２あるいはｍｉｎ｛Ｕｉ／Ｃｉ｝＞βとなっているかを確認し、そうであれば、経路変更を終了し、そうでなければ経路変更を再度行うことを特徴とする通信経路決定方法。
【請求項３】
通信網内の発信元ノードと着信先ノードの間に論理パスがＭ本存在し、発信元ノードは各パスの通信状態を一定周期ごとに観測し、あるパスにおいて品質劣化が検出されたならば該パスの通信経路変更先を決定する通信経路決定方法において、
網内における各内部ノードは、各リンクｉにおける転送レートＤｉ ｌｉｎｋ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉ ｌｉｎｋを一定周期τ毎に測定し、リンクｉにおける１ユーザ当りの使用帯域Ｕｉ ｌｉｎｋをＵｉ ｌｉｎｋ←（１−α）Ｕｉ ｌｉｎｋ＋αＤｉ ｌｉｎｋ／Ｎｉ ｌｉｎｋにより更新し、Ｄｉ ｌｉｎｋの平均レートであるａｖｇＤｉ ｌｉｎｋをａｖｇＤｉ ｌｉｎｋ←（１−γ）ａｖｇＤｉ ｌｉｎｋ＋γＤｉ ｌｉｎｋにより更新し、Ｕｉ ｌｉｎｋおよびａｖｇＤｉ ｌｉｎｋを網の境界に位置する送信元ノードへ通知し、
該送信元ノードは、請求項２と同様に各論理パスの品質状態を監視し、品質劣化パスｋｊ（ｋ１〜ｋＫ）を検出したならば、ｍｉｎ｛Ｕｉ ｌｉｎｋ｝を最大にする経路を探索し、そのパスの変更先経路として決定し、その経路上の各リンクにおけるＵｉ ｌｉｎｋの値を一時的にＵｉ ｌｉｎｋ←Ｕｉ ｌｉｎｋ−（ａｖｇＤｋｊ／ａｖｇＤｉ ｌｉｎｋ）×（Ｃｉ−Ｕｉ ｌｉｎｋ）（Ｃｉはリンクｉのリンク容量）に更新し、ａｖｇＤｉ ｌｉｎｋ←ａｖｇＤｉ ｌｉｎｋ＋ａｖｇＤｋｊに更新し、以上の操作をｊ＝１〜Ｋに対して行い、その後、Ｕｉｌｉｎｋ，ａｖｇＤｉ ｌｉｎｋの値が一時的に更新されたパスに関しては、それらの値を元に戻し、その後、請求項２と同様の方法で品質監視を行い、経路変更を行うことを特徴とする通信経路決定方法。
【請求項４】
通信網内の発信元ノードと着信先ノードの間に論理パスの設定要求があった場合に、網内の各リンクの通信状況に応じて該パスの通信経路を決定する通信経路決定方法において、
網内における各内部ノードは、各リンクｉにおける転送レートＤｉ ｌｉｎｋ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉ ｌｉｎｋを一定周期τ毎に測定し、リンクｉにおける１ユーザ当りの使用帯域Ｕｉ ｌｉｎｋをＵｉ ｌｉｎｋ←（１−α）Ｕｉ＋αＤｉ ｌｉｎｋ／Ｎｉ ｌｉｎｋにより更新し、Ｕｉｌｉｎｋを網の境界に位置する送信元ノードへ通知し、
該送信元ノードは、新たな論理パスを設定する要求がユーザからあった場合に、最新のＵｉ ｌｉｎｋの値を用いて、ｍｉｎ｛Ｕｉ ｌｉｎｋ｝を最大にする経路を探索し、そのパスの通信経路として設定することを特徴とする通信経路決定方法。
【請求項５】
請求項１または２のいずれかに記載の方法で、Ｎｉ，Ｄｉ，Ｕｉの測定を一定周期τ毎に行って品質劣化パスを検出する手段と、請求項１から４のいずれかに記載の方法で品質劣化パスの経路あるいは新たなパス設定要求に対する経路を決定する手段とを具備することを特徴とする通信経路決定装置。
【請求項６】
ユーザから到着したパケットを受けると、転送すべきパスを示すパスラベルをパケットヘッダに書き込むパス設定部と、
該パス設定部から受け取ったパケットのパケットサイズ、ＴＣＰフラグ情報を読み取り解析するパケットヘッダ解析部と、
該パケットヘッダ解析部からパケットを受け取り、該パケットのパスラベルから転送すべき経路を読み出し、該経路に転送する経路制御部と、
該パケットヘッダ解析部からパケットを受け取り、通過したパケットのサイズを計算し、転送レートと平均レートを更新し、転送レートを通知する転送レート測定部と、
該パケットヘッダ解析部からＴＣＰフラグ情報を受け取り、ＴＣＰフロー開始、フロー終了を示すパケットに対して、カウンタを増減してユーザフロー数を測定するユーザフロー数測定部と、
該転送レート測定部から転送レートおよび該ユーザフロー数測定部からユーザフロー数を受け取り、パスの１ユーザ当りの使用帯域を更新し、１ユーザ当りの平均使用帯域を計算する１ユーザ使用帯域算出部と、
該ユーザフロー数測定部から平均使用帯域およびパラメータを受け取り、品質劣化パスの存在を判定し、経路を並び替えて品質維持パスを通知するパス品質判定部と、
該パス品質判定部から品質劣化パスの通知を受けると、品質維持パスを検索し、該品質劣化パスの経路を該品質維持パスと同じ経路に変更するよう、該パス設定部に通知する変更経路決定部と
を具備することを特徴とする通信経路決定装置。
【請求項７】
通信経路を決定するプログラムであって、
発信元ノードに、請求項１または２に記載の手順をそれぞれ実行させるための通信経路決定用プログラム。
【請求項８】
通信経路を決定するための準備用プログラムであって、
網内における各内部ノードに、請求項３または４に記載の手順、および、１ユーザ当りの使用帯域および平均転送レートを網の境界に位置する送信元ノードへ通知する手順を、それぞれ実行させるための通信経路決定準備用プログラム。
【請求項９】
通信経路を決定するプログラムであって、
発信元ノードに、請求項３または４に記載の手順をそれぞれ実行させるための通信経路決定用プログラム。
【請求項１０】
請求項７〜９のいずれかに記載のプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＩＰネットワーク上において負荷分散を図るための通信経路決定方法および装置、ならびにそのプログラムに関する。
【０００２】
【従来の技術】
ＩＰネットワークが広く利用されてくるに伴って、ＩＰネットワーク上での通信品質保証に対する要求が高まっている。それにつれて、あるリンクに負荷が集中して品質が劣化することを回避するために、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）のような経路を明示的に指定できる技術を用いて、負荷分散を図る方法が考えられている。これまでの負荷分散方法は、下記特許文献の▲１▼〜▲４▼および下記非特許文献の▲１▼〜▲４▼に示すように、主にリンク使用率やトラヒック量［ｂｐｓ］，リンク容量のみをパラメータとして用いており、各経路のリンク使用率や空きリンク容量に基づいて負荷分散を行っている。
【０００３】
しかし、リンク使用率とユーザの体感するファイル転送時間やスループット等の品質との関連が不明であるため、例えば、ある２つの経路のリンク使用率が同じであったとしても、同時接続ユーザ数等の条件によって、ある一方の経路におけるユーザ通信品質は劣化している可能性がある，という問題点があった。このことは、下記非特許文献▲９▼に示されている。
【０００４】
また、パスの設定要求がユーザからあった場合、併せて必要な帯域を通知させ、その帯域が各リンクにおいて確保できるか否かを判定し、可能であればパスを張って、その経路上の使用可能帯域を減算する、という資源予約型の経路設定方法も考察されている（例えば、下記特許文献▲５▼〜▲７▼および下記非特許文献▲５▼▲６▼参照）。
【０００５】
この方法では、常にユーザが要求帯域に応じた分のトラヒックを送出していない場合には、ネットワーク内のリンク使用効率は悪くなる恐れがある。また、必要な帯域が確保できないときは、そのユーザはパスを張ることができず、通信を開始できないという場合も起こり得る、という問題点があった。
【０００６】
一方、リンクを通過するフローのファイル転送時間やスループットを直接測定して、その値を見て負荷分散を行うという方法も考えられるが、その方法は、ファイル転送時間やスループットというユーザ品質を、当該リンク上を通過する全てのパケットをキャプチャし、フローを組み上げて算出するか（例えば、下記非特許文献▲７▼参照）、もしくは、当該リンクの前段か後段もしくは両方に試験パケット送受信機を設置して、試験パケットを送信することにより品質測定を能動的に行う必要があり（例えば、下記非特許文献▲８▼参照）、一般的にこれらはデータ蓄積のためのリソースが必要となるか、専用の測定装置が必要となり、コストが増大してしまう、という問題点があった。
【０００７】
【特許文献１】
▲１▼特開２００２−２４７０８７号公報
【特許文献２】
▲２▼特開２００２−１９０８２５号公報
【特許文献３】
▲３▼特開２０００−２５３０５８号公報
【特許文献４】
▲４▼特開２００１−１４４８０４号公報
【特許文献５】
▲５▼特開２００２−２５２６３９号公報
【特許文献６】
▲６▼特開平９−８３５４６号公報
【特許文献７】
▲７▼特開２００２−５７７１０号公報
【０００８】
【非特許文献１】
▲１▼Ｙ．Ｗａｎｇ  ａｎｄ  Ｚ．Ｗａｎｇ，“Ｅｘｐｌｃｉｔ  Ｒｏｕｔｉｎｇ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｉｎｔｅｒｎｅｔ  Ｔｒａｆｆｉｃ  Ｅｎｇｉｎｅｅｒｉｎｇ，”ＩＣＣＣＮ９９．
【非特許文献２】
▲２▼宗宮利夫，仲道耕二，高島研也，小林信之，“ＩＰトラヒックエンジニアリングにおけるロードバランシング方式の検討，”電子情報通信学会技術研究報告ＳＳＥ２０００−５３，ｐｐ．１９−２４，２０００．
【非特許文献３】
▲３▼山口仁，吉岡弘高，栗原伸明，“ＭＰＬＳを用いたトラフィック分散方式に関する一考察，”電子情報通信学会総合大会，Ｂ−６−２２，２００１．
【０００９】
【非特許文献４】
▲４▼宮村崇，栗本崇，青木道宏，山中直明，“ＭＰＬＳのＥｘｐｌｉｃｉｔＲｏｕｔｉｎｇを用いた負荷分散方式に関する一考察，”電子情報通信学会技術研究報告ＳＳＥ２０００−５４，ｐｐ，２５−３０，２０００．
【非特許文献５】
▲５▼亀井聡，木村卓巳，“ＭＰＬＳトラヒックエンジニアリングにおけるアルゴリズム／トポロジ評価，”電子情報通信学会技術研究報告ＩＮ２０００−１４３，ｐｐ，６１−６６，２０００．
【非特許文献６】
▲６▼Ｑ．Ｍａ，Ｐ．Ｓｔｅｅｎｋｉｓｔｅ，ａｎｄ  Ｈ．Ｚｈａｎｇ，“Ｒｏｕｔｉｎｇ  Ｈｉｇｈ−ｂａｎｄｗｉｄｔｈ  Ｔｒａｆｆｉｃ  ｉｎ  Ｍａｘ−ｍｉｎ  Ｆａｉｒ  Ｓｈａｒｅ  Ｎｅｔｗｏｒｋｓ，”ＡＣＭ  ＳＩＧＣＯＭＭ’９６，ｐｐ，２０６−２１７，１９９６．
【００１０】
【非特許文献７】
▲７▼Ｊ．Ｑｕｉｔｔｅｋ，Ｔ．Ｚｓｅｂｙ，Ｇ．Ｃａｒｌｅ，ａｎｄ  Ｓ．Ｚａｎｄｅｒ，“Ｔｒａｆｆｉｃ  ｆｌｏｗ  ｍｅａｓｕｒｅｍｅｎｔｓｗｉｔｈｉｎ  ＩＰ  ｎｅｔｗｏｒｋｓ：ｒｅｑｕｉｒｅｍｅｎｔｓ．ｔｅｃｈｎｏｌｏｇｉｅｓ  ａｎｄ  ｓｔａｎｄａｒｄｉｚａｔｉｏｎ，”ＩＥＥＥ  ＳＡＩＮＴ  ２００２．ｐｐ．９７−９８，２００２．
【非特許文献８】
▲８▼“ＣＡＩＤＡ（ｃｏｏｐｅｒａｔｉｖｅ  ａｓｓｏｃｉａｔｉｏｎ  ｆｏｒ  Ｉｎｔｅｒｎｅｔ  ｄａｔａ  ａｎａｌｙｓｉｓ），”ｈｔｔｐ：／／ｗｗｗ．ｃａｉｄａ．ｏｒｇ／ｔｏｏｌｓ／．
【非特許文献９】
▲９▼川原亮一，峰野博史，“ＡＰ性能を考慮した複数経路負荷分散法に関する一考察，”電子情報通信学会ソサイエティ大会，Ｂ−７−４４，２００２．
【００１１】
【発明が解決しようとする課題】
上記の問題点を解決するため、本出願人（本発明者）は、本願出願前に特願２００２−２１５２７５号明細書および図面に記載の『複数経路負荷分散方法および装置、ならびにそのプログラム』（以下、Ａ方式と呼ぶ）を提案した。これは、測定が簡易な同時接続ユーザフロー数と使用帯域、および経路上の各リンク使用率、という値のみから、ネットワーク内のリンクを効率的に利用して各経路上のユーザ通信品質を均等に維持できるような複数経路負荷分散方法を提案した。
【００１２】
しかしながら、上記提案の方法では、下記のような問題点があった。
（１）予め張られた複数の経路間において、ある経路上のトラヒックの一部を予め張られた別の経路へ変更する場合にしか対応しておらず、経路単位での品質維持にしか対応しておらず、ユーザパス単位での品質管理やパス切り替えに対応していなかった。
（２）ユーザから新たなパスを張りたいという要求があった場合に、そのパスを張る方法について言及していなかった。
【００１３】
（３）網内において、経路上の各リンク使用率を測定して、その結果を網の境界に位置する送信元ノードに通知する機能が必要であり、ネットワーク規模が大きくなると、網の内部ノードは制御のための処理負荷が大きくなってしまい、かつ多数の制御用トラヒックが網に加わってしまう。
（４）経路変更を一定周期毎に実施する必要があり、経路変更後の制御の効果が現われるのに時間を要する場合には、制御が安定しない可能性があった。
【００１４】
（目的）
そこで、本発明の目的は、上述の問題点に鑑み、送信元ノードのみで測定可能な同時接続ユーザフロー数と使用帯域という値のみから各経路上のユーザパス通信品質を均等に維持できるような通信経路を決定することができ、または、新たなパスを張りたい場合にも対応して通信経路を決定することができる通信経路決定方法および装置、ならびにそのプログラムを提供することにある。
【００１５】
【課題を解決するための手段】
本発明の通信経路決定方法は、▲１▼通信網内の発信元ノードと着信先ノードの間に経路がＭ本存在し、経路ｉ上にｎｉ本の論理パスが張られ、発信元ノードは各経路の通信状態を一定周期ごとに観測し、ある経路において品質劣化が検出されたならば該経路を通るパスの通信経路変更先を決定する通信経路決定方法において、該発信元ノードは、経路ｉ（ｉ＝１，・・，Ｍ）上のボトルネックリンク容量Ｃｉを予め記憶しておき、一定周期τ毎に経路ｉへ送信される転送レートＤｉ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉを測定し、Ｄｉの平均レートであるａｖｇＤｉをａｖｇＤｉ←（１−γ）ａｖｇＤｉ＋γＤｉにより更新し、経路ｉにおける１ユーザ当りの使用帯域ＵｉをＵｉ←（１−α）Ｕｉ＋αＤｉ／Ｎｉにより更新し、同じく経路ｉ上にパスｊ（ｊ＝１，・・，ｎｉ）における転送レートＤｉ，ｊおよび平均同時接続ユーザフロー数Ｎｉ，ｊを測定し、その平均レートａｖｇＤｉ，ｊをａｖｇＤｉ，ｊ←（１−γ）ａｖｇＤｉ，ｊ＋γＤｉ，ｊにより更新し、パスｊにおける１ユーザ当りの使用帯域Ｕｉ，ｊをＵｉ，ｊ←（１−α）Ｕｉ，ｊ＋αＤｉ，ｊ／Ｎｉ，ｊにより更新し、Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めたパラメータβ，δ１を用いてｍｉｎ｛Ｕｉ／Ｃｉ｝＜βかつ（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＞δ１ならば品質劣化パスが存在すると判定し、ε１，ε２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅを満たす経路を品質劣化経路とし、Ｕｋの値で該経路を昇順に並び替え、そのときのｊ番目の該経路を品質劣化経路ｋｊ（ｋ１〜ｋＫ）とし、また、Ｕｍ＞（１＋ε２）×Ｕａｖｅを満たす経路を品質維持経路とし、Ｕｍの値で該経路を降順に並び替え、そのときのｊ番目の経路を品質維持経路ｍｊ（ｍｊ＝ｍ１〜ｍＭ）とし、品質劣化経路ｋｊから品質維持経路ｍｊへ移動すべきトラヒック量ｄｊをｄｊ＝｛（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ａｖｅＤｋｊ×δ｝（δは予め定めた係数）により算出し、品質劣化経路ｋｊのパス１のＵｋ，ｌを昇順に並び替え、ａｖｇＤｋ，１＋ａｖｇＤｋｊ，２＋・・・＋ａｖｇＤｋｊ，１＊＜ｄｊ＜ａｖｇＤｋｊ，１＋ａｖｇＤｋｊ，２＋・・・＋ａｖｇＤｋｊ，１＊＋ａｖｇＤｋｊ，（１＊＋１）を満たす１＊を求め、パス１から１＊までを経路ｋｊから経路ｍｊへ変更し、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行い、時間Ｔ（＞τ）が経過するまでの間、Ｕｉ，ａｖｇＤｉおよびＵｉ，ｊおよびａｖｇＤｉ，ｊの更新はτ毎に行い、時間Ｔを経過したなら、（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＜δ２あるいはｍｉｎ｛Ｕｉ／Ｃｉ｝＞βとなっているかを確認し、そうであれば、経路変更は終了し、そうでなければ経路変更を再度行うことを特徴としている。
【００１６】
▲２▼また、通信網内の発信元ノードと着信先ノードの間に論理パスがＭ本存在し、発信元ノードは各パスの通信状態を一定周期ごとに観測し、あるパスにおいて品質劣化が検出されたならば該パスの通信経路変更先を決定する通信経路決定方法において、該発信元ノードは、パスｉ（ｉ＝１，・・，Ｍ）上のボトルネックリンク容量Ｃｉを予め記憶しておき、一定周期τ毎にパスｉへ送信される転送レートＤｉ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉを測定し、パスｉにおける１ユーザ当りの使用帯域ＵｉをＵｉ←（１−α）Ｕｉ＋αＤｉ／Ｎｉにより更新し、Ｄｉの平均レートであるａｖｇＤｉをａｖｇＤｉ←（１−γ）ａｖｇＤｉ＋γＤｉにより更新し、Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めたパラメータβ，δ１を用いてｍｉｎ｛Ｕｉ／Ｃｉ｝＜βかつ（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＞δ１ならば品質劣化パスが存在すると判定し、ε１，ε２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅを満たすパスを品質劣化パスｋとし、Ｕｋの値で該パスを昇順に並び替え、そのときのｊ番目の該パスを品質劣化パスｋｊ（ｋ１〜ｋＫ）とし、また、Ｕｍ＞（１＋ε２）×Ｕａｖｅを満たすパスを品質維持パスｍとし、品質劣化パスｋｊに対し、｛Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）｝＞（１−ε１）×Ｕａｖｅを満たす品質維持パスｍを検索し、見つかったら品質劣化パスｋｊの経路を品質維持パスｍと同じ経路に変更し、その後、一時的にＵｍの値をＵｍ←｛Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）｝に更新し、ａｖｇＤｍ←ａｖｇＤｍ＋ａｖｇＤｋｊに更新し、以上の操作をｊ＝１〜Ｋに対して行い、見つからなかったら、該発信元ノードと着信先ノード間に現在トラヒックが流れていない予備の経路に変更し、その後、Ｕｍ，ａｖｇＤｍの値が一時的に更新されたパスに関しては、それらの値を元に戻し、時間Ｔ（＞τ）が経過するまでの間、Ｕｉ，ａｖｇＤｉの更新はτ毎に行い、時間Ｔが経過したなら、（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＜δ２あるいはｍｉｎ｛Ｕｉ／Ｃｉ｝＞βとなっているかを確認し、そうであれば、経路変更を終了し、そうでなければ経路変更を再度行うことも特徴としている。
【００１７】
▲３▼また、通信網内の発信元ノードと着信先ノードの間に論理パスがＭ本存在し、発信元ノードは各パスの通信状態を一定周期ごとに観測し、あるパスにおいて品質劣化が検出されたならば該パスの通信経路変更先を決定する通信経路決定方法において、網内における各内部ノードは各リンクｉにおける転送レートＤｉ ｌｉｎｋ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉ ｌｉｎｋを一定周期τ毎に測定し、リンクｉにおける１ユーザ当りの使用帯域Ｕｉ ｌｉｎｋをＵｉ ｌｉｎｋ←（１−α）Ｕｉ ｌｉｎｋ＋αＤｉ ｌｉｎｋ／Ｎｉ ｌｉｎｋにより更新し、Ｄｉ ｌｉｎｋの平均レートであるａｖｇＤｉ ｌｉｎｋをａｖｇＤｉ ｌｉｎｋ←（１−γ）ａｖｇＤｉ ｌｉｎｋ＋γＤｉ ｌｉｎｋにより更新し、Ｕｉ ｌｉｎｋおよびａｖｇＤｉ ｌｉｎｋを網の境界に位置する送信元ノードへ通知し、該送信元ノードは、上記▲２▼と同様に各論理パスの品質状態を監視し、品質劣化パスｋｊ（ｋ１〜ｋＫ）を検出したならば、ｍｉｎ｛Ｕｉ ｌｉｎｋ｝を最大にする経路を探索し、そのパスの変更先経路として決定し、その経路上の各リンクにおけるＵｉ ｌｉｎｋの値を一時的にＵｉ ｌｉｎｋ←Ｕｉｌｉｎｋ−（ａｖｇＤｋｊ／ａｖｇＤｉ ｌｉｎｋ）×（Ｃｉ−Ｕｉ ｌｉｎｋ）（Ｃｉはリンクｉのリンク容量）に更新し、ａｖｇＤｉ ｌｉｎｋ←ａｖｇＤｉ ｌｉｎｋ＋ａｖｇＤｋｊに更新し、以上の操作をｊ＝１〜Ｋに対して行い、その後、Ｕｉ ｌｉｎｋ，ａｖｇＤｉ ｌｉｎｋの値が一時的に更新されたパスに関しては、それらの値を元に戻し、その後、上記▲２▼と同様の方法で品質監視を行い、経路変更を行うことも特徴としている。
【００１８】
▲４▼また、通信網内の発信元ノードと着信先ノードの間に論理パスの設定要求があった場合に、網内の各リンクの通信状況に応じて該パスの通信経路を決定する通信経路決定方法において、網内における各内部ノードは各リンクｉにおける転送レートＤｉ ｌｉｎｋ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉ ｌｉｎｋを一定周期τ毎に測定し、リンクｉにおける１ユーザ当りの使用帯域ＵｉｌｉｎｋをＵｉ ｌｉｎｋ←（１−α）Ｕｉ＋αＤｉ ｌｉｎｋ／Ｎｉ ｌｉｎｋにより更新し、Ｕｉ ｌｉｎｋを網の境界に位置する送信元ノードへ通知し、該送信元ノードは、新たな論理パスを設定する要求がユーザからあった場合に、最新のＵｉ ｌｉｎｋの値を用いて、ｍｉｎ｛Ｕｉ ｌｉｎｋ｝を最大にする経路を探索し、そのパスの通信経路として設定することも特徴としている。
【００１９】
▲５▼また、本発明の通信経路決定装置は、上記▲１▼または▲２▼のいずれかに記載の方法で、Ｎｉ，Ｄｉ，Ｕｉの測定を一定周期τ毎に行って品質劣化パスを検出する手段と、上記▲１▼から▲４▼のいずれかに記載の方法で品質劣化パスの経路あるいは新たなパス設定要求に対する経路を決定する手段とを具備することを特徴としている。
【００２０】
【発明の実施の形態】
以下、本発明の原理と実施形態について、図面により詳細に説明する。
（原理）
ある経路における平均同時接続ユーザフロー数をＮ、そのリンクの平均使用帯域をＤ、ダウンロードするファイルサイズの平均をＦ、平均ファイル転送時間をＴと置くと、待ち行列理論におけるリトルの公式から、Ｎ＝Ｄ／Ｆ×Ｔの関係式が立成する。
【００２１】
すなわち、１ユーザ当りの使用帯域をＵ（＝Ｄ／Ｎ）と置くと、Ｕ＝Ｆ／Ｔ（ファイル転送速度に相当）となる。従って、経路ａにおけるＵａと経路ｂにおけるＵｂが等しくなれば（平均ファイルサイズが同じであれば）、平均ファイル転送時間も等しくできることになる。そこで、本発明においては、Ｕをユーザ通信品質を表すパラメータとして用い、各経路上のＵが等しくなるように負荷分散を行う。また、経路変更後、一定時間を置けば、制御の効果がＵの値に現われる。
【００２２】
何故ならば、例えば経路ａが品質劣化していると仮定し、その経路上のあるユーザのパスを経路ｂに切り替えた場合、経路ｂの品質状態がよいとすると、ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）のフロー制御により経路ｂ上でのファイル転送時間は速くなり、それに伴って１ユーザ当りの使用帯域Ｕも大きくなるからである。つまり、制御を実施した効果は、送信元ノードで測定できるＵの値のみを見れば把握できる。従って、従来の方法（例えば、前記特許文献▲１▼〜▲４▼、前記非特許文献▲１▼〜▲４▼参照）および前記Ａ方式のように、経路上の各リンク使用率を見て、負荷が減ったことを確認する必要がない。
【００２３】
（第１の実施形態）
図１は、本発明の第１の実施形態を示すネットワーク構成の図である。
図１に示すように、本発明の第１の実施形態である通信経路決定方法では、通信網において発信元ノード１０と着信先ノード２０との間に経路がＭ本存在し、経路ｉ上にｎｉ本の論理パスが張られる。発信元ノードは、経路ｉ（ｉ＝１・・・，Ｍ）上のボトルネックリンク容量Ｃｉを予め記憶しておき、一定周期τ毎に経路ｉへ送信される転送レートＤｉ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉを測定し、Ｄｉの平均レートであるａｖｇＤｉをａｖｇＤｉ←（１−γ）ａｖｇＤｉ＋γＤｉにより更新し、経路ｉにおける１ユーザ当りの使用帯域ＵｉをＵｉ←（１−α）Ｕｉ＋αＤｉ／Ｎｉにより更新する。
【００２４】
同様に、経路ｉ上のパスｊ（ｊ＝１，・・ｎｉ）における転送レートＤｉ，ｊおよび平均同時接続ユーザフロー数Ｎｉ，ｊを測定し、その平均レートａｖｇＤｉ，ｊをａｖｇＤｉ，ｊ←（１−γ）ａｖｇＤｉ，ｊ＋γＤｉ，ｊにより更新し、パスｊにおける１ユーザ当りの使用帯域Ｕｉ，ｊをＵｉ，ｊ←（１−α）Ｕｉ，ｊ＋αＤｉ，ｊ／Ｎｉ，ｊにより更新する。
【００２５】
Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めたパラメータβ，δ１を用いてｍｉｎ｛Ｕｉ／Ｃｉ｝＜βで、かつ（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＞δ１であれば、品質劣化パスが存在すると判定する。ε１，ε２を用いてＵｋ＜（１−ε１）×Ｕａｖｅを満たす経路を品質劣化経路とし、Ｕｋの値で該経路を昇順に並び替え、そのときのｊ番目の該経路を品質劣化経路ｋｊ（ｋｊ＝ｋ１〜ｋＫ）とする。また、Ｕｍ＞（１＋ε２）×Ｕａｖｅを満たす経路を品質維持経路とし、Ｕｍの値で該経路を降順に並び替え、そのときのｊ番目の経路を品質維持経路ｍｊ（ｍｊ＝ｍ１〜ｍＭ）とする。
【００２６】
品質劣化経路ｋｊから品質維持経路ｍｊへ移動すべきトラヒック量ｄｊをｄｊ＝｛（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ａｖｅＤｋｊ×δ（δは予め定めた係数）により算出する。品質劣化経路ｋｊのパス１のＵｋｊ，１を昇順に並び替え、ａｖｇＤｋ，１＋ａｖｇＤｋｊ，２＋・・・＋ａｖｇＤｋｊ，１＊＜ｄｊ＜ａｖｇＤｋ，１＋ａｖｇＤｋｊ，２＋・・・＋ａｖｇＤｋｊ，１＊ａｖｇＤｋｊ，（１＊＋１）を満たす１＊を求め、パス１から１：１＊までを経路ｋｊから経路ｍｊへ変更する。
【００２７】
これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行う。時間Ｔ（＞τ）が経過するまでの間、Ｕｉ、ａｖｇＤｉ、Ｕｉ，ｊ、ａｖｇＤｉ，ｊの更新はτ毎に行い、時間Ｔが経過したならば、（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＜δ２あるいはｍｉｎ｛Ｕｉ／Ｃｉ｝＞βとなっているかを確認し、そうであれば、経路変更は終了し、そうでなければ、経路変更を再度行う。
【００２８】
ここで、品質劣化経路ｋｊから品質維持経路ｍｊへ移動するトラヒック量をｄｊ＝｛（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ａｖｇＤｋｊを用いて算出している根拠について説明する。
図２は、ユーザ使用帯域とトラヒック量の関係、およびトラヒックの一部が別の経路へ移動して減った後の１ユーザ使用帯域の予測値を示したグラフである。図２に示すように、一般にＵは加わるトラヒック量ａｖｇＤに対して単調減少し、またａｖｇＤが０に近づいたときにＵはリンク容量Ｃｋｊを超えることはない。
【００２９】
そこで、ＵとａｖｇＤの関係を図２のように線形近似し、経路変更後にＵ＝Ｕａｖｅとなるように移動すべきトラヒック量ｄｊを算出している。また、経路変更するパスとして、Ｕｋｊ，１の値が小さいものから１＊目までを対象とすることにより、品質劣化度が高いユーザパス（すなわち、Ｕの値が小さいパス）を優先的に経路変更できる。
【００３０】
（第２の実施形態）
図３は、本発明の第２〜第４の実施形態が適用されるネットワーク構成図である。
図３に示すように、本発明の第２の通信経路決定方法においては、通信網において発信元ノード１０と着信先ノード２０の間に論理パスがＭ本存在している。発信元ノード１０は、パスｉ（ｉ＝１，・・，Ｍ）上のボトルネックリンク量Ｃｉを予め記憶しておき、一定周期τ毎にパスｉへ送信される転送レートＤｉ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉを測定し、パスｉにおける１ユーザ当りの使用帯域ＵｉをＵｉ←（１−α）Ｕｉ＋αＤｉ／Ｎｉにより更新し、Ｄｉの平均レートであるａｖｇＤｉをａｖｇＤｉ←（１−γ）ａｖｇＤｉ＋γＤｉにより更新する。
【００３１】
Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めたパラメータβ，δ１を用いてｍｉｎ｛Ｕｉ／Ｃｉ｝＜βで、かつ（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＞δ１ならば、品質劣化パスが存在すると判定する。ε１，ε２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅを満たすパスを品質劣化パスｋとし、Ｕｋの値で該経路を昇順に並び替え、そのときのｊ番目の該経路を品質劣化パスｋｊ（ｋｊ＝ｋ１〜ｋＫ）とする。また、Ｕｍ＞（１＋ε２）×Ｕａｖｅを満たす経路を、品質維持パスｍとする。
【００３２】
品質劣化パスｋｊに対し、｛Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）｝＞（１−ε１）×Ｕａｖｅを満たす品質維持パスｍを検索し、見つかったならば品質劣化パスｋｊの経路を品質維持パスｍと同じ経路に変更し、見つからなかったら、該発信元ノードと着信先ノード間に現在トラヒックが流れていない予備の経路に変更し、その後、一時的にＵｍの値をＵｍ←｛Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）｝に更新し、ａｖｇＤｍ←ａｖｇＤｍ＋ａｖｇＤｋｊに更新する。
【００３３】
以上の操作をｊ＝１〜Ｋに対して行い、その後、Ｕｍ，ａｖｇＤｍの値が一時的に更新されたパスに関しては、それらの値を元に戻す。時間Ｔ（＞τ）が経過するまでの間、ＵｉおよびａｖｇＤｉの更新はτ毎に行い、時間Ｔが経過したならば、（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＜δ２あるいはｍｉｎ｛Ｕｉ／Ｃｉ｝＞βとなっているかを確認し、そうであれば、経路変更は終了し、そうでなければ経路変更を再度行う。
【００３４】
図４は、ユーザ使用帯域とトラヒック量の関係、およびトラヒックの一部が別の経路から移動して増えた後の１ユーザ使用帯域の予測値を示したグラフである。
ここで、経路変更後にＵｍの値をＵｍ←Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）に変更する根拠について下記に述べる。経路変更後の値を、Ｕｍ’と置くと、図４の線形近似により、｛Ｕｍ−Ｕｍ’）／ａｖｇＤｋｊ＝（Ｃｍ−Ｕｍ）／ａｖｇＤｍの関係が成り立つとして、ａｖｇＤｋｊが加わった後のＵｍ’の値をＵｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）により推定している。
【００３５】
Ｕｍの値を一時的にＵｍ’に変更する理由は、ある品質劣化パスの経路変更先を決める際に、既に別の品質劣化パスの経路変更先として選ばれている場合には、その分のトラヒック量増加に伴うＵｍの減少を反映させておく必要があるからである。
【００３６】
（第３の実施形態）
本発明の第３の実施形態である通信経路決定方法においては、通信網において発信元ノード（図３の１０）と着信先ノード（同２０）の間に論理パスがＭ本存在する。網内における各内部ノードは、各リンクｉにおける転送レートＤｉ ｌｉｎｋ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉ ｌｉｎｋを一定周期τ毎に測定し、リンクｉにおける１ユーザ当りの使用帯域Ｕｉ ｌｉｎｋをＵｉｌｉｎｋ←（１−α）Ｕｉ ｌｉｎｋ＋αＤｉ ｌｉｎｋ／Ｎｉ ｌｉｎｋにより更新し、Ｄｉ ｌｉｎｋの平均レートであるａｖｇＤｉ ｌｉｎｋをａｖｇＤｉ ｌｉｎｋ←（１−γ）ａｖｇＤｉ ｌｉｎｋ＋γＤｉ ｌｉｎｋにより更新する。
【００３７】
以上の操作をｊ＝１〜Ｋに対して行い、その後、Ｕｉ ｌｉｎｋ，ａｖｇＤｉｌｉｎｋの値が一時的に更新されたパスに関しては、それらの値を元に戻す。その後、第２の実施形態と同様な方法で品質監視を行い、経路変更を行う。
ここでは、網内の各リンクでＤｉ ｌｉｎｋ、Ｕｉ ｌｉｎｋが測定可能で、それを送信元ノード１０へ通知可能なネットワークを前提としている。この場合には、ネットワーク内部での測定が必要となるが、その代わり、第１、第２の実施形態では、既にいずれかのユードパスが張ってある経路と同じ経路のみが変更先経路の候補として選ばれていたのに対して、第３の実施形態では、既に張っていない新たなパスも探索することが可能となる。
【００３８】
（第４の実施形態）
第４の実施形態である通信経路決定方法では、網内における各内部ノードは、各リンクｉにおける転送レートＤｉ ｌｉｎｋ［ｂｐｓ］および平均同時接続ユーザフロー数Ｎｉ ｌｉｎｋを一定周期τ毎に測定し、リンクｉにおける１ユーザ当りの使用帯域Ｕｉ ｌｉｎｋをＵｉ ｌｉｎｋ←（１−α）Ｕｉ ｌｉｎｋ＋αＤｉ ｌｉｎｋ／Ｎｉ ｌｉｎｋにより更新し、Ｕｉ ｌｉｎｋを網の境界に位置する送信元ノード１０へ通知する（図３参照）。
【００３９】
送信元ノード１０は、新たな論理パスを設定する要求がユーザからあった場合に、最新のＵｉ ｌｉｎｋの値を用いて、ｍｉｎ｛Ｕｉ ｌｉｎｋ｝を最大にする経路をそのパスの通信経路として設定する。
この方法も、第３の実施形態と同様に、ネットワーク内部での測定が必要となるが、その代わりに、新たなパス設定要求があった場合に、既に張っていない新たなパスを探索することが可能となる。
【００４０】
（第５の実施形態）
本発明の第５の実施形態である通信経路決定装置においては、第１、第２の実施形態の方法で、Ｎｉ，Ｄｉ，Ｕｉの測定を一定周期τ毎に行い、品質劣化パスを検出する手段と、第１から第４の実施形態のいずれかの方法で、品質劣化パスの経路あるいは新たなパス設定要求に対する経路を決定する手段とを設ける。
【００４１】
（実施例）
前述のように、図３は、本発明の第２〜第４の実施形態が適用されるネットワークの基本構成を示すものである。発信元ノード１０から着信先ノード２０へＭ本のパスが設定され、各パスはいくつかのリンクと中継ノード（図示省略）を介して張られている。図３の発信元ノード１０に通信経路決定装置が設定される。
【００４２】
図５は、本発明の第５の実施形態を示す通信経路決定装置の内部構成図である。
この通信経路決定装置３０は、ユーザから到着したパケットを受けるパス設定部３１と、パケットヘッダ解析部３２と、パスｉへパケットを送信する経路制御部３３と、転送レートを測定する転送レート測定部３４と、同時接続ユーザフロー数を測定するユーザフロー数測定部３５と、１ユーザ使用帯域を算出する使用帯域算出部３６と、パス品質を判定する品質判定部３７と、変更経路を決定する経路決定部３８とから構成される。
通信経路決定装置３０は、第２の実施形態の方法で品質劣化パスおよび品質維持パスを判定し、品質劣化パスの経路変更先を決定する。
【００４３】
以下、図５により、動作説明を行う。ユーザから到着したパケットは、パス設定部３１でパケットヘッダにユーザの転送すべきパスを示すパスラベルをパケットヘッダに書き込むか、新たにヘッダに追加する。パケットへッダ解析部３２によりパケットサイズ、ＴＣＰフラグ情報を読み取られた後、経路制御部３３に送信される。経路制御部３３は、そのパケットのパスラベルから転送すべき経路を読み出し、その経路へ転送する。
【００４４】
パケットヘッダ解析部３２により読み取られたパケットサイズは、転送レート測定部３４に通知される。転送レート測定部３４は、一定周期τの間に通過したパケットのサイズの和をパス毎に計算し、その値をτで割ることにより、パスｉへの転送レートＤｉならびにその平均レートであるａｖｇＤｉを、ａｖｇＤｉ←（１−γ）ａｖｇＤｉ＋γＤｉにより更新し、Ｄｉを１ユーザ使用帯域算出部３６に通知する。
【００４５】
一方、ＴＣＰフラグ情報は、同時接続ユーザフロー数測定部３５に通知され、パスｉにおいてＴＣＰフローの開始を示すＳＹＮフラグビットが立っているパケットを検出したならば、新しいフロー発生と判断し、同時接続フロー数カウンタを１増加する。また、ＴＣＰフロー終了を表すＦＩＮフラグビットが立っているパケットを検出したならば、同時接続フロー数カウンタを１減少する。τ時間毎に、このカウンタ値の平均値Ｎｉを算出し、１ユーザ使用帯域算出部３６に通知する。
【００４６】
１ユーザ使用帯域算出部３６は、パスｉにおける１ユーザ当りの使用帯域ＵｉをＵｉ←（１−α）Ｕｉ＋αＤｉ／Ｎｉにより更新し、かつＵａｖｅ＝ΣＵｉ／ｎを計算し、ＵｉおよびＵａｖｅをパス品質判定部３７に通知する。
【００４７】
パス品質判定部３７は、Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めたパラメータβ，δ１を用いてｍｉｎ｛Ｕｉ／Ｃｉ｝＜β、かつ（ｍａｘ｛Ｕｉ｝−ｍｉｎ｛Ｕｉ｝）／ｍａｘ｛Ｕｉ｝＞δ１ならば、品質劣化パスが存在すると判定する。ε１，ε２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅを満たすパスを品質劣化パスｋとし、Ｕｋの値でその経路を昇順に並び替え、そのときのｊ番目の経路を品質劣化経路ｋｊ（ｋｊ＝ｋ１〜ｋＫ）とする。また、Ｕｍ＞（１＋ε２）×Ｕａｖｅを満たす経路を、品質維持パスｍとし、変更経路決定部３８に通知する。
【００４８】
変更経路決定部３８は、品質劣化パスｋｊに対して、｛Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）｝＞（１−ε１）×Ｕａｖｅ（Ｃｍはパスｍのボトルネックリンク容量）を満たす品質維持パスｍを検索し、見つかったならば品質劣化パスｋｊの経路を品質維持パスｍと同じ経路に変更するよう、見つからなければ、発信元ノード１０と着信先ノード２０の間に現在トラヒックが流れていない予備の経路に変更するよう、パス設定部３１に通知する。
【００４９】
その後、一時的にＵｍの値を、Ｕｍ←Ｕｍ−（ａｖｇＤｋｊ／ａｖｇＤｍ）×（Ｃｍ−Ｕｍ）に更新し、ａｖｇＤｍ←ａｖｇＤｍ＋ａｖｇＤｋｊに更新する。以上の操作をｊ＝１〜Ｋに対して行い、その後、Ｕｍ，ａｖｇＤｍの値が一時的に更新されたパスに関しては、それらの値を元に戻す。
パス設定部３１は、変更経路決定部３８からの指示に従い、パスの経路を変更し、その経路を通るようにラベルを変更する。
【００５０】
なお、図５および段落〔００４３〕〜〔００４９〕で説明した通信経路決定装置の動作手順を、プログラムに変換した後、そのプログラムをＣＤ−ＲＯＭ等の記録媒体に格納しておけば、プログラムの売買時に便利であり、また、通信ネットワーク内の任意のノードに記録媒体を装着しておくことで、プログラムをインストールして実行させることにより、本発明を容易に実現することができる。
【００５１】
【発明の効果】
以上説明したように、本発明によれば、送信元ノードのみで測定可能な同時接続ユーザフロー数と使用帯域という値のみから各経路上のユーザパス通信品質を均等に維持できるような通信経路を決定することができる。また、新たなパスを張りたい場合にも、対応して通信経路を決定することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態を示すネットワークの構成図である。
【図２】１ユーザ使用帯域とトラヒック量の関係、およびトラヒックの一部が別の経路へ移動して減少した後の１ユーザ使用帯域の予測値を示すグラフである。
【図３】本発明の第２〜４の実施形態に適用されるネットワークの構成図である。
【図４】１ユーザ使用帯域とトラヒック量の関係、およびトラヒックの一部が別の経路から移動して増えた後の１ユーザ使用帯域の予測値を示すグラフである。
【図５】本発明の第５の実施形態を示す通信経路決定装置の内部構成図である。
【符号の説明】
１０…発信元ノード、２０…着信先ノード、３０…通信経路決定装置、
３１…パス設定部、３２…パケットヘッダ解析部、３３…経路制御部、
３４…転送レート測定部、３５…同時接続ユーザフロー数測定部、
３６…１ユーザ使用帯域算出部、３７…パス品質判定部、
３８…変更経路決定部。
【図１】
2004215006.tif 000003
【図２】
2004215006.tif 000004
【図３】
2004215006.tif 000005
【図４】
2004215006.tif 000006
【図５】
2004215006.tif 000007