0:00

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.

Â 2:25

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.

Â 3:01

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

Â 5:39

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.

Â