(57)【要約】【課題】パケット分類のための方法および装置【解決手段】一実施形態では、マルチプロセッサ／マルチスレッド環境のために効率良くパケットを分類するための方法が開示される。方法は、パケットを受信することから始まる。次いで、受信されたパケットからヘッダ情報が取り出される。次に、第１のハッシュ値が算出される。次いで、第１のハッシュ値をもとにして、ルックアップテーブルの中から１つの対象フィールドが決定される。次に、第２のハッシュ値が算出される。次いで、第２のハッシュ値は、ルックアップテーブルの対象フィールドに格納されている複数のハッシュ値と比較され、ルックアップテーブルの対象フィールドにある複数のハッシュ値の中から第２のハッシュ値と一致する値が決定される。もし一致する値がある場合は、受信されたパケットは、ルックアップテーブルのその行位置にある一致する値に対応するプロセッサに送信される。また、マルチコア／マルチスレッド環境において効率良くパケットを分類するためのネットワークインターフェースカードおよびシステムも提供される。【選択図】図５
2005507212.tif 000002
【特許請求の範囲】
【請求項１】
マルチプロセッサ／マルチスレッド環境のためにパケットを効率良く分類するための方法であって、
パケットを受信し、
前記受信されたパケットからヘッダ情報を取り出し、
第１のハッシュ値を算出し、
前記第１のハッシュ値をもとにしてルックアップテーブルの中から１つの対象フィールドを決定し、
第２のハッシュ値を算出し、
前記ルックアップテーブルの前記対象フィールドに格納されている複数のハッシュ値の中から前記第２のハッシュ値と一致する値を決定するために、前記第２のハッシュ値を前記ルックアップテーブルの前記対象フィールドに格納されている前記複数のハッシュ値と比較し、
一致する値がある場合は、前記受信されたパケットを前記ルックアップテーブルの前記行位置にある前記一致する値に対応するプロセッサに送信する
方法。
【請求項２】
請求項１に記載の方法であって、
前記第２のハッシュ値は前記取り出されたヘッダ情報よりもビットサイズが小さい、方法。
【請求項３】
請求項１に記載の方法であって、
前記対象フィールドは前記ルックアップテーブルの一行である、方法。
【請求項４】
請求項１に記載の方法であって、
前記受信されたパケットを前記ルックアップテーブルの前記対象フィールドにある前記一致する値に対応するプロセッサに送信する動作は、前記受信されたパケットを前記プロセッサに関連付けられた待ち行列に送信することを含む、方法。
【請求項５】
請求項１に記載の方法であって、
前記受信されたパケットからヘッダ情報を取り出す動作は、前記受信されたパケットのヘッダのフィールドをもとにしてキーを定めることを含む、方法。
【請求項６】
請求項５に記載の方法であって、
前記フィールドは前記パケットヘッダの第２〜４層に位置する、方法。
【請求項７】
請求項１に記載の方法はさらに、
一致する値がない場合は、前記受信されたパケットをどのプロセッサに送信するかを決定するためにラウンドロビン処理を実施することを備える方法。
【請求項８】
オプティミスティックなハッシュマッチングを実施するための方法であって、
それぞれが少なくとも１つのプロセッサに関連付けられている複数の値を有するルックアップテーブルを定め、
パケットを受信し、
前記パケットからキーを取り出し、
前記キーから第１のハッシュ値および第２のハッシュ値を算出し、
前記ルックアップテーブルの中から前記第１のハッシュ値に対応する１つの対象フィールドを識別し、
前記対象フィールドの中の前記値の中から前記第２のハッシュ値と一致する値を識別するために前記第２のハッシュ値を前記対象フィールドの中の値と比較し、
前記受信されたパケットを前記対象フィールドの中の前記一致する値に対応するプロセッサに送信する
方法。
【請求項９】
請求項８に記載の方法であって、
前記第１のハッシュ値および前記第２のハッシュ値は、異なるハッシュアルゴリズムによって算出される、方法。
【請求項１０】
請求項９に記載の方法であって、
前記ルックアップテーブルの中の前記複数の値および前記第２のハッシュ値は、共通のハッシュアルゴリズムによって算出される、方法。
【請求項１１】
請求項８に記載の方法はさらに、
前記受信されたパケットに割り当てられたプロセッサのアドレスを決定するために前記対象フィールドの中の前記一致する値に関連付けられたコードにアクセスすることを備える方法。
【請求項１２】
請求項８に記載の方法であって、
前記受信されたパケットを前記対象フィールドの中の前記一致する値に対応するプロセッサに送信する動作は、前記パケットを前記プロセッサに関連付けられた待ち行列の中に保持することを含む、方法。
【請求項１３】
請求項８に記載の方法はさらに、
前記対象フィールドの前記複数の値の中に前記第２のハッシュ値と一致する値がない場合は、複数のプロセッサの中の１つを前記パケットの送信先として識別するためにラウンドロビン処理を実行することを含む、方法。
【請求項１４】
ネットワークインターフェースカードであって、
パケットを受信するための回路と、
前記受信されたパケットのパケットヘッダのフィールドから第１のハッシュ値および第２のハッシュ値を算出するように構成されたパケット分類回路であって、前記第１のハッシュ値は、前記ネットワークインターフェースカードに通じているルックアップテーブルに関連付けられた１つの対象フィールドを示し、前記第２のハッシュ値は、前記対象フィールドの中の値の１つと一致することによって、前記パケットに割り当てられたプロセッサを識別する、パケット分類回路と、
前記パケットに割り当てられた前記プロセッサに関連付けられた待ち行列に前記パケットを送信するための回路と
を備えるネットワークインターフェースカード。
【請求項１５】
請求項１４に記載のネットワークインターフェースカードであって、
マルチプロセッサチップ上にあるネットワークインターフェースカード。
【請求項１６】
請求項１５に記載のネットワークインターフェースカードであって、
前記マルチプロセッサチップはサーバコンピュータの中に含まれる、ネットワークインターフェースカード。
【請求項１７】
マルチコア／マルチスレッド環境においてパケットを効率良く分類するためのシステムであって、
複数のプロセッサコアと、
前記パケットのパケットヘッダから第１のハッシュ値および第２のハッシュ値を算出するように構成されたパケット分類回路を有すると共にネットワークからパケットを受信するためのネットワークインターフェースカード（ＮＩＣ）であって、前記第１のハッシュ値はテーブルの中の１つの対象フィールドを示し、前記第２のハッシュ値は前記対象フィールドの中の１つの位置にあるデータを識別し、前記データは前記複数のプロセッサコアの中の１つを前記パケットの送信先として示す、ネットワークインターフェースカードと、
前記マルチプロセッサチップに通じると共に、前記テーブルに関連付けられたデータを格納するように構成された半導体チップと
を備えるシステム。
【請求項１８】
請求項１７に記載のシステムであって、
前記テーブルは高速周期ダイナミックＲＡＭ（ＦＣＤＲＡＭ）に格納されている、システム。
【請求項１９】
請求項１７に記載のシステムであって、
前記システムはサーバコンピュータである、システム。
【請求項２０】
請求項１７に記載のシステムであって、さらに、
複数のプロセッサコアに１対１で対応する一群の待ち行列を備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、プロセッサのアーキテクチャに関するものである。本発明は、より具体的には、ネットワークインターフェースのためのパケットの分類に関するものである。
【背景技術】
【０００２】
一枚のチップに設けられた共用ネットワークインターフェースに複数のコアを有するサーバは、受信したパケットを分類し、複数のコアのどのコアにその特定のパケットの処理を割り当てるかを決定する必要がある。パケット分類器が無いと、同一のフローからの複数のパケットがそれぞれ異なるコアに割り当てられ、コア同士の間で処理が逐次化される恐れがある。たとえ、同一のフローからのパケットが同じプロセッサコアに割り当てられた場合でも、このプロセスはオーバーヘッドが大きくなる。例えば、パケットが間違ったコアに転送された場合は、そのコアから正しいコアへとパケットを転送する必要がある。
【０００３】
パケット分類システムは、一般に、フローを識別するにあたってパケットヘッダのＬ２〜Ｌ４の部分を突き合わせる必要がある。あるパケット分類アルゴリズムは、パケットの分類処理に単一ハッシュ法（single hashing）を取り入れている。この場合は、対象となるフィールドすなわちパケットの送信元、宛先、ポート番号等を組み合わせたものに対応する１つのハッシュ値が算出される。算出されたハッシュ値は、次に、正確なＬ２〜Ｌ４フロー情報、すなわち突き合わせ作業に使用されるキーを含むルックアップテーブルを検索するために使用される。ルックアップテーブルは、しかしながら、一枚のマルチコア／マルチスレッドチップで何百万ものフローを扱う場合は過度に大きくなる。これは、何百万ものフローが同時にアクティブになる可能性があるサーバアプリケーションの場合に特に顕著である。また、ルックアップテーブルに通じる通信リンクは、パケット分類システムをサポートするためには高帯域である必要がある。これは、複合１ギガビット（ＧＢ）環境や１０ＧＢ環境等の高帯域環境において特に必要である。したがって、複数のマルチコア／マルチスレッドチップを有するサーバでは、このようなシステムをサポートするために必要なルックアップテーブルが過度に大きくなるので、上述のようなハッシュアルゴリズムを使用したパケットの分類は最適とは言えない。
【０００４】
図１は、パケットの分類に使用されるハッシュルックアップテーブルを図示したものである。ハッシュルックアップテーブル１００は、複数の行と列からなる。キー１０２は、受信されたパケットヘッダから取り出される。次に、ハッシュが算出され、行番号１０４が得られる。算出されたハッシュは、次に、キー１０２が格納されている行を検索するために使用される。ハッシュテーブル１００から検索された位置には、キーがまるごと格納されている。ハードウェアは、次に、各キーを取り出して、受信されたパケットのキーと比較し、厳密に一致するキーを探し出す。各キーは、約１００ビットから約３００ビットまでの大きさである。これは、インターネットにおけるデータ伝送に使用されるインターネットプロトコル（ＩＰ）の種類に応じて異なる。したがって、多数のキーを格納しようとすると、テーブルは過度に大きくなる。また、マルチチップ／マルチコア処理環境をサポートするために必要とされる帯域も、やはり過度に大きくなる。
【０００５】
以上からわかるように、マルチチップ／マルチコア処理環境を効率良くサポートできるように構成されたパケット分類システムを、同システムのサポートに必要とされる帯域およびルックアップテーブルに必要とされるメモリを低減させられるかたちで提供する必要がある。
【発明の開示】
【０００６】
本発明は、一般に、マルチコア／マルチスレッド環境において効率良く作動できるように構成されたパケット分類器を提供することによって、これらの必要性を満たすものである。なお、本発明は、装置、システム、デバイス、方法を含む様々なかたちで実現することが可能である。以下では、本発明の実施形態をいくつか取り上げて説明する。
【０００７】
一実施形態では、マルチプロセッサ／マルチスレッド環境において効率良くパケットを分類するための方法が提供される。この方法は、パケットを受信することから始まる。次いで、受信されたパケットからヘッダ情報が取り出される。次に、第１のハッシュ値が算出される。次いで、第１のハッシュ値をもとにして、ルックアップテーブルの中から対象となるフィールドが決定される。次に、第２のハッシュ値が算出される。次いで、第２のハッシュ値はルックアップテーブルの対象フィールドに格納されたハッシュ値と比較され、ルックアップテーブルの対象フィールドに格納された値の中から第２のハッシュ値と一致する値が決定される。一致する値がある場合は、受信されたパケットは、ルックアップテーブルのその行位置にある一致する値に対応するプロセッサに送信される。
【０００８】
別の一実施形態では、オプティミスティックなハッシュマッチングを実施するための方法が提供される。この方法は、複数の値を格納されたルックアップテーブルを定めることから始まる。ルックアップテーブルに格納された複数の値は、それぞれ少なくとも一つのプロセッサに関連付けられている。次いで、パケットが受信される。次に、パケットからキーが取り出される。次いで、キーをもとにして第１のハッシュ値および第２のハッシュ値が算出される。次に、ルックアップテーブルの中から第１のハッシュ値に対応する１つの対象フィールドが探し出される。次いで、第２のハッシュ値は対象フィールドの中の値と比較され、対象フィールドの中の値から第２のハッシュ値と一致する値が識別される。次に、受信されたパケットは対象フィールドの中のその一致する値に対応するプロセッサに送信される。
【０００９】
さらに別の一実施形態では、ネットワークインターフェースカードが提供される。ネットワークインターフェースカードは、パケットを受信するための回路を備える。ネットワークインターフェースカードは、また、パケット分類回路を備える。パケット分類回路は、受信されたパケットのパケットヘッダのフィールドから第１のハッシュ値および第２のハッシュ値を算出するように構成される。第１のハッシュ値は、ネットワークインターフェースカードに通じているルックアップテーブルに関連付けられた１つの対象フィールドを示す。第２のハッシュ値は、対象フィールドの中の１つの値に一致することによって、パケットに割り当てられたプロセッサを識別する。ネットワークインターフェースカードは、また、パケットに割り当てられたプロセッサに関連付けられた待ち行列（キュー）にパケットを送信するための回路を備える。
【００１０】
さらに別の一実施形態では、マルチコア／マルチスレッド環境において効率良くパケットを分類するためのシステムが提供される。このシステムは、データを格納できる半導体チップに通じているマルチプロセッサチップを備える。マルチプロセッサチップは、複数のプロセッサコアと、ネットワークからのパケットを受信するためのネットワークインターフェースカード（ＮＩＣ）とを備える。ＮＩＣは、パケットのパケットヘッダから第１のハッシュ値および第２のハッシュ値を算出するように構成されたパケット分類回路を備える。第１のハッシュ値は、テーブルの中の１つの対象フィールドを示す。第２のハッシュ値は、その対象フィールドの中の１つの位置にあるデータを識別する。データは、複数のプロセッサコアの中の１つをパケットの送信先として示す。システムは、また、テーブルに関連付けられたデータを格納するように構成された半導体チップを備える。半導体チップは、マルチプロセッサチップと接続されている。
【００１１】
本発明の他の特徴および利点は、本発明の原理を例示した添付の図面を参照した以下の詳細な説明から明らかになる。
【００１２】
本発明は、添付の図面を参照した以下の詳細な説明によって容易に理解される。図中、同一の参照番号は類似の要素を表すものとする。
【発明を実施するための最良の形態】
【００１３】
以下では、オプティミスティックなハッシュ処理を通してマルチスレッド／マルチコア環境のためにパケットを分類するための装置および方法の発明が説明される。しかしながら、当業者ならば明らかなように、本発明は、これらの詳細の一部または全部を特定しなくても実施することが可能である。また、本発明が不必要に不明瞭化されることのないように、周知の処理の詳述は省略した。また、本明細書で使用される「約」とは、対応する値の±１０％を含む範囲を意味するものとする。
【００１４】
以下で説明される実施形態は、パケット分類のためのオプティミスティックなハッシュ処理を提供する。一実施形態では、先ず、対象フィールドの第１のハッシュ値が算出される。次いで、パケッドヘッダのＬ２〜Ｌ４情報から第２のハッシュ値が計算される。第２のハッシュ値は、次いで、ルックアップテーブルに格納される。なお、第１および第２のハッシュ値の計算には、互いに異なるアルゴリズムが使用される。第２のハッシュ値は、ビットサイズでは、キーのために取り出された正確なＬ２〜Ｌ４パケットヘッダ情報よりも大幅に小さい。したがって、ルックアップテーブルが必要とする大きさも低減される。本実施形態では、第１のハッシュ値および第２のハッシュ値は比較することが可能である。また、ルックアップテーブルを有するチップとマルチコア／マルチスレッドチップとで必要とされる帯域の差も同様に低減される。第２のハッシュ処理は結果としてコリジョンを生じるので、厳密な一致があったか否かはソフトウェアがパケットヘッダを調べることによって決定することができる。
【００１５】
図２は、オプティミスティックなハッシュ処理を実行するように構成されたパケット分類器を有するマルチコア／マルチスレッドチップを、本発明の一実施形態にしたがって示した概略図である。マルチプロセッサチップ１１０は、複数のプロセッサコア１１２−１〜１１２−８およびキャッシュメモリ１１４を備える。ネットワークインターフェースカード（ＮＩＣ）１１６は、チップ１１０に設けられている。パケット分類器１２０は、受信されたパケッドヘッダを後述のハッシュ処理を実施することによって調べるように構成された回路を備える。ハッシュ値はルックアップテーブル１２２に格納された値と比較され、それによって、受信されたパケッドにどのプロセッサコアを割り当てるかが決定される。どのプロセッサコア１１２−１〜１１２−８を割り当てるかが決定されると、パケットはその割り当てられたプロセッサに対応する待ち行列１１８−１〜１１８−ｎに送信される。一実施形態では、待ち行列１１８−１〜１１８−ｎの数はチップ上１１０のプロセッサコア１１２−１〜１１２−８の数に等しい。したがって、チップ１１０が８つのプロセッサコア１１２−１〜１１２−８を有しているならば、待ち行列１１８−１〜１１８−ｎの数も８に等しい。なお、図中のチップ１１０は８つのプロセッサコア１１２−１〜１１２−８を有しているが、チップは任意の適切な数のプロセッサコアを有して良いので、これは例示のみを目的としたものであって拘束性を有さない。当業者ならばわかるように、ルックアップテーブル１２２は、マルチプロセッサチップ１１０に通じる半導体チップの上に設けて良い。別の一実施形態では、ルックアップテーブル１２２は、高速周期ダイナミックＲＡＭ（ＦＣＤＲＡＭ）等のメモリに格納される。なお、チップ１１０およびルックアップテーブル１２２は、サーバアプリケーションを実行するように構成されたウェブサーバ等のサーバコンピュータに組み込むこともできる。代表的なサーバアプリケーションとしては、電子商取引アプリケーションやデータベースアプリケーション等がある。
【００１６】
図３は、受信されたパケットに割り当てられたプロセッサを決定するための二段階のオプティミスティックなハッシュ処理を、本発明の一実施形態にしたがって示した説明図である。受信されたパケットＡ  １３２のＬ２〜Ｌ４ヘッダ情報は、ＮＩＣによって取り出される。受信されたパケットを解析してＬ２〜Ｌ４ヘッダ情報を取り出すための回路を有するＮＩＣとしては、例えば図２のＮＩＣが適切である。一実施形態では、解析および取り出しによって、受信されたパケットに関連付けられたキーA１３４が得られる。キーA１３４に対して第１のハッシュ動作を実施すると、ハッシュルックアップテーブル１３０の中の１つの対象フィールドを示す第１のハッシュ値１３６が得られる。例えば本発明の一実施形態では、第１のハッシュ値１３６は行番号を示す。キーA１３４に対して第２のハッシュ動作を実施すると、値Ｈ2（ＫA）１３８が得られる。なお、第２のハッシュ動作を実施するアルゴリズムは第１のハッシュ動作を実施するアルゴリズムとは異なる。一実施形態では、第２のハッシュ動作によって得られる値はキーよりも大幅にビットサイズが小さい。例えば一実施形態では、第２のハッシュ動作によって得られる値は１６ビット以下であり、キーのビットサイズと比べて少なくとも一桁は小さい。要するに、第２のハッシュ値は第１のハッシュ値よりも小さい。第２のハッシュ値は、次に、ハッシュテーブル１３０の対象フィールドに格納されたハッシュ値との比較に使用される。ここでは、第２のハッシュ動作によって得られる値Ｈ2（ＫA）１３８とハッシュテーブル１３０の対象フィールドの列１に格納された値とが一致する。ハッシュテーブル１３０の各エントリには、ソフトウェア情報１４０が関連付けられている。したがって、一致する値が決定されたときは、ソフトウェア情報１４０を取り出して、受信されたコアをハッシュルックアップテーブル１３０の中の一致する格納値に関連付けられたプロセッサコアに送信する。ソフトウェア情報１４０は、例えば、ハッシュルックアップテーブル１３０に組み込まれたコードの形態をとって良い。一実施形態では、コードは、ハッシュルックアップテーブルの中の一致する位置に割り当てられたプロセッサに関連付けられた待ち行列にパケットを送信するハンドルを有する。なお、ハッシュルックアップテーブル１３０はｍ×ｎの行列である。ここで、ｍおよびｎは任意の適切な整数である。
【００１７】
図４のハッシュルックアップテーブル１３０は、当然ながら、第２のハッシュ値の突き合わせを行えるようになる以前に構築されている。一実施形態では、ハッシュルックアップテーブルは、パケットの処理に伴って構築される。例えば、一致する値が見つからない場合は、そのパケットはラウンドロビン処理を経て１つのプロセッサコアに割り当てられる。そして、その一致しなかったハッシュ値はハッシュルックアップテーブル１３０に格納される。こうすれば、後に同じハッシュ値を有するパケットが受信された場合に、ラウンドロビン処理を経ることなく突き合わせおよびそれに続く特定のプロセッサコアに対する割り当てを行うことが可能である。
【００１８】
図４は、ハッシュ処理に使用されるキーを定めるパケットヘッダのＬ２〜Ｌ４部分を、本発明の一実施形態にしたがって詳細に示した説明図である。送られてきたデータパケットのヘッダは、層２（Ｌ２）１５０、層３（Ｌ３）１５２、層４（Ｌ４）１５４、およびその他の層と共に巡回冗長検査（ＣＲＣ）層１５６を有する。Ｌ２  １５０は、当業者に一般に知られた情報のうち、宛先アドレス１５０ａおよび送信元アドレス１５０ｂを有する。Ｌ３  １５２は、例えば通信制御プロトコル（ＴＣＰ）やユーザデータグラムプロトコル（ＵＤＰ）等のプロトコル部分１５２ａを有する。また、送信元アドレス部分１５２ｂおよび宛先アドレス部分１５２ｃも、やはりハッシュアルゴリズムによって考慮することが可能である。Ｌ４  １５４は、送信元ポート１５４ａおよび宛先ポート１５４ｂを有する。当業者ならば明らかなように、図面の制約上、図４には各層の全てのフィールドを図示しているわけではない。しかしながら、図３を参照にして上述したように、一実施形態では、図示されたフィールドは、キーを定めることを目的とした受信ヘッダの解析によって受信ヘッダから取り出されたものである。さらに、ハッシュアルゴリズムは任意の適切なフィールドを考慮することが可能なので、本発明は上述されたフィールドに限定されない。
【００１９】
コリジョンは、キーのビットサイズが大きいからではなく、むしろハッシュ値を格納することが原因で生じる。つまり、２つの受信パケットのキーが互いに異なる場合でも、算出されるハッシュ値が希に同一となる可能性がある。このとき、ハードウェアはこれら２つのパケットを同じプロセッサすなわち同じデータフローに割り当てる。一実施形態では、実際のヘッダ情報に対してソフトウェアチェックを行うことによってコリジョンを解決する。
【００２０】
図５は、受信パケットの送信先となるマルチプロセッサチップを決定するために実施される二段階のハッシュマッチング処理の各動作を本発明の一実施形態にしたがって示したフローチャートである。この方法は、複数の値を有するルックアップテーブルが定められる動作１６０から始まる。一実施形態では、適切なルックアップテーブルは、行列を構成する複数のセルに複数のハッシュ値を格納された図３のテーブルである。ルックアップテーブルは、マルチプロセッサチップに通じたチップ上に設けられている。一実施形態では、ルックアップテーブルは、例えば高速周期ダイナミックＲＡＭ（ＦＤＣＤＲＡＭ）等のメモリチップに格納されている。方法は、次いで、パケットが受信される動作１６２に進む。例えば、ネットワークインターフェースカード（ＮＩＣ）がインターネット等の分散ネットワークからパケットを受信して良い。方法は、次いで、パケットからキーが取り出される動作１６４に進む。一実施形態では、パケットヘッダのＬ２〜Ｌ４層に含まれるフィールドが解析され、キーのための情報が取り出される。方法は、次いで、キーから第１のハッシュ値および第２のハッシュ値が算出される動作１６６に進む。一実施形態では、第１のハッシュ値および第２のハッシュ値は互いに異なるハッシュアルゴリズムを使用して算出されるので、第２のハッシュ値は取り出されたキーおよび第１のハッシュ値よりも小さい。なお、動作１６０のルックアップテーブルの中に定められた複数のハッシュ値は、第２のハッシュアルゴリズムによって算出されたものである。
【００２１】
図５の方法は、次いで、第１のハッシュ値によってルックアップテーブルの中から対象フィールドが識別される動作１６８に進む。図３を参照にして上述したように、本発明の一実施形態における対象フィールドは、第１のハッシュ処理によって得られた値で示されるハッシュテーブルの中の一行である。なお、当業者ならば明らかなように、対象フィールドはハッシュテーブルの中の一列であっても良い。方法は、次いで、ハッシュルックアップテーブルの中の対象フィールドに格納されたハッシュ値の中に第２のハッシュ値と一致するものがあるか否かが決定される決定動作１７０に進む。ここでは、比較機能を実施するように構成されたハードウェアがこの動作を実行することができる。すなわち、対象フィールドを読み出して、その中のエントリを第２のハッシュ値と比較することができる。キーに対して第２のハッシュ処理を実施することによって得られたハッシュ値と、対象フィールドに格納されているハッシュ値の１つとが一致する場合は、受信されたパケットは、動作１７２において、対象フィールドに格納されている一致したハッシュ値に対応するプロセッサに送信される。一実施形態では、パケットは、そのプロセッサすなわちプロセッサコアに関連付けられた待ち行列に送信される。なお、図３を参照にして上述したように、パケットを適切な待ち行列に送るにあたっては、ハッシュテーブルに組み込まれたコードを使用して良い。一致するハッシュ値が無い場合は、動作１７４においてラウンドロビン処理が実行され、マルチコアチップの中のどのプロセッサコア、すなわちどの待ち行列にパケットを送信するかが決定される。
【００２２】
上述した実施形態は、簡単に言うと、パケット分類のためのオプティミスティックなハッシュ処理を提供するものである。パケッドヘッダ情報からは第１のハッシュ値が算出され、この値はハッシュルックアップテーブルの中から対象フィールドを識別するために使用される。また、同じパケッドヘッダ情報からは第２のハッシュ値も算出され、この値は対象フィールドの中に自身に一致する値を含むセルすなわち場所が存在するか否かを決定するために使用される。上述したように、ハッシュルックアップテーブルには第２のハッシュアルゴリズムによって得られた値が格納されている。第２のハッシュ値はキーすなわちパケットヘッダ情報よりもビットサイズが大幅に小さいので、ハッシュルックアップテーブルの大きさも大幅に低減される。例えば、ヴァージョン４のインターネットプロトコル（ＩＰｖ４）のパケットの代表的なキーサイズは約１００ビット以上であり、ヴァージョン６のインターネットプロトコル（ＩＰｖ６）のパケットの代表的なキーサイズは約３００ビットである。ところが、上述したように、第２のハッシュ値のビットサイズは１６ビット以下であり、別の一実施形態では、第２のハッシュ値のビットサイズは１０ビット以下である。得られる第２のハッシュ値のビットサイズは、当然ながら、計算に使用されるハッシュアルゴリズムに応じて異なる。このように、第２のハッシュ値を使用すれば、ハッシュルックアップテーブルに格納される値のビットサイズが一桁またはそれ以上の割合で低減される。その結果、ハッシュルックアップテーブルの大きさも大幅に低減される。こうすると、ハッシュルックアップテーブルを含むチップとプロセッサチップとの間の通信リンクに必要な帯域も同様に低減される。なお、ここで説明した実施形態は、他の任意の適切なパケットベースのプロトコルに使用することも可能である。
【００２３】
さらに、本発明は、携帯端末、マイクロプロセッサシステム、マイクロプロセッサベースのまたはプログラマブルな家電製品、ミニコンピュータ、およびメインフレームコンピュータ等の他の構成のコンピュータシステムに対して実施することも可能である。本発明は、また、ネットワークを通じて連結された遠隔処理機器によってタスクを実施される分散コンピューティング環境において実施することも可能である。
【００２４】
上述した実施形態を念頭におけば、本発明が、コンピュータシステムに格納されたデータを含む様々なコンピュータ動作を利用することがわかる。これらの動作は、物理量の物理的操作を必要とする。これらの物理量は、格納、転送、結合、比較、およびその他の操作を実施することが可能な電気信号または磁気信号のかたちを取るのが一般的であるが、それらに限定されることはない。さらに、実施される操作は製造する、識別する、決定する、比較する等の表現をとることが多い。
【００２５】
本発明の一部を構成するここで説明される動作は、いずれも有用なマシン動作である。本発明は、また、これらの動作を実施するためのデバイスすなわち装置にも関する。装置は、必要な目的のために特別に作成されたものであって良いし、あるいは、格納されたコンピュータプログラムによって選択的に活動化される若しくは構成される汎用コンピュータであっても良い。具体的に言うと、ここで教示された内容にしたがって書かれたコンピュータプログラムと共に各種の汎用マシンを使用する場合もあるし、あるいは、必要な動作を実施するべく特化された装置を構築する方が好都合な場合もある。
【００２６】
以上では、理解を促すために、ある程度の詳細を特定したうえで本発明を説明したが、添付した特許請求の範囲の範囲内ならば、一定の取り換えおよび変更が可能であることは明らかである。したがって、上述した実施形態は、例示的なものであって拘束性のものではなく、本発明は、上述した詳細に限定されず、添付した特許請求の範囲およびその等価物の範囲内で変更することが可能である。
【図面の簡単な説明】
【００２７】
【図１】パケットの分類に使用されるハッシュルックアップテーブルの図である。
【図２】オプティミスティックなハッシュ処理を実行するように構成されたパケット分類器を有するマルチコア／マルチスレッドチップを本発明の一実施形態にしたがって示した簡単な説明図である。
【図３】受信パケットに割り当てられるプロセッサを決定するために実施される二段階のオプティミスティックなハッシュ処理を本発明の一実施形態にしたがって示した説明図である。
【図４】ハッシュ動作に使用されるキーを定めるパケットヘッダのＬ２〜Ｌ４部分を本発明の一実施形態にしたがって示した詳細な説明図である。
【図５】受信パケットの送信先となるマルチプロセッサチップを決定するために実施される二段階のハッシュマッチング処理の各動作を本発明の一実施形態にしたがって示したフローチャートである。
【符号の説明】
【００２８】
１００…ハッシュルックアップテーブル
１０２…キー
１０４…行番号
１１０…マルチプロセッサチップ
１１２−１〜１１２−８…プロセッサコア
１１４…キャッシュメモリ
１１６…ネットワークインターフェースカード
１１８−１〜１１８−ｎ…待ち行列
１２０…パケット分類器
１２２…ルックアップテーブル
１３２…パケット
１３４…キー
１３６…第１のハッシュ値
１３８…第２のハッシュ値
１４０…ソフトウェア情報
１５０…層２
１５０ａ…宛先アドレス
１５０ｂ…送信元アドレス
１５２…層３
１５２ａ…プロトコル部分
１５２ｂ…送信元アドレス部分
１５２ｃ…宛先アドレス部分
１５４…層４
１５４ａ…送信元ポート
１５４ｂ…宛先ポート
１５６…巡回冗長検査
【図１】
2005507212.tif 000003
【図２】
2005507212.tif 000004
【図３】
2005507212.tif 000005
【図４】
2005507212.tif 000006
【図５】
2005507212.tif 000007
【国際公開パンフレット】
2005507212.tif 000008
2005507212.tif 000009
2005507212.tif 000010
2005507212.tif 000011
2005507212.tif 000012
2005507212.tif 000013
2005507212.tif 000014
2005507212.tif 000015
2005507212.tif 000016
2005507212.tif 000017
2005507212.tif 000018
2005507212.tif 000019
2005507212.tif 000020
2005507212.tif 000021
2005507212.tif 000022
2005507212.tif 000023
2005507212.tif 000024
2005507212.tif 000025
2005507212.tif 000026
【国際公開パンフレット（コレクトバージョン）】
2005507212.tif 000027
2005507212.tif 000028
【国際調査報告】
2005507212.tif 000029
2005507212.tif 000030
2005507212.tif 000031