Enrutamiento con Compensación de Espacio de Comunicación Polinómico

Este artículo presenta una familia de esquemas de enrutamiento balanceados en memoria que utilizan rutas relativamente cortas mientras almacenan relativamente poca información de enrutamiento. La calidad de las rutas proporcionadas por un esquema se mide en términos de su estiramiento, es decir, la razón máxima entre la longitud de una ruta que conecta un par de procesadores y su distancia. Los esquemas jerárquicos Hₖ (para cada entero k ≥ 1) presentados en este artículo garantizan un factor de estiramiento de O(k²) en la longitud de las rutas y requieren almacenar como máximo O(k n^(1/k) n D) bits de información de enrutamiento por vértice en una red de n procesadores con diámetro D. Los esquemas son independientes del nombre y aplicables a redes generales con pesos de arista arbitrarios. Esto mejora diseños anteriores cuyo límite de estiramiento era exponencial en k. Los esquemas propuestos se basan en una nueva solución eficiente a un cierto problema de teoría de grafos relacionado con cubiertas de grafos dispersos. La nueva técnica de cubrimiento ya ha encontrado varias otras aplicaciones en el área de la computación distribuida.