Cost based data dissemination in satellite networks

ABSTRACT

We consider the problem of data dissemination in a broadcast network. In contrast to previously studied models, broadcasting is among peers, rather than client server. Such a model represents, for example, satellite communication among widely distributed nodes, sensor networks, and mobile ad hoc networks. We introduce a cost model for data dissemination in peer to peer broadcast networks. The model quantifies the tradeoff between the inconsistency of the data, and its transmission cost; the transmission cost may be given in terms of dollars, energy, or bandwidth. Using the model we first determine the parameters for which eager (i.e. consistent) replication has a lower cost than lazy (i.e. inconsistent) replication. Then we introduce a lazy broadcast policy and compare it with several naive or traditional approaches to solving the problem.

REFERENCES

• 1: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Prefetching from Broadcast Disks, Proceedings of the Twelfth International Conference on Data Engineering, p.276-285, February 26-March 01, 1996
• 2: Swarup Acharya , Michael Franklin , Stanley Zdonik, Balancing push and pull for data broadcast, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.183-194, May 11-15, 1997, Tucson, Arizona, United States
• 3: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 4: Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990 [doi>10.1145/88636.87848]
• 5: Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
• 6: André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
• 7: Yuri Breitbart , Raghavan Komondoor , Rajeev Rastogi , S. Seshadri , Avi Silberschatz, Update propagation protocols for replicated databates, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.97-108, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 8: Yuri Breitbart , Henry F. Korth, Replication and consistency in a distributed environment, Journal of Computer and System Sciences, v.59 n.1, p.29-69, Aug. 1999 [doi>10.1006/jcss.1999.1639]
• 9: Lisa Gottesfeld Brown, A survey of image registration techniques, ACM Computing Surveys (CSUR), v.24 n.4, p.325-376, Dec. 1992 [doi>10.1145/146370.146374]
• 10: Alan Demers , Dan Greene , Carl Houser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, ACM SIGOPS Operating Systems Review, v.22 n.1, p.8-32, Jan., 1988 [doi>10.1145/43921.43922]
• 11: C. Fidge, Timestamps in message-passing systems that preserve the partial ordering, in: Proceedings of the 11th Australian Computer Science Conference (1988).
• 12: R. Golding, A weak-consistency architecture for distributed information services, Usenix Association, Computing Systems 5(4) (1992).
• 13: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 14: G. Grimmett and D. Welsh, Probability: an Introduction (Clarendon Press, 1986).
• 15: J. Holliday , D. Agrawal , A. El Abbadi, Planned Disconnections for Mobile Databases, Proceedings of the 11th International Workshop on Database and Expert Systems Applications, p.165, September 06-08, 2000
• 16: JoAnne Holliday , Divyakant Agrawal , Amr El Abbadi, Exploiting Planned Disconnections in Mobile Environments, Proceedings of the 10th International Workshop on Research Issues in Data Engineering, p.25, February 27-28, 2000
• 17: Tomasz Imielinski , B. R. Badrinath, Mobile wireless computing: challenges in data management, Communications of the ACM, v.37 n.10, p.18-28, Oct. 1994 [doi>10.1145/194313.194317]
• 18: Shu Jiang , Nitin H. Vaidya, Scheduling data broadcast to “impatient” users, Proceedings of the 1st ACM international workshop on Data engineering for wireless and mobile access, p.52-59, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313300.313385]
• 19: Peter J. Keleher, Decentralized replicated-object protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301345]
• 20: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 21: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, Nearest Neighbor Queries in a Mobile Environment, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.119-134, September 10-11, 1999
• 22: Robin Kravets , P. Krishnan, Power management techniques for mobile communication, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.157-168, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288276]
• 23: Rivka Ladin , Barbara Liskov , Liuba Shrira , Sanjay Ghemawat, Providing high availability using lazy replication, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.360-391, Nov. 1992 [doi>10.1145/138873.138877]
• 24: B. Liskov, R. Scheifler, E. Walker and W. Weihl, Orphan detection (extended abstract), in: Proceedings of the 17th International Symposium on Fault-Tolerant Computing (July 1987).
• 25: Joseph P. Macker , M. Scott Corson, Mobile ad hoc networking and the IETF, ACM SIGMOBILE Mobile Computing and Communications Review, v.2 n.1, January 1998 [doi>10.1145/584007.584015]
• 26: F. Mattern, Virtual time and global states of distributed systems, in: Proceedings of the International Workshop on Parallel and Distributed Algorithms (North-Holland, 1989).
• 27: C. Olston and J. Widom, Offering a precision-performance tradeoff for aggregation queries over replicated data, http://www-db.stanford.edu/pub/papers/trapp-ag.ps
• 28: Elena Pagani , Gian Paolo Rossi, Reliable broadcast in mobile multihop packet networks, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.34-42, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262125]
• 29: André Schiper , Jorge Eggli , Alain Sandoz, A New Algorithm to Implement Causal Ordering, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.219-232, September 26-28, 1989
• 30: Michael D. Schroeder , Andrew D. Birrell , Roger M. Needham, Experience with Grapevine: the growth of a distributed system, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.3-23, February 1984 [doi>10.1145/2080.2081]
• 31: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 32: Andrew S. Tanenbaum, Computer networks (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 33: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998 [doi>10.1109/SSDM.1998.688116]

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
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
data replication, distributed databases, satellite networks