The Design of an Optimal Pricing Scheme for ATM IntegratedServices Networks
Skip other details (including permanent urls, DOI, citation information)This work is protected by copyright and may be linked to without seeking permission. Permission must be received for subsequent distribution in print or electronically. Please contact mpubhelp@umich.edu for more information. :
For more information, read Michigan Publishing's access and usage policy.
Presented at MIT Workshop on Internet Economics March 1995
Abstract
ATM integratedservices networks are expected to dominate information carriage in the next 20 years. While there are extensive studies of the engineering problems of designing ATM integratedservices networks, related economic problems, such as how to price services offered by this type of network, have not been fully discussed.
In this paper, we formulate the problem of pricing and capacity investment for an ATM integratedservices network with timevarying demand. Based on an optimal control model formulation, we develop a 3stage procedure to determine the optimal amount of capacity and the optimal price schedule. We show that pricing a network service is similar to pricing a tangible product, except that the marginal cost of producing the product is replaced by the opportunity cost of providing the service, which includes both the opportunity cost of reserving and the opportunity cost of using network capacity.
1. Introduction
As a result of the rapid development of cellswitching technology, it is becoming increasingly efficient to provide different telecommunication services through one integratedservices network instead of multiple singleservice networks. It is expected that in the next twenty years, most of today's singleservice networks, such as telephone networks for voice communications, cable networks for broadcasting video, and the internet for data transfer, will be upgraded to Asynchronous Transfer Mode (ATM) integratedservices networks. In an ATM integratedservices network, any piece of information, regardless if it is voice, image, or text, is organized as a stream of fixedlength packets (i.e. cells) and transmitted over the network. By controlling the cell transmission rate and cell delay distribution of each stream, the network can use a single ATM cell transmission technology to provide a variety of transmission services, such as telephony, video, and file transfer.
While integrating multiple services into a single network generates economies of scope, heterogeneous services complicate pricing decisions. For example, users watching HDTV through the network require up to hundreds of thousands of cells to be transmitted per second while users who make phone calls send/receive only a couple of hundred cells per second; telnet users require mean cell transmission delay to be kept below a few tens of milliseconds but email senders will tolerate longer delay; web browsing generates a very bursty cell stream while constantbitrate file transfer results in a smooth cell stream; to carry a voice conversation with a decent quality, under certain encoding schemes, cell loss rate, i.e. the percentage of cells that are allowed to miss a maximum delay bound (usually 3050 ms for voice conversation), should not exceed 5%, while to carry video service, cell loss rate should be kept much lower ([Peha,91]). In all these cases, there are great differences among the services offered by the network; therefore, one might ask whether the prices of these service should also differ, and if so, how?
There is some literature on how to price a network that offers heterogeneous services. Cocchi et al. ( [Cocchi,93]) study the pricing of a single network which provides multiple services at different performance levels. They give a very impressive example which shows that in comparison with flatrate pricing for all services, a price schedule based on performance objectives can enable every customer to derive a higher surplus from the service, and at the same time, generate greater profits for the service provider. Dewan, Whang and Mendelson et al. ( [Dewan,90] and [Whang,90]) developed a clientserver queuing model in which the network is formulated as a server (or servers) with limited capacity, and consumers are treated as clients who demand the same service from the server but vary in both willingness to pay for the service and tolerance for delay. Based on that model, they discussed the optimal pricing policy and capacity investment strategy. MacKieMason and Varian ([MacKieMason, 94]) suggest a spotprice model for internet pricing. In their model, every internet packet is marked with the consumer's willingness to pay for sending it. The network always transmits packets with higher willingness to pay and drops packets with lower willingness to pay. The network charges a spot price that equals the lowest willingness to pay among all packets sent during each short period. The major benefit of this approach is that it provides consumers with an incentive to reveal their true willingness to pay, and based on that information, the network can resolve capacity contention in transmitting packets in a way that maximizes social welfare.
In the optimal pricing models mentioned above, the fact that different applications may have different performance objectives was usually not considered. Dewan, Whang and Mendelson's work ([Dewan,90], [Whang,90]) assumes that the consumer's willingness to pay depends only on expected mean delay, and MackieMason ([MackieMason,93]) assumes that consumers do not care about delay—only whether or not their packets are eventually transmitted. There is no way, for example, to accommodate a service that would impose a maximum delay limit. These formulations also do not consider the case of heterogeneous data rate and burstiness. Consequently, pricing policies developed in these studies cannot be applied in ATM integratedservices networks in which services differ from each other in terms of performance objectives and traffic pattern (data rate and burstiness). Some of these factors are considered in the paper by Cocchi et al. ([Cocchi,93]), however, it does not discuss procedures for designing an optimal pricing scheme.
In this paper, we examine the optimal pricing problem for ATM integratedservices networks. In our approach, the optimal price for each service is determined from the demand elasticity for the service, as well as the opportunity cost of providing the service. The opportunity cost is determined by the required performance objectives and traffic pattern of each service. Since demand for network services usually changes with time of day, we will develop a timevarying price schedule (i.e. price as a function of time of day) instead of giving a single price for each service.
The rest of our paper is organized as follows: in section 2, we present service models for different services offered by an ATM integratedservices network. In section 3, we formulate an optimal pricing model and discuss how to solve it using a 3stage procedure. We discuss the procedure in detail in section 4. Conclusions and future work are discussed in Section 5.
2. The Network Service Model
Network capacity is often subadditive, leading to conditions of natural monopoly for an integratedservices network operator. In the model that follows, we assume a single profitmaximizing monopolist operating the network. In this paper, we consider only a pointtopoint single link network. This frees us from network routing details and allows us to focus our attention on the economic principles for designing pricing policy. The capacity of that link is denoted as C_{T}, whose unit is the maximum number of cells that can be transmitted over the link per unit of time.
The network is used for providing multiple services. Quality of Service (QOS) is measured by the distribution of cell delay time, where lost cells are considered as being delayed infinitely. A service will be labeled as a "guaranteed" service if during each session, the network makes a commitment to meet some prespecified delay objectives. These guarantees are typically expressed in stochastic, not absolute terms, e.g. no more than 5% of the cells will be delayed for more than 30 ms; or the average delay will be less than 200 ms. If no such guarantee is made, the service is considered as besteffort service. Telephone calls, HDTV, and interactive games typically require some type of guaranteed service, while email is usually specified as a besteffort service.
Our pricing model considers both guaranteed services and besteffort service, which are discussed in the following subsections.
2.1 Service Model for Guaranteed Services
Guaranteed services differ from each other significantly in terms of performance objectives, traffic pattern (data rate and burstiness), and call duration distribution. For example, HDTV service has a much stricter performance objective and 500times higher mean data rate than telephone service. An HDTV session can take hours to complete, while telephone calls usually last only minutes. The transmission rate of the former (if the data stream is compressed) is also much burstier than that of the latter, which is typically not compressed.
In this paper, we assume the network offers N guaranteed services. Within the same service category i, (i=1), calls require the same performance objective, exhibit the same intercell arrival statistics, and have call duration drawn from the same distribution.
We assume the price for a call using guaranteed service is determined by service type i, call starting time, and service duration. For a call of service i which begins at time t, p_{i}(t) is the price that will be charged for each unit of time that the call lasts. A consumer will be charged a price equal to p_{i}(t) times the call duration if the call starts at time t. We shall also assume that for calls of a given service, call duration is independent of price.
Define λ_{i}[p_{i}(t),t] as the arrival rate of calls for service i given that the price of a call which starts at t will be p_{i}(t) throughout the call. [1]. Assume at any given price, p_{i}(t), and any given time t, call arrivals are Poisson, i.e. the number of calls arriving within any period is independent of the numbers of calls which arrived within previous periods. Note that we have also assumed no crosselasticity of demand between different services, which may not be realistic. We leave that enhancement for a future paper.
To meet guaranteed performance objectives, the network can only carry limited numbers of calls simultaneously. These numbers are determined by performance objectives and traffic patterns of each service. To avoid accepting more calls that it can handle, ATM integratedservices networks enforce an admission policy by which the network monitors the current network load and decides whether an incoming call should be admitted or rejected ([Peha,95]). This process is shown in Figure 2.1. We assume calls are not queued if they cannot be admitted immediately.
For each service i(i=1,N), we assume call duration is exponentially distributed with departure rate r_{i}. Define q_{i}(t) as the number of calls underway of service i at time t, and _{i}(t) as the expected value of q_{i}(t). Under the assumptions we made about call arrival. and departure processes, the rate of change of _{i} should follow:
=(1β_{i})λ_{i}(p_{i},t)r_{i} _{i}(t) i=1, N (21)
where β_{i} is the blocking probability.
Since both call arrival and departure are stochastic, unless the network has an infinite amount of capacity, there will always be a possibility of blocking calls. A high blocking probability gives consumers an unpleasant experience with the network and reduces the demand eventually, but a lower blocking probability also means more capacity will lay idle. From a network operator's perspective, the blocking probability should be kept at a desired level at which any marginal revenue increase from increasing demand by reducing blocking probability can no longer offset the marginal loss from letting more capacity lay idle. Values of desired blocking probability are usually determined during the longterm capacity investment decision. In the following, we will show how keeping blocking probability at the desired level will affect shortterm pricing decisions:
Suppose the network offers only one service; then the blocking probability at each time can be determined by:
where β is the blocking probability, H is the maximum number of calls that can be carried by the network, and is the product of call arrival rate and expected call duration.
Let be the blocking probability that the network operator desires to maintain. From (22), H can be uniquely determined by the desired blocking probability and the network load , i.e. H=d(,). In other words, to keep blocking probability at a desired level under given load , the network should be designed to carry H calls. This requirement can be translated into a demand for network capacity: define θ(H) as the amount of capacity needed to carry H calls, and α(,)=θ[d(,)]. α(,) can be. interpreted as the amount of capacity needed to keep blocking probability at when the network load is .
Since at each time, the network load is related to the expected number of calls in progress by , we can also express the amount of capacity needed as a function of expected number of calls in progress as: . A(,) increases with . A(,) is defined as the amount of capacity required to carry an average of calls with blocking probability . If capacity required exceeds total capacity C_{T}, the network either has to admit more calls than it can handle, thus failing to meet some QOS guarantee, or exceed the desired blocking probability.
At each time t, (t), the expected number of calls in progress is a function of previous and current prices. Therefore, in the short term, prices should be set such that the reserved capacity can never go above total capacity, i.e.:
A[(t),] ≤ C_{T} at all t (23)
(23) defines the "admissible region constraint" [2].
The definition of the admissible region constraint can be extended to a multiple services scenario, in which the reserved capacity is a function of the expected numbers of calls in progress for all services, which is shown below:
A[_{1} (t),.....,_{N}; _{1} (t),.....,_{N} (t) ≤ C_{T} (24)
2.2 Service Model for Besteffort Service
Given no performance guarantee, cells of besteffort service will be put in a buffer and transmitted only when there is remaining capacity after the needs of guaranteed services have been met. If there is not enough buffer space for all incoming cells, some of them will be dropped.
In our model, users of besteffort service are charged on a percell basis. We assume all cells of besteffort service share a buffer of size B_{s}. The willingness to pay for sending each cell is revealed to the network. At each time t, the network sets a cutoff price, p_{b}(t), which is a function of both current buffer occupancy and predicted willingness to pay values of future incoming cells. A cell will be accepted if and only if the willingness to pay for that cell is higher than p_{b}(t), and p_{b}(t) will also be the price charged for sending that cell. Accepted cells will be admitted into the buffer as long as the buffer is not full. Once admitted into the buffer, cells will eventually be transmitted according to a sequence dictated by some scheduling algorithm, such as firstcomefirstserve, or costbasedscheduling ([Peha,93]).
Assume at time t, the arrival process of cells of besteffort service is Poisson with expected value λ_{b}(0,t); the acceptance of cells is also Poisson with expected value λ_{b}[p_{b}(t),t]. Define s_{b}(t) as the instantaneous transmission rate of besteffort service at that time, then:
s_{b}(t)≤C_{T}  s[q_{1} (t), q_{2} (t),...,q_{N} (t)] (25)
where s[q_{1}(t), q_{2}(t),...,q_{N}(t)] is the instantaneous transmission rate of all guaranteed services, which is a function of numbers of calls in progress. Equation (25) implies the instantaneous transmission rate of besteffort service cannot exceed the total bandwidth left after transmitting all guaranteed services.
Under the assumptions: 1) accepted cells constitute a Poisson random process; 2) the instantaneous transmission rate depends on the bandwidth left by guaranteed services, which is also random; and 3) the buffer size is limited, there is a possibility that even accepted cells (i.e. cells with willingness to pay higher than the cutoff price) can be dropped because the buffer can become temporarily full. Define υ(t,Δt) as the number of cells actually admitted into the buffer during the interval [tt+Δt]; then the instantaneous admission rate can be defined as:
ο_{b}(t) is a random variable and we assume its expected value is _{b}(t), then
_{b}(t) ≤ λ_{i}[p_{b}(t),t] (27)
Define q_{b}(t) as the number of cells in the buffer at time t, then:
= ο_{b}(t)  s_{b}(t) (28)
and
s_{b} (t) ≤ q_{b} (t) ≤ B_{s} (29)
3. The Optimal Pricing Policy
In this section, we will discuss the profitmaximizing pricing policy for network operators. We formulate an optimal control model to derive the pricing policy, and discuss how to solve this model through a 3stage procedure.
3.1 The Optimal Pricing Model
Assume a network operator wants to maximize total profit over a period composed of multiple identical business cycles (such as days). The cycle length is T. Her rational behavior would be to choose a price schedule for each type of guaranteed service p_{i}(t), and besteffort service, p_{b}(t), and the amount of bandwidth C_{T} to maximize the following objective:
under constraints:
A[_{1}(t),.....,_{N}; _{1}(t),.....,_{N}(t)] ≤ C_{T} (33)
= ο_{b}(t)  s_{b}(t) (34)
when
q_{b}(t) = B_{s} ο_{b}(t) ≤ s_{b}(t) (35)
0 ≤ q_{b}(t) ≤ B_{s} (36)
s_{b}(t) ≤ C_{T}  s[q_{1} (t), q_{2} (t),..., q_{N} (t)] (37)
when
q_{b} (t) = 0 ο_{b} (t) ≥ s_{b} (t) (38)
q_{i}(0)=q_{i0}, i=1, N (39)
Interpretations of these constraints are the same as discussed in section 2, and definitions of variables can found in both section 2 and in the following list:
Variables of guaranteed services:
N  number of different services 
λ_{i}(p_{i},t) 
call arrival rate of service i at time t, when price is p_{i} 
p_{i}(t)  unit price for service i, as a function of call starting at time t 
r_{i}  call departure rate of service i 
q_{i}(t)  number of calls of service i in progress at time t 
expected value of q_{i}(t)  
s[q_{1}(t), q_{2}(t),...,q_{N}(t)]  total data rate of all guaranteed services at timet 
desired blocking probability for service i at time t 
Variables describing besteffort service:
q_{b}(t)  queue length of besteffort service at time t 
s_{b}(t)  cell transmission rate at time t 
λ_{b}[p_{b}(t),t] 
cell accepting rate, i.e. arrival rate of cells with willingness to pay higher than p_{b}(t) 
ο_{b}(t) 
admission rate of cells at time t 
expected value of ο_{b}[p_{b}(t), t] 

p_{b}(t) 
price for admitting one cell into the buffer at time t 
Other variables:
T 
duration of business cycle 
C_{T} 
total bandwidth 
K(C_{T}) 
amortization of capacity investment cost over one cycle 
B_{s} 
buffer size 
In (31), (1  β_{i}) λ_{i} (p_{i},t)dt is the expected number of calls of service i that will be admitted during the period [t,t+dt]. Multiplying this number by the unit price, p_{i}(t), and expected call duration, , yields the expected revenue from all calls of service i admitted in that interval. At time t, the network also charges a price for each cell of besteffort service that enters the buffer, and _{b}(t)dt is the expected number of cells that will enter the buffer at that time. Thus _{b}(t)p_{b}(t)dt is the expected revenue from besteffort service at t. The total expected profit is calculated by summing up expected revenue from all services, accumulated over all time in [0,T], minus the amortized capacity cost. At this point, we assume zero discount rate for simplicity.
3.2 The Solution: A 3stage Procedure
Though it would be ideal to solve the model defined in (31)  (38) directly to get the analytical form of the optimal pricing trajectory (p_{i}(t),p_{b}(t)) and the optimal amount of bandwidth (C_{T}), it is mathematically intractable. Therefore, we construct a threestage procedure to find a nearoptimal solution. At each stage, we will make some simplifying assumptions, or treat some variables as constants, and solve part of the problem. The solution obtained at one stage will be used either as an input to the next stage or as a feedback for modifying assumptions made in the previous stage. This process is iterated until prices stabilize at a nearoptimal level.
The 3stage procedure is defined as follows: at stage 1, we solve a longterm optimal investment problem to find the optimal amount of total bandwidth (C_{T}), as well as the desired blocking probability, _{i}(t), which we expect will vary with time of day. Using these values as inputs, we develop the optimal pricing policy at the second stage. The result shows that the optimal price for a service should be a function of the opportunity cost of providing that service. The opportunity cost is determined by both the service characteristics and the shadow prices of reserving/using network bandwidth. We give trial values to shadow prices and set up a price schedule for each guaranteed service accordingly. Based on these price schedules, the traffic load from guaranteed services can be determined. Under a given traffic load from guaranteed services, at the third stage, we formulate a more precise model to describe the cell flow of besteffort service at each moment. The spot price for besteffort service is then derived to maximize the revenue from besteffort service. From these spot prices, we can then decide the instantaneous value of using network bandwidth. This information is used as feedback to the second stage for adjusting the trial value of shadow prices we previously calculated, so the price schedule for guaranteed services can be refined. The process is iterated until both the price schedule for guaranteed services and the spot price for besteffort service stabilize.
In the next section, we will discuss the implementation details at each stage, and interpret the economic implications of our results.
4 Implementation of the 3stage Procedure
4.1 Stage 1: Optimal Investment
At this stage, we formulate and solve an optimization problem to determine the optimal amount of total bandwidth, C_{T}, and the desired blocking probability of each guaranteed service at each time, _{i}(t), i=1, N. The formulation of the problem is as follows:
Divide [0,T] into M time intervals, each lasting.w_{m}, (m=1,M). Take the average arrival rate as the arrival rate for all time during that interval. λ_{im} is determined by price p_{im}. We also assume that calls admitted during the interval [m2,m1] will have no influence on traffic load within the interval [m1,m]. _{im} is the blocking probability during the interval.[m1,m], which is a function of network loads within that interval.
At this stage we ignore blocking due to finite buffer space for besteffort traffic. Then the expected cell acceptance rate equals the expected cell admission rate, i.e. λ_{bm}(p_{bm})=_{bm}. In other words, all cells with willingness to pay higher than the cutoff price are assumed to be able to enter the buffer. To keep the queue length in the buffer reasonably short, we assume the expected cell admission rate equals the expected cell transmission rate, i.e. _{bm} = _{bm}. Consequently, λ_{bm}(p_{bm}) = _{bm}.
The network operator controls p_{im}, p_{bm}, and C_{T} to maximize total profit, i.e.:
s.t.
_{m} = A(_{im}, i=1, m, C_{T}),
where _{m} = (beta;_{1},.....β_{m})
(43)
where
[(1β_{im})_{im}, i=1, m] + λ_{bm} ≤ C_{T}, i=1, N (44)
This is an optimization problem with (N+1)M+1 controlling variables. It can be solved either by nonliner optimization techniques or generic algorithms such as simulated annealing. The resulting C_{t} and β_{im} will be considered as optimal values for the total amount of capacity and for blocking probability in each period.
Notice the solution we have obtained so far is not truly optimal because we have made several simplifications. One simplification is that we assume the traffic load in any period has no influence on the traffic load in succeeding periods. We have also ignored the fact that the arrival rate may change continuously over time within each period by using a single value λ_{im} as the arrival rate for all time in a period.[m1,m). Both simplifications will cause inaccuracy in our results. Interestingly, effects of these two simplifications depend on how we divide [0,T) into different intervals. If we divide [0,T) into longer intervals, i.e. w_{m} is larger, the effect of not considering the relationship between traffic load in different periods will be smaller and the effect of ignoring the change of arrival rate within a period is more serious. If we choose a smaller w_{m}, the effects will go in the opposite direction. Therefore, w_{m} should be chosen to minimize the total negative effect of these two simplifications.[3]
4.2 Stage 2: Optimal Pricing
We now allow the arrival rate to change continuously over time, consider the dependency of traffic load at different times, and derive the optimal pricing policy at this stage. We will still keep the assumption that for besteffort service, cell admission rate equals cell transmission rate at all times, and ignore blocking of besteffort traffic. As a result, λ_{b}(p_{b},t), the arrival rate of cells for which the willingness to pay is above the cutoff price p_{b}(t) at time t, is used both as the average rate of cell admission into the buffer and the average rate of cell transmission out of the buffer at time t tfor besteffort service in the problem formulation.
Given the amount of bandwidth (C_{T}) and optimal blocking probability (_{i}(t), i=1,N) calculated at stage 1, we can simplify the optimal pricing model defined in (31)  (39) as following:
subject to:
A[_{1} (t),.....,_{N} (t); _{1} (t),.....,_{N} (t)] ≤ C_{T} (47)
λ_{b}(p_{b},t) + [_{1} (t),..., _{n} (t)] ≤ C_{T} (48)
q_{i}(0) = q_{i0}, i=1, N (49)
We assume that. the optimal solution exists for this pricing model. The optimal solution to equation (45) through (49) must obey the following proposition, which yields the optimal pricing policy:
Proposition: The optimal pricing policy
Suppose p_{i}^{*}(t), p_{b}^{*}(t) are the optimal solutions to the pricing model defined in (44)(48), then:
(1) p_{i}^{*}(t) = h_{i}^{*}(t) and p_{b}^{*}(t) = *l_{2}(t)
if l_{2}(t) b 0 and h_{i}(t) b 0 i=1,N
(410)
or
(2) p_{i}^{*}(t) = h_{i}^{*}(t) and p_{b}^{*}(t) = p_{b}^{0}(t)
if l_{2}(t) = 0 and h_{i}(t) b 0 i=1,N
(411)
or
(3) p_{i}^{*}(t) = p_{i}^{0}(t) and p_{b}^{*}(t) = p_{b}^{0}(t)
if h_{i}(t) = 0 i=1,N
(412)
where: p_{i}^{0}(t) maximizes p_{i}(t)λ_{i}(p_{i},t), p_{b}^{0}(t) maximizes p_{b}(t)λ_{b}(p_{b},t),
l_{1}(t) is the Lagrangian multiplier of constraint (46), (414)
l_{2}(t) is the Lagrangian multiplier of constraint (47).
In Section 4.2.1 below, we discuss the economic implications of this policy. How to decide the optimal pricing schedule for guaranteed services based on the policy is discussed in Section 4.2.2.
4.2.1 Economic implications
The pricing policy shown in (49) is designed for situations in which the network capacity is tightly constrained. If the network operator prices services without considering capacity constraints, for guaranteed services, either the network can not meet performance requirements, or some services will experience a blocking rate beyond the designed value. For besteffort service, if the number of cells admitted exceeds the number of cells transmitted, the queue would grow without bound. Our proposition shows that under these scenarios, the network operator's optimal strategy is to attach an opportunity cost to each service (h_{i}(t) for guaranteed service i, and l_{2}(t) for best effort service), and price a network service in the same way as pricing a tangible product, except that the marginal production cost should be replaced by opportunity costs.
We now explain the rationale for using h_{i}(t) as the opportunity cost for providing guaranteed service i, and l_{2}(t) as the opportunity cost for providing besteffort service, starting by explaining the Lagrangian multipliers of the two capacity constraints. The economic implication of the Lagrangian multiplier of a resource constraint is the maximum value that can be derived from having one more unit of the constrained resource, i.e. the shadow price of consuming one unit of that resource. In our case, l_{1}(t), l_{2}(t) are shadow prices of reserving and using one unit of bandwidth, respectively. Since we measure the bandwidth in terms of the number of cells that can be sent per unit of time, at time t, when one cell of besteffort service is sent, one unit of bandwidth is consumed. Therefore, the unit opportunity cost for besteffort service at time t is just the shadow price of using one unit of bandwidth at that time, i.e. l_{2}(t).
To meet performance requirements for guaranteed services, the network needs to reserve some capacity each time a call is admitted. At each moment, part or all of reserved bandwidth will actually be used by guaranteed services. Consequently, the opportunity cost should include two components: the opportunity cost of reserving the bandwidth, and the opportunity cost of using it. In our formulation, at time t, the former equals the shadow price for reserving one unit of bandwidth, l_{1}(t), times the marginal increase of the amount of reserved bandwidth for admitting one more call, , and the latter equals the shadow price for using one unit of bandwidth, l_{2}(t), times the marginal increase of bandwidth usage which results from admitting one more call, . The total opportunity cost for a call is thus the sum of these two components, accumulated over all time. Since the service duration is an exponentiallydistributed random variable, the total cost, h_{1}(t), is estimated by taking mathematical expectation, using the distribution function of the call duration.().
Equation (410) is appropriate when the number of guaranteed calls that can be admitted while meeting performance requirements is still limited, but there is more than enough capacity to carry the cells from all guaranteed calls that are admitted, as well as all of the besteffort traffic that the network wants to carry. This situation might occur, for example, if the guaranteed calls are extremely bursty, or their performance requirements are extremely strict. i.e. λ_{b}(p_{b},t) + [_{1} (t),..., _{n} (t)] < C_{T}.
As a result, at time t, the shadow price of using the bandwidth, l_{2}(t), equals 0, and the optimal pricing policy should follow (410), i.e. the network operator should set price to maximize total revenue from besteffort service without considering the constraint on data rate.
Equation (411) specifies the pricing policy for the situation when there is an excessive amount of bandwidth. In this case, even if the network operator maximizes revenue without considering capacity constraints, she can still meet performance objectives for all services, keep blocking probability below the desired level, and have more transmission capacity for besteffort service than what is needed. As a result, both the opportunity costs for guaranteed services and the opportunity cost for besteffort service equal zero (i.e. h_{i}(t) = 0, l_{2}(t) = 0. This only happens when capacity is not constrained for both reservation and use for all time, or in other words, the capacity is over provisioned. Since we have assumed that the C_{T} was set at the optimal level in stage 1, this cannot occur.
4.2.2 The optimal pricing schedule for guaranteed services
As shown in (49), (410), the optimal price for guaranteed services depends on the ε_{i}, which is the demand elasticity, which reflects traffic characteristic and performance requirements, as well as l_{1}(t), l_{2}(t), the shadow prices for reserving and using bandwidth, respectively, i.e. :
where
To find p_{i}(t), values of l_{1}(t), l_{2}(t) need to be determined. At this point, we assume the values of l_{2}(t) have been estimated and given as . (This prior estimation will be modified by the feedback from stage 3). We then set l_{1}(t) to the trial value ,and construct the following procedure to find the optimal value for p_{i}(t), as well as to modify the estimate of l_{1}(t):

Calculate the optimal pricing schedule for guaranteed services by :

The call arrival rate of guaranteed services i at time t, is then . Given and the total amount of bandwidth, C_{T}, then the expected number of calls in progress,., and the blocking probability, , can be determined.

If l_{1}(t) is underestimated, will be lower than its optimal value, so call arrivals will be higher than the optimal level, which leads to the situation that blocking probability is higher than the desired level, i.e. at some t. If l_{1}(t) is overestimated, will be lower than its optimal value and .

Increase or decrease by Δl_{1}, depending on whether it is over or under estimated. Go to step 1 to calculate p_{i}(t).
The process is iterated until or is within a tolerable error band.
Notice the price schedule for guaranteed services is based on the given estimates of l_{2}(t), the shadow price for using the bandwidth. This estimate was given arbitrarily at the beginning, and needs to be modified by using feedback from the third stage.
4.3 Spot Pricing
Given the prices for guaranteed services obtained at the second stage, the distribution of available capacity for besteffort service as a function of time can be determined as C_{T}  s[q_{1} (t),..., q_{N}(t)]. At each instant, the network operator will set p_{b}(t), the spot price for admitting cells of besteffort service into the buffer to maximize:
under constraints:
s_{b}(t) ≤ C_{T}  s[q_{1} (t),..., q_{N} (t)] (417)
0 ≤ q_{b}(t) ≤ B_{s} (418)
when q_{b}(t) = B_{s} ο_{b}(t) ≤ s_{b}(t) (419)
when q_{b}(t) = 0 ο_{b}(t) ≥ s_{b}(t) (420)
Given ο_{b}(t), s_{b}(t) are random variables with complicated distributions, the problem in (414)  (418) cannot be solved directly. However, through simulation, we can design heuristic rules that indicate how the spot price, p_{b}(t), should be set based on current buffer occupancy and the expected distribution of willingness to pay of cells arriving in the future.
As soon as the spot price, p_{b}(t), is determined, a new estimate of l_{2}(t) can be constructed. This can be done by using the proposition above that defines the optimal pricing policy. Equation (410), i.e. p_{b}^{*}(t) = *l_{2}(t), applies when the bandwidth is fully used, and Equation (411), i.e. l_{2}(t)=0 applies otherwise. The new estimate can then be used as feedback to revise the optimal pricing schedule for guaranteed services.
The optimal pricing policy is reached by iterating the second and the third stages until both the price schedule for guaranteed services and the expected spot price for besteffort service stabilize.
5. Conclusions and Future Work
In this paper, we discuss the optimal pricing policy for ATM integratedservices networks. By formulating the pricing decision as a constrained control problem and developing a three stage procedure to solve that model, we find there is great similarity between the optimal pricing policy for network services and the optimal pricing policy for conventional products. We demonstrate that under capacity constraints, the service provider should consider the opportunity cost incurred by serving a customer. This opportunity cost should be used to determine the price of a network service in the same way as the marginal production cost is used to determine the price of a conventional product. We derive the mathematical expressions that calculate opportunity costs for different services offered by a single integratedservices network, and explain the implications of these expressions.
Though our procedure is designed for maximizing the service provider's profit, a similar approach can as well be used to maximize other objectives, such as social welfare.
In future work, we will extend our approach to more general situations, and develop pricing policies for situations in the presence of demand substitution effects. We are also interested in looking into pricing policies for a multilink network.
About the Authors
Qiong Wang: Doctoral Candidate. Department of Engineering and Public Policy, Carnegie Mellon University, Pittsburgh, PA 15213. Tel: +1 412 268 5617. Email: qw22@andrew.cmu.edu.
Jon M. Peha: Assistant Professor of Electrical and Computer Engineering, Engineering and Public Policy. Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213. Tel: +1 412 268 7126. Email: peha@ece.cmu.edu.
Marvin A. Sirbu: Professor of Engineering and Public Policy, Industrial Administration and Electrical and Computer Engineering. Department of Engineering and Public Policy, Carnegie Mellon University, Pittsburgh, PA 15213. Tel: +1 412 268 3436. Email: sirbu@cmu.edu.
The research reported in this paper was support in part by the National Science Foundation under grants NCR9210626 and 9307548NCR. Views and conclusion contained in this document are those of the authors and should not be interpreted as representing the official policies, either express or implied, of the National Science Foundation or the U.S. Government.
References
[Cocchi,93] Cocchi, R.; Shenker, S.; Estrin, D.; Lixia Zhang,."Pricing in computer networks: motivation, formulation, and example," IEEE/ACM Transactions on Networking; vol. 1, no. 6, Dec. 1993, pp. 61427. [doi: 10.1109/90.266050]
[Dewan,90] Dewan, S., and Mendelson, H., "User Delay Costs and Internal Pricing for a Service Facility," Management Science, vol. 36, no 12, pp.: 15021517, 1990.
[Kamien,81] Kamien, M. I., Schwartz, N., L., "Dynamic Optimization : the Calculus of Variations and Optimal Control in Economics and Management," North Holland, c1981.
[MacKieMason,94] MackieMason, J. K., Varian, H. R.,."Pricing the Internet," in Public Access to the Internet, B. Kahin and J. Keller, Eds. Englewood Cliffs, N.J. PrenticeHall, 1994.
[Pappas,87] Pappas, J. L., Hirschey, M., Managerial Economics, 5th ed. Dryden Press, c1987.
[Peha,95] Peha, J. M., Tobagi, F. A., "CostBased Scheduling and Dropping Algorithms To Support Integrated Services," to appear in IEEE Transactions on Communications.
[Peha,93] Peha, J. M., "The Priority Token Bank: Integrated Scheduling and Admission Control for an IntegratedServices Network," in Proceedings of IEEE International Conference on Communications, ICC93, Geneva, Switzerland, May 1993, pp. 34551.
[Peha,91] Peha, J. M.,.Scheduling and Dropping Algorithms to Support Integrated Services in. PacketSwitched Networks, Ph.D. Dissertation, Technical Report No. CSLTR91489, Computer Systems Laboratory, Stanford University, June, 1991.
[Tewari,95] Tewari, S., Peha, J. M., " Competition Among Telecommunications Carriers That Offer Multiple Services," Proceedings of 23rd Telecommunications Policy Research Conference, Solomon Island, Maryland, September 30  October 2, 1995.
[Whang,90] Whang, S., Mendelson, H., "Optimal IncentiveCompatible Priority Policy for the M/M/1 Queue," Operations Research, vol. 38, 1990, pp. 870883.
Notes
1. The consumer thus expected to pay if call length has a mean value of . It is more typical for a provider to define a price schedule R_{i}(t) where a call is charged R_{i}(t) at each instant it is in progress. Our formulation of p_{i}(t) is related to R_{i}(t) by when call length is exponentially distributed.
2. For a more detailed discussion on the admissible region, see [Tewari,95].
3. It is preferable to choose a larger w_{m} if call arrival rate is stable over time , and call duration is long, and a smaller w_{m} if arrival rate is sporadic and call duration is short.