Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing
Reexamination Certificate
2000-03-29
2004-08-03
Jean, Frantz B. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
C370S229000
Reexamination Certificate
active
06772215
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates in general to the telecommunications field and, in particular, to a method for minimizing feedback responses in Automatic Repeat Request (ARQ) protocols, such as, for example, selective-repeat ARQ protocols.
2. Description of Related Art
When data is conveyed between nodes in a telecommunication network, certain algorithms are used to recover from the transmission of erroneous data and the loss of data on the transmission links between the nodes. An algorithm commonly used to recover from the transmission of erroneous data is referred to as an ARQ protocol.
The existing ARQ protocols (i.e., algorithms) include two peer entities that communicate with each other over transmission links. Each such entity includes a receiver and a sender. The units of data conveyed between the peer entities are commonly referred to as Protocol Data Units (PDUs). The ARQ protocols include certain rules for sending and receiving PDUs, as well as rules for the structure of the PDUs. As such, the name “Automatic Repeat Request” indicates the basic function of the protocol: the receiver requests the sender to retransmit those PDUs that were lost or contained errors during transmission.
The receiver can inform the sender about which PDUs were correctly received (i.e., receiver acknowledges correctly-received PDUs) and/or which PDUs were incorrectly received. When the sender receives this information, it retransmits the “lost” PDUs. In other words, an ARQ protocol is a set of rules that allow the use of efficient retransmission mechanisms between a sending side and receiving side in a communication system. These rules specify, for example, how and in what form the PDUs are to be constructed so that the receiving side can interpret the conveyed PDUs correctly and respond to them accordingly.
Three main types of information elements (PDUs) can be transferred between two ARQ peer entities: user data; error recovery control data; and common control data. These three types of PDUs can be found in all of the existing ARQ protocols. A user data PDU contains at least user data and a sequence number. An error recovery control data PDU contains various control information needed for error recovery and control functions such as positive and negative acknowledgments. A common control data PDU contains common control data.
In the known High Level Data Link Control (HDLC) protocol, which forms the basis for many existing ARQ protocols, the three types of PDUs are called, respectively, information frames (I-frames), supervisory frames (S-frames), and unnumbered frames (U-frames). Examples of HDLC-derived ARQ protocols are the Radio Link Protocol (RLP) used in the Global System for Mobile Communications (GSM), the Radio Link Control (RLC) and Logical Link Control (LLC) protocols used in the General Packet Radio Service (GPRS), the Infrared Link Access Protocol (IrLAP) used in IrDA systems, and the LAP-B protocol used in X.25 systems. Notably, PDUs that include user data and at least a sequence number are denoted herein as Data-PDUs (D-PDUs), and PDUs that include control data needed for error control/recovery are denoted herein as Status-PDUs (S-PDUs).
In most communication systems, user data information is conveyed in both directions between the peer entities. A common feature included in an ARQ protocol is the possibility of including error control information in the user data PDUs. This capability is known as “piggybacking”. For example, an acknowledgment is included in all I-frames (i.e., D-PDUs) of HDLC-derived protocols. The acknowledgment informs the peer entity about the sequence number of the last (in-sequence) correctly received PDU.
The most common existing ARQ protocols implement one or more mechanisms to recover from errors on a transmission link, such as a Stop-and-Wait ARQ, Go-back-N ARQ, and Selective-Repeat ARQ. The use of these mechanisms and ARQs in general is well known.
FIG. 1
is a sequence diagram that illustrates the use of ARQ protocols. As shown, two ARQ peer entities
10
,
12
are communicating with each other. The arrows in
FIG. 1
indicate the transmission of PDUs between the two entities, and the content of each PDU is described directly above the respective arrow. Referring to
FIG. 1
, a sequence of transmitted D-PDUs and S-PDUs is shown. A D-PDU includes user data, a sequence number (SN), and possibly piggybacked error control information. An S-PDU includes status information but no user information. A sequence number (SN=x) is associated with a D-PDU to identify that specific D-PDU. An acknowledgment (ACK=x) is used to acknowledge any PDU with a SN<x. A negative acknowledgment (NAK=x) is used to acknowledge that a PDU (with an SN=x) has not been correctly received.
Two types of error control feedback responses are shown in FIG.
1
. For one of the feedback responses (e.g., S-PDU, ACK=2)
14
, the second ARQ peer entity
12
has acknowledged that it has received the PDUs with the SN=0 and SN=1. For the second type of feedback response (e.g., S-PDU, NAK=3)
16
, the second peer entity
12
has indicated that the PDU with the SN=3 was corrupted and should be retransmitted by the first peer entity
10
.
As discussed above, the S-PDUs are special PDUs which are transmitted between peer entities. An S-PDU includes information about the SNs of corrupted PDUS. Two main methods are currently used for coding the SNs within S-PDUs. One such method is to use a list of SNs to be retransmitted. The second method is to use a bitmap to represent the SNs to be retransmitted. As such, apart from representing SNs, an S-PDU also includes a format identifier which can be used by a receiver to distinguish between the different PDU formats (i.e., D-PDUs and S-PDUs).
The list method used for coding SNs includes the SNs of the erroneous PDUs in the S-PDU. If the length of the list is not predefined and thereby known, this length information is indicated in the S-PDU. For example, a length field can be included in the S-PDU.
FIG. 2
shows such an S-PDU, which can be created by a receiver using a list method for coding SNs.
Referring to
FIG. 2
, a receiver can create an S-PDU with the contents shown, if the sender has transmitted a sequence of D-PDUs with SNs=0-15, and the PDUs with SNs=3, 5, 6, 7 and 8 have failed (not been correctly received). For example, the first two elements in the list (after the length field) indicate that the D-PDU with SN=3 was erroneous. The third and fourth elements in the list indicate that the D-PDUs with SNs=5-8 were erroneous. The final element is included to acknowledge the remaining PDUs (SNs up to 15).
The size of the S-PDU depends on the number of bits used to represent the PDU format identifier field, the length field and the SN field. As such, the size of an S-PDU can be calculated by the expression:
DU.SIZE
LIST
=size(pdu.format.field)+size(length.field)+no.listelements*size(seq.no.field). (1)
For example, this list method is used in the SSCOP protocol, wherein two S-PDU formats exist and are denoted by the term “STAT” for a variable list length, and “USTAT” for a list with a limited number of elements (e.g., 2 elements).
FIG. 3
shows an S-PDU which can be created by a receiver using a bitmap method for coding SNs. When a bitmap is used to indicate SNs, the receiver creates the S-PDU from the SN of the last in-sequence correctly received D-PDU and a bitmap. This SN is referred to as a Start SN (SSN). Consequently, this S-PDU implicitly acknowledges all D-PDUs received up to the value of the SSN. Each location in the bitmap is used to address a specific S-PDU relative to the SSN. Typically, the size of the bitmap is fixed to the size of the ARQ receiver window and does not have to be explicitly indicated. If the bitmap is not fixed, the length has to be indicated.
The bitmap shown in
FIG. 3
shows an S-PDU created from the example described above with resp
Beming Per
Inoue Kazuhiko
Johansson Mathias
Meyer Michael
Rathonyi Bela
Jean Frantz B.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Method for minimizing feedback responses in ARQ protocols does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for minimizing feedback responses in ARQ protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for minimizing feedback responses in ARQ protocols will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300342