(57)【要約】【課題】  パケット転送制御装置において、最小の転送終了予定時刻を検索する処理時間を短縮することにより高速リンクに適用可能とするとともに、回路規模を小さくすることを目的としている。【解決手段】  パケット転送制御装置において、キューに格納された先頭パケットの転送終了予定時刻に対応する時刻情報と対応づけて、前記先頭パケットに対応する識別情報を記憶する識別情報記憶部と、前記識別情報記憶部で記憶された識別情報のうち、最小の時刻情報に対応する識別情報を読み出し、この読み出された識別情報に対応する先頭パケットの転送を指示するパケット転送順序制御部と、を備える。【選択図】  図１
2006005388.tif 000002
【特許請求の範囲】
【請求項１】
キューに格納された先頭パケットの転送終了予定時刻に対応する時刻情報と対応づけて、前記先頭パケットに対応する識別情報を記憶する識別情報記憶部と、
前記識別情報記憶部で記憶された識別情報のうち、最小の時刻情報に対応する識別情報を読み出し、この読み出された識別情報に対応する先頭パケットの転送を指示するパケット転送順序制御部と、
を備えることを特徴とするパケット転送制御装置。
【請求項２】
前記転送順序制御部は、前記識別情報記憶部で記憶された識別情報のうち、最小の時刻情報に対応し、かつ最初に記憶された識別情報を読み出し、この読み出された識別情報に対応する先頭パケットの転送を指示することを特徴とする請求項１に記載のパケット転送制御装置。
【請求項３】
前記識別情報記憶部は、キューに格納された先頭パケットの転送終了予定時刻に対応する時刻情報と対応づけて、前記キューへの格納順に前記先頭パケットに対応する識別情報を記憶することを特徴とする請求項２に記載のパケット転送制御装置。
【請求項４】
キューに格納された先頭パケットの転送終了予定時刻の計算値と、この計算値に対応する時刻情報の値との差分に基づいて、このキューに格納された次の先頭パケットの転送終了予定時刻を計算する転送終了予定時刻計算部を備えることを特徴とする請求項１〜請求項３に記載のパケット転送制御装置。
【請求項５】
前記識別情報記憶部は、前記時刻情報と識別情報とを対応づけるテーブルを用いることを特徴とする請求項１に記載のパケット転送制御装置。
【請求項６】
キューに格納された先頭パケットの転送終了予定時刻に対応する時刻情報と対応づけて、前記先頭パケットに対応する識別情報を記憶する識別情報記憶工程と、
前記識別情報記憶工程で記憶された識別情報のうち、最小の時刻情報に対応する識別情報を読み出し、この読み出された識別情報に対応する先頭パケットの転送を指示するパケット転送順序制御工程と、
を備えることを特徴とするパケット転送制御方法。
【請求項７】
前記転送順序制御工程は、前記識別情報記憶工程で記憶された識別情報のうち、最小の時刻情報に対応し、かつ最初に記憶された識別情報を読み出し、この読み出された識別情報に対応する先頭パケットの転送を指示することを特徴とする請求項６に記載のパケット転送制御方法。
【請求項８】
前記識別情報記憶工程は、キューに格納された先頭パケットの転送終了予定時刻に対応する時刻情報と対応づけて、前記キューへの格納順に前記先頭パケットに対応する識別情報を記憶することを特徴とする請求項７に記載のパケット転送制御方法。
【請求項９】
キューに格納された先頭パケットの転送終了予定時刻の計算値と、この計算値に対応する時刻情報の値との差分に基づいて、このキューに格納された次の先頭パケットの転送終了予定時刻を計算する転送終了予定時刻計算工程を備えることを特徴とする請求項６〜請求項８に記載のパケット転送制御方法。
【請求項１０】
前記識別情報記憶工程は、前記時刻情報と識別情報とを対応づけるテーブルを用いることを特徴とする請求項６に記載のパケット転送制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、パケット転送システムにおけるパケットの転送順序制御技術に関するものである。
【背景技術】
【０００２】
契約しているユーザ毎やフロー毎やサービスクラス毎にパケットを一時的にためておく多数のキューを備えた可変長パケット転送装置において、従来のパケットの転送順序制御（スケジューリング）方式の１つとして、重み付け公平キューイング（ＷＦＱ : Weighted Fair Queueing）が知られている（例えば特許文献１参照）。この方式では、最も早く転送を終えることができるパケットを選択するように、各キュー間のパケットに対して、転送終了予定時刻による転送順序の重み付け制御を行って、キュー間の公平パケット転送を図るとともに、使用されていない帯域（剰余リソース）を、アクティブキュー（転送動作を必要とするパケットが格納されているキュー）に公平に割り当ててリソースを有効利用し、アクティブキューのパケットをより高速に転送し、サービスの向上を図っている。
【０００３】
【特許文献１】特開２０００−１０１６３７号公報（第３頁〜第４頁）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
特許文献１に開示された従来のパケット転送制御装置においては、全キューの先頭パケットの転送終了予定時刻から最小のものを検索する必要がある。この検索処理は、例えば、キューの数が数千〜数万と膨大な場合には、Ethernet（登録商標）における最小パケット(64 byte)を転送する時間内に行うことは困難であるという問題点があった。さらに、この検索処理を厳密に行う場合は、全キューの先頭パケットの転送終了予定時刻をレジスタ等に保持し、最小のものを検索する必要があることから、回路規模が膨大になるという問題が生じる。
【０００５】
この発明は、上述のような課題を解決するためになされたもので、パケット転送制御装置において、最小の転送終了予定時刻を検索する処理時間を短縮することにより、例えばEthernet（登録商標）のような高速リンクに適用可能とするとともに、回路規模を小さくすることを目的としている。
【課題を解決するための手段】
【０００６】
この発明に係るパケット転送制御装置は、キューに格納された先頭パケットの転送終了予定時刻に対応する時刻情報と対応づけて、前記先頭パケットに対応する識別情報を記憶する識別情報記憶部と、前記識別情報記憶部で記憶された識別情報のうち、最小の時刻情報に対応する識別情報を読み出し、この読み出された識別情報に対応する先頭パケットの転送を指示するパケット転送順序制御部と、を備えるものである。
【発明の効果】
【０００７】
この発明は、パケット転送制御装置において、処理時間を短縮することにより高速リンクに適用可能とするとともに、回路規模を小さくすることができる。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
この発明の実施の形態１によるパケット転送制御装置は、転送終了予定時刻毎にＦＩＦＯ(First-In-First-Out)とその有無情報を設けることにより、パケットの入力もしくは出力毎に発生する足し算と、該当するＦＩＦＯへの情報の書き込みと、出力によって仮想時刻ＦＩＦＯが空になった場合に行うビットスキャン程度の処理で済むようにしているので、処理時間を短縮することにより高速リンクに適用可能とするとともに、回路規模を小さくすることができるものである。
【０００９】
図１、図２はこの発明の実施の形態１によるパケット転送制御装置を示す構成図である。
図１において、多重されたパケットは主信号入力信号１−１を解して、そのパケットのヘッダにてＷＦＱ(Weighted Fair Queueing)制御を行う単位であるキュー識別を行うキュー識別手段１−２へ入力され、パケットデータ及び識別情報を後段のパケット保持制御手段１−４に伝え、実際にフレームを格納するメモリ１−７に書き込まれる。パケットの到着と同時にキュー毎に外部設定手段１−６にて設定可能な重み情報保持手段１−５の情報と共に、そのパケットが新たにキューの先頭となる場合は、識別情報記憶部およびパケット転送順序制御部としてのＷＦＱ制御手段１−１０に情報通知信号１−８を伝え、そのＷＦＱ制御手段は、その帯域制御にて最も出力するのに適したパケットを決定後、パケット保持制御手段１−４へ読出命令１−９を出力し、それによってパケット出力信号１−１１によりパケットが転送される。なお、出力許可信号１−１２にて、例えばＰＡＵＳＥ制御の様に転送先から出力が止められる場合に使用され、許可されるまで出力をしない制御を行う。
【００１０】
次に図１におけるＷＦＱ制御手段１−１０の構成を、図２を用いて説明する。
図２において、まず入力側は、情報通知信号(内訳はキューＩＤ、パケット長、1/ウエイト、トリガパルス)１−８は、優先度情報計算手段２−１にてパケット長×1/ウエイトの計算処理を行い優先度Fi,1を求め、後段の加算器２−２にて仮想時刻レジスタ２−３の仮想時刻T0とその優先度Fi,1との足し算を行い、転送終了予定時刻Tedを求め、そのTedに対応する仮想時刻ＦＩＦＯ有無(レジスタ)２−５の該当する仮想時刻に対して“１”をセットすると共に、Tedに該当する識別情報記憶部としての仮想時刻ＦＩＦＯ(メモリ)２−４に識別情報としてのキューＩＤとパケット長をライトする。
【００１１】
一方、出力側は、ＦＩＦＯ時刻有無ビットスキャン２−７において、仮想時刻ＦＩＦＯレジスタ２−５のＥＸＩＳＴ信号の全nビットのＯＲ論理にてＥＸ信号を出力間隔制御２−６に出力し、そのトリガにて出力間隔制御２−６は開始命令及び仮想時刻ＦＩＦＯ(メモリ)２−４からのＥＭＰＴＹ（空き）信号が”1”でない場合はリードＥＮＢを出力して、出力すべきキューＩＤとレングス（パケット長）を読み出した後、ＥＭＰＴＹ信号が”1”であった場合は、ＦＩＦＯ時刻有無ビットスキャン２−７を起動し、その結果にて仮想時刻レジスタ２−３を更新する。なお、出力間隔制御２−６は、仮想時刻ＦＩＦＯ(メモリ)２−４からのパケット長情報と、外部からの出力許可信号１−１２により出力間隔の制御を行う。
【００１２】
次に図３，図４を用いて動作について説明する。
図３は仮想時刻を横軸に仮想時刻が左に流れている状態を示しており、旧時刻T-1以前の状態では、F1とF2とF3とF4とF8が存在しており、F1を読出したことによりT-1となり、T-1からF2を読出したことによりT0となると同時にF2＝4のフレームがそのF2を読み出したことにより新たに先頭になった状態を示している。
【００１３】
一方図４においては、より詳細な動作イメージを示しており、図３と同じ動作が行われているとする。図４において、F2を出力する出力間隔制御２−６で読み出したことにより、新たに新先頭となるフレームの情報が到着し、優先度情報計算手段２−１でlength/Weightの計算処理後、仮想時刻レジスタ２−３の現在仮想時刻T0と、加算器２−２にて足され、該当する仮想時刻ＦＩＦＯ時刻９の仮想時刻ＦＩＦＯ(メモリ)２−４にそのキューＩＤとパケット長が書き込まれる。その後、仮想時刻５の仮想時刻ＦＩＦＯ有無ビットを”0”に変更する。次回の出力機会を得た時は、現在仮想時刻をＦＩＦＯ時刻有無ビットスキャン２−７の処理にて時刻T0＝５の後で”１”であるビットをビット検索し、Tn=7を見つけて、現在仮想時刻T0を7にセットするとともに仮想時刻ＦＩＦＯ番号７にあるF4を出力する。次回から新先頭となるパケットが到着した場合は、図３のF3とF4が出力し終わるまでこの仮想時刻T0=７を保持し、加算器２−２のＢの入力として使用する。
【００１４】
出力間隔制御２−６にて次回の出力は仮想時刻ＦＩＦＯ番号７にあるF4を読み出したが、この場合、まだF8が仮想時刻ＦＩＦＯ番号７に溜まっているため、ＦＩＦＯ時刻有無ビットスキャンは行わない。さらに次の出力機会があった時、F8を読出し、それにより仮想時刻ＦＩＦＯ番号７に該当する仮想時刻ＦＩＦＯ有無ビットを”0”にし、次の仮想時刻T0をビットスキャンする。
【００１５】
以上のように、実施の形態１においては、転送終了予定時刻毎にＦＩＦＯとその有無情報を設けたことにより、パケットの入力もしくは出力毎に発生する足し算と、該当するＦＩＦＯへの情報の書き込みと、出力によって仮想時刻ＦＩＦＯが空になった場合に行うビットスキャン程度の処理であり、処理時間も回路規模も従来の技術より格段に低減することができる。
【００１６】
なお、巡回する仮想時刻は無限に取れるわけではないため、量子化誤差が発生し、厳密には出力帯域と出力順序は若干ずれることがあるが、長期的には公平性は守られる。
【００１７】
実施の形態２．
以上の実施の形態１では、量子化を考えた場合、出力帯域に誤差が発生することが分かっているが、それを厳密に行う必要がある場合は、その端数を持ち越し処理する手段を備えても良い。
図５はこの発明の実施の形態２によるパケット転送制御装置を示す構成図である。図において、実施の形態１の図２における優先度情報計算手段２−１と後段の加算器２−２の間に、端数メモリ５−１と端数持越制御手段５−２を装備することで転送終了予定時刻計算部を構成し、新たにリードによって発生した新先頭であることを示す情報を追加する。
【００１８】
次に動作について説明する。
優先度情報Fi,1のビット幅と現在仮想時刻T0のビット幅において、優先度情報Fi,1のビット幅が多い場合が普通であり、現在仮想時刻T0をFi,1の上位ビットと合わせ、残ったFi,1の下位ビットがその端数に当たる。この端数は図３のキューF2の様に連続してリードによって新たに先頭になる場合は切り捨てた端数を継続することによりそのキューF2に対しては相殺されることになるのである。なお、リードによって新たに先頭となるフレームがない場合は、それが空き帯域となり、他のキューにその帯域は配分されるため、持ち越す必要は無くなる。
【００１９】
以上のように、実施の形態２においては、端数を持ち越し処理する手段を設けることにより、厳密な帯域制御が可能となる。
【００２０】
また、その仮想時刻の量子化は、最大の優先度Fi,1の値を超えない様に端数のビットを設ける構成とする。各キューには先頭が１つしか存在しないため、この構成になる。この端数のビット数の多さによってパケットの出力順序が厳密なＷＦＱと異なることになるが、ほぼ入力順となる。
【００２１】
実施の形態３．
以上の実施の形態１、実施の形態２においては、仮想時刻ＦＩＦＯはほぼ収容するキュー数分の情報を各ＦＩＦＯにて保持するメモリ量が必要であったが、実施の形態３においては、その代わりに各仮想時刻ＦＩＦＯに対するポインタ情報と、キュー情報テーブルを設けることでさらにメモリ量を削減することが可能となる。
図６はこの発明の実施の形態３によるパケット転送制御装置を示す構成図である。図において、実施の形態２の図５における仮想時刻ＦＩＦＯ２−４の代わりに、仮想時刻ＦＩＦＯ制御手段６−１と、ＩＤテーブル(メモリ)６−２、ＦＩＦＯ時刻テーブル(メモリ)６−３を設ける。
【００２２】
次に動作について説明する。
図７はＩＤテーブル(メモリ)６−２のメモリマップを示しており、図８はＦＩＦＯ時刻テーブル(メモリ)６−３のメモリマップを示している。図７と図８の状態は図３と図４の状態と同様である。
【００２３】
まず、パケットが到着し、終了予定時刻TedとキューＩＤ、パケット長、トリガパルスが入力されると、仮想時刻ＦＩＦＯ制御手段６−１はセット時刻に対する仮想時刻ＦＩＦＯ有無レジスタ２−５の有無レジスタ値が“０”であった(トリガパルスでセットされる以前の値を参照する)場合は、ＩＤテーブル(メモリ)６−２に対して、入力したキューＩＤ＝前ＩＤ＝後ＩＤを書き込み、同時にパケット長を書き込む。
一方、ＦＩＦＯ時刻テーブル(メモリ)６−３に対しては、該当する仮想時刻をアドレスとして先頭ＩＤ＝末尾ＩＤ＝入力キューＩＤを書き込む。
【００２４】
以上が仮想時刻ＦＩＦＯ内が空の場合の書き込み手順であるが、次に既に１つのＩＤが入っている場合の書き込み手順を示す。
仮想時刻７のＦＩＦＯにキューＩＤ＝４のみ書かれていたとする。その時新たにキューＩＤ＝８のパケットが到着したとすると、まず、セット時刻に対する仮想時刻ＦＩＦＯ有無レジスタ２−５の有無レジスタ値が既に登録されているため“１”であり、その場合は該当するＦＩＦＯ時刻テーブル６−３の末尾ＩＤを読出して一時保持すると同時にキューＩＤ＝８をその末尾ＩＤに書き込む。さらにその一時保持したキューＩＤ（＝４であるが）をアドレスとしてＩＤテーブルの後ＩＤ＝８を書き込みさらにキューＩＤ＝８のアドレスの前ＩＤ＝４を書き込むと同時にパケット長も書き込む。
【００２５】
次に読出し側の動作を示す。
まず一つのＩＤしか仮想時刻ＦＩＦＯに溜まっていない場合を示す。読み出しのトリガがあった場合に、現在仮想時刻T0をアドレスとしてＦＩＦＯ時刻テーブルの先頭ＩＤと末尾ＩＤを読出し、先頭ＩＤ＝末尾ＩＤである場合は、その読み出したＩＤをアドレスとしてＩＤテーブルからパケット長を読み出すと同時に現在仮想時刻T0の仮想時刻ＦＩＦＯ有無レジスタを”0”にクリアする動作となる。
【００２６】
一方、２つ以上のＩＤが仮想時刻ＦＩＦＯに溜まっている場合は、読出しのトリガがあった場合に、現在時刻T0をアドレスとしてＦＩＦＯ時刻テーブルの先頭ＩＤと末尾ＩＤを読出し、先頭ＩＤ≠末尾ＩＤであるため、読み出した前ＩＤをアドレスとしてＩＤテーブルからパケット長及び後ＩＤを読み出して保持し、その後ＩＤを前述したＦＩＦＯ時刻テーブルの先頭ＩＤに書き込む処理を行う。
【００２７】
以上のように処理することにより、仮想時刻ＦＩＦＯの深さ(＝収容するキュー数)×仮想時刻数分のメモリ領域を確保する必要が無いためメモリ量を削減することができる。
【００２８】
なお、上述のように、ＷＦＱ制御手段１−１０等の制御手段は回路として説明したが、これらはソフトウエア処理により実現しても良い。
【図面の簡単な説明】
【００２９】
【図１】この発明の実施の形態１によるパケット転送制御装置を示す構成図
【図２】この発明の実施の形態１によるパケット転送制御装置を示す構成図
【図３】この発明の実施の形態１によるパケット転送制御装置を説明するための説明図
【図４】この発明の実施の形態１によるパケット転送制御装置を説明するための説明図
【図５】この発明の実施の形態２によるパケット転送制御装置を示す構成図
【図６】この発明の実施の形態３によるパケット転送制御装置を示す構成図
【図７】この発明の実施の形態３によるパケット転送制御装置におけるテーブルを示す図
【図８】この発明の実施の形態３によるパケット転送制御装置におけるテーブルを示す図
【符号の説明】
【００３０】
１−７  メモリ
１−１０  ＷＦＱ制御手段
２−１  優先度情報計算手段
２−２  加算器
６−１  端数メモリ
６−２  端数持越制御手段
【図１】
2006005388.tif 000003
【図２】
2006005388.tif 000004
【図３】
2006005388.tif 000005
【図４】
2006005388.tif 000006
【図５】
2006005388.tif 000007
【図６】
2006005388.tif 000008
【図７】
2006005388.tif 000009
【図８】
2006005388.tif 000010