Estudio del algoritmo de asignacion jerárquica paralela para conmutadores con colas virtuales a la salida

Resum

A lo largo de este trabajo de tesis, hemos presentado distintos algoritmos de planificación para conmutadores de altas prestaciones. Nuestro trabajo se ha centrado especialmente en conmutadores con colas virtuales a la salida y matrices de conmutación crossbar, puesto que esta arquitectura se ha impuesto como la más ventajosa en las implementaciones comerciales. Las dos principales contribuciones de este trabajo son la presentación y descripción del algoritmo AJP y la extensión y generalización de la arquitectura Birkhoffvon Neumann con equilibrado de carga. El algoritmo de planificación AJP pertenece a la clase de algoritmos de asignación de tamaño maximal o msm. Esta clase se caracteriza por una serie de cualidades deseables, tales como caudal elevado, bajo retardo, rapidez y sencillez de implementación. A su vez, los algoritmos msm se pueden clasificar en algoritmos AJS y algoritmos de asignacióniterativa. El algoritmo AJP presentado en esta tesis combina las ventajas de estas dos familias: por un lado, admite implementaciones hardware muy sencillas y, en consecuencia, tiempos de iteración bajos frente a los algoritmos de asignación iterativa. Por otro lado, se reduce el número de iteraciones necesarias frente a los algoritmos secuenciales, lo que redunda en una mayor escalabilidad. Estas ventajas convierten a AJP en un excelente candidato para los conmutadores de altas prestaciones,tanto en la red troncal -donde prima la rapidez- como en la red de acceso -donde prima la escalabilidad. AJP es un algoritmo "justo" (los dos primeros momentos de la distribución del intervalo entre dos servicios consecutivos de una cola no vacía se pueden acotar), se puede adaptar fácilmente para gestionar tráfico con distintas prioridades (subdividiendo cadaVOQ en prioridades) y es capaz de alcanzar un caudal del 100% en una única iteración en condiciones de saturación.