ルーターの性能を2倍に向上、ロチェスター工科大：IPルックアップを高速化

ロチェスター工科大学の研究チームが、ルックアップ時間を大幅に短縮し、ルーターのパフォーマンスを2倍以上に高めるプログラマブルスイッチ「CuVPP」を開発した。ベクトルパケット処理とカッコウフィルターを採用することで実現した。

[＠IT]

　ロチェスター工科大学は2020年11月19日（米国時間）、ルックアップ時間の大幅な短縮により、ルーターのパフォーマンスを2倍以上に高める新しいプログラマブルスイッチ「CuVPP」を開発したことを発表した。

　パフォーマンス向上のために2つの技術を採用した。第1はアルゴリズムだ。新しい最長フレフィックス一致（Longest Prefix Matching）アルゴリズムでは、ベクトルパケット処理（VPP）を利用して、命令とデータの両方にパケットバッチ処理とキャッシュローカリティを使用した。この結果、オフチップメモリへのルックアップ回数を最小限に抑えることができたため、ルックアップ時間を大幅に短縮できた。

　第2がフィルターだ。高速プリスクリーニングメカニズムとして、キャッシュ内にカッコウフィルター（Cuckoo Filter）を使用した。

　研究チームによると、CuVPPは実トラフィックでルックアップを毎秒450万回実行できるという。これは他の一般的な手法を上回る速度だ。

ロチェスター工科大学の研究チームが開発したプログラマブルスイッチ「CuVPP」は、ベクトルパケット処理（VPP）やカッコウフィルターを利用して、IPルックアップを高速化する（出典：ロチェスター工科大学）

ソフトウェアルーターに何が求められているのか

　研究チームは、プログラマブルソフトウェアルーターの処理時間の改善を目的に、研究を開始した。同ルーターは、ハードウェアルーターよりも柔軟なスケーリングが可能だが、今のところあまり高速ではなかったからだ。

　「ネットワークスイッチのプログラマビリティは、重要性を増している。仮想化がネットワーキングに導入され、SDN（ソフトウェア定義型ネットワーキング）の利用が進んでいるからだ。だが、ネットワーク速度が向上し、ルーティングテーブルサイズがますます拡大していることを考えると、コモディティハードウェア上のプログラマブルネットワークスイッチの性能（が期待よりも高くないこと）は、大きな問題だ」と、研究をリードしたロチェスター工科大学のコンピュータサイエンス教授、ミンソク・クォン氏は説明する。

　インターネットユーザーがWebサイトを訪問する際に、ルーターは効率的に宛先IPアドレスをルックアップ処理して、データパケットを転送できなければならない。ルックアップの課題はこれまで幅広く研究されてきた。ルックアップは計算コストが高く、タイムリー性が要求されるプロセスだからだ。IPアドレスを探す時間を短縮するために、研究チームはカッコウフィルター技術の採用を決めた。

　「われわれのスイッチは、高速でサイズが小さなキャッシュメモリでフィルター処理ができる。この手法を実現するには、テーブル全体を検索するのではなく、IPアドレスを事前にスクリーニングする。フィルターが小さい場合でも他に悪影響を与えないようにするため、従来のアルゴリズムを変更する必要がある」（クォン氏）

他の3種類の手法と性能を比較

　研究チームは、運用中のルーターのIPv6プレフィックスを使って、80Gbpsのネットワークで接続されたサーバを用いた実ネットワークトラフィックでCuVPPを評価した。現在一般に利用されている3種類の手法との比較だ。

　その結果、CuVPPはルックアップ速度を、ベースVPPの使用時よりも最大24％向上できた。VPPとブルームフィルターを組み合わせた場合に対しては最大51％、VPPとトライ木（Trie）の使用時よりも最大128％向上できた。

　ルーティングテーブルのサイズを200万プレフィックスまで拡大した場合でもスケーラブルな性能を発揮できた。

さまざまなルーティングテーブルサイズでのルックアップ速度の比較　CuVPP（黒）はルーティングテーブルのサイズが変化しても常に性能が高い（出典：ロチェスター工科大学）

　Cisco Systemsのディスティングイッシュトエンジニアで、研究チームの一員であるジョン・マーシャル氏（ロチェスター工科大学を1989年に卒業）は次のように述べる。「インターネットが成長を続ける中、IPv6の効率を高める技術が必要になっている。今回のアルゴリズム技術は、ソフトウェアルーターのパケット転送性能を著しく向上させる」

　研究チームはCuVPPについてまとめた論文で、クラスタコンピューティングの国際カンファレンス「IEEE Cluster 2020」で最優秀論文賞を受賞した。

　CuVPPはオープンソースプロトタイプであり、研究チームはこの技術が将来、IPルックアップの一翼を担うことを期待している。