Note: Descriptions are shown in the official language in which they were submitted.
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
A METHOD AND APPARATUS FOR TRANSFERRING DATA PACKETS IN
COMMUNICATION NETWORKS
TECHNICAL FIELD
The present invention relates generally to a
method and apparatus for transferring data units from a
sender to a receiver. In particular, the invention is
concerned with compensating for lost or disordered data
units received in a transcoder.
BACKGROUND OF THE INVENTION AND PRIOR ART
Recently, systems and solutions have been
developed for providing packet-based transmission of
digitally encoded information for a variety of services,
such as telephony, video telephony, television and video
distribution, in addition to Tnternet surfing and e-mail or
the like. These services are delay sensitive to a varying
extent and are often classified accordingly for selecting
suitable transmission mechanisms. The most delay sensitive
applications, such as telephony and video telephony, are
sometimes referred to as real-time services demanding a
total transmission time from sender to receiver of not more
than approximately 200 miliseconds. Less delay sensitive
applications, such as downloading of data, e.g., homepages
from the Internet, are sometimes referred to as best effort
services, for which a transmission time of a couple of
seconds is mostly acceptable. Thus when transmission
resources are shared; real-time data is typically given
priority over best effort data.
The information to be transmitted is digitally
encoded at the sending side and fitted into data units,.
e.g., data packets or frames, of a specific format according
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
2
to a coding scheme. The data units are handled as
transmission units along the transmission path which may for
example comprise various networks, switches, gateways and
routers. The encoded information is finally decoded when
received at its destination in order to be presented or
played to a user at the receiving end. However, due to
standard discrepancies, the sending and receiving equipment
are often only capable of using specific coding schemes
being different from each other, requiring that the
information encoded by the sender is re-coded somewhere
before reaching the receiving party. This operation is often
referred to as transcoding.
In addition, different networks and/or switching
nodes along the transmission path may also use formats and
coding schemes of different standards, resulting in further
needs for transcoding. Thus, the transmitted data may have
to be re-coded several times before reaching the final
receiver. For real-time services, and to a certain extent
also media streaming services, it is desirable to minimise
the delays due to transcoding activities in nodes of the
total transmission path. For example, if a delay of more
than 200 miliseconds is introduced in a voice call between
two parties, the dialogue flow becomes considerably
disturbed.
Fig. 1 illustrates an exemplary communication
scenario for transferring data between a sender 100 and a
receiver 102. In this simplified example, asymmetric
transmission in only one direction at a certain point of
time is considered. For symmetric transmissions, each party
100 and 102 is of course able to act as both sender and
receiver, such as for voice calls. The sender 100 is
connected to an access network 104 which may be a Local Area
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
3
Network (LAN), a wireless network or the like. The receiver
102 is likewise connected to another access network 106.
Each access network 104, 106 is further connected to
respective gateway switches 108, 110 for communication over
an intermediate communication system 112, which may comprise
one or more public networks such as the Internet or a Public
Switched Telephony Network (PSTN).
The sender 100 is capable of using a first coding
scheme for encoding the data to be transmitted. The receiver
102, on the other hand, is capable of using a second coding
scheme for decoding the received data, the. second coding
scheme being different from the first. Moreover, the
intermediate communication system 112 may use one or more
further coding schemes in different parts thereof for
transferring the communicated data. It is thus evident that
the communicated data must be re-coded each time it enters a
new domain using a coding scheme different from the one used
bef ore .
For example, transcoding must be done between
packet switched networks and circuit switched networks
using, e.g., Time Division Multiplexing (TDM). The data is
thus transferred over one or more transcoders for creating
new data units from the received previous ones before being
transmitted further in the transmission path. The gateways
108, 110, as well as other switching nodes within the
intermediate communication system 112 in Fig. 1, may
typically comprise such transcoders.
Furthermore, if one or more of the networks 104,
112, 106 use packet based transmission, there is a potential
risk of the data packets being received at the transcoders
in the wrong order. In packet based transmission, each data
packet is treated individually and may take separate
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
4
transmission paths and/or be subjected to different delays
in intermediate nodes. Therefore, a buffer is often arranged
in transcoders and receivers, sometimes referred to as a
fitter buffer, to compensate for packets being received with
different delays. The buffer enables the reception of a
plurality of data packets arranged in a queue before being
transcoded or decoded. The packets may then be re-ordered in
the queue if necessary. Another method is to simply discard
packets received in the wrong order, although resulting in a
degradation of quality. The receiving side of an
intermediate node between a packet domain and a TDM domain
typically includes a fitter buffer.
fitter-buffering techniques entail the drawback of
introducing unwanted delays in the transmission. It also
requires a clock timing reference when TDM based
transmission is involved. Furthermore, the final receiver
102 typically includes a fitter buffer or similar function
for decoding, adding to the total latency of the transmitted
data. A transcoding function should not add more latency
than the time required to process the data and to perform
the transcoding. However, if every data packet is
sequentially transcoded as they arrive, the resulting
quality will be degraded when arriving in the wrong order.
In particular, many coding schemes rely on historic data
when decoding a particular chunk of data,~i.e., information
from the previously decoded data is used fox decoding the
next data. All data must therefore be decoded in the same
sequence order as it was outputted from the sending encoder
in order to acquire high quality at the receiving end.
It is an object of the present invention to
overcome the drawbacks outlined above and achieve a high
quality of received encoded data when being decoded at the
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
receiving end, at the same time minimising transmission
delays in intermediate transcoders.
SUMMARY OF THE INVENTION
These and other objects are achieved by a simple
solution for minimising delays in transcoders and
eliminating the need for fitter buffers, wherein data units
arriving in an erroneous sequence order are compensated for
by restoring late arriving data.
A method and a transcoder unit are provided for
transcoding communicated data in a transmission path between
a sender and a final receiver. Data units comprising coded
information in a first format are received and coded into
new data units in a second format, based on a current coding
state extracted from a previous coding of data. A new
current coding state is extracted each time a data unit is
coded.
When receiving each data unit, it is detected
whether the received data is in an erroneous sequence order,
which may be done by reading information indicating a
sequence order of the received data. If that is the case,
the coding state extracted from the previous coding of data
is saved and a new pseudo coding state is extracted for
coding a next received data unit.
Tf missing data is eventually received, it is
coded into the second format based on the saved coding
state, and the coded missing data may be used as valid data.
The saved coding state may then be deleted. The saved coding
state may also be deleted if the corresponding missing data
is not received within a pre-set time period, which may be
based on data flow characteristics. The saved coding state
may also be deleted if the number of saved decoding states
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
6
reaches a pre-set threshold value, which likewise may be
based on data flow characteristics.
The inventive procedure may be used for decoding
received data units, wherein the coding states are decoding
states and that the second format is an intermediate format.
The received data units may then be decoded into a stream of
intermediate data divided into intermediate data segments
which are encoded into new data units.
The inventive procedure may also be used for
encoding received data units, wherein the coding states are
encoding states and the first format is an intermediate
format. The received data units may then comprise decoded
intermediate data which is encoded into new data units.
If the received data is in an erroneous sequence
order, error concealed data may be derived from the
previously received data unit and the current decoding
state, wherein the new pseudo coding state can be extracted
based on the derived error concealed data.
The inventive procedure may be implemented in a
transcoder unit located in the transmission path between the
sender and the final receiver, and having means for
performing the procedure.
The inventive procedure may also be implemented in
a computer program product directly loadable into a computer
in the transcoder unit, comprising software code means for
performing the procedure.
The inventive procedure may alternatively be
implemented in a computer program product stored on a
computer usable medium, comprising a readable program for
causing a computer in the transcoder unit to perform the
procedure.
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
7
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will now be described in
more detail and with reference to the accompanying drawings,
in which:
Fig. l is a schematic view of an exemplary communication
system for transferring data.
Fig. 2 is a schematic view of the data flow in a transcoder.
Fig. 3 is a logical scheme illustrating the decoding of data
packets arriving in the right order.
Fig. 4 is a logical scheme illustrating the decoding of data
when a data packet arrives in the wrong order.
Fig. 5 is a logical scheme illustrating the encoding of
intermediate data.
Fig. 6a is a logical scheme illustrating the encoding of
data when a data unit is lost.
Fig. 6b is a logical scheme illustrating the encoding of
data when missing data arrives late.
Fig. 7 is a logical scheme illustrating generally the
transcoding of data when a data unit arrives in the wrong .
order.
DESCRIPTION OF PREFERRED EMBODIMENTS
Fig. 1 illustrates an exemplary communication
system, described above, for transferring data between a
sender 100 and a receiver 102, in which the present
invention may be implemented. Of course, the invention may
also be used in numerous other types of communication
systems.
Fig. 2 is a schematic view of the data flow in an
exemplary transcoder unit 200 for transcoding data according
to the invention. Data 202, encoded according toga first
coding scheme and having a first format F, is received by
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
8
the transcoder unit 200 for transcoding the data into a
second coding scheme having a second format F'. The
transcoding process is in this example divided into two
operations, a decoding operation 204 and an encoding
operation 206. Between the two operations, the data is in a
decoded intermediate format IF 208. However, it is possible
within the scope of the invention to re-code or transcode
the incoming data 202 of the first format F directly into
the second format F' without using any intermediate format.
After being coded into the second format F', the data 210 is
transmitted further on to the next node, not shown, in the
transmission path. Furthermore, the transcoder comprises a
memory 212 for storing coding states, which will be
described in more detail below.
Typically, the incoming data is grouped into data
units, e.g., packets or frames, encoded according to the
first format F. The incoming data may be packet switched or
circuit switched. Each incoming data unit includes a field
or the like with information indicating a sequence order,
such as a sequence number or a time stamp, which is read by
the receiving transcoder unit 200. In the normal case, the
received data units are decoded sequentially in operation
204 into the next format IF or F' if the data units are
received in the correct order as they were originally
transmitted and with no lost data.
An example of this is illustrated in Fig. 3, with
further reference to Fig. 2, wherein F1, F2, F3... are data
packets 202 of the first format F being received in the
correct order at the transcoder unit 200. The data packets
202 are decoded separately in operation 204 into
intermediate data units 300 having the intermediate format
TF. When decoding each data packet 202, information from the
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
9
previous decoding result, which is represented in Fig. 3 as
a series of current historic decoding states DS 302, is
used. A decoding state comprises variables or parameters,
apart from the actual data, extracted from the performed
decoding operation and reflecting some characteristics of
the data.
Thus, a received data packet F1 is decoded 204
into an intermediate data unit IFl based on a current
decoding state DSO being extracted from the decoding result
of a previously decoded data packet, not shown. After using
the decoding state DSO, a new decoding state DS1 is
extracted from the latest decoding of F1. The next data
packet F2 is then decoded 204 into IF2 based on the last
decoding state DS1, and so on.
In this description, it is generally assumed that
all incoming data packets have equal size, although in
reality, the packet size may vary. In that case, the data
may be rearranged into equally sized units, but the
transcoding process can be handled using the same principles
as in the simplified case of equal packet size.
The-decoding procedure illustrated in Fig. 3
involves data packets received in the correct sequence
order. However, if a data packet is received having a
sequence number higher than the previous sequence number
incremented by one, it may be assumed that the missing
packet is lost or delayed. Alternatively, the packet order
may be indicated by a time stamp or any other order
indicating information. If a data packet is thus missing, an
error concealment mechanism may be invoked in order to
minimise the resulting quality degradation at the receiving
end. The error concealment mechanism may derive error
concealed data based on the previous data packet and the
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
latest decoding state extracted from the decoding of the
previous data packet. Error concealment is a well-known
procedure which attempts to create the most likely data when
no real data is available. The error concealment is
typically performed according to a prescribed standard for
the data format, or if no standard exists, a proprietary
mechanism may be used.
According to one aspect of the invention, an error
concealment mechanism is invoked when data is received in
the wrong sequence order, and the latest decoding state
before the error concealment is saved for later use if the
missing data packet eventually turns up, although in the
wrong order. In that case, the missing data packet is
decoded based on the saved decoding state according to the
invention.
Fig. 4 illustrates an exemplary decoding procedure
according to the invention when a data packet is received in
the wrong sequence order. First, a data packet F1 is decoded
204 into the intermediate data unit IFl based on the latest
decoding state DSO, wherein a new decoding state DS1 is
extracted, as in the previous example of Fig. 3. However,
next comes a data packet F3 having a sequence number 3
higher than the previous sequence number 1 incremented by
one. Upon detecting that the sequence number of the received
data packet F3 is erroneous, i.e. higher than expected, an
error concealment mechanism 400 is invoked for deriving
error concealed data 402 in the intermediate format and for
extracting a new pseudo decoding state DS2', based on the
previous decoding state DS1. The pseudo decoding state DS2'
may be extracted in the same way as the other decoding
states since the error concealment is a decoder function in.
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
11
which a decoding state can be extracted regardless of
whether real data is available.
The data packet F3 is then decoded 204 into the
intermediate data unit IF3 based on the new pseudo decoding
state DS2'. Furthermore, the previous decoding state DS1 is
saved in the memory 212 in the transcoder unit 200. A new
decoding state DS3 is also extracted from the decoding 204
of data packet F3 for later use when decoding a data packet
of the next sequence order, not shown.
In this example, the missing data packet F2 is
received next and can be decoded 204 into the intermediate
data unit IF2 based on the saved previous decoding state
DS1. The used saved decoding state DS1 may thereafter be
deleted from the memory 212 in the transcoder unit 200.
Finally, the restored intermediate data unit IF2 is inserted
in the right sequence order between IF1 and IF3, replacing
°the earlier derived error concealed data 402. However, if
the missing data packet F2 is not received, e.g., within a
pre-set time period, the error concealed data 402 may remain
valid when the data of the intermediate format 208 is
encoded 206 into the second format F' in the transcoder unit
200.
In this way, valid and decoded intermediate data
units 300 can be arranged in a correct sequence order before
being encoded again into the second format F', even if one
or more data units in the first format F was received at the
transcoder in an erroneous order. Furthermore, this
procedure is conducted with a minimum of delay, maintaining
a highest possible quality.
The example of Fig. 4 described above was
concerned with one data packet received out of sequence. A
corresponding procedure may be conducted if multiple data
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
12
packets are received out of sequence using multiple saved
decoding states. Furthermore, a saved decoding state may be
deleted from the memory 212 if it has remained unused for a
pre-set time period. The pre-set delete time period may
further be configurable or adaptive depending on data flow
characteristics, such as the number of data packets of
erroneous sequence order varying over time. Alternatively, a
number of simultaneously saved decoding states may be
maximised by a pre-set threshold value, which may likewise
be configurable or adaptive depending on data flow
characteristics. If the number of saved decoding states
reaches the pre-set threshold value, a mechanism may be
triggered for deleting individual saved decoding states from
the memory 212.
After the decoding operation 204, the intermediate
data units 300 are arranged into a continuous stream of data
208 which is fed into the encoding operation 206, see Fig.
2. The transcoder unit 200 then encodes the intermediate
data 208 into new data units such as packets, frames or
blocks, i.e., data portions of a predetermined size,
according to the new second coding scheme or format F'
depending on the availability of data. If no intermediate
data 208 is currently available, the encoding process may
simply wait until there is. The new data units in the second
format F' are finally transmitted to the next node in the
transmission path.
Fig. 5 illustrates an encoding procedure according
to the invention for the intermediate data stream 208
comprising the intermediate data units IF1, IF2, IF3... from
the previous decoding operation 204. First, the intermediate
data is received and may be arranged into new intermediate
data segments~Sl, S2, 53... 500, if necessary, to be encoded
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
13
into the second format F'. The size of the new intermediate
data segments 500, indicated by vertical dashed lines in the
figure, is in this example different from the size of the
intermediate data units 300 coming from the decoding
operation 204. Each new intermediate data segment or unit
500 is then encoded 206 into a new data unit 506 of the
second format F' based on a current encoding state ES 502
extracted from a previous encoding operation. An encoding
state comprises variables or parameters, apart from the
actual data, extracted from the performed encoding operation
and which is used for encoding data.
Thus, an intermediate data segment Sl is encoded
206 into a new data unit F'1 based on a last encoding state
ESO being extracted from the previously encoded new data
packet, not shown. After using the encoding state ESO, a new
encoding state ES1 is extracted from the latest encoding of
F'1. The next intermediate data segment or unit S2 is then
encoded 206 into F'2 based on the last decoding state DSL,
and so on.
The intermediate data units 300 may be classified
according to the nature of their contents such that "good
data" has been created directly from payload of an incoming
data packet or unit, and "error concealed data" has been
derived from the latest decoding state by using the error
concealment mechanism 400 when no incoming data packet or
unit of a correct sequence order was available. In the
example of Fig. 5, IF1. and.IF2 contains 'good data', whereas
IF3 contains 'error concealed data', in the figure indicated
with strokes. Consequently, segments S1 and S2 contain only
'good data' but segments S3 and S4 contain both 'good data'
and 'error concealed data' as a result from the difference
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
14
of size between the intermediate data units 300 and the
intermediate data segments 500.
According to one aspect of the invention, the
intermediate data segments 500 are treated differently
depending on the classification of the data. Thus, .if a
segment 500 contains at least some 'good data', the segment
is encoded and a new encoding state is extracted
accordingly. This is the case for all segments Sl - S4 shown
in Fig. 5.
However, if an entire segment contains no 'good
data', i.e., only 'error concealed data', the segment may
simply be discarded and the latest encoding state extracted
at least partly from 'good data' is saved. This is
illustrated in Fig. 6a, wherein a segment S1 containing
'good data' is encoded into a new data unit F'1 and a new
encoding state ES1 is extracted. The next segment S2
contains 'error concealed data' and no 'good data', which is
indicated with strokes in the figure, and is therefore
discarded 600. One new data unit is thereby considered to be
lost. The latest encoding state ES1 is saved for later use,
should the missing data eventually arrive.
With reference to Fig. 6b, a segment S1 containing
'good data' is encoded into a new data unit F'I and a new
encoding state ES1 is extracted, just as in the example of
Fig. 6a. The next arriving segment S2 contains 'error
concealed data' and no 'good data', again indicated with
strokes in the figure. According to an alternative
embodiment, the segment S2 is first encoded into a pseudo
data unit 602, based on the available error concealed data,
which is then discarded 600. In this case, a new pseudo
encoding state ES2' can. be extracted from the encoding of
S2, to be used for encoding the next segment, not shown. In
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
this example, the missing data eventually arrives later in
segment S4, which may be encoded into a new valid data unit
F'2 based on the earlier saved encoding state ES1. It should
be noted that the sequence order of the segments S1 - S4 is
selected from the division of the intermediate data stream
for illustrative purposes, and is not to be confused with
the sequence order of the actual data. Thus in this example,
segment S4 contains data that should have been included in
segment S2.
The restored new data unit F'2 may then be'
transmitted to the next node in the transmission path.
Furthermore, it is possible to send F'2 in an erroneous
sequence position, in this case after F'3, since the final
receiver is often capable of restoring the correct data unit
order before decoding.
The procedure described above in connection with
Fig. 6b may also be performed fox multiple segments arriving
out of sequence, using multiple saved encoding states.
Moreover, the same mechanisms as described above for saving
multiple decoding states can generally also be applied for
saving multiple encoding states.
The examples described above include the two
separate operations of first decoding received data from a
first format to an intermediate format, and then encoding
the intermediate data into a second format for transmission.
However, the invention may also be used for re-coding
incoming data of the first format directly into the second
format without using an intermediate format.
Fig. 7 illustrates the most general case according
to the invention of a re-coding or transcoding procedure
when a data unit is received in the wrong sequence order.
Generally, F1, F2, F3... denote incoming data units 700 having
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
16
a first format F. The data units 700 are coded separately in
operation 702 into new data units 704, in the figure
generally denoted as F'1, F'2, F'3..., having a second format
F'. The expression "coding" is used here for denoting any of
decoding, transcoding or encoding. When coding each incoming
data unit 700, information from a previous coding result,
which is represented in Fig. 7 as a series of current
historic coding states CS 706, is used.
Thus, a data unit F1 of the first format F is
coded 702 into a new data unit F'1 of the second format F'
based on a current coding state CSO, wherein a new coding
state CS1 is extracted. The next received data unit F3
includes a sequence number 3 higher than the previous
sequence number 1 incremented by one. Upon detecting that
the sequence number of the received data unit F3 is higher
than expected, pseudo data 708 of the second format F' is
created based on the current coding state CS1 for extracting
a new pseudo coding state CS2'. The data unit F3 is then
coded 702 into a new data unit F'3 based on the pseudo
coding state CS2'. Furthermore, the previous coding state
CSl is saved in the memory 212. A new coding state CS3 is
also extracted from the coding 702 of data unit F3 into the
new data unit F'3.
The missing data unit F2 is received next and can
be coded 702 into a new data unit F'2 based on the saved
previous coding state CS1. The used saved coding state CS1
may thereafter be deleted from the memory 212. Finally, the
restored data unit F'2 is used as valid data and the earlier
created pseudo data 708 is discarded. However, if the
missing data unit F2 is never received within a pre-set time
period, the pseudo data 708 may be used as valid data or may
be discarded, depending on the implementation.
SUBSTITUTE SHEET (RULE 26)
CA 02443079 2003-10-03
WO 02/082755 PCT/SE02/00590
17
By using the invention as described above, delays
in transcoders are minimised and the need for fitter buffers
is eliminated, while still maintaining a high quality of
transmitted data. Specifically, data units arriving in an
erroneous sequence order are compensated for by restoring
late arriving data according to the invention. The invention
is primarily aimed to be used for speech transcoding, but
may also be used for, e.g., fax transcoding, modem data or
packet based video signals.
The inventive method may be implemented in a
software code comprised in a computer program product,
directly loadable into a computer in the transcoder unit 200
or stored on a computer usable medium.
Glhile the invention has been described with
reference to specific exemplary embodiments, the description
is only intended to illustrate the inventive concept and
should not be taken as limiting the scope of the invention.
Various alternatives, modifications and equivalents may be
used without departing from the spirit of the invention,
which is defined by the appended claims.
SUBSTITUTE SHEET (RULE 26)
