Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
学位
证书

浏览 Coursera 的全部课程

浏览
搜索
企业版
登录
免费加入

Graphs and Degree Distributions

Loading...

网络：朋友、金钱和比特

普林斯顿大学

4.8（82 个评分） | 16K 名学生已注册

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. All the features of this course are available for free. It does not offer a certificate upon completion.

查看授课大纲

审阅

4.8（82 个评分）

5 stars
69 ratings
4 stars
10 ratings
3 stars
1 ratings
2 stars
1 ratings
1 star
1 ratings

PS

Mar 12, 2016

It is really a exceptional course which illustrates networking problems and answers with real life examples.

M

Jan 31, 2016

thanks to get world class education at home, my name is Mutlu from turkey

从本节课中

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.

Graphs and Degree Distributions17:23

The Internet's Reality18:38

Graph Performance and Likelihood10:10

Numerical Example and Generative Models15:48

教学方

Mung Chiang
Professor
Christopher Brinton
Lecturer

脚本

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.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司