 |
Claims  |
|
|
What is claimed is:
1. A data distribution system, comprising:
a multiplicity of data processing devices interconnected by data transmission media;
one of said data processing devices including:
memory for storing a message to be transmitted as a stream of data packets to at least one other of said data processing devices;
priority data, stored in said memory, representing a plurality of assigned priority levels p.sub.i for specified portions of said stored message such that all portions of said stored message have respective assigned priority levels; each
priority level p.sub.i indicating that the message portions to which each respective priority level p.sub.i is assigned are to be recoverable whenever at least a p.sub.i fraction of the transmitted data packets are received by a data receiving device;
programmable data processing circuitry;
a data encoding program, executed by said programmable data processing circuitry, for generating an encoded representation of said stored message that includes, for each said portion of said stored message, a level of redundant data L.sub.i
corresponding to the priority level p.sub.i assigned to said portion of said stored message, such that said encoded representation of said stored message includes a plurality of different non-zero levels of redundant data for said different portions of
said stored message;
a data packetizing program that distributes and stores said encoded representation of said stored message in a plurality of data packets such that, for each defined priority level p.sub.i, every possible subset of said data packets having more
than said p.sub.i fraction of said data packets includes sufficient information to reconstruct the portions of said stored message to which said priority level p.sub.i is assigned; and
data transmission apparatus for transmitting said encoded representation of said stored message as a sequence of said data packets representing a single logical message to said at least one other of said data processing devices;
said at least one other of said data processing devices including:
data receiving apparatus for receiving at least a subset of said transmitted data packets;
memory for at least temporarily storing said received data packets;
programmable data processing apparatus; and
a data decoding program, executed by said programmable data processing apparatus, for generating a decoded representation of said received data packets, including decoding different portions of said received data packets in accordance with the
different levels of redundant data included in said encoded representation of said stored message.
2. The data distribution system of claim 1,
said data encoding program including a program portion for embedding data representing said priority data in said encoded representation of said stored message; and
said data decoding program including a program portion for recovering said priority data from said received data stream and for storing said recovered priority data in said memory of said at least one other of said data processing devices.
3. The data distribution system of claim 1,
said data encoding program including a program portion for reordering portions of said encoded representation of said stored message in accordance with said priority data.
4. The data distribution system of claim 3, further including:
a data filter that receives said encoded data steam prior to receipt thereof by a second one of said data processing devices, removes portions of said received encoded data stream corresponding to said portions of said stored message assigned
lowest ones of said priority levels so as to generate a reduced bandwidth data stream, and then transmits said reduced bandwidth data stream to said second one of said data processing devices.
5. The data distribution system of claim 1, further including:
a data filter that receives said encoded data steam prior to receipt thereof by a second one of said data processing devices, removes portions of said received encoded data stream corresponding to said portions of said stored message assigned
lowest ones of said priority levels so as to generate a reduced bandwidth data stream, and then transmits said reduced bandwidth data stream to said second one of said data processing devices.
6. The data distribution system of claim 1, wherein
said encoded representation of said stored message generated by said encoding program includes (A) clear text data comprising said stored message in uncoded form, and (B) encoded redundant data; and
said data decoding program includes a program portion for utilizing said clear text data in said received encoded data stream as said decoded representation of said received data stream and for decoding said encoded redundant data to generate any
portions of said clear text data in said transmitted data stream not received by said at least one other of said data processing devices.
7. The data distribution system of claim 1, wherein said one data processing device includes
network control software, executed by said programmable data processing circuitry, for controlling transmission of said encoded data stream as a sequence of data packets, and
an application program, executed by said programmable data processing circuitry, that calls said data encoding program to encode said stored message, and that passes said encoded representation of said stored message to said network control
software for transmission as said sequence of data packets.
8. The data distribution system of claim 7, wherein said at least one other of said data processing devices includes:
network control software, executed by said programmable data processing apparatus, for controlling receipt of said sequence of data packets and for discarding ones of said data packets in said sequence of data packets that do not meet predefined
validity criteria; and
application software, executed by said programmable data processing apparatus, that calls said data decoding program to decode those of said received sequence of data packets not discarded by said network control software.
9. A method of operating a data distribution system, comprising the steps of:
in a first data processing device:
storing a message to be transmitted as a stream of data packets to at least one other of said data processing devices;
storing priority data representing a plurality of assigned priority levels p.sub.i for specified portions of said stored message such that all portions of said stored message have respective assigned priority levels; each priority level p.sub.i
indicating that the message portions to which each respective priority level p.sub.i is assigned are to be recoverable whenever at least a p.sub.i fraction of the transmitted data packets are received by a data receiving device;
executing a data encoding program to generate an encoded representation of said stored message that includes, for each said portion of said stored message, a level of redundant data corresponding to the priority level assigned to said portion of
said stored message, such that said encoded representation of said stored message includes a plurality of different levels of redundant data for said different portions of said stored message;
distributing and storing said encoded representation of said stored message in a plurality of data packets such that, for each defined priority level p.sub.i, every possible subset of said data packets having more than said p.sub.i fraction of
said data packets includes sufficient information to reconstruct the portions of said stored message to which said priority level p.sub.i is assigned; and
transmitting said encoded representation of said stored message as a sequence of said data packets representing a single logical message to at least one other data processing device; and
in said at least one other data processing device:
receiving at least a subset of said sequence of data packets;
at least temporarily storing said received data packets; and
executing a data decoding program to generate a decoded representation of said received data packets, including decoding different portions of said received data packets in accordance with the different levels of redundant data included in said
stored message.
10. The method of claim 9, further including:
in said first data processor, embedding data representing said priority data in said encoded representation of said stored message; and
in said at least one other data processing device, recovering said priority data from said received data packets and storing said recovered priority data in said at least one other of said data processing devices.
11. The method of claim 9,
in said first data processor, reordering portions of said encoded representation of said stored message in accordance with said priority data.
12. The method of claim 9, further including:
prior to receipt of said encoded data steam by at least a subset of said other data processing devices, removing portions of said transmitted sequence of data packets corresponding to said portions of said stored message assigned lowest ones of
said priority levels so as to generate a reduced bandwidth data stream, and then transmitting said reduced bandwidth data stream to said subset of said other data processing devices.
13. The method of claim 9, further including:
prior to receipt of said encoded data steam by at least a subset of said other data processing devices, removing portions of said received sequence of data packets corresponding to said portions of said stored message assigned lowest ones of said
priority levels so as to generate a reduced bandwidth data stream, and then transmitting said reduced bandwidth data stream to said subset of said other data data processing devices.
14. The method of claim 9, wherein
said encoded representation of said stored message generated by said encoding step includes (A) clear text data comprising said stored message in uncoded form, and (B) encoded redundant data; and
said data decoding program includes a program portion for utilizing said clear text data in said received sequence of data packets as said decoded representation of said received data stream and for decoding said encoded redundant data to
generate any portions of said clear text data in said transmitted data stream not received by said at least one other of said data processing devices.
15. The method of claim 9, including:
in said first data processing device, executing network control software for controlling transmission of said sequence of data packets as a sequence of data packets, and executing an application program that calls said data encoding program to
encode said stored message and that passes said encoded representation of said stored message to said network control software for transmission as said sequence of data packets.
16. The method of claim 15, including, in said at least one other of said data processing devices:
executing network control software to control receipt of said sequence of data packets and to discard ones of said data packets in said sequence of data packets that do not meet predefined validity criteria; and
executing application software that calls said data decoding program to decode those of said received sequence of data packets not discarded by said network control software.
17. A method of encoding and transmitting data, comprising the steps of:
in a first data processing device:
storing a message and priority data representing a plurality of assigned priority levels p.sub.i for specified portions of said message such that all portions of said message have respective assigned priority levels;
encoding said message so as to generate an encoded representation of said message that includes, for each said portion of said message, a level of redundant data corresponding to the priority level assigned to said portion of said message, such
that said encoded representation of said message includes a plurality of different levels of redundant data for said different portions of said message;
distributing and storing said encoded representation of said message in a plurality of packets such that, for each defined priority level p.sub.i, every possible subset of said packets having more than a corresponding fraction of said packets
includes sufficient information to reconstruct the portions of said message to which said priority level p.sub.i is assigned; and
transmitting said plurality of packets having said encoded representation of said message to at least one other data processing device.
18. The method of claim 17, further including:
in said first data processor
embedding data representing said priority data in said encoded representation of said stored message; and
ordering, in said packets, portions of said encoded representation of said stored message in accordance with said priority data.
19. The method of claim 18, further including:
prior to receipt of said packets by at least a subset of said other data processing devices, removing portions of said packets corresponding to said portions of said stored message assigned lowest or highest ones of said priority levels so as to
generate a reduced bandwidth data stream, and then transmitting said reduced bandwidth data stream to said subset of said other data processing devices. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
The present invention relates generally
to computer networks and other computer communications systems that transport data among network subscriber stations, and particularly to computer systems for encoding data so as to enable lossless reconstruction of received data even when a portion of
the data has been lost or corrupted during transmission of the data to the recipient.
BACKGROUND OF THE INVENTION
Most computer based data transmission systems and data storage systems provide at least the ability to detect transmission and storage errors to prevent corrupted data from being accepted. Such error detection systems use "error detection"
encoding techniques. The most commonly used error detection encoding technique makes use of error detection data called cyclic redundancy codes (CRCs), which are widely used due to their ease of computation and reliable error detection.
Erasure resilient codes, which enable lossless data recovery despite loss of information in transmission or storage, are also well known, although somewhat less widely used than error detection codes. For instance, Hamming codes and Reed-Solomon
codes are two well known examples of erasure resilient codes. The corresponding data encoding techniques add redundant information to stored or transmitted data. Reed-Solomon codes are used in many magnetic disk storage systems.
In general, the amount of redundant data added to transmitted or stored data by such redundancy encoding techniques varies from system to system. Adding more redundant data allows lossless recovery of data with higher error or data loss rates
than adding less redundant data, but reduces the transmission or storage efficiency of the associated system.
In real time data transmission systems, it is common to find that some parts of transmitted data are more important than other parts of the transmitted data. We will call a part consisting of equally important transmitted data a "unit". It is
also common that units of different importance that are naturally related to each other are grouped together to constitute what we herein call a "message" or "logical message". Furthermore, it is quite common that the information in the less important
units of a message are of no practical use without the information in the more important units, i.e., the less important units are critically dependent on the more important units.
In some previous systems known to the inventors of the present invention that use loss recovery encoding techniques, a single level of redundancy encoding is used for all data of each message transmitted or stored in each such system. For
instance, known disk drive storage systems each use a single version of the Reed-Solomon encoding technique with a single level of data redundancy. Such systems are inefficient in terms of the total bandwidth required due to using the same level of
importance for all units independent of their importance. Such systems tend to either (A) add less than the ideal amounts of redundancy to critical data due to the cost of adding such redundancy to the entire message, or (B) waste resources by adding
redundancy to the entire message based on the level of redundancy needed for the most critical data.
All other prior systems known to the inventors have partitioned the data stream into units, and redundantly encoded each unit using a single level of redundancy according to its importance. Under some data loss conditions, such systems may
suffer from the loss of the more important units within a message even when the less important dependent units get through.
It is an object of the present invention to allow the flexibility of using multilevel redundancy encoding over the entire message so as to guarantee acquisition of the units within the message in order of importance under any data loss
conditions.
It is a primary object of the present invention to provide systems that efficiently add redundancy data to messages. It is a related object of the present invention to provide systems that encode different portions of a data stream with two or
more different non-zero levels of redundant data such that portions of the data stream denoted as having higher priority are encoded with a higher level of redundant data than portions of the data stream denoted as having lower priority.
Another object of the present invention is to provide a system that accepts priority data regarding specified portions of a specified data stream and automatically scales the level of redundancy with which the various data stream portions are
encoded in accordance with the priority data.
Another object of the present invention is to provide systems that automatically decode and recover received data encoded with multiple levels of redundant data.
Still another object of the present invention is to provide a hierarchical or priority level based data filtering subsystem for use in a data distribution system having one or more data distribution subsystems with insufficient available data
bandwidth to transmit data streams that other portions of the data distribution system can handle. More specifically,, it is an objective of the present invention to provide a data filtering subsystem that automatically transmits only the highest
priority portions of such data streams into low bandwidth portions of the data distribution system.
Another object of the present invention is to simplify network communication protocols by making application programs responsible for redundant data encoding and decoding, while the network level software handles only data transmission on
corrupted data detection through the use of standard CRC codes or the like.
SUMMARY OF THE INVENTION
In summary, the present invention is a data distribution system having a multiplicity of data processing devices interconnected by data transmission media. At least one of the data processing devices transmits data to a plurality of the other
data processing devices in the system.
The transmitting data processing system includes memory for storing data (sometimes called messages) to be transmitted, programmable data processing circuitry, and data transmission apparatus for transmitting an encoded representation of the
stored data as an encoded data stream. Priority data, stored in the memory, represents a plurality of assigned priority levels for specified portions of the stored data such that all portions of the stored data have respective assigned priority levels.
A data encoding program, executed by the programmable data processing circuitry, generates an encoded representation of the stored data that includes, for each portion of the stored data, a level of redundant data corresponding to the priority level
assigned to that portion of the stored data. As a result, the encoded representation of the stored data includes a plurality of different levels of redundant data for the different portions of the stored data.
Each receiving data processing system includes memory for storing received data, programmable data processing circuitry, and data receiving apparatus for receiving at least a subset of the encoded data stream. A data decoding program, executed
by the programmable data processing apparatus, generates a decoded representation of the received data stream. The data decoding program decodes different portions of the received encoded data in accordance with the different levels of redundant data
included in the received data stream.
In a preferred embodiment application programs, rather than network control software, determine the priority levels of the various portions of the data to be transmitted. The application programs call data encoding procedures so as to encode
data with erasure resilient codes at redundancy levels associated with the priority levels assigned to the data portions by the application programs. The encoded representation of the data is called an erasure resilient code. By making application
programs responsible for data redundancy encoding and decoding, network protocols and systems are simplified.
The data encoding procedures embed data representing the priority data in the transmitted data stream. The data decoding program in the receiving data processing systems recovers the priority data from the received data stream and stores the
recovered priority data in its memory.
In some preferred embodiments, the data encoding program in the transmitting data processing system reorders, within a single message, portions of the encoded representation of the message in accordance with the priority data. The receiving data
processing systems re-map the received data back into the data's original order.
One reason for reordering the transmitted data is to facilitate truncation of the transmitted data by a data filter in a hierarchical data transmission system. The data filter receives the transmitted encoded data stream prior to its receipt by
the receiving data processing devices, removes portions of the received encoded data stream corresponding to the portions of the data assigned the lowest priority level(s) so as to generate a reduced bandwidth data stream, and then transmits the reduced
bandwidth data stream to the receiving data processing devices.
Different embodiments of the present invention use different erasure resilient codes for encoding the data to be transmitted. Some erasure resilient codes, such as Reed Solomon codes and the XOR based erasure resilient code in one of the
preferred embodiments, include (A) the data or message to be transmitted in uncoded or "clear text" form, and (B) encoded redundant data. This has the advantage that when all the transmitted data is received, virtually no computational resources are
required to recover the original data. The only computation resources used in those circumstances are the computational resources required to verify error free receipt of the data and to filter out the encoded redundant data. When a portion of the
transmitted data is not received, the data decoding program decodes the encoded redundant data portion of the received data to generate those portions of the data in the transmitted data stream not received.
In other preferred embodiments, the erasure resilient code used to transmit the data in a message consists entirely of data in an encoded representation.
BRIEF DESCRIPTION OF THE DRAWINGS
Additional objects and features of the invention will be more readily apparent from the following detailed description and appended claims when taken in conjunction with the drawings, in which:
FIG. 1 is a block diagram of a data distribution system for transmitting real time data, such as a video program, from transmitting workstations to receiving workstations.
FIG. 2 is a block diagram of a data transmitting workstation in accordance with the present invention.
FIG. 3 is a block diagram of a data receiving workstation in accordance with the present invention.
FIG. 4 is a block diagram of data structures for storing a message and for storing data packets containing an encoded representation of the message.
FIG. 5A is a block diagram of mapping information embedded in the data packets of FIG. 4. FIG. 5B is a block diagram showing how data packets can be prepared by a transmitting station for truncation by downstream data filters.
FIG. 6 is a block diagram of the data packets shown in FIG. 4 in accordance with a first preferred embodiment of the present invention.
FIG. 7 is a block diagram of the data packets shown in FIG. 4 in accordance with a second preferred embodiment of the present invention.
FIG. 8 depicts a flow chart of the data encoding procedure used in the first preferred embodiment of the present invention.
FIG. 9 depicts a flow chart of the data decoding procedure used in the first preferred embodiment of the present invention.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
Referring to FIG. 1, there is shown a data distribution system 100 having a multiplicity of data processing devices 102, 106, 110 interconnected by data transmission media 104, 108. At least one of the data processing devices 102 transmits data
to a plurality of the other data processing devices 106, 110 in the system.
For convenience, the data processing devices 102, 106, 110 are herein sometimes called workstations, subscriber stations or subscriber workstations. These terms are interchangeable.
For instance, the data distribution system 100 could be a wide area computer network that incorporates a number of local area networks. Such local area networks can be interconnected via one or more "network bridges" 109. For the purposes of
explaining the present invention, it will be assumed that the transmitting data processing system 102 is transmitting real time video images in the MPEG2 data format to subscriber stations 106, 110 having two distinct data bandwidth receiving
capabilities.
For instance, the subscriber stations 106 might be set top receivers for high definition televisions, while subscriber stations 110 might be set top receivers for standard televisions. In such a system, network bridge 109 would filter out
portions of the high definition television data stream that are unusable by the set top converters 110 for standard televisions. When high and low bandwidth devices are intermixed, but all connected to a high bandwidth transmission medium, similar
filtering can be performed at those of the subscriber stations 106, 110 that cannot process a portion of the transmitted information, by simply not processing those portions of the received data stream. Furthermore, the transmitting station 102 may also
perform a data filtering function, by transmitting out only the most important information when its outgoing data link is congested.
In another embodiment, subscriber stations 106, 110 are computer work stations that, among other tasks, can receive real time video transmissions. While workstations 106 have a high bandwidth connection to workstation 102 while workstations 110
have a lower bandwidth connection to workstation 102.
Referring to FIG. 2, the transmitting data processing system 102 is typically a desk top workstation computer (or a set top signal converter for a television) that includes memory 120 for storing data 122 to be transmitted, programmable data
processing circuitry (CPU) 124, and data transmission apparatus 128 (e.g., a network interface card) for transmitting an encoded representation of the stored data as an encoded data stream. For convenience, the stored data 122 will sometimes herein be
called the "message" that is to be transmitted.
Priority data 130, stored in the memory 120, represents a plurality of assigned priority levels for specified portions of the message 122 such that all portions of the message have respective assigned priority levels. A data encoding program
132, executed by the programmable data processing circuitry 124, generates an encoded message 134 representation of the message 122 that includes, for each portion of the message, a level of redundant data corresponding to the priority level assigned to
that portion of the message. As a result, the encoded representation 134 of the stored message 122 includes a plurality of different non-zero levels of redundant data for the different portions of the stored message 122.
The transmitting data processing system 102 preferably includes a user interface 135 having a keyboard 136, pointing device 138, display device 140 and audio speaker 142.
The transmitting data processing system 102 will preferably include apparatus for receiving and decoding messages sent by other network subscribers. The data receiver will typically be the same network interface 128 used for transmitting encoded
data. Received encoded messages 150 are processed by a decoder program 152, described in more detail below, to produce a decoded message file 154.
In the preferred embodiment, when the network subscriber 102 is a computer workstation, network control software 156 handles the transmission and receipt of data packets via the network interface 128, including adding a CRC error detection value
to each data packet to be transmitted and checking the CRC values on received data packets. When a received data packet's CRC value does not match the CRC value computed by the network control software 156 for the received data packet, the received data
packet is discarded because its contents have been corrupted.
Application programs 158 generate or otherwise provide the data to be transmitted by the network, and are also responsible for processing received data packets once the data packets have been validated via the above mentioned CRC check. In the
preferred embodiment, unlike prior art systems utilizing erasure resilient codes, application programs 158 are responsible for the encoding and decoding of the erasure resilient codes instead of the network control software 156. Primary reasons for
making application programs responsible for erasure resilient encoding and decoding are A) the information needed to determine redundancy priority levels for the various different portions of the transmitted data is typically resident in the application
programs, and B) simplification of the network control software makes the transmission network more efficient and manageable.
Referring to FIG. 3, in the preferred embodiment the receiving data processing systems 106, 110 are also typically desk top workstation computers or personal computers that include memory 120 for storing received encoded messages 150,
programmable data processing circuitry CPU) 160, and data receiving apparatus 162 (e.g., a network interface card or satellite receiving disk) for transmitting an encoded representation of the stored data as an encoded data stream. As mentioned above,
the receiving data processing systems 106, 110 may also be set top receivers for televisions or other similar devices.
Network control software 156 initially processes received data packets by comparing the CRC value in each received data packets with a CRC value computed for the data packet by the network control software, and discarding data packets whose
embedded and computed CRC values do not match. The received portions of the message that pass the CRC test are then passed to an application 158, which in turn calls a data decoding program 152.
The data decoding program 152, executed by the programmable data processing circuitry 160, generates a decoded message 154. The data decoding program 152 decodes different portions of the received encoded data in accordance with the different
levels of redundant data included in the received data stream.
When the receiving data processing system 106 are television "set top" receivers, the receiving data processing system 106 will typically have no user interface 135 other than a television set or other display and audio output device and a remote
controller or the like for inputting user commands. In such embodiments the keyboard 136 and pointing device 138 will typically be replaced by a remote control device and an infrared signal receiver.
Referring to FIG. 4, for purposes of explaining the operation of the present invention, we will assume that the data 122 to be transmitted is divided into three blocks 170-1, 170-2 and 170-3 of data, having respective lengths of b1, b2 and b3.
For instance, if the message is the MPEG data for a certain period of time, the message would include I-frames, P-frames and B-frames, each of which would be treated as a separate data block.
The three blocks 170 have separately assigned fractional priority values p1, p2, p3. For an MPEG message, suitable fractional priorities might be 0.5, 0.75 and 0.9 for I-frames. P-frames and B-frames, respectively. A "fractional priority
value" is defined as follows: the data is to be encoded with redundant data such that if at least a p1 fraction of the transmitted data is received, then the data in the first block 170-1 will be recovered. For instance, if p1 were equal to 0.5, then
the data would be encoded so that only half the transmitted data would need to be received to be able to recover the data in data block 170-1.
Note that a low fractional priority value is indicative of important data having a high priority level, while a high fractional priority value is indicative of less important data having a lower priority level. For convenience, this document
will sometimes refer to "high priority levels" and "low priority levels," meaning relatively low and relatively high fractional priority levels, respectively.
It is a feature of the present invention that transmitted data can be divided into an unrestricted number of distinct blocks, and that each such block can have a distinct assigned priority level. Three blocks and three priority levels are used
herein only to simplify the explanation of the invention.
The encoded data 134 consists, in one preferred embodiment, of a number of data packets 172-0, 172-1, . . . , 172-n-1. Each packet 172 includes, at a minimum, a packet ID 174, a portion of the erasure resilient code 176 (which may include
uncoded clear text data) for the message, and a packet CRC code 177. In the preferred embodiments all or some of the transmitted data packets 170 also include "mapping information" 178.
As indicated above, a logical message is transmitted as a set of data packets, and it is quite possible for the data packets for a single message to be transmitted to a subscriber over multiple transmission routes. In other words, some data
packets within a message may take a longer or different transmission path than other packets. As a result, the data packets may arrive at a subscriber station in a different order than the order in which they were transmitted. The packet ID 174
embedded in each transmitted data packet allows the receiving subscriber stations to reassemble the received data packets in their proper order, regardless of the order in which they are received.
Referring to FIG. 5A, in some preferred embodiments the Mapping Information 178 contains data that enables the receiving devices to determine block lengths b1 to b3, the fractional priority values p1 to p3 associated with the transmitted data,
and remapped position data rp1 to rp3.
It is sometimes desirable to order the data within the encoded data packets 134 in a different order from that of the original data 122. One reason for reordering the transmitted data is to facilitate truncation of the transmitted data by a data
filter. The data filter receives the transmitted encoded data steam prior to its receipt by the receiving data processing devices, removes portions of the received encoded data stream corresponding to the portions of the data assigned the lowest
priority level(s) so as to generate a reduced bandwidth data stream, and then transmits the reduced bandwidth data stream to the receiving data processing devices.
For instance, data filtering based on priority levels may be required when the transmitted data is sent to receiving devices or media with limited data bandwidth. More specifically, lower priority data might be deleted from the transmitted
encoded data by a network bridge 109 (see FIG. 1) if the bandwidth of the receiving local area network is insufficient to handle the full bandwidth of the transmitted data. In such a system, it will sometimes be preferable to order the data within the
transmitted data to simplify the data truncation task of the network bridge 109.
The remapped position data rp1, rp2, rp3 indicates the relative position of each of the source data blocks 170-1, 170-2, 170-3 located within the encoded data 134.
In some preferred embodiments of the present invention, only one type of data (e.g., MPEG2 data) is transmitted, and priority values are permanently assigned to that one type of data. In such embodiments, the mapping information 178 that is
embedded in the transmitted data packets needs to include only block size information. In other embodiments the priority values are updated occasionally, but not with every data transmission.
When data packets within a data stream are truncated so as to filter out a portion of the data stream, the CRC values of those packets will typically require recomputation. Alternately, "partial packet CRC" values can be pre-computed by the
transmitting workstation 102 and inserted in the original data packets at the point the packets will be truncated by downstream filters so as to avoid the need for the data stream filtering devices to compute new CRC values.
Referring to FIG. 5B, yet another alternative way to handle the need for accurate CRC values in truncated data packets is to break each data packet 172 into two or more "sub-packets" 180, each having its own "sub-packet ID" and its own CRC. In
the example shown in FIG. 5B, each data packet is divided into three sub-packets 180-1, 180-2 and 180-3, which may be transmitted by the communication network either together as a group, or as separate data packets. If the subpackets are transmitted
separately, this results in the transmission of more data packets, but reassembly of the sub-packets into their proper order at the receiving subscriber stations is easy. On the other hand, transmission of the sub-packets together as a single data
packet is useful in that it simplifies the data truncation task of data stream filters without requiring sub-packet reassembly by the receiving subscriber stations.
Referring to FIG. 6, in some preferred embodiments all the data in the encoded representation of the stored data is in encoded form. In other words, the erasure resilient code 134 portion of the transmitted data packets 170 does not include any
"clear text data" suitable for use by the recipients without decoding.
Referring to FIG. 7, in other preferred embodiments the encoded representation of the stored data generated by the encoding program includes (A) the stored data in decoded form, and (B) encoded redundant data. This has the advantage that when
all the transmitted data is received, virtually no computational resources are required to recover the original data. The only computation resources used in those circumstances are the computational resources required to verify error free receipt of the
data and to filter out the encoded redundant data. When a portion of the transmitted data is not received, the data decoding program decodes the encoded redundant data portion of the received data to generate those portions of the data in the
transmitted data stream not received.
FIG. 8 shows a flow chart of a first preferred multiple level redundancy encoding procedure 132. The procedure receives a vector representing the block lengths of the data to be encoded and a vector of fractional priority values (step 200).
Then it determines the total number t of data packets needed to store and transmit the data (step 202). This is determined by dividing each block length b.sub.i by its fractional priority p.sub.i, to determine the length of the data block after it has
been encoded (b.sub.i /p.sub.i). The computed encoded block lengths are then summed, and the resulting value is divided by n, which represents the space (i.e., the number of words) available in each data packet to store encoded message data.
Next, at step 204, the data blocks are optionally reordered so that the data blocks having highest priority are processed first and positioned first within the data packets 170. While this is not necessary, some details of the main data encoding
step (210) would require modification if the data blocks are not in "highest to lowest" priority order. In addition, the mapping information 178 is encoded to form encoding mapping information 179 and then stored in the data packets at step 204. In the
preferred embodiment, the mapping information 178 is encoded using the same level of redundancy encoding as that used for the highest priority data block in the message. In addition, the encoded mapping information 179 in every data packet includes, in
decoded form, one or more words that indicate (A) the total length of the encoded mapping information, (B) the number of data packets used to transmit the message, and (C) the fractional priority level p0 used to encode the mapping information. From
those pieces of information and from a sufficient number of received packets the mapping information 178 can be decoded and determined by receiving stations.
At step 206 some loop counters and pointers are initialized. Step 210 is the main data encoding step, and is repeated for each data block in the message to be sent.
| | |
