| 講演名 | 2012-03-09 スケーラブルな広域ルーティングに向けた到達性保証手法(経路制御) 島村 祥平, 長尾 洋也, 宮尾 武裕, 首藤 一幸, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 現行のEGPは各ルータがAS数Nに対してO(N)という数の経路情報を維持管理する必要がある.そのため,ルータが経路情報を管理しきれずに異常動作を起こす経路爆発という問題が存在する.我々は,ルータが管理する経路情報数を,その計算量から低減する手法を提案する.具体的には,構造化オーバレイネットワークの手法をEGPに導入する.インターネットのスケールフリー性を仮定すると,現行のO(N)に対して,到達性を保証しただけの現時点だとO(logN)に削減することができるが,経路長がO(NlogN)となる.しかし,経路情報数をO(log^2N)にすることにより経路長もO(log^2N)にすることが可能である.更に今後の最適化で経路長O(logN)を目指す. |
| 抄録(英) | Today's EGPs are necessary that each router maintains routing information of O(N) against N ASes. It is the source of the problem of Routes Explosion in which routers run into abnormal operation due to memory overflow. This paper shows a method to reduce the amount of routing information. The method reduces space complexity by introducing the ideas of structured overlay network into EGP. Assuming that Internet is a scale-free network, the complexity is reduced from today's O(N) to O(logN) in the current results, but path length is O(NlogN). However, it is possible path length reduce to O(log^2N) with O(log^2N) routing information. Furthermore, our target is O(log N) as same as today's EGP. |
| キーワード(和) | インターネット / ルーティングプロトコル / 構造化オーバレイネットワーク |
| キーワード(英) | Internet / routing protocol / structured overlay network |
| 資料番号 | IN2011-170 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IN |
|---|---|
| 開催期間 | 2012/3/1(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Networks (IN) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | スケーラブルな広域ルーティングに向けた到達性保証手法(経路制御) |
| サブタイトル（和） | |
| タイトル（英） | A Reachability Ensuring Technique for A Scalable Wide-Area Routing Method |
| サブタイトル（和） | |
| キーワード(1)（和/英） | インターネット / Internet |
| キーワード(2)（和/英） | ルーティングプロトコル / routing protocol |
| キーワード(3)（和/英） | 構造化オーバレイネットワーク / structured overlay network |
| 第 1 著者 氏名（和/英） | 島村 祥平 / Shohei SHIMAMURA |
| 第 1 著者 所属（和/英） | 東京工業大学大学院情報理工学研究科数理・計算科学専攻 Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 長尾 洋也 / Hiroya NAGAO |
| 第 2 著者 所属（和/英） | 東京工業大学大学院情報理工学研究科数理・計算科学専攻 Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| 第 3 著者 氏名（和/英） | 宮尾 武裕 / Takehiro MIYAO |
| 第 3 著者 所属（和/英） | 東京工業大学大学院情報理工学研究科数理・計算科学専攻 Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| 第 4 著者 氏名（和/英） | 首藤 一幸 / Kazuyuki SHUDO |
| 第 4 著者 所属（和/英） | 東京工業大学大学院情報理工学研究科数理・計算科学専攻 Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| 発表年月日 | 2012-03-09 |
| 資料番号 | IN2011-170 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 469 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |