(57)【特許請求の範囲】
【請求項１】
ネットワーク内でソースノードから宛先ノードにトラフィックを経路指定する方法であって、前記ネットワークが、前記ソースノードおよび前記宛先ノードを含む複数のノードと、前記複数のノードを接続する複数のリンクとを備えており、
前記複数のノードの各ノードによって、前記ノードのためのノードメトリック値を演算するステップであって、
前記ノードメトリック値の、隣接するノードからの成分を計算し、隣接するノードからの前記成分は、前記ノードのすべての隣接ノードから前記ノードへの今後のトラフィックを反映しており、
前記ノードの前記複数のリンクのすべてのうちの各リンクのための今後のトラフィックを決定し、前記今後のトラフィックは、前記ノードから複数の隣接ノードのうちの１つの隣接ノードに送られるべきパケットの数、または、前記１つの隣接ノードから前記ノードに送られるべきパケットの数を表しており、
前記ノードメトリック値の、隣接するノードへの成分を計算し、前記隣接するノードへの成分は、前記ノードから前記隣接ノードへの今後のトラフィックを反映しており、そして、
前記隣接するノードからの成分を前記隣接するノードへの成分に加算して、前記ノードメトリック値を得る
ことによって行われるところのステップと、
前記ソースノードから前記宛先ノードへのすべての使用可能な経路の各経路についての経路メトリック値を、前記経路に沿った複数の中間ノードのノードメトリック値を加算することによって決定するステップと、そして、
前記使用可能な経路の各経路の経路メトリック値に従って、前記ソースノードから前記宛先ノードへの負荷を前記使用可能な経路に割り当てるステップと
を含む方法。
【請求項２】
前記ノードメトリック値の、前記隣接するノードからの成分の前記計算が、
前記ノードのすべてのリンクの各リンクについて今後のトラフィックを決定するステップと、そして、
前記ノードの複数のリンクの今後のトラフィックを加算するステップと
を含む、請求項１に記載の方法。
【請求項３】
前記ノードのすべてのリンクの各リンクについての今後のトラフィックの前記決定が、
前記リンクの端部での隣接ノード内のキューの長さを決定するステップであって、前記キューが、前記ノードに送るべきパケットを格納するところのステップと、
データを前記ノードに送るために、前記隣接ノードの使用可能な帯域幅を決定するステップと、そして、
キューの前記長さと前記隣接ノードの前記使用可能な帯域幅を比較して、前記リンクについて今後のトラフィックを得るステップと
を含む、請求項２に記載の方法。
【請求項４】
前記ノードメトリック値の、前記隣接するノードへの成分の前記計算が、
前記ノードからデータを受け取るために、前記隣接ノードによって付与された帯域幅を決定するステップと、そして、
前記隣接ノードでの使用可能な帯域幅が制約要因である場合に、前記隣接ノードによって付与された前記帯域幅を加算して、隣接するノードへの成分を得るステップと
を含む、請求項３に記載の方法。
【請求項５】
前記ノードメトリック値の、前記隣接するノードへの成分の前記計算が、
前記ノードからデータを受け取るために、前記隣接ノードによって付与された帯域幅を決定するステップと、そして、
前記隣接ノードでの使用可能な帯域幅が制約要因である場合に、前記隣接ノードによって付与された前記帯域幅を加算して、隣接するノードへの成分を得るステップと
を含む、請求項２に記載の方法。
【請求項６】
前記ソースノードから前記宛先ノードへの負荷の前記割り当てが、
前記負荷を前記使用可能な経路に均等に割り当てるステップと、そして、
最も輻輳している経路から最も輻輳していない経路に負荷をシフトするステップと
を含む、請求項１に記載の方法。
【請求項７】
前記ノードメトリック値の、前記隣接するノードへの成分の前記計算が、
前記ノード内のキューの長さを決定するステップであって、前記キューが前記隣接ノードに送るべきパケットを格納するところのステップと、そして、
前記隣接ノードで使用可能な帯域幅が制約要因でない場合に、キューの前記長さを加算して、隣接するノードへの成分を得るステップと
を含む、請求項２に記載の方法。
【請求項８】
ネットワーク内でソースノードから宛先ノードにトラフィックを経路指定する方法であって、前記ネットワークが、前記ソースノードおよび前記宛先ノードを含む複数のノードと、前記複数のノードを接続する複数のリンクとを備えており、
前記複数のノードの各ノードによって、前記ノードのためのノードメトリック値を演算するステップであって、
前記ノードのすべてのリンクの各リンクについてメトリック値寄与要因を演算し、そして、
前記メトリック値寄与要因を加算して、前記ノードメトリック値を得る
ことによって行われるところのステップと、
前記ソースノードから前記宛先ノードへのすべての使用可能な経路の各経路について、前記経路に沿った中間ノードの、演算されたノードメトリック値を加算することによって、経路メトリック値を決定するステップと、そして、
前記使用可能な経路の各経路の経路メトリック値に従って、前記ソースノードから前記宛先ノードへの負荷を前記使用可能な経路に割り当てるステップと
を含む方法。
【請求項９】
前記リンクのための前記メトリック値寄与要因の前記計算が、
隣接ノードから前記ノードへの前記リンクに沿った第１の今後のトラフィックを決定するステップと、
前記ノードから前記隣接ノードへの第２の今後のトラフィックを決定するステップと、そして、
前記第１の今後のトラフィックと前記第２の今後のトラフィックとを加算して、前記リンクのための前記メトリック値寄与要因を得るステップと
を含む、請求項８に記載の方法。
【請求項１０】
第１の今後のトラフィックの前記決定が、
前記ノードに送るべきパケットを格納するために、前記隣接ノード内のキューの長さを決定するステップと、
前記隣接ノードの使用可能な帯域幅を決定するステップと、そして、
キューの前記長さと前記隣接ノード内の前記使用可能な帯域幅とを比較して、前記第１の今後のトラフィックを得るステップと
を含む、請求項９に記載の方法。
【請求項１１】
前記ソースノードから前記宛先ノードへの負荷の前記割り当てが、
前記負荷を前記使用可能な経路に均等に割り当てるステップと、そして、
最も輻輳している経路から最も輻輳していない経路に負荷をシフトするステップと
を含む、請求項１に記載の方法。
【請求項１２】
前記第２の今後のトラフィックの前記決定が、
前記ノードからデータを受け取るために、前記隣接ノードによって付与された帯域幅を決定するステップと、
前記隣接ノードで使用可能な帯域幅が制約要因である場合に、前記ノードの隣接ノードによって付与された前記帯域幅を加算して、前記第２の今後のトラフィックを得るステップと
を含む、請求項９に記載の方法。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、データネットワークにおける経路指定を改良するための方法に関する。詳細には、本発明は、ルータの処理速度が制約要因となっているネットワーク内でデータを経路指定するための方法を開示する。
【０００２】
（背景技術）
図１は、従来の技術による典型的なネットワーク１００の構造を示した図である。ネットワーク１００は、アプリケーションプログラムを実行することを目的とした複数のホスト１１０を備える。ネットワーク１００はまた、ホスト１１０にリンクし、それらの間でメッセージを運ぶサブネット１４０を含む。サブネット１４０は、通常、２つの基本構成要素、すなわち、ルータ１２０（スイッチング素子、ノード、またはインターフェースメッセージプロセッサとも呼ぶ）と、リンク１３０（伝送線とも呼ぶ）とを備える。それぞれのホスト１１０が、１つの、または時にはいくつかのルータ１２０に接続される。
【０００３】
メトリック値は、同じ１対のソース宛先ルータ１２０を接続する経路同士を比較することのできる数である。経路が、１対のソース宛先ルータ１２０を接続する１組のリンク１３０を備える。設計者が、トラフィックが最小経路メトリック値によって定義される最も効率的な経路をとるようにメトリック値を選択する。ルータ１２０が、実際に、１対のソース宛先ルータ１２０を接続する経路全体のメトリック値を評価できる。経路指定アルゴリズムにより、エンドツーエンド経路に適用される値としてのメトリック値を計算することができる。この方法で、メトリック値により、同じ宛先ルータ１２０への経路の比較が可能となる。もう１つのメトリック値の使用法は、ルータ１２０からの出リンク１３０に関連するコストを決定することである。多くの経路指定アルゴリズムにおいて、エンドツーエンドメトリック値（経路メトリック値）は、リンクメトリック値の和である。
【０００４】
従来の技術による経路指定プロトコルでは、メトリック値を計算するためにさまざまな方法が使用されている。経路指定情報プロトコル（ＲＩＰ）と同様に、１対のソース宛先ルータ１２０間のホップ（経路上のルータ１２０の数）をカウントする方法がある。他には、メトリック値を計算するための標準的な方法を持たずに、計算を局所的に選択する方法がある。メトリック値の計算に使用する要因には、以下のものが含まれる。すなわち、１．リンク帯域幅、２．リンク遅延、３．金銭的なコストなどの管理上の優先項目、４．リンク誤り率、５．リンク利用率である。現実のネットワーク内において、これらすべての要因が有用であるわけではない。特に、リンクメトリック値にリンク利用率を不適切に使用すると、経路振動が生じる可能性がある。たとえば、ある宛先に対する経路１（図示せず）上にトラフィックがあると仮定する。次いで、経路２（図示せず）が生じ、これも、同じ宛先に対して接続している。経路１および２の両方が、等しい帯域幅を有すると仮定する。経路２は、より負荷の重い経路１と比べて、より魅力のあるものとなる。次いで、トラフィックが経路２に移行し、経路１の負荷が軽くなり、そのため、より負荷の重くなった経路２と比べて、より魅力的なものとなる。このことにより、経路１および経路２間を交替して、最適な経路を選択することが可能となる。
【０００５】
メトリック値は、一般に、同じ動的経路指定プロトコル内でのみ比較可能である。ＲＩＰは、ホップカウントを使用し、それに対して、ＩＧＰＲ（内部ゲートウェイ経路指定プロトコル）およびＥＩＧＰＲ（拡張ＩＧＰＲ）は、実際には、一般に、帯域幅に基づく、同じ複雑な数式を使用する。ＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）は、実際には、ＩＧＰＲおよびＥＩＧＰＲと同様の、帯域幅に基づく、任意のインターフェースコストを使用する。
【０００６】
図２は、本発明によるネットワーク２００の構造を示した図である。例示のため、ネットワーク２００は、ブロードバンドワイヤレスメッシュトポロジネットワークとなっている。各ノード２１０は、見通し範囲（ＬＯＳ）がワイヤレス媒体リンク２２０を介して存在する他のＳＲノード２１０と、（たとえば、６ＧＨｚを超える）高い周波数で通信するための独特の能力を有する加入者無線（ＳＲ）とすることができる。ネットワーク２００に対して媒体アクセスを提供する独立したスケジューリングアルゴリズムがある。基本的に、各ノードは、その今後にスケジュールされている送信時間を他のノードに通信し、データを受け取るために使用可能なスロットを他のノードに知らせる。スケジュールは、連続更新される。このようにして、通信するノードは、データを交換するために使用可能な今後の時間について合意に達する。ネットワーク２００内の各ノード２１０は、任意の１回にその隣接ノード２１０の１つのみと通信することができる。たとえば、ノード４が１００Ｍｂｐｓの帯域幅を有すると仮定すると、ノード４がその隣接ノード１、２、５、６と通信する通信速度（Ｍｂｐｓでの）の和は、１００Ｍｂｐｓ以下でなければならない。このことは、ノード４を介するノード１からノード５へのトラフィックフローが、ノード４を介するノード２からノード６へのもう１つのトラフィックフロー用に残されている帯域幅に影響を与えるということであり、また逆も同じである。特に、ノード４がその帯域幅の４０Ｍｂｐｓを使用してノード２からパケットを受け取り、その帯域幅のもう１つの４０Ｍｂｐｓを使用してパケットをノード６に転送する場合、ノード１からノード５へのトラフィックを扱うために残されている帯域幅は２０Ｍｂｐｓだけである。ノード４は、ノード１からパケットを受け取るために２０Ｍｂｐｓの残りの帯域幅のうちの１０Ｍｂｐｓを使用することができ、そのパケットをノード５に転送するために、その使用可能な帯域幅のうちの最後の１０Ｍｂｐｓを使用する。
【０００７】
図２のネットワーク２００について、従来の技術による典型的なメトリック値の割当てには、欠点がある。第１に、ホップカウントメトリック値が、経路のメリットを反映しない。たとえば、ノード４が、ノード２からパケットを受け取るために１００Ｍｂｐｓのその帯域幅のうちの４０Ｍｂｐｓを使用し、そのパケットをノード６に転送するために４０Ｍｂｐｓを使用すると仮定すると、ノード１が、ホップカウントメトリック値を頼りに、４０Ｍｂｐｓでノード５にフローを送りたい場合、ここで、負荷の最適配分が適用可能であると仮定して、ノード３およびノード４を介して２つの経路間で負荷を半々に分割する。このことは、ノード４が、ノード１からパケットを受け取るために帯域幅の最後の２０Ｍｂｐｓを使用するということである。６０Ｍｂｐｓ（ノード２から４０Ｍｂｐｓおよびノード１から２０Ｍｂｐｓ）の入力速度と、わずか４０Ｍｂｐｓ（ノード６へ）の出力速度で、ノード４は、後のノード５への転送用にパケットを格納するためにバッファを使用しなければならない。すぐに、このバッファ内のキューはオーバーフローして、ノード４はパケットを落とさなければならない。これを、ノード輻輳と呼ぶ。したがって、ホップカウントメトリック値は、ノード１がノード３にそのトラフィックを迂回する必要があることを反映しない。
【０００８】
第２に、リンク帯域幅に基づくメトリック値の割当ても、ネットワーク２００に適用した場合、欠点を有する。（ノード１とノード４とを接続する）リンク１〜４および（ノード４とノード５とを接続する）リンク４〜５が、非常に高い帯域幅を有し、したがって、低いメトリック値を有すると仮定すると、ノード４を介するノード１からノード５への経路が好ましいものとなる。しかし、本発明によるネットワーク２００では、ノード４が制約要因であり、リンク１〜４や４〜５ではない。リンク１〜４および４〜５のための典型的なメトリック値は、変わらず、したがって、これら２つのリンクを含む経路のための経路メトリック値もまた、たとえノード４が、ノード４を介してノード２からノード６へのトラフィックを扱う帯域幅を使い果たした場合においても、変わらない。その結果、ノード１が４０Ｍｂｐｓでノード５にフローを送りたい場合には、ノード４を介する経路は魅力のあるものであるが、実際には、経路は、ノード４で輻輳している。
【０００９】
本発明の一目的は、本発明によるネットワーク２００において、どの１対のソース宛先ルータ間の経路の状況をも、より良く反映するための新しいメトリック値システムを提供することである。
【００１０】
（発明の概要）
本発明は、ノードメトリック値と呼ぶ、メリットのある新しい測定値を使用することにより、上述した目的を実現する。この技術により、経路の状況が、経路上の中間ノードのノードメトリック値を加算することにより計算される経路メトリック値によって表される。ノードメトリック値を計算する際に使用される要因には、以下のものが含まれる。すなわち、１．隣接ノードからそのノードへの今後のトラフィック、および２．そのノードから隣接ノードへの今後のトラフィックである。今後のトラフィックは、トラフィックスケジューリングの同報から周知である。
【００１１】
（発明を実施するための最良の形態）
図２を参照すると、ノード４を介するノード１からノード５への経路のメトリック値が、すべての中間ノードのノードメトリック値を加算することによって計算される。ここで、ノード４は、経路の唯一の中間ノードであり、したがって、そのメトリック値は、その経路の経路メトリック値でもある。経路メトリック値を計算するために、経路に沿った中間ノードのノードメトリック値を組み合わせる他の方法も使用できる。
【００１２】
ノード２１０のノード帯域幅は、ネットワーク２００におけるノード２１０の最大処理速度である。ノード２１０が、任意の１回、ただ１つの他のノード２１０と通信できるため、ノード２１０の帯域幅は、そのリンク間で共用される。ノード４が１００Ｍｂｐｓの帯域幅を有すると仮定すると、この帯域幅は、ノード１、２、５、および６に対する、その４つのリンク間で共用できる。言い換えれば、ノード４の４つのリンク上のトラフィック速度の和は、１００Ｍｂｐｓ以下でなければならない。一般に、リンクｉ〜ｊ上のトラフィック速度をＲ（ｉ，ｊ）で表し、次いで、Ｒ（４，１）＋Ｒ（４，２）＋Ｒ（４，５）＋Ｒ（４，６）≦１００Ｍｂｐｓとし、ここで、記号≦は、以下を表す。同様に、ノード３については、ノード３の最大帯域幅が１００Ｍｂｐｓと仮定して、Ｒ（３，１）＋Ｒ（３，５）≦１００Ｍｂｐｓである。
【００１３】
ノード４の４つのリンク上のトラフィックが、パケットがノード４に来ている場合は、入力トラフィックであり得るし、または、パケットがノード４から出てくる場合は、出力トラフィックであり得る。入力トラフィック速度が出力トラフィック速度を超える場合は、いくつかの入力パケットが、ノード４のバッファ内のキューに入れられなければならない。このキューの長さは、ノード４のメトリック値を計算する際の構成要素である。出力トラフィック速度が入力トラフィック速度を超える場合は、キュー内に以前に格納されたいくつかのパケットは、現在、所定の宛先に転送されている。
【００１４】
本発明によるノードのノードメトリック値は、隣接するノードからの成分と隣接するノードへの成分を備える。ノードのメトリック値の隣接するノードからの成分は、そのノードの隣接ノードからのデータ転送要求を扱うために必要なノードの帯域幅を反映する。ノードの隣接ノードが、そのノードに送るべきパケットの大きいキューを有し、これらの隣接ノードが、これらのパケットをそのノードに送るために使用可能な帯域幅を有する場合、そのノードは、隣接ノードからこれらのパケットを受け取るために、その帯域幅の多くを使用しなければならない。言い換えれば、そのノードに送るべきパケットのための隣接ノード内のキューが長くなり、これらの隣接ノードが、これらのパケットをそのノードに送るために使用可能な帯域幅を多く有する場合、そのノードのノードメトリック値を増加して、そのノードが、そのノードの隣接ノードからの増大し続けるデータ転送要求を扱うことにますます忙しくなることを示さなければならない。
【００１５】
ノードのメトリック値の隣接するノードへの成分は、そのノードからその隣接ノードへのデータ転送要求を扱うために必要なノードの帯域幅を反映する。ノードが、その隣接ノードに送るべきパケットの大きいキューを有する場合、そのノードは、これらのパケットを隣接ノードに送るために、その帯域幅の多くを使用しなければならない。言い換えれば、隣接ノードに送るべきパケットのためのそのノード内のキューが長くなる場合、そのノードのノードメトリック値を増加して、そのノードが、そのノードから隣接ノードへの増大し続けるデータ転送要求を扱うことにますます忙しくなることを示さなければならない。
【００１６】
ノードのリンク上の今後のトラフィックが、リンクの他の端部でそのノードから隣接ノードまで、または隣接ノードからそのノードへのいずれかで送るべきパケットの数によって表される。これらのパケットは、隣接ノードがそれらを受け取るのを待っているノード内のキューの中にある可能性がある。これらのパケットはまた、そのノードがそれらを受け取るのを待っている隣接ノード内のキューの中にある可能性もある。図２を参照して、ノード４がその全キャパシティを使用しており、次いで、ノード１が、ノード４に送るべきパケットを有すると仮定すると、ノード１は、後にノード４がいくらかの使用可能な帯域幅を有するようになった時に、ノード４に送るべきこれらのパケットをそのキュー内に入れなければならない。隣接するノードからの成分およびノード４のメトリック値を増加して、ノード４の帯域幅のいくつかを、ノード１内のキューを空にするために（すなわち、ノード１内のキューからパケットを受け取るために）今後に使用する必要がある場合の影響を反映しなければならない。たとえノード４がパケットを受け取るために使用可能な帯域幅を有していたとしても、ノード１もビジーであり、そのキューからノード４までパケットを送ることができない場合には、例外が適用される。この場合、ノード１がそれらをノード４に送るために使用可能な帯域幅を有していない限り、キュー内のパケットはノード４にとって負担にはならないため、ノード４のメトリック値を増加すべきではない。言い換えれば、ノード１内のキューの長さ、またはノード１がキューを空にするために使用可能な帯域幅のいずれかが、ノード４のメトリック値の一因となる制約要因である。一方が制約要因である場合、他方は、たとえそれが増加する場合でも、影響を及ぼさない。
【００１７】
周期的に、たとえば、マイクロ秒毎に、ノードメトリック値が更新（再計算）される。そのネットワークに対する設計者の望む特性により、ノードメトリック値構成要素を全部加算して、そのノードのためのメトリック値を得るか、または全部を加算する前に係数によって乗算することができる。
【００１８】
ノードメトリック値は、いくつかの経路上のトラフィックがノードの負荷を増加させた場合、そのノードのメトリック値が増加するという、基本プロパティを有する。たとえ経路のどのリンク上にもトラフィックがない場合でも、ノードは、経路の経路メトリック値の一因となる高いメトリック値を有することができる。以下に記述するように、各ノードでの輻輳の測定値（ノードメトリック値）は、ソースに向けて伝搬して戻る必要がある。このことは、周期的に送られる特別な経路指定パケットを介して、あるいは他の制御パケットまたはデータパケット上の情報をピギーバックすることにより、容易に行える。
【００１９】
以下の例は、本発明を使用するノードメトリック値の計算を示している。ノードｎが、数式
【００２０】
【数１】
0004756143.tif 000002
【００２１】
を使用して、それ自体のノードメトリック値Ｍ（ｎ）を計算する。
上式で、Ｎは、ノードｎのすべての隣接ノードの１組であり、
Ａi（ｎ）＝Ｍｉｎ［Ｑi（ｎ），ＢＷＡi（ｎ）］、
ＢＷＡn（ｉ）＞Ｑn（ｉ）またはＢＷＡn（ｉ）＞１．２*ＢＷＧi（ｎ）の場合は、Ｂi（ｎ）＝ＢＷＧi（ｎ）、
その他の場合は、Ｑn（ｉ）である。
【００２２】
上式で、Ｑi（ｎ）は、ノードｎに送るべきパケットのためのノードｉでのキューの長さである。
【００２３】
Ｑn（ｉ）は、ノードｉに送るべきパケットのためのノードｎでのキューの長さである。
【００２４】
ＢＷＧi（ｎ）は、帯域幅が付与される期間によって分割された、ノードｎからパケットを受け取るために、ノードｉによって付与される帯域幅である。
【００２５】
ＢＷＡi（ｎ）は、帯域幅が付与される期間によって分割された、ノードｎにパケットを送るために、ノードｉで使用可能な帯域幅である。
【００２６】
ＢＷＡn（ｉ）は、帯域幅が付与される期間によって分割された、ノードｉにパケットを送るために、ノードｎで使用可能な帯域幅である。
【００２７】
ΣiεNＡi（ｎ）は、ノードｎのノードメトリック値の隣接するノードからの成分であ
る。Ａi（ｎ）は、ノードｎが扱うためにその帯域幅のいくつかまたはすべてを使用しなければならない、ノードｉからノードｎへの、リンクｉ〜ｎ上の今後のトラフィックを反映する。Ａi（ｎ）は、２つの構成要素、Ｑi（ｎ）およびＢＷＡi（ｎ）を有する。Ｑi（ｎ）が短い場合、すなわち、ノードｎに送るべきパケットのためのノードｉでのキューの長さが短い場合、または言い換えれば、ノードｎに送るべきパケットがそれ程多くない場合は、ノードｎのメトリック値は、ノードｎを通過中のどの経路にとっても良い知らせであることを反映して、低くなければならない。ＢＷＡi（ｎ）が小さい場合、すなわち、帯域幅が付与される期間によって分割された、ノードｎに送るためにノードｉで使用可能な帯域幅が小さい場合は、ノードｉは、ノードｎに少ない数のパケットしか送ることができず、ノードｎのメトリック値は、ノードｎを通過中のどの経路にとっても良い知らせであることを反映するため、低くなければならない。これら２つの条件のうちのいずれかが、制約要因となる。たとえば、ノードｉがビジーであり、パケットをノードｎに送るために使用可能な帯域幅がない場合、すなわち、ＢＷＡi（ｎ）＝０である場合、Ｑi（ｎ）がどんなに大きい場合でもそれにかかわらず、Ａi（ｎ）＝Ｍｉｎ［Ｑi（ｎ），ＢＷＡi（ｎ）］＝０となる。ここで、ＢＷＡi（ｎ）は、制約要因である。
【００２８】
ΣiεNＢi（ｎ）は、ノードｎのノードメトリック値の隣接するノードへの成分である
。Ｂi（ｎ）は、ノードｎが、パケットをその隣接ノードｉに送る必要性を扱うために、どのぐらいの帯域幅を使用しなければならないかを反映する。一般に、Ｂi（ｎ）＝Ｑn（ｉ）である。このことは、一般に、ノードｎが、隣接ノードｉに送るべきパケットのキューを空にするために必要なだけ帯域幅を使用しなければならないということである。しかし、ノードｉがビジーであり、したがって、これらのパケットを受け取ることができないという状況が存在する。そのような場合は、ノードｎは、キューを空にするためにその帯域幅を使用しない。その結果、ノードｎのメトリック値は、このような状況においては、Ｑn（ｉ）に依存せずに、ノードｉがノードｎからパケットを受け取るようコミットした速度（付与された／コミットされた帯域幅）に依存すべきである。このような状況は、ほぼＢＷＡn（ｉ）＞Ｑn（ｉ）またはＢＷＡn（ｉ）＞１．２*ＢＷＧi（ｎ）の場合に起きる。
【００２９】
このＢＷＡn（ｉ）＞Ｑn（ｉ）の状況は、ノードｎがキューＱn（ｉ）を空にするために多くの使用可能な帯域幅を有する時に、ノードｎから受け取るためにノードｉに付与された／コミットされた帯域幅が制約要因であり、したがってＢi（ｎ）を表すべきであることを意味する。
【００３０】
同様に、このＢＷＡn（ｉ）＞１．２*ＢＷＧi（ｎ）の状況は、ノードｉがノードｎから受け取るために付与された帯域幅よりも、ノードｎがより多くの使用可能な帯域幅を有する場合に、ＢＷＧi（ｎ）が制約要因であり、Ｂi（ｎ）を表すべきであることを意味する。
【００３１】
ノードのノードメトリック値は、以下のように書き換えることができる。
【００３２】
【数２】
0004756143.tif 000003
【００３３】
上式で、Ａi（ｎ）＋Ｂi（ｎ）は、ノードｉおよびノードｎを含むノード対ｉ〜ｎに対応するメトリック値寄与要因である。すべてのメトリック値寄与要因を計算した後に、ノードｎは、それらを組み合わせて、そのメトリック値を得る。上述した数式において、組み合わせるとは、全部を加算することである。
【００３４】
ルートの経路メトリック値によって表されるルートの輻輳は、ソースノードと宛先ノードとを除いた、すべての中間ノード輻輳の測定値（ノードメトリック値）を加算することによって決定される。ルート（経路）の輻輳はまた、加重加算法、指数法の加算、最大法、またはそれらの組合せによっても決定することができる。加重加算法とは、ソースノードと宛先ノードとを除いた、経路上のノードのノードメトリック値のそれぞれを、全部加算する前に、係数で乗算することである。指数法の加算とは、ソースノードと宛先ノードとを除いた、経路上のノードのノードメトリック値のそれぞれを、全部加算する前に、いくらか累乗することである。最大法とは、ソースノードと宛先ノードとを除いた、経路上のノードのノードメトリック値の中の最高のノードメトリック値を、経路メトリック値として使用することである。
【００３５】
ソースノードが、ソースノードから宛先ノードへのすべての使用可能な経路の経路メトリック値を計算した後、ソースノードは、以下の方式でそのトラフィックを宛先ノードに割り当てることができる。
【００３６】
１．最低の経路メトリック値を有する経路を常に使用する。
【００３７】
２．各経路上のトラフィック量が経路メトリック値に反比例する、すべての使用可能な経路を使用する。
【００３８】
３．最良のＮ経路のみを使用する。ここで、Ｎは、変数に固定することができる。これらの経路間のトラフィックの割当ては、均等でも、またはこれらの経路の経路メトリック値に依存していてもよい。
【００３９】
４．使用可能な経路の間でトラフィックを均等に割り当て、次いで、最も輻輳した経路から最も輻輳していない経路に負荷をシフトする。このシフト量は、固定量（パーセントで）でも、または輻輳の相違に依存していてもよい。
【００４０】
たとえば、図２を参照して、ネットワーク２００の各ノード２１０が、１２０Ｍｂｐｓの最大帯域幅（キャパシティ）を有すると仮定する。ノード２は、５４Ｍｂｐｓの速度でノード４を介してノード６に対してデータを生成し、その結果、ノード４は、ノード２からパケットを受け取るためにその１２０Ｍｂｐｓ帯域幅のうちの５４Ｍｂｐｓを、およびノード６へこれらのパケットを転送するためにもう１つの５４Ｍｂｐｓを使用する。その結果、ノード４は、残されている帯域幅のうちの１２Ｍｂｐｓのみを有する（１２０−２*５４）。ここで、ノード１が、５４Ｍｂｐｓの速度でノード５にデータを送り始めると仮定する。このトラフィックに対しては２つの使用可能な経路がある。第１の経路は、ノード３を介して進み、第２の経路は、ノード４を介して進む（さらに、許容されたループはないと仮定する）。本発明によるノードメトリック値システムによれば、ノード４は、その帯域幅がほとんど使用されている（１０８／１２０）ため、高いメトリック値を有する。したがって、第２の経路は、第１の経路よりはるかに高い経路メトリック値を有する（ノード１が送り始める前は、ノード３は、全く負荷を持たない）。最初に、ノード１からの負荷が、２つの経路間で半々に分割される。すなわち、第１のパケットはノード３に送られ、第２のパケットはノード４に送られ、第３のパケットはノード３に送られ．．．と続く。これは、ノード１からノード４への２７Ｍｂｐｓと同様である。しかし、ノード４には、これを受け取るためにほんの１２Ｍｂｐｓしか残されていない。その結果、ノード４は、ノード１からパケットを受け取るために残りの１２Ｍｂｐｓのすべてを使用し、ノード４向けのノード１からのパケットの一部を、ノード１内のキューに入れなければならない。ノード４のノードメトリック値がさらに増加する原因となる、いくつかの事象がある。第１に、ノード４に送るべきパケットを保持するノード１内のキューの長さＱ1（４）が増加する。第２に、ノード４が、ノード１からノード５にパケットを転送するために残されている帯域幅を有さないため、ノード５に送るべきパケットを保持するノード４内のキューの長さＱ4（５）が増加する。第３に、ノード１は、ノード４に送るべき多くの使用可能な帯域幅ＢＷＡ1（４）を有する。これらの事象のすべてが、ノード４のメトリック値が、マイクロ秒毎に更新される場合、ノード４のメトリック値を増加させる一因となる。ノード１は、第１の経路のための低い経路メトリック値と第２の経路のための非常に高い経路メトリック値が、その負荷のほとんどを第１の経路にシフトさせることをただちに認識する。ノード４のメトリック値は、ノード１からノード４へのトラフィックが１２Ｍｂｐｓから６Ｍｂｐｓに減少すると、増加を停止する。この時、ノード４は、ノード１からノード５にパケットを転送するために６Ｍｂｐｓを使用し、ノード１からノード５に送るべきパケットのためのノード４内のキューは、増大することを停止し、ノード１内のキューもまた、増大することを停止する。しかし、ノード１は、第２の経路から第１の経路に負荷をシフトし続ける。定常状態で、ノード１は、第１の経路を介して８９％（４８．１Ｍｂｐｓ��を、および第２の経路を介して１１％（５．９Ｍｂｐｓ）を送る。このため、全部で１１９．９Ｍｂｐｓ（５４＋５４＋５．９＋５．９）となり、これは、ノード４のキャパシティ内である。
【００４１】
本発明によるノードメトリック値システムは、どのような特定のスケジューリング／帯域幅割当てアルゴリズムにも頼らない。本発明によるノードメトリック値システムで使用されるスケジューリングアルゴリズムは、帯域幅の動的割当てが可能である必要はない。
【００４２】
本発明によるノードメトリック値システムは、経路のメリット（経路メトリック値）を検査する場合、検査中の経路と同じノードを共用する他の経路上のトラフィックを考慮に入れる。したがって、本発明によるノードメトリック値システムは、従来の技術によるリンクメトリック値システム、特に、上述した種類の、ワイヤレスメッシュトポロジネットワークと比べて利点を有する。
【図面の簡単な説明】
【図１】  従来の技術による典型的なネットワークを示す図である。
【図２】  本発明によるネットワークを示す図である。
【図１】
0004756143.tif 000004
【図２】
0004756143.tif 000005