Performance of Scheduling Policies and Networks in Generalizad Adversarial Queueing Models

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.