NDLI: Algorithmic aspects of bandwidth trading

Please wait, while we are loading the content...

Algorithmic aspects of bandwidth trading

Content Provider	ACM Digital Library
Author	Naor, Joseph (Seffi) Chuzhoy, Julia Freund, Ari Bhatia, Randeep
Copyright Year	2009
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 so as to satisfy all the reservations made by its customers, or to maximize its revenue from whatever reservations can be satisfied. We model this as a real-time nonpreemptive scheduling problem in which machine types correspond to bandwidth pipes and jobs correspond to 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 associated with it a revenue, 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.
Starting Page	1
Ending Page	19
Page Count	19
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/1186810.1186820
Volume Number	3
Issue Number	1
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-02-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation algorithms for NP-hard problems Dynamic storage allocation General caching Resource allocation Scheduling
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A unified approach to approximating resource allocation and scheduling

Approximation Algorithms for NP-Hard Problems

Multi-User MIMO Scheduling in the Fourth Generation Cellular Uplink

An Online Integrated Resource Allocator for Guaranteed Performance in Data Centers

Optimizing Bandwidth Allocation in Flex-Grid Optical Networks with Application to Scheduling

Multiuser Scheduling in the 3GPP LTE Cellular Uplink

How well can primal-dual and local-ratio algorithms perform?

Constant bandwidth supply for priority processing

A unified approach to approximating resource allocation and scheduling (2000)

Algorithmic aspects of bandwidth trading

Similar Documents

A unified approach to approximating resource allocation and scheduling

Approximation Algorithms for NP-Hard Problems

Multi-User MIMO Scheduling in the Fourth Generation Cellular Uplink

An Online Integrated Resource Allocator for Guaranteed Performance in Data Centers

Optimizing Bandwidth Allocation in Flex-Grid Optical Networks with Application to Scheduling

Multiuser Scheduling in the 3GPP LTE Cellular Uplink

How well can primal-dual and local-ratio algorithms perform?

Constant bandwidth supply for priority processing

A unified approach to approximating resource allocation and scheduling (2000)

Algorithmic aspects of bandwidth trading