DIRECTED ACYCLIC GRAPH OPTIMIZATION BASED ON TIMING INFORMATION FOR GENERATING OPTIMIZED NETWORK CLOCK

• US 20170353292A1
• Filed: 06/02/2016
• Published: 12/07/2017
• Est. Priority Date: 06/02/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: THUBERT, PASCAL, MONTINI, LAURENT
• Granted Patent: US 10,298,346 B2
• Time in Patent Office: Days
• CPC Class Codes: H04J 3/0635 Clock or time synchronisation in a network timer in protocols H04L69/28
• CPC Class Codes: H04J 3/0679 by determining clock distribution path in a network
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 56/00 Synchronisation arrangements
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In one embodiment, a method comprises receiving, by a network device, one or more advertisement messages comprising timing information describing a quality of a network clock that is originated by a master clock device at a root of a directed acyclic graph (DAG); the network device executing an objective function for the DAG providing an optimized loopless time topology for the network clock, synchronized to the master clock device, based on the timing information; and the network device attaching to a parent device in the DAG based on the objective function, for optimized generation of the network clock by the network device.

Claims

1. A method comprising:

receiving, by a network device, one or more advertisement messages comprising timing information describing a quality of a network clock that is originated by a master clock device at a root of a directed acyclic graph (DAG);

the network device executing an objective function for the DAG providing an optimized loopless time topology for the network clock, synchronized to the master clock device, based on the timing information; and

the network device attaching to a parent device in the DAG based on the objective function, for optimized generation of the network clock by the network device.

2. The method of claim 1, further comprising receiving a plurality of said advertisement messages from respective attached network devices belonging to the DAG, the executing of the objective function comprising selecting the parent device among the attached network devices belonging to the DAG, based on the timing information from the respective advertisement messages.

3. The method of claim 2, further comprising:

selecting a second parent device, among the attached network devices, for attachment in the DAG based the corresponding advertisement message and the objective function;

generating the network clock, based on synchronizing to the master clock device via the second parent device in the DAG.

4. The method of claim 1, further comprising:

determining local time error attributes associated with the network device;

determining link-based time error attributes associated with a data link between the parent device and the network device; and

the network device outputting a locally-generated advertisement message specifying aggregated timing information based on the local time error attributes and the link-based time error attributes, the locally-generated advertisement message advertising an aggregated quality of the network clock that is originated by the master clock device and generated by the network device.

5. The method of claim 4, further comprising:

selecting a second parent device for attachment in the DAG based on the corresponding advertisement message and the objective function;

generating the network clock, based on synchronizing to the master clock device via the second parent device in the DAG; and

the network device outputting a second locally-generated advertisement message specifying second aggregated timing information based on the corresponding timing information by the second parent device, the local time error attributes and the link-based time error attributes, the second locally-generated advertisement message advertising a second aggregated quality of the network clock that is generated by the network device and synchronized to the master clock device via the second parent device.

6. The method of claim 1, wherein the timing information includes any one of precision time protocol (PTP) parameters for describing the quality, device timing quality information for any one or more of any network device along a path in the DAG between and including the parent device and the master clock device, link timing quality information for any one or more for any data link along the path, aggregated PTP parameters along the path, aggregated device timing quality information along the path, or aggregated link timing quality information along the path.

7. The method of claim 1, further comprising:

receiving, by the network device, a second advertisement message comprising corresponding timing information describing a quality of a second network clock that is originated by a second master clock device at the corresponding root of a second DAG;

the network device executing a second objective function for the second DAG providing the corresponding optimized loopless time topology for the second network clock, synchronized to the second master clock device, based on the corresponding timing information in the second advertisement message; and

the network device attaching to a second parent device in the second DAG based on the second objective function, for optimized generation of the second network clock by the network device.

8. The method of claim 7, further comprising the network device generating an aggregated network clock based on the master clock device in the DAG and the second master clock device in the second DAG.

9. An apparatus comprising

a device interface circuit configured for receiving one or more advertisement messages comprising timing information describing a quality of a network clock that is originated by a master clock device at a root of a directed acyclic graph (DAG);

and

a processor circuit configured for executing an objective function for the DAG providing an optimized loopless time topology for the network clock, synchronized to the master clock device, based on the timing information;

the processor circuit further configured for causing the apparatus to attach to a parent device in the DAG based on the objective function, for optimized generation of the network clock by the apparatus.

10. The apparatus of claim 9, wherein:

the device interface circuit is configured for receiving a plurality of said advertisement messages from respective attached network devices belonging to the DAG;

the processor circuit configured for selecting the parent device among the attached network devices belonging to the DAG, based on the timing information from the respective advertisement messages.

11. The apparatus of claim 10, wherein:

the processor circuit is configured for selecting a second parent device, among the attached network devices, for attachment in the DAG based the corresponding advertisement message and the objective function;

the processor circuit further configured for generating the network clock, based on synchronizing to the master clock device via the second parent device in the DAG.

12. The apparatus of claim 9, wherein the processor circuit further is configured for:

determining local time error attributes associated with the apparatus;

determining link-based time error attributes associated with a data link between the parent device and the apparatus; and

generating and outputting, via the device interface circuit, a locally-generated advertisement message specifying aggregated timing information based on the local time error attributes and the link-based time error attributes, the locally-generated advertisement message advertising an aggregated quality of the network clock that is originated by the master clock device and generated by the apparatus.

13. The apparatus of claim 12, wherein the processor circuit further is configured for:

selecting a second parent device for attachment in the DAG based on the corresponding advertisement message and the objective function;

generating the network clock, based on synchronizing to the master clock device via the second parent device in the DAG; and

generating and outputting, via the device interface circuit, a second locally-generated advertisement message specifying second aggregated timing information based on the corresponding timing information by the second parent device, the local time error attributes and the link-based time error attributes, the second locally-generated advertisement message advertising a second aggregated quality of the network clock that is generated by the apparatus and synchronized to the master clock device via the second parent device.

14. The apparatus of claim 9, wherein the timing information includes any one of precision time protocol (PTP) parameters for describing the quality, device timing quality information for any one or more of any network device along a path in the DAG between and including the parent device and the master clock device, link timing quality information for any one or more for any data link along the path, aggregated PTP parameters along the path, aggregated device timing quality information along the path, or aggregated link timing quality information along the path.

15. The apparatus of claim 9, wherein:

the device interface circuit is configured for receiving a second advertisement message comprising corresponding timing information describing a quality of a second network clock that is originated by a second master clock device at the corresponding root of a second DAG;

the processor circuit further is configured for executing a second objective function for the second DAG providing the corresponding optimized loopless time topology for the second network clock, synchronized to the second master clock device, based on the corresponding timing information in the second advertisement message; and

the processor circuit further is configured for attaching to a second parent device in the second DAG based on the second objective function, for optimized generation of the second network clock by the network device.

16. The apparatus of claim 15, wherein the processor circuit further is configured for generating an aggregated network clock based on the master clock device in the DAG and the second master clock device in the second DAG.

17. One or more non-transitory tangible media encoded with logic for execution by a machine and when executed by the machine operable for:

receiving, by the machine implemented as a network device, one or more advertisement messages comprising timing information describing a quality of a network clock that is originated by a master clock device at a root of a directed acyclic graph (DAG);

the network device executing an objective function for the DAG providing an optimized loopless time topology for the network clock, synchronized to the master clock device, based on the timing information; and

the network device attaching to a parent device in the DAG based on the objective function, for optimized generation of the network clock by the network device.

18. The one or more non-transitory tangible media of claim 17, further operable for:

determining local time error attributes associated with the network device;

determining link-based time error attributes associated with a data link between the parent device and the network device; and

the network device outputting a locally-generated advertisement message specifying aggregated timing information based on the local time error attributes and the link-based time error attributes, the locally-generated advertisement message advertising an aggregated quality of the network clock that is originated by the master clock device and generated by the network device.

19. The one or more non-transitory tangible media of claim 17, wherein the timing information includes any one of precision time protocol (PTP) parameters for describing the quality, device timing quality information for any one or more of any network device along a path in the DAG between and including the parent device and the master clock device, link timing quality information for any one or more for any data link along the path, aggregated PTP parameters along the path, aggregated device timing quality information along the path, or aggregated link timing quality information along the path.

20. The one or more non-transitory tangible media of claim 17, further operable for:

receiving, by the network device, a second advertisement message comprising corresponding timing information describing a quality of a second network clock that is originated by a second master clock device at the corresponding root of a second DAG;

the network device executing a second objective function for the second DAG providing the corresponding optimized loopless time topology for the second network clock, synchronized to the second master clock device, based on the corresponding timing information in the second advertisement message; and

the network device attaching to a second parent device in the second DAG based on the second objective function, for optimized generation of the second network clock by the network device.

21. -22. (canceled)