Contribución a la mejora del control de flujo en redes de acceso inalámbrico

Abstract

[SPA] Esta tesis se enmarca en el estudio de la red de transporte de las redes de acceso radio (Radio Access Networks, RANs), también denominado Backhaul. En particular esta tesis aborda los problemas asociados a la congestión en el Backhaul mediante una aproximación basada en teoría de control y la optimización matemática. Los problemas causados por la congestión en el Backhaul son de distinta naturaleza dependiendo de la tecnología RAN a la que da soporte. En esta tesis elaboramos un recorrido histórico por la evolución de las tecnologías RAN durante las dos últimas décadas, en el que nos centramos en las funcionalidades que dependen del Backhaul, y en las diferentes y en general, más exigentes, demandas que éstas imponen en la infraestructura de Backhaul. Iniciamos nuestro recorrido en las redes 3G (Universal Mobile Telecommunication System, UMTS), proseguimos con 3.5G (High Speed Data Access, HSDA) y finalizamos con 4G (Long Term Evolution, LTE). Describimos el impacto que la congestión del Backhaul tiene en cada una de ellas y se proponen mecanismos de control para contrarrestar sus efectos negativos. Los objetivos de esta tesis son los siguientes: 1. Proponer y evaluar mecanismos de control que mejoren el rendimiento de la sincronización de canal de transporte en FP en situaciones de congestión del backhaul. El marco tecnológico de este objetivo son las redes 3G (UMTS). 2. Proponer y evaluar mecanismos de control de flujo que consideren conjuntamente el interfaz radio y en el backhaul. El marco tecnológico de este objetivo es 3.5G (HSPA). 3. Proponer y evaluar un scheduling radio que considere conjuntamente los recursos del interfaz radio y del backhaul. El marco tecnológico de este objetivo es 4G (LTE). 4. Proponer y evaluar mecanismos de asignación coordinada de recursos en el interfaz radio y el backhaul. El marco tecnológico de este objetivo es 4G (LTE). 5. Abordar los objetivos anteriores dentro de la compatibilidad con las especificaciones técnicas de los protocolos implicados. Con respecto al último objetivo, consideramos que no resulta realista plantear algoritmos que impliquen un cambio en sistemas ya estandarizados y de amplio despliegue. Sin embargo, las especificaciones del 3GPP no tienen vocación de definir el funcionamiento de todos los algoritmos involucrados ya que su objetivo último es determinar claramente las interfaces para facilitar la interconexión entre dispositivos y equipos de distintos fabricantes y operadores. Los mecanismos que internamente emplean muchos protocolos para realizar ciertas tareas, en particular algoritmos de gestión de recursos o scheduling, se dejan abiertos a la implementación de los fabricantes, de forma que estos pueden diferenciarse tecnológicamente unos de otros en un entorno de competencia. Esto permite que nuevos mecanismos como los propuestos en este trabajo tengan cabida en los sistemas considerados. El objetivo principal de la Sincronización de Canal de Transporte en redes UMTS es que las tramas enviadas por la RNC lleguen a tiempo a los Nodos B para su transmisión a través del interfaz radio. Para ello, el 3GPP especifica un algoritmo conocido como Timing Adjustment que se encarga de controlar el retraso que experimentan las tramas en el interfaz Iub sumando o restando una cantidad constante. Este algoritmo reacciona con demasiada lentitud ante variaciones abruptas del retardo del interfaz Iub y, además, se puede volver inestable en escenarios de alta demora. Son situaciones que pueden estar propiciadas, entre otros motivos, por la congestión en el backhaul. Aplicando teoría de control en tiempo discreto, proponemos un nuevo mecanismo que garantiza la estabilidad en cualquier situación y mejora el rendimiento del algoritmo clásico. Las medidas de rendimiento se realizan mediante un simulador de la red UTRAN (UMTS RAN) teniendo en cuenta condiciones reales de tráfico en el interfaz Iub. Con la incorporación de HSPA en las redes UMTS la función de scheduling se ha desplazado desde la RNC hasta el Nodo B, generando la necesidad de unos buffers en el Nodo B. A su vez, esta nueva distribución de la capacidad de almacenamiento entre la RNC y el Nodo B requiere de un mecanismo de control de flujo que regule la transferencia de datos entre ambos. En esta tesis realizamos un detallado estudio analítico de este control de flujo abordándolo como un problema de optimización cuadrática. Partiendo de este análisis desarramos un nuevo algoritmo de control de flujo que consigue minimizar el retardo extremo a extremo gracias a que incorpora como parámetro la ocupación de los buffers de la RNC (además de la ocupación en el backhaul en el algoritmo de gestión de recursos radio, o scheduling. Para ello consideramos un escenario sencillo compuesto por una sola celda y una infraestructura backhaul consistente en un enlace punto-a-punto de capacidad C. Mostramos que cuando el backhaul es el cuello de botella, el rendimiento del scheduler radio con consideraciones de backhaul es claramente superior al scheduler convencional. Haciendo uso de técnicas de optimización de la utilidad de la red (NUM), abordamos de forma conjunta la gestión de recursos radio y del backhaul. Empleando descomposición dual, proponemos un mecanismo distribuido y de baja carga computacional que permite generar decisiones de asignación de recursos en el backhaul y en el interfaz radio, de forma coordinada y subtrama a subtrama. Finalmente, incorporamos en nuestro algoritmo el control _optimo de colas tandem, mejorando aun más el rendimiento respecto a los schedulers no coordinados. el Nodo B), algo que no se había considerado en algoritmos anteriores. Se trata, por tanto, de un control de flujo consciente del backhaul (backhaul-aware). Desde la implantación de LTE (4G), las tasas máximas de transmisión alcanzables en el interfaz radio se han disparado con respecto a las anteriores generaciones de sistemas móviles. Por primera vez operadores, fabricantes y comunidad académica coinciden en la necesidad de optimizar el uso los recursos del backhaul además de los recursos radio. En esta tesis estudiamos el impacto que tiene el backhaul en el algoritmo de gestión de recursos radio, o scheduling. Para ello consideramos un escenario sencillo compuesto por una sola celda y una infreastructura backhaul consistente en un enlace punto-a-punto de capacidad C. Mostramos que cuando el backhaul es el cuello de botella, el rendimiento del scheduler radio con consideraciones de backhaul es claramente superior al scheduler convencional. Haciendo uso de t_ecnicas de optimización de la utilidad de la red (NUM), abordamos de forma conjunta la gestión de recursos radio y del backhaul. Empleando descomposición dual, proponemos un mecanismo distribuido y de baja carga computacional que permite generar decisiones de asignación de recursos en el backhaul y en el interfaz radio, de forma coordinada y subtrama a subtrama. Finalmente, incorporamos en nuestro algoritmo el control _optimo de colas tandem, mejorando aun más el rendimiento respecto a los schedulers no coordinados.

[ENG] The framework of this thesis is the backhaul of radio access networks (RANs). We refer to backhaul as the infrastructure connecting the base stations of a cellular networks to either the radio network controller (RNCs) nodes or the core network nodes. In particular, this thesis addresses the issues associated to the congestion of the backhaul and the control algorithms that manage the resources of this infrastructure. The potential problems caused in the RAN by the backhaul congestion are of different nature depending on the RAN technology. We will provide a historical overview of the evolution of the RAN technologies over the last two decades, focusing on the functionalities relying on the backhaul, and how each generation imposes different and somewhat more stringent demands on the backhaul infrastructure. Along this work we focus chronologically on a specific RAN generation, starting with 3G, in particular Universal Mobile Telecommunication System (UMTS), then 3.5, High Speed Data Access (HSPA) and 4G Long Term Evolution (LTE). On each one, we study the impact of backhaul congestion on the RAN performance and propose a strategy to optimally control and manage the resources of the system. The objectives of this thesis can be formulated as follows: 1. To develop and evaluate effective control schemes to improve the performance of the transport channel synchronization functionality under backhaul congestion. The technological framework of this first objective is 3G (UMTS). 2. To develop and evaluate own control mechanisms that jointly consider the radio interface and the backhaul. The technological framework of this second objective is 3.5G (HSPA). 3. To study the impact of backhaul congestion on downlink scheduling over the radio interface. The technological framework of this second objective is 3.5G (HSPA). 4. To develop and evaluate mechanisms for coordinate resource allocation at both the radio interface and the backhaul. 5. To address previous objective with proposals that are compliant with the technical specifications of the involved protocols. With regard to this last objective, we consider that it is not fully realistic to come up with algorithms implying changes in systems that are already standardized and widely deployed. However, 3GPP standards do not pretend to define every algorithm involved, since the 3GPP's main objective is to clearly specify the interfaces to allow the interoperability between operators and deferent vendors' devices. The internal mechanisms contained in deferent layers of the protocol stack to accomplish each task are generally left open to operator or vendor choice. Especially resource management functions (such as scheduling or congestion control). This approach leverages innovation and research within the industry and the academia, and allows that mechanisms as the ones presented in this thesis be feasible within existing standardized cellular networks. The main objective of transport channel synchronization in UMTS is to make sure that the frames sent by the RNC arrive on time to the Nodes B (NBs) to be transmitted over the radio interface. For this task, the 3GPP specifies an algorithm known as timing adjustment (TA) that controls the delay suffered by the frames over the interface (Iub) connecting each NB with its corresponding RNC. The TA can add or subtract a certain quantity to the transmission delay. We show that the typical mechanism reacts too slowly in situations where the Iub delay increases abruptly, e.g. under transient congestion of the Iub. Besides, this classic algorithm shows potential instability issues in scenarios of very high delay. We address this problem using the tools of discrete-time control theory, which allows us to propose a new scheme that assures stability under any circumstances and improves the classical mechanism. The performance evaluation is carried out by means of simulation and considering realistic traffic scenarios for the Iub. With the introduction of HSPA (3.5G) in UMTS, the scheduling function was moved from the RNC to the Node B, imposing the inclusion of new data buffers at the NBs. Additionally, this redistribution of the data storage function between the RNCs and the NBs created the need of a flow control mechanism regulating the data transfers on the Iub. We model and analyze this mechanism as a quadratic optimization problem, and exploit this approach to propose a new flow control scheme that minimizes the end-to-end delay over the RAN by considering no only the situation of the NB buffer, but also of the RNC buffers. Our approach is a backhaul-aware optimal flow control system for RAN. Finally, in LTE (4G) systems, the peak transmission rates achievable by a user over the radio interface have boosted compared to previous generations. For the first time operators, vendors and the academic community agree on the need to optimize the backhaul resources, not only the radio resources. In fact, our point is that backhaul congestion impacts the performance of radio resource allocation and this function should be redesigned taking into consideration the capacity limitation of the backhaul. We use network utility maximization (NUM) techniques to address the problem of joint radio-backhaul scheduling. We use a dual decomposition approach to propose a low-complexity, distributed mechanism, that can make resource allocation decisions in a subframe basis. Finally, we incorporate the optimal control policy for tande queues in our mechanism, improving even more the performance compared to non-coordinated schedulers.