JP2000501899A - 広帯域トラフィックによる最適仮想経路容量割り当てシステムおよび方法 - Google Patents

広帯域トラフィックによる最適仮想経路容量割り当てシステムおよび方法

Info

Publication number
JP2000501899A
JP2000501899A JP9506610A JP50661097A JP2000501899A JP 2000501899 A JP2000501899 A JP 2000501899A JP 9506610 A JP9506610 A JP 9506610A JP 50661097 A JP50661097 A JP 50661097A JP 2000501899 A JP2000501899 A JP 2000501899A
Authority
JP
Japan
Prior art keywords
virtual
capacity
blocking
virtual path
ratio function
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
JP9506610A
Other languages
English (en)
Other versions
JP2000501899A5 (ja
Inventor
マロムソキイ，スザボルクス
ホレンダー，ウロデク（故人）
Original Assignee
テレフオンアクチーボラゲツト エル エム エリクソン（パブル）
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by テレフオンアクチーボラゲツト エル エム エリクソン（パブル） filed Critical テレフオンアクチーボラゲツト エル エム エリクソン（パブル）
Publication of JP2000501899A publication Critical patent/JP2000501899A/ja
Publication of JP2000501899A5 publication Critical patent/JP2000501899A5/ja
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q3/00—Selecting arrangements
    • H04Q3/0016—Arrangements providing connection between exchanges
    • H04Q3/0062—Provisions for network management
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13526—Indexing scheme relating to selecting arrangements in general and for multiplex systems resource management
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13531—Indexing scheme relating to selecting arrangements in general and for multiplex systems virtual networks - inc. PVN
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13562—Indexing scheme relating to selecting arrangements in general and for multiplex systems blocking

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Telephonic Communication Services (AREA)

Abstract

(57)【要約】 限られた伝送資源を、物理ネットワーク上に定義される種々の仮想経路に割り当てるための汎用割り当て方法およびシステム。物理ネットワーク要素のレイヤ上に、１つ以上の仮想経路のレイヤがある、二レベル階層構造を定義する（図）。各仮想経路に対してトラフィック要求を指定し、エントロピ比率関数をブロック化尺度として用いる。ブロック化確率を等しくすることによって、種々のリンク上の負荷の均衡を取り、ネットワークの物理資源の最適な割り当てを判定する。

Description

【発明の詳細な説明】 広帯域トラフィックによる最適仮想経路容量割り当てシステムおよび方法 Ｕ．Ｓ．Ｃ．§１１９（ｅ）および３７Ｃ．Ｆ．Ｒ§１．７８（ａ）（１）に基 づく優先権 この正式出願(nonprovisional application)は、１９９５年７月１４日にWlod ek Holender およびSzabolcs Malomsoky名義で出願され、同様に本発明と同じ譲 受人に譲渡された、"Efficient Dimensioning Methods For Broadband ATM Netw orks With General Type of Traffic"と題する、先願の米国特許出願番号第６０ ／００１，１６９号（弁理士整理番号第２７９４６−０００９４号）に基づく優 先権を主張する。 関連出願に対する引用 この正式米国特許出願は、１９９５年８月１１日に出願された"System and Me thod For Optimal Logical Network Capacity Dimensioning With Broadband Tr affic"と題する同時係属中の仮米国特許出願番号０８／５１４，２３５号（弁理 士整理番号第２７９４６−０００９３号）、および１９９５年８月１１に出願さ れた"System and Method For Adaptive Routing On A Virtual Path Broadband Network"と題する仮米国特許出願番号第０８／５１３，７２３号（弁理士整理番 号第２７９４６−０００９５号）に関連する主題を含む。これらの仮米国特許出 願およびその開示は、この言及により、本願にも含まれるものとする。 発明の背景 １．発明の技術分野 本発明は、遠隔通信ネットワークの効率的な割り当て(dimensioning)のための システムおよび方法に関し、更に特定すれば、ブロック化尺度(blocking measur e)としてエントロピ比率関数(entropy rate function)を用いて、制約のある物 理ネットワーク上において定義された仮想経路に容量を割り当てる技術に関する ものである。 ２．関連技術の説明 局所的な地理領域内に配置されている電話機器およびその他の通信装置は、従 来より、市内交換局(local exchange)と呼ばれる交換機器によって、互いに接続 されている。一方、市内交換局は、中継線交換局(trunk exchange)によって相互 接続されている。互いに隔離された地理的領域内に配置され異なる市内交換局に 接続されている電話／データ機器は、市内交換局および中継線交換局の複雑な群 を通じて、互いに通信する。これらの市内交換局および中継線交換局は、互いに 連結され遠隔通信ネットワークを形成する。このように、遠隔通信ネットワーク は、市内交換局、中継線交換局、移動無線交換局、長距離交換局、およびそれら の組み合わせのような、複数の相互接続ネットワーク要素で構成されている。各 ネットワーク・レベルでは、交換局のような１つのネットワーク要素から別のネ ットワーク要素へのトラフィックは、異なる交換局を経由する様々なルートを取 ることができる。 ネットワーク内における通信設備の効率的なネットワーク・トラフィック管理 には、最終的に選択されるトラフィック・ルート上で過度の輻輳を発生すること なく、各宛先のトラフィックの要件を処理するために、十分な数の回路が使用可 能となっていなければならない。また、ネットワークの輻輳は、全ての最終選択 ルート上においてできるだけ等しくなければならず、更に実際に供給されている ルートの中の未使用容量を最少に抑えて、資源の効率的な利用を確保する必要が ある。加えて、ネットワークを運営する電話会社の予算は限られているので、結 果的に、各ネットワーク内の既存の資源から、できるだけ高い効率を得なければ ならない。 従来より、通信ネットワーク内のトラフィック管理は、ネットワーク内のトラ フィック・パターンを周期的に調査し、回路および経路の構成を変更し、トラフ ィック処理効率向上を図る手順が含まれている。加えて、特定の場所または特定 の領域、および当該領域における局所的な出来事に対する通話密度の上昇を予測 して、更に多くの経路や回路をネットワークに追加する場合もある。従来のネッ トワーク管理システムは、ネットワーク内で選択されたルート間において、トラ フィック負荷の相対的分布を変更し、サービス品質（ＱｏＳ:quality of servic e)を過度に低下させることなく、ネットワークを最大限効率的に利用する ことも可能である。しかしながら、従来のトラフィック・ネットワーク管理シス テムおよび手順は、概して、ネットワーク内の回路およびルートの可用性増大に よって、個々のトラフィック要求を処理しようとするものであり、ネットワーク 内のルートや回路をより高い抽象レベルで再割り当てすることによってネットワ ークを再構成し、全体的な効率を最大化しようとするものではなかった。 遠隔通信システムにおける物理ネットワーク資源を管理する効率を最大に高め るという本来の必要性に加えて、近年における情報および通信技術の成長により 、新たな経済的好機および管理面での課題が多く生じた。遠隔通信サービスを提 供するベンダは、新たな顧客の要求に直面し続けている。遠隔通信ネットワーク を通じて普通の音声通信を提供するだけでは、もはや十分ではない。今日のユー ザは、音声信号だけでなく、データ、オーディオ、ビデオ、およびマルチメディ ア信号を、リアル・タイムおよびパケット交換ネットワークの双方で伝送する機 能を欲している。非同期転送モード（ＡＴＭ:Asynchronous Transfer Mode）技 術は、広帯域遠隔通信設備を提供するというその高い能力のために、増々重要性 を獲得しつつある。 ＡＴＭ技術の主要な特徴の１つは、ネットワーク資源利用におけるその柔軟性 である。この柔軟性の活用を可能にする１つの手法は、物理ネットワーク資源を 全体的または部分的に、論理的に定義した資源に区分することである。例えば、 物理ネットワークを複数の仮想ネットワークに区分することにより、物理ネット ワークの運営、保守および管理は、大幅に簡略化が可能となる。この手順によっ て、物理ネットワーク全体における各呼に対するトラフィック経路決定問題を分 析し解決する作業は、各仮想ネットワーク上の大幅に単純化された経路決定問題 へと縮小化することが可能になる。個別の仮想ネットワークは各々、物理ネット ワーク全体よりは全体として複雑度が低く、トラフィックの経路決定問題の解決 は容易となる。 物理資源の区分は、異なるトラフィック・タイプ、異なるサービス・クラス、 または賃借ネットワーク内における多種多様のトラフィック要求の存在によって 必要とされる場合もある。各顧客の用途に別個の物理ネットワークを提供する代 わりに、サービス・プロバイダは、単一の共通ＡＴＭ物理インフラストラクチャ 上に定義された多数の仮想ネットワークを設置することができる。 この仮想ネットワーク構造の構成における新たな柔軟性は、効率的な割り当て ツール、方法、およびアルゴリズムを必要とする。将来提供される遠隔通信サー ビスの性質は予測が困難なので、仮想ネットワーク資源の構成を管理するために 用いられる割り当て方法は、全てのタイプの広帯域ネットワークに対処可能でな ければならない。仮想ネットワークの構成を頻繁に改訂し、提供トラフィックの パターン変化に合わせていかなければならない場合、ネットワーク再割り当てお よび構成制御システムの計算効率も高くなければならない。ネットワークの再割 り当ておよびネットワークの再構成を行うために選択されるアルゴリズムは、各 仮想ネットワークの持続期間よりも大幅に短い時間期間の内にその計算を実行し なければならない。 割り当て技法は汎用トラフィック分布のモデル化ができなければならないとい う必要性があるために、多くの既存の割り当て技法は除外される。一般的に用い られている割り当て方法の殆どは、アーランのブロック化尺度(Erlang blocking measure)を使用することに起因する限界のために、汎用的なトラフィック・モデ ルを処理することができない。本発明の方法および装置は、これらの欠点を克服 するものである。 発明の概要 したがって、本発明の目的は、汎用トラフィック分布モデルを用いてユーザに ネットワークの割り当てを可能にすることである。本発明の別の目的は、最少の 計算資源を用いて割り当て計算の実行を可能にすることである。本発明のその他 の目的は、計算の複雑度が低く、その結果高速化を図った割り当てアルゴリズム を実施することである。本発明の更に他の目的は、できるだけ短い時間期間で再 割り当て計算を実行可能とすることである。本発明の更に別の目的は、仮想ネッ トワークの割り当ておよび仮想経路割り当てプロセスの効率を高めることである 。 複数の物理リンクから成る物理ネットワークにおいて、各物理リンクが予め指 定された伝送容量を有する場合について、本発明のシステムおよび方法は、汎用 トラフィック・モデルを支援する割り当て技法を例示する。割り当てのタスクは 、種々の物理リンクにわたる負荷バランスの問題として取り扱う。仮想経路の割 り 当ての問題に対する最適な解決策は、種々の仮想経路に対する割り当て容量の選 択に対応し、仮想経路の各々におけるブロック化は、種々のリンク上においてで きるだけ均一に行われる。 １つの態様において、本発明は、複数の交換局またはノードを相互接続する複 数の物理リンクを有する遠隔通信ネットワークを効率的に割り当てる方法を含む 。複数の物理リンクは、１本以上の仮想経路に関係する。仮想経路の各々は、遠 隔通信ネットワーク内の交換局またはノードの対間で、個々に切り替え可能な接 続を行う。提供トラフィックは、仮想経路の各々について指定され、遠隔通信ネ ットワークの各物理リンクに対して、伝送容量の制約が設定される。提供トラフ ィックとその他の計算パラメータ間の関係は、エントロピ・ブロック化尺度を用 いて遠隔通信ネットワーク上でモデル化され、種々の物理リンクに対する伝送容 量の制約を受ける複数の仮想経路に容量が割り当てられ、種々の仮想経路上のブ ロック化の確率は、予め選択されているエラー境界内で、できるだけ均一にする 。 図面の簡単な説明 本発明の方法およびシステムの一層完全な理解は、以下に続く好適実施例の詳 細な説明を、添付図面と関連付けながら参照することにより得ることができよう 。 図１は、仮想経路割り当てを実行可能な代表的遠隔通信ネットワークのブロッ ク図である。 図２は、代表的なＡＴＭセル構造の一例を示すブロック図である。 図３は、ＡＴＭネットワーク内においての相互接続された多数の仮想経路およ び仮想チャネルを示すブロック図である。 図４は、ＡＭＴネットワーク内における仮想経路および仮想チャネルの交差接 続(cross connection)および交換を示すブロック図である。 図５は、種々の対応するサービス・クラスおよび規格の層を示す、ＣＣＩＴＴ Ｂ−ＩＳＤＮ基準モデルを示す図である。 図６は、仮想賃借ライン（ＶＬＬ:virtual leased line）サービスを提供する 代表的なＡＴＭネットワークを示す図である。 図７は、ＡＴＭ交差接続を含む多層ＳＤＨを基本とする転送ネットワークを示 す図である。 図８は、仮想経路および物理リンク間の接続状態の関係を示す図である。 図９は、物理ネットワーク上で定義された仮想経路を割り当てる、代表的なプ ッシュ・ダウン・アルゴリズムの種々のステップを示すフロー・チャートである 。 図１０は、本発明に関係するエントロピ比率関数の特性を示すグラフである。 図１１は、図１０に示すエントロピ比率関数に関係するシフト・パラメータの 特性を示すグラフである。 図１２は、本発明に関係するエントロピ比率関数を用いた仮想経路割り当てア ルゴリズムの種々のステップを示すフロー・チャートである。 好適実施例の説明 従来のネットワーク内における輻輳制御 まず図1に移ると、複数の市内交換局２１ないし２６を含み、その各々には電 話機２７で表された、複数の市内加入者(local subscriber)が接続されている、 従来の公衆遠隔通信ネットワークの代表的な概略図が示されている。２カ所の市 内交換局２１および２４は、付随する遠隔加入者多重化段２８および２９を有す るものとして表されている。一方、多重化段２８および２９には、市内の顧客２ ７が接続されている。図１のネットワークは、更に、複数の中継線交換局３１な いし３４も含み、これらは主に種々の市内交換局を互いに相互接続し、ネットワ ークの種々の部分間にルートを設けるように機能する。中継線交換局３１は、移 動交換局３５に接続されたものとして示されている。移動交換局３５は、３８で 表した複数の移動無線電話加入者にサービスを提供する、１対の代表的な基地局 ３６および３７を含む。加えて、データベースやインテリジェント・ネットワー クのような他の遠隔通信サービスも、図示の交換局の様々なものに接続可能であ る。ネットワーク内の交換局２１ないし３５の各々の間には、複数の通信経路３ ０が示されており、各通信経路は、ケーブル、光リンクまたは無線リンクを含む 、複数の通信回路を含み、ネットワーク内の種々の交換局間で音声の搬送および ／またはデータ通信を行うことができる。 また、図１のネットワークは、通信リンク４１（点線で表す）によってネット ワーク内の交換局２１ないし３５の各々に接続され、各交換局に制御信号を送信 すると共に、各交換局からトラフィック・データを受信する、ネットワーク制御 システム４０を含む。ネットワーク制御システム４０はコマンドを発行して、ネ ットワークの種々のトラフィック・ルート内の通信経路を動的に再構成すると共 に、ネットワークの交換局内の警報システムを制御し、ネットワーク内の輻輳状 態軽減を図る微調整を行う。 ＡＴＭシステムの概要 公衆遠隔通信転送ネットワーク内では、現在多数の変化が起こりつつあり、し かも実施に移されつつある。公衆遠隔通信ネットワークの運営の主な目的の１つ は、共通インフラストラクチャ内の全てのタイプの遠隔通信サービスの転送およ び交換を処理する、単一形式の技術を普及させることであった。かかる技術の1 つが非同期転送モード（ＡＴＭ）技術である。 ＡＴＭは現在、実質的な「帯域幅粒状化」（bandwidth granularity）を有し 、非常に高い帯域幅接続性に対処可能な、ベアラ遠隔通信ネットワーク(bear er telecommunications network)を作成することによって、これらの必要性を満た すという試みにおいて実施されている。「帯域幅粒状化」という用語は、呼によ って要求される帯域が呼の期間にわたって自由に変更可能なネットワークの特性 に言及するものである。 公衆遠隔通信ネットワークにおいてＡＴＭ技術を使用することにより、関連す るサービスのスイッチングおよび転送の共通化、帯域幅粒状化の促進、可変ビッ ト・レート・サービスへの対応、およびマルチメディア・サービスへの対応とい うような機能を設けることが可能となる。これらの特徴のために、ＡＴＭは、国 際電信電話諮問委員会（ＣＣＩＴＴ）によって、広帯域ＩＳＤＮ（Ｂ−ＩＳＤＮ ）サービスのための中核技術として選択された。これは、低速等時性サービスに 対するトランシット遅延や、ネットワークに付加される複雑度、新たな性能パラ メータ（セル損失や輻輳のような）の導入のような、ＡＴＭの欠点ににも拘わら ずなされたのである。本発明のシステムは、この新たな性能パラメータの導入に 対処するものであり、これについて以下で更に詳しく記載する。 ＡＴＭネットワークは、独立同期デジタル階層（ＰＤＨ：plesiochronousdigi tal hierarchy）または同期デジタル階層（ＳＤＨ：synchronous digitalhierar chy）のいずれか、あるいは双方を用いて実施可能である。更に、純粋な ＡＴＭは、ＡＴＭおよびＳＴＭ（同期転送モード）間の多数の会話に起因する限 界がある場合はいつでも、ネットワークのベアラとして用いることができ、結果 的に発生する性能低下に対処することができる。 図２に示すＡＴＭセル構造は、ＡＴＭ技術の中核にある。ＡＴＭセルは、５３ バイト、即ち、オクテットの固定長を有し、５オクテットのヘッダおよび４８オ クテットの情報フィールド（ペイロードとしても知られている）に分割されてい る。ＡＴＭセル・ヘッダは、番号フィールドとして構成され、その主要な機能の １つは、ＡＴＭセルの発信地点から宛先地点まで１つ以上のスイッチング・ノー ドを経由してその経路を決定するのを助けることである。各ＡＴＭセルに保持さ れる情報は、比較的少量に維持することによって、スイッチング・ノードにおけ る内部バッファを小型化すると共に、これらバッファ内における待ち行列の遅延 を制限している。ＡＴＭは接続指向モード(connection-oriented mode)で動作す る。これは、モデリングの視点からは重要なことである。何故なら、既に確立さ れている回路切り替え数学モデル(circuit-switched mathematical model)を用 いて、ネットワーク資源の割り当ておよび制御の最適化を行うことが可能である からである。 ＡＴＭセル・ヘッダの主要な機能は、仮想接続の識別である。ＡＴＭセル内の 経路決定情報は、２つのフィールド内に収容される。即ち、どの仮想経路にＡＴ Ｍセルが属するのかを示す仮想経路識別子（ＶＰＩ）、および仮想経路内のどの 仮想チャネルにセルが属するのかを示す仮想チャネル識別子（ＶＣＩ）である。 仮想チャネルは、動的に配分可能な終端間接続である。光伝送リンクは、毎秒 数百メガバイトを搬送することができ、一方仮想チャネルは毎秒リンクの数キロ ビットを充たし得るに過ぎない。したがって、単一の伝送リンク上で、大多数の 同時仮想チャネルを支援することができる。 一方、仮想経路は、終点間の半永久的接続である。各仮想経路は、同時に接続 された多数の仮想チャネルを搬送することができる。仮想チャネルの大きな群が 一括して単一の単位として扱われ切り替えられるので、仮想経路の全処理要件は 仮想回路のそれよりも少なく、その結果、（仮想）回路当たりの処理は高速化し 、ネットワーク資源の格段に効率的な使用が可能となる。仮想経路のネットワー ク 管理は比較的単純で効率的である。 図２に示すように、ＡＴＭセル・ヘッダは、ネットワーク・ノード・インター フェース（ＮＮＩ）と比較すると、ユーザ・ネットワーク・インターフェース（ ＵＮＩ）において多少異なる。ＵＮＩは汎用フロー制御（ＧＦＣ）に４ビットを 含み、端末およびネットワーク間で使用可能な容量の公正かつ効率的な使用を保 証するために用いられる。ペイロード・タイプ・インディケータ（ＰＴＩ）フィ ールドが、ＡＴＭセルがユーザ情報または、例えば、保守の目的のための特殊ネ ットワーク情報のどちらを含むのかを示すために用いられる。セル損失優先度（ ＣＬＰ）フィールドは、２レベルの優先度を符号化し、ネットワーク状態のため にセルを破棄しなければならなくなったときに用いる。ヘッダ情報は、ヘッダ・ エラー制御（ＨＥＣ）フィールドに含まれるチェック・サムによって保護されて いる。 ＡＴＭセルの使用によって、情報転送レートを実際のサービス要件に適合させ ることが可能となる。必要とされる容量に応じて、単位時間当たりのセル数は、 データを搬送するために用いられる物理的媒体の伝送ビット・レートの限度まで 増加させることが可能である。データ・セルに加えて、信号、保守、およびアイ ドル・セルもある。信号セルは、ネットワーク内のエンド・ユーザ間、またはネ ットワーク内のノード間で用いられ、それらの機能は、例えば、接続といったサ ービスを設定することである。保守セルは、ＡＴＭレイヤの監視を行い、一方ア イドル・セルは伝送容量を伝送媒体の定格(rate)まで満たすために用いられる。 図３を参照すると、ＡＴＭリンク内の仮想チャネルおよび仮想経路のスイッチ ングおよび交差接続を図示したブロック図が示されている。スイッチの設計者の 視点からは、「ＶＰスイッチング」は、識別子フィールドの上位部分、即ち、短 縮フィールド(ＶＰＩ：shorter field)のみを用いるＡＴＭセルのスイッチング のことである。対照的に、「ＶＰ／ＶＣスイッチング」では、識別されたフィー ルド全体が用いられる（ＶＰＩおよびＶＣＩ双方）。ＶＰ／ＶＣ経路は、複数の 相互接続ＶＰ／ＶＣ長から成る。スイッチングおよび交差接続は、ＶＰレベルま たはＶＣレベルのいずれかで行うことができる。仮想経路識別子（ＶＰＩ）およ び仮想チャネル識別子（ＶＣＩ）は、ＡＴＭ回路内において、２段処理および経 路指示構造を定義する。ネットワーク・アーキテクチャの観点からは、仮想経路 （ＶＰ）は、１群の個々の接続であり、ＡＴＭネットワークのルート・マップに おける「ハイウエイ」の一種である。ネットワーク管理における重要なタスクの １つに、正しい量の伝送容量をかかるハイウエイ（即ち、仮想経路）の各々に配 分し、ネットワークの性能の最適化を図ることがあげられる。この最適化のタス クは、帯域幅管理または仮想経路割り当て技法の目的であり、以下で詳しく論ず るように、本発明の一態様の主題である。 次に図４を参照すると、仮想経路および仮想チャネルの交差接続ならびにスイ ッチングの概念が示されている。仮想経路識別子（ＶＰＩ）および仮想チャネル 識別子（ＶＣＩ）値は、特定のリンクに対してのみ有効である。各交差接続／ス イッチにおいて、新しいＶＰＩ／ＶＣＩ値がセルに割り当てられ、物理ポートと ＶＰＩ／ＶＣＩ値との組み合わせによってＡＴＭセルの識別を行う。次に、以下 の表１に示すような、変換テーブルを用いて、ＡＴＭセルの一例の経路指定を行 う。 ＡＴＭセルはＡＴＭ転送システム内における基本的な多重化単位であり、各セ ル即ち情報単位は、それ自体の接続および経路指定情報を含む。この特徴によっ て、サービス・チャネルの直接的な多重化およびデマルチプレクスが可能となり 、各チャネルは異なるビット・レートでの搬送を行うことができる。各ＡＴＭセ ルは、仮想経路識別子（ＶＰＩ）フィールドおよび仮想チャネル識別子（ＶＣＩ ）フィールド内のヘッダに含まれている情報によって識別され、その経路が指定 される。上述のように、仮想経路（ＶＰ）は、２つの終点、例えば、スイッチン グ・システム、ローカル・エリア・ネットワーク（ＬＡＮ）のゲートウエイ、ま た は私用ネットワークのゲートウエイ間の多重化回路の１群である。ＶＰは、仮想 経路終端間に直接論理リンクを設け、ＶＰＩ値は特定の仮想経路を識別する。 また、上述のように、ＡＴＭ技術において用いられている仮想経路の概念は、 多数の仮想チャネル（ＶＣ）を単一の単位としての処理を可能とする。共通の特 性、例えば、同じサービス品質（ＱｏＳ）を有する仮想チャネルは、一括してに 群に集合化することができ、これを１つの単位として搬送し、処理し、管理する ことができる。この柔軟性のある集合化(bundling)によって、ＡＴＭシステムの 処理および保守が簡略化される。 仮想経路および仮想チャネルの双方は、ＡＴＭネットワーク内に半永久的な経 路を設けるために使用することができる。ルートは、経路に沿った交差接続機器 またはマルチプレクサ内に「経路接続テーブル」を設定することによって、処理 支援システムから確立または解放される。また、仮想チャネルは、要求に応じた スイッチングにも使用可能であり、ユーザおよびネットワーク間またはネットワ ーク内のいずれかで信号を送信することによって、接続が確立される。 ＡＴＭ技術の１つの重要な特徴は、そのプロトコル・アーキテクチャに関連し 、いわゆる「中核および縁」原理に基づいて構築される。再伝送、フロー制御、 および遅延等価のような、転送される情報タイプに特定的なプロトコル機能は、 ＡＴＭネットワークの「縁部」にある端末において実行される。このため、単純 なセルの搬送およびスイッチング機能のみを含む、効率的でサービスに独立した 「中核」のネットワークが残る。この中核におけるＡＴＭノード内には、情報フ ィールドに対するエラー・チェックも、フロー制御も全くない。セル情報は単に 読みとられ、次いでＨＥＣを用いて、アドレスに影響を及ぼし得る単一ビット・ エラーを補正し、セルはその宛先に向けて切り替えられる。 ＡＴＭアダプテーション・レイヤ（ＡＡＬ：ATM adaptation layer）は、ネッ トワークの縁部において、提供されるサービスを強化するために用いられる。図 ５に示すように、Ｂ−ＩＳＤＮサービスのＣＣＩＴＴ基準モデルは、ＡＡＬがサ ービスに依存した機能を含むことを念頭に入れている。図５に示すように、ＡＴ Ｍ規格には３つのレイヤがある。第１レイヤは物理インターフェースおよびフレ ーミング・プロトコル(framing protocol)を定義する物理レイヤである。第２Ａ ＴＭレイヤは、選択された物理媒体には独立しており、セル構造を定義し、多重 化、デマルチプレクス、およびＶＰＩ／ＶＣＩ変換を行って論理ネットワーク内 のセルの流れを制御する。第３レイヤは、サービスおよびＡＴＭレイヤ間の重要 な適合化を行うことにより、サービスに独立したＡＴＭ転送を可能にするＡＡＬ である。ＡＡＬは、元のサービス・フォーマットと、ＡＴＭセルの情報フィール ドとの間のマッピングを行う。ＡＡＬによって与えられる機能の例には、可変長 パケット描写(variable-length packet delineation)、シーケンスの付番、クロ ック再生、および性能の監視が含まれる。 遠隔通信ネットワークにおけるＡＴＭの展開 ＡＴＭ技術の使用の１つとして、顧客の構内において用い、顧客のローカル・ エリア・ネットワーク内およびローカル・エリア・ネットワーク間における高速 データ通信を支援することができる。加えて、ＡＴＭは、音声およびビデオ通信 、データ転送、およびマルチメディアの応用を含む、顧客の構内ネットワークに おけるサービス全てに共通のインフラストラクチャ資源として用いることができ る。 ＡＴＭノードを公衆遠隔通信ネットワークに導入するサービスの一例は、仮想 賃借ライン（ＶＬＬ）サービスを提供することである。ＶＬＬサービスは仮想経 路の概念を基本とし、回線容量を直接顧客の要望に合わせて決定したり、インタ ーフェース構造を変更せずに容易に変更することを可能にする。ユーザ・ネット ワーク・インターフェース（ＵＮＩ）を通じて多数の論理接続をユーザに提供す ることができる。顧客に合わせたサービス品質を顧客に提供し、ユーザの要望に 沿うようにすることも可能である。したがって、多数のサービス・クラス、サー ビス・クラスの品質、および性能パラメータを選択することができる。例えば、 音声サービスは伝送遅延が少ないことを必要とするが、高いビット・エラーを許 容することができ、一方データ通信はネットワーク遅延に対してはより寛容であ るが、ビット・エラーには敏感である。したがって、特定用途のサービス・レベ ルの品質を、サービス・プロバイダおよび顧客間の契約によって合意し、手動で または自動的に検査することにより応諾を確認することができる。 図６に示すように、ＡＴＭネットワーク内に実施した、仮想チャネルを基本と するＶＬＬサービスの一例がある。ネットワーク端末ＡないしＥは、各々フロー 告示ノード(flow enforcement node)６０１ないし６０５を通じてＡＴＭ交差接 続ノード６１１ないし６１４にそれぞれ結合されている。ＡＴＭネットワークは 、複数のＡＴＭ交差接続６１１ないし６１４から成り、これらは、仮想経路およ び仮想チャネル・レベル双方における経路決定を行うことができる。フロー告示 機能６０１ないし６０５は、ＡＴＭネットワークの縁部に配置され、潜在的な過 負荷からネットワークを保護する。この機能は、接続が設定されたときに同意し た条件に違反する接続がないことを保証する。１つ以上の交差接続ノード６１１ ないし６１４にサービスを追加することにより、追加サービスを実施することが できる。図６のネットワーク内において、仮想経路の一例が、端末ＣおよびＤ間 の波線６２１によって示されている。端末ＡおよびＢ間の第１仮想接続が破線６ ３１によって示され、一方第２仮想接続が、破線６３２によって示されるような 、端末ＣおよびＥ間の破線によって示されている。 図６に示すような仮想賃借ラインネットワークに加えて、ＳＭＤＳ／ＣＢＤＳ およびフレーム・リレー(frame relay)のような他のサービスも、ネットワーク 内のＡＴＭノードにサーバを接続することによって、要求に応じて容易に追加す ることができる。住居区域では、ＡＴＭ技術は、オン・デマンド・ビデオのよう な新しい拡張娯楽サービス(enhanc edentertainment service)をエンド・ユーザ に提供するために使用することができる。ＡＴＭネットワークの柔軟性は、長距 離教育、ホーム・ショッピング、およびゲームのような多数のサービスへの対応 を可能とする。 図７は、ＳＤＨを基本とするレイヤ型転送ネットワーク上に重ね合わされたＡ ＴＭネットワークを示す。レイヤには、顧客構内ネットワーク・レイヤ７０１、 市内転送ネットワーク・レイヤ７０２、地域転送ネットワーク・レイヤ７０３、 および国内転送ネットワーク・レイヤ７０４が含まれる。複数のＡＴＭビジネス ・ネットワーク・ノード７１１ないし７１４が、顧客構内端末７１５およびＬＡ Ｎ７１６から、市内転送ネットワーク７０５内のＳＤＨ交差接続ノード７２２に 仕える複数の追加−削除マルチプレクサ(ＡＤＭ:add-drop multiplexer)７２１ の各々へのデータの流れを制御する。市内交差接続ノード７２２は、地域転送ネ ットワーク内の地域交差接続ノード７３１を通じて結合され、その内の２つは 追加−削除マルチプレクサ７３２によって結合されている。市内転送ネットワー ク・レイヤ７０２内では、１対のＡＴＭアクセス・ノード７２３、および追加− 削除マルチプレクサ７２１から成るＳＤＨリングが、交差接続７２２に仕え、最 大ＳＴＭ-１（毎秒１５５メガビット）までの容量、即ち、Ｂ−ＩＳＤＮサービ スに対する標準化されたアクセス・レートの加入者のアクセスのために用いられ る。 単一型旧電話サービス（ＰＯＴＳ:Plain Old Telephone Service）のような既 存のトラフィックは、このリング・ネットワーク上を搬送することができ、遠隔 マルチプレクサおよびその他のアクセス・ノードは、最終的な市内ループ接続を 与える。ＡＴＭアクセス・ノード７２３は、１カ所からの異なるサービスへのア クセスのために共用され、異なるＶＰ／ＶＣを用いて音声およびデータ双方を含 むことができる。ＡＴＭアクセス・ノード７２３では、ＡＴＭトラフィックを集 中し、搬送容量を一層効率的に利用するようにしている。 ＡＴＭアクセス・ノードのサイズは、必要な容量に応じて、小さなマルチプレ クサから大きな交差接続まで変化することができる。地域搬送層７０３では、Ａ ＴＭ交差接続７３３は、市内区域間でトラフィックの経路を決定するために用い られる。図７に示す国内搬送ネットワーク・レイヤ７０４では、ＡＴＭは不可視 である。ＡＴＭオーバーレイ・ネットワークでは、図７に示す場所に、フレーム ・リレーやＳＭＤＳ／ＣＢＤＳ等のサービスが容易に追加される。Ｂ−ＩＳＤＮ に対する機能(functionality)も適切なソフトウエアおよびハードウエアを追加 することにより、アクセス・ノードおよび地域ノードの双方に追加することがで きる。また、図７に示すように、ＣＣＩＴＴのＴＭＮ規格に準拠して動作するも ののように、ネットワーク管理システム７５０を実施し、必要なネットワーク管 理機能を、ネットワークのＳＤＨおよびＡＴＭ要素の双方に設けることができる 。 サブシステム７５０によるＡＴＭネットワークの管理は、本願の譲受人である 、Telefonaktiebolaget LM Ericssonによって供給されるネットワーク管理シス テムの遠隔通信管理および運営支援（ＴＭＯＳ）ファミリにしたがって実施すれ ばよい。かかるネットワーク管理は、以下に詳細に記載する本発明の教示にした がって実施される経路決定アルゴリズムや輻輳制御のような種々の機能を含むこ と も可能である。 仮想経路容量の割り当て 遠隔通信ネットワークの割り当てを行う有用なモデルは、割り当て問題を、個 別の接続形態および指定されたリンク容量を有する第１物理ネットワーク・レイ ヤと、仮想経路およびそれらの特定の経路決定法を有する第２仮想レイヤとから 成る二層構造を伴うものとして扱うことである。トラフィックの要求は、このモ デルにおいて、仮想経路に与えられる。ネットワーク容量を割り当てるタスクの みを扱う際、仮想経路は、事実上、既に経路が決定されている。各仮想経路は、 多数の物理リンクを経由して進むが、単一経路のみから成るハイウエイをエミュ レートする。各仮想経路は、１つの特性ブロック化値と、１つの特性割り当て容 量値とを有し、仮想経路と同じ数の変数のみがモデル内にある。 「提供トラフィック(offered traffic)」という用語は、各仮想経路に沿った 伝送容量に対する時間可変要求のことを言う。また、「トラフィック要求」とい う用語は、各リンクに対して提供されたトラフィックの時間平均値を示すために 用いる。ＡＴＭネットワーク上のトラフィックの特性は、単一パラメータのポア ソン分布によるモデル化が可能であり、トラフィックを同質な単一クラスのトラ フィックと呼ぶ。提供トラフィックが非同質である場合、通常マルチクラスのポ アソン分布を用いてこれをモデル化する。 また、提供トラフィックは、正規分布によるモデル化も可能である。これを正 規トラフィックと呼ぶ。最後に、ネットワークの割り当ては、測定によって決定 される実際のトラフィックを基準にすることも可能である。 多数のユーザの伝送要求は、結合して集合化したトラフィック・ストリームに することができる。例えば、数人のユーザがダラス(Dallas)からストックホルム （Stockholm）に同時に(contemporaneously)メッセージを送ることができる。こ れら多数の伝送を別個に管理する代わりに、これらを集合化して広帯域トランク ・ライン上を伝送すれば一層効率的である。先に論じたように、仮想チャネルは 、動的に割り当て可能な終点間接続である。仮想経路は、多数の仮想チャネルを 単一の単位として一括して扱い切り替えが可能な論理構造である。この統一した スイッチングによって、全体としての処理要件の低減、および伝送の高速化が得 ら れる。仮想経路の管理は仮想チャネルまたは個々の物理回路の管理よりも単純か つ効率的であるので、この技法によってネットワーク資源利用の大幅な改善が可 能となる。 仮想経路割り当てモデル 検討対象とする基本モデルは、固定経路(fixed routing)で動作する接続指向 ネットワーク(connection-oriented network)のそれである。物理ネットワーク を、１組Ｊの任意に接続されたリンクから成るものとして定義すると、各仮想経 路（ＶＰ）即ちルートｒは、要素がＪの副集合である、順序付けされたリストと なる。仮想経路および物理リンク間の関係は、ルーティング・マトリクス(rooti ng matrix)χに関して定義することができ、その要素は、 となる。 図８は、仮想経路および物理リンク間の接続形態関係を示す。図８において、 仮想経路ＶＰ1は物理リンクＰ1およびＰ2から成り、仮想経路ＶＰ2は物理リンク Ｐ2およびＰ3から成る。 種々のＶＰに割り当てられる容量と、物理リンクに割り当てられる対応する容 量との量的関係は、以下のようなマトリクスで与えられる。 ここで、χは（式１）で先に定義したタイプのルーティング・マトリクスであり 、ＣＶＰは仮想経路容量ベクトル、Ｃphysは物理リンク容量ベクトルである。 種々のＶＰに割り当てられた容量を表す物理リンク容量ベクトルＣphysは、物 理リンクのいずれにおいても、使用可能な物理容量を超えることはできない。こ の制限は、単純な制約関係によって表すことができる。 るベクトルである。（式３）はベクトル不等式であるので、双方のベクトルの対 応する成分はこの不等式を満足することを注記しておくのは重要である。図８に 示す単純な例では、ルーティング・マトリクスｘは、となり、ここで、仮想経路容量とＶＰに割り当てられる対応する物理リンク容量 との関係は、 は、物理リンクに対して割り当てられたベクトルである。 所与のルートｒに対する呼要求プロセスは、全ての呼を受け入れ全てのブロッ ケージ(blockage)を回避する無限容量を有する資源が当該プロセスに供給される とした場合の疑似占有分布(fictitious occupancy distribution)として公知の 、いずれかの固定プロセスとすることができる。Ｘｒは、この疑似無限容量資源 の占有レベルを示し、当技術では一般的に「提供トラフィック」と呼ばれている 。 仮想経路割り当て問題は、２つの目的を有する本発明のシステムおよび方法に おいて定義される。第１に、各仮想経路に配分される伝送容量を最適化し、伝送 コスト関数を最小にしなければならない。第２に、各物理リンクについて、この リンクを通過する種々の仮想経路に配分される容量は、当該物理リンクの物理伝 送容量の制約を超えてはならない。 種々の仮想経路に配分可能な物理容量は、範囲「０，Ｃphys］内のあらゆる実 数値を取る連続関数によって近似することができる。結果的に、資源最適化タス クは、個別の最適化や、それに付随する複雑性の全てが不要となる。本願におい て対処しようとしている割り当て問題では、異なるＶＰ間で共用する負荷につい ては検討しなかった。提供トラフィックは、各仮想経路について定義されるもの と仮定する。更に、ネットワークは固定経路指定を有するので、提供トラフィッ クの経路指定は、仮想経路の選択によって固定化される。 「プッシュ・ダウン」割り当て技法 仮想経路割り当てタスクは、本発明では負荷均衡化問題として見なされ、「負 荷」は適切に選択されたブロック化の尺度の値であり、最適な解は、仮想経路の 各々におけるブロック化ができるだけ均一に分散されるような、ＶＰ容量の配分 の選択に対応する。ブロック化分散を均一にする１つの方法は、種々の仮想経路 上のブロック化の値における発散を測定し、次いでこの発散を最小化することで ある。この手法は、標準的な最小化アルゴリズム、例えば、公知の模擬アニーリ ング技法(simul atedanealing technique)を用いて実施することができる。 関連する手法は、最初に最大のブロック化値を有する仮想経路を識別し、次に 、この仮想経路が最大のブロック化を有するＶＰではもはやなくなるまで、他の ＶＰから容量を再配分することによって、この仮想経路に対するブロック化を最 小にすることであろう。この形式化(formulation)は、最小−最大最適化問題に 対応し、以下に述べるように分析的に形式化することができる。 ｉ番目の仮想経路上におけるブロック化をＢ（ＶＰi）で示すとすると、最大 のブロック化を有するＶＰはｍａｘ（Ｂ（ＶＰi））であり、この場合最大値は 全てのＶＰに当てはまる。仮想経路集合に対するブロック化尺度の最大値は、Ｖ Ｐ割り当て問題に対する目的関数（コスト関数としても知られている）を定義す る。したがって、最適化手順の目標は、目的関数の最小値を見いだすことであり 、これは、 に対応する。ここで、最小値は全ての実現可能な構成に対して定義される。 この技法は、検討対象のＶＰ全ての間に最高のブロック化値を押し出す(pushd own)ことを伴うので、この技法を用いて最適化問題を解決するアルゴリズムのこ とを、「プッシュ・ダウン」アルゴリズムと呼ぶ。このアルゴリズムは、均一な ブロック化分布は、制約を受けないＶＰの割り当て問題の最良の解に対応すると いう事実に基づくものである。したがって、最良の解は、ＶＰの各々におけるブ ロック化をエラー境界内で等しくするように各ＶＰに容量を配分することである 。しかしながら、このような解は、種々の物理リンクの容量の制約のために、常 に実現可能とは限らない。物理リンクの容量が限られているため、当該物理リン クと交差するする全てのＶＰ間で共用する必要がある。 図９は、物理ネットワーク上で定義された仮想経路に割り当てるためのプッシ ュ・ダウン・アルゴリズムの代表的実施例の１つにおける種々のステップを示す 。この割り当てプロセスは、ステップ９０２における、種々のＶＰの接続形態の 定義から始まる。種々のＶＰは、ＶＰ割り当て集合にも組み入れられる。次に、 ９０３において、ＶＰは、それらの各々が交差する物理リンクの順に集合化され る。次に、９０４において初期の伝送容量の配分を各ＶＰに行う。９０５におい て、ブロック化の削減に対する目標値を選択する。目標を設定するためには、ま ずブロック化尺度を選択しなければならない。本発明の一好適実施例では、続く 章で詳細に説明するエントロピ比率関数を、ブロック化尺度として用いる。目標 値を用いて割り当てアルゴリズムに対する終了状態を設定する。 物理リンク各々におけるＶＰ各々のブロック化を９０６において決定する。単 一の物理リンクと交差する種々のＶＰが同一または同様のブロック化レベルを有 していない場合、現在各ＶＰに配分されている容量を９０７で見直して、エラー 境界内で、これらＶＰに対するブロック化値を等しくする。容量をＶＰに追加す るには、未配分の物理容量の配分、または既に配分されている容量の生産性の低 いＶＰから生産性の高いＶＰへの再配分によって行うことができる。この容量再 調節は、物理リンクのいずれの容量制約にも違反せずに行われる。 このプロセスの結果、９０８において、１つ以上の物理リンクがこの最適化手 順におけるボトル・ネックとして識別される。ＶＰのブロッケージ(blockage)が 最も多く、そのブロッケージが容量の再配分では減少することができない物理リ ンクのことを致命リンク(critical link)と呼ぶ。各致命リンクは、当該物理リ ンクと交差するＶＰ上で達成可能な、最も低いブロック化を決定する。プッシュ ・ダウン・アルゴリズムの主要なタスクの１つは、最適化手順の各段階において 、所与の仮想経路集合について致命リンクの集合を識別することである。 一旦致命リンクが９０８において識別されたなら、この致命リンクと交差する 種々の仮想経路間で、各仮想経路に対するブロック化値を等しくするように、物 理容量の再配分を行うことができる。尚、ある物理リンクが致命リンクであるこ とが発見された場合、事実上、それに配分されている容量はない。したがって、 致命リンクを通過するＶＰ間における容量の再配分は、アルゴリズムがこの割り 当て手順の段階に達して初めて可能となる。 次に、９０９において、容量が配分されたＶＰを、未だ割り当てを必要とする ＶＰ全ての集合から除去する。これに対応して、９１０において、使用可能な物 理リンク容量を、以前のステップにおいて除去されたＶＰの配分容量分だけ減少 させる。 こうして、割り当て問題は、残りのＶＰ集合に対する最大のブロック化確率を 最小化する最適化問題に縮小される。これによって、繰り返し再入力可能アルゴ リズム(recursive re-entrant algorithm)を用いて、この手順を実施できるよう になる。 以前のステップからのブロック化値をここで残りの割り当て問題における初期 値として用いる。この最適化手順は、各物理リンクの容量を配分し終わるまで、 ９１１において繰り返し実行される。要約すれば、この貧欲型のアルゴリズムは 、全てのＶＰの完全な集合に対して割り当てを行うことから開始して、割り当て を行うために残っている仮想経路集合がヌル集合となると、９１２において終了 する。 ここで強調すべきは、ここで詳細に説明しているタイプのあらゆる割り当てア ルゴリズムの実行は、図９に示すステップの順序を同様に辿る必要がないという ことである。割り当てアルゴリズムのステップの内いくつかの実行順序は、実施 の詳細および収束の考慮点に基づいて、図９に示すものとは異なってもよい。 所与のＶＰ集合において分析的に致命リンクを識別する問題は、困難なタスク であることがわかっている。提供トラフィックおよび物理リンク容量の制約から 直接致命リンクを判定する公知の技法はない。したがって、本プッシュ・ダウン ・アルゴリズムは、繰り返し手法を用いて致命リンクを識別する。このアルゴリ ズムは、均一の大きなブロック化値を全てのＶＰに対して用いることにより、全 てのＶＰの初期化を行う。選択する初期ブロック化値は、最初に配分されるＶＰ 容量の値の合計が種々の物理リンクの使用可能な物理容量を超えないように、十 分大きくしなければならない。 最適化手順において残っている全ての仮想経路の集合においてブロック化の度 合いをゆっくりと均一に低下させることによって、致命リンクは、交差される物 理リンクの物理容量の制約に最初に違反したリンクとして、各レベルで識別され る。 エントロピ・ブロック化尺度を用いた割り当て 割り当てプロセスの各段階において致命リンクを識別する上述の手順の速度お よび効率は、モデリングに用いるブロック化尺度の複雑性に対する依存度が非常 に高い。従来より、アーランのブロック化尺度（時間輻輳ブロック化式としても 知られている）を用いて、ネットワークにおけるＶＰ容量の最適な配分を判定し ている。 エントロピ比率関数をブロック化尺度として用いることを含む本技法は、アー ランのブロック化尺度の使用によって得ることができるものよりも素晴らしい結 果を得ることができる。エントロピ比率関数の使用により、任意のトラフィック 分布のモデリングが可能となり、殆どの場合この計算は、他のブロック化尺度に 基づく計算に比較して、格段に速く行うことができる。また、致命リンクの繰り 返し探索の大幅な改善が可能であることもわかっており、これは、主にエントロ ピ比率関数が凸関数であるという事実に基づく結果である。エントロピ比率関数 を用いた割り当てアルゴリズムの説明に先だって、エントロピ比率関数の特性に ついて探求することは有用であろう。 ブロック化尺度としてのエントロピ比率関数 既に注記したように、ブロック化尺度の選択は、プッシュ・ダウン・アルゴリ ズムには非常に重大である。エントロピ比率関数に基づくブロック化尺度の一般 式を次に導出し、提供トラフィックを単一クラスポアソン分布およびマルチクラ ス・ポアソン分布によって交代してモデル化するという状況例に適用する。 エントロピ比率関数は当技術では公知であり、物理リンク・レベルにおける輻 輳をモデル化するために用いられている。例えば、J.Y．Hui，A congestion Mea sure for Call Admission and Bandwidth Assignment for Multi-LayerTraffic ，International Journal of Digital & Analog Cabled Traffic Systems(1990) を参照されたい。しかしながら、これまで、仮想経路レベルまたはネットワーク ・レベルのいずれにおいても、割り当てまたは計画問題のいずれを解くブロック 化尺度としてもこれまで用いられたことはない。加えて、エントロピ比率関数は 、物理リンクの「有効容量」の概念を定義するために用いられている。ここで詳 細に説明するエントロピ比率関数を用いた割り当て技法は、ポアソン分布に従う 提供トラフィックに限定される訳ではなく、本システムおよび方法は、測定によ って決定されるものを含む、あらゆるタイプの提供トラフィック分布にも等しく 良好に動作することを記しておくのは重要である。 飽和ブロック化確率(saturation blocking probability)は、トラフィック要 求が伝送容量の指定値を超える確率として定義することができる。また、飽和確 率は、「末尾確率」(tail probability)とも呼ばれる。何故なら、これは提供ト ラフィック分布の末尾の確率質量(probability mass)を示すからである。この末 尾確率に対する公知の近似法、即ち、チャーノフの境界(Chernoff's Bound)を以 下で導出する。 任意の分布ランダム変数をＸ、所与の値をＣとする。また、ｓの正値全てに対 して、以下の境界が存在することを示すことができる。 ここで、Ｐ（Ｘ＞Ｃ）はランダム変数ＸがＣよりも大きな値を取る確率である。 この境界の導出は、マルコフの不等式に基づくものである。項１ｎ（（Ｅ5x） ）は対数モーメント発生関数を示し、累計関数(cumulant function)μ（ｓ）と も呼ぶ。最も厳しい境界（チャーノフの境界として知られている）は、指数部ｓ Ｃ−μ（ｓ）をＳに対して最大化することによって得られる。この最大値は、ｓ ＝ｓ＊のときに到達する。ここでｓ＊は、式Ｃ＝μ’（ｓ）の唯一の正の解であ る。 μ’（ｓ）がｓと共に増加することを示すことによって、そのルート(root)の はＳと共に増加する。また、これは、二次導関数が（シフトした）分布の分散に 等しいという事実によるものである。この最大化する指数部をＩx（Ｃ）で示し 、エントロピ比率関数と呼ぶ。エントロピ比率関数は累計関数の凸状共役変換で あり、以下の式で記述することができる。 の不等式によって導出することができる。 エントロピ比率関数分布の右末尾および左末尾間の関係は、パラメータｓを用い て、次のように表すことができる。 I-x(-C(s))=Ix(C(-s)) （式１０） したがって、パラメータｓの符号を変えることにより、エントロピ比率関数分布 の右末尾から左末尾に、またはその逆に切り替えることができる。 同質ポアソン・トラフィックに対するエントロピ比率関数 提供トラフィックが同質な場合に仮想経路を割り当てるためのエントロピ比率 関数の使用について最初に検討する。同質ポアソン・トラフィックは、帯域幅要 求パラメータＰ、平均着呼率ｒ，および各呼の平均期間ｈ（平均保持時間とも呼 ぶ）によって特徴付けることができる。したがって、トラフィック要求ρは、平 均着呼率と平均保持時間との積、即ち、ｒ＊ｈである。同質トラフィックの累計 関数は、以下の関係によって記述する。 s)=ρ(esp-1) （式１１） 結果的に、同質トラフィックに対する配分容量Ｃ，およびエントロピ比率関数Ｉ は、 C=μ′(s)=ρpesp （式１２） および Ｉ（Ｃ）＝ｓ*（Ｃ）・Ｃ−μ（ｓ*（Ｃ）） （式１３） 即ち、 Ｉ（Ｃ（ｓ））＝ｓρｐｅsp−ρ（ｅsp−１） （式１４） で与えられる。 ことにより、（式１４）によって記述されるタイプの同質なトラフィックに対す るエントロピ比率関数も、以下のような配分容量Ｃの関数としてのみ表すことが できる。 図１０は、単位帯域幅要求ｐにおける提供トラフィックの異なる値に対するエ ントロピ比率関数の特性をグラフで表したものである。図１１は、配分容量Ｃの 関数として表したシフト・パラメータｓを示す。 図１０および図１１に示すように、エントロピ比率関数は、３つの重要な特性 を有する。第１に、これは凸関数であり、分布の平均、即ち、Ｃ＝ρの場合、そ の最大値である０に到達する。第２に、シフト・パラメータｓは、分布の平均、 即ち、Ｃ＝ρの場合、Ｃの値の増加に対して、負から正に移動する。図１１から わかるように、シフト・パラメータｓは、Ｃ＜ρのとき負であり、Ｃ＞ρのとき 正である。第３に、シフト・パラメータｓは単調であり、仮想経路に配分される 容量の関数として増加する。 変換パラメータｓは、したがって、確率分布シフト・パラメータとして解釈す ることができる。シフト・パラメータが負の値を取る場合、確率分布は、シフト ・パラメータのゼロ値に対応する確率分布に比較して、左にシフトされる。シフ ト・パラメータが正の値を取る場合、確率値は右にシフトされる。 マルチクラス・ポアソン・トラフィックに対するエントロピ比率関数 トラフィック・モデルは、マルチクラス・ポアソン分布によって特徴付けられ る提供トラフィックに拡張することができ、このような提供トラフィック・モデ ルに対応するエントロピ比率関数を次に導出する。 単一クラス分布に対するエントロピ尺度を、マルチクラス分布に対するエント ロピ尺度と置き換える際、エントロピ比率関数は、もはや配分容量Ｃに関して明 示的に表現することができないという難題が生じる。この問題を回避するために 、エントロピ比率関数を、制御パラメータとして利用するシフト・パラメータｓ に関して表現する。このパラメータの絶対値を増加させることによって、配分容 量を暗示的に変化させ、エントロピ尺度を正方向に増分させることができる。 ここで、クラスｉ（ｉはｌからｋまでの値を取る）のランダム・トラフィック をＸiで表すとする。各クラスのピーク帯域幅要求ｐi、平均着呼率ｒi、および 保持時間ｈiは、ρi＝ｒiｈi、およびランダム変数Ｘiの累積値の期待値が、 となるように定義する。 確率の負の対数の推定値であり、 ここで、ｋはトラフィック・クラスの数、Ｃはこの総合マルチクラス・トラフィ ックを搬送するＶＰに配分される容量である。 次の関係は、全ての分布に対して有効である、エントロピ比率関数の一般的特 性を表す。 マルチクラス・ポアソン・トラフィックに対する対数モーメント発生関数は、 次の関係で与えられる。 エントロピ比率関数は次の一般形を有するので、 マルチクラス・トラフィックに対するエントロピ比率関数は、シフト・パラメー タｓに関して、次のように表すことができる。 ここで、配分容量Ｃは、更に、関数的にシフト・パラメータｓに関係付けること ができる。 単一クラスのエントロピ尺度をマルチクラスのエントロピ尺度と置き換える場 合、エントロピ尺度はもはや配分容量Ｃに関しては明示的に表すことができない ので、問題は分析的に一層複雑化する。この複雑化は、シフト・パラメータｓを （式２２）から消去できないという事実によるものである。 しかしながら、（式２１）はシフト・パラメータｓに関するエントロピ比率関 数を表すので、Ｃを変化させる代わりにｓを変化させることができる。したがっ て、（式２２）を用いることにより、アルゴリズムの各繰り返しステップにおい て、容量値が計算可能となる。尚、ｓのゼロ値はエントロピ尺度のゼロ値に対応 することを注記しておく。割り当てアルゴリズムは、全てのＶＰについてｓをゼ ロにセットすることにより初期化される。 正規分布トラフィックに対するエントロピ比率関数 エントロピ比率関数は、ポアソン分布の提供トラフィック以外にも、他のトラ フィック・モデルと共に使用可能である。以下に、２つの別の重要なトラフィッ ク・モデルについて論ずる。第１のトラフィック・モデルは、提供トラフィック の正規分布に対するエントロピ比率関数に基づくものである。エントロピ比率関 数に対する対応する式は、このトラフィック・モデルについて導出される。第２ のトラフィック・モデルは、提供トラフィックの分布についての明示的な想定で はなく、実際のトラフィック・フローの測定から導出されるエントロピ比率関数 に基づくものである。 正規分布トラフィックに対するエントロピ比率関数は、以下の式によって定義 されることが示されている。例えば、R.S．Ellis，Entropy，Large Deviationsa nd Statistical Mechanics 39(Springer-Verlag，1985)を参照されたい。 ここで、ｍは平均、およびσは正規分布Ｎ（ｍ，σ）の分散である。更に、 これら２つの関係から、制御パラメータｓに関する直接的なエントロピ比率関数 に対する、次の単純な表現が得られる。 したがって、正規分布トラフィックの場合、エントロピ比率関数は、単純な（そ して凸状の）二次関数となることが示される。 測定トラフィックに対するエントロピ比率関数 将来のネットワークにおいて供給される多種多様のサービスは、今日入手可能 なものよりも格段に多いであろうから、将来の広帯域ネットワークでは、ネット ワークに提供トラフィックの種類も膨大となろう。その結果、トラフィック分布 の特定の理想化された表現についての想定に基づく全てのモデルは、それら本来 の柔軟性欠如のために、不適当となる可能性が高い。トラフィック測定から導出 されるエントロピ比率関数を用いることにより、この難しいトラフィック・モデ ル推定問題に対する１つの解を与えることができる。 これまで論じてきたトラフィック・モデルは、呼のレベルの時間目盛り(times cale)上で定義してきた。対照的に、トラフィック測定統計は、標準的なＡＴＭ セルの時間目盛り上で定義される。呼のレベルの時間目盛りは、セル・レベルの 時間目盛りの近似と見なすことができる。したがって、呼の間にランダムに変化 するトラフィック要求は、呼レベルの時間目盛り上で一定の帯域幅の要求を記述 する１つ以上のパラメータによって抽象化することができる。 最近、エントロピ比率関数は、セル・レベルでのトラフィック測定から推定可 能であることが示唆されている。例えば、N．G． Duffiel de tal.，Entorpy of ATM Traffic Streams: A Tool for Estimating QoS Parameters（Dublin Insti tute for Advanced Studies，1994）を参照されたい。 エントロピ比率関数上のトラフィック過負荷の影響 エントロピ比率関数のブロック化尺度としての解釈は、各物理リンク上で提供 される平均トラフィックが、当該リンク上の対応する使用可能な物理容量よりも この条件は、現実的な過負荷状況では、違反される場合もあり得る。一様なポア ソン・トラフィックおよび時間輻輳ブロック化尺度に基づく以下の例（即ち、ア ーランのブロック化式）を検討する。 表２は、０．０３に固定したブロック化値について計算された、配分容量およ び対応するトラフィック要求の３つの値を纏めたものである。最後の場合、提供 トラフィックは、ブロック化が比較的低いにも拘わらず、配分容量よりも大きい ことに注意されたい。 反した場合、過負荷状況を包含するために拡張する必要があることを示す。数学 的には、かかる拡張は容易に行うことができる。以前に示したように、エントロ ピ比率関数は、Ｅ（Ｘｋ）においてゼロの極小値を有する凸関数である。エント ロピ比率関数の左枝(left branch)は過負荷領域を定義する（図１０および図１ １参照）。この領域では、エントロピ比率関数の増加は、配分容量の減少、およ び制御パラメータの負値に対応する。制御パラメータの符号を変更することによ って、エントロピ比率関数に基づくプッシュ・ダウン・アルゴリズムは、過負荷 領域を包含するように容易に拡張することができる。かかる拡張には、元の割り 当てアルゴリズムを少し変更すればよい。 残される問題は、主に概念的な性質のものであり、即ち、この拡張をどのよう に解釈するかということである。エントロピ比率関数の左枝領域は、確率質量の 左末尾の近似に対応し、 配分容量Cの利用のエントロピ尺度として解釈することができる。 初期状態では、配分された資源は物理資源の容量を超えたので、即ち、 応するため、利用を減らさなければならない。 過負荷領域における最適化の目的の１つの解釈は、以下のように行うことがで きる。この領域のエントロピ利用尺度の分布の均一性を改善するために、最も大 きな資源の顧客（即ち、最も低いエントロピを有するＶＰ）を識別し、この極端 な代用の利用を減らす。最大顧客の利用を減らすことは、過負荷領域におけるエ ントロピ比率関数の増加に対応する。したがって、この手法は、最適化プログラ ムの最大−最小形式化(max min formulation)に対応する。尚、ここでは、初期 状態において過負荷領域に当てはまる値から始めることによって、制約条件を適 用することを注記しておくべきであろう。 また、ここでも、エントロピ利用尺度の均一分布の最良の資源利用への対応付 けを使用することができる（最良の利用が実現不可能であっても）。右枝領域に 関しても同じ推論に従うと、制約条件を満たすためには、エントロピ利用尺度を 各致命リンク上では均一とする。更に、致命リンクと交差する全てのＶＰの容量 は、これらのＶＰのエントロピ利用値が等しくなるように配分される。 既に論じたように、エントロピ曲線の右側領域における最適化の目的は、最も 高いブロック化を有するＶＰ（即ち、最小のエントロピ・ブロック化尺度を有す るＶＰ）に配分される容量を増加させることである。これは、最適化プログラム の最大−最小形式化に対応する。尚、左側領域に対する最適化の目的は、以前に 形式化した左側領域に対する最適化の目的において、「利用」という用語を「ブ ロック化」という用語に置き換え、「最大の資源の顧客」という用語を「最も大 きなブロック化を有するＶＰ」という用語に置き換えることによって、右側領域 に対する最適化問題に変換することができる。 エントロピ比率関数の左枝および右枝に対する最適化の目的のこれら２つの異 なる形式化の結果、同一の最適化手順が得られる。双方の場合において、エント ロピ比率関数を増加させる必要がある。これは、制御パラメータｓの絶対値を増 加させることによって行うことができる。負荷が使用可能な資源を超えない場合 、シフト・パラメータは正となり、種々の仮想経路に配分される容量は、使用可 能な物理資源を全て配分するまで、連続的に高くすることができる。一方、負荷 が使用可能な資源を超えた場合、シフト・パラメータは負になる。このような場 合、配分容量は、物理資源の制約内に収まるまで、徐々に減らす必要がある。 エントロピ比率関数を用いたＶＰ割り当てアルゴリズム これまで詳細に説明したエントロピ比率関数の特徴を、ＶＰ割り当て問題を効 率的に解くために適用することができる。既に説明したように、ＶＰ割り当て問 題は、限られた物理ネットワーク資源を、提供トラフィック分布が与えられた複 数の予め定義されているＶＰ間で配分することを意図するものである。エントロ ピ比率関数をブロック化尺度として用いるＶＰ割り当てアルゴリズムの一実施例 を図１２に示す。 このプロセスは、一連の初期化ステップ１２０２ないし１２０６から開始する 。１２０２において、割り当て対象のＶＰ全てを、ＶＰ割り当て集合に組み入れ る。１２０３において、ネットワーク内の各物理リンクに対する伝送容量の制約 を指定する。１２０４において、エントロピ比率関数に対する1組の上限ＩMAXを 、仮想経路毎に1つ任意に指定する。 ステップ１２０２ないし１２０４は、実施上の検討にしたがって、いずれの順 序で実行してもよいことを注記しておくべきであろう。更に、１２０４において ＩMAXを定義するのは、提供トラフィックの分布の右末尾が打ち切られる現実的 な可能性がある場合のみ、即ち、ある有限値ＣMAXよりも大きなＸの値に対して 、Ｐ（Ｘ＞Ｃ）がゼロとなる場合のみである。提供トラフィックの分布が、打ち 切られた右末尾を有する場合、ブロック化ゼロを達成するようにネットワーク資 源のサイズを決めることは、論理的には可能となる。しかしながら、かかる状況 は実際には希である。 他の初期化ステップには、ステップ１２０５における各仮想経路に対する大き く等しいブロック化値の選択が含まれる。どこかで説明したように、エントロピ 比率関数の値とＶＰ上の対応するブロック化との間には逆の関係がある。結果的 に、大きなブロック化値はエントロピ比率関数の小さな値に対応する。先に展開 した関係を用いて、１２０５において種々のＶＰに対する初期容量配分も計算す る。 １２０６において、これらの初期容量配分を、各物理リンクに関して累積し、 当該物理リンクの予め指定されている伝送容量と比較する。初期配分が、１つ以 上の物理リンクにおいて過負荷があるようなものである場合、続く計算ステップ を変更し、シフト・パラメータｓの負値に基づく式を用いる。この結果は、過負 荷状況に対するアルゴリズムは、割り当て問題のシフト・パラメータｓの負値へ の反映に対応するという事実による。 初期化プロセスに含まれる他のステップは、提供トラフィックのモデルを選択 することであり、このモデルが測定を基本としてエントロピ比率関数Ｉ、配分容 量Ｃ、およびシフト・パラメータｓに対する対応関係を導出するのではない場合 のことである。このステップは、図１２には示されていない。 初期化ステップ１２０２ないし１２０６の後、割り当て技法は、繰り返しステ ップ１２０７ないし１２１５を実行する。図１２に概要を示す繰り返し技法は、 ２レベルの繰り返しであり、まずＶＰ割り当てアルゴリズムが、１つ以上の物理 リンクが最大（即ち、１００％）利用に達するまで、１２０７ないし１２１０に おいて示したように設定されたＶＰ割り当てにおいて、ＶＰに容量を繰り返し配 分していく。 容量が最大に配分された物理リンクのことを致命リンクと呼ぶ。したがって、 ステップ１２０７ないし１２１０の実際の効果は、致命リンクを繰り返し識別す ることである。致命リンク識別手順は、繰り返し手順の各段階において、１つの 物理リンクのみを致命リンクとして識別する可能性があるが、このアルゴリズム は、実施された場合には、所与の時間で１つ以上の致命リンクの識別および処理 も同様に可能である。 本発明の一実施例では、致命リンクの識別を行うには、１２０７において、提 供トラフィック・モデルに従うエントロピ比率関数に対する関数式を用いて、あ る固定量だけ現エントロピ比率関数推定値を増分する。かかる式の例は、一様な ポアソン・トラフィックについては（式１５）、マルチクラス・ポアソン・トラ フィックについては（式２１）、および正規分布トラフィックについては（式２ ３および式２５）において見いだすことができる。尚、エントロピ比率関数の推 定値に対する増分値は、場合によっては負の場合もあることを注記しておくべき であろう。これが発生する可能性があるのは、割り当てアルゴリズムが最適値を 行き過ぎてしまい、容量を配分し過ぎた場合である。 シフト・パラメータｓの値は、１２０８において、割り当て集合内の各ＶＰに ついて計算される。シフト・パラメータ値は、対応するＶＰについて、図１０の エントロピ−容量グラフの傾斜を表すことを注記しておくべきであろう。割り当 て集合におけるＶＰに配分される増分容量は、１２０９において、エントロピ比 率関数の増分値を用いて計算される。ステップ１２０７ないし１２０９は、実施 の考慮に基づいて、図１２に示したのとは異なるシーケンスで実行してもよい。 次に、１２１０において、各物理リンクについて、種々のＶＰに配分された容 量を累計し、１２１１において当該物理リンクの全容量と比較する。リンクの未 配分物理容量が予め設定した限度未満である場合、そのリンクは致命リンクと判 定される。 比較の結果物理リンクが致命リンクと識別された場合、計算は１２１２に進む 。致命リンクである物理リンクが発見されなかった場合、致命リンクが発見され るまで、ステップ１２０７ないし１２１０またはそれらの同等物を繰り返し実行 する。提供トラフィック・モデルが打ち切り右末尾を有するという希な状況では 、ときとしてこの繰り返し手順は致命リンクを全く識別できなくなる可能性があ る。 かかる状況では、１２０４において指定されるように、エントロピ比率関数がそ の最大値ＩMAXに達したときに、計算は自動的に終了する。 致命リンクを識別した後、ＶＰ割り当てアルゴリズムは結果を出力し、１２１ ２および１２１３に示した問題の再形式化を行う。１つ以上の物理リンクが１２ １１において致命リンクであると識別される毎に、ＶＰ割り当てアルゴリズムは ステップ１２１２に進み、出力を発生して、致命リンクと交差する各ＶＰ上に現 在配分されている容量を詳しく知らせる。致命リンクと交差するＶＰは、１２１ ３において、割り当て集合から除去される。割り当てを行うべきＶＰがなくなっ た場合、割り当てアルゴリズムは１２１６において終了する。 割り当てを行うべき１つ以上のＶＰが残っている場合、１２１５において割り 当て集合を定義し直し、かかるＶＰのみを含むようにする。致命リンクと交差す るＶＰは割り当て集合から除去されたので、そしてこれら除去されたＶＰは物理 リンク容量の一部を使用していたので、割り当てタスクは割り当て集合内に未だ 残っているＶＰに対する未配分物理リンク容量の分配を減らす。これを行う際、 １２１５において、種々の物理リンクの使用可能な容量を、１２１１において最 後に発見された致命リンクに対応する、除去されたＶＰに配分されていた量だけ 減らす。本発明の別の実施例では、ＶＰ割り当て集合から除去されたＶＰに対す るエントロピ比率関数の値を凍結することによって、同じ効果が得られる。除去 されたＶＰに配分されていた容量は１２１２で発生されたので、この計算は容易 に実行可能である。１２１５における問題の再形式化の後、アルゴリズムは１２ ０７に戻り、先と同様、割り当て集合内に未だ残っている全てのＶＰに対して、 エントロピ比率関数を固定量だけ増分する。 以上、本発明の方法および装置の好適実施例について、添付図面に示しかつ上 述の詳細な説明に記載したが、本発明はここに開示した実施例に限定される訳で はなく、以下の請求の範囲に記載し定義した、本発明の精神から逸脱することな く、種々の再構成、変更および交換が可能であることは理解されよう。
【手続補正書】特許法第１８４条の８第１項 【提出日】１９９７年９月１５日（１９９７．９．１５） 【補正内容】 請求の範囲 １．汎用トラフィックを搬送する遠隔通信ネットワーク上で定義された仮想経 路を割り当てるコンピュータ実装方法であって、前記ネットワークは、伝送容量 が制限された複数の相互接続リンクを有し、前記割り当て方法は、 トラフィック測定値によって決定される適切なエントロピ比率関数を選択し、 前記遠隔通信ネットワークの各仮想経路上の負荷をモデル化するステップと、 前記エントロピ比率関数を、前記汎用トラフィックに対する負荷均衡化問題を 解くように動作するブロック化尺度として用いる解法アルゴリズムを選択するス テップと、 前記エントロピ比率関数を組み込んだ前記負荷均衡化アルゴリズムを用いて計 算機システム上で計算を行い、前記仮想経路上でできるだけ均一な負荷分散を生 成するステップと、 から成る仮想経路割り当て方法。 ２．前記エントロピ比率関数は、遠隔通信ネットワーク上の提供トラフィック の特徴を理想化することによって決定される請求項１記載の仮想経路割り当て方 法。 ３．前記エントロピ比率関数は、提供トラフィックの一様ポアソン分布に対し て理想化される請求項２記載の仮想経路割り当て方法。 ４．前記エントロピ比率関数は、提供トラフィックのマルチクラス・ポアソン 分布に対して理想化される請求項２記載の仮想経路割り当て方法。 ５．前記エントロピ比率関数は、提供トラフィックの正規分布に対して理想化 される請求項２記載の仮想経路割り当て方法。 ６．前記エントロピ比率関数は、提供トラフィックの二項分布に対して理想化 される請求項２記載の仮想経路割り当て方法。 ７．前記提供トラフィックをモデル化するために用いられるエントロピ・ブロ ック化尺度はエントロピ比率関数Ｉx（Ｃ）であり、該エントロピ比率関数は、 任意に分布されるランダム変数Ｘが予め選択されている値Ｃ以上である確率の負 対数の近似として計算可能であり、前記エントロピ比率関数は、更に、分布の平 均において、その最小値であるゼロを得る凸関数である請求項２記載の仮想経路 割り当て方法。 ８．前記エントロピ比率関数を、前記汎用トラフィックに対する負荷均衡化問 題を解決するように動作するブロック化尺度として用いる前記アルゴリズムは、 プッシュ・ダウン・アルゴリズムである請求項１記載の仮想経路割り当て方法。 ９．前記プッシュ・ダウン・アルゴリズムは、更に、 前記割り当て対象の仮想経路を、割り当て集合に組み入れるステップと、 前記選択したエントロピ比率関数を用いて、各仮想経路が交差する各ネットワ ーク・リンク毎に、前記仮想経路に関するブロック化を計算するステップと、 各ネットワーク・リンク上で、最も大きなブロック化を有する仮想経路を識別 するステップと、 前記識別した仮想経路が、もはや最も大きいブロック化を有さなくなるまで、 前記ネットワーク資源の制約に違反することなく、追加の容量を配分するステッ プと、 を含む請求項８記載の仮想経路割り当て方法。 10．前記プッシュ・ダウン・アルゴリズムは、更に、 全仮想経路を割り当て集合に集合化するステップと、 各物理リンクの伝送容量を指定するステップと、 各仮想経路に比較的大きな初期ブロック化値を選択するステップと、 致命リンク識別アルゴリズムの収束を評価するためにエラー境界を選択するス テップと、 エントロピ・ブロック化尺度を用いて、各仮想経路に対してブロック化値を決 定するステップと、 前記物理リンクが使用可能な容量を有する限り、最大のブロック化値を有する 仮想経路を繰り返し識別するステップと、 最大利用度に達した物理リンクがなく、最大に妨害を受ける仮想経路のブロッ ク化減少が予め選択されているエラー境界よりも大きい限り、前記仮想経路間に おいて伝送容量を再割り当てすることにより、最も大きなブロック化値を有する 仮想経路のブロック化を減少させるステップと、 配分可能な容量が不足する物理リンクを致命リンクとして識別するステップと 、 前記割り当て集合から、致命リンクに該当する全ての仮想経路を除去するステ ップと、 残りの物理リンクの伝送容量を繰り返し再調節し、前記割り当て集合から最後 に除去された仮想経路に配分されていた容量を反映するステップと、 を含み、前記割り当て集合がヌル集合となるまで、前記繰り返しステップを繰り 返す請求項８記載の仮想経路割り当て方法。 11．複数のノードを相互接続する複数の物理リンクを有し、制約のある遠隔通 信ネットワークを割り当てる方法であって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングし、前記仮想経路の 各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切り替え可能な接 続を設けるようにするステップと、 選択された複数の前記仮想経路を割り当て集合に集合化するステップと、 初期状態においてブロック化が大きくなるように、各仮想経路に初期伝送容量 を配分するステップと、 現在の値よりも低い値を後続のブロック化に選択するステップと、 単一の物理リンクと交差する前記仮想経路の各々に関してブロック化の計算を 行うステップと、 物理リンクが、未配分容量を有さないと識別されるまで、異なる仮想経路間の ブロック化における変動に応答して、単一の物理リンクと交差する仮想経路間で 、使用可能な伝送容量を配分するステップと、 前記識別された物理リンクと交差する全ての仮想経路を、前記割り当て集合か ら除去するステップと、 前記除去された仮想経路に以前に配分されていた量だけ、前記物理リンクの各 各に割り当てられる伝送容量を減少させるステップと、 前記計算、割り当て、除去、および減少ステップを、前記割り当て集合に仮想 経路がなくなるまで繰り返し実行するステップと、 から成る方法。 12．複数のノードを相互接続する複数の物理リンクを有する遠隔通信ネットワ ーク上で定義された仮想経路を割り当てる方法であって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングし、前記仮想経路の 各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切り替え可能な接 続を設けるようにするステップと、 各物理リンクの伝送容量を指定するステップと、 選択された複数の前記仮想経路を割り当て集合に組み入れるステップと、 エントロピ比率関数をブロック化尺度として用い、前記割り当て集合内の各仮 想経路に伝送容量の初期値を配分し、前記初期値の各々を等しく、かつ前記ブロ ック化が大きくなるように選択するステップと、 前記仮想経路が交差する物理リンク間で、容量が最大に配分されている物理リ ンクを致命リンクとして繰り返し識別するステップであって、 エントロピ比率関数推定値を固定値だけ増分するサブステップと、 前記割り当て集合内の各仮想経路に対してシフト・パラメータを再計算するサ ブステップと、 前記増分されたエントロピ比率関数推定値および前記再計算されたシフト・パ ラメータを用いて、各仮想経路に配分される容量を再計算するサブステップと、 各物理リンクについて、前記仮想経路の全てに配分された容量を合計し、各物 理リンク上の全配分容量を得るサブステップと、 各物理リンクの前記全配分容量を、その指定容量と比較し、前記物理リンクの 未配分容量が実質的にゼロか否かについて判定を行うサブステップと、 致命リンクとして識別された物理リンクと交差する仮想経路の各々に、現在配 分されている容量を出力するサブステップと、 各致命物理リンクと交差する全ての仮想経路を前記割り当て集合から除去する サブステップと、 前記物理リンクの指定された物理容量を定義し直し、前記除去された仮想経路 に配分されていた容量を補償するサブステップと、 によって実行する前記識別ステップと、 から成る方法。 13．汎用トラフィックを搬送する遠隔通信ネットワーク上で定義された仮想経 路を割り当てるコンピュータ実装システムであって、前記ネットワークは、伝送 容量が制限された複数の相互接続リンクを有し、前記割り当て方法は、 トラフィック測定値によって決定される適切なエントロピ比率関数を選択し、 前記遠隔通信ネットワークの各仮想経路上の負荷をモデル化する手段と、 前記エントロピ比率関数を、前記汎用トラフィックに対する負荷均衡化問題を 解くように動作するブロック化尺度として用いる解法アルゴリズムを選択する手 段と、 前記エントロピ比率関数を組み込んだ前記負荷均衡化アルゴリズムを用いて計 算機システム上で計算を行い、前記仮想経路上でできるだけ均一な負荷分散を生 成する手段と、 から成る仮想経路割り当てシステム。 14．前記エントロピ比率関数は、遠隔通信ネットワーク上の提供トラフィック の特徴を理想化することによって決定される請求項１３記載の仮想経路割り当て システム。 15．前記エントロピ比率関数は、提供トラフィックの一様ポアソン分布に対し て理想化される請求項１４記載の仮想経路割り当てシステム。 16．前記エントロピ比率関数は、提供トラフィックのマルチクラス・ポアソン 分布に対して理想化される請求項１４記載の仮想経路割り当てシステム。 17．前記エントロピ比率関数は、提供トラフィックの正規分布に対して理想化 される請求項１４記載の仮想経路割り当てシステム。 18．前記エントロピ比率関数は、提供トラフィックの二項分布に対して理想化 される請求項１４記載の仮想経路割り当てシステム。 19．前記提供トラフィックをモデル化するために用いられるエントロピ・ブロ ック化尺度はエントロピ比率関数Ｉx（Ｃ）であり、該エントロピ比率関数は、 任意に分布されるランダム変数Ｘが予め選択されている値Ｃ以上である確率の負 対数の近似として計算可能であり、前記エントロピ比率関数は、更に、分布の平 均において、その最小値であるゼロを得る凸関数である請求項１４記載の仮想経 路割り当てシステム。 20．前記エントロピ比率関数を、前記汎用トラフィックに対する負荷均衡化問 題を解決するように動作するブロック化尺度として用いる前記アルゴリズムは、 プッシュ・ダウン・アルゴリズムである請求項１３記載の仮想経路割り当てシス テム。 21．更に、 前記割り当て対象の仮想経路を、割り当て集合に組み入れる手段と、 前記選択したエントロピ比率関数を用いて、各前記仮想経路が交差する各ネッ トワーク・リンク毎に、前記仮想経路に関するブロック化を計算する手段と、 各ネットワーク・リンク上で、最も大きなブロック化を有する仮想経路を識別 する手段と、 前記識別した仮想経路が、もはや最も大きいブロック化を有さなくなるまで、 前記ネットワーク資源の制約に違反することなく、追加の容量を配分する手段と 、を含む請求項２０記載の仮想経路割り当てシステム。 22．更に、 全仮想経路を割り当て集合に集合化する手段と、 各物理リンクの伝送容量を指定する手段と、 各仮想経路に比較的大きな初期ブロック化値を選択する手段と、 致命リンク識別アルゴリズムの収束を評価するためにエラー境界を選択する手 段と、 エントロピ・ブロック化尺度を用いて、各仮想経路に対してブロック化値を決 定する手段と、 前記物理リンクが使用可能な容量を有する限り、最大のブロック化値を有する 仮想経路を繰り返し識別する手段と、 最大利用度に達した物理リンクがなく、最大に妨害を受ける仮想経路のブロッ ク化減少が予め選択されているエラー境界よりも大きい限り、前記仮想経路間に おいて伝送容量を再配分することにより、最も大きなブロック化値を有する仮想 経路のブロック化を減少させる手段と、 配分可能な容量が不足する物理リンクを致命リンクとして識別する手段と、 前記割り当て集合から、致命リンクに該当する全ての仮想経路を除去する手段 と、 残りの物理リンクの伝送容量を繰り返し再調節し、前記割り当て集合から最後 に除去された仮想経路に配分さられていた容量を反映する手段と、 を含む請求項２０記載の仮想経路割り当てシステム。 23．複数のノードを相互接続する複数の物理リンクを有し、制約のある遠隔通 信ネットワークを割り当てるシステムであって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングする手段であって、 前記仮想経路の各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切 り替え可能な接続を設ける前記手段と、 選択された複数の物理リンクを１つ以上の仮想経路に集合化する手段であって 、前記仮想経路の各々が、前記遠隔通信ネットワーク内のノード対間に、個々に 切り替え可能な接続を設ける前記手段と、 選択された複数の前記仮想経路を割り当て集合に集合化する手段と、 初期状態においてブロック化が大きくなるように、各仮想経路に初期伝送容量 を配分する手段と、 現在の値よりも低い値を後続のブロック化に選択する手段と、 単一の物理リンクと交差する前記仮想経路の各々に関してブロック化の計算を 行う手段と、 物理リンクが、未配分容量を有さないと識別されるまで、異なる仮想経路間の ブロック化における変動に応答して、単一の物理リンクと交差する仮想経路間で 、使用可能な伝送容量を配分する手段と、 前記識別された物理リンクと交差する全ての仮想経路を、前記割り当て集合か ら除去する手段と、 前記識別された物理リンクと交差する全ての仮想経路を、前記割り当て集合か ら削減する手段と、 前記除去された仮想経路に以前に配分されていた量だけ、前記物理リンクの各 各に割り当てられる伝送容量を減少させる手段と、 前記計算、割り当て、除去、および減少ステップを、前記割り当て集合に仮想 経路がなくなるまで繰り返し実行する手段と、 から成るシステム。 24．複数のノードを相互接続する複数の物理リンクを有する遠隔通信ネットワ ーク上で定義された仮想経路を割り当てるシステムであって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングする手段であって、 前記仮想経路の各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切 り替え可能な接続を設ける前記手段と、 各物理リンクの伝送容量を指定する手段と、 選択された複数の前記仮想経路を割り当て集合に組み入れる手段と、 エントロピ比率関数をブロック化尺度として用い、前記割り当て集合内の各仮 想経路に伝送容量の初期値を配分し、前記初期値の各々を等しく、かつ前記ブロ ック化が大きくなるように選択する手段と、 前記仮想経路が交差する物理リンク間で、容量が最大に配分されている物理リ ンクを致命リンクとして繰り返し識別する手段であって、 エントロピ比率関数推定値を固定値だけ増分する手段と、 前記割り当て集合内の各仮想経路に対してシフト・パラメータを再計算する手 段と、 前記増分されたエントロピ比率関数推定値および前記再計算されたシフト・パ ラメータを用いて、各仮想経路に配分される容量を再計算する手段と、 各物理リンクについて、前記仮想経路の全てに配分された容量を合計し、各物 理リンク上の全配分容量を得る手段と、 各物理リンクの前記全配分容量を、その指定容量と比較し、前記物理リンクの 未配分容量が実質的にゼロか否かについて判定を行う手段と、 致命リンクとして識別された物理リンクと交差する仮想経路の各々に、現在割 り当てられている容量を出力する手段と、 各致命物理リンクと交差する全ての仮想経路を前記割り当て集合から除去する 手段と、 前記物理リンクの指定された物理容量を定義し直し、前記除去された仮想経路 に配分されていた容量を補償する手段と、 を含む前記識別手段と、 から成るシステム。 25．前記プッシュ・ダウン・アルゴリズムにおいて、最も大きいブロック化値 を有する仮想経路のブロック化を減少させるステップは、連続近似技法を用いて 実行する請求項１０記載の割り当て方法。 26．前記プッシュ・ダウン・アルゴリズムにおいて、最も大きいブロック化値 を有する仮想経路のブロック化を減少させるステップは、連続近似技法を用いて 実行する請求項２２記載の割り当てシステム。 【手続補正書】 【提出日】１９９８年２月１７日（１９９８．２．１７） 【補正内容】 １．図面の第１３（Ａ，Ｂ）図〜第２１図を削除する。
───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ， ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＬＳ，ＭＷ，ＳＤ，Ｓ Ｚ，ＵＧ)，ＵＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＺ， ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，ＨＵ，Ｉ Ｌ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＫ ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＫ， ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，Ｒ Ｕ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＴＪ，ＴＭ，ＴＲ ，ＴＴ，ＵＡ，ＵＧ，ＵＺ，ＶＮ

Claims (1)

  1. 【特許請求の範囲】 １．汎用トラフィックを搬送する遠隔通信ネットワーク上で定義された仮想経 路を割り当てるコンピュータ実装方法であって、前記ネットワークは、伝送容量 が制限された複数の相互接続リンクを有し、前記割り当て方法は、 適切なエントロピ比率関数を選択し、前記遠隔通信ネットワークの各仮想経路 上の負荷をモデル化するステップと、 前記エントロピ比率関数を、前記汎用トラフィックに対する負荷均衡化問題を 解くように動作するブロック化尺度として用いる解法アルゴリズムを選択するス テップと、 前記エントロピ比率関数を組み込んだ前記負荷均衡化アルゴリズムを用いて計 算機システム上で計算を行い、前記仮想経路上でできるだけ均一な負荷分散を生 成するステップと、 から成る仮想経路割り当て方法。 ２．前記エントロピ比率関数は、トラフィック測定値によって決定される請求 項１記載の仮想経路割り当て方法。 ３．前記エントロピ比率関数は、遠隔通信ネットワーク上の提供トラフィック の特徴を理想化することによって決定される請求項１記載の仮想経路割り当て方 法。 ４．前記エントロピ比率関数は、提供トラフィックの一様ポアソン分布に対し て理想化される請求項３記載の仮想経路割り当て方法。 ５．前記エントロピ比率関数は、提供トラフィックのマルチクラス・ポアソン 分布に対して理想化される請求項３記載の仮想経路割り当て方法。 ６．前記エントロピ比率関数は、提供トラフィックの正規分布に対して理想化 される請求項３記載の仮想経路割り当て方法。 ７．前記エントロピ比率関数は、提供トラフィックの二項分布に対して理想化 される請求項３記載の仮想経路割り当て方法。 ８．前記提供トラフィックをモデル化するために用いられるエントロピ・ブロ ック化尺度はエントロピ比率関数Ｉｘ（Ｃ）であり、該エントロピ比率関数は、 任意に分布されるランダム変数Ｘが予め選択されている値Ｃ以上である確率の負 対数の近似として計算可能であり、前記エントロピ比率関数は、更に、分布の平 均において、その最小値であるゼロを得る凸関数である請求項３記載の仮想経路 割り当て方法。 ９．前記エントロピ比率関数を、前記汎用トラフィックに対する負荷均衡化問 題を解決するように動作するブロック化尺度として用いる前記アルゴリズムは、 プッシュ・ダウン・アルゴリズムである請求項１記載の仮想経路割り当て方法。 10．前記プッシュ・ダウン・アルゴリズムは、更に、 前記割り当て対象の仮想経路を、割り当て集合に組み入れるステップと、 前記選択したエントロピ比率関数を用いて、各仮想経路が交差する各ネットワ ーク・リンク毎に、前記仮想経路に関するブロック化を計算するステップと、 各ネットワーク・リンク上で、最も大きなブロック化を有する仮想経路を識別 するステップと、 前記識別した仮想経路が、もはや最も大きいブロック化を有さなくなるまで、 前記ネットワーク資源の制約に違反することなく、追加の容量を配分するステッ プと、 を含む請求項９記載の仮想経路割り当て方法。 11．前記プッシュ・ダウン・アルゴリズムは、更に、 全仮想経路を割り当て集合に集合化するステップと、 各物理リンクの伝送容量を指定するステップと、 各仮想経路に比較的大きな初期ブロック化値を選択するステップと、 致命リンク識別アルゴリズムの収束を評価するためにエラー境界を選択するス テップと、 エントロピ・ブロック化尺度を用いて、各仮想経路に対してブロック化値を決 定するステップと、 前記物理リンクが使用可能な容量を有する限り、最大のブロック化値を有する 仮想経路を繰り返し識別するステップと、 最大利用度に達した物理リンクがなく、最大に妨害を受ける仮想経路のブロッ ク化減少が予め選択されているエラー境界よりも大きい限り、前記仮想経路間に おいて伝送容量を再割り当てすることにより、最も大きなブロック化値を有する 仮想経路のブロック化を減少させるステップと、 配分可能な容量が不足する物理リンクを致命リンクとして識別するステップと 、 前記割り当て集合から、致命リンクに該当する全ての仮想経路を除去するステ ップと、 残りの物理リンクの伝送容量を繰り返し再調節し、前記割り当て集合から最後 に除去された仮想経路に配分されていた容量を反映するステップと、 を含み、前記割り当て集合がヌル集合となるまで、前記繰り返しステップを繰り 返す請求項９記載の仮想経路割り当て方法。 12．複数のノードを相互接続する複数の物理リンクを有し、制約のある遠隔通 信ネットワーク上において仮想経路を割り当てる方法であって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングし、前記仮想経路の 各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切り替え可能な接 続を設けるようにするステップと、 各仮想経路に対して提供トラフィックを指定するステップと、 前記遠隔通信ネットワークの各物理リンクに対して、伝送容量制約を指定する ステップと、 エントロピ・ブロック化尺度を用いて、前記遠隔通信ネットワーク上で提供ト ラフィックのモデル化を行うステップと、 前記リンク伝送容量制約を受ける前記複数の仮想経路に容量を配分し、その際 異なる仮想経路に関するブロック化確率が、できるだけ均一となるようにするス テップと、 から成る方法。 13．複数のノードを相互接続する複数の物理リンクを有し、制約のある遠隔通 信ネットワークを割り当てる方法であって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングし、前記仮想経路の 各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切り替え可能な接 続を設けるようにするステップと、 選択された複数の前記仮想経路を割り当て集合に集合化するステップと、 初期状態においてブロック化が大きくなるように、各仮想経路に初期伝送容量 を配分するステップと、 現在の値よりも低い値を後続のブロック化に選択するステップと、 単一の物理リンクと交差する前記仮想経路の各々に関してブロック化の計算を 行うステップと、 物理リンクが、未配分容量を有さないと識別されるまで、異なる仮想経路間の ブロック化における変動に応答して、単一の物理リンクと交差する仮想経路間で 、使用可能な伝送容量を配分するステップと、 前記識別された物理リンクと交差する全ての仮想経路を、前記割り当て集合か ら除去するステップと、 前記除去された仮想経路に以前に配分されていた量だけ、前記物理リンクの各 各に割り当てられる伝送容量を減少させるステップと、 前記計算、割り当て、除去、および減少ステップを、前記割り当て集合に仮想 経路がなくなるまで繰り返し実行するステップと、 から成る方法。 14．複数のノードを相互接続する複数の物理リンクを有する遠隔通信ネットワ ーク上で定義された仮想経路を割り当てる方法であって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングし、前記仮想経路の 各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切り替え可能な接 続を設けるようにするステップと、 各物理リンクの伝送容量を指定するステップと、 選択された複数の前記仮想経路を割り当て集合に組み入れるステップと、 エントロピ比率関数をブロック化尺度として用い、前記割り当て集合内の各仮 想経路に伝送容量の初期値を配分し、前記初期値の各々を等しく、かつ前記ブロ ック化が大きくなるように選択するステップと、 前記仮想経路が交差する物理リンク間で、容量が最大に配分されている物理リ ンクを致命リンクとして繰り返し識別するステップであって、 エントロピ比率関数推定値を固定値だけ増分するサブステップと、 前記割り当て集合内の各仮想経路に対してシフト・パラメータを再計算するサ ブステップと、 前記増分されたエントロピ比率関数推定値および前記再計算されたシフト・パ ラメータを用いて、各仮想経路に配分される容量を再計算するサブステップと、 各物理リンクについて、前記仮想経路の全てに配分された容量を合計し、各物 理リンク上の全配分容量を得るサブステップと、 各物理リンクの前記全配分容量を、その指定容量と比較し、前記物理リンクの 未配分容量が実質的にゼロか否かについて判定を行うサブステップと、 によって実行する前記識別ステップと、 致命リンクとして識別された物理リンクと交差する仮想経路の各々に、現在配 分されている容量を出力するステップと、 各致命物理リンクと交差する全ての仮想経路を前記割り当て集合から除去する ステップと、 前記物理リンクの指定された物理容量を定義し直し、前記除去された仮想経路 に配分されていた容量を補償するステップと、 から成る方法。 15．汎用トラフィックを搬送する遠隔通信ネットワーク上で定義された仮想経 路を割り当てるコンピュータ実装システムであって、前記ネットワークは、伝送 容量が制限された複数の相互接続リンクを有し、前記割り当て方法は、 適切なエントロピ比率関数を選択し、前記遠隔通信ネットワークの各仮想経路 上の負荷をモデル化する手段と、 前記エントロピ比率関数を、前記汎用トラフィックに対する負荷均衡化問題を 解くように動作するブロック化尺度として用いる解法アルゴリズムを選択する手 段と、 前記エントロピ比率関数を組み込んだ前記負荷均衡化アルゴリズムを用いて計 算機システム上で計算を行い、前記仮想経路上でできるだけ均一な負荷分散を生 成する手段と、 から成る仮想経路割り当てシステム。 16．前記エントロピ比率関数は、トラフィック測定値によって決定される請求 項１５記載の仮想経路割り当てシステム。 17．前記エントロピ比率関数は、遠隔通信ネットワーク上の提供トラフィック の特徴を理想化することによって決定される請求項１５記載の仮想経路割り当て システム。 18．前記エントロピ比率関数は、提供トラフィックの一様ポアソン分布に対し て理想化される請求項１７記載の仮想経路割り当てシステム。 19．前記エントロピ比率関数は、提供トラフィックのマルチクラス・ポアソン 分布に対して理想化される請求項１７記載の仮想経路割り当てシステム。 20．前記エントロピ比率関数は、提供トラフィックの正規分布に対して理想化 される請求項１７記載の仮想経路割り当てシステム。 21．前記エントロピ比率関数は、提供トラフィックの二項分布に対して理想化 される請求項１７記載の仮想経路割り当てシステム。 22．前記提供トラフィックをモデル化するために用いられるエントロピ・ブロ ック化尺度はエントロピ比率関数Ｉx（Ｃ）であり、該エントロピ比率関数は、 任意に分布されるランダム変数Ｘが予め選択されている値Ｃ以上である確率の負 対数の近似として計算可能であり、前記エントロピ比率関数は、更に、分布の平 均において、その最小値であるゼロを得る凸関数である請求項１７記載の仮想経 路割り当てシステム。 23．前記エントロピ比率関数を、前記汎用トラフィックに対する負荷均衡化問 題を解決するように動作するブロック化尺度として用いる前記アルゴリズムは、 プッシュ・ダウン・アルゴリズムである請求項１５記載の仮想経路割り当てシス テム。 24．更に、 前記割り当て対象の仮想経路を、割り当て集合に組み入れる手段と、 前記選択したエントロピ比率関数を用いて、各前記仮想経路が交差する各ネッ トワーク・リンク毎に、前記仮想経路に関するブロック化を計算する手段と、 各ネットワーク・リンク上で、最も大きなブロック化を有する仮想経路を識別 する手段と、 前記識別した仮想経路が、もはや最も大きいブロック化を有さなくなるまで、 前記ネットワーク資源の制約に違反することなく、追加の容量を配分する手段と 、 を含む請求項２３記載の仮想経路割り当てシステム。 25．更に、 全仮想経路を割り当て集合に集合化する手段と、 各物理リンクの伝送容量を指定する手段と、 各仮想経路に比較的大きな初期ブロック化値を選択する手段と、 致命リンク識別アルゴリズムの収束を評価するためにエラー境界を選択する手 段と、 エントロピ・ブロック化尺度を用いて、各仮想経路に対してブロック化値を決 定する手段と、 前記物理リンクが使用可能な容量を有する限り、最大のブロック化値を有する 仮想経路を繰り返し識別する手段と、 最大利用度に達した物理リンクがなく、最大に妨害を受ける仮想経路のブロッ ク化減少が予め選択されているエラー境界よりも大きい限り、前記仮想経路間に おいて伝送容量を再配分することにより、最も大きなブロック化値を有する仮想 経路のブロック化を減少させる手段と、 配分可能な容量が不足する物理リンクを致命リンクとして識別する手段と、 前記割り当て集合から、致命リンクに該当する全ての仮想経路を除去する手段 と、 残りの物理リンクの伝送容量を繰り返し再調節し、前記割り当て集合から最後 に除去された仮想経路に配分さられていた容量を反映する手段と、 を含む請求項２３記載の仮想経路割り当てシステム。 26．複数のノードを相互接続する複数の物理リンクを有し、制約のある遠隔通 信ネットワーク上において仮想経路を割り当てるシステムであって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングする手段であって、 前記仮想経路の各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切 り替え可能な接続を設ける前記手段と、 各仮想経路に対して提供トラフィックを指定する手段と、 前記遠隔通信ネットワークの各物理リンクに対して、伝送容量制約を指定する 手段と、 エントロピ・ブロック化尺度を用いて、前記遠隔通信ネットワーク上で提供ト ラフィックのモデル化を行う手段と、 前記リンク伝送容量制約を受ける前記複数の仮想経路に容量を配分し、その際 異なる仮想経路に関するブロック化確率が、できるだけ均一となるようにする手 段と、から成るシステム。 27．複数のノードを相互接続する複数の物理リンクを有し、制約のある遠隔通 信ネットワークを割り当てるシステムであって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングする手段であって、 前記仮想経路の各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切 り替え可能な接続を設ける前記手段と、 選択された複数の前記仮想経路を割り当て集合に集合化する手段と、 初期状態においてブロック化が大きくなるように、各仮想経路に初期伝送容量 を配分する手段と、 現在の値よりも低い値を後続のブロック化に選択する手段と、 単一の物理リンクと交差する前記仮想経路の各々に関してブロック化の計算を 行う手段と、 物理リンクが、未配分容量を有さないと識別されるまで、異なる仮想経路間の ブロック化における変動に応答して、単一の物理リンクと交差する仮想経路間で 、使用可能な伝送容量を配分する手段と、 前記識別された物理リンクと交差する全ての仮想経路を、前記割り当て集合か ら除去する手段と、 前記除去された仮想経路に以前に配分されていた量だけ、前記物理リンクの各 各に割り当てられる伝送容量を減少させる手段と、 前記計算、割り当て、除去、および減少ステップを、前記割り当て集合に仮想 経路がなくなるまで繰り返し実行する手段と、 から成るシステム。 28．複数のノードを相互接続する複数の物理リンクを有する遠隔通信ネットワ ーク上で定義された仮想経路を割り当てるシステムであって、 前記複数の物理リンクを１つ以上の仮想経路にマッピングする手段であって、 前記仮想経路の各々が、前記遠隔通信ネットワーク内のノード対間に、個々に切 り替え可能な接続を設ける前記手段と、 各物理リンクの伝送容量を指定する手段と、 選択された複数の前記仮想経路を割り当て集合に組み入れる手段と、 エントロピ比率関数をブロック化尺度として用い、前記割り当て集合内の各仮 想経路に伝送容量の初期値を配分し、前記初期値の各々を等しく、かつ前記ブロ ック化が大きくなるように選択する手段と、 前記仮想経路が交差する物理リンク間で、容量が最大に配分されている物理リ ンクを致命リンクとして繰り返し識別する手段であって、 エントロピ比率関数推定値を固定値だけ増分する手段と、 前記割り当て集合内の各仮想経路に対してシフト・パラメータを再計算する手 段と、 前記増分されたエントロピ比率関数推定値および前記再計算されたシフト・パ ラメータを用いて、各仮想経路に配分される容量を再計算する手段と、 各物理リンクについて、前記仮想経路の全てに配分された容量を合計し、各物 理リンク上の全配分容量を得る手段と、 各物理リンクの前記全配分容量を、その指定容量と比較し、前記物理リンクの 未配分容量が実質的にゼロか否かについて判定を行う手段と、 を含む前記識別手段と、 致命リンクとして識別された物理リンクと交差する仮想経路の各々に、現在割 り当てられている容量を出力する手段と、 各致命物理リンクと交差する全ての仮想経路を前記割り当て集合から除去する 手段と、 前記物理リンクの指定された物理容量を定義し直し、前記除去された仮想経路 に配分されていた容量を補償する手段と、 から成るシステム。 29．前記プッシュ・ダウン・アルゴリズムにおいて、最も大きいブロック化値 を有する仮想経路のブロック化を減少させるステップは、連続近似技法を用いて 実行する請求項１１記載の割り当て方法。 30．前記プッシュ・ダウン・アルゴリズムにおいて、最も大きいブロック化値 を有する仮想経路のブロック化を減少させるステップは、連続近似技法を用いて 実行する請求項２５記載の割り当てシステム。
JP9506610A 1995-07-14 1996-07-11 広帯域トラフィックによる最適仮想経路容量割り当てシステムおよび方法 Ceased JP2000501899A (ja)

Applications Claiming Priority (5)

Application Number Priority Date Filing Date Title
US116995P 1995-07-14 1995-07-14
US08/514,480 1995-08-11
US08/514,480 US5872918A (en) 1995-07-14 1995-08-11 System and method for optimal virtual path capacity dimensioning with broadband traffic
US60/001,169 1995-08-11
PCT/SE1996/000941 WO1997004605A1 (en) 1995-07-14 1996-07-11 System and method for optimal virtual path capacity dimensioning with broadband traffic

Publications (2)

Publication Number Publication Date
JP2000501899A true JP2000501899A (ja) 2000-02-15
JP2000501899A5 JP2000501899A5 (ja) 2004-08-26

Family

ID=26668667

Family Applications (1)

Application Number Title Priority Date Filing Date
JP9506610A Ceased JP2000501899A (ja) 1995-07-14 1996-07-11 広帯域トラフィックによる最適仮想経路容量割り当てシステムおよび方法

Country Status (6)

Country Link
US (2) US5872918A (ja)
EP (1) EP0873656A1 (ja)
JP (1) JP2000501899A (ja)
AU (1) AU6376096A (ja)
CA (1) CA2226480A1 (ja)
WO (1) WO1997004605A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101428573B1 (ko) 2013-06-20 2014-08-11 경북대학교 산학협력단 네트워크 장치 및 트래픽 처리 방법

Families Citing this family (56)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
SE9402059D0 (sv) * 1994-06-13 1994-06-13 Ellemtel Utvecklings Ab Sätt och anordning vid telekommunikation
US6304549B1 (en) * 1996-09-12 2001-10-16 Lucent Technologies Inc. Virtual path management in hierarchical ATM networks
US6842780B1 (en) * 1997-04-08 2005-01-11 Swisscom Ag Method of management in a circuit-switched communication network and device which can be used as a node in a circuit-switched communication network
JPH1117719A (ja) * 1997-06-20 1999-01-22 Fujitsu Ltd クロスコネクト装置
US6085216A (en) * 1997-12-31 2000-07-04 Xerox Corporation Method and system for efficiently allocating resources for solving computationally hard problems
US6452939B1 (en) 1998-03-24 2002-09-17 Samsung Electronics Co., Ltd. ATM interface device with double header conversion
US6434619B1 (en) * 1998-04-29 2002-08-13 Alcatel Canada Inc. Internet-enabled service management system and method
US6459681B1 (en) * 1998-11-13 2002-10-01 Sprint Communications Company L.P. Method and system for connection admission control
US6493346B1 (en) * 1999-03-31 2002-12-10 Alcatel Usa Sourcing, L.P. System for providing conversion of TDM-based frame relay data in a cross-connect matrix to and from ATM data
US6862559B1 (en) * 1999-07-23 2005-03-01 Xerox Corporation Methods and apparatuses for measuring diversity in combinatorial structures
US6721270B1 (en) * 1999-08-09 2004-04-13 Lucent Technologies Inc. Multicommodity flow method for designing traffic distribution on a multiple-service packetized network
US6427035B1 (en) 1999-08-12 2002-07-30 Bellsouth Intellectual Property Corporation Method and apparatus for deploying fiber optic cable to subscriber
US6986137B1 (en) * 1999-09-28 2006-01-10 International Business Machines Corporation Method, system and program products for managing logical processors of a computing environment
US6519660B1 (en) * 1999-09-28 2003-02-11 International Business Machines Corporation Method, system and program products for determining I/O configuration entropy
US6810422B1 (en) 2000-01-14 2004-10-26 Lockheed Martin Tactical Defense Systems System and method for probabilistic quality of communication service determination
US6963575B1 (en) * 2000-06-07 2005-11-08 Yipes Enterprise Services, Inc. Enhanced data switching/routing for multi-regional IP over fiber network
NO20003682L (no) * 2000-07-18 2002-01-21 Ericsson Telefon Ab L M Måling av holdetid i kommunikasjonsnett
US6654655B1 (en) 2000-08-10 2003-11-25 Taiwan Semiconductor Manufacturing Co., Ltd Target generation system based on unlimited capacity allocation
US20010054097A1 (en) * 2000-12-21 2001-12-20 Steven Chafe Monitoring and reporting of communications line traffic information
US7336658B2 (en) * 2001-02-28 2008-02-26 Telefonaktiebolaget Lm Ericsson (Publ) Methods and system of virtual circuit identification based on bit permutation of link numbers for multi-stage elements
US7039705B2 (en) * 2001-10-26 2006-05-02 Hewlett-Packard Development Company, L.P. Representing capacities and demands in a layered computing environment using normalized values
US7054934B2 (en) * 2001-10-26 2006-05-30 Hewlett-Packard Development Company, L.P. Tailorable optimization using model descriptions of services and servers in a computing environment
US7035930B2 (en) * 2001-10-26 2006-04-25 Hewlett-Packard Development Company, L.P. Method and framework for generating an optimized deployment of software applications in a distributed computing environment using layered model descriptions of services and servers
CA2411806A1 (en) * 2001-11-16 2003-05-16 Telecommunications Research Laboratory Wide-area content-based routing architecture
GB0205284D0 (en) * 2002-03-06 2002-04-17 Lucent Technologies Inc Entropy based complexity measurement for behaviour analysis of distributed self-organizing systems in telecommunication networks
US7277400B2 (en) 2002-03-06 2007-10-02 Lucent Technologies Inc. Method of monitoring state of a telecommunications network comprising a plurality of nodes, and a corresponding telecommunications network
US7013318B2 (en) * 2002-05-29 2006-03-14 Raytheon Company Method and system for encapsulating cells
US7072960B2 (en) * 2002-06-10 2006-07-04 Hewlett-Packard Development Company, L.P. Generating automated mappings of service demands to server capacities in a distributed computer system
US7305464B2 (en) * 2002-09-03 2007-12-04 End Ii End Communications, Inc. Systems and methods for broadband network optimization
CN1235369C (zh) * 2002-09-17 2006-01-04 华为技术有限公司 一种实现光同步数字传送网多业务优化中路由分配的方法
US7307961B2 (en) * 2002-09-25 2007-12-11 At&T Knowledge Ventures, L.P. Traffic modeling for packet data communications system dimensioning
US20060031439A1 (en) * 2002-10-29 2006-02-09 Saffre Fabrice T Method and apparatus for network management
US7299273B2 (en) * 2002-12-16 2007-11-20 International Business Machines Corporation Method and system to bundle message over a network
US20040205064A1 (en) * 2003-04-11 2004-10-14 Nianjun Zhou Adaptive search employing entropy based quantitative information measurement
AU2003903602A0 (en) * 2003-07-14 2003-07-24 Steven Luzima Mutabazi Networking corridors for packet data and voice communications
US20080089347A1 (en) * 2003-08-29 2008-04-17 End Ii End Communications Inc. Systems and methods for broadband network optimization
JP4226600B2 (ja) * 2003-08-29 2009-02-18 富士通株式会社 ダイナミックトラフィック制御方法及びその装置
US7382801B2 (en) * 2003-09-03 2008-06-03 At&T Deleware Intellectual Property, Inc. Link capacity dimensioning methods for packet switched communications networks, and networks and links dimensioned thereby
US7577091B2 (en) * 2004-02-04 2009-08-18 Telefonaktiebolaget Lm Ericsson (Publ) Cluster-based network provisioning
US7489638B2 (en) * 2004-04-08 2009-02-10 Alcatel-Lucent Usa Inc. Scheduling with delayed graphs for communication networks
EP1594255B1 (de) * 2004-05-05 2007-09-05 Siemens Aktiengesellschaft Lastkontrolle in einem TMN System
WO2006059852A1 (en) * 2004-12-04 2006-06-08 Electronics And Telecommunications Research Institute Method and system for providing resources by using virtual path
US20080137533A1 (en) * 2004-12-23 2008-06-12 Corvil Limited Method and System for Reconstructing Bandwidth Requirements of Traffic Stream Before Shaping While Passively Observing Shaped Traffic
US8045453B2 (en) * 2005-01-20 2011-10-25 Alcatel Lucent Methods and systems for alleviating congestion in a connection-oriented data network
US7515594B2 (en) * 2005-07-15 2009-04-07 Telefonaktiebolaget L M Ericsson (Publ) Enhanced virtual circuit allocation methods and systems for multi-stage switching elements
US20070045400A1 (en) * 2005-08-23 2007-03-01 International Business Machines Corporation Distriubuted registry for personalization
US7712134B1 (en) * 2006-01-06 2010-05-04 Narus, Inc. Method and apparatus for worm detection and containment in the internet core
US8300798B1 (en) 2006-04-03 2012-10-30 Wai Wu Intelligent communication routing system and method
ATE494686T1 (de) * 2006-04-14 2011-01-15 Mitsubishi Electric Corp Verfahren zum erhalt von für das feedback zur kanalqualität auf mindestens einem frequenzunterband repräsentativer information
US7831700B2 (en) * 2006-10-16 2010-11-09 Futurewei Technologies, Inc. Distributed PCE-based system and architecture in multi-layer network
US8009669B2 (en) * 2006-10-16 2011-08-30 Futurewei Technologies, Inc. System of path computation element protocol support for large-scale concurrent path computation
US8300614B2 (en) * 2009-05-14 2012-10-30 Avaya Inc. Preventing packet loops in unified networks
US20140341568A1 (en) * 2013-05-20 2014-11-20 Sodero Networks, Inc. High-Throughput Network Traffic Monitoring through Optical Circuit Switching and Broadcast-and-Select Communications
US20140369347A1 (en) * 2013-06-18 2014-12-18 Corning Cable Systems Llc Increasing radixes of digital data switches, communications switches, and related components and methods
US10320970B2 (en) * 2016-09-28 2019-06-11 Nokia Of America Corporation System and method for anomaly detection for non-homogenous arrival rate
CN119626500B (zh) * 2024-11-20 2025-08-01 广州腾方科技有限公司 分诊屏远程智能管理系统及其方法

Family Cites Families (26)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4679187A (en) * 1985-04-22 1987-07-07 International Business Machines Corp. Adaptive trunk-compression system with constant grade of service
US4669113A (en) * 1985-04-26 1987-05-26 At&T Company Integrated network controller for a dynamic nonhierarchical routing switching network
US5175866A (en) * 1987-06-03 1992-12-29 Ericcson Ge Mobile Communications Inc. Fail-soft architecture for public trunking system
WO1990010984A1 (en) * 1989-03-14 1990-09-20 Alcatel N.V. Communication switching system
JP2837182B2 (ja) * 1989-08-04 1998-12-14 富士通株式会社 セルデータの伝送方法、送信要求処理方法及びスイッチ
US5270919A (en) * 1990-06-04 1993-12-14 At&T Bell Laboratories Network planning tool
JP2834293B2 (ja) * 1990-08-17 1998-12-09 株式会社日立製作所 バーチャルパス容量の変更方法
JP3241716B2 (ja) * 1990-08-31 2001-12-25 株式会社東芝 Ａｔｍ交換方法
JPH04151933A (ja) * 1990-10-16 1992-05-25 Toshiba Corp 通信網制御方式
JPH04326836A (ja) * 1991-04-26 1992-11-16 Nippon Telegr & Teleph Corp <Ntt> バーチャルパス容量制御装置
US5179556A (en) * 1991-08-02 1993-01-12 Washington University Bandwidth management and congestion control scheme for multicast ATM networks
JP3071007B2 (ja) * 1991-10-22 2000-07-31 富士通株式会社 通信ネットワーク制御方式
US5381404A (en) * 1992-07-14 1995-01-10 Mita Industrial Co., Ltd. Packet-switching communication network and method of design
JPH0697952A (ja) * 1992-08-10 1994-04-08 Nippon Telegr & Teleph Corp <Ntt> 非同期転送モードプライベート網エンドカスタマ制御方式
US5345444A (en) * 1992-09-30 1994-09-06 At&T Bell Laboratories Chuted, growable packet switching arrangement
US5289303A (en) * 1992-09-30 1994-02-22 At&T Bell Laboratories Chuted, optical packet distribution network
US5586267A (en) * 1992-10-13 1996-12-17 Bay Networks, Inc. Apparatus for providing for automatic topology discovery in an ATM network or the like
US5519707A (en) * 1992-10-13 1996-05-21 Synoptics Communications, Inc. Multiplexing of communications services on a virtual service path in an ATM network or the like
US5274643A (en) * 1992-12-11 1993-12-28 Stratacom, Inc. Method for optimizing a network having virtual circuit routing over virtual paths
US5357507A (en) * 1993-08-24 1994-10-18 Northern Telecom Limited Fast connection admission control for ATM networks
US5430729A (en) * 1994-04-04 1995-07-04 Motorola, Inc. Method and apparatus for adaptive directed route randomization and distribution in a richly connected communication network
US5559877A (en) * 1995-03-21 1996-09-24 At&T Automatic provisioning of trunking and routing parameters in a telecommunications network
US5596722A (en) * 1995-04-03 1997-01-21 Motorola, Inc. Packet routing system and method for achieving uniform link usage and minimizing link load
US5764740A (en) * 1995-07-14 1998-06-09 Telefonaktiebolaget Lm Ericsson System and method for optimal logical network capacity dimensioning with broadband traffic
US5727051A (en) * 1995-07-14 1998-03-10 Telefonaktiebolaget Lm Ericsson (Publ.) System and method for adaptive routing on a virtual path broadband network
US5937042A (en) * 1996-03-19 1999-08-10 Mci Communications Corporation Method and system for rehome optimization

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101428573B1 (ko) 2013-06-20 2014-08-11 경북대학교 산학협력단 네트워크 장치 및 트래픽 처리 방법

Also Published As

Publication number Publication date
AU6376096A (en) 1997-02-18
US5872918A (en) 1999-02-16
WO1997004605A1 (en) 1997-02-06
CA2226480A1 (en) 1997-02-06
EP0873656A1 (en) 1998-10-28
US6304639B1 (en) 2001-10-16

Similar Documents

Publication Publication Date Title
JP2000501899A (ja) 広帯域トラフィックによる最適仮想経路容量割り当てシステムおよび方法
US5727051A (en) System and method for adaptive routing on a virtual path broadband network
US5764740A (en) System and method for optimal logical network capacity dimensioning with broadband traffic
EP0765554B1 (en) A method and device for partitioning physical network resources
US5706279A (en) Methods and systems for managing packet flow into a fast packet switching network
US5812525A (en) Methods and systems for managing bandwidth resources in a fast packet switching network
US6594268B1 (en) Adaptive routing system and method for QOS packet networks
US5940372A (en) Method and system for selecting path according to reserved and not reserved connections in a high speed packet switching network
Shim et al. Modeling and call admission control algorithm of variable bit rate video in ATM networks
JP2000151652A (ja) 連続ビット・レ―ト仮想パス接続の帯域幅を動的に調節するための方法、システム及びネットワ―ク
Erfani et al. Dynamic access capacity management in a multiservice packet-mode environment
Larsson et al. Performance evaluation of a local approach for VPC capacity management
JP3786371B6 (ja) バンドトラヒックによる論理ネットワーク容量を最適にディメンジョニングするためのシステムおよび方法
Hughes et al. Comparison of virtual path bandwidth assignment and routing methods
Heijenk et al. Design and evaluation of a connection management mechanism for an ATM-based connectionless service
JP2794740B2 (ja) 網内リソース管理方法
TW399380B (en) System and method for optimal virtual path capacity dimensioning with broadband traffic
Chiotis et al. The effective bandwidth approach: configuration of ATM virtual connections
JP2844746B2 (ja) 呼受付制御方法
Jabbari A connection control strategy for bursty sources in broadband packet networks
JP2844627B2 (ja) 網内リソース割り当て方法
Valadas Dimensioning and Resource Management of ATM Networks
Ušcumlic et al. Scheduling in Optical Packet Rings
Erfani et al. IN A MULTISERVICE PACKET-MODE ENVIRONMENT
Yuan et al. Threshold–Based Connection Admission Control Scheme in ATM Networks: A Simulation Study

Legal Events

Date Code Title Description
A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20051122

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20051116

A313 Final decision of rejection without a dissenting response from the applicant

Free format text: JAPANESE INTERMEDIATE CODE: A313

Effective date: 20060410

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20060523