(57)【特許請求の範囲】
【請求項１】
受信したパケットの情報と保持している経路計算の基となる中継基礎情報により経路計算して、特定のパケットを中継するための中継確定情報を生成し、該生成された中継確定情報によりパケットの中継を行うパケット中継方法において、
経路計算前に中継基礎情報を基に中継方路を決定し、パケットを中継して経路計算を行い、中継確定情報を生成し、次以降の同宛先パケットを該中継確定情報に従い中継することを特徴とするパケット中継方法。
【請求項２】
１つ以上の物理もしくは論理インタフェースと、あるインタフェースから受信したパケットを、特定のパケットを中継するための登録済みの中継確定情報に従い中継するフォワーディング部と、パケットの情報と保持している経路計算の基となる中継基礎情報により経路計算して中継確定情報を生成する経路計算部とを具備するパケット中継装置において、
フォワーディング部は、中継確定情報に未登録の宛先のパケットを受信した場合に、中継基礎情報から中継方路を計算して該パケットを中継するとともに、当該パケットの情報を経路計算部に報告し、
経路計算部は、フォワーディング部から報告されたパケット情報と中継基礎情報により新たな中継確定情報を生成し、次以降の同宛先パケットの中継確定情報として登録する、
ことを特徴とするパケット中継装置。
【請求項３】
１つ以上の物理もしくは論理インタフェースと、あるインタフェースから受信したパケットを、特定のパケットを中継するための登録済みの中継確定情報に従い中継するフォワーディング部と、パケットの情報と保持している経路計算の基となる中継基礎情報により経路計算して中継確定情報を生成する経路計算部とを具備するパケット中継装置において、
フォワーディング部は、中継確定情報に未登録の宛先のパケットを受信した場合に、中継基礎情報から中継方路を計算して該中継方路を次以降の同宛先パケットの一時的な中継確定情報として登録し、該パケットを中継するとともに、当該パケットの情報を経路計算部に報告し、
経路計算部は、フォワーディング部から報告されたパケット情報と中継基礎情報により新たな中継確定情報を生成し、同宛先パケットの中継確定情報として登録する、
ことを特徴とするパケット中継装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、中継パケットの情報を中継方路選択に使用するパケット中継方法及びパケット中継装置に係わり、特にマルチキャスト通信に好適なパケット中継方法及びパケット中継装置に関する。
【０００２】
【従来の技術】
マルチキャスト通信とは、１つの計算機（ノード）がグループ宛に送信したパケットをそのグループに属する複数の計算機（ノード）のすべてに中継伝達するものである。図６にマルチキャスト通信の概念図を示す。図６では、ソースＳの計算機（１５０）が送信したパケットが同一グループＧのすべての計算機（１５１〜１５７）に中継伝達されることを示している。グループとは、マルチキャストの通信単位であり、パケット中継装置は１つのグループに対し、複数の中継インタフェースを保持している。基本的に、マルチキャスト通信では、同一のパケットを同一の計算機およびパケット中継装置に中継させない。ゆえに、パケット中継装置の入インタフェースは必ず１インタフェースである。ただし、ルーティングプロトコルのルート解決段階においてはその限りではない。図６のマルチキャスト通信では、グループ宛パケットを受信したパケット中継装置（ルータ）Ｒは、マルチキャストルーティングの冗長経路であるＲ１とＲ４間（１５８）、Ｒ４とＲ３間（１５９）、Ｒ２とＲ３間（１６０）、Ｒ６とＲ９間（１６１）、Ｒ８とＲ９間（１６２）にはパケット（ＩＰデータグラム）を中継しない。また、例えばＲ７（１６６）を考えると、データの流れを発信元側（１６３）を上流とし、宛先側を下流（１６４，１６５）とした場合、１つのパケット中継装置の上流に位置する計算機（１５１）に対しては、より上流のパケット中継装置（１６７）が中継するため、上流側（１６３）に中継する必要はない。
【０００３】
従来のマルチキャスト通信を実現するパケット中継装置について、図１７に従い説明する。パケット中継装置は、１つ以上の物理もしくは論理インタフェース（ここでは２２１〜２２６）を持ち、大きくフォワーディング部（２３５）と経路計算部（２３６）に分かれる。一般に経路計算部（２３６）は複数のフォワーディング部（２３５）を管理する。
【０００４】
フォワーディング部（２３５）は、特定のパケットを中継するための中継確定情報（２３４）を持ち、１つのインタフェース（２２１）から受信したパケット（２２７）のアドレス情報と、中継確定情報（２３４）のアドレス部を比較し、一致する中継確定情報のエントリの出インタフェース部に従い中継動作を行う。中継確定情報（２３４）には、過去に受信したパケットについて、経路計算部（２３６）により経路計算した結果が登録される。
【０００５】
経路計算部（２３６）は、発信元情報が正しいインタフェースから受信しているかを確認するための発信元情報（２４０）と、宛先により中継先を示す宛先情報（２４１）からなる中継基礎情報（２２０）を持つ。この中継基礎情報（２２０）の発信元情報（２４０）の入インタフェース部には、その発信元に最適のインタフェースを登録する。中継基礎情報（２２０）の宛先情報（２４１）の宛先部にはグループアドレスを登録し、出インタフェース部にはそのグループに中継するための最適の複数のインタフェースを登録する。この中継基礎情報（２２０）は、ユーザが設定する場合や、ルーティングプロトコルなどで装置間で解決する場合がある。
【０００６】
このような構成のパケット中継装置において、従来技術の場合、フォワーディング部（２３５）は、中継確定情報（２３４）に未登録の宛先のパケット（２３２）を受信した場合、当該パケット（２３２）を中継待ちキュー（２３７）に登録し、経路計算部（２３６）に、該受信パケット（２３２）のアドレス情報と受信インタフェース情報からなる不一致宛先情報（２３３）を報告する。経路計算部（２３６）は、フォワーディング部（２３５）から中継確定情報（２３４）に一致するアドレス部が存在しないことを示す不一致宛先情報（２３３）を受け取ると、該不一致宛先情報（２３３）内のアドレス情報に含まれる発信元情報および宛先情報と経路計算部内の中継基礎情報（２２０）の発信元情報（２４０）および宛先情報（２４１）を１エントリずつ比較し、受信方路の正当性の確認と中継先を算出し、宛先情報（２４１）の出インタフェース部から入インタフェースを削除して、フォワーディング部（２３５）に新たな中継確定情報エントリ追加要求（２３８）を発行する。フォワーディング部（２３５）は、経路計算部（２３６）からの中継確定情報エントリ追加要求（２３８）の内容を新たに中継確定情報（２３４）として格納し（２４２）、中継待ちキュー（２３７）に登録しているパケットから、この経路計算部（２３６）が新たに配布した中継確定情報（２３４）のアドレス部（２３９）と一致する宛先のパケット（２２７）を中継確定情報（２３４）に従い（２４３）、インタフェース（２２２，２２３，２２４，２２６）に中継する（２２８〜２３１）。そして、次に到着する同宛先を持つ中継パケットは新規に追加された中継確定情報に従い中継する。
【０００７】
もし、フォワーディング部（２３５）から報告された不一致宛先情報（２３３）に対して、経路計算部（２３６）での経路計算において、新たな中継確定情報が生成できなかった場合は、経路計算部（２３６）は中継確定情報作成不可報告をフォワーディング部（２３５）に報告する。フォワーディング部（２３５）は中継確定情報作成不可報告を受けると、中継待ちキュー（２３７）から該中継確定情報作成不可報告で指定されたパケットを削除する。
【０００８】
なお、図には示されていないが、経路計算部（２３６）は中継確定情報（２３４）を管理しており、ネットワークなどの状態変化に応じてフォワーディング部（２３５）へ中継確定情報（２３４）の変更も指示する。
【０００９】
【発明が解決しようとする課題】
このように、従来のパケット中継装置においては、フォワーディング部の中継確定情報に未登録の宛先のパケットを受信した場合、フォワーディング部では当該受信パケットを中継待ちキューに登録して、経路計算部に不一致宛先情報を報告し、経路計算部からの新たな中継確定情報あるいは生成不可通知を待って、受信パケットの中継あるいは削除を行うため、パケット中継の伝送遅延が発生し、さらに、中継待ちキューが有限であることから輻輳時などで溢れが生じ、中継すべきパケットが破棄されるという問題があった。また、経路計算部では、フォワーディング部から不一致宛先情報を受け取ると、逐一経路計算を実行するため、新たな中継確定情報が生成できなかった場合は、はじめから中継不可能なパケットの経路計算を経路計算部で行うといった冗長処理の問題があった。
【００１０】
本発明は、上記従来のパケット中継装置の問題に鑑み、中継確定情報に未登録の宛先のパケットを受信した場合の、フォワーディング部での経路計算部からの中継確定情報配布待ちによる中継パケットの伝送遅延の発生や中継待ちキュー溢れによるパケット廃棄の発生、さらには、経路計算部での冗長な経路計算処理の発生等を防止・軽減することを目的とすることにある。
【００１１】
【課題を解決するための手段】
上記目的を達成するために、本発明では、経路計算とパケット中継の処理の順番を換えて、経路計算前に中継基礎情報を基に中継方路を決定し、パケットを中継した後で経路計算を行い、中継確定情報を生成することにより、次以降の同宛先パケットを該中継確定情報に従い中継するようにする。
【００１２】
具体的には経路計算部は、ユーザの固定設定した中継基礎情報、あるいは隣接するパケット中継装置または計算機同士の通信により収集した経路情報により生成した中継基礎情報をあらかじめフォワーディング部に配布し、フォワーディング部は、宛先が中継確定情報に存在しないパケットを受信した場合、この経路計算部からあらかじめ配布されている中継基礎情報を利用して中継方路を計算し、当該パケットを中継待ちキューに格納することなく中継または廃棄する。それと同時にフォワーディング部は、この宛先が中継確定情報に存在しない受信パケット情報を含む不一致宛先情報を経路計算部に報告し、経路計算部は、保持している中継基礎情報とフォワーディング部から受けた不一致宛先情報の受信パケット情報により新たな中継確定情報を正式に作成し、フォワーディング部に配布する。次到着の同一宛先パケットは、フォワーディング部で、この経路計算部から配布された中継確定情報に従い中継する。
【００１３】
これにより、中継確定情報に未登録の宛先パケットを受信した場合、経路計算によるパケット中継の遅延や中継待ちキュー溢れによるパケット破棄がなくなり、また、中継不可能なパケットは、フォワーディング部で廃棄するため、経路計算部に報告する必要がなくなることにより冗長処理も削減できる。
【００１４】
また、本発明の別の構成では、フォワーディング部が決定した中継方路をフォワーディング部で一時的に中継確定情報として登録しておき、経路計算部へ報告した不一致宛先情報に対応する中継確定情報が経路計算部から配布される以前に、フォワーディング部が次到着の同一宛先パケットを受信した場合、フォワーディング部で一時的に登録した中継確定情報に従い中継する。これにより、フォワーディング部は、経路計算部へ冗長な不一致宛先情報を報告することを削除でき、また、経路計算部は、冗長な不一致宛先情報の報告による冗長な経路計算を削除できる。
【００１５】
なお、フォワーディング部は少なくとも最初の不一致宛先情報を経路計算部に報告し、経路計算部にて中継確定情報を正式に作成してフォワーディング部に配布するため、経路計算部で管理する中継確定情報とフォワーディング部の中継確定情報の一致性が保証される。
【００１６】
【発明の実施の形態】
以下、本発明の実施形態について図面を参照して説明する。
図１は、本発明によるパケット中継装置の第一の実施形態の機能ブロック図である。本パケット中継装置は、図１７と同様に、６つのインタフェース（１１〜１６）を持ち、大きく、パケットの中継経路を計算する経路計算部（１）とパケットを中継するフォワーディング部（２）に分かれる。経路計算部（１）とフォワーディング部（２）は、経路計算と中継処理の同時動作を可能にするため、それぞれ異なるプロセッサにより実現するのが好ましいが、単一プロセッサの別タスクモジュールに分けることでもよい。
【００１７】
経路計算部（１）は、中継経路を計算する基となる中継基礎情報（３）の更新と、中継基礎情報（３）を使い経路計算した結果である特定パケットの中継方路を格納した中継確定情報の生成と管理、フォワーディング部（２）への中継確定情報（２６）と中継基礎情報（６）の登録および更新を行う。本実施例では、中継基礎情報（３）は、このネットワーク内の受信パケットの受信方路の正当性をチェックするための発信元情報（４）と受信パケットの中継先を示す宛先情報（５）からなる。プロトコル情報（２９）については後述する。一般に経路計算部（１）は複数のフォワーディング部（２）を管理し、より信頼性を高める場合には、現用と予備の二重化構成がとられる。
【００１８】
フォワーディング部（２）は、受信したパケットを中継確定情報（２６）に従い中継するが、中継確定情報（２６）に受信パケットの発信元情報と宛先情報が一致するエントリが存在しなければ、経路計算部（１）からあらかじめ配布されている中継基礎情報（６）を用いて中継先を計算し、該パケットを中継する。その後、中継確定情報（２６）に存在しないパケットを中継したことを経路計算部（１）に不一致宛先情報（２７）として報告する。経路計算部（１）が不一致宛先情報（２７）と中継基礎情報（３）から計算し作成した中継確定情報エントリ追加要求（２８）をフォワーディング部（２）に発行すると、フォワーディング部（２）は、該中継確定情報エントリ追加要求（２８）から中継確定情報（２６）に新たなエントリを追加する。
【００１９】
次以降の同宛先パケットを受信した場合、フォワーディング部（２）では、この新たに追加された中継確定情報に従い当該パケットを中継する。図２はこれを示している。また、フォワーディング部（２）は、もし中継基礎情報（６）を用いても中継方路を決定できない場合、当該パケットを破棄する。図３はこれを示している。
【００２０】
中継確定情報（２６）および中継基礎情報（３，６）の検索情報は、発信元情報と宛先情報を持っており、経路計算部（１）とフォワーディング部（２）では受信パケットの発信元情報と宛先情報を比較して経路計算を行う。
【００２１】
中継確定情報（２６）と中継基礎情報（３，６）は、１つの発信元情報の入インタフェースエントリに対し、１つ以上の出インタフェースを登録でき、フォワーディング部（２）は、１つの入インタフェースから受信した１つのパケットを別の複数の出インタフェースにコピーし送信することによりマルチキャスト中継を実現する。
【００２２】
以下では、本パケット中継装置が、ＩＰ（Ｉnternet Ｐrotocol）マルチキャスト通信のネットワークでＩＰルータとして使用されるとする。
【００２３】
図５は、ＩＰマルチキャスト対応のネットワークシステムを示し、Ｒ１からＲ６（１２０〜１２５）がＩＰマルチキャスト対応のルータである。ルータとはＩＰプロトコルの通信単位パケットであるＩＰデータグラムを中継する装置である。図５のシステムにおいて、Ｓ１からＳ９（１２６〜１３４）は、ＩＰマルチキャストプロトコル対応の計算機であり、ＩＰデータグラムの発信者および受信者である。Ｇ１からＧ３（１３５〜１３７）はＩＰマルチキャスト通信の通信範囲を示し、Ｇ１（１３５）にはＳ１（１２６），Ｓ３（１２８），Ｓ９（１３４）が属し、Ｇ２（１３６）にはＳ３（１２８），Ｓ４（１２９），Ｓ８（１３３），Ｓ９（１３４）が属し、Ｇ３（１３７）にはＳ２（１２７），Ｓ５（１３０），Ｓ６（１３１），Ｓ７（１３２），Ｓ８（１３３）が属する。このシステムでは、Ｇ１（１３５）宛に送信したＩＰデータグラムは、Ｓ１（１２６），Ｓ３（１２８），Ｓ９（１３４）に中継され、Ｇ２（１３６）宛に送信したＩＰデータグラムは、Ｓ３（１２８），Ｓ４（１２９），Ｓ８（１３３），Ｓ９（１３４）に中継され、Ｇ３（１３７）宛に送信したＩＰデータグラムは、Ｓ２（１２７），Ｓ５（１３０），Ｓ６（１３１），Ｓ７（１３２），Ｓ８（１３３）に中継される。ルータＲ１（１２０）は６つのインタフェース（１１〜１６）を有し、インタフェースａ（１１）はルータＲ２（１２１）、インタフェースｂ（１２）はルータＲ６（１２５）、インタフェースｃ（１３）はルータＲ４（１２３）、インタフェースｄ（１４）は計算機Ｓ３（１２８）、インタフェースｅ（１５）は計算機Ｓ４（１２９）、インタフェースｆ（１６）はルータＲ５（１２４）とそれぞれ接続している。
【００２４】
マルチキャスト通信経路情報は、各ルータに予めユーザが設定する方式と、ルーティングプロトコルによりルータ間で情報の受け渡しを行い、自動的にマルチキャスト通信経路を計算する方式がある。ここで、ルーティングプロトコルＸとルーティングプロトコルＹの２つのマルチキャストルーティングプロトコルが存在すると仮定する。
【００２５】
図７および図８はルーティングプロトコルＸの動作を説明したものである。ルーティングプロトコルＸ（９）とは、図７で示す様にルータＲ１（１７６）は、自管理インタフェースの１つから受信したＩＰデータグラム（１７０）を受信したインタフェースを除くすべての自管理インタフェース（１７１〜１７３）に中継する。その中継されたルータがその中継されたＩＰデータグラムの宛先グループへ属するインタフェースが存在しないルータ（１７４）は、そのＩＰデータグラムを中継したルータに対してその発信元アドレスと宛先グループのＩＰデータグラムの中継拒否の刈込要求（１７５）を送信する。刈込要求（１７５）を受信したＩＰルータ（１７６）は以後、図８で示す様にその拒否された発信元アドレスと宛先グループを持つＩＰデータグラム（１８０）を受信すると、刈込要求を受信したインタフェース（１８１）には中継しない。
【００２６】
図９および図１０は、ルーティングプロトコルＹの動作を説明したものである。ルーティングプロトコルＹ（１０）は、図９で示す様にあらかじめ、あるグループのＩＰデータグラムの中継を希望する計算機（１９０，１９１）またはルータ（１９２，１９３）がグループ情報を含むグループ登録要求（１９４〜１９７）をルータ（１９２，１９３，１９８）に発行する。グループ登録要求を受信したルータ（１９２，１９３，１９８）はグループ登録要求（１９４〜１９７）を受信したインタフェースとグループ登録要求（１９４〜１９７）に含まれるグループ情報を登録する。その後、図１０で示す様に、以後登録しているグループ情報と一致する宛先のＩＰデータグラム（２００）を受信した場合、グループ登録要求を受信したインタフェース（２０１，２０２）のうち、ＩＰデータグラムを受信したインタフェース（２０３）以外のインタフェースに対して送信する。
【００２７】
図１１は、ＩＰデータグラムのヘッダフォーマットである。マルチキャスト通信において、発信元アドレスは、ＩＰデータグラムヘッダの発信元アドレスフィールド（２１０）に格納され、マルチキャストのグループアドレスは、ＩＰデータグラムヘッダの宛先アドレスフィールド（２１１）に格納される。宛名グループアドレスは、既存（クラスＡ〜Ｃ）のＩＰ宛先アドレスとの共存および区別をするためにクラスＤのアドレスが使用される。クラスＤのアドレスフォーマットを図１２に示す。図１２で先頭４ビットの「１１１０」がクラスＤを意味する。なお、クラスＡは先頭１ビットが「０」、クラスＢは先頭２ビットが「１０」、クラスＣは先頭３ビットが「１１０」である。
【００２８】
図５のシステムにおいて、ルータＲ１（１２０）は、インタフェースａ（１１）とインタフェースｂ（１２）とインタフェースｃ（１３）にはルーティングプロトコルＸ（９）が動作しており、インタフェースｄ（１４）とインタフェースｅ（１５）とインタフェースｆ（１６）にはルーティングプロトコルＹ（１０）が動作している。この２つのプロトコルＸ，Ｙは異なるが、同一のグループは互いに通信可能である必要がある。
【００２９】
図１に示した実施形態のパケット中継装置は、図５に示したネットワークシステムにおいてルータＲ１（１２０）に該当するものである。即ち、図１において、図５に示したようにインタフェースａ，ｂ，ｃ（１１，１２，１３）側のネットワークにはルーティングプロトコルＸ（９）が動作し、インタフェースｄ，ｅ，ｆ（１４，１５，１６）側のネットワークにはルーティングプロトコルＹ（１０）が動作している。このインタフェース毎のプロトコル情報を、プロトコル情報（２９）として、経路計算部（１）が管理している。
【００３０】
経路計算部（１）は隣接するＩＰルータの経路計算部とのルーティングプロトコルによる情報交換によって中継基礎情報（３）を収集する。このとき、ルーティングプロトコルを使用せず、ネットワーク情報をユーザが固定値入力により設定する場合もある。
【００３１】
ここで、経路計算部（１）は、中継基礎情報（３）の送信元情報（４）に、そのネットワークにもっとも近いインタフェースを登録する。図５のシステムの場合、ルータＲ１（１２０）の計算機Ｓ１（１２６）からの中継方路は、インタフェースａ（１１）とインタフェースｃ（１３）が中継可能であるが、インタフェースａ（１１）がルータＲ２（１２１）の１段中継に対して、インタフェースｃ（１３）はルータＲ２（１２１），Ｒ３（１２２），Ｒ４（１２３）と３段中継で到達するため、図１で示すように、発信元情報（４）のソース部がＳ１エントリ（１７）の入インタフェース部には、インタフェースａ（１１）が登録され、出インタフェース部には、ルーティングプロトコルＸ（９）が動作する全てのインタフェース（ａ（１１），ｂ（１２），ｃ（１３））のうち、入インタフェースであるインタフェースａ（１１）を除く全てのインタフェースｂ（１２），ｃ（１３）を登録する。また、図５の計算機Ｓ５（１３０）の様に、ルータＲ１（１２０）のインタフェースａ（１１）とインタフェースｃ（１３）の計算機Ｓ５（１３０）までの距離が２段中継で等しい場合は、ルータＲ１（１２０）からみたアドレスなどの情報からどちらか１つを選択する。ここでは、ルータＲ１（１２０）のインタフェースａ（１１）に接続しているルータＲ２（１２１）のインタフェース（１１）のＩＰアドレスがルータＲ１（１２０）のインタフェースｃ（１３）に接続しているルータＲ４（１２３）のインタフェース（１３）のＩＰアドレスより小さいものとし、ＩＰアドレスが小さいほうを選択するとする。よって、図１で示す様に、発信元情報（４）のソース部がＳ５のエントリ（１８）の入インタフェース部には、インタフェースａ（１１）を登録し、出インタフェースには、インタフェースｂ（１２），ｃ（１３）を登録する。
【００３２】
以上のことから、ルーティングプロトコルＸ（９）のネットワークとルーティングプロトコルＹ（１０）のネットワークで同一グループ間を相互に通信可能にするためには、ルーティングプロトコルＹ（１０）のネットワークのインタフェースから受信するＩＰデータグラムをルーティングプロトコルＸ（９）のネットワークのすべてのインタフェース（１１，１２，１３）に中継しなければならない。そのため、ルーティングプロトコルＸ（９）が動作する全てのインタフェースをプロトコル情報（２９）のプロトコルＸエントリから取り出し、宛先情報（５）の登録インタフェース部に追加して登録する。
【００３３】
図１において、経路計算部（１）は収集した発信元情報（４）と宛先情報（５）から、中継基礎情報（３）を生成し、フォワーディング部（２）に配布する（１９）。その結果、中継基礎情報（３，６）は経路計算部（１）とフォワーディング部（２）で同一のものとなる。また、経路計算部（１）は、ルーティングプロトコルＸ（９）による新たな送信元の発見や、ルーティングプロトコルＹ（１０）のグループ参加要求により、中継基礎情報（３）に変更があった場合も、フォワーディング部（２）に中継基礎情報（３）を再配布し（１９）、常に経路計算部（１）とフォワーディング部（２）の中継基礎情報（３，６）を同一に保つ。
【００３４】
図４は、図１に示した本発明の第一の実施形態のパケット中継装置において、フォワーディング部（２）がＩＰデータグラムを受信したときの動作のフローチャートである。以下、図１乃至図４を参照して、第一の実施形態のフォワーディング部（２）の動作を詳述する。
【００３５】
インタフェースａ（１１）から受信したＩＰデータグラム（２５）のＩＰヘッダに含まれる発信元であるソースアドレス及び宛先であるグループアドレスとフォワーディング部（２）の中継確定情報（２６）のソースアドレス及びグループアドレスを１エントリずつ比較する（ステップ９０）。もし、ＩＰデータグラム（２５）のヘッダ中のソースアドレスとグループアドレスがそれぞれ一致するエントリが中継確定情報（２６）中に存在すれば（ケース１０５）、そのエントリ中の入インタフェースがそのＩＰデータグラムを受信したインタフェース（１１）と一致しているか確認する（ステップ１０１）。もし、受信したＩＰデータグラム（２５）のＩＰヘッダ中のソースアドレスとグループアドレスが中継確定情報（２６）エントリのアドレス部と一致し、同エントリの入インタフェース部がＩＰデータグラムの受信インタフェース（１１）と違っていた場合（ケース１０６）は、そのＩＰデータグラムを廃棄する（ステップ１０２）。中継確定情報（２６）にソースアドレスとグループアドレスと入インタフェースが一致したエントリが存在すれば（ケース１１５）、フォワーディング部（２）は同エントリの出インタフェース部に登録している１つ以上のインタフェースにＩＰデータグラムを送信する（ステップ１０３）。このとき、出インタフェースが２つ以上登録されていたら、ＩＰデータグラムをコピーし、２つ以上のインタフェースに同一のＩＰデータグラムを送信する（図１の１２，１３，１４，１６）。この時、ＴＴＬなどのインタフェース毎情報によりＩＰデータグラムヘッダを変更する場合もある。  また、受信したＩＰデータグラム（２５）のＩＰヘッダ中のソースアドレスとグループアドレスが、中継確定情報（２６）のアドレス部と一致しない場合（ケース１０４）は、ＩＰデータグラムのソースアドレスと中継基礎情報（６）の発信元情報（７）のアドレス部を１エントリずつ比較し（ステップ９１）、一致するエントリが存在すれば（ケース１０８）、そのエントリの入インタフェース部（インタフェースａ（１１））とＩＰデータグラム（２５）の受信インタフェース（インタフェースａ（１１））を比較する（ステップ９２）。ここでインタフェースが不一致であれば（ケース１０９）、図３の６１に示すように、受信したＩＰデータグラム（６０）を廃棄する（１００）。インタフェースが一致していれば（ケース１１０）、そのエントリの出インタフェース部（インタフェースｂ（１２），ｃ（１３））を取り出す（ステップ９３）。
【００３６】
さらに、ＩＰデータグラム（２５）の宛先アドレスと中継基礎情報（６）の宛先情報部（８）のグループ部を比較し（ステップ９４）、一致するエントリがあれば（ケース１１１）、そのエントリの登録インタフェース部（インタフェースａ（１１），ｂ（１２），ｃ（１３），ｄ（１４），ｆ（１６））を取り出し、前の中継基礎情報（６）の発信元情報（７）から取り出した出インタフェース部との論理和をとり（ステップ９５）、ＩＰデータグラムの入インタフェース（インタフェースａ（１１））を削除し（ステップ９６）、出インタフェースを決定する（インタフェースｂ（１２），ｃ（１３），ｄ（１４），ｆ（１６））。中継基礎情報（６）の宛先情報部（８）のグループ部に一致するエントリが存在しなければ（ケース１１２）、前の中継基礎情報（６）の発信元情報から取り出した出インタフェース部のみを出インタフェースとする。
【００３７】
ＩＰデータグラム（２５）のソースアドレスと中継基礎情報（６）の発信元情報（７）のアドレス部の比較（９１）で、一致するエントリが存在しなかった場合（ケース１０７）は、出インタフェースなしとし、ＩＰデータグラム（２５）のグループアドレスと中継基礎情報（６）の宛先情報部（８）のグループ部を比較し（ステップ９４）、一致するエントリがあれば（ケース１１１）、そのエントリの登録インタフェース部を取り出し、形式上論理和をとり（ステップ９５）、ＩＰデータグラムの入インタフェースを削除し（ステップ９６）、出インタフェースを決定する。中継基礎情報（６）の宛先情報部（８）のグループ部に一致するエントリが存在しなければ（ケース１１２）、ここでも出インタフェースなしとなる。
【００３８】
ここでは、中継基礎情報（６）の発信元情報（７）と宛先情報（８）の比較を行っているが、中継基礎情報（６）の発信元情報（７）のみの比較でのパケット中継装置や、中継基礎情報（６）の宛先情報（８）のみの比較でのパケット中継装置も実現できる。中継基礎情報（６）の発信元情報（７）のみの比較でのパケット中継装置は、上記例での中継基礎情報（６）の宛先情報部（８）のグループ部不一致と同じ動作（ケース１１２）を行い、中継基礎情報（６）の宛先情報部（８）のみの比較でのパケット中継装置は、上記例での中継基礎情報（６）の発信元情報（７）のアドレス部不一致と同じ動作（ケース１０７）を行えばよい。
【００３９】
次に、算出した出インタフェースが存在するか判定し（ステップ９７）、１つ以上のインタフェースが存在すれば（ケース１１４）、出インタフェースのすべてのインタフェースに対し受信ＩＰデータグラムを送信する（ステップ９８）。出インタフェースに２つ以上のインタフェースが登録していたら受信ＩＰデータグラムをコピーし、２つ以上のインタフェースに同一のＩＰデータグラムを送信する（図１の２１〜２４）。算出した出インタフェースにインタフェースが存在しなければ（ケース１１３）、受信ＩＰデータグラムを削除する（ステップ１００）。
【００４０】
出インタフェースにインタフェースが存在し（ケース１１４）、中継基礎情報（６）を用い、受信ＩＰデータグラムを出インタフェースに従い送信した場合（ステップ９８）、フォワーディング部（２）は受信したＩＰデータグラム（２５）のソースアドレスとグループアドレスと入インタフェースからなる不一致宛先情報（２７）を共に経路計算部（１）へ報告する（ステップ９９）。
【００４１】
図４のフローチャートは、基本的に、受信ＩＤデータグラムを不一致宛先情報に置き替えれば、経路計算部（１）での処理にも適用できる。
すなわち、経路計算部（１）では、不一致宛先情報（２７）のソースアドレスと中継基礎情報（３）の発信元情報（４）のアドレス部を１エントリずつ比較し、一致するエントリが存在すれば（ケース１０８）、そのエントリの入インタフェース部（インタフェースａ（１１））と不一致宛先情報（２７）の入インタフェース（インタフェースａ（１１））を比較する。ここでインタフェースが不一致であれば（ケース１０９）、不一致宛先情報（２７）を廃棄する。インタフェースが一致していれば、そのエントリの出インタフェース部（インタフェースｂ（１２），ｃ（１３））を取り出す。さらに、不一致宛先情報（２７）の宛先アドレスと中継基礎情報（３）の宛先情報部（５）のグループ部を比較し、一致するエントリがあれば（ケース１１１）、そのエントリの登録インタフェース部（インタフェースａ（１１），ｂ（１２），ｃ（１３），ｄ（１４），ｆ（１６））を取り出し、前の中継基礎情報（３）の発信元情報（４）から取り出した出インタフェース部との論理和をとり、入インタフェース（インタフェースａ（１１））を削除し、出インタフェースを決定する（インタフェースｂ（１２），ｃ（１３），ｄ（１４），ｆ（１６））。中継基礎情報（３）の宛先情報部（５）のグループ部に一致するエントリが存在しなければ（ケース１１２）、前の中継基礎情報（３）の発信元情報（４）から取り出した出インタフェース部のみを出インタフェースとする。
【００４２】
不一致宛先情報（２７）のソースアドレスと中継基礎情報（３）の発信元情報（４）のアドレス部の比較で、一致するエントリが存在しなかった場合（ケース１０７）は、不一致宛先情報（２７）のグループアドレスと中継基礎情報（３）の宛先情報部（５）のグループ部を比較し、一致するエントリがあれば（ケース１１１）、そのエントリの登録インタフェース部を取り出し、前の中継基礎情報（３）の発信元情報（４）から取り出した出インタフェース部との論理和をとり、入インタフェースを削除する。
【００４３】
経路計算部（１）においても、中継基礎情報（３）の発信元情報（４）のみの比較でのパケット中継装置は、上記例での中継基礎情報（３）の宛先情報部（５）のグループ部不一致と同じ動作を行い、中継基礎情報（３）の宛先情報部（５）のみの比較でのパケット中継装置は、上記例での中継基礎情報（６）の発信元情報（４）のアドレス部不一致と同じ動作を行うようにすればよい。
【００４４】
算出した出インタフェースに１つ以上のインタフェースが存在すれば、不一致宛先情報（２７）のソースアドレスとグループアドレスと入インタフェースと上記算出した出インタフェースにより中継確定情報エントリ追加要求（２８）を作成しフォワーディング部（２）へ配布する。算出した出インタフェースにインタフェースが存在しなければ、不一致宛先情報通知（２７）を廃棄する。
【００４５】
フォワーディング部（２）は経路計算部（１）から配布された中継確定情報エントリ（２８）を中継確定情報（２６）に登録する。
【００４６】
中継確定情報（２６）の管理元は経路計算部（１）であり、ソースアドレス、グループアドレスのペアで発生する状況変化の検出と、それに伴う中継確定情報（２６）への反映とフォワーディング部（２）への配布は経路計算部（１）が行う。これは、ルーティングプロトコルＸ（９）による刈込要求や、ルーティングプロトコルＹ（１０）によるグループ参加要求などである。
【００４７】
フォワーディング部（２）では、その後、図２で示した様に、上記処理で中継したものと同一のソースアドレスとグループアドレスをもつＩＰデータグラム（４０）が到着した場合、該フォワーディング部（２）の中継確定情報（４５）に一致し、出インタフェースに従いＩＰデータグラムを送信する（４１〜４４）。
【００４８】
このように、図１の第一の本実施形態によれば、フォワーディング部が中継確定情報に未登録の宛先のパケットを受信した場合、経路計算部（１）に報告後、経路計算部（１）がフォワーディング部（２）に中継確定情報エントリ（２８）を配布し、フォワーディング部（２）が中継確定情報（２６）に配布された中継確定情報エントリ（２８）を追加する前に、受信フレームを最適なインタフェースに中継した後で、正式に経路計算部（１）で中継確定情報（２６）を作成することができる。
【００４９】
次に、本発明の第二の実施形態について説明する。図１において、フォワーディング部（２）が経路計算部（１）へ不一致宛先情報（２７）を報告して、経路計算部（１）が中継確定情報エントリ追加要求（２８）をフォワーディング部（２）へ発行し、フォワーディング部（２）が中継確定情報（２６）に新たなエントリを追加するまでには、ある一定以上の時間が必要である。この間に、フォワーディング部（２）が同一宛先パケットを受信することも考えられる。この場合、フォワーディング部（２）は、中継確定情報（２３４）に、該パケットを中継する情報が無いことから、再度、中継基礎情報（６）を用いて中継先を計算し、該パケットを中継して、不一致宛先情報（２７）を経路計算部へ報告することとなる。これに伴い、経路計算部（１）では、再び中継確定情報エントリ追加要求（２８）の作成、および発行といった冗長な処理が発生する。第二の実施形態は、これらの冗長な処理を削除するものである。
【００５０】
図１３は、本発明によるパケット中継装置の第二の実施形態の機能ブロック図を示す。図１３において、図１との相違点は、フォワーディング部（２）で中継確定情報（２６）に仮のエントリ登録（２４４）を追加したことであり、それ以外は図１と同じである。また、経路計算部（１）とフォワーディング部（２）は、それぞれ独立したプロセッサでの構成、あるいは、同一プロセッサのそれぞれ独立したタスクモジュールでの構成のいずれでもよく、これも第一の実施形態の場合と同様である。
【００５１】
図１４は中継確定情報の仮のエントリによるパケット中継を示す図、図１５は中継確定情報の仮のエントリを中継確定情報エントリ追加要求で更新することを示す図である。また、図１６は、図４と同様に、フォワーディング部（２）がＩＰデータグラムを受信したときの動作のフローチャートである。図１６で図４との相違点は、中継確定情報に仮エントリを登録する処理を追加したことであり、それ以外は図４と同じである。
【００５２】
以下、図１３乃至図１６を参照し、本第二の実施形態のフォワーディング部（２）の動作を、図４と対比させて詳述する。
図４では、受信したＩＰデータグラム（２５）のＩＰヘッダ中のソースアドレスとグループアドレスが、中継確定情報（２６）のアドレス部と一致しない場合（ケース１０４）、その後の処理として、算出した出インタフェースが存在するか判定し（ステップ９７）、１つ以上のインタフェースが存在すれば（ケース１１４）、出インタフェースのすべてのインタフェースに対して受信ＩＰデータグラムを送信するとした（ステップ９８）。
【００５３】
これに対し、図１６では、算出した出インタフェースが存在するか判定し（ステップ９７）、１つ以上のインタフェースが存在すれば（ケース１１４）、図１３に示す様に、中継確定情報（２６）に仮のエントリの登録（２４４）を行い（ステップ２４７）、出インタフェースのすべてのインタフェースに対し受信ＩＰデータグラムを送信する（ステップ９８）。ここで、中継確定情報（２６）に登録したエントリは、ＩＰデータグラム（２５）のソースアドレス、宛先アドレス、入インタフェース、およびステップ９６で算出した出インタフェースを基に作成したエントリである。
【００５４】
この様に、第二の実施形態では、中継確定情報（２６）に仮のエントリを登録する（ステップ２４７）ことにより、図１４に示すように、経路計算部（１）が中継確定情報エントリ追加要求（２８）を発行する前に、フォワーディング部（２）が次以降の同宛先パケットを受信した場合、ＩＰデータグラム（４０）のヘッダ中のソースアドレスとグループアドレスがそれぞれ一致する仮のエントリ（２４６）が中継確定情報（２４５）中に存在する（ケース１０５）こととなり、該仮のエントリ（２４６）中の入インタフェースがそのＩＰデータグラムを受信したインタフェース（１１）と一致しているか確認する処理（ステップ１０１）を継続することとなる。つまり、受信したＩＰデータグラム（４０）のＩＰヘッダ中のソースアドレスとグループアドレスが、中継確定情報（２４５）のアドレス部と一致しない場合（ケース１０４）の処理は実行されない。このため、ＩＰデータグラムのソースアドレスと中継基礎情報（６）の発信元情報（７）のアドレス部を１エントリずつ比較する処理（ステップ９１）から、フォワーディング部（２）が不一致宛先情報（２７）を経路計算部（１）へ報告する処理（ステップ９９）までが、再発生しないこととなる。
【００５５】
また、図１５は、経路計算部（１）が中継確定情報エントリ追加要求（２８）を正式に発行した後、フォワーディング部（２）が、図１４に示した中継確定情報（２４５）中の仮のエントリ（２４６）を該中継確定情報エントリ追加要求（２８）に従って更新したことを示している。フォワーディング部（２）が一時的に登録したエントリを仮のエントリ（２４６）とした理由は、図１５に示す様に、経路計算部（１）が中継確定情報エントリ追加要求（２８）を発行後、フォワーディング部（２）と経路計算部（１）で、中継確定情報（２４５）を一致させるために、正式にフォワーディング部（２）が、中継確定情報（２４５）の当該エントリ（２４６）を更新するためである。
【００５６】
以上の様なフォワーディング部（２）の処理に伴い、経路計算部（１）では、次以降の同宛先パケットによる不一致宛先情報（２７）が報告されることがなく、冗長な中継確定情報エントリ追加要求（２８）を作成する処理が削除されることとなる。
【００５７】
以上、本発明の実施形態を説明したが、中継基礎情報（３）や中継確定情報（２６）は、経路計算部（１）とフォワーディング部（２）で独立にアクセス可能な共通メモリ装置に格納しておくようにしてもよい。この場合、経路計算部（１）があらかじめフォワーディング部（２）に中継基礎情報（６）を配布しておく必要がなく、フォワーディング部（２）は、メモリ装置に格納された中継基礎情報（３）を基に中継方路を決定できる。
【００５８】
また、図１や図１３の実施形態では、中継基礎情報（３，６）を宛先情報（５，８）と発信元情報（４，７）から構成されるとしたが、宛先情報のみや、発信元情報のみとすることは任意である。これにより、パケット中継装置では宛先情報のみや発信元情報のみを収集すればよいネットワークが構築できる。さらに、図１や図１３の実施形態のように、中継基礎情報を宛先情報と発信元情報から構成すれば、これらのネットワークを相互に中継できるパケット中継装置が実現できる。
【００５９】
【発明の効果】
以上詳述したように、本発明によれば、受信したパケット情報から経路計算を行う通信手段において、経路計算処理とパケット中継の処理の順番を変えることで、フォワーディング部にパケット中継待ち状態を発生させないパケット中継装置を実現できる。具体的には、経路計算部の計算待ちによるパケット中継の遅延を減少させ、中継確定情報に未登録の宛先のパケットを受信した場合、そのパケットが中継できるパケットかどうかをフォワーディング部で判定し、中継不可能なパケットを経路計算部に報告しないことによる冗長処理の削除、フォワーディング部にパケット中継待ち状態を発生させないことにより経路計算部で中継確定情報が作成できなかった時に発生する中継待ちキューからのパケット削除処理の削除、経路計算部に報告後の中継待ちパケットのキューが有限であることから発生する輻輳時のパケット廃棄を減少させた、パケット中継装置を実現できる。
【００６０】
そして、経路計算部とフォワーディング部の機能を異なるプロセッサにより実現することにより、物理的に同時に経路計算と中継動作を行うことが可能で、従来より遅延の少ないフォワーディング機能を備えたパケット中継装置を実現できる。
【００６１】
また、経路計算部とフォワーディング部を単一プロセッサの別タスクモジュールに分ければ、処理の優先度や処理順番により、異なるプロセッサにした場合はほどではないが、同様の効果が得られる。さらに、異なるプロセッサによるパケット中継装置より安価なパケット中継装置が実現できる。
【００６２】
また、さらに、経路計算部とフォワーディング部の機能を分けた場合、経路計算部が計算中に次到着の同一宛先パケットを受信することにより、冗長な経路の再計算処理が該パケット中継装置に起こるが、フォワーディング部でも一時的に中継確定情報を登録することにより、この冗長な経路の再計算処理を行わないパケット中継装置も実現できる。
【図面の簡単な説明】
【図１】本発明によるパケット中継装置の一実施形態の機能ブロック図である。
【図２】中継確定情報によるパケット中継を示す図である。
【図３】受信インタフェース不一致によるパケット廃棄を示す図である。
【図４】本発明によるパケット中継装置の一実施形態のＩＰデータグラムを受信契機としたフォワーディング部の動作のフローチャートである。
【図５】発明の一実施形態のネットワークシステムの全体図である。
【図６】マルチキャスト通信の概念図である。
【図７】ルーティングプロトコルＸの動作１を示す図である。
【図８】ルーティングプロトコルＸの動作２を示す図である。
【図９】ルーティングプロトコルＹの動作１を示す図である。
【図１０】ルーティングプロトコルＹの動作２を示す図である。
【図１１】ＩＰデータグラムのヘッダフォーマットを示す図である。
【図１２】マルチキャストグループアドレスフォーマットを示す図である。
【図１３】フォワーディング部で中継確定情報に仮のエントリを追加する本発明の他の実施形態の機能ブロック図である。
【図１４】中継確定情報の仮のエントリによるパケット中継を示す図である。
【図１５】中継確定情報の仮のエントリを中継確定情報エントリ追加要求で更新することを示す図である。
【図１６】フォワーディング部で中継確定情報に仮のエントリを追加する本発明の他の実施形態のＩＰデータグラムを受信契機とした、フォワーディング部の動作のフローチャートである。
【図１７】従来のパケット中継装置の機能ブロック図である。
【符号の説明】
１  経路計算部
２  フォワーディング部
３  経路計算部の中継基礎情報
４  経路計算部の中継基礎情報の発信元情報
５  経路計算部の中継基礎情報の宛先情報
６  フォワーディング部の中継基礎情報
７  フォワーディング部の中継基礎情報の発信元情報
８  フォワーディング部の中継基礎情報の宛先情報
９  プロトコルＸ
１０  プロトコルＹ
１１〜１６  インタフェースａ〜ｆ
１９  中継基礎情報の配布
２５  フォワーディング部の処理中パケット
２６  フォワーディング部の中継確定情報
２７  不一致宛先情報
２８  中継確定情報エントリ追加要求
２９  経路計算部のプロトコル情報
４５  更新した中継確定情報
２４４  中継確定情報の仮のエントリ登録
２４５  仮のエントリを登録された中継確定情報
２４６  仮のエントリ
【図１】
0003928833.tif 000002
【図２】
0003928833.tif 000003
【図３】
0003928833.tif 000004
【図４】
0003928833.tif 000005
【図５】
0003928833.tif 000006
【図６】
0003928833.tif 000007
【図７】
0003928833.tif 000008
【図８】
0003928833.tif 000009
【図９】
0003928833.tif 000010
【図１０】
0003928833.tif 000011
【図１１】
0003928833.tif 000012
【図１２】
0003928833.tif 000013
【図１３】
0003928833.tif 000014
【図１４】
0003928833.tif 000015
【図１５】
0003928833.tif 000016
【図１６】
0003928833.tif 000017
【図１７】
0003928833.tif 000018