(57)【特許請求の範囲】
【請求項１】
マルチキャストネットワークを介して複数の他のパケット中継装置と接続され、ユニキャスト経路表に基づいて前記マルチキャストネットワークのマルチキャスト経路を構築するパケット中継装置であって、
回線を接続し、マルチキャストパケットの送受信を行う複数の回線部と、
前記マルチキャストパケットの送信元アドレスと、グループアドレスと、該マルチキャストパケットの中継における上流のパケット中継装置のアドレスと、該上流のパケット中継装置が存在する前記回線を示す情報とをマルチキャスト経路エントリとして記憶するマルチキャスト経路情報記憶部と、
前記マルチキャスト経路情報記憶部を管理する経路計算部とを有し、
前記経路計算部は、前記複数の他のパケット中継装置がEqual-cost Multipathを構成する場合において、前記複数の他のパケット中継装置が存在する複数の前記回線の中で前記マルチキャスト経路エントリとして記憶されている数が最も少ない回線に存在する該他のパケット中継装置を、前記マルチキャストパケットの中継における上流のパケット中継装置として選択し、前記マルチキャスト経路情報記憶部に記憶させることを特徴とするパケット中継装置。
【請求項２】
請求項１記載のパケット中継装置であって、
前記経路計算部は、前記記憶されている数が最も少ない回線に存在する前記他のパケット中継装置が複数存在する場合において、該複数存在する他のパケット中継装置の中で、前記上流のパケット中継装置として前記マルチキャスト経路情報記憶部に記憶されている数が最も少ない該他のパケット中継装置を前記マルチキャストパケットの中継における上流のパケット中継装置として選択することを特徴とするパケット中継装置。
【請求項３】
請求項１乃至２記載のパケット中継装置であって、
前記経路計算部は、少なくとも前記送信元アドレスとグループアドレスとにより特定されるストリーム毎に定められた重み付けにしたがって、前記マルチキャスト経路エントリとして記憶されている数の計数を変動させることを特徴とするパケット中継装置。
【請求項４】
マルチキャストネットワークを介して複数の他のパケット中継装置と接続され、ユニキャスト経路表に基づいて前記マルチキャストネットワークのマルチキャスト経路を構築するパケット中継装置であって、
回線を接続し、マルチキャストパケットの送受信を行い、トラフィック量の測定を行う複数の回線部と、
前記マルチキャストパケットの送信元アドレスと、グループアドレスと、該マルチキャストパケットの中継における上流のパケット中継装置のアドレスと、該上流のパケット中継装置が存在する前記回線を示す情報とをマルチキャスト経路エントリとして記憶するマルチキャスト経路情報記憶部と、
前記マルチキャスト経路情報記憶部を管理する経路計算部とを有し、
前記経路計算部は、前記複数の他のパケット中継装置がEqual-cost Multipathを構成する場合において、前記複数の他のパケット中継装置が存在する複数の前記回線のうち、第１の回線と第２の回線について前記測定したトラフィック量を比較し、該トラフィック量が少ない前記第１または第２の回線に存在する前記他のパケット中継装置を、前記マルチキャストパケットの中継における上流のパケット中継装置として選択し、前記マルチキャスト経路情報記憶部に記憶させることを特徴とするパケット中継装置。
【請求項５】
請求項４記載のパケット中継装置であって、
前記経路計算部は、前記測定したトラフィック量が少ない回線に存在する前記他のパケット中継装置が複数存在する場合において、該複数存在する他のパケット中継装置のうち、第１の他のパケット中継装置と第２の他のパケット中継装置について前記上流のパケット中継装置として前記マルチキャスト経路情報記憶部に記憶されている数を比較し、前記記憶されている数が少ない前記第１または第２の他のパケット中継装置を前記マルチキャストパケットの中継における上流パケット中継装置として選択することを特徴とするパケット中継装置。
【請求項６】
請求項５記載のパケット中継装置であって、
前記経路計算部は、少なくとも前記送信元アドレスとグループアドレスとにより特定されるストリーム毎に定められた重み付けにしたがって、前記記憶されている数の計数を変動させることを特徴とするパケット中継装置。
【請求項７】
マルチキャストネットワークを介して複数の他のパケット中継装置および第１の端末および第２の端末と接続され、前記第１の端末から送信されるマルチキャストパケットを前記第２の端末へ中継するためのマルチキャスト経路を、前記第２の端末から送信されるマルチキャスト受信要求の中継経路に基づいて構築するパケット中継装置であって、
マルチキャストパケットの送信元アドレスと、グループアドレスと、該マルチキャストパケットの中継における上流のパケット中継装置のアドレスとをマルチキャスト経路エントリとして記憶するマルチキャスト経路情報記憶部と、
前記マルチキャスト経路情報記憶部を管理する経路計算部とを有し、
前記経路計算部は、前記複数の他のパケット中継装置がEqual-cost Multipathを構成する場合において、前記複数の他のパケット中継装置のうち、前記上流のパケット中継装置として前記マルチキャスト経路情報記憶部に記憶されている数が最も少ない該他のパケット中継装置を前記マルチキャストパケットの中継における上流のパケット中継装置として選択し、前記マルチキャスト経路情報記憶部に記憶させることを特徴とするパケット中継装置。
【請求項８】
請求項７記載のパケット中継装置であって、
前記経路計算部は、少なくとも前記送信元アドレスとグループアドレスとにより特定されるストリーム毎に定められた重み付けにしたがって、前記記憶されている数の計数を変動させることを特徴とするパケット中継装置。
【請求項９】
回線を接続する複数の回線部を有し、マルチキャストネットワークを介して複数の他のパケット中継装置と接続され、記憶部を有するパケット中継装置において、ユニキャスト経路表に基づいて前記マルチキャストネットワークのマルチキャスト経路を構築する方法であって、
マルチキャストパケットの送信元アドレスと、グループアドレスと、該マルチキャストパケットの中継における上流のパケット中継装置のアドレスと、該上流のパケット中継装置が存在する前記回線を示す情報とをマルチキャスト経路エントリとして前記記憶部に記憶するステップと、
前記複数の他のパケット中継装置がEqual-cost Multipathを構成する場合において、
前記複数の他のパケット中継装置が存在する複数の前記回線のうち、第１の回線と第２の回線について前記マルチキャスト経路エントリとして記憶されている数を比較するステップと、
前記比較した結果、前記記憶されている数が少ない前記第１または第２の回線に存在する前記他のパケット中継装置をマルチキャストパケットの中継における上流のパケット中継装置として選択するステップとを有することを特徴とする方法。
【請求項１０】
請求項９記載の方法であって、
前記記憶されている数が少ない前記第１または第２の回線に存在する前記他のパケット中継装置が複数存在する場合において、
前記選択するステップは、前記複数存在する他のパケット中継装置のうち、第１の他のパケット中継装置と第２の他のパケット中継装置について前記上流のパケット中継装置として前記記憶部に記憶されている数を比較し、前記記憶されている数が少ない前記第１または第２の他のパケット中継装置を前記マルチキャストパケットの中継における上流のパケット中継装置として選択することを特徴とする方法。
【請求項１１】
マルチキャストネットワークを介して複数の他のパケット中継装置と接続され、記憶部を有するパケット中継装置において、ユニキャスト経路表に基づいて前記マルチキャストネットワークのマルチキャスト経路を構築する方法であって、
マルチキャストパケットの送信元アドレスと、グループアドレスと、該マルチキャストパケットの中継における上流のパケット中継装置のアドレスとをマルチキャスト経路エントリとして前記記憶部に記憶するステップと、
前記複数の他のパケット中継装置がEqual-cost Multipathを構成する場合において、
前記複数の他のパケット中継装置のうち、前記上流のパケット中継装置として前記記憶部に記憶されている数が最も少ない該他のパケット中継装置をマルチキャストパケットの中継における上流のパケット中継装置として選択するステップとを有することを特徴とする方法。
【請求項１２】
請求項９乃至１１記載の方法であって、
前記選択するステップでは、少なくとも前記送信元アドレスとグループアドレスとにより特定されるストリーム毎に定められた重み付けにしたがって、前記記憶されている数の計数を変動させることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネットにおけるマルチキャスト中継技術に関し、特にEqual-cost Multipathを用いたマルチキャストネットワークにおけるマルチキャスト経路の構築技術および負荷分散技術に関する。
【背景技術】
【０００２】
マルチキャストは、インターネットにおいてルータが複数の回線へパケットを複製出力することにより、送信された1つのパケットを同時に複数の受信者へ送信する技術である。1つの送信先にパケットを複数回送るのに比べて少ない量のパケットで複数の送信先にパケットを送ることが可能であるため、特にストリーミングやビデオ会議に代表される大容量トラフィックを必要とするリアルタイムマルチメディア通信に適している。
【０００３】
マルチキャストパケットを本来そのパケットを受信すべきユーザへのみ送信するためには、ルータがマルチキャストパケットを複数の回線へ出力する際、適切な回線を選択する必要がある。この回線選択の判断基準を作成するのがマルチキャスト経路制御プロトコルであり、PIM-SM(Protocol Independent Multicast Sparse-Mode: 非特許文献1)が通常用いられている。
【０００４】
PIM-SMの経路制御計算ではRPF(Reverse Path Forwarding)計算が中心的な役割を果たす。RPFでは、あるマルチキャスト送信サーバからのマルチキャストグループへの参加要求を下流の受信端末から受信したルータは、マルチキャスト送信サーバへ到達するための隣接PIM-SMルータ(RPF Neighbor)をユニキャスト経路表から算出し（以下、「RPF Neighbor計算」という）、そのRPF Neighborへ受信したグループ参加要求をPIM Joinメッセージで送る。また、当該ルータはマルチキャスト参加要求を送った方向とは逆方向の経路をマルチキャストパケットの中継経路として登録する。この繰り返しにより全てのマルチキャスト参加要求が送信サーバと受信端末の間の全ルータに通知され、その逆方向の経路がマルチキャストパケットの中継経路として登録されるため、送信サーバからのマルチキャストパケットが参加要求のある方向へ流れるようになる。
【０００５】
一方ユニキャストでは、ルータや回線の負荷分散のために、ECMP(Equal Cost Multipath)という技術が用いられる。これは同一の宛先に対して複数の隣接ルータを指定し、ストリームの内容に応じて1つの隣接ルータを中継先として選択する技術である。ストリーム毎にランダムに中継装置を選択することにより、ストリーム単位でルータや回線の負荷を分散することができる。ストリーム毎のランダムな選択には通常、ストリーム情報(送信元や送信先アドレスやポート番号)のハッシュ値が用いられる。
【０００６】
ECMPを用いた網でマルチキャストを動かす場合、RPF Neighbor計算の結果複数のRPF Neighborが見つかることがある。この場合、PIM-SM仕様では最大のIPアドレスを有する隣接ルータをRPF Neighborとすることになっている。このため、ECMPを用いたネットワークでも常に特定ルータにマルチキャストトラフィックが偏ってしまい、負荷分散が行われないことが課題とされている。
【０００７】
この課題に対してCisco社(非特許文献2)は、マルチキャスト送信サーバのIPアドレスとマルチキャストグループアドレスと隣接ルータのアドレスのハッシュを用いて、RPF Neighborを選択する技術を有する。この技術を用いると、ECMPを用いたネットワークでもこのハッシュ値によりマルチキャストトラフィックをストリーム毎にある程度分散させることが可能となる。
【０００８】
【非特許文献１】IETF, ”Protocol Independent Multicast Sparse-Mode (PIM-SM): Protocol Specification”, RFC2382.
【非特許文献２】Cisco Systems “Load Splitting IP Multicast Traffic over ECMP”, http://www.cisco.com/univercd/cc/td/doc/product/software/ios124/124tcg/timc_c/mcbspltt.htm#wp1053023
【発明の開示】
【発明が解決しようとする課題】
【０００９】
非特許文献２の方式では負荷分散の判定をトラフィックの内容のハッシュ値で実施するため、ハッシュ値が偏ってしまうようなトラフィックが流れる場合は、依然として特定方向にトラフィックが偏ってしまう。そのためECMPを構成するルータや回線間の負荷分散を保証することができない。
【００１０】
そこで、本発明はECMPを構成するルータや回線間でマルチキャストの負荷分散を実現するようにマルチキャスト経路を構築する方法および装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために本発明では、ECMPによりルータ等のパケット中継装置が、グループ参加要求を送信するRPF Neighborが複数存在する場合に、各RPF Neighbor候補に関するトラフィック流量を推定し、最もトラフィック流量が少ないルータをRPF Neighborとして選択することでマルチキャスト経路を構築する。
【００１２】
トラフィック流量を推定する方法としては、以下の3つの方法のいずれかを用いる。
【００１３】
第１の方法は、これまでに計算した全てのマルチキャスト経路に関するRPF Neighbor計算結果を計数し、最もRPF Neighborとして選択されている数が少ない装置を、トラフィック流量最小の装置とする方法である。
【００１４】
第２の方法は、これまでに計算した全てのマルチキャスト経路に関してRPF Neighbor方向の回線を計数し、最もRPF Neighbor方向の回線として選択されている数が少ない回線に存在する装置を、トラフィック流量最小の装置とする方法である。この方法で見つかった回線上に複数の装置が見つかった場合には、前述の第１の方法もしくはIPアドレスの大小によりトラフィック量最小の装置を決定する。
【００１５】
マルチキャストをストリーミングに用いた場合1ストリームあたりの帯域は通常一定レートであるため、経路エントリ数からストリームの帯域を推定することが可能となる。
【００１６】
第３の方法は、回線毎にトラフィック流量を定期的に測定し、RPF Neighbor方向の回線に関するトラフィック流量が最小の回線上に存在する装置を、トラフィック流量最小の装置とする方法である。この方法で見つかった回線上に複数の装置が見つかった場合には、第２の方法と同様にしてトラフィック量最小の装置を決定する。
【発明の効果】
【００１７】
本発明では、トラフィック流量推定に基づきRPF Neighborを選択することにより、トラフィックの内容に関係なくECMPを構成する隣接ルータや回線間での負荷分散を保証することができる。
【発明を実施するための最良の形態】
【００１８】
図1に本実施形態におけるPIM-SMマルチキャストネットワークの一例を示す。PIM-SMマルチキャストネットワークは、PIM-SMルータ100〜103，106と送信端末104と受信端末105から構成される。受信端末105が送信端末104からのマルチキャストグループへの参加要求（マルチキャスト受信要求）を送信すると、受信端末105を収容するルータ103が、ユニキャスト経路表に基づいて送信端末104方向のRPF Neighborを計算し、そのルータへPIM Joinメッセージを送信する。図１の場合はルータ103から送信端末104へは、ルータ101、102、106のどれを回っても等距離なので、ECMP構成となっている。このときルータ103はいずれか1つ（例えばルータ101）をRPF Neighborとして選択し、PIM Joinメッセージを送信する。この際、ルータ103はPIM Joinメッセージを送信した方向とは逆方向の経路をマルチキャストパケットの中継経路として登録する（例えば「ルータ101 → ルータ103 → 受信端末105」の経路）。そしてRPF Neighborとして選択されたルータ（例えばルータ101）が、ルータ103と同様に送信端末104方向のRPF Neighborを計算し、送信端末104を収容するルータ100へPIM Joinメッセージを送信し、その逆方向の経路をマルチキャストパケットの中継経路として登録することにより（例えば「ルータ100 → ルータ101 → ルータ103」の経路）、送信端末104から受信端末105までのマルチキャスト経路を構築する。なお本実施形態ではマルチキャスト経路制御プロトコルをPIM-SMに限定して記述しているが、ユニキャスト経路表に基づきマルチキャスト経路を構築する他のプロトコルでも、本発明は実現可能である。
【００１９】
図2にルータ103の内部構造を示す。ルータ103は回線を接続する回線部201、202、203のいずれかで受信したパケットを他の回線部を介して接続する回線へ中継する装置である。マルチキャストパケット中継処理部210は、ある回線を介して回線部から入力されたマルチキャストパケットをその内部にあるマルチキャスト経路表に従って他の回線部を介して接続される回線に出力する部分である。ユニキャストパケット中継処理部211も、同様にしてユニキャストパケットを中継する。これらの中継処理部の経路表は、メモリ213上にありCPU212上で動作する経路制御プログラム215により管理更新される。なお、マルチキャストパケット中継処理部210やユニキャストパケット中継処理部211は専用のハードウェア（ASIC）などにより実現される。
【００２０】
経路制御プログラム215は、マルチキャストパケット中継処理部210やユニキャストパケット中継処理部211との通信を行うデバイスドライバ260と、デバイスドライバから入力されたパケットを実際に処理するPIM-SM経路計算部220と、これまでに計算したユニキャスト経路表250、マルチキャスト経路表240、隣接ルータリスト230からなる。
【００２１】
図3に隣接ルータリスト230、マルチキャスト経路表240、ユニキャスト経路表250の詳細を示す。
【００２２】
隣接ルータリスト230は、ルータ103がPIM制御パケットを通じて認識した隣接マルチキャストルータの一覧である。図１においては、ルータ101,102,106がルータ103の隣接マルチキャストルータに該当する。隣接ルータリスト230は、隣接マルチキャストルータから受信するPIM制御パケット内に示される隣接マルチキャストルータのIPアドレスを示すNeighbor 231、隣接マルチキャストルータの存在する回線を示すInterface 232、当該エントリの有効期限を示すExpires at 233から構成され、PIM-SM制御パケット受信の度にPIM-SM経路計算部220によって更新される。ルータ103は、隣接ルータリスト230により自身に隣接するマルチキャストルータの有無やその接続先の回線を把握することができる。
【００２３】
マルチキャスト経路表240は、マルチキャストデータ中継先を決定するために用いるデータである。マルチキャスト経路表240は、中継すべきマルチキャストパケットの送信元サーバアドレスを示すSource 241、マルチキャストグループアドレスを示すGroup 242、当該マルチキャストパケットの受信回線を示すIncoming interface 243、当該マルチキャストパケットの出力回線を示すOutgoing interface list 244、当該マルチキャストパケット中継における上流のマルチキャストルータ（上流の隣接マルチキャストルータ）でありIncoming interface 243が示す回線に存在するルータのアドレスを示すUpstream Neighbor 245から構成される。マルチキャスト経路表240を作成するために、PIM-SM経路計算部220は、PIM Joinメッセージを受信すると、受信したPIM Joinメッセージ内に示されている送信サーバアドレス・グループアドレスをそれぞれ経路表のSource 241、Group 242に保存し、Source 241のアドレスに対するRPF Neighbor計算をユニキャスト経路表250に基づいて行うことでRPF Neighborを選択し、その結果をUpstream Neighbor 245に保存する。またRPF Neighborが存在する回線をIncoming Interface 243に保存し、PIM-SM制御パケット（PIM Joinメッセージ）を受信した回線をOutgoing Interface list 244に追加する。以上の計算結果をマルチキャストパケット中継処理部210へ反映することにより、実際のマルチキャストパケット中継にもPIM Joinメッセージの内容が反映される。すなわち、マルチキャストパケット中継処理部210は、マルチキャストパケットを受信すると送信サーバアドレス・グループアドレスを元に、PIM-SM経路計算部220によって反映され自身も保持するマルチキャスト経路表240を参照し、該当するOutgoing interface list 244に示される回線へ受信したマルチキャストパケットをコピーして中継する。
【００２４】
ユニキャスト経路表250は、前述のRPF Neighbor計算の際に用いられる情報である。ユニキャスト経路表250は、中継すべきユニキャストパケットの宛先アドレスを示すDestination 251、該ユニキャストパケットを中継すべきNext-hopのルータアドレスを示すNext-hop 252、該ユニキャストパケットの出力回線を示すInterface 253から構成される。PIM-SM経路計算部220は、前述のマルチキャスト経路表240作成におけるRPF Neighbor計算の際に、対象となるIPアドレス（PIM Joinメッセージ内に示されているマルチキャスト送信サーバアドレスであるSource 241のアドレス）について、ユニキャスト経路表250からDestination 251のフィールドが最長マッチするエントリを検索し、そのエントリのNext-hop 252のアドレスで隣接ルータリスト230に含まれているものをRPF Neighborとして選択する。
【００２５】
図4を用いて、RPF Neighbor計算アルゴリズムの全体像を説明する。PIM Joinメッセージにより送信元サーバアドレスS、グループアドレスGへのグループ参加要求がLine1からあったとき、PIM-SM経路計算部220はユニキャスト経路表250においてDestination 251のフィールドがSに最長マッチするエントリを検索し、該当するエントリのNext-hop 252欄のアドレスを上流ルータ候補とする(ステップ305)。この上流ルータ候補のうちPIM-SM隣接ルータリスト230のNeighbor 231に含まれているものが、RPF Neighborの候補となる(ステップ310)。この段階でRPF Neighbor候補が残っているかを判断し（ステップ315）、RPF Neighbor候補が残っており（ステップ315のY）、1つに絞り込まれない場合（ステップ325のN）が今回の発明の対象となるECMPのケースであり、ここからトラフィック流量を推測して1つのRPF neighborを確定すること(ステップ330)が本発明の技術である。この場合、ステップ330にて確定したルータがRPF neighborとなり、ステップ325でRPF Neighbor候補が１つに絞り込まれている場合は（ステップ325のY）そのルータがRPF neighborとなる。以上によりRPF Neighbor計算が行われる。上記RPF Neighbor計算が行われ、RPF Neighborが確定すると、PIM Joinメッセージの送信元サーバアドレスS、グループアドレスGでマルチキャスト経路表240を検索し、既に（S,G）のエントリが存在すれば（ステップ335のY）、その（S,G）エントリのOutgoing interface list 244にPIM Joinメッセージを受信したLine1を追加し（ステップ345）、マルチキャスト経路表240に（S,G）エントリが存在しなければ（ステップ335のN）、（S,G）のエントリを追加し、更に、Incoming interface 243に確定したRPF Neighborが存在する回線を、Outgoing interface list 244にPIM Joinメッセージを受信したLine1を、Upstream Neighbor245に確定したRPF Neighborのアドレスを、それぞれ設定する（ステップ340）。なお、ステップ315において、RPF Neighbor候補が残っていない場合は、マルチキャスト経路表240に経路追加せず終了する（ステップ320）。ステップ330のトラフィック流量を推測して1つのRPF neighborを選択する具体的な方法については、図５〜図８を用いて説明する。
【００２６】
図5を用いて、複数のRPF Neighbor候補から1つのRPF Neighborを確定する第１ののアルゴリズムを説明する。まずマルチキャスト経路表240に、参加要求があったマルチキャストグループに該当する経路情報が既に存在するか否か（すなわち、受信したPIM Joinメッセージ内に示されている送信サーバアドレスSとグループアドレスGと合致するエントリがマルチキャスト経路表240のSource 241とGroup 242に既に存在するか否か）を調べる(ステップ410)。ここでエントリが存在する場合（ステップ410のY）は過去にRPF Neighbor算出が済んでいるため、不要な経路変動を防ぐため、極力その算出結果を流用する。すなわち、該当するエントリのUpstream Neighbor 245がRPF Neighbor候補に含まれていれば（ステップ415のY）そのUpstream NeighborをそのままRPF Neighborと確定し(ステップ420)、含まれていなければ（ステップ415のN）、以下の要領でRPF Neighborを再選出する。
【００２７】
エントリが存在しない（ステップ410のN）、もしくは過去に選択したUpstream Neighborを流用できない（ステップ415のN）場合は、各RPF Neighbor候補に関してマルチキャスト経路表240からUpstream Neighbor 245欄が合致するエントリ数を算出し(ステップ500)、エントリ数が最小のRPF Neighbor候補が１つである場合は（ステップ430のN）、そのRPF Neighbor候補をRPF Neighborとして選択する(ステップ435)。エントリ数最小のRPF Neighbor候補が複数存在する場合は（ステップ430のY）、これらのルータのうちIPアドレスが最大のものをRPF Neighborとして選択する(ステップ440)。
【００２８】
以上のアルゴリズムを、図8のトポロジーでRouter700がマルチキャスト経路表710を有する場合を用いて説明する。送信元サーバServer7、グループアドレスGroup7宛のマルチキャスト経路エントリを追加するときに（ステップ410のN）、Server7へのRPF Neighbor候補がRouter1 701、Router2 702、Router3 703の3種類だったとする。ステップ500において、Router1、Router2、Router3を上流ルータとする経路エントリ数（マルチキャスト経路表710のUpstream Neighbor 715がRouter1、Router2、Router3となっている経路エントリ数）はそれぞれ2個、1個、3個なので、Server7へのRPF Neighborは、このエントリ数が最小であるRouter2と確定される。
【００２９】
上記アルゴリズムにより、複数のRPF Neighbor候補の中から最もRPF Neighborとして採用されている数の少ないルータ（すなわち、トラフィック流量が最も少ないルータであると推定されるルータ）をRPF Neighborとして確定することができ、これにより、ルータ間の負荷分散（図８の例では、Router1、Router2、Router3間の負荷分散）を実現することができる。
【００３０】
次に、図6を用いて、複数のRPF Neighbor候補から1つのRPF Neighborを確定する第２のアルゴリズムを説明する。まず図５のアルゴリズムと同じ要領で、エントリが存在しない（ステップ410のN）、もしくは過去に選択したUpstream Neighborを流用できない（ステップ415のN）場合に該当するかどうかを判断する。該当の場合には、各RPF Neighbor候補が存在する回線を、隣接ルータ表230内の対応するInterface欄232から求める（ステップ510）。そしてその各回線について、マルチキャスト経路表240からIncoming Interface 243欄が合致するエントリ数を算出し(ステップ511)、エントリ数が最小のInterfaceに属するRPF Neighbor候補が１つである場合は（ステップ430のN）、そのRPF Neighbor候補をRPF Neighborとして選択する(ステップ435)。
【００３１】
エントリ数が最小のInterfaceに属するRPF Neighborが複数存在する場合（ステップ430のY）は、以下のいずれかの方法を用いて1つのRPF Neighborを選択する。第１の方法は、IPアドレスが最大のものをRPF Neighborとする方法である(ステップ440)。第２の方法は、該当するRPF Neighbor候補に関して第１のアルゴリズムと同じ方法で1つのRPF Neighborを選定する方法である(図7ステップ620、630、640、650)。
【００３２】
以上のアルゴリズムを、図8のトポロジーでRouter700がマルチキャスト経路表710を有する場合を用いて説明する。送信元サーバServer7、グループアドレスGroup7宛のマルチキャスト経路エントリを追加するときに（ステップ410のN）、Server7へのRPF Neighbor候補がRouter1 701、Router2 702、Router3 703の3種類あったとする。隣接ルータ表230より、Router1、Router2、Router3の所属する回線はそれぞれLine1、Line2、Line2であり（ステップ510）、ステップ511において、Line1、Line2を上流ルータとする経路エントリ数（マルチキャスト経路表710のIncoming interface 713がLine1、Line2となっている経路エントリ数）はそれぞれ2個、4個なので、Server7へのRPF Neighborは、このエントリ数が最小であるLine1上に存在するRPF NeighborであるRouter1と確定される。
【００３３】
図６のアルゴリズムにより、複数のRPF Neighbor候補の中から、最もIncoming interfaceとして採用されている数の少ない回線（すなわち、トラフィック流量が最も少ない回線であると推定される回線）上に存在するルータをRPF Neighborとして確定することができ、これにより、回線間の負荷分散（図８の例では、Line1、Line2間の負荷分散）を実現することができる。ここで、回線、Line1、Line2とは、物理回線を指してもよいし、複数の物理回線を1つにまとめた論理的な回線（例えばリンクアグリゲーションやVLANなど）を指してもよい。
【００３４】
更に図７のアルゴリズムを用いれば、図５のアルゴリズムと同様にルータ間の負荷分散も実現することができる。
【００３５】
また、例えば図８の場合において図５のアルゴリズムのみを適用すると最もルータ負荷が低いと推定されるRouter2がRPF Neighborとして確定されるが、この場合Incoming interface 713としては負荷の高いと推定されるLine2が選択されてしまい、このようなケースでは図５のアルゴリズムだけでは負荷分散が不十分な場合が発生する。その点で、図６・図７のアルゴリズムはルータの負荷分散と回線の負荷分散がバランス良く行われるため、図５のアルゴリズムよりもネットワークトポロジーに柔軟に対応した負荷分散が可能である。
【００３６】
本実施形態ではエントリの個数を単純計数することによりトラフィック流量を推測しているが、例えば予め分かっている各ストリームのトラフィック流量を重み付けして計数することにより、より正確にトラフィック流量を推定することも可能である。
【００３７】
例えば、図８のマルチキャスト経路表710において、エントリ722に示すストリームによるトラフィック流量が他のエントリに示すストリームのトラフィック流量の２倍である場合には、エントリ722の重み付けを２倍にして計数する。この場合、図５のステップ500において、エントリ722のUpstream Neighbor 715のRouter1は２エントリ分として計数され、また、図６のステップ511においては、エントリ722のIncoming interface 713のLine1は２エントリ分として計数される。これにより、より正確にトラフィック流量を推定することが可能になる。なお、重み付けは２倍である必要はなく、任意の数に変動させることが可能である。
【００３８】
更に図2のルータの回線部201、202、203にトラフィック流入量を測定する機能を備えた場合、図6に示すフローチャートのステップ511にて、ステップ510で求めた各回線のトラフィック流入量をルータの回線部から取得し、その流入量が少ない順に順序付けし、ステップ430以下を実施し最も流入量が少ない回線上に存在する上位ルータを選択することにより、実際のトラフィック流量の測定結果に基づきRPF Neighborを選択することが出来る。
【００３９】
図５〜図８を用いて、マルチキャスト経路表240においてエントリ数が最小のIncoming interface 243やUpstream Neighbor 245に対応する上位ルータをRPF Neighborとすることを説明してきたが、負荷分散を実現するためには必ずしもエントリ数が最小のものを選択する必要はない。すなわち、エントリ数が最大のもの以外を選択すれば一定の負荷分散効果を得ることも可能である。また、例えば最もエントリ数の小さい回線は特定通信専用とするために経路として選択せず、２番目にエントリ数の小さい回線を選択したいケースも考えられる。エントリ数が最小の回線を選択する場合も、エントリ数が最大以外の回線を選択する場合も、他のいずれかの回線と比較してエントリ数小さい回線を選択する点では共通する。したがって、ECMPを構成する装置が存在する回線が複数存在する場合にそのうちの第１の回線と第２の回線のうち、Incoming interface 243としてエントリ数が少ない方の回線を選択するという方法でも負荷分散を実現してもよい。そして選択された回線上の上位ルータ装置がRPF Neighborとして確定される。上記の説明はUpstream Neighbor 245のエントリ数や、各回線のトラフィック流入量に基づいてRPF Neighborを選択する場合も同様である。
【図面の簡単な説明】
【００４０】
【図１】本実施形態におけるPIM-SMマルチキャストネットワークの例を示す。
【図２】Routerの内部構造を示す。
【図３】隣接ルータリスト・ユニキャスト経路表・マルチキャスト経路表を示す。
【図４】RPF Neighbor算出アルゴリズムを示す。
【図５】RPF Neighbor数に基づくRPF Neighbor選出アルゴリズムを示す。
【図６】RPF回線数に基づくRPF Neighbor選出アルゴリズム(1)を示す。
【図７】RPF回線数に基づくRPF Neighbor選出アルゴリズム(2)を示す。
【図８】ECMPとなるマルチキャストネットワークの例を示す。
【符号の説明】
【００４１】
100〜103,106：Router、104：送信端末、105：受信端末、201〜203：回線、210：マルチキャストパケット中継処理部、211：ユニキャストパケット中継処理部、215：経路制御プログラム、220：PIM-SM経路計算部、230：隣接ルータリスト、240：マルチキャスト経路表、250：ユニキャスト経路表、260：デバイスドライバ
【図１】
0004797010.tif 000002
【図２】
0004797010.tif 000003
【図３】
0004797010.tif 000004
【図４】
0004797010.tif 000005
【図５】
0004797010.tif 000006
【図６】
0004797010.tif 000007
【図７】
0004797010.tif 000008
【図８】
0004797010.tif 000009