A Simulation - Based algorithm for rrm

Hi, my name is David Fernández Piñas and I am going to present you my final project for the Open Source and Free Software Master of the Universitat Oberta de Catalunya. It is a research developed with the Internet Computing and Systems Optimization group about the design and implementation of an algorithm for the management of radio resources in satellite communications networks. Next slide: 2/22 Heafter is shown the index of the presentation. First of all, the project topic will be introduced. Some key concepts will be explained. Then, the problem addressed in this research will be described. It is a minimization problem. Next, it will be commented the literature review performed at the initial stage of the research, and the main issues found. In the "Our Approach" section, it will be described the new algorithm designed and implemented in order to efficiently manage the network radio resources. The results of several computational experiments performed with the implementation of the proposed algorithm are shown next. Finally, the conclusions of the research and possible future extensions are commented. Next slide: 3/22 The next figure shows the main aspects of the considered satellite network. It has a star topology. The terminals compete for the communication resources. Terminals convey their needs to the central hub, which assigns them resources in order to satisfy traffic quality of service needs, using the minimum resources. Next slide: 4/22 Terminals can get assigned three types of resources, radio- frequency bursts, depending on their current link budget: Bad, Average or Good. Next slide: 5/22 The period of resources assignment can be dimensioned analytically, following some considerations. The selection of a resources assignment period multiple of the shorter burst duration eases the resources management. Next slide: 6/22 As the considered system is based on Multi-Frequency Time Division Multiple Access, periodically, the available time and bandwidth must be assigned to the terminals. This can be done following and structured approach, where the available spectrum is first divided into carriers, then the frames of the carriers are assigned, or it can be done following an unstructured approach, assigning directly chunks of bandwidth and time anywhere, as shown in the right part of the figure. An structured approach is less optimum in the usage of resources, but minimizes signalling required to communicate the assignments to the terminals and requires less computational resources, while an unstructured approach allows the maximum optimization but makes the problem computationally hard. Next slide: 7/22 Five traffic profile files have been generated to perform the research. In each file, the arrival of requests for capacity at the network hub are described. Each request is of one of the three types of bursts shown before (slide 4) and it has an associated expiration time. Somehow, the traffic profile can be represented as falling blocks of a Tetris like game. If the needs are not allocated resources before they reach the floor, they are lost. If the transmission timeout is lower than the assignment period, the allocation of resources to a need is mandatory, otherwise it can still wait to the next allocation period. Next slide: 8/22 The problem addressed is how to minimize the bandwidth required to satisfy all the communication needs specified in the considered traffic profile, but also trying to keep low the size of the resulting Burst Time Plan (BTP), required to communicate the hub assignments to the terminals, and respecting some additional constraints. Next slide: 9/22 Before starting to search a way to solve the mentioned problem, a literature survey was performed in order to check if this problem had been addressed before and how. Several papers were found addressing the topic, but for best effort data traffic, without strict delay constraints, and all the papers found discarded unstructured approaches, due to the mentioned reasons (slide 6). One of the found papers, proposed the use of packing heuristics for static on-demmand assignment of resources (not each few milliseconds, as in our case), but previous experiences in the operations research field, made us suspect that a not so complex packing heuristic could be used also in our case, with assignments each 260 ms. Because of this, a literature survey on 2D strip packing algorithms was done, in order to select the heuristic that would be better for our problem characteristics. The literature research went further, to metaheuristics also. This has given ideas for future expansions of this research, in terms of the use of randomization and parallelization. Next slide: 10/22 As it has been mentioned, we propose an unstructured approach for solving the problem, but in order to minimize the signalling required, the frequency hoping of terminals is minimized when assigning resources, by aggregating contiguous needs from a single terminal. The Best Fit Decreasing Height heuristic is selected to solve the problem, after it is found in the literature survey that it can be used to place thousands of rectangles in hundredths of milliseconds. Finally, just mention that the scheduling of pending transmission needs is done according to an Earliest Deadline First policy, which is considered a very efficient one in the telecommunications literature. Next slide: 11/22 What follows now is an explanation of how the designed and implemented algorithm, based on the Best Fit Decreasing Height heuristic, works. The arriving transmission requests are checked each allocation period SF_T. They can be represented as falling blocks in the time dimension. Blocks from the same terminal are piled in columns, one per terminal. The solid rectangles are transmissions which timeout has exceeded the so called obliged transmission threshold, so they must be allocated in the next assignment period, while the outlined rectangles are transmissions that can still wait until the next period. The minimum possible value for the obliged transmission threshold is the allocation period, but it is convenient to make it higher, to avoid packet losses due to transmitter overload, which can happen due to the arrival of a packet with a short expiration time after a big packet with a long expiration time, which transmission has been excessively delayed due to a very low value of the obliged transmission threshold. Next slide: 12/22 Once collected and aggregated, optional and mandatory transmissions are stored in two vectors ordered by decreasing duration. The so called floor bursts vector contains the transmissions starting at the beginning of the assignment period and the floating bursts vector contains the transmissions that follow another previous transmissions that it has not been possible to aggregate, because of having a different bandwidth. In order to minimize signalling, just assignments for transmissions with the same bandwidth from the same terminal are aggregated. The results show that Just a few assignment periods have floating bursts, as the case shown in the figure. The floating bursts are bottom-left packet to the floor bursts. If this initial packing results in a bandwidth occupation higher than the current maximum bandwidth configured, the packing based on the Best Fit Decreasing Height heuristic is performed, otherwise assignments are done. Next slide: 13/22 The Best Fit Decreasing Height heuristic is applied first for the packing of mandatory transmissions, which will determine the minimum bandwidth required. The remaining resources are filled afterwards with optional transmissions, applying also the Best Fit Decreasing Height heuristic. The packing is obtained by placing the transmissions from down to top and in columns, forming levels. In order to minimize the signalling required to communicate the assignments to the terminals, in our proposed algorithm just items of the same bandwidth are placed on a given level. If this can not be done, a new level is created. Notice that on a real system, the algorithm should discard mandatory transmissions if they need more bandwidth than the one available, while in our implementation it results in an update of the maximum bandwidth used result, because our objective was the study of algorithm performance, not just an implementation of an algorithm for a system. The figure shows a resulting packing with our algorithm. Next slide: 14/22 Although the algorithm has been implemented as a C/C++ console application, an OpenGL based viewer has been developed so we can see it in action from trace files. Hereafter is shown a five minutes extract of viewer output for file#3 with PLR=0. The viewer stops each time an assignment that results in an update of the maximum bandwidth used result happens or when there are floating bursts, otherwise it runs continuously, increasing the assignment period counter. Next slide: 15/22 The figures show the allocations performed in the period of maximum bandwidth use for the cases of PLR=0 (maximum value of obliged transmission threshold). Next slide: 16/22 Next slide: 17/22 Hereafter are shown figures indicating the resources utilitzation efficiency in function of time for file#1 (minimum load) and file#3 (maximum load). The resources utilitzation efficiency increases with load. Next slide: 18/22 The resulting minimum bandwidth required does not depend on the obliged transmission threshold configured. Next slide: 19/22 The same happens with the resources utilitzation efficiency. Next slide: 20/22 This figure shows how the packet loss rate due to overload diminishes as the obliged transmission threshold is increased. Next slide: 21/22 The research has produced a novel approach to the radio resources management in telecommunications networks for time constrained traffic, by adapting an algorithm from operations research to telecommunications, implementing it and demonstrating its performance. In the future it is expected that the application of randomization and parallelization could lead to even more optimized results, compared to this deterministic version. Next slide: 22/22 That's all! Thank you for your attention.