Contents• P2P file-sharing system– Importance and problem of cooperative caching

A Caching Algorithm using Evolutionary
Game Theory in a File-Sharing System• Research objects• Evolutionary game theory• ModelingM d li P2P filfile-sharing
h i as caching
hi game– Demand and cost for caching– Selfish user behavior

Masahiro Sasabe,
Naoki Wakamiya, Masayuki Murata
Osaka University, Japansasabe@comm.eng.osaka-u.ac.jp
2007/7/3

ISCC 2007• Derivation of the number of cache files instationary state using evolutionary game theory– Replicator dynamics– Agent-based dynamics1

2007/7/3

P2P file-sharing system
filepeer• Caching a file incurs cost
– processing load, storage capacity• Some nodes may not be cooperative to cache files– Files and messages travel
over the logical network• Each node caches files
and shares them withothers– Other nodes cannot use the file due to disappearance
Performance improvement• File availability• Search latency– Files are original or
retrieved from others• A mechanism to accomplish effective caching isrequired– It is difficult to monitor and manage all nodes– Can the effective caching emerge from autonomous andselfish node behavior?

• Cooperatively caching afile on multiple nodes
enhances the system
performance
2007/7/3

ISCC 20073

2007/7/3

ISCC 2007

Research object

1. Model caching in a file-sharing system
as a caching game between two nodes• demand and cost for caching– We model caching in a file-sharing system as acaching gamecaching gamepeer• We take into account the cost and benefit of caching as
foff users
selfishness– We clarify the relationship between the model and thenumber of cache files• How does individual behavior affect system performance?
• Is it possible that selfish node behavior leads to cooperative
caching?
• Evolutionary game theoretic approach
ISCC 2007

4Research overview• Proposal of a mechanism to accomplish effective
caching in file-sharing systems

2007/7/3

2

Problem of cooperative cachingoverlay link

• A logical network isconstructed byestablishing logical links
among nodes

ISCC 2007

5disappearance
fileoverlay link
2. By using evolutionary game theory,
we clarify the caching condition in a steady state• relationship between the model and effective caching
2007/7/3

ISCC 200761

Evolutionary game theory

General game• What is evolutionary game theory?

• A game between two players is defined as apayoff matrix– It tries to figure out the evolutionary process oforganisms by game theory– Superior genes yield much offspring– Superiorpstrategies
gacquireq
more ppayoffsy• Individual strategy = behavior defined by a gene
• Payoffs acquired by a strategy = number of offspring– ex) (S，T)• A defector exploiting a cooperator gets T• The exploited cooperator receives S• Evolutionary game theory provides us with aframework to investigate the following
characteristics– Well known games• Prisoner’s Dilemma Game: T>R>P>S• Snowdrift Game: T>R>S>P– Strategy distribution in a steady state– Condition to reach the steady state
2007/7/3

ISCC 20077

2007/7/3

ISCC 20078

Derivation of strategy distribution
in a steady state

Caching game• We model caching in a file-sharing system as acaching game between two neighboring nodes• Replicator dynamics– Two strategies (caching, no caching)• We assume a file-sharing system consists of multiple cachinggames each of which deals with a single file

– Benefit for caching• Satisfaction obtained by the use of the file : b– Mathematical model of a phenomenon where asuperior strategy increases– It can be applicable when the number of individuals is
relatively large and the network among them is meanfield like• full-mesh network, global information– Cost for caching• Agent-based dynamics• Processing load: cl (Tab.2)• Storage capacity: cs (Tab.3)– Simulation-based model of a phenomenon that asuperior strategy spreads over the network in a hopby-hop manner• various network, local information

2007/7/3

ISCC 20079

2007/7/3

ISCC 2007

Replicator dynamics

Replicator dynamics- overview -- derivation process -10• Average payoffs of cooperators• The number of individuals increases inproportional to the superiority of the strategy– Rx + S (1 − x)

– superiority=average payoffs acquired by the strategy –average payoffs• Average payoffs of defectors– Tx + P (1 − x)

• Averageg ppayoffs
yof the whole nodes• Derivation process in a general game (Tab. 1)– x{Rx + S (1 − x)} + (1 − x){Tx + P (1 − x)}– ratio of cooperators: x– ratio of defectors: 1-x• Superiority of cooperators– {( R + P − T − S ) x + S − P}(1 − x)

• Replicator dynamics– x& = {( R + P − T − S ) x + S − P}(1 − x) x
2007/7/3

ISCC 200711

2007/7/3

Growth rate depends on the strategy’s superiority
ISCC 2007

122

Replicator dynamics

Replicator dynamics- equilibria -- Characteristics of caching games -• Replicator dynamics• Cost-to-benefit ratio of mutual cooperation: r• Relationship between r and x– x& = {( R + P − T − S ) x + S − P}(1 − x) x

• Equilibria

x = 0, 1,– By substituting x& = 0P−S
R + P −T − S– cost: load– 0 ≤ x ≤ 1 → (1 − x) x ≥ 0– From the definition of the caching gameP−S( R + P − T − S ) x + S − P > 0 if x <R + P −T − SP−S
( R + P − T − S ) x + S − P < 0 if x >R + P −T − SP−S– Stable equilibria (steady state) x =R + P −T − S
2007/7/3
ISCC 2007b − 2clc, r= lb − clb − clx=

• Stabilityy of equilibria
qin the cachinggg
game– cost: storage
x=b − csc, r= sbb − cs•13

2007/7/3

ISCC 2007– If Aj>Ai, node i imitates the strategy of node j with thefollowing probability• Number of nodes: 1000
• Network topologies– scale-free network based on BA model– waxman random network (α=0.15, β=0.2)– m=2, 4• Caching Costs cl and cs are set to 1– From the definition of r, benefit b is b = 1 + rr

• Initial strategy distribution is fifty-fifty• Simulation results are average over twenty
simulations in steady states

A j − Ai
T −P

– Otherwise, it does not change its strategy
Strategy is imitated in accordancewith its superiority
ISCC 200715

2007/7/3

ISCC 2007

Evaluation criteria

16

Impact of cost model• File availability

File availability

Search latency• Number of cache files is product of x and the number of nodes

4.5

hop count to the closest provider1– Ratio of nodes taking the strategy “caching:” x0.8

• Search latency
x0.6– Average hop count between a node to its closest
provider including itself– If a file disappears from the system, we alternatively
use the maximum hop count between two arbitrary
nodes

0.4

AD (load)
AD (storage)

0.2

RD (load)
RD (storage)

0

ISCC 200717

AD (load)
AD (storage)

4
3.5
3
2.5
2
1.5
1
0.5
00

0.2

0.4

0.6

0.8

10r

2007/7/3

0.2

0.4

0.6

0.8

1r

•AD:
File availability
agent-based dynamics
networkachieves(m=4) high•Cost•scale-freemodel of storage•RD:
replicator dynamics
file-availability

2007/7/3

14Simulation model

1 Select Node j randomly from neighboring nodes for1.
comparison of their payoffs
2. Decide the next strategy

2007/7/3

1
1+ r• x deteriorates with the increase of r (decrease of demand b)• cost model of load causes file disappearance when r = 1• cost model of storage achieves high file-availability

Node i plays a game once with all neighboring
nodes (one generation)
It determines the strategy of the next generation
based on average Ai of payoffs acquired

PA (i, j ) =x=– characteristics

Agent-based dynamics•x = 1− r

Searchlatency dynamics•AD:
agent-based•Searchlatencynetwork
increaseswith•scale-free(m=4)
growthof r•RD:replicatordynamics•Cost model of storage suppress theincrease of search latency

ISCC 2007183

Impact of network structure

Impact of network structure- average degree -- degree distribution -File availability

Search latency

File availability04
0.4
AD (load), m=2
AD (load), m=4AD (storage), m=2AD (storage), m=40.2

03

0.8

0.6

2.5
20.4
AD (load), scale-free
AD (load), random
0.2 AD (storage), scale-free

1.5
10.2

0.4

0.6

0.8

100r

File
availability•Scale-free
network (m=2, 4)•Smaller m promotes to increase highdemand files

0.2

0.4

0.6

0.8

1

•High degree nodes tends to acquire more
payoffs and be imitated•The impact of high degree nodes isaccelerated by their surrounding low degree
2007/7/3
ISCC 2007
nodes

0.2

0.4

0.6

0.8121.5
10r

193
2.500r•Scale-freenetwork (m=2, 4)
Search latency•In the cost model of storage, thedifference of m does not affect somuch

AD (load), scale-free
AD (load), random
AD (storage), scale-free
AD (storage), random

43.5

0.5

AD (storage), random

0.500

hop to tthe closest provider

x0.6

AD (load), m=2
AD (load), m=4
AD (storage), m=2
AD (storage), m=44
3.5

4.5

x0.8

Search latency

14.5

hop count tto the closest provider

10.4

0.60.81r•Scale-free
network (m=4)
File availability•Random
network(m=4)•Scale-free
networkslightly
encourages nodes to cooperatively
behave2007/7/3

0.2•Scale-free
network (m=4)
Searchlatency
network••Random
Search latencyis (m=4)
not much affectedby the difference of degree
distribution

ISCC 200720

Conclusions and future work
• Conclusions– We investigated effective caching in a file-sharing
system by using evolutionary game theory• We first modeled caching in a file-sharing system as a cachinggame between two nodes• We derived the relationship between models and the number
y stateof cache files in a steady– Theoretical approach by replicator dynamics– Simulation-based approach by agent-based dynamics• The cost model of storage could achieve a file-sharing systemwith high file-availability and low search-latency independentlyof the network structure• Future work
– Caching game taking into account combination ofmultiple costs including dynamic costs
2007/7/3

ISCC 2007

214