(57)【要約】  少なくとも１つの物理リンクを定義する少なくとも２つのスイッチング・デバイスをもつ電気通信キャリア・ネットワークでデータをルーティングする方法およびデバイスで、前記方法が、各々がネットワークの物理リンクの少なくとも１つを経由する特定のルーティングに対応付けられた複数のトラフィック・フローを事前に定義するステップと、トラフィック・フローに従いルーティング・システムを構成するステップと、トラフィック・フローの少なくとも一部に送信されるトラフィックのデータを収集して、収集したデータに基づいてネットワーク内のフローの各々についてトラフィック統計を計算するステップと、計算したトラフィック統計を利用してルーティング・システムの構成を再計算するステップとを含む。
2008527941.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの物理リンクを定義する少なくとも２つのスイッチング・デバイスを含む電気通信キャリア・ネットワークでデータをルーティングする方法で、前記方法が、
各々がネットワーク内の前記物理リンクの少なくとも１つを経由する特定のルーティングに対応付けられる複数のトラフィック・フローを事前に定義するステップと、
前記トラフィック・フローに従いルーティング・システムを構成するステップと、
前記トラフィック・フローの少なくとも一部に送信されるトラフィックのデータを収集するステップと、
前記収集したデータに基づいて、ネットワーク内の前記フローの各々についてトラフィック統計を計算するステップと、
前記計算したトラフィック統計を利用してルーティング・システムの構成を再計算するステップと、
を有することを特徴とする方法。
【請求項２】
前記事前に定義するステップが、ユーザーから前記トラフィック・フローを受信するステップを含むことを特徴とする請求項１記載の方法。
【請求項３】
前記事前に定義するステップが、前記複数のトラフィック・フローの定義を準備したデータベースに格納するステップを含むことを特徴とする請求項１記載の方法。
【請求項４】
さらに、前記再計算したルーティング・システムの構成に従い、ネットワーク内のネットワーク・デバイスを再構成するステップを有することを特徴とする請求項１乃至３の何れか１記載の方法。
【請求項５】
再構成するステップが、ネットワーク・デバイスをほぼ同時に再構成するステップを含むことを特徴とする請求項４記載の方法。
【請求項６】
さらに、
前記ルーティング・システムの構成の再計算のための少なくとも１つの事前選択した基準を事前に定義するステップと、
前記事前選択した基準の少なくとも１つを満たすかどうかを判定するステップとを有し、
再計算するステップが、最小の１つの事前選択した基準を満たした場合のみルーティング・システムの構成を再計算するステップを含むことを特徴とする請求項１乃至５の何れか１記載の方法。
【請求項７】
ルーティング・システムの構成の再計算のための事前選択した前記基準を、
・ネットワーク・トポロジーの変化
・少なくとも１つの論理リンクの変化
・少なくとも１つの選択したモニタリングする統計の変化
・少なくとも１つの論理リンクの帯域幅の利用の所定の確率閾値を超える変化
・事前選択した時間の経過
・サービス品質の要求事項の変更
・帯域幅利用の繰返しパターン
を含むグループから選択することを特徴とする請求項６記載の方法。
【請求項８】
さらに、前記再構成するステップの前に、再計算したルーティング・システムの構成が前記ネットワークの少なくとも１つの選択したメトリックを改善するかどうかを判定するステップを有することを特徴とする請求項４記載の方法。
【請求項９】
前記メトリックを、
ネットワークのスループットの向上
できるだけ最短パスの利用
均一な配布およびネットワーク帯域幅リソースの使用の提供
あらゆるリンクについて、所定値または計算値に対する（ΣＰＩＲ−ΣＣＩＲ）／（リンク許容量−ΣＣＩＲ）の比率の最小化
どの物理リンクにおいても総計ＣＩＲおよびＭＢＳトラフィックをユーザー設定値未満に制限
前記経路の包括コストの最小化
から選択することを特徴とする請求項８記載の方法。
【請求項１０】
電気通信キャリア・ネットワークがイーサーネット・ネットワークであることを特徴とする請求項１乃至９の何れか１記載方法。
【請求項１１】
さらに、特定のサービス品質を前記複数の論理リンクの各々に対応付けるステップを含むことを特徴とする請求項１０記載の方法。
【請求項１２】
さらに、前記デバイスの各々にプライベート・ネットワーク・アドレスを割り当てるステップを有することを特徴とする請求項１０または請求項１１記載の方法。
【請求項１３】
各前記プライベート・ネットワーク・アドレスが、前記トラフィック・フローの少なくとも１つに関する情報を含むことを特徴とする請求項１２記載の方法。
【請求項１４】
さらに前記トラフィック統計を格納するステップを有することを特徴とする請求項１乃至１３の何れか１記載の方法。
【請求項１５】
前記定義するステップから再計算するステップをオフラインで実施することを特徴とする請求項１乃至１４の何れか１記載の方法。
【請求項１６】
前記スイッチング・デバイスの少なくとも１つがプロセッサを含み、前記定義するステップから再計算するステップを前記プロセッサで実施することを特徴とする請求項１乃至１５の何れか１記載の方法。
【請求項１７】
さらにネットワークの初期化モードを実施するステップを含み、前記実施するステップが、
初期トポロジー・パラメータを前記プロセッサに入力するステップと、
ルーティング・システムの構成の再計算のための少なくとも１つの事前選択した基準を前記プロセッサに入力するステップと、
プロセッサに前記初期パラメータからプロビジョニング・テーブルを作成させるステップと、
必要なすべての論理リンクを定義するステップと、
サニティ・チェックを行うステップと、
サニティ・チェックにパスした後、前記入力した初期パラメータに従い仮経路を計算するステップと、
前記仮経路に従いルーティング・テーブルを作成するステップと、
前記作成したルーティング・テーブルを構成コマンドと一緒に前記ネットワーク・デバイスに転送することによって、すべてのネットワーク・デバイスを構成するステップと、
を有することを特徴とする請求項１６記載の方法。
【請求項１８】
さらに、
帯域幅利用の確率閾値と、前記確率が前記閾値を超えなければならない最低期間をネットワークに入力するステップと、
各論理リンクについて帯域幅利用の確率を計算するステップと、
前記計算した帯域幅利用の確率値を前記入力した帯域幅利用の確率閾値と比較するステップと、
前記確率の計算した期間を入力した時間閾値と比較するステップと、
経時的な帯域幅利用の確率値が許容閾値を超える場合、前記ルーティング・システムの構成を再計算するステップと、
前記再計算したルーティング・システムの構成を実装するステップと、
を含む、請求項１乃至１７の何れか１記載の方法。
【請求項１９】
さらに、前記実装するステップの前に、再計算したルーティング・システムの構成が前記ネットワークのスループットを向上させるかどうかを判定するステップを有することを特徴とする請求項１８記載の方法。
【請求項２０】
さらにネットワークの動作の構成変更モードを提供するステップを有し、前記提供するステップが、
構成変更のための新たなパラメータを前記プロセッサに入力するステップと、
前記入力したトラフィック・フローと前記新たなパラメータに基づき新たなプロビジョニング・テーブルを提供するステップと、
追加および／または削除するすべての物理リンクを再構成するステップと、
前記計算したトラフィック統計とともに、前記新たに入力したパラメータを利用して、前記ルーティング・システムの構成を再計算するステップと、
前記再計算したルーティング・システムの構成を利用して新たなルーティング・テーブルで前記ネットワーク・デバイスのすべてを再構成するステップと、
を有することを特徴とする請求項１８記載の方法。
【請求項２１】
さらに前記収集するステップと計算するステップを継続的に繰り返すステップを有することを特徴とする請求項１乃至２０の何れか１記載の方法。
【請求項２２】
さらに前記計算した統計を格納するステップを有し、
前記計算するステップが、前記格納した統計から、ネットワーク内の前記フローの各々について更新トラフィック統計を計算するステップを含むことを特徴とする請求項１乃至２１の何れか１記載の方法。
【請求項２３】
前記プロセッサが、ネットワークを経由するデータをルーティングするルーティング方式を定義し、ルーティング方式に従いスイッチング・デバイスを構成し、スイッチング・デバイスを再構成するための少なくとも１つの事前選択した基準を満たしているかどうかを判定し、基準の少なくとも１つを満たしている場合ルーティング方式を再定義し、再定義したルーティング方式に従ってスイッチング・デバイスを再構成するコンピュータ・プログラムを含むことを特徴とする請求項１６記載の方法。
【請求項２４】
各スイッチング・デバイスが、ネットワークを経由するデータをルーティングするルーティング方式を定義し、ルーティング方式に従いスイッチング・デバイスを構成し、スイッチング・デバイスを再構成するための少なくとも１つの事前選択した基準を満たしているかどうかを判定し、基準の少なくとも１つを満たしている場合ルーティング方式を同一に再定義し、再定義したルーティング方式に従ってスイッチング・デバイスを再構成する同一のコンピュータ・プログラムを含むことを特徴とする請求項１６記載の方法。
【請求項２５】
トラフィック・フローの各々がネットワーク内の少なくとも１つの物理リンクを経由する特定のルーティングと対応付けられる、複数のトラフィック・フローの定義を受信するように構成されたプロセッサを有する電気通信キャリア・ネットワークのネットワーク管理ステーションで、
前記プロセッサがさらに、
トラフィック・フローに従いルーティング・システムを構成し、
トラフィック・フローの少なくとも一部に送信されるトラフィックの収集データを受信し、
収集したデータに基づいてネットワーク内のトラフィック・フローの各々についてトラフィック統計を判定し、
計算したトラフィック統計を利用してルーティング・システムの構成を再計算する
ように構成されたことを特徴とするネットワーク管理ステーション。
【請求項２６】
さらにユーザー・インターフェースを有し、プロセッサがユーザー・インターフェースを介してユーザーから前記複数のトラフィック・フローの定義を受信するように構成されたことを特徴とする請求項２５記載のネットワーク管理ステーション。
【請求項２７】
前記プロセッサがさらにプライベート・ネットワーク・アドレスを前記デバイスの各々に割り当てるように構成されたことを特徴とする請求項２５または請求項２６記載のネットワーク管理ステーション。
【請求項２８】
各前記プライベート・ネットワーク・アドレスが前記トラフィック・フローの少なくとも１つに関する情報を含むことを特徴とする請求項２７記載のネットワーク管理ステーション。
【請求項２９】
トラフィック・フローの各々がネットワーク内の少なくとも１つの物理リンクを経由する特定のルーティングに対応付けられる、複数のトラフィック・フローの定義を受信するように構成されたプロセッサを有する電気通信キャリア・ネットワーク用スイッチング・デバイスで、
前記プロセッサがさらに、
トラフィック・フローに従いルーティング・システムを構成し、
トラフィック・フローの少なくとも一部に送信されるトラフィックの収集データを受信し、
収集したデータに基づいてネットワーク内のトラフィック・フローの各々についてトラフィック統計を判定し、
計算したトラフィック統計を利用してルーティング・システムの構成を再計算する
ように構成されたことを特徴とするスイッチング・デバイス。
【請求項３０】
さらにユーザー・インターフェースを有し、プロセッサがユーザー・インターフェースを介してユーザーから前記複数のトラフィック・フローの定義を受信するように構成されたことを特徴とする請求項２９記載のスイッチング・デバイス。
【請求項３１】
前記プロセッサがさらにプライベート・ネットワーク・アドレスを前記デバイスの各々に割り当てるように構成されたことを特徴とする請求項２９または請求項３０記載のスイッチング・デバイス。
【請求項３２】
各前記プライベート・ネットワーク・アドレスが前記トラフィック・フローの少なくとも１つに関する情報を含むことを特徴とする請求項３１記載のネットワーク管理ステーション。
【請求項３３】
コンピュータ用の命令のセットを内蔵するコンピュータ読み取り可能記憶媒体で、前記命令のセットが、コンピュータにより実行されるとき、
トラフィック・フローの各々がネットワーク内の少なくとも１つの物理リンクを経由する特定のルーティングに対応付けられる、所定のトラフィック・フローに従い電気通信キャリア・ネットワークのルーティング・システムを構成するステップと、
トラフィック・フローの少なくとも一部に送信されるトラフィックのデータを収集するステップと、
収集したデータに基づいて、ネットワーク内のトラフィック・フローの各々についてトラフィック統計を計算するステップと、
計算したトラフィック統計を利用してルーティング・システムの構成を再計算するステップと
をコンピュータに行わせることを特徴とするコンピュータ読み取り可能記憶媒体。
【請求項３４】
命令のセットが、コンピュータにより実行されるとき、さらに、
ユーザーから所定のトラフィック・フローを受信するステップを
コンピュータに行わせることを特徴とする請求項３３記載のコンピュータ読み取り可能記憶媒体。
【請求項３５】
受信するステップがユーザー・インターフェースを介してユーザーから所定のトラフィック・フローを受信するステップを含むことを特徴とする請求項３４記載のコンピュータ読み取り可能記憶媒体。
【請求項３６】
命令のセットが、コンピュータにより実行されるとき、さらに、
プライベート・ネットワーク・アドレスを前記デバイスの各々に割り当てるステップを
コンピュータに行わせることを特徴とする請求項３３乃至３５の何れか１記載のコンピュータ読み取り可能記憶媒体。
【請求項３７】
命令のセットが、コンピュータにより実行されるとき、さらにコンピュータに、各プライベート・ネットワーク・アドレスを生成させ、前記トラフィック・フローの少なくとも１つに関する情報を含ませることを特徴とする請求項３６記載のコンピュータ読み取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般的に電気通信キャリア・ネットワークのルーティングの方法およびシステムに関係し、特に、電気通信キャリア・ネットワークでデータ・トラフィックをルーティングする方法およびシステムに関係するものである。
【背景技術】
【０００２】
パケット交換網とは、一般に（データリンク層で）任意にノードを相互接続するコネクションレスの帯域幅共有ネットワークである。データ送信のためにノード間の接続を確立するには、ルーティング・メカニズムが必要である。現行のルーティング・プロトコルは任意かつランダムに互いに通信する多数のノードから構成される動的なトポロジーを特徴とするネットワーク経由での動的かつ予測不能な量のデータ転送に対応するように設計されている。これらネットワークは典型的にはエンタープライズ・ネットワークまたはインターネットである。前記データ転送に対処するために、ルーティング・プロトコルは各ルーターにネットワーク・トポロジーを継続的に学習させ、ネットワーク全体のトラフィックの状態に関する情報を継続的に収集させ、各ノードをルーティングするデータの量に注意し、起こりうる接続ごとに最適化した経路を計算して、各ルーティング・ノードのルーティング・テーブルを更新するように構成される。このため、各ルーターは、他のルーターとは独立して、自身のルーティング・テーブルを計算するが、該計算されたルーティング・テーブルがデータをどこに送るかを決める根拠となる。個々のルーターはネットワーク内の全体のトラフィック負荷またはパフォーマンスを把握していないため、情報はローカル（隣接ホップ）情報に基づいている。そのため、ネットワーク内の他のノードを考慮しないため該ルーティング・テーブルは準最適なものとなり、ルーティング・ノードにひどく負担がかかる。
【０００３】
米国特許出願第２００２０１５００４１号公報には、インターネットなどのＩＰベースのデータ・ネットワークで選択したデータ・パケットの転送のためのサービス品質を改善する方法およびシステムについて記載されている。この方法は顧客の環境内のサーバーを利用し、該サーバーの各々が送信元ノードまたは宛先ノードとして機能する。各リンクには、いくつかの代替パスを予め選択しておくことが好ましい。サーバーは、サーバー間でテスト・パケットを交換して各代替パスの転送パラメータをモニターおよび分析できる機能を持つソフトウェアを内蔵している。最適なパスが割り出されると、該サーバーはデータ・パケットのヘッダーを修正し、それによってデータ・パケットを選択した最適パス経由で宛先ノードにフォワード（転送）させる。
該方法では、２つのノード間ではパス（経路）をモニターするが、全体的にはモニターしない。さらに、データは経時的に収集されないため、ルーティング決定はある時点の瞬間的な情報のみに基づいたものとなる。
【０００４】
米国特許出願第２００２／０１７４２４６号公報には、ＩＰプロトコル・ネットワークにおけるルーターのルーティング・テーブルを計算し、個々のルーターから経路を計算するタスクをなくす集中システムについて記載されている。前記システムはネットワーク・トラフィック統計収集システムと、トラフィック統計に従いトラフィックをクラスに分類して各トラフィック・クラスに最適な経路を計算するマトリックス形成・最適化システムと、最適化した経路に関する情報を含めたルーティング・テーブルを個々のルーターに配信する配信システムとを含むものである。ＩＰネットワーキング・システムでの使用に限られる該システムは、何らかの変化があると必ずネットワークの新たなトポロジーの状態を学習しなければならない。これらの計算が継続的に必要なため、ネットワークは大量の計算を負い、たとえ変化がなくても、ほぼリアルタイムで、ルーティング・テーブルを自動的に「更新」し、該更新によって全体としてネットワークのデータ転送が遅くなる。
ルーティング・テーブルの更新またはこれらインターネット型のネットワークの再構成は、何か特定の基準とは関係なく、継続的に起こることが認識される。むしろ、これらのシステムを使用したネットワークが再構成される頻度はネットワークのサイズと複雑さ、計算の量、および計算速度、システムによるルーティング・テーブルの更新速度によって決まる。
【０００５】
コア・データ・トラフィックを転送するキャリア転送ネットワーク、例えばメトロエリア・ネットワークは、エンタープライズ・ネットワークまたは世界的なインターネットには似ていない。むしろ、キャリア転送ネットワークは従来の電話網であり、以下のような様々な属性で特徴付けられる。
・論理的なネットワークのトポロジーは通常メッシュ型である。
・物理的なネットワークは通常リング型である。
・ネットワークは明確に定義された自律ルーティング・ドメインからなる。
・各ノードは各ドメイン内の特定のノードに接続される。
・利用できる経路は既知で数が限られ、ネットワークのトポグラフィが変化するまで静的である。
・各ルーティング・ドメイン内の１ノードからの１サービスのすべてのトラフィックは比較的小さな有限の不変のノードのグループに向けられる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
これらネットワークは非効率であるという欠点がある。要求されるすべてのトラフィックを合理的な時間内にネットワークで確実に転送するために、ネットワークを十分に利用していないことが多い。そのため、ネットワーク上で空のフレームが送られることが多い。
さらに、一般化されたグローバルで動的なトポロジー・ネットワーク用に設計された前述の複雑なルーティング・プロトコルは、ネットワーク内の様々なノードの実際の状態に従いルーティング・テーブルを常に更新する必要があり、メトロ・ネットワークなどのキャリア・ネットワークのルーティング・ドメインで経路を確立するのに適さない。これはルーティング・プロトコルがあまりに複雑で、資源効率またはコスト効率が高くないからである。
従って、当分野では従来のキャリア・システムの安定性と信頼性をもつキャリア・ネットワークのメトロ・ネットワークおよびサブネットワークなどのルーティング方法およびシステムの必要性を長年感じており、従来の世界的なネットワークのシステムと同程度の柔軟性と適応性があるようなルーティング・システムを提供することが望ましい。
【課題を解決するための手段】
【０００７】
本発明のある例示的な実施例によると、トラフィック・データを利用して統計、特にネットワーク全体の統計を計算することによって、比較的安定したキャリア・ネットワークまたはメトロ・ネットワークの効率を高める方法を提供する。本発明において、「ネットワーク」という用語は別段の記載がない限りメトロ・ネットワークまたはキャリア・ネットワークをいい、「ネットワーク統計」または「グローバル統計」とはネットワークを経由するトラフィック・フローの一部もしくは全部から収集したトラフィック・データから計算したネットワーク全体のデータ・トラフィック・フローに関する統計を意味する。ここでは、キャリア・ネットワークを経由する様々な経路は予め分かっており、また比較的変わらないため、キャリア・ネットワークをパケットまたはフレームベースのメトロ・ネットワークにアップグレードする場合、ＩＰおよび同様なネットワークのように、様々なノードのトラフィックの状態を継続的に点検して、ルーティング・テーブルを置き換えるのは非効率であることは認識されている。本発明の例示的な実施例では、キャリア・ネットワークの固有の特性、すなわち制御され持続可能な動作およびトポロジーを活かしたはるかに効率的なシステムを提案する。本システムは、ネットワーク全体のグローバル・トラフィック統計に基づいてネットワークの全てのネットワーク・デバイス（例えば、スイッチ、ルーター）について、所定の基準を満たしたときだけルーティング・テーブルを計算する、あるいは、定期的に更新されるオフライン・アルゴリズムを利用する中央ルーティング・システムに基づく。ルーティング・テーブルはトポロジー、ネットワーク負荷統計、および一連のサービス品質保証制度（ＳＬＡ）（ネットワーク・プロバイダーが各顧客に提供するサービスを定義するもの）を考慮しながら、ネットワークのスループットを最適化する。所定のネットワーク・パラメータと合わせて経時的にネットワーク・デバイスから収集した負荷統計に従い、ルーティングを定期的に最適化する。
【０００８】
本発明のある例示的な実施例によると、コア・ネットワーク経由のすべてのトラフィックを所定のフロー（あるいは、論理的なリンク）のセットの中の１つと対応付けられると想定する。各フローは固有の送信元および宛先に対応付けられ、任意で、サービス品質（ＱＯＳ）要求事項と対応付けられる。これらの定義は「準静的」であり、すなわちフローのＳＬＡと送信元および宛先は比較的長期間静的であり、ネットワークが変わるときにしか変わらない。このため、ルーティング方式も準静的であり、すなわち比較的長期間固定しており、予め選んだ基準を満たすときにしか変わらない。
本発明において、ネットワークはイーサーネット・ネットワークである。この場合、コア・ネットワークは例えば標準的な機器を使って実装できる。この場合、機器はイーサーネット・スイッチを実装し、すなわちネットワークのトポロジーにおいてそのＭＡＣアドレスに従いパケットを正確に指し向ける。
【０００９】
本発明において、前記例示的な方法は、電気通信ネットワークのデータ層であるレイヤ２に実装される。このレイヤでは、まだ処理されていないデータのルーティングの変更がはるかに単純で、より効率的であり、必要な計算が少なく、コストが安くなる。なお、該方法を例や２に実装する代わりに、レイヤ３（静的ＩＰルーティング）またはネットワーク層１（ラムダ・ルーティング）などの他のネットワーク層に実装することも可能である。
このように、本発明において、キャリア・ネットワークでデータをルーティングする方法を提供し、前記方法は、各々がネットワーク内の少なくとも１つの物理リンクを経由する特定のルーティングに対応付けられる複数のトラフィック・フローを定義するステップと、トラフィック・フローに従いルーティング・システムを構成するステップと、前記トラフィック・フローの各々を経由するトラフィックのデータを収集または計算するステップと、収集したデータからネットワーク内の各トラフィック・フローについてのトラフィック統計を計算するステップと、計算したトラフィック統計を利用してルーティング・システムを再計算するステップを含む。
【００１０】
本発明において、該方法はさらに、ルーティング方式の再計算に関して事前選択した少なくとも１つの基準を定義するステップと、事前選択した基準の１つを満たしたときにルーティング方式を再計算するステップとを含む。
本発明において、ネットワークはイーサーネット・ネットワークである。
ある例示的な実施例によると、ルーティング・システムはトラフィック・フローが追加または削除または中断したときに再構成される。
好適な実施例によると、収集するステップは論理リンクの少なくとも一部を経由するトラフィックの状態に関する統計情報を収集するステップを含み、計算するステップは収集した情報を処理して、必要な帯域幅と実際のスループットの平均と分散の分布など、ネットワーク内のすべての論理リンクのトラフィック統計を提供するステップを含む。また、システムは以下詳述するような経路の計算のトリガーとなる他の基準を考慮することもできる。それから代替ルーティング方式を計算し、選んだネットワーク・メトリックに対するその効果を計算して、総ネットワーク・スループット（ネットワークが伝送する総帯域幅）などの現在のメトリックの値と比較する。新たなルーティング方式が、メトリックの改善率、およびメトリック値が改善する確率、およびエンドユーザーが予め選択した連続する変化の間隔の最低期間などの時間閾値、またはそのいずれかなどの統計値に基づいて、メトリックを改善したら、ネットワークを新たなルーティング方式に再構成する。
【００１１】
本発明のある例示的な実施例によると、新たなルーティング方式を計算するために事前選択した基準は、以下の再発事象の１つまたは全部を含めることができる。
・ネットワーク・トポロジーの変化
・少なくとも１つの論理リンクの変化
・選択したトラフィック統計の変化、例えば少なくとも１つの論理リンクの所定の（経時的な帯域幅利用の平均と分散の分布関数に基づく）確率閾値を超える帯域幅利用、またはピークのビットレートに対する平均のビットレートの比率の変化
・予め設定した時間の経過
さらに、好適な実施例によると、ルーティング・システムは、長期間（（時間、日、週、または月単位でありうる）比較的長期間オフラインで収集）のネットワークのトラフィック統計がユーザー定義の閾値を超える確率で、帯域幅のスループットに関してよりよいルーティング方式の計算をトリガーする帯域幅利用の繰返しパターンを示す場合に再構成することができる。
好ましくは、各構成可能なスイッチング・デバイスは、該スイッチング・デバイス自身のリンクに関するトラフィック情報を収集して、収集した情報を処理するために管理ステーションに送信するように状況に応じて変化し、構成される。
【００１２】
好適な実施例によると、管理ステーションは、ネットワーク経由でデータをルーティングするルーティング方式を定義し、ルーティング方式に従いネットワーク・デバイスを構成し、ネットワーク・デバイスを再構成するために事前選択した基準のうち少なくとも一つを満たしているかどうかを判定し、該基準の少なくとも一つを満たしている場合にルーティング方式を再定義し、再定義したルーティング方式に従い、好ましくはすべてオフラインで、ネットワークを再構成するコンピュータ・プログラムを含む。
【００１３】
代替実施例によると、各ネットワーク・デバイスは、ネットワーク経由でデータをルーティングするルーティング方式を定義し、ルーティング方式に従いすべてのネットワーク・デバイスを構成し、ネットワーク・デバイスを再構成するために事前選択した少なくとも１つの基準を満たしているかどうかを判定し、基準の少なくとも１つを満たしている場合にルーティング方式を再定義し、再定義したルーティング方式に従い、好ましくはすべてオフラインで、ネットワークを再構成する同一のコンピュータ・プログラムを含む。
【発明を実施するための最良の形態】
【００１４】
本発明は図面と合わせて以下の詳細な説明を読むと理解と認識が深まる。
【００１５】
本発明は電気通信キャリア・ネットワークを経由するパケットまたはフレームベースのデータ・フローの中央ルーティング・システムおよび方法に関係する。本システムでは、コア・ネットワークを経由するすべてのトラフィックを、各々が特定の送信元および宛先と、任意でサービス品質（ＱＯＳ）要求事項に対応付けられた所定のフロー（論理リンク）および物理リンクのセットの１つに対応させる。これら対応付けは「準静的」である、すなわちフロー経路は比較的長期間変わらないことが認識される。このため、ルーティング方式は一般的にネットワークが変わるときにのみ変える。加えて、ルーティング方式は他の所定の基準を満たしたとき、特に、ネットワーク・デバイスの少なくとも一部によって継続して収集したネットワーク・トラフィック・データから計算したネットワークのトラフィック統計に応答して変更する。ルーティング・システムは、これら基準を満たしたときに、ネットワーク・トポロジー、ネットワーク負荷統計、および一連のサービス品質保証制度（ＳＬＡ）に基づいて、ネットワークのネットワーク・デバイスの各々についてルーティング・テーブルを計算して更新するオフライン・アルゴリズムを利用する。本発明のある例示的な実施例の特別な特徴は、生成されるルーティング方式も準静的であること、すなわち、データ転送速度に対して長い期間更新または変更せず、これら所定の基準を満たしたときにのみ更新または変更することである。
【００１６】
本発明の例示的なシステムは先行技術に対していくつかの利点をもつ。まず、本システムは従来のキャリア・ネットワークで利用できるよりも様々なユーザーに対して優れたサービス品質を提供できる。２番目に、本システムは顧客の選好に従ってより多くのネットワーク・リソースの提供（配布）を行え、ネットワークのリソースが顧客の選好（例えば、データの均一な配布、最大限のスループット）に従って実質的に最適化されるように（準静的メカニズムを使って）十分に制御され、常に配布されることを意味する。３番目に、ピーク時間以外では利用されない帯域幅をとっておく必要がないため、ネットワーク・リソースをより効率的に利用できる。さらに、本システムは、ネットワークの要求事項の変更が、ＩＰプロトコルが使用するようなトラフィック・プロトコル外挿法を使用しないで、ユーザーによるなど直接システムに入力されるので、従来のネットワークよりもトポロジーおよびリンク方式の変化に対してネットワークの適応が速い。最後に、トポロジーの変化を常にモニタリングしないため、ルーティング・システムへの計算の負担が少なく、そのためパフォーマンスが向上する。このように、システムおよびルーターは、先行技術で起こっていたように、たとえルーティング・テーブルが変わらなくても、継続的にネットワークの現状を学習して、すべてのルーティング・テーブルを置き換えるという無駄な時間とネットワーク・リソースが必要ない。
本発明を電気通信ネットワーク、特にイーサーネット・ネットワークに関して以下詳細に説明していくが、本明細書で説明する準静的ルーティング方法は、ＩＰルーターなどのネットワーク・リソースの最適な利用のために、またストレージ・エリア・ネットワークのために、再ルーティングを必要とする他のキャリア・ネットワーク内の、あらゆる制御可能なルーティング・ドメインでの使用にも同様に適することは認識される。
【００１７】
本発明のルーティング・システムを利用したネットワーク１０に提案されるアーキテクチャの１例を図１に概略的に示す。本発明において、「ネットワーク」とはすべての物理リンクとすべての論理リンク、およびすべての着信トラフィックをルーティング・システムで制御できるあらゆるキャリア・ルーティング・ドメインである。図１において、ネットワーク１０は、ここでは４個で図示される複数のコア・ネットワーク・デバイス１３を含むコア・ネットワーク１２と、コア・ネットワーク１２に連結される複数の構成可能なスイッチング・エッジ・デバイス１４のエレメント（要素）をもつ。本実施例では、ネットワーク１０はイーサーネット・スイッチを実装する。構成可能なエッジ・デバイス１４は以下説明するようにシステムの様々な利用者が必要なデータを入力することによって構成できる。一のユーザーとサービス契約を結ぶ少なくとも一の顧客１６が各構成可能なスイッチング・デバイス１４に連結される。各構成可能なスイッチング・デバイス１４はコア・ネットワーク１２を経由するデータ・トラフィックを送信するための静的フォワーディング・テーブルまたはルーティング・テーブルを利用でき、何らかの管理プロトコルを使用して、そのリンクのすべてからトラフィック・データを収集できる。ネットワークは何らかのトポロジーでスイッチング・デバイスに接続する物理リンクを含めることができることは認識される。
管理ステーション２０は双方向通信のためにすべてのスイッチング・デバイス１４に連結する。図示する実施例では、管理ステーションは帯域内管理のためにスイッチング・デバイスに連結されている。代わりに、管理ステーションは帯域外管理のために各スイッチング・デバイス１４に物理的に連結してもよい。管理ステーション２０は適したプロセッサ（図示せず）を含み、以下詳述するアルゴリズムに従って、本発明の例示的な方法を実装するのに適切なコンピュータ・プログラム（例、コンピュータが読み取り可能な媒体に格納したコンピュータ命令）を含む。
本発明の例示的なルーティング・システムは次のように動作する。管理するキャリア・ネットワークのルーティング・ドメインまたはメトロ・ネットワークを適切なトポロジーに従って配置し、管理ステーションを様々なネットワーク・デバイスに連結する。本発明において、管理命令を実装でき（すなわち、ルーティング・テーブルを利用および更新でき）、トラフィック・データを収集およびフォワードできるスイッチ、ルーター等あらゆるネットワーク・デバイスをネットワークのリンクに利用できることが認識される。管理ステーションはコア・ネットワーク内のネットワーク・デバイスと、データ・トラフィックを送受信したい様々なユーザーに連結されるエッジ・デバイスの両方を管理できる。
【００１８】
ネットワークのトポロジーの詳細、様々な顧客が必要とする物理リンク、必要なフロー（論理リンク）は、（例えばキーボード、マウス、グラフィカル・ユーザー・インターフェースなどの入力デバイスを含むユーザー・インターフェースを介して）管理ステーションに入力されるパラメータである。このデータから仮プロビジョニング・テーブルを生成し、これらの入力パラメータのみに基づいて、最適経路を計算する。適切なルーティング・テーブルを生成して、それに従ってネットワーク・デバイスの各々を構成する。ネットワークはこれら静的経路を使って稼動を開始し、所定の基準を満たすまで変更せずに稼動を続ける。ネットワークが作動している間、ネットワーク全体の多数のスイッチング・デバイスが各経路のトラフィックに関するデータを継続的に収集する。このデータをネットワークに格納して、トラフィック統計を出すように処理する。好適な実施例によると、コア・デバイスとエッジ・デバイス両方のすべてのネットワーク・デバイスがそのデバイスに出入りするトラフィックのデータを収集して送信する。代替実施例によると、すべての着信ポートおよび発信ポートをモニタリングしてすべての経路が分かっているので、エッジ・デバイスからの統計だけを使用すれば、コア・デバイスの統計を外挿法で推定できるため、エッジ・デバイスだけがトラフィック・データを収集する。さらに別の実施例によると、ネットワーク全体のすべてのトラフィック統計を外挿法で推定するのに十分な限られた数のデバイスでのみトラフィック・データを収集する。
【００１９】
図１の例示的な実施例によると、収集したデータはすべて格納とオフライン処理のために管理ステーションに送る。
本実施例では、ネットワーク・デバイスの再構成のための多数の基準も管理ステーションに入力し、該基準のいずれもがルーティング方式の再計算とネットワークの可能な再構成をトリガーするのに十分なものである。以下にあげる基準に追加して、またはその代わりに、ユーザーは他の基準を選択してもよいが、適する基準の例のいくつかは次のとおりである。最初の基準は、物理リンクの追加または削除によるネットワーク・トポロジーの変化である。２番目の基準は、既存のトポロジーにおける少なくとも１つの論理リンクのプロビジョニングまたはフローの変化である。以上の場合のいずれにおいても、すべてオフラインで、ユーザーは（例えば、ユーザー・インターフェースを介して）ネットワークに新たなパラメータを入力し、ルーティング方式を再定義し、更新したルーティング・テーブルを生成する。更新したルーティング・テーブルは、複数のデバイスの再構成を同期させる命令とともに各ネットワーク・デバイスに提供され、その時点でネットワークは新たな静的ルーティング方式に変わる。
【００２０】
本発明によると、システムは経路計算のトリガーとなる他の基準も考慮することができる。本発明のある実施例によると、新たなルーティング方式を計算する事前選択した基準には、以下の追加事象（追加イベント）の１つまたは全部を含めることができる。
・一または複数の選択したトラフィック統計の変化、例えば、少なくとも１つの論理リンクの所定の確率閾値（経時的な帯域幅利用の平均と分散の分布関数）を超える帯域幅の利用
・前回の計算または再構成からの事前選択した時間の経過
・ユーザー定義の確率値、変化の規模、および時間の長さの閾値を超える帯域幅の利用の繰返しパターン、例えば、金曜午後から土曜日夜まで一定の場所における度重なる低下
新たなルーティング方式を計算したら、新たに計算したルーティング方式に従ってネットワークを再構成するかどうかを判定するために追加基準を利用することができる。好適な基準は、新たに計算したルーティング方式が現行のルーティング方式と比べてパフォーマンスが向上する（一または複数のネットワーク・メトリックが向上する）確率である。このように、代替ルーティング方式を計算したら、ネットワークの総スループットまたは以下詳述する他のメトリック（例えば、均一な配布、最低限の遅延等）に対するその影響を計算して、現行のネットワーク・メトリックと比較する。改善がみられない場合、または改善レベルが予め設定した閾値に達しない場合、この時点ではルーティング・テーブルを更新しない。予め設定した閾値以上に改善が期待され、改善によりこの値が予め設定した最低閾値に達する確率（例えば、９０％の確率でスループットが少なくとも１０％向上する確率）および、エンドユーザーが事前選択した連続する経路変更の間隔の最低期間の時間閾値を満たす場合、新たなルーティング方式に従って更新ルーティング・テーブルを作成して、複数のデバイスの再構成を同期させる命令とともに各ネットワーク・デバイスに提供し、その時点でネットワークは新たな静的ルーティング方式に変わる。
【００２１】
帯域幅利用の変化は以下のように判定できる。各論理リンクについて、そのリンクのユーザーはルーティング方式の再計算をトリガーするための帯域幅利用の確率の最低許容値（例えば、９５％）とその確率が維持しなければならない最低期間を選択する。本発明によると、実際のデータ・トラフィックに関してネットワーク内で収集した情報（各測定時点における帯域幅利用の測定値）を管理ステーションで受信および格納し、管理ステーションが経時的な平均と分散の分布を含めたトラフィック統計を計算し、これから、論理フローの各々について、帯域幅利用の確率値を計算する。
ユーザーは、１日など一定の事前選択した期間が経過する度に、ネットワークが最適レベルで稼動しているかを確認したいかを決定できる。再計算基準の１つとしてこの事前選択した期間を入力することによって、ユーザーは定期的にルーティング方式が再計算され、その見込みパフォーマンスが現行のパフォーマンスと比較されることを確保する。再計算されたルーティング方式の見込みパフォーマンスが現行のパフォーマンスと比較してメトリック値の改善になる場合、ネットワークを再構成する。
ルーティング方式の再計算のさらに別の例示的な基準は、帯域幅利用の繰返しパターンの発見である。トラフィック統計はネットワーク全体から継続的に収集され、管理センターに格納されるため、長期間（時間、日、週、または月単位）でオフラインで収集したネットワーク・トラフィックの長期間の統計もルーティング方式の最適化のために調査および利用できる。これら長期間の統計は帯域幅利用の繰返しパターンのユーザー定義の閾値を超える確率、例えば、平日のパターンとは異なる各週末の類似の利用パターン、または毎日定時の１０分間ある顧客の利用の増加を示す場合、新たなルーティング方式の計算がトリガーされ、それを帯域幅スループットまたはユーザーが予め定義した他の選択したメトリックに関して現行のルーティング方式と比較する。
【００２２】
ここで、本発明の好適な実施例による操作方法を、方法を図示する図２、３、および４のフローチャートに関連して説明していく。操作方法は主に以下の３つのタスクに分割できる。
１．ネットワークの初期化または「コールド・スタート」−図２に概略的に図示するネットワークの初期の学習および構成
２．ネットワークのランタイム−図３に概略的に図示する動作の稼動モードで、ネットワークはネットワーク・リソースの利用を最適化するためにルーティング方式をトラフィック・パターンに適応させることができる。
３．構成の変更−トポロジーの変更（必要な物理リンクの変更（例、物理リンクの追加および／または削除））、または図４に概略的に図示する論理リンクの変更、例えばフローの追加および／または削除のいずれか。
【００２３】
ここで図２を参照すると、本発明のある実施例によるネットワークの初期化（ブロック２２）を図示するフローチャートが示されている。ネットワークは構成されていないと仮定するが、ネットワーク・オペレータは以下詳述されるネットワーク・パラメータと、必要なサービスおよび／または論理リンクを知っていることが前提条件である。ネットワーク初期化または「コールド・スタート」はネットワークが初めから安定してかつ効率的に（最適ではなくても）動作を開始できるように設計されたいくつかの初期プロセスを含む。このため、ネットワークの動作開始のために複数のフローと経路に最初に分割する。
まず、予備ネットワーク学習をしておく（ブロック２４）。管理ステーションがネットワークのトポロジーを把握してネットワーク経由のデータ・トラフィックの経路を計算できるようにするために、ネットワークの初期パラメータを手作業で、または自動学習プロトコルを使って、管理ステーションに入力しなければならない。これらパラメータには次の項目が含まれる。
１．ネットワークで利用できるスイッチの数
２．各スイッチのポート数とその固有識別子
３．各ポートで利用できる帯域幅
４．ネットワーク・エレメントの物理的な接続方式、すなわちどのポートをどの物理リンクによって他のどのポートに接続するか
５．必要な論理リンク、その対応する送信元と宛先およびＳＬＡ
６．任意で、資本コストまたは相対コストに関し、ユーザーが負担する各リンクの使用コスト
この手動入力および／または自動学習プロトコルを使用する点は、ネットワークが独立してネットワークのトポロジーと論理リンクを学習しなければならないインターネットおよび同様なネットワークとはかけ離れていることが認識される。この点がネットワークの最適化プロセスのスピードアップと、不必要な計算のためのネットワーク・リソースの利用の減少に役立つ。
【００２４】
各論理リンクを含む必要なリンク方式は、送信元ポート・スイッチおよび宛先ポート・スイッチを含む入力である（ブロック２６）。論理リンクの必要な帯域幅（ｂｐｓ単位）を、必要な認定情報速度（ＣＩＲ）および／または必要な最大情報速度（ＰＩＲ）および／または必要な最大バーストサイズ（ＭＢＳ）などのあらゆる論理リンクの必要な帯域幅パラメータとともに定義する。最後に、望むなら、保護方式を設けてもよく、すなわちメインの物理リンクに障害が起こった場合に、物理リンクの障害許容および復旧のために事前に構成した代替経路の確立を可能にする任意のパラメータである。この場合、ネットワーク・デバイスは障害許容方式をサポートすることが認識される。
【００２５】
すべての入力データを受信した後、管理ステーションは入力パラメータを前提として、好ましくは、前のステップ中にユーザーが入力したユーザーの選好に応じた以下の制約事項またはメトリックの一部もしくは全部に従い、最適ルーティング方式を計算する（ブロック２８）。
１．ネットワークのスループットの向上
２．できるだけ最短パスを利用する（遅延を最小限にするため）
３．ネットワーク帯域幅リソースの均一な配布および利用の提供（ネットワークをより安定させ、ネットワーク全体にわたり再ルーティングを少なくするため）、これは例えばリンク間の分散が所定のパーセンテージよりも小さいものと定義できる
４．どのリンクについても、所定の値または計算値に対する（ΣＰＩＲ−ΣＣＩＲ）／（リンク許容量−ΣＣＩＲ）の比率を最小限にする。このため、保証されないトラフィックが過度にオーバーサブスクライブドにならない。
５．どの物理リンクでも総計ＣＩＲおよびＭＢＳをユーザー設定値未満に制限する。
６．経路のコストを最小限にする、すなわちユーザーのコスト負担が大きくなるリンク（例えば、ローカル回線に対して長距離回線）の使用をできるだけ少なくする。
ネットワークの経路を計算したら、管理システムはサニティ・チェックを行う（ブロック３０）。これは、ネットワークに必要な論理リンクとそれに対応するパラメータを割り当てることができる、すなわち十分な帯域幅があり、適正な物理リンクが存在すること（どの物理リンクにおいても総計ＣＩＲトラフィックをその物理リンクで利用できる帯域幅未満に制限することを含む）を検証することを意味する。サニティ・チェックにパスしなければ、管理ステーションはユーザーに通知し、論理リンクのパラメータの変更を提案する（ブロック２６）。
【００２６】
サニティ・チェックにパスしたら、管理ステーションはネットワーク・デバイスを構成する（ブロック３２）。管理ステーションは前のステップで計算したルーティング・パスを、イーサーネット・ネットワーク、ＭＰＬＳラベル・フォワーディング・テーブル、ＭＡＣ（媒体アクセス制御）またはあらゆる他のタイプの分類子を含むルーティング・テーブルに変換し、何かの標準管理プロトコルを使用してルーティング・テーブルを構成コマンドと一緒に様々な構成可能なスイッチ（ネットワーク・デバイス）に送る。これで、ネットワークは構成された経路を使って稼動を開始する（ブロック３４）。
本発明のシステムは、従来のほとんどのイーサーネットおよびＩＰ型のネットワークがするようにネットワークのトポロジーの動的なリアルタイム学習に依存しなくてもよいことが認識される。むしろ、ネットワークのトポロジーを管理ステーションに入力するので、本ネットワークのデバイスはネットワークのトポロジーを独立して学習する必要がない。この結果、前述したように、ネットワークの稼働中時間とリソースの大幅な節約となる。
【００２７】
本発明のある実施例によると、ネットワーク内部で把握されネットワーク内部でのみ使用するプライベートＭＡＣアドレスをネットワーク内の様々なノードまたはデバイスに割り当てる。プライベートアドレスは必ずしもＭＡＣアドレスである必要はなく、ネットワーク内のノードに与えられたあらゆる他のアドレス（例えば、ＩＰアドレスまたはＭＰＬＳパスなど）でもよいことが認識される。これらプライベート・ネットワーク・アドレスはランダムに生成しても、または事前選択したルールに従って生成してもよい。当業者には、これらプライベート・ネットワーク・アドレスは、その物理リンクを経由する各フローに関する情報を運ぶのにも使えることは認識される。この情報は、例えば、サービスの種類、保護手段があるかどうか、ルーティング階層に関するルーティング情報等を示すことができる。
プライベート・ネットワーク・アドレスの使用は、ハッカーおよびネットワーク内のノードにアクセスしようとする他の未許可の個人に対するネットワークの追加的な保護となる。望む場合、各顧客はそのすべてのステーションに対して１つのプライベート・ネットワーク・アドレスを割り当ててもよく、顧客内の個々のステーションはその従来のＭＡＣアドレスを内部利用及び外部利用の両方のためにとっておく。このように、ネットワーク内（またそのため、ルーティング・テーブル内）に必要なアドレス数は大幅に減少でき、それによって処理時間が短縮し、ネットワーク内のルーティングの効率が高まる。ランダムなプライベート・ネットワーク・アドレスまたは所定のルールに従ったプライベート・ネットワーク・アドレスの生成の選択は、管理ステーションで行える。代わりに、準静的アルゴリズムをいくつかのスイッチング・デバイス間に配布する場合、スイッチング・デバイスで実行するためにアドレス割り当て命令も配布される。
【００２８】
ここで図３を参照すると、本発明の好適な実施例によるネットワークの動作のネットワークのランタイム・モードを図示するフローチャートが示されている。この動作モードのとき、ネットワークのルーティングは所定の基準を満たしたときにネットワーク・トラフィック・パターンに適応する。すなわち、システムは様々なノードの経時的なデータ・トラフィック負荷に関する情報を収集、格納して、それに従い自己更新するので、ネットワーク・リソースの最適な利用に近づく。
こうして、ネットワークはある期間の間、当初の入力パラメータを使って生成されたデバイス構成、またはネットワークが最も最近更新したデバイス構成を利用して稼動する（ブロック４０）。システムの稼働中、各ネットワーク・デバイスは経時的な帯域幅利用について、それに接続される各物理リンクの利用に関する統計を収集する（ブロック４２）。この情報を何らかのシグナリング・プロトコルを使用して管理ステーションに送る。管理ステーションはデータを格納し、データを処理して様々なトラフィック統計、特に平均帯域幅利用または必要量、その分散、および帯域幅と経時的分散分布、並びに帯域幅利用の確率を計算する。ルーティング変更するための少なくとも１つの所定の基準を満たしたとき（ブロック４４）、管理ステーションは計算したトラフィック統計に基づいてルーティング方式の再計算を開始する（ブロック４６）。このルーティング最適化計算はユーザーが事前に選択した最適化基準と管理ステーションへの入力を利用する。これら基準には、特に、ユーザーが選択した最短パスの利用、ネットワーク内のトラフィックのほぼ均一な配布の提供、コア・ネットワークを経由するトラフィックのスループットの増加（ネットワークに出入りする帯域幅）が含まれよう。
【００２９】
本発明の好適な実施例によると、この新たに計算したルーティング方式は、ユーザーが事前に選択した一または複数のネットワーク・メトリックで測定して、ネットワーク内の帯域幅利用が全体的に改善しない限り実施しない。これらメトリックには、ネットワーク内のトラフィックの均一な配布の向上、コア・ネットワークを経由するトラフィックのスループットの増加等、および改善の確率を含むことができ、改善の規模はユーザーが選択した閾値（すなわち、９０％の確率でスループットが少なくとも１０％増加する）を超えなければならない。
本発明の本実施例によると、ルーティング方式の再計算とネットワークの再構成は動的ではなく、すなわちリアルタイムで起こるのではなく、所定の基準の閾値に達したときだけ起こる。例えば、前述したように、管理ステーションは論理フローの各々について、経時的な平均と分散分布を含めたトラフィック統計を計算し、これらから、帯域幅利用の確率値を計算する。この帯域幅確率値を入力した帯域幅利用確率閾値と比較する。検出された帯域幅利用が入力値より低い確率で変化する限り、または最低期間未満の間は、管理ステーションは情報の収集および格納とそれをトラフィック統計に処理することを続ける（ブロック４２）。
検出された帯域幅利用が最低閾値を超える期間で少なくとも入力した確率値で変化すると、管理ステーションは、様々な入力ネットワーク・パラメータとともに、収集、計算したトラフィック・データおよび統計を利用して、経路最適化を実行し、ネットワークの新たなルーティング方式を計算する（ブロック４６）。このように、再計算され、更新されたルーティング方式はネットワーク挙動によりよく適応し、ネットワーク全体のトラフィックをよりよくかつより均一に配布して（ビジーなパスをアンロードし、未使用のパスをロードするように）、より安価なパスを最大限に利用する（コスト関数を使って）、および／またはユーザーが定義する何か他の基準を考慮する。これらのステップはすべてネットワークの稼働中にオフラインで行うのが好ましいことは認識される。すなわち、ルーティング方式の変更はネットワーク経由のデータ転送速度に対して相対的にゆっくりと実施されることを意味する。
これで管理ステーションは、新たに計算したルーティング方式がネットワークのスループット（総伝送帯域幅）またはネットワークに関して何か他の選んだメトリックを増加させるかどうかを判断する（ブロック４８）。増加させなければ、管理ステーションは情報の収集および格納と、情報をトラフィック統計に処理することを続ける（ブロック４２）。メトリックが改善する場合には、管理ステーションはサニティ・チェックを行う（ブロック５０）。
【００３０】
サニティ・チェックにパスしたら、管理ステーションは前のステップで計算したルーティング・パスを、イーサーネット・ネットワーク、ＭＰＬＳラベル・フォワーディング・テーブル、ＭＡＣ（媒体アクセス制御）または何か他の種類の分類子を含む新たなデバイス構成用のルーティング・テーブルに変換して（ブロック５２）、何か標準的な管理プロトコルを使って構成コマンドを様々な構成可能なスイッチに送る。これが完了して検証されたら、ノード間に合理的なクロック・コヒーレンスがあると仮定すると、ネットワーク全体に「同時に」実行に移すのが好ましい。これは、例えば、ＧＰＳクロックを利用して確保できよう。代わりに、すべてのコア・ノードが少なくとも１つの構成スイッチに直接的なリンクをもつと仮定すると、複数の構成可能なエッジ・スイッチを同期させて、エッジ・ノードにコア・ノードの更新を同時にトリガーさせれば十分である。こうして新たなルーティング・パスへの変換がほぼ同時に起こるようにすべてのスイッチを同期させる。その時点で、ネットワークは新たに構成された経路を使って稼動を開始する（ブロック４８）。
本発明の好適な実施例によると、初期化中、ユーザーは異なる３セットの基準を入力できることは認識される。１セットめの基準は新たなルーティング・テーブルの計算を開始するための様々なルーティング変更基準（すなわち、帯域幅利用の確率）を含む。２セットめは、前記新たなルーティング方式の計算で利用するための最適化基準（均一な配布、最短パス）を含む。３セットめは、前記新たに計算されたルーティング方式に従いネットワークを再構成するかどうか、またはいつ再構成するかを決定する再構成基準（すなわち、スループットまたは他のメトリックの所望の変化率を超えた改善）を含む。
さらに、本発明の例示的なルーティング・システムはある期間中のネットワークの実際の状態に関して収集したデータに基づくだけでなく、ネットワークのトポロジーの変化にも応答して定期的なデバイスの再構成を行うことが認識される。
【００３１】
図４は本発明の実施例におけるネットワークの動作の構成変更モードを図示するフローチャートである。ユーザーはデバイスおよび物理リンクを追加または削除することによって、いつでもネットワークのトポロジーを変更できる。また、ユーザーは既存のトポロジーにおいて新たなサービスまたは既存のサービスを供給、削除もしくは変更してもよく、論理リンクを変更して、またはトポロジーを変更して一斉にサービスを更新することもできる。構成変更プロセスはネットワークの初期化のプロセスと似ているが、情報をランタイム・モードでネットワーク上で収集するというメリットが追加される。
ユーザーが構成変更に関して新たなパラメータを管理ステーションに入力すると（ブロック６０）、管理ステーションはネットワーク・トポロジーが変化したかどうか、およびトポロジーの更新が必要かどうかを判定する（ブロック６２）。もしトポロジーが変化していたら、管理ステーションが新たなトポロジーを把握して、更新経路を計算できるように、ネットワーク変更の初期のパラメータを管理ステーションに入力しなければならない（ブロック６４）。これらパラメータには、追加あるいは削除するスイッチの数、各スイッチのポート数、各ポートで利用できる帯域幅、各ポートの識別子、および修正したネットワーク・エレメントの物理的接続方式、すなわち、どのポートをどの物理リンクによって他のどのポートに接続するかが含まれる。
【００３２】
ネットワーク・トポロジーが変化していない場合、または、変化していれば、ネットワーク・トポロジーが更新されている場合、管理ステーションは論理リンク方式に変更が必要かどうか（すなわち、新たなプロビジョニング・テーブルが必要かどうか）を判定する（ブロック６６）。さらに、追加あるいは削除が必要な物理リンクおよびその各パラメータのすべてを構成する。送信元ポート・スイッチおよび宛先ポート・スイッチを含め、論理リンクの経路が定義される。論理リンクに必要な帯域幅（ｂｐｓ単位）を、必要な認定情報速度（ＣＩＲ）、必要な最大情報速度（ＰＩＲ）、必要な最大バースト・サイズ（ＭＢＳ）など、あらゆる必要な帯域幅パラメータと一緒に定義する。最後に、必要であれば、保護方式を設ける、例えば、メインの物理リンクに障害が起こった場合に物理リンクの障害許容および復元のために事前に構成した代替経路に切換られる任意のパラメータである。この場合、ネットワーク・デバイスは障害許容方式をサポートすることは認識される。
【００３３】
必要な論理リンク方式が更新されたら（ブロック６８）、管理ステーションは、各パスの利用について収集した統計と一緒に、新たに入力したパラメータを前提として、最適経路を計算する（ブロック７０）。最適経路は、できるだけ最短のパス、ほぼ均一な配布、およびネットワーク・帯域幅リソースの利用をもたらし、どの物理リンクにおいても総計ＣＩＲトラフィックをその物理リンクで利用できる帯域幅未満に制限し、任意で、どの物理リンクにおいても総計ＣＩＲおよびＭＢＳトラフィックをユーザー設定値未満に制限するようにすることが望ましい。経路の計算後、管理ステーションはサニティ・チェックを行い（ブロック７２）、ネットワークに必要な論理リンクと該論理リンクの対応パラメータが割り当てられるかを検証する。割り当てられない場合、管理ステーションはユーザーに通知して、論理リンク・パラメータの変更を提案する（ブロック６８）。サニティ・チェックにパスしたら、前ステップで計算したルーティング・パスを利用して新たなルーティング・テーブルを用いてネットワーク・デバイスを再構成し（ブロック７４）、同時に、ネットワークは新たに構成した経路を使って稼動を開始する（ブロック７６）。
このように、本発明は、ネットワークの過去の履歴および現在の利用または必要量の統計に基づいて、パケットベースのネットワークまたはルーティング・ドメインに集中ルーティングを提供する。ネットワーク・デバイスの一または複数において、またはすべてのデバイスが同じソフトウェアをもち、すべてのネットワークのトラフィック統計を共有する場合は同時に全てのネットワーク・デバイスにおいて、これらグローバル・ルーティング方式を前述した中央管理ステーションで計算できる。このように、本発明の代替実施例によると、本発明の方法を実装するコンピュータ・プログラムをネットワーク・デバイスのすべてに提供し、ネットワーク・デバイスの各々が他のすべてのデバイスからすべてのトラフィック・データを受信し、同一の統計および同一のルーティング方式を計算する。代わりに、一または複数のスイッチング・デバイスがすべてのトラフィック・データを受信して、それを利用してすべてのネットワーク統計を計算し、ネットワーク内のすべてのスイッチング・デバイスのために追加処理を行うことができる。
【００３４】
本発明は限られた数の実施例に関して説明してきたが、本発明の多くの変形、修正および他の応用を行えることは認識される。さらに、本発明は単なる例として上記説明してきたものに制限されないことについても認識される。むしろ、本発明は特許請求の範囲によってのみ制限されるものである。
【図面の簡単な説明】
【００３５】
【図１】本発明のある実施例により構築し作動状態にある通信ネットワークの概略図である。
【図２】本発明のある実施例によるネットワークの初期化を図示するフローチャートである。
【図３】本発明のある実施例によるネットワークの動作のネットワークランタイムモードを図示するフローチャートである。
【図４】本発明のある実施例によるネットワークの動作の構成変更モードを図示するフローチャートである。
【図１】
2008527941.tif 000003
【図２】
2008527941.tif 000004
【図３】
2008527941.tif 000005
【図４】
2008527941.tif 000006
【国際調査報告】
2008527941.tif 000007
2008527941.tif 000008
2008527941.tif 000009