B-ISDN技術の発展に伴って1対多通信や多対多通信などの多地点間通信のような多様かつ高度な通信形態のサービスが提供可能となっている。B-ISDNの情報転送技術として標準化が進められているATM技術を用いる網においては、交換点において情報を複製し多方路へ情報を伝達することが容易となり、網リソースを有効利用した多地点間接続の提供が可能となる。ルーチング問題は、1対1通信では2点を結ぶ経路を選択することとなるが、多地点間では各交換点は情報複製機能を備えているものとすると、発信ノードと着信ノードを結ぶ木状経路を選択することとなる。通信コスト等の点から最適な経路を選択することが重要である。

　多地点通信においては、通信中に発着信ノードが動的に参加したり、離脱したりすることが必ずある。従って、離脱するノードのコネクションを解放したり、参加するノードとコネクションを接続したりすることが必要となる。通信中に発着信ノードが動的に参加したり、離脱したりすることがないルーチング問題は静的ルーチング問題と呼び、逆に、発着信ノードが動的に参加したり、離脱したりすることがあるルーチング問題は動的ルーチング問題と呼ぶ。

　静的ルーチング問題において、中継専用ノードを含む多地点間の最適経路問題は、グラフ上でのスタイナー木問題(Steiner Tree Problem)として定式化される。この問題はNP完全(NP complete)であることが知られており、近似解法も含め各種の検討が行なわれている。

　動的ルーチング問題は木のリンク配列によって2問題に分けられる。一つは、新しい木を構成するときに元の木のリンクを配列にしない非再配列問題である。もう一つは、新しい木を構成するときに元の木のリンクを配列にする再配列問題である。非再配列問題とは、離脱するノードが木上の葉ノード(次数1)であれば、そのノードを結ぶルートを木から削除し、木上に残ったルートと参加するノードを結ぶ最適ルートを選択することである。一方、再配列問題とは、元の木のルートを一部または全てを削除/再配列し、木上のルートと参加するノードを結ぶ最適ルートを選択することである。図1に非再配列問題と再配列問題の例を示す。

図1 非再配列問題と再配列問題の例

　通信網において、リンクの再配列を行なうと、データの順序を逆転して受信する可能性があり、また、再配列の処理時間が増大し、ネットワーク制御が複雑になる。特に、従来のATM網では、セルの順序受信が重要であるので、再配列の場合より非再配列の場合の方が適している。このことを考慮して、1対多通信における動的ルーチングの非再配列問題の検討が行なわれている。

　完全放送型の多対多地点通信において、コネクションに参加ノード数がZとすれば、各参加ノードは一つの情報信号を送出し、他参加ノードからZ-1個の信号を受信する。多直通ポイントツウポイントパス形によるルーチングでは、Z(Z-1)/2個の通信回路が必要なので、膨大な通信コストを使うため、あまり実用化には適しない。一方、マルチキャスト木による完全放送型の多対多地点通信ルーチングでは、各参加ノードがマルチキャスト木を持ち、そのマルチキャスト木を経由して情報を送信する。従って、マルチキャスト木によるルーチングのコネクション全体は、Z個の木状経路があり、マルチキャストの情報複製機能を利用することによって多直通ポイントツウポイントパスによるルーチングより通信コストが低い。

　本論文では、マルチキャスト木によるルーチングに基づき、完全放送型の多対多地点通信において通信コストの点から最適な経路を選択するルーチングアルゴリズムに関する研究を報告する.論文の内容として、制約のない動的ルーチング問題と制約のある静的ルーチング問題と制約のある動的ルーチング問題において、それぞれの問題の最適な経路を選択する方式を論じ、そのルーチング方式に対するルーチングアルゴリズムを提案する。

　制約のない完全放送型多対多通信における動的ルーチングの非再配列問題では、通信経路を選択する方式に制約条件がないので、各参加ノードは一つの木状経路を経由し、情報をやりとりするのが最適である。この問題に対して、単純なDG(Dynamic Greedy)アルゴリズムと、スタイナー木問題の近似アルゴリズムの中で性能のよいRS(Rayward-Smith)アルゴリズムから改造されたDRS(Dynamic Rayward-Smith)アルゴリズムについて述べる。そして、それらのルーチングアルゴリズムを改善したWC(Weighted Center)アルゴリズムを提案し、計算機による性能比較を行なった。DGアルゴリズムとDRSアルゴリズムでは、参加するノードがあるとき、その時点だけを考えて最小コスト経路を選択することである。しかし、一つ一つの時点のコスト総和を最小化するにより、総合のコスト総和が最小になるとは限らない。参加する各ノードを木に接続する場合、木上の適切な位置がある。参加する各ノードに対する木上の適切な位置はグラフの形や木やリクエストの時間による順番などに関連する。WCアルゴリズムでは、木の中心部に近いことと小さいパスコストを与えることの2条件を満たすノードを探し、参加するノードをその2条件を満たしたノードに接続する。WCアルゴリズムはDGアルゴリズムとDRSアルゴリズムより良いコスト性能を与える。

　通信網におけるルーチングでは、通信品質について考慮する必要がある。例えば、マルチメディア通信サービスでは、発着局間の情報転送遅延時間とその通信品質の重要な指摘である。また、通信経路を選択する際には各リンクの使用可能な幅帯域を考慮する必要がある。コネクション設定の手順において、通信サービスとして要求される幅帯域を提供することができれば、通信経路のコネクションが設定される。これらのことにより、本論文では、発着局間の情報の転送遅延時間の上限値と各リンクの使用可能な幅帯域を通信経路選択の制約条件とする。

　制約のあるマルチキャスト木による静的ルーチング問題は、パスのモデルにより単一双方向のマルチキャスト木によるルーチングと多数単方向のマルチキャスト木によるルーチングに分けられる。図2に単一双方向のマルチキャスト木によるルーチングと多数単方向のマルチキャスト木によるルーチングの例を示す。

図2 単一双方向のマルチキャスト木によるルーチングと多数単方向のマルチキャスト木によるルーチングの例

　単一双方向のマルチキャスト木によるルーチングでは、各参加ノードが同一のマルチキャスト木状経路を経由して情報を送信する。従って、発着局間の情報の転送遅延時間を上限値に納めることができないので、各リンクの使用可能な幅帯域だけを通信経路選択の制約条件とする。このルーチングの経路を探すことに対し、SDMT(Single Duplex Multicast Tree)近似アルゴリズムと探索列挙法による完全アルゴリズムを提案し、SDMTアルゴリズムによる近似解答と探索列挙のアルゴリズムによる完全解答を比較し、近似解答の妥当性を示している。

　一方、多数単方向のマルチキャスト木によるルーチングでは、各参加ノードが一つのマルチキャスト木を持ち、その木状経路を経由して情報を送信するので、発着局間の情報の転送遅延時間を上限値に納めることができ、発着局間における転送遅延時間の上限値と各リンクの使用可能な幅帯域を通信経路選択の制約条件とする。このルーチングの経路を探すことに対し、MSMT(Multiple Simplex Multicast Tree)近似アルゴリズムと探索列挙法による完全アルゴリズムを提案し、MSMTアルゴリズムによる近似解答と探索列挙のアルゴリズムによる完全解答を比較した結果を示している。

　制約のあるマルチキャスト木による動的ルーチング問題は、静的ルーチング問題と同様、単一双方向のマルチキャスト木によるルーチングと多数単方向のマルチキャスト木によるルーチングに分けられ、発着局間の情報の転送遅延時間の上限値および各リンクの使用可能な幅帯域を通信経路選択の制約条件とする。

　単一双方向のマルチキャスト木によるルーチングにおいて、通信経路が一つのマルチキャスト木状経路となるので、動的ルーチング問題の場合には制約のない動的ルーチング問題に対するWCアルゴリズムを採用できる。この問題に対し、単純なSDG(Single Duplex Greedy)アルゴリズムとWCアルゴリズムから採用したCWC(Constrained Weighted Center)アルゴリズムを提案し、静的問題に対するSDMTアルゴリズムによる結果を下限値の尺度としてアルゴリズムの性能評価を行った。CWCアルゴリズムが良い結果を与えることを示している。

　一方、多数単方向のマルチキャスト木によるルーチングでは、単純なMSG(Multiple Simplex Greedy)アルゴリズムと、WMS(Weighted Multiple Simplex)アルゴリズムを提案する。WMSアルゴリズムでは、木の発信ノードに近いことと小さいパスコストを与えることの2条件を満たすノードを探し、参加するノードをその2条件を満たしたノードに接続する。静的問題に対するMSMTアルゴリズムによる結果を下限値の尺度としてこれらのアルゴリズムの性能評価を行なった、WMSアルゴリズムが良い結果を与えることを示している。

　次世代高速広帯域ネットワークの実現に向けた方式には、光交換網におけるLLN(Linear Lightwave Network)が提案されている。LLNを用いた光交換網を対象ネットワークモデルとした多対多通信のルーチング方式は今後の課題である。

　本論文は「The Multicast Tree Based Routing for The Complete Broadcast Multipoint-to-Multipoint Communications(完全放送型の多対多地点通信のマルチキャスト木によるルーチング)」と題し、全7章から成り英文で記載されている。

　第1章は本論文の序論であり、マルチメディア技術においては、情報分配サービス、多地点ビデオ会議システム、多対1情報収集システム等のマルチポイント接続の要求があり、これらの問題についてのルーチングの問題が重要であるとして、本論文の目的を示している。

　第2章では本研究の背景となるマルチポイント型ネットワークにおけるルーチング問題についての従来の研究を整理している。従来のマルチポイント型ルーチングの問題には、静的ルーチングと動的ルーチングがある。静的ルーチングではネットワークと参加ノードは予め決まっており、これを接続する経路を定める。動的ルーチングでは参加ノードが付け加わったり、除かれたりする変化が常時生ずるときに、マルチポイント通信のためのルーチングを行なう。従来マルチポイントルーチングでは、1対多の問題が主として扱われているのに対して本論文の研究では多対多の問題を種々の条件で扱う点に特色があり、問題の定式化も独自に行っている。

　第3章は「グラフモデル」と題し、本研究で提案するアルゴリズムを評価するために使用するグラフについて述べている。グラフはノード数で10から50の種々のグラフであり、そのノード間のリンクは乱数によって発生される。このようにしてランダムに発生した10種類のグラフについて本研究の第4章以下で提案するアルゴリズムが適用される。

　第4章はマルチポイント型動的アルゴリズムであるウェイテッドセンター(WC)アルゴリズムを提案している。この分野の研究としては従来から情報源ノードがひとつあり、多数の受信ノードが存在するモデルで、情報源ノードは接続から除かれることなく、受信ノードのみが追加されたり、除かれたりするモデルではいくつかの研究があるが、この研究ではすべての参加ノードが情報源であり、受信者でもあることを特色としている。ここで提案するWCアルゴリズムは、いくつかのノードが離脱しても中継ノードとして残される可能性の高いノードと、そのノードと新らしく参加するノードの間のパスのコストとを考え、新らしく参加するノードを接続してゆくものである。ノードが中継ノードとして残される可能性はトリーの中心部に近いほど高いと考え、中心部にあることを示す関数とコストの重み付けしたものをパラメータとして、トリーに入れるリンクを選択する。この章では第3章で設定した各種のグラフに対して、WCアルゴリズムを使い、重み付けを適切に選定すれば、従来知られているアルゴリズムに比べ、より低コストのトリー型接続を形成できることが示されている。

　第5章では制約条件を考慮した静的ルーチング問題について述べている。ここで示す問題では遅延制約とリンク容量制約を受けるものとしている。経路モデルはすべての経路を全二重とし、往復の情報は必ず同一の経路を通ることとする全二重モデル(SDMT)と、往復の経路をそれぞれ独立に取扱う単向モデル(MSMT)とに分類される。この章ではこの二つの問題について、最小コストの経路を求めるヒューリスティックなアルゴリズムを提案している。これらのヒューリスティックを用いたトリーのコストを全数探索によって求めた真の最小コストと比較して、ヒューリスティックの性能評価を行ない、計算時間を2桁以上低下して、コストは高々1.3倍程度に入ることを示している。

　第6章は制約条件を考慮した動的ルーティング問題に関するものである。ルーティングに当って第5章と同様の遅延制約とリンク容量制約が存在するものとし、第4章と同様にマルチキャストトリーに参加するノードの追加、削除が時間的に生ずるという条件で、全二重モデルと単向モデルの両方の場合についてルーティング問題を取扱う。この両者のモデルについて、共に2つのアルゴリズムが提案され、その性能について、第5章で示された、静的ルーティングで得られたコストを下限として性能評価を行なって、各アルゴリズムの特質を明らかにしている。全二重モデルについては制約付き重み付け中心(CWC)アルゴリズムか、単向モデルでは重み付き多重単向(WMS)アルゴリズムがすぐれていることを示している。

　第7章は本論文の結論であり、全体をとりまとめている。以上これを要するに本論文は次世代広帯域ネットワークの中で重要な役割を持つ多様なマルチキャスト通信のためのルーチングアルゴリズムを創案し、その特性を明らかにしたものであって、通信工学上貢献するところが少くない。

　よって著者は東京大学大学院工学系研究科電子工学専攻における博士の学位論文審査に合格したものと認める。