Scheduling on-demand broadcasts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Scheduling on-demand broadcasts: new metrics and algorithms

Full text

Pdf (1.22 MB)

Source

International Conference on Mobile Computing and Networking archive
Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking table of contents

Dallas, Texas, United States

Pages: 43 - 54

Year of Publication: 1998

ISBN:1-58113-035-X

Authors

Swarup Acharya	Information Sciences Research Center, Bell Laboratories, Lucent Technologies Murray Hill, NJ
S. Muthukrishnan	Mathematical Sciences Research Center, Bell Laboratories, Lucent Technologies, Murray Hill, NJ

Sponsors

IEEE-CS : Computer Society
SIGCOMM: ACM Special Interest Group on Data Communication
SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 40, Citation Count: 58

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/288235.288248 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AAFZ95	Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
	AF98	D. Aksoy and M. Franklin. Scheduling for large scale on-demand data broadcast. In Proc. oflEEE INFOCOM, San Francisco, CA, March 1998.
	AFZ95	S. Acharya, M. Franklin, and S. Zdonik. Disseminationbased data delivery using Broadcast Disks. IEEE Personal Communications, 2(6), December 1995.
	Air97	AirMedia, Inc. WWXV, URL, http: //www. airmedia, corn/, July 1997.
	Arc98	The Interact Traffic Archive. WWW, URL: http: //ita.ee.lbl.gov/html/traces.html, Feb 1998.
	Ard98	ARDIS Home Page. WWW, UP, L: http://www. ardis, co~ February 1998.
	Bak74	K.R. Baker. Introduction to Sequencing and scheduling. Wiley, New York, 1974.
	BC98	Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
	BCM98	Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
	BMDL94	K. P. Brown, M. Mehta, D. J. DeWitt, and M_iron Livny. Towards automated performaace tuning of complex workloads. Technical Report CS-TR-92-1247, University of Wisconsin, Madison, September 1994.
	CHBM97	Mark Crovella , Mor Harchol-Balter , Cristina Murta, Task Assignment in a Distributed System: Improving Performance by Unbalancing Load, Boston University, Boston, MA, 1997
	Com98	Comeast Online Home Page. WWW, URL: htt:p:// www. comcastonline, corn, February 1998.
	DAW96	H. Dykeman, M. H. Ammar, and J. Wong. Scheduling algorithms for videotext systems under broadcast delivery. In Proc. International Conference of Communications, pages 1847-1851, 1996.
	Dir96	Hughes Network Systems, DirecPC Home Page. WWW, URL:: http: //www. direcpc, corn/, October 1996.
	Hal97	Leslie A. Hall, Approximation algorithms for scheduling, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	Horn98	@Home Network Home Page. WWW, URL: http: / / ~. home. net:, February 1998.
	KSW98	Mikhail J. Atallah , Susan Fox , Suzanne Lassandro, Algorithms and Theory of Computation Handbook, CRC Press, Inc., Boca Raton, FL, 1998
	KTW96	Hans Kellerer , Thomas Tautenhahn , Gerhard J. Woeginger, Approximability and nonapproximability results for minimizing total flow time on a single machine, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.418-426, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237989]
	MD93	Manish Mehta , David J. DeWitt, Dynamic Memory Allocation for Multiple-Query Workloads, Proceedings of the 19th International Conference on Very Large Data Bases, p.354-367, August 24-27, 1993
	MPT93	Rajeev Motwani , Steven Phillips , Eric Torng, Non-clairvoyant scheduling, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.422-431, January 25-27, 1993, Austin, Texas, United States
	Pin95	M. Pinedo. Scheduling: Theor3 Algorithms and Systems. Prentice Hall, 1995.
	Sch86	Herb Schwetman, CSIM: a C-based process-oriented simulation language, Proceedings of the 18th conference on Winter simulation, p.387-396, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318464]
	SG97	Abraham Silberschatz , James L. Peterson , Peter B. Galvin, Operating system concepts (3rd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	SL94	S. Shekhar and D. Liu. Genesis and Advanced Traveler Information Systems (ATIS): Killer applications for mobile computing. In Proceedings of MOBIDATA Workshop, Rutgers University, 1994.
	Spe98	The Standard Performance Evaluation Corporation Home Page. %qVW, URL: http: //www. specbench. org/org/web9 6, Feb 1998.
	ST97a	Chi-Jiun Su , Leandros Tassiulas, Broadcast Scheduling for Information Distribution, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.109, April 09-11, 1997
	ST97b	C. Su and L. Tassiulas. Broadcast scheduling for the distribufion of information items with unequal length. In Proc. 31th Conf. on Information Science and Systems (CISS'97), March 1997.
	TCG+98	J. Trotter, M. Cmvatts, G. Griffith, P. Krzyzanowski, W. Lehder, S. Nossen, and C. Sreenan. Low speed data over the PWT wireless phone system. Bell Labs Technical Journal, 3(I):19-29, Jan 1998.
	Wav98	Lucent Technologies, WAVELAN Home Page. WWW, URL: http: //www. wavelan, con% Feb 1998.
	Wis98	V~eless Inteme~ LLC. Home Page. WWW, URL: http: //www. wirelessisp, net/ , February 1998.
	Won88	J. Wong. Broadcast delivery. Proceedings of the IEEE, 76(12), December 1988.
	Zha95	H. Zhang. Service disciplines for guaranteed performance service in packet-switching networks. Proceedings of the IEEE, 83(10), Oct 1995.

CITED BY 58

	Michael A. Bender , S. Muthukrishnan , Rajmohan Rajaraman, Improved algorithms for stretch scheduling, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.762-771, January 06-08, 2002, San Francisco, California
	Quinglong Hu , Wang-Chien Lee , Dik Lun Lee, Indexing techniques for wireless data broadcast under data clustering and scheduling, Proceedings of the eighth international conference on Information and knowledge management, p.351-358, November 02-06, 1999, Kansas City, Missouri, United States
	Weiwei Sun , Weibin Shi , Bole Shi , Wenyun Ji , Yijun Yu, A self-adaptive scheduling algorithm of on-demand broadcasts, Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.139-146, July 2001, Rome, Italy
	Uwe Kubach , Kurt Rothermel, Exploiting location information for infostation-based hoarding, Proceedings of the 7th annual international conference on Mobile computing and networking, p.15-27, July 2001, Rome, Italy
	Thomas Erlebach , Alexander Hall, NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.194-202, January 06-08, 2002, San Francisco, California
	Yair Bartal , S. Muthukrishnan, Minimizing maximum response time in scheduling broadcasts, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.558-559, January 09-11, 2000, San Francisco, California, United States
	Jeff Edmonds , Kirk Pruhs, Broadcast scheduling: when fairness is fine, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.421-430, January 06-08, 2002, San Francisco, California
	Yufei Guo , Sajar K. Das , Cristina M. Pinotti, A new hybrid broadcast scheduling algorithm for asymmetric communication systems: push and pull data based on optimal cut-off point, Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.123-130, July 2001, Rome, Italy
	Weiwei Sun , Weibin Shi , Bole Shi , Yijun Yu, A cost-efficient scheduling algorithm of on-demand broadcasts, Wireless Networks, v.9 n.3, p.239-247, May 2003
	Jiun-Long Huang , Wen-Chih Peng , Ming-Syan Chen, Binary interpolation search for solution mapping on broadcast and on-demand channels in a mobile computing environment, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
	Jianliang Xu , Dik-Lun Lee , Qinglong Hu , Wang-Chien Lee, Data broadcast, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
	Mohamed A. Sharaf , Panos K. Chrysanthis, Facilitating mobile decision making, Proceedings of the 2nd international workshop on Mobile commerce, September 28-28, 2002, Atlanta, Georgia, USA
	Wen-Chih Peng , Ming-Syan Chen, Dynamic generation of data broadcasting programs for a broadcast disk array in a mobile computing environment, Proceedings of the ninth international conference on Information and knowledge management, p.38-45, November 06-11, 2000, McLean, Virginia, United States
	L. Becchetti , S. Diggavi , S. Leonardi , A. Marchetti-Spaccamela , S. Muthukrishnan , T. Nandagopal , A. Vitaletti, Parallel scheduling problems in next generation wireless networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Demet Aksoy , Michael Franklin, R × W: a scheduling approach for large-scale on-demand data broadcast, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.846-860, Dec. 1999
	Yufei Guo , M. Cristina Pinotti , Sajal K. Das, A new hybrid broadcast scheduling algorithm for asymmetric communication systems, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.3, p.39-54, July 2001
	Mohamed A. Sharaf , Panos K. Chrysanthis, Semantic-based delivery of OLAP summary tables in wireless environments, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Laura Bright , Samrat Bhattacharjee , Louiqa Raschid, Supporting diverse mobile applications with client profiles, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA
	Jae-Hoon Kim , Kyung-Yong Chwa, Scheduling broadcasts with deadlines, Theoretical Computer Science, v.325 n.3, p.479-488, 6 October 2004
	Guohong Cao, A Scalable Low-Latency Cache Invalidation Strategy for Mobile Environments, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1251-1265, September 2003
	Nitin Prabhu , Vijay Kumar, Data scheduling for multi-item and transactional requests in on-demand broadcast, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus
	Thomas Erlebach , Alexander Hall, NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow, Journal of Scheduling, v.7 n.3, p.223-241, May-June 2004
	Jianliang Xu , Qinglong Hu , Dik Lun Lee , Wang-Chien Lee, SAIU: an efficient cache replacement policy for wireless on-demand broadcasts, Proceedings of the ninth international conference on Information and knowledge management, p.46-53, November 06-11, 2000, McLean, Virginia, United States
	Wen-Chih Peng , Ming-Syan Chen, Efficient channel allocation tree generation for data broadcasting in a mobile computing environment, Wireless Networks, v.9 n.2, p.117-129, March 2003
	Oleg Shigiltchoff , Panos K. Chrysanthis , Evaggelia Pitoura, Adaptive multiversion data broadcast organizations, Information Systems, v.29 n.6, p.509-528, September 2004
	Jianliang Xu , Qinglong Hu , Wang-Chien Lee , Dik Lun Lee, Performance Evaluation of an Optimal Cache Replacement Policy for Wireless Data Dissemination, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.125-139, January 2004
	Jiun-Long Huang , Ming-Syan Chen, Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1143-1156, September 2004
	Mohamed A. Sharaf , Panos K. Chrysanthis, On-demand data broadcasting for mobile decision making, Mobile Networks and Applications, v.9 n.6, p.703-714, December 2004
	Jeff Edmonds , Kirk Pruhs, A maiden analysis of Longest Wait First, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Joel L. Wolf , Mark S. Squillante , John J. Turek , Philip S. Yu , Jay Sethuraman, Scheduling Algorithms for the Broadcast Delivery of Digital Products, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.721-741, September 2001
	Weiwei Cao , Demet Aksoy, Beat the clock: a multiple attribute approach for scheduling data broadcast, Proceedings of the 4th ACM international workshop on Data engineering for wireless and mobile access, June 12-12, 2005, Baltimore, MD, USA
	Azzedine Boukerche , Trivikram Dash , Cristina M. Pinotti, Performance analysis of a novel hybrid push-pull algorithm with QoS adaptations in wireless networks, Performance Evaluation, v.60 n.1-4, p.201-221, May 2005
	Jeff Edmonds , Kirk Pruhs, A maiden analysis of longest wait first, ACM Transactions on Algorithms (TALG), v.1 n.1, p.14-32, July 2005
	Dimitrios Katsaros , Yannis Manolopoulos, Web Caching in Broadcast Mobile Wireless Environments, IEEE Internet Computing, v.8 n.3, p.37-45, May 2004
	Xiao Wu , Victor C. S. Lee, Wireless real-time on-demand data broadcast scheduling with dual deadlines, Journal of Parallel and Distributed Computing, v.65 n.6, p.714-728, June 2005
	Wai Gen Yee , Ophir Frieder, Scalable synchronization of intermittently connected database clients, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus
	Peter Triantafillou , R. Harpantidou , M. Paterakis, High performance data broadcasting systems, Mobile Networks and Applications, v.7 n.4, p.279-290, August 2002
	Chung Keung Poon , Feifeng Zheng , Yinfeng Xu, On-demand bounded broadcast scheduling with tight deadlines, Proceedings of the 12th Computing: The Australasian Theroy Symposium, p.139-143, January 16-19, 2006, Hobart, Australia
	Ilias Michalarias , Arkadiy Omelchenko , Hans-J. Lenz, FCLOS: A client-server architecture for mobile OLAP, Data & Knowledge Engineering, v.68 n.2, p.192-220, February, 2009
	Huaping Shen , Mohan Kumar , Sajal K. Das , Zhijun Wang, Energy-efficient data caching and prefetching for mobile devices based on utility, Mobile Networks and Applications, v.10 n.4, p.475-486, August 2005
	Victor C. Lee , Xiao Wu , Joseph Kee-Yin Ng, Scheduling real-time requests in on-demand data broadcast environments, Real-Time Systems, v.34 n.2, p.83-99, October 2006
	Mohamed A. Sharaf , Panos K. Chrysanthis , Alexandros Labrinidis , Kirk Pruhs, Efficient scheduling of heterogeneous continuous queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Hing-Fung Ting, A near optimal scheduler for on-demand data broadcasts, Theoretical Computer Science, v.401 n.1-3, p.77-84, July, 2008
	Agustinus Borgy Waluyo , Bala Srinivasan , David Taniar, Research in mobile database query optimization and processing, Mobile Information Systems, v.1 n.4, p.225-252, December 2005
	Demet Aksoy , Michael J. Franklin , Stanley B. Zdonik, Data Staging for On-Demand Broadcast, Proceedings of the 27th International Conference on Very Large Data Bases, p.571-580, September 11-14, 2001
	Jun Chen , Victor C. S. Lee , Edward Chan, Scheduling real-time multi-item requests in wireless on-demand broadcast networks, Proceedings of the 4th international conference on mobile technology, applications, and systems and the 1st international symposium on Computer human interaction in mobile technology, September 10-12, 2007, Singapore
	Mohamed A. Sharaf , Panos K. Chrysanthis , Alexandros Labrinidis , Kirk Pruhs, Algorithms and metrics for processing multiple heterogeneous continuous queries, ACM Transactions on Database Systems (TODS), v.33 n.1, p.1-44, March 2008
	Yang Zhang , Jing Zhao , Guohong Cao, On scheduling vehicle-roadside data access, Proceedings of the fourth ACM international workshop on Vehicular ad hoc networks, September 10-10, 2007, Montreal, Quebec, Canada
	Regant Y. S. Hung , H. F. Ting, Competitive analysis of most-request-first for scheduling broadcasts with start-up delay, Theoretical Computer Science, v.396 n.1-3, p.200-211, May, 2008
	Rinku Dewri , Indrakshi Ray , Indrajit Ray , Darrell Whitley, Optimizing on-demand data broadcast scheduling in pervasive environments, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Chao-Chun Chen , Chiang Lee , Lien-Fa Lin, A novel encoding scheme and data delivery in Ubiquitous computing systems, Wireless Networks, v.14 n.6, p.731-743, December 2008
	Hao-Ping Hung , Ming-Syan Chen, MULS: A General Framework of Providing Multilevel Service Quality in Sequential Data Broadcasting, IEEE Transactions on Knowledge and Data Engineering, v.19 n.10, p.1433-1447, October 2007
	Jonathan Beaver , Kirk Pruhs , Panos K. Chrysanthis , Vincenzo Liberatore, Improving the Hybrid Data Dissemination Model of Web Documents, World Wide Web, v.11 n.3, p.313-337, September 2008
	Yu-Chi Chung , Chao-Chun Chen , Chiang Lee, Design and Performance Evaluation of Broadcast Algorithms for Time-Constrained Data Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.18 n.11, p.1526-1543, November 2006
	Jiun-Long Huang , Ming-Syan Chen, A QoS-Aware and Energy-Conserving Transcoding Proxy Using On-Demand Data Broadcasting, IEEE Transactions on Mobile Computing, v.6 n.8, p.971-987, August 2007
	Hui Chen , Yang Xiao, On-Bound Selection Cache Replacement Policy for Wireless Data Access, IEEE Transactions on Computers, v.56 n.12, p.1597-1611, December 2007
	Kai Liu , Victor C. S. Lee, Simulation studies on scheduling requests for multiple data items in on-demand broadcast environments, Performance Evaluation, v.66 n.7, p.368-379, July, 2009
	Jianliang Xu , Xueyan Tang , Wang-Chien Lee, Time-Critical On-Demand Data Broadcast: Algorithms, Analysis, and Performance Evaluation, IEEE Transactions on Parallel and Distributed Systems, v.17 n.1, p.3-14, January 2006