research-article

Pangolin: speeding up concurrent messaging for cloud-based social gaming

Authors:

Philip A. Chou,

Sanjeev Mehrotra,

Jay ThalerAuthors Info & Claims

CoNEXT '11: Proceedings of the Seventh COnference on emerging Networking EXperiments and Technologies

Article No.: 23, Pages 1 - 12

https://doi.org/10.1145/2079296.2079319

Published: 06 December 2011 Publication History

Abstract

The convergence of games and online social platforms is an exploding phenomena. The continued success of social games hinges critically on the ability to deliver smooth and highly-interactive experiences to end-users. However, it is extremely challenging to satisfy the stringent performance requirements of online social games.

Motivated by an Xbox Live online social gaming application, we address the problem of concurrent messaging, where the maximum latency of game messages has to be tightly bounded. Learning from a large-scale measurement experiment, we conclude that the generic transport protocol TCP, currently being used in the game, cannot ensure concurrent messaging. We develop a new UDP-based transport protocol, named Pangolin. The core of Pangolin is an adaptive decision making engine derived from the Markov Decision Process theory. The engine optimally controls the transmission of redundant Forward Error Correction packets to combat data loss. Trace-driven emulation demonstrates that Pangolin reduces the 99.9-percentile latency from more than 4 seconds to about 1 second with negligible overhead.

Pangolin pre-computes all optimal actions and requires only simple table look-up during online operation. Pangolin has been incorporated into the latest Xbox SDK - released in November, 2010 - and is now powering concurrent messaging for hundreds of thousands of Xbox clients.

References

[1]

1 vs. 100 (Xbox 360). In Wikipedia.

[2]

Zynga -- the world's most intriguing startups. In Businessweek (November 2009).

[3]

The 25 largest facebook games as 2010 begins. In Inside Facebook (January 2010).

[4]

Allman, M., Eddy, W. M., and Ostermann, S. Estimating loss rates with tcp. In ACM SIGMETRICS Performance Evaluation Review (2003).

Digital Library

[5]

Allman, M., and Paxson, V. On estimating end-to-end network path properties. In SIGCOMM '99: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication (New York, NY, USA, 1999), ACM, pp. 263--274.

Digital Library

[6]

Balakrishnan, M., Birman, K., Phanishayee, A., and Pleisch, S. Ricochet: Lateral error correction for time-critical multicast. In Fourth Usenix Symposium on Networked Systems Design and Implementation (2007).

Digital Library

[7]

Balakrishnan, M., Marian, T., Birman, K., Weatherspoon, H., and Vollset, E. Maelstrom: Transparent error correction for lambda networks. In Fifth Usenix Symposium on Networked Systems Design and Implementation.

Digital Library

[8]

Beutler, F. J., and Ross, K. W. Optimal policies for controlled markov chains with a constraint. In Journal of Mathematical Analysis and Application (1985).

[9]

Bolot, J.-C., Fosse-Parisis, S., and Towsley, D. Adaptive fec-based error control for internet telephony. In IEEE INFOCOM (1999).

[10]

Bolot, J. C., and Vega-Garcia, A. The case for fec-based error control for packet audio in the internet. In ACM Multimedia Systems (1997).

[11]

Byers, J., Luby, M., Mitzenmacher, M., and Rege, A. A digital fountain approach to reliable distribution of bulk data. In Proceedings of ACM SIGCOMM (1998).

Digital Library

[12]

Byers, J. W., Considine, J., Mitzenmacher, M., and Rost, S. Informed content delivery across adaptive overlay networks. In Proceedings of ACM SIGCOMM (2002).

Digital Library

[13]

Chang, H., Jamin, S., and Wang, W. Live streaming performance of the zattoo network. In ACM Internet Measurement Conference (2009).

Digital Library

[14]

Chou, P. A., and Miao, Z. Rate-distortion optimized streaming of packetized media. In IEEE Transactions on Multimedia (Apr. 2006).

Digital Library

[15]

Chou, P. A., Wu, Y., and Jain, K. Practical network coding. In Allerton Conference on Communication, Control, and Computing (2003).

[16]

Dukkipati, N., Refice, T., Cheng, Y., Chu, J., Sutin, N., Agarwal, A., Herbert, T., and Jain, A. An argument for increasing tcp's initial congestion window. In ACM Sigcomm CCR (July 2010).

Digital Library

[17]

Gkantsidis, C., and Rodriguez, P. Network coding for large scale content distribution. In IEEE INFOCOM (2005).

[18]

Haeberlen, A., Dischinger, M., Gummadi, K. P., and Saroiu, S. Monarch: a tool to emulate transport protocol flowsover the internet at large. In IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement (New York, NY, USA, 2006), ACM, pp. 105--118.

Digital Library

[19]

Jiang, H., and Dovrolis, C. Passive estimation of tcp round-trip times. In ACM CCR (2002).

Digital Library

[20]

Liew, J. Why the economics of social gaming are so attractive to investors, December 2009.

[21]

Maymounkov, P., and Mazires, D. Rateless codes and big downloads. In The Second International Workshop on Peer-to-peer Systems (2003).

[22]

Mondal, A., and Kuzmanovic, A. Removing exponential backoff from tcp. In ACM SIGCOMM Computer Communication Review (2008).

Digital Library

[23]

Nonnenmacher, J., Biersack, E., and Towsley, D. Parity-based loss recovery for reliable multicast transmission, 1998.

[24]

Rhee, I., and Joshi, S. R. Fec-based loss recovery for interactive video transmission experimental study. In Proceedings of the IEEE International Conference on Multimedia Computing and Systems (1998).

Digital Library

[25]

Rothschild, J. High performance at massive scale: Lessons learned at facebook. In CNS Lecture Series (2009).

[26]

Rubenstein, D., Kasera, S., Towsley, D., and Kurose, J. Improving reliable multicast using active parity encoding services (apes). In Computer Networks (2004).

Digital Library

[27]

Shalunov, S. Low extra delay background transport (ledbat). In IETF Draft (2009).

[28]

Vasudevan, V., Phanishayee, A., Shah, H., Krevat, E., Andersen, D., Ganger, G., Gibson, G., and Mueller, B. Safe and effective fine-grained tcp retransmissions for datacenter communication. In ACM SIGCOMM (2009).

Digital Library

[29]

Zhang, C., Huang, C., Chou, P. A., Li, J., Mehrotra, S., Ross, K. W., Chen, H., Livni, F., and Thaler, J. Pangolin: Speeding up Concurrent Messaging for Cloud-Based Social Gaming. In Technical Report, Microsoft Research (June 2011). http://research.microsoft.com/~chengh/techreports/pangolintech.pdf.

Digital Library

Cited By

Garrido PSanchez IFerlin SAguero RAlay O(2019)rQUIC: Integrating FEC with QUIC for Robust Wireless Communications2019 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOBECOM38437.2019.9013401(1-7)Online publication date: Dec-2019
https://doi.org/10.1109/GLOBECOM38437.2019.9013401
Goel UWittie MClaffy KLe A(2016)Survey of End-to-End Mobile Network Measurement Testbeds, Tools, and ServicesIEEE Communications Surveys & Tutorials10.1109/COMST.2015.248597918:1(105-123)Online publication date: Sep-2017
https://doi.org/10.1109/COMST.2015.2485979
Micka SGoel UYe HWittie MMumey B(2015)pcp: Internet Latency Estimation Using CDN Replicas2015 24th International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2015.7288449(1-8)Online publication date: Aug-2015
https://doi.org/10.1109/ICCCN.2015.7288449
Show More Cited By

Recommendations

Pangolin: an SFL-based toolset for feature localization
ASE '19: Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering

Pinpointing the location where a given unit of functionality---or feature---was implemented is a demanding and time-consuming task, yet prevalent in most software maintenance or evolution efforts. To that extent, we present Pangolin, an Eclipse plugin ...
Using Twitter Data to Evaluate Pangolin Conservation Awareness
ACI '23: Proceedings of the Tenth International Conference on Animal-Computer Interaction

Pangolins are the most heavily trafficked species in the world. Despite this, they remain relatively unknown compared to other species also at risk from over-exploitation. Public awareness of the species is essential for developing successful ...
TCP CERL: congestion control enhancement over wireless networks

In this paper, we propose and verify a modified version of TCP Reno that we call TCP Congestion Control Enhancement for Random Loss (CERL). We compare the performance of TCP CERL, using simulations conducted in ns-2, to the following other TCP variants: ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '11: Proceedings of the Seventh COnference on emerging Networking EXperiments and Technologies

December 2011

364 pages

ISBN:9781450310413

DOI:10.1145/2079296

General Chairs:
Kenjiro Cho
IIJ/Keio University, Japan
,
Mark Crovella
Boston University

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 December 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

Co-NEXT '11

Sponsor:

SIGCOMM

Co-NEXT '11: Conference on emerging Networking Experiments and Technologies

December 6 - 9, 2011

Tokyo, Japan

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
159
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Garrido PSanchez IFerlin SAguero RAlay O(2019)rQUIC: Integrating FEC with QUIC for Robust Wireless Communications2019 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOBECOM38437.2019.9013401(1-7)Online publication date: Dec-2019
https://doi.org/10.1109/GLOBECOM38437.2019.9013401
Goel UWittie MClaffy KLe A(2016)Survey of End-to-End Mobile Network Measurement Testbeds, Tools, and ServicesIEEE Communications Surveys & Tutorials10.1109/COMST.2015.248597918:1(105-123)Online publication date: Sep-2017
https://doi.org/10.1109/COMST.2015.2485979
Micka SGoel UYe HWittie MMumey B(2015)pcp: Internet Latency Estimation Using CDN Replicas2015 24th International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2015.7288449(1-8)Online publication date: Aug-2015
https://doi.org/10.1109/ICCCN.2015.7288449
Howard ECooper CWittie MSwinford SYang QIshibashi YCheok A(2014)Cascading impact of lag on quality of experience in cooperative multiplayer gamesProceedings of the 13th Annual Workshop on Network and Systems Support for Games10.5555/2755535.2755551(1-6)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.5555/2755535.2755551
Howard ECooper CWittie MSwinford SYang Q(2014)Cascading impact of lag on Quality of Experience in cooperative multiplayer games2014 13th Annual Workshop on Network and Systems Support for Games10.1109/NetGames.2014.7008965(1-6)Online publication date: Dec-2014
https://doi.org/10.1109/NetGames.2014.7008965

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents