【手続補正書】
【提出日】平成17年9月29日(2005.9.29)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  ルーティング・テーブルを圧縮する方法であって、
前記ルーティング・テーブルのバイナリ・ツリー表現を構築するステップであって、前記バイナリ・ツリーは前記ルーティング・テーブルにおける様々なルートを表すノードを有している、ステップと、
次のホップを前記ノードに割り当てるステップと、
普及している次のホップを前記ツリーの上方向に移動させるステップと、
前記ツリーにおける冗長分岐を排除し、出力ツリーを生じさせるステップと、
前記出力ツリーを新たなルーティング・テーブルに変換するステップと、
を含むことを特徴とする方法。
【請求項２】  請求項１記載の方法において、前記割り当てるステップは、子ノードを１つだけ有する親ノードに対して新たな子ノードを作成し、次のホップを前記親ノードから前記新たな子ノードに割り当てるステップを含むことを特徴とする方法。
【請求項３】  請求項１記載の方法において、前記移動させるステップは、Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従って普及している次のホップを前記ツリーの上方向に移動させるステップを含み、ただし、Ａ＊Ｂは、親ノードにおいて、前記親ノードに対応する１対の子ノードに対して次のホップＡ及びＢの集合から形成される次のホップの集合であることを特徴とする方法。
【請求項４】  請求項１記載の方法において、前記移動させるステップは、最初のノードで開始し最後のノードで終了する一連の単一分岐に圧縮経路を適用するステップであって、Ｘは前記最後のノードにおける次のホップの集合を表し、Ｙは前記最初のノードにおける次のホップの集合を表すものとして、Ｘ∩Ｙ＝φならば、Ｙを最初のノードに、Ｘを最後のノードに割り当て、Ｘ∩Ｙ≠φならば、Ｘ∩Ｙを、最初のノードと最後のノードとに割り当てるという演算に従って、次のホップを前記ツリーの上方向に移動させるステップを含むことを特徴とする方法。
【請求項５】  請求項１記載の方法において、前記排除するステップは、
最も近接した空でない祖先ノードから次のホップを選択するステップと、
前記親ノードから分岐している子ノードを調べ、前記選択された次のホップが前記子ノードに対する次のホップの要素であるかどうかを判断し、そうである場合には、前記子ノードに対する前記次のホップを排除するステップと、
を含むことを特徴とする方法。
【請求項６】  請求項１記載の方法の結果としてコンピュータ可読な媒体に記憶され構築されていることを特徴とするルーティング・テーブル。
【請求項７】  ルーティング・テーブルのバイナリ・ツリー表現を圧縮する方法であって、前記バイナリ・ツリーは、複数のレベルにおいて、前記ルーティング・テーブルにおける様々なルートを表す複数のノードを有しており、あるレベルにおける親ノードは次のより下位のレベルにおけるゼロ、１又は２の子ノードに分岐することができ、前記ノードのいくつかは関連する次のホップを有している、方法において、
子ノードを１つだけ有する親ノードに対して新たな子ノードを作成し、次のホップを前記親ノードから前記新たな子ノードに割り当てることによって、前記ツリーを正規化するステップと、
Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従い、子ノードの対応する対に対する次のホップＡ及びＢの集合を親ノードにおいてスーパーネットすることによって、普及している次のホップを前記ツリーの上方向に移動させるステップであって、ただし、Ａ＊Ｂは、前記親ノードにおいて生じる次のホップの集合である、ステップと、
前記ツリーを下方向にサブネットして子ノードを有する冗長分岐を排除するステップであって、少なくとも１つの次のホップが、対応する最も近接した空でない祖先ノードの次のホップの集合に含まれている、ステップと、
を含むことを特徴とする方法。
【請求項８】  請求項７記載の方法において、前記正規化し、移動させ及びサブネットするステップは、前記ツリーを通過する３つのパスにおいて実行されることを特徴とする方法。
【請求項９】  請求項７記載の方法において、前記正規化し移動させるステップは、前記ツリーを通過する単一のパスにおいて実行されることを特徴とする方法。
【請求項１０】  請求項７記載の方法において、個別の親ノードに対してＡ＊Ｂ＝Ａ∩Ｂである場合には、前記個別の親ノードと関連する前記１対の子ノードにおける次のホップを除去するステップを更に含むことを特徴とする方法。
【請求項１１】  請求項７記載の方法において、前記サブネットするステップは、
最も近接した空でない祖先ノードから次のホップを選択するステップと、
前記親ノードから分岐している子ノードを調べ、前記選択された次のホップが前記子ノードに対する次のホップの要素であるかどうかを判断し、そうである場合には、前記子ノードに対する前記次のホップを排除するステップと、
を含むことを特徴とする方法。
【請求項１２】  請求項１１記載の方法において、前記選択するステップは、前記ツリー構造の変更を回避することを試みる次のホップを選択するステップを含むことを特徴とする方法。
【請求項１３】  ルーティング・テーブルのバイナリ・ツリー表現を圧縮する方法であって、前記バイナリ・ツリーは、複数のレベルにおいて、前記ルーティング・テーブルにおける様々なルートを表す複数のノードを有しており、あるレベルにおける親ノードは次のより下位のレベルにおけるゼロ、１又は２の子ノードに分岐することができる、方法において、
Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従い、普及している次のホップを前記ツリーの上方向に移動させるステップであって、ただし、Ａ＊Ｂは、親ノードにおいて、前記親ノードに対応する１対の子ノードに対する次のホップＡ及びＢの集合から形成される次のホップの集合である、ステップと、
前記ツリーにおける冗長分岐を排除するステップと、
を含むことを特徴とする方法。
【請求項１４】  請求項１３記載の方法において、個別の親ノードに対してＡ＊Ｂ＝Ａ∩Ｂである場合には、前記排除するステップに先立って、前記個別の親ノードと関連する前記１対の子ノードにおける次のホップを除去するステップを更に含むことを特徴とする方法。
【請求項１５】  請求項１３記載の方法において、前記排除するステップは、
最も近接した空でない祖先ノードから次のホップを選択するステップと、
前記親ノードから分岐している子ノードを調べ、前記選択された次のホップが前記子ノードに対する次のホップの要素であるかどうかを判断し、そうである場合には、前記子ノードに対する前記次のホップを排除するステップと、
を含むことを特徴とする方法。
【請求項１６】  請求項１５記載の方法において、前記選択するステップは、前記ツリー構造の変更を回避することを試みる次のホップを選択するステップを含むことを特徴とする方法。
【請求項１７】  ルーティング・テーブルを処理する方法であって、
Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従って前記人気のある次のホップを移動させることによって（ただし、Ａ＊Ｂは、次のホップＡ及びＢの集合から形成される次のホップの集合である）、より特定のルートからより一般的なルートに人気のある次のホップの集合を伝搬させるステップであって、より特定のルートは、より一般的なルートに対するＩＰアドレスと比較してプレフィクスのビット数が多いＩＰアドレスによって定義される、ステップと、
人気のある次のホップの集合から次のホップを選択して、前記より特定のルートを再定義するステップと、
を含むことを特徴とする方法。
【請求項１８】  請求項１７記載の方法において、共通のＩＰアドレスを有する冗長ルートをすべて排除するステップを更に含むことを特徴とする方法。
【請求項１９】  ルーティング・テーブルを圧縮する方法であって、
Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従って前記人気のある次のホップを移動させることによって（ただし、Ａ＊Ｂは、次のホップＡ及びＢの集合から形成される次のホップの集合である）、  人気のある次のホップの集合をスーパーネットするステップと、
選択された次のホップを人気のある次のホップの集合からサブネットして、冗長ルートを排除するステップと、
を含むことを特徴とする方法。
【請求項２０】  ルーティング・テーブルを記憶するメモリと、
前記メモリに結合されており、前記ルーティング・テーブルにリスト化されているルートに従ってメッセージをルーティングするプロセッサと、
前記メモリに記憶されている前記ルーティング・テーブルを圧縮するテーブル圧縮器であって、前記ルーティング・テーブルのバイナリ・ツリー表現を構築して次のホップを前記ツリーにおけるノードに割り当て、普及している次のホップを前記ツリーの上方向に移動させて前記ツリーにおける冗長分岐を排除し、前記ツリーを圧縮されたルーティング・テーブルに変換して戻す、テーブル圧縮器と、
を備えていることを特徴とするルータ。
【請求項２１】  請求項２０記載のルータにおいて、前記テーブル圧縮器は、前記メモリ内のプログラムであり前記プロセッサ上で実行されることを特徴とするルータ。
【請求項２２】  請求項２０記載のルータにおいて、前記テーブル圧縮器は集積回路装置として具体化されることを特徴とするルータ。
【請求項２３】  請求項２０記載のルータにおいて、前記テーブル圧縮器は、Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従って、次のホップを前記ツリーの上方向に移動させ、ただし、Ａ＊Ｂは、親ノードにおいて、前記親ノードに対応する１対の子ノードに対して次のホップＡ及びＢの集合から形成される次のホップの集合であることを特徴とするルータ。
【請求項２４】  請求項２０記載のルータにおいて、前記テーブル圧縮器は、最初のノードで開始し最後のノードで終了する一連の単一分岐に経路圧縮技術を適用し、Ｘは前記最後のノードにおける次のホップの集合を表し、Ｙは前記最初のノードにおける次のホップの集合を表すものとして、Ｘ∩Ｙ＝φならば、Ｙを最初のノードに、Ｘを最後のノードに割り当て、Ｘ∩Ｙ≠φならば、Ｘ∩Ｙを、最初のノードと最後のノードとに割り当てるという演算に従って、次のホップを前記ツリーの上方向に移動させることを特徴とするルータ。
【請求項２５】  請求項２０記載のルータにおいて、前記テーブル圧縮器は、最も近接した空でない祖先ノードから次のホップを選択し、前記親ノードから分岐している子ノードを調べ、前記選択された次のホップが前記子ノードに対する次のホップの要素であるかどうかを判断し、そうである場合には、前記子ノードに対する前記次のホップを排除することを特徴とするルータ。
【請求項２６】  ルーティング・テーブルを記憶するメモリと、
前記メモリに結合されており、前記ルーティング・テーブルにリスト化されているルートに従ってメッセージをルーティングするプロセッサと、
前記メモリに記憶されている前記ルーティング・テーブルを圧縮し、より特定のルートからより一般的なルートに人気のある次のホップの集合を伝搬させるテーブル圧縮器であって、より特定のルートは、より一般的なルートに対するＩＰアドレスと比較してプレフィクスのビット数が多いＩＰアドレスによって定義され、Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従って、前記人気のある次のホップを移動させ（ただし、Ａ＊Ｂは、次のホップＡ及びＢの集合から形成される次のホップの集合である）、人気のある次のホップの集合から次のホップを選択して、前記より特定のルートを再定義し、共通のＩＰアドレスを有する冗長ルートを排除する、テーブル圧縮器と、
を備えていることを特徴とするルータ。
【請求項２７】  コンピュータ可読な媒体であって、
ルーティング・テーブルのバイナリ・ツリー表現を構築するステップであって、前記バイナリ・ツリーは前記ルーティング・テーブルにおける様々なルートを表すノードを有している、ステップと、
次のホップを前記ノードに割り当てるステップと、
普及している次のホップを前記ツリーの上方向に移動させるステップと、
前記ツリーにおける冗長分岐を排除し、出力ツリーを生じさせるステップと、
前記出力ツリーを新たなルーティング・テーブルに変換するステップと、
を実行するコンピュータ実行可能な命令を記憶していることを特徴とするコンピュータ可読な媒体。
【請求項２８】  コンピュータ可読な媒体であって、
子ノードを１つだけ有する親ノードに対して新たな子ノードを作成し、次のホップを前記親ノードから前記新たな子ノードに割り当てることによって、前記ツリーを正規化するステップと、
Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従い、子ノードの対応する対に対する次のホップＡ及びＢの集合を親ノードにおいてスーパーネットすることによって、普及している次のホップを前記ツリーの上方向に移動させるステップであって、ただし、Ａ＊Ｂは、前記親ノードにおいて生じる次のホップの集合である、ステップと、
前記ツリーを下方向にサブネットして子ノードを有する冗長分岐を排除するステップであって、少なくとも１つの次のホップが、対応する最も近接した空でない祖先ノードの次のホップの集合に含まれている、ステップと、
を実行するコンピュータ実行可能な命令を記憶していることを特徴とするコンピュータ可読な媒体。
【請求項２９】  コンピュータ可読な媒体であって、
Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従い、普及している次のホップを前記ツリーの上方向に移動させるステップであって、ただし、Ａ＊Ｂは、親ノードにおいて、前記親ノードに対応する１対の子ノードに対する次のホップＡ及びＢの集合から形成される次のホップの集合である、ステップと、
前記ツリーにおける冗長分岐を排除するステップと、
を実行するコンピュータ実行可能な命令を記憶していることを特徴とするコンピュータ可読な媒体。
【請求項３０】  コンピュータ可読な媒体であって、
より特定のルートからより一般的なルートに人気のある次のホップの集合を伝搬させるステップであって、より特定のルートは、より一般的なルートに対するＩＰアドレスと比較してプレフィクスのビット数が多いＩＰアドレスによって定義される、ステップと、
Ａ∩Ｂ＝φならばＡ＊Ｂ＝Ａ∪ＢでありＡ∩Ｂ≠φならばＡ＊Ｂ＝Ａ∩Ｂであるという演算に従って前記人気のある次のホップを移動させるステップと（ただし、Ａ＊Ｂは、次のホップＡ及びＢの集合から形成される次のホップの集合である）、
人気のある次のホップの集合から次のホップを選択して、前記より特定のルートを再定義するステップと、
共通のＩＰアドレスを有する冗長ルートをすべて排除するステップと、
を実行するコンピュータ実行可能な命令を備えていることを特徴とするコンピュータ可読な媒体。