Pricing communication networks P9

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

Thêm vào BST

Báo xấu

81
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương này diễn tả hiện tượng tắc nghẽn, và những cách thức mà nó có thể ảnh hưởng đến quyết định giá. người sử dụng Internet là đặc biệt quen thuộc với các hiện tượng tắc nghẽn và sự suy giảm chất lượng dịch vụ xảy ra là số lượng người dùng đồng thời tăng. Điều này tương tự các hiệu ứng tắc nghẽn bởi kinh nghiệm lái xe khi cuộc hành trình lần và tăng số vụ tai nạn do xe ô tô ngày càng nhiều trên đường. Trong chương này, chúng tôi hiển thị như thế nào giá...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Pricing communication networks P9

Pricing Communication Networks: Economics, Technology and Modelling. Costas Courcoubetis and Richard Weber Copyright  2003 John Wiley & Sons, Ltd. ISBN: 0-470-85130-9 9 Congestion This chapter deals with the phenomenon of congestion, and the ways in which it can affect pricing decisions. Internet users are especially familiar with the phenomenon of congestion and the decline in service quality that occurs as the number of simultaneous users increases. This is similar to the congestion effects experienced by car drivers when journey times and accident numbers increase because more cars are on the road. In this chapter, we show how pricing can be used to control congestion and increase the value of services to users. In previous chapters we have neglected the effects of congestion by supposing that the beneﬁt that a user obtains from a communications service depends only upon parameters of that service and the amount of the service he obtains. We have imagined that if user i buys a quantity of a service xi at a price p then his net beneﬁt takes the form u i .xi / pxi (9.1) where for user i’s demand we write xi rather than x i , since his demand is one-dimensional. Once we know the users’ demand functions, the suppliers’ cost functions and their technology sets, the problems of maximizing the suppliers’ proﬁt or the social welfare can be solved by using prices to allocate services to the users who value them most and to match the demand for services to supply. This is all true for a service that has statically deﬁned guarantees that may not vary during the life of the service. In this case, congestion is expressed in terms of packet loss rate or packet delay, and a maximum tolerable level of congestion is part of the service speciﬁcation. Call admission control is used to maintain congestion below this level. Hence u i .xi / in (9.1) denotes the utility of using a quantity of service xi that has this level of congestion. When services have contracts with dynamic parameters (e.g. the maximum sending rate may vary during the life of the service), and there is no strict guarantee on minimum performance levels, users will be tempted to demand the most that they can from the network. But a decision by the network to grant such requests to all its customers may make performance intolerable. It is clear that (9.1) fails to capture the effects of the arbitrary levels of congestion that can occur if the network does not use controls such as call admission to restrict the maximum congestion level. In modelling congestion, we suppose that when a user receives more of a service the value of the service deteriorates, as it is experienced by him and all other users.
220 CONGESTION The models in this chapter are concerned with the effects of congestion and pricing that take congestion into account. In the case of services sharing a common resource pool, we model congestion by supposing that user i has a net beneﬁt that depends upon the amounts of service demanded by other users. That is, he enjoys net beneﬁt of a form such as u i .xi ; y/ pxi (9.2) P where y D i xi =k, for some constant k. Here k parameterizes the resource capacity of the system. The intuition is that congestion depends upon the load of the system, as measured P by y. Full load may correspond to i xi D k. If user i requests a quantity of service that is small compared with the total requests of all users, then y does not vary much with different choices of xi , and so the problem of maximizing (9.2) reduces to that of maximizing (9.1), with y taken as ﬁxed. In this chapter we suppose y is not ﬁxed, and consider the problem of determining p so that when the market is in equilibrium we maximize some measure such as social welfare or the service provider’s proﬁt. When a participant in a market can, without suffering penalty, make choices of variables that adversely affect the utilities of other participants, we say there is a negative market externality. Congestion is a good example of a negative market externality. Positive market externalities are also possible. For example, when a consumer purchases a particular model of mobile phone he increases the popularity of that phone; its increased popularity encourages the manufacturer to provide spare parts and accessories, making it more valuable to all its owners. Returning to our model of congestion: how can users be posed problems of maximizing their individual net beneﬁts so that social welfare is maximized when they do so? The answer, which we give in Section 9.1, is to price congestion. Economists say that we ‘internalize the externality’. The user’s ﬁnal charge has two parts: a charge for the cost for providing the service and a charge for congestion. The congestion charge is used to manage congestion and to determine how the available resources are shared amongst users. In general, moderate levels of congestion are usually desirable. This is because zero congestion may require very inefﬁcient use of resources. A high level of congestion uses resources more efﬁciently, but services are degraded too much. Ideally, a mechanism for controlling congestion by pricing should be self-tuning, and automatically ﬁnd a good compromise between service degradation and effective resource usage. In Section 9.2 we make the connection between congestion pricing and sharing ﬁnite resources under a capacity constraint. In Section 9.3 we give examples in which users share congested resources. We look at models with blocking, loss and delay. Section 9.3.2 looks at the problem of pricing more than one service, when the services are substitutes and both subject to congestion. An important notion, described in Section 9.4, is the realization of a congestion price as a sample path shadow price. Finally, in Section 9.5 we present a general model for congestion pricing. 9.1 Deﬁning a congestion price The following simple model illustrates the basic ideas of congestion pricing. Consider the case of a single service quantiﬁed in terms of a single dynamic parameter. Suppose n users make demands for quantities of this service. The producer can supply capacity k at cost c.k/. For the moment, we take k as ﬁxed and pose the problem of maximizing social
DEFINING A CONGESTION PRICE 221 welfare as X n maximize u j .x j ; y/ c.k/ (9.3) fx1 ;:::;x n ½0g jD1 P where y D i xi =k. Here u i is assumed to be strictly increasing and concave in xi and strictly decreasing and convex in y. Note that the only constraint on xi is xi ½ 0. The maximum occurs at the stationary point where @u i .xi ; y/ 1 X @u j .x j ; y/ n C D 0; i D 1; : : : ; n (9.4) @ xi k jD1 @y These equations give the socially optimal demands, say x1 ; : : : ; x n . Ł Ł Now suppose user i is presented with a price 1 X @u j .x j ; y/ n Ł pE D (9.5) k jD1 @y where because of the assumption that u j is decreasing in y, we have p E > 0. This price represents the marginal decrease in social welfare due to congestion by a marginal increase in usage. The sufﬁx E reminds us that we are pricing the externality. So user i is faced with the problem ð Ł maximize u i .xi ; y/ p E xi (9.6) xi ½0 He solves this where 1 X @u j .x j ; y/ n Ł @u i 1 @u i @u i 1 @u i C pE D C C D0 (9.7) @ xi k @y @ xi k @y k jD1 @y Now if n is large, it is reasonable to suppose that þ þ þ þ þ 1 @u i .xi ; y/ þ þ 1 X @u .x ; y/ þ n þ þ þ−þ j j þ þk þ þ (9.8) @y þ k jD1 @y þ Then (9.7) is approximately the same as (9.4), and so is solved by xi D xiŁ . Thus, individual maximization of net beneﬁt induces the socially optimal solution. Note that in solving (9.7), user i regards all other users’ demands as ﬁxed. Thus x1 ; : : : ; x n is a Nash equilibrium. That is, user i has no incentive to do other than choose Ł Ł xi D xi Ł , provided x D x Ł , for all j 6D i. j j Suppose the demand of each individual user is small. Then we might expect congestion prices to converge to optimal price under a tatonnement procedure having the following re- peated steps: (a) the network determines p E from (9.5) and communicates it to the users; (b) each user i solves (9.6) to determine a new xiŁ , assuming y is insensitive of his choice of xiŁ . Note that if the network is to solve (9.5) then it needs to know the users’ utility functions. This may be difﬁcult in practice. What the network might actually do is to vary p E until it ﬁnds an equilibrium at which no users wish to increase or decrease their demands. Similarly, we might wonder how user i can solve (9.6) without knowing the value of y. The simple answer is that u i .xi ; y/ is actually a function of the form u i .xi ; D.y//, where D is the value of the congestion for a given y. So user i needs only observe the value of the congestion caused by y, rather than y itself. This value of D is used when solving locally (9.6). In the following sections, we discuss some important properties of congestion prices.
222 CONGESTION 9.1.1 A Condition for Capacity Expansion Thus far, we have imagined that the capacity is ﬁxed. Let us suppose that c.k/ is increasing and convex in k. The maximized social welfare is X n w.k/ D u j .x Ł ; y Ł / j c.k/ jD1 Investment is worthwhile if w0 .k/ > 0. We can compute, X @w dx Ł n @w dy i w0 .k/ D C c0 .k/ i D1 @ xiŁ dk @ y dk P Now since social welfare is maximized, @w=@ xiŁ D 0. Thus, with x Ł D j x Ł , y D x Ł =k, j we have X @u i @ y n x Ł X @u i n w0 .k/ D c0 .k/ D c0 .k/ i D1 @ y @k k 2 i D1 @ y Capacity expansion is worthwhile if w0 .k/ > 0, and from the above this is equivalent to p E x Ł > kc0 .k/ Thus, congestion prices may be used by the service provider as signals for deciding whether to expand or reduce the capacity of the network. 9.1.2 Incentive Compatibility As noted above, the network operator must know the utilities of the users if he is to compute the congestion price from (9.4). In particular, he must know the derivatives of their utility function, i.e. their sensitivities to degradation in performance due to congestion. Is there any reason to expect that users will be truthful in declaring these sensitivities? Clearly not. Users may adopt complex strategies in which their declarations are far from the truth. We investigate such incentive compatibility issues in Sections 9.4.3 and 9.4.4. 9.1.3 Extensions P The deﬁnition of the load y D i xi =k is natural for a single link network in which xi is an average ﬂow and k is the bandwidth of the link. In principle, congestion measures, such as delay and packet loss, can be directly determined given the statistics of the trafﬁc and the service discipline of the link. But is our model useful for more general situations, in which we desire to price dynamic parameters of the contract that are not average ﬂows, but quantities such as leaky bucket parameters? Take as an example trafﬁc contracts in which each source is policed by its peak rate h and the leaky bucket .²; þ/, where the values of h and ² are ﬁxed, and þ is dynamic. How should the network charge for þ? One could now let xi denote the amount of þ in contract i. Then the congestion price would be the marginal total decrease in the utilities of all users due to congestion when the þ in some contract is marginally increased. One may consider a contract as producing a worst-case trafﬁc or trafﬁc corresponding to a typical source policed with the contract parameters.
CONNECTION WITH FINITE CAPACITY CONSTRAINTS 223 A similar analysis holds for a network in which the trafﬁc of user i passes through a number of links, say `1 ; : : : ; `m . In this case, u i depends upon the congestion at each of the links, and hence is a function u i .xi ; y`1 ;P : ; y`m /, where, summing over j such that user :: j uses link `, the load on link ` is y` D j: j2` x j =k` . Hence, if we deﬁne the congestion price p` at link ` to be E 1 X @u i .xiŁ ; y`1 ; : : : ; y`m / n p` D E (9.9) k` i D1 @ y` then the same global optimization problem is solved by charging each user the sum of the congestion prices on the links that his trafﬁc uses. 9.2 Connection with ﬁnite capacity constraints Thus far, we have placed no constraint on the total amount of services provided. In previous chapters, we have considered problems in which there is a capacity constraint, and the problem of maximizing social welfare takes the form X n X n maximize u i .xi /; subject to xi Ä C (9.10) fx1 ;:::;x n ½0g i D1 i D1 Recall that the problem of maximizing social welfare can be decentralized by presenting user i with a price ½C , where ½C is the shadow price of the constraint. Should one think of ½C as a congestion price? It is certainly true that when xi increases there is a reduction in the amount of resource that remains for the other users, and so an increase in xi negatively impacts the beneﬁts they obtain. Nonetheless, we believe it is best to reserve the terminology of ‘congestion price’ for circumstances in which xi appears explicitly in the utility of the other users, and there is no hard capacity constraint. It is still interesting to observe a close connection between the models. For purposes of illustration, consider a series of problems indexed by m D 1; 2; : : : , for which the utility of user i is u i .xi ; y/ D ai log xi D .m/ .y/xi . The interpretation of D .m/ .y/ is of the average amount of congestion cost incurred by user i for every unit of ﬂow he sends to the network. For instance, it may be average delay suffered by every packet sent. Thus, D .m/ .y/xi represents the (average) congestion cost suffered this user when transmitting at total rate xi . The net utility of the user is the utility of transmitting at rate xi reduced by the cost due to performance degradation. Note that both terms must be measured in the same units. Now the problem of maximizing social welfare is Xh n i maximize ai log xi D .m/ .y/xi fx1 ;:::;x n ½0g i D1 P where y D i xi . Suppose the congestion cost is D .m/ .y/ D 1=[m.C y/]. Note that D .m/ .C/ D 1, but for any y < C, D .m/ .y/ ! 0 as m ! 1. The idea here is that the congestion price is negligible when y < C, but tends to inﬁnity as y approaches C. Each curve becomes steeper as m grows. A physical interpretation is that as m increases the trafﬁc in each ﬂow becomes less random, tending to a constant ﬂow with the same rate, and congestion phenomena tend to appear rather suddenly as y approaches C. For this model the congestion price is p E D 1=m.C y Ł /2 where y Ł depends on m. P Some algebra shows that as m ! 1, y Ł ! C and p E ! i ai =C D ½C , where ½C is
224 CONGESTION simply the shadow price of the constraint in (9.10) when we put u i .xi / D ai log xi . Hence, one can think of the congestion cost as penalizing violation of a ﬂow feasibility constraint. Note that for any ﬁnite m we have y Ł < C, so the capacity constraint is not active. This is what often happens in problems with both congestion costs and capacity constraints. If the congestion cost grows very large before the capacity constraint in reached, then the capacity constraint is not active at the solution point. 9.3 Models in which users share congested resources In this section we present several models of congestion, and illustrate some ways that the social welfare maximization problem can be solved using congestion prices. 9.3.1 A Delay Model for a M/M/1 Queue An important version of the model in Section 9.1 is one in which there is explicit congestion cost, and the utility function of user i takes the form u i .xi ; y/ D vi .xi / i D.y/x i (9.11) Here, i D.y/xi is a congestion cost and i parameterizes the sensitivity of user i to congestion. For example, this congestion cost might arise as the product of xi and the average delay experienced by a packet belonging to user i when packets are served at a M=M=1 queue. Assuming service rate 1 and Poisson arrivals at rates x1 ; : : : ; x n , the average delay in the queue is 1=.1 y/, so we have 1 i D.y/x i D i xi ; yÄ1 1 y Note that vi .xi / increases in xi , and D.y/ increases in x j , for all j. The social welfare is Xð n Ł vi .xi / i D.y/x i i D1 and this is maximized by choosing x1 ; : : : ; x n to satisfy @vi @ D.y/ X n i D.y/ jxj D0 (9.12) @ xi @ y jD1 Denote the solution point as x1 ; : : : ; x n . The same point can be reached if user i is charged Ł Ł the congestion price given in (9.5), namely, þ Xn @ D.y/ þþ Ł pE D jxj @ y þ yDy Ł jD1 Note that p E is just the extra cost suffered by all users due to a marginal increase in user i’s demand. Customer i seeks to maximize his net beneﬁt of vi .xi / i D.y/x i p E xi under the assumption that he is a small participant and so his choice of xi does not affect p E or D. Taking the partial derivative of the above with respect to xi once again leads to (9.12), and we see that use of this congestion price maximizes social welfare.
MODELS IN WHICH USERS SHARE CONGESTED RESOURCES 225 9.3.2 Services Differentiated by Congestion Level Thus far, we have simpliﬁed our discussion by supposing that users buy only one service. However, the ideas extend to models with more than one service. The following is an interesting example. Suppose a service is sold in two versions. The services are perfect substitutes except that they differ in the levels of congestion present. The problem of maximizing social welfare takes the form Xh n i maximize vi .x1 C x2 / i i i D1 .y1 /x 1 i i D2 .y2 /x 2 i (9.13) fx1 ;x 2 ½0; i D1;:::;ng i D1 i i P where yt D i xti is the total load carried in version t and the congestion cost is of the same form as in (9.11). This has similarities with the model for ‘time-of-day pricing’ discussed in Section 8.4.1. In that model, the versions of the service correspond to peak and off-peak periods and one has constraints yt Ä Ct , t D 1; 2. As in the previous section, the problem can be decentralized by pricing congestion. User i should be faced with the problem h i maximize vi .x1 C x2 / i i i D1 .y1 /x 1 i i D2 .y2 /x 2 i i p1 x1 p2 x2 i (9.14) fx1 ;x 2 ½0g i i P where pt D @ Dt .y/=@ y i i xti is evaluated for the optimal fx1 ; x2 : i D 1; : : : ; ng. As i i above, the users treat D1 .y1 / and D2 .y2 / as ﬁxed. It is easy to see that the user problem i i is solved by taking either x1 D 0 or x2 D 0. As we see in our discussion of Paris Metro Pricing in Section 10.8.1 it can sometimes be economically efﬁcient to divide capacity in the manner above, so that users buy versions of the service that are best matched to their sensitivities to congestion. In the differentiated services IP network architecture, described in Section 3.3.7, different versions of the service (say, bronze, silver and gold) are given different priorities by the network. We can model that idea here, by imagining that version 1 receives higher priority service than version 2, and so D2 depends upon y1 and y2 , but D1 depends only upon y1 . The congestion prices are now @ D1 .y1 / X i @ D2 .y1 ; y2 / X i p1 D i x1 C i x2 @ y1 i @ y1 i @ D2 .y1 ; y2 / X i p2 D i x2 @ y2 i Again, the right-hand sides are to be evaluated at the optimal fx1 ; x2 : i D 1; : : : ; ng. The i i partial derivatives can be calculated if the functions D1 and D2 are known explicitly, or estimated using on-line measurements. As we see in Section 9.4, we might also create the same rate of charges using sample path shadow prices. The ideas of Section 9.4.2 could be generalized to the model of this section. This approaches avoids the need for performance models. 9.3.3 A Blocking Model This model shows how congestion prices can be used when congestion occurs because of blocking, i.e. when users are refused service. Blocking typically occurs because the call admission algorithm detects that there are not enough resources for new calls to be accepted.
226 CONGESTION See the discussion in Section 14.4. Suppose that there are n users and m types of calls. User i produces calls of type j at rate gij , j D 1; : : : ; m. A call type is differentiated in terms of its duration and the amount of resources that need to be reserved at the time the call is set up. The problem of the social planner is to choose the rates at which the users produce calls of the different types so as to maximize a social welfare function given by X n W D u i .g1 ; : : : ; gm I B1 ; : : : ; Bm / i i i D1 where B j D B j .g1 ; : : : ; gm / is the blocking probability for a call of type j and g j D Pn i i D1 g j is total arrival rate of calls of type j. Note that the blocking probability for calls of type j depends quite generally upon all the arrival rates of calls. Thus, we might model circumstances in which certain types of call have bandwidth reserved for them, or they are given priority. Blocking probabilities have interesting properties when calls are routed through a network and calls of the same type follow the same route. Increasing the rate of type i calls will deﬁnitely increase the blocking probability of the same call type, but may decrease the blocking probability of another type. This occurs because increasing blocking of calls sharing common links releases capacity in other parts of the network otherwise used by the blocked calls, and hence makes it easier for calls that would otherwise block to go through. We would like to know if social welfare can be maximized by prices. Can the social planner post prices for each of the call types, so that when customers do local optimizations, they end up choosing arrival rates that solve the social welfare maximization problem? At the social welfare optimum @W @u i X X @u k @ B` n m D i C D 0; 1Äi Än; 1Ä j Ä m @g ij @g j kD1 `D1 @ B` @g ij Pn Since B` depends upon g ij only through the sum g j D i D1 g ij , the above condition becomes @u i X X @u k @ B` n m C D 0; 1Äi Än; 1Ä j Äm (9.15) @g ij kD1 `D1 @ B` @g j Let w1 ; : : : ; wm be the prices charged to the customers for the calls that are accepted (i.e. not blocked), which depend only upon the call type. Then customer i will choose arrival rates that solve his local optimization problem X m maximize u i .g1 ; : : : ; gm I B1 ; : : : ; Bm / i i wk gk .1 i Bk / (9.16) g1 ;:::;gm i i kD1 where the values of the blocking probabilities Bk are those which are observed for the current operating point of the link. They are considered as given (measured). This is an important assumption which leads to the above deﬁnition of the local optimization problem. If, instead, users have knowledge of the derivatives of the blocking probabilities with respect to their arrival rates then this leads to a different optimization problem, in which such prices might not exist. In any case, if the size of the system is large compared to individual users, then it is a reasonable approximation that a single user cannot have a signiﬁcant effect on the blocking that takes place. We made a similar assumption in (9.8).
CONGESTION PRICES COMPUTED ON SAMPLE PATHS 227 User i is faced with solving (9.16). Users choose arrival rates to satisfy @u i w j .1 Bj/ D 0 ; 1Ä j Äm; 1Äi Än (9.17) @g ij Observe now that, if we choose the prices wŁ so that j X X @u k @ B` n m wŁ D j .1 Bj/ 1 ; 1Ä j Äm (9.18) kD1 `D1 @ B` @g j we are guaranteed that the global conditions (9.15) and the local conditions (9.17) are equivalent, and hence the arrival rates that maximize social welfare are also an equilibrium for the system of prices (9.18). Note that wŁ is a congestion price, in the sense that a j customer pays the rest of the customers (including himself) for the marginal decrease of their utility because of the increase of blocking that is caused when he increases the rate of requests for calls of type j. If we are to use (9.18) to compute the wŁ , we need to know how the blocking j probabilities vary with arrival rates. These values of @ B` =@g j might be obtained through more sophisticated modelling or by measurement. We also need explicit knowledge of the utility functions of the customers so that we can compute @u k =@ B` . Perhaps the customers of the network fall into a small number of classes, for which the utilities are known. If this is so, then the network operator can compute prices once he knows the number of users in each class. 9.4 Congestion prices computed on sample paths To compute the congestion price deﬁned in (9.5), we need to take derivatives of the utility functions of the users. There are two practical problems. First, to take derivatives, one must know the explicit form of the utilities. Secondly, the performance of a network is measured in some average sense, such as average delay, average throughput, or percentage of blocked calls. Hence, to compute a price in an actual situation, one must estimate such quantities, estimate their derivatives, and then charge each user a price that is deﬁned on a per unit of usage xi . Such a process can be lengthy and inaccurate. Let us look at a different approach. Instead of constructing a deterministic price that reﬂects the derivative of some average quantity, one may construct ﬂuctuating prices that capture temporal congestion effects, and which result in the same average price. For instance, if the quantities xi and y introduced in the previous sections are average ﬂows of packets, it may be sensible to charge each packet individually for the exact amount of cost its existence imposes on the rest of the packets in the system while this packet travels through the network. Then one may expect that, although each packet is charged a different amount, in a reasonably large time window the source of the packets will see the same average congestion price as is given in (9.5). Such prices are computed on a sample path rather than on an average basis. It turns out that such price computation has important practical implementation advantages. There is a possible problem with such pricing schemes on the ‘supply’ side. Who collects the charges? If it is the network provider then he has an incentive to increase congestion, perhaps by under-investing in capacity. To eliminate this possibility, there must be competition in supply. Competition induces social welfare maximization, which has been our objective throughout this chapter.
228 CONGESTION Sections 9.4.1–9.4.4 concern congestion charges that can be implemented as a per-packet charge. We begin with a model of a congested system in which the social welfare is a function of the rate of packet loss. In Section 9.4.2 social welfare is a function of packet delay. In both cases, the congestion charge is computed on a sample path basis. 9.4.1 A Loss Model Suppose n users produce streams of packets as Poisson processes of rates x1 ; : : : ; x n . Time is slotted into unit length slots, so that in any given slot the number of packets that arrive from stream i is distributed as a Poisson random variable with mean xi . Suppose that exactly C packets can be served in each slot. If more than C packets arrive then those in excess of C are lost. The network desires to maximize a social welfare function P P Ð i u i .x i / c i xi P Ð where c i x i is the rate of cost due to lost packets. For simplicity, assume that each lost packet costs one unit. Then c is the expected number of packetsP are lost per slot. The that Ð maximum is achieved when xi is chosen such that u i .xi / D c00 i xi . We explain how the social welfare optimum can be obtained in a decentralized way. We begin by computing the value of c0 . Let the random variable X denote the total number of P P packets that arrive during a slot. If the mean of X increases from i xi to i xi C Ž, the P Ð cost of lost packets increases by about c0 i x i Ž. This is equal to the extra losses that would be seen if an additional independent stream of packets were to arrive as a Poisson process of rate Ž. As Ž is assumed to be extremely small, the probability of a loss from this stream within any given slot is just Ž P.X ½ C/, i.e. the probability that an arrival occurs in this small rate-Ž stream times the probability that this arrival ﬁnds at Ð P least C packets from the other streams have also arrived in the same slot. Thus, c0 i x i D P.X ½ C/. Notice that the loss probability is P.X > C/, which is less. Suppose the following charging scheme is adopted. A unit of charge (or mark) is sent to user i whenever a packet in stream i is lost, or a packet in stream i is not lost, but had it not been present then some other packet would not have been lost. In other words, whenever the number of packets in a slot exceeds C, each packet that arrives in that slot generates a charge mark to the user to whose stream it belongs. This is illustrated in Figure 9.1. To compute the expected number of charge marks sent to user i per slot, think of the Poisson process of rate xi as the superposition of N independent streams, each of rate Ž D xi =N . Focus on one of these streams and observe that a packet from this stream produces a charge mark whenever the number of packets received from the other streams is at least C. Thus, the probability that this stream produces a charge mark is about arriving capacity load 1 time sample path shadow price 0 Figure 9.1 Sample path shadow price. A packet incurs a charge of 1 whenever it is lost, or if it had not been present another packet would not have been lost.
CONGESTION PRICES COMPUTED ON SAMPLE PATHS 229 P Ž P.Y ½ C/, where Y is a Poisson random variable with mean j xj Ž. Thus, the expected number of charge marks returned to user i per slot is N Ž P.Y ½ C/. However, N is arbitrary, so let N ! 1. This gives N Ž P.Y ½ C/ ! xi P.X ½ C/, the expected number of charge marks sent to user i per slot. Note that this is greater than the loss rate of xi P.X > C/. User i seeks to maximize u i .xi / xi P.X ½ C/. As previously in this chapter, he treats P.X ½ C/ as a ﬁxed probability, which he is individually too small to affect by his choice of xi . Thus, to maximize his net beneﬁt he chooses xi toP Ð u i .xi / P.X ½ C/ D 0. satisfy 0 0 .x / c0 From the paragraph above, this is the same as u i i i x i D 0, namely the condition for social welfare maximization. For simplicity, we have assumed that the congestion cost is the rate of the lost packets. If the cost of losing a packet is known, and the same for every packet and every user, then it makes sense to let the price per mark be the same to all users (‘anonymous’ or ‘nondiscriminatory’ in the economist’s language), and equal to the cost of losing a packet. More generally, however, the cost of losing a packet (through loss or delay) may be different for different users, and known only to the users. What now are the properties of an equilibrium? On the basis of present research, the answer is unclear. Thus, we have described a decentralized charging scheme that achieves the social welfare optimum. Note that it takes the general form of the congestion charges that we meet in this chapter: user i is charged for the losses that the presence of his packets inﬂict on other users. Because the charge is computed on-line, and sends a user a mark precisely when a small increase in capacity would reduce the rate of loss packets by one, we call this a sample path shadow price. Such a marking scheme is simple to implement in packet networks. A router can charge each packet that contributes to an overﬂow the monetary value of a mark (the cost of a packet loss). It then notiﬁes the source by sending back a mark; this is implemented by setting a special bit in the header of a packet that is travelling back to the destination. The user adjusts his rate of sending packets according to the rate of marks he receives, i.e. according to the rate of charge. Such schemes are analysed more in detail in Section 10.2. 9.4.2 A Congestion Model with Delay As above, suppose n users produce streams of packets as Poisson processes of rates x1 ; : : : ; x n . These are queued and served by a single server. Suppose all packets have service time 1. We model the system as a M=D=1 queue. Suppose user i has a net beneﬁt of the form P Á vi .xi / xi D j xj where D is the queueing delay of an average packet. Social welfare is Xh P Ái vi .xi / xi D j xj (9.19) i and is maximized where P Á P Á P Á vi0 .xi / D j xj j x j D0 j xj D 0 (9.20) We can calculate a sample path shadow price as follows. For each given packet that passes through the system we count the number of packets whose queueing delay would
230 CONGESTION have been one unit less if the given packet had not been present. Note that this equals the number of packets that arrive after the given packet and are served during the same busy period. Although this number is not known until some time after the given packet has left the system, it is eventually known. User i receives this count for each of his packets, as a congestion signal that reﬂects the effect that his packet has on increasing the delay of other packets. Suppose the expected number of packets that arrive after any given packet and are served in the same busy period is Y . User i can be charged a congestion price xi Y and presented with the problem ð Ł maximize vi .xi / xi D xi Y (9.21) xi Suppose user i is sufﬁciently small that neither D or Y changes appreciably with xi . As in the previous section, we may consider a small increase in ﬂow at rate Ž and argue that the P increase in rate of delay charge is ŽY D Ž D 0 .y/, so giving D 0 .y/ D Y , where y D j x j . Thus when users are subject to this form of sample path congestion charging the solution to (9.21) occurs where (9.20) holds, and so the social welfare maximum in (9.19) can be achieved by users individually optimizing their net beneﬁts in (9.21). Many of these ideas for constructing sample path congestion prices can be extended to the congestion charging of the differentiated services discussed in Section 3.3.7. 9.4.3 Bidding for Priority Suppose that n packets are queued at aP router. It is desired to schedule the packets to minimize a cost function of the form Ł i ci Di , where Di is the delay in the system experienced by packet i. This is done by the ‘c¼-rule’, which schedules packets in decreasing order of ciŁ =di , where di is the amount of time it takes to serve packet i. However, suppose the waiting costs ciŁ are unknown to the router. How can it ask the packets for these values and ensure that truthful answers are obtained? Suppose each packet declares a ci and packets are then served in decreasing order of P ci =di . Packet i is charged di c j , where the sum is taken over all j such that c j =d j < ci =di . Thus, the charge is the extra delay charge that packet i imposes on those packets which come behind it. The incentive issue is this. The true cost, ciŁ , is only known to packet i. It can declare any cost ci . However, if it declares a cost different from ciŁ , its total cost (delay cost plus charge) is greater than if it declares ci D ciŁ . That is, the scheme is incentive compatible. To see this, suppose packet i declares ci , with ci < ciŁ . If it were to increase this by some small Ž it might swap places with the packet immediately ahead of it, say packet j. It would save ciŁ d j in delay cost, but pay an extra charge of c j di . So the swap is to packet i’s advantage if ciŁ d j > c j di . Since we have assumed that packet j swaps positions with packet i, we must have .ci C Ž/d j > c j di , and if ciŁ > ci C Ž this implies ciŁ d j > c j di . Thus ci should not be declared any less than ciŁ . A similar argument shows that ci should not be declared any more than cŁ . j 9.4.4 Smart Markets The idea of a smart market is that of a bandwidth auction that occurs time slot by time slot. It is more of theoretical than practical interest, but provides another illustration of a way that congestion charges can be computed on a sample path basis.
AN INCENTIVE COMPATIBLE MODEL FOR CONGESTION PRICING 231 p(t) $10 $8 price = $5 $5 $1 2 packets per time slot Figure 9.2 In a smart market bandwidth auction the packets bid for slots and pay the price of the highest bid of a packet not accepted. The price p.t/ ﬂuctuates as a function of the competition in each slot. Consider, as an example, a resource that can carry at most two packets in each time slot. This capacity is to be auctioned amongst several competing users. In a given time slot, all competing users state the amounts they would be willing to pay for the network to carry one of their packets. For example, four users might bid $1, $5, $8 and $10. In this case, the price would be set at $5 and the packets of the two users who bid $8 and $10 would be carried, (see Figure 9.2). The idea is that if one more unit of capacity had been available then additional revenue of $5 could have been obtained. Thus, $5 is the ‘sample-path shadow price’ of the resource. It is also a congestion charge, in the sense that accepting the bid of any given user decreases the total utility that could otherwise be obtained by all other users if that user’s bid were not accepted, and this decrease equals the value of the highest unaccepted bid. It can be shown that this auction mechanism is incentive compatible, in that each user does best for himself by bidding the amount that equals his true utility for bandwidth (similarly as in the Vickrey auction, that we discuss in Section 14.1.2). This is a standard property of ‘second-price’ auctions, in which users do not pay their own bids, but pay a charge that is determined by the bids of the other users. One can think of practical schemes in which the user limits his total bill by stating in advance the amount he is prepared to pay (perhaps by prepayment). The network decrements this amount as the user’s trafﬁc passes through successive routers. When the balance reaches 0, the user’s packets become ‘best-effort’. If the user still has a balance left at the end, he receives credits. 9.5 An incentive compatible model for congestion pricing In concluding this chapter we give a model for congestion pricing that is even more general than in Section 9.1. It uses a form of Vickrey–Clarke–Groves mechanism to provides incentives to the users to choose socially optimal levels of demand and to reveal their true valuations of the service. P Suppose that y D x Ł maximizes the social welfare, i u i .y/, for y 2 A. Congestion is modelled by having u i depend upon the complete vector y. Suppose user i demands xi . Let x be the vector whose ith component is xi and whose jth component is x Ł , for each j j 6D i. Let user i be charged X X pi .xi / D max u j .y/ u j .x/ (9.22) y2A j6Di j6Di We call view this a ‘congestion charge’ because it represents the greatest increase in beneﬁt that other users might obtain if they were allowed freely to choose x, as against having to take the value of xi that has been chosen by user i, and to take x j D x Ł , for j 6D i. In other j words, pi .xi / measures the reduction in the beneﬁt obtained by other users because user
232 CONGESTION i is present and has chosen xi , and the other components have been ﬁxed at their social welfare optimal values. A property of this method of charging is that it makes the social welfare optimal point, x Ł , a Nash equilibrium, as deﬁned at the start of Section 6.4.1. To see this, suppose that x j D x Ł for j 6D i, and that user i seeks to maximize his consumer surplus by choice of j xi . He obtains " ( )# ð Ł X X max u i .x/ pi .xi / D max u i .x/ max u j .y/ u j .x/ xi xi y2A j6Di j6Di X X D max u j .x/ max u j .y/ xi y2A j j6Di X X D u j .x Ł / max u j .y/ (9.23) y2A j j6Di which is achieved by taking xi D xiŁ . Let us write the charge pi .xi / in one other way. Fix i. Let x 0 be the vector whose ith component is 0 and whose jth component is x Ł , for all j 6D i. Then j h P P i pi .xi / D max y2A j6Di u j .y/ j6Di u j .x 0 / hP P i (9.24) j6Di u j .x 0/ C j6Di u j .x/ The ﬁrst term is ﬁxed and is the opportunity cost to users j, j 6D i, of being forced to take x j D x Ł , even if user i creates no negative externality (xi D 0). The second term is the j extra congestion cost to the rest of the users when user i consumes xi . In the above we have assumed that the users’ utility functions are all known. Suppose users are asked to state their utility functions. Then truthful revelation of utility functions is also a Nash equilibrium strategy for all users. For suppose user i may be untruthful, † stating say u i , while all other users state their true utility functions, u j , j 6D i. The network allocates bandwidth on the basis of the utility functions that are revealed. User i is allocated bandwidth xiŁ , where x Ł maximizes the supposed social welfare function: † P u i .xi / C j6Di u j .x j /. User i is charged using (9.22). Under these conditions there is an incentive for user i to be truth-telling. This is because hisP surplus is (9.23), and this is maximized when x Ł is chosen by the network to maximize j u j .x j /, which will happen † if he states u i D u i . Thus, truthful statement of utility functions is a Nash equilibrium in a game in which users may lie about their utility functions. 9.6 Further reading The concepts of congestion pricing with applications to the Internet are nicely developed by MacKie-Mason and Varian (1994, 1995), who also proposed the idea of using smart markets in the networking context. Congestion pricing with priorities is addressed by Wilson (1990) and Mendelson and Whang (1990). Another interesting paper on concepts of congestion pricing is that of Gupta, Stahl and Whinston (1997). Congestion is a negative externality. The economics of externalities are studied in Chapter 24 of Varian (1992). Congestion has been always an important topic in transportation. An interesting web site that has references to congestion topics from this point of view is that of Metro Dynamics (2002). In Section 9.2 the congestion model with delay cost of the M=M=1 queue is taken from Walrand and Varaiya (2000). The chapter on economics is particularly worth reading. The
FURTHER READING 233 blocking model in Section 9.3.3 is from Courcoubetis and Reiman (1999). For further discussion of a delay-based sample path congestion charge, as in Section 9.4.2, see Key, Massoulie and Shapiro (2002). The model of bidding for priority in Section 9.4.3 is from private discussions with Pravin Varaiya.