You pick up your iPhone while waiting in line at a coffee shop. You google a not-so-famous actor, get linked to a Wikipedia entry listing his recent movies and popular YouTube clips of several of them. You check out user reviews on Amazon and pick one, download that movie on BitTorrent or stream that in Netflix. But suddenly the WiFi logo on your phone is gone and you're on 3G. Video quality starts to degrade, but you don't know if it's the server getting crowded or the Internet is congested somewhere. In any case, it costs you $10 per Gigabyte, and you decide to stop watching the movie, and instead multitask between sending tweets and calling your friend on Skype, while songs stream from iCloud to your phone. You're happy with the call quality, but get a little irritated when you see there're no new followers on Twitter. You may wonder how they all kind of work, and why sometimes they don't. Take a look at the list of 20 questions below. Each question is selected not just for its relevance to our daily lives, but also for the core concepts in the field of networking illustrated by its answers. This course is about formulating and answering these 20 questions.
Graphs and Degree Distributions
Loading...
来自 Princeton University 的课程
网络：朋友、金钱和比特
61 个评分
从本节课中
Does the Internet Have an Achilles' Heel?
At one time, there were rumors that the Internet has an Achilles' Heel, or a few center points which if attacked would completely disconnect the Internet. In this lecture, we debunk this myth, by showing that the fact the Internet is a "scale-free" network does imply it comes from a network model which would have such center points.
与讲师见面
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
Welcome to lecture ten of Networks, Friends, Money and Bytes.
In today's lecture, we'll try to formulate and answer this question.
Does the internet have an Achilles' heel? And of course the term Achilles' heel here
comes from the metaphor and we need to properly define what exactly do we mean an
Achilles' heel. Now, there's no shortage of vulnerability
of the Internet. In the second half of this course, we'll
be focusing a lot on the underlying architectural principles behind the
Internet. And we'll see that there are many holes
for security breach, for privacy intrusion, and also for unreliability.
However, a Achilles' heel here refers to a reported existence of a particular type of
Internet security issue back in 2000. And this specific vulnerability has the
following, Issues.
There is a highly connected router in the middle of the network can be easily
detected and if you destruct this router then the whole network will split into
many parts. Later in chapter thirteen, we'll talk a
lot more about routing and routers on the internet.
But for today, we can just say that in the Internet, there are many nodes and leads
of various kinds amd a lot of these nodes are what's called routers,
They route the packets across the Internet.
What this is saying is that, in the middle of the Internet, there're some very highly
connected routers. And if you destruct them because they sit in the middle of the
internet, where the many connections to the rest of the network.
If you take this one down, the entire network will break apart in many
distinctive pieces. It turns out that, if we define this kind
of specific vulnerability as the Achilles' heel,
Then Internet does not have an Achilles' heel.
And yet, back in 2000, it was reported that there is an Achiles' heel.
It was on the cover of Nature Magazine, and was a very alerting, report,
Except, it does not fit the reality of the Internet.
So why would there be such a report? And what can we learn from the way to
refute this wrong statement? Well, before we start answering that
question, we have to highlight that topology is only part of the story.
The story here is about a specific kind of robustness,
Or the network called the Internet. And as we have talked about, in networks, we have
to think about both the topology, Often represented as a graph with various
matrices associated with it, as well as the functionalities, which are captured by
a variety of mathematical models. So there are many functionalities,
For example, network protection. There are many network protocols, that
we'll talk about later in the course that can detect failure and then try to recover
from the failures. And these are functionalities sit on top
of the underlying topology, And therefore it's not just about what the
graph looks like. It's, it's also about the control plane
that sends a control signal to measure, detect, and recover from a variety of
failures, including router failures. On the flip side, often because of the
bugs or the time to converge in the network management plane that caused a lot
of failure issues. So both robustness and protection and
failures actually stem off and from the functionalities.
Robustness from the good things about functionality filler from the bugs and bad
design in the functionalities, rather than associate it with the underlying graphs.
Now having said that, let's assume actually incorrectly that, robustness is
about the graph only, for the rest of today's lecture, and let's say what we can
say there. Now, since we are focusing just on the
graphs today, I have to talk about three different kinds of graphs of the Internet.
One is the graph of webpages connected by hyperlinks, just like what we saw in
lecture two, or three, I should say with Google's PageRank.
Algorithm in ranking webpages based on this connectivity pattern.
Let's graph type number one. Graph type number two is graphs of the so
called autonomous systems, And.
These are business entities, For example, AT&T, British Telecom, Reliance in India,
and so on. Okay? Sometimes they are smaller entities,
smaller companies, or even campuses, for example, Princeton University.
These are different entities, profit or non-profit organizations, and they each
control a part of the overall network of networks that we call the Internet.
These individual autonomous systems, large and small ones, are connected by physical
as well as business relationships. That's the second type of graph.
The third type of graph, which is the focus today, is the graph of routers
connected by physical, often fiber, links. So if I just give you a picture of a
graph, This could be a graph where the nodes are
webpages and links are hyperlinks. It could be a graph where the nodes are
companies and organizations and the links are business relationships.
It could also be graphs where the nodes are actual physical routers and switches
and the links are physical fiber or copper wireless links.
When we talk about the robustness with respect to attack on hardware of the
Internet, we are talking about this third graph, the graph of routers.
And we are going to talk about the degree distribution of these graphs.
So I have to be able count the degrees of the nodes.
You may think that's an easy job, but actually,
Discovering the graph topology itself it is a very challenging task.
In fact for the Internet, no one has a precise map of the Internet.
You may think somewhere in the world that there is a place that stores the map of
the Internet. Actually, there is no such map.
If we're talking about the AS, autonomous system relation graph, many links are
missing. These business or physical links are not
reported or recorded. There also whats called Internet exchange
points. For example, thousands of these just in
Europe. As pairing shortcuts, they decide that
instead of going through some bigger autonomous system, they will form a short
cut themselves, say between two smaller and medium-sized autonomous systems and
often these are not reported. So, it's widely reported that it could be
more than half of the links actually missing and therefore we are not even
close to having precise view of the AS graph.
But what about the router level graph with physical links that we are focusing on
today? Often, the topology is estimated or
inferred based on some measurements. These are limited measurements called say
traceroutes. But it is also widely reported that because of the protocol
details, traceroutes often lead to bias the sampling.
In other words, in a huge network, , with many nodes and many links, a lot of links
are not properly recorded by this measurement methodology.
And in fact, near the edge of the network, for example, near your, corporation, near
on a campus, or near your home, High-rise buildings as opposed to in the
backbone of the network. There's often no scalable measurement
platforms. So at the router level, the graph is also
not known for sure. There are many missing links.
But let's assume again incorrectly, that we can measure the degrees accurately and
see what we can say. So let's skip the important fact that
robustness is more than just about a graph,
And skip the fact that these graphs, we do not yet have a good view.
And just go straight to say, suppose we believe that we can measure the degrees
and that's all that matters. The topology is all that matters.
Let's see what we can say. Alright.
So what is the degree distribution we observe for router level graphs?
Well, we can tabulate these degrees into a histogram.
And we can, therefore construct the probability distribution.
Let's say probability that a node's degree x is assuming a certain specific value
small x. And often, people look at the tail distribution, which is the
probability that the node degree x is bigger than or equal to a specific value
small x. It turns out that,
If you look at the either AS or router level, although the router level graph is
as well focusing right now. The tail distribution roughly follows x to
the power of minus alpha with sum constant k in front of it.
This alpha here is a constant parameter that describes that the decay of the tail
distribution and this approximate symbol basically says that for sufficiently large
small x. In other words, initially the tail may not
look like x to the power minus alpha, but when x small x is large enough the tail
eventually will look like this. So what's so special about the tail of the
degree distribution going down like x to the power minus alpha.
Well, it turns out that these kind of distribution is so-called long tail
distributions. And we will see why they are called long
tails as opposed to these short tails. And, if in the graph, the node degree
distribution follows long tail, then we got a corresponding network so-called
scale-free network or inhomogeneous networks.
As oppose to homeogenious networks, So homogeneous in what and scale-free in
what sense? Well, it turns out that a lot of
distributions, such as Gausian distribution or normal that we are so
familiar with, or exponential distribution, their tail distribution
decays much faster than this x to the power minus alpha.
And therefore, they do define a specific scale,
For example, for Gausian distribution, The scale is determined basically by the
mean and the standard deviation. And, it is not easy to get a node with a
degree [INAUDIBLE] degree that is way off from many standard deviation from the
mean. So that's why we call that homogeneous
networks, Whereas for long tail distribution, the
tail drops much more slowly, And for Gaussian, this would be basically
zero, But for long tail, this is still, still
signifigantly above zero. In this sense, it's called inhomogeneous
cuz there can be some nodes with a very high degree compared to the mean.
It's also called scale free, Because if you zoom into the tail, you see
that it also behaves like a heavy tail. So there's no characteristic scale.
No characteristic scale of, the node degrees.
So here is a cartoon to illustrate, this is Gaussian and this is long tail.
Okay, there is a scale with respect to Gaussian, there is no scale, the scale can
be arbitrary. It is very difficult to be a way off from
the mean, whereas this can be way off in a heavy tail, in a long tail distribution.
Now, what kind of distribution is long tail?
A specific special case is called a Pareto distribution,
The same Pareto as Pareto optimal that we were talking about in lecture one.
So, Pareto distribution has the following tail,
Which is the probability that our random variable x, say the node degree, is bigger
or equal to a specific small x equals x over k, for some constant k to the power
of minus alpha. That we can take the differentiation of
one minus this tail, which is the cumulative distribution, differentiate
this expression that will lead us to the probability distribution function, PDF,
for Pareto distribution, that says the probability that a Pareto distributed
random variable equals, sorry, equals x is alpha, k to the power alpha, just a
constant, times x to the power one plus alpha.
Okay? As you can see, both the tail distribution and the distribution itself
follows a long tail, X to the power minus something.
Okay? Either minus alpha or minus one plus alpha with some constants in front of it.
Now, in contrast, for a Gaussian, rather than a Pareto distribution, that PDF, is
as you may recall, one over square root two pi, standard deviation of sigma times
exponential minus x minus the mean mu2 squared over two sigma2.
Squared. Hm, okay? So for Pareto distribution, it follows
this. For Gaussian it follows this. We can easily convince ourselves
numerically that, if you plug some x in here, you will see that this is way
smaller than this, as x deviates much away from the mean. Okay?
This is exponential minus x squared, this is only x to the some power, one plus
alpha, negative. And a visualization for the Pareto distribution is a straight line
in the log-log curve.
