RATE SENSITIVE PACKET TRANSFER MECHANISM OVER A PEER-TO-PEER NETWORK

• US 20080034108A1
• Filed: 09/26/2007
• Published: 02/07/2008
• Est. Priority Date: 12/29/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Swarmcast, Inc.
• Inventors: Chapweske, Justin
• Granted Patent: US 7,831,718 B2
• Time in Patent Office: Days
• US Class Current: 709/234
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments

Abstract

An apparatus, method and system to improve data transfer across a communications network by employing an acknowledgment independent equalized data packet transfer mechanism on a peer-to-peer basis. The present disclosure teaches how many computers can send data to many other computers, with particularity on a peer-to-peer basis when desired, without requiring acknowledgements of safe receipt by the receiving computer. By aggregating several computers to send data in a collection to a requesting computer, transfer rates may be increased. Further, by not requiring acknowledgment of receipt from the receiving computer, and by treating all data packets with equal utility, the present disclosure teaches a mechanism that reduces file transfer administration bandwidth, increases file transfer scalability on demand, and increases overall network transfer efficiency.

Claims

1-136. -136. (canceled)

137. :

A method for distributing data within a computer network, the method comprising;

storing, at a starting computer, the data;

maintaining a table that stores addresses of computers that can transmit portions of the data;

receiving requests for the data from a first requesting computer and a second requesting computer;

evaluating, in response to receiving the requests, transfer rates of computers that store portions of the data and computers that have requested the data;

generating a first look-up list that indicates those computers that have the best transfer rates among the computers that store portions of the requested data and the computers that have requested the data, wherein the first look-up list indicates that the second requesting computer stores a second portion of the data;

transferring the first look-up list to the first requesting computer;

generating a second look-up list that indicates those computers that have the best transfer rates among the computers that store portions of the data and the computers that have requested the data, wherein the second look-up list that indicates that the first requesting computer stores a first portion of the data;

transferring the second look-up list to the second requesting computer;

delivering the first portion of the data from the starting computer to the first requesting computer;

delivering the second portion of the data to the second requesting computer; and

prior to delivering all of the data to either the first requesting computer or the second requesting computer, exchanging the first portion of the data and the second portion of the data between the first requesting computer and the second requesting computer.

138. :

The method of claim 137, wherein evaluating transfer rates comprises performing a hill-climbing algorithm that evaluates the transfer rates of the computers that store the portions of the data.

139. :

The method of claim 138, wherein applying the hill-climbing algorithm comprises identifying a current set of computers in a series of sets of the computers that store portions of the data or that have requested the data, wherein each set in the series includes a given number of the computers that store portions of the data or that have requested the data, wherein the current set of computers includes ones of the computers that have greater transfer rates than a previous set of computers in the series, and wherein the computers indicated by the table constitute a first set of computers in the series.

140. :

The method of claim 139, wherein identifying a current set of computers comprises;

sending, to computers in the previous set of the computers in the series, requests to identify computers that store portions of the data; and

identifying the given number of computers that have the greatest transfer rates among the computers identified by the computers in the previous set of computers, thereby identifying the computers in the current set of computers.

141. :

A download method for a file in a computer network comprising;

storing, at a starting computer, the file;

receiving a first file download request from a first computer;

downloading, from the starting computer, a first portion of the file to the first computer;

upon downloading the first portion of the file at the first computer, updating a table to record that the first computer received the first portion of the file;

receiving a second download request from a second computer;

evaluating transfer rates of computers that store portions of the file;

generating a look-up list that indicates those computers that store portions of the file that have the best transfer rates, wherein the look-up list indicates that the first computer stores the first portion of the file;

transferring the look-up list to the second computer;

downloading a second portion of the file to the second computer, the first portion containing at least some data of the file not contained within the second portion;

upon downloading the second portion of the file at the second computer, updating the table to record that the second computer received the second portion of the file;

using, with the second computer, the look-up list to identify the first computer as a computer that stores data of the file not contained within the second portion;

issuing a request from the second computer to the first computer for the data of the file not contained within the second portion; and

prior to downloading the entire file at the first computer, communicating, from the first computer to the second computer, at least some of the data of the original file not contained within the second portion.

142. :

The method of claim 141, wherein evaluating transfer rates comprises performing a bill-climbing algorithm that evaluates the transfer rates of the computers that store the portions of the file.

143. :

The method of claim 142, wherein applying the hill-climbing algorithm comprises identifying a current set of computers in a series of sets of the computers that store portions of the file, wherein each set in the series includes a given number of the computers that store portions of the file, wherein the current set of computers includes ones of the computers that store portions of the data or that have requested the data that have greater transfer rates than a previous set of computers in the series, and wherein the computers indicated by the table constitute a first set in the series.

144. :

The method of claim 143, wherein identifying a current set of computers comprises;

sending, to computers in the previous set of the computers, requests to identify computers that store portions of the file; and

identifying the given number of computers that have the greatest transfer rates among the computers identified by the computers in the previous set of computers, thereby identifying the computers in the current set of computers.

145. :

A network transmission apparatus comprising;

a processor;

a memory, communicatively connected to the processor;

a program, stored in the memory, including;

a module to receive a request for data from a requesting computer having one or more peer computers;

a module to identify which of the peer computers have previously requested and downloaded the data;

a module to evaluate transfer rates of the identified peer computers;

a module to generate a look-up list that indicates peer computers among the identified peer computers that have the best transfer rates;

a module to send requests to peer computers indicated by the look-up list to direct the peer computers to send partial portions the data to the requesting computer,

wherein the identified peer computers have downloaded different partial portions of the data, and

wherein the identified peer computers send the partial portions of the data to the requesting computer and complete downloading remaining portions of the requested data.

146. :

The network transmission apparatus of claim 145, wherein the module to evaluate transfer rates comprises a module to perform a hill-climbing algorithm that evaluates the transfer rates of the identified peer computers.

147. :

The network transmission apparatus of claim 146,

wherein the program further includes a module to store a table that indicates an initial set of peer computers that store portions of the data; and

wherein the module to apply the hill-climbing algorithm comprises a module to identify a current set of peer computers in a series of sets of the identified peer computers, wherein each set in the series includes a given number of the identified peer computers, wherein the current set of peer computers includes ones of the identified peer computers that have greater transfer rates than a previous set of peer computers in the series, and wherein the initial set of identified peer computers constitutes a first set in the series.

148. :

The network transmission apparatus of claim 147, wherein the module to identify a current set of peer computers comprises;

a module to send, to peer computers in the previous set of the peer computers in the series, requests to identify peer computers that store portions of the data; and

a module to identify the given number of peer computers that have the greatest transfer rates among the peer computers identified by the peer computers in the previous set of peer computers, thereby identifying the peer computers in the current set of peer computers.

149. :

A method of using a starting computer for transferring data, the method comprising;

receiving a request for the data from a requesting computer;

identifying peer computers that have previously downloaded at least a portion of the data;

evaluating transfer rates of the identified peer computers;

selecting a subset of the identified peer computers that have the greatest transfer rates among the identified peer computers, wherein the peer computers in the subset of the identified peer computers have downloaded different partial portions of the data;

sending requests to the peer computers in the subset of the identified peer computers,

wherein the requests instruct the peer computers to encode the different partial portions of the data at the identified computers, wherein the data is encoded using an acknowledgement independent equalized data packet encoding system, and

wherein the requests further instruct the peer computers to send the encoded different partial portions of the data from at least two different ones of the peer computers to the requesting computer and completing the download of the data at the identified peer computers.

150. :

The method of claim 149, wherein evaluating transfer rates comprises performing a hill-climbing algorithm that evaluates the transfer rates of the identified peer computers.

151. :

The method of claim 150,

wherein the method further comprises storing, on the starting computer, a table that indicates an initial set of peer computers that store portions of the data;

wherein applying the hill-climbing algorithm comprises identifying a current set of peer computers in a series of sets of the identified peer computers, wherein each set in the series includes a given number of the identified peer computers, wherein the current set of peer computers includes ones of the peer computers that have greater transfer rates than a previous set of peer computers in the series, and wherein the initial set of peer computers indicated by the table is a first set in the series.

152. :

The method of claim 151, wherein identifying a current set of peer computers comprises;

sending, to peer computers in the previous set of the peer computers in the series, requests to identify peer computers that store portions of the data; and

identifying the given number of peer computers that have the greatest transfer rates among the peer computers identified by the peer computers in the previous set of peer computers, thereby identifying the peer computers in the current set of peer computers.

153. :

A system for transferring data comprising;

means for receiving a request for the data from a requesting computer;

means for identifying computers that have previously requested and downloaded partial portions of the data;

means for evaluating transfer rates of the identified computers;

means for generating a look-up list that indicates computers among the identified computers that have the best transfer rates;

means to initiate transfer of the partial portions of the data from computers indicated by the look-up list to the requesting computer, wherein the computers indicated by the look-up list have only downloaded different partial portions of the data;

means to independently encode the different partial portions of the data at the identified computers using an acknowledgement independent equalized data packet encoding scheme; and

means to send the encoded data from the identified computers to the requesting computer and complete downloading of the remaining portions of the data.

154. :

The system of claim 153, wherein the means for evaluating transfer rates comprises means for performing a hill-climbing algorithm that evaluates the transfer rates of the identified computers.

155. :

The system of claim 154,

wherein the system further comprises means for storing, on the starting computer a table that indicates an set of computers that store portions of the data; and

wherein the means for applying the hill-climbing algorithm comprises means for identifying a current set of computers in a series of sets of the identified computers, wherein each set in the series includes a given number of the identified computers, wherein the current set of computers includes ones of the identified computers that have greater transfer rates than a previous set of computers in the series, and wherein the initial set of computers indicated by the table is a first set in the series.

156. :

The system of claim 155, wherein the means for identifying the current set of computers comprises;

means for sending, to computers in the previous set of the computers in the series, requests to identify computers that store partial portions of the data; and

means for identifying the given number of computers that have the greatest transfer rates among the computers identified by the computers in the previous set of computers, thereby identifying the computers in the current set of computers.