Concatenated error detection coding and packet numbering for hierarchical arq schemes

Concatenated Error Detection Coding and Package Numbering for Hierarchical ARQ Circuits

Field of the Invention

The present invention relates to sending packet data via a cascade link chain which uses packet retransmission to correct an error. In particular, the present invention relates to the transmission of packet data via cascade links, which have different characteristics with respect to packet transmission cost, quality, speed and / or traffic density. Examples of such cascading link links are portable computing devices (laptop, organizer, PDA) that are connected wirelessly (e.g. wireless) to a mobile or portable phone that is also connected to a cellular network via a radio link. Another example is wireless local area networks (LANs), where the computing device is wirelessly connected to a fixed hub or satellite station connected to a wired LAN structure (Ethernet).

Background of the Invention

High capacity data transmission uses packet switched networks, where data is transmitted in data packets which, in addition to information, carry source and destination addresses. If the packet is disturbed, for example, in the event of collision with another packet or when the alert level increases, the packet must be further transmitted by the source. The source must carry over the same packet until it is successfully sent, as indicated by the destination's confirmation that the packet has been received correctly. In order for the destination to be able to determine whether the packet has been received correctly, error detection coding is added to the packet, either in the form of forward error error correction (FEC) coding or in the form of cyclic redundancy check (CRC).

There are several schemes that provide automatic retransmission when the destination does not acknowledge receipt of the packet, so-called automatic repeat query (ARQ) methods. If no acknowledgment of receipt of the packet is received within a certain period of time, the source will automatically repeat the transmission. In its simplest form, the source waits for the destination to be confirmed after each packet has been sent, and continues to retransmit the same packet until it is received. Only after confirmation will the next package be sent. This is called the stop-and-wait ARQ method.

EE 03366 Bl

More efficient methods will continue to send packets, even if the previous ones have not been confirmed. Unacknowledged packets are stored for retransmission and are only deleted from memory after confirmation has been received. In these methods, packets are provided with a packet number so that the destination can confirm the correct packet number. Examples of ARQ methods that use packet numbering and do not wait for a response before sending the next packet are selective ARQ and (cumulative) go-back-N (ARQ). These methods provide higher performance, especially for those connections that include some reference.

Most of the data communication is not via a homogeneous connection, but via cascade link circuits connected by relay stations. Very often, individual links have different characteristics, and one link may be more sensitive to the others in terms of cost (public wired or cellular networks to local, private networks), data rate, or broadcast quality (which may be related to traffic volume). One example of such a cascade connection is the communication between a mobile base station and a portable computing device using short range wireless communication with a mobile phone to gain access to a mobile base station. Here is the most sensitive link for a mobile link. Another example is a portable computing device that is wirelessly connected to a local area network (LAN = local area network) that connects to a server. In this example, a sensitive link is a wireless link between a computer and a wired LAN. For such cascade connections, the ARQ protocol between ports (ARQ only between source and destination; relay stations only switch information without verifying that the information is correct) is not attractive, as an error requires re-transmission throughout the circuit, regardless of where the error occurred. In order to minimize retransmission over a sensitive link, it is preferable to only retransmit via the sensitive link those packets that were actually interrupted by the sensitive link. This requires distributed ARQ schemes, that is, separate ARQ schemes for each link. Extensive storage capabilities at relay stations are now required to optimize performance to support efficient ARQ methods.

Nature of the Invention

According to one embodiment of the present invention, there is disclosed a method that minimizes retransmissions over a sensitive link, but at the same time combines high power EE 03366 B1 with low storage demand at relay stations. It is a combination of port-to-port and line ARQ.

The present invention discloses a method in which retransmission over a sensitive link contains only those packets that were actually interrupted by the sensitive link. At the same time, the required storage capacity of the relay stations connecting the sensitive link and the non-sensitive link is reduced.

Faults in the sensitive connection will also result in redirection through non-sensitive links, but will be considered less important because non-sensitive links are more productive and / or cheaper.

According to one embodiment of the present invention, concatenated error detection coding and packet numbering are used. An ARQ protocol between ports is applied between the two end stations connected by a sensitive link and at least one non-sensitive link. The terminals have sufficient processing power and storage capacity to perform the inter-port protocol. Non-sensitive links between end stations implement their own local ARQs, which read the endpoint coding and numbering packet as a new information packet to which they add their local error detection coding and number. Therefore, the local ARQ protocol surrounds the inter-port ARQ protector, resulting in concatenation of error correction coding and numbering. The packet transmitted over a sensitive link contains only inter-port coding and numbering. However, the packet transmitted over a non-sensitive link also contains local coding and numbering. A relay station located between a non-sensitive and a sensitive link that receives the packet in an insensitive manner link checks the correctness of the received packet using local error detection coding. If the relay station determines that the packet has been received correctly, the relay station confirms the local number. The relay station then deletes the local coding and number and transfers the packet to the sensitive link. If the package is not received correctly at the relay station, it will not be acknowledged or transmitted to a sensitive link. If the relay station receives the packet from a sensitive link, the relay station does not check the received packet for correctness, but directly adds the local coding and number, and then transfers the packet to the non-sensitive link. The end station, which acts as a destination, is first checked for local error detection coding. If it is OK, a local number will be attached to the relay station. An inter-port protocol is then performed to see if the packet went through the sensitive link error-free as well. If the packet is not received correctly, the packet will not be acknowledged and the other end station will work

EE 03366 ΒΙ as the source, sends an additional packet. If the packet is correctly received, the destination acknowledges receipt of the packet by affixing the endpoint to the source of the packet number.

Brief description of the drawings

These and other features and advantages of the present invention will be readily apparent to one of ordinary skill in the art from the following description, taken in conjunction with the drawings in which.

FIG. 1 illustrates transmitting a packet over cascade connections over a local area network, FIG. 2 illustrates transmitting a packet via cascade connections between a laptop and a mobile system via a mobile phone with a low bandwidth radio frequency;

FIG. 3 illustrates an ARQ protocol between ports; FIG. 4 illustrates an ARQ protocol for a line; and FIG. 5 illustrates a concatenated ARQ protocol according to one embodiment of the present invention.

Detailed Description of the Invention

Transmission connections rarely contain a homogeneous link. Usually, transmission links consist of a cascade link chain, where each individual link has its own characteristics in terms of performance (data rate and link quality) and cost of transmission.

Data communications generally employ packet data techniques to transfer data. The data is taken from a packet that may have some general information, such as source and destination addresses, preferred delivery, and order number. Additionally, some error detection coding, such as a cycle code check CRS or a transmission error correction FEC, is added so that the destination can identify whether the packet has been received correctly. The packets can then be sent synchronously or asynchronously over the link. The destination checks the packet for correctness and sends either an acknowledgment signal (ACK) with the packet number or a non-acknowledgment signal (NAK) in case the packet is received correctly or incorrectly. If a non-acknowledgment signal is generated, the source may respond by sending an incorrect packet. However, many systems do not use non-confirmation signals. Instead, the source waits for the control time during the period and as a confirmation signal for the control time

EE 03366 B1 is not received during this period, the source automatically performs retransmission of the packet. This so-called Automatic Repeat Request (ARQ) or Automatic Repeat Request is a safer way to use non-confirmation signals because when the confirmation signal is interrupted, the source sends the packet further, but if the non-confirmation signal is interrupted, some information may never reach its destination. Note that confirmation messages do not need to be sent back individually, but can be integrated into a backward data feed, so-called cock riding.

There are many forms of ARQ schemes. In the simplest method, the source sends only one packet and then waits for confirmation for that packet. The same packet will be sent periodically until it is confirmed. This stop-and-wait ARQ method is not very effective, especially when there is a significant delay in the communication or processing of the destination. The higher throughput ARQ method continues to send packets, but saves sent packets until they are acknowledged. After the packet is confirmed, the packet is deleted from the list of stored packets. If the packets are not confirmed within the time limit, they will be sent in addition.

The present invention relates to the use of these ARQ protocols for cascade links or linkage. Two examples of this type of connection are illustrated in FIGS. 1 and 2. FIG. 1 shows a local wireless local area network (LAN). A wired LAN is connected to a server, whereas a laptop is connected to the same wired LAN via a radio link. A radio link is a sensitive link in this case because of its lower performance (lower data rate, lower quality, thus more retransmissions). In this example, the server and the laptop are the end stations. The hub acts as a relay station between a radio link and a wired LAN and can serve multiple laptops. In FIG. 2 is a portable data device, such as a laptop, a PDA organizer, etc., connected via a short-range radio frequency connection to a mobile phone connected to a cellular network via a radio link. In this example, a mobile link is a sensitive link in terms of performance (data rate and signal quality) and idle cost. The mobile base station (or intermediate work section connected to the base station) and the data device serve as end stations, whereas the mobile phone acts as a relay station. Errors due to reduced performance and / or cost, a wired LAN (a), or a short-range radio frequency link should not induce retransmissions over sensitive links.

The ARQ protocols provide error correction by retransmission for the communication systems described above. Straight-forward ARQ method

EE 03366 B1 utilizes an inter-port protocol that controls packets only at the end stations, as illustrated in FIG. 3. In FIG. 3 indicates a dashed sensitive link. The amount of memory required by the inter-ARQ protocol is only addressed by the end stations. The relay station simply needs to transfer information from one link to another without having to do anything with the packets. This ARQ protocol is not engaging in the above applications because errors in the non-sensitive link induce end-to-end transmissions, including sensitive links. This disadvantage can be avoided by using the line ARQ protocol as in FIG. 4 shown. In the ARQ protocol, a sensitive and non-sensitive link has its own ARQ protocol. Upgrades will only occur on the link where the errors actually occurred. However, as in FIG. 4 shown, the relay station must now be able to perform two local ARQ protocols, including frame recording for retransmission. This is not a problem for a non-sensitive link. Because of its high throughput and low pendulum delay, the buffer needs are limited, since higher throughput and shorter delay before attachment require less buffering. However, more sensitive memory capabilities are required for a sensitive link. However, in a wired LAN system that serves many portable users simultaneously, and in a portable telephone, the additional memory requirements and target protocol processing are not attractive. In FIG. Figure 4 shows this difference in memory capacity as a difference in memory capacity for the two ARQ methods. FIGS. 3-5 are packet characteristics capitalized by letters I, D and N, where I is the information packet, D is the error detection data added, and N is the packet number. In FIG. 3 there is only one type of packet containing endpoint error coding DJE and number N_E, where _E indicates that error detection coding D and number N are part of the inter-port protocol. In FIG. 4 is two local protocols that provide D_L1, N_L1 and D_L2, N_L2 for two local ARQs, where _L indicates that error detection coding D and number

N are parts of the local protocol. In FIG. 4 assumed that the packet length was the same for both links. This is not a required prerequisite and, for example, link 1 may well have bore D_L1 (II) N_L1, DJL1 (12) N_L1, ..., D_L1 (In) N_L1 if the packet of link 2 was divided into n packets for link 1.

According to one embodiment of the present invention, the complexity of the relay station can be reduced by applying only the local ARQ method to the non-sensitive link. This method requires only a small amount of memory. This may be achieved by covering the inter-port ARQ protocol with the local ARQ protocol, as illustrated in FIG. 5. In addition

EE 03366 B1 for port-to-port protocol between two end stations, the local ARQ protocol is used in the non-sensitive link. Inter-port protocol packets are considered normal data for the local ARQ protocol and coded and numbered for this additional error detection. If the end station A wants to send the information packet I, it adds an error detection coding DE and a number N_E to the inter-port protocol, resulting in a packet DE (I) N_E. Now the local ARQ protocol adds a second layer of error detection coding DL and a number NL to get the DL (DE (I) NE) N L packet. When the relay station receives this packet, the DL is first checked for error detection coding to see if the local link produced any errors . When the packet 10 is received correctly, the station A is acknowledged to receive the local number NL. The relay station then deletes the local ARQ ballast (ie DL and NL) from the packet and the packet is transferred to the sensitive link. If the packet is not received correctly, the local number N_L will not be acknowledged and the packet will not be transferred to a sensitive link. The packet is then transmitted via Station A via a locally insensitive link until the packet is correctly received and confirmed by the relay station.

If the transmitted packet is received by the end station, the packet is checked for correctness using error detection coding D E. Only errors on the sensitive link may have affected this packet, otherwise it would not have been transmitted. Subsequently, the station A acknowledges receipt of the inter-port protocol packet number if the packet is correctly received. If the packet is not received correctly, it must be sent over the entire connection. However, since the local link is an insensitive high performance link, this additional traffic to the insensitive link is not a problem.

Now, sending a packet is reversed. The end station B receives the information packet I and adds the end-protocol error detection coding DE and the numbering N_E to obtain DE (I) N_E. The encoded packet is then sent via a sensitive link to the relay station. The relay station does not check that the packet has been received correctly. The packet is taken as it is and a second layer of error detection coding DL and numbering N_L is applied around the packet to obtain DL (DE (I) N_E) NL. Upon receiving the packet, end station A first checks that the packet has passed through the last local link correctly by checking error detection coding D L. If error detection coding is correct, end station A acknowledges receipt of the (local) packet by relay station NL acknowledgment.

EE 03366 Bl

If the receipt of the packet number NL is not acknowledged, the packet is transmitted additionally, but only by the relay station. If the error detection coding DL is correct, the end station A takes the next layer of the ARQ and checks the error detection coding DE of the inter-port protocol. If the error detection coding DE is correct, then it is clear that the packet went through the entire connection correctly and that its reception can be acknowledged by acknowledging the receipt of N_E to the terminal B. If the error detection encoding D_E is not correct, then it is likely that the sensitive link encountered an error, and the target packet number N_E is not acknowledged. As a result, the end station B sends the packet further until the packet receipt is acknowledged by the end station A.

In another embodiment of the present invention, the relay station controls the error detection coding DE in the packet it receives from the end station B. It discards the packet when an error is detected, thus reducing traffic on the non-sensitive link. However, the additional ballast of sending incorrect packets over a high throughput link is not such a problem that checking the target protocol error at the relay station could unnecessarily burden the relay station.

It is clear, however, that the relay station must still have storage and processing capability to execute the local ARQ scheme. However, due to the higher performance of local links, the caching and processing needs for local ARQs are much lower than for port-to-port ARQs. Additionally, since the local ARQ is integrated into the inter-port ARQ, any unidentified errors in the local procedure are captured by the inter-port procedure. It will be understood that the security of this add-on should be used as little as possible in order to minimize add-on transmissions of the add via a sensitive link. However, the non-sensitive link does not have to be completely error free, which simplifies the implementation of the local ARQ even further. One possible extension of this base method is a system in which the inter-port packet is divided into smaller subpackets, each encoded and numbered locally, and then transmitted at high speed over a local link. In the relay station, the subpackets are collected and assembled into a single packet, which is then sent over a sensitive link. Another extension of the base method is a system in which a plurality of inter-port packets are collected and compiled into a large packet, which is then locally coded and numbered. This large packet is then sent over a local (non-sensitive) link, and the correctly received packet received by the relay station is inverted

EE 03366 ΒΙ to the original port-to-port packets, which are then individually transmitted and sent over a sensitive link.

You can continue the wrapping process with more cascading and sensitive links. Each time a new ARQ information shell is rebuilt around the former package. For the new encapsulation, the whole package (information + encoding + number) is considered as a new information package. In this way, a hierarchy of ARQ schemes is created and the ballast for a single ARQ scheme is located like a layer or shell around a packet. By stripping the ARQ ballasts one after the other, the processing station can determine where the error occurred and to which (relay) station the packet receipt can be acknowledged.

It will be appreciated by one of ordinary skill in the art that the present invention may be embodied in other specific forms without departing from their spirit and essential features. The variants disclosed herein are therefore considered to be illustrative and non-limiting in every respect. The scope of the invention is defined by the appended claims, not so much by the foregoing description, and any changes within its meaning and equivalents are therefore intended to be included therein.