Maximizing total upload in latency-sensitive P2P applications

ABSTRACT

Motivated by an application in distributed gaming, we define and study the latency-constrained total upload maximization problem. In this problem, a peer-to-peer overlay network is modeled as a complete graph and each node v_i has an upload bandwidth capacity c_i and a set of receivers R(i). Each sender-receiver pair (v_i,v_j), where v_j ∈ R(i), is a request that should be satisfied, i.e., v_i should send a data packet to each v_j ∈ R(i). The goal is to find a set of at most n multicast-trees T_i of depth at most 2, such that each node can be part of multiple trees, all capacity constraints are met, and the number of satisfied requests is maximized. In this paper, we prove that the problem is NP-complete, and we present an algorithm with approximation ratio 1-2/√^cmin, where ^cmin is the minimum upload capacity. Finally, we also study the impact of network coding on the quality and approximability of the solution.

REFERENCES

• 1: http://planetside.station.sony.com.
• 2: R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network Information Flow. IEEE Transactions on Information Theory, 2000.
• 3: G. Baier. Flows with Path Restrictions. PhD Thesis, TU Berlin, 2003.
• 4: G. Baier, T. Erlebach, A. Hall, E. Köhler, H. Schilling, and M. Skutella. Length-Bounded Cuts and Flows. In Proc. 33rd International Colloquium on Automata, Languages and Programming (ICALP), pages 679--690, 2006.
• 5: Suman Banerjee , Bobby Bhattacharjee , Christopher Kommareddy, Scalable application layer multicast, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: S. Banerjee, C. Kommareddy, K. Kar, B. Bhattacharjee, and S. Khuller. Construction of an Efficient Overlay Multicast Infrastructure for Real-time Applications. In Proc. 23th IEEE Infocom, 2003.
• 7: 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]
• 8: Y. W. Bernier. Latency Compensating Methods in Client/Server In-Game Protocol Design and Optimization. In Game Developers Conference, 2001.
• 9: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 10: A. R. Bharambe, V. N. Padmanabhan, and S. Seshan. Supporting Spectators in Online Multiplayer Games. In Proc. of HotNets, 2004.
• 11: MS. Borella. Source Models of Network Game Traffic. Computer Communications, 23(4), 2000.
• 12: E. Brosh and Y. Shavitt. Approximation and Heuristic Algorithms for Minimum Delay Application-Layer Multicast Trees. In Proc. 24th IEEE Infocom, 2004.
• 13: Y.-H. Chu, S. G. Rao, S. Seshan, and H. Zhang. A Case for End System Multicast. IEEE Journal on Selected Areas in Communications, 20(8), 2002.
• 14: C. Diot, B. N. Levine, B. Lyles, H. Kassem, and D. Balensiefen. Deployment Issues for the IP Multicast Service and Architecture. IEEE Networks, 14(1), 2000.
• 15: Bryan Ford , Pyda Srisuresh , Dan Kegel, Peer-to-peer communication across network address translators, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.13-13, April 10-15, 2005, Anaheim, CA
• 16: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 17: Chris GauthierDickey , Daniel Zappala , Virginia Lo , James Marr, Low latency and cheat-proof event ordering for peer-to-peer games, 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.1005877]
• 18: 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]
• 19: David A. Helder , Sugih Jamin, End-Host Multicast Communication Using Switch-Trees Protocols, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.419, May 21-24, 2002
• 20: John Jannotti , David K. Gifford , Kirk L. Johnson , M. Frans Kaashoek , James W. O'Toole, Jr., Overcast: reliable multicasting with on overlay network, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.14-14, October 22-25, 2000, San Diego, California
• 21: M. Karpinski, I. I. Mandoiu, A. Olshevsky, and A. Zelikovsky. Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. Algorithmica, 42(2), 2005.
• 22: B. Knutsson, H. Lu, W. Xu, and B. Hopkins. Peet-to-Peer Support for Massively Multiplayer Games. In Proc. 24th IEEE Infocom, 2004.
• 23: Guy Kortsarz , David Peleg, Approximating the weight of shallow Steiner trees, Discrete Applied Mathematics, v.93 n.2-3, p.265-285, July 20, 1999 [doi>10.1016/S0166-218X(99)00111-0]
• 24: J. Pang, F. Uyeda, and J. R. Lorch. Scaling Peer-to-Peer Games in Low-Bandwidth Environments. In Proc. 6th Intl. Workshop on Peer-to-Peer Systems (IPTPS), 2007.
• 25: Peter Quax , Patrick Monsieurs , Wim Lamotte , Danny De Vleeschauwer , Natalie Degrande, Objective and subjective evaluation of the influence of small amounts of delay and jitter on a recent first person shooter game, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016557]
• 26: Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
• 27: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 28: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 29: Jürgen Vogel , Jörg Widmer , Dirk Farin , Martin Mauve , Wolfgang Effelsberg, Priority-based distribution trees for application-level multicast, Proceedings of the 2nd workshop on Network and system support for games, p.148-157, May 22-23, 2003, Redwood City, California [doi>10.1145/963900.963914]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Theory

Keywords:
multicast, peer-to-peer gaming, upload maximization