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 case, I will have 1, 2 inputs that

go into this switch and there are two outputs coming out.

So this is what we call a two times two switch.

So this will be a two times two switch.

But if you look at this one, for example,

we see one, two, three outgoing edges and three ingoing edges.

So this is actually a three times three switch.

And in a general binary tree, we will

see that all these intermediate nodes over here, they

are all three times three switches.

So approximately half of the switches

are actually three times three switches.

So that's the switch size.

Now, you may say, well, why don't I

use a larger-sized switch?

That would help me a lot, right?

If I could use, say, a four times four switch, then

I would be able to have more inputs coming in,

more outputs coming out, and I can actually

maybe use a ternary tree rather than a binary tree.

In a binary tree, every note at the level

has two children, right?

But we could design a tree that has

at every level three children.

So then, they can use four times four switches.

But if you do that, then the path from the leaf

up to the root is getting shorter

and the diameter gets smaller.

So if I increase the switch size-- so rather

than three times three, we look at four times

four or five times five, six times six and so on-- then

the diameter will actually reduce.

So what about having a monster switch, like I have just one

switch and I have my input zero all the way up

to input n minus 1 and then I have my outputs

on the other side?

Well, of course, the switch size is n times n

but the diameter is nothing, right?

The diameter is reduced to one.

You can immediately go from an input to an output

through the switch.

But this, of course, conceals the problem.

So what we are interested in is, well, we're

actually really interested in how

to solve the problem of routing all these inputs

to these outputs using smaller switches of size three

times three or two times two.

What we're really interested in is,

what is the internal structure in this monster switch?

I sort of have concealed the problem by just saying, oh,

I've got a big switch.

But what we want to solve today is

how do we do the routing in this case within the monster switch?

So we want to use just small switch sizes

and build up a network using these smaller ones,

like three times three switches or two times two switches.

Now, so that brings us to yet another parameter,

because here, we'd like to count the number or smaller

switches that we use and that relates

to the cost of the network, the amount of hardware

that you need to put into it.

So in this example, we have the switch count.

Well, it's pretty simple, right?

It's 1, 2, 3, 4, 5, 6, 7-- we have seven switches.

And in general, if we have n inputs-- so 1,

2, 3, 4 inputs-- then the number of switches

that we use in the binary tree is 2 times the number

of inputs minus 1.

So let's write that down.

So over here, we would have 2 times n minus 1,

which is the number of switches that you actually use.