Implementing declarative overlays

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: Mark B. Abbott , Larry L. Peterson, A language-based approach to protocol implementation, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.4-19, Feb. 1993 [doi>10.1109/90.222903]
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: D. P. Anderson, Automated Protocol Implementation with RTAG, IEEE Transactions on Software Engineering, v.14 n.3, p.291-300, March 1988 [doi>10.1109/32.4650]
• 4: Hari Balakrishnan , Magdalena Balazinska , Don Carney , Uğur Çetintemel , Mitch Cherniack , Christian Convey , Eddie Galvez , Jon Salz , Michael Stonebraker , Nesime Tatbul , Richard Tibbetts , Stan Zdonik, Retrospective on Aurora, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.370-383, December 2004 [doi>10.1007/s00778-004-0133-5]
• 5: G. Berry. The Foundations of Esterel, pages 425--454. MIT Press, 1998.
• 6: Edoardo Biagioni, A structured TCP in standard ML., Proceedings of the conference on Communications architectures, protocols and applications, p.36-45, August 31-September 02, 1994, London, United Kingdom
• 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.
• 8: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 9: Walid Dabbous , Sean O'Malley , Claude Castelluccia, Generating efficient protocol code from an abstract specification, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.60-72, August 28-30, 1996, Palo Alto, California, United States
• 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.
• 11: Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
• 12: David J. DeWitt , Robert H. Gerber , Goetz Graefe , Michael L. Heytens , Krishna B. Kumar , M. Muralikrishna, GAMMA - A High Performance Dataflow Database Machine, Proceedings of the 12th International Conference on Very Large Data Bases, p.228-237, August 25-28, 1986
• 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.
• 14: Goetz Graefe, Encapsulation of parallelism in the Volcano query processing system, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.102-111, May 23-26, 1990, Atlantic City, New Jersey, United States
• 15: M. Handley, A. Ghosh, P. Radoslavov, O. Hodson, and E. Kohler. Designing extensible IP router software. In Proc. NSDI, May 2005.
• 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.
• 17: Eddie Kohler , M. Frans Kaashoek , David R. Montgomery, A readable TCP in the Prolac protocol language, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.3-13, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 18: 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]
• 19: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 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.
• 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.
• 22: Petros Maniatis , Mary Baker, Historic integrity in distributed systems, 2003
• 23: G. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In Proc. USITS, 2003.
• 24: David Mazières, A Toolkit for User-Level File Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.261-274, June 25-30, 2001
• 25: David Mosberger , Larry L. Peterson, Making paths explicit in the Scout operating system, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.153-167, October 29-November 01, 1996, Seattle, Washington, United States
• 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.
• 27: Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.82-91, May 28-31, 1990, Seattle, Washington, United States
• 28: V. Raman, A. Deshpande, and J. M. Hellerstein. Using state modules for adaptive query processing. In Proc. ICDE, 2003.
• 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.
• 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.
• 31: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 32: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 33: Ion Stoica , Daniel Adkins , Shelley Zhuang , Scott Shenker , Sonesh Surana, Internet indirection infrastructure, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.205-218, April 2004 [doi>10.1109/TNET.2004.826279]
• 34: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 35: Kenneth J. Turner, Using Formal Description Techniques: An Introduction to Estelle, Lotos, and SDL, John Wiley & Sons, Inc., New York, NY, 1993
• 36: Arthur H. Veen, Dataflow machine architecture, ACM Computing Surveys (CSUR), v.18 n.4, p.365-396, Dec. 1986 [doi>10.1145/27633.28055]
• 37: S. T. Vuong , A. C. Lau , R. I. Chan, Semiautomatic Implementation of Protocols Using an Estelle-C Compiler, IEEE Transactions on Software Engineering, v.14 n.3, p.384-393, March 1988 [doi>10.1109/32.4658]
• 38: Brian White , Jay Lepreau , Leigh Stoller , Robert Ricci , Shashi Guruprasad , Mac Newbold , Mike Hibler , Chad Barb , Abhijeet Joglekar, An integrated experimental environment for distributed systems and networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060313]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Design, Experimentation, Languages

Keywords:
dataflow engines, declarative overlays, executable pseudocode