Performance Evaluation of SpliTable: the Distributed BGP Routing Tables

摘要

The Internet is now facing a scalability issue due to its rapid growth. We have previously proposed SpliTable, a scalable way to support the Internet routes in a Service Provider network. In our proposal, BGP route selection is done by dis­tributed servers on behalf of the routers. The selected routes are then stored in distributed routing tables. Each router maintains only its share of Internet routes, not the routes for each prefix as it is the case today. This paper focuses on the performance evaluation of SpliTable. Prototype of route selection servers and ASBRs are implemented upon virtual machines in order to emulate a real SP network. We show the performance evaluation results in terms of table size reduction of the routers, number of DHT messages and the time required for the retrieval of the route in case it was not found in the cache.%近年，インターネットを構成するルータが保持すべきBGPの経路テーブルの量，及び処理すべきBGPメッセージの量が指数関数的に増大しており，経路収束の遅延による可用性の低下やISPによる設備更改コストの増加を引き起こす懸念から，インターネットのスケーラビリティを脅かす要因の1つと考えられている．筆者らは，分散ルートサーバの導入による経路計算処理の分散化と，DHT技術の活用による経路管理の分散化を行うことで，各ルータの経路制御処理負荷と保持すべき経路数の軽減を達成する経路制御アーキテクチャを提案している．提案技術はルータの保持経路数を大幅に削減できる効果が見込める一方，経路情報をルータ間で分散して保持しているため，転送すべきパケットの到着時に自ルータにキャッシュがない場合に他のルータから取得する時間が必要となることが課題であった．本稿ではプロトタイプによる提案方式の性能評価について報告する．性能評価では，複数の仮想マシン上に本提案方式を実装したソフトウェアルータを搭載することで1つのASを構築し，提案方式の効果や実用性について検証を行った．既存方式に比べて経路保持量が大幅に削減可能であることと，パケット到着時の経路情報取得処理が数ミリ秒程度で完了することを確認した．