JP2004080102A

JP2004080102A - Packet processing apparatus

Info

Publication number: JP2004080102A
Application number: JP2002233889A
Authority: JP
Inventors: Kazuhito Yasue; 安江　一仁
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2002-08-09
Filing date: 2002-08-09
Publication date: 2004-03-11
Also published as: US20040028041A1

Abstract

<P>PROBLEM TO BE SOLVED: To control the band of a packet without pressing the band of its own apparatus and to control the band of the packet with high precision in the packet processing apparatus for controlling the band of the packet. <P>SOLUTION: A preprocessing unit 10 imparts a time stamp to the received packet 90. A shared resource unit 40 controls the band of the packet based on the reception sequence information (for example, a time stamp, a sequence number) of each packet 91 dispersed in each distributed processing units 20<SB>-</SB>1-20<SB>-</SB>n. <P>COPYRIGHT: (C)2004,JPO

Description

【０００１】
【発明の属する技術分野】
本発明はパケット処理装置に関し、特にパケット（フレーム）の帯域を制御するパケット処理装置に関するものである。
近年、通信技術の発達に伴い、データだけでなく音声、靜画像、及び動画像等の通信情報量は急速に増大している。このような情報を伝送する通信網においては、各情報のフローが、所定の帯域内のあるか否かを判定して制御を行う帯域制御は、通信の信頼性を確保するためにますます重要である。
【０００２】
【従来の技術】
図１３は、一般的なパケット交換装置の構成例を示している。このパケット交換装置は、物理回線１３０＿１１〜１３０＿１ｉ、物理回線１３０＿２１〜１３０＿２ｉ、…、物理回線１３０＿ｋ１〜１３０＿ｋｉ（以下、符号１３０で総称することがある。）をそれぞれ終端する回線処理部１１０＿１，１１０＿２，…，１１０＿ｋ（以下、符号１１０で総称することがある。）、各回線処理部１１０にそれぞれ接続されたパケット処理装置１００ｚ＿１〜１００ｚ＿ｋ（以下、符号１００ｚで総称することがある。）、及びこれらのパケット処理装置１００ｚ＿１〜１００ｚ＿ｋで接続されたスイッチ１２０で構成されている。
【０００３】
なお、同図では、回線処理部１１０に複数の物理回線１３０が接続されているが、回線処理部１１０に接続される物理回線１３０の数は１本の場合もある。
動作において、例えば、回線処理部１１０＿ｊは、物理回線１３０＿ｊｉからの回線信号から取り出したパケット９０をパケット処理装置１００ｚ＿ｊに転送する。
【０００４】
パケット処理装置１００ｚ＿ｊは、回線処理部１１０＿ｋから受信したパケット９０に対して以下のイングレス（ｉｎｇｒｅｓｓ）処理（１）〜（４）を行った後、スイッチ１２０に転送する。
（１）クラシファイ処理：パケット９０の発信元、宛先、及びプロトコル等に基づきパケット９０のフロー種別を判定する。
【０００５】
（２）フィルタリング処理：透過禁止のパケット９０を廃棄する。
（３）ルーティング処理：パケット９０が持つ宛先情報等に基づき、スイッチ１２０を経由してどのパケット処理装置１００ｚにパケット９０を転送すべきかを決定し、転送先を示す情報（内部タグ）をパケット９０に付与する。
【０００６】
（４）帯域制御処理：上記のクラシファイ処理で指定されたパケット種別毎にパケット流量の制御を行う。
スイッチ１２０は、パケット処理装置１００ｚ＿ｊから受信したパケット９０を、その内部タグが示す、例えばパケット処理装置１００ｚ＿ｋに転送する。
【０００７】
パケット処理装置１００ｚ＿ｋは、スイッチ１２０から受信したパケット９０に対して以下のエグレス（Ｅｇｒｅｓｓ）処理（１）、（２）を行った後、回線処理部１１０に転送する。
（１）フィルタリング処理：透過禁止のパケット９０を廃棄する。
（２）ルーティング処理：パケット９０が持つ宛先情報等に基づき、パケット９０を回線処理部１１０を経由して転送すべき物理回線１３０を決定し、転送先を指定する情報（内部タグ）をパケット９０に付与する。
【０００８】
回線処理部１１０＿ｋは、パケット処理装置１００ｚ＿ｋから受信したパケット９０を内部タグで指定された、例えば物理回線１３０＿ｋ１に回線信号として出力する。
図１４は、パケットを分散して処理する一般的なパケット処理装置１００ｚの構成を示している。このパケット処理装置１００ｚは、パケットを分散して処理することにより処理性能を向上させている。
【０００９】
パケット処理装置１００ｚは、前処理部１０ｚ、分散処理部２０ｚ＿１〜２０ｚ＿ｎ（以下、符号２０ｚで総称することがある。）、共有リソース部４０ｚ、及び後処理部３０ｚで構成されている。この構成は、イングレス処理を行うパケット処理装置１００ｚ及びエグレス処理を行うパケット処理装置１００ｚに共通の構成である。
【００１０】
前処理部１０ｚは、上流から受信したパケットを複数の分散処理部２０ｚ＿１〜２０ｚ＿ｎの内のいずれか１つに送出する。この分散のためのアルゴリズムは、例えば、各分散処理部２０ｚに対応した出力キュー（図示せず）を設け、この出力キューのキュー長を監視する方式、ラウンドロビン方式等がある。
【００１１】
また、前処理部１０ｚは、分散したパケットの順序を下流の後処理部３０ｚで再生できるように、各パケットにシーケンス番号を付与する。
分散処理部２０ｚは、受信したパケットに対する各種処理、例えば、編集処理、検索処理等を行い、処理を完了したパケットを後処理部３０ｚに与える。
【００１２】
共有リソース部４０ｚは、分散処理部２０ｚ＿１〜２０ｚ＿ｎで共有する検索エンジン、共有メモリ等のリソースであり、各分散処理部２０ｚからアクセスされる。
後処理部３０ｚは、各パケットに付与されたシーケンス番号に基づき、前処理部１０ｚに入力されたパケットの順序を再生した後、下流に転送する。
【００１３】
パケット処理装置１００ｚは、さらに、パケットが所定の帯域内にあるか否かを制御する帯域制御、すなわち、所定の帯域に違反しているパケットを廃棄するか、又はマーキング（タグ付け）する等の帯域制御を行う。
ここで、一般的な帯域制御の方式として、（１）ジャンピングウインドウ帯域制御方式、（２）スライディングウインドウ帯域制御方式、及び（３）ＧＣＲＡ（Ｇｅｎｅｒｉｃ　Ｃｅｌｌ　Ｒａｔｅ　Ａｌｇｏｒｉｔｈｍ）帯域制御方式を以下に説明する。
【００１４】
（１）ジャンピングウインドウ帯域制御方式
図１５にジャンピングウインドウ帯域制御方式を示す。この方式は、絶対時間上で区切られた一定の時間幅ＴｗのウインドウＷｎ−１，Ｗｎ，Ｗｎ＋１，Ｗｎ＋２（同図において、ウインドウ時間幅Ｔｗ＝時刻Ｔｎ−Ｔｎ−１＝時刻Ｔｎ＋１−Ｔｎ＝時刻Ｔｎ＋２−Ｔｎ＋１＝時刻Ｔｎ＋３−Ｔｎ＋２）の中でそれぞれ受信したパケットの総バイト数に基づき、帯域を評価する方式である。
【００１５】
この方式は、実装が容易であるが、例えば、過去のウインドウＷｎ−１の情報を次のウインドウＷｎに引き継ぐことが出来ない。例えば、ウインドウＷｎ−１で受信したパケットのバイト数＝“０”であり、次のウインドウＷｎの受信パケットの総バイト数が契約した規定値を超えた場合、ウインドウＷｎ−１とウインドウＷｎで受信したパケットの合計バイト数の平均が規定値を越えない場合においても、帯域違反と判定される。
【００１６】
（２）スライディングウインドウ帯域制御方式
図１６に、スライディングウインドウ帯域制御方式を示す。この方式は、例えば、パケットｆａ，ｆｂ，ｆｃが到着する毎に、その到着時点Ｔａ，Ｔｂ，Ｔｃから過去一定時間幅Ｔｗのウインドウ内で受信したパケットの総バイト数に基づき、帯域を評価する。
【００１７】
この方式は、帯域をダイナミックに評価することができるが、実装は難しい。
（３）ＧＣＲＡ帯域制御方式
図１５にＧＣＲＡ帯域制御方式を示す。この方式は、連続する２つのパケットの受信間隔に基づき、帯域を評価する方式であり、論理的には、リーキバケット（ＬｅａｋｙＢｕｃｋｅｔ）帯域制御方式と等価である。
【００１８】
ＧＣＲＡ帯域制御方式のアルゴリズムを以下に説明する。
ここで、ＴＡＴ＝パケットの論理到着時刻（Ｔｈｅｏｒｅｔｉｃａｌ　Ａｒｒｉｖａｌ　Ｔｉｍｅ）、Ｔ＝実際のパケット到着時刻（Ｔｉｍｅ）、Ｉ＝増加パラメータ（Ｉｎｃｒｅｍｅｎｔ　Ｐａｒａｍｅｔｅｒ）、Ｌ＝リミットパラメータ（Ｌｉｍｉｔ　Ｐａｒａｍｅｔｅｒ）、ｎ＝パケット長（Ｐａｃｋｅｔ　Ｌｅｎｇｔｈ）とする。この内のＩ，Ｌの値は予め設定されている。
【００１９】
▲１▼制御を開始した後、最初に受信したパケットは、無条件に帯域制御結果＝“適合”と判定し、次式（１）で次のＴＡＴを算出する。
ＴＡＴ＝Ｔ＋ｎＩ　　　　　　　　　・・・式（１）
▲２▼以後、パケット（長さｎ、到着時刻Ｔ）受信毎にＴＡＴとの比較を行い、“適合”又は“非適合”の判定及び次のＴＡＴの算出を行う。
【００２０】
（ａ）比較結果：ＴＡＴ＜Ｔ（時刻ＴＡＴより後にパケットを受信、同図（１）参照）である場合、帯域制御結果＝“適合”とし、次式（２）で時刻Ｔを基点として次のＴＡＴを算出する。
ＴＡＴ＝Ｔ＋ｎＩ　　　　　　　　　・・・式（２）
（ｂ）比較結果：ＴＡＴ−Ｌ≦Ｔ≦ＴＡＴである場合（時刻（ＴＡＴ−Ｌ）より後かつ時刻ＴＡＴ前にパケットを受信した場合、同図（２）参照）、帯域制御結果＝“適合”とし、現在のＴＡＴを基点として次式（３）で次のＴＡＴを算出する。
【００２１】
次のＴＡＴ＝現在のＴＡＴ＋ｎＩ　　　・・・式（３）
（ｃ）比較結果：Ｔ＜ＴＡＴ−Ｌである場合（時刻（ＴＡＴ−Ｌ）より前にパケットを受信した場合、同図（３）参照）、帯域制御結果＝“不適合”とし、次式（４）で次のＴＡＴを算出する。すなわち、ＴＡＴの更新を行わない。
【００２２】
次のＴＡＴ＝現在のＴＡＴ　　　　　　　　　　・・・式（４）
【００２３】
【発明が解決しようとする課題】
このような帯域制御を分散処理部２０ｚで行った場合、各分散処理部２０ｚにパケットが分散されるためパケットの連続性が保たれず、したがって、精度の高い帯域制御を行うことは出来なかった。そこで、従来の帯域制御は、（１）前処理部１０ｚで行う方式、又は（２）後処理部３０ｚで行う方式があった。
【００２４】
（１）前処理部で帯域制御を行う方式
この方式は、分散処理を行う前であるため、パケット間隔の揺らぎが少なく、精度の高い帯域制御ができるという利点がある。しかしながら、帯域制御を行うためには、それ以前にクラシファイ処理を行う必要があり、これに伴って処理情報が発生することにより帯域を圧迫する。
【００２５】
（２）後処理部で帯域制御を行う方式
この方式は、分散処理部２０ｚ若しくは共有リソース部４０ｚでクラシファイ処理を行うことができる利点がある。しかしながら、分散処理部２０ｚ若しくは共有リソース部４０ｚが、クラシファイ結果情報を後処理部３０ｚに通知ための情報が必要であるため帯域の圧迫を招く。
【００２６】
また、上流でパケットがフロー分散及び合流されているため、パケット間隔の揺らぎが大きくなり、帯域制御の精度が低くなる欠点がある。
従って本発明は、パケットの帯域を制御するパケット処理装置において、自装置の帯域を圧迫することなくパケットの帯域制御を行うこと、また精度の高いパケット帯域制御を行うことを課題とする。
【００２７】
【課題を解決するための手段】
上記の課題を解決するため、本発明のパケット処理装置は、受信したパケットを複数の出力端子の内のいずれか１つに送出する前処理部と、各出力端子にそれぞれ接続されて各出力端子からの該パケットを処理する複数の分散処理部と、各分散処理部に分散された各パケットの受信順序情報に基づき、該パケットの帯域制御を行う共有リソース部と、各分散処理部からのパケットを合流して出力する後処理部と、を備えたことを特徴としている（請求項１、付記１）。
【００２８】
本発明のパケット処理装置１００は、図１４に示した一般的なパケット処理装置１００ｚと基本的な構成は同じであり、従来の前処理部１０ｚ、分散処理部２０ｚ＿１〜２０ｚ＿ｎ、共有リソース部４０ｚ、及び後処理部３０ｚの代わりに、前処理部１０、ｎ個の分散処理部２０＿１〜２０＿ｎ（以下符号２０で総称することがある。）、共有リソース部４０、及び後処理部３０で構成されている。
【００２９】
本発明のパケット処理装置１００が従来のパケット処理装置１００ｚと基本的に異なる点は、共有リソース部４０が、各分散処理部２０に分散されたパケットの受信順序情報を収集し、この情報に基づきパケットの帯域制御を行うことである。
すなわち、前処理部１０は、受信したパケットを、複数の出力端子の内から、例えば、従来の所定のアルゴリズムで選択した１つの出力端子に送出する。
【００３０】
各分散処理部２０＿１〜２０＿ｎは、それぞれ前処理部１０の出力端子から受信したパケットの処理を行う。
共有リソース部４０は、分散処理部２０＿１〜２０＿ｎに分散されているパケットの受信順序情報に基づき、パケットが所定の帯域内にあるか否かを判定する帯域制御を行う。
【００３１】
後処理部３０は、分散処理部で処理されたパケットを合流して出力する。
従って、本発明のパケット処理装置は、帯域制御結果に基づき自装置における帯域を圧迫すること無く、例えば、帯域違反のパケットの廃棄、又は下流に対して帯域違反の通知、さらにはパケットの送信元に帯域違反通知等を行いパケットの帯域制御が実現できる。
【００３２】
このように、分散処理部に分散されているパケットの帯域制御を共有リソース部４０で行うことが可能になり、余分な処理情報や通知情報が不要であるため帯域を圧迫することなくパケットを帯域制御することが可能になる。
なお、上記のパケットの廃棄、及び帯域違反の通知等の処理は、本発明の帯域制御結果に基づき、例えば、分散処理部、後処理部その他等の所定の処理部で行われる。
【００３３】
また、本発明は、上記の本発明において、該受信順序情報を、パケットに付与された時間情報とすることができる（請求項２、付記２）。
すなわち、共有リソース部４０は、パケットに付与された時間情報（例えば、タイムスタンプ）に基づき、パケットの正確な時系列上の位置を判別し、帯域制御を行う。これにより、パケットに時間情報を付与した時点から帯域制御前までの間の処理で発生する時系列上のパケットの揺らぎを補正することが可能になり、精度の良い帯域制御が可能になる。
【００３４】
また、本発明は、上記の本発明において、該前処理部は、該時間情報をパケットに付与することができる（請求項３、付記３）。
また、本発明は、上記の本発明において、該分散処理部は、該時間情報をパケットに付与することができる（付記４）。
【００３５】
すなわち、時間情報（タイムスタンプ）を、前処理部１０又は分散処理部２０でパケットに付与することが可能である。なお、時間情報の時系列上の揺らぎは、時間情報が前処理部１０で付与された方が分散処理部２０で付与された方より少なく、正確な帯域制御ができる。
【００３６】
例えば、前処理部１０が最前段でパケットにタイムスタンプを付与した場合、前処理部１０の後段の処理や分散処理部２０の分散処理に起因するパケットの揺らぎに影響されることなく、共有リソース部４０はパケットが前処理部１０に到着した時刻に基づき正確な帯域制御を行うことが可能になる。
【００３７】
また、本発明は、上記の本発明において、該共有リソース部は、該時間情報に基づき、該パケットを時系列順に並びかえる順序補正処理部を備えることができる（付記５）。
すなわち、順序補正処理部は、例えば、各分散処理部２０に分散処理されたため、時系列上の順序が変わってしまったパケットの順序を、このパケットに付与された時間情報（タイムスタンプ）に基づき、元に戻す。
【００３８】
これにより、パケットを時系列順に処理することが可能になり、帯域制御が容易になる。
また、本発明は、上記の本発明において、該受信順序情報が、さらに、該前処理部がパケットに付加した、パケットの受信順序を示すシーケンス番号を含み、該共有リソース部が、該シーケンス番号に基づき、該パケットを時系列順に並びかえる順序補正処理部を備えることができる（請求項４、付記６）。
【００３９】
これによっても、パケットを時系列順に処理することが可能になり、帯域制御が容易になる。
また、本発明は、上記の本発明において、該共有リソース部は、ジャンピングウインドウ帯域制御方式、スライディングウインドウ帯域制御方式、及びＧＣＲＡ帯域制御方式の内のいずれか１つの方式で帯域制御することができる（付記７）。
【００４０】
すなわち、共有リソース部４０は、図１５に示したジャンピングウインドウ帯域制御方式、図１６に示したスライディングウインドウ帯域制御方式、又は図１７に示したＧＣＲＡ帯域制御方式で帯域制御してもよい。
また、本発明は、上記の本発明において、該共有リソース部は、パケットをフロー別に分類するクラシファイ処理部をさらに備え、フロー別に帯域制御を行うことが可能である（請求項５、付記８）。
【００４１】
また、本発明は、上記の本発明において、各分散処理部は、パケットをフロー別に分類するクラシファイ処理部をさらに備え、該共有リソース部はフロー別に帯域制御を行うことができる（付記９）。
また、本発明は、上記の本発明において、該前処理部は、パケットをフロー別に分類するクラシファイ処理部をさらに備え、該共有リソース部はフロー別に帯域制御を行うことができる（付記１０）。
【００４２】
すなわち、クラシファイ処理部６０を、共有リソース部４０、分散処理部２０、又は前処理部１０に配置する。クラシファイ処理部６０は、パケットをフロー別に分類し、共有リソース部４０がフロー別に帯域制御を実施する。
これにより、フロー別の帯域制御が可能になる。なお、クラシファイ処理部の配置位置は、最も帯域を圧迫しないところを選択すればよく、一般的に分散処理部２０にクラシファイ処理部を配置する方式が、クラシファイ処理が分散されるため帯域圧迫が少ない。
【００４３】
また、本発明は、上記の本発明において、該受信順序情報が、該パケットの受信順序を示すシーケンス番号であり、該共有リソース部が、該パケットを該シーケンス番号順に並び変える順序補正処理部と、該パケットが自分自身に入力された時刻を計時するタイマとをさらに備え、該時刻に基づき帯域制御することが可能である（付記１１）。
【００４４】
すなわち、受信順序情報として、パケットの受信順序を示すシーケンス番号を用いる。共有リソース部４０は、さらに、順序補正処理部及びタイマを備えている。順序補正処理部はパケットをシーケンス番号順に並び変え、タイマは、パケットが共有リソース部４０に入力した時刻を計時し、この時刻に基づき、共有リソース部４０はパケットの帯域制御を行う。
【００４５】
これによっても、共有リソース部４０は帯域制御を行うことができる。すなわち、パケットが分散処理部２０に分散した場合においても、パケットが共有リソース部４０に到着した時刻に基づき帯域制御を行うことが可能になる。
なお、この帯域制御では、パケットにタイムスタンプを付与する必要はない。
【００４６】
さらに、本発明は、上記の本発明において、該前処理部が、該パケットに該シーケンス番号を付加してもよい（付記１２）。
【００４７】
【発明の実施の形態】
図１は、本発明に係るパケット処理装置１００の実施例を示している。このパケット処理装置１００は、図１４で示した一般的なパケット処理装置１００ｚと同様に、前処理部１０、分散処理部２０＿１〜２０＿ｎ、後処理部３０、及び共有リソース部４０で構成されている。
【００４８】
図１では、共有リソース部４０が、特に詳細に示されており、この共有リソース部４０が、順序補正処理部５０、クラシファイ処理部６０、及び帯域制御処理部７０で構成されていることが特徴である。
図２は、図１に示した前処理部１０の実施例を示している。この前処理部１０は、タイマ１１と、受信したパケット９０にタイマ１１が示す時刻、すなわち、タイムスタンプ９０ｃを付加して出力するタイムスタンプ付与部１２と、パケット９０にさらにシーケンス番号９０ｄを付与したパケット９１を出力するシーケンス番号付与部１３とを備えている。
【００４９】
さらに、前処理部１０は、パケット９１をｎ本の出力端子の内のいずれかに出力する出力キュースイッチ１４と、出力キュースイッチ１４の各出力端子に接続され、出力キュースイッチ１４から与えられたパケット９１をキューイングするキュー１５＿１〜１５＿ｎ（以下、符号１５で総称することがある。）と、キュー１５のキューイング状態を検出し、例えば、キューイングされているバイト数が最も少ないキュー１５を検出し、このキュー１５に次のパケット９１を与える指示を出力キュースイッチ１４に与える出力キュー指示部１６とを備えている。
【００５０】
図３（１）は、前処理部１０に入力されるパケット９０のフォーマット例を示している。このパケット９０は、ペイロード９０ａ及びパケットヘッダ９０ｂ（例えば、ＩＰｖ４ヘッダ）で構成されている。
同図（２）は、出力キュースイッチ１４に与えられるパケット９１のフォーマット例を示している。このパケット９１は、同図（１）に示したパケット９０と、このパケット９０に付与されたタイムスタンプ９０ｃ及びシーケンス番号９０ｄとで構成されている。
【００５１】
図４は、図１に示した分散処理部２０の動作例を示している。分散処理部２０は、前処理部１０から受信したパケット９１＿２，９１＿４，９１＿７（以下、符号９１で総称することがある。）を順次受信し、これらのパケット９１にそれぞれ付与されたシーケンス番号９０ｄ、タイムスタンプ９０ｃ等から成る情報９２＿２，９２＿４，９２＿７（以下、符号９２で総称することがある。）を共有リソース部４０に与える。
【００５２】
図５は、分散処理部２０及び共有リソース部４０で伝送される各情報例を示している。同図（１）は、情報９２の構成例を示している。この情報９２は、シーケンス番号９０ｄ、タイムスタンプ９０ｃ、パケット長９０ｅ、及びパケット情報９０ｈで構成されている。パケット情報９０ｈは、パケット９１のクラシファイに必要な情報、例えば宛先ＩＰアドレス、送信元ＩＰアドレス、又はＬ４プロトコル等である。
【００５３】
また、分散処理部２０は、逆に、共有リソース部４０から帯域制御結果であるタグ情報９０ｇとシーケンス番号９０ｄとから成る情報９４＿２，９４＿４，９４＿７（以下、符号９４で総称することがある。）を受信する。図５（３）は、この情報９４のフォーマット例を示しており、この情報９４は、シーケンス番号９０ｄとタグ情報９０ｇで構成されている。
【００５４】
さらに、分散処理部２０は、パケット９１のタイムスタンプ９０ｃ（図３（２）参照）の代わりに、自パケット９１に付与されたシーケンス番号９０ｄと同じシーケンス番号９０ｄの情報９４のタグ情報９０ｇを付与したパケット９５を後処理部３０に与える。
図５（４）は、パケット９５のフォーマット例を示しており、このパケット９５は、パケット９０、シーケンス番号９０ｄ、タグ情報９０ｇで構成されている。同図（３）については後述する。
【００５５】
図６は、情報９２の受信順序を補正する実施例（１）を示しており、この実施例（１）では、各分散処理部２０が、前処理部１０から受信したパケット９１の受信順序と同じ順序で情報９２（図５（３）参照、図６では、シーケンス番号９０ｄのみを示す。）を順序補正処理部５０ａに与える。
【００５６】
順序補正処理部５０ａは、分散処理部２０＿１〜２０＿ｎにそれぞれ対応したキュー（ＦＩＦＯ）５１＿１〜キュー５１＿ｎ（以下、符号５１で総称することがある。）及びセレクタ５２で構成されている。
キュー５１は、分散処理部２０から受信した情報９２をＦＩＦＯで記憶し、セレクタ５２は、全各キュー５１の中から一番若いシーケンス番号９０ｄの情報９２を選択してクラシファイ処理部６０に与える。
【００５７】
これにより、前処理部１０に入力されたパケット９０の順序と同じ順序で対応するパケット９０の情報９２が、クラシファイ処理部６０に与えられる。
図７は、情報９２の受信順序を補正する実施例（２）を示しており、この実施例（２）では、各分散処理部２０は、実施例（１）と異なり、パケット９１が自装置２０に入力された順と異なる順でパケット９１に対応する情報９２を順序補正処理部５０ｂに与える。
【００５８】
例えば、分散処理部２０＿１は、シーケンス番号９０ｄがそれぞれ“４１”、“４２”、“４７”であるパケット９１＿１，９１＿２，９１＿７を順次受信し、そして、シーケンス番号９０ｄがそれぞれ“４７”、“４１”、“４２”である情報９２＿７，９２＿１，９２＿２を順序補正処理部５０ｂに与える。
【００５９】
分散処理部２０の内部処理が分散して行われているようなとき、このような順序保存されない場合が発生する。
なお、図６と同様に図７では、各パケット９１及び情報９２には、シーケンス番号９０ｄのみが示され、タイムスタンプ９０ｃ等は省略されている。
【００６０】
順序補正処理部５０ｂは、バッファ５３を備えており、このバッファ５３に分散処理部２０＿１〜２０＿ｎから受信した情報９２＿０，９２＿１〜９２＿８を、シーケンス番号９０ｄの順に並べて記憶する。そして、順序補正処理部５０ｂは、シーケンス番号９０ｄの順（４０，４１，…，４８，…）にバッファ５３から情報９２を読み出してクラシファイ処理部６０に与える。
【００６１】
なお、図６及び図７において、分散処理部２０又は順序補正処理部５０ａは、シーケンス番号９０ｄの代わりにタイムスタンプ９０ｃを用いてパケットの順序を補正してもよい。この場合、シーケンス番号９０ｄは不要である。
図８は、クラシファイ処理部６０の実施例を示している。このクラシファイ処理部６０は、ＣＡＭ（Ｃｏｎｔｅｎｔ　Ａｄｄｒｅｓｓ　Ｍｅｍｏｒｙ）アクセス制御部６１とＣＡＭ・ＲＡＭ部６２で構成されている。
【００６２】
ＣＡＭ・ＲＡＭ部６２には、パケット情報９０ｈに対応するフロー番号９０ｆが登録されている。
ＣＡＭアクセス制御部６１は、情報９２の内のクラシファイ用パケット情報９０ｈ（図５（１）参照）をＣＡＭ・ＲＡＭ部６２に与え、パケット情報９０ｈに対応するフロー番号９０ｆを読出し、情報９２の内のパケット情報９０ｈの代わりにフロー番号９０ｆを付加した情報９３を帯域制御処理部７０に与える。
【００６３】
この情報９３は図５（２）に示されている。この情報９３は、シーケンス番号９０ｄ、タイムスタンプ９０ｃ、パケット長９０ｅ、及びフロー番号９０ｆで構成されている。
帯域制御処理部７０の実施例（１）〜（３）を図９〜図１２を用いて以下に説明する。
図９は、帯域制御処理部７０の実施例（１）を示している。この実施例（１）では、特に、図１５で説明したジャンピングウインドウ帯域制御方式の帯域制御処理部７０ａを示している。
【００６４】
帯域制御処理部７０ａは、各フロー番号９０ｆに対応した許容バイト数７２＿１及び受信バイト数７２＿２を記憶するメモリ７１を備えている。許容バイト数７２＿１には、フロー番号９０ｆに対応したフローの許容バイト数（このバイト数は許容設定帯域に対応）が予め登録されており、受信バイト数７２＿２には、フロー番号９０ｆに対応したフローの一定時間Ｔに受信した受信バイト数が記憶される。受信バイト数の初期値は“０”である。
【００６５】
帯域制御処理部７０ａの動作手順を以下に説明する。なお、この動作手順は、フロー番号毎に実行される。
ステップＳ１０：帯域制御処理部７０ａは、フロー番号９０ｆをメモリ７１に与え、これに対応する許容バイト数７２＿１及び受信バイト数７２＿２を読み出す。
【００６６】
ステップＳ１１：処理部７０ａは、新たな受信バイト数７２＿２＝前の受信バイト数７２＿２＋パケット長（バイト数）９０ｅで更新し、この新たな受信バイト数７２＿２をステップＳ１０で与えたフロー番号９０ｆと同一のフロー番号に対応する受信バイト数７２＿２に書き込む。
【００６７】
ステップＳ１２：処理部７０ａは、新たな受信バイト数７２＿２と許容バイト数７２＿１を比較し、フローの設定許容帯域が守られている否かを判定し、判定結果をタグ付けした情報９４（図５（３）参照）を分散処理部２０に与える。
図５（３）の説明で述べたように、この情報９４は、シーケンス番号９０ｄとタグ情報９０ｇで構成されている。タグ情報９０ｇは、例えば、許容帯域が守られていることを示す“ＯＫ”又は許容帯域違反を示す“ＮＧ”で構成してもよいし、又は“緑”、“黄”、又は“赤”等のカラー情報で構成してもよい。
【００６８】
ステップＳ１３：帯域制御処理部７０ａは、受信したタイムスタンプ９０ｃを参照して一定時間Ｔ毎にメモリ７１にエントリされた全受信バイト数７２＿２をクリアする。
なお、タイムスタンプ９０ｃを用いずに、帯域制御処理部７０ａにタイマ（図示せず）を備え、このタイマに基づき一定時間毎に全受信バイト数７２＿２をクリアしてもよい。この場合、タイムスタンプ９０ｃの情報は不要である。
【００６９】
前処理部１０にパケット９０が入力した時刻を示したタイムスタンプ９０ｃに基づく帯域制御は、帯域制御処理部７０ｃに情報９３が入力した時刻に基づく帯域制御より、前処理部１０及び分散処理部２０における処理に起因する情報９３間の揺れがないため、精度のよい帯域制御が可能である。
【００７０】
図１０は、帯域制御処理部７０の実施例（２）を示している。この実施例（２）では、特に、図１６で説明したスライディングウインドウ帯域制御方式の帯域制御処理部７０ｂを示している。
帯域制御処理部７０ｂは、フロー番号９０ｆに対応した許容バイト数７３＿１及び受信バイト数７３＿２〜７３＿ｍを記憶するメモリ７１を備えている。許容バイト数７３＿１には、フロー番号９０ｆに対応したフローの許容バイト数（設定許容帯域に対応）が予め登録されている。
【００７１】
受信バイト数７３＿２〜７３＿ｍには、フロー番号９０ｆに対応した受信したフローの受信バイト数が記憶される。受信バイト数７３＿２〜７３＿ｍの初期値は“０”である。
帯域制御処理部７０ｂの動作手順を以下に説明する。なお、この動作手順は、フロー番号毎に実行される。
【００７２】
ステップＳ２０：帯域制御処理部７０ｂは、受信した情報９３のフロー番号９０ｆをメモリ７１に与え、許容バイト数７３＿１、及び受信バイト数７３＿２〜７３＿ｍを読み出す。
ステップＳ２１：処理部７０ｂは、新しい受信バイト数７３＿２＝前の受信バイト数７３＿２＋パケット長９０ｅ（バイト数）で更新し、新しい受信バイト数７３＿２をメモリ７１の受信バイト数７３＿２に書き込む。
【００７３】
ステップＳ２２：処理部７０ｂは、受信バイト数７３＿２〜７３＿ｍを合計し、この合計バイト数と許容バイト数を比較し、設定許容帯域が守られている否かを判定し、この判定結果をタグ付けした情報９４（図５（３）参照）を分散処理部２０に与える。
ステップＳ２３：処理部７０ｂは、受信した情報９３のタイムスタンプ９０ｃに基づき、一定時間間隔ｔ毎に受信バイト数をシフト（受信バイト数７３＿ｍ←受信バイト数７３＿（ｍ−１），…，受信バイト数７３＿３←受信バイト数７３＿２，受信バイト数７３＿２←“０”（クリア））する。
【００７４】
なお、受信バイト数７３＿２〜７３＿ｍの数（ｍ−１）は、シフトする時間間隔ｔとウインドウ時間幅Ｔｗとで決まる。
また、タイムスタンプ９０ｃを用いずに、帯域制御処理部７０ａにタイマを備え、このタイマに基づき一定時間毎にシフトしてもよい。この場合、タイムスタンプ９０ｃは不要であるが、帯域制御処理部７０ａに情報９３に到着した時刻に基づき元のパケット９０の帯域制御を行うことになり、実施例（１）と同様に帯域制御に揺れが発生する。
【００７５】
図１１は、帯域制御処理部７０の実施例（３）を示している。この実施例（３）では、特にＧＣＲＡ帯域制御方式の帯域制御処理部７０ｃを示している。
帯域制御処理部７０ｃは、各フロー番号９０ｆに対応した帯域設定情報７４＿１（Ｉ：増加パラメータ、Ｌ：リミットパラメータ）及び次パケット到着予定時刻７４＿２（ＴＡＴ：論理到着時刻）を記憶するメモリ７１を備えている。増加パラメータＩ及びリミットパラメータＬは予め登録されている。
【００７６】
次パケット到着予定時刻７４＿２には、図１７の説明で示した式（１）〜（４）で計算した論理到着時刻ＴＡＴが記憶される。論理到着時刻ＴＡＴの初期値は“０”である。
帯域制御処理部７０ｃの動作手順を以下に説明する。なお、この動作手順は、フロー番号９０ｆ毎に実行される。
【００７７】
ステップＳ３０：帯域制御処理部７０ｃは、受信した情報９３（図５（２）参照）のフロー番号９０ｆをメモリ７１に与え、フロー番号９０ｆに対応する帯域設定情報７４＿１及び次パケット到着予定時刻７４＿２を読み出す。
ステップＳ３１：処理部７０ｃは、タイムスタンプ９０ｃ（＝実際のパケット到着時刻Ｔ）と到着予定時刻７４＿２（論理到着時刻ＴＡＴ）を比較して設定許容帯域が守られているか否かを判定し、その判定結果をタグ付けした情報９４を作成する。
【００７８】
ステップＳ３２：処理部７０ｃは、パケット到着時刻Ｔの条件（図１７（１）〜（３）参照）に基づき選択した式（１）〜（４）の内のいずれか１つを選択し、選択した式で論理到着時刻ＴＡＴを計算する。さらに、処理部７０ｃは、計算結果を当該フロー番号９０ｆに対応するメモリ７１内の次パケット到着予定時刻７４＿２に書き込むと共に、情報９４（図５（３）参照）を分散処理部２０に与える。
【００７９】
図１２は、図１１に示した帯域制御処理部７０ｃのより詳細な動作を示している。この詳細動作を以下に説明する。
処理部７０ｃは、クラシファイ処理部６０から情報９３（フロー番号９０ｆ、パケット長（ｎ）９０ｅ、タイムスタンプ（Ｔ）９０ｃ、及びシーケンス番号９０ｄ、図５（２）参照）を受信する。
【００８０】
処理部７０ｃは、フロー番号９０ｆをメモリ７１に与え、帯域設定情報７４＿１（＝増加パラメータＩ、リミットパラメータＬ）及び次パケット到着予定時刻７４＿２（＝論理到着時刻ＴＡＴ）を読み出す。
乗算器７０１は、パケット長ｎと増加パラメータＩを乗算した積（ｎ×Ｉ）を出力する。加算器７０２は、パケット論理到着時刻ＴＡＴと積（ｎ×Ｉ）を加算した和（ＴＡＴ＋ｎ×Ｉ）を出力する。加算器７０３は、時刻Ｔと積（ｎ×Ｉ）を加算した和（Ｔ＋ｎ×Ｉ）を出力する。
【００８１】
減算器７０５は、論理到着時刻ＴＡＴとリミットパラメータＬとの差（ＴＡＴ−Ｌ）を出力し、比較器７０６は、差（ＴＡＴ−Ｌ）とＴを比較し、（ＴＡＴ−Ｌ）＜ＴであるときＳＥＬ１＝“１”を出力し、Ｔ≦（ＴＡＴ−Ｌ）であるときＳＥＬ１＝“０”を出力する。比較器７０７は、ＴＡＴとＴを比較し、ＴＡＴ＜ＴであるときＳＥＬ０＝“１”を出力し、Ｔ≦ＴＡＴであるときＳＥＬ０＝“０”を出力する。
【００８２】
セレクタ７０４は、（ＳＥＬ０，ＳＥＬ１）＝（０，０）、（０，１）、又は（１，１）のとき、それぞれ、“ＴＡＴ”、“ＴＡＴ＋ｎ×Ｉ”、又は“Ｔ＋ｎ×Ｉ”を選択して出力する。
この選択されデータは、メモリ７１内の次パケット到着予定時刻７４＿２に書き込まれる。
【００８３】
これにより、Ｔ≦（ＴＡＴ−Ｌ）のとき、次のＴＡＴ＝現在のＴＡＴ、（ＴＡＴ−Ｌ）＜Ｔ≦ＴＡＴであるとき、次のＴＡＴ＝ＴＡＴ＋ｎ×Ｉ、ＴＡＴ＜Ｔであるとき、次のＴＡＴ＝“Ｔ＋ｎ×Ｉ”とする。
ＯＲ回路７０８は、ＳＥＬ０及びＳＥＬ１の論理和演算を行い、帯域制御結果として、適合＝“１”又は非適合＝“０”を出力する。この帯域制御結果をタグ付けした情報９４は、分散処理部２０に送信される。
【００８４】
この後、帯域制御結果に基づき、パケット９１等の廃棄等の所定の制御が行われる。
（付記１）
受信したパケットを複数の出力端子の内のいずれか１つに送出する前処理部と、
各出力端子にそれぞれ接続されて各出力端子からの該パケットを処理する複数の分散処理部と、
各分散処理部に分散された各パケットの受信順序情報に基づき、該パケットの帯域制御を行う共有リソース部と、
各分散処理部からのパケットを合流して出力する後処理部と、
を備えたことを特徴とするパケット処理装置。
【００８５】
（付記２）上記の付記１において、
該受信順序情報は、パケットに付与された時間情報であることを特徴としたパケット処理装置。
（付記３）上記の付記２において、
該前処理部が、該時間情報をパケットに付与することを特徴としたパケット処理装置。
【００８６】
（付記４）上記の付記２において、
該分散処理部が、該時間情報をパケットに付与することを特徴としたパケット処理装置。
（付記５）上記の付記２において、
該共有リソース部が、該時間情報に基づき、該パケットを時系列順に並びかえる順序補正処理部を有することを特徴としたパケット処理装置。
【００８７】
（付記６）上記の付記２において、
該受信順序情報が、さらに、該前処理部がパケットに付加した、パケットの受信順序を示すシーケンス番号を含み、
該共有リソース部が、該シーケンス番号に基づき、該パケットを時系列順に並びかえる順序補正処理部を有することを特徴としたパケット処理装置。
【００８８】
（付記７）上記の付記１において、
該共有リソース部は、ジャンピングウインドウ帯域制御方式、スライディングウインドウ帯域制御方式、及びＧＣＲＡ帯域制御方式の内のいずれか１つの方式で帯域制御することを特徴としたパケット処理装置。
【００８９】
（付記８）上記の付記１において、
該共有リソース部は、パケットをフロー別に分類するクラシファイ処理部をさらに備え、フロー別に帯域制御を行うことを特徴としたパケット処理装置。
（付記９）上記の付記１において、
各分散処理部は、パケットをフロー別に分類するクラシファイ処理部をさらに備え、該共有リソース部がフロー別に帯域制御を行うことを特徴としたパケット処理装置。
【００９０】
（付記１０）上記の付記１において、
該前処理部は、パケットをフロー別に分類するクラシファイ処理部をさらに備え、該共有リソース部がフロー別に帯域制御を行うことを特徴としたパケット処理装置。
【００９１】
（付記１１）上記の付記１において、
該受信順序情報が、該パケットの受信順序を示すシーケンス番号であり、
該共有リソース部が、該パケットを該シーケンス番号順に並び変える順序補正処理部と、該パケットが自分自身に入力された時刻を計時するタイマと、をさらに備え、該時刻に基づき帯域制御することを特徴としたパケット処理装置。
【００９２】
（付記１２）上記の付記１１において、
該前処理部が、該パケットに該シーケンス番号を付加することを特徴としたパケット処理装置。
【００９３】
【発明の効果】
以上説明したように、本発明に係るパケット処理装置によれば、共有リソース部が、各分散処理部に分散された各パケットの受信順序情報（例えば、タイムスタンプ、シーケンス番号）に基づき、該パケットの帯域制御を行うように構成したので、自装置の帯域を圧迫することなくパケットの帯域制御を行うことが可能になる。
【００９４】
また、好ましくは前処理部が、受信したパケットにタイムスタンプを付与するようにしたので、精度の高いパケット帯域制御を行うことが可能になる。
【図面の簡単な説明】
【図１】本発明に係るパケット処理装置の実施例を示したブロック図である。
【図２】本発明に係るパケット処理装置における前処理部の実施例を示したブロック図である。
【図３】本発明に係るパケット処理装置における前処理部におけるパケットのフォーマット例を示した図である。
【図４】本発明に係るパケット処理装置における分散処理部の動作例を示した図である。
【図５】本発明に係るパケット処理装置における各情報のフォーマット例を示した図である。
【図６】本発明に係るパケット処理装置の分散処理部及び順序補正処理部における順序補正の実施例（１）を示したブロック図である。
【図７】本発明に係るパケット処理装置の分散処理部及び順序補正処理部における順序補正の実施例（２）を示したブロック図である。
【図８】本発明に係るパケット処理装置におけるクラシファイ処理部の実施例を示したブロック図である。
【図９】本発明に係るパケット処理装置における帯域制御処理部の実施例（１）を示したブロック図である。
【図１０】本発明に係るパケット処理装置における帯域制御処理部の実施例（２）を示したブロック図である。
【図１１】本発明に係るパケット処理装置における帯域制御処理部の実施例（３）を示したブロック図である。
【図１２】本発明に係るパケット処理装置の帯域制御処理部における実施例（３）をより詳細に示したブロック図である。
【図１３】一般的なパケット交換装置の構成を示したブロック図である。
【図１４】一般的なパケット処理装置の構成を示したブロック図である。
【図１５】一般的なジャンピングウインドウ帯域制御方式を示した図である。
【図１６】一般的なスライディングウインドウ帯域制御方式を示した図である。
【図１７】一般的なＧＣＲＡ帯域制御方式を示した図である。
【符号の説明】
１００，１００＿１〜１００＿ｋ，１００ｚ，１００ｚ＿１〜１００ｚ＿ｋ　パケット処理装置
１１０，１１０＿１〜１１０＿ｋ　　回線処理部　　　　　　　　　１２０　スイッチ
１３０，１３０＿１１〜１３０＿１ｉ，…，１３０＿ｋ１〜１３０＿ｋｉ　物理回線
１０，１０ｚ　　前処理部　　　　　　　　　　　　　　　　　　　　　１１　　タイマ
１２　タイムスタンプ付与部　　　　　　　　　　　　　　１３　シーケンス番号付与部
１４　出力キュースイッチ　　　　　　　　　　　　　　　　１５，１５＿１〜１５＿ｎ　キュー
１６　出力キュー指示部
２０，２０＿１〜２０＿ｎ，２０ｚ，２０ｚ＿１〜２０ｚ＿ｎ　　分散処理部
３０，３０ｚ　　後処理部　　　　　　　　　　　　　　　　　　　　　４０，４０ｚ　　共有リソース部
５０，５０ａ，５０ｂ　　順序補正処理部　　　　　　　　　　５１＿１〜５１＿ｎ　キュー
５２　セレクタ　　　　　　　　　　　　　　　　　　　　　　　　　　５３　バッファ
６０　クラシファイ処理部　　　　　　　　　　　　　　　　６１　ＣＡＭアクセス制御部
６２　ＣＡＭ・ＲＡＭ部
７０，７０ａ，７０ｂ，７０ｃ　　帯域制御処理部　　　　　７１　　メモリ
７２＿１　許容バイト数　　　　　　　　　　　　　　　　　　　　７２＿２　受信バイト数
７３＿１　許容バイト数　　　　　　　　　　　　　　　　　　　　７３＿２〜７３＿４　受信バイト数
７４＿１　帯域設定情報　　　　　　　　　　　　　　　　　　　　７４＿２　次パケット到着予定時刻
７０１　　乗算器　　　　　　　　　　　　　　　　　　　　　　　　　　　７０２，７０３　　加算器
７０４　　セレクタ　　　　　　　　　　　　　　　　　　　　　　　　　７０５　減算器
７０６，７０７　　比較器　　　　　　　　　　　　　　　　　　　　　　７０８　　ＯＲ回路
９０，９１，９１＿０，９１＿１〜９０＿８　パケット　　　　９０ａ　　ペイロード
９０ｂ　　パケットヘッダ　　　　　　　　　　　　　　　　　　　９０ｃ　タイムスタンプ
９０ｄ　　シーケンス番号　　　　　　　　　　　　　　　　　　　９０ｅ　パケット長
９０ｆ　　フロー番号　　　　　　　　　　　　　　　　　　　　　　　９０ｇ　タグ情報
９０ｈ　　パケット情報　　　　　　　　　　　　　　　　　　　　　９２，９２＿０，９２＿１〜９２＿８　情報
９３，９４　情報　　　　　　　　　　　　　　　　　　　　　　　　　　９５　パケット
ＴＡＴ　　パケット論理到着時刻　　　　　　　　　　　　　Ｔ　パケット到着時刻
Ｉ　　増加パラメータ　　　　　　　　　　　　　　　　　　　　　Ｌ　リミットパラメータ
ｎ　　パケット長
図中、同一符号は同一又は相当部分を示す。[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a packet processing device, and more particularly, to a packet processing device that controls a band of a packet (frame).
In recent years, with the development of communication technology, the amount of communication information such as voice, still image, and moving image as well as data has been rapidly increasing. In communication networks that transmit such information, band control, which determines whether each information flow is within a predetermined band and controls it, is becoming increasingly important to ensure communication reliability. It is.
[0002]
[Prior art]
FIG. 13 shows a configuration example of a general packet switching device. This packet switching apparatus terminates physical lines 130_1-130_1i, physical lines 130_21-130_2i,..., Physical lines 130_k1-130_ki (hereinafter sometimes collectively denoted by reference numeral 130), and line processing units 110_1, 110_2,. , 110_k (hereinafter sometimes collectively referred to by reference numeral 110), packet processing devices 100z_1 to 100z_k (hereinafter sometimes collectively referred to by reference numeral 100z) connected to each line processing unit 110, and these packets, respectively. It is composed of switches 120 connected by processing devices 100z_1 to 100z_k.
[0003]
Although a plurality of physical lines 130 are connected to the line processing unit 110 in FIG. 2, the number of physical lines 130 connected to the line processing unit 110 may be one.
In operation, for example, the line processing unit 110_j transfers the packet 90 extracted from the line signal from the physical line 130_ji to the packet processing device 100z_j.
[0004]
The packet processing device 100z_j performs the following ingress processing (1) to (4) on the packet 90 received from the line processing unit 110_k, and then transfers the packet 90 to the switch 120.
(1) Classification processing: The flow type of the packet 90 is determined based on the source, destination, protocol, and the like of the packet 90.
[0005]
(2) Filtering process: Discard the transmission-prohibited packet 90.
(3) Routing processing: Based on the destination information and the like of the packet 90, it is determined to which packet processing apparatus 100z the packet 90 should be transferred via the switch 120, and information (internal tag) indicating the transfer destination is transferred to the packet 90. Attached to.
[0006]
(4) Bandwidth control processing: The packet flow rate is controlled for each packet type specified in the above-mentioned classifying processing.
The switch 120 transfers the packet 90 received from the packet processing device 100z_j to, for example, the packet processing device 100z_k indicated by the internal tag.
[0007]
The packet processing device 100z_k performs the following egress processing (1) and (2) on the packet 90 received from the switch 120, and then transfers the packet 90 to the line processing unit 110.
(1) Filtering process: Discard the transmission-prohibited packet 90.
(2) Routing processing: Based on destination information and the like of the packet 90, the physical line 130 to which the packet 90 is to be transferred via the line processing unit 110 is determined, and information (internal tag) designating a transfer destination is transmitted to the packet 90. Attached to.
[0008]
The line processing unit 110_k outputs the packet 90 received from the packet processing device 100z_k as a line signal to, for example, the physical line 130_k1 specified by the internal tag.
FIG. 14 shows a configuration of a general packet processing device 100z that processes packets in a distributed manner. This packet processing device 100z improves processing performance by processing packets in a distributed manner.
[0009]
The packet processing device 100z includes a pre-processing unit 10z, distributed processing units 20z_1 to 20z_n (hereinafter sometimes collectively referred to by reference numeral 20z), a shared resource unit 40z, and a post-processing unit 30z. This configuration is common to the packet processing device 100z that performs ingress processing and the packet processing device 100z that performs egress processing.
[0010]
The preprocessing unit 10z sends the packet received from the upstream to any one of the distributed processing units 20z_1 to 20z_n. An algorithm for this distribution includes, for example, a method of providing an output queue (not shown) corresponding to each distribution processing unit 20z and monitoring the queue length of this output queue, a round robin method, and the like.
[0011]
The preprocessing unit 10z assigns a sequence number to each packet so that the order of the distributed packets can be reproduced by the downstream postprocessing unit 30z.
The distributed processing unit 20z performs various processes on the received packet, for example, an editing process, a search process, and the like, and provides the completed packet to the post-processing unit 30z.
[0012]
The shared resource unit 40z is a resource such as a search engine and a shared memory shared by the distributed processing units 20z_1 to 20z_n, and is accessed from each distributed processing unit 20z.
The post-processing unit 30z reproduces the order of the packets input to the pre-processing unit 10z based on the sequence number assigned to each packet, and then transfers the packets downstream.
[0013]
The packet processing device 100z further performs band control for controlling whether or not the packet is within a predetermined band, that is, discards a packet violating the predetermined band or performs marking (tagging). Perform bandwidth control.
Here, as general band control systems, (1) jumping window band control system, (2) sliding window band control system, and (3) GCRA (Generic Cell Rate Algorithm) band control system will be described below.
[0014]
(1) Jumping window bandwidth control method
FIG. 15 shows a jumping window band control method. In this method, a window Wn-1, Wn, Wn + 1, Wn + 2 of a fixed time width Tw divided on an absolute time (window time width Tw = time Tn-Tn-1 = time Tn + 1-Tn = time in FIG. In this method, the bandwidth is evaluated based on the total number of bytes of each packet received in (Tn + 2−Tn + 1 = time Tn + 3−Tn + 2).
[0015]
This method is easy to implement, but, for example, cannot transfer the information of the past window Wn-1 to the next window Wn. For example, if the number of bytes of the packet received in the window Wn-1 is "0" and the total number of bytes of the received packet in the next window Wn exceeds the contracted prescribed value, the reception is performed in the windows Wn-1 and Wn. Even when the average of the total number of bytes of the packet does not exceed the specified value, it is determined that the bandwidth is violated.
[0016]
(2) Sliding window bandwidth control method
FIG. 16 shows a sliding window band control method. In this method, for example, each time a packet fa, fb, fc arrives, the bandwidth is evaluated based on the total number of bytes of the packet received within a window having a past fixed time width Tw from the arrival times Ta, Tb, Tc. .
[0017]
This method can dynamically evaluate the bandwidth, but is difficult to implement.
(3) GCRA Bandwidth control method
FIG. 15 shows the GCRA band control method. This method is a method of evaluating a band based on a reception interval between two consecutive packets, and is logically equivalent to a leaky packet band control method.
[0018]
The algorithm of the GCRA band control method will be described below.
Here, TAT = logical arrival time of packet (Theoretic @ Arrival @ Time), T = actual packet arrival time (Time), I = increase parameter (Increment @ Parameter), L = limit parameter (Limit @ Parameter), n = packet length ( Packet @ Length). The values of I and L are set in advance.
[0019]
{Circle around (1)} After the control is started, the first received packet is unconditionally determined as the band control result = “conforming”, and the next TAT is calculated by the following equation (1).
TAT = T + nI Equation (1)
{Circle around (2)} Thereafter, each time a packet (length n, arrival time T) is received, the packet is compared with the TAT to determine “conformity” or “non-conformity” and calculate the next TAT.
[0020]
(A) Comparison result: if TAT <T (packet received after time TAT, see FIG. 1A), band control result = “conformity”, and the following equation (2) starts from time T and Is calculated.
TAT = T + nI Equation (2)
(B) Comparison result: When TAT-L ≦ T ≦ TAT (when a packet is received after time (TAT-L) and before time TAT, see FIG. 2B), the bandwidth control result = “conformity” And the next TAT is calculated by the following equation (3) using the current TAT as a base point.
[0021]
Next TAT = Current TAT + nI Equation (3)
(C) Comparison result: When T <TAT-L (when a packet is received before time (TAT-L), see FIG. 3C), the band control result = “non-conforming”, and the following equation ( In 4), the next TAT is calculated. That is, the TAT is not updated.
[0022]
Next TAT = Current TAT ... Equation (4)
[0023]
[Problems to be solved by the invention]
When such band control is performed by the distributed processing unit 20z, the continuity of the packet is not maintained because the packets are distributed to each distributed processing unit 20z, and therefore, high-precision band control cannot be performed. . Therefore, the conventional band control includes (1) a method performed by the preprocessing unit 10z or (2) a method performed by the postprocessing unit 30z.
[0024]
(1) Bandwidth control by pre-processing unit
Since this method is performed before the distributed processing, there is an advantage that fluctuation of a packet interval is small and band control with high accuracy can be performed. However, in order to perform the band control, it is necessary to perform a classifying process before that, and the processing information is generated along with the classifying process.
[0025]
(2) Bandwidth control by post-processing unit
This method has an advantage that the classification processing can be performed by the distributed processing unit 20z or the shared resource unit 40z. However, since the distributed processing unit 20z or the shared resource unit 40z needs information for notifying the post-processing unit 30z of the classifying result information, band pressure is caused.
[0026]
In addition, since packets are distributed and merged upstream, there is a disadvantage that fluctuations in packet intervals become large and the accuracy of band control becomes low.
Accordingly, it is an object of the present invention to provide a packet processing apparatus for controlling a packet bandwidth, which performs packet bandwidth control without squeezing the bandwidth of its own apparatus, and performs highly accurate packet bandwidth control.
[0027]
[Means for Solving the Problems]
In order to solve the above problems, a packet processing device according to the present invention includes a preprocessing unit that sends a received packet to any one of a plurality of output terminals; A plurality of distributed processing units that process the packets from the distributed processing unit, a shared resource unit that performs bandwidth control of the packets based on the reception order information of each packet distributed to each distributed processing unit, and a packet from each distributed processing unit. And a post-processing unit that merges and outputs the combined data (claim 1 and supplementary note 1).
[0028]
The basic configuration of the packet processing device 100 of the present invention is the same as that of the general packet processing device 100z shown in FIG. 14, and the conventional preprocessing unit 10z, distributed processing units 20z_1 to 20z_n, shared resource unit 40z, And a post-processing unit 30z, instead of a pre-processing unit 10, n distributed processing units 20_1 to 20_n (hereinafter sometimes collectively referred to by reference numeral 20), a shared resource unit 40, and a post-processing unit 30. I have.
[0029]
The difference between the packet processing device 100 of the present invention and the conventional packet processing device 100z is that the shared resource unit 40 collects the reception order information of the packets distributed to each distributed processing unit 20, and based on this information, This is to perform packet bandwidth control.
That is, the preprocessing unit 10 sends out the received packet from one of the plurality of output terminals to, for example, one output terminal selected by a conventional predetermined algorithm.
[0030]
Each of the distributed processing units 20_1 to 20_n processes a packet received from an output terminal of the preprocessing unit 10, respectively.
The shared resource unit 40 performs band control to determine whether or not the packet is within a predetermined band based on the reception order information of the packets distributed to the distributed processing units 20_1 to 20_n.
[0031]
The post-processing unit 30 merges and outputs the packets processed by the distributed processing unit.
Therefore, the packet processing apparatus of the present invention does not squeeze the band in its own apparatus based on the result of the band control. The bandwidth control of the packet can be realized by performing the notification of the bandwidth violation.
[0032]
As described above, the bandwidth control of the packets distributed to the distributed processing unit can be performed by the shared resource unit 40, and the packet processing is performed without the bandwidth being squeezed because unnecessary processing information and notification information are not required. It becomes possible to control.
The above-described processing of discarding a packet and notifying of a band violation is performed by a predetermined processing unit such as a distributed processing unit, a post-processing unit, or the like based on the band control result of the present invention.
[0033]
According to the present invention, in the above-mentioned present invention, the reception order information can be time information added to the packet (Claim 2 and Supplementary Note 2).
That is, the shared resource unit 40 determines an accurate time-series position of the packet based on time information (for example, a time stamp) given to the packet, and performs band control. As a result, it is possible to correct the fluctuation of the packet in the time series generated in the process from the time when the time information is added to the packet to before the bandwidth control, and it is possible to perform the bandwidth control with high accuracy.
[0034]
Also, in the present invention according to the above-mentioned present invention, the pre-processing unit can add the time information to the packet (claim 3 and supplementary note 3).
Also, in the present invention according to the above-mentioned present invention, the distribution processing unit can add the time information to the packet (Supplementary Note 4).
[0035]
That is, time information (time stamp) can be added to the packet by the preprocessing unit 10 or the distributed processing unit 20. The time-series fluctuation of the time information is smaller when the time information is provided by the preprocessing unit 10 than when the time information is provided by the distributed processing unit 20, and accurate band control can be performed.
[0036]
For example, when the preprocessing unit 10 attaches a time stamp to a packet at the forefront stage, the shared resource is not affected by the packet fluctuation caused by the processing at the subsequent stage of the preprocessing unit 10 and the distributed processing by the distributed processing unit 20. The unit 40 can perform accurate bandwidth control based on the time when the packet arrives at the preprocessing unit 10.
[0037]
Also, in the present invention according to the above-mentioned present invention, the shared resource unit may include an order correction processing unit that rearranges the packets in a time-series order based on the time information (Supplementary Note 5).
That is, for example, the order correction processing unit determines the order of the packets whose order in the time series has been changed by the distributed processing by the respective distributed processing units 20 based on the time information (time stamp) given to the packets. , Undo.
[0038]
As a result, packets can be processed in chronological order, and band control becomes easy.
Also, in the present invention according to the above-mentioned present invention, the reception order information further includes a sequence number indicating a packet reception order added to the packet by the preprocessing unit, and the shared resource unit includes the sequence number. , An order correction processing unit for rearranging the packets in chronological order can be provided (claim 4, appendix 6).
[0039]
This also makes it possible to process the packets in chronological order, thereby facilitating bandwidth control.
Further, according to the present invention, in the above-mentioned present invention, the shared resource unit can perform band control by any one of a jumping window band control system, a sliding window band control system, and a GCRA band control system. (Appendix 7).
[0040]
That is, the shared resource unit 40 may perform the band control by the jumping window band control system shown in FIG. 15, the sliding window band control system shown in FIG. 16, or the GCRA band control system shown in FIG.
Further, according to the present invention, in the above-mentioned present invention, the shared resource unit further includes a classifier processing unit for classifying packets according to flows, and is capable of performing bandwidth control for each flow (claim 5, appendix 8). .
[0041]
Further, in the present invention according to the above-mentioned present invention, each distributed processing unit further includes a classifying processing unit for classifying packets by flow, and the shared resource unit can perform bandwidth control for each flow (Supplementary Note 9).
Also, in the present invention according to the above-mentioned present invention, the pre-processing unit further includes a classification processing unit for classifying packets by flow, and the shared resource unit can perform band control for each flow (Supplementary Note 10).
[0042]
That is, the classifying processing unit 60 is arranged in the shared resource unit 40, the distributed processing unit 20, or the preprocessing unit 10. The classifying unit 60 classifies the packets by flow, and the shared resource unit 40 performs band control by flow.
This enables band control for each flow. In addition, the arrangement position of the classifying processing unit may be selected so that the band is not compressed most. Generally, the method of disposing the classifying processing unit in the distributed processing unit 20 is such that the classifying process is dispersed and the band compression is small. .
[0043]
Also, in the present invention according to the above-mentioned present invention, the reception order information is a sequence number indicating a reception order of the packet, and the shared resource unit includes an order correction processing unit for rearranging the packet in the order of the sequence number. And a timer for measuring the time at which the packet was input to itself, and the bandwidth can be controlled based on the time (Supplementary Note 11).
[0044]
That is, a sequence number indicating a packet reception order is used as the reception order information. The shared resource unit 40 further includes an order correction processing unit and a timer. The order correction processing unit rearranges the packets in order of the sequence number, and the timer measures the time when the packet is input to the shared resource unit 40. Based on this time, the shared resource unit 40 controls the bandwidth of the packet.
[0045]
This also allows the shared resource unit 40 to perform band control. That is, even when the packets are distributed to the distribution processing unit 20, the bandwidth control can be performed based on the time when the packets arrive at the shared resource unit 40.
In this band control, it is not necessary to add a time stamp to a packet.
[0046]
Further, according to the present invention, in the above-described present invention, the pre-processing unit may add the sequence number to the packet (Supplementary Note 12).
[0047]
BEST MODE FOR CARRYING OUT THE INVENTION
FIG. 1 shows an embodiment of a packet processing device 100 according to the present invention. This packet processing device 100 includes a pre-processing unit 10, distributed processing units 20_1 to 20_n, a post-processing unit 30, and a shared resource unit 40, similarly to the general packet processing device 100z shown in FIG. .
[0048]
In FIG. 1, the shared resource unit 40 is shown in particular detail, and is characterized in that the shared resource unit 40 includes an order correction processing unit 50, a classifying processing unit 60, and a band control processing unit 70. It is.
FIG. 2 shows an embodiment of the pre-processing unit 10 shown in FIG. The preprocessing unit 10 adds the timer 11, the time indicated by the timer 11 to the received packet 90, that is, the time stamp adding unit 12 that adds the time stamp 90 c and outputs the packet 90, and further adds the sequence number 90 d to the packet 90. And a sequence number assigning unit 13 for outputting the packet 91.
[0049]
Further, the pre-processing unit 10 is connected to the output queue switch 14 for outputting the packet 91 to any one of the n output terminals, and to each output terminal of the output queue switch 14, and provided from the output queue switch 14. Queues 15_1 to 15_n for queuing the packet 91 (hereinafter sometimes collectively referred to by reference numeral 15) and the queuing state of the queue 15 are detected, and for example, the queue 15 with the least number of queued bytes is detected. An output queue instructing unit 16 for detecting and giving an instruction to give the next packet 91 to the queue 15 to the output queue switch 14.
[0050]
FIG. 3A shows a format example of the packet 90 input to the preprocessing unit 10. The packet 90 includes a payload 90a and a packet header 90b (for example, an IPv4 header).
FIG. 2B shows a format example of the packet 91 provided to the output queue switch 14. The packet 91 is composed of the packet 90 shown in FIG. 1A, a time stamp 90c and a sequence number 90d given to the packet 90.
[0051]
FIG. 4 shows an operation example of the distributed processing unit 20 shown in FIG. The distributed processing unit 20 sequentially receives the packets 91_2, 91_4, and 91_7 (hereinafter, may be collectively referred to by reference numeral 91) received from the preprocessing unit 10, and receives the sequence numbers 90d, Information 92_2, 92_4, and 92_7 including a time stamp 90c and the like (hereinafter, sometimes collectively referred to by reference numeral 92) are provided to the shared resource unit 40.
[0052]
FIG. 5 shows an example of each information transmitted by the distributed processing unit 20 and the shared resource unit 40. FIG. 1A shows a configuration example of the information 92. The information 92 includes a sequence number 90d, a time stamp 90c, a packet length 90e, and packet information 90h. The packet information 90h is information necessary for classifying the packet 91, for example, a destination IP address, a source IP address, or an L4 protocol.
[0053]
On the other hand, the distributed processing unit 20 conversely includes information 94_2, 94_4, and 94_7 including the tag information 90g, which is the band control result, and the sequence number 90d from the shared resource unit 40 (hereinafter, may be collectively referred to by reference numeral 94). To receive. FIG. 5C shows an example of the format of this information 94. This information 94 is composed of a sequence number 90d and tag information 90g.
[0054]
Further, the distribution processing unit 20 assigns tag information 90g of information 94 having the same sequence number 90d as the sequence number 90d assigned to the own packet 91, instead of the time stamp 90c of the packet 91 (see FIG. 3B). The resulting packet 95 is provided to the post-processing unit 30.
FIG. 5D shows a format example of the packet 95. The packet 95 is composed of a packet 90, a sequence number 90d, and tag information 90g. FIG. 3C will be described later.
[0055]
FIG. 6 shows an embodiment (1) in which the reception order of the information 92 is corrected. In this embodiment (1), each distributed processing unit 20 determines the reception order of the packet 91 received from the preprocessing unit 10. In the same order, information 92 (see FIG. 5C, FIG. 6 shows only the sequence number 90d) is given to the order correction processing unit 50a.
[0056]
The order correction processing unit 50a includes queues (FIFOs) 51_1 to 51_n (hereinafter, may be collectively referred to by reference numeral 51) corresponding to the distributed processing units 20_1 to 20_n, respectively, and a selector 52.
The queue 51 stores the information 92 received from the distributed processing unit 20 in FIFO, and the selector 52 selects the information 92 with the youngest sequence number 90d from all the queues 51 and gives the selected information 92 to the classification processing unit 60.
[0057]
Thereby, the information 92 of the corresponding packet 90 in the same order as the order of the packets 90 input to the pre-processing unit 10 is given to the classifying unit 60.
FIG. 7 shows an embodiment (2) in which the reception order of the information 92 is corrected. In this embodiment (2), each distributed processing unit 20 differs from the embodiment (1) in that the packet 91 The information 92 corresponding to the packet 91 is provided to the order correction processing unit 50b in an order different from the order input to the order 20.
[0058]
For example, the distributed processing unit 20_1 sequentially receives the packets 91_1, 91_2, and 91_7 whose sequence numbers 90d are "41", "42", and "47", respectively, and the sequence numbers 90d are "47" and "41", respectively. The information 92_7, 92_1, and 92_2 which are "" and "42" are provided to the order correction processing unit 50b.
[0059]
When the internal processing of the distributed processing unit 20 is performed in a distributed manner, such a case where the order is not preserved occurs.
In FIG. 7, as in FIG. 6, only the sequence number 90d is shown in each packet 91 and information 92, and the time stamp 90c and the like are omitted.
[0060]
The order correction processing unit 50b includes a buffer 53, and stores information 92_0, 92_1 to 92_8 received from the distribution processing units 20_1 to 20_n in the buffer 53 in the order of the sequence number 90d. Then, the order correction processing unit 50b reads the information 92 from the buffer 53 in the order of the sequence numbers 90d (40, 41,..., 48,.
[0061]
6 and 7, the distribution processing unit 20 or the order correction processing unit 50a may correct the order of the packets using the time stamp 90c instead of the sequence number 90d. In this case, the sequence number 90d is unnecessary.
FIG. 8 shows an embodiment of the classifier 60. The classification processing unit 60 includes a CAM (Content Address Memory) access control unit 61 and a CAM / RAM unit 62.
[0062]
A flow number 90f corresponding to the packet information 90h is registered in the CAM / RAM unit 62.
The CAM access control unit 61 gives the classifying packet information 90h (see FIG. 5A) in the information 92 to the CAM / RAM unit 62, reads the flow number 90f corresponding to the packet information 90h, and The information 93 to which the flow number 90f is added instead of the packet information 90h is given to the band control processing unit 70.
[0063]
This information 93 is shown in FIG. The information 93 includes a sequence number 90d, a time stamp 90c, a packet length 90e, and a flow number 90f.
Embodiments (1) to (3) of the band control processing unit 70 will be described below with reference to FIGS.
FIG. 9 shows an embodiment (1) of the band control processing unit 70. This embodiment (1) particularly shows the band control processing unit 70a of the jumping window band control system described with reference to FIG.
[0064]
The bandwidth control processing unit 70a includes a memory 71 that stores the allowable number of bytes 72_1 and the number of received bytes 72_2 corresponding to each flow number 90f. The permissible byte count 72_1 pre-registers the permissible byte count of the flow corresponding to the flow number 90f (this byte count corresponds to the permissible set bandwidth), and the received byte count 72_2 corresponds to the flow corresponding to the flow number 90f. The number of received bytes received during the predetermined time T is stored. The initial value of the number of received bytes is “0”.
[0065]
The operation procedure of the band control processing unit 70a will be described below. This operation procedure is executed for each flow number.
Steps S10: The bandwidth control processing unit 70a gives the flow number 90f to the memory 71, and reads out the allowable byte number 72_1 and the received byte number 72_2 corresponding to the flow number 90f.
[0066]
Steps S11: The processing unit 70a updates the new received byte count 72_2 = the previous received byte count 72_2 + the packet length (byte count) 90e, and updates the new received byte count 72_2 with the same flow number 90f as the flow number 90f given in step S10. Write to the received byte number 72_2 corresponding to the number.
[0067]
Steps S12: The processing unit 70a compares the new received byte count 72_2 with the allowable byte count 72_1, determines whether or not the set permissible bandwidth of the flow is maintained, and tags the information 94 (FIG. 5 (3) )) To the distributed processing unit 20.
As described in the description of FIG. 5C, the information 94 includes the sequence number 90d and the tag information 90g. The tag information 90g may be composed of, for example, “OK” indicating that the allowable band is being protected or “NG” indicating violation of the allowable band, or “green”, “yellow”, or “red”. And the like.
[0068]
Steps S13: The band control processing unit 70a refers to the received time stamp 90c and clears the total number of received bytes 72_2 entered in the memory 71 at regular time intervals T.
Note that a timer (not shown) may be provided in the band control processing unit 70a without using the time stamp 90c, and the total number of received bytes 72_2 may be cleared at regular intervals based on the timer. In this case, the information of the time stamp 90c is unnecessary.
[0069]
The band control based on the time stamp 90c indicating the time at which the packet 90 was input to the pre-processing unit 10 is performed more efficiently than the band control based on the time at which the information 93 is input to the band control processing unit 70c. Since there is no fluctuation between the information 93 due to the processing in the above, accurate band control is possible.
[0070]
FIG. 10 shows an embodiment (2) of the band control processing unit 70. This embodiment (2) particularly shows the band control processing unit 70b of the sliding window band control system described with reference to FIG.
The bandwidth control processing unit 70b includes a memory 71 that stores the allowable number of bytes 73_1 and the number of received bytes 73_2 to 73_m corresponding to the flow number 90f. In the allowable byte number 73_1, the allowable byte number (corresponding to the set allowable bandwidth) of the flow corresponding to the flow number 90f is registered in advance.
[0071]
The number of received bytes 73_2 to 73_m stores the number of received bytes of the received flow corresponding to the flow number 90f. The initial value of the received byte numbers 73_2 to 73 — m is “0”.
The operation procedure of the band control processing unit 70b will be described below. This operation procedure is executed for each flow number.
[0072]
Steps S20: The band control processing unit 70b gives the flow number 90f of the received information 93 to the memory 71, and reads out the allowable number of bytes 73_1 and the number of received bytes 73_2 to 73_m.
Steps S21The processing unit 70b updates the new received byte count 73_2 = the previous received byte count 73_2 + the packet length 90e (byte count) and writes the new received byte count 73_2 into the received byte count 73_2 of the memory 71.
[0073]
Steps S22: The processing unit 70b sums the number of received bytes 73_2 to 73_m, compares the total number of bytes with the allowable number of bytes, determines whether or not the set allowable band is being followed, and tags the result of the determination with a tag. 94 (see FIG. 5C) is given to the distributed processing unit 20.
Steps S23: The processing unit 70b shifts the number of received bytes at regular time intervals t based on the time stamp 90c of the received information 93 (the number of received bytes 73_m ← the number of received bytes 73_ (m−1),..., The number of received bytes 73_3 ← Received byte count 73_2, Received byte count 73_2 ← “0” (clear)).
[0074]
Note that the number (m-1) of the received byte numbers 73_2 to 73_m is determined by the time interval t for shifting and the window time width Tw.
Instead of using the time stamp 90c, a timer may be provided in the band control processing unit 70a, and shifting may be performed at regular intervals based on the timer. In this case, the time stamp 90c is unnecessary, but the bandwidth control of the original packet 90 is performed based on the time when the information 93 arrives at the bandwidth control processing unit 70a, and the bandwidth control is performed similarly to the embodiment (1). Shaking occurs.
[0075]
FIG. 11 shows an embodiment (3) of the band control processing unit 70. This embodiment (3) particularly shows the band control processing unit 70c of the GCRA band control system.
The bandwidth control processing unit 70c includes a memory 71 that stores bandwidth setting information 74_1 (I: increase parameter, L: limit parameter) and a scheduled next packet arrival time 74_2 (TAT: logical arrival time) corresponding to each flow number 90f. ing. The increase parameter I and the limit parameter L are registered in advance.
[0076]
The next packet expected arrival time 74_2 stores the logical arrival time TAT calculated by the equations (1) to (4) shown in the description of FIG. The initial value of the logical arrival time TAT is “0”.
The operation procedure of the band control processing unit 70c will be described below. This operation procedure is executed for each flow number 90f.
[0077]
Steps S30: The band control processing unit 70c gives the flow number 90f of the received information 93 (see FIG. 5 (2)) to the memory 71, and reads the band setting information 74_1 and the scheduled next packet arrival time 74_2 corresponding to the flow number 90f.
Steps S31: The processing unit 70c compares the time stamp 90c (= actual packet arrival time T) with the estimated arrival time 74_2 (logical arrival time TAT) to determine whether or not the set allowable bandwidth is maintained, and the determination result To create information 94 tagged with.
[0078]
Steps S32: The processing unit 70c selects one of the expressions (1) to (4) selected based on the condition of the packet arrival time T (see FIGS. 17A to 17C), and selects the selected expression To calculate the logical arrival time TAT. Further, the processing unit 70c writes the calculation result into the next packet expected arrival time 74_2 in the memory 71 corresponding to the flow number 90f, and also gives the information 94 (see FIG. 5C) to the distribution processing unit 20.
[0079]
FIG. 12 shows a more detailed operation of the band control processing unit 70c shown in FIG. The detailed operation will be described below.
The processing unit 70c receives information 93 (flow number 90f, packet length (n) 90e, time stamp (T) 90c, and sequence number 90d, see FIG. 5B) from the classifying processing unit 60.
[0080]
The processing unit 70c gives the flow number 90f to the memory 71, and reads out the band setting information 74_1 (= increase parameter I, limit parameter L) and the scheduled next packet arrival time 74_2 (= logical arrival time TAT).
The multiplier 701 outputs a product (n × I) obtained by multiplying the packet length n by the increase parameter I. The adder 702 outputs a sum (TAT + n × I) obtained by adding the packet logical arrival time TAT and the product (n × I). The adder 703 outputs a sum (T + n × I) obtained by adding the time T and the product (n × I).
[0081]
The subtractor 705 outputs the difference (TAT-L) between the logical arrival time TAT and the limit parameter L, and the comparator 706 compares the difference (TAT-L) with T, and when (TAT-L) <T When there is, SEL1 = "1" is outputted, and when T≤ (TAT-L), SEL1 = "0" is outputted. Comparator 707 compares TAT and T, and outputs SEL0 = “1” when TAT <T, and outputs SEL0 = “0” when T ≦ TAT.
[0082]
When (SEL0, SEL1) = (0, 0), (0, 1), or (1, 1), the selector 704 outputs “TAT”, “TAT + n × I”, or “T + n × I”, respectively. Select and output.
The selected data is written to the next scheduled packet arrival time 74_2 in the memory 71.
[0083]
Accordingly, when T ≦ (TAT−L), the next TAT = current TAT, when (TAT−L) <T ≦ TAT, when the next TAT = TAT + n × I, and when TAT <T, the next TAT = “T + n × I”.
The OR circuit 708 performs a logical OR operation on SEL0 and SEL1, and outputs conformity = “1” or nonconformity = “0” as a band control result. The information 94 tagged with the band control result is transmitted to the distributed processing unit 20.
[0084]
Thereafter, predetermined control such as discarding the packet 91 and the like is performed based on the band control result.
(Appendix 1)
A preprocessing unit for transmitting the received packet to any one of the plurality of output terminals;
A plurality of distributed processing units connected to each output terminal and processing the packet from each output terminal,
Based on the reception order information of each packet distributed to each distributed processing unit, a shared resource unit that performs bandwidth control of the packet,
A post-processing unit that merges and outputs packets from each distributed processing unit,
A packet processing device comprising:
[0085]
(Supplementary Note 2) In the above Supplementary Note 1,
The packet processing device, wherein the reception order information is time information given to the packet.
(Supplementary note 3) In the above supplementary note 2,
A packet processing apparatus, wherein the preprocessing unit adds the time information to a packet.
[0086]
(Supplementary Note 4) In the above Supplementary note 2,
The packet processing device, wherein the distributed processing unit adds the time information to the packet.
(Supplementary Note 5) In the above Supplementary note 2,
A packet processing device, characterized in that the shared resource unit includes an order correction processing unit for rearranging the packets in chronological order based on the time information.
[0087]
(Supplementary Note 6) In the above Supplementary note 2,
The reception order information further includes a sequence number indicating the reception order of the packet added to the packet by the preprocessing unit,
A packet processing device, wherein the shared resource unit includes an order correction processing unit that rearranges the packets in chronological order based on the sequence number.
[0088]
(Supplementary Note 7) In the above Supplementary Note 1,
The packet processing device, wherein the shared resource unit performs band control by any one of a jumping window band control system, a sliding window band control system, and a GCRA band control system.
[0089]
(Supplementary Note 8) In the above Supplementary Note 1,
The packet processing device, further comprising a classifying processing unit for classifying packets by flow, and performing bandwidth control by flow.
(Supplementary Note 9) In the above Supplementary Note 1,
A packet processing apparatus, wherein each of the distributed processing units further includes a classifying processing unit that classifies packets by flow, and the shared resource unit performs band control by flow.
[0090]
(Supplementary Note 10) In the above Supplementary Note 1,
The packet processing apparatus further comprising a classifying processing unit for classifying packets by flow, wherein the shared resource unit performs bandwidth control for each flow.
[0091]
(Supplementary Note 11) In the above Supplementary Note 1,
The reception order information is a sequence number indicating the reception order of the packet,
The shared resource unit further includes an order correction processing unit that rearranges the packets in order of the sequence number, and a timer that counts the time at which the packet is input to itself, and performs bandwidth control based on the time. Characteristic packet processing device.
[0092]
(Supplementary Note 12) In the above Supplementary Note 11,
The packet processing device, wherein the preprocessing unit adds the sequence number to the packet.
[0093]
【The invention's effect】
As described above, according to the packet processing device of the present invention, the shared resource unit determines the packet based on the reception order information (for example, time stamp and sequence number) of each packet distributed to each distributed processing unit. Is configured to perform the bandwidth control of the packet, it is possible to perform the bandwidth control of the packet without compressing the bandwidth of the own apparatus.
[0094]
Further, since the preprocessing unit preferably adds a time stamp to the received packet, it is possible to perform highly accurate packet bandwidth control.
[Brief description of the drawings]
FIG. 1 is a block diagram showing an embodiment of a packet processing device according to the present invention.
FIG. 2 is a block diagram showing an embodiment of a pre-processing unit in the packet processing device according to the present invention.
FIG. 3 is a diagram showing an example of a packet format in a preprocessing unit in the packet processing device according to the present invention.
FIG. 4 is a diagram illustrating an operation example of a distributed processing unit in the packet processing device according to the present invention.
FIG. 5 is a diagram showing a format example of each information in the packet processing device according to the present invention.
FIG. 6 is a block diagram showing an embodiment (1) of order correction in the distribution processing unit and the order correction processing unit of the packet processing device according to the present invention.
FIG. 7 is a block diagram showing an embodiment (2) of order correction in the distribution processing unit and the order correction processing unit of the packet processing device according to the present invention.
FIG. 8 is a block diagram showing an embodiment of a classifier in the packet processing apparatus according to the present invention.
FIG. 9 is a block diagram showing an embodiment (1) of a band control processing unit in the packet processing device according to the present invention.
FIG. 10 is a block diagram showing an embodiment (2) of the bandwidth control processing unit in the packet processing device according to the present invention.
FIG. 11 is a block diagram showing an embodiment (3) of a band control processing unit in the packet processing device according to the present invention.
FIG. 12 is a block diagram showing an example (3) of the band control processing unit of the packet processing device according to the present invention in more detail.
FIG. 13 is a block diagram showing a configuration of a general packet switching device.
FIG. 14 is a block diagram showing a configuration of a general packet processing device.
FIG. 15 is a diagram illustrating a general jumping window band control method.
FIG. 16 is a diagram illustrating a general sliding window band control method.
FIG. 17 is a diagram showing a general GCRA band control method.
[Explanation of symbols]
100, 100_1 to 100_k, 100z, 100z_1 to 100z_k Packet processing device
110, 110_1 to 110_k {line processing unit {120} switch
130, 130_1 to 130_1i, ..., 130_k1 to 130_ki１３０physical line
10,10z {preprocessing unit {11} timer
12 {time stamp assigning unit} {13} sequence number assigning unit
14 output queue switch {15, 15_1 to 15_n} queue
16 Output queue indicator
20, 20_1 to 20_n, 20z, 20z_1 to 20z_n {distributed processing unit
30, 30z {Post-processing unit {40, 40z} Shared resource unit "
50, 50a, 50b {order correction processing unit {51_1 to 51_n} queue>
52 selector 53 buffer
60 {Classification processing unit} 61} CAM access control unit
62 @ CAM / RAM section
70, 70a, 70b, 70c {Band control processor {71} Memory
72_1 {number of allowable bytes} 72_2} number of received bytes
73_1 {number of allowable bytes} 73_2-73_4} number of received bytes
74_1 {band setting information} {74_2} estimated next packet arrival time
701 {Multiplier} 702, 703} Adder
704 {selector} 705} subtractor
706, 707 {comparator} 708 OR circuit
90, 91, 91_0, 91_1 to 90_8 {Packet {90a} Payload
90b {Packet header {90c} Time stamp
90d {sequence number} 90e} packet length
90f {flow number} 90g tag information
90h {Packet information {92, 92_0, 92_1 to 92_8} information
93,94 {information} packet
TAT {packet logical arrival time} T} packet arrival time
I Increase parameter L Limit parameter
n packet length
In the drawings, the same reference numerals indicate the same or corresponding parts.

Claims

A preprocessing unit for transmitting the received packet to any one of the plurality of output terminals;
A plurality of distributed processing units connected to each output terminal and processing the packet from each output terminal,
Based on the reception order information of each packet distributed to each distributed processing unit, a shared resource unit that performs bandwidth control of the packet,
A post-processing unit that merges and outputs packets from each distributed processing unit,
A packet processing device comprising:

In claim 1,
The packet processing device, wherein the reception order information is time information given to the packet.

In claim 2,
A packet processing apparatus, wherein the preprocessing unit adds the time information to a packet.

In claim 2,
The reception order information further includes a sequence number indicating the reception order of the packet added to the packet by the preprocessing unit,
A packet processing device, characterized in that the shared resource unit includes an order correction processing unit that sorts the packets in chronological order based on the sequence number.

In claim 1,
The packet processing device, further comprising a classifying processing unit for classifying packets by flow, and performing bandwidth control by flow.