System and method for transparent electronic data transfer using error correction to facilitate bandwidth-efficient data recovery

• US 6,948,104 B2
• Filed: 06/26/2002
• Issued: 09/20/2005
• Est. Priority Date: 06/26/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: England, Paul, Herley, Cormac
• Primary Examiner(s): DILDINE JR, R STEPHEN
• Application Number:
  US10/183,581
• Publication Number:
  US 20040003333A1
• Time in Patent Office: 1,182 Days
• Field of Search: H03/M01.3/39, 714/712, 714/776
• US Class Current: 714/712
• CPC Class Codes: H04L 1/1812 Hybrid protocols; Hybrid automatic repeat request [HARQ]

Abstract

The invention disclosed herein includes a system and method for electronically transferring data through a communications connection in a transparent manner such that the data transfer does not interfere with other traffic sharing the connection. The invention transfers data using bandwidth of the connection that other traffic are not using. If other traffic desires to use the bandwidth currently being used by the invention, the invention relinquishes the bandwidth to the other traffic and retreats to avoid bandwidth contention. Although a retreat may cause gaps in the data transferred, a key aspect of the invention is that any missing data due to these gaps is recovered easily and in a bandwidth-efficient way using novel error correction and recovery.

Claims

1. A method for transferring pieces of discrete data electronically between a transmission unit and a reception unit, comprising:

requesting the discrete data from the transmission unit using the reception unit;

determining that a first number of discrete data pieces were received and that a second number of discrete date pieces are missing;

obtaining pieces of discrete error correction data from the transmission unit, the number of discrete error correction data pieces equal to the second number of missing discrete data pieces plus a safety value; and

recovering the missing discrete data pieces from the discrete error correction data pieces and the discrete data pieces received.

2. The method as set forth in claim 1, further comprising generating the discrete error correction data pieces by combining probabilistic weights and the discrete data.

3. The method as set forth in claim 1, further comprising constructing a system of equations equal in number to the number of missing discrete data pieces plus the safety value.

4. The method as set forth in claim 3, wherein the system of equations is a linear system of equations.

5. The method as set forth in claim 3, further comprising solving the system of equations to recover the missing discrete data pieces.

6. A method for error correction and recovery in a computer network having a server and a client, comprising:

transmitting a file in the form of N number of data packets from the server to the client in response to a request by the client;

determining that the client did not receive k number of the data packets and did received (N−

k) number of the data packets;

obtaining (k+a safety value) number of error correction packets from the server and

recovering the k number data packets not received from the (k+safety value) number of error correction packets obtained and the (N−

k) number of data packets received.

7. The method as set in claim 6, wherein the safety value is 3% of the k number of data packets not received.

8. A method for electronically transferring data between a client and a server over a fixed bandwidth connection having a plurality of channels, comprising:

providing a policy manager residing on the client to control to which channels the client subscribes;

subscribing to at least one of the plurality of channels to receive discrete data;

determining that not all of the discrete data was received and that there is missing discrete data;

subscribing to at least one of the plurality of channels to receive discrete error correction data, each one of the discrete error correction data containing a unique weighted combination of the discrete data; and

recovering the missing discrete data from the discrete error correction data received.

9. The method as set forth in claim 8, further comprising determining an amount of congestion in the fixed bandwidth connection and subscribing or unsubscribing from the plurality of channels based on the amount of congestion.

10. The method as set forth in claim 8, further comprising determining an amount of congestion based on how much data is lost during a transfer over the plurality of channels.

11. The method as set forth in claim 8, further comprising determining an amount of congestion based on a notification that other sources will be using the bandwidth connection.

12. A computer-readable medium having computer-executable instructions for transferring a data file having discrete data packets to a client computing device through a connection having a bandwidth, comprising:

receiving a multicast of discrete data packets in response to a request from the client computing device;

determining that a number of discrete data packets were not received and defining these discrete data packets not received as missing discrete data packets;

obtaining a multicast of discrete error correction packets, a number of discrete error correction packets obtained being equal to the number of missing discrete data packets plus a safety value; and

recovering each of the missing discrete data packets from the discrete error correction packets obtained;

whereby each of the discrete error correction packets contain a weighted combination of each of the discrete data packets.

13. The computer-readable medium as set forth in claim 12, further comprising constructing a system of equations from the discrete error correction packets.

14. The computer-readable medium as set forth in claim 12, wherein the discrete error correction packets are a linear, weighted combination of discrete data packets.

15. The computer-readable medium as set forth in claim 12, further comprising decomposing the system of equations into a plurality of smaller systems of equations called blocks and obtaining the missing discrete data packets from each one of the blocks.

16. The computer-readable medium as set forth in claim 15, further comprising assigning discrete error correction packets to each one of the blocks such that packet loss is approximately uniform throughout the blocks, rather than having many packet losses occur at a single one of the blocks.

17. The computer-readable medium as set forth in claim 16, further comprising assigning discrete error correction packets to a one of the blocks in a round-robin fashion.

18. A method for transferring a data file to a client computing device using plurality of channels contained within a fixed bandwidth network connection, comprising:

subscribing to at least a portion of the plurality of channels to receive discrete data packets of the data file;

determining a congestion status within the fixed bandwidth network connection, wherein determining a congestion status further comprises having an application on the client computing device send a notification of the applications intent to use at least a portion of the fixed bandwidth network connection;

unsubscribing from at least one of the plurality of channels if the congestion status detects congestion;

subscribing to additional ones of the plurality of channels if the congestion status detects little or no congestion; and

recovering any discrete data packets of the data file lost during data transfer using discrete error correction data packets.

19. A method for transferring a data file to a client computing device using a plurality of channels contained within a fixed bandwidth network connection, comprising:

subscribing to at least a portion of the plurality of channels to receive discrete data packets of the data file;

determining a congestion status within the fixed bandwidth network connection;

unsubscribing from at least one of the plurality of channels if the congestion status detects congestion;

subscribing to additional ones of the plurality of channels if the congestion status detects little or no congestion; and

recovering any discrete data packets of the data file lost during data transfer using discrete error correction data packets;

wherein the discrete error correction data packets are a weighted combination of the discrete data packets.

20. An electronic data transfer system, comprising:

a transmission unit for transmitting over a connection having a fixed bandwidth a data signal containing discrete data and an error correction signal containing discrete error correction data;

a reception unit capable of receiving the data signal and error correction signal; and

an error correction module located on the transmission unit for generating the discrete error correction data, each of the discrete error correction data being a weighted combination of the discrete data.

21. The electronic data transfer system as set forth in claim 20, further comprising a transparent download module located on the reception unit that manages the acquisition of the transmitted data signal and the transmitted error correction signal.

22. The electronic data transfer system as set forth in claim 20, further comprising a data recovery module located on the reception unit that uses the discrete error correction data to obtain any discrete data lost during transmission.

23. The electronic data transfer system as set forth in claim 20, further comprising a policy manager for controlling how the fixed bandwidth is used to receive the data signal and the error correction signal.

24. The electronic data transfer system as set forth in claim 20, further comprising a weights generator in the error correction module that generate probabilistic weight used to create the discrete error correction data.

25. A data transfer system for transferring a data file over a computer network through a fixed bandwidth network connection, comprising:

a data socket on a server computing device for multicasting discrete data packets of the data file;

discrete error correction data packets containing a weighted combination of the discrete data packets;

an error correction socket on the server computing device for multicasting the discrete error correction data packets; and

a transparent download module on a client computing device in communication with the server computing device over the fixed bandwidth network connection, the transparent download module capable of downloading the discrete data packets and the discrete error correction data packets.