Fault isolation for communication networks for isolating the source of faults comprising attacks, failures, and other network propagating errors
First Claim
1. A method for performing attack localization in a network having a plurality of nodes, the method comprising the steps of:
- determining, at each of the plurality of nodes in the network, if there is an attack on the node;
transmitting one or more messages between first and second nodes wherein said first node is upstream from said second node and wherein each of the one or more messages indicates that the node transmitting the message detected an attack at the message transmitting node; and
processing messages received in a message processing one of the first and second nodes to determine if the attack was passed to the message processing node from another node or if the message processing node is a first node to sustain an attack on a certain channel.
2 Assignments
0 Petitions
Accused Products
Abstract
A technique for isolating faults in a communication network is described. The techniques can be utilized in high speed communications networks such as all-optical networks (AONs). The technique is distributed, requires only local network node information and can localize attacks for a variety of network applications. The technique is particularly well suited to the problem of attack propagation which arises in AONs. The technique finds application in a variety of network restoration paradigms, including but not limited to automatic protection switching and loopback protection and provides proper network operation reduced, or in some cases no data loss and bounded delay time regardless of the location of the attack or the physical span of the network. Since the technique is distributed, and its associated delays do not depend on the number of nodes in the network. Hence the technique avoids the computational complexity inherent to centralized approaches. It is thus scalable and relatively rapid. Furthermore, the delays in attack isolation do not depend on the transmission delays in the network. A network management system can therefore offer hard upper-bounds on the loss of data due to failures or attacks. Fault localization with centralized algorithms depends on transmission delays, which are proportional to the distance traversed by the data. Since the described techniques for fault localization are not dependent on centralized computations, the techniques are equally applicable to local area networks, metropolitan area networks, or wide area networks.
204 Citations
16 Claims
-
1. A method for performing attack localization in a network having a plurality of nodes, the method comprising the steps of:
-
determining, at each of the plurality of nodes in the network, if there is an attack on the node;
transmitting one or more messages between first and second nodes wherein said first node is upstream from said second node and wherein each of the one or more messages indicates that the node transmitting the message detected an attack at the message transmitting node; and
processing messages received in a message processing one of the first and second nodes to determine if the attack was passed to the message processing node from another node or if the message processing node is a first node to sustain an attack on a certain channel. - View Dependent Claims (2, 3, 4, 5, 9, 10)
a detection time to detect the input and output signals and processing of the results of that detection, and a time delay associated with generating one or more messages for transmission to at least one of an upstream and a downstream node.
-
-
4. The method of claim 3 wherein said detection time comprises:
-
a time for capturing one or more messages from upstream and/or downstream nodes; and
a time to process the captured messages together with local information.
-
-
5. The method of claim 4 wherein:
-
the first node is upstream of the second node on a first channel which is an attacking channel;
both the first and second nodes identify the attacking channel;
wherein the first node transmits to a second node a finding that the channel is nefarious and the interval between the time when the attack hits the second node and the second node receives a message from the first node that the attack also hit the first node is not greater than a first predetermined period of time; and
wherein the localization of the attack commences at the second node as soon as the attack reaches the second node and the elapsed time until the second node identifies the attack and determines whether the first node also detected that attack is not greater than a second predetermined period of time.
-
-
9. The method of claim 1 wherein said message processing step comprises the steps of:
-
(a) determining a status of the message processing node; and
(b) concluding that said attack was passed to the message processing node if said status indicates an alarm and at least one message was received within a predetermined period of time by the message processing node from the message transmitting node indicating an alarm at the message transmitting node.
-
-
10. The method of claim 9 wherein said message processing step further comprises the step of:
(c) concluding the message processing node was the first node to sustain an attack on said channel if said status indicates an alarm and the message processing node does not receive a message indicating an alarm status at another node within the predetermined period of time.
-
6. A method for processing information in a node of a communication network comprising the steps of:
-
(a) computing a node status S of a node N1 at a time T. (b) transmitting a message including the node status information S to nodes downstream;
(c) determining if the status information indicates an alarm status for the node;
(d) in response to the status information not indicating an alarm status for the node, ending processing;
(e) in response to the status information indicating an alarm status at the node performing the steps of;
(1) determining if any alarm messages arrive at the node within a predetermined time interval;
(2) in response to no alarm messages arriving at the node within the predetermined time interval, setting the node status of the node to alarm; and
(3) in response to at least one alarm message arriving at the node within the predetermined time interval setting the node status of the node to no alarm.
-
-
7. A method for processing information in a node of a communications network comprising the steps of:
-
(a) computing a status of a node at a first time;
(b) transmitting the one or more messages including the node status on arcs leaving the node;
(c) collecting all messages arriving at the node within a predetermined time interval;
(d) computing at least one response to be included in at least one message wherein each of the at least one responses depends upon a node status of the node and information contained in the messages which arrived at the node within the predetermined time interval; and
(e) transmitting at least one message including one of the at least one responses on arcs leaving the node. - View Dependent Claims (8)
-
-
11. Apparatus provided at each of a plurality of nodes of a network for identifying the location of a fault in the network, said apparatus comprising:
-
(a) a fault detector for detecting a fault at a respective node and for providing a fault status signal indicating whether or not said node has experienced a fault and for transmitting said fault status signal to at least one other node in said network; and
(b) a response processor responsive to said fault status signal of the respective node and to a message received by said node from another node in said network within a predetermined time for updating the fault status signal of the respective node. - View Dependent Claims (12, 13)
-
-
14. A network comprising:
-
a plurality of nodes, each one comprising;
a fault detector for providing a fault status signal indicative of whether or not said node has experienced a fault; and
a response processor responsive to said fault status signal and to one or more messages received at said node from other nodes in said network for determining whether or not said fault originated at said node or whether said fault was propagated by the other node; and
at least one channel interconnecting the plurality of nodes.
-
-
15. A method for detecting the source of a fault in a network comprising a plurality of nodes, said method comprising the steps of:
-
(a) generating at a source node data for transmission to a destination node;
(b) transmitting said data to a next node within said network;
(c) transmitting a status message from the source node to said next node;
(d) receiving said data at said next node;
(e) receiving said status message at said next node;
(f) said next node determining whether an attack has been detected at said next node and said source node;
(g) determining whether a status message of said next node is enabled and;
(1) if the status message is enabled, disabling said status message in order to provide an indication that the next node is the source of the attack and transmitting the data and status message to a further next node if the next node is not the destination node; and
(2) if the status message disabled, providing an indication that the next node is not the source of the attack.
-
-
16. A method for optimizing alarm recovery, comprising the steps of:
-
computing the status of a node;
determining whether the computed node status is an alarm status;
receiving a message at the node from a downstream node within a predetermined period of time;
determining whether said received message is an alarm message;
providing an alarm signal if said received message is an alarm message and providing an alert signal if said received message is not an alarm message.
-
Specification