8.2 Droplet Sequence Generation
109
path p = (c 1 , m 1 , c 3 , c 4 , c 6 , h 1 , c 9 , c 10 , c 12 , c 14 , c 17 , d 1 , c 19 )
nonDe f ault p at h
p = {c 12 }
two possible paths options exist
path
h 0
0 = (c 1 , c 2 , c 3 , c 4 , c 6 , c 8 , c 9 , c 10 , c 11 )
path
h 0
1 = (c 1 , c 2 , c 3 , c 5 , c 7 , c 10 , c 11 )
p at h
h 0
0
=
nonDe fault
nonDe fault
nonDe fault
p at h
h 0
1
= {c 5 }
path
h 1
0 = (c 1 , c 2 , c 3 , c 4 )
p at h
h 1
0
=
• Paths of the 1 st candidate:path p , path
h 0
0
• Paths of the 2 nd candidate:path p , path
h 0
1 , path
h 1
0
Fig. 8.3 Candidate tree
Example 8.5 Consider the network shown in Fig. 8.2 and the experiment where
the payload should flow through the modules (m 1 , h 1 , d 1 ). Assignments of the
variables introduced before are shown in Fig. 8.3. First, the algorithm considers
the path of the payload, i.e. path p . The payload has to flow through the non-default
successor c 12 of the second bifurcation, i.e. nonDef ault path p = {c 12 }. Therefore,
the default successor c 11 needs to be blocked. This blocking is accomplished by
using a header h 0 . For this header, there are two path options: It can flow along
path
h 0
0 or path
h 0
1 as defined in Fig. 8.3. The first option contains only default
successors (i.e., nonDef ault path
h 0
0
= ∅). The second option contains the nondefault successor c 5 . The blocking of the corresponding default successor c 4 can
be done by a further header h 1 which has to flow along path
h 1
0 consisting of default
successors only.
This recursive procedure of determining path options produces a candidate tree,
which contains all possible sets of header paths. Recall that the options arise from
the different paths through which the headers can flow in order to get to the default
channel which should be blocked.
In order to realize the experiment, a set of paths, i.e. a candidate, has to be
selected. Therefore, the candidate tree is traversed top-down. At each point where
a header has multiple path options, exactly one is selected. The other path options
and their subsequent headers are not required at this point and, therefore, are not
part of the currently considered candidate. Overall, this candidate tree exhaustively
provides all potential candidates, i.e. contains all combinations of the path options.
109
path p = (c 1 , m 1 , c 3 , c 4 , c 6 , h 1 , c 9 , c 10 , c 12 , c 14 , c 17 , d 1 , c 19 )
nonDe f ault p at h
p = {c 12 }
two possible paths options exist
path
h 0
0 = (c 1 , c 2 , c 3 , c 4 , c 6 , c 8 , c 9 , c 10 , c 11 )
path
h 0
1 = (c 1 , c 2 , c 3 , c 5 , c 7 , c 10 , c 11 )
p at h
h 0
0
=
nonDe fault
nonDe fault
nonDe fault
p at h
h 0
1
= {c 5 }
path
h 1
0 = (c 1 , c 2 , c 3 , c 4 )
p at h
h 1
0
=
• Paths of the 1 st candidate:path p , path
h 0
0
• Paths of the 2 nd candidate:path p , path
h 0
1 , path
h 1
0
Fig. 8.3 Candidate tree
Example 8.5 Consider the network shown in Fig. 8.2 and the experiment where
the payload should flow through the modules (m 1 , h 1 , d 1 ). Assignments of the
variables introduced before are shown in Fig. 8.3. First, the algorithm considers
the path of the payload, i.e. path p . The payload has to flow through the non-default
successor c 12 of the second bifurcation, i.e. nonDef ault path p = {c 12 }. Therefore,
the default successor c 11 needs to be blocked. This blocking is accomplished by
using a header h 0 . For this header, there are two path options: It can flow along
path
h 0
0 or path
h 0
1 as defined in Fig. 8.3. The first option contains only default
successors (i.e., nonDef ault path
h 0
0
= ∅). The second option contains the nondefault successor c 5 . The blocking of the corresponding default successor c 4 can
be done by a further header h 1 which has to flow along path
h 1
0 consisting of default
successors only.
This recursive procedure of determining path options produces a candidate tree,
which contains all possible sets of header paths. Recall that the options arise from
the different paths through which the headers can flow in order to get to the default
channel which should be blocked.
In order to realize the experiment, a set of paths, i.e. a candidate, has to be
selected. Therefore, the candidate tree is traversed top-down. At each point where
a header has multiple path options, exactly one is selected. The other path options
and their subsequent headers are not required at this point and, therefore, are not
part of the currently considered candidate. Overall, this candidate tree exhaustively
provides all potential candidates, i.e. contains all combinations of the path options.