表題番号：2013A-872 日付：2014/04/11
研究課題超高速ネットワークの詳細モニタリングに向けた確率的ハッシュテーブル
研究者所属（当時） 資格 氏名
（代表者） 理工学術院 准教授 森　達哉
研究成果概要
【研究目的の概要】
テラビット級の超高速ネットワークでリアルタイムに詳細な観測を行うための基礎および応用技術を研究する．リアルタイムなネットワーク観測ではアドレスや名前，観測時刻などの膨大な変数間の対応関係を高速に記憶・参照することが求められる．一方で必ずしも まったく誤りのない完全な観測結果までは求められない．この点に注目し，わずかな誤りを許容することで記憶容量を大幅に圧縮し，高速化を図る確率的連想配列の研究に取り組む．またこの基礎技術を用いた具体的なアプリケーションを開発する．

【成果の概要】
2013年度は確率的ハッシュテーブル（連想配列）を実現するデータ構造とアルゴリズムの検討およびそのような確率的連想配列を利用した具体的なアプリケーションとして，個々の通信フローに対して，DNSクエリを参照・解析し，対応するサービス名を付与する方式(SFMap)を検討した．SFMap の用途は暗号化されたことにより，中身が不明な通信フローに対し，DNS クエリ・応答に組を解析することでその通信サービスを推定することであり，通信事業者が自社のネットワークの利用状況を把握するのに有用である．
確率的連想配列に関しては2つの Bloom Filter を組み合わせて Matrix を構成する方式(Matfix Filter=MF)を確立した．理論および数値計算による性能評価を行った結果，MF は既存方式と比較して良好な性能を得られることを確認した．具体的には所与のエラー率が与えられた下で {key, value} のタプルを連想配列に入力する際に，極力メモリ消費量を低減しつつも高速にデータの登録・参照が可能な方式である．特に key 数が膨大であり，value 数が比較的小さいようなケースにおいて既存方式に対して有利な性能を有する特徴がある．SFMap に関しては実通信データを用いた精度評価を行い，こちらも良好な性能が得られることを確認した．SFMap については JST ERATO の井上武氏と共著で国内学会で発表を行った他，実通信データを読み込んで所望の処理を実現するソフトウェアを開発した．

【今後の予定】
基礎的な方式および具体的なアプリケーションの良好な動作が確認できたので，2014年度は MF および SFMap の検討で得られた成果をまとめ，フルペーパーとして論文投稿する予定である．方式を実装したソフトウェアをオープンソースソフトウェアとして広く公開することも検討している．また，本研究は科研費スタート支援の補助を受けており，2014年度も継続する予定である．さらに本成果に基づいた民間企業との共同研究を実施する予定である．