1. Field of the Invention
The present invention relates to a method for minimizing the number of packets that need to be retransmitted in a two-way communication system having forward and back communication channels.
2. Description of Related Art
Computer users often transfer files of data, usually large, multimedia data files containing, for example, digitized music, still images or moving images, between a transmitter computer host and one or more subscriber (remote) receiver computers of a communication system. The communication system is generally referred to as a xe2x80x9cone-to-manyxe2x80x9d communication system, and may be, for example, a two-way satellite broadcast system or a computer network, such as the Internet. It is highly desirable that these large files are transferred error-free despite the effects of various types of noise interfering with the transmitted signal.
In general, the data bits or symbols (such as bytes) of the file to be transmitted are most likely to be organized into larger groups called packets. When a file is sent, header packets preceding the information packets are sent. Those header packets contain the address and control information to ensure that the following packets are received by the addressed subscriber computers. Moreover, each packet itself includes header bytes that indicate, inter alia, to which file the packet belongs and the position of the packet within that file. The remaining bytes of the packet are the body which includes the informational data, such as compressed video data. For example, a packet may be 4,096 bytes long, wherein the header portion is the first 16 bytes, and the body portion is the remaining 4,080 bytes. A file is thus transmitted over the forward channel of a two-way communication channel as a sequence of packets.
Occasionally, a subscriber computer does not receive all of the transmitted packets successfully. In particular, some of the transmitted packets may be identified as xe2x80x9clostxe2x80x9d, or as uncorrectably erroneous (xe2x80x9cbadxe2x80x9d), by the subscriber computer because of various types of noise interfering with the transmitted signal (hereinafter, for brevity, both the lost and bad packets will be referred to as xe2x80x9clostxe2x80x9d). For example, a host computer may send a packetized file to two subscriber computers A and B. For any number of reasons, the transmitted packets may experience different degrees and types of noise in the respective communication channels between the host computer and the subscriber computers A and B. Because of this, subscriber computer A may lose 20% of the transmitted packets, while subscriber computer B may lose only 5% of the transmitted packets. Generally, there may be hundreds or thousands of remote subscriber computers, with each subscriber computer possibly losing one or more of the transmitted packets due to noise between it and the transmitting host computer.
To correct for these packet losses, it is possible to retransmit over the forward channel the packets of the entire file to all of the subscriber computers. However, this method is costly, wastes time and bandwidth, and prevents the communication system from being used for other purposes. It is especially wasteful since most subscribers will lose only a few packets out of the entire file, and furthermore, there is no guarantee that the retransmitted packets will not also be lost.
Instead, back channels may be respectively provided between each subscriber computer and the host computer so that information regarding which packets were successfully received and which were lost can be sent back from the subscriber computers to the host computer. Using this information, the host computer is able to retransmit over the forward channel only the lost packets to the subscriber computers. Each back channel usually takes the form of a modem and telephone line, or may be part of a standard computer network, such as a LAN or the Internet. The back channel can also be linked through a satellite, although this may be more expensive. Other types of back channels may also be used, as will be appreciated by one skilled in the art.
Retransmission of lost packets in this fashion also requires a retransmission protocol between the host computer and the subscriber computers to determine when, and under what conditions, the retransmission is to be performed. For example, retransmission may be performed periodically, regardless of whether or not the host computer has received lost packet information from all of the subscriber computers. Alternatively, the host computer may actively seek out the lost packet information from each and every subscriber computer by polling them, and retransmit only after the polling has been completed. Of course, other retransmission protocols may be used, as will be appreciated by one skilled in the art.
In a simple transmission and retransmission approach, the host computer transmits over the forward channel the packets of a file. The host computer also saves these packets for possible retransmission. Upon reception, each subscriber computer creates a list of which packets were successfully received and which packets were lost, and sends that list to the host computer over its back channel. From these lists, the host computer accumulates a set of all of the lost packets required by the subscriber computers (none of the lost packets are repeated in this set). The host computer then retransmits over the forward channel the set of accumulated lost packets, and assuming the retransmitted packets are successfully received, the subscriber computers are able to successfully reconstruct the file.
However, this approach becomes increasingly inefficient for large numbers of subscriber computers, because each subscriber computer generally loses packets different from those lost by the other subscriber computers, thus causing the number of retransmitted packets to increase dramatically. In fact, the number of retransmission packets may begin to approach the entire number of originally transmitted packets, thus causing this approach to become as inefficient as retransmission without using back channels (in which the entire file is retransmitted). Furthermore, this approach has no way to account for the possible loss of some of the retransmitted packets on retransmission.
It would thus be desirable to provide a method that overcomes the above-described problems, especially in the case of a large number of subscriber computers communicating with a host computer. In particular, a method is provided that reduces the total number of retransmitted packets. Another method is provided that accounts for the likelihood that some of the retransmitted packets may be lost on retransmission, and thus increases the number of retransmitted packets accordingly.