JPH04287131A - 資源の時分割多重利用化装置及び方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、例えば中央処理装置、
又はディジタルデータ伝送システムのような、多重利用
資源のスケジューリングに関し、特に、作業を処理する
ために資源を使用したい需要を有する存在体（エンティ
ティ）、から与えられた作業を、多重利用資源が、制御
されたレートで行うという仕方での資源の多重利用スケ
ジューリングに関する。

【０００２】

【従来の技術】どの多重利用資源にとっても、資源のス
ケジューリングは問題である。スケジューリングの目標
は、資源を最大限に活用すること、資源を最も必要とす
るエンティティの、資源へのアクセスを最大にすること
、及び、資源を使用する全てのエンティティが資源に対
して少なくともある程度のアクセスを得られるようにす
ることである。

【０００３】中央処理装置及びディジタルデータ伝送シ
ステムのような多重利用資源の速度及び能力が増大する
につれて、これらの資源を使用するエンティティには、
実時間（リアルタイム）処理を要するものが含まれるよ
うになってきた。すなわち、定常的な率（レート）で資
源にアクセスする必要があるのである。このような、リ
アルタイム処理を要するエンティティの例は、ディジタ
ル化したビデオデータをテレビ受像機に供給する仮想回
路である。

【０００４】ディジタル化したビデオデータをテレビ受
像機が消化するときの消化レートは、固定である。もし
データがそのレートで到着しない場合、テレビ影像は動
くのをやめるか又は、全く映らなくなる。もしデータが
この固定レートよりも早く到着すると、データをバッフ
ァに記憶させる必要が生じる。又、もし少しの時間長さ
の間でもデータの到着レートが消費レートよりも高いま
までいる場合には、バッファはオーバフローし、データ
は廃棄されることになる。

【０００５】

【発明が解決しようとする課題】従来技術のスケジュー
ラは、リアルタイム処理を要しないエンティティに対す
る多重利用資源のスケジューリングについてはかなりよ
く処理してきたが、リアルタイム処理を要するエンティ
ティに対するスケジューリングについては、処理があま
りよくなかった。その理由は、従来技術のスケジューラ
においては、或るエンティティに対して多重利用資源が
作業を行うレートが、数の関数であり、多くの場合、そ
の資源を使用する他のエンティティの優先度の関数であ
ることである。

【０００６】もし或るエンティティが低い優先度を有す
るが高い優先度のエンティティが現在その資源を使用し
ていない場合、この低い優先度のエンティティは、その
資源に対して高いレートのアクセスを与えられる。とこ
ろが、もし高い優先度のエンティティがその資源を使用
している場合は、この低い優先度のエンティティはその
資源に対して低いレートのアクセスしか与えられない。

【０００７】更に、これらのことから判るように、資源
すなわちシステムへのエンティティのアクセスレートは
、そのシステムを使用しているエンティティの混合比率
が変化するにつれ、時間の経過の間に変化することがあ
る。

【０００８】ディジタル化したビデオデータを供給する
仮想回路の例が示すように、リアルタイム処理を要する
エンティティは、多重利用資源へのアクセスについて、
アクセスレートの制御された、「レート制御付き」アク
セスを必要とする。このようなレート制御付きアクセス
には、２つの面がある。第１に、リアルタイム処理を要
するエンティティは、或る設定時間長さにわたって比較
的一定な資源アクセス量を要する。この時間長さは、「
平均時間長さ、又は平均時間間隔」として知られている
。

【０００９】第２に、この一定な資源アクセス量は、平
均時間長さを通して比較的均一に与えられなければなら
ない。もし、例えば、仮想回路が、送信機へのアクセス
を全て平均時間長さの初めに受け、平均時間長さの終り
には少しも受けないとすると、テレビ受像機のバッファ
はオーバフローし、ビデオデータの一部が失われてしま
う。リアルタイム処理を要するエンティティが、多重利
用資源に対して平均時間長さを通して均一なアクセスが
得られないと、「ジッタ」現象が生じる。

【００１０】リアルタイム処理を要するエンティティが
必要とする均一度は、平均時間長さより短い第２の時間
長さの間に得られる資源へのアクセス量によって表され
る。この第２の時間長さは、「ジッタ平均時間長さ」と
して知られている。テレビ受像機の例に次いていえば、
ジッタ平均時間長さの間のアクセス量は、もしこのエン
ティティがジッタ平均時間長さの各々についてこのアク
セス量を受けた場合に平均時間長さの間にテレビ受像機
のバッファがオーバフローしないようなアクセス量でな
ければならない。

【００１１】上記から明らかなように、リアルタイム処
理を要するエンティティの間で資源を多重利用するため
に必要なのは、或るエンティティが、その必要とするア
クセスをその平均時間長さの間及びジッタ平均時間長さ
の間の両方において得られるように、これらのエンティ
ティに資源へのアクセスを与えることのできる技術であ
る。本発明の目的は、このような技術を提供することに
ある。

【００１２】

【課題を解決するための手段】本発明はその一態様にお
いて、資源を、エンティティから与えられる複数の作業
に対して時分割多重利用するための資源の時分割多重利
用化装置である。この資源は、複数の時間長さの間、こ
れらの複数の作業を実行する。この装置は、与えられた
作業を記述する作業記述子からなる作業記述子セットか
らなる。

【００１３】この装置は更に、これらの複数の時間長さ
からなる１つの時間長さセットの時間中、これらの作業
記述子セットの中の作業記述子を、この資源に、規則的
な仕方で供給するためのサーバ（供給窓口機構）と、こ
れらの作業記述子を受けるための且つ、これらエンティ
ティのうちの或る１つのエンティティから与えられた作
業に対するこれらの作業記述子をこれらの作業記述子セ
ット内に配置するための手段とからなり、このサーバが
これらの作業記述子をこの規則的な仕方で供給すること
によって、この資源が、この或る１つのエンティティか
ら与えられた作業を、制御されたレートで実施する。

【００１４】本発明の別の態様においては、これらの作
業記述子セットは、作業記述子の待ち行列として構成さ
れ、作業記述子をこれらの作業記述子セット内に配置す
るための手段は、作業記述子待ち行列管理体として構成
される。

【００１５】本発明の他の態様においては、アクセスレ
ートの制御を要しないエンティティのための最善努力待
ち行列を有する。待ち行列中の作業で現在実行中の作業
のない時間長さは、この最善努力待ち行列中の作業に使
用される。

【００１６】本発明の更に別の態様においては、エンテ
ィティが得るアクセスのレートが、パラメータによって
制御される。このパラメータは、作業記述子セット中の
作業記述子の密度を制限する機能を有する。

【００１７】本発明の更に他の態様においては、エンテ
ィティは、高速ネットワークに接続されたデバイス間の
接続、として構成され、多重利用資源は、このネットワ
ークとして構成される。

【００１８】本発明のこれらの、又その他の、態様、目
的、及び利点については、以下の詳細な説明及び図面を
参照することによって当業者には容易に理解できよう。

【００１９】

【実施例】以下の説明及び添付図面において、符号番号
の内、末尾の２桁を除く桁の数字はその要素項目の図示
されている図番を示し、末尾２桁はその要素項目が最初
に現れる図面中での追い番号である。

【００２０】以下、まずレートを制御してアクセスさせ
る技術の概観について述べ、次に高速パケットネットワ
ークに用いる具体的実施例について説明する。

【００２１】図１は、エンティティから受けた複数の作
業を多重利用資源に、制御されたレートで与えるための
、資源の時分割多重利用化装置１０１の概観図である。 これらの作業の各々は、行われるべき作業について記述
する作業記述子１０３によって代表される。或る場合に
は、作業記述子１０３自身が、行われるべき作業を有す
る。

【００２２】各作業記述子１０３は、行われるべき作業
の実施要請元であるエンティティを識別するエンティテ
ィ識別子（ＥＩＤ）１０５を有する。エンティティの例
としては、仮想回路、ＬＡＮに接続されたデバイス間の
接続体、又は処理装置において行われるプロセスが挙げ
られる。待ち行列管理体１０７は、各作業記述子１０３
を受けて、待ち行列１１５、及び１１７（０）から１１
７（ｎ）までのうちの１つの待ち行列の末尾に入れる。 資源サーバ、又はサーバ（資源に対する作業記述子供給
窓口機構）１０１によって、待ち行列の先頭から作業記
述子１０３が取り出され、多重利用資源に供給される。

【００２３】或る時点において、或るエンティティに与
えられるアクセスは、最善努力アクセス（特にレートを
制御されず、最善努力で得られるアクセス）、又は制御
されたレートでのアクセスのいずれかである。待ち行列
管理体１０７は、前者の場合には、このエンティティの
作業記述子１０３を、矢印１１１に示すように、最善努
力待ち行列に入れ、後者の場合には、矢印１１３で示す
ように、フレーム待ち行列１１７（０）から１１７（ｎ
）までのうちの１つの待ち行列に入れる。

【００２４】フレーム待ち行列１１７は各々、複数のス
ロットからなる１つの「スロットフレーム」に対応する
。各スロットは、１つの「スロットタイム」、すなわち
、１つの作業記述子１０３によって代表される作業を多
重利用資源が完了するのに要する時間長さ、を表す。 １つのフレーム中のスロットの数に１つのスロットによ
って表される時間長さを乗じたものが、フレーム待ち行
列１１７に対する「フレームタイム」である。

【００２５】サーバ１２１は、フレーム待ち行列１１７
のフレームタイムの間、或るフレーム待ち行列から取り
出した作業記述子に対応する作業を多重利用資源に与え
、続いて次のフレーム待ち行列１１７に行き、そのフレ
ーム待ち行列１１７のフレームタイムについて同様のこ
とを行う。

【００２６】もし或るフレーム待ち行列１１７の中に、
そのフレーム待ち行列１１７の全フレームタイムを必要
とするような十分な作業記述子がない場合には、そのフ
レーム待ち行列１１７のフレームタイムが終りになるま
で最善努力待ち行列１１５から作業記述子を供給する。 もし最善努力待ち行列１１５と前記の或るフレーム待ち
行列１１７とが両方とも空きの場合は、サーバ１２１は
、多重利用資源に作業記述子１０３を供給せず、多重利
用資源は、フレーム待ち行列１１７のフレームタイムの
残りの時間の間、アイドル状態となる。

【００２７】上記から判るように、待ち行列管理体１０
７は、或るエンティティ用の作業記述子１０３のフレー
ム待ち行列１１９への入れ方から、サーバ１２１がその
エンティティに属する作業を多重利用資源に与える際の
与え方のレートを判断できる。

【００２８】更に、待ち行列管理体１０７は、或る平均
時間長さの間に或るエンティティに対して行う作業量の
最大値を保証できるだけでなく或るジッタ平均時間長さ
の間に或るエンティティに対して行う作業量の最大値を
も保証できるような仕方で、フレーム待ち行列１１９に
作業記述子１０３を入れることができる。装置１０１は
、このようにして、多重利用資源への、レートを制御し
た状態でのアクセスを得ることができる。

【００２９】装置１０１における平均時間長さ（＄ＡＩ
＄）は、次に示す「数１」で表される。

【００３０】

【数１】

【００３１】ここに、＄ＦＴ＄は１つのフレームのフレ
ームタイム、又、＄ＦＮ＄はフレームの数である。＄Ｆ
Ｎ＄は、もちろん、装置１０１のフレーム待ち行列１１
７の数と同一である。

【００３２】ここで、以下の説明に便利なように更に、
「スーパーフレーム」（ＳＦ）について定義しておく。 すなわち、「スーパーフレーム」（ＳＦ）は、フレーム
待ち行列１１９によって表される複数のフレーム中の全
てのスロットからなる。これらのスロットの数が「スー
パーフレームサイズ」（ＳＦＳ）で、これは、１つのフ
レーム中のスロットの数すなわち「フレームサイズ」（
ＦＳ）と、＄ＦＮ＄との積である。

【００３３】平均時間長さの間に資源が或るエンティテ
ィのために作業をする最大時間量は、次に示す「数２」
で表される。

【００３４】

【数２】

【００３５】ここに「ＥＳ」は、１つのスーパーフレー
ムの間に待ち行列管理体１０７が或るエンティティに割
り当てることが許されている最大スロット数である。

【００３６】更に、或るエンティティが利用できる多重
利用資源の全「帯域幅」に対する比率が次の「数３」に
よって定められる。

【００３７】

【数３】

【００３８】以下に更に詳細に述べるように、待ち行列
管理体１０７は、或るエンティティに対するフレーム待
ち行列１１９中の作業記述子１０３の密度を制御するこ
とによって、ジッタを防止する。或る実施例において、
待ち行列管理体１０７は、或るエンティティが或るフレ
ーム待ち行列１１７中に有する作業記述子１０３の数を
制限し且つ、そのエンティティの作業記述子１０３が含
まれているフレーム待ち行列１１７間の時間長さを定め
ることによって、密度を制御する。

【００３９】サーバが或るエンティティの作業記述子を
含む１つのフレーム待ち行列１１７からそのエンティテ
ィの作業記述子１０３の取り出しを始める時間点と、サ
ーバがそのエンティティの作業記述子１０３を含む次の
フレーム待ち行列１１７から作業記述子１０３の取り出
しを始める時間点との間の時間長さが、そのエンティテ
ィのジッタ平均時間長さ（ＪＡＩ）である。このジッタ
平均時間長さは、次の「数４」によって表される。

【００３７】

【数４】

【００３８】ここに、Ｉは、飛び越えたフレームの数で
ある。ジッタ平均時間長さの間に行われる最大作業量は
、１つのフレームにおいて待ち行列管理体１０７がその
エンティティに割り当てることのできる最大スロット数
「ＭＦＳ」である。「ＭＦＳ」で表すと、「ＥＳ」／「
ＡＩ」は次の「数５」で表される。

【００３９】

【数５】

【００４０】次に、図２及び図３を参照してフレーム待
ち行列１１９に作業記述子１０３を入れるステップにつ
いて説明する。

【００４１】フレーム待ち行列１１９中の、レート制御
を要するエンティティの作業記述子１０３の密度を制御
するために待ち行列管理体１０７が用いるデータ構造を
、レート情報部（ＲＩ）１０９として図１に示す。この
レート情報部１０９をより詳細に示したものが図２であ
る。レート情報部１０９は、多重利用資源に対してレー
ト制御付きのアクセスを有する各入力項目についてのエ
ンティティレート情報（ＥＲＩ）を内蔵する入力項目レ
ート情報部分２０１を有する。

【００４２】各入力項目レート情報部分２０１には、次
の４種類の情報が含まれる。その１は「規定数」２０３
で、フレーム待ち行列１１７中に或るエンティティが持
つことのできる作業記述子１０３の最大数を示す。その
２は「間隔」２０５で、規定数２０３によって許可され
た数の作業記述子１０３が或るフレーム待ち行列１１７
に加えられた後に飛び越えられるフレーム待ち行列１１
７の数を示す。

【００４３】その３は、「現フレーム待ち行列番号」（
現行列番号）２０７で、現在そのエンティティの作業記
述子が加えられつつあるフレーム待ち行列の番号を示す
。そして、その４は、「残数」２０９で、現フレーム待
ち行列番号２０７によって指定されたフレーム待ち行列
１１７に更に入れることのできる作業記述子１０３の数
を示す。

【００４４】フレーム待ち行列１１９は、待ち行列管理
体１０７の中の、別のデータ構造であるフレーム待ち行
列状態部１０８から情報が得られる。図３にフレーム待
ち行列状態部１０８の詳細を示す。各フレーム待ち行列
１１７は、フレーム待ち行列状態部１０８にフレーム待
ち行列状態入力部分３１１を有する。各入力部分３１１
は、対応するフレーム待ち行列１１７の番号によって識
別される。

【００４５】フレーム待ち行列状態入力部分３１１の各
々には、対応するフレーム待ち行列１１７についての次
の４種類の情報が含まれる。その１は「先頭部」情報３
１３で、対応するフレーム待ち行列中の最初の作業記述
子１０３を示すポインタである。その２は「末尾部」情
報３１５で、対応するフレーム待ち行列中の最後の作業
記述子１０３を示すポインタである。

【００４６】その３は「カウント」情報３１７で、対応
するフレーム待ち行列１１７に現在ある作業記述子１０
３の数を示す。そして、その４は「制限値」情報３１９
で、対応するフレーム待ち行列１１７の中に存在を許容
される作業記述子１０３の最大数である。

【００４７】制限パラメータがあるため、フレーム待ち
行列１１７に対応するフレームの全てについてレート制
御を要するエンティティの作業記述子１０３を入れる必
要はなく、したがって、フレームの一部は最善努力待ち
行列１１５にある作業記述子１０３を入れてもよい。

【００４８】待ち行列管理体１０７が、レート制御を要
するエンティティに属する作業記述子１０３をフレーム
待ち行列１１７に入れるために用いる手法は、次に示す
ステップによるループである。このループは、待ち行列
１１９及び１１５に入れられるべき作業記述子１０３が
あり且つ待ち行列１１９及び１１５中に余地がある限り
続く。

【００４９】まず、或る作業記述子１０３について、も
し「残数」２０９が、入力項目レート情報部分２０１に
よって表されるエンティティの作業記述子１０３を、「
現フレーム待ち行列番号」２０７によって指定されるフ
レーム待ち行列１１７中に更に入れる余地がないことを
示した場合は、そのエンティティの作業記述子１０３を
受けられる次のフレーム待ち行列１１７を探して、「間
隔」２０５の値を「現フレーム待ち行列番号」２０７に
加えて、作業記述子の受け入れの用意をする。もし加え
た結果として得られた番号がフレーム待ち行列１１７の
最大数よりも大きい場合は、余分を切り捨てる。

【００５０】次に、「規定数」２０３から「残数」を設
定する。「現フレーム待ち行列番号」２０７によって指
定されたフレーム待ち行列１１７の末尾に作業記述子１
０３を加え、これを示すために、そのフレーム待ち行列
１１７に対応する、フレーム待ち行列状態入力部分３１
１中の「テール」ポインタ３１５の値を更新する。「残
数」２０９の値を減らす。そして、そのフレーム待ち行
列状態入力部分３１１中の「カウント」を増やす。

【００５１】ここで次に、多重利用資源に作業記述子１
０３を供給するステップについて説明する。

【００５２】サーバ１２１は、現待ち行列状態情報部１
２３の制御の下に作動する。この現待ち行列状態情報部
１２３は、その詳細を図３に示すように、次の５つの情
報項目からなる。その１は「フレームサイズ」情報３０
２で、フレーム待ち行列１１７で表されるフレーム中の
スロットの数を示す。その２は「送付済み数」情報３０
３で、現フレーム待ち行列１１７で表されるフレームタ
イムの間に送られた作業記述子１０３の数を示す。

【００５３】その３は「最善努力標識」情報３０５で、
サーバ１２１が、現フレーム待ち行列１１７から作業記
述子１０３を取る代わりに最善努力待ち行列１１５から
作業記述子１０３を取るべきときに表示される。その４
は「次フレーム待ち行列標識」情報３０６で、サーバ１
２１が、次のフレーム待ち行列１１７から作業記述子１
０３を取るべきときに表示される。そして、その５は「
出力フレーム待ち行列番号」情報３０７で、サーバ１２
１が現に作業（サーブ）中のフレームのフレーム待ち行
列１１７の番号を示す。

【００５４】サーバ１２１が待ち行列１１９及び１１５
から作業記述子を出力するために用いる手法は、次に示
すステップによるエンドレス・ループである。まず、も
し「出力フレーム待ち行列番号」３０７によって指定さ
れたフレーム待ち行列１１７中に作業記述子１０３があ
り且つ、「送付済み数」３０３が「フレームサイズ」３
０２よりも少ない場合は、フレーム待ち行列１１７の先
頭の作業記述子１０３を取り除き、フレーム待ち行列状
態情報部１０８中の「カウント」３１７の数を１つ減ら
し、取り除いた作業記述子１０３を多重利用資源に供給
し、「送付済み数」３０３の数を１つ増やす。

【００５５】もし「出力フレーム待ち行列番号」３０７
によって指定されたフレーム待ち行列１１７中に作業記
述子１０３がなく且つ、「最善努力指標」３０５が表示
されていない場合は、更にもし「送付済み数」３０３が
「フレームサイズ」３０２よりも少ないなら、「最善努
力表示」３０５を表示し、そうでなければ、「次フレー
ム待ち行列標識」３０６を表示する。

【００５６】もし「最善努力表示」３０５が表示されて
いて、最善努力待ち行列１１５の先頭に作業記述子１０
３がある場合は、作業記述子１０３を多重利用資源に供
給し、「送付済み数」３０３の数を１つ増やす。もし「
送付済み数」３０３が「フレームサイズ」３０２に等し
いか又は、より多い場合は、「次フレーム待ち行列標識
」３０６を表示する。

【００５７】もし「最善努力表示」３０５が表示されて
いて、最善努力待ち行列１１５中に作業記述子１０３が
もうない場合は、「次フレーム待ち行列標識」３０６を
表示して、「送付済み数」３０３が「フレームサイズ」
３０２に等しくなるような十分な数の作業記述子を供給
するのに必要な時間、待つ。

【００５８】そして、もし「次フレーム待ち行列標識」
３０６が表示されている場合は、「出力フレーム待ち行
列番号」３０７を１つ増やし、もし必要なら超過数を切
り捨て、「最善努力標識」３０５をリセットし、「次フ
レーム待ち行列標識」３０６をリセットし、「送付済み
数」３０３をゼロ（０）にリセットする。

【００５９】資源の時分割多重利用化装置１０１の利点
は、或るフレーム待ち行列１１７中に作業記述子１０３
を入れるための「規定数」２０３の値が共に、「フレー
ムサイズ」３０２によって指定される作業記述子１０３
の数よりも少ない限り、１つのエンティティのレートを
、他のどのエンティティのレートにも影響を与えずに変
更できることである。

【００６０】次に、図４、図５、及び図６を参照して、
本発明の一実施例の詳細について述べる。この実施例は
、広帯域ＬＡＮ（企業内情報通信網）へのデータパケッ
トの送付に用いる場合における、本発明に基づく資源の
時分割多重利用化装置１０１の作動特性を試験するため
のプロトタイプとして製作したものである。

【００６１】本プロトタイプの製作には、周知のＣプロ
グラミング言語で作成したプログラムを使用し、このプ
ログラムのコンパイル及び実行には、モトローラ社（Ｍ
ｏｔｏｒｏｌａ，　Ｉｎｃ．）製の２５ＭＨｚ、ＭＣ６
８０２０マイクロプロセッサを用いた。このプロトタイ
プは、毎秒２０万個のパケットをＬＡＮに送る能力があ
った。

【００６２】図４に、本実施例における、データパケッ
ト４０１及び接続レート制御情報４１９に用いられるデ
ータ構造を示す。データパケット４０１は、作業記述子
１０３に該当する。データパケット４０１のフィールド
には次の６種類の情報が含まれる。その１は「次のパケ
ット」情報４０３で、連携リスト中の次のパケット４０
１を示すポインタである。

【００６３】その２は「宛先」情報４０５で、送付中の
パケット４０１の宛先を示す。この情報は又、本実施例
においては、エンティティ識別子１０５の役もする。　
　その３は「規定数」情報４０７で、或るフレーム待ち
行列１１７中に入れられる、「宛先」情報４０５を有す
るパケット４０１の数を示す。その４は「間隔」情報４
０９で、「宛先」４０５を有するパケット４０１のある
フレーム待ち行列の間の間隔を示す。その５は「最大数
」情報４１１で、フレーム待ち行列１１９中に存在を許
されるパケット４０１の最大数を示す。

【００６４】そして、その６は「レート形式」情報４１
３で、「宛先」４０５を有するパケット４０１が、レー
ト制御と最善努力とのどちらの形式の扱いを受けるかを
示す。これら４０７から４１３のフィールド全体で、接
続記述部４１７を構成し、パケット４０１を送信するデ
バイスと「宛先」４０５によって指定されるデバイスと
の間の接続がどのような扱いを受けるかを記述する。も
し「レート形式」４１３が最善努力を指定する場合は、
４０７から４１３のフィールドはもちろん無意味となる
。実際例においては、パケット４０１にはデータ又はデ
ータポインタのいずれかも含まれる。

【００６５】本実施例の、接続レート制御情報４１９は
、前に説明したレート情報部１０９の入力項目レート情
報部分２０１に対応する。サーバ１２１が現在パケット
ネットワーク上にパケット４０１を入れつつある各接続
ごとに、接続レート制御情報４１９がある。フィールド
４２３及び４３７を除いては、接続レート制御情報４１
９の情報は、機能的に、入力項目レート情報部分２０１
及びパケット４０１の詳細説明図中同一名称のものに対
応する。

【００６６】接続レート制御情報４１９の情報中、「次
接続レート制御情報」４２３は、連携リスト中、次の接
続レート制御情報構造を示すポインタである。又、「待
ち数」情報４３７は、現在フレーム待ち行列１１９で待
ち合わせ中の、「宛先」４０５を有するパケット４０１
の数を示す。

【００６７】本実施例に用いられるデータ構造の残りの
部分を図５に示す。プロトタイプにおいては、送られる
パケット４０１のストリームは、自由パケット待ち行列
５０１によってシミュレートされる。この自由パケット
待ち行列５０１は、パケット４０１の連携リストで、自
由リスト先頭部５０３が待ち行列中の最初のパケット４
０１を指し、自由リスト末尾部５０４が待ち行列中の最
後のパケット４０１を指している。

【００６８】本実施例においては、更に、前に述べたレ
ート情報部１０９を、符号５０５に示すような形で設け
ている。このレート情報部５０５は、パケット４０１か
ら「宛先」４０５を取って、「接続レート制御情報」４
１９のポインタである「接続レート制御情報ポインタ」
５１５を得るのに用いている。これには、「宛先」４０
５で指定される宛先への接続記述４１７を含む。ここで
用いた技術は、「宛先」４０５に対する接続レート制御
情報４１９を含む接続レート制御情報４１９のハッシュ
チェーンの位置指定のためにハッシュテーブルを用いる
標準的技術の１つである。

【００６９】最初のステップで、「宛先」４０５がハッ
シュ機能５０７に与えられ、そこでハッシュテーブル入
力項目番号５０９が生成される。ハッシュテーブル入力
項目番号５０９は、ハッシュテーブル５１１への指標で
、ハッシュテーブル５１１は、接続レート制御情報４１
９の連携リストのポインタの配列体である。

【００７０】「宛先」４０５に対する接続レート制御情
報４１９は、どれも接続レート制御情報４１９の連携リ
スト上にあり、「宛先」情報４０５からハッシュ機能５
０７によって生成されたハッシュテーブル入力項目番号
５０９を、ハッシュテーブル入力項目５１３により表示
される。もし「宛先」４０５に対する接続レート制御情
報４１９が連携リスト上にある場合は、その「接続レー
ト制御情報ポインタ」情報５１５が返される。

【００７１】レート情報部５０５に加えられた接続レー
ト制御情報４１９は、接続レート制御情報４１９の自由
リスト（図示しない）から取り除かれて、レート情報部
５０５においてもはや必要とされなくなったときにその
自由リストに返される。

【００７２】キャッシュ５１７は、引き続いて送られる
パケット４０１においては、しばしば「宛先」４０５が
同じであることを利用する。すなわち、「宛先」４０５
で、その「宛先」についての接続レート制御情報４１９
がレート情報部５０５中に位置した「宛先」のうちの最
も後の「宛先」４０５（「最後の宛先」５１９として）
を、接続レート制御情報４１９用の「最後の接続レート
制御情報ポインタ」５２１と共に、キャッシュ５１７中
に保持する。もし次のパケット４０１の「宛先」４０５
がこれと同じ場合は、接続レート制御情報４１９のポイ
ンタがキャッシュ５１７から直接得られる。

【００７３】本実施例における、フレーム待ち行列状態
情報部１０８に対応する部分のデータ構造は、図３に示
す形式と全く同一である。本実施例における先頭部３１
３は、パケット４０１の連携リスト中の最初のパケット
に該当する。又、末尾部３１５は、連携リスト中の最後
のパケット４０１に該当する。

【００７４】図６は、プロトタイプであるこの実施例の
動作を示す流れ図６０１である。ステップ６０３におけ
るプロセス開始後、ステップ６０５において、パケット
４０１が初期化される。この初期化によって、パケット
４０１中の４０５から４１３までのフィールドが、パケ
ットの混合トラフィック状態をシミュレートするように
セットされる。或る種の初期化においては、乱数から生
成された整数を用いて得られた値が、「宛先」４０５、
「規定数」４０７、及び「間隔」４０９、の各フィール
ドの設定に使用される。

【００７５】次のステップ６０７において、種々のデー
タ構造が初期化される。全てのパケット４０１が自由リ
スト５０１に入れられ、全ての接続レート制御情報４１
９がこれら情報構造に関する自由リストに入れられる。 そして、レート情報部５０５、フレーム待ち行列状態３
０５及び現待ち行列状態１２３の構造が、接続レート制
御情報４１９の全ての待ち行列及び全てのフレーム待ち
行列１１７が空きでプロセスがフレーム待ち行列１１７
（０）から始まるような形に初期化される。

【００７６】一旦初期化が完了すると、ループ６２１の
実行が開始され、希望に応じて継続される。図６に示す
ように、ループ６２１のステップ６０９からステップ６
１７までが、待ち行列管理体１０７の動作に対応し、ス
テップ６１９が、サーバ１２１の動作に該当する。まず
、待ち行列管理体１０７の動作から説明すると、最初の
ステップ６０９において、自由リスト５０１からパケッ
ト４０１が読み出される。実際例においては、パケット
４０１は、装置１０１によって受信されたパケット用の
入力待ち行列から来ることになる。

【００７７】次のステップ６１１において、パケット４
０１の「レート形式」フィールド４１３から、このパケ
ットが必要とするサービス形式が判断される。もし「レ
ート形式」フィールド４１３が最善努力サービスを指定
している場合、パケット４０１は最善努力待ち行列１１
５中に入れられる。もし「レート形式」フィールド４１
３がレート制御力サービスを指定している場合には、次
のステップ６１３において、パケット４０１の「宛先」
４０５に対する接続レート制御情報４１９が調査される
。

【００７８】まず、「宛先」４０５がキャッシュ５１７
中の「最後の宛先」５１９と比較される。もし両者が同
一である場合は、最後の接続レート制御情報ポインタ５
２１に、「宛先」４０５に対する接続レート制御情報４
１９のポインタ５１５が含まれている。もし両者が同一
でない場合には、上に述べたように、「最後の宛先」５
１９がハッシュ機能５０７に供給される。

【００７９】もしレート情報部５０５中に「宛先」４０
５に対する接続レート制御情報４１９がある場合は、パ
ケット４０１のフィールド「規定数」４０７、「間隔」
４０９、及び「最大数」４１１が「宛先」４０５に対す
る接続レート制御情報４１９の対応するフィールド４２
５、４２７、及び４２９にコピーされる。この手順によ
って、同一宛先であっても別の接続については、レート
を別の値に制御することが可能となる。

【００８０】もし「宛先」４０５に対する接続レート制
御情報４１９がない場合は、接続レート制御情報４１９
は自由リストから取られて、接続レート制御情報４１９
の適切な連携リストに入れられる。そして、パケット４
０１の４０３から４１３までのフィールドの情報が、新
しい接続レート制御情報４１９の、対応するフィールド
４２１、４２５、から４２９まで、及び４３５にコピー
される。

【００８１】サービスを行う際のレートを判断するのに
必要な情報は、本実施例においてはパケット４０１に含
まれているが、別の実施例ではこの情報を実際のパケッ
ト４０１から分離することも可能である。そのような実
施例においては、接続の際のレートを示すメッセージを
パケット４０１から分けてパケット４０１の前に入れる
。その場合、接続レート制御情報４１９中の関連フィー
ルドは、メッセージ中の情報を用いてセットする。

【００８２】更に、待ち行列管理体１０７が、平均時間
長さ及びジッタ平均時間長さにの間に送られるパケット
４０１の数として表現されるレート情報を、サーバ１２
１がパケット４０１を希望レートで送るようにするため
に必要な情報である「規定数」４２５及び「間隔」４２
７の値に翻訳する。

【００８３】一旦「宛先」４０５用の接続レート制御情
報４１９が見いだされ、又は生成されると、次のステッ
プ６１７において、パケット４０１が適切なフレーム待
ち行列１１７中に入れられる。この処理を行うために用
いられる手法は、図２及び図３に関連して前に説明した
手法である。

【００８４】それに加えて、接続レート制御情報４１９
が、「待ち数」フィールド４３７において、フレーム待
ち行列１１９中に既にあるパケット４０１の数の動きを
常に把握する。もし待ち合わせしているパケットの数が
フィールド４２９に指定されている最大数に等しい場合
、パケット４０１はフレーム待ち行列１１７には入れら
れず、代わりに自由リスト５０１に戻される。実際例に
おいては、装置１０１がこの状態に応答して、パケット
４０１の伝送速度を下げるよう要請するメッセージをパ
ケット４０１の発送源に送る。

【００８５】パケット４０１が最善努力待ち行列１１５
又は適切なフレーム待ち行列１１７のいずれかに入れら
れた後、もし出力されるパケット４０１がある場合は、
次のステップ６１９において、パケット４０１が現フレ
ーム待ち行列１１７、又は最善努力待ち行列１１５から
出力される。もし出力されるパケット４０１がない場合
は、現フレーム待ち行列１１７に対応するフレームのフ
レームタイムが満了するまで出力はない。パケット４０
１の出力に用いる手法は、前に説明して手法と同じであ
る。

【００８６】更に、レート制御された接続に対するパケ
ットが１つ出力されるときは、パケット４０１の「宛先
」４０５に対する接続レート制御情報４１９の「待ち数
」フィールド４１９の値が１つ減らされる。本実施例に
おいては、パケット４０１が出力されると、自由リスト
５０１に戻される。

【００８７】流れ図６０１から判るように、ループ６２
１を１回実行するごとに、パケット４０１が最善努力待
ち行列１１５又はフレーム待ち行列１１７のいずれかに
入れられる。しかし、ループ６２１の実行に際してパケ
ットが最善努力待ち行列１１５又はフレーム待ち行列１
１７から出力されるのは、現フレーム待ち行列１１７又
は最善努力待ち行列１１５にパケットがあるときだけで
ある。すなわち、ループ６２１を実行することによって
、結果的に、フレーム待ち行列１１７にパケット４０１
が徐々に増加して来る。

【００８８】本実施例においては、フレーム待ち行列が
５０個あり、各フレームにはスロットが１００個あった
。又、接続レート制御情報は６０個で、レート情報部５
０５の接続は６０個まで可能、パケット４０１は１００
０個であった。

【００８９】実際例においては、待ち行列管理体１０７
及びサーバ１２１は同一のループの一部をなすのでなく
、むしろ、レート情報部１０９、フレーム待ち行列状態
情報部１０８、及び待ち行列１１５及び１１９を共用は
するが別の存在である。そのような実施例においては、
待ち行列管理体１０７は、作業記述子１０３を受けて待
ち行列１１５及び１１９に入れるプロセスであり、サー
バ１２１は、待ち行列１１９及び１１５から作業記述子
１０３を取って多重利用資源に供給する別のプロセスで
ある。いくつかの実際例においては、待ち行列管理体１
０７とサーバ１２１とは、別のハードウエア上で作動す
る。

【００９０】以上、複数のエンティティに対して制御さ
れたレートで資源を多重利用させる装置及び方法に関す
る発明を、プロトタイプの実施例について、通常の当業
者を対象に説明開示を行ってきた。本プロトタイプ実施
例は、本発明の原則を説明する目的に最適のものと確信
するが、プロトタイプであるため、実際例とは異なるこ
とがあり得ることは上記説明の中でも述べた通りである
。

【００９１】このような差異はフレーム待ち行列１１７
に関しても起こり得る。フレーム待ち行列１１７におい
て待ち行列を用いることにより、或るエンティティの作
業記述子１０３を、これら作業記述子１０３が装置１０
１に受け入れられたのと同じ順序で多重利用資源に供給
できる。しかし、レート制御付きサービスで、作業記述
子１０３が受け入れられた順序に作業記述子１０３を供
給しないサービスは、待ち行列以外の構造を有するもの
もある。

【００９２】更に、他の実施例においては、フレーム待
ち行列１１７を連携リスト以外の形で設けることもあり
得る。例としては、先頭と末尾とにポインタを有するバ
ッファである。最後に、他の実施例においては、フレー
ムが異なればフレームタイムも異なることがあり得る。 その場合、平均時間長さは、フレームタイムの合計であ
り、フレームに付随するフレーム待ち行列は、その最大
長が異なることもあり得る。

【００９３】他の実施例において差異が生じることが考
えられる領域としては、この他に、フレーム待ち行列１
１７中の作業記述子１０３の密度制御、レート情報部の
実際構造、及び最善努力待ち行列１１５の実際構造が考
えられる。「規定数」及び「間隔」を用いると密度制御
を特に簡単で効果的に行うことができるが、これ以外の
技術を使用することも可能である。

【００９４】レート情報部１０９の実際構造に関しては
、エンティティ認識子１０５によってアクセス可能なレ
ート情報リストの得られる技術であれば、全て利用可能
である。最善努力待ち行列については、他の方式では、
複数の最善努力待ち行列１１５を設けて、サーバ１２１
がこれら複数の最善努力待ち行列を回転円筒式に順次扱
う構造もあり得る。

【００９５】最後に、本実施例においては、データパケ
ットの長さを固定長としたが、他の実施例では可変長パ
ケットとすることもできる。そのような実施例の場合は
、「規定数」２０３、「残数」２０９、「フレームサイ
ズ」３０２、「送付済み数」３０３、「カウント」３１
７、及び「制限値」３１９、の値は、パケットの数の代
わりにバイト数を指定することになる。

【００９６】以上の説明は、本発明の一実施例に関する
もので、この技術分野の当業者であれば、本発明の種々
の変形例を考え得るが、それらはいずれも本発明の技術
的範囲に包含される。

【００９７】尚、特許請求の範囲に記載した参照番号は
発明の容易な理解のためで、その技術的範囲を制限する
よう解釈されるべきではない。

【００９８】

【発明の効果】以上述べたごとく、本発明によれば、作
業記述子を待ち行列に入れ、待ち行列管理体と、窓口機
構であるサーバとを設けて、資源の多重利用化装置及び
方法を構成しているので、作業記述子の待ち行列状態を
、アクセスレート制御を要するもの及び要しないものの
両方について、常に把握し、作業記述子、すなわち作業
を、資源に対して、常に必要に応じた最適状態で供給で
きる。

【００９９】したがって、資源の実時間利用、すなわち
資源への制御されたアクセスが必要な作業を有するエン
ティティは、本発明により、常に均一且つ適切なアクセ
スが得られ、従来技術におけるアクセスの不具合からく
る伝送データのオーバフロー、消失等のトラブルがなく
なり、安定した円滑な処理が可能となる。

【図面の簡単な説明】

【図１】本発明の全体を示す概観説明図である。

【図２】待ち行列への作業の割当制御に用いられる値の
説明図である。

【図３】資源への作業の付与の制御に用いられる値の説
明図である。

【図４】実施例に用いられるデータ構造の説明図である
。

【図５】実施例に用いられるデータ構造の別の説明図で
ある。

【図６】実施例の動作を説明する流れ図である。

【符号の説明】

１０１　　資源の時分割多重利用化装置１０３　　作業
記述子 １０５　　エンティティ識別子（ＥＩＤ）１０７　　待
ち行列管理体 １０８　　フレーム待ち行列状態情報部１０９　　レー
ト情報部 １１５　　最善努力待ち行列 １１７（０）〜１１７（ｎ）　　フレーム待ち行列１１
９　　フレーム待ち行列 １２１　　サーバ（資源に対する作業記述子供給窓口機
構） １２３　　現待ち行列状態情報部 ２０１　　入力項目レート情報部分 ２０３　　「規定数」情報 ２０５　　「間隔」情報 ２０７　　「現フレーム待ち行列番号」情報２０９　　
「残数」情報 ３０２　　「フレームサイズ」情報 ３０３　　「送付済み数」情報 ３０５　　「最善努力標識」情報 ３０６　　「次フレーム待ち行列標識」情報３０７　　
「出力フレーム待ち行列番号」情報３１１　　フレーム
待ち行列状態入力部分３１３　　「先頭部」情報 ３１５　　「末尾部」情報 ３１７　　「カウント」情報 ３１９　　「制限値」情報 ４０１　　データパケット ４０３　　「次のパケット」情報 ４０５　　「宛先」情報 ４０７、４２５　　「規定数」情報 ４０９、４２７　　「間隔」情報 ４１１、４２９　　「最大数」情報 ４１３　　「レート形式」情報 ４１７　　接続記述部 ４１９　　接続レート制御情報 ４２３　　「次接続レート制御情報」 ４３７　　「待ち数」情報 ５０１　　自由パケット待ち行列 ５０３　　自由リスト先頭部 ５０４　　自由リスト末尾部 ５０５　　レート情報部 ５０７　　ハッシュ機能 ５０９　　ハッシュテーブル入力項目番号５１１　　ハ
ッシュテーブル ５１３　　ハッシュテーブル入力項目 ５１５　　接続レート制御情報ポインタ５１７　　キャ
ッシュ ５１９　　最後の宛先

Claims (10)

【特許請求の範囲】
1. 【請求項１】　　複数の時間長さの間、資源を、エンテ
   ィティから与えられる複数の作業に対して時分割多重利
   用するための資源の時分割多重利用化装置において、前
   記の与えられた作業を記述する作業記述子セット（１１
   ７）と、前記の複数の時間長さからなる１つの時間長さ
   セットの間、前記の作業記述子セットの各々から、前記
   の作業記述子セットの中の作業記述子を、前記の資源に
   、規則的な仕方で供給するためのサーバ（１２１）と、
   前記の作業記述子を受けとり、前記の１つ以上のエンテ
   ィティのうちの或る１つのエンティティから与えられた
   作業に対する前記の作業記述子を前記の作業記述子セッ
   ト内に配置する手段（１０７）とからなり、前記のサー
   バが前記の作業記述子を前記の規則的な仕方で供給する
   ことによって、前記の資源が、前記の或る１つのエンテ
   ィティから与えられた作業を、制御されたレートで実施
   することを特徴とする資源の時分割多重利用化装置。
2. 【請求項２】　　前記の作業記述子を受けとり配置する
   手段が、前記の或る１つのエンティティに対する前記の
   作業記述子を前記の作業記述子セットに配置するに際し
   、前記の或る１つのエンティティに対する前記の作業記
   述子の、前記の作業記述子セットにおける密度制御が行
   われるように配置することを特徴とする請求項１の装置
   。
3. 【請求項３】　　前記の密度制御が、前記の作業記述子
   セットのうちの或る１つの作業記述子セットにおける、
   前記の或る１つのエンティティに対する前記の作業記述
   子の数を制限することと、前記の或る１つのエンティテ
   ィに対する前記の作業記述子を含む作業記述子セットを
   、前記の或る１つのエンティティに対する前記の作業記
   述子を含まない固定数の作業記述子セットから分離する
   こととによって行われる、ことを特徴とする請求項２の
   装置。
4. 【請求項４】　　作業記述子の最善努力セット（１１５
   ）を更に有し、前記のサーバが前記の１つ以上の作業記
   述子ットから作業記述子を供給しないときには、前記の
   １つの時間長さセットの間、作業記述子の最善努力セッ
   トから作業記述子を供給することを特徴とする請求項１
   の装置。
5. 【請求項５】　　前記の１つの時間長さセットが、サブ
   セットに再分され、前記のサーバが、前記の１つの時間
   長さセットのサブセットのうちの１つの所定サブセット
   の間、前記の或る１つの作業記述子セットから作業記述
   子を供給することを特徴とする請求項１の装置。
6. 【請求項６】　　複数の時間長さの間、資源を、エンテ
   ィティから与えられる複数の作業に対して時分割多重利
   用するための資源の時分割多重利用化方法において、前
   記のエンティティのうちの或る１つのエンティティから
   与えられた作業を記述する作業記述子を、作業記述子セ
   ット内に、第１の規則的な仕方で配置する過程と、前記
   の複数の時間長さからなる１つの時間長さセットの間、
   前記の作業記述子セットの中の作業記述子を前記の資源
   に第２の規則的な仕方で供給する過程とからなり、前記
   の第１の規則的な仕方は、前記の作業記述子を前記第２
   の規則的な仕方で前記の資源に供給することによって、
   前記の資源が、前記の或る１つのエンティティから与え
   られた作業を、制御されたレートで実施するような仕方
   であることを特徴とする資源の時分割多重利用化方法。
7. 【請求項７】　　前記作業記述子を配置する過程が、前
   記の或る１つのエンティティに対する前記の作業記述子
   の、前記の作業記述子セットにおける密度を制御するこ
   とを特徴とする請求項６の方法。
8. 【請求項８】　　前記作業記述子を配置する過程が、前
   記の作業記述子セットのうちの或る１つの作業記述子セ
   ット内に、前記の或る１つのエンティティに対する前記
   の作業記述子を、所定の最大数以下の範囲で配置する過
   程と、前記の作業記述子セットのうちの１つの作業記述
   子セット内に、前記の或る１つのエンティティに対する
   前記の作業記述子を再配置する前に、前記の作業記述子
   セットのうちの固定数の作業記述子セットをスキップす
   る過程とからなることを特徴とする請求項６の方法。
9. 【請求項９】　　制御されたレートを要しないエンティ
   ティに対する作業記述子を、作業記述子の最善努力セッ
   ト内に置く過程を更に有し、前記作業記述子セットから
   作業記述子を供給する過程が、前記の作業記述子セット
   から作業記述子が供給されないときには、作業記述子の
   最善努力セットから作業記述子を供給することを特徴と
   する請求項６の方法。
10. 【請求項１０】　　前記作業記述子セットから作業記述
    子を供給する過程が、前記作業記述子セットの各々につ
    いて、その中の作業記述子を、前記の１つの時間長さセ
    ットのサブセットのうちの１つの所定サブセットの間、
    前記資源に供給する過程を含むことを特徴とする請求項
    ６の方法。