(57)【特許請求の範囲】
【請求項１】
ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）パケットのキャリアクラスのＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）保証を実現するために、いくつかのユニークな情報を共有する一連のパケットであるフローを検出するフロー検出装置であって、検出対象の全てのフローに対して互いに異なる値をとるようなハッシュ関数の計算値を計算するハッシュ関数処理手段と、前記ハッシュ関数の計算値を使用するフロー番号と前記フロー各々に設定されたプライオリティとを格納するフロー検出テーブルとを有し、前記フロー検出テーブルを参照してフロー検出を行うことを特徴とするフロー検出装置。
【請求項２】
前記プライオリティは、前記ＩＰパケットのＱｏＳ保証を示すことを特徴とする請求項１記載のフロー検出装置。
【請求項３】
前記ハッシュ関数ｆの計算値は、ＩＰヘッダ内の情報とＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）内の情報とから予め計算することを特徴とする請求項１または請求項２記載のフロー検出装置。
【請求項４】
前記ＩＰヘッダ内の情報は、少なくともソースアドレスとデスティネーションアドレスとプロトコルとからなり、
前記ＴＣＰ／ＵＤＰ内の情報は、少なくともソースポート番号とデスティネーションポート番号とからなることを特徴とする請求項３記載のフロー検出装置。
【請求項５】
ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）パケットのキャリアクラスのＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）保証を実現するために、いくつかのユニークな情報を共有する一連のパケットであるフローを検出するフロー検出方法であって、検出対象の全てのフローに対して互いに異なる値をとるようなハッシュ関数の計算値を計算しておき、前記ハッシュ関数の計算値を使用するフロー番号と前記フロー各々に設定されたプライオリティとを格納するフロー検出テーブルを参照してフロー検出を行うことを特徴とするフロー検出方法。
【請求項６】
前記プライオリティは、前記ＩＰパケットのＱｏＳ保証を示すことを特徴とする請求項５記載のフロー検出方法。
【請求項７】
前記ハッシュ関数ｆの計算値は、ＩＰヘッダ内の情報とＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）内の情報とから予め計算するようにしたことを特徴とする請求項５または請求項６記載のフロー検出方法。
【請求項８】
前記ＩＰヘッダ内の情報は、少なくともソースアドレスとデスティネーションアドレスとプロトコルとからなり、
前記ＴＣＰ／ＵＤＰ内の情報は、少なくともソースポート番号とデスティネーションポート番号とからなることを特徴とする請求項７記載のフロー検出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はフロー検出装置及びそれに用いるフロー検出方法に関し、特にＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）パケットネットワークにおけるＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）保証を実現するためのフロー検出に関する。
【０００２】
【従来の技術】
一般的なＩＰパケットネットワークの構成例を図４に示す。図４において、ＩＰパケットネットワークではＰＣ（パーソナルコンピュータ）５から送られてきたパケットがノード（ルータ）６のセレクタ６１によってキュー６２−１〜６１−ｎに分配され、各キュー６２−１〜６１−ｎからＰＣ７，８へと送られる。上記のノード６でのパケット処理においては図示せぬフォワーディングテーブルを検索して送付先が決定されているが、このフォワーディングテーブル検索が主要なボトルネックとなっている。
【０００３】
ＩＰパケットのキャリアクラスのＱｏＳ保証を実現するにはフロー検出技術が必要である。フロー識別はＩＰパケット受信時のポリシング（流量監視）のトラヒック識別子、スイッチにおける優先クラス及びＩＰパケット出力時の帯域制御キュー番号を決定するために必要である。
【０００４】
フローとはいくつかのユニークな情報を共有する一連のパケットである。ユニークな情報としては送信先ＩＰアドレス／送信元ＩＰアドレス、送信先ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）／ＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）ポート番号／送信元ＴＣＰ／ＵＤＰポート番号、プロトコル種別、ＤＳＣＰ（Ｄｉｆｆｓｅｒｖ  Ｃｏｄｅ  Ｐｏｉｎｔ：ＩＰヘッダ内Ｔｙｐｅ  ｏｆ  Ｓｅｒｖｉｃｅフィールドの一部）等がある。
【０００５】
コネクションレスのＩＰネットワークでは、このフロー毎にＱｏＳクラスを割当てており、フロー識別はＩＰレベルでＱｏＳをサポートするための必須機能である。フロー識別することによって、ＩＰパケット受信時のポリシング（流量監視）のトラヒック識別子、スイッチにおける優先クラス及びＩＰパケット出力時の帯域制御のキュー番号を決定することでＱｏＳをサポートすることができる。
【０００６】
従来のフロー検出方法の一例を図５に示す。図５において、従来のフロー検出方法ではフロー検出装置４と、フローテーブル格納メモリ３とが用いられている。フローテーブル格納メモリ３に登録されるフロー検出テーブルの一例を図６に示す。
【０００７】
図６において、フロー検出テーブル３１にはＩＰソースアドレス（ＩＰ  ＳＡ）と、ＩＰデスティネーションアドレス（ＩＰ  ＤＡ）と、プロトコル（Ｐ）と、ソースポート番号（Ｓ  Ｐｏｒｔ）と、デスティネーションポート番号（Ｄ  Ｐｏｒｔ）と、プライオリティ（Ｐｒｉｏｒｉｔｙ）とが登録されている。
【０００８】
ＩＰパケットはＩＰヘッダ内の情報［ソースアドレス（ＳＡ）３２ｂｉｔｓ、デスティネーションアドレス（ＤＡ）３２ｂｉｔｓ、プロトコル（Ｐ）８ｂｉｔｓ］とＴＣＰ／ＵＤＰ内の情報［ソースポート番号（ＳＰ）１６ｂｉｔｓ、デスティネーションポート番号（ＤＰ）１６ｂｉｔｓ］との合計１０４ｂｉｔｓから６４Ｋのフローに識別されており、ＦｍｉｎからＦｍａｘまでの範囲のプライオリティ付けを行ったフロー番号Ｆが出力されている。
【０００９】
【発明が解決しようとする課題】
上述した従来のフロー検出方法では、ＩＰヘッダ内の情報とＴＣＰ／ＵＤＰ内の情報とからＩＰパケットを６４Ｋのフローに識別しており、ＦｍｉｎからＦｍａｘまでの範囲のプライオリティ付けを行ったフロー番号Ｆを出力しているので、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）等の大規模で高速かつ高価なメモリを必要とするという問題がある。
【００１０】
そこで、本発明の目的は上記の問題点を解消し、メモリ容量を大幅に削減することができ、ＣＡＭ等の高価なデバイスや低速なソフト処理によらずにフロー検出を行うことができるフロー検出装置及びそれに用いるフロー検出方法を提供することにある。
【００１１】
【課題を解決するための手段】
本発明によるフロー検出装置は、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）パケットのキャリアクラスのＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）保証を実現するために、いくつかのユニークな情報を共有する一連のパケットであるフローを検出するフロー検出装置であって、検出対象の全てのフローに対して互いに異なる値をとるようなハッシュ関数の計算値を計算するハッシュ関数処理手段と、前記ハッシュ関数の計算値を使用するフロー番号と前記フロー各々に設定されたプライオリティとを格納するフロー検出テーブルとを備え、前記フロー検出テーブルを参照してフロー検出を行っている。
【００１２】
本発明によるフロー検出方法は、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）パケットのキャリアクラスのＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）保証を実現するために、いくつかのユニークな情報を共有する一連のパケットであるフローを検出するフロー検出方法であって、検出対象の全てのフローに対して互いに異なる値をとるようなハッシュ関数の計算値を計算しておき、前記ハッシュ関数の計算値を使用するフロー番号と前記フロー各々に設定されたプライオリティとを格納するフロー検出テーブルを参照してフロー検出を行っている。
【００１３】
すなわち、ＩＰパケットのキャリアクラスのＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）保証を実現するにはフロー検出技術が必要である。フロー識別はＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）パケット受信時のポリシング（流量監視）のトラヒック識別子、スイッチにおける優先クラス及びＩＰパケット出力時の帯域制御キュー番号を決定するために必要である。
【００１４】
本発明は検出対象のすべてのフローに対して互いに異なる値をとるようなハッシュ関数ｆを計算しておき、このハッシュ関数ｆの計算値をフロー番号Ｆとして使用している。これによって、メモリ容量を大幅に削減することが可能となるため、ＣＡＭ等の高価なデバイスや低速なソフト処理によらずにフロー検出を行うことが可能となる。
【００１５】
【発明の実施の形態】
次に、本発明の一実施例について図面を参照して説明する。図１は本発明の一実施例によるフロー検出装置の構成を示すブロック図である。図１において、フロー検出装置１はハッシュ関数ｆによる計算を行うハッシュ関数処理部１１を備え、ハッシュ計算後フローテーブル格納メモリ２を参照してフロー検出を行う。
【００１６】
ここで、フローとはいくつかのユニークな情報を共有する一連のパケットである。ユニークな情報としては送信先ＩＰアドレス／送信元ＩＰアドレス、送信先ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）／ＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）ポート番号／送信元ＴＣＰ／ＵＤＰポート番号、プロトコル種別、ＤＳＣＰ（Ｄｉｆｆｓｅｒｖ  Ｃｏｄｅ  Ｐｏｉｎｔ：ＩＰヘッダ内Ｔｙｐｅ  ｏｆ  Ｓｅｒｖｉｃｅフィールドの一部）等がある。また、ハッシュ関数ｆは検出対象の全てのフローに対して互いに異なる値をとるようなハッシュ関数である。
【００１７】
図２は図１のハッシュ計算後フローテーブル格納メモリ２に登録されるハッシュ関数計算後のフロー検出テーブルの一例を示す図である。図２において、ハッシュ関数計算後のフロー検出テーブル２１はフロー番号Ｆ（１〜１０，１１〜２０，１００〜２００，５０〜７０，・・・）と、プライオリティ（Ｐｒｉｏｒｉｔｙ）（ＱｏＳ＃１，ＱｏＳ＃２，ＱｏＳ＃２０，ＱｏＳ＃４）とが記憶されている。
【００１８】
ここで、フロー番号Ｆとしては上記のハッシュ関数ｆの計算値を使用しており、検出対象の全てのフローに対して互いに異なる値をとるようなハッシュ関数ｆはＩＰヘッダ内の情報［ソースアドレス（ＳＡ：Ｓｏｕｒｃｅ  Ａｄｄｒｅｓｓ）、デスティネーションアドレス（ＤＡ：Ｄｅｓｔｉｎａｔｉｏｎ  Ａｄｄｒｅｓｓ）、プロトコル（Ｐ：Ｐｒｏｔｏｃｏｌ）］と、ＴＣＰ／ＵＤＰ内の情報［ソースポート番号（ＳＰ：Ｓｏｕｒｃｅ  Ｐｏｒｔ）、デスティネーションポート番号（ＤＰ：Ｄｅｓｔｉｎａｔｉｏｎ  Ｐｏｒｔ）］とから予め計算されている。
【００１９】
例えば、上記のＩＰヘッダ内の情報及びＴＣＰ／ＵＤＰ内の情報は合計で１０４ｂｉｔｓであるが、この１０４ｂｉｔｓをハッシュ関数ｆによって１６ｂｉｔｓに計算することで、ハッシュ計算後フローテーブル格納メモリ２を６４Ｋ分に削減することが可能となる。
【００２０】
図示せぬスケジューラは上述したフロー番号Ｆをキュー番号として、ＷＦＱ（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ）を行う。ここで、ＷＦＱとは複数のキューがある場合、各キューに割当てられた帯域や優先度に応じてキューに重み付けを設定するとともに、パケットのサイズも考慮して、どのキューのパケットから送出するかを決定するキューイングアルゴリズムである。
【００２１】
上述したハッシュ関数ｆの選び方としては、“Ｐｒａｃｔｉｃａｌ  ｍｉｎｉｍａｉｌ  ｐｅｒｆｅｃｔ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ  ｆｏｒ  ｌａｒｇｅ  ｄａｔａｂａｓｅｓ”［Ｅｄｗａｒｄ  Ａ．ＦＯＸ，Ｌｅｎｗｏｏｄ  Ｓ．Ｈｅａｔｈ，Ｑｉ  Ｆａｎ  Ｃｈｅｎ  ａｎｄ  Ａｍｊａｄ  Ｍ．Ｄａｏｕｄ；Ｃｏｍｍｕｎ．ＡＣＭ３５，１（Ｊａｎ．１９９２），Ｐａｇｅｓ１０５−１２１］、“Ａ  ｆａｓｔｅｒ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｃｏｎｓｔｒｕｃｔｉｎｇ  ｍｉｎｉｍａｌ  ｐｅｒｆｅｃｔ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ”（Ｅｄｗａｒｄ  Ａ．ＦＯＸ，Ｑｉ  Ｆａｎ  Ｃｈｅｎ  ａｎｄ  ＬｅｎｗｏｏｄＳ．Ｈｅａｔｈ；Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｆｉｆｔｅｅｎｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  ＡＣＭ  ＳＩＧＩＲ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｅｓｅａｒｃｈ  ａｎｄ  ｄｅｖｅｌｏｐｍｅｎｔ  ｉｎ  ｉｎｆｏｒｍａｔｉｏｎ  ｒｅｔｒｉｅｖａｌ，１９９２，Ｐａｇｅｓ２６６−２７３）等に記載された方法がある。
【００２２】
図３は図１のハッシュ計算後フローテーブル格納メモリ２のハッシュ関数ｆによるメモリ容量削減のイメージを示す図である。図３において、大規模なフローテーブル格納メモリ３（その内容については図６を参照）がハッシュ関数ｆによってハッシュ計算後フローテーブル格納メモリ２となり、そのメモリ容量を大幅に削減することができる。
【００２３】
本発明の一実施例の利点としてはメモリ容量を大幅に削減することが可能となるため、ＣＡＭ等の高価なデバイスや低速なソフト処理によらずにフロー検出を行うことができる。
【００２４】
しかしながら、問題点として、登録されていないＩＰパケットのフロー検出時に、ハッシュ関数を計算した場合、本来割当てたいプライオリティ付けに当てはまらず、違うプライオリティに割当てられる可能性があるが、これについてはレアケースとしている。
【００２５】
【発明の効果】
以上説明したように本発明によれば、いくつかのユニークな情報を共有する一連のパケットであるフローを検出する際に用いかつフロー各々に設定されたプライオリティを格納するフロー検出テーブルのフロー番号として、検出対象の全てのフローに対して互いに異なる値をとるようなハッシュ関数の計算値を使用することによって、メモリ容量を大幅に削減することができ、ＣＡＭ等の高価なデバイスや低速なソフト処理によらずにフロー検出を行うことができるという効果がある。
【図面の簡単な説明】
【図１】本発明の一実施例によるフロー検出装置の構成を示すブロック図である。
【図２】図１のハッシュ計算後フローテーブル格納メモリに登録されるハッシュ関数計算後のフロー検出テーブルの一例を示す図である。
【図３】図１のハッシュ計算後フローテーブル格納メモリのハッシュ関数ｆによるメモリ容量削減のイメージを示す図である。
【図４】従来のＩＰパケットネットワークの構成例を示すブロック図である。
【図５】従来のフロー検出装置の構成を示すブロック図である。
【図６】図５のフローテーブル格納メモリに登録されるフロー検出テーブルの一例を示す図である。
【符号の説明】
１  フロー検出装置
２  ハッシュ計算後フローテーブル格納メモリ
３  フローテーブル格納メモリ
１１  ハッシュ関数処理部
２１  ハッシュ関数計算後のフロー検出テーブル
【図１】
0003584884.tif 000002
【図２】
0003584884.tif 000003
【図３】
0003584884.tif 000004
【図４】
0003584884.tif 000005
【図５】
0003584884.tif 000006
【図６】
0003584884.tif 000007