For example this cut, let's say these two links cut ways one
and four, then this weight of cut gives you a capacity of eight,
this weight of cut gives a capacity of ten.
So, we just saw eight is smaller than ten.
So, the minimum cut is this minimum bisection in this case.
And a bisection bandwith is eight units. Now, there's also a famous, theorem
connecting the mean cut with the amount of flow you can squeeze from one node to
another. Let's say you want to squeeze a lot of
flows from the source to this destination through this graph.
Okay. For example I want to squeeze say 30,
well 30 is impossible because there are only 16 plus, 13 29 units that's
available to come out of the source. So let's say alright I want to squeeze 29
then, alright. And split 16 out of 16 go out this way,
13 out of 13 go out this way. So both links capacity at 40 utilized
Alright? Then what? The 13 arrives here, it can go out.
Okay, either part of this along this link with capacity 4 or along this length of
capacity 14 can all go along this length, for example.
Now the problem is 16 units arrive here and there's only one way to go out, that
way is the link with capacity only 12 which is smaller than 16 and so you
cannot squeeze all 16 units out of this node.
So 29 is not a flow that you can squeeze through from the source to the
destination. So now the questions is, what is the
maximum amount of flow that you can squeeze from source to destination for
this given topology and weights or capacity on the links.
Well, that is the famous maximum flow problem and there are several very famous
efficient algorithm to solve that. Now this is not a graph theory course of
whom will go through all of them. But I want to highlight one very elegant
theorem, assess the following. Well if you want to find out the maximum
flow through the network between two points,
it's the same as finding the minimum cut where the source lies on one side of the
cut, and destination on the other. So, source belongs to B1, the subside of
nodes, and destination belongs to B2, another subside of nodes.
It turns out that this shaded, configuration is the cut with the
smallest capacity. That is the min cut, okay?
You can convince this yourself, by cutting in different other ways.
In this min cut, we see that going from the V1 side to the V2 side, there are
three links of capacity 12, 7 and 1. So you add up together that is 23 units.
So the mean cut capacity for this graph, were source and destination lies on two
different sides of the cut is 23 units. So is it indeed possible to actually push
23 units from source to destination? Yes and here's one way to do it.
You put 11 on this link, 12 on this link. How do we get to this split into 11 and
12 this way. well that can be discovered by those
graph oretic algorithms that we're skipping.
But now, once you get to 11 here that's fine.
11 can all go on this way. 12 comes here.
11 will go here and one will go this way. So you all together got one plus 11, 12
units that fully utilizing those link. Okay.
This link's not used and the 11 arrives here.
You can split into 4 and 7. Now, you see why we took one unit off
this way. Because if all 12 unit gets to here, then
you won't be able to put them all to these two links.
So, it's not a surprise. In fact, a small example, you can eyeball
that indeed, you should put one out there.
And then the one together with 11 will saturate this link and the 11 will be
able to saturate these two links. And then once the seminar arrives here
with 12 as of to 19, but it can be supported out of this link unit of 20
capacity. So now finally, this destination gets two
things coming in one with 19, one with 4's all 23 units are received as they
were transmitted out of the source. So indeed as you can verify yourself,
there is no way to increase the max, the flow from source to destination.
So the maximum flow is 23 units, which is the same as the minimum cut size.
So that's a long detour of a fun and important classic result.
But in data center design when you scale out the topology, you want a large
bisection bandwidth okay. A large potential bottleneck to the
performance of communication within the data center.
The second criteria we use is called non blocking.
It originated from the circuit switching word for the telephone network.
There's something called non-blocking and something called rearrangably
non-blocking. Non-blocking says that, for whatever
traffic pattern arrives in the multi-stage network, which I'm going to
draw momentarily, as long a this input port and that output ports themselves
available, you should be able to find a way to pass
it through this multi-stage switched network.
So the connectivity pattern should be able to support that.
And rearrangeably non-blocking is a weaker condition, that says,
well, you may not be able to do that. But if I allow you to rearrange some of
the existing connectivity pattern. For example, instead of going this way,
say well, you should go this way. And this opens up a way for this input
code to this output. As long as you can rearrange existing
configuration and then be able to achieve non-blocking then that's also good okay.
So this is a weaker condition. Now what kind of switch network will have
blocking or rearrange for the non-blocking property?
Well only those that have rich enough connectivity patterns in them.
And indeed, in 1953, Clark invented a particular connectivity pattern and we're
going to see the kind of non-blocking conditions on the parameters for such
networks.
