Time and data synchronization between network devices

• US 20050135429A1
• Filed: 11/19/2004
• Published: 06/23/2005
• Est. Priority Date: 11/19/2003
• Status: Active Grant

• Current Assignee: Avaya Canada Corp. (Avaya Incorporated)
• Original Assignee: Avaya Canada Corp. (Avaya Incorporated)
• Inventors: Bingham, David Thomas, Hudici, Cristian, Poustchi, Behrouz, Stelzig, James Andrew
• Granted Patent: US 7,542,485 B2
• Time in Patent Office: Days
• US Class Current: 370/503
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: H04J 3/0641 Change of the master or reference, e.g. take-over or failure of the master
• CPC Class Codes: H04J 3/0664 unidirectional timestamps
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04Q 2213/13096 Digital apparatus individually associated with a subscriber line, digital line circuits
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13107 Control equipment for a part of the connection, distributed control, co-processing
• CPC Class Codes: H04Q 2213/13196 Connection circuit/link/trunk/junction, bridge, router, gateway
• CPC Class Codes: H04Q 2213/13213 Counting, timing circuits
• CPC Class Codes: H04Q 2213/1336 Synchronisation
• CPC Class Codes: H04Q 2213/13396 Signaling in general, in-band signalling

Abstract

To synchronize time between network devices equally capable of accurately maintaining an indication of current time, one of the network devices is deemed to be a reference for time and the other network devices synchronize their indications of current time to the reference. To synchronize copies of data at multiple network devices, each network device maintains a counter representative of the passage of time but not necessarily of current time. The counter at each device is periodically synchronized with the counters of other network devices. When data is changed at a network device, the value of the counter at the time of changing is stored in association with the changed data. Stored counter values are used to determine whether a local copy or a remote copy of the data is likely more recent and therefore preferable. A further test may be applied if a counter value comparison is inconclusive.

Claims

1. At one network device of a plurality of network devices, a method comprising:

maintaining a first counter to represent the passage of time such that the represented amount of passed time at any given moment is at least as large as the represented amount of passed time at any previous moment; and

when data is changed to become changed data;

storing in association with said changed data the value of said first counter at the time of changing of the data; and

sending to another network device an indication of said changed data along with the value of said first counter at the time of changing of the data.

2. The method of claim 1 wherein said indication of said changed data is a copy of the changed data.

3. The method of claim 1 further comprising:

synchronizing said first counter with a received indication of a value of a second counter maintained at said another network device to represent the passage of time such that the represented amount of passed time at any given moment is at least as large as the represented amount of passed time at any previous moment.

4. The method of claim 3 further comprising:

upon receiving an indication of a change to a remote copy of said changed data by said another network device and an associated value of the second counter at the time of changing of said remote copy;

comparing the stored value of said first counter against the received value of said second counter; and

determining which of the stored changed data and the remote copy of said changed data is preferable based on said comparing.

5. The method of claim 4 wherein, if said comparing indicates that the received value of said second counter represents a greater passage of time than the stored value of said first counter, said determining determines the remote copy of said changed data to be preferable to said stored changed data.

6. The method of claim 5 further comprising, if said comparing indicates that the received value of said second counter represents a greater passage of time than the stored value of said first counter, replacing said stored changed data with said remote copy.

7. The method of claim 4 wherein, if said comparing indicates that the received value of said second counter represents a lesser passage of time than the stored value of said first counter, said determining determines the stored data to be preferable to the remote copy of said data.

8. The method of claim 7 further comprising, if said comparing indicates that the received value of said second counter represents a lesser passage of time than the stored value of said first counter, sending a copy of said stored data to said another network device.

9. The method of claim 4 further comprising, if said comparing indicates that the received value of said second counter is equal to the stored value of said first counter, applying a further test to determine which of the stored data and the remote copy of said data is preferable.

10. The method of claim 9 wherein said applying a further test comprises comparing a unique identifier of said one network device to a unique identifier of said another network device.

11. The method of claim 10 wherein said unique identifiers are hardware addresses.

12. The method of claim 11 wherein, if said comparing indicates that said hardware address of said one network device is larger than said hardware address of said another network device, said determining determines the remote copy of said data to be preferable to the stored data.

13. The method of claim 12 further comprising, if said comparing indicates that said hardware address of said one network device is larger than said hardware address of said another network device, replacing said stored data with said remote copy.

14. The method of claim 11 wherein, if said comparing indicates that said hardware address of said one network device is smaller than said hardware address of said another network device, said determining determines the stored data to be preferable to the remote copy of said data.

15. The method of claim 14 further comprising, if said comparing indicates that said hardware address of said one network device is smaller than said hardware address of said another network device, sending a copy of said stored data to said another network device.

16. The method of claim 3 wherein said synchronizing comprises:

comparing said value of said second counter from said received indication to a current value of said first counter; and

based on said comparing, determining whether to adjust the value of said first counter.

17. The method of claim 16 further comprising, if said comparing indicates that said value of said second counter represents a greater passage of time than said current value of said first counter, setting the value of said first counter to said value of said second counter.

18. The method of claim 1 wherein said maintaining a first counter comprises, upon initialization of said one network device:

from previously stored counter values which were stored in association with any stored data that is indicated to be changed data, selecting a value representing the greatest amount of passed time; and

based on the selected value, initializing said first counter.

19. The method of claim 18 wherein said initializing comprises setting the value of said first counter to the selected value.

20. The method of claim 3 wherein said first counter and said second counter comprise monotonically increasing counters.

21. The method of claim 20 wherein said maintaining a first counter comprises periodically incrementing said first counter upon the elapsing of a predetermined time interval.

22. At one network device of a plurality of network devices, a method comprising:

receiving indications of a current time from other network devices, each of said network devices being equally capable of maintaining an accurate representation of current time;

determining which of said other network devices is a reference for time; and

synchronizing a clock with an indication of a current time received from said reference for time.

23. The method of claim 22 wherein said determining is based on a comparison of a hardware address of said one network device with the hardware addresses of said other network devices.

24. The method of claim 23 further comprising:

receiving an indication of a current time from a further network device whose capability for maintaining an accurate representation of current time is superior to the capability of said one network device for maintaining an accurate representation of current time, said further network device being distinct from said reference for time; and

synchronizing said clock with said indication of a current time received from said further network device.

25. A network device adapted to:

maintain a first counter to represent the passage of time such that the represented amount of passed time at any given moment is at least as large as the represented amount of passed time at any previous moment; and

when data is changed to become changed data;

store in association with said changed data the value of said first counter at the time of changing of the data; and

send to another network device an indication of said changed data along with the value of said first counter at the time of changing of the data.

26. The network device of claim 25 wherein said indication of said changed data is a copy of the changed data.

27. The network device of claim 25 further adapted to:

synchronize said first counter with a received indication of a value of a second counter maintained at said another network device to represent the passage of time such that the represented amount of passed time at any given moment is at least as large as the represented amount of passed time at any previous moment.

28. The network device of claim 27 further adapted to:

upon receiving an indication of a change to a remote copy of said changed data by said another network device and an associated value of the second counter at the time of changing of said remote copy;

compare the stored value of said first counter against the received value of said second counter; and

determine which of the stored changed data and the remote copy of said changed data is preferable based on said comparing.

29. The network device of claim 28 wherein, if said comparing indicates that the received value of said second counter represents a greater passage of time than the stored value of said first counter, said determining determines the remote copy of said changed data to be preferable to said stored changed data.

30. The network device of claim 29 further adapted to, if said comparing indicates that the received value of said second counter represents a greater passage of time than the stored value of said first counter, replace said stored changed data with said remote copy.

31. The network device of claim 28 wherein, if said comparing indicates that the received value of said second counter represents a lesser passage of time than the stored value of said first counter, said determining determines the stored data to be preferable to the remote copy of said data.

32. The network device of claim 31 further adapted to, if said comparing indicates that the received value of said second counter represents a lesser passage of time than the stored value of said first counter, send a copy of said stored data to said another network device.

33. The network device of claim 28 further adapted to, if said comparing indicates that the received value of said second counter is equal to the stored value of said first counter, apply a further test to determine which of the stored data and the remote copy of said data is preferable.

34. The network device of claim 33 wherein said applying a further test comprises comparing a unique identifier of said one network device to a unique identifier of said another network device.

35. The network device of claim 34 wherein said unique identifiers are hardware addresses.

36. The network device of claim 35 wherein, if said comparing indicates that said hardware address of said one network device is larger than said hardware address of said another network device, said determining determines the remote copy of said data to be preferable to the stored data.

37. The network device of claim 36 further adapted to, if said comparing indicates that said hardware address of said one network device is larger than said hardware address of said another network device, replace said stored data with said remote copy.

38. The network device of claim 35 wherein, if said comparing indicates that said hardware address of said one network device is smaller than said hardware address of said another network device, said determining determines the stored data to be preferable to the remote copy of said data.

39. The network device of claim 38 further adapted to, if said comparing indicates that said hardware address of said one network device is smaller than said hardware address of said another network device, send a copy of said stored data to said another network device.

40. The network device of claim 27 wherein said synchronizing comprises:

comparing said value of said second counter from said received indication to a current value of said first counter; and

based on said comparing, determining whether to adjust the value of said first counter.

41. The network device of claim 40 further adapted to, if said comparing indicates that said value of said second counter represents a greater passage of time than said current value of said first counter, set the value of said first counter to said value of said second counter.

42. The network device of claim 25 wherein said maintaining a first counter comprises, upon initialization of said one network device:

from previously stored counter values which were stored in association with any stored data that is indicated to be changed data, selecting a value representing the greatest amount of passed time; and

based on the selected value, initializing said first counter.

43. The network device of claim 42 wherein said initializing comprises setting the value of said first counter to the selected value.

44. The network device of claim 27 wherein said first counter and said second counter comprise monotonically increasing counters.

45. The network device of claim 44 wherein said maintaining a first counter comprises periodically incrementing said first counter upon the elapsing of a predetermined time interval.

46. A network device adapted to:

receive indications of a current time from other network devices, each of said network devices being equally capable of maintaining an accurate representation of current time;

determine which of said other network devices is a reference for time; and

synchronize a clock with an indication of a current time received from said reference for time.

47. The network device of claim 46 wherein said determining is based on a comparison of a hardware address of said one network device with the hardware addresses of said other network devices.

48. The network device of claim 47 further adapted to:

receive an indication of a current time from a further network device whose capability for maintaining an accurate representation of current time is superior to the capability of said one network device for maintaining an accurate representation of current time, said further network device being distinct from said reference for time; and

synchronize said clock with said indication of a current time received from said further network device.

49. A machine-readable medium including machine-executable code for execution at one network device of a plurality of network devices, comprising:

machine-executable code for maintaining a first counter to represent the passage of time such that the represented amount of passed time at any given moment is at least as large as the represented amount of passed time at any previous moment; and

machine-executable code for, when data is changed to become changed data;

storing in association with said changed data the value of said first counter at the time of changing of the data; and

sending to another network device an indication of said changed data along with the value of said first counter at the time of changing of the data.

50. The machine-readable medium of claim 49 wherein said indication of said changed data is a copy of the changed data.

51. The machine-readable medium of claim 49 further comprising:

machine-executable code for synchronizing said first counter with a received indication of a value of a second counter maintained at said another network device to represent the passage of time such that the represented amount of passed time at any given moment is at least as large as the represented amount of passed time at any previous moment.

52. The machine-readable medium of claim 51 further comprising:

machine-executable code for, upon receiving an indication of a change to a remote copy of said changed data by said another network device and an associated value of the second counter at the time of changing of said remote copy;

comparing the stored value of said first counter against the received value of said second counter; and

determining which of the stored changed data and the remote copy of said changed data is preferable based on said comparing.

53. The machine-readable medium of claim 52 wherein, if said comparing indicates that the received value of said second counter represents a greater passage of time than the stored value of said first counter, said determining determines the remote copy of said changed data to be preferable to said stored changed data.

54. The machine-readable medium of claim 53 further comprising machine-executable code for, if said comparing indicates that the received value of said second counter represents a greater passage of time than the stored value of said first counter, replacing said stored changed data with said remote copy.

55. The machine-readable medium of claim 52 wherein, if said comparing indicates that the received value of said second counter represents a lesser passage of time than the stored value of said first counter, said determining determines the stored data to be preferable to the remote copy of said data.

56. The machine-readable medium of claim 55 further comprising machine-executable code for, if said comparing indicates that the received value of said second counter represents a lesser passage of time than the stored value of said first counter, sending a copy of said stored data to said another network device.

57. The machine-readable medium of claim 52 further comprising machine-executable code for, if said comparing indicates that the received value of said second counter is equal to the stored value of said first counter, applying a further test to determine which of the stored data and the remote copy of said data is preferable.

58. The machine-readable medium of claim 57 wherein said applying a further test comprises comparing a unique identifier of said one network device to a unique identifier of said another network device.

59. The machine-readable medium of claim 58 wherein said unique identifiers are hardware addresses.

60. The machine-readable medium of claim 59 wherein, if said comparing indicates that said hardware address of said one network device is larger than said hardware address of said another network device, said determining determines the remote copy of said data to be preferable to the stored data.

61. The machine-readable medium of claim 60 further comprising machine-executable code for, if said comparing indicates that said hardware address of said one network device is larger than said hardware address of said another network device, replacing said stored data with said remote copy.

62. The machine-readable medium of claim 59 wherein, if said comparing indicates that said hardware address of said one network device is smaller than said hardware address of said another network device, said determining determines the stored data to be preferable to the remote copy of said data.

63. The machine-readable medium of claim 62 further comprising machine-executable code for, if said comparing indicates that said hardware address of said one network device is smaller than said hardware address of said another network device, sending a copy of said stored data to said another network device.

64. The machine-readable medium of claim 51 wherein said synchronizing comprises:

comparing said value of said second counter from said received indication to a current value of said first counter; and

based on said comparing, determining whether to adjust the value of said first counter.

65. The machine-readable medium of claim 64 further comprising machine-executable code for, if said comparing indicates that said value of said second counter represents a greater passage of time than said current value of said first counter, setting the value of said first counter to said value of said second counter.

66. The machine-readable medium of claim 49 wherein said maintaining a first counter comprises, upon initialization of said one network device:

from previously stored counter values which were stored in association with any stored data that is indicated to be changed data, selecting a value representing the greatest amount of passed time; and

based on the selected value, initializing said first counter.

67. The machine-readable medium of claim 66 wherein said initializing comprises setting the value of said first counter to the selected value.

68. The machine-readable medium of claim 51 wherein said first counter and said second counter comprise monotonically increasing counters.

69. The machine-readable medium of claim 68 wherein said maintaining a first counter comprises periodically incrementing said first counter upon the elapsing of a predetermined time interval.

70. A machine-readable medium including machine-executable code for execution at one network device of a plurality of network devices, comprising:

machine-executable code for receiving indications of a current time from other network devices, each of said network devices being equally capable of maintaining an accurate representation of current time;

machine-executable code for determining which of said other network devices is a reference for time; and

machine-executable code for synchronizing a clock with an indication of a current time received from said reference for time.

71. The machine-readable medium of claim 70 wherein said determining is based on a comparison of a hardware address of said one network device with the hardware addresses of said other network devices.

72. The machine-readable medium of claim 71 further comprising:

machine-executable code for receiving an indication of a current time from a further network device whose capability for maintaining an accurate representation of current time is superior to the capability of said one network device for maintaining an accurate representation of current time, said further network device being distinct from said reference for time; and

machine-executable code for synchronizing said clock with said indication of a current time received from said further network device.