通信網の構成には一般に,膨大な投資が必要であるだけでなく,網に対する将来需要や技術動向などの条件を考慮した上で,網の設計・計画を繰り返して行う必要がある.従来の通信網の設計法に関する研究では,網のトラヒック要求が単調に増加するという想定が大半であり,トラヒックの局所的な減少や変動のばらつきは考慮されることが少ない.短期な網設計を行うためには,このような局所的な変動を取り込んで,既存設備の有効活用が考慮されなければならない.

　本研究では,網設計・計画,特に短期設計において,既存網の存在を考慮した網設計法を提案することを目的としており,パケット交換網(以下,パケット網)及びATM伝送方式を用いた高速広帯域網(以下,ATM網)を設計の対象とする.

　パケット網の設計法において,基本設計問題であるリンク容量割り当て設計を検討した後,得られた結果やアルゴリズムをフロー割り当て設計及びトポロジー設計に応用し,設計法を拡張していく.パケット網におけるリンク容量割り当て設計に関する研究は,従来から広く行われてきたが,本研究では,既存網という概念を設計問題に取り入れ,今まで考慮されなかった設計問題を検討する.以下,この問題をCA問題(Capacity Assignment Problem)とよぶ.網の短期設計において,既存設備の単位コストが一般に新設設備のそれより小さいため,網設備(リンク)のコスト関数が図1のようになる.図中に,C_iはリンクiの容量,D_iはリンクiに対するコスト,C_0iはリングiにおける既存の容量である.また,d_0i及びd_1iはそれぞれ既存及び新設リンク容量の単位コストであり,網の短期設計の場合,一般にd_0id1iとなる.

　CA問題に対して,図1に示すコスト関数を用いて,パケットの遅延時間要求を満足し,かつ網コスト(総リンクコスト)が最小になるようにリンク容量を算出する.本研究では,リンクコスト関数が非線形かつ微分不可能であるため,このままでは従来の研究のようにラグランジュの乗数法を適用することができない.しかし,各々のリンクを次の3つの集合に適当に振り分けることによって,コスト関数がリンク容量に対して微分可能であると見なすことができるようになり,ラグランジュの乗数法が適用可能となる.ここで3つのリンク集合とは,

　である.

　以上により,CA問題を解くための基本的なアルゴリズムが得られる.このアルゴリズムでは,全てのリンク集合の組合せを考慮するため,最適解が得られるが,計算量が非常に多いという欠点がある.具体的には,網内のリンク数がmであるとき,計算量がO(m.3^m)となる.

　上述の問題を解決するため,計算量の少ない計算アルゴリズムを提案する.計算アルゴリズムでは,リンクの集合を考慮し,算出したリンク容量の値とリンク集合との矛盾が生じるかどうかを調べ,矛盾があったところを除外する.提案したアルゴリズムは,最適解が与えられるだけでなく,計算量も非常に小さいため(測定によると,ほぼO(m)),大規模な網に適用できることがわかる.

　提案した改善アルゴリズムを実際に,既存網を考慮したリンク容量割り当て設計問題に適用した結果,設計の解では,既存容量に固定されるリンクが存在し,特に既存設備の単位コストが小さくなると,このようなリンクが多くなる.これは,既存設備の有効利用が網設計に影響を与えることを示している.

　次に,パケット網のリンク容量・フロー割り当て設計問題(Capacity Flow Assignment Problem:CFA問題)を検討する.実際に,CFA問題はCA問題とFA問題(Flow Assignment Problem:フロー割り当て設計問題)に分解できる.また,FA問題が一種の最短経路問題であるため,各リンクの"長さ"を決定すれば,最短経路アルゴリズムを適用して解くことができる.このとき,リンクの長さが,CA問題で得られた網コストのリンクフローに対する微分となる.すなわち,リンクフローの増分による網コストの増分を最小化することが設計の目的である.FA問題を解くときに,CA問題のためのアルゴリズムが採用されるため,結果的にはCFA問題を解くことになる.

　CFA問題を解くアルゴリズムにおいて,様々な初期トポロジーを設定し,必要のないリンクを網から除外して得られる最小コストの結果が最適な網トポロジーとなる.従って,この方法でパケット網のトポロジー設計問題を解くことができる.設計アルゴリズムに対する有効な初期トポロジーとして,完全グラフが挙げられる.

　一方,既存網の影響を考慮したATM網の設計に関しては,本研究では,従来提案された設計法と異なる容易なかつ一般の通信トラヒックに応用可能な設計法を提案する.また,網を設計する際,一般にATM網のモデルでは,通信局間におけるトラヒック制御を容易に行うため,各通信局間に仮想的な経路(Virtual Path:VP)を設定する.本研究では,VP内に1種のトラヒックが収容されると仮定し,各VPの容量を独立に設計する.ATM網の設計は,大きく分けて次の3つの段階から構成される.

　1.VP内の仮想回線(Virtual Circuit:VC)数の算出

　2.VP容量の算出

　3.VPの物理リンクへの収容設計

　1の設計では,与えられた呼量に対して,通信の呼損率が許容値以下になるようにVC数を求める.この段階の設計が従来の回線交換網の回線数設計のように行える.これによって,アーランB式を用いてVC数を算出する.得られたVC数がVPに多重化される回線数を示している.

　2の設計では,セルの遅延時間及び棄却率といった通信品質を満足するように,VPの容量を算出する.この段階の設計において,VPをG/D/1/Kの待ち行列にモデル化し,解析を行った後VPの容量を求める.ただし,待ち行列解析を行う際,入力トラヒックにおけるセルの到着確率p_k(t)(時間間隔t内にk個のセルが到着する確率)を求めなければならない.しかし,一般の到着過程,特に,バースト性を表すものに対してp_k(t)を求めることは非常に困難であり,また,計算量が多いため,容易に計算できる近似法が必要となる.本研究では,まず,以下のような確率過程を"基本的な過程"として定義する.

　1.P:ポアソン分布による到着過程

　2.D:単位分布による到着過程

　3.Z:到着のない過程

　ATM網に対するバースト性を表すセルの到着過程は一般に複数の状態から構成され,それぞれの状態における確率過程が上述の基本的な過程であることがわかる.例えば,ON-OFFモデル＝D+Z,IPP＝P+Z,N状態-MMPP＝などである.以上を利用して,入力トラヒックの到着確率が近似できる.IPPの場合について,到着確率が次のように算出できる.

　ただし,1/及び1/はそれぞれIPPのONとOFF区間の平均時間であり,及びはそれぞれ基本的な過程であるP及びZの到着確率である.

　また,一般のN状態で構成される確率過程の到着確率が次のようになる.

　ただし,r_iは状態i区間の平均時間,p_(i,k)は状態iにおける基本的な過程のp_kである.

　以上の近似法を厳密計算法と比較すると,精度が非常に高いだけでなく,各々の基本的な過程のp_kが簡単に計算できるため,計算量が非常に小さいことがわかる.

　以上をまとめると,本研究で提案するVP容量の設計法は次のような性質をもっている.

　1.G/D/1/Kの解析によって,従来のような限られたトラヒックに対する設計法と異なり,一般の通信トラヒックに対応できる方法である.

　2.p_kの近似法によって,設計法の計算量が小さいため,大規模な網に適用することができる.

　2の設計段階で得られた各局間のVP容量を用いて,網コストが最小になるように,VPの物理リンクへの収容設計を3の段階で行う.この段階において,物理リンクのコスト関数が線形,非線形の他に,既存網を網設計に考慮するために,図1に示すようなコスト関数を用いる.3の設計問題は,一種の最短経路問題であり,パケット網のフロー割り当て設計問題を解くアルゴリズムが利用できる.既存網を考慮したATM網の設計結果より,パケット網と同様に,既存設備の有効利用が設計の前提であることがわかる.

図1:既存/新設設備のコスト差を考慮したリンクコスト関数

　本研究の結果及び結論として,以下のようなことが挙げられる.

　1.本研究で提案した通信網の設計法を実際の網に適用すると,既存設備の有効利用を考慮した網設計を行うことができる.

　2.提案した網設計法の計算量が小さいため,大規模な通信網に適用できる.

　本論文は「Research on Network Design with Consideration of Existing Network(既存網を考慮した通信網の設計法に関する研究)」と題し、通信網の設計で多くの研究が行われていた新規に網を設計する手法に変えて、現実に存在する通信網を有効に活用する設計手法に着目し、新たに高速計算アルゴリズムを提案し現実の設計に活用する目処を明らかにしたものであって、6章から構成されている。なお論文は英文で書かれている。

　第1章「Introduction(序論)」では、従来の研究成果をまとめた上で、本研究の課題と位置づけを示し、全体の概要を記している。

　第2章は「Link Capacity Assignment in Packet-switched Networks with Consideration of Existing Network(既存網を考慮したパケット交換網のリンク容量割り当て)」と題し、パケット網の設計において基本課題であるリンク容量割り当て設計を論じたもので、既存網の存在を考慮する基本アルゴリズムを提案し、通常想定される計算手法では多大の時間を要することを指摘した後に、リンクの性質により集合を導入することで計算の範囲を限定できることを明らかにするとともに、計算量を大幅に低減できる手法を新たに提案し、これを例示している。

　第3章は「CFA and TCFA Problem in Packet-switched Networks with Consideration of Existing Network(既存網を考慮したパケット通信網のリンク容量フロー割り当て問題並びにトポロジー容量フロー割り当て問題)」と題し、前章の発展として既存網の存在を考慮した上でリンク容量フロー割り当て問題(CFA)並びにトポロジーフロー割り当て問題(TCFA)を論じたもので、共に問題の定式化の後に計算アルゴリズムを提案し、同時に前章で提案した高速計算手法を適用することで設計を可能とすることを例示し、また良好な解を導くためには計算アルゴリズムの初期状態の設定が重要であることを述べている。

　第4章は「Outlines of the ATM Network Design(ATM網設計の概要)」と題し、既存網存在を考慮する通信網設計を発展させATM網に適用するための方針を論じたものであり、ATMに特有の仮想パス(VP)の設計問題に帰結するための設計方針を示し、この後にバースト性を考慮したトラヒックモデルにより取り扱うことができる多様な属性を持つ通信モデルを包含する設計を可能とすることを示している。

　第5章は「ATM Network Design Algorithms(ATM網設計アルゴリズム)」と題し、前章の各論として、設計問題をVP容量の算出とVPを物理リンクに収容するための設計手法に分割し、前者では、VPをG/D/1/Kの待ち行列モデルにモデル化してバースト性を考慮しつつ伝送単位であるセルの棄却率を求める近似計算手法を提案し必要とするVP容量を算出する手法を提示する一方、後者では既存網の存在を想定しつつパケット網のリンク容量フロー割り当て問題(CFA)のアルゴリズムを適用するための方策を示し、これらを総合した適用事例を示している。

　第6章は「Conclusions(結論)」であって、以上の成果を要約し大規模な通信網に適用可能な手法であることを結論している。

　以上これを要するに本論文は、既に存在する網を考慮し通信網の設備設計を行う手法を論じ、パケット交換網とATM網の設計を具体的に取り上げる中で、多大な計算時間を要することになる設計を網の規模に対して線型となるアルゴリズムとその過程で使用する数値計算手法を新たに提案することで、従来取り扱われることが少なかった既存網を考慮する設計に進歩をもたらしたものであって電子工学に貢献するところが多い。

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