Methods for transmitting data

• US 5,727,002 A
• Filed: 01/16/1996
• Issued: 03/10/1998
• 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: White, Marc, Miller, C. Kenneth, Cates, Kenneth, Robertson, Kary
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/585,948
• Time in Patent Office: 784 Days
• Field of Search: 371/32, 371/33, 395/200.01, 395/200.04, 395/200.11, 395/200.12
• 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 transmitting data over a communications link, comprising:

(A) setting a maximum data transmission rate to a value less than or equal to an available bandwidth of the communications link;

(B) partitioning the data into a plurality of blocks which each includes a plurality of frames;

(C) transmitting all of the frames to one or more recipients;

(D) during transmission, receiving acknowledgments from the recipients which include indications of frames requiting retransmission; and

(E) repeating steps (C), (D), and (E) for only those times which the acknowledgments indicate require retransmission.

2. A method for quickly and reliably transmitting data to at least two recipients over a communications link, comprising:

(A) setting a maximum data transmission rate to a value less than or equal to an available bandwidth of the communications link;

(B) transmitting a plurality of frames of data over the link to the recipients until all of the plurality of frames have been transmitted;

(C) while performing step (B), receiving acknowledgments from one or more of the recipients, the acknowledgments including indications of frames requiring retransmission; and

(D) after all of the plurality of frames have been transmitted, repeating steps (B), (C), and (D) for only those frames which the acknowledgments indicate require retransmission.

3. The method of claim 2 wherein steps (B), (C), and (D) are repeated, as recited in step (D), until no frames require retransmission.

4. The method of claim 2 wherein steps (B), (C), and (D) are repeated, as recited in step (D), until a predetermined amount of time has passed.

5. A method for transmitting data over a communications link, comprising:

(A) defining a multicast group of recipients to receive the data wherein the group includes a subset of all recipients;

(B) partitioning the data into a plurality of blocks which each includes a plurality of frames;

(C) transmitting all of the frames to the multicast group;

(D) during transmission, receiving acknowledgments from the recipients in the multicast group, the acknowledgements including indications of frames requiring retransmission; and

(E) repeating steps (C), (D), and (E) for only those frames which the acknowledgments indicate require retransmission.

6. A method for quickly and reliably transmitting data to a multicast group of recipients over a communications link, comprising:

(A) defining the multicast group of recipients to receive the data wherein the group includes a subset of all recipients;

(B) transmitting a plurality of frames of data over the link to the multicast group until all of the plurality of frames have been transmitted;

(C) while performing step (B), receiving acknowledgments from one or more of the recipients in the multicast group, the acknowledgments including indications of frames requiring retransmission; and

(D) after all of the plurality of frames have been transmitted, repeating steps (B), (C), and (D) for only those frames which the acknowledgments indicate require retransmission.

7. The method of claim 6 wherein steps (B), (C), and (D) are repeated, as recited in step (D), until no frames require retransmission.

8. The method of claim 6 wherein steps (B), (C), and (D) are repeated, as recited in step (D), until a predetermined amount of time has passed.

9. The method of claim 6 further comprising, prior to step (A), 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.

10. 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, each recipient being connected to the source by a different one of the communication links;

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

(C) while performing step (B), receiving acknowledgments from the recipients determined in step (A), the acknowledgements including indications of frames requiting retransmission;

(D) storing the acknowledgements and the predetermined rate at the source;

(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.

11. The method of claim 10 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 that are connected to the source, and wherein the recipients are members of a multicast group.

12. The method of claim 10 further comprising, alter step (F):

(G) transmitting a plurality of 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 plurality of 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.

13. A method for determining the frame error rates of communication links connecting recipients to a source, comprising:

(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;

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

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

(D) storing the acknowledgements and the predetermined rate at the source; and

(E) determining frame error rate of one or more of the communication links from information stored at the source.

14. The method of claim 13 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 that are connected to the source, and wherein the recipients are members of a multicast group.

15. A method for determining the connectivity between a source and members of a multicast group on a network, comprising:

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.

16. A method for transmitting data, comprising:

(A) transmitting a plurality of frames of data from a source to at least one recipient which is connected to the source by a first communication link having a first capacity;

(B) transmitting a subset of the plurality of frames of the data from the source 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;

(C) transmitting the plurality of frames over the first link and the subset of the plurality of frames over the second link until all of the plurality of frames have been transmitted over the first link;

(D) while performing step (C), receiving acknowledgments from the recipients connected to the source by the first and second links, the acknowledgments including indications of frames requiring retransmission; and

(E) after all of the plurality of frames have been transmitted over the first link, repeating steps (C), (D), and (E) for only those frames which the acknowledgments indicate require retransmission.

17. A method for quickly and reliably transmitting data to a large number of recipients, comprising:

(A) transmitting a plurality of frames of data over a link through a replication point to the recipients until all of the plurality of frames have been transmitted;

(B) while performing step (B), receiving and collecting acknowledgments from all of the recipients at the replication point, the acknowledgments including indications of frames requiring retransmission;

(C) passing on the received and collected acknowledgements from the replication point as an indication of frames requiring retransmission for all of the recipients;

(D) after all of the plurality of frames have been transmitted, repeating steps (A), (B), (C), and (D) for only those frames which the replication point has indicated require retransmission.

18. The method of claim 17 wherein steps (A), (B), (C), and (D) are repeated, as recited in step (D), until no frames require retransmission, and wherein the replication point comprises a router.