EPUBs are an experimental feature, and may not work in all readers.

Presented at MIT Workshop on Internet Economics March 1995

Abstract

We describe a simple charging and accounting mechanism for bursty high-priority connections, based on their effective bandwidths. A connection provides whatever traffic information it happens to have, essentially through its choice of charging regime. The mechanism thus performs the dual role of conveying information to the network that allows more efficient statistical sharing, and feedback to the connection about the congestion that it is causing.

1 Introduction

The usage of a network resource may not be well assessed by a simple count of the number of bits carried. For example, to provide an acceptable performance to bursty sources with tight delay and loss requirements it may be necessary to keep the average utilization of a link below 10%, while for constant rate sources or sources able to accommodate substantial delays it may be possible to push the average utilization well above 90%.

What is needed is a measure of resource usage which adequately represents the trade-off between sources of different types, taking proper account of their varying characteristics and requirements. In recent years the notion of an effective bandwidth ([6],[8],[9],[11]) has been developed to provide such a measure. The effective bandwidth of a source depends sensitively upon the statistical properties of the source, and thus the issue becomes how much of the effort of statistical characterization should fall upon the network and how much upon the user responsible for a source.

Within the telecommunications and computer industries it is possible to discern two extreme approaches to this issue. One approach insists that a user provide the network with a full statistical characterization of its traffic source, which is then policed by the network. Another approach stresses the difficulty for a user of providing any information on traffic characteristics, and expects the network to cope nevertheless. These descriptions are, of course, caricatures. Note, though, that both approaches recognize the benefits of statistical sharing: they differ in how much characterization effort is required, and how this effort should be distributed over the combined system comprising users and network.

The correct balance will necessarily involve trade-offs between the user's uncertainty about traffic characteristics and the network's ability to statistically multiplex connections in an efficient manner. In this paper we describe a charging mechanism that makes these trade-offs explicit, and show that it encourages the cooperative sharing of information and characterization effort between users and the network. An economist might describe the approach in terms of incentive-compatible tariffs in a stochastic environment. However there is no necessity for the various charges to be converted into monetary units: they could instead be viewed as coordination signals that allow users to assess the impact of their actions on the network. Thus a control engineer might prefer to describe the approach in terms of the hierarchical control through Lagrange multipliers of the combined system comprising users and network.

2 Effective bandwidths

In this Section we review the concept of an effective bandwidth, beginning with a very simple model.

Suppose that J sources share a single resource of capacity C, and let Aj be the load produced by source j. Assume that Aj, j = 1, 2,...,J, are independent random variables, with possibly different distributions. Can the resource cope with the superposition of the J sources? More precisely, can we impose a condition on the distributions of A1, A2,...,AJ which ensures that

(2.1)(2.1)

for a given value of g? The answer to this question is, by now, fairly well understood. There are constants s, K (depending on g and C) such that if

(2.2)(2.2)

where

(2.3)(2.3)

then condition (2.1) is satisfied. The expression (2.3) is called the effective bandwidth of source j. This result, originally due to Hui ([9]), was generalized in [11] to show that if the resource has a buffer, and if the load produced by source j in successive time periods is a sequence of independent bursts each distributed as Aj, then the probability the delay at the resource exceeds b time periods will be held below e-g provided inequality (2.2) is satisfied, with B again given by equation (2.3), where K = C and s = g/(bC). It is by now known that for quite general models of sources and resources it is possible to associate an effective bandwidth with each source such that, provided the sum of the effective bandwidths of the sources using a resource is less than a certain level, then the resource can deliver a performance guarantee (see [2], [3], [5], [14], [17], [18]). Often the relevant definition is of the form

(2.4)(2.4)

for particular choices of s and t, where Aj[0,t] is the load produced by source j over an interval of length t. There may be several constraints of the form (2.2) corresponding to different physical or logical resources within a network.

For example, suppose a single resource gives strict priority to sources j ΠJ1 which have a strict delay requirement, but also serves sources j ΠJ2 which have a much less stringent delay requirement. Then two constraints of the form

(2.5)(2.5)

will generally be needed to ensure that both sets of requirements are met (cf. [1],[4]). If the less stringent delay requirement becomes very weak, corresponding to a very large buffer and almost no sensitivity to delay, then s Æ 0 in (2.3), and

(2.6)(2.6)

the mean load produced by source j. The second constraint of (2.5) then becomes the simple constraint that the mean loads of all sources should not exceed the capacity of the resource, the minimal constraint necessary for the buffer queue to be stable.

Under specific modeling assumptions on sources it is often possible to refine the constraints (2.2), (2.5) by detailed numerical computations ([4],[6]). The effective bandwidths defined by the more refined constraints may no longer have the simple analytical forms (2.3) and (2.4), but share a qualitatively similar dependence on the statistical properties and performance requirements of the sources.

To develop some understanding of this dependence, let us consider the very simple case of an on/off source of peak rate h and mean rate m, for which

The effective bandwidth (2.3) of such a source is thenThe effective bandwidth (2.3) of such a source is then
(2.7)(2.7)

For fixed h this function is increasing and concave in m, while for fixed m it is increasing and convex in h. As s Æ 0 (corresponding to a very large capacity C in relation to the peak h), the effective bandwidth approaches m, the mean rate of the source. However as s increases (corresponding to a larger peak h in relation to the capacity C) the effective bandwidth increases to the peak rate h of the source.

3 Charging mechanisms

The notion of an effective bandwidth is relevant to issues ranging from network dimensioning to connection acceptance control ([7],[11]), and, we argue in this Section, to pricing. One possible charging mechanism might measure the effective bandwidth of a connection, perhaps by estimating expression (2.3) using an empirical averaging to replace the expectation operator. There is, however, a simpler indirect mechanism, which has important additional advantages in the coordination of information and characterization effort between users and the network.

3.1 Known peak rate, unknown mean rate

To illustrate the mechanism, consider first the case of an on/off source with a known (and possibly policed) peak rate h, but with a mean rate that may not be known with certainty, even to the user responsible for the source. Assume, however, that the user has a prior distribution G for the mean rate M of the call. The distribution G may represent very vague information, or might be constructed by recording past observed mean rates. Then the expected mean rate of the call is .

If the network knew the prior distribution G for the mean rate M, then the network would determine the effective bandwidth of the call, from equations (2.3) and (2.7), as

(3.1)(3.1)

But expression (3.1) is just the effective bandwidth if M is not random, but identical to its mean value under G. We see that since the source is on/off with known peak rate the network need only know EGM, the user's expected mean rate; further detail about the distribution G does not influence the effective bandwidth, and would be superfluous for the network to even request.

How, then, should the network encourage the user to assess and to declare the user's expected mean rate? We next investigate whether the charging mechanism might be used to provide the appropriate amount of encouragement.

Suppose that, before a call's admission, the network requires the user to announce a value m, and then charges for the call an amount f(m;M) per unit time, where M is the measured mean rate for the call. We suppose that the user is risk-neutral and attempts to select m so as to minimize EGf(m;M), the expected cost per unit time: call a minimizing choice of m, m with circumflexm with circumflex say, an optimal declaration for the user. What properties would the network like the optimal declaration to have? Well, first of all the network would like to be able to deduce from the user's expected mean rate EGM, and hence the effective bandwidth (3.1) of the call. A second desirable property would be that the expected cost per unit time under the optimal declaration be proportional to the effective bandwidth of the call (or, equivalently, equal to the effective bandwidth under a choice of units). In [13] it is shown that these two requirements essentially characterize the tariff f(m;M) as f(m;M) = a(m) + b(m)M, (3.2)

defined as the tangent to the curve B(h,M) at the point M = m (see Figure 1). The key property used in the proof [13] is the strict concavity of B(h,M) as a function of M. By a simple differentiation of the function (2.7), the coefficients in expression (3.2) are given by

(3.3)(3.3)

where we now make explicit the dependence of the coefficients on the peak rate h.

The properties characterizing the tariff f have many interesting and desirable consequences. For example, suppose that a user can, with some effort, improve its prediction of the statistical properties of a call. A crude method of deciding upon the declaration m might be to take the average of the measured means for the last n calls, but more sophisticated methods are possible. If the user is an organization containing many individuals, the user might observe the identity of the individual making the call, the applications active on that individual's desktop computer, as well as the called party, and utilize elaborate regression aids to make the prediction m. Is it worth the effort? In [13] it is shown that improved prediction reduces the expected cost per unit time of the connection by exactly the expected reduction in the effective bandwidth required from the network. This is an important property: users should not be expected to do more work determining the statistical properties of their calls than is justified by the benefit to the network of better characterization.

Figure 1: Effective bandwidth as a function of mean rateFigure 1: Effective bandwidth as a function of mean rate

We end this subsection with a brief comment on the independence assumption underlying our approach. The independence of loads produced by different sources is an essential feature of the analysis leading to the constraints (2.2), (2.5), and to the concept of an effective bandwidth. Within the framework of this Section, this corresponds to the assumption that the errors made by different users in predicting their own mean rates are independent, in addition to the assumption that, conditional on mean rates, sources behave independently. In effect, statistical sharing is averaging with respect to both sources of randomness simultaneously.

3.2 A numerical example

We now illustrate the formulae (3.3) with a numerical example. Suppose that the predominant traffic offered to a link of capacity 100 mbps falls into three categories, with peak and mean rates as described in Table 1. Then the choice s = 0.333 in expression (2.3) is reasonable [12]. Note that almost all of the charge for these three service types arises from the variable charge b(h,m).

Table 1

Rate (mbps) Charge
Service type Peak Mean fixed (s-1) variable (mbit-1)
1 0.1 0.04 2.7 x 10-4 1.0
2 2.0 0.02 1.3 x 10-4 1.4
3 10.0 0.01 1.1 x 10-3 7.9
h m a(h, m) b(h,m)

While the predominant traffic may be of types 1, 2 and 3, connections are not constrained to just these types. For example, a connection with a known peak rate of 2 mbps could select any pair (a(2,m),b(2,m)) from Figure 2, or a connection with a known peak rate of 10 mbps could select any pair (a(10,m),b(10,m)) from Figure 3.

Figure 2: Tariff choices, for a peak rate of 2 mbpsFigure 2: Tariff choices, for a peak rate of 2 mbps

Similarly tariffs may be calculated for sources with other peak rates. For a peak rate of 0.1 mbps the bandwidth B(h,M) is almost linear in M, producing a variable charge b(h,m) per unit of traffic that is almost constant in m. Since statistical multiplexing is efficient for sources with such low peak rates, very little incentive need be given to determine mean rates accurately. Peak rates above 2 mbps produce more concave effective bandwidths and hence more incentive to accurately estimate the mean. The various charges shown in Tables 1 and 2 are expressed in the same units (of resource usage per second or per megabit) and are directly comparable with each other.

Figure 3: Tariff choices, for a peak rate of 10 mbpsFigure 3: Tariff choices, for a peak rate of 10 mbps

Observe that the total charge for service type 1 is higher than that for service type 2: for these service types at this resource statistical sharing is relatively easy, and the advantage of a lower mean rate outweighs the disadvantage of a higher peak rate. The total charge for service type 3 is, however, more than twice as high as for service types 1 and 2: statistical sharing becomes more difficult with a peak rate as high as 10% of the capacity of the resource. Observe that for the three service types shown in Table 1 almost all of the total cost to the user arises from the variable charge. For the service types shown in Table 2 much more of the total cost arises from the fixed charge, more than half in the case of service type 6.

Table 2

Rate (mbps) Charge
Service type Peak Mean fixed (s-1) variable (mbit-1)
4 2.0 1.0 0.2 1.0
5 10.0 1.0 1.7 2.2
6 10.0 2.0 3.0 1.3
h m a(h, m) b(h, m)

The above charges can be compared with those that might be appropriate if the link were entirely loaded by delay-insensitive traffic (that is, traffic whose effective bandwidth approaches its mean rate, (2.6), and for which the average utilization could reasonably exceed 90%). A variable charge of about 0.5 per megabit would recover from such traffic about the same total revenue as can be recovered from a link loaded with high-priority traffic from the categories shown in Table 1. Note that delay-insensitive traffic does not directly substitute for high-priority traffic until its volume exceeds a certain level, about 50 mbps for the numerical example of this sub-section. There are two distinct constraints in (2.5): when the first constraint is tight and the second is not then the link is unable to accept any more high priority traffic and yet is capable of accepting more delay-insensitive traffic.

In passing we note an important relationship between the charging mechanism and recent work on call admission control. Suppose that a resource has admitted J calls, and can assess the total charge generated by these calls over a short period of time. Then consider the following call admission control: accept another call if this total charge is less than a threshold. For example, if admitted calls have high peak-time mean ratios, as for the service types in Table l, then this may amount to comparison of ΣjbjSj with a threshold, where bj is the variable charge for call j and Sj is the recently measured load of call j. It may seem that such a call admission control is naively straightforward: after all, the measurements Sj will be highly variable, according to whether the source is on, off or somewhere in between. In [7] it is shown that such a simple call admission control can be surprisingly robust and efficient.

3.3 Unknown peak and mean rate

Next consider the case of an on/off source where the peak rate as well as the mean rate may not be known with certainty. Let G be the joint prior distribution for the peak rate H and the mean rate M. If the network knew the prior distribution then it would determine the effective bandwidth of the call, from equations (2.3) and (2.7), as .

The network thus needs to know just the quantity EGZ where

(3.4)(3.4)

Suppose the network charges an amount f(z;M,H) per unit time, where z is chosen by the user, and M and H are subsequent measurements of the mean and peak rates respectively. In [13] it is shown that the optimal choice for the user is z = EGZ, and with this choice the expected cost per unit time is equal to the effective bandwidth of the call, if and only if

(3.5)(3.5)

where the right hand side of equation (3.4) is the tangent to the curve B(Z) = s-1 logZ at the point Z = z.

We may rewrite the form (3.5), using the definition (3.4), as

(3.6)(3.6)

where

(3.7)(3.7)

The form (3.6) is linear in the measured mean M, with a peak dependent charge of bz(H) per unit of carried traffic. The function bz(•) is increasing and convex: hence a connection that is more uncertain about its peak rate will prefer to choose a higher value z, thus incurring a higher charge per unit time and a lower charge per unit of carried traffic.

The tariff structure (3.6)-(3.7) subsumes the simpler structure (3.2) (3.3): if a user knows its peak rate H, but not the mean M, then its optimal choice of z under the structure (3.6)-(3.7) incurs charges identical to those incurred with an optimal choice of m under the structure (3.2)-(3.3).

We have discussed in details the development of charging mechanisms for on/off sources. The procedure readily generalizes to more complex sources. All that is required is that effective bandwidth, whether defined analytically or computationally, be capable of expression as a concave function of the expectation of a measurable quantity [13]. Other topics briefly mentioned in [13] include multiple resources and network routing. A proper discussion of these topics, and of multiple constraints of the form (2.5), requires a framework within which the shadow prices associated with different physical and logical resources can be assessed (cf. [10]).

4 Adaptation

Until now we have supposed that the choice of tariff is made once, at the start of a connection. Might it be worthwhile for a connection to vary this choice over its duration? Changes in the tariff regime might be made over time intervals longer than round-trip delay times, but shorter than a connection. Such changes would incur additional control and complexity overhead, but might allow more efficient statistical multiplexing, through a more precise indication of short-term statistical characteristics. Where statistical multiplexing is easy we might expect there to be little benefit, but there may be circumstances where a connection can make good short-term predictions that might be helpful to the network.

It is relatively easy to describe a mechanism which allows these various trade-offs to be assessed. Suppose that a connection may change its choice of tariff regime at any time, but must pay a fixed charge c every time this choice is exercised. Equivalently we allow a connection to become a sequence of shorter duration connections, but charge c for the set-up costs incurred by the network for each connection. Then a user is able to make its own evaluation of the benefit of changing the choice of tariff, and to assess whether the benefits of short-term prediction of its load outweigh the set-up charge c.

We have been especially concerned in this paper with the proper measurement of resource usage for bursty connections. There are, of course, many other important issues in the development of pricing schemes, and it is perhaps worth emphasizing that our approach makes no prejudgement about the resolution of several of these issues. For example, our charges are measured in units of resource usage: whether to convert these units into dollars or a non-monetary currency is left open. Similarly we might allow any such conversion to depend upon the type of day, or perhaps even an estimate of the load on the resource over the last few seconds or minutes (cf. [16]). Whatever view is taken on these issues, we believe it will be essential for the network and the users to have some mechanism for comparing the resource utilization of connections with very different statistical properties and performance requirements.


Acknowledgments

This paper has benefited from the questions and comments of Van Jacobson, Liam Murphy and Scott Shenker, to whom I am grateful.


Frank P. Kelly (f.p.kelly@statslab.cam.ac.uk) is with the Statistical Laboratory, University of Cambridge, and can be reached at 16 Mill Lane, Cambridge CB2 lSB, England.


References

1. Bean, N. (1994) Effective bandwidths with different quality of service requirements. In IFIP Transactions, Integrated Broadband Communication Networks and Services, V.B. Iverson (editor), Elsevier, Amsterdam, 241-252.return to text

2. Botvich, D.D. and Duffield, N. (1994) Large deviations, the shape of the loss curve, and economies of scale in large multiplexers. Dublin Institute for Advanced Studies.return to text

3. Courcoubetis, C. and Weber, R. (1994) Buffer overflow asymptotics for a switch handling many traffic sources. University of Cambridge.return to text

4. Elwalid, A. and Mitra, D. (1994) Analysis, approximations and admission control of a multi-service multiplexing system with priorities. A.T. & T. Bell Laboratories.return to textreturn to text

5. De Veciana, G. and Walrand, J. (1994) Effective bandwidths: call admission, traffic policing and filtering for ATM networks. Queuing Systems.return to text

6. Gibbens, R.J. and Hunt, P.J. (1991) Effective bandwidths for the multi-type UAS channel. Queuing Systems 9, 17-28. [doi: 10.1007/BF01158790]return to textreturn to text

7. Gibbens, R.J., Kelly, F.P. and Key, P.B. (1995) A decision-theoretic approach to call admission control in ATM networks. IEEE J. Selected Areas Communication.return to textreturn to text

8. Guerin, R., Ahmadi, H. and Naghshineh, M. (1991) Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE J. Selected Areas Communication. 9, 968 981. [doi: 10.1109/49.103545]return to text

9. Hui, J.Y. (1988) Resource allocation for broadband networks. IEEE J. Selected Areas in Communication. 6, 1598-1608. [doi: 10.1109/49.12887]return to textreturn to text

10. Kelly, F.P. (1988) Routing in circuit-switched networks: optimization, shadow prices and decentralization. Advances in Applied Probability 20, 112 144. [doi: 10.2307/1427273]return to text

11. Kelly, F.P. (1991) Effective bandwidths at multi-class queues. Queueing Systems 9, 5-16. [doi: 10.1007/BF01158789]return to textreturn to textreturn to text

12. Kelly, F.P. (1994) Tariffs and effective bandwidths in multiservice networks. In [15], 401-410.return to text

13. Kelly, F.P. (1994) On tariffs, policing and admission control of multiservice networks. Operations Research Letters 15, 1-9. [doi: 10.1016/0167-6377(94)90008-6]return to textreturn to textreturn to textreturn to textreturn to textreturn to text

14. Kesidis, G., Walrand, J. and Chang, C.S. (1993) Effective bandwidths for multiclass Markov fluids and other ATM sources. IEEE/ACM Transactions on Networking 1, 424-428. [doi: 10.1109/90.251894]return to text

15. Labetoulle, J. and Roberts, J.W. (editors) (1994) The Fundamental Role of Teletraffic in the Evolution of Telecommunication Networks, Elsevier, Amsterdam.return to textreturn to text

16. MacKie Mason, J.K. and Varian, H. (1994) Pricing the Internet. In Public Access to the Internet, B. Kahin and J. Keller (editors), Prentice-Hall, New Jersey.return to text

17. Simonian, A. and Guibert, J. (1994) Large deviations approximation for fluid sources fed by a large number of on/off sources. In [15], 1013 - 1022.return to text

18. Whitt, W. (1993) Tail probabilities with statistical multiplexing and effective bandwidths in multi-class queues. Telecommunication Systems 2, 71-167.return to text