That's the tree, Okay?

There is only one way to go from the root node to any of the leaf nodes, and there's

no cycle, where's for. In fact just look at this graph you see

that hey since node a is the parent of nodes b and d so the upload capacity of

node a is utilized. Seems node b has a child.

It's upload capacity will also be utilized.

But what about nodes c and d? They are the leaf nodes and therefore are

only on the receiving end and their upload capacities are entirely wasted.

So, C, D upload capacity are wasted. And, clearly, we wouldn't be able to

achieve this bound. Well, what if we use another tree?

In this case, the root will go to c first, and c go to d and then d go to a and b.

This is another tree. In this case AB's upload capacities are

not used. Their upload capacities are wasted.

That's not good either. So whichever tree you pick, you're going

to waste somebody's upload capacity. But wait a minute.

What if I use both? In fact, what if I use many trees?

Each tree is a multicast tree, and there will be some waste of upload capacity, but

if I use all of them, maybe that will be helpful.

For example, I can use another one where the roots go down to A first, then A goes

to C, C goes to D and B. This is the server, these are the four

peers, Okay?

There'll be yet another tree. It can be many of these, it just show

these three trees here. Now of course you have to make sure that

the upload capacity across all the trees for each pair is not exceeding this total

upload capability. For example, node A is used here and here.

So you better make sure that the rate you assign on this tree okay, say, you know,

ten megabits per second. Now this tree you say twenty megabits per

second. A has to be able to support both trees, so

you have to make sure. A has at least in the 30 mega per second

in the kind of uploading capacity. Okay?

So you have to carefully manage where you place each pair in each tree.

But, you see the problem. The problem is embedding multiple trees to

support the same multicast session in a general graph.

Possibly with constraints on, say, the number of children nodes you can have

degree bounds. And this is a very difficult combinatorial

optimization problem. Okay.

It is not a continuous problem, like what we've seen before.

Like in last lecture and TCP congest control.

This is a graph theoretic optimization problem.

In the advanced material we will look at approximation methods, again using

[inaudible] problem to solve this in approximated fashion.

But we can look at the exact answer . Through a interesting, development in the

coming five to ten minutes for a special ideal case.

But the intuition should be clear. That those peers with a large upload

capacity should be placed closer to the root of the tree and support more

children. And possibly show up in more of these

trees too. Okay?

That is the intuition. And here is the example.

The example we want to look at is that, well, I have a source, okay the root or

the server, okay? Indexed by, denoted by s.

So I have this server sitting there with a certain upload capacity.

Okay? That's the original sender.

And I have n peers. They each have a certain upload, capacity

ui. And this one got a u sub s.

So you cannot violate a ui and u sub s constraint.

Now, the questions is, how can you construct, multiple trees so that, you can

achieve this bound. Okay.

So let's first write down about it. We'll come back to this picture in a

minute. So here is the ballot you would like to

show you can achieve. Right.

You want to say that the time that is take to finish multi-casting this is the mean,

is the max of, three turns. Let's say,

Ignore the download speed. Okay.

Let's say the download speed is fast enough even for the lowest down-loader.

Let's just look at the bottleneck from upload capabilities.

So you're looking at the max of these two numbers.

Oops running out of space, Okay? And that's the denominator here.

So you want to show this is true, okay, where T is the total download time.

And this is equivalent to saying that the maximum rate that you can achieve across

all these multicast trees is. The mean of the reciprocal of these.

Okay? Us over F , and US plus the summation UI,

over NF . Okay?

The smaller of these two numbers, because the largest rate is simple a proportion to

one over the time it takes. Since F appears on both, let's just assume

it is one unit. Whether it's one megabyte, or one

gigabyte, it doesn't matter, okay? That means we want to show our max equals

the mean of. Two terms, US and US plus summation UI

over N. Okay?

Fine, this captures the essence of the self scaling property.

So we basically say that if the US is actually bigger than.

Us plus sum of UI over N. Which is roughly speaking the average

upload capacity, counting both server and all the peers.

If that's the case, you've got a pretty powerful server.

That's very good. That's one case.

Okay. Then the answer is that R max should equal

to the smaller of the two terms, that is this term.

The other scenario is that you got a pretty.

Obsolete server. Okay?

Uploading capacity is very small for whatever reason.

So US is actually smaller than the average of these servers and all peers uploading

capacity. In that case, our Mac should be the

smallest of the two. That is, it should be equal to this.

So let's look at these two cases. So case one.

Let's say your, server is not a very powerful one.

So US is less than US + summation UI over N.

Okay? This is the, condition here.

And now, what kind of tree shall we construct?

Well, basically, going to construct the following families of trees.

There'll be n trees, one for each of these n cases.

Each of these cases, you have a tool hop. Tree, okay?

The depth is two. It goes to one of the n peers and then

that peer will become the parent node for all of other n-1.

Peers. And you do the same thing, except you swap

the position of this, parent peer. Okay?

Now it becomes peer #two. And then it goes down to the other n-1,

one three up to n, peers. And you repeat this.

Now you've got n trees. And they say that I'm going to do

multicast simultaneously using all these n trees.

Don't worry about this tree yet. We'll come to that in the second case.

And I need to show you that I can assign the right rate, the multi cast rate.

For tree one. Rate on tree two up to rate on tree n.

So that the summation of these rates will achieve my, target, what I want to prove.

Which is, it should be equal to the smallest of these two terms.

That is, u sub s. That's what I need to prove.