MXPA03010849A

MXPA03010849A - Apparatus and method for delivery of packets in multi-hop wireless networks.

Info

Publication number: MXPA03010849A
Application number: MXPA03010849A
Authority: MX
Inventors: Guo Yile
Original assignee: Nokia Inc
Priority date: 2001-06-30
Filing date: 2002-06-26
Publication date: 2004-11-22
Also published as: CN100411327C; RU2003134626A; JP2007251991A; CN1541466A; RU2298289C2; EP1415424A4; JP2004537206A; AU2002311547B2; CA2449532A1; JP4392033B2; WO2003005629A1; EP1415424A1

Abstract

Se describe un sistema y metodo para reducir perdida de datos en redes inalambricas que resulta de la corrupcion de uno o mas enlaces inalambricos o que resulta de falla de un nodo de conexion intermedio; la red inalambrica, la cual incluye por lo menos un nodo intermedio que tiene una memoria intermedia interna para almacenar temporalmente de manera continua datos que pasan desde el nodo de origen hacia el nodo de destino, establece una trayectoria alterna que desvia el nodo defectuoso; los paquetes de datos perdidos son retransmitidos localmente en respuesta a la recepcion de un mensaje de error que indica la falla del nodo, o en respuesta a una solicitud de retransmision que resulta de la corrupcion de datos sobre un enlace inalambrico; los nodos intermedios que carecen de dicho almacenamiento temporal interno sirven para retransmitir solicitudes y mensajes corriente arriba hacia nodos con almacenamiento temporal interno.A system and method for reducing data loss in wireless networks that results from the corruption of one or more wireless links or that results from failure of an intermediate connection node is described; the wireless network, which includes at least one intermediate node that has an internal buffer to temporarily store data continuously passing from the source node to the destination node, establishes an alternate path that deflects the defective node; lost data packets are retransmitted locally in response to the reception of an error message indicating the failure of the node, or in response to a retransmission request that results from data corruption on a wireless link; intermediate nodes that lack such internal temporary storage serve to relay requests and messages upstream to nodes with internal temporary storage.

Description

APPARATUS AND METHOD FOR DELIVERY OF PACKAGES IN WIRELESS NETWORKS WITH MULTIPLE SUCCESSIVE JUMPS FIELD OF THE INVENTION This invention relates to wireless communication systems and in particular, to a system and method for reducing loss in data transmission when a link or node failure occurs.

BACKGROUND OF THE INVENTION Successive multi-hop wireless mobile networks typically lack a definite infrastructure and consequently experience frequent link failures caused by node mobility and wireless link interference. This represents a problem to ensure Quality of Service (QoS) in these networks. As understood in the related art, end-to-end retransmissions typically can not meet deadlines for timely deliveries of packets. The transfer of multiple media, in particular, is an example of an application that is adversely affected by the loss of data packets. Wireless networks with multiple successive jumps can be found, for example, in applications for operation in networks of personnel area, military applications, taxi networks, networks in conference rooms, and emergency applications that include "911 calls" that they are coordinated between groups involved in search and rescue missions, or through a network established between ambulance operators at the scene of an accident and doctors at a remote hospital. As a result, the network topology of a network with multiple successive mobile and wireless jumps changes over time when the nodes in the network are mobile and links are established and then terminated. Transient failures in such wireless links are also more likely compared to wired networks because wireless links are more susceptible to interference. Therefore, routing is a difficult problem in such networks, and a path from an origin to a destination can not always be assured for a complete communication session. Various research efforts have been made to optimize routing protocols in networks with multiple successive jumps. 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 said optimization procedures. Some of these criteria include energy conservation for mobile systems and congestion reduction. Similarly, adaptations to TCP / UDP have been suggested for transporting packets in a network with multiple successive jumps.

Previous research efforts in the area have been directed to routing issues without considering localized retransmissions and delivery of prioritized packages. The protocols discussed in the corresponding art depend on higher layers, such as TCP, to handle packet loss. These methods are based on end-to-end retransmission of lost packets and as such, are not convenient for securing QoS in a network with multiple successive wireless jumps, in which the link failure happens frequently, as this results in a intolerable delay. Furthermore, these methods do not provide prioritization in the delivery of packages because the packets that flow from a source to a destination are handled in a similar manner. This is not the optimal methodology because different microflows within a flow may have different delivery deadlines. The prioritized delivery in wired networks is known in the corresponding art, but delivery on time can not be ensured in a wireless network due to the high probability of transmission error. What is needed is an improved method for providing packets on time, with a high quality of service, in mobile wireless networks with multiple successive jumps.

BRIEF DESCRIPTION OF THE INVENTION The present invention results from the observation that the loss of data in wireless networks can be mitigated by temporarily storing in a network layer data packets at intermediate nodes in the transmission path, and retransmitting lost data packets. The wireless network, formed using one or more intermediate nodes that have internal buffers to continuously temporarily store data passing from source to destination nodes, establishes an alternate path that diverts the defective node and retransmits lost data packets in response to the reception of an error message. If a connection node lacks an internal buffer, the error message is transmitted upstream to a node that has temporarily stored data packets that can provide the missing data.

BRIEF DESCRIPTION OF THE DRAWINGS The description of the invention hereinafter refers to the accompanying drawings, in which: Figure 1 is a schematic representation of a wireless network showing a communication path formed by connection nodes; Fig. 2 is a flow chart describing data transmission using the wireless network of Fig. 1; Figure 3 is a diagram of a connection node of Figure 1 showing an internal buffer for temporarily storing data passing through the node; Figure 4 is a diagram of a connection node of Figure 1 showing high, low and normal priority transmission buffers for temporarily storing data passing through the node; Figure 5 is a flowchart that describes in more detail the process for transmitting undelivered data packets as represented in the flowchart of Figure 2; Figure 6 is a schematic representation of a wireless network including a connection node without internal buffer; Figure 7 is a schematic representation of a wireless network including a defective wireless link; and Figure 8 is a flow chart describing data transmission using the wireless network of Figure 7.

DETAILED DESCRIPTION OF A PREFERRED MODALITY In Figure 1 a simple wireless network 10 is shown, which includes a source node 11 (S) and a destination node 21 (D). A user of the wireless network 10 can transmit data by establishing an initial communication path between the originating node 1 1 and the destination node 21 through a series of intermediate connection nodes. The initial communication path may include, for purposes of illustration, path segments from the origin node 1 1 to a first connection node or intermediate node 13 (N0i), to a second intermediate node 15 (N02), towards a third intermediate node 17 (N03), to a fourth intermediate node 19 (N04), and then to the destination node 21. The initial communication path can be established through a serial combination of: a wireless link 31 between the originating node 1 1 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 node of destination 21. During the transmission of data on the initial communication path, one or more of the intermediate nodes 13-19 may fail. The failure may result, for example, from a cessation of operation of a connection node (for example, equipment failure or shutdown), from a mobile node moving out of the scale of an associated wireless link, or from an environment of adverse propagation (for example, atmospheric precipitation or turbulence) in the affected intermediate node. Therefore, the failure of an intermediate connection node would cause one or more of the wireless links 31-39 to be lost, resulting in a break in the initial communication path with loss or corruption of data as a consequence. The detection of node failure is understood in the relevant art and may for example use an interruption mechanism. The operation of the inventive method herein can be described with further reference to the flowchart of Figure 2, in which the initial communication path is established in a manner known in the relevant art, in step 51, and configured a stream of data packets 29 for transmission in accordance with a suitable protocol. Because the transmission of the data packet stream 29 to the destination node 21 starts through the initial communication path, each of the individual data packets in the data packet stream 29 passes successively through each of the intermediate nodes 13-19. At least one intermediate node in the initial communication path is configured so that the data packets are temporarily stored for possible local retransmission using priority queuing, in step 57, as described in more detail below. If the initial communication path remains intact, node failure is detected, in decision block 59, the system waits for the next transmission, in step 61, and receives data packets when provided, in step 53. Its failure an intermediate node, causing an alteration to one or more of the wireless links 31-39 forming the initial communication path, an alternative connection path is established, in step 63, using a method known in the relevant art, and the rest of undelivered data packets are transmitted to the destination node 21 to complete the transmission of the data packet stream 29, in step 65. By way of example, if the third intermediate node 17 fails, the wireless links 35 and 37 are lost, as indicated by the dotted lines in Figure 1 and therefore, the initial communication path is broken. The second intermediate node 15 is notified of the fault and an alternate path is found, which diverts the third intermediate node 17 defective, towards the destination node 21. Said alternate trajectory may include, for example, a first alternate connection node 23 ( NH) and a second alternate connection node 25 (N 2). A new wireless link 41 can be formed between the second intermediate node 15 and the first alternate connection node 23, another new wireless link 43 can be formed between the first alternate connection node 23 and the second alternate connection node 25, and can form a new wireless link 45 between the second alternate connection node 25 and the fourth intermediate node 19. The rest of the undelivered data packets is transmitted to the destination node 21, in step 67, as described in detail later. If the transmission session has not been completed, in decision block 61 of Figure 2, the operation returns to step 53, where the next portion of the data packet stream 29 is configured for transmission. In a preferred embodiment, each or more of the intermediate nodes 13-19 includes at least one internal buffer to continuously temporarily store data packets which pass through the respective connection node. As exemplified by the second intermediate node 15, shown in more detail in Figure 3, an internal buffer 71 is included to store a number of data packets. The size of the buffer 71 depends on the amount of available backup memory. in the second intermediate node 15 to be used for this function and is determined by one or more factors, which include the bandwidth of the application and mobility speed. If enough memory is available, the size of the buffer 71 can be increased to handle relatively high data transmission rates through the corresponding connection node and to accommodate data packets arriving during the discovery period of the alternate path. The buffer 71 can be implemented as a "software" memory consisting of a portion of the memory resident in the second intermediate node 15, or it 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 core to perform temporary storage. That is, the reconfigured core functions to temporarily store and prioritize packets, and to respond to retransmission requests. Said requests would be analyzed syntactically, the packets would be placed in the buffers, and the packets would be programmed in an output queue formation, as is known in the relevant art. Alternatively, the second intermediate node 5 may include an optional processing unit 79 for controlling the identification, storage and retransmission of the data packets in the buffer 71. As the transmitted data packets 29a, 29b, ..., 29n arrive to the wireless link 33 and are routed to the wireless link 35, the buffer 71 also temporarily stores the most recently transmitted data packets 29a, 29b, ..., 29n at memory locations 71a, 71c and 71e respectively, for example . The buffer 71 may follow a first-in-first-out protocol. Alternatively, temporary storage can be implemented on a per flow basis, in which data packets from a particular stream replace data packets previously stored temporarily from the same flow. In the preferred embodiment, the intermediate nodes 13-19 each include three internal buffers, exemplified with the buffers 73-77, as indicated in the diagram of the fourth intermediate node 19 in FIG. 4, the buffers comprise a portion of available memory or a discrete memory chip. In this configuration, the three buffers 73-77 can be used to segregate the received data packets 29a, 29b, ..., 29n in different transmission priority classes, for example, by providing a high priority buffer 73 , a normal priority buffer 65, and a low priority buffer 77. In this way, the data packets in the high priority buffer 73 can be queued for transmission before data packets in the buffer of low priority 77 using a method known in the relevant art. Figure 5 is a flowchart that provides a more detailed description of the operation performed in step 65 of Figure 2. From step 63, the alternate path between intermediate nodes 15 and 19 is established as shown in the figure 1, for example, when using connection nodes 15, 23, 25 and 19, in step 81. The data packets that now flow along the alternating path are consequently also temporarily stored in the connection nodes. alternate 23 and 25. The fourth intermediate node 19 is reconfigured with the establishment of the alternate transmission path. That is, the data packets, originally transmitted from the third intermediate node 17 to a port 19a before failure of the third intermediate node 17, are instead transmitted from the second alternate connection node 25 to a port 19b subsequent to the failure of the third intermediate node 17. The person skilled in the art can appreciate that the fourth intermediate node 19 reconfigured is the first node downstream in the new transmission path which is located both in the initial communication path and in the alternating 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, in Step 83. This is done to avoid retransmission of duplicate data packets. For example, as illustrated in Figure 4, the data packets 29a and 29n arrived at the fourth intermediate node 19 before the failure of the third intermediate node 17. When the fourth intermediate node 19 recognizes the reconfigured transmission path (ie, the data packet of the second intermediate node 15 arrives at port 19b and does not to 19a), a notification is sent to the second intermediate node 15 that the 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. In step 85 , the 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 stored temporarily. 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 means of the alternate path, in step 87. The fourth node intermediate 19 transfers the data packets 29a, 29b, and 29n to the destination node 21. If the applicable transmission protocol requires the orderly delivery of data packets, the data packet 29n is transferred to the destination node 21 only after the transfer of data pack 29a. Or, if the applicable transmission protocol does not require an orderly delivery, the data packet 29b, if temporarily stored in the high priority buffer 73, is transmitted before the data packets 29a and 29n which are temporarily stored in the low priority buffer 77. In addition, the remaining portion of the data packet stream 29 is transmitted through the alternating path, in step 87. The operation then returns to step 61, in FIG. Alternative modality of the inventive method, shown in Figure 6, the wireless network 10 includes an intermediate node not temporarily stored 27, wherein memory resources for an internal buffer have been provided in the intermediate node 27. Accordingly, the intermediate node 27 can not temporarily store the data packets that pass along the transmission path. However, the intermediate node 27 has the ability to pass upstream messages as well as an ability to find 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 retransmission message 49 is received by the intermediate node 27. Because the intermediate node 27 can not provide missing data packets in response to the failure of the node, the retransmission 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 packets, such as the data packet 29b shown in the illustration, is obtained from any of the buffers 73-77 and is provided to the requesting node, 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 origin node 1 1. In a network configuration where none of the intermediate nodes located between a defective node and the source node 11 includes internal buffers, missing data packets are obtained from source node 1 1 and are transmitted to the requesting node, as described above. In another alternative embodiment, the wireless link 37 in the wireless network 10 has degraded or otherwise become uncertain, due to interference in the transmission medium for example., as indicated in Figure 7. As a result, errors may have been introduced in 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 the Figure 8, in which the initial communication path is established, in step 91, and the packets of data from the data packet stream 29 are received at the intermediate nodes, in step 93, and temporarily stored, in the Step 95 No retransmission messages are received in decision block 99, if the wireless links 31-39 remain functional and the system waits for transmission, in step 101. When the wireless link 37 becomes uncertain and produces transmission errors, it is received a retransmission message and the third intermediate node 17 searches the internal buffers 73-77 for the corresponding data packet, in step 103. If the data packet is in one of the buffers 73-77, in the block of decision 105, the third intermediate node 17 schedules the data packet for priority retransmission in an output queue formation (not shown), in step 97. This transmission schedule is made according to the priority of transmission of the packet of data, as described above If the required data packet is not found in the internal buffers 73-77 of the third intermediate node 17, in the dec block 105, the next upstream node is verified for the requested replacement data, in step 107. If the requested data is found, in decision block 109, the data is transmitted, in step 97. If not found the requested data, in decision block 109, a query is made as to whether if the origin node 1 1 has been reached, in the decision block 11 1. If the origin node 11 has not been reached, the operation proceeds to decision block 105. If source node 1 has been reached, in decision block 1 1 1, and it does not contain the required data packet, in decision block 1 13, a message can be issued optional error to the originator of the data transmission, in step 115, and the operation proceeds to wait for the next transmission session, in step 101. If the requested data packet is available, in decision block 113, the packet of data is programmed and prioritized for transmission to the destination node 21 at 97. Although the invention has been described with reference to particular embodiments, it will be understood that the present invention is in no way limited to the particular constructions and methods described herein and / or shown in the drawings, but rather that further comprises any modification or equivalent within the scope of the claims.

Claims

NOVELTY OF THE INVENTION CLAIMS

1. - A communication method, suitable for use in a wireless network to reduce data loss resulting from the failure of an intermediate node during transmission of data packets from a source node (11) to a destination node (21) ), said communication method includes the steps of: establishing an initial communication path from the source node (11) to the destination node (21), said initial communication path comprises 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 comprises the steps of: storing said data packet (29a) in said first intermediate node (13) as said data packet (29a) passes through said first intermediate node (13); detecting the 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) that deviates said second intermediate node (17) in response to said step of detecting the failure of said second intermediate node (17); and retransmitting said data packet (29a) stored in said first intermediate node (13) through said alternating communication path.

2. - The communication method according to claim 1, further characterized in that said storage step comprises the step of temporarily storing said data packet (29a) in a selected buffer of a plurality of buffers (71), said buffer selected corresponds to a priority class of said data packet (29a).

3. The communication method according to claim 1, further characterized in that it further comprises the step of storing said temporarily stored data packet (29a) in an alternate connection node arranged in said alternating communication path.

4. - The communication method according to claim 1, further characterized by additionally comprising the step of notifying said first intermediate node (13) on the data packets received from said second intermediate node (17).

5. - The communication method according to claim 1, further characterized in that said step of transmitting said data packet (29a) through said alternating communication path comprises the step of programming the transmission in accordance with priority classes in a tail queue formation.

6. - The communication method according to claim 2, further characterized in that said step of transmitting said data packet (29a) temporarily stored in said first intermediate node (13) comprises the step of transmitting said data packet (29a) before transmitting a second data packet (29b) temporarily stored in a buffer of low priority class in said first intermediate node (13).

7. The communication method according to claim 2, further characterized in that said step of transmitting said data packet (29a) temporarily stored in said first intermediate node (13) comprises the step of transmitting said data packet (29a) after transmitting a second data packet (29b) temporarily stored in a high priority class buffer in said first intermediate node (13).

8. - The communication method according to claim 4, further characterized in that said step of notifying said first intermediate node (13), is performed through a node in said alternating communication path.

9. - The communication method according to claim 4, further characterized in that said initial communication path includes a third intermediate node (15) disposed between said first and second intermediate nodes, said third intermediate node (15) comprises means for retransmitting a message.

10. - The communication method according to claim 1, further characterized in that said alternate communication path comprises a third intermediate node (19) arranged in said initial communication path between said second intermediate node (17) and the destination node (twenty-one ).

11. - The communication method according to claim 10, further characterized in that it further comprises the passage of said third intermediate node (19) that recognizes a reconfigured transmission path in response to said step of transmitting said data packet temporarily stored in said first intermediate node (13).

12. - The communication method according to claim 11, further characterized by additionally comprising the passage of said third intermediate node (19) that notifies said first intermediate node (13) on the 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 according to claim 1, further characterized in that said step of detecting a failure of said second intermediate node (17), comprises the step of receiving a retransmission message.

14. The communication method according to claim 1, further characterized in that 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 ( twenty-one ).

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

16. - The wireless communication network according to claim 15, further characterized in that said internal buffer memory comprises buffers (71) of at least two different priority classes.

17. - The wireless communication network according to claim 15, further characterized in that said first intermediate node (13) further comprises processor means (79) for responding to a retransmission request (49).

18. - The wireless communication network according to claim 15, further characterized in that said second intermediate node (27) includes means for retransmitting a message.

19. The wireless communication network according to claim 15, further characterized in that said first intermediate node (13) comprises a core configured to temporarily store said portion of data that passes 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 method of communication includes the steps of: establishing a communication path from the source node (11) to the destination node (21), said communication path comprises at least a first intermediate 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 in said first intermediate node (13); receiving a retransmission message (49) in said first intermediate node (13) requesting a data packet (29b) identified as missing; and transmitting said data packet (29b) stored in said first intermediate node (13) in response to said step of receiving said retransmission message (49).

21. The communication method according to claim 20, further characterized in that it further comprises the step of determining that said data packet stored in said first intermediate node corresponds to said data packet (29b) identified as missing.

22. The communication method according to claim 20, further characterized in that said step of storing comprises the step of temporarily storing said data packet in a selected local buffer of a plurality of local buffers, said selected local buffer corresponds to a priority class of said data packet.

23. - The communication method according to claim 20, further characterized in that it further comprises the steps of: receiving said retransmission message in a second intermediate node (27); and retransmitting said retransmission message from said second intermediate node to said first intermediate node (13).

24. - The communication method according to claim 23, further characterized by additionally comprising the steps of: verifying a local buffer in said second intermediate node (27) for said data packet identified as missing in said retransmission message; and determining that said data packet identified as missing is not in said local buffer of the second intermediate node (27).