<< Volver atrás

Tesis:

Fairness and proactive congestion control in multipath networks

  • Autor: LUDEÑA GONZÁLEZ, Patricia

  • Título: Fairness and proactive congestion control in multipath networks

  • Fecha: 2022

  • Materia: Sin materia definida

  • Escuela: E.T.S.I. Y SISTEMAS DE TELECOMUNICACIÓN

  • Departamentos: INGENIERIA TELEMATICA Y ELECTRONICA

  • Acceso electrónico: https://oa.upm.es/70176/

  • Director/a 1º: LÓPEZ-PRESA, José Luis
  • Director/a 2º: TORRES TANDAZO, Rommel Vicente

  • Resumen: Los protocolos tradicionales de control de congestión suelen ser ineficaces para las redes de alta velocidad porque no pueden utilizar por completo la capacidad disponible. Además, las conexiones deben poder utilizar múltiples rutas para enrutar sus paquetes a fin de aprovechar al máximo la infraestructura de red disponible. Para las redes tradicionales de un solo camino, existen protocolos efectivos para lograr max-min fairness (MMF) y prevenir eficazmente la congestión a través de técnicas explícitas de control de velocidad. Sin embargo, para las redes multitrayecto, el problema es mucho más complejo y las soluciones actuales para asignar tasas de MMF necesitan resolver una serie de problemas de programación lineal (LP), con un alto costo computacional. Por lo tanto, se ha propuesto una relajación de MMF, a saber, upward max-min fairness (UMMF) que puede resolverse mediante algoritmos combinatorios simples. Las propuestas actuales realizan aproximaciones incrementales emulando el algoritmo de llenado de agua (waterfilling), que establece inherentemente una dependencia entre el tiempo requerido para lograr la solución óptima y la capacidad de los enlaces. Por tanto, cuanta más capacidad tenga la red, menos eficientes serán los algoritmos. En este trabajo se definió el concepto de nivel de saturación de un enlace, como base para el cómputo de las tasas equitativas. Luego, se desarrolló el primer algoritmo centralizado basado en este concepto, llamado c-SLEN, para asignar tasas UMMF en una red multitrayecto. A diferencia de sus predecesores, su tiempo de convergencia es independiente de la capacidad de la red y evita proactivamente la sobresaturación del enlace. Basado en c-SLEN, se derivó un protocolo distribuido, llamado d-SLEN. Este protocolo no necesita mantener información por flujo en los enrutadores y garantiza un tiempo de procesamiento constante para los paquetes de control, lo que lo convierte en un buen candidato para el uso práctico. La evaluación del desempeño por simulación de c-SLEN comparándolo con el algoritmo centralizado IEWF mostró la mejora del desempeño como consecuencia de la aplicación del concepto de nivel de saturación. Este algoritmo exhibe una convergencia mucho más rápida a las tasas de UMMF que su predecesor IEWF. Finalmente, a través de extensas simulaciones, se demostró que d-SLEN produce una mejora notable sobre los protocolos encontrados en la literatura. Converge casi de inmediato a tasas estables y se puede utilizar en un entorno dinámico donde las conexiones llegan y salen de la red en cualquier momento. Es capaz de mantener el tamaño de las colas de enlace en valores mínimos en todo momento, evitando así de manera proactiva la congestión de la red. ----------ABSTRACT---------- Traditional congestion control protocols are usually ineffective to high-speed networks because they are not able to fully utilize available capacity. Furthermore, connections need to be able to use multiple paths to route their packets in order to take full advantage of the available network infrastructure. For traditional singlepath networks, there are effective protocols to achieve max-min fairness (MMF) and effectively preventing congestion through explicit rate control techniques. However, for multipath networks, the problem is much more complex and current solutions to allocate MMF rates need to solve a series of linear programming (LP)problems, with high computational cost. Thus, a relaxation of MMF has been proposed, namely upward max-min fairness (UMMF) which can be solved by simple combinatorial algorithms. Current proposals carry out incremental approximations emulating the waterfilling algorithm, which inherently establishes a dependency between the time required to achieve the optimal solution and the capacity of the links. Thus, the more capacity the network has, the less efficient the algorithms are. In this work, the concept of saturation level of a link was defined, as the basis for the computation of fair shares. Then, the first centralized algorithm based on this concept, named c-SLEN, was developed to allocate UMMF rates in a multipath network. Unlike its predecessors, its convergence time is independent of network capacity and proactively prevents link oversaturation. Based on c-SLEN, a distributed protocol was derived, named d-SLEN. It does not need to maintain per-flow information on routers and guarantees constant processing time for control packets, making it a good candidate for practical use. The performance evaluation by simulation of c-SLEN comparing it with the centralized IEWF algorithm showed the performance improvement as a consequence of the application of the saturation level concept. This algorithm exhibits a much faster convergence to UMMF rates than its predecessor IEWF. Finally, through extensive simulations, it was shown that d-SLEN produces a remarkable improvement over state-of-the-art protocols. It converges almost immediately to stable rates and can be used in a dynamic environment where connections arrive and leave the network at any time. It is able to maintain the size of link queues at minimal values at all times, thus proactively avoiding network congestion.