| 講演名 | 1997/9/29 複数QoSに基づく近似精度可変な経路選択アルゴリズム 吉原 貴仁, 堀内 浩規, 杉山 敬三, 小花 貞夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | マルチメディアの通信サービスを提供する際には, 要求された通信路の帯域幅, 伝送遅延および誤り率等の複数のサービス品質 (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. |
| キーワード(和) | Quality of Service / 経路選択 / 近似比率 / 近似アルゴリズム |
| キーワード(英) | Quality of Service / routing / approximation ratio / approximation algorithm |
| 資料番号 | CS97-80 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CS |
|---|---|
| 開催期間 | 1997/9/29(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Communication Systems (CS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 複数QoSに基づく近似精度可変な経路選択アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Routing Algorithm for Multiple QoS Requirements with Arbitrary Approximation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Quality of Service / Quality of Service |
| キーワード(2)（和/英） | 経路選択 / routing |
| キーワード(3)（和/英） | 近似比率 / approximation ratio |
| キーワード(4)（和/英） | 近似アルゴリズム / approximation algorithm |
| 第 1 著者 氏名（和/英） | 吉原 貴仁 / Kiyohito YOSHIHARA |
| 第 1 著者 所属（和/英） | 国際電信電話株式会社 研究所 KDD R & D Laboratories |
| 第 2 著者 氏名（和/英） | 堀内 浩規 / Hiroki HORIUCHI |
| 第 2 著者 所属（和/英） | 国際電信電話株式会社 研究所 KDD R & D Laboratories |
| 第 3 著者 氏名（和/英） | 杉山 敬三 / Keizo SUGIYAMA |
| 第 3 著者 所属（和/英） | 国際電信電話株式会社 研究所 KDD R & D Laboratories |
| 第 4 著者 氏名（和/英） | 小花 貞夫 / Sadao OBANA |
| 第 4 著者 所属（和/英） | 国際電信電話株式会社 研究所 KDD R & D Laboratories |
| 発表年月日 | 1997/9/29 |
| 資料番号 | CS97-80 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 297 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |