Transcript P4P: Proactive Provider Assistance for P2P

P4P: Proactive Provider Assistance
for P2P
Haiyong Xie (Yale)
[email protected]
*This is a joint work with Arvind Krishnamurthy (UWashington) and Richard Yang (Yale).
Roadmap
Motivation
 P4P framework




Design rationale
System architecture
Computing peering suggestions
Evaluations
 Conclusion and future work

2007-5-25
1st NYC P2P Workshop
2
P2P : The Significant Bandwidth Consumer

Up to 60-70% of Internet traffic is contributed by
P2P applications [cachelogic]

Problems




2007-5-25
Scattered traffic
http://www.cachelogic.com
Increased network utilization
Degraded performance of other applications
Increased network operational costs
1st NYC P2P Workshop
3
Bandwidth Battle between ISPs and P2P
ISPs try to “manage”
P2P traffic




P2P tries to evade from
being captured
Upgrade network infrastructure
Deploy P2P caching devices
Rate limit P2P traffic


Use random ports
Encrypt traffic
The battle results in a lose-lose situation


2007-5-25
ISPs: increased financial and operational costs, increased
network utilization, degraded performance
P2P: increased complexity of P2P applications, reduced
interoperability, and impeded development of P2P
applications
1st NYC P2P Workshop
4
Objective:

Where are the problems?



Design a framework so that ISPs and P2P can
work together to achieve better results
ISPs do not disclose their network information for privacy
concerns
P2P does not have sufficient information to determine
network-aware peering relationships
ISPs can expose information to “guide” the peering
relationships in P2P systems to


2007-5-25
Improve the throughput of P2P users
Lower traffic costs for ISPs, balance traffic across the network
1st NYC P2P Workshop
5
P4P Framework – Design Rationale

Scalability




Privacy preservation
Try to improve performance for both ISPs and P2P
Extensibility




Support a large number of P2P users and networks in
dynamic settings
Application-specific requirements
Tracker-based vs. trackerless P2P systems
Gossip among peers
Incremental deploymentability
2007-5-25
1st NYC P2P Workshop
6
Design For Tracker-based P2P

Use BitTorrent in a single
ISP as an example



pTracker
2
pTracker keeps P2P
system states
iTracker makes
suggestions for peering
relationships
3
Information flow:




2007-5-25
iTracker
1. peer queries pTracker
2. pTracker asks iTracker
for guidance
3. iTracker returns highlevel peering suggestions
4. pTracker selects and
returns a set of active
peers, according to the
suggestions
4
1
ISP A
peer
iTracker can be run by third parties trusted by ISPs.
1st NYC P2P Workshop
7
Service Interfaces and States

Services provided by iTracker


Map an IP address to an opaque, privacy-preserving PID
PID = getpid(ip)
Compute peering suggestions for a given PID-based P2P state
[wij] = getpeering(PID-based-state)
wij : probability with which peers of PID i establish peering relationship with peers of
PID j

pTracker keeps states


2007-5-25
PID-peer state (updated by calling getpid() interface call)
P2P state (updated by collecting peer information)
PID
Peer list
PID
counter
upcap
downcap
……
……
……
……
……
……
i
pi
i
ni
ui
di
……
……
……
……
……
……
1st NYC P2P Workshop
8
How to Use iTracker Services

When a new peer joins the P2P network and queries the pTracker



pTracker gets the PID for this peer by calling getpid()
pTracker updates its internal P2P state
pTracker gets the PID-based peering suggestion [wij] by calling
getpeering()


pTracker selects a set of active peers according to [wij] and returns it
[wij] can be used to represent the peering relationships among peers,
and can be used to analyze performance

Original BitTorrent protocol selects peers randomly:
wij = nj / ∑nk

BitTorrent through caching (each PID has a caching peer only, and the
remaining peers in the same PID peers with the cache):
wij = 0 for non-caching peers and i≠j
2007-5-25
1st NYC P2P Workshop
9
Pros and Cons

Evaluate the design

Pros




Cons


2007-5-25
iTracker is stateless
Need no modification to P2P clients
Preserve privacy
Cannot handle trackerless P2P systems
Cannot handle gossip
1st NYC P2P Workshop
10
The Complete Design

iTracker’s responsibilities



iTracker
Keeps P2P system states
(PID-based, light-weight)
makes suggestions for
peering relationships
pTracker
Information flow:




2007-5-25
1. peers register or update
with iTracker
2. iTracker returns PID and
PID-based peering
suggestions
3. Peers exchange peer
information (with associated
PID information) through
gossips
4. Peers update peering
relationships according to the
received peering suggestions
3
ISP A
Peer a
1st NYC P2P Workshop
Peer b
11
How iTracker Works – Computing Peering
Suggestions

ISP’s model




P2P’s model




ISP’s network is a graph G=(V,E)
Link utilization be due to background traffic on edge e
Ie(i,j)=1 iff edge e is on the route from node i to j, determined by ISP’s
routing scheme
There are K P2P systems
Uploading/downloading capacity for all peers with PID i: uik, dik
Traffic uploaded from PID-i peers to PID-j peers: tijk
Peering suggestion

2007-5-25
Allow a certain number of random connections to ensure
robustness
1st NYC P2P Workshop
12
How iTracker Works – Computing Peering
Suggestions (cont’d)

Formulate as a joint optimization problem



2007-5-25
ISP’s objective: minimize maximum link utilization
P2P’s objective: maximize throughput
Joint optimization: min max link utilization for ISP when P2P throughput is
maximized
1st NYC P2P Workshop
13
How iTracker Works – Computing Peering
Suggestions (cont’d)

Naïve approach takes multiple
steps



Get optimal throughput Toptk for
each P2P system k by solving
its corresponding optimization
problem individually
Solve the ISP optimization
problem with constraints of
each P2P system’s throughput
being maximized
One-step approach through
duality transformation


2007-5-25
Apply dual transformation to
P2P optimization problem
Obtain a new optimization
problem by merging ISP and
dual P2P problems
1st NYC P2P Workshop
14
Roadmap
Motivation
 P4P framework




Design rationale
System architecture
Computing peering suggestions
Evaluations
 Conclusion and future work

2007-5-25
1st NYC P2P Workshop
15
Evaluation – Methodology

Simulations

Discrete-event simulation


a module for modeling BitTorrent protocol
a module for modeling underlying network topology and data
transfer dynamics using TCP rate equation
Network topology: PoP-level AT&T and Abilene
topologies
 Network routing: OSPF routing
PlanetLab experiments
 53 Internet2 nodes on PlanetLab
 iTracker for Abilene network
 Use OSPF routing to re-construct traffic load on Abilene
links


2007-5-25
1st NYC P2P Workshop
16
Evaluation – Abilene Simulation

Compared to P4P, native
P2P can result in




2x download completion
time
2x higher link utilization
Native P2P can result in
some peers experiencing
very long download
completion time
Native P2P can result in
much larger variance in
link utilization
2007-5-25
1st NYC P2P Workshop
17
Evaluation – AT&T Simulation

Compared to P4P, native
P2P can result in




1.6x download completion
time
3x higher link utilization
Some peers can
experience very long
download completion
time with native P2P
Link utilization variance
can be larger for native
P2P
2007-5-25
1st NYC P2P Workshop
18
Evaluation – Liveswarms on Planetlab


Liveswarms* is a P2P-based video streaming application,
which adapts BitTorrent protocol to video streaming context
Run liveswarms on 53 PlanetLab nodes for 900 seconds

P4P and native liveswarms
achieve roughly the same
amount of throughput

P4P reduces link load


Average link load saving is
34MB
Maximum average link load
saving is 60%


Native liveswarms:1Mbps
P4P liveswarms: 432Kbps
*Michael Piatek, Colin Dixon, Arvind Krishnamurthy, Tom Anderson. LiveSwarms: Adapting BitTorrent for end host
2007-5-25
multicast. Technical report: UW-CSE-06-11-01 1st NYC P2P Workshop
19
Conclusion and Future Work

Our design achieves the objective








Scalability: iTracker is light-weight, maintains necessary
states only
Privacy preservation
Extensibility
Robustness
Performance improvement for both ISPs and P2P
Incremental deploymentability
Implementation
Incentives
2007-5-25
1st NYC P2P Workshop
20
Questions?
2007-5-25
1st NYC P2P Workshop
21
Backup Slides
2007-5-25
1st NYC P2P Workshop
22
Computation cost is low


Among 34K+ swarms,
<1% have more than
100 leechers, and
about1% swarms
contribute to 50% of
traffic demand
Solution time of the
optimization problem is
linear to number of
swarms (slope ≈ 0.025)
2007-5-25
1st NYC P2P Workshop
23