Integrated erasure coding for data storage and transmission

• US 10,742,736 B2
• Filed: 12/19/2017
• Issued: 08/11/2020
• Est. Priority Date: 12/19/2017
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Xu, Jun, Ryan, Robert P., Mackey, Grant C., Malina, James N., O'Neill, Robin, Larson, Nils E.
• Primary Examiner(s): Won, Michael
• Assistant Examiner(s): McBeth, William C
• Application Number:
  US15/847,761
• Publication Number:
  US 20190190979A1
• Time in Patent Office: 966 Days
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H04L 1/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 1/0076 Distributed coding, e.g. network coding, involving channel coding coding in both space and time H04L1/0618; cooperative diversity H04B7/022
• CPC Class Codes: H04L 2001/0092 Error control systems characterised by the topology of the transmission link
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04N 21/231 Content storage operation, e.g. caching movies for short term storage, replicating data over plural servers, prioritizing data for deletion
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568

Abstract

Embodiments of network devices for content distribution are described. In some embodiments, an edge network device integrates network coding for content distribution with erasure coding for data storage. Embodiments of methods of integrating network coding and erasure coding are also disclosed. In some embodiments, an edge network device can determine content distribution and storage for content based on one or more penalty functions that assess storage capacity, computational power, user demand, and/or network bandwidth for optimal resource usage. In some embodiments, an edge network device creates fragments of content and transmits a subset of the fragments for early distribution. In response to a user request for the content, the edge network device can transmit the remaining fragments to the user device for the user device to reconstruct the original content.

Claims

1. A network device, comprising:

a memory comprising a cache and permanent storage; and

one or more processors configured to receive a request for information from a user device, the one or more processors further configured to;

in response to determining that an erasure encoded version of the requested information is stored in the memory of the network device;

in response to determining that a network condition does not satisfy a transmission quality threshold;

in response to determining that the erasure encoded version of the requested information is not stored in the cache of the network device;

in response to determining that a penalty for erasure encoding the requested information exceeds a penalty for retrieving the erasure encoded version of the requested information from the permanent storage of the network device, retrieve from the permanent storage and transmit the erasure encoded version of the requested information to the user device by applying network coding; and

in response to determining that the penalty for erasure encoding the requested information does not exceed the penalty for retrieving the erasure encoded version of the requested information from the permanent storage of the network device, partially retrieve the requested information from the permanent storage, erasure encode the partially retrieved requested information, and transmit the produced erasure encoded version of the requested information to the user device by applying network coding, wherein the partially retrieved requested information is a subset of the requested information needed to reconstruct the requested information at the network device.

2. The network device of claim 1, wherein the one or more processors are further configured to:

in response to determining that the network condition satisfies a transmission quality threshold, transmit the erasure encoded version of the requested information to the user device without applying network coding.

3. The network device of claim 1, wherein the one or more processors are further configured to:

in response to determining that the erasure encoded version of the requested information is stored in the cache of the network device, transmit the erasure encoded version of the requested information to the user device.

4. The network device of claim 1, wherein the one or more processors are further configured to:

in response to determining that the erasure encoded version of the requested information is not stored in the memory of the network device;

request that the requested information be transmitted from a data center and receive the requested information from the data center;

determine if the received requested information can be stored in the memory of the network device; and

in response to determining that the received requested information cannot be stored in the memory, transmit the received requested information based on the network condition.

5. The network device of claim 4, wherein transmission of the received requested information based on the network condition comprises transmitting the received requested information via network coding using a butterfly network with at least one multicast session.

6. The network device of claim 4, wherein transmission of the received requested information based on the network condition comprises selecting a type of network coding based on the network condition, wherein the type of network coding includes at least one of:

a deterministic network coding scheme or a random network coding scheme.

7. The network device of claim 4, wherein the one or more processors are further configured to:

in response to determining that the received requested information can be stored in the memory of the network device;

in response to determining that an amount of the received requested information satisfies an erasure encoding threshold, erasure encode the received requested information, store the erasure encoded received requested information in the permanent storage of the network device, and transmit the erasure encoded received requested information based on the network condition.

8. The network device of claim 7, wherein the one or more processors are further configured to:

in response to determining that the amount of the received requested information does not satisfy the erasure encoding threshold;

in response to determining that the erasure encoding threshold can be satisfied within a time duration, erasure encode the received requested information, store the erasure encoded received requested information in the permanent storage of the network device, and transmit the erasure encoded received requested information based on the network condition; and

in response to determining that the erasure encoding threshold cannot be satisfied within the time duration, request that the received requested information be transmitted from the data center.

9. A system comprising the network device of claim 1.

10. A method of transmitting data comprising:

in response to determining that an erasure encoded version of the requested information is stored in a storage external to a network device;

in response to determining that a network condition does not satisfy a transmission quality threshold;

in response to determining that an erasure encoded version of requested information is not stored in a cache of the network device;

in response to determining that a penalty for erasure encoding the requested information exceeds a penalty for retrieving the erasure encoded version of the requested information from the storage external to the network device, retrieving from the storage external to the network device and transmitting the erasure encoded version of the requested information by applying network coding; and

in response to determining that the penalty for erasure encoding the requested information does not exceed the penalty for retrieving the erasure encoded version of the requested information from the storage external to the network device, partially retrieving the requested information from the storage external to the network device, erasure encoding the partially retrieved requested information, and transmitting the produced erasure encoded version of the requested information by applying network coding, wherein the partially retrieved requested information is a subset of the requested information needed to reconstruct the requested information at the network device.

11. The method of claim 10, wherein determining that the penalty for erasure encoding the requested information exceeds the penalty for retrieving the erasure encoded version of the requested information from the storage external to the network device is based on at least one of:

a processing consumption, a response time, a segment quality, a storage capability, a power consumption, or a buffering time.

12. The method of claim 10, wherein the penalty for erasure encoding the requested information is based on processing consumption, and the penalty for retrieving the erasure encoded requested information from the storage external of the network device is based on storage capability.

13. The method of claim 10, wherein the requested information comprises video content.

14. The method of claim 10, wherein transmitting the produced erasure encoded version of the requested information comprises selecting a type of network coding based on a network condition, wherein the type of network coding includes a hybrid network coding scheme.

15. A network device, comprising:

a memory comprising a cache and permanent storage; and

one or more processors configured to receive a request for information from a user device, the one or more processors further configured to;

in response to determining that an erasure encoded version of the requested information is stored in the memory of the network device;

in response to determining that a penalty for erasure encoding the requested information exceeds a penalty for retrieving the erasure encoded version of the requested information from the permanent storage of the network device, retrieve from the permanent storage and transmit the erasure encoded version of the requested information to the user device by applying network coding; and

in response to determining that the penalty for erasure encoding the requested information does not exceed the penalty for retrieving the erasure encoded version of the requested information from the permanent storage of the network device;

partially retrieve the requested information from the permanent storage,

erasure encode the partially retrieved requested information, and

transmit the produced erasure encoded version of the requested information to the user device by applying network coding, wherein the partially retrieved requested information is a subset of the requested information needed to reconstruct the requested information at the network device.

16. The network device of claim 15, wherein the one or more processors are further configured to:

in response to determining that the erasure encoded version of the requested information is not stored in the memory of the network device;

request that the requested information be transmitted from a storage external to the network device and receive the requested information from the storage external to the network device;

in response to determining that an amount of the received requested information satisfies an erasure encoding threshold, erasure encode the received requested information, and store the erasure encoded received requested information in the permanent storage of the network device; and

in response to determining that the amount of the received requested information does not satisfy the erasure encoding threshold;

in response to determining that the erasure encoding threshold can be satisfied within a time duration, erasure encode the received requested information, and store the erasure encoded received requested information in the permanent storage of the network device; and

in response to determining that the erasure encoding threshold cannot be satisfied within the time duration, request that the received requested information be retransmitted from the storage external to the network device.

17. The network device of claim 15, wherein the requested information comprises video content.

18. The network device of claim 15, wherein the penalty for erasure encoding the requested information is based on processing consumption, and the penalty for retrieving the erasure encoded requested information from the permanent storage of the network device is based on storage capability.

19. The network device of claim 15, wherein to transmit the produced erasure encoded version of the requested information comprises transmitting the requested information via network coding using a butterfly network with at least one multicast session.