Ancho de banda de bisección

En redes informáticas, una red puede dividirse en dos particiones de igual tamaño. El ancho de banda de bisección de una topología de red es el ancho de banda mínimo disponible entre dos particiones cualesquiera. ^{[ 1 ]} Dado un grafo${\displaystyle G}$con vértices${\displaystyle V}$bordes${\displaystyle E}$y pesos de los bordes${\displaystyle w}$, el ancho de banda de bisección de${\displaystyle G}$es

${\displaystyle BB(G)=\min _{S\subset V:|S|={\frac {1}{2}}|V|}\quad \sum _{u\in S,v\not \in S}w(u,v)}$.

En otras palabras, la red se divide en dos partes de tal manera que el ancho de banda entre las dos particiones sea mínimo. ^{[ 2 ]} Se considera que una red tiene ancho de banda de bisección completo si${\displaystyle BB(G)\geq {\frac {1}{2}}|V|}$[ ^{3 ] Intuitivamente, el ancho de banda de bisección completo significa que si todos los vértices de la red coinciden como pares origen-destino, entonces si todos los pares envían flujo a una tasa de} 1 simultáneamente, no hay cuellos de botella de bisección. Por lo tanto, el ancho de banda de bisección representa el ancho de banda del cuello de botella de la red bisecada en su conjunto.

Para una matriz lineal con n nodos, el ancho de banda de bisección es igual al ancho de banda de un enlace. Para una matriz lineal, basta con interrumpir un enlace para dividir la red en dos particiones.

Para una topología de anillo con n nodos, se deben romper dos enlaces para dividir la red, por lo que el ancho de banda de la división se convierte en el ancho de banda de dos enlaces.

Para una topología de árbol con n nodos, se puede dividir por la raíz rompiendo un enlace, por lo que el ancho de banda de la bisección es el ancho de banda de un enlace.

Para topología de malla con n nodos,${\displaystyle {\sqrt {n}}}$Los enlaces deben romperse para bisecar la red, por lo que el ancho de banda de bisección es el ancho de banda de ${\displaystyle {\sqrt {n}}}$campo de golf.

Para una topología de hipercubo con n nodos, se deben romper n/2 enlaces para dividir la red por la mitad, por lo que el ancho de banda de la bisección es el ancho de banda de n/2 enlaces.

^{[ 2 ]}

El apoyo teórico a la importancia de esta medida de rendimiento de la red fue desarrollado en la investigación doctoral de Clark Thomborson (anteriormente Clark Thompson) . ^{[ 4 ]} Thomborson demostró que los algoritmos importantes para la ordenación, la transformada rápida de Fourier y la multiplicación de matrices se vuelven limitados por la comunicación —en lugar de limitados por la CPU o la memoria— en computadoras con ancho de banda de bisección insuficiente. La investigación doctoral de F. Thomson Leighton ^{[ 5 ]} ajustó el límite impreciso de Thomborson ^{[ 6 ]} sobre el ancho de banda de bisección de una variante computacionalmente importante del grafo de De Bruijn conocida como la red de intercambio de mezcla . Basándose en el análisis de Bill Dally sobre la latencia, el rendimiento promedio y el rendimiento de los puntos críticos de las redes m-arias n-cubo ^{[ 2 ]} para varios valores de m, se puede observar que las redes de baja dimensión, en comparación con las redes de alta dimensión (por ejemplo, n-cubos binarios) con el mismo ancho de banda de bisección (por ejemplo, toros ), tienen una latencia reducida y un mayor rendimiento de los puntos críticos. ^{[ 7 ]}

Cabe señalar que también existe evidencia que respalda la idea de que el ancho de banda de bisección y el rendimiento de la red son métricas asintóticamente diferentes, que pueden crecer a ritmos distintos según la topología de la red. ^{[ 3 ] [ 8 ]}