Boon Thau Loo

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-177

December 15, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-177.pdf

In this dissertation, we present the design and implementation of declarative networks. Declarative networking proposes the use of a declarative query language for specifying and implementing network protocols, and employs a dataflow framework at runtime for communication and maintenance of network state. The primary goal of declarative networking is to greatly simplify the process of specifying, implementing, deploying and evolving a network design. In addition, declarative networking serves as an important step towards an extensible, evolvable network architecture that can support flexible, secure and efficient deployment of new network protocols.

Our main contributions are as follows. First, we formally define the Network Datalog (NDlog) language based on extensions to the Datalog recursive query language, and propose NDlog as a Domain Specific Language for programming network protocols. We demonstrate that NDlog can be used to express a large variety of network protocols in a handful of lines of program code, resulting in orders of magnitude reduction in code size. For example, the Chord overlay network can be specified in 48 NDlog rules. In addition, the core of the language (Datalog) has polynomial complexity, and our NDlog extensions can be statically analyzed for termination using standard analysis techniques.

Second, to validate the design of NDlog, we present our implementation of P2, which is a full-fledged declarative networking system that compiles NDlog and executes it via a dataflow engine inspired by the Click modular router. We experimentally evaluate the P2 system on hundreds of distributed machines. The P2 system is publicly available for download and has been used in research projects at a number of institutions.

Third, based on our experiences implementing declarative networks, we explore a wide variety of database research issues that are important for the practical realization of declarative networks. These include pipelined execution of distributed recursive queries, reasoning about query semantics based on the well-known distributed systems notion of ¿eventual consistency¿, incorporating the notion of soft-state into the logical framework of NDlog, and the use of query optimizations to improve the performance of network protocols.

Advisors: Joseph M. Hellerstein and Ion Stoica

---

BibTeX citation:

@phdthesis{Loo:EECS-2006-177,
    Author= {Loo, Boon Thau},
    Title= {The Design and Implementation of Declarative Networks},
    School= {EECS Department, University of California, Berkeley},
    Year= {2006},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-177.html},
    Number= {UCB/EECS-2006-177},
    Abstract= {In this dissertation, we present the design and implementation of declarative networks. Declarative networking proposes the use of a declarative query language for specifying and implementing network protocols, and employs a dataflow framework at runtime for communication and maintenance of network state. The primary goal of declarative networking is to greatly simplify the process of specifying, implementing, deploying and evolving a network design. In addition, declarative networking serves as an important step towards an extensible, evolvable network architecture that can support flexible, secure and efficient deployment of new network protocols.

Our main contributions are as follows. First, we formally define the Network Datalog (NDlog) language based on extensions to the Datalog recursive query language, and propose NDlog as a Domain Specific Language for programming network protocols. We demonstrate that NDlog can be used to express a large variety of network protocols in a handful of lines of program code, resulting in orders of magnitude reduction in code size. For example, the Chord overlay network can be specified in 48 NDlog rules. In addition,  the core of the language (Datalog) has polynomial complexity, and our NDlog extensions can be statically analyzed for termination using standard analysis techniques.

Second, to validate the design of NDlog, we present our implementation of P2, which is a full-fledged declarative networking system that compiles NDlog and executes it via a dataflow engine inspired by the Click modular router. We experimentally evaluate the P2 system on hundreds of distributed machines. The P2 system is publicly available for download and has been used in research projects at a number of institutions.

Third, based on our experiences implementing declarative networks, we explore a wide variety of database research issues that are important for the practical realization of declarative networks. These include pipelined execution of distributed recursive queries, reasoning about query semantics based on the well-known distributed systems notion of ¿eventual consistency¿, incorporating the notion of soft-state into the logical framework of NDlog, and the use of query optimizations to improve the performance of network protocols.},
}

EndNote citation:

%0 Thesis
%A Loo, Boon Thau 
%T The Design and Implementation of Declarative Networks
%I EECS Department, University of California, Berkeley
%D 2006
%8 December 15
%@ UCB/EECS-2006-177
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-177.html
%F Loo:EECS-2006-177