p(@a,b,[a,c,b], 2) a
p(@e,c,[e,a,c], 2) e
figure 1. nodes in the network are running the shortest-path program. We only show newly derived tuples at each iteration.
p(@e,a,[e,a], 1) e
a l(@a,b, 5) l(@a,c, 1)
e l(@e,a, 1)
network node generates paths of increasing hop count, and
then propagates these paths to neighbor nodes along links.
We show only the derived paths communicated along the
solid lines. In actual query execution, derived tuples can be
sent along the bidirectional network links (dashed links).
In the first iteration, all nodes initialize their local
path tables to 1-hop paths using rule sp1. In the second
iteration, using rule sp2, each node takes the input paths
generated in the previous iteration, and computes 2-hop
paths, which are then propagated to its neighbors. For
example, path(@a,d,[a,b,d], 6) is generated at node
b using path(@b,d,[b,d], 1) from the first iteration,
and propagated to node a. In fact, many network protocols
propagate only the nextHop and avoid sending the entire
As paths are computed, the shortest one is incrementally updated. For example, node a computes the
cost of the shortest path from a to b as 5 with rule sp3,
and then finds the corresponding shortest path [a,b]
with rule sp4. In the next iteration, node a receives
path(@a,b,[a,c,b], 2) from node c, which has lower
cost compared to the previous shortest cost of 5, and hence
shortestPath(@a,b,[a,c,b], 2) replaces the previous tuple (the first two fields of source and destination are
the primary key of this relation).
Interestingly, while NDlog is a language to describe networks, there are no explicit communication primitives.
All communication is implicitly generated during rule
execution as a result of data placement specifications. For
example, in rule sp2, the path and link predicates have
different location specifiers, and in order to execute the rule
body of sp2 based on their matching fields, link and path
tuples have to be shipped in the network. It is the movement
of these tuples that generates the messages for the resulting
2. 4. Language extensions
We describe two extensions to the NDlog language:
link-restricted rules that limit the expressiveness of the language
in order to capture physical network constraints, and a
soft-state storage model commonly used in networking protocols.
Link-restricted rules: In the above path vector protocol, the
evaluation of a rule must depend only on communication
along the physical links. In order to send a message in a low-level network, there needs to be a link between the sender
and receiver. This is not a natural construct in Datalog.
Hence, to model physical networking components where
full connectivity is not available, NDlog provides restrictions
ensuring that rule execution results in communication only
among nodes that are physically connected with a bidirectional link. This is syntactically achieved with the use of the
special link predicate in the form of link-restricted rules.
A link-restricted rule is either a local rule (having the same
location specifier variable in each predicate), or a rule with
the following properties:
1. There is exactly one link predicate in the body.
2. All other predicates (including the head predicate)
have their location specifier set to either the first
(source) or second (destination) field of the link
This syntactic constraint precisely captures the requirement that we be able to operate directly on a network whose
link connectivity is not a full mesh. Further, as we demonstrate in Section 3, link-restriction also guarantees that all
programs with only link-restricted rules can be rewritten
into a canonical form where every rule body can be evaluated
on a single node, with communication to a head predicate
along links. The following is an example of a link-restricted
p(@Dest,...) :- link(@Src,Dest...),p1(@Src,...),
The rule body of this example is executed at @Src and the
resulting p tuples are sent to @Dest, preserving the communication constraints along links. Note that the body predicates of this example all have the same location specifier:
@Src, the source of the link. In contrast, rule sp2 of the
shortest path program is link-restricted but has some relations whose location specifier is the source, and others
whose location specifier is the destination; this needs to be
rewritten to be executable in the network, a topic we return
to in Section 3. 2.
In a fully connected network environment, an NDlog
parser can be configured to bypass the requirement for link-restricted rules.
soft-state storage Model: Many network protocols use the
soft-state approach to maintain distributed state. In the soft-state storage model, stored data have an associated lifetime
or time-to-live (TTL). A soft-state datum needs to be periodically refreshed; if more time than a TTL passes without a
datum being refreshed, that datum is deleted. Soft state is
often favored in networking implementations because in a
very simple manner it provides well-defined eventual consistency semantics. Intuitively, periodic refreshes to network
state ensure that the eventual values are obtained even if
there are transient errors such as reordered messages, node
disconnection, or link failures. However, when persistent
failures occur, no coordination is required to register the