(57)【要約】  アドレススペース中でのリクエストされたアドレスのアドレス検索に使用するための決定ツリーを構築するための方法及びコンピュータシステムである。アドレススペースは基本アドレス域のセットとして構成される。各基本アドレス域は下限及び上限アドレスにより規定され、アドレススペース中のアドレスは予め定められた数のビットにより表される。【選択図】図６ａ
2012524932.tif 000002
【特許請求の範囲】
【請求項１】
アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築する方法において、
前記アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は下限及び上限アドレスにより規定され、
前記アドレススペース中のアドレスは予め定められた数のビットにより表されており、
前記方法は、
−前記リクエストされたアドレスが属する前記基本アドレス域のセットから特定の基本アドレス域を決定するために決定ツリーを構成し、
前記決定ツリーは少なくとも１つのレベルを具備し、前記少なくとも１つのレベルは少なくとも１つのノードを具備し、
前記少なくとも１つのノードはノードアドレス域へマップするように構成されており、前記ノードアドレス域は前記アドレススペースのノード関連部分であり、前記ノードアドレス域は下限及び上限のノードアドレスにより規定され、
前記少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチは前記ノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
前記ブランチアドレス域は前記ノードアドレス域中のノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、前記分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定し、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、前記少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるか前記ノードアドレス域中の全てのアドレスで共通のアドレス部分であり、
−選択規則にしたがって、前記少なくとも１つのノード中に前記複数のアドレス部分を記憶するステップを含み、
前記選択規則は動作のグループからの少なくとも１つの動作を含み、前記動作は、
−前記ノードに一度だけ前記少なくとも１つの共通のアドレス部分を記憶し、
−前記少なくとも１つの省略可能なアドレス部分を省略し、
−前記分解ステップにおいて決定されたときの全ての他のアドレス部分を前記ノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は前記少なくとも１つの共通のアドレス部分または前記少なくとも１つの省略可能なアドレス部分のいずれでもない方法。
【請求項２】
前記少なくとも１つのノードの全てのブランチアドレス域の集合は前記少なくとも１つのノードのノードアドレス域である請求項１記載の方法。
【請求項３】
前記ブランチアドレス域は前記ブランチが指向する前記ノードの前記ノードアドレス域である請求項１記載の方法。
【請求項４】
前記ノードに記憶された前記アドレス部分により占有される総ビット数は前記ノードアドレスの総ビット数よりも少ない請求項１記載の方法。
【請求項５】
ノードは２つのノードブランチを有する単一のノードアドレスのアドレス部分を記憶するように構成され、前記単一のノードアドレスは少なくとも１つの省略可能なアドレス部分を有している請求項１記載の方法。
【請求項６】
前記決定ツリーはさらに少なくとも上位レベルより下の下位レベルを有するように構成され、前記下位レベルのノードは前記決定ツリーのリーフノードとして構成され、各リーフノードは前記基本アドレス域のセットから１つの基本アドレス域または１つの基本アドレス域の一部へマップし、各リーフノードはそれが属する前記それぞれの基本アドレス境界に関連される情報を記憶している請求項１記載の方法。
【請求項７】
各ノードはアドレス域を規定する接頭辞または接頭辞のセットから接頭辞に対するポインタを記憶するように構成され、前記接頭辞は前記ノードアドレス域を含む前記接頭辞のセットの前記最長の一致する接頭辞である請求項６記載の方法。
【請求項８】
リーフノードではない各ノードはさらに、前記ノードアドレスにおいて終点を有する接頭辞数をカウントするためのカウンタ値が配置されているノードアドレス当りのカウンタ値を記憶するように構成されている請求項７記載の方法。
【請求項９】
さらに、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを含み、前記ステップは前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記リクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの次のレベルのノードへブランチするステップを含んでいる請求項６記載の方法。
【請求項１０】
さらに、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを含み、前記ステップは前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
予め規定された定数値を有する前記リクエストされたアドレスを減算し、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記減算結果のそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの次のレベルのノードへブランチするステップを含んでいる請求項６記載の方法。
【請求項１１】
前記少なくとも１つの省略可能なアドレス部分は前記予め定められた数のビットの共通のノード接頭辞サブセットとしてノードアドレス域中の全てのアドレスに対して前記少なくとも１つの共通部により決定される共通のノード接頭辞であり、前記共通のノード接頭辞サブセットは前記ノードに記憶された前記アドレス部分のビットの前記サブセットから省略されている請求項１記載の方法。
【請求項１２】
前記少なくとも１つの省略可能なアドレス部分は前記ノードアドレス域中のノードアドレスの接尾辞を表し、前記接尾辞は値「ゼロ」を有し、前記少なくとも１つの省略可能なアドレス部分は前記ノードに記憶されるのを省略されている請求項１記載の方法。
【請求項１３】
前記少なくとも１つの共通のアドレス部分は前記ノード中の２以上のノードアドレスに共通であり、前記少なくとも１つの共通のアドレス部分は前記ノードにおいて一度のみ記憶され、取られるノードブランチを決定した時に一度のみ前記アドレスの対応するアドレス部分と比較される請求項１記載の方法。
【請求項１４】
予め定められた定数値を、前記下限及び上限のノードアドレスから、および各ノードアドレスから、および前記リクエストされたアドレスから減算するステップを含んでおり、
前記減算は各ノードアドレスの前記分解に先行している請求項１記載の方法。
【請求項１５】
前記予め定められた定数値は前記下限のノードアドレスの前記値に等しい請求項１４記載の方法。
【請求項１６】
さらに前記複数のビットにおいて圧縮関連の技術を適用することにより、前記ノードに記憶された前記アドレス部分により占有される総ビット数を減少するステップを含んでいる請求項１記載の方法。
【請求項１７】
前記比較の結果は上位桁アドレス部分から下位桁アドレス部分による優先度によりノードアドレス毎に考慮されており、ノードアドレスの下位桁アドレス部分の前記比較結果は前記ノードアドレスの前記上位桁アドレス部分の比較結果が等しい場合にのみ考慮され、
前記方法は、前記リクエストされたアドレスが属する前記ブランチアドレス域を規定するためノードアドレス毎に前記比較結果を組み合わせるステップを含んでおり、結果として前記ブランチアドレス域により規定されるように次のレベルへブランチするステップを含んでいる請求項９または１０記載の方法。
【請求項１８】
前記決定ツリーを構成するステップは、
−基本アドレス域の前記セットからのレンジ境界であるアドレスを選択し、前記選択されたアドレスの前記部分は前記決定ツリーのノードに含まれ、
−前記決定ツリー構造において前記ノードを構成するステップを含んでおり、それによって前記決定ツリーの各リーフノードは、１つの基本アドレス域を指向するかまたは基本アドレス域の前記セットから１つの基本アドレス域のサブセットを指向する請求項６記載の方法。
【請求項１９】
前記決定ツリーを構成するステップは上から下へのヒューリスティックにより行われ、
−一部がノードに含まれるアドレスを前記決定ツリーの前記上位レベルから開始して選択し、
−その後、下方向で次のレベルの前記ノードを構築し、
−全てのリーフノードが基本アドレス域または基本アドレス域の前記セットの基本アドレス域のサブセットを指向するときに終了するステップを含んでいる請求項１８記載の方法。
【請求項２０】
前記決定ツリーを構成するステップは下から上へのヒューリスティックにより実現され、
−一部がノードに含まれるアドレスを、リーフノードにブランチするノードを最初に構成する前記決定ツリーの前記下位レベルから選択を開始し、前記決定ツリーの各リーフノードは基本アドレス域または基本アドレス域の前記セットのアドレス域のサブセットを指向し、
−その後、前記決定ツリーに沿って上方向で次のレベルのノードを構築し、
−単一のルートノードが上位レベルで構築されるときに終了するステップを含んでいる請求項１８記載の方法。
【請求項２１】
アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するコンピュータシステムにおいて、
前記アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は下限及び上限アドレスにより規定され、
前記アドレススペース中のアドレスは予め定められた数のビットにより表されており、
前記コンピュータシステムは、メモリ及びプロセッサを具備し、前記プロセッサは前記メモリに結合され、ここで前記プロセッサは前記アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための前記決定ツリーを構築するための方法を実行するように構成され、その方法は、
−前記リクエストされたアドレスが属する基本アドレス域の前記セットから特定の基本アドレス域を決定するための前記決定ツリーを構成し、
前記決定ツリーは少なくとも１つのレベルを具備し、前記少なくとも１つのレベルは少なくとも１つのノードを具備し、
前記少なくとも１つのノードはノードアドレス域へマップするように構成されており、前記ノードアドレス域は前記アドレススペースのノード関連部分であり、前記ノードアドレス域は下限及び上限のノードアドレスにより規定され、
前記少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチは前記ノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
前記ブランチアドレス域は前記ノードアドレス域中のノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、前記分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定し、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、前記少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるか前記ノードアドレス域中の全てのアドレスで共通のアドレス部分であり、
−選択規則にしたがって、前記少なくとも１つのノード中に前記複数のアドレス部分を記憶するステップを含み、
前記選択規則は動作のグループからの少なくとも１つの動作を有し、前記動作は、
−前記ノードに一度だけ前記少なくとも１つの共通のアドレス部分を記憶し、
−前記少なくとも１つの省略可能なアドレス部分を省略し、
−前記分解ステップにおいて決定されたときの全ての他のアドレス部分を前記ノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は前記少なくとも１つの共通のアドレス部分または前記少なくとも１つの省略可能なアドレス部分ではないコンピュータシステム。
【請求項２２】
前記コンピュータシステムは、
少なくとも上位レベルより下の下位レベルを有するように前記決定ツリーを構成するステップを実行するように構成され、前記下位レベルのノードは前記決定ツリーのリーフノードとして構成され、各リーフノードは基本アドレス域の前記セットから１つの基本アドレス域または１つの基本アドレス域の一部へマップし、各リーフノードはそれが属するそれぞれの基本アドレス境界に関連される情報を記憶している請求項２１記載のコンピュータシステム。
【請求項２３】
さらに、前記コンピュータシステムは、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを実行するように構成され、前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
前記それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記リクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの前記次のレベルのノードへブランチするステップを含んでいる請求項２２記載のコンピュータシステム。
【請求項２４】
さらに、前記コンピュータシステムは、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを実行するように構成され、前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
予め規定された定数値を有する前記リクエストされたアドレスを減算し、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記減算結果のそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの次のレベルのノードへブランチするステップを含んでいる請求項２２記載のコンピュータシステム。
【請求項２５】
前記プロセッサは複数の処理ユニットを具備し、各処理ユニットは前記決定ツリーの少なくとも１つのレベルに関連され、前記決定ツリー計算の前記関連されるレベルにおいて、前記関連されるレベルの前記ノードに記憶される前記アドレス部分の少なくとも１つを前記リクエストされたアドレスのそれぞれの対応するアドレスと比較し、その後前記決定ツリーに沿って下方項で前記次のレベルの前記ノードへ分岐する処理を実行するように構成されている請求項２３または２４記載のコンピュータシステム。
【請求項２６】
前記コンピュータシステムは通信システム、ネットワーク化ルーターおよびパケットスイッチングシステムから選択されたものである請求項２１乃至２５のいずれか１項記載のコンピュータシステム。
【請求項２７】
アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するための、請求項２１乃至２６のいずれか１項記載のコンピュータシステムによりロードされるコンピュータの読取り可能な媒体に記憶されているコンピュータプログラムにおいて、
前記アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は下限及び上限アドレスにより規定され、
前記アドレススペース中のアドレスは予め定められた数のビットにより表されており、
前記コンピュータシステムは、メモリ及びプロセッサを具備し、前記プロセッサは前記メモリに結合され、コンピュータプログラムプロダクトはロードされた後、前記プロセッサが以下のステップを実行することを可能にし、即ち、
−前記リクエストされたアドレスが属する前記基本アドレス域のセットから特定の基本アドレス域を決定するための前記決定ツリーを構成し、
前記決定ツリーは少なくとも１つのレベルを有し、前記少なくとも１つのレベルは少なくとも１つのノードを有し、
前記少なくとも１つのノードはノードアドレス域へマップするように構成されており、前記ノードアドレス域は前記アドレススペースのノード関連部分であり、前記ノードアドレス域は下限及び上限のノードアドレスにより規定され、
前記少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチは前記ノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
前記ブランチアドレス域は前記ノードアドレス域中のノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、前記分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定し、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、前記少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるか前記ノードアドレス域中の全てのアドレスで共通のアドレス部分であり、
−選択規則にしたがって、前記少なくとも１つのノード中に前記複数のアドレス部分を記憶するステップを含み、
前記選択規則は動作のグループからの少なくとも１つの動作を含み、前記動作は、
−前記ノードに一度だけ前記前記少なくとも１つの共通のアドレス部分を記憶し、
−前記少なくとも１つの省略可能なアドレス部分を省略し、
−前記分解ステップにおいて決定されたときの全ての他のアドレス部分を前記ノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は前記少なくとも１つの共通のアドレス部分または前記少なくとも１つの省略可能なアドレス部分ではない方法。
【請求項２８】
請求項２７記載のコンピュータプログラムに与えられているコンピュータの読取り可能な媒体。
【請求項２９】
決定ツリーを使用することにより、アドレススペース中でリクエストされたアドレスのアドレス検索のためのコンピュータシステムであって、前記決定ツリーは請求項１乃至６のいずれか１項記載の方法にしたがって構成されており、前記コンピュータシステムはメモリ及びプロセッサを具備し、前記プロセッサは前記メモリに結合され、
前記プロセッサは、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを実行するように構成され、前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
前記それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記リクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの前記次のレベルのノードへブランチするステップを行うように構成されているコンピュータシステム。
【請求項３０】
前記コンピュータシステムはさらに、
前記それぞれのノードに記憶された前記アドレス部分を読取った後、減算結果を得るために予め規定された定数値を前記リクエストされたアドレスから減算し、前記レベルの前記それぞれのノード中に記憶された少なくとも１つのアドレス部分を前記リクエストされたアドレスのそれぞれの対応するアドレス部分とを比較する前記ステップ前に、前記リクエストされたアドレスを前記減算結果により置換するステップを行うように構成されている請求項２９記載のコンピュータシステム。
【請求項３１】
前記コンピュータシステムは通信システム、ネットワーク化ルーター、パケットスイッチングシステムから選択されたものである請求項２９または３０記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は決定ツリーを使用することによりアドレススペース中のリクエストされたアドレスのアドレス検索のための方法に関する。また本発明は決定ツリーを使用することによりアドレススペース中のリクエストされたアドレスのアドレス検索のためのコンピュータシステムに関する。さらに本発明は決定ツリーを使用することによりアドレススペース中のリクエストされたアドレスのアドレス検索のためのコンピュータプログラムに関する。
【背景技術】
【０００２】
本発明は基本アドレス域のセットを表すデータ構造およびその構造を検索するための方法に関する。また本発明はアドレス検索のためのシステムに関する。
【０００３】
アドレス検索は幾つかのドメイン中、主にＩＰ（インターネットプロトコル）検索およびルーティング及びパケット分類中、さらにプロセッサ間通信中においてアプリケーションを発見する基本的機能である。
【０００４】
インターネットバックボーンはパケットの目的地アドレスを使用し、パケットの次のホップを決定するためにアドレス検索を実行する。各ルーターは検索表中に数十万のエントリを含んでいる可能性があり、毎秒数百万の検索を行うことが必要とされる。インターネットトラフィックの急速な成長とルーティング表のサイズの成長により、より高い処理速度の必要性の増加に追いつくことがより困難になっている。さらに、ＩＰｖ６  １２８ビットアドレスの使用はアドレス幅においてスケール可能な検索方法解決策を要求している。過去２年間に３００％増加され、ＩＰｖ４消耗と結び付けられているＩＰｖ６成長は、アドレス幅でスケール可能な解決策の必要性を引き起こしている。
【０００５】
パケット分類は多Ｇｂｐｓ性能と、検索のための多数のフィールドおよび恐らく少数の表エントリを有することを必要とする。
【０００６】
プロセッサ間通信のさらに小さいスケールでは、バーチャルから物理的アドレスへの漸進的な変換は非常に小さいルーティング表を必要とする可能性があるが、検索時間の制約は通信待ち時間がマルチコアシステムの性能について臨界的であるのでさらに厳しい。
【０００７】
ｋ＋１の可変サイズの基本アドレス域を規定するアドレススペース［０，２Ｗ）とｋの特有アドレス（アドレス境界）Ａｉを仮定し、ここで０＜Ａｉ＜２ｎ−１であり、ｉ＝１，２，．．．，ｋとすると、アドレス検索は入来するリクエストされたアドレスＡＩＮが属する基本アドレス域を決定する。
【０００８】
通常、アドレス検索を行うとき、解決される必要のある多くの挑戦的な問題が存在する。性能（即ち高速度の検索と高い処理能力）は恐らくこのようなアルゴリズムで主な目標である。多くの場合では（例えばＩＰ検索、パケット分類）、検索期間に必要とされるメモリサイズも重要であり、しばしば性能（メモリアクセス遅延）を決定する。さらに、メモリ帯域幅は限定され、その効率的な利用は直接性能に影響する可能性がある。ルーティング表が大きくなるほど、性能は複数のエントリ（即ち複数のアドレス域）で良好にスケールする必要があり、一方でＩＰｖ４からＩＰｖ６への移動はアドレス幅（Ｗ）における性能のスケールも必要であることを示している。したがって所定のエントリのセットについての検索表（即ちメモリ内容）の「構造」を生成するための時間と、増分的な更新のために表を適合するための時間も多くのアプリケーションで重要である。
【０００９】
多数のアルゴリズムが提案されているので、前述の挑戦の幾つかが残されている。
【００１０】
種々のアルゴリズムがアドレスの検索に提案されている。これらは、GuptaおよびMcKeownによる“Algorithms for packet classification”、IEEE Network、Vol.15、24−32頁、2001年3/4月と、パケット分類（多数のフィールドでの検索）に焦点を当てたTaylorによる“Survey and taxonomy of packet classification techniques”、ACM Comput. Surv.、vol.37、no.3、238−275頁、2005年、または種々の方法のアルゴリズムの側面をより重要視しているRuiz−Sanchez等のうちの１人による“Survey and taxonomy of IP address lookup algorithms”、IEEE Network、Vol.15、8−23頁、2001年3/4月のような幾つかの研究で要約されている。
【００１１】
アドレス検索の前記の提案されたアルゴリズムの完全なリストと解析は前記の研究で見られることができる。
【００１２】
図１は基本的なアドレス域のセットを含むアドレススペースを示している。アドレススペースは例えばＩＰ（インターネットプロトコル）アドレススペースに関することができる。基本アドレス域のセットはアドレス境界により規定するインターバル101として表されることができ、ここでアドレスの完全なビットパターンは検索を行うために比較されることができ、或いは接頭辞102として表されることができ、そこから最も長い一致するものが報告されるべきである（最長の接頭辞の一致）。インターバル及び接頭辞として表される８つのアドレス域のセットＲ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、Ｒ６、Ｒ７、Ｒ６’が０００００から１１１１１に及ぶ５ビットアドレススペース（Ｗ＝５）について図１に示されている。接頭辞０＊１０３は通常インターバル［０００００，１００００）を規定するが、これは実際にはその一部のみ、インターバル（及び基本アドレス域）［０００００，００１１０）104を規定することに注意する。これは残りのアドレス域［００１１０，１００００）について、基本アドレス域（００１１＊、０１００＊、０１０１＊、０１１＊）105、106、107を規定するさらに長い接頭辞が存在する。
【００１３】
Ruiz−Sanchez等はアドレスの検索が２次元、即ち長さと値におけるサーチを含んでいることを示している。これらは「長さにおけるサーチ」または「値におけるサーチ」のようなサーチが基づいている次元にしたがって既存の方法をカテゴリ化する。
【００１４】
「トライ」として知られている方法はトライが長さの次元において逐次的サーチを行い、長さｎのステップｎ接頭辞で一致するので「長さにおけるサーチ」または「値におけるサーチ」として考えられることができる。
【００１５】
基本トライ構造における改良は、逐次的の代わりに長さにおける二進サーチと、（一方向のブランチノードを崩壊する）パス圧縮と、固定されたまたは可変のストライドのマルチビットトライを含むことができる。アドレス検索のための最良の既知のトライベースの構造はEatherton、W.、Varghese G.、Dittia Z.の“Tree bitmap: hardware/software IP lookups with incremental updates”、SIGCOMM Comput.、Commun.、Rev.34、２（2004年４月）、97−122と、Eatherton、William N.、Dittia; Zubin D.の“Tree bitmap data structures and their use in performing lookup operations”、米国特許第7249149号明細書のツリービットマップを使用するものである。
【００１６】
図２はトライ構造の１例を示している。水平方向では、101の基本アドレス域Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、Ｒ６、Ｒ７が201で示されている。垂直方向では、決定ツリーのブランチが202−203で示されている。決定ツリーに沿ったコースは、ビットが‘０’でありビット比較のため‘０’203とラベルを付けられた矢印と、ビットが‘１’でありビット比較のため‘１’202とラベルを付けられた矢印により示されている。
【００１７】
結果的な決定ツリーは非常に不平衡にされる可能性があることが観察される。Ruiz−Sanchezにより示されているように、その改良（例えばツリービットマップ）としてアドレス幅においてスケールしないトライの高さを制御することは困難である。さらに、トライのメモリ要求は比較的高い。マルチビットトライは決定ツリーの高さにおいて改良するが拡張性はなく、これらは指数関数的にそれらのメモリ消費を増加する。
【００１８】
図３は「レンジツリー」として知られている従来技術の方法による典型的な「値によるサーチ」方法を示している。水平方向では、101の基本的なアドレス域Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、Ｒ６、Ｒ７、Ｒ６’は301として示されている。図３では、各レベルにおいて、フルアドレス（アドレス境界）302の１以上の値はノードに記憶される必要があり、入来するリクエストされたアドレスＡＩＮと比較される。各ブランチ上のラベルＬ303は「未満の値を有すること」を示し、ラベルＥは「等しい値を有すること」を示し、ラベルＧ614は「超える値を有すること」を示し、ラベルＧＥ304は「超える値か等しい値を有すること」を示している。
【００１９】
従来技術のレンジツリーは長さの次元が記憶されて拡張された接頭辞（フル／完全なアドレス境界）と比較されることを防止する。これらは平衡された決定ツリーを生成する各比較ステップにおいて１又は多数のアドレス比較を行う。これらは各段で比較される完全なアドレスを記憶し、それ故かなりのメモリサイズを消費する必要がある。
【００２０】
図４はフルアドレス（アドレス境界）において多数の同時的な比較を行うが、毎ステップで多数のアドレスを読取るというそれらの要求により利用可能なメモリ帯域幅に対する方法の数が限定され、アドレス幅に関するそれらの拡張可能性を減少する。
【００２１】
データのツリー構造をサーチするための最も近い既知の方法として従来技術のレンジツリー方法の背景を理解することは有用である。
【００２２】
ｋ＋１の基本アドレス域を規定するアドレススペース［０，２Ｗ）とｋの特有のアドレス境界Ａｉを仮定し、ここで０＜Ａｉ＜２ｎ−１であり、ｉ＝１，２，．．．，ｋとすると、アドレス検索は入来するアドレスＡＩＮが属する基本アドレス域を決定する。
【００２３】
基本アドレス域401、405はその下及び上の境界のアドレス（終点）によりまたは接頭辞により規定される。
【００２４】
従来技術のレンジツリーはサーチのために組織されたツリー構造である。
【００２５】
レンジツリーノード406、407、410、411はｋ個のアドレス境界（ノードアドレス）を記憶し、入来するアドレスとｋ個のアドレス境界402との間のｋ個の（１以上）比較を行うツリー構造の一部である。これらの比較はそれぞれがノード403、404、409に関連されるｋ＋１個の互いに素なアドレス域（ブランチアドレス域）を規定する。
【００２６】
ルートレンジツリーノード407は全体的なアドレススペースへマップする。
【００２７】
任意の他のノード406、410、411はそのペアレントブランチ（ペアレントブランチアドレス域）と関連付けされるノードアドレス域へマップする。
【００２８】
マルチウェイレンジツリーは２以上の比較を単一のノードで行うことができるレンジツリーである。
【００２９】
レンジツリー408のリーフノードは基本アドレス域へマップする。
【００３０】
通常、マルチウェイレンジツリーノードはアドレススペースのアドレス域へマップする。（１）単一のツリーレベルのノードと（２）先のツリーレベルのリーフノードとのアドレス域の集合は全体的なアドレススペースである。チルドレンノードアドレス域の集合はそれらのペアレントノードのアドレス域である。
【００３１】
アドレス域を規定する接頭辞は、ペアレントノードアドレス域が接頭辞に全体的に含まれないときに、ノードがマップするアドレスインターバルを全体的に含んでいる最長の接頭辞を各ノードで記憶することによりレンジツリーに記憶されることができる。さらに、更新の理由のために、データ構造に記憶された各アドレス境界（ノードアドレス）は範囲がこのアドレス境界内に入る複数の接頭辞も記憶する。
【００３２】
通常、トライの方法はアドレスの部分で正確な一致を行い、レンジツリーの従来技術の方法はフルアドレスの比較を実行する。
【００３３】
マルチウェイレンジツリーノード501の一般的視点が図５に示されている。ノードは、ノードが［Ｎａ，Ｎｂ）502−503へマップするアドレス域に入来するアドレスＡＩＮが属するとき検索される。マルチウェイレンジツリーのルートノードは全体的なアドレススペース［０，２Ｗ）へマップし、ここでＷはアドレス幅である、ノードはｋ＋１個のアドレス域Ｒ１，Ｒ２，．．．，Ｒｋ＋１520−523を規定するｋ個の特有のアドレス境界Ａ１，Ａ２，．．．，Ａｉ，．．．，Ａｋ（ノードアドレスとしても示される）を記憶する。Ａｉ∈［Ｎａ，Ｎｂ）、∀ｉ∈は自然数であり、ｉ≦ｋであり、それによってＲ１＝［Ｎａ，Ａ１）,   ,Ｒｉ＝［Ａｉ−１，ＡｉＲｋ−１）＝［Ａｋ，Ｎｂ）である。その後、入来するアドレスＡＩＮ∈［Ｎａ，Ｎｂ）はそれが属するアドレス境界Ｒｉを決定するためアドレスＡｉに対して比較される必要がある。
【００３４】
図４は基本アドレス域のセットを記憶するマルチウェイレンジツリーの１例を示している。ルートノード407は全体的なアドレススペース［０，１０００００）にマップし、２つのアドレス境界“０１０１０”と“１００００”402を記憶して入来するアドレスＡＩＮに対して比較する。ＡＩＮ＜０１０１０であるならば、最も左のチャイルドノード411へのブランチ403が後続されこれは［０００００，０１０１０）にマップし、０１０１０≦ＡＩＮ＜１００００であるならば、中間チャイルドノード410へのブランチ409が後続され、これは［０１０１０，１０００００）へマップし、ＡＩＮ≧１００００であるとき、ノード406への最も右のブランチ404が取られ、これは［１００００，１０００００）へマップする。前述の数は二進符号化にある。同様に、最も左のチャイルド411ノードはアドレス“００１１０”と“０１００００”を比較する。ＡＩＮ＜００１１０であるならば、最も左のインターバルＲ１408へのブランチが後続され、これは［０００００，００１１０）401へマップし、００１１０≦ＡＩＮ＜０１０００であるならば、インターバルＲ２へのブランチが後続され、［０１０１０，１００００）へマップし、ＡＩＮ≧１００００であるとき、Ｒ３へのブランチが後続され、これは［１００００，１０００００）へマップする。
【発明の概要】
【００３５】
本発明の目的はより効率的なアドレス検索を可能にする方法を提供することである。
【００３６】
この目的はアドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するための方法により実現され、
アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は上限及び下限アドレスにより規定され、
アドレススペース中のアドレスは予め定められた数のビットにより表されており、
前記方法は、
−リクエストされたアドレスが属する基本アドレス域のセットから特定の基本アドレス域を決定するための決定ツリーを構成し、その決定ツリーは少なくとも１つのレベルを具備し、少なくとも１つのレベルは少なくとも１つのノードを具備し、
少なくとも１つのノードはノードアドレス域へマップするために構成されており、ノードアドレス域はアドレススペースのノード関連部分であり、ノードアドレス域は下限及び上限のノードアドレスにより規定され、
少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチはノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
ブランチアドレス域はノードアドレス域中のノードアドレスにより規定されており、
−複数のアドレス部分中の各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定し、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるかノードアドレス域中の全てのアドレスで共通のアドレス部分であり、
−選択規則にしたがって、少なくとも１つのノード中に複数のアドレス部分を記憶するステップを含み、
選択規則は動作のグループからの少なくとも１つの動作を有し、その動作は、
−ノードに一度のみ少なくとも１つの共通のアドレス部分を記憶し、
−少なくとも１つの省略可能なアドレス部分を省略し、
−分解ステップにおいて決定されたときの全ての他のアドレス部分をノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は少なくとも１つの共通のアドレス部分または少なくとも１つの省略可能なアドレス部分ではない。
【００３７】
１実施形態では、方法は、
−リクエストされたアドレスを入力として受信し、
−リクエストされたアドレスが属する基本アドレス域を決定するステップを含んでおり、これは決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
それぞれのノードに記憶されたアドレス部分を読取り、
そのレベル中のそれぞれのノードに記憶された少なくとも１つのアドレス部分をリクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
少なくとも１つの比較に基づいて、決定ツリーのリーフノードの１つに到達するとき基本アドレス域が決定されるまで、決定ツリーの次のレベルのノードへブランチするステップを含んでいる。
【００３８】
本発明はさらに、アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するためのコンピュータシステムに関し、
アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は上限及び下限アドレスにより規定され、
アドレススペース中のアドレスは予め定められた数のビットにより表されており、
コンピュータシステムはメモリ及びプロセッサを具備し、そのプロセッサはメモリに結合され、ここでプロセッサはアドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するための方法を実行するように構成され、
−リクエストされたアドレスが属する基本アドレス域のセットから特定の基本アドレス域を決定するための決定ツリーを構成し、その決定ツリーは少なくとも１つのレベルを含み、少なくとも１つのレベルは少なくとも１つのノードを含み、
少なくとも１つのノードはノードアドレス域へマップするために構成されており、ノードアドレス域はアドレススペースのノード関連部分であり、ノードアドレス域は下限及び上限のノードアドレスにより規定され、
少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチはノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
ブランチアドレス域はノードアドレス域中のノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定し、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるかノードアドレス域中の全てのアドレスで共通のアドレス部分であり、
−選択規則にしたがって、少なくとも１つのノード中に複数のアドレス部分を記憶するステップを含み、
選択規則は動作のグループからの少なくとも１つの動作を有し、動作は、
−ノードに一度のみ少なくとも１つの共通のアドレス部分を記憶し、
−少なくとも１つの省略可能なアドレス部分を省略し、
−分解ステップにおいて決定されたときの全ての他のアドレス部分をノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は少なくとも１つの共通のアドレス部分または少なくとも１つの省略可能なアドレス部分ではない。
【００３９】
さらに本発明は、前述したようなコンピュータシステムによりロードされるコンピュータの読取り可能な媒体上のコンピュータプログラムであって、アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するためのコンピュータプログラムに関し、
アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は上限及び下限アドレスにより規定され、
アドレススペース中のアドレスは予め定められた数のビットにより表されており、
コンピュータシステムはメモリ及びプロセッサを具備し、プロセッサはメモリに結合され、ここでプコンピュータプログラムプロダクトがロードされた後、プロセッサが以下のステップを実行することを可能にし、即ち、
−リクエストされたアドレスが属する基本アドレス域のセットから特別な基本アドレス域を決定するための決定ツリーを構成し、決定ツリーは少なくとも１つのレベルを具備し、この少なくとも１つのレベルは少なくとも１つのノードを具備し、
この少なくとも１つのノードはノードアドレス域へマップするために構成されており、ノードアドレス域はアドレススペースのノード関連部分であり、ノードアドレス域は下限及び上限のノードアドレスにより規定され、
少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチはノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
ブランチアドレス域はノードアドレス域中のノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定するか、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるかノードアドレス域中の全てのアドレスで共通のアドレス部分であるかであり、
−選択規則にしたがって、少なくとも１つのノード中に複数のアドレス部分を記憶するステップを実行することを可能にし、
その選択規則は動作のグループからの少なくとも１つの動作を有し、動作は、
−ノードに一度のみ少なくとも１つの共通のアドレス部分を記憶し、
−少なくとも１つの省略可能なアドレス部分を省略し、
−分解ステップにおいて決定されたときの全ての他のアドレス部分をノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は少なくとも１つの共通のアドレス部分または少なくとも１つの省略可能なアドレス部分ではない。
【００４０】
さらに本発明は前述したような決定ツリーを使用することにより、アドレススペース中でリクエストされたアドレスのアドレス検索のためのコンピュータシステムに関し、決定ツリーは前述したような方法にしたがって構築され、コンピュータシステムはメモリ及びプロセッサを具備し、プロセッサはメモリに結合され、前記プロセッサは以下のステップを実行するように構成されている。即ち、
−リクエストされたアドレスを入力として受信し、
−リクエストされたアドレスが属する基本アドレス域を決定するステップを実行し、このステップは決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
それぞれのノードに記憶されたアドレス部分を読取り、
レベル中のそれぞれのノードに記憶された少なくとも１つのアドレス部分をリクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
少なくとも１つの比較に基づいて、リーフノードの１つに到達するとき基本アドレス域が決定されるまで、決定ツリーの次のレベルのノードへブランチするステップを実行する。
【００４１】
さらに別の実施形態が従属請求項により規定されている。
【００４２】
本発明を電気通信応用を特に参照して説明したが、本発明のデータ構造及びサーチ方法はアドレスインターバルまたはアドレス接頭辞の形態でアドレス域を規定する任意のデータベースを迅速にサーチすることを促す。方法及びシステムはコンピュータハードウェアでの実行に良好に適しており、アドレス幅および記憶されたアドレス域の数に対してスケール可能であり、コンパクトな記憶を行い、インターネットマルチサービスルーターの設計における切迫した問題に適用されることができる。
【００４３】
データ構造及びサーチ方法は特にデジタルコンピュータハードウェアでの構成に有益である。現在関心をもたれている主な応用はＩＰ検査、パケット分類、マルチサービスルーターで使用される半導体集積回路である。しかしながらその技術はデータが優先順位を付けられる必要があるか、またはデータの構造が決定されその後分類される必要がある場合を含む種々の応用で有用である。アドレス検索の結果として、データにおける動作はより迅速に及び効率的に取られることができる。
【図面の簡単な説明】
【００４４】
【図１】アドレススペース内のアドレス域の１例を示す概略図である。
【図２】従来技術からのトライ方法による決定ツリーを示す概略図である。
【図３】従来技術からのレンジツリー方法による決定ツリーを示す概略図である。
【図４】従来技術からのマルチウェイレンジツリー方法による決定ツリーを示す概略図である。
【図５】レンジツリーノードへマップするレンジトライノードを示す概略図である。
【図６ａ】本発明の方法による決定ツリーを示す概略図である。
【図６ｂ】本発明の方法による決定ツリーノードを示す概略図である。
【図６ｃ】本発明の方法による決定ツリーノードを示す概略図である。
【図７ａ】本発明によるレンジトライを示す図である。
【図７ｂ】追加のリーフノードとポインタによる注釈動作後のレンジトライを示す図である。
【図８】本発明によるメモリ階層中の注釈を付けられたレンジトライノードの構成を示す図である。
【図９】本発明によるメモリ階層に記憶されるレンジトライノードおよびそれぞれのノードデータ構造のグラフィカル表示図である。
【図１０】本発明による本発明の機能ユニットとそれらの相互接続を示すブロック図である。
【図１１ａ】本発明による単一の３２ビット比較器の組合せ論理のブロック図である。
【図１１ｂ】本発明による次のレンジオフセットユニットを実行する組合せ論理のブロック図である。
【図１２ａ】本発明による方法を実行するために構成されたさらに別のコンピュータシステムの機能ブロックを示す概略図である。
【図１２ｂ】本発明による方法を実行するためのパイプライン方法で構成されたさらに別のコンピュータシステムの機能ブロックを示す概略図である。
【図１３】本発明による方法を実行するために構成されたシステムのブロックを示す概略図である。
【発明を実施するための形態】
【００４５】
本発明の実施例を添付の概略図を参照にして例示として説明する。図面では対応する参照符合は対応する部分を示している。  
本発明による方法はリクエストされた入来アドレスＡＩＮを受信し、リクエストされた入来アドレスＡＩＮが属する基本アドレス域Ｒ１．．．Ｒ７を決定する。レンジトライノードの外部特徴が従来技術のレンジツリーノードの外部特徴と１対１で一致する。図５はレンジツリーノードへマップするレンジトライノードを概略的に示している。
【００４６】
したがって、図５はレンジトライノードと従来技術のレンジツリーとの両者の外部特徴を例示するために使用されることができる。外部特徴は、１）ノードの下限502及び上限503により決定され、ノードがマップするアドレス域と、２）ノードのブランチ530、531、532、533と、３）ブランチ531、533、530、532がそれぞれ指向するブランチアドレス域520、521、522、523と、（ノードアドレスとしても示される）複数のアドレス境界により決定されるアドレス域507、505、504、506、508と、ノード範囲（下限及び上限のノードアドレス）502、503である。
【００４７】
本発明による方法とレンジツリー方法との違いは、（１）異なるデータがノードに記憶され、（２）ノード情報及び入来するアドレスに基づいて、取られるブランチを決定するために異なる計算が必要とされることである。
【００４８】
決定ツリーの第１のレベルのノードから開始して、本発明によれば、リクエストされた入来アドレスはノードで処理される。リクエストされた入来アドレスとノードに記憶されたデータとノード計算とに基づいて、取られるノードブランチが決定される。これは決定ツリーのリーフノード、したがってリクエストされた入来アドレスが属するアドレス域に到達するまで反復される。
【００４９】
本発明による方法は以下の方法で従来技術のマルチウェイレンジツリー方法を改良する。
【００５０】
恐らくコンピュータの読取り可能な媒体の帯域幅により規定されるツリーノード毎に記憶されるデータの最大量を仮定すると、方法はノードに記憶されるアドレス境界の数を増加する。これはアドレス境界の部分を共有及び省略することにより、および随意選択的にはさらに圧縮技術を使用してノードに記憶されるアドレス境界を圧縮することによって特定の実施形態の詳細な説明においてさらに説明するように行われることができる。
【００５１】
したがって、この方法はノードに記憶されたアドレス境界、及びしたがってノードで利用可能なブランチの数を増加する。そうすることにおいて、決定ツリーのレベル数は決定ツリーに記憶される所定数の基本アドレス域について、およびノード当りの記憶される所定量のデータについて減少される。
【００５２】
その後、リクエストされた入来アドレスを仮定すると、ノードに対応するデータに基づいて、ノードは取られる正確なブランチを決定するために複数の計算を行う必要がある。その計算は、（１）オリジナルアドレス境界を検索するためノードに記憶されているデータの圧縮を解除し、その後リクエストされた入来アドレスとアドレス境界との比較を行い、または（２）以下説明するように、圧縮を解除せずにノードに記憶されたデータについて直接計算を行う。後者の実施形態はアドレス整列動作と、アドレスの部分の比較とを含んでいる。
【００５３】
我々は、ノードに記憶することを必要とするアドレス境界の数を、（１）アドレス境界の共通アドレス部分を共有し、（２）省略可能なアドレス部分を省略し、随意選択的に（３）さらに決定ツリーのノードに記憶されるデータを圧縮することにより減少させ、その後圧縮されたアドレス部分を読取り、リクエストされた入来アドレスＡＩＮとノードのデータとを入力として使用して計算を行うことを本発明による方法の一般的説明として考慮する。計算は特にノードに記憶されるアドレス部分の圧縮を解除し、アドレス境界のアドレス部分において比較を行うことを含むことができる。
【００５４】
以下、多くの代替設計または本発明のレンジトライ方法を使用する迅速なアドレス検索のうちの１つである実施形態を詳細に説明する。しかしながら簡潔性と速度の均衡はすぐれている。幾つかのさらに別の実施形態は明細書の最後に簡単に説明されており、ノードに記憶されたアドレス境界を圧縮及び解除し、その後リクエストされた入来アドレスとアドレス境界との比較を行うことを含んでいる。
【００５５】
本発明の方法の１つの特定の実施形態はさらに（１）同じノードで並列に比較される（ノードアドレス／アドレス境界の）共通のアドレス部分を共有し、（２）比較のために必要とされないアドレス境界の部分を省略し、（３）省略されるアドレス部分を増加するためにアドレス境界及びリクエストされた入来アドレスを整列するように構成されている。
【００５６】
アドレス域を規定するアドレス境界（ノードアドレス）はアドレススペースにおいて疎にまたは密に位置されることができ、さらに長いまたは短いアドレス域をそれぞれ生成する。直観的に、より少数のアドレスビットの比較はアドレススペースにおいて疎な領域に十分であり、密な領域はより良好な正確性を必要とするが、共有されることができる長い共通の接頭辞および接尾辞さえも有することができる。前述の説明は平衡された結果的な決定ツリーを維持し、共有してメモリ帯域幅の利用をさらに改良することができる。さらに、この方法はアドレス幅が増加しルーティング表のサイズが成長すると共に、性能に関して拡張を可能にする。
【００５７】
例示すると、図６ａは本発明の方法によるマルチウェイ決定ツリーを示している。この決定ツリーはツリーの複数のレベルにおいて複数のノード601、602、603、604を有している。高いレベルのノードは高いレベルよりも低いレベルの複数のノードにブランチすることができる。高いレベルのノードは高いレベルよりも低いレベルの（チルドレン）ノードのペアレントである。
【００５８】
マルチウェイ決定ツリーは幾つかのレベルでは二進であることができるが、ツリーの単一のレベルでは３以上のブランチを有することもできる。
【００５９】
再度述べるが、図１に規定されているような基本アドレス域がここで使用される。図６ａが示すように、本発明の方法はより少数のアドレスビットを比較しながら、決定ツリーでブランチ数を増加する。図６ａの例では、５ビットの利用可能なメモリ帯域幅は図３に示されている従来技術のレンジツリー方法の１つに等しいと想定される。
【００６０】
本発明の方法を示すため、第１の反復では、レベル１  607におけるルートノード601において、入来アドレスＡＩＮの２つの上位桁ビットが２つの上位桁ビット“０１−−−”605と上位桁ビット“１−−−”606であるルートノードに記憶されたアドレス境界の部分と比較される。下位桁アドレス境界ビットは省略される（“−”により示されている）。この比較はこれが従来技術のレンジツリー構造で行われたかのように、完全なアドレス境界“０１０００”と“１００００”とを比較することに等しい。
【００６１】
レベル２  608における第２の反復では、ルートノード601からの中間分岐610を取った後、通常はアドレス境界“０１０１０”と“０１１００”とを比較する。しかしながら、第１の反復後、入来アドレスは“０１ｘｘｘ”であるｘは規定されていないビット値であることが知られているので、２つの上位桁ビットを記憶し比較することは必要とされない。また比較されるアドレス境界の下位桁ビットはその値が“０”であるため省略される。
【００６２】
同様に、ルートレベルから右のブランチ615を取った後、上位桁ビットは“１ｘｘｘ”であることが知られている。その後、レベル２  608において、比較される２つのアドレス境界“１１１００”と“１１１０１”は共有されその後ノードで一度のみ記憶され別々に比較される共通の接頭辞ＡｉＣＰ（“−１１０−”）611を有する。そのノード602の決定は共通の接頭辞ＡｉＣＰ比較と、（必要ならば）‘−−−−１’613と同じノード602で示されている下位桁ビットの比較の結果に基づいている。
【００６３】
この例で示されているように、本発明の方法はより少ないメモリ帯域幅を使用する従来技術のレンジツリーの１つよりも深くない良好に平衡された決定ツリーを生じる。
【００６４】
アドレス境界当たりノードに記憶されるデータ量を減少させる２つの付加的な方法が以下の２つの例で示されている。即ち方法のアドレス整列特性と、方法の共通のアドレス接尾辞特性の共有である。
【００６５】
図６ｂは本発明によるレンジトライ方法を使用してアドレス域のセット620を表すレンジトライノード622の１例を示している。ノードはアドレス境界の共通の接尾辞を共有する１例を示している。このノードは共通の接尾辞“１０”の２つのビットを有する２つのアドレス境界“１００１０”625と“１１０１０”626を表している。ＡＩＮの最初の３つのビットはアドレス境界625、626の接頭辞の３つのビット“１００”と“１１０”に対して比較される。ＡＩＮの３ビット接頭辞とアドレス境界３ビット接頭辞との間に正確な一致が存在しないならば、一致するアドレス境界が識別される。アドレス境界の２つの接頭辞のうちの一方とＡＩＮの正確な一致が存在するならば、共通のアドレス境界の接尾辞623はＡＩＮの接尾辞と比較される。この例では、入来アドレスの最後の２つのビットは“１０”に対して比較される。基本アドレス域は共通の接尾辞比較の結果とその直前に生じた一致に基づいて識別される。上記の例における本発明の利点は共通の接尾辞の共有と、したがってその記憶と、その読取りと、それを一度しか比較しないことにある。
【００６６】
図６ｃは本発明のレンジトライ方法を使用してアドレス境界のセット630を表すレンジトライノード632の１例を示している。ノードはアドレス境界と入来アドレスＡＩＮを整列する１例を表している。ノードがマップするアドレス域の長さは低いノード範囲アドレス634を上位のノード範囲アドレス637から減算する結果、即ちＮＬ＝０１１１０−１００１１＝００１０１であり、これはこの例では３つのビットが２つの上位桁ビットがゼロであるとき二進“１０１”で表されることを必要とする。ノードアドレス域の長さを表すために必要とされるビットの数はこのノードの必要とされる計算で使用される接尾辞ビットの数を決定する。したがってこの例では、下位桁アドレスビット（３ビット）の同じ数が以下の計算のためにこのノードで有用である。第１に低いノードボーダー634の３つの下位桁ビット“−−１１０”はＡＩＮの３つの下位桁ビットから減算される。アドレスから省略された上位桁ビットは‘−’により示される。減算結果の３つの下位桁ビットは次の計算の結果の３つの下位桁ビットに対して比較される。即ち低いノード範囲634の３つの下位桁ビット“−−１１０”は各アドレス境界635、636の３つの下位桁ビット“−−１１１”と“−−０１０”から減算される。上記比較の結果は取られるノードブランチを決定する。オリジナルノードの境界は共通の接頭辞をもたないが、整列後、ノードの計算から省略された２ビットの共通の接頭辞が存在することに注意すべきである。したがって、（１）ＡＩＮ、（２）低いビット境界634、（３）アドレス境界635、636の３つの下位桁ビットだけにおいて記憶及び計算を行う必要がある。
【００６７】
一般的に、本発明によるレンジトライノードとブランチは（従来技術の）レンジツリーデータ構造に１対１でマップされることができる。従来技術のレンジツリーでのように、レンジトライノードはアドレススペースのアドレス域へマップする。
【００６８】
（１）単一のツリーレベルにおけるノードと（２）先のツリーレベルのリーフノードのアドレス域の集合は全体的なアドレススペースである。チルドレンノードアドレス域の集合はそれらのペアレントノードのアドレス域である。
【００６９】
入来するアドレスＡＩＮがＡｋ−１≦ＡＩＮ≦Ａｋであるときブランチアドレス域［Ａｋ−１，Ａｋ）へ指向するノードブランチが取られる。しかしながら本発明によるレンジトライノードに記憶されているデータはレンジツリーノードよりも非常に少なく、チャイルドブランチが後続される入来アドレスに基づいて決定される必要のある計算も異なる。また、接頭辞は従来技術のレンジツリーに記憶される方法と同じ方法で本発明のデータ構造に記憶されることができる。
【００７０】
レンジトライノードは特別な実施形態にしたがって（１）２以上のアドレス境界の単一の共通のアドレス部分と、（２）比較に必要とされないビットの任意のサブセット（省略可能なアドレス部分）を省略した後の各アドレス境界の残りの部分とからなるように構成されることができるアドレス境界の部分からなり、このビットのサブセットはノードアドレス域で共通であるビットであってもよく、また値”０”を有するアドレス境界接尾辞であってもよい。
【００７１】
したがって図５、６ａ−６ｃによれば、本発明はアドレススペース中のリクエストされたアドレスのアドレス検索に使用するための決定ツリーを構築する方法を提供し、
アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は上限及び下限アドレスにより規定され、
アドレススペース中のアドレスは予め定められた数のビットにより表されており、
方法は、
−リクエストされたアドレスが属する基本アドレス域のセットから特定の基本アドレス域を決定するための決定ツリーを構成し、
決定ツリーは少なくとも１つのレベルを有し、その少なくとも１つのレベルは少なくとも１つのノードを有し、
少なくとも１つのノードはノードアドレス域へマップするために構成されており、ノードアドレス域はアドレススペースのノード関連部分であり、ノードアドレス域は下限及び上限のノードアドレスにより規定され、
少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチはノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
ブランチアドレス域はノードアドレス域中のノードアドレスにより規定され、
−複数のアドレス部分中の各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、
分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定し、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるかノードアドレス域中の全てのアドレスで共通のアドレス部分であり、
−選択規則にしたがって、少なくとも１つのノード中に複数のアドレス部分を記憶するステップを含み、
選択規則は動作のグループからの少なくとも１つの動作を有し、その動作は、
−ノードに一度だけ少なくとも１つの共通のアドレス部分を記憶し、
−少なくとも１つの省略可能なアドレス部分を省略し、
−分解ステップにおいて決定されたときの全ての他のアドレス部分をノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は少なくとも１つの共通のアドレス部分または少なくとも１つの省略可能なアドレス部分ではない。
【００７２】
予め定められたアドレススペース中にアドレスを有する入来アドレスＡＩＮが読取られる。次に、入来アドレスＡＩＮはアドレススペース域に対応するビット数により規定される。
【００７３】
アドレススペース内で、基本アドレス域Ｒ１，．．．，Ｒ７を規定する複数のアドレス境界が存在する。各基本アドレス域Ｒ１，．．．，Ｒ７はそれ自体は複数の個々のアドレスを有するサブアドレススペースである。
【００７４】
アドレス境界の数に基づいて、入来アドレスＡＩＮが位置される基本アドレス域を決定するために使用される決定ツリーが構築される。
【００７５】
アドレススペース内の入来アドレスの位置を決定するために、方法は、ビットのサブセットの値または全体的なリクエストされた入来アドレスのビットのサブセットの１以上の値または全体的なアドレス境界に対する１以上の比較を複数反復して行うように構成されている。ビットのサブセットのサイズは反復間で変化することができる。決定ツリーは反復の終了後、入来アドレスが属する基本アドレス域が決定される方法でブランチされる。以下、決定ツリーの構造をさらに詳細に説明する。
【００７６】
１実施形態では、本発明は前述の方法を提供し、この方法はさらに、
−リクエストされたアドレスを入力として受信し、
−リクエストされたアドレスが属する基本アドレス域を決定するステップを含んでおり、これは決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
それぞれのノードに記憶されたアドレス部分を読取り、
レベル中のそれぞれのノードに記憶された少なくとも１つのアドレス部分をリクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
少なくとも１つの比較に基づいて、リーフノードの１つに到達するとき基本アドレス域が決定されるまで、決定ツリーの次のレベルのノードへブランチするステップを含んでいる。
【００７７】
次に、本発明の方法によりノードに記憶され、読取られ、処理される必要のあるアドレス境界ビットの数を減少させるための１つの特別な実施形態について説明する。決定ツリーのノードにおいて、複数のアドレス境界に対して共通のビットは比較されるビットのサブセットとして共通のアドレス部分で組み合わせられることができる。これらのビットはノードに一度だけ記憶される必要があり、これらのビットの１度の比較しか２以上のアドレス境界で必要とされない。さらに、ノードがマップするアドレス域の全てのアドレスで共通のビットは比較から省略されることができる。また値ゼロを有するアドレス境界接尾辞ビットも比較から省略されることができる。最後にアドレス境界及びリクエストされた入来アドレスはノードに記憶される必要のある情報を最小にするように適切に整列されることができる。
【００７８】
この方法は実施形態によれば以下の特性を有する決定ツリーを適用する。即ち、
−ノードはアドレススペースのアドレス域へマップする。（１）単一のツリーレベルのノードと（２）先のツリーレベルのリーフノードのアドレス域の集合は全体的なアドレススペースである。チルドレンノードアドレス域の集合はそれらのペアレントノードのアドレス域である。  
−ノードで処理される必要のある比較当たりのアドレスビット（または決定ツリーのノードブランチ）の最大数はｌｏｇ２Ｄであり、ここでＤはノードがマップするアドレス域の長さである。  
−アドレス接尾辞はそれらの値がゼロであるとき処理から省略されることができる。幾つかのケースでは、記憶される必要のあるデータを減少させるためにアドレス境界に値ゼロの接尾辞をもたせることができ、その後新しいアドレス境界が生成されるが、これは決定ツリーに記憶されるアドレス域のオリジナルセットを規定するアドレス境界のオリジナルセットには含まれない。  
−共通のアドレス部分はアドレス境界（ノードアドレス）間で共有される。  
−アドレスはそれらの共有された共通の接頭辞を最大にするために適切に整列されることができる。
【００７９】
これらの特性に対応して、この実施形態による方法は幾つかのデータ処理規則を提供する。これらの規則は決定ツリーの深さを限定するため特別なメモリ帯域幅を仮定して、ノード当りのブランチ数の増加を意図する。
【００８０】
図５のノード501について考慮する。レンジトライノードの外部特徴がレンジツリーノードの外部特徴と１対１で一致しているとき、図５はレンジトライノードを例示するために使用されることができる。
【００８１】
第１の規則（規則１）はノード境界502、503の共通の接頭辞を省略する。アドレスＮａ502とアドレスＮｂ503においてノード境界の長さＬの共通の接頭辞ＣＰが存在するとき（Ｌ＜Ｗ、Ｗはアドレス幅）、アドレス（入来アドレス及びアドレス境界）のＬ個の上位桁ビットはノードにおける比較から省略されることができる。
【００８２】
第２の規則（規則２）はノードがマップするアドレス域内のアドレス境界Ａｉ504の共通の接頭辞（上位桁ビット）ＡＣＰを共有する。長さＬ（Ｌ＜Ｗ）の複数のアドレス境界Ａｉの共通の接頭辞ＡＣＰは多数の比較において共有されることができ、一度だけ記憶されて別々に処理されることができる。その後長さＬのＡＩＮ接頭辞がＡＣＰよりも小さいならば、ＡＩＮ∈Ｒ１である（即ちＡＩＮはＲ１に属する）。長さＬのＡＩＮ接頭辞がＡＣＰよりも大きいならば、ＡＩＮ∈Ｒｋ＋１である。長さＬのＡＩＮ接頭辞がＡＣＰに等しいならば、ＡＩＮの（Ｗ−Ｌ）ビット接尾辞（下位桁ビット）とアドレス境界Ａｉ504の（Ｗ−１）ビット接尾辞との比較はＡＩＮが属する場所を決定する。
【００８３】
第３の規則（規則３）は値‘０’のアドレス境界接尾辞を省略する。アドレス境界Ａｉ504に長さＬの接尾辞を有し、ここでＬ＜Ｗであり、即ちゼロである。その後、Ａｉ504のこの接尾辞はＡＩＮのＬ個の下位桁ビットに対して比較される必要はない。ＡＩＮの（Ｗ−Ｌ）ビット接頭辞（上位桁ビット）とアドレス境界Ａｉ504の（Ｗ−１）ビット接頭辞との比較はＡＩＮが属する場所を決定する。
【００８４】
第４の規則（規則４）はノードがマップするアドレス域内のアドレス境界Ａｉ504の共通の接尾辞（下位桁ビット）ＡＣＳを共有する。複数のアドレスＡｉの共通の接尾辞ＡＣＳは多数の比較間で共有され別々に処理されることができる。
【００８５】
Ｒｐ＝［Ａｐ−１，Ａｐ）、（ｐ∈自然数、１≦ｐ≦ｋ＋１）がＡｉとＡＩｎの（Ｗ−Ｌ）ビット接頭辞比較が示すアドレス域とする。以下の全ての３つの条件が正しいとき、ＡＩＮ∈Ｒｐ−１＝［Ａｐ−２，Ａｐ−１）である。  
（１）長さＬのＡＩＮ接尾辞がＡＣＳよりも小さい。  
（２）長さＷ−ＬのＡＩＮ接頭辞がＡｐ−１の接頭辞に等しい。  
（３）Ｒｐ≠Ｒ１
上述の３つの条件の１以上が満たされるならば、ＡＩＮ∈Ｒｐである。
【００８６】
第５の規則（規則５）はアドレス整列を使用する。アドレス境界Ａｉ504を有する［Ｎａ，Ｎｂ）をマップするノードＮ中のアドレスＡＩＮの検索は、アドレス境界Ａ’ｉ＝（Ａｉ−Ｎａ）を有するアドレス域［０，Ｎｂ−Ｎａ）にマップするノードＮ’中のアドレスＡ’ＩＮ＝（ＡＩＮ−Ｎａ）の検索に等しい。その後、Ａ’ＩＮがノードＮ’のアドレス域Ｒｉ＝［Ａ’ｉ−１，Ａ’ｉ）に属するとき、ＡＩＮはオリジナルノードのアドレス域Ｒｉ＝［Ａｉ−１，Ａｉ）に属する。
【００８７】
第５の規則は第１の規則の利点を最大にし、本質的には本発明の方法の基本特性を実現する。即ちノードが処理するために必要なアドレスビットの最大数はノード領域の長さを表すことを必要とされるビット数に等しく、即ちｌｏｇ２（Ｎｂ−Ｎａ）である。
【００８８】
前述の規則のうちの２以上を平行して適用することに関して問題が生じる。規則１乃至４はこれらが相互に影響しないとき独立して適用されることができる。例えば共通のノード接頭辞を使用することを省略でき（規則１）、任意のゼロの接尾辞を省略でき（規則３）、これらはアドレスの共通の接頭辞（規則２）の共有と、残りのアドレスビットの接尾辞（規則４）の共有を適用できる。
【００８９】
しかしながら第５の規則は規則１乃至４のうちの１以上と組み合わせて適用することがより困難である。第５の規則は共通のノード接頭辞を最大にすることを目的としており、したがってこれは第１の規則と組み合わせられることができるが、アドレス接頭辞が減算後に変化するので第２の規則の前に適用される必要がある。ゼロ及び共通のアドレス接尾辞に関しては、第５の規則は独立して適用されることができる。オリジナルアドレス値を使用してゼロと（長さＬの）共通のアドレス接尾辞をそれぞれ省略し共有し、したがって残りのＷ−Ｌアドレスビットで減算することが好ましい。Ｎａ502を減算する代わりに、残りはゼロであることを仮定するとＮａ502のＷ−Ｌの上位桁ビットが減算されることができるので、これは実現可能である。そうすることにおいて、アドレス整列が適用されるときでさえも接尾辞を共有する利点が維持され、さらに減算において関係する必要とされるアドレスビットは接頭辞の比較で必要とされるもののみに減少される。
【００９０】
前述の規則はノードに記憶されたアドレス境界の必要とされる部分とそれらのそれぞれの比較を減少することを考慮していることに注意すべきである。同じ規則がアドレス部分の部分とそれらのそれぞれの比較に適用されることができる。
【００９１】
最後に、規則２と規則４は２以上のノードアドレスの任意の共通のアドレス部分を共有するように拡張されることができる。
【００９２】
［システム］  
図１３は本発明による方法を実行するために構成されたシステム1300のブロック図を概略的に示している。システムはメモリ1301（例えばオンチップメモリＳＲＡＭ）と、それぞれが単一のツリーレベルの処理を実行するレンジトライ処理ユニット1302-1306と、随意選択的にメモリが全てのレンジトライノードを記憶するのに十分ではないならば最後のレンジトライレベルのノードを記憶するための外部メモリ1307（例えばＤＲＡＭ）（示されている例では第５のレベルのノードが外部で記憶されている）とを具備している。
【００９３】
各レンジトライ処理ユニット1302-1306の内部を以下詳細に説明し、図面１２ａ、１２ｂとさらに１例では図１０に示されているようなハードウェア構成が示されている。
【００９４】
入来アドレスＡＩＮはシステムの応用にしたがって、ネットワークのＩ／Ｏ装置を通してネットワークから入来するパケットのパケットヘッダより抽出された１または多数のパケットフィールドであることができる。入来アドレスＡＩＮはレンジトライ処理ユニット1302の第１のレベルに入り、これは第１のレンジトライレベルが単一のルートノードを具備するのでメモリを読取る必要はなく、1302でレジスタに記憶されることができる。レンジトライ処理レベル２  1303、３  1304、４  1305、５  1306は、先のレンジトライレベル処理ユニットにより決定されたレンジトライノードのデータをメモリ（ＳＰＲＡＭ1301またはＤＲＡＭ1307）から読取った後、1302と同じ計算を行う。前述の規則にしたがってまたはこれらの規則に加えて別の圧縮技術を使用することによりアドレス境界を圧縮形態で記憶する。最後のレンジトライ処理ユニット（レベル５）後に、各基本アドレス域の動作または一致する接頭辞を記憶する結果アレイ804はメモリユニットから読取られる必要がある。所定の入来アドレスについての一致する基本アドレス域および／または基本アドレス域に関連する動作はシステムの出力である。
【００９５】
システム1300はレンジトライ処理ユニットのシーケンスまたはメモリユニット1301、1307で読取りおよび書込むプロセッサとして示されているが、これは当業者に知られているように並列にユニット機能を処理する幾つかのシーケンスを具備することができまたは相互から遠隔的に位置されることができる１つのメインプロセッサにより制御されてもよい。
【００９６】
本発明の方法を実行するためのコンピュータ構成の例は（バックボーン）ネットワークルーター、パケットスイッチングシステム、マルチサービスインターネットルーター、マルチフィールドパケット分類システム、ゲートウェイ、サーバが提供するネットワークサービス（マルチキャスト、トンネル、仮想私設ネットワーク、サービス品質サポートをサポートする）、ネットワークセキュリティシステムである。
【００９７】
レンジトライ処理ユニット1302-1306は以下さらに詳細に説明するようにそれらのそれぞれの機能を実行するためのハードウェアまたはソフトウェアコンポーネントにおける機能を具備する。当業者は本発明の機能がハードウェアとソフトウェアコンポーネントの組合せにより実現されることができることを認識するであろう。当業者により知られているように、ハードウェアデジタルコンポーネントはレンジトライ処理ユニット1302、1303、1304、1305、1306内に存在することができ、或いはレンジトライ処理ユニット1302、1303、1304、1305、1306とインターフェースする別の回路として存在することができる。さらにソフトウェアコンポーネントが1302、1303、1304、1305、1306のメモリ領域またはメモリユニット1301、1307に存在できることが当業者により認識されよう。
【００９８】
図１３に示されているコンピュータシステム1300は本発明の方法による計算を行うように構成されている。コンピュータシステム1300は、コンピュータシステムにロードされた後にコンピュータシステムが本発明の方法を実行することを可能にするコンピュータの読取り可能な媒体上に存在する構造（またはプログラムコード）にしたがって計算を行うことができる。本発明は前述したような方法を記述するマシン読取り可能な指令の１以上のシーケンスを含んだコンピュータプログラム、またはそこに記憶されているこのようなコンピュータプログラムを有するデータ記憶媒体（例えば半導体メモリ）の形態を取ることができる。
【００９９】
したがって、本発明はアドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するためのコンピュータシステムを提供し、
アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は上限及び下限アドレスにより規定され、
アドレススペース中のアドレスは予め定められた数のビットにより表されており、
コンピュータシステムはメモリ及びプロセッサを具備し、プロセッサはメモリに結合され、ここでプロセッサはアドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するための方法を実行するように構成され、
−リクエストされたアドレスが属する基本アドレス域のセットから特定の基本アドレス域を決定するための決定ツリーを構成し、
決定ツリーは少なくとも１つのレベルを有し、少なくとも１つのレベルは少なくとも１つのノードを有し、
少なくとも１つのノードはノードアドレス域へマップするために構成されており、ノードアドレス域はアドレススペースのノード関連部分であり、ノードアドレス域は下限及び上限のノードアドレスにより規定され、
少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチはノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
ブランチアドレス域はノードアドレス域中のノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定し、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるかノードアドレス域中の全てのアドレスで共通のアドレス部分であり、
−選択規則にしたがって、少なくとも１つのノード中に複数のアドレス部分を記憶するステップを含み、
選択規則は動作のグループからの少なくとも１つの動作を有し、その動作は、
−ノードに一度だけ少なくとも１つの共通のアドレス部分を記憶し、
−少なくとも１つの省略可能なアドレス部分を省略し、
−分解ステップにおいて決定されたときの全ての他のアドレス部分をノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は少なくとも１つの共通のアドレス部分または少なくとも１つの省略可能なアドレス部分ではない。
【０１００】
レンジトライ処理ユニット1302-1306（又はプロセッサ）はさらに本発明の方法を実行するように構成され、
リクエストされたアドレスを入力として受信し、
−リクエストされたアドレスが属する基本アドレス域を決定するステップを実行し、このステップは決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
それぞれのノードに記憶されたアドレス部分を読取り、
レベル中のそれぞれのノードに記憶された少なくとも１つのアドレス部分をリクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
少なくとも１つの比較に基づいて、リーフノードの１つに到達するとき基本アドレス域が決定されるまで、決定ツリーの次のレベルのノードへブランチするステップを含んでいる。
【０１０１】
さらに本発明は、アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するための、前述したようなコンピュータシステムによりロードされるコンピュータの読取り可能な媒体上のコンピュータプログラムを提供し、
アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は上限及び下限アドレスにより規定され、
アドレススペース中のアドレスは予め定められた数のビットにより表されており、
コンピュータシステムはメモリ及びプロセッサを具備し、プロセッサはメモリに結合され、ここでプコンピュータプログラムプロダクトがロードされた後、プロセッサが以下のステップを実行することを可能にし、即ち、
−リクエストされたアドレスが属する基本アドレス域のセットから特定の基本アドレス域を決定するための決定ツリーを構成し、
決定ツリーは少なくとも１つのレベルを有し、少なくとも１つのレベルは少なくとも１つのノードを有し、
少なくとも１つのノードはノードアドレス域へマップするために構成されており、ノードアドレス域はアドレススペースのノード関連部分であり、ノードアドレス域は下限及び上限のノードアドレスにより規定され、
少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチはノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、
ブランチアドレス域はノードアドレス域中のノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、
分解は、次のａ）とｂ）の少なくとも一方を含み、
ａ）少なくとも１つの共通のアドレス部分として多数のノードアドレスに共通の少なくとも１つのアドレス部分を決定し、
ｂ）少なくとも１つの省略可能なアドレス部分として省略可能である少なくとも１つのさらに別のアドレス部分を決定し、少なくとも１つの省略可能なアドレス部分は値「ゼロ」のノードアドレス接尾辞であるかノードアドレス域中の全てのアドレスで共通のアドレス部分であり、
−選択規則にしたがって、少なくとも１つのノード中に複数のアドレス部分を記憶するステップを実行することを可能にし、
選択規則は動作のグループからの少なくとも１つの動作を有し、その動作は、
−ノードに一度のみ少なくとも１つの共通のアドレス部分を記憶し、
−少なくとも１つの省略可能なアドレス部分を省略し、
−分解ステップにおいて決定されたときの全ての他のアドレス部分をノードに記憶するステップを含んでおり、前記全ての他のアドレス部分は少なくとも１つの共通のアドレス部分または少なくとも１つの省略可能なアドレス部分ではない。
【０１０２】
さらに、本発明は前述したようにコンピュータプログラムが設けられているコンピュータの読取り可能な媒体を提供する。
【０１０３】
その方法によれば、レンジトライ処理ユニット1302、1303、1304、1305、1306は本発明の方法によりアドレス検索を行うために入来アドレスＡＩＮを受信する。入来アドレスはネットワークのＩ／Ｏ装置を通してネットワークから入来するパケットのパケットヘッダから抽出される。入来アドレスＡＩＮはパケットの目的地アドレスを含むが、さらにまたは代わりにソースアドレス、ソースポート、目的地ポートおよび／またはプロトコルを具備できる。入来アドレスＡＩＮはビットの予め定められた数のアドレス域をカバーするアドレススペース内のアドレスである。
【０１０４】
レンジトライ処理ユニット1302、1303、1304、1305、1306は、入来アドレスのビットの予め定められた数からビットのサブセットを複数反復して選択する。次に、各反復において、レンジトライ処理ユニット1302、1303、1304、1305、1306はビットの予め定められた数のサブセットの値をアドレススペースからのビットのサブセットの値と比較する。
【０１０５】
さらに、レンジトライ処理ユニット1302、1303、1304、1305、1306は前述したように第１、第２、第３、第４、第５の規則の１以上にしたがって規定されたアルゴリズムを実行するように構成されることができる。
【０１０６】
図１２ａは本発明による方法を実行するように構成されたさらに別のコンピュータシステム1200の機能ブロック図を概略的に示している。
【０１０７】
状況下で、アドレスをシフトし、比較されるそれらの部分を選択し、一致する領域を選択するために多ビット操作指令が必要とされる場合、本発明の方法をソフトウェアではなくハードウェアで実行することがより効率的である。他方で、ソフトウェア構成は方法がメモリアクセス数を減少し、メモリアクセス数の減少は明白に性能を改良するので、本発明の方法から利点を得ることもできる。
【０１０８】
さらにコンピュータシステム1200はメモリ1201、アドレスの一部のアドレス整列及び選択装置1202、1213と、比較器1203、1212と、共通の接頭辞アドレス整列及び選択装置1210、共通の接頭辞比較器1208と、共通の接尾辞アドレス整列及び選択装置1211と、共通の接尾辞比較器1209と、アドレス1204の部分の個々の比較に基づいて結果を出力する符号化装置と、必要ならば共通の接頭辞比較結果1205にしたがって符号化装置の結果を変更するモジュールと、必要ならば共通の接尾辞比較結果にしたがってモジュール1205の結果を変更するモジュール1206と、メモリ1201から読み出すための次のアドレスを計算するモジュール1207とを具備している。
【０１０９】
一般的に言えば、入来アドレスＡＩＮは1202、1213で適切に整列され、その一部は並列比較器1203、1212に与えられる。比較器1203、1212は異なる構造で変化できる可変の長さ、例えば８、１６または３２の比較を行うように構成されることができる。利用可能なメモリ帯域幅と行われる比較の長さは利用可能な比較の総数を決定し、例えば多数の８ビットおよび１６ビット比較として構成されることができる２５６ビットメモリ帯域幅と３２ビットの比較器であり、７個の３２ビット比較器1203、1212を有することができ、残りの３２ビットは共通の接頭辞1208と接尾辞1209のためのものである。各比較器の第２の入力はメモリ1201から読取られ、ヒューリスティックな所定のアドレス域のセットにより発生される単一の反復の１以上の決定ツリー境界（ツリーノード）を含む。ヒューリスティックの例を以下さらに詳細に説明する。２つの他の比較器1208、1209は並列に共通のアドレス接頭辞と接尾辞を比較する。それに続いて個々の比較器の結果は1204で符号化される。共通の接頭辞出力は規則２にしたがって1205で考慮される。その後、共通の接尾辞比較は規則４にしたがって1206で考慮される。前述の説明は図１２ｂに示されているようにパイプライン方法で実行されることもでき、それによって各反復は別々のメモリブロックを有する別々の段で実行される。そうすることにおいて、全体的な処理能力は追加的なハードウェアを犠牲にして改良されることができる。代わりにパイプライン段は二倍にされて、サイクル時間を改良するため異なる段において比較及びメモリアクセスを有することもできる。
【０１１０】
以下、本発明の特徴によるレンジトライデータ構造と、ノード記述及びハードウェア実行のより詳細な説明および例を示す。
【０１１１】
本発明は入来アドレスが属するアドレススペース中の基本アドレス域を識別するための迅速なサーチを行う。
【０１１２】
図７ａは本発明によるレンジトライの図を示し、図７ｂは追加的なリーフノードとポインタを有する注釈動作後のレンジトライの図を示している。
【０１１３】
最初に、図７ａに示されているようなレンジトライ700は（ａ）結果アレイ710へのポインタ760、761、762、764、765を保持する追加的なリーフノード730-734と、（ｂ）各非ルーと非リーフノードの最も右のチャイルドへのポインタ750、751と、（ｃ）リーフノードから結果アレイ710へのポインタ763、766、767の注釈を付けられている。
【０１１４】
注釈動作は図７ｂに示されているように注釈を付けられたレンジトライ700’を与える。
【０１１５】
例示により、オリジナルレンジトライ700はノードの３レベルを有する。
【０１１６】
追加的なリーフノードはレベル３よりも下では付加されないので、注釈を付けられたレンジトライ700’も３レベルのノードを有する。オリジナルレンジトライ700の非レベル３ノード701-703が結果アレイ710中のアドレス域Ｒｉを直接指向する場合、各追加的なリーフノード730-734は注釈を付けられたレンジトライ700’へ付加される。
【０１１７】
追加的なリーフノードはそれを指向するレンジトライノードの次のレベルに置かれ、結果アレイ中のアドレス域Ｒｉへのポインタを保持する。（即ち、ルートノード701はノード702、703へのペアレントであり、結果アレイ710のＲ３へ直接指向する。このことによりチルドレンノード721、722の間のルートノード720のチャイルドノードとして注釈を付けられたレンジトライ700’のレベル２に置かれる追加的なリーフノード732が生成される。
【０１１８】
追加なリーフノード732は結果アレイ710中のアドレス域Ｒ３への結果アレイポインタ762を保持する。類似の方法で、レンジトライ700’は追加的なリーフノード730、731、733、734の注釈が付けられる。）
レンジトライ700’の注釈付けは最も右のチャイルドへのポインタ750、751を使用して、非ルート非リーフノード721、722をそれらの最も右のチャイルドノード731、725と連結することにより継続する。
【０１１９】
レンジトライ700’の注釈付けは、レンジトライ700の各ノード704-706が結果アレイへのポインタ763、766、767を使用することにより指向している結果アレイ710中の最も右の結果とリーフノード723-725を連結することにより終了される。
【０１２０】
次に本発明によれば、３レベルの注釈を付けられたレンジトライ700’の各ノードは図８に示されている４レベルのメモリ階級のエントリに位置される。
【０１２１】
図８は本発明によるメモリ階級中の注釈を付けられたレンジトライノードの構成を示す図である。
【０１２２】
図８はさらにメモリ階級へのノードの組織およびレンジトライ700’に注釈を付けるポインタの意味も示している。
【０１２３】
メモリレベル１  801の単一のエントリ810は注釈を付けられたレンジトライ700’のルートノード720により満たされている。メモリレベル２  802とメモリレベル３  803は注釈を付けられたレンジトライ700’のレベル２およびレベル３のノードにより満たされている。メモリレベルｉのそれぞれの連続的なメモリエントリは注釈を付けられたレンジトライ700’のレベルｉの最も右のノードから開始して最も左のノード方向へ移動するノードにより満たされる。メモリレベル２  802は700’のレベル２からのノード、即ちエントリ０  811のノード722、エントリ１  812の追加的なリーフノード723、ノード２  813のノード721でセットアップされる。同じ方法で、メモリレベル３  803が満たされる。結果アレイ710は第４のメモリレベル804に存在し、ここでは結果アレイ710の最も右のレンジから開始し最も左のレンジ方向へ移動するように位置される。入来アドレスが属するレンジを識別するためのサーチが終了した後、結果アレイ804中のそれぞれのレンジのエントリは取られる動作832を決定するために得られる。即ちパケット分類およびＩＰ検索の場合、結果の模索はしばしば次のホップアドレスであるが、パケットの処理またはパケットヘッダの幾つかの変更であることができる。
【０１２４】
注釈を付けられたレンジトライ700’のノードをメモリレベル１−３  801-803に位置付ける前に、これらは最初に図９に表されているノードデータ構造901へ符号化されなければならない。
【０１２５】
図９はノードデータ構造901へのレンジトライノード900の例示的な表示を示している。レンジトライノード900中の情報はサーチ期間中にレンジトライノード900を横切って通過するときに行われる計算についての全ての必要な詳細を保持する。
【０１２６】
例によると、入来アドレス幅と利用可能な比較器の幅は３２ビットであると仮定される。利用可能なメモリ帯域幅は１２８であると仮定される。したがって４つの利用可能な比較器が存在する。ノードデータ構造901中の比較器１−３  931-933の比較値（アドレス部分）はノード900の比較器１−３  910-912の単一の比較値918で埋められる。比較器３  912の比較値は全体で３２ビット幅よりも小さく、したがって比較器３  933の比較値の残りのビットは０に設定される。比較値930の３２の下位桁ビット934は接頭辞／接尾辞比較値914-915または（有効ならば）比較器４  913の比較値を保持する。
【０１２７】
比較器１−４  910-913の動作モード（即ちディスエーブルされた［８８８８］、［８，８，１６］、［１６，０］）は比較器１−４動作モード945-948に位置される値に符号化される。（バイト整列のための）シフト制御941、比較開始バイト942、減算値943、接頭辞／接尾辞マスク944は共通の接頭辞914、共通の接尾辞915、減算値916の値に基づいて設定される。
【０１２８】
ノードデータ構造901を完了するため、次のメモリレベルへのポインタ950はノード900のポインタ917で埋められる。ルートノードは常にメモリレベル２  802のエントリ０  811を指向しているので、データ構造901で表されるルートノード720は次のメモリレベル950へのポインタをもたない。
【０１２９】
別の特別なケースはノードデータ構造901への追加的なリーフノード730-734を表している。追加的なリーフノードは結果アレイ710へのポインタ760、761、762、764、765のみを保持する。リーフノードに対するノードデータ構造901は、結果アレイへのポインタを保持するその最上位桁ビットと、このノードが追加的なリーフノードであることを述べるための特別な符号化を保持する比較器１  945の比較モードとを除いて、完全に０で埋められる。
【０１３０】
データ構造を有するメモリ階級をセットアップした後、本発明の方法によるアドレス検索は動作を開始できる。計算が開始され、メモリレベル801の単一のメモリエントリ810からルートノード720のデータ構造を検索することから開始する。
【０１３１】
［必要とされる計算］  
レンジトライノードデータ構造がメモリから検索された後、サーチパスに沿ってその後のレンジトライノードへのサーチが終了するまで進行するように幾つかの必要とされる計算が存在する。
【０１３２】
必要とされる計算の第１の部分が表１に示されており、ここでは比較器で比較される値は入来アドレスに基づいて計算される。１例として、図９で901で表されているノードが使用される。最初に本発明によれば、入力データはｓｈｉｆｔ＿ｃｔｒｌ＊２  941ビット左へシフトされ、（表１の行１に示されているように）右において０で充填される。本発明のこの実施形態では、シフトは入来アドレスをバイト整列するために０、２、４または６により左方向に行われると仮定する。その後、減算値943が本発明のこの実施形態により示されているように（表１の行２により示されているように）シフトされた入来アドレスの開始バイト942にのみ加算される。バイトは上位桁ビットから開始してカウントされる。その後、（表１の行３に示されているように）比較器動作モード945-948と開始バイト942に基づいて、４つの比較器で比較される値が構築される。比較器の動作モード945-948は比較器で実行される有用な比較の幅を決定する、この例では、３２ビット比較器１は４つの８ビット値を比較する。これは比較のために構築される値が開始バイトから開始する８ビットの４倍からなることを意味している。
【０１３３】
必要とされる計算の第２の部分が表２に示されており、ここでは比較が行われ、その結果は単一値に符号化される。計算はメモリ階級から検索されたレンジノードデータ構造901のデータに基づいている。
【表１】
2012524932.tif 000003
【０１３４】
最初に、比較は表１の行３で構築された値と、（表２の行１に示されているように）比較器１−３の比較値931-933との間で行われる。各比較器はモード［３２］、［１６，１６］、［８，８，８，８］で同時に動作するかのように比較を行う。各比較器の出力は１結果ビット（１：より小さい場合、０：等価より大きい場合）と１つの等しいビット（１：等しい場合、０:等しくない場合）である。表２の行１の比較器の出力（ｒｅｓ８，ｒｅｓ１６，ｒｅｓ３２，ｅｑｕａｌ８，ｅｑｕａｌ１６，ｅｑｕａｌ３２）は二進値であり、各ビットは行われる比較のうちの１つに対応する。
【表２】
2012524932.tif 000004
【０１３５】
その後、（表２の行２に示されているように）有効な結果だけが集められる。比較器の動作モードに基づいて、比較が有効であるならば（比較される値の全てのビットがゼロではないならば）、ビットのアレイが得られ、比較結果ビットから生成される。即ち比較器２はモード［８，８，１６］で動作し、全ての比較は有効であり、それ故比較器２の有効な比較結果はｒｅｓ８（３）、ｒｅｓ８（２）、ｒｅｓ１６（０）、ｅｑｕａｌ８（３）、ｅｑｕａｌ８（２）、ｅｑｕａｌ１６（０）である。
【０１３６】
その後、（１に符号化される）より少ないことが報告された有効な比較数をカウントすることにより（表２の行３に示されているように）各比較器の出力の符号化が行われる。計算を終了するため、表２の行３で発生された結果は（表２の行４に示されているように）比較の結果を形成するために二進数として加算される。
【０１３７】
表２の計算期間中、比較器はまた行われた結果の「等価」に関する結果を与える。この結果は前述したように扱われるが、１をカウントし相互に値を加算する代わりに、論理ＯＲが有効な等価結果間で行われる。
【０１３８】
必要とされる計算の最後の部分が表３に示されており、処理される次のメモリエントリの計算または結果アレイの最終結果に導かれる。最初に、（表３の行１に示されているように）比較の結果の最大の可能な符号化（ｍａｘ＿ｒａｎｇｅ）が計算される。比較器１−３の出力が全て１であり、表２の行２−４のものと類似のステップを行うことが仮定される。
【０１３９】
その後、表２の行４の符号化された結果が（表３の行２に示されているように）ｍａｘ＿ｒａｎｇｅ値に等しいか否かが決定される。この計算の結果はｍａｘ＿ｒａｎｇｅ  ビットに記憶される（１：等しい場合、０：等しくない場合）。これはその比較動作モードを考慮しながら比較器１の結果の上位桁ビットを検査することにより行われる。
【０１４０】
処理される次のメモリエントリを計算する前に、入来アドレスの接頭辞／接尾辞は（表３の行３に示されているように）接頭辞／接尾辞比較器で接頭辞／接尾辞値934に比較されるべきである。接頭辞／接尾辞の幅は接頭辞／接尾辞マスク944から得られる。接頭辞／接尾辞比較は結果ｐｒｅｆｉｘ＿ｌｅｓｓ（１：入来する接頭辞が共通の接頭辞よりも小さい場合、０：その他）と、ｐｒｅｆｉｘ＿ｅｑｕａｌ（１：入来する接頭辞が共通の接頭辞に等しい場合、０：その他）、ｓｕｆｆｉｘ＿ｌｅｓｓ（１：入来する接尾辞が共通の接尾辞よりも小さい場合、０：その他）、ｓｕｆｆｉｘ＿ｅｑｕａｌ（１：入来する接尾辞が共通の接尾辞に等しい場合、０：その他）を与える。
【０１４１】
計算の最後のステップはメモリから検索される次のノードのアドレスを計算することである。このアドレスは（表２の行４に示されているように）次のメモリレベル（存在するならば）へのポインタ950と次のレンジオフセットの和として計算される。
【表３】
2012524932.tif 000005
【０１４２】
次のレンジオフセットは（ａ）（表２の行４における）計算された符号化された結果及び等価、（ｂ）計算されたｍａｘ＿ｒａｎｇｅは（表３の）ｍａｘ＿ｒａｎｇｅ、ｐｒｅｆｉｘ＿ｌｅｓｓ、ｐｒｅｆｉｘ＿ｅｑｕａｌ、ｓｕｆｆｉｘ＿ｌｅｓｓであり、（ｃ）接頭辞／接尾辞マスク944の関数として決定される。特に入来する接頭辞が共通の接頭辞よりも小さいならば、次のレンジオフセットは最大の可能なオフセットである（ｍａｘ＿ｒａｎｇｅ）。入来する接頭辞が共通の接頭辞よりも大きいならば、次のレンジオフセットは０である。入来する接頭辞が共通の接頭辞に等しいならば、次のレンジオフセットは符号化された結果、または１によりインクリメントされた符号化された結果である（入来する接尾辞が共通の接尾辞よりも小さいとき、符号化された結果はｍａｘ＿ｒａｎｇｅに等しくなく、符号化された「等価」は１である）。
【０１４３】
この点で、メモリから検索される次のノードのアドレスが知られる。それぞれのメモリエントリは次のメモリレベルから検索され、計算は新しいノードデータ及び同じ入来アドレスで反復される。このサーチは結果に到達するまで継続される。
【０１４４】
万一、計算されているノードが追加的なリーフノードであるならば、計算は結果アレイへのポインタを検索するように減少される。
【０１４５】
表３の行１−３の計算は逐次的に存在したが、これらは相互に平行して行われ、表１、２の計算に平行して行われることができる。
【０１４６】
［必要とされる計算のアーキテクチャ］  
図１０は本発明による機能ユニットとそれらの相互接続を示すブロック図である。
【０１４７】
表１−３に記載されている計算は図１０に示されているような機能ユニットで実行されることができる。本発明のこの実施形態では、メモリ帯域幅１２８ビット幅、最大の比較器幅３２ビット、入来するアドレス３２ビット幅が仮定されている。当業者は本発明が帯域幅と比較器幅の他の値を使用することによって実施されることができることを認識するであろう。
【０１４８】
本発明のこの実施形態で必要とされる計算に対する入力は、入来アドレス（３２ビット幅）、ｓｈｉｆｔ＿ｃｏｎｔｒｏｌ（２ビット幅）、開始バイト（２ビット幅）、減算値（８ビット幅）、比較器の１−３動作モード（全体でそれぞれ３ビット幅）、比較値１−４（それぞれ３２ビット幅、全体で１２８ビット幅）、接頭辞／接尾辞比較値（２４ビット幅）、接頭辞／接尾辞マスク（１０ビット幅）、次のメモリレベルへのポインタ（次のメモリレベルのアドレスと同じ幅）である。これらの入力は図１０の機能ユニットに接続されている。ユニット間の物理的結合に沿って、計算は実行されることができる。
【０１４９】
特に、０充填1001によるシフタ左は入来アドレス入力と入力ｓｈｉｆｔ＿ｃｏｎｔｒｏｌ値に接続される。これはそのシフトされた値の出力（３２ビット幅）に減算装置1002に出力される。
【０１５０】
減算装置1002は入力開始バイト値、入力減算値、1001のシフトされた値の出力に結合される。その出力（減算された値：３２ビット幅）は比較値コンストラクタ１−３装置1003-1005と結合される。
【０１５１】
比較値コンストラクタ１−３装置1003-1005はそれらの出力（構築された比較値：３２ビット幅）を通して比較器１−３  1006-1008と接続される。出力を計算するため、これらは入力開始バイト値、比較器１−３動作モード、1002の減算された値出力と接続される。
【０１５２】
比較器１−３  1006-1008はそれらの出力（比較結果：１４ビット幅）を通して部分的な符号化装置１−３  1013-1015と接続される。出力を計算するため、これらは入力比較値１−３および1003-1005の構築される比較値１−３出力と接続される。
【０１５３】
比較器１  1006について、1006の比較結果出力の３ビットによる最大域検出装置1026との追加的な結合が存在する。
【０１５４】
比較器４  1009はその出力（比較結果：２ビット幅）が部分的な符号化装置４  1016と接続される。出力を計算するため、これは入力比較値４と入力入来アドレスと接続される。
【０１５５】
エネーブル１−３装置1010-1012はそれらの出力（有効な比較:５ビット幅）が部分符号化装置１−３  1013-1015および最大域部分符号化装置１−３  1017-1019と接続される。出力を計算するために、これらは入力比較値１−３と比較される。
【０１５６】
部分符号化装置１−３  1013-1015はそれらの出力（各部分符号化：４ビット幅、全体で１２ビット幅）は等しい符号化による部分符号化装置加算器1021へ接続される。出力を計算するため、これらは入力比較器１−３動作モード、比較器１−３  1006-1008結果出力、エネーブル１−３装置1010-1012結果出力と接続される。
【０１５７】
部分符号化装置４  1016はその出力（部分符号化：２ビット幅）が等しい符号化装置を有する符号化装置加算器1021へ接続される。出力を計算するため、これは入力比較器４動作モードおよび比較器４  1009結果出力と接続される。
【０１５８】
最大域部分符号化装置１−３  1017-1019はそれらの出力が最大域部分符号化加算器1022へ接続されている（各最大域部分符号化：全体で３ビット幅、９ビット幅）。出力を計算するためにこれらは入力比較器１−３動作モードおよびエネーブル装置１−３  1010-1012の結果出力に接続されている。
【０１５９】
最大域部分符号化装置４  1020はその出力が最大域部分符号化加算器1021へ接続されている（部分符号化：１ビット幅）。出力を計算するため、これは入力比較器４動作モードおよび比較器４  1009結果出力に接続される。
【０１６０】
最大域検出装置1026はその出力が次のレンジオフセット装置1024へ接続されている（検出される最大域：１ビット幅）。出力を計算するために、これは入力比較器１動作モードおよび比較器１  1006結果出力の３ビットと接続される。
【０１６１】
部分符号化装置１−４  1013-1016の部分符号化値出力は等しい符号化による部分符号化装置加算器1021の１４ビット幅の入力を形成する。この装置はその５ビット幅の出力が次のレンジオフセット装置1024へ接続される。
【０１６２】
最大域部分符号化装置１−４  1017-1020の最大域部分符号化値出力は最大域部分符号化装置加算器1022の１０ビット幅の入力を形成する。この装置はその４ビット幅出力が次のレンジオフセット装置1024へ接続される。
【０１６３】
接頭辞／接尾辞装置1023はその出力が次のレンジオフセット装置1024へ接続されている（１ビット幅ｐｒｅｆｉｘ−ｅｑｕａｌ、１ビット幅ｐｒｅｆｉｘ−ｌｅｓｓ、１ビット幅ｓｕｆｆｉｘ−ｌｅｓｓ）。出力を計算するために、これは入力入来アドレスと、入力接頭辞／接尾辞比較値と入力接頭辞／接尾辞マスクに接続されている。
【０１６４】
次のレンジオフセット装置1024はその出力が最後の加算器1025へ接続されている（次のレンジ：５ビット幅）。出力を計算するため、これは装置1021、1022、1023、1026の出力および接頭辞／接尾辞マスクの入力と接続されている。
【０１６５】
最後の加算器1025は次のメモリレベルのアドレスと同じ幅である計算出力を発生する。出力を計算するために、これは次のレンジオフセット装置1024の出力および、次のメモリレベルに対する入力ポインタと結合される。
【０１６６】
図１０の機能ユニットは次のメモリレベル中の次のレンジトライノードの位置を決定するために入来アドレスおよびノードデータ構造で動作する。
【０１６７】
ゼロ充填によるシフト左1001は表１の行１の計算を行うように計算されている。これはｓｈｉｆｔ＿ｃｔｒｌ値にしたがって０、２、４または６ビットにより入来アドレスをシフトする。本発明の実施形態は別の数のビットシフトを行うか、または異なる方法でシフトを行うことができる。
【０１６８】
減算装置1002はシフトされた入来アドレスの開始バイトへの値を加算減算するように構成され、それ故これは表１の行２の計算を行う。
【０１６９】
比較値コンストラクタ１−３  1003-1005は比較器１−３  1006-1008で比較される値を構築するように構成されている。その値は開始バイトの値と比較動作モード１−３に基づいて表１の行３に記載されているように構築される。
【０１７０】
比較器１−３  1006-1007は表２の行１でのように、構築された値を比較１−３の値に対して比較するように構成される。比較器の出力は１４ビット幅であり、比較のための全ての可能な幅についての比較結果（等価よりも大きい／より小さい、等しい）を表す。
【０１７１】
エネーブル装置1010-1012は本発明のこの実施形態では、比較器内の最も右の比較がディスエーブルされるか否かを決定するように構成され、その比較値は最も左のビットから開始して充填されることを仮定する。この状態は比較の値中の比較のための対応する値が０に等しいときに識別される。エネーブル装置の結果は比較器１−３動作モードと共に、部分符号化装置1013-1015と最大域部分符号化装置1017-1019へ通過される。これらの装置はいずれの比較結果がエネーブルされ／有効であるかを決定でき、（ａ）少ないことを報告する有効な比較結果（１に符号化）をカウントすることによって、および有効な等価結果において論理ＯＲを行うことにより各比較器の符号化された結果／等価（表２の行２−３）と、（ｂ）全ての比較結果が１であると仮定されるとき有効な比較結果（１に符号化）をカウントすることによって各比較器の符号化された最大域（表３の行１）とを計算することができる。
【０１７２】
本発明のこの実施形態では、比較器４  1009の比較は、比較値コンストラクタとエネーブル装置を必要とせずに入来アドレスと比較４の値との間で直接行われる。比較出力は比較器４の動作モードに基づいて、部分符号化装置1016と最大域部分符号化装置1020により自明な方法で符号化される。
【０１７３】
部分符号化装置１−４  1013-1016の出力は（表２の行４でのように）全ての比較の符号化された結果を計算するため「等しい符号化による部分符号化装置」1021で加算されるように構成される。この装置はさらに論理ＯＲにより符号化された等価結果を計算する。
【０１７４】
1021と類似の方法で、最大域部分符号化加算器1022は（表３の行１でのように）最大域を計算するため最大域部分符号化装置１−４  1017-1020の出力を加算するように構成される。
【０１７５】
最大域検出装置1026は比較器１  1006の上位桁ビットをチェックするように構成され、符号化された比較結果が最大の可能な域に等しいか否かを決定する。
【０１７６】
接頭辞／接尾辞装置1023は表３の行３の計算を行うように構成され、その出力は次のレンジオフセット装置1024へ接続される。
【０１７７】
次のレンジオフセット装置1024は1021（比較の符号化された結果及び符号化された等しい結果）と、1026（ｉｓ＿ｍａｘ＿ｒａｎｇｅ）と、1022（最大域）と、1023（ｐｒｅｆｉｘ＿ｌｅｓｓ、ｐｒｅｆｉｘ＿ｅｑｕａｌ、ｓｕｆｆｉｘ＿ｌｅｓｓ）と、接頭辞／接尾辞マスクとの出力に基づいて、次のレンジオフセットの値を決定するように構成される。
【０１７８】
計算ステップは加算装置1025中で次のレンジオフセットを次のメモリへのポインタへ加算することにより終了される。この時点で、結果に到達するまで、メモリから次のノードを検索し、同じ入来アドレスについて必要な計算を反復することが可能である。
【０１７９】
［装置の組合せ論理設計］  
０充填によるシフタ左1001はｓｈｉｆｔ＿ｃｔｒｌにより制御される２ビット幅４対１マルチプレクサのアレイとして構成される。
【０１８０】
減算装置1002は４つの８ビット幅の加算器のアレイとして構成される。減算値は開始バイトのそれぞれの加算器で加算されるだけであり、他の加算は０の加算により省略される。８ビット加算器は２レベルの桁上げ選択加算器として構成され、各レベルの４ビット加算器は桁上げ先見加算器として構成される。
【０１８１】
各比較値コンストラクタ１−３  1003-1005は開始バイトの論理関数と比較器の動作モードにより制御される４つの８ビット幅４対１マルチプレクサのアレイとして構成される。
【０１８２】
図１１ａは図１０の例に示されたような３２ビット幅比較器1006-1009を示している。
【０１８３】
３２ビット幅比較器は３２ビットの１つの比較と、１６ビットの２つの比較と、８ビットの４つの比較を行う。これは８ビット比較1101-1104を使用して実行され、それらの結果は反転されたツリー方式1105で組み合わされる。反転されたツリー1105では、接続論理装置1106-1108はより大きな比較の結果を形成するために使用される。比較の可能な結果は、「より大きい」、「等しい／より小さい」および「等しい」である。
【０１８４】
部分符号化装置１−３  1013-1015は比較動作モード１−３のビットとエネーブル装置１−３  1010-1012の出力とを使用し、比較器１−３  1006-1008の有効な出力を決定する。その後有効な結果は４つの１ビット入力の加算器で加算され、論理ＯＲが等価結果において行われる。
【０１８５】
等しい符号化による部分符号化加算器1021は３つの３ビット値と１つの１ビット値を加算する桁上げ和加算器として構成される。桁上げ和加算器の最終レベルで、結果符号化を得るための桁上げ先見加算器が存在する。加算に平行して、等価結果の論理ＯＲが実行される。
【０１８６】
共通の接頭辞／接尾辞の比較が行われなければならないならば、入来アドレスの共通の接頭辞ビットと共通の接尾辞ビットは接頭辞／接尾辞マスク値を使用することにより接頭辞／接尾辞装置1023で検索される。これらのビットはその後、２つの２４ビット幅の比較器でそれぞれの接頭辞／接尾辞値ビットに対して比較される。２４ビット幅の比較器は３２ビットの比較器と類似の方法で構成される。
【０１８７】
図１１ｂは次のレンジオフセット装置1024の構成を示している。
【０１８８】
最初に、次のレンジオフセット装置1024は接頭辞／接尾辞マスクのそれぞれのビットにおいて論理ＯＲ1101、1111を実行することにより有効な接頭辞と接尾辞の比較が存在するか否かを決定する。その後次のレンジオフセットが計算され、これは（ａ）０、（ｂ）ｍａｘ＿ｒａｎｇｅ、（ｃ）符号化された結果または（ｄ）符号化された結果＋１であることができる。それぞれの場合の状況が図１１ｂの装置の論理設計で示されている。１によるインクリメンタ1112は“ｃａｒｒｙ  ｉｎ”が１のときのみ加算し、そうでなければその出力はその入力と同じである。
【０１８９】
最後の加算器1025は２つのレベルの桁上げ選択加算器として構成される。第１のレベルは次のレンジ符号化と同じ幅であり、桁上げ先見加算器により構成される。第２のレベルは第１のレベルの実行に応じて、１によりインクリメントされるか、または１によりインクリメントされない残りのビット間で選択される。
【０１９０】
残りの論理装置はデジタルシステム設計の分野の当業者にはよく知られている。
【０１９１】
エネーブル装置1010-1012はＯＲ論理ゲートの階層として構成される。
【０１９２】
最大域部分符号化装置1017-1019は等価結果のない部分符号化装置1013-1015とほぼ同じであり、比較器の結果が全て１であることを仮定する。
【０１９３】
第４の部分符号化装置1016と第４の最大域部分符号化装置1020は比較器１−３のそれらの対応物のサブセットであり、比較器４  1009は２つのモード（エネーブル／ディスエーブル）で動作することに注意する。
【０１９４】
前述の実施形態は本発明によるレンジトライを使用する迅速なアドレス検索および接頭辞照合のための設計の例を示している。本発明によるレンジトライ方法及びシステムは簡潔性と速度との優れたバランスを与える。幾つかの他の構成はさらに前述したような考察を理解するデジタルシステム設計分野の当業者により容易に開発されることができる。
【０１９５】
レンジトライノードは共通のアドレス境界部を共有し、アドレス境界部を省略し、アドレスを整列する前述の規則に加えて圧縮された形態の複数のアドレス境界を記憶できる。このような場合には、コンピュータの読取り可能な媒体から読取られるノードデータの圧縮解除が前述の計算前に必要とされる。
【０１９６】
代わりに、レンジトライノードは別の方法で圧縮された複数のアドレス境界を記憶できる。その後、オリジナル範囲の圧縮解除及び検索が必要とされ、リクエストされた入来アドレスとノードに記憶されたアドレス境界の比較は取られるブランチを決定する。
【０１９７】
これらの両ケースおよび先に詳細に説明した特別な実施形態において、レンジトライの主な利点は予め定められたビットに記憶されたノードに明示的または暗黙的に記憶されたアドレス境界数を増加していることである。それにおいて、ノード当りの増加されたブランチ数が実現され、したがってより短くよりスケール可能な決定ツリーが構築されることができる。
【０１９８】
以下、アドレス域を規定するアドレス境界のセットを仮定して、本発明によるレンジトライデータ構造を構築するために使用されることができる４つのヒューリスティックを説明する。
【０１９９】
アドレススペースにおけるアドレス域Ｒｉ（例えばＲ１，．．．，Ｒ７）を規定するｋ＋１基本アドレス境界を規定するｋ個のアドレスＡｉのセットを仮定すると、本発明の方法による決定ツリーは前述の第１、第２、第４、第４、第５の規則に基づいて構築される。その構築は同時に低いツリー深さを標的としながら各反復で比較されるアドレス（ツリーノード）を選択することにより行われる。
【０２００】
決定ツリーを構築するとき２つの目的が存在する。第１の目的はノードブランチ数を最大にするために処理されるビットを少数にする必要があるアドレスを選択することである。第２に、決定ツリー中のノードは等しい又は類似の深さのサブツリーへブランチされなければならず、それによってツリー全体は実質的に平衡される。
【０２０１】
前述の目的は、ブランチ数の最大化が必ずしもツリーを平衡した状態に維持するわけではなくその逆もあるので、ある程度まで相互に相反する可能性がある。それ故、恐らく許容可能ではない複雑性を有するかおよび／または比較的多量の計算労力を必要とする最適な策ではなく４つの簡単なヒューリスティックが提案される。
【０２０２】
これらの２つの目的は別として、本発明の方法の構成に関して考慮される他のパラメータが存在する。これらのパラメータの幾つかはメモリ帯域幅、恐らく比較長、単一の反復における比較数、アドレス整列制限である。
【０２０３】
４つのヒューリスティックを、アドレス域とアドレス境界の随意選択的なセットに基づいて、本発明の方法により使用するための決定ツリーの構築について説明する。さらに、前述の考察にしたがってソフトウェアプログラミングの当業者によってさらに多くの開発が容易に行われることができる。
【０２０４】
各ヒューリスティックはツリーノードまたはツリーレベルの構造を生成する帰納的関数を使用する。２つの異なる方法、即ちトップダウンとボトムアップを考える。
【０２０５】
トップダウンヒューリスティックは第１にルートノードを生成し、その後同様にそのチルドレンへ、そしてツリーの終点（リーフ）方向へ移動する。
【０２０６】
ボトムアップヒューリスティックは第１にリーフノードを構築し、その後それらのアドレス境界は次のツリーレベルで使用され、これはツリーのルートに到達されるまで反復される。
【０２０７】
ヒューリスティックは特定の構造について調整されるべきであり、したがって少数のアドレス長のみまたは１または少数のそれらの組合せのみの比較が同時に行われることを可能にできる。
【０２０８】
２つのトップダウンおよび２つのボトムアップヒューリスティックをアドレス境界間でアドレス部分を共有及び省略する特定の実施形態に関して以下説明する。異なるヒューリスティックが異なる圧縮方式で必要とされるが、しかしながらこれは当業者により容易に開発されることができる。
【０２０９】
レンジトライを構築するヒューリスティックは方法の特定の構成に調整されることに注意する。以下説明する１つのトップダウンおよび１つのボトムアップヒューリスティックは単一の長さのみの比較を平行して可能にし、他は幾つかの組合せの比較を可能にする。ヒューリスティックの説明は次のとおりである。  
ａ）ＴＤ−ＳＬＣ  単一長の並列比較を有するトップダウンヒューリスティック：
１）方法の規則、特にアドレスの整列、ノード共通接頭辞及び省略されるゼロ接尾辞の発見を適用する。  
２）例えば８ビットのブランチの数を最大にする比較器長の中から最長の比較器長を選択する。ツリーの平衡と利用可能な比較器の数はこの時点では考慮されない。  
３）前述の比較長で処理されるセット中の全てのアドレス（アドレス境界）を考慮する。（選択された最長の比較長のために）比較されることができないアドレス接尾辞を省略し、これらがゼロに等しいことを仮定する。  
４）前述の比較により規定されるアドレス域（インターバル）を生成する。  
５）（レンジのアドレス境界により規定される）比較数が利用可能な比較器リソースへ減少されるまで、単一のアドレス域で隣接するアドレス域を融合する。この方法の規則、特に共有される共通のアドレス接頭辞と接尾辞を発見する方法の規則を考慮する。融合は平衡されたアドレス境界数を含むアドレス域（及び従ってレンジトライノード）を生成することを目的とする。結果的なアドレス域は本発明の方法の規則により比較が行われるノードブランチ及びそれらのボーダーである。  
６）生成されたチルドレンノードについて帰納的に反復する。  
７）各ノードが単一の基本アドレス域を含むときに終了する。  
アドレス域の数を平衡する代わりに、ツリーを平衡した状態に維持するために使用される他の計量、例えばレンジの密度、インターバル長当りのレンジの数が使用できることに注意する。  
ｂ）ＴＤ−ＶＬＣ  可変長の並列比較を有するトップダウンヒューリスティック：  
ＴＤ−ＶＬＣは前述のＴＤ−ＳＬＣであるが、ステップ５）が以下のように変更されている。  
５’）比較数が利用可能なリソースの数に減少されるまで、隣接するソートアドレス域を融合し、長いアドレス域を分割し、平衡された数の基本アドレス域を含むグループを生成する。分割はさらに長い長さの比較を付加する（より良好な正確性を実現する）ことにより行われる。可能にされた比較長の組合せはターゲット構成に基づいて考慮されるべきである。
【０２１０】
ｃ）ＢＵ−ＳＬＣ  単一長の並列比較を有するボトムアップヒューリスティック：
１）必要な限り方法の規則を適用した後、１つの反復で比較されることができる第１のｂアドレスＡｉ＞Ｎａ（ここでＮａは最初は０である）を選択する（例えばＡｉ，Ａｉ＋１，．．．Ａｂ；０≦ｉ≦ｂ）。比較長は全ての第１のｂアドレスに共通であり、比較がフルアドレス幅の比較の等価物であるのに十分であるべきである。規則（第１、必要な限り第５まで）はここでも適用される。
【０２１１】
２）生成下でノードのアドレス域の上限Ｎｂとして、アドレススペース中の任意の点を設定し、ここでＮｂ∈（Ａｔ，Ａｂ］およびｔ／ｂ＝Ｃ％であり（Ｃは０と１００の間の定数を示している）、それによってＮｂは０の最長の接尾辞を有する。生成下でノードへマップされる結果的なアドレス域は［Ｎａ，Ｎｂ）である。
【０２１２】
３）アドレススペース中の全てのアドレスＡｉがノードにあるまで先のグループＮｂの上限から開始して前述の処理を反復する。
【０２１３】
４）先のレベルにおける全てのノードのボーダーＮａ、Ｎｂを有するアドレスＡｉの新しいセットを使用して前述のステップを帰納的に反復する。  
５）リスト中の全てのアドレスが単一のノードで処理される（即ちルートノードが到達された）ときに終了する。  
ｄ）ＢＵ−ＶＬＣ  可変長の並列比較を有するボトムアップヒューリスティック：  
ＢＵ−ＶＬＣは変更されたステップ１を有するＢＵ−ＳＬＣである。ＢＵ−ＶＬＣで、比較長は可変であるがターゲットの構成により可能にされる組合せ内である必要がある。
【０２１４】
［レンジトライの更新］  
アドレス検索を使用する大部分の応用はアドレス域のそれらのセットを頻繁に更新する必要がある。例えば現在のコアルーターは約５分毎に接頭辞の更新を受信する。アドレス域が接頭辞又は簡単なインターバルとして説明されるとき、異なる更新機構が使用される必要がある。しかしながら、いずれかの場合には、更新はアドレス域を規定するアドレス（キー）を挿入または消去することを必要とする可能性がある。本発明の方法では、これは影響を受けたリーフノードまたはサブツリーを更新し、好ましくはボトムアップ方法を使用して前述のヒューリスティックに記載されているように分割又は融合を行うことにより容易に実現されることができる。
【０２１５】
アドレス域がインターバル、例えばパケット分類のポート域として説明されるとき、前述の簡単なアドレス挿入又は削除はインターバルを付加または除去するのに十分である。他方で、接頭辞がアドレス域を説明するために使用されるとき、更新機構はオーバーラップする接頭辞と単一の接頭辞の多部分の追跡をするためにより多くの情報を記憶する必要がある。しかしながら、都合のよいことは、本発明の方法がノード当り限定のないメモリ帯域幅とブランチの従来技術のレンジツリーで１対１でマップされることができ、したがって接頭辞を記憶し更新するレンジツリー技術にしたがうことができる。
【０２１６】
簡単に言えば、本発明の方法では、接頭辞は文献（P. Warkhede、S. Suri、G. Vargheseの“Multiway range trees: scalable ip lookup with fast updates”、Comput. Netw.、44巻、no.3、289-303頁、2004年）において従来技術のレンジツリーで記載されているように記憶及び更新されることができる。
【０２１７】
主要な考えは、アドレス域を規定する接頭辞はツリーのリーフのみではなく内部ツリーノードに記憶されることができることである。（接頭辞として説明した）アドレス域のボーダーを規定する各アドレス境界はアドレス境界上に終点を有する接頭辞の数のカウンタを維持する。Warkhede等により説明されているように、各ノードはＷ＋１ビットのビットマップを維持し、ここでｉ−１ビットは長さｉの接頭辞が一致しているか否かを示している。本発明の方法の規定とWarkhede等により説明されている従来技術のレンジツリーでは僅かな違いが存在する。本発明の方法では、比較は「より小さい」または「より大きい−等しい」を報告し、接頭辞“１０＊＊＊”がインターバル［１００００，１１０００）にマップされる。レンジツリーでは、比較は「より小さい−等しい」または「より大きい」を報告し、それ故例えば接頭辞“１０＊＊＊”がインターバル（１０１１１，１０１１１］にマップされる。Warkhede等は従来技術のレンジツリーがマップされるアドレススペースは（−∞，２］であり、接頭辞はその開始アドレス境界と接頭辞アドレス域に含まれるがそのペアレントでは含まれない任意のノード又はリーフアドレス境界とで記憶されることを考察する。本発明の方法は従来技術のレンジツリーのように比較を行うように容易に調節されるが、これは長いゼロ接尾辞の利点（規則３）を緩めるので、便宜的ではない。
【０２１８】
前述の例より、本発明の方法は１の接尾辞とは反対にゼロの接尾辞の範囲を有するインターバルに接頭辞をマップすることが観察されることができる。結論として、何の利点も失うことなく以下のように接頭辞の記憶及び更新機構を調節することが好ましい。本発明の方法のアドレススペースは［０，∞）にマップされ、接頭辞は接頭辞の終点と、接頭辞領域に含まれるがそのペアレントでは含まれない任意のノードまたはリーフアドレス境界とで記憶される。
【０２１９】
代わりに、アドレススペース［０，２Ｗ）はこの方法で最初に説明したように考慮されることができる。その後、その長さに沿って接頭辞（または接頭辞に対するポインタ）が各ノードで記憶され、そのアドレス域は接頭辞により含まれるが、そのペアレントノードのアドレス域は接頭辞により含まれない。（接頭辞として説明した）アドレス域ボーダーを規定する各アドレス境界はアドレス境界上に終点を有する接頭辞数に対してカウンタを維持する。新しい接頭辞が挿入されるとき、これは既にノードに記憶された任意の既存の接頭辞が新しく挿入されたものよりも短い場合のみ前述の条件に基づいてレンジトライノードに記憶されることができる。接頭辞が削除されるとき、削除された接頭辞を置換する接頭辞はそれがデータ構造に既に記憶されていても入力として与えられる必要がある。
【０２２０】
本発明の方法によるレンジトライはまた相互にオーバーラップする可能性があるアドレス域のセットを記憶することもできる。オーバーラップするアドレス域の任意のセット（インターバル）は接頭辞のセットが前述したように記憶される方法と同じ方法でレンジトライに記憶されることができる。
【０２２１】
本発明の他の実施形態が本発明の技術的範囲を逸脱せずに考慮され、実施されることができることが当業者に明白であろう。本発明の技術的範囲は特許請求の範囲によってのみ限定される。明細書は本発明を説明しているが、本発明を限定することを意図していない。
【図１】
2012524932.tif 000006
【図２】
2012524932.tif 000007
【図３】
2012524932.tif 000008
【図４】
2012524932.tif 000009
【図５】
2012524932.tif 000010
【図６ａ】
2012524932.tif 000011
【図６ｂ】
2012524932.tif 000012
【図６ｃ】
2012524932.tif 000013
【図７ａ】
2012524932.tif 000014
【図７ｂ】
2012524932.tif 000015
【図８】
2012524932.tif 000016
【図９】
2012524932.tif 000017
【図１０】
2012524932.tif 000018
【図１１ａ】
2012524932.tif 000019
【図１１ｂ】
2012524932.tif 000020
【図１２ａ】
2012524932.tif 000021
【図１２ｂ】
2012524932.tif 000022
【図１３】
2012524932.tif 000023
【手続補正書】
【提出日】平成23年4月5日(2011.4.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築する方法において、
前記アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は下限及び上限アドレスにより規定され、
前記アドレススペース中のアドレスは予め定められた数のビットにより表されており、
前記方法は、
−前記リクエストされたアドレスが属する前記基本アドレス域のセットから特定の基本アドレス域を決定するために決定ツリーを構成し、
前記決定ツリーは少なくとも１つのレベルを具備し、前記少なくとも１つのレベルは少なくとも１つのノードを具備し、
前記少なくとも１つのノードはノードアドレス域へマップするように構成されており、前記ノードアドレス域は前記アドレススペースのノード関連部分であり、前記ノードアドレス域は下限及び上限のノードアドレスにより規定され、
前記少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチは前記ノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、前記少なくとも１つのノードはさらに前記少なくとも２つのブランチアドレス域に前記ノードアドレス域を分割するように規定されている少なくとも１つのノードアドレスを有し、
前記ブランチアドレス域はノードアドレス域中の前記少なくとも１つのノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、各ノードアドレスの前記分解は、次の少なくとも一方を含み、それは、
分解されている前記ノードアドレスから、値「ゼロ」を有するノードアドレス接尾辞または前記ノードアドレス域中の全てのアドレスに共通のアドレス部である１以上のアドレス部分を決定し、前記１以上のアドレス部分は前記少なくとも１つのノードに記憶されるとき少なくとも１つの省略可能なアドレス部分として省略可能であるか、
前記省略可能なアドレス部分以外の全てのさらに残りのアドレス部分からの少なくとも１つの共通のアドレス部分として分解されている前記ノードアドレスに記憶するため、多数のノードアドレスに共通の１以上のアドレス部分を決定するかであり、
−選択規則にしたがって、前記少なくとも１つのノード中に前記複数のアドレス部分を記憶するステップを含み、
前記選択規則は動作のグループからの少なくとも１つの動作を含み、前記動作は、
−前記ノードに一度だけ前記少なくとも１つの共通のアドレス部分を記憶するか、
−前記少なくとも１つの省略可能なアドレス部分を省略するかのいずれかの動作と、
−前記分解ステップにおいて決定されたときの全ての他のアドレス部分を前記ノードに記憶する動作を含んでおり、前記全ての他のアドレス部分は前記少なくとも１つの共通のアドレス部分または前記少なくとも１つの省略可能なアドレス部分のいずれでもない方法。
【請求項２】
前記少なくとも１つのノードの全てのブランチアドレス域の集合は前記少なくとも１つのノードのノードアドレス域である請求項１記載の方法。
【請求項３】
前記ブランチアドレス域は前記ブランチが指向する前記ノードの前記ノードアドレス域である請求項１記載の方法。
【請求項４】
前記ノードに記憶された前記アドレス部分により占有される総ビット数は前記ノードアドレスの総ビット数よりも少ない請求項１記載の方法。
【請求項５】
ノードは２つのノードブランチを有する単一のノードアドレスのアドレス部分を記憶するように構成され、前記単一のノードアドレスは少なくとも１つの省略可能なアドレス部分を有している請求項１記載の方法。
【請求項６】
前記決定ツリーはさらに少なくとも上位レベルより下の下位レベルを有するように構成され、前記下位レベルのノードは前記決定ツリーのリーフノードとして構成され、各リーフノードは前記基本アドレス域のセットから１つの基本アドレス域または１つの基本アドレス域の一部へマップし、各リーフノードはそれが属する前記それぞれの基本アドレス境界に関連される情報を記憶している請求項１記載の方法。
【請求項７】
各ノードはアドレス域を規定する接頭辞または接頭辞のセットから接頭辞に対するポインタを記憶するように構成され、前記接頭辞は前記ノードアドレス域を含む前記接頭辞のセットの前記最長の一致する接頭辞である請求項６記載の方法。
【請求項８】
リーフノードではない各ノードはさらに、前記ノードアドレスにおいて終点を有する接頭辞数をカウントするためのカウンタ値が配置されているノードアドレス当りのカウンタ値を記憶するように構成されている請求項７記載の方法。
【請求項９】
さらに、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを含み、前記ステップは前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記リクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの次のレベルのノードへブランチするステップを含んでいる請求項６記載の方法。
【請求項１０】
さらに、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを含み、前記ステップは前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
予め規定された定数値を有する前記リクエストされたアドレスを減算し、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記減算結果のそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの次のレベルのノードへブランチするステップを含んでいる請求項６記載の方法。
【請求項１１】
前記少なくとも１つの省略可能なアドレス部分は前記予め定められた数のビットの共通のノード接頭辞サブセットとしてノードアドレス域中の全てのアドレスに対して前記少なくとも１つの共通部により決定される共通のノード接頭辞であり、前記共通のノード接頭辞サブセットは前記ノードに記憶された前記アドレス部分のビットの前記サブセットから省略されている請求項１記載の方法。
【請求項１２】
前記少なくとも１つの省略可能なアドレス部分は前記ノードアドレス域中のノードアドレスの接尾辞を表し、前記接尾辞は値「ゼロ」を有し、前記少なくとも１つの省略可能なアドレス部分は前記ノードに記憶されるのを省略されている請求項１記載の方法。
【請求項１３】
前記少なくとも１つの共通のアドレス部分は前記ノード中の２以上のノードアドレスに共通であり、前記少なくとも１つの共通のアドレス部分は前記ノードにおいて一度のみ記憶され、取られるノードブランチを決定した時に一度のみ前記アドレスの対応するアドレス部分と比較される請求項１記載の方法。
【請求項１４】
予め定められた定数値を、前記下限及び上限のノードアドレスから、および各ノードアドレスから、および前記リクエストされたアドレスから減算するステップを含んでおり、
前記減算は各ノードアドレスの前記分解に先行している請求項１記載の方法。
【請求項１５】
前記予め定められた定数値は前記下限のノードアドレスの前記値に等しい請求項１４記載の方法。
【請求項１６】
さらに前記複数のビットにおいて圧縮関連の技術を適用することにより、前記ノードに記憶された前記アドレス部分により占有される総ビット数を減少するステップを含んでいる請求項１記載の方法。
【請求項１７】
前記比較の結果は上位桁アドレス部分から下位桁アドレス部分による優先度によりノードアドレス毎に考慮されており、ノードアドレスの下位桁アドレス部分の前記比較結果は前記ノードアドレスの前記上位桁アドレス部分の比較結果が等しい場合にのみ考慮され、
前記方法は、前記リクエストされたアドレスが属する前記ブランチアドレス域を規定するためノードアドレス毎に前記比較結果を組み合わせるステップを含んでおり、結果として前記ブランチアドレス域により規定されるように次のレベルへブランチするステップを含んでいる請求項９または１０記載の方法。
【請求項１８】
前記決定ツリーを構成するステップは、
−基本アドレス域の前記セットからのレンジ境界であるアドレスを選択し、前記選択されたアドレスの前記部分は前記決定ツリーのノードに含まれ、
−前記決定ツリー構造において前記ノードを構成するステップを含んでおり、それによって前記決定ツリーの各リーフノードは、１つの基本アドレス域を指向するかまたは基本アドレス域の前記セットから１つの基本アドレス域のサブセットを指向する請求項６記載の方法。
【請求項１９】
前記決定ツリーを構成するステップは上から下へのヒューリスティックにより行われ、
−一部がノードに含まれるアドレスを前記決定ツリーの前記上位レベルから開始して選択し、
−その後、下方向で次のレベルの前記ノードを構築し、
−全てのリーフノードが基本アドレス域または基本アドレス域の前記セットの基本アドレス域のサブセットを指向するときに終了するステップを含んでいる請求項１８記載の方法。
【請求項２０】
前記決定ツリーを構成するステップは下から上へのヒューリスティックにより実現され、
−一部がノードに含まれるアドレスを、リーフノードにブランチするノードを最初に構成する前記決定ツリーの前記下位レベルから選択を開始し、前記決定ツリーの各リーフノードは基本アドレス域または基本アドレス域の前記セットのアドレス域のサブセットを指向し、
−その後、前記決定ツリーに沿って上方向で次のレベルのノードを構築し、
−単一のルートノードが上位レベルで構築されるときに終了するステップを含んでいる請求項１８記載の方法。
【請求項２１】
アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するコンピュータシステムにおいて、
前記アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は下限及び上限アドレスにより規定され、
前記アドレススペース中のアドレスは予め定められた数のビットにより表されており、
前記コンピュータシステムは、メモリ及びプロセッサを具備し、前記プロセッサは前記メモリに結合され、ここで前記プロセッサは前記アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための前記決定ツリーを構築するための方法を実行するように構成され、その方法は、
−前記リクエストされたアドレスが属する基本アドレス域の前記セットから特定の基本アドレス域を決定するための前記決定ツリーを構成し、
前記決定ツリーは少なくとも１つのレベルを具備し、前記少なくとも１つのレベルは少なくとも１つのノードを具備し、
前記少なくとも１つのノードはノードアドレス域へマップするように構成されており、前記ノードアドレス域は前記アドレススペースのノード関連部分であり、前記ノードアドレス域は下限及び上限のノードアドレスにより規定され、
前記少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチは前記ノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、前記少なくとも１つのノードはさらに前記少なくとも２つのブランチアドレス域に前記ノードアドレス域を分割するように規定されている少なくとも１つのノードアドレスを有し、
前記ブランチアドレス域はノードアドレス域中の前記少なくとも１つのノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、各ノードアドレスの前記分解は、次の少なくとも一方を含み、それは、
分解されている前記ノードアドレスから、値「ゼロ」を有するノードアドレス接尾辞または前記ノードアドレス域中の全てのアドレスに共通のアドレス部である１以上のアドレス部分を決定し、前記１以上のアドレス部分は前記少なくとも１つのノードに記憶されるとき少なくとも１つの省略可能なアドレス部分として省略可能であるか、
前記省略可能なアドレス部分以外の全てのさらに残りのアドレス部分からの少なくとも１つの共通のアドレス部分として分解されている前記ノードアドレスに記憶するため、多数のノードアドレスに共通の１以上のアドレス部分を決定するかであり、
−選択規則にしたがって、前記少なくとも１つのノード中に前記複数のアドレス部分を記憶するステップを含み、
前記選択規則は動作のグループからの少なくとも１つの動作を有し、前記動作は、
−前記ノードに一度だけ前記少なくとも１つの共通のアドレス部分を記憶するか、
−前記少なくとも１つの省略可能なアドレス部分を省略するかのいずれかの動作と、
−前記分解ステップにおいて決定されたときの全ての他のアドレス部分を前記ノードに記憶する動作を含んでおり、前記全ての他のアドレス部分は前記少なくとも１つの共通のアドレス部分または前記少なくとも１つの省略可能なアドレス部分ではないコンピュータシステム。
【請求項２２】
前記コンピュータシステムは、
少なくとも上位レベルより下の下位レベルを有するように前記決定ツリーを構成するステップを実行するように構成され、前記下位レベルのノードは前記決定ツリーのリーフノードとして構成され、各リーフノードは基本アドレス域の前記セットから１つの基本アドレス域または１つの基本アドレス域の一部へマップし、各リーフノードはそれが属するそれぞれの基本アドレス境界に関連される情報を記憶している請求項２１記載のコンピュータシステム。
【請求項２３】
さらに、前記コンピュータシステムは、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを実行するように構成され、前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
前記それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記リクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの前記次のレベルのノードへブランチするステップを含んでいる請求項２２記載のコンピュータシステム。
【請求項２４】
さらに、前記コンピュータシステムは、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを実行するように構成され、前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
予め規定された定数値を有する前記リクエストされたアドレスを減算し、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記減算結果のそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの次のレベルのノードへブランチするステップを含んでいる請求項２２記載のコンピュータシステム。
【請求項２５】
前記プロセッサは複数の処理ユニットを具備し、各処理ユニットは前記決定ツリーの少なくとも１つのレベルに関連され、前記決定ツリー計算の前記関連されるレベルにおいて、前記関連されるレベルの前記ノードに記憶される前記アドレス部分の少なくとも１つを前記リクエストされたアドレスのそれぞれの対応するアドレスと比較し、その後前記決定ツリーに沿って下方項で前記次のレベルの前記ノードへ分岐する処理を実行するように構成されている請求項２３または２４記載のコンピュータシステム。
【請求項２６】
前記コンピュータシステムは通信システム、ネットワーク化ルーターおよびパケットスイッチングシステムから選択されたものである請求項２１乃至２５のいずれか１項記載のコンピュータシステム。
【請求項２７】
アドレススペース中でリクエストされたアドレスのアドレス検索で使用するための決定ツリーを構築するための、請求項２１乃至２６のいずれか１項記載のコンピュータシステムによりロードされるコンピュータの読取り可能な媒体に記憶されているコンピュータプログラムにおいて、
前記アドレススペースは基本的なアドレス域のセットとして構成されており、
各基本的なアドレス域は下限及び上限アドレスにより規定され、
前記アドレススペース中のアドレスは予め定められた数のビットにより表されており、
前記コンピュータシステムは、メモリ及びプロセッサを具備し、前記プロセッサは前記メモリに結合され、コンピュータプログラムプロダクトはロードされた後、前記プロセッサが以下のステップを実行することを可能にし、即ち、
−前記リクエストされたアドレスが属する前記基本アドレス域のセットから特定の基本アドレス域を決定するための前記決定ツリーを構成し、
前記決定ツリーは少なくとも１つのレベルを有し、前記少なくとも１つのレベルは少なくとも１つのノードを有し、
前記少なくとも１つのノードはノードアドレス域へマップするように構成されており、前記ノードアドレス域は前記アドレススペースのノード関連部分であり、前記ノードアドレス域は下限及び上限のノードアドレスにより規定され、
前記少なくとも１つのノードは少なくとも２つのノードブランチを有し、
各ノードブランチは前記ノードアドレス域中のそれぞれのオーバーラップしないブランチアドレス域にマップしており、前記少なくとも１つのノードはさらに前記少なくとも２つのブランチアドレス域に前記ノードアドレス域を分割するように規定されている少なくとも１つのノードアドレスを有し、
前記ブランチアドレス域はノードアドレス域中の前記少なくとも１つのノードアドレスにより規定されており、
−複数のアドレス部分に各ノードアドレスを分解し、各アドレス部分は予め定められた数のビットのそれぞれのサブセットにより表され、各ノードアドレスの前記分解は、次の少なくとも一方を含み、それは、
分解されている前記ノードアドレスから、値「ゼロ」を有するノードアドレス接尾辞または前記ノードアドレス域中の全てのアドレスに共通のアドレス部である１以上のアドレス部分を決定し、前記１以上のアドレス部分は前記少なくとも１つのノードに記憶されるとき少なくとも１つの省略可能なアドレス部分として省略可能であるか、
前記省略可能なアドレス部分以外の全てのさらに残りのアドレス部分からの少なくとも１つの共通のアドレス部分として分解されている前記ノードアドレスに記憶するため、多数のノードアドレスに共通の１以上のアドレス部分を決定するかであり、
−選択規則にしたがって、前記少なくとも１つのノード中に前記複数のアドレス部分を記憶するステップを含み、
前記選択規則は動作のグループからの少なくとも１つの動作を含み、前記動作は、
−前記ノードに一度だけ前記前記少なくとも１つの共通のアドレス部分を記憶するか、
−前記少なくとも１つの省略可能なアドレス部分を省略するかのいずれかの動作と、
−前記分解ステップにおいて決定されたときの全ての他のアドレス部分を前記ノードに記憶する動作を含んでおり、前記全ての他のアドレス部分は前記少なくとも１つの共通のアドレス部分または前記少なくとも１つの省略可能なアドレス部分ではない方法。
【請求項２８】
請求項２７記載のコンピュータプログラムに与えられているコンピュータの読取り可能な媒体。
【請求項２９】
決定ツリーを使用することにより、アドレススペース中でリクエストされたアドレスのアドレス検索のためのコンピュータシステムであって、前記決定ツリーは請求項１乃至６のいずれか１項記載の方法にしたがって構成されており、前記コンピュータシステムはメモリ及びプロセッサを具備し、前記プロセッサは前記メモリに結合され、
前記プロセッサは、
−前記リクエストされたアドレスを入力として受信し、
−前記リクエストされたアドレスが属する前記基本アドレス域を決定するステップを実行するように構成され、前記決定ツリーの各レベルにおいて上位レベルのルートノードから開始し、
前記それぞれのレベルのそれぞれのノードについて：
前記それぞれのノードに記憶された前記アドレス部分を読取り、
前記レベル中の前記それぞれのノードに記憶された少なくとも１つのアドレス部分を前記リクエストされたアドレスのそれぞれの対応するアドレス部分と比較し、
前記少なくとも１つの比較に基づいて、前記リーフノードの１つに到達するとき前記基本アドレス域が決定されるまで、前記決定ツリーの前記次のレベルのノードへブランチするステップを行うように構成されているコンピュータシステム。
【請求項３０】
前記コンピュータシステムはさらに、
前記それぞれのノードに記憶された前記アドレス部分を読取った後、減算結果を得るために予め規定された定数値を前記リクエストされたアドレスから減算し、前記レベルの前記それぞれのノード中に記憶された少なくとも１つのアドレス部分を前記リクエストされたアドレスのそれぞれの対応するアドレス部分とを比較する前記ステップ前に、前記リクエストされたアドレスを前記減算結果により置換するステップを行うように構成されている請求項２９記載のコンピュータシステム。
【請求項３１】
前記コンピュータシステムは通信システム、ネットワーク化ルーター、パケットスイッチングシステムから選択されたものである請求項２９または３０記載のコンピュータシステム。
【国際調査報告】
2012524932.tif 000024
2012524932.tif 000025
2012524932.tif 000026