(57)【要約】  数理計画法を用いてマルチキャストツリーを設計する新規なマルチキャストツリー設計装置を提供する。  ノードとノード間を接続するリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーを設計するマルチキャストツリー設計装置であって、問題作成手段と問題解決手段とを有し、問題作成手段は、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式を作成する複数経路制約作成手段と、経路を全て重ね合わせてマルチキャストツリーを構成するための制約式を作成するツリー制約作成手段と、複数の経路を重ね合わせたときに経路同士が合流するトポロジーになることを許さないための制約式を作成する合流制約作成手段と、マルチキャストツリーを構成するリンクまたはノードに関する評価指標を最小化するための目的関数を作成する目的関数作成手段とを有し、問題解決手段は、問題作成手段により作成された制約式および目的関数から構成される数理計画問題を解くことでマルチキャストツリーを構成するリンクの集合を決定する。
2008133230.tif 000002
【特許請求の範囲】
【請求項１】
ノードと前記ノード間を接続するリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーを設計するマルチキャストツリー設計装置であって、問題作成手段と問題解決手段とを有し、
前記問題作成手段は、
配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式を作成する複数経路制約作成手段と、
前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式を作成するツリー制約作成手段と、
前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式を作成する合流制約作成手段と、
マルチキャストツリーを構成する前記リンクまたは前記ノードに関する評価指標を最小化するための目的関数を作成する目的関数作成手段とを有し、
前記問題解決手段は、前記問題作成手段により作成された前記制約式および前記目的関数から構成される数理計画問題を解くことで前記マルチキャストツリーを構成するリンクの集合を決定することを特徴とするマルチキャストツリー設計装置。
【請求項２】
配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式は、配信元ノードを始点とし配信先ノードを終点とする経路が通るリンクが、配信元ノードに直接つながるリンクの中に１本だけあるという制約式と、配信元ノードを始点とし配信先ノードを終点とする経路が通るリンクが、配信先ノードに直接つながるリンクの中に１本だけあり、配信先ノードを始点とするリンクの中には１本もないという制約式と、各配信先ノードに関して、経路が或るノードに入力するときは必ず当該ノードを始点とするリンクが１本存在し、逆に経路が或るノードに入力しないときは必ず当該ノードを始点とするリンクが存在しないという制約式とで構成され、
前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式は、各経路を重ね合わせたときにノードiからノードjへのリンクを通る経路が存在するかどうかを示す0-1変数xi,jは、配信元ノードを始点とし配信先ノードを終点とする経路がノードiからノードjへのリンクを通る総数が、Zxi,j (Zは配信先ノード数)以下かつxi,j以上を満足するように作成しなければならないという制約式で構成され、
前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式は、各ノードiにおいて、ノードiを終点とする全てのリンク集合のうち、多くとも１本のマルチキャストツリーのリンクが存在するという制約式で構成されることを特徴とする請求項１記載のマルチキャストツリー設計装置。
【請求項３】
前記目的関数は、配信元ノードを始点とし複数の配信先ノードを終点とする各経路の遅延の総和、マルチキャストツリーを構成するリンク数の総和、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路上の各リンクの帯域の逆数の最大値のいずれかの関数を含むことを特徴とする請求項１記載のマルチキャストツリー設計装置。
【請求項４】
前記問題作成手段は、前記経路はすでに通過した前記ノードへ折り返して通過することを許さないための制約式を作成する折り返し制約作成手段をさらに有することを特徴とする請求項１記載のマルチキャストツリー設計装置。
【請求項５】
前記経路はすでに通過した前記ノードへ折り返して通過することを許さないための制約式は、マルチキャストツリーを構成する各リンクにおいて、ノードiからノードjに至るリンクと、ノードjからノードiへ至るリンクは同時に存在し得ないという制約式で構成されることを特徴とする請求項４記載のマルチキャストツリー設計装置。
【請求項６】
前記問題作成手段は、１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式を作成する分岐実行制約作成手段をさらに有することを特徴とする請求項１記載のマルチキャストツリー設計装置。
【請求項７】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式は、ノード集合Iに含まれるノードの全てにおいてマルチキャストツリーが必ず分岐するという制約式で構成されることを特徴とする請求項６記載のマルチキャストツリー設計装置。
【請求項８】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式は、ノード集合Iに含まれるノードの少なくとも１つのノードにおいてマルチキャストツリーが必ず分岐するという制約式で構成されることを特徴とする請求項６記載のマルチキャストツリー設計装置。
【請求項９】
前記問題作成手段は、１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を許さないための制約式を作成する分岐禁止制約作成手段をさらに有することを特徴とする請求項１記載のマルチキャストツリー設計装置。
【請求項１０】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を許さないための制約式は、ノード集合Iに含まれる全てのノードiにおいて、ノードiへ入力するリンクがあるとき、必ずノードiから出力するリンクは１本であるという制約式で構成されることを特徴とする請求項９記載のマルチキャストツリー設計装置。
【請求項１１】
ノードと前記ノード間を接続するリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーを設計するマルチキャストツリー設計方法であって、
配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式、前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式、前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式、および、マルチキャストツリーを構成する前記リンクまたは前記ノードに関する評価指標を最小化するための目的関数を作成する問題作成ステップと、
前記問題作成ステップにより作成された前記制約式および前記目的関数から構成される数理計画問題を解くことで前記マルチキャストツリーを構成するリンクの集合を決定する問題解決ステップとを含むことを特徴とするマルチキャストツリー設計方法。
【請求項１２】
配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式は、配信元ノードを始点とし配信先ノードを終点とする経路が通るリンクが、配信元ノードに直接つながるリンクの中に１本だけあるという制約式と、配信元ノードを始点とし配信先ノードを終点とする経路が通るリンクが、配信先ノードに直接つながるリンクの中に１本だけあり、配信先ノードを始点とするリンクの中には１本もないという制約式と、各配信先ノードに関して、経路が或るノードに入力するときは必ず当該ノードを始点とするリンクが１本存在し、逆に経路が或るノードに入力しないときは必ず当該ノードを始点とするリンクが存在しないという制約式とで構成され、
前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式は、各経路を重ね合わせたときにノードiからノードjへのリンクを通る経路が存在するかどうかを示す0-1変数xi,jは、配信元ノードを始点とし配信先ノードを終点とする経路がノードiからノードjへのリンクを通る総数が、Zxi,j (Zは配信先ノード数)以下かつxi,j以上を満足するように作成しなければならないという制約式で構成され、
前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式は、各ノードiにおいて、ノードiを終点とする全てのリンク集合のうち、多くとも１本のマルチキャストツリーのリンクが存在するという制約式で構成されることを特徴とする請求項１１記載のマルチキャストツリー設計方法。
【請求項１３】
前記目的関数は、配信元ノードを始点とし複数の配信先ノードを終点とする各経路の遅延の総和、マルチキャストツリーを構成するリンク数の総和、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路上の各リンクの帯域の逆数の最大値のいずれかの関数を含むことを特徴とする請求項１１記載のマルチキャストツリー設計方法。
【請求項１４】
前記問題作成ステップは、前記経路はすでに通過した前記ノードへ折り返して通過することを許さないための制約式をさらに作成することを特徴とする請求項１１記載のマルチキャストツリー設計方法。
【請求項１５】
前記経路はすでに通過した前記ノードへ折り返して通過することを許さないための制約式は、マルチキャストツリーを構成する各リンクにおいて、ノードiからノードjに至るリンクと、ノードjからノードiへ至るリンクは同時に存在し得ないという制約式で構成されることを特徴とする請求項１４記載のマルチキャストツリー設計方法。
【請求項１６】
前記問題作成ステップは、１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式をさらに作成することを特徴とする請求項１１記載のマルチキャストツリー設計方法。
【請求項１７】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式は、ノード集合Iに含まれるノードの全てにおいてマルチキャストツリーが必ず分岐するという制約式で構成されることを特徴とする請求項１６記載のマルチキャストツリー設計方法。
【請求項１８】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式は、ノード集合Iに含まれるノードの少なくとも１つのノードにおいてマルチキャストツリーが必ず分岐するという制約式で構成されることを特徴とする請求項１６記載のマルチキャストツリー設計方法。
【請求項１９】
前記問題作成ステップは、１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を許さないための制約式をさらに作成することを特徴とする請求項１１記載のマルチキャストツリー設計方法。
【請求項２０】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を許さないための制約式は、ノード集合Iに含まれる全てのノードiにおいて、ノードiへ入力するリンクがあるとき、必ずノードiから出力するリンクは１本であるという制約式で構成されることを特徴とする請求項１９記載のマルチキャストツリー設計方法。
【請求項２１】
ノードと前記ノード間を接続するリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーをコンピュータによって設計するためのプログラムであって、前記コンピュータに、
配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式、前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式、前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式、および、マルチキャストツリーを構成する前記リンクまたは前記ノードに関する評価指標を最小化するための目的関数を作成する問題作成ステップと、
前記問題作成ステップにより作成された前記制約式および前記目的関数から構成される数理計画問題を解くことで前記マルチキャストツリーを構成するリンクの集合を決定する問題解決ステップとを実行させるためのプログラム。
【請求項２２】
配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式は、配信元ノードを始点とし配信先ノードを終点とする経路が通るリンクが、配信元ノードに直接つながるリンクの中に１本だけあるという制約式と、配信元ノードを始点とし配信先ノードを終点とする経路が通るリンクが、配信先ノードに直接つながるリンクの中に１本だけあり、配信先ノードを始点とするリンクの中には１本もないという制約式と、各配信先ノードに関して、経路が或るノードに入力するときは必ず当該ノードを始点とするリンクが１本存在し、逆に経路が或るノードに入力しないときは必ず当該ノードを始点とするリンクが存在しないという制約式とで構成され、
前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式は、各経路を重ね合わせたときにノードiからノードjへのリンクを通る経路が存在するかどうかを示す0-1変数xi,jは、配信元ノードを始点とし配信先ノードを終点とする経路がノードiからノードjへのリンクを通る総数が、Zxi,j (Zは配信元ノード数)以下かつxi,j以上を満足するように作成しなければならないという制約式で構成され、
前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式は、各ノードiにおいて、ノードiを終点とする全てのリンク集合のうち、多くとも１本のマルチキャストツリーのリンクが存在するという制約式で構成されることを特徴とする請求項２１記載のプログラム。
【請求項２３】
前記目的関数は、配信元ノードを始点とし複数の配信先ノードを終点とする各経路の遅延の総和、マルチキャストツリーを構成するリンク数の総和、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路上の各リンクの帯域の逆数の最大値のいずれかの関数を含むことを特徴とする請求項２１記載のプログラム。
【請求項２４】
前記問題作成ステップは、前記経路はすでに通過した前記ノードへ折り返して通過することを許さないための制約式をさらに作成することを特徴とする請求項２１記載のプログラム。
【請求項２５】
前記経路はすでに通過した前記ノードへ折り返して通過することを許さないための制約式は、マルチキャストツリーを構成する各リンクにおいて、ノードiからノードjに至るリンクと、ノードjからノードiへ至るリンクは同時に存在し得ないという制約式で構成されることを特徴とする請求項２４記載のプログラム。
【請求項２６】
前記問題作成ステップは、１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式をさらに作成することを特徴とする請求項２１記載のプログラム。
【請求項２７】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式は、ノード集合Iに含まれるノードの全てにおいてマルチキャストツリーが必ず分岐するという制約式で構成されることを特徴とする請求項２６記載のプログラム。
【請求項２８】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を必ず行わせるための制約式は、ノード集合Iに含まれるノードの少なくとも１つのノードにおいてマルチキャストツリーが必ず分岐するという制約式で構成されることを特徴とする請求項２６記載のプログラム。
【請求項２９】
前記問題作成ステップは、１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を許さないための制約式をさらに作成することを特徴とする請求項２１記載のプログラム。
【請求項３０】
１つ以上の前記ノードにおいて前記マルチキャストツリーの分岐を許さないための制約式は、ノード集合Iに含まれる全てのノードiにおいて、ノードiへ入力するリンクがあるとき、必ずノードiから出力するリンクは１本であるという制約式で構成されることを特徴とする請求項２９記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノードとリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーを設計する装置と方法に関する。
【背景技術】
【０００２】
従来のこの種の装置として、ダイクストラ法を用いてマルチキャストツリーを設計するマルチキャストツリー設計装置がある。ダイクストラ法は、定義されたコストが最小になるルートを選ぶアルゴリズムである。従って、配信元ノードから複数の配信先ノードまでのリンクコストが最小になるようなマルチキャストツリーを設計するのに向いていた。【０００３】
また、ダイクストラ法を改良して、マルチキャスト転送機能を有するノードとユニキャスト転送機能しか有しないノードとが混在したネットワークにおいて、配信元ノードから複数の配信先ノードまでのリンクコストが小さくなるようにしつつ、ユニキャスト機能しか有しないノードでは分岐が発生しないようなマルチキャストツリーを設計する装置が提案されている（例えば特許文献１参照）。【０００４】
他方、数理計画法を用いることにより、通信ネットワークにおける最適なパスの設計を行う方法が知られている。例えば特許文献２に記載された設計方法では、経路制御装置が、任意のネットワーク形態におけるパス割り当て方法を、線形計画の枠組みに沿って展開することにより、様々な線形計画の解法を適用して、パス配置およびフロー帯域ならびに目的関数値を求め、これらを比較評価することができるようにしている。また、例えば特許文献３には、数理計画法を用いて、ノード間を接続するリンクから構成されるネットワークを設計する方法が示されている。【０００５】
【特許文献１】特開２００７−６２２８号公報
【特許文献２】特許第３７８２０６３号公報
【特許文献３】特許第３１４１８０８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ダイクストラ法をベースとするマルチキャストツリー設計装置は、その最適化目的に応じた複雑なアルゴリズムを設計する必要がある。例えば、特許文献１では、ユニキャスト機能しか有しないノードで分岐が発生しないようにするために、ベースとなるダイクストラ法を改良している。このように、ダイクストラ法をベースとする限り、最適化目的がｎ種類あれば、ｎ種類のアルゴリズムを設計する必要がある。このため、一般的に開発コストが大きくなり、また設計したアルゴリズムの検証にも多大な時間と労力を必要とする。【０００７】
これに対して数理計画法によるネットワーク設計は、作成する数理計画問題が最適化目的毎に相違するものの、数理計画問題さえ作成することができれば、数理計画問題の解法自体は既存の解法アルゴリズムをそのまま利用することができるため、開発コストや検証時間の大幅な低減が可能になる。しかしながら、マルチキャストツリーの設計に対してはどのような数理計画問題が有効であるかは自明ではなく、マルチキャストツリーの設計に数理計画問題を適用した事例は見当たらないのが実情である。【０００８】
本発明の目的は、数理計画法を用いてマルチキャストツリーを設計する新規なマルチキャストツリー設計装置および方法を提供することにある。
【課題を解決するための手段】
【０００９】
本発明によれば、ノードと前記ノード間を接続するリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーを設計するマルチキャストツリー設計装置であって、問題作成手段と問題解決手段とを有し、前記問題作成手段は、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式を作成する複数経路制約作成手段と、前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式を作成するツリー制約作成手段と、前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式を作成する合流制約作成手段と、マルチキャストツリーを構成する前記リンクまたは前記ノードに関する評価指標を最小化するための目的関数を作成する目的関数作成手段とを有し、前記問題解決手段は、前記問題作成手段により作成された前記制約式および前記目的関数から構成される数理計画問題を解くことで前記マルチキャストツリーを構成するリンクの集合を決定することを特徴とするマルチキャストツリー設計装置が提供される。【００１０】
また、本発明によれば、ノードと前記ノード間を接続するリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーを設計するマルチキャストツリー設計方法であって、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式、前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式、前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式、および、マルチキャストツリーを構成する前記リンクまたは前記ノードに関する評価指標を最小化するための目的関数を作成する問題作成ステップと、前記問題作成ステップにより作成された前記制約式および前記目的関数から構成される数理計画問題を解くことで前記マルチキャストツリーを構成するリンクの集合を決定する問題解決ステップとを含むことを特徴とするマルチキャストツリー設計方法が提供される。【００１１】
更に、本発明によれば、ノードと前記ノード間を接続するリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーをコンピュータによって設計するためのプログラムであって、前記コンピュータに、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式、前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式、前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式、および、マルチキャストツリーを構成する前記リンクまたは前記ノードに関する評価指標を最小化するための目的関数を作成する問題作成ステップと、前記問題作成ステップにより作成された前記制約式および前記目的関数から構成される数理計画問題を解くことで前記マルチキャストツリーを構成するリンクの集合を決定する問題解決ステップとを実行させるためのプログラムが提供される。
【発明の効果】
【００１２】
本発明によれば、マルチキャストツリーを数理計画法を用いて設計するため、ダイクストラ法をベースとするマルチキャストツリー設計装置のように最適化目的毎に複雑なアルゴリズムを開発する必要がなくなる。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１の実施の形態にかかるマルチキャストツリー設計装置のブロック図である。
【図２】本発明の第１の実施の形態にかかるマルチキャストツリー設計装置の処理例を示すフローチャートである。
【図３】本発明の第１の実施の形態にかかるマルチキャストツリー設計装置に入力される各種パラメータの説明図である。
【図４】本発明の第２の実施の形態にかかるマルチキャストツリー設計装置のブロック図である。
【図５】本発明の第２の実施の形態にかかるマルチキャストツリー設計装置の処理例を示すフローチャートである。
【図６】本発明のその他の実施の形態の構成図である。
【符号の説明】
【００１４】
１００、２００、３００  マルチキャストツリー設計装置
１１０  データ処理装置
１２０  記憶装置
１２１  各種パラメータ
１２２  数理計画問題
１２３  解
１３０  入力装置
１４０  出力装置
１５０  入力手段
１６０、２６０  問題作成手段
１６１  複数経路制約作成手段
１６２  ツリー制約作成手段
１６３  合流制約作成手段
１６４  目的関数作成手段
１７０  問題解決手段
１８０  出力手段
２６１  折り返し制約作成手段
２６２  分岐実行制約作成手段
２６３  分岐禁止制約作成手段
３０１  経路設定機構
３０２  ネットワーク
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明を実施するための最良の形態について詳細に説明する。【００１６】
『第１の実施の形態』
図１を参照すると、本発明の第１の実施の形態にかかるマルチキャストツリー設計装置１００は、データ処理装置１１０と記憶装置１２０と入力装置１３０と出力装置１４０とで構成されている。【００１７】
入力装置１３０は、マルチキャストツリーの設計に必要な各種のパラメータを入力するための装置であり、例えばキーボードやファイル装置、データ受信装置などで構成される。【００１８】
出力装置１４０は、設計されたマルチキャストツリーを出力するための装置であり、例えばディスプレイやファイル装置、データ送信装置などで構成される。【００１９】
記憶装置１２０は、入力装置１３０から入力された各種のパラメータや処理過程のデータを記憶する装置であり、例えば半導体メモリや磁気ディスクなどで構成される。【００２０】
データ処理装置１１０は、入力装置１３０から入力された各種のパラメータに基づいて数理計画問題を作成し、それを解法することによって、マルチキャストツリーを導出する装置である。本実施の形態の場合、データ処理装置１１０は、入力手段１５０、問題作成手段１６０、問題解決手段１７０および出力手段１８０を有している。また問題作成手段１６０は、複数経路制約作成手段１６１、ツリー制約作成手段１６２、合流制約作成手段１６３および目的関数作成手段１６４を有する。これらは概ね以下のような機能を有する。【００２１】
入力手段１５０は、入力装置１３０からマルチキャストツリーの設計に必要な各種のパラメータを入力し、記憶装置１２０に各種パラメータ１２１として記憶する。【００２２】
問題作成手段１６０は、記憶装置１２０から各種パラメータ１２１を読み出し、マルチキャストツリー設計のための数理計画問題を作成し、記憶装置１２０に数理計画問題１２２として記憶する。具体的には、複数経路制約作成手段１６１により、配信元ノードを始点とし、複数の配信先ノードを終点とする複数の経路を構成するための制約式を作成し、ツリー制約作成手段１６２により、前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式を作成し、合流制約作成手段１６３により、前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式を作成し、目的関数作成手段１６４により、マルチキャストツリーを構成するリンクまたはノードに関する評価指標を最小化するための目的関数を作成する。この問題作成手段１６０で作成された制約式および目的関数が、数理計画問題を構成する。【００２３】
問題解決手段１７０は、記憶装置１２０から制約式および目的関数により構成される数理計画問題１２２を読み出し、それを解くことにより、マルチキャストツリーを構成するリンクの集合を決定し、記憶装置１２０に解１２３として記憶する。【００２４】
出力手段１８０は、記憶装置１２０から解１２３を読み出し、そのまま出力するか、あるいは所定のデータフォーマットに変換して出力装置１４０から出力する。【００２５】
次に、図１のブロック図および図２のフローチャートを参照して、本実施の形態の動作を説明する。【００２６】
まず、データ処理装置１１０の入力手段１５０は、マルチキャストツリーの設計に必要な各種のパラメータを入力装置１３０から入力し、記憶装置１２０に各種パラメータ１２１として記憶する（Ｓ１０１）。図３を参照すると、各種パラメータ１２１は、トポロジー情報１２１１、配信元ノード情報１２１２、配信先ノード情報１２１３およびその他の情報１２１４から構成される。【００２７】
トポロジー情報１２１１は、マルチキャストツリーの構築対象となるネットワークのトポロジーを定める情報であり、具体的には、ノードとリンクの接続を特定する。ネットワークに含まれるノードおよびリンクには、一意なノード番号およびリンク番号が付与されており、これらの番号を用いてノードとリンクとの接続関係が定義されている。【００２８】
配信元ノード情報１２１２は配信元ノードとなるノードのノード番号であり、配信先ノード情報１２１３は配信先ノードとなるノードのノード番号である。【００２９】
その他の情報１２１４は、例えば各リンクの遅延量や帯域などである。その他の情報１２１４として、どのような情報が必要になるかは、一般に制約式や目的関数の種類などによって相違する。【００３０】
次に、問題作成手段１６０は、記憶装置１２１から各種パラメータ１２１を読み出し、マルチキャストツリーを得るための数理計画法の問題を作成し、記憶装置１２０に記憶する（Ｓ１０２〜Ｓ１０５）。具体的には、以下のような手順で数理計画問題を作成する。【００３１】
まず、複数経路制約作成手段１６１は、配信元ノードsを始点とし、複数の配信先ノードzを終点とする複数の経路を構成するための制約式を作成する（Ｓ１０２）。このような制約式を作成する理由は、配信元ノードsから各配信先ノードzまでの各経路が確実に存在することを保証するためである。【００３２】
具体的には、複数経路制約作成手段１６１は、配信元ノードsについて式１に示す制約式を作成し、複数の配信先ノードzについて式２に示す制約式を作成し、通過ノードiについて式３に示す制約式を作成する。【００３３】
【数１】
2008133230.tif 000003
・・・（式１）
【数２】
2008133230.tif 000004
・・・（式２）
始点s,終点z以外のノードiについて、
【数３】
2008133230.tif 000005
・・・（式３）【００３４】
ここで、xzi,jは、配信元ノードsを始点とし、或る配信先ノードzを終点とする経路が、ノードiからノードjへのリンクを通るかどうかを示す0-1変数であり、例えばxzi,j=1のとき、ノードiからノードjへのリンクを通り、xzi,j=0のときは通らないことを示す。また、Zは配信先ノードの集合、ei,jはノードiからノードjへのリンク、E-(i)はノードiを終点とする全てのリンク集合、E+(i)はノードiを始点とする全てのリンク集合をそれぞれ示す。【００３５】
式１は、配信元ノードsを始点とし、配信先ノードzを終点とする経路が通るリンクが、配信元ノードsに直接つながるリンクの中に１本だけあることを意味している。式２は、配信元ノードsを始点とし配信先ノードzを終点とする経路が通るリンクが、配信先ノードzに直接つながるリンクの中に１本だけあり（式１）、かつ、配信先ノードzを始点とするリンクの中には１本もない（式２）ことを意味している。式３は、各配信先ノードzに関して、経路が或るノードiに入力するとき、必ず当該ノードiを始点とするリンクが１本存在し、逆に経路がノードiに入力しないとき、必ず当該ノードiを始点とするリンクが存在しないことを意味している。【００３６】
次に、ツリー制約作成手段１６２は、配信元ノードsを始点とし複数の配信先ノードzを終点とする複数の経路を全て重ね合わせてマルチキャストツリーを構成するための制約式を作成する（Ｓ１０３）。このような制約式を作成する理由は、この制約式が無ければ、配信元ノードsを始点とし複数の配信先ノードzを終点とする複数の経路がそれぞれ独立した経路として解に含まれることになり、マルチキャストツリーのトポロジーにならないためである。【００３７】
具体的には、ツリー制約作成手段１６２は、ネットワークの各リンクについて式４に示す制約式を作成する。
【数４】
2008133230.tif 000006
・・・（式４）【００３８】
ここで、Eはネットワークの全てのリンクの集合、xi,jは、各経路を重ね合わせたときにノードiからノードjへのリンクを通る経路が存在するかどうかを示す0-1変数であり、例えばxi,j=1のとき、ノードiからノードjへのリンクを通る経路が存在し、xi,j=0のときは存在しないことを示す。zが右肩に付いているxzi,jと記号的に似ているが、意味は全く相違する。【００３９】
式４は、各経路を重ね合わせたときにノードiからノードjへのリンクを通る経路が存在するかどうかを示す変数xi,jは、配信元ノードsを始点とし配信先ノードzを終点とする経路がノードiからノードjへのリンクを通る総数が、Zxi,j以下かつxi,j以上を満足するように作成しなければならないことを意味する。この制約式により、配信元ノードsを始点とし配信先ノードzを終点とする経路が１本以上Z本以下、ノードiからノードjへのリンクを通るならば、xi,j=1となり、配信元ノードsを始点とし配信先ノードzを終点とする経路が１本もノードiからノードjへのリンクを通らないならば、xi,j=0となる。【００４０】
次に、合流制約作成手段１６３は、配信元ノードsを始点とし複数の配信先ノードzを終点とする複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式を作成する（Ｓ１０４）。このような制約式を作成する理由は、この制約式が無ければ、経路同士が合流するような経路も解に含まれることになり、そうなるとツリー構造にならないためである。【００４１】
具体的には、合流制約作成手段１６３は、各ノードiにおいて式５に示す制約式を作成する。【００４２】
【数５】
2008133230.tif 000007
・・・（式５）【００４３】
式５は、ノードiを終点とする全てのリンク集合のうち、多くとも１本のマルチキャストツリーのリンクが存在することを意味する。【００４４】
次に、目的関数作成手段１６４は、マルチキャストツリーを構成するリンクまたはノードに関する評価指標を最小化するための目的関数を作成する（Ｓ１０５）。作成する目的関数は、最適化目的によって相違する。以下、幾つかの最適化目的を例示し、それに応じた目的関数の例を示す。【００４５】
(1)最適化目的：配信元ノードから配信先ノードまでの遅延の総和の最小化
この場合、目的関数作成手段１６４は、各経路の遅延の総和を目的関数とする。具体的には、式６に示す目的関数の最小化を適用する。【００４６】
【数６】
2008133230.tif 000008
・・・（式６）【００４７】
ここで、di,jはノードiからノードjへのリンクの遅延量であり、各種パラメータ１２１中のその他の情報１２１４で与えられる。式６は、各経路の遅延の総和を意味する【００４８】
(2)最適化目的：通過ノード数の最小化
この場合、目的関数作成手段１６４は、マルチキャストツリーを構成するリンク数の総和を目的関数とする。具体的には、式７に示す目的関数の最小化を適用する。【００４９】
【数７】
2008133230.tif 000009
・・・（式７）【００５０】
式７は、マルチキャストツリーのリンクの総数を意味する。【００５１】
(3)最適化目的：各リンクの余剰帯域の最大化
余剰帯域の最大化は、各リンクの帯域の逆数をペナルティと定義し、そのペナルティの最大を最小化することに等しい。したがって、目的関数作成手段１６４は、配信元ノードsを始点とし複数の配信先ノードzを終点とする複数の経路上の各リンクの帯域の逆数の最大値を目的関数とする。具体的には、式８に示す目的関数の最小化を適用する。【００５２】
【数８】
2008133230.tif 000010
・・・（式８）【００５３】
ここで、biはリンクiにおける帯域を示す定数であり、各種パラメータ１２１中のその他の情報１２１４で与えられる。式８は、マルチキャストツリーを構成する各リンクの帯域の逆数の最大値を意味する。【００５４】
本発明で使用する目的関数は、以上の目的関数にのみ限定されず、それらを組み合わせたものでも良いし、目的関数同士の積など目的関数の関数になっていても良い。【００５５】
問題作成手段１６０は、ステップＳ１０２〜Ｓ１０４で作成した制約式およびステップＳ１０５で作成した目的関数を、数理計画問題１２２として記憶装置１２０に記憶する。なお、ステップＳ１０２〜Ｓ１０５は必ずしもフローチャートに示した順番で実行する必要はなく、任意の順番で良い。【００５６】
次に問題解決手段１７０の動作を説明する。問題解決手段１７０は、記憶装置１２０から制約式および目的関数により構成される数理計画問題１２２を読み出し、必要に応じて各種パラメータ１２１を参照して、数理計画問題１２２を解法する（Ｓ１０６）。数理計画問題の解法アルゴリズムとしては、シンプレックス法、射影変換法、内点法など従来より様々なものが提案されているので、その中から適切なものを選択して使用することができる。【００５７】
問題解決手段１７０によって解法された数理計画問題１２２の解１２３は、記憶装置１２０に記憶される。解１２３には、数理計画問題１２２を解いて得られた変数xi,jの値が含まれる。【００５８】
次に出力手段１８０は、記憶装置１２０から解１２３を読み出し、設計結果のマルチキャストツリーとして出力装置１４０から出力する（Ｓ１０７）。解１２３に含まれる変数xi,jは、対応するリンクがマルチキャストツリーに含まれるかどうかを表しているので、出力手段１８０は、値1の変数xi,jの集合によって規定されるマルチキャストツリーを結果として出力する。出力に際して、実際にネットワークへ設定する装置に適したデータフォーマットに変換する処理を施しても良い。【００５９】
次に本実施の形態の効果を説明する。【００６０】
本実施の形態によれば、問題作成手段１６０が、配信元ノードsを始点とし複数の配信先ノードzを終点とする複数の経路を構成するための制約式、前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式、前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式、およびマルチキャストツリーを構成するリンクまたはノードに関する評価指標を最小化するための目的関数から構成される数理計画問題を作成し、問題解法手段１７０が、この数理計画問題を解くことでマルチキャストツリーを構成するリンクの集合を決定するため、ネットワークのトポロジー情報、配信元ノードsおよび配信先ノードzなどの情報が与えられた場合に、配信元ノードsから複数の配信先ノードzへパケットを転送するためのマルチキャストツリーを数理計画法を用いて設計することができる。【００６１】
また、本実施の形態によれば、配信元ノードsを始点とし各配信先ノードzを終点とする経路を意識して数理計画問題を解くため、そのような経路を意識せずにマルチキャストツリーを設計する方法に比べて、各経路に対して個別に制約をかけたり、最適化を行うことが可能である。以下、この点について補足説明する。【００６２】
配信元ノードsから複数の配信先ノードzへパケットを転送するためのマルチキャストツリーを数理計画法を用いて設計する他の方法として、下記のように、式１０、式１１、式１２に示す制約式の下で、式９に示す目的関数を最小化する数理計画問題を解法する方法が考えられる。【００６３】
Minimize
【数９】
2008133230.tif 000011
・・・（式９）
Subject to:
始点sについて、
【数１０】
2008133230.tif 000012
・・・（式１０）
各終点zについて、
【数１１】
2008133230.tif 000013
・・・（式１１）
始点s、各終点z以外のノードiについて、
【数１２】
2008133230.tif 000014
・・・（式１２）
ここで、Ｋは許容する最大分岐数である。【００６４】
しかし、式９〜式１２中の変数xの右肩にzが付いていないことから分かるように、この数理計画問題は、配信元ノードsを始点とし各配信先ノードzを終点とする経路は全く意識していない。このため、式９に示すような目標関数による最適化は可能であるが、本実施の形態の式６に示したような、配信元ノードから配信先ノードまでの経路に関する遅延の総和の最小化といったような最適化は行うことができない。【００６５】
また、本実施の形態では、配信元ノードから配信先ノードまでの各経路に対して個別に、指定したリンクを通るような制約をかけたり、経路の遅延量を或る値以下に抑えるような制約をかけることも可能になる。【００６６】
『第２の実施の形態』
図４を参照すると、本発明の第２の実施の形態にかかるマルチキャストツリー設計装置２００は、図１に示した第１の実施の形態にかかるマルチキャストツリー設計装置１００と比較して、問題作成手段１６０の代わりに問題作成手段２６０を有する点で相違する。【００６７】
問題作成手段２６０は、問題作成手段１６０におけるものと同様の複数経路制約作成手段１６１、ツリー制約作成手段１６２、合流制約作成手段１６３および目的関数作成手段１６４を有すると共に、折り返し制約作成手段２６１、分岐実行制約作成手段２６２および分岐禁止制約作成手段２６３を有する。本実施の形態では、新たな制約作成手段を３つ追加しているが、折り返し制約作成手段２６１、分岐実行制約作成手段２６２および分岐禁止制約作成手段２６３のうちのいずれか１つ或いは２つを追加した実施の形態も考えられる。これらは概ね以下のような機能を有する。【００６８】
折り返し制約作成手段２６１は、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路はすでに通過したノードへ折り返して通過することを許さないための制約式を作成する。【００６９】
分岐実行制約作成手段２６２は、１つ以上のノードにおいてマルチキャストツリーの分岐を必ず行わせるための制約式を作成する。【００７０】
分岐禁止制約作成手段２６３は、１つ以上のノードにおいてマルチキャストツリーの分岐を許さないための制約式を作成する。【００７１】
問題作成手段２６０は、複数経路制約作成手段１６１、ツリー制約作成手段１６２、合流制約作成手段１６３、折り返し制約作成手段２６１、分岐実行制約作成手段２６２および分岐禁止制約作成手段２６３で作成された制約式と、目的関数作成手段１６４で作成された目的関数とで構成される数理計画問題を記憶装置１２０に数理計画問題１２２として記憶する。【００７２】
次に、図４のブロック図および図５のフローチャートを参照して、本実施の形態の動作を説明する。【００７３】
まず、データ処理装置１１０は、第１の実施の形態のフローチャートである図２のステップＳ１０１〜Ｓ１０４と同様の処理を行うステップＳ２０１〜Ｓ２０４を実行することにより、マルチキャストツリーの設計に必要な各種のパラメータを入力装置１３０から入力して記憶装置１２０に各種パラメータ１２１として記憶すると共に、配信元ノードsを始点とし複数の配信先ノードzを終点とする複数の経路を構成するための制約式（式１〜式３）、前記複数の経路を全て重ね合わせてマルチキャストツリーを構成するための制約式（式４）、前記複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式（式５）を作成する。【００７４】
次に、問題作成手段２６０の折り返し制約作成手段２６１は、配信元ノードsを始点とし複数の配信先ノードzを終点とする複数の経路はすでに通過したノードへ折り返して通過することを許さないための制約式を作成する（Ｓ２０５）。このような制約式を作成する理由は、この制約式が無い場合、一度通過したノードへ折り返し、他のノードへ至る経路が解として得られる場合があり、そのような経路は明らかに無駄な経路であるため、それを排除するためである。ただし、このような制約式を使用する代わりに、解として得られたマルチキャストツリーを検査し、直前に通過したノードへ折り返している経路が存在した場合に、その他の解を求めるために再計算させるようにしても良い。なお、このような制約式を使用しても、一度通過したノードへ他のノードを経由して戻るループ構造は取り除くことはできないため、解にループ構造が含まれている場合、その他の解を求めるために再計算させることが望ましい。【００７５】
具体的には、折り返し制約作成手段２６１は、全てのリンクにおいて式１３に示す制約式を作成する。【００７６】
【数１３】
2008133230.tif 000015
・・・（式１３）【００７７】
式１３は、マルチキャストツリーを構成する各リンクにおいて、ノードiからノードjに至るリンクと、ノードjからノードiへ至るリンクは同時に存在し得ないことを意味する。【００７８】
次に、分岐実行制約作成手段２６２は、１つ以上のノードにおいてマルチキャストツリーの分岐を必ず行わせるための制約式を作成する（Ｓ２０６）。このような制約式を作成する理由は、ネットワーク中にパフォーマンスの高いルータ（ノード）が存在している状況では、そのノードで積極的にパケットのコピーを行って分岐をさせたい場合があるためである。【００７９】
具体的には、任意のノード集合Iに含まれるノードの全てにおいて分岐をさせる場合は、分岐実行制約作成手段２６２は、式１４および式１５に示す制約式を作成する。【００８０】
【数１４】
2008133230.tif 000016
・・・（式１４）【００８１】
【数１５】
2008133230.tif 000017
・・・（式１５）【００８２】
ここで、ノード集合Iは各種パラメータ１２１中のその他の情報１２１４で与えられる。式１４は、マルチキャストツリーが必ずノードiを通過することを意味する。式１５は、マルチキャストツリーが必ずノードiで分岐することを意味する。【００８３】
また分岐実行制約作成手段２６２は、任意のノード集合Iに含まれるノードの少なくとも１つのノードにおいて分岐をさせる場合は、式１６に示す制約式を作成する。【００８４】
【数１６】
2008133230.tif 000018
・・・（式１６）【００８５】
式１６の１番目の式は、変数yiが1のときそのノードiで必ず分岐することを意味し、２番目の式は、ノード集合Iに含まれるノードiに対応するyiのいずれかが必ず1になることを意味する。【００８６】
次に、分岐禁止制約作成手段２６３は、１つ以上のノードにおいてマルチキャストツリーの分岐を許さないための制約式を作成する（Ｓ２０７）。このような制約式を作成する理由は、ネットワーク中にマルチキャスト機能を有しないルータ（ノード）が存在する場合に、そのノードで分岐しないようにする必要があるためである。【００８７】
具体的には、分岐禁止制約作成手段２６３は、任意のノード集合Iに含まれる全てのノードiにおいて分岐を禁止する場合は、式１７に示す制約式を作成する。【００８８】
【数１７】
2008133230.tif 000019
・・・（式１７）【００８９】
式１７は、ノードiへ入力するリンクがあるとき、必ずノードiから出力するリンクは１本であることを意味する。ここで、分岐を禁止するノードiの集合Iは各種パラメータ１２１中のその他の情報１２１４で与えられる。【００９０】
次に、目的関数作成手段１６４は、第１の実施の形態と同様に、マルチキャストツリーを構成するリンクまたはノードに関する評価指標を最小化するための目的関数を作成する（Ｓ２０８）。【００９１】
問題作成手段２６０は、ステップＳ２０２〜Ｓ２０７で作成した制約式およびステップＳ２０８で作成した目的関数を、数理計画問題１２２として記憶装置１２０に記憶する。なお、ステップＳ２０２〜Ｓ２０８は必ずしもフローチャートに示した順番で実行する必要はなく、任意の順番で良い。【００９２】
以降、第１の実施の形態と同様に、問題解決手段１７０により数理計画問題１２２が解法され（Ｓ２０９）、出力手段１８０により、その解１２３に基づいて設計結果のマルチキャストツリーが出力装置１４０から出力される。【００９３】
次に本実施の形態の効果を説明する。【００９４】
本実施の形態によれば、第１の実施の形態と同様の効果が得られると同時に、以下のような効果が得られる。【００９５】
折り返し制約作成手段２６１を有することにより、一度通過したノードへ折り返して他のノードへ至る無駄な経路を排除することができる。【００９６】
分岐実行制約作成手段２６２を有することにより、ネットワーク中にパフォーマンスの高いルータ（ノード）が存在している場合に、そのノードで積極的にパケットのコピーを行って分岐をさせるようなマルチキャストツリーを設計することができる。【００９７】
分岐禁止制約作成手段２６３を有することにより、ネットワーク中にマルチキャスト機能を有しないか、有していてもパフォーマンスの低いルータ（ノード）が存在している場合に、そのノードで分岐をさせないようなマルチキャストツリーを設計することができる。【００９８】
『その他の実施の形態』
以上の実施の形態においては、ディスプレイ等で構成された出力装置１４０を備えていたが、図６に示すように、出力装置１４０の代わりに経路設定機構３０１を接続し、経路設定機構３０１により、マルチキャストツリー設計装置３００で設計されたマルチキャストツリーに基づいてネットワーク３０２中のノードに対してマルチキャストパケットの経路設定を行うようにしても良い。ここで、マルチキャストツリー設計装置３００は、第１または第２の実施の形態のマルチキャストツリー設計装置１００または２００で構成されている。【００９９】
本発明のマルチキャストツリー設計装置は、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態における入力手段１５０、問題作成手段１６０または２６０、問題解決手段１７０および出力手段１８０として機能させ、図２または図５に示した処理を行わせる。【０１００】
一般に数理計画問題は、線形の等式あるいは不等式で与えられる制約式の下で、線形の目的関数の極値を求める問題である。本実施形態では、制約式として、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路を構成するための制約式を用い、目的関数として、マルチキャストツリーを構成するリンクまたはノードに関する評価指標を最小化するための目的関数を用いることを基本とする。ただし、前記制約式だけでは、配信元ノードを始点とし複数の配信先ノードを終点とする複数の経路がそれぞれ独立した経路として解に含まれることになり、また経路同士が合流するような経路も解に含まれることになるため、そのような解を排除するために、前記経路を全て重ね合わせてマルチキャストツリーを構成するための制約式、複数の経路を重ね合わせたときに前記経路同士が合流するトポロジーになることを許さないための制約式を追加する。これによって、数理計画法を用いてマルチキャストツリーを設計することができる。また、配信元ノードを始点とし各配信先ノードを終点とする複数の経路を構成するための制約式を作成することにより、各経路に対して個別に制約をかけたり、最適化を行うことが可能となる。【０１０１】
本実施形態によれば、マルチキャストツリーを数理計画法を用いて設計するため、ダイクストラ法をベースとするマルチキャストツリー設計装置のように最適化目的毎に複雑なアルゴリズムを開発する必要がなくなる。【０１０２】
また本実施形態によれば、配信元ノードを始点とし各配信先ノードを終点とする複数の経路を意識して数理計画問題を解くため、そのような経路を意識せずにマルチキャストツリーを数理計画法で解く方法とは異なり、各経路に対して個別に制約をかけたり、最適化を行うことが可能になる。【０１０３】
本願は、日本の特願２００７−１１１４５６（２００７年４月２０日に出願）に基づいたものであり、又、特願２００７−１１１４５６に基づくパリ条約の優先権を主張するものである。特願２００７−１１１４５６の開示内容は、特願２００７−１１１４５６を参照することにより本明細書に援用される。【０１０４】
本発明の代表的な実施形態が詳細に述べられたが、様々な変更(changes)、置き換え(substitutions)及び選択(alternatives)が請求項で定義された発明の精神と範囲から逸脱することなくなされることが理解されるべきである。また、仮にクレームが出願手続きにおいて補正されたとしても、クレームされた発明の均等の範囲は維持されるものと発明者は意図する。
【産業上の利用可能性】
【０１０５】
本発明は、ノードとリンクとから構成されるネットワーク上で配信元ノードから複数の配信先ノードへパケットを転送するためのマルチキャストツリーを設計するために利用することができる。
【図１】
2008133230.tif 000020
【図２】
2008133230.tif 000021
【図３】
2008133230.tif 000022
【図４】
2008133230.tif 000023
【図５】
2008133230.tif 000024
【図６】
2008133230.tif 000025
【国際調査報告】
2008133230.tif 000026
2008133230.tif 000027
2008133230.tif 000028
2008133230.tif 000029