WO2003005629A1 - Apparatus and method for delivery of packets in multi-hop wireless networks - Google Patents

Abstract

A system and method are disclosed for reducing data loss in wireless networks resulting from corruption of one or more wireless links or resulting from failure of an intermediate connecting node. The wireless network, which includes at least one intermediate node (15) having an internal buffer (71) for continually buffering data passing from source node (11) to destination node (21), establishes an alternate path bypassing the failed node. Lost data packets are locally retransmitted in response to receipt of an error message indicating node failure, or in response to a retransmit request resulting from data corruption over a wireless link. Intermediate nodes lacking such internal buffering serve to relay requests and messages upstream to nodes with internal buffering.

Description

Title: Apparatus and Method for Delivery of Packets in Multi-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 multi-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. Multi-media transfer, in particular, is an example of an application that is adversely affected by loss of data packets. Multi-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 multi-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. Several research efforts have been undertaken to optimize routing protocols in multi-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 multi-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 multi-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 multi-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 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 describing data transmission using the wireless network of Fig. 7. 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 (N₀₁), to a second intermediate node 15 (N₀₂), to a third intermediate node 17 (N₀₃), to a fourth intermediate node 19 (N₀ ), 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 timeout 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 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. 1, 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π) and a second alternate connecting node 25 (Nι ).

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 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 packet(s) would be located in the buffer(s), and the packet(s) 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 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., 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 arrived 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 arrives 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. 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. 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. What is claimed is:

Claims

1. A communication method, suitable for use in a wireless network for reducing data loss resulting from the failure of an intermediate node during the transmission of data packets from a source node (11) to a destination node (21), said communication method including the steps of

establishing an initial communication path from the source node (11) to the destination node (21), said initial communication path comprising two or more intermediate nodes;

transmitting a data packet (29a) from the source node (11) through a first intermediate node (13);

characterized in that said method further comprises the steps of:

storing said data packet (29a) at said first intermediate node (13) as said data packet (29a) passes through said first intermediate node (13);

detecting failure of a second intermediate node (17) in response to said step of transmitting said data packet;

establishing an alternate communication path to the destination node (21) bypassing said second intermediate node (17) in response to said step of detecting failure of said second intermediate node (17); and

retransmitting said data packet (29a) stored at said first intermediate node (13) via said alternate communication path.

2. The communication method of claim 1 wherein said step of storing comprises the step of buffering said data packet (29a) into a selected one of a plurality of buffers (71), said selected buffer corresponding to a priority class of said data packet (29a).

3. The communication method of claim 1 further comprising the step of storing said buffered data packet (29a) at an alternate connecting node (23) disposed in said alternate communication path.

4. The communication method of claim 1 further comprising the step of notifying said first intermediate node (13) as to data packets received from said second intermediate node (17).

5. The communication method of claim 1 wherein said step of transmitting said data packet (29a) via said alternate communication path comprises the step of scheduling transmission in accordance with priority classes in an out queue.

6. The communication method of claim 2 wherein said step of transmitting said data packet (29a) buffered at said first intermediate node (13) comprises the step of transmitting said data packet (29a) prior to transmitting a second data packet (29b) buffered in a lower-priority class buffer at said first intermediate node (13).

7. The communication method of claim 2 wherein said step of transmitting said data packet (29a) buffered at said first intermediate node (13) comprises the step of transmitting said data packet (29a) subsequent to transmitting a second data packet (29b) buffered in a higher-priority class buffer at said first intermediate node (13).

8. The communication method of claim 4 wherein said step of notifying said first intermediate node (13) is performed by a node in said alternate communication path.

9. The communication method of claim 4 wherein said initial communication path includes a third intermediate node (15) disposed between said first and second intermediate nodes, said third intermediate node (15) comprising means for relaying a message.

10. The communication method of claim 1 wherein said alternate communication path comprises a third intermediate node (19) disposed in said initial communication path between said second intermediate node (17) and the destination node (21).

11. The communication method of claim 10 further comprising the step of said third intermediate node (19) recognizing a reconfigured transmission path in response to said step of transmitting said data packet buffered at said first intermediate node (13).

12. The communication method of claim 11 further comprising the step of said third intermediate node (19) notifying said first intermediate node (13) as to data packets received from said second intermediate node (17) in response to said step of said third intermediate node (19) recognizing a reconfigured transmission path.

13. The communication method of claim 1 wherein said step of detecting failure of said second intermediate node (17) comprises the step of receiving a retransmit message.

14. The communication method of claim 1 wherein said step of establishing an alternate communication path comprises the step of establishing a communication path from said first intermediate node (13) to the destination node (21).

15. A wireless communication network, suitable for transmitting data from a source node (11) to a destination node (21), said communication network including two or more intermediate nodes establishing an initial communication path between the source node (11) and the destination node (21), characterized in that a first said intermediate node (13) includes a buffer for storing at least a portion of the data which has passed through said first intermediate node (13).

16. The wireless communication network of claim 15 wherein said internal buffer comprises buffers (71) of at least two different priority classes.

17. The wireless communication network of claim 15 wherein said first intermediate node (13) further comprises processor means (79) for responding to a retransmission request (49).

18. The wireless communication network of claim 15 wherein a second said intermediate node (27) includes means for relaying a message.

19. The wireless communication network of claim 15 wherein said first intermediate node (13) comprises a kernel configured to buffer said portion of data passing through said first intermediate node (13).

20. A communication method, suitable for reducing data loss resulting from the failure of a wireless link between a source node (11) and a destination node (21), said communication method including the steps of

establishing a communication path from the source node (11) to the destination node (21), said communication path comprising at least a first intermedi ate node ( 13 ) ;

transmitting a data packet from the source node (11) through said first intermediate node (13);

characterized in that said communication method further comprises the steps of: storing said data packet at said first intermediate node (13);

receiving a retransmit message (49) at said first intermediate node (13) requesting a data packet (29b) identified as missing; and

transmitting said data packet (29b) stored at said first intermediate node (13) in response to said step of receiving said retransmit message (49).

21. The communication method of claim 20 further comprising the step of determining that said data packet stored at said first intermediate node corresponds to said data packet (29b) identified as missing.

22. The communication method of claim 20 wherein said step of storing comprises the step of buffering said data packet into a selected one of a plurality of local buffers, said selected local buffer corresponding to a priority class of said data packet.

23. The communication method of claim 20 further comprising the steps of:

receiving said retransmit message at a second intermediate node (27); and

relaying said retransmit message from said second intermediate node to said first intermediate node (13).

24. The communication method of claim 23 further comprising the steps of:

checking a local buffer in said second intermediate node (27) for said data packet identified as missing in said retransmit message; and

determining that said data packet identified as missing is not found in said second intermediate node local buffer (27).