Subtitles section Play video Print subtitles The following content is provided under a Creative 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