Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Building and Optimizing Declarative Networked Systems

David Chiyuan Chu

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-91
June 5, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-91.pdf

In the face of progressively diverse networking technologies and application traffic, it is increasingly infeasible to custom engineer networked systems for each scenario. Moreover, an expanding class of networks, networked embedded systems, are very difficult to program, yet require a high degree of per-deployment programming customization. We investigate a declarative approach to building and optimizing networked systems, with emphasis on networked embedded systems. Our findings indicate that ideas from data management may yield dividends for the design of networked systems in two key areas: (1) declarative interfaces for simplicity yet breadth of expressiveness, and (2) automatic optimizations for automatic performance improvements on the users' behalf. This dissertation reports on three efforts. First, we designed and implemented DSN: a declarative language, runtime and compiler for networked embedded systems. The new logic-based language in DSN has been highly intuitive for programming -- in one case, an algorithm designers' pseudocode mapped nearly line-for-line to working DSN code. Typically, lines-of-code are reduced by an order of magnitude vs. implementations in traditional embedded languages. We built a complementary compiler and runtime that showed negligible performance drop off vs. hand-tuned C implementations. As a result, we have been able to build whole system stacks -- save for device drivers -- entirely declaratively in under a hundred lines of code. Next, we designed and implemented NETOPT, a network optimizer that relieves programmers from having to manually solve two general networking problems: rendezvous and proxy selection. As part of this effort, we created novel program analysis and transformation algorithms to automatically select optimal communication rendezvous and proxies based on traffic and network conditions. When combined with either the DSN system, or similar systems for PC-class devices, user programs get 1-2 orders of magnitude performance improvement without need for programmers' assistance. Lastly, we designed and implemented WIRELESS-NETOPT, an extension of NETOPT for wireless networking. WIRELESS-NETOPT includes three wireless network optimizations from different layers of the networking stack. We show that the declarative interface readily supports such new domain-specific optimizations. Furthermore, these optimizations can be applied automatically and without added programmer effort, benefiting programs by 2x in energy savings.

Advisor: Joseph M. Hellerstein


BibTeX citation:

@phdthesis{Chu:EECS-2009-91,
    Author = {Chu, David Chiyuan},
    Title = {Building and Optimizing Declarative Networked Systems},
    School = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Jun},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-91.html},
    Number = {UCB/EECS-2009-91},
    Abstract = {In the face of progressively diverse networking technologies and application traffic, it is increasingly infeasible to custom engineer networked systems for each scenario.  Moreover, an expanding class of networks, networked embedded systems, are very difficult to program, yet require a high degree of per-deployment programming customization.

We investigate a declarative approach to building and optimizing networked systems, with emphasis on networked embedded systems.  Our
findings indicate that ideas from data management may yield dividends for the design of networked systems in two key areas: (1) declarative interfaces for simplicity yet breadth of expressiveness, and (2) automatic optimizations for automatic performance improvements on the users' behalf.

This dissertation reports on three efforts.  First, we designed and implemented DSN: a declarative language, runtime and compiler for
networked embedded systems.  The new logic-based language in DSN has been highly intuitive for programming -- in one case, an algorithm designers' pseudocode mapped nearly line-for-line to working DSN code.  Typically, lines-of-code are reduced by an order of magnitude vs. implementations in traditional embedded languages.  We built a complementary compiler and runtime that showed negligible performance drop off vs. hand-tuned C implementations.  As a result, we have been able to build whole system stacks -- save for device drivers -- entirely declaratively in under a hundred lines of code.

Next, we designed and implemented NETOPT, a network optimizer that relieves programmers from having to manually solve two general
networking problems: rendezvous and proxy selection.  As part of this effort, we created novel program analysis and transformation
algorithms to automatically select optimal communication rendezvous and proxies based on traffic and network conditions.  When combined with either the DSN system, or similar systems for PC-class devices, user programs get 1-2 orders of magnitude performance
improvement without need for programmers' assistance.

Lastly, we designed and implemented WIRELESS-NETOPT, an extension of NETOPT for wireless networking.  WIRELESS-NETOPT includes three wireless network optimizations from different layers of the networking stack.  We show that the declarative interface readily supports such new domain-specific optimizations.  Furthermore, these optimizations can be applied automatically and without added programmer effort, benefiting programs by 2x in energy savings.}
}

EndNote citation:

%0 Thesis
%A Chu, David Chiyuan
%T Building and Optimizing Declarative Networked Systems
%I EECS Department, University of California, Berkeley
%D 2009
%8 June 5
%@ UCB/EECS-2009-91
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-91.html
%F Chu:EECS-2009-91