一般論文

DBSJ Journal, Vol.7, No.3
December 2008

P2P ネットワークにおけるデータの更新量を考慮した更新伝播手法の提案
A Proposal of Update Propagation
Strategies Considering Degree of Data
Update in Peer-to-Peer Networks

渡辺 俊貴 ♥
原 隆浩 ♦

神崎 映光 ♦
西尾 章治郎 ♦Toshiki WATANABE Akimitsu KANZAKI
Takahiro HARA Shojiro NISHIO

P2P ネットワークでは，複数のピアにデータの複製を配置してネットワークの負荷を軽減することが有効である．このとき，デー
タが更新された際，複製を所持するピアに更新情報を伝播する必要があるが，データの更新量が少ない場合には，全てのピアが更新情報を必要とするとは限らない．本論文では，データの更新量を考慮した二つの更新伝播手法を提案する．提案手法
では，複製を所持する各ピアが設定する更新データを受信する
条件を考慮し，更新データを必要としていないピアへの更新情報の伝播を抑制することで，データ更新に伴うネットワークの負荷を削減する．
In a P2P network, it is common that data items are
replicated on multiple peers for improving data
availability. In such an environment, when a data item is
updated on a particular peer, the update should be
immediately propagated to other peers holding its replicas.
However, in some applications, some replica holders do
not need the latest version when the degree of change inthe update is small. In this paper, we propose two update
propagation strategies considering the degree of change indata update in P2P networks. Our proposed strategies
reduce the load for propagating updated data by
suppressing the update propagation to replica holders
which do not need to receive the latest version.

1. はじめに
近年，計算機の高性能化やネットワークのブロードバンド
化により，Peer-to-Peer (P2P)ネットワークを用いたデータ共有に関する研究が注目されている．P2Pネットワークでは，検索効率の向上や負荷分散のためにデータを複製し，複数のピアに配置することが有効である[1][2]．また，データに更新が発生する場合，そのデータの複製を所持するピア（複製所持ピア）に更新を通知する必要がある[3][4][5]．ここで，更新が頻繁に発生する環境では，更新発生のたびに全ての複製所持ピアに更新データを伝播すると，データ更新に伴うネットワークの負荷が非常に大きくなる．
一方，複製所持ピアの中には，データの更新量が少ない場
合には自身の複製を更新せず，データが大きく更新された場
合にのみ自身の複製を更新することを望むものが存在する．
例えば，株価や気象情報などの数値データがわずかに変化した場合や，Webページの一部のみが更新された場合は，その更新情報を必要としないピアが存在するものと考えられる．
このような環境では，各複製所持ピアが，データがどの程度更新された場合に更新データを受け取るかという条件（データ要求条件）を設定しておき，この条件を満たす場合にのみ更新データを受信することで，データ更新に伴うネットワー
クの負荷を削減できる．
本論文では，データの更新量を考慮した二つの更新伝播手法を提案する．一つ目の手法であるUPDD-S (Update
Propagation strategy considering Degree of Data updatewith Same-condition trees)では，同一のデータ要求条件を設定しているピアごとに木構造(SC: Same-Condition木)を構築する．更新発生時にはデータのオリジナルをもつピア（オリジナルノード）がそれぞれのSC木の根ノードに直接
更新データを送信することにより，データを必要としていな
いピアへの更新伝播を抑制する．二つ目の手法である
UPDD-SO (UPDD with Same-condition trees andOrdered-condition trees)では，SC木に加え，SC木の根ノードのみで構築される新たな木構造(OC: Ordered-Condition木)を構築することにより，複製所持ピアを階層的に管理する．
これにより，UPDD-Sと比較して，オリジナルノードの負荷を軽減する．

2. 想定環境
本論文では，非構造型P2Pネットワークにおいて，各ピア
が，自身または他のピアがもつデータにアクセスする環境を想定する．また，検索に用いるネットワークとは別に，各データごとに更新伝播用のネットワーク（更新伝播木）を構築
する．各データは，そのデータのオリジナルノードのみが更新し，このオリジナルノードが更新伝播木の根ノードとなる．
データにアクセスしたピアは，データの複製を作成し，そのデータの更新伝播木に参加する．また，データとしては，オンラインショップの価格情報や株価などの数値データをはじめ，更新によって変化したデータのサイズやその割合，更新された項目数など，データの更新前と更新後の差分を数値で表すことができるデータを対象とする．各複製所持ピアは，オリジナルデータが自身のもつ複製からどの程度変化した
場合に更新データを受信するか，という差分の値をデータ要求条件として指定する．
なお，本論文では，説明の容易さから，数値データを想定して説明する．

♥

学生会員 大阪大学大学院情報科学研究科博士後期課程
watanabe.toshiki@ist.osaka-u.ac.jp♦
正会員 大阪大学大学院情報科学研究科{kanzaki, hara, nishio}@ist.osaka-u.ac.jp

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008
オリジナルデータ

オリジナルノード

00
A

B

・・・・

2

C

17
00

D

7
33

21
33

33

A0

F
5
00

00

A

±2

B

+20,-14A2

2

2

データ要求条件00

所持する複製の値

SC木+10,-4+24,-18

E

±15

4

F

±5

4

・・・・

B

2

C

17
33

0⇒5
0⇒5

D
21

7
33

E
15
33

F
00

0⇒5
0⇒5

A

±2

A

±2

B

+20,-14B+15,-19

C+10,-4

C

+5,-9

D

+24,-18

D+19,-23E±15

E+10,-20

F

±5

F

±5

2
2

2

A2

B
B0

C

4

7

4
4

Fig.3

更新伝播先リスト

5

A0
A1

4

H
23

F
29

45
G
31

I
49

J
52

K
58

D
12
OC木

図 3 UPDD-SO における更新伝播木
Structure of a logical tree in UPDD-SO.

4. 提案手法

オリジナルデータ

0⇒5
0⇒5
A

4

SC木

図 1 UPDD-S における更新伝播木
Fig.1 Structure of a logical tree in UPDD-S.
オリジナルノード

2

D

2

E

A

C

複製所持ピア

2

A1

E
15

オリジナルノード

更新伝播先リスト

更新データ

SC木

図 2 UPDD-S における更新伝播
Fig.2 Update propagation in UPDD-S.

3. 関連研究
非構造型P2Pネットワークにおける更新伝播に関する研究
は，これまでにいくつか行われている．Dattaらは，確率に基づいて更新データを伝播させる手法を提案している[3]．この手法では，更新データを受け取ったピアは，同じデータの複製を所持するピアのうちいくつかに対して，ある確率で更新
データを伝播させる．これにより，更新データを重複して受け取る可能性を低くしつつ，全ての複製所持ピアに更新デー
タを伝播させることを目的としている．Wangらは，チェイン状の更新伝播用論理ネットワークを利用した更新伝播手法を提案している[4]．この手法では，複製を所持するピアを一直線のチェイン上に配置する論理ネットワークを形成することにより，更新伝播を実現する．また，筆者らの研究グ
ループでは，木構造の更新伝播用論理ネットワークを利用した更新伝播手法(UPT-FT: Update Propagation Tree with
Failure Tolerance)を提案している[5]．この手法では，複製所持ピアで構成される木構造ネットワーク（更新伝播木）を構築し，この木構造に沿って更新データを伝播させることで，更新伝播時の負荷分散と遅延減少を両立している．しかし，これらの手法は，データが更新された場合に，全ての複製所
持ピアに常に更新データを伝播させている．そのため，デー
タを更新する必要がないピアが存在する場合でも，それらのピアに更新を伝播させるため，ネットワーク負荷が高まって
しまう．

4.1
UPDD-S (Update Propagation strategy
considering Degree of Data update with
Same-condition trees)
UPDD-S では，同一のデータ要求条件をもつピアで構成される木構造（SC 木）を構築する．図１に UPDD-S における更新伝播木を示す．図１において，各ピアはそれぞれデータ
要求条件を設定しており，SC 木 A, E, F に参加するピアは値が 0 のデータ（複製）を，SC 木 B, C, D に参加するピアは値が 3 のデータ（複製）を所持している．

4.1.1 更新伝播
UPDD-S では，オリジナルデータが更新された場合，オ
リジナルノードが，その更新データを必要としているピアからなる SC 木の根ノードに更新データを送信する．
適切なピアにのみ更新データを伝播させるために，オリジ
ナルノードは，すべての SC 木の情報を更新伝播先リストとして管理する．図 1 の表に，更新伝播先リストの一例を示す．
この図において，オリジナルデータの値(0)と SC 木 A に属するピアが所持する複製の値(0)の差は 0 であり，SC 木 A のデータ要求条件は 2 である．このとき，SC 木 A に属するピア
は，オリジナルデータの値が 2 以上変化した場合に更新デー
タを受け取る必要がある．従って，オリジナルノードは，SC木 A の情報として±2 を更新伝播先リストに格納し，オリジ
ナルデータの更新量がこれらの値よりも大きい場合にのみ，対応する SC 木に更新データを伝播させる．
オリジナルデータが更新された場合，オリジナルノードは自身の更新伝播先リストを参照し，更新データを必要としている SC 木の根ノードに直接更新データを送信する．同時に，オリジナルノードは，自身の更新伝播先リストの情報を更新する．図 2 に，UPDD-S における更新伝播の様子を示す．オ
リジナルデータの値が 0 から 5 に更新された場合，オリジナ
ルノードは，データ要求条件を満たす SC 木 A と F の根ノードに更新データを送信する．その後，オリジナルノードは，各 SC 木に関する情報を更新する．たとえば，SC 木 B に関
しては，その値を 5 だけ減少させ，(+15, -19)に更新する．
最後に，更新データを受け取ったピアはそのデータを SC 木に沿って伝播させる．

4.1.2 木構造の維持
UPDD-Sでは，ピアがデータの複製を配置，削除した場合，更新伝播木上でピアの参加や脱退が発生する．

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008
からなる別の木構造（OC木）を構築する．このOC木は，データ要求条件の値が小さいピア（SC木の根ノード）の深さ
がより小さくなるn分木とする．

オリジナルノード
A: ±2

2
2

・・・

4.2.1 更新伝播

A

A0

2

2

D: +2,-12

55

・・・

E: ±104

更新伝播先リスト

B: ±4

55 D: ＋2,-12

B

C

-

00

図4
Fig.4

E
10

7

-

55

55

D
-

-

12

C: ±12--55

UPDD-SO において各ピアが管理する情報（更新データ伝播用）
Information managed by peers for update
propagation in UPDD-SO.

ピアが新たに更新伝播木に参加する場合，参加するピア（新規ピア）は，オリジナルノードに参加要求を送信する．
参加要求を受け取ったオリジナルノードは，新規ピアと等しいデータ要求条件をもつSC木の根ノードに参加要求を転送する．その後，SC木に沿って参加要求を伝播させ，新たな葉ノードの一つとしてそのSC木に参加する．一方，ピアが更新
伝播木から脱退する場合，脱退ピアは脱退要求を自身が参加するSC木の葉ノードまで伝播させ，その葉ノードと位置を入れ替えることにより，更新伝播木から脱退する．
この手順により，更新データを必要としていないピアへの更新伝播を抑制でき，更新伝播時のネットワーク上の負荷を削減できる．しかし，UPDD-Sでは，各ピアが様々なデータ要求条件を設定すると，多くのSC木が作成されることにな
る．この場合，オリジナルノードはすべてのSC木の情報を管理し，必要に応じてそれらの根ノードに直接更新データを送信する必要があり，オリジナルノードの負荷が高まってし
まう．

4.2 UPDD-SO (UPDD with Same-condition trees
and Ordered-condition trees)
UPDD-Sでは，各ピアのデータ要求条件を考慮することで，更新データを必要としていないピアへのデータ伝播を抑え，データ更新に伴う負荷を削減できる．しかし，前述した通り，
UPDD-Sでは，オリジナルノードが，存在する全てのデータ要求条件に対して個別にSC木を構築し，管理する必要がある．そのため，データ要求条件が多様な環境では，オリジナ
ルノードの負荷が高まってしまう．
この問題を解決するために，もう一つの手法である
UPDD-SOを提案する．UPDD-SOにおける更新伝播木の概要を図3に示す．UPDD-SOでは，UPDD-Sと同様に，デー
タ要求条件が等しいピアごとにSC木を構築する．また，オ
リジナルノードは，データ要求条件の大きさに応じて，各SC
木を複数のグループに分類し，それぞれのSC木の根ノード

図４に，更新データ伝播のためにOC木上のノードが管理する情報を示す．OC木上の各ノードは，UPDD-Sにおけるオリジナルノードと同様に，OC木上の子ノードが次に更新
データを受信する条件を更新伝播先リストとして管理する．
ただし，子孫ノードのうち，子ノードよりも次に更新データを受信する条件を表す値の絶対値が小さいノードが存在する場合には，その子孫ノードの情報も更新伝播先リストに加える．たとえば，図４のピアA0は，ピアB0とピアC0が次に更新データを受信する条件である±4と±12を更新伝播先リス
トに格納する．また，ピアB0の子孫ノードであるピアD0は，所持している複製の値(0)とオリジナルデータの値(5)との差が5であるため，オリジナルデータの値がさらに2増加した場合に更新データを必要としている．この値は，ピアB0が次に更新データを受信する条件(±4)より絶対値が小さいため，ピ
アA0は，ピアB0の子孫ノードの情報として，自身の更新伝播
先リストにピアD0の条件(+2, -12)を追加する．
以下では，図5を用いて，データ更新時の動作例を示す．
図5において，初期状態では，オリジナルノードおよび全複製所持ピアは，値が0である最新のデータ（複製）を所持しているものとする．
（1）データを更新したオリジナルノードは，UPDD-Sにおけるオリジナルノードの動作と同様に，自身の更新伝播先リストを参照し，更新データを必要としているピアを含むOC木が存在するかどうかを調べる．該当するOC木が存在する
場合，更新データを送信する．一方，更新データを送信しなかったピアに関しては，そのピアが次に更新データを受信する条件に関する情報を更新する．たとえば図5(a)において，データの値を0から5(+5)に更新したオリジナルノードは，自身の更新伝播先リストの中で，データ要求条件が±2である
ピアA0に更新データを送信する．一方，データ要求条件が±23であるピアF0には更新データを送信せず，ピアF0が次に更新データを受信する条件を5だけ減少させる(+18, -28)．
（2）更新データを受け取ったピアは，自身が所持する複製を更新し，SC木に沿って，データ要求条件が等しいピアに
更新データを伝播させる．同時に，自身の更新伝播先リスト
を参照し，自身の子ノードを根とする部分木のうち，更新データを必要としているピアが存在しているものに更新デー
タを送信する．また，更新データを送信しなかったピアに関しては，オリジナルノードと同様に，そのピアに関する情報を更新する．たとえば，図5(a)のピアA0は，自身の複製を0から5に更新し，SC木に沿って更新データを伝播させる．その後，自身の更新伝播先リストを参照し，値の絶対値がデー
タの更新量より小さいピアB0(±4)に更新データを送信する．
また，ピアC0は条件の値(±12)が更新量よりも大きいため，
更新データは送信せず，ピアC0の条件の値を5減少させる．
（3）手順（2）において更新データを受け取ったピアは，次に更新データを伝播すべき子孫ノードがOC木上に存在しな
い場合，更新データの伝播を停止し，自身と自身の子ノードが次に更新データを受信する条件を比較する．子ノードの条

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008

2
2

A0

オリジナルノード

2
2

2

B: ±4
B: ±4

D: ±7

2

C: +7,-17

E: ±104
D: +2,-12

E: +5,-15-

F: ±23

A: ±2

F: +18,-28

2

C

-

-

D: +2,-122

C: +7,-17

E: +5, -15

F
23
00

55

B

4

C

D
-

-

-

E
10

7

00

00

(a)更新伝播

-

00

55

E

-

12

00
-

F: +18,-28

A: ±2

A
B: ±4
D: +2,-1255

オリジナルノード

2

00

0→5
0→5

12

10
00

A0

2
2

F

0→5
0→5

7

2

23

B

D
-

A: ±2

A

C: ±12

0⇒5
0⇒5

-

更新データ

-

00

制御メッセージ(b)制御メッセージ伝播

図 5 UPDD-SO における更新伝播
Fig.5 Update propagation in UPDD-SO.

4.2.2 木構造の維持
UPDD-SOでは，UPDD-Sと同様に，ピアの参加や脱退に応じて，更新伝播木を維持する必要がある．各ノードは，OC
木上の親ノードと子ノードの情報（IPアドレスなど）に加え，各子ノードの子孫ノードであるピアのデータ要求条件を管理する．
ピアが更新伝播木に参加する場合，新規ピアは最初に，オ
リジナルノードに参加要求を送信し，新規ピアと同じデータ要求条件をもつピアを問い合わせる．オリジナルノードは，新規ピアと同じデータ要求条件をもつピアへと参加要求を伝播させる．
ピアが更新伝播木から脱退する場合，脱退ピアは，自身が参加するSC木の葉ノードに脱退要求を伝播させ，その葉ノードと位置を入れ替えることにより，更新伝播木から脱退する．

2000
1600
データ値

件の方が最小の絶対値が小さい場合，その子ノードの条件を親ノードに送信する（制御メッセージ）．たとえば，図5(a)のピアB0は，更新伝播先リスト内のピアD0とピアE0がこの時点では更新データを必要としていないため，更新データの伝播を停止し，自身の更新伝播先リストを更新する．その後，自身が次に更新データを受信する条件(±4)と，子ノードが次に更新データを受信する条件(+2, -12)および(+5, -15)を比較し，ピアB0自身よりも最小の絶対値が小さいピアD0の情報を，制御メッセージとしてピアA0に通知する（図5(b)）．
（4）制御メッセージを受信したピアは，メッセージに含まれるピアの情報を，自身の更新伝播先リストに追加する．たとえば，図5(b)のピアA0は, ピアB0の子孫ノードとして，ピアD0が次に更新データを受信する条件を追加する．その後，自身と更新伝播先リストに含まれる全てのピアの条件を比較し，その最小の絶対値が自身の条件よりも小さいピアが存在する場合，そのピアの情報を含む制御メッセージを親ノードに送信する．該当するピアが存在しない場合は，制御メッ
セージの伝播を停止する．図5(b)では，ピアA0の更新伝播先
リスト内に含まれるピアの中で，ピアA0の条件(±2)よりも最小の絶対値が小さいピアが存在しないため，ここで制御メッ
セージの伝播を停止する．

1200
800
400
0
0

200

400

600

800

1000

更新発生回数

Fig. 6図 6 データの更新度合い
Transition of the value of the originaldata.

5. 性能評価
本章では，提案手法の性能評価のために行ったシミュレー
ション実験の結果を示す．

5.1 シミュレーション環境
シミュレーション実験では，P2P ネットワークに参加する
ピア数を 1,000 とし，それらがべき法則(Power-Law
Random Graph: PLRG)[6]に従ってネットワークを構成するものとした．ここで，𝑖番目のピアの隣接ピア数𝑑 を以下の式で与え，一部のピアにリンクが集中する環境を実現した．

𝑑 = ⌊20 ∙ 𝑖⌋

データの種類を 100 とし，全ピアのうち，ピア番号が 1 から
100 までのピアが，それぞれデータ番号 1 から 100 のデータのオリジナルを所持するものとした．各ピアはそれぞれ，1
タイムスロット毎に 0.01 の確率であるデータを要求する．
要求するデータ番号の分布は Zipf 分布[7]に従うものとし，
データ番号が小さいデータに対する要求ほど頻繁に発生するものとした．具体的には，データ番号 j のデータの要求確率𝑞 を，以下の式で与えた．

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008

更新データ
3

制御メッセージ

木構造維持メッセージ3(×10 )
16
14
12
10
8
6
4
2
0

3

ネットワーク負荷(×10 )
16
14
12
10
8
6
4
2
0
200

400

600
800
更新回数

1000

200

(a)UPT-FT(×10 )
16
14
12
10
8
6
4
2
0
400

600
800
更新回数

200

1000

400

(b)UPDD-S

600
800
更新回数

1000

(c)UPDD-SO

図 7 ネットワーク負荷
Fig.7 Network load.

上式において，αはデータアクセス頻度の偏りを決定するパラメータであり，Zipf 係数と呼ばれる．シミュレーション実験では，Zipf 係数αは 0.5 とした．複製の配置方式には，オーナー複製法[2]を用いた．オーナー複製法では，データ要求が成功した際，クエリを発行したピアに複製を配置する．各
データのサイズは全て等しく，複製を保有可能な数は全てのピアで 10 とした．各ピアが複製を作成する際にデータ記憶
領域に空きがない場合は，LRU 方式に従って複製を置き換える．また，オリジナルデータは削除しないものとした．
各ピアは D 種類のデータ要求条件( × 1,
× 2, … ,×𝐷)の中からランダムに一つを選択するものとした．また，オ
リジナルノードは，初期値が 100 の数値データを所持し，図6 で示されるように，データの値を更新するものとした．データを更新する回数は，シミュレーション時間全体で更新頻度を変更し，200 回から 1,000 回まで変化させた．
オリジナルノードは，データ要求条件の大きさに応じて，5 つの OC 木を構築した．具体的には，データ要求条件が[1,20],[21,40],[41,60],[61,80],[81,100]のピアでそれぞれ OC
木を構築した．また，SC 木および OC 木はともに 2 分木とした．
更新データおよび更新伝播木維持の際に用いる各メッセージのサイズとして，更新データサイズを 10，木構造を維持するためにピア間で交換されるメッセージ（木構造維持メッセージ）および更新伝播時の制御メッセージのサイズを 1とした．以上の環境において，10,000 タイムスロットのシミュレーション実験を行い，データ要求条件を考慮せず木構造を用いて常に全ピアに更新データを伝播させる手法(UPT-FT)[5]と，UPDD-S および UPDD-SO における性能を評価した．UPT-FT に関しては，オリジナルノードのみ 5 つの子ノードをもち，それ以下の部分木は 2 分木となる更新伝
播木を構築した．ピアの参加，脱退時には，UPDD-S および
UPDD-SO における SC 木からの参加，脱退と同様の動作を行うものとした．
なお，実験では，アクセス頻度が最も大きいデータ番号 1のデータに注目して，このデータに関する評価値のみを調査した．ここで，データ番号 1 のデータを対象とした場合，更新データ伝播時の負荷や木構造維持に必要なメッセージ数

3(×10 )
12
UPDD-S (オリジナルノード)
UPDD-SO (オリジナルノード)
UPDD-S (他のピアの平均)
UPDD-SO (他のピアの平均)

10
データサイズ

𝑞 =∑

8
6
4
2
0
20

40

60

D

80

100

図 8 更新伝播負荷
Fig. 8 Update load.
は，すべてのデータの中で最も大きくなるが，他のデータに関しても，データ番号 1 のデータと同様の結果が得られる．

5.2 更新発生回数の影響
最初に，D=20 とし，更新発生回数を変化させた場合の，各 手法で伝播した更新データおよびメッセージのサイズの合計値を評価した．結果を図 7 に示す．図 7 において，横軸はデータの更新発生回数を表す．この図より，UPT-FT と比較して，UPDD-S および UPDD-SO では，更新データを必要としていないピアへの更新データの伝播を抑えることができるため，ネットワーク負荷が小さく抑えられていることがわかる．ここで，UPDD-S と UPDD-SO を比較した場合，
UPDD-SO におけるネットワーク負荷が増加していることがわかる．これは，UPDD-SO では，SC 木を構築，維持するための木構造維持メッセージや，データ更新時の制御メッセージを送受信する必要があるためである．さらに，
UPDD-SO において，更新データが OC 木に沿って伝播されるため，OC 木の葉ノードのみが更新データを必要としている場合でも，その間の節点に位置するピアにも更新データを伝播させなければならず，更新データ自体の伝播量も大きくなっている．

5.3 データ要求条件数の影響
次に，データの更新回数を 200 回とし，各ピアが設定するデータ要求条件の数 D の値を変化させた場合の，以下の値を日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008

評価した．
・オリジナルノードの更新伝播負荷
オリジナルノードが他のピアに 送信した更新データの合計サイズ
・オリジナルノード以外のピアの更新伝播負荷
オリジナルノード以外の複製所持ピアが他 のピアに送信した更新データの合計サイズの平均値
結果を図 8 に示す．図 8 において，横軸は D，縦軸はデー
タサイズを表す．ここで，UPT-FT では，他の手法と比べて伝播するデータのサイズが極端に大きくなるため，結果は省略している．
図 8 より，UPDD-SO は UPDD-S と比較して，オリジナ
ルノードの負荷が非常に小さく抑えられている一方で，他のピアの負荷が増加している．この結果より，UPDD-SO によって，データ更新に伴うオリジナルノードの負荷を他のピアに分散できていることがわかる．また，UPDD-SO では，Dの値が増加しても，オリジナルノードの負荷が大きくは増加していない．この結果から，各ピアが設定するデータ要求条件が増加しても，十分に負荷を分散できていることが確認できる．

[4] Wang, Z., Das, S.K., Kumar, M. and Shen, H.: “Update
propagation through replica chain in decentralized andunstructured P2P systems”, Proceedings of International
Conference on Peer-to-Peer Computing (P2P2007), pp.64–71(2004).
[5] Watanabe, T., Kanzaki, A., Hara, T. and Nishio, S.: “An
Update Propagation Strategy for Delay Reduction and Node
Failure Tolerance in Peer-to-Peer Networks”, Proceedings ofInternational Symposium on Frontiers in Networking with
Applications (FINA2007), pp.103–108 (2007).
[6] Admic, L.A., Lukose, R.M., Puniyani, A.R. and Huberman,
B.A.: “Search in power-law networks”, Physical Review E.,
Vol.64, No.4, 046135 (2001).
[7] Zipf, G.K.: “Human Behavior and the Principle of Least
Effort”, Addison-Wesley” (1949).

6. まとめと今後の課題

神崎 映光 Akimitsu KANZAKI

本論文では，データの更新量を考慮した二つの更新伝播手法を提案した．これらの手法では，更新データを必要としていないピアへの更新伝播を抑えることにより，更新伝播時の負荷を削減することができる．シミュレーション実験の結果から，提案手法によって，更新伝播に伴うネットワーク全体の負荷を削減できることを確認した．また，UPDD-SO では，
UPDD-S に比べよりオリジナルノードの負荷を軽減できることを確認した．
今後は，各ピアのデータ要求条件だけでなく，次に更新データを受け取る条件なども考慮して木構造を構築したり，更新伝播時に動的に木構造を組み替えることで，余分な更新伝播を少なくする方法を検討する予定である．

[謝辞]
本研究の一部は，文部科学省科学研究費補助金・特定領域研究(18049050)，文部科学省科学技術振興調整費「先端融合領域イノベーション創出拠点の形成：ゆらぎプロジェクト」，
および平成 20 年度総務省委託研究「ユビキタスサービスプ
ラットフォーム技術の研究開発」の研究助成によるものである．ここに記して謝意を表す．

[文献］[1] Cohen, E. and Shenker, S.: “Replication strategies in
unstructured peer-to-peer networks”, Proceedings of Special
Interest Group on Data Communicationsin (SIGCOMM2002),
pp.177–190 (2002).
[2] Lv, Q., Cao, P., Cohen, E., Li, K. and Shenker, S.: “Search andreplication in unstructured peer-to-peer networks”, Proceedingsof International Conference on Supercomputing (ICS2002),
pp.84–95 (2002).
[3] Datta, A., Hauswirth, M. and Aberer, K.: “Updates in highly
unreliable, replicated peer-topeer systems”, Proceedings ofInternational Conference on Distributed Computing Systems(ICDCS2003), pp.76–85 (2003).

渡辺 俊貴 Toshiki WATANABE
2007 年同大学院情報科学研究科博士前期課程修了．現在，同大学大学院情報科学研究科博士後期課程在学中．P2P ネット
ワークにおける複製管理に興味を持つ．電子情報通信学会，
情報処理学会，日本データベース学会の各学生会員．
2004 年大阪大学大学院情報科学研究科博士前期課程修了．
2005 年同大学院情報科学研究科博士後期課程中退後，同大
学院情報科学研究科マルチメディア工学専攻特任助手を経て，2007 年より同助教となり，現在に至る．博士（情報科学）．移動体ネットワーク，通信プロトコル，分散処理に興味を持つ．IEEE，電子情報通信学会，情報処理学会，日本
データベース学会の各会員．

原 隆浩 Takahiro HARA
1997 年大阪大学大学院工学研究科博士前期課程修了．同年
同大学院工学研究科博士後期課程中退後，同大学院工学研究
科情報システム工学専攻助手，2002 年同大学院情報科学研
究科マルチメディア工学専攻助手，2004 年より同大学院情報科学研究科マルチメディア工学専攻准教授となり，現在に至る．工学博士．データベースシステム，分散処理に興味を持つ．IEEE，ACM，電子情報通信学会，情報処理学会，日本データベース学会の各会員．

西尾 章治郎 Shojiro NISHIO
1980 年京都大学大学院工学研究科博士後期課程修了．工学博士．京都大学工学部助手，大阪大学基礎工学部および情報処理教育センター助教授，大阪大学大学院工学研究科情報シ
ステム工学専攻教授を経て，2002 年より大阪大学大学院情報科学研究科マルチメディア工学専攻教授となり，現在に至る．2000 年より大阪大学サイバーメディアセンター長，2003
年より大阪大学大学院情報科学研究科長，その後 2007 年より大阪大学理事・副学長に就任．データベース，マルチメディアシステムの研究に従事．現在，Data & Knowledge
Engineering 等の論文誌編集委員．本学会理事．電子情報通信学会，情報処理学会の各フェローを含め，ACM，IEEE な
ど 8 学会の各会員．

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月