高品質エンド間通信のための高速エッジルータの開発

本研究では、高速なパケット識別を可能とするルータを実現するための、識別アルゴリズムについて検討してきた。本年度は、前年度提案を行った、パケット識別を高速化するためのビット選択手法について、その有効性の検証、および性能改善のための新しいアルゴリズムの開発に重点をおいて研究を行ってきた。まず、平均探索時間を減少させる方法として、ビット位置ごとにルーティングテーブルのエントリ性質にもとづく指標を与え、その指標が大きい者から順に選択する手法を用いた。指標に用いた式として、エントリのビット位置における 0,1,*(Don't care)の値のエントリ数やその最大値、最小値を組み合わせた方法を複数用意し、それぞれに対して探索時間分布を求めて評価した結果、指定されたビット位置の値が0のエントリ数と1のエントリ数の差分と*のエントリ数の組み合わせた評価基準がもっとも平均探索時間を減少できたことを明らかにした。次に、さらなる性能向上の方法として、トラヒック特性をビット選択指標に反映させる方法についても考えた。これまではトラヒックの宛先アドレスを一様に分布させた評価のみを行っていたが、実際は宛先アドレスの分布は大きな偏りがあることが知られている。したがって、よりアクセス頻度の高いエントリのビット値に高い重みを与えて指標を作成することで、それらのビット位置が優先的に選択されて、アクセス頻度の高いエントリが短い探索時間で検索できるようになる。一般に公開されている8カ所のルーティングテーブルをもとに改善されたビット選択手法を導入した結果、すべての場合においてトラヒック特性を考慮することでさらなる探索時間の短縮が可能であり、最大40%程度高速化できることが可能であることがわかった。

本研究では、高速なパケット識別を可能とするルータを実現するための、識別アルゴリズムについて検討してきた。本年度は、前年度提案を行った、パケット識別を高速化するためのビット選択手法について、その有効性の検証、および性能改善のための新しいアルゴリズムの開発に重点をおいて研究を行ってきた。まず、平均探索時間を減少させる方法として、ビット位置ごとにルーティングテーブルのエントリ性質にもとづく指標を与え、その指標が大きい者から順に選択する手法を用いた。指標に用いた式として、エントリのビット位置における 0,1,*(Don't care)の値のエントリ数やその最大値、最小値を組み合わせた方法を複数用意し、それぞれに対して探索時間分布を求めて評価した結果、指定されたビット位置の値が0のエントリ数と1のエントリ数の差分と*のエントリ数の組み合わせた評価基準がもっとも平均探索時間を減少できたことを明らかにした。次に、さらなる性能向上の方法として、トラヒック特性をビット選択指標に反映させる方法についても考えた。これまではトラヒックの宛先アドレスを一様に分布させた評価のみを行っていたが、実際は宛先アドレスの分布は大きな偏りがあることが知られている。したがって、よりアクセス頻度の高いエントリのビット値に高い重みを与えて指標を作成することで、それらのビット位置が優先的に選択されて、アクセス頻度の高いエントリが短い探索時間で検索できるようになる。一般に公開されている8カ所のルーティングテーブルをもとに改善されたビット選択手法を導入した結果、すべての場合においてトラヒック特性を考慮することでさらなる探索時間の短縮が可能であり、最大40%程度高速化できることが可能であることがわかった。