User-perceived quality-of-experience (QoE) is critical in internet video delivery systems. Extensive prior work has studied the design of client-side bitrate adaptation algorithms to maximize single-player QoE. However, multiplayer QoE fairness becomes critical as the growth of video traffic makes it more likely that multiple players share a bottleneck in the network. Despite several recent proposals, there is still a series of open questions. In this paper, we bring the problem space to light from a control theory perspective by formalizing the multiplayer QoE fairness problem and addressing two key questions in the broader problem space. First, we derive the sufficient conditions of convergence to steady state QoE fairness under TCP-based bandwidth sharing scheme. Based on the insight from this analysis that in-network active bandwidth allocation is needed, we propose a non-linear MPC-based, router-assisted bandwidth allocation algorithm that regards each player as closed-loop systems. We use trace-driven simulation to show the improvement over existing approaches. We identify several research directions enabled by the control theoretic modeling and envision that control theory can play an important role on guiding real system design in adaptive video streaming.
Alternatively, server-side solutions regard the server as a single point of control and allocate bandwidth to players @cite_22 . However, the actual bandwidth bottleneck can occur in the network instead of server and the computation cost is high when the number of players is too large.
@cite_22
2150694596 2129486506 2122478169 2144363069
Supporting thousands, possibly hundreds of thousands, of players is a requirement that must be satisfied when delivering server based online gaming as a commercial concern. Such a requirement may be satisfied by utilising the cumulative processing resources afforded by a cluster of servers. Clustering of servers allow great flexibility, as the game provider may add servers to satisfy an increase in processing demands, more players, or remove servers for routine maintenance or upgrading. If care is not taken, the way processing demands are distributed across a cluster of servers may hinder such flexibility and also hinder player interaction within a game. In this paper we present an approach to load balancing that is simple and effective, yet maintains the flexibility of a cluster while promoting player interaction. In a Content Distribution Network (CDN), there are m servers storing the data; each of them has a specific bandwidth. All the requests from a particular client should be assigned to one server because of the routing protocol used. The goal is to minimize the total cost of these assignments—cost of each is proportional to the distance between the client and the server as well as the request size—while the load on each server is kept below its bandwidth limit. When each server also has a setup cost, this is an unsplittable hard-capacitated facility location problem. As much attention as facility location problems have received, there has been no nontrivial approximation algorithm when we have hard capacities (i.e., there can only be one copy of each facility whose capacity cannot be violated) and demands are unsplittable (i.e., all the demand from a client has to be assigned to a single facility). We observe it is NP-hard to approximate the cost to within any bounded factor in this case. Thus, for an arbitrary constant e>0, we relax the capacities to a 1+e factor. For the case where capacities are almost uniform, we give a bicriteria O(log n, 1+e)-approximation algorithm for general metrics and a (1+e, 1+e)-approximation algorithm for tree metrics. A bicriteria (α,β)-approximation algorithm produces a solution of cost at most α times the optimum, while violating the capacities by no more than a β factor. We can get the same guarantees for nonuniform capacities if we allow quasipolynomial running time. In our algorithm, some clients guess the facility they are assigned to, and facilities decide the size of the clients they serve. A straightforward approach results in exponential running time. When costs do not satisfy metricity, we show that a 1.5 violation of capacities is necessary to obtain any approximation. It is worth noting that our results generalize bin packing (zero connection costs and facility costs equal to one), knapsack (single facility with all costs being zero), minimum makespan scheduling for related machines (all connection costs being zero), and some facility location problems. Multiplayer games played over the Internet have become very popular in the lastfew years. An interesting subcategory are the so-called massively multiplayeronline games (MMOGs) that allow thousands of player characters to share asingle game world. Such a world is usually run on a high-performance and high-availability server cluster. However, even with games that have been extensivelybeta-tested, downtimes of several hours because of hard- or software failures arenot uncommon. Downtimes, especially in the ﬁrst few weeks after the release,can negatively aﬀect the image of the game and the company that created it.Traditionally, a cluster of servers contains one virtual world of a MMOG.Such infrastructure is inﬂexible and error-prone. One would rather like to havea system that allows disconnecting a server at runtime while others take overits tasks. Server-based MMOGs can have performance problems if players areconcentrated in certain parts of the game world or some worlds are overpopu-lated. Thus, there is also a need for load balancing mechanisms. Peer-to-Peer(P2P) systems quite naturally support the use of load balancing.In this paper we use a structured P2P technology for the organization of theinfrastructure and thus for the reduction of downtimes in MMOGs. We splitthe game world in disjunctive rectangular zones and distribute them on diﬀerentnodes of the P2P network.Online games are an interesting challenge and chance for the future devel-opment of the P2P paradigm. A wide variety of aspects of only theoreticallysolved and especially yet completely unsolved problems are covered by this ap-plication. Security and trust problems appear as well as the need to preventcheating. The application is not as tolerant to faults as instant messaging or ﬁlesharing. Consistent data storage is a problem, decisions and transactions haveto be performed in a decentralized way. Moreover, the P2P network is not usedas pure lookup service, but more as a communication and application-speciﬁcsocial structure.The rest of this paper is organized as follows: First we discuss related work inSection 2 and give a brief introduction to P2P and MMOGs and their challengesin Section 3. Section 4 shows our approach to use structured P2P Systems forMMOGs and section 5 the evaluation with player traces from a real MMOG.Finally, Section 6 provides conclusions. Content distribution networks (CDNs) need to make decisions, such as server selection and routing, to improve performance for their clients. The performance may be limited by various factors such as packet loss in the network, a small receive buffer at the client, or constrained server CPU and disk resources. Conventional measurement techniques are not effective for distinguishing these performance problems: application-layer logs are too coarse-grained, while network-level traces are too expensive to collect all the time. We argue that passively monitoring the transport-level statistics in the server's network stack is a better approach. This paper presents a tool for monitoring and analyzing TCP statistics, and an analysis of a CoralCDN node in PlanetLab for six weeks. Our analysis shows that more than 10 of connections are server-limited at least 40 of the time, and many connections are limited by the congestion window despite no packet loss. Still, we see that clients in 377 Autonomous Systems (ASes) experience persistent packet loss. By separating network congestion from other performance problems, our analysis provides a much more accurate view of the performance of the network paths than what is possible with server logs alone.