| 講演名 | 2001/6/18 光ネットワーク上のオンラインマルチキャスティング 橋本 堅太, 山田 敏規, 上野 修一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 小文では波長分割多重方式光ネットワーク上のマルチキャストと呼ばれる特別な通信要求に対するルーティングについて考察する. マルチキャストとはある固定された送信元と受信先の多重集合からなる通信要求である. まず, マルチキャストを実現するために必要となる波長数の最小値がネットワーク中のカットを横切る通信経路の数の平均の最大値と等しいという最大最小定理を示す. 次に, この定理に基づいたオンラインアルゴリズムを提案し, このアルゴリズムの競合比が送信元の次数とネットワークの辺連結度の比に等しいということを示す. さらに, 4/3がンラインアルゴリズムの競合比の下界であることを示す. |
| 抄録(英) | We consider the routing for a special type of communication requests, called a multicast, consisting of a fixed source and a multiset of destinations in a wavelength division multiplexing all optical network. We prove a min-max equality that the minimum number of wavelengths necessary for routing a multicast is equal to the maximum of the average number of paths that share a link in a cut of the network. Based on the min-max equality above, we propose an on-line algorithm for routing a multicast, and show that the competitive ratio of our algorithm is equal to the ratio of the degree of the source to the link connectivity of the network. We also show that 4/3 is a lower bound for the competitive ratio of an on-line algorithm for routing a multicast. |
| キーワード(和) | 光ネットワーク / 波長分割多重方式 / マルチキャスト / オンラインアルゴリズム / 競合比 |
| キーワード(英) | all-optical network / wavelength division multiplexing / multicast / on-line algorithm / competitive ratio |
| 資料番号 | COMP2001-20 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/6/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 光ネットワーク上のオンラインマルチキャスティング |
| サブタイトル（和） | |
| タイトル（英） | On-Line Multicasting in All-Optical Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 光ネットワーク / all-optical network |
| キーワード(2)（和/英） | 波長分割多重方式 / wavelength division multiplexing |
| キーワード(3)（和/英） | マルチキャスト / multicast |
| キーワード(4)（和/英） | オンラインアルゴリズム / on-line algorithm |
| キーワード(5)（和/英） | 競合比 / competitive ratio |
| 第 1 著者 氏名（和/英） | 橋本 堅太 / Kenta Hashimoto |
| 第 1 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Dept. of Communications and Integrated Systems Graduate School of Science and Engineering, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 山田 敏規 / Toshinori Yamada |
| 第 2 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Dept. of Communications and Integrated Systems Graduate School of Science and Engineering, Tokyo Institute of Technology |
| 第 3 著者 氏名（和/英） | 上野 修一 / Shuichi Ueno |
| 第 3 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Dept. of Communications and Integrated Systems Graduate School of Science and Engineering, Tokyo Institute of Technology |
| 発表年月日 | 2001/6/18 |
| 資料番号 | COMP2001-20 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 133 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |