Self-checking pair on a braided ring network

• US 7,372,859 B2
• Filed: 12/10/2004
• Issued: 05/13/2008
• Est. Priority Date: 11/19/2003
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Driscoll, Kevin R., Hall, Brendan, Paulitsch, Michael
• Primary Examiner(s): QURESHI, AFSAR M
• Application Number:
  US11/010,249
• Publication Number:
  US 20050152379A1
• Time in Patent Office: 1,250 Days
• Field of Search: 370/258, 370/270, 370/360, 370/400, 370/407, 370/425, 370/498, 370/447, 370/503, 455/422.1, 455/419, 455/453, 455/555, 375/211, 710/36, 710/100, 710/305, 709/240, 709/225
• US Class Current: 370/400
• CPC Class Codes: G06F 11/2007 using redundant communication media
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085

Abstract

In one embodiment, one or more self checking pairs are implemented at the application layer in a network that supports the qualified propagation of data at the transport layer (for example, in a network having a braided ring topology).

Claims

1. A network comprising:

a plurality of nodes that are communicatively coupled to one another over first and second channels that form first and second rings, respectively; and

at least one self checking pair comprising at least two of the plurality of nodes;

wherein each node is communicatively coupled via the first channel to a first neighbor node in a first direction and to a second neighbor node in a second direction;

wherein each node is communicatively coupled via the second channel to the first neighbor node in the first direction and to the second neighbor node in the second direction;

wherein the two nodes of the self checking pair are neighbor nodes of one another;

wherein, when each node relays a first relayed unit of data along the first channel in the first direction, that node relays information indicative of the integrity of the first relayed unit of data along with the first relayed unit of data;

wherein, when each node relays a second relayed unit of data along the second channel in the second direction, that node relays information indicative of the integrity of the second relayed unit of data along with the second relayed unit of data;

wherein, each of the two nodes of the self checking pair, for a particular unit of data communicated on the first channel in the first direction and on the second channel in the second direction;

sends, to the other of the two nodes included in the self checking pair, information about first and second instances of the particular unit of data received by that node from the first and second channels, respectively;

receives, from the other of the two nodes included in the self checking pair, information about first and second instances of the particular unit of data received by that other node from the first and second channels, respectively; and

selects, for use in processing performed by that node for the self checking pair, at least one of the first and second instances of the particular unit of data received by that node based on at least one of;

information about the first and second instances received by that node from the first and second channels, respectively; and

information about the first and second instances received by the other of the two nodes of the self checking pair from the first and second channels, respectively.

2. The network of claim 1, wherein the two nodes of the self checking pair perform replica determinate computation.

3. The network of claim 1, wherein:

each node is communicatively coupled via the first channel to a first neighbor'"'"'s neighbor node in the first direction and to a second neighbor'"'"'s neighbor node in the second direction; and

each node is communicatively coupled via the second channel to the first neighbor'"'"'s neighbor node in the first direction and to the second neighbor'"'"'s neighbor node in the second direction.

4. The network of claim 3,

wherein, when each node relays the first relayed unit of data along the first channel in the first direction, that node relays, to the first neighbor node and the first neighbor'"'"'s neighbor node of that node, the first relayed unit of data and the information indicative of the integrity of the first relayed unit of data;

and

wherein, when each node relays the second relayed unit of data along the second channel in the second direction, that node relays, to the second neighbor node and the second neighbor'"'"'s neighbor node, the second relayed unit of data and the information indicative of the integrity of the second relayed unit of data.

5. The network of claim 3,

wherein the information indicative of the integrity of the first relayed unit of data comprises information indicative of a comparison, performed by the respective node, between data received on the first channel from a respective second neighbor node of that node and data received from a respective second neighbor'"'"'s neighbor node of that node;

and

wherein the information indicative of the integrity of the second relayed unit of data comprises information indicative of a comparison, performed by the respective node, between data received on the second channel from a respective first neighbor node of that node and data received from a respective first neighbor'"'"'s neighbor node of that node.

6. The network of claim 3, wherein the first channel comprises, for each node:

a first direct link that communicatively couples that node to the first neighbor node of that node in the first direction;

a first skip link that communicatively couples that node to the first neighbor'"'"'s neighbor node of that node in the first direction;

a second direct link that communicatively couples that node to the second neighbor node of that node in the second direction; and

a second skip link that communicatively couples that node to the second neighbor'"'"'s neighbor node of that node in the second direction.

7. The network of claim 3, wherein the second channel comprises, for each node:

a first direct link that communicatively couples that node to the first neighbor node of that node in the first direction;

a first skip link that communicatively couples that node to the first neighbor'"'"'s neighbor node of that node in the first direction;

a second direct link that communicatively couples that node to the second neighbor node of that node in the second direction; and

a second skip link that communicatively couples that node to the second neighbor'"'"'s neighbor node of that node in the second direction.

8. The network of claim 1,

wherein the first channel comprises a first direct link that communicatively couples a first of the two nodes of the self checking pair to a second of the two self checking pairs;

wherein the second channel comprises a second direct link that communicatively couples the second of the two nodes of the self checking pair to the first of the two self checking pairs; and

wherein the first of the two nodes of the self checking pair sends the information about the first and second instances received by that node from the first and second channels, respectively, to the second of the two nodes of the self checking pair over the first direct link; and

wherein the second of the two nodes of the self checking pair sends the information about the first and second instances received by that node from the first and second channels, respectively, to the first of the two nodes of the self checking pair over the second direct link.

9. The network of claim 1, wherein each unit of data comprises a frame of data.

10. The network of claim 1, the information about the first and second instances of the particular unit of data received from the first and second channels, respectively, by each of the two nodes of the self checking pair comprises a syndrome generated by the respective node based on the first and second instances of the particular unit of data received from the first and second channels, respectively, by that node.

11. The network of claim 1, wherein each of the two nodes of the self checking pair select the at least one of the first and second instances of the particular unit of data received from the first and second channels, respectively, by the respective node based on at least a source of the particular unit of data.

12. The network of claim 11, wherein, if the source of the particular unit of data is another self-checking pair, each of the two nodes of the self checking pair selects the at least one of the first and second instances of the particular unit of data by:

selecting the first instance of the particular unit of data received by that node from the first channel, if the first instance of the particular unit of data received by that node was received with integrity;

selecting the second instance of the particular unit of data received by that node, if the first instance of the particular unit of data received by that node was not received with integrity and the second instance of the particular unit of data received by that node was received with integrity.

13. The network of claim 12, wherein if the source of the particular unit of data is another self-checking pair, each of the two nodes of the self checking pair selects the at least one of the first and second instances of the particular unit of data received by that node:

by selecting at least one of the first and second instances of the particular unit of data received by that node if;

the first instance of the particular unit of data received by that node was not received with integrity, the second instance of the particular unit of data received by that node was not received with integrity, and the first instance of the particular unit of data received by that node is identical to the second instance of the particular unit of data received by that node; and

by taking a default action if the first instance of the particular unit of data received by that node was not received with integrity, the second instance of the particular unit of data received by that node was not received with integrity, and the first instance of the particular unit of data received by that node is not identical to the second instance of the particular unit of data received by that node.

14. The network of claim 12, wherein the default action comprises at least one of:

selecting a last known-good value for use in the processing performed by the respective node and not performing the processing.

15. The network of claim 11, wherein if the source of the particular unit of data communicated on the first and second channels is a simplex source, each of the two nodes of the self checking pair selects the at least one of the first and second instances of the particular unit of data received by that node:

by selecting the first instance of the particular unit of data received by that node, if both the first instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair were received with integrity; and

by selecting the second instance of the particular unit of data received by that node, if at least one of the first instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair was received with integrity and both the second instance of the particular unit of data received by that node and the second instance of the particular unit of data received by the other of the two nodes of the self checking pair were received with integrity.

16. The network of claim 15, wherein if the source of the particular unit of data communicated on the first and second channels is a simplex source, each of the two nodes of the self checking pair select the at least one of the first and second instances of the particular unit of data received by that node:

by selecting at least one of the first and second instances of the particular unit of data received by that node if;

at least one of the first instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair were not received with integrity;

at least one of the second instance of the particular unit of data received by that node and the second instance of the particular unit of data received by the other of the two nodes of the self checking pair were not received with integrity; and

both the first instance of the particular unit of data received by that node is identical to the second instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair is identical to the second instance of the particular unit of data received by the other of the two nodes of the self checking pair.

17. The network of claim 16, wherein if the source of the particular unit of data communicated on the network is a simplex source, each of the two nodes of the self checking pair select the at least one of the first and second instances of the particular unit of data received by that node:

by taking a default action if;

at least one of the first instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair were not received with integrity;

at least one of the second instance of the particular unit of data received by that node and the second instance of the particular unit of data received by the other of the two nodes of the self checking pair were not received with integrity; and

either the first instance of the particular unit of data received by that node is not identical to the second instance of the particular unit of data received by that node or the first instance of the particular unit of data received by the other of the two nodes of the self checking pair is not identical to the second instance of the particular unit of data received by the other of the two nodes of the self checking pair.

18. A network comprising:

a plurality of nodes that are communicatively coupled to one another over first and second channels; and

at least one self checking pair comprising at least two of the plurality of nodes;

wherein each node is communicatively coupled via the first channel to;

at least one first transmit-to node to which that node transmits data on the first channel; and

at least one first receive-from node from which that node receives data from the first channel;

wherein each node is communicatively coupled via the second channel to;

at least one second transmit-to node to which that node transmits data on the second channel; and

at least one second receive-from node from which that node receives data from the second channel;

wherein a first of the two nodes of the self checking pair comprises the respective first receive-from node and the respective second transmit-to node for a second of the two nodes of the self checking pair;

wherein the second of the two nodes of the self checking pair comprises the respective second receive-from node and the respective first transmit-to node for the first of the two nodes of the self checking pair; and

wherein, when each node relays a first relayed unit of data along the first channel, that node relays information indicative of the integrity of the first relayed unit of data along with the first relayed unit of data;

wherein, when each node relays a second relayed unit of data along the second channel, that node relays information indicative of the integrity of the second relayed unit of data along with the second relayed unit of data;

wherein, each of the two nodes of the self checking pair, for a particular unit of data communicated on the first channel and on the second channel;

sends, to the other of the two nodes included in the self checking pair, information about first and second instances of the particular unit of data received by that node from the first and second channels, respectively;

receives, from the other of the two nodes included in the self checking pair, information about first and second instances of the particular unit of data received by that other node from the first and second channels, respectively; and

selects, for use in processing performed by that node for the self checking pair, at least one of the first and second instances of the particular unit of data received by that node based on at least one of;

information about the first and second instances received by that node from the first and second channels, respectively; and

information about the first and second instances received by the other of the two nodes of the self checking pair from the first and second channels, respectively.

19. The network of claim 18, wherein the first channel forms at least one of a ring and a mesh.

20. The network of claim 18, wherein the second channel forms at least one of a ring and a mesh.

21. A method for use in a network comprising a plurality of nodes that are communicatively coupled to one another over first and second channels that form first and second rings, respectively, wherein each node is communicatively coupled via the first channel to a first neighbor node in a first direction and to a second neighbor node in a second direction and wherein each node is communicatively coupled via the second channel to the first neighbor node in the first direction and to the second neighbor node in the second direction, wherein the network comprises at least one self-checking pair that includes two nodes that are neighbor nodes of one another, the method comprising:

relaying, by each of the plurality of nodes, along the first channel, a first unit of data received by the respective node on the first channel along with information indicative of the integrity of the first relayed unit of data;

relaying, by each of the plurality of nodes, along the second channel, a second unit of data received by the respective node on the second channel along with information indicative of the integrity of the second relayed unit of data;

wherein for a particular unit of data communicated on the first and second channels, at each of the two nodes of the self checking pair;

sending, to the other of the two nodes included in the self checking pair, information about first and second instances of the particular unit of data received by that node from the first and second channels, respectively;

receiving, from the other of the two nodes included in the self checking pair, information about first and second instances of the particular unit of data received by that other node from the first and second channels, respectively; and

selecting, for use in processing performed by that node for the self checking pair, at least one of the first and second instances of the particular unit of data received by that node based on at least one of;

information about the first and second instances received by that node from the first and second channels, respectively; and

information about the first and second instances received by the other of the two nodes of the self checking pair from the first and second channels, respectively.

22. The method of claim 21, wherein the two nodes of the self checking pair perform replica determinate computation.

23. The method of claim 21, wherein:

each node is communicatively coupled via the first channel to a first neighbor'"'"'s neighbor node in the first direction and to a second neighbor'"'"'s neighbor node in the second direction; and

each node is communicatively coupled via the second channel to the first neighbor'"'"'s neighbor node in the first direction and to the second neighbor'"'"'s neighbor node in the second direction.

24. The method of claim 23,

wherein, when each node relays the first relayed unit of data along the first channel in the first direction, that node relays, to the first neighbor node and the first neighbor'"'"'s neighbor node of that node, the first relayed unit of data and the information indicative of the integrity of the first relayed unit of data;

and

wherein, when each node relays the second relayed unit of data along the second channel in the second direction, that node relays, to the second neighbor node and the second neighbor'"'"'s neighbor node, the second relayed unit of data and the information indicative of the integrity of the second relayed unit of data.

25. The method of claim 23, further comprising:

comparing, by the respective node, between data received on the first channel from a respective second neighbor node of that node and data received from a respective second neighbor'"'"'s neighbor node of that node, wherein the information indicative of the integrity of the first relayed unit of data comprises information indicative of the comparison between the data received on the first channel from the respective second neighbor node of that node and the data received from the respective second neighbor'"'"'s neighbor node of that node; and

comparing, by the respective node, between data received on the second channel from a respective first neighbor node of that node and data received from a respective first neighbor'"'"'s neighbor node of that node, wherein the information indicative of the integrity of the second relayed unit of data comprises information indicative of the comparison between the data received on the second channel from the respective first neighbor node of that node and the data received from the respective first neighbor'"'"'s neighbor node of that node.

26. The method of claim 21,

wherein the first channel comprises a first direct link that communicatively couples a first of the two nodes of the self checking pair to a second of the two self checking pairs;

wherein the second channel comprises a second direct link that communicatively couples the second of the two nodes of the self checking pair to the first of the two self checking pairs; and

wherein the first of the two nodes of the self checking pair sends the information about the first and second instances received by that node from the first and second channels, respectively, to the second of the two nodes of the self checking pair over the first direct link; and

wherein the second of the two nodes of the self checking pair sends the information about the first and second instances received by that node from the first and second channels, respectively, to the first of the two nodes of the self checking pair over the second direct link.

27. The method of claim 21, wherein each unit of data comprises a frame of data.

28. The method of claim 21, the information about the first and second instances of the particular unit of data received from the first and second channels, respectively, by each of the two nodes of the self checking pair comprises a syndrome generated by the respective node based on the first and second instances of the particular unit of data received from the first and second channels, respectively, by that node.

29. The method of claim 21, wherein each of the two nodes of the self checking pair select the at least one of the first and second instances of the particular unit of data received from the first and second channels, respectively, by the respective node based on at least a source of the particular unit of data.

30. The method of claim 29, wherein, if the source of the particular unit of data is another self-checking pair, each of the two nodes of the self checking pair selects the at least one of the first and second instances of the particular unit of data by:

selecting the first instance of the particular unit of data received by that node from the first channel, if the first instance of the particular unit of data received by that node was received with integrity;

selecting the second instance of the particular unit of data received by that node, if the first instance of the particular unit of data received by that node was not received with integrity and the second instance of the particular unit of data received by that node was received with integrity.

31. The method of claim 30, wherein if the source of the particular unit of data is another self-checking pair, each of the two nodes of the self checking pair selects the at least one of the first and second instances of the particular unit of data received by that node by:

selecting at least one of the first and second instances of the particular unit of data received by that node if;

the first instance of the particular unit of data received by that node was not received with integrity, the second instance of the particular unit of data received by that node was not received with integrity, and the first instance of the particular unit of data received by that node is identical to the second instance of the particular unit of data received by that node; and

taking a default action if the first instance of the particular unit of data received by that node was not received with integrity, the second instance of the particular unit of data received by that node was not received with integrity, and the first instance of the particular unit of data received by that node is not identical to the second instance of the particular unit of data received by that node.

32. The method of claim 30, wherein the default action comprises at least one of:

selecting a last known-good value for use in the processing performed by the respective node and not performing the processing.

33. The method of claim 29, wherein if the source of the particular unit of data communicated on the first and second channels is a simplex source, each of the two nodes of the self checking pair selects the at least one of the first and second instances of the particular unit of data received by that node by:

selecting the first instance of the particular unit of data received by that node, if both the first instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair were received with integrity; and

selecting the second instance of the particular unit of data received by that node, if at least one of the first instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair was received with integrity and both the second instance of the particular unit of data received by that node and the second instance of the particular unit of data received by the other of the two nodes of the self checking pair were received with integrity.

34. The method of claim 33, wherein if the source of the particular unit of data communicated on the first and second channels is a simplex source, each of the two nodes of the self checking pair select the at least one of the first and second instances of the particular unit of data received by that node by:

selecting at least one of the first and second instances of the particular unit of data received by that node if;

at least one of the first instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair were not received with integrity;

at least one of the second instance of the particular unit of data received by that node and the second instance of the particular unit of data received by the other of the two nodes of the self checking pair were not received with integrity; and

both the first instance of the particular unit of data received by that node is identical to the second instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair is identical to the second instance of the particular unit of data received by the other of the two nodes of the self checking pair.

35. The method of claim 34, wherein if the source of the particular unit of data communicated on the network is a simplex source, each of the two nodes of the self checking pair select the at least one of the first and second instances of the particular unit of data received by that node:

by taking a default action if;

at least one of the first instance of the particular unit of data received by that node and the first instance of the particular unit of data received by the other of the two nodes of the self checking pair were not received with integrity;

at least one of the second instance of the particular unit of data received by that node and the second instance of the particular unit of data received by the other of the two nodes of the self checking pair were not received with integrity; and

either the first instance of the particular unit of data received by that node is not identical to the second instance of the particular unit of data received by that node or the first instance of the particular unit of data received by the other of the two nodes of the self checking pair is not identical to the second instance of the particular unit of data received by the other of the two nodes of the self checking pair.

36. A self checking pair comprising:

first and second nodes, wherein each of the first and second nodes comprises an interface to communicatively couple the respective node to at least first and second channels, wherein the first and the second channels comprise first and second rings respectively;

wherein the first and second nodes are neighbor nodes of one another;

wherein, for each unit of data relayed on the first and second channels, information indicative of the integrity of the relayed unit of data is relayed along with the relayed unit of data; and

wherein for a particular unit of data communicated on the network;

each of the first and second nodes exchange information about a first instance of the particular unit of data received from the first channel and about a second instance of the particular unit of data received from the second channel; and

each of the first and second nodes of the self checking pair selects, for use in processing performed by the respective node, at least one of the first and second instances of the particular unit of data received by the respective node based on at least one of;

information about the first and second instances received by that node from the first and second channels, respectively; and

information about the first and second instances received by the other of the two nodes of the self checking pair from the first and second channels, respectively.

37. Apparatus comprising:

a self checking pair comprising first and second nodes, wherein each of the first and second nodes comprises means for communicatively coupling the respective node to at least first and second channels, wherein the first and the second channels comprise first and second rings respectively;

wherein the first and second nodes are neighbor nodes of one another;

wherein, for each unit of data relayed on the first and second channels, information indicative of the integrity of the relayed unit of data is relayed along with the relayed unit of data; and

wherein each of the first and second nodes further comprises means for processing a particular unit of data communicated on the first and second channels, that comprises

means for sending, to the other of the two nodes included in the self checking pair, information about first and second instances of the particular unit of data received by that node from the first and second channels, respectively;

means for receiving, from the other of the two nodes included in the self checking pair, information about first and second instances of the particular unit of data received by that other node from the first and second channels, respectively; and

means for selecting, for use in processing performed by that node for the self checking pair, at least one of the first and second instances of the particular unit of data received by that node based on at least one of;

information about the first and second instances received by that node from the first and second channels, respectively; and

information about the first and second instances received by the other of the two nodes of the self checking pair from the first and second channels, respectively.