Hierarchical scheduler for deterministic networking

Patent metadata

Field	Value
Publication number	US-9749254-B2
Application number	US-201414280814-A
Country	US
Kind code	B2
Filing date	May 19, 2014
Priority date	May 19, 2014
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

In one embodiment, a method is disclosed in which a device identifies a set of data stream rates for a plurality of data streams. A Huffman tree is constructed for data transmission time slots based on the set of data stream rates. A number of time slots assigned to a parent node in the tree are determined and evenly distributed to child nodes of the parent node, to assign the time slots to the data streams.

First claim

What is claimed is:

1. A method, comprising:
identifying, at a device, a set of data stream rates for a plurality of data streams;
constructing, by the device, a Huffman tree for data transmission time slots based on the set of data stream rates by sorting the data streams by respective data rates;
determining, by the device, a number of time slots assigned to a parent node in the tree; and
using, by the device, the Huffman tree to evenly distribute time slots to child nodes of the parent node to assign the time slots to the data streams by:
grouping the data rates into pairs to form a base layer of child nodes,
assigning parent nodes to each pair of data rates in the base layer that combines frequencies and data rates of the child nodes in a given pair, and
continuing grouping and assigning until a root node is formed.

2. The method as in claim 1 , further comprising:
determining a cycle size for the time slots based on the data stream rates.

3. The method as in claim 2 , wherein the set of time periods is determined using a least-squares regression.

4. The method as in claim 2 , wherein the cycle size is a multiple of the data stream rates.

5. The method as in claim 1 , wherein a cycle size of the data transmission time slots is variable.

6. The method as in claim 5 , wherein the cycle size of the data transmission time slots is a power of two.

7. The method as in claim 1 , wherein the device is a path computation element (PCE).

8. An apparatus, comprising:
one or more network interfaces to communicate with a network;
a processor coupled to the network interfaces and adapted to execute one or more processes; and
a memory configured to store a process executable by the processor, the process when executed operable to:
identify a set of data stream rates for a plurality of data streams;
construct a Huffman tree for data transmission time slots based on the set of data stream rates by sorting the data streams by respective data rates;
determine a number of time slots assigned to a parent node in the tree; and
use the Huffman tree to evenly distribute time slots to child nodes of the parent node by:
grouping the data rates into pairs to form a base layer of child nodes,
assigning parent nodes to each pair of data rates in the base layer that combines frequencies and data rates of the child nodes in a given pair, and
continuing grouping and assigning until a root node is formed.

9. The apparatus as in claim 8 , wherein the process when executed is further operable to:
determine a cycle size for the time slots based on the data stream rates.

10. The apparatus as in claim 9 , wherein the set of time periods is determined using a least-squares regression.

11. The apparatus as in claim 9 , wherein the cycle size is a multiple of the data stream rates.

12. The apparatus as in claim 8 , wherein a cycle size of the data transmission time slots is variable.

13. The apparatus as in claim 12 , wherein the cycle size of the data transmission time slots is a power of two.

14. The apparatus as in claim 8 , wherein the process when executed is further operable to:
compute a network path for the data streams.

15. A tangible, non-transitory, computer-readable media having instructions encoded thereon, the instructions when executed by a processor operable to:
identify a set of data stream rates for a plurality of data streams;
construct a Huffman tree for data transmission time slots based on the set of data stream rates by sorting the data streams by respective data rates;
determine a number of time slots assigned to a parent node in the tree; and
use the Huffman tree to evenly distribute time slots to child nodes of the parent node by:
grouping the data rates into pairs to form a base layer of child nodes,
assigning parent nodes to each pair of data rates in the base layer that combines frequencies and data rates of the child nodes in a given pair, and
continuing grouping and assigning until a root node is formed.

16. The computer-readable media as in claim 15 , wherein the instructions when executed are further operable to:
determine a cycle size for the time slots based on the data stream rates.

17. The computer-readable media as in claim 16 , wherein the set of time periods is determined using a least-squares regression.

18. The computer-readable media as in claim 16 , wherein the cycle size is a multiple of the data stream rates.

19. The computer-readable media as in claim 15 , wherein the software when executed is further operable to:
compute a network path for the data streams.

20. The computer-readable media as in claim 15 , wherein a cycle size of the data transmission time slots is variable.

Assignees

• Cisco Tech Inc

Inventors

• Ficara Domenico

Classifications

• H04L47/60 Primary

  implementing hierarchical scheduling · CPC title

• H04J3/247

  ATM or packet multiplexing · CPC title

• H04L47/56

  implementing delay-aware scheduling · CPC title