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.