(57)【要約】【課題】測定が簡単な同時接続ユーザフロー数と使用帯域、経路上のボトルネックリンク使用率の値のみから各経路上のユーザ通信品質を均等に維持できるようにする。【解決手段】発信元ノード１１の場所に複数経路負荷分散装置を設置する。経路Ｉ上のリンクｊの使用帯域を測定し、経路ｉのボトルネックリンク使用率を算出し、リンク容量をＣｉとし、発信元ノード１１から経路ｉに送信される転送レートおよび平均同時接続ユーザフロー数を一定周期Ｔ毎に測定し、１ユーザ当りの使用帯域を算出し、品質劣化経路ｋｊから品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝（δは予め定めた係数）分のトラヒックに相当するユーザフローを経路ｋｊからｍｊに変更し、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行う。【選択図】　　　　図２
2004056737.tif 000002
【特許請求の範囲】
【請求項１】
通信網における発信元ノードと着信先ノードの間に経路がｎ本存在し、該発信元ノードから該着信先ノードに向かうユーザフローはｎ本の経路中の１本を介して転送され、該発信元ノードは各経路の通信状態を予め定めた周期毎に観測し、観測した状態に応じて該ユーザフローの通信経路を変更する複数経路負荷分散方法であって、
該発信元ノードに設置された複数経路負荷装置は、任意の経路ｉ上にあるリンクｊの使用帯域Ｂ（ｉ，ｊ）を測定し、
該経路のボトルネックリンク使用率をρｉ＝ｍａｘｊ（Ｂ（ｉ，ｊ）／Ｃ（ｉ，ｊ））（Ｃ（ｉ，ｊ）はリンクｊの容量）により算出し、またボトルネックとなるリンクの容量をＣｉとし、
該発信元ノードから経路ｉに送信される転送レートＤｉおよび平均同時接続ユーザフロー数Ｎｉを予め定めた周期Ｔ毎に測定し、
該経路ｉの１ユーザ当りの使用帯域をＵｉ＝Ｄｉ／Ｎｉにより算出し、
Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めた閾値ε１，ε２，ρｔｈ１，ρｔｈ２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅ　かつρｋ＞ρｔｈ１を満たす経路を品質劣化経路と仮定し、
Ｕｋの値で該経路を昇順に並び替え、並び替えた後におけるｊ番目の該経路を品質劣化経路ｋｊとし、
Ｕｍ＞（１＋ε２）×Ｕａｖｅ　かつ、ρｍ＜ρｔｈ２を満たす経路を品質維持経路と仮定し、
Ｕｍの値で該経路を降順に並び替え、並び替えた後におけるｊ番目の該経路を品質維持経路ｍｊとし、
該品質劣化経路ｋｊから該品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝（δは予め定めた係数）分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、
この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）（Ｋは品質劣化経路の本数、Ｍは品質維持経路の本数）に対して行うことを特徴とする複数経路負荷分散方法。
【請求項２】
請求項１記載の複数経路負荷分散方法において、
前記品質劣化経路ｋｊから品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、
品質劣化経路ｋｊから品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，ｄ｝（ｄは予め定めたトラヒック量）分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする複数経路負荷分散方法。
【請求項３】
請求項１記載の複数経路負荷分散方法において、
前記ρｉ，Ｎｉ，Ｄｉの測定を予め定めた周期Ｔ毎に行うが、同時に、該Ｔよりも短い測定周期τ（＝Ｔ／Ｍ’、Ｍ’は任意の整数）で区間（（ｎ−１）τ，ｎτ）におけるρｉ（ｎ），Ｎｉ（ｎ），Ｄｉ（ｎ）（ｎ＝１〜Ｍ’）の測定を行い、
Ｕｉ（ｎ）＝Ｄｉ（ｎ）／Ｎｉ（ｎ）として、（ρｉ（ｎ），Ｕｉ（ｎ））を用いてρ＝Ｆｉ（Ｕ）の関係を表す関数Ｆｉ（　）を推定し、
前記品質劣化経路ｋｊから品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、
該品質劣化経路ｋｊから該品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，Ｐｋｊ−Ｆｋｊ（Ｕａｖｅ）×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、
この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする複数経路負荷分散方法。
【請求項４】
請求項１記載の複数経路負荷分散方法において、
前記ρｉ，Ｎｉ，Ｄｉの測定を予め定めた周期Ｔ毎に行い、
Ｎａｖｅ＝ΣＮｉ／ｎおよび予め定めた閾値ε１，ε２，ρｔｈ１，ρｔｈ２を用いて、Ｎｋ＞（１＋ε１）×Ｎａｖｅ　かつρｋ＞ρｔｈ１を満たす経路を品質劣化経路とし、
Ｎｋの値で該経路を降順に並び替え、並び替えた後のｊ番目の該経路を品質劣化経路ｋｊとし、
また、Ｎｍ＜（１−ε２）×Ｎａｖｅ　かつρｍ＜ρｔｈ２を満たす経路を品質維持経路とし、
Ｎｍの値で該経路を昇順に並び替え、並び替えた後のｊ番目の該経路を品質維持経路ｍｊとし、
該品質劣化経路ｋｊから該品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｎｋｊ−Ｎａｖｅ）／Ｎｋｊ×Ｐｋｊ×Ｃｋｊ×δ｝（δは予め定めた係数）分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、
この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする複数経路負荷分散方法。
【請求項５】
請求項１記載の複数経路負荷分散方法において、
前記品質劣化経路ｋｊから品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、
品質劣化経路ｋｊから品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×Ｄｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、
この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする複数経路負荷分散方法。
【請求項６】
請求項３記載の複数経路負荷分散方法において、
前記品質劣化経路ｋｊから品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，Ｐｋｊ−Ｆｋｊ（Ｕａｖｅ）×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、
ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｎｋｊ−Ｎａｖｅ）／Ｎｋｊ×Ｄｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする複数経路負荷分散方法。
【請求項７】
請求項１から請求項６のいずれかに記載の複数経路負荷分散方法において、
前記品質劣化経路ｋｊから品質維持経路ｍｊへユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行う代わりに、
Ｋ＞Ｍの場合には、ｊ＝Ｋ＋１〜Ｍの品質劣化経路ｋｊに対しても、品質維持経路の中でρｎｅｗｍｉ＝｛（ρｔｈ２−ρｍｉ）×Ｃｍｉ＋ｄｉ｝／Ｃｍｉ＜ρｔｈ２（ｄｉはｉ＝１〜Ｍの品質劣化経路ｋｉから既に経路変更されたトラヒック量）を満たす品質維持経路ｍｉを探索し、もしあれば、該経路ｍｉに対して品質劣化経路から経路変更を請求項１から請求項６のいずれかの方法で行い、かつρｍｉの代わりにρｎｅｗｍｉを用いることを特徴とする複数経路負荷分散方法。
【請求項８】
請求項１から請求項６のいずれかに記載の複数経路負荷分散方法において、
前記平均同時接続ユーザフロー数Ｎｉを直接測定する代わりに、
ユーザフローのトランスポートプロトコルがＴＣＰであり、該ＴＣＰパケットヘッダ中のＴＣＰセッションの開始と終了を表すフラグであるＳＹＮフラグおよびＦＩＮフラグが立っているパケットをカウントすることにより、予め定めた周期Ｔの平均同時接続ＴＣＰフロー数を測定して、測定値をＮｉとして用い、請求項１から請求項６のいずれかの方法で経路変更を行うことを特徴とする複数経路負荷分散方法。
【請求項９】
請求項１から請求項６のいずれかに記載の複数経路負荷分散方法において、
前記平均同時接続ユーザフロー数Ｎｉを直接測定する代わりに、
各ユーザフローに対して保証レートＧを予め設定し、網の発信元ノードにおいてあるユーザからのパケットを受信したならば、該パケットの現在の送信レートと保証レートを比較して保証レートを超えているときは、該パケットにタギングし、
予め定めた周期Ｔよりも短い測定周期τ（＝Ｔ／Ｍ’、Ｍ’は整数）で区間［（ｎ−１）τ，ｎτ］において、タギングされていないパケットの経路ｉへの到着レート（Ａｉ（ｎ））を測定し、経路ｉの平均同時接続ユーザフロー数（Ｆｉ（ｎ）を、Ｆｉ（ｎ＋１）＝（１−ａ）＊Ｆｉ（ｎ）＋ａ＊Ａｉ（ｎ）／Ｇ（ａは平滑化パラメータ）により推定し、Ｎｉ＝Ｆｉ（Ｍ’）として用い、請求項１から請求項６のいずれかの方法で経路変更を行うことを特徴とする複数経路負荷分散方法。
【請求項１０】
請求項１，８または９のいずれかの方法で、ρｉ，Ｎｉ，Ｄｉの測定を予め定めた周期Ｔ毎に行う手段と、
請求項１から請求項７のいずれかに記載の方法で、品質劣化経路から品質維持経路へユーザフローの経路を変更する手段とを具備することを特徴とする複数経路負荷分散装置。
【請求項１１】
中継ノードを経由した発信元ノードと着信先ノードの間に経路が複数本存在する場合、該発信元ノードに設けられた複数経路負荷分散装置であって、
ユーザから到着したパケットに転送すべき経路の情報を書き込むか新たにヘッダを追加する経路設定部と、
パケットサイズ、ＴＣＰフラグ情報の読み取りなどを行うパケットヘッダ解析部と、
該パケットのヘッダ情報から転送すべき経路を読み出し、該経路に該パケットを転送する経路制御部と、
予め定めた周期に通過したパケットのサイズの和を経路毎、かつユーザフロー毎に計算し、計算値を該周期で割り算することで経路への転送レートとユーザフローの転送レートを算出する転送レート測定部と、
ＴＣＰフロー開始を検出して、同時接続フロー数カウンタを１増加し、ＴＣＰフロー終了を検出して、該カウンタを１減少し、該周期毎に該カウンタ値の平均値を算出する同時接続ユーザフロー数測定部と、
ある経路への転送レートを該経路での同時接続フロー数で割り算することで１ユーザ当りの使用帯域を算出する１ユーザ使用帯域算出部と、
該周期毎に、リンクの使用帯域の測定を中継リンクに指示し、その結果を受信し、該経路のボトルネックリンク使用率を算出し、経路品質判定部に通知するリンク使用率管理部と、
品質劣化経路を昇順に並び替え、品質劣化経路ｋｊを決定し、品質維持経路を降順に並び替え、品質維持経路ｍｊを決定し、該経路を経路変更トラヒック量算出部に通知する経路品質判定部と、
品質劣化経路ｋｊから品質維持経路ｍｊへ移動すべきトラヒック量を算出して、経路変更指示部に通知する経路変更トラヒック量算出部と、
前記転送レート測定部からユーザフロー毎の転送レートを受信し、品質劣化経路ｋｊに属するユーザフローの転送レートを昇順に並び替え、経路ｋｊから経路ｍｊへ変更するように経路設定部に指示する経路変更指示部と、
該経路変更指示部からの指示に従って、経路の設定テーブルを変更する経路設定部とを具備することを特徴とする複数経路負荷分散装置。
【請求項１２】
発信元ノードに設けられた複数経路負荷分散装置に各経路上のユーザ通信品質を均等に維持させるためのプログラムであって、
上記複数経路負荷分散装置を、請求項１，８または９のいずれかの方法で、ρｉ，Ｎｉ，Ｄｉの測定を予め定めた周期Ｔ毎に行う手段、ならびに、
請求項１から請求項７のいずれかに記載の方法で、品質劣化経路から品質維持経路へユーザフローの経路を変更する手段としてそれぞれ機能させるための通信品質均等維持用プログラム。
【請求項１３】
中継ノードを経由した発信元ノードと着信先ノードの間に経路が複数本存在する場合、該発信元ノードに設けられた複数経路負荷分散装置に各経路上のユーザ通信品質を均等に維持させるためのプログラムであって、
上記複数経路負荷分散装置を、ユーザから到着したパケットに転送すべき経路の情報を書き込むか新たにヘッダを追加する経路設定部、
パケットサイズ、ＴＣＰフラグ情報の読み取りなどを行うパケットヘッダ解析部、
該パケットのヘッダ情報から転送すべき経路を読み出し、該経路に該パケットを転送する経路制御部、
予め定めた周期に通過したパケットのサイズの和を経路毎、かつユーザフロー毎に計算し、計算値を該周期で割り算することで経路への転送レートとユーザフローの転送レートを算出する転送レート測定部、
ＴＣＰフロー開始を検出して、同時接続フロー数カウンタを１増加し、ＴＣＰフロー終了を検出して、該カウンタを１減少し、該周期毎に該カウンタ値の平均値を算出する同時接続ユーザフロー数測定部、
ある経路への転送レートを該経路での同時接続フロー数で割り算することで１ユーザ当りの使用帯域を算出する１ユーザ使用帯域算出部、
該周期毎に、リンクの使用帯域の測定を中継リンクに指示し、その結果を受信し、該経路のボトルネックリンク使用率を算出し、経路品質判定部に通知するリンク使用率管理部、
品質劣化経路を昇順に並び替え、品質劣化経路ｋｊを決定し、品質維持経路を降順に並び替え、品質維持経路ｍｊを決定し、該経路を経路変更トラヒック量算出部に通知する経路品質判定部、
品質劣化経路ｋｊから品質維持経路ｍｊへ移動すべきトラヒック量を算出して、経路変更指示部に通知する経路変更トラヒック量算出部、
前記転送レート測定部からユーザフロー毎の転送レートを受信し、品質劣化経路ｋｊに属するユーザフローの転送レートを昇順に並び替え、経路ｋｊから経路ｍｊへ変更するように経路設定部に指示する経路変更指示部、
該経路変更指示部からの指示に従って、経路の設定テーブルを変更する経路設定部としてそれぞれ機能させるための通信品質均等維持用プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＩＰネットワーク上の複数経路への負荷分散方法、負荷分散装置および負荷分散用プログラムに関し、特に、中継ノードを経由した発信元ノードと着信先ノードの間に経路が複数本存在する場合、該発信元ノードに設けられた複数経路負荷分散装置と、それを用いる複数経路負荷分散方法、ならびに各経路上のユーザ通信品質を均等に維持させるためのプログラムに関する。
【０００２】
【従来の技術】
ＩＰネットワークが広く利用されてくるに伴って、ＩＰネットワーク上での通信品質保証に対する要求が高まっている。そのような要求に応えて、あるリンクに負荷が集中するような場合、そのリンクにパケットを通すことにより品質が劣化することを回避するために、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ　Ｌａｂｅｌ　Ｓｗｉｔｃｈｉｎｇ）のような経路を明示的に指定できる技術を用いて、負荷分散を図る方法が提案されている。
【０００３】
上記従来の負荷分散方法は、主にリンク使用率のみをパラメータとして用いており、各経路のリンク使用率が同じになるように負荷分散を行っている。
しかし、リンク使用率とユーザの体感するファイル転送時間やスループット等の品質との関連が不明であるため、例えば、ある２つの経路のリンク使用率が同じであったとしても、同時接続ユーザ数等の条件によって、ある一方の経路におけるユーザ通信品質は劣化している可能性がある。
【０００４】
一方、リンクを通過するフローのファイル転送時間やスループットを直接測定して、その値を参照することで負荷分散を行う方法も考えられるが、この方法では、ファイル転送時間やスループットのようなユーザ品質を、当該リンク上を通過する全てのパケットをキャプチャしてフローを組み上げて算出するか、あるいは、当該リンクの前段か後段もしくはその両方に試験パケット送受信機を設置して、試験パケットを送信することにより、品質測定を行う必要があるため、一般的には、これは実装が困難である。
【０００５】
【発明が解決しようとする課題】
このように、従来の負荷分散方法では、リンク使用率のみをパラメータとして用いているが、体感するファイル転送時間やスループット等の品質との関連が明らかでないため、リンク使用率が同じであっても、一方の経路におけるユーザ通信品質が他方よりも劣化している可能性がある、という問題があった。
また、フローのファイル転送時間やスループットを直接測定し、その測定値により負荷分散を行う方法では、全てのパケットをキャプチャしてフローを組み上げ算出するか、あるいは、試験パケット送受信機を設置して、品質測定を行う必要があるため、実装が困難である、という問題があった。
【０００６】
そこで、本発明の目的は、これら従来の課題を解決し、測定が簡単な同時接続ユーザフロー数と使用帯域、経路上のボトルネットクンク使用率、の値のみから各経路上のユーザ通信品質を均等に維持できるような複数経路負荷分散方法および装置、ならびにそのプログラムを提供することにある。
【０００７】
【課題を解決するための手段】
上記目的を達成するため、本発明の複数経路負荷分散方法は、（１）通信網における発信元ノードと着信先ノードの間に経路がｎ本存在し、該発信元ノードから該着信先ノードに向かうユーザフローはｎ本の経路中の１本を介して転送され、該発信元ノードは各経路の通信状態を予め定めた周期毎に観測し、観測した状態に応じて該ユーザフローの通信経路を変更する複数経路負荷分散方法であって、
該発信元ノードに設置された複数経路負荷装置は、任意の経路ｉ上にあるリンクｊの使用帯域Ｂ（ｉ，ｊ）を測定し、該経路のボトルネックリンク使用率をρｉ＝ｍａｘ（Ｂ（ｉ，ｊ）／Ｃ（ｉ，ｊ））（Ｃ（ｉ，ｊ）はリンクｊの容量）により算出し、またボトルネックとなるリンクの容量をＣｉとし、該発信元ノードから経路ｉに送信される転送レートＤｉおよび平均同時接続ユーザフロー数Ｎｉを予め定めた周期Ｔ毎に測定し、該経路ｉの１ユーザ当りの使用帯域をＵｉ＝Ｄｉ／Ｎｉにより算出し、Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めた閾値ε１，ε２，ρｔｈ１，ρｔｈ２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅかつρｋ＞ρｔｈ１を満たす経路を品質劣化経路と仮定し、Ｕｋの値で該経路を昇順に並び替え、並び替えた後におけるｊ番目の該経路を品質劣化経路ｋｊとし、Ｕｍ＞（１＋ε２）×Ｕａｖｅかつ、ρｍ＜ρｔｈ２を満たす経路を品質維持経路と仮定し、Ｕｍの値で該経路を降順に並び替え、並び替えた後におけるｊ番目の該経路を品質維持経路ｍｊとし、該品質劣化経路ｋｊから該品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝（δは予め定めた係数）分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）（Ｋは品質劣化経路の本数、Ｍは品質維持経路の本数）に対して行うことを特徴としている。
（２）また、前記品質劣化経路ｋｊから品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、品質劣化経路ｋｊから品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，ｄ｝（ｄは予め定めたトラヒック量）分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことも特徴としている。
（３）また、前記ρｉ，Ｎｉ，Ｄｉの測定を予め定めた周期Ｔ毎に行うが、同時に、該Ｔよりも短い測定周期τ（＝Ｔ／Ｍ’、Ｍ’は任意の整数）で区間（（ｎ−１）τ，ｎτ）におけるρｉ（ｎ），Ｎｉ（ｎ），Ｄｉ（ｎ）（ｎ＝１〜Ｍ’）の測定を行い、Ｕｉ（ｎ）＝Ｄｉ（ｎ）／Ｎｉ（ｎ）として、（ρｉ（ｎ），Ｕｉ（ｎ））を用いてρ＝Ｆｉ（Ｕ）の関係を表す関数Ｆｉ（　）を推定し、前記品質劣化経路ｋｊから品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、該品質劣化経路ｋｊから該品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，Ｐｋｊ−Ｆｋｊ（Ｕａｖｅ）×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことも特徴としている。
（４）また、前記ρｉ，Ｎｉ，Ｄｉの測定を予め定めた周期Ｔ毎に行い、Ｎａｖｅ＝ΣＮｉ／ｎおよび予め定めた閾値ε１，ε２，ρｔｈ１，ρｔｈ２を用いて、Ｎｋ＞（１＋ε１）×Ｎａｖｅ　かつρｋ＞ρｔｈ１を満たす経路を品質劣化経路とし、Ｎｋの値で該経路を降順に並び替え、並び替えた後のｊ番目の該経路を品質劣化経路ｋｊとし、また、Ｎｍ＜（１−ε２）×Ｎａｖｅ　かつρｍ＜ρｔｈ２を満たす経路を品質維持経路とし、Ｎｍの値で該経路を昇順に並び替え、並び替えた後のｊ番目の該経路を品質維持経路ｍｊとし、該品質劣化経路ｋｊから該品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｎｋｊ−Ｎａｖｅ）／Ｎｋｊ×Ｐｋｊ×Ｃｋｊ×δ｝（δは予め定めた係数）分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことも特徴としている。
（５）また、前記品質劣化経路ｋｊから品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、品質劣化経路ｋｊから品質維持経路ｍｊへｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×Ｄｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことも特徴としている。
（６）また、前記品質劣化経路ｋｊから品質維持経路ｍｊへ、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，Ｐｋｊ−Ｆｋｊ（Ｕａｖｅ）×Ｃｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｎｋｊ−Ｎａｖｅ）／Ｎｋｊ×Ｄｋｊ×δ｝分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことも特徴としている。
（７）また、前記品質劣化経路ｋｊから品質維持経路ｍｊへユーザフローを経路ｋｊからｍｊへ変更し、この処理をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行う代わりに、Ｋ＞Ｍの場合には、ｊ＝Ｋ＋１〜Ｍの品質劣化経路ｋｊに対しても、品質維持経路の中でρｎｅｗｍｉ＝｛（ρｔｈ２−ρｍｉ）×Ｃｍｉ＋ｄｉ｝／Ｃｍｉ＜ρｔｈ２（ｄｉはｉ＝１〜Ｍの品質劣化経路ｋｉから既に経路変更されたトラヒック量）を満たす品質維持経路ｍｉを探索し、もしあれば、該経路ｍｉに対して品質劣化経路から経路変更を上記（１）から（６）のいずれかの方法で行い、かつρｍｉの代わりにρｎｅｗｍｉを用いることも特徴としている。
（８）また、前記平均同時接続ユーザフロー数Ｎｉを直接測定する代わりに、ユーザフローのトランスポートプロトコルがＴＣＰであり、該ＴＣＰパケットヘッダ中のＴＣＰセッションの開始と終了を表すフラグであるＳＹＮフラグおよびＦＩＮフラグが立っているパケットをカウントすることにより、予め定めた周期Ｔの平均同時接続ＴＣＰフロー数を測定して、測定値をＮｉとして用い、上記（１）から（６）のいずれかの方法で経路変更を行うことも特徴としている。
（９）また、前記平均同時接続ユーザフロー数Ｎｉを直接測定する代わりに、各ユーザフローに対して保証レートＧを予め設定し、網の発信元ノードにおいてあるユーザからのパケットを受信したならば、該パケットの現在の送信レートと保証レートを比較して保証レートを超えているときは、該パケットにタギングし、予め定めた周期Ｔよりも短い測定周期τ（＝Ｔ／Ｍ’、Ｍ’は整数）で区間［（ｎ−１）τ，ｎτ］において、タギングされていないパケットの経路ｉへの到着レート（Ａｉ（ｎ））を測定し、経路ｉの平均同時接続ユーザフロー数（Ｆｉ（ｎ）を、Ｆｉ（ｎ＋１）＝（１−ａ）＊Ｆｉ（ｎ）＋ａ＊Ａｉ（ｎ）／Ｇ（ａは平滑化パラメータ）により推定し、Ｎｉ＝Ｆｉ（Ｍ’）として用い、上記（１）から（６）のいずれかの方法で経路変更を行うことも特徴としている。
（１０）本発明の複数経路負荷分散装置は、上記（１），（８）または（９）のいずれかの方法で、ρｉ，Ｎｉ，Ｄｉの測定を予め定めた周期Ｔ毎に行う手段と、（１）から（７）のいずれかに記載の方法で、品質劣化経路から品質維持経路へユーザフローの経路を変更する手段とを具備することを特徴としている。
【０００８】
【発明の実施の形態】
以下、本発明の原理および実施形態を、図面により詳細に説明する。
（原理）
図１は、本発明における１ユーザ使用帯域とリンク使用率の関係を示す特性曲線図である。
いま、ある経路における平均同時接続ユーザ数をＮ、そのリンクの平均使用帯域をＤ、ダウンロードするファイルサイズの平均をＦ、平均ファイル転送時間をＴとする。上記各値を元に、待ち行列理論におけるリトルの公式から、下記関係式（１）が成立する。
Ｎ＝Ｄ／Ｆ×Ｔ　・・・・・・・・・・・・・・・・・・・・・（１）
すなわち、１ユーザ当りの使用帯域をＵ（＝Ｄ／Ｎ）と置くと、
Ｕ＝Ｆ／Ｔ　・・・・・・・・・・・・・・・・・・・・・・・（２）
これは、ファイル転送速度に相当する。
１ユーザ当りの使用帯域とファイル転送速度から、上記（１）式が導出される。
【０００９】
従って、経路ａにおけるＵａと経路ｂにおけるＵｂが等しくなれば、つまり平均ファイルサイズが同じであれば、平均ファイル転送時間も等しくできることになる。そこで、本発明においては、Ｕをユーザ通信品質を表すパラメータとして用い、各経路上のＵが等しくなるように負荷分散を行っている。
ここで、品質劣化経路ｋｊから品質維持経路ｍｊへ移動するトラヒック量を、
ｄｊ＝（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ・・・・・・・・・・・・・・・・・・（３）
を用いて算出している根拠について説明する。
【００１０】
縦軸に１ユーザ使用帯域Ｕ（＝Ｄ／Ｎ）をとり、横軸に使用率ρをとると、図１の実線で示すような曲線となる。
一般に、Ｕはリンク使用率ρに対して単調減少し、また、ρが０に近づいたときにＵはリンク容量Ｃｋｊを超えることはない。
そこで、Ｕとρの関係を図１の点線で示すように線形近似し、経路変更後にＵ＝Ｕａｖｅとなるような使用率ρｎｅｗを算出し、現在の使用率ρｋｊとρｎｅｗの差が（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊと計算され、それにリンク容量Ｃｋｊを掛けることによりｄｊを算出している。
【００１１】
（第１の実施形態）
本発明の第１の実施形態である複数経路負荷分散方法（請求項１）においては、発信元ノードは経路ｉ（ｉ＝１，・・・，ｎ）上にあるリンクｊの使用帯域Ｂ（ｉ，ｊ）〔ｂｐｓ〕を測定し、経路ｉのボトルネックリンク使用率をρｉ＝ｍａｘｊ（Ｂ（ｉ，ｊ）／Ｃ（ｉ，ｊ））（なお、Ｃ（ｉ，ｊ）は、経路ｉかつリンクｊのリンク容量〔ｂｐｓ〕）により算出し、また、ボトルネックとなるリンク容量をＣｉとし、該ノードから経路ｉへ送信される転送レートＤｉ〔ｂｐｓ〕および平均同時接続ユーザフロー数Ｎｉを一定周Ｔ毎に測定し、経路ｉにおける１ユーザ当りの使用帯域Ｕｉ＝Ｄｉ／Ｎｉにより算出し、Ｕａｖｅ＝ΣＵｉ／ｎおよび予め定めた閾値ε１，ε２，ρｔｈ１，ρｔｈ２を用いて、下式（３），（４）を満たす経路を品質劣化経路とする。
Ｕｋ＜（１−ε１）×Ｕａｖｅ　　　　・・・・・・・・・・・・・・・・（３）
ρｋ＞ρｔｈ１　　　　・・・・・・・・・・・・・・・・・・・・（４）
【００１２】
次に、Ｕｋの値で該経路を昇順に並び替え、そのときのｊ番目の該経路を品質劣化経路ｋｊ（ｋｊ＝ｋ１〜ｋｋ）とする。また、下式（５），（６）を満たす経路を品質維持経路とする。
Ｕｍ＞（１＋ε２）×Ｕａｖｅ　　　　　・・・・・・・・・・・・・・・（５）
ρｍ＜ρｔｈ２　　　　　　・・・・・・・・・・・・・・・・・・（６）
そして、Ｕｍの値で該経路を降順に並び替え、そのときのｊ番目の経路を品質維持経路ｍｊ（ｍｊ＝ｍ１〜ｍＭ）とする。
【００１３】
品質劣化経路ｋｊから品質維持経路ｍｊへ、下式（７）の分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する。
ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝　　　　　・・・・・・・・・・・・・・・・・・・（７）
なお、δは予め定めた係数である。
これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする。なお、Ｋは品質劣化経路の本数、Ｍは品質維持経路の本数である。
【００１４】
ここで、品質劣化経路ｋｊから品質維持経路ｍｊへ移動するトラヒック量を前記（３）式を用いて算出している根拠について説明する。
一般に、Ｕはリンク使用率ρに対して単調減少し（図１参照）、また、ρが０に近づいたときにＵはリンク容量Ｃｋｊを超えることはない（Ｕ＝＜Ｆ／Ｔ）。
そこで、Ｕとρの関係を図１のように線形近似し、経路変更後にＵ＝Ｕａｖｅとなるような使用率ρｎｅｗを算出し、現在の使用率ρｋｊと経路変更後使用率ρｎｅｗの差が（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊと計算され、それにリンク容量Ｃｋｊを掛けることにより、ｄｊを算出している。
【００１５】
（第２の実施形態）
本発明の第２の実施形態である複数経路負荷分散方法（請求項２）においては、第１の実施形態のように品質劣化経路ｋｊから品質維持経路ｍｊへ前記（７）式で示すトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、下記（８）式の分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する。
すなわち、品質劣化経路ｋｊから品質維持経路ｍｊへ、
ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，ｄ｝　・・・・・・・（８）
上式（８）で示す分のトラヒックに相当するユーザフローを経路ｋｊからｍｊに変更する。
なお、ｄは、予め定めたトラヒック量〔ｂｐｓ〕である。
そして、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする。
【００１６】
（第３の実施形態）
本発明の第３の実施形態である複数経路負荷分散方法（請求項３）においては、第１の実施形態と同様に、ρｉ，Ｎｉ，Ｄｉの測定を一定周期Ｔ毎に行い、同時にＴよりも短い測定周期τ（＝Ｔ／Ｍ’なお、Ｍ’は整数である）で区間［（ｎ−１）τ，ｎτ］における下記（９）式の測定を行う。
ρｉ（ｎ），Ｎｉ（ｎ），Ｄｉ（ｎ）　・・・・・・・・・・・・・（９）
なお、ｎ＝１〜Ｍ’である。
そして、Ｕｉ（ｎ）＝Ｄｉ（ｎ）／Ｎｉ（ｎ）として、（ρｉ（ｎ），Ｕｉ（ｎ））を用いて、ρ＝Ｆｉ（Ｕ）の関係を表す関数Ｆｉ（　）を推定する。
【００１７】
そして、第１の実施形態のように、品質劣化経路ｋｊから品質維持経路ｍｊへ前記（７）式に示す分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、下式（１０）に示す分のトラヒックに相当するユーザフローを経路ｋｊからｍｊに変更する。
ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，Ｐｋｊ−Ｆｋｊ（Ｕａｖｅ）×Ｃｋｊ×δ｝　　　　　　　　　　　　　・・・・・・・・・・・・・・・・・・・（１０）
そして、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする。
【００１８】
（第４の実施形態）
本発明の第４の実施形態である複数経路負荷分散方法（請求項４）においては、第１の実施形態と同様に、ρｉ、Ｎｉ、Ｄｉの測定を一定周期毎に行い、
Ｎａｖｅ＝ΣＮｉ／ｎおよび予め定めた閾値ε１，ε２，ρｔｈ１，ρｔｈ２を用いて、下式（１１）を満たす経路を品質劣化経路とする。
Ｎｋ＞（１＋ε１）×Ｎａｖｅ　かつ、
ρｋ＞ρｔｈ２　　・・・・・・・・・・・・・・・・・・・・・・（１１）
次に、Ｎｋの値で該経路を降順に並び替え、そのときのｊ番目の該経路を品質劣化経路ｋｊ（ｋｊ＝ｋ１〜ｋｋ）とする。
【００１９】
また、下記（１２）式を満たす経路を品質維持経路とする。
Ｎｍ＜（１−ε２）×Ｎａｖｅ　かつ、
ρｍ＜ρｔｈ２　・・・・・・・・・・・・・・・・・・・・・・・（１２）
次に、Ｎｍの値で該経路を昇順に並び替え、そのときのｊ番目の経路を品質維持経路ｍｊ（ｍｊ＝ｍ１〜ｍＭ）とする。品質劣化経路ｋｊから品質維持経路ｍｊへ下記（１３）式に示す分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする。
ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｎｋｊ−Ｎａｖｅ）／Ｎｋｊ×Ｐｋｊ×Ｃｋｊ×δ｝　　　・・・・・・・・・・・・・・・・・・・・・・・・（１３）
（なお、δは予め定めた係数）
【００２０】
（第５の実施形態）
本発明の第５の実施形態である複数経路負荷分散方法（請求項５）においては、第１の実施形態と同様に、品質劣化経路ｋｊから品質維持経路ｍｊへ、上記（７）式に示す分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、品質劣化経路ｋｊから品質維持経路ｍｊへ下記（１４）式に示す分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする。
ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×Ｄｋｊ×δ｝　・・・・・・・・・・・・・・・・・・（１４）
【００２１】
（第６の実施形態）
本発明の第６の実施形態である複数経路負荷分散方法（請求項６）においては、第３の実施形態と同様に、品質劣化経路ｋｊから品質維持経路ｍｊへ、上記（１０）式に示す分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更する代わりに、品質劣化経路ｋｊから品質維持経路ｍｊへ下記（１５）式に示す分のトラヒックに相当するユーザフローを経路ｋｊからｍｊへ変更し、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行うことを特徴とする。
ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｎｋｊ−Ｎａｖｅ）／Ｎｋｊ×Ｄｋｊ×δ｝　　　　　　　　　　　　　・・・・・・・・・・・・・・・・・・・（１５）
【００２２】
（第７の実施形態）
本発明の第７の実施形態である複数経路負荷分散方法（請求項７）においては、第１から第６の実施形態と同様に、品質劣化経路ｋｊから品質維持経路ｍｊへ、ユーザフローを経路ｋｊからｍｊへ変更し、これをｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行う代わりに、Ｋ＞Ｍの場合には、ｊ＝Ｋ＋１〜Ｍの品質劣化経路ｋｊに対しても、品質維持経路の中で下記（１６）式を満たす品質維持経路ｍｊを探索し、もしあれば、その経路ｍｊに対して品質劣化経路から品質維持経路を第１から第４のいずれかの方法で行うことを特徴とする（ただし、そのときには、ρｍｊの代わりにρｎｅｗｍｉを用いる）。
ρｎｅｗｍｉ＝｛（ρｔｈ２−ρｍｉ）×Ｃｍｉ＋ｄｉ｝／Ｃｍｉ＜ρｔｈ２（なお、ｄｉはｉ＝１〜Ｍの品質劣化経路ｋｉから既に経路変更されたトラヒック量）・・・・・・・・・・・・・・・・・・・（１６）
【００２３】
（第８の実施形態）
本発明の第８の実施形態である複数経路負荷分散方法（請求項８）においては、第１から第６の実施形態と同様に、平均同時接続ユーザフロー数Ｎｉを直接測定する代わりに、ユーザフローのトランスポートプロトコルがＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ　Ｃｏｎｔｒｏｌ　Ｐｒｏｔｏｃｏｌ）であり、該ＴＣＰパケットヘッダ中のＴＣＰセッションの開始と終了を表すフラグであるＳＹＮフラグおよびｆｉｎフラグが立っているパケットをカウントすることにより、一定周期Ｔの平均同時接続ＴＣＰフロー数を測定して、それをＮｉとして用いて第１から第６のいずれかの方法で経路変更を行うことを特徴とする。
【００２４】
（第９の実施形態）
本発明の第９の実施形態である複数経路負荷分散方法（請求項９）においては、第１から第６の実施形態と同様に、平均同時接続ユーザフロー数Ｎｉを直接測定する代わりに、各ユーザフローに対して保証レートＧを予め設定し、網の発信元ノードにおいてユーザからのパケットを受信したならば、該パケットの現在の送信レートと保証レートを比較して保証レートを超えているときには、該パケットにタギングし、一定周期Ｔよりも短い測定周期τ（＝Ｔ／Ｍ’，Ｍ’は整数）で区間［（ｎ−１）τ，ｎτ］において、タギングされていないパケットの経路ｉへの到着レート（Ａｉ（ｎ）［ｂｐｓ］）を測定し、経路ｉの平均同時接続ユーザフロー数（Ｆｉ（ｎ））を下記（１７式）により推定し、Ｎｉ＝Ｆｉ（Ｍ’）として用いて第１から第６のいずれかの方法で経路変更を行うことを特徴とする。
Ｆｉ（ｎ＋１）＝（１−ａ）＊Ｆｉ（ｎ）＋ａ＊Ａｉ（ｎ）／Ｇ・・・・・・・・・・・・・・・・・・・・・（１７）
（なお、上記（１７）式において、ａは平滑化パラメータである）
【００２５】
（第１０の実施形態）
本発明の第１０の実施形態である複数経路負荷分散方法（請求項１０）においては、第１、第８、第９のいずれかの方法で、ρｉ，Ｎｉ，Ｄｉの測定を一定周期Ｔ毎に行う手段、第１から第７のいずれかの方法で品質劣化経路および品質維持経路を判定し、品質劣化経路から品質維持経路へユーザフローの経路を変更する手段を具備することを特徴とする。
【００２６】
（実施例の説明）
以下、図面により本発明の実施例について説明する。
図２は、本発明の一実施例を示すネットワークの基本構成図である。
発信元ノード１１から着信先ノード１２へｎ本の経路１〜ｎが設定され、各経路１〜ｎはいくつかのリンク１６〜２１と中継ノード１３〜１５を介して張られている。図２の発信元ノード１１に複数経路負荷分散装置が設定される形態で利用される。
【００２７】
図３は、本発明の一実施例を示す複数経路負荷分散装置の構成図である。
ここでは、本発明の第８の方法で、使用率ρｉ、Ｎｉ、Ｄｉの測定を一定周期Ｔ毎に行い、第１の方法で品質劣化経路および品質維持経路を判定して、品質劣化経路から品質維持経路へユーザフローの経路を変更する複数経路負荷分散方法を用いた第１０の実施形態を用いた複数経路負荷分散装置３０の構成を示している。
【００２８】
図３に示すように、ユーザから到着したパケットは、経路設定部３１でパケットヘッダに該ユーザの転送すべき経路を示す経路情報をパケットヘッダに書き込むか、あるいは、新たなヘッダを追加する。次に、パケットヘッダ解析部３２によりパケットサイズ、ＴＣＰフラグ情報を読み取られた後、経路制御部３３へ送信される。経路制御部３３は、そのパケットのヘッダ情報から転送すべき経路を読み出し、その経路へ転送する。
【００２９】
パケットヘッダ解析部３２により読み取られたパケットサイズは、転送レート測定部３５へ通知され、転送レート測定部３５は一定周期Ｔの間に通過したパケットのサイズの和を経路毎、かつユーザフロー毎（あるいは、予め定めたユーザフローグループ毎）に計算し、その値をＴで割ることにより経路ｉへの転送レートＤｉならびにユーザフロー（グループ）１の転送レートＤｉ，ならびにＤｉｌをを算出し、Ｄｉを１ユーザ使用帯域算出部３８に通知する。
【００３０】
一方、ＴＣＰフラグ情報は、パケットヘッダ解析部３２から同時接続ユーザフロー数測定部３６に通知される。同時接続ユーザフロー数測定部３６は、経路ｉにおいてＴＣＰフローの開始を示すＳＹＮフラグビットが立っているパケットを検出したならば、新しいフロー発生と判断し、同時接続フロー数カウンタを１増加する。また、ＴＣＰフロー終了を表すＦＩＮフラグビットが立っているパケットを検出したならば、同時接続フロー数カウンタを１減少させる。Ｔ時間毎に、このカウンタ値の平均値Ｎｉを算出し、１ユーザ使用帯域算出部３８に通知する。
【００３１】
１ユーザ使用帯域算出部３８は、経路ｉにおける１ユーザ当りの使用帯域Ｕｉ＝Ｄｉ／Ｎｉにより算出し、かつＵａｖｅ＝ΣＵｉ／ｎを計算し、ＵｉおよびＵａｖｅを経路品質判定部３９に通知する。
リンク使用率管理部３７は、一定周期Ｔ毎に、経路ｉ上にあるリンクｊの使用帯域Ｂ（ｉ，ｊ）［ｂｐｓ］の測定を中継リンクに指示し、その結果を受信して、経路ｉのボトルネックリンク使用率をρｉ＝ｍａｘｊ（Ｂ（ｉ，ｊ）／Ｃ（ｉ，ｊ））（Ｃ（ｉ，ｊ）は経路ｉかつリンクｊのリンク容量［ｂｐｓ］）により算出し、またボトルネックとなるリンク容量をＣｉとして、ρｉおよびＣｉを経路品質判定部３９に通知する。
【００３２】
経路品質判定部３９は、Ｕａｖｅおよび予め定めた閾値ε１，ε２，ρｔｈ１，ρｔｈ２を用いて、Ｕｋ＜（１−ε１）×Ｕａｖｅ　かつρｋ＞ρｔｈ１を満たす経路を品質劣化経路とし、Ｕｋの値で品質劣化経路を昇順に並び替え、そのときのｊ番目の経路を品質劣化経路ｋｊ（ｋｊ＝ｋ１〜ｋｋ）とする。また、Ｕｍ＞（１＋ε２）×Ｕａｖｅ　かつρｍ＜ρｔｈ２を満たす経路を品質維持経路とし、Ｕｍの値で品質維持経路を降順に並び替え、そのときのｊ番目の経路を品質維持経路ｍｊ（ｍｊ＝ｍ１〜ｍＭ）とし、経路変更トラヒック量算出部４０に通知する。
【００３３】
経路変更トラヒック量算出部４０は、品質劣化経路ｋｊから品質維持経路ｍｊへ移動すべきトラヒック量を、ｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して下式（７）式により算出し、経路変更指示部３４に通知する。
ｄｊ＝ｍｉｎ｛（ρｔｈ２−ρｍｊ）×Ｃｍｊ，（Ｕａｖｅ−Ｕｋｊ）／（Ｃｋｊ−Ｕｋｊ）×ρｋｊ×Ｃｋｊ×δ｝　　　　　　・・・・・・・・・・・・・・・・・・・（７）
なお、δは予め定めた係数である。
【００３４】
経路変更指示部３４は、転送レート測定部３５からユーザフロー（グループ）毎の転送レートを受信し、品質劣化経路ｋｊに属するユーザフロー（グループ）１の転送レートＤｋｊ，１を昇順に並び替え、下記（１８）式を満たす１＊を求める。
Ｄｋｊ，１＋Ｄｋｊ，２＋・・＋Ｄｋｊ，１＊＜ｄｊ＜Ｄｋｊ，１＋Ｄｋｊ，２＋・・・＋Ｄｋｊ，１＊＋Ｄｋｊ，（１＊＋１）　　　　・・・・・・・・（１８）
次に、ユーザフロー（グループ）１から１＊までを経路ｋｊから経路ｍｊへ変更するように、経路設定部３１へ指示する。経路設定部３１は、その指示に従って経路の設定テーブルを変更する。以上をｊ＝１〜ｍｉｎ（Ｋ，Ｍ）に対して行う。
【００３５】
図３に示す複数経路負荷分散装置３０内の各ブロックを接続したフロー処理を、プログラムに変換し、変換されたプログラムを発信元ノード１１に設置された分散装置３０の各制御部に装着して、プログラムをインストールすることにより、各制御部でこれを実行すれば、本発明を容易に実現することが可能である。
【００３６】
【発明の効果】
以上説明したように、本発明によれば、測定が簡易な同時接続ユーザフロー数と使用帯域、経路上のボトルネックリンク使用率、などの値のみから各経路上のユーザ通信品質を均等に維持できるような複数経路負荷分散方法および装置を実現することができる。
【図面の簡単な説明】
【図１】本発明における１ユーザ使用帯域とリンク使用率の関係を示す特性曲線図である。
【図２】本発明の一実施例を示すネットワークの基本構成図である。
【図３】本発明の一実施例を示す複数経路負荷分散装置の構成図である。
【符号の説明】
１１…発信元ノード、１２…着信先ノード、１３〜１５…中継ノード、
１６〜２１…リンク、３０…複数経路負荷分散装置、３１…経路設定部、
３２…パケットヘッダ解析部、３３…経路制御部、３４…経路変更指示部、
３５…転送レート測定部、３６…同時接続ユーザフロー数測定部、
３７…リンク使用率管理部、３８…１ユーザ使用帯域算出部、
３９…経路品質判定部、４０…経路変更トラヒック量算出部。
【図１】
2004056737.tif 000003
【図２】
2004056737.tif 000004
【図３】
2004056737.tif 000005