0:00

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.

Â 2:02

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.

Â 3:00

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.

Â 7:23

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

Â 9:29

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.

Â 10:52

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.

Â 12:21

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.

Â 13:24

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.

Â 14:54

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.

Â 16:24

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.

Â 17:31

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

Â