11.8. Sparse Monitoring, Test Connection, and Routing for More than One Original Attack Flow

To place the monitors and set up test connections for more than one OAF is still an open question. In this section, we extend the results of the previous section and propose a sparse monitoring scheme, which includes monitor placement as well as regular and test connection setting policies for a two-OAF diagnosable network. We call it policy III.

For a two-diagnosable system, we propose that a nonmonitor node u must have D (u) OHMs, and a node u with a pendant node as its neighbor must be a monitor node. Again in a network with bidirectional fiber links and no wavelength conversion, we use test connections in addition to regular connections to make them two-diagnosable.

For test connections, for every nonmonitor node u, if there is a normal connection c on wavelength λ passing through or terminating at u, then one test connection from node u to each OHM is needed if no normal connection provides a monitor-segment on the corresponding link, except when u’s upstream neighbor node is UNN (u, c).

For routing, we use shortest-path routing except in certain specific situations where the routing policy is needed to guarantee the exact location of the OAFs. If the source of a connection c_i is a nonmonitor node that is also on the path of another connection c_j, then c_i must pass through three continuous nodes (n₁, n₂, n₃) ⊈ U(c_j) ∪ U(c_k), where c_k ≠ c_i, c_j is an arbitrary connection in the network.

In the following, we prove that a network is always two-OAF diagnosable if it is designed using the models and policies described above.

Lemma 6. If a connection c_i passes through three continuous nodes that are not in U(c_j), then there is at least one monitor segment msc_i such that msc_i ϵ Γ^–1(c_i), but msc_i ∉ Γ^–1(c_j).

Proof: Suppose that the three continuous nodes are {n₁, n₂, n₃} on c_i. If n₂ is not a monitor node, then both n₁ and n₃ must be monitor nodes. Then, msc_i = (n₂ → n₃) ϵ Γ^–1(c_i), but is not in Γ^–1(c_j), and the Lemma holds. If n₂ is a monitor node, then since both n₁ and n₂ are not in U(c_j), monitor segment msc_i = (n₁ → n₂) ϵ Γ^–1(c_i), but is not in Γ^–1(c_j). Again the result holds.

Thus, we can make the following claim.

Claim 3. A network using Policy III for monitor placement, test connection setup, and routing in a network with bidirectional fiber links and no wavelength converters is two-OAF diagnosable on each wavelength.

Proof: First, it is obvious that for each connection c, at least one monitor node m ϵ U (c). Thus, at least one monitor-segment monitors this connection (i.e., Γ^–1(c) ≠ Ø holds ∀ c ϵ C).

According to Theorem 3, for any three arbitrary connections, c_i, c_j, and c_k, the necessary and sufficient condition for a two-OAF diagnosable network is Γ^–1(c_i) ⊈ Γ^–1(c_j) ∪ Γ^–1(c_k). Because at least one monitor exists on each link, it is easy to argue that, assuming Γ^–1(c_i) ⊄ Γ^–1(c_j) ∪ Γ^{– 1}(c_k), this leads to a contradiction whether the source of connection c_i is a monitor node or not. Thus, under Policy III, the network is two-OAF diagnosable.

11.8.1. Examples

Figure 11.16(a) depicts a nine-node bidirectional mesh network. In this example, this network is a two-OAF diagnosable network. According to our sparse monitor placement policy, four monitor nodes are necessary. Let us say we choose nodes 2, 4, 6, and 8 as the monitor nodes and consider connections on only one wavelength.

The current set of connections consists of {c₁(1 → 2 → 3), c₂(1 → 4 → 7 → 8), c₃(3 → 2 → 5 → 6), c₄(9 → 6 → 5 → 4)}. Two of which are OAFs.

According to our test connection setup policy, for each nonmonitor node, at least one normal connection or one test connection must exist from this node to each of its OHMs, therefore, the test connection set consists of {t₁(5 → 2), t₂(5 → 8), t₃(9 → 8) t₄(3 → 6)}.

Thus, the current monitor-segment set is:

msc = {2c₁, 2c₃, 2t₁, 4c₂, 4c₄, 6c₃, 6c₄, 6t₄, 8c₂, 8t₂, 8t₃}

and the relation matrix between these monitor-segments and the connections is shown in Figure 11.16(b).

Let us assume that connections {c₁(1 → 2 → 3)} and {c₂(1 → 4 → 7 → 8)} are OAFs. Then, we obtain the status of all monitor-segments immediately: S(2c₁) = A = 1, S(2c₃) = Ā = 0, S(2t₁) = Ā = 0, S(4c₂) = A = 1, S(4c₄) = Ā = 0, S(6c₃) = Ā = 0, S(6c₄) = Ā = 0, S(6t₄) = A = 1, S(8c₂) = A = 1, S(8t₂) = Ā = 0, and S(8t₃) = Ā = 0. Thus, is obtained. This results in vector = (0 0 1 1 1 1 1 1). Since S(c₃), S(c₄), S(t₁), S(t₂), S(t₃), and S(t₄) are greater than 0, which means connections c₃, c₄, t₁, t₂, t₃, and t₄ are all IFs. Since S(c₁) = 0 and S(c₂) = 0, it implies that both c₁ and c₂ have unidentified status. Thus, according to Corollary 2, the unidentified connections c₁ and c₂ must be OAFs.

Now, let us assume that only connection c₁ is an OAF in the same network, as shown in Figure 11.17. Because the sets of connections are the same in both cases, the monitor-segment set and the relation matrix will be the same as the previous example. Since we assume that connection {c₁(1 → 2 → 3)} is an OAF, then we can get the status of all monitor-segments immediately: S(2c₁) = A = 1, S(2c₃) = Ā = 0, S(2t₁) = Ā = 0, S(4c₂) = A = 1, S(4c₄) = Ā = 0, S(6c₃) = Ā = 0, S(6c₄) = Ā = 0, S (6t₄) = A = 1, S(8c₂) = Ā = 0, S(8t₂) = Ā = 0, and S(8t₃) = Ā = 0. Thus, is obtained. This results in vector . Since S(c₂), S(c₃), S(c₄), S(t₁), S(t₂), S(t₃), and S(t₄) are greater than 0, which means connections c₂, c₃, c₄, t₁, t₂, t₃, and t₄ are all IFs. Since S(c₁) = 0, it implies that only c₁ has unidentified status. Thus, according to Corollary 2, the unidentified connection c₁ must be the OAF.