(57)【要約】  測定装置は、トークンのプロファイルと速度と最大数とを備える第１のトークンバケットを有する。この装置は、トークンのその固有のプロファイルと二つの関連速度と最大数とを備える別のトークンバケットを有する。動作時に、バケットがそのバケットについての最大トークン数未満を有する場合、装置はその速度で第１のトークンバケット内にトークンを追加し、第１のトークンバケットが一杯で他のトークンバケットがそうでない場合に、同一速度で他のトークンバケット内に所定数のトークンを追加する。加えて装置は、第２のトークンバケットに、それが一杯でない場合、トークンバケットに関連する第２の速度に従ってトークンを追加する。パケットを受け取ると、パケットが第１のマーキングを有し、第１のトークンバケットが十分な数のトークンを有する場合、パケットのマーキングを維持し、第１のバケット内のトークン数を減数し、これ以外の場合で、パケットが二つのマーキングの一方を有し、第２のトークンバケットが十分な数のトークンを有する場合、パケットの第２のマーキングを選択し、第２のトークンバケットを減数し、これ以外の場合で、パケットが二つのマーキングの一方以外のマーキングを有する場合、パケットのマーキングを二つのマーキングの一方以外として維持する。
2009522849.tif 000002
【特許請求の範囲】
【請求項１】
トークンバケットの着色行と分類列とを有し、各トークンバケットが最大数のトークンを持ち得る測定装置における各バケットのための方法であって、
前記バケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを所定速度で追加するステップと、
前記バケットがトークンで一杯である場合に、ａ）前記速度でトークンを廃棄するか、ｂ）同一行でかつ異なる分類列内の別のバケットにいくつかのトークンを追加するか、ｃ）異なる着色行でかつ同一列に属するバケット内にいくつかのトークンを追加するかを選択するステップとを含むことを特徴とする方法。
【請求項２】
列に対応する分類を有するデータパケットを受け取るときに、
前記列に属するバケット内に十分な数のトークンが存在する場合に、該バケット内のトークン数を減少させ、前記パケットに第１の色を関連付けるステップと、
上記以外の場合に、前記列に属する異なるバケット内のトークン数を減少させ、前記パケットに第２の色を関連付けるステップとをさらに含む請求項１記載の方法。
【請求項３】
前記異なるバケット内に十分な数のトークンが存在する場合に、前記異なるバケット内の前記トークン数を減少させ、前記パケットに第２の色を関連付け、
上記以外の場合に、前記パケットに第３の色を関連付ける請求項２記載の方法。
【請求項４】
前記パケットに前記第１の色を関連付けるステップは、前記パケットに緑色を関連付けるステップを含む請求項２記載の方法。
【請求項５】
前記パケットに前記第２の色を関連付けるステップは、前記パケットに黄色を関連付けるステップを含む請求項２記載の方法。
【請求項６】
前記パケットに前記第３の色を関連付けるステップは、前記パケットに赤色を関連付けるステップを含む請求項３記載の方法。
【請求項７】
前記トークンは異なる速度で各バケットに追加される請求項１記載の方法。
【請求項８】
前記十分な数のトークンは、前記データパケットのサイズを前記バケットのトークン数と比較することで判定される請求項２記載の方法。
【請求項９】
ひとつのバケット内の前記トークン数が前記パケットのサイズ以上である場合、十分な数のトークンが存在する請求項８記載の方法。
【請求項１０】
前記パケットの大きさはバイト単位で計測される請求項９記載の方法。
【請求項１１】
ひとつのバケットが最大数のトークンを有する場合、該バケットはトークンで一杯である請求項１記載の方法。
【請求項１２】
ひとつのバケット内のトークン数がしきい値以上である場合、十分な数のトークンが存在する請求項２記載の方法。
【請求項１３】
前記列は、トラフィッククラス、送信元アドレス、送信先アドレス、仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子（ＩＤ）、プロトコル、優先順位、差別化サービスコードポイント（ＤＳＣＰ）、又は用途種別のうちの１以上に少なくとも一部基づいて分類される請求項１記載の方法。
【請求項１４】
分類されたトークンバケット行を有し、各トークンバケットが最大数のトークンを有し得る測定装置における方法であって、
第１のバケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを所定の速度で追加するステップと、
前記第１のバケットがトークンで一杯となり、第２のバケットがトークンで一杯でない場合に、該第２のバケットにいくつかのトークンを追加するステップと、
前記第１のバケットに対応する分類を有するデータバケットを受け取るときに、
前記第１のバケット内に十分な数のトークンが存在する場合に、該第１のバケット内の前記トークン数を減少させ、前記パケットに第１の色を関連付けるステップと、
上記以外の場合に、前記パケットに第２の色を関連付けるステップとを含む、ことを特徴とする方法。
【請求項１５】
前記パケットに前記第１の色を関連付けるステップは、前記パケットに緑色を関連付けるステップを含む請求項１４記載の方法。
【請求項１６】
前記パケットに前記第２の色を関連付けるステップは、前記パケットに赤色を関連付けるステップを含む請求項１４記載の方法。
【請求項１７】
前記十分な数のトークンは、前記データパケットのサイズを前記バケット内の前記トークン数と比較することで判定される請求項１４記載の方法。
【請求項１８】
ひとつのバケット内の前記トークン数がパケットのサイズ以上である場合、十分な数のトークンが存在する請求項１７記載の方法。
【請求項１９】
前記パケットのサイズはバイト単位で計測される請求項１８記載の方法。
【請求項２０】
ひとつのバケットが最大数のトークンを有する場合、該バケットはトークンで一杯である請求項１４記載の方法。
【請求項２１】
ひとつのバケット内の前記トークン数がしきい値以上である場合、十分な数のトークンが存在する請求項１４記載の方法。
【請求項２２】
前記列は、トラフィッククラス、送信元アドレス、送信先アドレス、仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子（ＩＤ）、プロトコル、優先順位、差別化サービスコードポイント（ＤＳＣＰ）、又は用途種別のうちの１以上に少なくとも一部基づいて分類される請求項１４記載の方法。
【請求項２３】
最大数のトークンを有し得るトークンバケットを有する測定装置における方法であって、
前記バケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを所定速度で追加するステップと、
一つの分類を有するデータパケットを受け取るときに、
前記バケット内に十分な数のトークンが存在する場合に、前記パケットの前記分類に少なくとも一部基づいて、前記バケット内の前記トークン数を減少させ、前記パケットに第１の色を関連付けるステップと、
上記以外の場合に、前記パケットに第２の色を関連付けるステップとを含む、ことを特徴とする方法。
【請求項２４】
前記分類は、トラフィッククラス、送信元アドレス、送信先アドレス、仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子（ＩＤ）、プロトコル、優先順位、差別化サービスコードポイント（ＤＳＣＰ）、又は用途種別のうちの１以上に少なくとも一部基づいている請求項２３記載の方法。
【請求項２５】
トークンバケットの着色行と分類列とを有し、各トークンバケットが最大数のトークンを有し得る測定装置における方法であって、
第１の行の最後から２番目のバケットがトークンで一杯でない場合に、該最後から２番目のバケットにいくつかのトークンを所定速度で追加するステップと、
上記以外の場合で、前記第１の行の最後のバケットがトークンで一杯でない場合に、該最後のバケットにいくつかのトークンを追加するステップと、
上記以外の場合で、前記第２の行の第１のバケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを追加するステップと、
上記以外の場合で、前記第２の行の第２のバケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを追加するステップと、
列に対応する一つの分類を有するデータパケットを受け取るときに、
前記列に属する第１のバケット内に十分な数のトークンが存在する場合に、該第１のバケット内の前記トークン数を減少させ、前記パケットに第１の色を関連付けるステップと、
上記以外の場合で、前記列に属する第２のバケット内に十分な数のトークンが存在する場合に、該第２のバケット内の前記トークン数を減少させ、前記パケットに第２の色を関連付けるステップと、
上記以外の場合に、前記パケットに第３の色を関連付けるステップとを含む、ことを特徴とする方法。
【請求項２６】
前記パケットに前記第１の色を関連付けるステップは、前記パケットに緑色を関連付けるステップを含む請求項２５記載の方法。
【請求項２７】
前記パケットに前記第２の色を関連付けるステップは、前記パケットに黄色を関連付けるステップを含む請求項２５記載の方法。
【請求項２８】
前記パケットに前記第３の色を関連付けるステップは、前記パケットに赤色を関連付けるステップを含む請求項２５記載の方法。
【請求項２９】
前記十分な数のトークンは、前記データパケットのサイズを前記バケット内のトークン数と比較することにより判定される請求項２５記載の方法。
【請求項３０】
ひとつのバケット内の前記トークン数が前記パケットのサイズ以上である場合、十分な数のトークンが存在する請求項２９記載の方法。
【請求項３１】
前記パケットのサイズはバイト単位で計測される請求項３０記載の方法。
【請求項３２】
前記バケットが最大数のトークンを有する場合、該バケットはトークンで一杯である請求項２５記載の方法。
【請求項３３】
ひとつのバケット内の前記トークンの数がしきい値以上である場合、十分な数のトークンが存在する請求項２５記載の方法。
【請求項３４】
前記列は、トラフィッククラス、送信元アドレス、送信先アドレス、仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子（ＩＤ）、プロトコル、優先順位、差別化サービスコードポイント（ＤＳＣＰ）、又は用途種別のうちの１以上に少なくとも一部基づいて分類される請求項２５記載の方法。
【請求項３５】
前記第２の行の前記第１のバケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを第２の速度で追加し、
上記以外の場合で、前記第２の行の前記第２のバケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを追加するステップをさらに含む請求項２５記載の方法。
【請求項３６】
トークンバケットの着色行と分類列とを有し、各トークンバケットが最大数のトークンを有し得る測定装置における方法であって、
第１の行の最後から２番目のバケットがトークンで一杯でない場合に、該最後から２番目のバケットにいくつかのトークンを所定速度で追加するステップと、
上記以外の場合で、前記第１の行の最後のバケットがトークンで一杯でない場合に、該最後のバケットにいくつかのトークンを追加するステップと、
上記以外の場合に、
トークンを所定速度で廃棄するステップと、
前記第２の行の前記第１のバケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを第２の速度で追加するステップと、
上記以外の場合で、前記第２の行の前記第２のバケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを追加するステップと、
一つの列に対応する分類を有するデータパケットを受け取るときに、
前記列に属する第１のバケット内に十分な数のトークンが存在する場合に、該第１のバケット内の前記トークン数を減少させ、前記パケットに第１の色を関連付けるステップと、
上記以外の場合で、前記列に属する第２のバケット内に十分な数のトークンが存在する場合に、該第２のバケット内の前記トークン数を減少させ、前記パケットに第２の色を関連付けるステップと、
上記以外の場合に、前記パケットに第３の色を関連付けるステップとを含む、ことを特徴とする方法。
【請求項３７】
前記パケットに前記第１の色を関連付けるステップは、前記パケットに緑色を関連付けるステップを含む請求項３６記載の方法。
【請求項３８】
前記パケットに前記第２の色を関連付けるステップは、前記パケットに黄色を関連付けるステップを含む請求項３６記載の方法。
【請求項３９】
前記パケットに前記第３の色を関連付けるステップは、前記パケットに赤色を関連付けるステップを含む請求項３６記載の方法。
【請求項４０】
前記十分な数のトークンは、前記データパケットのサイズを前記バケット内の前記トークン数と比較することにより判定される請求項３６記載の方法。
【請求項４１】
ひとつのバケット内の前記トークン数が前記パケットのサイズ以上である場合、十分な数のトークンが存在する請求項４０記載の方法。
【請求項４２】
前記パケットのサイズはバイト単位で計測される請求項４１記載の方法。
【請求項４３】
ひとつのバケットが最大数のトークンを有する場合、該バケットはトークンで一杯である請求項３６記載の方法。
【請求項４４】
ひとつのバケット内の前記トークン数がしきい値以上である場合、十分な数のトークンが存在する請求項３６記載の方法。
【請求項４５】
前記列は、トラフィッククラス、送信元アドレス、送信先アドレス、仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子（ＩＤ）、プロトコル、優先順位、差別化サービスコードポイント（ＤＳＣＰ）、又は用途種別のうちの１以上に少なくとも一部基づいて分類される請求項３６記載の方法。
【請求項４６】
トークンバケットの着色行と分類列とを有し、各トークンバケットが最大数のトークンを有し得る測定装置における各バケットのための方法であって、
前記バケットがトークンで一杯でない場合に、該バケットにいくつかのトークンを所定速度で追加するステップと、
上記以外の場合、前記行内に少なくとも一つの残留バケットが存在する場合で、前記行内の第２のバケットがトークンで一杯でない場合に、前記行内の前記第２のバケットにいくつかのトークンを追加するステップと、
上記以外の場合で、前記第２の行内の第１のバケットがトークンで一杯でない場合に、前記第２の行内の前記第１のバケットにいくつかのトークンを追加するステップと、
上記以外の場合で、前記第２の行内の第２のバケットがトークンで一杯でない場合に、前記第２の行内の前記第２のバケットにいくつかのトークンを追加するステップと、
一つの列に対応する分類を有するデータパケットを受け取るときに、
前記列に属するバケット内に十分な数のトークンが存在する場合に、該バケット内の前記トークン数を減少させ、前記パケットに第１の色を関連付けるステップと、
上記以外の場合で、前記列に属する他のバケット内に十分な数のトークンが存在する場合に、該他のバケット内の前記トークン数を減少させ、前記パケットに第２の色を関連付けるステップと、
上記以外の場合に、前記パケットに第３の色を関連付けるステップとを含む、ことを特徴とする方法。
【請求項４７】
前記パケットに前記第１の色を関連付けるステップは、前記パケットに緑色を関連付けるステップを含む請求項４６記載の方法。
【請求項４８】
前記パケットに前記第２の色を関連付けるステップは、前記パケットに黄色を関連付けるステップを含む請求項４６記載の方法。
【請求項４９】
前記パケットに前記第３の色を関連付けるステップは、前記パケットに赤色を関連付けるステップを含む請求項４６記載の方法。
【請求項５０】
前記十分な数のトークンは、前記データパケットのサイズを前記バケット内のトークン数と比較することにより判定される請求項４６記載の方法。
【請求項５１】
ひとつのバケット内の前記トークン数が前記パケットのサイズ以上である場合、十分な数のトークンが存在する請求項５０記載の方法。
【請求項５２】
前記パケットサイズはバイト単位で計測される請求項５１記載の方法。
【請求項５３】
前記バケットが最大数のトークンを有する場合、該バケットはトークンで一杯である請求項４６記載の方法。
【請求項５４】
ひとつのバケット内の前記トークン数が所定のしきい値以上である場合、十分な数のトークンが存在する請求項４６記載の方法。
【請求項５５】
前記列は、トラフィッククラス、送信元アドレス、送信先アドレス、仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子（ＩＤ）、プロトコル、優先順位、差別化サービスコードポイント（ＤＳＣＰ）、又は用途種別のうちの１以上に少なくとも一部基づいて分類される請求項４６記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にデータ通信分野に関する。特に、本発明は受信データストリームを測定し、例えばパケット速度、パケット長、データストリーム中のパケットの到着時間等の一つの因子又は１以上の因子の組み合わせに基づいて、データストリーム内でパケットに異なるマーキングを施す装置に関する。例えばパケットを転送するか廃棄するかに関する保証レベルを示すために、パケットがマーキングされ、再マーキングされる。
【背景技術】
【０００２】
速度カラーマーカーが、トラフィックストリーム内のパケットを測定し、トラフィックパラメータに基づいてパケットにマーキングする。この種の測定とマーキングを用い、通信ネットワーク内で通信品質又は輻輳制御等のサービスが可能となる。二つの類似のカラー速度マーカーが、インターネット・エンジニアリング・タスク・フォース（ＩＥＴＦ；インターネット技術標準化委員会）インフォメーショナル・リクエスト・フォア・コメンツ（ＲＦＣ；インターネットプロトコル関係仕様コメント文書群）２６９７，２６９８に文書化されている。非特許文献１と非特許文献２とを参照されたい。
【０００３】
基準となるＲＦＣは、インターネットプロトコル（ＩＰ）準拠パケット交換インターネットワークの文脈において、カラー速度マーカーのアルゴリズムを説明している。しかしながら、この種のアルゴリズムは、セル交換ネットワークにも実装することができる。各カラーマーカーは、トラフィックストリーム、例えばＩＰパケットストリームを測定し、そのパケットを緑色、黄色、赤色のうちの一つでマーキングする。
【０００４】
ＲＦＣ２６９７に記載された単速度３色マーカー（ｓｒＴＣＭ：単速度３色マーカー）は、トラフィック速度、認定情報速度（ＣＩＲ）、及び二つの異なるバーストサイズ、認定バーストサイズ（ＣＢＳ）、及び超過バーストサイズ（ＥＢＳ）に基づいてＩＰストリーム内のパケットをマーキングする。要するに、パケットはそれがＣＢＳを超過しない場合は緑色に、ＣＢＳを超過するがＥＢＳを超過しない場合は黄色に、またＣＢＳもＥＢＳも共に超過する場合は赤色にマーキングされる。ｓｒＴＣＭは、トラフィックに関連する色を判定する上で、それがトラフィックのバーストの長さを用いるもののピーク速度を使用しない点に限定される。サービス又はサービスレベルは、そこでその色に基づいてトラフィックに供給される。
【０００５】
ＲＦＣ２６９８に記載された２速度３色マーカー（ｔｒＴＣＭ）は、二つの異なるトラフィック速度、ピーク情報速度（ＰＩＲ）、及び認定情報速度（ＣＩＲ）、及び対応バーストサイズの認定バーストサイズ（ＣＢＳ）とピーク情報バースト（ＰＢＳ）に基づいてＩＰストリーム内のパケットにマーキングする。ｔｒＴＣＭによれば、パケットはＰＩＲを超過する場合赤色にマーキングされ、パケットがＰＩＲを超過しない場合、それがＣＩＲを超過するか又はＣＩＲを超過しないかに応じて黄色又は緑色にマーキングされる。二つの速度、すなわちピークトラフィック速度（又は、単純にはピーク速度）と認定速度とを用いることで、ｔｒＴＣＭは、認定速度トラフィックとは別のピーク速度トラフィックを監視することができる。
【０００６】
ｓｒＴＣＭとｔｒＴＣＭは両方とも、トラフィックストリーム内の各パケットを測定し、パケットを着色するマーカーにそのパケットを転送又は送付する測定装置を意図している。両アルゴリズムは二つのモード、すなわち、測定器がトラフィックストリームを非着色であるかのように受信する色盲モードと、受信トラフィックストリーム内のパケットを既に例えば緑色、黄色、赤色のうちの一つで着色済み（「事前着色済み」）とする色知覚モードのうちの一方で動作する。事前着色工程と、測定器がパケット色を検出又は特定する詳細は、実装ごとに固有であり、本発明だけでなくＲＦＣもまた範囲外にある。
【０００７】
ＲＦＣは、測定結果に基づきパケットを再着色するマーカーを開示しており、一例として、パーホップ・ビヘイビヤー（ＰＨＢ；ホップ単位挙動）専用態様におけるパケットのＤｉｆｆＳｅｒｖ（ＤＳ）フィールドにおいてコードポイントとして色の符号化を提供しており、さらなる情報についてＩＥＴＦ  ＲＦＣ２４７４に言及している。非特許文献３を参照されたい。この色は、ＲＦＣ２５９７に従い、パケットの棄却順位として符号化することができる。非特許文献４を、参照されたい。
【０００８】
両方のカラーマーカーは、例えばトラフィックストリーム内のパケットにマーキングし、これによりパケットが緑色か黄色か赤色であるかに基づいて異なるレベルの保証がパケットに与えられるようにする。低下してゆくサービスレベルが、緑色パケット、続いて黄色パケット、さらに赤色パケットに与えられる。例えば、緑色パケットは配送を保証でき、又は少なくとも廃棄や棄却される可能性が低い状態で転送され、一方で黄色パケットはベストエフォート準拠で転送でき、赤色パケットは棄却される。
【０００９】
ＲＦＣには、パケット化データからなる単一ストリームのアドミッション速度、バーストサイズ、棄却順位を制御する方法として３色マーカーが記述されている。それらは、データを異なる優先順位の複数ストリームに分割したときに、これらの特性を制御する仕方に対処していない。
【００１０】
複数優先順位レベルを有するデータストリーム用にこれらのマーカーを用いる従来の手法は、以下を含む。
ａ．各優先順位ごとに単一のマーカーを用い、各優先順位ごとにデータを個別ストリームに分割する、又は
ｂ．単一マーカーを用い、異なる全ての優先順位の全データを単一のデータストリームとして処理する、又は
ｃ．先ずストリームを分割し、優先順位ごとにマーカーを用い、続いてストリームを再結合し、それらを単一の第２レベルマーカーを用いて測定することで、階層的様式にて上記二つの手法を組み合わせる。
【非特許文献１】Ｈｅｉｎａｎｅｎ，  Ｊ．、Ｒ．  Ｇｕｅｒｉｎ著、「Ａ  Ｓｉｎｇｌｅ  Ｒａｔｅ  Ｔｈｒｅｅ  Ｃｏｌｏｒ  Ｍａｒｋｅｒ（単速度３色マーカー）」、ＲＦＣ２６９７、１９９９年９月
【非特許文献２】Ｈｅｉｎａｎｅｎ，  Ｊ．、Ｒ．  Ｇｕｅｒｉｎ著、「Ａ  Ｔｗｏ  Ｒａｔｅ  Ｔｈｒｅｅ  Ｃｏｌｏｒ  Ｍａｒｋｅｒ（２速度３色マーカー）」、ＲＦＣ２６９８、１９９９年９月
【非特許文献３】Ｎｉｃｈｏｌｓ，  Ｋ．、Ｂｌａｋｅ，  Ｓ．、Ｂａｋｅｒ，  Ｆ．、Ｄ．  Ｂｌａｃｋ著、「Ｄｅｆｉｎｉｔｉｏｎ  ｏｆ  ｔｈｅ  Ｄｉｆｆｅｒｅｎｔｉａｔｅｄ  Ｓｅｒｖｉｃｅｓ  Ｆｉｅｌｄ  （ＤＳ  Ｆｉｅｌｄ）  ｉｎ  ｔｈｅ  ＩＰｖ４  ａｎｄ  ＩＰｖ６  Ｈｅａｄｅｒｓ（ＩＰｖ４及びＩＰｖ６ヘッダーにおける差別化サービスフィールド（ＤＳフィールド）の定義）」、ＲＦＣ２４７４、１９９８年１２月
【非特許文献４】Ｂｌａｋｅ，  Ｓ．、Ｂｌａｃｋ，  Ｄ．、Ｃａｒｌｓｏｎ，  Ｍ．、Ｄａｖｉｅｓ，  Ｅ．、Ｗａｎｇ，  Ｚ．、Ｗ．  Ｗｅｉｓｓ著、「Ａｎ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｄｉｆｆｅｒｅｎｔｉａｔｅｄ  Ｓｅｒｖｉｃｅｓ（差別化サービス用アーキテクチャ）」、ＲＦＣ２４７５、１９９８年１２月
【発明の開示】
【発明が解決しようとする課題】
【００１１】
各手法の利点と欠点は、その目的が複合ストリームの総合速度又は各優先順位ストリームの個別速度を制御することか否かに依存する。いずれの場合も、より優先順位の高いトラフィックに対し優先的処置を与えることが望ましい。例えば、最高位優先順位のデータストリームの入来速度とバースト特性が、そのデータストリームに使用するマーカーの認定速度内及び認定バーストサイズ内にある限り、低位優先順位のデータがどの程度存在するかにかかわらずその最高位のデータパケット全てを緑色にマーキングする。一部事例では、上記第１の手法が要件に合致する場合に、各優先順位ストリームの速度とバーストとを独立して制御することは容認可能である。この手法の欠点は、より高位の優先順位トラフィックが欠如した際に、より低位の優先順位トラフィックがより高位の優先順位トラフィックに対し留保された帯域を使用できない点にある。このことは、損失帯域と不十分なネットワーク利用という結果になる。
【００１２】
第２の手法は、優先順位を事実上無視することで全ての優先順位の総合を制御する。これにより、より高位の優先順位のトラフィックが欠如する際により低位の優先順位のトラフィックがフル速度を使い切ることができるが、複数優先順位のパケットが相互混合されているときは、より高位の優先順位トラフィックに対し優先的処置を提供できない。
【００１３】
第３の手法中の階層構造は、より高位の優先順位のトラフィックに対する所与の優先的処置と、その一方でより高位の優先順位のトラフィック欠如時に、より低位の優先順位のトラフィックが全帯域を使い尽せるようにする両方の目的に一部合致する構成とすることができる。第１のレベルにある全ての優先順位に関する認定速度バケットの速度とバーストサイズの和が、第２のレベルにある認定速度バケットの速度とバーストサイズに等しい場合、そのときはより高位の優先順位トラフィックに関する優先的処置を（認定速度とバーストサイズ仕様内で）保証することができる。第１のレベルにある全ての優先順位に関する超過速度バケットの速度とバーストサイズの和は、第２のレベルにある超過速度バケットの速度とバーストサイズを上回るよう構成される。これにより、任意の優先順位トラフィックが超過帯域を使い尽すことができる。その複合効果は、より高位の優先順位のトラフィックの優先的処置がその優先順位に関する認定速度内及びバーストサイズ内で保証される点にあるが、より下位の優先順位のトラフィックが超過であるとマーキングされた場合、より高位の優先順位トラフィックが使用していない全ての帯域は、より低位の優先順位のトラフィックしか使い尽せない。重要なことに、この手法は、単速度２色マーカーと考えたときに両方の目的に応えることが出来ない。
【課題を解決するための手段】
【００１４】
より高位の優先順位のトラフィックに対する優先的処置を保証する一方、低位優先順位のトラフィックがより高位の優先順位のトラフィックが使い尽せないあらゆる帯域を使用する複数優先順位用の速度カラーマーカーアルゴリズムを、開示する。このアルゴリズムは、より低位の優先順位のトラフィックが必ずしも常に過剰トラフィックとしてマーキングされるとは限らないとするものである。本発明の一実施態様は、（超過情報速度ソースをゼロに設定することで）単速度３色マーカーとして、又は（全ての優先順位に対する超過バケットサイズをゼロに設定することで）単速度２色マーカーとして動作する構成にできるデュアル速度３色マーカーである。しかしながら、本発明は、複数速度及び複数色のためのマーカーを一般に包含するものである。
【発明を実施するための最良の形態】
【００１５】
本発明は、添付図面の図において、限定の意図のない例示により説明される。
【００１６】
本発明は、複数優先順位向けマルチ速度マルチカラーマーカー又は単純に速度カラーマーカーである。複数優先順位向けデュアル速度３色マーカーは、各優先順位ごとに認定バケットと各優先順位ごとに超過バケットとを有するトークンバケット配列として特徴付けることができる。認定速度ソースは、最高位の優先順位向け認定バケット内にトークンを寄託する。そのバケットが一杯である場合、トークンは次の最低位優先順位向け認定バケット内に寄託され、以下同様とされる。最低位優先順位向け認定バケットが一杯であれば、トークンは廃棄され（「離脱」モード）、又は最高位優先順位向け超過バケット内に寄託される（「結合」モード）。超過速度ソースも、同様に、最高位優先順位向け超過バケット内にトークンを寄託する。このバケットが一杯である場合、そこに寄託された筈の全てのトークンが次の低位優先順位向け超過バケット内に寄託され、以下同様とされる。最低位優先順位向け超過バケットが一杯になると、そこに寄託し得た全てのトークンが廃棄される。バケットの初期状態は空か一杯であるが、システムをオンしたときに直ちにパケットのバーストが到着する可能性に対応すべく従来は初期状態を一杯としていた。本願明細書に使用する用語「一杯」は、必ずしも「一杯な」バケットが満杯であることを示唆するものではない。満杯であることに加え、「一杯な」バケットは大方一杯か又はほぼ一杯とすることができる。換言すれば、バケットが「一杯」であると見なす最大数のトークンを厳密に有することは要件ではない。
【００１７】
バケット内にトークンを寄託する速度は、幾つかの方法で達成することができる。一実施形態では、バケットは所定の「速度」を達成するのに連続様式にて一度に１個のトークンを受け取る。別の実施形態では、バケットは固定された周期間隔で同時に複数のトークンを受け取り、所定の「速度」を達成する。さらに別の実施形態では、バケットは所定の「速度」が所定の時間期間にわたり達成されるようパケット到着に基づいていくつかのトークンを受け取る。
【００１８】
先行技術（ＲＦＣ２６９７とＭＥＦ１０）は、パケット長を認定及び／又は超過バケット内のトークン数と比較し、パケットをしかるべくマーキングし、マーキング判定に基づいて適当なバケットからのトークンを使い尽すことで、それらが到着した際にパケットを測定しマーキングするアルゴリズムを説明するものである。アルゴリズムは、色盲動作モードと色知覚動作モードの両方を含む。本発明はアルゴリズムを修正し、これにより各パケットに指定された優先順位を持たせ、対応する優先順位向け認定バケット及び／又は超過バケット内のトークン数がしきい値と比較できるようにしてある。
【００１９】
図１を参照して、本発明の一実施形態１００をここで説明する。実施形態１００は、単速度２色マーカーである。本実施形態では、超過情報速度はゼロに設定してあり、全ての優先順位に対する超過バケットサイズはゼロに設定してある。かくして、単一行のバケット１１０，１２０，１３０，１４０が存在し、各バケットは異なる優先順位を有する。例示実施形態は４個の優先順位を有するが、一実施形態では２以上の優先実施形態を持たせることができることを理解されたい。バケット１１０は最高位の優先順位（優先順位３）を有し、一方でバケット１４０は最低位の優先順位（優先順位０）を有する。また、説明目的に合わせ、行中の各バケットは緑色バケットとして割り当ててある。
【００２０】
単一の認定速度ソース１０１が、全ての優先順位のパケットに対して最大総合速度を制御する。認定速度までの最高位の優先順位（優先順位３）からなる全ての到着パケットは緑色にマーキングされる。認定速度を超過する優先順位３のあらゆる到着パケットは、優先順位３の緑色バケット１１０内に蓄えられたトークンを消尽し、後続パケットは赤色にマーキングされることになる。優先順位３のパケットが総合認定速度１０１以上の速度にて到着する限り、到着する全てのより低位の優先順位のパケットはパケット優先順位に対応するバケット内のトークンを消尽し、後続パケットは赤色にマーキングされる。例えば、優先順位３のパケットが１０１以上の速度で到着すると、そのときは到着する優先順位２のパケットはバケット１２０内のトークン（優先順位２）を消尽することになり、後続の優先順位２のパケットは赤色にマーキングされる。続いて、到着する優先順位１と優先順位０のパケットがそれぞれ各バケット１３０，１４０内のトークンを消尽する。
【００２１】
優先順位３のパケットが総合認定速度１０１未満の速度で到着する場合、バケット１１０が満され、後続のトークンはバケット１２０内に流入する。これによって、優先順位２の到着パケットが認定総合速度１０１から優先順位３のトラフィックの実際の速度を減じた値まで緑色にマーキングされる。優先順位２のパケットが総合認定速度１０１から優先順位３の速度を減じた速度未満で到着する場合、バケット１２０も満され、後続のトークンがバケット１３０内に流入する。バケット１３０がトークンで満された場合その時は、そこで後続のトークンがバケット１４０内に流入することになる。バケット１４０が一旦トークンで満されると、後続のトークンは廃棄される。
【００２２】
別の実施形態では、バケット１１０が全ての優先順位（すなわち優先順位０〜３）のパケットに対してトークンを蓄積する。（優先順位以外の分類を、トラフィッククラス、送信元アドレス、送信先アドレス、送信元／送信先複合アドレス、仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子（ＩＤ）、プロトコル、又は用途種などを含む、パケットを識別するのに使用し得ることに留意されたい。）（トークンの）しきい値は各優先順位ごとに割り当てられ、バケット１１０は認定速度１０１にてトークンを受け入れ続ける。しかし本実施形態では、一旦バケット１１０がトークンで一杯になると、トークンは廃棄される。パケットが到着すると、バケット１００内のトークン数はパケットの優先順位に関するトークンのしきい値数と比較される。特定のパケットについてしきい値を満足すると、パケットは緑色にマーキングされ、トークンはバケット１１０から消尽される。さもなくば、そのパケットを赤色にマーキングする。他の実施形態では、パケットのマーキングに３色以上を用いることができる。一実施形態では、しきい値は低位優先順位パケットに対しより高くし、高優先順位パケットに対しより低くする。換言すれば、バケットはしきい値を満たすために低位優先順位パケットについては多数のトークンを持たねばならず、一方でバケットは高位優先順位パケットについてはしきい値を満たすために比較的少数のトークンを必要とする。しかしながら、任意の優先順位又は分類のパケットに対し任意のしきい値を用い得ることを当業者は理解しよう。
【００２３】
本発明の一実施形態を、図２を参照してここで説明する。単速度３色マーカーのためのこの実施形態は、図１の実施形態に類似しており、その差異はそれぞれバケット２１０，２２０，２３０，２４０からなる第２の行の追加である。バケットの第２行を第１の行に「結合」し、これを結合された単速度の３色マーカーに作り上げる。バケットの行の結合を、下記にさらに説明する。この説明の目的に合わせ、この第２の行内の各バケットは黄色バケットとする。バケットの緑色行が優先順位付けされるのと全く同じく、バケットの黄色行を優先順位付けする。バケット２１０は最高位の優先順位（優先順位３）の黄色バケットであり、一方でバケット２４０は最低位の優先順位（優先順位０）の黄色バケットである。
【００２４】
実施形態２００は、先の実施形態の如く同一のシングル認定速度ソースを含む。全ての優先順位について緑色バケットが一杯でない限り、黄色バケットへはトークンが決して流入しないことに留意されたい。例えば、バケット１１０がトークンで一杯となると、後続のトークンがバケット１２０内に流入し、続いてバケット１３０，１４０にそれぞれ流入する。しかしながら、バケット１４０がトークンで一杯になると、後続トークンは廃棄されない代りに、優先順位３の黄色バケット２１０内に流入する。最低優先順位の緑色バケット１４０から最高優先順位の黄色バケット２１０へのトークンのオーバフローが、前記した結合を表す。バケット２１０がトークンで一杯となると、後続トークンはバケット２２０等内へ流入する。最後に、他の全てのバケットがトークンで一杯となると、後続トークンはバケット２４０内に流入する。バケット２４０が一旦トークンで一杯になると、後続のトークンは廃棄される。
【００２５】
全ての優先順位に関して緑色バケットが一杯でない限り黄色バケット内へ決してトークンが流入しないとすると、全ての優先順位にわたる総合パケット到着速度が一部の時間期間にわたって認定速度未満でない限り、超過トラフィックは一切許されないことになる。正にこの状況が発生すると、バケット到着速度の検出時に黄色バケット内のトークンはさらに大きなバーストが可能になる（すなわち、黄色バケットが超過バースト容量を提供する）。
【００２６】
図３は、最高位の優先順位の黄色バケット２１０向けの超過速度ソース３０１を含む本発明の一実施形態を示す。本実施形態は、ＭＥＦ１０に記載されたものに類似するが、より高位の優先順位のトラフィックに対するより優先的処置を提供する能力をもって結合した結合されたデュアル速度３色マーカーである。超過トラフィックについてさえ、黄色バケットがトークンで満されるシーケンスは、より高位の優先順位のパケットがより低位の優先順位のトラフィックに対し優先度を与えられることを保証する（すなわち、赤色をマーキングされる可能性は少ない）ことに留意されたい。
【００２７】
図４は、離脱させたデュアル速度３色マーカー（ｄｒＴＣＭ）を規定する本発明の一実施形態を示す。図３について前記した結合されたｄｒＴＣＭとは異なり、離脱させたｄｒＴＣＭは最低位の優先順位緑色バケット１４０から最高位の優先順位黄色バケット２１０へオーバフロートークンを送らない。バケット１４０がトークンで満されると、後続のトークンは廃棄される。同様に、バケット２４０がトークンで満されると、後続のトークンは廃棄される。バケットの緑色行をバケットの黄色行から離脱させることで、入来する黄色トラフィックは全ての未使用緑色トラフィック帯域を利用することはできない。
【００２８】
本発明は、速度ソースをバケットの一部又は全部に加算することで一般化することができる。図５は、全てのバケットが個別の速度ソースを有する場合の一実施形態を示す。バケット５１０，５２０，５３０，５４０は、認定したバケットサイズと認定した速度ソース５１２，５２２，５３２，５４２をそれぞれ有する緑色バケットである。バケット５５０，５６０，５７０，５８０は、超過バーストサイズと超過速度ソース５５２，５６２，５７２，５８２をそれぞれ有する黄色バケットである。認定した速度ソースの和は、総認定速度に等しい。同様に、超過速度ソースの和は総超過速度に等しい。各バケットごとに個別速度ソースを持たせる効果は、最大で各バケットまでの一部帯域がより高位の優先順位のトラフィックの速度によらずに各レベルの優先順位で常時利用可能とすることを保証することにある。
【００２９】
例えば、バケット５１０は速度５１２にてトークンで満される。バケット５１０がトークンで満されると、後続のトークンは速度５１２でバケット５２０内に流入する。加えて、トークンは速度５２２でバケット５２０内に流入する。かくして、バケット５１０がトークンで一杯である場合、バケット５２０はその固有速度５２２にバケット５１０の速度５１２を加えたのに等しい速度にてトークンで満される。これにより、最低位の優先順位の緑色バケット５４０へ続く速度総合の縦列接続が生まれる。かくして、より高位の優先順位のパケットを受け取っていない（及び対応するより高位の優先順位帯域が使用されていない）時間期間中は、優先順位０のパケットは総認定速度で処理することができる。換言すれば、バケット５１０，５２０，５３０がパケットを処理するようトークンを使い尽していないときに、トークンは認定速度５４２に速度５１２，５２２，５３２の和を加えたものに等しい総速度でバケット５４０内に流入する。同様に、優先順位１のパケットは認定速度５３２に速度５１２，５２２の和を加えたものに等しい総速度で処理することができる。
【００３０】
図５に示す如く、緑色バケット５４０がトークンで満されると、後続のトークンは黄色バケット５５０内に流入する。システムが色知覚モードにおいて動作しているときにこの筋書は重要であり、何故ならそのことによって事前着色黄色トラフィックがバケット５４０からバケット５５０へのトークンオーバフローにより提供される追加の帯域を使用できるようにするからである。色知覚モードでは、パケットは緑色、黄色、又は赤色の一つとして事前着色されて到着する。かくして、優先順位ｍの緑色パケットが到着すると、そのときは対応する優先順位ｍの緑色バケット内に十分な数のトークンが存在すれば、優先順位ｍの緑色トークンが使い尽され、優先順位ｍの緑色パケットが処理される。優先順位ｍの緑色バケット内に十分なトークンが存在しない場合、そのときは優先順位ｍの緑色パケットは黄色にマーキングされ、優先順位ｍの緑色トークンは使い尽されないことになる。優先順位ｍの黄色バケット内に十分な数のトークンが存在する場合、優先順位ｍの黄色トークンが使い尽され、優先順位ｍの黄色パケットが処理される。優先順位ｍの黄色バケット内に不十分なトークンが存在する場合、優先順位ｍの黄色パケットは赤色にマーキングされ、優先順位ｍの黄色トークンは使い尽されないことになる。
【００３１】
緑色バケット５４０から黄色バケット５５０へのトークンの流れは、緑色パケットが総認定速度未満の速度で到着したときの時間期間を意味する。したがって、総認定速度に対応する帯域は、入来する緑色トラフィックにより完全に使い尽されることはない。緑色バケット５４０から黄色バケット５５０へオーバフロートークンを送ることで、黄色トラフィックは未使用緑色トラフィック帯域を利用できるようになる。
【００３２】
加えて、黄色バケット５５０，５６０，５７０，５８０はそれぞれ超過速度５５２，５６２，５７２，５８２でトークンを満すことができる。個別超過速度の効果は、一部の超過帯域が各レベルの優先順位にて常時利用可能であることを保証することにある。各超過速度の和は、総超過速度に等しい。
【００３３】
緑色バケット５４０が一杯であり、そこでオーバフロートークンがバケット５４０から黄色バケット５５０へ送られると考えると、緑色トラフィックとより高次の優先順位の黄色トラフィックのレベルが十分に低い場合、バケット５８０は総認定速度と総超過速度に対応する全帯域を用いることが可能である。緑色トラフィック帯域とより高位の優先順位の黄色トラフィック帯域が継続された時間期間にわたり完全に使い尽されていない場合、全優先順位の全ての緑色パケットと黄色パケットが結果的にトークンで満される。
【００３４】
図６にかかわる一実施形態を、ここで説明することにする。実施形態６００は、２行ｎ列の配列のバケットを持つように図示してある。ｘ行ｎ列のサイズの任意の二次元配列が本発明に従って実現できることを、当業者は理解しよう。かくして、実施形態６００は、２行ｎ＋１列のバケットを示す。各行は、色で標識付けしてある。この場合、各行は緑色又は黄色の一方で標識付けされる。各列はゼロからｎまでの優先順位を有しており、ここでｎは最高位の優先順位であり、ゼロは最低位の優先順位である。
【００３５】
バケットの行を識別し及び／又は優先順位付けするのに、他の色の組み合わせ、順序付け、又は他の標識を用いることもできる。同様に、バケットの列を識別し及び／又は優先順位付けするのに、他の組み合わせ、順序付け、分類、又は他の標識を用いることもできる。行列の編成は、優先順位に依拠させることができる。しかしながら、優先順位のレベルに基づき行列を編成することは必要ない。例えば、行と列を、パケットサイズ、パケット送信先又は当分野で周知の他のパケット特性に基づき編成することができる。一実施形態では、列はトラフィッククラスに基づき分類される。他の実施形態では、列は送信元アドレス、送信先アドレス、送信元／送信先複合アドレス、仮想ローカルエリアネットワーク（ＶＬＡＮ）識別子（ＩＤ）、プロトコル、用途種等に基づき分類される。
【００３６】
実施形態６００内の各バケットは、独立速度ソースを有する。独立速度ソースは、総合された全体として動作することもできる。例えば、速度ソース６１２，６２２，６３２は全体の認定速度を形成するために、組み合わせて演算することができる。かくして、速度ソース６２２は所定量だけその速度を減少させた場合、そのときは速度ソース６３２はその速度を同一量だけ上昇させ、これにより認定速度全体が不変のままとなるようにする。同様に、速度ソース６４２，６５２，６６２は総超過速度を形成するために組み合わせて動作する。加えて、実施形態６００の全てのバケットは、総速度全体を形成するために、組み合わさって動作することができる。
【００３７】
実施形態６００の動作は、各バケットごとに類似する。各バケットは、異なる速度でトークンを受け入れる。各バケットは、これもまた異なる個々の最大数のトークンを持たせることができる。各バケットは、それがその個々の最大数のトークンに達するまで、その個別速度でトークンを受け取る。バケットが一旦トークンで満されると、後続のトークン（すなわち、オーバフロートークン）は他所に分配しなければならない。このシステムは、オーバフロートークンの分配用選択肢を選択する。各バケットごとに、選択肢を、事前に、又はオーバフローが生成するときに選択することができる。オーバフロートークンを分配する選択肢を選択する規範及び／又は方法をここで説明はしないが、それは本発明範囲を逸脱するものである。
【００３８】
オーバフロートークンを分配する第１の選択肢は、オーバフロートークンが行内の最低位優先順位バケットからではない場合、同一行内の次の最低位優先順位バケット又はトークンで一杯になっていない行内の次の最低位優先順位バケットへそれらを送ることである。例えば、緑色パケット６１０（優先順位ｎ）が速度ソース６１２からのトークンで満されると、システムは行内の次の最低位優先順位のバケット、すなわち緑色バケット６２０（優先順位ｎ−１）へ、速度６１２でオーバフロートークンを送る。バケット６２０もまたトークンで満されると、システムはバケット６１０のオーバフロートークンを速度６１２にてバケット６３０へ送る。
【００３９】
オーバフロートークンを分配する第２の選択肢は、オーバフロートークンを次のより低位の列内のバケットへ送ることである。一例では、緑色バケット６１０が速度ソース６１２からのトークンで満されると、システムはオーバフロートークンを黄色バケット６４０へ送ることができる。バケット６１０，６４０は、共に優先順位ｎのバケットである。黄色バケット６４０がトークンで一杯になると、バケット６１９又はバケット６４０はオーバフロートークンを同様に優先順位ｎのバケットである黄色バケット６７０へ送る。別の例では、緑色バケット６３０がトークンで満されると、このシステムはオーバフロートークンを列内の次のより低位の優先順位０バケットとして黄色バケット６６０へ送る。しかしながら、緑色バケット６３０が最低位優先順位の緑色バケットであるとすると、システムは、むしろ又はまた、最高位優先順位の黄色バケット６４０へオーバフロートークンを送る。こうして、優先順位付きの縦列接続効果を達成することができる。
【００４０】
オーバフロートークンを分配する第３の選択肢は、図６の６９９に示すオーバフロートークンを廃棄することである。トークンを廃棄すると、対応帯域は未使用のままとされ、廃棄トークン期間中に事実上失われる。
【００４１】
一実施形態では、このシステムはパケット、例えば優先順位ｎ−１のパケットを受け取る。かくして、このシステムは先ず対応する緑色バケット６２０がパケットを処理するのに十分な数のトークンを有するかどうか検査する。一実施形態では、トークンの十分さはバケット内のトークン数をしきい値と比較することで判定される。別の実施形態では、十分な数のトークンは、受け取ったパケットのサイズをバケット内のトークン数と比較することで判定される。パケットのサイズ（例えば、バイト）がバケット内のトークン数以下である場合、そのときはパケットを処理するのに十分な数のトークンが存在する。バケット６２０内に十分な数のトークン数が存在する場合、パケットは緑色にマーキングされ、バケット６２０内のトークン数はパケット内のバイト数だけ減数される。
【００４２】
パケットのサイズがバケット６２０内のトークン数を上回る場合、そのときはバケット６２０は減数されず、システムはそこで黄色優先順位ｎ−１のバケット６５０内に十分な数のトークン数が存在するかどうか検査する。パケットのサイズがバケット６５０内のトークン数以下である場合、そのときはパケットは黄色にマーキングされ、バケット６５０内のトークン数はしかるべく減数される。パケットのサイズがバケット６５０内のトークン数を上回る場合、そのときはバケット６５０は減数されず、パケットは赤色にマーキングされる。
【００４３】
本願明細書に記載したシステムでは、受け取ったパケットのサイズは対応優先順位のバケット内のトークン数に対して比較されるだけである。換言すれば、入来優先順位ｎパケットは、優先順位ｎバケット内のトークン数に対するパケットサイズの比較に基づいてだけ処理することができる。優先順位ｎパケットのサイズは、処理目的に合わせ優先順位ｎ−１バケット内のトークン数と比較することはできない。
【００４４】
装置が色盲モードで動作している本発明の一実施形態では、入来する優先順位ｎのパケットのサイズを、処理目的に合わせて対応する優先順位ｎの緑色バケット６１０内のトークン数に対し先ず比較する。しかしながら、色知覚モードで動作している場合は、受け取ったパケットは到着時に事前着色される。色知覚モードでは、入来する優先順位ｎの緑色パケットのサイズもまた優先順位ｎの緑色バケット６１０内のトークン数と比較することができる。しかし、入来パケットが優先順位ｎの黄色パケットである場合は、このパケットのサイズを、対応する優先順位ｎの黄色バケット６４０内のトークン数と比較しなければならない。黄色バケット６４０がトークンで一杯である場合、そのときはバケット６４０は減数せず、パケットは赤色にマーキングされる。
【００４５】
「一実施形態」又は「一つの実施形態」に対する明細書の引用は、その実施形態に関連して説明した特定の特徴、構造、又は特性が本発明の少なくとも一つの実施形態に含まれることを意味することに、留意されたい。明細書の各所の語句「一実施形態中」の体裁は、必ずしも全て同一の実施形態を指すものではない。
【００４６】
詳細な説明の一部は、例えばコンピュータメモリ内のデータに対する処理のアルゴリズムと記号表現によって提示してある。これらのアルゴリズムの説明と表現は、データ処理技術の当業者がその仕事の実体を他の当業者に最も効果的に伝えるのに用いる手段である。
【００４７】
ここに一つのアルゴリズムがあり、それは概ね所望の成果に通ずる一連のステップと理解される。このステップは、物理量の物理的操作を必要とするものである。通常、必ずしもそうとは限らないが、これらの量は、記憶し転送し複合し比較し、さもなくば操作することのできる電気信号や磁気信号の形をとる。時として主に一般用途上の理由から、これらの信号が２進数、数値、要素、記号、文字、用語、又は番号等を指すことが好都合であることが判っている。
【００４８】
しかしながら、これら並びに同様の用語を全て適当な物理量に関連付け、単にこれらの量に適用するに便利な標識とすることは、念頭に置かれたい。詳細な説明全体を通じて説明に具体的に明記されず、又はそこから明白でない限り、「処理」、「計算」、「算出」、「判定」又は「表示」等の用語を用いた説明は、コンピュータシステムのレジスタやメモリ内の物理的（電子）量として表されるデータを操作して、コンピュータシステムのメモリやレジスタ又は他のこの種の情報の記憶装置、転送装置、表示装置内の物理量として同様に表される他のデータへ変換するコンピュータシステム又は同様の電子計算装置の機能及び処理を指す。
【００４９】
本発明は、本願明細書の動作を遂行する装置にも関するものである。これらの装置は、特に所要の目的に合わせ構成することができ、又はコンピュータ内に記憶させたコンピュータプログラムにより選択的に起動又は再構成する汎用コンピュータで構成される。この種のコンピュータプログラムは、下記に限定はされないが、フロッピー（登録商標）ディスク、光学式記憶媒体、ＣＤ−ＲＯＭ、磁気光ディスク、読み出し専用メモリ（ＲＯＭ）、随時読み書き可能メモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カード、フラッシュメモリカード等の任意の磁気又は他のディスク記憶媒体等の機械読み取り可能な記憶媒体に記憶させることができ、電気や光学や音響又は他の形態の伝搬信号（例えば、搬送波や赤外信号やデジタル信号等）、又は電子指示を記憶するのに適した任意種の媒体が、それぞれコンピュータシステムバスに結合される。
【００５０】
本願明細書に提示されたアルゴリズムと例示は、何ら特定のコンピュータ又は他の装置に本質的に関連するものではない。各種の汎用システムを本願明細書の教示に従うプログラムと共に用いることができ、又はより具体的な装置を構成して所与の方法ステップを遂行することが便利であることが分かろう。加えて、本発明は何らの特定のプログラミング言語を参照して説明はしない。各種プログラミング言語を用いて本願明細書に記載した発明の教示を実装できることは、理解されよう。
【図面の簡単な説明】
【００５１】
【図１】本発明の一実施形態を示すフロー概略図である。
【図２】本発明の一実施形態を示すフロー概略図である。
【図３】本発明の一実施形態を示すフロー概略図である。
【図４】本発明の一実施形態を示すフロー概略図である。
【図５】本発明の一実施形態を示すフロー概略図である。
【図６】本発明の一実施形態を示すフロー概略図である。
【図１】
2009522849.tif 000003
【図２】
2009522849.tif 000004
【図３】
2009522849.tif 000005
【図４】
2009522849.tif 000006
【図５】
2009522849.tif 000007
【図６】
2009522849.tif 000008
【国際調査報告】
2009522849.tif 000009
2009522849.tif 000010