Sync classes: A framework for optimal scheduling of requests in multimedia storage servers

Leana Golubchik; V. S. Subrahmanian; Sherry Marcus; Joachim Biskup

doi:10.1109/69.842251

Sync classes: A framework for optimal scheduling of requests in multimedia storage servers

Leana Golubchik^*, V. S. Subrahmanian, Sherry Marcus, Joachim Biskup

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

There have been many proposals on how media-on-demand servers can effectively allow clients to share resources. In this paper, given a set of clients, we show how these clients may be partitioned into "sync-classes" - sets of clients who can be serviced through allocation of a single set of resources. As a set of clients may be partitioned into sync-classes in many different ways, we show that a very large class of cost functions may be used to determine which partition to choose. We provide algorithms to compute such optimal splits. Our framework is very generic in the following ways: 1) The system may plug-in any cost function whatsoever, as long as it satisfies four common-sense axioms that evaluate costs, and 2) the system may evaluate the future anticipated requests of a user using any user model (e.g., a Markovian model) that has a specified I/O interface. Thus, a wide variety of predictive methods (of what the user will do) and a wide variety of costing methods may be used within our framework.

Original language	English (US)
Pages (from-to)	60-77
Number of pages	18
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	12
Issue number	1
DOIs	https://doi.org/10.1109/69.842251
State	Published - Jan 2000
Externally published	Yes

Funding

We would like to thank the anonymous referees for their insightful comments and suggestions for improving this paper. This work was done in part while Leana Golubchik was with the Department of Computer Science at Columbia University. This research was supported in part by U.S. National Science Foundation (NSF) CAREER grant CCR-98-96232, the U.S. Army Research Office under Grants DAAH-04-95-10174, DAAH-04-96-10297, and DAAH-04-96-1-0398, by the U.S. Army Research Laboratory under contract number DAAL01-97-K0135, and by an NSF Young Investigator award IRI-93-57756.

Keywords

Interactive systems
Media-on-demand servers
Optimization
Scheduling
Storage servers

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1109/69.842251

Cite this

@article{4cbf8700ecd140ac9473500f995e8c0a,

title = "Sync classes: A framework for optimal scheduling of requests in multimedia storage servers",

abstract = "There have been many proposals on how media-on-demand servers can effectively allow clients to share resources. In this paper, given a set of clients, we show how these clients may be partitioned into {"}sync-classes{"} - sets of clients who can be serviced through allocation of a single set of resources. As a set of clients may be partitioned into sync-classes in many different ways, we show that a very large class of cost functions may be used to determine which partition to choose. We provide algorithms to compute such optimal splits. Our framework is very generic in the following ways: 1) The system may plug-in any cost function whatsoever, as long as it satisfies four common-sense axioms that evaluate costs, and 2) the system may evaluate the future anticipated requests of a user using any user model (e.g., a Markovian model) that has a specified I/O interface. Thus, a wide variety of predictive methods (of what the user will do) and a wide variety of costing methods may be used within our framework.",

keywords = "Interactive systems, Media-on-demand servers, Optimization, Scheduling, Storage servers",

author = "Leana Golubchik and Subrahmanian, {V. S.} and Sherry Marcus and Joachim Biskup",

note = "Funding Information: We would like to thank the anonymous referees for their insightful comments and suggestions for improving this paper. This work was done in part while Leana Golubchik was with the Department of Computer Science at Columbia University. This research was supported in part by U.S. National Science Foundation (NSF) CAREER grant CCR-98-96232, the U.S. Army Research Office under Grants DAAH-04-95-10174, DAAH-04-96-10297, and DAAH-04-96-1-0398, by the U.S. Army Research Laboratory under contract number DAAL01-97-K0135, and by an NSF Young Investigator award IRI-93-57756.",

year = "2000",

month = jan,

doi = "10.1109/69.842251",

language = "English (US)",

volume = "12",

pages = "60--77",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "1",

}

TY - JOUR

T1 - Sync classes

T2 - A framework for optimal scheduling of requests in multimedia storage servers

AU - Golubchik, Leana

AU - Subrahmanian, V. S.

AU - Marcus, Sherry

AU - Biskup, Joachim

N1 - Funding Information: We would like to thank the anonymous referees for their insightful comments and suggestions for improving this paper. This work was done in part while Leana Golubchik was with the Department of Computer Science at Columbia University. This research was supported in part by U.S. National Science Foundation (NSF) CAREER grant CCR-98-96232, the U.S. Army Research Office under Grants DAAH-04-95-10174, DAAH-04-96-10297, and DAAH-04-96-1-0398, by the U.S. Army Research Laboratory under contract number DAAL01-97-K0135, and by an NSF Young Investigator award IRI-93-57756.

PY - 2000/1

Y1 - 2000/1

N2 - There have been many proposals on how media-on-demand servers can effectively allow clients to share resources. In this paper, given a set of clients, we show how these clients may be partitioned into "sync-classes" - sets of clients who can be serviced through allocation of a single set of resources. As a set of clients may be partitioned into sync-classes in many different ways, we show that a very large class of cost functions may be used to determine which partition to choose. We provide algorithms to compute such optimal splits. Our framework is very generic in the following ways: 1) The system may plug-in any cost function whatsoever, as long as it satisfies four common-sense axioms that evaluate costs, and 2) the system may evaluate the future anticipated requests of a user using any user model (e.g., a Markovian model) that has a specified I/O interface. Thus, a wide variety of predictive methods (of what the user will do) and a wide variety of costing methods may be used within our framework.

AB - There have been many proposals on how media-on-demand servers can effectively allow clients to share resources. In this paper, given a set of clients, we show how these clients may be partitioned into "sync-classes" - sets of clients who can be serviced through allocation of a single set of resources. As a set of clients may be partitioned into sync-classes in many different ways, we show that a very large class of cost functions may be used to determine which partition to choose. We provide algorithms to compute such optimal splits. Our framework is very generic in the following ways: 1) The system may plug-in any cost function whatsoever, as long as it satisfies four common-sense axioms that evaluate costs, and 2) the system may evaluate the future anticipated requests of a user using any user model (e.g., a Markovian model) that has a specified I/O interface. Thus, a wide variety of predictive methods (of what the user will do) and a wide variety of costing methods may be used within our framework.

KW - Interactive systems

KW - Media-on-demand servers

KW - Optimization

KW - Scheduling

KW - Storage servers

UR - http://www.scopus.com/inward/record.url?scp=0005074556&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0005074556&partnerID=8YFLogxK

U2 - 10.1109/69.842251

DO - 10.1109/69.842251

M3 - Article

AN - SCOPUS:0005074556

SN - 1041-4347

VL - 12

SP - 60

EP - 77

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 1

ER -

Sync classes: A framework for optimal scheduling of requests in multimedia storage servers

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this