(57)【特許請求の範囲】
【請求項１】
ハイブリッドファイバー−同軸ネットワークにおいてパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記ハイブリッドファイバー−同軸ネットワークが帯域幅割り当てユニット及び複数の端末装置ユニットを有し、前記複数の端末装置ユニットの内の各１つが帯域幅割り当てユニットと共に配置されるヘッドエンドコントローラと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、
(a)  識別された端末装置から伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、
(b) (1)前記伝送許可要求信号の到着の時間、(2) 要求された伝送と対応されるサービスのクラス、及び(3) 識別された端末装置の代わりに行われた先行する伝送許可要求のバーチャルスケジューリングタイムに基づいて、要求された伝送のためのバーチャルスケジューリングタイムを生成するステップと、
(c)  伝送スケジューリングリストに要求された伝送に対応するエントリーを追加するステップと、
(d)  辞典編集分類に従って伝送スケジューリングリストを分類するステップと、
(e)  伝送スケジューリングリストの前記バーチャルスケジューリングタイムの位置に従って、識別された端末装置へ伝送許可信号を送信するステップと、
を備えるパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項２】
(i) 伝送スケジューリングリストの各エントリーがサービスのクラスのインジケータを有し、
(ii) 前記エントリーが第１にサービスのクラスのインジケータによって分類され、第２にバーチャルスケジューリングタイムによって分類される、
請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項３】
伝送許可要求信号が先行する交渉又は準備の結果としてヘッドエンドコントローラによって生成される、請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項４】
前記バーチャルスケジューリングタイムが速度ベースのキューイングプロセスによって生成される、請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項５】
速度ベースのキューイングプロセスが重み付けられた公平なキューイングプロセスである、請求項４に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項６】
前記バーチャルスケジューリングタイムがリザーブトラフィッククラスと対応され、バーチャルクロックアルゴリズムによって生成される、請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項７】
(i) 前記伝送許可要求信号が、固定された大きさのパケットを伝送するのを許可するために識別された端末装置によって生成される一連の伝送許可要求信号の内の１つであり、
(ii) 前記ヘッドエンドコントローラが、識別された端末装置で受信されたが未だ認可されていない要求の総数のカウンタの形で、前記端末装置において各トラフィッククラス毎のキューの表示を維持し、
(iii)  端末装置あたり１つのバーチャルスケジューリングタイムだけが前記伝送スケジューリングリストに保持される、
請求項２に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項８】
共用媒体パケット方式ネットワーク上でパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記パケット方式ネットワークが集中帯域幅割り当てユニット及びネットワークアクセスユニットを有し、前記ネットワークアクセスユニットが前記帯域幅割り当てユニットと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、
(a)  ネットワークアクセスユニットから伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、
(b) (1)前記伝送許可要求信号の到着の時間、(2) 前記要求された伝送と対応されるサービスのクラス、及び(3) ネットワークアクセスユニットによって又はネットワークアクセスユニットの代わりに行われた先行する伝送許可要求のバーチャルスケジューリングタイムに基づいて、要求された伝送のためのバーチャルスケジューリングタイムを生成するステップと、
(c)  伝送スケジューリングリストに前記伝送許可要求信号に対応するエントリーを追加するステップと、
(d)  辞典編集分類に従って前記伝送スケジューリングリストを分類するステップと、
(e)  伝送スケジューリングリストの前記バーチャルスケジューリングタイムの位置に従って、ネットワークアクセスユニットへ伝送許可信号を伝送するステップと、
を備えるパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項９】
(i) 伝送スケジューリングリストの各エントリーがサービスのクラスのインジケータを有し、
(ii) 前記エントリーが第１にサービスのクラスのインジケータによって分類され、第２にバーチャルスケジューリングタイムによって分類される、
請求項８に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１０】
伝送許可要求信号が先行する交渉又は準備の結果として帯域幅割り当てユニットによって生成される、請求項８に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１１】
前記バーチャルスケジューリングタイムが速度ベースのキューイングプロセスによって生成される、請求項８に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１２】
速度ベースのキューイングプロセスが重み付けられた公平なキューイングプロセスである、請求項１１に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１３】
前記バーチャルスケジューリングタイムがリザーブトラフィッククラスと対応され、バーチャルクロックアルゴリズムによって生成される、請求項１２に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１４】
(i) 前記伝送許可要求信号が、固定された大きさのパケットを伝送するのを許可するためにネットワークアクセスユニットによって生成される複数の伝送許可要求信号の内の１つであり、
(ii) 前記帯域幅割り当てユニットが、前記ネットワークアクセスユニットで受信されたが未だ認可されていない要求の総数のカウンタの形で、ネットワークアクセスユニットの各トラフィッククラス毎のキューの表示を維持し、
(iii)  ネットワークアクセスユニットあたり１つのバーチャルスケジューリングタイムだけが前記伝送スケジューリングリストに保持される、
請求項１１に記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１５】
共用媒体パケット方式ネットワークにおいてパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記共用媒体パケット方式ネットワークが集中帯域幅割り当てユニット及び複数のネットワークアクセスユニットを有し、前記複数のネットワークアクセスユニットの各々が前記帯域幅割り当てユニットと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、
(a)  伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、
(b)  伝送スケジューリングリストに前記要求された伝送に対応するエントリーを追加するステップと、
(c)  前記伝送スケジューリングリストのエントリーのラウンドロビンスケジューリングに従って、前記複数のネットワークアクセスユニットの内の１つへ伝送許可信号を伝送するステップと、
を備え、
(i) 前記伝送許可要求信号が、固定された大きさのパケットを伝送するのを許可するために特定のネットワークアクセスユニットによって生成される複数の伝送許可要求信号の内の１つであり、
(ii) 前記帯域幅割り当てユニットが、各ネットワークアクセスユニット毎に受信されたが未だ認可されていない要求の総数のカウンタの形で、前記複数のネットワークアクセスユニットの各トラフィッククラス毎のキューの表示を維持し、  
(iii)  ネットワークアクセスユニットあたり１つのバーチャルスケジューリングタイムだけが前記伝送スケジューリングリストに保持される、
パケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１６】
ケーブルテレビジョンネットワークにおいてパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記ネットワークが帯域幅割り当てユニット及び複数のケーブルモデムを有し、前記複数のケーブルモデムの内の各１つが帯域幅割り当てユニットと共に配置されるヘッドエンドコントローラと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、
(a)  識別されたケーブルモデムから伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、
(b)  重み付けられた公平なキューイングアルゴリズムを用いて、 (1)前記伝送許可要求信号の到着の時間、(2) 要求された伝送と対応されるサービスのクラス、及び(3) 識別されたケーブルモデムの代わりに行われた先行する伝送許可要求のバーチャルスケジューリングタイムに基づいて、要求された伝送のためのバーチャルスケジューリングタイムを生成するステップと、
(c)  伝送スケジューリングリストに要求された伝送に対応するエントリーを追加するステップと、
(d)  辞典編集分類に従って伝送スケジューリングリストを分類するステップと、
(e)  伝送スケジューリングリストの前記バーチャルスケジューリングタイムの位置に従って、識別されたケーブルモデムへ伝送許可信号を送信するステップと、
を備えるパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１７】
ケーブルテレビジョンネットワークにおいてパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記ネットワークが帯域幅割り当てユニット及び複数のセットトップボックスを有し、前記複数のセットトップボックスの内の各１つが帯域幅割り当てユニットと共に配置されるヘッドエンドコントローラと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、
(a)  識別されたセットトップボックスから伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、
(b)  重み付けられた公平なキューイングアルゴリズムを用いて、 (1)前記伝送許可要求信号の到着の時間、(2) 要求された伝送と対応されるサービスのクラス、及び(3) 識別されたセットトップボックスの代わりに行われた先行する伝送許可要求のバーチャルスケジューリングタイムに基づいて、要求された伝送のためのバーチャルスケジューリングタイムを生成するステップと、
(c)  伝送スケジューリングリストに要求された伝送に対応するエントリーを追加するステップと、
(d)  辞典編集分類に従って伝送スケジューリングリストを分類するステップと、
(e)  伝送スケジューリングリストの前記バーチャルスケジューリングタイムの位置に従って、識別されたセットトップボックスへ伝送許可信号を送信するステップと、
を備えるパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１８】
帯域幅割り当てユニットが、(a) プロセッサと、(b) プロセッサによって読み取り可能で、請求項１乃至２０の内の特定の１つに記載される動作を実行するための指示のプログラムを符号化するプログラム記憶デバイスとを含む、請求項１乃至１７の何れかに記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【請求項１９】
プログラム記憶デバイスが、帯域幅割り当てユニットのプロセッサによって読み取り可能で、請求項１乃至１７の内の特定の１つに記載される動作を実行するための指示のプログラムを符号化する、請求項１乃至１７の何れかに記載のパケット方式通信信号の伝送を選択的に許可するための方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は概してコンピュータネットワーク通信の分野に関し、特に共用媒体パケット交換ネットワークにおいて伝送帯域幅を公平に割り当てるための方法に関する。
【０００２】
35 U.S.C. 120 （米国特許法第120 条）に従って、本願はここに参照のため組み込まれる発明者の仮出願(1995 年11月15日、米国特許出願番号60/000,796) の優先権を主張する。
【０００３】
【従来の技術】
序論
元来設計及び実施されるように、ケーブルテレビジョン(CATV)システムはヘッドエンドコントローラ、又は分配ステーション、及び顧客の間の同軸ケーブルのみで使用される。より新しいケーブルシステムは、光ファイバーと同軸ケーブルのハイブリッドになる傾向がある。ここで光ファイバーは長距離分配に使用され、同軸ケーブルは個々の顧客サイトへの最後の数千フィートに使用される。図１は、ハイブリッドファイバー−同軸(HFC) システム１００を示し、ここでヘッドエンドコントローラ１０５が１以上の光ファイバーリンク１１０を介してファイバー−同軸変換ユニット１１５へ接続され、次に、ファイバー−同軸変換ユニット１１５が多数の個々のユーザ又は顧客サイト（例えば、ホーム１２５）へ至る同軸ケーブル分配ネットワーク１２０へ供給されている。この一般的なタイプのハードウェア設計を備えたケーブルテレビジョンシステムは、現在の技術においてかなり一般的である。
【０００４】
ケーブルシステムは、元来ヘッドエンドコントローラ１０５から顧客１２５への単一方向伝送プログラミングを提供していた。コンピュータネットワークの発展と顧客へのリアルタイム対話型サービスを提供したいという要求のために、既存のHFC ネットワークタイプのネットワークで双方向通信を提供するための効率的な手段が必要とされる。多数のサービス提供者が、現在、ケーブル上での双方向サービスを供給している。概してこれらのサービスでは、ヘッドエンドコントローラからユーザサイトへの適度に高い帯域幅のリンクがある。しかしながら、他方向におけるリンク、即ち、ユーザのサイトからネットワークへのリンクはモデム等の従来のダイアル呼出し装置又は統合サービスディジタルネットワーク(ISDN)接続を介しており、これらは共にヘッドエンド−ユーザサイトリンクよりもはるかに低い帯域幅を有する。こうしたシステムは、顧客が、ネットワークからローカルマシン（例えば、パーソナルコンピュータ、即ち、より一般的には端末装置）へ材料をダウンロードするのを迅速にするが、ユーザがあらゆる重要な伝送を発信するのを容易に許可しない。
【０００５】
顧客が重要な伝送を発信できるようにする１つの方法は、比較的高い帯域幅を有する、そうした伝送用のケーブルシステムを使用可能にすることである。既存のHFC ネットワーク内で、顧客にデータアップストリームを伝送する能力を提供するには、サービス提供者（ヘッドエンドステーションを運営する組織）が、データサービス用のケーブルスペクトラムのセクション、即ち、帯域幅、をリザーブしておくと共に、その帯域幅をアップストリームユーザへ割り当てるためのメカニズムを提供する必要がある。図２に示されるように、リザーブされた帯域幅はバーチャルダウンストリームチャネル２００及びバーチャルアップストリームチャネル２０５を生成するために用いられる。このようにして、ダウンストリームデータ及びアップストリームデータは、ファイバー−同軸変換ユニット１１５を介して、１以上の顧客サイト（ケーブルモデム又はテレビジョンセットトップボックス等の端末装置２１０を介する）とヘッドエンドコントローラ１０５の間の、単一の物理的伝送ケーブル１２０上で（周波数）多重化（マルチプレックス）される。
【０００６】
図３は、帯域幅割り当てユニット(BAU) ３０５、物理的通信ネットワーク３１０及び複数のネットワークアクセスユニット(NAU) ３１５を含む汎用コンピュータ通信ネットワーク３００のブロック図である。ヘッドエンドコントローラ１０５と同様に、帯域幅割り当てユニット３０５は、ネットワーク３１０上で、ダウンストリーム帯域幅（即ち、帯域幅割り当てユニット３０５から又は帯域幅割り当てユニット３０５を介してネットワークアクセスユニット３１５又は顧客／ユーザサイトへの伝送）及びアップストリーム帯域幅（即ち、ネットワークアクセスユニット３１５又は顧客／ユーザサイトから帯域幅割り当てユニット３０５への伝送）を割り当てる。特に、帯域幅割り当てユニット３０５はネットワークアクセスユニット３１５（例えば、ユーザの端末装置２１０等）からの伝送帯域幅に対する要求を処理する。例えば、ネットワークアクセスユニット３１５は、顧客のサイトに配置されるパーソナルコンピュータ等の端末装置２１０であってもよい。
【０００７】
幾つかの有用な定義
ネットワーク特性及び帯域幅割り当ての様々な態様に関して、以下のアルファベット順の定義のリスト及び付随する議論が、読者のために設けられる。
【０００８】
オーソライゼーション(Authorization):  単一のネットワークアクセスユニット(NAU) 又はネットワークアクセスユニットの群に、特定の期間の間、ネットワークアクセスユニットが帯域幅割り当てユニット（即ち、アップストリーム）伝送資源を使用するのを認可又は許可する、帯域幅割り当てユニット(BAU) によって出された許可。帯域幅割り当てユニットが単一のネットワークアクセスユニットへ許可を出す場合には「方向付けられたグラント(directed grant)と称され、許可が多数のネットワークアクセスユニットへ出されるときには「競合グラント(contention grant)」と称される。許可は「使わなければなくなる(use it or lose it) 」ものである。以下、グラント(Grant) の議論も参照のこと。
【０００９】
帯域幅割り当てユニット(BAU):  共用媒体のダウンストリームチャネル及びアップストリームチャネルの双方に伝送資源をスケジュール及び割り当てするヘッドエンドコントローラ内に共に配置された帯域幅割り当て機能の集合。
【００１０】
サービスのクラス(Class of Service): ユーザのサービスの品質(QoS、以下参照のこと) 要求が値の連続スペクトラムで変化しても、ネットワークは関連するネットワーク実行パラメータの特定の目標値に対応するQoS クラスの内の制限されたセットの処理だけしかできない。
【００１１】
ITU(国際電気通信連合) は、I.371 勧告において以下のQoS クラスを特定している。
1.  決定的ビットレート(Deterministic Bit Rate; DBR):  トラフィックコンフォーマンスはピークセルレート(PCR) に基づき、低いセル遅延バリエーション(CDV) 及び低いセル損失率(CLR) によって特徴付けられる。
2.  統計的ビットレート(Statistical Bit Rate; SBR):  トラフトラフィックコンフォーマンスは持続可能セルレート(SCR) 、バーストサイズ及びPCR に基づき、中位から大きなCDV 及び低いCLR によって特徴付けられる。
3.  使用可能ビットレート(Available Bit Rate; ABR):  トラフトラフィックコンフォーマンスはネットワーク内で使用可能な実際の容量の動的フィードバックに基づいている。ソースは常に信号で伝えられ／交渉された最小セルレート(MCR) を送ってもよいが、決してPCR より多く送ってはいけない。このサービスタイプは、大きいCDV 、可変CTD 及び低いCLR によって特徴付けられる。
【００１２】
ATM フォーラムは、ITU クラスを採用し、更に以下のサービスクラスを追加した。
1.  決定的ビットレートは一定ビットレート(CBR) と称される。
2.  統計的ビットレートは可変ビットレート(VBR) と称される。
3.  リアルタイム可変ビットレート(Real-Time Variable Bit Rate; rt-VBR):
トラフトラフィックコンフォーマンスは持続可能レート、バーストサイズ及びピークレートに基づく。このサービスは、低いCDV 及び低いCLR によって特徴付けられる。
4.  不特定のビットレート(Unspecified Bit Rate; UBR):  トラフトラフィックコンフォーマンスはピクセルセルレートに基づき、潜在的に非常に大きいCDV 及びCLR を有することができる。
【００１３】
IETF (インターネットエンジニアリングタスクフォース) は以下のサービスクラスを定義した。
1.  リアルタイム(Real-Time):  トラフトラフィックコンフォーマンスは持続可能なレート及びバケットサイズを備えたトークンバケットに基づく。ピークレートはラインレートと仮定される。リアルタイムサービスは、低いパケット遅延バリエーション及び非常に低いパケット損失によって特徴付けられる。
2.  プレディクティブ(Predictive): トラフトラフィックコンフォーマンスは持続可能なレート及びバケットサイズを備えたトークンバケットに基づく。ピークレートはラインレートと仮定される。プレディクティブサービスは、中位のパケット遅延バリエーション及び低い（が、リアルタイムのパケット損失より大きい）パケット損失によって特徴付けられる。
3.  ベストエフォート(Best Effort):  トラフトラフィックコンフォーマンスがない。大きなパケット遅延バリエーション及び潜在的に大きいパケット損失によって特徴付けられる。
【００１４】
フロー(Flow): この明細書のために、フローはネットワーク又はサブネットワークを横切るパケットのセットであり、その全てがサービスの品質を制御するという同じ要求によってカバーされている。所定のネットワーク構成要素において、フローは単一のアプリケーションセッションからのパケットで構成されてもよいし、多数のアプリケーションセッションからの組み合わせのデータトラフィックを含む集合であってもよい。
【００１５】
フロー識別子(Flow Identifier):  フロー識別子はパケットをフローに属するものとして一意に識別する。フロー識別子の例としては、ATM VC, IPv6フロー識別子、IPv4 <IP  アドレス、プロトコル、ポート> から<IP アドレス、プロトコル、ポート> 対、又は<NAU id, QoSクラス> 対がある。フロー識別子として使用される<NAU id, QoSクラス> 対の場合、ネットワークアクセスユニットは、多数のアプリケーションレベルフローを、帯域幅割り当てユニット−ネットワークアクセスユニット対によって使用されるフロー識別子上で多重化してもよい。この明細書のために、関連するフローは帯域幅割り当てユニットによるフロー識別子の知識である。
【００１６】
グラント(Grant):  特定のネットワークアクセスユニットが伝送できる１以上の時間／空間スロットを特定する、帯域幅割り当てユニット(BAU) ３０５からネットワークアクセスユニット(NAU) ３１５への伝送。帯域幅割り当てユニット３０５によってスケジュールされた全ての動作状態にあるネットワークアクセスユニット３１５は、その帯域幅割り当てユニット３０５からのグラントを受信及び処理するために必要とされる。上記オーソライゼーション(Authorization) の議論も参照のこと。
【００１７】
マルチプレクシング(Multiplexing): マルチプレクシング（多重化）は、幾つかの数の上層従属アソシエーションを単一の低層集合アソシエーション上にマッピングする層機能として考えられる。ISO 層モデルによって、マルチプレクシングポイントは１以上のN+1 層従属アソシエーションをN 層従属アソシエーション上に集めるN 層機能である。
【００１８】
ネットワークアクセスユニット(NAU):  次の(1) から(3) に必要な帯域幅アクセス機能の集合。 (1)トラフィックを集める、(2) 帯域幅割り当てユニット３０５の要求を実行する、(3) オーソライゼーションを受信し、それらのオーソライゼーションに基づいて伝送する。
【００１９】
ネットワーク構成要素(Network Element):  データパケットを直接処理して、フローするデータにサービスの品質制御を行うことが潜在的に可能なインターネットワークのあらゆる構成要素。ネットワーク構成要素は、ATM スイッチ、パケットスイッチ、ルーター、サブネットワーク及びエンドノードオペレーションシステムを含む。
【００２０】
サービスの品質(Quality of Service, Qos):  サービスの品質要件は、ネットワークパフォーマンスの客観的な値によって特定される。これらのネットワークパフォーマンスパラメータは、例えば、パケット損失率、伝送遅延、及び遅延バリエーションを含んでもよい。ATM において、ネットワークパフォーマンスパラメータはI.356 勧告に特定され、セル損失率(CLR) 、セル伝送遅延(CTD) 及びセル遅延バリエーション(CDV) を含む。
【００２１】
従来、インターネットは単一のQoS 、即ち、使用可能な帯域幅及び瞬間負荷に依存する遅延特性を備えたベストエフォートの供給を提供してきた。アプリケーションによって見られるQoS の制御は、ネットワークインフラストラクチャを適切に設定することによって実行される。逆に、動的に制御可能なQoS を備えたネットワークは、個々のアプリケーションセッションが、知覚した必要性に従ってネットワークパケット供給特性を要求するのを可能にし、異なるサービスの品質を異なるアプリケーションに提供することができる。コンピュータネットワーク設計及び管理の当業者の内の１人によって、いかなる動的QoS 制御も全く提供しないエンドポイントと、QoS パラメータの非常に精密且つ正確な制御を提供するエンドポイントの間に有用な可能性の範囲があることが理解される。
【００２２】
リクエスト(Request):  ネットワークアクセスユニット３１５から帯域幅割り当てユニット３０５の方向（即ち、「アップストリーム(upstream)方向）に伝送資源をリクエストする、ネットワークアクセスユニット(NAU) から帯域幅割り当てユニット(BAU) へのメッセージ。N 層エンティティにおける伝送資源のリクエストは、N+1 層要求から明示的に生成されるか、N 層エンティティにおけるN+1 層トラフィックの到着によって暗示的に生成される。
【００２３】
共用媒体(Shared Media): (1) 帯域幅割り当てユニット３０５が、伝送の全体をスケジュールし、あらゆる単一のネットワークアクセスユニット３１５、ネットワークアクセスユニット３１５の群、或いは、帯域幅割り当てユニット３０５にリンクされた全ての複数のネットワークアクセスユニット３１５へ伝送可能であり、(2) 帯域幅割り当てユニット３０５が、あらゆる単一のネットワークアクセスユニット３１５又はネットワークアクセスユニット３１５の群に、ネットワークアクセスユニット３１５から帯域幅割り当てユニット３０５へ伝送するための媒体へのアクセスを明示的にオーソライゼーションする、ようなあらゆる媒体。
【００２４】
ネットワーク通信プロトコル
ネットワークトポロジ、ケーブル長及び電気的ファクタのために、イーサネットの衝突検出付きキャリヤセンスマルチプルアクセス(CSMA-CD) がハイブリッドファイバー−同軸(HFC) 環境でうまく作用しない。IEEE 802.6ディストリビューテッドキュードデュアルバス(DQDB)標準又はANSI X3.139-1987 / ANSI X3.148-1988 ファイバーディストリビューテッドデータインタフェース(FDDI)標準等の他の帯域幅共用設計は、ユーザサイト又は端末装置サイトの各連続対の間にポイントツーポイントリンクを必要とする。この要件は、物理的ケーブル上の無線周波(RF)スペクトラム又は帯域幅を最適に使用せず、単一のケーブルセグメント１２０上で供給されなければならない多数のエンドシステム（例えば、ユーザ又は端末装置サイト）に供給するのが極めて困難になる。こうしたリングアーキテクチャはまた、動作可能で正確に機能するネットワーク（又はサブネットワーク）の全てのノードに依存するために、公共サービスとして理想的ではない。
【００２５】
ケーブルシステム上ではたらくことが知られている１つの設計は、伝送資源を固定されたインクリメントベースで割り当てることであり、これによって、端末装置が伝送のための固定されたスロットに割り当てられる固定時間領域多重化アクセス(TDMA)方法に見られるように、各端末装置２１０（又は他のネットワークアクセスユニット３１５）がその割り当てられた中でのみ伝送できるようにする。同じことは、端末装置が専用ベースで周波数を割り当てられている周波数領域多重アクセス(FDMA)方法にも見られる。固定された帯域幅アプリケーションにおいて、これらの方法はしばしば非常に効率的である。しかしながら、インターネットトラフィック又は可変率ビデオトラフィック等の固定されていない帯域幅では、TDMA方法又はFDMA方法を使用すると、帯域幅を浪費することになる。すなわち、端末装置の帯域幅要件が時間内で変わると、TDMA方法及びFDMA方法は使用可能な帯域幅を非効率的に分割する。
【００２６】
多くのアプリケーション（即ち、端末装置２１０又は他のネットワークアクセスユニット３１５で実行する処理）は、提供されるあらゆる帯域幅で動作することができ、得られる限り多くの帯域幅を有効に利用することができる。これらのアプリケーションは、弾性帯域幅要件を有すると言われており、LAN （ローカルエリアネットワーク）で現在実行している殆どのアプリケーションは、弾性帯域幅要件を有する。弾性アプリケーションを支援するサービスクラスは、インターネットコミュニティにおける「ベストエフォート(best effort) 」及び広帯域ISDN/ATMコミュニティにて使用可能ビットレート(ABR) として知られている。サービスクラスのもう１つのセットは、回路エミュレーション及びビデオ等のリアルタイムアプリケーションを支援する。リアルタイムアプリケーションは、境界付けられたジッタ（例えば、パケット遅延バリエーション）を備えたネットワークを介して伝送されてもよい。これらのアプリケーションは非弾性又はリアルタイム帯域幅要件を有すると言われている。これらのトピックの一般的な議論については、Shenker, "Fundamental Design Issues for the Future Internet," IEEE Journal on Selected Areas in Communications (JSAC), Vol. 13, No. 7, September, 1955, pp. 1176-1188 を参照のこと。
【００２７】
非同期伝送モード(ATM) 交換は、前述のアプリケーションを支援するための十分なピーク及び集合帯域幅を提供すると共に多数のサービスクラスを支援するための受け入れられたメカニズムになっている。多くのATM 交換は、現在、ABR トラフィックで使用するときに異常な行動を示すと知られるファーストインファーストアウト(FIFO)キューイングによって実行されている。インターネットコンテキストでの同じ問題の議論については、Floyd and Jacobson, "On Traffic Phase Effects in Packet-Switched Gateways," Internetworking: Research and Experience, Vol. 3, pp. 115-116 (1992); 及びZhang et al., "Observations on the Dynamics of a Congestion Control Algorithm: The Effects of Two-Way Traffic," ACM SIGCOMM 91 Conference, September 3-6, 1991, Zurich, Switzerland, pp. 133-148を参照のこと。更に、FIFOキューイングによってアイソレーションがもたらされないために、誤った行動をとるアプリケーションに対して正確に行動するアプリケーションを保護することができない。
【００２８】
重み付けられた公正なキューイング
重み付けられた公正なキューイングは、リアルタイムパケット通信に境界付けられたジッタ（パケット遅延バリエーション）を提供するために用いられる。Parekh, "A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks," Ph.D. thesis, Department of Electrical Engineering and Computer Science, MIT (1992)を参照のこと。最近の結果によれば、バーチャルクロック及び自己クロックされた公正キューイングの密接に関連したメカニズムを用いるシステムにおいて遅延境界も設定した。Goyal et al., "Determining End-to-End Delay Bounds in Heterogeneous Networks," in Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV), Durham, N.H., April 18-22, 1995  を参照のこと。
【００２９】
重み付けられた公正なキューイングはまた、ABR 又は「ベストエフォート(best effort) 」サービスクラスに優れたサービスを提供することが知られている。公正なキューイングに関するオリジナルワークは、FIFO方式キューイングによる異常を回避したいという要求に基づいていた。弾性サービスクラスのメカニズムの一般的な議論に関しては、Christopher Lefelhocz, Bryan Lyles, Scott Shenker, Lixia Zhang, "Congestion Control for Best Effort Service: why we need a new paradigm," IEEE Network Magazine, January 1996 を参照のこと。
【００３０】
結果として、重み付けられた公正なキューイング等の非FIFOキューイングメカニズム及びラウンドロビン等の公正なキューイングに対する近似は、従来のパケット交換ネットワークにおける帯域幅を割り当てる手段として提案されてきた。例えば、Demers et al., "Analysis and Simulation of a Fair Queuing Algorithm," in Proceedings of ACM SIGCOMM, pp. 1-12, (1989) 及びHahne, "Round-Robin Scheduling for Max-Min Fairness in Data Networks," IEEE Journal on Selected Areas in Communications, Vol. 9, pp. 1024-1039 (1991) を参照のこと。
【００３１】
従来のパケット交換ネットワークでは、データパケットは、宛先端末装置（即ち、より一般的には、ネットワークアクセスユニット）への次の伝送のための帯域幅が割り当てられる前に、スイッチ（例えば、ヘッドエンドコントローラ、即ち、より一般的には、帯域幅割り当てユニット）に到着する。従って、これらのシステムにおいて、データパケットと伝送に対するリクエストの間に論理的分離がない。反対に、共用媒体ネットワークは、データパケットの伝送に対するリクエストとその実際の伝送を論理的、物理的、且つ一時的に分離する。
【００３２】
従って、従来のハイブリッドファイバー−同軸テレビジョンネットワーク等の共用媒体パケット交換ネットワークにおいて、帯域幅を公平且つ動的に割り当てる必要がある。こうした帯域幅割り当ては、弾性アプリケーション及び非弾性アプリケーションの双方を収容しなければならない。
【００３３】
【発明が解決しようとする課題】
本発明の目的は、弾性アプリケーション及び非弾性アプリケーションの双方を収容する共用媒体パケット交換ネットワークにおいて、帯域幅を公平且つ動的に割り当てるための方法を提供することである。
【００３４】
【課題を解決するための手段】
本発明は、弾性アプリケーション及び非弾性アプリケーションの双方を収容する共用媒体パケット交換ネットワークにおいて、帯域幅を公平且つ動的に割り当てるための方法に関する。本方法は、共用媒体ネットワーク（例えば、ネットワーク３００）において、端末装置２１０（即ち、より一般的にはネットワークアクセスユニット３１５）コントローラとヘッドエンドコントローラ１０５（即ち、より一般的には帯域幅割り当てユニット３０５）の間に帯域幅伝送スロットを割り当てることを目的とする。具体的には、本方法はネットワークアクセスユニットからの帯域幅割り当てユニットによって受信された伝送帯域幅に対するリクエストを操作し、到着するリクエストを共用媒体へのアクセスをグラントするためのバーチャルスケジューリング時間へと変換する。更に、本設計は、サービスの品質(QoS) 要件が最も厳しいサービスクラスに最も高い優先順位を与えるメカニズムを介して、多数のQoS クラスを支援している。
【００３５】
帯域幅割り当てユニット３０５がタイムスタンプをネットワークアクセスユニット３１５からの帯域幅に対するリクエストと対応させるならば、重み付けられた公平なキューイングアルゴリズム又はバーチャルクロックアルゴリムが用いられて、帯域幅割り当てユニット３０５がリクエストするネットワークアクセスユニット３１５にダウンストリームを伝送できる一連のアップストリームスロット／伝送割り当てグラントを生成してもよい。タイムスタンプは帯域幅に対するリクエストから導出されて、その後実際のパケットが伝送される伝送タイムスロットを生成するために用いられる。重み付けられた公平なキューイング又はバーチャルクロックアルゴリズムの使用によって隙間のないジッター境界がネットワークの非弾性サービス上に置かれることが可能であると共に、重み付けられた公平なキューイングの使用によって弾性アプリケーションに優れたサービスを提供することが知られている。
【００３６】
この考えは、伝送リクエストのバッチから成るネットワークアクセスユニット３１５からのリクエストを含むように拡張され、各パケット毎に１つのリクエストが伝送される。更に、リクエストは速度によって（例えば、「１秒当たり100 パケットを下さい(Please give me 100 packets-per-second) 」或いは、バーストによって（例えば、「私は送る準備ができてキューイングされた20パケットを持っている(I have 20 packets queued up ready to send) 」）行われる。
【００３７】
更に、リクエストは個々のキューイングされた伝送リクエストの集合を表す単一の情報要素（例えば、ネットワークアクセスユニットにおいて伝送キューの集合のリクエスト状況を表す単一のサマリーリクエスト）を含んでもよい。あるいは、リクエストは多数の情報要素、ネットワークアクセスユニットでの１個以上の伝送キュー上のバーストサイズ分のリクエストを表すバッチを含んでもよい。帯域幅割り当てユニットでいずれの設計を実行する際にもネットワークアクセスユニット毎に簡単なカウンタを用いることができ、このカウンタはリクエストが帯域幅割り当てユニットに受信されるときにインクリメントされ、オーソライゼーショングラントが帯域幅割り当てユニットによって出されるときにデクリメントされる。
【００３８】
更に、保証された速度ベースのサービスでは、帯域幅割り当てユニットにおいて、特定のサービスの速度でネットワークアクセスユニットの代わりにバーチャルサービスリクエストを出す代理リクエストジェネレータが使用されてもよい。
【００３９】
請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、ハイブリッドファイバー−同軸ネットワークにおいてパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記ハイブリッドファイバー−同軸ネットワークが帯域幅割り当てユニット及び複数の端末装置ユニットを有し、前記複数の端末装置ユニットの内の各１つが帯域幅割り当てユニットと共に配置されるヘッドエンドコントローラと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、 (a)  識別された端末装置から伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、 (b) (1)前記伝送許可要求信号の到着の時間、(2) 要求された伝送と対応されるサービスのクラス、及び(3) 識別された端末装置の代わりに行われた先行する伝送許可要求のバーチャルスケジューリングタイムに基づいて、要求された伝送のためのバーチャルスケジューリングタイムを生成するステップと、 (c)伝送スケジューリングリストに要求された伝送に対応するエントリーを追加するステップと、 (d)  辞典編集分類に従って伝送スケジューリングリストを分類するステップと、 (e)  伝送スケジューリングリストの前記バーチャルスケジューリングタイムの位置に従って、識別された端末装置へ伝送許可信号を送信するステップと、を備える。
【００４０】
請求項２に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、(i) 伝送スケジューリングリストの各エントリーがサービスのクラスのインジケータを有し、 (ii) 前記エントリーが第１にサービスのクラスのインジケータによって分類され、第２にバーチャルスケジューリングタイムによって分類される。
【００４１】
請求項３に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、伝送許可要求信号が先行する交渉又は準備の結果としてヘッドエンドコントローラによって生成される。
【００４２】
請求項４に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、前記バーチャルスケジューリングタイムが速度ベースのキューイングプロセスによって生成される。
【００４３】
請求項５に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項４に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、速度ベースのキューイングプロセスが重み付けられた公平なキューイングプロセスである。
【００４４】
請求項６に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、前記バーチャルスケジューリングタイムがリザーブトラフィッククラスと対応され、バーチャルクロックアルゴリズムによって生成される。
【００４５】
請求項７に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項２に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、(i) 前記伝送許可要求信号が、固定された大きさのパケットを伝送するのを許可するために識別された端末装置によって生成される一連の伝送許可要求信号の内の１つであり、 (ii) 前記ヘッドエンドコントローラが、識別された端末装置で受信されたが未だ認可されていない要求の総数のカウンタの形で、前記端末装置において各トラフィッククラス毎のキューの表示を維持し、 (iii)端末装置あたり１つのバーチャルスケジューリングタイムだけが前記伝送スケジューリングリストに保持される。
【００４６】
請求項８に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、共用媒体パケット方式ネットワーク上でパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記パケット方式ネットワークが集中帯域幅割り当てユニット及びネットワークアクセスユニットを有し、前記ネットワークアクセスユニットが前記帯域幅割り当てユニットと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、 (a)  ネットワークアクセスユニットから伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、 (b) (1)前記伝送許可要求信号の到着の時間、(2) 前記要求された伝送と対応されるサービスのクラス、及び(3) ネットワークアクセスユニットによって又はネットワークアクセスユニットの代わりに行われた先行する伝送許可要求のバーチャルスケジューリングタイムに基づいて、要求された伝送のためのバーチャルスケジューリングタイムを生成するステップと、 (c)  伝送スケジューリングリストに前記伝送許可要求信号に対応するエントリーを追加するステップと、 (d)  辞典編集分類に従って前記伝送スケジューリングリストを分類するステップと、 (e)  伝送スケジューリングリストの前記バーチャルスケジューリングタイムの位置に従って、ネットワークアクセスユニットへ伝送許可信号を伝送するステップと、を備える。
【００４７】
請求項９に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項８に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、(i) 伝送スケジューリングリストの各エントリーがサービスのクラスのインジケータを有し、 (ii) 前記エントリーが第１にサービスのクラスのインジケータによって分類され、第２にバーチャルスケジューリングタイムによって分類される。
【００４８】
請求項１０に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項８に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、伝送許可要求信号が先行する交渉又は準備の結果として帯域幅割り当てユニットによって生成される。
【００４９】
請求項１１に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項８に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、前記バーチャルスケジューリングタイムが速度ベースのキューイングプロセスによって生成される。
【００５０】
請求項１２に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１１に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、速度ベースのキューイングプロセスが重み付けられた公平なキューイングプロセスである。
【００５１】
請求項１３に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１２に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、前記バーチャルスケジューリングタイムがリザーブトラフィッククラスと対応され、バーチャルクロックアルゴリズムによって生成される。
【００５２】
請求項１４に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１１に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、(i) 前記伝送許可要求信号が、固定された大きさのパケットを伝送するのを許可するためにネットワークアクセスユニットによって生成される複数の伝送許可要求信号の内の１つであり、 (ii) 前記帯域幅割り当てユニットが、前記ネットワークアクセスユニットで受信されたが未だ認可されていない要求の総数のカウンタの形で、ネットワークアクセスユニットの各トラフィッククラス毎のキューの表示を維持し、 (iii)  ネットワークアクセスユニットあたり１つのバーチャルスケジューリングタイムだけが前記伝送スケジューリングリストに保持される。
【００５３】
請求項１５に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、共用媒体パケット方式ネットワークにおいてパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記共用媒体パケット方式ネットワークが集中帯域幅割り当てユニット及び複数のネットワークアクセスユニットを有し、前記複数のネットワークアクセスユニットの各々が前記帯域幅割り当てユニットと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、 (a)  伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、 (b)  伝送スケジューリングリストに前記要求された伝送に対応するエントリーを追加するステップと、 (c)  前記伝送スケジューリングリストのエントリーのラウンドロビンスケジューリングに従って、前記複数のネットワークアクセスユニットの内の１つへ伝送許可信号を伝送するステップと、を備える。
【００５４】
請求項１６に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１５に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、伝送許可要求信号がネットワークアクセスユニットによって生成される。
【００５５】
請求項１７に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１５に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、伝送許可要求信号が、帯域幅割り当てユニットと前記複数のネットワークアクセスユニットの内の前記１つとの間の先行する交渉の結果として、帯域幅割り当てユニットによって生成される。
【００５６】
請求項１８に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１５に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、(i) 前記伝送許可要求信号が、固定された大きさのパケットを伝送するのを許可するために特定のネットワークアクセスユニットによって生成される複数の伝送許可要求信号の内の１つであり、 (ii) 前記帯域幅割り当てユニットが、各ネットワークアクセスユニット毎に受信されたが未だ認可されていない要求の総数のカウンタの形で、前記複数のネットワークアクセスユニットの各トラフィッククラス毎のキューの表示を維持し、 (iii)  ネットワークアクセスユニットあたり１つのバーチャルスケジューリングタイムだけが前記伝送スケジューリングリストに保持される。
【００５７】
請求項１９に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、ケーブルテレビジョンネットワークにおいてパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記ネットワークが帯域幅割り当てユニット及び複数のケーブルモデムを有し、前記複数のケーブルモデムの内の各１つが帯域幅割り当てユニットと共に配置されるヘッドエンドコントローラと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、 (a)識別されたケーブルモデムから伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、 (b)  重み付けられた公平なキューイングアルゴリズムを用いて、 (1)前記伝送許可要求信号の到着の時間、(2) 要求された伝送と対応されるサービスのクラス、及び(3) 識別されたケーブルモデムの代わりに行われた先行する伝送許可要求のバーチャルスケジューリングタイムに基づいて、要求された伝送のためのバーチャルスケジューリングタイムを生成するステップと、 (c)  伝送スケジューリングリストに要求された伝送に対応するエントリーを追加するステップと、 (d)  辞典編集分類に従って伝送スケジューリングリストを分類するステップと、 (e)  伝送スケジューリングリストの前記バーチャルスケジューリングタイムの位置に従って、識別されたケーブルモデムへ伝送許可信号を送信するステップと、を備える。
【００５８】
請求項２０に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、ケーブルテレビジョンネットワークにおいてパケット方式の通信信号の伝送を選択的に許可するための方法であって、前記ネットワークが帯域幅割り当てユニット及び複数のセットトップボックスを有し、前記複数のセットトップボックスの内の各１つが帯域幅割り当てユニットと共に配置されるヘッドエンドコントローラと動作的に接続され、帯域幅割り当てユニットによって実行される前記方法は、 (a)  識別されたセットトップボックスから伝送許可要求信号を受信するステップを備え、前記伝送許可要求信号が要求された伝送と対応され、 (b)
重み付けられた公平なキューイングアルゴリズムを用いて、 (1)前記伝送許可要求信号の到着の時間、(2) 要求された伝送と対応されるサービスのクラス、及び(3) 識別されたセットトップボックスの代わりに行われた先行する伝送許可要求のバーチャルスケジューリングタイムに基づいて、要求された伝送のためのバーチャルスケジューリングタイムを生成するステップと、 (c)  伝送スケジューリングリストに要求された伝送に対応するエントリーを追加するステップと、 (d)辞典編集分類に従って伝送スケジューリングリストを分類するステップと、 (e)  伝送スケジューリングリストの前記バーチャルスケジューリングタイムの位置に従って、識別されたセットトップボックスへ伝送許可信号を送信するステップと、を備える。
【００５９】
請求項２１に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１乃至２０に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、帯域幅割り当てユニットが、(a) プロセッサと、(b) プロセッサによって読み取り可能で、請求項１乃至２０の内の特定の１つに記載される動作を実行するための指示のプログラムを符号化するプログラム記憶デバイスとを含む。
【００６０】
請求項２２に記載のパケット方式通信信号の伝送を選択的に許可するための方法は、請求項１乃至２０に記載のパケット方式通信信号の伝送を選択的に許可するための方法において、プログラム記憶デバイスが、帯域幅割り当てユニットのプロセッサによって読み取り可能で、請求項１乃至２０の内の特定の１つに記載される動作を実行するための指示のプログラムを符号化する。
【００６１】
説明のために、特定の実施例が以下に記載される。大括弧付きの番号は、実施例の記載に従う注釈を示す。
【００６２】
明確にするために、実際の実行の全ての特徴が本明細書に記載されるわけではない。勿論、あらゆるそのような実際の実行の展開において、あらゆるそうしたプロジェクトにあるように、数多くの技術及びプログラミング決定は、１つの実行が他の実行と異なる、展開者の特定の目標及びサブ目標（例えば、システム及び業務関連制約との合致）を達成するために行われなければならないことが分かる。更に、当環境に適切な技術及びプログラミング実行に注意を払わなければならない。こうした展開努力は複雑で時間がかかるものかもしれないが、それにもかかわらず、この開示の利益を有するデータ通信システム設計の分野の当業者にとって決まりきった仕事になることが分かる。
【００６３】
【発明の実施の形態】
伝送の選択的認可の例示的方法
本例示的実施例は、ネットワーク１００又はより一般的にはネットワーク３００等のハイブリッドファイバー−同軸(HFC) ネットワーク[2] においてパケット方式の通信信号[1] の伝送を選択的に許可するための方法を含む。HFC ネットワークは、ヘッドエンドコントローラ１０５（即ち、より一般的には帯域幅割り当てユニット３０５）及び、単一のヘッドエンドコントローラ１０５によってリンクされ、即ち、動作的に接続され、且つ管理される複数の端末装置ユニット２１０[3] （即ち、より一般的には複数のネットワークアクセスユニット３１５）を有する。表１及び表２は、記載される方法を更に示す擬似コードプログラムである。各帯域幅割り当てユニット３０５は、表１のライン５０１から５０９に示されるような変数と対応している。更に、帯域幅割り当てユニット３０５は、NAU からBAU への要求によって搬送されるデータを示すライン５１０から５１３に示されるような変数を有する。システム初期設定時間において、表１のライン５１４から５１５に記載されるような初期設定機能が実行されなければならない。
【００６４】
図４のデータフロー図を参照すると、ヘッドエンドコントローラ１０５（又は他の帯域幅割り当てユニット３０５）によって実行される方法は、
(a)  表１のライン５１７から５１９に示されるように識別された端末装置２１０から伝送許可要求４０５[4] を受信するステップを備え、伝送許可要求４０５が要求された伝送と対応され、
(b) (1)伝送許可要求４０５の到着の時間[6] 、(2) 伝送許可要求４０５と対応されるサービスのクラス[7] 、及び(3) 識別された端末装置２１０の代わりに行われた先行する伝送許可要求４０５のバーチャルスケジューリングタイム[8] に基づいて、要求された伝送のためのバーチャルスケジューリングタイム[5] を生成するステップを備える。表１のライン５２０から５２３は、重み付けられた公平なキューイングに基づくこのスケジューリング動作の実施を示している。
【００６５】
(c)  表１のライン５２４によって示されるように、伝送スケジューリングリストに伝送許可要求４０５に対応するエントリーを追加する[9] ステップと、
(d)  表１のライン５０８及び５０９によって示されるように、辞典編集分類に従って伝送スケジューリングリストを分類する[10]ステップと、
(e)  伝送スケジューリングリストのバーチャルスケジューリングタイムの位置に従って、識別された端末装置２１０へ伝送許可信号４１０を送信する[11]ステップと、を備える。表２のライン６０３から６０５は、重み付けられた公平なキューイングを用いてこの送信を示し、１個より多い要求がキューイングされた場合には、明示的な要求が到着せずに追加のグラントがスケジュールされることも示している。
【００６６】
例示的方法の説明の注釈
[1]   用語「パケット方式の通信信号(Packet-based communications signal)」は、インターネットプロトコル方式の通信、非同期転送モード(ATM) 通信、データグラムサービス、フレームリレー及び同様のサービスを含む。更に、例示的な実施例は、固定又は可変サイズのパケットに適用可能であり、接続のある又は接続のない方向付けられたネットワークプロトコルに適用可能である。
【００６７】
[2]   用語「ハイブリッドファイバー−同軸(HFC) ネットワーク(hybrid fiber-coax (HFC) network) 」は、光ファイバーリンクと同軸ファイバーリンクの組合せを含むネットワーク、例えば、図１に示されるネットワーク１００（図２も参照のこと）、を意味する。本発明の説明に重要なHFC ネットワークの１つの態様は、共用媒体アクセスネットワークとしてのその特徴付けである。共用媒体アクセスネットワークは、複数のステーションが１以上の共通チャネル（例えば、ケーブル又は無線周波の集合）で通信信号を伝送するものであり、ここで特定のステーションの集合の全て（例えば、図１、図２及び図３に示されるような複数のユーザサイト又はネットワークアクセスユニット）がチャネルの使用可能な帯域幅を共用している。
【００６８】
ケーブルテレビジョン(CATV)市場で特に目標とされる、HFC ネットワークの１実施例の追加の情報は、IEEE（米国電気電子学会）802.14ケーブルテレビプロトコルワーキンググループへ提出された"The UPSTREAMS Protocol for HFC Networks" 提案に記載されており、上記に参照された仮の米国出願の一部を形成している。802.14提案は、CATVネットワークの大きな配置領域にデータ、音声及びビデオ等の統合されたサービスを提供する１つの可能な手段を示す。しかしながら、本発明はHFC/CATVネットワークに限定されず、あらゆる共用媒体パケット交換ネットワークに適用可能である。例えば、物理的ネットワーク（例えば、図３の構成要素３１０）は、物理的（例えば、銅又は同軸）ケーブル上のベースバンド若しくは無線周波伝送の使用、又は無線又は赤外線伝送の使用を含んでもよいが、それらに限定されない。
【００６９】
[3]   本発明に従ったヘッドエンドコントローラ１０５は、例えば、CATV分配ハブにあり、帯域幅割り当てユニット機能を組み込み、帯域幅割り当てユニットへ供給される全ての資源、特にダウンストリーム及びアップストリームメッセージ帯域幅の割り当て、を管理する制御ユニットである。ヘッドエンドコントローラ１０５は、１以上の物理的デバイスを含んでもよいし、及び／又は１以上の物理的デバイス（図示せず）内で１以上のプログラマブルプロセッサによって実行される１以上のプログラムとして実行されてもよい。プロセッサは汎用プロセッサであってもよいし、また、この開示の利点を有する当業者によるルーチン選択の問題として、アプリケーション特定集積回路(ASIC)等の専用プロセッサであってもよい。
【００７０】
用語「端末装置(terminal equipment)」２１０は、ユーザ又は顧客サイトにあるユニットとされ、例えば、端末アダプタ及びネットワーク終端デバイス等の、既知の通信デバイスを含むことを意図している。特に、端末装置２１０はネットワーク割り当てユニット機能を集合的に実行する多数の物理的デバイスを含んでもよい。端末装置２１０はまた、１以上の物理的デバイス内で１以上のプログラマブルプロセッサ（前の段落で記載されるようなプロセッサ、図示せず）によって実行される１以上のプログラムとして実行されてもよい。
【００７１】
IEEE 802.14 提案に従って動作されるネットワークにおいて、例えば、ダウンストリーム無線周波(RF)チャネル上の共用規律は、ヘッドエンドコントローラ１０５が共通RFチャネル上で全てのステーション（例えば、端末装置ユニット２１０）へ同報通信（ブロードキャスト）する１対多方法である。ヘッドエンドコントローラ１０５からのメッセージは、ユニキャスト、マルチキャスト又は同報通信のいずれであってもよい。他方、アップストリームRFチャネル上の共用規律は、多くの端末装置ユニット２１０が同じアップストリームRFチャネルを共用する多対１方法である。アップストリームメッセージは常にユニキャストであり、端末装置２１０からヘッドエンドコントローラ１０５へ送信される。伝送のために、端末装置２１０は、ヘッドエンドコントローラ１０５から共通アップストリームRFチャネル帯域幅の一部を使用するための許可を得なければならない。
【００７２】
802.14タイプのネットワークにおいて、アップストリームチャネルへのアクセス（例えば、端末装置２１０からヘッドエンドコントローラ１０５）は、特定のステーション方式（方向付けられた認可）、競合方式（要求認可）に基づいて、又はステーション登録（獲得認可）のために認可される。特定のタイプの認可４１０及びこれらがスケジュールされるときは、ヘッドエンドコントローラ１０５によって直接管理される。これらの認可４１０は、ダウンストリームチャネルにおけるメッセージとして適切なステーション（単数又は複数）へ伝送される。端末装置２１０からの帯域幅に対する明示的要求に加えて、本方法はヘッドエンドコントローラ１０５と端末装置２１０の間の先行する交渉に従って、ヘッドエンドコントローラで自動的に生成される暗示的要求を収容できる。
【００７３】
[5] 伝送の「バーチャルスケジューリングタイム(virtual scheduling time) 」は、他の要求４１０に対して伝送するための許可の認可４１０を順序付ける又は配列するために使用される時間値である。バーチャルタイムは当業者に既知であり、ここで更には説明されない。バーチャルスケジューリングタイムの一般的概念についての更なる情報に関しては、例えば、A. Demers, S. Keshav, 及びS. Shenker, "Analysis and Simulation of a Fair Queuing Algorithm, " in Proceedings of ACM SigComm 1989, pp. 1-12; 又はL. Zhang, "Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks," in Proceedings of ACM SigComm 1990, pp. 19-29;  又はchapter 8 of L. Peterson and B. Davie, "A Systems Approach to Computer Networks, Morgan Kaufman Publishers, ISBN 1-55860-368-9, 1996を参照のこと。
【００７４】
[6] ヘッドエンドコントローラ１０５によって受信されるような要求４０５の到着の時間は、従来のクロック、例えば、ハードウェアクロッキングメカニズム、によって測定されてもよい。
【００７５】
[7] 用語「サービスのクラス(class of service)」は、損失及び遅延の割り当てに対して同様の処理を受けるデータフローの群に関する。（従来技術セクションの定義を参照のこと。）サービスのクラス要素は、バーチャルスケジューリングタイムを生成するためのアルゴリズム、例えば、重み付けられた公平なキューイング又はラウンドロビン、を選択するために用いられてもよい。
【００７６】
幾つかの実施に際して、単一のサービスのクラスだけが存在してもよい。例えば、インターネットの過去の実施等の受け継がれたシステムは、サービスのクラス自体に言及せずに単一のサービスのクラスを有したこともある。しかしながら、現代の用語と多数のサービスのクラスネットワークが現れたために、こうしたネットワークは単一のサービスのクラスを有するとして遡及的にラベル付けされている。
【００７７】
[8] 先行する要求４０５は、前述のように明示的要求又は暗示的要求であってもよい。先行する要求は、端末装置２１０の代わりになされ、（常時ではないが）しばしば端末装置２１０自体で行われたことを意味する。いかなる先行する要求も存在しないならば、端末装置２１０は、(1) ヘッドエンドコントローラ１１５（又は他の帯域幅割り当てユニット３０５）による直接ポールに応じて、又は(2) 競合メカニズムを介して、要求を伝送することができる。
【００７８】
[9] その最も基本において、伝送スケジューリングリストのエントリーは、バーチャルスケジューリングタイムに、要求を行った端末装置２１０の識別子を加えた形をとってもよい。伝送スケジューリングリストの各エントリーの位置は、そのエントリーと対応される端末装置２１０が共用媒体ネットワーク上の要求された伝送を伝送するための許可を受信する時間の、現在の視点を示してもよい。当業者は、端末装置２１０において追加のマルチプレクシングを導入することが可能であることを理解する。
【００７９】
この点に関する本方法の利点は、Demers他の先の教示を拡張して、所定の端末装置２１０からの（又は所定の端末装置２１０の代わりの）要求４０５の明示的リストを保持する必要がなく、各端末装置の伝送キュー（単数又は複数）毎の要求４０５の明示的リストの総数、及び各キューイングの第１要求４０５と対応されるバーチャルスケジューリングタイムを保持するだけでよい。Keschav, "On the Efficient Implementation of Fair Queuing", Internetworking, Research and Experience, Vol. 2, No. 3, September 1991, pp. 157-173を参照のこと。
【００８０】
[10]  新たなエントリーは、勿論、リストの分類された順序を維持するために適切な点で伝送スケジューリングリストへ追加されることが可能である。また、新たなエントリーは追加又は予め追加されて、リストが再分類される。概して、伝送スケジューリングリストにおけるエントリーの分類は、第１に、サービスの品質インジケータを介して辞典編集的に実行され、第２に、バーチャルスケジューリングタイムによって実行される。サービスの品質の例示的リストの指定に関しては、本明細書の従来技術セクションを参照のこと。
【００８１】
[11]  許可信号４１０は、ヘッドエンドコントローラ１０５によって単一の（識別された）端末装置２１０又は端末装置の群へ出される。具体的には、許可信号４１０は、受信端末装置２１０が特定の期間にアップストリーム伝送資源を使用するのを許容する。許可信号４１０が単一の端末装置２１０へ送信されるならば、「方向付けられた認可(directed grant)」と称される。許可信号４１０が複数の端末装置２１０へ伝送されると、「競合認可(contention grant)」と称される。
【００８２】
バーチャルスケジューリングタイム
１実施例において、バーチャルスケジューリングタイムは、重み付けられた公平なキューイング等の速度ベースのキューイングプロセス、又はラウンドロビン等の公平なキューイングへの近似によって生成される。ラウンドロビン等の設計は、ラウンドロビン順序でフローを供給することによってタイムスタンプによる順序付けと近似する。ラウンドロビン順序は、バーチャルスケジューリングタイムによって提供される順序から逸脱しているが、その逸脱は制限されている。
【００８３】
概して、公平なキューイング及び関連するアルゴリズムは、パケットシーケンスで動作する（ATM セルはこの議論のためのパケットである）。ATM において、これらのシーケンスはバーチャル回路識別子(VCI) 又はバーチャル経路識別子(VPI) によって識別されると共に、インターネットプロトコルセットでは、識別はIPアドレス、プロトコル及びポート番号又はフロー識別子（本明細書の従来技術セクションにあるフロー識別子の定義を参照のこと）に基づいている。自己クロックされ重み付けられた公平なキューイング方法及びバーチャルクロックキューイング方法の双方で、パケットがタイムスタンプによって順序付けられる（分類される）（ラウンドロビン等の設計は、タイムスタンプによってパケットの順序付けへの近接を提供する）。これらのタイムスタンプは、パケットのバーチャル終了時間を表し、パケットの長さに帯域幅の特定のパケットシーケンスの共用を表す重みを掛けて得られたオフセットを開始時間値に加えることで計算される。
【００８４】
バーチャルクロックにおいて、バーチャル終了時間は以下のように計算される。
【００８５】
【数１】
0003830592.tif 000002
【００８６】
ここで、VT(f,j) はフロー（バーチャル回路）f のパケットj と対応されるバーチャル終了時間であり、Arrival(f,j)はフローf のパケットi の到着時間であり、Length(f,j) はフローf のパケットj の長さ（例えば、バイト又はビット）であり、Rate(f) はフローf に割り当てられ／設定された伝送速度で、パケット毎に変化せず、MAX オペレータはその構成要素のパラメータの内の大きい方を選択する。
【００８７】
他方、自己クロックされ重み付けられた公平なキューイング方法は、以下の数式に従ってバーチャル終了時間を割り当てる。
【００８８】
【数２】
0003830592.tif 000003
【００８９】
ここで、SystemVirtualTime は、パケット(f,j+1) が到着するときに供給される（即ち、出力される）パケットと対応されるバーチャルタイムとして定義され、Weight(f) はフローf に割り当てられるチャネルの全帯域幅のフラクションである。
【００９０】
ATM システムにおいて、セルが固定した大きさであるためにパケット長は一定であり、従って、上記数式の双方の最も右側の項はパーフロー定数になる。例えば、ATM を用いるバーチャルクロックキューイングシステムにおいて、単純化された数式は以下のようになる。
【００９１】
【数３】
0003830592.tif 000004
【００９２】
結果として、バーチャルクロック又は自己クロックされ重み付けられた公平なキューイングを実行するATM キューイングポイント（例えば、ヘッドエンドコントローラ）は以下のステップを実行する。すなわち、(1) バーチャル回路の現行のバーチャルタイムの最大値、及び(i) 帯域幅に対するリクエストの到着時間又は(ii)システムバーチャルタイムの最大値を計算するステップと、(2) ステップ(1) の結果に、使用可能なアップストリーム帯域幅全体の回路の共用を表すパーバーチャル回路定数を加えるステップと、(3) ステップ(1) 及び(2) によって割り当てられたバーチャルタイムスタンプの増加値の順に、伝送許可信号を関連する端末装置に送信するステップと、を実行する。
【００９３】
追加の実施に対する注釈
通信帯域幅を割り当てるための上記の設計において、端末装置２１０が帯域幅を要求するが、ヘッドエンドコントローラ１０５によって割れ当てられたスロットを満たさない可能性が存在する。この問題を解決するには２つの簡単な方法がある。第１の方法は、端末装置２１０（即ち、端末装置のユーザ）に対して、当該端末がリクエストして割り当てられたが使用しなかった全ての帯域幅に料金を課すものである。第２の方法は、ヘッドエンドコントローラ１０５が、割り当てられた帯域幅を使用しなかった端末装置２１０による全ての未解決の要求４０５を消去するものである。第１の方法は、リクエストするのにコストがかかるが、帯域幅を使用しない。第２の方法は、n 個の連続スロット（ここで、n はサービス提供者によって定義されるパラメータで、恐らく2 あたりである）が満たされないならば、端末装置２１０に帯域幅を再度リクエストさせる傾向にある。２つの方法を組合せたものが望ましい。
【００９４】
より一般的な実施例
前述の特定の実施例のより一般的な実施は、ヘッドエンドコントローラ１０５の代わりに帯域幅割り当てユニット３０５の使用を含むものである。ここで、用語「帯域幅割り当てユニット(bandwidth allocation unit) 」は、接続されたリンク上の通信帯域幅の管理を含む機能を有する、あらゆるコントローラの汎用記述子となることを意図している。図１に示されるような標準ケーブルテレビジョンハイブリッドファイバー−同軸ネットワークにおいて、帯域幅割り当てユニット３０５はヘッドエンドコントローラ１０５のスーパーセットである。
【００９５】
プログラム記憶デバイス
上記のように、帯域幅割り当てユニットは、汎用プロセッサをプログラミングすることによって部分的に実行されてもよい。その１つの実行は、こうしたプロセッサを有する既存の帯域幅割り当てユニットを再プログラミングすることによって達成される。プログラミングはプロセッサによって読み取り可能なプログラム記憶デバイスの使用によって達成され、このデバイスが上記の動作を実行するためにプロセッサによって実行可能な指示のプログラムを符号化する。プログラム記憶デバイスは、例えば、プロセッサを含む回路基板にインストールされた読み取り専用メモリ(ROM) の形をとってもよいし、公知の又は後に開発された種類の他の形をとってもよい。指示のプログラムは、「オブジェクトコード(object code) 」、即ち、コンピュータによって実行可能な２進形式、であっても、実行の前にコンパイル又は翻訳を必要とする「ソースコード(source code) 」であっても、部分的にコンパイルされたコード等の何らかの中間形式であってもよい。プログラム記憶デバイス及び指示の符号化の正確な形は、ここでは重要でない。
【００９６】
当業者は、本発明が米国特許第５、４２５、０２７号に記載されるようなシステムによって必要とされる帯域幅資源の割り当てを計算するための方法及びメカニズムを提供して、こうした帯域幅資源の割り当てが、証明できる堅固なリアルタイム保証を提供し、弾性クラスに恐らく（制御理論的意味において）安定した強い（誤った行動をとるユーザは正確に動作するサービスに与えられたサービスを破壊できない）サービス、例えば、ABR 又はベストエフォート、を提供することを理解する。前述の引用を参照のこと。また、S. Shenker, "A Theoretical Analysis of Feedback Flow Control," Proceedings of SIGCOMM '90, 1990,及びS. Keshav, "A Control Theoretic Approach to Feedback Flow and Control," Computer Communications Review, Vol. 21:4, September 1991 も参照のこと。これらの特性は、リクエストがランダム順又はFIFOに相当する順に供給される共有媒体に必ずしも存在していない。
【００９７】
この開示の利益を有する当業者によって、ここに記載される本発明の概念から逸脱することなく先の説明から多数の変更を行うことが可能である。従って、単に前述の説明だけでなく、設定されるクレームが、このアプリケーションプログラムに主張される排他的権利を定義することを意図している。
【００９８】
【表１】
0003830592.tif 000005
【００９９】
【表２】
0003830592.tif 000006
【０１００】
【発明の効果】
本発明は上記より構成され、弾性アプリケーション及び非弾性アプリケーションの双方を収容する共用媒体パケット交換ネットワークにおいて、帯域幅を公平且つ動的に割り当てるための方法が提供される。
【図面の簡単な説明】
【図１】ハイブリッドファイバー−同軸ケーブルテレビジョン通信ネットワークのブロック図である。
【図２】共用媒体ネットワークにおけるバーチャルアップストリーム通信チャネル及びバーチャルダウンストリーム通信チャネルのブロック図である。
【図３】汎用通信ネットワークのブロック図である。
【図４】帯域幅割り当てユニットと単一のネットワークアクセスユニットの間の情報フローのブロック図である。
【符号の説明】
１００    ネットワーク
１０５    ヘッドエンドコントローラ
２１０    端末装置
３００    ネットワーク
３０５    帯域幅割り当てユニット
３１５    ネットワークアクセスユニット
４０５    伝送許可要求
４１０    伝送許可信号
【図１】
0003830592.tif 000007
【図２】
0003830592.tif 000008
【図３】
0003830592.tif 000009
【図４】
0003830592.tif 000010