Pushing dependent data in clients-providers-servers systems

ABSTRACT

In a satellite and wireless networks and in advanced traffic information systems in which the up-link bandwidth is very limited, a server broadcasts data files in a round-robin manner. The data files are provided by different providers and are accessed by many clients. The providers are independent and therefore files may share information. The clients who access these files may have different patterns of access. Some clients may wish to access more than one file at a time in any order, some clients may access one file out of of several files, and some clients may wish to access a second file only after accessing another file. The goal of the server is to order the files in a way that minimizes the access time of the clients given some a-priori knowledge of their access patterns. This paper introduces a clients-providers-servers model that represents certain environments better than the traditional clients-servers model. Then, we show that a random order of the data files performs well independent of the specific access pattern. Our main technical contribution is showing how to de-randomize the randomized algorithm that is based on selecting a random order. The resulting algorithm is a polynomial time deterministic algorithm that finds an order that achieves the bounds of the random order.

REFERENCES

• 1: 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
• 2: S. Acharya, M. J. Franklin, and S. Zdonik. Dissemination-based Data Delivery Using Broadcast Disks. IEEE Personal Communications, Vol. 2(6), 50-60, 1995.
• 3: N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons Inc., 1992.
• 4: M. H. Ammar and J. W. Wong. The Design of Teletext broadcast cycles. Performance Evaluation, Vol. 5(4), 235-242, 1985.
• 5: M. H. Ammax and J. W. Wong. On the optimality of cyclic transmission in Teletext systems. IEEE Transaction on Communication, COM-35(1), 68-73, 1987.
• 6: Amotz Bar-Noy , Randeep Bhatia , Joseph Naor , Baruch Schieber, Minimizing service and operation costs of periodic scheduling, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 25-27, 1998, San Francisco, California, United States
• 7: Tomasz Imielinski , S. Viswanathan , B. R. Badrinath, Energy efficient indexing on air, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.25-36, May 24-27, 1994, Minneapolis, Minnesota, United States
• 8: Claire Kenyon , Nicolas Schabanel, The data broadcast problem with non-uniform transmission times, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 17-19, 1999, Baltimore, Maryland, United States
• 9: M. Naor and O. Reingold. Private communication.
• 10: Satish Rao , Andréa W. Richa, New approximation techniques for some ordering problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.211-218, January 25-27, 1998, San Francisco, California, United States
• 11: 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
• 12: Sohail Hameed , Nitin H. Vaidya, Log-time algorithms for scheduling single and multiple channel data broadcast, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.90-99, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262136]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification