PDF (220652bytes)

1
WIT2000-G1-2
WWW ロボットの予備評価と高速化の検討
分散型
Experimental Evaluation of the Distributed WWW Robot and an Examination of the Speedup
山名 早人
森 英雄
田村 健人
Hayato YAMANA
Hideo MORI
Kent TAMURA
早稲田大学 理工学部 情報学科
京都大学大学院 情報学研究科
日本 IBM 東京基礎研究所
河野 浩之
村岡 洋一
Hiroyuki KAWANO
Yoichi MURAOKA
京都大学大学院 情報学研究科
早稲田大学 理工学部 情報学科
広域に分散した WWW サーバのデータの高速収集するための一手法として， WWW ロボッ
トと呼ばれる WWW サーバのデータを自動的に収集するプログラムをインターネット上に複数配置
し協調動作させる「分散型 WWW ロボット」について研究開発を実施している． 1998 年度末まで
に， 5ヶ所に分散したロボットを用いた評価を行いその有効性を確認した．本論文では，実用性を
評価するために実験規模を拡大し， 17ヶ所に分散配置された分散型 WWW ロボットを使い 6,500
の WWW サーバ（465 万 URL）を対象として行った結果を示す．この結果，一カ所で集中して収
集する場合に比較し，負荷均一化による分散により， 6.3 ∼ 286 倍の高速化が可能であることがわ
かった．特に， 17 台の分散型ロボットと 6,500 台の WWW サーバ間のデータ転送速度の間には，
同一の WWW サーバを対象とした場合でも平均 67.5 倍の速度差があり，さらなる高速化のために
は、データ転送速度を考慮した分散が重要になることが判明した．
1
はじめに
の 研 究 グ ルー プ
(IRTF-RD) が 中 心 と なっ て、
ARPA(Advanced Research Projects
世界中の WWW サーバから発信されるデータは
2000 年 1 月時点で約 17.8 億ページと予測される．
Agency(現
DARPA) や NSF(National Science Foundation) の
サポートを受け実施された研究である． Gatherer と
これらの WWW サーバのデータを自動的に収集す
呼ぶ WWW ロボットをネットワーク上の複数個所
るプログラムを一般に WWW ロボットと呼ぶ．この
に配置し分散収集をすることができるが，分散収集
WWW ロボットが全 WWW サーバにアクセスし，
必要な Web ページを収集するには，現状技術では
WWW ロボットを動作させるサーバの性能および回
時の WWW サーバの割り当ては静的分散であり，
分散の自動化については研究されていない．一方，
WebAnts は、 Texas
Instruments からの資金を受
線容量の制限などから，日本国内のみの WWW サー
け， John R. R. Leavitt 氏を中心にカーネギーメロ
バを対象とした場合でも 1ヶ月以上の時間を要する
ン大学で行われたプロジェクトである．複数のエー
[1]．また，インターネットに与える負荷の約 4 分の
1 が WWW ロボットのアクセスによって占められて
ジェント (Ant と呼ぶ) が協調して WWW サーバ群
に対して索引付けと検索を行う機能を提供し， Web
おり，インターネットに与える影響としても無視で
ページを分散収集する際の重複を避ることができる
きなくなってきている．
が，分散収集による高速化についての研究は実施さ
れていない．
このような問題を解決する方法として，分散型の
WWW ロボットが研究開発されており，代表例と
これに対して本研究では，田村の修士論文 [1] を
して， Harvest [2] や WebAnts [3] が挙げられる．
ベースとし，インターネット上に広域に分散した複
Harvest は， IRTF(Internet Research Task Force)
数の WWW ロボットを協調して動作させることによ
2
WIT2000-G1-2
り， Web ページを高速収集するための研究開発を実
ホスト数増加
施した1 [4] [5] [6] [7] [8] [9] [10]．これにより，従
来複数の WWW ロボットが同一の WWW サーバに
WWWサーバ数増加
14
12
アクセスし同じデータを収集するという無駄を無く
し，かつ，分散協調して集めることにより収集の高
ドメイン数増加
16
10
倍(前年比）
速化を目指した．
8
6
4
以下では，分散型 WWW ロボットによる収集高速
2
化の予備評価と，さらなる高速化のための検討を行
0
1992
1993
1994
1995
1996
1997
1998
1999
う．
2
図 2: ホスト数, ドメイン数,WWW サーバ数の毎年の増加
率 (米国 Internet Software Consortium, 英国 Netcraft 社
が公表するデータを元に作成)
Web ページ収集の現状と課題
2.1
インターネットと WWW の発展
イ ン ター ネッ ト に 接 続 す る コ ン ピュー タ 台 数
（ホ ス ト 数） は， 米 国 Internet
sortium
Software
Con-
(http://www.isc.org/) が 半 年 毎 に
公 表 す る デー タ に よ れ ば， 2000 年 1 月 現 在 で
約 7,200 万 台 で あ る． ま た， 英 国 Netcraft 社
(http://www.netcraft.co.uk/) が 毎 月 公 表 し て
い る デー タ に よ れ ば， WWW サー バ 数 は 2000 年
1 月現在で 995 万台であり，全ホストの約 14 ％ が
WWW サーバとして情報を発信していることにな
1994 年に WWW サーバ数が急増したのは，この
年に Netscape のバージョン１の公開に伴って急激に
ユーザ層が広がり，それに伴ってデータを発信する
WWW サーバ数が増加したためだと考えられる．
その後， WWW サーバ数の増加率は減少したが，
1998， 1999 年とほぼ前年比２倍で推移している．
一方，ホスト数及びドメイン数の増加は 1998， 1999
年とほぼ前年比 1.5 倍で推移している．
る．図 1に半年毎のインターネット接続ホスト台数と
WWW サーバ数の推移を示す．また，インターネッ
トに接続するホスト数，ドメイン数， WWW サーバ
数の毎年の増加率（前年比）を図 2に示す2 ．
Num.of Hosts
Hosts
80,000,000
Num.of WWW servers
WWW Servers
12,000,000
10,000,000
情報検索サービスの動向と WWW
サーバから発信されるデータ量
調査によれば， 1999 年 2 月現在の WWW サーバか
ら発信されるデータ量は約 8 億ページと推測される
[11]．テキストファイルのみのデータ量は 15TB (タ
グ部分を除けば 6TB ) であり，平均 18.7 KB/page
60,000,000
8,000,000
50,000,000
6,000,000
30,000,000
4,000,000
であるとの結果が得られている．これらの推定の詳
細は文献 [11] [12] に詳しいが，全体のページ数推
定は，複数の検索サービスに対して同じ Query を送
り，得られた検索結果の重複度から統計処理し算出
20,000,000
2,000,000
10,000,000
0
WWW
NEC 北米研究所の Steve Lawrence らの統計的
70,000,000
40,000,000
2.2
0
1993/7 1994/7
1995/7
1996/7
1997/7
1998/7
1999/7
1994/1
1995/1
1996/1
1997/1
1998/1
1999/1 2000/1
図 1: インターネットに接続するホスト数と WWW サー
バ数の推移 (米国 Internet Software Consortium, 英国
Netcraft 社が公表するデータを元に作成)
している．また，各ページの平均の大きさ等は，実
際に 2,500 の WWW サーバのデータを収集し算出し
ている．
1999 年 2 月 時 点 で の WWW サー バ 数 は， 英 国
Netcraft 社 の調査に よれば 430 万台であ り， 2000
年 1 月にはこれが 956 万台になっていることから推
測すると， 2000 年 1 月現在での Web ページ数は全
1 1998 年 度 ∼ 1999 年 度 に 実 施 し た 情 報 処 理 振 興 事 業 協 会
(IPA) の独創的情報技術育成事業の成果である．
2 ドメイン数は， edu, com, gov, mil, org, int, net で終わる
ドメインについては第二レベルで，それ以外のドメインは第三レベ
ルで計算した．
世界で 17.8 億程度となる．
2000 年 1 月 現 在 で の 有 名 な WWW 情 報 検 索
サー ビ ス サ イ ト が 収 集 し て い る Web ペー ジ 数
（各社 の公表 値）を調 査し たとこ ろ，最も 多く の
3
WIT2000-G1-2
ペー ジ を 収 集 し て い る 検 索 サー ビ ス サ イ ト は，
FAST(http://www.alltheweb.com/) で あ り，
3 億 ペー ジ（全 体 の 約 18 ％） に とど ま る． 一 方，
1997 年末時点での Web ページ数は 3.2 億，この時
点で最も多くのページを収集していたのは AltaVista
の 1.2 億ページであり，全体の約 38 ％をカバーして
1 20 を 越 え る Web ロ ボッ ト が 同 一 の WWW
サーバのデータを収集するのは無駄である点
インターネットの約４分の１を
2
トが利用している点
3 WWW 情報検索サービスがデータとして持つ
いた．このように，年々 Web ページ全体に対するカ
バー率は低下の一途をたどっている．
WWW ロボッ
Web のページのカバー率が低下している点
を考え合わせると，複数の WWW 情報検索サービ
スを提供するサイトが，個別にデータを収集せず協
2.3
Web
ページ収集と問題点
Web ページは，一般的には WWW ロボットと呼
ばれるプログラムを使って収集する．収集の開始点
となる URL を WWW ロボットに渡すことにより，
WWW ロ ボッ ト は， そ の 開 始 点 と な る URL か ら
力して高速に集めるための仕組みの構築が重要なポ
イントとなる．
3 研究開発内容概略
3.1
実験参加者
http プロトコルを用いて順次リンクをたどり WWW
コアメンバとして，早稲田大学，京都大学，北陸
ページを収集する．
公 開 さ れ て い る デー タ (http://info.
webcrawler.com/mak/projects/robots/
active/html/) に よ れ ば， 2000 年 1 月 現 在 で
の WWW ロボットの種類は 218 である．また，電
子技術総合研究所 (http://www.etl.go.jp/) への
アクセスログを元に調査したところ，常に 20 を越え
る Web ロボットが WWW サーバのデータ収集を毎
先端大学院大学，慶應義塾大学，大阪府立大学，日
本 IBM(株) 東 京 基 礎 研 究 所， シャー プ (株)， 電 子
技術総合研究所の８研究機関が参加すると共に，
外部協力機関を併せて合計 33 機関（21 大学， 4 イ
ンターネットサービスプロバイダ， 3 企業， 3 ネッ
トワーク機関， 2 国立研究所）が参加している (図
3)．
日行っていることが判明した．さらに，電子技術総
合研究所に対してアクセスのある WWW ロボット
を 調査 (1999 年 7 月 12 日 ∼ 18 日) し たと こ ろ，全
3.2
分散型 WWW ロボットの概要
分散型 WWW ロボットでは，
た．詳細を表 1に示す．
表 1: 全アクセスに占める WWW ロボットのアクセ
分散した
アクセスの 37 ％が Web ロボットによるものであっ
1 WWW ロボットをネットワーク上に分散して複
数配置する．
2
自動的に決定させると共に協調動作させる．
スの割合 (対象サーバ: 電総研)
WWW
ロボット運営
サイト
Excite
HotBot
Infoseek
FreshEye
全アクセスに
占める割合 (％)
6％
6％
4％
3％
WWW ロボットが担当するサーバを
の２点により，高速に WWW サーバ上のデータを収
集することを目指しており，直接の効果・成果，及
び，波及効果として以下の４点が期待される．
1 WWW サーバ上のデータを高速収集（目標は日
本全国の WWW サーバ上のデータを 24 時間以
WIDE で の 報 告 (http://www.wide.ad.jp/) に
内に収集) することが可能となる．
よ れ ば， http プ ロ ト コ ル は， 全 プ ロ ト コ ル の 70
高速収集により，検索サービスサイトでは，最
％程度を占めているため，電子技術総合研究所の
新のデータを利用した検索サービスの提供が可
WWW サーバへのロボットのアクセスが平均的なも
能となる．つまり，最新性において質の高い検
のであると仮定すると，「インターネットの約４分
索を提供することができるようになり，イン
の１は WWW ロボットが利用している」と推測する
ターネット検索ビジネスの活発化にもつながる
ことができる．このように，
と予想される．
2
4
WIT2000-G1-2
8.シャープ株式会社技術本部ソフトウェア研究所
1.東京大学 工学部 電子情報工学科
9.京都大学大学院情報学研究科
2.学術情報センター研究開発部
3.北陸先端科学技術大学院大学
4.奈良先端科学技術大学院大学情報科学研究科
5.東京大学 生産技術研究所
10.電子技術総合研究所情報アーキテクチャ部
6.岐阜大学工学部応用情報学科
11.慶應義塾大学環境情報学部
7.農林水産省農業研究センター
12.徳島大学工学部
13.岩手県立大学ソフトウェア情報学部
14.東京工業大学 大学院総合理工学研究科
Robot Server (PRSM)
15.横浜国立大学工学部電子情報工学科
core members
16.NTT未来ねっと研究所
17.琉球大学 総合情報処理センター
Another cooperated sites
18.南山大学経営学部情報管理学科
19.大阪府立大学工拡部経営工学科
20.(株)ネットウェーブ四国 技術部
21.トライネットワークインターナショナル（株）
JAIST Waseda Univ.
22.北海道地域ネットワーク協議会
23.ネスク・インターネット
ETL
Kyoto Univ.
24.東北インターネット協議会
25.早稲田大学理工学部情報学科
Osaka Pref. Univ.
26.日本IBM東京基礎研究所
27.Intioプロバイダ
28.九州大学大学院システム情報科学研究科
29.広島大学工学部第二類
Keio Univ.
30.東海地域ハブ研究会
31.東京大学 生産技術研究所
Sharp Corp.
32.筑波大学 学術情報処理センター
33.大阪教育大学 教育学部
21 Universities
4 ISPs
3 Companies
3 Internet Organizations
2 National Laboratories
図 3: 実験参加組織
writtenin Java
Pu b lic R o b o t
Se v e r M a n a g e r
PR S M
S e a rc h
S e rv ic e
S e rv e r( S S S )
data transferspeed
Si
d(Rj,Si)
Rj
c o n t ro l
WWW
Server
wi
PR S
c o n t ro l
Si+1
wi+1
PR S
WWW
Server
PR S
PR S
Lk
PR S
Si+2
PR S
Lk+1
wi+2
PR S
Rj+1
WWW
Server
分散型W W Wロボット
Si : WWW Server
wi : size of documents in Si
Rj : Public Robot Server(PRS)
d(Rj,Si) : data transfer speed between Si and Rj
Lk : Search Service Server that constructs WWW database
図 4: 分散型 WWW ロボットの仕組み
現在各検索サービスサイト毎に独立に動かして
3
与する．
いる WWW ロボットを本研究開発によって開
発された広域分散協調サーチロボットに置き換
えることにより，国レベル，あるいは，世界レ
3.3
分散型 WWW ロボットの動作概要
ベルでの協調収集が可能となる．これにより，
分 散 型 WWW ロ ボッ ト は， 図 4に 示 す よ う
現在インターネットの負荷の４分の１を占める
に，全体を管理する Public Robot Server Man-
WWW ロボットによる負荷を大幅に削減するこ
ager(PRSM) と 個々 の WWW ロ ボッ ト で あ る
とが可能となる．
Public
本ソフトウェアは次世代のコンピューティング
4
Robot
Server(PRS)
か ら構 成さ れる．
PRS・ PRSM は Java1.2 で 実 装 さ れ て お り，
PRSM は WWW サーバ Apache に JServ モジュー
環境として近年研究開発が活発化の兆しを見せ
ルを組み込み，処理は Java servlets で行っている．
ている Globus [13] に代表される「広域分散コ
PRSM は， PRS に 対 し て 担 当 WWW サー バ の
ンピューティング」の一つの重要なアプリケー
分配や，各 WWW サーバと PRS 間との距離計測を
ションとなり，本分野の研究開発の活性化に寄
指示する．一方， PRS で新規に発見された WWW
5
WIT2000-G1-2
サー バ や 距 離 計 測 の 結 果 は， PRSM に 送 ら れ，
ムに抽出したものである．
PRSM 側で PRS への 担当 WWW サー バ 割り 当て
を 行 う． PRS へ の 担 当 WWW サー バ 割 り 当 て 方
表 2: 評価実験に用いた PRS(順不同)
設置場所
式として，ランダム方式と負荷均等化方式の二種類
PRS01
をサポートしている [7]．このようにして， PRS は
PRS02
PRSM からの指示に基づき各々互いに重複しない
PRS03
WWW サーバを担当し Web ページを収集する．
PRS04
PRS05
収 集 さ れ た デー タ は， 最 終 的 に 図 中 の Search
Service
PRS06
Server(SSS) に 再 配 布 す る こ と に よ り，
PRS07
検 索 サー ビ ス の た め の 索 引 作 成 を 行 う． 現 在 の
PRS08
HTTP/1.1 準 拠 の サー バ は， 1 回 の 接 続 で 複 数 の
PRS09
PRS10
データを転送する Keep-Alive 機能を持っているが，
PRS11
複数のデータをまとめて転送する機能は持っていな
PRS12
い．このため，各 PRS で収集したデータを SSS に
PRS13
PRS14
再配布する際のオーバヘッドを小さくするため，複
PRS15
数のデータを 1 回の接続でまとめて圧縮して送る機
PRS16
能，及び， SSS からの要求に応じてデータ中の必要
PRS17
慶応大学
Intio プロバイダ
農林水産省 農業研究センター
琉球大学
奈良先端大学院大学
ＮＴＴ未来ねっと研究所
東北インターネット協議会
広島大学
東京工業大学
通商産業省 電子技術総合研究所
南山大学
岐阜大学
東京大学
徳島大学
京都大学
北海道地域ネットワーク協議会
国立情報学研究所
な部分のみ (例:URL や更新日時の指定による指定)
を送る機能を PRS に持たせる．
PRS は，まず起動時に PRSM にアクセスし，担
当リストを PRSM から取得する．担当のサーバの
表 3: 評価実験の対象とした WWW サーバの分類
ドメイン
ページをすべて 取得し終ると，再び担当 リストを
サーバ数
ac.jp
2,580
取得する．ページ収集は，インターネット及び相手
co.jp
2,371
の WWW サーバへ与える負荷を最小限におさえる
or.jp
606
ne.jp
435
go.jp,kek.jp
137
ため，動作時間を制限し，平日は午前 2 時∼午前 8
時，土日は午前 2 時∼午後 10 時のみページ収集を行
gr.jp
う．これは， Internet Exchange サイトの調査で，
ad.jp
地域名.jp
午前 2 時∼午前 8 時頃の負荷が一番小さいとの結果
合計
に基づいている．さらに， Java のスレッドを用い，
53
27
291
6,500
同時に 200 個のサーバに対して並列にアクセスを行
ない，高速化を実現している．
1 つのサーバに対しては，サーバへの負荷を少な
くするため，連続してアクセスはせず 20 秒おきにア
クセスを行なうが， WWW サーバが HTTP/1.1 の
Keep Alive 機能に対応している場合は可能な限り連
続でアクセスを行なう仕様となっている．
4.2
対象 WWW サーバの特徴解析
対 象 と し た 6,500 の WWW サー バ が 持 つ 総
URL 数 は， 4,653,140URL で あ り， 単 純 平 均 で
615URL/Server， メ ディ ア ン は 82URL/Server で
あっ た． ま た， 総 デー タ 容 量 は 22GB， 単 純 平 均
で 3.5MB/Server， メ ディ ア ン は 339KB/Server で
4
性能評価実験
4.1
実験参加サイトと対象 WWW サーバ
あった．
総容量の分布を図 5に示す．図の横軸は１サーバ当
りのデータ容量 (KB) であり，縦軸が累積 (サーバ数
性能評価実験は，表 2に示す 17 台の PRS(Public
及び容量) である．図から明らかなように，極端に
Robot Server) を用いて行った．また，実験対象と
データ量が多いサーバが存在し，データ量が多い上
して選んだ WWW サーバは，表 3に示す日本国内の
位 1 ％ (65 台) の WWW サー バ で 総 デー タ 量 の 43
6,500 サーバである．これらの WWW サーバはこれ
％を占めている．すなわち， WWW サーバのデータ
までの実験で把握している 50,000 サーバからランダ
を高速に収集するためには，これら大容量のデータ
6
WIT2000-G1-2
を持つ WWW サーバに対して複数の PRS により並
100.0%
90.0%
列収集することが重要となる．
80.0%
70.0%
60.0%
100.00%
50.0%
99%
40.0%
90.00%
30.0%
80.00%
20.0%
10.0%
70.00%
サーバ数累積
容量累積
0.0%
1
60.00%
10
100
1000
57%
50.00%
データ転送速度の最小値と最大値の差（倍）
40.00%
30.00%
図 6: 17PRS と 6500WWW サーバ間のデータ転送
20.00%
速度差 (倍) の分散
10.00%
.00%
1
10
100
1,000
10,000
100,000
1,000,000
データ容量 (KB) ／ WWW サーバ
図 5: 各 WWW サーバのデータ量の分布
表 4: 各 WWW サーバについて 17PRS 内で最高速・最低
速のデータ転送速度を持つ WWW サーバ数
PRS 名
最低速
最高速
PRS01
3
PRS02
3
14
PRS03
7
191
PRS04
19
314
PRS05
1
225
PRS06
6
3,040
PRS07
0
152
PRS08
2
290
PRS09
4
200
PRS10
425
0
PRS11
3
76
PRS12
4
229
PRS13
5
336
PRS14
4
114
PRS15
2
1,101
PRS と一番遅い PRS との差は， 2 倍∼ 710 倍，平
PRS16
6,004
15
均 67.5 倍，メディアン 48.2 倍であった．図 6にデー
PRS17
8
40
6,500
6,501(*)
4.3
負荷均等化評価
負荷均等化評価では，まず， 17PRS から 6,500 の
サーバに対してトップページ (例:http://www.etl.
go.jp:80/) から 50URL のみの限定収集を行い，各
PRS と 6,500 サーバ間のデータ転送速度 (byte/s) を
求めた．
同一の WWW サーバに対するデータ転送速度は，
17 個 の PRS で 大 き な 差 が 認 め ら れ た． 一 番 速 い
合計
タ転送速度差の分散を示す．上記より，ランダム分
94
(*) 同一最高転送速度を 2PRS が持つ．
散では，大きな負荷の不均衡が発生することが予測
され，負荷の均等化が必要になることがわかる．
また，表 4に各 WWW サーバについて 17PRS 内
うことにより，実測で 11.1 倍の速度向上が得られる
で最高速・最低速のデータ転送速度を持つ WWW
ことがわかる．予測値と実測値の間の誤差は平均 25
サーバ数を各 PRS 毎に集計したサーバ数を示す．こ
％であり，これは，ネットワーク及び WWW サーバ
の表から明らかなように， 6,500 の WWW サーバに
の動的負荷変動が原因と考えられる．
対する各 PRS のデータ転送速度に大きな片寄りがあ
ることがわかる．
負荷均等化では， [9] のアルゴリズムを用いて各
PRS へのスケジューリングを求め，得られたスケ
ジューリング結果を用いて評価を行った．
評価においては，ランダム分散時に比較して負荷
均等化により，どの程度負荷が均等化されるかを調
べた．表 5に，ランダム分散（予測値）及び均等化分
散 (予測値及び実測値) を示す．
表 5より，ランダム分散に比較して負荷均等化を行
4.4
分散型 WWW ロボット総合評価
単一の PRS を用いて 6,500 台の WWW サーバの
全データを収集する時間は，各 PRS によって異な
り，各 PRS が 1 スレッドを用い逐次に収集した場
合，最小 28 日 (京都大学) ∼最大 712 日 (北海道地域
ネットワーク協議会) と推定される3 ．
3 17PRS か ら 6500 の WWW サー バ に 対 す る 転 送 速 度 を
50URL のみのページを収集することによって求め，Σ｛(WWW
サーバが持つデータ容量) ÷ (転送速度)｝により逐次で収集した場
7
WIT2000-G1-2
表 5: 均等化分散の効果 (単位:hour)
表 6:
6,500WWW
サーバを収集した時の収集時間 (hour)
スレッド時 200 スレッド時
1
ランダム分散
(予測)
均等化分散
(予測)
均等化分散
(実測)
PRS01
68.8
41.7
28.2
PRS02
71.1
107.9
104.5
PRS03
88.3
35.0
43.7
PRS04
61.5
55.1
29.6
PRS05
51.7
63.7
53.7
PRS06
33.8
146.2
96.7
PRS07
57.6
55.2
44.7
PRS08
50.8
80.7
71.1
PRS09
43.1
39.0
38.7
PRS10
335.5
32.8
11.0
PRS11
51.8
38.3
28.8
PRS12
63.9
39.3
46.2
PRS13
70.6
56.1
13.7
PRS14
66.4
61.7
40.8
PRS15
37.1
51.4
52.4
PRS16
1216.1
107.9
109.5
PRS17
61.0
61.0
52.1
1216.1
146.2
109.5
-
8.3
11.1
最大値
ランダム
分散を基準
とした
速度向上
PRS01
1,008
32
PRS02
1,518
55
PRS03
1,201
55
PRS04
975
32
PRS05
987
24
PRS06
793
23
PRS07
1,066
59
PRS08
953
27
PRS09
1,033
34
PRS10
6,121
244
PRS11
1,158
42
PRS12
904
26
PRS13
1,025
31
PRS14
904
26
PRS15
691
26
PRS16
17,085
544
PRS17
1,663
53
均等化分散
109.5
1.9
集が可能な地点に PRS を配置することが効率化の点
で重要であることが数値的に証明された．
なお，現在各 PRS では 200 のサーバに対して同
時にアクセスできる仕組みを持っており，この 200
一方，各 PRS が 200 スレッドで並列に収集した場
スレッドを効率よく利用する均等化アルゴリズムに
合でも最小 23 時間 (NTT 未来ねっと研究所) ∼最大
ついても，今後さらなる検討が必要である．すなわ
23 日 (北海道地域ネットワーク協議会) が必要とな
る4 ．
表 6 5 に 1 スレッド及び 200 スレッド時の収集時間
ち， 200 スレッドを並列に動作させる場合には，収
集に時間のかかる WWW サーバの収集を先行させて
開始させ，負荷均等化を図る必要がある．
を示す．これを負荷均等化分散によって，高速化す
ることにより，図 7に示すように， 17 台の PRS で
5 おわりに
6.3 倍 (NTT 未来ねっと研究所を基準) ∼ 286 倍 (北
海道地域ネットワークを基準) の高速化を達成するこ
とができた．
イ ン ター ネッ ト 上 の 17ヶ 所 に 配 置 さ れ た 分 散
型 WWW ロ ボッ ト を 用 い， 日 本 国 内 の 6,500 の
本結果から，もともと高速に収集可能な PRS を
WWW サーバを対象とした収集実験を行い，実際の
基準とした場合には， 17 台に分散しても，必ずし
分散型 WWW ロボットの有効性を確認した．この結
も 17 倍の高速化が達成できないことがわかる．これ
果，一カ所で集中して収集する場合に比較し，負荷
は，例えば，処理能力 100 の計算機と処理能力 50 の
均一化を行った場合， 6.3 ∼ 286 倍の高速化が可能
計算機を使って並列計算した時に最大でも 1.5 倍にし
であることがわかった．
かならないことと同等である6 ．
インターネットに広域に分散したシステムは，イ
以上から，分散型 WWW ロボットを使って高速な
ンターネットの接続の不確実性，及び，複数システ
収集を実現するためには，ネットワーク的に高速収
ムの安定動作の確保の問題から，常に全てのシステ
合の実行時間を算出．
4 MAX ｛((1 スレッ ド で の 収集 時 間) ÷ 200),MAX(PRS が
担当する各 WWW サーバの収集時間)｝により算出した．各 PRS
で 200 スレッドに最適な分散ができたと仮定．
5 掲載の数値はデータ転送に必要な時間であり， PRS の仕様で
ある「接続切れ時の待ち時間 (20 秒)」は含まれない．
6 ここでの処理能力が PRS のデータ転送速度に対応する．
ムを動作させることは極めて困難となる．このた
め， (1) どのようにして広域に分散したシステムのメ
ンテナンスを行っていくか，また， (2) そのような状
況でどのような評価をすべきか，さらに， (3) 負荷の
均等化をさらに進めるための研究開発，の 3 点が本
8
WIT2000-G1-2
50.0
56
（倍)
45.0
128
156
258
200thread/PRS
40.0
1thread/PRS
35.0
30.0
25.0
20.0
15.0
10.0
5.0
0.0
PRS01 PRS02 PRS03 PRS04 PRS05 PRS06 PRS07 PRS08 PRS09 PRS10 PRS11 PRS12 PRS13 PRS14 PRS15 PRS16 PRS17
図 7: 分散収集による速度向上率 (倍)(各々の PRS で全データを収集した場合を基準)
研究の実運用を開始するにあたって残された課題で
[6] Hayato
ある．
Hideki
今後は，上記のような問題点を解決し，国内での
Hiroyuki
[7]
Hiroyuki
and
Yoichi
参考文献
田村健人: 分散 WWW ロボットに関する研究, 早稲田
大学修士論文, 早稲田大学 (1997.3)
Danzig,
Darren
[9]
The
Harvest Information Discovery and Access System, Computer Networks and ISDN Systems,
Vol.28, pp.119-125 (1995)
http://polarbear.eng.pgh.lycos.
com/webants/
[3] WebAnts:
Eectiveness of Cooperative Resource Collecting Robots for
Web Search Engines, Proc. of Pacrim'97, Vol.1,
[4] S.Kamei,H.Kawano and T.Hasegawa:
pp.410{413 (1997)
山名早人, 田村健人, 河野浩之, 亀井聡, 原田昌紀, 西村
英樹, 浅井勇夫, 楠本博之, 篠田陽一, 村岡洋一 : 分散
型 WWW ロボットによる WWW 情報収集, データ工
学ワークショップ DEWS98, No.24 (1998.3.5-7)
山 名, 田 村, 森, 河 野, 黒 田, 西 村, 浅 井, 楠 本, 篠 田, 村
岡: 国内の全 WWW データを 24 時間で収集する分
散型 WWW ロボットの試み ,North シンポジウム'99
論文集 (1999.3.6-7)
森 英雄，河野 浩之: 実測データに基づく分散協調型
WWW データ収集アルゴリズムの性能評価, 日本ソフ
トウェア科学会 The
Second Workshop on Internet
Technology (1999.8.25-27)
R.
Hardy, Udi Manber and Michael F.Schwartz:
森 英雄:
分散協調型 Web データ収集アルゴリズ
ムの性能評価, 京都大学 情報学科 特別研究報告書
(1999.2)
[8]
Peter B.
ASAI,
380, (1998.8.24-28)
御協力をいただきました．実験参加組織 (図 3) の皆
Bowman,
Isao
SHINODA
Proc. of SIGIR'98, Melbourne, Australia, pp.379-
様に感謝いたします．
Mic
Yoichi
Experiments of Collecting WWW
Information using Distributed WWW Robots,
本研究実施にあたっては，様々な面での御助言，
[5]
TAMURA,
MURAOKA:
謝辞
[2] C.
Kent
NISHIMURA,
KUSUMOTO,
実運用サービスを開始する予定である．
[1]
YAMANA,
KAWANO, Satoshi KAMEI, Masanori HARADA,
[10]
山名: 広域分散コンピューティングの現状と課題−分
散型 WWW ロボットを例に とって−,North シンポ
ジウム 2000 論文集 (2000.3.6-7)
[11] S.Lawrence and C.L.Giles:
mation on the Web,
Accessibility of Infor-
Nature, Vol.400, pp.107-109
(1999.7.8)
Lawrence, C. Lee Gilesd:
Searching the
World Wide Web,Science, Vol,280, No.5360, Issue
[12] Steve
3, pp. 98 - 100 (1998.4)
C.Kesselman:
The Globus Project: A
Status Report, Proc. of IPPS/SPDP'98 Heteroge-
[13] I.Foster,
neous Computing Workshop, pp.4-18 (1998)