Transcript Teams - Mobile Multimedia Laboratory

Peer-to-Peer Wireless Network Confederation
(P2PWNC)
George C. Polyzos
Mobile Multimedia Laboratory
Department of Computer Science
Athens University of Economics and Business
http://mm.aueb.gr/
P2P colloquium, Darmstadt, December 7, 2005
[email protected]
Idea
A wireless LAN (WLAN) aggregation scheme
Unites WLANs in citywide [con]federations
 Requires no authorities: open to all, IDs are free
 Relies on reciprocity between peers

Motivation

Numerous WLANs, connected to the Internet,
are within the range of passersby
Manhattan WLANs, 2002
Skyhook Wireless Wi-Fi Positioning System (WPS)
[email protected]
Motivation
Motivation (II)
Many WLANs are secured against outsiders
 Need incentives to keep them open

Motivation (III)

WLAN-enabled mobile phones are on the market
Motivation (IV)
Public WLAN operators mainly target “hotspots”
 Municipal wireless
still in its infancy

[email protected]
Motorola
CN620
Nokia 9500
The Public Hotspot Market
From Gartner:
2001: 1200 public hotspots worldwide
 2003: 71 000 public hotspots worldwide
 2005: 23 500 WLANs in hotels worldwide

A subscription buys you (June 2005):
Sprint PCS: 19 000 hotspots worldwide
 Boingo Wireless: 17 400 hotspots worldwide
 T-Mobile HotSpot: 16 663 hotspots worldwide

Skyhook Wireless data (2005):

[email protected]
50 000 WLANs in just 5 Massachusetts
cities and towns (Watertown, Brookline,
Roxbury, Newton, and Cambridge)
The Rules
P2PWNC: An incentives-based P2P system
Teams provide WLAN access to each other
 Teams should provide in order to consume

Blue
team
White
team
Green
team
: WLAN access point
: team member
[email protected]
WLAN view
Team view
N-way Exchanges
Adopt N-way exchanges as the incentive scheme





A generalization of barter, which retains some of its simplicity
“Provide to those [who provided to those]* who provided to me”
A type of (cyclical) indirect reciprocity
Scales to larger communities, compared to direct-only exchanges
Does not rely on (central or distributed) authorities
A
B
C
D
Some variants of the basic N-way scheme:
Cox, Noble, “Samsara: Honor Among Thieves in P2P Storage,” SOSP’03
Ngan, Wallach, Druschel, “Enforcing Fair Sharing of P2P Resources, “ IPTPS’03
Anagnostakis, Greenwald, “Exchange-based Incentive Mechanisms for P2P File Sharing,” ICDCS’04
Feldman, Lai, Stoica, Chuang, “Robust Incentive Techniques for P2P Networks,” ACM EC’04
[email protected]
Versions
Architecture
Version 1.0
(MMAPPS)
Incentive technique
Comment
MMAPPS local accounts
pattern
Relied on
tamperproof
software
NWAY1
Favors large teams,
unimplemented
Version 2.0
GMF2
Assumes
homogeneous
consumptions
Version 3.0
(in progress)
in progress
More realistic
assumptions
1. E. C. Efstathiou and G. C. Polyzos, “Self-Organized Peering of Wireless LAN Hotspots,” European
Transactions on Telecommunications, vol. 16, no. 5, (Special Issue on Self-Organization in Mobile Networking),
Sept/Oct. 2005. [12% acceptance rate]
2. E. C. Efstathiou, P. A. Frangoudis, and G. C. Polyzos, “Stimulating Participation in Wireless Community
Networks,” IEEE INFOCOM 2006, Barcelona, Spain, April 2006 (to appear). [18% acceptance rate]
[email protected]
Version History

Sept. 2002: P2PWNC started in the context of IST MMAPPS (Market
Management of Peer-to-Peer Services)

Sept. 2003: Demo of version 1.0
Team 1 (5 persons from AUEB)
Theory Team (2 persons from AUEB)

June 2005: Demo of version 2.0
Team 2 (3 persons)
Results will be presented at IEEE INFOCOM, Barcelona, April 2006

Oct. 2005: Started work on version 3.0
Team 3 (7 persons)
Preparing demo for TRIDENTCOM 2006 and/or INFOCOM 2006
[email protected]
System Entities
Team = Members + Access Points (APs)
Teams := P2PWNC peers
 Assume intra-team trust
 Team ID = (unique) PK-SK pair

PK: public key
SK: private key
Member certificate
Member ID = (unique) PK-SK pair
 Member certificate binds Member PK to Team PK

Receipt
Encodes P2PWNC transactions between teams
 Signed by consuming member
 Receipt weight: amount of bytes the AP forwarded

[email protected]
Member PK
Team PK
Signed by Team SK
Team PK
Member cert
Timestamp
Weight
Signed by
Member SK
Receipt Generation
11:50am = t0 (member connects)
11:51am (P requests 1st receipt)
CONN
RREQ
C
P
C
P
CACK
RCPT
RCPT timestamp = t0
RCPT weight = w1
11:52am (P requests 2nd receipt)
11:53am (member has departed)
RREQ
C
P
RCPT
RCPT timestamp = t0
RCPT weight = w2 > w1
[email protected]
RREQ
(timeout)
Receipt
Repository
P
RCPT
P stores last receipt
P2PWNC Protocol: Entities and Messages
Access Point
Mobile User
Repository
CONN
QUER
CACK
QRSP
RREQ
RCPT
RREQ
Timeout/
Conn. closed
RCPT P2PWNC/2.0
Content-length: 357
Algorithm: ECC160
Timestamp: Tue, 24 May 2005 17:26:41 +0000
Weight: 6336
BNibmxStfJlod/LnZubH6pzWHQqKyZFcSMjnZurmTe4KjCRkllhV93MEegPv
Csxz2oe/hqevoPSrwO1JLO/36J8HTIeyeKQqTCfx+EPxweAvYC/ZFb8URLa2
faIbvSgD3lm6Wa1S4cYlSWeSNmFzS/ebDFfzakqNSEsERefwEcdWJD9gzIXa
fL4pojhhfP5brS4QPtHzBl58POfKdx9AqCDMBxRoGALKJSJYYXlsrwtiyZJK
vPlU5B3lWrFuL25Pd+kv2iMVRElXk/4=
RCPT
Text-based protocol. Certificates and keys encoded in Base64.
[email protected]
Centralized Operation Mode
One RR (Receipt
Repository) for all
teams.
- Susceptible to DoS in
layer 3 and in app. layer
(overflow RR with fake
receipts)
- Confederation teams
may be unable or
unwilling to agree on the
same RR, dividing the
confederation
+ Simpler to deploy and
bootstrap
[email protected]
Decentralized Operation Mode
One RR (Receipt
Repository) per team
(running on the “team
server”).
+ Not susceptible to DoS
(IP address known only
within the team) and only
team members talk to it
- Needs gossiping
mechanism (which uses
the members themselves
to carry receipts around)
- Partial views of
confederation history can
favor free-riding
[email protected]
The Receipt Graph
Directed weighted graph (with cycles)
W1
E
F
W2
W5
Graph security
W4
W3
B
W6
W9
W7
A
Free-riders and colluders can create
an arbitrary number of fake vertices
and edges
G
W14
I
W8
W13
W10
W11
D
C
H
They cannot create fake outgoing
edges starting from teams who are
outside the colluding group (they do
not have the relevant private keys)
W12
Vertices: team public keys
Edge weight: sum of weights of corresponding receipts
Edges point from the consuming team to the providing team
[email protected]
GMF - Background
Directed weighted graph (with cycles)
W1
E
F
W2
W5
Graph security
W4
W3
B
W6
W9
W7
A
Free-riders and colluders can create
an arbitrary number of fake vertices
and edges
G
W14
I
W8
W13
W10
W11
D
C
H
They cannot create fake outgoing
edges starting from teams who are
outside the colluding group (they do
not have the relevant private keys)
W12
Vertices: team public keys
Edge weight: sum of weights of corresponding receipts
Edges point from the consuming team to the providing team
[email protected]
GMF - Heuristic
Directed weighted graph (with cycles)
W1
E
F
W2
W5
Graph security
W4
W3
B
W6
W9
W7
A
Free-riders and colluders can create
an arbitrary number of fake vertices
and edges
G
W14
I
W8
W13
W10
W11
D
C
H
They cannot create fake outgoing
edges starting from teams who are
outside the colluding group (they do
not have the relevant private keys)
W12
Vertices: team public keys
Edge weight: sum of weights of corresponding receipts
Edges point from the consuming team to the providing team
[email protected]
GMF - Evaluation
Directed weighted graph (with cycles)
W1
E
F
W2
W5
Graph security
W4
W3
B
W6
W9
W7
A
Free-riders and colluders can create
an arbitrary number of fake vertices
and edges
G
W14
I
W8
W13
W10
W11
D
C
H
They cannot create fake outgoing
edges starting from teams who are
outside the colluding group (they do
not have the relevant private keys)
W12
Vertices: team public keys
Edge weight: sum of weights of corresponding receipts
Edges point from the consuming team to the providing team
[email protected]
[email protected]
[email protected]
IST MMAPPS version (Version 1.0)
P2PWNC Domain Agent Application
WLAN events
WLAN service calls
WLAN Provisioning Service
[email protected]
Network Services
MMAPPS and JXTA
Firewall
Packet sniffer
Negotiation
DHCP
Routing / NAT
Rate control
Authentication
Accounting
Rules
IST MMAPPS version (Version 1.0)
1. Visitor credentials check
WLAN
WLAN
(visitor password resides in home database)
6. Balance OK: Proceed
Visitor
Negotiation
Visitor
Session
Visitor
Negotiation
5. Start
MMAPPS
Negotiation
2. Negotiate
Negotiation
Listener
3. Request service
4a. MMAPPS negotiation
MMAPPS
Negotiation
4b. Balance check
Visited peer - Provider
[email protected]
Home peer - Consumer
First attempts at Linux-based WLAN mgmt:
AAA, DHCP, NAT, QoS, …
[email protected]
First attempts at Linux-based WLAN mgmt:
Traffic logging using (fast) kernel, user modules
[email protected]
First simple rules
(tamperproof software!)
[email protected]
First experiments with PDAs
and Linux WLAN gateways
[email protected]
Version 2 Architecture
Receipt store
GMF execution
Member update
(decentralized
mode)
Home-AP interface
DHCP
NAT/router/firewall
Standard PC, or
collocated with Linksys
Authenticator
Receipt verification
Linksys WRT54GS AP
(32MB RAM, 8MB Flash)
Member-AP interface
Windows Mobile client
Member certificate
.
Receipt generation
Member-Home interface
[email protected]
Also carries team receipts
(decentralized mode)
Linksys WRT54GS
Linux-based WLAN access point





[email protected]
We implemented the P2PWNC protocol (AP side) on it
32 MB RAM, 8 MB Flash, 200 MHz CPU
Retails for less than $70
Cryptographic, maxflow performance comparable to 200 MHz PC
Can act as team server/RR (storing more than 10 000 receipts)
Repository Implementation
(Version 2.0)
• Receipt Repository
– Efficient, composite data
structure for receipt
storage and queries
– Incentive algorithms:
pluggable modules
– maximum-flow algorithm
optimizations
• Push-Relabel Algorithm O(V3)
• Global relabeling
heuristic
[email protected]
Linksys verification performance compared
to a 2GHz PC for all P2PWNC signature types
Athlon XP 2800
Linksys WRT54GS
Bit length
(RSA/ECC)
RSA
ECC
RSA
ECC
1024/160
0.4 ms
6.5 ms
12.3 ms
114.7 ms
1536/192
0.8 ms
6.0 ms
21.4 ms
99.9 ms
2048/224
1.3 ms
7.1 ms
37.9 ms
135.7 ms
3072/256
2.8 ms
8.6 ms
75.3 ms
453.0 ms
[email protected]
QoS Scheme for version 3.0
Reinterpret the result of
GMF not as probability
to provide unrestricted
service but as the QoS to
be provided
P2PWNC Team/TCA Server
Abstraction Layer (AL)
Linux
Module
MS
Windows
Module
OS - Internet Link
[email protected]
Proposal
Build traffic policing
module for both
Windows and Linuxbased (tc-based) routers
Secure Services (version 3.0)
Internet
Home AP 1
Home AP 2
Internet
Visited AP 1
Internet
Team
Server
1
Team
Server
2
Visited AP 2
GSM
Wireless Client 1
Wireless Client 2
Each client uses its own tunnel endpoint for scalability (usually their own home).
Client can learn the endpoint’s current IP address from his team server.
Caller sends SMS containing current tunnel endpoint IP address and a tunnel
identifier. No centralized registrars are needed (e.g. SIP registrars, dynamic DNS).
[email protected]
L2TP IPSec Tunnels
Client side support: Windows, Windows Mobile
Server side support: Linux (and Linksys), Windows
[email protected]
NAT traversal a problem for IPSec, but:
IPSEC-ESP-RFC 3948: UDP encapsulation of IPSec ESP Packets
(used after a NAT detection process detects a NAT)
Support for NAT-T in Windows, Windows Mobile and in the
Openswan Linux VPN gateway that we are using
[email protected]
VoIP for Windows Mobile (version 3.0)
[email protected]
Deployment: the Athens Wireless
Metropolitan Network
[email protected]
AWMN and P2PWNC
AWMN is one of the largest WMNs globally, with more than 3000 nodes
P2PWNC version 3.0 is designed to be compatible with most AWMN nodes
Setup of AWMN Node #66 in MMlab is finally underway!
[email protected]
P2PWNC Publications and Website
1. E. C. Efstathiou and G. C. Polyzos, “Self-Organized Peering of Wireless LAN Hotspots,” European Transactions on
Telecommunications, vol. 16, no. 5, (Special Issue on Self-Organization in Mobile Networking), Sept/Oct. 2005. [12% acceptance
rate]
2. E. C. Efstathiou and G. C. Polyzos, “Peer-to-Peer Wireless Network Confederation,” in Encyclopedia of Virtual Communities
and Technologies, S. Dasgupta, ed., Idea Group Reference, 2005.
3. E. C. Efstathiou and G. C. Polyzos, “P2PWNC: A Peer-to-Peer Approach to Wireless LAN Roaming,” in Handbook of Wireless
Local Area Networks: Applications, Technology, Security, and Standards, M. Ilyas, S. Ahson, eds., CRC Press, 2005.
4. E. C. Efstathiou, P. A. Frangoudis, and G. C. Polyzos, “Stimulating Participation in Wireless Community Networks,” IEEE
INFOCOM 2006, Barcelona, Spain, April 2006 (to appear). [18% acceptance rate]
5. P. A. Frangoudis, E. C. Efstathiou, and G. C. Polyzos, “Reducing Management Complexity through Pure Exchange Economies:
A Prototype System for Next Generation Wireless/Mobile Network Operators,” 12th Workshop of the HP Openview University
Association (HPOVUA), Porto, Portugal, July 2005.
6. E. C. Efstathiou and G. C. Polyzos, “Can Residential Wireless LANs Play a Role in 4G?” 4G Mobile Forum (4GMF) Annual
Conference, San Diego, CA, July 2005.
7. E. C. Efstathiou and G. C. Polyzos, “A Self-Managed Scheme for Free Citywide Wi-Fi,” IEEE WoWMoM Autonomic
Communications and Computing Workshop, Taormina, Italy, June 2005.
8. E. C. Efstathiou, “Self-Organized Peering of Wireless LANs,” IEEE INFOCOM 2005 Student Workshop, Miami, FL, March
2005.
9. E. C. Efstathiou and G. C. Polyzos, “Trustworthy Accounting for Wireless LAN Sharing Communities,” 1st European PKI
Workshop, Samos Island, Greece, June 2004.
10. E. C. Efstathiou and G. C. Polyzos, “Designing a Peer-to-Peer Wireless Network Confederation,” IEEE LCN Workshop on
Wireless Local Networks (WLN), Bonn, Germany, Oct. 2003.
11. P. Antoniadis, C. Courcoubetis, E. C. Efstathiou, G. C. Polyzos, and B. Strulo, “Peer-to-Peer Wireless LAN Consortia:
Economic Modeling and Architecture,” 3rd IEEE International Conference on Peer-to-Peer Computing, Linköping, Sweden, Sept.
2003.
12. E. C. Efstathiou and G. C. Polyzos, “A Peer-to-Peer Approach to Wireless LAN Roaming,” ACM MOBICOM Workshop on
Wireless Mobile Applications and Services on WLAN Hotspots (WMASH), San Diego, CA, Sept. 2003.
13. P. Antoniadis, C. Courcoubetis, E. C. Efstathiou, G. C. Polyzos, and B. Strulo, “The Case for P2P Wireless LAN Consortia,”
12th IST Summit on Mobile/Wireless Communications, Aveiro, Portugal, June 2003.
http://mm.aueb.gr/research/p2pwnc/
[email protected]