IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0768336
(2007-06-26)
|
등록번호 |
US-8214707
(2012-07-03)
|
발명자
/ 주소 |
- Munson, Michelle Christine
- Simu, Serban
|
출원인 / 주소 |
|
대리인 / 주소 |
Schwegman, Lundberg & Woessner, P.A.
|
인용정보 |
피인용 횟수 :
8 인용 특허 :
7 |
초록
▼
This disclosure relates to network data communication. Some embodiments include initiating a network connection between an original source and an ultimate destination, transmitting a block of data from the original source to the ultimate destination on the network, requesting retransmission of lost
This disclosure relates to network data communication. Some embodiments include initiating a network connection between an original source and an ultimate destination, transmitting a block of data from the original source to the ultimate destination on the network, requesting retransmission of lost blocks from the ultimate destination to the source and retransmitting the lost blocks from source to the ultimate destination. These embodiments further include measuring round-trip time of a retransmit request, the round-trip time measured from a time of transmission of a retransmit request from the ultimate destination to a time of reception at the ultimate destination after retransmission from the original source and setting the round-trip time as a minimum retransmission request time for the network connection, wherein the round-trip time includes latencies of the network connection and in data processes at the original source and at the ultimate destination.
대표청구항
▼
1. A method for reliable data transfer over an unreliable network between a sender and a receiver for which the time overhead for resending lost data remains constant for arbitrarily high delay, loss, or reordering of data in transit, and for arbitrarily high transmission speed, the method comprisin
1. A method for reliable data transfer over an unreliable network between a sender and a receiver for which the time overhead for resending lost data remains constant for arbitrarily high delay, loss, or reordering of data in transit, and for arbitrarily high transmission speed, the method comprising: acquiring an injection rate for transmission of data blocks from the sender;sending data blocks sequentially from the sender to the receiver at the injection rate;receiving one or more data blocks at the receiver, each block of the one or more data blocks including an identification number;detecting missing original data blocks based on identification numbers received;detecting missing retransmitted data blocks based on an expected time of receipt as a function of a predicted path round-trip time;determining a path round trip time through a predictive estimation of time to send a retransmission request from the receiver to the sender, retrieve a corresponding data block from a data source at the sender, and transmit the data block to the receiver;storing one or more identification numbers of data blocks lost on the receiver such that a time to add or retrieve a block id from storage does not degrade as a number of lost blocks scales up;sending retransmission requests from the receiver to the sender on a timer based on the predicted path round-trip time so that the sender can retransmit lost data as early as possible to maximize the contiguous receipt of data without re-transmitting too-early data blocks that are only delayed in transit and will eventually reach the receiver;storing retransmission requests for missed data blocks on the sender such that the time to add or retrieve the block id for a block to retransmit does not degrade as the number of retransmission requests increases;sending retransmitted data at the sender at a rate which is commensurate with the injection rate to minimize the storage of retransmission requests at the sender; andsending data for all outstanding retransmission requests first before sending data that has not yet been sent to avoid compounding data loss. 2. The method of claim 1, further comprising performing a Van Jacobson method of predicting path round-trip time. 3. The method of claim 1, further comprising at the receiver storing identification numbers of blocks to be retransmitted in a linear array, where a linear index of each block travels with a request for retransmission to the sender and back with the data block itself. 4. The method of claim 1, further comprising at the sender storing a plurality of identification numbers for blocks needing retransmission in a modified Red Black Tree with substantially constant-time retrieval of block id's sorted by number. 5. The method of claim 1, where retransmission requests travel in packets with a smallest size possible for the injection rate to minimize the time to transmit retransmission requests from the receiver to the sender. 6. The method of claim 1, further comprising using a high watermark calculated as a logarithmic function of the running average of the number of lost blocks in a disk write cache process to maximize the cache hit rate (thus minimizing random access to the disk). 7. The method of claim 1, wherein the sender transmits data blocks out of sequence. 8. The method of claim 1, further comprising the sender acquiring an injection rate for transmission of the data blocks. 9. The method of claim 1, wherein acquiring the injection rate includes acquiring a fixed injection rate. 10. The method of claim 1, wherein acquiring the injection rate includes acquiring a variable injection rate. 11. The method of claim 1, wherein the injection rate is repeatedly recalculated to prioritize the transmission speed relative to a different data transfer running concurrently over an identical network path, and wherein the injection rate is calculated as a proportion of a steady-state transmission rate for one flow of a target protocol used by the different data transfer running concurrently over the identical network path, comprising: a) acquiring a target protocol type, a minimum injection rate, a maximum injection rate and a prioritization factor from a user application;b) periodically re-calculating a new injection rate, comprising: measuring an instantaneous network round-trip time before transmitting and during transfer, and recording a smallest value observed as the base round trip time brtti;measuring the instantaneous network round-trip time during transferring and calculating a smoothed average round-trip time srtti;detecting missed data blocks and calculating an average packet loss probability pi; andcalculating a new rate each time interval (i+1) using: Ratei+1=1/2*(Ratei*BaseAvgi+1+Ratei+α/srtti)Where:BaseAvgi+1=1,ifbrtti+10.2 * brtti, switch to CONGESTED (C) mode Else stay in NC mode In C mode: If srtti decreased from last sample AND drtti <0.5 * brtti, switch to NC mode Else stay in C modeandd) using the calculated injection rate only in a “congested” mode and otherwise use the default injection rate. 18. The method of claim 17, where when in the “congested mode”, the prioritization multiple is set to a small fraction of the targeted protocol, causing the transmission rate to equal an insignificant proportion of the steady-state rate of the target protocol. 19. The method of claim 1, further comprising establishing at least initially the injection rate using automatic detection of the total bandwidth capacity of the transfer path. 20. The method of claim 1, further comprising providing an interface that allows a user or application to select a policy for determining the injection rate, including optionally selecting a targeted protocol type, a constant factor for multiplying the steady-state rate of the targeted protocol, and a maximum or minimum rate to cap the target injection rate. 21. A data transfer system for transfer of data over a network between the sender and the receiver, comprising: means for acquiring an injection rate for transmission of data blocks from the sender;means for sending data blocks sequentially from the sender to the receiver at the injection rate;means for receiving one or more data blocks at the receiver, each block of the one or more data blocks including an identification number;means for detecting missing original data blocks based on identification numbers received;means for detecting missing retransmitted data blocks based on an expected time of receipt as a function of a predicted path round-trip timemeans for determining a path round trip time through a predictive estimation of time to send a retransmission request from the receiver to the sender, retrieve a corresponding data block from a data source at the sender, and transmit the data block to the receiver;means for storing one or more identification numbers of data blocks lost on the receiver such that a time to add or retrieve a block id from storage does not degrade as a number of lost blocks scales up;means for sending retransmission requests from the receiver to the sender on a timer based on the predicted path round-trip time so that the sender can retransmit lost data as early as possible to maximize the contiguous receipt of data without re-transmitting too-early data blocks that are only delayed in transit and will eventually reach the receiver;means for storing retransmission requests for missed data blocks on the sender such that a time to add or retrieve the block id for a block to retransmit does not degrade as the number of retransmission requests increases;means for sending retransmitted data at the sender at a rate which is commensurate with the injection rate to minimize the storage of retransmission requests at the sender; andmeans for sending data for all outstanding retransmission requests first before sending data that has not yet been sent to avoid compounding data loss. 22. The data transfer system of claim 21, further comprising a path round-trip time predictor for accurately predicting round-trip times to identify lost blocks. 23. The data transfer system of claim 22, wherein the path round-trip predictor is adapted to perform Van Jacobson prediction of predicted round-trip time. 24. The data transfer system of claim 21, wherein a modified Red Black Tree with substantially constant-time retrieval is used by the retransmission means to store sequence numbers for the retransmissions sorted by number. 25. The data transfer system of claim 21, further comprising a disk write cache mechanism to minimize random access to a disk, the mechanism using a high watermark calculated as a running average of the size of a retransmission table. 26. The data transfer system of claim 21, further comprising a management interface for reliable and efficient data transfer. 27. A method for data transfer between a sender in communication with a data source and a receiver, the method comprising: dividing the data from the data source into one or more blocks;associating each block of the one or more blocks with a sequential identification number;receiving an injection rate for transmission of the data blocks;receiving retransmission requests from the receiver identifying one or more missing blocks, the retransmission requests based on a predicted path round-trip timeout for identifying missing blocks and transmitted from the receiver commensurate with the injection rate; andtransmitting data at the injection rate, the data comprising lost blocks identified in the retransmission requests followed by remaining blocks of the one or more blocks, the transmitting allowing non-sequential transmission of data blocks. 28. The method of claim 27, wherein receiving the injection rate includes receiving a fixed injection rate. 29. The method of claim 27, wherein receiving the injection rate includes receiving a variable injection rate. 30. The method of claim 27, further comprising storing a plurality of identification numbers in a modified Red Black Tree with substantially constant-time retrieval of retransmissions sorted by number.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.