2.7. 関連研究
また，HACの入力部にシフタを組み合わせ，個別の宛先アドレス毎ではなく，ある程度の宛先 アドレスレンジをまとめて格納する格納するHARC (Host Address Range Cache)，更にプログラマ ブルハッシュエンジンも組み合わせたIHARC (Intelligen HARC)を利用することで，更なるヒッ ト率改善が望めるとしている[52]．
2.7.2 Routing Lookups in Hardware at Memory Access Speeds
米国スタンフォード 大学のGuptaらは，ルータ装置のボトルネックの原因としてCIDRによるIP ルーティングで利用されている最長一致検索(LPM: Longest Prefix Match)のメカニズムを指摘し ， 解決策として，メモリをパイプライン状に配置し メモリアクセス毎に経路検索を可能とするアル ゴ リズムを提案した[53]．図2.17に，Guptaらが提案した経路検索アルゴ リズムDIR-24-8-BASIC
の構造を示す．
図2.17: DIR-24-8-BASICアーキテクチャ
DIR-24-8-BASICでは，TBL24と呼ぶ第一のテーブルとTBLlongと呼ぶ第二の2種類のテーブ ルを共にDRAMに格納する．TBL24は，224エントリを備え，プレフィックス長が24bit以下の IPv4の全経路情報を収める．各エントリには1bitの識別子と15bitの結果を収める．結果の15bit は，識別子が0の場合，次ホップ 情報を示し ，識別子が1の場合，TBLlongへのポインタを示す．
TBLlongは，プレフィックス長が24bitより大きいIPv4の全経路情報を収める．この2種類のテー ブルを利用して，次のように次ホップの経路を決定する．まず，IPv4アドレスの上位24bitを利用
してTBL24をアクセスする．プレフィックス長が24以下ならば，TBL24から読みだした値が次
ホップの経路である．プレフィックス長が25以上であればTBL24から読みだした15bitの結果と 元のIPv4アドレスの下位8bitを結合した23bitでTBLlongをアクセスし次ホップの経路を決定す る．ネットワークトラフィックの局所性(特にプレフィックス長の分布に関する空間的局所性)によ り，多くの場合，プレフィックス長は24以下であることが期待できるので1回のメモリ参照で経 路を決定することができる．また，DRAMを利用し ，メモリアクセス速度を50nsとすると，プ レフィックス長が24以下の場合は，20×106回の経路検索(＝20Mpps: Mega packet per second)が 可能であるとしている．
しかしながら，この手法は論文中での指摘もあるように，TBL24やTBLlongの更新が問題とな る．例えば ，プレフィックス長が8bitに対応するエントリはTBL24上に216エントリも存在する ため，このエントリ全てを更新することは著しい性能低下を引き起こす．
2.7. 関連研究
2.7.3 IP Caching for Terabit Speed Routers
カリフォルニア大学サンディエゴ 校のBryan Talbotらは，ネットワーク上では宛先IPアドレス が同じパケットが短時間に繰り返し出現しやすいという時間的局所性を指摘し，IPアドレスキャッ シュを利用して経路検索を高速化する手法を提案した[54]．
IPアドレスキャッシュの特徴は二つあり，一つ目はIPv4アドレスを二分割してインデックスと タグとして利用することである．二つ目は，キャッシュラインサイズが1Byte (1エントリ)という ことである．ネットワークを次々と流れるあるパケットのネクストホップ 情報に対して，次のパ ケットのネクストホップ情報が直接関係を持つことは無い，すなわち空間的局所性が存在しない ため，キャッシュラインに複数のネクストホップ情報を格納しても意味がないため，キャッシュラ インには1個の結果だけしか入れる必要がないとしている．通常のプロセッサのキャッシュ同様，
インデックスでキャッシュメモリにアクセスし ，該当エントリのタグとIPv4アドレス内のタグを 比較して一致すればキャッシュヒットとなる．9個のサイトから採取した実ネットワークトレース を利用した調査の結果，図2.18に示すように，IPv4アドレ スの上位をタグ，下位をインデックス とするのが良いことを示した．また，キャッシュエントリ数を4K〜256Kに変化させ，ダ イレ ク トマップ方式，2ウェイと4ウェイのセットアソシアティブ方式のキャッシュ構成を調査したとこ ろ，4ウェイ・セットアソシアティブ方式であれば ，4Kエントリのキャッシュで91%以上のヒッ ト率に達していることを示した．
図2.18:キャッシュのイメージ
DRAMを利用した経路検索では，スタンフォード 大学のGuptaらの手法[53]を用いてもDRAM のサイクルタイム(ここでは55ns)間隔でしか結果が出ない．しかしながら，4Kエントリ，2ウェ イ，2nsサイクルタイム，1nsレ イテンシのL1キャッシュをDRAMと組み合わせて利用すると最 悪ケースのサイトでも11.11ns間隔に改善できることを示した．また，1Mエント リ，4ウェイ，
2nsサイクルタイム，10nsレ イテンシのL2キャッシュも組み合わせると最悪ケースのサイトで
も3.45ns間隔に改善できることを示した．以上から，ネットワークの時間的局所性を利用したIP
キャッシュにより，4ns以下，すなわち250Mppsの経路検索性能を得られるため，Ethernetの平均 パケット長(約500Byte)を仮定すると半二重1Tbpsの処理速度を達成できるとした．
2.7. 関連研究
2.7.4 Multi-zone Caches for Accelerating IP Routing Table Lookups
アルバータ大学のChvetsらは，IPトラフィックに存在する局所性について考察を行ない，プレ フィックス長によって複数の領域に分割したキャッシュ(マルチゾーンキャッシュ)によってキャッ シュヒット率(＝経路検索性能)を向上させる手法を提案した[55]．
Chvetsらは，ネットワークの局所性として時間的局所性と空間的局所性を指摘している．時間
的局所性とは，短時間に同一の宛先アドレスが繰り返し 出現しやすい現象を指し ，これは，通信 トラフィックが，パケットの連なりとしてネットワークを通過するために存在するとしている．ま た，空間的局所性とは，同一レンジの宛先アドレス参照が出現しやすい現象を指し，これは，ネッ トワークアドレス(プレフィックス，アドレスの上位部分)が同じでホストアドレス(アドレスの下 位部分)が異なるIPアドレスが同一のサブネットに属しているため，サブネット内のあるアドレ スがアクセスされれば ，同一サブネット内の別のアドレ スもアクセスされやすいために存在して いるとしている．そして，2種類のサイトのトレースを調査し ，250ms以内に約80%のパケット で以前に出現した宛先アドレスが再参照されるという強い時間的局所性と，約95%の宛先アドレ ス参照はプレフィックス長が11bitから24bitの間という，アドレス空間全体の44%に存在してい るという強い空間的局所性を確認した．
そして，時間的局所性と空間的局所性の両方を効率的に利用するために，キャッシュエントリの 大半をゾーン1としてネットワークアドレスのうち頻繁に出現しやすいものに，残りのキャッシュ エントリをゾ ーン2としてそれ以外のネットワークアドレ ス用に割り当てるマルチゾーンキャッ シュを提案した．図2.19にマルチゾーンキャッシュのエントリ割合イメージを示す．
図2.19:マルチゾーンキャッシュのエントリ割合イメージ
マルチゾーンキャッシュでは，指定したプレフィックス長以下のエントリはゾーン1に，それ以 外はゾーン2に記録する．尚，キャッシュの各エントリは，10bitの出力ポート識別子とプレフィッ クス(プレフィックス長に依存)を格納するものとしている．マルチゾーンキャッシュの効力を確認 するために，プレフィックス長を18，20，22bitとして，2種類のゾーンを作った場合と，1種類 のゾーンだけの通常のキャッシュとを比較した．いずれのプレフィックス長でもゾーン1とゾーン 2の最適な割り合いは異なるものの，適切なゾーン分割を行なうと通常のキャッシュよりもキャッ シュミス率を約半分程度にできるという結果を得ている．また，Kasnaviらはマルチゾーンキャッ シュをパイプライン化して高速化する研究を行なっている[56]．