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