Internet広域分散協調サーチロボット の研究開発 早稲田大学 村岡洋一

概要 Jpドメインのみでもデータを集めきるのに1ヶ月以上かかる 24時間以内にjpドメインのデータを集めきることを目的とする研究の報告書 7個所に分散されたプロトタイプで103のWWWサーバーを対象に収集実験を行い、有効性を確認 ランダムな分散をした場合で2.6から10.6倍、負荷均一化を行なうと5.5から22倍の高速化が可能であることを確認　

はじめに Internet広域分散協調サーチロボットの研究 期待される成果 WWWロボットをネットワーク上に分散して複数配置 分散したロボットが担当するサーバーを自動的に決定させ、かつ協調動作させる 期待される成果 24時間以内に収集可能 最新データによる質の高い検索 国レベルおよび世界レベルでの協調収集した場合、ロボットによる負荷を大幅に削減可能

WWWロボットの問題 検索サービス毎にロボットを使用→サーバーへの負担 WWWページの取得に時間がかかる 収集データの陳腐化

分散協調サーチロボットの プロトコルの検討 Public Robot Server manager Web　server PRSM 制御 Search Service Server(SSS) 制御 PRS サイト間距離 Web　server PRS Web　server

PRSとPRSMのプロトコル設計 プロトコル (P1)担当するサーバーのリスト配布プロトコル (P2)発見したサーバーリストの配布プロトコル

PRSとPRSMの動作 動作 担当サーバーリストを送信(P1) WWWページを収集 WWWページを解析して未知のWWWサーバをPRSMに通知(P2) ページ収集情報(サイズ,転送時間)をPRSMに通知(P3) PRMSはPRSからの情報を元に次の担当サーバリストを作成

RPSの動作 PRSの動作 PRSMにアクセスし担当リストを取得 担当分を収集する 平日午前2時から午前8時、土日は午前2時から午後10時まで収集 100個のサーバーに同時にアクセス 1つのサーバーに対し20秒おきにアクセス 午前9時ごろ収集ログをPRSMに転送

PRSMの動作 現在はプロトタイプのためサーバーリストの更新は行なわず、手動で設定したリストをPRSへ送っている 次節で分散エリアを決定する方法について述べる

分散エリア決定法の検討 「負荷均等化アルゴリズム」の提案 負荷均等化の有用性を示す

Web空間のモデル化 Web空間の構成要素 スケーラビリティを考えホストを接点とした連結有効グラフとして表現 ＨＴＭＬで記述されたＷｅｂページ Ｗｅｂサーバーが動作している計算機 インターネット スケーラビリティを考えホストを接点とした連結有効グラフとして表現

ロボットのモデル化 ロボット：HTTPクライアントの一種 ロボットが保持する情報 負荷の均一化を行なうためにロボット間の通信が必要 自分が収集を担当しているホストのリスト 収集したWebページのデータ 各ホストのドキュメント量(KBytes) 各ホストの収集に要した時間 負荷の均一化を行なうためにロボット間の通信が必要 ロボットの数が増えるとパフォーマンスが落ちる ロボット間の距離を枝の重みとし,最小木をつくり、情報交換

パラメータの定義 Ｗｅｂ空間にロボットがm個所あるとし、その集合を とし、ロボットは最小木をなしているとする 収集対象となるホスト

コストの定義 ロボットのコストは収集にかかった時間で定義 当初ｐｉｎｇによる時間を利用する予定 実際にサーバにアクセスし50ファイルをｈｔｔｐにより収集したほうが良いことが判明 ロボットriの担当ホストHi=(hi1,hi2,…hini)に属するページを収集するのに要した時間tij(j=1,2,…,ni)(単位はmsec)

距離の定義 ネットワーク的な距離 ＝収集に要した時間/ドキュメント量 距離によるコスト ｗ:hに含まれる総ドキュメント量、ｄ：ｒからｈまでの距離

隣接ロボット間のコスト均等化1 ロボットは担当ホストでの収集を終えるとコストを計算 プリムのアルゴリズムにより最小木を構築 隣接ロボット間でコストの均等化を行なう 参考：http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim-jp.html

隣接ロボット間のコスト均等化2 A E A E 4 2 10 D 12 10 D 12 C C 2 2 4 4 F B 6 F B 6 8 3.5 -4.5 -2.5 C 2 2 10.5 4 F B 8 1.5 F B 6 -0.5 7.5 -2.5 8 8 10

隣接ロボット間のコスト均等化3 コストはロボットとホストの距離に依存する コストの均等化に注目している 隣接ロボットにホストを渡した結果かえってコストが増加することがある 複数ステップ先のホストで距離が短くなる場合も考えられる →複数ステップ先のコストを知る必要がある

負荷均等化アルゴリズム ロボット間で最小木を作る ホストを各ロボットにランダムに割り当てる 割り当てられたホストを収集する 隣接ロボット間でコスト均等化する 3に戻る

分散協調サーチロボットのプロトタイプシステムの設計と先行評価 103のＷＷＷサーバーを対象に7PRSで収集 3つのケースについて比較 同一データを収集 ランダムに分 負荷均一化を測った場合

実験結果(均一時)

実験結果(ランダムに分散)

実験結果(均一化後)

考察と検討 ランダムな分散をした場合で2.6から10.6倍、負荷均一化を行なうと5.5から22倍の高速化が可能 1~2週間で、収集時間の曜日の差がどの程度出るか 同じ平日でも収集時間の差によりサーバーを分類できるか