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.
- M. B. Abbott and L. L. Peterson. A language-based approach to protocol implementation. IEEE/ACM Transactions on Networking, 1(1), Feb. 1993. Google ScholarDigital Library
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley, 1995. Google ScholarDigital Library
- D. P. Anderson. Automated protocol implementation with RTAG. IEEE Trans. Softw. Eng., 14(3):291--300, 1988. Google ScholarDigital Library
- 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 ScholarDigital Library
- G. Berry. The Foundations of Esterel, pages 425--454. MIT Press, 1998.Google Scholar
- E. Biagioni. A structured TCP in Standard ML. In Proc. SIGCOMM, 1994. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- M. Handley, A. Ghosh, P. Radoslavov, O. Hodson, and E. Kohler. Designing extensible IP router software. In Proc. NSDI, May 2005. Google ScholarDigital Library
- 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 Scholar
- E. Kohler, M. F. Kaashoek, and D. R. Montgomery. A readable TCP in the Prolac protocol language. In Proc. SIGCOMM, 1999. Google ScholarDigital Library
- 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 ScholarDigital Library
- F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo, CA, 1992. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- P. Maniatis. Historic Integrity in Distributed Systems. PhD thesis, Computer Science Department, Stanford University, Stanford, CA, USA, Aug. 2003. Google ScholarDigital Library
- G. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In Proc. USITS, 2003. Google ScholarDigital Library
- D. Mazières. A toolkit for user-level file systems. In Proc. of the 2001 USENIX Technical Conference, June 2001. Google ScholarDigital Library
- D. Mosberger and L. L. Peterson. Making paths explicit in the Scout operating system. In Proc. OSDI, pages 153--167. ACM Press, 1996. Google ScholarDigital Library
- 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 Scholar
- G. M. Papadopoulos and D. E. Culler. Monsoon: An explicit token store architecture. In Proc. ISCA, May 1990. Google ScholarDigital Library
- V. Raman, A. Deshpande, and J. M. Hellerstein. Using state modules for adaptive query processing. In Proc. ICDE, 2003.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- T. Sellis. Multiple Query Optimization. ACM Transactions on Database Systems, 13(1):23--52, Mar. 1988. Google ScholarDigital Library
- I. Stoica, D. Adkins, S. Zhaung, S. Shenker, and S. Surana. Internet indirection infrastructure. IEEE/ACM Transactions on Networking, (2), Apr. 2004. Google ScholarDigital Library
- 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 ScholarDigital Library
- K. J. Turner, editor. Using formal description techniques -- An Introduction to Estelle, LOTOS and SDL. Wiley, 1993. Google ScholarDigital Library
- A. H. Veen. Dataflow machine architecture. ACM Computing Surveys, 18(4), Dec. 1986. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
Index Terms
Implementing declarative overlays
Recommendations
Implementing declarative overlays
SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principlesOverlay 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 ...
Performance analysis of structured peer-to-peer overlays for mobile networks
Distributed Hash Table DHT based Peer-to-Peer P2P overlays have been widely researched and deployed in many applications such as file sharing, IP telephony, content distribution and media streaming applications. However, their deployment has largely ...
Exploiting the synergy between gossiping and structured overlays
Gossip-based computer networkingIn this position paper we argue for exploiting the synergy between gossip-based algorithms and structured overlay networks (SON). These two strands of research have both aimed at building fault-tolerant, dynamic, self-managing, and large-scale ...
Comments