| Sažetak (engleski) | Increased bit rates in mobile networks and advancement in development of mobile devices causes more intensive use of multimedia services on the move. This also leads to increase in data traffic volume, calling for new resource management mechanisms which will take characteristics of multimedia services into account. This doctoral thesis deals with resource management in mobile networks based on service and user-related knowledge. The proposed solution builds on the description of multimedia services with different session configurations, corresponding to different utility levels. The idea is to use alternative session configurations in cases when the optimal one cannot be enforced, either at session admission time or during congestion when some resources of active sessions have to be released. %Besides the first configuration, which has the highest resource requirements and highest user perceived quality, several alternative configurations with decreased quality and resource requirements are defined. Service adaptation capabilities and user preferences are taken into account during creation of service configurations, so it is assumed that all configurations are acceptable to the users. Chapter 1 - Introduction Chapter 1 describes research motivation and contains a problem formulation, i.e., the research goal and hypothesis. The thesis research goal is to develop algorithms for admission control and resource allocation that will be based on service and user-related knowledge and adapted to demands of complex multimedia services with dynamic resource requirements, while considering priorities of different users and services. The research hypothesis is that the session admission control will be increased by using these algorithms, in comparison to the case when they are not used, and that the requested user perceived quality will be achieved or degraded in a controlled manner in case of resource shortage. The thesis research contribution consist of the following three parts: 1.) Admission control algorithm for multimedia sessions which increases session admission probability based on service and user-related knowledge, by using alternative session configurations in cases when the optimal configuration is not enforceable, 2.) Dynamic resource reallocation algorithm which achieves requested user perceived quality or enables controlled degradation thereof in case of resource shortage, 3.) Software simulator for verification of the proposed algorithms. The chapter ends with the description of the thesis structure. It summarizes the contents of each of the following chapters. Chapter 2 - Literature overview: description of multimedia sessions and session management The chapter provides a list of methodologies for description of multimedia services consisting of standardized methodologies and these proposed in the literature, with emphasis on the structure called Media Degradation Path (MDP). The MDP is a list of service configurations where each configuration contains service parameters (e.g., video resolution and frame rate, audio codec, etc.), resource requirements (e.g, bandwidth and maximum delay) and a utility value, which is a numeric indicator of user's satisfaction with regarding configuration. Besides the first configuration, which is optimal, several alternative configurations are defined and ordered by their decreasing utility value. During creation of alternative configurations user's preferences regarding flow importance are considered, i.e., flows that are more important are less likely to be degraded. Service adaptation capabilities are taken into account, too. It is thus assumed that alternative service configurations are acceptable to the users. An overview of session management in the 3rd Generation Partnership Project (3GPP) specifications is given, which includes a brief description of Long Term Evolution (LTE) network architecture, overview of resource management in LTE radio access network, in core network and in application domain, an overview of LTE control plane communication protocols and a brief description of improvements brought by LTE-Advanced. Description of LTE is followed by the overview of related work in admission control of sessions which lists basic concepts found in existing approaches. Next, an overview of existing approaches to resource allocation in literature is given. The chapter is concluded with chapter summary, which lists what is missing in current approaches and provides an introduction to the following sections. Chapter 3 - Admission control algorithm based on service and user-related knowledge The third chapter describes the admission control algorithm. First, it discusses the concept of MDP and identifies that it lacks a mechanism for description of service dynamics. It defines the concept of service state as a set of media flows that can be active simultaneously during session, which extends MDP with different sets of configurations for different service states. Following the modification of the MDP, the algorithm itself is described. First, a division of resource into different zones is explained, where a zone represents a portion of resources that can be assigned to a user, based on his category and the fact that the call is new or handed off from a neighbour network cell. Then, the admission control algorithm for sessions with single media flow is explained first for simplicity. The algorithm introduces the notion of critical border, i.e., the level of resource consumption that causes sessions to be admitted with alternative configurations instead of the optimal one. In this way, session admission probability is increased. Even if currently available resources are not sufficient for the optimal configuration, a session might still be admitted with an alternative configuration, which is still acceptable to the user, leading to increased user satisfaction. Having defined the algorithm for single media flow, the algorithm for sessions with multiple media flows is explained and its complexity analysis is provided. Two examples are given, illustrating algorithm behaviour in different situations. The chapter is concluded with analysis of scientific contribution and comparison to related work. Chapter 4 - Resource reallocation based on service and user-related knowledge The chapter describes resource reallocation algorithm. It begins with motivation for redistribution of already allocated resources: based on literature review, users prefer lower but constant average quality over fluctuations, so it is not advisable to redistribute already assigned resources. However, the existence of service states can lead to drastic changes in resource requirements of active sessions. Therefore, it is assumed that resource reallocation is justified in these extreme situations. By degrading some "greedy" sessions, according to the priorities of their users and the services they pertain to, a certain amount of resources is freed for new incoming sessions. The key idea of the approach is to utilize different configurations from MDPs of sessions and to switch some active sessions to less resource consuming configurations form their MDPs. The alternative configurations are acceptable to the users since users' preferences have been taken into account during creation of all configurations. This type of degradation is considered to be more acceptable to a user than an uncontrolled one, e.g, a uniform degradation of all service flows. The problem is mathematically formulated as a multi-choice multidimensional knapsack problem (MMKP), known to be NP-complete. Problem formulation aims to maximizes the weighted sum of two components, namely, users' utility (service quality, as perceived by the users) and operator's profit. The significance of each component can be altered by modifying the regarding weight factor. Constraints of the optimization problem include network bandwidth in downlink and uplink directions, as well as binary variables used for selection of configurations (exactly one configurations per session is selected). The algorithm is also formally written in pseudocode and the complexity analysis is provided. Formal definition is followed by the example of algorithm execution. The chapter is concluded with summary of scientific contribution and comparison to existing approaches in the literature. Chapter 5 - Implementation and verification of algorithms Verification of algorithms is explained in Chapter 5. First, an implementation of resource reallocation algorithm in Wolfram Mathematica 7.0 is described. It represents a static case where all the data is defined in advance and the algorithm is invoked manually. The optimization problem is solved by using optimisation methods built in Mathematica which find the optimal solution. The implementation has been evaluated and the following conclusions have been made. Search for the optimal solution is too time consuming (it can take over 30 seconds on a personal computer) and it is not applicable for real time scenario, thus making it clear that a heuristic algorithm has to be used instead. The ratio of degraded sessions is studied and it has been found that it depends on the intensity of degradation. Additionally, a lower limit of degradation of 40 % of initially assigned resources (for optimal configurations) is determined experimentally, however, it depends on the input dataset. In order to simulate both algorithms in a dynamic fashion, i.e., when they are run as needed, a simulator of multimedia sessions is developed and it is named ADAPTISE (ADmission control and resource Allocation for adaPtive mulTImedia SErvices). It simulates arrivals and durations of sessions by using different distributions, as well as, sessions' resource requirements and state changes. Each time a new session arrives, admission control algorithm is executed. When total resource consumption in the simulation reaches the predefined limit, resource reallocation algorithm is invoked and heuristic algorithm is used for finding a solution to the optimisation problem. Several different service types have been implemented and both algorithms have been tested independently. Since ADAPTISE's implementation is fairly abstract, the simulations in ADAPTISE have been rerun in LTE network simulator. For that purpose LTE-Sim 5.0 was used, which has been developed by Politecnico di Bari, in Italy. It simulates packet transmission over LTE radio network interface and takes into account the effects that can arise on the radio link. For each algorithm a set of instances has been run in ADAPTISE and each instance has been repeated in LTE-Sim 15 times, in order to take into account the average influence of variable radio link. Based on the results of tests in LTE-Sim the analysis of the algorithms impact has been conducted. Two sets of simulations have been run, one with an artificial traffic mix with equal ratios of five services types and one with the realistic traffic mix of current mobile networks. For the admission control algorithm 10 independent simulation instances have been run (for each traffic mix) and then repeated without using alternative service configurations, so that the admission decisions was made for one configuration only. Each such pair of simulation instances (with MDP and without it) has been rerun 15 times in LTE-Sim and the following conclusions have been derived: - number of admitted sessions can be increased in case of services with different quality configurations, with very little influence on quality, - number of admitted video sessions can be increased if the number of admitted sessions of other service types decreases, potentially leading to higher operator's profit. For the resource reallocation algorithm, 10 independent optimisation occurrences have been simulated in ADAPTISE (also for each traffic mix) and a trace has been created for the period before reallocation and the period after it. Each trace has been rerun in LTE-Sim 15 times, resulting in these conclusions: - total throughput of active sessions has been decreased and a portion of bandwidth has been set free for new incoming sessions, - depending on the ratios of currently active services, packet loss will either decrease or remain the same, i.e., conditions will be either improved or remain the same. The algorithms are mapped to the 3GPP LTE network architecture and it is suggested that the admission control algorithm runs on eNodeB nodes in the access network and that the resource reallocation algorithm runs on the Policy and Charging Rules Function (PCRF), assuming that application level signalling and calculation of MDP has been implemented in the network. Mapping of required signalling procedures to existing ones in 3GPP specifications is proposed and required changes in messages and/or sequences of messages are identified. Analysis of signalling overhead has been made, however, concrete influence of signalling still requires practical implementation in the network. Conclusion The conclusion summarises the research motivation and the goals that have been set and it explains how the research has been conducted. First, the chosen methodology for session description, i.e., the MDP, has been extended to support session dynamics and then the algorithms for admission control and resource reallocation have been developed based on the MDP. By using MDP knowledge about the user and the service was introduced to resource management procedures. Implementation of the algorithms has been developed in own simulator tool named ADAPTISE and simulations have also been verified in LTE network simulator. Additionally, a mapping of algorithms to 3GPP network architecture has been proposed. The future work will be based on using concrete measures of Quality of Experience (QoE) for verification of algorithms. Realistic QoE values could be acquired by using Mean Opinion Score (MOS) values or Willingness to Pay (WTP) information. Besides the knapsack-based formulation of resource reallocation problem, additional formulations will be examined and fairness of such approaches will be considered. |
