スケーラブルな広域ルーティングに向けた到達性保証手法

摘要

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(logiV) 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 0(log2 N) routing information. Furthermore, our target is O(log N) as same as today's EGP.%現行の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）を目指す.