Donnybrook: enabling large-scale, high-speed, peer-to-peer games

ABSTRACT

Without well-provisioned dedicated servers, modern fast-paced action games limit the number of players who can interact simultaneously to 16-32. This is because interacting players must frequently exchange state updates, and high player counts would exceed the bandwidth available to participating machines. In this paper, we describe Donnybrook, a system that enables epic-scale battles without dedicated server resources, even in a fast-paced game with tight latency bounds. It achieves this scalability through two novel components. First, it reduces bandwidth demand by estimating what players are paying attention to, thereby enabling it to reduce the frequency of sending less important state updates. Second, it overcomes resource and interest heterogeneity by disseminating updates via a multicast system designed for the special requirements of games: that they have multiple sources, are latency-sensitive, and have frequent group membership changes. We present user study results using a prototype implementation based on Quake III that show our approach provides a desirable user experience. We also present simulation results that demonstrate Donnybrook's efficacy in enabling battles of up to 900 players.

REFERENCES

• 1: Aditya Akella , Srinivasan Seshan , Anees Shaikh, An empirical evaluation of wide-area internet bottlenecks, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948219]
• 2: Suman Banerjee , Seungjoon Lee , Ryan Braud , Bobby Bhattacharjee , Aravind Srinivasan, Scalable resilient media streaming, Proceedings of the 14th international workshop on Network and operating systems support for digital audio and video, June 16-18, 2004, Cork, Ireland [doi>10.1145/1005847.1005851]
• 3: Tom Beigbeder , Rory Coughlan , Corey Lusher , John Plunkett , Emmanuel Agu , Mark Claypool, The effects of loss and latency on user performance in unreal tournament 2003®, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016556]
• 4: Ashwin Bharambe , Jeffrey Pang , Srinivasan Seshan, Colyseus: a distributed architecture for online multiplayer games, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.12-12, May 08-10, 2006, San Jose, CA
• 5: Blizzard Entertainment. Battle.net info. http://www.battle.net/info/faq.shtml, 2007.
• 6: Blizzard Entertainment. WoW PvP battlegrounds. http://www.worldofwarcraft.com/pvp/battlegrounds, 2008.
• 7: Broadband Reports. Broadband reports speed test statistics. http://www.dslreports.com/archive, Sept. 2007.
• 8: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 9: Castro, M., Druschel, P., Kermarrec, A.-M., and Rowstron, A. Scribe: A large-scale and decentralized application-level multicast infrastructure. IEEE JSAC 20, 8 (Oct. 2002).
• 10: Chu, Y.-H., Rao, S. G., Seshan, S., and Zhang, H. A case for end system multicast. IEEE JSAC 20, 8 (2002).
• 11: Cowan, N. The magical number 4 in short-term memory: A reconsideration of mental storage capacity. Behavioral and Brain Sciences 24, 1 (2001).
• 12: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 13: DIS Steering Committee. The DIS vision: A map to the future of distributed simulation, ver. 1. IST-SP-94-01, 1994.
• 14: John R. Douceur , Jay R. Lorch , Thomas Moscibroda, Maximizing total upload in latency-sensitive P2P applications, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248422]
• 15: GameZone. Blizzard Entertainment Announces World of Warcraft Release Plans for Europe. http://pc.gamezone.com/news/11_24_04_09_39AM.htm, 2004.
• 16: L. Gautier , C. Diot, Design and Evaluation of MiMaze, a Multi-Player Game on the Internet, Proceedings of the IEEE International Conference on Multimedia Computing and Systems, p.233, June 28-July 01, 1998 [doi>10.1109/MMCS.1998.693647]
• 17: Gilbert, E. N. Capacity of a burst-noise channel. The Bell System Technical Journal 39 (1960).
• 18: John A. Hamilton , David A. Nash , Udo W. Pooch, Distributed Simulation, CRC Press, Inc., Boca Raton, FL, 1996
• 19: Hu, S.-Y., Chen J.-F., and Chen, T.-H. VON: a scalable peer-to-peer network for virtual environments. IEEE Network 20, 4 (July/Aug. 2006).
• 20: IEEE. IEEE standard for distributed interactive simulation-application protocols, Sept. 1995. IEEE Standard 1278.1-1995.
• 21: IEEE. IEEE standard for modeling and simulation high level architecture (HLA), Sept. 2000. IEEE Standard 1516-2000.
• 22: Knutsson, B. et al. Peer-to-peer support for massively multiplayer games. In INFOCOM (July 2004).
• 23: Lee, Y., Agarwal, S., Butcher, C., and Padhye, J. Measurement and estimation of network QoS among peer Xbox 360 game players. In PAM (Apr. 2008).
• 24: McCoy, A., McLoone, S., Ward, T., and Delaney, D. Dynamic hybrid strategy models for networked multiplayer games. In ECMS (June 2005), pp. 727--732.
• 25: Aaron Mccoy , Tomas Ward , Seamus Mcloone , Declan Delaney, Multistep-ahead neural-network predictors for network traffic reduction in distributed interactive applications, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.17 n.4, p.16-es, September 2007 [doi>10.1145/1276927.1276929]
• 26: Microsoft Corporation. Xbox LIVE website. http://www.xbox.com/en-US/live/, 2007.
• 27: Mukherjee, A. On the dynamics and significance of low frequency components of Internet load. Internetworking: Research and Experience 5 (1994).
• 28: Ohio University. Ohio University announces changes in file-sharing policies. http://www.ohio.edu/students/filesharing.cfm, 2007.
• 29: O'Neill, V. Adding creamy nougat and a crisp candy coating to the network: XRNM and QNet. XNA GameFest (Aug. 2007).
• 30: Venkata N. Padmanabhan , Kunwadee Sripanidkulchai, The Case for Cooperative Networking, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.178-190, March 07-08, 2002
• 31: Pang, J., Uyeda, F., and Lorch, J. Scaling peer-to-peer games in low-bandwidth environments. In IPTPS (Feb. 2007).
• 32: Lothar Pantel , Lars C. Wolf, On the suitability of dead reckoning schemes for games, Proceedings of the 1st workshop on Network and system support for games, p.79-84, April 16-17, 2002, Braunschweig, Germany [doi>10.1145/566500.566512]
• 33: Paul, R. More universities banning Skype. http://arstechnica.com/news.ars/post/20060924-7814.html, 2006.
• 34: Piatek, M., Isdal, T., Anderson, T., Krishnamurthy, A., and Venkataramani, A. Do incentives build robustness in BitTorrent? In NSDI (Apr. 2007), pp. 1--14.
• 35: Daniel Pittman , Chris GauthierDickey, A measurement study of virtual populations in massively multiplayer online games, Proceedings of the 6th ACM SIGCOMM workshop on Network and system support for games, p.25-30, September 19-20, 2007, Melbourne, Australia [doi>10.1145/1326257.1326262]
• 36: Rao, S., Bharambe, A., Padmanabhan, V., Seshan, S., and Zhang, H. The impact of heterogeneous bandwidth constraints on DHT-based multicast protocols. In IPTPS (Feb. 2005).
• 37: Robson, J. G., and Graham, N. Probability summation and regional variation in contrast sensitivity across the visual field. Vision Research 21, 3 (1981).
• 38: Rosedale, P., and Ondrejka, C. Enabling player-created online worlds with grid computing and streaming. Gamasutra (Sept. 2003).
• 39: J. Rosenberg , J. Weinberger , C. Huitema , R. Mahy, STUN - Simple Traversal of User Datagram Protocol (UDP) Through Network Address Translators (NATs), RFC Editor, 2003
• 40: Sony Online Entertainment. PlanetSide FAQ. http://planetside.station.sony.com/faq.vm, 2008.
• 41: YVG Staff. Video game sales break records. http://us.i1.yimg.com/videogames.yahoo.com/feature/video-game-sales-break-records/1181404, Jan. 2008.
• 42: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Experimentation, Human Factors

Keywords:
computer games, doppelgängers, interest sets