Explore
For Enterprise
Join for Free
Log In

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

浏览 Coursera 的全部课程

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

Graph Performance and Likelihood

Loading...

网络：朋友、金钱和比特

普林斯顿大学

4.8（85 个评分） | 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（85 个评分）

5 stars
72 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

脚本

In this module of the video, we're going to delve a little deeper into

understanding the trade off between functionality, model, and a pure

topological model. We're going to build a functionality model

by looking at the trade off between performance and likelihood.

Now, you may remember that we said if we look at the set of all those graphs that

satisfy a particular parietal distribution.

The chance you're going to draw at random a graph that looks like a preferential

attachment kind of graph with highly connected nodes in the center of the

network is much higher than the chance of drawing a graph as looking like the

internet with highly connected edge. So, we have to quantify the notion of

likelihood. We'll also mention that.

The active design of the internet involved around some performance and technology

objective and constraints. So, let's construct also a performance

metric. Let's do the performance metric first.

There are many ways to understand this, many, many different ways.

We're going to look at particularly simple and useful model, okay.

We say that there are many sessions indexed by I, and for each end to end

session, there is a source called Si, there is a destination called Di And then

we say that the rate of the session this end to end session across the network.

This is a network from one source to one destination.

This session's through put, XI is proportional to the.

Source supply denoted by y, sub si and the destination demand denoted by y Di, the

product of the two. And this is related what's called a

gravity model to understand the implication of n users supply and demand

implication on the session, and then per-link loading.

And now we say, let B proportionality constant be, say, row.

Now, these numbers, Y Si, Y Di are fixed, okay?

So we're going to search over row, which will lead to different xis.

We will like to maximize the summation of all the sessions, n to n sessions,

through, to the sum of XI over I. Subject to the following technology

constraint. One is this equation.

How x I depends on Ys and the other is this routing constraint.

Let RKI be a binary number., Okay?

It is one if session I passes through a particular router, K, a node K in the

network. And is zero otherwise.

So RKI XI summing over all the Is, is basically the amount of traffic that had

to pass through a particular router, K. So it has to be less than or equal to the

bandwidth supportable by this router, B sub K.

So this is now an optimization problem. Where we vary xi, which is given the y sub

constant. Given numbers, varying essentially this

row parameter. And we say the optimized the answer, sum

of Xi<i>. The optimal answer subject to this</i>

constraint is the throughput. We call that P, which is a function of the

graph given G. So G is the graph and this is the

optimized answer. P of G is the hour performance metric.

Now let's take a look at the likelihood metric now.

Well, how do we quantify the notion of likelihood of a graph.

There are also many ways such as modularity that we mentioned in the

advanced material part of lecture eight. Now we are going to use the similar idea,

we say that if you look at a Graph, G. Okay?

And this graph basically leads to I and j many, node pairs, with the link between

them. Look at all these node pairs with the link

between them, okay? And then look at the product of the

degrees, di and dj. This somehow quantifies the notion that

how likely a network of this type may have arised.'Kay.

Each of these two nodes of a certain degree and effect that they are connected

is somehow proportional to the product of their degrees.

So you sum up all the connected node pairs IJ.

This is a quantity we're going to call small S, which clearly is a function of

the given graph G. Then we look at all the graphs Gs with the

same. No degree distribution, say Pareto with a

certain parameter. And then we pick out the graph G star with

the largest small s of G. And we call this the S sum x.

Why do we need to do this?'Cause Cuz then we can normalize our likelihood metric.

We would define big S of G as basically a normalized version of small s of G.

It's normalized by small s sum x. Now we uses big s of g to represent the

likelihood of drawing a graph with this no degree distribution.

From the set of all graphs satisfying the same distribution.

So now we got two things, one is P of G, the other is S of G. Given a graph will

clearly show constraint, the possible routing available and therefore

constraint, the possible sum of procession throughput.

And given a graph. You will also define the likelihood of

drawing that at random from the set of all graphs satisfying the same distribution.

So we've got P of G and S of G denote performance and likelihood respectively.

And our job is to look at their trade off. Here is a cartoon to illustrate a typical

trade off. Both points shown here satisfy the same

pareto node re-distribution. And yet, preferential attachment, which

leads to highly connected nodes in the center of the network sits here in the

trade off space between P and S. It is much more likely, it's a 80% chance,

to draw at random something that looks like professional attachment generated

topology, a scale free network with highly connected nodes to the center.

But its performance measured in bits per second is the sum of the optimized the

procession through put is much smaller ten to the say, power ten, compared to.

And different kind of topology, Internet like topology where the highly connected

nodes sitting in the edge of the network and the core is much as passer with medium

to low degree nodes. So the high, highly connected nodes are at

the lower edge. This is the kind of internet topology that

we see. They also satisfy node degree distribution

and their chance of getting joint random from that set is much smaller,

twenty percent compared to the preferential attachment kind of network.

However, the saving raises that their performance is much higher say two orders

of magnitude bigger and that matters a lot.

It's a hundred times more capable of supporting bandwidth and therefore revenue

going thru this network If you were designing the internet, you would do it

this way. Rather than saying, well let's just pick

at random. And enjoy a high likelihood of drawing it

at random. Even though it produces a performance

bottleneck with these high degree nodes hitting the center of the network,

reducing the capability of supporting a lot of bandwidth passing through it.

Because per interface bandwidth is necessarily low.

So no one will say, let's do it that way. People will say, well, let's design it

this way and make sure the performance is high.

And this illustrates the point that the internet router graph is performance

driven. And technology constraint can make routers

like this and yet have to support high performance. This is the way to go.

Small probability of being drawn but we're now drawing it at random anyway with a

high performance matrix. Now that was numbers associated with the

Internet Let's look at a very small example to work out some details now.

探索我们的目录

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

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

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

通过 App Store 下载

通过 Google Play 获取

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

社区
Learners
Partners
Developers
Beta Testers
Translators

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

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