Note: Descriptions are shown in the official language in which they were submitted.
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 1 -
Overload control method for a packet-switched network
FIELD OF THE INVENTION
The present invention relates to a method for controlling
overload in a packed-switched network, especially a
wireless or mobile network in which the Transmission
Control Protocol (TCP) is used as a transport layer
protocol.
BACKGROUND OF THE INVENTION
Overload or congestion control is one of the key mechanisms
to accommodate the increasingly diverse range of services
and types of traffic in the Internet. As commonly known,
TCP is the most popular transport layer protocol for data
transfer. It provides connection-oriented reliable transfer
of data between two connecting hosts, wherein a host refers
to a network-connected computer or to any system which can
be connected to a network for offering services to another
host connected to the same network. TCP uses several
techniques to maximize the performance of the connection by
monitoring different variables relating to the connection.
For example, TCP includes an internal algorithm for
avoiding congestion.
Congestion control relates to the general problem of
traffic management for packet-switched networks. Congestion
means a situation in which the number of transmission
requests at a specific time exceeds the transmission
capacity at a certain network point (called a bottle-neck
resource). Congestion usually results in overload
conditions. As a result, the buffers may overflow, for
instance, so that packets are retransmitted either by the
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 2 -
network or by the subscriber. In general, congestion
arises, when the incoming traffic to a specific link is
more than the outgoing link capacity. The primary function
of congestion control is to ensure good throughput and
delay performance while maintaining a fair allocation of
network resources to the users. For the TCP traffic, whose
traffic patterns are often highly bursty, connection
control poses a challenging problem. It is known that
packet losses result in a significant degradation in TCP
throughput. Thus, for the best possible throughput, a
minimum number of packet losses should occur.
Currently, several schemes, including Fast-TCP, have been
put forward to enhance the function of avoiding congestion
in the TCP flow control. Although the purpose of these
mechanisms is to avoid packet droppings in case of queue
overflows, network congestion cannot be completely avoided
even with very perfect congestion avoidance mechanisms.
Thus, it is still necessary to combine these mechanisms
with existing TCP flow control mechanisms for congestion
control, that is, source window reduction shall sometimes
be invoked by lost packets due to a buffer overflow, to
thereby alleviate the congestion in time.
Initially, the Internet was intended to support best-effort
service, and the TCP congestion control method that was
actually implemented has been developed on the assumption
that the network would be treated as a black box. This
means that the end nodes do not exercise control by
directly ascertaining the state of routers and transmission
lines, but rather regulate the traffic by inferring the
network load indirectly from packet loss and response time
fluctuations. In wired networks, this may not induce
serious problems, as packet losses mainly occur due to
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 3 -
congestion. However, in the presence of high error rates
and intermittent connective characteristic as in wireless
links, this reliance on packet drops as an indicator of
congestion causes a significant degradation in TCP
performance, since the TCP reacts to packet losses as it
would in the wired environment. Namely, it drops its
retransmit window size before retransmitting packets,
initiates congestion control or avoidance mechanisms and
resets its retransmission timer. This results in an
unnecessary reduction in the link bandwidth utilization of
wireless and mobile networks, causing poor throughput and
very high interactive delays.
Recently, several schemes have been proposed to alleviate
the effects of non-congestion-related losses on TCP
performance over networks that have wireless or similar
high-loss links.
In the article "Implementation and Performance Evaluation
of Indirect TCP" by Ajay V. Bakre et al, IEEE Transactions
on computers, Vol. 46, No. 3, March 1997, the Indirect-TCP
protocol is described as one of the first protocols to
distinguish different losses by splitting a TCP connection
between a fixed and a mobile host into two separate
connections at the base station, such that a more optimized
wireless link-specific protocol tuned for better
performance can be used over a one-hop wireless link.
However, there are some drawbacks of this approach, such as
loss of semantics, application re-linking and software
overhead.
Furthermore, an ELN (Explicit Loss Notification) protocol
has been proposed, wherein an explicit loss notification
option is added to TCP acknowledgments, when a packet is
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 4 -
dropped on the wireless link. In this case, future
cumulative acknowledgments corresponding to each lost
packet must always be marked to identify that a non-
congestion-related loss has occurred. Moreover, it might be
difficult to identify packets lost due to errors on lossy
links and to determine a connection of a corrupted packet,
since the header could itself be corrupted.
Additionally, another research area is described in "A
proposal to add Explicit Congestion Notification (ECN) to
IP" by K.K. Ramakrishnan et al, Internet Draft-kksjf-ecn-
02.txt, September 1998, wherein congestion control is
decoupled from packet loss. By doing this, packet losses
will not invoke congestion control, such that transmission
errors do not lead to a reduced throughput. In particular,
an Explicit Congestion Notification (ECN) is added to a TCP
acknowledgment option by detecting incipient congestion in
the network. Upon receiving this ECN message, the
transmitter reduces its congestion window whenever a loss
occurs.
However, many current networks with routers whose main
function is to route packets have no provision for the
detection of an incipient congestion before a queue
overflow occurs. Nevertheless, even if such a provision
were provided, the packet marking rate could not catch up
with its passing rate during periods where the average
queue size exceeds an upper threshold. Therefore, routers
drop packets rather than setting the ECN in the packet
header.
In spite of all these difficulties, ECN is likely to be
adopted gradually. Thus, accommodating migration is an
essential requirement for future TCP networks.
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 5 -
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to
provide a method for controlling overload in a packet-
switched network, and a packet-switched telecommunication
network, by means of which an unnecessary reduction of the
link bandwidth utilization can be prevented.
This object is achieved by a method for controlling
overload in a packet-switched network comprising traffic
sources, traffic destinations and network nodes, said
method comprising the steps of:
transmitting data packets from one of said traffic sources
to one of said traffic destinations;
transmitting an acknowledgment packet from said one traffic
destination to said one traffic source, if a data packet
has been received correctly at said one destination; and
adding a congestion notification information to a data
packet following a data packet lost due to a buffer
overflow.
Additionally, the above object is achieved by a packet-
switched telecommunication network comprising:
network nodes interconnected by transmission lines;
user terminals connected to said network nodes, said user
terminals acting as traffic sources which transmit data
packets and as traffic destinations which receive data
packets;
detecting means for detecting a loss of a data packet due
to a buffer overflow in one of said network nodes; and
control means for adding a congestion notification
information to a data packet following a data packet lost
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 6 -
due to said buffer overflow, in response to a detection
result of said detection means.
Accordingly, a short-cut ECN mechanism (Wireless-ECN) which
preferably can be used in wireless or mobile environments
is provided. Like ELN, the mechanism is arranged to
communicate the reason for a packet loss to the TCP source.
In particular, the source can be informed that a loss
happened due to reasons related to a network congestion,
such that congestion control can be decoupled from
retransmissions. Thus, the congestion window is only
reduced in case the congestion notification information has
been received, without considering packet losses. By
quickly informing the source that a loss happened due to
reasons relating to a network congestion, congestion
control and loss recovery mechanism can be separated. This
mechanism is simple to implement and compatible with the
existing TCP congestion control.
When Wireless-ECN is used in the traditional ECN
environment, Wireless-ECN is interpreted by the TCP source
as a new instance of congestion. The integration of
Wireless-ECN into the known ECN mechanism allows congestion
control to be initiated by WECN or ECN messages. Since a
WECN message should be added at least not later than the
threshold number of following packets, it may invoke
congestion control even sooner than with the fast
retransmission mechanism. The integration of the WECN into
the ECN mechanism not only avoids unnecessary congestion-
induced packet losses, but also prevents the unnecessary
delayed initiation of congestion control which often occurs
due to a loss of an ECN packet or an inefficient effect of
the ECN mechanism or other exceptions in the ECN mechanism.
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
Preferably, said following data packet directly follows
said lost data packet. This ensures that the congestion
notification information can inevitably by added even with
multiple packet losses, and there is no need for mechanism
in the router to monitor the average queue size. Since the
congestion notification information is added as quickly as
possible after a packet loss has occurred due to
congestion, it is ensured that a network congestion is
alleviated in time.
Furthermore, the congestion notification may be added in
the header of said following data packet. In this case, bit
No. 5 in the IPv 4 TOS octet can be used, for example.
Preferably, each of the network nodes should be able to add
the congestion notification information to thereby indicate
a congestion-related data loss. Thereby, multiple WECN
messages provide a robustness against the possibility of
dropping a WECN packet in the bi-directional transmitting
paths.
The congestion notification information is allowed to be
added to those following data packets which belong to the
same congestion window in the successively past routers.
Moreover, each network node is allowed to add the
congestion information only once. Thus each congestion
notification information added in a transmission window
belongs to another network node.
Having received a data packet with an added congestion
notification information, the traffic destination
preferably sets a congestion notification flag in the
header of an acknowledgment packet. The congestion
notification flag may be bit No. 8 in the TCP header of the
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
_ g _
subsequent acknowledgment packet. Since the TCP uses the
WECN message to invoke congestion control, only a
retransmission mechanism is performed in case of a packet
loss without a WECN message. Thus, the TCP data flow rate
is not affected. This is very useful in wireless or mobile
networks, since the network itself has the function of
distinguishing different sources of packet losses. By
notifying the source with a WECN acknowledgment packet
whenever a congestion-related loss has occurred, packet
losses due to transmission errors cannot reduce the TCP
flow control window (congestion window), which results in a
significant performance improvement. The congestion window
can only be reduced by the congestion notification flag set
due to a congestion loss.
Preferably, a congestion processing is repeated at the
traffic source only after the outstanding data packets
transmitted before the first receipt of a congestion
notification flag have all been acknowledged. Thereby,
reduction of the congestion window is not repeated, if the
packet was dropped before the source reduced its window in
response to the congestion notification flag.
The WECN mechanism according to the present invention
enables complete decoupling of the congestion control
function from packet losses. Compared to ECN, the WECN
notification may inevitably be added, since the dropped
packets give the buffer time to vacate some space for
holding and transmitting new data. In case a WECN is lost,
e.g. in a high loss link condition where all WECN
notifications are lost in a control cycle, or in case only
one WECN is added in a transmission window and this WECN is
lost by accident, this loss will result in a failure of
congestion control for that flow and an increased
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 9 -
congestion of the network, since the assumed source of data
loss was not a congestion. Nevertheless, other WECNs are
added for subsequent dropped packets in the next congestion
window. Thus, the mechanism is very secure and robust
compared to the ECN mechanism where the loss of an ECN will
not cause another addition of an ECN packet.
According to the present invention, no packet losses need
to be considered to invoke congestion window reduction.
Since mechanisms for monitoring-the average queue size are
not required in the routers, the WECN mechanism can be
implemented in a simple manner and opens the way to a
further deployment of the ECN mechanism. It is to be noted
that the WECN mechanism is compatible with all TCP
congestion control mechanisms, as long as they are invoked
by packet losses, and it is easy to incorporate them into
wireless and mobile networks. With the incremental
deployment of the ECN mechanism, the integration of WECN
into ECN may allow congestion control to be initiated by
WECN or ECN messages and WECN packet functions only if a
packet lost due to a congestion arrives earlier than an ECN
within the corresponding data window. With the addition of
WECN to the Fast-TCP mechanism, the window reduction could
be invoked by WECN when a buffer overflow occurs, since the
TCP behavior at the end systems is not changed. Thus, this
is an effective way of inproving TCP performance in
wireless and mobile networks.
In addition, since WECN is required to be added not later
than after a threshold number of duplicate
acknowledgements, improved TCP performance in wired network
environments can be expected, since the initiation of
congestion control is accelerated by the WECN message.
Moreover, if this message is used for triggering the
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 10 -
transmission or retransmission data packets, it can hasten
the speed of entering into the TCP recovery phase due to
congestion, such that congestion-induced lost packets are
quickly retransmitted.
BRIEF DESCRIPTION OF THE DRAWINGS
In the following, the present invention will be described
in greater detail on the basis of a preferred embodiment
with reference to the accompanying drawings, in which:
Fig. 1 shows a general block diagram of a flow control loop
in a TCP over ATM network, in which the preferred
embodiment of the present invention is implemented;
Fig. 2 shows a general block diagram of an intermediate
node arranged between a traffic source and a traffic
destination, according to the preferred embodiment of the
present invention;
Fig. 3 shows a general block diagram of two subsequent
intermediate nodes according to the preferred embodiment of
the present invention;
Fig. 4 shows a diagram of transmissions between a traffic
source and a traffic destination, in case a wireless
congestion notification (WECN) arrives at the traffic
source before a usual congestion notification (ECN) within
the same transmission window;
Fig. 5 shows a diagram of transmissions between the traffic
source and the traffic destination, in case a non-
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 11 -
congestion packet loss is detected before a congestion
notification within the same transmission window;
Fig. 6 shows a diagram of transmissions between the traffic
source and the traffic destination, in case a WECN arrives
at the traffic source after an ineffective ECN
implementation in the preceding transmission window;
Fig. 7 shows a diagram of transmissions between the traffic
source and the traffic destination, in case a WECN is
received at the traffic source after a normal ECN within
the same transmission window;
Fig. 8 shows a diagram of transmissions between the traffic
source and the traffic destination, in case a WECN is set
before three following packets in the same transmission
window;
Fig. 9 shows a diagram of transmissions between the traffic
source and the traffic destination, in case of a WECN and a
non-congestion packet loss within the same transmission
window; and
Fig. 10 shows a diagram of transmissions between the
traffic source and the traffic destination, in case of a
delayed set of WECN and multiple congestion losses within
the same transmission window.
DESCRIPTION OF THE PREFERRED EMBODIMENT
In the following the preferred embodiment of the present
invention will be described on the basis of a TCP over ATM
network as shown in Fig. 1.
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 12 -
ATM (Asynchronous Transfer Mode) is a connection-oriented
packet-switching technique which the international
telecommunication standardization organization ITU-T has
chosen as the target solution of the broadband Integrated
Services Digital Network (B-ISDN). The problems of
conventional packet networks have been eliminated in the
ADM network by using short packets of a standard length (53
bytes), known as cells. ATM networks are quickly being
adopted as backbones for the various parts of TCP/IP
networks such as the Internet. This also applies to
wireless or mobile networks.
According to Fig. 1, a connection between two user
terminals A and B in the TCP over ATM network is shown,
i.e. the user terminals using TCP as a transport layer
protocol. In addition, two access nodes AN1 and AN2 of the
user terminals, one intermediate node N1 and transmission
lines TL1, TL2 connecting the nodes are shown.
After an initial handshake has been completed, the user
terminals A and B begin to transmit data by means of TCP
segments. The term "segment" refers to the unit of
information passed by TCP to IP (Internet protocol). IP
headers are attached to these TCP segments to form IP
datagrams, i.e. TCP segments are transferred to the
receiver within IP datagrams as the information units used
by IP. Each uncorrupted TCP segment including the hand
shaking segments, is acknowledged. To illustrate the
function of the flow control loop, it is assumed that the
user terminal A transmits one TCP segment to the user
terminal B. At the network layer, the user terminal A adds
an IP header to this TCP segment to form an IP datagram.
This datagram is converted into standard ATM cells in the
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 13 -
access node AN1 located at the edge of the ATM network ANW.
The cells of the datagram are then routed through the ATM
network to the access node AN2 of the user terminal B. This
access node reconstructs the original IP datagram from the
arriving cells and sends the IP datagram to the user
terminal B. The user terminal B removes the IP header to
reveal the TCP segment. If the segment is received
correctly, the user terminal B sends an acknowledging TCP
segment ACK back to the user terminal A.
TCP is one of the few transport protocols that natively has
a congestion control mechanism. The preferred embodiment of
the present invention relies on this known TCP control
mechanism. Therefore, this mechanism is described briefly
in the following.
TCP congestion control is based on two variables: the
receiver's advertised window (Wrcvr) and the congestion
window (CNWD). The receiver's advertised window is
maintained at the receiver as a measure of the buffering
capacity of the receiver, and the congestion window is
maintained at the transmitter as a measure of the capacity
of the network. The TCP source can never transmit more
segments than the minimum of the receiver's advertised
window and the congestion window.
The TCP congestion control method comprises two phases:
slow start and congestion avoidance. A variable called
SSTHRES (Slow Start Threshold) is maintained at the source
to distinguish between the two phases. The source starts to
transmit in the slow start phase by sending one TCP
segment, i.e. the value of CWND is set to one at the
beginning. When the source receives an acknowledgment, it
increments CWND by one, and, as a consequence, transmits to
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 14 -
more segments. In this way the value of CWND doubles every
round trip time during the slow start phase, as each
segment is acknowledged by the destination terminal. The
slow start phase ends and the congestion avoidance phase
begins, when CWND reaches the value of SSTHRES.
If a data packet is lost in a TCP connection, the source
does not receive an acknowledgment and performs a loss
recovery operation.
By duplicating the acknowledgments, the TCP source can be
made to slow down its output rate. This is based on the
fast retransmission and fast recovery algorithms which the
source automatically performs after receiving a certain
number of duplicate acknowledgments. These algorithms are
widely implemented in different TCP versions. According to
the algorithms, the source performs, after having received
a predetermined threshold number of acknowledgments (e. g.
three acknowledgements), a retransmission of what appears
to be the missing segment, without waiting for the expiry
of a retransmission timer (fast retransmission algorithm).
After this, the source performs congestion avoidance,
instead of slow start, in order not to reduce the data flow
abruptly (fast recovery algorithm).
Fig. 2 shows a general diagram of an intermediate node
connected to a TCP source A and a TCP destination B, which
both may be workstations or the like. In the intermediate
node, a congestion is shown as a black star, a passing data
packet as a solid square, and a data packet lost due to the
congestion as a doted square.
According to the preferred embodiment of the present
invention, a Wireless-ECN (WECN) control means C is
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 15 -
provided in the intermediate node, which is arranged to
mark a data packet with an explicit wireless congestion
notification (WECN) immediately after a packet loss has
occurred due to a buffer overflow which may be detected by
a detecting means (not shown). The detecting means may be
included in the control means C or may be a separate means
in the intermediate node.
If a first lost packet due to a buffer overflow in the
intermediate node or router is detected within a
transmission window of the TCP source A, a WECN is added in
the header of the immediately following passing packet. The
required time for this operation is available due to the
dropped data packet which results in additional buffer
time. Thus, the WECN is added as quickly as possible after
a packet loss, such that the network congestion can be
alleviated as soon as possible.
Furthermore, an arrow at the bottom of Fig. 2 shows the
transmitting path of the WECN, wherein the TCP destination
B sets a WECN flag in the header of an acknowledgment
packet in response to the receipt of a WECN data packet, to
thereby notify the congestion in the intermediate node.
Each node in the network should be able to add the WECN to
thereby indicate a congestion as soon as a packet loss
occurs. To reduce redundant adding of WECN, only one WECN
message is required to be set in a node, which is
sufficient to notify the congestion. However, the WECN,
which may be a single WECN bit, may be added in the
following packets belonging to the same transmission or
congestion window by different ones of successive routers
passed by the data packets. As it takes a round-trip time
from the first added WECN to reach the source A and the
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 16 -
condition and buffer occupancy in each network node usually
various greatly, not only one WECN is usually set in a
transmission window during a round-trip time, because the
first lost packet in each intermediate node may not occur
at the same time. Thus, each WECN added in a transmission
window belongs to a different transmitting network node
which is allowed to add the WECN only once.
Fig. 3 shows a general diagram of an intermediate node 1
and an intermediate node 2, successively connected in the
direction of the forward path. In the present case, both
intermediate nodes 1 and 2 are congested. A WECN data
packet having an added WECN is shown as a hatched square.
According to Fig. 3, a control means C1 arranged in the
intermediate node 1 adds a WECN to the second data packet,
since the first data packet is lost due to the congestion.
Furthermore, the third data packet is also lost due to the
congestion. However, since the intermediate node 1 is only
allowed to add the WECN once, the first data packet remains
without a WECN addition. The data packet sequence is then
transmitted via the forward path to the intermediate node
2, where the fifth and sixth data packets are lost due to
the congestion. Accordingly, a WECN is added to the seventh
data packet by a control means C2 of the intermediate node
2.
The TCP destination B receives the data packet sequence
comprising the WECN packets number 2 and 7 and sets the
WECN flags of the corresponding acknowledgment packets to
be returned to the TCP source A.
In the forward path, the successive routers may not erase a
WECN bit in arriving packets, to thereby maintain the WECN
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 17 -
compliance in the network. As the TCP destination B sets a
WECN flag in the TCP header of an acknowledgment packet in
response to each IP packet with an added WECN bit, the TCP
source A may receive a plurality of WECN packets coming
from different intermediate nodes within a congestion
window. Since the main function of WECN is to initiate a
congestion control, i.e. to reduce the congestion window,
only once in a transmission window in the event of a
network congestion, these multiple WECN messages also
provide a robustness against the possibility of dropping a
WECN packet in the bi-directional transmitting path.
In order to comply with the currently proposed ECN
mechanism in the IETF draft, the congestion experienced
information should be kept in the regular headers of an IP
packet, since the processing of the regular headers in IP
packets is more efficient than processing the header
information in IP options. In the ECN mechanism, bit No. 6
and bit No. 7 of the IPv4 TOS octet are designated as the
ECT bit and the CE bit, respectively. In addition thereto,
bit No. 5 in the IPv4 TOS octet can be chosen as the WECN-
Echo flag used to indicate congestion packet losses by
intermediate routers or other network elements. Thereby, a
different window reduction can be initiated by the WECN
congestion control.
Accordingly, when the TCP destination B receives a CE data
packet, it sets the ECN-Echo flag in the TCP header of the
subsequent ACK packet. According to the different CE bit
settings for the ECN and the WECN packets, two different
flags of the TCP header are requirted. Since bit No. 9 is
designated as the ECN-Echo flag of the TCP header, bit No.
8 can be used as the WECN-Echo flag. Thus, if any of the
received data packets are CE packets with bit 5 setting,
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 18 -
then the returned ACK has its WECN-Echo flag set. If any of
the received data packets are CE packets with bit 7
setting, then the returned ACK has its ECN-Echo flag set.
As only one WECN is allowed to be added in an intermediate
node, the number of WECN packets will not exceed the number
of total network nodes to be passed by the data packet.
Thereby, the burden of providing an interphase facility
between IP and TCP at the destination side can be relieved.
Thus, according to the above proposed WECN mechanism, since
non-congestion packet losses are not allowed to initiate
congestion control for the consideration of decoupling
congestion control and retransmission strategies, end nodes
detect dropped data packets by receiving a WECN message set
by the intermediate network nodes just in times of buffer
overflow, wherein the congestion response of the end nodes
to a received CE packet is at least as strong as the
congestion response to a dropped data packet which is
independent of congestion control. There is also no need of
particular implementations of TCP related to the ECN
mechanism proposed by ITEF, wherein TCP requires a less
conservative response as compared to the case of a dropped
packet, especially over small time scales, since a buffer
overflow has not yet occurred.
The additional requirement for the TCP source A to react to
multiple WECN acknowledgment packets is that it should not
repeat the reduction of the congestion window since the
packet was probably dropped before the TCP source A has
reduced its congestion window in response to an earlier
WECN acknowledgment packet. Thus, the TCP source A should
react to a WECN acknowledgment packet at most once per
round-trip time. This can be achieved by adapting the TCP
source A in such a manner that it reacts to a subsequent
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 19 -
WECN acknowledgment packet only after the outstanding data
packets, transmitted before the TCP source A entered into a
loss recovery phase upon receiving the first WECN
acknowledgment packet, have all been acknowledged. Like in
the ECN mechanism, the TCP could be changed so as to
provide a negotiation phase during setup to determine if
both end nodes are WECN capable.
The WECN mechanism according to the preferred embodiment of
the present invention leads to an independence of the TCP
from the packet loss as an indicator of congestion. Since
the TCP uses the WECN message to invoke congestion control
whenever a packet loss occurs, only a retransmission
mechanism is started as a response to a packet loss without
a WECN message, such that the TCP data flow rate is not
affected in such a case. This is very useful in wireless or
mobile networks, since the network itself has the function
of distinguishing different sources of packet losses. Thus,
the TCP congestion window can only be reduced by the WECN
message which is set due to congestion losses.
Moreover, the TCP source A may only react once during a
round-trip time and generally to the earliest one of
received WECN and ECN ACKs. If an ECN ACK is received at
first, the conventional congestion control is invoked at
the TCP source A. However, when some packet losses due to
congestion arrive before the ECN messages within a round-
trip time, the WECN messages added just upon the first
packet loss caused by the congestion will arrive in time to
initiate a general congestion control e.g. with half
reduction of window size instead of waiting for the later
arrival of the ECN packets. Thus, WECN leads to a
congestion control which is completely free from non-
congestion lost packets and high performance is assured
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 20 -
without having to resort to islands of different sources of
packet losses in wireless and mobile networks.
The WECN mechanism according to the preferred embodiment of
the present invention not only leads to a decoupling of
congestion control from loss recovery but also contributes
to the loss recovery phase. Since it is required that the
WECN is set immediately after the packet loss occurs, it is
very likely that the WECN acknowledgement packet arrives
before the threshold number of duplicate acknowledgement
packets. If this WECN message is used to trigger the
transmission or retransmission of any data packets, it can
increase the speed of entering the TCP recovery phase so as
to quickly retransmit congestion-related lost packets.
However, the ECN cannot always be added immediately after a
lost packet in case there are several successive packet
losses or disordered packets before the arrival of the ECN
message. Thus, it cannot be judged which lost packet has
triggered the addition of the ECN or if it was added
without delay. Thus, it is suggested only applying ECN to
quickly enter into the loss recovery phase, before the
threshold duplicate acknowledgement packets arrive.
Otherwise, data transmission during loss recovery should be
performed on the basis of the traditional fast
retransmission and fast recovery algorithm.
Fig. 4 shows a diagram of transmissions between the TCP
source A and the TCP destination B, wherein the
transmission of a first message X and a second message Y is
depicted as a plurality of forward and backward arrows each
indicating the transmission of a data packet and an
acknowledgement packet (ACK), respectively. In the diagram,
the transmission proceeds from the top to the bottom and
corresponding ACK messages are indicated by the backward
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 21 -
arrows from the destination B to the source A. Thus, a
transmission window is indicated by the time period
(vertical direction) from the starting point of a forward
arrow to the end point of the corresponding backward arrow.
During the transmission of the message X, the second data
packet is lost due to a congestion loss 1 notified to the
TCP destination B by the subsequent third data packet.
Thus, an acknowledgement packet with a set WECN-Echo flag
is returned to the TCP source A before any ECN message has
arrived. Based on the received acknowledgment and duplicate
acknowledgement with the set WECN-Echo flag, the TCP source
A performs a congestion control by reducing SSTHRES to half
of the current CWND value. Then, CWND is set equal to the
new SSTHRES.
In the present case, an ECN is set delayed in the fifth
data packet, such that an ECN-Echo flag is set in the
corresponding ACK packet. At the TCP source A, the ACK with
ECN-Echo flag is ignored, since the WECN ACK has already
been received in the same transmission window (i.e. forward
and backward arrow relating to the transmission of the
message Y). Nevertheless, the conventional TCP fast
retransmission algorithm is started for the lost packet 1,
since the threshold number of duplicate ACKs, i.e. 3 ACKs,
has been received.
Furthermore, an additional congestion loss 2 occurs at the
sixth data packet, such that a WECN is set in the seventh
data packet so as to initiate an ACK with a WECN-Echo flag.
However, the WECN message is also ignored at the TCP source
A, since the ACK with WECN-Echo flag is also received
within the above same transmission window. Again, the
conventional TCP fast retransmission algorithm is performed
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 22 -
for the lost packet 2 after the receipt of 3 duplicate
ACKs.
Fig. 5 shows a diagram similar to the diagram according to
Fig. 4, wherein a non-congestion loss 1 occurs during the
transmission of the first data packet of the message X. In
the present case, the treshold number of duplicate
acknowledgements arrive at the TCP source A before the
receipt of the ECN acknowledgment. Furthermore, a
congestion loss 2 occurs during the transmission of the
sixth data packet of the message X.
Since no WECN is added in response to the non-congestion
loss 1, the conventional fast retransmission algorithm is
performed, i.e. the lost data packet is retransmitted after
three duplicate acknowledgments have been received.
Moreover, the conventional congestion control, e.g.
reduction of SSTHRES to 0.625CWND and setting of a new CWND
equal to the new SSTHRES, is performed in response to the
receipt of the ECN acknowledgment. In the present example,
a WECN is set in response to the non-congestion loss 2.
However, the corresponding WECN ACK is ignored, since it is
received within the same transmission window. Nevertheless,
due to the conventional retransmission algorithm, the lost
packet 2 is retransmitted after the receipt of three
duplicate acknowledgements.
Fig. 6 shows another transmission example, wherein an ECN
is set in a previous transmission window (message X) due to
a detected congestion and, despite of the conventional
congestion performed in response to the receipt of the ECN
ACK, a subsequent packet loss occurs in the following
transmission window (message Y).
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 23 -
Due to the congestion loss, a WECN is set in the following
data packet, and a WECN congestion control, i.e.
SSTHRES=1/2CWND and CWND=SSTHRES, according to the
preferred embodiment of the present invention is performed
in response to the receipt of the WECN ACK. Moreover, the
conventional fast retransmission is performed after the
receipt of three duplicate acknowledgements, to thereby
retransmit the lost data packet. The subsequent ECN message
is ignored due to its receipt within the same transmission
window.
Fig. 7 shows a transmission example in which an ECN message
is received before a subsequent non-congestion packet loss
1 and congestion packet loss 2 within the same transmission
window.
According to Fig. 7, a conventional congestion control is
performed in response to the receipt of the ECN ACK.
However, the non-congestion loss 1 does not initiate a WECN
message. After three duplicate ACKs, the conventional
retransmission of the non-congestion loss 1 is performed.
The subsequent WECN ACK set in response to the congestion
loss 2 is ignored at the TCP source A, since it has
occurred in the same transmission window. Nevertheless,
again, the conventional retransmission is performed after
the receipt of three duplicate acknowlegments.
Fig. 8 shows a case in which the second and sixth data
packets of a message X are lost due to congestion, and the
seventh data packet is a disordered packet. Thus, WECN
messages are set in the third and eighth data packet, since
the seventh data packet is a disordered one. The congestion
control according to the preferred embodiment of the
present invention is then performed in response to the
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 24 -
receipt of the first WECN ACK. Thereafter, a conventional
retransmission is performed in response to the receipt of
three duplicate ACKs. However, the second WECN ACK which is
accompanied by one duplicate WECN ACK (due to the
disordered packet) is ignored, since it is received within
the same transmission window. Nevertheless, the conven-
tional retransmission is again performed for the lost
packet 2 after the receipt of three duplicate ACKs. Since
the disordered packet cannot be identified, a retrans-
mission thereof is not possible.
In Fig. 9, a further transmission example is shown, wherein
a non-congestion loss 1 (first data packet) and a later
congestion loss 2 (fifth data packet) followed by a non-
congestion loss 3 (sixth data packet) occur during the
transmission of a message X.
The first non-congestion loss 1 does not initiate any
congestion control procedure and leads to a conventional
retransmission after the receipt of three duplicate ACKs.
Due to the immediately following non-congestion loss, the
WECN set in the sixth data packet in response to the
congestion loss 2 is not received at the TCP destination B.
Since the sixth data packet is lost due to the non-
congestion loss 3, no WECN is set in the seventh data
packet. Thus, the WECN ACK is transmitted in response to
the receipt of the eighth data packet, to thereby initiate
the congestion control procedure according to the preferred
embodiment of the present invention. Due to the lost sixth
and non-WECN seventh data packet, the WECN ACK is
accompanied by two duplicate WECN ACKs. Thereafter, the
losses 2 and 3 are retransmitted according to the
conventional retransmission algorithm.
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 25 -
Finally, Fig. 10 shows a case in which three congestion
losses 1 to 3 occur during the transmission of the message
X, wherein the corresponding WECN are set delayed.
According to the conventional retransmission, each of the
three lost data packets 1 to 3 is retransmitted by the TCP
source A in response to the receipt of the respective three
duplicate ACKs (retransmission of lost packet 3 not shown).
In the present case, the congestion control procedure
according the preferred embodiment of the present invention
is delayed until the first WECN ACK has been received.
However, the subsequent WECN ACK within the same
transmission window is ignored.
The above described ECN-based overload control method may
be utilized in any packet network. According to the above
description, the overload control can be performed without
substantially changing the conventional overload control
processing of the TCP.
Although the invention has been described here in
connection with the preferred embodiment according to the
attached drawings, it is clear that the invention is not
limited to these examples, as it can be varied in several
ways within the scope of the attached claims. As indicated
above, a prerequisite for a user terminal is that it
acknowledges correctly received (i.e. uncorrupted) data
units. Therefore, the idea can in principal be applied to
any other protocol which sends acknowledgments. As already
said, the user terminals may have a wireless access to the
network.
In summary, the invention relates to a method for
controlling overload in a packet-switched network,
CA 02372023 2001-10-26
WO 00/65782 PCT/EP99/02856
- 26 -
especially a mobile or wireless network where the
transmission control protocol (TCP) is used as the
transport layer protocol. A congestion notification
information is added to a data packet following a data
packet lost due to a buffer overflow. This is an effective
way to improve TCP performance in wireless and mobile
networks, since congestion control can be performed
completely independent from retransmissions. The proposed
mechanism provides a simple way of introducing TCP
congestion avoidance control strategies into wireless and
mobile networks. In addition, the congestion notification
information should be added at least not later than a
threshold number of following packets to thereby fasten the
rate of congestion control initiation and loss recovery due
to congestion.