JPH09168031A - パケット送出に関する実時間スケジューリング方法 - Google Patents

Abstract

(57)【要約】 【課題】 一括送信番組と非一括送信番組とが混在する
番組集合のパケットを各番組ごとに決められた周期で送
出するようにフレームに割り当てるスケジューリングを
実時間で行う。 【解決手段】 番組集合を一括送信番組と非一括送信番
組とに分割し、一括送信番組の集合についてその割当要
求率が１以下になりかつ番組当り一括で送信すべきパケ
ット数の整数倍となる最小のパケット数を一括送信番組
用サブフレームの送信容量とし、フレームの送信容量の
残りを非一括送信番組用のサブフレームの送信容量とし
て設定し、フレームを送出する各時刻ごとにＥＤＦアル
ゴリズムに従って一括送信番組のパケットを一括送信番
組用サブフレームに割り当てるとともに非一括送信番組
のパケットを非一括送信番組用サブフレームに割り当て
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、パケット送出のた
めのスケジューリングを実時間で行う方法に関する。

【０００２】

【従来の技術】ラジオの番組放送システムにおいて、ラ
ジオ局はある周波数帯を使って放送番組の音声情報や文
字情報を送出する。同一周波数帯で複数の番組を放送す
る場合には、各番組情報はパケットと呼ばれる送信単位
となる一定量の情報に分割され、多重伝送される。各放
送番組は所定の周期で所定のパケット数の情報が送出さ
れなければならず、複数の番組から集められたパケット
は一定のパケット数分の送信容量をもつフレームに収容
されて定期的に送出される。ここに各番組のパケットを
その送出期限に間に合うようにフレームに割り当てるス
ケジューリング問題が生じる。パケット送出に関するス
ケジューリング問題は、タスクを期限に間に合うように
資源に割り当てるスケジューリング問題と同一視でき
る。タスクスケジューリングについては、タスクの性質
が極めて限定されている場合、またはタスクの性質を一
般化した場合の割当アルゴリズムはいろいろ研究されて
いる。しかしパケット送出のスケジューリング問題に公
知のタスクスケジューリング手法を適用しようとする
と、前者の場合タスクの性質が限定され過ぎ、また後者
の場合には計算量が多くなり、実時間での適用は難し
い。

【０００３】なおこの種の技術として関連するものに
は、例えば「ＳｃｈｅｄｕｌｉｎｇＡｌｇｏｒｉｔｈｍ
ｓ ｆｏｒ Ｈａｒｄ Ｒｅａｌ−ｔｉｍｅ Ｓｙｓｔ
ｅｍｓ ： Ａ Ｂｒｉｅｆ Ｓｕｒｖｅｙ」（ＴＵＴ
ＯＲＩＡＬ Ｈａｒｄ Ｒｅａｌ−Ｔｉｍｅ Ｓｙｓｔ
ｅｍｓ ｐｐ．１５０−１７３， ＩＥＥＥ ＣＯＭＰ
ＵＴＥＲ ＳＯＣＩＥＴＹ ＰＲＥＳＳ）等がある。

【０００４】

【発明が解決しようとする課題】実時間で行うパケット
送出のスケジューリングにおいては、（１）各番組の送
出期限に間に合うようにパケット送出できるか否かを判
定できること（２）フレームに対するパケットの割当効
率が高いものであること（３）パケット送出遅延が発生
したときの制御ができること（４）番組集合が変化した
とき対応できること、の要件を実時間で満足する必要が
ある。番組集合は、１周期当りのパケット数を１つのフ
レームに割り当てて一括で送信すべき一括送信番組と、
１周期当りのパケット数を複数のフレームに分散して送
信可能な非一括送信番組とに分類できる。すべての番組
が非一括送信番組である場合には、上記（１）から
（４）までの要求に答えるため、Ｅａｒｌｉｅｓｔ Ｄ
ｅａｄｌｉｎｅ Ｆｉｒｓｔ（ＥＤＦ）と呼ばれる割当
アルゴリズムを適用することができる。しかし番組集合
に一括送信番組が混在する場合には、上記（１）から
（４）までの要求に適応する割当アルゴリズムは知られ
ていない。

【０００５】本発明の目的は、番組集合に一括送信番組
が混在する場合のパケット送出に関するスケジューリン
グを実時間で行う方法を提供することにある。

【０００６】

【課題を解決するための手段】本発明は、番組集合を一
括送信番組と非一括送信番組とに分割し、一括送信番組
の集合についてその割当要求率が１以下になりかつ番組
当り一括で送信すべきパケット数の整数倍となる最小の
パケット数をこの一括送信番組集合についてのサブフレ
ームの送信容量とし、フレームの送信容量から一括送信
番組用のサブフレームの送信容量を除いた残りを非一括
送信番組用のサブフレームの送信容量として設定し、フ
レームを送出する各時刻ごとにＥＤＦアルゴリズムに従
って、一括送信番組のパケットを一括送信番組用サブフ
レームに割り当てるとともに非一括送信番組のパケット
を非一括送信番組用サブフレームに割り当てるパケット
送出に関する実時間スケジューリング方法を特徴とす
る。

【０００７】番組集合は一括送信番組と非一括送信番組
とから構成されるが、仮にすべての番組が非一括送信番
組である番組集合を考えると、ＥＤＦアルゴリズムは、
「パケットのフレームへの割当要求率が１以下である番
組集合を期限に遅れなしで割り当て可能」であることを
保証する。このため番組集合が非一括送信番組である場
合には、パケットの割当要求率の計算のみで各番組の送
出期限に間に合うようにパケット送出できるか否かを判
定することができ、この判定に要する計算は実時間に行
なうことが可能である。本発明は、一括送信番組の１周
期当りのパケット数（１ページ分のパケット数）が一定
であるので、１ページ分のパケット数を単位とすると、
一括送信番組を非一括送信可能な番組と考えることがで
き、注目する番組集合のパケット割当にＥＤＦを適用し
上記の判定を実時間に行うものである。これによって一
括送信番組が期限に遅れなしでパケット割当可能である
ことが保証される。非一括送信番組については、一括送
信番組用サブフレームに一括送信番組のパケットを割り
当てない空きが生じたとき、非一括送信番組の集合のう
ち一部のパケットを割り当てることによってフレームに
対するパケットの割当効率を上げるとともに非一括送信
番組のパケット送出を早める。非一括送信番組のパケッ
トを一括送信番組用サブフレームと非一括送信番組用サ
ブフレームのいずれに割り当てる場合にも、それぞれの
サブフレームについてパケット割当要求率を計算するこ
とによって番組のパケット送出が期限に遅れなしで可能
か否かの判定ができる。非一括送信番組に優先度を設定
すれば、パケット割当要求率の計算によって優先度の高
い非一括送信番組の期限に遅れなしを保証することがで
きる。優先度が低くパケット送出遅延が発生する非一括
送信番組については、その周期又はパケット数／ページ
を変更して対応するように制御する。

【０００８】パケット送出をスケジューリングするスケ
ジューラは、各番組の属性（周期及びパケット数／ペー
ジ）に応じて各サブフレームの送信容量を設定する前処
理モジュールと、フレームの送出時刻に合わせて起動さ
れ実時間でパケットのフレームへの割当を行うパケット
割当モジュールとから構成される。前処理モジュールで
初期設定した後、番組集合が変わらない限りパケット割
当モジュールを繰り返し実行すればよい。番組集合が変
化したとき前処理モジュールから実行するが、計算量が
少なく実時間での適用が可能である。

【０００９】

【発明の実施の形態】

（１）はじめに 本実施形態では、ラジオの番組放送システムにおいて、
ラジオ局が同一周波数帯で複数の番組を放送する場合に
各番組の情報を送出するためのスケジューリングの問題
をとりあげる。各番組は決められた送信期限までに所定
量の情報が送出されねばならない。まず使用する用語に
ついて説明する。パケットとは、送信単位となる一定量
の情報である。各番組は周期的な送信期限までに送信し
なければならないパケット数が決められている。ページ
とは、各番組の１周期当りの送信パケット数をいう。フ
レームとは、一定のパケット数分の送信容量をもち定期
的に送信される送信単位であり、各番組のパケットが集
められて１つのフレームを構成する。一括送信番組と
は、１ページ分のパケットを一つのフレームに割り当て
て一括で送信しなければならないような番組をいう。非
一括送信番組とは、１ページ分のパケットをいくつかの
フレームに分けて分割送信してもよいような番組をい
う。番組集合とは、送信の対象となる番組の全体であ
り、本実施形態では一括送信番組と非一括送信番組とか
ら構成される。本実施形態では、このような番組集合に
ついて、フレームという送信容量の制約の下で各番組の
送信周期に間に合うように、どのような順番で各時刻に
どれだけのパケットをフレームに割り当てるかを決定す
るスケジューリングの問題を解決するものである。

【００１０】図３は、番組集合とフレームの事例を示す
図である。番組集合は１０個の番組から成り、一括送信
番組Ａ１〜Ａ４と非一括送信番組Ｂ１〜Ｂ６とから構成
される。番組Ａ１〜Ａ４は一括送信番組であり、１つの
フレームにそれぞれ２１パケットずつ割り当てねばなら
ない。フレームは９５パケットの容量をもち、１秒に１
回送信するものとする。なおパケットの内容は固定長の
ディジタル化された音声情報であり、文字情報を含んで
いてもよい。

【００１１】図４は、本発明を適用するパケット送出装
置の構成を示す図である。番組入力装置１は各番組の情
報を入力する端末装置である。送出制御装置２は番組入
力装置１から入力された番組情報をパケットに分割し、
各番組の優先順位などの情報を基にしてパケットをフレ
ームに割り当てる。スケジューラ３は本発明のスケジュ
ーリング方式を適用する装置であり、送出制御装置２が
行うパケット割り当ての処理を制御する。スケジューラ
３はマイクロプロセッサのような計算装置と関連する記
憶装置によって実現される。番組送出装置４はパケット
が割り当てられたフレームを送出する装置である。

【００１２】図５は、パケット割当の基本となるＥａｒ
ｌｉｅｓｔ Ｄｅａｄｌｉｎｅ Ｆｉｒｓｔ（ＥＤＦ）
と呼ばれるアルゴリズムを示すフローチャートである。
このフローチャートは、１ページ分のパケット数が均一
な番組集合をフレームに割り当てるときのＥＤＦアルゴ
リズムを示す。まずフレームが送出される時刻につい
て、送信要求のあった各番組のパケット数のうちまだ送
信されていないパケット数をそれぞれ未処理パケット数
に設定し、フレームの割当パケット数を０に設定する
（ステップ１１）。未処理パケット数が０でない番組が
あれば（ステップ１２ＹＥＳ）、未処理パケット数が０
でない番組のうち次のフレーム送出時刻から次の送出周
期までの時間が最も短い番組を選択する（ステップ１
３）。該当する番組が複数ある場合には、いずれか１つ
の番組を選択する。次に選択した番組についてフレーム
の空き容量を越えない範囲でできるだけ多くのパケット
数をフレームに割り当てる（ステップ１４）。次に割り
当てたパケット数を割当パケット数に加算し、この番組
の未処理パケット数から割り当てたパケット数を減算す
る（ステップ１５）。最後にフレームが満杯か否かを判
定し、フレームが満杯でなければ（ステップ１６Ｎ
Ｏ）、ステップ１２に戻って処理を続行する。未処理パ
ケット数が０でない番組がなくなったとき（ステップ１
２ＮＯ）、又はフレームが満杯のとき（ステップ１６Ｙ
ＥＳ）、処理を終了する。送出制御装置２は、割当の済
んだパケットをフレームに格納する。さらに次のフレー
ム送出時刻についてステップ１１からの処理を繰り返
す。

【００１３】ＥＤＦアルゴリズムは、各番組が周期的な
送信期限をもつ非一括送信番組である場合に「パケット
のフレームへの割当要求率が１以下である番組集合を期
限に遅れなしで割当可能」であることが証明されてい
る。ここでパケット数Ｒの送信容量をもつフレームへの
番組集合の割当要求率とは、この番組集合に含まれる番
組Ｐ_i（ｉ＝１，２，…ｍであり、ｍは番組集合に含ま
れる番組数）の１ページ分のパケット数ＰＰ_i、周期長
（秒）をＰＴ_iとしたとき Σ（ＰＰ_i÷ＰＴ_i÷Ｒ） （式１） である。ここでΣはｉが１からｍまでについて合計する
ことを示す。

【００１４】上記の条件によれば、パケットの割当要求
率の計算のみで送信期限に遅れなしで割当可能かどうか
の判定ができる。この判定に要する計算は、実時間に行
うことが可能である。

【００１５】（２）第１の実施形態 図１は、第１の実施形態の概略を説明する図である。ま
ず番組集合を一括送信番組と非一括送信番組とに分割す
る。次に９５パケットの送信容量をもつフレームを一括
送信番組用サブフレームと非一括送信番組用サブフレー
ムに分割する。ここでサブフレームとは、フレームの一
部であり、パケット数で計数される送信容量をもつフレ
ーム内の領域である。次に一括送信番組は一括送信番組
用サブフレームに割り当て、非一括送信番組は非一括送
信番組用サブフレームに割り当てる。

【００１６】図２は、第１の実施形態をとるスケジュー
ラ３の処理の流れを示すフローチャートである。スケジ
ューラ３は大きく前処理モジュールとパケット割当モジ
ュールに分かれる。図２でステップ２１及び２２が前処
理モジュール、ステップ２３〜２５がパケット割当モジ
ュールに含まれる。まず番組集合を一括送信番組の集合
と非一括送信番組の集合とに分割する（ステップ２
１）。次に分割したそれぞれの番組集合に割り当てるサ
ブフレームの送信容量を求める（ステップ２２）。まず
一括送信番組集合について、その割当要求率が１以下に
なりかつ一括送信番組集合内の番組の１ページ分のパケ
ット数の整数倍となる最小のパケット数を求め、これを
一括送信番組集合のサブフレームの送信容量とする。つ
まり（式１）のパケット数Ｒを変数とし、「一括送信番
組について（式１）の値を加え合わせたものが１以下で
ある」という不等式を「Ｒは一括送信番組集合の１ペー
ジ分のパケット数（本実施形態では２１）の整数倍とな
るできるだけ小さな整数」という条件の下で解き、Ｒの
数を決定する。本実施形態ではこの不等式は次のように
なる。 ２１÷（３×Ｒ）＋２１×３÷（４×Ｒ）≦１ ただしＲは２１の整数倍となる最小の整数である。Ｒを
計算すると４２となり、これが一括送信番組集合のサブ
フレームの送信容量となる。次にフレームの送信容量９
５パケットから一括送信番組集合のサブフレームの送信
容量４２パケットを減じた５３パケットを非一括送信番
組集合のサブフレームの送信容量とする。最初のフレー
ム送出時刻に達したとき（ステップ２３ＹＥＳ）、スケ
ジューラ３は上記のＥＤＦアルゴリズムに従って一括送
信番組用のサブフレームに一括送信番組を割り当てる
（ステップ２４）。各番組の情報は１ページずつ割り当
てられる。次に上記のＥＤＦアルゴリズムに従って非一
括送信番組用のサブフレームに非一括送信番組を割り当
てて（ステップ２５）、ステップ２３に戻る。なお非一
括送信番組が期限に遅れなしで非一括送信番組用のサブ
フレームに割り当て可能であるためには非一括送信パケ
ットの非一括送信番組用のサブフレームへの割当要求率
が１以下である必要がある。

【００１７】上述したように、ＥＤＦアルゴリズムは、
各番組が周期的な非一括送信番組であるという条件の下
でパケットの割当要求率のみの計算で割当期限に遅れな
しでスケジューリングできるかどうかを判定ができるう
え、要求率が１以下であれば必ず期限を守る割当を行う
ことができるため、効率的な実時間スケジューリングに
適している。第１の実施形態では各番組が周期的な非一
括送信番組であるという条件が成り立たないため、番組
集合を一括送信番組と非一括送信番組に分割し、それぞ
れにサブフレームを割り当てることによりＥＤＦを適用
可能にしている。

【００１８】（３）第２の実施形態 第１の実施形態では、一括送信番組集合に対して一括送
信番組用サブフレームを割り当てているが、一括送信番
組は２１パケットを単位にしてフレームへ割り当てなけ
ればならず、非一括送信番組が１パケットを単位にして
フレームへ割り当てるのに比べてサブフレームへの割当
効率が低下する場合が生じる。第２の実施形態は非一括
送信番組の一部を一括送信番組用サブフレームに割り当
てることによってフレームへの割当効率を上げるもので
ある。

【００１９】図６は、第２の実施形態の概略を説明する
図である。まず番組集合を一括送信番組と非一括送信番
組とに分割し、フレームを一括送信番組用サブフレーム
と非一括送信番組用サブフレームに分割する。次に非一
括送信番組の一部を選び、一括送信番組に補充して一括
送信番組用サブフレームに割り当てる。ただし非一括送
信番組の一部として選んだ番組集合は、一括送信番組の
１ページ分のパケット数（２１パケット）の整数倍で同
じ周期のパケット集合となるように選ぶ。残りの非一括
送信番組は非一括送信番組用サブフレームに割り当て
る。

【００２０】図７は、第２の実施形態をとるスケジュー
ラ３の処理の流れを示すフローチャートである。図でス
テップ３１〜３４が前処理モジュールに含まれ、ステッ
プ３５がパケット割当モジュールに含まれる。まずステ
ップ２１と同じく、番組集合を一括送信番組の集合と非
一括送信番組の集合とに分割する（ステップ３１）。次
に非一括送信番組Ｂ１〜Ｂ６の各Ｂ_j（ｊは１から６ま
での整数）から一括送信番組用サブフレームに補充でき
るパケット数を決定する（ステップ３２）。一括送信番
組のサブフレームへの割当要求率をＸとし、Ｐ_Aを一括
送信番組の１ページ分のパケット数（本実施形態では２
１）、Ｒ_Aを一括送信番組用サブフレームの送信容量と
し、Ｒ_Bを非一括送信番組用サブフレームの送信容量と
する。また非一括送信番組Ｂ_jの１ページ分のパケット
数をＰＢ_j、周期の長さをＴＢ_jとする。このとき整数Ｎ
_j（ｊは１から６までの整数）について、次の式３及び
式４を満たし、式２の値を最小にするＮ_jを求める。 最小化 Σ（ＰＢ_j−Ｐ_A×Ｎ_j）÷ＴＢ_j÷Ｒ_B （式２） ただし、 Ｘ＋Σ（Ｐ_A×Ｎ_j÷ＴＢ_j÷Ｒ_A）≦１ （式３） ０≦Ｐ_A×Ｎ_j≦ＰＢ_j （式４） である。ここでΣはｊが１から６までについて合計する
ことを示す。Ｘは第１の実施形態の方法によって計算さ
れる。式３は一括送信番組用サブフレームへのパケット
の割当要求率を１以下にすることを意味している。式２
は非一括送信番組用サブフレームへのパケットの割当要
求率を最小にすることを示している。非一括送信番組が
期限に遅れなしで非一括送信番組用サブフレームに割当
可能であるためには、式２が１以下である必要がある。
次に各番組Ｂ_jのＰ_A×Ｎ_j個分のパケットを周期がＴ
Ｂ_j、１ページ分のパケット数がＰ_A×Ｎ_jである仮想的
な一括送信番組とする。そして非一括送信番組Ｂ_jの１
ページ分のパケット数からＰ_A×Ｎ_j個のパケット数を除
いた仮想的な非一括送信番組を作る（ステップ３３）。
次にそれぞれの番組集合に割り当てるサブフレームの送
信容量を求める（ステップ３４）。次にパケット割当モ
ジュールに制御が渡ったとき一括送信番組及び非一括送
信番組のサブフレームへの割当を行う（ステップ３
５）。ステップ３４及びステップ３５は、仮想的な一括
送信番組を一括送信番組用サブフレームに割り当てるこ
とを除いてステップ２２〜２５の処理と同様である。

【００２１】第２の実施形態によれば、第１の実施形態
よりも一括送信番組のサブフレームへのパケット割当効
率を上げることができる。

【００２２】（４）第３の実施形態 第２の実施形態では、数学的に最も割当効率が上げるよ
うに、非一括送信番組を一括送信番組用サブフレームへ
補充した。しかし扱う番組数が多くなり第２の実施形態
で示す計算量が大きなものになる場合や、計算しなくと
もほぼ最適な補充の仕方になりそうなＮ_jが求まる場合
など、事前に規則を用意することにより計算を早めるこ
とができる。以下このような規則の例を示す。

【００２３】規則例１：非一括送信番組のうち１番組を
構成するパケット数／ページが多いほど優先度を上げ、
優先度の高い番組から一括送信番組のサブフレームに補
充する。例えば図３に示す非一括送信番組Ｂ２は１ペー
ジ分のパケット数が多いため補充のための優先順位を高
くしておき、まずＢ２から補充するＮ_jを求める。もし
まだ一括送信番組のサブフレームに空きがあれば次に優
先順位の高い番組を補充の候補とする、というようにし
て計算が早められる。

【００２４】規則例２：割当要求率が０．５％以下の番
組は除いて計算し、最後にフレームの空き領域へ割り当
てる。例えば非一括送信番組Ｂ５、Ｂ６は１ページ分の
パケット数が少なく送出周期が大きいため、まずこれら
を除外して上記計算を行った後、サブフレームの空き部
分に割り当てる、としても十分割当可能な場合が多い。

【００２５】規則例３：番組Ｂ１，Ｂ３，Ｂ２の順で一
括送信番組のサブフレームに補充する。特にどの番組を
選ぶかが規則化しにくい場合など、単にある番組を指定
するというだけの規則を用意することもできる。

【００２６】このように事前に規則化できるものを規則
として記憶装置上のルールベースに蓄えることによっ
て、スケジューラ３によってアクセスし計算を早くする
ことが可能である。

【００２７】（５）第４の実施形態 ＥＤＦは割当要求率が１以下の場合、必ず期限を守る割
当が保証されるが、１を越える場合は期限を守らない割
当をする。第４の実施形態は、割当要求率が１を越える
場合には予め定めた優先順位により、必ず期限を守って
送出したい番組のパケットを許容番組として確保し、各
フレーム送出時刻においてフレームにパケットが割り当
てられていない領域（フレームの空き）がある場合に残
りのパケットをフレームに割り当てることにより、優先
順位の高い番組を送出期限に遅れることなくフレームに
割り当てることができる。

【００２８】図８は、第４の実施形態のスケジューラ３
の処理を示す図である。ステップ４１は、あらかじめ定
められている非一括送信番組の優先順位に従って優先順
位の高い番組から順に許容番組集合に追加するものであ
る。ある非一括送信番組をこの集合に追加しようとする
とき、この番組の追加により非一括送信番組のサブフレ
ームに対する許容番組集合の割当要求率が１を越える場
合、追加をやめてステップ４１の処理を終了する。ステ
ップ４１はステップ３３とステップ３４との間で行う。
例えば番組Ｂ１が最も優先順位が高く、Ｂ２，Ｂ３，・
・・の順に優先順位が下がって行くものとする。このと
き番組Ｂ１，Ｂ２，Ｂ３の順で許容番組集合に追加して
行く。番組Ｂ４を追加すると非一括送信番組用サブフレ
ームに対する割当要求率が１を越えるとすると、許容番
組集合の追加をやめ、番組Ｂ４，Ｂ５，Ｂ６は許容番組
集合に含まないとする。そしてステップ２５の代わりに
ステップ４２及び４３を行う。ステップ４２で非一括送
信番組のうち許容番組集合を割当が決められているサブ
フレームにＥＤＦを用いて割り当てる。次にステップ４
３で非一括送信番組のうち許容番組集合に含まれない番
組を空きのあるサブフレームへＥＤＦを用いて割り当て
る。ただし非一括送信番組のうち許容番組集合に含まれ
ない番組集合については割当期限を守ることは保証され
ない。

【００２９】ＥＤＦは各パケット送出時刻におけるそれ
ぞれの番組の割当優先関係が割当期限までの時間により
変わる。このように優先度が固定でない割当方式は動的
な優先度の付け方といわれる。これに対して優先順位が
予め固定である静的な優先度の付け方をとる割当方式で
は、時間経過に伴う状況を反映することが難しいため、
割当期限を守るようスケジューリングすることが難し
い。特にどうしても割当に遅延が生じるような場合では
この傾向は強くなる。第４の実施形態によれば、どうし
ても割当に遅延が生じる番組集合についても優先順位に
忠実なフレーム割当を実現できる。

【００３０】（６）第５の実施形態 第５の実施形態は、ステップ４１の後で予め定めた規則
に従って許容番組集合に含まれない番組からいくつかの
番組を選び、周期又はパケット数／ページを修正する処
理を行うものである。以下このようにして修正を行うべ
く選ばれた番組を修正番組と呼ぶ。以下このような修正
規則の例を挙げる。

【００３１】修正規則１：許容番組集合に選ばれなかっ
た番組を修正番組として選び、修正番組の周期を許容パ
ケットのパケット数と修正パケットのパケット数の割当
要求率が１以下になるまで延ばす。例えば許容番組集合
に選ばれなかった番組を修正番組として選び、修正番組
のパケットについて周期が元の周期より長くなってもよ
いから周期的な割当をしたいという要求があるとする。
このとき上記修正規則１を適用し、修正された修正番組
を新たに非一括送信番組として登録し、非一括送信番組
用サブフレームにパケットの割当を行うものである。

【００３２】修正規則２：許容番組集合に選ばれなかっ
た番組を修正番組として選び、修正番組のパケット数／
ページを仮想的に減じ、許容パケット数と修正パケット
数を合わせたパケットの割当要求率が１以下になるまで
パケット数を減らす。例えば修正番組のパケットについ
て、周期は守りたいが割当を要求するパケット数のすべ
てをフレームに割り当てなくてもよいという要求がある
とする。このとき上記修正規則２を適用し、パケット数
の減少を行った修正パケット数を新たに非一括送信番組
のパケット数として登録し、非一括送信番組用サブフレ
ームにパケットの割当を行うものである。

【００３３】第５の実施形態によれば、どうしてもパケ
ット割当に遅延が生じる番組集合について、どの番組が
どの程度周期の遅れを生じるか又はどの番組がどれだけ
の情報量を削られるかを予め予測することができる。

【００３４】（７）第６の実施形態 ＥＤＦはフレームに空きがあればできるだけ早くパケッ
トを割り付けようとする性質がある。そのためパケット
はフレームへある時刻に固まって割り当てられ、別の時
刻にはフレームにかなり空きが生じる傾向がある。定期
的にフレームに空きができる場合は、その空き部分へ第
４の実施形態で説明した許容番組に含まれない番組を割
り当てることにより、許容番組に含まれない番組の割り
付けもある程度定期的に行うことができる。しかしフレ
ームへの空きが突発的である場合、許容番組に含まれな
い番組が定期的にフレームへ割り当てられない。これは
許容番組に含まれない番組でもできるだけ定期的にフレ
ームに割り当てたい場合には不都合である。そのため特
に一括送信番組のように１ページ分のパケット数が多い
番組では、突発的にフレームに空きができても無駄にな
る。しかし一括送信番組用サブフレームに仮想的に空パ
ケット番組を割り当てることにより、フレームの空きを
なるべく周期的に近いものにできる。

【００３５】図９（ａ）は空パケット番組を考慮しない
場合、図９（ｂ）は空パケット番組を割り当てる場合の
一括送信番組用サブフレームへのパケット割当状況を示
す図である。図９の横軸は時間軸を示し、数字は秒単位
の時刻を示す。１つの升目が２１パケット分の送信容量
を示し、一括送信番組用サブフレームは２１パケット×
２の送信容量があるものとする。番組Ａ１，Ａ２，Ａ３
及びＡ４は一括送信番組とし、それぞれ図３に示すパケ
ット数／ページと周期をもつものとする。図で空白にな
っている升目はその時刻のサブフレームに２１パケット
分の空きがあることを示す。図９（ｂ）は番組集合Ａ１
〜Ａ４にパケット数／ページが２１、周期２秒の仮想的
な番組Ｃを加えてパケット割当を行ったときのパケット
割当状況を示す。図９（ａ）と図９（ｂ）とを比較すれ
ば明らかなように、空パケット番組Ｃを加えることによ
って周期的に２１パケット分の空き領域を確保すること
ができる。

【００３６】（８）第７の実施形態 図１０は、他の一括送信番組集合を示す図である。番組
Ａ５のパケット数／ページは１９パケットであり、他の
番組Ａ２〜Ａ４の２１パケットとは異なる。上記実施形
態によれば、番組Ａ２〜Ａ４と番組Ａ５は１ページ分の
パケット数が異なる一括送信番組であるため、異なるサ
ブフレームを確保する。しかし第２の実施形態で述べた
ように、１ページ分のパケット数が大きくなるとそのサ
ブフレームへの割当効率が低下する場合がある。そこで
番組Ａ２〜Ａ４と番組Ａ５のように１ページ分のパケッ
ト数にあまり差のない番組は、１つのサブフレームでパ
ケット割当を行うのが効率的である。このときパケット
数／ページの多い番組Ａ２〜Ａ４を基準にして実施形態
１〜６の方式によって一括送信番組のサブフレームを確
保する。

【００３７】（９）第８の実施形態 これまでに説明した実施形態では番組集合が固定であっ
た。しかし実際のラジオ放送では、ある時間帯ごとに番
組編成が変化する。また地震などのニュース速報や緊急
番組が入る場合が考えられる。このような番組編成の変
化に対して、番組編成の変化するたびに以上の実施形態
のステップ２１及び２２の前処理を行い、この前処理に
より得られた条件の下にステップ２３以下のパケット割
当処理を実時間で計算して実時間スケジューリングを実
現することができる。

【００３８】

【発明の効果】本発明によれば、一括送信番組と非一括
送信番組とが混在する番組集合のパケット送出に関する
スケジューリングを実時間で行えるという効果がある。

【図面の簡単な説明】

【図１】第１の実施形態の概略を説明する図である。

【図２】第１の実施形態のスケジューラ３の処理の流れ
を示すフローチャートである。

【図３】番組集合とフレームの事例を説明する図であ
る。

【図４】実施形態のパケット送出装置の構成を示す図で
ある。

【図５】ＥＤＦアルゴリズムの処理の流れを示すフロー
チャートである。

【図６】第２の実施形態の概略を説明する図である。

【図７】第２の実施形態のスケジューラ３の処理の流れ
を示すフローチャートである。

【図８】第４の実施形態のスケジューラ３の処理を示す
図である。

【図９】空パケット番組による一括送信番組用サブフレ
ームへのパケット割当状況を示す図である。

【図１０】他の一括送信番組の集合を説明する図であ
る。

【符号の説明】

３・・・スケジューラ

Claims (5)

【特許請求の範囲】
1. 【請求項１】各放送番組が１周期当り所定のパケット数
   の情報を送出するよう定められており、複数の番組から
   集められたパケットを所定のパケット数分の送信容量を
   もち定期的に送信されるフレームに収納してパケット送
   出するときのパケットを該フレームに割り当てるスケジ
   ューリング方法において、 該複数の番組を１周期当りのパケット数を１つのフレー
   ムに割り当てて一括で送信すべき一括送信番組と１周期
   当りのパケット数を複数のフレームに分散して送信可能
   な非一括送信番組とに分割し、 一括送信番組の集合についてその割当要求率が１以下に
   なりかつ番組当り一括で送信すべきパケット数の整数倍
   となる最小のパケット数を該一括送信番組の集合につい
   てのサブフレームの送信容量とし、フレームの送信容量
   から一括送信番組用のサブフレームの送信容量を除いた
   残りを非一括送信番組用のサブフレームの送信容量とし
   て設定し、 フレームを送出する各時刻ごとにＥＤＦアルゴリズムに
   従って、一括送信番組のパケットを一括送信番組用サブ
   フレームに割り当てるとともに非一括送信番組のパケッ
   トを非一括送信番組用サブフレームに割り当てることを
   特徴とするパケット送出に関する実時間スケジューリン
   グ方法。
2. 【請求項２】該一括送信番組用サブフレームに一括送信
   番組のパケットを割り当てない空きが生じたとき、非一
   括送信番組の集合のうち一部のパケットを割り当てるこ
   とを特徴とする請求項１記載のパケット送出に関する実
   時間スケジューリング方法。
3. 【請求項３】該一括送信番組用サブフレームに一括送信
   番組のパケットを割り当てない空きが生じたとき、一括
   送信番組用サブフレームへのパケット割当要求率を１以
   下にしかつ非一括送信番組用サブフレームへのパケット
   割当要求率を最小にするように非一括送信番組の集合の
   うち一部のパケットを該一括送信番組用サブフレームの
   空き領域に割り当てることを特徴とする請求項２記載の
   パケット送出に関する実時間スケジューリング方法。
4. 【請求項４】非一括送信番組に優先度を設定し、優先度
   の高い番組から順に該一括送信番組用サブフレームの空
   き領域に補充することを特徴とする請求項２記載のパケ
   ット送出に関する実時間スケジューリング方法。
5. 【請求項５】非一括送信番組に優先度を設定し、優先度
   の高い番組から順に一括送信番組用サブフレーム又は非
   一括送信番組用サブフレームへパケットを割り当てたと
   きの割当要求率が１以下である限り１周期当り所定のパ
   ケット数の送出を保証するパケット割当スケジューリン
   グを行うことを特徴とする請求項２記載のパケット送出
   に関する実時間スケジューリング方法。