| No | 98839 |
|---|---|
| 標題（和） | 複数QoSに基づく近似精度可変な経路選択アルゴリズム |
| 標題（英） | Routing Algorithm for Multiple QoS Requirement with Arbitrary Approximation |
| 研究会名（和） | 交換システム; 情報ネットワ-ク; 通信方式 |
| 研究会名（英） | Switching Systems Engineering ; Information Networks ; Communication Systems |
| 開催年月日 | 1997-09-29 |
| 終了年月日 | 1997-09-30 |
| 会議種別コード | 2 |
| 共催団体名（和） | |
| 資料番号 | SSE97-89, IN97-82, CS97-80 |
| 抄録（和） | マルチメディアの通信サ-ビスを提供する際には,要求された通信路の帯域幅,伝送遅延および誤り率等の複数のサ-ビス品質(QoS)条件を同時に満足し,かつコスト最小の経路を選択することにより,網の効率的な利用を図ることが重要である.従来より,このための近似アルゴリズムが提案されているが,1)選択経路が経験則に依存する,2)近似の性能を表す近似比率(選択経路のコストと最適経路のコストの比の最大値)が網構成に依存した固定値となるため,任意の近似比率で経路選択ができない,3)複数のQoS条件を満足する経路があっても,実際には選択されない可能性があるという問題がある.本稿ではこれらの問題を解決するため,アルゴリズム実行時に近似比率(1+ε)を任意に設定することにより,複数QoS条件を同時に満足し,かつ最適経路のコストの(1+ε)倍以内のコストを持つ経路を実用的な処理時間で選択する近似アルゴリズムを提案する. |
| 抄録（英） | It is significant to utilize network resources efficiently by selecting a route that satisfies multiple Quality of Services (QoSs) ; bandwidth, delay, error ratio, and so on, when providing multimedia services. Existing routing algorithms for the above have the following defects ; 1) selected routes depend on users′ experience, 2) their approximation ratios that represent the accuracy of approximation (the maximum value of the cost of the selected route to the one of an optimal route) are constants depending on network configuration, and 3) they do not necessarily select any routes even though there is a feasible route. This paper proposes a new and practical approximation algorithm for multiple QoSs that takes an arbitrary approximation ratio, (1+ε), and selects a route, the cost of which is at most (1+ε) times as much as the one of the optimal route. |
| 収録資料名（和） | 電子情報通信学会技術研究報告 |
| 収録資料の巻号 | Vol.97 No.293 |
| ページ開始 | 81 |
| ページ終了 | 86 |
| キーワード（和） | 近似アルゴリズム |
| キーワード（英） | approximation algorithm |
| 本文の言語 | JPN |
| 著者（和） | 小花貞夫 |
| 著者（ヨミ） | オバナサダオ |
| 著者（英） | Obana Sadao |
| 所属機関（和） | KDD |
| 所属機関（英） | KDD |
| 著者（和） | 杉山敬三 |
| 著者（ヨミ） | スギヤマケイゾウ |
| 著者（英） | Sugiyama Keizo |
| 所属機関（和） | KDD |
| 所属機関（英） | KDD |
| 著者（和） | 堀内浩規 |
| 著者（ヨミ） | ホリウチヒロキ |
| 著者（英） | Horiuchi Hiroki |
| 所属機関（和） | KDD |
| 所属機関（英） | KDD |
| 著者（和） | 吉原貴仁 |
| 著者（ヨミ） | ヨシハラキヨヒト |
| 著者（英） | Yoshihara Kiyohito |
| 所属機関（和） | KDD |
| 所属機関（英） | KDD |