(57)【要約】【課題】バケット数が増大しても、少ない実装面積でバケット値を記憶する。【解決手段】レートリミット処理回路１４において、トークン加算処理部１４Ａが、バケット＃ｉごとに固有の加算タイミングＴａ＃ｉで、バケット値メモリ回路１１のバケット値Ｂｔ＃ｉをＲｔ＃ｉ×Ｔｍだけ一括して加算更新し、増分計算部１４Ｂが、直前加算タイミングＴａ＃ｉからフレーム入力時点Ｔｆまでの経過期間長Ｔｐに増加したバケット値増分ΔＢ＃ｉを計算し、フレーム判定部１４Ｃが、ΔＢ＃ｉから計算した暫定バケット値Ｂｆ＃ｉとフレーム長Ｌと比較して通過／廃棄を判定し、バケット値更新部１４Ｄが、通過判定に応じて、Ｂｆ＃ｉからＬとΔＢ＃ｉとを減算して得たＢｔ＃ｉをバケット値メモリ回路１１に更新記録する。【選択図】  図１
2018037827.tif 000002
【特許請求の範囲】
【請求項１】
入力されたフレームに関する出力レートを、トークンバケット方式に基づいて、Ｎ（Ｎは２以上の整数）個のフロー＃ｉ（ｉ＝１〜Ｎの整数）ごとに制限するレートリミット回路であって、
前記フロー＃ｉごとに設けられたバケット＃ｉに関するバケット値Ｂｔ＃ｉの加算更新が互いに重複することなく順次実行されるように、前記バケット値Ｂｔ＃ｉの加算更新を指示する加算タイミングＴａ＃ｉを、一定の加算周期Ｔｍでそれぞれ出力するタイマ回路と、
前記バケット＃ｉに関するバケット値Ｂｔ＃ｉを、それぞれ対応する記憶領域で記憶するバケット値メモリ回路と、
前記加算タイミングＴａ＃ｉに応じて、前記バケット値メモリ回路の対応するバケット値Ｂｔ＃ｉを加算更新するとともに、新たな入力フレームに応じて、前記バケット値メモリ回路から取得した、前記新たな入力フレームのフロー＃ｉと対応するバケット＃ｉのバケット値Ｂｔ＃ｉに基づいて、前記新たな入力フレームの通過／廃棄を判定するレートリミット処理回路とを備え、
前記レートリミット処理回路は、
前記加算タイミングＴａ＃ｉに応じて、前記バケット値メモリ回路のバケット値Ｂｔ＃ｉに、前記フロー＃ｉに関するトークンレートＲｔ＃ｉから計算した前記加算周期Ｔｍ分のトークン加算量Ｒｔ＃ｉ×Ｔｍを、前記バケット値Ｂｔ＃ｉの上限であるバケットサイズＢｓ＃ｉを超えない範囲で一括して加算更新するトークン加算処理部と、
フロー＃ｉに関する新たな入力フレームに応じて、直前の加算タイミングＴａ＃ｉから前記新たな入力フレームの入力時点までの経過期間の経過期間長Ｔｐに前記トークンレートＲｔ＃ｉを乗算することにより、前記経過期間に増加したバケット値増分ΔＢ＃ｉを計算する増分計算部と、
前記バケット値メモリ回路のバケット値Ｂｔ＃ｉに前記バケット値増分ΔＢ＃ｉを、前記バケットサイズＢｓ＃ｉを超えない範囲で加算することにより、前記入力フレームの入力時点における暫定バケット値Ｂｆ＃ｉを計算した後、前記入力フレームのフレーム長Ｌと比較することにより、前記入力フレームの通過／廃棄を判定するフレーム判定部と、
前記入力フレームに対して通過と判定された場合、前記暫定バケット値Ｂｆ＃ｉから前記フレーム長Ｌと前記バケット値増分ΔＢ＃ｉとを減算することにより、新たなバケット値Ｂｔ＃ｉを計算して前記バケット値メモリ回路に更新記録するバケット値更新部とを有する
ことを特徴とするレートリミット回路。
【請求項２】
入力されたフレームに関する出力レートを、トークンバケット方式に基づいて、Ｎ（Ｎは２以上の整数）個のフロー＃ｉ（ｉ＝１〜Ｎの整数）ごとに制限するレートリミット回路であって、
前記フロー＃ｉごとに設けられたバケット＃ｉのうち、基準となる基準バケット＃Ｓのバケット値Ｂｔ＃Ｓを加算更新する加算タイミングＴａ＃Ｓを、一定の加算周期Ｔｍで出力するタイマ回路と、
前記バケット＃ｉに関するバケット値Ｂｔ＃ｉを、それぞれ対応する記憶領域で記憶するバケット値メモリ回路と、
前記加算タイミングＴａ＃Ｓを基準として、前記バケット＃ｉに関するバケット値Ｂｔ＃ｉの加算更新が互いに重複することなく順次実行されるように計時した、前記バケット＃ｉのそれぞれに関する加算タイミングＴａ＃ｉに応じて、前記バケット値メモリ回路の対応するバケット値Ｂｔ＃ｉを加算更新するとともに、新たな入力フレームに応じて、前記バケット値メモリ回路から取得した、前記新たな入力フレームのフロー＃ｉと対応するバケット＃ｉのバケット値Ｂｔ＃ｉに基づいて、前記新たな入力フレームの通過／廃棄を判定するレートリミット処理回路とを備え、
前記レートリミット処理回路は、
前記加算タイミングＴａ＃ｉに応じて、前記バケット値メモリ回路のバケット値Ｂｔ＃ｉに、前記フロー＃ｉに関するトークンレートＲｔ＃ｉから計算した前記加算周期Ｔｍ分のトークン加算量Ｒｔ＃ｉ×Ｔｍを、前記バケット値Ｂｔ＃ｉの上限であるバケットサイズＢｓ＃ｉを超えない範囲で一括して加算更新するトークン加算処理部と、
フロー＃ｉに関する新たな入力フレームに応じて、直前の加算タイミングＴａ＃ｉから前記新たな入力フレームの入力時点までの経過期間の経過期間長Ｔｐに前記トークンレートＲｔ＃ｉを乗算することにより、前記経過期間に増加したバケット値増分ΔＢ＃ｉを計算する増分計算部と、
前記バケット値メモリ回路のバケット値Ｂｔ＃ｉに前記バケット値増分ΔＢ＃ｉを、前記バケットサイズＢｓ＃ｉを超えない範囲で加算することにより、前記入力フレームの入力時点における暫定バケット値Ｂｆ＃ｉを計算した後、前記入力フレームのフレーム長Ｌと比較することにより、前記入力フレームの通過／廃棄を判定するフレーム判定部と、
前記入力フレームに対して通過と判定された場合、前記暫定バケット値Ｂｆ＃ｉから前記フレーム長Ｌと前記バケット値増分ΔＢ＃ｉとを減算することにより、新たなバケット値Ｂｔ＃ｉを計算して前記バケット値メモリ回路に更新記録するバケット値更新部とを有し、
前記増分計算部は、前記加算タイミングＴａ＃Ｓから前記加算タイミングＴａ＃ｉまでの加算更新前期間に、フロー＃ｉの入力フレームが新たに入力された場合、前記バケット値増分ΔＢ＃ｉを前記トークン加算量Ｒｔ＃ｉ×Ｔｍだけ加算する
ことを特徴とするレートリミット回路。
【請求項３】
請求項１または請求項２に記載のレートリミット回路において、
前記バケットの特性を示すプロファイルを、それぞれ固有のＩＤと対応させて記憶するプロファイルメモリ回路をさらに備え、
前記バケット値メモリ回路は、前記バケット値ごとに、対応するバケットに適用するプロファイルを示すＩＤを記憶し、
前記レートリミット処理回路は、フロー＃ｉに関する新たな入力フレームに応じて、前記バケット値メモリ回路からバケット＃ｉのＩＤを取得し、前記プロファイルメモリ回路から前記ＩＤに基づき取得したプロファイルに基づいて、前記バケット値Ｂｔ＃ｉの加算更新および前記入力フレームの通過／廃棄判定を行う
ことを特徴とするレートリミット回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力されたフレームに関する出力レートをフローごとに制限するレートリミット回路技術に関する。
【背景技術】
【０００２】
従来、データ通信網において、フレームの出力レートを制限する方法として、トークンバケット方式を用いたレートリミット技術が提案されている。
トークンバケット方式では、規定の出力レートで処理可能な余裕度を示すトークンという仮想の量を設定し、フレームが下流に出力されて余裕ができた分だけトークンをトークンバケットに溜めて、上流からフレームが入力されると、入力フレームの大きさに相当するトークンがトークンバケットにあるかどうかで、フレームを下流に出力するか廃棄するかを判定している。
【０００３】
図１２は、従来のレートリミット回路を示す構成例である。図１２において、分類回路は、各入力フレームを複数のフローに分類し、フレームとともに分類結果（フロー番号）を出力する。振り分け回路は、分類回路からの分類結果（フロー番号）に基づいて、入力フレームをＮ（Ｎは２以上の整数）個のレートリミット処理回路＃１，＃２，…，＃Ｎのいずれかに振り分ける。各レートリミット処理回路＃１，＃２，…，＃Ｎにより、通過判定されたフレームは、セレクタを介して下流に出力される。
【０００４】
図１３は、従来のレートリミット処理を示す説明図である。図１３に示すように、フロー毎に備えられた各レートリミット処理回路＃１，＃２，…，＃Ｎは、予め設定された出力レート等の条件に基づいて、各自のトークンバケットに溜められているトークンの量、すなわちバケット値を、クロックサイクルごとに逐次更新する。分類回路での分類結果（フロー番号）に基づいて振り分け回路により選択されたレートリミット処理回路＃ｉ（ｉは１〜Ｎの整数）は、バケット値と入力フレームのフレーム長とに基づいて、入力フレームの通過／廃棄を判定する。
【０００５】
図１４は、従来のレートリミット処理に応じたバケット値の変化を示すタイムチャートである。レートリミット処理回路＃ｉは、予め設定されている一定の出力レートに基づいて、バケット値の上限であるバケットサイズを超えない範囲で、クロックサイクルごとにバケット値を加算することにより、トークンバケットにトークンを追加する。また、フレーム入力に応じて振り分け回路により選択された場合、レートリミット処理回路＃ｉは、バケット値と入力フレームのフレーム長とを比較し、入力フレームのフレーム長分のトークンがトークンバケットにあれば、通過と判定して入力フレームを出力し、フレーム長分だけバケット値を減算する。一方、入力フレームのフレーム長がバケット値より大きく、フレーム長分のトークンがトークンバケットになければ、廃棄と判定して入力フレームを廃棄する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−８８９９８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、このような従来技術では、レートリミット処理回路ごとに、各バケットのバケット値をクロックサイクルごとに同時に更新しているため、複数の記憶領域を同時に更新することが不可能なメモリを、複数のバケットで共用できないことから、各バケット値を記憶するレジスタを並列的に設ける必要があった。したがって、バケット数の増加に応じて必要なレジスタ数も増大するため、フロー分類数の増加に合わせて例えば数千個のバケットを管理するような場合には、レートリミット回路の実装面積が極めて膨大なサイズとなるという問題点があった。
【０００８】
本発明はこのような課題を解決するためのものであり、バケット数が増大しても、少ない実装面積でバケット値を記憶できるレートリミット回路技術を提供することを目的としている。
【課題を解決するための手段】
【０００９】
このような目的を達成するために、本発明にかかるレートリミット回路は、入力されたフレームに関する出力レートを、トークンバケット方式に基づいて、Ｎ（Ｎは２以上の整数）個のフロー＃ｉ（ｉ＝１〜Ｎの整数）ごとに制限するレートリミット回路であって、
前記フロー＃ｉごとに設けられたバケット＃ｉに関するバケット値Ｂｔ＃ｉの加算更新が互いに重複することなく順次実行されるように、前記バケット値Ｂｔ＃ｉの加算更新を指示する加算タイミングＴａ＃ｉを、一定の加算周期Ｔｍでそれぞれ出力するタイマ回路と、前記バケット＃ｉに関するバケット値Ｂｔ＃ｉを、それぞれ対応する記憶領域で記憶するバケット値メモリ回路と、前記加算タイミングＴａ＃ｉに応じて、前記バケット値メモリ回路の対応するバケット値Ｂｔ＃ｉを加算更新するとともに、新たな入力フレームに応じて、前記バケット値メモリ回路から取得した、前記新たな入力フレームのフロー＃ｉと対応するバケット＃ｉのバケット値Ｂｔ＃ｉに基づいて、前記新たな入力フレームの通過／廃棄を判定するレートリミット処理回路とを備え、前記レートリミット処理回路は、前記加算タイミングＴａ＃ｉに応じて、前記バケット値メモリ回路のバケット値Ｂｔ＃ｉに、前記フロー＃ｉに関するトークンレートＲｔ＃ｉから計算した前記加算周期Ｔｍ分のトークン加算量Ｒｔ＃ｉ×Ｔｍを、前記バケット値Ｂｔ＃ｉの上限であるバケットサイズＢｓ＃ｉを超えない範囲で一括して加算更新するトークン加算処理部と、フロー＃ｉに関する新たな入力フレームに応じて、直前の加算タイミングＴａ＃ｉから前記新たな入力フレームの入力時点までの経過期間の経過期間長Ｔｐに前記トークンレートＲｔ＃ｉを乗算することにより、前記経過期間に増加したバケット値増分ΔＢ＃ｉを計算する増分計算部と、前記バケット値メモリ回路のバケット値Ｂｔ＃ｉに前記バケット値増分ΔＢ＃ｉを、前記バケットサイズＢｓ＃ｉを超えない範囲で加算することにより、前記入力フレームの入力時点における暫定バケット値Ｂｆ＃ｉを計算した後、前記入力フレームのフレーム長Ｌと比較することにより、前記入力フレームの通過／廃棄を判定するフレーム判定部と、前記入力フレームに対して通過と判定された場合、前記暫定バケット値Ｂｆ＃ｉから前記フレーム長Ｌと前記バケット値増分ΔＢ＃ｉとを減算することにより、新たなバケット値Ｂｔ＃ｉを計算して前記バケット値メモリ回路に更新記録するバケット値更新部とを有するものである。
【００１０】
また、本発明にかかる他のレートリミット回路は、入力されたフレームに関する出力レートを、トークンバケット方式に基づいて、Ｎ（Ｎは２以上の整数）個のフロー＃ｉ（ｉ＝１〜Ｎの整数）ごとに制限するレートリミット回路であって、前記フロー＃ｉごとに設けられたバケット＃ｉのうち、基準となる基準バケット＃Ｓのバケット値Ｂｔ＃Ｓを加算更新する加算タイミングＴａ＃Ｓを、一定の加算周期Ｔｍで出力するタイマ回路と、前記バケット＃ｉに関するバケット値Ｂｔ＃ｉを、それぞれ対応する記憶領域で記憶するバケット値メモリ回路と、前記加算タイミングＴａ＃Ｓを基準として、前記バケット＃ｉに関するバケット値Ｂｔ＃ｉの加算更新が互いに重複することなく順次実行されるように計時した、前記バケット＃ｉのそれぞれに関する加算タイミングＴａ＃ｉに応じて、前記バケット値メモリ回路の対応するバケット値Ｂｔ＃ｉを加算更新するとともに、新たな入力フレームに応じて、前記バケット値メモリ回路から取得した、前記新たな入力フレームのフロー＃ｉと対応するバケット＃ｉのバケット値Ｂｔ＃ｉに基づいて、前記新たな入力フレームの通過／廃棄を判定するレートリミット処理回路とを備え、前記レートリミット処理回路は、前記加算タイミングＴａ＃ｉに応じて、前記バケット値メモリ回路のバケット値Ｂｔ＃ｉに、前記フロー＃ｉに関するトークンレートＲｔ＃ｉから計算した前記加算周期Ｔｍ分のトークン加算量Ｒｔ＃ｉ×Ｔｍを、前記バケット値Ｂｔ＃ｉの上限であるバケットサイズＢｓ＃ｉを超えない範囲で一括して加算更新するトークン加算処理部と、フロー＃ｉに関する新たな入力フレームに応じて、直前の加算タイミングＴａ＃ｉから前記新たな入力フレームの入力時点までの経過期間の経過期間長Ｔｐに前記トークンレートＲｔ＃ｉを乗算することにより、前記経過期間に増加したバケット値増分ΔＢ＃ｉを計算する増分計算部と、前記バケット値メモリ回路のバケット値Ｂｔ＃ｉに前記バケット値増分ΔＢ＃ｉを、前記バケットサイズＢｓ＃ｉを超えない範囲で加算することにより、前記入力フレームの入力時点における暫定バケット値Ｂｆ＃ｉを計算した後、前記入力フレームのフレーム長Ｌと比較することにより、前記入力フレームの通過／廃棄を判定するフレーム判定部と、前記入力フレームに対して通過と判定された場合、前記暫定バケット値Ｂｆ＃ｉから前記フレーム長Ｌと前記バケット値増分ΔＢ＃ｉとを減算することにより、新たなバケット値Ｂｔ＃ｉを計算して前記バケット値メモリ回路に更新記録するバケット値更新部とを有し、前記増分計算部は、前記加算タイミングＴａ＃Ｓから前記加算タイミングＴａ＃ｉまでの加算更新前期間に、フロー＃ｉの入力フレームが新たに入力された場合、前記バケット値増分ΔＢ＃ｉを前記トークン加算量Ｒｔ＃ｉ×Ｔｍだけ加算するようにしたものである。
【００１１】
また、本発明にかかる上記レートリミット回路の一構成例は、前記バケットの特性を示すプロファイルを、それぞれ固有のＩＤと対応させて記憶するプロファイルメモリ回路をさらに備え、前記バケット値メモリ回路は、前記バケット値ごとに、対応するバケットに適用するプロファイルを示すＩＤを記憶し、前記レートリミット処理回路は、フロー＃ｉに関する新たな入力フレームに応じて、前記バケット値メモリ回路からバケット＃ｉのＩＤを取得し、前記プロファイルメモリ回路から前記ＩＤに基づき取得したプロファイルに基づいて、前記バケット値Ｂｔ＃ｉの加算更新および前記入力フレームの通過／廃棄判定を行うようにしたものである。
【発明の効果】
【００１２】
本発明によれば、バケット値の加算更新処理が時分割で実行されるため、各バケット値を共通のバケット値メモリ回路で記憶することができ、個別のレジスタでバケット値を記憶する場合と比較して、実装面積を大幅に削減することが可能となる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施の形態にかかるレートリミット回路の構成を示すブロック図である。
【図２】バケット値メモリ回路での記憶例である。
【図３】第１の実施の形態にかかるバケットタイマの値と加算タイミングを示すタイミングチャート（アップカウンタの場合）である。
【図４】第１の実施の形態にかかるバケットタイマの値と加算タイミングを示すタイミングチャート（ダウンカウンタの場合）である。
【図５】第１の実施の形態にかかるリートリミット処理に応じたバケット値の変化を示すタイミングチャートである。
【図６】第２の実施の形態にかかるレートリミット回路の構成を示すブロック図である。
【図７】第２の実施の形態にかかるバケットタイマの値と加算タイミングを示すタイミングチャート（アップカウンタの場合）である。
【図８】第２の実施の形態にかかるバケットタイマの値と加算タイミングを示すタイミングチャート（ダウンカウンタの場合）である。
【図９】第２の実施の形態にかかるリートリミット処理に応じたバケット値の変化（フレーム入力：加算更新後期間）を示すタイミングチャートである。
【図１０】第２の実施の形態にかかるリートリミット処理に応じたバケット値の変化（フレーム入力：加算更新前期間）を示すタイミングチャートである。
【図１１】第３の実施の形態にかかるレートリミット回路の構成を示すブロック図である。
【図１２】従来のレートリミット回路を示す構成例である。
【図１３】従来のレートリミット処理を示す説明図である。
【図１４】従来のレートリミット処理に応じたバケット値の変化を示すタイムチャートである。
【発明を実施するための形態】
【００１４】
［発明の原理］
まず、本発明の原理について説明する。
一般的なトークンバケット方式では、トークンレートＲｔに基づきバケットに溜められているトークンの量、すなわちバケット値Ｂｔを、例えばシステムクロックなどの、最小時間単位ごとに加算更新して、リアルタイムなバケット値Ｂｔを計算している。これにより、いずれのタイミングでフレームが入力された場合でも、正確なトークン量に基づいて、入力フレームに対する通過／廃棄判定を行うことが可能となる。
【００１５】
しかしながら、リアルタイムでバケット値を計算するためには、各バケット値を並列的に加算更新する必要がある。この際、同一メモリ回路で各バケット値を記憶する場合、メモリ回路へのアクセス衝突が発生する。このため、レジスタなどの独立した回路素子で各バケット値を記憶しておく必要があり、実装面積の増大に繋がる。
本発明は、これらバケット値を共通のメモリ回路で記憶することにより実装面積を削減するものとし、メモリ回路へのアクセス衝突を回避するため、バケット値の加算更新をバケットごとの個別の加算タイミングにより時分割処理するようにしたものである。
【００１６】
この際、バケット値の加算更新を時分割処理した場合、バケット値を逐次加算更新できないため、加算タイミングＴａごとに、加算タイミング間隔に相当する加算周期Ｔｍ分のトークン加算値Ｒｔ×Ｔｍを一括してバケット値Ｂｔに加算するようにしたものである。ここで、トークン加算値Ｒｔ＃ｉと加算周期Ｔｍが定数なので、Ｒｔ＃ｉ×Ｔｍも定数である。これにより、加算タイミングＴａごとに、バケット値Ｂｔを、実際にバケットに溜められているべきトークン量Ｔｋと一致させることができる。
【００１７】
また、フレーム入力時には、直前の加算タイミングＴａからフレーム入力時点Ｔｆまでの経過期間長Ｔｐ分のトークン量に相当するバケット値増分ΔＢを、バケット値Ｂｔに加算して暫定バケット値Ｂｆを計算し、この暫定バケット値Ｂｆとフレーム長Ｌとを比較して、通過／廃棄判定を行うようにしたものである。これにより、加算タイミングＴａとは異なるタイミングＴｆでフレームが入力されても、実際のトークン量Ｔｋと一致した暫定バケット値Ｂｆに基づいて、入力フレームの通過／廃棄を正確に判定することができる。
【００１８】
さらに、通過の判定に応じてバケット値Ｂｔを更新する場合には、暫定バケット値Ｂｆからフレーム長Ｌを減算した後、さらにバケット値増分ΔＢを減算することにより、バケット値を補正しておくようにしたものである。これにより、次回の加算タイミングＴａにおいて、加算周期Ｔｍ分のトークン加算値Ｒｔ×Ｔｍして加算した時点で、バケット値Ｂｔを実際のトークン量Ｔｋと一致させることができる。
【００１９】
次に、本発明の実施の形態について図面を参照して説明する。
［第１の実施の形態］
まず、図１を参照して、本発明の第１の実施の形態にかかるレートリミット回路１０について説明する。図１は、第１の実施の形態にかかるレートリミット回路の構成を示すブロック図である。
【００２０】
このレートリミット回路１０は、データ通信網を構成する各種通信装置で用いられて、例えば図１２に示したような、前段の分類回路から出力された入力フレームと分類結果（フロー番号）とに基づいて動作することにより、入力フレームに関する出力レートを、トークンバケット方式に基づいて、Ｎ（Ｎは２以上の整数）個のフロー＃ｉ（ｉ＝１〜Ｎの整数）ごとに制限する回路である。
【００２１】
図１に示すように、レートリミット回路１０には、主な回路部として、バケット値メモリ回路１１、タイマ回路１２、およびレートリミット処理回路１４が設けられている。
【００２２】
バケット値メモリ回路１１は、各バケットに関するバケット値を、それぞれ対応する記憶領域で記憶するメモリ回路である。
図２は、バケット値メモリ回路での記憶例である。ここでは、バケットｉごとに、バケット値Ｂｔ＃ｉ、バケットサイズＢｓ＃ｉ、トークンレートＲｔ＃ｉ、およびトークン加算値Ｒｔ＃ｉ×Ｔｍがそれぞれ記憶されている。
【００２３】
タイマ回路１２は、フロー＃ｉごとにバケットタイマ＃ｉを有し、フロー＃ｉごとに設けられたバケット＃ｉに関するバケット値Ｂｔ＃ｉの加算更新が互いに重複することなく順次実行されるように、バケット値Ｂｔ＃ｉの加算更新を指示する加算タイミングＴａ＃ｉを、バケットタイマ＃ｉから一定の加算周期Ｔｍでそれぞれレートリミット処理回路１４へ出力する機能を有している。
【００２４】
トークンバケット方式では、前述したように、フロー＃ｉに対して予め設定されたトークンレートＲｔ＃ｉに基づいて、単位時間当たりで一定数のトークンがバケットに追加される。バケット値Ｂｔ＃ｉは、バケット＃ｉに溜められているトークン量を示す値である。本実施の形態では、タイマ回路１２において、バケット＃ｉごとに個別のバケットタイマ＃ｉを設け、各バケット値Ｂｔ＃ｉの加算更新を実行する加算タイミングＴａ＃ｉを生成している。
【００２５】
図３は、第１の実施の形態にかかるバケットタイマの値と加算タイミングを示すタイミングチャート（アップカウンタの場合）である。図４は、第１の実施の形態にかかるバケットタイマの値と加算タイミングを示すタイミングチャート（ダウンカウンタの場合）である。
バケット＃１，＃２，…，＃Ｎ関するバケットタイマ＃１，＃２，…，＃Ｎの値は、処理時間長Ｔｗだけ順にずらして、一定の加算周期Ｔｍで繰り返しカウントされる。この際、図３のようにアップカウンタを用いてもよく、図４のようにダウンカウンタを用いてもよい。
【００２６】
バケット＃１，＃２，…，＃Ｎに関する加算タイミングＴａ＃１，＃２，…，＃Ｎは、バケットタイマ＃１，＃２，…，＃Ｎの満了時で、処理時間長Ｔｗだけ順にずらして、一定の加算周期Ｔｍで繰り返し出力される。Ｔｗは、１つのバケット値Ｂｔを加算更新する処理に要する処理時間長を示している。Ｔｍは、Ｎ個すべてのバケット値Ｂｔの加算更新に要する加算周期を示しており、Ｎ×Ｔｗ分より長い時間長を持つ。これにより、バケット値メモリ回路１１で記憶している各バケット値ＢｔがＢｔ＃１から順にＢｔ＃Ｎまで加算更新され、これが加算周期Ｔｍで繰り返し実行されることになる。
【００２７】
レートリミット処理回路１４は、加算タイミングＴａ＃１，＃２，…，＃Ｎのそれぞれに応じて、バケット値メモリ回路１１の対応するバケット値Ｂｔ＃１，＃２，…，＃Ｎを加算更新する機能と、新たな入力フレームに応じて、バケット値メモリ回路１１から取得した、新たな入力フレームのフロー＃ｉと対応するバケット＃ｉのバケット値Ｂｔ＃ｉに基づいて、新たな入力フレームの通過／廃棄を判定する機能とを有している。
【００２８】
レートリミット処理回路１４には、主な回路部として、トークン加算処理部１４Ａ、増分計算部１４Ｂ、フレーム判定部１４Ｃ、およびバケット値更新部１４Ｄが設けられている。
【００２９】
トークン加算処理部１４Ａ、タイマ回路１２からの加算タイミングＴａ＃ｉに応じて、バケット値メモリ回路１１から取得したバケット値Ｂｔ＃ｉに、フロー＃ｉに対して予め設定されているトークンレートＲｔ＃ｉから計算した加算周期Ｔｍ分のトークン加算量Ｒｔ＃ｉ×Ｔｍを、バケット値Ｂｔ＃ｉの上限であるバケットサイズＢｓ＃ｉを超えない範囲で一括して加算更新する機能を有している。この際、バケット値Ｂｔ＃ｉは、予め設定されているバケットサイズＢｓ＃ｉが上限値となるため、加算更新時において、例えばＢｔ＃ｉ＋Ｒｔ＃ｉ×ＴｍとＢｓ＃ｉのうち小さいほうの値を選択して加算更新すればよい。
【００３０】
増分計算部１４Ｂは、フロー＃ｉに関する新たな入力フレームに応じて、フロー＃ｉに関する直前の加算タイミングＴａ＃ｉから新たな入力フレームの入力時点までの経過期間長Ｔｐに、トークンレートＲｔ＃ｉを乗算することにより、直前の加算タイミングＴａ＃ｉから新たな入力フレームの入力時点までの間に増加したバケット値増分ΔＢ＃ｉを計算する機能を有している。
【００３１】
フレーム判定部１４Ｃは、バケット値メモリ回路１１のバケット値Ｂｔ＃ｉにバケット値増分ΔＢ＃ｉを、バケット値Ｂｔ＃ｉの上限であるバケットサイズＢｓ＃ｉを超えない範囲で加算することにより、入力フレームの入力時点における暫定バケット値Ｂｆ＃ｉを計算する機能と、得られた暫定バケット値Ｂｆ＃ｉを入力フレームのフレーム長Ｌと比較することにより、入力フレームの通過／廃棄を判定する機能と、得られた判定結果が通過判定を示す場合には入力フレームを下流に出力する機能と、得られた判定結果が廃棄判定を示す場合には入力フレームを廃棄する機能とを有している。この際、バケット値Ｂｔ＃ｉは、予め設定されているバケットサイズＢｓ＃ｉが上限値となるため、加算更新時において、例えばＢｔ＃ｉ＋Ｒｔ＃ｉ×ＴｍとＢｓ＃ｉのうち小さいほうの値を選択して暫定加算更新すればよい。
【００３２】
バケット値更新部１４Ｄは、フレーム判定部１４Ｃにより入力フレームに対して通過と判定された場合、暫定バケット値Ｂｆ＃ｉからフレーム長Ｌとバケット値増分ΔＢ＃ｉとを減算することにより、新たなバケット値Ｂｔ＃ｉを計算してバケット値メモリ回路１１に更新記録する機能を有している。
【００３３】
［第１の実施の形態の動作］
次に、図５を参照して、本実施の形態にかかるレートリミット回路１０の動作について説明する。図５は、第１の実施の形態にかかるリートリミット処理に応じたバケット値の変化を示すタイミングチャートである。
ここでは、フロー＃ｉの入力フレームに対するリートリミット処理のみに注目して説明するものとし、バケット値Ｂｔ＃ｉ、暫定バケット値Ｂｆ＃ｉ、バケットサイズＢｓ＃ｉ、およびトークンレートＲｔ＃ｉを省略して単にＢｔ，Ｂｆ，Ｂｓ，Ｒｔと表すものとする。
【００３４】
まず、時刻Ｔ１における加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ０を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ１でバケット値メモリ回路１１を更新する。これにより、加算タイミングＴａ＃ｉごとに、バケット値Ｂｔを、実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致させることができる。なお、図５の例では、時刻Ｔ１以前のバケット値Ｂｔ０がバケットサイズＢｓに達しているため、時刻Ｔ１におけるバケット値Ｂｔ１もＢｓと等しい値となる。
【００３５】
その後、時刻Ｔｆ１にフロー＃ｉの新たなフレームが入力された場合、増分計算部１４Ｂは、直前の加算タイミングＴａ＃ｉである時刻Ｔ１から時刻Ｔｆ１までの経過期間長Ｔｐ１に、トークンレートＲｔを乗算することにより、時刻Ｔ１から時刻Ｔｆ１までの間に増加したバケット値増分ΔＢ１を計算する。
【００３６】
続いて、フレーム判定部１４Ｃは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ１に、増分計算部１４Ｂで計算したバケット値増分ΔＢ１を加算することにより、時刻Ｔｆ１における暫定バケット値Ｂｆ１を計算し、入力フレームのフレーム長Ｌ１と比較する。これにより、加算タイミングＴａ＃ｉの時刻Ｔ１とは異なる時刻Ｔｆ１でフレームが入力されても、実際のトークン量Ｔｋと一致した暫定バケット値Ｂｆ１に基づいて、入力フレームの通過／廃棄を正確に判定することができる。
【００３７】
ここで、図５の例では、バケット値Ｂｔ１がバケットサイズＢｓに達していることから、暫定バケット値Ｂｆ１もＢｓと等しくなるが、Ｂｆ１＞Ｌ１であることから、フレーム判定部１４Ｃは入力フレームに対して通過と判定し、入力フレームを下流へ出力する。
また、バケット値更新部１４Ｄは、フレーム判定部１４Ｃでの通過判定に応じて、暫定バケット値Ｂｆ１からフレーム長Ｌ１とバケット値増分ΔＢ１とを減算することにより、バケット＃ｉの新たなバケット値Ｂｔ１’を計算してバケット値メモリ回路１１に更新記録する。
【００３８】
その後、時刻Ｔ２における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ１’を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ２でバケット値メモリ回路１１を更新する。この際、時刻Ｔｆ１において、バケット値更新部１４Ｄにより、バケット値増分ΔＢ１でバケット値Ｂｔ１’が補正されているため、時刻Ｔ２において、バケット値に加算周期Ｔｍ分のトークン加算値Ｒｔ×Ｔｍを一括して加算した時点で、バケット値Ｂｔ２を実際のトークン量Ｔｋと一致させることができる。
【００３９】
続く、時刻Ｔ３における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ２を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ３でバケット値メモリ回路１１を更新する。これにより、時刻Ｔ３において、バケット値Ｂｔ３が実際のトークン量Ｔｋと一致することになる。
【００４０】
その後、時刻Ｔｆ３にフロー＃ｉの新たなフレームが入力された場合、増分計算部１４Ｂは、直前の加算タイミングＴａ＃ｉである時刻Ｔ３から時刻Ｔｆ３までの経過期間長Ｔｐ３に、トークンレートＲｔを乗算することにより、時刻Ｔ３から時刻Ｔｆ３までの間に増加したバケット値増分ΔＢ３を計算する。
続いて、フレーム判定部１４Ｃは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ３に、増分計算部１４Ｂで計算したバケット値増分ΔＢ３を加算することにより、時刻Ｔｆ３における暫定バケット値Ｂｆ３を計算し、入力フレームのフレーム長Ｌ３と比較する。
【００４１】
ここで、図５の例では、Ｂｆ３＞Ｌ３であることから、フレーム判定部１４Ｃは入力フレームに対して通過と判定し、入力フレームを下流へ出力する。
また、バケット値更新部１４Ｄは、フレーム判定部１４Ｃでの通過判定に応じて、暫定バケット値Ｂｆ３からフレーム長Ｌ３とバケット値増分ΔＢ３とを減算することにより、バケット＃ｉの新たなバケット値Ｂｔ３’を計算してバケット値メモリ回路１１に更新記録する。
【００４２】
続く、時刻Ｔ４における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ３’を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ４でバケット値メモリ回路１１を更新する。これにより、時刻Ｔ４において、バケット値Ｂｔ４が実際のトークン量Ｔｋと一致することになる。
【００４３】
［第１の実施の形態の効果］
このように、本実施の形態は、レートリミット処理回路１４において、トークン加算処理部１４Ａが、システムクロックなどの最小時間単位よりも周期が長い、バケット＃ｉごとに固有の加算タイミングＴａ＃ｉで、バケット値メモリ回路１１のバケット値Ｂｔ＃ｉをＲｔ＃ｉ×Ｔｍだけ一括して加算更新し、増分計算部１４Ｂが、直前加算タイミングＴａ＃ｉからフレーム入力時点Ｔｆまでの経過期間長Ｔｐに増加したバケット値増分ΔＢ＃ｉを計算し、フレーム判定部１４Ｃが、ΔＢ＃ｉから計算した暫定バケット値Ｂｆ＃ｉとフレーム長Ｌと比較して通過／廃棄を判定し、バケット値更新部１４Ｄが、通過判定に応じて、Ｂｆ＃ｉからＬとΔＢ＃ｉとを減算して得たＢｔ＃ｉをバケット値メモリ回路１１に更新記録するようにしたものである。
【００４４】
これにより、バケット値の加算更新処理が時分割で実行されるため、各バケット値を共通のバケット値メモリ回路１１で記憶することができ、個別のレジスタでバケット値を記憶する場合と比較して、実装面積を大幅に削減することが可能となる。
【００４５】
また、直前の加算タイミングＴａ＃ｉからフレーム入力時点Ｔｆまでの経過期間長Ｔｐ分のトークン量に相当するバケット値増分ΔＢ＃ｉを、バケット値Ｂｔ＃ｉに加算して得られた暫定バケット値Ｂｆ＃ｉと、フレーム長Ｌとを比較して通過／廃棄判定を行うようにしたので、加算タイミングＴａ＃ｉとは異なるタイミングＴｆでフレームが入力されても、実際のトークン量Ｔｋと一致した暫定バケット値Ｂｆ＃ｉに基づいて、入力フレームの通過／廃棄を正確に判定することができる。
【００４６】
さらに、通過の判定に応じて、暫定バケット値Ｂｆ＃ｉからフレーム長Ｌを減算した後、さらにバケット値増分ΔＢ＃ｉを減算することにより、バケット値Ｂｔ＃ｉを補正しておくようにしたので、次回の加算タイミングＴａ＃ｉにおいて、加算周期Ｔｍ分のトークン加算値Ｒｔ＃ｉ×Ｔｍを一括して加算した時点で、バケット値を実際のトークン量Ｔｋと一致させることができる。
【００４７】
したがって、バケット値Ｂｔ＃ｉを補正する際、直前に入力されたフレームの入力時刻や、次にバケット値ＢＴ＃ｉを加算更新すべき更新時刻を、バケット値メモリ回路１１で記憶保持しておく必要がなくなるため、記憶容量を削減でき、結果として実装面積を大幅に削減することが可能となる。また、トークン加算量Ｒｔ＃ｉ×Ｔｍやバケット値増分ΔＢ＃ｉを計算するための演算が単純なので、処理速度が遅いソフトウェアを介さずに、処理速度が速いハードウェアのみで処理を行うことが可能である。
【００４８】
［第２の実施の形態］
次に、図６を参照して、本発明の第２の実施の形態にかかるレートリミット回路１０について説明する。図６は、第２の実施の形態にかかるレートリミット回路の構成を示すブロック図である。
【００４９】
第１の実施の形態では、タイマ回路１２に各フロー＃１，＃２，…，＃Ｎに対応するバケットタイマ＃１，＃２，…，＃Ｎを設けて、フロー＃ｉごとに個別の加算タイミングＴａ＃ｉを出力する場合を例として説明した。本実施の形態では、タイマ回路１２に１つのバケットタイマ＃Ｓを設け、バケット＃１，＃２，…，＃Ｎのうち、基準となる基準バケット＃Ｓの加算タイミングＴａ＃Ｓを出力し、レートリミット処理回路１４が、この加算タイミングＴａ＃Ｓに基づき、各バケット＃ｉの加算タイミングＴａ＃ｉを内部で計時する場合について説明する。
【００５０】
図７は、第２の実施の形態にかかるバケットタイマの値と加算タイミングを示すタイミングチャート（アップカウンタの場合）である。図８は、第２の実施の形態にかかるバケットタイマの値と加算タイミングを示すタイミングチャート（ダウンカウンタの場合）である。
基準バケット＃Ｓ（Ｓ＝１）に関する加算タイミングＴａ＃Ｓは、バケットタイマ＃Ｓの満了時で、一定の加算周期Ｔｍで繰り返し出力される。バケット＃１，＃２，…，＃Ｎに関する加算タイミングＴａ＃１，＃２，…，＃Ｎは、加算タイミングＴａ＃Ｓからの経過時間がＴｗ×（１−１），Ｔｗ×（２−１），…，Ｔｗ×（Ｎ−１）になる時で、処理時間長Ｔｗだけ順にずらして一定の加算周期Ｔｍで繰り返される。
【００５１】
加算タイミングＴａ＃Ｓからの経過時間は、図７のようにバケットタイマがアップカウントの場合はバケットタイマ＃Ｓの現在値、図８のようにダウンカウントの場合はバケットタイマ＃Ｓの現在値と最大値Ｔｍの差分である。レートリミット処理回路１４は、加算タイミングＴａ＃Ｓを基準として、各バケット＃ｉの加算タイミングＴａ＃ｉを内部で計時する。したがって、タイマ回路１２に関する実装面積を削減することができる。
【００５２】
なお、Ｔｗは、１つのバケット値Ｂｔを加算更新する処理に要する処理時間長を示している。Ｔｍは、Ｎ個すべてのバケット値Ｂｔの加算更新に要する処理時間長を示しており、Ｎ×Ｔｗ分より長い時間長を持つ。これにより、バケット値メモリ回路１１で記憶している各バケット値ＢｔがＢｔ＃１から順にＢｔ＃Ｎまで加算更新され、これが加算周期Ｔｍで繰り返し実行されることになる。
【００５３】
第１の実施の形態では、新たなフレームが入力された場合、直前の加算タイミングＴａからフレーム入力時点Ｔｆまでの経過期間長Ｔｐを計時して、トークンレートＲｔ＃ｉを乗算することにより、バケット値増分ΔＢ＃ｉを計算している。この経過期間長Ｔｐは、バケットタイマがアップカウントの場合はバケットタイマ＃Ｓの現在値、ダウンカウントの場合はバケットタイマ＃Ｓの現在値と最大値Ｔｍの差分である。
【００５４】
しかし、本実施の形態にかかる上記構成を採用した場合、レートリミット処理回路１４には加算タイミングＴａ＃Ｓしか入力されないため、外部からの入力信号をトリガとして経過期間長Ｔｐを計時する場合には、いずれのバケット＃ｉにおいても、経過期間長Ｔｐの計時を開始するタイミングが加算タイミングＴａ＃Ｓに限定されることになる。このため、経過期間長Ｔｐの計時開始タイミング、すなわち加算タイミングＴａ＃Ｓから、実際にバケット値＃ｉが加算更新される加算タイミングＴａ＃ｉまでの期間は、バケット値メモリ回路１１のバケット値Ｂｔ＃ｉが加算更新されていないことになる。
【００５５】
したがって、バケット値Ｂｔ＃ｉが加算更新されていない期間に新たなフレームが入力された場合、入力フレームに対する正確な通過／廃棄判定ができなくなる。
本実施の形態では、このようなケースを回避するため、増分計算部１４Ｂにおいて、加算タイミングＴａ＃Ｓから加算タイミングＴａ＃ｉまでの加算更新前期間に、フロー＃ｉの入力フレームが新たに入力された場合、バケット値増分ΔＢ＃ｉをトークン加算量Ｒｔ＃ｉ×Ｔｍだけ加算するようにしたものである。
【００５６】
［第２の実施の形態の動作］
次に、図９および図１０を参照して、本実施の形態にかかるレートリミット回路１０の動作について説明する。図９は、第２の実施の形態にかかるリートリミット処理に応じたバケット値の変化（フレーム入力：加算更新後期間）を示すタイミングチャートである。図１０は、第２の実施の形態にかかるリートリミット処理に応じたバケット値の変化（フレーム入力：加算更新前期間）を示すタイミングチャートである。
以下では、フレーム入力が、加算更新後期間である場合と加算更新前期間である場合に分けて説明する。
【００５７】
［フレーム入力が加算更新後期間である場合］
まず、図９を参照して、加算タイミングＴａ＃ｉから次の加算タイミングＴａ＃Ｓまでの加算更新後期間にフレームが入力された場合の動作について説明する。
ここでは、フロー＃ｉの入力フレームに対するリートリミット処理のみに注目して説明するものとし、バケット値Ｂｔ＃ｉ、暫定バケット値Ｂｆ＃ｉ、バケットサイズＢｓ＃ｉ、およびトークンレートＲｔ＃ｉを省略して単にＢｔ，Ｂｆ，Ｂｓ，Ｒｔと表すものとする。
【００５８】
まず、時刻Ｔ１Ｓに加算タイミングＴａ＃Ｓが入力された後の、時刻Ｔ１における加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ０を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ１でバケット値メモリ回路１１を更新する。これにより、加算タイミングＴａ＃ｉごとに、バケット値Ｂｔを、直前の加算タイミングＴａ＃Ｓに実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致させることができる。なお、図９の例では、時刻Ｔ１以前のバケット値Ｂｔ０がバケットサイズＢｓに達しているため、時刻Ｔ１におけるバケット値Ｂｔ１もＢｓと等しい値となる。
【００５９】
その後、時刻Ｔ１から時刻Ｔ２Ｓに加算タイミングＴａ＃Ｓが入力されるまでの加算更新後期間のうち、時刻Ｔｆ１にフロー＃ｉの新たなフレームが入力された場合、増分計算部１４Ｂは、直前の加算タイミングＴａ＃Ｓである時刻Ｔ１Ｓから時刻Ｔｆ１までの経過期間長Ｔｐ１に、トークンレートＲｔを乗算することにより、時刻Ｔ１から時刻Ｔｆ１までの間に増加したバケット値増分ΔＢ１を計算する。
【００６０】
続いて、フレーム判定部１４Ｃは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ１に、増分計算部１４Ｂで計算したバケット値増分ΔＢ１を加算することにより、時刻Ｔｆ１における暫定バケット値Ｂｆ１を計算し、入力フレームのフレーム長Ｌと比較する。これにより、加算タイミングＴａ＃ｉの時刻Ｔ１とは異なる時刻Ｔｆ１でフレームが入力されても、実際のトークン量Ｔｋと一致した暫定バケット値Ｂｆ１に基づいて、入力フレームの通過／廃棄を正確に判定することができる。
【００６１】
ここで、図９の例では、バケット値Ｂｔ１がバケットサイズＢｓに達していることから、暫定バケット値Ｂｆ１もＢｓと等しくなるが、Ｂｆ１＞Ｌ１であることから、フレーム判定部１４Ｃは入力フレームに対して通過と判定し、入力フレームを下流へ出力する。
また、バケット値更新部１４Ｄは、フレーム判定部１４Ｃでの通過判定に応じて、暫定バケット値Ｂｆ１からフレーム長Ｌ１とバケット値増分ΔＢ１とを減算することにより、バケット＃ｉの新たなバケット値Ｂｔ１’を計算してバケット値メモリ回路１１に更新記録する。
【００６２】
続いて、時刻Ｔ２Ｓに加算タイミングＴａ＃Ｓが入力された後の、時刻Ｔ２における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ１’を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ２でバケット値メモリ回路１１を更新する。この際、時刻Ｔｆ１において、バケット値更新部１４Ｄにより、バケット値増分ΔＢ１でバケット値Ｂｔ１’が補正されているため、時刻Ｔ２において、バケット値に加算周期Ｔｍ分のトークン加算値Ｒｔ×Ｔｍを一括して加算した時点で、バケット値Ｂｔ２を、直前の加算タイミングＴａ＃Ｓに実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致させることができる。
【００６３】
続く、時刻Ｔ３Ｓに加算タイミングＴａ＃Ｓが入力された後の、時刻Ｔ３における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ２を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ３でバケット値メモリ回路１１を更新する。これにより、時刻Ｔ３において、バケット値Ｂｔ３が、直前の加算タイミングＴａ＃Ｓに実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致することになる。
【００６４】
その後、時刻Ｔ３から時刻Ｔ４Ｓに加算タイミングＴａ＃Ｓが入力されるまでの加算更新後期間のうち、時刻Ｔｆ３にフロー＃ｉの新たなフレームが入力された場合、増分計算部１４Ｂは、直前の加算タイミングＴａ＃Ｓである時刻Ｔ３Ｓから時刻Ｔｆ３までの経過期間長Ｔｐ３に、トークンレートＲｔを乗算することにより、時刻Ｔ３Ｓから時刻Ｔｆ３までの間に増加したバケット値増分ΔＢ３を計算する。
続いて、フレーム判定部１４Ｃは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ３に、増分計算部１４Ｂで計算したバケット値増分ΔＢ３を加算することにより、時刻Ｔｆ３における暫定バケット値Ｂｆ３を計算し、入力フレームのフレーム長Ｌ３と比較する。
【００６５】
ここで、図９の例では、Ｂｆ３＞Ｌ３であることから、フレーム判定部１４Ｃは入力フレームに対して通過と判定し、入力フレームを下流へ出力する。
また、バケット値更新部１４Ｄは、フレーム判定部１４Ｃでの通過判定に応じて、暫定バケット値Ｂｆ３からフレーム長Ｌ３とバケット値増分ΔＢ３とを減算することにより、バケット＃ｉの新たなバケット値Ｂｔ３’を計算してバケット値メモリ回路１１に更新記録する。
【００６６】
続く、時刻Ｔ４Ｓに加算タイミングＴａ＃Ｓが入力された後の、時刻Ｔ４における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ３’を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ４でバケット値メモリ回路１１を更新する。これにより、時刻Ｔ４において、バケット値Ｂｔ４が、直前の加算タイミングＴａ＃Ｓに実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致することになる。
【００６７】
［フレーム入力が加算更新前期間である場合］
次に、図１０を参照して、加算タイミングＴａ＃ｉから次の加算タイミングＴａ＃Ｓまでの加算更新前期間にフレームが入力された場合の動作について説明する。
ここでは、フロー＃ｉの入力フレームに対するリートリミット処理のみに注目して説明するものとし、バケット値Ｂｔ＃ｉ、暫定バケット値Ｂｆ＃ｉ、バケットサイズＢｓ＃ｉ、およびトークンレートＲｔ＃ｉを省略して単にＢｔ，Ｂｆ，Ｂｓ，Ｒｔと表すものとする。
【００６８】
まず、時刻Ｔ１Ｓに加算タイミングＴａ＃Ｓが入力された後の、時刻Ｔ１における加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ０を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ１でバケット値メモリ回路１１を更新する。これにより、加算タイミングＴａ＃ｉごとに、バケット値Ｂｔを、直前の加算タイミングＴａ＃Ｓに実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致させることができる。なお、図１０の例では、時刻Ｔ１以前のバケット値Ｂｔ０がバケットサイズＢｓに達しているため、時刻Ｔ１におけるバケット値Ｂｔ１もＢｓと等しい値となる。
【００６９】
その後、時刻Ｔ２Ｓに加算タイミングＴａ＃Ｓが入力されてから、次の加算タイミングＴａ＃ｉまでの加算更新前期間のうち、時刻Ｔｆ１にフロー＃ｉの新たなフレームが入力された場合、増分計算部１４Ｂは、直前の加算タイミングＴａ＃Ｓである時刻Ｔ２Ｓから時刻Ｔｆ１までの経過期間長Ｔｐ１と加算周期Ｔｍとの和に、トークンレートＲｔを乗算することにより、時刻Ｔ１から時刻Ｔｆ１までの間に増加したバケット値増分ΔＢ１を計算する。
【００７０】
続いて、フレーム判定部１４Ｃは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ１に、増分計算部１４Ｂで計算したバケット値増分ΔＢ１を加算することにより、時刻Ｔｆ１における暫定バケット値Ｂｆ１を計算し、入力フレームのフレーム長Ｌと比較する。これにより、加算タイミングＴａ＃ｉの時刻Ｔ１とは異なる時刻Ｔｆ１でフレームが入力されても、実際のトークン量Ｔｋと一致した暫定バケット値Ｂｆ１に基づいて、入力フレームの通過／廃棄を正確に判定することができる。
【００７１】
ここで、図１０の例では、バケット値Ｂｔ１がバケットサイズＢｓに達していることから、暫定バケット値Ｂｆ１もＢｓと等しくなるが、Ｂｆ１＞Ｌ１であることから、フレーム判定部１４Ｃは入力フレームに対して通過と判定し、入力フレームを下流へ出力する。
また、バケット値更新部１４Ｄは、フレーム判定部１４Ｃでの通過判定に応じて、暫定バケット値Ｂｆ１からフレーム長Ｌ１とバケット値増分ΔＢ１とを減算することにより、バケット＃ｉの新たなバケット値Ｂｔ１’を計算してバケット値メモリ回路１１に更新記録する。
【００７２】
その後、時刻Ｔ２における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ１’を、トークンレートＲｔに加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ２でバケット値メモリ回路１１を更新する。この際、時刻Ｔｆ１において、バケット値更新部１４Ｄにより、バケット値増分ΔＢ１でバケット値Ｂｔ１’が補正されているため、時刻Ｔ２において、バケット値に加算周期Ｔｍ分のトークン加算値Ｒｔ×Ｔｍを一括して加算した時点で、バケット値Ｂｔ２を、直前の加算タイミングＴａ＃Ｓに実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致させることができる。
【００７３】
続く、時刻Ｔ３Ｓに加算タイミングＴａ＃Ｓが入力された後の、時刻Ｔ３における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ２を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ３でバケット値メモリ回路１１を更新する。これにより、時刻Ｔ３において、バケット値Ｂｔ３が、直前の加算タイミングＴａ＃Ｓに実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致することになる。
【００７４】
その後、時刻Ｔ４Ｓに加算タイミングＴａ＃Ｓが入力されてから、次の加算タイミングＴａ＃ｉまでの加算更新前期間のうち、時刻Ｔｆ３にフロー＃ｉの新たなフレームが入力された場合、増分計算部１４Ｂは、直前の加算タイミングＴａ＃Ｓである時刻Ｔ４Ｓから時刻Ｔｆ３までの経過期間長Ｔｐ３と加算周期Ｔｍとの和に、トークンレートＲｔを乗算することにより、時刻Ｔ３Ｓから時刻Ｔｆ３までの間に増加したバケット値増分ΔＢ３を計算する。
続いて、フレーム判定部１４Ｃは、バケット＃ｉと対応するバケット値メモリ回路１１のバケット値Ｂｔ３に、増分計算部１４Ｂで計算したバケット値増分ΔＢ３を加算することにより、時刻Ｔｆ３における暫定バケット値Ｂｆ３を計算し、入力フレームのフレーム長Ｌ３と比較する。
【００７５】
ここで、図９の例では、Ｂｆ３＞Ｌ３であることから、フレーム判定部１４Ｃは入力フレームに対して通過と判定し、入力フレームを下流へ出力する。
また、バケット値更新部１４Ｄは、フレーム判定部１４Ｃでの通過判定に応じて、暫定バケット値Ｂｆ３からフレーム長Ｌ３とバケット値増分ΔＢ３とを減算することにより、バケット＃ｉの新たなバケット値Ｂｔ３’を計算してバケット値メモリ回路１１に更新記録する。
【００７６】
その後、時刻Ｔ４における新たな加算タイミングＴａ＃ｉに応じて、トークン加算処理部１４Ａは、バケット値メモリ回路１１のバケット値Ｂｔ３’を、トークンレートＲｔと加算周期Ｔｍとの積からなるトークン加算量Ｒｔ×Ｔｍだけ一括して加算し、得られたバケット値Ｂｔ４でバケット値メモリ回路１１を更新する。これにより、時刻Ｔ４において、バケット値Ｂｔ４が、直前の加算タイミングＴａ＃Ｓに実際にバケット＃ｉに溜められているべきトークン量Ｔｋと一致することになる。
【００７７】
［第２の実施の形態の効果］
このように、本実施の形態は、タイマ回路１２が、バケットのうち、基準となる基準バケット＃Ｓのバケット値Ｂｔ＃Ｓを加算更新する加算タイミングＴａ＃Ｓを、一定の加算周期Ｔｍで出力し、レートリミット処理回路１４が、加算タイミングＴａ＃Ｓを基準として、バケットに関するバケット値の加算更新が互いに重複することなく順次実行されるように計時した、バケットのそれぞれに関する加算タイミングＴａ＃ｉに応じて、バケット値メモリ回路１１の対応するバケット値を加算更新し、増分計算部１４Ｂが、加算タイミングＴａ＃Ｓから加算タイミングＴａ＃ｉまでの加算更新前期間に、フロー＃ｉの入力フレームが新たに入力された場合、バケット値増分ΔＢ＃ｉをトークン加算量Ｒｔ＃ｉ×Ｔｍだけ加算するようにしたものである。
【００７８】
これにより、新たなフレームが、加算タイミングＴａ＃Ｓから加算タイミングＴａ＃ｉまでの加算更新前期間に入力された場合には、バケット値増分ΔＢ＃ｉがトークン加算量Ｒｔ＃ｉ×Ｔｍだけ加算されるため、その後、実行される加算タイミングＴａ＃ｉにおける加算更新分だけ、フレーム入力時に補正されることになる。したがって、タイマ回路１２から加算タイミングＴａ＃Ｓだけを基準として出力する構成を採用した場合でも、入力フレームの通過／廃棄を正確に判定することができ、結果として、タイマ回路１２に関する実装面積を削減することができる。
【００７９】
［第３の実施の形態］
次に、図１１を参照して、本発明の第３の実施の形態にかかるレートリミット回路１０について説明する。図１１は、第３の実施の形態にかかるレートリミット回路の構成を示すブロック図である。
レートリミット回路１０により、複数のフローについて出力レートを制限する場合、フローによって、バケットサイズＢｓ＃ｉ、トークンレートＲｔ＃ｉ、トークン加算値Ｒｔ＃ｉ×Ｔｍなど、バケットの特性を示すプロファイルが異なる場合がある。
【００８０】
本実施の形態は、これらプロファイルを、それぞれ固有のＩＤと対応させて記憶するプロファイルメモリ回路１３を設けるとともに、バケット値メモリ回路１１で、バケット値ごとに、対応するバケットに適用するプロファイルを示すＩＤを記憶しておき、レートリミット処理回路１４が、フロー＃ｉに関する新たな入力フレームに応じて、バケット値メモリ回路１１からバケット＃ｉのＩＤを取得し、プロファイルメモリ回路１３からＩＤに基づき取得したプロファイルに基づいて、バケット値Ｂｔ＃ｉの加算更新および入力フレームの通過／廃棄判定を行うようにしたものである。
【００８１】
図１１の例では、プロファイルメモリ回路１３に、Ｍ（Ｍは正整数）個のプロファイルが登録されており、それぞれのプロファイルには、バケットサイズＢｓ＃ｉ、トークンレートＲｔ＃ｉ、およびトークン加算値Ｒｔ＃ｉ×Ｔｍが設定されている。
一方、バケット値メモリ回路１１は、それぞれのフロー＃ｉのバケット値Ｂｔ＃ｉごとに、対応するバケット＃ｉで用いるプロファイルを示すＩＤ＃ｉが設定されている。
【００８２】
したがって、レートリミット処理回路１４は、フロー＃ｉに関する新たなフレームが入力された場合、バケット値メモリ回路１１からバケット＃ｉのＩＤを取得し、プロファイルメモリ回路１３からそのＩＤに基づき取得したプロファイルに基づいて、バケット値Ｂｔ＃ｉの加算更新および入力フレームの通過／廃棄判定を行う。
なお、図１１の例では、タイマ回路１２が基準となる加算タイミングＴａ＃Ｓのみを出力する、第２の実施の形態に沿った構成が例として示されているがこれに限定されるものではなく、第１の実施の形態に沿った構成としてもよい。
【００８３】
［第３の実施の形態の効果］
このように、本実施の形態は、バケットの特性を示すプロファイルを、それぞれ固有のＩＤと対応させて記憶するプロファイルメモリ回路１３を設けて、バケット値メモリ回路１１で、バケット値ごとに、対応するバケットに適用するプロファイルを示すＩＤを記憶し、レートリミット処理回路１４が、フロー＃ｉに関する新たな入力フレームに応じて、バケット値メモリ回路１１からバケット＃ｉのＩＤを取得し、プロファイルメモリ回路１３からＩＤに基づき取得したプロファイルに基づいて、バケット値Ｂｔ＃ｉの加算更新および入力フレームの通過／廃棄判定を行うようにしたものである。
【００８４】
これにより、フローごとに、バケットのプロファイルとして、バケットサイズＢｓ＃ｉ、トークンレートＲｔ＃ｉ、およびトークン加算値Ｒｔ＃ｉ×Ｔｍを容易に設定したり選択することができる。したがって、異なるバケットで同じプロファイルを用いる場合には、バケット値メモリ回路１１で同じＩＤを登録しておけばよく、各バケットのプロファイルの設定に要する作業負担を大幅に軽減できる。また、プロファイルを格納するためのメモリの容量を増大させずに、バケット数Nを増やすことが可能となる。
【００８５】
［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。
【符号の説明】
【００８６】
１０…レートリミット回路、１１…バケット値メモリ回路、１２…タイマ回路、１３…プロファイルメモリ回路、１４…レートリミット処理回路、１４Ａ…トークン加算処理部、１４Ｂ…増分計算部、１４Ｃ…フレーム判定部、１４Ｄ…バケット値更新部、Ｔｍ…加算周期、Ｔｗ…処理時間長、Ｔａ…加算タイミング、Ｂｔ…バケット値、Ｂｓ…バケットサイズ、Ｒｔ…トークンレート、Ｔｐ…経過期間長、Ｌ…フレーム長、ΔＢ…バケット値増分、Ｂｆ…暫定バケット値、Ｔｋ…トークン量。
【図１】
2018037827.tif 000003
【図２】
2018037827.tif 000004
【図３】
2018037827.tif 000005
【図４】
2018037827.tif 000006
【図５】
2018037827.tif 000007
【図６】
2018037827.tif 000008
【図７】
2018037827.tif 000009
【図８】
2018037827.tif 000010
【図９】
2018037827.tif 000011
【図１０】
2018037827.tif 000012
【図１１】
2018037827.tif 000013
【図１２】
2018037827.tif 000014
【図１３】
2018037827.tif 000015
【図１４】
2018037827.tif 000016