The Role of Price in The Connection Establishment Process
The Role of Price in The Connection Establishment Process
The Role of Price in The Connection Establishment Process
421-429
In this paper, we discuss the role of prices in combining user characterization, network resource allocation,
and contract negotiation to form a complete connection establishment process. We suggest that such a
process should encourage network efficiency through distributed resource allocation among virtual circuits,
circuit bundles, and virtual paths. We adopt effective bandwidth as our user traffic characterization and our
pricing base, and we measure network efficiency by total user benefit. We allow a limited degree of statistical
multiplexing by incorporating multiplexing gain into the prices. Finally, we propose a hierarchical and
distributed negotiation structure under which only hierarchically adjacent and geographically local network
entities communicate with each other.
I. Introduction
Emerging networks such as Asynchronous Transfer Mode (ATM) will attempt to provide guaranteed
performance to variable bit rate (VBR) services. Data networks have generally provided VBR services, but
only on a best effort basis. Telephone networks have generally provided guaranteed performance, but only to
circuit-switched services.
In ATM, user information streams are organized into small fixed-length packets called cells. These cells are
sent through shared transmission lines and routed by switches with shared buffers. This resource sharing
through cell-switching increases network utilization levels and gives the network the flexibility of providing
potentially unlimited classes of service. However, due to the cell-switching nature of ATM, a more complex
connection establishment procedure is required to guarantee the quality of services (QoS) and to avoid
congestion. Equally important is the economic aspect of connection establishment. It is thought that the
decision to accept a call and the amount of resources to assign to it should be based both on the network’s
capability to accept the call and the network’s economic efficiency.
The evolving view of connection establishment for connection-oriented services involves two stages. The first
stage consists of separate roles for the user and the network. The user agent must characterize the
information streams that will be transmitted and her valuation of the service. Similarly, the network agent must
determine the network’s resources and its capabilities to accommodate various mixes of service types. The
second stage involves negotiations between multiple network and user agents, in which the parties agree to
set up connections to transmit the agreed information streams in a manner to guarantee the agreed QoS, and
at agreed prices. In [9], we reviewed recent contributions to each of these steps, and suggested problems that
must be solved to integrate these into a complete connection establishment process. In this paper, we set up
a mathematical framework to investigate the role of prices in the connection establishment process. We
suggest that prices can allocate resources at each of three network levels in a manner that encourages
network efficiency, as measured by total user benefit.
Some recent research has investigated the use of pricing in implementing a distributed contract negotiation
process. Best-effort service computer networks have been studied in [1] [2] [3], and ATM networks have been
considered in [4] [5] [6] [7] [8] [9]. Although pricing methods for best-effort service can not be directly used in
networks which guarantee QoS, the ideas are similar. The ATM work typically focuses on specific network
processes. For example, Kelly [4] devised a pricing structure to encourage users to reveal the true mean rates
of their traffic streams so that mean-rate policing is unnecessary. Low [5] exploited the trade-off between
buffer and bandwidth to improve network efficiency, and Murphy [7] emphasized issues of resources
allocation among different network levels.
Our pricing scheme in this paper is based on the framework laid in [9], where effective bandwidth is used as
both the user traffic characterization and the pricing base. Our method differs from others in that certain
degree of statistical multiplexing is allowed and the effects of multiplexing gain on resource allocation and
prices are studied. Furthermore, we propose a hierarchical and distributed negotiation structure under which
only adjacent and local network levels communicate with each other.
We model a user’s demand for bandwidth for a non-real-time service through user benefit as a function of
completion time (Figure 1b). For example, a user can decide to transmit her data at once or to spread out the
data transmission, depending on prices for bandwidth. Benefit functions for non-real-time service change with
elapsed time and remaining file size.
We choose effective bandwidth to characterize user traffic streams. Effective bandwidth [10] [11] [12] [13] [14]
[15] models a source’s use of network resources at the user/network interface. A source is fed into a finite
buffer served at a constant rate. If the loss is asymptotically exponential in the buffer length, then the source is
said to have an effective bandwidth. The rate of the exponential decrease depends on the service rate and on
the burstiness of the source. The concept is usually used in reverse: in the range of small loss probabilities
and large buffer lengths, a source must be served at a rate at least equal to its effective bandwidth in order to
meet the corresponding loss criterion.
The effective bandwidth is bounded by the source’s mean and peak rates, and is a function of the source’s
burstiness and of ξ = ( log ( lossprobability ) ) ⁄ ( bufferlength ) . One nice property of many systems with
effective bandwidths is that the effective bandwidth of multiplexed sources sharing the same buffer is equal to
For real-time service, effective bandwidth is calculated for the transmitted traffic stream given a channel’s
QoS defined by cell loss probability and maximal delay jitter. Thus we obtain effective bandwidth as a function
of pre-transmission loss, as depicted in Figure 2, to characterize user traffic streams.
peak rate
Effective Effective
Bandwidth Bandwidth
a) Effective bandwidth for real-time services b) Effective bandwidth for non-real-time services
For non-real-time service, if a user transmits the data at a constant rate during each negotiation cycle, the
effective bandwidth of the traffic is equal to its mean rate. Effective bandwidth is inversely proportional to the
completion time (Figure 2b).
We explicitly characterize a network’s current capabilities to offer a particular service mix according to the
partition of resources at three levels: virtual circuit (VC), circuit bundle (CB), and virtual path (VP) [16]. A
virtual path is a group of connections sharing a common path from source to destination. Virtual circuits are
the individual connections within a virtual path. Routing is performed on the virtual path level. A circuit bundle
groups VCs with common characteristics as given by the resource management architecture. Among the
numerous combinations, the following allocation methods are often considered:
VP/QoS Allocation: All VCs with identical paths and QoS are statistically multiplexed.
Prices play an important role in implementing the distributed negotiation processes. By setting prices, the
network agent signals to the user agents the available capacity and the market demand. A user agent reacts
to the price by choosing the amount of resources to demand. At market-clearing prices, the network and user
agents agree on the prices and the amount of resources for each connection.
We argue that effective-bandwidth pricing reflects an individual user’s usage of the network, and thus is better
than peak-rate pricing or mean-rate pricing when statistical multiplexing is considered in admission control.
Peak-rate pricing charges more than what a VBR traffic source actually uses due to the multiplexing gain.
Mean-rate pricing, or per-packet pricing, does not reflect the cost caused by the burstiness of traffic sources.
The key to efficient network usage is to charge users fairly according to the amount of resources occupied by
individual users. Effective bandwidth of a traffic stream can be considered as composed of two parts:
meanrate + burstiness . We therefore propose that users be charged an amount equal to
effective bandwidth x price. A traffic stream will thus be charged for its mean rate plus an amount based on its
burstiness.
Contract negotiation is performed at three levels, and each level communicates only with its adjacent levels.
Each circuit bundle, virtual path and trunk maximizes its total user benefit as a supplier as it negotiates with
lower network levels by setting the right prices; and maximizes its consumer surplus as a consumer as it
negotiates with the higher level by choosing the right demand. For example, when negotiation takes place
between a virtual path and its circuit bundles, the virtual path is a supplier while its circuit bundles are
consumers. For a negotiation between a circuit bundle and its virtual circuits, the role of the circuit bundle is
switched to a supplier while its virtual circuits become the consumers. Three levels of negotiations thus take
place on different time scales with the lowest level having the shortest negotiation cycle. Consequently,
computations of optimal resource allocations are distributed among network levels and among local network
areas.
Under this resource allocation scheme, virtual circuits within a virtual path are grouped into different bundles
(circuit bundles) according to their QoS1 specifications. Virtual circuits within a circuit bundle are statistically
multiplexed, and the statistical multiplexing gain is considered in the admission control and pricing. Since we
assume that non-real-time data can be transmitted at a constant rate during a negotiation cycle, no statistical
multiplexing gain exists for non-real-time traffic. Due to the variable-rate traffic of real-time service, statistical
multiplexing gain is present.
E ijk : effective bandwidth of virtual circuit (VC) i within circuit bundle (CB) j which is within virtual path (VP) k .
S jk : capacity of CB j within VP k .
T l : capacity of trunk l .
V k : capacity of VP k .
Q ijk : pre-transmission loss for real-time services and completion time for non-real-time services.
ben ijk : benefit function for VC i within CB j and within VP k , or benefit function of user ( i , j , k ).
1
Ikl = : if VP k ’s route uses trunk l , I kl is equal to 1. Otherwise, it is equal to 0.
0
I : a routing matrix with I kl as elements.
We assume that the effective bandwidth of a real-time service is decreasing, differentiable and jointly convex
in a circuit bundle’s capacity S ij and Q ijk . Higher pre-transmission loss results in less traffic being transmitted
onto the network, and therefore less effective bandwidth. Higher capacity allows a longer buffer for the same
maximal delay jitter, and therefore it reduces the effective bandwidth needed for the same cell loss probability.
1. QoS of the circuit bundle here is defined by cell loss probability and maximal delay jitter.
64000
62000
60000
Effective Bandwidth
58000
56000
54000
52000
50000
48000
46000
0 2e+07 4e+07 6e+07 8e+07 1e+08
Channel Capacity
For non-real-time services, we assume that effective bandwidth is decreasing, differentiable and convex in
completion time Q ijk , but does not change with capacity S ij . For convenience, we denote the effective
bandwidth for both types of service by Eijk ( Q ijk, S jk ) . In addition, we assume that benefit functions are
concave, decreasing and differentiable in Q ijk .
max
Q ijk, S jk, V k
∑ ∑ ∑ benijk ( Qijk )
i j k
(1)
subject to constraints:
∑ S jk ≤ Vk ∀k (3)
j
1. The parameters of the fluid flow are: fluid rates (64000,32000), transition rates (.985222,.722282). The QoS is
–9
defined by a maximal delay jitter of 0.05 and a loss probability of 10 .
S jk – ∑ E ijk ( Q ijk, S jk ) is a concave function since ∑ Eijk ( Qijk, Sjk ) is convex. Because the objective function
i i
and the constraint functions in (6) are concave, this is a concave programming problem and Kuhn-Tuker
conditions [22] are sufficient and necessary for the global optimal solution. Kuhn-Tuker theorem gives (2)-(4)
plus the following conditions for optimality:
∂ ∂ ∂E
L ( λ jk, µ k, ρl ) = ben ijk ( Q ijk ) – λ jk ijk ≤ 0 ∀( i, j, k ) (7)
∂ Q ijk ∂ Q ijk ∂ Q ijk
∂ ∂E
Q ijk ben ijk ( Q ijk ) – λjk ijk = 0 ∀( i, j, k ) (8)
∂ Q ijk ∂ Q ijk
∂ ∂E
L ( λ jk, µ k, ρ l ) = λ jk – λ jk ∑ ijk – µ k ≤ 0 ∀( j, k ) (9)
∂ S jk i
∂ S jk
∂E
S jk λ jk – λ jk ∑ ijk – µ k = 0 ∀ ( j, k ) (10)
i
∂ S jk
∂
L ( λ jk, µ k, ρ l ) = µ k – ∑ ρl I kl ≤ 0 ∀l (11)
∂ Vk l
Vk µ k – ∑ ρ l I kl = 0 ∀l (12)
l
λ jk S jk – ∑ E ijk = 0 ∀( j, k ) (13)
i
µ k Vk – ∑ S jk = 0 ∀k (14)
j
ρ l T l – ∑ V K I kl = 0 ∀l (15)
k
λ jk, µ k, ρ l ≥ 0 ∀( j, k, l ) (16)
Solving such a maximization problem for a network of moderate size can be computationally intensive, and
thus it is desirable to distribute the computation to various network levels and local network areas. If we
consider the Lagrangian multipliers λ jk, µ k, ρ l to be the prices charged by CB ( j, k ), VP k , and trunk l
respectively, equations (7)-(8), (9)-(10), and (11)-(12) describe VC ( i, j, k ), CB ( j, k ) and VP k ‘s behavior in
response to the prices as a consumer, and equations (2)-(4), (13)-(15) describe the VC, CB and VP’s strategy
as a supplier. By decomposing the Kuhn-Tucker conditions into separate roles of consumer and supplier at
each network level, we might be able to transform the centralized problem into a distributed problem.
User ( i, j, k ) maximizes his consumer surplus given his circuit bundle’s price λ jk and the capacity of the circuit
bundle S jk :
∂ ∂E
ben ijk ( Q ijk ) – λ jk ijk ≤ 0 (18)
∂ Q ijk ∂ Q ijk
∂ ∂E
Q ijk ben ijk ( Q ijk ) – λ jk ijk = 0 (19)
∂ Q ijk ∂ Q ijk
(18) and (19) show that if the marginal benefit ( – ∂ ben ijk ( Q ijk ) ) is strictly greater than the marginal cost of
∂ Q ijk
∂Eijk
effective bandwidth ( – λ jk ) for all values of pre-transmission loss or completion time Q ijk , then set
∂ Q ijk
Q ijk = 0 . If the two can be equal, then the optimal Q' ijk can be solved from:
∂ ∂E
ben ijk ( Q ijk ) – λjk ijk = 0 (20)
∂ Q ijk ∂ Q ijk
(20) means that the marginal benefit equals the marginal cost at Q' ijk for all users who choose to use the
service.
Circuit bundle ( j, k ) maximizes its total user benefit given fixed capacity S jk as a supplier:
subject to constraints:
Q ijk ≥ 0 (23)
Kuhn-Tucker theory indicates that if Q' ijk, λ' jk solve the saddle-value problem of (25), then Q' ijk solves the
above maximization problem.
(25) says that the tasks of optimization can be performed separately by the circuit bundle and its users. Circuit
bundle ( j, k ) minimizes total user benefit of the circuit bundle L jk , for fixed demands Q ijk , by varying the
circuit bundle’s price λ jk , which leads to
On the other hand, user ( i, j, k ) maximizes L jk , for a fixed circuit bundle price λ jk , by varying its demand Q ijk ,
which results in equations (18)-(19). These equations mean that users will behave in a socially optimal way as
they maximize their own consumer surplus if the right prices are charged, assuming that collusion and market
manipulation by users are absent. Circuit bundles do not need to collect each user’s benefit function if the
right prices can be obtained through some iterative negotiation such as that described in section IV.
If the capacity is fully utilized, we can solve for the optimal solutions Q' ijk and λ' jk in terms of the circuit
bundle’s capacity S jk . The envelope theorem indicates that:
If the circuit bundle’s capacity is not fully utilized, then the optimal price per effective bandwidth unit λ' jk = 0 ,
and thus d ben jk ( S jk ) = 0 .
d S jk
The marginal benefit of a circuit bundle depends the equilibrium price reached between the CB and its VCs,
∂E'
λ' jk , and on the marginal aggregate multiplexing gain (MAMG) within the CB, – ∑ ikj . If no multiplexing
i
∂ S jk
Number of users
Figure 4 Marginal aggregate multiplexing gain versus number of users
If we can obtain the sensitivity of the benefit function ben jk ( S jk ) , e.g. by (28), then the circuit bundle is able to
maximize its consumer surplus given its VP’s price µ k . Circuit bundle ( j, k ) performs:
∂
ben jk ( S jk ) – µ k ≤ 0 (30)
∂ S jk
S jk ∂ ben jk ( S jk ) – µ k = 0 (31)
∂S
jk
Virtual path k maximizes its total user benefit given its fixed capacity V k :
subject to constraints:
∑ Sjk ≤ Vk (33)
j
Using the same saddle-value argument, virtual path k obtains (36)-(37), and circuit bundle ( j, k ) obtains
(30)-(31), which means that the total user benefit of virtual path k is maximized as circuit bundles maximize
their own consumer surplus and that virtual path k does not need to know its circuit bundles’ benefit
functions.
µ k Vk – ∑ S jk = 0 ∀k (36)
j
Vk – ∑ S jk ≥ 0 ∀k (37)
j
Substituting the sensitivity of each bundle’s benefit to allocated bandwidth given by (28) into (39) and (40), we
get
This complementary slackness condition indicates that if the second term in (39) is less than zero, then no
capacity will be allocated to CB ( j, k ). If the second term is equal to zero, then (40) has to be true.
Note that µ k is the unit bandwidth price charged by VP k to its CBs, and thus µ k is the same for all CBs within
the VP. Equation (40) means that for a fixed VP price per effective bandwidth unit µ k , a higher marginal
aggregate multiplexing gain (MAMG) – ∑ ∂ Eijk ( Q' ijk, S jk ) of a CB within a virtual path lowers the CB’s
i
∂ S jk
price charged to its VCs. As a result, prices charged by the CBs to their VCs vary within a virtual path,
depending on the marginal aggregate multiplexing gain of each circuit bundle. For non-real-time service
where multiplexing gain does not exist, equation (40) simplifies to λ' jk = µ k .
Intuitively, the network encourages network efficiency by lowering its prices to circuit bundles with higher
MAMG, and consequently allows more resources to be allocated to such circuit bundles and more
multiplexing gains to be achieved.
d
ben k ( V k ) = µ' k ( V k ) (41)
d Vk
If virtual circuit k can obtain the sensitivity of the benefit function, e.g. by (41), it can maximize its consumer
surplus by choosing the best virtual path bandwidth allocation Vk given a price equal to the sum of prices
charged by all trunks which the virtual path uses:
∂
ben k ( V k ) – ∑ ρ l I kl ≤ 0 (43)
∂Vk l
∂
V k ben k ( V k ) – ∑ ρl I kl = 0 (44)
∂ Vk l
max ∑ benk ( Vk )
V k k
(45)
subject to constraints:
∑ Vk Ikl ≤ Tl (46)
k
Vk ≥ 0 (47)
T l – ∑ V k I kl ≥ 0 (49)
k
ρ l T l – ∑ V k I kl = 0 (50)
k
Substituting the sensitivity of each VP’s benefit given by (41) into (49) and (50), we get
µ' k – ∑ ρ l I kl ≤ 0 (51)
l
Equations (18), (19), (26), (27), (36)-(39), and (49)-(52) derived from the distributed approach are identical to
the optimal conditions given by the centralized network maximization problem in section V.A. This means if
every negotiation level converges to its optimal point, then an globally optimal point is achieved.
max
E ijk, S jk, V k
∑ ∑ ∑ ben ijk ( Eijk )
i j k
(53)
subject to constraints:
∑ S jk ≤ Vk ∀k (55)
j
∑ Vk Ikl ≤ Tl ∀l (56)
k
Kuhn-Tuker theory gives the following conditions including (54)-(56) that an optimal solution satisfies:
∂ L ( λ , µ , ρ ) = ∂ ben ( E ) – λ ≤ 0 ∀ ( i, j, k ) (59)
∂ Eijk jk k l
∂ E ijk ijk ijk jk
∂
Eijk ben ijk ( E ijk ) – λjk = 0 ∀( i, j, k ) (60)
∂E
ijk
∂ L(λ , µ , ρ ) = λ – µ ≤ 0 ∀ ( j, k ) (61)
∂ S jk jk k l jk k
∂
L ( λ jk, µ k, ρ l ) = µ k – ∑ ρ l I kl ≤ 0 ∀k (63)
∂ Vk l
V k µ k – ∑ ρ l I kl = 0 ∀k (64)
l
λ jk S jk – ∑ E ijk = 0 ∀( j, k ) (65)
i
µ k Vk – ∑ S jk = 0 ∀k (66)
j
ρ l T l – ∑ V K I kl = 0 ∀l (67)
k
λ jk, µ k, ρ l ≥ 0 ∀( j, k, l ) (68)
(61) and (62) means CB price and VP price are equal for the circuit bundles having positive capacity
allocations from the same virtual path. Therefore, under this network architecture, the circuit bundle level
virtually disappears since this level does not differentiate itself from other network levels either in admission
control or pricing.
This centralized problem can also be decomposed into a distributed problem as we did in the last subsection.
In general, this problem is a simplified version of the last problem. Total user benefit of the network is
maximized when the equilibrium prices, obtained through the distributed negotiation process, equal the
Lagrangian multipliers λ jk, µ k, ρl , where λ jk is the optimal price charged by circuit bundle ( i, j ) to its virtual
circuits, µ k is the price charged by virtual path k to its circuit bundles, and ρ l is the price charged by trunk l to
each virtual path going through the trunk.
Statistical multiplexing is incorporated in the pricing model and the effects of multiplexing gain on prices and
resource allocation are studied. In summary, higher marginal aggregate multiplexing gain of a circuit bundle
lowers the price charged by the circuit bundle to its users and allows the circuit bundle to obtain more capacity
from its virtual path than other circuit bundles within the virtual path.
References
[1] R. Cocchi, D. Estrin, S. Shenker and L. Zhang. “Pricing in computer networks: motivation, formulation,
and example.” IEEE/ACM Transaction on Networking, 1(6):614-627,December 1993.
[2] J. K. Mackie-Mason and H. R. Varian. “Pricing the Internet”, Second International Conference on
Telecommunication Systems Modelling and Analysis, pp378-393, Nashville, Tennessee, March 24-27,
1994.
[3] C. Parris, S. Keshav and D. Ferrari. “A framework for the study of pricing in integrated networks.”
Technical Report TR-92-016, International Computer Science Institute, Berkeley, CA, March 1992.
[4] F. P. Kelly. “On tariffs, policing and admission control for multiservice networks.” Operations Research
Letters, 15:1-9, 1994.
[5] S. H. Low and P. P. Varaiya. “A new approach to service provisioning in ATM networks.” IEEE
Transactions on Networking, 1(3):547-553, 1883.
[6] J. Murphy and L. Murphy. “Bandwidth allocation by pricing in ATM networks.” preprint.
[7] J. Murphy, L. Murphy and E. C. Posner. “Distributed pricing for embedded ATM networks.” International
Teletraffic Congress ITC-14, Antibes, France, June 1994.
[8] C. Parris and D. Ferrari. “A resource based pricing policy for real-time channels in a packet-switching
network.” preprint.
[9] S. Jordan and H. Jiang. “Connection Establishment in High Speed Networks.” submitted to IEEE
Journal on Selected Areas in Communications.
[10] J. Y. Hui. “Resource allocation for broadband networks.” IEEE Journal on Selected Areas in
Communications, 6(9):1598-1608, December 1988.
[11] F. P. Kelly. “Effective bandwidths at multi-class queues.” Queueing Systems, 9: 5-15, September, 1991.
[12] R. J. Gibbens and P. J. Hunt. “Effective bandwidths for the multi-type UAS channel.”, Queueing
Systems, 9:17-28, May 1991.
[13] R. Guerin, H. Ahmadi and M. Naghshineh. “Equivalent capacity and its application to bandwidth
allocation in high-speed networks.” IEEE Journal on Selected Areas in Communications, 9(7):968-981,
September 1991.
[14] G. Kesidis, J. Walrand and C. S. Chang. “Effective bandwidths for multiclass markov fluids and other
ATM sources.” IEEE/ACM Transactions on Networking, 1(4):424-428, August 1993.
[15] A. I. Elwalid and D. Mitra. “Effective bandwidth of general markovian traffic sources and admission
control of high speed networks.” IEEE/ACM Transactions on Networking, 1(3):329-343, June 1993.
[16] J. Burgin and D. Dorman. “Broadband ISDN resource management: the role of virtual paths.” IEEE