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.