Sparse graph coding scheduling for deterministic Ethernet

• US 9,705,700 B2
• Filed: 10/21/2014
• Issued: 07/11/2017
• Est. Priority Date: 10/21/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Valenza, Salvatore, Muccifora, Roberto, Ficara, Domenico, Cuda, Davide, Caldarola, Leo
• Primary Examiner(s): Taha, Shaq
• Assistant Examiner(s): Preval, Lionel
• Application Number:
  US14/519,714
• Publication Number:
  US 20160112308A1
• Time in Patent Office: 994 Days
• Field of Search: 370401, 370406, 370400, 370336, 398 43, 714784
• CPC Class Codes: H04L 12/417 with deterministic access, e.g. token passing
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling

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.

Claims

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 Ethernet network.

18. A non-transitory computer-readable medium storing computer program codes that, when executed, perform an operation for:

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 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.