Presented at MIT Workshop on Internet Economics March 1995


In the near future a collection of data communication networks (the Internet) is going to provide a variety of services through multiple service classes where each service class will provide a different performance in terms of response time. These service classes will be designed to provide appropriate levels of service to user applications. This paper presents a priority pricing scheme which can be used to manage such a network. Each priority class may be mapped to one or more service classes. The approach presented in this paper can be implemented in a completely decentralized environment. Some simulation results using a hypothetical network with different service levels and requirements are also presented. These results indicate that priority pricing improves the performance significantly as compared to free access (or no usage base pricing) and flat pricing. The implementation of this priority pricing scheme is a practical solution to incentive compatibility in a network with diverse and unobservable user characteristics.

1. Introduction

In the near future a collection of computer networks is going to provide a wide variety of services with an even wider set of user demands with respect to these services. The research community has had a considerable amount of experience with the Internet and a significant amount of research is being done to manage efficiently the resources (routers, communication links, and even data communication protocols) of these networks. These networks will significantly change the Internet, both technically and in terms of kinds of services being offered. Today, the common examples of Internet services include email, FTP, Telnet, IRC, Gopher, and WWW, with limited experience with real-time audio/video services such as MBONE. With the advent of WWW, the access to information on the Internet has become easier and more user friendly—not to mention highly data intensive. The result of availability of user friendly interfaces and high speed access, coupled with greater awareness of these services, has already started creating congestion problems on the Internet.

In coming years, personal publishing through WWW or its descendants and an increased number of real-time audio/video applications such as teleconferencing may be offered through the public data networks such as the Internet. This will create significant congestion problems on the network, resulting in the degradation of service quality. [1] At present the Internet backbone is comprised of T1 and T3 lines with the data transmission speeds of 1.5 Mbps and 45 Mbps respectively; this is orders of magnitude higher than a few years ago when almost the entire backbone was running at 56 kbps. In the next 5 years this capacity may be increased to gigabit ranges. However, the number of servers and users have both increased by several orders of magnitudes in the past 3 years and, as mentioned earlier, the services provided on the network have become much more data intensive.

We believe that the arguments in favor of simply over-providing capacity on the Internet are in error. There are physical and cost limitations of providing capacity, whereas on the application level the desire for additional capacity seems boundless. Furthermore, the future applications on the Internet inherently have different quality of service requirements. [2] Thus, it is essential that appropriate resource management techniques be developed and tested for a multi-service class network.

There are, however, several complications in providing resource management schemes that will be universally accepted. The matter is complicated further because different parts of the network will be owned by different entities and, even though different networks owners may be forced to carry packets from other networks via legislation or by mutual agreement, the required quality of service (in terms of response time) may not be delivered to packets from other networks. The need to deliver different service quality to different services and users, and the need to provide different network providers with incentives to deliver desired service quality, clearly indicates that the current non-priority best effort model of the Internet is not sufficient to sustain a multi-service or integrated service computer network. This, however, does not mean that separate (proprietary) networks have to be developed and maintained for different kinds of services. The positive externalities of interconnectivity, the efficiencies of operation due to availability of different types of services, and the potential to provide interoperability between these services, may outweigh the benefits of separate networks—if the negative externalities or the performance considerations can be addressed.

We believe that a viable approach should have the following characteristics: (i) it should reduce the excess load from the user end without wasting network resources (for example by congesting routers) when users can reschedule without any loss in their value, (ii) it should take the impact of current load on the future arrivals into account, (iii) it should preferably be coarser than packet level pricing so that it is easier and less costly to implement, (iv) the load status of the network nodes (routers, gateways) should be taken into account in users' decision making processes, (v) it should be implemented in a completely decentralized manner, thus not requiring any central governing body and allowing for interaction with other possible resource management schemes, (vi) it should result in effective load management, (vii) it should have multiple priorities to take into account the different qualities of service required by different applications and users, and (viii) it should be implemented in such a way that users have incentives to make the right decisions and service providers have incentives to provide the right level of service.

In the rest of this paper we present a detailed discussion of the issues relevant for the management of integrated service computer networks and present a priority pricing scheme that has the potential to address many of the required attributes for a resource management scheme. In section 2 we present the future of the computer networks, the different types of services and their network resource requirements, and the interaction of different players who will constitute the electronic marketplace. In section 3 we provide details of our priority pricing scheme and discuss the potential of this approach in facilitating electronic commerce. In section 4 we provide details on how our pricing approach can be implemented in real-time. In section 5 we provide detailed results from our extensive simulation study. We conclude in section 6 with directions for future research.

2. The Future of the Computer Networks

At present, different telecommunication services are provided by different types of communication networks, such as voice on telephone networks, business transactions on proprietary or leased networks, and data communication on private/public computer networks. However, a computer's ability to transfer any kind of data in digital form and then transmit/receive it has already led to a variety of services being offered or tested over public computer networks. In the near future it is conceivable that a single network architecture may be able to handle different types of data communication requirements imposed by different services. Figure 1 illustrates a conceptual figure of such a network; note that users may be on servers themselves and may be accessing services on other servers or providing services to other servers or users. In this section we will examine the types of data communication networks that might be integrated, types of services that may be offered along with their service requirements, and the question of how an appropriately designed pricing policy may help in managing the resources in such an environment.

Figure 1 - A Multiservice Integrated Network with Multiple Infrastructure ProvidersFigure 1 - A Multiservice Integrated Network with Multiple Infrastructure Providers

By a single network architecture we mean that users may have a single interface to a communication network through which they will be able to access any application. Clearly, this requires a tremendous amount of interoperability within physical infrastructure and between the different parties involved, such as service providers, infrastructure providers, and software developers. There is a relatively strong consensus that packet switching technology will be the technology of choice to meet this interoperability requirement (see Shenker, 1995). Within the packet switching technology, however, there are several protocols that may be chosen as a communication protocol, such as TCP/IP, ATM, and UDP. There are several ways in which technological interoperability may be achieved among competing technologies, for example by enveloping [3]packets in appropriate protocol or by using multiple protocol routers. However, for the purpose of this paper we focus on: (i) the rationale of providing interoperability between services and thus the technology, (ii) the mechanism needed to provide this interoperability, and (iii) the incentive to infrastructure providers to provide appropriate service levels to users from different subscriber bases.

To understand the aforementioned issues we first have to understand the types of services and applications that may have to be provided or for which this single data communication network will be used. These services will range from simple email to multimedia real-time teleconferencing. However, from our perspective it hardly matters what applications do; the important aspect is the service requirement. For example, email is generally considered to have relatively small sensitivity to delay, while on the other hand a voice conversation may be extremely delay-sensitive. It may be possible to define several categories of service quality depending upon the required response time by an application (figure 2 provides one such categorization). This categorization is based on the delay requirements of an application. Other categorizations may be defined by the data requirement (or size) of different applications (see Shenker, 1995); however, for the purpose of our discussion the depicted categorization is sufficient.

Figure 2 - Relationship Between Delay Characteristics and Delay PredictionFigure 2 - Relationship Between Delay Characteristics and Delay Prediction

Another important aspect of application requirements is the sensitivity to lost packets. Typically, in a TCP/IP network, a receiving application waits until it receives all the packets before presenting it to the user because the traditional alphanumeric data is rather sensitive to incomplete information. In some future applications (for example, in real-time video) some packets may be dropped (and not resent) without much loss in presentation because of the presence of redundancy in the data. On the other hand some applications may be real-time as well as very sensitive to dropped packets (for example, audio conversations). The different delay requirements coupled with the sensitivity to lost packets will force future data communication networks to support multiple service classes with multiple data transfer protocols.

Bohn, et al. (1994) suggest a voluntary precedence level choice for different applications dependent upon their delay requirements and loss sensitivity. In their scheme the user's traffic is monitored after some time interval (say monthly) and the user may be penalized if she does not choose the appropriate precedence for their application. There is a lack of incentive to provide multiple precedence networks on the part of network providers under this scheme, since the providers are not rewarded for providing multiple service classes. Moreover, it is a mistake to categorize the service requirements by just looking at the appearance or title of an application—we must look at the context in which an application is used. For example, email based real-time transaction systems are being developed by some researchers (see Kalakota, et al., 1995) or email based EDI systems; clearly in such applications even email cannot tolerate any delay. However, we believe only users can truly know what level of service is tolerable for their purposes and service providers should play only a passive role in deciding the service quality—this can be ensured only through a proper incentive mechanism.

The next part of the problem arises from the fact that the Internet of the future will be comprised of several multi-service class data communication networks. Besides the technological issue of interoperability, one has to provide enough incentive for these individual networks to provide similar service class levels across the whole network. Specifically, why will a network provide a high service class to a request from another network without proper incentive, and if a price is quoted how will a network requesting a service class know whether it is fair?

In the next section we introduce a priority pricing model that has the potential to be a good resource allocation mechanism in real-time. It can be implemented in a completely decentralized manner where individual networks need worry only about the loads on their systems to compute near-optimal prices. Users of the network services will make myopic decisions, which will lead to socially optimal choices. The priority classes can be associated with the service classes. Table 1 provides a hypothetical example where there are 4 user priority classes available [4] in a multiple protocol network that uses ATM as the protocol for continuous real-time data, which is sensitive to dropped packets; UDP for continuous real-time data, which is relatively tolerant to dropped packets; and TCP/IP for bursty data, which may or may not be real-time in nature.

Table 1 - A Hypothetical Example Associating Priority Classes to Service Classes
Priority Class Service Class
1 - Highest Priority ATM access
2 TCP/IP real-time applications, Frame Relay, SMDS
3 UDP and TCP/IP higher best effort level
4 - Lowest Priority TCP/IP lower best effort level

Note that in Table 1 we suggest multiple levels of best effort service; this is a finer division of delay requirements which customers may want. Real-time TCP/IP applications are applications that are not very data intensive but can suffer relatively little delay: for example possible real-time transactions which use email as the base application. Dynamic allocation of bandwidth will make it possible to assign the bandwidth necessary for ATM applications; however, once the allocation is made and applications continue to send data, no TCP/IP or UDP packets may be sent via the ATM allocated bandwidth. The remaining bandwidth then operates according to the priority of the packets in a normal packet switching environment, i.e., routers will poll the queues from highest to lowest priority before sending a packet and send the packet with highest priority first.

3. Priority Pricing Approach

In Gupta, Stahl, and Whinston (1995a) we present a priority pricing mechanism for network computing. The model presented there is based on general equilibrium theory in economics, but departs from the Arrow-Debreu framework in a manner that makes the results computationally practical. In a pure Arrow-Debreu model, a commodity would be defined for every contingency and every moment in time. Given stochastic demands for computational services, the full state-space model would be much too large for practical purposes. In lieu of state-contingent equilibrium prices, we introduce the concept of a "stochastic equilibrium" in which (i) average flow rates of service requests are optimal for each user given the prices and anticipated delay, and (ii) the anticipated delays are the correct ex-ante expected delays given the average flow rates. Further, an optimal stochastic equilibrium is one that maximizes the net social benefits. We derive a formula that characterizes the priority prices that support an optimal stochastic equilibrium.

This equilibrium concept (and associated results) has significant informational and computational implications. First, it allows the decentralization of the resource allocation process to the user level and reduces the information required for the user's decision problem to current rental prices and current expected delays. The administrative and communication costs of distributing this information pales in comparison to the associated costs of an extremely large number of Arrow-Debreu contingency markets (or even spot auction markets). Secondly (as presented in more detail later), prices can be adjusted in real-time in a manner that pushes them into (and keeps them in) a neighborhood of theoretically optimal prices, and this process can be decentralized as well. Again the computational and communication costs of this mechanism pales in comparison to that of fixed-point algorithms for Arrow-Debreu equilibrium prices.

Although it might be impossible to achieve exact optimal pricing in practice for a volatile environment such as the Internet, we contend that it is possible to compute near- optimal prices in real-time. As a result of this near-optimal pricing, users with different values for the same service will choose different ways or times to obtain the same service. This, in turn, can provide substantial reduction in peak loads and will achieve better distribution of the load over time.

These results are based on an objective function that maximizes collective benefits of the system and its users. The natural question to ask is: why should network service providers be concerned about collective benefits of the system? The primary reason is that the market on the Internet can essentially be viewed as a service industry, and customer satisfaction is directly related to the market share in service industries. The issue of interoperability with other subnetworks also may force these providers to look for a socially optimal choice, since without interoperability a subnetwork will become a deserted information island with little value.

From the practical standpoint these results have significant importance. The priority prices at the servers decentralize the management and accounting problems. They give the users or their clients access to an evaluation mechanism to decide when and what kind of service they want and at what priority. At the server level this scheme will allow the management to assess the queues and delays more accurately and design their systems accordingly. Priority prices will allow servers to maintain or delete different classes of services depending upon the type of traffic they experience. At the network level they will allow for a better load distribution because excessively loaded and thus highly priced servers would be avoided by users and priority prices will allow proper incentives to provide different equivalent classes of services across the network.

The price at a particular server for a particular priority class can be represented by the following system of equations (see the appendix for the mathematical model):


  • ∑rmk(q) is the price of a job sized q at server m for priority class k,

  • mkq is the arrival rate of jobs sized q at machine m in priority class k

  • ∑ Wl is a continuously differentiable, strictly increasing function of arrival rates cmkq and capacity vm, which provides the waiting time at a server m for priority class l,

  • ∑ dij is the delay cost parameter of consumer i for service j, and

  • ∑ xijlm is the flow rate of service j for consumer i with priority l at server m.

Let us briefly interpret this equation. The first term on the right side is the derivative of waiting time with respect to the arrival rate of jobs of size q. Since the waiting time is a strictly increasing function of this arrival rate, an increase in the arrival rate of a certain priority class increases the prices for that priority class. The second term ∑ij dij xijlm can be interpreted as the accumulated delay cost of the system; an increase in this cost increases the price. Since the jobs in the highest priority class impose delays on the jobs in all other priority classes, whereas the jobs in lowest priority classes impose very little delay on the jobs in other priority classes, the prices for higher priority classes are higher than those of lower priority classes. These prices are optimal congestion tolls; some other approaches for the congestion tolls are provided by Mendelson and Whang (1990), MacKie-Mason and Varian (1994), and Shenker (1995).

The optimal prices can be computed only if the optimal arrival rates are known and true equilibrium waiting times are known. We propose an iterative approach where the current estimates of the prices are computed given the historical information on flow rates and waiting times. This iterative approach can be implemented and analyzed by using simulation techniques where we estimate the prices using the transient information to guide the system towards a stochastic equilibrium. In the next section we first introduce the iterative approach and a conceptual model of the Internet that we are using to evaluate our pricing scheme, and then we present the simulation model that we are using to estimate the prices and calculate the benefits.

4. Iterative Price Computation and the Simulation Model

Figure 3 presents a conceptual model of the Internet. Essentially, we model the Internet infrastructure as a black-box, i.e., we aggregate the total delay at the server such that it appears that delay is only suffered at the server. [5] The users are connected to the Internet through some access providers (which we can consider as a service in itself). The access providers and the service providers, e.g., news, movies, video-conferencing, databases, etc., are "directly" connected to the Internet through a data-pipeline of a certain capacity. In this model, the capacity of the data-pipeline is essentially the bottleneck for the service providers. [6] In the absence of any pricing mechanism as more users demand a service, the quality of the service (in terms of data transfer rates) suffers. [7] Furthermore, as the congestion increases at the data-pipeline, the backbone experiences more load also due to the resending of lost packets. The network service providers are able to monitor the loads at different servers, and they impose prices according to the load imposed by the servers on the backbone due to the congestion at their gateways.

The prices are computed based on the system of equations presented in the previous section. However, since these prices are not computed at the equilibrium conditions, they are approximate at any given time. We implement the following iterative equation to update the prices at any given time (t+1):


  • α is a number between (0,1)

  • is the estimated new price at time (t+1) using equations (1)

  • is the implemented price during the time (t, t+1)

Figure 3 - A Conceptual Model of The InternetFigure 3 - A Conceptual Model of The Internet

The idea behind updating the price this way is to provide a shield against local fluctuations in demand and in the stochastic nature of the process. A lower value of the parameter a means that the price adjustment will be gradual in time, whereas a higher a will result in potentially large changes in the prices from period to period. In our experience with the simulations, we have found that smaller values of a, of the order of 0.1, result in reasonably quick convergence and higher stability in prices.

We implement our pricing mechanism by using a simulation platform. The objectives of the simulations are two fold: (i) to provide a sense of the degree of improvement an appropriately designed pricing scheme may provide, and (ii) to gain insight into the real-time implementation of a pricing mechanism. Very little is known about the performance and/or design of feedback mechanisms to control processes in real-time. To our knowledge, our effort is the first systematic, theoretically supported approach to such real-time problem solving. We have gained valuable insights and have developed several mechanisms for consistent predictions in real-time. The details of these approaches are beyond the scope of this paper and will be presented elsewhere; however, we present a sketch of overall approach here along with some results.

Figure 4 provides a flow diagram of the simulation model we are using at present. The arrival rates to the system are price/cost sensitive; to explore the effect of scaling, we vary a parameter Xo. Suppose with Xo the optimal arrival rates of jobs entering the system is xo. As we increase Xo to X'o, the service requests are increased and more users try to enter the system; however, the prices are also increased resulting in an optimal arrival rate of x'o which usually is not directly proportional to the increase in Xo. Alternatively, we can interpret Xo as the arrival rate to the system that would occur if there were free access and zero expected waiting times (i.e., the hypothetical uncongested arrival rate or the demand for network services). Note that realized arrivals into the system are always less than Xo. Figure 5 graphically illustrates the above mentioned phenomenon.

Upon the arrival of a service request, the type of service required is identified (a service is characterized by the amount of computational cycles required at a server). Then, the current estimates of prices and predicted waiting times are obtained for all the servers offering the particular service. The user then evaluates the total expected cost of this service in terms of her delay cost and the service cost against her value of the service. If the total cost of the service is higher than her value for the service, the user quits the system; otherwise, she submits the request for obtaining the service. [8] We generate user values and delay costs from normal distributions; the mean delay costs are set to be less than 1% of the mean job value.

Figure 4 - Flow Chart of the Simulation ModelFigure 4 - Flow Chart of the Simulation Model

A user's request is sent to the server that was chosen as the least cost server. For example, if a service is available at 5 servers, then the user estimates the total cost of the service by adding his expected delay cost and network services cost at all the 5 servers and chooses the one where the total cost is expected to be the smallest. If the server queue is empty, the request is immediately processed; however, if some job requests exist in the server queue, then the requests are handled in a FIFO manner, by priority class.

Figure 5 - Effect of Scaling Parameter XoFigure 5 - Effect of Scaling Parameter Xo

The estimates of waiting times and prices are updated every 'T' units of time. Although we can conceivably update the expectations whenever a request is made, we find three major arguments for less frequent updates in stochastic systems: (i) estimating waiting times and prices over a longer time period provides more stable results; (ii) once we are in the vicinity of the stochastic equilibrium, the small fluctuations in prices will not warrant frequent updates; and (iii) the computational effort required in recomputing the prices and waiting times at each request might negate any benefits derived from pricing. However, as other parameters are changed, the update interval also must be changed for any cross-comparison of results.

The results presented here are based on a model that has 50 servers and 100 services. The capacity of the data pipelines at the servers are generated through a random process to be among the following: (i) 128 kbps (kilobits per second), (ii) 256 kbps, (iii) 384 kbps, (iv) 1.544 Mbps (megabits per second), (v) 4.0 Mbps, and (vi) 10.0 Mbps. The first three choices here represent 2, 4, or 6 multiplexed ISDN (Integrated Services Digital Network) data channels respectively, the fourth choice is the capacity of a T1 line, and fifth and sixth choices are typical of those achieved via Framerelay or SMDS (Switched Multimegabit Data Services) connections. The size of each service is also randomly generated to be in the range of 10 kb - 15 Mb (or, 1.22 kilobytes - 1.8 megabytes); however, the distribution is chosen so that there are higher number of smaller services to simulate a more realistic service request distribution. Figure 6 displays the service size distribution. A server can provide several of the 100 services. A service can be provided on up to 25 servers; the exact number of servers on which a service is available is generated randomly from a discrete uniform distribution. Figure 7 displays a sample of a service directory, which provides information on how many and which services are available on a server, and where a service is available and on how many servers. The service directory and the network configuration, in terms of service sizes and server capacities, were kept constant for all the results reported here.

We examine this system under a free access policy, our priority pricing policy, and a flat pricing policy where every job is charged the same amount regardless of its size. We compare these three pricing policies under different sets of load conditions by simulating higher loads as higher arrival rates to the system. A higher arrival rate induces more load on the system and helps in understanding the behavior of a network with fixed capacity under increasing load. Specifically, we examine this model for an arrival rate of 10 to 500; this captures the system behavior under virtually no queues (at the arrival rate of 10) and under extremely long queues (at the arrival rate of 500).

Figure 6 - Distribution of Service Sizes Used in the SimulationFigure 6 - Distribution of Service Sizes Used in the Simulation

We present our results under two sets of conditions. First we compare the results for all the three pricing policies when perfect information regarding the waiting times is available. [9] However, providing perfect information in any realistic situation is not practical because of excessive cost involved in computing new information for every new request; furthermore, several requests can be submitted virtually at the same time making this information invalid even if it were financially possible to provide perfect information. Thus, we also provide results for the case when perfect information regarding the waiting time is not available, and only an estimated (or predicted) waiting time is known. In the latter case both prices and predicted waiting times are updated at the same time, whereas in the former case only prices are updated after a fixed interval of time, while implementing our pricing policy.

Figure 7 - A Service DirectoryFigure 7 - A Service Directory

5. Simulation Results

We provide results for multiple service classes and some robustness results against customer misrepresentation, along with the implications of these results. The results presented here are suggestive of the benefit of applying a priority pricing scheme to Internet services. Essentially, without a pricing mechanism, users with zero or low delay cost have nothing to discourage them from over utilizing the services; however, with a pricing mechanism they are forced to obtain only the services for which their value is higher than the cost. In addition they choose the appropriate service class dependent upon their service requirements. Service providers, on the other hand, have incentives to provide multiple service classes because they can generate higher revenues and provide better service overall at the same time.

First we present results for the case when perfect information regarding the delays is available. As mentioned earlier, exact information cannot be provided in real-world application. We provide these results as a benchmark case since these conditions are best case scenarios for free access and flat pricing. It is quite difficult to assess good flat prices in a large network such as one modeled here; poorly chosen flat prices may in fact provide worse performance than free access. To get estimates of good flat prices we collected the average price information during simulation runs with our pricing scheme and then used these average prices as flat prices for our simulations with flat prices. Since in a network with multiple priority classes the waiting times in lower priority classes depend upon the future arrivals in higher waiting classes during their stay in the queue, it is not possible to assess exact waiting times for a network with priority classes. Thus, for this case we restrict our attention to simulation results with just one priority class.

Figure 8 presents the results from the simulation with exact waiting time information. In the figure we present the net benefits [10] per unit time and customer benefits [11] per unit time under all three pricing policies. The results indicate clearly that as the load on the system increases our dynamic pricing approach performs far better than either the free access or the flat pricing strategy. Our pricing approach not only is significantly better in terms of net benefits but the customer benefits are also significantly higher. In fact, our pricing approach delivers higher customer benefits than the net benefits with flat pricing. Figure 8 also suggests that a flat pricing scheme may be found which is better than free access in terms of net benefits (provides additional revenue for service providers) and is comparable in terms of customer benefits and thus customer satisfaction.

Another important point to realize is that when the load is low our pricing scheme delivers the same performance as zero pricing, i.e., the prices adjust according to the load on the system. This is a significant and desirable characteristic of any pricing scheme because this allows for a self-adjusting real-time implementation of our optimal pricing scheme in data networks where prediction of load is extremely difficult.

Next, we present results for the case where perfect delay information is not known but after fixed intervals of time (periods) when prices are updated, estimation of future waiting times are performed. These estimated waiting times are then used by customers to evaluate their service needs. Our experience with the pricing strategies have revealed that it is not possible to predict delay with the same accuracy with free access as compared with our pricing approach, hence the performance with free access deteriorates exponentially (see Gupta, Stahl, and Whinston, 1995b). Thus, we do not present results using free access and flat pricing with predicted delays. Instead we concentrate on providing results with priority classes.

Figure 9 presents net and customer benefits per unit time with a non-priority and a two priority network. Other details such as the customer arrivals, delay costs, service requirements were held constant in the simulation runs across these two situations by generating random numbers from the same streams for each parameter in both cases.

The figure indicates that for quite a large range of load the two-priority system performs better than a one-priority system in terms of both the net and customer benefits. As the load increases the net benefits tend to increase, and a similar trend can be seen with customer benefits. However, in a fixed capacity network, benefits may only increase up to a certain load by using any pricing scheme—we call it critical load. Beyond the critical load a network performance deteriorates and the only way to increase the benefits beyond this point is to increase network capacity. By using our approach and simulation modules it is possible to compute these critical loads to compare them to the mean loads at any network in order to make rational capacity expansion decisions.

Some large customers may have the incentive to misrepresent their needs in an attempt to artificially increase or decrease the prices by providing wrong information regarding their delay costs. In economics this is called the incentive compatibility problem. In a data communication network such as the Internet with different customers, it is difficult to envision a price scheme that is absolutely incentive compatible, as compared to a centrally managed network (see, for example, Mendelson and Whang, 1990). However, we contend that it is more important to have a robust pricing scheme that deviates little from its performance in case of misrepresentation as compared to correct representation. A robust system may also allow us to avoid any direct query regarding customers' value of delay for pricing purposes, since surrogate estimation schemes for this purpose may be designed.

Figure 10 provides a comparison of our pricing policies with and without misrepresentation of delay costs. In the misrepresentation case, customers overquote their value of delay to the network by a mean factor of 125%. It is clear from the figure that very little may be gained from misrepresentation; in fact, the performance in case of a two-priority system is virtually identical. We think that Figure 10 provides evidence that our pricing approach and its implementation is quite robust against misrepresentation of delay cost. This has encouraged us to develop a surrogate scheme for estimating average delay cost. We are in the initial development process of this surrogate scheme and will present these results in the future.

6. Summary and Conclusions

In this paper we provide a glimpse of the future of the Internet. The Internet is going to provide a diverse group of services to a diverse group of users with different service requirements. The only possible way to realize such a network is by allowing a multi-service class network with possibly diverse data transmission protocols to cater to different service requirements and/or specifications.

We present a priority pricing approach to manage a multi-service class network. This pricing scheme can be implemented in real-time and in a completely decentralized setting. We are developing and testing the implementation by simulating a network of diverse server capacities and service requirements. The simulation involves the feedback of information regarding the expected network performance for the future. The success of any real-time pricing scheme will depend upon the reasonable prediction of expected performance. Through our simulation studies we have developed mechanisms that provide these expectations with reasonable accuracy and will provide important guidelines in actual implementations.

Our simulation results provide evidence that significant advantages can be gained by using a priority pricing approach in data networks. We contend that the priority pricing will allow the dynamic management of bandwidth in multiple class networks through priority pricing. Revenue (cost) will provide incentives for network service providers (customers) to provide (choose) appropriate service classes. Furthermore, our implementation seems to be robust against misrepresentation, which has encouraged us to develop surrogate estimation procedures where no user input is required except service requirements.

Our simulation platform is a powerful tool to explore various pricing strategies, regulatory impact, and infrastructure investment. It can provide guidelines for capacity expansion and information restructuring. We can also use it for exploring the effect of using different pricing strategies by different network entities.

In future research we will concentrate on the development of better estimation techniques and development and testing of accounting and billing procedures. Specifically, we will test the effect of different proposed accounting and billing schemes. We will evaluate the relative strengths and weaknesses of various accounting and billing schemes by testing their impact on actual processing of data. We will also test the effects of different market structures that may arise in electronic commerce.

Appendix: Mathematical Model
Vij Instantaneous value of service j to customer i
dij Delay cost of customer i for service j
wmk Waiting time at server m in priority class k
rmk(q) Rental price at server m in priority class k, for q bits
qj Number of bits associated with service j
t(j, m, k) Expected throughput time for service j, at server m, in priority class k
pijkm Probability that customer i will request service j at server m, in priority class k
Xo Demand scaling parameter
lij Fraction of Xo associated with customer i for service j

Benefit Maximization

subjected to

where cm is the matrix of service request arrival rate by job size and priority, and vm is the capacity at the server m.

Customer Optimization

The customer costs are optimized as follows:

Then the probability that a customer will submit their job is given by

The resulting stochastic arrival rate to the system is then

Author Information

Alok Gupta (, Dale Stahl (, and Andrew Whinston ( are affiliated with the University of Texas at Austin.


Bohn, R., Braun, H. W., Claffy, K. C., and Wolff, S., "Mitigating the Coming Internet Crunch: Multiple Service Levels via Precedence," Technical Report, University of California, March 1994.

Cocchi R., Estrin, D., Shenker, S., and Zhang, L., "Pricing in Computer Networks: Motivation, Formulation, and Example, IEEE/ACM Transactions on Networking, v. 1-6, 614-627, 1993.

Cronin, Mary J., Doing Business on The Internet: How the Electronic Highway is Transforming American Companies, Van Nostrand Reinhold, NY, 1994.

Gupta, A., D. O. Stahl, and A. B. Whinston, "An Economic Approach to Network Computing with Priority Classes," Journal of Organizational Computing, forthcoming, 1995a. A version of this paper is available in HTML format on the World Wide Web server of the Center for Information Systems Management, University of Texas at Austin. The URL for linking to this server is [formerly] The paper is under the title of "CISM Working papers." The paper can be viewed with any browser.

Gupta, A., D. O. Stahl, and A. B. Whinston, "Pricing of Services on The Internet," in IMPACT: How IC2 Research Affects Public Policy and Business Markets

Fred Phillips and W. W. Cooper eds., Greenwood Publishing, CT, forthcoming, 1995b.

Kalakota, R., J. Stallert, and A. B. Whinston, "Solving Operations Research Problems Using a Global Client/Server Architechture," working paper, CISM, The University of Texas at Austin, 1995.

Loch, C., "Pricing in Markets Sensitive to Delay," Ph.D. Dissertation, Stanford University, 1991.

MacKie-Mason, J. K., and H. R. Varian, "Pricing the Internet," Technical Report, February 1994.

Mendelson, H., and S. Whang "Optimal Incentive-Compatible Priority Pricing for the M/M/1 Queue," Operations Research, 38, 870-83, 1990. [doi: 10.1287/opre.38.5.870]

Shenker, S., "Service Models and Pricing Policies for an Integrated Services Internet," in Public Access to the Internet, B. Kahin and J. Keller eds., MIT Press, Cambridge, MA, 1995.

Spigai, Fran, "Information Pricing," in Annual Review of Information Science and Technology, v. 26, ed. Williams, M. E., Learned Information Inc., Medford, NJ, 39-73, 1991.


1. In this paper we use the words service quality and service requirement to mean the response time delivered or needed for a particular service.return to text

2. We will elaborate on this further in the next section.return to text

3. Enveloping refers to a technique where packets of one type are packaged in the packets of another type for transmission purposes; for example, at present the MBONE packets which are normally in UDP format are usually enveloped in TCP/IP disguise.return to text

4. There may be more priority classes than users are allowed to use in order to perform important network management tasks, which may indeed take precedence over any other usage.return to text

5. This assumption is used to simplify the model; however, the results presented here can easily be extended to the cases where the delay is suffered at multiple nodes as shown in Gupta, Stahl, and Whinston (1995a).return to text

6. From the users' perspective, in reality, the bottleneck is either the server's pipeline or the slowest data communication link in their path to the server.return to text

7. Note that some users might decide not to get the service because of the excessive delays; however, users with negligible delay costs will try to obtain the service regardless of the delays. Thus, with no pricing mechanism the services can potentially be accessed by only the users who value it the least.return to text

8. Realistically, this work would be done by a smart agent executing on a client on the users machine. We discuss this and more implementation issues later in the paper.return to text

9. Note that the perfect waiting time information scenario case is the "best-case" scenario for our implementation of the free access policy because users first check where can they get the fastest service and the information they get is exact.return to text

10. net benefits = total value - total delay cost.return to text

11. customer benefits = net benefits - total price. Note that with free access, net benefits = customer benefits.return to text