既存網を考慮したパケット交換網のリンク容量割り当て設計法 : 凹のリンクコスト関数の場合

概要

論文の詳細を見る
通信網の設計・構築を行う際、一般に網の既存設備を有効利用することが重要である。筆者らは、パケット交換網におけるリンク容量割り当て問題(CA問題)について、既存網の概念を網設計問題に採り入れ、リンクコスト関数が凸関数の場合を検討した。凸のコスト関数が、既存設備の単位コストが新設設備のそれより小さい場合を表現し、短期網設計の設備コスト関数として用いられる。しかし、長期網設計などの場合では、一般に設備のコスト関数が凹関数である。本論文では、リンクコスト関数が凹関数の場合のパケット交換網におけるCA問題を検討し、問題に対する設計アルゴリズムを提案することを目的としている。本論文では、CA問題の定式化を行った後、問題の最適解の重要な性質を求める。この性質とは、問題の最適解において、既存のリンク容量に等しく設定されるリンクが存在しないことである。この性質により、ラグランジュの乗数法に基づく2つのヒューリスティック的な設計アルゴリズムが提案される。本論文で考慮されるCA問題は凸計画問題ではないため、大域最適解を求めることが困難であり、ヒューリスティック的な手法を用いて解を求める必要がある。しかし、数値結果より、解の最適性およびアルゴリズムの計算量の面では、提案されたアルゴリズムがCA問題を効率よく解くことができるとわかる。
1996-03-29

既存網を考慮したパケット交換網のリンク容量割り当て設計法 : 凹のリンクコスト関数の場合

スポンサーリンク

概要

著者

関連論文

スポンサーリンク