them unmodified. The combined packets can be from individual flows, known as intra-flow coding, or across multiple flows, inter-flow coding.

While intra-flow coding within multicast flows has been well studied, inter-flow coding between unicast flows has received less attention, yet is, perhaps, of more immediate relevance to current Internet traffic. Inter-flow coding is known to be challenging [12]. The task of a network finding a feasible linear network code in a distributed fashion, but with some global sharing of calculations, is investigated in [13] through the use of a genetic algorithm. This task can be formulated as a CSP.

Let G = (*V, E*) denote a directed acyclic multi-graph representing the network with vertices V and edges E. Each vertex represents either a source of an information flow, a destination or router in the network. Edges represent physical connections between these elements. Time is slotted and each edge can transmit a single packet per slot. We allow multiple edges between vertex pairs in order to accommodate higher rate links. It is the goal of each link beyond the source to determine a linear combination of its incoming packets to forward so that ultimately all flows get to their destinations.

As the combination of packets coded by each link will take care of routing, each flow p ∈ P is defined by its source, σ(p) ∈ V , and its destination δ(p) ∈ V . Each flow is assumed to be unit rate with higher rate flows accommodated by flows with the same source and destination vertices. We will treat the collection of source, Sp∈P
{σ(p)}, and destination vertices, Sp∈P
{δ(p)}, as special, solely having one incoming and one outgoing edge per flow respectively.

For each edge i ∈ E, define s(i), s : E 7→ V , to be its source vertex and t(i), t : E 7→ V , to be its target vertex.

For each vertex v ∈ V we define the set of incoming edges Iv := {i ∈ E : t(i) = v} and the set of outgoing edges Ov := {i ∈ E : s(i) = v}. For each edge not corresponding to source, i ∈ E\Sp∈P Oσ(p), we associate a variable xi ∈ D :=
{1*, . . . ,* 2 |P |}, which is an enumeration of the power set of the set of flows P. We define a bijective map ψ : *D 7→ {*0, 1}
|P | that determines a vector whose positive entries correspond to flows to be coded.

In total, we have |E \Sp Oσ(p)| clauses. One for every link that isn't an outgoing link from a source vertex. At each time slot, each link that doesn't correspond to a source or final destination link, i ∈ E \Sp
(Oσ(p) ∪ Iδ(p)), wishes to forward a packet consisting of XORed packets (corresponding to addition in the Galois field of two elements) from the flows indicated by ψ(xi). Each final link i ∈Sp Iδ(p) wishes to forward packets from p, which we indicate by the vector γp with a 1 at the location p and zeros elsewhere. A link and its immediate upstream neighbouring links will be dissatisfied if it cannot do so.

More formally, for each edge not corresponding to the outgoing link from a source or incoming link to a destination, i ∈ E \Sp∈P
(Oσ(p)∪Iδ(p)), we have a clause m ≡ i, Φm(~x),
defined by

$\Phi_{m}(x_{i},x_{j:j\in I_{s(i)}})=\begin{cases}1&\text{if}\exists\,\theta\text{s.t.}\Psi(I_{s(i)})\theta^{T}=\psi(x_{i})^{T}\\ 0&\text{otherwise.}\end{cases}$
4 where θ is a binary vector and Ψ(Is(i)) is the rectangular matrix consisting of ψ(xj )
Tfor j ∈ Is(i) \Sp∈P Oσ(p) and and γ T
p if i ∈ Oσ(p)for some p.

To complete the CSP, we need to ensure that packets from flow p can be decoded at their destination δ(p). For i ∈Sp∈P
Iδ(p), then with δ(p 0) = t(i) we introduce a clause

$$\Phi_{m}(x_{j:j\in I_{s(i)}})=\begin{cases}1&{\mathrm{if~}\exists\,\theta\,\,\mathrm{s.t.~}\Psi(I_{s(i)})\theta^{T}=\gamma_{p^{\prime}}^{T}}\\ 0&{\mathrm{otherwise.}}\end{cases}$$

where again θ is a binary vector and Ψ is is the rectangular matrix defined above. The set of clauses a link variable xi, i ∈ E \ (Sp∈P Oσ(p) ∪ Iδ(p)), participates in is

$${\mathcal{M}}_{i}=\{m\equiv j:j=i{\mathrm{~or~}}i\in I_{s(j)}\}$$

Any variable assignment then satisfies this CSP if and only if it is a realizable network code satisfying all flow demands.

Hence, to find a proper assignment a decentralized CSP
solver requires only that each link i can determine whether: (i)
its own coding is realizable and the coding of its immediately down-stream links are realizable; or (ii) if at least one of these is not realizable. This is sufficient to evaluate eq. (3). Each link does not need to explicitly know: (D3) the code selected by any other link; (D4) the network topology; (D5) any details of how code realizability is determined at any link.

4) Decentralized transmission scheduling. In an Ethernet or WLAN it is necessary to schedule transmissions by stations.

This might be achieved in a centralized manner using TDMA,
but it can also be formulated as a decentralized problem.

The classical CSMA/CA approach to decentralized scheduling never settles to a single schedule and some comes at a cost of the possibility of continual collisions. Recently, there has been interest in decentralized approaches for finding collisionfree schedules, see [14], [15]. This task can be formulated as a CSP as follows. Let V denote the set of transmitters in the WLAN, T denote the set of available time slots and define N = |V | and M = N(N − 1)/2. Let xi be a variable with value equal to the transmission slot selected by transmitter i ∈ V . Define a clause Φm(~x) associated with each pair of transmitters m ≡ (*i, j*) such that

$$\Phi_{m}(x_{i},x_{j})={\begin{cases}1&{\mathrm{if~}}x_{i}\neq x_{j}\\ 0&{\mathrm{otherwise.}}\end{cases}}$$

The participation sets are

$${\mathcal{M}}_{i}=\bigcup_{j\neq i}\{m\equiv(i,j)\}.$$

Any variable assignment satisfies this CSP if and only if it is also a collision-free time-slot schedule. To find a collision-free schedule, when one exists, a decentralized CSP solver requires only that each transmitter i can measure whether: (i) all of its neighbours are using a different time-slot from transmitter i; or (ii) at least one transmitter in the WLAN has selected the same time-slot as transmitter i. Again, this is all that is needed to evaluate eq. (3). Each transmitter does not need to know:
(D3) the time-slot selected by any other transmitter; (D4) the set of transmitters; (D5) the clauses.