Method and apparatus for synchronizing a data communications network

• US 20050117593A1
• Filed: 12/01/2003
• Published: 06/02/2005
• Est. Priority Date: 12/01/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shand, Ian Michael Charles
• Granted Patent: US 7,366,099 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

A method is disclosed for synchronizing a data communications network. The data communications network comprises a plurality of existing nodes forming one or more synchronization domains and a node entering the network. Each existing node in a synchronization domain stores a common representation of the synchronization domain and is configured to flood the synchronization domain with domain representation information. In a synchronization domain identification step formed at the entering node, the entering node exchanges entering node domain representation information with a first neighboring existing node. The entering node identifies as a first synchronization domain common with the first neighboring existing node all neighboring existing nodes from which the entering node domain representation information is flooded back the entering node.

Claims

1. A method of synchronizing a data communications network comprising a plurality of existing nodes forming one or more synchronization domains and a node entering the network, in which each existing node in a synchronization domain stores a common representation of the synchronization domain and is configured to flood the synchronization domain with domain representation information, in which, in a synchronization domain identification step performed at the entering node, the entering node exchanges entering node domain representation information with a first neighboring existing node, and identifies as a first synchronization domain common with the first neighboring existing node all neighboring existing nodes from which the entering node domain representation information is flooded back to the entering node.

2. A method as claimed in claim 1 further comprising the step, performed at the entering node, of exchanging entering node domain node representation information with a second neighboring existing node not identified as being in the first synchronization domain, if any.

3. A method as claimed in claim 2 in which the entering node exchanges entering node domain representation information with the second neighboring existing node after a timeout period following the exchange of entering node domain representation information with the first neighboring existing node.

4. A method as claimed in claim 2 in which the entering node exchanges entering node domain representation with all nodes not identified as being in the first synchronization domain simultaneously.

5. A method as claimed in claim 1 in which the entering node repeats the synchronization domain identification step successively until all synchronization domains are identified.

6. A method as claimed in claim 1 in which the synchronization domain identification exchange step comprises a synchronization step.

7. A method as claimed in claim 1 further comprising the step, performed at the entering node of selecting as the first neighboring existing node the node having the largest store of domain representation information.

8. A method as claimed in claim 7 further comprising the step, performed at the entering node, of requesting domain representation information store size in an initiation exchange with neighboring existing nodes.

9. A method as claimed in claim 1 further comprising the step, performed at the entering node, of suppressing synchronization with neighboring existing nodes prior to the synchronization domain identification step.

10. A method as claimed in claim 1 comprising the step, performed at the entering node, of sending separately identifiable entering node domain representation information to each neighboring existing node and identifying as respective synchronization domains each set of neighboring existing nodes from which commonly identified entering node domain representation information is returned.

11. A method as claimed in claim 10 in which the separately identifiable entering node domain representation information comprises a separately identifiable fragment of the entering node domain representation information.

12. A method as claimed in claim 10 further comprising the step, performed at the entering node, of synchronizing the entering node with a neighboring existing node in each synchronization domain.

13. A method as claimed in claim 1 in which the data communications network comprises a mobile network.

14. A method as claimed in claim 1 in which, where a new link appears between the entering node and the network, the entering node sends entering node domain representation information via an existing link with a neighboring node and monitors for flooding back of the entering node domain representation information via the new link.

16. A computer readable medium comprising one or more sequences of instructions for synchronizing a data communications network which instructions, when executed by one or more processors, cause the one or more processors to perform the steps of the method of any of claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 or 15.

32. An apparatus for synchronizing a data communications network, the apparatus comprising:

one or more processors;

a network interface communicatively coupled to the processor and configured to communicate one or more packet flows among the processor and network; and

a computer readable medium comprising one or more sequences of instructions for synchronizing a data communications network which instructions, when executed by one or more processors, cause the one or more processors to perform the steps of the method of any of claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 or 15.

15. A method of identifying synchronization domain candidate nodes in a data communications network in which each node in the network stores synchronization domain representation information comprising the steps of comparing the sizes of the synchronization domain representation information stores and selecting a node having the largest store as a synchronization domain candidate.

17. An apparatus for synchronizing a data communications network comprising a plurality of existing nodes forming one or more synchronization domains and a node entering the network, in which each existing node in a synchronization domain stores a common representation of the synchronization domain and is configured to flood the synchronization domain with domain representation information, comprising means, in a synchronization domain identification step, for exchanging entering node domain representation information with a first neighboring existing node, and means for identifying as a first synchronization domain common with the first neighboring existing node all neighboring existing nodes from which the entering node domain representation information is flooded back to the entering node.

18. An apparatus as claimed in claim 17 further comprising means for exchanging entering node domain node representation information with a second neighboring existing node not identified as being in the first synchronization domain, if any.

19. An apparatus as claimed in claim 18 in which the means for exchanging entering node domain representation information is arranged to exchange said information with the second neighboring existing node after a timeout period following the exchange of entering node domain representation information with the first neighboring existing node.

20. An apparatus as claimed in claim 18 in which the means for exchanging entering node domain representation exchanges said information with all nodes not identified as being in the first synchronization domain simultaneously.

21. An apparatus as claimed in claim 17 in which the means for exchanging entering node domain information repeats the synchronization domain identification step successively until all synchronization domains are identified.

22. An apparatus as claimed in claim 17 in which the synchronization domain identification exchange step comprises a synchronization step.

23. An apparatus as claimed in claim 17 further comprising means for selecting as the first neighboring existing node the node having the largest store of domain representation information.

24. An apparatus as claimed in claim 23 further comprising means for requesting domain representation information store size in an initiation exchange with neighboring existing nodes.

25. An apparatus as claimed in claim 17 further comprising means for suppressing synchronization with neighboring existing nodes prior to the synchronization domain identification step.

26. An apparatus as claimed in claim 17 comprising means for sending separately identifiable entering node domain representation information to each neighboring existing node and means for identifying as respective synchronization domains each set of neighboring existing nodes from which commonly identified entering node domain representation information is returned.

27. An apparatus as claimed in claim 26 in which the separately identifiable entering node domain representation information comprises a separately identifiable fragment of the entering node domain representation information.

28. An apparatus as claimed in claim 26 further comprising means for synchronizing the entering node with a neighboring existing node in each synchronization domain.

29. An apparatus as claimed in claim 17 in which the data communications network comprises a mobile network.

30. An apparatus as claimed in claim 17 in which where a new link appears between the entering node and the network, the means for exchanging entering node domain representation information sends entering node domain representation information via an existing link with a neighboring existing node and monitors for flooding back of the entering node domain representation information via the new link.

31. An apparatus for identifying synchronization domain candidate nodes in a data communications network in which each node in the network stores synchronization domain representation information comprising means for comparing the sizes of the synchronization domain representation information stores and means for selecting a node having the largest store as a synchronization domain candidate.

33. A method of synchronizing a data communications network comprising a plurality of existing nodes forming one or more synchronization domains and a node entering the network, wherein each existing node in a synchronization domain stores a common representation of the synchronization domain and is configured to flood the synchronization domain with domain representation information, the method comprising the steps of:

exchanging entering node domain representation information with a first neighboring existing node as part of a synchronization domain identification process;

identifying, as a first synchronization domain common with the first neighboring existing node, all neighboring existing nodes; and

receiving node domain representation information in flooded communications from all said neighboring existing nodes.