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.
Graph Performance and Likelihood
Loading...
来自 Princeton University 的课程
网络：朋友、金钱和比特
59 个评分
从本节课中
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 BrintonVisiting Researcher and Lecturer
Department of Electrical Engineering
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.
