ABSTRACT
The latency between machines on the Internet can dramatically affect users' experience for many distributed applications. Particularly, in multiplayer online games, players seek to cluster themselves so that those in the same session have low latency to each other. A system that predicts latencies between machine pairs allows such matchmaking to consider many more machine pairs than can be probed in a scalable fashion while users are waiting. Using a far-reaching trace of latencies between players on over 3.5 million game consoles, we designed Htrae, a latency prediction system for game matchmaking scenarios. One novel feature of Htrae is its synthesis of geolocation with a network coordinate system. It uses geolocation to select reasonable initial network coordinates for new machines joining the system, allowing it to converge more quickly than standard network coordinate systems and produce substantially lower prediction error than state-of-the-art latency prediction systems. For instance, it produces 90th percentile errors less than half those of iPlane and Pyxida. Our design is general enough to make it a good fit for other latency-sensitive peer-to-peer applications besides game matchmaking.
- D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris. Resilient overlay networks. In Proc. Symposium on Operating Systems Principles (SOSP), Oct. 2001. Google ScholarDigital Library
- T. Beigbeder, R. Coughlan, C. Lusher, J. Plunkett, E. Agu, and M. Claypool. The effects of loss and latency on user performance in unreal tournament 2003®. In In NetGames, Aug./Sep. 2004. Google ScholarDigital Library
- Bungie. Halo 3 Forum. http://www.bungie.net/Forums/posts.aspx?postID=8455638.Google Scholar
- D. R. Choffnes and F. Bustamante. Taming the Torrent: A practical approach to reducing cross-ISP traffic in peer-to-peer systems. In Proc. SIGCOMM Conference, pages 363--374, Aug. 2008. Google ScholarDigital Library
- M. Costa, M. Castro, A. Rowstron, and P. Key. PIC: Practical Internet coordinates for distance estimation. In Proc. International Conference on Distributed Computing Systems (ICDCS), pages 178--187, Mar. 2004. Google ScholarDigital Library
- F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: A decentralized network coordinate system. In Proc. SIGCOMM Conference, pages 426--437, Aug./Sep. 2004. Google ScholarDigital Library
- F. Dabek, J. Li, E. Sit, J. Robertson, M. F. Kaashoek, and R. Morris. Designing a DHT for low latency and high throughput. In Proc. Symposium on Networked Systems Design and Implementation (NSDI), pages 85--98, Mar. 2004. Google ScholarDigital Library
- P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149--160, 1984.Google Scholar
- P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. IDMaps: A global Internet host distance estimation service. IEEE/ACM Transactions on Networking, Oct. 2001. Google ScholarDigital Library
- M. J. Freedman, K. Lakshminarayanan, and D. Mazières. OASIS: Anycast for any service. In Proc. Symposium on Networked Systems Design and Implementation (NSDI), pages 129--142, May 2006. Google ScholarDigital Library
- S. Guha and P. Francis. Characterization and measurement of TCP traversal through NATs and firewalls. In Proc. Internet Measurement Conference (IMC), Oct. 2005. Google ScholarDigital Library
- I. Herman, G. Melançon, and M. S. Marshall. Graph visualization and navigation in information visualization: a survey. IEEE Transactions on Visualization and Computer Graphics, 6:24--43, 2000. Google ScholarDigital Library
- J. Ledlie, P. Gardner, and M. Seltzer. Network coordinates in the wild. In Proc. Symposium on Networked Systems Design and Implementation (NSDI), pages 299--311, Apr. 2007. Google ScholarDigital Library
- Y. Lee, S. Agarwal, C. Butcher, and J. Padhye. Measurement and estimation of network QoS among peer Xbox 360 game players. In Proc. Passive and Active Measurement Conference (PAM), pages 41--50, Apr. 2008. Google ScholarDigital Library
- H. Lim, J. C. Hou, and C.-H. Choi. Constructing Internet coordinate system based on delay measurement. IEEE Transactions on Networking, 13(3):513--525, June 2005. Google ScholarDigital Library
- C. Lumezanu, D. Levin, and N. Spring. PeerWise discovery and negotiation of faster paths. In Proc. Workshop on Hot Topics in Networks (HotNets), Nov. 2007.Google Scholar
- C. Lumezanu and N. Spring. Measurement manipulation and space selection in network coordinates. In Proc. International Conference on Distributed Computing Systems (ICDCS), pages 361--368, June 2008. Google ScholarDigital Library
- H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iPlane: An information plane for distributed services. In Proc. Symposium on Operating Systems Design and Implementation (OSDI), pages 367--380, Nov. 2006. Google ScholarDigital Library
- H. V. Madhyastha, E. Katz-Bassett, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iPlane Nano: Path prediction for peer-to-peer applications. In Proc. Networked Systems Design and Implementation (NSDI), Apr. 2009. Google ScholarDigital Library
- MaxMind. Geolocation and online fraud prevention from MaxMind. http://www.maxmind.com/.Google Scholar
- D. Moore, R. Periakaruppan, and J. Donohoe. Where in the world is netgeo.caida.org? In Proc. INET Conference, July 2000.Google Scholar
- D. R. Morrison. PATRICIA--practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM (JACM), 15(4):514--534, Oct. 1968. Google ScholarDigital Library
- T. S. E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proc. IEEE Computer and Communications Conference (INFOCOM), 2002.Google ScholarCross Ref
- V. N. Padmanabhan and L. Subramanian. An investigation of geographic mapping techniques for Internet hosts. In Proc. SIGCOMM Conference, pages 173--185, Aug. 2001. Google ScholarDigital Library
- M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti. Lighthouses for scalable distributed location. In Proc. International Workshop on Peer-to-Peer Systems (IPTPS), Feb. 2003.Google ScholarCross Ref
- J. Rosenberg, J. Weinberger, C. Huitema, and R. Mahy. STUN -- simple traversal of user datagram protocol (UDP) through network address translators (NATs). Network Working Group RFC 3489, Mar. 2003. Google ScholarDigital Library
- Route Views Project. University of Oregon. http://www.routeviews.org/.Google Scholar
- Y. Shavitt and T. Tankel. Big-Bang Simulation for embedding network distances in Euclidean space. IEEE/ACM Transactions on Networking, 12(6):993--1006, Dec. 2004. Google ScholarDigital Library
- Y. Staff. Video game sales break records. http:// us.i1.yimg.com/videogames.yahoo.com/feature/video-game-sales-break-records/1181404, Jan. 2008.Google Scholar
- L. Tang and M. Crovella. Virtual landmarks for the Internet. In Proc. Internet Measurement Conference (IMC), pages 143--152, Oct. 2003. Google ScholarDigital Library
- W. Theilmann and K. Rothermel. Dynamic distance maps of the Internet. In Proc. Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Mar. 2000.Google ScholarCross Ref
- W. S. Togerson. Multidimensional scaling of similarity. Psychometrika, 30(4):379--393, Dec. 1965.Google ScholarCross Ref
- G. Wang, B. Zhang, and T. S. E. Ng. Towards network triangle inequality violation aware distributed systems. In Proc. Internet Measurement Conference (IMC), pages 145--157, Oct. 2007. Google ScholarDigital Library
- B. Wong, A. Slivkins, and E. G. Sirer. Meridian: A lightweight network location service without virtual coordinates. In Proc. SIGCOMM Conference, pages 85--96, Aug. 2005. Google ScholarDigital Library
- G. Yona, N. Linial, and M. Linial. ProtoMap: automatic classification of protein sequences and hierarchy of protein families. Nucleic Acids Research, 28(1):49--55, 2000.Google ScholarCross Ref
- H. Zheng, E. K. Lua, M. Pias, and T. G. Griffin. Internet routing policies and round-trip times. In Proc. Passive and Active Measurement Conference (PAM), Mar./Apr. 2005. Google ScholarDigital Library
- G. Zigelman, R. Kimmel, and N. Kiryati. Texture mapping using surface flattening via multi-dimensional scaling. IEEE Transactions on Visualization and Computer Graphics, 8(2):198--207, Apr. 2002. Google ScholarDigital Library
Index Terms
- Matchmaking for online games and other latency-sensitive P2P systems
Recommendations
Matchmaking for online games and other latency-sensitive P2P systems
SIGCOMM '09The latency between machines on the Internet can dramatically affect users' experience for many distributed applications. Particularly, in multiplayer online games, players seek to cluster themselves so that those in the same session have low latency to ...
Switchboard: a matchmaking system for multiplayer mobile games
MobiSys '11: Proceedings of the 9th international conference on Mobile systems, applications, and servicesSupporting interactive, multiplayer games on mobile phones over cellular networks is a difficult problem. It is particularly relevant now with the explosion of mostly single-player or turn-based games on mobile phones. The challenges stem from the ...
Matchmaking in multi-player on-line games: studying user traces to improve the user experience
NOSSDAV '14: Proceedings of Network and Operating System Support on Digital Audio and Video WorkshopDesigning and implementing a quality matchmaking service for Multiplayer Online Games requires an extensive knowledge of the habits, behaviors and expectations of the players. Gathering and analyzing traces of real games offers insight on these matters, ...
Comments