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.
