講演抄録/キーワード |
講演名 |
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 |