Data transmission

• US 6,151,696 A
• Filed: 01/23/1998
• Issued: 11/21/2000
• Est. Priority Date: 01/19/1995
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Starburst Communications
• Inventors: Robertson, Kary, White, Marc, Miller, C. Kenneth, Cates, Kenneth
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/012,386
• Time in Patent Office: 1,033 Days
• Field of Search: 714/748, 714/749
• US Class Current: 714/748
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 12/1836 with heterogeneous network architecture
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/115 using a dedicated packet
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 5/1446 of transmission speed
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/24 Negotiation of communication capabilities
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 69/329 : in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04W 28/06 : Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 28/22 : Negotiating communication rate
• CPC Class Codes: H04W 4/06 : Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 8/005 : Discovery of network devices, e.g. terminals

Abstract

A data transmission method quickly and reliably transfers data (e.g., a computer file) from a source to recipients. While the frames are being transmitted, negative acknowledgments from recipients are received by the source. These acknowledgments indicate which frames require retransmission. After all frames have been transmitted out, a retransmission is performed by the source for only those frames which the acknowledgments indicate require retransmission. Additional retransmissions can occur. This multi-pass data transfer technique requires only negative acknowledgements to be sent by the recipients. Features include the ability to set the transmission rate and to define multicast groups. Also, it is possible to determine the capacity of links of unknown capacity using a "multicast network probe" feature of the invention, and to determine the frame error rates of known-capacity links by utilizing the same feature. A "multicast ping" feature of the invention can be used to determine the connectivity between a source and members of a multicast group. "Speed groups" can be set up after determining link capacities, or if they are already known, whereby the recipients connected to the source by the fastest links receive all of the data while slower-link recipients receive only a portion of the data, on the first pass. The number of recipients which can receive the data from the source can be greatly increased by using a "negative acknowledgement collection" scheme whereby "replication points" (preferably routers) collect individual negative acknowledgements and forward them as a unit to the next level.

Claims

1. A method for determining the capacities of communication links connecting recipients to a source, comprising:

(A) determining which recipients are connected to the source by the communication links;

(B) transmitting frames of data from the source to the recipients determined in step (A) at a predetermined rate over the communication links;

(C) receiving acknowledgments from the recipients determined in step (A), the acknowledgments including indications of frames requiring retransmission;

(D) storing, at the source, the acknowledgments and the predetermined rate;

(E) repeating steps (B), (C), (D), and (E) for a different predetermined rate until steps (B), (C), (D), and (E) have been repeated a predetermined number of times; and

(F) determining capacity of one or more of the communication links from information stored at the source.

2. The method of claim 1 wherein step (A) is performed by the source sending a ping request to the recipients over the communication links and the source receiving responses from the recipients.

3. The method of claim 1 further comprising, after step (F):

(G) transmitting frames of other data from the source to at least one of the recipients which is connected to the source by one of the communication links determined in step (F) to have a first capacity; and

(H) transmitting a subset of the frames of other data from the source to at least one other of the recipients which is connected to the source by one of the communication links determined in step (F) to have a second capacity where the first capacity is higher than the second capacity.

4. A method for transmitting data, comprising:

(a) partitioning the data into one or more blocks wherein each block comprises one or more packets and each packet comprises one or more bits, said partitioning comprising setting the number of packets per block to be approximately equal to the maximum number of available bits per packet;

(b) transmitting all of the packets in one of the blocks to one or more recipients;

(c) receiving, from one or more of the recipients, indications of packets in the transmitted block that require retransmission, each indication associated with a different one of the recipients and comprising a bitmap contained within a packet wherein the bitmap comprises a number of bits approximately equal to the maximum number of available bits in the packet and each bit of the bitmap represents a different one of the packets in the transmitted block; and

(d) retransmitting only those packets requiring retransmission.

5. The method of claim 4 further comprising, before step (a), the step of setting a maximum transmission rate to a value less than or equal to an available bandwidth of a communications link over which the data is transmitted.

6. The method of claim 4 wherein step (b) comprises transmitting all of the packets in one of the blocks to at least one recipient which is connected to the source by a first communication link having a first capacity and transmitting a subset of all the packets in one of the blocks to at least one other recipient which is connected to the source by a second communication link having a second capacity where the first capacity is higher than the second capacity.

7. The method of claim 4 wherein step (b) further comprises transmitting through a replication point and wherein the method further comprises:

receiving at the replication point from one or more of the recipients, indications of packets in the transmitted block that require retransmission, each indication associated with a different one of the recipients and comprising a bitmap contained within a packet wherein the bitmap comprises a number of bits approximately equal to the maximum number of available bits in the packet and each bit of the bitmap represents a different one of the packets in the transmitted block;

passing on the indications associated with each of a different one of the recipients from the replication point as an indication of packets in the transmitted block requiring retransmission for all of the recipients; and

retransmitting only those frames which the replication point indicated require retransmission.

8. The method of claim 7 wherein the steps are repeated until no packets require retransmission, and wherein the replication point comprises a router.

9. The method of claim 4 wherein the method for transmitting data is also for determining the capacities of communications links connecting recipients to a source and the method further comprises:

before step (a), determining which recipients are connected to the source by the communications links, each recipient being connected to the source by a different one of the communications links;

in step (c) transmitting the packets at a predetermined rate; and

after step (d), the method further comprises;

(e) storing the indications of packets in the transmitted block that require retransmission and the predetermined rate at the source;

(f) repeating steps (c), (d), (e), and (f) for a different predetermined rate until steps (c), (d), (e), and (f) have been repeated a predetermined number of times; and

(g) determining capacity of one or more of the communication links from information stored at the source.

10. The method of claim 9 wherein determining which recipients are connected to the source is performed by the source sending a ping request to the recipients over the communication links and the source receiving responses from the recipients that are connected to the source, and wherein the recipients are members of a multicast group.

11. The method of claim 9 further comprising, after step (g):

(h) transmitting packets of other data from the source to at least one of the recipients which is connected to the source by one of the communication links determined in step (g) to have a first capacity; and

(i) transmitting a subset of the packets of other data from the source to at least one other of the recipients which is connected to the source by one of the communication links determined in step (g) to have a second capacity where the first capacity is higher than the second capacity.

12. The method of claim 4 wherein the method for transmitting data is for transmitting data to determine the error rates of communication links connecting recipients to a source, and wherein the method further comprises:

before step (a), determining which recipients are connected to the source by the communication links, each recipient being connected to the source by a different one of the communication links;

in step (b), transmitting all of the packets in one of the blocks from the source to the recipients at a predetermined rate; and

after step (d), storing the storing the indications of packets in the transmitted block that require retransmission and the predetermined rate at the source and determining frame error rate of one or more of the communication links from information stored at the source.

13. The method of claim 12 wherein determining which recipients are connected to the source is performed by the source sending a ping request to the recipients over the communication links and the source receiving responses from the recipients that are connected to the source, and wherein the recipients are members of a multicast group.

14. The method of claim 12 wherein step (a) further comprises:

sending a ping request from the source over the network to all of the members of the multicast group;

receiving at the source responses to the ping request from all of the members of the multicast group; and

determining, at the source, roundtrip delay for the ping request to travel to each of the members of the multicast group and back to the source.

15. The method of claim 4 wherein step (c) is accomplished during transmission.

16. The method of claim 15 wherein step (d) further comprises, after all the packets have been transmitted, repeating steps (b), (c), and (d) for only those indications of packets in the transmitted block that require retransmission.

17. The method of claim 16 wherein steps (b), (c), and (d) are repeated, as recited in step (d), until no packets require retransmission.

18. The method of claim 17 wherein steps (b), (c), and (d) are repeated, as recited in step (d), until a predetermined amount of time has passed.

19. The method of claim 4 wherein:

before step (a), the method further comprises defining a multicast group of recipients to receive the data, the multicast group comprising a subset of all recipients; and

step (b) further comprises transmitting all of the packets in one of the blocks to the multicast group.

20. The method of claim 19 wherein step (d) further comprises, after all the packets have been transmitted, repeating steps (b), (c), and (d) for only those packets in the transmitted block that require retransmission.

21. The method of claim 20 wherein steps (b), (c), and (d) are repeated until no packets require retransmission.

22. The method of claim 20 wherein steps (b), (c), and (d) are repeated until a predetermined amount of time has passed.

23. The method of claim 20 further comprising, prior to defining a multicast group, sending a ping request to all recipients and receiving responses from the recipients that are connected to a source of the ping request in order to determine which recipients are available to be in the multicast group.