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. Akella, A., Seshan, S., and Shaikh, A. An empirical evaluation of wide-area Internet bottlenecks. In SIGCOMM (Oct. 2003), pp. 316--317.
2. Banerjee, S., Lee, S., Bhattacharjee, B., Srinivasan, A., and Braud, R. Scalable resilient media streaming. In NOSSDAV (June 2004).
3. Beigbeder, T., Coughlan, R., Lusher, C., Plunkett, J., Agu, E., and Claypool, M. The effects of loss and latency on user performance in Unreal Tournament 2003. In NetGames (Aug. 2004), pp. 144--151.
4. Bharambe, A., Pang, J., and Seshan, S. Colyseus: A distributed architecture for interactive multiplayer games. In NSDI (May 2006).
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. Castro, M., Druschel, P., Kermarrec, A.-M., Nandi, A., Rowstron, A., and Singh, A. Splitstream: High-bandwidth multicast in a cooperative environment. In SOSP (2003).
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. Dabek, F., Cox, R., Kaashoek, F., and Morris, R. Vivaldi: A decentralized network coordinate system. In SIGCOMM (Aug. 2004), pp. 15--26.
13. DIS Steering Committee. The DIS vision: A map to the future of distributed simulation, ver. 1. IST-SP-94-01, 1994.
14. Douceur, J., Lorch, J., and Moscibroda, T. Maximizing total upload in latency-sensitive P2P applications. In SPAA (June 2007), pp. 270--279.
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. Gautier, L., and Diot, C. Design and evaluation of MiMaze, a multi-player game on the Internet. In IEEE Multimedia Systems Conference (July 1998).
17. Gilbert, E. N. Capacity of a burst-noise channel. The Bell System Technical Journal 39 (1960).
18. Hamilton, J. A., Nash, D. A., and Pooch, U. W. Distributed Simulation. CRC Press, 1997.
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. McCoy, A., Ward, T., McLoone, S., and Delaney, D. Multistep-ahead neural-network predictors for network traffic reduction in distributed interactive applications. TOMACS 17, 4 (Sept. 2007).
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. Padmanabhan, V., and Sripanidkulchai, K. The case for cooperative networking. In IPTPS (Mar. 2002).
31. Pang, J., Uyeda, F., and Lorch, J. Scaling peer-to-peer games in low-bandwidth environments. In IPTPS (Feb. 2007).
32. Pantel, L., and Wolf, L. C. On the suitability of dead reckoning schemes for games. In NetGames (Apr. 2002), pp. 79--84.
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. Pittman, D., and Dickey, C. G. A measurement study of virtual populations in massively multiplayer online games. In NetGames (Sept. 2007).
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. Rosenberg, J., Weinberger, J., Huitema, C., and Mahy, R. STUN - Simple Traversal of User Datagram Protocol (UDP) Through Network Address Translators (NATs). RFC 3489 (Proposed Standard), Mar. 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. Zhang, Y., Duffield, N., Paxson, V., and Shenker, S. On the constancy of Internet path properties. In IMC (Nov. 2001).

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles