## Subtitles section Play video

• The following content is provided under a Creative

• Your support will help MIT OpenCourseWare

• 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.