000012579 001__ 12579 000012579 005__ 20190219123646.0 000012579 037__ $$aTESIS-2013-120 000012579 041__ $$aeng 000012579 080__ $$a004 000012579 1001_ $$aCelaya Alastrué, Javier 000012579 24500 $$aSTaRS$$bA scalable task routing approach to distributed scheduling 000012579 260__ $$aZaragoza$$bUniversidad de Zaragoza, Prensas de la Universidad$$c2013 000012579 300__ $$a123 000012579 4900_ $$aTesis de la Universidad de Zaragoza$$v2013-101$$x2254-7606 000012579 500__ $$aPresentado: 06 09 2013 000012579 502__ $$aTesis-Univ. Zaragoza, Informática e Ingeniería de Sistemas, 2013$$bZaragoza, Universidad de Zaragoza$$c2013 000012579 506__ $$aby-nc-nd$$bCreative Commons$$c3.0$$uhttps://creativecommons.org/licenses/by-nc-nd/3.0/ 000012579 520__ $$aLa planificación de muchas tareas en entornos de millones de nodos no confiables representa un gran reto. Las plataformas de computación más conocidas normalmente confían en poder gestionar en un elemento centralizado todo el estado tanto de los nodos como de las aplicaciones. Esto limita su escalabilidad y capacidad para tolerar fallos. Un modelo descentralizado puede superar estos problemas pero, por lo que sabemos, ninguna solución propuesta hasta el momento ofrece resultados satisfactorios. En esta tesis, presentamos un modelo de planificación descentralizado con tres objetivos: que escale hasta millones de nodos, sin una pérdida de prestaciones que lo inhabilite; que tolere altas tasas de fallos; y que permita la implementación de varias políticas de planificación para diferentes situaciones. Nuestra propuesta consta de tres elementos principales: un modelo de datos genérico para representar la disponibilidad de los nodos de ejecución; un esquema de agregación que propaga esta información por una capa de red jerárquica; y un algoritmo de reexpedición que, usando la información agregada, encamina tareas hacia los nodos de ejecución más apropiados. Estos tres elementos son fácilmente extensibles para proporcionar diversas políticas de planificación. En concreto, nosotros hemos implementado cinco. Una política que simplemente asigna tareas a nodos desocupados; una política que minimiza el tiempo de finalización del trabajo global; una política que cumple con los requerimientos de fecha límite de aplicaciones tipo "saco de tareas"; una política que cumple con los requerimientos de fecha límite de aplicaciones tipo "workflow"; y una política que otorga una porción equitativa de la plataforma a cada aplicación. La escalabilidad se consigue a través del esquema de agregación, que provee de suficiente información de disponibilidad a los niveles altos de la jerarquía sin inundarlos, y el algoritmo de reexpedición, que busca nodos de ejecución en varias ramas de la jerarquía de manera concurrente. Como consecuencia, los costes de comunicación están acotados y los de asignación muestran un comportamiento casi logarítmico con el tamaño del sistema. Un millar de tareas se asignan en una red de 100.000 nodos en menos de 3,5 segundos, así que podemos plantearnos utilizar nuestro modelo incluso con tareas de tan solo unos minutos de duración. Por lo que sabemos, ningún trabajo similar ha sido probado con más de 10.000 nodos. Los fallos se gestionan con una estrategia de mejor esfuerzo. Cuando se detecta el fallo de un nodo, las tareas que estaba ejecutando son reenviadas por sus propietarios y la información de disponibilidad que gestionaba es reconstruida por sus vecinos. De esta manera, nuestro modelo es capaz de degradar sus prestaciones de manera proporcional al número de nodos fallidos y recuperar toda su funcionalidad. Para demostrarlo, hemos realizado pruebas de tasa media de fallos y de fallos catastróficos. Incluso con nodos fallando con un periodo mediano de solo 5 minutos, nuestro planificador es capaz de continuar dando servicio. Al mismo tiempo, es capaz de recuperarse del fallo de una fracción importante de los nodos, siempre que la capa de red jerárquico que sustenta el sistema pueda soportarlo. Después de comprobar que es factible implementar políticas con muy distintos objetivos usando nuestro modelo de planificación, también hemos probado sus prestaciones. Hemos comparado cada política con una versión centralizada que tiene pleno conocimiento del estado de cada nodo de ejecución. El resultado es que tienen unas prestaciones cercanas a las de una implementación centralizada, incluso en entornos de gran escala y con altas tasas de fallo. 000012579 6531_ $$aarquitectura de ordenadores 000012579 6531_ $$aredes de ordenadores 000012579 6531_ $$asimulación 000012579 6531_ $$acomputer architecture 000012579 6531_ $$acomputer networks 000012579 6531_ $$asimulation 000012579 700__ $$aArronategui Arribalzaga, Unai$$edir. 000012579 7102_ $$aUniversidad de Zaragoza$$bInformática e Ingeniería de Sistemas 000012579 8560_ $$fzaguan@unizar.es 000012579 8564_ $$s2611669$$uhttps://zaguan.unizar.es/record/12579/files/TESIS-2013-120.pdf$$zTexto completo (eng) 000012579 909CO $$ooai:zaguan.unizar.es:12579 000012579 909co $$ptesis 000012579 909CO $$pdriver 000012579 9102_ $$aArquitectura y tecn. Computadoras$$bInformática e Ingeniería de Sistemas 000012579 980__ $$aTESIS