Transcript Presentation - UCSB Computer Science

Exploiting super peers for largescale peer-to-peer Wi-Fi roaming
Efstratios G. Dimopoulos, Pantelis A. Frangoudis and George.C.Polyzos
Motivation






Very high Wi-Fi density in cities
The case for Skyhook
Residential Wi-Fi hotspots with excess capacity
How to exploit this user-provided
infrastructure?
We need a Wi-Fi sharing scheme!
Can community based Wi-Fi access
complement cellular?
2
Design options
Centralized
 Permanent IDs
 Full view of
transactions
 Easy to detect misuse
Decentralized
 Free/disposable IDs
 Enhances privacy
 Should discourage
misuse
FON
Our approach
3
Our approach
Design principle
 Users form a club that relies on indirect
service reciprocity
Distinct characteristics
 Fully decentralized
 No user registration
 Designed with off-the-shelf equipment in mind
 Does not assume altruists
4
Entities
Peer: provides service via home AP,
consumes when mobile
 Peer ID: uncertified public/private key pair
 Accounting unit: digital receipt

Signed by roaming user
 Proof of transaction


Receipt repositories
5
Receipts and the reciprocity
algorithm

Receipt generation



Storage



AP periodically requests fresh
receipt
Roamer sends signed receipt
Receipt repositories
Input to the reciprocity
algorithm
Contributor Public Key
Consuming member Certificate
Timestamp
Weight (amount of bytes relayed)
Member Signature
(Signed with member private key)
Algorithm output


Indirect Normalized Debt (IND)
Translated to QoS
6
Can it scale?
7
The locality of visits
Visits to foreign
areas are rare
 IND ≈0
 Receipts are
unvalued in
foreign areas

8
A Super-Peer-assisted
architecture
At least one Super
Peer per Area
Super Peers:
• Globally known
•
Trusted
•
Without extra
computational
capabilities
9
An algorithm for large-scale
roaming - Specification

The algorithm should run for all transactions
(not only for roaming ones)




Low Complexity
As few Super Peers as possible
Super peers should be used only when necessary
Incentive based

Normal users



To contribute service to Super Peers
To contribute service to roamers
Super Peers

To mediate other transactions
10
Example
Team Server
VSP HSP
calculates:
The
the
The VSP
runs runs
the reciprocity
1.reciprocity
The
IND
for the
The final
team
server
runs
in
algorithm
for algorithm
the
prospective
prospective
consumer.
the
reciprocity
order
to
calculate
the
consumer,
in
order
to
0,2xIND (VSP)algorithm
+ 0,8xIND(HSP)
IND for the
the quantity
prospective
calculate
(IND)
isconsumer
able toSP
guarantee.
2.that
Theheguarantor
for this
transaction.
Green Team
Team Server
Team Server
Team Server
Home Super Peer
HOME P2PWNC AREA
P2PWNC AREA
Visited Super Peer
According to the result he should not contribute service.
AP
Informs
The
He asks
asks
consumer
receipts
the
service
HSP
signs
from
from
(guarantor)
receipts
an
the
AP
SPuser’s
and
to
for
and
the
informs
his
the
SP
own
Team
and
the
use
the
Server
AP
and
SP
about
also
signs
oftothe
Simultaneously
Informs
asks
the
from
VSP
the
for
the
calculated
home
location
IND
SP
A
user
visits
a
foreign
area
So, he asks the SP of his home location to find a
11
from
provider
the
the
consumer
SP
receipts
about
of histhe
on
to
home
the
behalf
INDthe
AP
area
calculated
of
the for
SP the
calculate
the
same
quantity
and
waits
guarantor, in order to provide service to the user
Everyone is happy!

Roaming users have consumed service

The AP has gained the valuable
receipts of the SP

The SP helped a member of his area
and paid off his debt
12
Simulations




Input Parameters
Server Repository Size
Client Repository Size
Users Number






Areas Number
Area Population
Roaming probability
Number of stay rounds in the
foreign area(stop over rounds)
Contribution of the super peers
to IND
Number of super peers per
area





Output Parameters
SW
Hit Ratio
Requests to the super
peers
Super peers guarantees
13
Number of Regions Effect
Input Parameters
Num ber of Regions effect on Hit ratio
Client Repository Size=300 (receipts)
Number of peers=1000 (2x500 4x250 - 8x125 - 10x1000 20x50)
Roaming Start Round=5
Roaming Probability p=0.1
Stop Over Rounds=1
Super peers Participation=80% consumer
part. - 20% provider part.
Average Hit ratio
Server Repository Size=2000 (receipts)
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
Num ber of Regions effect on SW
Average SW per Match
Patience=20 (rounds)
0 2 4 6 8 10 12 14 16 18 20 22
Num ber of Regions
10
9
8
7
6
5
4
3
2
1
0
0
2
4
6
8 10 12 14 16 18 20 22
Num ber of Regions
NORMAL
NORMAL
ROAMERS
ROAMERS
NORMAL w ith Super Peers
NORMAL w ith Super Peers
ROAMERS w ith Super Peers
ROAMERS w ith Super Peers
Super Peers per Region=1
14
Server Repository Size Effect
Input Parameters
30%
20%
Super peers Participation=80% consumer part. 20% provider part.
Super Peers per Region=1
6
5
4
3
Server Repository Size (receipts)
Server Repository Size (receipts)
00
30
50
27
50
00
00
25
22
20
50
17
3500
00
00
3000
30
27
2500
50
00
2000
25
50
00
20
1500
22
50
1000
17
500
00
0
0%
50
1
0%
00
2
10%
0
Stop Over Rounds=1
Super peers help
40%
15
20%
Super peers requests
50%
00
40%
60%
12
60%
7
50
Average Hit ratio
70%
8
15
80%
Average SW per Match
80%
10
Roaming Probability p=0.1
ratio (%)
Client Repository Size=250
Roaming Start Round=5
9
90%
Server Repository Size=1000 (250) 3000
12
100%
10
100%
10
Patience=20(rounds)
Number of peers=1000 (4x250)
Server Repository Size effect on SW
Server
Repository
on HitPeers
Server
Repository
size Size
effecteffect
on Super
Ratio
Usage
Server Repository Size (receipts)
NORMAL
NORMAL
ROAMERS
ROAMERS
NORMAL w ith Super Peers
NORMAL w ith Super Peers
ROAMERS w ith Super Peers
ROAMERS w ith Super Peers
15
Participations of super peers in
the IND result
Input Parameters
Hom e Super Peer Participation
Effect on Hit Ratio
Patience = 20 (rounds)
Hom e Super Peer Participation effect on
SW
Receipts to merge = 300
Number of Peers = 1000 ( 4x250) - (20x50)
Roaming Start Round = 25
10
99%
98%
97%
96%
95%
0%
20% 40%
60% 80% 100%
Hom e SP participation
Roaming Probability p = 0.1
NORMAL w ith Super Peers
Stop Over Rounds = 1
ROAMERS w ith Super Peers
Average SW per Match
Repository size = 2000 (receipts)
Average request/consume
ratio %
100%
8
6
4
2
0
0%
20%
40%
60%
80%
100%
Hom e SP Participation
NORMAL
ROAMERS
super peers participation=variable
Super Peers per Region = 1
16
The effect of the number of
super peers per region
Input Parameters
Patience = 5 (rounds)
Super Peers per Region Effect on Hit
Ratio
Super Peers per Region effect on SW
10
Receipts to merge = 100
Number of Peers = 1000 ( 8x125)
Average SW per Match
Repository size = 500 (receipts)
Average Hit ratio
100%
95%
90%
85%
80%
0
Roaming Start Round = 1
1
2
3
Super Peers Per Region
NORMAL w ith Super Peers
Roaming Probability p = 0.1
ROAMERS w ith Super Peers
4
8
6
4
2
0
0
1
2
3
4
Super Peers Per Region
NORMAL
ROAMERS
Stop Over Rounds = 1
super peers participation (Home Visited)=80% - 20%
Super Peers per Region = 1,2,3
17
Scale Effect
Input Parameters
Scale effect on Hit Ratio
Scale Effect on SW
Patience = 20 (rounds)
100%
10
Average SW per Match
Repository size = 1500 (receipts)
Receipts to merge = 250
Number of Peers = (4x250) (10x250) (20x250) (28X250)
Roaming Start Round = 1
Average Hit Ratio
90%
80%
70%
60%
50%
Roaming Probability p = 0.1
6
4
2
0
0
2000
4000
6000
Num ber of Peers
Stop Over Rounds = 2
8
Series1
Series2
8000
0
2000
4000
6000
Num ber of Peers
Series1
Series2
super peers participation (Home - Visited)=80% - 20%
Super Peers per Region = 1
18
8000
THE END
Thank you!
19