通信システム、ルータ位置算出装置、およびルータ位置算出プログラム
【課題】disjointな（経路上に共通ルータを持たない独立な）マルチキャストツリーを動的に構築することができる通信システム、ルータ位置算出装置、およびルータ位置算出プログラムを提供する。
【解決手段】ルータ論理位置計算部２１は、配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、新たに追加される追加ルータと接続される、配信サーバ側に設けられた上流ルータと追加ルータの論理的な位置関係を示す追加ルータ接続情報と、複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値とに基づいて追加ルータの論理的な位置を算出する。
【解決手段】ルータ論理位置計算部２１は、配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、新たに追加される追加ルータと接続される、配信サーバ側に設けられた上流ルータと追加ルータの論理的な位置関係を示す追加ルータ接続情報と、複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値とに基づいて追加ルータの論理的な位置を算出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配信サーバによって送信される放送用のメインマルチキャストパケットと、バックアップサーバによって送信されるバックアップマルチキャストパケットとを転送する複数のルータを備えた通信システムに関する。また、本発明は、本通信システムを構成するルータの論理的な位置関係に係る処理を行うルータ位置算出装置およびルータ位置算出プログラムにも関する。
【背景技術】
【０００２】
動画配信等のサービスを実現するために、OSI（Open Systems Interconnection） Layer3層のIP（Internet Protocol）においてマルチキャスト（非特許文献１参照）が定義され、これに対応した各種プロトコル（非特許文献２および３参照）が実装・運用されている。しかし、IP層における（IP経路制御プロトコルに基づく）ネットワーク障害の検出・復旧に数秒〜数10秒の通信断を伴うことが問題となる。そこで、冗長構成を持つIPネットワークを対象として、この通信断時間を補償し、サービスを無瞬断化するために、本発明者は特願２００４−０６０５２８、特願２００４−３４９６６５、および特願２００５−０６２２９３に記載の技術を提案している。
【０００３】
マルチキャスト配信経路の決定は、マルチキャスト受信者から発信者（またはランデブーポイント（RP）と呼ばれる特別なノード）に向かうユニキャスト経路情報に基づいて、PIM-SMマルチキャスト経路制御プロトコル（非特許文献２参照）が行う。ユニキャスト経路情報は、OSPF（Open Shortest Path First）（非特許文献３参照）等のユニキャスト経路制御プロトコルによって生成される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Beau Williamson著，「ＩＰマルチキャストネットワーク開発ガイドＶｏ１．１」，ソフトバンクパブリッシング株式会社，２００１年７月３日
【非特許文献２】D.Estrin，他９名，RFC2362-Protocol Independent Multicast-Sparse Mode（PIM-SM）:Protocol Specification，［online］，１９９８年，The Internet Society，［２０１０年５月２６日検索］，インターネット＜URL: http://www.faqs.org/rfcs/rfc2362.html＞
【非特許文献３】J.Moy，RFC2328-OSPF Version 2，［online］，１９９８年，The Internet Society，［２０１０年５月２６日検索］，インターネット＜URL: http://www.faqs.org/rfcs/rfc2328.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００５】
図１０は、本発明者が提案した技術による通信ネットワークの構成を示している。放送配信サーバ１０１は、配信対象のストリームデータが格納されたマルチキャストパケットを送信する。送信されたマルチキャストパケットは、通常配信用（メイン）マルチキャストＧｍとして、Ｌ２スイッチ１０２および各通信装置（ルータ１０４ｂ，１０５ｂ，１０６ｂ，１０７およびＬ２スイッチ１０９）を経由してクライアント端末１１０へ転送される。また、Ｌ２スイッチ１０２によってマルチキャストパケットが複製され、バックアップサーバ１０３へ送信される。バックアップサーバ１０３は、受信したマルチキャストパケットを複製し、２つの予備配信用（バックアップ）マルチキャストＧｂ１およびＧｂ２として送信する。
【０００６】
バックアップマルチキャストＧｂ２には、バックアップサーバ１０３によって一定の遅延が付加される。バックアップマルチキャストＧｂ１およびＧｂ２は、定常時にはルータ１０４ａで破棄される。クライアント端末１１０に最も近いエッジのルータ１０７の近傍には通信制御装置１０８が設けられている。通信制御装置１０８は、メインマルチキャストＧｍの配信断を検出した場合、バックアップマルチキャストＧｂ１およびＧｂ２の受信に参加する。バックアップマルチキャストＧｂ１およびＧｂ２はルータ１０４ａから、ルータ１０５ａ，１０６ａ，１０７を経由して、通信制御装置１０８によって受信される。
【０００７】
通信制御装置１０８は、受信したバックアップマルチキャストＧｂ１およびＧｂ２をメインマルチキャストに変換して代理出力する（図１０のマルチキャストＧｍ’）。この際、障害点（ルータ・リンク）を避けるために、メインマルチキャストとバックアップマルチキャストの配信経路はdisjoint（互いに疎 ＝ 同一ルータ・リンクを経由しない）である必要がある。
【０００８】
非特許文献２によれば、マルチキャストツリーは、受信者から発信者（またはRP）に向かって、各ルータがユニキャスト経路情報に従い、ホップバイホップで構築する。したがって、ある受信者から同一（あるいはネットワークトポロジ的に隣接する）発信者へ複数のマルチキャストツリーを設定しようとすると、同一ルータ・リンク経由となる傾向にある。すなわち、通常の運用では図１１のように、メインマルチキャストとバックアップマルチキャストで同一ルータを経由することになる。
【０００９】
本技術が対象とする冗長構成を持つネットワークトポロジでは、等コストのユニキャスト経路（equal-costのRPF（Reverse Path Forwarding）経路）が複数存在するため、本来、disjointなマルチキャストツリーを少なくとも２種類以上構築し得る環境である。しかしながら、一般的なPIM-SM実装では、複数のequal-cost RPF 経路（i.e. 上流ルータ）が存在する場合、最も大きなアドレスを持つ上流ルータが一意に選択されるため（非特許文献１）、ツリーが重複するという問題がある（図１１参照）。
【００１０】
これに対して負荷分散の観点から、ソースIPアドレスをkeyとするハッシュ計算により、異なる上流ルータを選択するPIM-SMの実装も存在する。しかしながら、本機能はdisjointなツリー設定を保証するものではない。
【００１１】
本発明は、上述した問題点に鑑みてなされたものであって、disjointな（経路上に共通ルータを持たない独立な）マルチキャストツリーを動的に構築することができる通信システム、ルータ位置算出装置、およびルータ位置算出プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、上記の課題を解決するためになされたもので、第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されており、前記第１の配信サーバおよび前記第２の配信サーバに最も近いルータを除く任意のルータが追加された際の論理的な追加位置は、階層構造を有する前記複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、新たに追加される追加ルータと接続される、前記第１の配信サーバおよび前記第２の配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、に基づいて算出されたことを特徴とする通信システムである。
【００１３】
また、本発明は、第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されている通信システムに対して新たに追加ルータを追加する際の論理的な位置を算出するルータ位置算出装置であって、前記配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、新たに追加される追加ルータと接続される、前記配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、を記憶する記憶部と、前記ネットワークトポロジ情報、前記追加ルータ接続情報、および前記識別値に基づいて前記追加ルータの論理的な位置を算出する位置算出部と、を有することを特徴とするルータ位置算出装置である。
【００１４】
また、本発明のルータ位置算出装置において、前記位置算出部は、前記追加ルータ接続情報に基づいて、前記追加ルータと接続される前記第１の上流ルータおよび前記第２の上流ルータを選択し、前記ネットワークトポロジ情報に基づいて、当該選択した第２の上流ルータの下流ルータを選択すると共に当該選択した下流ルータの前記第１の上流ルータを選択し、当該選択した下流ルータの前記第１の上流ルータの識別値と、前記追加ルータと接続される前記第１の上流ルータの識別値とを比較した結果に基づいて前記追加ルータの論理的な位置を算出することを特徴とする。
【００１５】
また、本発明のルータ位置算出装置において、前記位置算出部は、前記追加ルータ接続情報に基づいて、前記追加ルータと接続される前記第２の上流ルータを選択し、前記ネットワークトポロジ情報に基づいて、当該選択した第２の上流ルータと同一階層であって隣りのルータを選択すると共に当該選択した隣りのルータの下流ルータを選択し、当該選択した下流ルータの識別値に基づいて前記追加ルータの論理的な位置を算出することを特徴とする。
【００１６】
また、本発明のルータ位置算出装置において、前記位置算出部は、階層lにおける前記配置方向の位置がj番目であって、当該位置に対応する前記識別値R［l，j］を有する前記追加ルータと接続される前記第１の上流ルータ、前記第２の上流ルータの前記識別値をそれぞれR［l-1，j”］、R［l-1，j’］とし、前記追加ルータと同一階層のi番目のルータの前記第１の上流ルータ、前記第２の上流ルータの前記識別値をそれぞれR［l-1，i”］、R［l-1，i’］とした場合に、（i’＜j’）または（i’＝j’かつi”≦j”）であればi＜jが成り立つように、かつ、（i’＞j’）または（i’＝j’かつi”＞j”）であればi＞jが成り立つようにjを決定することを特徴とする。
【００１７】
また、本発明のルータ位置算出装置は、前記位置算出部によって算出された前記追加ルータの論理的な位置に基づいて前記追加ルータの前記識別値を算出する識別値算出部をさらに有することを特徴とする。
【００１８】
また、本発明は、第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されている通信システムに対して新たに追加ルータを追加する際の論理的な位置を算出する処理をコンピュータに実行させるためのルータ位置算出プログラムであって、前記配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、新たに追加される追加ルータと接続される、前記配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、を記憶する記憶部と、前記ネットワークトポロジ情報、前記追加ルータ接続情報、および前記識別値に基づいて前記追加ルータの論理的な位置を算出する位置算出部と、としてコンピュータを機能させるためのルータ位置算出プログラムである。
【発明の効果】
【００１９】
本発明によれば、disjointなマルチキャストツリーを動的に構築することができるという効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施形態によるルータ位置算出装置の構成を示すブロック図である。
【図２】本発明の一実施形態における別上流ルータ選択手法を説明するための参考図である。
【図３】本発明の一実施形態における下流ルータ選択手法を説明するための参考図である。
【図４】本発明の一実施形態におけるデータ構造を説明するための参考図である。
【図５】本発明の一実施形態におけるルータの追加例を説明するための参考図である。
【図６】本発明の一実施形態におけるルータの追加例を説明するための参考図である。
【図７】本発明の一実施形態におけるルータの追加例を説明するための参考図である。
【図８】本発明の一実施形態におけるネットワーク構成例を示す参考図である。
【図９】本発明の一実施形態における下流ルータ選択手法の手順を示すフローチャートである。
【図１０】従来の通信ネットワークの構成を示す構成図である。
【図１１】従来技術の問題点を説明するための説明図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照し、本発明の実施形態を説明する。まず、前提条件として以下を仮定する。ネットワーク構成例は図１０と同様であり、配信サーバによって送信される放送用のマルチキャストパケットと、バックアップサーバによって送信されるバックアップマルチキャストパケットとを転送する複数のルータを備えた通信システムとなっている。また、本通信システムは、マルチキャストソース（ソースホストあるいはRP（Rendezvous Point）、DC（Data Center）エッジルータ、コアルータ、顧客側エッジルータのように階層化されたネットワークトポロジを有している。メインマルチキャストソース（根）およびバックアップマルチキャストソース（根）は、それぞれ固定された１ノードのみとする。任意のルータ（節）から根に向かって、２つのequal-costな上流ルータが存在する。下流ルータは、最も大きなインタフェースアドレスを持つ上流ルータに向けてjoin（マルチキャストパケット受信へ参加）する（前述した非特許文献１参照）。
【００２２】
（別上流ルータ選択手法）
上記を満たす環境において、各下流ルータでは、２つの上流ルータにそれぞれ複数の論理的接続を設定し、メインマルチキャストおよびバックアップマルチキャストを別々の上流ルータから取得できるようにする。以下、図２を参照しながら、設定方法の原理を説明する。本通信システムを構成するルータに対して、ネットワーク管理者によって、以下の手順で設定がなされるものとする。
【００２３】
１．下流ルータXと上流ルータAを接続する物理リンクに対して２つの（論理的な）サブネット（ネットワークアドレス：NA1とNA2）を設定する。
２．下流ルータXと上流ルータBを接続する物理リンクに対して２つの（論理的な）サブネット（ネットワークアドレス：NB1とNB2）を設定する。
３．ユニキャスト経路計算対象となるサブネットを２つのグループに分類する。NA1とNB1はグループ１に、NA2とNB2はグループ２に所属させる。
４．メインマルチキャストソースが属するサブネットはグループ１に、バックアップマルチキャストソースが属するサブネットはグループ２に所属させる。
【００２４】
５．グループ１とグループ２は独立にユニキャスト経路計算を行う。これにより、ルータXからメインマルチキャストソースに向かうユニキャスト経路はNA1とNB1、バックアップマルチキャストソースに向かうユニキャスト経路はNA2とNB2となる。このように、NA1およびNB1は、メインマルチキャストパケットの転送用として割り当てられ、NA2およびNB2は、バックアップマルチキャストパケットの転送用として割り当てられることになる。
【００２５】
６．NA1とNB1ならびにNA2とNB2について、アドレスの大小関係を逆にする（e.g. NA1＞NB1，NA2＜NB2）。これにより、メインとバックアップでjoin（マルチキャストパケット受信への参加）対象の上流ルータを別（e.g. メインは上流ルータA（NA1），バックアップは上流ルータB（NB2））にする。以下、メインマルチキャストソースに向かうツリー（第１ツリー）が設定される物理リンクを第１リンク、バックアップマルチキャストソースに向かうツリー（第２ツリー）が設定される物理リンクを第２リンクと定義する。２つのマルチキャストソースに対して等コストとなる２つの上流ルータ候補が存在する場合に、上記の手法によって、各々のマルチキャストソースへ向かう経路を分岐することができる。
【００２６】
なお、上述の手法の他に、「マルチキャストソースIPアドレスをkeyとするハッシュ計算に基づく上流ルータ選択手法」を用いて、第１リンクおよび第２リンクを設定してもよい。すなわち、ルータで使用されるハッシュ関数は一意であるものとして、以下のようにすることによって、図２と同じ効果を得ることができる。
１．各ルータのハッシュ処理によって、メインマルチキャストソース（第１の配信サーバ）に向かうツリーが第１の上流ルータ（第１リンク）を選択するように（メインマルチキャストソースによって送信されるマルチキャストパケットが、各ルータの第１の上流ルータから各ルータに転送されるように）、メインマルチキャストソースのＩＰアドレスを決定する。
２．各ルータのハッシュ処理によって、バックアップマルチキャストソース（第２の配信サーバ）に向かうツリーが第２の上流ルータ（第２リンク）を選択するように（バックアップマルチキャストソースによって送信されるマルチキャストパケットが、各ルータの第２の上流ルータから各ルータに転送されるように）、バックアップマルチキャストソースのＩＰアドレスを決定する。
【００２７】
別上流ルータ選択手法として、上述した２つの方式のうちのいずれかの方式を適用した上で、下記の下流ルータ配置手法を導入することによって、マルチキャストソースに直接接続されたルータを除き、任意のルータから２つのマルチキャストソースに向けて、disjointなマルチキャストツリーを構成することが可能となる。
【００２８】
（下流ルータ配置手法）
さらに、全ての下流ルータで上流ルータの選択方針を一致させる。その上で、追加する下流ルータの（ネットワークトポロジ上の論理的な）位置を、下記の方針に従い適切に決定することにより、冒頭で述べた前提条件を満たすネットワークトポロジで、メインマルチキャストツリーとバックアップマルチキャストツリーをdisjointに設定することができる。以下、図３を参照しながら、下流ルータの追加アルゴリズムを説明する。
【００２９】
１．各階層l（l≧0）において、各ルータは３．以降に示す方針に基づき、ネットワークトポロジ上で左側より順番に並んでいるものとする。
２．初期状態として、マルチキャストソースに接続された最上流（l＝0）のルータが２台存在するものとする。
３．追加する下流ルータに対して、図２を用いて説明した設定方法に従い、メインマルチキャストを右側の上流ルータ（第１上流ルータ）から、バックアップマルチキャストを左側の上流ルータ（第２上流ルータ）から取得する設定を行う。
【００３０】
４．各ルータを一意に表すために、該ルータの位置する階層l、ならびに該階層lにおける左からの順序jを使用する。すなわち、階層lにおける左からj（j≧0）番目のルータをR［l，j］のように記述する。
５．階層0（l＝0）におけるルータについては、メインマルチキャストソースを収容するルータをR［0，1］、バックアップマルチキャストソースを収容するルータをR［0，0］と規定する。
６．ある階層l（l≧1）に下流ルータR［l，j］を新たに追加する場合を考える。まず新たな下流ルータR［l，j］と同一階層に属する他のルータをR［l，i］と記述する。ここで、i（i≧0）は、該階層l上で左側から数えたルータの順序（R［l，j］の追加前の順序）を表す。ただしi＝0を最も左側とする。
【００３１】
７．jの値（階層lにおいて左からj番目を意味する）を、以下の条件を満たすように決定する。ただしj＝0を最も左側とする。R［l，j］の第２・第１上流ルータをそれぞれR［l-1，j’］およびR［l-1，j”］とし、R［l，i］の第２・第１上流ルータをそれぞれR［l-1，i’］およびR［l-1，i”］とすると、階層lの全てのi、ならびにこれに付随する階層l-1のi'， i"について、下記の条件に従ってjを決定する。
（i’＜j’）または（i’＝j’かつi”≦j”） ⇒ i＜j
（i’＞j’）または（i’＝j’かつi”＞j”） ⇒ i＞j
【００３２】
図３に示される例では、ルータ群３０１を構成する各ルータについてはi’＜j’が満たされており、ルータ群３０２を構成する各ルータについてはi’＝j’かつi”≦j”が満たされている。したがって、階層lに追加されるルータR［l，j］はネットワークトポロジ上で、ルータ群３０１および３０２よりも右側に追加されることになる。また、ルータ群３０３を構成する各ルータについてはi’＝j’かつi”＞j”が満たされており、ルータ群３０４を構成する各ルータについてはi’＞j’が満たされている。したがって、階層lに追加されるルータR［l，j］はネットワークトポロジ上で、ルータ群３０３および３０４よりも左側に追加されることになる。上記のことから、ルータR［l，j］は、図３に示される位置に追加される。
【００３３】
図１は、本実施形態によるルータ位置算出装置の構成を示している。本ルータ位置算出装置は、階層構造を有する複数のルータを備えた通信システムに追加する新たなルータのネットワークトポロジ上の論理的な位置を、上記の下流ルータ配置手法を用いて算出する。図１において、記憶部１は各種の情報およびデータを記憶する。記憶部１によって記憶される情報およびデータには、各種パラメタや、初期NWトポロジ情報、追加ルータ接続情報、論理NWトポロジ情報等が含まれる。
【００３４】
各種パラメタには、既に構築されている通信システムで設定されているVLAN ID・IPアドレス/プレフィックス情報（各ルータのID値を含む）が含まれる。初期NWトポロジ情報は、現在の通信システムを構成する複数のルータの論理的な位置関係（ネットワークトポロジ）を示している。追加ルータ接続情報は、新たに追加される追加ルータと接続される、配信サーバまたはバックアップサーバ側に設けられた上流ルータと新たな追加ルータの論理的な位置関係を示している。追加ルータの上流ルータは、前述した別上流ルータ選択手法に従って、ネットワーク管理者によって予め各種の設定がなされているものとする。論理NWトポロジ情報は、前述した方法によって算出された位置に新たな追加ルータが配置された状態で、通信システムを構成する複数のルータの論理的な位置関係（ネットワークトポロジ）やVLAN ID・IPアドレス/プレフィックス等を示している。
【００３５】
記憶部１は演算部２に接続されている。演算部２は、初期NWトポロジ情報、追加ルータ接続情報、およびVLAN ID・IPアドレス/プレフィックス情報等を入力として演算を行い、論理NWトポロジ情報を出力する。演算部２は、ルータ論理位置計算部２１、ルータID計算部２２、VLAN ID・IPアドレス/プレフィックス生成部２３、およびNWトポロジ出力表示部２４を備えている。
【００３６】
ルータ論理位置計算部２１は、初期NWトポロジ情報と追加ルータ接続情報を用いて、前述した「下流ルータ配置手法」に従って追加ルータの論理位置を計算する。ルータID計算部２２は、論理位置を計算された各ルータに対してVLAN ID・IPアドレス/プレフィックス情報の範囲内で32bitのID値（Router ID）を計算し、付与する。VLAN ID・IPアドレス/プレフィックス生成部２３は、前述した「別上流ルータ選択手法」に従うネットワーク管理者の指示に基づいて、各ルータのインタフェースに設定すべきVLANのVLAN ID・IPアドレス/プレフィックスを生成し、付与する。これらの結果は、出力データ（論理NWトポロジ情報）として記憶部１に格納される。出力データは、NWトポロジ出力表示部２４を通じて、ルータの論理位置あるいは物理位置を基準とした可視化が可能である。
【００３７】
次に、上述した「別上流ルータ選択手法」および「下流ルータ配置手法」の実現例を説明する。
（別上流ルータ選択手法の実現例）
１．下流ルータXと上流ルータAを接続する物理リンクに対して、２つの802.1q tagged VLAN（VLAN A1とVLAN A2）を設定する。VLAN A1にネットワークアドレスNA1を、VLAN A2にネットワークアドレスNA2を割り当てる。
２．下流ルータXと上流ルータBを接続する物理リンクに対して、２つの802.1q tagged VLAN (VLAN B1とVLAN B2) を設定する。VLAN B1にネットワークアドレスNB1を、VLAN B2にネットワークアドレスNB2を割り当てる。
【００３８】
３．OSPFのプロセス（インスタンス）を２つ（プロセス1とプロセス2）起動する。各プロセスは、対象となるサブネットグループ毎にユニキャスト経路計算を独立して行う。
４．対象となるサブネットを２つのグループに分類し、それぞれOSPFプロセス1とOSPFプロセス2に所属させる。NA1とNB1はOSPFプロセス1に、NA2とNB2はOSPFプロセス2に所属させる。このように、NA1およびNB1は、メインマルチキャストパケットの転送用として割り当てられ、NA2およびNB2は、バックアップマルチキャストパケットの転送用として割り当てられることになる。
【００３９】
５．メインマルチキャストソースの属するサブネットはOSPFプロセス1に所属させる。バックアップマルチキャストソースの属するサブネットはOSPFプロセス2に所属させる。
６．NA1とNB1ならびにNA2とNB2について、アドレスの大小関係を逆にする（e.g. NA1＞NB1，NA2＜NB2）。これにより、メインとバックアップでjoin（マルチキャストパケット受信への参加）対象の上流ルータが別（e.g. メインは上流ルータA（NA1），バックアップは上流ルータB（NB2））になる。
【００４０】
（下流ルータ配置手法の実現例）
１．図４に示されるようなデータ構造を作成する。特徴を以下に示す。
（ａ）各ルータ（図４において丸印で示されている）には、互いを識別するために、（少なくとも）階層内で一意であるID値が付与されている。以降、階層lのルータR［l，i］のID値をID［l，i］のように記述する。任意のi，j（i＜j）についてID［l，i］＜ID［l，j］とする（左側のルータが小さなID値を有する）。なお、ID値の保持方法については、明示的にルータID等として各ルータに割り当ててもよいし、暗黙の値としてネットワーク運用者が一元管理してもよい。
【００４１】
（ｂ）各ルータは、同一階層の前後（左側と右側）のルータを指し示すポインタ情報（図４の*prev と*next）を有する。
（ｃ）各ルータは、１つ上流の階層について、第１上流ルータ（１個）を指し示すポインタ情報（あるいはID値）を有する（図４の*ru）。
（ｄ）各ルータは、１つ上流の階層について、第２上流ルータ（１個）を指し示すポインタ情報（あるいはID値）を有する（図４の*bu）。
【００４２】
（ｅ）各ルータは、１つ下流の階層について、第１下流ルータ（メインマルチキャスト配信経路の下流ルータ）（0〜複数個）を指し示すポインタ情報を有する（図４の**rdh，**rdt，*rd0〜*rdm）。
（ｆ）各ルータは、１つ下流の階層について、第２下流ルータ（バックアップマルチキャスト配信経路の下流ルータ）（0〜複数個）を指し示すポインタ情報を有する（図４の**bdh，**bdt，*bd0〜*bdm）。
（ｇ）各階層のルータ群を管理するための管理情報（e.g. 各階層の先頭ルータを指し示すポインタ）を保持する（図４の*L_0〜）。
【００４３】
２．階層0（最上流）にマルチキャストソース（メイン・バックアップ）を収容する２台のルータR［0，0］、R［0，1］が設置された状態を初期状態とする。
【００４４】
３．図４に対して、階層lにルータを追加した例を図５〜図７に示す。図５〜図７を用いてルータ追加アルゴリズムを説明する。図５〜図７において、下流ルータと第１上流ルータは実線で結ばれており、下流ルータと第２上流ルータは１点鎖線で結ばれている。すなわち、実線がメインマルチキャストの配信経路となり、１点鎖線がバックアップマルチキャストの配信経路となる。なお、以下の（Ａ）〜（Ｈ）の処理は、主にルータ論理位置計算部２１によって行われ、最終的に追加ルータに付与するID値の算出は、ルータID計算部２２によって行われる。以下の処理を行うためルータ論理位置計算部２１は、追加ルータの第１上流ルータおよび第２上流ルータを選択する機能、第２上流ルータの第２下流ルータを選択する機能、第２下流ルータの第１上流ルータを選択する機能、第２上流ルータの隣（本実現例では左側）の上流ルータを選択する機能、および選択したルータ同士のID値を比較する機能等を備えている。
【００４５】
（Ａ）追加ルータR［l，j］は、第２上流ルータR［l-1，j’］と第１上流ルータR［l-1，j”］へのポインタおよびID値（ID［l-1，j’］，ID［l-1，j”］を有するもの（あるいは取得可能）とする。
（Ｂ）第２上流ルータR［l-1，j’］の第２下流ルータR［l，b(k)］（k＝0〜mの自然数であり、b(k)はbdk＝bd0〜bdmに対応する。該第２下流ルータ（i.e. R［l，b(k)］) の階層lにおける左からの順序を関数b(k)により表す）の存在有無をチェックし、存在する場合には（Ｃ）へ進む。R［l-1，j’］に対してR［l，b(k)］が１つも存在しない場合は（F）へ進む。
【００４６】
（Ｃ）第２上流ルータR［l-1，j’］の第２下流ルータR［l，b(k)］をID値の小さい順に（i.e. k = 0より昇順に）選択し、順次（Ｄ）を実行する。ID値最大（k＝m）のルータR［l，b(m)］まで（Ｄ）が実行された場合（i.e. ID［l-1，{b(m)}”］≦ID［l-1，j”］）は（Ｈ）へ進む。
（Ｄ）R［l，b(k)］の第１上流ルータR［l-1，{b(k)}”］のID値（ID［l-1，{b(k)}”］）を取得し、ID［l-1，j”］と比較する。比較の結果、ID［l-1，{b(k)}”］≦ID［l-1，j”］であれば（Ｃ）に戻る。また、ID［l-1，{b(k)}”］＞ID［l-1，j”］であれば（Ｅ）へ進む。
【００４７】
（Ｅ）R［l，b(k)-1］とR［l，b(k)］の間にR[l，j]を挿入する（追加ルータの論理位置の決定）。ID［l，b(k)-1］＜ID［l，j］＜ID［l，b(k)］を満たすID［l，j］を付与して処理を終了する（e.g. ID［l，j］＝（ID［l，b(k)-1］+ID［l，b(k)］)/2）。
（Ｆ）第２上流ルータR［l-1，j’］の左側の上流ルータR［l-1，j’-1］を選択し、（Ｇ）へ進む。R［l-1，j’-1］が無い場合（j’＝0：R［l-1，j’］は階層l-1の先頭ルータ）は、R［l，j］を階層lの先頭ルータ（j＝0）として挿入する（追加ルータの論理位置の決定）。この場合、適切なID［l，0］を付与して処理を終了する（e.g. ID［l，0］＝0，ID［l，1］＝ID［l，2］/2）。
【００４８】
（Ｇ）R［l-1，j’-1］の第２下流ルータの中からR［l，b(m)］（ID値最大のルータ）を選択し、（Ｈ）へ進む。第２下流ルータが無い場合はj’＝j’-1として（Ｆ）へ戻る。
（Ｈ）R［l，b(m)］とR［l，b(m)+1］の間にR［l，j］を挿入する（追加ルータの論理位置の決定）。ID［l，b(m)］＜ID［l，j］＜ID［l，b(m)+1］を満たすID［l，j］を付与して処理を終了する（e.g. ID［l，j］＝（ID［l，b(m)］+ID［l，b(m)+1］)/2)。
【００４９】
例えば図５では、（Ｂ）→（Ｃ）→（Ｄ）→（Ｃ）→（Ｄ）→（Ｅ）で配置が終了する。まず（Ｂ）において第２上流ルータR［l-1，0］の第２下流ルータの存在有無がチェックされる。第２下流ルータが存在しているため、（Ｃ）へ進む。（Ｃ）において、R［l-1，0］の第２下流ルータR［l，0］が選択され、（Ｄ）へ進む。（Ｄ）において、R［l，0］の第１上流ルータR［l-1，1］のID値（ID［l-1，1］）とR［l，j］の第１上流ルータR［l-1，2］のID値（ID［l-1，2］）が比較される。ID［l-1，1］＜ID［l-1，2］であるため、（Ｃ）に戻る。
【００５０】
（Ｃ）においてR［l-1，0］の次の第２下流ルータR［l，1］が選択され、（Ｄ）へ進む。（Ｄ）においてR［l，1］の第１上流ルータR［l-1，3］のID値（ID［l-1，3］）とR［l，j］の第１上流ルータR［l-1，2］のID値（ID［l-1，2］）が比較される。ID［l-1，3］＞ID［l-1，2］であるため、（Ｅ）へ進む。（Ｅ）において、R［l，0］とR［l，1］の間にR［l，j］を挿入することが決定され、ID値が算出される。
【００５１】
また、図６では、（Ｂ）→（Ｃ）→（Ｄ）→（Ｃ）→（Ｄ）→（Ｃ）→（Ｈ）で配置が終了する。まず（Ｂ）において第２上流ルータR［l-1，1］の第２下流ルータの存在有無がチェックされる。第２下流ルータが存在しているため、（Ｃ）へ進む。（Ｃ）において、R［l-1，1］の第２下流ルータR［l，3］が選択され、（Ｄ）へ進む。（Ｄ）において、R［l，3］の第１上流ルータR［l-1，2］のID値（ID［l-1，2］）とR［l，j］の第１上流ルータR［l-1，4］のID値（ID［l-1，4］）が比較される。ID［l-1，2］＜ID［l-1，4］であるため、（Ｃ）に戻る。
【００５２】
（Ｃ）においてR［l-1，1］の次の第２下流ルータR［l，4］が選択され、（Ｄ）へ進む。（Ｄ）においてR［l，4］の第１上流ルータR［l-1，4］のID値（ID［l-1，4］）とR［l，j］の第１上流ルータR［l-1，4］のID値（ID［l-1，4］）が比較される。同一のID値であるため、（Ｃ）に戻る。（Ｃ）において、R［l-1，1］のID値最大の第２下流ルータR［l，4］まで（Ｄ）が実行されたので、（Ｈ）へ進む。（Ｈ）において、R［l，4］とR［l，5］の間にR［l，j］を挿入することが決定され、ID値が算出される。
【００５３】
また、図７では、（Ｂ）→（Ｆ）→（Ｇ）→（Ｈ）で配置が終了する。まず（Ｂ）において第２上流ルータR［l-1，3］の第２下流ルータの存在有無がチェックされる。第２下流ルータが存在しないため、（Ｆ）へ進む。（Ｆ）において、R［l-1，3］の左側のルータR［l-1，2］が選択され、（Ｇ）へ進む。（Ｇ）において、R［l-1，2］の第２下流ルータの中からID値が最大のルータR［l，6］が選択され、（Ｈ）へ進む。（Ｈ）において、R［l，6］とR［l，7］の間にR［l，j］を挿入することが決定され、ID値が算出される。
【００５４】
上述した追加工程を繰り返した例を図８に示す。l≧1以上の階層における任意のルータで、２種類のdisjointなマルチキャスト配信木が設定できていることが分かる。どのルータを起点にしてメインおよびバックアップのマルチキャスト配信経路を設定する場合でも、双方の配信経路が重ならないようにすることができる。
【００５５】
図９は、上述した下流ルータ配置手法の手順を示している。以下、上記の処理と対応させながら、図９に示される処理を説明する。まず、引数kに0を設定し、第２上流ルータの引数R［l-1，j’］に追加ルータR［l，j］の第２上流ルータを設定すると共に、第１上流ルータの引数R［l-1，j”］に追加ルータR［l，j］の第１上流ルータを設定する（ステップＳ９０１）。
【００５６】
続いて、R［l-1，j’］に第２下流ルータが存在するか否かを判定する（ステップＳ９０２）。このステップは（Ｂ）に対応する。第２下流ルータが存在する場合にはステップＳ９０３へ進み、存在しなかった場合にはステップＳ９０８へ進む。ステップＳ９０３においては、第２下流ルータの引数R［l，b(k)］にR［l-1，j’］の第２下流ルータを設定すると共に、第１上流ルータの引数R［l-1，{b(k)}”］にR［l，b(k)］の第１上流ルータを設定する。このステップは（Ｃ）に対応する。
【００５７】
続いて、ID［l-1，{b(k)}”］≦ID［l-1，j”］であるか否かを判定する（ステップＳ９０４）。このステップは（Ｄ）に対応する。ID［l-1，{b(k)}”］≦ID［l-1，j”］であった場合にはステップＳ９０６へ進み、ID［l-1，{b(k)}”］＞ID［l-1，j”］であった場合にはステップＳ９０５へ進む。ステップＳ９０５においては、ID［l，b(k)-1］＜ID［l，j］＜ID［l，b(k)］を満たすID［l，j］を付与して処理を終了する。このステップは（Ｅ）に対応する。
【００５８】
また、ステップＳ９０６においては、R［l-1，j’］の第２下流ルータのうち、ID値が最大のルータまでID値の比較を行ったか否かを判定する。このステップは（Ｃ）に対応する。ID値が最大のルータまでID値の比較を行っていない場合には、次の第２下流ルータの処理を行うためkの値を１増加し（ステップＳ９０７）、ステップＳ９０３に戻る。また、ID値が最大のルータまでID値の比較を行った場合には、ID値最大の第２下流ルータの引数R［l，b(m)］の設定を行い（ステップＳ９１０）、ID［l，b(m)］＜ID［l，j］＜ID［l，b(m)+1］を満たすID［l，j］を付与して処理を終了する（ステップＳ９１１）。ステップＳ９１０〜Ｓ９１１は（Ｈ）に対応する。
【００５９】
一方、ステップＳ９０８においては、第２上流ルータR［l-1，j’］に左側のルータが存在するか否かを判定する。このステップは（Ｆ）に対応する。左側のルータが存在しない、すなわちR［l-1，j’］が階層l-1の先頭のルータである場合、R［l，j］を階層lの先頭ルータとし、適切なID［l，0］を付与して処理を終了する（ステップＳ９１２）。このステップは（Ｆ）に対応する。また、左側のルータが存在した場合、R［l-1，j’］に第２下流ルータが存在するか否かを判定する（ステップＳ９０９）。第２下流ルータが存在した場合にはステップＳ９１０へ進み、第２下流ルータが存在しなかった場合には、左側のルータについてステップＳ９０８の処理を再度行う。
【００６０】
上述したように、本実施形態の別上流ルータ選択手法では、配信サーバまたはバックアップサーバに最も近いルータを除く任意のルータにおいて、２つの上流ルータと接続する各物理リンクに対してそれぞれ２つずつサブネットが設定されると共に、各サブネットがメインマルチキャスト用およびバックアップマルチキャスト用に適切にグループ化され、各サブネットのネットワークアドレスが、所定の関係を満たすように設定される。これによって、２つのマルチキャストソースに対して等コストとなる２つの上流ルータ候補が存在する場合に、各々のマルチキャストソースへ向かう経路を分岐することができる。
【００６１】
また、本実施形態の下流ルータ配置手法では、階層構造を有する複数のルータの論理的な位置関係を示す初期NWトポロジ情報（ネットワークトポロジ情報）と、追加ルータと接続される上流ルータと追加ルータの論理的な位置関係を示す追加ルータ接続情報と、複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値（ID値）とに基づいて、追加ルータの論理的な位置を算出することによって、全てのルータにおいて、disjointなマルチキャスト配信経路の確立が保証される。
【００６２】
よって、本実施形態によれば、別上流ルータ選択手法および下流ルータ配置手法を組み合わせることによって、disjointなマルチキャストツリーを動的に構築することができる。したがって、ネットワーク管理者の意思により、マルチキャストソースあるいはグループ単位で、２つのdisjointな配信経路に分離してマルチキャスト配信を行うことが可能となる。
【００６３】
また、既存ルータの持つOSPF機能、PIM-SM機能のみを用いて、disjointなマルチキャスト配信経路を確保することができる。静的にマルチキャスト配信経路を固定するのではなく、従来と同様、配信経路はOSPF/PIM-SMにより動的に決定されるため、ネットワーク障害時にはOSPF/PIM-SMによる配信経路切り替えが機能する。
【００６４】
以上、図面を参照して本発明の実施形態について詳述してきたが、具体的な構成はこれらの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。例えば、別上流ルータ選択手法において、経路を分岐するためにはNA1＜NB1，NA2＞NB2としてもよく、その場合にはネットワークトポロジ上でメインマルチキャストソースとバックアップマルチキャストソースの位置が逆となる。
【００６５】
また、上述した実施形態によるルータ位置算出装置は、その動作および機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行させることにより実現してもよい。
【００６６】
ここで、「コンピュータ」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００６７】
また、上述したプログラムは、このプログラムを記憶装置等に格納したコンピュータから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上述したプログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータに既に記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【符号の説明】
【００６８】
１・・・記憶部、２・・・演算部、２１・・・ルータ論理位置計算部、２２・・・ルータID計算部、２３・・・VLAN ID・IPアドレス/プレフィックス生成部、２４・・・NWトポロジ出力表示部、１０１・・・放送配信サーバ、１０２，１０９・・・Ｌ２スイッチ、１０３・・・バックアップサーバ、１０４ａ，１０４ｂ，１０５ａ，１０５ｂ，１０６ａ，１０６ｂ，１０７・・・ルータ、１０８・・・通信制御装置、１１０・・・クライアント端末
【技術分野】
【０００１】
本発明は、配信サーバによって送信される放送用のメインマルチキャストパケットと、バックアップサーバによって送信されるバックアップマルチキャストパケットとを転送する複数のルータを備えた通信システムに関する。また、本発明は、本通信システムを構成するルータの論理的な位置関係に係る処理を行うルータ位置算出装置およびルータ位置算出プログラムにも関する。
【背景技術】
【０００２】
動画配信等のサービスを実現するために、OSI（Open Systems Interconnection） Layer3層のIP（Internet Protocol）においてマルチキャスト（非特許文献１参照）が定義され、これに対応した各種プロトコル（非特許文献２および３参照）が実装・運用されている。しかし、IP層における（IP経路制御プロトコルに基づく）ネットワーク障害の検出・復旧に数秒〜数10秒の通信断を伴うことが問題となる。そこで、冗長構成を持つIPネットワークを対象として、この通信断時間を補償し、サービスを無瞬断化するために、本発明者は特願２００４−０６０５２８、特願２００４−３４９６６５、および特願２００５−０６２２９３に記載の技術を提案している。
【０００３】
マルチキャスト配信経路の決定は、マルチキャスト受信者から発信者（またはランデブーポイント（RP）と呼ばれる特別なノード）に向かうユニキャスト経路情報に基づいて、PIM-SMマルチキャスト経路制御プロトコル（非特許文献２参照）が行う。ユニキャスト経路情報は、OSPF（Open Shortest Path First）（非特許文献３参照）等のユニキャスト経路制御プロトコルによって生成される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Beau Williamson著，「ＩＰマルチキャストネットワーク開発ガイドＶｏ１．１」，ソフトバンクパブリッシング株式会社，２００１年７月３日
【非特許文献２】D.Estrin，他９名，RFC2362-Protocol Independent Multicast-Sparse Mode（PIM-SM）:Protocol Specification，［online］，１９９８年，The Internet Society，［２０１０年５月２６日検索］，インターネット＜URL: http://www.faqs.org/rfcs/rfc2362.html＞
【非特許文献３】J.Moy，RFC2328-OSPF Version 2，［online］，１９９８年，The Internet Society，［２０１０年５月２６日検索］，インターネット＜URL: http://www.faqs.org/rfcs/rfc2328.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００５】
図１０は、本発明者が提案した技術による通信ネットワークの構成を示している。放送配信サーバ１０１は、配信対象のストリームデータが格納されたマルチキャストパケットを送信する。送信されたマルチキャストパケットは、通常配信用（メイン）マルチキャストＧｍとして、Ｌ２スイッチ１０２および各通信装置（ルータ１０４ｂ，１０５ｂ，１０６ｂ，１０７およびＬ２スイッチ１０９）を経由してクライアント端末１１０へ転送される。また、Ｌ２スイッチ１０２によってマルチキャストパケットが複製され、バックアップサーバ１０３へ送信される。バックアップサーバ１０３は、受信したマルチキャストパケットを複製し、２つの予備配信用（バックアップ）マルチキャストＧｂ１およびＧｂ２として送信する。
【０００６】
バックアップマルチキャストＧｂ２には、バックアップサーバ１０３によって一定の遅延が付加される。バックアップマルチキャストＧｂ１およびＧｂ２は、定常時にはルータ１０４ａで破棄される。クライアント端末１１０に最も近いエッジのルータ１０７の近傍には通信制御装置１０８が設けられている。通信制御装置１０８は、メインマルチキャストＧｍの配信断を検出した場合、バックアップマルチキャストＧｂ１およびＧｂ２の受信に参加する。バックアップマルチキャストＧｂ１およびＧｂ２はルータ１０４ａから、ルータ１０５ａ，１０６ａ，１０７を経由して、通信制御装置１０８によって受信される。
【０００７】
通信制御装置１０８は、受信したバックアップマルチキャストＧｂ１およびＧｂ２をメインマルチキャストに変換して代理出力する（図１０のマルチキャストＧｍ’）。この際、障害点（ルータ・リンク）を避けるために、メインマルチキャストとバックアップマルチキャストの配信経路はdisjoint（互いに疎 ＝ 同一ルータ・リンクを経由しない）である必要がある。
【０００８】
非特許文献２によれば、マルチキャストツリーは、受信者から発信者（またはRP）に向かって、各ルータがユニキャスト経路情報に従い、ホップバイホップで構築する。したがって、ある受信者から同一（あるいはネットワークトポロジ的に隣接する）発信者へ複数のマルチキャストツリーを設定しようとすると、同一ルータ・リンク経由となる傾向にある。すなわち、通常の運用では図１１のように、メインマルチキャストとバックアップマルチキャストで同一ルータを経由することになる。
【０００９】
本技術が対象とする冗長構成を持つネットワークトポロジでは、等コストのユニキャスト経路（equal-costのRPF（Reverse Path Forwarding）経路）が複数存在するため、本来、disjointなマルチキャストツリーを少なくとも２種類以上構築し得る環境である。しかしながら、一般的なPIM-SM実装では、複数のequal-cost RPF 経路（i.e. 上流ルータ）が存在する場合、最も大きなアドレスを持つ上流ルータが一意に選択されるため（非特許文献１）、ツリーが重複するという問題がある（図１１参照）。
【００１０】
これに対して負荷分散の観点から、ソースIPアドレスをkeyとするハッシュ計算により、異なる上流ルータを選択するPIM-SMの実装も存在する。しかしながら、本機能はdisjointなツリー設定を保証するものではない。
【００１１】
本発明は、上述した問題点に鑑みてなされたものであって、disjointな（経路上に共通ルータを持たない独立な）マルチキャストツリーを動的に構築することができる通信システム、ルータ位置算出装置、およびルータ位置算出プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、上記の課題を解決するためになされたもので、第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されており、前記第１の配信サーバおよび前記第２の配信サーバに最も近いルータを除く任意のルータが追加された際の論理的な追加位置は、階層構造を有する前記複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、新たに追加される追加ルータと接続される、前記第１の配信サーバおよび前記第２の配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、に基づいて算出されたことを特徴とする通信システムである。
【００１３】
また、本発明は、第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されている通信システムに対して新たに追加ルータを追加する際の論理的な位置を算出するルータ位置算出装置であって、前記配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、新たに追加される追加ルータと接続される、前記配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、を記憶する記憶部と、前記ネットワークトポロジ情報、前記追加ルータ接続情報、および前記識別値に基づいて前記追加ルータの論理的な位置を算出する位置算出部と、を有することを特徴とするルータ位置算出装置である。
【００１４】
また、本発明のルータ位置算出装置において、前記位置算出部は、前記追加ルータ接続情報に基づいて、前記追加ルータと接続される前記第１の上流ルータおよび前記第２の上流ルータを選択し、前記ネットワークトポロジ情報に基づいて、当該選択した第２の上流ルータの下流ルータを選択すると共に当該選択した下流ルータの前記第１の上流ルータを選択し、当該選択した下流ルータの前記第１の上流ルータの識別値と、前記追加ルータと接続される前記第１の上流ルータの識別値とを比較した結果に基づいて前記追加ルータの論理的な位置を算出することを特徴とする。
【００１５】
また、本発明のルータ位置算出装置において、前記位置算出部は、前記追加ルータ接続情報に基づいて、前記追加ルータと接続される前記第２の上流ルータを選択し、前記ネットワークトポロジ情報に基づいて、当該選択した第２の上流ルータと同一階層であって隣りのルータを選択すると共に当該選択した隣りのルータの下流ルータを選択し、当該選択した下流ルータの識別値に基づいて前記追加ルータの論理的な位置を算出することを特徴とする。
【００１６】
また、本発明のルータ位置算出装置において、前記位置算出部は、階層lにおける前記配置方向の位置がj番目であって、当該位置に対応する前記識別値R［l，j］を有する前記追加ルータと接続される前記第１の上流ルータ、前記第２の上流ルータの前記識別値をそれぞれR［l-1，j”］、R［l-1，j’］とし、前記追加ルータと同一階層のi番目のルータの前記第１の上流ルータ、前記第２の上流ルータの前記識別値をそれぞれR［l-1，i”］、R［l-1，i’］とした場合に、（i’＜j’）または（i’＝j’かつi”≦j”）であればi＜jが成り立つように、かつ、（i’＞j’）または（i’＝j’かつi”＞j”）であればi＞jが成り立つようにjを決定することを特徴とする。
【００１７】
また、本発明のルータ位置算出装置は、前記位置算出部によって算出された前記追加ルータの論理的な位置に基づいて前記追加ルータの前記識別値を算出する識別値算出部をさらに有することを特徴とする。
【００１８】
また、本発明は、第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されている通信システムに対して新たに追加ルータを追加する際の論理的な位置を算出する処理をコンピュータに実行させるためのルータ位置算出プログラムであって、前記配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、新たに追加される追加ルータと接続される、前記配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、を記憶する記憶部と、前記ネットワークトポロジ情報、前記追加ルータ接続情報、および前記識別値に基づいて前記追加ルータの論理的な位置を算出する位置算出部と、としてコンピュータを機能させるためのルータ位置算出プログラムである。
【発明の効果】
【００１９】
本発明によれば、disjointなマルチキャストツリーを動的に構築することができるという効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施形態によるルータ位置算出装置の構成を示すブロック図である。
【図２】本発明の一実施形態における別上流ルータ選択手法を説明するための参考図である。
【図３】本発明の一実施形態における下流ルータ選択手法を説明するための参考図である。
【図４】本発明の一実施形態におけるデータ構造を説明するための参考図である。
【図５】本発明の一実施形態におけるルータの追加例を説明するための参考図である。
【図６】本発明の一実施形態におけるルータの追加例を説明するための参考図である。
【図７】本発明の一実施形態におけるルータの追加例を説明するための参考図である。
【図８】本発明の一実施形態におけるネットワーク構成例を示す参考図である。
【図９】本発明の一実施形態における下流ルータ選択手法の手順を示すフローチャートである。
【図１０】従来の通信ネットワークの構成を示す構成図である。
【図１１】従来技術の問題点を説明するための説明図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照し、本発明の実施形態を説明する。まず、前提条件として以下を仮定する。ネットワーク構成例は図１０と同様であり、配信サーバによって送信される放送用のマルチキャストパケットと、バックアップサーバによって送信されるバックアップマルチキャストパケットとを転送する複数のルータを備えた通信システムとなっている。また、本通信システムは、マルチキャストソース（ソースホストあるいはRP（Rendezvous Point）、DC（Data Center）エッジルータ、コアルータ、顧客側エッジルータのように階層化されたネットワークトポロジを有している。メインマルチキャストソース（根）およびバックアップマルチキャストソース（根）は、それぞれ固定された１ノードのみとする。任意のルータ（節）から根に向かって、２つのequal-costな上流ルータが存在する。下流ルータは、最も大きなインタフェースアドレスを持つ上流ルータに向けてjoin（マルチキャストパケット受信へ参加）する（前述した非特許文献１参照）。
【００２２】
（別上流ルータ選択手法）
上記を満たす環境において、各下流ルータでは、２つの上流ルータにそれぞれ複数の論理的接続を設定し、メインマルチキャストおよびバックアップマルチキャストを別々の上流ルータから取得できるようにする。以下、図２を参照しながら、設定方法の原理を説明する。本通信システムを構成するルータに対して、ネットワーク管理者によって、以下の手順で設定がなされるものとする。
【００２３】
１．下流ルータXと上流ルータAを接続する物理リンクに対して２つの（論理的な）サブネット（ネットワークアドレス：NA1とNA2）を設定する。
２．下流ルータXと上流ルータBを接続する物理リンクに対して２つの（論理的な）サブネット（ネットワークアドレス：NB1とNB2）を設定する。
３．ユニキャスト経路計算対象となるサブネットを２つのグループに分類する。NA1とNB1はグループ１に、NA2とNB2はグループ２に所属させる。
４．メインマルチキャストソースが属するサブネットはグループ１に、バックアップマルチキャストソースが属するサブネットはグループ２に所属させる。
【００２４】
５．グループ１とグループ２は独立にユニキャスト経路計算を行う。これにより、ルータXからメインマルチキャストソースに向かうユニキャスト経路はNA1とNB1、バックアップマルチキャストソースに向かうユニキャスト経路はNA2とNB2となる。このように、NA1およびNB1は、メインマルチキャストパケットの転送用として割り当てられ、NA2およびNB2は、バックアップマルチキャストパケットの転送用として割り当てられることになる。
【００２５】
６．NA1とNB1ならびにNA2とNB2について、アドレスの大小関係を逆にする（e.g. NA1＞NB1，NA2＜NB2）。これにより、メインとバックアップでjoin（マルチキャストパケット受信への参加）対象の上流ルータを別（e.g. メインは上流ルータA（NA1），バックアップは上流ルータB（NB2））にする。以下、メインマルチキャストソースに向かうツリー（第１ツリー）が設定される物理リンクを第１リンク、バックアップマルチキャストソースに向かうツリー（第２ツリー）が設定される物理リンクを第２リンクと定義する。２つのマルチキャストソースに対して等コストとなる２つの上流ルータ候補が存在する場合に、上記の手法によって、各々のマルチキャストソースへ向かう経路を分岐することができる。
【００２６】
なお、上述の手法の他に、「マルチキャストソースIPアドレスをkeyとするハッシュ計算に基づく上流ルータ選択手法」を用いて、第１リンクおよび第２リンクを設定してもよい。すなわち、ルータで使用されるハッシュ関数は一意であるものとして、以下のようにすることによって、図２と同じ効果を得ることができる。
１．各ルータのハッシュ処理によって、メインマルチキャストソース（第１の配信サーバ）に向かうツリーが第１の上流ルータ（第１リンク）を選択するように（メインマルチキャストソースによって送信されるマルチキャストパケットが、各ルータの第１の上流ルータから各ルータに転送されるように）、メインマルチキャストソースのＩＰアドレスを決定する。
２．各ルータのハッシュ処理によって、バックアップマルチキャストソース（第２の配信サーバ）に向かうツリーが第２の上流ルータ（第２リンク）を選択するように（バックアップマルチキャストソースによって送信されるマルチキャストパケットが、各ルータの第２の上流ルータから各ルータに転送されるように）、バックアップマルチキャストソースのＩＰアドレスを決定する。
【００２７】
別上流ルータ選択手法として、上述した２つの方式のうちのいずれかの方式を適用した上で、下記の下流ルータ配置手法を導入することによって、マルチキャストソースに直接接続されたルータを除き、任意のルータから２つのマルチキャストソースに向けて、disjointなマルチキャストツリーを構成することが可能となる。
【００２８】
（下流ルータ配置手法）
さらに、全ての下流ルータで上流ルータの選択方針を一致させる。その上で、追加する下流ルータの（ネットワークトポロジ上の論理的な）位置を、下記の方針に従い適切に決定することにより、冒頭で述べた前提条件を満たすネットワークトポロジで、メインマルチキャストツリーとバックアップマルチキャストツリーをdisjointに設定することができる。以下、図３を参照しながら、下流ルータの追加アルゴリズムを説明する。
【００２９】
１．各階層l（l≧0）において、各ルータは３．以降に示す方針に基づき、ネットワークトポロジ上で左側より順番に並んでいるものとする。
２．初期状態として、マルチキャストソースに接続された最上流（l＝0）のルータが２台存在するものとする。
３．追加する下流ルータに対して、図２を用いて説明した設定方法に従い、メインマルチキャストを右側の上流ルータ（第１上流ルータ）から、バックアップマルチキャストを左側の上流ルータ（第２上流ルータ）から取得する設定を行う。
【００３０】
４．各ルータを一意に表すために、該ルータの位置する階層l、ならびに該階層lにおける左からの順序jを使用する。すなわち、階層lにおける左からj（j≧0）番目のルータをR［l，j］のように記述する。
５．階層0（l＝0）におけるルータについては、メインマルチキャストソースを収容するルータをR［0，1］、バックアップマルチキャストソースを収容するルータをR［0，0］と規定する。
６．ある階層l（l≧1）に下流ルータR［l，j］を新たに追加する場合を考える。まず新たな下流ルータR［l，j］と同一階層に属する他のルータをR［l，i］と記述する。ここで、i（i≧0）は、該階層l上で左側から数えたルータの順序（R［l，j］の追加前の順序）を表す。ただしi＝0を最も左側とする。
【００３１】
７．jの値（階層lにおいて左からj番目を意味する）を、以下の条件を満たすように決定する。ただしj＝0を最も左側とする。R［l，j］の第２・第１上流ルータをそれぞれR［l-1，j’］およびR［l-1，j”］とし、R［l，i］の第２・第１上流ルータをそれぞれR［l-1，i’］およびR［l-1，i”］とすると、階層lの全てのi、ならびにこれに付随する階層l-1のi'， i"について、下記の条件に従ってjを決定する。
（i’＜j’）または（i’＝j’かつi”≦j”） ⇒ i＜j
（i’＞j’）または（i’＝j’かつi”＞j”） ⇒ i＞j
【００３２】
図３に示される例では、ルータ群３０１を構成する各ルータについてはi’＜j’が満たされており、ルータ群３０２を構成する各ルータについてはi’＝j’かつi”≦j”が満たされている。したがって、階層lに追加されるルータR［l，j］はネットワークトポロジ上で、ルータ群３０１および３０２よりも右側に追加されることになる。また、ルータ群３０３を構成する各ルータについてはi’＝j’かつi”＞j”が満たされており、ルータ群３０４を構成する各ルータについてはi’＞j’が満たされている。したがって、階層lに追加されるルータR［l，j］はネットワークトポロジ上で、ルータ群３０３および３０４よりも左側に追加されることになる。上記のことから、ルータR［l，j］は、図３に示される位置に追加される。
【００３３】
図１は、本実施形態によるルータ位置算出装置の構成を示している。本ルータ位置算出装置は、階層構造を有する複数のルータを備えた通信システムに追加する新たなルータのネットワークトポロジ上の論理的な位置を、上記の下流ルータ配置手法を用いて算出する。図１において、記憶部１は各種の情報およびデータを記憶する。記憶部１によって記憶される情報およびデータには、各種パラメタや、初期NWトポロジ情報、追加ルータ接続情報、論理NWトポロジ情報等が含まれる。
【００３４】
各種パラメタには、既に構築されている通信システムで設定されているVLAN ID・IPアドレス/プレフィックス情報（各ルータのID値を含む）が含まれる。初期NWトポロジ情報は、現在の通信システムを構成する複数のルータの論理的な位置関係（ネットワークトポロジ）を示している。追加ルータ接続情報は、新たに追加される追加ルータと接続される、配信サーバまたはバックアップサーバ側に設けられた上流ルータと新たな追加ルータの論理的な位置関係を示している。追加ルータの上流ルータは、前述した別上流ルータ選択手法に従って、ネットワーク管理者によって予め各種の設定がなされているものとする。論理NWトポロジ情報は、前述した方法によって算出された位置に新たな追加ルータが配置された状態で、通信システムを構成する複数のルータの論理的な位置関係（ネットワークトポロジ）やVLAN ID・IPアドレス/プレフィックス等を示している。
【００３５】
記憶部１は演算部２に接続されている。演算部２は、初期NWトポロジ情報、追加ルータ接続情報、およびVLAN ID・IPアドレス/プレフィックス情報等を入力として演算を行い、論理NWトポロジ情報を出力する。演算部２は、ルータ論理位置計算部２１、ルータID計算部２２、VLAN ID・IPアドレス/プレフィックス生成部２３、およびNWトポロジ出力表示部２４を備えている。
【００３６】
ルータ論理位置計算部２１は、初期NWトポロジ情報と追加ルータ接続情報を用いて、前述した「下流ルータ配置手法」に従って追加ルータの論理位置を計算する。ルータID計算部２２は、論理位置を計算された各ルータに対してVLAN ID・IPアドレス/プレフィックス情報の範囲内で32bitのID値（Router ID）を計算し、付与する。VLAN ID・IPアドレス/プレフィックス生成部２３は、前述した「別上流ルータ選択手法」に従うネットワーク管理者の指示に基づいて、各ルータのインタフェースに設定すべきVLANのVLAN ID・IPアドレス/プレフィックスを生成し、付与する。これらの結果は、出力データ（論理NWトポロジ情報）として記憶部１に格納される。出力データは、NWトポロジ出力表示部２４を通じて、ルータの論理位置あるいは物理位置を基準とした可視化が可能である。
【００３７】
次に、上述した「別上流ルータ選択手法」および「下流ルータ配置手法」の実現例を説明する。
（別上流ルータ選択手法の実現例）
１．下流ルータXと上流ルータAを接続する物理リンクに対して、２つの802.1q tagged VLAN（VLAN A1とVLAN A2）を設定する。VLAN A1にネットワークアドレスNA1を、VLAN A2にネットワークアドレスNA2を割り当てる。
２．下流ルータXと上流ルータBを接続する物理リンクに対して、２つの802.1q tagged VLAN (VLAN B1とVLAN B2) を設定する。VLAN B1にネットワークアドレスNB1を、VLAN B2にネットワークアドレスNB2を割り当てる。
【００３８】
３．OSPFのプロセス（インスタンス）を２つ（プロセス1とプロセス2）起動する。各プロセスは、対象となるサブネットグループ毎にユニキャスト経路計算を独立して行う。
４．対象となるサブネットを２つのグループに分類し、それぞれOSPFプロセス1とOSPFプロセス2に所属させる。NA1とNB1はOSPFプロセス1に、NA2とNB2はOSPFプロセス2に所属させる。このように、NA1およびNB1は、メインマルチキャストパケットの転送用として割り当てられ、NA2およびNB2は、バックアップマルチキャストパケットの転送用として割り当てられることになる。
【００３９】
５．メインマルチキャストソースの属するサブネットはOSPFプロセス1に所属させる。バックアップマルチキャストソースの属するサブネットはOSPFプロセス2に所属させる。
６．NA1とNB1ならびにNA2とNB2について、アドレスの大小関係を逆にする（e.g. NA1＞NB1，NA2＜NB2）。これにより、メインとバックアップでjoin（マルチキャストパケット受信への参加）対象の上流ルータが別（e.g. メインは上流ルータA（NA1），バックアップは上流ルータB（NB2））になる。
【００４０】
（下流ルータ配置手法の実現例）
１．図４に示されるようなデータ構造を作成する。特徴を以下に示す。
（ａ）各ルータ（図４において丸印で示されている）には、互いを識別するために、（少なくとも）階層内で一意であるID値が付与されている。以降、階層lのルータR［l，i］のID値をID［l，i］のように記述する。任意のi，j（i＜j）についてID［l，i］＜ID［l，j］とする（左側のルータが小さなID値を有する）。なお、ID値の保持方法については、明示的にルータID等として各ルータに割り当ててもよいし、暗黙の値としてネットワーク運用者が一元管理してもよい。
【００４１】
（ｂ）各ルータは、同一階層の前後（左側と右側）のルータを指し示すポインタ情報（図４の*prev と*next）を有する。
（ｃ）各ルータは、１つ上流の階層について、第１上流ルータ（１個）を指し示すポインタ情報（あるいはID値）を有する（図４の*ru）。
（ｄ）各ルータは、１つ上流の階層について、第２上流ルータ（１個）を指し示すポインタ情報（あるいはID値）を有する（図４の*bu）。
【００４２】
（ｅ）各ルータは、１つ下流の階層について、第１下流ルータ（メインマルチキャスト配信経路の下流ルータ）（0〜複数個）を指し示すポインタ情報を有する（図４の**rdh，**rdt，*rd0〜*rdm）。
（ｆ）各ルータは、１つ下流の階層について、第２下流ルータ（バックアップマルチキャスト配信経路の下流ルータ）（0〜複数個）を指し示すポインタ情報を有する（図４の**bdh，**bdt，*bd0〜*bdm）。
（ｇ）各階層のルータ群を管理するための管理情報（e.g. 各階層の先頭ルータを指し示すポインタ）を保持する（図４の*L_0〜）。
【００４３】
２．階層0（最上流）にマルチキャストソース（メイン・バックアップ）を収容する２台のルータR［0，0］、R［0，1］が設置された状態を初期状態とする。
【００４４】
３．図４に対して、階層lにルータを追加した例を図５〜図７に示す。図５〜図７を用いてルータ追加アルゴリズムを説明する。図５〜図７において、下流ルータと第１上流ルータは実線で結ばれており、下流ルータと第２上流ルータは１点鎖線で結ばれている。すなわち、実線がメインマルチキャストの配信経路となり、１点鎖線がバックアップマルチキャストの配信経路となる。なお、以下の（Ａ）〜（Ｈ）の処理は、主にルータ論理位置計算部２１によって行われ、最終的に追加ルータに付与するID値の算出は、ルータID計算部２２によって行われる。以下の処理を行うためルータ論理位置計算部２１は、追加ルータの第１上流ルータおよび第２上流ルータを選択する機能、第２上流ルータの第２下流ルータを選択する機能、第２下流ルータの第１上流ルータを選択する機能、第２上流ルータの隣（本実現例では左側）の上流ルータを選択する機能、および選択したルータ同士のID値を比較する機能等を備えている。
【００４５】
（Ａ）追加ルータR［l，j］は、第２上流ルータR［l-1，j’］と第１上流ルータR［l-1，j”］へのポインタおよびID値（ID［l-1，j’］，ID［l-1，j”］を有するもの（あるいは取得可能）とする。
（Ｂ）第２上流ルータR［l-1，j’］の第２下流ルータR［l，b(k)］（k＝0〜mの自然数であり、b(k)はbdk＝bd0〜bdmに対応する。該第２下流ルータ（i.e. R［l，b(k)］) の階層lにおける左からの順序を関数b(k)により表す）の存在有無をチェックし、存在する場合には（Ｃ）へ進む。R［l-1，j’］に対してR［l，b(k)］が１つも存在しない場合は（F）へ進む。
【００４６】
（Ｃ）第２上流ルータR［l-1，j’］の第２下流ルータR［l，b(k)］をID値の小さい順に（i.e. k = 0より昇順に）選択し、順次（Ｄ）を実行する。ID値最大（k＝m）のルータR［l，b(m)］まで（Ｄ）が実行された場合（i.e. ID［l-1，{b(m)}”］≦ID［l-1，j”］）は（Ｈ）へ進む。
（Ｄ）R［l，b(k)］の第１上流ルータR［l-1，{b(k)}”］のID値（ID［l-1，{b(k)}”］）を取得し、ID［l-1，j”］と比較する。比較の結果、ID［l-1，{b(k)}”］≦ID［l-1，j”］であれば（Ｃ）に戻る。また、ID［l-1，{b(k)}”］＞ID［l-1，j”］であれば（Ｅ）へ進む。
【００４７】
（Ｅ）R［l，b(k)-1］とR［l，b(k)］の間にR[l，j]を挿入する（追加ルータの論理位置の決定）。ID［l，b(k)-1］＜ID［l，j］＜ID［l，b(k)］を満たすID［l，j］を付与して処理を終了する（e.g. ID［l，j］＝（ID［l，b(k)-1］+ID［l，b(k)］)/2）。
（Ｆ）第２上流ルータR［l-1，j’］の左側の上流ルータR［l-1，j’-1］を選択し、（Ｇ）へ進む。R［l-1，j’-1］が無い場合（j’＝0：R［l-1，j’］は階層l-1の先頭ルータ）は、R［l，j］を階層lの先頭ルータ（j＝0）として挿入する（追加ルータの論理位置の決定）。この場合、適切なID［l，0］を付与して処理を終了する（e.g. ID［l，0］＝0，ID［l，1］＝ID［l，2］/2）。
【００４８】
（Ｇ）R［l-1，j’-1］の第２下流ルータの中からR［l，b(m)］（ID値最大のルータ）を選択し、（Ｈ）へ進む。第２下流ルータが無い場合はj’＝j’-1として（Ｆ）へ戻る。
（Ｈ）R［l，b(m)］とR［l，b(m)+1］の間にR［l，j］を挿入する（追加ルータの論理位置の決定）。ID［l，b(m)］＜ID［l，j］＜ID［l，b(m)+1］を満たすID［l，j］を付与して処理を終了する（e.g. ID［l，j］＝（ID［l，b(m)］+ID［l，b(m)+1］)/2)。
【００４９】
例えば図５では、（Ｂ）→（Ｃ）→（Ｄ）→（Ｃ）→（Ｄ）→（Ｅ）で配置が終了する。まず（Ｂ）において第２上流ルータR［l-1，0］の第２下流ルータの存在有無がチェックされる。第２下流ルータが存在しているため、（Ｃ）へ進む。（Ｃ）において、R［l-1，0］の第２下流ルータR［l，0］が選択され、（Ｄ）へ進む。（Ｄ）において、R［l，0］の第１上流ルータR［l-1，1］のID値（ID［l-1，1］）とR［l，j］の第１上流ルータR［l-1，2］のID値（ID［l-1，2］）が比較される。ID［l-1，1］＜ID［l-1，2］であるため、（Ｃ）に戻る。
【００５０】
（Ｃ）においてR［l-1，0］の次の第２下流ルータR［l，1］が選択され、（Ｄ）へ進む。（Ｄ）においてR［l，1］の第１上流ルータR［l-1，3］のID値（ID［l-1，3］）とR［l，j］の第１上流ルータR［l-1，2］のID値（ID［l-1，2］）が比較される。ID［l-1，3］＞ID［l-1，2］であるため、（Ｅ）へ進む。（Ｅ）において、R［l，0］とR［l，1］の間にR［l，j］を挿入することが決定され、ID値が算出される。
【００５１】
また、図６では、（Ｂ）→（Ｃ）→（Ｄ）→（Ｃ）→（Ｄ）→（Ｃ）→（Ｈ）で配置が終了する。まず（Ｂ）において第２上流ルータR［l-1，1］の第２下流ルータの存在有無がチェックされる。第２下流ルータが存在しているため、（Ｃ）へ進む。（Ｃ）において、R［l-1，1］の第２下流ルータR［l，3］が選択され、（Ｄ）へ進む。（Ｄ）において、R［l，3］の第１上流ルータR［l-1，2］のID値（ID［l-1，2］）とR［l，j］の第１上流ルータR［l-1，4］のID値（ID［l-1，4］）が比較される。ID［l-1，2］＜ID［l-1，4］であるため、（Ｃ）に戻る。
【００５２】
（Ｃ）においてR［l-1，1］の次の第２下流ルータR［l，4］が選択され、（Ｄ）へ進む。（Ｄ）においてR［l，4］の第１上流ルータR［l-1，4］のID値（ID［l-1，4］）とR［l，j］の第１上流ルータR［l-1，4］のID値（ID［l-1，4］）が比較される。同一のID値であるため、（Ｃ）に戻る。（Ｃ）において、R［l-1，1］のID値最大の第２下流ルータR［l，4］まで（Ｄ）が実行されたので、（Ｈ）へ進む。（Ｈ）において、R［l，4］とR［l，5］の間にR［l，j］を挿入することが決定され、ID値が算出される。
【００５３】
また、図７では、（Ｂ）→（Ｆ）→（Ｇ）→（Ｈ）で配置が終了する。まず（Ｂ）において第２上流ルータR［l-1，3］の第２下流ルータの存在有無がチェックされる。第２下流ルータが存在しないため、（Ｆ）へ進む。（Ｆ）において、R［l-1，3］の左側のルータR［l-1，2］が選択され、（Ｇ）へ進む。（Ｇ）において、R［l-1，2］の第２下流ルータの中からID値が最大のルータR［l，6］が選択され、（Ｈ）へ進む。（Ｈ）において、R［l，6］とR［l，7］の間にR［l，j］を挿入することが決定され、ID値が算出される。
【００５４】
上述した追加工程を繰り返した例を図８に示す。l≧1以上の階層における任意のルータで、２種類のdisjointなマルチキャスト配信木が設定できていることが分かる。どのルータを起点にしてメインおよびバックアップのマルチキャスト配信経路を設定する場合でも、双方の配信経路が重ならないようにすることができる。
【００５５】
図９は、上述した下流ルータ配置手法の手順を示している。以下、上記の処理と対応させながら、図９に示される処理を説明する。まず、引数kに0を設定し、第２上流ルータの引数R［l-1，j’］に追加ルータR［l，j］の第２上流ルータを設定すると共に、第１上流ルータの引数R［l-1，j”］に追加ルータR［l，j］の第１上流ルータを設定する（ステップＳ９０１）。
【００５６】
続いて、R［l-1，j’］に第２下流ルータが存在するか否かを判定する（ステップＳ９０２）。このステップは（Ｂ）に対応する。第２下流ルータが存在する場合にはステップＳ９０３へ進み、存在しなかった場合にはステップＳ９０８へ進む。ステップＳ９０３においては、第２下流ルータの引数R［l，b(k)］にR［l-1，j’］の第２下流ルータを設定すると共に、第１上流ルータの引数R［l-1，{b(k)}”］にR［l，b(k)］の第１上流ルータを設定する。このステップは（Ｃ）に対応する。
【００５７】
続いて、ID［l-1，{b(k)}”］≦ID［l-1，j”］であるか否かを判定する（ステップＳ９０４）。このステップは（Ｄ）に対応する。ID［l-1，{b(k)}”］≦ID［l-1，j”］であった場合にはステップＳ９０６へ進み、ID［l-1，{b(k)}”］＞ID［l-1，j”］であった場合にはステップＳ９０５へ進む。ステップＳ９０５においては、ID［l，b(k)-1］＜ID［l，j］＜ID［l，b(k)］を満たすID［l，j］を付与して処理を終了する。このステップは（Ｅ）に対応する。
【００５８】
また、ステップＳ９０６においては、R［l-1，j’］の第２下流ルータのうち、ID値が最大のルータまでID値の比較を行ったか否かを判定する。このステップは（Ｃ）に対応する。ID値が最大のルータまでID値の比較を行っていない場合には、次の第２下流ルータの処理を行うためkの値を１増加し（ステップＳ９０７）、ステップＳ９０３に戻る。また、ID値が最大のルータまでID値の比較を行った場合には、ID値最大の第２下流ルータの引数R［l，b(m)］の設定を行い（ステップＳ９１０）、ID［l，b(m)］＜ID［l，j］＜ID［l，b(m)+1］を満たすID［l，j］を付与して処理を終了する（ステップＳ９１１）。ステップＳ９１０〜Ｓ９１１は（Ｈ）に対応する。
【００５９】
一方、ステップＳ９０８においては、第２上流ルータR［l-1，j’］に左側のルータが存在するか否かを判定する。このステップは（Ｆ）に対応する。左側のルータが存在しない、すなわちR［l-1，j’］が階層l-1の先頭のルータである場合、R［l，j］を階層lの先頭ルータとし、適切なID［l，0］を付与して処理を終了する（ステップＳ９１２）。このステップは（Ｆ）に対応する。また、左側のルータが存在した場合、R［l-1，j’］に第２下流ルータが存在するか否かを判定する（ステップＳ９０９）。第２下流ルータが存在した場合にはステップＳ９１０へ進み、第２下流ルータが存在しなかった場合には、左側のルータについてステップＳ９０８の処理を再度行う。
【００６０】
上述したように、本実施形態の別上流ルータ選択手法では、配信サーバまたはバックアップサーバに最も近いルータを除く任意のルータにおいて、２つの上流ルータと接続する各物理リンクに対してそれぞれ２つずつサブネットが設定されると共に、各サブネットがメインマルチキャスト用およびバックアップマルチキャスト用に適切にグループ化され、各サブネットのネットワークアドレスが、所定の関係を満たすように設定される。これによって、２つのマルチキャストソースに対して等コストとなる２つの上流ルータ候補が存在する場合に、各々のマルチキャストソースへ向かう経路を分岐することができる。
【００６１】
また、本実施形態の下流ルータ配置手法では、階層構造を有する複数のルータの論理的な位置関係を示す初期NWトポロジ情報（ネットワークトポロジ情報）と、追加ルータと接続される上流ルータと追加ルータの論理的な位置関係を示す追加ルータ接続情報と、複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値（ID値）とに基づいて、追加ルータの論理的な位置を算出することによって、全てのルータにおいて、disjointなマルチキャスト配信経路の確立が保証される。
【００６２】
よって、本実施形態によれば、別上流ルータ選択手法および下流ルータ配置手法を組み合わせることによって、disjointなマルチキャストツリーを動的に構築することができる。したがって、ネットワーク管理者の意思により、マルチキャストソースあるいはグループ単位で、２つのdisjointな配信経路に分離してマルチキャスト配信を行うことが可能となる。
【００６３】
また、既存ルータの持つOSPF機能、PIM-SM機能のみを用いて、disjointなマルチキャスト配信経路を確保することができる。静的にマルチキャスト配信経路を固定するのではなく、従来と同様、配信経路はOSPF/PIM-SMにより動的に決定されるため、ネットワーク障害時にはOSPF/PIM-SMによる配信経路切り替えが機能する。
【００６４】
以上、図面を参照して本発明の実施形態について詳述してきたが、具体的な構成はこれらの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。例えば、別上流ルータ選択手法において、経路を分岐するためにはNA1＜NB1，NA2＞NB2としてもよく、その場合にはネットワークトポロジ上でメインマルチキャストソースとバックアップマルチキャストソースの位置が逆となる。
【００６５】
また、上述した実施形態によるルータ位置算出装置は、その動作および機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行させることにより実現してもよい。
【００６６】
ここで、「コンピュータ」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００６７】
また、上述したプログラムは、このプログラムを記憶装置等に格納したコンピュータから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上述したプログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータに既に記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【符号の説明】
【００６８】
１・・・記憶部、２・・・演算部、２１・・・ルータ論理位置計算部、２２・・・ルータID計算部、２３・・・VLAN ID・IPアドレス/プレフィックス生成部、２４・・・NWトポロジ出力表示部、１０１・・・放送配信サーバ、１０２，１０９・・・Ｌ２スイッチ、１０３・・・バックアップサーバ、１０４ａ，１０４ｂ，１０５ａ，１０５ｂ，１０６ａ，１０６ｂ，１０７・・・ルータ、１０８・・・通信制御装置、１１０・・・クライアント端末
【特許請求の範囲】
【請求項１】
第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、
前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、
前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されており、
前記第１の配信サーバおよび前記第２の配信サーバに最も近いルータを除く任意のルータが追加された際の論理的な追加位置は、
階層構造を有する前記複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、
新たに追加される追加ルータと接続される、前記第１の配信サーバおよび前記第２の配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、
前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、
に基づいて算出されたことを特徴とする通信システム。
【請求項２】
第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されている通信システムに対して新たに追加ルータを追加する際の論理的な位置を算出するルータ位置算出装置であって、
前記配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、
新たに追加される追加ルータと接続される、前記配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、
前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、
を記憶する記憶部と、
前記ネットワークトポロジ情報、前記追加ルータ接続情報、および前記識別値に基づいて前記追加ルータの論理的な位置を算出する位置算出部と、
を有することを特徴とするルータ位置算出装置。
【請求項３】
前記位置算出部は、前記追加ルータ接続情報に基づいて、前記追加ルータと接続される前記第１の上流ルータおよび前記第２の上流ルータを選択し、前記ネットワークトポロジ情報に基づいて、当該選択した第２の上流ルータの下流ルータを選択すると共に当該選択した下流ルータの前記第１の上流ルータを選択し、当該選択した下流ルータの前記第１の上流ルータの識別値と、前記追加ルータと接続される前記第１の上流ルータの識別値とを比較した結果に基づいて前記追加ルータの論理的な位置を算出することを特徴とする請求項２に記載のルータ位置算出装置。
【請求項４】
前記位置算出部は、前記追加ルータ接続情報に基づいて、前記追加ルータと接続される前記第２の上流ルータを選択し、前記ネットワークトポロジ情報に基づいて、当該選択した第２の上流ルータと同一階層であって隣りのルータを選択すると共に当該選択した隣りのルータの下流ルータを選択し、当該選択した下流ルータの識別値に基づいて前記追加ルータの論理的な位置を算出することを特徴とする請求項２に記載のルータ位置算出装置。
【請求項５】
前記位置算出部は、階層lにおける前記配置方向の位置がj番目であって、当該位置に対応する前記識別値R［l，j］を有する前記追加ルータと接続される前記第１の上流ルータ、前記第２の上流ルータの前記識別値をそれぞれR［l-1，j”］、R［l-1，j’］とし、前記追加ルータと同一階層のi番目のルータの前記第１の上流ルータ、前記第２の上流ルータの前記識別値をそれぞれR［l-1，i”］、R［l-1，i’］とした場合に、（i’＜j’）または（i’＝j’かつi”≦j”）であればi＜jが成り立つように、かつ、（i’＞j’）または（i’＝j’かつi”＞j”）であればi＞jが成り立つようにjを決定することを特徴とする請求項２〜請求項４のいずれか一項に記載のルータ位置算出装置。
【請求項６】
前記位置算出部によって算出された前記追加ルータの論理的な位置に基づいて前記追加ルータの前記識別値を算出する識別値算出部をさらに有することを特徴とする請求項２〜請求項５のいずれか一項に記載のルータ位置算出装置。
【請求項７】
第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されている通信システムに対して新たに追加ルータを追加する際の論理的な位置を算出する処理をコンピュータに実行させるためのルータ位置算出プログラムであって、
前記配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、
新たに追加される追加ルータと接続される、前記配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、
前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、
を記憶する記憶部と、
前記ネットワークトポロジ情報、前記追加ルータ接続情報、および前記識別値に基づいて前記追加ルータの論理的な位置を算出する位置算出部と、
としてコンピュータを機能させるためのルータ位置算出プログラム。
【請求項１】
第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、
前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、
前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されており、
前記第１の配信サーバおよび前記第２の配信サーバに最も近いルータを除く任意のルータが追加された際の論理的な追加位置は、
階層構造を有する前記複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、
新たに追加される追加ルータと接続される、前記第１の配信サーバおよび前記第２の配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、
前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、
に基づいて算出されたことを特徴とする通信システム。
【請求項２】
第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されている通信システムに対して新たに追加ルータを追加する際の論理的な位置を算出するルータ位置算出装置であって、
前記配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、
新たに追加される追加ルータと接続される、前記配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、
前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、
を記憶する記憶部と、
前記ネットワークトポロジ情報、前記追加ルータ接続情報、および前記識別値に基づいて前記追加ルータの論理的な位置を算出する位置算出部と、
を有することを特徴とするルータ位置算出装置。
【請求項３】
前記位置算出部は、前記追加ルータ接続情報に基づいて、前記追加ルータと接続される前記第１の上流ルータおよび前記第２の上流ルータを選択し、前記ネットワークトポロジ情報に基づいて、当該選択した第２の上流ルータの下流ルータを選択すると共に当該選択した下流ルータの前記第１の上流ルータを選択し、当該選択した下流ルータの前記第１の上流ルータの識別値と、前記追加ルータと接続される前記第１の上流ルータの識別値とを比較した結果に基づいて前記追加ルータの論理的な位置を算出することを特徴とする請求項２に記載のルータ位置算出装置。
【請求項４】
前記位置算出部は、前記追加ルータ接続情報に基づいて、前記追加ルータと接続される前記第２の上流ルータを選択し、前記ネットワークトポロジ情報に基づいて、当該選択した第２の上流ルータと同一階層であって隣りのルータを選択すると共に当該選択した隣りのルータの下流ルータを選択し、当該選択した下流ルータの識別値に基づいて前記追加ルータの論理的な位置を算出することを特徴とする請求項２に記載のルータ位置算出装置。
【請求項５】
前記位置算出部は、階層lにおける前記配置方向の位置がj番目であって、当該位置に対応する前記識別値R［l，j］を有する前記追加ルータと接続される前記第１の上流ルータ、前記第２の上流ルータの前記識別値をそれぞれR［l-1，j”］、R［l-1，j’］とし、前記追加ルータと同一階層のi番目のルータの前記第１の上流ルータ、前記第２の上流ルータの前記識別値をそれぞれR［l-1，i”］、R［l-1，i’］とした場合に、（i’＜j’）または（i’＝j’かつi”≦j”）であればi＜jが成り立つように、かつ、（i’＞j’）または（i’＝j’かつi”＞j”）であればi＞jが成り立つようにjを決定することを特徴とする請求項２〜請求項４のいずれか一項に記載のルータ位置算出装置。
【請求項６】
前記位置算出部によって算出された前記追加ルータの論理的な位置に基づいて前記追加ルータの前記識別値を算出する識別値算出部をさらに有することを特徴とする請求項２〜請求項５のいずれか一項に記載のルータ位置算出装置。
【請求項７】
第１の配信サーバおよび第２の配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータを備えた通信システムであって、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第１の配信サーバによって送信されるマルチキャストパケットが、前記第１の配信サーバ側に設けられた第１の上流ルータから転送されるように前記第１の配信サーバのIPアドレスが決定されており、前記複数のルータを構成する各ルータのハッシュ処理によって、前記第２の配信サーバによって送信されるマルチキャストパケットが、前記第２の配信サーバ側に設けられた第２の上流ルータから転送されるように前記第２の配信サーバのIPアドレスが決定されている通信システムに対して新たに追加ルータを追加する際の論理的な位置を算出する処理をコンピュータに実行させるためのルータ位置算出プログラムであって、
前記配信サーバによって送信されるマルチキャストパケットを転送する、階層構造を有する複数のルータの論理的な位置関係を示すネットワークトポロジ情報と、
新たに追加される追加ルータと接続される、前記配信サーバ側に設けられた上流ルータと前記追加ルータの論理的な位置関係を示す追加ルータ接続情報と、
前記複数のルータの各々に対して、各ルータの論理的な位置に対応して付与された識別値であって、同一階層内でルータの配置方向に沿って値が増加するように付与された識別値と、
を記憶する記憶部と、
前記ネットワークトポロジ情報、前記追加ルータ接続情報、および前記識別値に基づいて前記追加ルータの論理的な位置を算出する位置算出部と、
としてコンピュータを機能させるためのルータ位置算出プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１０−１８７４１５（Ｐ２０１０−１８７４１５Ａ）
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願番号】特願２０１０−１２４９１２（Ｐ２０１０−１２４９１２）
【出願日】平成２２年５月３１日（２０１０．５．３１）
【分割の表示】特願２００５−２３５６９９（Ｐ２００５−２３５６９９）の分割
【原出願日】平成１７年８月１６日（２００５．８．１６）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願日】平成２２年５月３１日（２０１０．５．３１）
【分割の表示】特願２００５−２３５６９９（Ｐ２００５−２３５６９９）の分割
【原出願日】平成１７年８月１６日（２００５．８．１６）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]