(57)【特許請求の範囲】
【請求項１】
パケットベースの通信ネットワークを設計する、プロセッサベースの方法において、
（Ａ）  リンク及び関連する容量を有する初期ネットワークトポロジーを付加リンク及び容量のうちの一方で増強する段階と、
（Ｂ）  少なくとも単一の接続に係るフロー要求を前記パケットベースネットワークにおいてルーティングできるようになるまで前記増強段階を反復する段階とを有し、前記（Ａ）増強する段階がさらに、
（Ａ１）  エンド−ツー−エンド要求フローをそれらに係る最小スループット要求に基づいてキーパー要求とストラグラー要求とに分割する段階と、
（Ａ２）  前記キーパー要求を所定のルーティングアルゴリズムに従って完全なネットワークトポロジーを表わすグラフに係るリンク上でルーティングする段階と、
（Ａ３）  前記完全グラフ中の前記キーパー要求をルーティングするように指定されたリンクを用いて前記完全ネットワークトポロジーの一部を表わすサブグラフを構成する段階と、を有することを特徴とするネットワーク設計方法。
【請求項２】
前記（Ａ）増強する段階が、さらに、
（Ａ４）  前記キーパー要求から構成された前記サブグラフ中にストラグラー要求を満たす経路が存在するか否かを決定する段階を有することを特徴とする請求項１に記載のネットワーク設計方法。
【請求項３】
前記増強する段階が、さらに、
（Ａ１８）  ストラグラー要求を満たす経路が前記サブグラフ内に存在する場合には前記サブグラフ内の最短経路に沿って前記ストラグラー要求をルーティングする段階と、
（Ａ１９）  前記経路に沿って前記ストラグラー要求を満たす適切な接続性及び容量のうちの一方が存在するか否かを決定する段階と、を有することを特徴とする請求項１に記載のネットワーク設計方法。
【請求項４】
前記方法が、さらに、
（Ｃ）  前記ネットワークトポロジーが充分に最適化されたか否かを決定する目的でネットワーク費用値を計算する段階を有することを特徴とする請求項１に記載のネットワーク設計方法。
【請求項５】
パケットベースのネットワークを設計する装置において、
リンク及び関連する容量を有する初期ネットワークトポロジーを付加リンク及び容量のうちの一方で増強する少なくとも一つのプロセッサと、
ここで、前記プロセッサは少なくとも単一の接続に係るフロー要求が前記パケットベースネットワークにおいてルーティングされうるようになるまで前記増強を反復し、
前記初期ネットワークトポロジー及び前記増強されたネットワークトポロジーのうちの単一あるいは複数個をストアするメモリと、を有し、
前記プロセッサがさらに、
エンド−ツー−エンド要求フローをそれらに係る最小スループット要求に基づいてキーパー要求とストラグラー要求とに分割し、前記キーパー要求を所定のルーティングアルゴリズムに従って完全なネットワークトポロジーを表わすグラフに係るリンク上でルーティングし、及び、前記完全グラフ中の前記キーパー要求をルーティングするように指定されたリンクを用いて前記完全ネットワークトポロジーの一部を表わすサブグラフを構成することによって増強を実行することを特徴とするネットワーク設計装置。
【請求項６】
機械によって読みとり可能な単一あるいは複数個のプログラムを含む媒体を有するパケットベース通信ネットワーク設計装置において、前記プログラムが、実行された場合に、
リンク及び関連する容量を有する前記パケットベース通信ネットワークの初期ネットワークトポロジーを付加リンク及び容量のうちの一方で増強する段階と、
少なくとも単一の接続に係るフロー要求が前記パケットベースネットワークにおいてルーティングされうるようになるまで前記増強段階を反復する段階とをインプリメントし、前記増強する段階がさらに、
エンド−ツー−エンド要求フローをそれらに係る最小スループット要求に基づいてキーパー要求とストラグラー要求とに分割する段階と、
前記キーパー要求を所定のルーティングアルゴリズムに従って完全なネットワークトポロジーを表わすグラフに係るリンク上でルーティングする段階と、
前記完全グラフ中の前記キーパー要求をルーティングするように指定されたリンクを用いて前記完全ネットワークトポロジーの一部を表わすサブグラフを構成する段階と、を有することを特徴とするネットワーク設計装置。
【請求項７】
パケットベース通信ネットワークを設計する、プロセッサベースの方法において、該方法は、
リンク及び関連する容量を有する初期ネットワークトポロジー中の単一あるいは複数個のリンクをデロードする段階からなり、前記単一あるいは複数個のリンクは、前記パケットベース通信ネットワーク内でルーティングされる少なくとも一つの接続に関連するトラフィック要求に関して比較的軽い負荷を有しており、該方法はさらに、
あらゆるリンクの除去がネットワーク費用の著しい低減をもたらさないと考えられるようなリンクネットワークトポロジーが実現されるまで前記デロードする段階を反復する段階からなり、
前記デロードする段階が、さらに、
調節可能な利用閾値に基づいて前記トラフィック要求に関する比較的軽い負荷を有する候補リンクを識別する段階と、
前記トラフィック要求と各々の候補リンクを通過するフローのホップ数との積の総和を計算する段階と、
最小の総和を有する候補リンクを選択して前記リンクを前記ネットワークトポロジーから一時的に除去する段階と、
前記一時的に除去されたリンクを除く前記ネットワークトポロジーに係るネットワーク費用値を計算する段階と、
前記ネットワーク費用値が低減される場合に新たなネットワークトポロジーを構成する目的で前記一時的に除去されたリンクを前記ネットワークトポロジーから除去する段階と、
前記ネットワーク費用が低減されない場合に前記一時的に除去されたリンクを前記ネットワークトポロジーに再挿入する段階と、を有することを特徴とするネットワーク設計方法。
【請求項８】
パケットベース通信ネットワークを設計する装置において、
リンク及び関連する容量を有する初期ネットワークトポロジー中の単一あるいは複数個のリンクをデロードする少なくとも一つのプロセッサと、
ここで、前記単一あるいは複数個のリンクは、前記パケットベース通信ネットワーク内でルーティングされる少なくとも一つの接続に関連するトラフィック要求に関して比較的軽い負荷を有している当該プロセッサは、あらゆるリンクの除去がネットワーク費用の著しい低減をもたらさないと考えられるようなリンクネットワークトポロジーが実現されるまで前記デロード段階を反復し、
候補リンク、ネットワークトポロジー、及びネットワーク費用よりなる単一あるいは複数個のリストをストアするメモリとを有し、
前記プロセッサがさらに、
調節可能な利用閾値に基づいて前記トラフィック要求に関する比較的軽い負荷を有する候補リンクを識別し、
前記トラフィック要求と各々の候補リンクを通過するフローのホップ数との積の総和を計算し、
最小の総和を有する候補リンクを選択して前記リンクを前記ネットワークトポロジーから一時的に除去し、
前記一時的に除去されたリンクを除く前記ネットワークトポロジーに係るネットワーク費用値を計算し、
前記ネットワーク費用値が低減される場合に新たなネットワークトポロジーを構成する目的で前記一時的に除去されたリンクを前記ネットワークトポロジーから除去し、
前記ネットワーク費用が低減されない場合に前記一時的に除去されたリンクを前記ネットワークトポロジーに再挿入することによって前記リンクデロードを実行することを特徴とするネットワーク設計装置。
【請求項９】
機械によって読みとり可能な単一あるいは複数個のプログラムを含む媒体を有するパケットベース通信ネットワーク設計装置において、前記プログラムが、実行された場合に、
リンク及び関連する容量を有する初期ネットワークトポロジー中の単一あるいは複数個のリンクをデロードする段階と、
ここで、前記単一あるいは複数個のリンクは、前記パケットベース通信ネットワーク内でルーティングされる少なくとも一つの接続に関連するトラフィック要求に関して比較的軽い負荷を有し、
あらゆるリンクの除去がネットワーク費用の著しい低減をもたらさないと考えられるようなリンクネットワークトポロジーが実現されるまで前記デロードする段階を反復する段階とをインプリメントし、
前記デロードする段階がさらに、
調節可能な利用閾値に基づいて前記トラフィック要求に関する比較的軽い負荷を有する候補リンクを識別する段階と、
前記トラフィック要求と各々の候補リンクを通過するフローのホップ数との積の総和を計算する段階と、
最小の総和を有する候補リンクを選択して前記リンクを前記ネットワークトポロジーから一時的に除去する段階と、
前記一時的に除去されたリンクを除く前記ネットワークトポロジーに係るネットワーク費用値を計算する段階と、
前記ネットワーク費用値が低減される場合に新たなネットワークトポロジーを構成する目的で前記一時的に除去されたリンクを前記ネットワークトポロジーから除去する段階と、
前記ネットワーク費用が低減されない場合に前記一時的に除去されたリンクを前記ネットワークトポロジーに再挿入する段階と、を有することを特徴とするパケットベース通信ネットワーク設計装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパケットベースネットワークの設計方法及びその装置に関し、特に性能を保証したＩＰ（インターネットプロトコル）ネットワークの設計に関する。
【０００２】
【従来の技術】
従来技術に係るＩＰネットワークは、その能力に係る企画・設計の最適化が非常に限られた状態で構築されてきた。これらのネットワークは、性能を保証せず、“できるだけの努力をすることによって実現されるサービス”のみを提供している。しかしながら、顧客の期待は、ＩＰネットワークが予測可能な性能を提供するように設計されることによって初めて充足される。特に、ネットワークサービスプロバイダは、彼ら自身の仮想プライベートネットワーク（ＶＰＮ）顧客に対して、帯域保証をサポートしなければならない。
【０００３】
加えて、あらゆるネットワーク設計に係る考慮事項に含まれるべきことは、与えられたネットワークにおいて用いられるネットワークルータには複数のタイプが存在する、という事実である。例えば、ルーセント・テクノロジー（Lucent Technologies, Inc.、New Jersey州Murray Hill）社より市販されているLucent's PacketStarTMＩＰスイッチは、重み付け公平キューイング（ＷＦＱ）及び最長キュードロップ（ＬＱＤ）を用いたフロー毎キューイングを含む、斬新なトラフィックスケジューリング並びにバッファ管理能力を有しており、非常に高いレベルのリソース利用率を達成しつつＶＰＮに対する最小帯域保証を行なうことを可能にしている。他方、既存のレガシールータは、適切なフロー分離をサポートせず、それらの先入れ先出し（ＦＩＦＯ）スケジューリングが、ランダム早期検出（ＲＥＤ）バッファ管理ポリシーと組み合わせた場合においてさえも、ＶＰＮ間で共有される帯域にわずかの制御しか行なうことができず、スループットがＴＣＰ（トランスミッション制御プロトコル）の動的性質によって大きく影響を受けてしまう。このＴＣＰは、ＩＰネットワークにおいて最も多く用いられている転送プロトコルである。
【０００４】
【発明が解決しようとする課題】
従って、ユーザ、すなわちネットワークデザイナに、同一（同種）あるいは異なった（異種）タイプのルータを有し、例えばＶＰＮ等の種々のアプリケーションに関して実質的な性能の保証を実現するＩＰネットワークを設計することを可能にする、ネットワーク設計ツールに関する要求が存在する。詳細に述べれば、デザイナによって与えられる仕様に基づいてワーストケース及び最良の必要リンク容量を自動的に計算し、ネットワークのトポロジーを最適化し、及び、ネットワークにおける最適ルータ配置を決定する設計ツールに係る要求が存在する。
【０００５】
【課題を解決するための手段】
本発明は、既存のＩＰネットワーク、例えば“最大の努力”基準の下に設計されたネットワークなどと比較して、実質的に改善された性能を有するＩＰネットワークを設計する方法及び装置を提供する。詳細に述べれば、本発明は、ワーストケース及び最良のリンク能力要求を自動的に計算し、ネットワークのトポロジーを最適化し、及び、ネットワークにおける最適ルータ配置を決定する方法及びその装置を含んでいる。
【０００６】
本発明の第一の側面においては、ネットワークのリンクに係る必要リンク容量を計算する方法及びその装置が提供される。詳細に述べれば、最大及び最小リンク容量限界が計算可能であって、ユーザに、種々の設計パラメータの関数としてワーストケース及び最良の結果を提供する設計方法論が提供される。すなわち、与えられたネットワークトポロジー、特定のＩＰ要求及びネットワーク遅延に関して、本発明に係る設計方法は、ユーザが、与えられたネットワークの各々のリンクに係る種々のネットワーク混雑シナリオ、例えばネットワーク全体に係る複数個のボトルネック事象の発生など、に係る必要リンク容量を計算することを可能にする。本発明に係る設計方法においては、ユーザは、特定のトポロジーが与えられると、そのネットワークのどの位置に特定のボトルネックが存在しているかを知ることを必要とせずに、ＩＰネットワークを設計することが可能である。さらに、本発明に係るリンク容量計算法は、与えられた要求内に単一あるいは複数個の接続が存在するような場合も取り扱う。
【０００７】
本発明に係る第二の側面においては、ネットワーク設計に関連するネットワークトポロジーを最適化する方法及び装置が提供される。詳細に述べれば、最適ネットワークトポロジーが、本発明に従って、全体としてのネットワークコストの低減を指向するように定式化される。ある実施例においては、ネットワークトポロジーにあまり用いられないリンクを付加することではなく、ある既存のリンクのスペア容量に係るわずかな要求をパックすることによって、ネットワークコストの低減を指向する反復増強法が提供される。別の実施例では、最適ネットワークトポロジーを構成する目的で、負荷の軽い識別されたリンクを除去することによってネットワークコストの低減を指向する反復デロード法が提供される。
【０００８】
本発明に係る第三の側面においては、ネットワークコスト削減を最大にすることを目指して既存のネットワークにおけるＦＩＦＯ／ＲＥＤルータを置換するためのＷＦＱ／ＬＱＤルータの配置を決定する方法及び装置が提供される。本発明に係る方法は、混合整数プログラミングモデルを利用することによってこの種の決定を実現する。
【０００９】
【発明の実施の形態】
以下、本発明は、ＶＰＮの枠組みの中で記述される。しかしながら、本発明はそのようなアプリケーションあるいはシステムに限定されているのではない。本明細書に記述されている考え方は、あらゆるＩＰアプリケーション及びシステムアーキテクチャを含むあらゆるタイプのパケットベースのネットワークに対して適用可能である。さらに、本明細書において用いられている“プロセッサ”という術語は、ＣＰＵ（中央処理ユニット）及び関連するメモリを含むあらゆる処理デバイスを包含することを企図したものである。本明細書において用いられる“メモリ”という術語は、プロセッサあるいはＣＰＵに関連するメモリ、例えばＲＡＭ、ＲＯＭ、固定記憶デバイス（例えばハードディスクドライブ）、あるいはリムーバブル記憶デバイス（例えばフロッピーディスク）等を含むものである。加えて、処理デバイスは、例えばキーボードのような、処理ユニットにデータを入力する単一あるいは複数個の入力デバイス、及び、ＣＲＴディスプレイ及び／あるいはプリンタのような、処理ユニットに係る結果を出力する単一あるいは複数個の出力デバイスを有している。さらに、プロセッサに関連する種々の要素が他のプロセッサによって共有される場合もあり得ることに留意されたい。従って、本明細書において記述されている、本発明に係る方法を実行するソフトウエアインストラクションすなわちコードは、単一あるいは複数個の関連するメモリデバイス（ＲＯＭ、固定あるいはリムーバブル記憶装置）にストアされており、用いられる場合には、ＲＡＭにロードされてＣＰＵによって実行される。さらに、特に明示しない限り、本明細書においては、“ノード”、“スイッチ”、“ルータ”という術語が相互に交換可能であることにも留意されたい。
【００１０】
前述されているように、サービス品質（ＱｏＳ）保証をした最適ＩＰネットワーク設計は、研究上の既知の重要な問題である。実際、インターネットの商用利用及びビジネスのインターネットに対する依存の急増のために、ＩＰネットワークは非常に重要な使命を担うように変質してきており、今日のＩＰネットワークにおける“最大の努力”によるサービスという方針はもはや適切ではない。本発明は、例えばＶＰＮ等のその種のネットワークに対する帯域及び他のＱｏＳを提供するＩＰネットワークの設計に係る方法論を提供する。例えば、ネットワークの接続性及びトラフィックに係る要求が与えられると、本発明に係る設計手続きは、ネットワークトポロジー、及び、当該ネットワークにおける全てのルータが例えばPacketStarＩＰスイッチのようにＷＦＱ／ＬＱＤ機能を有している場合に前記要求を充足する、対応するリンク容量を生成する。同様のことが、ＦＩＦＯ／ＲＥＤ方式を用いる旧来のルータを用いた場合に係る第二の設計においてもなされる。その後、ネットワークコストの定量的な削減量の観点から、比較がなされる。この比較を実現するために、ＦＩＦＯスケジューリングをＲＥＤと共に用いた場合のＴＣＰスループット性能に係るモデルが使用される。上述の双方の場合において、開放最短経路第一（ＯＳＰＦ）ルーティングプロトコルによって課せられる制限が考慮される。さらに、本発明は、従来技術に係るルータネットワークを、旧来のルータをＷＦＱ／ＬＱＤルータに置換することによって性能保証を有するネットワークに転換するためのルータ配置問題も取り扱う。詳細に述べれば、本発明に係る方法は、ネットワークコストを最大限削減する目的でＷＦＱ／ＬＱＤルータが導入されるべき、ネットワーク内の戦略的位置を識別する。
【００１１】
図１は、本発明に従ったＩＰネットワーク設計システムの実施例を示すブロック図である。ＩＰネットワーク設計システム１０は、それ自体、複数個の、互いに相互に接続された機能プロセッサ、すなわち、ルーティングプロセッサ１２、ルーティングプロセッサ１２に機能的に接続されたワーストケース必要リンク容量プロセッサ１４、ワーストケース必要リンク容量プロセッサ１４に機能的に接続された最良リンク容量設計プロセッサ１６、ワーストケース必要リンク容量プロセッサ１４に機能的に接続されたネットワークトポロジー最適化プロセッサ１８、及び、最良リンク容量プロセッサ１６に機能的に接続されたルータ置換プロセッサ２０、を有している。図１に示された機能プロセッサ１２から２０は、それぞれ専用の処理デバイス（例えば、ＣＰＵ及び関連するメモリ）によってインプリメントされることも可能であり、また、集合的に単一あるいは複数個の処理デバイスによってインプリメントされることも可能である。すなわち、本発明に係るＩＰネットワーク設計システム１０は、単一の処理デバイスあるいは複数個の処理デバイスのいずれによってもインプリメント可能である。
【００１２】
ＩＰネットワーク設計システム１０への入力及び関連する方法論として、すなわち、ストアされたデータ信号の形態あるいは処理デバイスへの設計システムユーザによる入力で、バックボーンネットワークの初期トポロジーが、グラフＧ＝（Ｖ，Ｅ）の形態で入力される。ここで、Ｖは存在点（ＰＯＰすなわちルータが位置する点）に対応するノードの組であり、ＥはＰＯＰ間の直接接続を実現するリンクの組である。以下に説明されているように、初期ネットワークトポロジーは、ネットワークトポロジー最適化プロセッサ１８によって与えられることも可能である。さらに、システムへの入力として、マイレージベクトル→Ｌ＝［Ｌ1，Ｌ2，．．．，Ｌ|E|］が与えられる。ここで、Ｌlは、Ｅに属するリンクｌの実際の長さである。さらに、ポイント−ツー−ポイントＩＰトラフィック要求の組も設計システム１０へ供給される。ここで、各々のＩＰフロー要求ｉは、次式にて表わされるｆiによって与えられる。
ｆi＝（ｓi，ｔi，ａi，ｎi，ｄi，＿ｒi）
ここで、ｓi及びｔiは、それぞれＶ内のソース及びデスティネーションノードであり、ａiはトランスポートプロトコルタイプ（ＴＣＰあるいはＵＤＰ（データグラム使用プロトコル））、ｎiは当該フロー中におけるＴＣＰあるいはＵＤＰ接続の個数、ｄiは当該フローが双方向であると仮定した場合の最小スループット要求の総数、及び、＿ｒiはソース側顧客サイトからｓiへのアクセスリンク速度とデスティネーション側顧客からｔiへのアクセスリンク速度とのうちの最小値である。ここで、Ｆが全てのｆiを含む組とし、Ｆ1を、あるルーティングアルゴリズムＲに従ってリンク１を通過するようにルーティングされたＦの要素からなるサブセットとする。選択されたルーティングアルゴリズムＲは、上述された入力に基づいて、ルーティングプロセッサ１２（図１）によって実行される。ルーティングプロセッサ１２の出力（図１において参照符号Ａによって示されているもの）は、要求フロー及びネットワークトポロジーの関数としてのルーティング情報、すなわち、各々のリンク上に見出されるフロー（トラフィック）つまり各リンクを通過するｆiである。
【００１３】
本発明に係る設計システムは、標準的なＯＳＰＦプロトコルにおいて用いられているものと同様の最短経路ルーティングにフォーカスしている。最短経路は、Ｅにおける各々のリンクｌに係る与えられたリンク長ｌlに基づいて計算される。ここで、→ｌ＝［ｌ1，ｌ2，．．．，ｌ|E|］をこれらのリンク長より構成されるベクトルとする。タイブレーク方式が用いられ、あらゆるソースとデスティネーションとの間には単一のルートが存在する、ということを仮定する。リンクｌの容量をＣlとし、ネットワーク全体において用いられる基幹回線の大きさ（すなわち容量）が単一の値であるという仮定の下に、Ｃlが基幹回線容量（例えば、ＤＳ３、ＯＣ３等）によって表現されるとする。さらに、→Ｃ＝［Ｃ1，Ｃ2，．．．，Ｃ|E|］がリンク容量ベクトルを表わすとする。
【００１４】
一般に、ネットワーク設計システム１０及びその関連する方法は、なかんずく、以下の容量割り当て問題を取り扱う。  Ｆによって与えられるスループット要求が充足され、その一方で総ネットワークコストを最小化する、必要とされる容量ベクトル→Ｃを見出すこと。ここで、Ｅにおけるリンクのサブセットに対してゼロ容量を割り当てることにより、Ｇのトポロジーが、接続性を低減することによって実効的に変更されることが可能であり、その結果、要求のルーティングに影響を及ぼす。後に議論されるように、本発明に係るＩＰネットワーク設計方法は、トポロジー最適化も含んでいる。
【００１５】
図２に示されているように、本発明に係るシステムにおいて用いられる一般的な設計アルゴリズム２００の一実施例は、次のようなものである。まず、各々のリンクにおけるトラフィックミックスＦlが（ルーティングプロセッサ１２によって）、（最適化プロセッサ１８から与えられる）Ｇのサブグラフである初期ネットワークトポロジーＧs、ルーティングアルゴリズムＲ、リンク長ベクトル→ｌ、及びＩＰ要求の組Ｆに基づいて計算される（ステップ２０２）。次に、Ｆｌ内の帯域要求を充足するために必要とされる各々のリンクの容量が、（必要リンク容量プロセッサ１４及び１６によって）ネットワーク内のルータのタイプ、混雑シナリオに係る相異なった仮定、そしてある場合にはＴＣＰ要求のエンド−ツー−エンド遅延に基づいて計算される（ステップ２０４）。その後、本発明に係る設計システムは、（最適化プロセッサ１８によって）最終的なネットワーク設計が得られたか否かを決定する（ステップ２０６）。得られていない場合には、ステップ２０８において、ネットワークトポロジーに対して（最適化プロセッサ１８による）摂動が加えられ、ステップ２０２及び２０４に従って新たなネットワークコストが評価される。この設計反復は、最終的なネットワーク設計が得られるまで反復される。最終設計の結果は、（ステップ２１０において）、例えば当該設計システムのユーザに対して表示される情報の形態で出力される。この出力結果には、（１）ベクトル→Ｃ、（２）各々のトラフィックフローｆiに係るルート、及び、（３）対応するネットワークコスト、が含まれる。
【００１６】
本発明に係る方法の重要な機能の一つは、同種の場合、すなわち、従来技術に係るＦＩＦＯ／ＲＥＤルータあるいはＷＦＱ／ＬＱＤルータのいずれかしか含まないようなネットワークと、異種の場合、すなわち双方のルータタイプの混合の場合との双方が適応させられ得る、という点である。さらに、本発明に係る方法は、旧来のＦＩＦＯ／ＲＥＤルータネットワークへのＷＦＱ／ＬＱＤルータの最適配置を見出すためのコアエンジンとしても機能する。
【００１７】
本発明の主要な側面への参照を容易にする目的で、以下の記述はいくつかの節に分割される。節１．０においては、あらゆる与えられたＴＣＰ／ＵＤＰスループット要求を充足する目的で必要とされるリンク容量の本発明に従った推定が説明される。この際、ワーストケースリンク容量設計要求プロセッサ１４及び最良リンク容量設計プロセッサ１６が用いられる。ネットワークトポロジー最適化プロセッサ１８によって実行される本発明に従ったネットワークトポロジー最適化は、節２．０で記述される。節３．０においては、ルータ置換プロセッサ２０によって計算される本発明に従った異種ルータネットワークにおけるＷＦＱ／ＬＱＤルータの最適配置が説明される。ＩＰネットワーク設計事例が節４．０において与えられる。節５．０は、節１．０を参照して、ＦＩＦＯ／ＲＥＤの下でのスループット割り当ての説明が提供される。節６．０は、節３．０で説明された本発明に係るルータ配置実施例を参照して、ＮＰハードネスの説明がなされる。加えて、参照をより容易にする目的で、それぞれの節はさらに小項目に分割されている。
【００１８】
本発明に係る方法論の一つの注目点は、ＴＣＰがプライマリトランスポートプロトコルとして用いられるＩＰベースのＶＰＮに関して帯域保証を行なうことであるので、本発明は、ネットワーク内のリンクを介してルーティングされるＴＣＰ接続群の各々に係る与えられた要求の組を保証するために、当該リンクがどのくらいの容量を有する必要があるかを決定する。通常、接続の各群は相異なったＶＰＮに属していて、そのＶＰＮのポイント−ツー−ポイント要求のうちの一つを表わしている。この問題に対する回答は、特に当該ネットワークにおけるルータにおいて用いられるパケットスケジューリング及びバッファ管理戦略に依存する。今日のインターネットにおいて最もポピュラーなルータは、パケットドロップポリシーとしてＲＥＤを用いるＦＩＦＯスケジューリングを使用している。しかしながら、PacketStarＩＰスイッチなどの先進的な次世代ルータは、公平性を有してＶＰＮレベルで帯域保証を実現し、フロー（すなわち接続）レベルで分離特性を実現する目的で、最長キュードロップ（ＬＱＤ）ポリシーを用いるＷＦＱスケジューラを利用する。以下に明らかにされるように、ＲＥＤと組み合わせられた従来技術に係るＦＩＦＯは、ＬＱＤと組み合わせられたＷＦＱ（ＷＦＱ／ＬＱＤ）よりもより大きなリンク容量を有するように設計されていない限り、帯域保証を実現することは通常不可能である。
【００１９】
リンク容量プロセッサ１４、１６は、要求されるフローに係る要求、選択されたスケジューリング及びバッファ方式が与えられると、回線容量要求を計算する。以下に、ＦＩＦＯ／ＲＥＤ方式を用いることによって問題となる設計面での考慮事項が、リンク容量設計プロセッサ１４、１６によってインプリメントされるこれら設計問題を処理する方法論と共に議論される。その後、ＷＦＱ／ＬＱＤ方式に係る設計上の考慮事項が議論される。この際、それらに係る必要リンク容量は、プロセッサ１４あるいは１６のいずれかによって計算される。最後に、本発明に従ったリンク容量設計方法のいくつかの実施例が詳細に説明される。
【００２０】
１．１  ランダム早期検出法を用いるファーストイン・ファーストアウト（ＦＩＦＯ／ＲＥＤ）
容量ｃlFIFOを有するボトルネックリンクｌを介してルーティングされるＴＣＰ接続の組Ｆ1を考える。ＦＩＦＯ／ＲＥＤの下で各ＴＣＰソースが貪欲に混雑回避領域で動作するものと仮定すると、節５．０において説明されているように、S.Floyd,"パケット交換ネットワークにおける複数個の混雑したゲートウェイを有する接続",ACM COmputer Comm. Review, Vol.21, No.5, pp.30-47(1991年10月)及び、M.Mathies, J.Semke, J.Mahdavi, and T.Ott,"ＴＣＰ混雑回避アルゴリズムの巨視的振る舞い",ACM Computer Comm. Review, Vol.27, No.3, pp67-82(1997年7月)による結果に基づいて、Ｆlに属するあらゆる与えられた接続ｉに関して、リンク容量の共有分が、
【数５】
0003654499.tif 000002
によって与えられる。ここで、τi及びｈiは、それぞれ、接続ｉの経路におけるラウンドトリップ遅延（ＲＴＤ）及び混雑したリンクの個数である。混雑したリンクとは、そのキューにおいてパケットロスが生ずるほどの高い負荷を有するリンクを表わしており、それに対して混雑していないリンクとは、パケットロスが発生しないリンクを表わしている。言い換えれば、リンク容量は、競合するＴＣＰ接続の間で、式（１）によって与えられる重みに比例して共有される。この重みは、ラウンドトリップ時間τ及びｈの２乗根との積の逆数である。ここで、以下の、ＦＩＦＯ／ＲＥＤとＷＦＱ／ＬＱＤとの間の基本的な差異に留意されたい。双方の場合とも、あらゆる接続のリンク共有は、その重みに比例する。ＷＦＱ／ＬＱＤの場合には、以下に説明されているように、接続に係る重みはネットワークオペレータの制御下にあり、任意に設定されうる。しかしながら、ＦＩＦＯ／ＲＥＤにおいては、重みは接続経路の特徴、つまりτ及びｈによって決定付けられており、ほとんど制御不能である。
【００２１】
与えられたＶＰＮにおける各々のポイント−ツー−ポイント要求ｉは、現実には複数個のＴＣＰ接続に対応しており、それら各々が同一の重みｗiを有している。なぜなら、それら全体が、τi及びｈiによって特徴付けられる同一の最短経路を実現しているからである。ここで、ｎiを、Ｆlに属する要求ｉを構成するＴＣＰ接続の個数とする。式（１）より、要求ｉによって獲得されるリンク共有は、
【数６】
0003654499.tif 000003
によって与えられる。与えられた要求ｉ内のＴＣＰ接続の個数ｎiが実際の要求の値ｄiに比例すると仮定すると、式（２）は、
【数７】
0003654499.tif 000004
【数８】
0003654499.tif 000005
となる。
【００２２】
要求を充足するリンク容量ｃlFIFOを有するためには、∀ｉ∈Ｆlなるｉに関して、ｒli≧ｄiが必要である。このことは、全ての要求を充足する最小リンク容量が
【数９】
0003654499.tif 000006
によって与えられることを意味している。この際、ｗi（ｉ∈Ｆl）は、式（４）によって与えられる。リンク容量ｃlFIFOは、明らかに全ての要求の総和以上である。
【数１０】
0003654499.tif 000007
さらに、ｉ*を式（５）において最大値を取る要求とするとき、式（３）及び式（５）を組み合わせることによって、
【数１１】
0003654499.tif 000008
を得る。この際、ｒli*＝ｄi*であり、ｒli≧ｄi（∀ｉ∈Ｆl）である。言い換えれば、ｉ*は、その必要量が正確に割り当てられた要求であり、他の全ての要求に対してはその必要とされる以上の帯域が割り当てられる。
【００２３】
式（５）に従って必要とされるリンク容量を計算するために用いられるパラメータは、ｄi、τi及びｈi（ｉ∈Ｆl）である。要求ｄiは与えられ、遅延τi（伝播遅延）の固定部分は最短経路から決定されて広い範囲にわたって主要部分であることが期待されるため（キューに係る遅延成分の平均を加えることも可能である）、第三のパラメータｈiの値のみが自明ではない。
【００２４】
ｈiの決定の問題を取り扱うために、以下で、いくつかの定義を導入する。-ｈiを、接続ｉの最短経路に対応するホップの数とする。明らかに、混雑したホップの数ｈiは、ｈi≦-ｈiを（∀ｉ∈Ｆl）満たす。ここで、Ｉ＝［Ｉ1、I2、．．．、Ｉ|F|］を、ネットワーク内の全てのリンクの混雑状況を表わすベクトルとする。この際、Ｉjは、リンクｊのインジケータであり、リンクｊが混雑している場合には１、それ以外の場合は０である。さらに、Ｈ＝［ｈ1、ｈ2、．．．、ｈ|F|］を、各々のエンド−ツー−エンド要求の経路における混雑したリンクの個数よりなるベクトルとする。すなわち、
【数１２】
0003654499.tif 000009
であり、ｐ（ｉ）は、要求ｉが横断するリンクシーケンス（経路）を表わしている。また、Ｈl＝［ｈi1、ｈi2、．．．、ｈ|Fl|］を、要求ｉ（ｉ∈Ｆl）に対するｈiよりなるベクトルとする。
【００２５】
ベクトルＩ及びＨは、各々、＿Ｉ＝｛０、１｝|E|及び＿Ｈ＝｛０、１、．．．-ｈi｝×．．．×｛０、１、．．．、-ｈ|F|｝よりなる組に属する値を取る。ここで、ｇを前述されているように定義された＿Ｉと＿Ｈとの間のマッピングとする。
【数１３】
0003654499.tif 000010
組_Ｉは、ｇによって、＿Ｈfとして表わされる_Ｈのサブセットにマッピングされ、この_Ｈfは、
_Ｈf＝｛Ｈ∈_Ｈ、∃Ｉ∈＿Ｉ s.t. Ｈ＝ｇ（Ｉ）｝
のように表現される、＿Ｈに属する利用可能な要素よりなる組である。言い換えれば、Ｈ∈＿Ｈは、必ずしも全てが利用可能ではない。
【００２６】
｛Ｈ｝をＨl（ｌ∈Ｅ）の組とする。要求ｉに対応するｈiの要素は、ｌ∈ｐ（ｉ）を満たす全てのベクトルＨl、すなわち、接続ｉの経路における全てのリンク、に現われる。同一の要求に係る全ての要素が同一である場合には、｛Ｈ｝はコンシステントであるという。｛Ｈ｝がコンシステントである場合には、ｈiに係るベクトルＨ（ここで、ｈiは全てのＨl（ｌ∈ｐ（ｉ））における要求ｉの共通要素である）は、｛Ｈ｝の共通ベクトルであると呼称される。さらに、｛Ｈ｝は、（ｉ）それがコンシステントであって、かつ、（ｉｉ）その共通ベクトルが利用可能である場合に、利用可能であるといわれる。
【００２７】
式（５）におけるリンク容量の計算は、要求ｉがリンクｌにおけるシェアｒliを（その経路に沿った他のリンクにおけるシェアがｒliより小さければ）そのシェアを達成しない、という、ネットワーク全体のシナリオにおける複数個のボトルネックの効果を考慮していない。それゆえ、ｒliと要求ｉの経路における他のリンクの最小シェアとの差異（これは、ｄiより大きい。なぜなら、ｐ（ｉ）内の全てのリンクにおいてｒli≧ｄiであるからである。）が、その要求に影響を与えることなく、ｃlFIFOから差し引かれることが可能である。そうでない場合には、この余剰容量は、リンクｌを通過する、その必要容量が既に満たされた貪欲な要求によって取り込まれる。この意味では、式（５）におけるｃlFIFOを、その必要とされるリンク容量の上限とみなすことができ、それを-ｃlFIFOと書き表わすことにすると、
【数１４】
0003654499.tif 000011
のように書き直すことができる。ここで、重みｗjの、従って、-ｃlFIFOの、Ｈlの値に関する依存性を強調したい。さらに、前述された複数ボトルネック効果を考慮することによって、必要とされるリンク容量の下限＿ｃlFIFOが以下のように求められる。-ｃlFIFOに基づいて、要求ｉのシェアが、
【数１５】
0003654499.tif 000012
のように得られる。そして、経路に沿った最小シェアが
【数１６】
0003654499.tif 000013
のように計算される。ここで、＿ｒi≧ｄiは、例えばネットワークへのＶＰＮのアクセスリンク速度に起因する、発生しうるあらゆる制限を表わす適切な値にセットされる。式（７）の最小値がｒl*i（Ｈl*）に対応する場合には、リンクｌ*が要求ｉに関するボトルネックリンクである。最終的に、＿ｃlFIFOが
【数１７】
0003654499.tif 000014
のように求められる。これは、Ｈlの関数であるだけではなく、｛Ｈ｝のサブセットであるＨl'（∀ｌ’∈ｐ（ｉ））の関数である。＿ｃlFIFOが下限である理由は、あらゆる与えられた可能な｛Ｈ｝に関して、ある要求のボトルネックをシフトすることにつながる、ある種の要求アイドリングシナリオが存在するからである。このボトルネックシフトによって、アクティブな要求からの必要事項を充足させるために＿ｃlFIFOより大きな容量が必要とされる。
【００２８】
これまで、ネットワーク内の各々のリンクｌに係るＨlの関数として、容量の上限及び下限である-ｃlFIFO及び＿ｃlFIFOについて議論された。現実のＨlがどのようなものであるかがわかっていないため、以下の境界が決定される。
【数１８】
0003654499.tif 000015
【数１９】
0003654499.tif 000016
ここで、各々の利用可能なＨ∈＿Ｈfに関して、対応するＨlを形成し、-ｃlFIFO及び＿ｃlFIFO（｛Ｈ｝）を計算する。必要とされる容量ｃlFIFOの正確な値は＿ｃlFIFO（Ｈmin）≦ｃlFIFO≦-ｃlFIFO（Ｈmax）を満たす。よって、これらの境界は、Ｈ∈＿Ｈfの実際の値とは独立にリンク容量の上限及び下限を与える。これらの境界は計算可能であるが、現実的には、すなわち、より計算を容易にする目的で、境界が次のように与えられる。
【数２０】
0003654499.tif 000017
【数２１】
0003654499.tif 000018
ここで、最大及び最小は、可能性にかかわらずＨの全ての値に関して考慮する。この際、Ｈlworstが、Ｈlを式（６）における各々のｉに関してｈi＝-ｈiでありかつｊ≠ｉに対してｈj＝１（各々の要求ｉ∈Ｆlが少なくともその経路中の混雑したリンクとしてリンクｌを有している）であるように選択することによって得られることは明らかである。同様に、Ｈlbestが、Ｈlを式（６）における各々のｉに関してｈi＝１でありかつｊ≠ｉに対してｈj＝-ｈjであるように選択することによって得られる。
【００２９】
しかしながら、定義によって、以下の不等式が存在する。
【数２２】
0003654499.tif 000019
ここで、-ｃlFIFO（Ｈmin）は、式（９）において最大の代わりに最小を取ることによって規定される。それゆえ、-ｃlFIFO（Ｈworst）は上限として用いられる。-ｃlFIFO（Ｈbest）は下限の良好な候補である。なぜなら、-ｃlFIFO（Ｈbest）及び_ｃlFIFO（Ｈmin）は双方とも-ｃlFIFO（Ｈmin）より小さく、節５．０で示されているケーススタディにおいては、-ｃlFIFO（Ｈbest）≦＿ｃlFIFO（｛Ｈ｝）であることが、ＨがＨhop及びＨoneに等しいこと（それぞれ、ｈi＝-ｈi、及びｈi＝１、ｉ＝１，２，．．．，｜Ｆ｜である）に対応する｛Ｈ｝の二つの代表的な値に関して示されるからである。Ｈoneは、各々の要求が単一の混雑したリンクをその経路上に有していることに対応し、可能ではない。Ｈhopは可能であって、全ての要求がアクティブかつ貪欲であり、各々のリンクが少なくとも一つの１ｈｏｐ要求を担っている場合に対応する。これらの方法論に係る実施例は、以下、節１．４において説明される。
【００３０】
次に、以下の議論においては、本発明に係るシステム１０を用いる設計者が、スケジューリング／バッファリング方式としてＷＦＱ／ＬＱＤを選択したと仮定する。PacketStarＩＰスイッチは、３層階層構造ＷＦＱスケジューラを用いることによって出力リンク毎に６４０００フローキューをサポートすることが可能であることが知られている（例えば、V.P.Kumar, T.V.Lakshman, and D.Stiliadisによる“ベストエフォート方式を越えて。明日のインターネットにおける差動的サービスに係るルータアーキテクチャ”という表題の論文(IEEE Comm. Magazine, Vol.36, No.5, pp.152-164(1998.5))を参照）。スケジューラ階層の最上位おいては、相異なったＶＰＮ間でリンク容量が分割されており、各々のＶＰＮ内ではそれがアプリケーション分類（例えば、ＦＴＰ様のＴＣＰフロー、Ｔｅｌｎｅｔ様のＴＣＰフロー、ＵＤＰフロー等）に基づいて分割され、最後に、各々のアプリケーション分類の帯域が、さらに、その分類に属するフロー間で分割される（各々の分類内でのフローレベルには通常等しい重みが与えられるが、異なるようにすることも可能である）。
【００３１】
バッファリソースを効率的に使用する目的で、PacketStarＩＰスイッチは、全てのフロー間での共有バッファプールのソフト分割を利用する。それぞれのフローは、共有バッファに適切なパケットバックログを維持することが可能である場合には、その重みに対応するリンク容量（リンクシェア）を獲得することが可能である。言い換えれば、ＷＦＱスケジューラは、各々のフローに対してパケット伝送目的で当該リンクにアクセスする公平な機会を提供するが、このことは、当該フローが共有バッファへの不適切なアクセス制御のために適切なパケットバックログを維持できない場合には、リンク容量の公平な共有を必ずしも意味しない。この問題は、例えば、ＴＣＰのようなパケットロスに敏感なトラフィックが、未制御ＵＤＰなどのパケットロスには敏感でないトラフィックと競合している場合、あるいは、相異なったラウンドトリップ遅延（ＲＴＤ）を有するＴＣＰ接続がリンク容量に関して競合している場合、に発生しうる。最初の状況の場合には、ＴＣＰスループットがパケットロスに敏感であるために（ＴＣＰソースは、パケットロスが検出されると、そのウィンドウを小さくすることによってレートを低減する）、パケットロス状況に応じてそのレートを適応させないアプリケーション（非適応ＵＤＰソースあるいは標準的なＴＣＰの振る舞いに従わない過激なＴＣＰソースのいずれかである）は、共有バッファプールから不公平なシェアを獲得してしまうことが可能であるからである。相異なったＲＴＤを有するＴＣＰ接続という第二のシナリオは公知の問題であり、例えば、S.Floyd and V.Jacobsonによる“パケット交換ゲートウェイにおけるトラフィックフェーズ効果”という表題の論文(Internetworking。Research and Experience, Vol.3, No.3, pp.115-156(1992.9))T.V.Lakshman and U.Madhowによる“ＴＣＰ／ＩＰを用いたウィンドウベースフロー制御の性能解析。広帯域遅延積及びランダムロスの効果”という表題の論文(IFIP Trans. High Perf. Networking, North Holland, pp.135-150(1994))等の文献を参照されたい。大きなＲＴＤを有するＴＣＰ接続への不公平さの理由は、混雑回避フェーズにおけるＴＣＰのＲＴＤ毎の一定ウィンドウ増大の結果、より小さなＲＴＤを有する接続がそのウィンドウをより速く増大させることが可能になり、それらがその経路におけるあるルータでバックログを作成する際に、そのバックログがより小さなＲＴＤを有する接続に関してより速く成長するからである（なぜなら、バックログは各々のＲＴＤ毎に１パケットずつ成長するから）。
【００３２】
完全バッファ共有に起因するこれらの問題を解決するため、PacketStarＩＰスイッチは、以下のバッファ管理戦略を利用する。各々のフローには、常に保証されている公称バッファ空間が割り当てられ、バッファ空間が利用可能な場合には、フローバッファの占有がその公称割り当てを超過してなされることが許可される。この公称割り当ては、その接続の帯域遅延積に理想的に比例するように設定されるが、遅延情報が欠落している場合には、ＷＦＱスケジューラ内の当該接続に係る重みに比例するようにセットされる。到着するパケットのためのスペースがバッファ内に確保できない場合には、バッファ内に既に存在しているパケットが押し出される。パケットが破棄されるフローキューは、その公称割り当てを最も超過しているものである（公称割り当てが等しい場合には、このことは最長キューから落とすということに等しい）。前述されているように、小さいＲＴＤを有するＴＣＰフローはその公称割り当て以上の最長キューを有する可能性が高いため、ＬＱＤポリシーは大きなＲＴＤを有する接続に対する不公平性を緩和する。加えて、非適応ソースは長いキューを有する可能性が高く、従ってＬＱＤポリシーによってペナルティを課せられる。
【００３３】
よって、ＷＦＱによって実現されるフロー分離は、ＬＱＤによって実現される保護及び公平性と組み合わせられて、各々のフロー、フロー分類、あるいはＶＰＮのエンド−ツー−エンド要求が、その重みに比例するリンク容量のシェアを獲得することを可能にする（例えば、B.Suter, T.V.Lakshman, D.Stiliadis, and A.K.Choudhuryによる“フロー毎キューイングを行なうＴＣＰのサポートに係る設計考慮事項”という表題の論文(Proc. IEEE Infocom, pp.299-306, San Francisco(1998.3))を参照）。
【００３４】
結果として、スケジューラは重み付けを行ない、公称バッファ割り当てが、与えられたリンクｌにおいて、ポイント−ツー−ポイントＶＰＮ要求ｄiの組を充足するために必要とされるリンク容量が単に要求の総和に等しくなるように、すなわち
【数２３】
0003654499.tif 000020
であるように設定される。ここで、Ｆlはリンクｌを介してルーティングされる全ＶＰＮ要求よりなる組である。しかしながら、ＷＦＱ／ＬＱＤ機能を有するルータと比較して、ルータがＦＩＦＯ／ＲＥＤのみをサポートする場合には、同一の要求を満たすためにより大きな容量が必要とされる。
【００３５】
１．３  ＴＣＰとＵＤＰの双方による容量要求
これまでは、ＴＣＰトラフィックのみが必要とされるリンク容量を計算するために考慮されてきており、ＦＩＦＯ／ＲＥＤを利用する場合に式（１１）及び（１２）、ＷＦＱ／ＬＱＤの場合に式（１３）によってそれぞれ境界が与えられてきた。フロー毎キューイングによって分離が実現されるため、ＷＦＱ／ＬＱＤの場合に関する総必要容量を求めるためには、ＵＤＰ要求を追加すればよい。ここでは、過激なＵＤＰトラフィックがその要求を越える可能性があまり無いと仮定して、ＦＩＦＯ／ＲＥＤの場合にも同一の手法を適用する。よって、ＷＦＱ／ＬＱＤの場合の必要リンク量は
【数２４】
0003654499.tif 000021
によって与えられ、ＦＩＦＯ／ＲＥＤの場合には、その上限が
【数２５】
0003654499.tif 000022
その下限が
【数２６】
0003654499.tif 000023
によって与えられる。さらに、ＨhopとＨoneの二つの特別な場合には、上限及び下限はそれぞれ
【数２７】
0003654499.tif 000024
【数２８】
0003654499.tif 000025
【数２９】
0003654499.tif 000026
【数３０】
0003654499.tif 000027
によって与えられる。ここで、ｄiUDPは、要求ｉに係るＵＤＰスループット要求事項を表わしており、シーリング関数┌．┐は、リンク容量が離散的（トランク回線単位）であることを説明するために導入された。
【００３６】
１．４  リンク容量計算実施例
以上に導出されたような式が与えられたので、以下は、本発明に係る方法の種々の実施例を、本発明に係るネットワーク設計システムのユーザによって選択された特定の設計基準に関連する必要リンク容量の計算に関連して示す。以下に記述されているように、以下の方法は、ワーストケースリンク容量設計要求プロセッサ１４及び／あるいは最良リンク容量設計プロセッサ１６（図１）によって実行される。
【００３７】
図３は、本発明に従って、ＦＩＦＯ／ＲＥＤベースのワーストケース必要リンク容量を計算する方法３００である。ここで、ｃという文字はＴＣＰトラフィックのみを考慮するリンク容量を表わす一方、ＣはＴＣＰとＵＤＰ双方のトラフィックを考慮するリンク容量を表わす。従って、式における項からも明らかなように、第一付加項はＴＤＰトラフィックに係る必要リンク容量であり、第二付加項はＵＤＰトラフィックに係る必要リンク容量である。さらに、この種の計算は、ルーティングプロセッサ１２及びユーザからの入力に基づいて、ワーストケース必要リンク容量プロセッサ１４（図１）によって実行される。従って、この設計方法は、システム１０のユーザに、入力された特定の使用に基づいて、必要とされるリンク容量の計算をリンク毎に提供する。
【００３８】
ステップ３０２においては、プロセッサ１４は、ルーティングプロセッサ及びユーザから入力パラメータを受け取る。プロセッサ１２からの入力には、接続ｉに係るポイント−ツー−ポイントＶＰＮ要求の組であるｄi及びラウンドトリップ遅延τiが含まれる。もちろん、これらの入力は、最初にユーザによって規定されたものである。加えて、ユーザは、スケジューリング／バッファリング方式（この例ではＦＩＦＯ／ＲＥＤである）、及び混雑オプションＨO（例えば、Ｈworst、Ｈhop、及びＨone）を規定する。既に説明されているように、混雑オプションは、あるｈiの値を与えられた設計基準に割り当てるものである。ｈiは、接続ｉの経路における混雑したリンクの数を表わす。節１．２で示されたように、Ｈworstは、式（６）における各々のｉに対して、ｈi＝-ｈiかつｊ≠ｉに関してｈj＝１という条件（Ｆlに属する各々の要求ｉが、少なくとも、その経路内に混雑したリンクとしてリンクｌを有する）の下にＨlを選択することによって得られる。Ｈworstは式（１５）において規定された上限であり、（最良リンク容量プロセッサ１６によって計算された）下限Ｈbestと共に、Ｈの全ての値に適用される。さらに、ステップ３０３において、Ｈhop及びＨoneが規定される。これらは、それぞれｈi＝-ｈi及びｈi＝１（ｉ＝１，２，．．．，｜Ｆ｜）に対応する上限Ｈworstの特別な値である。Ｈoneは、各々の要求がその経路内に単一の混雑したリンクを有する場合であり、可能ではない。Ｈhopは可能であって、全ての要求がアクティブかつ貪欲であり、各々のリンクが少なくとも一つの１ホップ要求を担っている場合に対応する。本発明に従って、ユーザはオプションＨOのみを規定すればよいことに留意されたい。なぜなら、それらに対応するｈiの値はプロセッサ１４に係るメモリ内にストアされているからである。
【００３９】
ステップ３０４においては、ユーザによって選択されたオプションに依存して、ワーストケース必要リンク容量が計算される。すなわち、現在のネットワークトポロジーにおける各々のリンクのリンク容量が、要求、遅延、スケジューリング／バッファリング方式及び選択された混雑オプションに基づいて計算される。ここで、図３のステップ３０４において示されたＨworst、Ｈhop及びＨoneに係る式は、既に説明された式（１５）、（１７）、（１９）にそれぞれ等しく、式（６）の右辺がシーリング関数の第一項として挿入されたものである。最後に、現在のトポロジーの各々のリンクに対する必要リンク容量（図１において参照符号Ｂにて示されていたもの）が、例えばプロセッサ１４に係るディスプレイを介してユーザに出力される。
【００４０】
図４は、本発明に従ったＦＩＦＯ／ＲＥＤベースの最良リンク容量を計算する方法４００を示した流れ図である。それぞれの式における項から明らかなように、第一付加項はＴＤＰトラフィックに係る必要リンク容量であり、第二付加項はＵＤＰトラフィックに係る必要リンク容量である。さらに、これらの計算は、ルーティングプロセッサ１２、ユーザ及びワーストケース必要リンク容量プロセッサ１４からの入力に基づいて、最良リンク容量設計プロセッサ１４によって実行される（なぜなら、シェアｒｉが-ｃlFIFOの関数だからである）。従って、この設計方法により、システム１０のユーザが、入力された特定の使用に基づいて、必要とされるリンク容量をリンク毎に計算することが可能になる。
【００４１】
まず、ステップ４０２において、プロセッサ１６はプロセッサ１４と同様の入力、すなわち、ネットワークトポロジー、ソース−デスティネーション要求、ラウンドトリップ遅延及びユーザによってなされた混雑選択シナリオを受信する。さらに、プロセッサ１４によって計算された必要リンク容量もプロセッサ１６に供給される。ユーザは、本発明に従って、オプションＨO（例えば、Ｈbest、Ｈhop、Ｈone）のみを規定する必要がある、ということに留意されたい。なぜなら、それらに対応するｈiの値はプロセッサ１６に係るメモリ内にストアされているからである。前述されているように、Ｈbestは、式（６）における各々のｉに対して、ｈi＝１かつｊ≠ｉに関してｈj＝-ｈjという条件の下にＨlを選択することによって得られる。さらに、Ｈhop及びＨoneが、それぞれｈi＝-ｈi及びｈi＝１（ｉ＝１，２，．．．，｜Ｆ｜）に対応するものとして、ステップ４０４で規定される。
【００４２】
次に、ユーザによって選択されたオプションに基づいて、必要とされる最良リンク容量が計算される。すなわち、現在のネットワークトポロジーにおける各々のリンクのリンク容量が、要求、遅延、スケジューリング／バッファリング方式及び選択された混雑オプションに基づいて計算される。図４のステップ４０４において示されたＨbest、Ｈhop、Ｈoneに係る式は、前述された式（１６）、（１８）、（２０）と同一のものであり、式（６）の右辺が式（１６）のシーリング関数の第一項として挿入され、式（８）の右辺が式（１８）、（２０）のシーリング関数の第一項として挿入されたものであることに留意されたい。最後に、現在のトポロジーにおける各々のリンクに係る必要リンク容量（図１において参照符号Ｄによって示されていたもの）が、例えばディスプレイを介してユーザに出力される。単一の入力デバイス及び単一の出力デバイスが、本発明に従ったシステム１０に係る全てのユーザ選択可能入力及び出力に関して用いられることに留意されたい。従って、プロセッサ１６の出力をプロセッサ１４の出力と比較して以下の点に注目すべきである。ネットワークトポロジーは変化していない。しかしながら、あるリンクの容量は、ネットワーク全体での複数ボトルネック効果を考慮して、低減されている場合がある。
【００４３】
図５は、本発明に従った、ＷＦＱ／ＬＱＤベースのリンク容量ＣlWFQを計算する方法５００を示している。この実施例においては、ユーザがＷＦＱ／ＬＱＤスケジューリング／バッファリング方式を選択することが仮定されている。このため、限界及び混雑オプションに基づいた計算は不要であり、結果として、各々のリンクｌに関してＴＣＰ／ＵＤＰトラフィックに係るＶＰＮ要求ｄiのみが、必要リンク容量を計算するための入力として必要とされる（ステップ５０２）、ということに留意されたい。ＷＦＱ／ＬＱＤ方式においては上限及び下限を計算する必要がないため、プロセッサ１４あるいはプロセッサ１６のいずれかが必要リンク容量を計算するために用いられるだけであることにも留意されたい。よって、ステップ５０４において、スケジューラは重み付けを行ない、与えられたリンクｌに対する公称バッファ割り当てが、ポイント−ツー−ポイントＶＰＮ要求ｄiの組を満たすために必要とされるリンク容量が、ステップ５０６に式で示されているように、単に要求の総和に等しいものであるように設定される。ここで、Ｆlは、リンクｌを介してルーティングされる全てのＶＰＮ要求の組である（すなわち、それらＶＰＮ要求は、その最短経路にリンクｌを有している）。ステップ５０８においては、リンク容量がユーザに出力される（例えばディスプレイを介して）。
【００４４】
２．０  ネットワークトポロジー最適化
考慮している容量割り当て問題に関しては、ゼロ容量を割り当てることによって、元のネットワークトポロジーＧ内におけるいくつかのリンクを除去するという柔軟性がある。このリンク除去に係る動機付けは、ネットワーク全体の費用と低減するためにいくつかの使用頻度の低いネットワークファシリティを排除する、ということである。本発明に係る設計プロセス全体を通じて、ネットワーク費用は以下の関数に基づいて計算される。
【数３１】
0003654499.tif 000028
ここで、Ｍ（．，．）及びＴ（．）は、それぞれマイレージ及び終端費用関数である。この費用関数は、簡単のために選択されたものであって本発明の理解を容易にするためのものであることに留意されたい。費用関数の他の一般的な形式も、本発明に容易に組み込まれうる。ネットワークトポロジー最適化プロセッサ１８がネットワーク費用を計算することが望ましい。しかしながら、プロセッサ１４あるいは１６が、このことを行なってもよい。
【００４５】
以下のサブセクションにおいては、ネットワークトポロジー最適化に係る二つの実施例とその変形例が考察される。それらは、リンク増強アプローチとリンクデロードアプローチである。ネットワークトポロジー最適化のプロセスは、ネットワークトポロジー最適化プロセッサ１８によっても実行される。さらに、システム１０を用いるためにルーティングプロセッサ１２へ最初に与えられるネットワークトポロジーは、ネットワークトポロジー最適化プロセッサ１８によって与えられるか、あるいはシステム１０のユーザによって与えられるかのいずれかである。
【００４６】
２．１  増強最適化
図６から９には、本発明に従った増強アプローチを用いるネットワークトポロジー最適化方法６００が示されている。この増強アプローチにおいては、Ｇの適切なサブグラフＧsから開始して、それを付加リンク及び／あるいは容量によって、全ての要求がルーティングされるまで増強する。初期には、Ｇのエッジが選択されてサブグラフＧsが構成される。Ｇｓを構成する方法は以下の通りである。まず、ステップ６０２において、全てのエンド−ツー−エンド要求フローｉが二つの組、すなわち、その最小スループット要求ｄiに基づいて、キーパーとストラグラーとに分割される。ある実施例においては、基準は、トランク回線帯域の少なくとも一ユニットを必要とする要求がキーパーであり、その残り、すなわち、端数のトランクサイズの要求を有するものがストラグラーになる。ステップ６０４においては、キーパー要求が、選択されたルーティングアルゴリズム、例えば最短経路ルーティング（これは、ＯＳＰＦルーティングプロトコルによって用いられているアルゴリズムである）、に従って、完全なグラフＧ上でルーティングされる。キーパーに関するルーティングが計算されると、キーパーの要求を実現するためにそれぞれのルートに沿った必要とされる容量がトランク回線の大きさの単位で提供される。トランク回線の大きさは本質的に離散的であるため、キーパーのルートに沿って余分な（スペアとしての）容量が存在することになる。キーパー要求全てをルーティングした後、Ｇ内のリンクのうち、キーパーの要求を伝達するために用いられたリンクが初期状態のサブグラフＧsを構成する（ステップ６０６）。この時点では、Ｇｓは、ストラグラーのうちのいくつかのソースとデスティネーションとの接続を実現していない場合がある。よって、本発明は、設計者に、全てのソース−デスティネーション間の接続を実現するストラグラー接続増強オプションを提供する（ステップ６０８）。このオプションが選択された場合には、ステップ６１０において、全てのストラグラーがワーキングリストＬ１に配置される。リストが空ではない場合には（ステップ６１２）、ステップ６１４において一つのストラグラーがリストから選択される。選択されたストラグラーはｆiとして示される。次に、ステップ６１６において、ｆiのソースノードとデスティネーションノードとの間の経路がＧs内に存在するか否かが、リンクに係る容量制限を考慮することなく決定される。そのような経路が存在する場合には、ｆiはワーキングリストＬ１から削除される（ステップ６１８）。存在しない場合には、ステップ６２０において、ストラグラーｆiはキーパーに変換され、そのソースノードからデスティネーションノードへＧ内の最短経路に沿ってルーティングされ、その際にその経路に沿って必要な容量が追加される。その経路沿いの、現在のＧsに含まれていないリンクは、Ｇsに追加されて新たなＧsが構成される。その後、ステップ６１８において、ｆiがワーキングリストＬ１から除去される。
【００４７】
ｆiがＬ１から除去された後、他のストラグラーが残存しているか否かを見るためにリストがチェックされる。存在する場合には、ステップ６１４から６２０が反復される。存在しない場合には、処理はステップ６２２へ進む。ステップ６０８において、ストラグラー接続を選択するオプションが設計システム１０のユーザに与えられたことを想起されたい。ストラグラー接続オプションが選択されていない、あるいはストラグラー選択オプションが選択されてその処理が完了した場合には、以下の手続きが実行される。ステップ６２２において、全ストラグラーがワーキングリストＬ２に配置される。ストラグラーリストは、さらにストラグラーが残存しているか否かを見る目的で反復してチェックされる（ステップ６２４）。ステップ６２６においては、あるストラグラーｆjがリストＬ２から選択される。ステップ６２８においては、ｆjがＧs内のソースノードとデスティネーションノードとの間の最短経路に沿ってルーティングされる。ステップ６３０においては、この最短経路に沿ってｆjを満たすのに適切な接続とその容量が存在するか否かが決定される。存在する場合には、ｆｊはリストＬ２から除去され（ステップ６３２）、リスト内にストラグラーが残存しているか否かを見る目的でリストがチェックされて（ステップ６２４）プロセスが反復される。しかしながら、最短経路に沿ってｆjを満たすのに適切な接続とその容量が存在しない場合には、設計者は以下の二つの別の増大方法から選択することになる（ステップ６３６）。一つの方法は、容量のみを増大するアプローチであり、他方は、容量と接続とを増大するアプローチである。
【００４８】
容量のみを増大する方法においては、これ以降、初期Ｇsが不変に保たれる。ストラグラーがＧｓにおいては満たされない場合には、付加容量がそのルートに沿って追加される（ステップ６３８）。この方法の一つの利点は計算効率である。なぜなら、Ｇsが初期フェーズ以降不変であるからである。このため、ストラグラーのルートはＧsにおける容量増大によって影響を受けない。このようなことは、ストラグラーの一部がルーティングされた後に接続増大がなされるような他の方法においては起こらない。ステップ６３８の後に、ｆｊはリストから除去され（ステップ６３２）、この処理はＬ２内の残存しているストラグラーに関して反復される。
【００４９】
本発明に係る別の増大戦略は、ストラグラーがスペア容量あるいはＧs内の接続の欠如のためにルーティングされ得ない場合（後者は、接続完了手続きオプション（ステップ６１０から６２０）がＧsに関して実行された場合には発生しない）には、Ｇsのスペア容量と接続性の双方を強化する目的で、付加ストラグラーがキーパーに変換される。ストラグラー−キーパー変換は、以下の二つのアプローチのうちの一つを介して実現される。設計者は、その方法を選択することができる（ステップ６４０）。
【００５０】
第一の方法は、スレッショルド制御ストラグラー変換と呼称される。この方法は、キーパーとストラグラーの要求値の間の閾値を低下させることによって、あるストラグラー要求をキーパー要求に変換するものである（ステップ６４２）。この閾値は、初期には単位トランク回線サイズに設定される。その後、新たに変換されたキーパーが、ステップ６４４において、全トポロジーＧ内の最短経路に従ってルーティングされる。リンクは、必要とされる容量が割り当てられて追加される。新たに活性化されたリンクは、現時点のＧsを増強して新たなＧsを構成するために用いられる。閾値が低下させられた場合には新たな容量や接続が追加されるが、新たに追加されたリソースは、ルーティングされることになっているストラグラーの要求を直接的に取り扱うものではないことに留意されたい。さらに、Ｇｓの接続が変化するため、以前にルーティングされたストラグラーの最短経路が、新たなＧｓにおいて変更される可能性がある（キーパーに関してはそのようなことは無い。なぜなら、キーパーはＧに関してルーティングされるからである。）。結果として、既にルーティングされたストラグラーの全てのルーティングをやり直すことが望ましく（ステップ６４８）、ステップ６２２へ戻ってストラグラーの再ルーティングを行なう。この閾値低下、ストラグラー−キーパー変換、及びＧs増大プロセスは、全てのストラグラーがＧs上でルーティングされうるまで反復される（ステップ６２４）。その後、結果として得られるＧsは、最終的なネットワークトポロジーとなる。接続完了オプション（ステップ６０８）が初期Ｇsを構成するために実行される理由は明らかである。すなわち、このオプションがない場合には、Ｇs中に接続がない小さなストラグラー要求が存在すると、このストラグラー要求がキーパーに変換されるまで閾値が低下させられ続けることになるからである。これは、容量設定の観点からは非常に無駄であり、計算効率も悪い。前者は、ネットワーク中の間違った位置に不要なスペア容量を導入することになり、後者はストラグラーが複数回、すなわち、閾値が低下させられてＧsの接続が変化させられるたびに再ルーティングされるという事実に対応している。
【００５１】
別のストラグラー変換方法は、直接ストラグラー変換と呼称され、ストラグラーが、現時点のＧs上でルーティングされ得ない場合に、直接キーパーに変換される方式である（ステップ６４６）。この場合においても、変換されたストラグラーはＧ上でルーティングされ、（必要とされる場合には）追加リンク及び容量が追加されてＧsが増大される。Ｇｓの増大の後に起こりうる最短経路の変化のために、それ以前にルーティングされた全てのストラグラーは破棄され（ステップ６４８）、閾値制御変換の場合と同様、再ルーティングされる（ステップ６２２）。
【００５２】
その後、選択された変換オプションにかかわらず、全てのストラグラーがルーティングされてワーキングリストＬ２に残存するストラグラーが無くなると、ネットワーク最適化プロセスは完了し（ブロック６３４）、最終的なネットワークトポロジーが得られる。
【００５３】
２．２  リンクデロード最適化
リンクデロードを用いる実施例においては、トポロジー全体Ｇから開始して、ある個数のわずかしか負荷のかかっていないリンクを除去することによってネットワーク費用の改善を試み、最終的なトポロジーを得る、という方針を採用する。独自の最短経路ルーティングを用いるため、リンク内の全てのトランク回線が、ネットワーク内のルーティングパターンを変更する目的で除去される。図７には、本発明に従ったリンクデロード法が示されている。まず、ステップ７０２において、担っているトラフィックフロー及びチューニング可能な利用閾値Ｔｈｄdeloadに基づいて、デロードされる候補となるリンクが識別される。詳細に述べれば、ＦＩＦＯ／ＲＥＤルータネットワークの場合には、
【数３２】
0003654499.tif 000029
の場合には、リンクｌはデロードされる候補となる。ＷＦＱ／ＬＱＤルータネットワークの場合には、対応する基準は
【数３３】
0003654499.tif 000030
である。候補となるリンクが選択されると、それらは、それらが担っているトラフィックが再ルーティングされる場合の既存のネットワーク設計に対する予想されるインパクトの大きさに従って順序付けされる（ステップ７０２）。この目的のために、候補リストが空ではない場合には（ステップ７０４）、各々の候補リンクを横断するフローの要求とホップ数との積の総和が計算される（ステップ７０８）。次に、ステップ７１０において、前記積の総和が最小である候補リンクが、ネットワークトポロジーから一時的に除去される。動機付けは、ネットワーク費用の急激な変化を回避するために、デロードプロセスの間のトポロジー／容量擾乱を最小化することである。候補リンクが一時的に除去された後、新たなルート、容量要求、及びその結果として必要になるネットワーク費用が再計算される（ステップ７１２）。リンク除去がネットワーク費用を低減する場合には、当該リンクは永久的に除去される（ステップ７１６）。しかしながら、リンク除去によってネットワーク費用が低減されない場合には、この現時点の候補リンクはトポロジー内には残存させられるが候補リストからは除去される（ステップ７１８）。その後、デロードプロセスは、積の総和が最小であるリスト内の次の候補リンクに関して（直前の候補が除去された場合には更新されたトポロジー、直前の候補が保持された場合には同一のトポロジー、のいずれかを用いて）反復される（ステップ７０４）。候補リストが空である場合には、デロードプロセスは完了している（ステップ７０６）。
【００５４】
節２．０において議論されたトポロジー最適化の種々の変形例がインプリメントされてテストされている。例えば、ストラグラーがルーティングされる際の相異なった順序付けや増大方法をリンクデロード方法と組み合わせて用いる方法などが試みられた。すなわち、リンクデロード方法は、単独の最適化方法としても利用可能であるが、増大方法と共に利用することも可能である。つまり、リンクデロード方法は、リンク増大方法の後に実行されうる。その結果得られる性能に関しては、種々のケーススタディが議論されている節４ｌ：０に示されている。
【００５５】
トポロジー最適化の増大方法においては、反復の途中で生成されたネットワーク配置の費用は顕わには考慮されない。しかしながら、ネットワーク費用の最小化は、トラフィックパッキングとトポロジー増大を介して暗黙のうちになされる。このことは、ネットワーク費用は、わずかしか利用されない付加リンクを導入することよりも既存のリンクのスペア容量上に小さな要求をパックすることによってネットワーク費用が低減されうるという観察結果に基づいている。
【００５６】
増大方法において、新たなストラグラーの要求を満たすためにリンクに付加容量が必要とされる場合、実際に必要とされる容量は、ＷＦＱ／ＬＱＤルータのケースでは、単純加算で直接的に計算されうることに留意されたい。しかしながら、ＦＩＦＯ／ＲＥＤルータネットワークにおいては、デロード方法が好ましいとされる。なぜなら、節１．０で示された必要リンク容量は、リンク上のトラフィックの混合が変化するとかなり大きく変化しうるからである。
【００５７】
さらに、最短経路に基づく要求ルーティングに関しては、余分な容量を全く有さないリンクと総容量としてゼロが割り当てられたリンクとの間に微妙な差異が存在することに留意されたい。この二つの場合における要求のルーティングは著しく異なっており、区別して考えられるべきものである。
【００５８】
従って、前述されているネットワークトポロジー最適化のあらゆる実施例が与えられると、最適化プロセッサ１８の出力（図１において参照符号Ｃが付されたもの）は、ルーティングプロセッサ１２を介して、ワーストケース必要リンク容量プロセッサ１４に供給されることが望ましいネットワークトポロジーであり、ルーティングプロセッサ１２は、前述されているように、受信したトポロジーが与えられると必要リンク容量を計算する。その後、図２に関連して説明されているように、そのトポロジーが設計者の基準を満たす最終的なトポロジーであるか否かを例えばネットワーク費用あるいは有効化に係る考察を通じて決定する。最終的なトポロジーではない場合には、最終的なネットワークトポロジーが定式化されるまで、（いずれがインプリメントされている場合においても）最適化プロセスが反復される。
【００５９】
３．０  ルータ置換
従来技術に係るＦＩＦＯ／ＲＥＤルータのみを用いる既存のＩＰネットワークを考える。そのネットワークが、単純グラフＧs＝（Ｖ’，Ｅ’）によって表現されているとする。ここで、Ｖ’は、ルータの組に対応するノードの組であり、Ｅ’は、ルータを接続しているリンクの組である。ここで、以下の問題Ｐを考える。最大Ｎmax個のＷＦＱ／ＬＱＤルータが与えられてそれぞれがＶ’内の既存のあらゆるＦＩＦＯ／ＲＥＤルータの一対一置換に用いられうるとしたとき、ネットワーク費用の削減が最大となるＦＩＦＯ／ＲＥＤルータの組を見出す。
【００６０】
ＴFIFO（Ｃ）及びＴWFQ（Ｃ）を、それぞれ、容量Ｃのリンクを終端するために必要となるＦＩＦＯ／ＲＥＤルータ及びＷＦＱ／ＬＱＤルータの終端費用とする。また、Ｍ（Ｃ，Ｌ）を、用いられているルータのタイプにかかわらず、容量Ｃ及び長さＬを有するリンクのマイレージ費用とする。既存のネットワークにおけるＦＩＦＯ／ＲＥＤルータのうちのいくつかをＷＦＱ／ＬＱＤルータで置換することによって、ネットワーク費用全体における変化は二つの個別の成分に分割されうる。第一は、選択されたＦＩＦＯ／ＲＥＤルータをＷＦＱ／ＬＱＤルータにアップグレードすることに係る費用である。第二は、従来技術に係るＦＩＦＯ／ＲＥＤスケジューリング／バッファ管理が先進的な次世代ルータにおけるＷＦＱ／ＬＱＤに置換される場合における、必要転送容量の低下に伴う費用削減である。この置換プロセスに係る費用の追加／削減の詳細を理解するために、本発明は以下の２ステップのプロセスを提供する。第一に、選択されたＦＩＦＯ／ＲＥＤルータの組を、置換するルータと同一の個数のインターフェース及び終端容量を有するＷＦＱ／ＬＱＤルータを用いて一つずつ置換する。選択されたＦＩＦＯ／ＲＥＤルータｉのこのような置換にかかる費用をＱiで表わす。第二に、ＦＩＦＯ／ＲＥＤルータｉ及びｊを接続している伝送リンクｌ＝（ｉ，ｊ）に関して、ｉ及びｊの双方がＷＦＱ／ＬＱＤルータによって置換される場合には、リンクｌの必要容量は、改善されたパケットスケジューリング及びルータバッファ管理によって低減される。結果として、費用削減は、（ｉ）新たに配置されたＷＦＱ／ＬＱＤルータに係る余剰なインターフェース／終端容量の“償還”を得ること、及び（ｉｉ）リンクｌに係るマイレージ費用の低減、から導き出される。詳細に述べれば、リンクｌ＝（ｉ，ｊ）の終端ルータｉ及びｊの双方のみをＷＦＱ／ＬＱＤルータによって置換した場合には、費用削減分Ｓi,jは、
【数３４】
0003654499.tif 000031
によって与えられる。ここで、ＣlＦIFOおよびＣlWFQは、それぞれＦＩＦＯ／ＲＥＤ及びＷＦＱ／ＬＱＤの場合に対応する要求容量である。ここで、Ｓi,jはこの種の置換から導き出される実際の費用削減量の控えめな推定であることに留意されたい。なぜなら、これは、分離されたリンク毎の基準に基づいた必要容量に係るインパクトのみを考慮しているに過ぎないからである。ＷＦＱ／ＬＱＤルータが追加された場合のリンクｌを通過するフローに係るより厳しい帯域制御のために、ネットワークのいずれかでさらなる容量低減が可能である場合がある。
【００６１】
上述された枠組みに基づいて、本発明に従って、問題Ｐが以下のような混合整数プログラミング（ＭＩＰ）問題として定式化される。
【数３５】
0003654499.tif 000032
ここで、Ｑiは、前述されたように、ルータｉのアップグレード費用である。Ｓi,jは式（２２）で定義された費用削減であり、
【数３６】
0003654499.tif 000033
の場合にはＳi,j＝０であることに留意されたい。ｘiは二値決定変数であり、ルータｉがＷＦＱ／ＬＱＤルータによって置換されるように選択された場合にのみｘi＝１である。ｙi,jは、リンクｌ＝（ｉ，ｊ）に係る費用削減実現を反映する依存変数である。上記（ａ）及び（ｂ）に規定された拘束条件に従って、ｙi,jは、ｘi＝１かつｘj＝１の場合にのみ、非零である。それ以外の場合には、ｙi,j＝０である。このことは、費用削減は、リンクの双方の終端部がＷＦＱ／ＬＱＤルータに接続される場合にのみ実現されうる、という事実に対応している。ここで、ｙi,jを二値変数として規定する必要が無いことに留意されたい。なぜなら、Ｓi,j≧０の場合には、目的とする関数を最大化することは、ｘｉ及びｘｊの値が拘束条件（ａ）及び（ｂ）に従う場合には、自動的にｙi,jを１にすることになるからである。それ以外の場合には、拘束条件によってｙi,jが０になる。Ｎmaxは、置換されることが可能なＦＩＦＯ／ＲＥＤルータの最大数を規定する入力パラメータである。Ｎmaxが｜Ｖ’｜に設定されている場合には、このＭＩＰ問題の解は、置換されるべきルータの最適数をその対応する位置と共に決定することになる。
【００６２】
上記ＭＩＰ定式化に基づいて、ルータ再配置プロセッサ２０は、標準的なＭＩＰ最適化パッケージを用いて、最適ルータ再配置ソフトウエアぷろぐらむをインプリメントする。用いられるこの種の標準的なＭＩＰ最適化パッケージには、ＡＭＰＬ（当業者には公知であり、R.Fourere, D.M.Gay and B.W.Kernighan, “ＡＭＰＬ−数学プログラミング向けのモデリング言語”(Boyd & Fraser Publishing Company(1993))に記述されている）及びＣＰＬＥＸ混合整数ソルバー（ＩＬＯＧ  Ｉｎｃ．のＣＰＬＥＸ部門より入手可能）が含まれる。３３３ＭＨｚのＰｅｎｔｉｕｍＩＩＰＣで実行すると、およそ１００個のノード及び３００のリンクを有する従来技術に係るＦＩＦＯ／ＲＥＤネットワークにおけるＷＦＱ／ＬＱＤルータの最適配置が、数秒のうちに決定された。
【００６３】
４．０  ケーススタディ
この節では、本発明に従ったＩＰネットワーク容量割り当て及び最適ルータ再配置に関するいくつかのケーススタディ（具体例）の結果が議論される。第一のケーススタディは、１９９４年末のＮＳＦＮＥＴのトポロジーに基づいている。図１２は、このトポロジーを示しており、本発明に従ったデザインフレームワークにおける完全トポロジーＧとして用いられたものである。トランク回線サイズは、ネットワーク全体で２４０にセットされている。図１３は、その要素がこの例で用いられているポイント−ツー−ポイントトラフィック要求に対応している行列を示している。トラフィック要求の相対的な大きさは、メリットネットワーク情報センターサービスによる“ＮＳＦＮＥＴバックボーンネットワークに係る統計報告（１９９４）”という１９９４年の統計値に従って、R.H.Hwangによる“高速ネットワークにおけるルーティング”（マサチューセッツ大学（at Amherst）の博士学位論文（１９９３年５月））によって提案されたスケーリング法を用いて設定されている。さらに、各々の要求の絶対値を、１９９４年からの成長分を反映する目的でスケールアップしている。ネットワークコスト全体Ｊが、トランク回線当たりのある任意の終端費用及び長さ当たりのある任意のマイレージ費用に基づいて計算される。終端費用及びマイレージ費用は、ＦＩＦＯ／ＲＥＤルータとＷＦＱ／ＬＱＤルータとで同一であると仮定された。ネットワーク設計においては、前述された種々のトポロジー最適化戦略及び相異なったネットワーク混雑仮定が用いられた。
【００６４】
４．１  同種ルータによる設計
まず、ＦＩＦＯ／ＲＥＤルータあるいはＷＦＱ／ＬＱＤルータのいずれか一方だけが用いられる同種ネットワークの場合を考察する。以下、これらのネットワークを、全ＦＩＦＯ／ＲＥＤケース及び全ＷＦＱ／ＬＱＤケースと呼称する。ここで考察するネットワーク設計問題においては、全ネットワーク費用は二つのファクタ、すなわち、（１）トポロジー最適化法の結果としての最終ネットワークトポロジー、及び、（２）リンクの必要容量（これは、ルータにおいて利用可能なスケジューリング／バッファリング機能の関数である）、によって支配されている。以下、これらの二つのファクタによるインパクトを個別に議論する。
【００６５】
４．１．１  ルータ機能によるインパクト
ルータ機能によるインパクトのみに注目するために、以下では、全ての設計に関して同一の最終トポロジーを用いる。このことは、トポロジー最適化モジュールを停止して、初期バックボーンＧを最終トポロジーとして用いる、すなわち、最終Ｇs＝Ｇとすることによって実現される。結果として、全ＷＦＱ／ＬＱＤ設計及び全ＦＩＦＯ／ＲＥＤ設計の双方ともが、図１２に示されたものと同一のトポロジーを有することになる。この際、全てのリンクはアクティブである。図１４は、対応する結果をまとめたものである。同一の最終ネットワークトポロジー（よってトラフィックルーティングが同一）の場合には、全ＷＦＱ／ＬＱＤ設計と全ＦＩＦＯ／ＲＥＤ設計との間の費用の差異は、ＷＦＱ／ＬＱＤルータの先進的なスケジューリング及びバッファ管理機能に起因する容量削減のみに由来する。全ＷＦＱ／ＬＱＤ設計の費用は相異なったネットワーク混雑シナリオにおいても不変であるが、全ＦＩＦＯ／ＲＥＤ設計の費用は、ネットワーク混雑シナリオに係る仮定に依存して変化する。全ＷＦＱ／ＬＱＤ設計の場合には、ワーストケース混雑シナリオの下では、すなわち、-ＣlFIFO（Ｈworst）に基づくと、全ＦＩＦＯ／ＲＥＤ設計の場合の１／３未満となる。また、最良混雑シナリオ（Ｈbest）の場合においてもかなり低い。相異なった混雑シナリオ（Ｈworst、Ｈhop、Ｈone、Ｈbest）が仮定された場合にＦＩＦＯ設計の費用が著しく異なることに注目されたい。しかしながら、複数ボトルネック効果に起因する（-ＣlFIFO（Ｈhop）と＿ＣlFIFO（Ｈhop）との間及び-ＣlFIFO（Ｈone）と＿ＣlFIFO（Ｈone）との間）費用の差異は、Ｈの選択に起因する費用の差異と比較して小さい。前述されているように、混雑シナリオは実際には動的であって予測不可能であるため、全トラフィックシナリオの下での最小スループットに係る決定論的保証をすることを欲する場合には、ＦＩＦＯ／ＲＥＤリンク容量計算に関しては、ワーストケースシナリオ、すなわちＨworst、を仮定するしか選択肢が存在しない。図１４は、κでさらわされた“ネットワーク全体での過剰構成ファクタ”と呼ばれる列も含んでいる。最終ネットワークトポロジーＧs（Ｖ’，Ｅ’）及び最小スループット要求ｄiを満足する関連したリンク容量Ｃlが与えられると、κは
【数３７】
0003654499.tif 000034
のように定義される。κの定義を誘導するために、個々のリンクｌ及び対応する比
【数３８】
0003654499.tif 000035
を考える。理想的には、リンク容量がトランク回線の大きさという段差を有してではなく連続的に利用可能であり、かつ、理想的なリンク帯域スケジューリング／バッファ管理が利用可能である場合には、全ての要求の必要最小スループットを満たすためには、
【数３８】
0003654499.tif 000036
が１に等しいことが十分である。同一の議論がネットワーク内の全てのリンクに関して適用されると、κの理想値（最小値）も１に等しくなる。よって、κは、リンク容量の離散的性質（すなわち、トランク回線数を直近の整数倍に丸めることが必要であること）やルータにおけるソフィスティケートされた帯域スケジューリング及びバッファ管理の欠如などといった理想的ではない状況に起因する“容量過剰構成”を表わす指標となる。
【００６６】
図１４より、ＷＦＱ／ＬＱＤ設計の場合には、リンク容量の離散的性質のために、κが１より少し大きいことがわかる。他方、ＦＩＦＯ／ＲＥＤルータにおい蹴る適切なトラフィック管理機能の欠如のために、ＦＩＦＯ／ＲＥＤ設計の場合には遙かに大きい容量過剰構成が必要とされる。すなわち、必要最小スループットを満たす目的でＴＣＰ固有の不公平性を克服するためには、過剰なリンク容量が必要とされる。
【００６７】
ＮＳＦＮＥＴバックボーン設計に加えて、大規模キャリアクラスのネットワークの設計に同様の方法を試してみた。その結果は、図１５に示されている。見出されたことは、ＮＳＦＮＥＴの場合と質的には同様であるが、全ＦＩＦＯ／ＲＥＤ配置と全ＷＦＱ／ＬＱＤ配置との間の相対的な費用の差異がより大きくなっていることである。このことは、ＮＳＦＮＥＴの場合と比較して、ネットワークの大きさ及びトラフィックの多様性が増大していることに起因する。式（５）から、ＦＩＦＯ／ＲＥＤルータの場合には、リンクの必要容量は最大
【数３９】
0003654499.tif 000037
比を有する要求によって支配されている、ということに留意されたい。ネットワークが大きくなればなるほど、トラフィック要求のエンド−ツー−エンド遅延がより多様化し、よって
【数３９】
0003654499.tif 000038
の最大値も大きくなる。
【００６８】
４．１．２  トポロジー最適化法の比較
次に、節２．０で議論した種々のトポロジー最適化法の有効性の比較を行なう。ここでは、ＮＳＦＮＥＴバックボーンを例示目的に使用する。図１６は、ＷＦＱ／ＬＱＤルータのみを利用した種々の最適化オプションの結果を示している。ＦＩＦＯ／ＲＥＤルータの場合は含まれていない。なぜなら、そのような場合にはリンクデロード法がより望ましいからである。図１６に示されているように、種々の方式に基づいたネットワーク費用についての結果は、“容量のみの”増大方法を除いて互いに非常に近接している。この“容量のみ”増大方法はかなり悪く、費用が３０％より多く増大している。このような性能は、本発明の発明者が試みた他の設計の場合においても共通に見られるものであって、要求をキーパーあるいはストラグラーとして分類する際の適応の欠如の効果に擬せられるものである。すなわち、ひとたび閾値が選択されると、各々の要求は分類されて、通常、決して変換されない。ＮＳＦＮＥＴの例においては、選択された閾値は、キーパーによって構成されたサブグラフＧsの接続性が充分ではなく、いくつかの要求が他のより最適なトポロジーの場合よりもより長い経路を横断しなければならない。“容量のみ”増大方法を増強する一つの可能性のある方法は、複数個の閾値を試行して、最低ネットワーク費用を実現するものを選択することである。
【００６９】
ＮＳＦＮＥＴスタディに関しては、初期バックボーンＧが疎であって各ノード対間での要求が存在するために、トポロジー最適化によって除去されうるＧ内のリンクはほとんど無い。結果として、トポロジー最適化法により、最適化されていないトポロジーＧに対して最大およそ３％の費用削減が実現された。しかしながら、他のテストケースにおいては、トポロジー最適化法を用いることによって、およそ１５％から９０％以上というより大きな費用削減が実現できることが明らかになった。一般に、実際の費用削減は初期トポロジーＧ及びトラフィック要求の分布に強く依存する関数である。
【００７０】
計算効率の観点では、リンクデロード法のみに依存することが、特に初期バックボーンＧが非常に高い接続性を有していて、要求の大部分がトランク回線サイズに比べて遙かに小さい場合には、比較的高コストである。これらの場合には、リンクデロードのみの方式ではＧ内のほとんど全てのリンクをデロードしようとするのに対し、増大方式は、キーパーのルーティングを介して、“コア”トポロジーを構成するリンクのサブセットを高速に選択することによってプロセスをスピードアップすることが可能である。最後に、リンクデロード法は、通常、同一かあるいはよりよいネットワーク費用を実現するため、増大法が完了した後にリンクデロード法を適用することが望ましい。このようにすることによって、試行した種々の設計の場合では、０から１５％の範囲のさらなる費用削減が実現された。
【００７１】
図１７及び１８は、トポロジー最適化及びルータ機能の組み合わせによるネットワーク費用へのインパクトを、それぞれＮＳＦＮＥＴの場合とキャリアクラスバックボーン例の場合に示すものである。図１７及び１８に示されているネットワーク費用は、与えられた配置に関して見出された“最適”トポロジーに基づくものである。最も控えめな仮定の下でも、ＦＩＦＯ／ＲＥＤルータの代わりにＷＦＱ／ＬＱＤルータを用いることによって費用に関する実質的な利点が実現される。
【００７２】
４．２  ルータ配置
次に、固定数Ｎ個のＷＦＱ／ＬＱＤルータのみが、前述されたＮＳＦＮＥＴバックボーンを構成するために他のＦＩＦＯ／ＲＥＤルータと共に用いられる異種配置の場合を考える。節３．０において記述されたＷＦＱ／ＬＱＤルータ配置に基づいて、図１９は、Ｎが変化した際のＷＦＱ／ＬＱＤルータの最適配置を示している。-ＣlFIFO（Ｈworst）に基づく対応するネットワーク費用も計算されている。双方向トラフィック要求の仮定により、あらゆる容量（よって費用）削減を実現するためには、少なくとも二つのＷＦＱ／ＬＱＤルータが必要とされる。以下、全ＦＩＦＯ／ＲＥＤ配置に係る費用を基準として利用する。ＷＦＱ／ＬＱＤルータの第一対は、適切に配置されると、およそ１２．１％の費用削減を実現することが可能である。これは、ノード８（サンフランシスコ）とノード１０（シカゴ）との間の単一の長距離リンクの必要容量を低減することによって実現される。このリンクは、その容量の絶対値が大きいこと（トランク回線の絶対数が大きい）及びマイレージが大きいことのために、最も著しい費用削減となる。より多くのＷＦＱ／ＬＱＤルータが最適配置されるにつれて、リンクによって担われているトラフィックの
【数３９】
0003654499.tif 000039
比の最大値が大きいために大きな過剰構成ファクタを有し、大きな絶対容量を有するリンク間で、ＷＦＱ／ＬＱＤルータがクラスタを構成するようになる。
【００７３】
同様のルータ配置が、キャリアクラスのネットワーク例に関して適用された。図２０は、全ＦＩＦＯ／ＲＥＤ配置における相異なった個数のルータが最適配置されたＷＦＱ／ＬＱＤルータによって置換された場合の対応する費用削減を示している。まず、１０％のＦＩＦＯ／ＲＥＤルータが最適配置されたＷＦＱ／ＬＱＤルータによって置換されると、ネットワーク費用がおよそ１５％削減される。この大幅な費用削減は、高価な（長距離の）リンクにおける大幅な容量低減に依るものである。ＷＦＱ／ＬＱＤルータの割合が２０％、さらには３０％へと増大させられた場合にも、費用低減は依然としてかなりの大きさを保っている。これは、ＷＦＱ／ＬＱＤクラスタの形成に依るものであって、“利益を受ける”リンク、すなわちクラスタ内及びクラスタ間リンク、の個数を急速に増大させることになる。その後は、早期の最適化によって大部分の費用削減がなされてしまっているために、費用削減率は徐々に低下していく。
【００７４】
５．０  ＦＩＦＯ／ＲＥＤの下でのスループット割り当て
サブセクション１．１を参照すると、M.Mathis, J.Semke, J.Mahdavi, and T.Ottによる“ＴＣＰ混雑回避アルゴリズムの巨視的振る舞い”という表題の論文（ACM Computer Comm. Review, Vol.27, No.3,pp.67-82(1997.7)）においてＴＣＰ接続のスループットを計算するために用いられている仮定は、
（ｉ）リンクは軽度から中度のパケットロスの下で動作しており、ＴＣＰの動的ウィンドウメカニズムは混雑回避領域によって主として支配されている。この領域においては、パケットロスが検出されると、混雑ウィンドウが半分に閉じられる。ロスが著しい条件下では、ＴＣＰウィンドウフロー制御においてはタイムアウトが発生し、ウィンドウが１パケットの値に低減されてスロースタートモードになる。
（ｉｉ）接続の経路に沿ったパケットロスは、１／ｐ個のパケットが送信されるたび毎に１つのパケットが欠落するという仮定の下に、一定の損失確率ｐによって表現される。
【００７５】
これらの仮定の下では、接続の混雑ウィンドウは、図２１に示されているような、周期的な鋸波状の振る舞いをする。図２１においては、最大ウィンドウサイズＷmaxが充分大きく、混雑ウィンドウはその飽和値に到達しない（Ｗ＜Ｗmax）ことが仮定されている。レシーバが全てのパケットに対してアクノレッジを返す場合には、ウィンドウは１ラウンドトリップ時間だけ開き（このことは、図２１における傾きが１に等しいことを意味している）、各々のサイクルはＷ／２ラウンドトリップ時間（τ・Ｗ／２）だけ継続する。サイクル当たりに送信されるパケット数は、グラフの下側の面積によって与えられ、（Ｗ／２）2＋０．５×（Ｗ／２）2＝（３／８）×Ｗ2である。仮定（ｉｉ）の下では、これは、１／ｐに等しく、すなわち、Ｗ＝（８／３ｐ）0.5であることを意味している。よって、ＴＣＰ接続のスループットは、
【数４０】
0003654499.tif 000040
によって与えられる。
【００７６】
リンクｌを介してルーティングされる全ＴＣＰ接続の組Ｆlにおける各々の接続のスループットを計算する目的で、以下の仮定を行なう。
（ｉｉｉ）Ｓを混雑したリンクの組とし、Ｘjをリンクｊにおけるパケットドロッププロセスとする。Ｘj（ｊ∈Ｓ）は独立であって、各々が同一の損失確率ｐ0によって表現されると仮定する。同様の仮定は、S.Floydによる“パケット交換ネットワークにおける複数個の混雑したゲートウェイを有する接続  第一部。一方通行トラフィック”という表題の論文（ACM Computer Comm. Review, Vol.21, No.5, pp.30-47(1991.10)）において、ｎ個のリンク全てとリンク当たり一つのホップ接続を横断する（すなわち、各々のリンクが二つの接続によって横断されている）ｎホップ接続から構成されたｎ個のリンク及び（ｎ＋１）個の接続よりなる線型トポロジーにおけるＴＣＰスループットを計算するために用いられている。
【００７７】
この仮定の下では、接続ｉに係る経路ロス確率は、
ｐi＝１−（１−ｐ0）hi                                    （２５）
によって与えられる。ここで、ｈｉは、ＴＣＰ接続の経路における混雑したホップの個数である。実際、ｊ1、ｊ2、．．．、ｊhiを接続ｉの経路における混雑したリンクの順序付けられた組とし、ｊ1及びｊhiを、それぞれ、接続ｉによって横断される最初と最後の混雑したリンクとする。接続ｉのＮ個のパケットがソースから送出される場合には、ｐ0Ｎ個がリンクｊ1において落ち、（１−ｐ0）Ｎ個が通過する。リンクｊ２に到達した（１−ｐ0）Ｎ個のパケットのうちのｐ0（１−ｐ0）Ｎ個が落ち、（１−ｐ0）2Ｎ個が通過する。このようにして、リンクｊhiに到達した（１−ｐ0）hi-1Ｎ個のパケットのうちのｐ0（１−ｐ0）hi-1Ｎ個が落ち、（１−ｐ0）hiＮ個が伝達される。それゆえ、失われたパケットの総数はＮ−（１−ｐ0）hiＮ個であって、式（２５）で与えられる損失比に対応する。損失確率ｐ0が小さい場合には、ｐiはｈｉ・ｐ0に等しい。なぜなら、式（２５）におけるｐ0の高次の項は無視されるからである。式（２４）に代入することによって、
【数４１】
0003654499.tif 000041
を得る。ここで、
【数４２】
0003654499.tif 000042
である。
【００７８】
与えられたリンクｌ∈Ｓ（容量ｃlFIFO）に対して、ｒliを接続ｉ∈Ｆlのスループットシェアとする。サブセクション１．１において議論されて考慮された複数ボトルネック効果を無視してリンクｌのみを考えると、式（２６）におけるｒiをｒliとして取り扱うことが可能であり、
【数４３】
0003654499.tif 000043
が得られる。明らかに、リンクバッファは、式（２７）におけるｃlFIFOの総計スループットを実現することが可能である程度に充分に（帯域遅延積のオーダー程度）大きい必要がある。このような状況ではない場合には、リンクはわずかしか利用されていない。式（２７）より、δの値として
【数４４】
0003654499.tif 000044
が、接続ｉのスループットシェアとして
【数４５】
0003654499.tif 000045
が得られる。前掲のMathisらによる参照文献においては、式（２４）の結果の有効性を確認するために、シミュレーションが用いられた。前掲のFloydによる参照文献においては、前述されたリンク当たり二つの接続の場合に関する同様の結果をシミュレーションで導いて有効性を確認する目的で、相異なった方法が用いられた。しかしながら、式（２８）より得られる結果は任意のトポロジーにおける任意のＴＣＰトラフィックパターンへの一般化であって、スループット割り当ての重み付けの性質を表わしている。
【００７９】
６．０  ルータ再配置実施例におけるＮＰハードネス
以下のグラフ問題Ｐ（Ｇ，Ｎ）を考える。  単純重みグラフＧ＝（Ｖ，Ｅ，Ｓ）が与えられている。この際、Ｓは｜Ｖ｜×｜Ｖ｜重み行列であって、そのノード対ｉ，ｊ∈Ｖに対応する要素Ｓi,jは、
【数４６】
0003654499.tif 000046
である。Ｓi,jの削減は、双方のノードｉ及びｊが選択された場合に実現される。目的は、選択されるノード総数をＮ以下に保ちつつ、削減量を最大化することである。このグラフ問題Ｐ（Ｇ，Ｎ）は、節３．０で記述された問題Ｐにおいて、全てのＱiをゼロに設定した特別な場合であることは明らかである。Ｐ（Ｇ，Ｎ）におけるノードの選択は、ＷＦＱ／ＬＱＤアップグレードを行なうためのＦＩＦＯ／ＲＥＤロケーションの選択に対応している。
【００８０】
Ｐ（Ｇ，Ｎ）はＰの特別な場合であるため、ＰがＮＰハードであることを証明するためには、Ｐ（Ｇ，Ｎ）がＮＰハードであることを示すのが十分である。Ｐ（Ｇ，Ｎ）がＮＰハードであることの証明は、ＮＰ完全最大クリーク問題の決定バージョンのＰ（Ｇ，Ｎ）の場合への還元を通じたものである。クリーク問題は当業者には公知であり、例えば、M.R.Garey and D.S.Johnsonによる“コンピュータ及びイントラクタビリティ。ＮＰ完全性の理論への指針”という表題の文献（Freeman(1979)）及びC.H.Papadimitriouらによる“組み合わせ最適化。アルゴリズム及び複雑さ”という表題の文献（Prentice Hall(1982)）に記述されている。最大クリーク問題Ｑ（Ｇ，Ｎ）の決定バージョンは、以下のように書き表わすことが可能である。  単純グラフＧ＝（Ｖ，Ｅ）及び正の整数Ｎが与えられた場合に、｜Ｖ’｜＝Ｎかつ全ての相異なったｉ，ｊ∈Ｖ’に対して（ｉ，ｊ）∈ＥなるＧのサブグラフＧs＝（Ｖ’，Ｅ’）が存在するか？
【００８１】
Ｐ（Ｇ，Ｎ）がＮＰハードであることを証明するために、
【数４７】
0003654499.tif 000047
と設定することによって、Ｑ（Ｇ，Ｎ）をＰ（Ｇ，Ｎ）の場合に還元することが可能である。Ｐ（Ｇ，Ｎ）から導かれる最大削減がＮ（Ｎ−１）／２に等しく、かつこれ以上還元できない場合にのみ、Ｑ（Ｇ，Ｎ）が“ｙｅｓ”という解を有することは明らかである。
【００８２】
問題Ｐは、以下のステップを用いて、一般化されたナップザック問題に変換されることが可能である。第一に、ナップザックの大きさをＮmaxに設定し、Ｇ内のＦＩＦＯ／ＲＥＤルータを、それぞれが１という大きさを有する、ナップザックに詰め込まれるアイテムと見なす。次に、あらゆるアイテム対（ｉ，ｊ）に、ユーティリティ値Ｓi,jを割り当てる。このことは、アイテムｉ及びｊの双方がナップザックに詰め込まれる場合にのみ実現される。その後、各々のアイテムｉに対して、それがナップザックに詰め込まれる場合にペナルティＱiを関連づける。選択されたアイテムの組に係る総ユーティリティ値を、ユーティリティ値Ｓi,jの総和からその組のペナルティＱiの総和を減じたものと定義する。このようにすることで、置換されるべきＦＩＦＯ／ＲＥＤルータの最適の組の選択が、与えられたナップザックサイズの下で総ユーティリティ値を最大化するような詰め込まれるアイテムの組の選択の問題になる。
【００８３】
よって、既に説明されているように、ＩＰベースネットワークにおける性能保証を実現する必要性は、数多くのキャリアがバックボーンインターネット接続を提供するためにＩＰを直接ＳＯＮＥＴにパックするようになってきているため、より重要になってきている。本発明は、これら及びその他の問題を取り扱うネットワーク設計及び容量最適化アルゴリズムを提供する。さらに、本発明は、同種（全ＷＦＱ／ＬＱＤあるいは全ＦＩＦＯ／ＲＥＤネットワーク）及び異種ネットワークの双方に係る設計を実現する。異種ネットワークにおいては、本発明に係る方法は、ＦＩＦＯ／ＲＥＤルータが組み込まれたネットワークにおけるＷＦＱ／ＬＱＤルータの最適配置の問題を解決する。
【００８４】
ここで、これまでに記述された本発明の望ましい実施例に係る詳細な記述が本発明を制限している訳では無い。例えば、本発明に係るネットワーク設計システム及び方法は、ＶＰＮサービスを実現する他のアプローチ、例えば（ｉ）ＩＰパケット中のサービスタイプ（ＴＯＳ）フィールドを利用して、ネットワークエッジに位置するルータに監視させてＶＰＮ契約を超過しているトラフィックにマークをする方法、及び、（ｉｉ）（ｉ）とＷＦＱ／ＬＱＤを組み合わせた組み合わせ方法、等に対しても適用可能である。さらに、本発明は、より高度なルーティング、例えば偏差（デフレクション）及びＯＳＰＦにおけるＴＯＳベースルーティングの使用を介したループフリー非最短経路ネクストホップフォワーディング等と共にインプリメントされうる。さらに、本発明は、ＮＰハードルータ配置問題を解く他の方法をインプリメントすることも可能である。本発明は、例えば、同種ＷＦＱ／ＬＱＤルータネットワークを同種ＦＩＦＯ／ＲＥＤルータネットワークと組み合わせる２層ネットワークを介した差動サービスをサポートするインフラストラクチャの設計に用いられうる。さらに、前述されたＴＣＰスループットモデルは、タイムアウト及び／あるいは最大レシーバ／送信側ウィンドウサイズが主たるものであるような領域をカバーするように、及びクラス間ＷＦＱや各クラスのフロー間でのＦＩＦＯ等の他のタイプのパケットスケジューリングをカバーするように、それぞれ拡張されうる。
【００８５】
以上の説明は、本発明の一実施例に関するもので，この技術分野の当業者であれば、本発明の種々の変形例が考え得るが、それらはいずれも本発明の技術的範囲に包含される。
【００８６】
【発明の効果】
以上述べたごとく、本発明によれば、ワーストケース及び最良のリンク能力要求を自動的に計算し、ネットワークのトポロジーを最適化し、及び、ネットワークにおける最適ルータ配置を決定する方法及びその装置が提供される。
【図面の簡単な説明】
【図１】  本発明の実施例に従ったＩＰネットワーク設計システムを示すブロック図。
【図２】  本発明の実施例に従った設計方法を示す流れ図。
【図３】  本発明の実施例に従った必要リンク容量計算法を示す流れ図。
【図４】  本発明の別の実施例に従った必要リンク容量計算法を示す流れ図。
【図５】  本発明のさらに別の実施例に従った必要リンク容量計算法を示す流れ図。
【図６】  本発明の実施例に従ったネットワークトポロジーの最適化法を示す流れ図。
【図７】  本発明の実施例に従ったネットワークトポロジーの最適化法を示す流れ図。
【図８】  本発明の実施例に従ったネットワークトポロジーの最適化法を示す流れ図。
【図９】  本発明の実施例に従ったネットワークトポロジーの最適化法を示す流れ図。
【図１０】  本発明の別の実施例に従ったネットワークトポロジーの最適化法を示す流れ図。
【図１１】  本発明の実施例に従ったネットワーク内ルータの配置の決定法を示す流れ図。
【図１２】  本発明のインプリメントする場合のネットワークトポロジーの一例を示す図。
【図１３】  本発明に関して実行されたケーススタディに係る実例及びその結果を示す表。
【図１４】  本発明に関して実行されたケーススタディに係る実例及びその結果を示す表。
【図１５】  本発明に関して実行されたケーススタディに係る実例及びその結果を示す表。
【図１６】  本発明に関して実行されたケーススタディに係る実例及びその結果を示す表。
【図１７】  本発明に関して実行されたケーススタディに係る実例及びその結果を示す表。
【図１８】  本発明に関して実行されたケーススタディに係る実例及びその結果を示す表。
【図１９】  本発明に関して実行されたケーススタディに係る実例及びその結果を示す表。
【図２０】  本発明に関して実行されたケーススタディに係る実例及びその結果を示す表。
【図２１】  ＴＣＰ混雑ウィンドウのダイナミクスを例示するグラフ。
【符号の説明】
１０  ＩＰネットワーク設計システム
１２  ルーティングプロセッサ
１４  ワーストケース必要リンク容量プロセッサ
１６  最良リンク容量設計プロセッサ
１８  ネットワークトポロジー最適化プロセッサ
２０  ルータ再配置プロセッサ
【図１】
0003654499.tif 000048
【図２】
0003654499.tif 000049
【図３】
0003654499.tif 000050
【図４】
0003654499.tif 000051
【図５】
0003654499.tif 000052
【図６】
0003654499.tif 000053
【図７】
0003654499.tif 000054
【図８】
0003654499.tif 000055
【図９】
0003654499.tif 000056
【図１０】
0003654499.tif 000057
【図１１】
0003654499.tif 000058
【図１２】
0003654499.tif 000059
【図１３】
0003654499.tif 000060
【図１４】
0003654499.tif 000061
【図１５】
0003654499.tif 000062
【図１６】
0003654499.tif 000063
【図１７】
0003654499.tif 000064
【図１８】
0003654499.tif 000065
【図１９】
0003654499.tif 000066
【図２０】
0003654499.tif 000067
【図２１】
0003654499.tif 000068