(57)【特許請求の範囲】
【請求項１】
フレームのマーキング値が大きくなるほどフレームの廃棄優先度が高くなるように、入力フレームにマーキング閾値以下のマーキング値をマーキングするマーキング部と、
トークンを蓄積するトークンバケットと、
時間の経過に応じて、前記トークンバケットへトークンを生成するにあたり、トークン生成レートを設定するトークン生成部と、
入力フレームのフレームサイズに応じて、前記トークンバケットのトークンを消費するにあたり、入力フレームのフレームサイズがＬであり、前記マーキング閾値がｄであるときに、トークン消費量をＬ／（ｄ＋１）に設定するトークン消費部と、
前記トークンバケットのトークン量が前記トークンバケットのトークン最大量を上回るときに、前記トークンバケットのトークン量をトークン蓄積初期値に設定するとともに、前記マーキング閾値を減少させるマーキング閾値減少部と、
前記トークンバケットのトークン量が入力フレームのフレームサイズに応じたトークン量を下回るときに、前記トークンバケットのトークン量をトークン消費初期値に設定するとともに、前記マーキング閾値を増加させるマーキング閾値増加部と、
を備えることを特徴とするフレームマーキング回路。
【請求項２】
フレームのマーキング値が大きくなるほどフレームの廃棄優先度が高くなるように、入力フレームにマーキング閾値以下のマーキング値をマーキングするマーキング部と、
トークンを蓄積するトークンバケットと、
時間の経過に応じて、前記トークンバケットへトークンを生成するにあたり、前記マーキング閾値がｄであるときに、トークン生成レートをｄ＋１に比例する値に設定するトークン生成部と、
入力フレームのフレームサイズに応じて、前記トークンバケットのトークンを消費するにあたり、入力フレームのフレームサイズがＬであるときに、トークン消費量をＬに設定するトークン消費部と、
前記トークンバケットのトークン量が前記トークンバケットのトークン最大量を上回るときに、前記トークンバケットのトークン量をトークン蓄積初期値に設定するとともに、前記マーキング閾値を減少させるマーキング閾値減少部と、
前記トークンバケットのトークン量が入力フレームのフレームサイズに応じたトークン量を下回るときに、前記トークンバケットのトークン量をトークン消費初期値に設定するとともに、前記マーキング閾値を増加させるマーキング閾値増加部と、
を備えることを特徴とするフレームマーキング回路。
【請求項３】
前記マーキング閾値減少部は、前記トークン蓄積初期値を前記マーキング閾値に応じた値に設定することを特徴とする、請求項１又は２に記載のフレームマーキング回路。
【請求項４】
前記マーキング閾値増加部は、前記トークン消費初期値を前記マーキング閾値に応じた値に設定することを特徴とする、請求項１から３のいずれかに記載のフレームマーキング回路。
【請求項５】
前記マーキング部は、前記マーキング閾値以下の全マーキング値の出現頻度を等しくすることを特徴とする、請求項１から４のいずれかに記載のフレームマーキング回路。
【請求項６】
前記マーキング部は、前記マーキング閾値以下の全マーキング値の出現頻度を等しくし、前記全マーキング閾値に非線形変換を加えることを特徴とする、請求項１から４のいずれかに記載のフレームマーキング回路。
【請求項７】
前記マーキング部は、前記マーキング閾値以下の全マーキング値の出現頻度に重み付けすることを特徴とする、請求項１から４のいずれかに記載のフレームマーキング回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信装置におけるトラヒック制御技術に係り、ユーザトラヒックのバースト性を許容しながら、多様なレートに応じたきめ細かなマーキングを行う技術に関する。
【背景技術】
【０００２】
一般に、アクセスネットワークにおいて、データの転送制御を行う通信装置は、ユーザから転送されたトラヒックの集線を行い、各ユーザトラヒックを多重した上でコアネットワーク（通信事業者間を接続する大容量の基幹通信ネットワーク）に転送する。各通信装置は、ユーザトラヒックに関して、ＶＬＡＮＩＤ等のユーザ識別子を用いて送信元ユーザを識別する。ユーザ規模の大きい地域においては、大規模のユーザを収容可能とする装置を構築することで、少ない接続段数によりエリアをカバーすることが可能である。ユーザ規模の小さい地域においては、広範囲のエリアをカバーすることから、小規模な通信装置同士を多段接続することで集線を行い、コアネットワークに接続する構成が必要となる。
【０００３】
一般的に、スループットや遅延などの転送品質は、通信装置の多段接続数に応じて劣化することが知られている。このため、ユーザ規模におけるネットワーク構成の違いから、各通信装置に収容された各ユーザトラヒックに関して、スループットや遅延などの転送品質に不公平が生じる。これは、コアネットワークから遠い通信装置に収容されたユーザトラヒックほど、集線回数が増加し、それに伴いキュー（Ｑｕｅｕｅ）での転送順番待ち回数が増え、遅延が増大しスループットが減少するためである。こうした不公平性を解消するためには、転送品質の公平性を実現するためのトラヒック制御方法が必要となる。なお、キュー（Ｑｕｅｕｅ）とは待ち行列のことであり、ここでは、通信装置により受信され優先度およびユーザ識別子等によって振り分けられたフレームが、宛先通信ポートへの送信に備えて先入れ先出しのリスト構造で保持されたものである。
【０００４】
このような転送品質の公平性を実現するための第１の従来技術として、例えば非特許文献１に記載の２レート３カラーマーカーが存在する。この技術は、トラヒックレート、およびピークレート（ＰＩＲ）、最低保証レート（ＣＩＲ）、ピークバーストサイズ（ＰＢＳ）、最低保証バーストサイズ（ＣＢＳ）を用いてフレームへのマーキングを行う。トラヒックレートがＰＩＲを超過する場合は赤色に、ＰＩＲを超過しないかつＣＩＲを超過する場合は黄色に、それ以外の場合は緑色にマーキングを行う。その後、マーキングされた色に従ってフレームの廃棄を行う。この際、赤色のフレームが最も廃棄されやすく、緑色のフレームが最も廃棄されにくい。この技術により、レートの大きいトラヒックほどフレームが廃棄されやすくなり、スループットの公平性を向上させることができる。
【０００５】
転送品質の公平性を実現するための第２の従来技術として、非特許文献２に記載のＲａｉｎｂｏｗ  Ｆａｉｒ  Ｑｕｅｕｅｉｎｇ（ＲＦＱ）がある。この技術は、エッジルータにてフローごとのレートを推定し、レートが大きいフローのフレームほど多色にマーキングを行い、コアルータに転送し、コアルータにてバッファ閾値超過時に輻輳を検出し、レートが大きい場合に着色される色のフレームを廃棄する。輻輳継続時に廃棄する色を増やしていくことで、レートの大きいフローから順にフレームが廃棄され、スループットの公平化を図る。なお、この際、レートはｒｎｅｗ＝（１−ｅ−Ｔｋ／Ｋ）ｌｋ／Ｔｋ＋ｅ（−Ｔｋ／Ｋ）ｒｏｌｄによって求められる。ここで、更新前及び更新後のレートをそれぞれｒｎｅｗ及びｒｏｌｄ、ｋ番目のフレームの到着時間をｔｋ、Ｔｋ＝ｔｋ−ｔｋ−１、Ｋを定数、フレーム長をｌｋとし、ｌｋ／Ｔｋは現時点の実際のレートである。
【０００６】
これらの技術を用いることで、レートの大きいユーザトラヒックのフレームが廃棄され易いようマーキングを行い、ユーザトラヒック間の転送品質の公平性を改善することができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】ＲＦＣ２６９８  Ａ  Ｔｗｏ  Ｒａｔｅ  Ｔｈｒｅｅ  Ｃｏｌｏｒ  Ｍａｒｋｅｒ，ｐｐ．１−５．
【非特許文献２】Ｒａｉｎｂｏｗ  ｆａｉｒ  ｑｕｅｕｅｉｎｇ：ｆａｉｒ  ｂａｎｄｗｉｄｔｈ  ｓｈａｒｉｎｇ  ｗｉｔｈｏｕｔ  ｐｅｒ−ｆｌｏｗ  ｓｔａｔｅ，ＩＥＥＥ  ＩＮＦＯＣＯＭ  ２０００，ｖｏｌ．２，９２２−９３１．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、これらの技術では、バースト性を許容しながら多様なレートに応じたきめ細かなマーキングを行うことができず、トラヒック間の転送品質の公平性が低下する場合があった。
【０００９】
例えば、非特許文献１の技術においては、各ユーザトラヒックに対して、最低保証レートに満たないフレームの転送とピークレートを超過するフレームの廃棄を行うために、各フレームに対して２つの閾値を用いて３色の内のいずれかのマーキングを行う。よって、３段階のレート制御しか行うことができず、すなわち、４段階以上のきめ細かなレート制御による公平性の実現を行うことができない。また、マーキングの段階数を増やすために、同様の手法で単純にＮを自然数としＮレートＮ＋１カラーとした場合、トークンバケットがＮ個必要となり、装置が複雑化する問題がある。
【００１０】
また、非特許文献２の技術においては、各トラヒックのレートを時間減衰のパラメータを用いて計測するため、バースト性の高いトラヒックを許容できない場合がある。すなわち、更新前のレートｒｏｌｄの影響が時間経過により減衰するように、更新後のレートｒｎｅｗを算出することから、特定の時間範囲の間に一定量のフレームを許容し転送するバースト許容の概念と反し、バースト性の高いトラヒックのフレームほど廃棄されやすい色にマーキングされる。その結果、転送品質の公平性が低下しやすい。
【００１１】
本発明が解決しようとする問題点は、従来技術では、バースト性を許容しながら多様なレートに応じたきめ細かなマーキングを行うことができず、トラヒック間の転送品質の公平性の低下が発生する点である。例えば、２レート３カラーのマーキングでは、４段階以上のきめ細かなマーキングを行うことができず、マーキングの段階数を増やすため同様の手法でＮレートＮ＋１カラー化するためには、トークンバケットをＮ個保持することが必要で、装置が複雑化し、高コスト化する課題があった。また、ＲＦＱでは、ＮレートＮ＋１カラー化が可能である一方で、バースト性が高いトラヒックのフレームほど廃棄されやすい色にマーキングされ、公平性が低下する。
【００１２】
そこで、前記課題を解決するために、本発明は、ユーザトラヒックのバースト性を許容しながら、多様なレートに応じたきめ細かなマーキングを簡単に行うことを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、フレームのマーキング値が大きくなるほどフレームの廃棄優先度が高くなるように、入力フレームにマーキング閾値以下のマーキング値をマーキングする。トークンバケットを１個配置し、時間の経過に応じてトークンを生成し、入力フレームのフレームサイズに応じてトークンを消費する。
【００１４】
入力フレームの単位時間に入力するフレームサイズが小さいときには、トークンの生成がトークンの消費を上回るところ、トークンバケットが満杯になるたびに、トークンを除去するとともに、マーキング閾値を減少させて、入力フレームが廃棄されにくいようにした。
【００１５】
入力フレームの単位時間に入力するフレームサイズが大きいときには、トークンの消費がトークンの生成を上回るところ、トークンバケットが空になるたびに、トークンを補充するとともに、マーキング閾値を増加させて、入力フレームが廃棄されやすいようにした。
【００１６】
入力フレームの単位時間に入力するフレームサイズが大きいときに、トークン消費初期値の分だけトークンを補充し、トークン消費初期値に応じて許容するバースト量を設定することとした。バーストが入力される最中でも、マーキング閾値が徐々には大きくなってもある程度小さく設定されていれば、バーストは廃棄されにくくなる。
【００１７】
具体的には、本発明は、フレームのマーキング値が大きくなるほどフレームの廃棄優先度が高くなるように、入力フレームにマーキング閾値以下のマーキング値をマーキングするマーキング部と、トークンを蓄積するトークンバケットと、時間の経過に応じて、前記トークンバケットへトークンを生成するトークン生成部と、入力フレームのフレームサイズに応じて、前記トークンバケットのトークンを消費するトークン消費部と、前記トークンバケットのトークン量が前記トークンバケットのトークン最大量を上回るときに、前記トークンバケットのトークン量をトークン蓄積初期値に設定するとともに、前記マーキング閾値を減少させるマーキング閾値減少部と、前記トークンバケットのトークン量が入力フレームのフレームサイズに応じたトークン量を下回るときに、前記トークンバケットのトークン量をトークン消費初期値に設定するとともに、前記マーキング閾値を増加させるマーキング閾値増加部と、を備えることを特徴とするフレームマーキング回路である。
【００１８】
この構成によれば、ユーザトラヒックのバースト性を許容しながら、多様なレートに応じたきめ細かなマーキングを簡単に行うことができる。
【００１９】
また、本発明は、前記トークン生成部は、トークン生成レートを設定し、前記トークン消費部は、入力フレームのフレームサイズがＬであり、前記マーキング閾値がｄであるときに、トークン消費量をＬ／（ｄ＋１）に設定することを特徴とするフレームマーキング回路である。
【００２０】
この構成によれば、トークン生成レートを例えばｒに設定したときに、マーキング閾値ｄは、フレーム到着レートＲに対してｍｒ＜Ｒ≦（ｍ＋１）ｒとなる０以上の整数ｍに収束することができる。
【００２１】
また、本発明は、前記トークン生成部は、前記マーキング閾値がｄであるときに、トークン生成レートをｄ＋１に比例する値に設定し、前記トークン消費部は、入力フレームのフレームサイズがＬであるときに、トークン消費量をＬに設定することを特徴とするフレームマーキング回路である。
【００２２】
この構成によれば、比例係数を例えばｒに設定したときに、マーキング閾値ｄは、フレーム到着レートＲに対してｍｒ＜Ｒ≦（ｍ＋１）ｒとなる０以上の整数ｍに収束することができる。
【００２３】
また、本発明は、前記マーキング閾値減少部は、前記トークン蓄積初期値を前記マーキング閾値に応じた値に設定することを特徴とするフレームマーキング回路である。
【００２４】
この構成によれば、マーキング閾値に応じてトークン蓄積初期値を可変にするときに、トークン蓄積初期値を大きくするほど、マーキング閾値を速く減少させることができ、トークン蓄積初期値を小さくするほど、マーキング閾値を遅く減少させることができる。
【００２５】
また、本発明は、前記マーキング閾値増加部は、前記トークン消費初期値を前記マーキング閾値に応じた値に設定することを特徴とするフレームマーキング回路である。
【００２６】
この構成によれば、マーキング閾値に応じてトークン消費初期値を可変にするときに、トークン消費初期値を大きくするほど、許容するバースト量を増加させることができ、トークン消費初期値を小さくするほど、マーキング閾値を速く増加させることができる。
【００２７】
また、本発明は、前記マーキング部は、前記マーキング閾値以下の全マーキング値の出現頻度を等しくすることを特徴とするフレームマーキング回路である。
【００２８】
この構成によれば、入力フレームに容易にマーキングすることができる。
【００２９】
また、本発明は、前記マーキング部は、前記マーキング閾値以下の全マーキング値の出現頻度を等しくし、前記全マーキング閾値に非線形変換を加えることを特徴とするフレームマーキング回路である。
【００３０】
この構成によれば、入力フレームにマーキングするときに、廃棄優先度の高低に応じて、マーキングの粒度を可変とすることができる。
【００３１】
また、本発明は、前記マーキング部は、前記マーキング閾値以下の全マーキング値の出現頻度に重み付けすることを特徴とするフレームマーキング回路である。
【００３２】
この構成によれば、入力フレームにマーキングするときに、廃棄優先度の高低に応じて、マーキングの粒度を可変とすることができる。
【発明の効果】
【００３３】
本発明は、ユーザトラヒックのバースト性を許容しながら、多様なレートに応じたきめ細かなマーキングを簡単に行うことができる。
【図面の簡単な説明】
【００３４】
【図１】本発明のフレームマーキング回路の構成を示す図である。
【図２】実施形態１のトークン蓄積アルゴリズムを示す図である。
【図３】実施形態１のトークン消費アルゴリズムを示す図である。
【図４】実施形態２のトークン蓄積アルゴリズムを示す図である。
【図５】実施形態２のトークン消費アルゴリズムを示す図である。
【発明を実施するための形態】
【００３５】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施の例であり、本発明は以下の実施形態に制限されるものではない。
【００３６】
（実施形態１）
本発明のフレームマーキング回路の構成を図１に示す。フレームマーキング回路１は、不図示のフレーム振り分け機能を持つ装置あるいは装置の一部等から入力フレームＩｎを入力し、不図示の他の通信装置への転送待ちキュー等へと出力フレームＯｕｔを出力する。マーキングの際、Ｎを自然数として、ＮレートＮ＋１カラーでマーキングを行う。すなわち、異なるＮ個のレートを用いて、フレームをＮ＋１色にマーキングする。
【００３７】
不図示のコンピュータ等のユーザ端末から送信されるフレームは、ユーザを識別するための情報（ユーザ識別子）及び当該フレームを廃棄制御の対象とするか非廃棄制御の対象とするかを設定する優先度を示す情報が付与されている。フレームマーキング回路１に転送されるフレームは、不図示のフレーム振り分け機能を持つ装置あるいは装置の一部等により、ユーザ識別子または当該優先度、あるいは両方を用いて振り分けられる。
【００３８】
フレームマーキング回路１は、バッファ１１、マーキング部１２、トークンバケット１３、トークン生成部１４、トークン消費部１５及びマーキング閾値設定部１６から構成され、マーキング閾値設定部１６は、マーキング閾値減少部１７及びマーキング閾値増加部１８から構成される。バッファ１１は、入力フレームＩｎをフレームマーキング回路１の外部から入力格納し、出力フレームＯｕｔをＦＩＦＯ（先入れ先出し）の順番で、トークン消費部１５及びマーキング部１２を経てフレームマーキング回路１の外部に出力する。
【００３９】
マーキング部１２は、フレームのマーキング値が大きくなるほどフレームの廃棄優先度が高くなるように、入力フレームＩｎにマーキング閾値ｄ以下のマーキング値をマーキングする。トークンバケット１３は、トークンを蓄積する。マーキング部１２は、ＮレートＮ＋１カラーでマーキングを行うが、トークンバケット１３は、Ｎ個でなく１個である。
【００４０】
トークン生成部１４は、時間の経過に応じて、トークンバケット１３へトークンを生成する。トークン消費部１５は、入力フレームＩｎのフレームサイズＬに応じて、トークンバケット１３のトークンを消費する。入力フレームＩｎのフレームサイズＬが小さいときおよび入力フレームＩｎの到着間隔が長いときには、トークンの生成がトークンの消費を上回る。入力フレームＩｎのフレームサイズＬが大きいときおよび入力フレームＩｎの到着間隔が短いときには、トークンの消費がトークンの生成を上回る。
【００４１】
マーキング閾値設定部１６のうちマーキング閾値減少部１７は、トークンバケット１３のトークン量ｋがトークンバケット１３のトークン最大量Ｂを上回るときに、トークンバケット１３のトークン量ｋをトークン蓄積初期値ａｄに設定するとともに、マーキング閾値ｄを減少させる。つまり、入力フレームＩｎの単位時間に入力するフレームサイズＬが小さいときには、トークンの生成がトークンの消費を上回るところ、マーキング閾値減少部１７は、トークンバケット１３が満杯になるたびに、トークンを除去するとともに、マーキング閾値ｄを減少させて、入力フレームＩｎが廃棄されにくいようにする。
【００４２】
マーキング閾値設定部１６のうちマーキング閾値増加部１８は、トークンバケット１３のトークン量ｋが入力フレームＩｎのフレームサイズＬに応じたトークン量を下回るときに、トークンバケット１３のトークン量ｋをトークン消費初期値ｃｄに設定するとともに、マーキング閾値ｄを増加させる。つまり、入力フレームＩｎの単位時間に入力するフレームサイズＬが大きいときには、トークンの消費がトークンの生成を上回るところ、マーキング閾値増加部１８は、トークンバケット１３が空になるたびに、トークンを補充するとともに、マーキング閾値ｄを増加させて、入力フレームＩｎが廃棄されやすいようにする。
【００４３】
そして、入力フレームのフレームサイズＬが大きいときに、マーキング閾値増加部１８は、トークン消費初期値ｃｄの分だけトークンを補充し、トークン消費初期値ｃｄに応じて許容するバースト量を設定する。ここで、バーストは、特定の時間範囲の間に許容され転送される、一定量のフレームである。よって、バーストが入力される以前には、マーキング閾値ｄは小さく設定されているため、バーストが入力される最中でも、マーキング閾値ｄが徐々には大きくなってもある程度小さく設定されていれば、バーストは高い廃棄優先度を有する大きいマーキング値がマーキングされず廃棄されにくくなる。
【００４４】
これにより、ユーザトラヒックのバースト性を許容しながら、多様なレートに応じたきめ細かなマーキングを簡単に行うことができる。
【００４５】
実施形態１のトークン蓄積アルゴリズムを図２に示す。トークン生成部１４は、時間がΔｔだけ経過しているかどうかを判断する（ステップＳ１）。トークン生成部１４は、時間がΔｔだけ経過していると判断すれば（ステップＳ１においてＹＥＳ）、トークン量ｋとしてｒΔｔを生成する（ステップＳ２）。ここで、ｒはトークン生成レートである。トークン生成部１４は、時間がΔｔだけ経過していないと判断すれば（ステップＳ１においてＮＯ）、ステップＳ１の処理を繰り返し実行する。
【００４６】
マーキング閾値減少部１７は、トークン量ｋがトークン最大量Ｂを上回っているかどうかを判断する（ステップＳ３）。マーキング閾値減少部１７は、トークン量ｋがトークン最大量Ｂを上回っていると判断すれば（ステップＳ３においてＹＥＳ）、トークン量ｋをトークン蓄積初期値ａｄに設定し（ステップＳ４）、マーキング閾値ｄを１だけ減少させ（ステップＳ５）、トークン蓄積アルゴリズムを終了させる。ここで、トークン蓄積初期値ａｄは、０以上でありトークン最大量Ｂ以下である。マーキング閾値減少部１７は、トークン量ｋがトークン最大量Ｂを上回っていないと判断すれば（ステップＳ３においてＮＯ）、トークン蓄積アルゴリズムを終了させる。
【００４７】
実施形態１のトークン消費アルゴリズムを図３に示す。トークン消費部１５は、入力フレームＩｎのフレームサイズＬをバッファ１１から入力し（ステップＳ１１）、マーキング閾値ｄをマーキング閾値設定部１６から入力し（ステップＳ１２）、トークン量ｋとしてＬ／（ｄ＋１）を消費する（ステップＳ１３）。
【００４８】
マーキング閾値増加部１８は、消費後のトークン量ｋが０を下回っているかどうかを判断する（ステップＳ１４）。つまり、マーキング閾値増加部１８は、消費前のトークン量ｋがＬ／（ｄ＋１）を下回っているかどうかを判断する。マーキング閾値増加部１８は、消費後のトークン量ｋが０を下回っていると判断すれば（ステップＳ１４においてＹＥＳ）、トークン量ｋをトークン消費初期値ｃｄに設定し（ステップＳ１５）、マーキング閾値ｄを１だけ増加させ（ステップＳ１６）、トークン消費アルゴリズムを終了させる。ここで、トークン消費初期値ｃｄは、０以上でありトークン最大量Ｂ以下である。マーキング閾値増加部１８は、消費後のトークン量ｋが０を下回っていないと判断すれば（ステップＳ１４においてＮＯ）、トークン消費アルゴリズムを終了させる。
【００４９】
図２に示したトークン蓄積アルゴリズム及び図３に示したトークン消費アルゴリズムは、並行して繰り返し実行される。ここで、トークンの生成及びトークンの消費が釣り合っていれば、フレーム到着レートをＲとして、ｒΔｔ＝ＲΔｔ／（ｄ＋１）が成立する。そして、ｍを０以上の整数として、ｍｒ＜Ｒ≦（ｍ＋１）ｒが成立すれば、ｍ−１＜ｄ≦ｍが成立する。よって、マーキング閾値ｄは、フレーム到着レートＲに対してｍｒ＜Ｒ≦（ｍ＋１）ｒとなる０以上の整数ｍに収束することができる。
【００５０】
マーキング閾値減少部１７は、トークン蓄積初期値ａｄをマーキング閾値ｄに応じた値に設定してもよい。これにより、トークン蓄積初期値ａｄを大きくするほど、マーキング閾値ｄの更新まで時間を要さないため、マーキング閾値ｄを速く減少させることができる。そして、トークン蓄積初期値ａｄを小さくするほど、マーキング閾値ｄの更新まで時間を要するため、マーキング閾値ｄを遅く減少させることができる。
【００５１】
マーキング閾値増加部１８は、トークン消費初期値ｃｄをマーキング閾値ｄに応じた値に設定してもよい。これにより、トークン消費初期値ｃｄを大きくするほど、マーキング閾値ｄの更新まで消費量を多くするため、許容するバースト量を増加させることができる。そして、トークン消費初期値ｃｄを小さくするほど、マーキング閾値ｄの更新まで時間を要さないため、マーキング閾値を速く増加させることができる。
【００５２】
マーキング部１２は、マーキング閾値ｄ以下の全マーキング値ｐの出現頻度を等しくする。例えば、ｉをフレーム番号として、ｐｉ＝（ｐｉ−１＋１）ＭＯＤ（ｄ＋１）とする方法や、０以上ｄ以下の一様分布の乱数を生成して、ｐに代入する方法等がある。ｐを生成した後に、ｐがＮを超えている場合には、ｐにＮを代入する。
【００５３】
マーキング部１２は、マーキング値ｐに対応した値をマーキングする。マーキング位置としては、例えば入力フレームＩｎのヘッダ内のＤＳＣＰやＣＯＳ等を用いてもよいし、新たなフィールドを定義してもよいし、その際新たなビット列を挿入してもよい。
【００５４】
ｍ≦Ｎ−１であれば、ｐに対して０以上ｍ以下の値が等しい頻度で生成され、０以上ｍ以下の各値にマーキングされた出力フレームＯｕｔがレートｒで出力される。ｍ＞Ｎ−１であれば、０以上Ｎ−１以下の各値にマーキングされた出力フレームＯｕｔがレートｒで出力され、Ｎにマーキングされた出力フレームＯｕｔがレートＲ−Ｎｒで出力される。これにより、入力フレームＩｎに容易にマーキングすることができる。
【００５５】
（実施形態２）
実施形態２は、実施形態１と比較して、マーキング方法は同様であるが、トークン蓄積アルゴリズム及びトークン消費アルゴリズムが相違する。
【００５６】
実施形態２のトークン蓄積アルゴリズムを図４に示す。トークン生成部１４は、時間がΔｔだけ経過しているかどうかを判断する（ステップＳ２１）。トークン生成部１４は、時間がΔｔだけ経過していると判断すれば（ステップＳ２１においてＹＥＳ）、トークン量ｋとしてｒ（ｄ＋１）Δｔを生成する（ステップＳ２２）。ここで、ｒは比例係数である。トークン生成部１４は、時間がΔｔだけ経過していないと判断すれば（ステップＳ２１においてＮＯ）、ステップＳ２１の処理を繰り返し実行する。
【００５７】
マーキング閾値減少部１７は、トークン量ｋがトークン最大量Ｂを上回っているかどうかを判断する（ステップＳ２３）。マーキング閾値減少部１７は、トークン量ｋがトークン最大量Ｂを上回っていると判断すれば（ステップＳ２３においてＹＥＳ）、トークン量ｋをトークン蓄積初期値ａｄに設定し（ステップＳ２４）、マーキング閾値ｄを１だけ減少させ（ステップＳ２５）、トークン蓄積アルゴリズムを終了させる。ここで、トークン蓄積初期値ａｄは、０以上でありトークン最大量Ｂ以下である。マーキング閾値減少部１７は、トークン量ｋがトークン最大量Ｂを上回っていないと判断すれば（ステップＳ２３においてＮＯ）、トークン蓄積アルゴリズムを終了させる。
【００５８】
実施形態２のトークン消費アルゴリズムを図５に示す。トークン消費部１５は、入力フレームＩｎのフレームサイズＬをバッファ１１から入力し（ステップＳ３１）、トークン量ｋとしてＬを消費する（ステップＳ３２）。
【００５９】
マーキング閾値増加部１８は、消費後のトークン量ｋが０を下回っているかどうかを判断する（ステップＳ３３）。つまり、マーキング閾値増加部１８は、消費前のトークン量ｋがＬを下回っているかどうかを判断する。マーキング閾値増加部１８は、消費後のトークン量ｋが０を下回っていると判断すれば（ステップＳ３３においてＹＥＳ）、トークン量ｋをトークン消費初期値ｃｄに設定し（ステップＳ３４）、マーキング閾値ｄを１だけ増加させ（ステップＳ３５）、トークン消費アルゴリズムを終了させる。ここで、トークン消費初期値ｃｄは、０以上でありトークン最大量Ｂ以下である。マーキング閾値増加部１８は、消費後のトークン量ｋが０を下回っていないと判断すれば（ステップＳ３３においてＮＯ）、トークン消費アルゴリズムを終了させる。
【００６０】
図４に示したトークン蓄積アルゴリズム及び図５に示したトークン消費アルゴリズムは、並行して繰り返し実行される。ここで、トークンの生成及びトークンの消費が釣り合っていれば、フレーム到着レートをＲとして、ｒ（ｄ＋１）Δｔ＝ＲΔｔが成立する。そして、ｍを０以上の整数として、ｍｒ＜Ｒ≦（ｍ＋１）ｒが成立すれば、ｍ−１＜ｄ≦ｍが成立する。よって、マーキング閾値ｄは、フレーム到着レートＲに対してｍｒ＜Ｒ≦（ｍ＋１）ｒとなる０以上の整数ｍに収束することができる。
【００６１】
（実施形態３）
実施形態３は、実施形態１、２と比較して、トークン蓄積アルゴリズム及びトークン消費アルゴリズムは同様であるが、マーキング方法が相違する。
【００６２】
マーキング部１２は、マーキング閾値ｄ以下の全マーキング値ｐの出現頻度を等しくし、全マーキング閾値ｐに非線形変換を加える。例えば、０以上ｄ以下の各値の出現頻度が等しくなるようにｐを生成する。生成されたｐが０の場合、変換を行わない。生成されたｐが１以上の場合、ｃｅｉｌ（ｘ）をｘの天井関数として、ｐ＝ｃｅｉｌ（ｌｏｇ２ｐ）なる変換を行った後、ｐ＞Ｎの場合にのみｐにＮを代入する。この方法により、各値がマーキングされたフレームが出力されるレートを異ならせることが可能となる。
【００６３】
上記変換を行った場合には、変換前のｐが０のとき変換後のｐは０となり、変換前のｐが１より大きく２以下のとき変換後のｐは１となり、変換前のｐが３より大きく４以下のとき変換後のｐは２となり、変換前のｐが４より大きく８以下のとき変換後のｐは３となる。このように、フレームの到着レートが小さくマーキングされる値が小さい値に限定されるほど、粒度の細かいマーキングを行う一方で、フレームの到着レートが大きくマーキングされる値が大きい値に及ぶほど、粒度の粗いマーキングを行うことができる。
【００６４】
これにより、入力フレームＩｎにマーキングするときに、廃棄優先度の高低に応じて、マーキングの粒度を可変とすることができる。
【００６５】
（実施形態４）
実施形態４は、実施形態１、２と比較して、トークン蓄積アルゴリズム及びトークン消費アルゴリズムは同様であるが、マーキング方法が相違する。
【００６６】
マーキング部１２は、マーキング閾値ｄ以下の全マーキング値ｐの出現頻度に重み付けする。例えば、ｐ生成時の０，１，２，・・・，ｄの出現頻度の重みを、１：２：３：・・・：ｄ＋１と定める。ただし、生成されたｐがＮを超えている場合には、ｐにＮを代入する。この場合には、ｄ≦Ｎ−１のときにおいて、０，１，２，・・・，ｄにマーキングされたフレームの出力レートの比は、１：２：３：・・・：ｄ＋１となり、ｄ＞Ｎ−１のときにおいて、０，１，２，・・・，ｄ−１にマーキングされたフレームの出力レートの比は、１：２：３：・・・：ｄとなる。
【００６７】
これにより、入力フレームＩｎにマーキングするときに、廃棄優先度の高低に応じて、マーキングの粒度を可変とすることができる。
【産業上の利用可能性】
【００６８】
本発明に係るフレームマーキング回路は、ユーザトラヒックのバースト性を許容しながら、多様なレートに応じたきめ細かなマーキングを行うときに適用することができる。
【符号の説明】
【００６９】
１：フレームマーキング回路
１１：バッファ
１２：マーキング部
１３：トークンバケット
１４：トークン生成部
１５：トークン消費部
１６：マーキング閾値設定部
１７：マーキング閾値減少部
１８：マーキング閾値増加部
Ｉｎ：入力フレーム
Ｏｕｔ：出力フレーム
【図１】
0005432195.tif 000002
【図２】
0005432195.tif 000003
【図３】
0005432195.tif 000004
【図４】
0005432195.tif 000005
【図５】
0005432195.tif 000006