(57)【要約】【課題】  ネットワークの動作において、より高い効率を達成するためにトラフィック負荷の測定値を行うネットワーク管理手順を提供する。【解決手段】  選択された利用可能なサービス経路上で着信呼をいずれにルーティングするかを判定するための方法では、利用可能なサービス経路は、その各リンクが、特定されたマージンを上回る分だけの十分な利用可能容量を有する場合に、優先的に処理される。課金収入を計算するための方法では、搬送される負荷についての契約要件を有するネットワークサービスプロバイダが、契約に準拠していないことにより、損失した帯域幅に対して、徴収額の減額が要求されるようになる。【選択図】図１
2005341540.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークのソースノードと宛先ノードとの間で送出される帯域幅を搬送することによって提供される、少なくとも１つのサービスのクラスに対する課金を計算する方法であって、サービスクラスｓに関連する各ソース−宛先ノード対σが通信経路(s,σ)と呼ばれるものであり、該方法は、
(a)少なくとも１つの通信経路(s,σ)に関して、２つあるいはそれ以上の連続した各時間窓に対して、該ネットワークが準拠するか、準拠しないかを判定する段階と、
(b)該時間窓の各々に対して、搬送される送出帯域幅の単位当たりの各々に対するプラスの収入増加分を発生する段階と、
(c)該時間窓の各々に対して、該ネットワークが準拠していない間に損失された、送出された帯域幅の単位当たりの各々に対するマイナスの収入減額分を発生する段階とからなり、
(A)契約した最大範囲に違反しない該送出された通信経路帯域幅の測定値に対し、搬送される通信経路帯域幅と送出される通信経路帯域幅との測定比が、少なくともその契約された値であるときには該ネットワークは準拠しているものとし、そうでないときには該ネットワークが準拠していないものとし、
(B)契約した最大範囲に違反する該送出された通信経路帯域幅の測定値に対し、搬送される通信経路帯域幅の測定値が少なくともその契約された値であるときには該ネットワークは準拠しているとし、そうでないときには該ネットワークが準拠していないものとすることを特徴とする方法。
【請求項２】
リンクにより相互に接続されるノードからなるパケット通信ネットワークを動作し、１つあるいは複数のサービスのクラスをサポートする方法であって、ソースノードと宛先ノードとからなる該ネットワークのノード対の各々に対し、各サービスクラスはそれぞれ、該ソースノードから該宛先ノードまで該ネットワークを通る許容経路の組を有し、該サービス固有の経路はサービス経路と呼ばれるものであり、
該方法は、少なくとも１つのサービスクラスｓに対して、
(a)入口ノードと呼ばれる少なくとも１つのノードにおいて、該ノードが該ソースノードとなるような、少なくともいくつかのサービス経路によってかけられる負荷を測定する段階と、
(b)該入口ノードにおいて、該少なくともいくつかのサービス経路上の該負荷を予め規定される設計負荷と比較し、これにより該サービス経路の該負荷状態が過剰利用状態か標準利用状態かを判定する段階と、
(c)該入口ノードにおいて、複数の着信呼の各々によって該ネットワークへ送出される該負荷を測定し、かつ該呼に応答して該ネットワークにより搬送される該負荷を測定する段階と、
(d)該入口ノードにおいて、送出される負荷の測定値と搬送される負荷の測定値とから、該ネットワークが準拠状態か非準拠状態かを判定する段階と、
(e)該入口ノードにおいて、標準利用状態のサービス経路を優先的に選択する手順に従って、少なくとも１つの着信呼を宛先ノードにルーティングする段階と、
(f)該入口ノードにおいて、少なくとも１つの時間窓において、該ルーティングされた着信呼に起因して、該ネットワークにより搬送される負荷に対するプラスの収入増加分を発生する段階と、
(g)該入口ノードにおいて、少なくとも１つの時間窓において、該入口ノードから該宛先ノードへのルーティングのために該ネットワークに送出され、非準拠状態の該ネットワークから損失された負荷に対するマイナスの収入減額分を発生する段階とを有することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット網における認証制御、ルーティング(経路制御)及び課金計算の方法に関する。より詳細には、本発明は、多重レベルのサービスをサポートするネットワークを動作させる際に、そのような方法を使用することに関する。
【背景技術】
【０００２】
サービス品質保証制度(Ｓervice-Ｌevel Agreement：ＳＬＡ)は、パケット網サービスのプロバイダと１人の顧客(すなわち加入者)との間で交わされる契約であり、あるアプリケーションあるいはサービスを特定した呼を処理する際に、少なくとも満たされなければならない、ある最低限のサービス品質を規定するものである。ＳＬＡが規定する場合がある性能に関する１つの測定値は帯域幅の広さであり、帯域幅は所望に応じて利用可能でなければならない。顧客を特定した一組の各通信経路(stream)において、所望に応じて利用可能にされるべき帯域幅の広さをＳＬＡが規定するとき、仮想私設網(Ｖirtual Ｐrivate Ｎetwork：ＶＰＮ)が定義される。本明細書では「通信経路(stream)」は、ある特定クラスのサービスｓに関連して、呼に関わるソースノードと宛先ノードとからなるネットワークのノード対σである。種々の実現可能なサービスクラスには、例えば、音声、データ、Ｅ-メール、ファイル転送、ウエブ・ブラウジング及び映像などがある。パケット網は、例えばＡＴＭ、ＩＰあるいはフレーム・リレー・プロトコルをサポートするネットワークである。
【０００３】
以降、用語「呼」は、一般に呼、接続あるいはフローと呼ばれる任意の通信トランザクション、あるいは個別の通信トランザクションの部分を示すために用いることとする。
【０００４】
パケット網の動作において、種々の顧客を特定した着信呼は、リンク帯域幅容量のような、同じネットワークリソースにおいて競合しなければならない。さらに、同じ顧客に属するか、他の顧客に属するかに関わらず、種々のサービスクラスの呼によって同じリソースの競合が生じる。そのような環境では、各サービスクラスにおいて要求されるサービス品質を一貫して各顧客に提供し、同時に有効にネットワークを動作させることは難しい。
【０００５】
この問題に対する１つの解決策は、最適な状態で予想されるトラフィックパターンに対応するように、ネットワークの帯域幅の負荷Ｘsrを設計することである。ここで設計負荷Ｘsrは、サービス経路(s,r)上で、すなわち所与のサービスクラスｓの所与のソース−宛先ノード対間の経路ｒにおいて搬送されるべく設計される帯域幅である。通信トラフィックの統計的な特性を明確に見極める設計方法は、例えば「Optimization Method for Routing and Logical Network Design in Multi-Service Networks」という名称で、本出願と同じ譲受人に譲渡された、1998年１２月２９日にD.Mitra等に付与された米国特許第5,854,903号に記載される。典型的な設計方法を仮想私設網に拡張する方法は、「Method for Resource Allocation and Routing in Multi-Service Virtual Private Networks」という名称で、本発明と同じ譲受人に譲渡された、D.Mitra等による1998年４月２４日に出願された同時係属の米国特許出願第09/065,506号に記載される。多数の商品取引の流れに関連する概念に基づく設計方法は、「Multicommodity Flow Method For Designing Traffic Distribution On A Multiple-Service Packetized Network」という名称で、本出願と同じ譲受人に譲渡された、D.Mitra等による1999年８月９日に出願された米国特許出願第09/370,826号に記載される。
【０００６】
そのようなオフラインのネットワーク設計方法は有用ではあるが、その方法では、リアルタイムにトラフィックの状況に応答することはできない。しかしながら、トラフィックはランダムに変動する性質があるため、ルーティングの決定がリアルタイムの測定により通知可能であるなら、実現され得る全ての搬送されるトラフィックあるいは全収入において、多くの場合に潜在的な利益がある。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従って本発明は、ネットワークの動作において、より高い効率を達成するためにトラフィック負荷の測定値を用いるネットワーク管理手順を提供する。
【課題を解決するための手段】
【０００８】
本出願人は、ネットワーク動作において、より高い効率を達成するために、トラフィック負荷(すなわちトラフィック帯域幅)の測定を適用するネットワーク管理のための手順を開発した。
【０００９】
一実施例では、本発明は、選択された利用可能なサービス経路上で着信呼をいずれにルーティングするかを決定するための方法を含む。本方法によれば、利用可能なサービス経路は、いかにしてその測定された負荷がその設計負荷に一致するかに応じて、過剰な利用状態(oversubscribed)または標準利用状態(undersubscribed)に分類される。過剰利用状態の利用可能なサービス経路は、その各リンクが、ここで帯域幅予約(bandwidth reservation)と呼ばれるマージン以上に十分に大きい利用可能容量を有する場合にのみ、着信呼を搬送するだけの十分に利用可能な帯域幅を有するものと考えられる。
【００１０】
別の実施例では、本発明は課金収入を計算するための方法を含み、その方法では、所与の通信経路のための増加収入は、ネットワークサービスプロバイダがその所与の通信経路に関してＳＬＡに準拠するか否かに依存する。一実施例に従えば、準拠するサービスプロバイダは、送出された負荷が契約した範囲内にあるときには、送出された負荷のうちの少なくとも契約した部分(すなわち送出された通信経路帯域幅)を搬送しなければならないが、送出された負荷が契約した範囲より大きいときには、特定の負荷のみを搬送すればよい。徴収額の減額(revenue penalty)は、サービスプロバイダが準拠していない間に損失した、送出された通信経路帯域幅に対して要求される。
【００１１】
さらに別の実施例では、本発明は、所与の通信経路のために予定された着信呼に対する「入口ノード」において、その着信呼のための少なくともいくつかの利用可能なサービス経路がそれぞれ過剰利用状態か、標準利用状態かを判定するステップと、送出される負荷及び搬送される負荷の測定値から、ネットワークがある条件、例えば上記のＳＬＡ条件に準拠するか否かを判定するステップと、標準利用状態のサービス経路を優先的に選択する手順に従って着信呼をルーティングするステップと、ルーティングされた呼に起因して搬送される負荷に対して、少なくとも１つの時間窓においてプラスの収入増加を発生するステップとを実行することを含む。
【実施例】
【００１２】
本発明の実施に関連する典型的なＳＬＡは、各通信経路(s,σ)に対して、全送出帯域幅Ｕsσ(「契約された送出帯域幅」)と、全搬送帯域幅Ｖsσ(「契約された搬送帯域幅」)、Ｖsσ＜Ｕsσを規定する。事実上、比Ｖsσ＜Ｕsσは、その通信経路のために契約された通信量許容比(flow-acceptance ratio)である。着信するトラフィックの統計的な性質に起因して、着信呼の１００％が許容されることは、無限の容量を有するネットワークにしか保証できないため、この比は正確に一致させることはできないことに留意されたい。
【００１３】
ＳＬＡの項目に準拠するか否かを判定するために、測定値に基づいて、実際の送出帯域幅と搬送帯域幅が推定される。送出パケットと搬送パケットとを調べることにより、帯域幅を直接測定することができる。別法では、呼をカウントし、各呼に関連する有効帯域幅から全帯域幅が推定される(有効帯域幅は、以下に詳細に記載される)。いずれの場合でも、帯域幅測定は、入口ノード、すなわち対応する通信経路のソースノードにおいて行われることが望ましい。
【００１４】
最初に、呼レベルの課金に基づくＳＬＡ監視方式が記載される。その後、パケットレベル(すなわちデータレベル)の課金に基づくＳＬＡ監視方式の例が説明される。以下に記載する数値によるケース・スタディでは、呼レベルの課金を用いた。
【００１５】
典型的な測定手順は、ここで「ＳＬＡ窓(SLA windows)」と呼ぶ時間窓(time window)を用いており、また指数関数による平滑化処理も用いている。ＳＬＡ時間窓長τ及び平滑化パラメータαSLAもＳＬＡにおいて規定されることが望ましい。
【００１６】
【数１】
2005341540.tif 000003
（以下、「Ｖ〜ｓσ（ｎ）」と表記、以下、同種の符号について同様に表記）が時間窓ｎにおいて搬送される通信経路帯域幅の測定値を示し、Ｕ〜ｓσ（ｎ）が同じ時間窓において送出される通信経路帯域幅の測定値を示すものとする。各測定値は、ある程度の推定量を含むため、以下の説明において、この値を「推定された」帯域幅値と呼ぶ。
【００１７】
以下の説明では、Ｖ〜ｓσ(n)及びＵ〜ｓσ(n)の平滑化処理が用いられるか、用いられないかは任意選択である(以下に記載する数値を用いたケース・スタディでは、平滑化された値が行われた)。しかしながら、この状況において有用な平滑化処理の１つの形を示すために、ここで
【数２】
2005341540.tif 000004
（以下、それぞれ「Ｖ〜ｓσＳＭ(n)」及び「Ｕ〜ｓσＳＭ(n)」と表記、以下、同種の記号について同様に表記）は平滑化された値を表し、Ｖ〜ｓσＲＡＷ(n)及びＵ〜ｓσＲＡＷ(n)は対応する生の値、すなわち平滑化されていない値を示すものとする。その際、例示的な平滑化手法に従えば、以下のようになる。
【数３】
2005341540.tif 000005
【００１８】
典型的なＳＬＡに従えば、準拠する顧客は、その送出される通信経路帯域幅が契約した量を超えない顧客である。サービスプロバイダは、契約された送出帯域幅に対する契約された搬送帯域幅の割合と同じだけの推定された送出帯域幅の分を搬送することを保証する。サービスプロバイダが約束した帯域幅より少ない分しか搬送しない場合には、準拠していないことを表し、サービスプロバイダが準拠していない間に損失した(すなわち搬送されない)各呼に対して減額を行う。
【００１９】
一方、契約した量より広い通信経路帯域幅を送出する場合には、その顧客は準拠していない状態である。この場合には、サービスプロバイダは、搬送帯域幅のうちの契約された量のみを搬送することを保証する。契約された量を搬送し損なう場合には、サービスプロバイダが準拠していないことを表す。この場合にサービスプロバイダは、損失した呼、例えば契約した量までの失われた帯域幅に対して減額を行う。
【００２０】
入口ノードにおいて、顧客とサービスプロバイダの準拠状況を監視し、かつ対応する準拠状態、非準拠状態の通知が行われることが望ましい。
【００２１】
図１は、ＳＬＡ準拠のための典型的な決定プロセスを示す。ブロック５では、送出される通信経路帯域幅の推定値Ｕ〜sσ(n)が、契約された値Ｕsσと比較される。送出帯域幅の推定値(以下に見られるように、同様に搬送帯域幅の推定値)は、ｎ番目のＳＬＡ窓の端で判定される。しかしながら、サービスプロバイダがＳＬＡに準拠する場合には値「compliant」を取り、準拠しない場合には値「non-compliant」を取る変数「SLA_state」は、全時間窓に渡って均一になるように処理される(より一般的には、顧客及びサービスプロバイダのＳＬＡ準拠の各状態を記述する変数の対は、全時間窓に渡って均一になるように処理される)。この近似は処理の負担を制御するために有用であり、平均化を可能にし、精度を上げる傾向があることがわかった。
【００２２】
送出される帯域幅の推定値が契約値以下である場合には、ブロック５の出力は「yes」である。この場合、図の下側の左側の格子、すなわち象限Ａ及びＢにより表されるように、顧客はＳＬＡに準拠している。ブロック５の出力が「no」である場合には、象限Ｃ及びＤにより表されるように、顧客はＳＬＡに準拠していない。
【００２３】
サービスプロバイダがＳＬＡに準拠しているか否かの検査(同様に、変数SLA_stateの値を判定する)は、ブロック５の結果に応じて、異なる形を取る。準拠している顧客の場合には、ブロック１０の検査が当てはまる。ブロック１０では、送出される帯域幅に対する搬送される帯域幅の比が比較される。契約値の比Ｖsσ／Ｕsσが推定値の比Ｖ〜sσ(n)／Ｕ〜sσ(n)以下である場合には、図の象限Ａに示されるように、サービスプロバイダは、時間窓ｎの間にＳＬＡに準拠していることを表す。そうでない場合には、図の象限Ｂに示されるように、サービスプロバイダはＳＬＡに準拠していないことを表す。
【００２４】
準拠していない顧客の場合には、ブロック１５の検査が当てはまる。ブロック１５の検査に従えば、搬送帯域幅の契約された量Ｖsσが推定量Ｖ〜sσ(n)以下である場合には、図の象限Ｃに示されるように、サービスプロバイダは時間窓ｎの間にＳＬＡに準拠していることを表す。そうでない場合には、図の象限Ｄに示されるように、サービスプロバイダはＳＬＡに準拠していないことを表す。
【００２５】
搬送される全ての呼が、サービスプロバイダへの収入を発生し、通信料(flow revenue)の測定値Ｗsσ(n)を増加させる。例えば図２に示されるように、以前の累積的な収入測定値Ｗsσ(n-1)(図のブロック２０に示される)は、ブロック２５に示される現在の通信料だけ加算点３０において増加され、ＳＬＡ時間窓ｎのための現在の累積的な収入測定値Ｗsσ(n)(ブロック３５)を構成する。ブロック２５の現在の増加分は、時間窓ｎにおいて搬送される通信経路(s,σ)の呼の数Ｍsσ(n)と通信経路収入パラメータｗsσとの積である。限定するわけではなく、例として、数値を用いたケース・スタディでは、ｗsσを、有効帯域幅ｄsとサービスクラスｓの呼の平均保留時間ｈsとの積に等しくなるように設定していることに留意されたい。有効帯域幅は、ネットワーク構成要素のバースト、遅延、ジッタ及び損失ような種々のパケットレベルの要因に対して、１つのパラメータとして課金するように調整されることができる。
【００２６】
ＳＬＡに準拠していない状態の間に、サービスプロバイダが呼を損失する場合には、減額を行う義務が生じる場合もある。図２の典型的な方式では、累積的な通信料減額の測定の以前の値penaltysσ(n-1)(ブロック５５)は、現在の減額の増加分だけ加算点６０において増加され、時間窓ｎに対する累積的な測定の現在値penaltysσ(n)(ブロック６５)を構成する。現在の減額の増加分は、図のブロック４０に示される値である。しかしながら乗算器５０では、サービスプロバイダが時間窓ｎにおいてＳＬＡに準拠している場合には、現在の減額の増加分の乗算の重みとして、０が与えられる(その場合には、ブロック６５において累積値には加えられない)。そうでない場合には、減額の増加分の乗算の重みは１を取る。
【００２７】
ブロック４０に示されるように、減額の増加分は典型的には３つのファクタ、すなわち通信経路収入パラメータｗsσと、ＳＬＡ時間窓ｎにおいて損失した通信経路(s,σ)の呼の数Ｎsσ(n)と、典型的には１より大きい、調整可能な減額乗数ｍsσとの積である。
【００２８】
種々の別形態の減額構造を実施するのも容易である。例えば、送出される帯域幅の量がＳＬＡに規定される量より総量として多い場合でも、図２の減額構造は、ネットワークのＳＬＡ状態が図１の象限Ｄにある間に損失した全ての呼について、サービスプロバイダに減額を課す。送出されるトラフィックの全超過量を認めないために、搬送帯域幅の測定値(すなわち推定値)と契約値との間の差のみを含むように、図２のブロック４０のファクタＮsσ(n)を制限することが有効な場合もあろう。
【００２９】
加算点７０では、ブロック３５の累積的な通信経路収入値とブロック６５の累積的な通信経路減額値が、ブロック７５に示されるように、それぞれプラス及びマイナスの寄与値として、正味の通信経路収入W_netsσ(n)に組み合わせられる。全通信経路に渡ってW_netsσ(n)を加算することにより、ブロック８０に示されるように、累積的な正味の収入に関するネットワーク全体の測定値W_net(n)が与えられる。
【００３０】
上記の説明では、Ｖ〜sσ(n)及びＵ〜sσ(n)に対して平滑化した値を用いるか、平滑化されていない値を用いるかはオプションとして取り扱われてきた。しかしながら現在の考えに従えば、平滑化された値に基づいてＳＬＡ状態の判定を行うが、各時間窓において送出される帯域幅及び搬送される帯域幅の平滑化されていない値に基づいて収入及び減額値を計算することが特に有効であろう。
【００３１】
上記のように、呼レベルを監視することに対する別の形態は、パケット(データ)レベルで送出される帯域幅及び搬送される帯域幅を測定することである。例えばLeaky-bucket技術を用いれば、そのような測定を行うことが容易になる(Leaky-bucket測定は、搬送された帯域幅の量、及び準拠していないとして破棄された、あるいはマークされた量を示すであろう。従って送出される量は容易に推定される)。パケットレベルの測定においては、ωsσが、サービスプロバイダが、ある単位量の通信経路(s,σ)のデータを搬送することにより発生する収入を表すものとする。従ってこの状況において、時間窓ｎの間のこの収入の増加分に適した式は以下の通りである。
【数４】
2005341540.tif 000006
【００３２】
パケットレベルの測定において特に有効であると考えられる減額構造は、時間窓ｎの間に増加する減額値、すなわちpenaltysσ(n)−penaltysσ(n-1)に対して、以下の規定(i)〜(iii)により定義される。この規定は、図１の象限Ａ〜Ｄを参照して行われる。
(ｉ)通信経路(s,σ)のためのネットワークＳＬＡ状態が象限ＡあるいはＣにある場合には、減額値の増加分は０である。
(ii)ＳＬＡ状態が象限Ｂにある場合には、減額値の増加分は以下の式により表される。
【数５】
2005341540.tif 000007
(iii)ＳＬＡ状態が象限Ｄにある場合には、減額値の増加分は以下の式により表される。
【数６】
2005341540.tif 000008
【００３３】
表記［…］+は、括弧内の量が０より小さいなら、０に設定されることを意味している。
【００３４】
その通信経路のために許容可能な経路の中で、各通信経路のための送出されたトラフィックを(統計的な意味で)割り当てるにために、オフライン設計プロセスを用いることが望ましい。設計段階からＳＬＡ管理プロセスにまで至る情報は、一般にＵsσ及びＶsσ、並びに設計されたサービス経路負荷Ｘsrを含むであろう。トラフィック変動を見込んで余分な容量を予約するように、トラフィック帯域幅の平均値に基づく設計の生の出力から負荷Ｘsrを導出することが望ましいことがわかっている。従って、設計プロセスが、サービス経路上で搬送される全帯域幅の平均値Ｍsrを生成する場合には、Ｍsrにトラフィック変動に関連する付加的な増分を加えた値に等しい、対応する負荷パラメータＸsrを設定する。そのような変動の測定値として、例えば標準偏差を用いることができるが、十分な測定値が、平均値の平方根により与えられることがわかっている。従って、Ｘsr＝Ｍsr＋γ√Ｍsrを設定することが有効であることがわかっている。ただしγは小さな０以上の数であり、典型的には約０．５である。同様に、Ｖsσ＝Ｍsσ−β√Ｍsσを設定することが有効であることがわかっている。ただしβは別の小さな０以上の数であり、典型的には約０．５である。上記の式において、Ｍsσは、設計プロセスから得られた、通信経路(s,σ)の平均的に搬送される全帯域幅である。βが増加すると、トラフィック変動が増加するとともに、搬送帯域幅の契約量Ｖsσがより急激に減少する。従ってβを増加させることは、サービスプロバイダによって受ける不快感の増加を、損失した呼のために受ける減額に反映させるのに適している。一方βの増加は、ＳＬＡのために契約された通信量許容比Ｖsσ／Ｕsσを減少させる傾向もある。
【００３５】
損失した呼に対する減額構造は、上記のように、設計プロセスにオプションとして含めることができるが、その結果、ある程度複雑になるであろう。そのため以下に報告される数値を用いたケース・スタディでは、設計プロセスに減額構造は含めなかった。
【００３６】
別の収入構造を実施することも容易である。例えば、サービスプロバイダは、送出される帯域幅の量が契約量(contracted value)より大きい、すなわちネットワーク状態が図１の象限Ｃにあるとき、契約された帯域幅値で呼を搬送するための割増を要求することを望む場合もあろう。そのような場合には、ネットワーク状態が象限Ｃにあるときに、基本的な通信経路収入パラメータｗsσより大きい、第２レベルの収入パラメータを適用することができる。そのような第２レベルのパラメータは、例えば全搬送帯域幅に適用することができるか、あるいは契約量より多い搬送帯域幅に対してのみ適用することができる。
【００３７】
「経路分類」と呼ばれる、ネットワーク管理の段階では、各入口ノードは、全時間窓ｎに対して、入口ノードからの各サービス経路(s,r)の、呼に渡って合計された帯域幅負荷に基づいて変数statussr(n)を見積もり、これらの変数をデータベースに保管する。各変数statussr(n)は、時間窓ｎの始めに計算され、窓内で固定されたままである。この状態変数は、その入口ノードとして所与のノードを有する各通信経路、対応する各出口ノード、及び各サービスクラスｓのための各許容可能な経路ｒに対して計算される。
【００３８】
図３は、statussr(n)を見積もるための典型的なプロセスを示す。ブロック８５では、時間窓ｎの始めにサービス経路(s,r)上で測定された帯域幅負荷Ｚsr(n)が設計負荷Ｘsrと比較される。ブロック９０に示されるように、測定負荷が設計負荷以下である場合には、サービス経路の負荷状態は、「標準利用状態」であることを表す(すなわちstatussr(n)がＵＳに等しく設定される)。ブロック９５に示されるように、測定負荷が設計負荷より大きい場合には、その負荷状態は、「過剰利用状態」であることを表す(すなわちstatussr(n)がＯＳに等しく設定される)。サービス経路の負荷状態は、以下に記載される、「ルーティング及び認証制御」と呼ばれる段階の実施において重要である。
【００３９】
ここで、入口ノードにおいてローカルな測定値から計算される量を用いて、サービス経路帯域幅負荷Ｚsr(n)を測定するための典型的な手順が記載される。この測定手順は、時間窓の長さτと、平滑化パラメータαを用いる指数関数的な平滑化とに基づいている。異なる値の時間窓長及び平滑化パラメータを用いることができる同様の手順も、送出された通信経路負荷及び搬送された送信経路負荷、Ｕ〜sσ(n)及びＶ〜sσ(n)を計算するために容易に適用される。
【００４０】
ｔがｎ番目の時間窓内の時間値、すなわち(n-1)τ≦ｔ＜ｎτを表すものとする。Ｙsr(t)が、時間ｔにおけるサービス経路(s,r)上の全帯域幅使用量を示すものとする。Ｙsr(t)は、新しい各呼を有する、ある単位の有効帯域幅ｄsだけ増加し、各呼の終了時に同量だけ減少することに留意されたい。
【００４１】
【数７】
2005341540.tif 000009
（以下、「Ｙ￣ｓｒ(n)」と表記、以下、同種の記号について同様に表記）がｎ番目の時間窓に渡るサービス経路上の平均帯域幅使用量を示す、すなわち
【数８】
2005341540.tif 000010
である。Ｚsr(ｎ＋１)は、(ｎ＋１)番目の時間窓の開始時点でのサービス経路上で、呼に渡って合計された帯域幅使用量の指数関数的に平滑化された推定値を示すものとする。
【００４２】
そのとき本発明の方法に従えば、Ｚ￣ｓｒ(n＋1)＝αＺｓｒ(n)＋(1−α)Ｙｓｒ(n)が成立する。
【００４３】
他のノード(もちろん各通信経路のための呼に関して入口ノードである場合がある)からの干渉を受けることなく、その入口ノードのみがサービス経路(s,r)上で呼を設定されているので、全ての必要な負荷情報が利用可能であることについて留意されたい。
【００４４】
ここで、ルーティング及び認証制御のための制御アルゴリズムを説明する。最初に、これらのアルゴリズムは、仮想パーティショニング(Ｖirtual Ｐertitioning：ＶＰ)として知られる方法を適用することに注目されたい。ＶＰ法では、各リンクｌの帯域幅容量は、リンクｌが含まれる全てのサービス経路による競合の対象となるリソースと見なされる。このＶＰの応用形態では、標準利用状態(所与の時間において)の競合するそれらのサービス経路は、過剰利用状態のサービス経路より高い優先権を与えられる。以下に説明するように、ここで帯域幅保護(ＢＰ)と呼ばれる手順は、所与の通信経路に関連する新しい呼が設定されるとき、この優先権を履行する。呼設定時に、典型的な実施例では、入口ノードは、対象のサービス経路及び現在の時間窓ｎに対するstatussr(n)の値の要求及び指示を、対象のサービス経路の各リンクに送出することに留意されたい。
【００４５】
ここで、図４を参照して帯域幅保護手順を記載する。この手順は、入口ノードにおいて実行されることが望ましい。ｌが可能なサービス経路により横断されるリンクを表し、Ｃlがリンクｌの帯域幅容量を表し、ｙl(ｔ)が呼設定の時間ｔにおけるリンク上の全帯域幅使用量を表すものとする(明らかに、ｙl(ｔ)はＣlより大きい値を取ることができない)。(s,r)が、着信呼をルーティングするために選択されている利用可能なサービス経路を表すものとする。
【００４６】
図のブロック１００では、現在の時間窓ｎにおける利用可能なサービス経路の状態が標準利用状態であるか否か(すなわちstatussr(n)がＵＳに等しいか)の判定が行われる。サービス経路が標準利用状態であると判定される場合には、ブロック１０５においてさらに、呼を許容するだけの十分に利用可能な帯域幅がサービス経路上にあるか否かの判定が行われる。ブロック１０５では、呼設定の時間に、利用可能なサービス経路により横断される全てのリンクｌに対して、着信呼の有効帯域幅ｄsを受け入れるだけの十分な残り容量が存在する場合にのみ、すなわち、ｌ∈(s，r)，ｙl(ｔ)＋ｄs≦Ｃlの場合にのみ、十分な帯域幅が存在するであろう。この条件が満たされる場合には、ブロック１１５において示されるように、その呼は許容される。そうでない場合には、ブロック１２０に示されるように、その呼は拒否される。
【００４７】
再びブロック１００を参照すると、サービス経路が標準利用状態でないと判定される場合には、過剰利用状態となる(すなわちstatussr(n)がＯＳに等しい)。その場合には、ブロック１１０において、サービス経路上に、その呼を許容するだけの十分に利用可能な帯域幅があるか否かの判定が行われる。ブロック１１０において適用される検査は、ブロック１０５において適用される検査より負荷が重い。ブロック１１０では、サービス経路により横断される各リンクｌは、有効帯域幅ｄｓの場合のみならず、ここで帯域幅予約と呼ばれる帯域幅の量
【数９】
2005341540.tif 000011
（以下、「Ｒｄ＾」と表記、以下、同種の記号について同様に表記）の場合も残り容量を有することが必要とされる。すなわち、
【数１０】
2005341540.tif 000012
の場合にのみ、その呼が許容される（ブロック１２５）。そうでない場合には、その呼は拒否される(ブロック１３０)。
【００４８】
帯域幅予約Ｒｄ＾は、本ルーティング手順に対して、２つの観点から標準利用状態のサービス経路に強制的に優先権を与えるようにする。第１に、過剰利用状態のサービス経路上で呼をルーティングしようとする試みは、標準利用状態のサービス経路上でルーティングを試みる場合より多く要求される検査を満足しなければならない。第２に、帯域幅予約を強要することにより、過剰利用状態のサービス経路上での呼のルーティングが成功した後に、その経路に沿った各リンクが、そのようなリンクが含まれる少なくとも１つの標準利用状態のサービス経路上で呼を搬送するための容量を依然として有することが確実になる(Ｒの値に応じて、いくつかの標準利用状態のサービス経路上で呼を搬送するための残り容量が存在する場合もある)。
【００４９】
ここで記載される帯域幅予約は２つのファクタ、すなわち帯域幅保護パラメータＲ及び量ｄ＾の積である。帯域幅保護パラメータは、調整可能な小さな正の数であり、典型的には１．０〜２．０の範囲にあり、代表値は約１である。量ｄ＾は、例えば全てのサービスクラスに渡って最も大きな有効帯域幅、すなわち
【数１１】
2005341540.tif 000013
である。
【００５０】
選択されたサービス経路上で呼を設定するための試みは、図４の帯域幅保護手順が実施された後に、そのサービス経路の全てのリンクがその呼を許容する場合にのみ成功することに留意されたい。
【００５１】
上記のように、量ｙl(ｔ)は、呼設定の時間ｔにおけるリンクｌ上の全帯域幅使用量を表す。入口ノードが、関連する経路に属するリンク上での帯域幅使用量に関するこの情報を捕捉するために種々の方法がある。１つのアプローチは、入口ノードが、典型的には、関連するルータから使用量情報(usage information)を要求する特殊化した偵察パケット(scout packet)を、必要に応じて送出することである。そのようなアプローチは有効ではあるが、少なくともある場合には不都合が生じる恐れがある、比較的大きな量のシグナリング・トラフィック・オーバーヘッドをネットワークに与える。別のアプローチは、「周期的な情報伝送」(periodic flooding)と呼ばれることもあり、入口ノードが、ネットワークに対して使用量情報のための要求を定期的に報知することである。このアプローチは、偵察パケットで使用した量より少ないトラフィックオーバーヘッドしか付加しないが、次の要求までに報知サイクルの遅れが生じ、一般に入口ノードは遅れた情報を必然的に用いることになる。
【００５２】
さらに第３のアプローチは、少なくともある場合には有効であると考えられるアプローチであり、入口ノードが以前の呼設定要求を通して捕捉した使用量情報を適用する。このアプローチの利点は、シグナリングトラフィックオーバーヘッドをほとんど、あるいは全く付加せず、少なくともいくつかの経路の場合、最新のルーティングの試みと同じ新しい情報を提供する。リンク使用量情報を捕捉するために以前の呼設定の試行を使用することは、例えば「A Method Of Admission Control And Routing Of Virtual Circuits」という名称で、本出願とともに譲渡された、R. Gawlick等による1995年１１月３０日に出願された同時係属の米国特許出願第08/565737号に説明される。
【００５３】
ここで図５を参照すると、ブロック１３５において、通信経路(s,σ)のための新しい呼をルーティングするための要求が表される。ブロック１４０及び１４５は、スティック・ルーティング(sticky routing)として知られる手順に従って呼をルーティングするための試みを表す。スティック・ルーティングは、例えばR.J.Gibbens等による「Dynamic alternative routing modeling and behavior」(Proc. 12th Int. Teletraffic Congress, Torino, 3.4A.3.1-3.4A.3.7，1988年)に記載される。
【００５４】
入口ノードは、関連する通信経路のための任意の許容可能な経路上で新しい呼をルーティングすることを試みるオプションを有する。スティック・ルーティング手順に従えば、優先されるのは、同じ通信経路のための呼がルーティングに成功した最後のサービス経路を使用することである。しかしながら図５の典型的な手順では、最後のサービス経路(ブロック１４０において、「current(s,r)」として示される)は、現在の時間窓ｎにおいて標準利用状態の場合にのみ選択されることができる。こうして、ブロック１４０の標準利用状態のための検査が満足される場合には、ブロック１４５に示されるようにルーティングを試みるために、サービス経路current(s,r)が選択される。
【００５５】
ブロック１４０の検査が満足されない場合には、ブロック１５０に示されるように、現在の時間窓において、標準利用状態の許容可能な経路の組Ｒ(s,σ)において任意のサービス経路が存在するか否かの判定が行われる。そのようなサービス経路が少なくとも１つある場合には、時間窓ｎにおいて許容可能なサービス経路の組ＲUS(s,σ;n)が定義され、ブロック１５５に示されるように、その組の要素、典型的にはランダムに選択された要素が、ルーティングを試みるために選択される。
【００５６】
ブロック１５０において、許容可能な標準利用状態のサービス経路が見つけられない場合には、ブロック１６０に示されるように利用可能な過剰利用状態のサービス経路のうちの好ましい経路が選択される。その好ましい過剰利用状態のサービス経路は、最も負荷が大きいと判定される経路である。この状況では、負荷の量は、設計負荷Ｘsrが、時間ｔでサービス経路上の全帯域幅使用量Ｙsr(ｔ)より大きい分の量である。こうして最も負荷が大きい経路は、量Ｙsr(ｔ)−Ｘsrを最小にする許容可能な経路の組の中の経路である。入口ノードがＹsr(ｔ)とＸsrの値の所有権を有するため、最も負荷が大きい経路の判定は、入口ノードにおいて容易に行うことができることに留意されたい。
【００５７】
一旦サービス経路が選択されたなら、ブロック１６５において、選択された経路で呼を設定するための試みが行われ、その際図５の帯域幅保護手順が実施される。ブロック１７０では、ルーティングの試みが成功したか否かの判定が行われる。成功した場合には、もし用いられるならスティック・ルーティングに従って、ブロック１７５に示されるように、最後の成功したサービス経路current(s,r)を含むレジスタが更新される。ブロック１７０での検査により、その試みが失敗したことが示される場合には、その呼は損失されるか、あるいは代替的に、以下に記載される、クランクバック(crankback)と呼ばれる手順に従って、その呼をルーティングするための新しい試みが行われる場合もある。
【００５８】
スティック・ルーティングが適用されている場合であって、ブロック１７０における検査がルーティングの試みが失敗したことを示す場合には、ブロック１８０に示されるように、current(s,r)がヌル値に設定される。
【００５９】
選択されたサービス経路において呼設定を行うための試みが失敗した場合、そのサービス経路が別の呼設定要求を受け入れることができる可能性は最初は小さいが、時間とともに高くなるであろう。従って一般に、ここで再生時間と呼ばれる時間Ｔrecの間、選択されたサービス経路を選択対象から排除することが望ましいであろう。時間Ｔrecの間、経路選択手順からそのような経路を排除することが、図５のブロック１８０に示される。
【００６０】
ブロック１８５に示されるように、ブロック１３５〜１８０の呼設定の試みの結果とともに、監視データが更新される。「監視データ」は、状態決定、収入及び減額計算等において用いられることになる情報を意味している。そのような情報は、例えば、搬送及び阻止される呼の数、搬送及び阻止される帯域幅等のトラックを保持する入口ノードにおけるデータベースのエントリを含む。
【００６１】
上記のように、呼設定の試みが失敗した場合には、クランクバック手順を適用することにより新しい呼設定の試みが行われる場合もある。典型的なクランクバック手順に従えば、ブロック１８５の後、新しい呼がルーティングされたか、あるいは呼設定要求が所定の回数だけ失敗するまで、ブロック１４０〜１８５の手順が繰り返される。少なくともいくつかの場合には、一定の条件を満足する場合にのみクランクバックを適用することが望ましい。例えば、選択的なクランクバックの一形態では、その呼を損失することにより、サービスプロバイダが減額を被るようになる場合にのみ、すなわちサービスプロバイダが現在、関連する通信経路に関してＳＬＡに準拠していない場合にのみ、新しい呼設定の試みが行われる。
【００６２】
上記のように、オフライン設計段階からＳＬＡ管理プロセスに至る情報は一般に、送出される通信経路帯域幅の設計値Ｕsσ、搬送される通信経路帯域幅の設計値Ｖsσ、各通信経路に対応する各サービス経路上で搬送される全帯域幅の平均値Ｍsrを含むであろう。上記のように設計値Ｍsrから、サービス経路の設計負荷Ｘsrが得られる。
【００６３】
また上記のように、ＳＬＡが、顧客により特定される一組の通信経路それぞれにおいて、要求に応じて、利用可能にされる帯域幅の量を規定するときに、ＶＰＮが定義される。送出される通信経路帯域幅及び搬送される通信経路帯域幅に関して上記したＳＬＡ準拠の概念は、ＶＰＮが規定されている準拠の問題を処理するために
容易に拡張される。すなわち、以前に図１のブロック１０及び１５の検査が、所与の通信経路(s,σ)に固有の量Ｖsσ、Ｕsσ、Ｖ〜sσ(n)及びＵ〜sσ(n)に適用されたが、ここで同じ検査が、添字νを有する特定のＶＰＮに属する所与の副次的な通信経路(s,σ;ν)に固有の類似の値、Ｖs,σ(ν)、Ｕs,σ(ν)、Ｖs,σ(ν)(n)及びＵs,σ(ν)(n)にされる。そのような副次的な通信経路を「ＶＰＮ通信経路」と呼ぶ。
【００６４】
こうして、図２に関連して上記したような収入及び減額構造は、サービスプロバイダが、その顧客のためのＶＰＮを動作させることによって顧客から徴収することができる正味の収入を決定するように容易に変更される。
【００６５】
オフライン設計段階への入力として、１つあるいは複数のＶＰＮが規定される場合もある。そのような場合には、前述した負荷Ｘsrに類似ではあるが、特定のＶＰＮ、νのトラフィックに固有であるサービス経路負荷Ｘsr(ν)を、設計段階の出力から直接、あるいは変更後に得ることができる。負荷Ｘsr(ν)を「ＶＰＮサービス経路設計負荷」と呼ぶ。
【００６６】
上記のように、種々のサービス経路(同じ通信経路及び異なる通信経路の場合の両方)は、サービス経路の中で共有されるリンク上で制限された帯域幅容量において競合する。あまりにも大きなトラフィックが所与のリンクを通してルーティングされる場合には、ネットワーク障害が発生するようになる。この帯域幅保護手順は、同じリンクを横断する標準利用状態のサービス経路に利用することができる過剰利用状態のサービス経路上のリンク帯域幅を予約することにより、そのような障害を防ぐ助けとなる。
【００６７】
ＶＰＮが導入されるとき、さらに別の競合の形態が現れる。例えば、異なるＶＰＮが同じリンク帯域幅において競合し、また１つのＶＰＮ内で、異なる通信経路及び同じ通信経路に属する異なる経路が、同じリンク帯域幅において競合する場合もある。これらの競合の形態は、図４の帯域幅保護手順を単に拡張するだけで、容易に取り扱える。上で定義した変数statussr(n)に類似ではあるが、ＶＰＮ、νに属するサービス経路に固有の新しい変数statussr(ν)(n)を定義することにより、前述の概念が拡張される。ＶＰＮサービス経路(s,r;ν)は標準利用状態を表しており、statussr(ν)(n)は、時間窓ｎのＶＰＮサービス経路(s,r;ν)上で測定された負荷Ｚsr(ν)(n)が設計負荷Ｘsr(ν)以下である場合には、ＵＳに等しく設定される。そうでない場合には、ＶＰＮサービス経路は過剰利用状態を表しており、statussr(ν)(n)はＯＳに等しく設計される。
【００６８】
図４の手順と同様に、呼が過剰利用状態のＶＰＮサービス経路上でルーティングされる場合には、帯域幅予約Ｒ１ｄ＾が義務づけられる。
【００６９】
所与のＶＰＮ内では、そのＶＰＮに関連する種々のサービスクラス間での競合が生じる場合もある。すなわち、それは多くの場合に、ＶＰＮの所有者が、全てのクラスの呼の累積的な許容率との関連性より、特定クラスのサービスに対する呼の許容率との関連性が低い場合である。そのようなＶＰＮ所有者は、ネットワークリソースを支配し、他のクラスの呼を排除するために、ある特定のサービスクラスの呼を妨げることを望むであろう。そのような環境では、設計されたトラフィックのシェア以上を取得している場合には、所与のＶＰＮソース−行先ノード対を過剰利用状態として特徴付けることが有用である。任意のサービスクラスの新しい呼は、帯域幅予約Ｒ２(ν)ｄ＾が、その結果的なＶＰＮサービス経路に課せられる場合にのみ、過剰利用状態の対の間でルーティングされるであろう。
【００７０】
一般に、帯域幅予約パラメータＲ1は、ネットワーク上の全てのＶＰＮに共通であるが、帯域幅予約パラメータＲ2(ν)は、各ＶＰＮの場合に個別にネゴシエーション(negotiation)される。一般に、Ｒ2(ν)はＲ1と少なくとも同じ大きさであろう。
【００７１】
上記概念が、図６を参照してさらに詳細に記載される。枠１９０では、変数statussr(ν)(n)は、上記のように値ＵＳあるいはＯＳを取る。枠１９５では、さらに別の変数statusσ(ν)(n)が導入される。この変数は、全てのサービスクラス及び全ての許容可能な経路に渡って負荷変数Ｘsr(ν)を加算することにより得られるＶＰＮ設計負荷Ｘσ(ν)に関連して定義される。すなわち、
【数１２】
2005341540.tif 000014
である。ただしＲ(ν)(s,σ)はＶＰＮ通信経路(s,σ;ν)のための許容可能な経路の組である。設計負荷Ｘσ(ν)が、全てのサービスクラスに渡って加算された、ＶＰＮ通信経路(s,σ;ν)のための時間窓において搬送される帯域幅に等しい測定された負荷Ｚσ(ν)(n)と比較される。Ｚσ(ν)(n)がＸσ(ν)以下である場合には、変数statusσ(ν)(n)はＵＳに等しく設定される。そうでない場合には、ＯＳに等しく設定される。
【００７２】
図の象限Ａは、statusｓｒ(ν)(n)及びstatusσ(ν)(n)の両方がＵＳに等しい状態を表す。この場合には、着信呼は、帯域幅予約を課すことなく、提供されたサービス経路上でルーティングために許容される。
【００７３】
図の象限Ｂは、statusｓｒ(ν)(n)はＯＳであるが、statusσ(ν)(n)はＵＳである状態を表す。この場合には、帯域幅予約Ｒ１ｄ＾が利用可能な場合にのみ呼が許容される。
【００７４】
図の象限Ｃは、statusｓｒ(ν)(n)はＵＳであるが、statusσ(ν)(n)はＯＳである状態を表す。この場合には、帯域幅予約Ｒ２ｄ＾が利用可能な場合にのみ呼が許容される。
【００７５】
図の象限Ｄは、statusｓｒ(ν)(n)及びstatusσ(ν)(n)の両方がＯＳである状態を表す。この場合には、上記の帯域幅予約の両方が利用可能な場合にのみ、すなわち全帯域幅予約(Ｒ１＋Ｒ２ (ν))ｄ＾が利用可能な場合にのみ呼が許容される。
【００７６】
上記の説明から、ＶＰＮトラフィックは種々のレベルの集合体において考慮されうることが、当業者には理解されよう。低いレベルの集合体では、トラフィックは、３組の指標(s,r;ν)により特定される、ＶＰＮサービス経路のレベルにおいて考慮することができる(全ての経路ｒは、ソース、すなわち入口ノードσ1と、宛先、すなわち出口ノードσ2とからなる、いくつかの所与のソース−宛先対σに対応することを理解されたい)。高いレベルでは、トラフィックは、所与の通信経路に対応する全経路に渡って合計される。これは、３組の指標(s,r;ν)により特定される、ＶＰＮ通信経路レベルを定義する。
【００７７】
さらに高いレベルでは、ＶＰＮ通信経路トラフィックは全サービスクラスに渡って合計される。これは、一対の指標(σ;ν)により特定される、ＶＰＮパイプレベルを定義する。上で定義した変数statusσ(ν)(n)は、ＶＰＮパイプレベルにおけるトラフィック負荷に関連することは理解されよう。
【００７８】
より高いレベルでは、ＶＰＮパイプトラフィックは、共通の入口ノードσ1を共有する異なるソース−宛先対σに渡って合計される。言い換えると、所与の入口ノードからの全ＶＰＮパイプトラフィックがともに合計される。これは、一対の指標(σ1;;ν)により特定される、ＶＰＮホース(hose)レベルを定義する。
【００７９】
図６を参照した上記の方法は、ＶＰＮサービス経路とＶＰＮパイプとによって帯域幅の共有を調節(regulate)するために設計される。少なくともいくつかの場合には、ＶＰＮパイプレベルより高いか、あるいは低いレベルの集合体において図６の方法を適用することが望ましいであろう。すなわち、ＶＰＮ通信経路レベルあるいはＶＰＮホースレベルにおいて、statusσ(ν)(n)に類似の変数が容易に案出され、statusσ(ν)(n)の代わりに図６の方法において適用される。
【００８０】
以下に本発明の実施例を記載する。図７に示されるように、８個のノード(Ｎ＝８)を有し、その１０対が直接接続される仮想的なネットワークに基づいて、数値を用いたケース・スタディを行った。ネットワークは、２０個の向きを決められた有向リンク(Ｌ＝２０)を有し、その向きは接続された各ノード対の各方向の１つである。有向リンクの典型的な帯域幅はＯＣ３＝１５５Ｍｂｐｓであるが、アルゴンヌ(３)、プリンストン(４)、ヒューストン(８)及びアトランタ(７)を接続するリンクは例外であり、その帯域幅は２×ＯＣ３＝３１０Ｍｂｐｓである。ネットワーク内の全リソースの１つの測定値は２４ＯＣ３−ｈｏｐｓである。
【００８１】
それぞれｓ＝１、２、…、６により示される６個のサービスクラス、すなわち音声、データ１、データ２、データ３、データ４及び映像(video)がある。これらのサービスクラスの個々のフローの有効帯域幅は、ｄs＝１６、４８、６４、９６、３８４及び６４０Ｋｂｐｓである。音声(ｓ＝１)及び映像(ｓ＝６)は遅延に影響されやすいサービスクラスであり、その許容可能な経路の組Ｒ(s,σ)は、最小限のホップ数を有する経路のみからなる。これら２つのサービスクラスはそれぞれ全６８経路を有する。残りの４つはデータサービスクラスであり、全て遅延に影響されない。その許容可能な経路の組はＲ(s,σ)、ｓ＝２、３、４、５は同じであり、４つ以下のホップを有する経路からなる。そのような各ｓについては、全１６０経路ある。
【００８２】
そのサービスクラスのフローの平均持続時間あるいは保持時間ｈsは、１、１、１、４、４、６．６７であり、時間の単位は３分である。従って映像フローは平均で２０分間継続する。
【００８３】
次に、ＳＬＡにおいても規定され、設計において用いられる、通信経路(s,σ)に送出される全帯域幅Ｕsσを説明する。ここで行列Ｕs＝｛Ｕsσ｝、ｓ＝１、２、…、６を定義し、さらに簡潔にするために、１つの基本行列Ｕを定義し、その行列から、Ｕs＝ｋsＵを得る。ただしｋsはスカラー乗数である。その乗数は、ｋs＝０．３９、０．１４、０．１２、０．１４、０．１１、０．１０である。リアルタイムサービス(ｓ＝１及び６)のための全送出トラフィックは、データサービスのためのトラフィックと概ね釣り合う。表Ｉは行列Ｕを与える。
【００８４】
搬送フローから収入への変換は、ある単位時間に搬送される１６Ｋｂｐｓ帯域幅が単位収入を発生することに基づいて計算される。
【００８５】
D. Mitra等による「ATM network design and optimization: A multirate loss network framework」(IEEE/ACM Trans. Networking 4 531-543(1996))に記載される技術により、ケース・スタディのための設計を行った。その設計により、０．９９より大きい個々の通信経路のためのフロー許容率が与えられる。
【００８６】
ここでは、全通信経路(s,σ)、すなわち全サービスクラス及び入口−出口ノード対のための実際に送出される全トラフィックの組により特徴付けられる特有のトラフィックパターンをそれぞれ有する、３つのシナリオを考慮した。そのトラフィックパターンは以下の通りである。
(ｉ)標準パターン：送出されるトラフィックＵ(s,σ)が、ＳＬＡ及び設計において規定された量と同じである理想的なケースである。
(ii)均衡の取れた異常パターン：任意に選択されるノード対の半分は、送出されるトラフィックを全く有さず、一方残りの半分は、各サービスクラスのために、ＳＬＡ／設計値の２倍の送出されるトラフィックを有する。
(iii)均衡の取れない異常パターン：任意に選択された、全ノード対の２５％が、各サービスクラスのために、ＳＬＡ／設計の各値の２倍大きい実際に送出されるトラフィックを有し、一方残りの７５％では、実際に送出されるトラフィックは予想通りである。
【００８７】
フローの持続時間あるいは保持時間は、指数関数的に分布するものと仮定される。
【００８８】
正味の収入、W_net(…)及びpenalty(…)が上記で累積的に定義されたのに対して、この節において提供される結果は、単位時間に対して、すなわちシミュレートされた時間の長さで割ることにより累積的な量から得られる。
【００８９】
サンプルパス(全てのフロー要求の時間及びプロファイル)は、所与のシナリオ(scenarios)の全ての試行に対して同じく再現された。全ての試行の場合、1000万のフローがシミュレートされる。ここで報告される統計値は、固定状態に達するために十分に大きくなるように選択された移行時間の後に収集された結果に基づく。統計値に寄与するフローの数は、信頼区間が無視できるほど小さくなるように十分に大きい。
【００９０】
このスタディの対象のパラメータは、β、すなわち設計／ＳＬＡインターフェースの補償パラメータ、α及びτ、すなわち測定プロセスにおける指数関数的な平滑化パラメータ及び時間窓長、並びに重要なＲ、すなわち帯域幅保護パラメータである。
【００９１】
測定パラメータは実験的に選択された。より大きなαは、より大きな平滑化と、より長い時間窓長を意味する。いずれか一方が増加することにより、測定の品質が改善されるが、著しいトラフィック変動への応答が遅くなることを犠牲にしている。このスタディでは、それを満足するための妥協案は、τ、すなわち平均保持時間のオーダを１に等しく設定し、αを０．８にすることである。またここで報告された結果の場合、ＳＬＡ監視プロセスの平滑化パラメータ及び時間窓長を上記と同じようにしている。
【００９２】
以下に帯域幅保護の効果について記載する。正味の収入における帯域幅保護の効果は、標準パターン、均衡の取れた異常パターン及び均衡の取れていない異常パターンの場合にそれぞれ表II、III及びIVに示される。これらのスタディの場合、パラメータγ及びβを０．５に固定した。ここでは、選択的なクランクバック及び再生時間機構を適用していない。
【００９３】
標準的なトラフィック条件の場合、正味の収入における帯域幅保護及び減額乗数の効果は、小さくなることがわかった。これは、収入を最大にするようにこのトラフィック条件に対してルーティングアルゴリズムが特に最適化され、またＳＬＡが、実際に搬送される帯域幅が送出される帯域幅に非常に近く、小さな損失比を示すように巧みに操作されているためである。結果として、減額は、全ての発生した収入に比べて著しく小さくなる。さらに発生した全収入は、帯域幅保護を高めると、わずかに減少する。この動きは、送出されるトラフィックのバースト的な性質のため、帯域幅保護が標準的な条件においても適用されていることを示す。
【００９４】
次に均衡の取れた異常トラフィックパターンでは、全ての送出される帯域幅が標準に近い場合であっても、最初に、送出される帯域幅と実際に搬送される帯域幅との間に顕著なギャップが見られる。ここで最も重要なのは、帯域幅保護の効果である。その保護が全ての発生した収入に関して大きな損失を引き起こすことはなく、１単位の帯域幅保護が適用されるときに、減額は１桁だけ低減され、２単位の帯域幅保護が適用されるときには、さらに半分だけ低減される。均衡の取れていない異常トラフィックの場合には、この動きは顕著になり、いずれのシナリオにおいても、小さな帯域幅保護でも著しく有効で、十分な効果があることがわかる。用いられる減額乗数に応じて、帯域幅保護のための最適値は１か、２であることが、その結果からわかる。
【００９５】
設計−ＳＬＡインターフェースにおける補償パラメータの効果について記載する。表５は、帯域幅保護パラメータＲ＝１で、他のパラメータが上記と同じであるときの、３つのシナリオの場合に、βが変動する効果を示す。
【００９６】
以上のように本発明によれば、ネットワークの動作において、より高い効率を達成するためにトラフィック負荷の測定値を行うネットワーク管理手順を実現することができる。
【００９７】
【表１】
2005341540.tif 000015
【００９８】
【表２】
2005341540.tif 000016
【００９９】
【表３】
2005341540.tif 000017
【０１００】
【表４】
2005341540.tif 000018
【０１０１】
【表５】
2005341540.tif 000019
【図面の簡単な説明】
【０１０２】
【図１】例示的なタイプのＳＬＡによる準拠決定を示す注釈を付けた流れ図である。(i)所与の通信経路の送出される負荷について、顧客が契約した範囲に準拠するか否か、(ii)サービスプロバイダ(図において「ＳＰ」で示される)が、送出された負荷のうちの契約された量を搬送するか否かによって、図のように、４つの結果を取り得る。
【図２】一実施例において、本発明の例示的な実施例による増加する通信経路収入計算を示す流れ図である。図の下側近くにある最終的な加算点では、搬送される負荷に対するプラス分の収入増加と、損失した負荷に対するマイナス分の減額とが組み合わされ、正味の通信経路収入増加を構成する。
【図３】一実施例において、本発明の例示的な実施例に従って、測定された負荷を設計負荷と区分けすることにより、サービス経路の負荷状態を判定する方法を示す流れ図である。
【図４】一実施例において、本発明の例示的な実施例による、ルーティング決定における帯域幅保護を示す流れ図である。
【図５】一実施例において、本発明による所与の通信経路のための新しい呼を要求するための処理方法を示す流れ図である。図４の帯域幅保護手順は、図５の手順に含まれる。
【図６】ＶＰＮがネットワークによりサポートされるときに適用することができる帯域幅保護の典型的な形を示す図である。
【図７】実施例において記載される数値を用いたケース・スタディのための基本構成として用いられる仮想的な通信ネットワークの概略図である。
【図１】
2005341540.tif 000020
【図２】
2005341540.tif 000021
【図３】
2005341540.tif 000022
【図４】
2005341540.tif 000023
【図５】
2005341540.tif 000024
【図６】
2005341540.tif 000025
【図７】
2005341540.tif 000026