New queuing schemes to improve the efficiency of hybrid and hierarchical high-performance interconnection network topologies
Pedro Yébenes · Dialnet (Universidad de la Rioja) · 2018
Actualmente muchas aplicaciones requieren una capacidad de computacion y/o almacenamiento que no puede ser satisfecha con solo ordenador, asi que tienen que ejecutarse en super computadores o en centros de datos. Estos sistemas sea interconectan mediante una red que debe cumplir los requisitos de comunicacion de esas aplicaciones para no ser el cuello de botella del sistema. Hay muchos factores que impactan en el rendimiento general de una red. La topologia de red, que define el patron de interconexion, es una de las mas importantes ya que otros factores dependen de ella, como el algoritmo de encaminamiento. En la ultima decada, se han propuesto nuevas topologias para aprovechar los nuevos conmutadores con muchos puertos que han aparecido en el mercado, asi como reducir los inconvenientes de las tradicionales topologias directas e indirectas. En este sentido, las propuestas mas destacas son las topologias KNS, Dragonfly, y Slim Fly, en las cuales se centra esta tesis. Aunque estas topologias ofrecen unas buenas propiedades, la congestion y sus efectos negativos derivados pueden perjudicar el rendimiento de la red. Especificamente, el peor de estos efectos derivados es el bloqueo de la cabeza de la cola, el cual aparece cuando el paquete en la cabeza de una cola se bloquea y previene el avance de otros paquetes almacenados detras suya, incluso si estos solicitan recursos que no estan en uso. Para combatir este problema se han propuesto tecnicas que se conocen como esquemas de colas. Muchas de ellas no consideran ni la topologia ni el algoritmo de encaminamiento, mientras que otras lo hacen, las cuales han sido descritas como mas eficientes, es decir, utilizan menos recursos de red y/o logran una mayor mejor en el rendimiento de la red. Has donde sabemos, no hay ningun esquema de colas que haya sido disenado especificamente para las topologias KNS, Dragonfly o Slim Fly. Por este motivo, en esta tesis proponemos varios esquemas de colas que las tienen en cuenta, asi como sus algoritmos de encaminamiento minimos. Ademas, en el caso de las topologias Dragonfly y Slim Fly, nuestras propuestas consideran el problema de los interbloqueos, ya que sus algoritmos de encaminamiento minimos necesitan rutas de escape para evitarlo. En la mayoria de los sistemas coexisten aplicaciones con diferentes niveles de prioridad, cada una con distintos requisitos de latencia o de ancho de banda. Sin embargo, las tecnicas de calidad de servicio que abordan este problema normalmente usan colas, al igual que los esquemas de colas. Para combinar estos enfoques, proponemos en esta tesis un mecanismo que es capaz de implementar esquemas de colas mientras que ofrece servicios diferenciados. En el caso de las topologias Dragonfly y Slim Fly, proponemos dos variaciones de los mecanismos previos para que tambien eviten los interbloqueos. Las topologias Dragonfly y Slim Fly presentan algunos casos de trafico, conocidos como trafico adversario, que sobre utilizan algunos caminos de la red, lo que conlleva a una perdida de rendimiento. Para evitar estas situaciones, se utilizan los algoritmos de encaminamiento no minimo, aunque se requieren caminos de escape adicionales para evitar los interbloqueos. Tambien proponemos en esta tesis una extension de los esquemas de colas disenados para encaminamiento minimo para estas topologias para que se ajusten al encaminamiento no minimo. Ademas, proponemos una mejora para los algoritmos de encaminamiento no minimos utilizados en la topologia Slim Fly para eliminar alguno de sus inconvenientes mientras incrementamos su rendimiento y/o reducimos el numero de caminos de escape necesarios para evitar interbloqueos.