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, 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 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 Services

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 (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 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 (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[₁ (t),.....,_N; ₁ (t),.....,_N (t) ≤ C_T (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 B_s. The willingness to pay for sending each cell is revealed to the network. At each time t, the network sets a cut-off 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 first-come-first-serve, or cost-based-scheduling ([Peha,93]).

Figure 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[p_b(t),t]. Define s_b(t) as the instantaneous transmission rate of best-effort service at that time, then:

s_b(t)≤C_T - s[q₁ (t), q₂ (t),...,q_N (t)] (2-5)

where s[q₁(t), q₂(t),...,q_N(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 υ(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:

(2-6)

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

_b(t) ≤ λ_i[p_b(t),t] (2-7)

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

= ο_b(t) - s_b(t) (2-8)

and

s_b (t) ≤ q_b (t) ≤ B_s (2-9)

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 best-effort service, p_b(t), and the amount of bandwidth C_T to maximize the following objective:

(3-1)

under constraints:

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

A[₁(t),.....,_N; ₁(t),.....,_N(t)] ≤ C_T (3-3)

= ο_b(t) - s_b(t) (3-4)

when

q_b(t) = B_s ο_b(t) ≤ s_b(t) (3-5)

0 ≤ q_b(t) ≤ B_s (3-6)

s_b(t) ≤ C_T - s[q₁ (t), q₂ (t),..., q_N (t)] (3-7)

when

q_b (t) = 0 ο_b (t) ≥ s_b (t) (3-8)

q_i(0)=q_i0, 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:

Variables describing best-effort service:

Other variables:

In (3-1), (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 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)p_b(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 (p_i(t),p_b(t)) and the optimal amount of bandwidth (C_T), 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 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 (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 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.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 [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(p_bm)=_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(p_bm) = _bm.

The network operator controls p_im, p_bm, and C_T to maximize total profit, i.e.:

(4-1)

s.t.

(4-2)

_m = A(_im, i=1, m, C_T),

where _m = (beta;₁,.....β_m)

(4-3)

where

[(1-β_im)_im, i=1, m] + λ_bm ≤ C_T, 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 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.[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. 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 best-effort service, cell admission rate equals cell transmission rate at all times, and ignore blocking of best-effort traffic. As a result, λ_b(p_b,t), the arrival rate of cells for which the willingness to pay is above the cut-off 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 best-effort 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 (3-1) - (3-9) as following:

(4-5)

subject to:

i = 1,N, (4-6)

A[₁ (t),.....,_N (t); ₁ (t),.....,_N (t)] ≤ C_T (4-7)

λ_b(p_b,t) + [₁ (t),..., _n (t)] ≤ C_T (4-8)

q_i(0) = q_i0, 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 p_i^*(t), p_b^*(t) are the optimal solutions to the pricing model defined in (4-4)-(4-8), then:

(1) p_i^*(t) = h_i^*(t) and p_b^*(t) = *l₂(t)

if l₂(t) b 0 and h_i(t) b 0 i=1,N

(4-10)

or

(2) p_i^*(t) = h_i^*(t) and p_b^*(t) = p_b⁰(t)

if l₂(t) = 0 and h_i(t) b 0 i=1,N

(4-11)

or

(3) p_i^*(t) = p_i⁰(t) and p_b^*(t) = p_b⁰(t)

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

(4-12)

where: p_i⁰(t) maximizes p_i(t)λ_i(p_i,t), p_b⁰(t) maximizes p_b(t)λ_b(p_b,t),

, (4-13)

i = 1,N

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

l₂(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 (h_i(t) for guaranteed service i, and l₂(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₂(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, l₁(t), l₂(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. l₂(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₁(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₂(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, h₁(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(p_b,t) + [₁ (t),..., _n (t)] < C_T.

As a result, at time t, the shadow price of using the bandwidth, l₂(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. h_i(t) = 0, l₂(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 (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 l₁(t), l₂(t), the shadow prices for reserving and using bandwidth, respectively, i.e. :

where

To find p_i(t), values of l₁(t), l₂(t) need to be determined. At this point, we assume the values of l₂(t) have been estimated and given as . (This prior estimation will be modified by the feedback from stage 3). We then set l₁(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₁(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, C_T, then the expected number of calls in progress,., and the blocking probability, , can be determined.

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

4. Increase or decrease by Δl₁, 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₂(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 C_T - s[q₁ (t),..., q_N(t)]. At each instant, the network operator will set p_b(t), the spot price for admitting cells of best-effort service into the buffer to maximize:

(4-15)

under constraints:

(4-16)

s_b(t) ≤ C_T - s[q₁ (t),..., q_N (t)] (4-17)

0 ≤ q_b(t) ≤ B_s (4-18)

when q_b(t) = B_s ο_b(t) ≤ s_b(t) (4-19)

when q_b(t) = 0 ο_b(t) ≥ s_b(t) (4-20)

Given ο_b(t), s_b(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, 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₂(t) can be constructed. This can be done by using the proposition above that defines the optimal pricing policy. Equation (4-10), i.e. p_b^*(t) = *l₂(t), applies when the bandwidth is fully used, and Equation (4-11), i.e. l₂(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.