skip to main content
article

Implementing declarative overlays

Published:20 October 2005Publication History
Skip Abstract Section

Abstract

Overlay networks are used today in a variety of distributed systems ranging from file-sharing and storage systems to communication infrastructures. However, designing, building and adapting these overlays to the intended application and the target environment is a difficult and time consuming process.To ease the development and the deployment of such overlay networks we have implemented P2, a system that uses a declarative logic language to express overlay networks in a highly compact and reusable form. P2 can express a Narada-style mesh network in 16 rules, and the Chord structured overlay in only 47 rules. P2 directly parses and executes such specifications using a dataflow architecture to construct and maintain overlay networks. We describe the P2 approach, how our implementation works, and show by experiment its promising trade-off point between specification complexity and performance.

References

  1. M. B. Abbott and L. L. Peterson. A language-based approach to protocol implementation. IEEE/ACM Transactions on Networking, 1(1), Feb. 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. D. P. Anderson. Automated protocol implementation with RTAG. IEEE Trans. Softw. Eng., 14(3):291--300, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. H. Balakrishnan, M. Balazinska, D. Carney, U. Cetintemel, M. Cherniack, C. Convey, E. Galvez, J. Salz, M. Stonebraker, N. Tatbul, R. Tibbetts, and S. Zdonik. Retrospective on Aurora. VLDB Journal, 13(4), Dec. 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. G. Berry. The Foundations of Esterel, pages 425--454. MIT Press, 1998.Google ScholarGoogle Scholar
  6. E. Biagioni. A structured TCP in Standard ML. In Proc. SIGCOMM, 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Y.-H. Chu, S. G. Rao, and H. Zhang. A case for end system multicast. In Proc. of ACM SIGMETRICS, pages 1--12, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. W. Dabbous, S. W. O'Malley, and C. Castelluccia. Generating efficient protocol code from an abstract specification. In Proc. SIGCOMM, pages 60--72, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. F. Dabek, J. Li, E. Sit, F. Kaashoek, R. Morris, and C. Blake. Designing a DHT for low latency and high throughput. In Proc. NSDI, Month 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. S. Deering and D. R. Cheriton. Multicast routing in datagram internetworks and extended LANs. ACM Transactions on Computer Systems, 8(2):85--111, May 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. D. J. DeWitt, R. H. Gerber, G. Graefe, M. L. Heytens, K. B. Kumar, and M. Muralikrishna. Gamma - a high performance dataflow database machine. In VLDB, pages 228--237, 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. M. Fecko, M. Uyar, P. Amer, A. Sethi, T. Dzik, R. Menell, and M. McMahon. A success story of formal description techniques: Estelle specification and test generation for MIL-STD 188-220. Computer Communications (Special Edition on FDTs in Practice), 23, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. G. Graefe. Encapsulation of parallelism in the Volcano query processing system. In Proc. of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990, pages 102--111. ACM Press, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. M. Handley, A. Ghosh, P. Radoslavov, O. Hodson, and E. Kohler. Designing extensible IP router software. In Proc. NSDI, May 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. R. Huebsch, B. N. Chun, J. M. Hellerstein, B. T. Loo, P. Maniatis, T. Roscoe, S. Shenker, I. Stoica, and A. R. Yumerefendi. The architecture of PIER: an Internet-scale query processor. In CIDR, pages 28--43, 2005.Google ScholarGoogle Scholar
  17. E. Kohler, M. F. Kaashoek, and D. R. Montgomery. A readable TCP in the Prolac protocol language. In Proc. SIGCOMM, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. E. Kohler, R. Morris, B. Chen, J. Jannotti, and M. F. Kaashoek. The Click modular router. ACM Trans. Comput. Syst., 18(3):263--297, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo, CA, 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. J. Li, J. Stribling, T. Gil, R. Morris, and F. Kaashoek. Comparing the performance of distributed hash tables under churn. In Proc. IPTPS, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. B. T. Loo, J. M. Hellerstein, and I. Stoica. Customizable routing with declarative queries. In Third Workshop on Hot Topics in Networks (HotNets-III), Nov. 2004.Google ScholarGoogle Scholar
  22. P. Maniatis. Historic Integrity in Distributed Systems. PhD thesis, Computer Science Department, Stanford University, Stanford, CA, USA, Aug. 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. G. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In Proc. USITS, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. D. Mazières. A toolkit for user-level file systems. In Proc. of the 2001 USENIX Technical Conference, June 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. D. Mosberger and L. L. Peterson. Making paths explicit in the Scout operating system. In Proc. OSDI, pages 153--167. ACM Press, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. S. Manku, C. Olston, J. Rosenstein, and R. Varma. Query processing, approximation, and resource management in a data stream management system. In Proc. CIDR, 2003.Google ScholarGoogle Scholar
  27. G. M. Papadopoulos and D. E. Culler. Monsoon: An explicit token store architecture. In Proc. ISCA, May 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. V. Raman, A. Deshpande, and J. M. Hellerstein. Using state modules for adaptive query processing. In Proc. ICDE, 2003.Google ScholarGoogle Scholar
  29. S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling Churn in a DHT. In Proc. of the 2004 USENIX Technical Conference, Boston, MA, USA, June 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. A. Rodriguez, C. Killian, S. Bhat, D. Kostic, and A. Vahdat. MACEDON: Methodology for Automatically Creating, Evaluating, and Designing Overlay Networks",. In Proc. NSDI, March 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In SIGMOD Conference, pages 23--34, 1979. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. T. Sellis. Multiple Query Optimization. ACM Transactions on Database Systems, 13(1):23--52, Mar. 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. I. Stoica, D. Adkins, S. Zhaung, S. Shenker, and S. Surana. Internet indirection infrastructure. IEEE/ACM Transactions on Networking, (2), Apr. 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw., 11(1):17--32, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. K. J. Turner, editor. Using formal description techniques -- An Introduction to Estelle, LOTOS and SDL. Wiley, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. A. H. Veen. Dataflow machine architecture. ACM Computing Surveys, 18(4), Dec. 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. S. T. Vuong, A. C. Lau, and R. I. Chan. Semiautomatic implementation of protocols using an Estelle-C compiler. IEEE Transactions on Software Engineering, 14(3), Mar. 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  38. B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. An integrated experimental environment for distributed systems and networks. In Proc. OSDI 2002, Boston, MA, Dec. 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Implementing declarative overlays

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in

      Full Access

      • Published in

        cover image ACM SIGOPS Operating Systems Review
        ACM SIGOPS Operating Systems Review  Volume 39, Issue 5
        SOSP '05
        December 2005
        290 pages
        ISSN:0163-5980
        DOI:10.1145/1095809
        Issue’s Table of Contents
        • cover image ACM Conferences
          SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles
          October 2005
          259 pages
          ISBN:1595930795
          DOI:10.1145/1095810

        Copyright © 2005 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 20 October 2005

        Check for updates

        Qualifiers

        • article

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader