(57)【特許請求の範囲】
【請求項１】
ネットワークのための輻輳制御方法であって、
予め定められた時間間隔の間に、１組の仮想パスを前記ネットワークの１組の発信ノード及び宛先ノードのペアの間に割り当て、
前記予め定められた時間間隔の間に、１組の最大許容レートを前記割り当てられた仮想パスの組にそれぞれ割り当て、
前記予め定められた時間間隔の間に、１組のバーストアクセスしきい値を１組のサービスクラスにそれぞれ割り当て、ここで、前記割り当てられたバーストアクセスしきい値は対応する前記割り当てられた最大許容レート以下であり、
トラフィックをバーストレベルで前記各発信ノードにおいて最大許容レートの前記割り当てられた組及びバーストアクセスしきい値の前記割り当てられた組に基づいて制御する諸ステップから成ることを特徴とする輻輳制御方法。
【請求項２】
請求項１の方法であって、前記制御するステップが、
前記発信ノードの１つで前記トラフィックのバーストの始まりを検出し、
前記割り当てられた仮想パスの組の中から、前記検出されたバーストに対応する前記割り当てられた仮想パスを識別し、
前記サービスクラスの組の中から、前記検出されたバーストに対応する前記サービスクラスを識別し、
前記割り当てられたバーストアクセスしきい値の組の中から、前記識別されたサービスクラスに対応する前記バーストアクセスしきい値を識別し、
前記識別された割り当てられた仮想パスで進行中の全バーストに対して確保されたピークセルレートの合計＋前記検出されたバーストのピークセルレートが前記識別されたバーストアクセスしきい値以下の時、前記検出されたバーストを取り入れ、
前記識別された割り当てられた仮想パスで進行中の全バーストに対して確保された前記ピークセルレートの合計＋前記検出されたバーストのピークセルレートが前記識別されたバーストアクセスしきい値より大きいとき、前記検出されたバーストを拒絶する諸ステップから成ることを特徴とする請求項１に記載の方法。
【請求項３】
請求項２の方法であって、前記取り入れるステップが更に、
前記識別された割り当てられた仮想パスに、前記検出されたバーストの前記ピークセルレートに等しいバンド幅を確保することを含むことを特徴とする、請求項２に記載の方法。
【請求項４】
請求項２の方法であって、
前記検出されたバーストの終わりを検出したとき、前記確保されたバンド幅を前記識別された割り当てられた仮想パスに開放するステップを更に含むことを特徴とする、請求項２に記載の方法。
【請求項５】
ネットワークで１組のバーストアクセスパラメータを決定するための方法であって、
１組の割り当てられた仮想パスに対応する１組の最大許容レートをそれぞれ計算し、
各割り当てられた仮想パスの１組のサービスクラスに対応する１組の推定提供負荷を前記計算された最大許容レートに基づいて計算し、
ネットワークのバースト拒絶の重み付けされたレートの合計がネットワーク容量制約、サービスの品質制約、及びフロー制約の維持に従って最小化されるように、前記計算された最大許容レートの組及び前記計算された推定提供負荷の組に基づいて１組のバーストアクセスしきい値を計算する諸ステップから成る方法。
【請求項６】
ネットワークで輻輳を回避するための方法であって、
予め定められた時間間隔の間に、１組の仮想パスをネットワークの１組の発信ノード及び宛先ノードのペアの間に割り当て、
前記予め定められた時間間隔の間に、１組の最大許容レートを前記割り当てられた仮想パスの組にそれぞれ割り当て、
トラフィックをバーストレベルで前記各発信ノードにおいて前記割り当てられた最大許容レートの組に基づいて制御する諸ステップから成り、
前記制御するステップが、
前記発信ノードの１つで前記トラフィックのバーストの始まりを検出し、
前記割り当てられた仮想パスの組の中から、前記検出されたバーストに対応する前記割り当てられた仮想パスを識別し、
前記識別された割り当てられた仮想パスで進行中の全バーストに対して確保されたピークセルレートの合計＋前記検出されたバーストのピークセルレートが前記識別された割り当てられた仮想パスの前記最大許容レート以下の時、前記検出されたバーストを取り入れ、
前記識別された割り当てられた仮想パスで進行中の全バーストに対して確保された前記ピークセルレートの合計＋前記検出されたバーストのピークセルレートが前記識別された割り当てられた仮想パスの前記最大許容レートより大きいとき、前記検出されたバーストを拒絶する諸ステップから成ることを特徴とする方法。
【請求項７】
請求項６の方法であって、前記取り入れるステップが更に、
前記識別された割り当てられた仮想パスに、前記検出されたバーストの前記ピークセルレートに等しいバンド幅を確保することを含むことを特徴とする、請求項６に記載の方法。
【請求項８】
請求項６の方法であって、
前記検出されたバーストの終わりを検出したとき、前記確保されたバンド幅を前記識別された割り当てられた仮想パスに開放するステップを更に含むことを特徴とする、請求項６に記載の方法。
【発明の詳細な説明】
【０００１】
［発明の属する技術分野］
本発明は非同期転送モード（ＡＴＭ）ネットワークに関し、更に詳細には、ＡＴＭバックボーンネットワークにおける輻輳回避のための方法及びシステムに関する。
【０００２】
［背景技術］
一般に通信ネットワークは伝送リンク（又は「リンク」）により相互接続される複数のノードを含み、伝送リンクは特定のバンド幅（又は容量）により定められる。ＡＴＭネットワークでは、発信ノードはデータを固定長セルの形態で宛先ノードへ接続（仮想回線と呼ばれる）を通して送信し、接続は発信ノードと宛先ノードの間で確立される。仮想回線は、発信ノードと宛先ノードの間のゼロ又は１以上のノード（即ち、交換機）を通過できる。発信ノードと宛先ノードの間の仮想回線のグループは仮想パスと呼ばれる。セルは音声、コンピュータのデータ、映像、マルチメディア、インターネットのデータ等を含む如何なるタイプのディジタル化された情報も含むことができる。
【０００３】
ＡＴＭバックボーンネットワークでは、発信ノードは１又は複数の外部アクセスネットワークからのトラフィックを受信する。ネットワークの輻輳を制御するために、ネットワークはトラフィックに関連する仮想回線のサービス品質（ＱＯＳ）要求を満たすことを要求されるリソースを決定し、もし決定されたリソースが利用可能ならば、リソースを仮想回線用に確保するために接続受付制御（ＣＡＣ）法を使用する。
【０００４】
発信ノードがトラフィックを外部アクセスネットワークから受信するとき、発信ノードはトラフィックコントラクトをネットワークと取り決め、トラフィックコントラクトはネットワークで仮想回線を確立することを要求されるリソースを決定するために必要な情報を含む。特に、トラフィックコントラクトはトラフィック記述子及びＱＯＳ要求を含む。更に、トラフィック記述子は、発信トラフィック記述子及びセル遅延変動許容差（ＣＤＶＴ）を含む。一般に、発信トラフィック記述子のパラメータはピークセル率（ＰＣＲ）、平均又は持続可能なセル率（ＳＣＲ）、及び最大バーストサイズ（ＭＢＳ）である。
【０００５】
一般に、既存のＡＴＭネットワークは、ネットワークがトラフィックに関連する仮想回線のＱＯＳ要求を満たすために確保しなければならないバンド幅の量を決定するために、（等価バンド幅法として知られる）色々な固有の方法を使用する。いったんネットワークが必要なバンド幅を決定したら、次にネットワークは、ネットワークの仮想パスが仮想回線を収容するのに十分なバンド幅を有するかどうかを決定する。もしネットワークがそのような仮想パスを識別したら、ネットワークは仮想パスを支持するリンク上に決定されたバンド幅を確保する。もしネットワークがそのような仮想パスを識別できなければ、ネットワークはトラフィックを拒絶する。
【０００６】
一般に、ＡＴＭネットワークは、トラフィックストリームに関連する仮想回線の全持続時間のために必要なバンド幅を確保する。仮想回線の持続時間はトラフィックストリームの個々のバーストの持続時間の合計よりも実質的に長いので、仮想回線は確保されたバンド幅をバースト間の沈黙時間の間には使用せず、従って、バースト的なトラフィックに対するバンド幅の不十分な使用を招く。
【０００７】
バースト的なトラフィックに対するバンド幅の不十分な使用への既知の解決法は、仮想回線の持続時間の代わりに個々のバーストの持続時間に対してだけ必要なバンド幅を確保することである。特に、「ITU-T Rec. 1.371, "Traffic Control And Congestion Control In B-ISDN", Perth, U. K. November 6-14,1995」は、ＡＢＴ法として既知のバーストレベル確保法を開示している。この方法では、各バーストのセルブロックは（ＲＭセルと呼ばれる）特別な管理セルに囲まれ、管理セルは各バーストの始まりと終わりをそれぞれ識別する。ＲＭセルは、ネットワーク内部でバーストを移送するために必要なバンド幅を識別する。
【０００８】
２つのタイプのＡＢＴ法、即ち、遅延伝送を用いるＡＢＴ（ＡＢＴ／ＤＴ）及び即時伝送を用いるＡＢＴ（ＡＢＴ／ＩＴ）が存在する。ＡＢＴ／ＤＴ法を使用するネットワークでは、発信ノードがバーストを外部アクセスネットワークから受信するとき、発信ノードはＲＭセルをＡＴＭネットワークへ送信し、バーストをネットワーク内部へ入れる許可を要求する。次に発信ノードは、ネットワークからの承認通知又は拒絶通知を待つ。ネットワークは、要求がバーストに関連する仮想回線のＱＯＳを満たすために利用可能である必要なバンド幅を有するかどうかを決定し、もしそうならば、ネットワークはその仮想回線のために必要なバンド幅を確保し、承認通知を発信ノードへ送信する。承認通知を受信するとき、発信ノードはバーストをネットワークの内部へ入れる。しかし、もしネットワークが要求は利用可能である必要なバンド幅を有さないと決定したら、ネットワークは拒絶通知を発信ノードへ送信する。
【０００９】
ＡＢＴ／ＩＴ法を使用するネットワークでは、発信ノードがバーストを外部アクセスネットワークから受信するとき、ネットワークでバーストを転送するために必要なバンド幅を確保することなく、発信ノードは直ちにバーストをネットワークの内部に入れる。その結果、バーストをネットワークの内部へ入れた後、もし入れられたバーストの仮想回線に関連するどのリンクもバーストを移送するために利用可能である必要なバンド幅を有さなければ、ネットワークはバーストを廃棄する。
【００１０】
ＡＢＴ／ＤＴ法の短所の１つは、広域ネットワークでは、ネットワークのノード間の長い伝送遅延のために、各バーストに対して必要なバンド幅を決定し確保するプロセスが、個々のバーストの持続時間及びバーストが到着する間の時間と比較して極端に長いことである。他方、ＡＢＴ／ＩＴ法は、ネットワークがバーストを移送するために必要なバンド幅を有さないとき、バーストをネットワーク内部に入れることにより既に輻輳したネットワークの輻輳を悪化させる。
【００１１】
従って、ＡＴＭネットワークのバースト的なトラフィックのための既存の輻輳制御回避法の上記及び他の短所を処理するための方法及びシステムを有することが望ましい。
【００１２】
［課題を解決するための手段］
本発明による方法及びシステムは、予め定められた時間間隔の間に１組のバーストアクセスパラメータをＡＴＭネットワークの１組の発信ノードと宛先ノードのペアの間の１組の予め割り当てられた仮想パスに予め割り当てること、及びバーストレベルで、トラフィックを、各発信ノードにおいて、予め割り当てられたバーストアクセスパラメータの組に基いて、ＡＴＭネットワークの他のノードと通信することなく制御することによりＡＴＭネットワークの輻輳を制御する。特に、ネットワークはそれぞれ、予め定められた時間間隔の間に、ネットワークの各発信−宛先ノードのペアの間の１組の仮想パスを予め割り当て、１組の最大許容レートを予め割り当てられた仮想パスの組へ割り当て、１組のバーストアクセスしきい値を１組のサービスクラスへそれぞれ前もって割り当て、予め割り当てられた仮想パスでは、前もって割り当てられたバーストアクセスしきい値は対応する予め割り当てられた最大許容レート以下である。
【００１３】
次に、ネットワークの各発信ノードは、バーストレベルで、発信ノードに向けられたトラフィックを、予め割り当てられた最大許容レートの組及び前もって割り当てられたバーストアクセスしきい値の組に基いて、ネットワークの他のノードと通信することなく制御する。特に、各発信ノードは、発信ノードに向けられたトラフィックのバーストの始まりを検出する。発信−宛先ノードのペアの間に予め割り当てられた仮想パスの組の中から、発信ノードは、検出されたバーストに関連する予め割り当てられた仮想パスを識別する。次に発信ノードは、検出されたバーストのサービスクラス、及び識別されたサービスクラスに対応するバーストアクセスしきい値を識別する。識別された予め割り当てられた仮想パスで進行中の全バーストに対して確保されたピークセルレートの合計＋検出されたバーストのピークセルレートが識別されたバーストアクセスしきい値より小さいとき、発信ノードは検出されたバーストを識別された予め割り当てられた仮想パスに入れる。さもなければ、発信ノードはネットワークから検出されたバーストを拒絶する。
【００１４】
本発明による方法及びシステムは、ネットワークのバースト拒絶の重み付けされたレートの合計が最小になるように、ネットワーク容量、サービス要求のバースト拒絶品質、及びフロー制約条件維持を条件として、１組のバーストアクセスパラメータを設計するための便宜を提供する。特に、ネットワークは、ネットワークの予め割り当てられた各仮想パスに対する１組の最大許容レートを計算する。計算された最大許容レートに基づいて、ネットワークは、予め割り当てられた各仮想パスの各サービスクラスに関連する推定提供負荷を計算する。更に、計算された最大許容レートの組及び計算された推定提供負荷の組に基づいて、ネットワークは１組のバーストアクセスしきい値を計算する。
【００１５】
［発明の実施の形態］
以下の本発明の実施例の記載は関連する図面を参照する。異なる図面の同じ参照番号は、同じ又は類似の構成要素を指す。
【００１６】
予め定められた時間間隔の間に１組のバーストアクセスパラメータをＡＴＭネットワークの１組の発信ノードと宛先ノードのペアの間の１組の予め割り当てられた仮想パスに予め割り当てバーストレベルで、トラフィックを、各発信ノードにおいて、予め割り当てられたバーストアクセスパラメータの組に基いて、ＡＴＭネットワークの他のノードと通信することなく制御する。特に、予め定められた時間間隔の間に、ネットワークはそれぞれ、ネットワークの各発信−宛先ノードのペアの間の１組の仮想パスを予め割り当て、１組の最大許容レートを予め割り当てられた仮想パスの組へ割り当て、１組のバーストアクセスしきい値を１組のサービスクラスへそれぞれ前もって割り当て、予め割り当てられた仮想パスでは、前もって割り当てられたバーストアクセスしきい値は対応する予め割り当てられた最大許容レート以下である。ネットワーク制御装置は、予め割り当てられた仮想パス、最大許容レート、及びバーストアクセスしきい値を、例えば１時間毎の間隔でトラフィック要求の変化に適応するように調節できる。
【００１７】
次に、各発信ノードのバースト制御装置は、トラフィックをバーストレベルで、予め割り当てられた最大許容レートの組及び前もって割り当てられたバーストアクセスしきい値の組に基づいて、ネットワークの他のノードと通信することなく制御する。特に、各バースト制御装置は、発信ノードに向けられたトラフィックのバーストの始まりを検出し、検出されたバーストに関連する予め割り当てられた仮想パスを識別し、検出されたバーストのサービスクラス及び識別されたサービスクラスに対応するバーストアクセスしきい値を識別する。もし、識別された予め割り当てられた仮想パスで進行中の全バーストに対して確保されたピークセルレートの合計＋検出されたバーストのピークセルレートが識別されたバーストアクセスしきい値より小さければ、バースト制御装置は検出されたバーストを識別された予め割り当てられた仮想パスに入れる。さもなければ、バースト制御装置はネットワークから検出されたバーストを拒絶する。
【００１８】
本発明による方法及びシステムは、ネットワークのバースト拒絶の重み付けされたレートの合計が最小になるように、ネットワーク容量、サービス要求のバースト拒絶品質、及びフロー制約条件維持を条件として、１組のバーストアクセスパラメータを設計する。特に、ネットワークは、ネットワークの予め割り当てられた各仮想パスに対する１組の最大許容レートを計算する。計算された最大許容レートに基づいて、ネットワークは、予め割り当てられた各仮想パスの各サービスクラスに関連する仮想負荷を計算する。更に、計算された最大許容レートの組及び計算された仮想負荷の組に基づいて、ネットワークは１組のバーストアクセスしきい値を計算する。
【００１９】
ここで、発信ノードは、外部ネットワーク（例えば、アクセスネットワーク）からトラフィックを受信するＡＴＭネットワークのノードとして定義され、トラフィックをゼロ又は１以上のノードを通して予め割り当てられた仮想パスを経由し、ＡＴＭネットワークの宛先ノードへルーティングする。ここで、宛先ノードは、ここで定義された１又は複数の発信ノードからトラフィックを受信するＡＴＭネットワークのノードとして定義され、トラフィックを外部ネットワーク（例えば、アクセスネットワーク）又はエンドユーザへルーティングする。一般的かつ概括的に、ここでバーストはトラフィックストリームの連続するセルのストリームとして定義され、各セルはトラフィックストリームの沈黙時間よりも統計的に著しく短い時間間隔により分離される。一般に、バースト的なトラフィックストリームは、連続するセルの１又は複数のストリームを含む。
【００２０】
図１は、本発明の実施例によるＡＴＭバックボーンネットワーク１６０のブロック線図である。ネットワーク１６０は、バックボーンノード１００ａ、１００ｃ、ネットワーク制御装置１２０、伝送リンク（又は「リンク」）１１０ａｂ、１１０ａｃ、１１０ａｂ、及びリンク１２５ａ〜１２５ｃから成る。ノード１００ａ〜１００ｃは、例えば、バックボーン交換機又はバックボーンルータを含む。
【００２１】
ノード１００ａは、ノード１００ｂ、１００ｃに伝送リンク１１０ａｂ、１１０ａｃを経由してそれぞれ接続する。ノード１００ｂは、ノード１００ｃに伝送リンク１１０ｂｃを経由して接続する。ノード１００ａ〜１００ｃは、ネットワーク制御装置１２０にリンク１２５ａ〜１２５ｃを経由してそれぞれ接続する。ネットワーク制御装置１２０は、情報をリンク１２５ａ〜１２５ｃを経由してノード１００ａ〜１００ｃにそれぞれ伝達する。
【００２２】
また、ノード１００ａ〜１００ｃは、外部アクセスネットワーク１３０ａ〜１３０ｃに via 伝送リンク１３５ａ〜１３５ｃを経由してそれぞれ接続する。アクセスネットワーク１３０ａ〜１３０ｃは、サービスノード１４０1〜１４０N、１４５1〜１４５N、及び１５０1〜１５０Nにそれぞれ接続する。各サービスノード１４０1〜１４０N、１４５1〜１４５N、及び１５０1〜１５０Nは、例えば、音声、データ、及び／又は映像の形態のトラフィックを生成する装置を含む。
【００２３】
図２は、本発明の実施例によるノード１００ａのネットワーク制御装置１２０及びバーストレベル制御装置２００のブロック線図である。バーストレベル制御装置２００は、ネットワーク制御装置１２０とリンク１２５ａを経由して通信する。同様に、ノード１００ｂ、１００ｃはまたバーストレベル制御装置を含み、バーストレベル制御装置はネットワーク制御装置１２０とリンク１２５ｂ、１２５ｃを経由してそれぞれ通信する。
【００２４】
図２に示されるように、バーストレベル制御装置２００は、トラフィックをアクセスネットワーク１３０ａからリンク１３５ａを経由して受信する。次に、バーストレベル制御装置２００は、（図１に示される）リンク１２５ａを経由してバースト識別データ２２０をネットワーク制御装置１２０へ送信し、リンク１２５ａを経由してバーストアクセスパラメータ２３０をネットワーク制御装置１２０から受信する。バースト識別データ２２０は、例えば、バーストが始まる時間、バーストが終わる時間、ピークセルレート、サービスクラス、及びバーストに関連する仮想パスを含む。
【００２５】
図３は、本発明の実施例によりネットワーク制御装置１２０が実行するステップのフローチャートである。ネットワーク制御装置１２０は提供負荷、及びネットワーク１６０の各発信−宛先ノードのペアに対する各サービスクラスに関連するバーストパラメータを推定する（ステップ３００）。推定提供負荷は、例えば、アクセスネットワーク１３０ａ〜１３０ｃからネットワーク１６０へ向けられたセルの平均数を含む。各サービスクラスに対して、推定バーストパラメータは、バーストの平均持続時間、及び推定提供負荷に対応するバーストのピークセルレートを含む。
【００２６】
また、ネットワーク制御装置１２０はネットワーク１６０の接続形態、及びリンク１１０ａｂ、１１０ａｃ、１１０ｂｃの容量（又はバンド幅）を識別し、１組の仮想パスをネットワーク１６０の各発信−宛先ノードのペアに対して予め割り当てる（ステップ３１０）。予め割り当てられた各仮想パスは、１又は複数のリンクにわたる。例えば、ネットワーク１６０は、発信ノード１００ａと宛先ノード１００ｃの間に、リンク１１０ａｂ、１１０ｂｃから成る仮想パスを確立する。同様に、ネットワーク１６０は、発信ノード１００ａと宛先ノード１００ｃの間に、リンク１１０ａｃから成る他の仮想パスを確立する。
【００２７】
ネットワーク制御装置１２０は、各発信−宛先ノードのペアに対する推定提供負荷に関連するＱＯＳ要求を識別する（ステップ３２０）。ネットワーク制御装置１２０は、発信−宛先ノードのペアの間に予め割り当てられた各仮想パスに対する識別されたＱＯＳ要求を満たす１組のバーストアクセスパラメータを計算する（ステップ３３０）。ネットワーク制御装置１２０は、計算されたバーストアクセスパラメータを発信−宛先ノードのペアの間で予め割り当てられた各仮想パスに割り当てる（ステップ３４０）。次に、ネットワーク制御装置１２０は、割り当てられたバーストアクセスパラメータをネットワーク１６０の各発信ノードに分配する（ステップ３５０）。
【００２８】
図４は、ネットワーク１６０のバースト拒絶の重み付けされたレートの合計が本発明の実施例によって最小になるように、ネットワーク容量、サービスバースト拒絶要求の品質、及びフロー制約条件維持を条件として１組の バーストアクセスパラメータを計算するためにネットワーク制御装置１２０が実行するステップのフローチャートである。ネットワーク制御装置１２０は、各発信−宛先ノードのペアに対する最大許容レート（ＭＰＲ）の合計を計算する（ステップ４００）。次に、ネットワーク制御装置１２０は、（例えば、セル／秒の単位で）各発信−宛先ノードのペアの間の最大許容レートを計算する（ステップ４１０）。ステップ４１０で計算された最大許容レートに基づいて、次にネットワーク制御装置１２０は、予め割り当てられた各仮想パスの各サービスクラスに関連する推定提供負荷を計算する（ステップ４２０）。ステップ４１０で計算された最大許容レート及びステップ４２０で計算された推定トラフィック負荷に基づいて、次にネットワーク制御装置１２０は、（例えば、セル／秒の単位で）予め割り当てられた各仮想パスの各サービスクラスに対するバーストアクセスしきい値を計算する（ステップ４３０）。
【００２９】
また、ネットワーク制御装置１２０は、ステップ４００〜４３０で計算されたバーストアクセスパラメータが更に改良する必要があるかどうかを決定する（ステップ４４０）。もし、計算されたバーストアクセスパラメータが更に改良する必要があれば（ステップ４６０）、ネットワーク制御装置１２０はバーストアクセスパラメータの新しい組をステップ４００〜４３０を繰り返すことにより計算する。もし計算されたバーストアクセスパラメータが更に改良する必要がなければ（ステップ４５０）、ネットワーク制御装置１２０はバーストアクセスパラメータの新しい組を計算しない（ステップ４７０）。
【００３０】
図５は、本発明の実施例による発信ノード１００ａでトラフィックを制御するためにバーストレベル制御装置２００が実行するステップのフローチャートである。バーストレベル制御装置２００は、新しく到着したバーストの始まりを検出する（ステップ５００）。例えば、無接続トラフィックに対して、バースト制御装置２００は、トラフィックストリームにおけるトークンの存在からバーストの始まりを検出する。トラフィックを生成するサービスノード（例えば、顧客の構内設置の機器（ＣＰＥ）、又はＡＴＭ適応レイヤ（ＡＡＬ））が、トークンをバースト的なトラフィックに挿入する。図１の実施例では、サービスノード１４０1〜１４０Nがトークンを各サービスノードにより生成されたトラフィックに挿入する。或いは、アクセスネットワーク１３０ａのＡＴＭ適応レイヤがトークンを挿入する。トークンはバーストの宛先、バーストのピークセルレート、及びバーストのＱＯＳパラメータを含まなければならない。
【００３１】
接続向きのトラフィックに対して、バーストレベル制御装置２００は、バーストの始まりを仮想回線上の新しいセルの到着から検出する。或いは、バーストレベル制御装置２００は、セルの始まりをトークンの存在から検出する。しかし、接続向きのトラフィックに対して、トークンはバーストの宛先、バーストのピークセルレート、及びバーストのＱＯＳパラメータを含む必要はない。
【００３２】
バーストレベル制御装置２００は、検出されたバーストに関連する予め割り当てられた仮想パス（ステップ５１０）、サービスクラス（ステップ５２０）、及びピークセルレート（ステップ５３０）を識別する。次に、バーストレベル制御装置２００は、識別された予め割り当てられた仮想パスで進行中の全バーストに対して確保されたピークセルレートの合計＋検出されたバーストのピークセルレートが識別されたサービスクラスのバーストアクセスしきい値以下かどうかを決定する（ステップ５４０）。もしバーストレベル制御装置２００が、識別された予め割り当てられた仮想パスで進行中の全バーストに対して確保されたピークセルレートの合計＋検出されたバーストのピークセルレートが識別されたサービスクラスのバーストアクセスしきい値以下でないと決定したら（ステップ５５０）、バーストレベル制御装置２００はネットワーク１６０からのバーストを拒絶する（ステップ５６０）。
【００３３】
もしバーストレベル制御装置２００が、識別された予め割り当てられた仮想パスで進行中の全バーストに対して確保されたピークセルレートの合計＋検出されたバーストのピークセルレートが識別されたサービスクラスのバーストアクセスしきい値以下であると決定したら（ステップ５７０）、バーストレベル制御装置２００は、検出されたバーストを識別された予め割り当てられた仮想パスに入れる（ステップ５８０）。次に、バーストレベル制御装置２００は、識別された予め割り当てられた仮想パスに、検出されたバーストのピークセルレートに等しいバンド幅を確保する（ステップ５９０）。
【００３４】
バーストレベル制御装置２００が検出されたバーストの終わりを検出したとき、バーストレベル制御装置２００は、検出されたバーストのピークセルレートを識別された予め割り当てられた仮想パスで進行中の全バーストに対して確保されたピークセルレートの合計を引く。接続向きの トラフィック及び無接続トラフィックに対して、バースト制御装置２００は、バーストの終わりをトラフィックストリームのトークンの存在から検出する。或いは、接続向きのトラフィックに対して、バースト制御装置２００は、バーストの終わりをトラフィックストリームの沈黙時間が予め定められたしきい値を越えたときに検出する。ネットワークオペレータは、このしきい値をバーストレベル制御装置２００でバーストピークセルレートの逆以上に設定できる。
【００３５】
トラフィックモデル
本発明の実施例により、ネットワーク１６０に向けられたトラフィックは沈黙時間間隔により分離されたバーストを含むことができ、バーストはネットワーク制御装置１２０でポアソン分布によりモデル化される。特に、各バーストのセルは、統計的に沈黙時間間隔より非常に短い時間間隔により分離される。従って、セル中間到着レートはバースト中間到着レートよりも非常に小さく、セル中間到着時間が平均バースト中間到着時間を越える可能性は小さい。従って、最小セル中間到着時間は、バーストピークセルレートの逆により制限される。
【００３６】
バースト（又はバースト長）のセルの数は確率変数Ｌとして表され、Ｌは無限分散（即ち、尾部が重い特性）を有する。Poreto分布は無限分散を有する確率分布の例の１つであり、次のように表される。
【数１】
0004263361.tif 000002
ここで、１＞ａ＞０であり、ｂは正規化された定数であり、
【数２】
である。
0004263361.tif 000003
パラメータａは平均バースト長の単調に増加する関数として表され、平均バースト長は次のように表される。
【数３】
0004263361.tif 000004
更に、サービスの複数クラスを含むトラフィックの場合、パラメータａ、ｂ、及びＬはサービスクラスｋの関数として次のように表される。
ａ＝ａ（ｋ），ｂ＝ｂ（ｋ），及びＬ＝Ｌ（ｋ）  ここで、ｋ＝１，２，．．．，Ｋ
【００３７】
バースト拒絶確率
ネットワーク制御装置１２０は、次のパラメータに基づいてネットワーク１６０のバースト拒絶確率を計算する。
Ａ（ｖ，ｋ）  −  発信−宛先ノードのペアｖ（例えば、発信ノード１００ａと宛先ノード１００ｃ）の発信ノードにおけるサービスクラスｋの推定されたバースト到着レート。
ｕ（ｖ）  −  発信−宛先ノードのペアｖに提供されたバーストレベルに基づいて推定された合計負荷。
ｕ（ｖ，ｋ）  −  サービスクラスｋが、発信−宛先ノードのペアｖに対してバーストレベルに基づいて提供された負荷を推定した。
ｕ（ｖ，ｋ，ｓ）  −  サービスクラスｋが、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓに対して提供されたバーストレベルに基づいて負荷を推定した。
ｐ（ｖ，ｋ，ｓ）  −  発信−宛先ノードのペアｖの発信ノードに到着し、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓ上でルーティングされるクラスｋバーストの割合であり、ｐ（ｖ，ｋ，ｓ）≧０に対してΣｐ（ｖ，ｋ，ｓ）＝１である。
Ｂ（ｖ，ｋ，ｓ） - 発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓからバーストするサービスクラスｋの拒絶の確率。
ｄ（ｋ）  −  発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓからバーストするサービスクラスｋの拒絶レートを制限するＱＯＳ要求。
Ｍ（ｖ，ｓ）  −  発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓに対する最大許容レート。
ｑ（ｖ，ｋ，ｓ）  −  サービスクラスｋに関連するバーストアクセスしきい値であり、０≦ｑ（ｖ，ｋ，ｓ）≦Ｍ（ｖ，ｓ）である。
Ｒ（ｖ，ｓ）  −  発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓで進行中の全バーストに対して確保されたピークセルレートの合計。
Ｒ（ｖ，ｋ，ｓ）  −  サービスクラスｋが、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓに提供されたセルレベルに基づいて負荷を推定した。
Ｆ（Ｒ，ｖ，ｓ）  −  Ｒ（ｖ，ｓ）がＲに等しい確率であり、０≦Ｒ≦Ｍ（ｖ，ｓ）である。
Ｔ（ｋ）  −  推定された平均バースト持続時間。
ｒ（ｋ）  −  サービスクラスｋに関連するバーストのピークセルレート。
【００３８】
ネットワーク制御装置１２０は、発信−宛先ノードのペアｖに提供された負荷ｕ（ｖ，ｋ）を、発信−宛先ノードのペアｖの発信ノードにおけるサービスクラスｋのバースト到着レート（Ａ（ｖ，ｋ））及び平均バースト持続時間（Ｔ（ｋ））の観点から次のように推定する。
ｕ（ｖ，ｋ）＝Ａ（ｖ，ｋ）Ｔ（ｋ）
【００３９】
同様に、 ネットワーク制御装置１２０は、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓに提供された負荷ｕ（ｖ，ｋ，ｓ）を、発信−宛先ノードのペアｖの発信ノードにおけるサービスクラスｋのバースト到着レート(Ａ（ｖ，ｋ）)、平均バースト持続時間(Ｔ（ｋ）)、及び発信−宛先ノードのペアｖの発信ノードに到着し、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓ上でルーティングされるクラスｋバースト(ｐ（ｖ，ｋ，ｓ）)の割合の観点から次のように推定する。
ｕ（ｖ，ｋ，ｓ）＝Ａ（ｖ，ｋ）ｐ（ｖ，ｋ，ｓ）Ｔ（ｋ）
Ｒ（ｖ，ｋ，ｓ）＝ｕ（ｖ，ｋ，ｓ）ｒ（ｋ）
【００４０】
ネットワーク制御装置１２０は、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓで進行中の全バーストに対して確保されたピークセルレートの合計確率分布を計算する。各ｑ（ｖ，ｋ，ｓ）がＭ（ｖ，ｓ）に対して予め設定される実施例では、ネットワーク制御装置１２０は、Ｆ（Ｒ，ｖ，ｓ）及びＢ（ｖ，ｋ，ｓ）を次の式を使用して計算する。
ＲＦ（Ｒ，ｖ，ｓ）＝Σｕ（ｖ，ｋ，ｓ）ｒ（ｋ）Ｆ（Ｒ−ｒ（ｋ），ｖ，ｓ），全サービスクラスｋ＝１，．．．，Ｋにわたって和が取られる。  （２）
もしｘ＜０なら、Ｆ（ｘ，ｖ，ｓ）＝０
ΣＦ（Ｒ，ｖ，ｓ）＝１，Ｒ＝０からＭ（ｖ，ｓ）まで和が取られる。  （３）
Ｂ（ｖ，ｋ，ｓ）＝ΣＦ（Ｒ，ｖ，ｓ），ＲからＭ（ｖ，ｓ）−ｒ（ｋ）以上Ｍ（ｖ，ｓ）まで和が取られる。  （４）
次に、ネットワーク制御装置１２０は、式（４）に基づいて発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓからのサービスクラスｋバーストの拒絶の確率(Ｂ（ｖ，ｋ，ｓ）)を決定するために、再帰的に式（２）（３）を解く。
【００４１】
各ｑ（ｖ，ｋ，ｓ）がＭ（ｖ，ｓ）に対して予め設定されない実施例では、ネットワーク制御装置１２０はＦ（Ｒ，ｖ，ｓ）及びＢ（ｖ，ｋ，ｓ）を、例えば、「A. Gersht, K. J. Lee, "Virtual-Circuit Load Control In Fast Packet-Switch Broadband Networks", Proceedings of GLOBECOM '88, December 1988」に開示された方法を使用して計算する。
【００４２】
バーストアクセスパラメータ設計
本発明の実施例により、ネットワーク制御装置１２０は、図４（ステップ４００〜４７０）に記載されたバーストアクセスパラメータを以下のように計算する。ネットワーク制御装置１２０が、ネットワーク１６０の各発信−宛先ノードのペアｖの間に予め割り当てられた各仮想パスｓ各サービスクラスｋのＱＯＳバースト拒絶要求（ｄ（ｋ））を満たすようにバーストアクセスパラメータを計算し、ネットワーク１６０のバースト拒絶の重み付けされたレートの合計が、リンク容量 (又は バンド幅)及びＱＯＳバースト拒絶要求の特定の組に対して最小にされる。
【００４３】
ネットワーク制御装置１２０は、バーストアクセスパラメータを次のパラメータに基づいて計算する。
Ｍl  −  ネットワーク制御装置１２０によりリンクｌ（例えば、リンク１１０ａｂ）に割り当てられた最大許容レートの合計であって、Ｍl＝ΣＭ（ｖ，ｓ）であり、リンクｌに予め割り当てられた全想パスにわたって和を取られる。
Ｃl  −  リンクｌの容量（又はバンド幅）の合計。
ｗ（ｋ）  −  例えば、サービスクラスｋの優先権に基づいてサービスクラスｋに割り当てられた重み。
Ｑ（ｖ，ｓ）  −  発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓ上のバースト拒絶の重み付けされたレート。
Ｑ  −  ネットワーク１６０のバースト拒絶の重み付けされたレートの合計であって、Ｑ＝ΣＱ（ｖ，ｓ）であり、ネットワーク１６０の発信−宛先ノードのペアｖの間に予め割り当てられた全仮想パスｓにわたって和が取られる。
【００４４】
バーストアクセスパラメータを計算するために、ネットワーク制御装置１２０は、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓ上でバースト拒絶Ｑ（ｖ，ｓ）の重み付けされたレートを使用する。バースト拒絶Ｑ（ｖ，ｓ）の重み付けされたレートは、次のように定義される。
【数４】
0004263361.tif 000005
次に、ネットワーク制御装置１２０は、バースト拒絶の重み付けされたレートの合計ＱをパラメータＭ（ｖ，ｓ）、ｐ（ｖ，ｋ，ｓ）、及びｑ（ｖ，ｋ，ｓ）にわたって最小にする。特に、特定のＡ（ｖ，ｋ）、Ｔ（ｋ）、ｗ（ｋ）、ネットワーク接続形態、リンク容量、及び１組の 予め割り当てられた仮想パスに対して、ネットワーク制御装置１２０は、ＱをＭ（ｖ，ｓ）、ｐ（ｖ，ｋ，ｓ）、及びｑ（ｖ，ｋ，ｓ）にわたり、次の制約を条件として最小にする。
ＱＯＳバースト拒絶制約：  Ｂ（ｖ，ｋ，ｓ）≦ｄ（ｋ）
リンク容量制約：  Ｍ≦Ｃl
フロー制約条件維持：  Σｐ（ｖ，ｋ，ｓ）＝1,  ｐ（ｖ，ｋ，ｓ）≧０
バーストアクセスしきい値制約：  ０≦ｑ（ｖ，ｋ，ｓ）≦Ｍ（ｖ，ｓ）
【００４５】
ＱＯＳバースト拒絶制約の緩和
ネットワーク制御装置１２０は、ＱＯＳバースト拒絶制約を緩和するために損失関数法を使用する。特に、ネットワーク制御装置１２０は、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓのサービスクラスｋに対するＱＯＳバースト拒絶制約に従わない次のような損失関数Ｇ（ｖ，ｋ，ｓ）を使用する。
もしＢ（ｖ，ｋ，ｓ）≧ｄ（ｋ）ならば、Ｇ（ｖ，ｋ，ｓ）＝g［｛Ｂ（ｖ，ｋ，ｓ）／ｄ（ｋ）｝−１］
さもなければ、Ｇ（ｖ，ｋ，ｓ）＝０  （６）
ここでｇは、ＱＯＳバースト拒絶制約Ｂ（ｖ，ｋ，ｓ）≦ｄ（ｋ）を破ることに対する損失の強さを決定する正の乗算である。同様に、ネットワーク制御装置１２０は、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓの全サービスクラスに対するＱＯＳバースト拒絶制約に従わない次のような損失関数Ｇ（ｖ，ｓ）を使用する。
Ｇ（ｖ，ｓ）＝ΣＧ（ｖ，ｋ，ｓ）、ｋ＝１からｋ＝Ｋまでの和を取られる。
【００４６】
次に、ネットワーク制御装置１２０は、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓのバースト拒絶の重み付けされたレートの合計を次のように表す。
Ｑ*（ｖ，ｓ）＝Ｑ（ｖ，ｓ）＋Ｇ（ｖ，ｓ）  （７）
Ｇ＝ΣＧ（ｖ，ｓ）、ここでネットワーク１６０の発信−宛先ノードの全ペアｖの間に予め割り当てられた全仮想パスｓにわたって和が取られる。
Ｑ*＝Ｑ＋Ｇ
次に、ネットワーク制御装置１２０は、Ｑ*を以下の制約に従って最小にする。
リンク容量制約：  Ｍl≦Ｃl
フロー制約条件維持：  Σｐ（ｖ，ｋ，ｓ）＝1,  ｐ（ｖ，ｋ，ｓ）≧０
バーストアクセスしきい値制約：  ０≦ｑ（ｖ，ｋ，ｓ）≦Ｍ（ｖ，ｓ）
【００４７】
加えて、ネットワーク制御装置１２０は、バースト拒絶の重み付けされたレートの合計Ｑ*を最小にするタスクを３つの関連するサブタスクに分解する。サブタスクは以下のようである。
サブタスク（１）：  各発信−宛先のペアｖの間に予め割り当てられた各仮想パスｓに対する最大許容レートＭ（ｖ，ｓ）を計算する。
サブタスク（２）：  発信−宛先ノードのペアｖの発信ノードに到着し、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓ上でルーティングされるクラスｋバーストの割合ｐ（ｖ，ｋ，ｓ）を計算する。
サブタスク（３）：  発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓの各サービスクラスｋに対するバーストアクセスしきい値ｑ（ｖ，ｋ，ｓ）を計算する。
【００４８】
ネットワーク制御装置１２０は、サブタスク（１）〜（３）を順次実行する。各サブタスクに対して、ネットワーク制御装置１２０は（以下で定義される）目的関数を変数Ｍt（ｖ，ｓ）、ｐt（ｖ，ｋ，ｓ）、及びｑt（ｖ，ｋ，ｓ）の各組にわたってそれぞれ最適化し、他の２組の変数を固定したままにする。ここで、ｔは特定の反復を表す。例えば、サブタスク（１）の反復ｔを完了した後、ネットワーク制御装置１２０は、計算されたＭt（ｖ，ｓ）をｐt（ｖ，ｋ，ｓ）を計算するために使用する。同様に、サブタスク（２）の反復ｔを完了した後、ネットワーク制御装置１２０は、計算されたＭt（ｖ，ｓ）及びｐt（ｖ，ｋ，ｓ）をｑt（ｖ，ｋ，ｓ）を計算するために使用する。もし必要なら、ネットワーク制御装置は、サブタスク（１）〜（３）を各計算されたＭt（ｖ，ｓ）、ｐt（ｖ，ｋ，ｓ）、及びｑt（ｖ，ｋ，ｓ）を改良するために使用できる。
【００４９】
サブタスク（ｌ）：  最大許容レートの計算
ネットワーク制御装置１２０は、Ｍt（ｖ）の推定、ネットワーク１６０の各発信−宛先ノードのペアｖの間に予め割り当てられた全仮想パスｓに対する最大許容レートの合計を計算し、ＱＯＳバースト拒絶制約Ｂt（ｖ，ｋ，ｓ）≦ｄ（ｋ）、及びリンク容量制約Ｍlt≦Ｃlが満たされるように、最大許容レートＭt（ｖ，ｓ）を各発信−宛先ノードのペアｖの間に予め割り当てられた各仮想パスｓに割り当てる。特に、ネットワーク制御装置１２０は、反復手順をＭt（ｖ）の推定を計算するために使用し、各Ｍt（ｖ，ｓ）を予め割り当てられた各仮想パスｓに割り当てる。各反復ｔにおいて、ネットワーク制御装置１２０が反復ｔ−１において計算するｐt-1（ｖ，ｋ，ｓ）及びｑt-1（ｖ，ｋ，ｓ）に基づき、ネットワーク制御装置１２０は各発信−宛先ノードのペアｖに対して推定されたＭt（ｖ）を計算し、Ｍt（ｖ，ｓ）をネットワーク１６０の予め割り当てられた各仮想パスｓに割り当てる。
【００５０】
ネットワーク制御装置１２０は、Ｍt（ｖ）の初期推定として以下のＭt（ｖ）に対する下限を使用する。
【数５】
0004263361.tif 000006
初期反復ｔ＝０において、ネットワーク制御装置１２０はＭ（ｖ）を次のように初期化する。
Ｍ0（ｖ）＝ΣＲ（ｖ，ｋ，ｓ）（１−ｄ（ｋ））、ここで全サービスクラスｋ＝１，．．．，Ｋ、及び発信−宛先ノードのペアｖの間に予め割り当てられた全仮想パスｓにわたって和を取られ、並びに
Ｍ0（ｖ）＝ΣＡ（ｖ，ｋ）Ｔ（ｋ）ｒ（ｋ）（１−ｄ（ｋ））、ここで全サービスクラスｋ＝１，．．．，Ｋに対して和が取られる。
【００５１】
次に、ネットワーク制御装置１２０は、Ｍt（ｖ，ｓ）を各発信−宛先ノードのペアｖの間に予め割り当てられた各仮想パスに対して以下のように計算する。ネットワーク制御装置１２０は、最大限のリンク仮想残存容量（Ｃl−Ｍl）がΣＭt（ｖ，ｓ）＝Ｍt（ｖ）に従って最小化されるように、Ｍt（ｖ，ｓ）を予め割り当てられた各仮想パスｓに対して計算する。ここで、ネットワーク１６０の予め割り当てられた全仮想パスｓにわたって和が取られ、０≦Ｍt（ｖ，ｓ）である。ネットワーク制御装置１２０は、各Ｍt（ｖ，ｓ）を、フロー偏差法（例えば、「A. Gersht, A. Shulman, "Optimal Routing In Circuit-Switched Communication Networks," IEEE Transactions On Communications, Volume 37, No. 11, November 1989」で開示されるフロー偏差法）を使用することにより計算する。
【００５２】
各反復ｔにおける初期反復の後、ネットワーク制御装置１２０は、Ｍt（ｖ）をネットワーク制御装置１２０が反復ｔ−１において計算するＭt-1（ｖ）に基づいて以下のように改良する。
Ｍt（ｖ）＝Ｍt-1（ｖ）＋ｂt-l（ｖ）
ここで、ｂt（ｖ）はネットワーク制御装置１２０がＭt（ｖ）をインクリメントするステップサイズであり、ｂ0（ｖ）は０に等しい。ｔ≧１に対して、ネットワーク制御装置１２０はｂt（ｖ）を反復ｔ−１で計算される｛Ｂ（ｖ，ｋ，ｓ）／ｄ（ｋ）｝−１の最大値に比例するように選択し、最大値は全サービスクラスｋ＝１，．．．，Ｋ及び発信−宛先ノードのペアｖの間に予め割り当てられた全仮想パスｓにわたって取られる。これらの反復は、ＱＯＳバースト拒絶制約が各発信−宛先ノードのペアｖの間に予め割り当てられた各仮想パスｓの全クラスに対して満たされるまで続く。次に、ネットワーク制御装置１２０は、リンク容量制約Ｍl≦Ｃlが満たされる限りＱを減少させるようにｂt（ｖ）を修正する。
【００５３】
サブタスク（２）：  負荷割り当ての計算
ネットワーク制御装置１２０は、ｐt（ｖ，ｋ，ｓ）、発信−宛先ノードのペアｖの発信ノードに到着し発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓへルーティングされるクラスｋバーストの割合を次のように計算する。予め割り当てられた仮想パスの組、反復ｔにおいて計算されるＡ（ｖ，ｋ）、Ｔ（ｋ）、ｒ（ｋ）、ｗ（ｋ）、Ｍt（ｖ，ｓ）、及び反復ｔ−１において計算されるしきい値ｑt-1（ｖ，ｋ，ｓ）に基づいて、ネットワーク制御装置１２０は、各ｐ（ｖ，ｋ，ｓ）をＱ*が最小になるようにΣｐt（ｖ，ｋ，ｓ）＝１，ｐt（ｖ，ｋ，ｓ）≧０に従って計算する。初期反復ｔ＝０において、ネットワーク制御装置１２０は、ｑ0（ｖ，ｋ，ｓ）がＭ0（ｖ，ｓ）に等しいと仮定してＭt（ｖ，ｓ）及びｑt-1（ｖ，ｋ，ｓ）の与えられた組に対してＱ*を最適化するｐt（ｖ，ｋ，ｓ）の値を計算する。
【００５４】
次に、ネットワーク制御装置１２０は、Ｌ（ｖ，ｋ，ｓ）（サービスクラスｋに対して発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓの長さ）を計算する。ネットワーク制御装置１２０は、Ｌ（ｖ，ｋ，ｓ）をｐ（ｖ，ｋ，ｓ）に対してＱ*の偏導関数を取ることにより計算する。
【００５５】
バーストアクセスしきい値制約０≦ｑ（ｖ，ｋ，ｓ）≦Ｍ（ｖ，ｓ）を満たす如何なる与えられたＭ（ｖ，ｓ）及びｑ（ｖ，ｋ，ｓ）に対しても、ネットワーク制御装置１２０は、１組のｐ（ｖ，ｋ，ｓ）を各発信−宛先ノードのペアｖに対して独立に計算する。各計算されたｐ（ｖ，ｋ，ｓ）は、対応する予め割り当てられた仮想パスｓが最小のＬ（ｖ，ｋ，ｓ）を有するときだけ正の値を有する。計算されたｐ（ｖ，ｋ，ｓ）から、ネットワーク制御装置１２０は一意にＱ*（ｖ，ｓ）（従って、Ｑ*）を決定する。もしネットワーク制御装置１２０がＧ（ｖ，ｓ）＝０と決定したら、ＱＯＳバースト拒絶制約は満たされる。換言すれば、Ｑ*（ｖ，ｓ）はＱ（ｖ，ｓ）に等しく、ネットワーク制御装置１２０は、Ｍ（ｖ，ｓ）及びｑ（ｖ，ｋ，ｓ）の与えられた組に対して、ｐ（ｖ，ｋ，ｓ）の値を、バースト拒絶の重み付けされたレートの合計ＱがＱＯＳバースト拒絶制約に従って最小化されるように計算した。
【００５６】
予め割り当てられた仮想パスｓの各組に対して、ネットワーク制御装置１２０は長さＬ（ｖ，ｋ，ｓ）を、ｐ（ｖ，ｋ，ｓ）に対してＱ*（ｖ，ｓ）の偏導関数を取ることにより計算する。ネットワーク制御装置１２０は、反復フロー偏差法を、リンク容量制約に従って、提供負荷を最小の長さを有する予め割り当てられた仮想パスｓにシフトするために使用する。
【００５７】
式（４）（５）（６）及び（７）から、ネットワーク制御装置１２０は、予め割り当てられた各仮想パスｓの長さＬ（ｖ，ｋ，ｓ）を次のように計算できる。
Ｌ（ｖ，ｋ，ｓ）＝｛∂Ｑ*（ｖ，ｓ）｝／｛∂ｐ（ｖ，ｋ，ｓ）｝
＝Ａ（ｖ，ｋ）Ｂ（ｖ，ｋ，ｓ）ｗ（ｋ）＋｛∂Ｂ（ｖ，ｋ，ｓ）／∂ｐ（ｖ，ｋ，ｓ）｝［Ａ（ｖ，ｋ，）ｐ（ｖ，ｋ，ｓ）ｗ（ｋ）＋２ｇＹ（ｖ，ｋ，ｓ）］  （８）
ここで、Ｙ（ｖ，ｋ，ｓ）＝｛Ｂ（ｖ，ｋ，ｓ）／ｓ（ｋ）｝−１
さもなければ０であり、
【数６】
0004263361.tif 000007
【００５８】
全サービスクラスｋ及び予め割り当てられた仮想パスｓに対して各ｑ（ｖ，ｋ，ｓ）がＭ（ｖ，ｓ）に予め設定される実施例では、ネットワーク制御装置１２０は、導関数Ｚ（Ｒ，ｖ，ｋ，ｓ）＝｛∂Ｆ（Ｒ，ｖ，ｓ）／∂ｐ（ｖ，ｋ，ｓ）｝をＦ（Ｒ，ｖ，ｓ）と共同して次のように計算する。Ｒ＞０に対して、ネットワーク制御装置１２０は、Ｚ（Ｒ，ｖ，ｋ，ｓ）を式（２）及び（３）に基づいて式（２）の両側から偏導関数をを取り式（１）を使用することにより計算する。
【数７】
0004263361.tif 000008
次に、ネットワーク制御装置１２０は、Ｚ（０，ｖ，ｋ，ｓ）を計算するためにＦ（０，ｖ，ｓ）の偏導関数を次のように取る。
Ｚ（０，ｖ，ｋ，ｓ）＝−Ａ（ｖ，ｋ）Ｔ（ｋ）（１−Ｂ（ｖ，ｋ，ｓ））Ｆ（０，ｖ，ｓ）  （１０）
【００５９】
全サービスクラスｋ及び予め割り当てられた仮想パスｓに対して各ｑ（ｖ，ｋ，ｓ）がＭ（ｖ，ｓ）に予め設定されない実施例では、ネットワーク制御装置１２０は、Ｆ（Ｒ，ｖ，ｓ）（従って、Ｚ（Ｒ，ｖ，ｋ，ｓ））を、例えば、「A. Gersht, K. J. Lee, "Virtual-Circuit Load Control In Fast Packet-Switch Broadband Networks," Proceedings of GLOBECOM '88, December 1988」で開示された方法を使用して計算する。
【００６０】
ネットワーク制御装置１２０は、次のステップを実行することにより、式（２）及び（３）を共同して、各サービスクラスに対して独立に式（９）及び（１０）を再帰的に解く（ネットワーク制御装置１２０は、Ｌ（ｖ，ｋ，ｓ，ｉ）及びｐ（ｖ，ｋ，ｓ，ｉ）をｉ番目に反復中のＬ（ｖ，ｋ，ｓ）及びｐ（ｖ，ｋ，ｓ）の値にそれぞれ予め設定するために使用する）。
ステップ０：  ネットワーク制御装置１２０はｐ（ｖ，ｋ，ｓ，ｉ）を（ｌ／ｎ（ｖ））に等しく設定する。ここで、ｎ（ｖ）は、発信−宛先ノードのペアｖの間に予め割り当てられた仮想パスｓの数であり、ｉ＝０である。
ステップ１：  ネットワーク制御装置１２０は、Ｌ（ｖ，ｋ，ｓ，ｉ）を（８）〜（１０）から再帰的な式（２）〜（４）を使用してｐ（ｖ，ｋ，ｓ，ｉ）に対して計算する。
ステップ２：  ネットワーク制御装置１２０は、Ｌ（ｖ，ｋ，ｓ，ｉ）を式ｐ（ｖ，ｋ，ｓ，ｉ＋１）＝（１−γ（ｉ））ｐ（ｖ，ｋ，ｓ，ｉ）＋γ（ｉ）δ（ｖ，ｋ，ｓ，ｉ）を使用して計算する。ここで、γ（ｉ）はステップサイズを表し、もしＬ（ｖ，ｋ，ｓ，ｉ）がＬ（ｖ，ｋ，ｍ，ｉ）の最小値に等しければ、δ（ｖ，ｋ，ｓ，ｉ）は１に等しく、ｍは予め割り当てられた仮想パスｓを表すインデックスであり、予め割り当てられた全仮想パスｍにわたって最小値が取られ、さもなければδ（ｖ，ｋ，ｓ，ｉ）は０に等しい。
ステップ３：  ネットワーク制御装置１２０は、ステップ１及び２を、予め割り当てられた仮想パスの長さの最大値と予め割り当てられた仮想パスの長さの最小値の差がεより小さくなるまで繰り返す。ここで、εは予め定められた パラメータである。
【００６１】
サブタスク（３）：  バーストアクセスしきい値の計算
Ｍt（ｖ，ｓ）、ｐt（ｖ，ｋ，ｓ）、及びｕt（ｖ，ｋ，ｓ）の与えられた組に対して、ネットワーク制御装置１２０は、１組のバーストアクセスしきい値ｑt（ｖ，ｋ，ｓ）をバーストアクセスしきい値制約０＜ｑt（ｖ，ｋ，ｓ）≦Ｍt（ｖ，ｓ）に従ってバースト拒絶の重み付けされたレートの合計Ｑ*が全ｑt（ｖ，ｋ，ｓ）にわたって最小化されるように計算する。各反復ｔにおいて、Ｍt（ｖ，ｓ）及びｐt（ｖ，ｋ，ｓ）の計算された値に基づき、ネットワーク制御装置１２０は、Ｑ*（ｖ，ｓ）を最小化するｑt（ｖ，ｋ，ｓ）の値を独立にかつ、例えば、予め割り当てられた全仮想パスｓと並行して計算する。
【００６２】
ネットワーク制御装置は、ｑt（ｖ，ｋ，ｓ）の値を計算するために例えば、「A. Gersht, K. J. Lee,"Virtual-Circuit Load Control In Fast Packet-Switch Broadband Networks", Proceedings of GLOBECOM '88, December 1988」で開示された最適化法を使用する。
【００６３】
本発明の好ましい実施例及び方法として現在考えられるものが図示され記載されてきたが、種々の変更及び修正をなすことができ、本発明の範囲から逸脱することなく等価物を本発明の実施例の構成要素と置換できることは、当業者により理解されるであろう。
【００６４】
加えて、多くの修正が、特定の構成要素、技術、又は本発明の教示に対する実施を本発明の中心的範囲から逸脱することなく適合させるためになされる。従って、本発明は本明細書で開示される特定の実施例及び方法に限定されず、添付された請求項の範囲内にある全実施例を含む。
【図面の簡単な説明】
【図１】  本発明の実施例によるＡＴＭバックボーンネットワークのブロック線図である。
【図２】  本発明の実施例によるＡＴＭバックボーンネットワークにおけるネットワーク制御装置及びバーストレベル制御装置のブロック線図である。
【図３】  本発明の実施例によりネットワーク制御装置が実行するステップのフローチャートである。
【図４】  本発明の実施例によりバーストアクセスパラメータを計算するためにネットワーク制御装置が実行するステップのフローチャートである。
【図５】  本発明の実施例によりバースト的なトラフィックを制御するためにバーストレベル制御装置が実行するステップのフローチャートである。
【符号の説明】
１００ａ〜１００ｃ  ノード
１１０ａｂ、１１０ａｃ、１１０ｂｃ  リンク
１２０  ネットワーク制御装置
１２５ａ〜１２５ｃ  リンク
１３０ａ〜１３０ｃ  外部アクセスネットワーク
１３５ａ〜１３５ｃ  伝送リンク
１４０1〜１４０N、１４５1〜１４５N、１５０1〜１５０N  サービスノード
１６０  ネットワーク
２００  バースト制御装置
２２０  バースト識別データ
２３０  バーストアクセスパラメータ
【図１】
0004263361.tif 000009
【図２】
0004263361.tif 000010
【図３】
0004263361.tif 000011
【図４】
0004263361.tif 000012
【図５】
0004263361.tif 000013