Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2719))
Included in the following conference series:
2078Accesses
Abstract
We study algorithmic problems that are motivated by bandwidth trading in next generation networks. Typically, bandwidth trading involves sellers (e.g., network operators) interested in selling bandwidth pipes that offer to buyers a guaranteed level of service for a specified time interval. The buyers (e.g., bandwidth brokers) are looking to procure bandwidth pipes to satisfy the reservation requests of end-users (e.g., Internet subscribers). Depending on what is available in the bandwidth exchange, the goal of a buyer is to either spend the least amount of money to satisfy all the reservations made by its customers, or to maximize its revenue from whatever reservations can be satisfied.
We model the above as a real-time non-preemptive scheduling problem in which machine types correspond to bandwidth pipes and jobs correspond to the end-user reservation requests. Each job specifies a time interval during which it must be processed and a set of machine types on which it can be executed. If necessary, multiple machines of a given type may be allocated, but each must be paid for. Finally, each job has a revenue associated with it, which is realized if the job is scheduled on some machine.
There are two versions of the problem that we consider. In the cost minimization version, the goal is to minimize the total cost incurred for scheduling all jobs, and in the revenue maximization version the goal is to maximize the revenue of the jobs that are scheduled for processing on a given set of machines. We consider several variants of the problems that arise in practical scenarios, and provide constant factor approximations.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. M. Arkin and E. B. Silverberg, Scheduling jobs with fixed start and end times.Discrete Applied Mathematics, Vol. 18, pp. 1–8, 1987.
A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, Approximating the throughput of multiple machines in real-time scheduling, SIAM Journal on Computing, Vol. 31 (2001), pp. 331–352.
R. Bar-Yehuda, A. Bar-Noy, A. Freund, J. Naor, and B. Schieber, A unified approach To approximating resource allocation and scheduling,Proc. 32nd Annual ACM Symposium on Theory of Computing, pp. 735–744, 2000.
P. Berman and B. DasGupta, Multi-phase algorithms for throughput maximization for real-time scheduling.Journal of Combinatorial Optimization, Vol. 4, pp. 307–323, 2000.
R. Bar-Yehuda and S. Even, A linear time approximation algorithm for the weighted vertex cover problem.Journal of Algorithms, Vol. 2, pp. 198–203, 1981.
G. Cheliotis, Bandwidth Trading in the Real World: Findings and Implications for Commodities Brokerage.3rd Berlin Internet Economics Workshop, 26–27 May 2000, Berlin.
S. Chiu and J. P. Crametz, Surprising pricing relationships.Bandwidth Special Report, RISK. ENERGY & POWER RISK MANAGEMENT pages 12–14, July 2000. (http://www.riskwaters.com/bandwidth)
J. Chuzhoy, R. Ostrovsky, Y. Rabani, Approximation algorithms for the job interval selection problem and related scheduling problemsProc. 42nd Annual Symposium of Foundations of Computer Science, pp. 348–356, 2001.
M.R. Garey, D.S. Johnson, G.L. Miller and C.H. Papadimitriou, The complexity of coloring circular arcs and chords.SIAM Journal on Algebraic and Discrete Methods, Vol. 1, pp. 216–227, 1980.
M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems.SIAM J. on Computing, Vol. 24, pp. 296–317, 1995.
K. Jansen An approximation algorithm for the license and shift class design problemEuropean Journal of Operational Research 73 pp. 127–131, 1994.
C. Kenyon and G. Cheliotis, Stochastic Models for Telecom Commoditiy PricesComputer Networks 36(5–6):533–555, Theme Issue on Network Economics, Elsevier Science, 2001.
A. W. J. Kolen and L. G. Kroon, On the computational complexity of (maximum) class scheduling,European Journal of Operational Research, Vol. 54, pp. 23–38, 1991.
A. W. J. Kolen and L. G. Kroon, On the computational complexity of (maximum) shift scheduling,European Journal of Operational Research, Vol. 64, pp. 138–151, 1993.
A. W. J. Kolen and L. G. Kroon, An analysis of shift class design problems,European Journal of Operational Research, Vol. 79, pp. 417–430, 1994.
A. W. J. Kolen and J. K. Lenstra, Combinatorics in operations research,Handbook of Combinatorics, Eds: R. L. Graham, M. Grotschel, and L. Lovasz, North Holland, 1995.
F. C. R. Spieksma. On the approximability of an interval scheduling problem.Journal of Scheduling, Vol. 2 pp. 215–227, 1999.
V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
http://www.zurich.ibm.com/bandwidth/concepts.html
P. Winkler and L. Zhang, Wavelength Assignment and Generalized Interval Graph Coloring,Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003.
Author information
Authors and Affiliations
Bell Labs, 600 Mountain Ave, Murray Hill, NJ, 07974
Randeep Bhatia
Computer Science Dept., Technion, Haifa, 32000, Israel
Julia Chuzhoy, Ari Freund & Joseph Seffi Naor
- Randeep Bhatia
You can also search for this author inPubMed Google Scholar
- Julia Chuzhoy
You can also search for this author inPubMed Google Scholar
- Ari Freund
You can also search for this author inPubMed Google Scholar
- Joseph Seffi Naor
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Dept. of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands
Jos C. M. Baeten
School of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, Atlanta, GA, 30332-0205, USA
Jan Karel Lenstra
Department of Information Technology, Uppsala University, P.O. Box 337, 75105, Uppsala, Sweden
Joachim Parrow
Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500 AE, Enschede, The Netherlands
Gerhard J. Woeginger
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bhatia, R., Chuzhoy, J., Freund, A., Naor, J.S. (2003). Algorithmic Aspects of Bandwidth Trading. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds) Automata, Languages and Programming. ICALP 2003. Lecture Notes in Computer Science, vol 2719. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45061-0_59
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-40493-4
Online ISBN:978-3-540-45061-0
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative