Sparse graph coding scheduling for deterministic ethernet

Patent metadata

Field	Value
Publication number	US-2016112308-A1
Application number	US-201414519714-A
Country	US
Kind code	A1
Filing date	Oct 21, 2014
Priority date	Oct 21, 2014
Publication date	Apr 21, 2016
Grant date	—

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.

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 deterministic binary schedule specifies that a first one of the data fragments is to be transmitted at a first moment in time, and wherein the deterministic binary schedule further specifies that a duplicate copy of the first data fragment is to be transmitted at a second moment in time distinct from the first moment in time.

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

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

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

7 . The method of claim 6 , 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.

8 . The method of claim 7 , 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.

9 . The method of claim 8 , 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.

10 . The method of claim 8 , 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.

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

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

13 . The network device of claim 11 , wherein the deterministic binary schedule specifies that a first one of the data fragments is to be transmitted at a first moment in time, and wherein the deterministic binary schedule further specifies that a duplicate copy of the first data fragment is to be transmitted at a second moment in time distinct from the first moment in time.

14 . The network device of claim 11 , 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.

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

16 . The network device of claim 11 , wherein each of the plurality of data flows corresponds to a respective period value, and the 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.

17 . The network device of claim 16 , 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.

18 . The network device of claim 17 , 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.

19 . The network device of claim 18 , 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.

Assignees

• Cisco Tech Inc

Inventors

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

Classifications

• H04L47/283

  in response to processing delays, e.g. caused by jitter or round trip time [RTT] · CPC title

• H04L45/74

  Address processing for routing · CPC title

• H04L45/24

  Multipath · CPC title

• H04L45/66 Primary

  Layer 2 routing, e.g. in Ethernet based MAN's · CPC title

• H04L47/50 Primary

  Queue scheduling · CPC title