(57)【要約】ネットワーク内でトラフィックのルーティングを管理する方法およびシステムは、「最適ルート」選択プロセスをイネーブルするために、ネッワークのトポロジカルなアドレス空間マップを展開させる。ネットワークは、複数のピアリングパートナーに接続されたバックボーンから構成される。ネットワークモニタトラフィック上のポイントが動く。中央設備は、ネットワーク内のトラフィックおよびルートを解析し、インテリジェントルーティング管理を実行する。インテリジェントルーティング管理は、トラフィックがネットワーク上の好適なルートにより適切にルーティングされ、非能率的なルーティングを避けることを保証する。インテリジェントルーティング管理はまた、ネットワークのアドレス空間マップの精度をさらに向上させるために、ネットワークに導入される新しいルートを選択する。【選択図】図２Ｂ
2004508743.tif 000002
【特許請求の範囲】
【請求項１】
バックボーンおよび複数のピアリングパートナーを含むネットワークにおいて信号をルーティングする方法であって、各ピアリングパートナーは該バックボーンに接続され、該方法は、
該ネットワークのアドレス空間マップを展開させるステップであって、該アドレス空間マップは、該ネットワークのトポロジカルな領域と特定のセットの信号アドレスとを関連付ける、ステップと、
該バックボーン上の信号をルーティングするために該アドレス空間マップを用いるステップと
を包含する、方法。
【請求項２】
前記信号は、コールドポテトルーティングを用いて前記バックボーン上でルーティングされる、請求項１に記載の方法。
【請求項３】
前記コールドポテトルーティングは、前記バックボーン上の信号を該信号のアドレスに対応する前記ネットワークの前記トポロジカルな領域に最も近い該バックボーンの接続に搬送する、請求項２に記載の方法。
【請求項４】
前記ピアリングパートナーは、ホットポテトルーティングを用いて信号を前記バックボーンにルーティングする、請求項１に記載の方法。
【請求項５】
前記ホットポテトルーティングは、信号を該信号のアドレスに対応する前記ネットワークの前記トポロジカルな領域に最も近い前記バックボーンの接続上に配置する、請求項４に記載の方法。
【請求項６】
前記信号をルーティングするためにアドレス空間マップを用いるステップは、
ルートのためのルート選好を前記ネットワークに導入するステップと、
前記アドレス空間マップに従って該ネットワークの複数のトポロジカルな領域にわたって集合するルートを非集合化するステップと
をさらに包含する、請求項１に記載の方法。
【請求項７】
複数の入力ポイントを介してバックボーンに接続された複数のネットワークを有するシステムのアドレス空間マップを用いてルーティングを変更する方法であって、該方法は、
該複数のネットワークから到着する複数のメッセージの該入力ポイントをモニタリングするステップと、
該複数のメッセージ入力ポイントとそれらに関連したメッセージソースアドレス範囲とを相関させて、該システムのアドレス空間マップを展開させるステップと、
変更されたルーティングをインプリメントするために該アドレス空間マップを用いるステップと
を包含する、方法。
【請求項８】
前記変更されたルーティングをインプリメントするためにアドレス空間マップを用いるステップは、
第１のパスから到着する第１のソースアドレス範囲からのメッセージの量が、第１の閾値量を超えると判定すると、該第１のパスを介して移動するように、すべてのメッセージを該第１のソースアドレス範囲内の宛先アドレスに好んで選ぶステップをさらに包含する、請求項７に記載の方法。
【請求項９】
前記変更されたルーティングをインプリメントするためにアドレス空間マップを用いるステップは、
第１のパスが選好されなかったと判定し、さらに該第１のパスから到着する該第１のソースアドレス範囲からのメッセージの量が、第２の閾値量を超えると判定すると、該第１のソースアドレス範囲に関連した発行されたルートを非集合化するステップをさらに包含する、請求項８に記載の方法。
【請求項１０】
前記第１のソースアドレス範囲は、同一のインターネットプロトコルアドレスおよびマスクに対応するアドレスの群である、請求項９に記載の方法。
【請求項１１】
前記第１の閾値は、前記第１のソースアドレス範囲からのメッセージの総量のうち予め設定された割合である、請求項９に記載の方法。
【請求項１２】
前記第２の閾値は、前記第１のソースアドレス範囲からのメッセージの総量のうち予め設定された割合である、請求項９に記載の方法。
【請求項１３】
ネットワークにおいてトラフィックルーティング管理を実行する方法であって、該方法は、
複数の信号についてソースアドレス範囲をモニタリングするステップと、
該複数の信号について到着ネットワーク接続ポイントをモニタリングするステップと、
該ネットワークのアドレス空間マップを展開させるステップと
を包含する、方法。
【請求項１４】
信号を該信号の宛先アドレス範囲に最も近いネットワーク接続ポイントにルーティングするために前記アドレス空間マップを用いるステップをさらに包含する、請求項１３に記載の方法。
【請求項１５】
前記アドレス空間マップを用いるステップは、
ルートが信号量の閾値を超えると判定すると、ネットワークルーティングプロトコルに従って自然に選択されず、かつネットワーク構成パラメータに従って禁止されないルートテーブルルートを選好するステップをさらに包含する、請求項１４に記載の方法。
【請求項１６】
前記ネットワークルーティングプロトコルは、ボーダーゲートウェイプロトコルである、請求項１５に記載の方法。
【請求項１７】
前記ルートテーブルルートを選好するステップは、ルートについての局所的な選好を変更するステップを包含する、請求項１５に記載の方法。
【請求項１８】
前記信号量の閾値は、前記ソースに対応するソースアドレス範囲からの信号の総数のうち予め設定された割合である、請求項１５に記載の方法。
【請求項１９】
前記信号量の閾値は、信号の予め設定された数である、請求項１５に記載の方法。
【請求項２０】
前記アドレス空間マップを用いるステップは、信号の前記ソースアドレス範囲内の新しいルートを前記ネットワークに導入するステップをさらに包含する、請求項１４に記載の方法。
【請求項２１】
前記新しいルートを導入するステップは、外部システムからボーダーゲートウェイプロトコルセッションを用いてルート発表を発行するステップを含む、請求項２０に記載の方法。
【請求項２２】
前記アドレス空間マップを用いるステップは、該アドレスマップとネットワーク中の既存のルートとの間の差異を一致させるステップをさらに包含する、請求項１４に記載の方法。
【請求項２３】
各ソースアドレス範囲は、プレフィックス長を含むインターネットプロトコルアドレスである、請求項１３に記載の方法。
【請求項２４】
前記ネットワーク接続ポイントはインターフェイスである、請求項１３に記載の方法。
【請求項２５】
前記ネットワークのアドレス空間マップを展開させるステップは、
該ネットワーク中のルータ上のルートテーブルからルート入力を収集するステップと、
該ネットワーク中の該ルータを通過する前記モニタリングされる複数の信号における信号トラフィック統計入力をコンパイルするステップであって、各信号トラフィック統計入力は、ソースアドレス範囲に対応する信号の量の測定を含む、ステップと
をさらに包含する、請求項１３に記載の方法。
【請求項２６】
各信号トラフィック統計入力とルート入力とを相関させるステップをさらに包含する、請求項２５に記載の方法。
【請求項２７】
各信号は、インターネットプロトコルパケットである、請求項２５に記載の方法。
【請求項２８】
各信号トラフィック統計入力は、
インターネットプロトコルアドレスと、
該インターネットプロトコルアドレス範囲についてのプレフィックス長と、
関連のルート入力と
をさらに含む、請求項２５に記載の方法。
【請求項２９】
各ルート入力は、広告されたボーダーゲートウェイプロトコルルートを含む、請求項２５に記載の方法。
【請求項３０】
前記モニタリングされた複数の信号は、前記ネットワーク内で送信された信号を含む、請求項１３に記載の方法。
【請求項３１】
前記モニタリングされた複数の信号は、前記ネットワーク内で送信された信号のサンプリングされた部分を含む、請求項１３に記載の方法。
【請求項３２】
前記モニタリングされた複数の信号は、
前記ネットワーク内で送信された信号のセットと、
該ネットワークの前記アドレス空間マップの一部に充填するために生成された信号のセットと
を含む、請求項１３に記載の方法。
【請求項３３】
前記モニタリングされた複数の信号は、前記ネットワークの実質的に等しい信号範囲を提供するために生成された信号のセットを含む、請求項１３に記載の方法。
【請求項３４】
前記モニタリングするステップは自動的に実行され、かつ前記アドレス空間マップを展開させるために自動的に用いられる、請求項１３に記載の方法。
【請求項３５】
前記アドレス空間マップを用いるステップは、自動的に実行される、請求項１４に記載の方法。
【請求項３６】
前記ルートテーブルルートを選好するステップは、自動的に実行される、請求項１５に記載の方法。
【請求項３７】
前記新しいルートを導入するステップは、自動的に実行される、請求項２０に記載の方法。
【請求項３８】
前記信号トラフィック統計をコンパイルするステップは、自動的に実行される、請求項２５に記載の方法。
【請求項３９】
ネットワークにおいてトラフィックルーティング管理を実行するためのコンピュータプログラム製品であって、
複数の信号についてソースアドレス範囲をモニタリングするプログラムコードと、
該複数の信号について到着ネットワーク接続ポイントをモニタリングするプログラムコードと、
該ネットワークのアドレス空間マップを展開させるプログラムコードと
を含むプログラムコードを格納するコンピュータ読み出し可能媒体を備えた、コンピュータプログラム製品。
【請求項４０】
信号を前記信号の宛先アドレス範囲にトポロジカル的に最も近いネットワーク接続ポイントにルーティングするために前記アドレス空間マップを使用するプログラムコードをさらに含む、請求項３９に記載のコンピュータプログラム製品。
【請求項４１】
前記アドレス空間マップを用いるプログラムコードは、
ルートが信号量の閾値を超えると判定すると、ネットワークルーティングプロトコルに従って自然に選択されず、かつネットワーク構成パラメータに従って禁止されないルートテーブルルートを選好するプログラムコードをさらに含む、請求項４０に記載のコンピュータプログラム製品。
【請求項４２】
前記アドレス空間マップを用いるプログラムコードは、
信号の前記ソースアドレス範囲内の新しいルートを前記ネットワークに導入するプログラムコードをさらに含む、請求項４０に記載のコンピュータプログラム製品。
【請求項４３】
前記アドレス空間マップを用いるプログラムコードは、該アドレスマップとネットワーク中の既存のルートとの間の差異を一致させるプログラムコードをさらに含む、請求項４０に記載のコンピュータプログラム製品。
【請求項４４】
前記ネットワークのアドレス空間マップを展開させるプログラムコードは、
該ネットワーク中のルータ上のルートテーブルからルート入力を収集するプログラムコードと、
該ネットワーク中の該ルータを通過する前記モニタリングされる複数の信号における信号トラフィック統計入力をコンパイルするプログラムコードであって、各信号トラフィック統計入力は、ソースアドレス範囲に対応する信号の量の測定を含む、プログラムコードと
をさらに含む、請求項３９に記載のコンピュータプログラム製品。
【請求項４５】
各信号トラフィック統計入力とルート入力とを相関させるプログラムコードをさらに含む、請求項４４に記載のコンピュータプログラム製品。
【請求項４６】
ネットワークにおいて信号のルーティングを管理する方法であって、
該ネットワーク中のルートテーブルからルート入力を受け取るステップと、
該ネットワーク上で１つ以上のルータを通る信号上で、インターネットプロトコル統計データ入力を受け取るステップであって、各インターネットプロトコル統計データ入力は、信号ソースアドレス範囲に対応する信号の量の測定を含む、ステップと
該ルート入力および該インターネットプロトコル統計データ入力を用いて該ネットワークのアドレス空間マップを展開させるステップと、
該アドレス空間マップをインプリメントするステップと
を包含する、方法。
【請求項４７】
前記アドレス空間マップをインプリメントするステップは、好適なルートを選択するステップを包含する、請求項４６に記載の方法。
【請求項４８】
前記好適なルートを選択するステップは、
ルートが信号量の閾値を超えると判定すると、ネットワークルーティングプロトコルに従って自然に選択されず、かつネットワーク構成パラメータに従って禁止されないルート入力を該好適なルートとして選択するステップを包含する、請求項４７に記載の方法。
【請求項４９】
前記ネットワークルーティングプロトコルは、ボーダーゲートウェイプロトコルである、請求項４８に記載の方法。
【請求項５０】
前記アドレス空間マップをインプリメントするステップは、非集合化ルートを選択するステップをさらに包含する、請求項４７に記載の方法。
【請求項５１】
前記非集合化ルートを選択するステップは、
インターネットプロトコル統計データ入力に対応するルートを該非集合化ルートとして選択するステップであって、該ルートは、前記ネットワークに現在発表された前記ルートテーブルルートよりもより明確である、ステップを包含する、請求項５０に記載の方法。
【請求項５２】
前記より明確なルートは、より長いプレフィックス長を有する、請求項５１に記載の方法。
【請求項５３】
ネットワークにおいて信号のルーティングを管理するコンピュータプログラム製品であって、
該ネットワーク中のルートテーブルからルート入力を受け取るプログラムコードと、
該ネットワーク上で１つ以上のルータを通る信号上で、インターネットプロトコル統計データ入力を受け取るプログラムコードであって、各インターネットプロトコル統計データ入力は、信号ソースアドレス範囲に対応する信号の量の測定を含む、プログラムコードと
該ルート入力および該インターネットプロトコル統計データ入力を用いて該ネットワークのアドレス空間マップを展開させるプログラムコードと、
該アドレス空間マップをインプリメントするプログラムコードと
を含むプログラムコードを格納するコンピュータ読み出し可能媒体を備えた、コンピュータプログラム製品。
【請求項５４】
前記アドレス空間マップをインプリメントするプログラムコードは、好適なルートを選択するプログラムコードを含む、請求項５３に記載のコンピュータプログラム製品。
【請求項５５】
前記好適なルートを選択するプログラムコードは、
ルートが信号量の閾値を超えると判定すると、ネットワークルーティングプロトコルに従って自然に選択されず、かつネットワーク構成パラメータに従って禁止されないルート入力を該好適なルートとして選択するプログラムコードを含む、請求項５４に記載のコンピュータプログラム製品。
【請求項５６】
前記アドレス空間マップをインプリメントするプログラムコードは、非集合化ルートを選択するプログラムコードをさらに含む、請求項５４に記載のコンピュータプログラム製品。
【請求項５７】
前記非集合化ルートを選択するプログラムコードは、
インターネットプロトコル統計データ入力に対応するルートを該非集合化ルートとして選択するプログラムコードであって、該ルートは、前記ネットワークに現在発表された前記ルートテーブルルートよりもより明確である、プログラムコードを含む、請求項５６に記載のコンピュータプログラム製品。
【請求項５８】
コンテンツプロバイダに接続されたバックボーンと、コンテンツユーザに接続された第１のネットワークとを含むシステムにおいて、該コンテンツプロバイダと該コンテンツユーザとの間のトラッフィクをルーティングする方法であって、該第１のネットワークは１つ以上の接続によりバックボーンに接続されており、
該コンテンツプロバイダのトラフィックを該バックボーン上に設置するステップと、
該バックボーン上の該トラフィックを該第１のネットワークにルーティングするステップと、
該トラフィックを、該コンテンツユーザにトポロジカル的に最も近い該第１のネットワークと該バックボーンとの間の該接続上に配置するステップと
を包含する、方法。
【請求項５９】
前記コンテンツプロバイダは、アクセスポイントを介して前記バックボーンに接続される、請求項５８に記載の方法。
【請求項６０】
前記コンテンツプロバイダは、ワールドワイドウェブコンテンツプロバイダである、請求項５８に記載の方法。
【請求項６１】
前記システムは、前記コンテンツユーザに接続された第２のネットワークをさらに含み、前記方法は、
前記トラフィックが前記第１のネットワークまたは前記第２のネットワークを介して該システムに送信されたか否かを決定し、該トラフィックを該システムに送信する該ネットワークを選択するステップと、
前記バックボーン上の該トラフィックを該選択されたネットワークにルーティングするステップと、
該トラフィックを、該コンテンツユーザにトポロジカル的に最も近い該選択されたネットワークと該バックボーンとの間の該接続上に配置するステップと
を包含する、請求項５８に記載の方法。
【請求項６２】
ネットワークトラフィックをルーティングするためのシステムであって、
バックボーンと、
該バックボーン上の複数の存在ポイントであって、各存在ポイントはトラフィックデータを収集し、かつ該トラフィックデータをネットワークオペレーションセンターに送信する、複数の存在ポイントと、
該トラフィックデータを受け取るために該バックボーンに接続され、該トラフィックデータを解析し、該解析されたデータに基づいて該システムのルーティング政策を自動的に変更するネットワークオペレーションセンターと
を備えた、システム。
【請求項６３】
複数のピアリングパートナーネットワークをさらに含み、各ピアリングパートナーネットワークは１つ以上の存在ポイントで前記バックボーンに接続されている、請求項６２に記載のシステム。
【請求項６４】
各ピアリングパートナーネットワークは、該ピアリングパートナーネットワークが前記バックボーンから受け取るすべてのトラフィックについての料金が支払われる、請求項６３に記載のシステム。
【請求項６５】
少なくとも１つのピアリングパートナーネットワークは、ピアリングパートナーネットワークの一部でない他のインターネットサービスプロバイダへのトランジット接続を提供する、請求項６４に記載のシステム。
【請求項６６】
１つ以上のピアリングパートナーネットワークをさらに含み、各ピアリングパートナーネットワークは９つ以上の存在ポイントでＯＣ−３ライン接続により前記バックボーンに接続されている、請求項６２に記載のシステム。
【請求項６７】
各存在ポイントは、
前記バックボーンと１つ以上のピアリングパートナーネットワークとの間のトラフィックをルーティングするためのルータであって、該ルータはさらに、インターネットプロトコル統計報告を生成し、ルートテーブルを読み出し、該インターネットプロトコル統計報告および該ルートテーブルをコンピュータに送信する、ルータと、
該インターネットプロトコル統計報告および該ルートテーブルを受け取り、該インターネットプロトコル統計報告および該ルートテーブルを前記ネットワークオペレーションセンターに送信するためのコンピュータと
を含む、請求項６２に記載のシステム。
【請求項６８】
前記コンピュータは、前記インターネットプロトコル統計報告と前記ルートテーブルとをさらに相関させる、請求項６７に記載のシステム。
【請求項６９】
前記コンピュータは、新しいルーティング政策に対応する前記ネットワークオペレーションから好適なルートをさらに受け取る、請求項６７に記載のシステム。
【請求項７０】
前記コンピュータは、前記新しいルーティング政策と既存のルーティング政策とをさらに比較し、該新しいルーティング政策と該既存のルーティング政策との間の差異をインプリメントする、請求項６９に記載のシステム。
【請求項７１】
前記バックボーンは、デンスウェーブディビジョンマルチプレキシングシステムである、請求項６２に記載のシステム。
【請求項７２】
各存在ポイントはトラフィックデータを自動的に収集し、前記ネットワークオペレーションセンターは該トラフィックデータを自動的に解析する、請求項６２に記載のシステム。
【発明の詳細な説明】
【０００１】
（発明者）
Ｍｉｃｈａｅｌ　Ｅ．Ｇａｄｄｉｓ，Ｐｅｔｅｒ　Ｎ．Ｈｉｃｋｓ，Ｄａｖｉｄ　Ｂａｒｍａｎｎ　ａｎｄ　Ｓｔｅｖｅｎ　Ｔ．Ｎｕｎｅｓ
（背景）
（発明の分野）
本発明は、概して、ネットワークルーティングに関し、より詳細には、ルート非集合およびルート選択選好に基づく最良の既存ルーティングに対する地域アドレスロケーションを動的に決定することに関する。
【０００２】
（発明の背景）
インターネットの成長、特にワールドワイドウェブ（ＷＷＷ）によって、インターネットを含む一群の接続されたネットワークおよび接続されたネットワークシステムを介する取引の流れの量が莫大に増加している。インターネットサービスプロバイダ（ＩＳＰ）等のアクセスプロバイダは、インターネットに接続しＷＷＷにアクセスするために、ビジネスおよび個人のための接続を提供する。ＩＳＰは、それらの顧客が他のＩＰＳによってサービスされるインターネット上のポイントに到達することを許容するために相互に連結する必要がある。
【０００３】
インターネットサービスプロバイダ（ＩＳＰ）間の取引の交換（ここで、一つのＩＳＰの顧客からの取引は、他のＩＳＰの顧客に行き先が定められる）は、「ピアリング」と呼ばれる。これは、「トランジット」と対照される。ここで、交換された取引は、受信するＩＳＰの顧客にだけではなく、インターネット（受信ＩＳＰピアリング接続を介して順に到達される）の全体を通じて他のユーザにも行き先が定められる。ＩＳＰは、一般にトランジット接続に代価を請求する一方、ピアリング接続は、金銭の交換を含まない。したがって、ピアリングは自由な２方向のＩＳＰ間顧客取引の交換を提供する一方、トランジットは、支払われたアクセスをインターネット全体に提供する。例えば、それら自体の国家的なバックボーンを有する大きなＩＳＰは、しばしば、それらの顧客のデータを自由に交換するために、国家的なバックボーンを有する他の大きなＩＳＰと相互に一致する。インターネットのバックボーンは、端部、すなわち局所間のデータをネットワークの部分およびインターネットピアリングポイントに移動させるＩＳＰのネットワークの中心部分である。ピアリングの代わりに、国家的なバックボーンを有する大きなＩＳＰは、トランジットサービスを、相互のバックボーン共有を提示できないより小さい、局所的なＩＳＰに提示する。これらのより小さいＩＳＰは、より大きいＩＳＰの国家的バックボーンをそれらのサービスエリアの外側のユーザに到達するために使用する。
【０００４】
ピアリング接続は、２つの異なるＩＳＰ間の取引の流れがほぼ等しいという、基礎となる仮定に基づいている。情報トラフィック（帯域幅）を自由に且つ代価なしで交換するためのこれらの相互の取り決めは、一つのピアリングパートナーが実質的に他より多くのトラフィックを搬送することを強いられる場合、経済的な意義をなさない。アンバランスな帯域幅が、大抵のピアリングされたデータが「ホットポテトルーティング」と呼ばれるルーティング方法を用いてルーティングされるため、ピアリング関連に影響し得る。
【０００５】
ホットポテトルーティングにおいて、顧客のトラフィックを搬送する起点ピアネットワークは、行先ピアのネットワークに最も近い入力ポイントを見い出し、出来るだけ早くトラフィックを落とす。ピアネットワークがトラフィックを運ぶことが利用可能な場合、キャリアがさらなる帯域幅を搬送する誘因は存在しない。同様に、行先ピアネットワークは、返信データを起点のネットワークに送信する。このデータ移送のために用いられた二つの交換ポイントが地理的に分散されている場合、この種のルーティングは、非対称なルーティング経路を二つのネットワーク終端間に作り出す。ここで、一つの「ｔｏ」経路は、主として行先ピアのネットワーク上を移動し、「ｆｒｏｍ」経路は、主として起点のネットワーク上を移動する。用いられる帯域幅の量が両方向において非対称であり、且つ、二つのネットワークが類似の地理的範囲を有している場合、これは、公平な経済的交換を作り出す。各ピアキャリアは帯域幅を二等分し、各ピアは、移動の半分を支払うために（おそらく）一人の支払い顧客を有する。これは、インターネットピアリングの基礎をなす基本的なやりとりの提案である。
【０００６】
しかしながら、インターネットピアリングモデルは、一般的に、ピア間の対称な帯域幅の仮定に基づいているが、この仮定は、欠点があることが判明している。ＷＷＷの成長およびにＷＷＷトラフィック内の増加は、帯域幅の非対称性の問題を悪化させる。ウェブコンテンツプロバイダは、おびただしい量のデータを伝達する傾向がある。ウェブコンテンツプロバイダおよびウェブコンテンツを見る個人の間の帯域幅は、しばしばアンバランスになる。ウェブコンテンツプロバイダは、典型的には、それらが受け取るよりも４〜１０倍程度多くの帯域幅を送信する。個人は、ちょうど一つのアドレスまたはページリクエストを送信することによってウェブページをリクエストし得、これに対して、ウェブページプロバイダは、複数のウェブページをその個人に返信し、これにより、大量の帯域幅を消費する。
【０００７】
例えば、個人にサービスするＩＳＰ　ＡとウェブコンテンツプロバイダにサービスするＩＳＰ　Ｂ間のシナリオを考える。ＩＳＰ　ＡおよびＢの双方は、ホット−ポテトルーティングを用い、ネットワークトラフィックをピアリングＩＳＰに最も近い入力ポイントに落とす。ＩＳＰ　Ａは、ウェブページに対するリクエストを受け取り、そのリクエストをルーティングし、その結果、そのリクエストは、ＩＳＰ　Ｂによって移動された距離の大部分について運ばれる（ホットポテトルーティング）。ＩＳＰ　Ｂは、リクエストされたウェブページを返送して、個人からの最初のリクエストよりかなり大量の帯域幅を構成する。ＩＳＰ　Ｂは、同様にホットポテトルーティングを用い、その結果、ＩＳＰ　Ａは、ウェブトラフィックを移動された距離の大部分について運ぶ。ＩＳＰ　Ａは、このシナリオでは、帯域幅のトラフィック負担の公平な割当てより多くの運ぶことを強いられる。さらに、ＩＳＰ　Ａは、それ自身の顧客に、余分な帯域幅について多くを負担させることができない。余分な帯域幅を開始する存在がＩＳＰ　Ｂの顧客であるからである。現行のピアリングシステムは、その帯域幅を増加させるために適切な経済的な刺激をＩＳＰに対して提供しない。増加された帯域幅は、ＩＳＰのピアによって消費され得るからである。
【０００８】
ウェブコンテンツプロバイダは、しばしば、それらがそれらのＩＳＰを介して経験する帯域幅の制限によって束縛される。いくつかのウェブコンテンツプロバイダは、マルチホーム化するによって、すなわち、複数のＩＳＰを有するサービスを請け負って、さらなる帯域幅の容量を購入することおよびおそらく余分量を購入することによって、この問題を解決することを試みる。しかしながら、各潜在的なクライアント端末への余分な経路の付加によって、複雑さが増加される結果となる。マルチホーム化されることは、バックボーンインターネットネットワークオペレータのように考えることおよび活動すること、および正確にトラフィックをルーティングする容量を有することを要求する。
【０００９】
最良の経路管理の結果としての負担は、困難なタスクであり、大抵のウェブコンテンツプロバイダによってマスターされる可能性がないものである。ボーダーゲートウェイプロトコル（ＢＧＰ）（これは、インターネット上のネットワーク間のデータをルーティングするために用いられる）は、貧弱なツールであり、ルータにおいてプロセスを形成する自動化された決定に利用可能な制限された最良の経路情報を有している。微小エンジニアリングの多くのプロバイダへの良好な接続性能は、ＢＧＰプロトコルおよびそのルールの実質的な知識を要求するだけではなく、ネットワーク構造および下流プロバイダ自体の操作性能の実質的な知識も要求する。
【００１０】
したがって、ウェブコンテンツプロバイダ、並びに、他のインターネット消費者は、彼らが大量のネットワーク帯域幅を、各ウェブコンテンツプロバイダにインターネットルーティングの専門家になることを要求することなく購入することができるシステムを必要とする。しかしながら、ウェブトラフィックは、ピアリング帯域幅の非対称性の問題に実質的に寄与するので、ネットワークピアにおいて開始するウェブトラフィックを含め、すべてのネットワークキャリアをそれらが運ぶウェブ帯域幅のために補償する方法が要求される。経済的に合理的なシステムが、ウェブ帯域幅を提供するために必要とされ、これにより、ウェブコンテンツプロバイダは、彼らのサービスの真の費用を支払い、ＩＳＰは、それらのネットワークシステムに交差するウェブ帯域幅について支払われる。
【００１１】
（発明の要旨）
本発明は、ウェブコンテンツプロバイダおよび他のインターネット帯域幅消費者（「コンテンツプロバイダ」）が彼らが要求するインターネットの帯域幅を取得することを許容し、一方で、アクセスプロバイダにビットごとを基礎として彼らが運ぶトラフィックに対して支払うシステムを提供する。本システムは、システム内のトラフィックのルーティングが、本システムのトポロジカルな「アドレス空間マップ」の開発を通して、「最良のルート」選択プロセスを可能にすることを管理および促進する。ネットワークの「トポロジー」は、回路ルート距離におけるネットワークのジオグラフィに類似する。コンテンツプロバイダは、マルチホーミングルーティング供給（ｉｓｓｕｅ）に関与する必要がなく、アクセスプロバイダは、彼らが彼らのネットワークの使用に対して支払われることが保証される。
【００１２】
知的なルーティング交換システムは、ピアリングパートナーネットワークのセットに相互に連結されたバックボーンを含む。バックボーンは、ロングホール（ｌｏｎｇ−ｈａｕｌ）トラフィックを運ぶために用いられる。中央ネットワークオペレーションセンター（ＮＯＣ）は、全体の知的ルーティングネットワークのトポロジカルなアドレス空間マップを発展させ、ルーティング管理を行う。知的ルーティング管理システムは、帯域幅がピアリングパートナーネットワークに地域的に要求されおよび配信されること、およびトラフィックがロングホールデータ分配のためのバックボーンによって両方向に運ばれることを保証する。交換システムは、地域的なキャリアに送信される全トラフィックのためにコールドポテトルーティングを、地域的キャリアから受信される全トラフィックのためにホットポテトルーティングを使用する。ピアリングパートナーが地域的トラフィックのみを運ぶことを保証することによって、ピアリングパートナーは、もはやピアアクセスプロバイダからの不公平な搬送非対称帯域幅を受けることがない。
【００１３】
バックボーンは、ピアリングパートナーネットワークのプールにバックボーン上の地域的な存在ポイント（ＰＯＰ）のセットを通して接続される。ピアリングパートナーは、典型的に複数ＰＯＰに接続するうまく接続された主要トラフィックキャリアである。各ピアリングパートナーとの契約が、知的ルーティングシステ全体がバックボーン上およびバックボーン外の変形トラフィックのために十分な帯域幅を提供することを保証するように取り決められる。
【００１４】
知的ルーティングシステムの顧客は、ＰＯＰの一つでの知的ルーティングシステムに接続する。顧客は、例えば、ウェブホスティングカンパニー、個人インターネットサービスプロバイダ、または法人顧客であり得る。各顧客は、知的ルーティングシステムサービスを購入契約し、特定のＰＯＰ接続位置を取得する。
【００１５】
各ピアリングパートナーは、ネットワークにわたるバックボーンから送信されたすべてのビットに対する料金がアクセス顧客端末に支払われる。顧客は、バックボーンの実際の使用に基づくｐｒｏ−ｒａｔａを基礎として請求書が送られる。
【００１６】
バックボーン上の全てのトラフィックの地域的な配信を実行することは、バックボーンへの入力ポイントの位置に関して、相互に連結されたピアリングパートナーネットワーク内のインターネットプロトコル（ＩＰ）アドレスの群のトポロジカルな位置についての詳細な情報を要求する。中央ＮＯＣは、知的ルーティングネットワークについてのこのような詳細な情報を提供するアドレス空間マップを、ネットワークトラフィックをモニタリングすることによって発展させる。種々のＩＰアドレス範囲からの各ＰＯＰ入力ポイントで受信されたトラフィックに関する情報が、各ＰＯＰに集められる。ＰＯＰデータは、ＮＯＣに処理のために送信される。
【００１７】
ＮＯＣは、「最良のルート」情報を発展させ、この情報は、ＰＯＰのセットおよび相互に連結されたピアリングパートナーネットワークに戻して分配される。「最良のルート」情報は、トラフィックが知的ルーティングネットワーク上の好ましいルートを通して正しくルーティングされることを保証し、可能な場合にバックボーン上のトラフィック維持し、効率の悪いルーティングを避ける。ＮＯＣはまた、アドレス空間マップの正確さをさらに向上するために知的ルーティングネットワークに導入されるべき新しいルートを選択する。
【００１８】
（好適な実施形態の詳細な説明）
参照がここで詳細に本発明のいくつかの実施形態に対してなされる。この実施形態の例は、添付された図面に図示される。実行できる場合、同一の参照符号は、図面の全体を通して同一または類似の部分に参照するために用いられる。
【００１９】
（導入）
図１Ａは、インターネットおよびウェブトラフィックを運ぶための既存のシステムに関する背景情報を提供する。図１Ａは、通信ネットワーク１００を示す。ネットワーク１００は、三つのインターネットサービスプロバイダ（ＩＳＰ）１１０、１２０、１３０および代表であるインターネット１４０を含む。ＩＳＰ１１０は、ポイント１１２を含む。ＩＳＰ１２０は、ポイント１２２を含む。ＩＳＰ１３０は、ポイント１３２を含む。そして、インターネット１４０は、ポイント１４２を含む。各ポイントは、ネットワーク１００内の特定のインターネットプロトコル（ＩＰ）アドレスを表す。各ＩＳＰは、ある地理的領域にインターネットアクセスを提供する設備および電話通信ラインのセットを表す。ＩＳＰは、インターネット接続を種々の個人および会社に提供し、各個人および会社は、ＩＰアドレスまたはＩＰアドレス範囲を有する。インターネット１４０は、コンピュータネットワークのワールドワイドシステム表し、そのシステムの一部分は、Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ（「ｔｈｅ　Ｗｅｂ」または「ＷＷＷ」）。
【００２０】
個々のＩＳＰ１１０、１２０および１３０は、全ネットワーク１００の送り先にそれぞれ個々に接続されていない。ＩＳＰ１１０、１２０および１３０は、ネットワーク１００の他の部分にアクセスするために、ピアリングおよびトランジット接続のシステムを用いる。ピアリングおよびトランジット接続は、地域的なネットワークがネットワーク外の方向へのアクセスを、他の地域的ネットワークの使用を取り決めることによって提示することを許容する。ＩＳＰは、しばしば、米国におけるネットワークアクセスポイント等のネットワーク焦点ポイントに、および地域的あるいは国際的なスイッチングポイントに相互に連結する。接続するＩＳＰは、典型的にはボーダーゲートウェイプロトコル（ＢＧＰ）を用いて、ルーティング情報を互いに交換する。
【００２１】
ピアリング接続１５０は、ＩＳＰ１１０およびＩＳＰ１３０を接続する。ピアリング接続は、相互のトラフィック交換を許容するために二つのネットワークキャリア間の取り決められた同意である。図１Ａに示されるように、ポイント１３２にアクセスするＩＳＰ１１０のポイント１１２を許容するために、ＩＳＰ１１０およびＩＳＰ１３０は、トラフィックアクセスピアリング接続１５０を交換する。
【００２２】
トランジット接続１６０は、ＩＳＰ１２０をインターネット１４０と接続する。トランジット接続は、第二のネットワークに接続するために、一つのネットワークを通過する。例えば、図１Ａに示されるように、インターネット１４０のポイント１４２がＩＳＰ１２０のポイント１２２によって到達されるために、トラフィックがＩＳＰ１１０にわたってルーティングされることが必要である。
【００２３】
図１Ｂは、ネットワーク１９０内の二つのＩＳＰ間の「ホットポテトルーティング」および「コールドポテトルーティング」の図である。ＩＳＰ１１０およびＩＳＰ１３０は、二つの異なるピアリング接続１５０Ａおよび１５０Ｂを介して接続される。ピアリングトラフィック（「ピアリングパートナー」）を交換するＩＳＰは、典型的に複数のピアリング接続を異なる配置領域に有し得る。ＩＳＰ１１０は、ＩＳＰ１１０のネットワーク内に含まれる特定のＩＰアドレスを表すポイント１１２を接続する。ポイント１１２は、ＩＳＰ１１０を介してのみ到達可能である。同様に、ＩＳＰ１３０は、ＩＳＰ１３０のネットワーク内に特定のＩＰアドレスを表すポイント１３２を含む。
【００２４】
ＩＳＰ１３０のポイント１３２がトラフィックをＩＳＰ１１０のポイント１１２に送信することを望むと仮定する。このトラフィックは、二つの異なる方法でルーティングされ得る。ＩＳＰ１３０は、ＩＳＰ１３０のネットワークからのトラフィックをできるだけ早く取り除くために、最も近いピアリング接続をソースポイント１３２（ピアリング接続１５０Ａ）に選択し得る。ＩＳＰ１３０自体のネットワークのトラフィックをできるだけ早く落とすこの方法は、「ホットポテト」ルーティングとして参照される。代替として、ＩＳＰ１３０は、送先ポイント１１２（ピアリング接続１５０Ｂ）上のトラフィックを保持し得る。自身のネットワーク上のトラフィックをできるだけ長い間保持するこの方法は、「コールドポテト」ルーティングとして参照される。
【００２５】
典型的に大抵のピアリングパートナーによって行われるホットポテトルーティングは、他のピアリングパートナーのネットワークアドレス空間の知識を要求しない。例えば、ポイント１３２からのトラフィックをポイント１１２にホットポテトルート１７０を介してルーティングするために、ＩＳＰ１３０は、それ自身のＩＳＰ１１０に最も近いピアリング接続を決定するできることが必要とするのみである。ＩＳＰ１３０は、ピアリング接続１５０Ａがポイント１３２に、ピアリング接続１５０Ｂにより近いことを決定するために、それ自身の内部ネットワークの知識を必要とするのみである。
【００２６】
対照として、トラフィックのコールドポテトルーティング１７２を最適に行うことができるために、ＩＳＰ１３０は、知的なルーティング決定をなすことができる必要がある。ＩＳＰ１３０は、ＩＳＰ１３０およびＩＳＰ１１０間のピアリング接続１５０Ａおよび１５０Ｂがどこに位置するかを知る必要がある。ＩＳＰ１３０は、さらに、ＩＳＰ１１０に配置されるポイント１１２が、トポロジカル的に、ピアリング接続１５０Ａに対抗するピアリング接続１５０Ｂにより近いことを認めることができる必要がある。ネットワークの「トポロジカル」は、回路ルート距離におけるネットワークの配置に類似する。この知的ルーティング決定は、ピアリングパートナーＩＳＰ１１０のアドレス空間の知識を要求する。いくつかのルーティング情報は、ＢＧＰルーティング情報を介して取得され得る。しかしながら、ＢＧＰ情報は、不正確で且つ不完全であり得、また、相互に変更され得る。
【００２７】
図２Ａは、ＩＳＰ間の接続提示の種類を図示する。ネットワーク２００は、三つのＩＳＰ１１０、１２０および１３０を含む。ＩＳＰ１１０は、ポイント１１２を含む。ＩＳＰ１２０は、ポイント１２２を含む。そして、ＩＳＰ１３０は、ポイント１３２を含む。四つの異なるピアリング接続は、ＩＳＰ１１０とＩＳＰ１３０とを接続する：１５０Ａ、１５０Ｂ、１５０Ｃおよび１５０Ｄ。ピアリング接続２５２は、ＩＳＰ１１０およびＩＳＰ１２０を接続する。ピアリング接続２５４は、ＩＳＰ１２０およびＩＳＰ１３０を接続する。
【００２８】
ネットワーク２００は、ＢＧＰを用いて通信して、ネットワーク内の種々のＩＰアドレス、またはポイント間のトラフィックをルーティングする。ＢＧＰは、自律システム（ＡＳ）のネットワーク内のルーティング情報を交換するためのプロトコルである。以下の例において、各ＩＳＰは単一の自律システムであることが仮定される。ＡＳは、単一のネットワークの管理者またはルーティング権威によって制御されるネットワークまたはネットワークの群である。各ＡＳは、一つ以上のＩＰアドレス範囲の接続された群を含む。各ＡＳは、ＡＳナンバーを有している。ＩＳＰ１１０は、ＡＳナンバー１００を有し、ＩＳＰ１２０は、ＡＳナンバー５０を有している。
【００２９】
ルーターは、ＡＳ間のトラフィックをＢＧＰルーティング情報を用いてルーティングする。異なるＡＳ通知間のルーターは、ルーターがそれ自身のＡＳ外の送先の知識を要求することを許容するために、互いにルーティングする。各ルート通知は、既知のルーターのリスト、各ルーターから到達可能なアドレスのリスト、および（必要に応じて）最良のルートが選択されるのを保証することを助力する各経路に関連するコスト測定基準のようなアイテムを含めて、特定のルート情報を含む。
【００３０】
一つの特定の種類のコスト測定基準は、ＡＳ　Ｐａｔｈである。ＡＳ　Ｐａｔｈの特質は、特定のルートが通過する種々のＡＳの跡を維持する。ルートが通過する各個人のＡＳは、特定のＡＳナンバーを有するＡＳ　Ｐａｔｈ特質内で識別される。ルートが新しいＡＳを通過する各時間に、新しいＡＳは、そのＡＳ　Ｐａｔｈ特質をルートについてのＡＳナンバーのリストに追加する。例えば、ネットワーク２００において、ポイント１１２がトラフィックをポイント１３２に送信することを望むと仮定する。ポイント１３２からポイント１１２への接続１５０のセットを介するトラフィックルートは、ＡＳ　Ｐａｔｈ特質１００を含む。接続２５２および２５４を介するポイント１１２および１３２間のトラフィックルートは、５０、１００のＡＳ　Ｐａｔｈを含む。より長いＡＳ　Ｐａｔｈを有するルートは、概して、好ましいルートではなく、したがって、接続１５０を介するルートが、ＡＳ　Ｐａｔｈ特質が続く場合に、概して、用いられる。
【００３１】
しかしながら、ＡＳ　Ｐａｔｈ特質は、同じ二つの通知システムを接続する複数のルート間を区別する際に助けとならない。例えば、ＩＳＰ１１０のポイント１１２およびＩＳＰ１３０のポイント１３２間のトラフィックルートが望ましいと仮定する。ＩＳＰ１１０およびＩＳＰ１３０（１５０Ａ、Ｂ、ＣおよびＤ）間に４つのピアリング接続が存在し、ＡＳ　Ｐａｔｈ特質は、各接続に対して同一の値を有する。この場合、ｍｕｌｔｉ−ｅｘｉｔ識別子（ＭＥＤ）特質は、ＡＳへの複数の入力ポイントが存在する場合に好ましい経路についての情報を外部の隣接のＡＳに提供する。より低いＭＥＤ特質が好ましく、不履行のＮＥＤは０である。
【００３２】
例えば、ＩＳＰ１１０は、以下のＭＥＤを接続１５０のセットに通知し得る。
【００３３】
【表１】
2004508743.tif 000003
この例では、最も短いＭＥＤは、１５０Ｃに対応する。これは、ＭＥＤ特質が続く場合、ポイント１１２および１３２間の好ましいルートになる。
【００３４】
ＡＳ　Ｐａｔｈ特質は、過渡的であり、ルート内の各ネットワークに沿って通過されること意味する。しかしながら、ＭＥＤ特質は、過渡的ではなく、隣接のネットワーク間で交換されるだけであり、ルートを通過しないことを意味する。
【００３５】
ＡＳによって通知されるＡＳ　ＰａｔｈおよびＭＥＤ値は、常に、正確なルーティング情報を提供しなくてもよい。例えば、ＡＳは、一つのルートを他を超えて選択するために、彼らが通知したＡＳ　ＰａｔｈまたはＮＥＤ値を故意に変更し得る。加えて、ＡＳ　ＰａｔｈおよびＭＥＤ情報は、それだけで、トラフィックを送信するための最良の経路が選択されることを保証するルートについての十分な情報を提供しなくてもよい。ルーティングテーブルは、しばしば、大きくなり、および、空間をセーブするために、アドレスは、アドレスマスクを用いてアドレス範囲にグループ化される。これは、より小さいルーティングテーブルを許容するが、特定のアドレスへのルーティングに関してより正確性に欠ける情報を提供し得る。
【００３６】
ＢＧＰ　ＡＳ　ＰＡＴＨおよびＭＥＤ情報内に存在し得る不正確さは、ＢＧＰルーティング問題の典型的な例である。一般に、ＢＧＰルーティングは、複雑であり、しばしば、決定マスキングプロセスを混乱させ、ＢＧＰルーティング値のみでは、ネットワークでの正確に最良のルーティング経路を反映することが信頼され得ない。ＢＧＰは、ネットワーク経路の特長についての非常に広い情報を与える。ルートを評価するための、固定された、標準化された帯域幅、信頼性、または距離経路特質は存在しない。全ての情報は、ソースおよび中間ネットワークから信頼される必要がある。中間ネットワークは、起点のネットワークからのルートパラメータを拒絶し得、したがって、下流での最良の経路計算に影響を与える。
【００３７】
（アドレス空間マップ）
図２Ｂは、本発明の実施形態におけるＩＳＰのアドレス空間の非集合を図示する。本発明は、ルート情報を集め、関連性のあるアドレス空間のトポロジカルなアドレス空間マップをコンパイルすることによってネットワークルーティングを向上させる。本明細書に記載されたアドレス空間マップは、インターネットのネットワーク内の異なるＩＰアドレスの位置の詳細な図である。このようなアドレス空間マップをコンパイルするプロセスを理解するために、インターネットおよびウェブトラフィックルーティングに用いられる現行の既存ＩＰアドレスするスキームの背景を提供することが必要である。
【００３８】
ＩＰアドレスは、インターネットネットワーク接続における終端ポイント（一般に単一の機械）に割り当てられた３２ビット数である。ソースおよび送先終端ポイントのＩＰアドレスは、インターネットネットワークにわたってルーティングされた各パケットに追加される。「点付きの４つの表記（ｄｏｔｔｅｄ　ｑｕａｄ　ｎｏｔａｔｉｏｎ）」では、例としての３２ビットアドレスが、１４０．２５．５．５であり得る。十進法の数のそれぞれは、８ビット、および０〜２５５の範囲によって表される。したがって、十進法では、アドレス１４０．２５．５．５は、１０００１１００．０００１１００１．０００００１０１．０００００１０１に変換される。ＩＰアドレスのいくつかの部分は、局所的なマシンアドレス（さらにホストアドレスとして知られている）を表し、およびＩＰアドレスの残りは、ネットワークアドレスを表す。組織化は、特定のサブネットを識別するためにホストアドレスにおけるビットのいくつかを用い得る。典型的に、サブセットは、特定の地理的位置におけるマシンの全てを表し得る。
【００３９】
一旦、特定のパケットが送先組織化のゲートウェイまたは接続ポイントに到着すると、組織化のサブネット内のルーティングが、ホストナンバーを用いて局所的なルーターによって行われる。組織に対して外部のグローバルルーターは、一般に、ホストナンバーに接続される必要がない。ルーターは、ＩＰアドレス内のどのビットをマスクに用いることによって接続される必要があるかを決定する。マスクは、ＩＰアドレスに適用され、マスク内の１に対応するＩＰアドレスナンバーのみが見られる。例えば、ＩＰアドレスのネットワークアドレス部分は、１４０．２５である場合、サブネットは５、ホストアドレスは５、ネットワークアドレスを見るためのみにルータを向けるためのマスクは、１１１１１１１１．１１１１１１１１．００００００００．００００００００または２５５．２５５．０．０である。このようなマスクは、さらに、「プレフィックスの長さ１６」または「／１６」として参照される。可能な３２の二進数デジット１６が見られるからである。
【００４０】
一旦マスクがＩＰアドレスに付与されると、その結果のＩＰアドレスは、異なるＩＰアドレスの範囲を参照する。例えば、ＩＰアドレス１４０．２５．１．１／３２は、単一のアドレスを参照する。しかしながら、ＩＰアドレス１４０．２５．１．１．／２４は、２５５の異なるＩＰアドレス１４０．２５．１．０〜１４０．２５．１．２５５の範囲をカバーする。
【００４１】
したがって、／１２プレフィックス長さを有するＩＰアドレスは、／１６プレフィックス長さを有するＩＰアドレスより少ない粒度を提供する。プレフィックス長さは、ＩＰアドレスへのルーティングの際に、いかに多くのＩＰアドレスの二進数のデジットが見られるか、より大きいプレフィックス長さが３２ビットのＩＰアドレスより多くを見るかを決定する。ＩＰアドレスの二進数デジットより多くは見られるので、該当するＩＰアドレスによって表されるアドレス範囲は、より小さくなる。
【００４２】
アドレス空間マップは、異なるアドレス範囲がネットワーク内にどこに位置するかを決定する。より大きいプレフィックス長さのマスクが、アドレス空間マップを発展させるために付与されるので、マップの粒度もまた増加する。アドレス空間マップの粒度を増加するこのプロセスは、アドレス空間の「非集合」として参照される。
【００４３】
アドレス空間マップは、ＩＰアドレスおよびＩＰアドレスに到達するように従われたルートを調べることによって作成される。ネットワーク内で使用されるルーティングの規定の認識に基づいて、アドレス空間マップは、ルーティングの規定の認識が特定のＩＰアドレス空間と共にネットワークのトポロジーの空間に関連するように作成される。このアドレス空間マップは、ネットワークを貫流するトラフィックの論理的なルーティングの決定をするのに利用される。
【００４４】
図２Ｂは、４つのピア接続１５０Ａ、１５０Ｂ、１５０Ｃ、および１５０Ｄを介してルート情報収集サイト２５０に接続されるＩＳＰ１１０を含む。各ピア接続は、異なる現在の地点（ＰＯＰ）においてサイト２５０に接続する。各ＰＯＰは、サイト２５０中の入口地点である。ＩＳＰ１１０のアドレス空間２１０は、ピア接続１５０Ａにトポロジー的に最も近接するＩＳＰ１１０のネットワークの部分である。同様に、アドレス空間２２０はピア接続１５０Ｂにトポロジー的に最も近接し、アドレス空間２３０はピア接続１５０Ｃに最も近接し、ならびにアドレス空間２４０はピア接続１５０Ｄに最も近接する。
【００４５】
ネットワークの「トポロジー」は、回線のルート間隔におけるネットワークの配置にいくらか類似する。例えば、大学Ａおよび大学Ｂがサンフランシスコにおいて互いに通りを横切って位置されると仮定すると、双方のネットワークアドレスは、故に互いに配置的に近接する。会社Ａはインターネット接続を大学Ａに提供し、会社Ｂはインターネット接続を大学Ｂに提供するとさらに仮定する。会社ＡおよびＢのネットワークがロサンゼルスにおいて接続を介して互いにのみ接続される場合、大学ＡおよびＢのネットワークアドレスは、双方のネットワーク間の全てのトラフィックがロサンゼルスを通過する必要があるため、互いにトポロジー的に近接していない。
【００４６】
トポロジーの間隔は、地形の間隔に直接関係しない。ネットワークオペレータは、１回線におけるルートのメートル／コストに基づいてネットワークトポロジーを変化し得る。例えば、ネットワークオペレータは、ネットワークを設定して、サンフランシスコを介する代わりにダラスを介してロサンゼルスからデンバーへのルートを選択し得る。このようなネットワークルーティングの選択は、典型的に帯域幅問題を避けてルーティングするのに利用される。
【００４７】
ＩＰアドレス領域２１６．１００．０．０／１６は、アドレス空間２１０内に位置されるアドレス空間２１２内に含まれる。ＩＰアドレス領域２１６．２５．０．０／１６は、アドレス空間２２０内に位置されるアドレス空間２２２内に含まれる。ＩＰアドレス領域２１６．１０．０．０／１６は、アドレス空間２３０内に位置されるアドレス空間２３２内に含まれる。ＩＰアドレス空間２１６．５．０．０／１６は、アドレス空間２４０内に位置されるアドレス空間２４２内に含まれる。地点２１５は、ＩＰアドレス２１６．１００．５．０／３２に一致し、アドレス空間２１２に位置される。地点２２５は、ＩＰアドレス２１６．２５．５．１／３２に一致し、アドレス空間２２２に位置される。地点１１２は、ＩＰアドレス２１６．１０．５．５／３２に一致し、アドレス空間２３２に位置される。
【００４８】
ＩＳＰ１１０は、ホットポテト（ｈｏｔ　ｐｏｔａｔｏ）ルーティングを用いて、可能な限り素早く隣接するネットワーク上にネットワークトラフィックをルーティングする。ルート情報収集サイト２５０は、入来トラフィックをモニタリングして、トラフィックのソースＩＰアドレス、マスク使用、および到達インタフェース（到達ピア接続）を収集する。サイト２５０はまた、各特定のインタフェースに到達する特定のＩＰアドレスおよびマスクを持つトラフィックのパーセンテージを計算する。この情報を用いて、ルート情報収集サイト２５０は、ＩＳＰ１１０のネットワークのアドレス空間マップを発展させる。アドレス空間マップは、ＩＰアドレス領域とサイト２５０にトポロジー的に最も近接するピア接続とを結び付ける。
【００４９】
サイト２５０によって発展されたアドレス空間マップの粒度は、各ＩＰアドレス領域のプレフィックス長に依存する。例えば、地点１１２は、２１６．１０．５．５のＩＰアドレスおよび／３２（全アドレスがアドレス空間マップを決定するのに調べられることを意味する）の関連したプレフィックス長を有する。ホットポテトルーティングを用いて、ＩＳＰ１１０は、地点１１２からインタフェース１５０Ｃ上に全てのトラフィックを外部に送信する。サイト２５０は、ＩＳＰ１１０がホットポテトルーティングを使用することを承知している。従って、ルート情報収集サイト２５０は、地点１１２がＩＳＰ１１０のアドレス空間２３０内に位置されることを正確に決定することが可能である。
【００５０】
ルート情報収集サイト２５０が小さいプレフィックス長を用いるトラフィックをモニタリングする場合、ＩＳＰ１１０のネットワーク空間のアドレス空間マップを完全に解決するのに十分な粒状ではないかもしれない。例えば、地点２１５および地点２２５が共にルート情報収集サイト２５０にトラフィックの等しい量を送信すると仮定する。サイト２５０が／８のプレフィックス長を用いて全ての入来トラフィックのＩＰアドレスを収集し、分析する場合、サイト２５０は、インタフェース１５０Ａから到達する全２１６．０．０．０／８の５０％およびインタフェース１５０Ｂから到達する全２１６．０．０．０／８トラフィックの５０％を見込む。／８のプレフィックス長は、十分な粒度を提供せず、ＩＳＰ１１０のアドレス空間マップを生成する。ＩＳＰ１１０のアドレス空間マップは、地点２１５からのトラフィックと地点２２５からのトラフィックとを区別して、帰還ルーティングに対して最も最適なインタフェースを選択し得る。
【００５１】
しかし、ルーチング情報収集サイト２５０が、プレフィックス長／１６を使用して入来トラフィックを収集および解析する場合、異なる状態が生じる。この場合、サイト２５０は、インターフェイス１５０Ａから到着する１００％の全ての２１６．１００．０．０／１６トラフィックおよびインターフェイス１５０Ｂから到着する１００％の全ての２１６．２５．０．０／１６トラフィックであることを理解する。この粒度のレベルによって、サイト２５０は、点２１５（２１６．１００．５．０）への最も近いピアリング（ｐｅｅｒｉｎｇ）接続が接続１５０Ａであり、点２２５（２１６．２５．５．１）への最も近いピアリング（ｐｅｅｒｉｎｇ）接続が接続１５０Ｂであることを正確に判定することを可能にする。点２１５および点２２５からの現存するトラフィックフローに基づいて、これは、ＩＳＰ１１０のアドレス空間マップに対して十分な粒度である。トラフィックルーティングアドレスの粒度の増加プロセスは、「ルーチングデアグリゲーション」と呼ばれ、このプロセスは、ネットワークのアドレス空間マップの精度を改善するために使用される。
【００５２】
ＩＳＰ１００からのトラフィックフローが変化する場合、アドレス空間マップに対する要求された粒度が同様に変化し得ることが当業者に明白である。さらに、アドレス空間マップが１００％の全ての「最も近い接続」決定を解決することが必要である。動作的な観点から十分な粒度はより低い百分率の決定を用いて達成され得る。十分に詳述されたアドレス空間マップの生成は、ＢＧＰルーチング情報単独で依存するよりもより正確な「最良のルート」決定を可能にする。
【００５３】
（インテリジェントルーチングシステム）
（ａ．全システム構成）
図３は、本発明の実施形態におけるインテリジェントルーチングシステムの図である。インテリジェントルーチングシステム３００は、システム３００のアドレス空間マップを発達させ最良のルートを選好してシステム３００内で使用することによってルーチングを実行する。インテリジェントルーチングシステム３００は、ピアリングパートナ３４０、３４１、３４２、３４３、３４４、３４５、３４６、３４７、３４８、３４９、３５０、３５１、および３５２に接続されるバックボーン３１０からなる。各ピアリングパートナは、バックボーンへのアクセスポイントである１以上のＰｏｉｎｔｓ　ｏｆ　Ｐｒｅｓｅｎｃｅ（ＰＯＰ）を介してバックボーン３１０に接続する。またバックボーン３１０は、ネットワークオペレーションセンター（ＮＯＣ）３２０を含む。
【００５４】
バックボーン３１０は、３３０、３３１、３３２、３３３、３３４、３３５、３３６、３３７、および３３８の９つのＰＯＰを有する。バックボーン３１０は多少のＰＯＰを含み得ることが当業者に明らかである。各ピアリングパートナは１つ以上のＰＯＰに接続される。ピアリングパートナ３４０は、ＰＯＰ３３０および３３１に接続される。ピアリングパートナ３４１は、ＰＯＰ３３０、３３１および３３２に接続される。ピアリングパートナ３４２は、ＰＯＰ３３２、３３３および３３４に接続される。ピアリングパートナ３４３は、ＰＯＰ３３４および３３５に接続される。ピアリングパートナ３４４は、ＰＯＰ３３５、３３６および３３７に接続される。ピアリングパートナ３４５は、ＰＯＰ３３７および３３８に接続される。ピアリングパートナ３４６は、ＰＯＰ３３８および３３７に接続される。ピアリングパートナ３４７は、ＰＯＰ３３８、３３７および３３６に接続される。ピアリングパートナ３４８は、ＰＯＰ３３６および３３５に接続される。ピアリングパートナ３４９は、ＰＯＰ３３５、３３４および３３３に接続される。ピアリングパートナ３５０は、ＰＯＰ３３３および３３２に接続される。ピアリングパートナ３５１は、ＰＯＰ３３２、３３１および３３０に接続される。ピアリングパートナ３５２は、ＰＯＰ３３０に接続される。
【００５５】
バックボーン３１０は、多くの帯域幅の波長を搬送することが可能な大きい伝送線である。インテリジェントルーチングシステム３００はバックボーン３１０を使用して、地理的に離れた位置にわたって、例えば長距離伝送ウエブトラフィックを搬送する。一実施形態では、バックボーン３１０は、容量３２　ＯＣ−Ｉ９２レート信号線を用いて高密度波多重分割システム（ＤＷＤＭ）である。
【００５６】
各ピアリングパートナは、バックボーン３１０を行き来するトラフィックを搬送するための帯域幅を提供する。十分に接続された主要なキャリアおよびＩＳＰは、システム３００のネットワークを使用するために、インテリジェントルーチングシステム３００と契約（ｃｏｎｔｒａｃｔ）することによってピアリングパートナとなる。各ピアリングパートナは、所定量の最小帯域幅をインテリジェントルーチングシステムに提供し、最小数のＰＯＰにおけるバックボーンに接続するように要求され得る。ピアリングパートナは米国ネットワークキャリアおよびインターネットネットワークキャリアの両方からなり得る。
【００５７】
複数のピアリングパートナは、同じ地理領域に及び得る。しかし、各ピアリングパートナは、一般的にトポロジカルに独立している。すなわち、特定のＩＰアドレスは、２つの独立ピアリングパートナネットワークを介してマルチホームド（ｍｕｌｔｉ−ｈｏｍｅｄ）であり、到達可能でなければ、ネットワーク回路デスティネーションは独立している。従って、ピアリングパートナは、同じ地理領域に及び得るが、各ピアリングパートナネットワークは、トポロジカルに独立しており、固有である。
【００５８】
各ピアリングパートナは、特定のピアリングパートナを介して達成可能なＩＰアドレスのセットを含む。例えばピアリングパートナ３４６は、アドレス３０２を含む。ネットワークトラフィックをアドレス３０２に送信するために、ピアリングパートナ３４６のネットワークのいくつかの部分が使用される。図３は、ピアリングパートナとバックボーン３１０との間の接続を図示する。しかし、ピアリングパートナ自体の間のさらなる接続が存在することが当業者に明らかになる。典型的には、ピアリングパートナは、各ネットワーク間の１以上の接続を確立する。
【００５９】
１人以上のピアリングパートナー（ｐｅｅｒｉｎｇ　ｐａｒｔｎｅｒ）がインターネットの他の部分との中継接続を提供する。これらの中継接続は、インテリジェントルーティングシステム３００内に無いインターネットロケーションへのリンクを提供する。ピアリングパートナー３４３は、ＩＳＰ３８２への中継接続を有する。ピアリングパートナー３５０は、ＩＳＰ３８０への中継接続を有する。インテリジェントルーティングシステム３００内にはより多くの中継接続が作製されてもよいし、これより少なくてもよいことが当業者にとってあきらかである。さらに、インテリジェントルーティングシステム３００は、他の伝送制御プロトコル／インターネットプロトコル（ＴＣＰ／ＩＰ）ネットワークを用いてインプリメントされてもよく、インターネットの使用に限定されない。
【００６０】
１実施形態において、少なくとも４個のピアリングパートナーの各々が、最低、少なくとも９個のＰＯＰへの１つのＯＣ−３ライン接続（トラフィックを５１．８４Ｍｂｐｓ（１秒毎に１００万ビット、または１秒毎に１００万メガビット）で３度搬送する）を提供する。さらなるピアリングパートナーの各々は、最低、少なくとも３個のＰＯＰへの１個のＯＣ−３ライン接続を提供する。ピアリングパートナーのセットのうち、少なくとも２つは、インテリジェントルーティングシステム３００に接続されないインターネットの部分、または他のネットワークに接続する。潜在的ピアリングパートナーの例は、Ｓｐｒｉｎｇ（ＴＭ）、ＵＵＮｅｔ（Ｒ）およびＧＴＥ（ＴＭ）といった企業を含む。
【００６１】
バックボーン３１０上の各ＰＯＰは、バックボーン３１０へのアクセスポイントである。各ＰＯＰは、一意に定まるＩＰアドレスを有する。ＰＯＰは、バックボーン３１０に流れ込むトラフィックに関する情報を収集するために用いられる。ＮＯＣ３２０は、中央ロケーションであり、ここから、インテリジェントルーティングシステム３００が監視および維持される。各ＰＯＰにおいて集められたトラフィック情報は、ＮＯＣに周期的に送信され、このＮＯＣにおいて、情報が処理されてインテリジェントルーティングシステム３００のアドレススペースマップを生成する。このアドレススペースマップ情報は、システム３００にとってのインテリジェント「最良ルーティング」をＮＯＣによって決定する際に用いられる。
【００６２】
インテリジェントルーティングシステム３００を利用するために、カスタマ３９０は、アクセスポイントを介してＰＯＰのうちの１つ（図３におけるＰＯＰ３３２）に接続する。カスタマ３９０は、局在的接続回線または専用線といった、多数の異なったタイプの接続を用いてアクセスポイントに接続し得る。カスタマ３９０は、個人、法人または個々のＩＳＰであり得る。カスタマは、バックボーン３１０、およびシステム３００内の各ピアリングパートナーを用いるために、単一のＰＯＰを通じてインテリジェントルーティングシステム３００にのみ接続する必要がある。
【００６３】
図３において、ピアリングパートナーからＰＯＰへの各接続は、バックボーンとＩＳＰとの間の単一の接続を図示する。１実施形態において、ピアリングパートナーとバックボーンとの間の帯域幅を拡大するために、複数の接続が、ピアリングパートナーをＰＯＰサイトに接続し得る。複数の接続の実施形態において、ＢＧＰルートは、複数の接続にわたって同時に、かつ等しく広告（ａｄｖｅｒｔｉｓｅｄ）される。このＢＧＰルーティング方式（ｒｏｕｔｉｎｇ　ｐｅｒｓｐｅｃｔｉｖｅ）でいけば、ＩＳＰへのすべての接続のコストが等しいと思われる。
【００６４】
第１のＢＧＰ複数パス構成は、各物理的接続に対して別々のＢＧＰセッションを用いる。この構成において、ルーティングの機能がイネーブルされ、「マルチパス」と呼ばれる。通常、ＢＧＰは、最良のルートとして単一のルートを選択する。マルチパスは、同じ区域から習得された複数の等しいコストルートが順方向テーブルの中にインストールされることを可能にする。順方向テーブルにおける複数のエントリは、ルータに同じコストパスにわたってバランストラフィックをロードさせ、トラフィックバランスの目的を達成する。
【００６５】
第２のＢＧＰ複数パス構成は、すべての物理的接続に対して単一のＢＧＰセッションを用いる。この構成において、ピアリングパートナーの区域（ｎｅｉｇｈｂｏｕｒ）は、ピアリングパートナーのルータ上のループバックアドレスを用いてピアリングされる。さらに、各物理パスを介するループバックアドレスへのルートは、通常、静的ルートを介して、順方向テーブルの中に挿入される。その結果、バックボーンルータは、ピアリングパートナーから１つのルートを受け取るが、このルートへのパスは、複数の物理的接続により表される。従って、ルータは、すべての物理的接続を介してトラフィックをルートへ転送し、トラフィックバランスの目的を達成する。
【００６６】
ｂ）トラフィック情報モニタリングネットワーク
図４は、本発明の実施形態におけるインテリジェントルーティングシステムの部分４００の図示である。明瞭にするために、インテリジェントルーティングシステム３００全体は図示されない。しかしながら、図４に示されるシステムの部分は、全体としてインテリジェントルーティングシステム３００全体を表すものであることが当業者にとって明らかである。
【００６７】
システム４００は、１つ以上のＰＯＰのセット３３６、３３７および３３８に接続されるピアリングパートナーのセット３４８、３４４、３４５、３４６および３４７を含む。各ＰＯＰはＮＯＣ３２０に接続され、さらに、バックボーン３１０に接続される。システム４００は、ルートトラフィックフローを相互接続するルータのセットを含む。ルータは、さらに、これらのルート間で、例えば、ＢＧＰルートアナウンスメント等のルーティング情報を伝達し、ルータが受信するトラフィックを各ルータが配向することを可能にする。システム４００における選択されたルータも、インテリジェント「最良ルート」マネージメントを実行する際に用いるために、システム４００内のトラフィックフローに関する情報を収集する。
【００６８】
各ピアリングパートナーは、ピアリングパートナーのネットワーク内でトラフィックをルーティングするルータのセットを含む。明瞭にするために、ＰＯＰに接続するエッジルータのみが図４に示される。ピアリングパートナーは複数のルータを含むことが当業者により理解される。ピアリングパートナー３４８は、４１２ＡからＰＯＰ３３６に接続されるルータ４０２Ａを含む。ピアリングパートナー３４４は、４１２ＢからＰＯＰ３３６に接続されるルータ４０２Ｂ、および４１２ＣからＰＯＰ３３７に接続されるルータ４０２Ｃを含む。ピアリングパートナー３４５は、４１２ＤからＰＯＰ３３７に接続されるルータ４０２Ｄ、および４１２ＥからＰＯＰ３３８に接続されるルータ４０２Ｅを含む。ピアリングパートナー３４６は、４１２ＦからＰＯＰ３３７およびＰＯＰ３３８に接続されるルータ４０２Ｆを含む。ピアリングパートナー３４７は、４１２ＧからＰＯＰ３３６に接続されるルータ４０２Ｇ、４１２ＨからＰＯＰ３３７に接続されるルータ４０２Ｈ、および４１２ＩからＰＯＰ３３８に接続されるルータ４０２Ｉを含む。
【００６９】
接続４１２のセット（４１２Ａ−Ｉ）は、インテリジェントルーティングシステムをピアリングパートナーからＰＯＰに搬送する。接続４１２のセットは、さらに、ルートアナウンスメントを各ピアリングパートナーからＰＯＰに搬送する。アナウンスされたルートのセットは、ピアリング接続と中継接続とで異なる。ピアリング接続は、ピアリングパートナー同士の「ネット上（ｏｎ−ｎｅｔ）」ルートのみをアナウンスする。なぜなら、インターネット全体には、ピアリング接続を介して到達し得ないからである。「ネット上」接続は、有料カスタマのみへの接続であり、他のピアリング習熟（ｐｅｅｒ−ｌｅａｒｎｅｄ）ルートへの接続ではない。中継接続は、インターネット全体に到達可能性を提供し、通常、ＢＧＰルートのフルセットをアナウンスする。
【００７０】
ルートアナウンスメントを含むトラフィックは、２重機能を実行するルータ／コレクタを介して各ＰＯＰに到着する。各ルータ／コレクタは、トラフィックをバックボーン３１０におよびバックボーン３１０からルーティングし、さらに、システムを通って流れるトラフィックに関する情報を収集する。トラフィックはルータ／コレクタ４２０Ａを介してＰＯＰ３３６に到着し、トラフィックはルータ／コレクタ４２０Ｂを介してＰＯＰ３３７に到着し、トラフィックはルータ／コレクタ４２０Ｃを介してＰＯＰ３３８に到着する。
【００７１】
各ルータ／コレクタ４２０は、それ自体の中に流れるトラフィックをモニタリングし、ＩＰ統計データを収集するように改変されたルータである。ＩＰ統計データは、特定のピアリングパートナーからの、特定のＰＯＰにおける特定のＩＰアドレスレンジからどれだけ多くのネットワークトラフィックが受信されるかを記録する。ネットワークトラフィックは、ルータ／コレクタを通って流れるメッセージおよび信号の量を表し、パケットカウントとバイトカウントの両方について測定される。ＩＰ統計データは、各ルータ／コレクタ４２０のために設定された、特定の最小のプレフィクス長さでモニタリングされる。アドレスをモニタリングするための細分性は、用いられる最小のプレフィクス長さが変化することにより、各ルータ／コレクタ上で変更され得る。ルータ／コレクタ４２０の１実施形態は、Ｃｉｓｃｏ（Ｒ）ルータモデルＧＳＲ１２０１６（ギガビットスイッチルータ）であり、ルータソフトウェアは、ＩＰ統計データのために必要とされる情報を収集するように改変される。１実施形態において、Ｃｉｓｃｏ（Ｒ）ＮｅｔＦｌｏｗ製品の改変されたバージョンがＩＰ統計データを収集する際に用いられる。
【００７２】
アドレスマップを生成する際に用いられる統計データは、ＩＰパケットトラフィックに加えて、他のタイプのネットワーク信号トラフィックに関しても収集され得ることが当業者にとって明らかである。アドレスマップは、例えば、非同期転送モード（ＡＴＭ）信号等の、任意の数の異なったタイプの信号を用いるネットワークのために生成され得る。所望ならば、ネットワーク信号データのすべてがモニタリングされ得る。しかしながら、大量のトラフィックを有するネットワークにおいて、すべての信号をモニタリングすることは、扱い難い量のデータを生成し得る。あるいは、モニタリングは、サンプリングを用いて実行され得、これにより、収集されたデータの量を低減する一方で、ネットワーク全体にわたって、信号の正確なデータベースが送信されることを達成する。
【００７３】
さらに、信号トラフィックは、どの信号を測定するかを選択するいくつかの異なった方法を用いて、統計データ収集に関してモニタリングされ得る。１実施形態において、ピアリングネットワークを介して受信されるすべてのネットワークトラフィックに関するトラフィック統計がモニタリングされる。この方法は、高いトラフィック感度を有する。ルーティング決定は、トラフィックパターンにおける傾向の方向に偏る。従って、ルーティングポリシー（ｒｏｕｔｉｎｇ　ｐｏｌｉｃｙ）は、最も有益である場合にのみおそらくインプリメントされる。さらに、トラフィック統計は、単独でソース毎のネットワーク単位で集計され得、このことは、統計のオーバーヘッドを低減する。最後に、トラフィックは、受動的に測定され、統計的トラフィック測定を行なうために、さらなるトラフィックは生成されない。しかしながら、ほんの少しのトラフィックを生成するアドレススペースは、特徴付けが困難である。
【００７４】
別の実施形態において、トラフィック応答は、必要に応じて、アドレススペース全体にわたってアクティブに生成され、既存のネットワークトラフィックを補完する。この方法は、周囲のトラフィックが不十分であるアドレスマップにおけるギャップが満たされることを可能にする。しかしながら、この方法は、ネットワークにおけるアクティブな介入を必要とし、トラフィックの帯域幅を拡大する。さらに、トラフィックがサンプリング単位でモニタリングされる場合、アクティブに生成されたトラフィックは、周囲のネットワークトラフィックに比べて少量で生じる。従って、サンプリングは所望の結果の多くを削除し得る。
【００７５】
さらに別の実施形態において、アクティブに生成されたトラフィックのみがモニタリングされ、インテリジェントルーティングネットワークの外側の宛先に送信されたトラフィックはモニタリングされない。この方法は、モニタリングされるトラフィックの量を大幅に低減し、従って、おそらくサンプリングを使用する必要を無くす。この方法は、さらに、特定の領域におけるアドレススペースの割合の正確な概観（ｖｉｅｗ）を提供する。なぜなら、トラフィックは均一な配信において生成され得るからである。しかしながら、統計は、宛先によってフィルタリングするために、ソース毎のネットワークと宛先毎のネットワークの両方の単位で集計されなければならない。この方法において、起動ホストへの応答トラフィックのみが測定され、このことは、ルータ上で処理する統計に特定のオーバーヘッドを付加する。さらに、この方法は、トラフィック感度の損失を引き起こし得る。
【００７６】
各ルータ／コレクタ４２０はサーバ４５０に接続される。ルータ／コレクタ４２０Ａはサーバ４５０Ａに接続される。ルータ／コレクタ４２０Ｂはサーバ４５０Ｂに接続され、ルータ／コレクタ４２０Ｃはサーバ４５０Ｃに接続される。各サーバ４５０は、ＩＰ統計データをルータ／コレクタ４２０から受信し、さらに、ルータ／コレクタ４２０のルートテーブルを受信する。ルートテーブルは、通常、ＢＧＰテーブルであり、これはＢＧＰを介して受信されたすべてのルートをリスト出力する。ＢＧＰテーブルはルータの標準的インプリメント機能であり、正確なフォーマットはルータメーカ独自であるが、ＢＧＰテーブルは、通常、アドレスプレフィックス／マスク、および各プレフィックス／マスクについてのＢＧＰ属性を含む。ルートテーブルは、さらに、ＢＧＰ以外のルーティングプロトコルから取得したルーティング情報を含んでもよいことが当業者により理解される。
【００７７】
サーバ４５０は、収集されたＩＰ統計データおよびルートテーブル情報に関する処理を実行し、ＮＯＣ３２０のために周期的な情報の更新を準備する。各サーバ４５０により実行されるタスクは、代替的に、各ＰＯＰ上の複数のサーバ間で分割され得ることが当業者により理解される。
【００７８】
周期的に、各ＰＯＰは、ＩＰ統計データおよびルートテーブル情報に関する情報の更新をＮＯＣに送信する。各ＰＯＰは、情報の更新を提供するために、接続４２４を介してＮＯＣに接続される。ＰＯＰ３３６は、接続４２４Ａを介してＮＯＣ３２０に接続される。ＰＯＰ３３７は接続４２４Ｂを介してＮＯＣ３２０に接続され、ＰＯＰ３３８は接続４２４Ｃを介してＮＯＣ３２０に接続される。
【００７９】
ＮＯＣ３２０は、ＩＰ統計データおよびルートテーブル情報に関する情報の更新を、ルータ４２６を介して各ＰＯＰから受信する。情報の更新は、ＮＯＣ上のサーバ４５２に送信され、このサーバはさらに処理してインテリジェントルーティングシステム全体のコヒーレントなアドレススペースマップを生成し、システムにとっての「最良ルート」マネージメントを容易にする。ＮＯＣは、中央ルーティング決定をルーティングして、ＰＯＰを介してインテリジェントルーティングシステムに戻す。ＰＯＰは、その後、バックボーンネットワーク内の選好ルートにより、ＮＯＣの「最良ルート」マネージメント決定をインプリメントする。すなわち、インテリジェントルーティングシステム内で、選好されたルートが用いられるように指定する。ネットワークアドレススペースマップにおいて細分性の増大が所望されるＩＰアドレスレンジの分化（ｄｅａｇｇｒｅｇａｔｅｄ）されたルートも用いられる。
【００８０】
一般に、単一のピアリングパートナーからの単一のＰＯＰにおけるバックボーンネットワーク内への複数の接続（例えば、ピアリングパートナー３４８は、ＰＯＰ３３６への２つの物理的接続を有する）は、単一接続として扱われる。従って、選好することがルート上で選択される場合、リターントラフィックは、順方向トラフィックとピアリングパートナーとのすべての物理的接続を用いる。分化が行なわれる場合、トラフィックと分化された宛先との間のトラフィックは、すべての物理的接続を利用する。
【００８１】
あるルートが一度選好されると、このルートは、他の可能なルートよりもインテリジェントルーティングシステムによって用いられるように選択される。さらに、分化されたルートは、より特殊なルートを表し、このルートは、さらに、他の、より特殊でないルートよりも選択される。例えば、図３に戻って参照して、選好されたルートがＰＯＰ３３７を用いるピアリングパートナー３４６におけるアドレス３０２のために存在することを想定されたい。メッセージがアドレス３０２の宛先を有するＰＯＰ３３１に到着した場合、インテリジェントルーティングシステムネットワークは、バックボーン３１０上のメッセージをＰＯＰ３３１からＰＯＰ３３７にルーティングし、選好されたバックボーンルートをたどり、その後、メッセージは、ピアリングパートナー３４６を通ってアドレス３０２にルーティングされる。選好されたルートは、インテリジェントルーティングシステムネットワークルータに、十分なＢＧＰ情報を提供し、バックボーン３１０に従ってコールドポテト（ｃｏｌｄ−ｐｏｔａｔｏ）ルーティングを適切に実行する。
【００８２】
図５Ａおよび図５Ｂは、各ＰＯＰ上のルータ／コレクタにより収集された情報のタイプを図示する。図５Ａは、ＩＰ統計データテーブル５００の図示である。ＩＰ統計データテーブル５００は、各ＰＯＰで見出されるトラフィックフローをモニタリングするために用いられ、各ＩＰアドレスレンジにおいて受信されたトラフィックの量に関する情報をコンパイルする。ＩＰ統計データテーブル５００は、ＰＯＰにおいて受信された各ＩＰアドレスレンジの別個の記録エントリを生成する。ＩＰアドレスレンジはＩＰアドレスおよびマスクによって表される。別個のＩＰ統計データエントリは、さらに、異なったインターフェースまたは異なったＰＯＰに到着するトラフィックのために維持される。ＩＰアドレス上で用いられるマスクは、プレフィックスの長さに対応する。用いられるプレフィックスの長さは、用いられる「バケット（ｂｕｃｋｅｔ）」の細分性を決定し、このＩＰアドレスのためのＩＰ統計を収集する。ＩＰ統計データテーブル５００のエントリは、最小のプレフィックスの長さを有し、収集されたアドレスの細分性を設定するルータ／コレクタにおけるセットはデータを提供する。
【００８３】
例えば、１実施形態において、最小のプレフィックスの長さは、／２０に設定される。すべてのＩＰ統計データは、このアドレスマスクを用いて収集される。最小のプレフィックスの長さは、必要に応じて調整され得、アドレススペースマップの細分性を増大または減少させる。例えば、ＩＰ統計データが／３２マスクを用いて収集された場合、各個々のＩＰアドレスおよび対応するルートについて、別個のＩＰ統計データテーブル５００が生成される。これは、非常に大きいテーブル５００に至り、ネットワークアドレススペースに関する最も詳細な情報を提供する。
【００８４】
例えば、情報がＩＰアドレス１４０．１５０．１６．０からＰＯＰに送信されると想定されたい。／３２のプレフィックス（マスク１１１１１１１１．１１１１１１１１．１１１１１１１１．１１１１１１１１）が用いられた場合、ＩＰ統計データテーブル５００エントリは、１４０．１５０．１６．０の単一の個別ＩＰアドレスに対応する。しかしながら、／８のプレフィックス（マスク１１１１１１１１．００００００００．００００００００．００００００００）が用いられた場合、ＩＰ統計データテーブル５００エントリは、１４０の第１のカッドネットワークアドレス（１４０．１００．１６．０、１４０．０．０．０等）を有する個別ＩＰアドレスのレンジに対応する。
【００８５】
ＩＰ統計データテーブル５００は、さらに、トラフィックが到着するＰＯＰを示すエクスチェンジＩＤに追従する。同じＩＰアドレス、または異なったＰＯＰ上に到着するアドレスレンジを有するトラフィックは、別々に追従される。最初に、別個のＩＰ統計データテーブル５００が各ＰＯＰで生成される。従って、エクスチェンジＩＤは、ＩＰ統計テーブル５００が生成されたＰＯＰを反映する。１実施形態において、各エクスチェンジＩＤは、特定のＰＯＰに対応して割り当てられた番号である。
【００８６】
特定のネットワーク接続を表すインターフェースの番号は、さらに、各ＩＰ統計データテーブル５００エントリに追従される。インターフェース番号は、特定のピアリングパートナーに接続される物理ルータインターフェースを識別する。ＩＰ統計が収集されると、トラフィックを送信するピアリングパートナーは、各個別ＩＰ統計データテーブル５００エントリと関連するインターフェース番号を介して識別され得る。例えば、マルチホーム（ｍｕｌｔｉ−ｈｏｍｅｄ）カスタマは、２つの異なったピアリングパートナーを介してトラフィックを送信し得る。このような場合、異なったピアリングパートナーから到着するトラフィックは、異なったインターフェース番号により区別され得る。中継接続の場合、インターネットアドレススペース全体には中継インターフェースを介して到達可能である。
【００８７】
ＩＰ統計データテーブル５００は、インテリジェントルーティングシステムネットワークの種々の部分へと流れるトラフィックの量に関するＰＯＰルータ／コレクタからの統計をコンパイルするために用いられる。ネットワークトラフィックは、ネットワーク全体にわたって送信されるメッセージまたは信号を含む。バイトカウントは、特定のＩＰ統計データエントリ（特定のアドレスレンジに対応する）に関する、ルータ／コレクタにより受信されたバイトの総数に追従する。パケットカウントは、特定のエントリに関する、ルータ／コレクタにより受信されるパケットの総数に追従する。
【００８８】
ＩＰ統計データテーブル５００強度変数（ｓｔｒｅｎｇｔｈ　ｖａｒｉａｂｌｅ）は、特定のＩＰ統計データテーブル５００エントリに与えられる重みを決定する数である。与えられたＩＰアドレスレンジの強度は、通常、より多くのトラックが特定のソースのＩＰアドレスレンジから受信されると増加する。強度変数は、調整され得、インテリジェントルーティングシステム用のアドレススペースマップの計算における各エントリの使用を変更する。強度変数は、ローパスフィルタ閾値との関連でさらに議論される。
【００８９】
関連するルートエントリへのＩＰ統計データテーブル５００ポインタは、ルートエントリテーブル５１０における対応するルートエントリを参照するデータメモリポインタである。ポインタは、ルートエントリテーブル５１０における、最も特殊または最も分化された、対応するＩＰアドレスレンジを参照する。ルートエントリテーブル５１０における対応するルートエントリは、ルート処理中に決定される。このとき、ＩＰ統計データテーブル５００およびルートエントリテーブル５１０は相互に関連する。
【００９０】
図５Ｂは、ルートエントリテーブル５１０の実施形態の図示である。各ＰＯＰは、特定のＰＯＰにおいて現在広告されるルートに対応するルートエントリテーブルを生成する。さらなるルートが、ルートの分化が原因で付加され、ルートの集合化が原因で削除され、あるいはインテリジェントルーティングシステムネットワーク上のピアリングパートナーから付加されるか、または取り除かれると、ルートテーブル５１０エントリは変化する。ルートエントリテーブル５１０におけるエントリのリストは、ＰＯＰにおける各ルータ／コレクタＢＧＰルートにおけるＢＧルートテーブルから直接的に取得される。しかしながら、各ルートエントリに関するさらなる情報は、データをＩＰ統計データテーブル５００と相互に関連させた後、およびＰＯＰおよびＮＯＣにおける他の処理の後に計算される。
【００９１】
ルートエントリテーブル５１０は、ＩＰアドレス、マスク、プレフィックス、エクスチェンジＩＤ、および各ルートエントリ毎のインターフェースの数を含む。ルートエントリテーブル５１０は、さらに、「ネクストホップ（ｎｅｘｔ　ｈｏｐ）変数を含む。この変数は、ルータにおける、そのアドレスレンジの次のルータの全３２ビットＩＰアドレスである。例えば、ＰＯＰ３３０が「１４０．１５０．０．０」のＩＰアドレスレンジに対して「１４０．１００．１．１」のネクストホップアドレスを有する場合、ＰＯＰ３３０からＩＰアドレスレンジ１４０．１５０．０．０に到達するために、ＰＯＰ３３０ルータは、トラフィックを１４０．１００．１．１に配置されるルータに送信する。ルートエントリテーブル５１０におけるＡＳ＿パスは、特定のルートと関連するＡＳ＿パスコスト測定基準（ｃｏｓｔ　ｍｅｔｒｉｃ）を表す。ＭＥＤは、特定のルートと関連するＭＥＤコスト測定基準を表す。ＩＰアドレス、マスク、プレフィックスの長さ、エクスチェンジＩＤ、インターフェース数、ネクストホップおよびコスト測定基準変数は、すべて、各ＰＯＰルータ／コレクタのＢＧＰルートテーブルから取得される。
【００９２】
ルートエントリテーブル５１０は、さらに、ピアＩＤを含む。これは、各ピアリングパートナー接続または負荷バランシングされた（ｌｏａｄ−ｂａｌａｎｃｅｄ）接続の群に割り当てられる数である。ピアＩＤは、各ＰＯＰにおいて実行される処理の部分として計算される。これは、次のホップフィールド、およびそのＰＯＰにおける各ピアと関連するネクストホップを特定するＰＯＰ構成ファイルに基づく。
【００９３】
ステータスフラグのセットは、ルートに関する、および最良ルートマネージメント解析プロセスにおいてどのように用いられるかに関する情報を提供する。各ステータスフラグは、１ワードが３２ビットのビット形式で表される。図６〜図１２に関してさらに説明されるように、ステータスフラグは、データ収集およびルート処理中に設定される。例示的ステータスフラグのセットは以下のように与え有られる：
ＮＯ＿ＩＮＴＥＲＦＡＣＥ　　　　ルートは選択されない。なぜなら、どのインターフェースも関連付けられ得ないからである。
【００９４】
ＣＯＭＢＩＮＥＤ　　　　　　　　ルートは選択されない。なぜならこれは別のルートに組合されたからである。
【００９５】
ＤＵＰＬＩＣＡＴＥ　　　　　　　ルートは選択されない。なぜなら、これは別のルートの複製だからである。
【００９６】
ＴＲＡＮＳＩＴ　　　　　　　　　ルートは中継ルートである。
【００９７】
ＰＲＥＦＩＸ＿ＬＥＮＧＴＨ　　　プレフィックスの長さがフィルタリングされるために、ルートは選択されない。
【００９８】
ＵＮＩＱＵＥ　　　　　　　　　　一意に定まるエントリがフィルタリングされるために、ルートは選択されない。
【００９９】
ＢＥＬＯＷ＿ＴＨＲＥＳＨＯＬＤ　ルートは選択されない。なぜなら、そのパケットカウントが閾値未満であったからである。
【０１００】
ＨＯＮＯＲ＿ＡＳ　　　　　　　　ルートは選択されない。なぜなら、ＡＳパスが受け付けられ（ｈｏｎｏｒｉｎｇ）、これが違反（ｖｉｏｌａｔｅ）されるからである。
【０１０１】
ＨＯＮＯＲ＿ＭＥＤ　　　　　　　ルートは選択されない。なぜなら、ＭＥＤが受け付けられ、これが違反されるからである。
【０１０２】
ＳＥＬＥＣＴＥＤ＿ＮＡＴＵＲＡＬ　　ルートは選択されない。なぜなら、ＢＧＰがどのみちこれを選択するからである。
【０１０３】
ＳＥＬＥＣＴＥＤ＿ＩＮＪＥＣＴ　　　ローカル選好が行なわれるように、ルートは選択されない。
【０１０４】
ＰＲＥＦＥＲＲＥＤ＿ＴＲＡＮＳＩＴ　ルートは、中継ルートであり、これも選好される。
【０１０５】
ＤＥＡＧＧＲＥＧＡＴＥＤ　　　　　　ルートは分化されている
ＬＯＷ＿ＰＡＳＳ　　　　　　　　　　ローパスフィルタリングであるため、ルートは選択されない
ＡＳ＿ＥＸＣＬＵＳＩＯＮ　　　　　　ルートは選択されない。なぜなら、そのＡＳパスはＡＳを除外するからである。
【０１０６】
ＬＩＮＧＥＲＩＮＧ　　　　　　　　　ルートは選択されなかったが、この反復、但し、ローパスフィルタはこれを保持する
ＰＥＮＤＩＮＧ＿ＷＩＴＨＤＲＡＷ　　ルートが照合され得ない場合、ルートは除去を保留する
ＷＩＴＨＤＲＡＷＮ　　　　　　　　　ルー取り除かれた
ＭＯＲＥ＿ＳＰＥＣＩＦＩＣ＿ＰＥＥＲ　　ルート分化は、別のピア上のより特殊なルートによって回避される
これらのステータスフラグうちの特定のフラグは、通常、最初のデータ収集およびデータコンソリデーション（ｄａｔａ　ｃｏｎｓｏｌｉｄａｔｉｏｎ）中に設定される。例えば、ＮＯ＿ＩＮＴＥＲＦＡＣＥステータスフラグは、インターフェースがルートと関連付けられ得ない場合に設定される。インターフェースの関連の欠如は、ルートが好適なルートとして選択されることを回避する。ＣＯＭＢＩＮＥＤ、ＤＵＰＬＩＣＡＴＥ、およびＴＲＡＮＳＩＴステータスフラグも、最初のデータ収集およびコンソリデーション中に設定される。
【０１０７】
任意に、大きさの限界がプレフィックス／マスクに設けられ得、使用される用いられたルートのボリュームを制限する。ルートが最大プレフィックス／マスクの大きさの限界を超過したために、ルートがフィルタリングアウトされた場合、ＰＲＥＦＩＸ＿ＬＥＮＧＴＨフラグが設定される。特定のＩＰアドレスに対応するすべてのルートが同じインターフェースを介して取得された場合、ＵＮＩＱＵＥフラグが設定され得る。ＵＮＩＱＵＥフラグが設定されたルートは、インテリジェントルーティング計算から除去され得る。なぜなら、そのＩＰアドレスの宛先を獲得する方法は１つのみだからである。インテリジェントルーティングシステムの１実施形態において、ＵＮＩＱＵＥステータスフラグは用いられない。
【０１０８】
ルート処理中のステータスフラグセットは、ルート処理アクションに対応するテクストにおいて後述される。上述のステータスフラグのリストは、例示にすぎないことが当業者により理解される。多少の情報がルートエントリテーブル５１０におけるエントリと一緒に追従され得る。
【０１０９】
各ルータ／コレクタからのＢＧＰと、各ルータ／コレクタからのＩＰ統計データテーブル５００とが相互に関連付けられた後、ルートエントリテーブル５１０におけるパケットカウントおよびバイトカウントフィールドは、ルートエントリテーブル５１０に付加される。強度フィールドは、さらに、各ＰＯＰにおける処理中に付加される。
【０１１０】
（ルート処理および選択）
図６は、インテリジェントルーティングシステムにおいてルート情報をモニタリングおよび配信するための全体的なプロセス６００のフローチャートである。ルート処理は、各ＰＯＰとＮＯＣの両方において実行される。ＰＯＰ（７００）におけるルート処理は、プロセス６００の工程６１０〜工程６４０を含み（図７により詳細に示される）、ＮＯＣ（８００）におけるルート処理は、プロセス６００の工程６５０〜工程６９０を含む（図８により詳細に示される）。１実施形態において、ＮＯＣは、１日に１度更新される。ＮＯＣの更新は、多かれ少なかれ周期的に実行され得ることが当業者に明らかである。
【０１１１】
各ＰＯＰにおいて、外部ＢＧＰルート情報が収集される（６１０）。外部ＢＧＰルート情報は、上述のように、各ＰＯＰにおけるルータ／コレクタのルートテーブルから収集される。ＩＰ統計データは、さらに、各ＰＯＰにおいて収集され（６２０）、ＩＰ統計データテーブル５００を生成する。ＢＧＰルート情報およびＩ統計データは、その後、相互に関連付けられ（６３０）、ルートエントリテーブル５１０を生成する。
【０１１２】
関連付け（６３０）中に、各エントリテーブル５１０のエントリに対応するＩＰ統計データテーブル５００のエントリは、パケットカウントおよびバイトカウントフィールドを満たすために用いられる。必要ならば、複数のＩＰ統計データテーブル５００エントリからのトラフィックフローが組合され、特定のルートエントリに関するパケットカウントおよびバイトカウント全体を提供する。例えば、ＩＰ統計データテーブル５００が、ＩＰアドレスレンジ１４０．１５０．１．０／２４および１４０．１５０．３０．０／２４に関するエントリを有する場合、これらの２つのＩＰ統計アドレスエントリと相互に関連する特定のルートがもはや存在しないならば、これらの２つのエントリからのパケットカウントおよびバイトカウントは組合され、１４０．１５０．０．０／１６のルートエントリテーブル５１０ＩＰアドレスレンジと相互に関連付けられる。工程６４０に示されるように、工程６１０〜６３０は、ＰＯＰの各々において繰返される。
【０１１３】
ＩＰ統計データテーブル５００、および各ＰＯＰからのルートエントリテーブル５１０は、その後、ＮＯＣに送信され、ここで、復号ＮＯＣ　ＩＰ統計データおよびルートエントリテーブルが形成される（６５０）。ＮＯＣ　ＩＰ統計およびルートエントリテーブルデータは、その後、再び互いに関連付けられ（６６０）、クロスＰＯＰ情報を説明する。ルート選好セレクション論理値６７０がインプリメントされ、インテリジェントルーティングシステムネットワークのバックボーン内で最良のルートを選好する。ルート分化選択論理値６８０がインプリメントされ、アドレススペースマップ細分性を改善する。これは、カスタマにアナウンスされるより特殊なルートを用い、これにより詳細なＩＰ統計データを生成することによって行なわれる。
【０１１４】
結果として生じたルート情報は、その後、配信され（６９０）ＰＯＰに戻される。ここから、このルート情報は、インテリジェントルーティングシステムネットワーク内で配信される。各ＰＯＰは、個別のエクスチェンジＩＤ番号を有し、各ＰＯＰは、エクスチェンジＩＤフィールドを用いて、その関連するルートをＮＯＣマスターファイルから選択する。ルート情報は、各個別のＰＯＰにおいてルーティングポリシーをインプリメント（６９５）するために用いられる（プロセス１１００Ａおよび１１００Ｂによる１実施形態において、およびプロセス１１００Ｃによる別の実施形態に示されるように）。
【０１１５】
図７は、各ＰＯＰにおいて実行されるルートおよびトラフィックフローの処理（７００）の、より詳細なフローチャートである。各ＰＯＰにおけるトラフィックデータは、ルータ／コレクタによりモニタリングされ、ルータ／コレクタに接続されるサーバにおいて処理されるように蓄積される。ＮＯＣに送信されるべきデータテーブルは周期的に更新される。
【０１１６】
外部ＢＧＰルートは、ルータ／コレクタから読み出される（７１０）。累積的ルートエントリテーブル５１０は更新される（７２０）。現在のＩＰ統計ファイルは、ＩＰ統計リーダから取得（７３０）および格納される。ＩＰ統計ファイルは、ルータ／コレクタから読み出された未処理トラフィック情報を含み、どのルートもこの時点ではコンソリデート（ｃｏｎｓｏｌｉｄａｔｅ）または廃棄されない。１実施形態において、ＩＰ統計リーダは、ルータ／コレクタからトラフィック情報レポートを読み出し、トラフィック情報レポートに基づいた、対応するＩＰ統計データテーブル５００を生成するように構成されるソフトウェアモジュールである。
【０１１７】
プロセス７００は、７４０を点検し、最終のデータ更新期間に達したかどうかを見出し、ＩＰ統計データテーブル５００およびルートエントリテーブル５１０を更新するときかどうかを決定する。最終データ更新期間に達していない場合、プロセス７００は、工程７１０に戻り、ルートおよびＩＰ統計データを取得することを継続する。通常、工程７１０〜工程７３０は１日に複数回実行され、工程７４０は１日に１度だけ最終データ更新期間に達する。
【０１１８】
最終データ更新期間に達した場合、プロセス７００は、工程７５０に進み、ＩＰ統計データおよびルートエントリデータの処理を開始する。未処理のＩＰ統計情報は、読み出され（７５０）、ＩＰ統計データテーブル５００におけるインクルージョンのためにフィルタリングされる。最小パケットカウント数はＩＰ統計データテーブル５００エントリを生成するために必要とされ、データがほとんど使用されない擬似ルート上のデータが蓄積することを回避する。ルートエントリテーブル５１０に存在しないルートをリスト出力するＩＰ統計ファイルもフィルタリングアウトされ、例外として格納される。例外は、例えば、ルーティング障害またはルートスプーフィングを示し、ハードウェア障害またはピアリングパートナーのネットワーク内の障害を識別する際に有用である。例外は、カウントされ、別々のファイルに格納される。
【０１１９】
ＩＰ統計データテーブル５００は、さらに、工程７５０において、ルートテーブル５１０と相互に関連付けられる。パケットカウントおよびバイトカウントは、ＩＰ統計データテーブル５００からの情報を用いて、各ルートエントリテーブル５１０リスト項目に添付される。ＩＰ統計データテーブル５００エントリは、リスト項目の中で可能な最も特殊なルートテーブル５１０と相互に関連付けられる。
【０１２０】
例えば、以下のＩＰ統計データテーブル５００エントリが存在することを想定されたい。
【０１２１】
【表２】
2004508743.tif 000004
さらに、以下の２つのルートテーブル５１０リスト項目が存在することを想定されたい。
【０１２２】
【表３】
2004508743.tif 000005
１００のＩＰ統計パケットカウントは、ルートテーブル５１０リスト項目１４０．１５０．１６．０／２０にのみ割り当てられる。しかしながら、この／２０ルートリスト項目が存在しなかった場合、１００のＩＰ統計パケットカウントは、その後、目標のＩＰ統計エントリに対応する最も特殊な既存のルートとしてのルートリスト項目１４０．１５０．０．０／１６に割り当てられる。
【０１２３】
ファイルはＮＯＣに更新を送信するための準備において格納される（７６０）。格納されたファイルは、ＩＰ統計データテーブル５００、ルートエントリテーブル５１０、例外ファイル、およびインターフェース毎に例外の数を識別するインターフェース統計ファイルを含むフィルタリングされたＩＰ統計を含む。インターフェース統計ファイルは、特定の障害を有するピアリングパートナーを識別する際に有用である。ＰＯＰにおけるルート処理は、その後、終了する（７７０）。ＰＯＰデータは、ここで、ＮＯＣに送信される準備ができている。
【０１２４】
図８は、ＮＯＣにおいて実行されるルートおよびトラフィックフロー処理８００のより詳細なフローチャートである。各ＰＯＰから収集されたデータは解析され、選好されるネットワークルートと、さらなるインテリジェントルーティングシステムアドレススペースマップ情報を獲得するために分化されるルートとを識別するようにする。
【０１２５】
ＮＯＣは、ルートエントリテーブル５１０およびＩＰ統計データテーブル５００を各ＰＯＰから受信する（８１０）。ＮＯＣは、各ＰＯＰからのデータを用いてマスタールートエントリテーブル５１０を形成する（８１２）。ＮＯＣは、その後、各ＰＯＰからの個別ＩＰ統計データテーブルを用いて、マスターＩＰ統計データテーブル５００を形成する（８１４）。マスターＩＰ統計データテーブル５００は、包括的ルートエントリテーブル５１０に存在しないルートをリスト出力するＩＰ統計ファイルをフィルタリングアウトする。マスターＩＰ統計データテーブル５００の関連するルートエントリを示すポインタは、包括的ルートエントリテーブル５１０を示すように変更される。
【０１２６】
次の処理は、工程８２０〜８２８におけるマスタールートエントリテーブル５１０、および工程８４０〜８４８におけるマスターＩＰ統計データテーブル５００を用いて進行する。マスターＩＰ統計データテーブル５００処理（工程８４０〜工程８４８）は、工程８２２において生成されたマスタールートエントリテーブル５１０からの情報を用いる。従って、処理工程は、工程８２０および工程８２２が実行された後、いくつかの異なった順序で進行し得る。１実施形態において、工程８２２の後に存在する、マスタールートエントリテーブル５１０からの情報を必要とするマスターＩＰ統計データテーブル５００（工程８２０〜８２８）を用いる処理は、マスタールートエントリテーブル５１０上で処理工程８２４〜８２８を完了する前に、まず実行される。この実施形態において、ステップは以下の順序で実行される。すなわち、工程８１０〜工程８２２、工程８４０〜工程８４８、およびその後、工程８２４〜工程８２８、次に工程８５０および工程８５２である。
【０１２７】
別の実施形態において、工程８２２の、もとのマスタールートエントリテーブル５１０のコピーが生成され、マスターＩＰ統計データテーブル５００を処理する際に用いられる（工程８４０〜８４８）一方で、処理は、マスタールートエントリテーブル５１０上で進行する（工程８２４〜８２８）。これは、いくつかの処理が同時に実行されることを可能にする。工程８１０〜工程８２２が実行された後、工程８２４〜工程８２８および工程８４０〜工程８４８が、少なくとも部分的に同時に実行され、次に工程８５０および工程８５２が続く。
【０１２８】
工程８２０、工程８２２、工程８２４、工程８２６および工程８２８は、マスタールートエントリテーブル５１０上の処理を含む。ＮＯＣは、ピアリングパートナーのルーティングにおける非効率を識別するために、すべての中継ネクストホップのリストを読み出す（８２０）。ルートエントリテーブル５１０のＢＧＰルーティング情報は、ルートの作成、および通過されるルートをネットワーク接続するものを識別する。中継ネクストホップのリストが与えられると、ＮＯＣは、例えば、第１のピアリングパートナーが第２のピアリングパートナーを用いてバックボーンにアクセスすることを識別できる。このようなルーティング非効率をピアリングパートナーにより識別することは、インテリジェントルーティングシステムが非効率的なピアリングパートナーとともに動作し、非効率を解決することを可能にする。
【０１２９】
ＮＯＣは、その後、ルートエントリテーブル５１０におけるすべてのＩＰアドレスレンジリスト項目を通じて反復（８２２）し、図９に示されるルート選好選択プロセス９００により各リスト項目を処理する。ルート選好選択プロセス９００は、同じＩＰアドレスおよびマスクに対応するルートの各セットを分類する。選好プロセス９００は、１つの群における各ルートの属性を比較し、最良のルートを選好し、特定のＩＰアドレスおよびマスクのために用いる。
【０１３０】
例えば、図５Ｂにおいて、３つの異なったルートが、同じＩＰアドレス（１４０．１５０．０．０）およびマスク（／１６プレフィックスの長さ）に対応するルートエントリテーブル５１０においてリスト出力される。これらの３つのルートは、ルート群を含む。ルート群内の３つのルートは、ＡＳ＿パス、ＭＥＤおよびパケットカウントといった異なる属性を有する。ルート選好選択プロセスは、可能ならば、マスタールートエントリテーブル５１０内で選択されたステータスフラグを設定することにより、ルート群における３つの別項のルートの中から好適なルートを選択する。
【０１３１】
マスタールートエントリテーブル５１０のルートは、ステータスフラグによりフィルタリングされる（８２４）。「ＳＥＬＥＣＴＥＤ＿ＩＮＪＥＣＴ」ステータスフラグが活性化されたこのようなルートのみが「現在の選好されたルート」リストとして保存される。これらの選好されたルートは、好適なバックボーンルートとしてのインテリジェントルーティングシステムネットワークの中に用いられるように指定されるルートである。
【０１３２】
選好ルートは、その後、ＡＳ排他によりフィルタリングされる（８２６）。ＡＳ＿ＥＸＣＬＵＳＩＯＮステータスフラグは、ピアリングパートナーが広告するルートだけが残され、変化しないことをピアリングパートナーが特に要求する場合に設定される。この方法で、ピアリングパートナーは、それが所望し、インテリジェントルーティングシステムがこれらのルートを変更しないならば特定のルートを固定できる。フィルタリングされたルートは、現在の選好されたルートのリストから除去される。
【０１３３】
現在の選好されるルートは、その後、ローパスフィルタリングされる（８２８）。ローパスフィルタリング工程８２８は、間欠ＩＳＰトポロジー変化からのノイズ、あるいは不安定または非常駐のルートをフィルタリングアウトすることによりフラッピングするルートからのノイズを削除することを支援する。すべての前に選好されたルートのマスター選好ルートリストが維持される。現在の好適なルートリストは、マスター選好ルートリストと対照して点検される。マスターリストに現れない現在のリストに現れるルートは、マスターリストに付加され、比較的低い強度値が与えられる。さらにマスターリストに現れる現在のリストに現れるルートは、それらの強度値を値が増加したマスターリストに有する。現在のリストに現れないマスターリストに現れるルートは、マスターリストにおけるそれらの強度値の値が減少される。１実施形態において、強度値は、０と１との間で変動する。特定の閾値より大きい強度を有する選好ルートのみが、「好適なルート」出力ファイルにおける工程８５０に手渡される。ローパス閾値は、例えば、ルート選好のために必要とされる時間を増加または減少させ、インテリジェントルーティングシステム上の新しいルートに応答して変化するように変更され得る。ローパスフィルタリングが原因で選択されないルートは、そのＬＯＷ＿ＰＡＳＳステータスフラグが設定される。ＬＩＮＧＥＲＩＮＧステータスフラグも設定される。適用可能であれば、現在の選好ルートリストに存在しなかったとしても、ルートは、ローパスフィルタリングの後、依然として「好適なルート」出力ファイルに含まれることを示す。
【０１３４】
工程８４０、８４２、８４４、８４６および８４８は、マスターＩＰ統計データテーブル５００におけるエントリに関する処理を含む。ＮＯＣは、マスターＩＰ統計データテーブル５００におけるすべてのエントリを通じて反復し、図１０に示されるルート分化選択プロセス１０００により各エントリを処理する（８４０）。ルート分化選択プロセス１０００は、ＩＰ統計データテーブル５００エントリを、同じＩＰアドレスレンジの異なったルートに対応して、ルートテーブル５１０エントリの分類と類似して各セットを分類する。分化ルートとして用いられるべきでないＩＰ統計エントリは、フィルタリングアウトされ、テーブルから削除され、現在の分化リストを生成する。ルート分化選択プロセス１０００中に、分化のために選択されたＩＰ統計エントリと関連する特定の親ルートの、ＤＥＡＧＧＲＥＧＡＴＥＤステータスフラグが設定される。ルートテーブルエントリは、ＤＥＡＧＧＲＥＧＡＴＥＤステータスフラグ上でフィルタリングされ（８４２）、ＤＥＡＧＧＲＥＧＡＴＥＤと付されたルートは、「分化ルートと関連するルートエントリ」出力ファイルを生成するために用いられる。
【０１３５】
ＮＯＣは、現在の分化リストおよび分化ルートファイルと関連するルートエントリを取得し、ＡＳ＿ＥＸＣＬＵＳＩＯＮステータスフラグにより分化されるべきルートのリストを、工程８２６において実行されたフィルタリングと類似にフィルタする（８４４）。
【０１３６】
ＮＯＣは、その後、分化リストおよび関連するルートエントリファイルを、工程８２８で実行されたフィルタリングと類似にローパスフィルタする（８４６）。ローパスフィルタ工程は、ノイズをトポロジー変化またはルートフラッピングから削除することを支援する。強度変数は、現在の分化リスト上のルートが前の分化リスト上に現れたかどうかを反映する。すべての前に分化されたルートのマスター分化リストは維持される。現在の分化リストは、マスター分化リストと対照して点検される。マスターリストに現れない現在のリストに現れるルートは、マスターリストに付加され、比較的低い強度値が与えられる。さらにマスターリストに現れる現在のリストに現れるルートは、マスターリストにおける強度値の値が増加される。現在のリストに現れないマスターリストに現れるルートは、マスターリストにおける強度値の値が低減される。１実施形態において、強度値は、０と１との間で変動する。特定の閾値より大きい強度を有する分化ルートのみが、「分化ルート」出力ファイルにおける工程８４８に手渡される。ローパスフィルタリングが原因で選択されないルートは、ＬＯＷ＿ＰＡＳＳステータスフラグが設定される。
【０１３７】
分化ルート出力ファイルに残存するルートは、分化され（８４８）、ここで、アドレス群のセットを大きいアドレスレンジ内に折り畳むことが可能である。例えば、ＩＰ統計の最小プレフィックスの長さが／２０であることを想定されたい。分化に関して表示された４つの／２０アドレスエントリが同じルートを参照する場合、これは４つの異なった／２０アドレスが、インテリジェントルーティングシステムネットワークのトポロジーのアドレススペースマップにおいて近接して配置されることを示す。このような場合、これらの４つの異なった／２０分化ルートを、例えば、単一の／１８分化ルート内に集合させることがより効率的である。集合は、効率化のために行なわれ、ルーティングテーブルの大きさが不必要に無用に増加することを回避する。
【０１３８】
選択された出力ファイルは格納され、工程８５０におけるＰＯＰに伝送される。選択された出力ファイルは、好適なルートファイル、分化ルートファイル、および選択されないルートエントリである。ＮＯＣ処理は、その後、終了する（８５２）。
【０１３９】
図９は、ルート選好選択プロセス９００の流れ図である。ルート選好選択プロセス９００は、好適バックボーンルートとしてインテリジェントルーティングシステムネットワーク内で選好されるようにマスタールートエントリーテーブル５１０からルートを選択する。ルート選好選択プロセス９００は、マスタールートエントリーテーブルから、同じアドレス範囲（すなわち、同じＩＰアドレスおよびマスク）に対応するルートの各セットをグループ分けする。各ルートグループは一緒に処理され、最適ルートが自然に選択されるか、または、最適ルートが確実に選択されるように最適ルートを選好する必要があるかを判断するための比較をグループ内で行う。
【０１４０】
ルート選好選択プロセス９００は、ルートグループを選択し、そのグループ内のそれぞれのルートエントリーを処理する。プロセス９００は、次いで、次のルートグループを選択し、未処理のルートグループがなくなるまでこのサイクルを繰り返す。
【０１４１】
ＮＯＣの管理者は、特定のネットワーク構成パラメータを設定することによって、プロセス９００に影響を及ぼす。これらのネットワーク構成パラメータは、ルートを選好するかどうかを判断するためにＮＯＣルート選好選択プロセス９００がＡＳ＿ＰａｔｈおよびＭＥＤ　ＢＧＰパラメータの受け付けを要求するかどうかを判断する。一実施形態において、ＭＥＤおよびＡＳ＿Ｐａｔｈ属性の受け付けは保証されず、インテリジェントルーティングシステムは、ピアリングパートナーが提案する好適ルート候補に関わりなく、ＮＯＣにおいてルーティングを決定することが可能になる。
【０１４２】
第１のルートグループ内の第１のルートが選択（９０５）される。ＢＥＬＯＷ＿ＴＨＲＥＳＨＯＬＤステータスフラッグが設定（９１０）される。このステータスフラッグは、ルート選好を保証する対象ルートに関連するパケットが十分あることが分かると、プロセス９００の後になってクリアされる。ＳＥＬＥＣＴＥＤ＿ＮＡＴＵＲＡＬステータスフラッグがクリア（９１２）される。ＳＥＬＥＣＴＥＤ＿ＮＡＴＵＲＡＬステータスフラッグは、その関連ルートがＢＧＰによって自然に選択されるかどうかを示す。ステップ９１４〜９５２において、ＭＥＤおよびＡＳ＿Ｐａｔｈ　ＢＧＰパラメータをルートグループ内で比較して、グループ内の「最適」ルートが自然に選択されるかどうか、または、最適ルートを選択するために最適ルートを選好する必要があるかどうかを判断する。
【０１４３】
プロセスは、ＭＥＤの受け付けが要求されているかどうかをチェック（９１４）する。告知されたルートＭＥＤ属性の受け付けを要求するかどうかの判断は、ＭＥＤネットワーク構成パラメータの受け付けを設定するＮＯＣの管理者によって行われる。ＭＥＤの受け付けが必須でない場合、プロセスはステップ９２０に進む。ＭＥＤの受け付けが必須である場合、プロセスは、第１の選択されたルートがＭＥＤに反するかどうかをチェック（９１６）する。ＭＥＤに反しない場合、プロセスはステップ９２０に進む。しかし、ルートがＭＥＤに反する場合、プロセスは、ＨＯＮＯＲ＿ＭＥＤステータスフラッグを設定（９１８）して、ＭＥＤに反するためこのルートを禁止し、システムがＭＥＤの要求を選択したことを知らせる。プロセスは、次いで、ステップ９２０に進む。
【０１４４】
プロセスは、対象のルートがそのルートグループ内の最短のＡＳ＿Ｐａｔｈを有するかどうかを判断（９２０）する。対象のルートが最短のＡＳ＿Ｐａｔｈを有さない場合、プロセスは、インテリジェントルーティングシステムにおいてＡＳ＿Ｐａｔｈ属性の受け付けが必須であるかどうかを判断（９２２）する。告知されたルートのＡＳ＿Ｐａｔｈ属性の受け付けを要求するかどうかの判断は、ＡＳ＿Ｐａｔｈネットワーク構成パラメータの受け付けを設定するＮＯＣの管理者によって行われる。ＡＳ＿Ｐａｔｈの受け付けが必須である場合、ＨＯＮＯＲ＿ＡＳステータスフラッグが設定（９２４）されて、このルートが禁止されていることが知らされ、プロセスはステップ９６０に進む。ＡＳ＿Ｐａｔｈ属性の受け付けが要求されていない場合、プロセスはステップ９６０に進む。
【０１４５】
９２０において、対象のルートがそのルートグループ内の最短のＡＳ＿Ｐａｔｈを有すると判断された場合、プロセスは、最短のＡＳ＿Ｐａｔｈとなるように対象のルートがルートグループ内の別のルートと結び付けられているかどうかを判断するためにチェック（９３０）する。結び付けられていない場合、ＳＥＬＥＣＴＥＤ＿ＮＡＴＵＲＡＬステータスフラッグが設定（９３２）され、プロセスはステップ９６０に進む。最短のＡＳ＿Ｐａｔｈとなるように対象のルートがルートグループ内の別のルートと結び付けられている場合、プロセスは、最短のＡＳ＿Ｐａｔｈとなるように結ばれている全てのルートが同じ区域（ｎｅｉｇｈｂｏｒ）を有するかどうかを判断するためにチェック（９４０）する。「同じ区域」をチェックすることによって、最短のＡＳ＿Ｐａｔｈとなるように結び付けられているルートが、同じピアリングパートナーからのルートであるかどうかが判断される。ＭＥＤ属性は、特定のＡＳ（自律系）またはピーリングパートナーにローカルな属性である。同じピーリングパートナーからのルートのみが、有効なＭＥＤ比較を行い得る。
【０１４６】
最短のＡＳ＿Ｐａｔｈとなるように結び付けられている全てのルートが同じ区域を有さない場合、ＭＥＤ比較は無効となり、プロセスはステップ９６０に進む。全てのルートが同じ区域を有する場合、プロセスは、対象のルートがルートグループ内の最短のＭＥＤを有するかどうかを判断するためにチェック（９５０）する。有する場合、ＳＥＬＥＣＴＥＤ＿ＮＡＴＵＲＡＬステータスフラッグが設定（９５２）され、プロセスはステップ９６０に進む。対象のルートがルートグループ内の最短のＭＥＤを有さない場合、プロセスは直接ステップ９６０に進む。
【０１４７】
ステップ９６０において、プロセスは、対象のルートに関連するトラフィックの量が選好閾値を越えるかどうかを判断する。選好閾値はＮＯＣにおいて判断され、非常に小さなトラフィックを有するルートが選好されることを防ぐために用いられる。選好閾値は、より多いまたはより少ないルートを選好するために変更され得、一実施形態において、特定のルートグループからのトラフィック全体の割合（パケットまたはバイトで測定される）に関して設定される。一実施形態において、ルートグループから集められた全てのトラフィックデータの少なくとも５０％の閾値が最初に設定され、選好閾値は必要に応じて変更される。
【０１４８】
選好閾値を越えない場合、ルートの選好を正当化するためのルートに関連する十分なパケットがないため、プロセスは終了（９８０）する。しかし、選好閾値を越える場合、ＢＥＬＯＷ＿ＴＨＲＥＳＨＯＬＤステータスフラッグがクリア（９６２）される。プロセスは、次いで、ルートが自然に選択されているか、または、禁止されているかをチェック（９６４）する。自然に選択されるルートは選好される必要がなく、これらのルートは、ルート選好選択プロセスにおいて設定される「ＳＥＬＥＣＴＥＤ＿ＮＡＴＵＲＡＬ」ステータスフラッグを有する。禁止されているルートは選択されてはならない。禁止されているルートは、「ＨＯＮＯＲ＿ＭＥＤ」または「ＨＯＮＯＲ＿ＡＳ」ステータスフラッグが設定されているルートである。
【０１４９】
ルートが自然に選択されている、または、禁止されている場合、プロセスは終了（９８０）する。しかし、ルートが自然に選択されていない、または禁止されていない場合、ＳＥＬＥＣＴＥＤ＿ＩＮＪＥＣＴステータスフラッグが設定（９６６）される。プロセスは、次いで、対象のルートが中継ルートであるかどうかを判断するためにチェック（９７０）する。ルートが中継ルートでない場合、プロセスは終了（９８０）する。しかし、ルートが中継ルートである場合、非中継ルートが利用可能であるかどうかを判断するためにチェック（９７２）が行われる。
【０１５０】
非中継ルートが利用可能でない場合、プロセスは終了（９８０）する。しかし、非中継ルートが利用可能である場合、ＰＲＥＦＥＲＲＥＤ＿ＴＲＡＮＳＩＴステータスフラッグが設定（９７４）される。プロセスは、次いで、終了（９８０）する。
【０１５１】
ルート選好選択プロセスは、次いで、ルートグループ内の次のルートを選択して処理する。第１のルートグループ内の全てのルートが処理された後、次のルートグループが選択されて処理される。全てのルートグループが処理された後、ルート選好選択プロセスは、現在のＮＯＣ更新サイクルに関して終了する。
【０１５２】
図１０は、ルート分化選択プロセスの流れ図である。ルート分化選択プロセス１０００は、分化ルートとしてインテリジェントルーティングシステムネットワークに導入されるべきルートをマスターＩＰ統計データテーブル５００から選択する。これらの分化ルートは、インテリジェントルーティングシステムネットワークに用いられるルートテーブルのサイズを増大させる。分化ルートは、ＩＳＰ接続のセットの宛先パスの細分性（ｇｒａｎｕｌａｒｉｔｙ）を増大させる。ルート分化選択プロセスは、同じＩＰアドレスおよびマスクに対応するマスターＩＰ統計データテーブル５００からルートの各セットをグループ分けする。
【０１５３】
ルート分化選択プロセスは、第１のルートグループから第１のルートを選択（１００５）する。プロセスは、ルートに関連するパケットの数が分化閾値を越えるかどうかをチェック（１０１０）する。分化閾値は、選好閾値に直接関連しない。一実施形態において、分化閾値は、特定のルートグループからのトラフィック全体の割合に関して設定される。例えば、分化閾値が７５％に設定される場合、特定のルートは、閾値を越えるために、ルートグループからのトラフィック全体の７５％以上である必要がある。分化閾値は、より多いまたはより少ないルートを選択するために、ＮＯＣの管理者によって変更され得る。
【０１５４】
分化閾値を越えない場合、分化ルートは削除（１０３０）され、プロセスは終了（１０４２）する。分化閾値を越える場合、プロセスは、対応するルートエントリーが導入を許可するかどうかをチェック（１０２０）する。禁止されているルートを導入することはできない。特に、禁止されているルートは、「ＨＯＮＯＲ＿ＭＥＤ」または「ＨＯＮＯＲ＿ＡＳ」ステータスフラッグが設定されているルートである（ＮＯＣにおいて設定されるネットワーク構成パラメータによって判断されるように）。ルート導入が許可されていない場合、分化ルートが削除（１０３０）され、プロセスは終了（１０４２）する。
【０１５５】
ルート導入が許可されている場合、分化するルートを選択する前に満たす必要がある条件がもう１つある。分化ルートの候補に対応するルートエントリーより具体的なルートエントリーが別のピアリングパートナーに存在する場合、ルーティングシナリオが起きる可能性がある。他のピアリングパートナー上のより具体的なルートエントリーも分化ルートより具体的でなく、分化ルートのアドレス範囲を含む場合、元の対応するルートエントリーの属性を有する分化ルートを導入することは間違いである。
【０１５６】
従って、対応するルートエントリーが導入を許可する場合、親ルートより具体的なルートエントリーが別のピアリングパートナーに存在するかどうかのチェック（１０２５）が行われる。このシナリオが起きる場合、ＭＯＲＥ＿ＳＰＥＣＩＦＩＣ＿ＰＥＥＲフラッグが対応するルートエントリーに設定（１０２７）され、分化ルートが削除される。プロセスは、次いで、終了（１０４２）する。反対に、より具体的なルートが存在しない場合、ＤＥＡＧＧＲＥＧＡＴＥＤステータスフラッグが、関連するルートテーブル５１０に（フィルタリングおよび分析後のために）設定（１０４０）され、プロセスは終了（１０４２）する。第１のルートグループから次のルートが選択され、ルート分化プロセスは、全てのルートグループが処理されるまで続けられる。全てのルートグループが処理された後、ルート分化選択プロセス１０００は、現在のＮＯＣ更新サイクルに関して終了する。
【０１５７】
図８に示すように、ＮＯＣにおける処理が一旦完了（ステップ８５０）すると、格納出力ファイルがＰＯＰに伝送される。ＰＯＰは、それぞれ、好適ルート、選択されていないルートエントリー、分化ルート、および分化ルートに関連するルートエントリーなどの新しいＮＯＣ出力ファイルリスト項目を受信する。
【０１５８】
（最適ルートインプリメンテーション）
好適ルートのリストおよび分化ルートのリストは、インテリジェントルーティングシステムネットワークにおいて、各ＰＯＰにおけるルート処理を介してインプリメントされる。一実施形態において、図１１Ａおよび１１Ｂに示すように、周期的なルート処理１１００Ａを用いて、ＮＯＣからの新しい更新がインプリメントされ、連続的なルート処理１１００Ｂを用いて、外部ＢＧＰピアから受信されたＢＧＰ告知および撤回に応答して、分化ルートが管理される。これは、分化ルートの有効性が「親」ルートエントリーの現在の有用性に結び付けられているため、必要である。別の実施形態において、単一のプロセス１１００Ｃを用いて、ＮＯＣの更新の後にルート処理がインプリメントされる。このアプローチは、ルータが分化ルートと「親」エントリーとの間の関連性を明白に許容することができ、かつ、分化ルートを内部から管理することができることを必要とする。
【０１５９】
図１１Ａは、ＰＯＰ導入器における周期的なルート処理１１００Ａの流れ図である。各ＰＯＰ導入器は、バックボーンネットワーク内のルートを選好するように、または、消費者に告知される分化ルートを導入するように構成されたソフトウェアからなる。各ＰＯＰは、ＢＧＰスピーカおよびリスナープログラムを含むソフトウェアルート導入モジュールを含み、このモジュールは、ピアから送信されるルーティング情報を監視するメカニズムを提供し、ルーティング情報をピアリングセッションに導入することを可能にする。各ＰＯＰは、図１１Ａに示すステップを個別に実行する。各ＰＯＰは、分化ルートに関連するルートエントリーと共に、ＮＯＣ好適ルートおよび分化ルートファイルを受信（１１０２）する。好適ルートファイルは、処理を実行する特定のＰＯＰのために形成（１１０４）される。特定の選好は、処理を実行するＰＯＰに関連する選好である。特定のＰＯＰは、各好適または分化ルートに関連する交換ＩＤリスト項目を介して示される。
【０１６０】
ローカル選好がインストール（１１０６）される。「ローカル選好」は、ネットワークにおける優先順位を示すＢＧＰパラメータである。より下位のローカル選好値は、ネットワークにおけるより下位の優先順位を示す。ＢＧＰローカル選好は、ＡＳ＿ＰａｔｈおよびＭＥＤ値よりも優先順位が高い。選好ルートは、バックボーンネットワーク内の特定のルートを支持するために、ローカル選好の優先順位が高い。一実施形態において、導入された分化ルートは、マスクの長さが同じであるルートエントリーがピアリングパートナーから告知される場合に、ピアリングパートナーによって習得されたルートが導入されたルートに取って代わるように、低い優先順位のローカル選好によってインストールされる。
【０１６１】
ＰＯＰに既存する分化ルートは、ＮＯＣから新しく受信される分化ルートのリストと比較（１１０８）される。この比較によって、告知されるべきルートおよび撤回されるべきルートの更新リストが生成される。分化ルートの古いリストおよび新しいリストの両方で発見されるルートは、変更されておらず、従って、告知も撤回も行われていない。古いリストで発見されるが新しいリストで発見されないルートは、撤回されている。新しいリストで発見されるが古いリストで発見されないルートは、告知されるべきルートのリストに追加されている。ＰＥＮＤＩＮＧ＿ＷＩＴＨＤＲＡＷステータスフラッグは、「まだ有効でない」として、撤回されるべきルートに一時的に印をつけるように設定される。
【０１６２】
分化されるべきルートのステータスは、選好または分化されるべきルートがまだ存在することを確かめるためにチェックするＢＧＰ「ソフト再構成インバウンド（ｓｏｆｔ　ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ　ｉｎｂｏｕｎｄ）」（「ソフトイン（ｓｏｆｔ　ｉｎ）」）を介して確認（１１１０）される。ＢＧＰ「ソフトイン」は、確認されるべきルートを最初に送信したピアリングパートナーからルートのフルセットを再送する。従って、ルートを抜かしてしまう危険性はない。ルートに関連するデータの受信と分析との間に時間遅延があるため、「ソフトイン」ＢＧＰチェック、および、同じルートの選好または分化を行うことが望ましい。この時間間隔において、ルートを撤回することが可能である。ＢＧＰ「ソフトイン」のチェックによってルートが確認されると、ＰＥＮＤＩＮＧ＿ＷＩＴＨＤＲＡＷステータスフラッグが取り除かれる。ルートが確認されないままの場合、ＰＥＮＤＩＮＧ＿ＷＩＴＨＤＲＡＷステータスフラッグは、ＷＩＴＨＤＲＡＷＮステータスフラッグと取って代わる。
【０１６３】
告知されるべきルートおよび撤回されるべきルートは、ＢＧＰセッションソフトウェアフォーマット、例えば、ＳＢＧＰ（シンプルＢＧＰ）フォーマットのファイルに書き込まれる（１１１２）。ルートの告知および撤回は、次いで、ルータ管理専用の外部システム上のＢＧＰセッションを介して発行（１１１４）される。プロセスは、次いで、終了（１１１６）する。ＮＯＣにおける周期的なルート処理は、各ＰＯＰにおいて、好適ルートおよび分化ルートの更新がＮＯＣから受信される度に繰り返される。
【０１６４】
図１１Ｂは、各ＰＯＰ導入器において生じる連続的なルート処理１１００Ｂの流れ図である。連続的なルート処理は、ＮＯＣルート更新の受信に依存しない進行中の処理である。ＰＯＰ導入器は、ＢＧＰを介してルート告知および撤回を受信するのを待つ（１１２０）。ＢＧＰ告知および撤回メッセージが受信（１１２２）されると、プロセスは、受信された告知および撤回とルート分化の既存リストとを比較（１１２４）する。この比較によって、告知および撤回されるべきルートの新しいリストが生成される。
【０１６５】
告知および撤回の新しいリストは、ＢＧＰセッションソフトウェアフォーマットのファイルに書き込まれ（１１２６）、告知および撤回は、次いで、ＢＧＰセッションを介して発行（１１２８）される。プロセスは、次いで、ステップ１１２２に戻り、別のＢＧＰメッセージを受信するのを待つ。
【０１６６】
図１１Ｃは、ＰＯＰ導入器におけるルート処理の別の実施形態１１００Ｃの流れ図である。各ＰＯＰ導入器は、バックボーンネットワーク内のルートを選好するように、または、消費者に告知される分化ルートを導入するように構成されたソフトウェアからなる。各ＰＯＰは、リモートシェルスクリプトを含むソフトウェアルート導入モジュールを含み、このモジュールは、ルータの現在の構成を確認するメカニズムを提供し、ルート選好および分化ルートの設置を可能にする。各ＰＯＰは、図１１Ｃに示すステップを個別に実行する。各ＰＯＰは、分化ルートに関連するルートエントリーと共に、ＮＯＣ好適ルートおよび分化ルートファイルを受信（１１５０）する。
【０１６７】
一実施形態において、リモートシェルスクリプトは、好適ルートおよび分化ルートの現在のリストをルータから検索（１１５１）する。現在の好適ルートは、ＮＯＣからの最新の好適ルートと比較される。その結果、新しく選好されるルートのリストおよびもはや選好されないルートのリストが得られる。好適ルート変更ファイルが形成（１１５２）されて、これらの変更をインプリメントするために必要とされるコマンドがルータに提供される。現在の分化ルートは、ＮＯＣからの最新の分化ルートと比較される。その結果、分化する新しいルートのリストおよびもはや分化しないルートのリストが得られる。分化ルート変更ファイルが形成（１１５４）されて、これらの変更をインプリメントするために必要とされるコマンドがルータに提供される。
【０１６８】
一実施形態において、リモートシェルスクリプトは、変更ファイルに含まれるＢＧＰローカル選好および分化ルートをインストール（１１５６）する。図１１Ｃの方法は、導入されたルータを親プレフィックスに関連付ける専門ルータを使用する。ルータソフトウェアは、（１）導入されたルートを親ルートと一致させ、（２）親プレフィックスと一致するために、より具体的なプレフィックスを導入し、（３）親から導入されたルートへの全てのＢＧＰ属性をコピーし、かつ（４）親ルートの有用性に基づいて、導入されたルートを挿入または除去する。
【０１６９】
情報および処理フロー
図１２は、インテリジェントルーティングシステム内の情報および処理フローを示す。図１２は、システム１２００を構成する、ピアリングパートナー（ｐｅｅｒｉｎｇ　ｐａｒｔｎｅｒ）３４４、ＰＯＰ３３７、およびＮＯＣ３２０間の情報フローを示す。システム１２００は、インテリジェントルーティングシステムネットワークの一部を表わしている。
【０１７０】
ピアリングパートナー３４４は、ＰＯＰ３３７にトラフィックを送る、ルータ４０２Ｃを備える。ＰＯＰ３３７は、ルータ／コレクタ４２０Ｂ、ならびに２つのサーバ４５０Ｂおよび４５１Ｂを備える。ルータ／コレクタ４２０Ｂは、システム１２００のトラフィックをルーティングし、トラフィックの統計および他の情報を収集する。ＮＯＣ３２０は、サーバ４５２およびルータ４２６を備える。ルータ４２６は、ＰＯＰ３３７から情報を受け取り、ＰＯＰ３３７にＮＯＣ３２０の情報を返送するために用いられる。
【０１７１】
ルート４１２Ｃ、４１２Ｄ、および４１２Ｆが、ルータ／コレクタ４２０Ｂに通知される。ルータ／コレクタ４２０Ｂでは、ＩＰ統計ソフトウェアモジュール１２６８が、ルータ／コレクタ４２０Ｂを通過するトラフィックに関するＩＰ統計報告を収集する。ＩＰ統計ソフトウェアモジュール１２６８はまた、ルータ／コレクタ内のコンフィギュレーションオプションを変更することにより、入来するＩＰ統計データの最小プレフィックス長を設定する。１つの実施形態では、Ｃｉｓｃｏ（Ｒ）ＮｅｔＦｌｏｗサービスソフトウェアの改正版が、ＩＰ統計データを生成するために用いられる。
【０１７２】
ＩＰ統計報告１２５２が、処理のために、サーバ４５０Ｂに送られる。未処理の統計データ１２７０を受け取るソフトウェアモジュールは、未処理の統計バッファ１２１０を生成する。未処理の統計バッファ１２１０は、入来するＩＰ統計データパケットを二重にバッファリングするために用いられる。１つの実施形態では、ＣｆｌｏｗＭｕｘソフトウェアが、ＮｅｔＦｌｏｗデータを受け取るために用いられる。
【０１７３】
未処理の統計データ１２７２を集約するソフトウェアモジュールは、未処理の統計バッファ１２１０からパケットを抽出し、それに応じて、ＩＰ統計テーブル１２１２のセットを更新する。ＩＰ統計テーブル１２１２からトラフィック報告を読み出すように構成された、ＩＰ統計リーダソフトウェアモジュール１２７４が、ルートファイル１２１４内に、対応するＩＰ統計データテーブルエントリを作成する。１つの実施形態では、Ｃｆｌｏｗｄソフトウェアの改正版が、統計テーブル１２１２を作成し、また、所望のＩＰ統計をＮｅｔＦｌｏｗリーダを介して抽出することを可能にする、Ｕｎｉｘ（Ｒ）ソケットインターフェースも提供する。ＮｅｔＦｌｏｗリーダは、ｃｆｄｎｅｔｓと呼ばれるＣｆｌｏｗｄ内に含まれるソフトウェアモジュールに基づく。
【０１７４】
ルートテーブルリーダソフトウェアモジュール１２７６は、ルータ／コレクタ４２０Ｂからルートテーブル１２５４を読出し、その情報を用いて、ＰＯＰルートファイル１２１４内にルートテーブルエントリを作成する。ルーティング処理ソフトウェア１２７８は、ルートテーブルエントリと、ＰＯＰルートファイル１２１４内のＩＰ統計データテーブルエントリとを相互に関連づける。
【０１７５】
ＰＯＰルートファイル１２１４内の情報は、ＮＯＣ３２０にあるサーバ４５２に送信される。各ＰＯＰからのルートファイルは、ＮＯＣルートファイル１２１６内で結合され、格納される。ＮＯＣルーティング処理ソフトウェア１２８４は、ＮＯＣルートファイル１２１６上で動作する。１つの実施形態では、ＮＯＣルートファイル１２１６が、長期間の格納および解析のために、リアルタイムデータベース管理格納システム１２１８内に格納される。
【０１７６】
テストおよび解析ソフトウェアモジュール１２８０もまた、ＮＯＣルートファイル１２１６上で動作する。ユーザのグラフィカルユーザインターフェース（ＧＵＩ）１２８２は、テストおよび解析モジュール１２８０から得られた情報を表示する。当業者に明白であるように、テストおよび解析ソフトウェア１２８０、およびＧＵＩ１２８２はオプションであり、さらなる自動化されたチェックおよび統計が所望される場合に用いられ得る。例えば、ＧＵＩ１２８２は、制御パラメータを変更し、インテリジェントルーティングシステムの統計に対するパラメータの影響を観察するために用いられ得る。
【０１７７】
コントローラ１２４０は、ＮＯＣおよびＰＯＰ内の他のソフトウェアモジュールを制御する。コントローラ１２４０は、各ソフトウェアモジュールを連続して開始し、データディレクトリを管理し、システム１２００のファイルおよびディレクトリをクリーンアップする。１つの実施形態では、ユーザのＧＵＩ１２８２が、コントローラ１２４０にユーザコマンドを入力するために用いられる。他の実施形態では、コンフィギュレーションファイルが、コントローラ１２４０の動作を変えるために、手動で操作され得る。コントローラ１２４０は、各ＰＯＰでの情報収集、ＮＯＣへの収集した情報の送信、ネットワークのアドレス空間マップの展開、および選好分化ルート（ｐｒｅｆｅｒｅｎｃｅ　ａｎｄ　ｄｅａｇｇｒｅｇａｔｅ　ｒｏｕｔｅｓ）へのアドレス空間マップの使用を行うプロセスの自動化を管理する。コントローラ１２４０はまた、ルートを選好し、分化ルートを導入するプロセスの自動化を管理する。アドレス空間マップを作成して用いるプロセスも手動で実施され得ることは、当業者には明白である。しかしながら、収集されているデータ量が多いこと、およびプロセスの反復的な性質により、プロセスを自動化することがより効率的である。
【０１７８】
選好分化ルート１２６０は、ＮＯＣ３２０からＰＯＰサーバ４５１Ｂ上にあるＰＯＰルートファイル１２２０へと送信される。さらなるＰＯＰルーティング処理１２９０が、ＰＯＰルートファイル１２２０上で実施される。現在のルータ４２０Ｂのコンフィギュレーションが収集され（ｃｏｌｌｅｃｔｅｄ）、ルーティング処理１２９０により、現在のルータコンフィギュレーションと、好ましい分化されたルートファイル１２２０で得られた、所望のルータコンフィギュレーションとを比較する。ルーティング処理１２９０は、ルートポリシーの更新１２９２で用いられる、好ましいルート変更ファイル、および分化されたルート変更ファイルを生成する。ルートポリシーの更新１２９２により、バックボーンネットワーク内のルートが選好され、インテリジェントルーティングシステムネットワーク全体にわたって告知される、分化ルートが導入される。
【０１７９】
本発明は、特定の実施形態に関して詳述されたが、他の実施形態も可能である。当業者に理解されるように、本発明は、本発明の本質的な特徴から逸脱することなく、他の特定の形態で具現化され得る。例えば、多様なピアリングパートナー、バックボーン、およびＰＯＰコンフィギュレーションが、インテリジェントルーティングシステムの範囲内で可能である。インテリジェントルーティングシステムは、他のＴＣＰ／ＩＰネットワークを用いてインプリメントされ得、インターネットの用途に限定されない。さらに、インテリジェントルーティングシステム内で展開されたアドレス空間マップの細分性は、例えば、システムによって監視されるＩＰ統計データ上で最小プレフィックス長を変更することにより変わり得る。したがって、本発明は、特許請求の精神および範囲、ならびに等価物に含まれる、全ての代替物、修正、および改変を包含することを企図する。
【図面の簡単な説明】
【図１Ａ】
図１Ａは、異なるＩＳＰ間の典型的なピアリングおよびトランジット接続を用いるネットワークの図である。
【図１Ｂ】
図１Ｂは、二つのＩＳＰ間の「ホットポテトルーティング」および「コールドポテトルーティング」の図である。
【図２Ａ】
図２Ａは、異なるＩＳＰ間の接続の図である。
【図２Ｂ】
図２Ｂは、本発明の実施形態におけるＩＳＰのアドレス空間の非集合の図である。
【図３】
図３は、本発明の実施形態における知的ルーティングシステムの図である。
【図４】
図４は、本発明の実施形態における知的ルーティングシステムの部分の図である。
【図５Ａ】
図５Ａは、本発明の実施形態におけるＩＰ統計データテーブルの図である。
【図５Ｂ】
図５Ｂは、本発明の実施形態におけるルート入力テーブルの図である。
【図６】
図６は、本発明の実施形態におけるモニタリングルート情報および分配ルート情報のプロセスのフロー図である。
【図７】
図７は、本発明の実施形態における存在ポイント（ＰＯＰ）コレクターでのルート処理のフロー図である。
【図８】
図８は、本発明の実施形態におけるニューヨークオペレーションセンター（ＮＯＣ）でのルート処理のフロー図である。
【図９】
図９は、本発明の実施形態におけるルート優先選択プロセスのフロー図である。
【図１０】
図１０は、本発明の実施形態におけるルート非集合選択プロセスのフロー図である。
【図１１Ａ】
図１１Ａは、本発明の実施形態におけるＰＯＰインジェクターでの周期的ルート処理のフロー図である。
【図１１Ｂ】
図１１Ｂは、本発明の実施形態におけるＰＯＰインジェクターでの連続するルート処理のフロー図である。
【図１１Ｃ】
図１１Ｃは、本発明の他の実施形態におけるＰＯＰインジェクターでのルート処理のフロー図である。
【図１２】
図１２は、本発明の実施形態における知的ルーティングシステム内の情報および処理フローの図である。
【図１Ａ】
2004508743.tif 000006
【図１Ｂ】
2004508743.tif 000007
【図２Ａ】
2004508743.tif 000008
【図２Ｂ】
2004508743.tif 000009
【図３】
2004508743.tif 000010
【図４】
2004508743.tif 000011
【図５Ａ】
2004508743.tif 000012
【図５Ｂ】
2004508743.tif 000013
【図６】
2004508743.tif 000014
【図７】
2004508743.tif 000015
【図８】
2004508743.tif 000016
【図９】
2004508743.tif 000017
【図１０】
2004508743.tif 000018
【図１１Ａ】
2004508743.tif 000019
【図１１Ｂ】
2004508743.tif 000020
【図１１Ｃ】
2004508743.tif 000021
【図１２】
2004508743.tif 000022
【国際公開パンフレット】
2004508743.tif 000023
2004508743.tif 000024
2004508743.tif 000025
2004508743.tif 000026
2004508743.tif 000027
2004508743.tif 000028
2004508743.tif 000029
2004508743.tif 000030
2004508743.tif 000031
2004508743.tif 000032
2004508743.tif 000033
2004508743.tif 000034
2004508743.tif 000035
2004508743.tif 000036
2004508743.tif 000037
2004508743.tif 000038
2004508743.tif 000039
2004508743.tif 000040
2004508743.tif 000041
2004508743.tif 000042
2004508743.tif 000043
2004508743.tif 000044
2004508743.tif 000045
2004508743.tif 000046
2004508743.tif 000047
2004508743.tif 000048
2004508743.tif 000049
2004508743.tif 000050
2004508743.tif 000051
2004508743.tif 000052
2004508743.tif 000053
2004508743.tif 000054
2004508743.tif 000055
2004508743.tif 000056
2004508743.tif 000057
2004508743.tif 000058
2004508743.tif 000059
2004508743.tif 000060
2004508743.tif 000061
2004508743.tif 000062
2004508743.tif 000063
2004508743.tif 000064
2004508743.tif 000065
2004508743.tif 000066
2004508743.tif 000067
2004508743.tif 000068
2004508743.tif 000069
2004508743.tif 000070
2004508743.tif 000071
2004508743.tif 000072
2004508743.tif 000073
2004508743.tif 000074
2004508743.tif 000075
2004508743.tif 000076
2004508743.tif 000077
2004508743.tif 000078
2004508743.tif 000079
2004508743.tif 000080
2004508743.tif 000081
2004508743.tif 000082
2004508743.tif 000083
2004508743.tif 000084
2004508743.tif 000085
2004508743.tif 000086
2004508743.tif 000087
2004508743.tif 000088
2004508743.tif 000089
2004508743.tif 000090
2004508743.tif 000091
2004508743.tif 000092
2004508743.tif 000093
2004508743.tif 000094
【国際公開パンフレット（コレクトバージョン）】
2004508743.tif 000095
2004508743.tif 000096
【国際調査報告】
2004508743.tif 000097
2004508743.tif 000098
2004508743.tif 000099
2004508743.tif 000100
2004508743.tif 000101