(57)【要約】多数の経路が利用可能な場合に宛先へのトラフィックのルーティングを最適化するための方法及びシステム（１００）。性能監視及び推論コンポーネント（１０２）は、大きな一組のサブネットワークへの利用可能な経路の性能を測定し、該測定値を使用して更に大きな一組のサブネットワークへの全ての利用可能な経路の性能を推論する。ルーティング最適化コンポーネント（１０４）は、前記コンポーネント（１０２）からの情報及び他の経路特性に基づきルーティングテーブルにコストを割り当てるコスト関数を使用し、更に最小化方法論を使用して、コスト関数により規定される極めて低いコストを有するルーティングテーブルを見つけだす。ＢＧＰブリッジ（１０６）は、前記最適化コンポーネント（１０４）により生成されたルーティングテーブルを取得し、その情報をＢＧＰを使用してルータ（１１６）に通信し、これにより、該ルータ（１１６）が該ルーティングテーブルに従ってトラフィック（１０８）のルーティングを行うことが確実となる。【選択図】図２
2004507917.tif 000002
【特許請求の範囲】
【請求項１】
複数のルートが利用可能なネットワークにおいてソースからルーティング宛先までトラフィックをルーティングするための方法であって、
前記ルートの各々にコストを割り当て、コスト関数により規定される最低のコストを有するルートを選択する、
という各ステップを有する、トラフィックのルーティング方法。
【請求項２】
前記選択されたルートをルータへ伝送するステップを更に含む、請求項１に記載の方法。
【請求項３】
前記ソースから前記選択されたルートを介した前記ルーティング宛先へのトラフィックのルーティングを前記ルータに行わせるステップを更に含む、請求項２に記載の方法。
【請求項４】
前記コストが、該コストが割り当てられるルート上の経路特性の関数である、請求項１に記載の方法。
【請求項５】
前記経路特性が、レイテンシ、パケット損失、ヘッドルーム、対価、経路長、ルート変化、及びＢＧＰ到達可能性からなるグループから選択される、請求項４に記載の方法。
【請求項６】
前記ルーティング宛先の場所を決定し、前記利用可能なルートを介した前記ソースから別の宛先へのトラフィックの送信に関連する前記経路特性の測定値に基づいて前記経路特性を推論する、という各ステップを更に含む、請求項４に記載の方法。
【請求項７】
前記ルーティング宛先の場所が円交差法により決定され、該円交差法が、
複数のソース場所から前記ルーティング宛先へトラフィックが移動するのに要する時間を測定し、
該時間を距離の等価値に変換し、
前記距離の等価値を円の半径として使用すると共に、前記ソース場所を中心として使用して、複数の交差する円を形成し、
該円の交差から前記ルーティング宛先の物理的な場所を決定する、
という各ステップを含む、請求項６に記載の方法。
【請求項８】
前記ソースから他の宛先への前記経路特性の加重平均を前記ルーティング宛先に対する前記他の宛先の物理的な近接性に基づいて決定することにより前記経路特性を推論するステップを更に含む、請求項４に記載の方法。
【請求項９】
前記ソースと複数の他の宛先との間のレイテンシを測定し、
前記ルーティング宛先と前記他の宛先との間の物理的な距離を決定し、
該距離の関数として前記レイテンシの測定値の加重平均を計算し、
該加重平均を前記ソースと前記ルーティング宛先との間のレイテンシの概算値として使用する、
という各ステップを更に含む、請求項１に記載の方法。
【請求項１０】
複数のルートが利用可能なネットワークにおいてソースからルーティング宛先へトラフィックをルーティングするための方法であって、
利用可能なルートの各々毎に、前記ソースから前記ルーティング宛先へのトラフィックのルーティングに関する経路特性の測定値を取得し、
コスト関数を使用して各利用可能なルートに該ルートに関する経路特性の関数としてコストを割り当て、
前記利用可能なルート上の前記コスト関数を最小化し、
該コスト関数の最小化により決定された最低コストのルートに従って前記トラフィックをルーティングする、
という各ステップを有する、トラフィックのルーティング方法。
【請求項１１】
前記最低コストのルートをルータへ伝送するステップを更に含む、請求項１０に記載の方法。
【請求項１２】
前記ソースから前記最低コストのルートを介して前記ルーティング宛先へのトラフィックのルーティングを前記ルータに行わせるステップを更に含む、請求項１１に記載の方法。
【請求項１３】
前記経路特性が、レイテンシ、パケット損失、ヘッドルーム、対価、経路長、ルート変化、及びＢＧＰ到達可能性からなるグループから選択される、請求項１０に記載の方法。
【請求項１４】
前記ルーティング宛先の場所を決定し、前記利用可能なルートを介した前記ソースから別の宛先へのトラフィックの送信に関連する前記経路特性の測定値に基づいて前記経路特性を推論する、という各ステップを更に含む、請求項１０に記載の方法。
【請求項１５】
前記ルーティング宛先の場所が円交差法により決定され、該円交差法が、
複数のソース場所から前記ルーティング宛先へトラフィックが移動するのに要する時間を測定し、
該時間を距離の等価値に変換し、
前記距離の等価値を円の半径として使用すると共に、前記ソース場所を中心として使用して、複数の交差する円を形成し、
該円の交差から前記ルーティング宛先の物理的な場所を決定する、
という各ステップを含む、請求項１４に記載の方法。
【請求項１６】
前記ソースから他の宛先への前記経路特性の加重平均を前記ルーティング宛先に対する前記他の宛先の物理的な近接性に基づいて決定することにより前記経路特性を推論するステップを更に含む、請求項１０に記載の方法。
【請求項１７】
前記ソースと複数の他の宛先との間のレイテンシを測定し、
前記ルーティング宛先と前記他の宛先との間の物理的な距離を決定し、
該距離の関数として前記レイテンシの測定値の加重平均を計算し、
該加重平均を前記ソースと前記ルーティング宛先との間のレイテンシの概算値として使用する、
という各ステップを更に含む、請求項１０に記載の方法。
【請求項１８】
複数のルートが利用可能なネットワークにおいてソースからルーティング宛先へトラフィックをルーティングするための方法であって、
利用可能なルートの各々毎に、前記ソースから前記ルーティング宛先へのトラフィックのルーティングに関する経路特性の測定値を取得し、
コスト関数を使用して各利用可能なルートに該ルートに関する経路特性の関数としてコストを割り当て、
前記コスト関数により規定される最低コストを有するルートを選択し、
該最低コストのルートに従って前記トラフィックをルーティングする、
という各ステップを有する、トラフィックのルーティング方法。
【請求項１９】
前記最低コストのルートをルータへ伝送するステップを更に含む、請求項１８記載の方法。
【請求項２０】
前記ソースから前記最低コストのルートを介した前記ルーティング宛先へのトラフィックのルーティングを前記ルータに行わせるステップを更に含む、請求項１９に記載の方法。
【請求項２１】
前記経路特性が、レイテンシ、パケット損失、ヘッドルーム、対価、経路長、ルート変化、及びＢＧＰ到達可能性からなるグループから選択される、請求項１８に記載の方法。
【請求項２２】
前記ルーティング宛先の場所を決定し、前記利用可能なルートを介した前記ソースから別の宛先へのトラフィックの送信に関連する前記経路特性の測定値に基づいて前記経路特性を推論する、という各ステップを更に含む、請求項１８に記載の方法。
【請求項２３】
前記ルーティング宛先の場所が円交差法により決定され、該円交差法が、
複数のソース場所から前記ルーティング宛先へトラフィックが移動するのに要する時間を測定し、
該時間を距離の等価値に変換し、
前記距離の等価値を円の半径として使用すると共に、前記ソース場所を中心として使用して、複数の交差する円を形成し、
該円の交差から前記ルーティング宛先の物理的な場所を決定する、
という各ステップを含む、請求項２２に記載の方法。
【請求項２４】
前記ソースから他の宛先への前記経路特性の加重平均を前記ルーティング宛先に対する前記他の宛先の物理的な近接性に基づいて決定することにより前記経路特性を推論するステップを更に含む、請求項１８に記載の方法。
【請求項２５】
前記ソースと複数の他の宛先との間のレイテンシを測定し、
前記ルーティング宛先と前記他の宛先との間の物理的な距離を決定し、
該距離の関数として前記レイテンシの測定値の加重平均を計算し、
該加重平均を前記ソースと前記ルーティング宛先との間のレイテンシの概算値として使用する、
という各ステップを更に含む、請求項１８に記載の方法。
【請求項２６】
複数のルートが利用可能なネットワークにおいてソースからルーティング宛先へトラフィックをルーティングするための方法であって、
利用可能なルートの各々毎に、前記ソースから前記ルーティング宛先へのトラフィックのルーティングに関する経路特性の測定値を取得し、
コスト関数を使用して各利用可能なルートに該ルートに関する経路特性の関数としてコストを割り当て、
前記各ルート上の前記コスト関数を最小化して、該コスト関数により規定される前記トラフィックのルーティングの最低コストを有するルートを識別し、
該最低コストのルートを含むルーティングテーブルを生成する、
という各ステップを有する、トラフィックのルーティング方法。
【請求項２７】
前記ルーティングテーブルをルータへ伝送するステップを更に含む、請求項２６に記載の方法。
【請求項２８】
前記ルートに対する前記ルーティングテーブルの適用を前記ルータに行わせるステップを更に含む、請求項２７に記載の方法。
【請求項２９】
前記経路特性が、レイテンシ、パケット損失、ヘッドルーム、対価、経路長、ルート変化、及びＢＧＰ到達可能性からなるグループから選択される、請求項２６に記載の方法。
【請求項３０】
前記ルーティング宛先の場所を決定し、前記利用可能なルートを介した前記ソースから別の宛先へのトラフィックの送信に関連する前記経路特性の測定値に基づいて前記経路特性を推論する、という各ステップを更に含む、請求項２６に記載の方法。
【請求項３１】
前記ルーティング宛先の場所が円交差法により決定され、該円交差法が、
複数のソース場所から前記ルーティング宛先へトラフィックが移動するのに要する時間を測定し、
該時間を距離の等価値に変換し、
前記距離の等価値を円の半径として使用すると共に、前記ソース場所を中心として使用して、複数の交差する円を形成し、
該円の交差から前記ルーティング宛先の物理的な場所を決定する、
という各ステップを含む、請求項３０に記載の方法。
【請求項３２】
前記ソースから他の宛先への前記経路特性の加重平均を前記ルーティング宛先に対する前記他の宛先の物理的な近接性に基づいて決定することにより前記経路特性を推論するステップを更に含む、請求項２６に記載の方法。
【請求項３３】
前記ソースと複数の他の宛先との間のレイテンシを測定し、
前記ルーティング宛先と前記他の宛先との間の物理的な距離を決定し、
該距離の関数として前記レイテンシの測定値の加重平均を計算し、
該加重平均を前記ソースと前記ルーティング宛先との間のレイテンシの概算値として使用する、
という各ステップを更に含む、請求項２６に記載の方法。
【請求項３４】
複数のルートが利用可能なネットワークにおいてソースからルーティング宛先へトラフィックをルーティングするための、コンピュータにより実施されるシステムであって、
コンピュータシステムと、
該コンピュータシステムに関するプログラミングであって、前記ルートの各々にコストを割り当て、及びコスト関数により規定される最低コストを有するルートを選択するための、プログラミングと
を含む、コンピュータにより実施されるシステム。
【請求項３５】
前記選択されたルートをルータへ伝送するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項３４に記載のシステム。
【請求項３６】
前記ソースから前記選択されたルートを介した前記ルーティング宛先へのトラフィックのルーティングを前記ルータに行わせるための、前記コンピュータシステムに関するプログラミングを更に含む、請求項３５に記載のシステム。
【請求項３７】
前記コストが、該コストが割り当てられるルート上の経路特性の関数である、請求項３４に記載のシステム。
【請求項３８】
前記経路特性が、レイテンシ、パケット損失、ヘッドルーム、対価、経路長、ルート変化、及びＢＧＰ到達可能性からなるグループから選択される、請求項３７に記載のシステム。
【請求項３９】
前記ルーティング宛先の場所を決定し、及び前記利用可能なルートを介した前記ソースから別の宛先へのトラフィックの送信に関連する前記経路特性の測定値に基づいて前記経路特性を推論するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項３７に記載のシステム。
【請求項４０】
複数のソース場所から前記ルーティング宛先へトラフィックが移動するのに要する時間を測定し、
該時間を距離の等価値に変換し、
前記距離の等価値を円の半径として使用すると共に、前記ソース場所を中心として使用して、複数の交差する円を形成し、
該円の交差から前記ルーティング宛先の物理的な場所を決定する
ための、前記コンピュータシステムに関するプログラミングを更に含む、請求項３９に記載のシステム。
【請求項４１】
前記ソースから他の宛先への前記経路特性の加重平均を前記ルーティング宛先に対する前記他の宛先の物理的な近接性に基づいて決定することにより前記経路特性を推論するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項３７に記載のシステム。
【請求項４２】
前記ソースと複数の他の宛先との間のレイテンシを測定し、
前記ルーティング宛先と前記他の宛先との間の物理的な距離を決定し、
該距離の関数として前記レイテンシの測定値の加重平均を計算し、
該加重平均を前記ソースと前記ルーティング宛先との間のレイテンシの概算値として使用する
ための、前記コンピュータシステムに関するプログラミングを更に含む、請求項３４に記載のシステム。
【請求項４３】
複数のルートが利用可能なネットワークにおいてソースからルーティング宛先へトラフィックをルーティングするための、コンピュータにより実施されるシステムであって、
コンピュータシステムと、
該コンピュータシステムに関するプログラミングであって、
利用可能な各ルート毎に、前記ソースから前記ルーティング宛先へのトラフィックのルーティングに関する経路特性の測定値を取得し、
コスト関数を使用して各利用可能なルートに該ルートに関する経路特性の関数としてコストを割り当て、
前記利用可能なルート上の前記コスト関数を最小化し、
該コスト関数の最小化により決定された最低コストのルートに従って前記トラフィックをルーティングする
ための、前記コンピュータシステムに関するプログラミングと
を含む、コンピュータにより実施されるシステム。
【請求項４４】
前記最低コストのルートをルータへ伝送するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項４３に記載のシステム。
【請求項４５】
前記ソースから前記最低コストのルートを介した前記ルーティング宛先へのトラフィックのルーティングを前記ルータに行わせるための、前記コンピュータシステムに関するプログラミングを更に含む、請求項４４に記載のシステム。
【請求項４６】
前記経路特性が、レイテンシ、パケット損失、ヘッドルーム、対価、経路長、ルート変化、及びＢＧＰ到達可能性からなるグループから選択される、請求項４３に記載のシステム。
【請求項４７】
前記ルーティング宛先の場所を決定し、及び前記利用可能なルートを介した前記ソースから別の宛先へのトラフィックの送信に関連する前記経路特性の測定値に基づいて前記経路特性を推論するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項４３に記載のシステム。
【請求項４８】
複数のソース場所から前記ルーティング宛先へトラフィックが移動するのに要する時間を測定し、
該時間を距離の等価値に変換し、
前記距離の等価値を円の半径として使用すると共に、前記ソース場所を中心として使用して、複数の交差する円を形成し、
該円の交差から前記ルーティング宛先の物理的な場所を決定する
ための、前記コンピュータシステムに関するプログラミングを更に含む、請求項４７に記載のシステム。
【請求項４９】
前記ソースから他の宛先への前記経路特性の加重平均を前記ルーティング宛先に対する前記他の宛先の物理的な近接性に基づいて決定することにより前記経路特性を推論するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項４３に記載のシステム。
【請求項５０】
前記ソースと複数の他の宛先との間のレイテンシを測定し、
前記ルーティング宛先と前記他の宛先との間の物理的な距離を決定し、
該距離の関数として前記レイテンシの測定値の加重平均を計算し、
該加重平均を前記ソースと前記ルーティング宛先との間のレイテンシの概算値として使用する
ための、前記コンピュータシステムに関するプログラミングを更に含む、請求項４３に記載のシステム。
【請求項５１】
複数のルートが利用可能なネットワークにおいてソースからルーティング宛先へトラフィックをルーティングするための、コンピュータにより実施されるシステムであって、
コンピュータシステムと、
該コンピュータシステムに関するプログラミングであって、
利用可能な各ルート毎に、前記ソースから前記ルーティング宛先へのトラフィックのルーティングに関する経路特性の測定値を取得し、
コスト関数を使用して各利用可能なルートに該ルートに関する経路特性の関数としてコストを割り当て、
前記コスト関数により規定される最低コストを有するルートを選択し、
該最低コストのルートに従って前記トラフィックをルーティングする
ための、前記コンピュータシステムに関するプログラミングと
を含む、コンピュータにより実施されるシステム。
【請求項５２】
前記最低コストのルートをルータへ伝送するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５１に記載のシステム。
【請求項５３】
前記ソースから前記最低コストのルートを介した前記ルーティング宛先へのトラフィックのルーティングを前記ルータに行わせるための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５２に記載のシステム。
【請求項５４】
前記経路特性が、レイテンシ、パケット損失、ヘッドルーム、対価、経路長、ルート変化、及びＢＧＰ到達可能性からなるグループから選択される、請求項５１に記載のシステム。
【請求項５５】
前記ルーティング宛先の場所を決定し、及び前記利用可能なルートを介した前記ソースから別の宛先へのトラフィックの送信に関連する前記経路特性の測定値に基づいて前記経路特性を推論するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５１に記載のシステム。
【請求項５６】
複数のソース場所から前記ルーティング宛先へトラフィックが移動するのに要する時間を測定し、
該時間を距離の等価値に変換し、
前記距離の等価値を円の半径として使用すると共に、前記ソース場所を中心として使用して、複数の交差する円を形成し、
該円の交差から前記ルーティング宛先の物理的な場所を決定する
ための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５５に記載のシステム。
【請求項５７】
前記ソースから他の宛先への前記経路特性の加重平均を前記ルーティング宛先に対する前記他の宛先の物理的な近接性に基づいて決定することにより前記経路特性を推論するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５１に記載のシステム。
【請求項５８】
前記ソースと複数の他の宛先との間のレイテンシを測定し、
前記ルーティング宛先と前記他の宛先との間の物理的な距離を決定し、
該距離の関数として前記レイテンシの測定値の加重平均を計算し、
該加重平均を前記ソースと前記ルーティング宛先との間のレイテンシの概算値として使用する
ための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５１に記載のシステム。
【請求項５９】
複数のルートが利用可能なネットワークにおいてソースからルーティング宛先へトラフィックをルーティングするための、コンピュータにより実施されるシステムであって、
コンピュータと、
該コンピュータに関するプログラミングであって、
利用可能な各ルート毎に、前記ソースから前記ルーティング宛先へのトラフィックのルーティングに関する経路特性の測定値を取得し、
コスト関数を使用して各利用可能なルートに該ルートに関する経路特性の関数としてコストを割り当て、
前記各ルート上の前記コスト関数を最小化して、該コスト関数により規定される前記トラフィックのルーティングの最低コストを有するルートを識別し、
該最低コストのルートを含むルーティングテーブルを生成する
ための、前記コンピュータに関するプログラミングと
を含む、コンピュータにより実施されるシステム。
【請求項６０】
前記ルーティングテーブルをルータへ伝送するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５９に記載のシステム。
【請求項６１】
前記ルートに対する前記ルーティングテーブルの適用を前記ルータに行わせるための、前記コンピュータシステムに関するプログラミングを更に含む、請求項６０に記載のシステム。
【請求項６２】
前記経路特性が、レイテンシ、パケット損失、ヘッドルーム、対価、経路長、ルート変化、及びＢＧＰ到達可能性からなるグループから選択される、請求項５９に記載のシステム。
【請求項６３】
前記ルーティング宛先の場所を決定し、及び前記利用可能なルートを介した前記ソースから別の宛先へのトラフィックの送信に関連する前記経路特性の測定値に基づいて前記経路特性を推論するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５９に記載のシステム。
【請求項６４】
複数のソース場所から前記ルーティング宛先へトラフィックが移動するのに要する時間を測定し、
該時間を距離の等価値に変換し、
前記距離の等価値を円の半径として使用すると共に、前記ソース場所を中心として使用して、複数の交差する円を形成し、
該円の交差から前記ルーティング宛先の物理的な場所を決定する
ための、前記コンピュータシステムに関するプログラミングを更に含む、請求項６３に記載のシステム。
【請求項６５】
前記ソースから他の宛先への前記経路特性の加重平均を前記ルーティング宛先に対する前記他の宛先の物理的な近接性に基づいて決定することにより前記経路特性を推論するための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５９に記載のシステム。
【請求項６６】
前記ソースと複数の他の宛先との間のレイテンシを測定し、
前記ルーティング宛先と前記他の宛先との間の物理的な距離を決定し、
該距離の関数として前記レイテンシの測定値の加重平均を計算し、
該加重平均を前記ソースと前記ルーティング宛先との間のレイテンシの概算値として使用する
ための、前記コンピュータシステムに関するプログラミングを更に含む、請求項５９に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般にインターネット等の相互接続されたネットワークにおけるルーティングに関し、特に、コスト関数を使用して複数の代替的なルーティングテーブル間で選択を行うことに関する。
【０００２】
【従来の技術】
インターネットプロトコル（ＩＰ）は、アドレス空間を規定する。ＩＰバージョン４（ＩＰｖ４）では、アドレス空間は、［０，２３２］の範囲の全ての整数（約４０億のアドレス）である。インターネット上の複数の「ノード」間には一対一のマッピングが存在する。１つのノードは通常は単一のコンピュータに割り当てられるが、多くの例外が存在する。例えば、インターネット上で単一のノードとして作用する多数のコンピュータが存在する可能性があり、より一般的には、多数のノードとして作用する単一のコンピュータ（すなわち多数のＩＰアドレスが割り当てられたもの）が存在する可能性がある。１つのノードは、データパケットが中間的なノードを通過することなく２つのノード間で移動することが可能である場合に、もう１つの近接する（ａｄｊａｃｅｎｔ）又は「隣接する（ｎｅｉｇｈｂｏｒｉｎｇ）」ノードに結合される。所与のノードにデータパケットを送る際にどの隣接ノードを使用するかを選択するプロセスはルーティングと呼ばれる。特に、経路全体ではなくどの隣接ノードを使用すべきかのみを選択するインターネットプロトコル戦略（ｓｔｒａｔｅｇｙ）は、「ホップ・バイ・ホップ・ルーティング（Ｈｏｐ−Ｂｙ−Ｈｏｐ Ｒｏｕｔｉｎｇ）」と呼ばれる。
【０００３】
到達可能性（ｒｅａｃｈａｂｉｌｉｔｙ）は、ルーティング選択を行う上で最も重要な基準である。自明であるように、あらゆる隣接ノードは互いに到達可能である。一般に、ノードＢがノードＡの隣接ノードである場合、ノードＢはノードＡから到達可能であり、又はノードＢはノードＡの隣接ノードから到達可能である。ノードＢがノードＡの２つ以上の隣接ノード（ノードＢに到達するためにノードＡを使用する隣接ノードを除く）から到達可能である場合には、ノードＡは、各ノードにより提供される経路に基づいて次のホップノードを選択しなければならない。従来、ホップ数で表した自律システム（ＡＳ：Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）経路長が、該選択を行う際に使用される主な特性となる。
【０００４】
あらゆるノードに対する到達可能性その他の経路情報を格納し通信することが技術的に困難であることより、膨大な数のノードを想定して、サブネットワークを使用した収集機構が考案された。サブネット化は、アドレス空間を幾つかのサブネットワーク（アドレスプリフィクスにより識別されるもの）へと分割し、その各々が連続したアドレスブロックを表す。１つのＡＳは、複数のサブネットの集合を含む。かかる各集合は、所与のプリフィクスが１つのＡＳでしか見出すことができないものであるという点で互いに独立している。所与のプリフィクスを含む一意のＡＳは、該プリフィクスにおけるＩＰアドレスの全てにパケットを配送することを責務とする。この概念は、ルーティングの複雑性を低減させるものとなる。これは、各ノードがインターネット上の他のあらゆるノードへの経路を知ることを必要とするのではなく、各ノードのＡＳの「ボーダ（ｂｏｒｄｅｒｓ）」に如何に到達するかを知るだけでよいからである。該ボーダ上のノード（ボーダゲートウェイとしても知られる）は、宛先ＡＳへパケットを配送することになる他のＡＳにおける隣接するボーダノードを選択することを責務とする。ＩＰアドレスを使用する場合とは異なり、ボーダゲートウェイは、全てのＡＳに対する到達可能性その他の経路情報を通信し格納することが可能である。これは、ＡＳ空間が、ＩＰアドレス空間よりも遙かに小さいからである。このボーダゲートウェイノード間の到達可能性及び経路情報を交換するために使用されるプロトコルは、ボーダゲートウェイプロトコル（ＢＧＰ）として知られるものであり、その現行バージョンはＢＧＰバージョン４（ＢＧＰ４）である。
【０００５】
【発明が解決しようとする課題】
ＢＧＰは、インターネット上のルーティングの複雑性を管理可能な程度まで低減させるものであるが、如何なる経路特性がルート選択アルゴリズムにとって利用可能であるべきかを決定する際のトレードオフを必要とするものである。ボーダゲートウェイ間で交換される経路情報には、経路中のＡＳのリストが含まれ、実際に使用される殆どのルート選択アルゴリズムは、通常は最小限のＡＳホップで経路を選択する。経路長（ＡＳホップ数）以外の基準に基づいて選択を行うことは可能であるが、ＢＧＰにより提供される情報からは、最短経路を選択しないだけの十分な正当性は通常は存在しない。
【０００６】
経路長の使用は、経路長が必ずしも性能を表すものとはならないという点で、ヒューリスティックなものである。全てのＡＳが等価なものであり、それ故、所与の宛先ＡＳに到達するために使用した際に同一の欠点に寄与するものである場合には、ＡＳ経路長を最小限にすることが最適なルートを見つけるための正しい戦略であることになる。ＡＳが等価なものでない場合であっても、ルーティングアルゴリズムが経路長以外の経路特性に対するアクセスを有さない場合には、最小限の長さを有する経路を選択することが正当な戦略である。しかし、実験的な証拠により、ＡＳ間に大幅な性能差が存在することが立証された。最小数のＡＳを有する経路は、所与のプリフィクスへ最も早く到達するものとならないことが多い。同様に、ＡＳの違いに起因して、ＡＳ経路長は等しいが性能は等しくない経路が存在することが多い。更なる経路特性を経路選択アルゴリズムに追加する必要があるのは、この違いのためである。
【０００７】
例えば、図１は、５つのＡＳ１０〜１８を示している。同図から分かるように、ＡＳ１１０からＡＳ５ １８まで２つの経路（すなわち、ＡＳ１ １０→ＡＳ２ １２→ＡＳ５ １８、又はＡＳ１ １０→ＡＳ３ １４→ＡＳ５ １８）が存在する。その両方の経路とも、同じＡＳホップ数を有しており、それ故、同じＢＧＰ経路長を有していることに留意されたい。その結果として、ＢＧＰは、該２つの経路を等価なものとみなし、この場合には、単に任意結合分解機構（ａｒｂｉｔｒａｒｙ ｔｉｅ ｂｒｅａｋｉｎｇ ｍｅｃｈａｎｉｓｍ）を採用することによりルートが選択されることになる。また、ＡＳ１１０からＡＳ４ １６まで２つの経路（すなわち、ＡＳ１ １０→ＡＳ２ １２→ＡＳ４ １６、又はＡＳ１ １０→ＡＳ３ １４→ＡＳ５ １８→ＡＳ２ １２→ＡＳ４ １６）が存在することに留意されたい。この場合には、ＢＧＰは典型的には、ＡＳホップ数を最小限にして経路「ＡＳ１ １０→ＡＳ２ １２→ＡＳ４ １６」を選択することになる。しかし、上記で概説した各々の場合、ＢＧＰルート選択は、例えば高レイテンシ（ｈｉｇｈ ｌａｔｅｎｃｙ：長い待ち時間）やパケット損失等に起因して、性能の低下に通ずるものとなり得る。ＢＧＰは、何れかの条件の存在を知るための方法を有しておらず、単に宛先までのＡＳホップ数を最小限にすることによりトラフィックをルーティングするものである。よって、性能その他の経路特性に基づきトラフィックをルーティングする方法が必要とされている。本発明は、かかる必要性並びに本書に記載する他の必要性を満たすものである。
【０００８】
【課題を解決するための手段】
本発明は、多数の経路が利用可能である場合に、性能その他の経路特性をルート選択プロセスに含めることにより、ＢＧＰでは不可能なことを克服してルート選択を最適化するものである。本発明は、１つ又は２つ以上のマルチホームのＡＳ又はその等価物を有するあらゆるネットワークで利用することが可能な性能ベースのルーティングシステム及び方法である。更に、ＡＳから他のＡＳへの結合数が増大して一層多数のルーティング選択肢が利用可能となった場合には、本発明による性能ベースのルーティングは、より一層有利なものとなる。
【０００９】
本発明の一実施形態によれば、複数ルートの任意の組み合わせを使用する場合のコストを記述するコスト関数の使用を介してルーティングを制御する機構が提供される。本発明の別の実施形態によれば、前記コスト関数により規定される複数ルートのより優れた組み合わせを見つけるために前記コスト関数を最小限にするための方法が提供される。本発明の更に別の態様によれば、標準的なＢＧＰと相互に動作する機構が提供される。
【００１０】
例示のため、及び制限を加えることは目的とせず、３つのコンポーネント、すなわち、性能監視及び推論コンポーネント、ルーティング最適化コンポーネント、及びＢＧＰブリッジに関して、本願発明を上位概念で説明する。
【００１１】
性能監視及び推論コンポーネントは、大きな一組のサブネットワークへの利用可能な経路の性能を測定し、該測定値を使用して更に大きな一組のサブネットワークへの全ての利用可能な経路の性能を推論する。これに関連する幾つかの種類の性能測定（レイテンシ及びパケット損失等）が存在する。該性能監視及び推論コンポーネントの出力は、あらゆる宛先に対するあらゆる利用可能な経路についての各種類の性能のテーブルである。
【００１２】
ルーティング最適化コンポーネントは、前記性能監視及び推論コンポーネントにより生成された前記性能テーブル、並びに、何れかの宛先に送られることになるトラフィックの量、各経路で利用可能な容量、及び何れかの経路を使用する際の経済的な対価といった、その他の重要な情報を使用する。該ルーティング最適化コンポーネントは、入力情報に基づいてあらゆるルーティングテーブルにコストを割り当てることができるコスト関数を含む。該ルーティング最適化コンポーネントは、最小化方法論（ｍｉｎｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄｏｌｏｇｙ）を使用して、コスト関数により規定される極めて低いコストを有するルーティングテーブルを見つけだす。該最小化方法論によりどのルーティングテーブルが選択されることになるかを変更するための主な方法は、前記コスト関数を変更することである。ルーティング最適化コンポーネントの出力は、前記最小化方法論により見つけ出されたルーティングテーブルである。
【００１３】
ＢＧＰブリッジは、前記ルーティング最適化コンポーネントにより生成されたルーティングテーブルを取得し、その情報をＢＧＰを使用してルータに通信し、これにより、該ルータが該ルーティングテーブルに従ってトラフィックのルーティングを行うことが確実となる。
【００１４】
本発明の目的は、複数の代替的な経路に関する性能測定に基づいてルーティング決定を行うことにある。
【００１５】
本発明の別の目的は、複数の代替的な経路の動作上の及び／又は経済上の特性に基づいてルーティング決定を行うことにある。
【００１６】
本発明の別の目的は、ルーティングテーブルに関連するコストを決定することにある。
【００１７】
本発明の別の目的は、コストの最小化に基づいてルーティングテーブルを選択することにある。
【００１８】
本発明の別の目的は、１つの宛先に対して多数の経路が利用可能である場合にルーティング決定を最適化することにある。
【００１９】
本発明の別の目的は、最適化されたルーティングテーブルから導出されたルーティング情報をＢＧＰルータへ通信することにある。
【００２０】
本発明の更なる目的及び利点については本明細書の以下の部分で明らかとなる。ここで、その詳細な説明は、本発明に制限を加えることなく、本発明の好適な実施形態を完全に開示することを目的としたものである。
【００２１】
本発明は、本発明の例示を目的とし同様の構成要素に同様の符号を付した図面を参照することにより一層完全に理解されよう。
【００２２】
【発明の実施の形態】
本発明の例示を目的として図面を参照する。本発明は図２及び図２０に関して一般に説明するシステム及び方法で実施されるものである。本書に開示する基本的な思想から逸脱することなく、該システムは、その構成に関し及びその構成要素の細部に関して変更し得るものであり、該方法は、その特定のステップ及びその順序に関して変更し得るものである、ということが理解されよう。
【００２３】
最初に図２を参照する。同図には、本発明による性能ベースのルーティングシステム１００の一好適実施形態の機能ブロック図が示されている。図示の例では、本発明は、性能監視及び推論コンポーネント１０２、ルーティング最適化コンポーネント１０４、及びＢＧＰブリッジコンポーネント１０６を含む。
【００２４】
一般に、性能監視及び推論コンポーネント１０２は、一組のサブネットワークに対して利用可能となる特定経路の性能を測定し、次いで該測定値を使用して一層大きな一組のサブネットワークに対して利用可能となる全ての経路の性能を推論する。監視及び推論コンポーネント１０２により行うことができる性能測定の例としてレイテンシ及びパケット損失が挙げられる（但しこれらには限定されない）。性能監視及び推論コンポーネント１０２は、各宛先に対する各利用可能な経路毎に測定され又は推論された各種の性能のテーブルを生成する。
【００２５】
次いで、ルーティング最適化コンポーネント１０４は、前記性能監視及び推論コンポーネント１０２により生成された性能テーブル（及び随意選択的には更に別の経路特性）を使用して、１つのルーティングテーブルに関する「コスト」を決定する。上述の更に別の経路特性のうち一般に使用される可能性のあるものとして、各宛先に対するトラフィック１０８の量、各経路上の利用可能な容量１１０、何れかの経路を使用することの経済的な対価１１２、及び経路長１１４が挙げられる。トラフィックの種類（例えば「データ」対「ＶｏＩＰ」）をルーティング最適化コンポーネント１０４の入力として使用することさえ可能である。上記の列挙は、全てを包含するものではなく、単なる例示として提供したものである。
【００２６】
性能テーブル及び適当と思われる任意の更なる経路特性に基づき、コスト関数を使用してルーティングテーブルにコストが割り当てられる。次いで、関連する最小化プロセスが実行されて、コスト関数により規定される「低コスト」を有するルーティングテーブルが識別される。該最小化プロセスによりどのルーティングテーブルが選択されることになるかを変更する主な方法がコスト関数の変更であることに留意されたい。ルーティング最適化コンポーネント１０４の出力は、低コストを有するよう最小化プロセスにより見つけ出されたルーティングテーブルである。
【００２７】
ＢＧＰブリッジ１０６は、ルーティング最適化コンポーネント１０４により生成されたルーティングテーブルを取得して、その情報をＢＧＰを使用してルータ１１６へ通信し、これにより、該ルータが該ルーティングテーブルに従ってトラフィックをルーティングすることが確実となる。
【００２８】
ここで、本発明の性能ベースのルーティングシステム１００の上記３つのコンポーネントの各々について一層詳細に説明する。かかるコンポーネントの各々の説明は、本発明を例示するものであって本発明の制限を目的とするものではなく、当業者であれば本書での開示から導出することができる多数の代替的構成及び実施形態が存在する、ということが理解されよう。
１．性能監視及び推論コンポーネント
ＢＧＰはＡＳ間で性能情報を交換しないため、ＢＧＰプロトコルとは別個に、利用可能なＡＳ経路の性能を測定する必要がある。本発明では、性能監視及び推論コンポーネント１０２は、レイテンシ及びパケット損失といった経路特性（一般に性能特性と記述することができる）を測定する。しかし、レイテンシ及びパケット損失は、一例として挙げたものに過ぎず、本発明を制限するものでもなく、またネットワークルーティングに関連する任意の数の経路特性が存在し得る、ということが理解されよう。可能であれば、該測定は、全ての宛先に対する全ての利用可能な経路にわたり実行されるべきであり、またリアルタイムで更新されるべきである。しかし、あまりにも多数の性能測定値を収集することは非現実的となり得るため、性能監視及び推論コンポーネント１０２は、推論方法論を使用して、一組の宛先に対する実際の性能に基づき他の組の宛先に対する性能を推論する。
【００２９】
性能監視及び推論コンポーネント１０２は好適には、ＡＳ内で実行され本発明を使用してルーティングを制御するソフトウェアとして実施される。更に、性能ｎｏ測定は、何れかの隣接するＡＳを使用して何れかの宛先サブネットワークに到達する結果としてＡＳが観測すると考えられる性能を精確に表現するようにＡＳの視点から行うべきである。このため、多数のＡＳが本発明を使用してそれらのルーティングを制御する場合には、性能監視及び推論コンポーネントは、かかるＡＳの各々内から実行されるべきである。
（ａ） 性能の監視
更なる説明のため、ここでレイテンシ及びパケット損失の測定方法について解説する。しかし、他の経路特性を測定するには異なる技術が必要になる可能性があることが理解されよう。
【００３０】
特定のＩＰアドレスに対するラウンドトリップレイテンシ及びパケット損失の両者は、ｐｉｎｇ（周知技術）を使用して測定することができる、ということが当業者には理解されよう。ｐｉｎｇは、インターネット制御メッセージプロトコル（ＩＣＭＰ）エコーメッセージを宛先ホストに送り、該ホストから１つのＩＣＭＰエコー応答を受信するまでに要した時間を計測することによって機能する。該応答が何らかの指定された時間量野の値に受信されなかった場合には、これはパケット損失として扱われる。代替的な技術は、伝送制御プロトコル（ＴＣＰ）セッションを確立するために３方向（ｔｈｒｅｅ−ｗａｙ）ハンドシェイクで使用される同期（ＳＹＮ）パケットと応答（ＡＣＫ）パケットとの間の時間を測定することである。古典的なｐｉｎｇに優るこの技術の利点は、該技術が、性能のより精確な測定値を一般に提供する点にある。これは、ルータ及びホストがＩＣＭＰトラフィックの優先順位を下げる（ｄｅｐｒｉｏｒｉｔｉｚｅ）ことが多いからである。該技術はまた、ネットワーク内の一層高い可視性を提供する。これは、多くのホストが、ＴＣＰコネクションは許容するがＩＣＭＰメッセージは許容せず、又はファイアウォールのためかかるメッセージを受信することができないからである。
【００３１】
ＴＣＰハンドシェイク法の変形例により更に高い可視性を提供することができる。ファイアウォールによっては、ＴＣＰハンドシェイクにおける最初のＳＹＮパケットをブロックすることにより、外部ホストがＴＣＰセッションを開始するのを防止する。しかし、かかるファイアウォールは通常は、内部ホストが外部とのコネクションを開始することを許容し、このため、ＡＣＫパケットが該ファイアウォールを通過することを許容する。ＡＣＫパケットを期待していないホスト（すなわち該ＡＣＫパケットに対応するＳＹＮパケットを送っていないホスト）にＡＣＫパケットが送られた場合には、該ホストは一般に、該ＡＣＫパケットが無効であることを示すリセット（ＲＳＴ）パケットで応答することになる。この挙動を使用して、ＡＣＫパケットとＲＳＴパケットとの間の時間を測定することにより、ラウンドトリップレイテンシを決定することができる。しかし、この技術は、全ての宛先に対してうまく機能するものではなく、ネットワークによっては、期待しないＡＣＫパケットをそれがホストに到達する前に破棄する「ステートフル（ｓｔａｔｅｆｕｌ）」ファイアウォールによって保護されたものがある。ウェブサーバといった周知のＴＣＰポートでのコネクションをいとわずに許容するマシンの場合、ＳＹＮ ｐｉｎｇは、最も効果的なものであり、かかる測定値を取得するのに好適な方法である。
【００３２】
上述の測定技術は、ネットワーク中のホストがＴＣＰ／ＩＰプロトコルを使用することを前提としたものである。しかし、他のプロトコルが開発された場合には、宛先に対するレイテンシ及びパケット損失を確立するための匹敵する方法が存在するはずである、ということが理解されよう。更に、かかる測定を行うための使用可能な他の適当な方法が存在し、本発明は上述の例により与えられる方法に限定されるものではない、ということが理解されよう。
【００３３】
上述したような性能その他の経路特性は、一般に、特定のネクストホップＡＳにより提供される経路を使用して特定のＩＰアドレスをプロービングすることにより、測定されることになる。しかし、インターネット上でのルーティングは、ＩＰアドレスの範囲であるサブネットワーク（プリフィクスとしても知られる）の細分性（ｇｒａｎｕｌａｒｉｔｙ）で指定される。それ故、本発明をインターネット上でのルーティングに適用するためには、サブネットワークに到達するために所与のネクストホップＡＳにより提供される経路の特性を記述する必要がある。一例として、但し制限を目的とせず、その実施のための好適な方法は、所与のサブネットワーク内の特定の代表的なＩＰアドレスに対する個々の測定値を平均化して該サブネットワークに対する性能を記述することである。サブネットワークに対する性能その他の特性を規定するための代替的な方法が存在するが、該サブネットワーク内の特定のＩＰアドレスに対する測定値を平均化するのが好適である。これは、特定のサブネットワークに対する優れたルートとは、該サブネットワーク内の特定のアドレスに対する優れた性能を提供するルートであるからである。
（ｂ） 性能の推論
様々な理由のため、利用可能なあらゆるｐｉｎｇ法を使用してもプロービングすることができない多数の宛先が存在する可能性がある場合であっても、プロービングすることができる宛先の数は依然として膨大である。例えば、使用中の約８万のプリフィクスが存在する場合には、行うことができる測定の数は、「８万」×「該測定を行うことができるＡＳの数」となる。所与のサブネットワークに到達するために各々の隣接するＡＳにより提供される経路の測定をリアルタイムで行うことができるのが理想的である。しかし、極めて多くの測定を行う場合には、大量のリソースが必要となる。更に、かかるサブネットワーク中の多くのホスト（かかるサブネットのプロービングを実際に受けるもの）は、かかる頻繁なプロービングを疑わしいものとして取り扱う可能性がある。また、サブネットワークの出力トラフィックの全てを隣接するＡＳ上へシフトさせることなく該隣接するＡＳにより提供される経路上で該サブネットワーク中の１ノードに対する性能を監視することは技術的に困難である。このため、全ての利用可能な経路上の多数のサブネットワークに対する性能を、一層少数の経路上の遙かに少数のサブネットワークに対する測定を使用して推論することができることが有用である。
【００３４】
行う必要のある測定の数を低減させるために、性能監視及び推論コンポーネント１０２は、幾つかの組をなすサブネットワークに対する性能を幾つかのより少数のサブネットワークに対する測定を使用して推論する性能推論方法論を用いる。ここで、２つのサブネットワークに対する性能は、その各サブネットワークに到達するために使用される経路間の差が小さい場合には同様であるべきである、ということに留意されたい。例えば、２つの異なるＩＰアドレスに到達するための経路がその端部近傍の分岐を除いて同一である場合には、それら２つのＩＰアドレスに対する性能の差は、宛先ホストが該経路の一部であると考えた場合、異なる経路の部分上の性能差に起因するものでなければならない。一方、該２つの異なるアドレスに対する経路が分岐する際、該２つのアドレスに対する性能の相関関係はゼロに近づくはずである。この原理を用いると、地理的な意味でもトポロジ的な意味でも互いに近いアドレスは類似した性能を有するはずである。更に、サブネットワークはＩＰアドレスの集合を表すものであるため、同様の推論がサブネットワークにも当てはまる。しかし、「地理的又はトポロジ的なサブネットワークの場所」と称した場合には、これは、該サブネットワーク中の各ホストの全般的な地理的又はトポロジ的な場所を意味するものである、ということが理解されよう。
【００３５】
ＩＰアドレスのトポロジ的な場所は、標準的な「ｔｒａｃｅｒｏｕｔｅ」ツール（宛先に到達するために選択された経路上の全てのルータホップの識別を試行するもの）を使用して決定することができる場合が多い。しかし、ｔｒａｃｅｒｏｕｔｅは、不完全な情報を提供することが多く、これは特に多くのルータがｔｒａｃｅｒｏｕｔｅに応答しないためである。
【００３６】
ＩＰアドレスひいてはサブネットワークの精確なトポロジ的な場所を決定するのは困難であるが、それにもかかわらず、おおよその地理的な場所は、異なるソースから同一のＩＰアドレスへのレイテンシ測定の交差（ｉｎｔｅｒｓｅｃｔｉｏｎ）を介して識別することができる。例えば、図３を参照すると、単一のソース２００から１つのＩＰアドレスまでの観測されたレイテンシは、該ソース２００と該宛先ＩＰアドレス２０２との間の距離の近似値へと変換することができる。該概算距離Ｄは、観測されたレイテンシ（図示の例では５３ｍｓ）をパケットの速度（単位：距離／時間）の概算値と組み合わせることにより決定される。例えば、光ファイバケーブルでは、パケットは、真空中の光の速度のおおよそ２／３の速度で伝搬することが分かっている。この速度は、物理的な媒体の変化、ネットワーク経路中の湾曲の程度、及びルータその他のデバイスにより加えられるレイテンシを含む、幾つかの要因の影響を受けることになる。これらの変動が存在するものと仮定すると、分析を介してではなく統計的な観測を介して平均速度を決定するのがより信頼性が高い。しかし、この速度の上限は容易に指定することが可能である。これは、パケットが高速よりも速く移動することはできないからである。このため、１つのサブネットワークに対するレイテンシは、やはり該サブネットワーク中の幾つかの組をなす代表的なＩＰアドレスに対するレイテンシの平均として規定される。
【００３７】
ソースと宛先との間の距離が概算されると、該距離に等しい半径と該ソースの地理的な場所に配置された中心とを有する円を規定することができる。これを図４に円２０４で示す。この場合、ソース２００は該円の中心にあり、該円の半径は概算された距離Ｄである。該概算された距離Ｄが実際の距離の上限であることが分かっている場合には、宛先は該円内に存在しなければならない。他のソースから同一の宛先までの距離の概算値を使用して更なる円を生成することができる。例えば、図５は、宛先２０２までの距離の概算値Ｄ１，Ｄ２，Ｄ３をそれぞれ有する３つのソース２００，２０６，２０８を示している。それらソースの場所及び距離の概算値を使用して、図６に示すように交差する円２０４，２１０，２１２を規定することができる。それら距離の概算値の全てが実際の距離の上限である場合には、宛先はそれら円の全ての交差部分内に位置していなければならない。これもまた図６に示されている。同図において、宛先２０２は、円２０４，２１０，２１２の交差部分内に位置している。円２０４，２１０，２１２の直径は本例では比例して描かれていないことに留意されたい。
【００３８】
各距離の上限が近接する結果として、交差領域が小さなものとなり、このため宛先の地理的な場所が一層精確に特定されることになる、ということに留意されたい。更に、より多くのソース（特に宛先に対して地理的に異なるソース）を追加することにより、交差領域が更に縮小して特定の精度が増大することになる。更に、より多くの測定を行うと共に最低のレイテンシの測定を選択することにより、交差領域のサイズが更に縮小されることになる。更に、この方法は、特定のＩＰアドレス及びサブネットワークの両者に（各場合に適当な距離を用いることにより）使用することが可能である。また、地理的な場所を識別することを目的としたこれらレイテンシ測定に用いるソースは、性能その他の経路特性を監視するために使用されるソースと同一である必要はない、ということに留意されたい。性能その他の経路特性を監視するために収集されるレイテンシは、かかる測定値を使用してルーティングの決定を行うＡＳの視点から収集される必要があり、任意のＩＰアドレス又はサブネットワークの地理的な場所は、該ソースに関係するものではなく、このため任意のＡＳの視点から決定することができる。
【００３９】
各宛先の地理的な場所を概算した後、複数対をなす宛先の全ての対の間の距離の概算値を容易に計算することができる。２つの宛先の間の距離が極端に短い場合には、該２つの宛先のうちの一方に対してのみ性能を測定し、他方の宛先がそれと同じ性能を有するものと仮定することで、妥当な精度を得ることが可能である。この推論の精度は、２つのポイントが互いにトポロジ的及び地理的に如何に近接しているかによって決まる。しかし、２つのポイントが地理的に極めて近接している場合には、それらはトポロジ的に近接している可能性が高い。このため、該推論の信頼性は、該２つのポイント間の距離が短くなるにつれて増大するはずである。この観測を使用し、幾つかのサンプル宛先に関する性能測定値を組み合わせて重み付けした平均（すなわち加重平均）を求めることが可能であり、これは、単一の目標宛先に対する性能を一層精確に概算するものとなる。各性能測定値に割り当てる重みは、目標宛先とサンプル宛先との間の距離の逆元（ｉｎｖｅｒｓｅ）となる。該距離の逆元は、性能測定値が目標宛先に対する未測定の性能と同一であるという相対的な信頼性を記述するものであるため、各性能測定値の重み付けを行うために使用される。
【００４０】
例えば、図７を参照すると、３つのプリフィクスＰＲ１，ＰＲ２，ＰＲ３が存在する場合、及びレイテンシ又は他の経路特性の測定が特定のネクストホップＡＳ２を使用してソースＡＳ１からプリフィクスＰＲ１，ＰＲ２の各々に対して行われた場合には、ＡＳ２により提供される経路を使用したプリフィクスＰＲ３に対するレイテンシ又は経路特性を推論することが可能である。Ｌ（ＡＳ＿Ｘ，ＡＳ＿Ｙ，ＰＲ＿Ｚ）は、ＡＳ　ＡＳ＿Ｙにより提供される経路が使用される場合におけるＡＳ ＡＳ＿ＸからプリフィクスＰＲ＿Ｚへのレイテンシを表すものとする。また、Ｄ（ＰＲ＿Ｘ，ＰＲ＿Ｙ）は、プリフィクスＰＲ＿ＸとプリフィクスＰＲ＿Ｙとの間の距離を表すものとする。次式を使用して、ネクストホップＡＳとしてＡＳ２を使用した場合のＡＳ１からＰＲ３へのレイテンシを推論することが可能である。
【００４１】
【数１】
2004507917.tif 000003
【００４２】
この例では、２つのプリフィクスのみに対する測定値が使用されるが、実際には、多数の測定値を使用して１つの推論を行うべきである。また、該推論方程式において使用される測定は全て、同一のネクストホップＡＳを使用して行われたものでなければならず、ＡＳは、推論される経路中のネクストホップと一致しなければならない、ということに留意されたい。該例では、ＡＳ２が測定及び推論の両方のためのネクストホップＡＳである。この例は、ソースＡＳから宛先へトラフィックを送るための経路が１つしか存在しないものと仮定している。しかし、１つのＡＳは多数のＡＳに結合することが可能であり、それ故、２つ以上のネクストホップＡＳが宛先へのトラフィックの送信に利用可能となる可能性がある。このため、更なる明瞭化のために、Ｌ（ＡＳ１，ＡＳ３，ＰＲ３）を推論する場合には、測定もまたネクストホップとしてＡＳ３を使用しなければならないことになる。同様の計算を複数のネクストホップＡＳの各々毎に行うことになる。また、本書で説明する平均化技法は例示のみを目的としたものであり、非平均化技法を含む他の技術を使用することも可能である、ということが理解されよう。更に、上記の例で距離の逆元を使用して各項の重み付けを行う代わりに、経路上で共有されているルータの数により測定した共有トポロジの量を使用して各項を重み付けすることも可能である
この技術が任意の所与の宛先に対する性能を精確に概算するものとなるという保証は存在しないが、その有効性は、実際の測定値の集合を使用して容易に決定することができる。かかる測定値を使用する場合には、任意の所与の精度にとって必要となる、推論値に対する測定値の比を決定するのが直接的である。例えば、幾つかのランダムに選択された一部の測定値を「サンプル対象外（ｏｕｔ−ｏｆ−ｓａｍｐｌｅ）」として扱い、これを残りの「サンプル対象（ｉｎ−ｓａｍｐｌｅ）」の測定値により推論しなければならないものとすることができる。「サンプル対象外」データの相対的な大きさは、誤差の平方自乗平均（ＲＭＳ）が許容可能なしきい値内にくるまで小さくすることができる。
【００４３】
更に、経路特性を推論するための上述の技術は好適なものであるが、以下に示すような他の方法（但しこれらには限定されない）で推論を行うことが可能であることが理解されよう。
１．複数組のプリフィクスを監視し、次いで各組中の全てのプリフィクスを同じ様式で扱う。
２．類似性に基づきプリフィクスを集め、かかる集めたプリフィクスの全ての組を同じ様式で扱う。
３．類似した特性を有するプリフィクスをサブセットへと分け、該サブセットを同じ様式で扱う。
４．性能、地理的場所、及びその他の相関的な因子といった（但しこれらに限定されない）類似性の基準に基づきプリフィクスを複数の組に配置し、該組のプリフィクスを同じ様式で扱う。
【００４４】
１つの組は、単一のプリフィクス、１グループのプリフィクス、互いに地理的に近接した２つの組の組み合わせ、ＡＳに対して同様の性能を経験する２つの組の組み合わせ、及び複数の組からなる複数の組等とすることが可能であることに留意されたい。
【００４５】
最後に、本書に記載の経路特性を推論するための技術に対する更なる改善として次の事項が挙げられる（但しこれらには限定されない）。
１．経路特性が推論されることになる宛先のＡＳ経路と同じＡＳ経路にわたり性能測定を行う。
２．ｔｒａｃｅｒｏｕｔｅにより決定されるようなトポロジを推論技術に追加する。この場合、各測定値は、測定される宛先と推論が行われる宛先との両方に共通の経路の長さにより重み付けすることができる。
（ｃ） 円の交差
推論プロセスは、異なるＡＳ経路の性能の変化を考慮するために、頻繁に実行する必要があるが、サブネットワークの地理的な場所は、あまり頻繁には変化しない。このため、サブネットワークの地理的な場所を決定するためのプロセスは、あまり頻繁に行う必要がない。しかし、該プロセスを実行する場合には、妥当に短い時間で実行する必要がある。該プロセスの計算上の動作の殆どは、各ソースから宛先への距離を表す一組の円の交差を見出すことを含み、このため、該交差の発見を効率的に行わなければならない。
【００４６】
任意の２つの円の交差は、単純な代数から計算することが可能であり、それら円が実際に交差するものと仮定すれば、２つの交差点により記述することができる。一組の円の交差は２つの段階で行うことができる。第１段階で、交差の２つの点を全ての対をなす円について計算することができる。何れかの円がそれよりも大きな円の内側に完全に含まれている場合には、該大きな円が破棄される。第２段階で、前記第１段階による全ての点を検査して、それらの点があらゆる円内に含まれるか否かを判定する。任意の２つの円の交差は、一定の時間で実行され、Ｎ個の円からなる複数の対を形成するのにＮ（Ｎ−１）／２の方法が存在し、その各々により２つの点が生成される。よって、第１段階は２Ｎ（Ｎ−１）／２＝Ｎ（Ｎ−１）個の点を生成する。第２段階はそれらの各点と各円との間の一定時間の比較（ｃｏｎｓｔａｎｔ ｔｉｍｅ ｃｏｍｐａｒｉｓｏｎ）を行う。第１段階からのＮ（Ｎ−１）個の点が存在するため、Ｎ×Ｎ（Ｎ−１）の比較が存在することになり、従って、該比較は、Ｏ（Ｎ３）時間で実行される。よって、プロセス全体は、Ｏ（Ｎ２＋Ｎ３）＝Ｏ（Ｎ３）ステップで実行される（Ｎは円の個数）。
【００４７】
ソースの数が多い場合には、一組の円を交差させるためのＯ（Ｎ３）のプロセスはあまりにも遅いものとなり得る。しかし、線形時間で実行される直接的な近似を使用して該交差プロセスをスピードアップさせることが可能である。１つの組からの任意の２つの円を交差させた後、それらの交差領域の境界を形成する矩形を構成することができる。任意に選択された該矩形と残りの円との交差は、新たな矩形で表すことができる。このステップは、残りの全ての円について繰り返すことができ、この場合、各ステップで生成された矩形は次のステップでの交差のために使用される。交差の各々を記述するために生成された矩形が、交差領域を完全に包囲する場合には、最後のステップで生成された最後の矩形が各円の領域の交差を完全に包囲することになる。２つの円の間の第１の交差は、一定時間で実行される。同様に、残りのＮ−２ステップの各々は、１つの円と１つの矩形との間の一定時間の交差となる。よって、プロセス全体はＯ（Ｎ）ステップで実行される（Ｎは円の個数）。
【００４８】
３つの互いに交差する円３００，３０２，３０４に適用される上述の「矩形による近似」プロセスの一例を図８Ａないし図８Ｄに示す。最初に、図８Ａに示すように、円３００，３０２といった２つの円の交差３０６が求められることになる。次いで、その交差領域を、（好適には図８Ｂに示すような矩形形状の）交差オブジェクト３０８により取り囲むことができる。該交差オブジェクト３０８は、該交差を取り囲む最小の境界を表すものとなるべきである。図８Ｃも参照すると、概算された交差が、交差オブジェクト３０８の内側のハッチングされた領域３１０で示されている。ここで、第３の円３０４が描かれた場合における該円３０４と交差オブジェクト３０８との交差が、ハッチングされた領域３１２で示されている。
【００４９】
よって、上述の方法は、１つの交差オブジェクトと以前の複数の交差について概略的に述べたものであることが理解されよう。次いで、交差オブジェクトは、後続の円又は該後続の円を表すオブジェクトと交差することになる。交差オブジェクトは好適には、上述のような矩形形状のものであるが、代替的に他の形状（例えば多角形）にすることも可能である。この方法は、精度の代償の元に線形時間で実行する計算技術を用いることより、計算上の複雑性を低減させ、計算速度を増大させるものである。
２．ルーティング最適化コンポーネント
図２を再び参照する。ルーティング最適化コンポーネント１０４は、好適には、ルート選択に関連し得るあらゆるデータに基づいてルーティングテーブルを生成するソフトウェアから構成される。該ルーティング最適化コンポーネント１０４は、性能監視及び推論コンポーネント１０２により提供される経路特性のテーブル、、並びに、各プリフィクスに送られるトラフィック１０８の量、各ネクストホップＡＳに対して利用可能となる容量１１０、及び任意のネクストホップＡＳを使用する対価１１２といった他の関連情報にアクセスすることができる。トラフィック１０８は、Ｎｅｔｆｌｏｗ（Ｒ）及びその類を使用して容易に得ることができる。「パイプサイズ」又は容量１１０は、システム設計情報から得ることができる。対価１１２は、バックボーンプロバイダその他との契約その他のサービス合意から得ることができる。特定の経路の特性に関して他の情報が存在しない場合には少なくとも経路長１１４（単位：ＡＳホップ）を知ることが有用であり、該経路長は、全ての経路に関してルーティング最適化コンポーネント１０４にも提供される。この情報は、ＢＧＰから容易に得ることができる。同様に、所与のサブネットワークが隣接するＡＳから到達可能であるか否かがルーティング最適化コンポーネント１０４に提供されなければならない。これは、特定のルートを選択プロセスから除外できるようにするためである。他の変数（例えばトラフィックの種類）がルート選択プロセスに関係すると思われる場合には、該変数もまたルーティング最適化コンポーネント１０４に対して利用可能にするべきである。ルーティング最適化コンポーネント１０４に対してデータを利用可能にする多くの方法が存在するが、最も一般的に適当できる解決策はデータベースにデータを格納することである、ということが当業者には理解されよう。
【００５０】
利用可能な経路情報の全て、及びその他の関連情報が与えられた場合、ルーティング最適化コンポーネント１０４の目的は、できる限り「良い」ルーティングテーブルを生成することである。しかし、「良い」ルーティングとは、本発明のユーザによって異なって定義され得る。例えば、あるユーザは、レイテンシよりもパケット損失に重きを置く可能性があり、かかるユーザは、パケット損失を最小限にする（たとえそれがレイテンシの増大を意味するものとなろうとも）ルーティングテーブルの生成をルーティング最適化コンポーネント１０４に行わせることを望むことになろう。またユーザによっては、ルート選択の対価に重きを置く可能性があり、かかるユーザは、結果的にパケット損失及びレイテンシが生じることになる（それが大して補償する必要のないものであることを意味する場合）ルーティングテーブルを好むことになろう。ルート選択プロセスにおける異なる嗜好を考慮するために、ルーティング最適化コンポーネント１０４は、ルーティングテーブルのコスト関数をユーザが指定することを可能にする。該コスト関数は、あらゆるルーティングテーブルを評価し、該ルーティングテーブルに非負の実数値のコストを割り当てる（この場合、より小さいコストはより優れたルーティングを意味するものと解釈される）ことができなければならないものである。コスト関数は、経路特性又は任意の他の関連情報を使用してコストを決定することが可能である。
【００５１】
この発明のユーザは、任意のコスト関数を自由に規定することが可能であり、ルーティング最適化コンポーネントの責務は、該コスト関数により規定される小さなコストを有するルーティングテーブルを見出すことにある。考え得るルーティングテーブルの膨大な空間が与えられた場合には、ルーティング最適化コンポーネントは、全ての探索ではなく最小化アルゴリズムを使用して、小さなコストを有するルーティングテーブルを見出す。
（ａ） ルーティングテーブル
ルーティングテーブルは、任意の所与のプリフィクスに到達するためにどのネクストホップＡＳを使用することになるかを示す行列である。各ソースＡＳ毎の行、及び各宛先プリフィクス毎の列が存在する。任意のルーティング行列Ｒについて、表記Ｒ［ｉ，ｊ］は、宛先ｊに到達するためにソースＡＳｉにより使用されるネクストホップＡＳを示すものとなる。本発明が、単一のＡＳについてのルーティングしか制御しないものである場合には、該行列には一行しか存在しないことになる。しかし、本発明の利益の一つは、本発明が複数のソースＡＳにわたりルーティングを最適化して該ＡＳがより協働的にインターネットのリソース（利用可能な帯域幅等）を使用することを可能にすることにある。
【００５２】
例えば、図９は、８つのＡＳ（ＡＳ１ ４００，ＡＳ２ ４０２，ＡＳ３ ４０４，ＡＳ４ ４０６，ＡＳ５ ４０８，ＡＳ６ ４１０，ＡＳ７ ４１２，ＡＳ８ ４１４）が存在するネットワーク構成の一例を概略的に示している。ＡＳ６ ４１０はプリフィクスＰＲ１，ＰＲ２を含むものとして示され、ＡＳ７ ４１２は、プリフィクスＰＲ３を含むものとして示され、ＡＳ８ ４１４は、プリフィクスＰＲ４を含むものとして示されている。しかし、１つのネットワークは、図示するよりも少数の又は多数のＡＳを含むことが可能であり、各ＡＳは、少なくとも１つのプリフィクスを含むものとなる、ということが理解されよう。また、ＡＳ１ ４００が幾つかの隣接するＡＳを有していることを図９が示していることに留意されたい。ここで、ＡＳ４００は、「高度にマルチホーム化された（ｈｉｇｈｌｙ ｍｕｌｔｉ−ｈｏｍｅｄ）」ＡＳと呼ばれるものであり、すなわち、多数の他のＡＳに直接結合されたものである。
【００５３】
該８つのＡＳの各々を１つのソースＡＳとみなすものと仮定して、この構成に関する考え得るルーティングテーブルを図１０に示す。しかし、図１０に示すルーティングテーブルは単なる一例であり、利用可能な多数の代替的な経路に起因して使用することが可能な多数の他のルーティングテーブルが存在する、ということが理解されよう。
【００５４】
ＡＳ１ ４００に焦点を当てる。図９は、ＡＳ１ ４００からＡＳ６ ４１０又はＡＳ７ ４１２又はＡＳ８ ４１４への複数のルートが利用可能であることも示している。これは、図１０に示すルーティングテーブルの第１行が、図１１ないし図１４に示すような複数の代替的なエントリを有することができることを意味している。例えば、図１１では、プリフィクスＰＲ１，ＰＲ２（両方ともＡＳ６ ４１０内に存在する）へのトラフィックは、ネクストホップＡＳとしてのＡＳ２ ４０２を介してルーティングされる。又は、両方のプリフィクスへのトラフィックは、図１２に示すようにＡＳ３ ４０４を介してルーティングされる。ＡＳ２ ４０２及びＡＳ３ ４０４の間の結合（ｔｉｅ）が性能に基づくものである場合には、該結合は任意に分断することができる。代替的には、ネットワーク上の当該部分における負荷を平衡化させることにより該結合を分断することができる。例えば、図１３のルーティングテーブルでは、プリフィクスＰＲ１，ＰＲ２へのトラフィックは、ＡＳ２ ４０２及びＡＳ３ ４０４間でそれぞれ分割される。しかし、負荷の平衡化は、性能に基づきルート間に結合が存在する場合に限定されるものではなく、特定のルート上の負荷又は代替的にはヘッドルームを一般にルーティングを最適化するために追加の因子とすることが可能である、ということが理解されよう。
【００５５】
ここで図１４を参照する。同図には、図９に基づく更なる代替的なルーティングテーブルが示されている。この場合には、ＡＳ５ ４０８が、プリフィクスＰＲ４へトラフィックをルーティングするためのネクストホップＡＳとして次善のものと仮定されている。図１４のルーティングテーブルでは、プリフィクスＰＲ４へトラフィックをルーティングするためのネクストホップＡＳとしてＡＳ４ ４０６が選択されている（すなわち、ＡＳ８ ４１４に対して直接ではなくＡＳ７ ４１２を介してルーティングする）。上記のルーティングテーブルは、単なる例示であり、図９に示すネットワーク構成のために多数の代替的なルーティングテーブルを生成することが可能である、ということが当業者には理解されよう。
【００５６】
したがって、多数の代替的なルーティングテーブルを用いてソースＡＳから宛先へトラフィックを送ることが可能であることが理解されよう。ルーティングテーブルに関する上記説明を心に留めつつ、ルーティング行列に関するコストを決定するためのコスト関数について説明することとする。
（ｂ） コスト関数
コスト関数は、あらゆるルーティング行列の使用コストを決定する。ルーティング行列中に何行が存在するかにかかわらず、ルーティング行列に同一のコスト関数を適用することが可能であることに留意されたい。換言すれば、同一のルーティング最適化コンポーネントを使用するソースＡＳの個数が増大した場合にコスト関数を修正する必要がない。
【００５７】
ルーティングに最も関係する項の幾つかを含むコスト関数の一例を次式で示すことができる。
【００５８】
Ｃ（Ｒ）＝ｋ１・レイテンシ（Ｒ）＋ｋ２・ヘッドルーム（Ｒ）＋ｋ３・対価（Ｒ）
ここで、Ｒはルーティング行列、Ｃは該ルーティング行列のコスト、ｋ１，ｋ２，ｋ３は該項の相対的な重要性を便利に調整するための係数である。
【００５９】
その第一項であるレイテンシ（Ｒ）の一例は次式で示すことができる。
【００６０】
【数２】
2004507917.tif 000004
【００６１】
ここで、トラフィック［ｉ，ｊ］は、ＡＳｉからプリフィクスｊへ送られるトラフィックの量を表し、レイテンシ［ｉ，ｊ，Ｒ［ｉ，ｊ］］は、ＡＳｉからネクストホップＡＳ Ｒ［ｉ，ｊ］を使用してプリフィクスｊに到達する際に期待されるレイテンシの量を表している。これがレイテンシ（Ｒ）に関する良い選択である理由は、該式が、１バイトあたりの平均レイテンシを表すことにあり、このため、その小さな値は小さな平均レイテンシを表すものとなる。
【００６２】
第二項であるヘッドルーム（Ｒ）は、任意の経路を介してルーティングされたトラフィックの量が利用可能な容量よりも大きい場合に直面するキュー効果（ｑｕｅｕｉｎｇ ｅｆｆｅｃｔｓ）を指すものである。経路全体に沿った精確な容量を知ることは困難であるが、ソースＡＳとそれに隣接するＡＳとの間の容量は入手できるはずである。キュー効果は、極めて精確なキューモデルを使用して記述することが可能であるが、本発明の目的のためには、単純な個々の線形関数では不十分である。かかる関数は、容量に対するトラフィックの比が小さい場合にはキュー効果は無視できるが該比が大きい場合にはキュー効果は重大なものとなるという事実を考慮すべきである。例えば、以下の関数は、全容量の７０％をしきい値として使用している。この場合には、ヘッドルーム（Ｒ）の項は、図１５に示すように重要なものとなる。
【００６３】
ヘッドルーム［Ｒ］＝Ｉｆ［トラフィック対容量比［ｉ，ｋ］＜．７，
ｔｈｅｎ ｋＳｍａｌｌ・トラフィック対容量比［ｉ，ｋ］，
ｅｌｓｅ ｋＬａｒｇｅ・トラフィック対容量比［ｉ，ｋ］
ここで、
【００６４】
【数３】
2004507917.tif 000005
【００６５】
であり、ｋＳｍａｌｌは該式中の他の項の大きさに対して小さな数であり、ｋＬａｒｇｅは該式中の他の項の大きさに対して大きな数である。このヘッドルーム関数を使用したキューの考慮は、利用可能な容量に比べてトラフィックの量が大きい場合に、ヘッドルームが該式中で最も重要な因子となるが、その比が小さい場合には、該項は他の因子に比べて小さくなる、という利点を有するものである。ｋＳｍａｌｌ及びｋＬａｒｇｅの値並びにしきい値レベルは任意に選択されることに留意されたい。別の重み及びしきい値も併用することが可能である。これは、ヘッドルーム項を重要であるとみなすべき点まで容量に対するトラフィックの比が増大した際に単にコスト関数を急速に上昇させることが目的だからである。
【００６６】
対価項Ｐｒｉｃｅ（Ｒ）は、ルーティング行列に従ってトラフィックをルーティングするために要する単なるドル量である。これは、各ソースＡＳと各ネクストホップＡＳとの間の経済的な契約、並びにルーティング行列により各ソースＡＳが各ネクストホップＡＳへ送ることになるトラフィックの量によって決まる。
【００６７】
コスト関数に現れ得る幾つかの他の項が存在する。例えば、パケット損失は、ルート選択に極めて関係するものであり、レイテンシに極めて類似した態様でコスト関数に追加することが可能なものである。有用となり得る項の次に明らかな例がルート変更項であり、この場合、ルート変更（Ｒ）＝［ルーティング行列が実際に使用される場合に変更されることになるルートの数］ である。ルート変更項は、不必要な変更を回避するため、又は時間と共に発生する共振の防止を助けるために有用なものである。
（ｃ） 最小化アルゴリズム
コスト関数の最小化のために使用することができる幾つかの周知のアルゴリズムが存在する。かかる各アルゴリズムは、速度、最適度、及びリソース要件の間で異なるトレードオフを提供するものである。その幾つかの例が、遺伝的アルゴリズム（ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ）、焼きなまし法（Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ）、及び傾斜探索法（ｇｒａｄｉｅｎｔ ｓｅａｒｃｈ）である。遺伝的アルゴリズムは、ルーティングテーブルのサイズを考えると、おそらくあまりにも多大なメモリを要するため実施できないであろう。焼きなまし法は、遺伝的アルゴリズムと比べると大してメモリを要するものではないが、変化するネットワーク状況に応じるために新たなルーティングテーブルを生成することが必要となる速度を考えると、おそらく遅すぎるものとなる。傾斜探索法は、多大なメモリを要するものではなく、焼きなまし法と比べて非常に高速ではあるが、ローカルミニマ（ｌｏｃａｌ ｍｉｎｉｍａ）に捕捉される可能性があるため、この解決策は次善のものとなることが多い。
【００６８】
多数の技術を使用して、コスト関数により規定される小さなコストを有するルーティング行列を見出すことができることは明らかであるが、好適なアルゴリズムは、ローカルミニマから逃れるための上昇移動（ｕｐ−ｈｉｌｌ ｍｏｖｅｓ）を時折伴う、驚くほど単純なバイアス式ランダムウォーク（ｂｉａｓｅｄ ｒａｎｄｏｍ ｗａｌｋ）である。より詳細には、該アルゴリズムは、開始ルーティング行列をランダムに生成することにより機能する。該アルゴリズムは次いで、何れかのソースＡＳｉ及び何れかの宛先プリフィクスｊをランダムに選択することにより何回かの反復へと進行する。該アルゴリズムは、何らかの確率で、新たなネクストホップＡＳをＲ［ｉ，ｊ］に割り当て、又は最低のコストを生じさせるネクストホップＡＳをＲ［ｉ，ｊ］に割り当てる。最低のコストを生じさせるネクストホップＡＳを見出すために、該アルゴリズムは、全ての代替的なネクストホップＡＳにわたって反復し、それらをＲ［ｉ，ｊ］に割り当て、次いで新たなルーティング行列についてコスト関数を評価する。傾斜探索法と同様に、このアルゴリズムはローカルな移動しか行わない。しかし、このアルゴリズムは、ランダムな移動を時折行うため、容易にローカルミニマに捕捉されることはない。
【００６９】
バイアス式ランダムウォークアルゴリズムの実際上の問題は、各反復において、ネクストホップＡＳをランダムに割り当てない限り、各ネクストホップＡＳを選択する度にコスト関数の評価を行わなければならないことである。コスト関数の計算が低速である場合には、これは、妥当な時間内に計算することができる該アルゴリズムの反復の数を制限するものとなる。これは問題である。なぜなら、該アルゴリズムが多数の反復を実行できない場合には、最後の反復時のルーティング行列があまり最適でないものとなるからである。評価の各ステージで情報をキャッシュして該情報を更新するだけにすることにより、コスト関数の評価をスピードアップさせることができる場合が多い。
【００７０】
例えば、上述したようなレイテンシ及びヘッドルーム項を有する次式のコスト関数について考察する。
【００７１】
Ｃ（Ｒ）＝ｋ１・レイテンシ（Ｒ）＋ｋ２・ヘッドルーム（Ｒ）
あるルーティング行列Ｒ０（Ｒ０［ＡＳ１，ＰＲ１］＝ＡＳ２、Ｃ（Ｒ０）＝Ｃ０）が存在するものと仮定する。Ｒ１［ＡＳ１，ＰＲ１］＝ＡＳ３であることを除き、Ｒ１をＲ０と同一に構築する。新たなＲ１にコスト関数を単に適用する場合よりも遙かに迅速にＣ（Ｒ１）を計算することが可能である。コスト関数の定義より、Ｃ（Ｒ０）＝ｋ１・レイテンシ（Ｒ０）＋ｋ２・ヘッドルーム（Ｒ０）、及びＣ（Ｒ１）＝ｋ１・レイテンシ（Ｒ１）＋ｋ２・ヘッドルーム（Ｒ１）となる。レイテンシ項のスピードアップは、ｋ１・レイテンシ（Ｒ１）＝ｋ１・レイテンシ（Ｒ０）−レイテンシ［ＡＳ１，ＰＲ１，Ｒ０［ＡＳ１，ＰＲ１］］＋レイテンシ［ＡＳ１，ＰＲ１，Ｒ１［ＡＳ１，ＰＲ１］］となることの観測から得られる。よって、以前のレイテンシ項「レイテンシ（Ｒ０）」を単にキャッシュすることにより新たなレイテンシ項を計算することが可能である。
【００７２】
ヘッドルーム項は、それよりも僅かに複雑なものとなる。これは、非線形のキュー効果によるものである。しかし、各隣接するＡＳに送られるトラフィックの量を追跡するために１つの行列を使用する場合には、ヘッドルーム項もまた迅速に計算することができる。隣接トラフィック＿Ｒ０が、あるＡＳからその他のＡＳに送られたトラフィックの量を示す行列である場合には、隣接トラフィック＿Ｒ１は次式で定義することができる。
【００７３】
隣接トラフィック＿Ｒ１［ＡＳ１，ＡＳ２］
＝隣接トラフィック＿Ｒ０［ＡＳ１，ＡＳ２］−トラフィック［ＡＳ１，ＰＲ１］
更に、
隣接トラフィック＿Ｒ１［ＡＳ１，ＡＳ３］
＝隣接トラフィック＿Ｒ０［ＡＳ１，ＡＳ３］−トラフィック［ＡＳ１，ＰＲ１］
他の全てのＡＳの場合には、
隣接トラフィック＿Ｒ１［ｉ，ｋ］＝隣接トラフィック＿Ｒ０［ｉ，ｋ］
となる。隣接トラフィック＿Ｒ１行列からヘッドルームを計算するのは容易である。以前のヘッドルーム項は、数４からトラフィック対容量比を計算するが、隣接対トラフィック行列を使用して数５からその値を計算することが可能である。
【００７４】
【数４】
2004507917.tif 000006
【００７５】
【数５】
2004507917.tif 000007
【００７６】
この方法は、特定のタイプのコスト関数の場合にはうまく機能しないが、コストが、ちょうど各変数によるコストに対する寄与の総和となる場合には、
コスト（Ｒ１）＝コスト（Ｒ０）−コスト寄与（旧値）＋コスト寄与（新値）
と言える。これらの個々の寄与が計算の速いものである場合には、変化する変数が少数であると仮定すれば、旧コストから新コストを見出すのもまた速くなる。
（ｄ） 多数のソースＡＳ
既述のように、本発明は、多数のソースＡＳを有するシステムのためのルーティングテーブルを最適化するために使用することができる。かかるルーティングテーブルの一例を図１０に示す。多数のソースＡＳを有するシステムを最適化することにより生成される該ルーティングテーブルは、ルーティング決定を別個に行うことにより生成されたルーティングテーブルよりも潜在的に一層最適なものとなる。例えば、本発明の最適化アルゴリズムは、複数のソースＡＳの全てからのトラフィックが如何なる経路の利用可能な容量をも超えないように各ソースＡＳにルートを割り当てることができる。しかし、ルーティング決定が別個に行われる場合には、ソースＡＳは、特定の経路の容量が他のソースのトラフィックにより既に消費されている場合であっても、該経路に沿ってトラフィックをルーティングしてしまう可能性がある。しかし、該ルーティング最適化アルゴリズムの１つの実例（ｉｎｓｔａｎｃｅ）が幾つかのソースＡＳのためのルートを選択する場合に、かかるソースＡＳは、ルーティング決定を受信するために該ルーティング最適化アルゴリズムと連絡することができないと機能しなくなる可能性がある。該最適化アルゴリズムは、ルーティングを集中管理化することにより障害発生の可能性が追加されることに加えて、ルーティング行列中の行数が非常に大きくなると非常に低速化し得る。
【００７７】
幾つかのソースＡＳのためのルーティングを最適化するために、本発明は、ルーティング行列の区画化を行って、各部分を平衡して解決することができるようにする。図１６は、図１０のルーティングテーブルの一例を示している（楕円は各区画を示している）。ルーティング最適化アルゴリズムの各実例は、ルーティング行列全体を使用するが、その行列中の幾つかのエントリを修正することしか許容されない。各ソースＡＳは、そのソースＡＳに対応する行中の任意の要素を修正することが許容されるアルゴリズムの一実例を実行する。また、任意のソースＡＳ中に含まれるプリフィクスに対応する列中の任意の要素を修正することが許容されるアルゴリズムの「中央の（ｃｅｎｔｒａｌ）」実例が存在する。行列のうち、ソースＡＳで実行中のアルゴリズムの実例が修正を行うことが許容された部分は、該行列のうち、中央アルゴリズムが修正を行うことが許容された部分と重複することに留意されたい。しかし、行列のうち各ソースＡＳで実行中のアルゴリズムにより修正できる部分間には重複は存在しない。
【００７８】
アルゴリズムの中央の実例は、各ソースＡＳからルーティング行列の複製を定期的に取り出し、及びそのルーティング行列の複製を各ソースＡＳに送らなければならない。アルゴリズムの中央の実例は、幾つかのソースＡＳからルーティング行列の複製を取得する場合に、該ルーティング行列の特定のエントリをそれ自体のルーティング行列にコピーする。詳細には、アルゴリズムの中央の実例は、ソースＡＳに対応する行中のエントリであって他のソースＡＳに含まれるプリフィクスに対応する列中に存在しないエントリをコピーする。ソースＡＳで実行中のアルゴリズムの実例は、中央アルゴリズム実例からルーティング行列の複製を受信すると、特定のエントリをそれ自体のルーティング行列にコピーする。ソースＡＳで実行中のアルゴリズムの実例は、該ソースＡＳに対応しない全ての行からのエントリの全てをコピーする。該ソースＡＳに対応する行から、該アルゴリズムの実例は、他のソースＡＳに含まれるプリフィクスに対応する全ての列からの全てのエントリをコピーする。
３．ＢＧＰブリッジコンポーネント
この時点で、ソースＡＳ中のルーティング最適化コンポーネント１０４により行われた決定を該ＡＳ中の各ルータに伝達する必要がある、ということが理解されよう。これは、ＢＧＰブリッジコンポーネント１０６を使用して達成される。
【００７９】
動作時に、ルーティング最適化コンポーネント１０４は、該ＡＳに対応するルーティング行列中の行をＢＧＰブリッジ１０６に送る。該ＢＧＰブリッジ１０６は、ＥＢＧＰを使用して、隣接するＡＳの各々、並びに該ＡＳ内のルートリフレクタとピアになる（ｐｅｅｒ）、ルーティングサーバである。該ルーティングサーバは、ＢＧＰブリッジ１０６が全てのＢＧＰビュー（ｖｉｅｗｓ）をルーティング最適化コンポーネント１０４に通信することを可能にし、更にルーティング最適化コンポーネント１０４がルーティングテーブルをＢＧＰブリッジ１０６に通信することを可能にする、非ＢＧＰ双方向通信チャネルをルーティング最適化コンポーネント１０４に含めるよう修正される。随意選択的に、ＢＧＰブリッジ１０６にＩＢＧＰで通信を行わせるよう修正することも可能である。ＢＧＰブリッジ１０６は、隣接するＡＳから受信した経路、並びにルーティング最適化コンポーネント１０４から受信したルーティングテーブルに基づき、任意の所与のプリフィクスに到達するためにどのネクストホップを使用するかを選択する。殆どの環境では、ＢＧＰブリッジ１０６は、ルーティング最適化コンポーネント１０４により指定されたネクストホップを選択することになる。しかし、ＢＧＰブリッジ１０６は、隣接するＡＳとピアであるため、ルーティング最適化コンポーネント１０４により指定されたルートが（おそらくは該ルートの使用中止の結果として）無効であることを学ぶことが可能である。ルーティング最適化コンポーネント１０４により指定されたルートが使用できない場合には、ＢＧＰブリッジ１０６は、隣接するＡＳから受信した情報に基づき標準的なＢＧＰ経路選択アルゴリズムを使用して経路選択を行い、その情報をルーティング最適化コンポーネント１０４へ伝送することになる。該選択は、ＥＢＧＰを使用してルートリフレクタへ通信され、該ルートリフレクタは、その決定をＩＢＧＰを使用してＡＳ内の他のルータの全てに通信する。
ＰＮＡＰ内での配置
以上、本発明を一般にＡＳに関して（特にマルチホーム化されたＡＳに関して）説明してきた。本発明はまた、プライベートネットワークアクセスポイント（ＰＮＡＰ）（すなわち高度にマルチホーム化されたＡＳ）を用いたネットワークに関連して使用するのに特に適したものである。一般的に言えば、ＰＮＡＰは、２つの二分体（ｈａｌｖｅｓ）から構成されるものと考えることができる。一方の二分体は顧客に接続され、他方の二分体はＮＳＰ（すなわちネットワークサービスプロバイダ）に接続される。次いで該ＮＳＰが宛先に接続され、該宛先は、該ＮＳＰの顧客又は他のＰＮＡＰの顧客とすることが可能である。例えば、図１７は、複数のＮＳＰにより複数のバックボーンＢ１〜Ｂｎを介してインターネット５０６に接続された第１ＰＮＡＰ５０２及び第２ＰＮＡＰ５０４を有する相互接続ネットワーク５００の概要を示す説明図である。各ＰＮＡＰには、それを顧客側ＣＳと複数のバックボーンに接続されたプロバイダ側ＰＳとに分割する垂直方向の破線が記載されている。図示の例の場合、ＰＮＡＰのプロバイダ側はバックボーンＢ１〜Ｂｎを介して互いに接続され、次いで該バックボーンＢ１〜Ｂｎがインターネット５０６に接続されている。２つのＰＮＡＰしか示していないが、１つ又は他の任意数のＰＮＡＰがネットワーク中に存在することが可能である、ということに留意されたい。
【００８０】
図示を単純化するために、ＰＮＡＰ５０２の顧客側に接続された２つの顧客５０８，５１０、及びＰＮＡＰ５０４の顧客側に接続された２つの顧客５１２，５１４しか示していない。しかし、典型的にはより多くの顧客が、それらＰＮＡＰの顧客側に接続されることになる、ということが理解されよう。顧客５０８，５１０は、両方のＰＮＡＰの顧客側に接続されて示されており、よって「マルチホーム化されている」とみなされる、ということに留意されたい。しかし、顧客は、代替的に、１つのＰＮＡＰのみに接続すること、又は任意数のＰＮＡＰに同時に接続されることが可能である。顧客５０８，５１０がインターネット５０６へのリンク５１６，５１８に接続されて示されていることに留意されたい。これもまた「マルチホーム化された」構成であるとみなされる。しかし、顧客がマルチホーム化されている必要はないことが理解されよう。
【００８１】
上述のように、ＰＮＡＰのプロバイダ側は、ＮＳＰにより提供される複数のバックボーンに接続される。次いでこれらのバックボーンがインターネット５０６の構造の大部分を形成し、該インターネット５０６に宛先５２０，５２２といったインターネットユーザが接続される。図の単純化のために、かかる２つの宛先しか示していないが、任意数の宛先が存在することが可能である。ＮＳＰは、これらバックボーン上でＰＮＡＰを介して該ＮＳＰ間でトラフィックを交換することはない、ということに留意されたい。バックボーンＢ１〜Ｂｎを提供するＮＳＰ間のトラフィック交換は、パブリック又はプライベートピアリング（ｐｅｅｒｉｎｇ）ポイント（図示せず）で行われる。例えば、顧客５０８は典型的には、そのトラフィックをＰＮＡＰ５０２を介してその顧客側からプロバイダ側へとルーティングすることになる。次いで該ＰＮＡＰ５０２は、該顧客から、バックボーンＢ１〜Ｂｎのうちの１つを介して、別のＰＮＡＰ上の宛先への経路、又は非ＰＮＡＰの宛先（例えば宛先５２０）への経路を選択することになる。
【００８２】
トラフィックをＰＮＡＰの顧客から宛先へルーティングするには、該ＰＮＡＰにおける１つ又は２つ以上のルータが、該宛先へのネクストホップＡＳを指定するルーティングテーブルを有していなければならない、ということが理解されよう。ここで図２を再び参照する。既述のように、ＢＧＰブリッジ１０６は、ルーティング最適化コンポーネント１０４からルータ１１６へルーティング情報をＢＧＰ互換形式で通信する。本発明がＰＮＡＰで実施される場合にはルータ１１６は該ＰＮＡＰ中に存在することになることが理解されよう。また、図示の構成では、ルーティングテーブルの如何なる変更もＢＧＰブリッジ１０６によりＰＮＡＰ中のあらゆるルータへ伝送することが可能である、ということに留意されたい。また、ＢＧＰブリッジ１０６が該情報をあらゆるＰＮＡＰ中のあらゆるルータに伝送することも可能である。
【００８３】
これは、米国特許第６，００９，０８１号においてルーティングテーブルが伝送される態様とは異なるものであることに留意されたい。該システムでは、各ＰＮＡＰは一意のＡＳを有しており、１つのＰＮＡＰ中の全てのルータは、互いに通信し、ＰＮＡＰと同じＡＳを有しており、各バックボーンが一意のＡＳを有している。ルートリフレクタは、ルートの全てを照合し、ポリシーを適用し、及びフィルタリングされた組をなすルートを前記適用されたポリシーに基づきＰＮＡＰ中の全てのルータに伝送するために使用される。しかし、本発明では、ルートリフレクタは必要なく、その代わりに（必要であれば）、ＢＧＰブリッジ１０６を各コアルータ又はエッジルータに論理的に結合させてルートを直接伝送することができる。該コアルータ及びエッジルータは、単純にパケットを転送し、ポリシー決定は行わない。ルーティング最適化コンポーネント１０４が失敗した場合には、ＢＧＰブリッジ１０６が既存のルーティングテーブルを使用して処理を続行することになる。
【００８４】
ＢＧＰブリッジ１０６とＰＮＡＰ中のルータとの間のインタフェイスの更なる解説のため、コアルータ及びボーダルータが使用される拡張されたルータ構成６００の一例を図１８に示す。図１８に示す例では、一対のＢＧＰブリッジ１０６ａ，１０６ｂが冗長性を持たせるためにルーティング最適化コンポーネント１０４に接続される。次いで該ＢＧＰブリッジ１０６ａ，１０６ｂがスイッチ６０２ａ，６０２ｂに接続され、次いで該スイッチが複数のコアルータ６０４１〜６０４ｎに接続され、次いで該コアルータの各々がＮＳＰルータ６０６１〜６０６ｎに接続される。更に、ボーダルータ６０８ａ，６０８ｂがスイッチ６０２ａ，６０２ｂに接続され、及び該ボーダルータ６０８ａ，６０８ｂに顧客６１０１〜６１０ｎが接続される。
【００８５】
動作時には、ＢＧＰブリッジ１０６ａ，１０６ｂは、通常のＢＧＰピアリングセッションを介してＮＳＰルータ６０６から宛先への経路を取得する。次いで、ＢＧＰブリッジ１０６ａ，１０６ｂは、該情報を既述の最適化のためにルーティング最適化コンポーネント１０４へ通信する。該最適化の後、ルーティング最適化コンポーネント１０４が、経路選択を決定するために、各宛先プリフィクス毎にルーティングテーブルをＢＧＰブリッジ１０６に通信する。該ルーティング最適化コンポーネント１０４が何らかの理由により動作不能となった場合には、ＢＧＰブリッジが、受信した最後のルーティングテーブル並びにＮＳＰから受信した動的な情報に基づいて経路選択の決定を行うことになる。
【００８６】
ボーダルータ６０８は、スイッチ６０２を介してコアルータ６０４に接続され、ＢＧＰブリッジ１０６とピアになる。コアルータ６０４もまた、ＢＧＰブリッジ１０６とピアになる。コア／ボーダルータとＢＧＰブリッジ１０６との間のピアリングは、ＩＢＧＰを介したものとなり、一方、ＮＳＰルータ６０６とＢＧＰブリッジ１０６との間の通信にはＥＢＧＰが使用される。トラフィックの転送の決定は、ＢＧＰブリッジ１０６から単一の経路を取得するボーダルータ６０８により行われる。該ボーダルータと同じ単一経路を取得するコアルータ６０４は、ＮＳＰルータ６０６へトラフィックを転送する。
【００８７】
ＢＧＰブリッジへルーティングテーブルを通信することにより、ルーティング最適化コンポーネント１０４は、ルーティングを行う上で大きなフレキシビリティを有するものとなり、例えば、サービスの最適なレベル又は量に基づいてルーティング決定を考慮することが可能となる（但しこれには限定されない）、ということに留意されたい。
【００８８】
ここで図１９を参照する。同図には、本発明をＰＮＡＰにおいて如何に実施することができるかを更に示すために、ルータ構成７００の更に一般的な例が示されている。この場合には、図１８に示すコア及びボーダルータが省かれている。その代わりに、ＢＧＰブリッジ１０６は、ＩＢＧＰを使用してスイッチ７０２を介してエッジルータ７０４１〜７０４ｎとピアになっている。ＢＧＰブリッジ１０６はまた、ＥＢＧＰを使用してＮＳＰルータ７０６及び顧客７０８とピアになっている。顧客のピアリングは、該顧客がＢＧＰ互換ルータを有している場合にのみ可能となり、この場合には、顧客によるルーティング決定のためにルーティング情報を顧客に提供することができる、ということに留意されたい。またＢＧＰブリッジは、それが認知しているネットワークに関する全ての情報を全てのピアに送ることはない、ということに留意されたい。その代わりに、顧客のルートのみがＮＳＰルータに送られる。ＮＳＰのルートも送られた場合には、ＰＮＡＰを介してＮＳＰ間にトラフィックが不意に通過する可能性がある。
【００８９】
よって、ＢＧＰブリッジ１０６は、ＮＳＰのルータから全ての利用可能な経路に関するプリフィクスを受信し、その情報をルーティング最適化コンポーネント１０４へ通信する、ということが分かる。次いで、ルーティング最適化コンポーネント１０４が、パス選択の決定のためにＢＧＰブリッジにルーティングテーブルを通信することにより、経路選択に影響を与える。
【００９０】
ＰＮＡＰにおいて本発明を実施することの更なる特徴は、性能測定値の取得に関するものである。既述のように、レイテンシは、特定のルートの性能を決定する際の重要な因子であり、既述のようにｐｉｎｇを使用するといった、レイテンシを決定するための幾つかの方法が存在する。しかし、ＰＮＡＰは、多数のバックボーンに接続することができるため、特定のバックボーン上でレイテンシの測定を行うことができる必要がある。これを実施するための１つの方法として、ｐｉｎｇでネクストホップＡＳを指定してＩＰの「ルーズ・ソース・ルーティング」と呼ばれる機能を使用することが挙げられる。しかし、ルーズ・ソース・ルーティングは、一様にサポートされるものではない。ここで図２０を参照する。代替的な方法は、アドレス指定可能なデバイスを、特定のバックボーンプロバイダに固有のアドレスと共に、各バックボーン接続のＰＮＡＰ側の端部に配置することである。例えば、図２０に示すように、ＰＮＡＰ１ ８００ 及び ＰＮＡＰ２ ８０２ は、第１プロバイダにより確立されたバックボーンＢ１と第２プロバイダにより確立されたバックボーンＢ２とを介して互いに接続される。第１のアドレス指定可能なデバイス８０４は、バックボーンＢ１のプロバイダに固有のアドレスを使用してＰＮＡＰ２ ８０２ に配置される。同様に、第２のアドレス指定可能なデバイス８０６は、バックボーンＢ２のプロバイダに固有のアドレスを使用してＰＮＡＰ２ ８０２ に配置される。次いで、ＰＮＡＰ１及びＰＮＡＰ２からのレイテンシ測定を行うために、各々のアドレス指定可能なデバイスを、それぞれの関連するバックボーン上でプロービングすることができる。また、既述の円交差及び推論方法を使用して、プロービングできない特定の宛先に対するレイテンシを推論することも可能である、ということに留意されたい。したがって、本方法は、インターネット上のトラフィックのルーティングを最適化するものであることが分かる。ＰＮＡＰを含めてＡＳを用いたネットワークに関して本発明を説明してきたが、本発明はあらゆるデータ通信ネットワークに適用できることが当業者には理解されよう。また、本書での議論は、ＡＳからプリフィクスへのトラフィックのフローに焦点を絞ったものであるが、本書に記載の技術は、ネットワーク上のあらゆるポイント間のトラフィックフローに適用できることが理解されよう。更に、本書に記載の本発明は、ネットワーク上に問題が存在するか否かを判定するためのネットワーク監視ツールとして使用できることが理解されよう。各性能監視及び推論コンポーネントは、ネットワーク上の他の各ポイントのための検査ステーションであり、ルーティング最適化コンポーネントは、その情報を使用して、ネットワークトラフィックフロー及び該トラフィックを特定のルート上に送る際のコストを監視することができる。よって、特定のルートに関する相対的に高いコストは、ネットワーク上の問題の指示子として使用することができる。
【００９１】
本方法及びシステムは、好適には、関連するソフトウェア、ハードウェア、通信インタフェイス等を使用して本書に記載した機能を実行する従来のコンピュータシステムを使用して、コンピュータにより実施されるものとなる、ということが理解されよう。当業者には理解されるように、本書に記載の本発明を実施するための実際のコードは、従来のプログラミング技術を使用して様々なプラットフォーム用に書くことが可能である。したがって、かかるコードの詳細については本書では解説しないこととする。
【００９２】
上記説明は、多数の特殊性を含むものであるが、それらは、本発明の範囲を制限するものと解釈されるべきではなく、本発明の現時点での好適な実施形態の単なる例示を提供するものである。本発明の範囲は、特許請求の範囲及びその法的な等価物によって決定されるべきである。したがって、本発明の範囲は、当業者にとって自明となる他の実施形態を完全に包含するものであり、よって、本発明の範囲は、特許請求の範囲以外の何ものによっても制限されるものではない。該特許請求の範囲における単数形式の用語は、「唯一」を（その旨を明示しない限り）意図したものではなく、「１つ又は２つ以上」を意図している。上記の好適な実施形態の構成要素に対する構造的、化学的、及び機能的な等価物であって当業者に既知であるもの全てを特許請求の範囲に包含させることが意図されている。更に、本発明により解決することが求められる課題を特許請求の範囲に含めるために装置又は方法が各々の課題又はあらゆる課題に取り組む必要はない。更に、本開示における要素、部品、又は方法ステップは、それらが特許請求の範囲に明示的に記載されているか否かにかかわらず公に提供することを意図したものではない。特許請求の範囲に記載する要素は、該要素が「〜のための手段」なる表現を用いて明確に記載されていない限り、合衆国法典第３５編第１１２条第６段落の規定の下で解釈されるべきではない。
【図面の簡単な説明】
【図１】多数のＡＳを有するネットワークの概要図である。
【図２】本発明による性能ベースのルーティングシステムの機能ブロック図である。
【図３】単一のソースから単一の宛先へのレイテンシ測定値の物理的距離への変換を示す説明図である。
【図４】レイテンシ及び図３に示す距離測定値から導出された地理的領域の決定を示す説明図である。
【図５】多数のソースから単一の宛先へのレイテンシ測定値の物理的距離への変換を示す説明図である。
【図６】本発明による円交差位置特定（ｃｉｒｃｕｌａｒ ｉｎｔｅｒｓｅｃｔｉｏｎ ｌｏｃａｔｉｎｇ）技法を示す説明図である。
【図７】本発明による推論技法を示す説明図である。
【図８Ａ】線形時間で実行される近似を使用する、図６に示す円交差位置特定技法の代替的な実施形態を示す説明図である。
【図８Ｂ】線形時間で実行される近似を使用する、図６に示す円交差位置特定技法の代替的な実施形態を示す説明図である。
【図８Ｃ】線形時間で実行される近似を使用する、図６に示す円交差位置特定技法の代替的な実施形態を示す説明図である。
【図８Ｄ】線形時間で実行される近似を使用する、図６に示す円交差位置特定技法の代替的な実施形態を示す説明図である。
【図９】高度にマルチホーム化されたＡＳを有するネットワークを示す概要図である。
【図１０】図９に示すネットワーク構成に関するルーティングテーブルの一例である。
【図１１】図９に示すネットワーク構成における単一のソースＡＳに関するルーティングテーブルの一例である。
【図１２】図１１に示すルーティングテーブルの第１の代替例である。
【図１３】図１１に示すルーティングテーブルの第２の代替例である。
【図１４】図１１に示すルーティングテーブルの第３の代替例である。
【図１５】本発明によるヘッドルーム関数（ｈｅａｄｒｏｏｍ）関数の一例のパラメータを示すグラフである。
【図１６】最適化のために区分化された図１０のルーティングテーブルを示す図である。
【図１７】インターネットに結合された２つのＰＮＡＰ及び２つのマルチホーム化されたカスタマと相互接続されたネットワークを示す概要図である。
【図１８】本発明を関連して用いることができるコア及びボーダを使用したルータ構成の一例を示すブロック図である。
【図１９】本発明を関連して用いることができるエッジルータを使用したルータ構成の一例を示すブロック図である。
【図２０】２つの相互接続されたＰＮＡＰ及びアドレス指定可能な装置を、特定のバックボーンをプロービングするためのバックボーンプロバイダと共に示す概要図である。
【符号の説明】
１００　　性能ベースのルーティングシステム
１０２　　性能監視及び推論コンポーネント
１０４　　ルーティング最適化コンポーネント
１０６　　ＢＧＰブリッジコンポーネント
１０８　　トラフィック
１１０　　容量
１１２　　対価
１１４　　経路長
１１６　　ルータ
【図２】
2004507917.tif 000008
【図３】
2004507917.tif 000009
【図５】
2004507917.tif 000010
【図１５】
2004507917.tif 000011
【図１７】
2004507917.tif 000012
【図１８】
2004507917.tif 000013
【図１９】
2004507917.tif 000014
【国際公開パンフレット】
2004507917.tif 000015
2004507917.tif 000016
2004507917.tif 000017
2004507917.tif 000018
2004507917.tif 000019
2004507917.tif 000020
2004507917.tif 000021
2004507917.tif 000022
2004507917.tif 000023
2004507917.tif 000024
2004507917.tif 000025
2004507917.tif 000026
2004507917.tif 000027
2004507917.tif 000028
2004507917.tif 000029
2004507917.tif 000030
2004507917.tif 000031
2004507917.tif 000032
2004507917.tif 000033
2004507917.tif 000034
2004507917.tif 000035
2004507917.tif 000036
2004507917.tif 000037
2004507917.tif 000038
2004507917.tif 000039
2004507917.tif 000040
2004507917.tif 000041
2004507917.tif 000042
2004507917.tif 000043
2004507917.tif 000044
2004507917.tif 000045
2004507917.tif 000046
2004507917.tif 000047
2004507917.tif 000048
2004507917.tif 000049
2004507917.tif 000050
2004507917.tif 000051
2004507917.tif 000052
2004507917.tif 000053
2004507917.tif 000054
2004507917.tif 000055
2004507917.tif 000056
2004507917.tif 000057
2004507917.tif 000058
2004507917.tif 000059
2004507917.tif 000060
2004507917.tif 000061
2004507917.tif 000062
2004507917.tif 000063
2004507917.tif 000064
2004507917.tif 000065
2004507917.tif 000066
2004507917.tif 000067
2004507917.tif 000068
2004507917.tif 000069
2004507917.tif 000070
2004507917.tif 000071
【国際調査報告】
2004507917.tif 000072