Bisection bandwidth

In computer networking, a network may be bisected into two equal-sized partitions. The bisection bandwidth of a network topology is the minimum bandwidth available between any two such partitions.^[1] Given a graph ${\displaystyle G}$ with vertices ${\displaystyle V}$, edges ${\displaystyle E}$, and edge weights ${\displaystyle w}$, the bisection bandwidth of ${\displaystyle G}$ is

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

In other words, the network is bisected s in such a way that the bandwidth between the two partitions is minimum.^[2] A network is considered to have full bisection bandwidth if ${\displaystyle BB(G)\geq {\frac {1}{2}}|V|}$.^[3] Intuitively, full bisection bandwidth means that if all vertices in the network are matched as source-destination pairs, then if all pairs send flow at rate 1 simultaneously, there are no bisection bottlenecks. Therefore, bisection bandwidth accounts for the bottleneck bandwidth of the bisected network as a whole.

For a linear array with n nodes bisection bandwidth is one link bandwidth. For linear array only one link needs to be broken to bisect the network into two partitions.

For ring topology with n nodes two links should be broken to bisect the network, so bisection bandwidth becomes bandwidth of two links.

For tree topology with n nodes can be bisected at the root by breaking one link, so bisection bandwidth is one link bandwidth.

For Mesh topology with n nodes, ${\displaystyle {\sqrt {n}}}$ links should be broken to bisect the network, so bisection bandwidth is bandwidth of ${\displaystyle {\sqrt {n}}}$ links.

For Hyper-cube topology with n nodes, n/2 links should be broken to bisect the network, so bisection bandwidth is bandwidth of n/2 links.

^[2]

Theoretical support for the importance of this measure of network performance was developed in the PhD research of Clark Thomborson (formerly Clark Thompson).^[4] Thomborson proved that important algorithms for sorting, Fast Fourier transformation, and matrix-matrix multiplication become communication-limited—as opposed to CPU-limited or memory-limited—on computers with insufficient bisection bandwidth. F. Thomson Leighton's PhD research^[5] tightened Thomborson's loose bound ^[6] on the bisection bandwidth of a computationally-important variant of the De Bruijn graph known as the shuffle-exchange network. Based on Bill Dally's analysis of latency, average-case throughput, and hot-spot throughput of m-ary n-cube networks^[2] for various m, it can be observed that low-dimensional networks, in comparison to high-dimensional networks (e.g., binary n-cubes) with the same bisection bandwidth (e.g., tori), have reduced latency and higher hot-spot throughput.^[7]

Note, there is also support that bisection bandwidth and network throughput are asymptotically different metrics, which may grow at different rates depending on the network topology. ^[3][8]

This computer networking article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e