11.7. Sparse Monitoring and Routing Algorithms

Thus far we established conditions for monitoring and diagnosing attacks. To find out the exact location of an OAF in a network, we have to determine monitor placement and a routing policy that work together in such a way that we can meet the necessary and sufficient conditions. We cannot satisfy the conditions if several connections neither traverse a monitor nor pass through nodes next to a monitor.

We develop several sparse monitoring and the corresponding routing policies. The conditions require that there must be at least one monitor-segment on every connection. Thus, with a given monitor placement policy, the routing policy needs to route connections through at least one monitor or its neighbor. Obviously, a smaller number of monitors places more restrictions on the routing policies. This has an adverse impact on the blocking probability. Since sparse monitor placement is a difficult problem, only heuristic solutions are given here.

11.7.1. Sparse Monitoring, Test Connection, and Routing for a Single Original Attack Flow Policy I

To detect a single OAF, we need the following definitions. If a monitor is connected directly to a nonmonitor node u, then the monitor is said to be a one-hop-distance monitor (OHM). OHM (u) denotes the set of OHMs for node u. The degree of node u is denoted by D (u). A node with a degree of one is called a pendant node.

To guarantee the exact location of the OAF in a network, we suggest the following sparse monitor placement policy: (1) every nonmonitor node u should have D (u)≥ 2, (2) a nonmonitor node u must have D (u) OHMs, and (3) a node u with a pendant node as its neighbor must be a monitor node.

We assume that each link in the network is bidirectional so that there is one fiber in each of two directions on each link. In the network, there are two kinds of connections set up: one is the normal connection, which is set up by users and the other is the test connection, which is requested by the network management system. A test connection is used to determine if a node is a PAN or not. For a nonmonitor node, if there is a normal connection on wavelength λ terminating at this node and no normal connection provides a monitor-segment on the corresponding link, then one test connection from this node to each OHM is needed.

We normally use shortest-path routing except in one case to guarantee the exact location of the OAF in a network. For any two normal connections (excluding test connections) originating from the same nonmonitor node, at least one must pass through three different (including source and destination) nodes (i.e., ∀c_i, c_j ϵ R, and c_i = {u₀,...}, c_j = {u₀,...}, then either ∃{u_a, u_b, u_c} ⊂ c_i but ⊄ c_j or ∃{u_a, u_b, u_c} ⊂ c_j but ⊄ c_i).

According to our crosstalk attack model, the crosstalk attack only affects the same wavelength connections at the wavelength selective switch. To simplify our analysis, we assume that (1) there is no wavelength converter (in case there is one, then the monitor is required to detect attack conditions across conversions) in the whole network, and (2) for each link only one fiber exists in each direction. Then we claim the following.

Claim 1. With the above monitor placement, test connection setup, and routing policy, a network with one fiber on each link and without a wavelength converter is one-OAF diagnosable on each wavelength.

Proof: We only provide an outline of a proof. Since each fiber (wavelength) link has a monitor node on at least one of the ends, each monitor segment is monitored. Thus, Γ^–1(c) ≠ Ø holds ∀ c ϵ C. Moreover with the routing policy, no two connections have the same segments, and therefore, Γ^–1(c_i) ≠ Γ^–1(c_j). Thus, under this condition, the network is one-OAF diagnosable.

Since attacks do not propagate from one wavelength to another, therefore, we can always detect OAFs on all wavelengths in the whole network, if there is only one OAF on each wavelength.

11.7.2. Examples

Figure 11.13(a) depicts a four-node bidirectional mesh network with two monitor nodes, 2 and 4, and only one wavelength.

Suppose the following connections exist and one of them is an OAF. The connection set consists of {c₁(1 → 4), c₂(1 → 2 → 3), c₃(3 → 4 → 1), c₄(3 → 2 → 1)}. For each nonmonitor node, one normal connection exists from this node to everyone of its OHMs, thus according to our test connection setup policy, no test connection is necessarily needed.

Thus, the current monitor-segment set is msc = {2c₂, 2c₄, 4c₁, 4c₃}, and the relation matrix between these monitor-segments and the connections is shown in Figure 11.13(b).

Figure 11.13. Diagnose the OAF in a network without a test connection.

[View full size image]

Let us assume that connection {c₂(1 → 2 → 3)} is the OAF. Then, we can get the status of all monitor-segments as folllows: S(2c₂) = A = 1, S(2c₄) = Ā = 0, S(4c₁) = A = 1, and S(4c₃) = A = 1. Thus, and vector .

Since S (c₁), S (c₃), and S (c₄) are all greater than 0, this means that connections c₁, c₃, and c₄ are all IFs. Also S (c₂) = 0, which means that c₂ is in unidentified status. Thus, the only unidentified connection c₂ must be an OAF.

Now, let us assume that connection c₃ does not exist. Then, according to our test connection setup policy, a test connection t₃ is established from node 3 to node 4 because of a lacking monitor-segment on link (3, 4), as shown in Figure 11.14(a). Then, as shown in Figure 11.14(b), we can get the relation matrix of monitor-segments and connections. By using the same method as shown in the previous example, we obtain the vector , from which we can determine the only unidentified connection c₂ as the OAF.

Figure 11.14. Diagnose the OAF in a network with a test connection.

[View full size image]

11.7.3. Sparse Monitoring, Test Connection, and Routing Policy II

The previous method requires a lot of monitor nodes in a network (more than half). To reduce the total number of monitor nodes in a network, we propose another heuristic method. With this new method, fewer monitors are required in the whole AON. In this case, we need to change the test connection and routing scheme.

We require that any nonmonitor node u must have at least one OHM. Moreover, for any monitor or nonmonitor node, if there is a normal connection passing through or terminating at this node, then there must be one test connection from this node to each OHM (if an OHM exists) that must exist if there is no normal connection that exists on the corresponding link. In other words, there must be either a regular or a test connection from a node to each of its OHMs.

For routing, we use shortest-path routing except in the following cases:

Comparing this policy with the previous sparse monitor policy (Policy I) where any nonmonitor node u requires D (u) OHMs, we see that this new method only requires one OHM for each nonmonitor node. Considering the expense of a monitor, this is a big advantage. Now we make the following claim.

Claim 2. With the above new sparse monitoring policies, a network is one-OAF diagnosable.

Proof: Again we provide an informal proof. It is easy to see that we cannot find two connections in the network such that Γ^–1(c_i) = Γ^–1(c_j). Thus, under this condition, the network is one-OAF diagnosable. More details can be found in Wu and Somani [16, 19].

11.7.4. Connection Routing Algorithm in One–Original Attack Flow Networks

In this section we develop a practical routing algorithm. Without loss of generality, we develop a variant of the shortest-path algorithm that satisfies the above routing constraints. The pseudo code for the algorithm is given below.

BEGIN:
							Given a node request.
							Run Shortest-Path-Algorithm to find the source-destination path. /*Test connections are ignored to compute the path and removed if the path uses links with test connections*/.
							IF Fail to find any available path, reject this request,
							ELSE find one path P1,
							IF source node s is a monitor node,
							THEN accept this request and set up this connection with path P1.
							ELSE source node s is a nonmonitor node,
							Check number of nodes n on P1,
							IF
								n ≥ 3,
							THEN accept this request and set up this connection with path P1.
							ELSE check all existing connections originated from s,
							IF all existing connections’ paths include at least three nodes,
							THEN accept this request and set up this connection with path P1.
							ELSE remove one link on path P1 from original graph and reiterate the algorithm.
							ENDIF
							ENDIF
							ENDIF
							ENDIF
							END

Suppose the maximum output degree of network nodes is Max{D(u)} = d_N, then, with this routing algorithm, at most d_N connections need to be checked before we can make a decision for the connection request.

11.7.5. Example

Figure 11.15(a) depicts a nine-node bidirectional mesh network. According to the sparse monitor placement policy, only three monitor nodes are necessary in this network. Here, we choose nodes 4, 5, and 6 as the monitor nodes and the remaining nodes as nonmonitor nodes. By considering attack connections that are on the same wavelength to simplify our example, we assume that only one wavelength is supported in this network.

Suppose a normal connection set consists of {c₁(1 → 2 → 3 → 6), c₂(2 → 1 → 4 → 5), c₃(3 → 2 → 5 → 6), c₄(9 → 6 → 5 → 4)}, and only one of them is an OAF.

According to our test connection setup policy, no test connection is necessarily needed. Thus, the current monitor-segment set is msc = {4c₂, 4c₄, 5c₃, 5c₄, 6c₁, 6c₃, 6c₄}, and the relation matrix between these monitor-segments and the connections is shown in Figure 11.15(b).

Figure 11.15. Single-wavelength crosstalk attack diagnosable network.

[View full size image]

Let us assume that connection {c₁(1 → 2 → 3 → 6)} is the OAF. Then, we can get the status of all monitor-segments immediately: S(4c₂) = A = 1, S(4c₄) = Ā = 0, S(5_c3) = A = 1, S(5_c4) = A = 1, S(6c₁) = A = 1, S(6c₃) = Ā = 0, and S(6c₄) = Ā = 0. Thus, and vector =(0111) are obtained.

The values of S(c₂), S(c₃), and S(c₄) are greater than 0, implying that connections c₂, c₃, and c₄ are all IFs, while S(c₁) = 0 implies that connection c₁ is in the unidentified status. Thus, the only unidentified connection c₁ must be an OAF.