11.4. Necessary and Sufficient Conditions for Crosstalk Attack Detection
In this section, we first prove that we can localize all crosstalk attacks in an AON with sparse monitors. Initially, we focus on a special situation where only one crosstalk attack exists on each wavelength in the whole network. Later, we extend this result to a general case where more than one crosstalk attack exists on a wavelength. This work is based on the general principle theory of system level diagnosis [24, 25].
11.4.1. Single Crosstalk Attack in a Network
A network is called one-OAF diagnosable if a single OAF can always be detected and localized. For a given graph G(V, E), let M denote the set of monitor nodes, and let N denote the set of nonmonitor nodes, M ⊆ V, N ⊂ V, and M ∪ N = V. Let C = R∪ T denote the set of connections that exist in the network, where R is the regular set of connections and T is the set of test connections.
Let ci be a connection consisting of nodes {u0, u1, u2,..., uk,...}. Let U(ci) denote the set of nodes on connection ci’s path. Then, cij denotes a one-hop segment (uj→uj+1) on connection ci.
11.4.2. Monitoring Relationship
There are three kinds of relations between a monitor and a connection:
Direct-Monitor. A monitor m is a direct-monitor of a connection c if mϵU (c). As shown in Figure 11.6, monitor m2 is a direct-monitor of connection c1 because m2 is on connection c1’s path: m2 ϵ U(c1).
One-Hop Monitor. A monitor m is a one-hop monitor of a connection c if m ∉ U(c) and ∃ (u → m), where u ϵ U(c). As shown in Figure 11.6, monitor m1 is a one-hop monitor of connection c1 because m1 is not on connection c1’s path: m1 ∉ U(c1) and ∃ (2 → m1)⊆ connection c2, where node 2 ϵ U(c1).
Nonmonitor. A monitor m is a nonmonitor of a connection c if m ∉ U(c) and ∄ (u → m), where u ϵ U (c). In Figure 11.6, both monitors m1 and m2 are nonmonitors of connection c3, because m1, m2 ∉ U(c3), and ∄ (u → m1or m2) in any existing connection, where u ϵ U(c3).
Figure 11.6. Relation between a monitor and a connection.
Monitor-Segment
A monitor-segment mscij is a one-hop segment cij, where node uj+1 is a monitor. Let MSC denote the set of the monitor-segments. Let mscij denote this particular monitor-segment. Mostly, we use msc to denote a common monitor segment. Two monitor-segments are shown in Figure 11.7: one is made by connection c2 and monitor node m1, denoted by m1c2, while the other is made by a one-hop segment on connection c1, from node 2 to node m2, and monitor node m2, denoted by m2c1.
A monitor-segment msc = (u → m) is monitoring a connection c if the monitor m is a direct-monitor of this connection, where the segment (u → m) ϵ c, or if the monitor m is a one-hop monitor of a connection c, where u ϵ U(c), and m ∉ U(c).
For example, in Figure 11.7, monitor m2 is a direct-monitor for connection c1, and monitor m1 is a one-hop monitor for connection c1. According to our definition, both monitor-segments m1c2 and m2c1 are monitoring connection c1, and neither of them is monitoring connection c3. Let (msc, c) denote this relation between monitor-segment msc and connection c. Consequently, the status of the segment (u → m) indicated by monitor m is the status of the monitor-segment, denoted by S (msc). S (msc) can be either A or Ā. For example, in Figure 11.7, if the status of c2 in monitor m1 is indicated as A, then the status of the monitor segment S (m1c2) is A.
Figure 11.7. Attack monitoring mechanism and monitor-segment
The status of a connection can be either innocent flow (IF) or uncertain. IF means that the connection is determined as IF, and uncertain means that the connection cannot be determined either as IF or as OAF. Let S (c) denote the status of connection c. Table 11.1 shows the relations between a monitor-segment status and its monitoring connection’s status. For a connection c, which is not being monitored by msc, we say that msc has nonmonitoring relation with c. Table 11.1 shows the relations between a monitor-segment and its nonmonitoring connection.
| Relation | S(msc) | S(c) |
|---|---|---|
| msc monitoring c | A | uncertain |
| (msc, c) | Ā | IF |
| msc nonmonitoring c | A | IF |
| Ā | uncertain |
Figure 11.8 depicts two special cases of monitor-segments. Figure 11.8(a) shows the monitor m as the originating node of the connection c. For this case, monitor m and connection c make up a special monitor-segment msc, and only connection c is monitored by this monitor-segment, while all other connections are not monitored. If S (msc) = A, all other connections can be identified as IF. Figure 11.8(b) shows the relation between a monitor segment msc1 and a connection c2, where c1 ∉ c2, and n, m ϵ U (c2). In this case, both c1 and c2 share the same nodes n and m. While it seems that c2 is monitored by msc1, in fact the relation between connection c2 and the monitor-segment msc1 is nonmonitoring. This can be explained as follows. According to our definition of monitoring, the only two cases of monitoring are either the segment is a part of the monitored connection (that is clearly not the case here), or the monitored connection does not pass through the monitor (which is also not true here). The example provided by Figure 11.8(b) does not fit either of these definitions and the statement is true. Hence this is a nonmonitor relation.
Figure 11.8. Special monitor-segment.
We represent the connections and monitors using a bipartite graph. Figure 11.9(a) shows the network graph G(V, E). Figure 11.9(b) shows a graph with all connections separated into one-hop segments, for example, c1–1 is the first segment of connection c1. Figure 11.9(c) depicts the bipartite graph G′(V′, E′) for the shown connections. In graph G′(V′, E′), the vertices set V′ = {mcij}∪{Ck} consists of the monitor-segments and the connection (i.e., mcij ϵ MC), and ck ϵ C. For example, 3c12 is a monitor-segment made up by monitor node 3 and one-hop segment c12, shown in Figure 11.9(b). An edge in G′ depicts a relation between a monitor segment and a connection. In the figure, a directed edge from a monitor-segment msc to a connection c describes the monitoring relation between this pair of monitor-segment and connection, and (msc, c) denotes the edge.
Let Γ(msci) = {cj|(msci, cj ϵ E′} denote the set of connections monitored by a monitor-segment msci. Let γ–1(ci) = {mscj|(mscj, ci) ϵ E′} denote the set of monitor-segments monitoring a connection ci.
A connection is called unidentified if we cannot obtain the status of the connection directly from the status of the set of all monitor-segments in the network. Figure 11.10 shows an example to help understand this concept. A network and its connections are shown in Figure 11.10. If connection c1 is the OAF, according to the truth table, we can identify the status for both the monitor-segments and connections, as shown in Table 11.2. The monitor-segments can only identify the status of c2 and c3 as IF and the status of connection c1 as uncertain according to both monitor-segments’ results.
Figure 11.10. Unidentified connection.
| Monitor-Segments | S(msc) | S(c1) | S(c2) | S(c3) |
|---|---|---|---|---|
| S(1c2) | A | uncertain | uncertain | IF |
| S(3c3) | A | uncertain | IF | uncertain |