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