Ancho de bisección - Enciclopedia

En la red de computadoras, una red puede dividirse en dos particiones de igual tamaño. La banda de división de una topología de red es la banda mínima disponible entre cualquier dos de tales particiones. Dado un grafo


G


{\displaystyle G}

con vértices

V


{\displaystyle V}

, aristas

E


{\displaystyle E}

, y pesos de aristas

w


{\displaystyle w}

, la banda de división de

G


{\displaystyle G}

es



B
B
(
G
)
=

min

S
⊂
V
:

|

S

|

=


1
2



|

V

|





∑

u
∈
S
,
v
∉
S


w
(
u
,
v
)


{\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 de manera que la banda entre las dos particiones sea mínima. Una red se considera que tiene una banda de división completa si



B
B
(
G
)
≥


1
2



|

V

|



{\displaystyle BB(G)\geq {\frac {1}{2}}|V|}

. Intuitivamente, la banda de división completa significa que si todos los vértices de la red se emparejan como pares fuente-destino, entonces si todos los pares envían flujo a una velocidad de 1 simultáneamente, no hay atascos de división. Por lo tanto, la banda de división tiene en cuenta la banda de atasco de la red dividida en su conjunto.


Cálculos de banda de división

Para una matriz lineal con n nodos, la banda de división es la banda de un enlace. En una matriz lineal solo se necesita romper un enlace para dividir la red en dos particiones.

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

Para una topología en árbol con n nodos, puede dividirse en la raíz rompiendo un enlace, por lo que la banda de división es la banda de un enlace.

Para una topología en malla con n nodos, se deben romper




n




{\displaystyle {\sqrt {n}}}

enlaces para dividir la red, por lo que la banda de división es la banda de




n




{\displaystyle {\sqrt {n}}}

enlaces.

Para una topología de hipercubo con n nodos, se deben romper




n




{\displaystyle \frac{n}{2}}

enlaces para dividir la red, por lo que la banda de división es la banda de




n




{\displaystyle \frac{n}{2}}

enlaces.


Significación de la banda de división

El apoyo teórico para la importancia de esta medida de rendimiento de la red se desarrolló en la investigación doctoral de Clark Thomborson (antes conocido como Clark Thompson). Thomborson demostró que algoritmos importantes para el ordenamiento, la transformada rápida de Fourier y la multiplicación de matrices por matrices se vuelven limitados por comunicación, en lugar de limitados por CPU o memoria, en computadoras con una banda de división insuficiente. La investigación doctoral de F. Thomson Leighton reflejó la bound suelta de Thomborson sobre la banda de división de una variante computacionalmente importante del grafo de De Bruijn conocida como la red de desplazamiento y cambio. Basado en el análisis de latencia, el rendimiento promedio y el rendimiento en puntos calientes de redes de n-cubo m-arias para varios m, se puede observar que las redes de baja dimensión, en comparación con redes de alta dimensión (por ejemplo, n-cubos binarios) con la misma banda de división (por ejemplo, toros), tienen menor latencia y un rendimiento en puntos calientes más alto.
Nota: también hay apoyo que la banda de división y el rendimiento de la red son métricas diferentes en términos asintóticos, que pueden crecer a diferentes tasas dependiendo de la topología de la red.


Referencias