Previous | Next --- Slide 18 of 51
Back to Lecture Thumbnails

Why is the bisection bandwidth in the first network (on the previous slide) O(n)?


I don't really understand the intuition behind bisection bandwidth. Where are we cutting the network to measure the severed links? And how does that indicate the overall bandwidth of the network if we only cut the links in a specific place?


Let's say we have two machines in a network - we want to measure the bandwidth between them. Imagine a "cut" in the network, which is a partition into two connected subgraphs such that one machine is in each. The bandwidth is the number of connections spanning from one subgraph to the other.

According to the max-flow min-cut theorem, the cut with minimum bandwidth limits the flow between our two machines - the bandwidth of that cut is precisely the maximum flow possible. So a network with O(n) cut bandwidth would be able to simultaneously send O(n) data between two machines.

Forcing the cut to be a bisection provides a sort of generalization to any two points rather than two specific ones, think of it like an "average" maximum flow.


Correct me if I'm wrong -- "misleading" in this case refers to the fact that bandwidth bisection only tells part of the story. For example, we may have chosen to arrange routers and links to reflect the fact that certain nodes will be expected to communicate more than other pairs.


I found a more concrete definition of "Bisection Bandwidth", that is " A bisection of a network is a partition into two equally-sized sets of nodes. The sum of the capacities of links between the two partitions is called the bandwidth of the bisection. The bisection bandwidth of a network is the minimum such bandwidth along all possible bisections. Therefore, bisection bandwidth can be thought of as a measure of worst-case network capacity. " So the bisection bandwidth of networks in the precious slide is 8.


@xiaoguaz Ah, thanks for that clarification. Given what you said, I think the "warning" mentioned above refers to the fact that the links in a bisection bandwidth basically assume a bandwidth of value 1 (in other words, you just count the number of links cut). In reality, various models of routers and transmission media can result in very different transmission/bandwidth rates, so the warning above seems to refer to the simplifying assumption made in the bandwidth bisection that each link has equal bandwidth (or that different non-optimal routes may need to be taken in certain scenarios).


I think the "Warning" mentioned in the slide is more relevant to the overhead of routing instead of the difference of bandwidth between links.

For example, in a typical max-flow-min-cut scenario, we are already considering a weighted graph (in the network case, the links have different bandwidths). And, we usually just consider the sum up the weights of the crossing links.

However, in our case, the nodes in the graph (in the network case, it's the switches / routers) have associated latencies. For example, in our network we may use a router that incurs 5-second latency for all package-forwardings. Also, our router may not use the "optimal" way to forward the packages to the destination. I believe this is what the "Warning" is about.


Thanks to previous comments, I understand the bisection bandwidth of direct network to be O(n). But why is it O(n/2) for the indirect network of previous slides? Should I be counting the number of interconnect links?


@KnightsLanding: Yes, the bisection bandwidth refers to the worst case when we partition equally.

Since only ONE package can go across a node to another node at any given time, then in the indirect network pictured in the last slide, at most n/2 packages can be sent across the divide.


@blairwaldorf Thank you!

So it's different case then in the next slide where the n nodes connects to themselves through the network?


Bisection bandwidth measures the bottleneck of the network.


@blairwaldorf I think the bisection bandwidth is still N for the multi stage log network in the previous slide. Because we can make a vertical cut in the middle and there will be N links connecting the divided parts. It is correct that only N/2 packages could be sent across, but that is the measurement of maximum throughput utilization of the network, instead of the throughout of the network, which is a property regardless of the load pattern