The visual signature of radial distribution is a straight line in the log, log plot of the tail distribution, because we can easily see that the log of the tail distribution, log of the probability that operator, with the distributed random variable is bigger than or greater than the fixed number X equals minus alpha log of X plus alpha times log of K. Now since K is constant, this is just an offset. What matters is that the log of this tail probability is minus alpha times the log of X so that on the log plot, it is a straight line with a negative slope of a minus alpha. So this is slope is minus alpha, and this is how usually we could pick. Pareto or in general, a long tail distribution. Either the distribution itself or the tail distribution on the log, log plot and see. The straight line. And, the slope of the straight line indicates the decay exponent. So, this decay exponent has been observed to be something like -2.1 for the in degree of web page graphs, for -2.4 for the out degree of web page graphs, -2.38 for router graphs. It has been discovered that many different networks exhibit the scale free property. In the sense that their node degree have the following distribution or tail distribution that follows say, Pareto or other long tail. Distributions. Okay, Now let's just clarify before going any further that scale free network in this lecture is not the small world networks in the previous lecture, number nine. In particular, scale free property of a network concerns only with the distribution of the known degrees and is entirely a topological property. What we'll see that is implications to functionality such as robustness to a tax on certain routers differs dependent on other factors. In contrast, small world is a property of a network concerning the existence and discoverability of short path between node pairs. And therefore, it is both structural or topological as we saw explained through [inaudible]. As well as functional as we saw in algorithmic small world. Now, of course, our network could be both small word and scale free. And indeed, in the vast materials in the last lecture we saw models that can make that happen. Now back to the scale free network and the Achilles heel of the Internet/ In the late 90s to 2000, certain researchers discovered that hey, the Internet router graph also exhibit this straight line on log-log plot and also has a Pareto distribution of the no degree sequence. That means it is robust against random attacks because we randomly picked a router to attack, its likely that you will not be destroying many connected paths. But, it is susceptible to attack on the most highly connected nodes. These are the routers that are, has the largest degree and because it's a scale free network, there can be routers with a really big degree. And if the target attack exactly on those networks then something bad will happen because these nodes are sitting in the middle of the network. Meaning it's in the middle of many paths and therefore if these nodes go down they are going to break up the entire Internet into many individual pieces. So this router sitting in the middle with many degrees. Some of the most highly connected nodes in the network. And yet it is in the center of the network, and thereby destroying it will bring down the network by destroying it into many small pieces. And therefore this node, is the Achilles heel of the internet. Now this is a, a very alarming statement, and it almost sounded like true, except, it is not, true. Okay Internet has many vulnerabilities towards security and reliability. But it doesn't have a highly connected router sitting in the middle of the network. What is Internet's reality then? Here's a multiple choise with two choises. Graph A, shows a typical Achilles heel kind of network. You've got very highly connected nodes like these two sitting in the center of the network. And graph B, turns out to have the same degree distribution. If you just look at degree distribution you cannot tell the difference between the two. But they clearly look very different. In other words, you can have two very different looking networks sharing the same no degree distribution, Say Pareto distribution. Okay, distribution of no degree does not lead to a unique type of network topology. In particular, in this network topology, you see some of these edge nodes are very highly connected. And, in fact, as you go into the core of the network, you get a much sparser connectivity pattern. A lot of these nodes are only medium to low degree. So if you're a tech. The most highly connected degrees nodes you're going to just bring down certain edge networks of the Internet, rather than destroying the entire network, by breaking down the core of the network. Whereas if you want to target mediumly connected nodes there too many of them. Remember, the degree distribution. If you target medium connected nodes then there are a whole lot of them. It's not exactly easy to know where they are, not necessarily, we'll be attacking these particular nodes. In another words, highly connected nodes. Routers with a lot of interfaces are actually more likely, much more likely sitting on the edge and what's in the middle is usually medium to low degree, that is the internet's reality. This picture does not fit the empirical data, does not fit the actual he has, or does not fit the actual router graph. So we wonder why not in the middle. And a clear answer is the following because you cannot have both a large degree many interfaces on the router and a large bandwidth per degree a high speed supported on each interface. Later in chapter thirteen we look at a little bit of router architecture and we will see that there is a constraint of total processing bandwidth. How many packets per second this router can actually process? And this number, let's say, thousand in some unit. You can view that as ten degrees and ten notes that can be connected to this router, and then each of them can be sending, say 100 certain units, 100 mega packet per second to this router or it can be, be composed into 100 degree, and then each interface however, can only support ten on the same mega base, mega packets per second. So there is an intrinsic trade off between degree. How many can you talk to and the bandwidth per degree. . And the router sitting in the middle of the network, these kind of routers by necessity must have a large bandwidth per degree. Because, there are layers of aggregation of trafic and statistical multiplexing again. Later in chapter thirteen, we'll talk more about this. But as you go from your home, Your work place your campus. Through many layers of aggregation. Each time there's aggregation you have more and more traffic. And by the time you get to the core of the network. These core routers. You must support a large band width per degree. You have to process many packets for each interface. And therefore you cannot possibly have too many interfaces. This option is not going to scale the network. Instead you will have a fewer think nodes connected to you, and then can support a high speed per interface. And that's because their product has to be constrained by technology and economic realities. Here's a typical chart showing some of the state of the art, in 2002, Cisco core routers, and some of the aggregators and some of the edge switches. The y axis is the total band width. Okay, and the y is the router degree in log scale. You can see that there are some performance. Boundary this is the total bandwidth okay, is already fixed. As you increase the node degree you are going to suffer in the bandwidth per degree and you cannot arbitrarily increase both this number and that number because their product is capped for different kind of router families. In other words, Cisco and Juniper, the top two core router manufacturers in the world. They cannot possibly manufacture a router that can make their total bandwidth to be very big. In the end, you have to come down to be a tradeoff. And for performance reason, you're going to have a large bandwidth per degree at the expense of smaller degree. No, But still, you may say, I still have other questions. For example, what about long tail distribution? Well, as we just saw that, you can have two networks, A and B. Both are long tail distribution in their no degree sequence, but they look very different, and have very different properties other than there are no degrees, which they share the same distribution. In other words, no degree distribution does not imply actual in tar topology. This is a very crude summary of the topology. The second object it might be but that's not likely. What is not likely, you may say that. This kind of graph is not likely. This is more likely and indeed in the next module of the video for this lecture we will indeed quantify the notion that this is much more likely and this is highly unlikely. In other words, if I have. A bag sent of many topologies. Each ball in the bag, each point element in this set is a topology, and they all satisfy power law of this long tail distribution, such as Pareto for the no degrees. In that I randomly draw one out of the bag, the chance that it would look like this with highly connect nodes in the middle is much higher than the probability of drawing something that look like this. And indeed. The internet renact, reality is much less likely. However, internet, was not drawn at random. It was designed, instead, with. Economic objective, we're coming to that in the next lecture. And simply put, we say that we want to maximize the [inaudible] going through the network, because that is how revenue will be generated subject to. Technology constraint, for example. I cannot make an arbitrary high bandwidth, total bandwidth router, and therefore, therefore, I must face a trade off between bandwidth per degree and the degree itself. So even thought it is not like, as likely to be drawn at random, we just have to realize Internet was never evolved as a random object. It was designed - with constraints and objective functions. The third objection might be, what about preferential attachment, that you might have heard about this phrase, and we have refrained from bringing this up, up to this point. We will bring them up in the next module of the. Video and a lot more in the advance material. But roughly speaking it says that, the rich gets richer phenomenon. Okay. As you add more no's. They will have a tendency to aggregate, to attach, to those nodes with already with a large degree. So a highly connected node gets even more highly connected. And this is what's called a preferential attachment. It turns out that, preferential attachment can A) generate This scale free network and b, it will lead to Achilles heels. The highly connect nodes in the middle of the network that phenomena will be true if preferential attachment is indeed case. So you may wonder gee, preferential attachment generates scale free and leads to achilles heel. So shouldn't scale free network have achilles heel. Not quite. That's actually logically incorrect statement because its not the only generative model. There are also other generative models that can also generate what we observe, and notably distribution, and yet do not lead to Achilles heel, such as what's called constrained optimization model, which we'll visit in the next module of the video. In other words, preferential attachment, PA for short, implies scale free network and implies Achilles heel. That, however, does not mean that scale free implies Achilles Heel. Because com string optimization in other models can also generate scale free network. So scale free network does not imply either or any of these generative model. Generative model is a hindsight explanatory process. Okay, they both can generate our empirical observation. The existence of this observation does not logically imply either of them is correct, and therefore does not imply Achilles heel. In short, there are three fallacies in this Achilles Heel, issue. First, the measurement's actually incomplete, and that skews the data. We actually don't know if the known degree distribution is indeed parietal. Second, even if it is, power law distribution does not imply professional attachment. And therefore does not imply Achilles Heel, necessarily. In fact, if you look at the internet reality, you see that in AT&T's 2003 networks. The highly connected nodes are on the edge. Okay? The maximum degree of the core outer is 68. But the degree of the at router was 313, much bigger. And finally, as we, I briefly mentioned, there's also functional protection on top of the topological properties. So we focused on this part of the logical fallacies, but if you cover all three that completes the discussion. Of why the internet actually does not have Achilles heel and you can see why people might have thought that it could have Achilles heel. But both the empirical evidence from carriers and router vendors as well as this logical discussion show that the internet does not have this kind of
