| 内容要旨 | | 1はじめに テレビ会議,映像分配,遠隔学習,分散コンピューティングなどシステム応用が拡大されつつある現状の下で,マルチキャスト(multicast)通信は,通信ネットワークの重要な機能として取り上げれている.マルチキャスト通信のルーティング(routing)とは,システムのリソースに関する情報を利用して送信元(source)から多送信先(destination)までの効率的な通信経路(route)を計算するものである.このような計算は複雑度が非常に高く,理論的にはNP完全問題とされている.特に,ネットワークサイズが大きい場合,ヒューリスティックな方法,あるいは漸近的な方法,及び分散型計算方法を用いらざるを得ない. 本論文の目的は,大規模ネットワークを対象とするマルチキャストルーティング方法を講じることにある.その際,主に以下の四つの問題解決を目指している.(1)全体のネットワークをマルチクラスタ・アーキテクチャ(multi-cluster architecture)によって構成されることを検討する.(2)近似最適経路を求めるヒューリスティックなルーティングアルゴリズムを提案する.(3)漸近的な手法を用いた大域的な近似最適経路の求め方を提案する.(4)送信先における受信したい情報量に対する異なる要求,即ち,非対称的なマルチキャスト通信という状況を考え,それに対応できるルーティング方法を提案する.それに,リアルタイム・マルチメディア通信において,送信元から送信先までの通信遅延に制限要求がある場合の遅延制約型ルーティング方法を提案する. 2マルチクラスタ・アーキテクチャ2.1クラスタリングの必要性 大規模ネットワークにおいては,トポロジ情報やリソース情報を集中的に管理することは困難である.それを解決するために,クラスタリング(clustering)を行い,ネットワークをクラスタに分けて,クラスタ単位で情報共有及びクラスタ外へアグリゲートな(aggregate)情報を提供することにより,効率的にルーティングを行う.クラスタリングを用いることによって,以下のメリットがある. ●分散型計算によって計算複雑度が低減される. ●各クラスタは局所的な情報(即ち,"部分知識")を所有するだけでルーティングが行える. ●システムのスケラビリティ(scalability)が向上できる. ●異種ネットワーク間の接続管理が容易になる. 2.2クラスタリング 制約条件のあるクラスタリング問題はNP完全問題に属する.そのため,従来ではヒューリスティックを用いて,集中型計算で近似解を求める方法はよく使われる.しかし,大規模ネットワークの場合は,集中型計算に問題が生じやすい.特に,ネットワークの拡張やトポロジの局部的な変動等を考えると,分散型計算は望ましい.そこでここで,完全分散型のクラスタリングアルゴリズムを提案した.アルゴリズムを実行する前提条件は以下にある.つまり,ネットワーク中のノードにID番号が付き(そのノードの果たす役割によって付ける),他のノードに識別できる.近隣のノードにメッセージを送り合うことにより,各ノードは矛盾なく各々のクラスタへ配属されることになる. ルーティングを行うために,クラスタにおいては一つあるいは複数のノードがクラスタ内のトポロジ情報やリソース情報を持つ.また,境界(boundary)ノードは,クラスタに関するアグリゲートな情報を所有するように設定する. 3マルチキャスト・ツリーを求める基本的な方法 マルチキャスト・ツリー(multicast tree)を求める方法は,二種類に大別できる.Source-Initiated方法とDestination-Initiated方法である.ここで,マルチクラスタ・アーキテクチャを有するネットワークにおけるSource-Initiated方法とDestination-Initiated方法をそれぞれ提案する. Source-Initiated方法 この方法は,三つのフェーズによって構成される.第一フェーズは,トポロジ情報を用い,マルチキャスト・メンバー・ノードが含まれているクラスタに対してクラスタレベルのツリー(CLT)を求める.このCLTはホップ数(hops)情報に基づいて得られるMinimum Spanning Tree(MST)である.第二フェーズは,CLTにあるクラスタの間に,マルチキャスト・メンバー・ノード以外のリレー(relay)用境界ノードを決める.第三フェーズは,各クラスタにおけるマルチキャスト・メンバー・ノードとリレーノードを連結する最小コストツリー(minimum-cost tree)を求める. Destination-Initiated方法 この方法も,三つのフェーズで構成される.第一フエーズは,マルチキャスト・メンバー・ノードが含まれる下流(downstream)のクラスタにおいて,これらのノードを連結する最小コストツリーを求める.第二フェーズは,各最小コストツリーと送信ノード間の最短経路を求める.第三フェーズは,最短経路が通る上流(upstream)のクラスタにおいて,マルチキャスト・メンバー・ノードとリレー用境界ノードを連結する最小コストツリーを求める. 以上のSource-Initiated方法とDestination-Initiated方法を用いて行ったシミュレーションから,後者は前者より,より最適な結果が得られることがわかる.しかし,両方法は計算複雑度が低いことを評価できるものの,大域的な最適収束解は得られない. 4漸近的な手法によるマルチキャスト・ツリーを求める方法 3で述べた方法で最適収束解を得られないことを踏まえ,ここで,Aggregate-Disaggregate Flow手法及び双対手法を使用し,大域的な最適収束解を得るような方法を提案する. 解決方法は次のようである. 問題の分解 大域的な最小コストツリー問題(オリジナル問題)を,AP(Aggregate-flow Problem)とDP(Disaggregate-flow Problem)に分解する.APは,任意クラスタのノードと他のクラスタ(クラスタノード)からなるグラフを対象とし,クラスタ内部のコスト,及びノードとクラスタ間のコストの加算結果を最小化することを目的とする.DPは,連結している任意二つのクラスタからなるグラフを対象とし,クラスタ間のコスト,各ノードとダミーノード間のコストの加算結果を最小化することを目的とする.その上,DPに対し双対変換を行い,DDP(Dual Disaggregate-flow Problem)となる.APとDDPを結合させることにより,オリジナル問題をミニマックス問題に変形させる. 問題の定式化 オリジナル問題の定式化の形は,上述の分解により,APの定式化とDPの定式化あるいはDDPの定式化になる.AP定式化の目的関数は,クラスタの内部リンクにおけるフローのコストと,ノードとクラスタ間のアグリゲート・リンク(aggregate link)におけるフローのコストとの合計値を最小化するものである.その制約条件としては,(1)送信ノードにおけるフローの量はp-1(pはマルチキャストグループのメンバー数),受信ノードにおけるフローの量は-1,他のノードは0である.(2)リンク上のフロー量の合計値はそのリンクの容量以下でなければならない.ということがあげられる.一方,DP定式化の目的関数は,クラスタ間のリンクにおけるフローのコストと,ノードの出/入フローのコストとの合計値を最小化するものである.その制約条件として,リンク上のフロー量はそのリンクの容量以下であり,ノードの出/入フローはそのノードにおけるアグリゲート・リンクの容量以下でなければならない.DDP定式化は,双対コスト変数の導入よりDP定式化から変換できる. 問題の解法 前述したミニマックス問題を解決するには,まず,アグリゲート・リンクの初期コストを設定し,APを解いてクラスタ内部リンクのフローとアグリゲート・リンクのフロー量を求める.その結果を用いて,DDPを解くことができ,双対コスト変数の値を得る.次に,双対コスト変数の値をAPのアグリゲート・リンクの新しいコストとして入力し,APを解く.APを解いてから,DDPを解く.このプロセスを繰り返し実行していく.つまり,オリジナル問題の最適解の下限値(LB)となるAPの解と,オリジナル問題の最適解の上限値(UB)となるDDPの解の差,いわゆる最適解ずれを縮小しながら,最適解を求めていく.その中で,Lagrangean緩和法とSubgradient手法に基づいたアルゴリズムを用いて,個々のAPとDDPを解く. この方法による最適解への収束性を保つことが判明した.シミュレーションの結果により,クラスタのサイズの変化に伴い,最適解への収束の速度が違うことを示した.この方法の主なメリットは,計算時間と解の最適性の間にトレード・オフ(trade-off)があることである. 5非対称的なマルチキャスト・ツリーを求める方法 大規模ネットワークの場合は,相互接続されている各サブ・ネットワークの性能の差,受信端末の性能の差,あるいは単に受信ユーザの情報に対する興味の相違などのため,同一情報を異なる帯域(違う受信品質)で受信することがある.従来のマルチキャストルーティング方法では,この種のいわゆる非対称的なマルチキャストを考慮していない.以下に,非対称的なマルチキャスト・ツリーの求め方を提案する. 5.1MCT(Minimum-Cost Tree)を求める近似解法 ヒューリスティック方法を用いた次の三つのアルゴリズムを検討する. (1)SPT Heuristic(SPTH) 各受信ノードと送信ノード間の最短パス(メトリックはコストとする)を計算する.共通なリンクを併合し,一つのツリーをなす.その中のリンクに対して,リンクを共通に使う受信ノードの帯域要求値の中の最大なものを使用帯域として設定する. アルゴリズムの計算複雑度1:O((n2+n-p)(p-1)). 1ここに示すのは,クラスタ毎の計算複雑度である.また,nはクラスタサイズ,pはマルチキャストグループサイズである.以下同. (2)Modified Shortest Path Heuristic(MSPH) Steiner-treeを求める従来のアルゴリズムの一つであるShortest Path Heuristic(SPH)を修正する.これを非対称的なマルチキャスト・ツリーの計算に用いる.アルゴリズムの構成は,以下のとおりである. Step1:クラスタにおける送信ノードに一番"近い"境界ノードを見つけ出す.上流のクラスタの中に,下流の受信ノードのリレーノードとなる境界ノードを見つけ出す. Step2:マルチキャスト・メンバー・ノードあるいはリレーノードを含むクラスタの中で,SPHに従い帯域要求値の大小の順にノードを上流の境界ノードが頂点となるツリーを構成していく. Step3:隣接しているクラスタにある各サブ・ツリーを,相応な境界ノード間の"最短"パスで連結し,一つのツリーを構成する. アルゴリズムの計算複雑度:O(n2p). (3)Modified Average Distance Heuristic(MADH) Average Distance Heuristic(ADH)は,Steiner-treeを解く基本的なアルゴリズムの一つである.ここで,これをを修正し,非対称的なマルチキャスト・ツリーの計算に当てる.アルゴリズムの構成は,以下のとおりである. Step1:MSPHのStep1と同じ. Step2:マルチキャスト・メンバー・ノードあるいはリレーノードが含まれるクラスタにおいて,最初は,マルチキャスト・メンバー・ノードとリレーノードを個々のサブ・ツリーとする.各サブ・ツリーとの平均距離の最小なセントラルノード経由で二つのサブ・ツリーを"最短"パスで連結する.これを繰り返して行い,最終的にこれら全てのノードを連結した一つのツリーになる. Step3:MSPHのStep3と同じ. アルゴリズムの計算複雑度:O(n3). シミュレーションより,帯域要求の非対称性を考慮しない従来のアルゴリズムに比べ,提案したMSPTH,MSPH及びMADHのほうは性能がはるかによく,その利点を示している. 5.2遅延制約のあるMCTを求める近似解法 ヒューリスティック方法を用いた次の三つのアルゴリズムを検討する. (1)Delay-Constrained SPT Heuristic(DCSPTH) Step1:送信ノードから各受信ノードまでの"最短"(遅延をメトリックとする)パスを求める.遅延制限値との差(遅延ギャップ)を計算する.遅延制限値を超す"最短"パスを持つ受信ノードがある場合,受信ノードと交渉して遅延制限値を緩める. Step2:遅延ギャップが非零の受信ノードに対して,送信ノードとの間のパスをコスト上の最適化を行う.即ち,クラスタにおいて,受信ノードあるいは下流境界ノードと上流境界ノード間のパスの代わりに遅延制限を違反しない最小コストパスを使う.遅延ギャップから新パスの旧パスとの遅延増加分を引き,上流のクラスタに送る.上流のクラスタにおいても,同様な処理を行う. Step3:全てのパスに対して最適化処理を終え,パスを併合して一つのツリーをなす.各リンクに対しては,そのリンクを共通に使う受信ノードの帯域要求値の中の最大なものを使用帯域として設定する. アルゴリズムの計算複雑度:O((n3-n2p+n2+n-p)(p-1)). (2)Delay-Constrained Shortest Path Heuristic(DCMSPH) Step1:送信ノードから受信ノードが含まれるクラスタ(の境界ノード)間の"最短"(遅延をメトリックとする)パスを求める.遅延制限値と,クラスタにある受信ノードの最大遅延値との差を遅延ギャップとする.遅延制限値を超す"最短"パスを持つ受信ノードがある場合,受信ノードと交渉して遅延制限値を緩める. Step2:クラスタにおいて,初期サブ・ツリーに上流境界ノードが含まれるとする.帯域要求値の大小の順に,遅延制限を違反しない最小コストパスでノードを,サブ・ツリーに連結する.遅延ギャップからクラスタ内のパスの遅延の増加分を引き,遅延ギャップ値を上流のクラスタに送る.上流のクラスタにおいても,同様な処理を行う. Step3:隣接しているクラスタにある各サブ・ツリーを,相応な境界ノード間の"最短"パスで連結し,一つのツリーを構成する. アルゴリズムの計算複雑度:O(n3p-n2p2+n2p). (3)Delay-Constrained Distance Network Heuristic(DCMDNH) Step1:DCMSPHのStep1と同じ. Step2:クラスタにおいて,上流境界ノードと各受信ノードあるいは下流境界ノードとの"最短"(遅延をメトリックとする)パスを求める.これらのパスによって一つのツリーが構成される.このツリーに対して,遅延制限を違反しない限り,コストのより小さいパスを用いてパス切換えを行う.ただし,ここで,パスのコストはパスの本来のコスト掛ける帯域要求値後得られた値のことである.遅延ギャップからクラスタ内のパスの遅延の増加分を引き,遅延ギャップ値を上流のクラスタに送る.上流のクラスタにおいても,同様な処理を行う. Step3:DCMSPHのStep3と同じ. アルゴリズムの計算複雑度:O(n4+n2(p-1)). 6おわりに 本論文は,大規模ネットワークに適するマルチキャストルーティング方法として,クラスタリングに基づくマルチキャストルーティング方法を提案した.シミュレーションにより,これらの方法の特性を示し,従来の方法に比べ,有効性を指摘した.帯域要求の動的な変化に対応できるような方法などが,今後の研究課題である. |