(57)【特許請求の範囲】
【請求項１】
複数の処理対象が各処理対象毎に許容される固有の周期間隔で分散配置され、該分散配置された配置位置に基いて処理対象が順次処理される分散配置テーブルの作成方法において、
各処理対象を配置する均等な周期間隔毎の配置位置（以下、理想位置という。）の第ｎ番目（ｎは２以上の整数）の配置位置が、他の処理対象に既に配置されて配置不能な場合に、該理想位置からその１つ前に配置した当該処理対象の第（ｎ−１）番目の理想位置まで、配置可能な空き位置を順次探索する過程と、
該探索により検出された配置可能な空き位置に、前記第ｎ番目の理想位置に配置すべき処理対象を配置する過程と、
前記第（ｎ−１）番目の理想位置までに、配置可能な空き位置が検出されない場合は、配置不能として判定する過程と、
を含むことを特徴とする分散配置テーブル作成方法。
【請求項２】
複数の処理対象が各処理対象毎に許容される固有の周期間隔で分散配置され、該分散配置された配置位置に基いて処理対象が順次処理される分散配置テーブルの作成方法において、
分散配置テーブルの先頭から１周期間隔までの配置位置において、第１番目の処理対象を配置する配置可能な初期位置を探索する過程と、
該探索により最初に検出した配置可能な初期位置を初期位置候補として設定し、該初期位置候補を基に、後続の処理対象について所定の周期間隔で配置を試み、後続の処理対象が配置可能かどうかを判定する過程と、
後続の処理対象が配置不可能な場合、前記分散配置テーブルの先頭から１周期間隔までの配置位置において、他の配置可能位置を初期位置候補として設定し、該他の位置の初期位置候補を基に、後続の処理対象について所定の周期間隔で配置を試み、後続の処理対象が配置可能かどうかを判定する過程と、
前記他の位置の初期位置候補を基に配置を試みた後続の処理対象が配置不可能な場合に、更に他の位置の初期位置候補を設定して同様の判定を行う処理を繰返して行う過程と、
前記判定により後続の処理対象が配置可能となる初期位置候補を初期位置として設定する過程とを含むことを特徴とする分散配置テーブル作成方法。
【請求項３】
複数の処理対象が各処理対象毎に許容される固有の周期間隔で分散配置され、該分散配置された配置位置に基いて処理対象が順次処理される分散配置テーブルの作成方法において、
分散配置テーブルの先頭から１周期間隔までの配置位置において、第１番目の処理対象を配置する配置可能な初期位置を探索する過程と、
該探索により最初に検出した配置可能な初期位置を初期位置候補として設定し、該初期位置候補を基に、後続の処理対象について所定のゆらぎ幅以内の周期間隔で配置を試み、後続の処理対象が配置可能かどうかを判定する過程と、
後続の処理対象が配置不可能な場合、前記分散配置テーブルの先頭から１周期間隔までの配置位置において、他の配置可能位置を初期位置候補として設定し、該他の位置の初期位置候補を基に、後続の処理対象について同様に所定のゆらぎ幅以内の周期間隔で配置を試み、後続の処理対象が配置可能かどうかを判定する過程と、
前記他の位置の初期位置候補を基に配置を試みた後続の処理対象が配置不可能な場合に、更に他の位置の初期位置候補を設定して同様の判定を行う処理を繰返して行う過程と、
前記判定により後続の処理対象が配置可能となる初期位置候補を初期位置として設定する過程と、
前記分散配置テーブルの先頭から１周期間隔までの全ての配置位置において設定した初期位置候補に対して後続の処理対象が配置不可能な場合には、前記所定のゆらぎ幅を漸次増加して同様の処理を繰返す過程と、
を含むことを特徴とする分散配置テーブル作成方法。
【請求項４】
複数の処理対象が各処理対象毎に許容される固有の周期間隔で分散配置され、該分散配置された配置位置に基いて処理対象が順次処理される分散配置テーブルの作成方法において、
各処理対象を配置する均等な周期間隔毎の配置位置（以下、理想位置という。）の第ｎ番目（ｎは２以上の整数）の配置位置が、他の処理対象に既に配置されて配置不能な場合に、該理想位置からその１つ前に配置した当該処理対象の第（ｎ−１）番目の理想位置まで、配置可能な空き位置を順次探索する過程と、
該探索により検出された配置可能な空き位置に、前記第ｎ番目の理想位置に配置すべき処理対象を配置する過程と、
前記第（ｎ−１）番目の理想位置までに、配置可能な空き位置が検出されない場合は、前記第（ｎ−１）番目の理想位置に配置すべき処理対象を配置した実配置位置の更に前方の配置可能位置を探索し、該探索により検出された配置可能な空き位置に、前記第ｎ番目の理想位置に配置すべき処理対象を配置する過程と、
前記第（ｎ−１）番目の理想位置に配置すべき処理対象の実配置位置を、前記第ｎ番目の理想位置に配置すべき処理対象の実配置位置に配置されたものと見なし、かつ、前記第ｎ番目の理想位置に配置すべき処理対象の実配置位置を、前記第（ｎ−１）番目の理想位置に配置すべき処理対象の実配置位置に配置されたものと見なして、ゆらぎ幅の算定を行う過程と、
を含むことを特徴とする分散配置テーブル作成方法。
【請求項５】
ＡＴＭシェアリンクサービスにおける複数の仮想チャネルのグループに帯域を割当てる処理に用いる分散配置テーブルの作成方法において、
各処理対象のグループを配置する理想位置の第ｎ番目（ｎは２以上の整数）の配置位置が、他の処理対象のグループに既に配置されて配置不能な場合に、該理想位置からその１つ前に配置した当該処理対象のグループの第（ｎ−１）番目の理想位置まで、配置可能な空き位置を順次探索し、該第（ｎ−１）番目の理想位置までに、配置可能な空き位置が検出されない場合は、配置不能として判定する過程、
又は分散配置テーブルの先頭から１周期間隔までの配置可能な初期位置の中から、後続の処理対象のグループが配置可能となる初期位置を探索し、該後続の処理対象のグループが配置可能となる初期位置を初期位置として設定する過程、
又は分散配置テーブルの先頭から１周期間隔までの配置可能な初期位置の中から、後続の処理対象のグループが所定のゆらぎ幅以内で配置可能となる初期位置を探索し、該後続の処理対象のグループが所定のゆらぎ幅以内で配置可能となる初期位置を初期位置として設定し、後続の処理対象のグループが所定のゆらぎ幅以内で配置可能となる初期位置が検出されない場合に、前記所定のゆらぎ幅を漸次増加して同様の処理を繰返す過程、
又は第ｎ番目の理想位置からその１つ前に配置した当該処理対象のグループの第（ｎ−１）番目の理想位置までに、配置可能な空き位置が検出されない場合に、該第（ｎ−１）番目の理想位置に配置すべき処理対象のグループを配置した実配置位置の更に前方の配置可能位置を探索し、該探索により検出された配置可能な空き位置に、前記第ｎ番目の理想位置に配置すべき処理対象のグループを配置し、前記第（ｎ−１）番目の理想位置に配置すべき処理対象のグループの実配置位置を、前記第ｎ番目の理想位置に配置すべき処理対象のグループの実配置位置に配置されたものと見なし、かつ、前記第ｎ番目の理想位置に配置すべき処理対象のグループ実配置位置を、前記第（ｎ−１）番目の理想位置に配置すべき処理対象のグループの実配置位置に配置されたものと見なして、ゆらぎ幅の算定を行う過程、
の少なくとも１つの過程を含むことを特徴とする分散配置テーブル作成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＡＴＭシェアリンクサービスにおける仮想チャネル（ＶＣ：Virtual Channel)の帯域割当て等の処理に用いる分散配置テーブル作成方法に関する。
【０００２】
ＡＴＭシェアリンクサービスは、各ユーザ間で帯域を共有することにより帯域を効率的に使用し、より低廉な通信サービスを提供するもので、帯域が空いているときは最大帯域（ＰＣＲ：Peak Cell Rate）で伝送し、帯域が混んでいるときは最低保証帯域（ｍＣＲ：minimum Cell Rate ）で伝送する帯域共用サービスである。
【０００３】
図７はグループ単位で帯域を共用するＡＴＭシェアリンクサービスの説明図である。ＡＴＭシェアリンクサービスは、仮想チャネル（ＶＣ１，ＶＣ２，ＶＣ３，・・・）を幾つかのグループ（Ｇ１，Ｇ２，・・・，Ｇｎ）に分け、それぞれのグループに所定の帯域を割当て各グループの帯域をグループ内の複数の仮想チャネル間で共用する。
【０００４】
各仮想チャネルからのセルは、グループ毎のバッファメモリ７−１1 〜７−１n に格納され、読出し制御部７−２は、分散配置テーブル７−３に分散配置して格納されたグループＩＤを順次読出し、該グループＩＤにより指定されるグループのバッファメモリ７−１1 〜７−１n から、順次、セルを読み出して共有帯域の伝送路７−４上に送出する。
【０００５】
例えば、図７において、グループＧ１に１２０Mbpsの帯域が与えられ、そのグループ内に最低保証帯域（ｍＣＲ：minimum Cell Rate ）が１Mbps、最大帯域（ＰＣＲ：Peak Cell Rate）が１０Mbpsの仮想チャネルが１２０個収容されているとする。
【０００６】
そして、仮に１２０Mbpsの帯域を与えられたグループが１０個分収容されている場合には、共有帯域の伝送路７−４は１．２Gbpsの帯域となり、分散配置テーブル７−３は１．２Gbpsの帯域を１０個のグループに均等に分散して配分すれば良いことになるが、各グループの要求帯域は一般に個々に異なり、分散配置テーブル７−３は、各グループをその要求帯域に応じて異なる周期間隔で配置する必要があり、また、各グループの帯域が変動したり、グループ数の増減により、それらの変動に応じて分散配置テーブル７−３の配置位置を更新し、作成し直さなければならない。
【０００７】
分散配置テーブルは、グループ毎のセルの読出し処理等、複数の処理対象に対する処理を、特定の処理対象に片寄ることなく均等に分散して行いたい場合に多く用いられ、テーブル上に処理対象を分散して配置し、該テーブル上に配置された処理対象を順番に取出して処理を行うことにより、公平な分散処理が実現される。
【０００８】
分散配置テーブルは、前述したように処理対象の配置間隔の変動や処理対象自体の増減により、処理対象の配置を更新しなければならない。そして、頻繁に処理対象の配置間隔の変動や処理対象の増減があり、かつ高速処理が要求されるシステムでは、分散配置テーブルの更新・作成に費やされる時間は処理性能の劣化につながり、分散配置テーブルの作成時間を極力短縮することが要求されている。
【０００９】
また、きめ細かい分散配置テーブルを用いれば、処理対象をより均等に分散配置することができるが、分散配置テーブルを格納するメモリの制約上、分散配置テーブルの大きさには制限があり、必ずしも全ての処理対象が均等に分散配置されるほどの十分大きな分散配置テーブルを用いることはできない。
【００１０】
分散配置テーブルが小さくなると、配置位置が粗くなるため、処理対象を理想的な均等位置に配置することができなくなり、処理対象の配置位置が理想的な均等位置からある程度ずれることとなる。このずれを、「ゆらぎ」 と呼んでいるが、より均等な処理を行うためには、このゆらぎを極力小さくすることが要求される。
【００１１】
さらに、１つの分散配置テーブルで多くの処理対象を扱うために、１つの分散配置テーブルにおける処理対象の収容率を増加させることが要求されている。本発明は、テーブル作成時間が短く、配置位置のゆらぎが小さく、また、処理対象の収容率が高い分散配置テーブルの作成方法に関する。
【００１２】
【従来の技術】
図８は従来の分散配置方法による分散配置テーブル上への処理対象の配置の説明図である。同図は分散配置テーブル上における配置位置を示し、○印は、同一グループの処理対象が所定の周期間隔で理想的に分散配置される位置を表し、×印は配置不能位置を表し、◎印は実際に配置する位置を表している。なお、以下において、同一グループの処理対象が所定の周期間隔で理想的に分散配置される間隔を「理想間隔」 といい、該理想間隔毎の配置位置を「理想位置」 という。
【００１３】
まず、図８の（ａ）に示すように、分散配置テーブルの先頭から理想間隔までの間で、配置可能な空き位置のサーチを行い、配置可能な空き位置が検出されれば、その最初に検出された配置可能位置を初期位置とする。
【００１４】
その後、初期位置に配置した処理対象と同一グループの処理対象を、順次、初期位置から理想間隔毎の各理想位置に配置する。図８の（ｂ）は各理想位置に配置可能な状態であり、後続の処理対象が各理想位置に配置された場合を示している。
【００１５】
但し、後続の処理対象全てが理想間隔毎の理想位置に配置されるとは限らず、理想位置に配置不能な処理対象を全て配置不能として処理することとすると、処理対象の収容率が低下してしまうので、実配置位置には理想位置からのある程度の許容幅を持たせることとしている。
【００１６】
そして、或グループの処理対象の理想位置に他のグループの処理対象が配置されていて該理想位置に配置不可能な場合は、その或グループの処理対象において１つ前に配置された配置位置まで、配置位置を１つずつ前方にずらしながら配置可能位置を探索して検出し、その位置に該処理対象を配置する。なお、前方にずらす分には、要求された帯域が損われることはない。
【００１７】
このときの前方へずらした分がゆらぎである。なお、該グループの処理対象において１つ前に配置された配置位置まで、配置可能位置が検出されない場合は、配置不能とし、そのグループの設定は拒否される。
【００１８】
図８の（ｃ）は、理想位置に配置不能な場合を示し、２番目の理想位置８−１が配置不能であるため、その前方の配置可能位置をサーチし、２番目の理想位置に配置すべき処理対象を、理想位置８−１から前方の配置可能位置８−２に配置され、３番目の理想位置８−３に配置すべき処理対象も同じく該理想位置が配置不能であるため、前方の配置可能位置をサーチし、２番目の処理対象が配置された位置８−２までサーチし、その結果、配置可能位置が検出されない場合は、配置不能とする。
【００１９】
図９は前述の従来の分散配置方法のフロー図である。まず最初に、分散配置テーブルの先頭から理想間隔までの間に、配置可能な初期位置を探索する（９−１）。探索の結果、配置可能な初期位置が存在しない場合は配置不能とする (９−２) 。
【００２０】
配置可能な初期位置が存在する場合は、最初に検出した配置可能位置を初期位置に設定する（９−３）。次に、設定した初期位置を基に理想間隔毎に後続の処理対象の実配置を試みる（９−４）。理想位置に実配置可能であれば、ゆらぎ幅０で分散配置処理を完了する（９−５）。
【００２１】
後続の処理対象が理想位置に実配置不能であれば、理想位置から前方に１つずつ配置可能位置を探索し（９−６）、先に配置した処理対象の配置位置までに配置可能位置が存在するかを判定し（９−７）、存在すれば、その位置に処理対象を実配置して分散配置を完了する（９−８）。なお、このときゆらぎ幅を計算する。そして、先に配置した処理対象の配置位置までに配置可能位置が存在しなければ、配置不能とする（９−９）。
【００２２】
【発明が解決しようとする課題】
従来の分散配置方法は、理想位置への配置が不可能な場合、先に配置した処理対象の配置位置まで、１つずつ前方にずらしながら配置可能位置を探索していた。このため、図８の（ｃ）に示す場合のように、３番目の理想位置に配置すべき処理対象の配置可能位置が、２番目の理想位置までに存在しない場合であっても、更に、２番目の処理対象の実配置位置まで探索を行って配置不能と判定していた。
【００２３】
このことは、既に２番目の理想位置に配置すべき処理対象の配置位置を探索する際に、２番目の理想位置から該２番目の処理対象の実配置位置までには、配置可能位置が存在しないことが検出済みであるにもかかわらず、次の３番目の処理対象の配置位置を探索する際にも、再び２番目の処理対象の理想位置から該２番目の処理対象の実配置位置までを探索していたため、無駄なサーチを重複して行っていたことになる。
【００２４】
また、初期位置の配置位置に依存して、以降の処理対象が理想位置に若しくは理想位置からの小さなゆらぎで配置可能となるか、又は配置不能となるかが決定されるにもかかわらず、先頭から理想間隔までの間で配置可能な初期位置をサーチし、最初に検出した初期位置を基に以降の処理対象を配置するだけであった。
【００２５】
このように、従来の分散配置方法は、余分な配置位置まで無駄に探索を行っていたため、分散配置テーブルの作成に余計な時間を要していた。また、従来の分散配置方法は、最初に検出した初期位置を固定的に設定していたため、配置不能となる処理対象が多く発生し、処理対象の収容率が低く、またゆらぎ幅が大きくなるという問題を生じていた。
【００２６】
本発明は、余分な配置位置の探索を削減して、分散配置テーブルの作成時間の短縮化を図るとともに、初期位置の配置位置を変化させて、処理対象を配置可能位置に配置し、処理対象の収容率を向上させることを目的とする。
【００２７】
また、より小さなゆらぎで配置可能な初期位置が存在する場合には、その初期位置を優先して設定してゆらぎ幅の最小化を図り、また、理想位置に配置不能な場合における配置可能位置のサーチ範囲を改善してゆらぎ幅の増大を最小限に抑えることを目的とする。
【００２８】
【課題を解決するための手段】
本発明の分散配置テーブルの作成方法は、（１）複数の処理対象が各処理対象毎に許容される固有の周期間隔で分散配置され、該分散配置された配置位置に基いて処理対象が順次処理される分散配置テーブルの作成方法において、各処理対象を配置する均等な周期間隔毎の配置位置（以下、理想位置という。）の第ｎ番目（ｎは２以上の整数）の配置位置が、他の処理対象に既に配置されて配置不能な場合に、該理想位置からその１つ前に配置した当該処理対象の第（ｎ−１）番目の理想位置まで、配置可能な空き位置を順次探索する過程と、該探索により検出された配置可能な空き位置に、前記第ｎ番目の理想位置に配置すべき処理対象を配置する過程と、前記第（ｎ−１）番目の理想位置までに、配置可能な空き位置が検出されない場合は、配置不能として判定する過程とを含むものである。
【００２９】
また、（２）分散配置テーブルの先頭から１周期間隔までの配置位置において、第１番目の処理対象を配置する配置可能な初期位置を探索する過程と、該探索により最初に検出した配置可能な初期位置を初期位置候補として設定し、該初期位置候補を基に、後続の処理対象について所定の周期間隔で配置を試み、後続の処理対象が配置可能かどうかを判定する過程と、後続の処理対象が配置不可能な場合、前記分散配置テーブルの先頭から１周期間隔までの配置位置において、他の配置可能位置を初期位置候補として設定し、該他の位置の初期位置候補を基に、後続の処理対象について所定の周期間隔で配置を試み、後続の処理対象が配置可能かどうかを判定する過程と、前記他の位置の初期位置候補を基に配置を試みた後続の処理対象が配置不可能な場合に、更に他の位置の初期位置候補を設定して同様の判定を行う処理を繰返して行う過程と、前記判定により後続の処理対象が配置可能となる初期位置候補を初期位置として設定する過程とを含むものである。
【００３０】
また、（３）分散配置テーブルの先頭から１周期間隔までの配置位置において、第１番目の処理対象を配置する配置可能な初期位置を探索する過程と、該探索により最初に検出した配置可能な初期位置を初期位置候補として設定し、該初期位置候補を基に、後続の処理対象について所定のゆらぎ幅以内の周期間隔で配置を試み、後続の処理対象が配置可能かどうかを判定する過程と、後続の処理対象が配置不可能な場合、前記分散配置テーブルの先頭から１周期間隔までの配置位置において、他の配置可能位置を初期位置候補として設定し、該他の位置の初期位置候補を基に、後続の処理対象について同様に所定のゆらぎ幅以内の周期間隔で配置を試み、後続の処理対象が配置可能かどうかを判定する過程と、前記他の位置の初期位置候補を基に配置を試みた後続の処理対象が配置不可能な場合に、更に他の位置の初期位置候補を設定して同様の判定を行う処理を繰返して行う過程と、前記判定により後続の処理対象が配置可能となる初期位置候補を初期位置として設定する過程と、前記分散配置テーブルの先頭から１周期間隔までの全ての配置位置において設定した初期位置候補に対して後続の処理対象が配置不可能な場合には、前記所定のゆらぎ幅を漸次増加して同様の処理を繰返す過程とを含むものである。
【００３１】
また、（４）複数の処理対象が各処理対象毎に許容される固有の周期間隔で分散配置され、該分散配置された配置位置に基いて処理対象が順次処理される分散配置テーブルの作成方法において、各処理対象を配置する均等な周期間隔毎の配置位置（以下、理想位置という。）の第ｎ番目（ｎは２以上の整数）の配置位置が、他の処理対象に既に配置されて配置不能な場合に、該理想位置からその１つ前に配置した当該処理対象の第（ｎ−１）番目の理想位置まで、配置可能な空き位置を順次探索する過程と、該探索により検出された配置可能な空き位置に、前記第ｎ番目の理想位置に配置すべき処理対象を配置する過程と、前記第（ｎ−１）番目の理想位置までに、配置可能な空き位置が検出されない場合は、前記第（ｎ−１）番目の理想位置に配置すべき処理対象を配置した実配置位置の更に前方の配置可能位置を探索し、該探索により検出された配置可能な空き位置に、前記第ｎ番目の理想位置に配置すべき処理対象を配置する過程と、前記第（ｎ−１）番目の理想位置に配置すべき処理対象の実配置位置を、前記第ｎ番目の理想位置に配置すべき処理対象の実配置位置に配置されたものと見なし、かつ、前記第ｎ番目の理想位置に配置すべき処理対象の実配置位置を、前記第（ｎ−１）番目の理想位置に配置すべき処理対象の実配置位置に配置されたものと見なして、ゆらぎ幅の算定を行う過程とを含むものである。
【００３２】
また、（５）ＡＴＭシェアリンクサービスにおける複数の仮想チャネルのグループに帯域を割当てる処理に用いる分散配置テーブルの作成方法において、各処理対象のグループを配置する理想位置の第ｎ番目（ｎは２以上の整数）の配置位置が、他の処理対象のグループに既に配置されて配置不能な場合に、該理想位置からその１つ前に配置した当該処理対象のグループの第（ｎ−１）番目の理想位置まで、配置可能な空き位置を順次探索し、該第（ｎ−１）番目の理想位置までに、配置可能な空き位置が検出されない場合は、配置不能として判定する過程、又は分散配置テーブルの先頭から１周期間隔までの配置可能な初期位置の中から、後続の処理対象のグループが配置可能となる初期位置を探索し、該後続の処理対象のグループが配置可能となる初期位置を初期位置として設定する過程、
又は分散配置テーブルの先頭から１周期間隔までの配置可能な初期位置の中から、後続の処理対象のグループが所定のゆらぎ幅以内で配置可能となる初期位置を探索し、該後続の処理対象のグループが所定のゆらぎ幅以内で配置可能となる初期位置を初期位置として設定し、後続の処理対象のグループが所定のゆらぎ幅以内で配置可能となる初期位置が検出されない場合に、前記所定のゆらぎ幅を漸次増加して同様の処理を繰返す過程、
又は第ｎ番目の理想位置からその１つ前に配置した当該処理対象のグループの第（ｎ−１）番目の理想位置までに、配置可能な空き位置が検出されない場合に、該第（ｎ−１）番目の理想位置に配置すべき処理対象のグループを配置した実配置位置の更に前方の配置可能位置を探索し、該探索により検出された配置可能な空き位置に、前記第ｎ番目の理想位置に配置すべき処理対象のグループを配置し、前記第（ｎ−１）番目の理想位置に配置すべき処理対象のグループの実配置位置を、前記第ｎ番目の理想位置に配置すべき処理対象のグループの実配置位置に配置されたものと見なし、かつ、前記第ｎ番目の理想位置に配置すべき処理対象のグループ実配置位置を、前記第（ｎ−１）番目の理想位置に配置すべき処理対象のグループの実配置位置に配置されたものと見なして、ゆらぎ幅の算定を行う過程、の少なくとも１つの過程を含むものである。
【発明の実施の形態】
図１は本発明の第１の実施の形態の分散配置テーブル作成方法の説明図である。同図は分散配置テーブル上における配置位置を示し、○印は理想間隔で同一グループの処理対象を配置する理想位置を表し、×印は配置不能位置を表し、◎印は該処理対象を実際に配置する位置（実配置位置）を表している。
【００３３】
図１の（ａ）に示すように、或グループのｎ番目の処理対象がその理想位置１−１へ配置することが不可能であり、かつ、その前の（ｎ−１）番目の処理対象もその理想位置１−２に配置不可能で、該（ｎ−１）番目の処理対象はその配置位置にゆらぎを生じ、配置位置１−３に配置されているものとする。
【００３４】
このとき、図１の（ａ）に示す下向矢印部の配置位置は、（ｎ−１）番目の処理対象の配置可能位置探索時において、配置不能として検出された位置であるので（配置可能なら（ｎ−１）番目の処理対象が配置されているはずである）、ｎ番目の処理対象の配置可能位置探索時においては、図１の（ｂ）に示すように、（ｎ−１）番目の処理対象の理想位置１−２の直前まで配置可能位置探索を行い、この位置までに配置可能位置が存在しない場合は、図の下向矢印部の配置位置の探索は行わず、配置不能と判定することにより、余分な配置位置の探索を削減し、分散配置テーブルの作成時間を短縮化を図る。
【００３５】
図２は本発明の第２の実施の形態の分散配置テーブル作成方法の説明図である。同図は分散配置テーブル上における初期位置を示し、○印は初期位置の候補位置を表し、×印は配置不能位置を表し、◎印は配置不能処理対象を生じない初期位置を表している。
【００３６】
同図に示すように、分散配置テーブルの先頭から初期位置サーチ幅（この幅は理想間隔の幅とすることができる。）の配置可能位置について、配置可能な初期位置のサーチを行い、最初に検出した初期位置の候補位置２−１を暫定的な初期位置として設定し、後続の処理対象について配置を試み、後続の処理対象が配置不能となった場合、次の候補位置２−２に初期位置を変化させて、後続の処理対象の配置を試み、同様に後続の処理対象が配置不能となった場合、順次、次の候補位置を初期位置として設定し、そして配置不能な処理対象を生じない初期位置２−３が探索されると、この位置を初期位置として設定する。
【００３７】
図３は前述の本発明の第２の実施の形態の分散配置テーブル作成方法のフロー図である。図３に示すフロー図において、３−１から３−８の符号を付したフローは、図９に示したフロー図の９−１から９−８の符号を付したフローと同様であるので、重複した説明は省略する。
【００３８】
図３に示す３−９及び３−１０の符号の付した処理が従来と異なる処理であり、従来、先に配置した処理対象の配置位置までに配置可能位置が存在しなければ、配置不能としたのに対し、本発明の第２の実施の形態は、別の配置可能初期位置が存在するかどうかを調べ（３−９）、存在する場合にはその別な位置を初期位置として設定し（３−１０）、再度この設定し直した初期位置を基に理想間隔毎に実配置を試みる（３−４）。初期位置を設定し直すことにより、配置不可能となった後続の処理対象が、配置可能となる機会が増え、処理対象の収容率を向上させることができる。
【００３９】
図４は本発明の第３の実施の形態の分散配置テーブル作成方法の説明図である。この実施の形態は、処理対象の収容率の増加とゆらぎ幅の最小化を図るために、より小さなゆらぎで配置可能な初期位置候補がある場合に、その初期位置候補を優先させて初期位置に設定するものである。
【００４０】
図４において、○印及び◎印は分散配置テーブルの初期位置サーチ幅（理想間隔）内における配置可能な初期位置候補を表し、◎印はその中でゆらぎ幅の条件を満たす初期位置候補として最初に検出された初期位置候補を示している。
【００４１】
より小さなゆらぎで後続の処理対象が配置可能な初期位置候補を検出する手順として、初期位置サーチ幅内における配置可能な初期位置候補の中から、最初、ゆらぎ幅の条件を０（ゆらぎ無し；デフォルト値）として該条件を満たす初期位置候補をサーチする。
【００４２】
そして、前述の条件を満たす初期位置候補が検出されれば、該初期位置候補を初期位置として設定するが、該条件を満たす初期位置候補が検出されない場合は、ゆらぎ幅の条件を漸次緩めて増加させながら繰返しサーチすることにより、ゆらぎ幅が最小となる初期位置を検出し、その初期位置を優先させて設定する。この構成により、より小さなゆらぎで後続の処理対象が配置可能な初期位置を設定することができ、ゆらぎの増大を最小限に抑えることが可能となる。
【００４３】
図５は本発明の第４の実施の形態の分散配置テーブル作成方法の説明図である。この実施の形態は、処理対象を理想位置に配置することが不能な場合に、配置可能位置を前方に１つずつずらしながら探索する範囲として、従来、同一グループの処理対象を先に配置した位置までとしていたのを、更に探索範囲を広げて配置可能位置を探索し、処理対象の収容率の向上を図るものである。
【００４４】
図５の（ａ）は拡大した配置可能位置の探索範囲を示し、図５の（ｂ）は探索範囲の拡大に伴うゆらぎの乗せ換えの様子を示している。また、同図において○印は理想位置を表し、×印は配置不能位置を表し、◎印は実際の配置位置を表している。
【００４５】
図５の（ａ）に示すように、理想位置５−１が配置不能であった場合に、配置可能位置を前方に１つずつずらしながら、第１の実施の形態で説明したように１つ前の理想位置５−２まで探索し、該１つ前の理想位置５−２までに配置可能位置が検出されない場合は、先に配置した同一グループの処理対象の配置位置５−３の更に前方から配置位置を１つずつずらしながら配置可能位置を探索する。
【００４６】
そして、配置可能位置が検出されると、その位置５−４に処理対象を配置する。即ち、後続の処理対象が配置不能である場合に、先に配置した同一グループの処理対象の配置位置を飛び越して配置位置を探索し、検出した配置可能位置に該グループの処理対象を配置する。
【００４７】
この場合、図５の（ｂ）に示すように、理想位置５−１から理想間隔を超えた実配置位置５−４に配置したゆらぎ幅をｔ2 とし、先に配置した同一グループの処理対象のゆらぎ幅をｔ1 とすると、ゆらぎ幅ｔ2 は極めて大きな値になってしまうように見えるが、以下に説明するように処理対象自体のゆらぎは、それほど大きくはならない。
【００４８】
即ち、実配置位置５−３及び５−４に配置した処理対象は、同一グループに属する処理対象であり、後続の理想位置に配置すべき処理対象を、先に配置した処理対象の前方に配置しても、処理対象自体の処理順序が入れ替るわけではない。
【００４９】
そこで、図５の（ｃ）に示すように、理想位置５−２に配置すべき処理対象が実配置位置５−４に配置され、理想位置５−１に配置すべき処理対象が実配置位置５−３に配置されたものと見なしてゆらぎの乗せ換えをおこなうと、実配置位置５−４のゆらぎ幅は（ｔ2 −Ｔ）、実配置位置５−３のゆらぎ幅は（ｔ1 ＋Ｔ）となり、ゆらぎ幅（ｔ2 −Ｔ）及びゆらぎ幅（ｔ1 ＋Ｔ）はいずれもゆらぎ幅ｔ2 より小さな値となり、実際上のゆらぎ幅として格別支障がない場合が多い。
【００５０】
以上説明した本発明の第１乃至第４の実施の形態は、それぞれ互いに組合せて使用することにより、分散配置テーブルの作成時間の短縮化又はゆらぎの増大の抑制又は処理対象の収容率の向上を同時に図ることが可能となる。
【００５１】
図６は以上説明した第１乃至第４の実施の形態を組合せた分散配置テーブル作成のフロー図である。まず最初に、ゆらぎの初期値を設定し（６−１）、先頭から理想間隔までの間に配置可能な初期位置を探索し（６−２）、配置可能な初期位置が存在しなければ配置不能とする（６−３）。
【００５２】
配置可能な初期位置が存在すれば、初期位置の位相を設定し（６−４）、設定した初期位置を基に理想間隔毎に後続の処理対象の実配置を試みる。そして、その実配置が可能であれば、ゆらぎ幅０で分散配置を完了する（６−５）。実配置が可能でなければ、理想位置から前方に１つずつずらしながら配置可能位置を探索する（６−６）。
【００５３】
配置可能位置が先に配置した処理対象よりも前方である場合、ゆらぎの乗換えを行って（６−７）ゆらぎ幅を求め（６−８）、配置可能位置が先に配置した処理対象よりも後方であれば、その位置でゆらぎ幅を求める（６−８）。
【００５４】
そして、ゆらぎ幅が条件を満たすかどうかを調べ、満たす場合は分散配置を完了する（６−９）。ゆらぎ幅の条件を満たさない場合は、別の配置可能な初期位置が存在するかどうかを調べ（６−１０）、存在する場合はその初期位置の位相に設定し、前述のフロー（６−４）以下の処理を繰返す。
【００５５】
別の配置可能な初期位置が存在しない場合は、ゆらぎの条件を緩めることが可能か判定し（６−１１）、緩めることが不可能であれば配置不能とする（６−１２）。ゆらぎの条件を緩めることが可能であれば、ゆらぎ幅の値を増加して設定し、前述のフロー（６−２）以下の処理を繰返す。
【００５６】
【発明の効果】
以上説明したように、本発明によれば、分散配置テーブルの作成において、配置可能位置の探索範囲として、同一グループの処理対象の先に配置した実配置位置とその理想位置との間の範囲を除外することにより、テーブル作成時間を短縮化することができ、また、初期位置変更して後続の処理対象の配置を行うことにより、配置不能となる処理対象を減少させ、処理対象の収容率を向上させることができ、また、漸次ゆらぎ条件を緩めながら、初期位置変更して後続の処理対象の配置を行うことにより、より小さなゆらぎで処理対象を配置するとともに処理対象の収容率を向上させ、更に、配置可能位置の探索範囲として、同一グループの処理対象の先に配置した実配置位置の前方を探索することにより、配置可能位置が拡張され、処理対象の収容率を向上させることができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態の分散配置テーブル作成方法の説明図である。
【図２】本発明の第２の実施の形態の分散配置テーブル作成方法の説明図である。
【図３】本発明の第２の実施の形態の分散配置テーブル作成方法のフロー図である。
【図４】本発明の第３の実施の形態の分散配置テーブル作成方法の説明図である。
【図５】本発明の第４の実施の形態の分散配置テーブル作成方法の説明図である。
【図６】本発明の第１乃至第４の実施の形態を組合せた分散配置テーブル作成のフロー図である。
【図７】グループ単位で帯域を共用するＡＴＭシェアリンクサービスの説明図である。
【図８】従来の分散配置方法による分散配置テーブル上への処理対象の配置の説明図である。
【図９】従来の分散配置方法のフロー図である。
【符号の説明】
１−１  ｎ番目の処理対象の理想位置
１−２  （ｎ−１）番目の処理対象の理想位置
１−３  （ｎ−１）番目の処理対象の実配置位置
【図１】
0003694856.tif 000002
【図２】
0003694856.tif 000003
【図３】
0003694856.tif 000004
【図４】
0003694856.tif 000005
【図５】
0003694856.tif 000006
【図６】
0003694856.tif 000007
【図７】
0003694856.tif 000008
【図８】
0003694856.tif 000009
【図９】
0003694856.tif 000010