(57)【特許請求の範囲】
【請求項１】
複数のホストおよび1以上の相互接続ノードを含むパケットネットワークにおいて資源を予約する方法であって：
複数の受信ホストを動作して、1以上の予約に影響を与えるパラメータを含む逆方向にルート設定されたパケットを、ルートに沿って1以上の前記相互接続ノードを経由して1以上の送信ホストへ送る段階と；
前記１以上の相互接続ノードが、
異なる受信者から受取った逆にルート設定されたパケットの1以上の予約に影響を与えるパラメータを結合して、結合された予約に影響を与えるパラメータを生成して、
前記結合された予約に影響を与えるパラメータを記憶して、
前記結合された予約に影響を与えるパラメータを含む逆方向にルート設定されたパケットをさらに前記ルートに沿って1以上の送信ホストへ送るように動作する段階と；
前記送信ホストを動作して、資源予約パケットを前記ルートに沿って1以上の受信者へ送り返す段階と；
前記１以上の相互接続ノードを動作して、前記予約パケットに応答して、該ノードに記憶された予約に影響を与えるパラメータにしたがって資源を予約する段階とを含む方法。
【請求項２】
前記1以上の予約に影響を与えるパラメータが所望のサービス品質クラスの指標を含み；
前記1以上の相互接続ノードが：
前記予約に影響を与えるパラメータを更新して、下流の受信者によって要求される最高のサービス品質クラスを表わし；
前記最高のサービス品質クラスと関係する資源予約プロセスにしたがって資源を予約するように動作する請求項1記載の方法。
【請求項３】
前記1以上の予約に影響を与えるパラメータが経路の特徴を表わすパラメータを含む請求項1記載の方法。
【請求項４】
前記経路の特徴を表わすパラメータが1以上の遅延パラメータを含む請求項３記載の方法。
【請求項５】
前記ホストが共有のツリールート設定アルゴリズムにしたがって通信する請求項１ないし４の何れか1項記載の方法。
【請求項６】
パケットネットワークノードであって：
前記パケットネットワークノードを経由して複数の受信ホストから１以上の送信ホストへ送信される1以上の予約に影響を与えるパラメータを含む逆方向にルート設定されたパケットを受信する手段と、
受信された逆方向にルート設定されたパケットの１以上の予約に影響を与えるパラメータを結合して、結合された予約に影響を与えるパラメータを生成する手段と；
前記結合された予約に影響を与えるパラメータを記憶する手段と；
さらにルートに沿って前記結合された予約に影響を与えるパラメータを含む逆にルート設定されたパケットを前記１以上の送信ホストへ送る手段と；
予約パケットに応答するノードに記憶された結合された予約に影響を与えるパラメータにしたがって資源を予約する手段とを含むパケットネットワークノード。
【請求項７】
複数のホストおよび1以上の相互接続ノードを含むパケットネットワークにおいて資源を予約する方法であって：
1以上の経路パラメータを含む経路の特徴を表わすデータパケットを、ルートに沿って1以上の前記相互接続ノードを経由して1以上の送信ホストへ送るように複数の受信ホストを動作する段階と；
前記1以上の相互接続ノードを、
受取った経路の特徴を表わすデータパケットの1以上の経路パラメータをプロセスして、更新された経路の特徴を表わす経路パラメータを生成し、
前記更新された経路パラメータを記憶し、
前記更新された経路パラメータを含む経路の特徴を表わすデータパケットを前記ルートに沿って前記送信ホストへさらに送るように動作する段階と；
資源予約パケットを1以上の受信者へ前記ルートに沿って戻す段階と；
前記予約パケットに応答して、そのノードに記憶された経路の特徴を表わすデータにしたがって資源を予約するように、前記送信ホストを動作する段階とを含む方法。
【発明の詳細な説明】
【０００１】
発明の属する技術分野
本発明はパケットネットワークにおいて資源を受取る方法に関する。本発明はとくに、サービス品質保証を提供するインターネットを用意することに関係して利用される。
【０００２】
従来の技術
インターネットにおいて資源を予約する方法はよく知られている。現在インターネットにおいて最もよく支援（サポート）されている方法は、資源予約プロトコル（ＲＳＶＰ）(Resource Reservation Protocol)によって規定されている。
【０００３】
例えば電話による会話またはテレビ会議がインターネット上で実行されるとして要求されることは、インターネットが実時間通信を提供できることが望まれている。これに関係して、提供できる２つのサービス品質は、次のドキュメント（本明細書において参考文献として取り上げられる）によって特定されている：
（１）S.Schenker, C.Partridge, R.Guerin. Specification of Guaranteed Quality of Service, Request For Comments, September 1997, RFC 2212;
（２）J.Wroclawski. Specification of the Controlled-Load Network Element Service, Request For Comments, September 1997, RFC 2211。
【０００４】
本質的に、第１のドキュメントにおいて規定される保証サービスでは、ユーザのメッセージが受取り者に到達するのにかかる時間における上界を特定でき、制御されるロードサービス（２）は、サービスが軽くロードされる(lightly loaded)ときのみ、インターネットによって与えられるのと品質上類似したサービスを提供する。ＲＳＶＰプロトコルにしたがってインターネットを動作すると、実時間通信を行なうことができる。ＲＳＶＰプロトコルにしたがってインターネットを動作するときの上述のサービス品質クラスへの通信の準備は次の文献に記載されている（同様に本明細書において参考文献として取り上げる）：
（３）P.White. RSVP and Integrated Services in the Internet:a tutorial, IEEE Communications magazine, May 1997。
【０００５】
ＲＳＶＰプロトコルにしたがって動作するインターネットワークにおいて、送信者がトラヒックレベルを高めたいとき、1以上の受信者へ最初に経路情報パケットを送り、移動した経路の特徴に関する情報および増加したトラヒックレベルを特定する情報を与える。この経路情報パケットが各ノードを通って進み、これにより送信者からの増加したトラヒックが1以上の受信者へ送られることになる。経路特徴データは、パケットがノードを通った結果としてノードにインストールされる。このプロセスが完了すると、1以上の受信者は増加したトラヒックの規格および二端点間の経路の特徴（受取った経路情報パケットから得られる）に基づいて要求された予約を計算し、要求された予約を特定するパケットを送信者へ送り返す。十分なネットワーク資源が使用可能なとき、予約要求パケットを受取る各ノードは適切な資源を予約し、パケットを送信者へ送り返す。
【０００６】
インターネットがＲＳＶＰにしたがって動作するとき、受信者は資源の予約を要求する責務を負う。対照的に、インターネットストリームプロトコルバージョン２（ＳＴ２）にしたがって動作するインターネットでは、送信者が資源の予約を要求する責務を負う。
【０００７】
ＳＴ２にしたがって動作するネットワークは、ＲＳＶＰで可能であったよりも迅速に資源を予約することができるが、一対多または多対一の通信において異なるサービスレベルを提供することはできない。
【０００８】
発明が解決しようとする課題
本発明の態様にしたがって、複数のホストおよび1以上の相互接続ノードを含むパケットネットワークにおいて資源を予約する方法であって：
複数の受信ホストを動作して、1以上の予約に影響を与えるパラメータを含む逆方向にルート設定されたパケットを、ルートに沿って1以上の前記相互接続ノードを経由して1以上の送信ホストへ送る段階と；
前記１以上の中間ノードが、
異なる受信者から受取った逆にルート設定されたパケットの1以上のパラメータを結合して、結合された予約に影響を与えるパラメータを生成して、
前記結合されたパラメータを記憶して、
前記結合されたパラメータを含む逆方向にルート設定されたパケットをさらに前記ルートに沿って1以上の送信ホストへ送るように動作する段階と；
前記送信ホストを動作して、資源予約パケットを前記ルートに沿って1以上の受信者へ送り返す段階と；
前記１以上の中間ノードを動作して、前記予約パケットに応答して、該ノードに記憶された予約に影響を与えるパラメータにしたがって資源を予約する段階とを含む方法を提供する。
【０００９】
中間ノードは受信者によって送られた予約に影響を与えるデータを検査し、それにしたがって資源を予約するので、本発明では資源の予約を受信者の要件に一層よく合わせることができる。さらに本発明では、送信者が始めた資源予約プロトコルと関係するより迅速な資源予約を犠牲にせずにこれを達成する。
【００１０】
さらに、このやり方で経路の特徴（特性データ）を結合することによって、ネットワーク内のノード間で送られる経路の特徴を表わすデータ量は、送信者が多くの受信者にトラヒックを送るとき（すなわち送信者がマルチキャスティングするとき）に低減する。
【００１１】
いくつかの実施形態では、前記１以上の予約に影響を与えるパラメータは所望のサービス品質クラスの指標を含み、前記１または複数の中間ノードは：
前記パラメータを更新して、下流の受信者によって要求される最高のサービス品質クラスを表示し；
前記最高のサービス品質クラスと関係する資源予約プロセスにしたがって資源を予約するように動作する。
【００１２】
このやり方では、１対多または多対多の通信において異なるサービス品質クラスを支援することができる。例えば、一部の受信者は上述の保証されたサービスにしたがってサービス品質を要求でき、一方で他の受信者は上述の制御されたロード規格のみにしたがってサービス品質を要求することができる。したがってより融通の利くサービスを提供することができる。
【００１３】
ある種の実施形態では、予約パケットは１以上の送信者によって出力されるトラヒックの性質を示す情報を保持し、ノードは予約される資源を計算するときにその情報を検討する。アプリケーションにおいて、送信者からのトラヒックが所定の特徴をもつとき、これは本質的ではなくなる。
【００１４】
好ましい実施形態では、ホスト間のルート設定は共有のツリープロトコルにしたがう。したがって複数の送信者がいる状況では、ノードに記憶される必要がある予約に影響を与えるデータ量を低減する。
【００１５】
これはとくに多数の送信者を含む通信に対して効果的である。多数の人を含むテレビまたはオーディオ会議では、多数の送信者が存在していてもよい。マルチプレーヤゲームまたは分散形対話シミュレーションでは、はるかにより多数の送信者が可能である。これらは潜在的には、メッセージを送受信する何千ものホストを含む。
【００１６】
本発明の第２の態様にしたがって、パケットネットワークであって：
受信された逆方向にルート設定されたパケットの１以上のパラメータを結合して、結合された予約に影響を与えるパラメータを生成する手段と；
前記結合されたパラメータを記憶する手段と；
さらに前記ルートに沿って前記結合されたパラメータを含む逆にルート設定されたパケットを前記送信ホストへ送る手段と；
予約パケットに応答するノードに記憶された結合された予約に影響を与えるパラメータにしたがって資源を予約する手段とを含むパケットネットワークノードを提供する。
【００１７】
ここで、本発明の特定の実施形態を例示的に添付の図面を参照して記載することにする。
【００１８】
発明の実施の形態
図１には7つの構成要素（Ｈ１ないしＨ７）が示されており、各構成要素はローカルエリアネットワーク（Ｌ１ないしＬ６）に接続され、さらにローカルエリアネットワークはゲートウエイルータ（Ｒ１ないしＲ６）を含む。コンピュータＨ５、Ｈ６の２つは単一のローカルエリアネットワーク（ＬＡＮ）に接続され、他の５つのコンピュータは各ＬＡＮに接続されている。ゲートウエイルータ（Ｒ１ないしＲ７）はネットワークによって相互接続されており、該ネットワークは、中間のルータ（ＡないしＥ）によって1以上の他のサブネットによって接続された多数のサブネット（Ｓ１ないしＳ６）を含む。
【００１９】
第１のサブネットＳ１は3つのゲートウエイルータ（Ｒ１ないしＲ３）を第１の中間のルータＡへ接続して、代わって第１の中間のルータは第２のサブネットＳ２を介して第２の中間のルータＢへ接続されている。第３のサブネットＳ３は第２の中間のルータを第３および第４の中間のルータＣ、Ｄへ接続する。第３の中間のルータＣは第４のサブネットＳ４を介して第４のゲートウエイルータＲ４へ接続される。第５のサブネットＳ５は第４の中間のルータＤを両方の第５の中間ルータＥおよび第５のゲートウエイルータＲ５へ接続する。第５の中間のルータＥは第６のサブネットＳ６を介して第６のゲートウエイルータＲ６へ接続される。
【００２０】
コンピュータ（Ｈ１ないしＨ７）、ルータ（Ｒ１ないしＲ７、ＡないしＥ）、およびサブネット（Ｓ１ないしＳ６）は、インターネットの一部を形成している。インターネットは、ＬＡＮ（Ｌ１ないしＬ６）へ接続された多数の他のコンピュータ（図示されていない）を含み、さらに他のサブネット、ルータ、およびＬＡＮを含むこともある。インターネットはコンピュータ（Ｈ１ないしＨ７）がメッセージを互いに送ることができるように動作する。インターネットは、例えば一般的にインターネットとして知られているネットワークであってもよい。
【００２１】
インターネットはＴＣＰ／ＩＰネットワークアーキテクチャにしたがって動作する。さらに図１に示された少なくともコンピュータおよびルータはマルチキャスティングを支援する。
【００２２】
７つのコンピュータ（Ｈ１ないしＨ７）のそれぞれは、そのユーザがマルチプレーヤゲームに参加できるようにするプログラムによって制御される。ユーザがゲームに影響を与えるように動作するとき、このアクションを表わすメッセージは他のコンピュータのそれぞれへ送られる。当業者によって認識されるように、このようなメッセージはマルチキャスティングプロトコルにしたがって、マルチキャストグループを形成する７つのコンピュータを使用してルート設定される。以下の記述では、資源ベースのツリーマルチキャストルート設定プロトコルが使用されるが、その代わりにコアベースのツリー（ＣＢＴ）プロトコルのような共有ツリープロトコルを使用することができる。当業者は、共有ツリーマルチキャスティングプロトコルにしたがって動作するのに本発明を採用することにほとんど問題がない。
【００２３】
インターネットという用語にしたがって、後述ではコンピュータはホストと呼ばれ、用語‘ノード’はホストおよびルータの両方を指すことを意図している。コンピュータ上を走行しているプログラムはアプリケーションと呼ばれる。インターネットにアクセスするのに必要な1以上のアプリケーションは所定のホストによって実行できるので、各アプリケーションに‘ポート番号’を割り当てて、ポート番号で分類された到来メッセージを対応するアプリケーションに送ることができる。
【００２４】
当業者には分かっているように、ＴＣＰ／ＩＰプロトコルスーツ(suite)はノードではなく、インターフェイスを参照するアドレスを使用する。したがってホストＨ１はインターフェイスＩ１のＩＰアドレスによって識別され、ルータＲ１は、該ルータＲ１をＬＡＮ Ｌ１に接続するインターフェイス用の１つのＩＰアドレスと、該ルータＲ１を第１のサブネットＳ１に接続するインターフェイスＩ3用の別のアドレスとをもつ。
【００２５】
メッセージは、送信ホストからマルチキャストグループ内の他のホストへ下流を移動するといわれている。したがって、例えば第１のホストＨ１から他のホストへのメッセージの資源の予約については、第１のルータＲ１と第１のＬＡＮ Ｌ１との間のインターフェイスＩ１は上流のインターフェイスであることが知られており、第１のルータＲ１と第１のサブネットＳ１との間のインターフェイスＩ２は下流インターフェイスであることが知られている。
【００２６】
おおざっぱに言うと、本発明の第１の実施形態によると、７つのホスト（Ｈ１ないしＨ７）にサービスしているインターネットの一部は、ＴＣＰ／ＩＰネットワークアーキテクチャにしたがって動作するが、加えて各ホストは他のホストと通信するのに次の手続きにしたがってインターネットの資源を予約することができる。ホストの予約に適した資源をもつことによって、他のホストへの通信経路の特徴を制御することができる。例えば、通信遅延が最小にされるか、または所定の範囲よりも低くすることができる。
【００２７】
この実施形態においては、各ホストは時折予約パケット（以下ではＲＥＳパケット）を他の全てのホストへ送る。このパケットの目的の一部は各ノードに、資源ベースのツリーにおいて直ぐ上流のノードの下流インターフェイスのアドレスを与えることであり、メッセージはこの資源ベースのツリーにしたがって他の各ホストへ向かう。このアドレスは先行するホップアドレスとして知られている。当業者は、類似の機能がＲＳＶＰプロトコルのＰＡＴＨ（経路）メッセージによって実行されることを認識する。
【００２８】
受信ホストが少なくとも1つのＲＥＳパケットを受取ると、後方向制御（Backward Control）パケット（以下では、ＢＷＤＣパケットと記載される）を送信ホストへ送信を開始する。通常、受信ホストは所定のリフレッシュ期間において（（以下で開示される）一定の環境を通って）１つのこのようなパケットを送る。
【００２９】
各ノードは、それが受取るＢＷＤＣパケットを読み取り、メモリ内のパケットに含まれる経路の特徴を表わす最悪を記憶する。記憶された値を使用して、インターフェイス経路の特徴ごとの最悪を表わすデータを更新する（このような記憶されたデータは当業者に対する‘状態’エントリーとして知られている）。インターフェイス状態エントリごとの類似の最悪は、ノードの他の各下流インターフェイスに対して生成される。次に状態エントリは比較され、ノード経路の特徴ごとの最悪は状態エントリから得られ、上流へ送られるＢＷＤＣパケット内に含まれる。
【００３０】
上流へ送られるＢＷＤＣパケットの内容は、ノードから送られた先のＢＷＤＣパケットの内容とは異なる。さもなければＢＷＤＣパケットはリフレッシュ期間が終わったときに送られる。
【００３１】
この手続きの結果、資源ベースのツリー内の各ノードはインターフェイス状態エントリごとの最悪、すなわち該ノードから受信ホストの１以上へ導かれるツリー上の経路から全ての経路の特徴を表わす最悪を記憶することになる。
【００３２】
次に受取られるＲＥＳパケットに基づいて、各ノードはインターフェイス状態エントリごとの対応する最悪を使用して、ツリーの各下流リンク上で要求される予約を計算する。
【００３３】
ノードにおけるインストールされた予約または状態エントリは、ＲＳＶＰにおいて使用されるようないわゆる‘ソフト状態’を使用して実行される。したがって状態エントリは当業者に知られている適切なリフレッシュがないときに削除されることになる。
【００３４】
ここで予約プロセスを図２ないし５に関係してより詳しく記載する。
【００３５】
送信ホストから送られるＲＥＳパケットは、図２に開示された情報を含む。パケットは同様のやり方でＩＰデータグラム内に、例えばＲＳＶＰ制御メッセージへエンカプシュレート（カプセル化）され、ＩＰヘッダ内の他のヘッダフィールド（図示されていない）によってこの予約プロトコルに関係するデータグラムとして識別される。当業者は図２に示されていないＩＰヘッダ内の対のフィールドをよく知っていると考えられる。
【００３６】
ＲＥＳパケット内の他のフィールドは次の情報を含む。
・session（セッション）―これはＲＳＶＰプロトコルによって識別されるセッションと同一である―これはＲＥＳパケットが関係するフロー（すなわち、1以上のメッセージ）用の送信先アドレス（マルチキャストグループに対するマルチキャストアドレス）、およびフローに関係する他のパラメータを含む。当業者はこれらのパラメータの性質が分かる。
・Sender Template（送信者テンプレート）―これはＲＳＶＰプロトコルによって規定される対応するフィールドと同一である―すなわち、これは送信ホストを識別するフィルタ規格である。これは送信ホストのＩＰアドレス、加えて選択的に使用される送信ホストポートを含む。
・Traffic specification(Tspec)（トラヒック規格）―これは後続のトークンバケット表示を使用して送信ホストのトラヒック特徴を記述しているＲＳＶＰプロトコルによって規定される対応するフィールドと同一である。
【００３７】
ｐ＝フローのピークレート（バイト／秒）
ｂ＝バケットの深さ（バイト）
ｒ＝トークンバケットレート（バイト／秒）
ｍ＝最小の規制されたユニット（バイト）
Ｍ＝最大のデータグラムの大きさ（バイト）
・previous hop (Phop)（先のホップ）―これはＲＳＶＰプロトコルによって規定された対応するフィールドと同一であり、すなわちこれは先行のホップアドレスを含むオブジェクトである。
・timestamp（タイムスタンプ）フィールド―これは分散形ツリーを下って次のノードへ到達する直前にローカルノードクロックの時刻でスタンプされる。
・end-to-end delay（二端点間遅延）フィールド―これは、パケットが送信ホストによって送られるときから次のノードの上流インターフェイスに到達するときまでの現在の遅延を与える。
・CRTフィールド（２ビット）―これは送信ホストアプリケーションのシーリング予約タイプを識別する。１１は保証されるサービスを示し、１０は制御されるロードを示し、００は最善を尽くすことを示す。０１は現在は特定されていないが、最善を尽くすタイプと制御されるロードタイプとの間における新しいサービス品質に対して使用することができる。
・QoSvoid bit―これは１に設定されるときに、サービス品質保証を提供できないことを示す。
【００３８】
送信ホストが保証されるサービスを要求するとき、データグラムはさらに次の情報を含む保証されたサービスオブジェクトを含む。値CSumおよびDSumは上述の保証されたサービス規格において規定される。
・CSum―最後の上流がポイントを再生してからのＣ値の累積。
・DSum―最後の上流がポイントを再生してからのＤ値の累積。
・desired delay bound(所望の遅延範囲)フィールド―送信ホストアプリケーションによって要求される二端点間の遅延範囲を示す。
・accumlated delay bound（累積された遅延範囲）フィールド―送信ホストと次のノードの上流インターフェイスとの間のインストールされた遅延範囲を示す。
・delayvoid bit(DV)―設定されると、このビットは所望の遅延範囲を保証できない受信ホストに対する指標となる。
・lossvoid bit(LV)―設定されると、このビットは損失のないサービスを保証できない受信ホストに対する指標となる。
【００３９】
アプリケーションの制御のもとで実行する各ノードおよび受信ホストによって送られるＢＷＤＣを図３に示した。ＲＥＳパケットのように、ＢＷＤＣパケットはＩＰデータグラム内にエンカプシュレートされる。各場合において送信先のＩＰアドレスは先行のホップアドレスである。当業者は、この態様においてＢＷＤＣパケットはＲＳＶＰプロトコルのＲＥＳＶパケットと同じである。
【００４０】
ＢＷＤＣパケット内に含まれる他の情報は次のものを含む：
・session（セッション）―これは対応するＲＥＳパケットに対して上述で規定されるセッションフィールドと同一である。
・downstream hop（下流ホップ）オブジェクト―これはＲＳＶＰの次のホップオブジェクトと同一である。―すなわちこれは、その送られるパケットの直ぐ下流のノードの上流インターフェイスのアドレスを与える。
・timestamp（タイムスタンプ）フィールド―ノードの直ぐ上流へ送られる直前にローカルノードクロックの時刻でスタンプされる。
・timedeltaprevフィールド―これは、ノードの直ぐ上流へ送られる直前にtimedeltaprevの記憶された値（この値は後で開示する）で満たされる。
・CRTrフィールド（２ビット）―このフィールドは、受信ホストアプリケーションシーリング予約タイプを示す。このフィールドの値とそれらが表わす予約タイプとの間のマッピングは、ＲＥＳメッセージ内のＣＲＴフィールドと同じである。
・Worst Case Delay（最悪ケース遅延）フィールド―これは、ＢＷＤＣパケットを送るノードの上流インターフェイスとそのノードの下流の各受信ホストとの間で測定される最大データパケット伝搬遅延に等しい。
・path MTU（経路ＭＴＵ）フィールド―これは、ＢＷＤＣパケットを送るノードの上流インターフェイスとそのノードの下流の各受信ホストとの間の最小path MTU値に等しい。
・Worst Case Ctot（最悪ケースCtot）フィールド―これは保証されるサービス規格に規定される通りである―すなわちこれは、ＢＷＤＣパケットを送るノードの上流インターフェイスとそのノードの下流の各受信ホストとの間で経路に沿って最大の累積されたCtot値に等しい。
・Worst Case Dtot（最悪ケースDtot）―これは保証されるサービス規格において規定される通りである―すなわちこれはＢＷＤＣパケットを送るノードの上流インターフェイスとそのノードの下流の各受信ホストとの間の経路に沿って最大の累積されたDtot値に等しい。
・path bandwidth（経路バンド幅）―これはＢＷＤＣパケットを送ったノードの上流インターフェイスとそのノードの下流の各受信ホストとの間で経路に沿う最大経路バンド幅に等しい。
・sender address（送信者アドレス）―送信ホストのアドレスの組―アドレスは（ホストＨ１ないしＨ７のグループのマルチキャストアドレスと組み合わせて）、資源ベースのツリーがパケットに関係するノードを示す。
【００４１】
CtotおよびDtotは保証されるサービス規格において規定される通りである。送信ホストが保証サービスを要求したとき、ＢＷＤＣパケットはさらに次のものを含む：
・excess delay field(超過遅延フィールド)―インストールされた二端点間遅延範囲が所望の二端点間遅延を現在超えた量。
・bottleneck flag（ボトルネックフラグ）―後で開示するように、これは１に設定されたとき、ＢＷＤＣメッセージが少なくともボトルネックルータに関する限り移動したことを示す（すなわちＲＥＳメッセージの第１の経路上で累積された範囲が最初に所望の範囲を超えたときのルータ）。
【００４２】
最初に予約を設定するとき、各ホストはＲＥＳパケットを他のホストへ送る。送信ホストから受信ホストへ経路によって構成される資源ベースのツリー上の各ノードは次のタイミング動作を実行する。後で開示するように、各ノードは、ＲＥＳパケットを受取るたびにこれらの動作を実行する。
【００４３】
最初にtimestampフィールドは読み取られ、ノードのローカルクロックと比較され、ＲＥＳパケットが最後のホップを横切るのにかかった時間を判断する。この継続時間はパラメータtimedeltaprevとしてノードに記憶される。このtimestampは次にノードのローカルクロックにしたがって設定され、ＲＥＳパケットは受信ホストへ向けて資源ベースのツリーに沿って次のノードへ送られる。このプロセスは、（下流方向で移動するとき）関係する各ノードがそれらの直ぐ上流ホップにおける伝搬遅延を表わすパラメータ（timedeltaprev）を記憶するまで反復される。
【００４４】
ＲＥＳパケットが資源ベースのツリーのノードを通って伝搬されると、各受信ホストはＢＷＤＣパケットを送信ホストへ送る。ホストによってパケット内に置かれる初期値は、次のように判断される。path MTUおよびpath bandwidthは、送信ホストが取付けられているＬＡＮの特徴に対応する。ホストは下流ノードフィールド内にＩＰアドレスを挿入し、それが要求するサービス品質にしたがってCRTrを設定する。最悪ケース(worst case)の経路の特徴は、ボトルネックフラグのように全てゼロに設定される。excess delayフィールドはこの段階で使用されない。timedeltaprevパラメータはtimedeltaprevフィールドに割り当てられる。
【００４５】
ＢＷＤＣパケットを受取ると、ノードは後述のタイミング動作、およびノード経路の特徴ごとの最悪を判断する動作を実行する。
【００４６】
タイミング動作は、ノードが最初にパケット内のtimedeltaprevフィールドを読取ることを含む。タイミング動作は（下流方向に移動するときに）ノードから下流のホップにおける（ＲＥＳパケットによって経験される）伝搬遅延を記録することが分かる。さらにＢＷＤＣパケットのタイムスタンプフィールドおよびローカルクロックを読み取ることによって、他の方向において同じホップ上の伝搬遅延の値が得られる。下流ホップにおける遅延は何れの方向においても同じであると仮定される。したがってこれらの２つの遅延の平均をとることによって、ノードクロック間の不一致とは無関係に伝搬遅延値が得られる。下流ホップに対するこの平均遅延はパラメータ‘dnext’としてノードによって記憶される。
【００４７】
経路の特徴を監視する動作は次の通りである。
【００４８】
ＢＷＤＣパケットが到達すると、ノードは最初に現在のセッションおよび２つの経路を識別するパラメータによって識別される下流経路、すなわちパケットの下流ノードフィールドに関係する経路状態エントリごとの最悪、並びにＢＷＤＣメッセージが到達した下流インターフェイスのアドレスの存在を検査する。
【００４９】
経路およびセッションに関係する経路状態エントリごとに予め記憶された最悪が見付からないとき、経路状態エントリごとの新しい最悪が生成される。
【００５０】
経路状態エントリごとの最悪のフォーマットは図４に示した通りであり、session identifyingフィールド、sender addressフィールド、およびtwo path identifyingフィールドを含み、さらに加えて次のフィールド：
・Worst Case Ctot（最悪ケースCtot）
・Worst Case Dtot（最悪ケースDtot）
・Worst Case Delay（最悪ケース遅延）
・ path bandwidth（経路バンド幅）
・     CRTr
・path MTU（経路MTU）
・dnext
・bottleneck flag（ボトルネックフラグ）
経路状態エントリごとの新しい最悪は、CRTr、経路バンド幅、pathMTU、Worst Case Delay、Worst Case Ctot、およびWorst Case Dtotの値を割り当てることによって生成され、これらの値はＢＷＤＣパケット内において経路状態エントリごとの最悪の対応するフィールドに含まれている。タイミング動作において計算されるパラメータdnextはdnextフィールドに割り当てられる。bottleneck flagはゼロに初期設定され、次に記載するように使用される。
【００５１】
ノードは同じインターフェイス上に経路状態エントリごとに複数の最悪をもち、同じセッションに関係するとき、ノードはそれらを結合して、インターフェイス状態エントリごとに最悪を生成する。この状況は下流インターフェイスが共有媒体のＬＡＮへ接続するときに生じることがある。
【００５２】
図５に示したように、インターフェイス状態エントリごとの最悪は経路状態エントリごとの最悪と同じフィールドを含むが、経路状態エントリごとの最悪は下流ノードフィールドがない。session、sender adressフィールド、および下流インターフェイスフィールドに割り当てられた値は経路状態エントリごとの最悪のものと同じである。他のフィールドの値は次のように計算される。
・Worst Case Ctot = MAX{Worst Case Ctoti}
・Worst Case Dtot = MAX{Worst Case Dtoti}
・Worst Case Delay = MAX{Worst Case Delayi}
・path bandwidth = MAX{path bandwidthi}
・pathMTU = MIN{pathMTUi}
・CRTr = MAX{CRTi}
・dnext = MAX{dnexti}
なお、下付き文字ｉは１ないし下流インターフェイスを共有するノード数の値をとる。インターフェイス状態エントリごとの最悪で記憶された値Worst Case Ctot、Worst Case Dtot、Worst Case Delayは、下流インターフェイスに対する最悪ケース(worst case)の経路特徴値である。これらの値はインターフェイスとは異なる経路に関係することが可能である。経路状態エントリごとの何れかがそれを１に設定するときは、bottleneck flag(ボトルネックフラグ)は１に設定される。
【００５３】
そのダウンストリームインターフェイスのそれぞれに対してインターフェイス状態エントリごとの最悪を生成するとき、ノードは各状態期間に少なくとも１回ノードデータごとに最悪を含むＢＷＤＣパケットを生成する。ノードデータごとの最悪に含まれるパラメータは次のように計算される。
・Worst Case Ctot = MAX{Worst Case Ctotn + Clocaln}、なおClocalnはＢＷＤＣパケットが到達した下流インターフェイスとノードの（session(セッション)によって判断される）上流インターフェイスとの間のCtotの値である；
・Worst Case Dtot = MAX{Worst Case Dtotn + Dlocaln}、なおDlocalnはＢＷＤＣパケットが到達した下流インターフェイスとノードの（sessin(セッション)によって判断される）上流インターフェイスとの間のCtotの値である；
・ Worst Case Delay = MAX{Worst Case Delayn} + dnextn
・ path bandwidth ＝ MIN(MAX{path bandwidthn}, path bandwidth upstream)
・CRTr = MAX{CRTn}
・pathMTU = MIN(MIN{pathMTUn}, pathMTU upstream)
なお、ｎは１からノードからの下流インターフェイス数への値をとるインデックスであり、‘pathMTU upstream’および‘path bandwidth upstream’はそれぞれ最小のパケットの大きさおよび上流ホップのバンド幅を表わす。
【００５４】
CRTrが１１に設定されないとき、Ctot、Dtot、Worst Case Delayはゼロに設定される。
【００５５】
上述の演算は、現在のセッションに関係する資源ベースのツリー内の各ノードによって繰り返される。所定の送信ホストからのフローは、各ノードがノードから受信ホストへ導かれる全ての経路の最悪のケースの特徴を記憶することが認識されるであろう。
【００５６】
次に送信ホストは別のＲＥＳパケット（図２参照）要求、例えば保証されるサービスを送る。したがってパケット内のＣＲＴフィールドは１１に設定され、所望の遅延範囲は、パケットが送信ホストから全ての受信ホストへ到達するのにかかる時間に代わること受信者が望む制限値に設定される。
【００５７】
トラヒック規格フィールドは送信ホストによって埋められ、二端点間遅延フィールドは送信ホストにおいて記憶されるパラメータdnextの値に設定される。所望の遅延範囲以外の保証されるサービスの各フィールドはゼロに初期化される。
【００５８】
資源ベースのツリーに沿う下流の第１のノードでは、照会遅延は現在のセッションに含まれる１以上の下流ホップのそれぞれに対してフローに与えられることになる。これは次の式にしたがって決定される：
式（１）
Qdelay=所望の範囲(desired-bound)−累積された範囲(accumulated-bound)−最悪ケース遅延(Worst Case Delay)
Worst Case Delay値は、対応するフィールドと、現在のノードにおけるインターフェイス状態エントリごとの最悪のdnextパラメータとの和に等しい。第１のノードにおいて、累積された範囲は通常ゼロかまたは非常に小さい値である。Qdelay値は、受信ホストへの経路の残りにおいて許容できる合計の待ち行列遅延についての推定値を表わす。
【００５９】
ＲＳＶＰプロトコルにしたがって動作する受信者によって実行されるプロセスに類似したプロセスを使用して、各下流ホップ(downstream hop)において予約されるバンド幅を計算して、所望の範囲において‘オンコース（予定進路を進行している）’に留まる。インターフェイスパラメータごとの個々の最悪はこのインターフェイスと異なる経路に関係していることあがるので、この計算によるとしばしば過大推定になってしまうことがある。当業者は、次の式を使用して推定値を計算することを実現することになる：
式２
Qdelayend2end = ［(b-M)(p-R)/｛R(p-r) +（(M + Ctot)/R）｝］+ Dtot
(ケースp > R > = r)
式３
Qdelayend2end =（(M + Ctot)/R）+ Dtot      (ケースR > = p > = r)
パラメータＭ、ｐ、ｂ、およびｒはＲＥＳメッセージの対応するフィールドから得られる（これらの符号の意味はＲＥＳメッセージに対して既に開示した通りである）。CtotおよびDtotの値は、現在の下流インターフェイスに関係するインターフェイス状態エントリごとの最悪からの値と、ＣおよびＤのローカル値との和である。Qdelayの値を得て、式２および３へ挿入するために、式１が使用される。式１を解いて、Ｒに対する値を得て、バンド幅Ｒが現在の下流インターフェイスから導き出されるホップ上で予約される。
【００６０】
保証されるサービス規格に記載される規則にしたがって、CsumおよびDsumの値を他のパラメータと共に使用して、パケット損失を防ぐために予約に割り当てられなければならないバッファリング量を計算する。
【００６１】
予約要求がサービスされると、ＲＥＳパケット内のend-to-end delay（端端間遅延）フィールドはそれを次に示すものに追加することによって増加する：
・次のホップに対する伝搬遅延、dnext；および、
・ＲＥＳパケットが参照するフローのデータパケットにおける（関係する出力するインターフェイスに対する）現在のローカル照会遅延の推定値。
【００６２】
さらに次の更新がＲＥＳパケットに対して行なわれる：
・コピーされたパケットのaccumlated delay bound（累積遅延範囲）フィールドは次に示すものによって増加される：
１）次のホップに対する伝搬遅延、dnext；および、
２）ＲＥＳパケットが参照するフローのメッセージにおける（関係する下流インターフェイスに対する）インストールされたローカル待ち行列遅延範囲。このローカル照会遅延範囲は、Ｒの予約された値を式２および式３へ、それぞれパラメータCtotおよびDtotに対するローカル値ＣおよびＤと共に挿入することによって得られる。
【００６３】
ＲＥＳパケットに対して次の更新を行なう：
・Ｃのローカル値をCSumフィールドに加える；および、
・Ｄのローカル値をDSumフィールドに加え、
これは送信ホストのトラヒックの再形成が下流インターフェイスにおいて実行されないことを条件とし、この場合にCSumおよびDsumがゼロに設定される。
【００６４】
さらに次の何れかのとき、Qosvoidフィールドが１に設定される：
ａ）保証されるサービス予約試行は、トラヒック規格のトークンバケットレートと少なくとも同じ大きさのバンド幅を予約しないとき；または、
ｂ）制御されるロード予約試行が失敗するとき。
【００６５】
ノードが１に設定されるQosvoidの組をもつＲＥＳパケットを受取るとき、MIN{CRTs，CRTr}が１０または１１のときは、このノードは制御されるロード予約を保証する試行を行なう。
【００６６】
フィールドの更新が完了するとき、ＲＥＳパケットをルート設定ツリーにしたがって各次のホップに到達する前に、timestampフィールドは（上述のように）ローカルクロックに等しく設定される。
【００６７】
類似のプロセスが次の各ノードにおいて実行され、インストールされた待ち行列によって累積された範囲が増加することによって式（１）から得られるQdelayの値を生成することになり、これは受信ホストへの経路の残りに対して許容できる合計の待ち行列遅延の推定値を維持する。宣言されるトラヒック規格にしたがうホストからのメッセージがあると仮定し、各ノードが計算されたバンド幅Ｒを予約できるとすると、ノードにおける上述のプロセスは、送信ホストからのメッセージが受信ホストの全てに対する所望の遅延範囲内に伝えることができるようにするのに効果的である。
【００６８】
ノードが上述のように計算されたバンド幅を予約できないとき、（ノードにおいて規制の実行を受け）可能な限り大きなバンド幅が予約される。しかしながら予約されるバンド幅量は、ＲＥＳパケットのトークンバケットレートフィールド(tocken bucket rate field)の値よりも小さいとき、保証されるサービスは提供されず、これはdelayvoid、lossvoid、Qosvoidフラグを１に設定することによって示される。
【００６９】
予約されたバンド幅がＲＥＳパケットのトークンバケットレートフィールドの値よりも大きいとき、累積される範囲は所望の範囲と比較される。
【００７０】
所望の範囲がより大きくなると、予約プロセスは上述のように継続する。予約されたバンド幅Ｒは上述のように過大に推定されることがあるので、これはしばしば、所望の遅延範囲よりも小さい二端点間の経路において遅延を与える予約を設定することになる。
【００７１】
しかしながら所望の範囲がより小さくなるとき、ノードは次のように動作する：
・インターフェイス状態エントリごとの関連性と関係する予約のbottleneck flagを設定して、ボトルネックノードとしてそれ自身を分類する；
・ＲＥＳパケット内のdelayvoidフラグを１に設定し、それをツリーにしたがってノードへ送る。
【００７２】
ノードは、delayvoidフィールドを１に設定したＲＥＳパケットを受取ると、可能な最大バンド幅（送信ホストのピークレートの倍数に制限される可能性が高い）を予約し、それを送る。
【００７３】
（CRTs=CRTr=11において）delayvoidフィールドが１に設定され、delaylossフィールドが０に設定されたＲＥＳパケットを受取るとき、受信ホストはaccumulated delay boundフィールドがdesired delay boundフィールドを超える量を計算する。受信ホストは直ちに、excess delayフィールドが計算された超過遅延に設定され、bottleneckフィールドがゼロに設定されたＢＷＤＣパケットを送る。このようなＢＷＤＣパケットを受取る各ノードは、インターフェイス状態エントリごとのノードの関係する最悪のbottleneck flagが１に設定されない限りパケットを無視する。ボトルネックノードはＢＷＤＣパケットを受取り、bottleneck flagフィールドを1に設定する。ノードは、ローカルバンド幅の予約を増加することによってＢＷＤＣメッセージ内に示されたexcess delayを削除または低減する試行を行なう。この後でexcess delayが依然として存在するとき、excess delayの修正値をもつＢＷＤＣパケットはホップへ、および同時に送信者へ送られ、ＢＷＤＣパケットが送信者に届くかまたはexcess delayが削除されるまで、各ノードにおいて予約増加が試行される。
【００７４】
上述の実施形態では、データは各ノードにおいて結合され、結合されたデータを使用して、適切な資源予約を計算するとき、ノードの上流へ送られる。
【００７５】
別の実施形態では、資源予約は、結合が行なわれるノードにおいて結合されたデータに基づいて計算することができる。
【００７６】
第２の実施形態は第１の実施形態に類似しているが、共有のツリープロトコルを使用する。第２の実施形態において、sender addressフィールド（ＢＷＤＣパケットでは、経路ごとに最悪およびインターフェイス状態エントリごとに最悪）は要求されない。これは、ＲＥＳパケットが送られないインターフェイスが、sessionパラメータおよび到来インターフェイスに基づいてノードによって判断できるからである。共有のツリーを使用するとき、インターフェイス状態エントリごとの最悪が、マルチキャストグループに対する特定の送信者ではなくマルチキャストグループに関係することになるとき、各ノードにおけるインターフェイス状態エントリごとの最悪の数は、ノードから出力インターフェイス数と同じである。
【００７７】
マルチ送信者環境において、第２の実施形態は、既知の予約プロトコルと比較して要求されるインターフェイス状態エントリごとの最悪の量を低減することが分かるであろう。
【００７８】
上述の実施形態において、Ｃターム（例えば、Ctot）、Ｄターム（例えば、Dtot）、およびリンク伝搬遅延の最悪ケースの組み合せは各用語ごとに独立して行なわれた。したがって非常に保守的なローカルバンド幅予約となる。好ましい実施形態では、Ｄ用語とリンク伝搬遅延とを含むレートの独立した遅延パラメータが使用される。これは、単なる各経路からの最大値Ｄではなく、遅延パラメータから独立した最悪ケースのレートの値としてＤの送られた値を取ることによって達成できる。
【００７９】
上述の実施形態では、下流の受信者の1人によって要求される最高のサービス品質をルータが見付けることができることが分かるであろう。同様の検討をータおよび他の予約に影響を与えるパラメータに応用する。ネットワーク内の中間ノードにおけるこのようなパラメータの結合により、パケットネットワークにおけるマルチキャスト通信に対してより融通の利く資源予約を行なうことができる。
【図面の簡単な説明】
【図１】  インターネットを使用して相互に通信するコンピュータグループを示す模式図。
【図２】  本発明の第１の実施形態において使用されたパケットを設定する予約内容を示す模式図。
【図３】  第１の実施形態で使用されたノードパケットごとの上流にルート設定された最悪の経路の特徴内容を示す模式図。
【図４】  第１の実施形態にしたがって動作するノード内に記憶される経路データごとに最悪の経路の特徴を示す模式図。
【図５】  第１の実施形態にしたがって動作するノードに記憶されるインターフェイスデータごとに最悪の経路の特徴を示す模式図。
【図１】
0004399109.tif 000002
【図２】
0004399109.tif 000003
【図３】
0004399109.tif 000004
【図４】
0004399109.tif 000005
【図５】
0004399109.tif 000006