Transcript Slide 1

Measurement and Estimation of
Network QoS among Peer Xbox Game
Players
Youngki Lee, KAIST
Sharad Agarwal, Microsoft Research
Chris Butcher, Bungie Studio
Jitu Padhye, Microsoft Research
• A series of online multiplayer game via Xbox Live
▫ First Person Shooter (FPS) game
▫ 15 million copies sold worldwide
• We focus on Halo 3 for data collection and analysis.
▫ Halo 3 has a large set of widely distributed player population.
▫ released on September 25, 2007.
2
P2P architecture of Halo
 Xbox console
3
P2P architecture of Halo
• P2P, a peer as a server
• Network QoS between the server peer and other client peers
is important for game quality.
▫ excellent experience: latency (< 50ms), BWXbox
(50~70Kbps).
Live
matchmaking
minimum
▫ Xbox
consolerequirement: latency (< 150ms), BW (>30Kbps).
service
QoS probing among peers
Probing using the
packet-pair technique
Query: Give me a list of
hosts that satisfy my criteria
Candidate hosts
Xbox Live
matchmaking service
5
Motivation
• Understand network path quality (NPQ) among peer game
players and characteristics of the players
▫ NPQ in terms of network delay and capacity
• Address the problem of NPQ measurement overhead
▫ improve user pre-game experience
 probe fewer, better candidate hosts
• Limited publications on large-scale E2E network characterization
▫ Planetlab-based end-to-end NPQ studies: O(100) nodes
▫ king-based end-to-end NPQ studies O(1000) nodes
▫ several studies of provisioned server based games
6
Methodology
1. Collect probe data among peer game players
a) consoles report the probe results back to Xbox live service.
2. Understand characteristics of peer game playing
3. Understand NPQ between peer game players
4. Examine stability and predictability of NPQ
a) propose three simple predictors

IP history, prefix history, geography
b) examine robustness of the predictors
7
Outline
• Background
• Motivation
• Analysis on probe data
▫ general characteristics
▫ NPQ results
• NPQ prediction
▫ IP history predictor
▫ prefix history predictor
▫ geography predictor
• Conclusion
8
Data
• Session data (per game attempted)
▫ time, session-id, src IP
• NPQ measurement data (per probing to a host)
▫
▫
▫
▫
session-id, dest IP
# of packet-pairs sent, # of packet-pairs rcvd
minimum and median latency
average downstream and upstream capacity
• Player locations calculated from their IP addresses
▫ MaxMind database provides mapping between locations and
IP addresses
9
Basic statistics
11.14.2007  1.3.2008 (50 days)
sessions
39,803,350
5,658,951
distinct IPs
126,085,887
total probes
• 126 million probes among 5.6 million IP addresses !!!
10
Geographic distribution
85% in USA
13% in Europe
2% in Asia,
Australia
11
Player characterization
• Strong diurnal pattern (peaks between 2 ~ 8PM, UTC time)
• Most players played a few games, only some a lot
• Probe distribution per game trial (session)
▫ 90% of sessions probed fewer than 10 hosts, but some a lot.
cumulative freq.
(sessions)
1
0.9
0.1
1
10
100
# of probes
12
1000
Delay distribution
• 25% of the delay measurement are above 150ms.
▫ 150 ms: upper bound for responsive experience in FPS games.
1
25%
cumulative freq.
(probes)
0.75
0.1
0.01
1
10
150
100
1000
delay (ms)
13
10000
Capacity distribution
• Peaks around typical broadband capacities in USA.
frequency (x 1,000,000)
(probes)
▫ marginal error due to the packet pair technique.
6
10Mbps
192Kbps
5
4
3
2
1.6Mbps
1
5.8Mbps
0
0
2000
4000
6000
capacity (Kbps)
14
8000
10000
Outline
• Background
• Motivation
• Analysis on probe data
▫ general characteristics
▫ NPQ results
• NPQ prediction
▫ IP history predictor
▫ prefix history predictor
▫ geography predictor
• Conclusion
15
Predictors
• Predict NPQ without probing
▫ to disqualify a host, select a host, do quick re-probe
▫ potentially reduce the user-wait time and probe traffic
• IP/Prefix history predictor
▫ reuse the previous probe results between the same IP pair
▫ reuse results between two peers within the same prefix pair
 determine prefixes by BGP table (12/27/2007 RouteViews)
• Geography predictor
▫ predict delay or capacity based on the geographic distance
16
IP history predictor (delay)
• Delays are very consistent over time, even for 50 days
▫ excellent predictor for delay
1
Within 5 min
Within 30 min
0.6
Within 6 hr
0.4
Within 1 day
No Constraints(50 days)
0.2
• CV= Stdev/Mean, small CV = small variation
17
1.9
More
coefficient of variation (CV)
1.7
1.5
1.3
1.1
0.9
0.7
0.5
0.3
0
0.1
cumulative freq.
(src-dst IP pairs)
0.8
IP history predictor (capacity)
• Capacities are also quite consistent over time.
▫ decent predictor for downstream capacity
0.8
Within 5 min
Within 30 min
Within 6 hr
Within 1 day
No Constraints (50 days)
0.6
0.4
0.2
18
1.9
More
coefficient of variation (CV)
1.7
1.5
1.3
1.1
0.9
0.7
0.5
0.3
0
0.1
cumulative freq.
(src-dst IP pairs)
1
Prefix history predictor
• Quite consistent, but more variation compared to IP pairs
▫ outliers mostly caused the variation.
▫ good predictor for delay after removing outliers.
cumulative freq.
(src-dst prefix pairs)
1
0.8
Within 5 min
Within 30 min
Within 6 hr
Within 1 day
No Constraints (50 days)
0.6
0.4
0.2
0
coefficient of variation (CV)
19
Geography predictor
• Distance has strong correlation with minimum delay
▫ good predictor for removing hosts with high latency
1200
Delay (ms)
1000
800
600
400
200
0
0 2000 4000 6000 8000 10000 12000
Distance (miles)
20
Conclusions
• Large-scale end host latency and capacity characterization
• Large-scale P2P game network characterization
▫ 126 million probes among 5.6 million unique IPs
• NPQ prediction for delay
▫ IP history : great !
▫ prefix history: good after removing outliers
▫ geography : great for removing distant hosts
• NPQ prediction for capacity
▫ IP history: decent!
▫ prefix history: not feasible
▫ geography: not feasible
21