| 講演名 | 1998/5/28 Fallback+:複数のQoS要求を満たす経路選択アルゴリズム 谷岡 秀昭, 木下 和彦, 滝根 哲哉, 村上 孝三, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | マルチサービスネットワークにおいて、帯域や遅延など複数のQoS要求を満たす経路選択アルゴリズムが必要となる。これは複数制約下での最短路問題として定式化できるが、NP完全であることが知られている。それゆえ多くの発見的アルゴリズムが提案されたが、その中で代表的なものにFallbackアルゴリズムがある。これは、個々のQoSを目的関数とする最短路問題を遂次的に解き、解が全てのQoS要求を満たせば、経路として採用するというものである。本稿では、このFallbackアルゴリズムを拡張し、QoS要求を満たしつつ、ネットワーク側の視点から最も低コストな経路を選択する発見的アルゴリズムFallback+を提案する。これは、コストあるいは個々のQoSに対する最短経路を得る過程で、暫定解として生成される経路を廃棄せず、Fallbackする前に別候補として検討するものである。Fallback+の最大計算量はFallbackと等しいが、Fallback+はより高い確率でQoS要求を満たす経路を選択可能である。更に、シミュレーションの結果から、Fallback+の実行速度は平均的には単純なFallbackより10%以上高速であり、また、最適な経路を選択する確率も高いことを示した。 |
| 抄録(英) | QoS(quality-of-service) routing is an essential element in multi-service networks to support diverse applications which have stringent QoS requirements such as bandwidth, delay and error ratio. QoS routing can be formulated as a shortest path problem subject to multiple constraints. Note that it is NP-complete. In this paper, we propose a new routing algorithm Fallback+. The basic idea in Fallback+ is to utilize all information produced in the conventional Fallback routing with Dijkstra's algorithm. In Dijkstra's algorithm, it is likely to produce tentative routes from a source to a destination before determining the shortest route. Fallback+ stores them as candidates, and checks them before fallback. Therefore, Fallback+ can find a feasible route with the higher probability. And the computational complexity of Fallback+ is the same as the conventional Fallback routing. Moreover, we perform simulation experiments, and compared with the conventional Fallback routing, we confirm that the CPU time of Fallback+ is the shorter and that the probability to find the optimal route is the higher. |
| キーワード(和) | マルチサービスネットワーク / 最短路問題 / Fallback / Dijkstraのアルゴリズム / QoS保証 |
| キーワード(英) | multi-service network / shortest path problem / Fallback algorithm / Dijkstra's algorithm / QoS guarantee |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | SSE |
|---|---|
| 開催期間 | 1998/5/28(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Switching Systems Engineering (SSE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Fallback+:複数のQoS要求を満たす経路選択アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Fallback+: A Routing Algorithm Subject to Multiple QoS Constraints |
| サブタイトル（和） | |
| キーワード(1)（和/英） | マルチサービスネットワーク / multi-service network |
| キーワード(2)（和/英） | 最短路問題 / shortest path problem |
| キーワード(3)（和/英） | Fallback / Fallback algorithm |
| キーワード(4)（和/英） | Dijkstraのアルゴリズム / Dijkstra's algorithm |
| キーワード(5)（和/英） | QoS保証 / QoS guarantee |
| 第 1 著者 氏名（和/英） | 谷岡 秀昭 / Hideaki Tanioka |
| 第 1 著者 所属（和/英） | 大阪大学工学部情報システム工学科 Department of Infomation Systems Engineering, Faculty of Engeering, Osaka University |
| 第 2 著者 氏名（和/英） | 木下 和彦 / Kazuhiko Kinoshita |
| 第 2 著者 所属（和/英） | 大阪大学大学院工学研究科情報システム工学専攻 Department of Infomation Systems Engineering, Graduate School of Engineering, Osaka University |
| 第 3 著者 氏名（和/英） | 滝根 哲哉 / Tetsuya Takine |
| 第 3 著者 所属（和/英） | 京都大学大学院情報学研究科数理工学専攻 Department of Applied Mathmatics and Physics Graduate School of Informatics, Kyoto University |
| 第 4 著者 氏名（和/英） | 村上 孝三 / Koso Murakami |
| 第 4 著者 所属（和/英） | 大阪大学大学院工学研究科情報システム工学専攻 Department of Infomation Systems Engineering, Graduate School of Engineering, Osaka University |
| 発表年月日 | 1998/5/28 |
| 資料番号 | |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 83 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |