Network clock synchronization scheme

• US 6,714,563 B1
• Filed: 04/26/1999
• Issued: 03/30/2004
• Est. Priority Date: 04/26/1999
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kushi, David M.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Ferris, Derrick W
• Application Number:
  US09/299,829
• Time in Patent Office: 1,800 Days
• Field of Search: 370/351, 370/395.62, 370/503, 370/509, 370/510, 370/511, 370/254, 370/256, 713/400, 713/401
• US Class Current: 370/503
• CPC Class Codes: H04J 3/0679 by determining clock distribution path in a network

Abstract

A clock distribution tree for a digital network is automatically established through the use of spanning tree computations at nodes of the network. The computations rely, at least in part, upon the exchange of clock distribution messages between the nodes of the network. Each clock distribution message includes information regarding a clock source available at the source node of the message. The clock distribution tree is hierarchical in nature, with nodes that are lower in the hierarchy (i.e., at a higher stratum level) extracting clock from links with nodes that are higher in the hierarchy (i.e., at a lower stratum level); this helps preserve the synchronous digital hierarchy of the network. The spanning tree computations involve a root selection process and a convergence test. The root selection process is made on the basis of configuration vectors exchanged as part of the clock distribution messages. The configuration vectors include a port priority, a node stratum level and a primary reference source identifier. The convergence test includes determining whether a number of clock distribution messages received or transmitted equals a network maximum diameter parameter for the network.

Claims

1. A method comprising establishing a clock distribution tree within a synchronous digital network through the use of spanning tree computations at n odes of the network, the computations relying, at least in part, upon the exchange of clock distribution messages between the nodes of the network, each clock distribution message including information regarding a clock source available at the source node of the message, said information indicating a priority level assigned to said clock source and a stratum level for said clock source.

2. The method of claim 1 wherein the clock distribution tree is hierarchical in nature, with nodes that are lower in the hierarchy extracting clock from links with nodes that are higher in the hierarchy.

3. The method of claim 2 wherein the spanning tree computations involve a root selection process and a convergence test.

4. The method of claim 3 wherein the root selection process is made on the basis of configuration vectors that are embedded within the clock distribution messages.

5. The method of claim 4 wherein the configuration vectors comprise a node stratum level and a primary reference source identifier.

6. The method of claim 5 wherein the convergence test comprises determining whether a number of clock distribution messages received or transmitted equals a network maximum diameter parameter for the network.

7. A method comprising automatically selecting at a node of a synchronous digital network a clocking source for the node according to a comparison of clock source configuration vectors, each vector associated with a port in the network and each vector identifying the associated port'"'"'s priority, a stratum level of a clock source available at that port and an indication of a primary reference clock source for that port, at least one of the vectors having been:

a) sent to the node by another node of the synchronous digital network; and

, b) having been received by the node.

8. The method of claim 7 wherein other clock source configuration vectors are exchanged between other nodes of the network as part of an exchange of configuration messages.

9. The method of claim 8 wherein at least one of the configuration vectors is associated with a virtual node of the network.

10. The method of claim 8 wherein each node of the network is configured to extract clock information only from links to adjacent nodes at an equal or lower stratum level.

11. A set of computer-readable instructions, which when executed by a processor of a network node cause the processor to help establish a clock distribution tree for a synchronous digital network to which the node belongs by executing spanning tree computations that rely, at least in part, upon the exchange of clock distribution messages between the node and other nodes of the synchronous digital network, each clock distribution message including information regarding a clock source available at the source node of the message, said information indicating a priority level assigned to said clock source and a stratum level for said clock source.

12. The set of computer-readable instructions of claim 11 further comprising instructions that when executed by the processor cause the processor to ensure that the node extracts a clock only from links with nodes that are higher in a hierarchy of the network.

13. The set of computer readable instruction of claim 12 wherein the spanning tree computations involve a root selection process and a convergence test.

14. The set of computer-readable instructions of claim 13 wherein the root selection process is made on the basis of configuration vectors that are embedded within the clock distribution messages.

15. The set of computer-readable instructions of claim 14 wherein the configuration vectors comprise a node stratum level and a primary reference source identifier.

16. The set of computer-readable instructions of claim 15 wherein the convergence test comprises determining whether a number of clock distribution messages received or transmitted equals a network maximum diameter parameter for the network.

17. A synchronous network node comprising a processor and readable media having executable instructions to automatically select a clocking source for the node according to a comparison of clock source configuration vectors, each vector associated with a port in a network and each vector identifying the associated port'"'"'s priority, a stratum level of a clock source available at that port and an indication of a primary reference clock source for that port, at least one of the vectors having been:

a) sent to the node by another node of the synchronous digital network, and, b) having been received by the node.

18. The network node of claim 17 wherein the other clock source configuration vectors are exchanged between other nodes of the network as part of an exchange of configuration messages.

19. The network node of claim 18 wherein at least one of the configuration vectors is associated with a virtual node of the network.

20. The network node of claim 18 being further configured to extract clock information only from links to adjacent nodes at an equal or lower stratum level.

21. A method to recognize a root clock source for a synchronous network, said method comprising:

a) receiving, at a second node that is part of said synchronous network, a message that was sent from a first node, said first node also part of said synchronous network, said message comprising;

(i) an indication of a first priority level assigned to a first clocking signal, said first clocking signal recognized by said first node as said root clock source when said message was sent by said first node, said first clocking signal found at a first port within said network and

(ii) an indication of a stratum level for said first clocking signal; and

,

b) comparing, by said second node, said first priority level against a second priority level, said second priority level assigned to a second clocking signal, said second signal recognized by said second node as said root clock source.

22. The method of claim 21 further comprising identifying, at said second node, said first clocking signal as said root clock source because said first priority level is higher in priority than said second priority level.

23. The method of claim 22 wherein said first priority level being higher in priority than said second priority level causes said second node to transition from a converged state to an unconverged state.

24. The method of claim 23 further comprising recognizing at said second node that a selection process for determining said root clock source has converged.

25. The method of claim 24 wherein said recognizing further comprises recognizing at said second node that a specific number of messages have been received that each indicate the same root clock source.

26. The method of claim 21 further comprising keeping said recognition, at said second node, that said second clocking signal is said root clock source because said first priority level is lower in priority than said second priority level.

27. The method of claim 21 wherein said first priority level is the same as said second priority level and wherein said method further comprises comparing, by said second node, said indication of said stratum level for said first clocking signal against an indication of a stratum level for said second clocking signal.

28. The method of claim 27 further comprising identifying, at said second node, said first clocking signal as said root clock source because said stratum level for said first clocking signal is lower than said stratum level for said second clocking signal.

29. The method of claim 28 further comprising recognizing at said second node that a s election process for determining said root clock source has converged.

30. The method of claim 29 wherein said recognizing further comprises recognizing at said second node that a specific number of messages have been received that each indicate the same root clock source.

31. The method of claim 27 further comprising keeping said recognition, at said second node, that said second clocking signal is said root clock source because said stratum level for said first clocking signal is higher than said stratum level for said second clocking signal.

32. The method of claim 27 wherein said stratum level for said first clocking signal is the same as said stratum level for said second clocking signal, and wherein said message further comprises an indication as to whether said first clocking signal is internally or externally generated relative to said network.

33. The method of claim 32 further comprising identifying, at said second node, said first clocking signal as said root clock source because said first clocking signal is externally generated relative to said network and said second clocking signal is internally generated relative to said network.

34. The method of claim 33 further comprising recognizing at said second node that a selection process for determining said root clock source has converged.

35. The method of claim 34 wherein said recognizing further comprises recognizing at said second node that a specific number of messages have been received that each indicate the same root clock source.

36. The method of claim 32 further comprising keeping said recognition, at said second node, that said second clocking signal is said root clock source because said second clocking signal is externally generated relative to said network and said first clocking signal is internally generated relative to said network.

37. The method of claim 21 wherein said second node is within an unconverged state.

38. The method of claim 21 wherein said message further comprises information that informs said second node of the best clock available to and usable by said first node.

39. The method of claim 38 further comprising selecting a root port for said second node, said root port being a port where a link resides having a clocking signal that is extracted by said second node.

40. The method of claim of claim 39 further comprising configuring said second node'"'"'s clocking hardware to extract a clock at said root port.

41. The method of claim 39 wherein said selecting a root port further comprises:

receiving messages from adjacent nodes, each message indicating the stratum level of its respective adjacent node; and

, refusing to use, as said root port, a port of said second node where a link resides that communicates to those of said adjacent ports having a higher stratum level than said second node.

42. A set of computer-readable instructions which, when executed by a processor of a second node that is part of a synchronous network, cause said processor to perform a method that identifies a root clock source for said synchronous network, said method comprising comparing a first priority level against a second priority level, said first priority level assigned to a first clocking signal, said first clocking signal found at a first port within said network, said first node having sent a message to said second node that included an indication o f said first priority level and an indication of a stratum level for said first clocking signal, said first node having recognized said first clocking signal as said root clock source when said message was sent, said second priority level assigned to a second clocking signal, said second clocking signal recognized by said second node as said root clock source.

43. The set of computer-readable instructions of claim 42 wherein said method further comprises identifying said first clocking signal as said root clock source because said first priority level is higher in priority than said second priority level.

44. The set of computer-readable instructions of claim 43 wherein said first priority level being higher in priority than said second priority level causes said second node to transition from a converged state to an unconverged state.

45. The set of computer-readable instructions of claim 43 wherein said method further comprises recognizing that a selection process for determining said root clock source has converged.

46. The set of computer-readable instructions of claim 45 wherein said recognizing further comprises recognizing that a specific number of messages have been received and wherein each of said messages indicate the same root clock source.

47. The set of computer-readable instructions of claim 42 wherein said method further comprises keeping said recognition that said second clocking signal is said root clock source because said first priority level is lower in priority than said second priority level.

48. The set of computer-readable instructions of claim 42 wherein said method further comprises comparing said indication of said stratum level for said first clocking signal against an indication of a stratum level for said second clocking signal if said first priority level is the same as said second priority level.

49. The set of computer-readable instructions of claim 48 wherein said method further comprises identifying said first clocking signal as said root clock source because said stratum level for said first clocking signal is lower than said stratum level for said second clocking signal.

50. The set of computer-readable instructions of claim 49 wherein said method further comprises recognizing that a selection process for determining said root clock source has converged.

51. The set of computer-readable instructions of claim 50 wherein said recognizing further comprises recognizing that a specific number of messages have been received and wherein each of said messages indicate the same root clock source.

52. The set of computer-readable instructions of claim 48 wherein said method further comprises keeping said recognition that said second clocking signal is said root clock source because said stratum level for said first clocking signal is higher than said stratum level for said second clocking signal.

53. The set of computer-readable instructions of claim 48 wherein said method further comprises, if said stratum level for said first clocking signal is the same as said stratum level for said second clocking signal, identifying said first clocking signal as said root clock source because said first clocking signal is externally generated relative to said network and said second clocking signal is internally generated relative to said network, and wherein, said message further comprised an indication as to whether said first clocking signal is internally or externally generated relative to said network.

54. The set of computer-readable instructions of claim 53 wherein said method further comprises recognizing that a selection process for determining said root clock source has converged.

55. The set of computer-readable instructions of claim 54 wherein said recognizing further comprises recognizing that a specific number of messages have been received and wherein each of said messages indicate the same root clock source.

56. The set of computer-readable instructions of claim 48 wherein said method further comprises, if said stratum level for said first clocking signal is the same as said stratum level for said second clocking signal, keeping said second clocking signal as said root clock source because said first clocking signal is internally generated relative to said network and said second clocking signal is externally generated relative to said network, and wherein, said message further comprised an indication as to whether said first clocking signal is internally or externally generated relative to said network.

57. The set of computer-readable instructions of claim 42 wherein said second node may be within an unconverged state or a converged state.

58. The set of computer-readable instructions of claim 42 wherein said message further comprises information that informs said second node of the best clock available to and usable by said first node.

59. The set of computer-readable instructions of claim 58 wherein said method further comprises selecting a root port for said second node, said root port being a port where a link resides having a clocking signal that is extracted by said second node.

60. The set of computer-readable instructions of claim 59 wherein said method further comprises configuring said second node'"'"'s clocking hardware to extract a clock at said root port.

61. The set of computer-readable instructions of claim 59 wherein said selecting a root port further comprises:

receiving messages from adjacent nodes, each message indicating the stratum level of its respective adjacent node; and

, refusing to use, as said root port, a port of said second node where a link resides that communicates to those of said adjacent ports having a higher stratum level than said second node.

62. A second node, said second node capable of being part of a synchronous network, said second node comprising:

a) means for receiving a message that was sent from a first node, said first node also part of said synchronous network, said message comprising;

(i) an indication of a first priority level for a first clocking signal, said first clocking signal recognized by said first node as a root clock source for said network when said message was sent, said first clocking signal found at a first port within said network and

(ii) an indication of a stratum level for said first clocking signal; and

,

b) means for comparing said first priority level against a second priority level, said second priority level for a second clocking signal, said second clocking signal recognized by said second node as said root clock source.

63. The second node of claim 62 further comprising means for identifying said first clocking signal as said root clock source because said first priority level is higher in priority than said second priority level.

64. The second node of claim 62 further comprising means for comparing a first indication against a second indication if said first priority level is the same as said second priority level, wherein, said message further comprises said first indication, said first indication indicative of a first stratum level, said first stratum level being the stratum level for said first clocking signal, said second indication indicating the stratum level for said second clocking signal.

65. The second node of claim 64 further comprising means for identifying said first clocking signal as said root clock source because said stratum level for said first clocking signal is lower than said stratum level for said second clocking signal.

66. The second node of claim 64 further comprising means for identifying, if said first stratum level is the same as said second stratum level, said first clocking signal as said root clock source because said first clocking signal is externally generated relative to said network and said second clocking signal is internally generated relative to said network.

67. The second node of claim 62 wherein said message further comprises information that informs said second node of the best clock available to and usable by said first node.

68. The second node of claim 67 further comprising means for selecting a root port for said second node, said root port being a port where a link resides having a clocking signal that is extracted by said second node.

69. The second node of claim 68 further comprising means for configuring said second node'"'"'s clocking hardware to extract a clock at said root port.

70. An apparatus that can be used to implement a node within a synchronous digital network, said apparatus comprising a network clock distribution protocol entity, said network clock distribution protocol entity to identify a root clock source of said network, said network clock distribution protocol entity to send messages that contain:

(i) an indication of a priority level of a clocking source that is recognized by said network clock distribution protocol entity as said root clock source; and

,

(ii) an indication of a stratum level of said clocking source.

71. The apparatus of claim 70 wherein said apparatus is a switch.

72. The apparatus of claim 70 wherein said network clock distribution protocol is implemented with software.

73. The apparatus of claim 70 wherein said apparatus further comprises installed network clock hardware.

74. The apparatus of claim 70 wherein said messages further contain an indication whether said recognized root clock source is an internal clock source or an external clock source.

75. The apparatus of claim 74 wherein said messages further contain an indication of a stratum level of said node.

76. The apparatus of claim 75 wherein said messages further contain a network address of said node.