Note: Descriptions are shown in the official language in which they were submitted.
~ '''O91/1~289 2 1 ~ O 0 3 ~ PCT/US90/07472
._
TRA~SMITTING F~NcoDF~n DATA ON UNRFT~I~RT~ NFTWORK~
~ckground of the Invent;on
This invention relates to communication systems
and in particular to the application of data encoding
techniques, such as data compression, to unreliable
networks.
Packet-switched digital co nication networks
allow digital systems to communicate with each other. They
typically include several nodes which may transmit, receive
or forward data. ~ata to be transmitted are loaded into
frames, along with a destination address which determines
which node is to receive the frame. The frames are sent
from one node to another either directly or via a series of
intermediate nodes. The comm~n;cation channel established
between nodes in a network is known as a virtual circuit.
Packet-switched data may be transmitted over a
reliable network, in which error recovery is built into the
network. For example, an error checking system, such as
CRC error checking, may be provided ~etween the nodes of a
network. In this arrangement, whenever a receiving node
detects an error in a received frame, it requests
retransmission of that frame from the sending node.
In some protocols, the sender retransmits every
frame that has been transmitted since the last error upon
discovery of that error. This type of protocol is called
"go-back-n". Alternatively, the sender may simply
retransmit those frames that are in error. This type of
protocol is called ~'selective retransmission."
On some networks, especially those with low
error rates, no error recovery is included. On these
"unreliable networks", the end systems are left to recover
from any errors over the network as they see fit.
Typically, the receiving end system will use a reverse
channel to acknowledge the reception of frames to the
sending end system. Frames that are not received are not
W09lt10289 2 1 ~ O 0 3 9 PCT/US90/07472
acknowledged, and frames that are received with errors
initiate error recovery procedures. The frames are then
retransmitted by the sender. In these "unreliable
networks", increased data throughput is often achieved by
having the network nodes simply drop frames when errors are
~ detected, without attempting error recovery. The end
systems have the task of detecting the loss of frames, and
requesting retransmission.
It is advantageous to perform data compression
on data that are sent through the network, as this reduces
the amount of data to be sent through the network. This is
usually accomplished by sending the data over a reliable
network, i.e., one in which error recovery is provided
inside of the data compression encoding and decoding.
Other forms of data encoding are also useful,
such as scrambling or encryption. These operations are
also usually accomplished by sending the encoded data over
a reliable network.
Many powerful data encoding methods need to
remain synchronized. This synchronization can be broken
when a frame is received containing errors or is lost
altogether. Adaptive and variable field length data
encoding are two methods that require synchronization. In
adaptive compression, the vocabularies used to encode and
decode a compressed frame change as a function of the data
being sent. The vocabulary at the encoder and the
vocabulary at the decoder must remain synchronized. An
error will usually affect the vocabulary of the receiver
and cause it to decode all subsequent frames erroneously.
In variable field length systems, errors may cause data to
be interpreted using different field lengths than those
with which the data were intended to be decoded. These
data encoding methods will usually continue to operate
erroneously if they are not resynchronized and will often
tend to progress to a state where all data are received
erroneously.
Q 3 ~
, ~.~
The resynchronization of the decoder can be achieved by resetting each
of them to the same predetermined state. This predetermined state could be
fixed or could change with time.
SummarY of the Invention
In accordance with the present invention, there is provided a method for
transmitting encoded data across unreliable networks. The encoding is of a type
in which encoding an decoding are synchronized. The data is encoded using
a data encoding method. The encoded data is ll~lsnlilled across the unreliable
network. The data is then received and decoded. At intervals, the encoding
method is periodically resynchronized at frame boundaries.
In a preferred embodiment, any errors introduced by the unreliable
network is detected, and the encoding method is reset upon the detection of
errors.
The invention has the advantage of allowing synchronized encoding of
data over an unreliable channel in an essentially transparent fashion. This is
done despite the tendency of error propagation in synchronized data encoding
methods. In fact, the invention takes advantage of this tendency in order to
provide detection of out-of-
. ~
WO91/10289 2 1 ~ O 0 3 ~ PCT/~iS90/074,2
-- 4
sequence frames. Hence, in the case of data compression,
an unreliable network can be provided with enhanced
throughput. Data compression and other methods may thus be
used without the expense of a network error recovery system
in addition to what the end systems are already using.
Other advantages and features of the invention
will become apparent from the following description of the
preferred embodiment, and from the claims.
DescrLption of the Preferred Fmho~im~nt
Fig. l is a block diagram of a prior art
network.
Fig. 2 is a block diagram of a prior art data
encoding method as applied to the network of Fig. l.
Fig. 3 is a block diagram of the data encoding
method of the invention.
Fig. 4 is a schematic outline of an illustrative
comml1nication network as is known in the art.
Fig. 5 is a block diagram of a full-duplex
encoder-decoder pair.
Fig. 6 is a flow chart of the data encoding
reset protocol phases. -
Fig. 7 is a chart of an error being correctedusing the data encoding reset protocol of the invention and
its effect on the data frames.
Fig. 8 is a chart of an error being corrected
where the reset request is lost due to an error on the
reverse channel.
Fig. 9 is a diagram illustrating the propagation
of frames through a channel using periodic reset.
In a simple reliable network (Fig. l), the
network, itself, incorporates error recovery. End system 6
(source S) applies data to network 8, which is made
reliable ~y elements of procedure 13, 17 and error
detection blocks 14, 20, the operation of which is well
known in the art. Error detection information, such as a
~091/10289 2 1 8 0 0 3 ~ PCT/US90/07472
- 5 -
cyclic redundancy code (CRC), is added to the encoded data
by error detection code generator 14. The resulting data
are transmitted across channel 16, which may be a virtual
circuit in a network, such as the one indicated by X or Y
in the network shown schematically in Fig. 4. Within this
channel 16, errors are randomly introduced in the data.
These errors may arise from a variety of sources, such as
crosstalk, induced spikes, or power line surges.
Errors introduced in transmitting the data over
the channel 16 are detected (using the error detection
information) by error detector 20, which, in conjunction
with the receiving end's elements of procedure 17, causes a
request for retransmission to be sent to the transmitting
end's elements of procedure 13 over a reverse channel (not
shown in Fig. 1). In some networks, the elements of
procedure and error recovery blocks shown in Fig. 1 are
repeated at numerous nodes along the virtual circuit (Fig.
4).
If no errors are detected, the received data are
passed on to the end system 6 at the destination. The
source 10 may thus send data and expect them to arrive at
the destination 24 with no errors, though some of the data
may have to be retransmitted between network nodes during
this process.
Referring to Fig. 2, the usual prior art method
of incorporating data compression into a network system is
to add an encoder 12 before the transmission end's elements
of procedure 13, and to add a decoder 22 after the
receiving end's elements of procedure 17.
In this approach, the source 10 applies data to
be transmitted to the encoder 12 which encodes these data
using a data encoding algorithm. This algorithm may be a
data compression algorithm such as an adaptive data
compression algorithm, or it may be another type of
algorithm, such as an encryption algorithm. These methods
of data encoding are well known in the art.
WO91/l0289 2 1 8 0 0 3 q PCTt~S90/07~72
The encoded data are passed on to the
transmitting end's elements of procedure 13 and error
detection code generator 14 which adds error detection
information and transmits the data over channel 16 where
errors may be introduced.
Error detector 20 receives the transmitted data
and checks them for errors. If errors are detected, the
receiving end's elements of procedure 17 will request
retransmission of the data as described above. Thus, the
decoder 22 will always receive data free of channel errors,
will always remain in synchronization with the encoder 12,
and will decode these data and pass them on to the
destination 24.
The preferred embodiment of the invention is
structured differently, as may be seen in Fig. 3. The
elements of procedure 13, 17 and error detection blocks 14,
20 are moved outside of the network system 8, and reside in
the end systems 6. The data compression encoder 12 and
decoder 22 remain within the network system 8, but error
detection blocks lS, 21 have been added outside of the
encoder and decoder. A second error detection code
generator 15 (e.g., a CRC generator) is ahead of encoder 12
at the transmitting end. A second error detector 21 is
downstream of the decoder 22.
Within the transmitting end system 6, source 10
applies data to the transmitting end's elements of
procedure 13, which passes the data on to the error
detection code generator 14, which, in turn, introduces
error detection information into the data.
The data are then passed to the network system
8, where a second error detectior code generator 15,'this
one, a part of the encoding system, introduces further
error detection information into the data. The data are
then encoded in encoder 12 and transmitted over channel 16
At the receiving end, the data are decoded in
decoder 22. Errors introduced on channel 16 may be present
WO91/10289 ~ 2 1 8 0 0 3 9 PCT~US90/~7472
-- 7
in the data and, if so, the decoded data will also contain
errors. In using data encoding methods that require
synchronization, errors will typically cause more errors,
which will, in turn, cause further errors, and very quickly
the decoder will be generating a stream of completely
erroneous data. In the case of adaptive data compression,
this arises because the vocabulary used to decode the data
is dependent on the data themselves, and once it is flawed
it decodes the data incorrectly. This erroneously decoded
data leads to a more flawed vocabulary, which leads to more
erroneously decoded data, and so on. It should also be
noted that, because the data compression is continuous
across frames ~i.e. the vocabulary is not reset for each
frame), missing or out-of-sequence frames will also be
decoded incorrectly.
Received data is also supplied to error detector
20 in the end system 6 at the destination, which works in
conjunction with the receiving end's elements of procedure
17 to require retransmission of erroneous frames, in the
conventional way. ~owever, before retransmission may
occur, the data encoding method must be reset, otherwise
the retransmitted frames would be decoded erroneously. To
this end, decoding error detector 21 sends a reset request
to encoder 12 over a reverse channel.
The relationship between a channel and its
reverse channel is illustrated in Fig. 5. Referring to
this figure, it can be seen that encoder 12a encodes data
to be sent across channel 16 to be decoded by decoder 22b.
At the same time, encoder 12b may encode data to be sent
across channel 16' to be decoded by decoder 22a. Channel
16' is the reverse channel for channel 16, and vice-versa.
This reverse channel 16' is used by the decoding error
detector 21 to send reset requests when an error is
detected in the data decoded by decoder 22b.
As the reverse channel is also unreliable, an
error-tolerant reset protocol is used for the reset
WO9l/10289 21 aoo3s PCT/US90/07472
-- 8 --
operation. Referring to Figs. 6 and 7, this protocol is
initiated when an erroneous frame 52 is detected at the
decoder 22b. When this error18 is detected (at 40 in Fig.
6), the decoder 22b of site B starts a timer 46 and causes
the encoder 12b to send a reset request codeword 42 over
channel 16'. This codeword 42 is received by decoder 22a
which instructs the encoder 12a to reset its data encoding
algorithm. In addition to resetting itself, the encoder
12a also acknowledges reception of the reset request
codeword 42 by inserting a reset acknowledgement codeword
44 in a frame 50. This frame is sent over channel 16 to
decoder 22b which then stops the timer 48 and resets its
data decoding algorithm. At this point, the decoder-
encoder pair are resynchronized and they are ready to
communicate properly with one another, beginning with the
data following the reset acknowledgement codeword 44.
If an error18' occurs on the reverse channel 16',
as shown in Fig. 8, and thus the decoder 22a does not
receive the reset request codeword 42, the encoder 12a will
not reset itself, and will fail to send a reset
acknowledgement codeword 44. This situation is detected by
site B when the reset acknowledgement codeword 44 has not
been received before the timer expires 49. When the timer
expires 49, a second reset request codeword 54 is sent over
channel 16' to decoder 22a. The reset operation then
proceeds as described above.
Note that if an error18 occurs in the forward
channel 16 and prevents the decoder 22b from receiving the
reset acknowledgement codeword 44, the timer will also
expire and a second reset request codeword 54 will be sent.
It should also be noted that errors may occur in successive
reset request codewords or reset acknowledgement codewords,
or in a combination of the two, and that the decoder 22b
will keep sending reset request codewords until the whole
protocol has been satisfied. Thus the protocol is capable
of resetting the data encoding despite the occurrence of
WO91/10289 2 1 ~ O 0 3 ~ PCT/~iS90/07472
g
channel errors on forward channel 16 or reverse channel
16'.
A network equipped with the invention will
perform data encoding and provide the advantages inherent
to this type of data encoding in a way that is transparent
to the end systems using the network. If errors occur on
the network, they will appear no different from errors that
would otherwise occur on an unreliable network, because the
network is capable of resetting its data encoding before
retransmission is started. Thus error propagation due to
loss of synchronization will be limited to those frames
that were sent prior to the retransmission.
The fact that the data encoding is continuous
across frames allows the data encoding to recover in the
case of an out-of-sequence or missing frame, as well.
Also, false resets may be generated, meaning a
reset request (or reset acknowledgement) is generated when
it is not needed. These false resets will typically mean
only a momentary loss of compression efficiency, e.g., as
the data compression algorithm relearns its vocabulary.
Error detection capability may be enhanced by
the data encoding, and may also be used as an additional
mechanism of error detection. For example, some algorithms
destroy much of the data following an error. This enhances
the error detection capabilities of the error detection
algorithms as, in general, their detection reliability
increases as the number of errors in a frame increases.
Furthermore, in this type of algorithm one can periodically
include a control codeword in the data at the encoder. If
such a control codeword is then found to be absent at the
decoder, an error is detected. It is also possible to
detect illegal codewords in the data to be decoded, since
in most algorithms there exist codewords which cannot
appear in a valid sequence of codewords. The presence of
such a codeword signals an error.
WO 91/10289 21 aoo3s PCT/US90/07472
-
-- 10 --
If go-back-n retransmission is used, there will
be no degradation in network performance, as one error will
cause that frame and all subsequent frames to be
retransmitted. If selective retransmission is being
S performed, then the fact that the data encoding errors may
propagate into subsequent frames until the data encoding is
reset may cause some otherwise unnecessary frame
retransmissions. But these may be offset by advantages
inherent in the data encoding. For example, the amount of
increased throughput of a network which uses a data
compression algorithm may be much more significant than
that lost in extra retransmissions.
Longer channels take longer to reset, as the
reset request codeword and the reset acknowledgement
lS codeword must each propagate through the length of the
channel. It can thus be advantageous, when selective
retransmission is being used, to simply reset the data
encoding periodically, independent of any errors. In this
way, the most time that is ever spent while the decoder is
out of synchronization with the channel is the time between
resets, which can be set to be shorter than the round-trip
time of the network. As a special case of this periodic
reset, if the frames are sufficiently long, it may be
desirable to reset the encoder and decoder at the beginning
of each frame. This has the advantage that no vocabulary
needs to be stored between frames.
The time between resets, however, is constralned
by the data encoding method. An adaptive data compression
algorithm, for example, may not become efficient until it
has accumulated a certain vocabulary, and hence increased
frequency of resets may reduce compression efficiency.
Networks where it is advantageous to use periodic resets
are those in which a>m/2, where m is the minimal reset
interval that still provides acceptable data encoding
performance, and a is the round trip equivalent of the
data. The minimal reset interval m is typically on the
WO 9IJ10289 2 1 8 0 n 3 9 PCT/~S90/07472
order of a few kilobytes for an adaptive data compression
algorithm.
The use of periodic reset is shown in Fig. 9.
In this illustrated case, the data encoding is reset every
nine frames, by sending frames 50 that include a reset ack
codeword 44 every nine frames. The round trip equivalent
of this illustrative channel is thirty-two frames. Using
periodic reset is advantageous in this case, as single
errors will only affect the decoding of at most nine
frames, which is fewer than the thirty-two that would be
affected using a reset protocol.
In some networks, it is advantageous to use a
combination of the two techniques. In shorter paths within
the network, the reset protocol would be the most
advantageous, whereas longer ones would benefit from
periodic reset. In a system which uses both techniques,
the choice of reset methods is made based on the
configurations of the channel once the routing of the
channel from node to node has been decided. For example,
in Fig. 4, the X channel which passes via nodes a, b, c and
d might use the reset protocol, while the Y channel passing
via a longer path might use periodic resets.
In communication networks, it is not uncommon
for several nodes to be communicating with the same node,
and thus the decoding timers would have to be duplicated.
In this type of situation, a way to reduce complexity is to
use the same timer for all decoders at once. If a reset
request codeword or a reset acknowledgement codeword is
lost, and the timer expires, a second reset request
codeword is sent on all of the channels waiting for a reset
acknowledgement codeword, until the protocol is satisfied.
This system is useful if the number of channels is not too
large relative to the error rates on each channel.
Other embodiments are within the scope of the
following claims. For example, the data encoding error
detection (15, 21) and end system error detection (1~, 20)
WO91/10289 2 1 ~ O 0 3 ~ PCT/US90~07472
....... .
- 12 -
might be combined, to reduce system complexity, but in
practice, it is generally preferable to keep these
functions separate, as it is better not to constrain the
end systems to a specific type of error detection. In this
way, a network which includes data encoding may be used
with different types of end systems, as long as they are
designed to operate over unreliable channels. Although it
would, in principle, be possible to build data encoding
into the end systems 6, anà thus avoid the need for
separate error detection and reset capability for the
encoding process, it is also generally preferable not to do
so. By leaving data encoding to the network system, the
expense and complexity of encoding need not be incurred in
portions of the network where it is not cost effective.
For example, data compression tends to be cost effective
only on the backbone network and not the local portions of
a network.
