Note: Descriptions are shown in the official language in which they were submitted.
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
Title: Apparatus and Method for Delivery of Packets in Mufti-Hop Wireless
Networks
FIELD OF THE INVENTION
This invention relates to wireless communication systems and, in particular,
to
a system and method for reducing data transmission loss when a link or node
failure
occurs.
BACKGROUND OF THE INVENTION
Wireless mufti-hop mobile networks characteristically lack a definite
infrastructure and, consequently, experience frequent link failures caused by
node
mobility and interference in wireless links. This poses a problem in ensuring
Quality
of Service (QoS) in such networks. As understood in the relevant art, end-to-
end
retransmissions typically can not satisfy deadlines for timely delivery of
packets.
Mufti-media transfer, in particular, is an example of an application that is
adversely
affected by loss of data packets. Mufti-hop wireless networks can be found,
for
example, in applications for personal area networking, military applications,
taxicab
networks, networks in conference rooms, and emergency applications including
"911
calls" coordinating between groups involved in search and rescue missions, or
via a
network established between ambulance operators at the scene of an accident
and
doctors at a remote hospital.
Accordingly, the network topology of a wireless mobile mufti-hop network
changes over time where network nodes are mobile and links are established and
then
terminated. Transient failures in such wireless links are also more probable
in
comparison to wired networks because wireless links are more susceptible to
interference. Routing is therefore a difficult problem in such networks, and a
path
from a source to a destination can not always be assured for an entire
communication
session.
CONFIRMATION COPY
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
Several research efforts have been undertaken to optimize routing protocols in
mufti-hop networks. These routing protocols optimize routes from a source node
to a
destination node in the presence of link failures caused by node mobility or
link
degradation due to transmission interference. Various criteria have been
suggested to
establish the communication path using such optimization procedures. Some of
these
criteria include power conservation for mobile systems and congestion
reduction.
Similarly, adaptations to TCP/UDP have been suggested to transport packets in
an
mufti-hop network.
Prior research efforts in the area have addressed routing issues without
considering localized retransmissions and prioritized delivery of packets. The
protocols discussed in the relevant art depend on higher layers, such as TCP,
to deal
with packet loss. Such approaches rely on end-to-end retransmission of lost
packets
and, as such, are not suited for ensuring QoS in a wireless mufti-hop network,
in
which link failure happens frequently, as this results in intolerable delay.
Additionally, such approaches do not provide for prioritization in the
delivery of
packets because the packets flowing from a source to a destination are handled
similarly. This is not the optimal methodology as different micro-flows within
a flow
may have different delivery deadlines. Prioritized delivery in wired networks
is
known in the relevant art, but delivery on time cannot be assured in a
wireless
network because of the high probability of transmission error.
What is needed is an improved method for providing on-time packet delivery,
with a high quality of service, in mobile mufti-hop wireless networks.
SUMMARY OF THE INVENTION
The present invention results from the observation that data loss in wireless
networks can be mitigated by network-layer buffering data packets at
intermediate
nodes in the transmission path, and locally retransmitting lost data packets.
The
wireless network, formed using one or more intermediate nodes having internal
-2-
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
buffers for continually buffering data passing from source to destination
nodes,
establishes an alternate path bypassing the failed node and retransmitting
lost data
packets in response to receipt of an error message. If a connecting node lacks
an
internal buffer, the error message is transmitted upstream to a node having
buffered
data packets which can provide the missing data.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention description below refers to the accompanying drawings, of
which:
Fig. 1 is a diagrammatical representation of a wireless network showing a
communication path formed by connecting nodes;
Fig. 2 is a flow diagram describing data transmission using the wireless
network of Fig. 1;
Fig. 3 is a diagram of a connecting node of Fig. 1 showing an internal buffer
for buffering data passing through the node;
Fig 4 is a diagram of a connecting node of Fig. 1 showing high, normal, and
low-priority transmission buffers for buffering data passing through the node;
Fig. 5 is a flow diagram describing in greater detail the process of
transmitting
undelivered data packets as represented in the flow diagram of Fig. 2;
Fig. 6 is a diagrammatical representation of a wireless network including a
connecting node without internal buffering;
Fig. 7 is a diagrammatical representation of a wireless network including a
failed wireless link; and
Fig. 8 is a flow diagram descmbing data transmission using the wireless
network of Fig. 7.
-3-
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT
There is shown in Fig. 1 a simple wireless network 10, including a source
node 11 (S) and a destination node 21 (D). A user of the wireless network 10
may
transmit data by establishing an initial communication path between the source
node
11 and the destination node 21 via a series of intermediate connecting nodes.
The
initial communication path may include, for purpose of illustration, path
segments
from the source node 11 to a first connecting node or intermediate node 13
(No,), to a
second intermediate node 15 (No2), to a third intermediate node 17 (No3), to a
fourth
intermediate node 19 (No4), and then to the destination node 21. The initial
communication path may be established by a serial combination of: a wireless
link 31
between the source node 11 and the first intermediate node 13, a wireless link
33
between the first intermediate node 13 and the second intermediate node 15, a
wireless link 35 between the second intermediate node 15 and the third
intermediate
node 17, a wireless link 37 between the third intermediate node 17 and the
fourth
intermediate node 19, and a wireless link 39 between the fourth intermediate
node 19
and the destination node 21.
During transmission of data over the initial communication path, one or more
of the intermediate nodes 13-19 may fail. Failure may result, for example,
from a
cessation of operation of a connecting node (e.g., equipment failure or power-
down),
from a mobile node moving out of the range of an associated wireless link, or
from an
adverse propagation environment (e.g., atmospheric precipitation or
turbulence) at the
affected intermediate node. Accordingly, failure of a intermediate connecting
node
would cause one or more of the wireless links 31-39 to be lost, resulting in a
break to
the initial communication path with loss or corruption of data as a
consequence.
Detection of node failure is well-understood in the relevant art and may
utilize a time-
out mechanism, for example.
Operation of the present inventive method can be described with additional
reference to the flow diagram of Fig. 2 in which the initial communication
path is
-4-
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
established in a manner well-known in the relevant art, at step 51, and a data
packet
stream 29 is configured for transmission in accordance with an appropriate
protocol.
As transmission of the data packet stream 29 to the destination node 21 is
initiated via
the initial communication path, each of the individual data packets in the
data packet
stream 29 successively passes through each of the intermediate nodes 13-19. At
least
one intermediate node in the initial communication path is configured such
that the
data packets are buffered for possible local retransmission using priority
queuing, at
step 57, as described in greater detail below. If the initial communication
path
remains intact, there is node failure detected, at decision block 59, the
system stands
by for the next transmission, at step 61, and receives data packets when
provided, at
step 53.
If an intermediate node fails, causing a disruption to one or more of the
wireless links 31-39 forming the initial communication path, an alternative
connecting
path is established, at step 63, using a method known in the relevant art, and
the
remaining undelivered data packets are transmitted to the destination node 21
to
complete the transmittal of the data packet stream 29, at step 65. By way of
example,
if the third intermediate node 17 fails, the wireless links 35 and 37 are
lost, as
indicated by dotted lines in Fig. l, and the initial communication path is
thereby
broken. The second intermediate node 15 is notified of the failure and an
alternate
path, bypassing the failed third intermediate node 17, is found to the
destination node
21. Such an alternate path may include, for example, a first alternate
connecting node
23 (N,1) and a second alternate connecting node 25 (N12).
A new wireless link 41 can be formed between the second intermediate node
15 and the first alternate connecting node 23, another new wireless link 43
can be
formed between the first alternate connecting node 23 and the second alternate
connecting node 25, and a new wireless link 45 can be formed between the
second
alternate connecting node 25 and the fourth intermediate node 19. The
remaining
-5-
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
undelivered data packets are then transmitted to the destination node 21, at
step 67, as
described in greater detail below. If the transmission session has not been
completed,
at decision block 61 in Fig. 2, operation returns to step 53 where the next
portion of
the data packet stream 29 is configured for transmittal.
In a preferred embodiment, each of one or more of the intermediate nodes 13-
19 includes at least one internal buffer for continuously buffering data
packets which
pass through the respective connecting node. As exemplified by the second
intermediate node 15, shown in greater detail in Fig. 3, an internal buffer 71
is
included for storing a number of data packets. The size of the buffer 71 is
dependent
upon the amount of spare memory available in the second intermediate node 15
for
use for this function and is determined by one or more factors, including the
bandwidth of the application and mobility rate. If sufficient memory is
available, the
size of the buffer 71 can be increased to handle relatively higher rates of
data
transmission through the corresponding connecting node and to accommodate data
packets arriving during the period of alternate path discovery.
The buffer 71 can be implemented as a 'software' buffer comprised of a
portion of the memory resident in the second intermediate node 15, or can be
provided as a hardware component, such as a RAM, in the second intermediate
node
15. The software buffer can be implemented by reconfiguring the node kernel to
do
the buffering. That is, the reconfigured kernel functions to buffer and
prioritize the
packets, and to respond to retransmission requests. Such requests would be
parsed,
the packets) would be located in the buffer(s), and the packets) would be
scheduled
into an out queue, as is well-known in the relevant art. Alternatively, the
second
intermediate node 15 may include an optional processing unit 79 for
controlling the
identification, storage, and retransmission of the data packets in the buffer
71. As
transmitted data packets 29a, 29b,...,29n arrive on the wireless link 33 and
are routed
out on the wireless link 35, the buffer 71 also buffers the most recently-
transmitted
-6-
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
data packets 29a, 29b,...,29n in memory locations 71a, 71c, and 71e
respectively, for
example. The buffer 71 may follow a first-in-first-out protocol.
Alternatively,
buffering can be implemented on a per-flow basis, in which data packets of a
particular flow replace previously-buffered data packets of the same flow.
In the preferred embodiment, the intermediate nodes 13-19 each include three
internal buffers, as exemplified by buffers 73-77, as indicated in the diagram
of the
fourth intermediate node 19 in Fig. 4, the buffers comprising a portion of
available
memory or a discrete memory chip. In this configuration, the three buffers 73-
77 can
be used for segregating the received data packets 29a, 29b,...,29n into
different
transmission priority classes, for example, by providing a high-priority
buffer 73, a
normal-priority buffer 75, and a low-priority buffer 77. Thus, data packets in
the
high-priority buffer 73 may be queued for transmission ahead of data packets
in the
low-priority buffer 77 using a method known in the relevant art.
Fig. 5 is a flow diagram providing a more detailed description of the
operation
performed at step 65 of Fig. 2. From step 63, the alternate path between
intermediate
nodes 15 and 19 is established as shown in Fig. 1, for example, by utilizing
connecting nodes 15, 23, 25, and 19, at step 81. Data packets which now flow
along
the alternate path are accordingly, also buffered in the alternate connecting
nodes 23
and 25. The fourth intermediate node 19 is reconfigured with the establishment
of the
alternate transmission path. That is, data packets, originally transmitted
from the third
intermediate node 17 to a port 19a prior to failure of the third intermediate
node 17,
are instead transmitted from the second alternate connecting node 25 to a port
19b
subsequent to the failure of the third intermediate node 17. It can be
appreciated by
one skilled in the relevant art that the reconfigured fourth intermediate node
19 is the
first downstream node in the new transmission path which lies both in the
initial
communication path and in the alternate transmission path. When the fourth
intermediate node 19 receives a path establishment message for the same flow
(i.e.,
_7_
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
the data packet stream 29), the fourth intermediate node 19 recognizes that
the third
intermediate node 17 has failed and responds by notifying the second
intermediate
node 15 as to which data packets have been received by the fourth intermediate
node
19, at step 83. This is done to avoid the retransmission of duplicate data
packets.
For example, as illustrated in Fig. 4, the data packets 29a and 29n arnved at
the fourth intermediate node 19 prior to the failure of the third intermediate
node 17.
When the fourth intermediate node 19 recognizes the reconfigured transmission
path
(i.e., the data packet from the second intermediate node 15 arnves at the port
19b and
not 19a), a notification is sent to the second intermediate node 15 that data
packets
29a and 29n have been received. The second intermediate node 15 then checks to
determine which data packets sent to the third intermediate node 17 were not
received
by the fourth intermediate node 19 and determines that the data packet 29b was
not
received by the fourth intermediate node 19.
At step 85, data packets identified as missing are obtained from the nearest
upstream node, in the initial communication path, where the target node has
the
corresponding data buffered. The data packet 29b exemplifies a missing data
packet,
which is then retrieved from the buffer 71 in the second intermediate node 15
and
transmitted to the fourth intermediate node 19 by way of the alternate path,
at step 87.
The fourth intermediate node 19 transfers the data packets 29a, 29b, and 29n
to the
destination node 21. If the applicable transmission protocol requires ordered
delivery
of data packets, the data packet 29n is transferred to the destination node 21
only after
transferal of the data packet 29a. Or, if the applicable transmission protocol
does not
require ordered delivery, the data packet 29b, if buffered in the high-
priority buffer
73, is transmitted ahead of the data packets 29a and 29n which are buffered in
the
low-priority buffer 77. Additionally, the remaining portion of the data packet
stream
29 is transmitted via the alternate path, at step 87. Operation then returns
to step 61,
in Fig. 2.
_g_
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
In an alternative embodiment of the inventive method, shown in Fig. 6, the
wireless network 10 includes a non-buffered intermediate node 27, where there
have
not been provided in the intermediate node 27 memory resources for an internal
buffer. Consequently, the intermediate node 27 cannot buffer the data packets
passing
along the transmission path. However, the intermediate node 27 has the
capability for
passing messages upstream as well as a capability for finding alternate paths
in case
of node or link failure. If an intermediate node fails as discussed above, for
example,
the third intermediate node 17, a retransmit message 49 is received by the
intermediate node 27. Because the intermediate node 27 can not provide missing
data
packets in response to the node failure, the retransmit message 49 is sent
upstream to
the next intermediate node having internal buffers, such as the first
intermediate node
13, for example. The missing data packet(s), such as the data packet 29b shown
in the
illustration, is obtained from any of the buffers 73-77 and provided to the
requesting
node, here exemplified by the fourth intermediate node 19. If the missing data
packet
29b is not present in any of the buffers 73-77 of the first intermediate node
13, the
message is transmitted to the source node 11. In a network configuration where
none
of the intermediate nodes located between a failed node and the source node 11
includes internal buffers, missing data packets are obtained from the source
node 11
and transmitted to the requesting node, as described above.
In yet another alternative embodiment, the wireless link 37 in the wireless
network 10 has become degraded or otherwise unreliable, due to interference in
the
transmission medium for example, as indicated in Fig. 7. As a result, errors
may have
been introduced into the packet transmission between the third intermediate
node 17
and the fourth intermediate node 19. The corrective action can be described
with
additional reference to the flow diagram of Fig. 8 in which the initial
communication
path is established, at step 91, and data packets from the data packet stream
29 are
received at the intermediate nodes, at step 93, and buffered, at step 95.
-9-
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
No retransmission messages are received, at decision block 99, if the wireless
links 31-39 remain functional and the system stands by for transmission, at
step 101.
When the wireless link 37 becomes unreliable and produces transmission errors,
a
retransmit message is received and the third intermediate node 17 searches
internal
buffers 73-77 for the corresponding data packet, at step 103. If the data
packet is
found in one of the buffers 73-77, at decision block 105, the third
intermediate node
17 schedules the data packet for priority retransmission into an out-queue
(not
shown), at step 97. This transmission scheduling is done in accordance with
the
transmission priority of the data packet, as described above.
If the required data packet is not found in the internal buffers 73-77 of the
third intermediate node 17, at decision block 105, the next upstream node is
checked
for the requested replacement data, at step 107. If the requested data is
found, at
decision block 109, the data is transmitted, at step 97. If the requested data
is not
found, at decision block 109, a query is made as to whether the source node 11
has
been reached, at decision block 111. If the source node 11 has not been
reached,
operation proceeds to decision block 105. If the source node 11 has been
reached, at
decision block 111, and does not contain the required data packet, at decision
block
113, an optional error message may be issued to the originator of the data
transmission, at step 115, and operation proceeds to standby for the next
transmission
session, at step 101. If the requested data packet is available, at decision
block 113,
the data packet is scheduled and prioritized for transmission to the
destination node
21, at 97.
While the invention has been described with reference to particular
embodiments, it will be understood that the present invention is by no means
limited
to the particular constructions and methods herein disclosed and/or shown in
the
drawings, but also comprises any modifications or equivalents within the scope
of the
claims.
-10-
CA 02449532 2003-12-02
WO 03/005629 PCT/IB02/02432
What is claimed is:
-11-
