In data communications, two modes of data transfer are commonly used. One mode is the datagram delivery mode, which does not guarantee delivery of data being transmitted in this mode. The other mode is the guaranteed delivery mode, which uses means such as acknowledgement messages, timers and retransmission protocols to guarantee delivery of the data transmitted in this mode. The most common protocols associated with these data transfer modes are UDP (User Datagram Protocol) for datagram delivery and TCP (Transmission Control Protocol) for guaranteed delivery.
In data communication systems offering true Point-to-Multipoint (P2MP) data transmission (e.g. satellite communication systems) multicast traffic is often delivered using a non-guaranteed delivery mode. This is quite natural and self-evident, since implementing a guaranteed delivery protocol over a multicast channel has been proven to be quite a challenge. Over the years some methods were suggested for implementing a P2MP guaranteed delivery data transfer mode, yet all these methods had significant shortcomings. Some of these methods involved use of complicated retransmission protocols, others were very chatty (i.e. produced significant volumes of overhead traffic) in both directions of communication, and in many cases these methods did not really guarantee delivery in all scenarios. In fact, none of these methods was commonly accepted for applications for which use of UDP is not good enough.
Two problems have to be solved in order to provide a guaranteed delivery service over a multicast channel. The first is a non-responding destination problem. Even a single non-responding (malfunctioning) destination may cause a data source to retransmit the traffic indefinitely. This may lead to a growing waste of channel capacity, up to a point where the communication channel could be rendered useless due to being totally filled with senseless retransmissions. The second is a network sizing problem. Several retransmission cycles might be required until all destinations receive a transmission and acknowledge its reception. As the number of retransmission cycles required might be unpredictable, it might not be possible to properly size the total capacity (bandwidth) needed for such a communication system. If the capacity is undersized, the system might not function properly. If the capacity is oversized, the system might be too expensive to operate, or the cost of the service might be too high.
Stream Compression is a known, highly efficient data compression technology. Stream Compression is based on monitoring traffic that flows through a source node, identifying repetitions of data blocks (sequences) in the traffic, and building a dictionary for the identified data blocks (sequences), wherein each identified data block is assigned a short identifier (shorter than the data block itself). A copy of the dictionary is then sent by the source node to a destination node, and is saved in a memory at the destination node. After verifying that the dictionary is saved in the destination node, and identifying another repetition of a data block in the traffic that is already included in the dictionary, the source node transmits a short identifier assigned to the data block (according to the dictionary) instead of the data block itself, thus compressing the data, i.e. reducing the volume of data being transmitted. Upon receiving the short identifier, the destination node replaces the short identifier with the corresponding data block in accordance with the saved dictionary, thus decompressing the data and restoring it to its original form.
In order to use Stream Compression in a P2MP system, the dictionary needs to be transmitted to all destination nodes and each destination node must save a copy of the dictionary. Once all destination nodes have copies of the dictionary, the source node can replace, upon detecting an instance of a data block already included in the dictionary in the traffic to be transmitted to the destination nodes, the instance of the data block with a short identifier in accordance with the dictionary. Since each of the destination nodes has a copy of the dictionary, any destination node receiving the short identifier can replace it with the original data block.
In a P2MP system, in order to efficiently transmit a Stream Compression dictionary to a plurality of destination nodes, a multicast transmission has to be used. However, multicast is a non-reliable delivery service. On the other hand, in order to achieve an efficient and fault free operation of the Stream Compression algorithm, it is crucial that the source node does not attempt to compress data blocks that are not included in the copies of the dictionary stored at the destination nodes. The cost of an error (i.e. of an attempt to compress a data block not existing in a copy of the dictionary stored at a destination node) is rather high and could involve any of needing retransmissions, delivering erroneous data to any number of applications at the destination node, and a complete loss of data.
USPTO Backgrounds
USPTO Backgrounds