| Abstract | dc.description.abstract | Esta tesis estudia problemas generados en redes de colas haciendo un an´alisis de
peor caso. Para esto se basa en un modelo de adversario llamado Adversarial Queueing
Theory (AQT). En esta tesis se presentan tres variantes de dicho modelo, cada una
enfocada al estudio de distintos problemas generados en redes de colas; problemas
motivados en redes de producci´on industriales o redes de comunicaci´on similares a
Internet. Adem´as se hace una contribuci´on directa a la versi´on continua del modelo
AQT llamado Continuous Adversarial Queueing Theory (CAQT).
El modelo de AQT tiene como principales componentes una red, un adversario y
una pol´ıtica. La red est´a representada por un grafo dirigido. El adversario inyecta
carga en la red, representada por paquetes, decidiendo el momento de inyecci´on,
punto de inyecci´on, camino que tiene que recorrer y destino de cada paquete, todo
esto en el momento de la inyecci´on. Cuando m´as de un paquete quiere cruzar un
arco al mismo, tiempo la pol´ıtica act´ua como criterio para determinar qu´e paquete
cruza primero, mientras que los paquetes restantes esperan en una cola asociada al
arco. Todo esto ocurre en un periodo arbitrariamente largo de tiempo. Para que el
adversario no sobrecargue la red trivialmente, ´este es acotado en base a la capacidad
de servicio de cada arco. Como par´ametro de buen comportamiento para pol´ıticas y
redes se define estabilidad, que de manera informal se puede entender como que es
la propiedad de que el n´umero de paquetes que todava no han llegado a destino est´e
acotado por una constante que no depende del tiempo.
En el primer modelo presentado se analizan redes de colas generadas en servidores.
En este modelo el adversario inyecta tareas representadas por un conjunto de procesos,
y en donde la dependencia entre todos los procesos de cada tarea est´a dada por una funci´on Booleana, que para cada proceso que depende del estado de los mismos.
De esta forma se da una condici´on suficiente para que dichas redes sean estables.
Un segundo modelo presentado, llamado AQT with setups, modela el problema
cuando el adversario puede inyectar paquetes de distinto tipo, y cada arco tiene que
pagar en tiempo de no trabajo cada vez que cambia el tipo de paquete que est´a
sirviendo. Como primer resultado se presentan la equivalencia entre una versi´on general
del modelo y una m´as restringida, lo que permite trabajar con la ´ultima sin perder
generalidad en t´erminos de estabilidad. Adem´as se caracteriza el conjunto de todas
las redes estables. En t´erminos de pol´ıticas, se demuestra la existencia de una red y
un adversario que impiden la existencia de pol´ıticas estables. Finalmente, se provee
de una variante de fluidos que permite ocupar herramientas externas para demostrar
estabilidad.
El aporte hecho a CAQT es la demostraci´on de estabilidad para el caso en que la red
es un anillo en una sola direcci´on. Adem´as, apoy´andose en el resultado ya probado
de estabilidad para grafos dirigidos sin ciclos, se caracteriza todo el conjunto de redes
estables.
El ´ultimo modelo presentado, llamado NSCAQT, asume que cada cola tiene un
reloj, hecho muy natural si se piensa que cada nodo es un computador y cada computador
tiene su propio reloj, y adem´as que dichos relojes no est´an sincronizados
necesariamente. De est´a forma, pol´ıticas que usan dicho reloj para tomar su decisi´on
pueden cambiar su funcionamiento con respecto al probado en el modelo de CAQT.
En este marco se demuestra que cuando los relojes pueden marcar horas distintas pero
la diferencia entre ellos no var´ıa, todas las pol´ıticas que son estables cuando todos los
relojes marcan la misma hora siguen siendo estables. Adem´as, para el caso en que las
diferencias entre los relojes puede variar pero de manera acotada, se presentan dos
familias de pol´ıticas estables que basan su decisi´on en el momento de inyecci´on de
cada paquete y alg´un par´ametro del camino que tienen que recorrer. Finalmente para
cuando los relojes no tienen cota para la diferencia entre ellos se presenta una nueva
pol´ıtica estable. | |
