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.
Waiting Functions and Price Optimization
Loading...
来自 Princeton University 的课程
网络：朋友、金钱和比特
59 个评分
从本节课中
How Do I Save on Each GB?
In the last lecture, we studied flat-rate and usage-based pricing schemes for mobile carriers. What these both fail to model is the time varying aspect of demand: consumption varies throughout the day, leading to peaks and troughs in usage. In this lecture, we will look at methods of Smart Data Pricing for taking this into account.
与讲师见面
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonVisiting Researcher and Lecturer
Department of Electrical Engineering
If I tell you that you have to wait for a certain amount of time t but then in
return, I'll give you a certain reward, p. Then what is the chance that you will
wait, that a month of time t, okay? Let's say this is a probability, a
likelihood of that you'll be waiting that long for this amount of reward.
Now, what this would be, would depends on, the ratio of your price sensitivity versus
delay tolerance, reflected in this dependance of these two arguments.
So this is what we call a waiting function.
Okay? With a little abuse of notation, we use w
to denote the function as well, w as a function of t and p.
Now this really should be a different function, for different users and
different applications. So, if you got, you know,
50 users each got to less on average, 100 applications then you should have, in full
generality, four or 5,000 different such waiting functions.
But in general, for practical purposes, we'll group them into the similar classes.
For example, we'll say that Alice and Bob, belong to the same class or, email versus,
Facebook update belongs to the same class. And then we'll have fewer functions to
estimate. Now in order to talk more about this, we
need to paramaterize this function, w okay.
Now, we know that w should be decreasing function in t because longer you're asked
to wait, the less change you're willing to wait.
Should also be at the same time, increasing function in P because the more
pricing functions you're given, the higher the chance that you will wait.
Now of course, there are many currently infinite number of functions that are,
decreasing in t and increasing in p. But one typical and very simple
parameterization is through the following form.
We say that w as a function of t and p, is simply p / t.
Now, this is not the final answer for one thing, the t can be zero, so let's say t +
one. Now, second this is not really
differentiating between your dependence on p versus t.
So one possibility is to get the denominator power beta.
So this is a function that it's parameterize by beta.
Beta is some positive real number that can praumatize a different concept weighting
functions. Now, in general, if you have a large beta.
That means that you are not willing to wait a whole lot.
If it's a small beta, then it means you are willing to wait a lot.
For example, based on our own survey in the US, we found that beta is about 2.027
for YouTube streaming. And, beta is the 0.63554 for video
download, for example from iTunes, okay. So, this, is much smaller number and
therefore reflects a much, more likely chance that it's going to wait.
So different users, different apps, different demographics and countries, you
can have different betas. Of course you don't have to stick to this
para, particular parameterization, but this is a fairly simple and quite useful
one. And later in the homework one of the
problems asks you to run through an estimation of weighting functions.
Now, suppose you have indeed run through an a y estimation weighting functions.
Now, the second step, after that profiling step, is the price optimization engine.
Here, the price can be viewed as incentive or reduction in price or reward of credit
to your monthly bill. Okay?
So instead of, say, now it's $ten a gigabyte,
I'm going to give you a reduction down to $eight a gigabyte if it's really needy of
incentive for you to shift traffic into this, say, middle of the night.
And maybe $one a gigabyte. Okay?
Now, we're not going to presuppose a particular price.
This should be discovered through an optimization problem.
So, what kind of optimization? As you may recall, we need an objective
function, we need different constraints, and we need variables.
And the rest will be constants if they're not variables.
So, what is our objective function here? For the carriers, there are two kinds of
costs incurred now. One is the cost of exceeding capacity.
That can translate into user turns or the capital expenditure you need to provide to
increase capacity and overprovision by the peek traffic.
Okay? The other is the cost of reward, meaning that since you are not charging
$ten but instead eight or $one, then you are giving away $two or $nine in these two
cases respectively, for example. So you got two kinds of cars that you want
to balance their sum, and let's say you weighted a sum of them.
Eight is the weighting parameter, some real positive number, times the exceeding
capacity cost to plus the reward cost. We'll see an example in detail soon.
And then the constraint basically is to say that I need to maintain proper
accounting of the traffic for each given period.
Lets say I've got two periods here okay, period one, period two.
The traffic that comes, goes away from period one into period two because of this
incentive versus traffic that goes from period two back to period one because of
incentives. You have to keep track of those traffic
getting in and out of the given period. And the variables are indeed these price
rewards. They are going to shape this part, and
clearly they define this part of the objective, and they are constrained by
your proper accounting rule. This is the optimization problem that
we'll be dealing with. Now before we show any examples, want to
highlight that there are also many system implementation issues involved here.
It's not just a mathematical exercise. As in many of the upcoming lectures in
this course. There are quite a few modules that require
different kinds of coding capability. For example, we need a graphic using
interface, simplest one would be the best, now we have to interface with the IOS and
Android, And or Windows if you use Windows Dongles
for 3G and LTE. We also need traffic measurement, and also
mobility pattern analysis in order to run the profiling engine.
We need a computational engines to run the price setting on a very dynamic basis, and
we need a database, of course, which could be partially split into your phone or
iPads and partially given to the ISP's. Okay.
Which part goes here and which part goes here, would, in part, depends on the
privacy and security concerns. And you also need, of course, scheduling
control software. Some of this may, goes to the end-user
devices. Okay?
Your phone and tablet. Some of that goes into gateways.
For example, in your home, your cable provider may have a residential gateway
together with a wifi. Okay? And some of that, control software
need to go into the backend usually, the control plane of the carriers, for example
we will see later in lecture nineteen something called the PCRF in cellular 3G,
4G networks. Okay?
You need software intelligence across all of these points in the network end to end.
As you can see, this is a gigantic piece of implementation,
Involves many different addiments and kinds of codes.
I just want to highlight that. This also says that basically,
You've got a network. Okay.
This is your network. You've got also end user devices.
The traditional network management software says, the intelligence should all
reside inside the network. But increasingly, you see these end user
devices capable and essential part of the network management.
And as you can see some of that here, here, here of these software animate
actually need to be split architecturally and put onto the end user devices.
Now, we have run a trial of TDP, in a project called, Data Me here actually at
Princeton with about 50 participants. And the same team is now going to launch
commercial class with a five commercial carriers, including three of the largest
in the US and India. But for this local, Princeton, small scale
trial that has been concluded already, what we have observed is that we can see a
30% reduction in the peak average ratio. That is, you chop the peak.
Okay, read from the average by 30%. Yet, at the same time, you also see
another almost magical thing: 107% increase in the average amount of usage
over, say, a day, or week. The key word is that this is average.
In other words, not only you chopped the peak, dump it to the valley, but also
raise the sea level. Use the metaphor of chopping, say, ice
bergs onto the ocean. The sea level also rise.
The total usage, or average, over day's usage rises affects more than doubles.
Why is that? Well, that's mostly because when people
look at the design. Okay.
I skipped the graphic using today's interface design, cuz it's really outside
the scope of this quarter networking. But one of the implementation gives you a
color-coded tab on your home screen. And, people look at the green button,
instead of red one, knowing that this is a very inexpensive, a cheap period to use
internet. And then, they start to consume more.
So, it leads to both a reduction in cost, and an increase in total usage.
That translates into, better profit for the carriers.
At the same time, it also translates into lower prices, back to the motivating
questions for this whole lecture. Lower prices per gigabyte for consumers
like you and me. Plus, it gives, actually, as a side
benefits, the power to chose between paying more for faster service and paying
less to save money, if you are capable of with willing to wait.
So that is the win-win created by such a TDP trial.
And I just want to illustrate one more time this solid line is.
The traffic over a 24-hour period, without TDP.
And the dotted line is an example of what you get with TDP.
So you can see, it makes this up and down less dynamic.
The ideal case you want it to be straight line.
And say, under the area, under the curves of the same area, let me convert that into
straight lines, so that the area under the straight line is the same as before.
Now that will be the ideal, but up close, in order to achieve that ideal the rewards
be very high cuz you have to take away a lot of time sensitive traffic.
And the objective function may say that you know, a times the cost of eExceeding
capacity may not be so heavy that it means that you can send out any reward that's
also a cost term. So the balance between these two cost
terms will determine how flatten you want to make this traffic profile look like.
In other words, if I increase this constant a, the weight in front cause
exceeding capacity relative to the cost of sending our rewards.
If I increase that a, then this will be flatter and flatter.
So how can I describe how flat it is? One possible quantitative metrics that if
I look at the straight line, and then look at the difference between this line and
one traffic curve. Say, the one before TDP, okay?
In absolute value, so this will be counted to size this, and this will be counted.
Okay. You add up those error differentials, we
call that residue spread, okay. The spread between, peak and valley.
Then, the residue spread should be a decreasing function of the capacity weight
eight. In fact, on plotting on log scale here you
see that indeed, as a becomes heavier and heavier weight, ISP has one more incentive
to reduce the spread and you see actually, in this particular example, at least, a
very sharp drop off, the cliff behavior. Now, what exactly should a be?
That, I don't know. There's no universally correct answer.
It depends on the actual cost structure again which is very proprietary sensitive
commercial secrets of different carriers. But the general methodology is as we just
