(57)【要約】【課題】受信した経路情報と、経路情報表に登録された経路情報との比較に要する時間を短縮する中継装置を提供する。【解決手段】ハッシュ値計算部１０２は、複数のメンバを含む経路情報を１つのハッシュ値に変換する。経路情報キャッシュ部１０４は、登録済みの経路情報と、そのハッシュ値とを経路情報表として記憶する。経路情報比較部１０３は、受信した経路情報のハッシュ値と、経路情報キャッシュ部１０４に保存されたハッシュ値とを比較する。経路情報処理部１０５は、経路情報比較部１０３の比較結果に基づいて、受信した経路情報を、経路情報表に追加登録する。【選択図】　　図１
2004040551.tif 000002
【特許請求の範囲】
【請求項１】
複数のメンバを含む経路情報をハッシュ値に変換するハッシュ値計算部と、
登録済みの経路情報を、該登録済みの経路情報のハッシュ値と共に保存する記憶部と、
受信した経路情報のハッシュ値と、前記記憶部に保存されたハッシュ値とを比較する比較部と、
前記比較部による比較結果に基づいて、受信した経路情報を登録するか否かを判定する登録判定部とを備えることを特徴とする中継装置。
【請求項２】
前記比較部は、受信した経路情報のハッシュ値と、登録済みの経路情報のハッシュ値とが一致すると、当該登録済みの経路情報の各メンバと、前記受信した経路情報の各メンバとを更に比較する、請求項１に記載の中継装置。
【請求項３】
前記比較部は、前記記憶部に保存された複数の経路情報を含む一の経路情報群のハッシュ値と、受信した複数の経路情報を含む他の経路情報群のハッシュ値とを比較する、請求項１又は２に記載の中継装置。
【請求項４】
他の中継装置から定期的に前記他の経路情報群を受信して、該他の経路情報群のハッシュ値と、前記記憶部に保存された一の経路情報群のハッシュ値とを比較する、請求項３に記載の中継装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は中継装置に関し、更に詳しくは、新たに収集した経路情報を経路情報表に登録する中継装置に関する。
【０００２】
【従来の技術】
ルータ等の中継装置は、ルーティングプロトコルを用いて他のルータから経路情報を収集し、収集した経路情報をメモリ等の記憶装置（経路情報キャッシュ）に経路情報表として登録する。中継装置は、外部のネットワークに向けたパケットを受信すると、経路情報を参照して、受信したパケットの送信先を決定する。新たなネットワークの追加や、ネットワークの構成の変更が確認されると、経路情報表に新たな経路情報が追加される。
【０００３】
図１４は、メモリに記憶される経路情報表の構成を示している。経路情報表は、経路情報への参照値（ポインタ）の集合として構成される。各経路情報は、複数のメンバ（経路情報の最小単位）から構成される。経路情報表は、例えば数千のオーダーの経路情報を有し、各経路情報は、例えば数百のオーダーのメンバの集合体として構成される。
【０００４】
図１５は、中継装置が経路情報を登録する際の手順をフローチャートとして示している。中継装置は、新たな経路情報を受信すると（ステップＳ１０１）、新たな経路情報と、経路情報キャッシュに記憶された、経路情報表に登録済みの経路情報との比較を開始する。中継装置は、経路情報表に登録された経路情報のうち、未比較の経路情報が経路情報キャッシュに存在するか否かを判断し（ステップＳ１０２）、未比較の経路情報が残っている場合には、そのうちの１つを選択し、新たに受信した経路情報と比較する（ステップＳ１０３）。
【０００５】
経路情報の比較は、経路情報を構成する全てのメンバが同じであるか否かを判断することによって行なわれる（ステップＳ１０４）。具体的には、まず、図１４に示す経路情報１を読み込み、新たに受信した経路情報のメンバ１と、経路情報１のメンバとを比較し、双方のメンバが一致する場合には、引き続きメンバ２、メンバ３、、、と順次にメンバ同士の比較を実行する。全てのメンバ同士が同じ値であった場合には、新たに受信した経路情報と、経路情報表に登録されている経路情報とが同一であると判定され、新たに受信した経路情報を破棄する（ステップＳ１０５）。
【０００６】
ステップＳ１０４において、比較対象の双方の経路情報に、１つでも異なる値のメンバが存在するときには、ステップＳ１０２へ戻り、経路情報表に未比較の経路情報が残っているか否かが再び判断される。未比較の経路情報が残っていない、つまり、経路情報表の全ての経路情報との比較が終了した場合には、新たに受信した経路情報と、経路情報キャッシュに記憶されている経路情報とは異なる経路情報であると判定され、新たに受信した経路情報を、経路情報表に追加登録する（ステップＳ１０６）。
【０００７】
【発明が解決しようとする課題】
上記した従来の中継装置では、新たな経路情報を受信するたびに、経路情報表の全ての経路情報について、全てのメンバ同士の比較を行なう必要があり、メンバの比較回数は、経路情報数×メンバ数（数千×数百）程度が必要になる。このため、データ（経路情報数又はメンバ数）量が多くなるに従い、比較に要する時間が飛躍的に増加する。経路制御プロトコルの種類によっては、中継装置は何度も再送（フラッディング）される同じ経路情報を受信することがあり、経路情報の比較に要する時間は、性能上無視できない問題となっている。
【０００８】
本発明は、上記問題を解消し、複数のメンバから構成される新たに受信した経路情報が、経路情報表に既に登録されている経路情報と同じ経路情報であるか否かを、少ない比較回数で判断可能な中継装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記目的を達成するために、本発明の中継装置は、複数のメンバを含む経路情報をハッシュ値に変換するハッシュ値計算部と、登録済みの経路情報を、該登録済みの経路情報のハッシュ値と共に保存する記憶部と、受信した経路情報のハッシュ値と、前記記憶部に保存されたハッシュ値とを比較する比較部と、前記比較部による比較結果に基づいて、受信した経路情報を登録するか否かを判定する登録判定部とを備えることを特徴とする。
【００１０】
本発明の中継装置では、複数のメンバで構成される経路情報と、その経路情報を変換したハッシュ値とを経路情報表に登録する。中継装置が新たに経路情報を受信すると、新たに受信した経路情報をハッシュ値に変換し、このハッシュ値と、経路情報表に登録済みのハッシュ値とを比較する。このため、中継装置は、全てのメンバを比較することなく、双方の経路情報が同一であるか否かを判定することができる。
【００１１】
本発明の中継装置では、前記比較部は、受信した経路情報のハッシュ値と、登録済みの経路情報のハッシュ値とが一致すると、当該登録済みの経路情報の各メンバと、前記受信した経路情報の各メンバとを更に比較することが好ましい。この場合、異なるメンバで構成される経路情報が、同じハッシュ値に変換された場合でも、双方の経路情報が同一であるか否かを正しく判断することができる。
【００１２】
また、本発明の中継装置では、前記比較部は、前記記憶部に保存された複数の経路情報を含む一の経路情報群のハッシュ値と、受信した複数の経路情報を含む他の経路情報群のハッシュ値とを比較することが好ましい。この場合、ハッシュ値計算部は、複数の経路情報を一まとめにした経路情報群をハッシュ値に変換し、比較部は、記憶部に記憶された経路情報を一まとめにした経路情報群のハッシュ値と、新たに受信した経路情報群のハッシュ値とを比較する。複数の経路情報をまとめて比較することで、双方の経路情報群が同一であるか否かの判定が容易に行なえる。
【００１３】
本発明の中継装置は、他の中継装置から定期的に前記他の経路情報群を受信して、該他の経路情報群のハッシュ値と、前記記憶部に保存された一の経路情報群のハッシュ値とを比較することが好ましい。この場合、他の中継装置が記憶する経路情報と同じ経路情報を記憶する中継装置が得られ、複数の中継装置が記憶する経路情報の整合を容易に行なうことができる。
【００１４】
【発明の実施の形態】
以下、図面を参照し、本発明の実施形態例に基づいて、本発明を更に詳細に説明する。図１は、本発明の第１実施形態例の中継装置における経路情報を登録する機能の構成をブロック図として示している。中継装置は、経路情報を収集して登録する機能を有し、経路情報受信部１０１、ハッシュ値計算部１０２、経路情報比較部１０３、経路情報キャッシュ部（メモリ）１０４、経路情報処理部１０５、及び、経路情報送信部１０６を備え、互いに異なるネットワーク間を中継する。
【００１５】
経路情報受信部１０１は、ネットワークから送信された経路情報を受信する。ハッシュ値計算部１０２は、受信された経路情報をハッシュ値に変換する。経路情報キャッシュ部１０４は、経路情報、及び、経路情報表を記憶する。経路情報表は、経路情報への参照値（ポインタ）と、ハッシュ変換されたハッシュ値とを対応付けて記憶する。経路情報比較部１０３は、新たに受信した経路情報と、経路情報キャッシュ部１０４に記憶されている経路情報とをハッシュ値を用いて比較し、双方の経路情報が同じ経路情報であるか否かを判断する。
【００１６】
経路情報比較部１０３の比較の結果、新たに受信した経路情報と同じ経路情報が、経路情報表に登録されていないと判定されると、経路情報処理部１０５は、新たに受信した経路情報を経路情報表に追加登録する。経路情報送信部１０６は、追加登録された経路情報を外部のネットワークに向けて送信する。経路情報比較部１０３の比較の結果、新たに受信した経路情報と同じ経路情報が、経路情報表に登録されていると判定されると、新たに受信した経路情報は破棄される。
【００１７】
図２は、本実施形態例の中継装置が受信する経路情報の構成例を示している。経路情報はデータの型（ｔｙｐｅ）、データのサイズ（Ｄａｔａ　ｓｉｚｅ）、経路情報中に含まれるグループアドレス（Ｇｒｏｕｐ　Ａｄｄｒｅｓｓ）、及び、ソースアドレス（Ｓｏｕｒｃｅ　Ａｄｄｒｅｓｓ）の組数を示すカウント（ｃｏｕｎｔ）、及び、ＲＰアドレス（ＲＰ　Ａｄｄｒｅｓｓ）の４つのメンバを含む固定部長部分と、グループアドレス及びソースアドレスが組となって１組以上が含まれる可変長部分とから構成される。
【００１８】
図３は、経路情報キャッシュ部１０４に記憶される経路情報表の構成を示している。本実施形態例の経路情報表は、経路情報のハッシュ値を有する点で、図１４に示す従来の経路情報表と相違する。各経路情報のハッシュ値は、図２に示す経路情報の固定長部分、及び、可変長部分を含む全てのメンバを合成したものをハッシュ変換することによって得られる。ハッシュ変換によって得られるハッシュ値は、値が異なるメンバで構成される経路情報が同じハッシュ値にならないように、その変換値の範囲（ビット長）が設定される。
【００１９】
図４は、図１の中継装置が経路情報を受信した際の動作手順をフローチャートとして示している。図５は、中継装置が受信する経路情報の具体例を示している。図６は、経路情報キャッシュ部１０４に記憶されている経路情報表、及び、経路情報の具体例を示している。図７は、図５に示す経路情報を、図６示す経路情報に追加登録した経路情報表の具体例を示している。以下、中継装置が新たに経路情報を受信した際の動作について、その具体例と共に説明する。
【００２０】
図４において、経路情報受信部１０１が外部のネットワークから送信された経路情報を受信すると（ステップＳ１）、受信された経路情報は、ハッシュ値計算部１０２によってハッシュ値に変換される（ステップＳ２）。例えば受信した経路情報が図５に示す経路情報であった場合、同図に示す全てのメンバを含む経路情報がハッシュ変換され、ハッシュ値「２２２２」が得られる。経路情報比較部１０３は、比較すべき経路情報が経路情報キャッシュ部１０４に存在するか否かを判断し（ステップＳ３）、比較対象の経路情報が存在する場合には、経路情報キャッシュ部１０４に記憶された経路情報表から、経路情報のハッシュ値を１つ選択する（ステップＳ４）。中継装置が図６に示す経路情報表を記憶している場合には、比較対象の経路情報として、まず、経路情報１が選択される。
【００２１】
経路情報比較部１０３は、新たに受信した経路情報のハッシュ値と、選択した経路情報のハッシュ値とが一致するか否か、つまり、双方の経路情報が同じであるか否かを判定する（ステップＳ５）。双方の経路情報のハッシュ値が一致する場合には、双方の経路情報が同じであると判定され、新たに受信した経路情報が破棄される（ステップＳ６）。図５に示す経路情報、及び、図６に示す経路情報１の例では、双方の経路情報は異なるため、図５に示す新たに受信した経路情報のハッシュ値（２２２２）と、図６に示す経路情報１のハッシュ値（１００１）とは一致しない。
【００２２】
双方の経路情報のハッシュ値が一致しない場合には、ステップＳ３へ戻り、経路情報比較部１０３は、比較すべき経路情報が経路情報キャッシュ部１０４に残っているか否かを再び判断する。図５に示す新たに受信した経路情報のハッシュ値（２２２２）は、ステップＳ３からステップＳ５までによって、図６に示す経路情報２のハッシュ値（１５００）、及び、経路情報３のハッシュ値（２０２０）と順次に比較される。ステップＳ５において、新たに受信した経路情報が経路情報３のハッシュ値と一致しないと判定されると、ステップＳ３に戻り、ステップＳ３では、経路情報表に比較すべき経路情報が残っていないと判断される。
【００２３】
ステップＳ３で比較すべき経路情報が残っていない、つまり、経路情報キャッシュ部１０４に記憶されている全ての経路情報のハッシュ値と、新たに受信した経路情報のハッシュ値とが一致しない場合には、新たに受信された経路情報は、経路情報処理部１０５によって経路情報キャッシュ部１０４へ追加登録される（ステップＳ７）。図６に示す経路情報表へ、図５に示す経路情報を追加登録すると、図７に示す更新された経路情報表が得られる。ステップＳ７で新たな経路情報が経路情報表に追加されると、新たに追加された経路情報は、経路情報送信部１０６によって外部のネットワークに向けて送信される（ステップＳ８）。
【００２４】
ここで、図７に示す更新された経路情報表を有する中継装置が、再び図５に示す経路情報を受信した場合には、ステップＳ５では、新たに受信した経路情報のハッシュ値（２２２２）と、経路情報４のハッシュ値（２２２２）とが一致すると判定される。中継装置は、新たに受信した経路情報と同じ経路情報を既に経路情報キャッシュ部１０４に記憶しているため、ステップＳ６へ移行し、新たに受信した経路情報を破棄する。
【００２５】
本実施形態例では、新たに受信した経路情報と、経路情報表に登録済みの経路情報とを、経路情報のハッシュ値を用いて比較する。このため、新たに受信した経路情報と一致する経路情報が、経路情報キャッシュ部１０４中に存在するか否かの判定を、双方の経路情報の全てのメンバ同士を比較することなく行なうことができ、判定に要する時間を短縮することができる。
【００２６】
中継装置は、プロトコルによっては同じ経路情報を何度も繰り返し受信するが、本実施形態例では、登録済みの経路情報と同じ経路情報を受信した際に、その経路情報を破棄するまでに要する時間を短縮することができる。経路情報は可変長のデータとして構成されるが、ハッシュ値は固定長であるため、値の比較が容易となり、中継装置の処理能力が向上する。また、ハッシュ値の計算は、１つの経路情報に対して１回だけ行なえばよいため、経路情報のメンバ数が多い場合でも、経路情報を破棄するか否かの判定に要する時間が増大しない。
【００２７】
図８は、本発明の第２実施形態例の中継装置が経路情報を受信した際の動作手順を示している。本実施形態例は、図４のステップＳ５に後続して、ハッシュ値が同じ経路情報のメンバ同士を比較するステップを有する点で、第１実施形態例と相違する。図９は、経路情報キャッシュ部１０４に記憶されている経路情報表、及び、経路情報の具体例を示している。図１０は、図５に示す経路情報を、図９に示す経路情報に追加登録した経路情報表の具体例を示している。以下、本実施形態例の中継装置が経路情報を受信した際の動作について、その具体例と共に説明する。
【００２８】
中継装置は、ステップＳ５で、新たに受信した経路情報と、経路情報キャッシュ部１０４に記憶された経路情報とをハッシュ値を用いて比較し、ハッシュ値が同じであると判定すると、双方の経路情報の全てのメンバ同士を比較し、双方の経路情報が同一であるか否かを判定する（ステップＳ９）。双方の経路情報が同一であると判断された場合には、新たに受信した経路情報は破棄される。
【００２９】
図９に示す経路情報を有する中継装置が、図５に示す経路情報を新たに受信した場合には、ステップＳ５において、新たに受信した経路情報のハッシュ値は、図９に示す経路情報３のハッシュ値と同じであると判定される。中継装置は、次いでステップＳ８において、図５に示す経路情報の各メンバと、図９に示す経路情報３の各メンバとをメンバ毎に比較する。この場合、双方のメンバは４つ目のメンバ（ＲＰアドレス）が一致しないため、双方の経路情報は同一ではないと判定される。
【００３０】
双方の経路情報が同一でないと判定された場合には、ステップＳ３へ戻り、経路情報キャッシュ部１０４に比較すべき経路情報が残っているか否かが判断される。比較すべき経路情報が残っていないときには、ステップＳ６において、新たに受信した経路情報は経路情報表に追加登録される。図５に示す経路情報を、図９に示す経路情報表に追加登録すると、図１０に示す更新された経路情報表が得られる。更新された経路情報表は、同じハッシュ値を持ち、異なるメンバで構成される経路情報を有する。
【００３１】
本実施形態例では、新たに受信した経路情報と、経路情報表に登録済みの経路情報とを、ハッシュ値を用いて比較し、双方の経路情報のハッシュ値が一致する場合には、それらの経路情報の全てのメンバ同士を比較する。このため、異なるメンバで構成される経路情報が同じハッシュ値に変換された場合であっても、正しく経路情報の比較を行なうことができる。
【００３２】
図１１は、本発明の第３実施形態例の中継装置が経路情報を受信した際の動作手順を示している。本実施形態例は、中継装置が複数の経路情報を有する経路情報群（集合体）を受信する点で、第１及び第２実施形態例と相違する。図１２は、本実施形態例の中継装置が受信する経路情報（集合体）の具体例を示している。図１３は、中継装置が受信する経路情報（集合体）の他の具体例を示している。以下、中継装置が新たな経路情報の集合体を受信した際の動作について、その具体例と共に説明する。
【００３３】
中継装置は、外部のネットワークから送信された経路情報の集合体を受信し（ステップＳ１０）、経路情報の集合体のハッシュ値を計算する（ステップＳ１１）。中継装置が新たに３つの経路情報が含まれる経路情報の集合体（図１２）を受信した場合には、ステップＳ１１では、ハッシュ値計算部１０２は経路情報の集合体のハッシュ値を計算し、そのハッシュ値（１２３４５）を得る。ハッシュ値計算部１０２は、経路情報キャッシュ部１０４に記憶されている経路情報を一まとめにした集合体からハッシュ値を計算する（ステップＳ１２）。中継装置が図６に示す３つの経路情報を記憶している場合には、ステップＳ１２では、３つの経路情報の各メンバを一まとまりにした集合体のハッシュ値を計算し、そのハッシュ値（１２３４５）を得る。
【００３４】
次いで、経路情報比較部１０３は、ステップＳ１２で計算されたハッシュ値と、ステップＳ１１で計算されたハッシュ値とを比較し（ステップＳ１３）、双方のハッシュ値が一致するか否かを判定する。双方のハッシュ値が一致すると判定されると、双方の経路情報の集合体は、同一の経路情報で構成されていると判断され、経路情報の集合体の破棄などの、経路情報の集合体の一致時の処理が行なわれる（ステップＳ１４）。図６に示す経路情報を経路情報キャッシュ部１０４に記憶する中継装置が、図１２に示す経路情報の集合体を受信した場合には、双方の経路情報の構成が同一であるため、双方のハッシュ値は一致する。
【００３５】
中継装置が図１３に示す経路情報の集合体を受信した場合には、ステップＳ２では、図１３に示す経路情報の集合体のハッシュ値（９８７６５）が計算される。中継装置が、図６に示す経路情報を記憶している場合には、双方の経路情報の構成が異なるため、ステップＳ１３では、双方のハッシュ値が一致しない。ステップＳ１３でハッシュ値が一致しないと判定されると、新たな経路情報を登録するための、経路情報の集合体の不一致時の処理が行なわれる（ステップＳ１４）。
【００３６】
本実施形態例では、複数の経路情報が含まれる経路情報の集合体を受信し、受信した経路情報の集合体と同じ経路情報が経路情報キャッシュ部１０４に記憶されているか否かを、ハッシュ値を用いて比較する。このため、経路情報数が多い場合であっても、双方に含まれる経路情報の比較に要する時間が増大しない。中継装置が、同じ経路情報を記憶すべき他の中継装置に向けて、自身が有する全ての経路情報を一まとめにして送信すると、経路情報を送信した中継装置と、経路情報を受信した他の中継装置とが記憶する経路情報が同一であるか否かが容易に確認できる。
【００３７】
以上、本発明をその好適な実施形態例に基づいて説明したが、本発明の中継装置は、上記実施形態例にのみ限定されるものでなく、上記実施形態例の構成から種々の修正及び変更を施した中継装置も、本発明の範囲に含まれる。
【００３８】
【発明の効果】
以上説明したように、本発明の中継装置は、ハッシュ値を用いて、新たに受信した経路情報が、経路情報表に登録済みであるか否かを判定する。このため、経路情報数や、経路情報のメンバ数が多い場合であっても、経路情報同士の比較に要する時間が増大しない。
【図面の簡単な説明】
【図１】本発明の第１実施形態例の中継装置の構成を示すブロック図。
【図２】図１の中継装置が受信する経路情報の構成例を示すブロック図。
【図３】図１の経路情報キャッシュ部１０４に記憶される経路情報表の構成例を示すブロック図。
【図４】図１の中継装置が経路情報を新たに受信した際の動作手順を示すフローチャート。
【図５】図１の中継装置が受信する経路情報の具体例を示すブロック図。
【図６】図１の経路情報キャッシュ部１０４に記憶されている経路情報表、及び、経路情報の具体例を示すブロック図。
【図７】図５に示す経路情報を、図６に示す経路情報に追加登録した経路情報表の具体例を示すブロック図。
【図８】本発明の第２実施形態例の中継装置が経路情報を受信した際の動作手順を示すフローチャート。
【図９】本発明の第２実施形態例における経路情報キャッシュ部１０４に記憶されている経路情報表、及び、経路情報の具体例を示すブロック図。
【図１０】図５に示す経路情報を、図９に示す経路情報に追加登録した経路情報表の具体例を示すブロック図。
【図１１】本発明の第３実施形態例の中継装置が経路情報を受信した際の動作手順を示すフローチャート。
【図１２】本発明の第３実施形態例の中継装置が受信する経路情報（集合体）の具体例を示すブロック図。
【図１３】本発明の第３実施形態例の中継装置が受信する経路情報（集合体）の他の具体例を示すブロック図。
【図１４】従来の中継装置における、メモリに記憶される経路情報表の構成を示すブロック図。
【図１５】従来の中継装置が経路情報を登録する際の動作手順を示すフローチャート。
【符号の説明】
１０１：経路情報受信部
１０２：ハッシュ計算部
１０３：経路情報比較部
１０４：経路情報キャッシュ部
１０５：経路情報処理部
１０６：経路情報送信部
【図１】
2004040551.tif 000003
【図２】
2004040551.tif 000004
【図３】
2004040551.tif 000005
【図４】
2004040551.tif 000006
【図５】
2004040551.tif 000007
【図６】
2004040551.tif 000008
【図７】
2004040551.tif 000009
【図８】
2004040551.tif 000010
【図９】
2004040551.tif 000011
【図１０】
2004040551.tif 000012
【図１１】
2004040551.tif 000013
【図１２】
2004040551.tif 000014
【図１３】
2004040551.tif 000015
【図１４】
2004040551.tif 000016
【図１５】
2004040551.tif 000017