JP2000165450A

JP2000165450A - 通信ネットワ―ク設計方法及びその装置

Info

Publication number: JP2000165450A
Application number: JP33131199A
Authority: JP
Inventors: Benmohamed Lotfi; ベンモハームドロトゥフィ; Dravida Subrahmanyam; ドラビダスブラーマニアム; Harshavardhana Paramasiviah; ハーシャバードハナパラマシビアー; Cheong Lau Wing; チェオンラオウィン; Kumar Mittal Ajay; クマーミッタルアジェイ
Original assignee: Lucent Technologies Inc
Current assignee: Nokia of America Corp
Priority date: 1998-11-24
Filing date: 1999-11-22
Publication date: 2000-06-16
Also published as: CA2285789A1; EP1005193A2; KR20000035662A; US6795399B1

Abstract

(57)【要約】【課題】最悪及び最良の必要リンク容量を自動的に計
算し、ネットワークのトポロジーを最適化し、最適ルー
タ配置を決定するツールを提供すること。【解決手段】与えられたネットワークトポロジー、特
定のＩＰ要求及びネットワーク遅延に関して、本発明に
係る設計方法は、ユーザが、与えられたネットワークの
各々のリンクに係る種々のネットワーク混雑シナリオ、
例えばネットワーク全体に係る複数個のボトルネック事
象の発生など、に係る必要リンク容量を計算することを
可能にする。また、最適ネットワークトポロジーが、本
発明に従って、全体としてのネットワークコストの低減
を指向するように定式化される。さらに、既存のネット
ワークにおけるＦＩＦＯ／ＲＥＤルータを置換するため
のＷＦＱ／ＬＱＤルータの配置を決定する方法及び装置
が提供される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はパケットベースネッ
トワークの設計方法及びその装置に関し、特に性能を保
証したＩＰ（インターネットプロトコル）ネットワーク
の設計に関する。

【０００２】

【従来の技術】従来技術に係るＩＰネットワークは、そ
の能力に係る企画・設計の最適化が非常に限られた状態
で構築されてきた。これらのネットワークは、性能を保
証せず、“できるだけの努力をすることによって実現さ
れるサービス”のみを提供している。しかしながら、顧
客の期待は、ＩＰネットワークが予測可能な性能を提供
するように設計されることによって初めて充足される。
特に、ネットワークサービスプロバイダは、彼ら自身の
仮想プライベートネットワーク（ＶＰＮ）顧客に対し
て、帯域保証をサポートしなければならない。

【０００３】加えて、あらゆるネットワーク設計に係る
考慮事項に含まれるべきことは、与えられたネットワー
クにおいて用いられるネットワークルータには複数のタ
イプが存在する、という事実である。例えば、ルーセン
ト・テクノロジー（Lucent Technologies, Inc.、New J
ersey州Murray Hill）社より市販されているLucent'sPa
cketStar^TMＩＰスイッチは、重み付け公平キューイング
（ＷＦＱ）及び最長キュードロップ（ＬＱＤ）を用いた
フロー毎キューイングを含む、斬新なトラフィックスケ
ジューリング並びにバッファ管理能力を有しており、非
常に高いレベルのリソース利用率を達成しつつＶＰＮに
対する最小帯域保証を行なうことを可能にしている。他
方、既存のレガシールータは、適切なフロー分離をサポ
ートせず、それらの先入れ先出し（ＦＩＦＯ）スケジュ
ーリングが、ランダム早期検出（ＲＥＤ）バッファ管理
ポリシーと組み合わせた場合においてさえも、ＶＰＮ間
で共有される帯域にわずかの制御しか行なうことができ
ず、スループットがＴＣＰ（トランスミッション制御プ
ロトコル）の動的性質によって大きく影響を受けてしま
う。このＴＣＰは、ＩＰネットワークにおいて最も多く
用いられている転送プロトコルである。

【０００４】

【発明が解決しようとする課題】従って、ユーザ、すな
わちネットワークデザイナに、同一（同種）あるいは異
なった（異種）タイプのルータを有し、例えばＶＰＮ等
の種々のアプリケーションに関して実質的な性能の保証
を実現するＩＰネットワークを設計することを可能にす
る、ネットワーク設計ツールに関する要求が存在する。
詳細に述べれば、デザイナによって与えられる仕様に基
づいてワーストケース及び最良の必要リンク容量を自動
的に計算し、ネットワークのトポロジーを最適化し、及
び、ネットワークにおける最適ルータ配置を決定する設
計ツールに係る要求が存在する。

【０００５】

【課題を解決するための手段】本発明は、既存のＩＰネ
ットワーク、例えば“最大の努力”基準の下に設計され
たネットワークなどと比較して、実質的に改善された性
能を有するＩＰネットワークを設計する方法及び装置を
提供する。詳細に述べれば、本発明は、ワーストケース
及び最良のリンク能力要求を自動的に計算し、ネットワ
ークのトポロジーを最適化し、及び、ネットワークにお
ける最適ルータ配置を決定する方法及びその装置を含ん
でいる。

【０００６】本発明の第一の側面においては、ネットワ
ークのリンクに係る必要リンク容量を計算する方法及び
その装置が提供される。詳細に述べれば、最大及び最小
リンク容量限界が計算可能であって、ユーザに、種々の
設計パラメータの関数としてワーストケース及び最良の
結果を提供する設計方法論が提供される。すなわち、与
えられたネットワークトポロジー、特定のＩＰ要求及び
ネットワーク遅延に関して、本発明に係る設計方法は、
ユーザが、与えられたネットワークの各々のリンクに係
る種々のネットワーク混雑シナリオ、例えばネットワー
ク全体に係る複数個のボトルネック事象の発生など、に
係る必要リンク容量を計算することを可能にする。本発
明に係る設計方法においては、ユーザは、特定のトポロ
ジーが与えられると、そのネットワークのどの位置に特
定のボトルネックが存在しているかを知ることを必要と
せずに、ＩＰネットワークを設計することが可能であ
る。さらに、本発明に係るリンク容量計算法は、与えら
れた要求内に単一あるいは複数個の接続が存在するよう
な場合も取り扱う。

【０００７】本発明に係る第二の側面においては、ネッ
トワーク設計に関連するネットワークトポロジーを最適
化する方法及び装置が提供される。詳細に述べれば、最
適ネットワークトポロジーが、本発明に従って、全体と
してのネットワークコストの低減を指向するように定式
化される。ある実施例においては、ネットワークトポロ
ジーにあまり用いられないリンクを付加することではな
く、ある既存のリンクのスペア容量に係るわずかな要求
をパックすることによって、ネットワークコストの低減
を指向する反復増強法が提供される。別の実施例では、
最適ネットワークトポロジーを構成する目的で、負荷の
軽い識別されたリンクを除去することによってネットワ
ークコストの低減を指向する反復デロード法が提供され
る。

【０００８】本発明に係る第三の側面においては、ネッ
トワークコスト削減を最大にすることを目指して既存の
ネットワークにおけるＦＩＦＯ／ＲＥＤルータを置換す
るためのＷＦＱ／ＬＱＤルータの配置を決定する方法及
び装置が提供される。本発明に係る方法は、混合整数プ
ログラミングモデルを利用することによってこの種の決
定を実現する。

【０００９】

【発明の実施の形態】以下、本発明は、ＶＰＮの枠組み
の中で記述される。しかしながら、本発明はそのような
アプリケーションあるいはシステムに限定されているの
ではない。本明細書に記述されている考え方は、あらゆ
るＩＰアプリケーション及びシステムアーキテクチャを
含むあらゆるタイプのパケットベースのネットワークに
対して適用可能である。さらに、本明細書において用い
られている“プロセッサ”という術語は、ＣＰＵ（中央
処理ユニット）及び関連するメモリを含むあらゆる処理
デバイスを包含することを企図したものである。本明細
書において用いられる“メモリ”という術語は、プロセ
ッサあるいはＣＰＵに関連するメモリ、例えばＲＡＭ、
ＲＯＭ、固定記憶デバイス（例えばハードディスクドラ
イブ）、あるいはリムーバブル記憶デバイス（例えばフ
ロッピーディスク）等を含むものである。加えて、処理
デバイスは、例えばキーボードのような、処理ユニット
にデータを入力する単一あるいは複数個の入力デバイ
ス、及び、ＣＲＴディスプレイ及び／あるいはプリンタ
のような、処理ユニットに係る結果を出力する単一ある
いは複数個の出力デバイスを有している。さらに、プロ
セッサに関連する種々の要素が他のプロセッサによって
共有される場合もあり得ることに留意されたい。従っ
て、本明細書において記述されている、本発明に係る方
法を実行するソフトウエアインストラクションすなわち
コードは、単一あるいは複数個の関連するメモリデバイ
ス（ＲＯＭ、固定あるいはリムーバブル記憶装置）にス
トアされており、用いられる場合には、ＲＡＭにロード
されてＣＰＵによって実行される。さらに、特に明示し
ない限り、本明細書においては、“ノード”、“スイッ
チ”、“ルータ”という術語が相互に交換可能であるこ
とにも留意されたい。

【００１０】前述されているように、サービス品質（Ｑ
ｏＳ）保証をした最適ＩＰネットワーク設計は、研究上
の既知の重要な問題である。実際、インターネットの商
用利用及びビジネスのインターネットに対する依存の急
増のために、ＩＰネットワークは非常に重要な使命を担
うように変質してきており、今日のＩＰネットワークに
おける“最大の努力”によるサービスという方針はもは
や適切ではない。本発明は、例えばＶＰＮ等のその種の
ネットワークに対する帯域及び他のＱｏＳを提供するＩ
Ｐネットワークの設計に係る方法論を提供する。例え
ば、ネットワークの接続性及びトラフィックに係る要求
が与えられると、本発明に係る設計手続きは、ネットワ
ークトポロジー、及び、当該ネットワークにおける全て
のルータが例えばPacketStarＩＰスイッチのようにＷＦ
Ｑ／ＬＱＤ機能を有している場合に前記要求を充足す
る、対応するリンク容量を生成する。同様のことが、Ｆ
ＩＦＯ／ＲＥＤ方式を用いる旧来のルータを用いた場合
に係る第二の設計においてもなされる。その後、ネット
ワークコストの定量的な削減量の観点から、比較がなさ
れる。この比較を実現するために、ＦＩＦＯスケジュー
リングをＲＥＤと共に用いた場合のＴＣＰスループット
性能に係るモデルが使用される。上述の双方の場合にお
いて、開放最短経路第一（ＯＳＰＦ）ルーティングプロ
トコルによって課せられる制限が考慮される。さらに、
本発明は、従来技術に係るルータネットワークを、旧来
のルータをＷＦＱ／ＬＱＤルータに置換することによっ
て性能保証を有するネットワークに転換するためのルー
タ配置問題も取り扱う。詳細に述べれば、本発明に係る
方法は、ネットワークコストを最大限削減する目的でＷ
ＦＱ／ＬＱＤルータが導入されるべき、ネットワーク内
の戦略的位置を識別する。

【００１１】図１は、本発明に従ったＩＰネットワーク
設計システムの実施例を示すブロック図である。ＩＰネ
ットワーク設計システム１０は、それ自体、複数個の、
互いに相互に接続された機能プロセッサ、すなわち、ル
ーティングプロセッサ１２、ルーティングプロセッサ１
２に機能的に接続されたワーストケース必要リンク容量
プロセッサ１４、ワーストケース必要リンク容量プロセ
ッサ１４に機能的に接続された最良リンク容量設計プロ
セッサ１６、ワーストケース必要リンク容量プロセッサ
１４に機能的に接続されたネットワークトポロジー最適
化プロセッサ１８、及び、最良リンク容量プロセッサ１
６に機能的に接続されたルータ置換プロセッサ２０、を
有している。図１に示された機能プロセッサ１２から２
０は、それぞれ専用の処理デバイス（例えば、ＣＰＵ及
び関連するメモリ）によってインプリメントされること
も可能であり、また、集合的に単一あるいは複数個の処
理デバイスによってインプリメントされることも可能で
ある。すなわち、本発明に係るＩＰネットワーク設計シ
ステム１０は、単一の処理デバイスあるいは複数個の処
理デバイスのいずれによってもインプリメント可能であ
る。

【００１２】ＩＰネットワーク設計システム１０への入
力及び関連する方法論として、すなわち、ストアされた
データ信号の形態あるいは処理デバイスへの設計システ
ムユーザによる入力で、バックボーンネットワークの初
期トポロジーが、グラフＧ＝（Ｖ，Ｅ）の形態で入力さ
れる。ここで、Ｖは存在点（ＰＯＰすなわちルータが位
置する点）に対応するノードの組であり、ＥはＰＯＰ間
の直接接続を実現するリンクの組である。以下に説明さ
れているように、初期ネットワークトポロジーは、ネッ
トワークトポロジー最適化プロセッサ１８によって与え
られることも可能である。さらに、システムへの入力と
して、マイレージベクトル→Ｌ＝［Ｌ₁，Ｌ₂，．．．，
Ｌ_|E|］が与えられる。ここで、Ｌ_lは、Ｅに属するリン
クｌの実際の長さである。さらに、ポイント−ツー−ポ
イントＩＰトラフィック要求の組も設計システム１０へ
供給される。ここで、各々のＩＰフロー要求ｉは、次式
にて表わされるｆ_iによって与えられる。ｆ_i＝（ｓ_i，ｔ_i，ａ_i，ｎ_i，ｄ_i，＿ｒ_i）ここで、ｓ_i及びｔ_iは、それぞれＶ内のソース及びデス
ティネーションノードであり、ａ_iはトランスポートプ
ロトコルタイプ（ＴＣＰあるいはＵＤＰ（データグラム
使用プロトコル））、ｎ_iは当該フロー中におけるＴＣ
ＰあるいはＵＤＰ接続の個数、ｄ_iは当該フローが双方
向であると仮定した場合の最小スループット要求の総
数、及び、＿ｒ_iはソース側顧客サイトからｓ_iへのアク
セスリンク速度とデスティネーション側顧客からｔ_iへ
のアクセスリンク速度とのうちの最小値である。ここ
で、Ｆが全てのｆ_iを含む組とし、Ｆ₁を、あるルーティ
ングアルゴリズムＲに従ってリンク１を通過するように
ルーティングされたＦの要素からなるサブセットとす
る。選択されたルーティングアルゴリズムＲは、上述さ
れた入力に基づいて、ルーティングプロセッサ１２（図
１）によって実行される。ルーティングプロセッサ１２
の出力（図１において参照符号Ａによって示されている
もの）は、要求フロー及びネットワークトポロジーの関
数としてのルーティング情報、すなわち、各々のリンク
上に見出されるフロー（トラフィック）つまり各リンク
を通過するｆ_iである。

【００１３】本発明に係る設計システムは、標準的なＯ
ＳＰＦプロトコルにおいて用いられているものと同様の
最短経路ルーティングにフォーカスしている。最短経路
は、Ｅにおける各々のリンクｌに係る与えられたリンク
長ｌ_lに基づいて計算される。ここで、→ｌ＝［ｌ₁，ｌ
₂，．．．，ｌ_|E|］をこれらのリンク長より構成される
ベクトルとする。タイブレーク方式が用いられ、あらゆ
るソースとデスティネーションとの間には単一のルート
が存在する、ということを仮定する。リンクｌの容量を
Ｃ_lとし、ネットワーク全体において用いられる基幹回
線の大きさ（すなわち容量）が単一の値であるという仮
定の下に、Ｃ_lが基幹回線容量（例えば、ＤＳ３、ＯＣ
３等）によって表現されるとする。さらに、→Ｃ＝［Ｃ
₁，Ｃ₂，．．．，Ｃ_|E|］がリンク容量ベクトルを表わ
すとする。

【００１４】一般に、ネットワーク設計システム１０及
びその関連する方法は、なかんずく、以下の容量割り当
て問題を取り扱う。Ｆによって与えられるスループッ
ト要求が充足され、その一方で総ネットワークコストを
最小化する、必要とされる容量ベクトル→Ｃを見出すこ
と。ここで、Ｅにおけるリンクのサブセットに対してゼ
ロ容量を割り当てることにより、Ｇのトポロジーが、接
続性を低減することによって実効的に変更されることが
可能であり、その結果、要求のルーティングに影響を及
ぼす。後に議論されるように、本発明に係るＩＰネット
ワーク設計方法は、トポロジー最適化も含んでいる。

【００１５】図２に示されているように、本発明に係る
システムにおいて用いられる一般的な設計アルゴリズム
２００の一実施例は、次のようなものである。まず、各
々のリンクにおけるトラフィックミックスＦ_lが（ルー
ティングプロセッサ１２によって）、（最適化プロセッ
サ１８から与えられる）Ｇのサブグラフである初期ネッ
トワークトポロジーＧ_s、ルーティングアルゴリズム
Ｒ、リンク長ベクトル→ｌ、及びＩＰ要求の組Ｆに基づ
いて計算される（ステップ２０２）。次に、Ｆｌ内の帯
域要求を充足するために必要とされる各々のリンクの容
量が、（必要リンク容量プロセッサ１４及び１６によっ
て）ネットワーク内のルータのタイプ、混雑シナリオに
係る相異なった仮定、そしてある場合にはＴＣＰ要求の
エンド−ツー−エンド遅延に基づいて計算される（ステ
ップ２０４）。その後、本発明に係る設計システムは、
（最適化プロセッサ１８によって）最終的なネットワー
ク設計が得られたか否かを決定する（ステップ２０
６）。得られていない場合には、ステップ２０８におい
て、ネットワークトポロジーに対して（最適化プロセッ
サ１８による）摂動が加えられ、ステップ２０２及び２
０４に従って新たなネットワークコストが評価される。
この設計反復は、最終的なネットワーク設計が得られる
まで反復される。最終設計の結果は、（ステップ２１０
において）、例えば当該設計システムのユーザに対して
表示される情報の形態で出力される。この出力結果に
は、（１）ベクトル→Ｃ、（２）各々のトラフィックフ
ローｆ_iに係るルート、及び、（３）対応するネットワ
ークコスト、が含まれる。

【００１６】本発明に係る方法の重要な機能の一つは、
同種の場合、すなわち、従来技術に係るＦＩＦＯ／ＲＥ
ＤルータあるいはＷＦＱ／ＬＱＤルータのいずれかしか
含まないようなネットワークと、異種の場合、すなわち
双方のルータタイプの混合の場合との双方が適応させら
れ得る、という点である。さらに、本発明に係る方法
は、旧来のＦＩＦＯ／ＲＥＤルータネットワークへのＷ
ＦＱ／ＬＱＤルータの最適配置を見出すためのコアエン
ジンとしても機能する。

【００１７】本発明の主要な側面への参照を容易にする
目的で、以下の記述はいくつかの節に分割される。節
１．０においては、あらゆる与えられたＴＣＰ／ＵＤＰ
スループット要求を充足する目的で必要とされるリンク
容量の本発明に従った推定が説明される。この際、ワー
ストケースリンク容量設計要求プロセッサ１４及び最良
リンク容量設計プロセッサ１６が用いられる。ネットワ
ークトポロジー最適化プロセッサ１８によって実行され
る本発明に従ったネットワークトポロジー最適化は、節
２．０で記述される。節３．０においては、ルータ置換
プロセッサ２０によって計算される本発明に従った異種
ルータネットワークにおけるＷＦＱ／ＬＱＤルータの最
適配置が説明される。ＩＰネットワーク設計事例が節
４．０において与えられる。節５．０は、節１．０を参
照して、ＦＩＦＯ／ＲＥＤの下でのスループット割り当
ての説明が提供される。節６．０は、節３．０で説明さ
れた本発明に係るルータ配置実施例を参照して、ＮＰハ
ードネスの説明がなされる。加えて、参照をより容易に
する目的で、それぞれの節はさらに小項目に分割されて
いる。

【００１８】本発明に係る方法論の一つの注目点は、Ｔ
ＣＰがプライマリトランスポートプロトコルとして用い
られるＩＰベースのＶＰＮに関して帯域保証を行なうこ
とであるので、本発明は、ネットワーク内のリンクを介
してルーティングされるＴＣＰ接続群の各々に係る与え
られた要求の組を保証するために、当該リンクがどのく
らいの容量を有する必要があるかを決定する。通常、接
続の各群は相異なったＶＰＮに属していて、そのＶＰＮ
のポイント−ツー−ポイント要求のうちの一つを表わし
ている。この問題に対する回答は、特に当該ネットワー
クにおけるルータにおいて用いられるパケットスケジュ
ーリング及びバッファ管理戦略に依存する。今日のイン
ターネットにおいて最もポピュラーなルータは、パケッ
トドロップポリシーとしてＲＥＤを用いるＦＩＦＯスケ
ジューリングを使用している。しかしながら、PacketSt
arＩＰスイッチなどの先進的な次世代ルータは、公平性
を有してＶＰＮレベルで帯域保証を実現し、フロー（す
なわち接続）レベルで分離特性を実現する目的で、最長
キュードロップ（ＬＱＤ）ポリシーを用いるＷＦＱスケ
ジューラを利用する。以下に明らかにされるように、Ｒ
ＥＤと組み合わせられた従来技術に係るＦＩＦＯは、Ｌ
ＱＤと組み合わせられたＷＦＱ（ＷＦＱ／ＬＱＤ）より
もより大きなリンク容量を有するように設計されていな
い限り、帯域保証を実現することは通常不可能である。

【００１９】リンク容量プロセッサ１４、１６は、要求
されるフローに係る要求、選択されたスケジューリング
及びバッファ方式が与えられると、回線容量要求を計算
する。以下に、ＦＩＦＯ／ＲＥＤ方式を用いることによ
って問題となる設計面での考慮事項が、リンク容量設計
プロセッサ１４、１６によってインプリメントされるこ
れら設計問題を処理する方法論と共に議論される。その
後、ＷＦＱ／ＬＱＤ方式に係る設計上の考慮事項が議論
される。この際、それらに係る必要リンク容量は、プロ
セッサ１４あるいは１６のいずれかによって計算され
る。最後に、本発明に従ったリンク容量設計方法のいく
つかの実施例が詳細に説明される。

【００２０】１．１ランダム早期検出法を用いるファ
ーストイン・ファーストアウト（ＦＩＦＯ／ＲＥＤ）容量ｃ_l ^FIFOを有するボトルネックリンクｌを介してル
ーティングされるＴＣＰ接続の組Ｆ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, pp6
7-82(1997年7月)による結果に基づいて、Ｆ_lに属するあ
らゆる与えられた接続ｉに関して、リンク容量の共有分
が、

【数５】によって与えられる。ここで、τ_i及びｈ_iは、それぞ
れ、接続ｉの経路におけるラウンドトリップ遅延（ＲＴ
Ｄ）及び混雑したリンクの個数である。混雑したリンク
とは、そのキューにおいてパケットロスが生ずるほどの
高い負荷を有するリンクを表わしており、それに対して
混雑していないリンクとは、パケットロスが発生しない
リンクを表わしている。言い換えれば、リンク容量は、
競合するＴＣＰ接続の間で、式（１）によって与えられ
る重みに比例して共有される。この重みは、ラウンドト
リップ時間τ及びｈの２乗根との積の逆数である。ここ
で、以下の、ＦＩＦＯ／ＲＥＤとＷＦＱ／ＬＱＤとの間
の基本的な差異に留意されたい。双方の場合とも、あら
ゆる接続のリンク共有は、その重みに比例する。ＷＦＱ
／ＬＱＤの場合には、以下に説明されているように、接
続に係る重みはネットワークオペレータの制御下にあ
り、任意に設定されうる。しかしながら、ＦＩＦＯ／Ｒ
ＥＤにおいては、重みは接続経路の特徴、つまりτ及び
ｈによって決定付けられており、ほとんど制御不能であ
る。

【００２１】与えられたＶＰＮにおける各々のポイント
−ツー−ポイント要求ｉは、現実には複数個のＴＣＰ接
続に対応しており、それら各々が同一の重みｗ_iを有し
ている。なぜなら、それら全体が、τ_i及びｈ_iによって
特徴付けられる同一の最短経路を実現しているからであ
る。ここで、ｎ_iを、Ｆ_lに属する要求ｉを構成するＴＣ
Ｐ接続の個数とする。式（１）より、要求ｉによって獲
得されるリンク共有は、

【数６】によって与えられる。与えられた要求ｉ内のＴＣＰ接続
の個数ｎ_iが実際の要求の値ｄ_iに比例すると仮定する
と、式（２）は、

【数７】

【数８】となる。

【００２２】要求を充足するリンク容量ｃ_l ^FIFOを有す
るためには、∀ｉ∈Ｆ_lなるｉに関して、ｒ^l _i≧ｄ_iが必
要である。このことは、全ての要求を充足する最小リン
ク容量が

【数９】によって与えられることを意味している。この際、ｗ_i
（ｉ∈Ｆ_l）は、式（４）によって与えられる。リンク
容量ｃ_l ^FIFOは、明らかに全ての要求の総和以上であ
る。

【数１０】さらに、ｉ^*を式（５）において最大値を取る要求とす
るとき、式（３）及び式（５）を組み合わせることによ
って、

【数１１】を得る。この際、ｒ^l _i*＝ｄ_i*であり、ｒ^l _i≧ｄ_i（∀ｉ
∈Ｆ_l）である。言い換えれば、ｉ*は、その必要量が正
確に割り当てられた要求であり、他の全ての要求に対し
てはその必要とされる以上の帯域が割り当てられる。

【００２３】式（５）に従って必要とされるリンク容量
を計算するために用いられるパラメータは、ｄ_i、τ_i及
びｈ_i（ｉ∈Ｆ_l）である。要求ｄ_iは与えられ、遅延τ_i
（伝播遅延）の固定部分は最短経路から決定されて広い
範囲にわたって主要部分であることが期待されるため
（キューに係る遅延成分の平均を加えることも可能であ
る）、第三のパラメータｈ_iの値のみが自明ではない。

【００２４】ｈ_iの決定の問題を取り扱うために、以下
で、いくつかの定義を導入する。^-ｈ _iを、接続ｉの最短
経路に対応するホップの数とする。明らかに、混雑した
ホップの数ｈ_iは、ｈ_i≦^-ｈ_iを（∀ｉ∈Ｆ_l）満たす。
ここで、Ｉ＝［Ｉ₁、I₂、．．．、Ｉ_|F|］を、ネットワ
ーク内の全てのリンクの混雑状況を表わすベクトルとす
る。この際、Ｉ_jは、リンクｊのインジケータであり、
リンクｊが混雑している場合には１、それ以外の場合は
０である。さらに、Ｈ＝［ｈ₁、ｈ₂、．．．、ｈ_|F|］
を、各々のエンド−ツー−エンド要求の経路における混
雑したリンクの個数よりなるベクトルとする。すなわ
ち、

【数１２】であり、ｐ（ｉ）は、要求ｉが横断するリンクシーケン
ス（経路）を表わしている。また、Ｈ_l＝［ｈ_i1、
ｈ_i2、．．．、ｈ_|Fl|］を、要求ｉ（ｉ∈Ｆ_l）に対す
るｈ_iよりなるベクトルとする。

【００２５】ベクトルＩ及びＨは、各々、＿Ｉ＝｛０、
１｝^|E|及び＿Ｈ＝｛０、１、．．．^-ｈ_i｝×．．．×
｛０、１、．．．、^-ｈ_|F|｝よりなる組に属する値を取
る。ここで、ｇを前述されているように定義された＿Ｉ
と＿Ｈとの間のマッピングとする。

【数１３】組_{_}Ｉは、ｇによって、＿Ｈ_fとして表わされる_{_}Ｈのサ
ブセットにマッピングされ、この_{_}Ｈ_fは、_{_} Ｈ_f＝｛Ｈ∈_{_}Ｈ、∃Ｉ∈＿Ｉ s.t. Ｈ＝ｇ（Ｉ）｝のように表現される、＿Ｈに属する利用可能な要素より
なる組である。言い換えれば、Ｈ∈＿Ｈは、必ずしも全
てが利用可能ではない。

【００２６】｛Ｈ｝をＨ_l（ｌ∈Ｅ）の組とする。要求
ｉに対応するｈ_iの要素は、ｌ∈ｐ（ｉ）を満たす全て
のベクトルＨ_l、すなわち、接続ｉの経路における全て
のリンク、に現われる。同一の要求に係る全ての要素が
同一である場合には、｛Ｈ｝はコンシステントであると
いう。｛Ｈ｝がコンシステントである場合には、ｈ_iに
係るベクトルＨ（ここで、ｈ_iは全てのＨ_l（ｌ∈ｐ
（ｉ））における要求ｉの共通要素である）は、｛Ｈ｝
の共通ベクトルであると呼称される。さらに、｛Ｈ｝
は、（ｉ）それがコンシステントであって、かつ、（ｉ
ｉ）その共通ベクトルが利用可能である場合に、利用可
能であるといわれる。

【００２７】式（５）におけるリンク容量の計算は、要
求ｉがリンクｌにおけるシェアｒ^l _iを（その経路に沿っ
た他のリンクにおけるシェアがｒ^l _iより小さければ）そ
のシェアを達成しない、という、ネットワーク全体のシ
ナリオにおける複数個のボトルネックの効果を考慮して
いない。それゆえ、ｒ^l _iと要求ｉの経路における他のリ
ンクの最小シェアとの差異（これは、ｄ_iより大きい。
なぜなら、ｐ（ｉ）内の全てのリンクにおいてｒ^l _i≧ｄ
_iであるからである。）が、その要求に影響を与えるこ
となく、ｃ_l ^FIFOから差し引かれることが可能である。
そうでない場合には、この余剰容量は、リンクｌを通過
する、その必要容量が既に満たされた貪欲な要求によっ
て取り込まれる。この意味では、式（５）におけるｃ_l
^FIFOを、その必要とされるリンク容量の上限とみなすこ
とができ、それを^-ｃ_l ^FIFOと書き表わすことにすると、

【数１４】のように書き直すことができる。ここで、重みｗ_jの、
従って、^-ｃ_l ^FIFOの、Ｈ_lの値に関する依存性を強調し
たい。さらに、前述された複数ボトルネック効果を考慮
することによって、必要とされるリンク容量の下限＿ｃ
_l ^FIFOが以下のように求められる。^-ｃ_l ^FIFOに基づい
て、要求ｉのシェアが、

【数１５】のように得られる。そして、経路に沿った最小シェアが

【数１６】のように計算される。ここで、＿ｒ_i≧ｄ_iは、例えばネ
ットワークへのＶＰＮのアクセスリンク速度に起因す
る、発生しうるあらゆる制限を表わす適切な値にセット
される。式（７）の最小値がｒ^l* _i（Ｈ_l*）に対応する
場合には、リンクｌ^*が要求ｉに関するボトルネックリ
ンクである。最終的に、＿ｃ_l ^FIFOが

【数１７】のように求められる。これは、Ｈ_lの関数であるだけで
はなく、｛Ｈ｝のサブセットであるＨ_l'（∀ｌ’∈ｐ
（ｉ））の関数である。＿ｃ_l ^FIFOが下限である理由
は、あらゆる与えられた可能な｛Ｈ｝に関して、ある要
求のボトルネックをシフトすることにつながる、ある種
の要求アイドリングシナリオが存在するからである。こ
のボトルネックシフトによって、アクティブな要求から
の必要事項を充足させるために＿ｃ_l ^FIFOより大きな容
量が必要とされる。

【００２８】これまで、ネットワーク内の各々のリンク
ｌに係るＨ_lの関数として、容量の上限及び下限である^-
ｃ_l ^FIFO及び＿ｃ_l ^FIFOについて議論された。現実のＨ_l
がどのようなものであるかがわかっていないため、以下
の境界が決定される。

【数１８】

【数１９】ここで、各々の利用可能なＨ∈＿Ｈ_fに関して、対応す
るＨ_lを形成し、^-ｃ_l ^FIFO及び＿ｃ_l ^FIFO（｛Ｈ｝）を計
算する。必要とされる容量ｃ_l ^FIFOの正確な値は＿ｃ_l
^FIFO（Ｈ^min）≦ｃ_l ^FIFO≦^-ｃ_l ^FIFO（Ｈ^max）を満た
す。よって、これらの境界は、Ｈ∈＿Ｈ_fの実際の値と
は独立にリンク容量の上限及び下限を与える。これらの
境界は計算可能であるが、現実的には、すなわち、より
計算を容易にする目的で、境界が次のように与えられ
る。

【数２０】

【数２１】ここで、最大及び最小は、可能性にかかわらずＨの全て
の値に関して考慮する。この際、Ｈ_l ^worstが、Ｈ_lを式
（６）における各々のｉに関してｈ_i＝^-ｈ_iでありかつ
ｊ≠ｉに対してｈ_j＝１（各々の要求ｉ∈Ｆ_lが少なくと
もその経路中の混雑したリンクとしてリンクｌを有して
いる）であるように選択することによって得られること
は明らかである。同様に、Ｈ_l ^bestが、Ｈ_lを式（６）に
おける各々のｉに関してｈ_i＝１でありかつｊ≠ｉに対
してｈ_j＝^-ｈ_jであるように選択することによって得ら
れる。

【００２９】しかしながら、定義によって、以下の不等
式が存在する。

【数２２】ここで、^-ｃ_l ^FIFO（Ｈ^min）は、式（９）において最大
の代わりに最小を取ることによって規定される。それゆ
え、^-ｃ_l ^FIFO（Ｈ^worst）は上限として用いられる。^-ｃ
_l ^FIFO（Ｈ^best）は下限の良好な候補である。なぜな
ら、^-ｃ_l ^FIFO（Ｈ^be ^st）及び_ｃ_l ^FIFO（Ｈ^min）は双方
とも^-ｃ_l ^FIFO（Ｈ^min）より小さく、節５．０で示され
ているケーススタディにおいては、^-ｃ_l ^FIFO（Ｈ^best）
≦＿ｃ_l ^FIFO（｛Ｈ｝）であることが、ＨがＨ^hop及びＨ
^oneに等しいこと（それぞれ、ｈ_i＝^-ｈ _i、及びｈ_i＝
１、ｉ＝１，２，．．．，｜Ｆ｜である）に対応する
｛Ｈ｝の二つの代表的な値に関して示されるからであ
る。Ｈ^oneは、各々の要求が単一の混雑したリンクをそ
の経路上に有していることに対応し、可能ではない。Ｈ
^hopは可能であって、全ての要求がアクティブかつ貪欲
であり、各々のリンクが少なくとも一つの１ｈｏｐ要求
を担っている場合に対応する。これらの方法論に係る実
施例は、以下、節１．４において説明される。

【００３０】次に、以下の議論においては、本発明に係
るシステム１０を用いる設計者が、スケジューリング／
バッファリング方式としてＷＦＱ／ＬＱＤを選択したと
仮定する。PacketStarＩＰスイッチは、３層階層構造Ｗ
ＦＱスケジューラを用いることによって出力リンク毎に
６４０００フローキューをサポートすることが可能であ
ることが知られている（例えば、V.P.Kumar, T.V.Laksh
man, and D.Stiliadisによる“ベストエフォート方式を
越えて。明日のインターネットにおける差動的サービス
に係るルータアーキテクチャ”という表題の論文(IEEE
Comm. Magazine, Vol.36, No.5, pp.152-164(1998.5))
を参照）。スケジューラ階層の最上位おいては、相異な
ったＶＰＮ間でリンク容量が分割されており、各々のＶ
ＰＮ内ではそれがアプリケーション分類（例えば、ＦＴ
Ｐ様のＴＣＰフロー、Ｔｅｌｎｅｔ様のＴＣＰフロー、
ＵＤＰフロー等）に基づいて分割され、最後に、各々の
アプリケーション分類の帯域が、さらに、その分類に属
するフロー間で分割される（各々の分類内でのフローレ
ベルには通常等しい重みが与えられるが、異なるように
することも可能である）。

【００３１】バッファリソースを効率的に使用する目的
で、PacketStarＩＰスイッチは、全てのフロー間での共
有バッファプールのソフト分割を利用する。それぞれの
フローは、共有バッファに適切なパケットバックログを
維持することが可能である場合には、その重みに対応す
るリンク容量（リンクシェア）を獲得することが可能で
ある。言い換えれば、ＷＦＱスケジューラは、各々のフ
ローに対してパケット伝送目的で当該リンクにアクセス
する公平な機会を提供するが、このことは、当該フロー
が共有バッファへの不適切なアクセス制御のために適切
なパケットバックログを維持できない場合には、リンク
容量の公平な共有を必ずしも意味しない。この問題は、
例えば、ＴＣＰのようなパケットロスに敏感なトラフィ
ックが、未制御ＵＤＰなどのパケットロスには敏感でな
いトラフィックと競合している場合、あるいは、相異な
ったラウンドトリップ遅延（ＲＴＤ）を有するＴＣＰ接
続がリンク容量に関して競合している場合、に発生しう
る。最初の状況の場合には、ＴＣＰスループットがパケ
ットロスに敏感であるために（ＴＣＰソースは、パケッ
トロスが検出されると、そのウィンドウを小さくするこ
とによってレートを低減する）、パケットロス状況に応
じてそのレートを適応させないアプリケーション（非適
応ＵＤＰソースあるいは標準的なＴＣＰの振る舞いに従
わない過激なＴＣＰソースのいずれかである）は、共有
バッファプールから不公平なシェアを獲得してしまうこ
とが可能であるからである。相異なったＲＴＤを有する
ＴＣＰ接続という第二のシナリオは公知の問題であり、
例えば、S.Floyd and V.Jacobsonによる“パケット交換
ゲートウェイにおけるトラフィックフェーズ効果”とい
う表題の論文(Internetworking。Research and Experie
nce, Vol.3, No.3, pp.115-156(1992.9))；T.V.Lakshma
n 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(1
998.3))を参照）。

【００３４】結果として、スケジューラは重み付けを行
ない、公称バッファ割り当てが、与えられたリンクｌに
おいて、ポイント−ツー−ポイントＶＰＮ要求ｄ_iの組
を充足するために必要とされるリンク容量が単に要求の
総和に等しくなるように、すなわち

【数２３】であるように設定される。ここで、Ｆ_lはリンクｌを介
してルーティングされる全ＶＰＮ要求よりなる組であ
る。しかしながら、ＷＦＱ／ＬＱＤ機能を有するルータ
と比較して、ルータがＦＩＦＯ／ＲＥＤのみをサポート
する場合には、同一の要求を満たすためにより大きな容
量が必要とされる。

【００３５】１．３ＴＣＰとＵＤＰの双方による容量
要求これまでは、ＴＣＰトラフィックのみが必要とされるリ
ンク容量を計算するために考慮されてきており、ＦＩＦ
Ｏ／ＲＥＤを利用する場合に式（１１）及び（１２）、
ＷＦＱ／ＬＱＤの場合に式（１３）によってそれぞれ境
界が与えられてきた。フロー毎キューイングによって分
離が実現されるため、ＷＦＱ／ＬＱＤの場合に関する総
必要容量を求めるためには、ＵＤＰ要求を追加すればよ
い。ここでは、過激なＵＤＰトラフィックがその要求を
越える可能性があまり無いと仮定して、ＦＩＦＯ／ＲＥ
Ｄの場合にも同一の手法を適用する。よって、ＷＦＱ／
ＬＱＤの場合の必要リンク量は

【数２４】によって与えられ、ＦＩＦＯ／ＲＥＤの場合には、その
上限が

【数２５】その下限が

【数２６】によって与えられる。さらに、Ｈ^hopとＨ^oneの二つの特
別な場合には、上限及び下限はそれぞれ

【数２７】

【数２８】

【数２９】

【数３０】によって与えられる。ここで、ｄ_i ^UDPは、要求ｉに係る
ＵＤＰスループット要求事項を表わしており、シーリン
グ関数┌．┐は、リンク容量が離散的（トランク回線単
位）であることを説明するために導入された。

【００３６】１．４リンク容量計算実施例以上に導出されたような式が与えられたので、以下は、
本発明に係る方法の種々の実施例を、本発明に係るネッ
トワーク設計システムのユーザによって選択された特定
の設計基準に関連する必要リンク容量の計算に関連して
示す。以下に記述されているように、以下の方法は、ワ
ーストケースリンク容量設計要求プロセッサ１４及び／
あるいは最良リンク容量設計プロセッサ１６（図１）に
よって実行される。

【００３７】図３は、本発明に従って、ＦＩＦＯ／ＲＥ
Ｄベースのワーストケース必要リンク容量を計算する方
法３００である。ここで、ｃという文字はＴＣＰトラフ
ィックのみを考慮するリンク容量を表わす一方、ＣはＴ
ＣＰとＵＤＰ双方のトラフィックを考慮するリンク容量
を表わす。従って、式における項からも明らかなよう
に、第一付加項はＴＤＰトラフィックに係る必要リンク
容量であり、第二付加項はＵＤＰトラフィックに係る必
要リンク容量である。さらに、この種の計算は、ルーテ
ィングプロセッサ１２及びユーザからの入力に基づい
て、ワーストケース必要リンク容量プロセッサ１４（図
１）によって実行される。従って、この設計方法は、シ
ステム１０のユーザに、入力された特定の使用に基づい
て、必要とされるリンク容量の計算をリンク毎に提供す
る。

【００３８】ステップ３０２においては、プロセッサ１
４は、ルーティングプロセッサ及びユーザから入力パラ
メータを受け取る。プロセッサ１２からの入力には、接
続ｉに係るポイント−ツー−ポイントＶＰＮ要求の組で
あるｄ_i及びラウンドトリップ遅延τ_iが含まれる。もち
ろん、これらの入力は、最初にユーザによって規定され
たものである。加えて、ユーザは、スケジューリング／
バッファリング方式（この例ではＦＩＦＯ／ＲＥＤであ
る）、及び混雑オプションＨ^O（例えば、Ｈ^w ^orst、Ｈ
^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に係る式は、既に説明された
式（１５）、（１７）、（１９）にそれぞれ等しく、式
（６）の右辺がシーリング関数の第一項として挿入され
たものである。最後に、現在のトポロジーの各々のリン
クに対する必要リンク容量（図１において参照符号Ｂに
て示されていたもの）が、例えばプロセッサ１４に係る
ディスプレイを介してユーザに出力される。

【００４０】図４は、本発明に従ったＦＩＦＯ／ＲＥＤ
ベースの最良リンク容量を計算する方法４００を示した
流れ図である。それぞれの式における項から明らかなよ
うに、第一付加項はＴＤＰトラフィックに係る必要リン
ク容量であり、第二付加項はＵＤＰトラフィックに係る
必要リンク容量である。さらに、これらの計算は、ルー
ティングプロセッサ１２、ユーザ及びワーストケース必
要リンク容量プロセッサ１４からの入力に基づいて、最
良リンク容量設計プロセッサ１４によって実行される
（なぜなら、シェアｒｉが^-ｃ_l ^FIFOの関数だからであ
る）。従って、この設計方法により、システム１０のユ
ーザが、入力された特定の使用に基づいて、必要とされ
るリンク容量をリンク毎に計算することが可能になる。

【００４１】まず、ステップ４０２において、プロセッ
サ１６はプロセッサ１４と同様の入力、すなわち、ネッ
トワークトポロジー、ソース−デスティネーション要
求、ラウンドトリップ遅延及びユーザによってなされた
混雑選択シナリオを受信する。さらに、プロセッサ１４
によって計算された必要リンク容量もプロセッサ１６に
供給される。ユーザは、本発明に従って、オプションＨ
^O（例えば、Ｈ^best、Ｈ^h ^op、Ｈ^one）のみを規定する必
要がある、ということに留意されたい。なぜなら、それ
らに対応するｈ_iの値はプロセッサ１６に係るメモリ内
にストアされているからである。前述されているよう
に、Ｈ^bestは、式（６）における各々のｉに対して、ｈ
_i＝１かつｊ≠ｉに関してｈ_j＝^-ｈ_jという条件の下にＨ
_lを選択することによって得られる。さらに、Ｈ^hop及び
Ｈ^oneが、それぞれｈ_i＝^-ｈ_i及びｈ_i＝１（ｉ＝１，
２，．．．，｜Ｆ｜）に対応するものとして、ステップ
４０４で規定される。

【００４２】次に、ユーザによって選択されたオプショ
ンに基づいて、必要とされる最良リンク容量が計算され
る。すなわち、現在のネットワークトポロジーにおける
各々のリンクのリンク容量が、要求、遅延、スケジュー
リング／バッファリング方式及び選択された混雑オプシ
ョンに基づいて計算される。図４のステップ４０４にお
いて示されたＨ^best、Ｈ^hop、Ｈ^oneに係る式は、前述さ
れた式（１６）、（１８）、（２０）と同一のものであ
り、式（６）の右辺が式（１６）のシーリング関数の第
一項として挿入され、式（８）の右辺が式（１８）、
（２０）のシーリング関数の第一項として挿入されたも
のであることに留意されたい。最後に、現在のトポロジ
ーにおける各々のリンクに係る必要リンク容量（図１に
おいて参照符号Ｄによって示されていたもの）が、例え
ばディスプレイを介してユーザに出力される。単一の入
力デバイス及び単一の出力デバイスが、本発明に従った
システム１０に係る全てのユーザ選択可能入力及び出力
に関して用いられることに留意されたい。従って、プロ
セッサ１６の出力をプロセッサ１４の出力と比較して以
下の点に注目すべきである。ネットワークトポロジーは
変化していない。しかしながら、あるリンクの容量は、
ネットワーク全体での複数ボトルネック効果を考慮し
て、低減されている場合がある。

【００４３】図５は、本発明に従った、ＷＦＱ／ＬＱＤ
ベースのリンク容量Ｃ_l ^WFQを計算する方法５００を示し
ている。この実施例においては、ユーザがＷＦＱ／ＬＱ
Ｄスケジューリング／バッファリング方式を選択するこ
とが仮定されている。このため、限界及び混雑オプショ
ンに基づいた計算は不要であり、結果として、各々のリ
ンクｌに関してＴＣＰ／ＵＤＰトラフィックに係るＶＰ
Ｎ要求ｄ_iのみが、必要リンク容量を計算するための入
力として必要とされる（ステップ５０２）、ということ
に留意されたい。ＷＦＱ／ＬＱＤ方式においては上限及
び下限を計算する必要がないため、プロセッサ１４ある
いはプロセッサ１６のいずれかが必要リンク容量を計算
するために用いられるだけであることにも留意された
い。よって、ステップ５０４において、スケジューラは
重み付けを行ない、与えられたリンクｌに対する公称バ
ッファ割り当てが、ポイント−ツー−ポイントＶＰＮ要
求ｄ _iの組を満たすために必要とされるリンク容量が、
ステップ５０６に式で示されているように、単に要求の
総和に等しいものであるように設定される。ここで、Ｆ
_lは、リンクｌを介してルーティングされる全てのＶＰ
Ｎ要求の組である（すなわち、それらＶＰＮ要求は、そ
の最短経路にリンクｌを有している）。ステップ５０８
においては、リンク容量がユーザに出力される（例えば
ディスプレイを介して）。

【００４４】２．０ネットワークトポロジー最適化考慮している容量割り当て問題に関しては、ゼロ容量を
割り当てることによって、元のネットワークトポロジー
Ｇ内におけるいくつかのリンクを除去するという柔軟性
がある。このリンク除去に係る動機付けは、ネットワー
ク全体の費用と低減するためにいくつかの使用頻度の低
いネットワークファシリティを排除する、ということで
ある。本発明に係る設計プロセス全体を通じて、ネット
ワーク費用は以下の関数に基づいて計算される。

【数３１】ここで、Ｍ（．，．）及びＴ（．）は、それぞれマイレ
ージ及び終端費用関数である。この費用関数は、簡単の
ために選択されたものであって本発明の理解を容易にす
るためのものであることに留意されたい。費用関数の他
の一般的な形式も、本発明に容易に組み込まれうる。ネ
ットワークトポロジー最適化プロセッサ１８がネットワ
ーク費用を計算することが望ましい。しかしながら、プ
ロセッサ１４あるいは１６が、このことを行なってもよ
い。

【００４５】以下のサブセクションにおいては、ネット
ワークトポロジー最適化に係る二つの実施例とその変形
例が考察される。それらは、リンク増強アプローチとリ
ンクデロードアプローチである。ネットワークトポロジ
ー最適化のプロセスは、ネットワークトポロジー最適化
プロセッサ１８によっても実行される。さらに、システ
ム１０を用いるためにルーティングプロセッサ１２へ最
初に与えられるネットワークトポロジーは、ネットワー
クトポロジー最適化プロセッサ１８によって与えられる
か、あるいはシステム１０のユーザによって与えられる
かのいずれかである。

【００４６】２．１増強最適化図６から９には、本発明に従った増強アプローチを用い
るネットワークトポロジー最適化方法６００が示されて
いる。この増強アプローチにおいては、Ｇの適切なサブ
グラフＧ_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に基づいて、デロードされる候補となるリン
クが識別される。詳細に述べれば、ＦＩＦＯ／ＲＥＤル
ータネットワークの場合には、

【数３２】の場合には、リンクｌはデロードされる候補となる。Ｗ
ＦＱ／ＬＱＤルータネットワークの場合には、対応する
基準は

【数３３】である。候補となるリンクが選択されると、それらは、
それらが担っているトラフィックが再ルーティングされ
る場合の既存のネットワーク設計に対する予想されるイ
ンパクトの大きさに従って順序付けされる（ステップ７
０２）。この目的のために、候補リストが空ではない場
合には（ステップ７０４）、各々の候補リンクを横断す
るフローの要求とホップ数との積の総和が計算される
（ステップ７０８）。次に、ステップ７１０において、
前記積の総和が最小である候補リンクが、ネットワーク
トポロジーから一時的に除去される。動機付けは、ネッ
トワーク費用の急激な変化を回避するために、デロード
プロセスの間のトポロジー／容量擾乱を最小化すること
である。候補リンクが一時的に除去された後、新たなル
ート、容量要求、及びその結果として必要になるネット
ワーク費用が再計算される（ステップ７１２）。リンク
除去がネットワーク費用を低減する場合には、当該リン
クは永久的に除去される（ステップ７１６）。しかしな
がら、リンク除去によってネットワーク費用が低減され
ない場合には、この現時点の候補リンクはトポロジー内
には残存させられるが候補リストからは除去される（ス
テップ７１８）。その後、デロードプロセスは、積の総
和が最小であるリスト内の次の候補リンクに関して（直
前の候補が除去された場合には更新されたトポロジー、
直前の候補が保持された場合には同一のトポロジー、の
いずれかを用いて）反復される（ステップ７０４）。候
補リストが空である場合には、デロードプロセスは完了
している（ステップ７０６）。

【００５４】節２．０において議論されたトポロジー最
適化の種々の変形例がインプリメントされてテストされ
ている。例えば、ストラグラーがルーティングされる際
の相異なった順序付けや増大方法をリンクデロード方法
と組み合わせて用いる方法などが試みられた。すなわ
ち、リンクデロード方法は、単独の最適化方法としても
利用可能であるが、増大方法と共に利用することも可能
である。つまり、リンクデロード方法は、リンク増大方
法の後に実行されうる。その結果得られる性能に関して
は、種々のケーススタディが議論されている節４ｌ：０
に示されている。

【００５５】トポロジー最適化の増大方法においては、
反復の途中で生成されたネットワーク配置の費用は顕わ
には考慮されない。しかしながら、ネットワーク費用の
最小化は、トラフィックパッキングとトポロジー増大を
介して暗黙のうちになされる。このことは、ネットワー
ク費用は、わずかしか利用されない付加リンクを導入す
ることよりも既存のリンクのスペア容量上に小さな要求
をパックすることによってネットワーク費用が低減され
うるという観察結果に基づいている。

【００５６】増大方法において、新たなストラグラーの
要求を満たすためにリンクに付加容量が必要とされる場
合、実際に必要とされる容量は、ＷＦＱ／ＬＱＤルータ
のケースでは、単純加算で直接的に計算されうることに
留意されたい。しかしながら、ＦＩＦＯ／ＲＥＤルータ
ネットワークにおいては、デロード方法が好ましいとさ
れる。なぜなら、節１．０で示された必要リンク容量
は、リンク上のトラフィックの混合が変化するとかなり
大きく変化しうるからである。

【００５７】さらに、最短経路に基づく要求ルーティン
グに関しては、余分な容量を全く有さないリンクと総容
量としてゼロが割り当てられたリンクとの間に微妙な差
異が存在することに留意されたい。この二つの場合にお
ける要求のルーティングは著しく異なっており、区別し
て考えられるべきものである。

【００５８】従って、前述されているネットワークトポ
ロジー最適化のあらゆる実施例が与えられると、最適化
プロセッサ１８の出力（図１において参照符号Ｃが付さ
れたもの）は、ルーティングプロセッサ１２を介して、
ワーストケース必要リンク容量プロセッサ１４に供給さ
れることが望ましいネットワークトポロジーであり、ル
ーティングプロセッサ１２は、前述されているように、
受信したトポロジーが与えられると必要リンク容量を計
算する。その後、図２に関連して説明されているよう
に、そのトポロジーが設計者の基準を満たす最終的なト
ポロジーであるか否かを例えばネットワーク費用あるい
は有効化に係る考察を通じて決定する。最終的なトポロ
ジーではない場合には、最終的なネットワークトポロジ
ーが定式化されるまで、（いずれがインプリメントされ
ている場合においても）最適化プロセスが反復される。

【００５９】３．０ルータ置換従来技術に係るＦＩＦＯ／ＲＥＤルータのみを用いる既
存のＩＰネットワークを考える。そのネットワークが、
単純グラフＧ_s＝（Ｖ’，Ｅ’）によって表現されてい
るとする。ここで、Ｖ’は、ルータの組に対応するノー
ドの組であり、Ｅ’は、ルータを接続しているリンクの
組である。ここで、以下の問題Ｐを考える。最大Ｎ_max
個のＷＦＱ／ＬＱＤルータが与えられてそれぞれがＶ’
内の既存のあらゆるＦＩＦＯ／ＲＥＤルータの一対一置
換に用いられうるとしたとき、ネットワーク費用の削減
が最大となるＦＩＦＯ／ＲＥＤルータの組を見出す。

【００６０】Ｔ^FIFO（Ｃ）及びＴ^WFQ（Ｃ）を、それぞ
れ、容量Ｃのリンクを終端するために必要となるＦＩＦ
Ｏ／ＲＥＤルータ及びＷＦＱ／ＬＱＤルータの終端費用
とする。また、Ｍ（Ｃ，Ｌ）を、用いられているルータ
のタイプにかかわらず、容量Ｃ及び長さＬを有するリン
クのマイレージ費用とする。既存のネットワークにおけ
るＦＩＦＯ／ＲＥＤルータのうちのいくつかをＷＦＱ／
ＬＱＤルータで置換することによって、ネットワーク費
用全体における変化は二つの個別の成分に分割されう
る。第一は、選択されたＦＩＦＯ／ＲＥＤルータをＷＦ
Ｑ／ＬＱＤルータにアップグレードすることに係る費用
である。第二は、従来技術に係るＦＩＦＯ／ＲＥＤスケ
ジューリング／バッファ管理が先進的な次世代ルータに
おけるＷＦＱ／ＬＱＤに置換される場合における、必要
転送容量の低下に伴う費用削減である。この置換プロセ
スに係る費用の追加／削減の詳細を理解するために、本
発明は以下の２ステップのプロセスを提供する。第一
に、選択されたＦＩＦＯ／ＲＥＤルータの組を、置換す
るルータと同一の個数のインターフェース及び終端容量
を有するＷＦＱ／ＬＱＤルータを用いて一つずつ置換す
る。選択されたＦＩＦＯ／ＲＥＤルータｉのこのような
置換にかかる費用をＱ_iで表わす。第二に、ＦＩＦＯ／
ＲＥＤルータｉ及びｊを接続している伝送リンクｌ＝
（ｉ，ｊ）に関して、ｉ及びｊの双方がＷＦＱ／ＬＱＤ
ルータによって置換される場合には、リンクｌの必要容
量は、改善されたパケットスケジューリング及びルータ
バッファ管理によって低減される。結果として、費用削
減は、（ｉ）新たに配置されたＷＦＱ／ＬＱＤルータに
係る余剰なインターフェース／終端容量の“償還”を得
ること、及び（ｉｉ）リンクｌに係るマイレージ費用の
低減、から導き出される。詳細に述べれば、リンクｌ＝
（ｉ，ｊ）の終端ルータｉ及びｊの双方のみをＷＦＱ／
ＬＱＤルータによって置換した場合には、費用削減分Ｓ
_i,jは、

【数３４】によって与えられる。ここで、Ｃ_lＦ^IFOおよびＣ
_l ^WFQは、それぞれＦＩＦＯ／ＲＥＤ及びＷＦＱ／ＬＱＤ
の場合に対応する要求容量である。ここで、Ｓ_i,jはこ
の種の置換から導き出される実際の費用削減量の控えめ
な推定であることに留意されたい。なぜなら、これは、
分離されたリンク毎の基準に基づいた必要容量に係るイ
ンパクトのみを考慮しているに過ぎないからである。Ｗ
ＦＱ／ＬＱＤルータが追加された場合のリンクｌを通過
するフローに係るより厳しい帯域制御のために、ネット
ワークのいずれかでさらなる容量低減が可能である場合
がある。

【００６１】上述された枠組みに基づいて、本発明に従
って、問題Ｐが以下のような混合整数プログラミング
（ＭＩＰ）問題として定式化される。

【数３５】ここで、Ｑ_iは、前述されたように、ルータｉのアップ
グレード費用である。Ｓ_i _,jは式（２２）で定義された
費用削減であり、

【数３６】の場合にはＳ_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, “ＡＭ
ＰＬ−数学プログラミング向けのモデリング言語”(Boy
d & Fraser Publishing Company(1993))に記述されてい
る）及びＣＰＬＥＸ混合整数ソルバー（ＩＬＯＧＩｎ
ｃ．のＣＰＬＥＸ部門より入手可能）が含まれる。３３
３ＭＨｚのＰｅｎｔｉｕｍＩＩＰＣで実行すると、およ
そ１００個のノード及び３００のリンクを有する従来技
術に係るＦＩＦＯ／ＲＥＤネットワークにおけるＷＦＱ
／ＬＱＤルータの最適配置が、数秒のうちに決定され
た。

【００６３】４．０ケーススタディこの節では、本発明に従ったＩＰネットワーク容量割り
当て及び最適ルータ再配置に関するいくつかのケースス
タディ（具体例）の結果が議論される。第一のケースス
タディは、１９９４年末のＮＳＦＮＥＴのトポロジーに
基づいている。図１２は、このトポロジーを示してお
り、本発明に従ったデザインフレームワークにおける完
全トポロジーＧとして用いられたものである。トランク
回線サイズは、ネットワーク全体で２４０にセットされ
ている。図１３は、その要素がこの例で用いられている
ポイント−ツー−ポイントトラフィック要求に対応して
いる行列を示している。トラフィック要求の相対的な大
きさは、メリットネットワーク情報センターサービスに
よる“ＮＳＦＮＥＴバックボーンネットワークに係る統
計報告（１９９４）”という１９９４年の統計値に従っ
て、R.H.Hwangによる“高速ネットワークにおけるルー
ティング”（マサチューセッツ大学（at Amherst）の博
士学位論文（１９９３年５月））によって提案されたス
ケーリング法を用いて設定されている。さらに、各々の
要求の絶対値を、１９９４年からの成長分を反映する目
的でスケールアップしている。ネットワークコスト全体
Ｊが、トランク回線当たりのある任意の終端費用及び長
さ当たりのある任意のマイレージ費用に基づいて計算さ
れる。終端費用及びマイレージ費用は、ＦＩＦＯ／ＲＥ
ＤルータとＷＦＱ／ＬＱＤルータとで同一であると仮定
された。ネットワーク設計においては、前述された種々
のトポロジー最適化戦略及び相異なったネットワーク混
雑仮定が用いられた。

【００６４】４．１同種ルータによる設計まず、ＦＩＦＯ／ＲＥＤルータあるいはＷＦＱ／ＬＱＤ
ルータのいずれか一方だけが用いられる同種ネットワー
クの場合を考察する。以下、これらのネットワークを、
全ＦＩＦＯ／ＲＥＤケース及び全ＷＦＱ／ＬＱＤケース
と呼称する。ここで考察するネットワーク設計問題にお
いては、全ネットワーク費用は二つのファクタ、すなわ
ち、（１）トポロジー最適化法の結果としての最終ネッ
トワークトポロジー、及び、（２）リンクの必要容量
（これは、ルータにおいて利用可能なスケジューリング
／バッファリング機能の関数である）、によって支配さ
れている。以下、これらの二つのファクタによるインパ
クトを個別に議論する。

【００６５】４．１．１ルータ機能によるインパクトルータ機能によるインパクトのみに注目するために、以
下では、全ての設計に関して同一の最終トポロジーを用
いる。このことは、トポロジー最適化モジュールを停止
して、初期バックボーンＧを最終トポロジーとして用い
る、すなわち、最終Ｇ_s＝Ｇとすることによって実現さ
れる。結果として、全ＷＦＱ／ＬＱＤ設計及び全ＦＩＦ
Ｏ／ＲＥＤ設計の双方ともが、図１２に示されたものと
同一のトポロジーを有することになる。この際、全ての
リンクはアクティブである。図１４は、対応する結果を
まとめたものである。同一の最終ネットワークトポロジ
ー（よってトラフィックルーティングが同一）の場合に
は、全ＷＦＱ／ＬＱＤ設計と全ＦＩＦＯ／ＲＥＤ設計と
の間の費用の差異は、ＷＦＱ／ＬＱＤルータの先進的な
スケジューリング及びバッファ管理機能に起因する容量
削減のみに由来する。全ＷＦＱ／ＬＱＤ設計の費用は相
異なったネットワーク混雑シナリオにおいても不変であ
るが、全ＦＩＦＯ／ＲＥＤ設計の費用は、ネットワーク
混雑シナリオに係る仮定に依存して変化する。全ＷＦＱ
／ＬＱＤ設計の場合には、ワーストケース混雑シナリオ
の下では、すなわち、^-Ｃ_l ^FIFO（Ｈ^worst）に基づく
と、全ＦＩＦＯ／ＲＥＤ設計の場合の１／３未満とな
る。また、最良混雑シナリオ（Ｈ^be ^st）の場合において
もかなり低い。相異なった混雑シナリオ（Ｈ^worst、Ｈ
^hop、Ｈ^one、Ｈ^best）が仮定された場合にＦＩＦＯ設計
の費用が著しく異なることに注目されたい。しかしなが
ら、複数ボトルネック効果に起因する（^-Ｃ_l ^FIFO（Ｈ
^hop）と＿Ｃ_l ^FIFO（Ｈ^hop）との間及び^-Ｃ
_l ^FIFO（Ｈ^one）と＿Ｃ_l ^FIFO（Ｈ^one）との間）費用の差
異は、Ｈの選択に起因する費用の差異と比較して小さ
い。前述されているように、混雑シナリオは実際には動
的であって予測不可能であるため、全トラフィックシナ
リオの下での最小スループットに係る決定論的保証をす
ることを欲する場合には、ＦＩＦＯ／ＲＥＤリンク容量
計算に関しては、ワーストケースシナリオ、すなわちＨ
^worst、を仮定するしか選択肢が存在しない。図１４
は、κでさらわされた“ネットワーク全体での過剰構成
ファクタ”と呼ばれる列も含んでいる。最終ネットワー
クトポロジーＧ_s（Ｖ’，Ｅ’）及び最小スループット
要求ｄ_iを満足する関連したリンク容量Ｃ_lが与えられる
と、κは

【数３７】のように定義される。κの定義を誘導するために、個々
のリンクｌ及び対応する比

【数３８】を考える。理想的には、リンク容量がトランク回線の大
きさという段差を有してではなく連続的に利用可能であ
り、かつ、理想的なリンク帯域スケジューリング／バッ
ファ管理が利用可能である場合には、全ての要求の必要
最小スループットを満たすためには、

【数３８】が１に等しいことが十分である。同一の議論がネットワ
ーク内の全てのリンクに関して適用されると、κの理想
値（最小値）も１に等しくなる。よって、κは、リンク
容量の離散的性質（すなわち、トランク回線数を直近の
整数倍に丸めることが必要であること）やルータにおけ
るソフィスティケートされた帯域スケジューリング及び
バッファ管理の欠如などといった理想的ではない状況に
起因する“容量過剰構成”を表わす指標となる。

【００６６】図１４より、ＷＦＱ／ＬＱＤ設計の場合に
は、リンク容量の離散的性質のために、κが１より少し
大きいことがわかる。他方、ＦＩＦＯ／ＲＥＤルータに
おい蹴る適切なトラフィック管理機能の欠如のために、
ＦＩＦＯ／ＲＥＤ設計の場合には遙かに大きい容量過剰
構成が必要とされる。すなわち、必要最小スループット
を満たす目的でＴＣＰ固有の不公平性を克服するために
は、過剰なリンク容量が必要とされる。

【００６７】ＮＳＦＮＥＴバックボーン設計に加えて、
大規模キャリアクラスのネットワークの設計に同様の方
法を試してみた。その結果は、図１５に示されている。
見出されたことは、ＮＳＦＮＥＴの場合と質的には同様
であるが、全ＦＩＦＯ／ＲＥＤ配置と全ＷＦＱ／ＬＱＤ
配置との間の相対的な費用の差異がより大きくなってい
ることである。このことは、ＮＳＦＮＥＴの場合と比較
して、ネットワークの大きさ及びトラフィックの多様性
が増大していることに起因する。式（５）から、ＦＩＦ
Ｏ／ＲＥＤルータの場合には、リンクの必要容量は最大

【数３９】比を有する要求によって支配されている、ということに
留意されたい。ネットワークが大きくなればなるほど、
トラフィック要求のエンド−ツー−エンド遅延がより多
様化し、よって

【数３９】の最大値も大きくなる。

【００６８】４．１．２トポロジー最適化法の比較次に、節２．０で議論した種々のトポロジー最適化法の
有効性の比較を行なう。ここでは、ＮＳＦＮＥＴバック
ボーンを例示目的に使用する。図１６は、ＷＦＱ／ＬＱ
Ｄルータのみを利用した種々の最適化オプションの結果
を示している。ＦＩＦＯ／ＲＥＤルータの場合は含まれ
ていない。なぜなら、そのような場合にはリンクデロー
ド法がより望ましいからである。図１６に示されている
ように、種々の方式に基づいたネットワーク費用につい
ての結果は、“容量のみの”増大方法を除いて互いに非
常に近接している。この“容量のみ”増大方法はかなり
悪く、費用が３０％より多く増大している。このような
性能は、本発明の発明者が試みた他の設計の場合におい
ても共通に見られるものであって、要求をキーパーある
いはストラグラーとして分類する際の適応の欠如の効果
に擬せられるものである。すなわち、ひとたび閾値が選
択されると、各々の要求は分類されて、通常、決して変
換されない。ＮＳＦＮＥＴの例においては、選択された
閾値は、キーパーによって構成されたサブグラフＧ_sの
接続性が充分ではなく、いくつかの要求が他のより最適
なトポロジーの場合よりもより長い経路を横断しなけれ
ばならない。“容量のみ”増大方法を増強する一つの可
能性のある方法は、複数個の閾値を試行して、最低ネッ
トワーク費用を実現するものを選択することである。

【００６９】ＮＳＦＮＥＴスタディに関しては、初期バ
ックボーンＧが疎であって各ノード対間での要求が存在
するために、トポロジー最適化によって除去されうるＧ
内のリンクはほとんど無い。結果として、トポロジー最
適化法により、最適化されていないトポロジーＧに対し
て最大およそ３％の費用削減が実現された。しかしなが
ら、他のテストケースにおいては、トポロジー最適化法
を用いることによって、およそ１５％から９０％以上と
いうより大きな費用削減が実現できることが明らかにな
った。一般に、実際の費用削減は初期トポロジーＧ及び
トラフィック要求の分布に強く依存する関数である。

【００７０】計算効率の観点では、リンクデロード法の
みに依存することが、特に初期バックボーンＧが非常に
高い接続性を有していて、要求の大部分がトランク回線
サイズに比べて遙かに小さい場合には、比較的高コスト
である。これらの場合には、リンクデロードのみの方式
ではＧ内のほとんど全てのリンクをデロードしようとす
るのに対し、増大方式は、キーパーのルーティングを介
して、“コア”トポロジーを構成するリンクのサブセッ
トを高速に選択することによってプロセスをスピードア
ップすることが可能である。最後に、リンクデロード法
は、通常、同一かあるいはよりよいネットワーク費用を
実現するため、増大法が完了した後にリンクデロード法
を適用することが望ましい。このようにすることによっ
て、試行した種々の設計の場合では、０から１５％の範
囲のさらなる費用削減が実現された。

【００７１】図１７及び１８は、トポロジー最適化及び
ルータ機能の組み合わせによるネットワーク費用へのイ
ンパクトを、それぞれＮＳＦＮＥＴの場合とキャリアク
ラスバックボーン例の場合に示すものである。図１７及
び１８に示されているネットワーク費用は、与えられた
配置に関して見出された“最適”トポロジーに基づくも
のである。最も控えめな仮定の下でも、ＦＩＦＯ／ＲＥ
Ｄルータの代わりにＷＦＱ／ＬＱＤルータを用いること
によって費用に関する実質的な利点が実現される。

【００７２】４．２ルータ配置次に、固定数Ｎ個のＷＦＱ／ＬＱＤルータのみが、前述
されたＮＳＦＮＥＴバックボーンを構成するために他の
ＦＩＦＯ／ＲＥＤルータと共に用いられる異種配置の場
合を考える。節３．０において記述されたＷＦＱ／ＬＱ
Ｄルータ配置に基づいて、図１９は、Ｎが変化した際の
ＷＦＱ／ＬＱＤルータの最適配置を示している。^-Ｃ_l
^FIFO（Ｈ^worst）に基づく対応するネットワーク費用も
計算されている。双方向トラフィック要求の仮定によ
り、あらゆる容量（よって費用）削減を実現するために
は、少なくとも二つのＷＦＱ／ＬＱＤルータが必要とさ
れる。以下、全ＦＩＦＯ／ＲＥＤ配置に係る費用を基準
として利用する。ＷＦＱ／ＬＱＤルータの第一対は、適
切に配置されると、およそ１２．１％の費用削減を実現
することが可能である。これは、ノード８（サンフラン
シスコ）とノード１０（シカゴ）との間の単一の長距離
リンクの必要容量を低減することによって実現される。
このリンクは、その容量の絶対値が大きいこと（トラン
ク回線の絶対数が大きい）及びマイレージが大きいこと
のために、最も著しい費用削減となる。より多くのＷＦ
Ｑ／ＬＱＤルータが最適配置されるにつれて、リンクに
よって担われているトラフィックの

【数３９】比の最大値が大きいために大きな過剰構成ファクタを有
し、大きな絶対容量を有するリンク間で、ＷＦＱ／ＬＱ
Ｄルータがクラスタを構成するようになる。

【００７３】同様のルータ配置が、キャリアクラスのネ
ットワーク例に関して適用された。図２０は、全ＦＩＦ
Ｏ／ＲＥＤ配置における相異なった個数のルータが最適
配置されたＷＦＱ／ＬＱＤルータによって置換された場
合の対応する費用削減を示している。まず、１０％のＦ
ＩＦＯ／ＲＥＤルータが最適配置されたＷＦＱ／ＬＱＤ
ルータによって置換されると、ネットワーク費用がおよ
そ１５％削減される。この大幅な費用削減は、高価な
（長距離の）リンクにおける大幅な容量低減に依るもの
である。ＷＦＱ／ＬＱＤルータの割合が２０％、さらに
は３０％へと増大させられた場合にも、費用低減は依然
としてかなりの大きさを保っている。これは、ＷＦＱ／
ＬＱＤクラスタの形成に依るものであって、“利益を受
ける”リンク、すなわちクラスタ内及びクラスタ間リン
ク、の個数を急速に増大させることになる。その後は、
早期の最適化によって大部分の費用削減がなされてしま
っているために、費用削減率は徐々に低下していく。

【００７４】５．０ＦＩＦＯ／ＲＥＤの下でのスルー
プット割り当てサブセクション１．１を参照すると、M.Mathis, J.Semk
e, J.Mahdavi, and T.Ottによる“ＴＣＰ混雑回避アル
ゴリズムの巨視的振る舞い”という表題の論文（ACM Co
mputer Comm. Review, Vol.27, No.3,pp.67-82(1997.
7)）においてＴＣＰ接続のスループットを計算するため
に用いられている仮定は、（ｉ）リンクは軽度から中度のパケットロスの下で動作
しており、ＴＣＰの動的ウィンドウメカニズムは混雑回
避領域によって主として支配されている。この領域にお
いては、パケットロスが検出されると、混雑ウィンドウ
が半分に閉じられる。ロスが著しい条件下では、ＴＣＰ
ウィンドウフロー制御においてはタイムアウトが発生
し、ウィンドウが１パケットの値に低減されてスロース
タートモードになる。（ｉｉ）接続の経路に沿ったパケットロスは、１／ｐ個
のパケットが送信されるたび毎に１つのパケットが欠落
するという仮定の下に、一定の損失確率ｐによって表現
される。

【００７５】これらの仮定の下では、接続の混雑ウィン
ドウは、図２１に示されているような、周期的な鋸波状
の振る舞いをする。図２１においては、最大ウィンドウ
サイズＷ_maxが充分大きく、混雑ウィンドウはその飽和
値に到達しない（Ｗ＜Ｗ_max）ことが仮定されている。
レシーバが全てのパケットに対してアクノレッジを返す
場合には、ウィンドウは１ラウンドトリップ時間だけ開
き（このことは、図２１における傾きが１に等しいこと
を意味している）、各々のサイクルはＷ／２ラウンドト
リップ時間（τ・Ｗ／２）だけ継続する。サイクル当た
りに送信されるパケット数は、グラフの下側の面積によ
って与えられ、（Ｗ／２）²＋０．５×（Ｗ／２）²＝
（３／８）×Ｗ²である。仮定（ｉｉ）の下では、これ
は、１／ｐに等しく、すなわち、Ｗ＝（８／３ｐ）^0.5
であることを意味している。よって、ＴＣＰ接続のスル
ープットは、

【数４０】によって与えられる。

【００７６】リンクｌを介してルーティングされる全Ｔ
ＣＰ接続の組Ｆ_lにおける各々の接続のスループットを
計算する目的で、以下の仮定を行なう。（ｉｉｉ）Ｓを
混雑したリンクの組とし、Ｘ_jをリンクｊにおけるパケ
ットドロッププロセスとする。Ｘ_j（ｊ∈Ｓ）は独立で
あって、各々が同一の損失確率ｐ⁰によって表現される
と仮定する。同様の仮定は、S.Floydによる“パケット
交換ネットワークにおける複数個の混雑したゲートウェ
イを有する接続第一部。一方通行トラフィック”とい
う表題の論文（ACM Computer Comm. Review, Vol.21,N
o.5, pp.30-47(1991.10)）において、ｎ個のリンク全て
とリンク当たり一つのホップ接続を横断する（すなわ
ち、各々のリンクが二つの接続によって横断されてい
る）ｎホップ接続から構成されたｎ個のリンク及び（ｎ
＋１）個の接続よりなる線型トポロジーにおけるＴＣＰ
スループットを計算するために用いられている。

【００７７】この仮定の下では、接続ｉに係る経路ロス
確率は、ｐ_i＝１−（１−ｐ⁰）^hi （２５）によって与えられる。ここで、ｈｉは、ＴＣＰ接続の経
路における混雑したホップの個数である。実際、ｊ₁、
ｊ₂、．．．、ｊ_hiを接続ｉの経路における混雑したリ
ンクの順序付けられた組とし、ｊ₁及びｊ_hiを、それぞ
れ、接続ｉによって横断される最初と最後の混雑したリ
ンクとする。接続ｉのＮ個のパケットがソースから送出
される場合には、ｐ⁰Ｎ個がリンクｊ₁において落ち、
（１−ｐ⁰）Ｎ個が通過する。リンクｊ２に到達した
（１−ｐ⁰）Ｎ個のパケットのうちのｐ⁰（１−ｐ⁰）Ｎ
個が落ち、（１−ｐ⁰）²Ｎ個が通過する。このようにし
て、リンクｊ_hiに到達した（１−ｐ⁰）^hi-1Ｎ個のパケ
ットのうちのｐ⁰（１−ｐ⁰）^hi-1Ｎ個が落ち、（１−ｐ
⁰）^hiＮ個が伝達される。それゆえ、失われたパケット
の総数はＮ−（１−ｐ⁰）^hiＮ個であって、式（２５）
で与えられる損失比に対応する。損失確率ｐ⁰が小さい
場合には、ｐ_iはｈｉ・ｐ⁰に等しい。なぜなら、式（２
５）におけるｐ⁰の高次の項は無視されるからである。
式（２４）に代入することによって、

【数４１】を得る。ここで、

【数４２】である。

【００７８】与えられたリンクｌ∈Ｓ（容量ｃ_l ^FIFO）
に対して、ｒ^l _iを接続ｉ∈Ｆ_lのスループットシェアと
する。サブセクション１．１において議論されて考慮さ
れた複数ボトルネック効果を無視してリンクｌのみを考
えると、式（２６）におけるｒ _iをｒ^l _iとして取り扱う
ことが可能であり、

【数４３】が得られる。明らかに、リンクバッファは、式（２７）
におけるｃ_l ^FIFOの総計スループットを実現することが
可能である程度に充分に（帯域遅延積のオーダー程度）
大きい必要がある。このような状況ではない場合には、
リンクはわずかしか利用されていない。式（２７）よ
り、δの値として

【数４４】が、接続ｉのスループットシェアとして

【数４５】が得られる。前掲のMathisらによる参照文献において
は、式（２４）の結果の有効性を確認するために、シミ
ュレーションが用いられた。前掲のFloydによる参照文
献においては、前述されたリンク当たり二つの接続の場
合に関する同様の結果をシミュレーションで導いて有効
性を確認する目的で、相異なった方法が用いられた。し
かしながら、式（２８）より得られる結果は任意のトポ
ロジーにおける任意のＴＣＰトラフィックパターンへの
一般化であって、スループット割り当ての重み付けの性
質を表わしている。

【００７９】６．０ルータ再配置実施例におけるＮＰ
ハードネス以下のグラフ問題Ｐ（Ｇ，Ｎ）を考える。単純重みグ
ラフＧ＝（Ｖ，Ｅ，Ｓ）が与えられている。この際、Ｓ
は｜Ｖ｜×｜Ｖ｜重み行列であって、そのノード対ｉ，
ｊ∈Ｖに対応する要素Ｓ_i,jは、

【数４６】である。Ｓ_i,jの削減は、双方のノードｉ及びｊが選択
された場合に実現される。目的は、選択されるノード総
数をＮ以下に保ちつつ、削減量を最大化することであ
る。このグラフ問題Ｐ（Ｇ，Ｎ）は、節３．０で記述さ
れた問題Ｐにおいて、全てのＱ_iをゼロに設定した特別
な場合であることは明らかである。Ｐ（Ｇ，Ｎ）におけ
るノードの選択は、ＷＦＱ／ＬＱＤアップグレードを行
なうためのＦＩＦＯ／ＲＥＤロケーションの選択に対応
している。

【００８０】Ｐ（Ｇ，Ｎ）はＰの特別な場合であるた
め、ＰがＮＰハードであることを証明するためには、Ｐ
（Ｇ，Ｎ）がＮＰハードであることを示すのが十分であ
る。Ｐ（Ｇ，Ｎ）がＮＰハードであることの証明は、Ｎ
Ｐ完全最大クリーク問題の決定バージョンのＰ（Ｇ，
Ｎ）の場合への還元を通じたものである。クリーク問題
は当業者には公知であり、例えば、M.R.Garey and D.S.
Johnsonによる“コンピュータ及びイントラクタビリテ
ィ。ＮＰ完全性の理論への指針”という表題の文献（Fr
eeman(1979)）及びC.H.Papadimitriouらによる“組み合
わせ最適化。アルゴリズム及び複雑さ”という表題の文
献（Prentice Hall(1982)）に記述されている。最大ク
リーク問題Ｑ（Ｇ，Ｎ）の決定バージョンは、以下のよ
うに書き表わすことが可能である。単純グラフＧ＝
（Ｖ，Ｅ）及び正の整数Ｎが与えられた場合に、｜Ｖ’
｜＝Ｎかつ全ての相異なったｉ，ｊ∈Ｖ’に対して
（ｉ，ｊ）∈ＥなるＧのサブグラフＧ_s＝（Ｖ’，
Ｅ’）が存在するか？

【００８１】Ｐ（Ｇ，Ｎ）がＮＰハードであることを証
明するために、

【数４７】と設定することによって、Ｑ（Ｇ，Ｎ）をＰ（Ｇ，Ｎ）
の場合に還元することが可能である。Ｐ（Ｇ，Ｎ）から
導かれる最大削減がＮ（Ｎ−１）／２に等しく、かつこ
れ以上還元できない場合にのみ、Ｑ（Ｇ，Ｎ）が“ｙｅ
ｓ”という解を有することは明らかである。

【００８２】問題Ｐは、以下のステップを用いて、一般
化されたナップザック問題に変換されることが可能であ
る。第一に、ナップザックの大きさをＮ_maxに設定し、
Ｇ内のＦＩＦＯ／ＲＥＤルータを、それぞれが１という
大きさを有する、ナップザックに詰め込まれるアイテム
と見なす。次に、あらゆるアイテム対（ｉ，ｊ）に、ユ
ーティリティ値Ｓ_i,jを割り当てる。このことは、アイ
テムｉ及びｊの双方がナップザックに詰め込まれる場合
にのみ実現される。その後、各々のアイテムｉに対し
て、それがナップザックに詰め込まれる場合にペナルテ
ィＱ_iを関連づける。選択されたアイテムの組に係る総
ユーティリティ値を、ユーティリティ値Ｓ _i,jの総和か
らその組のペナルティＱ_iの総和を減じたものと定義す
る。このようにすることで、置換されるべきＦＩＦＯ／
ＲＥＤルータの最適の組の選択が、与えられたナップザ
ックサイズの下で総ユーティリティ値を最大化するよう
な詰め込まれるアイテムの組の選択の問題になる。

【００８３】よって、既に説明されているように、ＩＰ
ベースネットワークにおける性能保証を実現する必要性
は、数多くのキャリアがバックボーンインターネット接
続を提供するためにＩＰを直接ＳＯＮＥＴにパックする
ようになってきているため、より重要になってきてい
る。本発明は、これら及びその他の問題を取り扱うネッ
トワーク設計及び容量最適化アルゴリズムを提供する。
さらに、本発明は、同種（全ＷＦＱ／ＬＱＤあるいは全
ＦＩＦＯ／ＲＥＤネットワーク）及び異種ネットワーク
の双方に係る設計を実現する。異種ネットワークにおい
ては、本発明に係る方法は、ＦＩＦＯ／ＲＥＤルータが
組み込まれたネットワークにおけるＷＦＱ／ＬＱＤルー
タの最適配置の問題を解決する。

【００８４】ここで、これまでに記述された本発明の望
ましい実施例に係る詳細な記述が本発明を制限している
訳では無い。例えば、本発明に係るネットワーク設計シ
ステム及び方法は、ＶＰＮサービスを実現する他のアプ
ローチ、例えば（ｉ）ＩＰパケット中のサービスタイプ
（ＴＯＳ）フィールドを利用して、ネットワークエッジ
に位置するルータに監視させてＶＰＮ契約を超過してい
るトラフィックにマークをする方法、及び、（ｉｉ）
（ｉ）とＷＦＱ／ＬＱＤを組み合わせた組み合わせ方
法、等に対しても適用可能である。さらに、本発明は、
より高度なルーティング、例えば偏差（デフレクショ
ン）及びＯＳＰＦにおけるＴＯＳベースルーティングの
使用を介したループフリー非最短経路ネクストホップフ
ォワーディング等と共にインプリメントされうる。さら
に、本発明は、ＮＰハードルータ配置問題を解く他の方
法をインプリメントすることも可能である。本発明は、
例えば、同種ＷＦＱ／ＬＱＤルータネットワークを同種
ＦＩＦＯ／ＲＥＤルータネットワークと組み合わせる２
層ネットワークを介した差動サービスをサポートするイ
ンフラストラクチャの設計に用いられうる。さらに、前
述されたＴＣＰスループットモデルは、タイムアウト及
び／あるいは最大レシーバ／送信側ウィンドウサイズが
主たるものであるような領域をカバーするように、及び
クラス間ＷＦＱや各クラスのフロー間でのＦＩＦＯ等の
他のタイプのパケットスケジューリングをカバーするよ
うに、それぞれ拡張されうる。

【００８５】以上の説明は、本発明の一実施例に関する
もので，この技術分野の当業者であれば、本発明の種々
の変形例が考え得るが、それらはいずれも本発明の技術
的範囲に包含される。

【００８６】

【発明の効果】以上述べたごとく、本発明によれば、ワ
ーストケース及び最良のリンク能力要求を自動的に計算
し、ネットワークのトポロジーを最適化し、及び、ネッ
トワークにおける最適ルータ配置を決定する方法及びそ
の装置が提供される。

【図面の簡単な説明】

【図１】本発明の実施例に従ったＩＰネットワーク設
計システムを示すブロック図。

【図２】本発明の実施例に従った設計方法を示す流れ
図。

【図３】本発明の実施例に従った必要リンク容量計算
法を示す流れ図。

【図４】本発明の別の実施例に従った必要リンク容量
計算法を示す流れ図。

【図５】本発明のさらに別の実施例に従った必要リン
ク容量計算法を示す流れ図。

【図６】本発明の実施例に従ったネットワークトポロ
ジーの最適化法を示す流れ図。

【図７】本発明の実施例に従ったネットワークトポロ
ジーの最適化法を示す流れ図。

【図８】本発明の実施例に従ったネットワークトポロ
ジーの最適化法を示す流れ図。

【図９】本発明の実施例に従ったネットワークトポロ
ジーの最適化法を示す流れ図。

【図１０】本発明の別の実施例に従ったネットワーク
トポロジーの最適化法を示す流れ図。

【図１１】本発明の実施例に従ったネットワーク内ル
ータの配置の決定法を示す流れ図。

【図１２】本発明のインプリメントする場合のネット
ワークトポロジーの一例を示す図。

【図１３】本発明に関して実行されたケーススタディ
に係る実例及びその結果を示す表。

【図１４】本発明に関して実行されたケーススタディ
に係る実例及びその結果を示す表。

【図１５】本発明に関して実行されたケーススタディ
に係る実例及びその結果を示す表。

【図１６】本発明に関して実行されたケーススタディ
に係る実例及びその結果を示す表。

【図１７】本発明に関して実行されたケーススタディ
に係る実例及びその結果を示す表。

【図１８】本発明に関して実行されたケーススタディ
に係る実例及びその結果を示す表。

【図１９】本発明に関して実行されたケーススタディ
に係る実例及びその結果を示す表。

【図２０】本発明に関して実行されたケーススタディ
に係る実例及びその結果を示す表。

【図２１】ＴＣＰ混雑ウィンドウのダイナミクスを例
示するグラフ。

【符号の説明】

１０ＩＰネットワーク設計システム１２ルーティングプロセッサ１４ワーストケース必要リンク容量プロセッサ１６最良リンク容量設計プロセッサ１８ネットワークトポロジー最適化プロセッサ２０ルータ再配置プロセッサ

───────────────────────────────────────────────────── フロントページの続き (71)出願人 596077259 600 ＭｏｕｎｔａｉｎＡｖｅｎｕｅ, ＭｕｒｒａｙＨｉｌｌ，ＮｅｗＪｅｒｓｅｙ 07974−0636Ｕ．Ｓ．Ａ. (72)発明者ロトゥフィベンモハームドアメリカ合衆国、07728 ニュージャージー、フリーホールド、ズロッキンサークル 701−１ (72)発明者スブラーマニアムドラビダアメリカ合衆国、01540 マサチューセッツ、ゴートン、ドラムリンヒルロード 25 (72)発明者パラマシビアーハーシャバードハナアメリカ合衆国、07746 ニュージャージー、マルボロ、サレムコート 11 (72)発明者ウィンチェオンラオアメリカ合衆国、07724 ニュージャージー、イートンタウン、ビクトリアドライブ 40 (72)発明者アジェイクマーミッタルアメリカ合衆国、08817 ニュージャージー、エジソン、リベンデルウェイ 312

Claims

【特許請求の範囲】

【請求項１】パケットベースの通信ネットワークを設
計する方法において（Ａ）前記パケットベース通信ネットワークのトポロ
ジーにおけるノード間の含ませられる各々のリンクに係
る一対のリンク容量値を計算するステップと、（Ｂ）各々のリンクに係る前記上限及び下限の範囲の
値の選択目的で前記リンク容量値を出力するステップ
と、を有し、前記リンク容量値は、フロー要求の組、ラウンドトリッ
プ遅延及び少なくとも一つの接続要求に係るリンク混雑
シナリオに基づくリンク容量範囲の上限及び下限を表わ
しており、前記選択された値は、前記ネットワークトポロジーにお
ける仕様に関して少なくとも一つの接続要求を実質的に
満足するを有することを特徴とする通信ネットワーク設
計方法。
【請求項２】前記パケットベース通信ネットワーク
が、ＦＩＦＯ／ＲＥＤスケジューリング／バッファリン
グ方式を用いることを特徴とする請求項１に記載の通信
ネットワーク設計方法。
【請求項３】前記上限^-ｃ_l ^FIFOが、【数１】によって表わされ、ｄ_iは前記フロー要求に係るスルー
プットを表わし、Ｈ_lはＦ _l内の各々のフローの経路にお
ける混雑したリンクの個数よりなるベクトルを表わし、
Ｆ_lはリンクｌを介してルーティングされる要求を含む
組を表わし、ｗはラウンドトリップ遅延とリンク混雑シ
ナリオの関数であることを特徴とする請求項２に記載の
通信ネットワーク設計方法。
【請求項４】前記下限＿ｃ_l ^FIFOが、【数２】によって表わされ、ｒ_iは要求ｉによって獲得されるリ
ンクシェアを表わしており、｛Ｈ｝はＨ_lの組を表わ
し、Ｆ_lはリンクｌを介してルーティングされる要求を
含む組を表わしていることを特徴とする請求項２に記載
の通信ネットワーク設計方法。
【請求項５】前記リンク混雑シナリオがユーザによっ
て選択可能であることを特徴とする請求項１に記載の通
信ネットワーク設計方法。
【請求項６】前記リンク混雑シナリオが、前記ネット
ワーク内の接続経路における混雑したリンクの個数を表
わすｈの関数であることを特徴とする請求項１に記載の
通信ネットワーク設計方法。
【請求項７】前記上限に係る前記リンク混雑シナリオ
が、ｈ_iが^-ｈ_iに等しくかつｊ≠ｉなるｊに関してｈ_j＝
１であるように規定されること、ここで、ｈ_iは前記ネ
ットワーク内の接続ｉの経路における混雑したリンクの
個数を表わしており、^-ｈ_iは接続ｉに係る最短経路に対
応するホップの個数を表わしており、及び、ｈ_jは前記
ネットワーク内の接続ｊの経路における混雑したリンク
の個数を表わしている、を特徴とする請求項６に記載の
通信ネットワーク設計方法。
【請求項８】前記下限に係る前記リンク混雑シナリオ
が、ｈ_jが^-ｈ_jに等しくかつｊ≠ｉなるｊに関してｈ_i＝
１であるように規定されること、ここで、ｈ_jは前記ネ
ットワーク内の接続ｊの経路における混雑したリンクの
個数を表わしており、^-ｈ_jは接続ｊに係る最短経路に対
応するホップの個数を表わしており、及び、ｈ_iは前記
ネットワーク内の接続ｉの経路における混雑したリンク
の個数を表わしている、を特徴とする請求項６に記載の
通信ネットワーク設計方法。
【請求項９】前記上限と前記下限との間の場合に対す
る前記リンク混雑シナリオがｈ_i＝^-ｈ_iであるように規
定されること、ここで、ｈ_iは前記ネットワーク内の接
続ｉの経路における混雑したリンクの個数を表わしてお
り、^-ｈ_iは接続ｉに係る最短経路に対応するホップの個
数を表わしている、を特徴とする請求項６に記載の通信
ネットワーク設計方法。
【請求項１０】前記上限と前記下限との間の場合に対
する前記リンク混雑シナリオがｈ_i＝１であるように規
定されること、ここで、ｈ_iは前記ネットワーク内の接
続ｉの経路における混雑したリンクの個数を表わしてい
る、を特徴とする請求項６に記載の通信ネットワーク設
計方法。
【請求項１１】前記パケットベース通信ネットワーク
がＩＰネットワークプロトコルを採用していることを特
徴とする請求項１に記載の通信ネットワーク設計方法。
【請求項１２】前記パケットベース通信ネットワーク
がＴＣＰとラン巣ポートプロトコルを採用していること
を特徴とする請求項１１に記載の通信ネットワーク設計
方法。
【請求項１３】前記リンク容量値の計算がＴＣＰトラ
フィックを考慮していることを特徴とする請求項１２に
記載の通信ネットワーク設計方法。
【請求項１４】前記パケットベース通信ネットワーク
がＵＤＰトランスポートプロトコルを採用していること
を特徴とする請求項１１に記載の通信ネットワーク設計
方法。
【請求項１５】前記リンク容量値の計算がＵＤＰトラ
フィックを考慮していることを特徴とする請求項１４に
記載の通信ネットワーク設計方法。
【請求項１６】前記パケットベース通信ネットワーク
がＴＣＰ及びＵＤＰトランスポートプロトコルを採用し
ていることを特徴とする請求項１１に記載の通信ネット
ワーク設計方法。
【請求項１７】前記リンク容量値の計算がＴＣＰ及び
ＵＤＰトラフィックを考慮していることを特徴とする請
求項１６に記載の通信ネットワーク設計方法。
【請求項１８】前記パケットベース通信ネットワーク
が仮想プライベートネットワークであることを特徴とす
る請求項１に記載の通信ネットワーク設計方法。
【請求項１９】特定の要求内の接続の個数が複数であ
ることを特徴とする請求項１に記載の通信ネットワーク
設計方法。
【請求項２０】パケットベース通信ネットワークを設
計する装置において前記パケットベース通信ネットワー
クのトポロジーにおけるノード間の含ませられる各々の
リンクに係る一対のリンク容量値を計算する少なくとも
一つのプロセッサと、ここで、前記リンク容量値は、フ
ロー要求の組、ラウンドトリップ遅延及び少なくとも一
つの接続要求に係るリンク混雑シナリオに基づくリンク
容量範囲の上限及び下限を表わしており、前記プロセッ
サは、各々のリンクに係る前記上限及び下限の範囲の値
の選択目的で前記リンク容量値を出力することがかのう
である、加えて、前記選択された値は、前記ネットワー
クトポロジーにおける仕様に関して少なくとも一つの接
続要求を実質的に満足する、前記リンク容量値及び選択結果のうちの一つあるいは複
数個をストアするメモリと、を有することを特徴とする
通信ネットワーク設計装置。
【請求項２１】前記パケットベース通信ネットワーク
が、ＦＩＦＯ／ＲＥＤスケジューリング／バッファリン
グ方式を用いることを特徴とする請求項２０に記載の通
信ネットワーク設計装置。
【請求項２２】前記上限^-ｃ_l ^FIFOが、【数３】によって表わされること、ここで、ｄ_iは前記フロー要
求に係るスループットを表わし、Ｈ_lはＦ_l内の各々のフ
ローの経路における混雑したリンクの個数よりなるベク
トルを表わし、Ｆ_lはリンクｌを介してルーティングさ
れる要求を含む組を表わし、及び、ｗはラウンドトリッ
プ遅延とリンク混雑シナリオの関数である、を特徴とす
る請求項２１に記載の通信ネットワーク設計装置。
【請求項２３】前記下限＿ｃ_l ^FIFOが、【数４】によって表わされること、ここで、ｒ_iは要求ｉによっ
て獲得されるリンクシェアを表わしており、｛Ｈ｝はＨ
_lの組を表わし、Ｆ_lはリンクｌを介してルーティングさ
れる要求を含む組を表わしている、を特徴とする請求項
２１に記載の通信ネットワーク設計装置。
【請求項２４】前記リンク混雑シナリオがユーザによ
って選択可能であることを特徴とする請求項２０に記載
の通信ネットワーク設計装置。
【請求項２５】前記リンク混雑シナリオが、前記ネッ
トワーク内の接続経路における混雑したリンクの個数を
表わすｈの関数であることを特徴とする請求項２０に記
載の通信ネットワーク設計装置。
【請求項２６】前記上限に係る前記リンク混雑シナリ
オが、ｈ_iが^-ｈ_iに等しくかつｊ≠ｉなるｊに関してｈ_j
＝１であるように規定されること、ここで、ｈ_iは前記
ネットワーク内の接続ｉの経路における混雑したリンク
の個数を表わしており、^-ｈ_iは接続ｉに係る最短経路に
対応するホップの個数を表わしており、及び、ｈ_jは前
記ネットワーク内の接続ｊの経路における混雑したリン
クの個数を表わしている、を特徴とする請求項２５に記
載の通信ネットワーク設計装置。
【請求項２７】前記下限に係る前記リンク混雑シナリ
オが、ｈ_jが^-ｈ_jに等しくかつｊ≠ｉなるｊに関してｈ_i
＝１であるように規定されること、ここで、ｈ_jは前記
ネットワーク内の接続ｊの経路における混雑したリンク
の個数を表わしており、^-ｈ_jは接続ｊに係る最短経路に
対応するホップの個数を表わしており、及び、ｈ_iは前
記ネットワーク内の接続ｉの経路における混雑したリン
クの個数を表わしている、を特徴とする請求項２５に記
載の通信ネットワーク設計装置。
【請求項２８】前記上限と前記下限との間の場合に対
する前記リンク混雑シナリオがｈ_i＝^-ｈ_iであるように
規定されること、ここで、ｈ_iは前記ネットワーク内の
接続ｉの経路における混雑したリンクの個数を表わして
おり、^-ｈ_iは接続ｉに係る最短経路に対応するホップの
個数を表わしている、を特徴とする請求項２５に記載の
通信ネットワーク設計装置。
【請求項２９】前記上限と前記下限との間の場合に対
する前記リンク混雑シナリオがｈ_i＝１であるように規
定されること、ここで、ｈ_iは前記ネットワーク内の接
続ｉの経路における混雑したリンクの個数を表わしてい
る、を特徴とする請求項２５に記載の通信ネットワーク
設計装置。
【請求項３０】前記パケットベース通信ネットワーク
がＩＰネットワークプロトコルを採用していることを特
徴とする請求項２０に記載の通信ネットワーク設計装
置。
【請求項３１】前記パケットベース通信ネットワーク
がＴＣＰとラン巣ポートプロトコルを採用していること
を特徴とする請求項３０に記載の通信ネットワーク設計
装置。
【請求項３２】前記リンク容量値の計算がＴＣＰトラ
フィックを考慮していることを特徴とする請求項３１に
記載の通信ネットワーク設計装置。
【請求項３３】前記パケットベース通信ネットワーク
がＵＤＰトランスポートプロトコルを採用していること
を特徴とする請求項３０に記載の通信ネットワーク設計
装置。
【請求項３４】前記リンク容量値の計算がＵＤＰトラ
フィックを考慮していることを特徴とする請求項３３に
記載の通信ネットワーク設計装置。
【請求項３５】前記パケットベース通信ネットワーク
がＴＣＰ及びＵＤＰトランスポートプロトコルを採用し
ていることを特徴とする請求項３０に記載の通信ネット
ワーク設計装置。
【請求項３６】前記リンク容量値の計算がＴＣＰ及び
ＵＤＰトラフィックを考慮していることを特徴とする請
求項３５に記載の通信ネットワーク設計装置。
【請求項３７】前記パケットベース通信ネットワーク
が仮想プライベートネットワークであることを特徴とす
る請求項２０に記載の通信ネットワーク設計装置。
【請求項３８】特定の要求内の接続の個数が複数であ
ることを特徴とする請求項２０に記載の通信ネットワー
ク設計装置。
【請求項３９】単一あるいは複数個のプログラムを含
み、機械によって読み取り可能な媒体を製造する装置に
おいて、前記プログラムが、実行される際に、（Ａ）パケットベース通信ネットワークのトポロジー
におけるノード間の含ませられる各々のリンクに係る一
対のリンク容量値を計算するステップと、ここで、前記
リンク容量値は、フロー要求の組、ラウンドトリップ遅
延及び少なくとも一つの接続要求に係るリンク混雑シナ
リオに基づくリンク容量範囲の上限及び下限を表わして
いる、（Ｂ）各々のリンクに係る前記上限及び下限の範囲の
値の選択目的で前記リンク容量値を出力するステップ
と、を実行し、ここで、前記選択された値は、前記ネッ
トワークトポロジーにおける仕様に関して少なくとも一
つの接続要求を実質的に満足する、ことを特徴とする装
置。
【請求項４０】パケットベース通信ネットワークを設
計する方法において（Ａ）前記パケットベース通信ネットワークのトポロ
ジーにおけるノード間の含ませられる各々のリンクにお
けるスケジューラ重み及びバッファ割り当てを設定する
ステップと、（Ｂ）各々のリンクに対するリンク容量値を計算する
ステップとを有し、ここで、各々のリンク容量値は少な
くとも一つの接続に関連するフロー要求のスループット
の総和である、ことを特徴とする通信ネットワーク設計
方法。
【請求項４１】パケットベース通信ネットワークを設
計する装置において前記パケットベース通信ネットワー
クのトポロジーにおけるノード間の含ませられる各々の
リンクにおけるスケジューラ重み及びバッファ割り当て
を設定する少なくとも一つのプロセッサと、ここで、当
該プロセッサは、さらに、各々のリンクに対するリンク
容量値をも計算する、この際、各々のリンク容量値は少
なくとも一つの接続に関連するフロー要求のスループッ
トの総和であり、前記スケジューラ重み、前記バッファ割り当て、及び前
記各々のリンクに対する前記リンク容量値のうちの一つ
あるいは複数個をストアするメモリと、を有することを
特徴とする通信ネットワーク設計装置。
【請求項４２】パケットベース通信ネットワークを設
計する目的で、単一あるいは複数個のプログラムを含
む、機械によって読み取り可能な媒体を製造する装置に
おいて、前記プログラムが、実行される際に、前記パケットベース通信ネットワークのトポロジーにお
けるノード間の含ませられる各々のリンクにおけるスケ
ジューラ重み及びバッファ割り当てを設定するステップ
と、各々のリンクに対するリンク容量値を計算するステップ
とを実行し、ここで、各々のリンク容量値は少なくとも
一つの接続に関連するフロー要求のスループットの総和
であることを特徴とする装置。