Bisection bandwidth

In computer networking, a network may be <a href="/facts/Bisection/JTsya7Ca">bisected</a> into two equal-sized partitions. The bisection bandwidth of a <a href="/facts/Network_topology/rBYE0kke">network topology</a> is the minimum bandwidth available between any two such partitions. Given a graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
 with vertices 
 
 
 
 V
 
 
 {\displaystyle V}
 
, edges 
 
 
 
 E
 
 
 {\displaystyle E}
 
, and edge weights 
 
 
 
 w
 
 
 {\displaystyle w}
 
, the bisection bandwidth of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is

 
 
 
 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)}
 
.
In other words, the network is bisected s in such a way that the <a href="/facts/Bandwidth_(computing)/lY6Tb4gX">bandwidth</a> between the two partitions is minimum. A network is considered to have full bisection bandwidth if 
 
 
 
 B
 B
 (
 G
 )
 ≥
 
 
 1
 2
 
 
 
 |
 
 V
 
 |
 
 
 
 {\displaystyle BB(G)\geq {\frac {1}{2}}|V|}
 
. 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.

Bisection bandwidth open-in-new

Bisection bandwidth