Extensible optimization in overlay dissemination trees

ABSTRACT

We introduce XPORT, a profile-driven distributed data dissemination system that supports an extensible set of data types, profile types, and optimization metrics. XPORT efficiently implements a generic tree-based overlay network, which can be customized per application using a small number of methods that encapsulate application-specific data filtering, profile aggregation, and optimization logic. The clean separation between the "plumbing" and "application" enables the system to uniformly support disparate dissemination-based applications.We first provide an overview of the basic XPORT model and architecture. We then describe in detail an extensible optimization framework, based on a two-level aggregation model, that facilitates easy specification of a wide range of commonly used performance goals. We discuss distributed tree transformation protocols that allow XPORT to iteratively optimize its operation to achieve these goals under changing network and application conditions. Finally, we demonstrate the flexibility and the effectiveness of XPORT using real-world data and experimental results obtained from both prototype-based LAN emulation and deployment on PlanetLab.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: S. Banerjee, C. Kommareddy, K. Kar, S. Bhattacharjee, and S. Khuller. Construction of an efficient overlay multicast infrastructure for real-time applications. In INFOCOM, 2003.
• 3: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 4: Antonio Carzaniga , Alexander L. Wolf, Forwarding in a content-based network, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863975]
• 5: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 6: R. Chand , P. A. Felber, A Scalable Protocol for Content-Based Routing in Overlay Networks, Proceedings of the Second IEEE International Symposium on Network Computing and Applications, p.123, April 16-18, 2003
• 7: Y. Diao and M. J. Franklin. Query processing for high-volume xml message brokering. In VLDB, 2003.
• 8: Y. Diao, S. Rizvi, and M. J. Franklin. Towards an internet-scale xml dissemination service. In VLDB, 2004.
• 9: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 10: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 11: Dejan Kostić , Adolfo Rodriguez , Jeannie Albrecht , Amin Vahdat, Bullet: high bandwidth data dissemination using an overlay mesh, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 12: Boon Thau Loo , Tyson Condie , Joseph M. Hellerstein , Petros Maniatis , Timothy Roscoe , Ion Stoica, Implementing declarative overlays, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 13: O. Papaemmanouil, Y. Ahmad, U. Cetintemel, J. Jannotti, and Y. Yildirim. Extensible profile-driven data dissemination. Technical report, Brown University, CS-06-05, 2006.
• 14: Olga Papaemmanouil , Yanif Ahmad , Uğur Çetintemel , John Jannotti , Yenel Yildirim, XPORT: extensible profile-driven overlay routing trees, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142583]
• 15: Olga Papaemmanouil , Ugur Cetintemel, SemCast: Semantic Multicast for Content-Based Data Dissemination, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.242-253, April 05-08, 2005 [doi>10.1109/ICDE.2005.131]
• 16: A. Rodriguez, C. Killian, S. Bhat, D. Kostic, and A. Vahdat. Macedon: Methodology for automatically creating, evaluating, and designing overlay networks. In NSDI, 2004.
• 17: Adolfo Rodriguez , Dejan Kosti , Amin Vahdat, Scalability in Adaptive Multi-Metric Overlays, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.112-121, March 24-26, 2004
• 18: D. Sandler, A. Mislove, A. Post, and P. Druschel. Feedtree: Sharing web micronews with peer-to-peer event notification. In IPTPS, Ithaca, New York, Feb. 2005.
• 19: P. Schwarz , W. Chang , J. C. Freytag , G. Lohman , J. McPherson , C. Mohan , H. Pirahesh, Extensibility in the Starburst database system, Proceedings on the 1986 international workshop on Object-oriented database systems, p.85-92, September 23-26, 1986, Pacific Grove, California, United States
• 20: Yongluan Zhou , Beng Chin Ooi , Kian-Lee Tan , Feng Yu, Adaptive Reorganization of Coherency-Preserving Dissemination Tree for Streaming Data, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.55, April 03-07, 2006 [doi>10.1109/ICDE.2006.13]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.0 GENERAL

General Terms:
Design

Keywords:
dissemination, overlay networks