【手続補正書】
【提出日】平成15年12月24日(2003.12.24)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
宛先アドレスと送信元アドレスとをこの順に連結した経路アドレスのビットパターンに対応した2分木構造の検索木情報を格納する記憶手段と、
受信したマルチキャストパケットから宛先アドレスと送信元アドレスとを読み出し、その読み出した宛先アドレスと送信元アドレスとをこの順に連結して経路アドレスを生成し、その生成された経路アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を行う一致判定手段とを有することを特徴とするパケット中継装置。
【請求項２】
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
宛先アドレスと送信元アドレスとを連結した経路アドレスのビットパターンに対応した2分木構造の検索木情報を格納する記憶手段と、
受信したマルチキャストパケットから宛先アドレスと送信元アドレスとを読み出し、その読み出した宛先アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を行い、その読み出した送信元アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を行う一致判定手段とを有することを特徴とするパケット中継装置。
【請求項３】
上記一致判定手段は、受信したマルチキャストパケットから読み出した宛先アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を、受信したマルチキャストパケットから読み出した送信元アドレスと上記記憶手段に格納されている経路アドレスとの一致判定より先に行うことを特徴とする請求項２に記載のパケット中継装置。
【請求項４】
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
宛先アドレスと送信元アドレスとをこの順に連結した経路アドレスのビットパターンに対応した2のｐ乗分木構造（ｐは自然数）の検索木情報を格納する記憶手段と、
受信したマルチキャストパケットから宛先アドレスと送信元アドレスとを読み出し、その読み出した宛先アドレスと送信元アドレスとをこの順に連結して経路アドレスを生成し、その生成された経路アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を行う一致判定手段とを有することを特徴とするパケット中継装置。
【請求項５】
複数のネットワークを相互に接続し、パケットを中継するパケット中継装置であって、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
送信元アドレスと宛先アドレスとを、宛先アドレス、送信元アドレスの順に連結して経路アドレスとし、上記経路アドレスのビットパターンに対応した２分木構造に構成された検索木情報を格納する記憶手段と、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスをこの順に連結した経路アドレスの上位ビットから１ビットづつ検査し、その検査したビットの値によって上記記憶手段に格納された２分木構造をもつ検索木を検索する回路とを有することを特徴とするパケット中継装置。
【請求項６】
複数のネットワークを相互に接続し、パケットを中継するパケット中継装置であって、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
送信元アドレスと宛先アドレスとを、宛先アドレス、送信元アドレスの順に連結して経路アドレスとし、上記経路アドレスのビットパターンに対応した２のp乗分木構造に構成された検索情報を格納する記憶手段と、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを連結した経路アドレスの上位ビットからｐビットづつ検査し、その検査したビットの値によって上記記憶手段に記憶された２のｐ乗分木構造をもつ検索木を検索する回路とを有することを特徴とするパケット中継装置。
【請求項７】
複数のネットワークを相互に接続し、パケットを中継するパケット中継装置であって、受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーとして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
送信元アドレスと宛先アドレスを、宛先アドレス、送信元アドレスの順に連結して経路アドレスとし、この経路アドレスのビットパターンに対応する２のｐ乗分木構造をとる検索テーブルを格納する記憶手段と、
経路アドレスの上位ｍビットに対応する２のｍ乗個の２のｐ乗分木のノードを、記憶手段上の決まった位置に展開し、それぞれのノードを、経路アドレスの第０ビットから第(ｍ−１)ビットまでが取りうる値に１対１に対応させ、検索時には、経路アドレスの第０ビットから第(ｍ−１)ビットの値に従って、展開されたノードの一つを選択し、第ｍビット以降は経路アドレスをｐビットづつ検査し、その検査したビットの値によって上記記憶手段に記憶された２のｐ乗分木構造をもつ検索木の枝を検索する回路を有することを特徴とするパケット中継装置。
【請求項８】
複数のネットワークを相互に接続し、パケットを中継するパケット中継装置であって、受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
送信元アドレスと宛先アドレスとを、宛先アドレス、送信元アドレスの順に連結して経路アドレスとし、上記経路アドレスのビットパターンに対応した２分木構造に構成された検索木情報を格納する記憶手段と、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスをこの順に連結した経路アドレスの上位ビットから１ビットづつ検査し、その検査したビットの値によって上記記憶手段に格納された２分木構造をもつ検索木を検索する回路とを有することを特徴とするパケット中継装置。
【請求項９】
請求項８に記載のパケット中継装置において、
検索木情報を、1つの２分木ノードと、その直下につながるｐ−１段分の合計(２のｐ乗−１)個分の２分木ノードを一つの２のｐ乗分木ノードにまとめ、まとめられる最下段の２の(ｐ−１)乗個の２分木ノードに、それより上段のノードに割り付けられていたエントリデータを埋め込み、２のｐ乗分木ノードを、２分木を２の(ｐ−１)乗個分併せた形で構成することを特徴とするパケット中継装置。
【請求項１０】
請求項８に記載のパケット中継装置において、
一つの２分木ノードと、その直下につながるｐ−１段分の合計(２のｐ乗−１)個分の２分木ノードを一つの２のｐ乗分木ノードにまとめ、まとめられる最下段の２の(ｐ−１)乗個の２分木ノードに、それより上段のノードに割り付けられていたエントリデータを埋め込むことにより、２のｐ乗分木ノードを、２分木を２の(ｐ−１)乗個分併せた形で構成することに加え、２分木を複数個併せるときに、一つだけ持てば良い要素を一つだけ保持するようにすることを特徴とする特徴とするパケット中継装置。
【請求項１１】
請求項９又は請求項１０に記載のパケット中継装置において、
２のｐ乗分木ノードを検索のために読むときにノード全てを読まずに、２のｐ乗分木ノードを作成するときに併せた２の(ｐ−１)乗個の２分木ノードの内の、いずれか一つに対応するデータのみを読むようにすることを特徴とするパケット中継装置。
【請求項１２】
請求項１０に記載のパケット中継装置において、
各ノードにそのノード自身のマスク長を格納するのではなく、そのノードの直ぐ下に繋がるノードのマスク長を格納することにより、ノードのマスク長を、そのノードのデータを読む前に知り、経路アドレスの、ノードのマスク長で示されるビット位置から、そのビット位置＋ｐ−１までの値に従い、ノードのデータの内、読み込む部分を選択することを特徴とするパケット中継装置。
【請求項１３】
ルータに入ってきたパケットの宛先アドレスから、このパケットを次に出力すべきポート、及び、次に送るべきルータ、又はホストのアドレスを高速に検索するための検索手段に関し、
検索を、宛先アドレスの上位ビットから１ビットづつ検査してゆく２分木検索により行い、検査を行うビット位置を、マスク長に対応させることにより、マスク付きの一致検索を行い、検索木の各ノードの最初に読み込むデータ内に、そのノードにエントリが割り付けられているか否かを示すフラグを設け、最初に、このフラグを読み込み、エントリが割り付けられていないノードでは、経路情報を読み込まないようにすることにより、データの読み込み時間を短縮し、検索処理の高速化を図ることを特徴とするパケット中継装置。
【請求項１４】
マルチキャストパケットのヘッダ情報を入力され、上記マルチキャストパケットに対する送信ポート等の転送情報を検索して出力する専用ＬＳＩにおいて、
マルチキャストパケットの宛先アドレスと送信元アドレスをこの順に連結した経路アドレスの上位ビットからｐビットづつ検査し、上記検査ビットの値によって記憶手段に記憶された２のｐ乗分木構造をもつ検索木を検索する回路を有することを特徴とする専用ＬＳＩ。