Tesis doctoral de Christopher Thraves Caro
Esta tesis estudia problemas generados en redes de colas haciendo un analisis de peor caso. Para esto se basa en un modelo de adversario llamado «adversarial queueing theory» (atq). En esta tesis se presentan tres variantes de dicho modeo, cada una enfocada al estudio de distintos problemas generados en redes de colas; problemas motivados en redes de produccion industrailes o redes de comunicacion similares a internet. Ademas se hace una contribucion directa a la version continua del modelo aqt llamado «continuous adversarial theory» (caqt). el modelo de aqt tiene como principales componentes una red, un adversario y una politica. La red esta representada por un grafo dirigido. El adversario inyecta carga en la red, represnetada por paquetes, decidiendo el momento de inyeccion , punto de inyeccion, camino que tiene que recorrer y destino de cada paquete , todo esto en el momento de la inyeccion. Cuando mas de un paquete quiere cruzar un arco al mismo tiempo, la politica actúa como criterio para determinar que paquete cruza primero, mientras que los paquetes restantes esperan en uan cola asociada al arco. Todo esto ocurre en un perido arbitrariamente largo de tiempo. para que un adversario no sobrecargue la red triviamente, este es acotado en base a la capaciada de servicio de cada arco. Como parametro de buen comportamiento para politicas y redes se define estabilidad, que de manera informal se puede entender como que es la propiedad de que el numero de paquetes que todavia no han llegado a destino este acotado por una cosntante 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 esta dada por un funcion booleana, que paraq cada proceso depende del estad de los mismos. De esta forma se da una condicion sufieciente para que dichas redes sean estables. un segundo modelo presentado, llamado «aqt with setups», modela el problema cuando el adversario puede inyectar paquetes de distintotipo, y cada arco tiene que pagar en tiempo de no trabajo cada vea que cambia elt ipo de paquete que esta sirviendo. Como primer resultado se presnetan la equiValencia entre un version general del modelo y una mas restringida, lo que permite trabajar con la ultima sin perder generalidad en ternminos de estabilidad. Ademas se caracteriza el conjunto de todas las redes estables. En terminos de politicas, se demuestra la existencia de una red y yun adversario que impiden la existencia de politicas estables. Fianlmente, se provee de una variante de fluidos que permite ocupar herramientas externas para demostrar estabiliadad. el aporte hecho a caqt es al demostracion de estabiliad para el caso en que la red es un anillo en una sola dirección. Ademas, apoyandose en el resulado ya probado de estabiliad para grafos dirigidos sin ciclos, se caracteriza todo el conjuntos 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 compuador y cada computador tiene su propio reloj, y ademas que dichos relojes no estan sincronizados necesariamente. De esta forma, politicas que usan dicho reloj para tomar su decisión pueden cambiar su funcionamiento con respecto al probado en el modelo caqt. En este marco se demuestra que cuando los relojes pueden marcar horas distintas pero la diferencia entre ellos no varia, todas las politicas que son etables cuando todos los relojes marcan la misma hora siguen siendo estables. Ademas, para el aso en que las diferencias entre los relojes puede variar pero de manera acotada, se presntan dos familias de politicas estables que basan su decision en el momento de inyeccion de cada paquete y algun aprametro del camino que tienen que recorrer. Finalmente para cuando los relojes no tienen cota para la diferencia entre ellos se presenta una nueva politica estable.
Datos académicos de la tesis doctoral «Performance of scheduling policies and networks in generalized adversarial queueing models«
- Título de la tesis: Performance of scheduling policies and networks in generalized adversarial queueing models
- Autor: Christopher Thraves Caro
- Universidad: Rey juan carlos
- Fecha de lectura de la tesis: 11/03/2008
Dirección y tribunal
- Director de la tesis
- Antonio Fernandez Anta
- Tribunal
- Presidente del tribunal: sebastií Sallent ribes
- pedro De las heras quiros (vocal)
- sancho Salcedo sanz (vocal)
- María j. Blesa aguilera (vocal)