1. Introduction
In recent years, the increasing number of live-streamed and on-demand classes using ZOOM and other technologies by Corona Disaster, as well as the increasing demand for live-streamed entertainment by Youtubers and others, have led to the need for higher quality in streaming communications. In addition, the demand for high-quality streaming communication by a large number of users is increasing, and it may be extended to multi-server streaming where video chunks are requested simultaneously from multiple web servers [1], [2].
In terms of streaming communication protocols, DASH (Dynamic Adaptive Streaming over HTTP) was established as an ISO international standard in 2012 [3]. This is used by adaptively varying the bit rate according to each user's network bandwidth, which can greatly improve the quality of streaming communication. Based on the 2019 Cisco Visual Networking Index [4], it is reported that approximately 79% of global mobile data traffic will be video by 2022. Therefore, providing high-quality video streaming services is the main challenge to keep user Quality of Experience (QoE) high. Moreover, due to its application in various fields, such as emergency response training and medical surgery, QoE is considered to need to be high [5]. Various protocols have been presented, however, DASH, which is an international standard, is widely used for adaptive video streaming.
In order to improve QoE in DASH, a multi-server system has been presented by pseudo-increasing bandwidth through multiple servers. This multi-server system is designed to share streaming content efficiently in addition to having redundant server resources for each streaming content, which is excellent for fault tolerance. Assigning DASH server to users in these multi-servers environment is important to maintain QoE. However, a method of server assignment of users (user allocation method) considering the bandwidth of the overall system among multiple DASH servers has not yet been proposed. There is a risk that a client's selfish behavior may cause the load to be concentrated on a particular server, adversely affecting the overall system [6]. In other words, if each user selects the server with the highest bandwidth in priority without considering the status of other users, users will concentrate on the server with the highest bandwidth, resulting in video quality less than that which can be obtained originally, which adversely affects the QoE. Allocated bandwidth must be reserved for comfortable streaming communications [7]. Therefore, in a multi-server environment, an appropriate user allocation method according to the network traffic situation of the overall system is required.
In this paper, we propose an appropriate user allocation method that takes into account the traffic situation of other users in overall multi-server system. In order to take into account the traffic situation of the overall system, we use a coalition structure generation of cooperative game theory. Cooperative game theory analyzes the benefits that arise when users cooperate with each other and form coalitions to achieve a certain goal. Using this theory, an coalition is created for each server, the gain is analyzed using a gain function defined by the server's bandwidth and the user's bit rate, and the average quality for all users is improved by the allocation that maximizes the gain from the coalition. In addition, by using the coalition structure generation in cooperative game theory, the overall QoE is improved by considering the gain of the overall system and avoiding the concentration of users on a particular server.
Our contributions of this paper are as follows.
- Avoiding server concentration by considering the overall system traffic.
- Using coalition structure generation to take into account the traffic situation of the overall system.
- Improving QoE by avoiding server concentration.
- Applicable even when user bandwidth requirements change.
- Improving QoE compared to the conventional fixed bandwidth request method.
This paper is organized as follows. Section 2 describes cooperative game theory as a preliminary preparation, and Sect. 3 describes DASH, game theory, and user assignment methods as related work. Section 4 describes our proposed method, and Sect. 5 describes the simulation environment and results. Section 6 summarizes our paper.
2. Preliminaries
First, we briefly explain some preliminary knowledge of game theory. For more information, please refer to [8].
2.1 Cooperative Game Theory
In a multiplayer system consisting of multiple autonomous players, players are expected to solve more difficult problems efficiently by cooperating with each other. In this case, it is necessary to consider how selfish players form cooperative relationships (coalitions) and how they allocate the gains obtained through coalition. Cooperative game theory is the theoretical basis for solving these problems.
There are two major types of research in cooperative game theory. One is the problem of distributing the gain of the coalition to the users, and a method of distribution is called the solution concept. Various solution concepts have been proposed so far, such as core, Shapley value [8], [9]. The other is called the coalition structure formation problem, which is the problem of partitioning the set of players so that the sum of the gains is maximized when it is not optimal for everyone to cooperate [10]-[14]. In this study, we use this coalition structure formation problem to allocate users to multi-servers by considering overall network traffic situation.
2.2 Formulation of Cooperative Games
We focus on characteristic function form (coalition) games. A characteristic function game is a typical representation of cooperative games proposed by von Neumann and Morgenstern. In characteristic function games, a characteristic function is used, which takes as its argument a subset of the players' coalitions and gives the gain obtained by each coalition.
A cooperative game in characteristic function form is represented by a set of players participating in the game \(\mathcal{A}\) and a pair of characteristic functions \(v\), \((\mathcal{A},v)\). The coalition and the characteristic function of the cooperative game are defined as follows [15].
Definition 1. (Coalition) Let \(\mathcal{A}=\{1, 2, \ldots, a\}\) be the set of all players participating in the game. The set of all players participating in the game is \(\mathcal{A}=\{1,2,\ldots,a\}\), and any subset \(\mathcal{D}\) of \(\mathcal{A}\) is called an coalition.
Definition 2. (Characteristic Function) The characteristic function \(v:2^{\mathcal{A}}\to\mathbb{R}\), for any coalition \(\mathcal{D}\), gives the gain \(v(\mathcal{D})\) when the players in the coalition \(\mathcal{D}\) cooperate.
Next, we describe a characteristic function that is additive. When two coalitions merge, such a characteristic function is said to be additive if the new coalition is greater than or equal to the sum of the gains of the original two coalitions [15].
Definition 3. (Preferential Characteristic Function) For any coalition \(\mathcal{D}_i\) and \(\mathcal{D}_j\) satisfying \(\mathcal{D}_i\) and \(\mathcal{D}_j=\emptyset\), a characteristic function satisfying \(v(\mathcal{D}_i)+v(\mathcal{D}_j)\le v(\mathcal{D}_i\cup\mathcal{D}_j)\). The characteristic function satisfying \(v(\mathcal{D}_i\cup\mathcal{D}_j)\) is called the superior additive characteristic function.
When the characteristic function is additive, the solution to the coalition structure generation problem is obvious, and the optimal coalition structure is the overall coalition (an coalition consisting of all players). However, the larger the coalition, the smaller the gain may be, and sometimes it is better to have the smallest possible coalition. In the coalition structure generation problem described below, the objective is to find the combination of coalitions (coalition structure) that maximizes the sum of the gains when the characteristic function is not dominant.
2.3 Coalition Structure Generation
As mentioned earlier, the total coalition is not always optimal, and players can maximize the sum of their gains by splitting into multiple coalitions of appropriate size. Such a problem is called the coalition structure generation problem and can be formulated as a complete set partitioning problem [10]. The study of coalition structure generation problems can be applied to distributed routing problems, multi-sensor networks, and other fields. In recent years, many researchers in the field of multi-agent systems have proposed algorithms for efficiently solving the coalition structure generation problem [11]-[14], [16].
The coalition structure is defined as follows [15].
Definition 4. (Coalition Structure) A \(CS=\{\mathcal{D}_1,\mathcal{D}_2,\dots\}\) that satisfies the following properties is called a coalition structure. \[\begin{equation*} \mathcal{D}_i\cap\mathcal{D}_j=\emptyset, \bigcup_{\mathcal{D}_i\in CS}\mathcal{D}_i=\mathcal{A}, \forall i, j(i\neq j). \tag{1} \end{equation*}\]
The gain \(V(CS)\) of the coalition structure \(CS\) is given by the sum of the gains of each coalition in the coalition structure as follows,
| \[\begin{equation*} V(CS)=\sum_{\mathcal{D}_i\in CS}v(\mathcal{D}_i). \tag{2} \end{equation*}\] |
In addition, the optimal coalition structure is defined as follows [15].
Definition 5. (Optimal Coalition Structure) We call the optimal coalition structure \(CS^*\) the coalition structure that satisfies the following,
| \[\begin{equation*} \forall CS, V(CS^*)\le V(CS). \tag{3} \end{equation*}\] |
In this study, we control the reassignment so as to obtain this optimal coalition structure \(CS^*\).
3. Related Work
3.1 DASH
In order to maximize the QoE of the user, various bit rate selection methods have been proposed using MPEG-DASH. In recent years, the existing researches are mainly classified into the following three categories.
1. Throughput-based methods: The main basic rate-based (RB) methods [17] and FESTIVE [18] use the predicted throughput for bitrate selection. The throughput is predicted using the harmonic mean, and the maximum bitrate lower than this prediction is selected.
2. Buffer-based methods: Buffer-based (BB) methods [19] and BOLA [20] use buffer occupancy information to control video streaming. BB only considers buffer occupancy, while BOLA uses Lyapunov's optimization to determine the bit rate.
3. Hybrid methods: The bit rate is selected using the throughput, buffer occupancy, and other information. The main methods are Model Predictive Control (MPC) [21] and Machine Learning Pensieve [22]. Pensieve uses reinforcement learning (RL) to enhance the neural network model to select the bit rate based on the previous results of bandwidth, buffer occupancy, and bit rate.
Thus, research has been conducted to improve the user QoE by controlling the bit rate selection of DASH. From the above selection methods, in this study, we use FESTIVE, which is not affected by buffer size, to observe the QoE of users in a multi-server environment.
3.2 Game Theory in DASH Environment
To improve the QoE of DASH users, game-theoretic methods have been proposed [23]-[25].
First, a method is proposed to design and formulate a decision-making problem by using a negotiation game and a consensus mechanism to achieve high and stable user QoE in VoD streams [23]. The method uses cooperative and non-cooperative game-like techniques depending on the number of players in the game. The method shows an average QoE and stability improvement of 38.5 and 62%, respectively, over existing methods, and is capable of reducing rebuffering and startup delays.
H. Yuan, et al. [24] formulate the concurrent bandwidth problem in DASH streaming using noncooperative game theory. The method proposes a new QoE model that incorporates various parameters such as actual and referenced buffer lengths and perceived video quality, in addition to a rate adaptation algorithm to improve user QoE while ensuring fairness among players.
A. Bentaleb et al. [25] propose a fully distributed joint HAS (FDCHAS) method for VoD services based on game theory with a consensus mechanism. The method involves a two-stage game on the user and network sides, respectively, and shows that this can improve user QoE, stability, and fairness.
However, since these methods do not consider multi-server environments, they cannot solve the problem of which server a user should connect to.
3.3 User Allocation Method
User allocation in a multi-server environment, which is the main objective of this research, is formulated using cooperative game theory in [6]. A gain function is defined based on the bandwidth of the server and the required video quality of the user, and user allocation is performed based on the gain obtained by this function. This method can improve the average video quality of users, but in this experiment, the video quality demanded by users is predetermined and does not correspond to the dynamic variation of DASH. Therefore, if this method is applied to the actual DASH behavior, there is a concern that the QoE may drop due to the concentration of users on a specific server when the quality demanded by users is extremely low.
In order to avoid this user concentration, we introduce the coalition structure generation problem to improve the QoE of all users by dynamically distributing users according to the bandwidth of the server and the quality requirements of the users without concentrating them on a specific server.
4. Proposed Method
4.1 Problem Formulation
First, we describe the multi-server environment in this research. In order to increase the bandwidth available to the user, our environment consists of multiple servers with different bandwidths in a row, thus pseudo-increasing the overall bandwidth of the system. Each user selects one of these servers and connects to it to watch DASH streaming. Note that our proposed system requires centralized control with a master device to summarize local information of each server and user.
Next, we model the underlying network in this study as a bipartite graph \(\mathcal{G}(\mathcal{U},\mathcal{S},\mathcal{E},\mathcal{W})\). The graph \(\mathcal{G}\) mainly internally connects a set of servers \(i\) \(\mathcal{S}\)\((i\in\mathcal{S})\) and a certain number of users (DASH users) \(\mathcal{U}\). On the other hand, \(\mathcal{E}\) represents the edge (network edge) connecting user \(\mathcal{U}\) and server \(\mathcal{S}\), and \(\mathcal{W}\) represents the E2E bandwidth between \(\mathcal{U}\) and \(\mathcal{S}\). For simplicity, overlay networks are considered, and intermediate routers and switches (backbone) are abstracted [6]. However, the proposed model is orthogonal and can be easily adapted and extended to account for intermediate network components. Since DASH streaming is a fully distributed system and user behavior is mainly affected by network behavior, we assume that the user is always measuring the bandwidth [6]. Let the number of users be \(U\) and the number of servers in the system be \(S\), where \(\boldsymbol{b}=(b_1,b_2,..b_S)\) is the bandwidth of the server, and \(\lambda_u\) represents the required video quality of user \(u\)\((u\in\mathcal{U})\). Figure 1 below shows a summary of the assumed environment for the above content.
 |
Fig. 1 Assumed environment. |
In this study, we also utilize cooperative game theory to improve QoE in a multi-server environment. The objective of the game is to improve the QoE of all users by optimizing the user allocation based on the server bandwidth and the quality requirements of the users. In this study, we first use a coalitional game in which players create various coalitions to increase their profits.
Define the game as \(\mathcal{G}(\mathcal{P},\mathcal{C},\mathcal{F})\), where \(\mathcal{P}\) is the set of players \(p\) in the system who are DASH users (\(\mathcal{P}=\mathcal{U}\)), \(\mathcal{C}\) is the number of coalitions. In this game, users using the same server form a single coalition, so the number of coalitions is fixed and equal to the number of servers in the system (\(\mathcal{C}=\mathcal{S}\)). The coalition for each server is denoted as \(\mathcal{C}=\{\mathcal{C}_1,\mathcal{C}_2,\cdot\cdot\mathcal{C}_S\}\). However, it is assumed that each of the two coalitions contains a different player (\(\mathcal{C}_i,\mathcal{C}_j:i\neq j\Longrightarrow\mathcal{C}_i\cap\mathcal{C}_j=\emptyset\)). Also, let \(\mathcal{C}_{\rm{all}}\) be the overall coalition consisting of all players in the game, and let the coalition \(\mathcal{C}_i\)\((\mathcal{C}_i\in \mathcal{C})\), and let \(\mathcal{F}\) be the characteristic function that defines the gain of the coalition \(\mathcal{C}_i(\mathcal{C}_i\in \mathcal{C})\).
4.2 Algorithm of Our Proposed Method
When allocating each user to a server, this study considers that the gain is increased by selecting an coalition (in this study, a server) that has more bandwidth per user that can be used by the users in the future. Therefore, we define the gain from the coalition as the difference between the requested video quality and the server bandwidth. We assume that the larger the difference between the server's bandwidth and the user's requested video quality, the more likely it is to provide good video quality to the users connected to that server. Based on the above, we define the characteristic function of the coalitional game as follows,
| \[\begin{equation*} \forall\mathcal{C}_i \in \mathcal{C} : \mathcal{F}(\mathcal{C}_i)=b_i-\sum\limits_{p\in\mathcal{C}_i}\lambda_p. \tag{4} \end{equation*}\] |
For Eq. (1), if \(\mathcal{C}_i=\emptyset\), the calculation is performed with \(\mathcal{F}(\mathcal{C}_i)=0\). Next, we describe Algorithm 1, which performs the coalition and migration of multiple users in this study. First, in the initialization phase (lines 2 to 4), \(|\mathcal{C}_i|\) is the number of users in \(\mathcal{C}_i\), and the number of users according to the ratio of \(\boldsymbol{b}\) is assigned to each server \(i\). Also, initialize the user migration flag variable \(migrated\) with \(False\). This variable is used to indicate whether the migration has been successfully performed for a specific player (user) \(p\), and by using this variable, the algorithm can be repeated with existing users and servers each time the migration is performed. The outer loop statement (line 6) is used to ensure that all existing coalitions (servers) and their corresponding players (users) are iterated.
 |
Line 7 initializes \(migrated\) to \(false\) each time a migration is performed. Next, we loop through the existing servers (line 8), and for each user belonging to that server (line 9), we check if that user should be migrated to another server. Note that all users in the coalition are assumed to be the same user. Therefore, the results do not depend on the selected users in the coalition in line 9. To do this, we need to iterate through the available servers, except for the one to which the user currently belongs (line 10).
Then, the function \({\rm CHECK\_MIGRATION}(p,\mathcal{C}_i,\mathcal{C}_j)\) is called to migrate player \(p\) based on the migration condition and Algorithm 2 described below. When the migration takes place, it returns \(true\) to the variable \(migrated\) to terminate all loops except the current loop and the outer loop statement. If migration does not take place, it continues looping for the remaining players and coalitions. These processes iterate the migration of users and set the number of people in each coalition \(|\mathcal{C}_i|\) to an appropriate value.
 |
4.3 Conditionals and Migration Algorithm
In a coalitional game, players increase their gain by continuously migrating from one coalition to another, but in this study, we efficiently increase the gain by adding a condition for the migration. We denote the two coalitions in the game as \(\mathcal{C}_i\) and \(\mathcal{C}_j\), and when a player \(p\) in \(\mathcal{C}_i\) migrations from \(\mathcal{C}_i\) to \(\mathcal{C}_j\), the player \(p\) in \(\mathcal{C}_i\) will have \(\overline{\mathcal{C}_i}^p\) and \(\widehat{\mathcal{C}_j}^p\). If the set consists of only two coalitions, then \(\mathcal{C}_{\rm{all}}=\mathcal{C}_i\cup\mathcal{C}_j\) and \(\mathcal{C}_i\cup\mathcal{C}_j=\emptyset\) are valid. Based on these contents, the migration conditions for players defined in the existing study [6] are shown below.
Definition 6. Migration conditions for conventional research [6]
| \[\begin{eqnarray*} &&\!\!\!\!\! \{\mathcal{C}_i,\mathcal{C}_j\}\rhd^p\{\overline{\mathcal{C}_i}^p, \widehat{\mathcal{C}_j}^p\} \tag{5} \\ &&\!\!\!\!\! \Longleftrightarrow\mathcal{F}(\overline{\mathcal{C}_i}^p)>\mathcal{F}(\mathcal{C}_i)\land \mbox{}\mathcal{F}(\widehat{\mathcal{C}_j}^p)>\mathcal{F}(\mathcal{C}_i) \nonumber \end{eqnarray*}\] |
where \(\rhd^p\) represents the migration of player \(p(p\in\mathcal{C}_i)\), and on the left side, it represents the migration of player \(p\) for two coalitions \(\{\mathcal{C}_i,\mathcal{C}_j\}\), which creates a new coalition \(\{\overline{\mathcal{C}_i}^p,\widehat{\mathcal{C}_j}^p\}\) is generated by the migration of player \(p\). Next, for the right-hand side, \(\mathcal{F}(\overline{\mathcal{C}_i}^p)>\mathcal{F}(\mathcal{C}_i)\) is the gain function (5) from \(\overline{\mathcal{C}_i}^p\) to \(\sum\limits_{p\in\overline{\mathcal{C}_i}^p}\lambda_p\) is less than \(\mathcal{C}_i\)'s \(\sum\limits_{p\in\mathcal{C}_i}\lambda_p\), so it clearly holds. Also, for \(\mathcal{F}(\widehat{\mathcal{C}_j}^p)>\mathcal{F}(\mathcal{C}_i)\), when the gain of the new coalition \(\widehat{\mathcal{C}_j}^p\) is higher than the gain of the original coalition \(\mathcal{C}_i\) For \(\widehat{\mathcal{C}_j}^p\), the migration is established when the gain of the new coalition \(\widehat{\mathcal{C}_j}^p\) is higher than the gain of the original coalition \(\mathcal{C}_i\).
In addition to the above coalitional games, we introduce the coalition structure formation problem into the migration condition. This is an idea to maximize the total gain of the players in a cooperative game by dividing the coalition into several parts when the gain from all coalitions \(\mathcal{C}_{\rm{all}}\) is not the maximum gain. By introducing this coalition structure formation problem, we aim to avoid the concentration of users on a specific server in this research.
Definition 7. Migration conditions considering the coalition structure generation problem
| \[\begin{eqnarray*} &&\!\!\!\!\! \{\mathcal{C}_i,\mathcal{C}_j\}\rhd^p\{\overline{\mathcal{C}_i}^p, \widehat{\mathcal{C}_j}^p\}\nonumber \\ &&\!\!\!\!\! \mbox{}\Longleftrightarrow\mathcal{F}(\overline{\mathcal{C}_i}^p)+\mathcal{F}(\widehat{\mathcal{C}_j}^p)>\mathcal{F}(\mathcal{C}_i)+\mathcal{F}(\mathcal{C}_j). \tag{6} \end{eqnarray*}\] |
Equation (6) indicates that a migration is successful when the total gain of the migration coalition \(\{\overline{\mathcal{C}_i}^p,\widehat{\mathcal{C}_j}^p\}\) is higher than the total gain of pre-migration coalition \(\{\mathcal{C}_i,\mathcal{C}_j\}\) for a player \(p\)\((p\in\mathcal{C}_i)\). This assumes that the set consists of only two coalitions, as in (6) above, and that users are concentrated in one coalition that is, \(\mathcal{C}_i=\mathcal{C}_{\rm{all}}\) and \(\mathcal{C}_j=\emptyset\). In order to avoid this problem, we divide the number of coalitions into the same number as the number of servers according to the coalition structure generation problem.
Based on the above two conditional Eqs. (5) and (6), the player in our game migrations the coalition. The condition for the migration depends on the state of the coalition \(\mathcal{C}_j\) to which the player \(p\) is migrationing, and only condition (6) is applied when \(\mathcal{C}_j=\emptyset\), while conditions (5) and (6) are applied when \(\mathcal{C}_j\neq\emptyset\). The conditional expression based on the above classification is shown below.
Definition 8. Migration conditions of our method
| \[\begin{eqnarray*} &&\!\!\!\!\! \{\mathcal{C}_i,\mathcal{C}_j\} \rhd^p \{\overline{\mathcal{C}_i}^p,\widehat{\mathcal{C}_j}^p\},\mathcal{C}_j=\emptyset\nonumber\\ &&\!\!\!\!\! \mbox{}\Longleftrightarrow\mathcal{F}(\overline{\mathcal{C}_i}^p)+\mathcal{F}(\widehat{\mathcal{C}_j}^p)>\mathcal{F}(\mathcal{C}_i)+\mathcal{F}(\mathcal{C}_j), \tag{7} \\ &&\!\!\!\!\! \{\mathcal{C}_i,\mathcal{C}_j\} \rhd^p\{\overline{\mathcal{C}_i}^p,\widehat{\mathcal{C}_j}^p\},\mathcal{C}_j\neq\emptyset \nonumber \\ &&\!\!\!\!\! \mbox{}\Longleftrightarrow\mathcal{F}(\overline{\mathcal{C}_i}^p)+\mathcal{F}(\widehat{\mathcal{C}_j}^p)>\mathcal{F}(\mathcal{C}_i)+\mathcal{F}(\mathcal{C}_j)\land\nonumber\\ &&\!\!\!\!\! \mbox{}\mathcal{F}(\overline{\mathcal{C}_i}^p)>\mathcal{F}(\mathcal{C}_i)\land\mathcal{F}(\widehat{\mathcal{C}_j}^p)>\mathcal{F}(\mathcal{C}_i). \tag{8} \end{eqnarray*}\] |
Finally, the function CHECK_MIGRATION (line 11) of the migration algorithm based on the above information is shown in Algorithm 2. In the definition of the Coalition Structure Generation, when the total gain of a coalition that migrates users is greater than the total gain of a coalition, user migrate. This final total gain is maximized by a coalition with migrated users, thus the total gain obtained in our proposed method is also guaranteed to be the maximum value.
5. Numerical Analysis
In this study, our simulation was performed using NS (Network Simulator)-3. We use the total number of segments \(N\) as the QoE evaluation value when DASH streaming is 300 s under the conditions of \(U=10,20,30\), \(S=4\), and \(\boldsymbol{b}=\) (90, 70, 50, 30) Mbps. The bitrate selection method is FESTIVE [18], and there are seven selectable image quality levels: 88 k, 3 M, 5.9 M, 8.8 M, 11.8 M, 14.7 M, and 17.6 Mbps. In addition, every 100 s, a reallocation is performed using the aforementioned migration conditions. We define the following equations with reference to [22]: \(r_n\) as the selected image quality for the \(n\)th segment (\(n\le N\)), \(r_{\rm{min}}\) as the minimum image quality, and \(QoE_u\) as the QoE of the user in the \(u\)th segment (\(u\le U\)). In this study, we assume an environment where the minimum image quality is compensated, so we exclude the term to account for buffer underrun.
| \[\begin{equation*} QoE_u=\sum\limits_{\mathit{n}=1}^{N} q(r_{n})-\sum\limits_{n=1}^{N-1}\vert q(r_{n+1})-q(r_{n})\vert, \tag{9} \end{equation*}\] |
where:
| \[\begin{equation*} q(r_n)=\log(r_{n}/r_{\min}). \tag{10} \end{equation*}\] |
The average QoE of all users is defined as \(QoE_{\rm{Average}}\), as follows,
| \[\begin{equation*} QoE_{\rm{Average}}=(\sum\limits_{u=1}^U QoE_u)/U. \tag{11} \end{equation*}\] |
Figure 2 shows the results of the simulation based on the above conditions and evaluation equations. As shown in Fig. 2, the proposed method can improve the average QoE of all users compared to the existing method. Also, the difference in QoE is larger when the number of users \(U\) is large. In our numerical analysis, we set \(S=4\). As the number of servers increases, the QoE will increase since the number of migration candidates will increase. However, if the number of servers is greater than the number of users, the QoE will not change because each user can connect to each server without multi server. Next, for each term on the right-hand side of Eq. (9), the average value of all users in the first term is \(q_{\rm{sum}}\), and the average value of all users in the second term is \(q_{\rm{sub}}\), as shown in Figs. 3 and 4, respectively.
 |
Fig. 2 QoE average per number of users. |
 |
Fig. 3 Average of first term of QoE evaluation formula. |
 |
Fig. 4 Average of second term of QoE evaluation formula. |
The \(q_{\rm{sum}}\) is the evaluation value mainly due to the image quality selected by the user. As shown in Figure 3, the average of the image quality selected by the users is higher in the proposed method compared to the existing methods. This can be attributed to the fact that the upper limit of the maximum image quality that can be selected by a user has been raised by pseudo-increasing the bandwidth that each user can use per person by avoiding the concentration of users in the proposed method.
Next, \(q_{\rm{sub}}\) is the evaluation value due to the variation difference in image quality selected by the user. As shown in Fig. 4, we were able to suppress the variation difference in image quality compared to the existing method and maintain stable video quality. In particular, when the bandwidth pressure is improved by avoiding the concentration of users (\(U=10,20\)), the video quality can be stabilized significantly.
Finally, the number of people connected to a specific server (Server1) in the conventional method [6] is \(U_{\rm{con}}\) and the number of people connected in the proposed method is \(U_{\rm{pro}}\). The reduction rate of user concentration in a specific server for each number of users compared to the existing method, \({U_{\rm{pro }}/U_{\rm{con}}}\times 100\) is shown in Fig. 5.
 |
Fig. 5 Reduction rate in user concentration on server. |
As shown in Fig. 5, the concentration of users on a particular server decreased by more than 60 percent in all cases, indicating that the coalition structure generation problem can be used to avoid the concentration of users on a particular server. This reduction in user concentration increases the bandwidth available to a single user, allowing him or her to select a higher quality image, which is thought to increase the QoE.
6. Conclusion
We proposed a user allocation method that improves an average QoE of all users in a DASH multi-server environment by considering the bandwidth used by the overall system when allocating users and by using the coalition structure generation problem. Moreover, we extended our control to also take into account the variation of the average required bit rate of the user's video. As a result, by introducing the coalition structure generation problem in the migration condition, we were able to avoid the concentration of users on a particular server and improve the average QoE.
In the future, we will consider reallocation of user and propose a system that takes user characteristics into account, such as a billing system.
Acknowledgments
These research results were obtained from the commissioned research (No.05601) by National Institute of Information and Communications Technology (NICT), Japan. This work was supported by JSPS KAKENHI Grant Numbers JP19K11947, JP22K12015, 22H00247.
References
[1] S. Zhang, B. Li, and B. Li, “Presto: Towards fair and efficient HTTP adaptive streaming from multiple servers,” Proc. Conference of IEEE International Conference on Communications (ICC), pp.6849-6854, 2015.
CrossRef
[2] T. Bat-Erdene, Y.N.H. Zayed, X. Qiu, I. Shakoor, A. Mekni, P.A. Kara, M.G. Martini, L. Bokor, and A. Simon, “On the quality of experience of content sharing in online education and online meetings,” Infocommunications Journal, vol.XIV, no.2, pp.73-84, June 2022.
CrossRef
[3] ISO/IEC, “23009-1 Dynamic adaptive streaming over HTTP (DASH),” Part1: Media presentation description and segment formats, 2012.
[4] GMDT Forecast, et al., “Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update, 2017-2022,” Update, vol.2017, p.2022, 2019.
[5] A.A. Barakabitze, N. Barman, A. Ahmad, S. Zadtootaghaj, L. Sun, M.G. Martini, and L. Atzori, “QoE management of multimedia streaming services in future networks: A tutorial and survey,” IEEE Commun. Surveys Tuts., vol.22, no.1, pp.526-565, Firstquarter 2020, doi: 10.1109/COMST.2019.2958784.
CrossRef
[6] O. El Marai, M. Bagaa, and T. Taleb, “Coalition game-based approach for improving the QoE of DASH-based streaming in multi-servers scheme,” Proc. Conference of IEEE Global Communications Conference (GLOBECOM), pp.1-6, 2020.
CrossRef
[7] S. Miyata and K. Yamaoka, “Reducing total call-blocking rates by flow admission control based on equality by heterogeneous traffic,” Infocommunications Journal. vol.LXV, pp.27-34, April 2010.
[8] A. Okada, Game Theory, 1996 (in Japanese).
[9] S. Mutou M. Nakayama, and Y. Hunaki, Kyouryoku Ge-mu Riron, 2008 (in japanese).
[10] D. Yun Yeh, “A dynamic programming approach to the complete set partitioning problem,” BIT, vol.26, no.4, pp.467-474, Dec. 1986.
CrossRef
[11] N. Ohta, V. Conitzer, R. Ichimura, Y. Sakurai, A. Iwasaki, and M. Yokoo, “Coalition structure generation utilizing compact characteristic function representations,” Trans. Japanese Society for Artificial Intelligence, vol.26, no.3, pp.451-460, 2011.
CrossRef
[12] T. Rahwan and N.R. Jennings, “An improved dynamic programming algorithm for coalition structure generation,” Proc. 7th International Joint Conference on Autonomous Agents and Multiagent Systems, vol.3, pp.1417-1420, 2008.
CrossRef
[13] T. Rahwan, S.D. Ramchurn, V.D. Dang, A. Giovannucci, and N.R. Jennings, “Anytime optimal coalition structure generation,” AAAI, vol.7, pp.1184-1190, 2007.
[14] T. Sandholm, K. Larson, M. Andersson, O. Shehory, and F. Tohmé, “Coalition structure generation with worst case guarantees,” Artificial Intelligence, vol.111, no.1-2, pp.209-238, 1999.
CrossRef
[15] M. Yokoo, A. Iwasaki, Y. Sakurai, and Y. Okamoto, “Game theory for computer scientists ― Cooperative games ―,” Computer Software, vol.30, no.2, pp.33-51, 2013 (in Japanese).
[16] S. Ueda, M. Kitaki, A. Iwasaki, and M. Yokoo, “Concise characteristic function representations in coalitional games based on agent types,” Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
[17] B. Wei, H. Song, S. Wang, and J. Katto, “Performance analysis of adaptive bitrate algorithms for multi-user DASH video streaming,” Proc. Conference of IEEE Wireless Communications and Networking Conference (WCNC). pp.1-6, 2021.
CrossRef
[18] J. Jiang, V. Sekar, and H. Zhang, “Improving fairness, efficiency, and stability in HTTP-based adaptive video streaming with FESTIVE,” Proc. 8th International Conference on Emerging Networking Experiments and Technologies, pp.97-108, 2012.
CrossRef
[19] T.-Y. Huang, R. Johari, N. McKeown, M. Trunnell, and M. Watson, “A buffer-based approach to rate adaptation: Evidence from a large video streaming service,” Proc. 2014 ACM Conference on SIGCOMM, pp.187-198, 2014.
CrossRef
[20] K. Spiteri, R. Urgaonkar, and R.K. Sitaraman, “BOLA: Near-optimal bitrate adaptation for online videos,” IEEE/ACM Trans. Netw., vol.28, no.4, pp.1698-1711, 2020.
CrossRef
[21] X. Yin, A. Jindal, V. Sekar, and B. Sinopoli, “A control-theoretic approach for dynamic adaptive video streaming over HTTP,” Proc. ACM Conference on Special Interest Group on Data Communication, pp.325-338, 2015.
CrossRef
[22] H. Mao, R. Netravali, and M. Alizadeh, “Neural adaptive video streaming with pensieve,” Proc. Conference of the ACM Special Interest Group on Data Communication, pp.197-210, 2017.
CrossRef
[23] A. Bentaleb, A.C. Begen, S. Harous, and R. Zimmermann, “Want to play DASH? A game theoretic approach for adaptive streaming over HTTP,” Proc. 9th ACM Multimedia Systems Conference, MMSys'18, New York, NY, USA, pp.13-26, 2018, Association for Computing Machinery.
CrossRef
[24] H. Yuan, H. Fu, J. Liu, J. Hou, and S. Kwong, “Non-cooperative game theory based rate adaptation for dynamic video streaming over HTTP,” IEEE Trans. Mobile Comput., vol.17, no.10, pp.2334-2348, 2018.
CrossRef
[25] A. Bentaleb, A.C. Begen, S. Harous, and R. Zimmermann, “A distributed approach for bitrate selection in HTTP adaptive streaming,” Proc. Conference of ACM Multimedia Conference on Multimedia Conference, MM 2018, pp.573-581, 2018.
CrossRef
Authors
Shibaura Institute of Technology
received the B.E. degree from the Shibaura Institute of Technology in 2007, and the M.E. and D.E. degrees from the Tokyo Institute of Technology in 2009 and 2012 respectively. From 2012 to 2015, she was a research associate at the Kanagawa University. Since 2015, she had been an assistant professor at the Shibaura Institute of Technology. Since 2018, she has been an associate professor at the Shibaura Institute of Technology. Her research interests include mathematical modelling and analysis for QoS performance evaluation, queuing theory, game theory and resource allocation problems in communication networks and information security.
 |
Shibaura Institute of Technology
received B.E., M.E., and Ph.D. degrees in communications engineering from Osaka University in 2000, 2001, and 2003, respectively. He joined the Graduate School of Informatics, Kyoto University and worked there as an assistant professor from 2003 to 2011 and as an associate professor from 2011 to 2021. He was a visiting scholar at the Wireless Information Network Laboratory, Rutgers University from 2008 to 2009. In 2021, he joined the Faculty of Engineering, Shibaura Institute of Technology as a professor. In May 2023, he founded Hyper Digital Twins Co., Ltd. (HDT), where he is currently a director. He has published more than 160 reviewed papers. His main research interest is cooperation in heterogeneous networks. He received the young researchers' award, the best tutorial paper award of the Communications Society, the best paper award from the IEICE in 2006, 2019, and 2022, respectively. He also received the Young Scientist Award from Ericsson Japan in 2007 and the TELECOM System Technology Award from the Telecommunications Advancement Foundation in 2016. He is a fellow of the IEICE and a senior member of the IEEE.
 |
