Topologías de Red Estáticas y Métricas de Rendimiento en Sistemas de Interconexión

Conceptos Fundamentales

Throughput: Es la capacidad de tráfico que una red es capaz de absorber por unidad de tiempo.

Topologías Estáticas

Array Lineal (Bilateral)

Consiste en una serie de nodos conectados en serie mediante enlaces punto a punto.

• Grado (G): 2 (1 en los extremos, 2 en el resto).
• Diámetro (D): N - 1.
• Coste (C): N - 1.
• Ancho de Bisección (B): 1.

Anillo

Es una evolución del array lineal en el que se conecta el primer nodo con el último.

• Grado (G): 2.
• Diámetro (D): N - 1.
• Coste (C): N.
• Ancho de Bisección (B): 2.

Barrel Shifter de 8 nodos

Cada nodo está conectado con todos aquellos que estén a una distancia potencia de 2.

• Grado (G): 2n - 1.
• Diámetro (D): 2.
• Coste (C): N/2 + N(n - 1).
• Nodos (N): 2ⁿ.
• Ancho de Bisección (B): N - 2 + N/2.

Árbol

Presenta una mala bisección, ya que produce un cuello de botella en el nodo raíz. A su vez, provoca problemas de interconexión en caso de fallo de un nodo.

• Grado (G): 3.
• Diámetro (D): 2(n - 1).
• Coste (C): N - 1.
• Nodos (N): 2ⁿ - 1.
• Ancho de Bisección (B): 1.

Árbol Grueso (Fat Tree)

Mantiene el ancho de banda constante aumentando el ancho de banda disponible en los nodos cercanos a la raíz. Mejora, por lo tanto, la bisección.

• Grado (G): 2n - 1.
• Diámetro (D): 2(n - 1).
• Coste (C): (n - 1) * 2^n-1.
• Nodos (N): 2ⁿ - 1.
• Ancho de Bisección (B): G / 2.

Estrella

Posee el mínimo grado posible. Presenta problemas de conectividad extremos: si falla el nodo central, fallan todos.

• Grado (G): 1.
• Diámetro (D): 2.
• Coste (C): N - 1.
• Ancho de Bisección (B): 1.

Malla (Mesh)

Nodos unidos en forma matricial. Utiliza un algoritmo de encaminamiento DOR (Dimension-Ordered Routing) que impide los abrazos mortales (deadlocks). Además, es posible la existencia de particiones. (Cálculos basados en una malla cuadrada):

• Grado (G): 2n.
• Diámetro (D): n(d - 1).
• Coste (C): n * d(n - 1)(d - 1).
• Nodos (N): dⁿ.
• Ancho de Bisección (B): d^n-1.

Toro (Torus)

Caso especial de malla al que se le añade un enlace más por dimensión. Solo se aprovecha esta arquitectura en máquinas que utilicen todos los nodos para un mismo trabajo.

• Grado (G): 2n.
• Diámetro (D): n(d / 2).
• Coste (C): 2dn.
• Nodos (N): dⁿ.
• Ancho de Bisección (B): 2d^n-1.

Malla Iliac

Los enlaces periféricos no se unen con los extremos, sino con la fila siguiente. Es topológicamente igual al toro, pero permite pasar por todos los nodos en una sola pasada (ideal para broadcast).

Hipercubo

• Grado (G): n.
• Diámetro (D): n.
• Coste (C): n * 2^n-1.
• Nodos (N): 2ⁿ.
• Ancho de Bisección (B): 2^n-1.

CCC (Cubos Conectados en Ciclos)

Hipercubos cuyos vértices han sido convertidos en anillos de tantos nodos como dimensiones.

• Grado (G): 3.
• Diámetro (D): 2n.
• Coste (C): 3n * 2^n-1.
• Nodos (N): n * 2ⁿ.
• Ancho de Bisección (B): 2^n-1.

Toro de n dimensiones (Conexiones n-cubo k-arias)

• Grado (G): 2n.
• Diámetro (D): n * (k / 2).
• Coste (C): 2kn.
• Nodos (N): kⁿ.
• Ancho de Bisección (B): 2 * k^n-1.