(57)【特許請求の範囲】
【請求項１】
各コネクションの識別子情報および帯域情報ならびに各コネクションの理想的なセル送出タイミングの揺らぎ許容値情報の組を記録するコネクション情報保持手段と、
指定されたポリシに基づいて前記コネクション情報保持手段に記録されたコネクション情報の組を並べ替えるコネクション情報ソート手段と、
スケジューリングテーブル上のタイムスロット毎に配置され当該タイムスロットに割当てられたコネクションを識別するとともに各コネクションごとの前記許容値情報が設定されたコネクション識別手段と、
各タイムスロットに配置するコネクションのコネクション識別手段をタイムスロット毎にリスト状に接続して管理する手段と、
各コネクションが要求するセル出力タイミングの予約を受け付けて前記コネクション識別手段を配置するタイムスロット管理手段と、
このタイムスロット管理手段に対して各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置を予約する手段と、
スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段を重複して予約配置したときにこれを異なるタイムスロットに分散させる手段と
を含むスケジューリング手段を備え、
このスケジューリング手段のスケジューリング結果にしたがってセルを読出す手段を備え、
前記コネクション情報ソート手段は、各コネクションの帯域情報を参照し広帯域のものから順にソートする手段を備え、
前記タイムスロット管理手段は、このソートする手段のソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付ける手段を備え、
前記分散させる手段は、前記受け付ける手段の受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段を重複して予約配置したときには、前記許容値が昇順になるように前記コネクション識別手段を並び替える第一のステップと、並び替えられたリストの２番目以降の前記コネクション識別手段を隣接する後方のタイムスロットへスライドし、スライドした前記コネクション識別手段の前記許容値をスライドしたタイミング分ずつ減少させる第二のステップとを実行し、このときに、既にこの後方のタイムスロットに他の前記コネクション識別手段が配置されているときには、再度、前記第一および第二のステップを実行する手段を備えた
ことを特徴とするセル読出スケジューリング装置。
【請求項２】
各コネクションの帯域情報を参照し広帯域のものから順にソートし、このソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付け、
スケジューリングテーブル上のタイムスロットにはそれぞれ当該タイムスロットを予約したコネクションを識別するためのコネクション識別手段を配置し、
各タイムスロットに配置するコネクションのコネクション識別手段をタイムスロット毎にリスト状に接続して管理し、
スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段を重複して予約配置したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続したコネクション識別手段のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ、このときに、既にこの後方のタイムスロットに他の前記コネクション識別手段が配置されているときには、この他の前記コネクション識別手段を前方よりスライドさせた前記コネクション識別手段のリストの最後尾に移し、この結果として各タイムスロットに配置されたコネクション識別手段の数を０または１に限定し、これによりセル読出タイムスロットを決定する
セル読出スケジューリング方法であって、
各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした理想的なタイムスロット配置を予約する際に、配置する前記コネクション識別手段に対して対応するコネクション帯域情報のタイムスロット揺らぎ許容値を設定し、
リスト状に接続された前記コネクション識別手段を分散して配置揺らぎ許容範囲内のタイムスロットに配置するときに、リストに含まれる前記コネクション識別手段が示すコネクションの前記許容値の情報を参照し、前記許容値が昇順になるように前記コネクション識別手段を並び替える第三のステップと、並び替えられたリストの２番目以降のものを隣接する後方のタイムスロットへスライドし、スライドした前記コネクション識別手段の前記許容値をスライドしたタイミング分ずつ減少させる第四のステップとを実行し、このときに既に後方のタイムスロットに前記コネクション識別手段が配置されているときには、再び、前記第三および第四のステップを実行する
ことを特徴とするセル読出スケジューリング方法。
【請求項３】
スケジューリング単位として単一のコネクションを扱っている部分の代わりに、一つ以上のコネクションにより構成されるコネクショングループをスケジューリング単位として扱う請求項２記載のセル読出スケジューリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数のコネクションを単一の回線に多重する装置（例えばＡＴＭ(Asynchronous Transfer Mode:非同期転送モード)ノード装置）に利用する。特に、各コネクションが必要とする出力帯域を、設定されたセル送出間隔揺らぎの許容範囲内で使用する技術に関する。
【０００２】
【従来の技術】
ＡＴＭ網を構成するノード装置では、複数の入力回線から入力されたセルを単一の出力回線に多重する場合に、これを実現する方法の一つとして、各々の入力回線に対応するセルキューを用意し、各入力回線が要求する帯域幅に応じた頻度でセルキューからセルを周期的に読出し、出力回線にセルを送出するという手法が用いられる。このとき、設定帯域の異なる各セルキューからセルを周期的に読出すアルゴリズムとしては、例えばＷＲＲ(Weighted Round Robin)方式などがある。
ＷＲＲ方式では、読出対象のセルキューに設定帯域幅に比例した重み付けを行い、１周期の間に各セルキューからこの重み分の数のセル読出しを行う。この仕組みにより、いずれのセルキューも設定帯域にしたがって公平な出力帯域を確保することを期待できる。
【０００３】
しかしながら、ＷＲＲ方式でセル多重を行うとき、多重される各コネクションのセル送出間隔は、１周期内の各セルキューからのセル読出方法に依存する。各コネクションのセルの送出間隔を一定に保とうとするならば、セルキューからのセル読出しタイミングが周期内で一定になるようにし、かつ隣接する周期間でもセル読出間隔が一定になるようにする必要がある。
【０００４】
ところが多重するコネクション数が多い場合や多重された回線の帯域占有率が高い場合には、各コネクションのセル送出間隔は他のコネクションのセル送出状況に影響されることがある。つまり、複数のコネクションが同じタイミングでセルを出力しようとするとセル多重部でブロッキングが発生するため、出力できなかったコネクションのセル出力タイミングには遅延が発生する。そのため、多数のコネクションを高い帯域占有率で多重するときには、個々のコネクションが要求するセル送出間隔を守れない可能性がある。
【０００５】
このことは、ネットワーク内で高い回線品質を保つために厳密なセル送出間隔をスケジューリングしようとする場合に問題となる。よって、この問題を解決するためには、適切なセル読出スケジューリング手段が必要となる。
【０００６】
その一つとして、全コネクションの１周期内セル読出スケジュールをあらかじめ作成したタイミングスケジューリングテーブルにより決めておき、このテーブルに基づいてセル読出しを行う方法が用いられる。
【０００７】
なお、このスケジューリングテーブルはセル送出するタイミングであるタイムスロット１周期分により構成されており、
（ａ）各コネクションの帯域幅に比例してタイムスロットを割当てる。
（ｂ）各コネクションに割当てるタイムスロットが１周期内に複数存在する場合には、周期内で偏在することなく一定の間隔で配置する。
（ｃ）複数周期で見たときにも、タイムスロットの配置間隔が一定の間隔になるように配置する。
（ｄ）各タイムスロット周期間隔は、割当て帯域から計算される理想的な配置位置に対し、一定の許容範囲を持つ。
というものであるとする。
【０００８】
このスケジューリングテーブルを作成する方法の例として下記の手順がある。まず、（タイムスロット数）×（コネクション数）の配列を用意し、これをスケジューリング配列とする。乱数により各コネクションの初期配置タイムスロット（先頭のタイムスロット）を決定したら、配列の該当する位置をマークする。初期配置タイムスロットが決まったら、そこを基準にして理想間隔によりその後のセル送出タイミングを示すタイムスロットを決定し、スケジューリング配列にマークする。これを１周期分繰り返す。しかし、初期配置タイムスロットは乱数によって決めているため１周期の先頭に位置するわけではない。そこで、配列として与えられている最終位置のタイムスロットの次には先頭位置のタイムスロットに戻るような操作を行う。これにより、初期配置タイムスロットを起点として１周期分のタイムスロットが連続した配列を想定することができる。全てのコネクションについて同様の操作を繰り返し、スケジューリング配列を構築する。
【０００９】
スケジューリング配列が構築できたら、１周期の内で最初のタイムスロットより配置するコネクションを順に確定していく。各タイムスロットについて、全コネクションを順に検索していき、スケジューリング配列内でマーキングされたコネクションが複数存在している場合には、コネクション毎に前回のタイムスロット割当位置を基準とした理想間隔からどれくらいずれているかを計算する。そして最もずれの大きいコネクションをタイムスロットに配置する。また、ずれが同じ大きさだった場合には帯域幅の大きなコネクションを優先して配置する。この操作を全タイムスロットについて繰り返し、全てのタイムスロットに重複して配置されたタイムスロットがなくなるようにする。以上の操作によりスケジューリングテーブルを作成できる。
【００１０】
【発明が解決しようとする課題】
従来の技術では、扱う対象となるコネクション数が多くなればなるほどスケジューリングのための計算処理が複雑になり、スケジューリングテーブル作成のために多大な時間がかかることになる。いくら特性の良いスケジューリングテーブルであっても、生成に膨大な時間を必要とするものでは実用的ではない。よって、より高速にスケジューリングテーブルを生成可能とする手段を有することが必要である。
【００１１】
また、タイムスロット配置位置揺らぎ許容値がコネクション毎に異なった場合などへの対応が難しい等、拡張性に乏しいという欠点がある。
【００１２】
本発明は、このような背景に行われたものであって、従来のスケジューリング方法と同等またはそれ以上の特性を有するスケジューリングテーブルを従来よりも高速に生成することができるセル読出スケジューリング装置および方法を提供することを目的とする。本発明は、コネクション個別のタイムスロット配置位置揺らぎ許容値の導入に対応することができるセル読出スケジューリング装置および方法を提供することを目的とする。
【００１３】
【課題を解決するための手段】
本発明の第一の観点はセル読出スケジューリング装置であって、本発明の特徴とするところは、各コネクションの識別子情報および帯域情報の組を記録するコネクション情報保持手段と、指定されたポリシに基づいて前記コネクション情報保持手段に記録されたコネクション情報の組を並べ替えるコネクション情報ソート手段と、スケジューリングテーブル上のタイムスロット毎に配置され当該タイムスロットに割当てられたコネクションを識別するコネクション識別手段と、各タイムスロットに配置するコネクションのコネクション識別手段をタイムスロット毎にリスト状に接続して管理する手段と、各コネクションが要求するセル出力タイミングの予約を受け付けて前記コネクション識別手段を配置するタイムスロット管理手段と、このタイムスロット管理手段に対して各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置を予約する手段と、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段を重複して予約配置したときにこれを異なるタイムスロットに分散させる手段とを含むスケジューリング手段を備え、このスケジューリング手段のスケジューリング結果にしたがってセルを読出す手段を備えたところにある。
【００１４】
すなわち、本発明では、スケジューリングテーブルを作成する際にスケジューリング配列の参照回数を減らすため、スケジューリングテーブル上にタイムスロットを予約したコネクション識別手段を例えば接続するコネクション識別手段を示すポインタによって関連付け、効率的な参照を行う。このことによりスケジューリング配列の参照回数を減少させることができる。
【００１５】
タイムスロット予約用のコネクション情報をポインタによって接続するリスト構造で扱うことから、タイムスロットの配置位置のスライドをポインタの付替えにより実現する。このことにより複数のコネクションが同一のタイムスロットを予約した場合のタイムスロット配置処理を高速に実行することができる。
【００１６】
さらに詳しくは、前記コネクション情報ソート手段は、各コネクションの帯域情報を参照し広帯域のものから順にソートする手段を備え、前記タイムスロット管理手段は、このソートする手段のソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付ける手段を備え、前記分散させる手段は、この受け付ける手段の受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段を重複して予約配置したときには、リスト状に接続した前記コネクション識別手段のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ、このときに、既にこの後方のタイムスロットに他の前記コネクション識別手段が配置されているときには、この他の前記コネクション識別手段を前方よりスライドさせた前記コネクション識別手段のリストの最後尾に移す手段を備えることが望ましい。
【００１７】
また、前記コネクション情報保持手段は、各コネクションの理想的なセル送出タイムスロットの揺らぎ許容値情報を併せて記録する手段を含み、前記コネクション識別手段に当該許容値情報が設定され、前記分散させる手段は、前記受け付ける手段の受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段を重複して予約配置したときには、前記許容値が昇順になるように前記コネクション識別手段を並び替える第一のステップと、並び替えられたリストの２番目以降の前記コネクション識別手段を隣接する後方のタイムスロットへスライドし、スライドした前記コネクション識別手段の前記許容値をスライドしたタイミング分ずつ減少させる第二のステップとを実行し、このときに、既にこの後方のタイムスロットに他の前記コネクション識別手段が配置されているときには、再度、前記第一および第二のステップを実行する手段を備えることができる。
【００１８】
すなわち、タイムスロット予約用のコネクション情報に配置位置揺らぎ許容値を与え、スケジューリングテーブル上のスライド処理に移動範囲を設定し、コネクション情報のリスト長により管理する。これによりコネクション毎に異なる配置位置揺らぎ許容値を設定することができる。
【００１９】
タイムスロット予約用のコネクション情報の配置位置揺らぎ許容値の値によりリストの要素を昇順に並び替える。これにより多重する複数のコネクションがそれぞれ異なる配置位置揺らぎ許容値を持つときの多重効率が向上する。
【００２０】
本発明の第二の観点はセル読出スケジューリング方法であって、本発明の特徴とするところは、各コネクションの帯域情報を参照し広帯域のものから順にソートし、このソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付け、スケジューリングテーブル上のタイムスロットにはそれぞれ当該タイムスロットを予約したコネクションを識別するためのコネクション識別手段を配置し、各タイムスロットに配置するコネクションのコネクション識別手段をタイムスロット毎にリスト状に接続して管理し、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段を重複して予約したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続したコネクション識別手段のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ、このときに、既にこの後方のタイムスロットに他の前記コネクション識別手段が配置されているときには、この他の前記コネクション識別手段を前方よりスライドさせた前記コネクション識別手段のリストの最後尾に移し、この結果として各タイムスロットに配置されたコネクション識別手段の数を０または１に限定し、これによりセル読出タイムスロットを決定するところにある。
【００２１】
また、前記コネクション識別手段の１番目が配置されているタイムスロットの前方に前記コネクション識別手段の２番目以降のものをスライドさせる余地がある場合には、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段を重複して予約配置したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続した前記コネクション識別手段のうちで２番目以降のものを隣接する前方または後方のタイムスロットにスライドさせ、このときに、既にこの前方または後方のタイムスロットに他の前記コネクション識別手段が配置されているときには、これを後方または前方よりスライドさせた前記コネクション識別手段のリストの最後尾に移し、この結果として各タイムスロットに配置された前記コネクション識別手段の数を０または１に限定し、これによりセル読出タイムスロットを決定することができる。これにより、タイムスロット配置の自由度がさらに向上する。
【００２２】
また、各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした理想的なタイムスロット配置を予約する際に、配置する前記コネクション識別手段に対して対応するコネクション帯域情報のタイムスロット揺らぎ許容値を設定し、リスト状に接続された前記コネクション識別手段を分散して近傍のタイムスロットに配置するときに、リストに含まれる前記コネクション識別手段が示すコネクションの前記許容値の情報を参照し、前記許容値が昇順になるように前記コネクション識別手段を並び替える第三のステップと、並び替えられたリストの２番目以降のものを隣接する後方のタイムスロットへスライドし、スライドした前記コネクション識別手段の前記許容値をスライドしたタイミング分ずつ減少させる第四のステップとを実行し、このときに既に後方のタイムスロットに前記コネクション識別手段が配置されているときには、再び、前記第三および第四のステップを実行することもできる。
【００２３】
スケジューリング単位として単一のコネクションを扱っている部分の代わりに、一つ以上のコネクションにより構成されるコネクショングループをスケジューリング単位として扱うこともできる。
【００２４】
本発明の第三の観点はプログラムであって、情報処理装置にインストールすることにより、その情報処理装置に、各コネクションの識別子情報および帯域情報の組を記録するコネクション情報保持機能と、指定されたポリシに基づいて前記コネクション情報保持機能に記録されたコネクション情報の組を並べ替えるコネクション情報ソート機能と、スケジューリングテーブル上のタイムスロット毎に配置され当該タイムスロットに割当てられたコネクションを識別するコネクション識別機能と、各タイムスロットに配置するコネクションのコネクション識別機能をタイムスロット毎にリスト状に接続して管理する機能と、各コネクションが要求するセル出力タイミングの予約を受け付けて前記コネクション識別機能を配置するタイムスロット管理機能と、このタイムスロット管理機能に対して各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置を予約する機能と、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約配置したときにこれを異なるタイムスロットに分散して配置する機能とを含むスケジューリング機能を実現させ、このスケジューリング機能のスケジューリング結果にしたがってセルを読出す機能を実現させることを特徴とする。
【００２５】
前記コネクション情報ソート機能は、各コネクションの帯域情報を参照し広帯域のものから順にソートする機能を備え、前記タイムスロット管理機能は、このソートする機能のソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付ける機能を備え、前記分散させる機能は、この受け付ける手段の受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約配置したときには、リスト状に接続した前記コネクション識別機能のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ、このときに、既にこの後方のタイムスロットに他の前記コネクション識別機能が配置されているときには、この他の前記コネクション識別機能を前方よりスライドさせた前記コネクション識別機能のリストの最後尾に移す機能を備えて実現させることが望ましい。
【００２６】
前記コネクション情報保持機能は、各コネクションの理想的なセル送出タイムスロットの揺らぎ許容値情報を併せて記録する機能を含み、前記コネクション識別機能に当該許容値情報が設定され、前記分散させる機能は、前記受け付ける機能の受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約配置したときには、前記許容値が昇順になるように前記コネクション識別機能を並び替える第一のステップと、並び替えられたリストの２番目以降の前記コネクション識別機能を隣接する後方のタイムスロットへスライドし、スライドした前記コネクション識別機能の前記許容値をスライドしたタイミング分ずつ減少させる第二のステップとを実行し、このときに、既にこの後方のタイムスロットに他の前記コネクション識別機能が配置されているときには、再度、前記第一および第二のステップを実行する機能を備えて実現させることが望ましい。
【００２７】
あるいは、本発明の第三の観点はプログラムであって、情報処理装置にインストールすることにより、その情報処理装置に、各コネクションの帯域情報を参照し広帯域のものから順にソートし、このソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付け、スケジューリングテーブル上のタイムスロットにはそれぞれ当該タイムスロットを予約したコネクションを識別するためのコネクション識別機能を配置し、各タイムスロットに配置するコネクションのコネクション識別機能をタイムスロット毎にリスト状に接続して管理し、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続したコネクション識別機能のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ、このときに、既にこの後方のタイムスロットに他の前記コネクション識別機能が配置されているときには、この他の前記コネクション識別機能を前方よりスライドさせた前記コネクション識別機能のリストの最後尾に移し、この結果として各タイムスロットに配置されたコネクション識別機能の数を０または１に限定し、これによりセル読出タイムスロットを決定する手順を実行させることを特徴とする。
【００２８】
前記コネクション識別機能の１番目が配置されているタイムスロットの前方に前記コネクション識別機能の２番目以降のものをスライドさせる余地がある場合には、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約配置したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続したコネクション識別機能のうちで２番目以降のものを隣接する前方または後方のタイムスロットにスライドさせ、このときに、既にこの前方または後方のタイムスロットに他の前記コネクション識別機能が配置されているときには、これを後方または前方よりスライドさせた前記コネクション識別機能のリストの最後尾に移し、この結果として各タイムスロットに配置された前記コネクション識別機能の数を０または１に限定し、これによりセル読出タイムスロットを決定する手順を実行させることが望ましい。
【００２９】
各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした理想的なタイムスロット配置を予約する際に、配置する前記コネクション識別機能に対して対応するコネクション帯域情報のタイムスロット揺らぎ許容値を設定し、リスト状に接続された前記コネクション識別機能を分散して近傍のタイムスロットに配置するときに、リストに含まれる前記コネクション識別機能が示すコネクションの前記許容値の情報を参照し、前記許容値が昇順になるように前記コネクション識別機能を並び替える第三のステップと、並び替えられたリストの２番目以降のものを隣接する後方のタイムスロットへスライドし、スライドした前記コネクション識別機能の前記許容値をスライドしたタイミング分ずつ減少させる第四のステップとを実行し、このときに既に後方のタイムスロットに前記コネクション識別機能が配置されているときには、再び、前記第三および第四のステップを実行する手順を実行させることが望ましい。
【００３０】
スケジューリング単位として単一のコネクションを扱っている部分の代わりに、一つ以上のコネクションにより構成されるコネクショングループをスケジューリング単位として扱うこともできる。
【００３１】
【発明の実施の形態】
本発明実施例のセル読出スケジューリング装置および方法を図１ないし図４を参照して説明する。図１は本発明実施例のセル読出スケジューリング装置のブロック構成図である。図２は本発明実施例のセル読出スケジューリング方法の手順を示すフローチャートである。図３はスケジューリングテーブル１周期におけるスケジューリングの概念図である。図４は理想位置からのずれの少ないスケジューリングテーブルを作成するために、スケジューリングテーブル作成を複数回実行する場合の手順を示すフローチャートである。
【００３２】
本発明の第一の観点はセル読出スケジューリング装置であって、本発明の特徴とするところは、図１に示すように、各コネクションの識別子情報および帯域情報の組を記録するコネクション情報保持手段１と、指定されたポリシに基づいてコネクション情報保持手段１に記録されたコネクション情報の組を並べ替えるコネクション情報ソート手段２と、スケジューリングテーブル上のタイムスロット毎に配置され当該タイムスロットに割当てられたコネクションを識別するコネクション識別手段３と、各タイムスロットに配置するコネクションのコネクション識別手段３をタイムスロット毎にリスト状に接続して管理するリスト管理手段４と、各コネクションが要求するセル出力タイミングの予約を受け付けてコネクション識別手段３を配置するタイムスロット管理手段５と、このタイムスロット管理手段５に対して各コネクションの先頭のタイムスロット（初期配置タイムスロット）およびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置を予約する初期配置タイムスロット予約手段６および理想配置タイムスロット予約手段７と、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションがコネクション識別手段３を重複して予約したときにはこれを異なるタイムスロットに分散して配置する配置タイムスロット分散手段８とを含むスケジューリング手段９を備え、このスケジューリング手段９のスケジューリング結果にしたがってセルを読出すセル読出手段１０を備えたところにある。
【００３３】
さらに詳しくは、コネクション情報ソート手段２は、各コネクションの帯域情報を参照し広帯域のものから順にソートし、タイムスロット管理手段５は、このコネクション情報ソート手段２のソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付け（図２のＳ１、Ｓ２の処理）、配置タイムスロット分散手段８は、この受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別手段３を重複して予約配置したときには、リスト状に接続したコネクション識別手段３のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ（図２のＳ３、Ｓ４の処理）、このときに、既にこの後方のタイムスロットに他のコネクション識別手段３が配置されているときには、この他のコネクション識別手段３を前方よりスライドさせたコネクション識別手段３のリストの最後尾に移す。
【００３４】
あるいは、図４のステップＳ５の処理として、コネクション情報保持手段１は、各コネクションの理想的なセル送出タイムスロットの揺らぎ許容値情報を併せて記録し、コネクション識別手段３に当該許容値情報が設定され、配置タイムスロット分散手段８は、タイムスロット管理手段５の受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションがコネクション識別手段３を重複して予約配置したときには、前記許容値が昇順になるようにコネクション識別手段３を並び替える第一のステップと、並び替えられたリストの２番目以降のコネクション識別手段３を隣接する後方のタイムスロットへスライドし、スライドしたコネクション識別手段３の前記許容値をスライドしたタイミング分ずつ減少させる第二のステップとを実行し、このときに、既にこの後方のタイムスロットに他のコネクション識別手段３が配置されているときには、再度、前記第一および第二のステップを実行する。その結果として、最も最大配置位置揺らぎの小さいスケジューリングテーブルを採用する。
【００３５】
本発明の第二の観点は、図１に示すセル読出スケジューリング装置に適用するセル読出スケジューリング方法であって、本発明の特徴とするところは、各コネクションの帯域情報を参照し広帯域のものから順にソートし、このソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付け、スケジューリングテーブル上のタイムスロットにはそれぞれ当該タイムスロットを予約したコネクションを識別するためのコネクション識別手段３を配置し、各タイムスロットに配置するコネクションのコネクション識別手段３をタイムスロット毎にリスト状に接続して管理し、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションがコネクション識別手段３を重複して予約したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続したコネクション識別手段３のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ、このときに、既にこの後方のタイムスロットに他のコネクション識別手段３が配置されているときには、この他のコネクション識別手段３を前方よりスライドさせたコネクション識別手段３のリストの最後尾に移し、この結果として各タイムスロットに配置されたコネクション識別手段３の数を０または１に限定し、これによりセル読出タイムスロットを決定するところにある。
【００３６】
コネクション識別手段３の１番目が配置されているタイムスロットの前方にコネクション識別手段３の２番目以降のものをスライドさせる余地がある場合には、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションがコネクション識別手段３を重複して予約配置したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続したコネクション識別手段３のうちで２番目以降のものを隣接する前方または後方のタイムスロットにスライドさせ、このときに、既にこの前方または後方のタイムスロットに他のコネクション識別手段３が配置されているときには、これを後方または前方よりスライドさせたコネクション識別手段３のリストの最後尾に移し、この結果として各タイムスロットに配置されたコネクション識別手段３の数を０または１に限定し、これによりセル読出タイムスロットを決定する。
【００３７】
さらに、各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした理想的なタイムスロット配置を予約する際に、配置するコネクション識別手段３に対して対応するコネクション帯域情報のタイムスロット揺らぎ許容値を設定し、リスト状に接続されたコネクション識別手段３を分散して近傍のタイムスロットに配置するときに、リストに含まれるコネクション識別手段３が示すコネクションの前記許容値の情報を参照し、前記許容値が昇順になるようにコネクション識別手段３を並び替える第三のステップと、並び替えられたリストの２番目以降のものを隣接する後方のタイムスロットへスライドし、スライドしたコネクション識別手段３の前記許容値をスライドしたタイミング分ずつ減少させる第四のステップとを実行し、このときに既に後方のタイムスロットにコネクション識別手段３が配置されているときには、再び、前記第三および第四のステップを実行する。
【００３８】
スケジューリング単位として単一のコネクションを扱っている部分の代わりに、一つ以上のコネクションにより構成されるコネクショングループをスケジューリング単位として扱うこともできる。
【００３９】
本発明の第三の観点はプログラムであって、本発明のセル読出スケジューリング装置は、情報処理装置としてのパーソナル・コンピュータ装置等に本発明のプログラムをインストールすることにより、そのパーソナル・コンピュータ装置等を本発明のセル読出スケジューリング装置に相応する装置とすることにより実現することができる。このパーソナル・コンピュータ装置等により、本発明のセル読出スケジューリング方法を実行させることができる。
【００４０】
すなわち、本発明のプログラムは、情報処理装置としてのパーソナル・コンピュータ装置等にインストールすることにより、そのパーソナル・コンピュータ装置等に、各コネクションの識別子情報および帯域情報の組を記録するコネクション情報保持機能と、指定されたポリシに基づいて前記コネクション情報保持機能に記録されたコネクション情報の組を並べ替えるコネクション情報ソート機能と、スケジューリングテーブル上のタイムスロット毎に配置され当該タイムスロットに割当てられたコネクションを識別するコネクション識別機能と、各タイムスロットに配置するコネクションのコネクション識別機能をタイムスロット毎にリスト状に接続して管理する機能と、各コネクションが要求するセル出力タイミングの予約を受け付けて前記コネクション識別機能を配置するタイムスロット管理機能と、このタイムスロット管理機能に対して各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置を予約する機能と、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約配置したときにこれを異なるタイムスロットに分散して配置する機能とを含むスケジューリング機能を実現させ、このスケジューリング機能のスケジューリング結果にしたがってセルを読出す機能を実現させることを特徴とする。
【００４１】
前記コネクション情報ソート機能は、各コネクションの帯域情報を参照し広帯域のものから順にソートする機能を備え、前記タイムスロット管理機能は、このソートする機能のソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付ける機能を備え、前記分散させる機能は、この受け付ける手段の受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約配置したときには、リスト状に接続した前記コネクション識別機能のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ、このときに、既にこの後方のタイムスロットに他の前記コネクション識別機能が配置されているときには、この他の前記コネクション識別機能を前方よりスライドさせた前記コネクション識別機能のリストの最後尾に移す機能を備えて実現させることができる。
【００４２】
前記コネクション情報保持機能は、各コネクションの理想的なセル送出タイムスロットの揺らぎ許容値情報を併せて記録する機能を含み、前記コネクション識別機能に当該許容値情報が設定され、前記分散させる機能は、前記受け付ける機能の受け付け結果を参照しスケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約配置したときには、前記許容値が昇順になるように前記コネクション識別機能を並び替える第一のステップと、並び替えられたリストの２番目以降の前記コネクション識別機能を隣接する後方のタイムスロットへスライドし、スライドした前記コネクション識別機能の前記許容値をスライドしたタイミング分ずつ減少させる第二のステップとを実行し、このときに、既にこの後方のタイムスロットに他の前記コネクション識別機能が配置されているときには、再度、前記第一および第二のステップを実行する機能を備えて実現させることができる。
【００４３】
本発明のプログラムによって、パーソナル・コンピュータ装置を本発明のセル読出スケジューリング装置に相応する装置とすることにより、そのパーソナル・コンピュータ装置に、各コネクションの帯域情報を参照し広帯域のものから順にソートし、このソート順にしたがって各コネクションから先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした各コネクションの理想的なタイムスロット配置の予約を受け付け、スケジューリングテーブル上のタイムスロットにはそれぞれ当該タイムスロットを予約したコネクションを識別するためのコネクション識別機能を配置し、各タイムスロットに配置するコネクションのコネクション識別機能をタイムスロット毎にリスト状に接続して管理し、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続したコネクション識別機能のうちで２番目以降のものを隣接する後方のタイムスロットにスライドさせ、このときに、既にこの後方のタイムスロットに他の前記コネクション識別機能が配置されているときには、この他の前記コネクション識別機能を前方よりスライドさせた前記コネクション識別機能のリストの最後尾に移し、この結果として各タイムスロットに配置されたコネクション識別機能の数を０または１に限定し、これによりセル読出タイムスロットを決定する手順を実行させることを特徴とする。
【００４４】
前記コネクション識別機能の１番目が配置されているタイムスロットの前方に前記コネクション識別機能の２番目以降のものをスライドさせる余地がある場合には、スケジューリングテーブル上の１つのタイムスロットに対して複数のコネクションが前記コネクション識別機能を重複して予約配置したときには、スケジューリングテーブル上の１つのタイムスロットに対してリスト状に接続したコネクション識別機能のうちで２番目以降のものを隣接する前方または後方のタイムスロットにスライドさせ、このときに、既にこの前方または後方のタイムスロットに他の前記コネクション識別機能が配置されているときには、これを後方または前方よりスライドさせた前記コネクション識別機能のリストの最後尾に移し、この結果として各タイムスロットに配置された前記コネクション識別機能の数を０または１に限定し、これによりセル読出タイムスロットを決定する手順を実行させることができる。
【００４５】
各コネクションの先頭のタイムスロットおよびこの先頭のタイムスロットを起点とした理想的なタイムスロット配置を予約する際に、配置する前記コネクション識別機能に対して対応するコネクション帯域情報のタイムスロット揺らぎ許容値を設定し、リスト状に接続された前記コネクション識別機能を分散して近傍のタイムスロットに配置するときに、リストに含まれる前記コネクション識別機能が示すコネクションの前記許容値の情報を参照し、前記許容値が昇順になるように前記コネクション識別機能を並び替える第三のステップと、並び替えられたリストの２番目以降のものを隣接する後方のタイムスロットへスライドし、スライドした前記コネクション識別機能の前記許容値をスライドしたタイミング分ずつ減少させる第四のステップとを実行し、このときに既に後方のタイムスロットに前記コネクション識別機能が配置されているときには、再び、前記第三および第四のステップを実行する手順を実行させることができる。
【００４６】
スケジューリング単位として単一のコネクションを扱っている部分の代わりに、一つ以上のコネクションにより構成されるコネクショングループをスケジューリング単位として扱うこともできる。
【００４７】
以下では、本発明実施例をさらに詳細に説明する。
【００４８】
（第一実施例）
以下、本発明第一実施例について説明する。
【００４９】
まず、各コネクションに、割当て帯域にしたがってスケジューリングテーブル１周期内のセル配置数および理想セル出力間隔を計算する。計算した各コネクションのタイムスロットの１周期分をこのコネクションのタイムスロット群と呼ぶとすると、このタイムスロット群のスケジューリングテーブルへの配置開始位置は任意であるから、タイムスロットの全分布が均一になるようにタイムスロット群の配置開始位置を決める。
【００５０】
タイムスロット位置を均一配置するために有効なタイムスロット群配置開始位置決定手段としては、タイムスロット群に含まれるタイムスロット数の多いコネクションから順に割当てを行うこと、含まれるタイムスロット数の同じタイムスロット群は、配置開始位置を均等にずらして配置することなどがあげられる。
【００５１】
なお、各タイムスロットにはそれぞれ単一のコネクションしか割当てることができないが、上記の方法では単一のタイムスロットに複数のコネクションが割当てられることがある。そこで、理想セル出力間隔で配置されたタイムスロット位置を配置位置揺らぎ許容範囲内でずらすことにより、タイムスロットへのコネクション割当ての重複を回避する。
【００５２】
図５は上記に示した方法に基づいて、各コネクションの理想セル出力間隔に対応したセル出力タイミングをｍ×ｎ配列にマッピングしたものである。ここではコネクション数はｍ、スケジューリングテーブル１周期分のタイムスロット数はｎであるものとする。しかし、各コネクションのセル出力タイムスロットは計算される理想的な間隔で配置されており、複数のコネクション間で同一のタイムスロットを共有してしまっている部分がある。
【００５３】
これよりスケジューリングテーブルを生成するために、配置用リストを構築する配列（図６、図７）を用意する。図６および図７の配列は、それぞれがセル配置可能なタイムスロット数の要素により構成される。以降、図６の配列をタイムスロット配列、図７の配列をコネクション配列と呼ぶ。
【００５４】
タイムスロット配列はスケジューリングテーブルのタイムスロット位置に対応する。この配列はポインタのフィールドを有し、タイムスロット位置に対応した要素のポインタが該当するコネクション配列の要素を指し示す。また、論理的にはリング状の構造を有しており、最後の要素の次には先頭の要素に戻って連続しているものとする。
【００５５】
一方、コネクション配列は各コネクションＩＤのフィールドおよびポインタのフィールドを有する。タイムスロット配列のポインタにより指し示される。また、同一のタイムスロットに複数のコネクションが割当てられている場合に該当するコネクション（コネクション配列の要素）をリスト構造で指し示すために、ポインタを保持している。なお初期状態では、タイムスロット配列およびコネクション配列の全要素に初期値（例えば０）が設定されている。
【００５６】
図５の例にしたがい、各コネクションの理想タイムスロット位置を計算する。コネクション＃１はタイムスロット１が理想位置なので、タイムスロット配列の１番目の要素のポインタ値を参照する。しかし、この要素には初期値（＝０）が設定されているので、まだコネクションが配置されていないことがわかる。よって、コネクション配列の未使用の要素にコネクションＩＤを書き込み、その配列の要素番号をタイムスロット配列の１番目の要素にポインタとして書き込む。この時点では、タイムスロット配列の先頭の要素は（１）になっており、コネクション配列の先頭の要素は（１：０）になっている。また、コネクション＃１はタイムスロット５も理想位置なので、タイムスロット配列の５番目の要素を検索し、同様にタイムスロット配列の要素は（２）、コネクション配列の２番目の要素には（１：０）と書き込む。
【００５７】
コネクション＃１のタイムスロット位置の計算が全て終了したら、次のコネクションの計算を行う。コネクション＃２もタイムスロット１に配置されているので（図５）、まずタイムスロット配列の１番目の要素を参照する。しかし、１番目の要素のポインタが初期値（＝０）ではないので、既に別のコネクションが配置されていることがわかる。そこで、このポインタで示されるコネクション配列を参照する。ここではタイムスロット配列の１番目の要素のポインタ値は（１）なので、コネクション配列の１番目の要素を参照することになる。
【００５８】
コネクション配列の１番目の要素は（１：０）となっていることから、コネクション＃１が既に配置されており、ポインタ値が初期値であることからそれ以外のコネクションは配置されていないことがわかる。よって、空いているコネクション配列の要素にコネクションＩＤを書き込み、その配列の要素番号を先程参照したコネクション配列のポインタ値として書き込む。つまり、１番目の要素は（１：３）となる。
【００５９】
この時点の各配列の内容は、図８に示すとおりである。以降、同様の操作を全てのコネクションについて行う。また概念的には、図９のような終端要素のポインタ値が（０）になるリスト構造のデータを構築することになる。以降の説明はこのリスト構造を用いて行う。
【００６０】
全てのコネクションの配置が終了したら、作成したタイムスロット配列、コネクション配列をもとにして、タイムスロットにコネクションＩＤを配置していく。
【００６１】
該当するタイムスロットにコネクションＩＤが一つしか割当てられていなければ、そのまま配置するが、二つ以上のコネクションＩＤが割当てられている場合には、ポインタで繋がれたリストの二つ目以降の要素を次のタイムスロット配列の要素にポインタを接続しなおす。ただし、移動するコネクション配列要素は移動先のコネクション配列要素よりも前にリンクする。これはタイムスロット位置の理想配置位置からのずれの最大値を小さく抑えるためである。図１０にこの手順を示す。
【００６２】
前述したとおり、タイムスロット配列はリング構造を有しているので、最後の配列要素に複数のコネクションＩＤが割当てられている場合には、後方のコネクション配列要素はタイムスロット配列の先頭要素にシフトすることになる。この操作により、スケジューリングテーブルの終端部と先頭部との接続もシームレスに行うことができる。図１１にこの手順を示す。
【００６３】
上記の手順において、コネクション配列の要素がリンク構造により複数接続されることがあるが、このコネクション配列要素の接続数の最大値は理想配置位置からのずれの最大値に一致する。よって、この配列要素の最大値を監視することにより、あらかじめ規定したセル配置位置揺らぎの許容値を超えるか否かを判断することが可能である。例えば、図１２の配置の場合には、最大セル配置位置揺らぎは３セル分であり、セル配置位置揺らぎ許容値を２セルとするならば、（１８：０）のタイムスロットはセル配置位置揺らぎ許容値を超えるためセル配置位置違反となる。
【００６４】
上記手順を繰り返すことにより、最終的には全てのコネクション配列要素をタイムスケジューリング要素に対して１対１で対応付けすることができる。このタイムスロット位置とコネクションＩＤとの組み合わせは、スケジューリングテーブルとして用いることが可能である。
【００６５】
生成されたスケジューリングテーブルの特性の判断基準の一つとして、最大セル配置位置揺らぎを用いることができる。この値は、初めに行う各コネクションのテーブル割当て処理（図５）により変動する。そこで複数のパターンを生成し、それぞれのパターンについて上記のスケジューリングテーブル配置処理を行い、最大セル配置位置揺らぎを比較することで、よりセル配置位置揺らぎの小さいスケジューリングテーブルを生成することが可能である。
【００６６】
（第二実施例）
本発明第一実施例では、全てのコネクションに対して同一の最大セル配置位置揺らぎ許容値が設定されていたが、複数の揺らぎ許容値を設定する必要がある場合には、配置位置の揺らぎをより厳密に管理する必要がある。
【００６７】
本例では、図１３に示すとおり、コネクション配列に配置位置揺らぎ許容値フィールドを拡張する。このフィールドには、計算により算出される理想配置位置に対して許容される最大のずれを設定する。
【００６８】
各コネクション毎に計算された理想配置位置をタイムスロット配列およびコネクション配列毎にマッピングする操作については、上記拡張によらないので、第一実施例と同様の操作を行う。ただし、設定されたコネクション配列には、コネクションＩＤの他に、各コネクション毎に設定された配置位置揺らぎ許容値が設定されているものとする。
【００６９】
第一実施例では、全コネクションについて配置位置揺らぎ許容値が同一であったため、一つのタイムスロットに対して複数のコネクションＩＤが割当てられていた場合に、その連続する配列要素数のみしか管理しなかった。しかし、第二実施例では、各コネクション毎に配置位置揺らぎ許容値が異なるため、第一実施例のような単純シフト処理を行うことはできない。そこで、タイムスロット配列要素に複数のコネクション配列要素が連なっている場合には、各コネクション配列要素に設定された配置位置揺らぎ許容値の小さいものから順に並び替え操作を行う（図１４）。
【００７０】
このとき、各コネクション配列要素の当該タイムスロット配列における順番が、各コネクション配列要素の配置位置揺らぎ許容値を超えないことを監視する必要がある。もし、この条件を満たせない場合には、最終的に生成されるタイムスケジューリングテーブルが配置位置揺らぎ許容値違反の不正なものとなるため、各コネクションの理想配置位置のマッピングからやり直す必要がある。
【００７１】
上記操作により、当該タイムスロット配列における順番が先頭のコネクション配列要素以外は次のタイムスロット配列要素にシフトする。ここで、シフトするコネクション配列要素の配列位置揺らぎ許容値はシフトした分だけデクリメントする（図１４（ｃ））。そして、次のタイムスロット配列要素に１つ以上のコネクション配列が割当てられている場合には、先程と同様に、各コネクション配列要素の配置位置揺らぎ許容値によって並び替え操作を行う。
【００７２】
上述の操作を繰り返すことにより、コネクション毎に異なる配置位置揺らぎ許容値を設定した場合も、各コネクションの揺らぎ許容値を満たしたスケジューリングテーブルを構築することが可能となる。
【００７３】
（第三実施例）
第二実施例では、各コネクションの理想配置位置が同一のタイムスロットに割当てられていたときに、該当タイムスロットに配置できなかったコネクション配列要素を後方のタイムスロット配列要素にシフトしていたが、このシフト方向を前方に対して拡張することにより、より配置位置揺らぎを小さくすることが可能である。ただし、同一タイムスロット群に含まれる二つの隣接タイムスロットに関して、前のタイムスロットが後方シフト、後のタイムスロットが前方シフトしている場合には、前方のタイムスロットとの間隔を調べ、該当するコネクションの直前位置に配置されたタイムスロットとの間隔が許容される間隔よりも広くなっていることを確認しなければならない。タイムスロット間の間隔が、規定される間隔よりも狭い場合には、後のタイムスロットは後方シフトにしなければならない。このように前方シフトと後方シフトとを併用する場合に、後方シフトのみの場合よりもタイムスロット配置のための計算が複雑になるため、処理に時間がかかることになるが、最大セル配置位置揺らぎを小さくすることができる。
【００７４】
（第四実施例）
これまでの実施例では、コネクション配列の各要素には単一のコネクションに付けられたＩＤを対応付けるものとして扱った。さらに加えて、複数のコネクションをグループ化して単一のまとまったコネクショングループとして扱う場合においても、このコネクショングループを前述の実施例における単一コネクションに置き替えて扱うことが可能である。つまり、各コネクショングループにＩＤを付与し、全体の帯域を各グループに設定した帯域に比例して帯域を割当てることができる。
【００７５】
【発明の効果】
以上説明したように、本発明によれば、従来のスケジューリング方法と同等またはそれ以上の特性を有するスケジューリングテーブルを従来よりも高速に生成することができる。コネクション個別のタイムスロット配置位置揺らぎ許容値の導入に対応することができる。
【図面の簡単な説明】
【図１】本発明実施例のセル読出スケジューリング装置のブロック構成図。
【図２】本発明実施例のセル読出スケジューリング方法の手順を示すフローチャート。
【図３】本発明実施例のスケジューリングテーブル１周期におけるスケジューリングの概念図。
【図４】本発明実施例の理想位置からのずれの少ないスケジューリングテーブルを作成するために、スケジューリングテーブル作成を複数回実行する場合の手順を示すフローチャート。
【図５】本発明実施例の各コネクションの理想セル出力間隔に対応したセル出力タイミングをｍ×ｎ配列にマッピングした状態を示す図。
【図６】本発明実施例のタイムスロット配列を示す図。
【図７】本発明実施例のコネクション配列を示す図。
【図８】本発明実施例のタイムスロット配列およびコネクション配列の記録状況を示す図。
【図９】本発明実施例のスケジューリング方法を説明するための図。
【図１０】本発明実施例のスケジューリング方法を説明するための図。
【図１１】本発明実施例のスケジューリング方法を説明するための図。
【図１２】本発明実施例のスケジューリング方法を説明するための図。
【図１３】本発明実施例の拡張されたコネクション配列を示す図。
【図１４】本発明実施例のスケジューリング方法を説明するための図。
【符号の説明】
１  コネクション情報保持手段
２  コネクション情報ソート手段
３  コネクション識別手段
４  リスト管理手段
５  タイムスロット管理手段
６  初期配置タイムスロット予約手段
７  理想配置タイムスロット予約手段
８  配置タイムスロット分散手段
９  スケジューリング手段
１０  セル読出手段
【図１】
0003766603.tif 000002
【図２】
0003766603.tif 000003
【図３】
0003766603.tif 000004
【図４】
0003766603.tif 000005
【図５】
0003766603.tif 000006
【図６】
0003766603.tif 000007
【図７】
0003766603.tif 000008
【図８】
0003766603.tif 000009
【図９】
0003766603.tif 000010
【図１０】
0003766603.tif 000011
【図１１】
0003766603.tif 000012
【図１２】
0003766603.tif 000013
【図１３】
0003766603.tif 000014
【図１４】
0003766603.tif 000015