p(@a,d,[a,b,d], 6) p(@a,b,[a,c,b], 2) a p(@e,b,[e,a,b], 6) p(@e,c,[e,a,c], 2) e

1

figure 1. nodes in the network are running the shortest-path program. We only show newly derived tuples at each iteration.

p(@a,b,[a,b], 5) p(@a,c,[a,c], 1)

c l(@c,b, 1)

5

1

a

b 5

1

1

p(@b,d,[b,d], 1) p(@e,a,[e,a], 1) e

1

a l(@a,b, 5) l(@a,c, 1) e l(@e,a, 1)

1

1

5

b

d

Initially l(@b,d, 1)

1

c

1 p(@c,b,[c,b], 1)

b c

1 p(@c,d,[c,b,d], 2)

 

First iteration d

1

Second iteration d

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 path vector.

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 network protocol.

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 predicate.

 

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 rule:

p(@Dest,...) :- link(@Src,Dest...),p1(@Src,...),

p2(@Src,...),..., pn(@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