お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2012-03-09 10:10
スケーラブルな広域ルーティングに向けた到達性保証手法
島村祥平長尾洋也宮尾武裕首藤一幸東工大IN2011-170
抄録 (和) 現行のEGPは各ルータがAS数$N$に対して$O(N)$という数の経路情報を維持管理する必要がある.
そのため,ルータが経路情報を管理しきれずに異常動作を起こす経路爆発という問題が存在する.
我々は,ルータが管理する経路情報数を,その計算量から低減する手法を提案する.具体的には,構造化オーバレイネットワークの手法をEGPに導入する.インターネットのスケールフリー性を仮定すると,現行の$O(N)$に対して,到達性を保証しただけの現時点だと$O(\log N)$に削減することができるが,経路長が$O(N \log N)$となる.しかし,経路情報数を$O(\log^2 N)$にすることにより経路長も$O(\log^2 N)$にすることが可能である.更に今後の最適化で経路長$O(\log N)$を目指す. 
(英) 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(\log N)$ in the current results, but path length is $O(N \log N)$.
However, it is possible path length reduce to $O(\log^2 N)$ with $O(\log^2 N)$ routing information. Furthermore, our target is $O(\log N)$ as same as today's EGP.
キーワード (和) インターネット / ルーティングプロトコル / 構造化オーバレイネットワーク / / / / /  
(英) Internet / routing protocol / structured overlay network / / / / /  
文献情報 信学技報, vol. 111, no. 469, IN2011-170, pp. 199-204, 2012年3月.
資料番号 IN2011-170 
発行日 2012-03-01 (IN) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード IN2011-170

研究会情報
研究会 NS IN  
開催期間 2012-03-08 - 2012-03-09 
開催地(和) 宮崎シーガイア 
開催地(英) Miyazaki Seagia 
テーマ(和) 一般 
テーマ(英) General 
講演論文情報の詳細
申込み研究会 IN 
会議コード 2012-03-NS-IN 
本文の言語 日本語 
タイトル(和) スケーラブルな広域ルーティングに向けた到達性保証手法 
サブタイトル(和)  
タイトル(英) A Reachability Ensuring Technique for A Scalable Wide-Area Routing Method 
サブタイトル(英)  
キーワード(1)(和/英) インターネット / Internet  
キーワード(2)(和/英) ルーティングプロトコル / routing protocol  
キーワード(3)(和/英) 構造化オーバレイネットワーク / structured overlay network  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 島村 祥平 / Shohei Shimamura / シマムラ ショウヘイ
第1著者 所属(和/英) 東京工業大学 (略称: 東工大)
Tokyo Institute of Technology (略称: Tokyo Tech)
第2著者 氏名(和/英/ヨミ) 長尾 洋也 / Hiroya Nagao / ナガオ ヒロヤ
第2著者 所属(和/英) 東京工業大学 (略称: 東工大)
Tokyo Institute of Technology (略称: Tokyo Tech)
第3著者 氏名(和/英/ヨミ) 宮尾 武裕 / Takehiro Miyao / ミヤオ タケヒロ
第3著者 所属(和/英) 東京工業大学 (略称: 東工大)
Tokyo Institute of Technology (略称: Tokyo Tech)
第4著者 氏名(和/英/ヨミ) 首藤 一幸 / Kazuyuki Shudo / シュドウ カズユキ
第4著者 所属(和/英) 東京工業大学 (略称: 東工大)
Tokyo Institute of Technology (略称: Tokyo Tech)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2012-03-09 10:10:00 
発表時間 20 
申込先研究会 IN 
資料番号 IEICE-IN2011-170 
巻番号(vol) IEICE-111 
号番号(no) no.469 
ページ範囲 pp.199-204 
ページ数 IEICE-6 
発行日 IEICE-IN-2012-03-01 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会