Declarative Networking
By Boon Thau Loo, Tyson Condie, Minos Garofalakis, David E. Gay, Joseph M. Hellerstein, Petros Maniatis,
Raghu Ramakrishnan, Timothy Roscoe, and Ion Stoica
abstract
Declarative Networking is a programming methodology
that enables developers to concisely specify network protocols and services, which are directly compiled to a dataflow
framework that executes the specifications. This paper provides an introduction to basic issues in declarative networking, including language design, optimization, and dataflow
execution. We present the intuition behind declarative programming of networks, including roots in Datalog, extensions for networked environments, and the semantics of
long-running queries over network state. We focus on a
sublanguage we call Network Datalog (NDlog), including
execution strategies that provide crisp eventual consistency
semantics with significant flexibility in execution. We also
describe a more general language called Overlog, which
makes some compromises between expressive richness and
semantic guarantees. We provide an overview of declarative network protocols, with a focus on routing protocols
and overlay networks. Finally, we highlight related work in
declarative networking, and new declarative approaches to
related problems.
1. intRoDuction
Over the past decade there has been intense interest in the
design of new network protocols. This has been driven from
below by an increasing diversity in network architectures
(including wireless networks, satellite communications,
and delay-tolerant rural networks) and from above by a
quickly growing suite of networked applications (
peer-to-peer systems, sensor networks, content distribution, etc.)
Network protocol design and implementation is a challenging process. This is not only because of the distributed nature and large scale of typical networks, but also
because of the need to balance the extensibility and flexibility of these protocols on one hand, and their robustness
and efficiency on the other hand. One needs to look no
further than the Internet for an illustration of these hard
trade-offs. Today’s Internet routing protocols, while arguably robust and efficient, make it hard to accommodate
the needs of new applications such as improved resilience
and higher throughput. Upgrading even a single router is
hard. Getting a distributed routing protocol implemented
correctly is even harder. Moreover, in order to change or
upgrade a deployed routing protocol today, one must get
access to each router to modify its software. This process
is made even more tedious and error-prone by the use of
conventional programming languages.
In this paper, we introduce declarative networking, an
application of database query language and processing techniques to the domain of networking. Declarative networking
is based on the observation that network protocols deal at
their core with computing and maintaining distributed state
(e.g., routes, sessions, performance statistics) according to
basic information locally available at each node (e.g., neighbor tables, link measurements, local clocks) while enforcing
constraints such as local routing policies. Recursive query
languages studied in the deductive database literature27
are a natural fit for expressing the relationship between
base data, derived data, and the associated constraints. As
we demonstrate, simple extensions to these languages and
their implementations enable the natural expression and
efficient execution of network protocols.
In a series of papers with colleagues, we have described
how we implemented and deployed this concept in the P2
declarative networking system.
24 Our high-level goal has
been to provide software environments that can accelerate
the process of specifying, implementing, experimenting
with and evolving designs for network architectures.
As we describe in more detail below, declarative networking can reduce program sizes by orders of magnitude
relative to traditional approaches, in some cases resulting in
programs that are line-for-line translations of pseudocode
in networking research papers. Declarative approaches also
open up opportunities for automatic protocol optimization
and hybridization, program checking, and debugging.
2. LanGuaGe
In this section, we present an overview of the Network Datalog
(NDlog) language for declarative networking. The NDlog
language is based on extensions to traditional Datalog, a
well-known recursive query language designed for querying graph-structured data in a centralized database. NDlog’s
integration of networking and logic is unique from the perspectives of both domains. As a network protocol language, it
is notable for the absence of any communication primitives
like “send” or “receive”; instead, communication is implicit
in a simple high-level specification of data partitioning. In
comparison to traditional logic languages, it is enhanced
to capture typical network realities including distribution,
link-layer constraints on communication (and hence deduction), and soft-state8 semantics.
We step through an example to illustrate the standard
execution model for Datalog, and demonstrate its close
connections to routing protocols, recursive network graph
computations, and distributed state management. We then
describe the Overlog
21 extensions to the NDlog language that
support soft-state data and events.
A previous version of this paper was published in
Proceedings of ACM SIGMOD’s International Conference of
Management of Data (2006).