パケット転送装置およびパケット転送方法
【課題】フローの数の多少にかかわらずMax Tokenの増大を抑制し、かつトークン値の廃棄の発生を抑制する。
【解決手段】パケット転送装置100は、トークンバケット方式で記憶部140−1〜140−nのトークン値の加減算を行うとともに、トークン値がMax Tokenを超過したら超過した分のトークン値を廃棄するトークン演算部160を有する。また、パケット転送装置100は、パケットバッファ120−1〜120−nのパケットの格納の有無およびトークン値の廃棄の有無に応じて、フロー♯1〜♯nのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部200を有する。また、パケット転送装置100は、優先制御信号生成部200で設定されたフロー♯1〜♯nのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部220を有する。
【解決手段】パケット転送装置100は、トークンバケット方式で記憶部140−1〜140−nのトークン値の加減算を行うとともに、トークン値がMax Tokenを超過したら超過した分のトークン値を廃棄するトークン演算部160を有する。また、パケット転送装置100は、パケットバッファ120−1〜120−nのパケットの格納の有無およびトークン値の廃棄の有無に応じて、フロー♯1〜♯nのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部200を有する。また、パケット転送装置100は、優先制御信号生成部200で設定されたフロー♯1〜♯nのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部220を有する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、パケット転送装置およびパケット転送方法に関する。
【背景技術】
【0002】
従来、パケット通信の技術分野においては、パケットが伝送される複数のフローの合流地点にパケット転送装置を設けることが知られている。パケット転送装置は、複数のフローを流れるパケットの出力順序を制御しながら出力回路に転送することにより、出力回路のトラフィックを制御する。
【0003】
また、パケット転送装置のパケット転送技術としてトークンバケット方式が知られている。トークンバケット方式は、複数のフローを流れるパケットをパケットバッファにいったん格納し、パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を用いてパケットを出力する。
【0004】
図8は、トークンバケット方式を説明するための図である。図8において横軸は時間を示し、縦軸は記憶部に記憶されているトークン値を示す。トークンバケット方式では、複数のフローに対応してトークン値が記憶される記憶部を有する。トークンバケット方式では、記憶部に記憶されたトークン値に、あらかじめ設定された周期(以下、「トークン追加周期」という。)で所定のトークン値(以下、「追加トークン値」という。)を加算する(図8の(a)参照)。また、トークンバケット方式では、記憶部に記憶されているトークン値が正または出力パケット長以上である場合にパケットの出力許可を行う。また、トークンバケット方式では、パケットバッファからパケットが出力されたら、パケットが出力されたフローに対応する記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する(図8の(b)参照)。なお図8の例は、トークン値が正の場合にパケットの出力許可を行う例である。また、トークンバケット方式では、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値(以下、「Max Token」という。)を超過したら、超過した分のトークン値を廃棄する(図8の(c)参照)。
【0005】
トークンバケット方式によって導かれるシェーピングレート(Shaping Rate:以下、「Sh_R」という。) は、トークン追加周期と、追加トークン値とによって以下のように表される。
Sh_R [bps(bits per second)]=追加トークン値[byte]×8/トークン追加周期[s(second)]
なお、Sh_Rとは、フローごとのパケットの出力帯域である。例えば、追加トークン値が40,000[byte]、トークン追加周期が32[us](=32×10^−6 [s])の場合、Sh_Rは10G[bps](=40,000 [byte]×8/32×10^−6[s])となる。
【0006】
また、パケット転送装置では、トークンバケット方式とラウンドロビン(Round Robin:以下、「RR」という。)方式との組み合わせにより、複数のフローからのパケットの出力順序を制御することが知られている。RR方式とは、複数のフローを順番に選択しながら、選択されたフローのパケットバッファに格納されたパケットを順次出力する方式である。
【0007】
図9は、トークンバケット方式とRR方式との組み合わせを用いたパケット出力を説明するための図である。フロー♯1〜フロー♯nを流れるパケット♯1〜パケット♯nは、パケットバッファ♯1〜パケットバッファ♯nにそれぞれ格納される。なおnは2以上の自然数である。ここで、フロー♯1〜フロー♯nのうち、記憶部に記憶されたトークン値が正であり、かつパケットバッファにパケットが格納されているフローが順次選択され、選択されたフローのパケットバッファに格納されたパケットが出力回路へ出力される。なお、フロー♯1〜フロー♯nそれぞれのSh_Rの総和ΣSh_Rは、出力回線のワイヤレート以下である。
【0008】
なお、複数のフローのパケットの出力帯域を管理する方法としては、WRR(Weighted Round Robin)という技術も知られている。WRRは、トークンの代わりに重み(Weight)をフローごとに与える。また、WRRでは、あるフローが読み出し権利を得たら重みに応じた量を読み出した後、次のフローに読み出し権利を渡す制御を行う。例えばパケットの出力帯域=10G[bps]であり、重み=1のフローが1本のみである場合、そのフローは10G[bps]の性能が得られる。また、パケットの出力帯域=10G[bps]であり、重み=1のフローがもう1本存在すれば、各フローはそれぞれ5G[bps]の性能が得られる。ここで、一方のフローにパケットが入力されない場合、他方のフローが10G[bps]の出力帯域を占有することになるが、出力されたパケットを受信する装置が5G[bps]の受信能力しか無ければパケットは廃棄される。そこでもしパケットの出力帯域の上限設定が必要な場合、各フローにシェーパの設定を行う。
【0009】
ところで、従来技術では、トークン値の廃棄の発生を抑制する目的で、パケットバッファにパケットが格納されているフローのMax Tokenを、パケットバッファにパケットが格納されていないフローのMax Tokenより大きく設定することが知られている。例えば従来技術は、パケットバッファにパケットが格納されていないフローのMax Token=追加トークン値×1とし、パケットバッファにパケットが格納されているフローのMax Token=追加トークン値×nとする。ここでnは、トークン値が廃棄されない程度に大きく設定する値である。
【先行技術文献】
【特許文献】
【0010】
【特許文献1】特開2007−181085号公報
【発明の概要】
【発明が解決しようとする課題】
【0011】
しかしながら、従来技術は、フローの数にかかわらずMax Tokenの増大を抑制することについては考慮されていない。
【0012】
すなわち、従来技術によれば、フロー数の増大にしたがって記憶部に記憶されているトークン値の最大値が大きくなる場合がある。以下この点について説明する。図10,図11は、従来技術のパケット転送装置のトークン値の遷移モデルを示す図である。図10のトークン値の遷移モデルは、3フローを収容したパケット転送装置の一例である。また、図11のトークン値の遷移モデルは、全体の帯域は図10の場合と変えずに2フロー増加したパケット転送装置の一例である。図10と図11において、各フローのパケットバッファにパケットが格納されていない期間をαで示し、パケットバッファにパケットが格納されている期間をβで示す。また、図10と図11において、複数のトークン追加周期を時間軸に沿って周期(A)〜周期(F)という。
【0013】
図10の周期(A)ではフロー♯1とフロー♯2のパケットバッファにパケットが格納されていないので、フロー♯5のパケットバッファからパケットが出力される(図10の(a)参照)。続いて周期(B)に入ると各フローの記憶部にトークン値が加算される(図10の(b)参照)。なおフロー♯1およびフロー♯2のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期(B)ではフロー♯1、フロー♯2およびフロー♯5のパケットバッファにパケットが格納されているから、フロー♯1、フロー♯2、フロー♯5の順にパケットが出力される(図10の(c)参照)。また、周期(B)においてパケットを出力した後、フロー♯1とフロー♯2のトークン値は負になるのに対して、フロー♯5のトークン値は正であるから、フロー♯5からパケットが出力される(図10の(d)参照)。続いて周期(C)に入ると各フローの記憶部にトークン値が加算される(図10の(e)参照)。周期(C)ではフロー♯1およびフロー♯2のトークン値が「0」つまり正ではないから、フロー♯1およびフロー♯2からはパケットが出力されず、フロー♯5からパケットが出力される(図10の(f)参照)。図10の周期(D)以降の処理は図10の周期(B)および周期(C)と同様であるから、説明を省略する。
【0014】
次に、図11の周期(A)は図10の場合と同様であるから説明を省略する。これに対して、図11の周期(B)では、フロー♯3とフロー♯4が追加されてフロー数が多くなっているから、フロー♯1〜フロー♯4の順にパケットが出力され(図11の(a)参照)、フロー♯5からはパケットが出力されない。この状態で周期(C)に入ると各フローの記憶部にトークン値が加算される(図11の(b)参照)。その結果、図10のフロー♯5と図11のフロー♯5を比較すると、フロー数が多い図10のフロー♯5の記憶部に記憶されるトークン値の最大値が、図10の場合と比べて大きくなる。なお、図11の周期(C)の以後の処理は図10の周期(B)および周期(C)と同様であるから、説明を省略する。
【0015】
このように、RR方式を用いてパケットを出力するフローを順次選択する場合、フローの数が多くなるにしたがって、あるフローのパケットを出力する処理の待ち時間が長くなる。待ち時間の間はトークン追加周期がくるたびに記憶部にトークン値が加算される。一方、待ち時間の間はパケットが出力されないから、記憶部に記憶されているトークン値の減算は行われない。したがって、フローの数が多くなると、記憶部に記憶されるトークン値の最大値は大きくなる。トークン値の最大値が大きくなると、トークン値がMax Tokenを超えてトークン値の廃棄が発生するおそれが増大する。パケットバッファにパケットが格納されているフローに対してトークン値の廃棄が頻繁に発生すると、パケットの出力帯域の劣化につながるので好ましくない。一方、トークン値の廃棄を抑制するためにMax Tokenを大きく設定することも考えられるが、これは回路規模の増大を招くので好ましくない。
【0016】
開示の技術は、上記に鑑みてなされたものであって、フローの数にかかわらずMax Tokenの増大を抑制し、かつトークン値の廃棄の発生を抑制することができるパケット転送装置およびパケット転送方法を提供することを目的とする。
【課題を解決するための手段】
【0017】
本願の開示するパケット転送装置は、一つの態様において、パケットを伝送する複数のフローを流れるパケットをそれぞれ複数のフローに対応して格納するパケットバッファを有する。また、パケット転送装置は、パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を複数のフローに対応して記憶する記憶部を有する。また、パケット転送装置は、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算するトークン演算部を有する。トークン演算部は、パケットバッファからパケットが出力されたフローに対応して記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する。また、トークン演算部は、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する。また、パケット転送装置は、複数のフローごとにパケットバッファにパケットが格納されているか否かを検出するパケット監視部を有する。また、パケット転送装置は、パケット監視部で検出されたパケットの格納の有無およびトークン演算部によるトークン値の廃棄の有無に応じて、複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部を有する。また、パケット転送装置は、優先制御信号生成部で設定された複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部を有する。
【発明の効果】
【0018】
本願の開示するパケット転送装置の一つの態様によれば、フローの数の多少にかかわらずMax Tokenの増大を抑制し、かつトークン値の廃棄の発生を抑制することができる。
【図面の簡単な説明】
【0019】
【図1】図1は、実施例にかかるパケット転送装置の全体構成を示す図である。
【図2】図2は、優先制御信号生成部の詳細構成を示す図である。
【図3】図3は、出力フロー選択部の詳細構成を示す図である。
【図4】図4は、スキップ判定回路の動作を説明するための図である。
【図5】図5は、優先制御信号生成部の動作を説明するための図である。
【図6】図6は、実施例にかかるパケット転送装置のトークン値の遷移モデルを示す図である。
【図7A】図7Aは、実施例にかかるパケット転送装置のトークン値の遷移モデルを示す図である。
【図7B】図7Bは、実施例にかかるパケット転送装置のトークン値の遷移モデルを示す図である。
【図8】図8は、トークンバケット方式を説明するための図である。
【図9】図9は、トークンバケット方式とRR方式との組み合わせを用いたパケット出力を説明するための図である。
【図10】図10は、従来技術のパケット転送装置のトークン値の遷移モデルを示す図である。
【図11】図11は、従来技術のパケット転送装置のトークン値の遷移モデルを示す図である。
【発明を実施するための形態】
【0020】
以下に、本願の開示するパケット転送装置およびパケット転送方法の実施例を図面に基づいて詳細に説明する。なお、この実施例により開示技術が限定されるものではない。
【実施例】
【0021】
図1は、実施例にかかるパケット転送装置の全体構成を示す図である。本実施例のパケット転送装置100は、パケットバッファ120と、記憶部140と、トークン演算部160と、パケット監視部180と、優先制御信号生成部200と、出力フロー選択部220とを有する。
【0022】
パケットバッファ120は、パケットバッファ120−1〜パケットバッファ120−nを有する。パケットバッファ120−1〜パケットバッファ120−nはそれぞれ、パケットを伝送するフロー♯1〜フロー♯nに対応して設けられる。パケットバッファ120−1〜パケットバッファ120−nには、フロー♯1〜フロー♯nを流れるパケットがそれぞれ格納される。
【0023】
記憶部140は、記憶部140−1〜記憶部140−nを有する。記憶部140−1〜記憶部140−nはそれぞれ、フロー♯1〜フロー♯nに対応して設けられる。記憶部140−1〜記憶部140−nには、それぞれトークン値が記憶される。トークン値は、パケットバッファ120−1〜パケットバッファ120−nに格納されたパケットの出力を許可するか否かを判別するのに用いる情報である。
【0024】
トークン演算部160は、トークンバケット方式にしたがって、記憶部140−1〜記憶部140−nに記憶されているトークン値に、トークン追加周期で追加トークン値を加算する。また、トークン演算部160は、記憶部140−1〜記憶部140−nのうちパケットバッファからパケットが出力されたフローに対応する記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する。さらに、トークン演算部160は、記憶部140−1〜記憶部140−nごとに、記憶されたトークン値が正か負かを判別する。記憶部140−1〜記憶部140−nごとのトークン値の正負の情報は、トークン情報として、優先制御信号生成部200と出力フロー選択部220に出力される。また、トークン演算部160は、フロー♯1〜フロー♯nに対応して記憶部140−1〜記憶部140−nに記憶されたトークン値があらかじめ設定されたMax Tokenを超過したら超過した分のトークン値を廃棄する。記憶部140−1〜記憶部140−nごとのトークン値の廃棄の有無の情報は、トークン廃棄情報として、優先制御信号生成部200に出力される。
【0025】
パケット監視部180は、フロー♯1〜フロー♯nからパケットが入力されたら、パケットバッファ120−1〜パケットバッファ120−nのうち、パケットが入力されたフローに対応するパケットバッファにパケットを格納する。また、パケット監視部180は、パケットが格納されたパケットバッファの総パケット数の加算を行う。また、パケット監視部180は、パケットバッファ120−1〜パケットバッファ120−nからパケットが出力されたら、パケットが出力されたパケットバッファの総パケット数の減算を行う。さらに、パケット監視部180は、パケットバッファ120−1〜パケットバッファ120−nそれぞれの総パケット数を監視することにより、パケットバッファにパケットが格納されているか否かを検出する。パケットバッファ120−1〜パケットバッファ120−nごとのパケットが格納されているか否かの情報は、パケット有無情報として、優先制御信号生成部200と出力フロー選択部220に出力される。
【0026】
優先制御信号生成部200には、トークン演算部160から出力されたトークン廃棄情報およびトークン情報と、パケット監視部180から出力されたパケット有無情報と、出力フロー選択部220から出力されたスキップ情報とが入力される。優先制御信号生成部200は、入力された各情報に基づいて、フロー♯1〜フロー♯nのパケット出力の優先度を高優先度または低優先度に設定する。フロー♯1〜フロー♯nごとのパケット出力の優先度は、優先情報として出力フロー選択部220に出力される。優先制御信号生成部200の詳細は後述する。
【0027】
出力フロー選択部220は、優先制御信号生成部200から出力されたフロー♯1〜フロー♯nごとのパケット出力の優先情報に応じて、パケットを出力するフローを順次選択する。より具体的には、出力フロー選択部220は、フロー♯1〜フロー♯nを高優先度のクラスと低優先度のクラスに分け、高優先度のクラスのフローから優先的にパケットを出力し、高優先度のフローがなくなったら、低優先度のフローからパケットを出力する。出力フロー選択部220は、パケットバッファにパケットが格納されていないフローまたは記憶部のトークン値が負のフローをスキップしながらパケットを出力するフローを順次選択する。フロー♯1〜フロー♯nごとのスキップの発生の有無の情報は、スキップ情報として、優先制御信号生成部200に出力される。また、フロー♯1〜フロー♯nのうち、どのフローからパケットが出力されたかという情報は、出力フロー情報として、パケットバッファ120、トークン演算部160、およびパケット監視部180に出力される。
【0028】
次に、優先制御信号生成部200の詳細を説明する。図2は、優先制御信号生成部200の詳細構成を示す図である。優先制御信号生成部200は、選択回路202−1〜選択回路202−nと、and回路204a−1〜and回路204a−nと、and回路204b−1〜and回路204b−nとを有する。選択回路202−1〜選択回路202−nはそれぞれ、フロー♯1〜フロー♯nに対応して設けられる。and回路204a−1〜and回路204a−nはそれぞれ、フロー♯1〜フロー♯nに対応して設けられる。and回路204b−1〜and回路204b−nはそれぞれ、フロー♯1〜フロー♯nに対応して設けられる。
【0029】
and回路204a−1〜and回路204a−nにはそれぞれ、フロー♯1〜フロー♯nのトークン廃棄情報のうち、対応するフローのトークン廃棄情報が入力される。トークン廃棄情報は、トークン値の廃棄が発生した場合には「1」、トークン値の廃棄が発生しなかった場合には「0」という論理値でand回路204a−1〜and回路204a−nに入力される。
【0030】
また、and回路204a−1〜and回路204a−nにはそれぞれ、フロー♯1〜フロー♯nのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。つまり、パケット有無情報は、フローのパケットが存在した場合には「1」、フローのパケットが存在しない場合には「0」という論理値でand回路204a−1〜and回路204a−nに入力される。
【0031】
また、and回路204a−1〜and回路204a−nはそれぞれ、入力されたトークン廃棄情報とパケット有無情報に応じた論理値を、対応する選択回路202−1〜選択回路202−nに出力する。具体的には、and回路204a−1〜and回路204a−nはそれぞれ、入力されたトークン廃棄情報とパケット有無情報がともに「1」の場合には「1」を、対応する選択回路202−1〜選択回路202−nに出力する。また、and回路204a−1〜and回路204a−nはそれぞれ、入力されたトークン廃棄情報とパケット有無情報の少なくとも一方が「0」の場合には「0」を、対応する選択回路202−1〜選択回路202−nに出力する。
【0032】
一方、and回路204b−1〜and回路204b−nにはそれぞれ、フロー♯1〜フロー♯nのトークン情報のうち、対応するフローのトークン情報が入力される。トークン情報は、記憶部のトークン値が正の場合は「1」、記憶部のトークン値が負の場合は「0」という論理値でand回路204b−1〜and回路204b−nに入力される。
【0033】
また、and回路204b−1〜and回路204b−nにはそれぞれ、フロー♯1〜フロー♯nのスキップ情報のうち、対応するフローのスキップ情報が入力される。スキップ情報は、フローのパケット出力処理がスキップされた場合には「1」、フローのパケット出力処理がスキップされなかった場合には「0」という論理値でand回路204b−1〜and回路204b−nに入力される。さらに、and回路204b−1〜and回路204b−nにはそれぞれ、フロー♯1〜フロー♯nのパケット有無情報のうち、対応するフローのパケット有無情報が論理反転されて入力される。つまり、フローのパケットが存在しない場合には「1」、フローのパケットが存在する場合には「0」という論理値でand回路204b−1〜and回路204b−nに入力される。
【0034】
and回路204b−1〜and回路204b−nはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報に応じた論理値を、対応する選択回路202−1〜選択回路202−nに出力する。具体的には、and回路204b−1〜and回路204b−nはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報がともに「1」の場合には「1」を、対応する選択回路202−1〜選択回路202−nに出力する。また、and回路204b−1〜and回路204b−nはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報のいずれかが「0」の場合には「0」を、対応する選択回路202−1〜選択回路202−nに出力する。
【0035】
選択回路202−1〜選択回路202−nはそれぞれ、対応するand回路204a−1〜and回路204a−nおよびand回路204b−1〜and回路204b−nから入力された論理値に応じた論理値を優先情報として出力する。例えば選択回路202−1は、and回路204a−1から出力された論理値が「1」で、and回路204b−1から出力された論理値が「0」の場合は、フロー♯1の優先度を高優先度に設定する論理値「1」を優先情報として出力する。一方、選択回路202−1は、and回路204a−1から出力された論理値が「0」で、and回路204b−1から出力された論理値が「1」の場合は、フロー♯1の優先度を低優先度に設定する論理値「0」を優先情報として出力する。選択回路202−2〜選択回路202−nについても同様である。
【0036】
次に、出力フロー選択部220の詳細を説明する。図3は、出力フロー選択部220の詳細構成を示す図である。出力フロー選択部220は、ストリクトプライオリティ(Strict Priority:以下「SP」という。)回路222と、RR回路224aと、RR回路224bを有する。また、出力フロー選択部220は、出力用and回路226a−1〜出力用and回路226a−nと、出力用and回路226b−1〜出力用and回路226b−nとを有する。また、出力フロー選択部220は、出力フロー保持回路228と、スキップ判定回路230−1〜スキップ判定回路230−nを有する。
【0037】
出力用and回路226a−1〜出力用and回路226a−nにはそれぞれ、フロー♯1〜フロー♯nの優先情報のうち、対応するフローの優先情報が入力される。優先情報は、フローの優先度が高優先度の場合には「1」、フローの優先度が低優先度の場合には「0」の論理値で出力用and回路226a−1〜出力用and回路226a−nに入力される。
【0038】
また、出力用and回路226a−1〜出力用and回路226a−nにはそれぞれ、フロー♯1〜フロー♯nのトークン情報のうち、対応するフローのトークン情報が入力される。また、出力用and回路226a−1〜出力用and回路226a−nにはそれぞれ、フロー♯1〜フロー♯nのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。パケット有無情報は、パケットバッファにパケットが格納されている場合には「1」、パケットバッファにパケットが格納されていない場合には「0」の論理値で出力用and回路226a−1〜出力用and回路226a−nに入力される。
【0039】
出力用and回路226a−1〜出力用and回路226a−nはそれぞれ、入力された優先情報とトークン情報とパケット有無情報に応じた論理値を、RR回路224aに出力する。具体的には、出力用and回路226a−1〜出力用and回路226a−nはそれぞれ、入力された優先情報とトークン情報とパケット有無情報の全ての論理値が「1」の場合には論理値「1」を出力する。また、出力用and回路226a−1〜出力用and回路226a−nはそれぞれ、入力された優先情報とトークン情報とパケット有無情報の少なくとも1つの論理値が「0」の場合には論理値「0」を出力する。
【0040】
一方、出力用and回路226b−1〜出力用and回路226b−nにはそれぞれ、フロー♯1〜フロー♯nのトークン情報のうち、対応するフローのトークン情報が入力される。また、出力用and回路226b−1〜出力用and回路226b−nにはそれぞれ、フロー♯1〜フロー♯nのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。
【0041】
出力用and回路226b−1〜出力用and回路226b−nはそれぞれ、入力されたトークン情報とパケット有無情報に応じた論理値を、RR回路224bに出力する。具体的には、出力用and回路226b−1〜出力用and回路226b−nはそれぞれ、入力されたトークン情報とパケット有無情報の論理値がともに「1」の場合には論理値「1」を出力する。また、出力用and回路226b−1〜出力用and回路226b−nはそれぞれ、入力されたトークン情報とパケット有無情報の少なくとも一方の論理値が「0」の場合には論理値「0」を出力する。
【0042】
RR回路224aは、フロー♯1〜フロー♯nのうち、出力用and回路226a−1〜出力用and回路226a−nからの出力論理値が「1」である出力用and回路に対応するフローを順次選択してSP回路222に出力する。RR回路224bは、フロー♯1〜フロー♯nのうち、出力用and回路226b−1〜出力用and回路226b−nからの出力論理値が「1」である出力用and回路に対応するフローを順次選択してSP回路222に出力する。
【0043】
SP回路222は、RR回路224aからの出力がある場合、RR回路224aからの出力を出力フロー情報として出力する。つまり、SP回路222は、高優先度に設定されたフローがあるときには、高優先度のフローからのパケット出力を優先する。一方、SP回路222は、RR回路224aからの出力がない場合、RR回路224bからの出力を出力フロー情報として出力する。このように、出力フロー選択部220は、フロー♯1〜フロー♯nを高優先度のクラスと低優先度のクラスに分け、高優先度のクラスのフローから優先的にパケットを出力し、高優先度のフローがなくなったら、低優先度のフローからパケットを出力する。
【0044】
SP回路222から出力された出力フロー情報は、出力フロー選択部220の外部へ出力されるとともに、出力フロー保持回路228と、スキップ判定回路230−1〜スキップ判定回路230−nのそれぞれに入力される。出力フロー保持回路228は、SP回路222から出力された出力フロー情報を保持するとともに、前回出力フロー情報をスキップ判定回路230−1〜スキップ判定回路230−nのそれぞれに入力する。スキップ判定回路230−1〜スキップ判定回路230−nはそれぞれ、出力フロー情報と前回出力フロー情報に基づいて、フロー♯1〜フロー♯nのパケット出力の処理がスキップされたか否かを判定する。前回出力フロー情報とは、最新のパケット出力の1つ前にパケットバッファからパケットが出力されたフローの情報である。
【0045】
図4は、スキップ判定回路の動作を説明するための図である。図4において、自フローとは、フロー♯1〜フロー♯nのそれぞれのフローを指す。スキップ判定回路230−1〜スキップ判定回路230−nは、フロー♯1〜フロー♯nのそれぞれに対して以下のフローチャートの処理を行う。また、図4の例では、フロー♯1〜フロー♯nにはそれぞれ、昇順のフローID(Identification)が付されているものとする。
【0046】
まず、スキップ判定回路230−1〜スキップ判定回路230−nは、フロー♯1〜フロー♯nのうち、パケットバッファからパケットが出力された最新のフローのID(以下、「出力フローID」という。)=自フローIDであるか確認する(ステップS1)。ステップS1でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローにスキップ有りの判定がなされていたら、そのスキップ判定を解除する(ステップS2)。
【0047】
一方、ステップS1でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、出力フローID>自フローIDであるか確認する(ステップS3)。ステップS3でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、フロー♯1〜フロー♯nのうち、前回出力フローID<自フローIDであるか確認する(ステップS4)。前回出力フローIDとは、出力フローIDの1つ前にパケットバッファからパケットが出力されたフローのIDである。ステップS4でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローがスキップされたと判定する(ステップS5)。
【0048】
一方、S4でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、前回出力フローID>出力フローIDであるか確認する(ステップS6)。ステップS6でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローがスキップされたと判定する(ステップS7)。一方、ステップS6でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローはスキップ判定が解除されているかまたはスキップされたと判定されているかの現在の状態(以下、「現在スキップ判定状態」という。)を保持する(ステップS8)。
【0049】
ステップS3でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、前回出力フローID≧自フローIDであるか確認する(ステップS9)。ステップS9でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、現在スキップ判定状態を保持する(ステップS10)。
【0050】
一方、ステップS9でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、前回出力フローID<出力フローIDであるか確認する(ステップS11)。ステップS11でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、現在スキップ判定状態を保持する(ステップS12)。一方、ステップS11でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローがスキップされたと判定する(ステップS13)。
【0051】
スキップ判定回路230−1〜スキップ判定回路230−nから出力されたフロー♯1〜フロー♯nの現在スキップ判定状態は、スキップ情報として優先制御信号生成部200に入力される。図5は、優先制御信号生成部200の動作を説明するための図である。優先制御信号生成部200は、以下のフローチャートの処理をフロー♯1〜フロー♯nのそれぞれに対して行う。
【0052】
まず、優先制御信号生成部200は、フロー♯1〜フロー♯nのスキップ情報に基づいて、フロー♯1〜フロー♯nのスキップの発生が有か否かを判定する(ステップS20)。ステップS20でYesと判定した場合、優先制御信号生成部200は、フロー♯1〜フロー♯nのトークン情報に基づいて、フロー♯1〜フロー♯nのトークン値の正か否かを判定する(ステップS21)。ステップS21でYesと判定した場合、優先制御信号生成部200は、フロー♯1〜フロー♯nのパケット有無情報に基づいて、フロー♯1〜フロー♯nのパケットが有るか無いかを判定する(ステップS26)。一方、ステップS21でNoと判定した場合、優先制御信号生成部200は、フローの優先度を現在の優先度に保持する(ステップS23)。ステップS26でYesと判定した場合、優先制御信号生成部200は、このフローの優先度を低優先度に設定する(ステップS22)。
【0053】
ステップS20でNoと判定した場合、または、ステップS26でNoと判定した場合、優先制御信号生成部200は、フロー♯1〜フロー♯nのトークン廃棄情報に基づいて、フロー♯1〜フロー♯nのトークン値の廃棄が有か否かを判定する(ステップS24)。ステップS24でYesと判定した場合、優先制御信号生成部200は、このフローの優先度を高優先度に設定する(ステップS25)。一方、ステップS24でNoと判定した場合、優先制御信号生成部200は、フローの優先度を現在の優先度に保持する(ステップS23)。なおフロー♯1〜フロー♯nの優先度の初期状態は低優先度に設定される。
【0054】
なお、本実施例では、優先制御信号生成部200は、フロー♯1〜フロー♯nのスキップ情報、トークン情報、パケット有無情報、およびトークン廃棄情報に基づいて、フロー♯1〜フロー♯nの優先度を設定しているが、これには限られない。すなわち、優先制御信号生成部200は、パケット監視部180で検出されたパケット有無情報およびトークン演算部160によるトークン廃棄情報に応じて、フロー♯1〜フロー♯nのパケット出力の優先度を高優先度または低優先度に設定することができる。より具体的には、優先制御信号生成部200は、パケット監視部180で検出されたパケットの格納が有りであり、かつトークン演算部160によるトークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定することができる。また、優先制御信号生成部200は、少なくともパケット監視部180で検出されたパケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定することができる。
【0055】
次に、図6,図7A,図7Bを用いて、実施例にかかるパケット転送装置100のトークン値の遷移について説明する。図6,図7A,図7Bは、実施例にかかるパケット転送装置100のトークン値の遷移モデルを示す図である。図6,図7A,図7Bはそれぞれ、フロー♯1〜フロー♯5のトークン値の遷移モデルを示している。図6,図7A,図7Bのフロー♯1〜フロー♯5において、横軸は時間を示し、縦軸は記憶部♯1〜記憶部♯5に記憶されているトークン値を示す。図6,図7A,図7Bにおいて、各フローのパケットバッファにパケットが格納されていない期間をαで示し、パケットバッファにパケットが格納されている期間をβで示す。また、図6と図7Aにおいて、複数のトークン追加周期を時間軸に沿って周期(A)〜周期(F)という。また、図7Bは図7Aのトークン値の遷移モデルの続きを示すものであるから、図7Bの複数のトークン追加周期を時間軸に沿って周期(F)〜周期(K)という。
【0056】
図6の周期(A)では、パケットバッファ120−1〜パケットバッファ120−4にパケットが格納されていないから、フロー♯1〜フロー♯4の優先度はそれぞれ低優先度に設定されているとする。一方、フロー♯5の優先度は高優先度に設定されているとする。図6の周期(A)ではパケットバッファ120−1〜パケットバッファ120−4にパケットが格納されていないので、フロー♯5のパケットバッファ♯5からパケットが出力される(図6の(a)参照)。
【0057】
続いて周期(B)に入ると記憶部140−1〜記憶部140−5に記憶されているトークン値に追加トークン値が加算される(図6の(b)参照)。なおフロー♯1〜フロー♯4のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期(B)では、フロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図6の(c)参照)。また、周期(B)においてパケットを出力した後、フロー♯5のトークン値は負になるから、フロー♯1のパケットバッファ120−1からパケットが出力される(図6の(d)参照)。
【0058】
続いて周期(C)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図6の(e)参照)。なおフロー♯1〜フロー♯4のトークン値はパケット有り時のMax Tokenに変更される。周期(C)ではパケットバッファ120−1〜パケットバッファ120−5にパケットが格納されているが、フロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図6の(f)参照)。また、周期(C)においてパケットを出力した後、フロー♯5のトークン値は負になるから、パケットバッファ120−2およびパケットバッファ120−3からパケットが出力される(図6の(g)参照)。図6の周期(D)以降の処理は図6の周期(B)および周期(C)と同様であるから説明を省略する。
【0059】
図6で示した本実施例のモデルと図11で示した従来技術のパケット転送装置のモデルとを比較すると、フロー#5の優先度を高優先度に設定しているから、フロー#5のトークン値の最大値が従来技術に比べて小さくなる。つまり、高優先度のフローは優先的にパケットが出力され、パケットが出力されるたびにトークン値が減算されるので、トークン値の最大値を抑制することができる。したがって、Max Tokenを比較的小さく設定したとしてもトークン値の廃棄は発生し難い。その結果、Max Tokenを抑制しつつ、トークン値の廃棄の発生を抑制することができる。
【0060】
次に、図7A,図7Bでは、フロー♯1〜フロー♯5の優先度がそれぞれ低優先度に設定されているとする。まず、図7Aの周期(A)ではフロー♯1〜フロー♯5がいずれも低優先度に設定されているから、フロー♯1〜フロー♯4の順に、パケットバッファ120−1〜パケットバッファ120−4からパケットが出力される(図5Aの(a)参照)。
【0061】
続いて周期(B)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Aの(b)参照)。なおフロー♯5のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期(B)ではフロー♯1〜フロー♯4のトークン値が負であるから、パケットバッファ120−1〜パケットバッファ120−4からはパケットは出力されず、パケットバッファ120−5からパケットが出力される(図7Aの(c)参照)。
【0062】
続いて周期(C)に入ると記憶部140−1〜記憶部140−5にトークン値が加算される(図7Aの(d)参照)。周期(C)においても、フロー♯1〜フロー♯4のトークン値が負であるから、パケットバッファ120−1〜パケットバッファ120−4からはパケットは出力されず、パケットバッファ120−5からパケットが出力される(図7Aの(e)参照)。
【0063】
続いて周期(D)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Aの(f)参照)。周期(D)では、フロー♯1〜フロー♯4のトークン値が0つまり正ではないから、パケットバッファ120−1〜パケットバッファ120−4からはパケットは出力されず、パケットバッファ120−5からパケットが出力される(図7Aの(g)参照)。
【0064】
続いて周期(E)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Aの(h)参照)。周期(E)では、フロー♯1〜フロー♯4の順に、パケットバッファ120−1〜パケットバッファ120−4からパケットが出力される(図7Aの(i)参照)。
【0065】
続いて周期(F)に入ると記憶部140−1〜記憶部140−5にトークン値が加算される(図7Aの(j)参照)。ここで、フロー♯5では、記憶部140−5に記憶されたトークン値がMax Tokenを超過するから、超過した分のトークン値は廃棄される(図7Aの(k)参照)。すると、フロー♯5は、パケットバッファ120−5にパケットが格納されており、かつトークン値の廃棄が発生するので、パケットの出力の優先度が高優先度に設定される(図7Aの(m)参照)。周期(F)では、フロー♯1〜フロー♯4のトークン値が負であるから、パケットバッファ120−1〜パケットバッファ120−4からはパケットは出力されず、パケットバッファ120−5からパケットが出力される(図7Bの(n)参照)。図7Bの周期(G)は図5Bの周期(F)と同様であるから、説明を省略する。また、図7Bの周期(H)は図7Aの周期(D)と同様であるから、説明を省略する。
【0066】
続いて周期(I)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Bの(o)参照)。周期(I)ではパケットバッファ120−1〜パケットバッファ120−5にパケットが格納されているが、フロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図7Bの(p)参照)。また、周期(I)においてパケットを出力した後、フロー♯5のトークン値は0つまり正ではなくなるから、パケットバッファ120−1、パケットバッファ120−2からパケットが出力される(図7Bの(q)参照)。
【0067】
続いて周期(J)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Bの(r)参照)。周期(J)ではフロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図7Bの(s)参照)。また、周期(J)においてパケットを出力した後、フロー♯5のトークン値は負になるから、パケットバッファ120−3からパケットが出力される(図7Bの(t)参照)。
【0068】
続いて周期(K)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Bの(u)参照)。周期(K)ではフロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図7Bの(v)参照)。また、周期(K)においてパケットを出力した後、フロー♯5のトークン値は負になるから、パケットバッファ120−4からパケットが出力される(図7Bの(w)参照)。
【0069】
以上のように、仮に、フロー♯5の優先度が低優先度の状態からトークン値が遷移したとしても、パケットバッファ120−5にパケットが格納されており、かつフロー♯5のトークン値がMax Tokenに達した時点でフロー♯5の優先度は高優先度に設定される。したがって、図7A,図7Bで示したパケット転送装置のモデルと図11で示した従来技術のパケット転送装置のモデルとを比較すると、フロー#5のトークン値の最大値が従来技術に比べて小さくなる。つまり、高優先度のフローは優先的にパケットが出力され、パケットが出力されるたびにトークン値が減算されるので、トークン値の最大値を抑制することができる。したがって、Max Tokenを比較的小さく設定したとしてもトークン値の廃棄は発生し難い。その結果、Max Tokenを抑制しつつ、トークン値の廃棄の発生を抑制することができる。
【0070】
また、本実施例によれば、パケットバッファ120−1〜パケットバッファ120−nにパケットが蓄積された後、所定の時間が経過するとパケットを廃棄するHead Dropのような制御を行う場合であっても、パケットの廃棄の発生を抑制することができる。つまり、従来技術では、パケットバッファ120−1〜パケットバッファ120−nにパケットが蓄積されているにもかかわらず、他のフローの処理待ちのためにパケットが廃棄されるおそれがある。この点、本実施例は、パケットバッファ120−1〜パケットバッファ120−nにパケットが格納されていれば、トークン値の廃棄が発生した時点で高優先度になり、優先してパケットが出力されるので、所定時間経過後のパケットの廃棄が生じ難い。
【0071】
ところで、トークン値の廃棄が発生しないようにMax Tokenを設定するためには、Max Token[byte]=フロー数[本]×最大パケット長[byte]/出力回線ワイヤレート[bps]×フローのSh_R[bps]とする。
【0072】
例えばあるパケット転送装置Xが、収容フロー数1024、最大パケット長10K[byte]、Sh_R設定粒度500K[bps]、Sh_Rのレンジ500K[bps]〜10G[bps]、トークン追加周期32u[s]という仕様となっているとする。このパケット転送装置Xにおいて、Sh_Rが500K[bps]の場合、トークン追加周期ごとに2[byte](=500K[bps]/8×32u[s])のトークン値が加算される。また、このパケット転送装置Xにおいて、Sh_Rが10Gbpsの場合、トークン追加周期ごとに40000byte(=10G[bps]/8×32u[s])のトークン値が加算される。
【0073】
また、Sh_Rが1[Mbps]のフローが1000本あり、Sh_Rが9G[bps] のフローが1本あり、トータルのSh_Rが10G[bps]である場合を例に挙げると、Sh_Rが1M[bps]のフローのMax Tokenは、1K[byte](= 1000[本]×10K[byte]/(10×10^9)[bps]×(1×10^6)[bps])となる。また、Sh_Rが9G[bps]のフローのMax Tokenは、9M[byte](=1000[本]×10K[byte]/(10×10^9)[bps]×(9×10^9)[bps])となる。
【0074】
これに対して、本実施例のパケット転送装置においては、46K[byte](=1回の追加トークン分(36K[byte])+最大パケット長(10K[byte]))のMax Tokenで、パケットの出力帯域の劣化を抑制することができる。ここで、低優先度のフローは従来技術に比べてトークン値が貯まりやすくなるが、Sh_Rが低ければ、トークン追加周期ごとのトークン値の追加は小さい。したがって、低優先度のフローであっても、従来技術のような例えば9M[byte]ものトークン値には達し難い。
【0075】
また、Sh_Rが1M[bps]のフローの最大待ち合わせ時間は、80[ms]となる。つまり、低優先(1M[bps])のフローには、32u[s]周期で1G[bps]分が割り当てられるので、単位時間あたりには4K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、80[ms]必要になる。ここで、待ち合わせ時間の間に追加するトークン値は10K[byte](=1M[bps]/8×80m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
【0076】
以下、本実施例のパケット転送装置についてフローの本数およびフローのSh_Rを変えたいくつかのケースを説明する。
【0077】
(ケース1)
Sh_Rが1M[bps]のフローが500本、Sh_Rが5M[bps]のフローが500本、Sh_Rが7G[bps]のフローが1本である場合を例に挙げる。Sh_Rが7G[bps]のフローのMax Tokenが38K[byte]であった場合、Sh_Rが7G[bps]のフローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが5M[bps]のフローの最大待ち合わせ時間は、26.7m[s] となる。つまり、低優先(1M[bps] と5M[bps])のフローには、32u[s]周期で3G[bps]分が割り当てられるので、単位時間あたり12K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、26.7[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン値は16.7K[byte](=5M[bps] /8 x 26.7m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
【0078】
(ケース2)
Sh_Rが1M[bps]フローが999本、Sh_Rが5M[bps]フローが1本、Sh_Rが9G[bps]フローが1本である場合を例に挙げる。Sh_Rが9G[bps]フローのMax Tokenが46K[byte]であった場合、Sh_Rが9G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが5M[bps]のフローの最大待ち合わせ時間は、80m[s]となる。つまり、低優先(1M[bps])のフローには、32u[s]周期で1G[bps]分が割り当てられるので、単位時間あたり4K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、80[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン値は50K[byte](=5M[bps] / 8 x 80m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
【0079】
(ケース3)
Sh_Rが1M[bps]フローが1000本、Sh_Rが1G[bps]フローが1本、Sh_Rが8G[bps]フローが1本である場合を例に挙げる。Sh_Rが8G[bps]フローのMax Tokenが42K[byte]であった場合、Sh_Rが8G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが1G[bps]のフローの最大待ち合わせ時間は、40m[s]となる。つまり、低優先(1M[bps]と1G[bps])のフローには、32u[s]周期で2G[bps]分が割り当てられるので、単位時間あたり8K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、40[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン量は5M[byte](=1G[bps]/8×40m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
【0080】
また、Sh_Rが1G[bps]フローのMax Tokenも42K[byte]であった場合、Sh_Rが1G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。そのときはSh_Rが8G[bps]フローのMax TokenはSh_Rが1G[bps]フローにより10K[byte]パケット出力時間を奪われてもトークン値の廃棄の発生を回避しなければならないため、さらに最大パケット長分を加えた52K[byte]のMax Tokenが必要となる。しかし、それでも従来技術においてパケットの出力帯域の劣化を抑制ために必要なMax Tokenと比較すると1/100以下のMax Tokenでパケットの出力帯域の劣化を抑制することができる。
【0081】
以上、本実施例のパケット転送装置100によれば、バケットバッファ120−1〜パケットバッファ120−nにパケットが格納されているフロー♯1〜フロー♯nでトークン値の廃棄が発生したら、そのフローのパケット出力の優先度は高優先度になる。パケット出力の優先度が高優先度になると、そのフローのパケットバッファからは優先的にパケットが出力される。パケットバッファからパケットが出力されると、パケットが出力されたフローに対応して記憶部に記憶されたトークン値から出力パケット長に応じたトークン値が減算される。したがって、本実施例のパケット転送装置100によれば、フローの数が増大したとしても、記憶部に記憶されるトークン値の最大値を抑制することができるので、Max Tokenを抑制し、かつトークン値の廃棄の発生を抑制することができる。
【0082】
上記の実施例に関し、さらに以下の付記を開示する。
【0083】
(付記1)パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファと、
前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を前記複数のフローに対応して記憶する記憶部と、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算するとともに、前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算し、さらに前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄するトークン演算部と、
前記複数のフローごとに前記パケットバッファにパケットが格納されているか否かを検出するパケット監視部と、
前記パケット監視部で検出された前記パケットの格納の有無および前記トークン演算部による前記トークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部と、
前記優先制御信号生成部で設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部と
を備えたことを特徴とするパケット転送装置。
【0084】
(付記2)前記優先制御信号生成部は、前記パケット監視部で検出された前記パケットの格納が有りであり、かつ前記トークン演算部による前記トークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定し、
少なくとも前記パケット監視部で検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
付記1に記載のパケット転送装置。
【0085】
(付記3)前記トークン演算部は、前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別し、
前記出力フロー選択部は、前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながらパケットを出力するフローを順次選択し、
前記優先制御信号生成部は、前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が正と判別されたフローのパケット出力の優先度を低優先度に設定し、
前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が負と判別されたフローのパケット出力の優先度を保持し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が無しであるフローの優先度を保持する
付記1に記載のパケット転送装置。
【0086】
(付記4)パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファにパケットが格納されているか否かを前記複数のフローごとに検出する監視ステップと、
前記複数のフローに対応して記憶部に記憶されており、前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値のそれぞれに、あらかじめ設定された周期で所定のトークン値を加算する加算ステップと、
前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する減算ステップと、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する廃棄ステップと、
前記監視ステップで検出されたパケットの格納の有無および前記廃棄ステップによるトークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先度設定ステップと、
前記優先度設定ステップで設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択ステップと
を備えたことを特徴とするパケット転送方法。
【0087】
(付記5)前記優先度設定ステップは、前記監視ステップで検出された前記パケットの格納が有りであり、かつ前記廃棄ステップによる前記トークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定し、
少なくとも前記監視ステップで検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
付記4に記載のパケット転送方法。
【0088】
(付記6)前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別する判別ステップを有し、
前記出力フロー選択ステップは、前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながらパケットを出力するフローを順次選択し、
前記優先度設定ステップは、前記出力フロー選択ステップでスキップされて、かつ前記判別ステップでトークン値が正と判別されたフローのパケット出力の優先度を低優先度に設定し、
前記出力フロー選択ステップでスキップされて、かつ前記判別ステップでトークン値が負と判別されたフローのパケット出力の優先度を保持し、
前記出力フロー選択ステップでスキップされず、かつ前記判別ステップでトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、
前記出力フロー選択ステップでスキップされず、かつ前記判別ステップでトークン値の廃棄が無しであるフローの優先度を保持する
付記4に記載のパケット転送方法。
【符号の説明】
【0089】
100 パケット転送装置
120 パケットバッファ
140 記憶部
160 トークン演算部
180 パケット監視部
200 優先制御信号生成部
220 出力フロー選択部
【技術分野】
【0001】
本発明は、パケット転送装置およびパケット転送方法に関する。
【背景技術】
【0002】
従来、パケット通信の技術分野においては、パケットが伝送される複数のフローの合流地点にパケット転送装置を設けることが知られている。パケット転送装置は、複数のフローを流れるパケットの出力順序を制御しながら出力回路に転送することにより、出力回路のトラフィックを制御する。
【0003】
また、パケット転送装置のパケット転送技術としてトークンバケット方式が知られている。トークンバケット方式は、複数のフローを流れるパケットをパケットバッファにいったん格納し、パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を用いてパケットを出力する。
【0004】
図8は、トークンバケット方式を説明するための図である。図8において横軸は時間を示し、縦軸は記憶部に記憶されているトークン値を示す。トークンバケット方式では、複数のフローに対応してトークン値が記憶される記憶部を有する。トークンバケット方式では、記憶部に記憶されたトークン値に、あらかじめ設定された周期(以下、「トークン追加周期」という。)で所定のトークン値(以下、「追加トークン値」という。)を加算する(図8の(a)参照)。また、トークンバケット方式では、記憶部に記憶されているトークン値が正または出力パケット長以上である場合にパケットの出力許可を行う。また、トークンバケット方式では、パケットバッファからパケットが出力されたら、パケットが出力されたフローに対応する記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する(図8の(b)参照)。なお図8の例は、トークン値が正の場合にパケットの出力許可を行う例である。また、トークンバケット方式では、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値(以下、「Max Token」という。)を超過したら、超過した分のトークン値を廃棄する(図8の(c)参照)。
【0005】
トークンバケット方式によって導かれるシェーピングレート(Shaping Rate:以下、「Sh_R」という。) は、トークン追加周期と、追加トークン値とによって以下のように表される。
Sh_R [bps(bits per second)]=追加トークン値[byte]×8/トークン追加周期[s(second)]
なお、Sh_Rとは、フローごとのパケットの出力帯域である。例えば、追加トークン値が40,000[byte]、トークン追加周期が32[us](=32×10^−6 [s])の場合、Sh_Rは10G[bps](=40,000 [byte]×8/32×10^−6[s])となる。
【0006】
また、パケット転送装置では、トークンバケット方式とラウンドロビン(Round Robin:以下、「RR」という。)方式との組み合わせにより、複数のフローからのパケットの出力順序を制御することが知られている。RR方式とは、複数のフローを順番に選択しながら、選択されたフローのパケットバッファに格納されたパケットを順次出力する方式である。
【0007】
図9は、トークンバケット方式とRR方式との組み合わせを用いたパケット出力を説明するための図である。フロー♯1〜フロー♯nを流れるパケット♯1〜パケット♯nは、パケットバッファ♯1〜パケットバッファ♯nにそれぞれ格納される。なおnは2以上の自然数である。ここで、フロー♯1〜フロー♯nのうち、記憶部に記憶されたトークン値が正であり、かつパケットバッファにパケットが格納されているフローが順次選択され、選択されたフローのパケットバッファに格納されたパケットが出力回路へ出力される。なお、フロー♯1〜フロー♯nそれぞれのSh_Rの総和ΣSh_Rは、出力回線のワイヤレート以下である。
【0008】
なお、複数のフローのパケットの出力帯域を管理する方法としては、WRR(Weighted Round Robin)という技術も知られている。WRRは、トークンの代わりに重み(Weight)をフローごとに与える。また、WRRでは、あるフローが読み出し権利を得たら重みに応じた量を読み出した後、次のフローに読み出し権利を渡す制御を行う。例えばパケットの出力帯域=10G[bps]であり、重み=1のフローが1本のみである場合、そのフローは10G[bps]の性能が得られる。また、パケットの出力帯域=10G[bps]であり、重み=1のフローがもう1本存在すれば、各フローはそれぞれ5G[bps]の性能が得られる。ここで、一方のフローにパケットが入力されない場合、他方のフローが10G[bps]の出力帯域を占有することになるが、出力されたパケットを受信する装置が5G[bps]の受信能力しか無ければパケットは廃棄される。そこでもしパケットの出力帯域の上限設定が必要な場合、各フローにシェーパの設定を行う。
【0009】
ところで、従来技術では、トークン値の廃棄の発生を抑制する目的で、パケットバッファにパケットが格納されているフローのMax Tokenを、パケットバッファにパケットが格納されていないフローのMax Tokenより大きく設定することが知られている。例えば従来技術は、パケットバッファにパケットが格納されていないフローのMax Token=追加トークン値×1とし、パケットバッファにパケットが格納されているフローのMax Token=追加トークン値×nとする。ここでnは、トークン値が廃棄されない程度に大きく設定する値である。
【先行技術文献】
【特許文献】
【0010】
【特許文献1】特開2007−181085号公報
【発明の概要】
【発明が解決しようとする課題】
【0011】
しかしながら、従来技術は、フローの数にかかわらずMax Tokenの増大を抑制することについては考慮されていない。
【0012】
すなわち、従来技術によれば、フロー数の増大にしたがって記憶部に記憶されているトークン値の最大値が大きくなる場合がある。以下この点について説明する。図10,図11は、従来技術のパケット転送装置のトークン値の遷移モデルを示す図である。図10のトークン値の遷移モデルは、3フローを収容したパケット転送装置の一例である。また、図11のトークン値の遷移モデルは、全体の帯域は図10の場合と変えずに2フロー増加したパケット転送装置の一例である。図10と図11において、各フローのパケットバッファにパケットが格納されていない期間をαで示し、パケットバッファにパケットが格納されている期間をβで示す。また、図10と図11において、複数のトークン追加周期を時間軸に沿って周期(A)〜周期(F)という。
【0013】
図10の周期(A)ではフロー♯1とフロー♯2のパケットバッファにパケットが格納されていないので、フロー♯5のパケットバッファからパケットが出力される(図10の(a)参照)。続いて周期(B)に入ると各フローの記憶部にトークン値が加算される(図10の(b)参照)。なおフロー♯1およびフロー♯2のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期(B)ではフロー♯1、フロー♯2およびフロー♯5のパケットバッファにパケットが格納されているから、フロー♯1、フロー♯2、フロー♯5の順にパケットが出力される(図10の(c)参照)。また、周期(B)においてパケットを出力した後、フロー♯1とフロー♯2のトークン値は負になるのに対して、フロー♯5のトークン値は正であるから、フロー♯5からパケットが出力される(図10の(d)参照)。続いて周期(C)に入ると各フローの記憶部にトークン値が加算される(図10の(e)参照)。周期(C)ではフロー♯1およびフロー♯2のトークン値が「0」つまり正ではないから、フロー♯1およびフロー♯2からはパケットが出力されず、フロー♯5からパケットが出力される(図10の(f)参照)。図10の周期(D)以降の処理は図10の周期(B)および周期(C)と同様であるから、説明を省略する。
【0014】
次に、図11の周期(A)は図10の場合と同様であるから説明を省略する。これに対して、図11の周期(B)では、フロー♯3とフロー♯4が追加されてフロー数が多くなっているから、フロー♯1〜フロー♯4の順にパケットが出力され(図11の(a)参照)、フロー♯5からはパケットが出力されない。この状態で周期(C)に入ると各フローの記憶部にトークン値が加算される(図11の(b)参照)。その結果、図10のフロー♯5と図11のフロー♯5を比較すると、フロー数が多い図10のフロー♯5の記憶部に記憶されるトークン値の最大値が、図10の場合と比べて大きくなる。なお、図11の周期(C)の以後の処理は図10の周期(B)および周期(C)と同様であるから、説明を省略する。
【0015】
このように、RR方式を用いてパケットを出力するフローを順次選択する場合、フローの数が多くなるにしたがって、あるフローのパケットを出力する処理の待ち時間が長くなる。待ち時間の間はトークン追加周期がくるたびに記憶部にトークン値が加算される。一方、待ち時間の間はパケットが出力されないから、記憶部に記憶されているトークン値の減算は行われない。したがって、フローの数が多くなると、記憶部に記憶されるトークン値の最大値は大きくなる。トークン値の最大値が大きくなると、トークン値がMax Tokenを超えてトークン値の廃棄が発生するおそれが増大する。パケットバッファにパケットが格納されているフローに対してトークン値の廃棄が頻繁に発生すると、パケットの出力帯域の劣化につながるので好ましくない。一方、トークン値の廃棄を抑制するためにMax Tokenを大きく設定することも考えられるが、これは回路規模の増大を招くので好ましくない。
【0016】
開示の技術は、上記に鑑みてなされたものであって、フローの数にかかわらずMax Tokenの増大を抑制し、かつトークン値の廃棄の発生を抑制することができるパケット転送装置およびパケット転送方法を提供することを目的とする。
【課題を解決するための手段】
【0017】
本願の開示するパケット転送装置は、一つの態様において、パケットを伝送する複数のフローを流れるパケットをそれぞれ複数のフローに対応して格納するパケットバッファを有する。また、パケット転送装置は、パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を複数のフローに対応して記憶する記憶部を有する。また、パケット転送装置は、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算するトークン演算部を有する。トークン演算部は、パケットバッファからパケットが出力されたフローに対応して記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する。また、トークン演算部は、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する。また、パケット転送装置は、複数のフローごとにパケットバッファにパケットが格納されているか否かを検出するパケット監視部を有する。また、パケット転送装置は、パケット監視部で検出されたパケットの格納の有無およびトークン演算部によるトークン値の廃棄の有無に応じて、複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部を有する。また、パケット転送装置は、優先制御信号生成部で設定された複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部を有する。
【発明の効果】
【0018】
本願の開示するパケット転送装置の一つの態様によれば、フローの数の多少にかかわらずMax Tokenの増大を抑制し、かつトークン値の廃棄の発生を抑制することができる。
【図面の簡単な説明】
【0019】
【図1】図1は、実施例にかかるパケット転送装置の全体構成を示す図である。
【図2】図2は、優先制御信号生成部の詳細構成を示す図である。
【図3】図3は、出力フロー選択部の詳細構成を示す図である。
【図4】図4は、スキップ判定回路の動作を説明するための図である。
【図5】図5は、優先制御信号生成部の動作を説明するための図である。
【図6】図6は、実施例にかかるパケット転送装置のトークン値の遷移モデルを示す図である。
【図7A】図7Aは、実施例にかかるパケット転送装置のトークン値の遷移モデルを示す図である。
【図7B】図7Bは、実施例にかかるパケット転送装置のトークン値の遷移モデルを示す図である。
【図8】図8は、トークンバケット方式を説明するための図である。
【図9】図9は、トークンバケット方式とRR方式との組み合わせを用いたパケット出力を説明するための図である。
【図10】図10は、従来技術のパケット転送装置のトークン値の遷移モデルを示す図である。
【図11】図11は、従来技術のパケット転送装置のトークン値の遷移モデルを示す図である。
【発明を実施するための形態】
【0020】
以下に、本願の開示するパケット転送装置およびパケット転送方法の実施例を図面に基づいて詳細に説明する。なお、この実施例により開示技術が限定されるものではない。
【実施例】
【0021】
図1は、実施例にかかるパケット転送装置の全体構成を示す図である。本実施例のパケット転送装置100は、パケットバッファ120と、記憶部140と、トークン演算部160と、パケット監視部180と、優先制御信号生成部200と、出力フロー選択部220とを有する。
【0022】
パケットバッファ120は、パケットバッファ120−1〜パケットバッファ120−nを有する。パケットバッファ120−1〜パケットバッファ120−nはそれぞれ、パケットを伝送するフロー♯1〜フロー♯nに対応して設けられる。パケットバッファ120−1〜パケットバッファ120−nには、フロー♯1〜フロー♯nを流れるパケットがそれぞれ格納される。
【0023】
記憶部140は、記憶部140−1〜記憶部140−nを有する。記憶部140−1〜記憶部140−nはそれぞれ、フロー♯1〜フロー♯nに対応して設けられる。記憶部140−1〜記憶部140−nには、それぞれトークン値が記憶される。トークン値は、パケットバッファ120−1〜パケットバッファ120−nに格納されたパケットの出力を許可するか否かを判別するのに用いる情報である。
【0024】
トークン演算部160は、トークンバケット方式にしたがって、記憶部140−1〜記憶部140−nに記憶されているトークン値に、トークン追加周期で追加トークン値を加算する。また、トークン演算部160は、記憶部140−1〜記憶部140−nのうちパケットバッファからパケットが出力されたフローに対応する記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する。さらに、トークン演算部160は、記憶部140−1〜記憶部140−nごとに、記憶されたトークン値が正か負かを判別する。記憶部140−1〜記憶部140−nごとのトークン値の正負の情報は、トークン情報として、優先制御信号生成部200と出力フロー選択部220に出力される。また、トークン演算部160は、フロー♯1〜フロー♯nに対応して記憶部140−1〜記憶部140−nに記憶されたトークン値があらかじめ設定されたMax Tokenを超過したら超過した分のトークン値を廃棄する。記憶部140−1〜記憶部140−nごとのトークン値の廃棄の有無の情報は、トークン廃棄情報として、優先制御信号生成部200に出力される。
【0025】
パケット監視部180は、フロー♯1〜フロー♯nからパケットが入力されたら、パケットバッファ120−1〜パケットバッファ120−nのうち、パケットが入力されたフローに対応するパケットバッファにパケットを格納する。また、パケット監視部180は、パケットが格納されたパケットバッファの総パケット数の加算を行う。また、パケット監視部180は、パケットバッファ120−1〜パケットバッファ120−nからパケットが出力されたら、パケットが出力されたパケットバッファの総パケット数の減算を行う。さらに、パケット監視部180は、パケットバッファ120−1〜パケットバッファ120−nそれぞれの総パケット数を監視することにより、パケットバッファにパケットが格納されているか否かを検出する。パケットバッファ120−1〜パケットバッファ120−nごとのパケットが格納されているか否かの情報は、パケット有無情報として、優先制御信号生成部200と出力フロー選択部220に出力される。
【0026】
優先制御信号生成部200には、トークン演算部160から出力されたトークン廃棄情報およびトークン情報と、パケット監視部180から出力されたパケット有無情報と、出力フロー選択部220から出力されたスキップ情報とが入力される。優先制御信号生成部200は、入力された各情報に基づいて、フロー♯1〜フロー♯nのパケット出力の優先度を高優先度または低優先度に設定する。フロー♯1〜フロー♯nごとのパケット出力の優先度は、優先情報として出力フロー選択部220に出力される。優先制御信号生成部200の詳細は後述する。
【0027】
出力フロー選択部220は、優先制御信号生成部200から出力されたフロー♯1〜フロー♯nごとのパケット出力の優先情報に応じて、パケットを出力するフローを順次選択する。より具体的には、出力フロー選択部220は、フロー♯1〜フロー♯nを高優先度のクラスと低優先度のクラスに分け、高優先度のクラスのフローから優先的にパケットを出力し、高優先度のフローがなくなったら、低優先度のフローからパケットを出力する。出力フロー選択部220は、パケットバッファにパケットが格納されていないフローまたは記憶部のトークン値が負のフローをスキップしながらパケットを出力するフローを順次選択する。フロー♯1〜フロー♯nごとのスキップの発生の有無の情報は、スキップ情報として、優先制御信号生成部200に出力される。また、フロー♯1〜フロー♯nのうち、どのフローからパケットが出力されたかという情報は、出力フロー情報として、パケットバッファ120、トークン演算部160、およびパケット監視部180に出力される。
【0028】
次に、優先制御信号生成部200の詳細を説明する。図2は、優先制御信号生成部200の詳細構成を示す図である。優先制御信号生成部200は、選択回路202−1〜選択回路202−nと、and回路204a−1〜and回路204a−nと、and回路204b−1〜and回路204b−nとを有する。選択回路202−1〜選択回路202−nはそれぞれ、フロー♯1〜フロー♯nに対応して設けられる。and回路204a−1〜and回路204a−nはそれぞれ、フロー♯1〜フロー♯nに対応して設けられる。and回路204b−1〜and回路204b−nはそれぞれ、フロー♯1〜フロー♯nに対応して設けられる。
【0029】
and回路204a−1〜and回路204a−nにはそれぞれ、フロー♯1〜フロー♯nのトークン廃棄情報のうち、対応するフローのトークン廃棄情報が入力される。トークン廃棄情報は、トークン値の廃棄が発生した場合には「1」、トークン値の廃棄が発生しなかった場合には「0」という論理値でand回路204a−1〜and回路204a−nに入力される。
【0030】
また、and回路204a−1〜and回路204a−nにはそれぞれ、フロー♯1〜フロー♯nのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。つまり、パケット有無情報は、フローのパケットが存在した場合には「1」、フローのパケットが存在しない場合には「0」という論理値でand回路204a−1〜and回路204a−nに入力される。
【0031】
また、and回路204a−1〜and回路204a−nはそれぞれ、入力されたトークン廃棄情報とパケット有無情報に応じた論理値を、対応する選択回路202−1〜選択回路202−nに出力する。具体的には、and回路204a−1〜and回路204a−nはそれぞれ、入力されたトークン廃棄情報とパケット有無情報がともに「1」の場合には「1」を、対応する選択回路202−1〜選択回路202−nに出力する。また、and回路204a−1〜and回路204a−nはそれぞれ、入力されたトークン廃棄情報とパケット有無情報の少なくとも一方が「0」の場合には「0」を、対応する選択回路202−1〜選択回路202−nに出力する。
【0032】
一方、and回路204b−1〜and回路204b−nにはそれぞれ、フロー♯1〜フロー♯nのトークン情報のうち、対応するフローのトークン情報が入力される。トークン情報は、記憶部のトークン値が正の場合は「1」、記憶部のトークン値が負の場合は「0」という論理値でand回路204b−1〜and回路204b−nに入力される。
【0033】
また、and回路204b−1〜and回路204b−nにはそれぞれ、フロー♯1〜フロー♯nのスキップ情報のうち、対応するフローのスキップ情報が入力される。スキップ情報は、フローのパケット出力処理がスキップされた場合には「1」、フローのパケット出力処理がスキップされなかった場合には「0」という論理値でand回路204b−1〜and回路204b−nに入力される。さらに、and回路204b−1〜and回路204b−nにはそれぞれ、フロー♯1〜フロー♯nのパケット有無情報のうち、対応するフローのパケット有無情報が論理反転されて入力される。つまり、フローのパケットが存在しない場合には「1」、フローのパケットが存在する場合には「0」という論理値でand回路204b−1〜and回路204b−nに入力される。
【0034】
and回路204b−1〜and回路204b−nはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報に応じた論理値を、対応する選択回路202−1〜選択回路202−nに出力する。具体的には、and回路204b−1〜and回路204b−nはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報がともに「1」の場合には「1」を、対応する選択回路202−1〜選択回路202−nに出力する。また、and回路204b−1〜and回路204b−nはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報のいずれかが「0」の場合には「0」を、対応する選択回路202−1〜選択回路202−nに出力する。
【0035】
選択回路202−1〜選択回路202−nはそれぞれ、対応するand回路204a−1〜and回路204a−nおよびand回路204b−1〜and回路204b−nから入力された論理値に応じた論理値を優先情報として出力する。例えば選択回路202−1は、and回路204a−1から出力された論理値が「1」で、and回路204b−1から出力された論理値が「0」の場合は、フロー♯1の優先度を高優先度に設定する論理値「1」を優先情報として出力する。一方、選択回路202−1は、and回路204a−1から出力された論理値が「0」で、and回路204b−1から出力された論理値が「1」の場合は、フロー♯1の優先度を低優先度に設定する論理値「0」を優先情報として出力する。選択回路202−2〜選択回路202−nについても同様である。
【0036】
次に、出力フロー選択部220の詳細を説明する。図3は、出力フロー選択部220の詳細構成を示す図である。出力フロー選択部220は、ストリクトプライオリティ(Strict Priority:以下「SP」という。)回路222と、RR回路224aと、RR回路224bを有する。また、出力フロー選択部220は、出力用and回路226a−1〜出力用and回路226a−nと、出力用and回路226b−1〜出力用and回路226b−nとを有する。また、出力フロー選択部220は、出力フロー保持回路228と、スキップ判定回路230−1〜スキップ判定回路230−nを有する。
【0037】
出力用and回路226a−1〜出力用and回路226a−nにはそれぞれ、フロー♯1〜フロー♯nの優先情報のうち、対応するフローの優先情報が入力される。優先情報は、フローの優先度が高優先度の場合には「1」、フローの優先度が低優先度の場合には「0」の論理値で出力用and回路226a−1〜出力用and回路226a−nに入力される。
【0038】
また、出力用and回路226a−1〜出力用and回路226a−nにはそれぞれ、フロー♯1〜フロー♯nのトークン情報のうち、対応するフローのトークン情報が入力される。また、出力用and回路226a−1〜出力用and回路226a−nにはそれぞれ、フロー♯1〜フロー♯nのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。パケット有無情報は、パケットバッファにパケットが格納されている場合には「1」、パケットバッファにパケットが格納されていない場合には「0」の論理値で出力用and回路226a−1〜出力用and回路226a−nに入力される。
【0039】
出力用and回路226a−1〜出力用and回路226a−nはそれぞれ、入力された優先情報とトークン情報とパケット有無情報に応じた論理値を、RR回路224aに出力する。具体的には、出力用and回路226a−1〜出力用and回路226a−nはそれぞれ、入力された優先情報とトークン情報とパケット有無情報の全ての論理値が「1」の場合には論理値「1」を出力する。また、出力用and回路226a−1〜出力用and回路226a−nはそれぞれ、入力された優先情報とトークン情報とパケット有無情報の少なくとも1つの論理値が「0」の場合には論理値「0」を出力する。
【0040】
一方、出力用and回路226b−1〜出力用and回路226b−nにはそれぞれ、フロー♯1〜フロー♯nのトークン情報のうち、対応するフローのトークン情報が入力される。また、出力用and回路226b−1〜出力用and回路226b−nにはそれぞれ、フロー♯1〜フロー♯nのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。
【0041】
出力用and回路226b−1〜出力用and回路226b−nはそれぞれ、入力されたトークン情報とパケット有無情報に応じた論理値を、RR回路224bに出力する。具体的には、出力用and回路226b−1〜出力用and回路226b−nはそれぞれ、入力されたトークン情報とパケット有無情報の論理値がともに「1」の場合には論理値「1」を出力する。また、出力用and回路226b−1〜出力用and回路226b−nはそれぞれ、入力されたトークン情報とパケット有無情報の少なくとも一方の論理値が「0」の場合には論理値「0」を出力する。
【0042】
RR回路224aは、フロー♯1〜フロー♯nのうち、出力用and回路226a−1〜出力用and回路226a−nからの出力論理値が「1」である出力用and回路に対応するフローを順次選択してSP回路222に出力する。RR回路224bは、フロー♯1〜フロー♯nのうち、出力用and回路226b−1〜出力用and回路226b−nからの出力論理値が「1」である出力用and回路に対応するフローを順次選択してSP回路222に出力する。
【0043】
SP回路222は、RR回路224aからの出力がある場合、RR回路224aからの出力を出力フロー情報として出力する。つまり、SP回路222は、高優先度に設定されたフローがあるときには、高優先度のフローからのパケット出力を優先する。一方、SP回路222は、RR回路224aからの出力がない場合、RR回路224bからの出力を出力フロー情報として出力する。このように、出力フロー選択部220は、フロー♯1〜フロー♯nを高優先度のクラスと低優先度のクラスに分け、高優先度のクラスのフローから優先的にパケットを出力し、高優先度のフローがなくなったら、低優先度のフローからパケットを出力する。
【0044】
SP回路222から出力された出力フロー情報は、出力フロー選択部220の外部へ出力されるとともに、出力フロー保持回路228と、スキップ判定回路230−1〜スキップ判定回路230−nのそれぞれに入力される。出力フロー保持回路228は、SP回路222から出力された出力フロー情報を保持するとともに、前回出力フロー情報をスキップ判定回路230−1〜スキップ判定回路230−nのそれぞれに入力する。スキップ判定回路230−1〜スキップ判定回路230−nはそれぞれ、出力フロー情報と前回出力フロー情報に基づいて、フロー♯1〜フロー♯nのパケット出力の処理がスキップされたか否かを判定する。前回出力フロー情報とは、最新のパケット出力の1つ前にパケットバッファからパケットが出力されたフローの情報である。
【0045】
図4は、スキップ判定回路の動作を説明するための図である。図4において、自フローとは、フロー♯1〜フロー♯nのそれぞれのフローを指す。スキップ判定回路230−1〜スキップ判定回路230−nは、フロー♯1〜フロー♯nのそれぞれに対して以下のフローチャートの処理を行う。また、図4の例では、フロー♯1〜フロー♯nにはそれぞれ、昇順のフローID(Identification)が付されているものとする。
【0046】
まず、スキップ判定回路230−1〜スキップ判定回路230−nは、フロー♯1〜フロー♯nのうち、パケットバッファからパケットが出力された最新のフローのID(以下、「出力フローID」という。)=自フローIDであるか確認する(ステップS1)。ステップS1でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローにスキップ有りの判定がなされていたら、そのスキップ判定を解除する(ステップS2)。
【0047】
一方、ステップS1でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、出力フローID>自フローIDであるか確認する(ステップS3)。ステップS3でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、フロー♯1〜フロー♯nのうち、前回出力フローID<自フローIDであるか確認する(ステップS4)。前回出力フローIDとは、出力フローIDの1つ前にパケットバッファからパケットが出力されたフローのIDである。ステップS4でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローがスキップされたと判定する(ステップS5)。
【0048】
一方、S4でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、前回出力フローID>出力フローIDであるか確認する(ステップS6)。ステップS6でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローがスキップされたと判定する(ステップS7)。一方、ステップS6でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローはスキップ判定が解除されているかまたはスキップされたと判定されているかの現在の状態(以下、「現在スキップ判定状態」という。)を保持する(ステップS8)。
【0049】
ステップS3でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、前回出力フローID≧自フローIDであるか確認する(ステップS9)。ステップS9でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、現在スキップ判定状態を保持する(ステップS10)。
【0050】
一方、ステップS9でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、前回出力フローID<出力フローIDであるか確認する(ステップS11)。ステップS11でYesの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、現在スキップ判定状態を保持する(ステップS12)。一方、ステップS11でNoの場合、スキップ判定回路230−1〜スキップ判定回路230−nは、自フローがスキップされたと判定する(ステップS13)。
【0051】
スキップ判定回路230−1〜スキップ判定回路230−nから出力されたフロー♯1〜フロー♯nの現在スキップ判定状態は、スキップ情報として優先制御信号生成部200に入力される。図5は、優先制御信号生成部200の動作を説明するための図である。優先制御信号生成部200は、以下のフローチャートの処理をフロー♯1〜フロー♯nのそれぞれに対して行う。
【0052】
まず、優先制御信号生成部200は、フロー♯1〜フロー♯nのスキップ情報に基づいて、フロー♯1〜フロー♯nのスキップの発生が有か否かを判定する(ステップS20)。ステップS20でYesと判定した場合、優先制御信号生成部200は、フロー♯1〜フロー♯nのトークン情報に基づいて、フロー♯1〜フロー♯nのトークン値の正か否かを判定する(ステップS21)。ステップS21でYesと判定した場合、優先制御信号生成部200は、フロー♯1〜フロー♯nのパケット有無情報に基づいて、フロー♯1〜フロー♯nのパケットが有るか無いかを判定する(ステップS26)。一方、ステップS21でNoと判定した場合、優先制御信号生成部200は、フローの優先度を現在の優先度に保持する(ステップS23)。ステップS26でYesと判定した場合、優先制御信号生成部200は、このフローの優先度を低優先度に設定する(ステップS22)。
【0053】
ステップS20でNoと判定した場合、または、ステップS26でNoと判定した場合、優先制御信号生成部200は、フロー♯1〜フロー♯nのトークン廃棄情報に基づいて、フロー♯1〜フロー♯nのトークン値の廃棄が有か否かを判定する(ステップS24)。ステップS24でYesと判定した場合、優先制御信号生成部200は、このフローの優先度を高優先度に設定する(ステップS25)。一方、ステップS24でNoと判定した場合、優先制御信号生成部200は、フローの優先度を現在の優先度に保持する(ステップS23)。なおフロー♯1〜フロー♯nの優先度の初期状態は低優先度に設定される。
【0054】
なお、本実施例では、優先制御信号生成部200は、フロー♯1〜フロー♯nのスキップ情報、トークン情報、パケット有無情報、およびトークン廃棄情報に基づいて、フロー♯1〜フロー♯nの優先度を設定しているが、これには限られない。すなわち、優先制御信号生成部200は、パケット監視部180で検出されたパケット有無情報およびトークン演算部160によるトークン廃棄情報に応じて、フロー♯1〜フロー♯nのパケット出力の優先度を高優先度または低優先度に設定することができる。より具体的には、優先制御信号生成部200は、パケット監視部180で検出されたパケットの格納が有りであり、かつトークン演算部160によるトークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定することができる。また、優先制御信号生成部200は、少なくともパケット監視部180で検出されたパケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定することができる。
【0055】
次に、図6,図7A,図7Bを用いて、実施例にかかるパケット転送装置100のトークン値の遷移について説明する。図6,図7A,図7Bは、実施例にかかるパケット転送装置100のトークン値の遷移モデルを示す図である。図6,図7A,図7Bはそれぞれ、フロー♯1〜フロー♯5のトークン値の遷移モデルを示している。図6,図7A,図7Bのフロー♯1〜フロー♯5において、横軸は時間を示し、縦軸は記憶部♯1〜記憶部♯5に記憶されているトークン値を示す。図6,図7A,図7Bにおいて、各フローのパケットバッファにパケットが格納されていない期間をαで示し、パケットバッファにパケットが格納されている期間をβで示す。また、図6と図7Aにおいて、複数のトークン追加周期を時間軸に沿って周期(A)〜周期(F)という。また、図7Bは図7Aのトークン値の遷移モデルの続きを示すものであるから、図7Bの複数のトークン追加周期を時間軸に沿って周期(F)〜周期(K)という。
【0056】
図6の周期(A)では、パケットバッファ120−1〜パケットバッファ120−4にパケットが格納されていないから、フロー♯1〜フロー♯4の優先度はそれぞれ低優先度に設定されているとする。一方、フロー♯5の優先度は高優先度に設定されているとする。図6の周期(A)ではパケットバッファ120−1〜パケットバッファ120−4にパケットが格納されていないので、フロー♯5のパケットバッファ♯5からパケットが出力される(図6の(a)参照)。
【0057】
続いて周期(B)に入ると記憶部140−1〜記憶部140−5に記憶されているトークン値に追加トークン値が加算される(図6の(b)参照)。なおフロー♯1〜フロー♯4のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期(B)では、フロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図6の(c)参照)。また、周期(B)においてパケットを出力した後、フロー♯5のトークン値は負になるから、フロー♯1のパケットバッファ120−1からパケットが出力される(図6の(d)参照)。
【0058】
続いて周期(C)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図6の(e)参照)。なおフロー♯1〜フロー♯4のトークン値はパケット有り時のMax Tokenに変更される。周期(C)ではパケットバッファ120−1〜パケットバッファ120−5にパケットが格納されているが、フロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図6の(f)参照)。また、周期(C)においてパケットを出力した後、フロー♯5のトークン値は負になるから、パケットバッファ120−2およびパケットバッファ120−3からパケットが出力される(図6の(g)参照)。図6の周期(D)以降の処理は図6の周期(B)および周期(C)と同様であるから説明を省略する。
【0059】
図6で示した本実施例のモデルと図11で示した従来技術のパケット転送装置のモデルとを比較すると、フロー#5の優先度を高優先度に設定しているから、フロー#5のトークン値の最大値が従来技術に比べて小さくなる。つまり、高優先度のフローは優先的にパケットが出力され、パケットが出力されるたびにトークン値が減算されるので、トークン値の最大値を抑制することができる。したがって、Max Tokenを比較的小さく設定したとしてもトークン値の廃棄は発生し難い。その結果、Max Tokenを抑制しつつ、トークン値の廃棄の発生を抑制することができる。
【0060】
次に、図7A,図7Bでは、フロー♯1〜フロー♯5の優先度がそれぞれ低優先度に設定されているとする。まず、図7Aの周期(A)ではフロー♯1〜フロー♯5がいずれも低優先度に設定されているから、フロー♯1〜フロー♯4の順に、パケットバッファ120−1〜パケットバッファ120−4からパケットが出力される(図5Aの(a)参照)。
【0061】
続いて周期(B)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Aの(b)参照)。なおフロー♯5のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期(B)ではフロー♯1〜フロー♯4のトークン値が負であるから、パケットバッファ120−1〜パケットバッファ120−4からはパケットは出力されず、パケットバッファ120−5からパケットが出力される(図7Aの(c)参照)。
【0062】
続いて周期(C)に入ると記憶部140−1〜記憶部140−5にトークン値が加算される(図7Aの(d)参照)。周期(C)においても、フロー♯1〜フロー♯4のトークン値が負であるから、パケットバッファ120−1〜パケットバッファ120−4からはパケットは出力されず、パケットバッファ120−5からパケットが出力される(図7Aの(e)参照)。
【0063】
続いて周期(D)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Aの(f)参照)。周期(D)では、フロー♯1〜フロー♯4のトークン値が0つまり正ではないから、パケットバッファ120−1〜パケットバッファ120−4からはパケットは出力されず、パケットバッファ120−5からパケットが出力される(図7Aの(g)参照)。
【0064】
続いて周期(E)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Aの(h)参照)。周期(E)では、フロー♯1〜フロー♯4の順に、パケットバッファ120−1〜パケットバッファ120−4からパケットが出力される(図7Aの(i)参照)。
【0065】
続いて周期(F)に入ると記憶部140−1〜記憶部140−5にトークン値が加算される(図7Aの(j)参照)。ここで、フロー♯5では、記憶部140−5に記憶されたトークン値がMax Tokenを超過するから、超過した分のトークン値は廃棄される(図7Aの(k)参照)。すると、フロー♯5は、パケットバッファ120−5にパケットが格納されており、かつトークン値の廃棄が発生するので、パケットの出力の優先度が高優先度に設定される(図7Aの(m)参照)。周期(F)では、フロー♯1〜フロー♯4のトークン値が負であるから、パケットバッファ120−1〜パケットバッファ120−4からはパケットは出力されず、パケットバッファ120−5からパケットが出力される(図7Bの(n)参照)。図7Bの周期(G)は図5Bの周期(F)と同様であるから、説明を省略する。また、図7Bの周期(H)は図7Aの周期(D)と同様であるから、説明を省略する。
【0066】
続いて周期(I)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Bの(o)参照)。周期(I)ではパケットバッファ120−1〜パケットバッファ120−5にパケットが格納されているが、フロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図7Bの(p)参照)。また、周期(I)においてパケットを出力した後、フロー♯5のトークン値は0つまり正ではなくなるから、パケットバッファ120−1、パケットバッファ120−2からパケットが出力される(図7Bの(q)参照)。
【0067】
続いて周期(J)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Bの(r)参照)。周期(J)ではフロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図7Bの(s)参照)。また、周期(J)においてパケットを出力した後、フロー♯5のトークン値は負になるから、パケットバッファ120−3からパケットが出力される(図7Bの(t)参照)。
【0068】
続いて周期(K)に入ると記憶部140−1〜記憶部140−5に記憶されたトークン値に追加トークン値が加算される(図7Bの(u)参照)。周期(K)ではフロー♯5だけが高優先度に設定されているから、フロー♯5のパケットバッファ120−5から優先的にパケットが出力される(図7Bの(v)参照)。また、周期(K)においてパケットを出力した後、フロー♯5のトークン値は負になるから、パケットバッファ120−4からパケットが出力される(図7Bの(w)参照)。
【0069】
以上のように、仮に、フロー♯5の優先度が低優先度の状態からトークン値が遷移したとしても、パケットバッファ120−5にパケットが格納されており、かつフロー♯5のトークン値がMax Tokenに達した時点でフロー♯5の優先度は高優先度に設定される。したがって、図7A,図7Bで示したパケット転送装置のモデルと図11で示した従来技術のパケット転送装置のモデルとを比較すると、フロー#5のトークン値の最大値が従来技術に比べて小さくなる。つまり、高優先度のフローは優先的にパケットが出力され、パケットが出力されるたびにトークン値が減算されるので、トークン値の最大値を抑制することができる。したがって、Max Tokenを比較的小さく設定したとしてもトークン値の廃棄は発生し難い。その結果、Max Tokenを抑制しつつ、トークン値の廃棄の発生を抑制することができる。
【0070】
また、本実施例によれば、パケットバッファ120−1〜パケットバッファ120−nにパケットが蓄積された後、所定の時間が経過するとパケットを廃棄するHead Dropのような制御を行う場合であっても、パケットの廃棄の発生を抑制することができる。つまり、従来技術では、パケットバッファ120−1〜パケットバッファ120−nにパケットが蓄積されているにもかかわらず、他のフローの処理待ちのためにパケットが廃棄されるおそれがある。この点、本実施例は、パケットバッファ120−1〜パケットバッファ120−nにパケットが格納されていれば、トークン値の廃棄が発生した時点で高優先度になり、優先してパケットが出力されるので、所定時間経過後のパケットの廃棄が生じ難い。
【0071】
ところで、トークン値の廃棄が発生しないようにMax Tokenを設定するためには、Max Token[byte]=フロー数[本]×最大パケット長[byte]/出力回線ワイヤレート[bps]×フローのSh_R[bps]とする。
【0072】
例えばあるパケット転送装置Xが、収容フロー数1024、最大パケット長10K[byte]、Sh_R設定粒度500K[bps]、Sh_Rのレンジ500K[bps]〜10G[bps]、トークン追加周期32u[s]という仕様となっているとする。このパケット転送装置Xにおいて、Sh_Rが500K[bps]の場合、トークン追加周期ごとに2[byte](=500K[bps]/8×32u[s])のトークン値が加算される。また、このパケット転送装置Xにおいて、Sh_Rが10Gbpsの場合、トークン追加周期ごとに40000byte(=10G[bps]/8×32u[s])のトークン値が加算される。
【0073】
また、Sh_Rが1[Mbps]のフローが1000本あり、Sh_Rが9G[bps] のフローが1本あり、トータルのSh_Rが10G[bps]である場合を例に挙げると、Sh_Rが1M[bps]のフローのMax Tokenは、1K[byte](= 1000[本]×10K[byte]/(10×10^9)[bps]×(1×10^6)[bps])となる。また、Sh_Rが9G[bps]のフローのMax Tokenは、9M[byte](=1000[本]×10K[byte]/(10×10^9)[bps]×(9×10^9)[bps])となる。
【0074】
これに対して、本実施例のパケット転送装置においては、46K[byte](=1回の追加トークン分(36K[byte])+最大パケット長(10K[byte]))のMax Tokenで、パケットの出力帯域の劣化を抑制することができる。ここで、低優先度のフローは従来技術に比べてトークン値が貯まりやすくなるが、Sh_Rが低ければ、トークン追加周期ごとのトークン値の追加は小さい。したがって、低優先度のフローであっても、従来技術のような例えば9M[byte]ものトークン値には達し難い。
【0075】
また、Sh_Rが1M[bps]のフローの最大待ち合わせ時間は、80[ms]となる。つまり、低優先(1M[bps])のフローには、32u[s]周期で1G[bps]分が割り当てられるので、単位時間あたりには4K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、80[ms]必要になる。ここで、待ち合わせ時間の間に追加するトークン値は10K[byte](=1M[bps]/8×80m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
【0076】
以下、本実施例のパケット転送装置についてフローの本数およびフローのSh_Rを変えたいくつかのケースを説明する。
【0077】
(ケース1)
Sh_Rが1M[bps]のフローが500本、Sh_Rが5M[bps]のフローが500本、Sh_Rが7G[bps]のフローが1本である場合を例に挙げる。Sh_Rが7G[bps]のフローのMax Tokenが38K[byte]であった場合、Sh_Rが7G[bps]のフローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが5M[bps]のフローの最大待ち合わせ時間は、26.7m[s] となる。つまり、低優先(1M[bps] と5M[bps])のフローには、32u[s]周期で3G[bps]分が割り当てられるので、単位時間あたり12K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、26.7[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン値は16.7K[byte](=5M[bps] /8 x 26.7m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
【0078】
(ケース2)
Sh_Rが1M[bps]フローが999本、Sh_Rが5M[bps]フローが1本、Sh_Rが9G[bps]フローが1本である場合を例に挙げる。Sh_Rが9G[bps]フローのMax Tokenが46K[byte]であった場合、Sh_Rが9G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが5M[bps]のフローの最大待ち合わせ時間は、80m[s]となる。つまり、低優先(1M[bps])のフローには、32u[s]周期で1G[bps]分が割り当てられるので、単位時間あたり4K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、80[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン値は50K[byte](=5M[bps] / 8 x 80m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
【0079】
(ケース3)
Sh_Rが1M[bps]フローが1000本、Sh_Rが1G[bps]フローが1本、Sh_Rが8G[bps]フローが1本である場合を例に挙げる。Sh_Rが8G[bps]フローのMax Tokenが42K[byte]であった場合、Sh_Rが8G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが1G[bps]のフローの最大待ち合わせ時間は、40m[s]となる。つまり、低優先(1M[bps]と1G[bps])のフローには、32u[s]周期で2G[bps]分が割り当てられるので、単位時間あたり8K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、40[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン量は5M[byte](=1G[bps]/8×40m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
【0080】
また、Sh_Rが1G[bps]フローのMax Tokenも42K[byte]であった場合、Sh_Rが1G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。そのときはSh_Rが8G[bps]フローのMax TokenはSh_Rが1G[bps]フローにより10K[byte]パケット出力時間を奪われてもトークン値の廃棄の発生を回避しなければならないため、さらに最大パケット長分を加えた52K[byte]のMax Tokenが必要となる。しかし、それでも従来技術においてパケットの出力帯域の劣化を抑制ために必要なMax Tokenと比較すると1/100以下のMax Tokenでパケットの出力帯域の劣化を抑制することができる。
【0081】
以上、本実施例のパケット転送装置100によれば、バケットバッファ120−1〜パケットバッファ120−nにパケットが格納されているフロー♯1〜フロー♯nでトークン値の廃棄が発生したら、そのフローのパケット出力の優先度は高優先度になる。パケット出力の優先度が高優先度になると、そのフローのパケットバッファからは優先的にパケットが出力される。パケットバッファからパケットが出力されると、パケットが出力されたフローに対応して記憶部に記憶されたトークン値から出力パケット長に応じたトークン値が減算される。したがって、本実施例のパケット転送装置100によれば、フローの数が増大したとしても、記憶部に記憶されるトークン値の最大値を抑制することができるので、Max Tokenを抑制し、かつトークン値の廃棄の発生を抑制することができる。
【0082】
上記の実施例に関し、さらに以下の付記を開示する。
【0083】
(付記1)パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファと、
前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を前記複数のフローに対応して記憶する記憶部と、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算するとともに、前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算し、さらに前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄するトークン演算部と、
前記複数のフローごとに前記パケットバッファにパケットが格納されているか否かを検出するパケット監視部と、
前記パケット監視部で検出された前記パケットの格納の有無および前記トークン演算部による前記トークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部と、
前記優先制御信号生成部で設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部と
を備えたことを特徴とするパケット転送装置。
【0084】
(付記2)前記優先制御信号生成部は、前記パケット監視部で検出された前記パケットの格納が有りであり、かつ前記トークン演算部による前記トークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定し、
少なくとも前記パケット監視部で検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
付記1に記載のパケット転送装置。
【0085】
(付記3)前記トークン演算部は、前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別し、
前記出力フロー選択部は、前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながらパケットを出力するフローを順次選択し、
前記優先制御信号生成部は、前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が正と判別されたフローのパケット出力の優先度を低優先度に設定し、
前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が負と判別されたフローのパケット出力の優先度を保持し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が無しであるフローの優先度を保持する
付記1に記載のパケット転送装置。
【0086】
(付記4)パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファにパケットが格納されているか否かを前記複数のフローごとに検出する監視ステップと、
前記複数のフローに対応して記憶部に記憶されており、前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値のそれぞれに、あらかじめ設定された周期で所定のトークン値を加算する加算ステップと、
前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する減算ステップと、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する廃棄ステップと、
前記監視ステップで検出されたパケットの格納の有無および前記廃棄ステップによるトークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先度設定ステップと、
前記優先度設定ステップで設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択ステップと
を備えたことを特徴とするパケット転送方法。
【0087】
(付記5)前記優先度設定ステップは、前記監視ステップで検出された前記パケットの格納が有りであり、かつ前記廃棄ステップによる前記トークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定し、
少なくとも前記監視ステップで検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
付記4に記載のパケット転送方法。
【0088】
(付記6)前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別する判別ステップを有し、
前記出力フロー選択ステップは、前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながらパケットを出力するフローを順次選択し、
前記優先度設定ステップは、前記出力フロー選択ステップでスキップされて、かつ前記判別ステップでトークン値が正と判別されたフローのパケット出力の優先度を低優先度に設定し、
前記出力フロー選択ステップでスキップされて、かつ前記判別ステップでトークン値が負と判別されたフローのパケット出力の優先度を保持し、
前記出力フロー選択ステップでスキップされず、かつ前記判別ステップでトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、
前記出力フロー選択ステップでスキップされず、かつ前記判別ステップでトークン値の廃棄が無しであるフローの優先度を保持する
付記4に記載のパケット転送方法。
【符号の説明】
【0089】
100 パケット転送装置
120 パケットバッファ
140 記憶部
160 トークン演算部
180 パケット監視部
200 優先制御信号生成部
220 出力フロー選択部
【特許請求の範囲】
【請求項1】
パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファと、
前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を前記複数のフローに対応して記憶する記憶部と、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算するとともに、前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算し、さらに前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄するトークン演算部と、
前記複数のフローごとに前記パケットバッファにパケットが格納されているか否かを検出するパケット監視部と、
前記パケット監視部で検出された前記パケットの格納の有無および前記トークン演算部による前記トークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部と、
前記優先制御信号生成部で設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部と
を備えたことを特徴とするパケット転送装置。
【請求項2】
前記優先制御信号生成部は、前記パケット監視部で検出された前記パケットの格納が有りであり、かつ前記トークン演算部による前記トークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定し、
少なくとも前記パケット監視部で検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
請求項1に記載のパケット転送装置。
【請求項3】
前記トークン演算部は、前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別し、
前記出力フロー選択部は、前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながらパケットを出力するフローを順次選択し、
前記優先制御信号生成部は、前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が正と判別されたフローのパケット出力の優先度を低優先度に設定し、
前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が負と判別されたフローのパケット出力の優先度を保持し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が無しであるフローの優先度を保持する
請求項1に記載のパケット転送装置。
【請求項4】
パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファにパケットが格納されているか否かを前記複数のフローごとに検出する監視ステップと、
前記複数のフローに対応して記憶部に記憶されており、前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値のそれぞれに、あらかじめ設定された周期で所定のトークン値を加算する加算ステップと、
前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する減算ステップと、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する廃棄ステップと、
前記監視ステップで検出されたパケットの格納の有無および前記廃棄ステップによるトークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先度設定ステップと、
前記優先度設定ステップで設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択ステップと
を備えたことを特徴とするパケット転送方法。
【請求項1】
パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファと、
前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を前記複数のフローに対応して記憶する記憶部と、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算するとともに、前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算し、さらに前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄するトークン演算部と、
前記複数のフローごとに前記パケットバッファにパケットが格納されているか否かを検出するパケット監視部と、
前記パケット監視部で検出された前記パケットの格納の有無および前記トークン演算部による前記トークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部と、
前記優先制御信号生成部で設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部と
を備えたことを特徴とするパケット転送装置。
【請求項2】
前記優先制御信号生成部は、前記パケット監視部で検出された前記パケットの格納が有りであり、かつ前記トークン演算部による前記トークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定し、
少なくとも前記パケット監視部で検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
請求項1に記載のパケット転送装置。
【請求項3】
前記トークン演算部は、前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別し、
前記出力フロー選択部は、前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながらパケットを出力するフローを順次選択し、
前記優先制御信号生成部は、前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が正と判別されたフローのパケット出力の優先度を低優先度に設定し、
前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が負と判別されたフローのパケット出力の優先度を保持し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が無しであるフローの優先度を保持する
請求項1に記載のパケット転送装置。
【請求項4】
パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファにパケットが格納されているか否かを前記複数のフローごとに検出する監視ステップと、
前記複数のフローに対応して記憶部に記憶されており、前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値のそれぞれに、あらかじめ設定された周期で所定のトークン値を加算する加算ステップと、
前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する減算ステップと、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する廃棄ステップと、
前記監視ステップで検出されたパケットの格納の有無および前記廃棄ステップによるトークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先度設定ステップと、
前記優先度設定ステップで設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択ステップと
を備えたことを特徴とするパケット転送方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7A】
【図7B】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7A】
【図7B】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2011−199521(P2011−199521A)
【公開日】平成23年10月6日(2011.10.6)
【国際特許分類】
【出願番号】特願2010−63206(P2010−63206)
【出願日】平成22年3月18日(2010.3.18)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
【公開日】平成23年10月6日(2011.10.6)
【国際特許分類】
【出願日】平成22年3月18日(2010.3.18)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
[ Back to top ]