A modest proposal for preventing Internet congestion

Andrew Odlyzko, AT&T Labs-Research

A simple approach, called PMP (Paris Metro Pricing), is suggested for dealing with congestion in packet networks such as the Internet. It is to partition a network into several logical networks, each of which would treat all packets equally on a best effort basis, just as the current Internet does. There would be no formal guarantees of quality of service. The separate networks would differ only in the prices paid for using them. Networks with higher prices would attract less traffic, and thereby provide better service. Price would be the primary tool of traffic management.

1. Introduction

The Internet is the great success story of the 1990s. However, endemic congestion has led to wide dissatisfaction, and there is general agreement that new applications, especially real time ones such as packet telephony, will require higher quality of service. Various solutions to data network congestion are being developed, typically involving bandwidth reservation or priority setting. (See [Huitema, JordanJ, Keshav, Shenker2] for a discussion of some proposals and references.) Many of the proposed schemes are complicated, and involve substantial costs in both development and operations. Furthermore, since the basic problem is that of allocating a limited resource, any solutions will surely have to involve a pricing mechanism. This is felt by some to be a blemish, going against the tradition of the "free" Internet. Still, an explicit charging mechanism does appear inevitable to prevent the "tragedy of the commons" in which every packet is sent with the highest possible priority. Following in the footsteps of Jonathan Swift [Swift], I propose to turn a perceived burden into a solution, and rely on usage-sensitive pricing to control congestion, bypassing most of the complexity of other solutions. This should allow for simpler networks that are easier to design and deploy and operate faster.

The proposal (called PMP, an abbreviation of Paris Metro Pricing, for reasons explained below) is to partition a network into several logically separate networks. Each would have a fixed fraction of the capacity of the entire network. (Some variations on this design are possible and are discussed in Section 2.) All networks would route packets using protocols similar to the current TCP and UDP, with each packet treated equally. The only difference between the networks would be that they would charge different prices. Customers would choose the network to send their packets on (on a packet-by-packet basis, if they wished), and would pay accordingly. There would be no formal guarantees of quality of service, with packets handled on a "best effort" basis. The expectation is that the networks with higher prices would be less congested than those with lower prices.

All pricing mechanisms affect user demand, and thus can modify traffic loads. For example, the discount for evening calls on the voice telephone network shifts demand into the off-peak hours, and evens out the load on the network. The PMP proposal is to go further and use pricing as the main method of traffic management.

The PMP proposal was inspired by the Paris Metro system. Until about 15 years ago, when the rules were modified, the Paris Metro operated in a simple fashion, with 1st and 2nd class cars that were identical in number and quality of seats. The only difference was in the price of 1st and 2nd class tickets. (The Paris regional RER lines still operate on this basis.) The result was that 1st class cars were less congested, since only people who cared about being able to get a seat, not have to put up with noisy teenagers, etc., paid for 1st class. The system was self-regulating, in that whenever 1st class cars became too popular, some people decided they were not worth the extra cost, and traveled 2nd class, reducing congestion in 1st class and restoring the differential in quality of service between 1st and 2nd class cars.

The analogy of PMP with the Paris Metro should not be overdrawn. On the Paris Metro, both 1st and 2nd class passengers arrived at the destination at the same time. Different prices paid only for the expected differential in discomfort caused by congestion. In PMP, differences in service quality would be more complicated. For example, packets on lower-priced networks would have a higher chance of being dropped. The main point of the analogy is to show that a simple pricing scheme can induce users to separate themselves into classes that provide different quality of service, and that the division can be self-stabilizing.

Pricing is a crude tool. Different applications vary in requirements for bandwidth, latency, and jitter, for example. PMP would not provide any specific Quality of Service (QoS) guarantees. Unlike ATM, say, it would provide only a few channels, which would have only expected levels of service, not guaranteed ones. Moreover, subdividing a network into several pieces (even when the subdivision is on the logical and not the physical level) loses some of the advantages of statistical multiplexing that large networks offer. The justification for PMP is that, for all its deficiencies, the Internet does work, and with less congestion, even real-time applications can be run. Furthermore, there is no simple characterization of what QoS is required by different applications. The quality of service perceived by users depends in complicated ways on quantitative measures of network performance, and has a large subjective component. Thus there is little hope of satisfying everyone's quality demands. The hope of PMP is that a few classes of service will be satisfactory for most applications, just as a few classes of airline service suffice for most travelers, even though they have varied preferences for leg room, food, air temperature, and other attributes of air travel.

There are experts in the data networking community who argue that instead of working on complicated network schemes, all resources should be devoted to improving capacity (the "fat dumb pipe" model). (See p. 138 of [Huitema] and [Steinberg].) Technology is changing rapidly, and so there is an advantage to simple systems, since they can be developed and deployed much faster. As an example, for all the vaunted flexibility of ATM, it is currently being used primarily to provide "fat dumb pipes" [Steinberg]. ATM happens to be the fastest technology available, so it is deployed even though hardly any of its features are used. However, "fat dumb pipes" by themselves are unlikely to provide a workable solution, since all the evidence shows that with zero marginal costs, traffic will always grow to exhaust capacity. The PMP proposal is close to the "fat dumb pipe" one in the spectrum of possible approaches to network management. However, it brings in economic incentives to provide uncongested pipes (and thus higher quality services) for those who need them.

PMP inverts the usual order in which networks are designed. Usually an attempt is made to determine the QoS required by various application, then the network is designed to provide that QoS, and finally the prices are set. PMP sets the prices, and allows users to determine, based on their requirements and budgets as well as the feedback they receive about the collective actions of other user, what QoS they will receive. The expectation is that the different logical networks would usually have predictable performance and would provide sufficient QoS variety to satisfy most needs.

The pricing mechanism of PMP is about as simple as that of any usage-sensitive pricing scheme that has been proposed for the Internet. Thus the additional complexity it would introduce is minimal, and appears inevitable, since usage-sensitive pricing appears inevitable. The advantage of PMP is that it would provide congestion control essentially for free, once the pricing mechanism is in place, with only minor changes to the network infrastucture being required to handle the traffic management tasks.

The success of the Internet comes to a large extent from its connectionless nature, which simplifies the tasks of both users (who do not need to know anything about how their packets are handled) and networks (which, aside from the issue of routing tables, only have to react to local conditions, and do not need central or even distributed end-to-end coordination). Lack of adequate QoS is now leading the Internet community to consider bandwidth reservation policies such as RSVP. These require network nodes along the path of a transmission to coordinate their actions, and are thus "reinventing telephone technologies" [Steinberg]. The hope is that PMP would permit dispensing with measures such as RSVP and their complexity, and go back to the simpler model of the traditional Internet.

PMP is also designed to be acceptable to users, who have a strong preference for flat-rate pricing. It appears that consumers are willing to tolerate substantial variation in quality of a service or a product, but strongly prefer simple and predictable pricing schemes.

Section 2 presents PMP in greater detail. Section 3 discusses some of the potential problems of PMP, and possible ways to overcome them. Section 4 deals with the transition to PMP. Section 5 sketches the arguments for usage-sensitive pricing of the Internet, and also describes the public's aversion to such schemes, and the way in which PMP might help reconcile the two. Finally, Section 6 briefly outlines some of the other proposals for pricing data networks.

Modeling proposals such as PMP is hard, since our knowledge of the Internet and of user requirements and responses to different pricing schemes is sketchy at best. Appendix 1 presents some simple economic models of the gains that one could obtain from schemes such as PMP. Since there are large economies of scale and a steep learning curve in networking, lower cost service can be secured for all users by providing premium channels that attract additional, QoS-sensitive users. Such users are currently crowded out by the traffic that is insensitive to congestion.

Many aspects of PMP would require extensive research before it could be considered for deployment. This note is only a sketchy initial proposal.

The main idea of PMP is simply to have several channels that differ in price. They would offer different expected quality of service through the action of users who select the channel to send their data on. This section presents some methods for implementing this idea, and also discusses some related issues.

The number of subnetworks in PMP should be small, possibly just two, but more likely three or four. Having few networks minimizes losses from not aggregating all the traffic, and also fits consumer preferences (discussed in Section 5) for simple schemes. Furthermore, it is known (cf. [Wilson]) that in many situations, most of the economic gains from subdivision into different classes of service can be gained with just a few classes. In other, somewhat similar settings, a small number of classes of service has worked satisfactorily. Some railroads in the 19th century had up to four classes of cars, whereas today they operate with one or two. Airlines mostly have either two or three classes of service.

The basic version of PMP mentioned in the Introduction assigns to each subnetwork a fixed fraction of the capacity of the entire network. One can also use priorities. In the proposals [BohnBCW, GuptaSW2], for example, packets with higher priorities would always be treated by a router before packets with lower priorities. The advantage of this approach is that the full gain from aggregating all traffic on one network would be obtained. However, allowing high priority packets to block completely lower priority ones violates the fairness criterion that appears to be important to consumers (see Section 5 for further discussion of this topic). A better approach might be to use weights in routing decisions, such as in the weighted round-robin technique [Keshav]. One could also use different approaches in different parts of the network. One can even mix these approaches on the same link. For example, one could assign 40% of the capacity of the network to class 1 traffic, and 60% to classes 2 and 3, with weighted priority queuing determining what packets in classes 2 and 3 are to be sent first. The fixed assignment of capacities to different classes of service would probably be best for the core of the network.

In general, assignments of capacities and prices to the subnetworks in PMP should stay constant for extended periods. This would fit consumer preferences for simplicity and also allow usage patterns to stabilize, and thus produce a predictable level of service on different networks. However, it might also be desirable to have different assignments of capacities and prices for nights and weekends, to encourage better utilization.

PMP is concerned primarily with the user interactions with the network. It does not specify how traffic management is to be carried out inside the network. Methods such as Fair Queuing can be used with PMP when appropriate, as can IP-switching and tag-routing. Just as some current Internet IP traffic is carried by ATM networks, PMP traffic can be sent over a variety of networks. The intention in PMP is to reduce the traffic management task by inducing users to separate themselves into classes with different requirements. This would eliminate or at least reduce the need for approaches such as RSVP [Huitema, Keshav], which violate the Internet's connectionless approach, and require complicated coordination across the network. However, PMP could be combined with RSVP, if that was felt to be necessary, by having a separate channel devoted to traffic with bandwidth reservations. (One could also carve out RSVP capacity out of the lowest-cost channel.)

PMP is concerned only with usage-sensitive charges for data sent over a network. Currently such charges are infrequent, but there strong arguments (summarized in Section 5) that such charges will be needed for efficient networks that provide the variety of new services that are emerging. Other charges are already common. Flat monthly fees based on the bandwidth of the access link currently pay for most of the Internet. There are also charges for connect time (common in Europe, for example, whereas in the U.S. they apply primarily for access through 800 numbers, or for some online services), which are appropriate when modems or telephone lines have to be paid for. (Such charges would be less appropriate if data splitting equipment is installed, so that data traffic does not use the switches of the voice phone network.) Some charges of these types would be expected to apply in addition to the usage-sensitive charges for PMP (but would be considerably lower than if there was no charge for data loads). (For a survey of different types of Internet access charges around the world, see [OECD].)

PMP would also not deal with some other problems where charging might be appropriate. The only effective way to deal with spam (massive junk email) may well be to impose charges for email delivery. However, a 200-byte spam message takes just as much effort to recognize and delete as a 200-kilobyte message, while the costs of handling a 200-byte message are extremely low. Therefore, to control spam, email charges would have to be considerably higher than the charges imposed by PMP, and should be considered separately.

PMP charges would be assessed on each packet, and would probably consist of a fixed charge per packet and a fee depending on the size of the packet. The combination of these two fees would depend on network costs. Application software would undoubtedly be written to generate packets of sizes that would minimize transmission costs, so the prices would have to be "incentive compatible," in economists' language.

3. PMP problems and solutions

Would users find the lack of guaranteed quality of service (QoS) of PMP acceptable? In voice telephony, experience has taught people to expect a uniform and high level of service. However, that is an exception. Most purchases (of books, cars, and so on) are made on the basis of expected, not guaranteed, quality. (Section 5 has further discussion of this topic.) Today's Internet provides extremely variable and mostly low quality of service. This is only because there is no alternative. Few people are happy with the service they get, and some applications are impossible to implement or perform poorly. This appears to be the driving force behind the numerous proposals to provide quality of service guarantees. (See [JordanJ] for an overview and references.) However, it seems likely that the main problem is not the variability in quality of service on the Internet but the generally low quality of that service. There are fewer complaints about QoS on various institutional LANs and WANs, which do not have any service guarantees, and even the Internet is generally regarded as good in the early morning hours when it is lightly loaded. This suggests that PMP, a best-effort system without guarantees, but with several channels of different congestion levels, might satisfy most needs.

Even though the concept of guaranteed QoS is attractive, it is largely a mirage. The only ironclad guarantees that can be made are for constant bandwidth. That is what voice phone users get, since 64 kbs of network capacity is devoted to each call. In addition, this voice call guarantee only applies to a connection that is established, as there are periods of congestion when call attempts fail. There are also occasional glitches, such as calls being dropped or noise on the line, but they are infrequent enough not to be a problem. In data networks, efficiency depends largely on statistical multiplexing of sources with varying and unpredictable bandwidth demands. However, it is clearly impossible to satisfy all user requirements and take advantage of the efficiency of multiplexing. A 100 Mbs channel can often handle 50 transmissions, each of which requires 1 Mbs on average, but occasionally has bursts of 5 Mbs. However, if many of the bursts occur at the same time, not all the demands can be accommodated. The current TCP forces all transmissions to slow down, which might be regarded as unfair to the sources that are transmitting at low rates. UDP does not slow down at all, which is unfair to TCP users. Many of the proposed schemes (and even existing ones, such as those in Frame Relay networks) guarantee each source 1.5 Mbs of capacity, say. Doing this, however, requires that the network have, if not centralized, then at least closely coordinated control, to set up end-to-end bandwidth reservations. Further, the network and the transmitters have to negotiate for each session. The result for the user, which, after all, should be the deciding factor, is that the perceived performance of the network can degrade suddenly as a result of unpredictable actions of others, when the bandwidth of a connection drops down to the minimal guaranteed level. In particular, applications have to be responsive to network conditions, just as they have to be in a best-effort system like PMP.

Guaranteed QoS is a mirage for another reason as well. For at least the next decade, it appears that ATM will not come to the desktop. Hence most applications (aside possibly from services such as packet telephony, which might use their own network infrastructure) will start out on Ethernet-like networks, which are inherently best-effort.

PMP would do away with the complexity of network control. There would be occasional service degradations, but if they are infrequent enough, this should be acceptable. In PMP, the higher-priced networks would be less congested, and would suffer less frequent service degradation. A service with a minimal bandwidth guarantee of 0.5 Mbs could be simulated by sending the most important 0.5 Mbs (the voice in a videoconference call as well as the high order bits of the picture, say) on a higher-priced channel, and the rest on a lower-priced one. There would be no latency or packet delivery guarantees, but with a sufficient differential in congestion on the two networks, the effect could be comparable to that of conventional networks.

The main potential PMP problem is inefficiency. To provide a higher QoS than the current Internet, the premium networks would need to be less heavily loaded. Would capacity utilization have to be so low as to make the scheme uneconomic? Unfortunately we do not have enough information to answer this question. We do not even know how efficiently the Internet is operating. There have been careful studies of Internet performance (see [MonkC, NLANR, Paxson2, YajnikKT] and especially [Paxson3]), but the difficulties of collecting the data and analyzing it are substantial. There is not even comprehensive and widely accepted data on packet loss rates [Metcalfe]. There are regular workshops on Internet traffic measurement (see [NLANR] for pointers to these and other information sources), but the state of our ignorance about the Internet is astounding. The large network providers do not provide basic data on their total traffic or capacity utilization, and apparently many do not collect careful statistics. It appears that every part of the Internet is a bottleneck, and that the most serious choke points move around. Even such notoriously congested links as the one across the Atlantic do have periods when traffic moves smoothly.

The difficulties in deciding how efficiently the Internet is operating substantial. For the voice phone network, the problem is much simpler. Calls are discrete items, and are either completed or not. The fraction of calls that are blocked provides a precise measure of congestion. The AT&T voice phone network routinely operates at over 80% of its maximal capacity during the peak business hours, and few calls are blocked. However, the total capacity utilization is in the 15-20% range, since there are few calls in the slack periods. (It is worth mentioning that although these are precise figures, they are based on the idea that a phone call is 64 kbs. With compression, much lower transmission capacity would suffice. Thus even in the phone network the measurement of capacity utilization is not easy.)

On the Internet, capacity utilization is much harder to define. The statistics for the NSFNET compiled by Merit (and available through the links at [NLANR]) show that this backbone, towards the end of its existence, when it consisted exclusively of T3 lines, transmitted data at a rate that was only about 5% of the link capacity. What this presumably means is that the bottlenecks were elsewhere, most likely at the routers, or at the links connecting to the backbone. We do not know what the true capacity utilization was.

There are also problems in interpreting current Internet statistics. For example, consider the 15-minute average throughput data for the PacBell NAP for the period Aug. 3, 1997 to Aug. 27, 1997, available through the links at [NLANR]. After removing the data for Aug. 14 and 15 (when apparently the entire NAP was down for a few hours), we find that the minimum transmission rate was 50.3 Mbs, maximum was 309.4 Mbs, average was 222.3 Mbs, and the standard deviation was 48.0 Mbs. Thus the average transmission rate was 72% of the maximal one, much higher than for the phone network. Remarkably enough, the statistics for just Saturdays and Sundays during that period show figures of 107.8, 273.3, 205.5, and 41.3, respectively. This is again in contrast to the voice phone network, where there is little traffic on weekends. Similar utilization profiles apply to the other major switching points for which data is available at [NLANR].

One conclusion that could be drawn from these statistics is that the Internet is much more efficient than the voice phone network, with capacity utilization of over 70% as against 15-20%. However, such an argument is easy to question. For one thing, the maximal transmission rate through a node on the Internet under normal conditions is much less than the theoretical throughput. This is because data traffic is fractal [LelandTWW] (an observation that was first made in LANs, and has now been confirmed in many other data networks). This suggests that all data networks with heterogeneous sources will use only a fraction of their capacity, a considerably smaller fraction than the phone network does. There are further complications. Taking the ratio of observed average traffic to observed maximal traffic is a misleading utilization statistic, since the observed maximum is small compared to capacity. Further, observed traffic is not the same as useful traffic. When packets get lost, they are retransmitted (when using TCP, for example), which inflates traffic counts. The retransmission problem gets worse precisely when congestion increases. (The TCP acknowledgement packets appear to pose less of an overhead, but the routing information that is constantly being transmitted is another burden.)

Probably the main conclusion that can be drawn from available traffic statistics is that the Internet is terribly congested, and that it is extremely inefficient in the social and economic sense by repressing demand. Some of the apparently high utilization rate that is observed for the PacBell NAP, for example, is caused by the desirable shift of large data transfers (such as in mirroring databases) to the slack night hours. Most of it, though, appears to be caused by not satisfying existing and potential demand for data service. There is some data available through [NLANR] on packet loss rates, which are one indication of congestion. That is not the full story, though. Most of the Internet traffic is TCP, which uses variants of Van Jacobson's backoff algorithm (introduced in 1988 to prevent another collapse of the type that the Internet had suffered then). This algorithm slows down individual transmissions in the presence of congestion. Further, this algorithm has the effect of slowing demand from users, who, as a result of slow transmission, do less work on the Net than they could otherwise. Therefore the actual demand for data transmission is probably much higher during peak hours than is apparent from the statistics.

One indication of the repressed demand for Internet service is provided by comparing modem usage with traffic statistics. Data from an ISP show that the average number of modems in use is about 30% of the maximum number, a pattern of usage closer to that of the voice phone network than of the transmission pattern through the NAPs, say. This shows that it is not that traffic demand is more even on the Internet than on the voice phone network. Instead, what we are seeming is the result of severe congestion and rationing.

We are all familiar with highway traffic, when cars are moving smoothly, and then a sudden perturbation leads to a jam. It is a general phenomenon of queuing systems that close to a critical point, small increases in utilization can yield dramatic deterioration in service quality. Consider the simplest system, the M/M/1 queue. If the average throughput is increased from 90% of maximum feasible to 99%, the average queue size will grow from 9 to 99, and therefore the average time spent waiting in the queue will grow by the same factor of 11. Conversely, if we decrease utilization from 99% to 90%, by less than 10%, queue size and the time waiting in the queue will both decrease by a factor of 11. Note that such dramatic increases in service quality at small costs of efficiency are possible only near the critical point. If the M/M/1 queue is operating at 50% of maximum throughput, an 11-fold decrease in average queue size is possible only by going down to a utilization rate of 1/11, a 5.5-fold decrease.

The analogy should not be overdrawn, but the data cited earlier suggest that the Internet is operating closer to the 99% utilization level than to the 50% level in a queue. Looking at queue sizes in routers may be misleading, since most of the demand reduction is probably coming from the automatic action of TCP and users' reactions. Real congestion may be much worse. If this is true, small decreases in network utilization might lead to dramatic improvements in perceived QoS. The problem is how to achieve and maintain such a reduction. Usage-sensitive pricing would provide an incentive for users to keep their traffic demands from clogging the network, and also for service providers to build the capacity that there is demand for.

Much better data on the perceived quality of service as a function of capacity utilization is needed to determine how well PMP would perform. The hope that PMP would not require extreme overengineering of the network is supported by the observation that during the night and early morning, the Internet provides much better perceived service than during the busy hours. However, the load carried by the Internet does not vary much, as is shown by data cited before for the NAPs.

Various additional aspects of PMP that are important for its operation will not be dealt with here, as they would require further study, but do not seem to be crucial. For example, how does a network that implements PMP interoperate with one that does not? (A simple rule might be to send all traffic from a network that does not use PMP on the lowest priority subnetwork, but other rules could be more appropriate.) How would revenues be split among different service providers? Also, one would need to provide facilities for either the sender or the receiver to pay for the transmission, a problem that also occurs in other schemes. Both these problems have been considered in the literature for other pricing schemes. How frequently would the capacities and prices of different subnetworks in PMP vary? (In particular, should there be off-peak discounts, given that the Internet is a global network, and peak hours might occur at different times in different regions?)

The remainder of this section concentrates on a few aspects of PMP. One crucial problem is how to set prices and capacities of the separate networks. This is a difficult problem in general. However, it should not be too difficult to get nearly optimal solutions. Aside from relying on customer surveys and user complaints, one could obtain the necessary data from time of day variations in traffic patterns. I suggest that prices and capacities of the networks should stay constant for extended periods, to provide the predictability of price and service quality that consumers like. (However, one might allow for some time of day price variations, such as the evening discount on long distance phone calls). Since consumers could choose for each packet the network to send it on, I expect that some would go by some general expectation of quality of service for different networks, while others would hunt (using software on their computers) for the cheapest way to satisfy their requirements. The latter class would serve a role similar to that of speculators in commodity markets, who provide liquidity. The natural variation in total demand for transmission with time of day would lead these users to shift their demand among different channels. This should allow network operators to deduce what the distribution of consumer demands and valuations is.

For the PMP proposal to work, the performance of the different networks has to be predictable, at least on average. Unfortunately, the fractal nature of data traffic [LelandTWW] means that we have to expect that all PMP channels will experience sporadic congestion. All we can expect is that the higher-priced channels will experience this service degradation less frequently. This could lead to network instability, with degradation on one channel propagating to other channels. For example, an extended congestion episode on the lowest-priced channel might lead a large fraction of users of that channel to decide to pay extra and send their packets to the higher-priced networks, which would then become intolerably congested. There are several ways to overcome this problem (should it turn out to be a serious one). One is by modifying the charging mechanism. Access to the premium channels might be not on a packet-by-packet basis, but instead the user would pay for the right to send 1,000 packets on that channel in the next second. This would increase the financial barrier to upgrading channels.

Another way to lessen the instability problem is to promote segregation of different types of services on different networks. For example, the lowest-priced network (where the price per packet might be zero, as mentioned before) could have artificial delays and packet losses induced by the network operators, to make it unusable for videoconferencing, say. (For example, the capacity of the lowest-priced channel could be lowered in slack times by requiring that packets in that channel spend some time in the buffer before being transmitted.) This would be analogous to the policies of various companies. For example, Federal Express has next-day delivery and "next-day-by-10am" delivery. Regular next-day delivery packages that are available for delivery at 10 am are not delivered then, but in a separate trip in the afternoon. This type of approach, referred to as "damaged goods," has been studied by Deneckere and McAfee [DeneckereM], who show that it is common in high-tech industries, and that it often serves to promote social welfare. (This approach appears to be especially suited for trade in information goods. See [Odlyzko, Varian2].) Methods of this type could be used to induce a more even load on the separate networks, and thus compensate for some of the potential difficulties.

4. PMP implementation

The PMP proposal can be regarded as a logical development of some current trends. Various Internet service providers (ISPs) are planning to distinguish their networks through higher quality of service (QoS), and plan to charge extra for that. Customers with connections to several ISPs would then have a choice similar to that in PMP. S. Keshav has pointed out that MCI is planning a network for business customers that would be physically separate from MCI's regular network for individuals. MCI customers who sign up for both networks will then have a limited version of PMP available to them. The PMP proposal would simply let each ISP offer its customers an array of choices that they might have available through different ISPs anyway, and should therefore be more efficient.

PMP would be easy to introduce. It would not be necessary to wait for the deployment of IPv6 [Huitema] or other protocols. The current IPv4 packets already have a 3-bit priority field that is unused. (It was used for only a brief period a decade ago [BohnBCW, Bailey].) Since the number of networks in PMP is likely not to exceed 4, this is more than sufficient. Interoperability would be easy, as all packets that do not contain any bits indicating class of service could be sent on the lowest cost (and lowest priority) network.

At least initially, the cost per packet on the lowest cost network would undoubtedly be zero. There are strong arguments (see Section 5) for usage-sensitive prices even on this network, but zero prices would make this network look like the current Internet, and so make the transition easier. It might also be possible to have zero prices on this network in the long run during slack periods.

Eventually applications, such as videoconferencing software, would be rewritten to give users the choice of network (and thus of quality of their transmission channel) from within each application. Since that would take time, initially one would need to write "wrapper" software that would handle all IP traffic on a user's machine and set the priority bits to the level specified by the user. Network administrators would have a chance to police users' behavior at the firewall. For example, a university might reset priorities of packets coming from students' computers to that of the lowest class.

Inside the network, changes would only have to be done in the router software. It would be necessary to maintain logically separate queues or to give appropriate priority to packets from different channels.

The major change required in a network by PMP is the same one as that needed for any usage-sensitive pricing scheme. It would be necessary to install hardware or software to count the packets and bytes for each user. Essentially all of this accounting could be done at the edges of the network, although there would probably have to be some measurement at the inter-ISP gateways. This task could be simplified by using sampling. Unlike some other pricing schemes, PMP would not require any detailed accounting or pricing decision to be made in the core of the network, where speed of operations is the greatest requirement, and so simplicity is desirable.

There is often a chicken and egg problem with introduction of new network services. They require users to justify introducing the service, but there are no users until the service is widely deployed. PMP could be implemented within a single ISP initially, and used to provide substitutes for private line and Frame Relay services for large organizations that have several facilities in areas covered by that ISP.

As with most other pricing schemes, there are still areas requiring further research. For example, how should one charge for multicasting? (Cf. [HerzogSE].) It would also be necessary to arrange for 800-like services, in which the receiver pays. These have already been considered in the literature, and the authenticated transactions required for them can also be carried out just by the service providers at the edges of the network.

5. The irresistible force runs into the immovable object

The need for usage-sensitive pricing appears to be irresistible. It has impeccable economic logic as well as increasing practical evidence behind it. Unfortunately, it collides with users' unshakeable preference for flat-rate pricing. The problem is how to reconcile the two.

The case for usage-sensitive pricing of the Internet has been ably made many times already, for example in [Clark2, GuptaSW4, MacKieMV1, MacKieMV2, Shenker1, Shenker2, ShenkerCEH]. The basic problem is that the demand for transmission capacity appears to be practically unlimited, especially as high bandwidth services are developed. This guarantees a continuation of the nearly constant congestion we are experiencing right now. This congestion will make many novel services, such as teleconferencing, impossible, as data transfers that are insensitive to delay continue to crowd out all other traffic.

The basic argument in favor of usage-sensitive charges is magnified by the many incentives for Internet users to behave in ways detrimental to other users, an example of the "tragedy of the commons." When America Online switched to flat-rate pricing at the end of 1996, its system could not cope with increased demand. As it became harder for users to get a new connection, they started leaving their connections open even when they were not doing anything, seriously aggravating the problem. For America Online, the problem was a shortage of modems, which would not have been alleviated by charging for packets sent. However, similar perverse incentives exist on the Internet to increase data transfers. To get better performance from the "World Wide Wait" while Web surfing, tools such as PeakJet use the time that a user spends looking at a Web page to download all pages linked to it, so that if the user decides to read one of them, it can be fetched quickly from a local disk. The worse the congestion, the greater the incentive for individuals to employ such tools, and many servers have experienced overloads as a result. Similarly, there is an increasing temptation to use systems such as WebWhacker. This program can spend a whole night downloading Web pages to the hard disk of a PC, just in case that PC's owner wants to spend a few minutes looking at a small selection of those pages the next day. While so far only local congestion problems have been documented that are caused by PeakJet, WebWhacker, and similar systems, their widespread use would overwhelm the current Internet. Most computers on average use only a small fraction of the capacity of their link to the Internet. PeakJet and WebWhacker exploit the full available bandwidth. It would take fewer than 200,000 PCs (under 1% of all networked PCs) connected at 28.8 Kbs to saturate the current Internet (which is estimated to have a capacity of about 5 Gbs) if all were downloading Web pages at a steady 28.8 Kbs rate. There is nothing wrong with PeakJet and WebWhacker per se, as they can be useful, especially when the user has urgent tasks and the local connection to the Internet is slow. The main problem with such tools is that with flat-rate pricing, they create incentives for users to rely on them indiscriminately, even when the benefit to those users is minor.

In general, the survival of the Internet owes much to altruism and ignorance. There are all too many incentives for users to abuse the system. These incentives are growing, and as the user population becomes increasingly heterogeneous, less inclined to cooperate. The official TCP standard requires transmissions to slow down when congestion occurs, and the Internet would collapse without this feature. However, there are many faulty implementations of TCP that are already deployed, and if they were used more widely, the Internet would almost surely suffer congestion collapses [Paxson1]. Further, there is no effective method to prevent the creation and use of rogue versions of TCP, which would speed up transmission of packets when they encounter delays or packet losses. Such versions would provide better service to their users (as long as not too many others follow the same strategy and cause a collapse), and in a flat-rate pricing environment would not cost those users anything extra.

Even without unintentionally defective or rogue implementations of TCP, the Internet is already threatened by the growth of services that use protocols such as UDP, which do not slow down transmission in the presence of congestion [BradenFM]. Usage-sensitive pricing could provide incentives for cooperative behavior. If every packet incurred a charge, sending two copies of a packet to cope with network losses would double the cost of the transmission, and induce marginal users to postpone or abandon their transmissions.

Usage-sensitive pricing would also play a useful role in providing incentives to service providers to build adequate capacity in the core of the Internet. It is estimated that ISPs currently spend only about a third of their budget buying bandwidth. Gains in market share appear to be the highest priority, and providing good connectivity to existing customers is secondary. This is only to be expected with the current flat-rate scheme, since revenues depend only on the number of users.

Consumer usage as well as satisfaction with good or services depend in large part on their subjective reactions to pricing schemes (cf. [Brittan]). In particular, while the arguments for usage-sensitive pricing seem to be irresistible, they run into users' seemingly immovable preference for flat rates. This preference has attracted considerable attention recently, especially when America Online was forced to offer such a plan. However, there are many earlier examples in the online world, as when services such as Prodigy and CompuServe were forced to stop charging for individual email messages. Large organizations also show a strong preference for flat rates. The introduction by the U. S. Defense Data Network of usage-sensitive pricing resulted in the different branches of the U. S. armed forces building their own networks [Bailey]. This preference for flat rates is not unique to data networking. It is a general phenomenon that was probably first explored and documented in the context of pricing of local telephone calls in the Bell System in the 1970s [CosgroveL]. In practice, what it means is that consumers are willing to pay more for a flat-rate plan than they would under a per-user pricing scheme. This preference is being exploited by various businesses, to the extent that there is even a utility that offers an annual supply of natural gas for heating for a flat fee. (The fee is based on the previous year's usage, with surcharges or refunds if consumption deviates by more than 20% from the expected level.) As was already recognized in [CosgroveL], there appear to be three main reasons for the preference for flat rates:

Flat rates are preferred by consumers, but they also have major advantages for service providers. They were already advocated for broadband services by Anania and Solomon in [AnaniaS], a paper that was first presented almost a decade ago. On the Internet, they eliminate the need for a traffic measurement and charging infrastructure, which, even for a system such as PMP, where almost all the work would be done at the edges of the network, would be costly to implement. (Flat rates often have socially desirable effects, as well. In pricing of household garbage disposal, they decrease dumping of garbage, for example [FullertonK].)

Flat rate pricing often allows service providers to collect more revenue. This is often true even when the user preferences mentioned above (which are hard to incorporate into conventional utility maximization arguments) are ignored. In general, flat-rate (or subscription) pricing is likely to be dominant in sales of information goods [BB, FishburnOS, Odlyzko, Varian1]. The conventional economic utility maximization arguments show that the advantages of bundling strategies (selling combinations of goods for a single price) increase as marginal costs decrease (cf. [BakosB]). Even sales of software are likely to be more profitable in the conventional arrangement of a fixed fee for unlimited use than on a per-use basis [FishburnOS]. However, all those predictions are for goods and services with negligible marginal costs. Moreover, there are often positive network externalities that strengthen the case for subscription or site licensing plans. For example, a software producer benefits from users recruiting other users, generating enhancements to the basic package, and so on.

While there are strong arguments, such as those mentioned above, that flat-rate pricing will be increasing as electronic commerce grows, those arguments have limited applicability to data network pricing. What makes flat-rate local calling plans feasible is that making a call requires time from the consumer. As a result, most households make only about 5 local calls per day (of about 4 minutes each). There would be no monetary cost for making more, but there would be a cost in time. Similarly, demand for natural gas for heating does not vary too much with price, since for most homes, the price of gas is not a huge part of the budget, and maintaining a temperature of 90 degrees Fahrenheit appeals to few people. Internet access is different, since the usable bandwidth is growing, and computers can keep a link occupied even in the absence of human intervention. Marginal costs are still negligible. However, there are substantial negative network externalities. If Alice uses a word processor, that does not preclude anyone else using it, and her usage is likely to benefit others, who will be able to share files with her and consult her about bugs. When she sends a packet, though, it can only impede other users' transmissions. Therefore usage-sensitive pricing does seem to be necessary. The problem is how to make it palatable to users.

Consumers have long accepted a variety of usage-sensitive rates. In the United States, long distance phone calls have largely been paid for on a per-use basis, and in most of the rest of the world even local calls have traditionally incurred charges. While there is a tendency towards flat rates in general, as marginal costs diminish and it becomes easier to satisfy consumer preferences, this trend is not universal. For example, Federal Express and United Parcel Service are moving towards charging for delivery of express mail according to distance, instead of using a flat fee. Even in Internet transmissions, there have been many instances of charging for the amount of transmitted data [Brownlee, OECD]. Such usage-sensitive pricing appears to be spreading for large customers in the U.S., with UUnet, MCI, and other carriers offering them. Many ISPs have declared that they intend to move away from flat rate pricing for individuals. It seems it should be possible to persuade users to accept usage-sensitive pricing, especially if the benefits are made clear. PMP should make the transition easier than with most other schemes, since the lowest-priced channel could be offered initially at zero cost per packet, and would thus behave just like today's Internet.

In PMP, the preference for flat-rate pricing can be partially accommodated by selling large blocks of transmission capacity (giving the user the right to send or receive 100 MB of data over a week through the lowest priced channel, or 60 MB through the next most expensive channel, say). Such pricing has worked well in long distance telephony in the United States, with consumers typically paying for more capacity than they used [MitchellV].

PMP offers a simple pricing plan with constant and easily understood pricing, which is an advantage, as it fits consumer desires. It does not offer any service guarantees, however. Such guarantees are popular. L. L. Bean has developed an enviable reputation, partially as a result of its no-questions-asked return policy. Cable TV companies are trying to improve their notoriously bad customer relations by offering days of free service when interruptions occur. Marketing of telecommunications services to large corporate users also increasingly relies on guarantees of features such as availability and data delivery delays. However, few guarantees are absolute, and most purchases are made on the basis of expectations. The restaurant meals and books we buy, the movies we go to, even the clothes we purchase after trying them on in a store, all involve large elements of uncertainty about the quality we experience. When we subscribe to a newspaper or a magazine, neither we nor the editors know in advance precisely what we will get. Expectations, based on our own experience, word of mouth recommendations, and other sources, is what we rely on. Moreover, consumers are willing to accept occasional large deviations from the expected quality of service. An airplane passenger in first class may have an uncomfortable trip, if there is a sick and crying child in the seat behind. On the other hand, a coach passenger may have three seats to herself, enough to stretch out and get a good night's sleep on a trans-oceanic flight, and have a much better experience than those in first class. On average, though, a first class ticket does provide superior service, and that is enough to maintain a huge price differential. It seems likely that consumers could accept the lack of guarantees of QoS in PMP, especially if the average quality of different channels were predictable enough.

Consumer and business behavior is often hard to fit into the standard economic framework. A puzzle of modern economics is the reluctance of businesses to use price overtly as a method of rationing popular goods or services. With some minor exceptions, ski-lift ticket prices do not depend on the quality of the snow, nor on whether it is the peak vacation season. Opera tickets usually do not depend on who the lead singers are, and admission prices to first-run movies do not depend on the length of ticket lines. For some reason, free enterprise companies prefer the socialist method of rationing by queue to that of rationing by price. This appears to reflect a general public aversion to the auction mechanism. During the oil crises of the 1970s, bizarre gasoline rationing rules that were (correctly) derided by economists as ineffective and inefficient were popular with the public. Laws against ticket scalping are common, and are widely supported. Yet, to most economists, scalpers fulfill a socially useful role of getting tickets into the hands of those who are willing to pay the most for them. The main puzzle for most economists in this area seems to be that scalpers can make a living. Why don't theaters and sports arenas simply adjust ticket prices to clear the market and appropriate to themselves some of the gain that the public or the scalpers obtain? However, that is simply not done, except in unusual circumstances. There have been attempts to explain this phenomenon using conventional economic utility maximization arguments (cf. [BarroR]), but they are not entirely convincing. It seems likely that the cause lies more in the realm of consumers' seemingly irrational economic behavior, whose study was pioneered by Kahneman and Tversky. The challenge is to design pricing schemes that approach the goal of efficiency that can be achieved by auction mechanisms, and yet do respect consumer aversion to the auction.

A particularly important role in consumer behavior in the economic and political arenas is played by the notion of fairness [Odlyzko, Zajac]. Fairness is likely to play an increasing role in electronic commerce. Decreasing marginal costs are increasing the incentives for sellers to impose artificial barriers, and at the same time the nature of electronic commerce makes it much more apparent to consumers that the barriers are artificial. Therefore it will be increasingly important to convince consumers of the fairness of pricing schemes. In the design of PMP, assigning fixed capacity to different subnetworks is likely to appeal to consumers more than some of the priority schemes mentioned in Section 2. It avoids the appearance of an auction, in which users willing to pay higher prices hog all the bandwidth. It also throws the onus for congestion on other users, and not on the network provider, which again seems to be more palatable.

6. Other pricing proposals

Several proposals have been made for usage-sensitive pricing. Extensive information can be found on the Web site [Varian0] and in the collection of paper edited by McKnight and Bailey (of which the reference [AnaniaS] below is one). Further references, short summaries, and criticisms can be found in [Clark1, Shenker1, ShenkerCEH]. Here I only make a few remarks on the main features of some of these proposals, and how they compare to PMP.

Among the earliest and most influential pricing proposals is that of MacKie-Mason and Varian [MacKieMV1, MacKieMV2]. (A preprint with their scheme had circulated much earlier. For extensions of their work, see also [LehrW].) They propose imposing charges on packets when those packets contribute to congestion. In particular, charges would be zero when the network is not fully utilized. Their Vickrey auction mechanism has some desirable properties. However, as is pointed out in [Clark1, ShenkerCEH], for example, it requires complicated systems to conduct an auction among individual packets (which, moreover, would be most involved in the core of the network, where simplicity is of highest value to obtain high speed of operation). In addition, this proposal does not deal with the problem that delay or loss of an individual packet at a single node is not a good measure of network performance for most applications. Further, since a packet typically goes over a dozen or more routers, in the absence of global information about all routers on the path, how could the user decide how much to bid to get through the first router on the path? Finally, in terms of meeting customer preferences, the MacKie-Mason and Varian proposal is likely to be unsatisfactory, since it is impossible to predict how much it will cost to transmit any single packet.

The Gupta et al. proposal [GuptaSW1, GuptaSW2, GuptaSW3, GuptaSW4] is (oversimplifying a lot) to have a set of service classes and priorities. As is pointed out in [Clark1, ShenkerCEH], there are problems with this approach, among them that low priority classes could fail to get any bandwidth at all if enough traffic from higher priority classes show up. The scheme also has substantial overhead. It requires collecting and processing extensive information about the network.

The schemes that are closest to PMP are those advocated by Clark [Clark1, Clark2] and Shenker et al. [ShenkerCEH]. These authors point out that quality as perceived by consumers is not just a matter of minimizing packet delays or losses, but depends on the application, and is hard to quantify. It is also highly unlikely that an optimal policy can be found that would deal with the varied requirements of a heterogeneous user population and many different services. Those authors argue for edge pricing (i.e., charging at the entrance and exit from the network, not based on what happens at internal nodes, as is required by the MacKie-Mason and Varian proposal), which is a feature of PMP. They also argue for at least some variant of Clark's proposal of charging for expected usage, with those portions of a consumer's offered load that deviate from negotiated statistics being treated at lower priorities. (This part is similar to another proposal of Kelly [Kelly].) The problem with charging for negotiated usage profiles, just as with applications of future markets to networks, is that they do not deal with the inevitable short-term fluctuations in traffic. It is desirable to provide incentives for users to either lower their load on the network or else switch to a higher-priced network when congestion occurs.

Feng, Kandlur, Saha, and Shin [FengKSS1, FengKSS2, FengKSS3] have proposed implementing services such as controlled-load and guaranteed service (cf. [BradenCS]) without end-to-end network coordination. They use adaptive packet marking with two classes, with higher priority packets treated preferentially at the routers, to provide soft guarantees of QoS. They are not concerned with pricing as such, but appear to assume a variant of Clark's scheme of charging for expected usage. In many ways their proposal is similar to PMP in lack of hard QoS guarantees and having separate classes of packets. However, they assume more intelligence in the network (changing marking of packets, for example) and have just two classes of packets. Their main concern is with modifying TCP to accomplish their goals.

Acknowledgements: I thank Jerry Ash, Vijay Bhagavath, Steve Bellovin, Kim Claffy, Kerry Coffman, John Denker, Nick Duffield, Bruce Emerson, Anja Feldmann, Philippe Flajolet, John Friedman, Paul Ginsparg, Albert Greenberg, Paul Henry, Andrew Hume, Chuck Kalmanek, S. Keshav, Chuck McCallum, Nick Maxemchuk, Rodolfo Milito, Deborah Mills-Scofield, Gerry Ramage, Jennifer Rexford, Paul Resnick, Don Towsley, Greg Wetzel, Walter Willinger, and Pat Wirth for comments on an earlier draft or providing useful information. References:

Appendix 1. Gains from network segmentation
(Note: This appendix looks much better in the typeset version.)
Various aspects of PMP require additional study and modeling.  Here we
consider only some simple models of the gains that can be obtained by
having logically separate networks that operate at different
utilization levels.  These models are crude and are not specific to
PMP. Any other scheme that exploits the economies of scale of
aggregating traffic with different utilization levels would provide
comparable benefits in this model.  For an example of other types of
economic models dealing with pricing in data networks, see
[CocchiSEZ], for example.  Still, even these models may shed some
light on how benefits of better data networks would be divided.

We will assume that there are two types of demands for data transport.
Users (generally processes, and not individuals) will be assumed to
fall into types A and B. Type A users might correspond to bulk file
transfers that are not sensitive to delays.  We will assume that when
the price is x (per byte, say), type A users will wish to send

            a / ( x exp(x) )                                       (A1)

bytes (per day, say).  They will then generate network revenues of

            a exp(-x).                                             (A2)

This is an unconventional model, but might not be unreasonable for
data traffic, with total demand limited primarily by general budget
constraints at low prices.  Note that historically, prices of data
transmission have been dropping, but total spending has been climbing.
We will assume that the cost (the ongoing operational cost, as well as
depreciation and profit, which will be assumed to be limited by
competition) of operating a network that carries w bytes is

           c * w^{3/4}                                             (A3)

for some constant c > 0.  This is a conservative assumption, since it
corresponds to less than a 16% reduction in costs when the network
doubles in size (2^{3/4} = 1.68179...).  The economies of scale faced
by a single ISP that moves from purchasing T1 lines to T3 lines or the
learning curve experience faced by the network equipment manufacturers
justify assumptions of even higher reductions in costs, which
correspond to exponents even lower than the 3/4 assumed above.

With the above assumptions, if there are only type A users, we expect
the cost of the network to equal the revenues, so that

     a exp(-x) = c * ( a x^{-1} exp{-x} )^{3/4},                    (A4)

which is equivalent to

            x^3 exp{-x} = a^{-1} c^4.                               (A5)

The unique maximum of x^3 exp{-x} occurs at x=3 and equals 27 exp{-3}
= 1.344250....  Hence for combinations of a and c with c^4 > 27 a
exp{-3}, (i.e., high costs of network compared to demand), there is no
price x that will recover costs, and so the network will not be built.
For c^4 < 27 a exp{-3}, there will be two solutions for x, and it is
the smaller one, call it xA, that will be preferred, since it
corresponds to higher revenue and higher traffic.

Suppose that there are also type B users, who will only use a network
when its utilization rate is at most half of that acceptable to type A
users.  (This is a pessimistic assumption, since it seems likely that
much smaller reductions in network loads would suffice to produce
substantial improvements in service.)  Suppose that at price x, they
will generate traffic of

           b x^{-1} exp{-x}.                                       (A6)

Constructing a separate network for these users will cost

       c ( 2 b x^{-1} exp{-x} )^{3/4}                              (A7)

(the 2 coming from lower utilization rate), and bring revenues of

           b exp{-x}.                                              (A8)

Thus in this case the price x that equalizes revenue and cost is a
solution to

        x^3 exp{-x} = 8 b^{-1} c^4                                 (A9)

(provided it exists, which happens when 27 b >= 8 c^4 e^3).  We will
use xB to denote the minimal solution to (A9).

Suppose a single network with a single price were to be built for both
type A and type B users.  Then its average utilization would have to
be half that of a network meant for type A users alone, and so at
price x would have revenue

             (a+b) exp{-x}                                        (A10)

but cost

       c ( 2 (a+b) x^{-1} exp{-x} )^{3/4}.                        (A11)

Hence the price x that equalizes cost and revenue would have to

       x^3 exp{-x} = 8 (a+b)^{-1} c^4.                            (A12)

We let xAB denote the minimal solution to (A12) (when one exists,
which happens precisely for 27 (a+b) >= 8 c^4 e^3).  We note that if b
> 7a, so demand from type B users is large compared to that of type A
users, type A users will benefit by having lower prices than if they
had their own network, since xAB < xA.  If b is small compared to a,
though, then even if xAB exists, xAB will be larger than xA, so type A
users will be paying more than if they had their own network.  They
will also get better service, but the assumption is that they do not
need it.  (Note that type B users will always benefit from having type
A users on their network, as prices will be lower, reflecting greater
economies of scale.)

Suppose finally that we can have two networks for type A and type B
users that are logically separate but physically part of the same
network.  We also assume that the provision of the logical separation
imposes negligible additional costs.  Then, if the price for type A
users is set at y and those of type B at z, revenue will be

           a exp{-y} + b exp{-z}                                  (A13)

and the cost of the network will be

       c ( a y^{-1} exp{-y} + 2 b z^{-1} exp{-z} )^{3/4}.         (A14)

Prices y and z now need to satisfy

      a exp{-y} + b exp{-z} =
   c ( a y^{-1} exp{-y} + 2 b z^{-1} e^{-}z )^{3/4}.

Since we have two prices to select, we have more freedom of choice.
By letting y -> infinity or z -> infinity we can reduce to networks
that cater exclusively to type B and type A users, respectively.
Intermediate choices are more interesting, though.  We consider a few

Example 1.  a=b=3, c=1.

We have xA = 0.9524456..., xAB = 2.784204..., while xB does not exist.
The network for type A users only produces traffic of 1.215175..., and
revenues of 1.157389...  (in the arbitrary units we are using).  A
single network for type B and type A users would produce revenue of
0.3706693...  from traffic of 0.133132..., and so clearly would not be
built, since both type A users and service providers would be much
better off with a network just for type A users.  On the other hand,
consider a single physical network that has separate channels for the
two types of users.  Setting prices y= 0.9 and z= 1.33865...  leads to
total traffic of 1.942837...  (about 1.355 of type A and 0.587 of type
B) and total revenues of 2.00630..., 1.2197...  from type A traffic
and and 0.78659...  from type B traffic.  Note that the gain to type A
users from a network that accomodates type B users is relatively
slight.  The price they pay is reduced only by 5.5%.  (The prices y=
0.9 and z= 1.33865...  were selected to be close to those that
maximize total revenue.  Lowering the price y substantially below 0.9
quickly leads to declining revenues and soon after that there is no
choice for z that will satisfy Eq. (A15).)  The main benefit goes to
type B users, who are offered a service they are want at a price they
are willing to pay, and to network providers, whose revenue (and
presumably profit) grows by 73%.

Example 2.  a=20, b=10, c=1.

Then the optimal prices are xA = 0.424384..., xB = 1.56303..., and xAB
= 0.85627...  for networks designed for type A traffic only, type B
traffic only, and both types on the same network, respectively.  We
next consider a single physical network with logically separate
networks for the two types of traffic.  Total revenue is maximized
with prices close to y=0.42 and z= 0.606846....  The traffic and
revenue results of this choice for prices is shown in Table 1.

        Table 1.  Traffic on various networks in Example 2

                network          traffic       revenue

                A only           30.8293       13.0834

                B only            1.3403        2.0950

        A+B on single network    14.8809       12.7422

           A+B on logically      40.2699       18.5916
           separate networks

As in Example 1, type A users experience a slight gain, while type B
users find their price drops by a factor of 2.5 (compared to relying
on a totally separate network just for their own traffic).  Networks
operators have a revenue gain of 22% (compared to running separate
networks for the two types of users).

Example 3.  a=10, b=20, c=1.

Then the optimal prices are xA = 0.55928..., xB = 1.04321..., and xAB
= 0.85627...  for networks designed for type A traffic only, type B
traffic only, and both types on the same network, respectively.  A
single physical network with logically separate networks for the two
types of traffic and prices y=0.53 and z= 0.69381...  results in
higher traffic and revenues, as is shown in Table 2.  A
revenue-maximizing network provider would be almost indifferent
between having physically separate networks for the two types of users
and a single one that gives all traffic the quality of service
demanded by type B users.  (Type B users would benefit from having a
single network, type A users would lose from it.)  However, a single
physical network with logically separate channels would increase
revenues by 24%.

           Table 2.  Traffic on various networks in Example 3

                network          traffic       revenue

                A only           10.2206        5.7162

                B only            6.7545        7.0463

        A+B on single network    14.8809       12.7422

           A+B on logically      25.5093       15.8794
           separate networks

In all these examples, gains to type A users are small.  This may help
to explain why there has not been more pressure from users of the
current Internet (whose applications almost by definition have to work
reasonably well even in the presence of congestion) for higher quality
of service.

In the three examples above, a and b are comparable, which means that
the potential traffic from users of types A and B is assumed
comparable.  This might seem unrealistic, given that the bulk of
current Internet traffic appears to be insensitive to congestion.
However, the current distribution of traffic is unlikely to be typical
of what would be seen if choices were offered.  Much of Web surfing
would surely move to higher-priced channels if those provided better
quality of service.  Furthermore, while the Internet is large and
growing rapidly, it is still dwarfed by the private line and frame
relay networks.  Large fractions of the traffic from those networks
could be diverted to the Internet if the latter could be improved.