Presented at MIT Workshop on Internet Economics March 1995

Abstract

ATM integrated-services networks are expected to dominate information carriage in the next 20 years. While there are extensive studies of the engineering problems of designing ATM integrated-services 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 integrated-services network with time-varying demand. Based on an optimal control model formulation, we develop a 3-stage 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 cell-switching technology, it is becoming increasingly efficient to provide different telecommunication services through one integrated-services network instead of multiple single-service networks. It is expected that in the next twenty years, most of today's single-service 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) integrated-services networks. In an ATM integrated-services network, any piece of information, regardless if it is voice, image, or text, is organized as a stream of fixed-length 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 e-mail senders will tolerate longer delay; web browsing generates a very bursty cell stream while constant-bit-rate 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 30-50 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 flat-rate 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 client-server 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. MacKie-Mason and Varian ([MacKie-Mason, 94]) suggest a spot-price 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 Mackie-Mason ([Mackie-Mason,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 integrated-services 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 integrated-services 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 time-varying 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 integrated-services network. In section 3, we formulate an optimal pricing model and discuss how to solve it using a 3-stage 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 sub-additive, leading to conditions of natural monopoly for an integrated-services network operator. In the model that follows, we assume a single profit-maximizing monopolist operating the network. In this paper, we consider only a point-to-point 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 CT, 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 pre-specified 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 best-effort service. Telephone calls, HDTV, and interactive games typically require some type of guaranteed service, while e-mail is usually specified as a best-effort service.

Our pricing model considers both guaranteed services and best-effort service, which are discussed in the following sub-sections.

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 500-times 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 inter-cell 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, pi(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 pi(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[pi(t),t] as the arrival rate of calls for service i given that the price of a call which starts at t will be pi(t) throughout the call. [1]. Assume at any given price, pi(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 cross-elasticity 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 integrated-services 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.

Figure 2.1 Call Admission Process for Guaranteed ServicesFigure 2.1 Call Admission Process for Guaranteed Services

For each service i(i=1,N), we assume call duration is exponentially distributed with departure rate ri. Define qi(t) as the number of calls underway of service i at time t, and i(t) as the expected value of qi(t). Under the assumptions we made about call arrival. and departure processes, the rate of change of i should follow:

=(1-βii(pi,t)-ri i(t) i=1, N (2-1)

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 long-term capacity investment decision. In the following, we will show how keeping blocking probability at the desired level will affect short-term pricing decisions:

Suppose the network offers only one service; then the blocking probability at each time can be determined by:

(2-2)

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 (2-2), 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 CT, 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),] ≤ CT at all t (2-3)

(2-3) 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) ≤ CT (2-4)

2.2 Service Model for Best-effort Service

Given no performance guarantee, cells of best-effort 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 best-effort service are charged on a per-cell basis. We assume all cells of best-effort service share a buffer of size Bs. The willingness to pay for sending each cell is revealed to the network. At each time t, the network sets a cut-off price, pb(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 pb(t), and pb(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 first-come-first-serve, or cost-based-scheduling ([Peha,93]).

Figure 2.2 Service Model for Best-effort ServiceFigure 2.2 Service Model for Best-effort Service

Assume at time t, the arrival process of cells of best-effort service is Poisson with expected value λb(0,t); the acceptance of cells is also Poisson with expected value λb[pb(t),t]. Define sb(t) as the instantaneous transmission rate of best-effort service at that time, then:

sb(t)≤CT - s[q1 (t), q2 (t),...,qN (t)] (2-5)

where s[q1(t), q2(t),...,qN(t)] is the instantaneous transmission rate of all guaranteed services, which is a function of numbers of calls in progress. Equation (2-5) implies the instantaneous transmission rate of best-effort 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 cut-off price) can be dropped because the buffer can become temporarily full. Define υ(tt) as the number of cells actually admitted into the buffer during the interval [ttt]; then the instantaneous admission rate can be defined as:

(2-6)

οb(t) is a random variable and we assume its expected value is b(t), then

b(t) ≤ λi[pb(t),t] (2-7)

Define qb(t) as the number of cells in the buffer at time t, then:

= οb(t) - sb(t) (2-8)

and

sb (t) ≤ qb (t) ≤ Bs (2-9)

3. The Optimal Pricing Policy

In this section, we will discuss the profit-maximizing 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 3-stage 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 pi(t), and best-effort service, pb(t), and the amount of bandwidth CT to maximize the following objective:

(3-1)

under constraints:

, i ≥ 0 i = 1, N (3-2)

A[1(t),.....,N; 1(t),.....,N(t)] ≤ CT (3-3)

= οb(t) - sb(t) (3-4)

when

qb(t) = Bs οb(t) ≤ sb(t) (3-5)

0 ≤ qb(t) ≤ Bs (3-6)

sb(t) ≤ CT - s[q1 (t), q2 (t),..., qN (t)] (3-7)

when

qb (t) = 0 οb (t) ≥ sb (t) (3-8)

qi(0)=qi0, i=1, N (3-9)

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(pi,t)

call arrival rate of service i at time t, when price is pi
pi(t) unit price for service i, as a function of call starting at time t
ri call departure rate of service i
qi(t) number of calls of service i in progress at time t

i(t)

expected value of qi(t)
s[q1(t), q2(t),...,qN(t)] total data rate of all guaranteed services at timet

i(t)

desired blocking probability for service i at time t

Variables describing best-effort service:

qb(t) queue length of best-effort service at time t
sb(t) cell transmission rate at time t

λb[pb(t),t]

cell accepting rate, i.e. arrival rate of cells with willingness to pay higher than pb(t)

οb(t)

admission rate of cells at time t

b(t)

expected value of οb[pb(t), t]

pb(t)

price for admitting one cell into the buffer at time t

Other variables:

T

duration of business cycle

CT

total bandwidth

K(CT)

amortization of capacity investment cost over one cycle

Bs

buffer size

In (3-1), (1 - βi) λi (pi,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, pi(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 best-effort 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)pb(t)dt is the expected revenue from best-effort 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 3-stage Procedure

Though it would be ideal to solve the model defined in (3-1) - (3-8) directly to get the analytical form of the optimal pricing trajectory (pi(t),pb(t)) and the optimal amount of bandwidth (CT), it is mathematically intractable. Therefore, we construct a three-stage procedure to find a near-optimal 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 near-optimal level.

Figure 4.1 The 3-stage ProcedureFigure 4.1 The 3-stage Procedure

The 3-stage procedure is defined as follows: at stage 1, we solve a long-term optimal investment problem to find the optimal amount of total bandwidth (CT), 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 best-effort service at each moment. The spot price for best-effort service is then derived to maximize the revenue from best-effort 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 best-effort 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 3-stage 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, CT, 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.wm, (m=1,M). Take the average arrival rate as the arrival rate for all time during that interval. λim is determined by price pim. We also assume that calls admitted during the interval [m-2,m-1] will have no influence on traffic load within the interval [m-1,m]. im is the blocking probability during the interval.[m-1,m], which is a function of network loads within that interval.

At this stage we ignore blocking due to finite buffer space for best-effort traffic. Then the expected cell acceptance rate equals the expected cell admission rate, i.e. λbm(pbm)=bm. In other words, all cells with willingness to pay higher than the cut-off 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(pbm) = bm.

The network operator controls pim, pbm, and CT to maximize total profit, i.e.:

(4-1)

s.t.

(4-2)

m = A(im, i=1, m, CT),

where m = (beta;1,.....βm)

(4-3)

where

[(1-βim)im, i=1, m] + λbm ≤ CT, i=1, N (4-4)

This is an optimization problem with (N+1)M+1 controlling variables. It can be solved either by non-liner optimization techniques or generic algorithms such as simulated annealing. The resulting Ct 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.[m-1,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. wm 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 wm, the effects will go in the opposite direction. Therefore, wm 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 best-effort service, cell admission rate equals cell transmission rate at all times, and ignore blocking of best-effort traffic. As a result, λb(pb,t), the arrival rate of cells for which the willingness to pay is above the cut-off price pb(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 best-effort service in the problem formulation.

Given the amount of bandwidth (CT) and optimal blocking probability (i(t), i=1,N) calculated at stage 1, we can simplify the optimal pricing model defined in (3-1) - (3-9) as following:

(4-5)

subject to:

i = 1,N, (4-6)

A[1 (t),.....,N (t); 1 (t),.....,N (t)] ≤ CT (4-7)

λb(pb,t) + [1 (t),..., n (t)] ≤ CT (4-8)

qi(0) = qi0, i=1, N (4-9)

We assume that. the optimal solution exists for this pricing model. The optimal solution to equation (4-5) through (4-9) must obey the following proposition, which yields the optimal pricing policy:

Proposition: The optimal pricing policy

Suppose pi*(t), pb*(t) are the optimal solutions to the pricing model defined in (4-4)-(4-8), then:

(1) pi*(t) = hi*(t) and pb*(t) = *l2(t)

if l2(t) b 0 and hi(t) b 0 i=1,N

(4-10)

or

(2) pi*(t) = hi*(t) and pb*(t) = pb0(t)

if l2(t) = 0 and hi(t) b 0 i=1,N

(4-11)

or

(3) pi*(t) = pi0(t) and pb*(t) = pb0(t)

if hi(t) = 0 i=1,N

(4-12)

where: pi0(t) maximizes pi(ti(pi,t), pb0(t) maximizes pb(tb(pb,t),

, (4-13)

i = 1,N

l1(t) is the Lagrangian multiplier of constraint (4-6), (4-14)

l2(t) is the Lagrangian multiplier of constraint (4-7).

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 (4-9) 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 best-effort 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 (hi(t) for guaranteed service i, and l2(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 hi(t) as the opportunity cost for providing guaranteed service i, and l2(t) as the opportunity cost for providing best-effort 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, l1(t), l2(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 best-effort service is sent, one unit of bandwidth is consumed. Therefore, the unit opportunity cost for best-effort service at time t is just the shadow price of using one unit of bandwidth at that time, i.e. l2(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, l1(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, l2(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 exponentially-distributed random variable, the total cost, h1(t), is estimated by taking mathematical expectation, using the distribution function of the call duration.().

Equation (4-10) 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 best-effort 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(pb,t) + [1 (t),..., n (t)] < CT.

As a result, at time t, the shadow price of using the bandwidth, l2(t), equals 0, and the optimal pricing policy should follow (4-10), i.e. the network operator should set price to maximize total revenue from best-effort service without considering the constraint on data rate.

Equation (4-11) 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 best-effort service than what is needed. As a result, both the opportunity costs for guaranteed services and the opportunity cost for best-effort service equal zero (i.e. hi(t) = 0, l2(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 CT 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 (4-9), (4-10), 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 l1(t), l2(t), the shadow prices for reserving and using bandwidth, respectively, i.e. :

where

To find pi(t), values of l1(t), l2(t) need to be determined. At this point, we assume the values of l2(t) have been estimated and given as . (This prior estimation will be modified by the feedback from stage 3). We then set l1(t) to the trial value ,and construct the following procedure to find the optimal value for pi(t), as well as to modify the estimate of l1(t):

  1. Calculate the optimal pricing schedule for guaranteed services by :

    and

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

  3. If l1(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 l1(t) is over-estimated, will be lower than its optimal value and .

  4. Increase or decrease by Δl1, depending on whether it is over or under estimated. Go to step 1 to calculate pi(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 l2(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 best-effort service as a function of time can be determined as CT - s[q1 (t),..., qN(t)]. At each instant, the network operator will set pb(t), the spot price for admitting cells of best-effort service into the buffer to maximize:

(4-15)

under constraints:

(4-16)

sb(t) ≤ CT - s[q1 (t),..., qN (t)] (4-17)

0 ≤ qb(t) ≤ Bs (4-18)

when qb(t) = Bs οb(t) ≤ sb(t) (4-19)

when qb(t) = 0 οb(t) ≥ sb(t) (4-20)

Given οb(t), sb(t) are random variables with complicated distributions, the problem in (4-14) - (4-18) cannot be solved directly. However, through simulation, we can design heuristic rules that indicate how the spot price, pb(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, pb(t), is determined, a new estimate of l2(t) can be constructed. This can be done by using the proposition above that defines the optimal pricing policy. Equation (4-10), i.e. pb*(t) = *l2(t), applies when the bandwidth is fully used, and Equation (4-11), i.e. l2(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 best-effort service stabilize.

5. Conclusions and Future Work

In this paper, we discuss the optimal pricing policy for ATM integrated-services 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 integrated-services 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 multi-link 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. E-mail: 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. E-mail: sirbu@cmu.edu.

The research reported in this paper was support in part by the National Science Foundation under grants NCR-9210626 and 9307548-NCR. 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. 614-27. [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.: 1502-1517, 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.

[MacKie-Mason,94] Mackie-Mason, J. K., Varian, H. R.,."Pricing the Internet," in Public Access to the Internet, B. Kahin and J. Keller, Eds. Englewood Cliffs, N.J. Prentice-Hall, 1994.

[Pappas,87] Pappas, J. L., Hirschey, M., Managerial Economics, 5th ed. Dryden Press, c1987.

[Peha,95] Peha, J. M., Tobagi, F. A., "Cost-Based 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 Integrated-Services Network," in Proceedings of IEEE International Conference on Communications, ICC-93, Geneva, Switzerland, May 1993, pp. 345-51.

[Peha,91] Peha, J. M.,.Scheduling and Dropping Algorithms to Support Integrated Services in. Packet-Switched Networks, Ph.D. Dissertation, Technical Report No. CSL-TR-91-489, 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 Incentive-Compatible Priority Policy for the M/M/1 Queue," Operations Research, vol. 38, 1990, pp. 870-883.


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 Ri(t) where a call is charged Ri(t) at each instant it is in progress. Our formulation of pi(t) is related to Ri(t) by when call length is exponentially distributed.return to text

2. For a more detailed discussion on the admissible region, see [Tewari,95].return to text

3. It is preferable to choose a larger wm if call arrival rate is stable over time , and call duration is long, and a smaller wm if arrival rate is sporadic and call duration is short.return to text