(57)【特許請求の範囲】
【請求項１】
パケットの転送速度が予め定めた基準速度以内になるようにシェーピング制御を行うシェーピング制御装置において、
パケットの属する呼の理論的転送時刻を演算する理論的転送時刻演算手段と、
演算された前記理論的転送時刻に関連する情報を、規格化された時間単位で区分けしてパケットの属する呼に関連づけて保持する第１の保持手段と、
前記理論的転送時刻演算手段にて演算された理論的転送時刻と前記基準時刻との差分が所定時間以内の場合に、該理論的転送時刻に関する情報を対応するパケットに関連づけて保持する第２の保持手段と、
前記第２の保持手段に保持されている前記情報に対応する理論的転送時刻と基準時刻とを比較し、前記基準時刻以前の前記情報を抽出する抽出手段と、を備え、
前記抽出手段で抽出された情報に基づいて、前記呼に属するパケットの転送を行うことを特徴とするシェーピング制御装置。
【請求項２】
前記抽出手段により抽出されたパケットの属する呼の転送時刻に基づいて、該呼の理論的転送時刻を演算し、前記第１または第２の保持手段に前記情報を保持することを特徴とする請求項１に記載のシェーピング制御装置。
【請求項３】
前記第１の保持手段は、出力ポート種別、回線品質種別、および通信速度種別の少なくとも一つを含む呼の範疇に基づいて、それぞれ異なる複数の時系列を設定し、これら時系列にパケットの属する呼を区分けすることを特徴とする請求項１または２に記載のシェーピング制御装置。
【請求項４】
前記第１の保持手段は、それぞれ異なる規格化時間を有する複数の時系列を設定し、これら時系列にパケットの属する呼を区分けすることを特徴とする請求項１または２に記載のシェーピング制御装置。
【請求項５】
前記第１の保持手段は、出力ポート種別、回線品質種別、および通信速度種別の少なくとも一つを含む呼の範疇に基づいて、前記複数の時系列のそれぞれに対応する規格化時間を設定することを特徴とする請求項４に記載のシェーピング制御装置。
【請求項６】
前記抽出手段は、前記呼の範疇に基づいて優先順位付けを行い、この優先順位付けした結果に基づいて、前記第１の保持手段に保持されている前記情報の一部を前記第２の保持手段に保持させることを特徴とする請求項３または５に記載のシェーピング制御装置。
【請求項７】
前記第２の保持手段は、パケットの属する呼が転送可能か否かを示す転送可能識別子を該呼に関連づけて保持し、
前記基準時刻以前の前記理論的転送時刻を有するパケットの属する呼に対応する前記転送可能識別子を転送可能状態にセットする識別子設定手段をさらに備え、
前記抽出手段は、前記第２の保持手段に保持されている呼のうち、前記転送可能識別子が転送可能状態にセットされている呼に関連する情報を抽出することを特徴とする請求項１乃至５のいずれかに記載のシェーピング制御装置。
【請求項８】
パケットの転送速度が予め定めた基準速度以内になるようにシェーピング制御を行うシェーピング制御装置において、
パケットの属する呼の理論的転送時刻を演算する理論的転送時刻演算手段と、
前記理論的転送時刻演算手段にてパケットの属する呼の理論的転送時刻を演算する前に、パケットに関連する情報を呼単位で保持するパケット情報保持手段と、
演算された前記理論的転送時刻に関連する情報を、規格化された時間単位で区分けして保持する第１の保持手段と、
前記理論的転送時刻演算手段にて演算された理論的転送時刻と前記基準時刻との差分が所定時間以内の場合に、該理論的転送時刻に関する情報を対応するパケットに関連づけて保持する第２の保持手段と、
前記第２の保持手段から転送されたパケットの属する呼と同一の呼のパケットを、前記パケット情報保持手段から抽出して前記理論的転送時刻演算手段に転送する抽出手段と、を備えることを特徴とするシェーピング制御装置。
【請求項９】
前記抽出手段は、前記第１の保持手段に保持されている前記情報を、後入れ先出し(LIFO:Last In Fast Out)方式で管理することを特徴とする請求項１乃至８のいずれかに記載のシェーピング制御装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットの転送速度が予め定めた基準速度を越えないように制御するシェーピング制御方法およびシェーピング制御装置に関する。
【０００２】
【従来の技術】
パケット通信では、回線の利用効率を高めるために、転送速度が予め定めた上限帯域を越えないように、転送速度を事業者が既定した基準速度以内に維持するシェーピングと呼ばれる制御を行っている。
【０００３】
従来、パケットを転送する時間割を予め決定してリスト等で管理する手法（時間割先決定方式）や、パケットの転送時刻前に全要素の情報を走査し、その都度、転送可能か否かを判断する手法（転送時走査方式）等が提案されている。
【０００４】
時間割先決定方式は、パケットが到着した時点で、パケットの属する呼の転送可能時刻を計算し、その計算結果に基づいて、パケットを転送順に並んだリストに挿入する方式である。この方式の場合、パケットの到着した順番と、パケットを転送する順番とは一般的に異なるため、高精度のシェーピングを行うには、すでに並んでいる要素を走査し、転送可能時刻順に随時並び替える処理が必要となる。したがって、転送順序を正しく設定するには、全要素を走査して、各要素の理論的転送時刻を互いに比較する必要がある。
【０００５】
【発明が解決しようとする課題】
しかしながら、要素を記憶している保持手段に対するアクセス回数には制限があるため、パケットの転送周期内で走査可能な要素の数は限られており、高精度で大量の呼に対してシェーピングを行うことは困難である。
【０００６】
一方、転送時走査方式では、転送前に、全要素の中から転送可能な要素を走査するため、呼が接続する物理層の状況等を勘案することが可能である。しかしながら、物理層の状況はパケット単位で変化しており、また、高速レートの呼のパケットは保持手段に滞留する時間が短いため、高精度のシェーピングを行うには、毎パケット周期で全要素を走査する必要がある。ところが、上述したように、保持手段に対するアクセス回数には制限があるため、大量の呼に対して高精度にシェーピングを行うことは困難である。
【０００７】
本発明は、このような点に鑑みてなされたものであり、その目的は、大量の呼に対して高精度にシェーピングを行うことが可能なシェーピング制御方法およびシェーピング制御装置を提供することにある。
【０００８】
【課題を解決するための手段】
上述した課題を解決するために、本発明の一態様によれば、パケットの転送速度が予め定めた基準速度以内になるようにシェーピング制御を行うシェーピング制御装置において、パケットの属する呼の理論的転送時刻を演算する理論的転送時刻演算手段と、演算された前記理論的転送時刻に関連する情報を、規格化された時間単位で区分けしてパケットの属する呼に関連づけて保持する第１の保持手段と、前記理論的転送時刻演算手段にて演算された理論的転送時刻と前記基準時刻との差分が所定時間以内の場合に、該理論的転送時刻に関する情報を対応するパケットに関連づけて保持する第２の保持手段と、前記第２の保持手段に保持されている前記情報に対応する理論的転送時刻と基準時刻とを比較し、前記基準時刻以前の前記情報を抽出する抽出手段と、を備え、前記抽出手段で抽出された情報に基づいて、前記呼に属するパケットの転送を行うことを特徴とするシェーピング制御装置が提供される。
【０００９】
また、本発明の一態様によれば、パケットの転送速度が予め定めた基準速度以内になるようにシェーピング制御を行うシェーピング制御装置において、パケットの属する呼の理論的転送時刻を演算する理論的転送時刻演算手段と、前記理論的転送時刻演算手段にてパケットの属する呼の理論的転送時刻を演算する前に、パケットに関連する情報を呼単位で保持するパケット情報保持手段と、演算された前記理論的転送時刻に関連する情報を、規格化された時間単位で区分けして保持する第１の保持手段と、前記理論的転送時刻演算手段にて演算された理論的転送時刻と前記基準時刻との差分が所定時間以内の場合に、該理論的転送時刻に関する情報を対応するパケットに関連づけて保持する第２の保持手段と、前記第２の保持手段から転送されたパケットの属する呼と同一の呼のパケットを、前記パケット情報保持手段から抽出して前記理論的転送時刻演算手段に転送する抽出手段と、を備えることを特徴とするシェーピング制御装置が提供される。
【００１９】
【発明の実施の形態】
以下、本発明に係るシェーピング制御装置について、図面を参照しながら具体的に説明する。
【００２０】
（第１の実施形態）
図１は本発明に係るシェーピング制御装置の第１の実施形態のブロック図である。図１のシェーピング制御装置は、理論的転送時刻演算部（理論的転送時刻演算手段）１と、理論的転送時刻保持部２と、二次時間管理部（第１の保持手段）３と、理論的転送時刻採集部（識別子設定手段）４と、一次時間管理部（第２の保持手段）５と、転送決定部（抽出手段）６とを備えている。
【００２１】
理論的転送時刻保持部２は、仮想パス（ＶＰ）や仮想回線（ＶＣ）などのシェーピング対象ごとに、ピークレート(peak rate)やサステイナブルレート(sustainable rate)などの理論的転送時刻を、パケットの属する呼に対応づけて保持する。
【００２２】
理論的転送時刻演算部１は、理論的転送時刻保持部２に保持されている情報に基づいて、パケットの属する呼の理論的転送時刻を演算し、その演算結果により、理論的転送時刻保持部２に保持されている時刻を更新する。
【００２３】
二次時間管理部３は、転送待ちの呼に関する情報を、規格化された時間単位で区分けして保持する。図２は二次時間管理部３の一例を示す図であり、転送待ちの呼を所定の時間区分で分類した例を示している。図中の各升目が時間区分に対応する。
【００２４】
図２は複数の時系列ＴＧ１〜ＴＧ３がそれぞれ異なる時間区分を有する例を示している。図２の時系列ＴＧ１は時間区分ＴＤ11〜ＴＤ1nを有し、時系列ＴＧ２は時間区分ＴＤ21〜ＴＤ2nを有し、時系列ＴＧ３は時間区分ＴＤ31〜ＴＤ3nを有する。
【００２５】
図２の時系列ＴＧ１〜ＴＧ３は、転送速度に応じて分類されており、高速側の時間区分の単位時間（一つの時間区分に割り当てられる時間間隔）を、低速側の時間区分の単位時間よりも短くしている。例えば、図２の時系列ＴＧ１の単位時間は16パケット周期、時系列ＴＧ２の単位時間は64パケット周期、時系列ＴＧ３の単位時間は256パケット周期である。
【００２６】
また、各時系列ごとに、先頭時間区分と最終時間区分とを識別する時系列指示子が設けられている。ここで、時系列指示子が示す先頭の時間区分（図２の左端）が、最も現在時刻に近い時間区分であり、末尾の時間区分（図２の右端）は最も現在時刻から離れた時間区分である。
【００２７】
図２の時系列ＴＧ１では、時間区分ＴＤ11〜ＴＤ1nの順番に時系列が過去から未来に進み、時間区分ＴＤ11内には、時系列ＴＧ１の先頭の時間区分に転送される呼の理論的転送時刻の集合が収容されている。また、時間区分ＴＤ1n内には、時系列ＴＧ１の最後の時間区分に転送される呼の理論的転送時刻の集合が収容されている。
【００２８】
同様に、時系列ＴＧ２では、時間区分ＴＤ21〜ＴＤ2nの順番に時系列が過去から未来に進み、時系列ＴＧ３では、時間区分ＴＤ31〜ＴＤ3nの順番に時系列が過去から未来に進む。
【００２９】
図２の時間区分のそれぞれには、時間区分内の要素の先頭、末尾および長さ等を管理するための時間区分指示子が時間区分ごとに設けられている。ここで、時間区分指示子の先頭から末尾の方向は、時間区分内の要素の接続順番を表しており、必ずしも時間の進行方向を関連づける必要はない。
【００３０】
図２の時系列ＴＧ１〜ＴＧ３は、出力ポート種別、回線品質種別、および通信速度種別等の呼の範疇に基づいて設定される。各時系列はそれぞれ異なる規格化時間を備えており、これら規格化時間の長さは、呼の範疇に基づいて設定される。
【００３１】
図１の一次時間管理部５は、例えば図３に示すように、パケットの属する呼に関連づけられた呼識別子と、理論的転送時刻と、転送時刻に到達したことを意味する転送可能識別子とを対応づけた管理テーブルを有する。一次時間管理部５には、二次時間管理部３に格納された呼情報の一部が移動もしくは複製して格納される。
【００３２】
このとき、一次時間管理部５に格納された呼情報を後入れ先出し(LIFO:Last In First Out)方式で二次時間管理部３に転送するのが望ましい。後入れ先出し方式を採用すれば、転送する情報の検索と情報の読み出しに要する時間が短くなるためである。
【００３３】
図１の転送決定部６は、一次時間管理部５に保持されている理論的転送時刻と現在時刻とをパケット周期ごとに比較し、現在時刻と一致またはより過去を示す理論的転送時刻に対応する呼の転送可能識別子をセットする。
【００３４】
転送決定部６は、転送可能識別子がセットされている呼に関連する呼情報の中から、転送する呼を優先度等を考慮に入れて選択し、呼情報を信号線を介して出力する。転送決定部６は、理論的転送時刻保持部２に保持されている、呼の理論的転送時刻を再計算し、必要があれば更新を行う。
【００３５】
図４は理論的転送時刻演算部１の処理動作を示すフローチャートである。まず、信号線を介して入力されたパケットに対して、理論的転送時刻保持部２に保持されている時刻に基づいて理論的転送時刻を演算する（ステップＳ１）。
【００３６】
ここでは、シェーピングのピークレートやサステイナブルレート等の各パケットの理論的転送時刻を演算する。シェーピング対象は、例えば、出力ポートの種別、回線品質の種別、通信速度の種別、仮想回線の種別、および仮想パスの種別などである。
【００３７】
次に、演算された理論的転送時刻と現在時刻との差分が所定時間以内（例えば、各時系列の単位時間以内）か否かを判定する（ステップＳ２）。上記の差分が所定時間以内であれば、理論的転送時刻演算部１は、演算した理論的転送時刻を呼情報に関連づけて一次時間管理部５に格納する（ステップＳ３）。
【００３８】
次に、上記の差分がゼロか否かを判定する（ステップＳ４）。差分がゼロ、すなわち、理論的転送時刻が現在時刻と一致する場合には、一次時間管理部５内の該当する呼に対応する転送可能識別子を転送可能状態にセットする（ステップＳ５）。
【００３９】
一方、上記の差分が所定時間より大きければ、理論的転送時刻から対応する時間区分を演算し、時間区分指示子の情報により、二次時間管理部３の対応する時間区分の待ち行列に理論的転送時刻を呼情報に関連づけて保持する（ステップＳ６）。
【００４０】
このとき、演算された理論的転送時刻が、時系列的に設けられた最後の時間区分の時間帯よりも未来の場合には、同一の時系列指示子の示す末尾の時間区分に、理論的転送時刻を呼情報に関連づけて保持する。なお、時間区分内の配列は、必ずしも理論的転送時刻の時間順になっていなくてもよい。
【００４１】
図１の理論的転送時刻採集部４は、二次時間管理部３内の時系列を優先度等の方法により選択し、時系列の最初に転送を行う集合の保持されている時間区分から、理論的転送時刻の呼情報複数を取り出し、取り出した呼情報を一次時間管理部５に呼情報に関連づけて保持する。
【００４２】
例えば、時系列ＴＧ１が選択された場合には、時系列の時系列指示子が示す先頭の時間区分の待ち行列の中から、時間区分の時間区分指示子が示す先頭の時間区分の要素を複数抽出する。また、理論的転送時刻採集部４は、複数の時間区分の中から呼情報を選択してもよい。
【００４３】
このとき、一次時間管理部５に保持された個々の理論的転送時刻が現在時刻と一致、または過去の場合には、一次時間管理部５に保持された理論的転送時刻に関連づけて転送可能識別子をセットする。
【００４４】
このように、本実施形態は、呼情報をシェーピング対象ごとに二次時間管理部３に分類して格納して転送順に並び替え、転送準備が整うと一次時間管理部５に転送するため、大量の呼を高精度にシェーピングすることができる。
【００４５】
また、異なる複数のシェーピング対象に対して、それぞれ最適なシェーピングを行うことができる。
【００４６】
また、一次時間管理部５に保持された呼に関する情報を転送するか否かを転送可能識別子で識別するようにしたため、転送するか否かの判断を迅速に行うことができる。
【００４７】
また、演算された理論的転送時刻と基準時刻との比較結果に基づいて、二次時間管理部３から一次時間管理部５に呼情報を転送するタイミングを設定するため、基準時刻を変更することにより、一次時間管理部５の内容を任意に変更することができる。
【００４８】
（第２の実施形態）
図５は本発明に係るシェーピング制御装置の第２の実施形態のブロック図である。図５では、図１と共通する構成部分には同一符号を付しており、以下では相違点を中心に説明する。
【００４９】
図５のシェーピング制御装置は、図１に新たにパケット情報保持部７を追加した構成になっている。パケット情報保持部７は、理論的転送時刻演算部１で演算処理を行う前に、入力されたパケットに関連する情報を呼単位で保持する。
【００５０】
図５の転送決定部６は、一次時間管理部５と二次時間管理部３が呼に関連する情報を保持していない場合には、この呼に関連する情報を理論的転送時刻演算部１に送る。一方、一次時間管理部５や二次時間管理部３が呼に関連する情報を保持している場合には、そのまま待機する。
【００５１】
また、転送決定部６は、パケットが外部に転送された場合には、転送されたパケットの属する呼と同一の呼に関連する情報を、パケット情報保持部７から抽出して理論的転送時刻演算部１に送る。理論的転送時刻演算部１に送られたパケットに対しては、図４と同様の処理が行われる。
【００５２】
このように、図５の転送決定部は、一次時間管理部５と二次時間管理部３の内部に、同一の呼に属するパケット（に関連づけられた情報）が一つしか存在しないように制御を行う。
【００５３】
このため、一次時間管理部３や二次時間管理部５内にパケットが滞留しなくなり、パケットの転送時刻を正確に演算することができる。したがって、理論的転送時刻を演算してから実際に転送されるまでの期間を最小にすることができ、転送時刻の精度向上が図れる。
【００５４】
上述した実施形態では、一次時間管理部５と二次時間管理部３を用いて２階層に階層化する例を示しているが、３階層以上に階層化してもよい。
【００５５】
また、一次時間管理部５と二次時間管理部３の少なくとも一方における時系列と時間区分の時間的前後関係をリスト構造で管理すれば、内部構成を簡略化できる。あるいは、一次時間管理部５と二次時間管理部３の少なくとも一方を連想メモリで構成してもよい。
【００５６】
【発明の効果】
以上詳細に説明したように、本発明によれば、パケットの属する呼の転送順序を、シェーピング対象ごとに階層的に設定するため、大量の呼を精度よくシェーピングすることができる。
【００５７】
また、理論的転送時刻に関連する情報を、出力ポートの種別、回線品質の種別、および通信速度の種別等の呼の範疇ごとに異なる時間単位で区分けして保持する第１の保持手段を設けるため、呼の範疇ごとに、最適な転送順序を設定できる。
【図面の簡単な説明】
【図１】本発明に係るシェーピング制御装置の第１の実施形態のブロック図。
【図２】二次時間管理部の内部構成を示す図。
【図３】一次時間管理部の内部構成を示す図。
【図４】理論的転送時刻演算部の処理動作を示すフローチャート。
【図５】本発明に係るシェーピング制御装置の第２の実施形態のブロック図。
【符号の説明】
１  理論的転送時刻演算部
２  理論的転送時刻保持部
３  二次時間管理部
４  理論的転送時刻採集部
５  一次時間管理部
６  転送決定部
【図１】
0003713411.tif 000002
【図２】
0003713411.tif 000003
【図３】
0003713411.tif 000004
【図４】
0003713411.tif 000005
【図５】
0003713411.tif 000006