JPH09214529A - 相対的エラー解決策を用いたレートベースのスケジューリング方法及び装置 - Google Patents

Abstract

(57)【要約】 【課題】 共通のリソースをレートに基づきスケジュー
リングしそして重み付けして公平に分担させる方法及び
装置を提供する。 【解決手段】 レートに基づく新規なスケジューリング
方法は、ＡＴＭのようなコンピュータネットワークにお
いて流れをスケジューリングするのに適用することがで
きる。又、コンピュータジョブををスケジューリングす
る際に重み付けされた公平なサービスを与えるように使
用することもできる。ネットワークアダプタのレートス
ケジューリングに一般に使用される多数の方法とは異な
り、本発明の方法は、全ての流れに対して厳密なレート
保証を与えることができる。本発明の顕著な特徴は、時
間ドメインではなく、周波数ドメインにおいて動作する
ことである。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、共通のリソースの
レートに基づくスケジューリング及び重み付けされた公
平な分担のための方法及び装置に係る。レートに基づく
スケジューリング及び重み付けされた公平な分担の問題
は、多数の異なる状況において生じ、例えば、コンピュ
ータネットワークの分野又はプロセッサの設計に関連し
ている。一般に、本発明は、広範な環境及び用途におい
てあるレート（率）に基づいてジョブをスケジューリン
グする問題に係る。

【０００２】

【従来の技術】共通のリソースを共用する異なるジョブ
をスケジューリングする問題が多数の異なる状況におい
て生じる。最も一般的には、次のように表すことができ
る。

【０００３】ある種の単一のリソースは、整数ｉ＝１、
２・・・ｎで指示される多数のエンティティにより共用
される。各エンティティは、それに関連したレートＲ
（ｉ）を有する。こられのレートは、全てのＲ（ｉ）の
和がリソースの容量を越えないように指定される。例え
ば、コンピュータネットワークにおいては、エンティテ
ィが個々の流れであり、そして共用リソースが、制限さ
れた通信リンク又はサーバ容量である。エンティティ
は、あるサービス増分において一度に１つづつサービス
される。例えば、ネットワーク流のサービス増分は、１
つのパケット（又はＡＴＭ用語ではセル）である。スケ
ジューラと称する装置は、エンティティにより受け取ら
れる平均サービスレートがその指定のレートＲ（ｉ）と
なるように異なるエンティティに対してサービスの順序
を決定する必要がある。長時間の平均レートを保証する
ことはさておき、重要な目標は、各個々のサービス増
分、即ち各流れの各パケットの理想的なサービス時間と
実際のサービス時間との間の食い違いを最小にすること
である。

【０００４】このような問題が生じる環境の一例は、そ
のサイクルに対して競合するジョブをスケジューリング
しなければならないプロセッサである。全てのジョブの
重要性が等しい場合には、全てのジョブにプロセッサ容
量の等しい分担を与えるのが望ましい。しかしながら、
ジョブの重要度が異なる場合に、考えられる戦略は、全
てのジョブにそれらの重要度に対応して重みを指定し、
そして各ジョブに指定された重みに比例するプロセッサ
容量の分担を各ジョブに与えることである。この場合
に、所望のサービススレートは、流れの重みにより決定
される。別の解決策は、特定の方針及び問題の環境に対
して特有の他のルールに基づいて流れに重みを指定する
ことである。例えば、あるルールは、優先順位の高いジ
ョブにある固定の割り当てを与え、そして残りの帯域巾
を優先順位の低いジョブで分担することである。

【０００５】上記したように、同様の問題が生じる別の
例は、コンピュータネットワークである。例えば、ＡＴ
Ｍネットワークにおいては、通常、ネットワークを横断
する各流れにあるレートが組み合わされる。このレート
は、例えば、一定ビットレート（ＣＢＲ）トラフィック
のように、設定時間にネットワークと交渉した結果であ
ってもよいし、又は使用可能なビットレート（ＡＢＲ）
トラフィックの場合のように、トラフィック管理フィー
ドバック制御機構の結果であってもよい。これらレート
の組は、長時間ＣＢＲ流のように、比較的静的である
か、又はＡＢＲ流の場合のように、混雑に応答して迅速
に変化する。

【０００６】例えば、多くのパケット交換ネットワーク
の場合のように、たとえレートが明確に指定されなくて
も、異なる流れが異なる重要度のことがある。例えば、
ある流れは、１０００人のユーザからのデータの成分流
であり、一方、別の流れは、１人のユーザを表すことが
ある。このような場合に、それらの相対的な重要性が与
えられて異なる流れに重みを指定することが適当であ
る。流れの全需要が、制限されたリソース通常は通信リ
ンクの容量を越える場合に、考えられる方針は、プロセ
ッサの共用の例で上記したように、全ての流れに対しそ
れらの重みに比例して混雑スイッチを作用させることで
ある。これは、流れに対しレートを効果的に指定する。

【０００７】最近、コンピュータネットワークのスイッ
チングポイントにおけるレートに基づくスケジューリン
グ規律が多くの注目を集めている。このような機構の包
括的な検討が、ヒューイ・ザングの出版物「パケット交
換ネットワークにおける性能保証のためのサービス規律
（Ｓｅｒｖｉｃｅ Ｄｉｓｃｉｐｌｉｎｅｓ ｆｏｒＧ
ｕａｒａｎｔｅｅｄ Ｐｅｒｆｏｍａｎｃｅｉｎ Ｐａ
ｃｋｅｔ−Ｓｗｉｔｃｈｉｎｇ Ｎｅｔｗｏｒｋ
ｓ）」、プロシーディングズＩＥＥＥ、１９９５年１０
月号に見られる。これらの機構は、一般に、ネットワー
クスイッチに適用することができ、そして流れに指定さ
れたレートを保証することができる。

【０００８】

【発明が解決しようとする課題】コンピュータネットワ
ークにおいて異なる流れをスケジューリングする問題は
ネットワークのスイッチに対して存在するだけでなく、
ホストアダプタにおいても存在する。例えば、ＡＴＭネ
ットワークのアダプタは、各々関連するレートを有する
異なる流れをスケジュールしなければならない。典型的
に、ＣＢＲ流は、予め計算されたスケジュールに基づき
高い優先順位でサービスを受ける。ＣＢＲスケジュール
を予め計算する場合の１つの欠点は、非ＣＢＲ流を考慮
に入れずに計算されるために、非ＣＢＲ流のサービスが
ＣＢＲバーストにより不必要に悪影響を受けることであ
る。又、スケジュールを予め計算することは、計算的に
経費がかかる上に、通常は、ソフトウェアにおいて低速
の時間スケールで実行されるという欠点がある。これ
は、新たな接続が確立されたときにこれを実行するだけ
でよいＣＢＲ流に対して受け入れることができるが、頻
繁にレートの変化する多数の流れをスケジュールする必
要がある場合には実行できない。

【０００９】レートに基づいたスケジューリングとして
知られている別の機構は、例えば、「ザＡＴＭフォーラ
ム・トラフィック・マネージメント・スペシフィケーシ
ョン・バージョン４．０」に記載されたいわゆる「漏洩
性バケット（Ｌｅａｋｙ Ｂｕｃｋｅｔ）」である。こ
の機構は、多量の過流（ｐｅｒ ｆｌｏｗ）状態を必要
とし、従って、多数の流れに対して禁止的となる。

【００１０】又、いわゆる「タイム・ホイール」又は
「カレンダー待ち行列」解決策もしばしば使用される。
カレンダー待ち行列解決策の例は、ブラウン・Ｒの「カ
レンダー待ち行列：シュミレーション均一セット問題の
ための高速０（１）優先順位待ち行列実施（Ｃａｌｅｎ
ｄａｒ Ｑｕｅｕｅ：Ａ ｆａｓｔ ０（１） ｐｒｉ
ｏｒｉｔｙ ｑｕｅｕｅ ｉｍｐｌｅｍｅｎｔａｔｉｏ
ｎ ｆｏｒ ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｅｖｅｎ
ｓｅｔ ｐｒｏｂｌｅｍ）」、コミュニケーション
ズ．オブ・ジ・ＡＣＭ、第３１巻、第１２２０−１２２
７ページに見られる。「漏洩性バケット」機構とは異な
り、カレンダー待ち行列は、実施が簡単である。しか
し、不都合なことに、このカレンダー待ち行列解決策
は、一般に、流れにより得られる長時間平均レートがそ
の指定のレートに等しくなるよう保証することができな
い。

【００１１】それ故、ネットワークアダプタにおいて動
的に変化するレートで流れをレートに基づきスケジュー
リングするのに使用することができると共に、流れの指
定レートを保証することのできる機構を設計することが
所望される。

【００１２】又、この機構は、ＣＢＲ型トラフィック
（パケット交換ネットワークにおける保証されたサービ
スとしても知られている）及びＡＢＲ型トラフィック
（適応トラフィックとしても知られている）に同時に使
用できると共に、ＡＴＭネットワークにおけるＶＢＲ
（可変ビットレート）トラフィック（パケット交換ネッ
トワークにおける予想トラフィックとしても知られてい
る）にも使用できることが望ましい。更に、この機構
は、既に述べたレートに基づくスケジューリングの更に
一般的な状況にも使用できることが望まれる。

【００１３】ヒューイ・ザング著の出版物に説明された
スイッチスケジューリングのための解決策は、アダプタ
に容易に適用することができない。その１つの理由は、
スイッチのためのほとんどのスケジューリング機構が、
スイッチへのパケット到着時間に基づいて、異なる流れ
からのパケットのスケジューリング順序を決定するから
である。到着時間の考え方は、アダプタに対し常に充分
に特定されるものではない。というのは、通常、アダプ
タは、データを送信する準備ができたときに、アプリケ
ーションからのデータを要求するからである。

【００１４】必要とされるのは、多数の異なる環境にお
いて機能するレートスケジューリングに対する一般的な
解決策である。特に、新規な解決策は、ネットワークア
ダプタ及びネットワークスイッチに対して良好に機能し
なければならない。

【００１５】相対エラー（ＲＥ）機構と称するここに述
べる新規な機構は、特にネットワークアダプタ及びネッ
トワークスイッチに使用して、厳密なレート保証を与え
ることができる。しかしながら、上記のように、その使
用は、コンピュータネットワークの分野に限定されるも
のではない。時間ドメインで動作するほとんどの上記機
構とは異なり、ＲＥ機構は、周波数ドメインで動作す
る。その１つの効果は、レートから時間への変換（レー
トの逆数を見つけることを伴う）の必要性が排除される
ことである。

【００１６】

【課題を解決するための手段】本発明によれば、コンピ
ュータシステムの共用リソースにおいて複数のデータ流
をスケジューリングする方法であって、各データ流は、
複数のデータセルを含み、上記方法は、共用リソースに
スケジューラを設け、このスケジューラは複数のリンク
セルスロットを有し；複数のデータ流を受け取るように
スケジューラを初期化し；複数のデータ流の各々をスケ
ジューラで受け取り、各データ流は、要求された流量
（レート）を含み；上記スケジューラにより、複数のデ
ータ流各々の要求された流量各々の和が上記共用リソー
スの使用可能な帯域巾よりも小さく且つセルごとのベー
スで実際のスケジューリング時間と理想的なスケジュー
リング時間との間の相対的なエラーが最小にされるよう
に、複数のデータ流の各々をスケジューリングし；そし
て 上記受け取り及びスケジューリングの段階を繰り返
す；という段階を備えた方法が提供される。

【００１７】本発明は、その広い形態において、請求項
１に記載した複数のデータ流をスケジューリングする方
法に関する。

【００１８】

【発明の実施の形態】以下、添付図面を参照して、本発
明の好ましい実施形態を詳細に説明する。本発明の好ま
しい実施形態は、コンピュータネットワークについて説
明する。図１を参照すれば、例示的なネットワークは、
１０、１２、１４及び１６と示された４つのホストノー
ドを含むように示されている。又、各ホストノードは、
多数のユーザによって共用されるようにも示されてい
る。特に、ホストノード１０は、２６及び２８と示され
たユーザを有し、ホストノード１２は、３０及び３２と
示されたユーザを有し、ホストノード１４は、３４及び
３６と示されたユーザを有し、そしてホストノード１６
は、３８及び４０と示されたユーザを有する。

【００１９】又、図１に例示するネットワークは、各々
４２及び４４と示された２つのスイッチも備えている。
ユーザは、ネットワークを通して互いに通信する。例え
ば、ホストノード１０のユーザ２６は、ホストノード１
４のユーザ３６と通信し、ホストノード１０のユーザ２
８は、ホストノード１６のユーザ３８と通信し、ホスト
ノード１２のユーザ３０、３２は、ホストノード１６の
ユーザ３８及び４０と各々通信する。

【００２０】ホストノードは、スイッチに接続されて示
され、そしてスイッチは、通信リンクによって互いに接
続されて示されている。例えば、リンク１８は、ホスト
ノード１０をスイッチ４２に接続し、そしてスイッチ４
２及び４４は、リンク２０によって接続されている。リ
ンク２２は、ホストノード１２をスイッチ４２に接続
し、リンク２４は、スイッチ４２をホストノード１４に
接続し、そしてリンク２５は、スイッチ４４をホストノ
ード１６に接続する。便宜上、ソースから行先へのデー
タの流れをこの流れのソースと関連させる。例えば、ユ
ーザ２６からユーザ３６への流れを「ユーザ２６の流
れ」と称することにする。

【００２１】ホストノード１０、１２、１４及び１６の
各々は、スケジューラを含むように示されている。より
詳細には、ホストノード１０は、スケジューラ５０を有
し、ホストノード１２は、スケジューラ５２を有し、ホ
ストノード１４は、スケジューラ５４を有し、そしてホ
ストノード１６は、スケジューラ５６を有する。一般
に、スケジューラは、ホストアダプタカード（図示せ
ず）に存在する。

【００２２】又、スイッチ４２及び４４の各々は、スイ
ッチに接続された各リンクに関連したスケジューラを有
するものとして示されている。例えば、スイッチ４２
は、リンク１８に関連したスケジューラ５８を備えてい
る。スケジューラ６０はリンク２２に関連され、スケジ
ューラ６２はリンク２４に関連され、そしてスケジュー
ラ６４はリンク２０に関連される。スイッチ４４は、リ
ンク２０に関連したスケジューラ６６を含み、一方、ス
ケジューラ６８は、リンク２５に関連される。

【００２３】図１に示すスケジューラの各々は、例示的
ネットワーク内の共通のリソースを共用する異なる流れ
をスケジューリングする役目を果たす。

【００２４】例えば、制限ファクタ（即ち「ボトルネッ
ク」）リソースがリンクの容量であると仮定する。例え
ば、ネットワークの全てのリンクが容量１５５Ｍｂｓで
あるが、リンク２０は容量５０Ｍｂｓであると仮定す
る。それ故、ユーザ２８、ユーザ３０及びユーザ３２
は、共通のボトルネックリンク、即ちリンク２０を共用
する。それ故、公平さを確保するために、これらユーザ
の各々は、リンク２０の容量の１／３、即ちほぼレート
Ｒ（２）＝Ｒ（３）＝Ｒ（４）＝１６．６７Ｍｂｓでデ
ータを送信することができる。それ故、ユーザ２６は、
リンク１８の残りの全帯域巾即ちＲ（１）＝１３８．３
３Ｍｂｓでデータを送信することができる。しかしなが
ら、ユーザ２６及びユーザ２８のレートの和がリンク２
０の容量である１５５Ｍｂｓを越えず、且つユーザ２
８、ユーザ３０及びユーザ３２のレートの和がリンク２
０の容量である５０Ｍｂｓを越えない限り、他の送信レ
ートの指定も考えられる。スケジューラが各ユーザに与
える平均サービスレートは、これらユーザに指定された
レートに等しくなければならない。従って、スケジュー
ラ５０は、ユーザ２６及び２８によりホストノード１０
へ送られる流れをレートＲ（１）及びＲ（２）で各々ス
ケジューリングする役目を果たす。

【００２５】本発明は、図１に示すいずれのスケジュー
ラにも組み込めるもので、共通のリソースをレートに基
づいてスケジューリングしそして重み付けして公平に共
用するための方法及び装置に関する。

【００２６】例えば、本発明の実施形態は、図１に例示
するネットワークにおける流れについて説明する。しか
しながら、本発明は、コンピュータジョブをスケジュー
リングするのに重み付けされた公平なレートサービスを
必要とするいかなるコンピュータ用途にも適用できる。
ここに例示する実施形態は、非同期転送モード（ＡＴ
Ｍ）を一例として使用する。ＡＴＭネットワークは、Ａ
ＴＭセルと一般に称する固定長さのデータバケットを使
用する。しかしながら、上記したように、本発明は、可
変長さのデータパケットへと一般化することができる。

【００２７】ＡＴＭネットワークを特定例として使用す
ると、本発明は、ホストノード１０、１２、１４及び１
６の各々に含まれたスケジューラ（即ち、５０、５２、
５４及び５６）及び／又はスイッチ４２、４４のスケジ
ューラ５８、６０、６６及び６８を有するアダプタ（図
示せず）に関する。

【００２８】以下に述べるように、本発明の主たる考え
方は、相対エラー（ＲＥ）解決策を用いて、ＡＴＭネッ
トワークのスイッチ又はアダプタによりセルごとのベー
スで実際のスケジューリング時間と「理想的」なスケジ
ューリング時間との食い違いを最小にすることである。

【００２９】ここに述べる観点において、スイッチ又は
アダプタにより流れをスケジューリングする場合の問題
は次のように表される。 条件：整数１、２・・・ｎで指示されるｎ個の流れが容
量Ｃのスロットリンク（スイッチ又はアダプタ）を共有
する。

【００３０】この実施形態に対し、例えば、非同期転送
モード（ＡＴＭ）ネットワークにおいて全てのパケット
は同じサイズであると仮定する。固定サイズのパケット
を表すのにＡＴＭ期間セルを使用する。リンク速度にお
ける１つのセルの送信時間は「セル時間」又は「セルス
ロット」と称し、これらは交換可能である。

【００３１】ｊ番目のリンクセルスロットの始めに、ス
ケジューラは、どの流れのセル（もしあれば）を送信の
ためにスケジュールしなければならないかを決定する必
要がある。その目標は、各セルの実際の送信時間と理想
的な送信時間との間の境界定めされた食い違いで、流れ
ｉの長期間平均レートがＲ（ｉ）に保証されるように確
保することである。

【００３２】又、プロセッサジョブのスケジューリング
については（ネットワークにおける流れスケジューリン
グとは対照的に）、レートＲ（ｉ）が一般にジョブの重
みを表し、Ｃがこれらジョブに使用できるプロセッサ容
量であり、上記不等式は通常等式であり、そしてサービ
ス増分は通常ジョブ専用のある数のプロセッササイクル
である。

【００３３】以下ＲＥ機構又はＲＥスケジューラと称す
る本発明の構成を充分に説明するために、次の変数を使
用する。 Ｄ（ｉ、ｊ）：リンクセルスロットｊにおける流れｉの
エラー項。 Ｒ（ｉ）：流れｉのレート。ｉ＝０は、「仮想流」（以
下に述べる）に対応する。そのレートは、単に、使用可
能な帯域巾Ｃと、全ての実際の流れｉ＝１、２・・・ｎ
のレートの和との間の差である。 ｗ（ｉ）：使用可能な全帯域巾Ｃに対する流れｉのレー
ト。 注：Ｒ（ｉ）は、初期化及びレート変更のみに対して必
要とされ、流れごとの状態に記憶される必要はない。変
数ｗ（ｉ）及びＤ（ｉ、ｊ）は、流れごとに記憶され
る。

【００３４】ゼロで指示される流れは、いわゆる「仮想
流」である。そのレートは、単に、全ての「実際」の流
れにより使用されないリンク帯域巾である。ここでは、
流れ０を通常の流れと称し、流れ０のセルを送信するこ
とは、アイドルセルが送信される（「実際」の流れのセ
ルが送信されるのではない）ことを意味する。

【００３５】手順ＲＥ＿Ｓｃｈｅｄｕｌｅｒの初期化
は、次のように生じる。 ｊ＝０； ｆｏｒ ａｌｌ ｉ ｛ ｗ（ｉ）＝Ｒ（ｉ）／Ｃ Ｄ（ｉ、０）＝０； ｝

【００３６】ＲＥスケジューラは、次の擬似コードで示
すように動作する。 ＲＥ＿Ｓｃｈｅｄｕｌｅｒ； ｄｏ ｆｏｒｅｖｅｒ ｛ ｆｉｎｄ ｆｌｏｗ ｆ ｗｉｔｈ Ｄ（ｆ，ｊ）＝ｍａｘ＿｛ｉ｝Ｄ（ ｉ，ｊ） ｉｆ（（ｆ＞０）ＡＮＤ（ｃｅｌｌ ｏｆ ｆｌｏｗ ｆ ａｖａｉｌａ ｂｌｅ）） ｔｒａｎｓｍｉｔ ｎｅｘｔ ｃｅｌｌ ｆｒｏｍ ｆｌｏｗ ｆ ｅｌｓｅ ｄｏ ｎｏｔ ｔｒａｎｓｍｉｔ（ｔｒａｎｓｍｉｔ ａｎ ｉｄｌｅ ｃｅｌｌ） ｊ＝ｊ＋１； Ｄ（ｆ，ｊ）＝Ｄ（ｆ，ｊ）＋ｗ（ｆ）−１； ｆｏｒ ａｌｌ ｉ≠ｆ Ｄ（ｉ．ｊ）＝Ｄ（ｉ，ｊ）＋ｗ（ｉ）； ｝

【００３７】次の手順は、ある流れのレートが変化した
際に適当な変数を更新する。１組のレートがレート変化
の後に実現可能となり、即ち全てのレートの和がリンク
帯域巾Ｃを越えないものと仮定する。 Ｒａｔｅ＿Ｃｈａｎｇｅ； ｉｆ ｒａｔｅ ｏｆ ｆｌｏｗ ｉ〉０ ｃｈａｎｇｅｄ ｔｏ Ｒｎｅｗ （ｉ） ｗｏｌｄ（ｉ）＝ｗ（ｉ）； ｗ（ｉ）＝Ｒｎｅｗ（ｉ）／Ｃ； Ｄｏｌｄ（ｉ，ｊ）＝Ｄ（ｉ，ｊ）； Ｄ（ｉ，ｊ）＝ｗ（ｉ）−１； ｗ（０）＝ｗｏｌｄ（０）＋ｗｏｌｄ（ｉ）−ｗ（ｉ） Ｄ（０．ｊ）＝Ｄ（０，ｊ）＋Ｄｏｌｄ（ｉ，ｊ）−Ｄ（ｉ，ｊ）；

【００３８】手順Ｒａｔｅ＿Ｃｈａｎｇｅは、インアク
ティブな流れに対してｗ（ｉ）＝０を指定することによ
り新たな流れが入るか又は古い流れが退出する場合にも
使用できることに注意されたい。又、レートの変化は、
全ての「実際」の流れの全てのレートの和がリンク容量
を越えないという要件に違反しないと仮定することにも
注意されたい。同様に、あるレートで新たな流れが入る
ときには、全てのレートの和がリンク容量を依然として
越えない。多数の流れのレートが同時に変化する場合に
は、手順Ｒａｔｅ＿Ｃｈａｎｇｅは、全ての流れに対し
一度に１つづつ予想される。

【００３９】上記したＲＥスケジューラは、多数の特性
を示す。特性１と称する第１の特性は、次の通りであ
る。Ｂ（ｉ、ｍ）は、分離状態における流れｉのｍ番目
のセルの「理想的」な送信開始時間を表すものとする。
ゼロ番目のセルの送信が時間０にスタートすると仮定す
れば、ｍ番目のセルの送信は、厳密に時間ｍＴ（ｉ）に
スタートする。ここで、Ｔ（ｉ）＝ｃｅｌｌ＿ｌｅｎ／
Ｒ（ｉ）である。但し、ｃｅｌｌ＿ｌｅｎは１つのセル
の長さ（単位はビット）であり、そしてＲ（ｉ）は流れ
Ｉの指定のレート（単位は時間、例えば、秒）である。
スケジューラＲＥのもとでの流れｉのｍ番目のセルの実
際の送信時間の開始をＡ（ｉ、ｍ）で表す。従って、い
かなるｍについても、 −Ｔ（ｉ）＋ｃｅｌｌ＿ｔｉｍｅ≦Ａ（ｉ，ｍ）−Ｂ
（ｉ，ｍ）≦（ｎ／２＋１）Ｔ（ｉ） となり、ここで、ｎはサポートされる流れの数、Ｔ
（ｉ）＝ｃｅｌｌ＿ｌｅｎ／Ｒ（ｉ）はレートＲ（ｉ）
におけるセル送信間のインターバル、ｃｅｌｌ＿ｔｉｍ
ｅ＝ｃｅｌｌ＿ｌｅｎ／Ｃはリンク速度におけるセル送
信時間である。流れがスケジュールされたときにデータ
が入手できなかったためにｋ個のスケジューリング機会
が流れｉにより脱落した場合には、ｍ番目のセルが最終
的に入手できるときに、このセルの送信スタート時間
が、次を満足する。 −Ｔ（ｉ）＋ｃｅｌｌ＿ｔｉｍｅ≦Ａ（ｉ，ｍ＋ｋ）−
Ｂ（ｉ，ｍ＋ｋ）≦（ｎ／２＋１）Ｔ（ｉ） これは、ＲＥスケジューラが欠落したセル機会をあたか
もセルが実際に送信されたかのように処理し、従って、
ｍ番目のセルは、ｋ個のセル機会が欠落した場合にｍ＋
ｋ番目のセルと区別できないことを意味する。特性１
は、上記のように、分析で証明することのできる最悪の
ケースの食い違いを与える。実行される実際のシュミレ
ーションでは、全ての流れの全てのセルに対して観察さ
れた食い違いは、以下に推量子（ｃｏｎｊｅｃｔｕｒ
ｅ）として表される非常に厳密な制約を満足する。推量
子は、ＲＥ機構の食い違い境界が −Ｔ（ｉ）＋ｃｅｌｌ＿ｔｉｍｅ≦Ａ（ｉ．ｍ）−Ｂ
（ｉ．ｍ）≦Ｔ（ｉ）＋ｃｅｌｌ＿ｔｉｍｅ となるようなものである。この表示は、特性１の場合と
同じである。

【００４０】上記ＲＥスケジューラにより示される特性
２と称する第２の特性は、ＲＥスケジューリングのもと
で流れｆにより得られる長期間レートが厳密に流れＦの
指定のレートＲ（ｆ）であり、即ちＲＥスケジューラ
が、流れに指定された任意の１組のレートに対し全ての
流れに厳密なレート保証を与えるというものである。

【００４１】この第２の特性は、上記第１の特性から直
ちに続くものである。というのは、各セルがその理想的
な送信時間から固定の境界内に送信されるからである。

【００４２】上記ＲＥ機構の導出は、添付資料Ａに見ら
れる。上記特性１の証明は、添付資料Ｂに見られる。

【００４３】図２は、図１のいずれかのスケジューラに
おいて実行されるＲＥ機構の動作を示すフローチャート
である。図２は、静的なレートでのＲＥ機構の動作を示
す。プロセスは、ステップ１００で始まり、スケジュー
ラは初期化を行う。初期化の間に、スケジューラにより
次の動作が実行される。リンクセルスロットゼロは０に
等しくセットされる。仮想流量（レート）Ｒ（０）は、
使用可能な帯域巾Ｃと実際の流れｉ＝１、２・・・ｎの
全てのレートの和との間の差に等しくセットされる。最
終的に、全ての流量ｉ＝１、２・・・ｎに対し、全帯域
巾Ｃに対する各流量の流れｉのレートは、流れｉのレー
トと、使用可能な全帯域巾Ｃとの商に等しくセットさ
れ、そしてリンクセルスロット０における各流れｉのエ
ラー項は、０に等しくセットされる。

【００４４】ステップ１０４において、ＲＥスケジュー
ラは、エラー項Ｄ（ｆ、ｊ）が１組の全ての流れｉにお
ける全てのエラー項Ｄ（ｆ、ｊ）に対し最大値に等しく
なるような流れｆを見つける。

【００４５】ステップ１０８において、スケジューラ
は、流れｆが仮想流（ｆ＝０）であるか「実際」の流れ
（ｆ＞０）であるかをチェックする。その流れが仮想流
である場合、又は流れｆが実際の流れであるが、使用で
きるセルをもたない場合には、ステップ１１２におい
て、アイドルセルが送信される。もしそうであれば、ス
テップ１１６において、流れｆから次のセルが送信され
る。

【００４６】ステップ１２０において、リンクセルスロ
ットインデックスｊが１だけ増加され、そしてリンクセ
ルスロットｊにおける流れｆのエラー項は、リンクセル
スロットｊにおける流れｆのエラー項と流れｆの相対レ
ートｗ（ｉ）との和から１を引いたものに等しくセット
される。

【００４７】ステップ１２４において、流れｆのレート
に等しくない流れｉの全てのレートに対し、リンクセル
スロットｊにおける流れｉのエラー項は、リンクセルス
ロットｊにおける流れｉのエラー項と、使用可能な全帯
域巾Ｃに対する流れｉのレートとの和に等しくセットさ
れる。次いで、スケジューラは、ステップ１０４へ復帰
し、プロセスを続ける。

【００４８】図３のブロック図は、ステップ２００、２
０２及び２０４として示された次の３つの外部事象の１
つが各々生じるときにとられる動作を示している。 （１）ステップ２００において、新たな流れｉが指定の
レートＲｎｅｗ（ｉ）で入る。この場合に、変数ｗ
（ｉ）及びＲ（ｉ、ｊ）が割り当てられてゼロに初期化
され、手順Ｒａｔｅ＿Ｃｈａｎｇｅがステップ２０６に
おいてスケジューラにより実行される。 （２）ステップ２０２において、スケジューラは、流れ
ｉが退出することを検出する（又はそれが通知され
る）。この場合に、Ｒｎｅｗ（ｉ）はゼロにセットさ
れ、次いで、手順Ｒａｔｅ＿Ｃｈａｎｇｅがステップ２
０６において実行された後に、変数ｗ（ｉ）及びＲ
（ｉ、ｊ）がステップ２０８において割り当て解除され
る。 （３）ステップ２０４において、流れｉのレートは、Ｒ
ｎｅｗ（ｉ）へ変化する。この場合に、手順Ｒａｔｅ＿
Ｃｈａｎｇｅがステップ２０６において実行される。

【００４９】ステップ２００、２０２及び２０４に述べ
たこれら３つの事象は、ステップ２０６におけるＲＥ＿
Ｓｃｈｅｄｕｌｅｒの実行と完全に同期して生じ得るこ
とに注意されたい。しかしながら、ステップ２０６の手
順Ｒａｔｅ＿Ｃｈａｎｇｅの実行結果が、ステップ２０
６でスケジューラにより使用される変数ｗ（ｉ）、ｗ
（０）、Ｄ（ｉ、ｊ）及びＤ（０、ｊ）に影響するの
で、これらの変数は、事象が生じた後に、ある（好まし
くは最も接近した）セルスロット時間の始めに更新さ
れ、そしてこの更新は、ステップ２０６のＲＥ＿Ｓｃｈ
ｅｄｕｌｅｒの判断に先行するものと仮定する。

【００５０】以上、本発明の好ましい実施形態について
説明したが、本発明の概念を組み込んだ他の実施形態も
考えられることが当業者に明らかであろう。それ故、本
発明は、上記開示に限定されるものではなく、請求の範
囲のみによって限定されるものとする。

【００５１】添付資料 ＡＲＥ機構の導出 リンクのｊ番目のセルスロットの開始の時間をＳ（ｊ）
で表す（Ｓ（０）＝０と仮定する）。従って、 Ｓ（ｊ）＝ｊ ｃｅｌｌ＿ｔｉｍｅ （１） となる。但し、ｃｅｌｌ＿ｔｉｍｅは、リンク速度で１
つのセルを送信する時間（秒）である。時間Ｓ（ｊ）ま
でに、スケジューラは、ｍ（ｊ）−１の送信スケジュー
リング機会をある流れｉに与えており、従って、流れｉ
のｍ番目のセルがＳ（ｊ）又はそれ以降にスケジュール
されると仮定する。次いで、Ｓ（ｊ）又はそれ以降に次
にスケジュールされるべきセルの理想的な送信開始時間
をＬ（ｉ、ｊ）で表す。指定のレートＲ（ｉ）ビット／
秒をもつある流れｉについて考える。そのゼロ番目のセ
ルが時間Ｔ＝０秒に送信されると仮定する。流れｉは、
送信すべきセルを常に有すると仮定すれば、他の流れが
存在しない場合に、流れｉのｍ（ｊ）番目のセルの送信
開始の理想的な時間は、単に、Ｂ（ｉ、ｍ（ｊ））＝ｍ
（ｊ）ｃｅｌｌ＿ｌｅｎ／Ｒ（ｉ）であり、但し、ｃｅ
ｌｌ＿ｌｅｎは、１つのセルの長さ（ビット）である。
定義により、 Ｌ（ｉ、ｊ）＝Ｂ（ｉ、ｍ（ｊ）） （２） である。ｊ番目のリンクセルスロットの開始に流れｉに
より累積された送信時間の相対的エラーをＤ（ｉ、ｊ）
で表す。即ち、 Ｄ（ｉ、ｊ）＝（Ｓ（ｊ）−Ｌ（ｉ、ｊ）／Ｔ（ｉ） （３） となる。但し、 Ｔ（ｉ）＝ｃｅｌｌ＿ｌｅｎ／Ｒ（ｉ） （４） は、単に、レートＲ（ｉ）における流れｉのセル間の
「理想的」なインターバルであるか、又はＲ（ｉ）にお
いて１つのセルの有効なビット数送信するに必要な時間
である。最終的に、リンクレートＣに対する流れｉのレ
ートをｗ（ｉ）で表し、従って、次のようになる。 ｗ（ｉ）＝Ｒ（ｉ）／Ｃ＝ｃｅｌｌ＿ｔｉｍｅ／Ｔ（ｉ） （５） 但し、ｃｅｌｌ＿ｔｉｍｅは、リンク速度で１つのセル
を送信する時間である。Ｌ（ｉ、ｊ）の定義により、こ
れは、流れｉのスケジューリング機会においてスケジュ
ーリングされるべき流れｉの次のセルの理想的な時間で
あることが観察される。 流れｉのセルがスロットｊで送られない場合 Ｌ（ｉ、ｊ＋１）＝Ｌ（ｉ、ｊ） （６ａ） 流れｉのセルがスロットｊで送られる場合 Ｌ（ｉ、ｊ＋１）＝Ｌ（ｉ、ｊ）＋Ｔ（ｉ） （６ｂ） それ故、Ｓ（ｊ）＝Ｓ（ｊ−１）＋ｃｅｌｌ＿ｔｉｍｅ
に注目すれば、式（３）及び（６ａ、ｂ）から、次のよ
うになる。 流れｉのセルがスロットｊで送られない場合 Ｄ（ｉ、ｊ）＝（Ｓ（ｊ−１）−Ｌ（ｉ、ｊ−１） ＋ｃｅｌｌ＿ｔｉｍｅ）／Ｔ（ｉ） （７ａ） 流れｉのセルがスロットｊで送られる場合 Ｄ（ｉ、ｊ）＝（Ｓ（ｊ−１）−Ｌ（ｉ、ｊ−１） ＋ｃｅｌｌ＿ｔｉｍｅ−（Ｔ（ｉ））／Ｔ（ｉ）（７ｂ） 最後に、式（７ａ、ｂ）、（３）及び（５）から、次の
ようになる。 流れｉのセルがスロットｊで送られない場合 Ｄ（ｉ、ｊ）＝Ｄ（ｉ、ｊ−１）＋ｗ（ｉ） （８ａ） 流れｉのセルがスロットｊで送られる場合 Ｄ（ｉ、ｊ）＝Ｄ（ｉ、ｊ−１）＋ｗ（ｉ）−１ （８ｂ）

【００５２】添付資料 Ｂ特性１の証明 最初に静的なケース（即ち、レートが変化しない）を考
える。最初に式（３）から、Ｓ（ｊ）−Ｌ（ｉ、ｊ）＝
Ｄ（ｉ、ｊ）Ｔ（ｉ）となることに注意されたい。ｍ
（ｊ）番目のセルがセルスロットｊにおいて実際に送信
された流れｉについて考える。次いで、セルｍ（ｊ）の
実際の送信開始時間は、Ａ（ｉ、ｍ（ｊ））＝Ｓ（ｊ）
であり、それ故、式（２）を用いると、式（３）を次の
ように書き直すことができる。 Ａ（ｉ、ｍ（ｊ））−Ｂ（ｉ、ｍ（ｊ））＝Ｄ（ｉ、ｊ）Ｔ（ｉ） （９） 又、次のように示すことができる。 −１＋ｗ（ｉ）≦Ｄ（ｉ、ｊ）≦ｎ／２＋１ （１０） これは、式（５）に関連して、次のことを意味する。 −Ｔ（ｉ）＋ｃｅｌｌ＿ｔｉｍｅ≦Ａ（ｉ、ｍ（ｊ）） −Ｂ（ｉ、ｍ（ｊ））≦（ｎ／２＋１）Ｔ（ｉ） （１１） これは、特性１のステートメントを確立する。式（１
０）が成り立つことを示すためには、一連の５つの命題
が必要である。 命題１の証明 である。ここで、各々の新たな繰り返しにおいて、セル
がスケジュールされない流れｉのＤ（ｉ、ｊ）は、ｗ
（ｉ）だけ増加され、一方、セルがスケジュールされた
流れのＤ（ｉ、ｊ）は、ｗ（ｉ）−１だけ増加されるこ
とに注意されたい。それ故、全ての流れｉにわたるＤ
（ｉ、ｊ）の和は変化しない。というのは、最初に 命題２：Ｄ（ｉ、ｊ）≧ｗ（ｉ）−１命題２の証明 いずれかの流れｉを考える。ｗ（ｉ）≦１であり、従っ
て、ｗ（ｉ）−１≦０であることに注意されたい。従っ
て、Ｄ（ｉ、ｊ）≧０である限り、命題のステートメン
トは成り立つ。ここで、Ｄ（ｉ、ｊ）＜０のときにも命
題のステートメントが成り立つことを証明する。Ｄ
（ｉ、ｊ）がその符号を負でないものから負へ変化する
ようなｊについて考える。最初は、全てのｉについて、
Ｄ（ｉ、ｊ）＝０であるから、このようなｊが存在しな
ければならない。アルゴリズムの動作により、これは、
ステップｊ−１において流れｉがスケジュールされた場
合にのみ生じ、それ故、Ｄ（ｉ、ｊ）＝Ｄ（ｉ、ｊ−
１）＋ｗ（ｉ）−１≧ｗ（ｉ）−１となることが明らか
である。命題１は、いかなる繰り返しｊにおいても、少
なくとも１つの流れｋがＤ（ｋ、ｊ）≧０を有すること
を意味する。従って、ステップｊにおいて、スケジュー
ラにより、Ｄ（ｉ、ｊ）＜０である流れｉを選択するこ
とができない。それ故、ステップｊ＋１においては、Ｄ
（ｉ、ｊ＋１）＝Ｄ（ｉ、ｊ）＋ｗ（ｉ）≧Ｄ（ｉ、
ｊ）≧ｗ（ｉ）−１となる。ここで、この議論を続ける
と、Ｄ（ｉ、ｊ）がその符号を負に変化した後に、Ｄ
（ｉ、ｊ）は、それが正になるまで、ｊと共に単調に増
加することに注意されたい。符号が負に変化するとき
に、命題２が成り立つことは既に示したので、ここで
は、いかなるｊについても、Ｄ（ｉ、ｊ）が負であるよ
うに成立されることになる。ＱＥＤ。命題２は、式（１
０）の左辺を証明する。命題３ ：ある任意性ｋ＞０及びある繰り返しｊについて
考える。繰り返しｊにおいてＤ（ｉ、ｊ）＜０の流れの
数をｎ１（ｊ、ｋ）で表し、０≦Ｄ（ｉ、ｊ）≦ｋ＋１
の流れの数をｎ２（ｊ、ｋ）で表し、そしてＤ（ｉ、
ｊ）＞ｋ＋１の流れの数をｎ３（ｊ、ｋ）で表す。従っ
て、次のようになる。 ｎ３（ｊ、ｋ）≦ｎ１（ｊ、ｋ）／（ｋ＋１）命題３の証明 ：命題１及び２により、 である。それ故、ｎ１（ｊ、ｋ）≧（ｋ＋１）ｎ３
（ｊ、ｋ）となり、命題３のステートメントは、次のよ
うになる。推論１ ：いかなるｊについても、全流れ数をｎとすれ
ば、ｎ３（ｊ、ｋ）≧ｎ／（ｋ＋２）である。推論１の証明 ｎ＝ｎ１（ｊ、ｋ）＋ｎ２（ｊ、ｋ）＋ｎ３（ｊ、ｋ）
≧ｎ１（ｊ、ｋ）＋ｎ３（ｊ、ｋ） であり、従って、命題３から、ｎ３（ｊ、ｋ）≦ｎ１
（ｊ、ｋ）／（ｋ＋１）≦（ｎ−ｎ３（ｊ、ｋ））／
（ｋ＋１）であるか、又はｎ３（ｉ）（ｋ＋２）≦ｎで
あり、これは、推論のステートメントを意味する。命題４ ：いかなるｋ≧ｎ／２−１及びいかなるｊについ
ても、命題３の表示においてＤ（ｉ、ｊ）＞Ｋ＋１、即
ちｎ３（ｊ、ｋ）≦１となるような流れがせいぜい１つ
はある。命題４の証明 ：命題３に対する推論１により、次のよう
になる。 ｎ３（ｊ、ｋ）≦ｎ／（ｋ＋２）≦ｎ／（ｎ／２−１＋
２）＝２ｎ／（ｎ＋２）＜２ ｎ３（ｊ、ｋ）は整数であるから、ｎ３（ｊ、ｋ）≦１
を意味する。ＱＥＤ。推論２ ：いかなるｊについても、Ｄ（ｉ、ｊ）＞ｎ／２
である流れがせいぜい１つはある。推論２の証明 ：ｋ＝ｎ／２−１にセットすることによ
り、命題４から直ちに続く。命題５ ：Ｄ（ｉ、ｊ）≧ｎ／２＋１の流れはない。命題５の証明 ：幾つかのｉ、ｊがあって、 Ｄ（ｉ、ｊ）≧ｎ／２＋１ （１２） であるとする。少なくとも１つの流れｉに対して式（１
２）が生じる最初の時間ｊを考える。それ故、Ｄ（ｉ、
ｊ−１）＜ｎ／２＋１であり、従って、ｊ番目のステッ
プにおいて、Ｄ（ｉ、ｊ）の値が増加される。これは、 Ｄ（ｋ、ｊ−１）≧Ｄ（ｉ、ｊ−１） （１３） である他の流れｋが時間ｊ−１にスケジュールされたこ
とを意味することが容易に分かる。従って、次のように
なる。 Ｄ（ｉ、ｊ−１）＝Ｄ（ｉ、ｊ）−ｗ（ｉ）＞ｎ／２＋
１−ｗ（ｉ）＞ｎ／２ しかしながら、スロットｊ−１においてスケジュールさ
れた流れｋは、 Ｄ（ｋ、ｊ−１）≧Ｄ（ｉ、ｊ−１） でなければならず、それ故、式（１３）は、Ｄ（ｋ、ｊ
−１）≧ｎ／２も意味し、従って、Ｄ（ｉ、ｊ−１）≧
ｎ／２及びＤ（ｋ，ｊ−１）≧ｎ／２であるような２つ
の流れｉ及びｋが存在する。しかしながら、これは、推
論２のステートメントを否認する。得られた否認が命題
５の証明を完了する。ここで、式（１０）の右辺も証明
され、これは、静的なケースに対する特性１の証明を完
了する。ここで、手順Ｒａｔｅ＿ｃｈａｎｇｅが命題１
で与えられる不変量を保持することに注意されたい。命
題１の証明を繰り返すと、命題１がレート変更の後も成
立し続けることが分かる。命題２が成立することを明ら
かにすると共に、レート変更の後に、流れｉ及び「仮
想」流０以外の流れのＤ（ｉ、ｊ）が不変に保たれ、 Ｄ（ｉ、ｊ）＝ｗｎｅｗ（ｉ）−１ 及び Ｄｎｅｗ（０、ｊ）＝Ｄｏｌｄ（０、ｊ）＋Ｄｏ１ｄ
（ｉ、ｊ）−Ｄｎｅｗ（ｉ、ｊ） であることにも注意されたい。レート変更まで命題２が
成り立つと仮定する。従って、全てのｋに対して、 Ｄｏｌｄ（ｋ、ｊ）≧ｗｏｌｄ（ｋ）−１ である。それ故、 Ｄｎｅｗ（０、ｊ）＝Ｄｏｌｄ（０、ｊ）＋Ｄｏｌｄ（ｉ、ｊ） −Ｄｎｅｗ（ｉ，ｊ）≧ｗｏｌｄ（０）−１＋ｗｏ１ｄ（１） −１−ｗｎｅｗ（ｉ）＋１＝ｗｎｅｗ（０）−１ となる。従って、命題２は、レート変更の後も全ての流
れに対して成り立つ。ここで、命題２の証明の議論を繰
り返すと、これがレート変更後のその後の繰り返しに対
して成り立つことが分かる。最初に（第１のレート変更
の前に）命題２が成り立つことが示されたので、レート
変更のシーケンスについての帰納により、レート変更が
存在しても命題２が成り立つ。従って、式（１０）の左
辺は、レート変更が存在しても成り立つ。命題３及び４
の証明は、命題１のみに依存し、それ故、レート変更が
存在しても成り立つことが容易に明らかである。最終的
に、命題４は、レート変更の直後に成り立つので、命題
５の証明は、変更なしに繰り返すことができる。従っ
て、式（１０）は、レート変更が存在しても成り立つ。
これは、式（１０）の右辺を立証する。ここで、レート
変更のときに、レート変更後の次のセルの理想的な終了
時間が充分に定められないことに注意されたい。という
のは、手前のセルと次のセルとの間に経過する時間が古
いレートにも依存するからである。これは、次のように
定義しなければならない。Ｄ（ｉ、ｊ）の新たな値が与
えられると、式（３）に基づきレート変更後の次のセル
の送信の開始の新たな理論的な時間Ｌ（ｉ、ｊ）を最初
に定義する。この定義が与えられると、流れのレートが
再び変化するまで式（８ａ、ｂ）の導出は、有効なまま
である。従って、特性１は、レート変更が存在しても成
り立つ。

【図面の簡単な説明】

【図１】本発明が使用されるコンピュータネットワーク
を例示するブロック図である。

【図２】図１のホストノード１０のスケジューラ５０に
関して本発明を説明するフローチャートである。

【図３】図１のホストノード１０のスケジューラ５０に
対する３つの外部事象の作用を示すフローチャートであ
る。

【符号の説明】

１０、１２、１４、１６ ホストノード １８、２０、２２、２４、２５ リンク ２６、２８、３０、３２、３４、３６、３８、４０ ユ
ーザ ４２、４４ スイッチ ５０、５２、５４、５６、５８ スケジューラ ６０、６２、６４、６６、６８ スケジューラ

Claims (6)

【特許請求の範囲】
1. 【請求項１】 コンピュータシステムの共用リソースに
   おいて複数のデータ流をスケジューリングする方法であ
   って、各データ流は、複数のデータセルを含み、上記方
   法は、 上記共用リソースにスケジューラを設け、このスケジュ
   ーラは複数のリンクセルスロットを有し；複数のデータ
   流を受け取るようにスケジューラを初期化し；複数のデ
   ータ流の各々をスケジューラで受け取り、各データ流
   は、要求された流量を含み；上記スケジューラにより、
   上記複数のデータ流各々の要求された流量各々の和が上
   記共用リソースの使用可能な帯域巾より小さく且つセル
   ごとのベースで実際のスケジューリング時間と理想的な
   スケジューリング時間との間の相対的なエラーが最小に
   されるように、複数のデータ流の各々をスケジューリン
   グし，そして上記受け取り及びスケジューリングの段階
   を繰り返す；という段階を備えたことを特徴とする方
   法。
2. 【請求項２】 スケジューラを初期化する上記段階は、 リンクセルスロットの値をゼロにセットし；仮想流量の
   値を、上記共用リソースの使用可能な帯域巾の値と、全
   てのデータ流の流量の和の値との差に等しくセットし；
   各データ流の流量を、各データ流の流量と使用可能な全
   帯域巾との商にセットし；そしてリンクセルスロット０
   における各流量のエラー項をゼロの値にセットする；と
   いう段階を含む請求項１に記載のコンピュータシステム
   の共用リソースにおいて複数のデータ流をスケジューリ
   ングする方法。
3. 【請求項３】 複数のデータ流をスケジューリングする
   上記段階は、 データ流及びデータ流のセルが使用できるかどうかを決
   定し；上記決定段階が、上記データ流及びデータ流のセ
   ルが使用できないと決定した場合にはナルセルを送信
   し；上記決定段階が、上記データ流及びデータ流のセル
   が使用できると決定した場合には上記セルを送信し；上
   記リンクセルスロットを増加し；上記リンクセルスロッ
   トにおける上記データ流のエラー項を、上記リンクセル
   スロットにおける上記データ流のエラー項と、使用でき
   る全帯域巾に対するデータ流の流量との和から１を引い
   たものに等しくセットし；そして上記流量に等しくない
   データ流の全ての流量に対し、上記リンクセルスロット
   における上記データ流のエラー項を、上記リンクセルス
   ロットにおける流れのエラー項と、使用できる全帯域巾
   に対する流量との和に等しくセットする；という段階を
   備えた請求項１に記載のコンピュータシステムの共用リ
   ソースにおいて複数のデータ流をスケジューリングする
   方法。
4. 【請求項４】 コンピュータシステムの共用リソースに
   おいて複数のデータ流をスケジューリングする装置であ
   って、各データ流は、複数のデータセルを含み、上記装
   置は、 共用リソースのスケジューラであって、複数のリンクセ
   ルスロットを有するスケジューラを形成する手段と；複
   数のデータ流を受け取るようにスケジューラを初期化す
   る手段と；複数のデータ流の各々をスケジューラで受け
   取るための手段とを備え、各データ流は、要求された流
   量を含み；上記複数のデータ流各々の要求された流量各
   々の和が上記共用リソースの使用可能な帯域巾より小さ
   く且つセルごとのベースで実際のスケジューリング時間
   と理想的なスケジューリング時間との間の相対的なエラ
   ーが最小にされるように、複数のデータ流の各々をスケ
   ジューリングするスケジューラと；上記受け取り及びス
   ケジューリングの段階を繰り返す手段とを備えたことを
   特徴とする装置。
5. 【請求項５】 スケジューラを初期化する上記手段は、 リンクセルスロットの値をゼロにセットする手段と；仮
   想流量の値を、上記共用リソースの使用可能な帯域巾の
   値と、全てのデータ流の流量の和の値との差に等しくセ
   ットする手段と；各データ流の流量を、各データ流の流
   量と使用可能な全帯域巾との商にセットする手段と；リ
   ンクセルスロット０における各流量のエラー項をゼロの
   値にセットする手段とを備えた請求項４に記載の装置。
6. 【請求項６】 複数のデータ流をスケジューリングする
   上記手段は、 データ流及びデータ流のセルが使用できるかどうかを決
   定する手段と；上記決定段階が、上記データ流及びデー
   タ流のセルが使用できないと決定した場合にはナルセル
   を送信する手段と；上記決定段階が、上記データ流及び
   データ流のセルが使用できると決定した場合には上記セ
   ルを送信する手段と；上記リンクセルスロットを増加す
   る手段と；上記リンクセルスロットにおける上記データ
   流のエラー項を、上記リンクセルスロットにおける上記
   データ流のエラー項と、使用できる全帯域巾に対するデ
   ータ流の流量との和から１を引いたものに等しくセット
   する手段と；上記流量に等しくないデータ流の全ての流
   量に対し、上記リンクセルスロットにおける上記データ
   流のエラー項を、上記リンクセルスロットにおける流れ
   のエラー項と、使用できる全帯域巾に対する流量との和
   に等しくセットする手段とを備えた請求項４に記載の装
   置。