(57)【特許請求の範囲】
【請求項１】
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
宛先アドレスと送信元アドレスとをこの順に連結した経路アドレスのビットパターンに対応した2分木構造の検索木情報を格納する記憶手段と、
受信したマルチキャストパケットから宛先アドレスと送信元アドレスとを読み出し、その読み出した宛先アドレスと送信元アドレスとをこの順に連結して経路アドレスを生成し、その生成された経路アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を行う一致判定手段とを有することを特徴とするパケット中継装置。
【請求項２】
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
宛先アドレスと送信元アドレスとを連結した経路アドレスのビットパターンに対応した2分木構造の検索木情報を格納する記憶手段と、
受信したマルチキャストパケットから宛先アドレスと送信元アドレスとを読み出し、その読み出した宛先アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を行い、その読み出した送信元アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を行う一致判定手段とを有することを特徴とするパケット中継装置。
【請求項３】
上記一致判定手段は、受信したマルチキャストパケットから読み出した宛先アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を、受信したマルチキャストパケットから読み出した送信元アドレスと上記記憶手段に格納されている経路アドレスとの一致判定より先に行うことを特徴とする請求項２に記載のパケット中継装置。
【請求項４】
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
宛先アドレスと送信元アドレスとをこの順に連結した経路アドレスのビットパターンに対応した2のｐ乗分木構造（ｐは自然数）の検索木情報を格納する記憶手段と、
受信したマルチキャストパケットから宛先アドレスと送信元アドレスとを読み出し、その読み出した宛先アドレスと送信元アドレスとをこの順に連結して経路アドレスを生成し、その生成された経路アドレスと上記記憶手段に格納されている経路アドレスとの一致判定を行う一致判定手段とを有することを特徴とするパケット中継装置。
【請求項５】
複数のネットワークを相互に接続し、パケットを中継するパケット中継装置であって、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
送信元アドレスと宛先アドレスとを、宛先アドレス、送信元アドレスの順に連結して経路アドレスとし、上記経路アドレスのビットパターンに対応した２分木構造に構成された検索木情報を格納する記憶手段と、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスをこの順に連結した経路アドレスの上位ビットから１ビットづつ検査し、その検査したビットの値によって上記記憶手段に格納された２分木構造をもつ検索木を検索する回路とを有することを特徴とするパケット中継装置。
【請求項６】
複数のネットワークを相互に接続し、パケットを中継するパケット中継装置であって、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
送信元アドレスと宛先アドレスとを、宛先アドレス、送信元アドレスの順に連結して経路アドレスとし、上記経路アドレスのビットパターンに対応した２のp乗分木構造（pは自然数）に構成された検索情報を格納する記憶手段と、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスを連結した経路アドレスの上位ビットからｐビットづつ検査し、その検査したビットの値によって上記記憶手段に記憶された２のｐ乗分木構造をもつ検索木を検索する回路とを有することを特徴とするパケット中継装置。
【請求項７】
複数のネットワークを相互に接続し、パケットを中継するパケット中継装置であって、受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーとして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
送信元アドレスと宛先アドレスを、宛先アドレス、送信元アドレスの順に連結して経路アドレスとし、この経路アドレスのビットパターンに対応する２のｐ乗分木構造（pは自然数）をとる検索テーブルを格納する記憶手段と、
経路アドレスの上位ｍビット（mは自然数）に対応する２のｍ乗個の２のｐ乗分木のノードを、記憶手段上の決まった位置に展開し、それぞれのノードを、経路アドレスの第０ビットから第(ｍ−１)ビットまでが取りうる値に１対１に対応させ、検索時には、経路アドレスの第０ビットから第(ｍ−１)ビットの値に従って、展開されたノードの一つを選択し、第ｍビット以降は経路アドレスをｐビットづつ検査し、その検査したビットの値によって上記記憶手段に記憶された２のｐ乗分木構造をもつ検索木の枝を検索する回路を有することを特徴とするパケット中継装置。
【請求項８】
複数のネットワークを相互に接続し、パケットを中継するパケット中継装置であって、受信したマルチキャストパケットの宛先アドレスと送信元アドレスを検索のキーにして上記マルチキャストパケットに対する経路情報を検索し、上記経路情報に従い１つ又は複数のポートに上記マルチキャストパケットを転送するパケット中継装置において、
送信元アドレスと宛先アドレスとを、宛先アドレス、送信元アドレスの順に連結して経路アドレスとし、上記経路アドレスのビットパターンに対応した２分木構造に構成された検索木情報を格納する記憶手段と、
受信したマルチキャストパケットの宛先アドレスと送信元アドレスをこの順に連結した経路アドレスの上位ビットから１ビットづつ検査し、その検査したビットの値によって上記記憶手段に格納された２分木構造をもつ検索木を検索する回路とを有することを特徴とするパケット中継装置。
【請求項９】
請求項８に記載のパケット中継装置において、
検索木情報を、1つの２分木ノードと、その直下につながるｐ−１段分（pは自然数）の合計(２のｐ乗−１)個分の２分木ノードを一つの２のｐ乗分木ノードにまとめ、まとめられる最下段の２の(ｐ−１)乗個の２分木ノードに、それより上段のノードに割り付けられていたエントリデータを埋め込み、２のｐ乗分木ノードを、２分木を２の(ｐ−１)乗個分併せた形で構成することを特徴とするパケット中継装置。
【請求項１０】
請求項８に記載のパケット中継装置において、
一つの２分木ノードと、その直下につながるｐ−１段分（pは自然数）の合計(２のｐ乗−１)個分の２分木ノードを一つの２のｐ乗分木ノードにまとめ、まとめられる最下段の２の(ｐ−１)乗個の２分木ノードに、それより上段のノードに割り付けられていたエントリデータを埋め込むことにより、２のｐ乗分木ノードを、２分木を２の(ｐ−１)乗個分併せた形で構成することに加え、２分木を複数個併せるときに、一つだけ持てば良い要素を一つだけ保持するようにすることを特徴とする特徴とするパケット中継装置。
【請求項１１】
請求項９又は請求項１０に記載のパケット中継装置において、
２のｐ乗分木ノードを検索のために読むときにノード全てを読まずに、２のｐ乗分木ノードを作成するときに併せた２の(ｐ−１)乗個の２分木ノードの内の、いずれか一つに対応するデータのみを読むようにすることを特徴とするパケット中継装置。
【請求項１２】
請求項１０に記載のパケット中継装置において、
各ノードにそのノード自身のマスク長を格納するのではなく、そのノードの直ぐ下に繋がるノードのマスク長を格納することにより、ノードのマスク長を、そのノードのデータを読む前に知り、経路アドレスの、ノードのマスク長で示されるビット位置から、そのビット位置＋ｐ−１までの値に従い、ノードのデータの内、読み込む部分を選択することを特徴とするパケット中継装置。
【請求項１３】
マルチキャストパケットのヘッダ情報を入力され、上記マルチキャストパケットに対する送信ポート等の転送情報を検索して出力する専用ＬＳＩにおいて、
マルチキャストパケットの宛先アドレスと送信元アドレスをこの順に連結した経路アドレスの上位ビットからｐビット（pは自然数）づつ検査し、上記検査ビットの値によって記憶手段に記憶された２のｐ乗分木構造をもつ検索木を検索する回路を有することを特徴とする専用ＬＳＩ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のネットワークを相互に接続し、パケットを中継するパケット中継装置、特にマルチキャストパケットの次転送先検索方式に関する。
【０００２】
【従来の技術】
ユーザの増加に伴い、インターネットを流れるトラフィック(パケット)が急増し、インターネットが大規模化・高速化している。また、現在のインターネット(Internet Protocolによるパケット通信網：以下ＩＰネットワーク)では、従来のデータ系の通信だけでなく、インターネット電話やインターネット放送などのリアルタイム系アプリケーション(用途)も登場し、音声通信機能の取り込みや、放送機能の取り込みが進んでいる。このような状況下において、ＩＰネットワークにおけるＩＰマルチキャスト技術は、インターネットにおける動画や音声やコンテンツなどのマルチメディアデータの配信に有効な技術として期待されている。また、ＩＰネットワークを構成するパケット中継装置(ルータ)におけるＩＰマルチキャスト技術のサポート、ＩＰマルチキャスト技術の高速化が課題となっている。
【０００３】
ルータは、ある端末から特定の一つの端末にパケットを送信するユニキャスト通信の場合、受信パケットのヘッダ内の宛先ＩＰアドレスに対応する経路情報(次に転送すべきルータあるいは端末のＩＰアドレス、およびルータ内の送信ポート番号)をルーティングテーブルから検索し、パケットを送信する。以下、ユニキャストの経路検索について簡単に説明する。
【０００４】
ルーティングテーブルは、宛先ＩＰアドレスに対応するサブネットワークアドレスとサブネットマスク長および、上記の経路情報から構成される情報群を複数保持している。以下では、これらの情報群をエントリと呼ぶ。ここでサブネットワークとは、例えば宛先の企業網の様な端末の部分集合を示し、サブネットワークアドレスは部分集合のＩＰアドレスをアドレス情報として結合したアドレス群である。また、サブネットマスク長はＩＰアドレスのうち上位何ビットが上記のサブネットワークの識別子であるかを示す値である。ルータは、受信パケットの宛先ＩＰアドレスにエントリ内のサブネットマスク長だけ上位ビットから有効なマスクをかけたものとエントリのサブネットワークアドレスを比較して、一致するエントリの経路情報を検索結果とする。このようにサブネットワーク単位でエントリを構成することによりルーティングテーブルのエントリ数を大幅に縮小し、検索処理の効率化を図っている。複数のエントリに一致した場合は、サブネットマスク長が最長のエントリの経路情報を検索結果とする。以下では、この検索方式を最長一致検索と呼ぶ。
【０００５】
ある端末から特定の複数の端末にパケットを送信するマルチキャスト通信の場合、ルーティングテーブルの各エントリは、送信元サブネットアドレスとアドレスマスクとマルチキャストグループアドレス、および経路情報から構成される。マルチキャスト・グループアドレスとは、送信元がパケットを送信すべき複数の宛先の集合(以下、マルチキャストグループと呼ぶ。)に対して割り当てられる識別子である。ルータは、受信パケットのヘッダ内の送信元ＩＰアドレスと受信パケットのヘッダ内の宛先ＩＰアドレス部に入っているマルチキャスト・グループアドレスをキーにして、ルーティングテーブルを検索する。マルチキャストの場合、検索の結果一致したエントリの経路情報は複数の送信ポート番号から構成される。ルータはこの送信ポート番号に従い、受信パケットをコピー処理して、上記特定のマルチキャストグループ向けに出力する。これらの検索処理やコピー処理の負荷が重く、マルチキャスト通信の性能が低いと、マルチキャストパケットを転送処理するルータ全体の性能低下の要因となってしまう。このため、通常のユニキャストパケット中継処理と同様に高速化が要求されている。
【０００６】
ルータの負荷分散処理方式による高速化に関しては、例えば特開平６−１９７１１１号公報（以下「従来技術１」という。）に言及がある。従来技術１では、負荷分散処理方式により、高速中継可能なルータを実現することを目的としている。パケット中継を行うパケット中継モジュールがバスにより複数接続され、各々が同じくバスに接続された管理部からのルーティングテーブル情報に基づいてパケット中継機能を行う。パケット中継モジュールの増設により、性能向上ができる。さらに、従来技術１のパケット中継モジュールは、受信パケットのヘッダを抽出し、パケット転送先の検索処理を行うルーティング処理部と、受信パケットをメモリに格納し、上記解析結果に基づいて対応する他のパケット中継モジュールに受信パケットを転送する転送処理部を備え、別々の処理部で機能分担処理させることでパケット中継処理の高速化を図っている。しかし、従来技術１では、マルチキャストパケットの中継処理の高速化に関しては記載がない。
【０００７】
ルータにおけるマルチキャストパケットの宛先の検索（以下、マルチキャスト経路検索と呼ぶ）に関しては、例えば、(以下「従来技術２」という。)に記載されている。従来技術２では、ルーティングテーブル検索をハッシュ検索方式を用いることにより高速化している。ルーティングテーブル情報をそのまま検索すると、対象となる宛先ＩＰアドレスが増加しテーブルのエントリが増加するに従って、検索処理にかかる検索時間が著しく増加してしまう。従来技術２は、ハッシュ値を計算するためのキーとして受信パケット内の送信元ＩＰアドレスを使用しており、ハッシュ値が等しい宛先ＩＰアドレスに対するエントリをグループ化したルーティングテーブル群を備える。
【０００８】
マルチキャストパケット受信時には、ルータ内部の経路検索処理部は、受信パケットの送信元ＩＰアドレスからハッシュ値を計算し、該ハッシュ値に対応する上記ルーティングテーブルを検索する。ハッシュ値に従ってルーティングテーブルの検索範囲を限定することで経路検索の高速化を図っている。
【０００９】
一方、経路検索方式としてRadishアルゴリズムが知られている。Radishアルゴリズムに関しては、例えば"A technical memo of WIDE project, Kazuhiko Yamamoto, Akira Kato and Akira Watanabe,Radish−A Simple Table Structure for CIDR"（以下「従来技術３」という。）に記載されている。
【００１０】
このRadish方式のルーティングテーブルは、エントリを２分木構造に構成し、検索を高速化している。具体的には、ＩＰアドレス形式の最上位ビットをルート(木構造の根)側とする左右にポインタを持つ複数の頂点(ノード)をポインタでつないだ２分木構造の各ノードにエントリを割り付けて構成している。この２分木構造を検索する際には、受信パケットの宛先ＩＰアドレスを上位ビットから１ビットづつ検査し、検査されたビットの値(０または１)に従って各ノードの左右のどちらかのポインタを選択して次のノードに移動する。このような検索により目的のエントリが割り付けられたノードにたどり着くことができる。
【００１１】
従来技術３は、宛先ＩＰアドレスを１ビットずつ検査して２分木を辿るため、ルーティングテーブルのエントリが多くなっても、高々宛先ＩＰアドレスのビット数回の検査を行う(２分木ノードを辿る)ことで検索を終了することができる。
【００１２】
上記のユニキャストの経路検索の説明で述べた、マスク長の異なる複数のエントリにマッチする場合、従来技術３のRadish方式のルーティングテーブルの検索においては、木を辿る途中で複数個のエントリにマッチすることになる。エントリがマッチする度にそのエントリ内の経路情報の候補を保持しておき、新たにエントリにマッチした場合には、以前の候補を新しい候補に更新してゆくことで最長一致検索仕様を満たすことができる。
【００１３】
また、従来技術３のRadish方式を適用したユニキャスト経路検索を高速に行う技術として、「ＩＰルーチングテーブルのハードウェアによる高速検索方式」  1998年電子情報通信学会通信ソサイエティ大会（以下「従来技術４」という。）がある。従来技術４は次ノード選択回路、ネットワークアドレス比較回路、検索終了判定回路からなる。ここでネットワークアドレス比較回路は、Radish方式で構成した２分木から不要な枝を取り除いた場合、ノード自体が保持するネットワークアドレスと、受信パケットの宛先ＩＰアドレスにノードが保持するマスクをかけたものを比較することによって、削除された枝において検査されるべきビット(１または複数の連続したビット)の値を一度に検査するための回路であり、この比較の結果が一致の場合は正しいノードに到達したことを意味し、不一致の場合は正しくないノードに到達したことを意味する。
【００１４】
従来技術４では、次ノードの選択と上記で説明したネットワークアドレス比較処理を並列処理し、検索処理の高速化を図っている。
【００１５】
また、Radish方式と同様なPatricia Trie検索アルゴリズムによるユニキャスト経路検索を高速に行う技術として、「高速ＩＰアドレス解決Ｈ／Ｗエンジンの開発」  1998年電子情報通信学会通信ソサイエティ大会（以下「従来技術５」という。）がある。従来技術５も従来技術４と同様にして木構造の検索の各処理を並列化して高速化を図っている。
【００１６】
従来技術５のPatricia Trie検索アルゴリズムによるユニキャスト経路検索をさらに高速化する技術として、「マルチウェイ化ツリーによるＩＰルーチングテーブルの高速検索方式」  1998年電子情報通信学会通信ソサイエティ大会(従来技術６)がある。従来技術６ではPatricia Trieアルゴリズムによる２分木構造を２のＮ乗分木に構成することにより、高速化を図る旨が記載されている。
【００１７】
また、上記のユニキャスト経路検索において最長一致検索を高速に行う技術として、特開平１０−２２２５３５号公報（以下「従来技術７」という。）がある。従来技術７では、従来技術３のRadish方式とは異なる方法で２分木を構成し、その２分木を検索するハードウェアで構成されたデータ検索回路を用いて最長一致検索を高速に行っている。従来技術７の２分木の具体的な検索方法は、受信パケットの宛先ＩＰアドレスにノード内に保持されているサブネットマスクをかけたものと、ノードのサブネットワークアドレスを比較し、比較の結果一致すればこのノードの経路情報を検索結果として検索を終了し、不一致の場合は、マスクされた宛先アドレスとノードのサブネットワークアドレスを０以上の整数とみなして大小比較を行い、その大小に従って２分木の左右の枝を辿るというものである。この際、マスク長が長いエントリから順に２分木の上部に配置しておくと、その順に検索が行われるため、最長一致検索が実現できる旨が記載されている。なお、上記では、マスク長は上位何ビットがサブネットワークアドレスとして有効かを示す値である、という定義に従って従来技術７の内容を説明したが、従来技術７の明細書中では、マスク長を、ＩＰアドレスのサブネットワークアドレス部分ではない下位のビット数の長さとして定義しており、また、最長一致検索方式をベストマッチ方式と呼んでおり、上記ベストマッチ方式は、マスク長が最短のものを検索結果として採用する。
【００１８】
【発明が解決しようとする課題】
現在、ＩＰマルチキャスト通信は、インターネット上に仮想的に構築されたマルチキャストネットワークにおいて限定的に利用されているにすぎない。そのネットワーク規模もそれほど大きくなく、マルチキャスト通信の検索処理や転送処理は、ルータの転送性能劣化の原因にはなっていない。しかし、今後、インターネットにおけるマルチキャスト機能を利用したアプリケーションが広く普及すると、それに伴い、ルータが保持するマルチキャストルーティングテーブルのエントリ数が多くなる。従って、ルーティングテーブルの検索処理の高速化をエントリ数の多い条件下で実現することが求められている。
【００１９】
従来技術２ではハッシュ方式のマルチキャスト経路検索方式が記載されているが、ハッシュ方式の場合、ハッシュ値の算出法はエントリの数にはよらず一定であり、エントリの増加に応じて柔軟にルーティングテーブル群の数を増やすことができない。従って、エントリが増加した場合、分割されるルーティングテーブル自体が長くなり、平均検索時間が長くなるという問題がある。
【００２０】
この点、上述のRadishアルゴリズムを用いてユニキャストの経路検索を行う方法によれば、ハッシュ方式に比べて、ルーティングテーブルのエントリ数が増大しても、検索処理時間が増大しないという利点がある。
【００２１】
しかし、従来技術３乃至従来技術５には、Radishアルゴリズム(あるいはPatricia Trieアルゴリズム)を用いたマルチキャストの経路検索に関する記載はない。
【００２２】
また、従来技術６では、２分木構造を２のＮ乗分木に構成することにより、最大検索時間を１／Ｎに短縮する旨が記載されているが、マルチキャスト経路検索に関しては言及していない。
【００２３】
また、従来技術７にもマルチキャストの経路検索を高速化する方式については言及されていない。さらに、従来技術３の２分木の構造が、登録されるエントリによって一意に決定し、その最大検索時間は検索に用いるキーのビット数によって決まるのに対し、従来技術７の２分木の構造は、その作り方によっては、ノードが一方向に長くつながる木ができてしまい、平均検索時間が長くなる場合がある。このような木が構成されるのを防ぐには、２分木が均等に広がるように構成するアルゴリズムが必要であるが、そのアルゴリズムについては述べられていない。また、従来技術７の２分木構造を構成する際、マスク長が長いエントリから順に２分木の上部に配置しておくと、その順に検索が行われるため、最長一致検索処理が実現できると述べているが、マスク長が異なるノードのつなぎ方に関しては詳細は述べられていない。また、従来技術３のように検査ビットの値に従って２分木の左右の枝を辿るのではなく、ノードにおける大小比較の結果、その大小に従って２分木の左右の枝を辿るため、２のｐ乗分木方式を実現することができない。
【００２４】
そこで、本発明の第１の目的は、マルチキャストパケットの中継処理に関し、マルチキャストパケット経路検索処理の高速化の手段を提案することである。
【００２５】
また、本発明の第２の目的は、Radishアルゴリズムによる２分木検索方式をマルチキャスト経路検索に適用する手段を提案することである。
【００２６】
また、本発明の第３の目的は、検索のキーのビット数が大きい場合でも、ノードを辿る回数がビット数より少なく、最大検索時間が少ない経路検索方式を、マルチキャスト経路検索方式に適用する手段を提案することである。
【００２７】
本発明の第４の目的は、Radishアルゴリズムによるマルチキャストルーティングテーブルの２分木検索方式に従って経路検索処理を高速に行う回路の構成を提案することである。
【００２８】
【課題を解決するための手段】
上記の目的を達成するために、本発明では、以下に述べる方式および手段を持つ。
【００２９】
パケットの送信元の端末のＩＰアドレス(送信元ＩＰアドレス)と、パケットを送信すべき端末が属するマルチキャスト・グループのグループアドレス(宛先マルチキャスト・グループアドレス)とを検索のキーとして用いるマルチキャスト経路検索において、送信元ＩＰアドレスと宛先マルチキャスト・グループアドレスを連結して一つの経路アドレスとして定義し、この経路アドレスのビットパターンに従い、マルチキャストルーティングテーブルを２分木に構成し、受信したマルチキャストパケットの送信元ＩＰアドレスと宛先マルチキャスト・グループアドレスとを連結した経路アドレスの上位ビットから１ビットづつ検査し、上記検査ビットの値によって２分木構造をもつ検索木を検索する。
【００３０】
また、上記の経路アドレスに関し、送信元ＩＰアドレスと宛先マルチキャスト・グループアドレスの連結順を、宛先マルチキャスト・グループアドレス、送信元ＩＰアドレスの順にして経路アドレスを定義し、この経路アドレスのビットパターンに従い、マルチキャストルーティングテーブルを２分木に構成する。
【００３１】
また、２分木方式の検索木を構成する各ノードを、２分木ノードから４分木、８分木、あるいは一般に２のｐ乗と、枝別れの数を２のべき乗で増やすことで、マルチキャストルーティングテーブルを２のｐ乗分木構造に構成し、受信したマルチキャストパケットの宛先マルチキャスト・グループアドレスと送信元ＩＰアドレスをこの順に連結した経路アドレスを、一つのノードで１ビットではなく、連続する２ビット、３ビット、あるいは一般にｐビットを同時に検査し、上記連続するビットの値によって２のｐ乗分木構造を持つマルチキャストルーティングテーブルを検索する。
【００３２】
また、上記の経路アドレスとして、マルチキャスト・グループアドレス自体ではなく、マルチキャスト・グループアドレスの下位２８ビットのマルチキャスト・グループＩＤと送信元ＩＰアドレスをこの順に連結したものを採用し、この経路アドレスのビットパターンに従い、マルチキャストルーティングテーブルを２分木あるいは２のｐ乗分木に構成する。
【００３３】
また、検索木を構成するメモリ量を減らすために、２のｐ乗分木を構成する際、一つの２分木ノードと、その直下につながる(ｐ−１)段分の合計(２のｐ乗−１)個分の２分木ノードを一つの２のｐ乗分木ノードにまとめ、まとめられる最下段の２の(ｐ−１)乗個の２分木ノードに、それより上段のノードに割り付けられていたエントリデータを埋め込むことにより、２のｐ乗分木ノードを２分木ノードを２の(ｐ−１)乗個分併せた形で構成するようにし、さらに、２分木を複数個併せるときに、共通なノードデータの要素を一つだけもつようにする。
【００３４】
また、２分木ノードを２のｐ乗分木にまとめる際、２のｐ乗分木ノードのメモリ量削減と、各２のｐ乗分木ノードのメモリ量の統一のために、送信ポート情報を検索木のノードから分離して記憶手段の別領域に格納し、検索木のノードには上記送信ポート情報の格納領域へのポインタを保持することで、エントリが割り当てられている２分木ノードと、エントリが割り当てられていない２分木ノードのデータ量を同じにし、これらの２分木ノードをまとめて２のｐ乗分木ノードを構成する。
【００３５】
また、経路アドレスの検査すべきビット位置を示すマスク長に関し、各２のｐ乗分木ノードにそのノード自身のマスク長を格納するのではなく、そのノードの直下につながるノードのマスク長と格納することにより、経路検索処理を行うために検索木データが格納されている記憶手段からノードデータを読込む際、ノードデータ全てを読込むのではなく、直前に読込んだノードに格納されているマスク長を用いて、ノードデータのうち必要な部分のみを選択して読込む。
【００３６】
また、各ノードの先頭に、そのノードにエントリが割り付けられているか否かを示すフラグを設け、最初に、このフラクを読込み、エントリが割り付けられていないノードでは、経路情報を読込まないようにする。
【００３７】
また、経路アドレスの上位ｍビットに対応する２のｍ乗個の２のｐ乗分木ノードを、記憶手段上の決まった位置に展開し、展開されたそれぞれのノードを、経路アドレスの第０ビットから第(ｍ−１)ビットまでが取りうる値に１対１に対応させ、検索時には、経路アドレスの第０ビットから第(ｍ−１)ビットの値に従って、該ノードを選択する。
【００３８】
また、宛先アドレスと送信元アドレスをこの順に連結して経路アドレスとし、上記経路アドレスの上位ｍビットに対応する２のｍ乗個の２のｐ乗分木ノードを決まった位置に格納し、それ以降の木は２のｐ乗分木構造に構成して格納する記憶手段を持ち、経路検索時には、受信したマルチキャストパケットの宛先アドレスと送信元アドレスをこの順に連結した経路アドレスの第０ビットから第(ｍ−１)ビットの値に従って、メモリ上の決まった位置に展開されたノードの一つを選択し、経路アドレスの第ｍビット以降は経路アドレスをｐビットずつ検査して２のｐ乗分木に構成されたマルチキャストルーティングテーブルを検索する回路をもつ。
【００３９】
その他の本願が解決しようとする課題、及びその解決手段は、後述の「発明の実施の形態」の欄、及び本願図面で明らかにされる。
【００４０】
【発明の実施の形態】
以下、本発明の実施例を図面を用いて説明する。
【００４１】
まず、一般的なネットワークの構成およびそのネットワークにおけるパケット中継動作を図２、３、４を用いて説明する。
【００４２】
図２に示したネットワークは、パケットを送受信する端末(Ｔ１１、Ｔ１２、Ｔ２１、Ｔ２２，Ｔ３１、Ｔ３２、Ｔ４１、Ｔ４２、Ｔ５１、Ｔ５２)と、端末を相互に接続するサブネットワーク(ＳＮ１〜ＳＮ５)と、該サブネットワークを相互に接続するルータ(Ｒ１〜Ｒ３)から構成される。また、ルータＲ１はポートＰ１１、Ｐ１２、Ｐ１３を持ち、ルータＲ２はポートＰ２１、Ｐ２２、Ｐ２３、Ｐ２４を持ち、ルータＲ３はポートＰ３１、Ｐ３２、Ｐ３４、Ｐ３５を持つ。各端末には識別子としてアドレスが割り当てられており、例えばＩＰネットワーク上の各端末には３２ビットのＩＰアドレスが割り当てられている。このＩＰアドレスについて図３(ａ)を用いて説明する。図３(ａ)に示したＩＰアドレス(１)は、サブネットワークアドレス(２)とホストアドレス(３)から構成される。
【００４３】
サブネットワークアドレスは、サブネットワークの識別子であり、ホストアドレスはサブネットワーク内の端末の識別子である。サブネットワークアドレスのビット数はサブネットマスク長で示されており、このサブネットマスク長だけ上位ビットから有効なマスク(サブネットマスク)とＩＰアドレスのビットごとの論理積をとることにより、ＩＰアドレスからサブネットワークアドレスを得ることができる。
【００４４】
次に、ある端末から特定の一つの端末にパケットを送信するユニキャスト通信について、図２を用いてパケット中継動作を説明する。一例として、端末Ｔ１１から端末Ｔ２２へユニキャストパケットを送信する場合について説明する。送信されるパケットのヘッダフォーマットを図３(ｃ)に示す。図３(ｃ)の送信元ＩＰアドレスフィールド(７)には送信元端末Ｔ１１のＩＰアドレスが格納され、宛先ＩＰアドレスフィールド(８)には宛先端末Ｔ２２のＩＰアドレスが格納される。端末Ｔ１１からのユニキャストパケットを受信したルータＲ１は、パケットヘッダ内の宛先ＩＰアドレスフィールドを検査し、宛先端末Ｔ２２がサブネットワークＳＮ２上にあり、かつ、サブネットワークＳＮ２がルータＲ２経由で接続されていることを認識し、パケットを送信すべきルータＲ２のＩＰアドレス(ネクストホップＩＰアドレスと呼ぶ)および送信すべきポートＰ１２を決定し、パケットを出力する。ルータＲ１からのユニキャストパケットを受信したルータＲ２は、パケットヘッダ内の宛先ＩＰアドレスフィールドを検査し、宛先端末Ｔ２２がサブネットワークＳＮ２上にあり、かつ、サブネットワークＳＮ２がルータＲ２に直接接続されていることを認識し、ネクストホップＩＰアドレス(今の場合、端末２２のＩＰアドレス)および送信すべきポートＰ２２を決定し、パケットを出力する。
【００４５】
次に、ルータの構成およびルータのユニキャストパケットの中継動作を図４を用いて説明する。図４のルータ１０は、入力ポート１１-i(＝１〜Ｎ)、出力ポート１２-i(＝１〜Ｎ)、ルーティング処理部１３-i(＝１〜Ｎ)、スイッチ１４、通信制御部１５-i(＝１〜Ｎ)、管理部１６から構成される。上記で説明したユニキャストパケットが入力ポート１１-iから入力されると、ルーティング処理部１３-iがパケットのヘッダ内の宛先ＩＰアドレスをキーにしてユニキャストルーティングテーブルを検索する。この検索により、ネクストホップＩＰアドレスと、出力すべき出力ポート１２-iの番号(送信ポート番号)を決定し、上記ネクストホップＩＰアドレスと送信ポート番号をパケットに付加してスイッチ１４に送出する。スイッチ１４は上記送信ポート番号に対応する出力ポート１２-iを保持する通信制御部１５-iにパケットをスイッチングする。スイッチングされたパケットを受信した通信制御部１５-iは、パケットに付加されているネクストホップＩＰアドレスに対応するデータリンク層のＭＡＣ(Media Access Control)アドレスを対応テーブルに従って決定してパケットの宛先ＭＡＣアドレスとして付加して、送信ポート番号に対応する出力ポート１２-iにパケットを送出する。
【００４６】
なお、上記のユニキャストルーティングテーブルは、管理部１６が他のルータと接続情報をやり取りして作成し、各ルーティング処理部１３-iに配布する。また、管理部１６は、他のルータおよび端末とデータリンク層の情報のやり取りをし、ネクストホップＩＰアドレスと、そのＩＰアドレスを持つルータおよび端末のＭＡＣアドレスの対応テーブルを作成して各通信制御部１５-iに配布する。
【００４７】
次に、ある端末から特定の複数の端末にパケットを送信するマルチキャスト通信について、図２を用いてパケット中継動作を説明する。一例として、端末Ｔ１１からある特定のマルチキャストグループに属する端末(Ｔ２１、Ｔ３１、Ｔ３２、Ｔ４１、Ｔ４２、Ｔ５１)へマルチキャストパケットを送信する場合について説明する。マルチキャストグループは、クラスＤのＩＰアドレス(マルチキャスト・グループアドレス)によって識別される。このクラスＤのＩＰアドレスの構造を図３(ｂ)に示す。クラスＤのＩＰアドレス(４)は、クラスＤであることを示す"１１１０"という上位４ビット(５)と２８ビットのマルチキャスト・グループＩＤ(以下、ＧＩＤ)(６)から構成される。上記のマルチキャスト・グループアドレスによって識別されるマルチキャストグループは、複数のサブネットワークにまたがることが可能である。また、グループに属する端末のメンバー構成は動的で、端末は自由にマルチキャストグループに参加、離脱することができる。
【００４８】
端末Ｔ１１から、あるマルチキャストグループ宛に送信されたマルチキャストパケットのヘッダ内の送信元ＩＰアドレスフィールド(図３(ｃ)の７)には送信元端末Ｔ１１のＩＰアドレスが格納され、宛先ＩＰアドレスフィールド(図３(ｃ)の８)には、ユニキャストパケットの場合とは異なり、宛先のマルチキャスト・グループアドレスが格納される。端末Ｔ１１からのマルチキャストパケットを受信したルータＲ１は、ユニキャストパケットの場合とは異なり、パケットヘッダ内の送信元ＩＰアドレスフィールドと宛先ＩＰアドレスフィールドの２つのフィールドを検査し、このマルチキャストパケットの送信元端末Ｔ１１がサブネットワークＳＮ１上にあることを認識し、さらに、このサブネットワークＳＮ１から、宛先マルチキャストアドレスに属する端末の全てにパケットを送信するためにルータＲ１がパケットを送信すべき送信ポートＰ１２、Ｐ１３を決定し、上記ポートにパケットをコピーして出力する。ルータＲ１からのマルチキャストパケットを受信したルータＲ２は、Ｒ１と同様な検査を行い、このマルチキャストパケットの送信元端末Ｔ１１がサブネットワークＳＮ１上にあることを認識し、さらに、宛先マルチキャストアドレスに属する端末が存在するサブネットワークＳＮ２、ＳＮ３にパケットを送信するためにルータＲ２がパケットを送信すべき送信ポートＰ２２、Ｐ２３を決定し、上記ポートにパケットをコピーして出力する。ルータＲ３も同様にしてＲ１から受信したパケットを送信すべきポートＰ３４、Ｐ３５を決定し、上記ポートにパケットをコピーして出力する。
【００４９】
次に、ルータのマルチキャストパケットの中継動作を図４を用いて説明する。上記で説明したマルチキャストパケットが入力ポート１１-iから入力されると、ルーティング処理部１３-iがパケットのヘッダ内の送信元ＩＰアドレスと宛先ＩＰアドレス(宛先マルチキャストアドレス)をキーにしてマルチキャストルーティングテーブルを検索する。この検索により、出力すべき１つまたは複数の出力ポート１２-iの番号(送信ポート番号)を決定し、受信したパケットをコピーし、各送信ポート番号をパケットに付加してスイッチ１４に送出する。スイッチ１４は上記送信ポート番号に対応する出力ポート１２-iを保持する通信制御部１５-iにパケットをスイッチングする。スイッチングされたパケットを受信した通信制御部１５-iは、ユニキャストパケットの場合とは異なり、マルチキャストパケットのヘッダ内の宛先マルチキャストアドレスを用いてデータリンク層のマルチキャスト用ＭＡＣアドレスを生成し、パケットの宛先ＭＡＣアドレスとして付加して、送信ポート番号に対応する出力ポート１２-iにパケットを送出する。
【００５０】
なお、上記のマルチキャストルーティングテーブルは、ユニキャストルーティングテーブルと同様にして管理部１６が他のルータと接続情報をやり取りして作成し、各ルーティング処理部１３-iに配布する。
【００５１】
次に、本発明の一実施例として、ルータの全体構成例を図１を用いて説明する。
【００５２】
まず、ルータ７００の構成を図１を用いて説明する。５０５はスイッチであり、図４のスイッチ１４に対応する。上記スイッチ５０５に、装置全体の管理機能と経路情報の収集・分配等の機能をもつ管理部６０１が接続されている。管理部６０１は図４の管理部１６に対応する。また、スイッチ５０５には、高速にパケット中継処理を行う機能を有するパケット処理部６００を複数接続することができる。パケット処理部６００は、図４のルーティング処理部１３−ｉに対応する。管理部６０１は、それぞれのパケット処理部６００にルーティングテーブルを配布し、それぞれのパケット処理部６００が上記ルーティングテーブルに基づいてパケット中継処理を行うことによりルータの機能を実現する。
【００５３】
さらに、各パケット処理部６００には、ネットワークを接続するための通信ポートを備える通信制御部５０１、６０２、６０３(図４の通信制御部１５-iに対応)が接続される。通信制御部は、各種類のネットワークに接続することができる。また、そのネットワークの通信速度に応じて、高速通信(例えば、図２の５００)ならば１ポート、低速通信(例えば、図２の６０４、６０５)ならば複数ポートを設け、１つまたは複数のネットワークと接続することができる。
【００５４】
次に、上記のパケット処理部６００の構成について、図１を用いて説明する。図１において、パケット処理部６００は、パケット転送処理を行う転送処理部５０４と、パケットを格納するパケットバッファを備えるメモリ５０３と、メモリ５０３に格納されたパケットのヘッダ情報を用いて経路検索を行う経路検索処理部４００と、転送処理部５０４および通信制御部５０１を制御する制御回路５０２とを有する。経路検索処理部４００は、ルーティングテーブルを格納するメモリ３００と、そのルーティングテーブルを検索し、検索結果を転送処理部５０４へ出力する経路検索処理回路２００から構成される。
【００５５】
次に、パケット処理部６００における、マルチキャストパケットの中継処理の動作を説明する。なお、パケット中継処理を行う前に、管理部６０１が、スイッチ５０５に接続している全パケット処理部６００に、それぞれのマルチキャストルーティングテーブルを配布しており、各パケット処理部６００はメモリ３００にルーティングテーブルを格納している状態とする。通信制御部５０１がネットワーク５００から受信したマルチキャストパケットをメモリ５０３へ転送し格納する。転送処理部５０４はメモリ５０３に格納されたパケットデータの内、パケットヘッダ情報を抽出して経路検索処理部４００へ転送する。経路検索処理回路２００は、受信パケットのヘッダ内の送信元アドレスと宛先マルチキャスト・グループアドレスを用いてメモリ３００内に格納されているマルチキャストルーティングテーブルの検索を行い、検索結果として、パケットを送信すべきＮ個(Ｎは１以上の整数)の送信ポート番号を転送処理部５０４へ転送する。
【００５６】
上記の検索結果を受信した転送処理部５０４は、先にメモリ５０３に格納されているパケットに対してパケットヘッダの書換などの処理を施し、パケットに上記Ｎ個の送信ポートの内の１つの番号を付加してスイッチ５０５に転送する。転送処理部５０４は上記の処理をＮ回繰り返し、１つの受信パケットに対する転送処理を終了する。また、送信ポート番号が自パケット処理部に接続されている通信制御部のポート番号である場合は、自パケット処理部に接続されている通信制御部にパケットを送信する。
【００５７】
スイッチ５０５は転送処理部５０４により転送されたパケットを、付加されている送信ポート番号に従い、各パケット処理部にスイッチングする。上記スイッチングされたパケットを受信したパケット処理部６００は、上記パケットを通信制御部(５０１、６０２、６０３)へ転送する。通信制御部は、上記パケットのヘッダ内の宛先マルチキャストアドレスからマルチキャスト用ＭＡＣアドレスを生成し、宛先ＭＡＣアドレスとしてパケットに付加して各ネットワークに送信する。
【００５８】
本発明は、上記の経路検索処理部４００の高速化に関するものである。以下では、この経路検索処理部４００に関し、まず、方式１として、マルチキャストルーティングテーブルを２分木に構成し、その２分木構造を検索する検索方式(以下、２分木検索方式と呼ぶ)について説明する。方式２として、方式１を改良し、さらに検索を高速に行うために、マルチキャストルーティングテーブルを２のｐ乗分木に構成し、その２のｐ乗分木構造を検索する検索方式(以下、２のｐ乗分木検索方式と呼ぶ)について説明する。また、その方式２の説明の中で、マスク長ｍビットのノードをメモリ上に展開して方式１、２のノードを渡る回数を削減する方式(方式３)について説明する。最後に、本発明の一実施例として、方式２および３の方式を適用した経路検索処理を実現するハードウェア構成について説明する。
【００５９】
まず、方式１の２分木検索方式について説明する。
【００６０】
従来の技術で説明したように、マルチキャスト経路検索を行う際、受信パケットのヘッダ内の送信元ＩＰアドレスと、宛先マルチキャスト・グループアドレスを検索のキーとしてマルチキャストルーティングテーブルを検索する。すなわち、この２つの情報の組み合わせにより、そのマルチキャストパケットの送信元から宛先までの経路が識別される。
【００６１】
従って、送信元ＩＰアドレスとマルチキャスト・グループアドレスを連結して、これを経路アドレスとして定義し、この経路アドレスと経路情報の組をエントリとしてマルチキャストルーティングテーブルを構成することにより、この経路アドレスをキーとして、マルチキャストルーティングテーブルを検索することができる。
【００６２】
また、上記の２つのアドレスのうち、マルチキャスト・グループアドレスに関しては、マルチキャスト・グループ一つに対して一つのアドレスが割り当てられているので、ルーティングテーブル検索時は、エントリに保持されたマルチキャスト・グループアドレスとの一致比較を行えばよい。
【００６３】
しかし、上記の２つのアドレスのうち、送信元ＩＰアドレスに関しては、受信パケットの送信元ＩＰアドレスに、エントリに保持されているサブネットマスク長だけ上位ビットから有効なマスクをかけたものとエントリに保持されている送信元サブネットワークアドレスに一致するエントリの経路情報を検索結果とするが、この場合、ユニキャスト経路検索と同様に最長一致検索を行う必要がある。
【００６４】
以上のことから、送信元ＩＰアドレスとマルチキャスト・グループアドレスの連結順を、マルチキャスト・グループアドレス、送信元ＩＰアドレスの順にして、これを経路アドレスとして定義し、この経路アドレスのビットパターンに従ってマルチキャストルーティングテーブルを２分木構造に構成することにより、従来技術３に述べられているRadish方式を用いたユニキャスト経路検索方式と同様にして、経路アドレスに関して最長一致検索を行うことができる。この場合、経路アドレスの定義から、マルチキャスト・グループアドレスについては一致比較、送信元ＩＰアドレスに関しては最長一致検索を行うことできる。
【００６５】
図５に２分木で構成されたマルチキャストルーティングテーブルを検索する際に用いる経路アドレスを示す。なお、この経路アドレスは後述する２のｐ乗分木検索方式にも採用する。図５(ａ)の経路アドレス３２は、マルチキャスト・グループアドレス(３０)と送信元ＩＰアドレス(３１)とを連結したものであり、ビット数は６４ビットである。図５(ｂ)の経路アドレス３３は、マルチキャスト・グループアドレス(３０)から"１１１０"というＩＰアドレスのクラスＤを示す上位４ビットの値を除いたマルチキャスト・グループＩＤ(３４)と、送信元ＩＰアドレス(３１)とを連結したものであり、ビット数は６０ビットである。木構造を構成するための値(今の場合は検索アドレス)のビット数が少ない方が木の構造が浅くなり、検索時に辿る最大ノード数が減るため、以下では、ビット数の少ない図５(ｂ)の経路アドレス３３を採用して説明する。
【００６６】
次に、上記の経路アドレスを用いてマルチキャストルーティングテーブルを２分木に構成する方法について説明する。木構造の考え方は経路アドレスのビット数には依存しないので、簡単のため、マルチキャスト・グループＩＤは１ビット、送信元ＩＰアドレスは２ビットと仮定して説明する。この場合経路アドレスは３ビットとなる。
【００６７】
図６に２分木の構造の例を示す。図６に示すように、各ノードは、経路アドレスモａａａモと、経路アドレスマスク長ｎ、および、そのノードの下につく二つのノードへのポインタを持つ。ここで、経路アドレスマスク長とは、そのノードが持つ経路アドレスの上位何ビットが有効であるかを示す値であり、また、そのノードでの受信パケットの経路アドレスの検査ビット位置も示す。また、経路アドレスと経路アドレスマスクの組を表記法モａａａ：ｎモで表す。この表記法により、マスク付き経路アドレスを表すことにする。
【００６８】
各ノードを木の上から順に、経路アドレスマスク長０ビット、１ビット、２ビット、３ビットのノードと呼ぶ。
【００６９】
経路アドレスマスク長０ビットのノード（４０）では、経路アドレスマスク長の値で示されている経路アドレスの第０ビットを検査し、その値が０か１かに従い左/右のポインタを辿ることにより経路アドレスマスク長１ビットのノード（４１、４２）に移り、経路アドレスマスク長１ビットのノードでは、経路アドレスの第１ビットが０か１かに従い左/右のポインタを辿ることにより経路アドレスマスク長２ビットのノード（４３、４４、４５、４６）に移り、経路アドレスマスク長２ビットのノードでは、経路アドレスの第２ビットが０か１かに従い左/右のポインタを辿ることにより経路アドレスマスク長３ビットのノード（４７、４８、４９、５０、５１、５２、５３、５４）に移る。
【００７０】
検索したい経路アドレスについて、この木の経路アドレスマスク長０ビットのノード（４０）から順に、各ビットが０か１かに従いポインタを辿った場合、経路アドレスマスク長０ビットのノードは経路アドレスがどの値をとる場合にも通過し、経路アドレスマスク長１ビットのノード（４１、４２）は左から順に経路アドレスの各ビットが０ｘｘ、１ｘｘの場合に通過し、経路アドレスマスク長２ビットのノード（４３、４４、４５、４６）は左から順に経路アドレスの各ビットが００ｘ、０１ｘ、１０ｘ、１１ｘの場合に通過し、経路アドレスマスク長３ビットのノード（４７、４８、４９、５０、５１、５２、５３、５４）は左から順に経路アドレスの各ビットが０００、００１、０１０、０１１、１００、１０１、１１０、１１１の場合に通過する。ここで、ｘは、そのビット値が０または１のどちらでも良いことを示す。
【００７１】
従って、経路アドレスマスク長０ビットのノード（４０）は、経路アドレスがマスク付き経路アドレス ０００：０に属する場合に通過し、経路アドレスマスク長１ビットのノード（４１、４２）は、経路アドレスがそれぞれマスク付き経路アドレス０００：１、１００：１に属する場合に通過し、経路アドレスマスク長2ビットのノード（４３、４４、４５、４６）は、経路アドレスがそれぞれマスク付き経路アドレス０００：２、０１０：２、 １００：２、１１０：２に属する場合に通過し、経路アドレスマスク長3ビットのノード(４７、４８、４９、５０、５１、５２、５３、５４)は、経路アドレスがそれぞれマスク付き経路アドレス０００：３、００１：３、...、１１１：３に属する場合に通過する。
【００７２】
上記の通り、この木の各ノードは、経路アドレスと経路アドレスマスク長が異なる全マスク付き経路アドレスに１対１に対応している。
【００７３】
上記の２分木において、図７に示すマルチキャストルーティングテーブルの各エントリに対応するノード４０、４８、４４、４２、５３に該エントリを割り付ける。具体的には、図１２を用いて後述するように、ノードのデータ構造内にエントリが割り付けられているか否かを示すフラグを設け、エントリが割り付けられたノード内の上記フラグの値を１に設定し、かつ送信ポート情報あるいは送信ポート情報へのポインタをノード内に格納する。本明細書では、ノードに＊を付記することにより、ノードにエントリが割り付けられていることを表すことにする。
【００７４】
受信パケットの経路アドレスが０１１(図６の６０)の場合、この木の上から各ビットが０か１かに従いポインタを辿ると、"＊"が付記されたノード４０、４４が、マスク付きの検索で一致することが分かる。そこで、ルーティングテーブルエントリが複数一致した場合は、送信元ＩＰアドレスに関して最長一致検索を行うことを考慮すると、一致した"＊"付きノード４０、４４の内、上記で定義した経路アドレスマスク長が最も長いノード、すなわち最も末端に近いノード４４に割り付けられたエントリの経路情報を、ルーティングテーブルの検索結果とする。なお、図７のルーティングテーブルの例では、エントリ内の経路情報は省略している。
【００７５】
上記検索方法から分かるように、"＊"が付記されておらず、かつ"＊"付きのノードにたどり着くための途中経路にもなっていないノード４７、４９、５０、５１、５２、５４、４５は木から取り除いても、検索結果には影響しない。むしろ、最下のノードが、"＊"が付記されていていないノードの場合は最下まで移動せずに検索が終了するために効率的である。そこで、"＊"が付記されておらず、かつ"＊"付きのノードにたどり着くための途中経路にもなっていないノードを木から取り除くと図８のようになる。
【００７６】
上記の方法を用い、経路アドレス長が３２ビットと仮定した場合、図９に示す経路テーブルに対応する2分木を構成すると、図１０に示す分岐も"＊"も無いノードの長い列６１ができる。なお、図９のルーティングテーブルの例では、図７と同様にエントリ内の経路情報は省略している。また、図１０の0xNNNNNNNNという表記法は、NNNNNNNNが１６進数表示であることを示す。このように、左右の片方のポインタだけに次のノードがつながり、かつエントリが割り当てられていないノードを取り除くことにより、検索時に辿るノード数を減らすことができる。
【００７７】
図１０の例においては、分岐も"＊"も無いノード列６１を取り除き、直ぐ上のノード６２の分岐方向(図１０では右側)に、取り除かれたノード列６１の直ぐ下のノード６３を付ける。その結果、図１１に示す形となる。このように途中のノード列を取り除くことを、以後、木の縮退と呼ぶ。
【００７８】
次に縮退した２分木の検索法を説明する。
【００７９】
図１１に示す例では、経路アドレスマスク長０ビットのノード６２で第０ビットの検査を行った後、経路アドレスマスク長１５ビットのノード６３に跳ぶので、経路アドレスマスク長１５ビットのノード６３で第１５ビットだけを検査したのでは、途中のビット、即ち第１ビットから第１４ビットが検査できない。そこで、第１ビットから第１５ビットの検査を一回の処理で行う為に、受信パケットの経路アドレスの第１ビットから第１５ビットとノード６３の経路アドレス0x85040000の第１ビットから第１５ビットの一致比較を行う。比較結果が一致すれば正しいノードにたどり着いたこと、即ち、縮退しない木で１ビットづつ比較しても、このノードにたどり着いたことを意味し、一致しなければ、正しくないノードにたどり着いたこと、即ち縮退しない木では、行き先が無いことを意味する。
【００８０】
ここで、図１１に示す例では、第０ビットは、既にテストされ、第０ビットが等しくなる方の分岐が選択されている為、常に一致する。一般に、あるノードにたどり着く毎に、正しいノードにたどり着いたか否かを検査していれば、第０ビットから、そのノードの経路アドレスマスク長までのビットに関しては、受信パケットの経路アドレスと、ノードの経路アドレスとが等しいことが保証されているので、次のノードにたどり着いたときに、前にどのビットまで検査したかに関らず、第０ビットからノードの経路アドレスマスク長までのビットに関して、受信パケットの経路アドレスとノードの経路アドレスとが等しいか否かを調べて良い。
【００８１】
次に、上記で説明した２分木を構成するノードのデータ構造について、図１２を用いて説明する。図１２(ａ)において、ワード１１０、１１１内の次のノードのマスク長０、１は、このノード自身の経路アドレスマスク長ではなく、このノードの直下のノードの経路アドレスマスク長である。このように、自分自身でなく直下のノードのマスク長を設定する理由は高速化のためであり、その説明は図２０を用いて後述する。ワード１１０、１１１内のフラグ０、フラグ１は、このノードがエントリが割り付けられているノードか否か、即ち、図６、８、１０、１１で示した木の例において、このノードが、"＊"が付記されているノードか否かを示すフラグ(以下、エントリ有りフラグと呼ぶ)や、このノードに一致するパケットに関する属性フラグなどが設定されるフィールドである。フラグ０とフラグ１には、同じ値を設定する。これは、ワード１１０とワード１１１の一つだけを読めば良いようにするためであり、このように、ノードの全てを読むのではなく、一部分を読むことによる高速化については図２０を用いて後述する。ワード１１０、１１１内の次のノードへのポインタ０、１は、経路アドレスの、このノードの経路アドレスマスク長で示されるビット位置の値が、それぞれ０、１のときに次に辿るノードへのポインタである。ワード１１２、１１３の経路アドレスは、このノードに対応する経路アドレスであり、例えばワード１１２にはノードの経路アドレスの内、上位２８ビットを設定し、ワード１１３にはノードの経路アドレスの内、下位３２ビットを設定する。
【００８２】
図１２(ａ)では、２分木ノードのデータ構造の中に送信ポート情報１１４を保持する例を示している。図１２(ｂ)では、送信ポート情報１１４を２分木ノード構造から分離し、分離した送信ポート情報へのポインタ１１５を保持する例を示している。送信ポート情報は、受信マルチキャストパケットを転送すべき１つまたは複数の送信ポート番号を示し、ルータのポート数が多い場合は数ワード必要になる。従って、図１２(ａ)のように、２分木ノード構造内に送信ポート情報１１４を保持する場合、エントリが割り付けられている２分木ノードと、エントリが割り付けられていない２分木ノードで、その大きさが大きく異なることになる。このようにノードの大きさが異なると、ノード内の次ノードへのポインタに必要なビット数が多くなることや、そのポインタから実際のメモリのアドレスを計算する処理が複雑になり、特にハードウェア構成が複雑になるという問題が考えられる。
【００８３】
図１２(ｂ)のように送信ポート情報をノードから分離し、ノードにはその送信ポート情報へのポインタ１１５を保持する場合、エントリが割り付けられている／いないに関わらずノードの大きさは一定になり、ハードウェア構成を単純にする利点がある。
【００８４】
次に、方式２の２のｐ乗分木検索方式について説明する。
【００８５】
上記で説明した２分木方式では、一つのノードに２つの分岐先があり１ビットづつ検索していた。検索のキーのビット数は、検索時に辿るノードの数(の最大値)に一致する。したがって、最大の検索時間は(式１)で表される。
【００８６】
(最大検索時間)＝(一つのノードの処理時間)×(検索のキーのビット数)  ・・・  (式１)
すなわち、最大検索時間は検索のキーのビット数に比例する。この最大検索時間をさらに大幅に短縮し、高速化することが求められる。
【００８７】
そこで、以下で説明する２のｐ乗分木方式では、一つのノードに２のｐ乗の分岐先を設け、同時にｐビットづつ検索することにより、従来に比べ、検索時間を１／ｐに短縮するものである。以後、一つのノードに２のｐ乗の分岐先があるノードのことを２のｐ乗分木ノードと呼ぶ。
【００８８】
２のｐ乗分木ノードは、２分木方式で説明した２分木ノードから構成される木を変形することにより作成する。木の変形の方法は、経路アドレスマスク長ｎの２分木ノード一つと、この２分木ノードの下に存在する、経路アドレスマスク長(ｎ＋１)ビットから(ｎ＋ｐ−１)ビットの2分木ノードを、一つの２のp乗分木ノードに対応させるものである。また、以下では、上記のように対応させてまとめた２のｐ乗分木ノードに関し、まとめる前に頂点にあった２分木ノードのマスク長ｎを引き継いで、この２のｐ乗分木ノードのマスク長をｎと定義する。
【００８９】
上記の変形法の例として、２分木から８分木への変形法を図１３に示す。
【００９０】
経路アドレスのビット数が６０ビットの場合で、８分木を構成する場合を考える。この場合、一つの８分木に対応させる２分木ノードの選び方として、マスク長０〜２、３〜５、....、５７〜５９、６０ビットの２分木ノードを、それぞれ一つの８分木ノードとする場合(図１３(ａ))と、マスク長１〜３、４〜６、....、５５〜５７、５８〜６０ビットの２分木ノードを、それぞれ一つの８分木ノードとする場合(図１３(ｂ))と、第２〜４、５〜７、....、５６〜５８、５９〜６０ビットの２分木ノードを、それぞれ一つの８分木ノードとする場合(図１３(ｃ))の３通りがあり、どの区切り方でも、構成可能だが、木全体では、エントリの追加、削除を容易に行えるように、上記３通りのビット位置の区切り方の内、一つを使用する。
【００９１】
上記３通りのビット位置の区切り方の内、最初の区切り方以外では、マスク長が０ビットから始まっていないので最初のビットの検査を別に行う必要がある。この検査には、マスク長ｍビットのノードをメモリ上の決まった位置に展開する方法(以下、方式３と呼ぶ)を使用する。
【００９２】
以下、方式３について説明する。方式３は、２のｐ乗分木構造のマスク長ｍビットのノードを、ノードがある場合も無い場合も区別せず全て予め用意し、メモリ上の決まった位置に展開しておき、経路検索開始時に、受信パケットの経路アドレスの上位ｍビットの値に従って上記の展開されたノードの内の一つを選択してメモリから読み込む。この方式により上位ｍビット分の検索時間を省くことができる。
【００９３】
上記の方式３を適用した例を、図１３(ｂ)、(ｃ)に示した区切り位置の場合について図１４(ａ)、(ｂ)に示す。
【００９４】
図１４(ａ)に示す構成では、マスク長１ビットの８分木ノード９０、９１をメモリ上の決まった位置に並べ、それぞれを、受信パケットの経路アドレスの第０ビットが０か１かに従い選択することにより、最初の第０ビットの検査を行ったことになる。図１４(ｂ)に示す構成では、マスク長２ビットの８分木ノード９２、９３、９４、９５をメモリ上の決まった位置に並べ、それぞれを、受信パケットの経路アドレスの第０〜１ビットの値が００か０１か１０か１１かに従い選択することにより、最初の第０、１ビットの検査を行ったことになる。
【００９５】
さらに、図１３(ａ)、(ｂ)、(ｃ)に示す各ビットの区切り位置の場合に、それぞれ最初に並べる８分木ノード数を１、２、４個ではなく、これらの８倍である８、１６、３２個、８の２乗倍である６４、１２８、２５６個、或いは一般に８のｑ乗倍個にし、最初の１回、２回、或いは一般にｑ回の８分木ノードの検索時間を無くすことも可能である。この場合、メモリ上の決まった位置に展開する８分木ノードのマスク長ｍは、図１３(ａ)、(ｂ)、(ｃ)に示す各ビットの区切り位置の場合、それぞれ、ｍ＝３×ｑ、１＋３×ｑ、２＋３×ｑとなり、この上位ｍビット分の検索時間を省くことができる。ｑ＝１の場合、即ち８分木ノードの１回のノードの検索時間を無くす場合で、図１３(ａ)、(ｂ)、(ｃ)に示す３通りの各ビットの区切り位置の場合についてのメモリ上へのノードの展開法を、図１５(ａ)、(ｂ)、(ｃ)にそれぞれ示す。
【００９６】
図１５(ａ)では、マスク長ｍ＝３の８分木ノードを８個メモリ上の決まった位置に展開し、受信パケットの経路アドレスの第０〜２ビットの計３ビットの値に従って、展開された８分木ノードの内の一つを選択する。図１５(ｂ)では、マスク長ｍ＝１＋３＝４の８分木ノードを１６個メモリ上の決まった位置に展開し、受信パケットの経路アドレスの第０〜３ビットの計４ビットの値に従って、展開された８分木ノードの内の一つを選択する。図１５(ｃ)では、マスク長ｍ＝２＋３＝５の８分木ノードを３２個メモリ上の決まった位置に展開し、受信パケットの経路アドレスの第０〜４ビットの計５ビットの値に従って、展開された８分木ノードの内の一つを選択する。
【００９７】
以上、８分木を例にして方式３について説明したが、同様にして、マスク長ｍビットの２のｐ乗分木ノードをメモリ上の決まった位置に展開し、上位ｍビット分の検索時間を省くことができる。ｐ、ｑの値を大きくすると、経路検索時間を短縮することができるが、多くのメモリを必要とするので、ｐ、ｑの値は、メモリ効率と性能のトレードオフから決めるようにする。
【００９８】
以上、方式３について、２のｐ乗分木ノードの場合について述べたが、同様にして、方式１の２分木検索方式にこの方式３を適用することも可能である。
【００９９】
次に、４分木ノード、８分木ノード、１６分木ノード、或いは一般に２のべき乗分木のノードの構成法を図１６を用いて説明する。
【０１００】
図１６は４分木で、ある１つの２分木ノードＡ、Ｂ、Ｃ、Ｄ、Ｅと、その直下の２個の２分木ノードＡ０、Ａ１、Ｂ０、Ｂ１、Ｃ０、Ｃ１、Ｄ０、Ｄ１、Ｅ０、Ｅ１の、各々合計３個の２分木ノードをまとめて一つの４分木ノード１００、１０１、１０２、１０３、１０４にする場合の例であり、合計３個の２分木ノードをつぶして、下の方の２分木ノードだけの大きさにする。つぶし方は、経路アドレスマスク長に関する最長一致検索の仕様に従い、経路検索を行った場合に、２分木の場合と４分木の場合とで、経路検索結果が同じになる、という条件を満たすように行う。
【０１０１】
４分木の場合の、このノードのつぶし方を図１７に示す。図１７において、＊Ａという表記は、ノードＡに割り付けられているエントリ内の経路情報を表すことにする。また、＊Ａという表記がないノードにはエントリが割り付けられていないことを意味する。
【０１０２】
２分木構造において、３つのノードが全部ある場合(図１７(ａ))、全ノードにエントリが割り付けられていたら、下のノードの経路情報＊Ａ０、＊Ａ１を残し、上のノードは削除する。これは、ノードＡのエントリが一致したらノードＡ０かノードＡ１のどちらかのエントリが必ず一致するので、最長一致検索を行うことから、ノードＡの経路情報＊Ａが使用されることが無いからである。
【０１０３】
上のノードＡにエントリが割り付けられており、下のノードＡ０、Ａ１の内Ａ１にだけエントリが割り付けられていない場合(図１７(ｂ))、ノードＡ１に、Ａの経路情報＊Ａを格納する。下のノードＡ０、Ａ１の内Ａ０だけエントリが割り付けられていない場合も同様である。
【０１０４】
下のノードＡ０、Ａ１の両方にエントリが割り付けられていない場合(図１７(ｃ))には、Ａ０、Ａ１の両方のノード内に、Ａの経路情報＊Ａを格納する。
【０１０５】
下のノードＡ１が無い場合(図１７(ｄ))、Ａ１を補い、Ａ１には、上のノードＡの経路情報＊Ａを格納し、さらに、ノードＡ１の下にはノードが繋がっていないので、ノードＡ１の下のノードへのポインタはＮＵＬＬにする。下のノードＡ０、Ａ１の内Ａ０だけエントリが割り付けられていない場合も同様である。
【０１０６】
下のノードＡ０、Ａ１の両方が無い場合(図１７(ｅ))、両方を補い、両方のノードに、Ａの経路情報＊Ａを格納し、両方のノードの下のノードへのポインタはＮＵＬＬにする。
【０１０７】
上のノードＡにエントリが割り付けられていない場合(図１７(ｆ))、ノードＡをただ単に削除する。
【０１０８】
上のノードＡに経路が割り付けられておらず、下のノードＡ０、Ａ１の内、Ａ１にもエントリが割り付けられていない場合(図１７(ｇ))、４分木にした場合もＡ１の経路情報は無い。下のノードＡ０、Ａ１の内、Ａ０にエントリが割り付けられていない場合も同様である。
【０１０９】
上のノードＡにエントリが割り付けられてなく、下のノードＡ０、Ａ１の両方にエントリが割り付けられていない場合(図１７(ｈ))、４分木にした場合もＡ０、Ａ１の両方のノードの経路情報は無い。
【０１１０】
下のノードＡ０だけしかない場合(図１７(Ｉ))には、下のノードＡ１を補う。下のノードＡ１だけしかない場合も同様である。
【０１１１】
８分木の場合も同様にして、一つにまとめる７個の２分木ノードをつぶして、一番下の４個のノードだけの大きさにする。上の方の３つの２分木ノードのつぶし方の２つの例を図１８に示す。
【０１１２】
図１８(ａ)は一つにまとめる７個の２分木ノードが全てあるが、その内のいくつかにしかエントリが割り付けられていない場合の例であり、最下の４つのノードの内、エントリが割り付けられていないノードＡ０１、Ａ１０には、そのノードの上方につながっているノードの内、エントリが割り付けられている最も下、即ち最も経路アドレスマスク長が長いノード(それぞれ、Ａ、Ａ１)の経路情報＊Ａ、＊Ａ１を格納する。
【０１１３】
図１８(ｂ)は一つにまとめる７個の２分木ノードの内のいくつかしかノードが存在しない場合の例であり、存在しないノードＡ０１、Ａ１０を、まずエントリが割り付けられていないノードとして補い、図１８(ａ)と同じ規則で、経路情報を格納する。最下の４つのノードＡ００、Ａ０１、Ａ１０、Ａ１１の内、補ったノードＡ０１、Ａ１０の下には、ノードが繋がっていないので、下のノードへのポインタはＮＵＬＬにする。
【０１１４】
一般に２のｐ乗分木の場合も同様にして、一つにまとめる(２のｐ乗−１)個の２分木ノードをつぶして、一番下の２の(ｐ−１)乗個のノードだけの大きさにする。
【０１１５】
また、４、８、１６、...分木ノードでは、２分木ノードを２、４、８、...個まとめて扱うので、１つの４、８、１６、...分木ノードにまとめられる２分木ノード間で共通な要素は、一つだけ持てばよく、これにより、４、８、１６、...分木ノードのメモリ量を小さくできる。１つにの４、８、１６、...分木ノードにまとめられる2分木ノード間で共通な要素には、ノードが持つ経路アドレス、及び、経路アドレスマスク長があるが、経路アドレスマスク長については、後述するように、このノード自身の経路アドレスマスク長ではなく、このノードの直下のノードの経路アドレスマスク長を持つようにするので、メモリ量を小さくする効果は無い。
【０１１６】
次に、２のｐ乗分木ノードの一つの例として、４分木ノードのデータ構造について図１９を用いて説明する。４分木ノードを構成する際、上記２分木ノードを２つまとめ、まとめられる２つの２分木ノードに共通のデータを一つだけ保持するようにする。この共通のデータは、そのノードの経路アドレスだけである(ワード１２４、１２５)。また、まとめられる２分木ノードが、経路が割り付けられているか否かによりその大きさが異なると、それらをまとめて構成する４分木ノードの大きさも異なってしまう。従って、図１２(ｂ)で示したように、送信ポート情報をノードから分離し、ノード内にはこの送信ポート情報へのポインタを保持する２分木ノードをまとめる。
【０１１７】
図１９において、ワード１２０、１２１、１２２、１２３内の次ノードのマスク長ｔｔ、フラグｔｔ、次ノードへのポインタｔｔはそれぞれ、受信パケットの経路アドレスの、このノードの経路アドレスマスク長ｍで示された第ｍビット、および第ｍ＋１ビットの値ｔｔに対応する値である。ここでｔｔは００、０１、１０、１１の値を取りうる。２分木の場合と同様に、フラグ００とフラグ０１は同じ値を設定し、フラグ１０とフラグ１１も同じ値を設定する。
【０１１８】
図１２(ｂ)に示す例では、２分木ノードは、２のべき乗の大きさである１６バイトにわずかに入りきらない大きさになっているが、４分木ノードにし、１ノード内に経路アドレスを一つしか持たないようにすることで、２のべき乗の大きさである３２バイトに丁度収まるようになっている。８分木ノードにし、経路アドレスを１ノードで一つだけ保持するようにすれば、６４バイトの大きさに収まる上に、４バイトの余裕ができ、この領域は他の情報を入れるのに使用できる。さらに1つにまとめる２分木の数を増やせば(すなわち、２のｐ乗分木のｐの値を大きくとれば)、２のべき乗の大きさに対し、1つのノードの大きさをさらに小さくできる。
【０１１９】
このように、１ノードの大きさを２のべき乗の大きさに収めることで、ハードウェアの構成を非常に簡単にできる。ハードウェアの構成を簡単にできる例を以下に示す。
【０１２０】
１つ目の例として、４分木ノードが３２バイトに収まる場合、メモリを複数バンクで構成していた場合でも１ノードのメモリ領域がバンク境界にまたがることがないこと、メモリにダイナミックＲＡＭを使用していた場合でも１ノードのメモリ領域がＲｏｗアドレス境界にまたがることがないこと。
【０１２１】
２つ目の例として、ノード内の各要素のメモリ上のアドレス(以下、メモリアドレスと呼ぶ)を求めるときに、そのノードへのポインタとそのポインタからのオフセットの足し算でなく、メモリアドレスの上位ビットはポインタの値にし、下位ビットをオフセットにすればよいこと。例えば４分木ノードが３２バイトに収まる場合、あるノード内のある要素のメモリアドレスを生成するには、そのノードへのポインタをメモリアドレスの２の５乗ビット以上に割り付け、ノード内のその要素へのオフセットをメモリアドレスの２の０乗ビットから２の４乗ビットに割り付ければよい。
【０１２２】
３つ目の例として、例えば４分木ノードが３２バイトに収まる場合、各ノードに保持する次のノードへのポインタとして、(次のノードの先頭のバイトアドレス)÷３２、という値を保持すればよく、１ノード内で１ポインタあたり５ビットづつデータ量を減らせることが挙げられる。
【０１２３】
次に、例えば、図１の経路検索処理回路２００を専用ＬＳＩで構成する場合のノードの読み込み方式について説明する。４、８、１６、...分木ノードにした場合に１つのノードが大きくなり、検索処理時にテーブルを保持するメモリから専用ＬＳＩ内に１つのノードを全て読み込むと、ノードを大きくするに従い読み込み時間が伸び、性能低下要因となる、という問題があるが、この問題は、ノードを大きくしたときに、１つのノード全てを読み込まず一部だけを読み込む、という方で回避する。この方法について、図２０を用いて説明する。
【０１２４】
図２０に４分木の場合の例を示す。既に図１９を用いて説明したように、経路アドレスマスク長ｍビットの４分木ノードは、図１２(ｂ)で示した、経路アドレスの第ｍビット目の値が０の場合に対応する２分木ノードと、１の場合に対応する２分木ノードを併せた構造になっている。従って、受信パケットの経路アドレスの第ｍビット目の値にしたがって、対応する方の２分木ノードの部分だけを読み込むことにより、ノードの大きさが大きくなっても２分木ノードの場合と同じデータ量を読み込むようにする。このとき、図１９で示した、1つにまとめられる2分木ノード間で一つだけ保持する要素であるノードの経路アドレス(ワード１２４、１２５)は、受信パケットの経路アドレスのｍビット目の値に係わらず読み込むようにする。
【０１２５】
さらに、受信パケットの経路アドレスの第(ｍ＋１)ビット目の値に従い、２分木ノードで２つ存在した次ノードへのポインタの内、一方だけを読み込むようにすることにより、読み込むデータ量をさらに少なくする。
【０１２６】
この方法は２分木検索方式にも使用できる。例えば第ｍビット目の２分木ノードの場合には、受信パケットの経路アドレスの第ｍビット目の値に従い、２つの次ノードへのポインタの内、一方だけを読み込むようにする。
【０１２７】
上記方法を全て行い、結局、このノードの経路アドレスマスク長をｍとした場合、宛先アドレスの第ｍ、ｍ＋１ビットの値が００か、０１か、１０か、１１かに従い、それぞれ(ワード１２０→ワード１２４→ワード１２５→ワード１２６)、(ワード１２１→ワード１２４→ワード１２５→ワード１２６)、(ワード１２２→ワード１２４→ワード１２５→ワード１２７)、(ワード１２３→ワード１２４→ワード１２５→ワード１２７)の順にデータを読み込むようにする(図２０（ｂ）)。
【０１２８】
このように、あるノードの一部分だけを読み込むためには、このノードの経路アドレスマスク長ｍを知る必要があり、このノードの経路アドレスマスク長ｍは、１ノードのデータ読み込みの最初に読み込むか、この情報を１つ前のノードに移し、一つ前のノードのデータ読み込み時に読み込む必要がある。ノードのマスク長ｍを１ノードのデータ読み込みの最初に読み込む方法は、例えば、図１の経路検索処理回路２００を専用ＬＳＩで構成する場合、宛先の第ｍビット目の値の抽出のための専用ＬＳＩ内のゲートディレイ、及び、次に読み込む部分のメモリアドレスをメモリに出力してからメモリからのデータを専用ＬＳＩ内に読み込むまでの時間であるメモリリードレイテンシだけ、マスク長ｍを読み込んでから次に読み込む部分を選択して読み込むまで時間が空いてしまうので、ノードの一部だけを読むことによる性能向上効果が少ない。ノードのマスク長ｍを１つ前のノードに移し、一つ前のノードのデータの読み込み時に読み込む方が性能向上効果がある。
【０１２９】
さらに、ノードの経路アドレスマスク長ｍを１つ前のノードに移す場合、１ノードのデータを読み込む順序を、１番目に次のノードの経路アドレスマスク長ｍ、次のノードへのポインタ、次にノードの経路アドレス、送信ポート情報へのポインタの順にすることにより、次のノードの最初に読み込む部分のメモリアドレスが最も早く計算できるようにする。
【０１３０】
次のノードへのポインタは、次のノードのメモリ領域の先頭部分を指しており、次のノードの先頭から最初に読み込む部分までのメモリアドレスのオフセットは、次のノードのマスク長ｍを読み込み、受信パケットの経路アドレスの該当ビット位置の値を検査することにより、得られる。
【０１３１】
次に、１ノード内で、条件によっては、読み込む必要が無い要素を、その条件に従って読み込まないようにすることで、読み込みの時間を削減し、高速化を図る方法について図２１を用いて説明する。
【０１３２】
図２１に4分木の場合の例を示す。２分木構造の説明で述べたように一般に木構造においては、全ノードにエントリが割り付けられているわけではなく、枝の分岐の個所では、エントリが割り付けられていなくてもノードを設ける必要がある。図２１に示すように、ノードデータの最初に読み込むワード１２０、１２１、１２２、１２３内のフラグ内のエントリ有りフラグの値に従い、エントリが割り付けられていないノードでは、送信ポート情報へのポインタを読み込まないようにすることで、読み込み時間の短縮を図ることができる。エントリ有りフラグは１ビットで表現できるので、この情報を読み込むことによる読み込み時間の増大は小さい。
【０１３３】
この方法では、このノードのマスク長をｍとすると、宛先アドレスの第ｍ、ｍ＋１ビットの値が００で、ワード１２０を読み、フラグ００から、４分木を構成する０番目の２分木に経路情報が無いと判った場合、ワード１２４、１２５だけを読めば良く、経路情報が有ると判った場合にだけ、図２１（ｂ）に示すようにワード１２４→ワード１２５→ワード１２６の順に読めば良い。宛先アドレスの第ｍ、ｍ＋１ビットの値が０１、１０、１１の場合も同様である。
【０１３４】
以上、２分木検索方式(方式１)、２のｐ乗分木検索方式(方式２)、およびマスク長ｍビットのノードをメモリ上に展開する方法(方式３)という各検索方式について説明した。次に、図１の経路検索処理回路２００が上記の方式を用いて経路検索処理を行う際のフローチャートについて図２２を用いて説明する。図２２のフローチャートでは、方式２と方式３とを組み合わせた場合の例を示す。この例では、経路アドレスの第０ビットから第(ｍ−１)ビットの値に従って、メモリ上の決まった位置に展開された２のｐ乗分木ノードの一つを選択する。以下ではこのように選択し、検索の最初に読込む２のｐ乗分木ノードを初段ノードと呼ぶ。第ｍビット以降は経路アドレスをｐビットずつ検索し、２のｐ乗分木を検索する。図１のメモリ３００には、上記の方式２および方式３の検索方式に従った２のｐ乗分木ノードデータ、および送信ポート情報が格納されているとする。
【０１３５】
なお、以下では方式２と方式３とを組合わせた例について説明するが、方式１と方式３とを組み合わせた場合でも同様なフローチャートに従うことで実現可能である。また、このフローチャートに従うことにより、ソフトウェアでもハードウェアでも経路検索処理を実現することができる。ソフトウェアで実現する場合、図１の経路検索処理回路２００にはＣＰＵを用いればよい。またハードウェアで実現する場合、図１の経路検索処理回路２００を専用ＬＳＩで構成すればよい。
【０１３６】
図２２の処理８１０は木構造検索処理であり、また、処理８１１は送信ポート情報処理である。まず、木構造検索処理８１０について説明する。
【０１３７】
図１の経路検索処理回路２００は、受信パケットの宛先マルチキャスト・グループＩＤおよび送信元ＩＰアドレスを受け取ると、これらの値から図５を用いて説明した経路アドレスを生成し、この経路アドレスと初段ノードのマスク長ｍの値から初段ノードへのポインタを生成し、このポインタと、経路アドレスの第ｍビットから第(ｍ＋ｐ−１)ビットの値(以下、検査ビット値と呼ぶ)に従ってメモリ３００に格納されている初段ノードの読み込みアドレスを生成し、メモリ３００から該初段ノードの一部を読み込む(図２２の８００)。
【０１３８】
次に、図１の経路検索処理回路２００は、受信パケットの経路アドレスにノードのマスク長だけ上位ビットから有効とするマスクをかけたものと、ノードの経路アドレスと比較し(図２２の８０１)、不一致の場合は木構造検索処理８１０を終了する(図２２の８０９)。一致する場合は図２２の処理８０２に進む。
【０１３９】
次に、図２２の処理８０２、および８０３について説明する。これらの処理は、最長一致検索を実現するための経路情報の更新処理である。経路情報としては、図１のメモリ３００が出力するノードデータの内、エントリ有りフラグと、送信ポート情報へのポインタがある。図１の経路検索処理回路２００は、ノードデータ内のエントリ有りフラグを検査し、エントリ有りフラグの値が１の場合(図２２の８１２)のみ、読み込んだノード内の新たな経路情報をレジスタに保持する(図２２の８０３)。エントリ有りフラグの値が０の場合は更新処理を行わない(図２２の８１３)。
【０１４０】
次に、図１の経路検索処理回路２００は、図１のメモリ３００が出力するノードデータの内の次ノードへのポインタがＮＵＬＬかどうかを判定し(図２２の８０４)、ＮＵＬＬの場合は木構造検索処理８１０を終了する。ＮＵＬＬでない場合はそのポインタと、新たな検査ビットの値に従ってメモリ３００に格納されている初段ノードの読み込みアドレスを生成し、メモリ３００から該ノードデータを読み込む(図２２の８０５)。
【０１４１】
以下、上記の処理を繰り返すことにより、２のｐ乗分木方式の経路検索を行うことができる。
【０１４２】
次に、図２２の送信ポート情報処理８１１について説明する。木構造検索処理の結果、図１の経路検索処理回路２００内のレジスタには、経路情報として、上記のエントリ有りフラグと送信ポート情報へのポインタが保持されている。図１の経路検索処理回路２００は、まず、レジスタに保持されているエントリ有りフラグを調べ(図２２の８０６)、その値が０の場合は経路検索処理を終了し、転送処理部５０４へ検索結果無しという通知をする。エントリ有りフラグの値が１の場合は、検索の結果、あるエントリに一致したことになるため、送信ポート情報へのポインタを用いてメモリ３００から送信ポート情報を読み出す(図２２の８０７)。この送信ポート情報からパケットを送信すべき１つまたは複数のポート番号を生成して図１の転送処理部５０４へ送信し(図２２の８０８)、すべてのポート番号を送信し終わると経路検索処理を終了する。
【０１４３】
次に、本発明の一実施例として、図２２で説明した検索方式をハードウェアで実現する場合の構成例について、図２３、図２４を用いて説明する。
【０１４４】
図２３に経路検索処理部４００をハードウェアで構成した場合の構成例を示す。経路検索処理回路２００は、木構造検索回路２０１と、読み込みアドレス生成回路２０２と、メモリ制御回路２０６と、送信ポート情報処理回路２０３と、経路検索処理制御回路２０４とからなる。
【０１４５】
木構造検索回路２０１は、メモリ３００に格納された２のｐ乗分木構造を検索し、次に読み込むべきノードのポインタの生成、受信パケットの経路アドレスの検査ビット値の抽出、木構造検索の終了判定、検索結果である経路情報の候補の更新を行う。また、読み込みアドレス生成回路２０２は、木構造検索処理時には、木構造検索回路２０１から出力される読み込むべきノードへのポインタ、および検査ビット値、および経路検索処理制御回路２０４から出力されるタイミング信号に従い、図２０を用いて説明した順序でノード内の読み込みワードのメモリアドレスを生成してメモリ制御回路２０６に送信する。また、送信ポート情報処理時には、木構造検索回路２０１内のレジスタに検索結果として保持されている送信ポート情報へのポインタから送信ポート情報のメモリアドレスを生成する。また、メモリ制御回路２０６は、上記のメモリアドレスと、経路検索処理制御回路２０４から出力されるタイミング信号に従い、メモリ制御信号を生成する。また、送信ポート情報処理回路２０３は、メモリ３００から読み出された送信ポート情報からパケットを送信すべき１つまたは複数のポート番号を生成して転送処理部５０４へ送信する。また、経路検索処理制御回路２０４は、経路検索処理回路２００全体の制御(各回路の動作タイミングおよび動作状態管理など)を行う。
【０１４６】
上記の経路検索処理回路２００を専用ＬＳＩで実現する場合、メモリ３００は上記専用ＬＳＩの外部に備えても良いし、専用ＬＳＩ内の内臓メモリを使用しても良い。メモリ３００として専用ＬＳＩの内蔵メモリ使用すると、外部メモリを使用する場合に比べてメモリアクセス時間が短くなり、メモリ３００内に格納されたルーティングテーブルの検索処理を高速に行うことができる。
【０１４７】
次に、経路検索処理部４００の動作について図２３を用いて説明する。また、木構造検索回路２０１の詳細動作については、図２４を用いて後述する。
【０１４８】
木構造検索回路２０１は、転送処理部５０４から受信パケットの宛先マルチキャスト・グループＩＤおよび送信元ＩＰアドレスを受け取ると、これらの値から経路アドレスを生成し、この経路アドレスとノードのマスク長の値から次ノードへのポインタを生成して、読み込みアドレス生成回路２０２に転送する。また、木構造検索回路２０１は、ノードのマスク長で示される経路アドレスの検査ビット位置の値(検査ビット値)を抽出して、読み込みアドレス生成回路２０２に転送する。
【０１４９】
読み込みアドレス生成回路２０２はこのノードへのポインタと、検査ビット値と、経路検索処理制御回路２０４からのタイミング信号を用いて、図２０を用いて説明した順序でノード内の読み込みワードのメモリアドレスを生成し、メモリ制御回路２０６に送信する。メモリ制御回路２０６は上記メモリアドレスと経路検索処理制御回路からのタイミング信号を用いてメモリ制御信号を生成し、メモリ３００へ出力する。上記のメモリ制御信号を受信したメモリ３００は、対応するノードデータを信号線２１４を用いて木構造検索回路へ転送する。
【０１５０】
木構造検索回路２０１はこのノードデータを用いて、図２２の処理８０１、８０２、８０３、８０４、８０５を行う。これらの処理の詳細は図２４で後述する。図２２の処理８０１および８０４に対応する判定処理において木構造検索を終了すると判定した場合は、木構造検索終了信号を経路検索処理制御回路２０４へ出力し、経路検索処理制御回路２０４は送信ポート情報読み込み処理を開始する。終了と判定されない場合は、終了と判定されるまで図２２の処理８０１、８０２、８０３、８０４、８０５を繰り返す。
【０１５１】
次に、経路検索処理制御回路２０４は、木構造検索回路２０１内に保持された経路情報(エントリ有りフラグ、送信ポート情報へのポインタ)のうちのエントリ有りフラグを調べ、その値が０の場合は経路検索処理を終了し、転送処理部５０４へ検索結果無しという通知をする。エントリ有りフラグの値が１の場合は、送信ポート情報読み込みおよび送信ポート生成処理制御を開始し、木構造検索回路２０１を制御して、送信ポート情報へのポインタを読み込みアドレス生成回路２０２へ出力させる。読み込みアドレス生成回路２０２はこの送信ポート情報へのポインタと、経路検索処理回路２０４からのタイミング信号を用いて、読み出すべき送信ポート情報が格納されているメモリアドレスを生成し、メモリ制御回路２０６へ送信し、メモリ制御回路２０６は、上記のメモリアドレスと、経路検索処理制御回路２０４から出力されるタイミング信号に従い、メモリ制御信号を生成してメモリ３００へ出力し、この制御信号を受信したメモリ３００から信号線２１４上に送信ポート情報が出力される。送信ポート情報処理回路２０３はこの送信ポート情報を取り込み、パケットを送信すべき１つまたは複数のポート番号を生成して転送処理部５０４へ送信する。
【０１５２】
送信ポート情報の構造については、複数の送信ポート番号をポインタでつないだリスト構造や、送信ポート番号のビットマップ化などが考えられるが、リスト構造の場合、送信ポート番号が多いとメモリアクセス回数が増加し、結果として検索処理が遅くなる問題がある。送信ポート番号をビットマップ化する方法は、そのビットマップをメモリ３００からバーストリードして送信ポート情報処理回路２０３内に保持しておき、そのビットマップをデコードして送信ポート番号を生成することにより、メモリアクセス回数を減らすことができる。
【０１５３】
すべての送信ポート番号を出力した後で、経路検索処理制御回路２０４は経路検索処理を終了し、次のパケット処理の制御を行う。
【０１５４】
次に、図２３の木構造検索回路２０１の詳細を図２４を用いて説明する。
【０１５５】
まず、図２２の初段ノードリード処理８００および次ノードリード処理８０５に対応する処理について、図２４を用いて説明する。転送処理部５０４より信号線２０５を用いて送信される宛先マルチキャスト・グループアドレスおよび送信元ＩＰアドレスは、経路アドレス生成回路２０７内に保持される。経路アドレス生成回路２０７はこれらの情報から、図５(ｂ)で説明した６０ビットの経路アドレス３３を生成し、初段ノードへのポインタ生成回路２０８、検査ビット抽出回路２０９、マスク処理回路２１０へ出力する。
【０１５６】
初段ノードへのポインタ生成回路２０８は、予め初段ノードマスク長レジスタ２２９に設定されている値ｍに従い、受信パケットの経路アドレスの第０ビットから第(ｍ−１)の上位ｍビットの値を抽出し、このｍビットの値に従って初段ノードへのポインタを生成してポインタセレクタ２１１へ出力する。ポインタセレクタ２１１は、信号線２２６によって図２３の経路検索処理制御回路２０４から送信される初段ノード読み込み／初段ノード以外のノード読み込み選択信号に従い、初段ノードの読み込み時は、上記の初段ノードへのポインタを選択して図２３の読み込みアドレス生成回路２０２へ出力する。また、ポインタセレクタ２１１は、初段ノード以外のノードの読み込み時は、次ノードへのポインタレジスタ２１５に保持されている次ノードへのポインタを選択して読み込みアドレス生成回路２０２へ出力する。
【０１５７】
また、上記の処理と並行して、検査ビット抽出回路２０９は、初段ノード読み込み時には、検査ビット位置セレクタ２１２において選択されて出力される初段ノードマスク長レジスタ２２９の設定値ｍに従い、経路アドレスの第ｍビットから第(ｍ＋ｐ−１)ビットまでのｐビットの検査ビット値を抽出して図２３の読み込みアドレス生成回路２０２へ出力する。また、初段ノード以外のノードの読み込み時は、後述する次ノードマスク長レジスタ２１６に保持されている次ノードのマスク長ｍ１が、検査ビット位置セレクタ２１２において選択されて検査ビット抽出回路２０９に出力され、検査ビット抽出回路２０９は、この次ノードのマスク長ｍ１に従い、経路アドレスの第ｍ１ビットから第(ｍ１＋ｐ−１)ビットまでのｐビットの検査ビット値を抽出して図２３の読み込みアドレス生成回路２０２へ出力する。
【０１５８】
図２３の読み込みアドレス生成回路２０２およびメモリ制御回路２０６は、上記のノードへのポインタとｐビットの検査ビット値を用いて、図２０を用いて説明した順序でノード内の読み込みワードのメモリアドレスおよびメモリ制御信号を生成し、メモリ３００は入力されたメモリアドレスに格納されているノード内の読み込みワードを信号線２１４に出力する。
【０１５９】
信号線２１４のビット幅が３２ビットの場合、図２０で説明した方式を採用すると一回のノード(の一部)の読み込みワード数は４ワードとなり、これらのデータは図２０の表に示した順番で信号線２１４に出力され、各レジスタ(次ノードへのポインタレジスタ２１５、次ノードマスク長レジスタ２１６、経路アドレス上位レジスタ２１７、経路アドレス下位レジスタ２２２、フラグレジスタ２２４、送信ポート情報ポインタレジスタ２３０)に保持される。各レジスタの保持タイミングは経路検索処理制御回路２０４からの制御信号(図示していない)により制御される。次ノードへのポインタレジスタ２１５には次ノードへのポインタが保持され、次ノードマスク長レジスタ２１６には次ノードのマスク長が保持され、経路アドレス上位レジスタ２１７にはノードの経路アドレスの上位２８ビットが、経路アドレス下位レジスタ２２２には経路アドレスの下位３２ビットがそれぞれ保持され、フラグレジスタ２２４にはエントリ有りフラグが保持され、送信ポート情報ポインタレジスタ２３０には送信ポート情報へのポインタが保持される。
【０１６０】
次に、図２２の経路アドレス一致比較処理８０１に対応する処理について、図２４を用いて説明する。初段ノード読み込み時には、マスク長セレクタ２２８を介して初段ノードマスク長レジスタ２２９の設定値がマスク処理回路２１０に入力する。
【０１６１】
初段ノード以外のノード読み込み時には、マスク長セレクタ２２８を介してマスク長レジスタ２２７に保持されているノードのマスク長がマスク処理回路２１０に入力する。このマスク長レジスタ２２７の値は、一つ前に読み込んだノードに格納されている次ノードのマスク長の値であり、次ノードマスク長レジスタ２１６に保持されていたものである。次ノードマスク長レジスタ２１６の値は、ノードの読み込み毎に更新されるため、更新される前に、現在読み込んでいるノード(以下、現ノードと呼ぶ)の経路アドレス一致比較処理に使用する現ノードのマスク長をマスク長レジスタ２２７に保持しておく。
【０１６２】
マスク処理回路２１０は、これらのマスク長だけ上位ビットから有効とするマスクを生成し、このマスクと、経路アドレス生成回路２０７から出力される受信パケットの経路アドレスとの論理積をとり、その結果(以下、マスクした受信パケットの経路アドレスと呼ぶ)を一致比較回路２１３に出力する。また、経路アドレス上位レジスタ２１７、経路アドレス下位レジスタ２２２に保持されているノードの経路アドレスの上位２８ビット、下位３２ビットはこの順に連結され、ノードの経路アドレスとして一致比較回路２１３に入力される。一致比較回路２１３は、このノードの経路アドレスと、上記で説明した、マスクされた受信パケットの経路アドレスとを比較し(以下経路アドレス比較と呼ぶ)、その結果が不一致となる場合には不一致信号を信号線２１８を用いて木検索終了判定回路２１９に転送する。木検索終了判定回路２１９は上記不一致信号を受信し、木構造検索終了信号を図２３の経路検索処理制御回路２０４に送信する。
【０１６３】
また、マスク長レジスタ２２７の値は、上記の経路アドレス比較が行われた後、次ノードマスク長レジスタ２１６に保持されている次ノードのマスク長の値によって更新され、次のノードの読み込み時の経路アドレス比較に使用される。
【０１６４】
次に、図２２の処理８０２、および８０３に対応する処理について、図２４を用いて説明する。
【０１６５】
一致比較回路２１３における経路アドレス比較の結果一致した場合、一致比較回路２１３は信号線２２０を用いて一致信号を更新判定回路２２１に出力する。この一致信号が更新判定回路２２１に入力され、かつ、フラグレジスタ２２４に保持されているエントリ有りフラグの値が１の場合(図２５の８１２)のみ、更新判定回路２２１は更新信号をフラグレジスタ２２３および送信ポート情報へのポインタレジスタ２２５に出力する。更新信号を受信したフラグレジスタ２２３は、フラグレジスタ２２４に保持されているエントリ有りフラグを新たに保持し、同じく更新信号を受信した送信ポート情報へのポインタレジスタ２２５は、送信ポート情報ポインタレジスタ２３０に保持されている送信ポート情報へのポインタを新たに保持する(図２２の経路情報更新処理８０３)。エントリ有りフラグの値が０の場合は更新判定回路２２１は更新信号を送信しないので、フラグレジスタ２２３および送信ポート情報へのポインタレジスタ２２５は更新処理を行わない(図２２の８１３)。
【０１６６】
経路情報として上記のフラグおよび、送信ポート情報へのポインタ以外の情報を追加する必要がある場合は、木構造のノード内にそれらの情報を追加し、それらの情報を保持、更新するレジスタを新たに追加すればよい。
【０１６７】
次に、図２２の次ノードへのポインタがＮＵＬＬかどうかの判定処理８０４に対応する処理について、図２４を用いて説明する。次ノードへのポインタレジスタ２１５内に保持されている次ノードへのポインタは木検索終了判定回路２１９に入力される。この次ノードへのポインタがＮＵＬＬの場合、木検索終了判定回路２１９は図２３の経路検索処理制御回路２０４に木検索終了信号を出力する。
【０１６８】
以上、図２３の木構造検索処理回路２０１の詳細動作を図２４を用いて説明したが、ハードウェアで構成するため、図２２の木構造検索処理の中の８０１、８０２、８０３、８０４、８０５の各処理は逐次処理をする必要はなく、各処理に必要なデータが各レジスタ２１５、２１６、２１７、２２２、２２４、２３０に保持された後に、各処理を開始すればよく、上記の各処理を並列処理を行うことにより、高速に木構造の検索を行うことができる。
【０１６９】
【発明の効果】
マルチキャスト経路検索において検索のキーとなる宛先マルチキャスト・グループアドレスと送信元ＩＰアドレスをこの順に連結して一つの経路アドレスとして定義し、この経路アドレスのビットパターンに従い、マルチキャストルーティングテーブルを２分木に構成することにより、エントリ数が増大しても検索時間は増加しない検索処理を行うことができる。
【０１７０】
また、検索木を構成する各ノードを、従来の方法である２分木ノードから４分木、８分木、あるいはそれ以上と、枝別れの数を２のべき乗で増やすことにより、１つのノードで１ビットでなく、連続する２ビット、３ビット、あるいはそれ以上のビット数を同時に検査でき、検索終了までに辿るノードの数が減り、経路検索処理の高速化を図る効果がある。
【０１７１】
図２５に、エントリ数に対する従来技術２のハッシュ方式のマルチキャスト経路検索の処理性能９００、および本発明の２分木方式のマルチキャスト経路検索の処理性能９０１、２のｐ乗分木方式のマルチキャスト経路検索の処理性能(例として、４分木方式の性能９０２、８分木方式の性能９０３)を示す。ハッシュ方式では、エントリ数に反比例して処理性能が劣化するのに対し、２分木方式および２のｐ乗分木方式ではエントリ数に依存せず一定となる。また、２分木方式に対し、４分木方式は２倍の性能を実現でき、また、８分木方式では３倍の性能を実現できる。
【０１７２】
さらに、上記の経路アドレスとして、マルチキャスト・グループアドレス自体ではなく、マルチキャスト・グループアドレスの下位２８ビットのマルチキャスト・グループＩＤと送信元ＩＰアドレスをこの順に連結したものを採用し、この経路アドレスのビットパターンに従い、マルチキャストルーティングテーブルを２分木あるいは２のｐ乗分木に構成することにより、検索木の深さを決定する経路アドレスのビット数を４ビット減らし、ノードを渡る最大回数を減らすことができる。
【０１７３】
また、４分木、８分木、あるいは一般に２のｐ乗分木を構成するときに、１つの２分木ノードと、その直下につながる(ｐ−１)段分の合計(２のｐ乗−１)個分の２分木ノードを一つの２のｐ乗分木ノードにまとめ、まとめられる最下段の２の(ｐ−１)乗個の２分木ノードに、それより上段のノードに割り付けられていた経路データを埋め込むことにより、まとめる前には２分木ノード換算で(２のｐ乗−１)個分のメモリ量だったものを、２の(ｐ−１)乗個分のメモリ量に減らす効果がある。
【０１７４】
さらに、２分木ノードを２のｐ乗分木にまとめる際、送信ポート情報を検索木のノードから分離して記憶手段の別領域に格納し、検索木のノードには上記送信ポート情報の格納領域へのポインタを保持することで、エントリが割り当てられている２分木ノードと、エントリが割り当てられていない２分木ノードのデータ量を同じにし、これらの２分木ノードをまとめて２のｐ乗分木ノードを構成する際に、２のｐ乗分木ノードのメモリ量の削減と、各２のｐ乗分木ノードのメモリ量の統一を図ることができる
また、この２分木を複数個併せた形で構成した４分木、８分木、あるいはそれ以上の枝別れ数のノードを、検索のために読むときにノード全てを読むのではなく、必要な部分のみを読むようにすることにより、ノードが大きくなることによるデータの読み込み時間の増大を防ぎ、経路検索処理の高速化を図る効果がある。
【０１７５】
また、各ノードに、そのノード自体のマスク長ではなく、そのノードのすぐ下につながるノードのマスク長を格納することにより、ノードのマスク長をノードのデータを読む前に知ることができ、ノードのデータを読む前に、ノードのどの部分を読み込めば良いかが分かり、必要な部分のみを読むことができるようになり、ノードが大きくなることによるデータの読み込み時間の増大を防ぎ、経路検索処理の高速化を図る効果がある。
【０１７６】
また、各ノードの先頭に、そのノードにエントリが割り付けられているか否かを示すフラグを設け、最初に、このフラグを読み込み、エントリが割り付けられていないノードでは、経路情報を読み込まないようにすることにより、データの読み込み時間が短縮され、経路検索処理の高速化を図る効果がある。
【０１７７】
また、経路アドレスの上位数ビット分、ノードをメモリ上の決まった位置に展開し、受信パケットの経路アドレスの上位数ビットに従い、ノードが格納されている位置を直接にアクセスすることは、検索処理時間を無くし、経路検索処理の高速化を図る効果がある。
【０１７８】
また、上記の高速化手段をハードウェアで構成することにより、経路検索処理の高速化を図る効果がある。
【図面の簡単な説明】
【図１】本発明の一実施例であるパケット中継装置の例であるルータのブロック図。
【図２】一般的なネットワークの構成例を示す図。
【図３】ＩＰアドレスの構成、およびクラスＤのＩＰアドレスの構成、およびＩＰパケットのパケットヘッダフォーマット。
【図４】一般的なルータの構成例を示す図。
【図５】本発明で定義する経路アドレスの構成図。
【図６】経路アドレス長３ビットの場合の全てのノードがある２分木。
【図７】経路アドレス長３ビットの場合のマルチキャストルーティングテーブルの例。
【図８】図６においてエントリが割り付けられておらず、かつ、エントリ付きのノードへの途中経路にもなっていないノードを取り除いた木。
【図９】経路アドレス３２ビットの場合のマルチキャストルーティングテーブルの例。
【図１０】図９に示したマルチキャストルーティングテーブルに対応する木。
【図１１】図１０において枝別れもエントリの割り付けも無いノードを取り除いた木。
【図１２】２分木ノードのデータ構造を示す図。
【図１３】２分木から８分木への変形時に一つの８分木ノードにまとめられる２分木ノードを囲んだ木。
【図１４】マスク長が０ビットから始まらないようにビット位置を区切った場合に最初のノードをメモリ上に展開することにより区切り位置までのビットの検索を行う木。
【図１５】先頭のさらに多くのビット数の検索時間を省いた木。
【図１６】２分木から４分木への変形時に１つの４分木ノードにまとめられる２つの２分木ノードを２つの２分木ノード分につぶした木。
【図１７】１つの４分木ノードにまとめられる３つの２分木ノードの、２つの２分木ノードへのつぶし方。
【図１８】１つの８分木ノードにまとめられる７つの２分木ノードの、４つの２分木ノードへのつぶし方。
【図１９】４分木ノードのデータ構造を示す図。
【図２０】ノードの大きさが大きくなったときにノードデータリード時間の増大を防ぐために１つのノード全てを読み込まずに一部だけを読み込む方法を示す図。
【図２１】条件によっては読み込む必要が無い要素を、条件に従い読み込まないようにすることで読み込みの時間を削減することで高速化を図る方法を示す図。
【図２２】本発明の一実施例である経路検索処理部の検索処理フローチャート。
【図２３】本発明の一実施例である経路検索処理部のブロック図。
【図２４】本発明の一実施例である、木構造のマルチキャストルーティングテーブル検索を行う木構造検索処理回路のブロック図。
【図２５】ハッシュ方式、２分木方式、２のｐ乗分木方式の、エントリ数に対する処理性能を示す図。
【符号の説明】
Ｔ１１、Ｔ１２、Ｔ２１、Ｔ２２、Ｔ３１、Ｔ３２、Ｔ４１、Ｔ４２、Ｔ５１、Ｔ５２・・・ネットワーク上でパケットを送受信する端末、ＳＮ１〜ＳＮ５・・・各端末が属するサブネットワーク、Ｒ１〜Ｒ３・・・サブネットワークを相互に接続するルータ、Ｐ１１、Ｐ１２、Ｐ１３、Ｐ２１、Ｐ２２、Ｐ２３、Ｐ２４、Ｐ３１、Ｐ３２、Ｐ３４、Ｐ３５・・・各ルータのポート、１・・・ＩＰアドレス、２・・・サブネットワークを識別するサブネットワークアドレス、３・・・ネットワーク内の端末を識別するホストアドレス、４・・・クラスＤのＩＰアドレス、５・・・クラスＤであることを示すクラスＤのＩＰアドレスの上位４ビット、６・・・マルチキャスト・グループＩＤ、７・・・ＩＰパケットヘッダの送信元アドレスフィールド、８・・・ＩＰパケットヘッダの宛先アドレスフィールド、１１-i(＝１〜Ｎ)・・・ルータの入力ポート、１２-i(＝１〜Ｎ)・・・ルータの出力ポート、１３-i(＝１〜Ｎ)・・・ルーティング処理部、１４・・・スイッチ、１５-i(＝１〜Ｎ)・・・通信制御部、１６・・・管理部、３２・・・マルチキャスト・グループアドレス、送信元ＩＰアドレスの順に連結して生成した経路アドレス、３３・・・マルチキャスト・グループＩＤ、送信元ＩＰアドレスの順に連結して生成した経路アドレス、６０・・・経路アドレス長３ビットの場合の受信パケットの経路アドレスの一例、４０〜５４、６２〜６５、７０〜８４、９０〜９５、１００〜１０４、１３０〜１４４・・・木を構成するノード、６１・・・枝別れもエントリの割り付けも無いノードの長い列、１１０〜１１３、１１５・・・２分木ノードを構成する３２ビットを単位とするワード、１１４・・・送信ポート情報、１２０〜１２７・・・４分木ノードを構成する３２ビットを単位とするワード、２００・・・経路検索処理回路、２０１・・・木構造検索回路、２０２〜２０４、２０６・・・経路検索処理回路を構成する各回路、２０５・・・転送処理部、経路検索処理部間の信号線、２０７〜２１３、２１５〜２３０・・・木構造検索回路を構成する各回路および信号線、２２６・・・経路検索処理制御回路からの読み込みノード(初段ノードかそれ以外か)選択制御信号線、３００・・・マルチキャストルーティングテーブルが格納されるメモリ、４００・・・経路検索処理回路とメモリから構成される経路検索処理部、５００、６０４、６０５・・・ルータに接続されるネットワークの例、５０１、６０２、６０３・・・通信制御部、５０２・・・パケットデータのメモリ格納およびメモリからの読み出しを制御する制御回路、５０３・・・パケットデータが格納されるメモリ、５０４・・・パケット転送処理部、５０５・・・複数のパケット処理部および管理部が接続されるスイッチ、６００・・・パケット処理部、６０１・・・ルータ全体の管理を行う管理部、７００・・・ルータ。
【図１】
0003735471.tif 000002
【図２】
0003735471.tif 000003
【図３】
0003735471.tif 000004
【図４】
0003735471.tif 000005
【図５】
0003735471.tif 000006
【図６】
0003735471.tif 000007
【図７】
0003735471.tif 000008
【図８】
0003735471.tif 000009
【図９】
0003735471.tif 000010
【図１０】
0003735471.tif 000011
【図１１】
0003735471.tif 000012
【図１２】
0003735471.tif 000013
【図１３】
0003735471.tif 000014
【図１４】
0003735471.tif 000015
【図１５】
0003735471.tif 000016
【図１６】
0003735471.tif 000017
【図１７】
0003735471.tif 000018
【図１８】
0003735471.tif 000019
【図１９】
0003735471.tif 000020
【図２０】
0003735471.tif 000021
【図２１】
0003735471.tif 000022
【図２２】
0003735471.tif 000023
【図２３】
0003735471.tif 000024
【図２４】
0003735471.tif 000025
【図２５】
0003735471.tif 000026