【手続補正書】
【提出日】平成19年11月28日(2007.11.28)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  サーチリクエストにおいて与えられるデスティネーションアドレスキーの第１の部分によってインデックス付けされた複数個の第１のメモリ場所を含む第１レベルのマッパと、
第１のメモリ場所のインデックス付けされた１つに記憶される第１のサブツリーセレクトおよびサーチリクエストにおけるデスティネーションアドレスキーの第２の部分に依存してインデックス付けされた複数個の第２のメモリ場所を含む第２レベルのマッパとを含み、ルックアップテーブルに対して発行された単一のサーチリクエストの結果、マッパの１つの場所に記憶される、キーに対する最長プレフィックス一致に対応する値が得られる、最長プレフィックス一致ルックアップテーブル。
【請求項２】  第２のレベルのマッパはさらに、
第１のサブツリーセレクトによってインデックス付けされたサブツリー記述子を記憶するサブツリーメモリと、
第２のメモリ場所を含むサブツリーマッパと、
選択されたサブツリー記述子およびキーの第２の部分に依存してサブツリーマッパに対するマッパインデックスを与えるマッパアドレス論理とを含む、請求項１に記載のルックアップテーブル。
【請求項３】  サブツリー記述子はさらに、
サブツリーのためのデフォルト値と、
ビットマップとを含み、前記ビットマップは、サブツリーにおける各可能なノードごとに１ビットを含み、さらに、
複数個のブロックポインタを含み、各ブロックポインタは、値を記憶するための第２のメモリ場所のブロックのベースアドレスを記憶する、請求項２に記載のルックアップテーブル。
【請求項４】  サーチリクエストにおいて与えられるデスティネーションアドレスキーの第１の部分によってインデックス付けされた複数個の第１のメモリ場所を含む第１レベルのマッパと、
第１のメモリ場所のインデックス付けされた１つに記憶される第１のサブツリーセレクトおよびサーチリクエストの中のデスティネーションアドレスキーの第２の部分に依存してインデックス付けされた複数個の第２のメモリ場所を含む第２レベルのマッパと、
ルックアップテーブルに対して発行された単一のサーチリクエストからマッパの１つの
場所に記憶された、キーに対する最長プレフィックス一致に対応する値を転送するための手段とを含む、最長プレフィックス一致ルックアップテーブル。
【請求項５】  第２レベルのマッパはさらに、
第１のサブツリーセレクトによってインデックス付けされたサブツリー記述子を記憶するサブツリーメモリと、
第２のメモリ場所を含むサブツリーマッパと、
選択されたサブツリー記述子およびキーの第２の部分に依存してサブツリーマッパのためのマッパインデックスを与えるための手段とを含む、請求項４に記載のルックアップテーブル。
【請求項６】  サブツリー記述子はさらに、
サブツリーのためのデフォルト値と、
ビットマップとを含み、前記ビットマップは、サブツリーにおける各可能なノードごとに１ビットを含み、さらに、
複数個のブロックポインタを含み、各ブロックポインタは、第２のメモリ場所のブロックのベースアドレスを記憶する、請求項５に記載のルックアップテーブル。
【請求項７】  サーチリクエストにおいて与えられるＩＰデスティネーションアドレスの第１の部分によってインデックス付けされた複数個の第１のメモリ場所を含む第１レベルのマッパと、
第１のメモリ場所のインデックス付けされた１つに記憶された第１のサブツリーセレクトおよびサーチリクエストの中のＩＰデスティネーションアドレスの第２の部分に依存してインデックス付けされた複数個の第２のメモリ場所を含む第２レベルのマッパとを含み、ルックアップテーブルに対して発行された単一のサーチリクエストの結果、マッパの１つの場所に記憶される、ＩＰアドレスに対応する最長プレフィックス一致が得られる、ＩＰアドレスのための最長プレフィックス一致を与えるルックアップテーブル。
【請求項８】  第２レベルのマッパはさらに、
第１のサブツリーセレクトによってインデックス付けされたサブツリー記述子を記憶するサブツリーメモリと、
第２のメモリ場所を含むサブツリーマッパと、
選択されたサブツリー記述子およびＩＰアドレスの第２の部分に依存してサブツリーマッパのためのマッパインデックスを与えるマッパアドレス論理とを含む、請求項７に記載のルックアップテーブル。
【請求項９】  サブツリー記述子はさらに、
サブツリーのためのデフォルト値と、
ビットマップとを含み、前記ビットマップは、サブツリーにおける各可能なノードごとに１ビットを含み、さらに、
複数個のブロックポインタを含み、各ブロックポインタは、最長プレフィックス一致を記憶するための第２のメモリ場所のブロックのベースアドレスを記憶する、請求項８に記載のルックアップテーブル。
【請求項１０】  「０」にセットされた、ノードに対応するビットマップ中の１ビットは、ノードが前のノードと値を共有することを示す、請求項３または請求項６に記載のルックアップテーブル。
【請求項１１】  第２のメモリ場所のためのインデックスは、ノードに対応するビットより前にビットマップに記憶された「１」の数に依存する、請求項３、６、９のいずれかに記載のルックアップテーブル。
【請求項１２】  サブツリーのためのマッパに記憶された値の数は、ビットマップに記憶された「１」の数に依存する、請求項１１に記載のルックアップテーブル。
【請求項１３】  ブロックは、１６個の第２のメモリ場所を含む、請求項３、６、９のいずれかに記載のルックアップテーブル。
【請求項１４】  可能なノードの数は、２５６個である、請求項３、６、９のいずれかに記載のルックアップテーブル。
【請求項１５】  第２のメモリ場所の１つに記憶される第２のサブツリーセレクトおよびキーの第３の部分に依存してインデックス付けされた複数個の第３のメモリ場所を含む第３レベルのマッパをさらに含む、請求項１、４、７のいずれかに記載のルックアップテーブル。
【請求項１６】  第３のメモリ場所の１つに記憶される第３のサブツリーセレクトおよびキーの第４の部分に依存してインデックス付けされた複数個の第４のメモリ場所を含む第４レベルのマッパをさらに含む、請求項１５に記載のルックアップテーブル。
【請求項１７】  キーは３２ビットであり、キーの第１の部分は１６ビットであり、キーの第２の部分は８ビットであり、キーの第３の部分は８ビットである、請求項１５に記載のルックアップテーブル。
【請求項１８】  キーは４０ビットであり、キーの第１の部分は１６ビットであり、キーの第２の部分は８ビットであり、キーの第３の部分は８ビットであり、キーの第４の部分は８ビットである、請求項１６に記載のルックアップテーブル。
【請求項１９】  「０」にセットされた、ノードに対応するビットマップ中の１ビットは、ノードが前のノードとブロックポインタを共有することを示す、請求項９に記載のルックアップテーブル。
【請求項２０】  第２のメモリ場所の１つに記憶された第２のサブツリーセレクトおよびＩＰアドレスの第３の部分に依存してインデックス付けされた複数個の第３のメモリ場所を含む第３レベルのマッパをさらに含む、請求項７に記載のルックアップテーブル。
【請求項２１】  第３のメモリ場所の１つに記憶された第３のサブツリーセレクトおよびＩＰアドレスの第４の部分に依存してインデックス付けされた複数個の第４のメモリ場所を含む第４レベルのマッパをさらに含む、請求項２０に記載のルックアップテーブル。
【請求項２２】  ＩＰアドレスは３２ビットであり、ＩＰアドレスの第１の部分は１６ビットであり、ＩＰアドレスの第２の部分は８ビットであり、ＩＰアドレスの第３の部分は８ビットである、請求項２０に記載のルックアップテーブル。
【請求項２３】  ＩＰアドレスは４０ビットであり、ＩＰアドレスの第１の部分は１６ビットであり、ＩＰアドレスの第２の部分は８ビットであり、ＩＰアドレスの第３の部分は８ビットであり、ＩＰアドレスの第４の部分は８ビットである、請求項２１に記載のルックアップテーブル。
【請求項２４】  サーチリクエストにおいて与えられるデスティネーションアドレスキーの第１の部分で第１レベルのマッパ中の第１の場所を選択するステップと、
インデックス付けされた第１の場所に記憶された第１のサブツリーセレクトを検出すると、サーチリクエスト中のデスティネーションアドレスキーの第２の部分および第１のサブツリーセレクトに依存して第２レベルのマッパ中の第２の場所を選択するステップと、
キーに対する単一のサーチリクエストに応答してマッパの１つの場所に記憶される、キーに対する最長プレフィックス一致に対応する値を転送するステップとを含む、キーに対する最長プレフィックス一致を与えるための方法。
【請求項２５】  第２の場所を選択するステップはさらに、
サブツリーメモリにおいて第１のサブツリーセレクトによってインデックス付けされたサブツリー記述子を選択するステップと、
選択されたサブツリー記述子およびキーの第２の部分に依存してサブツリーマッパのためのマッパインデックスを判定するステップと、
マッパインデックスでサブツリーマッパ中の第２のメモリ場所を選択するステップとを含む、請求項２４に記載の方法。
【請求項２６】  サブツリー記述子を選択するステップは、
サブツリーのためのデフォルト値を設けるステップと、
ビットマップを設けるステップとを含み、前記ビットマップは、サブツリーにおける各可能なノードごとに１ビットを含み、さらに、
複数個のブロックポインタを設けるステップを含み、各ブロックポインタは、第２のメ
モリ場所のブロックのベースアドレスを記憶する、請求項２５に記載の方法。
【請求項２７】  「０」にセットされた、ノードに対応するビットマップ中の１ビットは、ノードが前のノードと値を共有することを示す、請求項２６に記載の方法。
【請求項２８】  第２のメモリ場所のためのインデックスは、ノードに対応するビットより前にビットマップに記憶された「１」の数に依存する、請求項２６に記載の方法。
【請求項２９】  サブツリーのためのマッパに記憶された値の数は、ビットマップに記憶された「１」の数に依存する、請求項２８に記載の方法。
【請求項３０】  ブロックは、１６個の第２のメモリ場所を含む、請求項２６に記載の方法。
【請求項３１】  可能なノードの数は、２５６個である、請求項２６に記載の方法。
【請求項３２】  第２の場所に記憶された第２のサブツリーセレクトを検出すると、キーの第３の部分および第２のサブツリーセレクトに依存して第３レベルのマッパ中の第３の場所を選択するステップをさらに含む、請求項２４に記載の方法。
【請求項３３】  第３の場所に記憶された第３のサブツリーセレクトを検出すると、キーの第４の部分および第３のサブツリーセレクトに依存して第４レベルのマッパ中の第４の場所を選択するステップをさらに含む、請求項３２に記載の方法。
【請求項３４】  キーは３２ビットであり、キーの第１の部分は１６ビットであり、キーの第２の部分は８ビットであり、キーの第３の部分は８ビットである、請求項３２に記載の方法。
【請求項３５】  キーは４０ビットであり、キーの第１の部分は１６ビットであり、キーの第２の部分は８ビットであり、キーの第３の部分は８ビットであり、キーの第４の部分は８ビットである、請求項３３に記載の方法。