Control and pricing in stochastic networks with concurrent resource occupancy

ABSTRACT

Concurrent resource occupancy pervades most engineering and service systems. For example, a multi-leg plane trip requires seat reservation on several connecting flights; a configure-to-order product demands the simultaneous processing of all its components; a file transfer on the Internet needs band-width on all the links along its route from source to destination. The object of our study is a network with stochastic concurrent occupancy of resources. The network can be physical (e.g., a telecommunication network), or virtual (e.g., the Worldwide Web), or relational (e.g., the bill of materials of a product, representing its configuration of all components); and both the demand/order arrivals and their processing times required of the resources are stochastic. Our goal is to do revenue optimization in the network through two decisions: (a) <i>pricing:</i> to determine the price charged to each job class and its dynamic adjustment over time; and (b) <i>resource control:</i> to regulate the distribution of resources among the job classes, in particular, when to accept/reject a job and from which class.

Below, we highlight a new <i>fixed-point approximation</i> for a network operating under a set of thresholds that control the access of jobs from each class. With this fixed-point approximation, the resource control problem takes the form of setting the optimal thresholds, which can be formulated and solved as a linear program. To determine the optimal prices then amounts to solving another set of optimality equations on top of the linear program. Furthermore, we can show that our approach via solving optimization problems based on the fixed-point approximation is optimal in some asymptotic sense.

REFERENCES

• 1: Tian Bu , Don Towsley, Fixed point approximations for TCP behavior in an AQM network, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.216-225, June 2001, Cambridge, Massachusetts, United States
• 2: GIBBENS, R. J., S. K. SARGOOD, C. VAN EIJL, F. P. KELLY, H. AZMOODEH, R. N. MACFADYEN, N. W. MACFADYEN, Fixed-Point Models for the End-to-End Performance Analysis of IP Networks. 13th ITC Specialist Seminar, IP Traffic Measurement, Modeling and Management, Sept. 2000, Monterey, California.
• 3: KELLY, F. P., Routing in Circuit-Switched Networks: Optimization, Shadow Prices and Decentralization. Advances in Applied Probability,20 (1988), 112--144.
• 4: WHITT, W., Blocking When Service Is Required from Several Facilities Simultaneously, AT&T Technical Journal,64 (1985), 1807--1805.