Clique aggregation in TDMA networks

• US 7,505,470 B2
• Filed: 11/19/2004
• Issued: 03/17/2009
• 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
• Primary Examiner(s): Chan; Wing F
• Assistant Examiner(s): Tsegaye; Saba
• Application Number:
  US10/994,209
• Publication Number:
  US 20050152377A1
• Time in Patent Office: 1,579 Days
• Field of Search: 370/216, 370221-228, 370/254, 370/255, 370/258, 370/389, 370/390, 370/400, 370/419, 370/237, 370/238, 370/328, 370/329, 709/239
• US Class Current: 370/400
• CPC Class Codes: H04L 12/43 with synchronous transmission, e.g. time division multiplex [TDM], slotted rings
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085

Abstract

In one embodiment, a method resolves cliques formed in a network comprising a plurality of nodes that are communicatively coupled to one another over at least a first channel. The method comprises, at each node, wherein that node is a member of a current clique: listening asynchronously for data on the first channel from a first neighbor'"'"'s neighbor node of that node. The method further comprises, at that node, when a first valid frame is received on the first channel from the first neighbor'"'"'s neighbor node of that node, listening asynchronously for a second valid frame on the first channel from a first neighbor node of that node. The method further comprises, at that node, when the second valid frame is received on the first channel, checking if the first valid frame and the second valid frame are both from the same other clique, and, if the first valid frame and the second valid frame are both from the same the same other clique, determining if that node should defect from the current clique towards the other clique.

Claims

1. A method of resolving cliques formed in a network comprising a plurality of nodes that are communicatively coupled to one another over at least a first channel, the method comprising:

at each node, wherein that node is a member of a current clique;

listening asynchronously for data on the first channel from a first neighbor'"'"'s neighbor node of that node;

when a first valid frame is received on the first channel from the first neighbor'"'"'s neighbor node of that node, listening asynchronously for a second valid frame on the first channel from a first neighbor node of that node;

when the second valid frame is received on the first channel, checking if the first valid frame and the second valid frame are both from the same other clique; and

if the first valid frame and the second valid frame are both from the same other clique, determining if that node should defect from the current clique towards the other clique and defecting from the current clique towards the other clique if that node determines that the node should defect from the current clique towards the other clique before the period.

2. A method of resolving cliques formed in a network comprising a plurality of nodes that are communicatively coupled to one another over at least a first channel, the method comprising:

at each node, wherein that node is a member of a current clique;

synchronously listening for data on the first channel from a first neighbor node of that node;

if, after listening synchronously for data on the first channel from the first neighbor node of that node for a period of time, a valid frame has not been received from the first neighbor node of that node;

listening asynchronously for data on the first channel from a first neighbor'"'"'s neighbor node of that node;

when a first valid frame is received on the first channel from the first neighbor'"'"'s neighbor node of that node, listening asynchronously for a second valid frame on the first channel from the first neighbor node of that node;

when the second valid frame is received on the first channel, checking if the first valid frame and the second valid frame are both from the same other clique;

if the first valid frame and the second valid frame are both from the same other clique, determining if that node should defect from the current clique towards the other clique and defecting from the current clique towards the other clique if that node determines that the node should defect from the current clique towards the other clique.

3. The method of claim 2, wherein if the first valid frame and the second valid frame are both from the same other clique, that node defects from the current clique towards the other clique if the other clique includes more member nodes than the current clique.

4. The method of claim 2, wherein the period of time comprises one TDMA round.

5. The method of claim 2, wherein the plurality of nodes are assigned an order, wherein determining if that node should defect from the current clique towards the other clique comprises identifying which member node of a given clique comes first in the assigned order.

6. The method of claim 2, wherein the channel comprises a ring.

7. The method of claim 2, wherein the first channel comprises, for each node:

a first direct link that communicatively couples that node to the first neighbor node for that node via the first channel;

a first skip link the communicatively couples that node to the first neighbor'"'"'s neighbor node for that node via the first channel;

a second direct link that communicatively couples that node to a second neighbor node for that node via the first channel; and

a second skip link the communicatively couples that node to the second neighbor'"'"'s neighbor node for that node via the first channel.

8. The method of claim 2, further comprising determining if a given frame received asynchronously on the first channel from the first neighbor'"'"'s neighbor node of that node comprises one of the first valid frame and the second valid frame.

9. The method of claim 2, wherein the first valid frame comprises a frame that is syntactically correct and that is in agreement with a schedule position of that node.

10. The method of claim 2, wherein the second valid frame comprises a frame that is syntactically correct and that is in agreement with a schedule position of that node.

11. The method of claim 10, wherein the validity of a schedule alignment of a given frame is validated using explicit schedule data contained within the given frame.

12. The method of claim 10, wherein the validity of a schedule alignment of a given frame is validated using implicit schedule data contained within the given frame.

13. The method of claim 2, wherein checking if the first valid frame and the second valid frame are both from the same other clique comprises checking if first valid frame and the second valid frame were both transmitted from respective nodes that are both members of the same other clique.

14. The method of claim 2, wherein checking if the first valid frame and the second valid frame are both from the same other clique comprises checking if the time observed between reception of the two valid frames is in agreement with an expected time between reception of the two valid frames.

15. A node comprising:

an interface to communicatively couple the node to a channel;

wherein the channel communicatively couples the node to a plurality of other nodes, wherein the plurality of nodes comprises a first neighbor node and a first neighbor'"'"'s neighbor node to which the channel communicatively couples the node in a first direction; and

wherein the node is a member of a current clique;

the node listens asynchronously for data on the first channel from the first neighbor'"'"'s neighbor node;

when a first valid frame is received on the first channel from the first neighbor'"'"'s neighbor node, the node listens asynchronously for a second valid frame on the first channel from the first neighbor node;

when the second valid frame is received on the first channel, the node checks if the first valid frame and the second valid frame are from the same other clique; and

if the first valid frame and the second valid frame are both from the same other clique, the node determines if the node should defect from the current clique towards the other clique and the node defects from the current clique towards the other clique if the node determines that the node should defect from the current clique towards the other clique.

16. The node of claim 15, wherein:

before listening asynchronously, the node listens synchronously for data on the first channel from the first neighbor node; and

if, after listening synchronously for data on the first channel from the first neighbor node of that node for a period of time, the node has not received a valid frame from the first neighbor node, the node listens asynchronously for the data on the first channel from the first neighbor'"'"'s neighbor node.

17. A node comprising:

an interface to communicatively couple the node to a channel;

wherein the channel communicatively couples the node to a plurality of other nodes, wherein the plurality of nodes comprises a first neighbor node and a first neighbor'"'"'s neighbor node to which the channel communicatively couples the node in a first direction; and

wherein the node is a member of a current clique;

wherein the node listens synchronously for data on the first channel from a first neighbor node of that node; and

if, after listening synchronously for data on the first channel from the first neighbor node of that node for a period of time, the node has not received a valid frame from the first neighbor node;

the node listens asynchronously for data on the first channel from the first neighbor'"'"'s neighbor node;

when a first valid frame is received on the first channel from the first neighbor'"'"'s neighbor node, the node listens asynchronously for a second valid frame on the first channel from the first neighbor node;

when the second valid frame is received on the first channel, the node checks if the first valid frame and the second valid frame are both from the same other clique; and

if the first valid frame and the second valid frame are both from the same other clique, the node determines if the node should defect from the current clique towards the other clique and the node defects from the current clique towards the other clique if the node determines that the node should defect from the current clique towards the other clique.

18. The node of claim 17, wherein if the first valid frame and the second valid frame were transmitted by nodes that are both members of the same other clique, the node defects from the current clique towards the other clique if the other clique includes more member nodes than the current clique.

19. The node of claim 17, wherein the plurality of nodes are assigned an order, wherein the node determines if the node should defect from the current clique towards the other clique by identifying which member node of a given clique comes first in the assigned order.

20. A network comprising:

a plurality of nodes that are communicatively coupled to one another over a first channel;

wherein the channel communicatively couples each node to a first neighbor node and a first neighbor'"'"'s neighbor node in a first direction; and

wherein each node is a member of a current clique;

wherein each node;

listens asynchronously for data on the first channel from the first neighbor'"'"'s neighbor node of that node;

when a first valid frame is received on the first channel from the first neighbor'"'"'s neighbor node of that node, the node listens asynchronously for a second valid frame on the first channel from the first neighbor node of that node;

when the second valid frame is received on the first channel, that node checks if the first valid frame and the second valid frame are both from the same other clique; and

if the first valid frame and the second valid frame are both from the same other clique, that node determines if that node should defect from the current clique for that node towards the other clique and the node defects from the current clique towards the other clique if the node determines that the node should defect from the current clique towards the other clique.

21. A network comprising:

a plurality of nodes that are communicatively coupled to one another over a first channel;

wherein the channel communicatively couples each node to a first neighbor node and a first neighbor'"'"'s neighbor node in a first direction; and

wherein each node is a member of a current clique;

wherein each node listens synchronously for data on the first channel from a first neighbor node of that node; and

if, after listening synchronously for data on the first channel from the first neighbor node of that node for a period of time, that node has not received a valid frame from the first neighbor node of that node;

the node listens asynchronously for data on the first channel from the first neighbor'"'"'s neighbor node of that node;

when a first valid frame is received on the first channel from the first neighbor'"'"'s neighbor node of that node, the node listens asynchronously for a second valid frame on the first channel from the first neighbor node of that node;

when the second valid frame is received on the first channel, that node checks if the first valid frame and the second valid frame are both from the same other clique; and

if the first valid frame and the second valid frame are both from the same other clique, that node determines if that node should defect from the current clique for that node towards the other clique and that node defects from the current clique towards the other clique if that node determines that the node should defect from the current clique towards the other clique.

22. The network of claim 21, wherein if the first valid frame and the second valid frame are both from the same other clique, that node defects from the current clique towards the other clique if the other clique includes more member nodes than the current clique.

23. The network of claim 21, wherein the plurality of nodes are assigned an order, wherein each node determines if that node should defect from the current clique towards the other clique by identifying which member node of a given clique comes first in the assigned order.

24. The network of claim 21, wherein the channel comprises a ring.

25. The network of claim 21, wherein the first channel comprises, for each node:

a first direct link that communicatively couples that node to the first neighbor node for that node via the first channel;

a first skip link the communicatively couples that node to the first neighbor'"'"'s neighbor node for that node via the first channel;

a second direct link that communicatively couples that node to a second neighbor node for that node via the first channel; and

a second skip link the communicatively couples that node to a second neighbor'"'"'s neighbor node for that node via the first channel.