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

摘要

現行のEGPは各ルータがAS数Nに対してO（N）という数の経路情報を維持管理する必要がある．そのため，ルータが経路情報を管理しきれずに異常動作を起こす経路爆発という問題が存在する．我々は，ルータが管理する経路情報数を，その計算量から低減する手法を提案する．具体的には，構造化オーバレイネットワークの手法をEGPに導入する．インターネットのスケールフリー性を仮定すると，現行のO（N）に対して，到達性を保証しただけの現時点だとO（log N）に削減することができるが，経路長がO（N log N）となる．しかし，経路情報数をO（(logN)~2）にすることにより経路長もO（(logN)~2）にすることが可能である．更に今後の最適化で経路長O（log N）を目指す．