Commons license.

Your support will help MIT OpenCourseWare

continue to offer high-quality educational resources for free.

To make a donation or view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

MARTEN VAN DIJK: So today, we're going

to talk about communication networks.

Communication networks is a great application

of graph theory.

So what we're going to study is, how

do you route packets through networks?

So you have the internet, which is a chaotic network.

It's not organized.

We are interested in highly structured networks

and you can find them, for example,

in parallel computers, where you want to route the data flow.

You can find them in certain telephone switches networks

and so on.

So we are going to talk about a few very special ones,

binary trees, and then slowly we will figure out

what all these performance measures really mean.

This one has to do with latency.

We have switches, their size, the number of them,

congestion, and then we will slowly get down

to Benes network, which is a really beautiful network

with beautiful parameters.

And we are going to prove those.

So let's start off with the first one, the complete binary

tree, and let me draw it for you.

In this network, we will have a root

and let me just draw it first We have vertices that

represent here the switches.

So these circles-- let me explain it over here-- actually

represent a switch.

And the idea is that these actually direct packets

through the network.

And these packets are fixed-size packets

of data, so like, I don't know, say 4,000 bytes or bits

or whatever the network wants you to comply to.

So these are fixed-size pieces of data.

So what we want is we want to be able from every terminal--

and the terminal I will denote by a square--

from every terminal, I want to be

able to reach any other terminal.

So what is a terminal?

A terminal is like a computer or something like that.

It's actually the source and the destination of data.

So what we are looking for is how can we

route-- how we can find a network of switches

that are connected through wires, fibers, or-- yeah?

What's the question?

AUDIENCE: Can you move down a bit

the top of the-- how it's getting cut off?

No, the--

That one.

MARTEN VAN DIJK: Oh, sorry.

AUDIENCE: All right.

Thank you.

MARTEN VAN DIJK: So what we want is

we want to route packets that's come from any terminal

to any other terminal.

That is what our goal is and we want to make sure

that that is efficient.

So the first one is this binary tree.

And let's see how this may work.

We may have switches that actually have

inputs coming from terminals.

And the switches may also output to terminals,

so here at the bottom.

At this site, we have a similar structure.

this is the root of the tree.

We have another switch over here.

We go down, we go up here, and once more, like this.

And again, we have-- oops.

We have input coming in or an output coming out

to their respective terminals.

So what is happening here is that I

would like to have an input-- say input zero wants

to travel all the way over to say,

the output that is present over here.

So let me label these.

So we have the output zero, input one, output one,

input two and output two, input three, and output four.

So well, I can definitely reach every single output

from any input so that's great.

So this looks like something that you are familiar with,

right?

It's just a tree.

It's a directed graph, but these edges

go in both directions, right?

So I have an edge that goes from here to here and back from here

to here.

So this is the kind of layout that you could try out

first to see whether this type of network

would lead to good performance.

So let's have a look at the different parameters

and see how well this behaves.

So here, we have a few parameters

that we will be talking about.

So first of all, let's talk about the latency

in this particular network.

So how are we going to measure this?

Well, we're going to look at this graph

and we're going to measure it by the number of wires

that you need to go through from an input to an output.

So let me write this down.

So the latency is the time that is required for a packet

to travel from an input to an output.

And how are we going to measure this?

Well, we're just going to measure this

by the number of wires that we need to go through.

So this you have seen before.

We can measure this by the diameter

of that particular graph.

So here, we will define it for a network.

So the diameter of a network is going

to be the length of the shortest path between the input

and output that are furthest apart.

So let's have a look at the graph above.

So for example, we can clearly see that, for example, input

and output-- so say, input zero and output one

are connected by just going up one step over here,

but just going up from here to here.

Then, this switch forwards the packet to this switch.

This switch reroutes it, forwards it over here,

and then it goes back to the output, output one.

So for example, this particular path only has 1, 2, 3, 4 edges.

And what we are interested in is sort of the worst-case time

that it requires to go from an input to an output.

So that means that we are interested in a diameter.

And a diameter is in this case, well, the shortest path

that you can find from an input to an output that are furthest

apart.

So what are those who are furthest apart?

Well, of course, you would like to go through here, right?

So if I connect the input zero to say, output four,

I will need to go all the way up through the route

down to the output.

And how many edges do we see here?

1, 2, 3, 4, 5, 6-- so in this example,

we have a diameter that is equal to six.

And in general, if you are looking at n times n networks,

what does it mean?

n is the number of inputs and n is also the number of outputs.

So in this case, we have a four times-- well,

this is actually three over here--

we have four inputs and four outputs.

So this particular example depicted on the board

is a four times four network.

So if you generalize this for any size binary tree,

say, an n times n network, then what's

the diameter of such a general network?

Well, if we have n inputs and n outputs,

well, we have to go all the way up

through towards the root and all the way down.

So we actually count the length of a leaf to the root

here twice.

So in general, we have a diameter that looks like this.

It's 2 times 1 plus the logarithm of n.

So in this lecture, we will have n is going to be a power of 2,

just to make calculations simple.

And the logarithm is always to the base two.

So this is a diameter of a general binary tree.

And well, what are the other parameters?

So that does not look too bad.

It's logarithmic in answer.

That sounds pretty good.

What about the switch sizes?

Well, how do I measure those?

It's like the number of inputs that get into it

and the number of outputs that get out.

So in this