Un Modelo de Equilibrio para Ruteo y Control de Flujo en Redes de Comunicaciones

Abstract

El modelo de maximización de utilidades de la red (NUM) caracteriza el régimen estacionario del flujo en una red de comunicaciones, mediante un problema de optimización convexa. Este modelo, propuesto por Kelly y estudiado posteriormente por Low y Mazumdar, muestra que la mayoría de los protocolos diseñados para el control de congestión en redes resuelven implícitamente una versión de NUM en régimen estacionario.

En esta memoria se estudia una nueva versión de NUM (MNUM), que combina el control de flujo y elección multirrutas, basado en un modelo de elección discreta en cada router. Para definir el equilibrio se analizan las ecuaciones en valor esperado y se muestra que ellas son la solución de un problema de optimización convexa. El problema resultante es un análogo al problema dual de NUM, donde el límite de integración es reemplazado por el costo esperado de atravesar la red bajo la asignación estocástica. Se estudian propiedades de la función de costos, la relación implícita de las variables de equilibrio en función del precio en los arcos y se finaliza con la obtención del problema primal similar a NUM con un término adicional asociado al modelo de elección discreta utilizado.

Junto con el análisis del modelo, se muestra cómo el equilibrio definido puede ser implementado modificando los actuales protocolos de internet. Para ello se define un nuevo mecanismo de notificación de la congestión, basado en el esquema de marcaje aditivo normalizado para estimar precios de las rutas. Finalmente se presenta un algoritmo de medias sucesivas que converge a la solución de MNUM, para una amplia familia de funciones de utilidad que incluye a la familia de funciones α-justas con α ≥ 1.