(57)【要約】【課題】シェーピング装置において、セルを格納すべき空き領域を高速に検索するとともにセルの順序逆転を確実に防止する。【解決手段】バッファにセルを格納する際の空き領域を検索するための空き領域検索方法において、オフセット算出ステップは、新たなセルの入力に応じて、対応するチャネルの直前のセルが格納された格納領域と直前のセルがチャネルに対応する基本間隔に基づいて格納されるべきであった格納領域とのずれを示すオフセット値を求める。比較ステップは、オフセット値と基本間隔に相当するシェイパー値とを比較する。第１検索ステップは、オフセット値の方が大きかった場合は、直前のセルが格納された格納領域の次の格納領域からバッファの空き領域を検索する。第２検索ステップは、オフセット値がシェイパー値を超えていない場合は、シェイパー値からオフセット値を差し引いた分だけ直前のセルが格納された格納領域から離れた格納領域からバッファの空き領域を検索する。【選択図】      図１
2005223787.tif 000002
【特許請求の範囲】
【請求項１】
複数の格納領域に格納されたデータを所定の時間間隔で順次に出力する構成を備えたバッファに、複数のチャネルそれぞれにかかわるセルを前記各チャネルに対応して定められた基本間隔に相当する格納領域ごとに格納することにより、前記各チャネルにおけるセル送出間隔を調整するシェーピング装置に利用され、前記バッファにセルを格納する際の空き領域を検索するための空き領域検索方法において、
新たなセルの入力に応じて、対応するチャネルの直前のセルが格納された格納領域と前記直前のセルが前記チャネルに対応する基本間隔に基づいて格納されるべきであった格納領域とのずれを示すオフセット値を求めるオフセット算出ステップと、
前記オフセット値と前記基本間隔に相当するシェイパー値とを比較する比較ステップと、
前記オフセット値の方が大きかった場合は、前記直前のセルが格納された格納領域の次の格納領域から前記バッファの空き領域を検索する第１検索ステップと、
前記オフセット値が前記シェイパー値を超えていない場合は、前記シェイパー値から前記オフセット値を差し引いた分だけ前記直前のセルが格納された格納領域から離れた格納領域から前記バッファの空き領域を検索する第２検索ステップと
を備えたことを特徴とする空き領域検索方法。
【請求項２】
複数の格納領域を有し、前記複数の格納領域に格納されたデータを所定の時間間隔で順次に出力するバッファと、
複数のチャネルそれぞれに対応し、前記各チャネルにかかわるセルの前記バッファにおけるアドレスとこのアドレスが前記各チャネルに対応する基本間隔に基づいて算出された目標位置からずれている量を示すオフセット値とを保持する管理テーブルと、
新たなセルの入力に応じて、前記新たなセルが属するチャネルに対応して前記管理テーブルに保持された情報と前記チャネルに対応する基本間隔に基づいて決定されたシェイパー値とに基づいて、前記新たなセルを格納するための格納領域に対応する検索開始位置を求める開始位置算出手段と、
前記検索開始位置から前記バッファに残されている空き領域を検索する空き検索手段と、
前記空き検索手段によって検索された格納領域に、前記新たなセルを書き込む書込手段と、
前記空き検索手段によって検索された格納領域のアドレスと前記チャネルに対応する基本間隔とに基づいて、このアドレスに対応するオフセット値を算出するオフセット算出手段と、
前記空き検索手段によって検索された格納領域のアドレスと前記オフセット算出手段によって算出されたオフセット値とを用いて、前記管理テーブルに前記チャネルに対応して保持された情報を更新するテーブル更新手段とを備え、
前記開始位置算出手段は、
前記管理テーブルに前記チャネルに対応して保持されたオフセット値と基本間隔に対応するシェイパー値とを比較する比較手段と、
前記シェイパー値から前記オフセット値を差し引いた値と前記管理テーブルに保持されたアドレスとに基づいて、前記新たなセルを格納すべき格納領域の目標位置を算出する目標算出手段と、
前記比較手段によって前記オフセット値が前記シェイパー値を超えている旨の比較結果が得られたときに、前記管理テーブルに保持された前記アドレスの次のアドレスを検索開始位置として出力し、他の場合は、前記目標算出手段によって算出された目標位置を検索開始位置として出力する選択手段とを備えた
ことを特徴とするシェーピング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＡＴＭセルの伝送を行う基幹網と無線通信網を構成する基地局との間に配置される基地局管理装置などにおいて、基幹網に送出するＡＴＭセルの送出間隔を調整するシェーピング装置に関し、特に、シェーピング装置に備えられたバッファの空き領域を検索する空き領域検索方法およびこれを用いたシェーピング装置に関する。
【背景技術】
【０００２】
図３に、従来のシェーピング装置の構成例を示す。
図３に示したシェーピング装置に入力されるセルは、順次に内部バッファ４０１に保持され、このとき、セルの構成要素であるタグに含まれているチャネル識別子（ＶＣＩ）が、監視部４０２に渡される。これに応じて、監視部４０２は、受け取ったチャネル識別子に対応して予め設定された監視パラメータに基づいて、内部バッファ４０１に保持されたセルをネットワークに送出すべきタイミングを示すセル送出間隔目標値Ｘ０を算出する。このセル送出間隔目標値Ｘ０に基づいて、セル格納部４０３は、リングバッファ４０４の適切な空き領域に入力セルを格納する。つまり、セル格納部４０３は、リングバッファ４０４からセル送出間隔目標値Ｘ０以降の空き領域を検索し、検索した空き領域に入力セルを格納する。例えば、図３に示すように、セル送出間隔目標値Ｘ０で示される格納領域およびこれに続くいくつかの格納領域が既に他のチャネルのセルに占められている場合（図３において、他のチャネルのセルを格納している格納領域に網掛けを付して示した）に、セル格納部４０３は、このセル送出間隔目標値Ｘ０に最も近い空き領域（図３において、矢印を付して示す）に入力セルを格納する。
【０００３】
一方、図３に示したリングバッファ４０４は、循環型のシフトレジスタと同様に、一定の時間ごとに、ポインタによって示された先頭の記憶領域に格納されたセルを出力し、次の記憶領域に先頭を示すポインタを移す動作を繰り返す。また、このリングバッファ４０４は、先頭を示すポインタを移す際に、ポインタの移動先の記憶領域を示すアドレスを監視部４０２に渡し、上述したセル送出間隔目標値Ｘ０の算出処理に供する。
【０００４】
このようにして、図３に示したシェーピング装置では、リングバッファ４０４の先頭の記憶領域に保持されているセルの送出タイミングを基準として、入力セルのセル送出間隔目標値Ｘ０を算出し、これに基づいて入力セルをリングバッファ４０４に格納していくことにより、各チャネルについて設定された監視パラメータに従うように、セルの送出間隔を調整することができる。
【０００５】
図４に、シェーピング装置の別構成例を示す。
図４に示した読出処理部４１１は、シェーピングバッファ４１２の読出位置を示すリードポインタの位置を循環的に管理しながら、このシェーピングバッファ４１２に保持されているセルを順次に読み出して出力する。また、図４に示したバッファ管理テーブル４１３には、各チャネルにおける直前のセルの格納場所およびその格納場所と目標となった格納場所とのずれ（以下、オフセットと称する）を示す情報を保持している。そして、目標位置算出部４１４は、新たなセルの入力に応じて、このバッファ管理テーブル４１３に格納された情報とそのチャネルについて設定された送出間隔とに基づいて、目標とすべき格納場所を求める。
【０００６】
このとき、目標位置算出部４１４は、セルの送出間隔に対応するシェイパー値ＳＲとバッファ管理テーブル４１３に格納されたオフセット値ＯＳおよび直前のセルの格納場所を示すバッファ番号ＢＮとを用いて、式（１）で表されるような目標位置ＴＮを求める。
ＴＮ＝ＢＮ＋ＳＲ−ＯＳ    ・・・（１）
例えば、チャネルＡに対応するセルＡ４が新たに入力されたときに、図５に符号Ａ１〜Ａ３を付して示すようにシェーピングバッファ４１２に格納されている場合に、目標位置算出部４１４は、直前のセルＡ３に対応するバッファ番号（例えば、１８）およびこのセルＡ３に対応する目標位置ＴＮと実際の格納位置とのずれであるオフセット値（例えば、８）とシェイパー値（例えば、５）とに基づいて、目標位置ＴＮとしてバッファ番号１５を求める。
【０００７】
このようにして得たれた目標位置ＴＮを検索開始位置として、空き検索部４１５は、シェーピングバッファ４１２の空き領域の検索を行い、得られた空き領域の位置を示すバッファ番号を書込処理部４１６に渡す。このとき、書込処理部４１６には、空き領域に対応するバッファ番号とともに、このバッファ番号と上述した目標位置ＴＮとのずれに相当する新たなオフセット値が渡され、これに応じて、書込処理部４１６は、新たなセルをシェーピングバッファ４１２の空き領域に格納するとともに、このバッファ番号と新たなオフセット値とを用いて、バッファ管理テーブル４１３の内容を更新する。
【０００８】
このように、図４に示したシェーピング装置では、シェーピングバッファ４１２に新たなセルを書き込んだバッファ番号と本来そのセルを書き込むべき目標値とのずれをオフセット値として管理し、次のセルをシェーピングバッファ４１２に書き込む際に、このオフセット値を考慮して新たな目標値を算出することにより、複数のセルにかかわる送出間隔の平均値をほぼシェイパー値ＳＲに一致させることができる。
【０００９】
図３あるいは図４に示したシェーピング装置では、入力されるセルがどのようなサービスに供されるチャネルにかかわるものであるかにかかわらず、同等の条件のもとで空き領域の探索が行われている。
このため、例えば、図３に矢印で示したセル送出間隔目標値Ｘ０以降に連続して他のチャネルのセルがリングバッファ４０４に格納されていた場合には、音声通信に割り当てられたチャネルの新たなセルが、上述したセル送出間隔目標値Ｘ０から大きく遅れた位置に格納され、結果として、そのセルの送出タイミングが遅れてしまう場合があった。
【００１０】
このような場合に対応する対策として、例えば、セル送出間隔に大きな揺らぎが許されないようなチャネルのセルを優先的に格納する領域をリングバッファに設け、セル送出速度のみならず、セル送出間隔の揺らぎに関する許容範囲を考慮して、リングバッファへの格納を制御する手法などが提案されている（特許文献１参照）。
【特許文献１】特開平７−１７０２６６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上述したように、様々なサービスに供されるチャネルが混在する基地局制御装置に備えられるシェーピング装置では、サービスごとに異なる通信品質を満足するために、入力セルをシェーピング装置のバッファに格納する際に非常に複雑な制御が必要とされ、これに伴って、シェーピング装置も極めて複雑な構成となってきている。
その一方、例えば、全てのチャネルに同等のサービス品質を提供することを前提としたネットワークシステムなどのように、個々のチャネルのセル送出間隔に許容される揺らぎに大きなばらつきがない分野もある。
【００１２】
そして、このような分野においてシェーピング装置に望まれる性能は、個々のセル送出間隔を厳格に制御することよりも、むしろ、空き領域の検索処理を高速化することである。
また、どのような分野におけるシェーピング装置でも、各チャネルにかかわるセルの送出順序を厳密に管理する機能は重要である。
【００１３】
しかしながら、図３に示したリングバッファ４０４においても、図４に示したシェーピングバッファ４１２においても、先頭の記憶領域あるいはリードポインタで示される記憶領域のセルが読み出されて出力されるタイミングは、新たなセルが入力されるタイミングとは全く独立に、一定のクロックに基づいて決定されている。
このため、上述した手法のいずれを適用した場合においても、次に読み出される記憶領域の位置とセル送出間隔目標値Ｘ０あるいは目標位置ＴＮとの相対位置によっては、セル順序の逆転が起こり得る。例えば、図４に示したシェーピング装置において、新たなセルＡ４が入力されたときに、リードポインタがバッファ番号１６に到達してこのバッファ番号１６を占有していた他のチャネルのセルが出力されると、上述したセルＡ４は、バッファ番号１６に書き込まれてしまうため、バッファ番号１８に格納されたセルＡ３との間でセル順序の逆転が発生する。もちろん、図３に示したシェーピング装置でも同様の順序逆転が発生する可能性がある。
【００１４】
このような順序逆転の発生原因は、これらのシェーピング装置において、直前のセルが書き込まれた位置にかかわらず、セル送出間隔に基づいて算出した目標値を検索の基点として、空きバッファの検索を行っているところにある。
本発明は、シェーピング装置において、セルを格納すべき空き領域を高速に検索するとともにセルの順序逆転を確実に防止可能な空きバッファ検索方法およびこの空きバッファ検索方法を適用したシェーピング装置を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明にかかわる空き領域検索方法は、オフセット算出ステップと、比較ステップと、第１検索ステップと、第２検索ステップとから構成される。
本発明にかかわる空き領域検索方法の原理は、以下の通りである。
複数の格納領域に格納されたデータを所定の時間間隔で順次に出力する構成を備えたバッファに、複数のチャネルそれぞれにかかわるセルを各チャネルに対応して定められた基本間隔に相当する格納領域ごとに格納することにより、各チャネルにおけるセル送出間隔を調整するシェーピング装置に利用され、バッファにセルを格納する際の空き領域を検索するための空き領域検索方法において、オフセット算出ステップは、新たなセルの入力に応じて、対応するチャネルの直前のセルが格納された格納領域と直前のセルがチャネルに対応する基本間隔に基づいて格納されるべきであった格納領域とのずれを示すオフセット値を求める。比較ステップは、オフセット値と基本間隔に相当するシェイパー値とを比較する。第１検索ステップは、オフセット値の方が大きかった場合は、直前のセルが格納された格納領域の次の格納領域からバッファの空き領域を検索する。第２検索ステップは、オフセット値がシェイパー値を超えていない場合は、シェイパー値からオフセット値を差し引いた分だけ直前のセルが格納された格納領域から離れた格納領域からバッファの空き領域を検索する。
【００１６】
このように構成された空き領域検索方法の動作は、下記の通りである。
例えば、チャネルＡにかかわる２つのセルＡ１、Ａ２が既にバッファに格納されているときに、新たなセルＡ３が入力されると、オフセット算出ステップにおいて、セルＡ１とセルＡ２とがそれぞれ格納された格納領域の間隔とチャネルＡに対応する基本間隔に対応するシェイパー値とに基づいて、直前のセルであるセルＡ２に対応する格納位置の目標値と実際の格納場所とのずれを示すオフセット値ＯＳが算出される。そして、比較ステップにおいて、上述したオフセット値ＯＳがシェイパー値ＳＲを超えていない場合に、第２検索ステップにより、オフセット値ＯＳとシェイパー値ＳＲとセルＡ２の格納位置とに基づいて決定した検索開始位置から空き領域を検索することにより、直前のセルとの間に空けるべき間隔とその直前のセルに対応するオフセットとを考慮して、平均的なセル間隔を基本間隔に維持するように、新たなセルＡ３の格納場所を決定する。一方、比較ステップにおいて、オフセット値ＯＳが基本間隔に対応するシェイパー値ＳＲよりも大きいとされた場合は、第１検索ステップにより、オフセット値ＯＳの値にかかわらず、直前のセルＡ２が格納された格納領域の次の格納領域から開始される。
【００１７】
本発明にかかわるシェーピング装置は、バッファと、管理テーブルと、開始位置算出手段と、空き検索手段と、書込手段と、オフセット算出手段と、テーブル更新手段とから構成され、開始位置算出手段は、比較手段と、目標算出手段と、選択手段とから構成される。
本発明にかかわるシェーピング装置の原理は、以下の通りである。
【００１８】
バッファは、複数の格納領域を有し、複数の格納領域に格納されたデータを所定の時間間隔で順次に出力する。管理テーブルは、複数のチャネルそれぞれに対応し、各チャネルにかかわるセルのバッファにおけるアドレスとこのアドレスが各チャネルに対応する基本間隔に基づいて算出された目標位置からずれている量を示すオフセット値とを保持する。開始位置算出手段は、新たなセルの入力に応じて、新たなセルが属するチャネルに対応して管理テーブルに保持された情報とチャネルに対応する基本間隔に基づいて決定されたシェイパー値とに基づいて、新たなセルを格納するための格納領域に対応する検索開始位置を求める。空き検索手段は、検索開始位置からバッファに残されている空き領域を検索する。書込手段は、空き検索手段によって検索された格納領域に、新たなセルを書き込む。オフセット算出手段は、空き検索手段によって検索された格納領域のアドレスとチャネルに対応する基本間隔とに基づいて、このアドレスに対応するオフセット値を算出する。テーブル更新手段は、空き検索手段によって検索された格納領域のアドレスとオフセット算出手段によって算出されたオフセット値とを用いて、管理テーブルにチャネルに対応して保持された情報を更新する。開始位置算出手段において、比較手段は、管理テーブルにチャネルに対応して保持されたオフセット値と基本間隔に対応するシェイパー値とを比較する。開始位置算出手段において、目標算出手段は、シェイパー値からオフセット値を差し引いた値と管理テーブルに保持されたアドレスとに基づいて、新たなセルを格納すべき格納領域の目標位置を算出する。開始位置算出手段において、選択手段は、比較手段によってオフセット値がシェイパー値を超えている旨の比較結果が得られたときに、管理テーブルに保持されたアドレスの次のアドレスを検索開始位置として出力し、他の場合は、目標算出手段によって算出された目標位置を検索開始位置として出力する。
【００１９】
このように構成されたシェーピング装置の動作は、下記の通りである。
開始位置算出手段に備えられた比較手段により、新たに入力されたセルがかかわるチャネルに対応して管理テーブルに保持されたオフセット値がシェイパー値を超えない旨の比較結果が得られている限りは、選択手段により、目標算出手段によって算出された目標位置を検索開始位置として選択することにより、セルがバッファに格納される間隔の平均値をシェイパー値に対応するように制御する。一方、オフセット値がシェイパー値を超えている旨の比較結果が得られた場合には、目標算出手段によって算出された目標位置から直前のセルが格納された位置までは他のセルが格納されていると判断し、直前のセルの格納場所として管理テーブルに格納されたアドレスの次のアドレスを検索開始位置として選択することにより、空き検索手段による無駄な検索処理を省略する。また、これにより、書込手段が新たに入力されたセルを書き込むバッファのアドレスは、直前のセルが書き込まれたアドレスよりも確実に後のアドレスとなる。いずれの場合も、空き検索手段によって検索された格納領域のアドレスに基づいて、オフセット算出手段によってオフセット値が算出され、テーブル更新手段による管理テーブル更新処理に供される。
【発明の効果】
【００２０】
本発明の空き領域検索方法およびこれを用いたシェーピング装置では、新たなセルを格納するための空き領域の検索が、このセルにかかわるチャネルにおける直前のセルの格納位置から遡った位置にある格納領域から開始されることを確実に防ぐことができるので、セルの送出順序を厳格に管理することができる。また、直前のセルの格納位置から遡った位置にある格納領域についての空き領域の検索を明らかに無駄な処理として省略することにより、空き領域の検索に要する時間の短縮を図ることもできる。
【００２１】
このようにして、オフセット値に基づいてセルの送出間隔を調整するとともに、セルの送出順序を確実に、しかも高速に管理することができるので、シェーピング装置を備えた基地局制御装置などのネットワーク機器の信頼性を向上するとともに、その処理速度を向上させることができる。
【発明を実施するための最良の形態】
【００２２】
以下、図面に基づいて、本発明の実施形態について詳細に説明する。
図１に、本発明にかかわるシェーピング装置の実施形態を示す。
なお、図１に示した構成要素のうち、図４に示した各部と同等のものについては、図４に示した符号を付して示し、その説明を省略する。
図１に示したシェーピング装置において、開始位置算出部２１０は、目標位置算出部４１４に加えて、比較器２１１と、アドレス計算部２１２と、セレクタ２１３とを備えている。
【００２３】
この開始位置算出部２１０において、比較器２１１は、バッファ管理テーブル４１３から読み出されたオフセット値ＯＳと入力セルにかかわるチャネルのシェイパー値ＳＲとを比較し、比較結果をセレクタ２１３に入力する。また、アドレス計算部２１２は、バッファ管理テーブル４１３から読み出されたバッファ番号ＢＮに数値「１」を加算したアドレスを出力する。また、図１に示したセレクタ２１３は、上述した比較器２１１による比較結果に応じて、このアドレス計算部２１２の出力と目標位置算出部４１４の出力とのいずれかを選択し、選択したアドレスを空き検索部４１５に検索開始アドレスとして入力する。
【００２４】
また、図１に示したオフセット算出部２１４は、比較器２１１、バッファ管理テーブル４１３および空き検索部４１５から受け取る情報に基づいて、適切なオフセット値を算出し、書込処理部４１６に入力する。
次に、図１に示したシェーピングバッファ４１２に新たなセルを書き込む動作を詳細に説明する。
【００２５】
図２に、シェーピングバッファにセルを書き込む動作を表す流れ図を示す。
チャネルＡに属する新たなセルＡ４が入力されると（ステップ３０１）、開始位置算出部２１０は、入力されたセルにかかわるチャネルに対応してバッファ管理テーブル４１３に格納された情報を参照する（ステップ３０２）。
例えば、図５に示したように、入力されたセルＡ４よりも前のセルＡ３がシェーピングバッファ４１２に格納されている場合には、ステップ３０２において、該当するチャネルにおいて入力セルの直前に位置するセルの格納場所を示すバッファ番号ＢＮと対応するオフセット値ＯＳとが得られる。この場合には、ステップ３０３の肯定判定として、ステップ３０４に進み、比較器２１１により、オフセット値ＯＳと該当するチャネルのシェイパー値ＳＲとを比較する。
【００２６】
図５に示したセルＡ３が属するチャネルＡ対応してバッファ管理テーブル４１３に保持されたオフセット値ＯＳ（＝８）は、シェイパー値ＳＲ（＝５）よりも大きいので、ステップ３０４の肯定判定となり、セレクタ２１３により、アドレス計算部２１２によって算出されたアドレス、つまり、バッファ番号ＢＮに数値「１」を加算して得られるアドレスが、検索開始位置ＳＳとして選択される（ステップ３０５）。また、このとき、オフセット算出部２１４は、オフセット値ＯＳがシェイパー値ＳＲ以上である旨の比較結果に応じて、オフセット値ＯＳからシェイパー値ＳＲを差し引いた値に数値「１」を加算して新たなオフセット値の初期値を求める（ステップ３０６）。
【００２７】
一方、オフセット値ＯＳがシェイパー値ＳＲ未満である場合（ステップ３０４の否定判定）に、セレクタ２１３は、従来と同様に、目標位置算出部４１４によって算出された目標位置に対応するアドレスを検索開始位置ＳＳとして選択し（ステップ３０７）、また、オフセット算出部２１４は、オフセット値ＯＳの初期値を数値「０」とする（ステップ３０８）。
【００２８】
このように、比較器２１１の出力に応じて、セレクタ２１３が目標位置算出部４１４あるいはアドレス計算部２１２の出力を選択することにより、空き検索部４１５に適切な検索開始位置ＳＳからシェーピングバッファ４１２の空き領域を検索させることができる。つまり、上述した式（１）で求めた目標位置が直前のセルの格納場所を示すバッファ番号ＢＮよりも後のアドレスを指している場合は、空き検索部４１５にこの目標位置を検索開始位置として渡し、目標位置がバッファ番号ＢＮを遡る場合は、空き検索部４１５にステップ３０５で求めた検索開始位置を渡して、空き領域の検索に供することができる。
【００２９】
このようにして検索開始位置を制御することにより、ステップ３０９において、空き検索部４１５によって検索される空き領域は、確実に直前のセルが格納されたアドレスよりも後ろ側に位置することになる。また、図２に示したステップ３０６およびステップ３０８のように、オフセット値ＯＳの初期値を決定し、空き検索部４１５によって検索開始位置の格納領域から順次にその領域が空いているか否かを確認していく毎に、オフセット算出部２１４が、この初期値に数値「１」を加算していくことにより、新たなセルの格納場所に対応するオフセット値ＯＳを求める（ステップ３１０）。
【００３０】
書込処理部４１６は、空き検索部４１５で得られたバッファ番号ＢＮとともにこのオフセット値ＯＳを受け取り、バッファ番号ＢＮで示されるシェーピングバッファ４１２の格納領域に新たなセルを書き込むとともに（ステップ３１１）、このバッファ番号ＢＮおよびオフセット値ＯＳを用いて、該当するチャネルに対応するバッファ管理テーブル４１３の情報を更新し（ステップ３１２）、セルの書込処理を終了する。
【００３１】
このようにして、オフセット値ＯＳによって各チャネルに属するセルの送出間隔の調整を図りながら、オフセット値ＯＳがシェイパー値ＳＲ以上となった場合に従来の技術において発生していた無駄な上にセルの順序逆転を発生させる危険性のある検索処理、すなわち、直前のセルの格納位置を示すバッファ番号ＢＮよりも遡った位置からバッファ番号ＢＮまでの格納領域に関する空き検索処理を排除することができる。
【００３２】
これにより、無駄な空き検索処理を省略して空き検索に要する時間の短縮を図るとともに、セルの格納順序の逆転を確実に防ぐことができる。
なお、新たに入力されたセルがそのチャネルの先頭のセルだった場合などには、バッファ管理テーブル４１３にそのチャネルに対応するバッファ番号などの情報が格納されていないので、ステップ３０３の否定判定となる。この場合に、開始位置算出部２１０は、読出処理部４１１による読出位置を示すリードポインタＲＰを検索開始位置ＳＳとして空き検索部４１５に渡し（ステップ３１３）、これに応じて、空き検索部４１５により、リードポインタＲＰ以降で最も早く読み出される位置にある空き領域が検索される（ステップ３１４）。また、この場合に、オフセット算出部２１４は、オフセット値ＯＳとして数値「０」を出力し（ステップ３１５）、上述した空き検索部４１５によって検索されたバッファ番号ＢＮとともに書込処理部４１６によるセルの書込処理に供する。
【００３３】
また、バッファ管理テーブル４１３に各チャネルに対応して格納されたバッファ番号ＢＮは、読出処理部４１１により、そのアドレスに格納されたセルが読み出されたときにクリアされる。つまり、読出処理部４１１は、リードポインタＲＰと各チャネルに対応して格納されたバッファ番号ＢＮとを照合し、一致した場合にそのバッファ番号およびオフセット値をクリアして、該当するチャネルに属するセルがシェーピングバッファ４１２に格納されていないことを示す。
【産業上の利用可能性】
【００３４】
本発明にかかわる空き領域検索方法およびシェーピング装置は、オフセット値に基づいてセルの送出間隔を調整するとともに、セルの送出順序を確実に、しかも高速に管理するものであるので、ほぼ全てのチャネルが同等に優先度を持つような用途において極めて有用である。
【図面の簡単な説明】
【００３５】
【図１】本発明にかかわるシェーピング装置の実施形態を示す図である。
【図２】シェーピングバッファにセルを書き込む動作を表す流れ図である。
【図３】従来のシェーピング装置の構成例を示す図である。
【図４】シェーピング装置の別構成例を示す図である。
【図５】オフセット値によるシェーピング動作を説明する図である。
【符号の説明】
【００３６】
２１０  開始位置算出部
２１１  比較器
２１２  アドレス計算部
２１３  セレクタ
２１４  オフセット算出部
４０１  内部バッファ
４０２  監視部
４０３  セル格納部
４０４  リングバッファ
４１１  読出処理部
４１２  シェーピングバッファ
４１３  バッファ管理テーブル
４１４  目標位置算出部
４１５  空き検索部
４１６  書込処理部
【図１】
2005223787.tif 000003
【図２】
2005223787.tif 000004
【図３】
2005223787.tif 000005
【図４】
2005223787.tif 000006
【図５】
2005223787.tif 000007