(57)【特許請求の範囲】
【請求項１】
到来するパケットを一時蓄積する複数のバッファと、この複数のバッファからのパケットの読み出しを制御する読み出し制御部とを備え、
この読み出し制御部は、パケットが互いに衝突することなく前記複数のバッファから読み出されるように競合制御する手段を含む競合制御装置において、
前記競合制御する手段は、前記複数のバッファのパケット蓄積状況にしたがって競合制御をシミュレートする手段と、このシミュレートする手段のシミュレーション結果にしたがって前記バッファにパケットの読み出し許可を与える手段とを備え、
前記シミュレートする手段は、前記複数のバッファに対応する仮想的な複数のキューと、このキューそれぞれに備えられた複数のカウンタとを備え、
この複数のカウンタは対応する前記バッファに蓄積されているパケット数を保持し、
前記複数のカウンタの保持するパケット数にしたがって競合制御をシミュレートする手段を含み、
前記許可を与える手段によりパケットの読み出し許可が与えられるバッファの順序を時系列的に記録する手段を備え、
前記記録する手段の記録数が閾値をこえるときには前記シミュレートする手段によるシミュレーションを一時休止させる手段を備え、
前記閾値はスループットと公平性に応じて設定された
ことを特徴とする競合制御装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパケットを用いた通信に利用する。本発明は大規模かつ高速なパケット交換機に利用するに適する。
【０００２】
【従来の技術】
パケット交換機では、パケットを一時蓄積するために複数のバッファが設けられている。このバッファからパケットを読み出すときには、同一出力回線に向かう複数のパケットが互いに衝突しないように、バッファ間の競合制御が必要になる。
【０００３】
従来の競合制御装置の構成を図７に示す。従来の競合制御装置の動作を図８に示す。入力されたパケットは、図７に示すように、それぞれのバッファに入力される。図７では、＃１〜＃Ｎまでバッファがあるが、これらは、例えば、各入力回線毎にバッファが備えられている場合もあるし、各クラス毎にバッファが備えられている場合もある。パケットは、一般に可変長パケットである。図７では、説明の簡単化のため、固定長単位でパケットを分割している。読み出し制御部１０は、Ｎ個のバッファから１個のバッファを選択し、その先頭のパケットを読み出す。
【０００４】
図８を用いて従来の競合制御の動作を説明する。競合制御を開始して、時間Ｔ後に、競合制御が終了し、次に読み出すバッファが選択される。競合制御の方式として、例えば、リングアービトレーションがある。ここで、どのバッファにもパケットが存在しなければ、次に読み出すバッファは選択されない。競合制御が終了しても、パケットが読み出されている場合は、パケットの読み出しが終了するまで待つ。パケットの読み出しが終了していれば、読み出しパケットがある場合には、前回選択した選択バッファからパケットを読み出すと同時に、再度競合制御を開始する。これらの動作を繰り返す。
【０００５】
【発明が解決しようとする課題】
しかしながら、パケット長Ｌが短く、その読み出し時間Ｌ／Ｃ（Ｃは読み出し回線速度）が競合制御所要時間Ｔより小さいとき、パケットが読み出されても、次に選択するバッファが見つからないため、出力回線はアイドル状態となる。したがって、スループットの低下を招く。
【０００６】
もし、従来の方式において、スループットの低下を防ぐには、最小パケット長Ｌｍｉｎ  の読み出し時間Ｌｍｉｎ  ／Ｃより、Ｔを小さくする必要があるが、高速処理のスイッチでは、インプリメントの制約があり、経済的に実現することは困難である。
【０００７】
このように、従来の競合制御装置では、Ｌ／Ｃ＜Ｔとなるパケットが到着すると、スループットが低下するという問題がある。特に、大規模化され、高速化されたパケット交換機では、このようなスループットの低下は大きな問題となる。
【０００８】
本発明は、このような背景に行われたものであって、本発明の目的は、Ｌ／Ｃ＜Ｔとなるパケットが到着しても、スループットの低下を招かない競合制御装置を提供することにある。本発明は、大規模化され、高速化されたパケット交換機に適した競合制御装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
本発明は、実際のバッファからのパケット読み出しとは別に、実際のバッファのパケット蓄積状況に基づくモデルを利用して競合制御をシミュレートすることを最も主要な特徴とする。
【００１０】
このモデルでは、実際の複数のバッファに対応する仮想的な複数のキューを想定し、実際の複数のバッファに蓄積されたパケットの識別情報をこの仮想的な複数のキューに蓄積しこの複数のキューに蓄積された当該識別情報に対して競合制御シミュレーションを実行する。
【００１１】
したがって、シミュレーションにおける競合制御は一定周期で実行される。これに対し、実際のバッファからのパケット読み出しでは、さまざまなパケット長のパケットが読み出されるので、比較的パケット長の長いパケットを読み出している間は、次の読み出し予定のバッファに送出許可を与えるまでの待ち時間が多く発生する。この待ち時間の間にもシミュレーションにおける競合制御は一定周期で実行されている。
【００１２】
このため、シミュレーションにおける競合制御では、実際のバッファに与える送出許可を実際のパケット読み出しに先行して生成することができる。このようにして生成された送出許可は、時系列的に記録して蓄積しておく。これにより、実際のバッファにおけるパケット読み出しに対する送出許可を隙間なく与えることが可能となる。
【００１３】
これにより、Ｌ／Ｃ＜Ｔとなる状況が発生しても、パケットの競合制御は先行して終了しているため、読み出し許可を速やかに与えることができる。したがって、Ｌ／Ｃ＜Ｔとなるパケットが到着しても、スループットの低下を招かない競合制御装置を実現することができる。
【００１４】
すなわち、本発明は、到来するパケットを一時蓄積する複数のバッファと、この複数のバッファからのパケットの読み出しを制御する読み出し制御部とを備え、  この読み出し制御部は、パケットが互いに衝突することなく前記複数のバッファから読み出されるように競合制御する手段を含む競合制御装置である。
【００１５】
ここで、本発明の特徴とするところは、前記競合制御する手段は、前記複数のバッファのパケット蓄積状況にしたがって競合制御をシミュレートする手段と、このシミュレートする手段のシミュレーション結果にしたがって前記バッファにパケットの読み出し許可を与える手段とを備えたところにある。
【００１６】
このとき、前記シミュレートする手段は、前記複数のバッファに対応する仮想的な複数のキューを備え、前記複数のバッファに蓄積されたパケットの識別情報をこの仮想的な複数のキューにそれぞれ蓄積しこの複数のキューに蓄積された当該識別情報に対して競合制御シミュレーションを実行する手段を含むことが望ましい。
【００１７】
前記許可を与える手段によりパケットの読み出し許可が与えられるバッファの順序を時系列的に記録する手段を備えることが望ましい。
【００１８】
さらに、この記録する手段の記録数が閾値をこえるときには前記シミュレートする手段によるシミュレーションを一時休止させる手段を備えることが望ましい。
【００１９】
例えば、頻繁にパケットが到着するバッファａと、そうでないバッファｂがある場合に、頻繁にパケットが到着するバッファａについては、バッファｂにパケットが到着しない期間中に、前記シミュレートする手段により送出許可が次々に生成されることになる。
【００２０】
このときに、頻繁にパケットが到着しないバッファｂにパケットが到着した場合には、バッファａに次々に与えられる送出許可によりバッファａからおおかたのパケットの読み出しが終了した後に、やっとバッファｂに送出許可が与えられることになり、バッファｂの待ち時間を増大させる結果となる。このようなスループットの不公平性を是正するために、バッファａに対する送出許可がある程度蓄積されたときには、一時的にシミュレーションを休止させる。この休止期間中にバッファｂにパケットが到着したならば、シミュレーションが再開されたときには、バッファｂに対する送出許可がバッファａと対等に与えられることになり、スループットの不公平性が是正される。
【００２１】
前記シミュレートする手段は、例えば、リングアービトレーションにより競合制御をシミュレートする手段を含むことができる。
【００２２】
【発明の実施の形態】
（参考例）
本発明の参考例の競合制御装置の構成を図１を参照して説明する。図１は本発明の参考例の競合制御装置の構成を示す図である。
【００２３】
本参考例は、図１に示すように、到来するパケットを一時蓄積する複数のバッファ＃１〜＃Ｎと、この複数のバッファ＃１〜＃Ｎからのパケットの読み出しを制御する読み出し制御部１０とを備え、この読み出し制御部１０は、パケットが互いに衝突することなく複数のバッファ＃１〜＃Ｎから読み出されるように競合制御する競合制御装置である。
【００２４】
ここで、本参考例の特徴とするところは、複数のバッファ＃１〜＃Ｎのパケット蓄積状況にしたがって競合制御をシミュレートする手段であるバーチャルキュー部２０を備え、このバーチャルキュー部２０のシミュレーション結果にしたがってバッファ＃１〜＃Ｎにパケットの読み出し許可を与えるところにある。
【００２５】
バーチャルキュー部２０は、複数のバッファ＃１〜＃Ｎに対応する仮想的な複数のバーチャルキュー＃１〜＃Ｎを備え、複数のバッファ＃１〜＃Ｎに蓄積されたパケットの識別情報としてのリクエスト情報をこの仮想的な複数のバーチャルキュー＃１〜＃Ｎにそれぞれ蓄積しこの複数のバーチャルキュー＃１〜＃Ｎに蓄積された当該リクエスト情報に対して競合制御シミュレーションを実行する。
【００２６】
また、読み出し制御部１０によりパケットの読み出し許可が与えられるバッファの順序を時系列的に記録する手段である読み出し情報キュー２２を備える。
【００２７】
バーチャルキュー部２０は、リングアービトレーションにより競合制御をシミュレートする。
【００２８】
次に、本発明の参考例の動作を図１ないし図３を参照して説明する。図２は本発明の参考例のバーチャルキュー部の動作を示すフローチャートである。図３は本発明の参考例のバッファ部の動作を示すフローチャートである。
【００２９】
図１は、複数の入力回線に転送されてくるパケットがそれぞれ回線毎にバッファ＃１〜＃Ｎに入力される構成を示している。パケットを固定長単位で分割しているのは説明の簡単化のためである。パケットがあるバッファ＃ｉ（ｉは１〜Ｎのいずれか）に入力されると、それに相当するバーチャルキュー＃ｉに、リクエスト要求のためのリクエスト情報が入力される。バーチャルキュー＃ｉは、リクエスト個数をカウントするカウンタ（図示せず）を備えている。
【００３０】
図２に示すように、バーチャルキュースケジューラ２１は、バーチャルキュー＃１〜＃Ｎに対して競合制御シミュレーションを行う。競合制御シミュレーションの所要時間Ｔは、Ｌｍｉｎ  ／Ｃに近く設定される。競合制御シミュレーションにより読み出しバッファが選択されると、その送出許可は、読み出し情報キュー（ＦＩＦＯ）２２に入力される。ここでは、競合制御シミュレーションにはリングアービトレーションを用いる。
【００３１】
すなわち、バーチャルキュー＃１〜＃Ｎにそれぞれ備えられたカウンタはバッファ＃１〜＃Ｎにそれぞれ蓄積されているパケット数を示す。リングアービタがバーチャルキュー＃１〜＃Ｎを巡回することにより、カウンタが“０”ではないバーチャルキューに順次送出許可を与える。
【００３２】
バーチャルキュー部２０の動作は、バッファ部３０のバッファ＃１〜＃Ｎにおけるパケットの読み出しのタイミングとは独立に行われている。したがって、Ｌ／Ｃ＞Ｔなるパケットを読み出した場合には、競合制御がパケット読み出しよりも早く終了するので、次の読み出しバッファをサーチする。
【００３３】
図３にあるように、バッファ部３０の読み出し制御部１０は、パケットの読み出しが終了すると、バーチャルキュー部２０の読み出し情報キュー２２に情報があれば、読み出し情報キューの先頭の情報（選択すべきバッファ）をＦＩＦＯで読み出し、当該バッファの先頭パケットをバッファ部３０から読み出す。
【００３４】
この動作によって、Ｌｍｉｎ  ／Ｃ＜Ｔである場合でも、Ｌｍｉｎ  ／Ｃ＜Ｔなるパケットの場合に先行して競合制御を行うことができるので、スループットの低下を防ぐことができる。
【００３５】
（実施例）
本発明実施例を図４を参照して説明する。図４は本発明実施例の競合制御装置の構成を示す図である。
【００３６】
本発明実施例の競合制御装置は、図１に示した本発明の参考例の競合制御装置に加え、図４に示すように、読み出し情報キュー２２のキュー長にしたがってバーチャルキュースケジューラ２１によるシミュレーションを一時休止させるためのキュー長閾値を設けたところが異なる。
【００３７】
次に、本発明実施例の競合制御装置の動作を図４および図５を参照して説明する。図５は本発明実施例のバーチャルキュー部２０の動作を示すフローチャートである。バッファ部３０の動作は、本発明の参考例と同様である。
【００３８】
本発明実施例が本発明の参考例と異なるところは、バーチャルキュー部２０の読み出し情報キュー２２に閾値Ｑを設定しておくところにある。図５に示したように、読み出し情報キュー２２のキュー長がＱ以下であれば、本発明第一実施例と同じであるが、キュー長がＱよりも大きくなると、バーチャルキュースケジューラ２１にバックプレッシャ信号が転送され、競合制御シミュレーションの開始がストップされる。キュー長がＱ以下ならば、競合制御シミュレーションが開始される。
【００３９】
この動作によって、Ｑを小さく設定すれば、各バッファ＃１〜＃Ｎのスループットの不公平性を改善することができる。その原理は、既に説明したように、頻繁にパケットが到着するバッファａと、そうでないバッファｂがある場合に、頻繁にパケットが到着するバッファａについては、バッファｂにパケットが到着しない期間中に、バーチャルキュースケジューラ２１により送出許可が次々に生成されることになる。
【００４０】
このときに、頻繁にパケットが到着しないバッファｂにパケットが到着した場合には、バッファａに次々に与えられる送出許可によりバッファａからおおかたのパケットの読み出しが終了した後に、やっとバッファｂに送出許可が与えられることになり、バッファｂの待ち時間を増大させる結果となる。このようなスループットの不公平性を是正するために、バッファａに対する送出許可がある程度蓄積されたときには、一時的にシミュレーションを休止させる。この休止期間中にバッファｂにパケットが到着したならば、シミュレーションが再開されたときには、バッファｂに対する送出許可がバッファａと対等に与えられることになり、スループットの不公平性が是正される。ただし、小さ過ぎると、従来の方式に近づいてしまうので、適当なＱを選ぶ必要がある。
【００４１】
（実施例まとめ）
図６に、従来の競合制御装置と本発明の競合制御装置のスループットを比較した。図６は横軸に平均パケット長をとり、縦軸にスループットをとる。パケット長は、指数分布にしたがうと仮定し、平均パケット長Ｌは、競合制御時間に対して規格化した値としている。Ｑは無限大と仮定した。本発明では、競合制御時間が緩和されても、バーチャルキューを用いてあらかじめパケットを選択しているので、スループットの低下を防ぐことができる。
【００４２】
【発明の効果】
以上説明したように、本発明によれば、Ｌ／Ｃ＜Ｔとなるパケットが到着しても、スループットの低下を招かない競合制御装置を実現することができる。本発明によれば、大規模化され、高速化されたパケット交換機に適する競合制御装置を実現することができる。
【図面の簡単な説明】
【図１】本発明参考例の競合制御装置の構成を示す図。
【図２】本発明参考例のバーチャルキュー部の動作を示すフローチャート。
【図３】本発明参考例のバッファ部の動作を示すフローチャート。
【図４】本発明実施例の競合制御装置の構成を示す図。
【図５】本発明実施例のバーチャルキュー部の動作を示すフローチャート。
【図６】従来の競合制御装置と本発明の競合制御装置のスループットを比較する図。
【図７】従来の競合制御装置を説明するための図。
【図８】従来の競合制御装置の動作を示すフローチャート。
【符号の説明】
１０ 読み出し制御部
２０ バーチャルキュー部
２１ バーチャルキュースケジューラ
２２ 読み出し情報キュー
３０ バッファ部
【図１】
0003592586.tif 000002
【図２】
0003592586.tif 000003
【図３】
0003592586.tif 000004
【図４】
0003592586.tif 000005
【図５】
0003592586.tif 000006
【図６】
0003592586.tif 000007
【図７】
0003592586.tif 000008
【図８】
0003592586.tif 000009