# Pricing communication networks P10

Chia sẻ: Do Xon Xon | Ngày: | Loại File: PDF | Số trang:26

0
51
lượt xem
4

## Pricing communication networks P10

Mô tả tài liệu

Hợp đồng dịch vụ xác định đảm bảo rằng sẽ được đáp ứng bởi nhà cung cấp cả dịch vụ và người mua của hợp đồng. Như chúng ta đã thấy trong Chương 2, hợp đồng dịch vụ có thể phải linh hoạt đảm bảo về hiệu suất, cho phép cả các nhà điều hành mạng và người sử dụng để thay đổi các thông số quan trọng, chẳng hạn như tốc độ mà những người sử dụng có thể gửi dữ liệu đến mạng. Cả hai bên có thể có lợi. Nếu năng động giá cả có sẵn, người...

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Pricing communication networks P10

1. Pricing Communication Networks: Economics, Technology and Modelling. Costas Courcoubetis and Richard Weber Copyright  2003 John Wiley & Sons, Ltd. ISBN: 0-470-85130-9 10 Charging Flexible Contracts Service contracts deﬁne guarantees that are to be met by both the service provider and the buyer of the contract. As we saw in Chapter 2, service contracts may have ﬂexible guarantees in terms of performance that allow both the network operator and the user to vary important parameters, such as the rate at which the users may send data to the network. Both parties can beneﬁt. If dynamic pricing is available, the user can dynamically vary the amount of resources he consumes by changing his willingness to pay. The network can control congestion by dynamically adjusting the share of resources that each user is allowed making use of the loose obligations in the contracts. Flexibility is particularly useful when the load on the network dynamically rises and falls as connections start and ﬁnish, or the available capacity ﬂuctuates. Flexibility can also beneﬁt a user whose resource requirements vary with time. He need not predict and reserve at the start what he thinks his maximum resource requirements might be. The network also beneﬁts because it need not reserve resources that might not be used, and so more service requests can be accommodated. Of course, by not reserving his maximum requirements, a user runs the risk that at a future time the resources he needs may be unavailable or too expensive to obtain. Since the time-varying availability of resources means that ﬂexible contracts do not provide strict performance guarantees, users with applications that require strict guarantees may prefer contracts whose parameters are deﬁned at the time the contract is set up and remain static throughout their lives. Such contracts can be priced using the ideas for guaranteed services described in Chapter 8. Contracts with ﬂexible guarantees are appropriate for elastic applications. An elastic application is one that can adapt itself to a varying availability of network resources. Examples are video and voice encoders and decoders that can change their data compression rate without signiﬁcant loss of perceived quality. Of course, even elastic applications require some minimum resources and this may restrict the number of such applications that can be accommodated simultaneously. A network that shares its resources amongst elastic applications with ﬂexible contracts must decide how to divide the network resources amongst them. It does this by setting the dynamic parameters of the contracts to make best use of the resources. If each user is allowed too large a peak rate then there may be unnecessary congestion. However, if each user is allowed only a small peak rate then resources might be wasted. In general, any parameter of a contract can be ﬂexible, but in practice it is the peak rate that is most often ﬂexible. Let us focus on contracts like this. As there is only a single
5. THE PROPORTIONAL FAIRNESS MODEL 239 Example 10.1 (A fair window ﬂow control) Suppose the ﬂow xr on route r is controlled by a window of size Br bytes (as described in Section 3.3.7). In general, the use of window ﬂow control leads to ﬂuctuating rates. That is, xr varies in time and the resulting trafﬁc is bursty. However, as an approximation to the actual case, suppose that the network is equipped with additional mechanisms to smooth bursts so that there is a static regime in which xr remains constant. Let Tr be the round-trip time on route r, excluding any queueing delay on the forward path or backward path due to packets waiting in buffers (i.e. the round-trip time if the system is lightly loaded). Let Br and Tr be ﬁxed. Also assume that inside the network packets are queued at the routers in order of their arrival, and buffers are large enough to imply no packet losses. In this model, sources do not react to congestion indication signals and send packets at constant continuous rates xr D Trtotal =Br , where Trtotal is the total round-trip delay on route r. It can be shown that in the corresponding ﬂuid model there is a unique static regime and in this regime the resulting set of ﬂows fxr g is the unique solution to the optimization problem X X maximize .Br log xr xr Tr / ; subject to xr Ä C j for all j x½0 r 2R r : j2r This is similar to the problem of allocating ﬂows in a weighted proportionally fair P way, but with a penalty term of r xr Tr , that has the interpretation of the total rate of delay incurred by packets. If the round trip times are negligible, then the static ﬂows will comprise a weighted proportionally fair allocation with weights equal to the window sizes. Thus, we see that ﬁxed size window control can achieve a fair sharing of the bandwidth according to this criterion, provided scheduling at each link is performed in an appropriate manner. In more general set-ups, it can also be shown that ﬂow control mechanisms that use additive increase/multiplicative decrease tend to produce ﬂow allocations that are proportionately fair. Such mechanisms control the window size so that in the absence of congestion the sending rate increases at a constant rate, while if capacity is exceeded on some link in the path and congestion occurs, then the sending rate decreases at a rate proportional to its size at the time congestion was sensed. Further details are given in Section 10.4. 10.2 The proportional fairness model Let us continue with the model of the previous section. Recall that each route is associated with a user and requires some subset of the links. User r is an elastic user, whose utility for a ﬂow of xr is u r .xr /, which we assume to be increasing, strictly concave and continuously differentiable in xr . Let us deﬁne SYSTEM as the global optimization problem of maximizing the social welfare, subject to the capacities of the links. It is X X SYSTEM : maximize u r .xr / ; subject to xr Ä C j ; for all j 2 L x½0 r 2R r : j2r We can rewrite this as X SYSTEM : maximize u r .xr / ; subject to Ax Ä C (10.2) x½0 r where Ajr D 1 or 0 as j 2 r or j 62 r, respectively.
6. 240 CHARGING FLEXIBLE CONTRACTS Although it is easy enough to formulate SYSTEM, it is not practical for the network operator to solve it. The problem is that he does not know all the utility functions, u r . Similarly, the users cannot solve SYSTEM because they do not know each other’s utilities or the constraint set Ax Ä C. Fortunately, if the network and users exchange a little information they can solve SYSTEM together. Suppose user r is willing to pay an amount wr per unit time, and that if he does this he receives a ﬂow xr D wr =½r . Here ½r is the charge per unit ﬂow on route r and is controlled by the network. Imagine that the network somehow chooses the ½r s so that the resulting ﬂows are feasible. Given that user r has been told the price ½r his problem is USERr : maximize u r .wr =½r / wr (10.3) wr ½0 Note that he has all the information he needs to solve this problem. What problem should the network solve? It cannot easily solve SYSTEM because it does not know the users’ utility functions. However, suppose the users communicate their wr s and the network then allocates ﬂows so they are weighted proportionally fair. That is, it solves the problem X NETWORK : maximize wr log xr ; subject to Ax Ä C (10.4) x½0 r 2R A key result is that the solution of SYSTEM occurs when the NETWORK and USERr problems are solved simultaneously, with their solutions in equilibrium. That is, there exist f½r g, fxr g, fwr g such that xr D wr =½r and these are simultaneously solutions to SYSTEM, NETWORK, and USERr for all r. This result is important because it means that if the users and network communicate their wr s and ½r s, then the solution of SYSTEM can be obtained using information that is available to each agent. Let us prove the key result. It follows from solving SYSTEM by Lagrangian methods. Given the value of ½r the solution of USERr is straightforward: wr satisﬁes u r .wr =½r / 0 ½r D 0 (10.5) Consider the solution of NETWORK. Imagine that the fwr g are given and ﬁxed. The fact P that r wr log xr is concave in x and the constraints are linear, means that NETWORK can be solved by maximization of its Lagrangian, i.e. by solving X maximize L ; where L D wr log xr C ¼> .C Ax z/ (10.6) x;z½0 r 2R Since for this objective function xr D 0 cannot be optimal, L is maximized where it is stationary with respect to xr , and so @L wr X D ¼j D 0 @ xr xr j: j2r Thus necessary and sufﬁcient conditions for fxr g to be a solution to NETWORK are that we can ﬁnd f¼ j g such that wr xr D P ; ¼ ½ 0; x ½ 0; and ¼> .C Ax/ D 0 (10.7) j: j2r ¼ j
7. THE PROPORTIONAL FAIRNESS MODEL 241 These equations have a nice interpretation as deﬁning a set of market clearing prices f¼ j g when user r has an initial amount of money wr and purchases as much bandwidth as possible in route r. As necessary conditions these imply the existence of fxr g and f¼ j g satisfying (10.7). Similarly, consideration of the solution of SYSTEM by maximizing its Lagrangian gives that a sufﬁcient condition for its solution is the existence of fxr g, f¼ j g such that X u r .xr / 0 ¼ j D 0 ; ¼ ½ 0 ; x ½ 0 ; and ¼> .C Ax/ D 0 (10.8) j: j2r P Now if USERr and NETWORK have solutions that coincide, we must have ½r D j: j2r ¼ j . This means that the sufﬁcient condition (10.8) of SYSTEM can be satisﬁed using the nec- essary conditions for the NETWORK and USERr problems in (10.5) and (10.7). We stress again that the advantage of approaching the solution of SYSTEM by way of the NETWORK and USERr problems is that the network and users only need information to which they have access. The network does not need to know the users’ utility functions, and the users need not know the resource constraints of the links. The network communicates with the user r by announcing a new value of the rate xr , or equivalently announcing a new price ½r . Using this data, user r solves USERr and then tells the network his new selection of wr . In practice, however, it is not guaranteed that this iterative computation between the users and the network converges and that its solution is stable. This is because the computations are asynchronous and the communication of the values of fwr g and fxr g are subject to random delays which differ from user to user. It would be better if we could avoid having to solve the NETWORK problem in some central location, but could instead solve it in some decentralized way. Ideally, the network could communicate some information to the users that would give them the incentives to make their own adjustments to ﬂows in a way to solve NETWORK themselves. This would be similar to the way that the TCP protocol operates in the Internet, in which software running on each user’s computer adjusts the local sending rate and results in an allocation of ﬂows inside the network by operating in a distributed fashion. The challenge is to understand how this can be done so that the network as a whole reacts intelligently to perturbations and the resulting allocation of ﬂows solves the desired network optimization problem. We begin by presenting two algorithms that solve NETWORK in a distributed fashion. We then discuss some convergence and stability results, which suggest that such a distributed solution to NETWORK, combined with users solving their own local USERr problem, does eventually converge to the solution of the SYSTEM problem. 10.2.1 A Primal Algorithm One way to ﬁnd fxr g and f¼ j g that satisfy the sufﬁcient conditions (10.7) of NETWORK is by use of a so-called primal algorithm. In both this algorithm and the dual algorithm which follows, we assume the wr s are held ﬁxed by the users at constant values. Consider the system ! d X xr .t/ D Är wr xr .t/ ¼ j .t/ (10.9) dt j: j2r ! X ¼ j .t/ D p j xs .t/ (10.10) s: j2s
9. THE PROPORTIONAL FAIRNESS MODEL 243 NETWORK. For example, one can take p j .y/ D maxf0; y C j C žg=ž 2 . Then maximizing U is an arbitrarily close approximation to the SYSTEM problem as ž ! 0. 10.2.2 A Dual Algorithm An alternative approach uses a dual algorithm, based on the Lagrangian dual problem to NETWORK. This problem is: minimize¼½0 maxx;z½0 L, where L is deﬁned in (10.6). It reduces to ! X X X maximize wr log ¼j ¼jCj ¼½0 r j: j2r j and the objective function can be approximated by ! X X XZ ¼j V.¼/ D wr log ¼j q j .¹/ d¹ r j: j2r j 0 where we imagine that q j .0/ D 0 and q j .¹/ increases rapidly to C j for ¹ > 0, as shown at the right of Figure 10.2. To ﬁnd fxr g, f¼ j g, consider the system ! d X ¼ j .t/ D Ä j xr .t/ q j .¼ j .t// (10.11) dt r : j2r wr xr .t/ D X (10.12) ¼k .t/ k:k2r Again, Ä j > 0, and q j .¼ j / is interpreted as a rate of ﬂow in link j corresponding to a rate of charge in that link of ¼ j . This rate of charge adjusts itself proportionally to the excess demand (the term in the right-hand side of (10.11)). This is similar to the tatonnement process of Section 5.4.1. As with the primal algorithm, it can be shown that V.¼/ is strictly concave in ¼ and that it is a Lyapunov function for the system (10.11)–(10.12). Thus, ¼ converges to the maximizer of V. 10.2.3 User Adaptation So far, we have assumed that the wr s are ﬁxed on the timescales of the operation of the pri- mal and dual algorithms. In this case NETWORK is solved by assigning each user r a rate xr . Now suppose that the wr s are allowed to change. A simple iteration between users and network could take place as follows. The users could wait until the xr s in NETWORK converge. Then, after computing the resulting prices based on their previous selections of wr s and the newly deﬁned xr s, they could solve their local USERr problems and make new choices of wr s. These could become new inputs to NETWORK, which could be resolved, and so on. A more interesting iteration is when both problems are solved at the same time. Observe that xr .t/ is deﬁned by the differential equation (10.9), which user r can affect only through his choice of wr .t/. Suppose that he monitors xr .t/ continuously and varies wr .t/ so that wr .t/ D xr .t/u r .xr .t// 0 (10.13)
10. 244 CHARGING FLEXIBLE CONTRACTS This choice is consistent with continuously maximizing his net beneﬁt. To see this, suppose that at time t he observes the implied price ½r .t/ D wr .t/=xr .t/. For a Ž that is imagined to be inﬁnitesimally small, he chooses wr .t C Ž/ for time t C Ž so to maximize his net beneﬁt, i.e. so wr .t C Ž/ D arg maxwr [u r .wr =½r .t// wr ]. This happens if and only if wr .t C Ž/ satisﬁes u r .wr .t C Ž/=½r .t// D ½r .t/, which is (10.13) as Ž ! 0. Thus, we see 0 that choosing wr .t/ by (10.13) is consistent with his continually maximizing his net beneﬁt at the presently implied price. In summary, user r responds to the varying prices by solving USERr and using (10.13) in the place of wr in (10.9). Using revised Lyapunov functions, one can again establish the stability of both the primal and dual algorithms in this case, i.e. when users solve their local optimization problems while they perform ﬂow control. The appropriate Lyapunov function for the primal is P X X Z s: j2s xs U.x.t// D u r .xr / p j .y/ dy (10.14) r j 0 where again, this can be made an arbitrarily close approximation to the SYSTEM problem by appropriate choice of p j .Ð/ 10.2.4 Stochastic Effects and Time Lags Further things can be said when there are delays and stochastic effects. One can still prove convergence but the coefﬁcient Är is important. When there are no delays or stochastic effects, the speed of convergence increases with both Är and the magnitude of the derivatives of p j .Ð/ at the point where U.x/ is maximized. One can think of p 0j .Ð/ as the sensitivity of the resource’s load response, and of Är as the sensitivity of the response of end-systems to congestion marks. To model delays we would write ¼.t djr / and xs .t djs / on the right-hand sides of (10.9) and (10.10), where djk is a number expressing the time delay in communication between user k and link j. When there are stochastic effects, decreasing Är or increasing p0j .Ð/ leads to a smaller variance in the distribution of x.t/ at equilibrium. Increasing p0j .Ð/ and Är increases the speed of convergence but may make the system unstable. Thus, there is a trade-off between the speed of convergence and stability. In broad terms, the speed of convergence decreases as the magnitude of the djr increase, and the equilibrium point of the resulting system is asymptotically stable provided Är is sufﬁciently small (for a given choice of p j .Ð/s). In our discussion so far, we have assumed that the choice of the function p j .Ð/ that is to be implemented at link j is simply an engineering decision, whose aim is to realize a robust and efﬁcient ﬂow control procedure that will lead to a good approximation to the optimal solution of SYSTEM. We now discuss how such a choice may be related to actual congestion costs. 10.2.5 Proportional Fairness with a Congestion Cost In Chapter 9 we considered models in which social welfare is reduced by a congestion cost. A model with a congestion cost that is similar to (10.2) is ! X X X SYSTEMc : maximize u r .xr / cj xs (10.15) x½0 r j s: j2s