(57)【特許請求の範囲】
【請求項１】
各セルを転送するターン内における各回線毎の転送の順序を、前記ターン中の各時点を示すスロットに指定するタイムスロットと、
前記タイムスロットが備えるスロット数と同数の要素を備えて、その各要素に対してセルの転送対象である各前記回線を設定するセル読み出し順序管理テーブルと、
前記セル読み出し順序管理テーブルへの、各前記回線の設定を制御するスケジュール算出手段と、
前記セル読み出し順序管理テーブルの各要素を、前記タイムスロットの各スロットの指定された位置に変換する配置処理手段を備え、
前記ターン毎に、前記タイムスロッにおいて指定された順番に従い、その指定された前記回線のセルを順次転送するスケジュールシステムにおいて、
各前記回線におけるセルを送信するレートを、セルを転送する１回のターン中に当該回線から転送するセル数であるＰＣＲ値により示し、
前記セル読み出し順序管理テーブル内における、転送対象の各回線を新規に設定する場合の設定位置を、前記回線のＰＣＲ値毎に示すスケジュール管理テーブルを備え、
個々の回線毎のセルを送信するレート従い、各前記回線毎の、セルを読み出して転送する順序を制御することを特徴とするスケジュールシステム。
【請求項２】
前記スケジュール算出手段は、
前記セル読み出し順序管理テーブル内における、指定されたＰＣＲ値の整数倍を成す要素の次の位置の要素であって、指定されたＰＣＲ値分の連続する要素に対して当該回線が設定可能であるという条件を満たし、かつその最も前方の要素がある場合には、当該要素の位置を、前記指定されたＰＣＲ値を備える回線の設定位置を示すデータとして当該ＰＣＲ値と対応させて前記スケジュール管理テーブルに登録する手段と、
新規に転送を行う回線が発生した場合に、前記セル読み出し順序管理テーブルにおける、前記スケジュール管理テーブルに記録された当該回線のＰＣＲ値に該当する設定位置から、当該ＰＣＲ値分の連続する要素に対して当該回線を新規設定する手段と、
現在転送中の回線の通信が削除された場合に、前記セル読み出し順序管理テーブルの当該回線を設定した要素から、当該回線の設定を解除する手段と、
転送対象の回線の新規設定や削除が発生した場合に、前記スケジュール管理テーブルの登録を最新のデータに更新する手段を備えることを特徴とする請求項１に記載のスケジュールシステム。
【請求項３】
前記配置処理手段は、
前記セル読み出し順序管理テーブルにおける、各前記ＰＣＲ値の整数倍の要素の次の位置から当該ＰＣＲ値分の連続する要素が、前記タイムスロットにおける均等の間隔に分散された位置に変換されるように指定された、各要素毎の変換先のスロット位置の指定に基づいて、前記セル読み出し順序管理テーブル内の各要素を前記タイムスロット内の指定された各位置に変換する手段と、
もし、前記セル読み出し順序管理テーブルの要素に回線が設定されている場合には、前記タイムスロットにおける当該回線の変換先のスロットにおいて、当該回線のセルを転送する旨を指定して設定する手段を備えることを特徴とする請求項２に記載のスケジュールシステム。
【請求項４】
前記タイムスロットのスロット数、及び各前記回線の各ＰＣＲ値のそれぞれの値を、いずれも“２”の非負の整数によるべき乗を成す値とすることを特徴とする請求項２又は請求項３に記載のスケジュールシステム。
【請求項５】
前記セル読み出し順序管理テーブルから前記タイムスロットへの変換方法は、
整数“Ａ”を、“２”の“Ａ”乗の値が前記タイムスロット長を成す値とし、
前記セル読み出し順序管理テーブルの各要素、及び前記タイムスロットの各スロット位置を、“１”から前記タイムスロット長の値までの連続番号を用いて示し、
まず、前記セル読み出し順序管理テーブルの各要素を取り、
当該要素における連続番号の値から“１”を減じた値を、もし上位の桁に値がない場合には“０”を補完して“Ａ”桁の２進数により表示し、
当該“Ａ”桁の２進数の表示を、上位の桁から下位の桁への並びを逆順に変換して、変換された“Ａ”桁の２進数を得て、
当該変換された“Ａ”桁の２進数の値に対して“１”を加えた値を、当該要素の変換先である前記タイムスロットのスロット位置として定めることを特徴とする請求項４に記載のスケジュールシステム。
【請求項６】
前記スケジュール算出手段は、
前記セル読み出し順序管理テーブルの要素から回線の設定を解除した場合において、もし当該回線が設定されていた位置よりも後方に、当該回線のＰＣＲ値以下のＰＣＲ値を備える他の回線が設定されている場合には、当該他の回線の設定位置を、先に回線の設定が解除された個所に移動させることを特徴とする請求項２から請求項５のいずれか一つに記載のスケジュールシステム。
【請求項７】
前記スケジュール算出手段は、
前記セル読み出し順序管理テーブルの要素から回線の設定を解除した場合において、もし当該回線が設定されていた位置よりも後方に、当該回線のＰＣＲ値以下のＰＣＲ値を備える他の回線が設定されている場合には、該当する回線の内で最もＰＣＲ値の大きい回線であって、かつその内で最も後方に位置する１つの回線の設定位置を、先に回線の設定が解除された個所に移動させることを特徴とする請求項２から請求項５のいずれか一つに記載のスケジュールシステム。
【請求項８】
前記回線を、ＡＴＭ回線とすることを特徴とする請求項１から請求項７のいずれか一つに記載のスケジュールシステム。
【請求項９】
各回線におけるセルを送信するレートを、セルを転送する１回のターン中に当該回線から転送するセル数であるＰＣＲ値により示し、
各セルを転送する前記ターン内における各前記回線毎の転送の順序を指定するタイムスロットの、前記ターン中の各時点を示すスロットに指定される順番に従い、指定された前記回線のセルを順次転送するステップと、
前記タイムスロットが備えるスロット数と同数の要素を備えてその各要素に対してセルの転送対象である各前記回線を設定するセル読み出し順序管理テーブルに対して、各前記回線の設定を制御するステップと、
前記セル読み出し順序管理テーブルの各要素を、前記タイムスロットの各スロットの指定された位置に変換するステップと、
前記セル読み出し順序管理テーブル内における、転送対象の各回線を新規に設定する場合の設定位置を、前記回線のＰＣＲ値毎に示すスケジュール管理テーブルを適切に更新し、参照するステップを備え、
個々の回線毎のセルを送信するレート従い、各前記回線毎の、セルを読み出して転送する順序を制御することを特徴とするスケジュール方法。
【請求項１０】
前記セル読み出し順序管理テーブル内における、指定されたＰＣＲ値の整数倍を成す要素の次の位置の要素であって、指定されたＰＣＲ値分の連続する要素に対して当該回線が設定可能であるという条件を満たし、かつその最も前方の要素がある場合には、当該要素の位置を、前記指定されたＰＣＲ値を備える回線の前記セル読み出し順序管理テーブル内の設定位置を示すデータとして、当該ＰＣＲ値と対応させて前記スケジュール管理テーブルに登録するステップと、
新規に転送を行う回線が発生した場合に、前記セル読み出し順序管理テーブルにおける、前記スケジュール管理テーブルに記録された当該回線のＰＣＲ値に該当する設定位置から、当該ＰＣＲ値分の連続する要素に対して当該回線を新規設定するステップと、
現在転送中の回線の通信が削除された場合に、前記セル読み出し順序管理テーブルの当該回線を設定した要素から、当該回線の設定を解除するステップと、
転送対象の回線の新規設定や削除が発生した場合に、前記スケジュール管理テーブルの登録を最新のデータに更新するステップを備えることを特徴とする請求項９に記載のスケジュール方法。
【請求項１１】
前記セル読み出し順序管理テーブルにおける、各前記ＰＣＲ値の整数倍の要素の次の位置から当該ＰＣＲ値分の連続する要素が、前記タイムスロットにおける均等の間隔に分散された位置に変換されるように指定された、各要素毎の変換先のスロット位置の指定に基づいて、前記セル読み出し順序管理テーブル内の各要素を前記タイムスロット内の指定された各位置に変換するステップと、
もし、前記セル読み出し順序管理テーブルの要素に回線が設定されている場合には、前記タイムスロットにおける当該回線の変換先のスロットにおいて、当該回線のセルを転送する旨を指定して設定するステップを備えることを特徴とする請求項１０に記載のスケジュール方法。
【請求項１２】
前記タイムスロットのスロット数、及び各前記回線の各ＰＣＲ値のそれぞれの値を、いずれも“２”の非負の整数によるべき乗を成す値とすることを特徴とする請求項１０又は請求項１１に記載のスケジュール方法。
【請求項１３】
前記セル読み出し順序管理テーブルから前記タイムスロットへの変換方法は、
整数“Ａ”を、“２”の“Ａ”乗の値が前記タイムスロット長を成す値とし、
前記セル読み出し順序管理テーブルの各要素、及び前記タイムスロットの各スロット位置を、“１”から前記タイムスロット長の値までの連続番号を用いて示し、
まず、前記セル読み出し順序管理テーブルの各要素を取り、
当該要素における連続番号の値から“１”を減じた値を、もし上位の桁に値がない場合には“０”を補完して“Ａ”桁の２進数により表示し、
当該“Ａ”桁の２進数の表示を、上位の桁から下位の桁への並びを逆順に変換して、変換された“Ａ”桁の２進数を得て、
当該変換された“Ａ”桁の２進数の値に対して“１”を加えた値を、当該要素の変換先である前記タイムスロットのスロット位置として定めることを特徴とする請求項１２に記載のスケジュール方法。
【請求項１４】
前記セル読み出し順序管理テーブルの要素から回線の設定を解除した場合において、もし当該回線が設定されていた位置よりも後方に、当該回線のＰＣＲ値以下のＰＣＲ値を備える他の回線が設定されている場合には、当該他の回線の設定位置を、先に回線の設定が解除された個所に移動させることを特徴とする請求項１０から請求項１３のいずれか一つに記載のスケジュール方法。
【請求項１５】
前記セル読み出し順序管理テーブルの要素から回線の設定を解除した場合において、もし当該回線が設定されていた位置よりも後方に、当該回線のＰＣＲ値以下のＰＣＲ値を備える他の回線が設定されている場合には、該当する回線の内で最もＰＣＲ値の大きい回線であって、かつその内で最も後方に位置する１つの回線の設定位置を、先に回線の設定が解除された個所に移動させることを特徴とする請求項１０から請求項１３のいずれか一つに記載のスケジュール方法。
【請求項１６】
前記回線を、ＡＴＭ回線とすることを特徴とする請求項９から請求項１５のいずれか一つに記載のスケジュール方法。
【請求項１７】
個々のＡＴＭ回線毎のセルを送信するレート従い、各前記ＡＴＭ回線毎の、セルを読み出して転送する順序を制御するスケジュールシステムを備えるＡＴＭ交換機において、
前記スケジュールシステムは、
各前記ＡＴＭ回線におけるセルを送信するレートを、セルを転送する１回のターン中に当該ＡＴＭ回線から転送するセル数であるＰＣＲ値により示し、
各セルを転送するターン内における各前記ＡＴＭ回線毎の転送の順序を、前記ターン中の各時点を示すスロットに指定するタイムスロットと、
前記タイムスロットが備えるスロット数と同数の要素を備えて、その各要素に対してセルの転送対象である各前記ＡＴＭ回線を設定するセル読み出し順序管理テーブルと、
前記セル読み出し順序管理テーブルへの、各前記ＡＴＭ回線の設定を制御するスケジュール算出手段と、
前記セル読み出し順序管理テーブルの各要素を、前記タイムスロットの各スロットの指定された位置に変換する配置処理手段と、
前記セル読み出し順序管理テーブル内における、転送対象の各ＡＴＭ回線を新規に設定する場合の設定位置を、前記ＡＴＭ回線のＰＣＲ値毎に示すスケジュール管理テーブルを備え、
前記ターン毎に、前記タイムスロットにおいて指定された順番に従い、その指定された前記ＡＴＭ回線のセルを順次転送することを特徴とするＡＴＭ交換機。
【請求項１８】
前記スケジュール算出手段は、
前記セル読み出し順序管理テーブル内における、指定されたＰＣＲ値の整数倍を成す要素の次の位置の要素であって、指定されたＰＣＲ値分の連続する要素に対して当該ＡＴＭ回線が設定可能であるという条件を満たし、かつその最も前方の要素がある場合には、当該要素の位置を、前記指定されたＰＣＲ値を備えるＡＴＭ回線の設定位置を示すデータとして当該ＰＣＲ値と対応させて前記スケジュール管理テーブルに登録する手段と、
新規に転送を行うＡＴＭ回線が発生した場合に、前記セル読み出し順序管理テーブルにおける、前記スケジュール管理テーブルに記録された当該ＡＴＭ回線のＰＣＲ値に該当する設定位置から、当該ＰＣＲ値分の連続する要素に対して当該ＡＴＭ回線を新規設定する手段と、
現在転送中のＡＴＭ回線の通信が削除された場合に、前記セル読み出し順序管理テーブルの当該ＡＴＭ回線を設定した要素から、当該ＡＴＭ回線の設定を解除する手段と、
転送対象のＡＴＭ回線の新規設定や削除が発生した場合に、前記スケジュール管理テーブルの登録を最新のデータに更新する手段を備えることを特徴とする請求項１７に記載のＡＴＭ交換機。
【請求項１９】
前記配置処理手段は、
前記セル読み出し順序管理テーブルにおける、各前記ＰＣＲ値の整数倍の要素の次の位置から当該ＰＣＲ値分の連続する要素が、前記タイムスロットにおける均等の間隔に分散された位置に変換されるように指定された、各要素毎の変換先のスロット位置の指定に基づいて、前記セル読み出し順序管理テーブル内の各要素を前記タイムスロット内の指定された各位置に変換する手段と、
もし、前記セル読み出し順序管理テーブルの要素にＡＴＭ回線が設定されている場合には、前記タイムスロットにおける当該ＡＴＭ回線の変換先のスロットにおいて、当該ＡＴＭ回線のセルを転送する旨を指定して設定する手段を備えることを特徴とする請求項１８に記載のＡＴＭ交換機。
【請求項２０】
前記タイムスロットのスロット数、及び各前記ＡＴＭ回線の各ＰＣＲ値のそれぞれの値を、いずれも“２”の非負の整数によるべき乗を成す値とすることを特徴とする請求項１８又は請求項１９に記載のＡＴＭ交換機。
【請求項２１】
前記セル読み出し順序管理テーブルから前記タイムスロットへの変換方法は、
整数“Ａ”を、“２”の“Ａ”乗の値が前記タイムスロット長を成す値とし、
前記セル読み出し順序管理テーブルの各要素、及び前記タイムスロットの各スロット位置を、“１”から前記タイムスロット長の値までの連続番号を用いて示し、
まず、前記セル読み出し順序管理テーブルの各要素を取り、
当該要素における連続番号の値から“１”を減じた値を、もし上位の桁に値がない場合には“０”を補完して“Ａ”桁の２進数により表示し、
当該“Ａ”桁の２進数の表示を、上位の桁から下位の桁への並びを逆順に変換して、変換された“Ａ”桁の２進数を得て、
当該変換された“Ａ”桁の２進数の値に対して“１”を加えた値を、当該要素の変換先である前記タイムスロットのスロット位置として定めることを特徴とする請求項２０に記載のＡＴＭ交換機。
【請求項２２】
前記スケジュール算出手段は、
前記セル読み出し順序管理テーブルの要素からＡＴＭ回線の設定を解除した場合において、もし当該ＡＴＭ回線が設定されていた位置よりも後方に、当該ＡＴＭ回線のＰＣＲ値以下のＰＣＲ値を備える他のＡＴＭ回線が設定されている場合には、当該他のＡＴＭ回線の設定位置を、先にＡＴＭ回線の設定が解除された個所に移動させることを特徴とする請求項１８から請求項２１のいずれか一つに記載のＡＴＭ交換機。
【請求項２３】
前記スケジュール算出手段は、
前記セル読み出し順序管理テーブルの要素からＡＴＭ回線の設定を解除した場合において、もし当該ＡＴＭ回線が設定されていた位置よりも後方に、当該ＡＴＭ回線のＰＣＲ値以下のＰＣＲ値を備える他のＡＴＭ回線が設定されている場合には、該当するＡＴＭ回線の内で最もＰＣＲ値の大きいＡＴＭ回線であって、かつその内で最も後方に位置する１つのＡＴＭ回線の設定位置を、先にＡＴＭ回線の設定が解除された個所に移動させることを特徴とする請求項１８から請求項２１のいずれか一つに記載のＡＴＭ交換機。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＡＴＭ（ａｓｙｎｃｈｒｏｎｏｕｓ  ｔｒａｎｓｆｅｒ  ｍｏｄｅ：非同期転送モード）回線におけるセルの読み出しの制御に関し、特に、各セルを効率的に読み出すためのスケジュールシステムとそのスケジュール方法に関する。
【０００２】
【従来の技術】
ＡＴＭ（ａｓｙｎｃｈｒｏｎｏｕｓ  ｔｒａｎｓｆｅｒ  ｍｏｄｅ：非同期転送モード）は、伝送するデータを全て５３オクテット（１オクテット＝８ビット）の「セル」という単位に分割して高速に送受信する通信方式である。ＡＴＭは、マルチメディア・データ等の大容量のデータの転送に適しており、又広帯域ＩＳＤＮの基幹技術となっている。
【０００３】
ＡＴＭでは多重通信を行い、更に一定時間に送信するセル数（セルのレート）を自由に設定することによって、その伝送速度を調節することができる。このため、送信の対象に音声、静止画、動画等が混在する場合においても、これを適切に伝送することができる。
【０００４】
また、ＡＴＭ交換機は、大容量、高速度のデジタル交換を行い端末間の通信を仲介するのであり、例えば、複数のＡＴＭ回線を単一の物理伝送路にセル多重化して送出する等の交換を行う。
【０００５】
この場合、各ＡＴＭ回線のデータを読み出す順番は（つまり、各回線毎のセルの送信の順番は）、データを適正な速度により送信するためにも、同じ回線のセルの送信が一時に集中しないように、各回線毎のレートに応じて各セルを（なるべく等間隔に）分散して送信することが求められる。
【０００６】
例えば、各セルの送信の順番を指定するタイムスロットを用いて、セルの送信を制御する場合においては、各ＡＴＭ回線の出力ポートにおけるバースト性を軽減する等のために、同じ回線の各セルをタイムスロット内の分散された位置に適切に割り当てるスケジュールを行う必要がある。
【０００７】
この各回線毎の、その回線のセルを送信する最大の速度を指定するための値には、ＰＣＲ値（Ｐｅａｋ  Ｃｅｌｌ  Ｒａｔｅ：最大セル転送速度）がある。ＰＣＲは、ＡＴＭにおいて、セルが転送可能な最大の速度を示すものであり、又ＰＣＲ値により同じ回線の各セルを転送する最小の間隔が決定される。以下、本明細書においてはＰＣＲ値を、各回線毎の、１つのタイムスロット内において転送可能なセル数を示すものとする。つまり、例えばＰＣＲ値が“４”である回線では、タイムスロットの１回のターンで、４個のセルを送信できるのである。
【０００８】
従来の、各回線のセルを、タイムスロット内の分散された位置に割り当てるための技術には、例えば、次に説明するものがある。図１４は、従来の、各セルをタイムスロット内の分散された位置に割り当てるスケジューリングの処理の一例を、タイムスロット長が１６である場合を例に説明するための図である。
【０００９】
まず、タイムスロットに割り当てることのできる最大のセル数（以下、この数を“ＴＥＮ”と記す）分の長さを備えるテーブルである、セル読出順番管理テーブルを用意する。
【００１０】
このセル読出順番管理テーブル内に、転送する各データの１つのタイムスロット内で転送するセル数分の（つまり、各データのＰＣＲ値分の）要素を、一まとめにそれぞれ確保する。図１４の例においては、“Ａ”、“Ｂ”に示されるＡＴＭ回線（又、転送するデータ）のＰＣＲ値は“２”であり、“Ｃ”のＰＣＲ値は“１”であり、セル読出順番管理テーブル内に先頭の要素から順次確保している。
【００１１】
タイムスロットにおいては、セル読出順番管理テーブルの各要素の順番に対応して、各セルの割り当て先のスロットが指定されており、送信する各回線のセルをその指定された位置に割り当てる。図１４の例では、“Ａ”の各セルは１と２の番号に対応するスロットに、“Ｂ”のセルは３と４の番号に対応するスロットに、それぞれ割り当てられている。
【００１２】
タイムスロットでは、各スロットに割り当てられたセルを右回りに順次送信する。つまり、セル読出順番管理テーブルの順番において１、９、５、１３、・・・の順に送信していくのであり、このようにして同じ回線におけるセルが分散して送信されるのである。例えば図１４では、“Ａ”や“Ｂ”における２つのセルが、タイムスロット内の向かい合う位置に割り当てられたことによって、１つのターン中に２つのセルを送信するレートにより、順次その各セルが等間隔に送信されるのである。
【００１３】
以上のようにして、サービス対象の各ＡＴＭ回線におけるＰＣＲ値を基にセル読出順番管理テーブルをスケジュールし、このスケジュールされたセル読出順番管理テーブルに従って読み出し制御を行うことで、サービス対象の各ＡＴＭ回線の各セルの転送における転送のレートが保証されるのである。
【００１４】
ここでの、セル読出順番管理テーブル内の連続する各順番を、タイムスロット内の分散された各位置に変換する方法には、例えば次の方法がある。
【００１５】
図１２は、セル読出順番管理テーブルの各位置をタイムスロット内の位置に変換する方法の一計算例を示すものであり、図１３においてはその変換結果の一覧を示している。
【００１６】
ここでは、タイムスロットの長さが１６である場合を例に説明しているが、長さが２のべき乗を成す（例えば、３２、６４、・・・等）他の場合においても同様に適応することができる。ここでセル読出順番管理テーブルの長さは、タイムスロットの長さと等しく、又このためｌｏｇ２（テーブル長）桁の２進数で表すことができる（この例においては、ｌｏｇ２（１６）＝４桁である）。
【００１７】
図１２に示されるように、まず各順番の値から“１”を引いた値を求めて、これを（４桁の）２進数で表す。そして、２進数により示された各桁の数値（“０”又“１”）の順番を逆順に変換する。つまり、４桁の２進数により示された値のＭＳＢ（ｍｏｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｂｉｔ：最上位ビット）側とＬＳＢ（ｌｅａｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｂｉｔ：最下位ビット）側との、順番を逆に入れ替えて得られる２進数の値を求めるのである。そして、得られた値に対し“１”を加えた値を、対応するタイムスロット位置と定めるのである。
【００１８】
例えば、セル読出順番管理テーブル内の“８番目”においては、“１”を減じ（４桁の）２進数で表すと“０１１１”（＝７）が得られ、これの各桁を逆順に並べることにより“１１１０”（＝１４）の値を得る。最後に、この値に“１”を加えることにより、変換結果である対応するタイムスロット位置“１５”が得られる。
【００１９】
ここでは、サービスされる各ＡＴＭ回線における帯域の最大レート（ＰＣＲ値）を２のべき乗値とし、このＰＣＲ値によりセル読出順番管理テーブルをスケジュールする。ＰＣＲ値をこのように２のべき乗値（つまり、１、２、４、８、・・・等）とする手法は、通常よく用いられる手法であり、このため２進数の性質を利用することができ、処理を単純化することができるのである。
【００２０】
特に、この変換方法は、セル読出順番管理テーブルにおいて、（２のべき乗である）ＰＣＲ値分の要素を、そのＰＣＲ値の整数倍の位置の先から（つまり、整数倍の位置の次の位置から）連続して確保する場合に適しており、ここで確保された要素はタイムスロットに均等の間隔で分散されるのである。更に、ここでの（２のべき乗である）ＰＣＲ値分の要素を、そのＰＣＲ値の整数倍の位置の先から確保することは、各回線におけるＰＣＲ値分の要素を、降順に先頭から並べるのみで達成される。
【００２１】
例えば、図１４の例では、ＰＣＲ値がそれぞれ“２”“２”“１”である３つの回線“Ａ”“Ｂ”“Ｃ”を、ＰＣＲ値が降順となるように順次並べて、セル読出順番管理テーブルにおいてＰＣＲ値分の要素を確保している。これにより均等の間隔でタイムスロットに割り当てられるため、各回線のセルが等間隔に送信されるのである。
【００２２】
また逆に、従来では、各回線が送出するセルを均一のレートにより転送するために、上記の方法のようにして、出順番管理テーブルにおいてＰＣＲ値が降順となるように各回線のための要素を順次並べて確保していたのである。
【００２３】
しかし、この各ＡＴＭ回線のセルを転送するＡＴＭ交換機においては、常に定常的な通信速度によりデータを送信するとは限らず、各回線毎に途中でデータの転送が終了したり、逆に新規のデータ転送が開始することがある。
【００２４】
このため、従来のＡＴＭ交換機においては、前述の説明の様に出順番管理テーブルの先頭から各回線をＰＣＲ値の降順に、かつ途中で未使用の空き領域が発生しないようにスケジュールし、出順番管理テーブル内のその各回線の位置を適宜更新を行うのであった。
【００２５】
次に、上述の方法によりセル読出順番管理テーブルのスケジューリングを処理する、従来のスケジュールシステムを説明する。
【００２６】
図１６は、従来のＡＴＭ回線のセルの読み出しを制御するスケジュールシステム１００ａの構成を示すブロック図である。
【００２７】
図１６を参照すると、従来のスケジュールシステム１００ａでは、まず回線設定インタフェース１０において受信したデータを、スケジュール算出部２０ａに供給し、セル読み出し管理テーブルへのスケジュール計算を実行する。
【００２８】
配置処理部３０は、このスケジュール算出部２０ａが計算したスケジュール結果を、タイムスロット４０に設定する。つまり、配置処理部３０は、セル読み出し管理テーブルの各要素を、図１２、図１３に示される変換方法に従い、タイムスロット４０の各位置に変換するのである。
【００２９】
このタイムスロットの設定に従い、装置へ入力されたＡＴＭ回線をコネクション入力キュー５０から、シェーピングサービス出力キュー６０へ読み出すことにより、各ＡＴＭ回線のレートを保証したシェーピングサービスを実施可能とする。
【００３０】
また、図１６の従来のスケジュール算出部２０ａの構成と動作は、以下の通りである。
【００３１】
即ち、回線設定インタフェース１０から入力されたデータを、パラメータ処理部において処理し、スケジュール対象算出部へ出力する。スケジュール対象算出部は、回線の新規収容又は回線削除に伴い、セル読出順番管理テーブルにおける位置を変更すべき回線を算出する。この従来のスケジュール算出部２０において、スケジュール変更の対象となるＡＴＭ回線は、回線の新規収容又は回線削除を行う回線のＰＣＲ値と、同一のＰＣＲ値を有する回線の一部と、より小さなＰＣＲ値を有する回線の全てである。
【００３２】
スケジュールクリア部は、スケジュールが変更となるセル読出順番管理テーブルをクリアする。スケジュール算出部は、算出されたスケジュール変更対象の回線の内で、ＰＣＲ値の大きな回線から降順に、セル読出順番管理テーブルの空き領域の先頭部分より順にスケジュールする。これは、シェーピングサービスされるＡＴＭ回線のレートを保証するためには、回線のＰＣＲ値降順よりスケジュールした方がセル読出順番管理テーブルの収容効率が良いからである。
【００３３】
また、上記の様にＰＣＲ値を２のべき乗の値とした場合には、セル読出順番管理テーブルの空き領域の先頭部分より、ＰＣＲ値の大きな回線から降順にスケジュールすることにより、セル読み出し管理テーブルにおけるレート保証された位置を確保することができるのである。
【００３４】
しかし、ここで回線を整列しなかった場合、つまり、整列させることなく各回線をセル読出順番管理テーブルの空き領域の先頭部分より順にスケジュールした場合には、回線の降順の並びが崩れて回線レートの保証が失われる危険がある。
【００３５】
図１５は、セル読出順番管理テーブルにおいて、回線の降順の並びが崩れた場合におけるセルの読出しを説明する図であり、図１４の３つの回線が“Ｃ”“Ａ”“Ｂ”の順に、つまりＰＣＲ値が“１”“２”“２”の順に並べられている。前の図１４の例においては等間隔にセルが送信されていた“Ａ”“Ｂ”の回線は、不均一な間隔によりセルが送信され、ＰＣＲ値が示す送信間隔の条件が満たされない。
【００３６】
従って従来では、スケジュールの新規収容や変更を行う場合には、上記の様に処理対象の各回線を整列させる必要があった。
【００３７】
【発明が解決しようとする課題】
上述したように従来のスケジュールシステムでは、セル読出順番管理テーブルに登録する回線に変更が発生する度に、登録されている全ての回線をＰＣＲ値の降順に整列させて先頭から並べなおす等の、面倒な処理を実行する必要があった。
【００３８】
また、従来のこの問題点に対する対応策としては、セル読出順番管理テーブルに登録済みの回線の内でも、変更の発生した回線のＰＣＲ値よりも大きなＰＣＲ値を有する回線においては、その再スケジュールにおいてセル読出順番管理テーブル内の位置に変更が発生しないために、位置の変換処理の対象を、当該ＰＣＲ値と同等のＰＣＲ値を備える回線の一部及び、より小さいＰＣＲ値を備える回線の全てのみに限定して、再スケジュールの計算を実行するという方法もある。しかし、このように再スケジュールの対象がより限定されたとしても、回線の新規追加等の変更が発生する度に、整列させて並べ替える面倒な処理を実行することは変わらない。
【００３９】
本発明の第１の目的は、上記従来技術の欠点を解決し、複雑な構成や複雑な処理等を必要とすることなく、各回線のレートを保証し高速、大容量のデータ転送を実行するスケジュールシステムとそのスケジュール方法を提供することである。
【００４０】
本発明の第２の目的は、上記従来技術の欠点を解決し、各回線のセル読出順番管理テーブル内の位置を適切に管理更新するためのテーブルを新たに備えることにより、セル読出順番管理テーブルへの更新処理を大幅に削減するスケジュールシステムとそのスケジュール方法を提供することである。
【００４１】
【課題を解決するための手段】
上記目的を達成するため本発明のスケジュールシステムは、各セルを転送するターン内における各回線毎の転送の順序を、前記ターン中の各時点を示すスロットに指定するタイムスロットと、前記タイムスロットが備えるスロット数と同数の要素を備えて、その各要素に対してセルの転送対象である各前記回線を設定するセル読み出し順序管理テーブルと、前記セル読み出し順序管理テーブルへの、各前記回線の設定を制御するスケジュール算出手段と、前記セル読み出し順序管理テーブルの各要素を、前記タイムスロットの各スロットの指定された位置に変換する配置処理手段を備え、前記ターン毎に、前記タイムスロッにおいて指定された順番に従い、その指定された前記回線のセルを順次転送するスケジュールシステムにおいて、各前記回線におけるセルを送信するレートを、セルを転送する１回のターン中に当該回線から転送するセル数であるＰＣＲ値により示し、前記セル読み出し順序管理テーブル内における、転送対象の各回線を新規に設定する場合の設定位置を、前記回線のＰＣＲ値毎に示すスケジュール管理テーブルを備え、個々の回線毎のセルを送信するレート従い、各前記回線毎の、セルを読み出して転送する順序を制御することを特徴とする。
【００４２】
請求項２の本発明のスケジュールシステムは、前記スケジュール算出手段は、前記セル読み出し順序管理テーブル内における、指定されたＰＣＲ値の整数倍を成す要素の次の位置の要素であって、指定されたＰＣＲ値分の連続する要素に対して当該回線が設定可能であるという条件を満たし、かつその最も前方の要素がある場合には、当該要素の位置を、前記指定されたＰＣＲ値を備える回線の設定位置を示すデータとして当該ＰＣＲ値と対応させて前記スケジュール管理テーブルに登録する手段と、新規に転送を行う回線が発生した場合に、前記セル読み出し順序管理テーブルにおける、前記スケジュール管理テーブルに記録された当該回線のＰＣＲ値に該当する設定位置から、当該ＰＣＲ値分の連続する要素に対して当該回線を新規設定する手段と、現在転送中の回線の通信が削除された場合に、前記セル読み出し順序管理テーブルの当該回線を設定した要素から、当該回線の設定を解除する手段と、転送対象の回線の新規設定や削除が発生した場合に、前記スケジュール管理テーブルの登録を最新のデータに更新する手段を備えることを特徴とする。
【００４３】
請求項３の本発明のスケジュールシステムは、前記配置処理手段は、前記セル読み出し順序管理テーブルにおける、各前記ＰＣＲ値の整数倍の要素の次の位置から当該ＰＣＲ値分の連続する要素が、前記タイムスロットにおける均等の間隔に分散された位置に変換されるように指定された、各要素毎の変換先のスロット位置の指定に基づいて、前記セル読み出し順序管理テーブル内の各要素を前記タイムスロット内の指定された各位置に変換する手段と、もし、前記セル読み出し順序管理テーブルの要素に回線が設定されている場合には、前記タイムスロットにおける当該回線の変換先のスロットにおいて、当該回線のセルを転送する旨を指定して設定する手段を備えることを特徴とする。
【００４４】
請求項４の本発明のスケジュールシステムは、前記タイムスロットのスロット数、及び各前記回線の各ＰＣＲ値のそれぞれの値を、いずれも“２”の非負の整数によるべき乗を成す値とすることを特徴とする。
【００４５】
請求項５の本発明のスケジュールシステムは、前記セル読み出し順序管理テーブルから前記タイムスロットへの変換方法は、整数“Ａ”を、“２”の“Ａ”乗の値が前記タイムスロット長を成す値とし、前記セル読み出し順序管理テーブルの各要素、及び前記タイムスロットの各スロット位置を、“１”から前記タイムスロット長の値までの連続番号を用いて示し、まず、前記セル読み出し順序管理テーブルの各要素を取り、当該要素における連続番号の値から“１”を減じた値を、もし上位の桁に値がない場合には“０”を補完して“Ａ”桁の２進数により表示し、当該“Ａ”桁の２進数の表示を、上位の桁から下位の桁への並びを逆順に変換して、変換された“Ａ”桁の２進数を得て、当該変換された“Ａ”桁の２進数の値に対して“１”を加えた値を、当該要素の変換先である前記タイムスロットのスロット位置として定めることを特徴とする。
【００４６】
請求項６の本発明のスケジュールシステムは、前記スケジュール算出手段は、前記セル読み出し順序管理テーブルの要素から回線の設定を解除した場合において、もし当該回線が設定されていた位置よりも後方に、当該回線のＰＣＲ値以下のＰＣＲ値を備える他の回線が設定されている場合には、当該他の回線の設定位置を、先に回線の設定が解除された個所に移動させることを特徴とする。
【００４７】
請求項７の本発明のスケジュールシステムは、前記スケジュール算出手段は、前記セル読み出し順序管理テーブルの要素から回線の設定を解除した場合において、もし当該回線が設定されていた位置よりも後方に、当該回線のＰＣＲ値以下のＰＣＲ値を備える他の回線が設定されている場合には、該当する回線の内で最もＰＣＲ値の大きい回線であって、かつその内で最も後方に位置する１つの回線の設定位置を、先に回線の設定が解除された個所に移動させることを特徴とする。
【００４８】
請求項８の本発明のスケジュールシステムは、前記回線を、ＡＴＭ回線とすることを特徴とする。
【００４９】
請求項９の本発明のスケジュール方法は、各回線におけるセルを送信するレートを、セルを転送する１回のターン中に当該回線から転送するセル数であるＰＣＲ値により示し、各セルを転送する前記ターン内における各前記回線毎の転送の順序を指定するタイムスロットの、前記ターン中の各時点を示すスロットに指定される順番に従い、指定された前記回線のセルを順次転送するステップと、前記タイムスロットが備えるスロット数と同数の要素を備えてその各要素に対してセルの転送対象である各前記回線を設定するセル読み出し順序管理テーブルに対して、各前記回線の設定を制御するステップと、前記セル読み出し順序管理テーブルの各要素を、前記タイムスロットの各スロットの指定された位置に変換するステップと、前記セル読み出し順序管理テーブル内における、転送対象の各回線を新規に設定する場合の設定位置を、前記回線のＰＣＲ値毎に示すスケジュール管理テーブルを適切に更新し、参照するステップを備え、個々の回線毎のセルを送信するレート従い、各前記回線毎の、セルを読み出して転送する順序を制御することを特徴とする。
【００５０】
請求項１０の本発明のスケジュール方法は、前記セル読み出し順序管理テーブル内における、指定されたＰＣＲ値の整数倍を成す要素の次の位置の要素であって、指定されたＰＣＲ値分の連続する要素に対して当該回線が設定可能であるという条件を満たし、かつその最も前方の要素がある場合には、当該要素の位置を、前記指定されたＰＣＲ値を備える回線の前記セル読み出し順序管理テーブル内の設定位置を示すデータとして、当該ＰＣＲ値と対応させて前記スケジュール管理テーブルに登録するステップと、新規に転送を行う回線が発生した場合に、前記セル読み出し順序管理テーブルにおける、前記スケジュール管理テーブルに記録された当該回線のＰＣＲ値に該当する設定位置から、当該ＰＣＲ値分の連続する要素に対して当該回線を新規設定するステップと、現在転送中の回線の通信が削除された場合に、前記セル読み出し順序管理テーブルの当該回線を設定した要素から、当該回線の設定を解除するステップと、転送対象の回線の新規設定や削除が発生した場合に、前記スケジュール管理テーブルの登録を最新のデータに更新するステップを備えることを特徴とする。
【００５１】
請求項１１の本発明のスケジュール方法は、前記セル読み出し順序管理テーブルにおける、各前記ＰＣＲ値の整数倍の要素の次の位置から当該ＰＣＲ値分の連続する要素が、前記タイムスロットにおける均等の間隔に分散された位置に変換されるように指定された、各要素毎の変換先のスロット位置の指定に基づいて、前記セル読み出し順序管理テーブル内の各要素を前記タイムスロット内の指定された各位置に変換するステップと、もし、前記セル読み出し順序管理テーブルの要素に回線が設定されている場合には、前記タイムスロットにおける当該回線の変換先のスロットにおいて、当該回線のセルを転送する旨を指定して設定するステップを備えることを特徴とする。
【００５２】
請求項１２の本発明のスケジュール方法は、前記タイムスロットのスロット数、及び各前記回線の各ＰＣＲ値のそれぞれの値を、いずれも“２”の非負の整数によるべき乗を成す値とすることを特徴とする。
【００５３】
請求項１３の本発明のスケジュール方法は、前記セル読み出し順序管理テーブルから前記タイムスロットへの変換方法は、整数“Ａ”を、“２”の“Ａ”乗の値が前記タイムスロット長を成す値とし、前記セル読み出し順序管理テーブルの各要素、及び前記タイムスロットの各スロット位置を、“１”から前記タイムスロット長の値までの連続番号を用いて示し、まず、前記セル読み出し順序管理テーブルの各要素を取り、当該要素における連続番号の値から“１”を減じた値を、もし上位の桁に値がない場合には“０”を補完して“Ａ”桁の２進数により表示し、当該“Ａ”桁の２進数の表示を、上位の桁から下位の桁への並びを逆順に変換して、変換された“Ａ”桁の２進数を得て、当該変換された“Ａ”桁の２進数の値に対して“１”を加えた値を、当該要素の変換先である前記タイムスロットのスロット位置として定めることを特徴とする。
【００５４】
請求項１４の本発明のスケジュール方法は、前記セル読み出し順序管理テーブルの要素から回線の設定を解除した場合において、もし当該回線が設定されていた位置よりも後方に、当該回線のＰＣＲ値以下のＰＣＲ値を備える他の回線が設定されている場合には、当該他の回線の設定位置を、先に回線の設定が解除された個所に移動させることを特徴とする。
【００５５】
請求項１５の本発明のスケジュール方法は、前記セル読み出し順序管理テーブルの要素から回線の設定を解除した場合において、もし当該回線が設定されていた位置よりも後方に、当該回線のＰＣＲ値以下のＰＣＲ値を備える他の回線が設定されている場合には、該当する回線の内で最もＰＣＲ値の大きい回線であって、かつその内で最も後方に位置する１つの回線の設定位置を、先に回線の設定が解除された個所に移動させることを特徴とする。
【００５６】
請求項１６の本発明のスケジュール方法は、前記回線を、ＡＴＭ回線とすることを特徴とする。
【００５７】
請求項１７の本発明のＡＴＭ交換機は、個々のＡＴＭ回線毎のセルを送信するレート従い、各前記ＡＴＭ回線毎の、セルを読み出して転送する順序を制御するスケジュールシステムを備えるＡＴＭ交換機において、前記スケジュールシステムは、各前記ＡＴＭ回線におけるセルを送信するレートを、セルを転送する１回のターン中に当該ＡＴＭ回線から転送するセル数であるＰＣＲ値により示し、各セルを転送するターン内における各前記ＡＴＭ回線毎の転送の順序を、前記ターン中の各時点を示すスロットに指定するタイムスロットと、前記タイムスロットが備えるスロット数と同数の要素を備えて、その各要素に対してセルの転送対象である各前記ＡＴＭ回線を設定するセル読み出し順序管理テーブルと、前記セル読み出し順序管理テーブルへの、各前記ＡＴＭ回線の設定を制御するスケジュール算出手段と、前記セル読み出し順序管理テーブルの各要素を、前記タイムスロットの各スロットの指定された位置に変換する配置処理手段と、前記セル読み出し順序管理テーブル内における、転送対象の各ＡＴＭ回線を新規に設定する場合の設定位置を、前記ＡＴＭ回線のＰＣＲ値毎に示すスケジュール管理テーブルを備え、前記ターン毎に、前記タイムスロットにおいて指定された順番に従い、その指定された前記ＡＴＭ回線のセルを順次転送することを特徴とする。
【００５８】
請求項１８の本発明のＡＴＭ交換機は、前記スケジュール算出手段は、前記セル読み出し順序管理テーブル内における、指定されたＰＣＲ値の整数倍を成す要素の次の位置の要素であって、指定されたＰＣＲ値分の連続する要素に対して当該ＡＴＭ回線が設定可能であるという条件を満たし、かつその最も前方の要素がある場合には、当該要素の位置を、前記指定されたＰＣＲ値を備えるＡＴＭ回線の設定位置を示すデータとして当該ＰＣＲ値と対応させて前記スケジュール管理テーブルに登録する手段と、新規に転送を行うＡＴＭ回線が発生した場合に、前記セル読み出し順序管理テーブルにおける、前記スケジュール管理テーブルに記録された当該ＡＴＭ回線のＰＣＲ値に該当する設定位置から、当該ＰＣＲ値分の連続する要素に対して当該ＡＴＭ回線を新規設定する手段と、現在転送中のＡＴＭ回線の通信が削除された場合に、前記セル読み出し順序管理テーブルの当該ＡＴＭ回線を設定した要素から、当該ＡＴＭ回線の設定を解除する手段と、転送対象のＡＴＭ回線の新規設定や削除が発生した場合に、前記スケジュール管理テーブルの登録を最新のデータに更新する手段を備えることを特徴とする。
【００５９】
請求項１９の本発明のＡＴＭ交換機は、前記配置処理手段は、前記セル読み出し順序管理テーブルにおける、各前記ＰＣＲ値の整数倍の要素の次の位置から当該ＰＣＲ値分の連続する要素が、前記タイムスロットにおける均等の間隔に分散された位置に変換されるように指定された、各要素毎の変換先のスロット位置の指定に基づいて、前記セル読み出し順序管理テーブル内の各要素を前記タイムスロット内の指定された各位置に変換する手段と、もし、前記セル読み出し順序管理テーブルの要素にＡＴＭ回線が設定されている場合には、前記タイムスロットにおける当該ＡＴＭ回線の変換先のスロットにおいて、当該ＡＴＭ回線のセルを転送する旨を指定して設定する手段を備えることを特徴とする。
【００６０】
請求項２０の本発明のＡＴＭ交換機は、前記タイムスロットのスロット数、及び各前記ＡＴＭ回線の各ＰＣＲ値のそれぞれの値を、いずれも“２”の非負の整数によるべき乗を成す値とすることを特徴とする。
【００６１】
請求項２１の本発明のＡＴＭ交換機は、前記セル読み出し順序管理テーブルから前記タイムスロットへの変換方法は、整数“Ａ”を、“２”の“Ａ”乗の値が前記タイムスロット長を成す値とし、前記セル読み出し順序管理テーブルの各要素、及び前記タイムスロットの各スロット位置を、“１”から前記タイムスロット長の値までの連続番号を用いて示し、まず、前記セル読み出し順序管理テーブルの各要素を取り、当該要素における連続番号の値から“１”を減じた値を、もし上位の桁に値がない場合には“０”を補完して“Ａ”桁の２進数により表示し、当該“Ａ”桁の２進数の表示を、上位の桁から下位の桁への並びを逆順に変換して、変換された“Ａ”桁の２進数を得て、当該変換された“Ａ”桁の２進数の値に対して“１”を加えた値を、当該要素の変換先である前記タイムスロットのスロット位置として定めることを特徴とする。
【００６２】
請求項２２の本発明のＡＴＭ交換機は、前記スケジュール算出手段は、前記セル読み出し順序管理テーブルの要素からＡＴＭ回線の設定を解除した場合において、もし当該ＡＴＭ回線が設定されていた位置よりも後方に、当該ＡＴＭ回線のＰＣＲ値以下のＰＣＲ値を備える他のＡＴＭ回線が設定されている場合には、当該他のＡＴＭ回線の設定位置を、先にＡＴＭ回線の設定が解除された個所に移動させることを特徴とする。
【００６３】
請求項２３の本発明のＡＴＭ交換機は、前記スケジュール算出手段は、前記セル読み出し順序管理テーブルの要素からＡＴＭ回線の設定を解除した場合において、もし当該ＡＴＭ回線が設定されていた位置よりも後方に、当該ＡＴＭ回線のＰＣＲ値以下のＰＣＲ値を備える他のＡＴＭ回線が設定されている場合には、該当するＡＴＭ回線の内で最もＰＣＲ値の大きいＡＴＭ回線であって、かつその内で最も後方に位置する１つのＡＴＭ回線の設定位置を、先にＡＴＭ回線の設定が解除された個所に移動させることを特徴とする。
【００６４】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００６５】
図１は、本発明の一実施の形態によるスケジュールシステムの構成を示すブロック図である。
【００６６】
本実施の形態のスケジュールシステムは、ＡＴＭ交換機等における個々のＡＴＭ回線毎のセルの読み出し順番を管理するシステムであり、セルの読み出し順番を設定するテーブルであるセル読出順番管理テーブルに対して、各回線を適切に設定することによりその読出しの順番を管理するのである。
【００６７】
また、以下に説明するように、セル読出順番管理テーブルに対し効率的に各回線を設定することにより、回線収容や削除が繰り返し実施される環境においても、少ない処理のみでその更新を実現するのである。
【００６８】
図１を参照すると、本実施の形態のスケジュールシステム１００は、回線設定インタフェース１０、スケジュール算出部２０、配置処理部３０、タイムスロット４０を備え、コネクション入力キュー５０を受け付けて、シェーピングサービス出力キュー６０を出力する。これらの各部は、その各部の処理を実行する半導体回路等を用いる等により実現することができる。また、図１６の従来のスケジュールシステム１００ａとの主要な相違点は、以下に説明するスケジュール算出部２０とその処理である。
【００６９】
図２は、本実施の形態のセル読出順番管理テーブルの一例を示す図である。
【００７０】
本実施の形態のスケジュールシステムは、スケジュール算出部２０が、各回線をセル読出順番管理テーブルに、その（２のべき乗である）ＰＣＲ値に基づいて、そのＰＣＲ値の整数倍の位置の先から確保するように制御する。この確保された各回線を、図１２、図１３の例に示されるタイムスロットへの変換方法に従い変換し、タイムスロットにおける変換された順番に従い各回線のセルを読み出して転送する。先の従来技術において説明したように、（図２の例のように）ＰＣＲ値の整数倍の位置の先から確保された各回線の要素は、タイムスロット内の等間隔の位置に配置されるため、各回線の送信のレートに従うセルの適切な転送が実現されるのである。
【００７１】
また、もし回線が複数の個所に確保可能な場合においては、その最も始めの個所（番号が最も小さい個所）に確保する。これにより、テーブルの後方に広く未使用のエリアが確保されるため、以後の、新規の回線が効率良く確保することができるのである。
【００７２】
ここで、従来のスケジュールシステム１００ａでは、回線収容又は回線削除が発生した場合には、セル読出順番管理テーブルにおける各回線の位置を全て整列する必要があった。それは、各回線を正しくＰＣＲ値の整数倍の位置の先から確保するために必要であったのである。
【００７３】
しかし、本実施の形態のスケジュールシステムでは、各回線の位置をＰＣＲ値の降順に整列させる方法ではなく、各回線のＰＣＲ値に基づく適切な配置位置を示すスケジュール管理テーブルを備えて、そのテーブルの指定する位置に回線を配置することにより、整列処理を必要とすることなく適切な回線のスケジューリングを実現する。
【００７４】
図３は、図２のセル読出順番管理テーブルの例に対する、本実施の形態のスケジュール管理テーブルの一例を示す図であり、回線のＰＣＲ値を“ＥＮ”の列に、その各回線のＰＣＲ値に対応する適切な配置位置を“ＦＥＰ”の列に示している。
【００７５】
ここで、スケジュール管理テーブルが示す適切な各回線の配置位置とは、上述の説明にあるように、当該回線のＰＣＲ値の整数倍の位置の先からであって、かつ最も番号の少ない位置である。
【００７６】
ＰＣＲ値が“１”である回線は、セル読出順番管理テーブルの“８番目”の位置に配置することができ、ＰＣＲ値が“２”である回線は、セル読出順番管理テーブルの“１５番目”の位置に配置することができる。また、ＰＣＲ値が“４”以上の回線は、他の回線の間の空き領域には配置することはできず、末尾の“２５番目”から配置されることとなる。
【００７７】
また、新規の回線をスケジュール管理テーブルに基づいて新たに配置した場合や、回線が削除された場合においては、スケジュール算出部２０は、セル読出順番管理テーブルの各値を最新のものに更新する。このスケジュール管理テーブルの更新処理は、従来におけるセル読出順番管理テーブル自体を操作することが必要な整列処理と比較して、遥かに簡易な処理であり、スケジューリングに必要とされた処理の大幅な削減が実現される。
【００７８】
このように本実施の形態のスケジューリングシステムでは、スケジュール管理テーブルを用いることにより、各回線を正しくそのＰＣＲ値の整数倍の位置の先から確保することが、セル読出順番管理テーブルの整列処理を必要とすることなく実現されるのである。
【００７９】
本実施の形態のセル読出順番管理テーブルにおいては、図２の例に示されるように、確保された各回線の領域の間に空き領域が生じたり、又各セルのＰＣＲ値の降順の整列が崩れた場合においても、各回線を整列する処理を実行する必要はない。
【００８０】
しかし又、各回線が確保した領域の間に空き領域がある場合においては、セル読出順番管理テーブルの後方の回線を移動してその空き領域を埋めることで、後方の未使用領域をより広く取ることができるのであるから、このような移動処理を行うことは有効である。このため、本実施の形態の効果的な一実施例として、セル読出順番管理テーブルからの回線の削除時に、回線間に挟まれた空き領域が発生したり、その空き領域が拡大した場合においては、当該空き領域を埋めることのできる回線が、当該空き領域よりも後方に存在するかどうかを検索し、存在する場合にはこれを空き領域内に移動し、当該空き領域を埋める（又は、空き領域を狭める）処理を実行する方式が考えられる。回線の１つを移動する処理は、全ての回線を整列させる処理と比較して、遥かに簡易な処理であり、スケジューリング処理の削減の効果と共に、広く未使用領域が確保できる効果が得られる。
【００８１】
また、他の実施例として、セル読出順番管理テーブルに回線を新規に登録する場合（又前記の実施例における回線を移動する場合）に、各回線が確保した領域の間の空き領域内に対しては、当該空き領域に登録することのできる最長の長さのＰＲＣ値の回線のみを登録する方式も考えられる。つまり、図２の例において、１５〜１６番目の空き領域にはＰＣＲ値が“２”の回線を登録することができるため、ここで８番目の空き領域が既に埋められている場合においても、ＰＣＲ値が“１”の回線は１５番目の空き領域に登録せずに、末尾の２５番目とするものである。これは、スケジュール算出部２０が、このように規定されるスケジューリングを実現するようにスケジュール管理テーブルの各値を定めることによって、前述の各実施例と同様に実現することができる。
【００８２】
次に、本実施の形態のスケジュールシステムの一実施例の動作を、スケジュール算出部２０における演算処理等を含めて詳細に説明する。
【００８３】
ここではまず、スケジュール算出部２０がスケジュール計算に用いる各種のパラメータを説明する。
【００８４】
図１に示されるように、スケジュール算出部２０の内部スケジュール算出部はスケジュール管理テーブルを備える。上記説明したように、スケジュール管理テーブルは、回線を新たに収容する場合における最適の位置“ＦＥＰ”を、ＰＣＲ値の種別“ＥＮ”（ここでは、１、２、４、８）毎に示すテーブルである。このテーブルに示される位置に各回線を収容することにより、各回線の送信のレートが保証される。
【００８５】
更に、スケジュール算出部２０は、セル読出順番管理テーブルの長さを示すエントリー総数“ＴＥＮ”と、回線が割り当て済みのセル読出順番管理テーブルの総数を示す使用エントリー総数“ＴＵＥＮ”と、回線が割り当て済みのセル読出順番管理テーブルの最後尾を示す最終ボックス番号“ＴＵＥＢ”を、パラメータとして備えてこれらの値を管理し、かつセル読出順番管理テーブルの更新に応じて最新の値にこの各パラメータを更新する。
【００８６】
例えば、図２の例においては、エントリー総数“ＴＥＮ”の値は“３２”であり、使用エントリー総数“ＴＵＥＮ”の値は“２１”であり、最終ボックス番号“ＴＵＥＢ”の値は“２４”である。
【００８７】
また、スケジュール算出部２０の処理を説明するために、“Ａ”、“Ｂ”、“Ｃ”、“Ｄ”、“Ｅ”、“Ｆ”を、内部パラメータを示す整数変数として用いる。
【００８８】
図４は、本実施例のスケジュールシステムによる、セル読出順番管理テーブル内に回線を新規に収容する処理を説明するためのフローチャートであり、図５は、セル読出順番管理テーブル内から回線を削除する処理を説明するためのフローチャートである。この各フローチャート内においては、カギ括弧を、括弧内の数値を小数点以下に切り捨てた値を示すために用いている（例えば、［５／２］＝２）。
【００８９】
回線収容の動作を、図４のフローチャートを用いて説明する。
【００９０】
回線収容動作においては、収容対象の回線のＰＣＲ値“ＥＮ”を基に、セル読出順番管理テーブル内に収容可能かどうかの収容判定を行う。収容対象の回線は、既に登録済みの回線の間の空き領域か、又は末尾の未使用領域に対して登録する。
【００９１】
まず、既にスケジュールされているセル読出順番管理テーブル内に、収容を要請された回線を、収容可能な空き領域が存在するかどうかを判定する（ステップ４０１）。
【００９２】
収容可能な回線相当の空き領域が存在すると判定された場合には、スケジュール管理テーブルから対応するデータ“ＦＥＰ”を読み出し、セル読出順番管理テーブル内の配置位置として決定し、これを配置する（ステップ４０２）。また、これによりセル読出順番管理テーブルが更新されたため、スケジュール管理テーブルに対しても、これに対応する更新処理を行う（ステップ４０３）。
【００９３】
空き領域の回線収容判定において、空き領域内に収容不可能と判定され、更にセル読み出し順序管理テーブル内の未使用領域への収容判定も（ステップ４０４）、不可能と判定された場合には（ステップ４０５）、当該回線の収容が不可能と判定し、回線収容処理を終了する。
【００９４】
ここで、空き領域内への収容が不可能の場合においても、もし、未使用領域への配置が可能と判定された場合には、未使用領域内の当該回線の収容が可能であり、かつ収容に適する（つまりＰＣＲ値の整数倍の先である）位置を算出し（ステップ４０６）、当該回線の収容位置として決定する（ステップ４０７）。回線収容位置の決定後には、スケジュール管理テーブルの更新処理を行う。
【００９５】
スケジュール管理テーブルの更新処理は、前述の各実施例に示される様に、各回線が所望の方式に従って配置されるように更新するのであり、この実施例においては、スケジュール算出部２０により次のように更新を実行する。
【００９６】
まず、回線収容後に新しくできた空き領域を管理するためのパラメータを、図５に示す様に更新する（ステップ４０８〜４１４）。
【００９７】
即ち、回線収容後の空き領域を計算してこれをパラメータ“Ｃ”に代入し（ステップ４０８）、収容した回線のＰＣＲ値“ＥＮ”よりも、帯域の小さな回線から降順に以下の処理を逐次実施する（ステップ４０９）。
【００９８】
まず、当該ＰＣＲ値の回線の、計算した空き領域内への収容可否判定を実施し（ステップ４１０、４１１）、収容可能と判定された場合には、配置位置及び空き領域の更新処理を行い（ステップ４１２）、当該ＰＣＲ値“ＥＮ”の回線の配置位置“ＦＥＰ”としてスケジュール管理テーブルに登録する（ステップ４１３）。
【００９９】
収容可否判定にて、収容不可と判定し、更にコネクションが最後である（つまり、ＰＣＲ値が“１”）と判定された場合には（ステップ４１４）、使用エントリー総数“ＴＵＥＮ”及び最終ボックス番号“ＴＵＥＢ”の更新処理（ステップ４１５）を行い回線収容処理を完了する。
【０１００】
次に、回線削除動作を、図５のフローチャートを用いて説明する。
【０１０１】
回線削除動作においては、まず、回線削除要求があった回線を、当該回線の配置位置“ＳＯＥ”から削除する（ステップ５０１）。
【０１０２】
次に、回線削除に伴うセル読み出し順序管理テーブル内の、既にスケジュール済みの各回線の配置移動処理を、以下のように場合分けをして説明する。
【０１０３】
ここで削除された回線分の空き領域が、セル読み出し管理テーブル内に存在しているかどうかを判定し（ステップ５０３）、もし存在する場合には、図７に示す様に配置移動に伴う位置補正値を算出する（ステップ５０４〜５０７）。ここで、該当回線分の空き領域は、ステップ５０５の条件により図７に示す状態である。従って、配置移動後の配置位置は、それぞれステップ５０６又はステップ５０７の様に補正する。
【０１０４】
位置補正値の算出後は、図８に示す様に移動対象の回線を移動する（ステップ５０８、５０９）。ただし、ステップ５０８の条件が成立するのは、移動対象の回線と削除された回線の長さが一致する場合であり、そうでない場合には回線の移動を行わずに分岐する。
【０１０５】
配置移動処理が行われた場合には、配置位置移動により生じたセル読み出し順序管理テーブルの更新に伴い、図９に示す様にスケジュール管理テーブルの各値を更新する（ステップ５１０〜５１６）。スケジュール管理テーブルの更新処理では、もし空き領域が移動処理により配置移動された場合には（ステップ５１１、５１２）、そのスケジュール管理テーブル内の配置位置を補正するのである（ステップ５１３）。そして上記更新処理を、回線のＰＣＲ値降順に逐次実施する（ステップ５１５）。
【０１０６】
この移動処理終了後には、更に大きな空き領域が確保され、その結果、より帯域の大きな回線の配置移動が可能になる場合がある。この場合には、該当回線のＰＣＲ値を更新して上記手順を再び実施することで実施可能となる（ステップ５１６）。
【０１０７】
また、ステップ５０３の分岐において、セル読出順番管理テーブル内に該当回線分の空き領域がない場合には、次回線収容位置を更新し（ステップ５１７）、配置移動判定を行う（ステップ５１８）。即ち、回線削除処理後（ステップ５１８）、回線の配置移動ができず、又最終ボックス番号“ＴＵＥＢ”の変更も起こらない場合には、使用エントリー総数を更新して回線削除処理を完了する（ステップ５２８）。
【０１０８】
他方、回線削除により配置移動を伴う場合には、移動処理を実施する（ステップ５２０）。ただし、削除対象となる回線が最終ボックス番号の最後尾に配置されている様な場合には、移動処理は実施されない（ステップ５１９）。配置移動処理後におけるスケジュール管理パラメータの更新処理（ステップ５２１〜５２６）は、ステップ５１０〜５１６と同様である。
【０１０９】
スケジュール管理パラメータ更新処理終了後、使用エントリー総数“ＴＵＥＮ”及び最終ボックス番号“ＴＵＥＢ”を更新し回線削除処理を完了する（ステップ５２７）。
【０１１０】
以上説明されたように、本実施の形態のスケジュールシステムは、セル読出順番管理テーブルにおける各回線の位置を、簡易な処理により適切に割り当てることができる。
【０１１１】
また、本実施の形態において、セル読出順番管理テーブルの各位置の回線をタイムスロットに変換する方法として、図１２、図１３の例に示される変換方法を用いるものとして説明したが、各回線をそのＰＣＲ値の整数倍の位置の先から連続して確保した場合に、タイムスロットに均等の間隔で分散される変換方法は、これに限られるものではなく、図１２、図１３は変換方法の１つの例を示すものである。
【０１１２】
しかし、本実施の形態のスケジュールシステムによるセル読出順番管理テーブルのスケジューリング方法は、以上説明されたいずれの実施例においても、タイムスロットへの変換方法に影響されることはなく、上記のタイムスロットへの変換の条件を満たす他の変換方法を採用した場合においても、同じ効果を得ることができる。
【０１１３】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【０１１４】
【発明の効果】
以上説明したように本発明のスケジュールシステムによれば、以下のような効果が達成される。
【０１１５】
本発明のスケジュールシステムは、ＡＴＭ回線のレートを保証しセルの転送を管理するためのセル読出順番管理テーブルにおいて、スケジュール管理テーブルを参照することにより、各回線の位置をそのＰＣＲ値に基づいて適切に決定するすることができる。このため、従来における、ＰＣＲ値の降順に整列させる条件や、途中に空き領域を作らない等の条件が不要となり、適切にかつより柔軟にスケジューリングが実現される。
【０１１６】
従来のスケジュールシステムでは、各ＡＴＭ回線のレートを保証するために、回線の新規収容又は回線削除時等において、ＰＣＲ値の降順に、かつ途中に空き領域がないようにスケジュールを行うものであった。このため、従来では回線の新規収容等や回線削除等が発生する度に、各回線を整列させて並べ替える面倒な更新処理を必要としていた。
【０１１７】
本発明のスケジュールシステムを用いることにより、このような回線の新規収容等の度の整列の処理等の殆どが不要となるのである。
【０１１８】
図１０と図１１は、本発明と従来の、回線の新規収容及び削除が繰り返し実施された場合における処理を比較した図であり、上から順に、左側の欄に示されたコネクションの追加や削除を行う同一の処理を、双方が順次実行している。これにより、本発明のスケジューリングシステムでは、従来に比較し配置移動の対象が大幅に削減されていることが示されている。
【０１１９】
例えば、新規に回線を収容する場合においては、従来では当該コネクションのＰＣＲ値と同等な他コネクションの一部及び、より小さなＰＣＲ値を有する全てのコネクションを移動させる必要があるのに対して、本発明のスケジューリングシステムでは、各コネクションを移動させる必要がない。
【０１２０】
また一方で、回線を削除する場合においては、従来では当該コネクションのＰＣＲ値と同等な他コネクションの一部及び、より小さなＰＣＲ値を有する全てのコネクションを移動させる必要があるのに対して、本発明のスケジューリングシステムにおいて移動させるコネクションは、当該コネクションのＰＣＲ値と同等又はより大きなＰＣＲ値を有するコネクションの１つのみである。
【０１２１】
更に、セル読出順番管理テーブル内における未使用領域を比較した場合においても、従来の方式によるものと比較して問題はない。
【０１２２】
この点は、図１０及び図１１における、セル読出順番管理テーブル内の未使用の領域の、（２のべき乗を成す）ＰＣＲ値を備える回線数への換算を示す表を参照すると、本発明のスケジューリングシステムは、この実施例の各ステップにおいて従来と同様の量の回線を新たに収容することができることが示されている。
【０１２３】
以上説明したように、本発明のスケジューリングシステムを用いることにより、従来と同様の回線の収容率を実現しながら、スケジューリングのための処理を大幅に削減することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態によるスケジュールシステムの構成を示すブロック図である。
【図２】本発明の第１の実施の形態のセル読出順番管理テーブルの一例を示す図である。
【図３】本発明の第１の実施の形態のスケジュール管理テーブルの一例を示す図である。
【図４】本発明の第１の実施の形態の回線収容処理の一実施例を説明するためのフローチャートである。
【図５】本発明の第１の実施の形態の回線削除処理の一実施例を説明するためのフローチャートである。
【図６】本発明の第１の実施の形態の空き領域を管理するパラメータの更新の一実施例を説明するための図である。
【図７】本発明の第１の実施の形態の配置移動に伴う位置補正値の算出の一実施例を説明するための図である。
【図８】本発明の第１の実施の形態の移動対象回線の移動の一実施例を説明するための図である。
【図９】本発明の第１の実施の形態のスケジュール管理パラメータの配置位置の補正の一実施例を説明するための図である。
【図１０】本発明の第１の実施の形態のセル読出順番管理テーブルのスケジューリングの一実施例を示す図である。
【図１１】従来のセル読出順番管理テーブルのスケジューリングの一実施例を示す図である。
【図１２】セル読出順番管理テーブルの各位置をタイムスロット内の位置に変換する方法の一計算例を示す図である。
【図１３】図１２の計算方法による変換結果の一覧を示す図である。
【図１４】各セルをタイムスロット内の分散された位置に割り当てるスケジューリングの処理の一例を説明するための図である。
【図１５】従来の、セル読出順番管理テーブルにおいて回線の降順の並びが崩れた場合におけるセルの読出しを説明する図である。
【図１６】従来のスケジュールシステムの構成を示すブロック図である。
【符号の説明】
１００  スケジュールシステム
１００ａ  従来のスケジュールシステム
１０  回線設定インタフェース
２０  スケジュール算出部
２０ａ  従来のスケジュール算出部
３０  配置処理部
４０  タイムスロット
５０  コネクション入力キュー
６０  シェーピングサービス出力キュー
【図１】
0003596603.tif 000002
【図２】
0003596603.tif 000003
【図３】
0003596603.tif 000004
【図４】
0003596603.tif 000005
【図５】
0003596603.tif 000006
【図６】
0003596603.tif 000007
【図７】
0003596603.tif 000008
【図８】
0003596603.tif 000009
【図９】
0003596603.tif 000010
【図１０】
0003596603.tif 000011
【図１１】
0003596603.tif 000012
【図１２】
0003596603.tif 000013
【図１３】
0003596603.tif 000014
【図１４】
0003596603.tif 000015
【図１５】
0003596603.tif 000016
【図１６】
0003596603.tif 000017