Sparse graph coding scheduling for deterministic Ethernet

Patent metadata

Field	Value
Publication number	US-9705700-B2
Application number	US-201414519714-A
Country	US
Kind code	B2
Filing date	Oct 21, 2014
Priority date	Oct 21, 2014
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

Embodiments provide techniques for transmitting data packets across a deterministic Ethernet network. Embodiments receive, at a first device in the deterministic Ethernet network, a deterministic binary schedule specifying timing information for transmitting data fragments relating to a plurality of data flows. Data packets to transmit to a destination device within the deterministic Ethernet network are received at the first device. Embodiments include fragmenting each of the data packets into two or more fragments and encoding at least one of the two or more fragments for each of the data packets with a respective sparse graph code. The encoded fragments are transmitted to the destination device, across multiple paths through the deterministic Ethernet network, according to timing information specified in the deterministic binary schedule.

First claim

We claim:

1. A method, comprising:
receiving, at a first device in a deterministic Ethernet network, a deterministic binary schedule specifying timing information for transmitting data fragments relating to a plurality of data flows;
receiving data packets to transmit to a destination device within the deterministic Ethernet network;
fragmenting each of the data packets into two or more fragments;
encoding, by operation of one or more computer processors, at least one of the two or more fragments for each of the data packets with a respective sparse graph code; and
transmitting the encoded fragments to the destination device, across multiple paths through the deterministic Ethernet network, according to timing information specified in the deterministic binary schedule, comprising:
transmitting a first one of the data fragments at a first moment in time, according to the timing information specified in the deterministic binary schedule; and
transmitting a duplicate copy of the first data fragment at a second moment in time, according to the timing information specified in the deterministic binary schedule, wherein the second moment in time is subsequent to the first moment in time.

2. The method of claim 1 , wherein the sparse graph code comprises a low-density parity-check code.

3. The method of claim 1 , wherein the destination device, upon receiving the two or more fragments, is configured to reassemble the data packet from the received two or more fragments, wherein the destination device is configured to compute a first fragment using the sparse graph codes, thereby creating zero-jitter scheduling for the transmission of the data packets.

4. The method of claim 3 , wherein the destination device is configured to reassemble the data packet using fragments received from different paths through the deterministic Ethernet network.

5. The method of claim 1 , wherein each of the plurality of data flows corresponds to a respective period value, and the method further comprising:
generating the deterministic binary schedule specifying the timing information for transmitting data fragments relating to a plurality of data flows, such that all of the respective two or more fragments for each of the data packets arrives at the destination device according to a schedule determined based on the respective period values.

6. The method of claim 5 , further comprising:
preloading each network device within the deterministic Ethernet network with the generated deterministic binary schedule,
wherein receiving, at the first device in a deterministic Ethernet network, the deterministic binary schedule further comprises retrieving the deterministic binary schedule from a storage medium accessible by the first device onto which the deterministic binary schedule was preloaded.

7. The method of claim 6 , further comprising:
determining an optimal number of multiple paths on which the encoded fragments are to be transmitted, based on an estimated data loss rate for the deterministic Ethernet network, wherein the encoded fragments are transmitted to the destination device across the optimal number of multiple paths through the deterministic Ethernet network.

8. The method of claim 7 , wherein the optimal number of multiple paths is determined further based on an estimated time savings value corresponding to transmitting the encoded fragments across an additional path through the deterministic Ethernet network.

9. The method of claim 7 , wherein the optimal number of multiple paths is determined further based on an estimated amount of increased bandwidth consumed from transmitting the encoded fragments across an additional path through the deterministic Ethernet network.

10. A network device, comprising:
one or more computer processors;
one or more ports connecting the network device to a deterministic Ethernet network; and
logic for:
receiving, at the network device, a deterministic binary schedule specifying timing information for transmitting data fragments relating to a plurality of data flows;
receiving data packets to transmit to a destination device within the deterministic Ethernet network;
fragmenting each of the data packets into two or more fragments;
encoding, by operation of the one or more computer processors, at least one of the two or more fragments for each of the data packets with a respective sparse graph code; and
transmitting, using the one or more ports, the encoded fragments to the destination device across multiple paths through the deterministic Ethernet network, according to timing information specified in the deterministic binary schedule, comprising:
transmitting a first one of the data fragments at a first moment in time, according to the timing information specified in the deterministic binary schedule; and
transmitting a duplicate copy of the first data fragment at a second moment in time, according to the timing information specified in the deterministic binary schedule, wherein the second moment in time is subsequent to the first moment in time.

11. The network device of claim 10 , wherein the sparse graph code comprises a low-density parity-check code.

12. The network device of claim 10 , wherein the destination device, upon receiving the two or more fragments, is configured to reassemble the data packet from the received two or more fragments, wherein the destination device is configured to compute a first fragment using the sparse graph codes, thereby creating zero-jitter scheduling for the transmission of the data packets.

13. The network device of claim 12 , wherein the destination device is configured to reassemble the data packet using fragments received from different paths through the deterministic Ethernet network.

14. The network device of claim 10 , wherein each of the plurality of data flows corresponds to a respective period value, and the network device further comprising logic for:
generating the deterministic binary schedule specifying the timing information for transmitting data fragments relating to a plurality of data flows, such that all of the respective two or more fragments for each of the data packets arrives at the destination device according to a schedule determined based on the respective period values.

15. The network device of claim 14 , further comprising logic for:
preloading each network device within the deterministic Ethernet network with the generated deterministic binary schedule,
wherein the logic for receiving, at the first device in a deterministic Ethernet network, the deterministic binary schedule further comprises logic for retrieving the deterministic binary schedule from a storage medium accessible by the first device onto which the deterministic binary schedule was preloaded.

16. The network device of claim 15 , further comprising logic for:
determining an optimal number of multiple paths on which the encoded fragments are to be transmitted, based on an estimated data loss rate for the deterministic Ethernet network, wherein the encoded fragments are transmitted to the destination device across the optimal number of multiple paths through the deterministic Ethernet network.

17. The network device of claim 16 , wherein the optimal number of multiple paths is determined further based on (i) an estimated time savings value corresponding to transmitting the encoded fragments across an additional path through the deterministic Ethernet network and (ii) an estimated amount of increased bandwidth consumed from transmitting the encoded fragments across an additional path through the deterministic Et

Assignees

• Cisco Tech Inc

Inventors

• Ficara Domenico
• Cuda Davide
• Caldarola Leo
• Valenza Salvatore
• Muccifora Roberto

Classifications

• H04L47/56

  implementing delay-aware scheduling · CPC title

• H04L12/417 Primary

  with deterministic access, e.g. token passing · CPC title

• H04L47/826

  Involving periods of time · CPC title

• H04L47/50 Primary

  Queue scheduling · CPC title