(12) United States Patent
`US 6,772,215 B1
`(10) Patent N0.:
`
`Rathonyi et al.
`(45) Date of Patent:
`Aug. 3, 2004
`
`USOO6772215B1
`
`(54) METHOD FOR MINIMIZING FEEDBACK
`RESPONSES IN ARQ PROTOCOLS
`
`(75)
`
`Inventors: Bela Rathonyi, Malmo (SE); Joachim
`.
`-
`:acgs’ figgnlngg’enhfilghag M139?
`ac .en
`,
`’
`g’
`0C
`0 m
`(SE)> M3911?“ J0h3n550n> SPHCHI‘lHa
`(SE); Chrlstlaan ROObOL Hasselby
`(SE); Erik Sch0'n, Tokyo (JP);
`Kazuhiko Inoue, Tokyo (JP)
`
`8/1998 Ayerst et al.
`5,799,012 A *
`............... 370/336
`
`5,968,197 A * 10/1999 Doiron .................... 714/748
`............ 370/392
`5,991,299 A * 11/1999 Radogna et al.
`2:323:32: 2 : 3:888 Ill/{inartnitetlaL ~~~~~~~~~~~~~ 338731;);
`,
`,
`yers e a . ...........
`
`6,317,430 B1 * 11/2001 Knisely et a].
`..... 370/394
`
`
`..
`6,359,877 B1 *
`3/2002 Rathonyi et al.
`..... 370/349
`.......... 370/229
`6,473,399 B1 * 10/2002 Johansson et al.
`6,542,490 B1 *
`4/2003 Ahmadvand et al.
`....... 370/338
`
`FOREIGN PATENT DOCUMENTS
`
`(73) Assignee: Telefonaktiebolaget LM Ericsson
`(publ), Stockholm (SE)
`
`EP
`
`4/1997
`0 768806 A2
`OTHER PUBLICATIONS
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`PP
`21 A 1. No.: 09/537,146
`.
`.
`Ffled.
`
`(22)
`
`Blah 29,2000
`Related U.S. Application Data
`lfgg‘gisional application No. 60/128,517, filed on Apr. 9,
`
`(60)
`
`Int. Cl.7 ................................................ G06F 15/16
`(51)
`(52) U.S. Cl.
`........................................ 709/230, 370/229
`(58) Field of Search .......................... 709/230; 370/229,
`’
`’
`7
`370/232 394 395.1 349
`_
`References CltEd
`U.S. PATENT DOCUMENTS
`
`(56)
`
`3/1984 Donnan ....................... 371/32
`4,439,859 A *
`
`39222938 2 * 13133: 311:“ 6: all‘
`‘
`””” 370/392
`e e a . .........
`a
`9
`,
`
`. 370/449
`5,673,252 A *
`9/1997 Johnson et al.
`..
`
`5/1998 Delp et al. ............... 710/7
`5,752,078 A *
`
`......... 395/182.16
`5,754,754 A
`5/1998 Dudley et al.
`
`Throughput analysis of some ARQ protocols in the presence
`of feedback errors by Cam et al.; IEEE; vol. 45 No. 1, Jan.
`1997*
`Richard Cam and Cyril Leung; ThroughputAnalysis ofSome
`AR Protocols in the Presence 0 Feedback Errors; IEEE
`Transactions on Communications; Jan. 1997; vol. 45, No. 1;
`pp 35_44
`ISR, PCT/SE/ 00/00677, Completed Aug. 23, 2000.
`* cited by examiner
`
`Primary Examiner—Frantz 3 Jean
`(57)
`ABSTRACT
`g
`p
`A method for minimizin feedback res onses in an ARQ
`protocol is disclosed, whereby different mechanisms can be
`used to indicate erroneous D-PDUs and construct S-PDUs.
`The S—PDUs are constructed so as to optimize performance
`in accordance With certain criteria. One such criterion used
`
`is to minimize the size of the S-PDUs. A second such
`criterion used is to maximize the number of SNs included in
`_
`.
`.
`.
`an S PDU 0f 11“”th Slze‘
`
`64 Claims, 3 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`BROADCOM 1 O O 1
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 1 0f3
`
`US 6,772,215 B1
`
`A80
`Entity~1
`
`10
`
`FIG.1
`PRIOR ART
`
`
`
`, 12
`
`
`Entity-2
`
` D-PDU,SN=O
`
`
`
`D-PDU,SN=1
`
`D-PDU,SN=2
`
`D-PDU,SN=3
`
`D—PDU,SN=4
`
`
`\ S-PDU,ACK=2
`
`
`
`
`
`
`
`
`
`
`
`D'PDU'SN:5
`
`S-PDU,ACK=3
`
`
`
`
`
`FIG. 2
`PRIOR ART
`PDU_format=S-PDU
`Length=5
`
`‘
`3*”
`
`FIG.4
`Type=enMAw
`
`LENGTH
`Bitmap
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG-3
`PRIOR ART
`PDU_format=S-PDU
`SSN=2
`
`
`
`
`FIG. 5
`
`BITMAP=O1000O1111111OOD
`
`SN
`1
`
`FIG 5
`T m.
`
`
`we-
`LENGTH
`
`
`
`type=LlST
`LENGTH=°
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LENGTH=4
`
`SN1=1
`SN2=25 _
`3N3=50
`SNLENGTH
`
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 2 013
`
`US 6,772,215 B1
`
`WF
`
`SN
`LENGTH
`
`Bitmap
`Ty9e=LIST’
`LENGTH
`
`8N1
`C
`
`S NLENGTH
`LLENGTH
`
`N/A
`
`
`WL
`
`ENGTH
`
`bitmag
`Type=NO_MORE
`
`FIG. 8
`
`
`
` LENGTH
`
`
`
`
`
`
`
`
`
`
`—-—n
`
`
`
`0 4
`
`
`
`"SN,
`1
`000000000001
`00000001 1001
`
`25
`
`
`
`
`
`FIG.1O
`
`
`Field Value
`Field
`_] Field—l
`
`decimal
`Bits
`size
`
`BITMAP’
`N/A‘]
`70“]
`2
`
`LENGTH
`2
`00010
`5
`FFSN
`27L
`000000011011
`12
`
`
`gitmap
`28-43
`0001111011101011
`16
`
`[EST
`N/A_x
`01
`2‘1
`LENGTH
`‘
`2
`00010}
`5
`
`
`[£51,
`__
`91
`000001011011
`12—]
`
`L]
`3
`00011
`5
`LSN,‘
`101
`000001100101
`12
`L2
`0
`00000
`5
`
`NO_MORE
`N/A
`00 f
`2 ‘
`'
`FIG. 11
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 3 013
`
`US 6,772,215 B1
`
`
`
` 1110111
`
`0111101111
`
`1111111111
`1101111111
`
`1111011111
`
`1111011111
`1111101111
`
`1111111011
`
`
`
`
`1011111111
`0
`
`
`
`000001100101
`
`Fidd
`
`LIST’
`
`
`
`
`
`
`
`Field Value
`Bits
`decimal
`
`N/A
`01
`
`
`
`Field
`size
`
`1——
`
`___—m
`
`___-3
`N/A
`
`
`
`
`
`
`101
`
`
`
`FIG. 13
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`US 6,772,215 B1
`
`1
`METHOD FOR MINIMIZING FEEDBACK
`RESPONSES IN ARQ PROTOCOLS
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`This Application for Patent claims the benefit of priority
`from, and hereby incorporates by reference the entire dis-
`closure of, co-pending US. Provisional Application for
`patent Ser. No. 60/128,517, filed Apr. 9, 1999.
`
`BACKGROUND OF THE INVENTION
`
`1. Technical Field of the Invention
`
`The present invention relates in general to the telecom-
`munications field and, in particular, to a method for mini-
`mizing 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 telecommu-
`nication 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 erro-
`neous 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 trans-
`mission 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
`
`receiver acknowledges
`were correctly received (i.e.,
`correctly-received PDUs) and/or which PDUs were incor-
`rectly 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. Auser data PDU contains at least user data and a
`sequence number. An error recovery control data PDU
`contains various control information needed for error recov-
`
`ery 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 Pro-
`tocol (RLP) used in the Global System for Mobile Commu-
`nications (GSM), the Radio Link Control (RLC) and Logical
`Link Control (LLC) protocols used in the General Packet
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`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 possi-
`bility 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 acknowl-
`edgment 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-WaitARQ, Go-back-N
`ARQ, and Selective-Repeat ARQ. The use of these mecha-
`nisms 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 trans-
`mitted D-PDUs and S-PDUs is shown. A D-PDU includes
`
`user data, a sequence number (SN), and possibly piggy-
`backed 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 acknowl-
`edge 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 acknowl-
`edged 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
`
`

`

`US 6,772,215 B1
`
`3
`
`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.SIZEL,S]=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 respect to FIG. 2,
`and a window size of 16. As such, each location in the
`bitmap can have one of the two values, 0 or 1: A“1” means
`that SN=(SSN+bitiposition) has been correctly received;
`and a “0” value means that SN=(SSN+bit position) has not
`been correctly received. Of course, the meaning of the “0”
`and “1” values can be interchanged. The size of an S-PDU
`when using such a bitmap can be derived from the following
`expression:
`
`PDU.SIZEB,TMAP=size(pdu.format.field)+size(SSN.field)+size(bit-
`map.field).
`(2)
`
`Both the RLC and LLC protocols in the GPRS system use
`such an expression and convey bitmaps between peer enti-
`ties for error control purposes.
`A significant problem with existing ARQ protocols is that
`they are static in construction (e.g., fixed length messages
`are used). In certain situations, this approach leads to a waste
`of bandwidth resources, because a great deal of overhead
`information is transmitted unnecessarily. For example, such
`situations can occur in systems having a large number of
`D-PDUs being transmitted between two ARQ peer entities,
`and these D-PDUs have to be acknowledged and selectively
`requested for
`retransmission. For some error control
`situations,
`the existing solutions introduce a significant
`amount of unnecessary overhead. The following example
`illustrates such a situation.
`
`4
`Table 1 below shows the number of bits needed to code
`
`an S-PDU using the list and bitmap methods described
`above. Different error circumstances are provided to high-
`light the large difference in the number of bits required for
`the two methods. Assume that the following element sizes
`are used: bitmap=128 bits;
`length=5 bits; and one PDU
`format identifier=1 bit (for distinguishing between a D-PDU
`and an S-PDU). As such, the different S-PDU sizes shown
`in Table 1 are calculated in accordance with Equations (1)
`and (2) above, respectively.
`As illustrated by rows 2—5 in Table 1, both of the existing
`solutions have problems with efficiently building small
`S-PDUs for error circumstances shown. The length of the
`LIST does not depend so much on the number of erroneous
`D-PDUs, but rather on the distribution of the errors within
`the window used. This fact becomes evident by comparing
`rows 1 and 2 in Table 1.
`
`TABLE 1
`
`Erroneous D-PDUs
`
`(SN)
`51—77
`1, 25, 50, 95
`27—30, 35, 39, 41, 91—93
`3, 7, 11, 16, 33, 45, 55, 66, 78, 82, 91
`10—29, 31, 33, 36
`
`1
`2
`3
`4
`5
`
`Size of S-PDU
`bits
`
`LIST BITMAP
`42
`141
`114
`141
`138
`141
`282
`141
`114
`141
`
`#
`
`SN
`27
`4
`10
`11
`23
`
`A general statement of the problem to be solved is to
`determine how to efficiently represent (encode) in a message
`the status of an arbitrary amount and distribution of n
`numbers from a set of m numbers. As such, a significant
`need exists for a method that can be used to minimize the
`
`size of S-PDUs in an ARQ protocol Also, a significant need
`exists for a method that can be used to maximize the number
`
`of SNs in an S-PDU with limited size, if it is not possible to
`fit all potential SNs into a single S-PDU. As described in
`detail below, the present invention successfully resolves the
`above-described problems and other related problems.
`SUMMARY OF THE INVENTION
`
`In accordance with an embodiment of the present
`invention, a method for minimizing feedback responses in
`an ARQ protocol is provided, whereby different mechanisms
`can be used to indicate erroneous D-PDUs and construct
`
`S-PDUs. In particular, these different mechanisms can be
`combined in a single S-PDU. The S-PDUs are constructed
`so as to optimize system performance in accordance with
`certain criteria. One such criterion used is to minimize the
`size of the S-PDUs. A second such criterion used is to
`maximize the number of SNs included in an S-PDU of
`limited size.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`An important technical advantage of the present invention
`is that radio interface bandwidth resources can be saved.
`
`In the Wideband-Code Division Multiple Access
`(WCDMA) system currently being standardized for the
`so-called 3rd Generation Cellular Communication System,
`one ARQ protocol used is an RLC protocol. The,SN set
`includes the values 0—4095, which means that each SN is
`coded with 12 bits. An assumption can be made that for high
`data rates, a relatively large set of SNs will have to be
`addressed in some S-PDUs. Also, assume that the status of
`100 D-PDUs (SN=1—100) needs to be communicated
`between the RLC peer entities in an S-PDU.
`
`60
`
`65
`
`technical advantage of the present
`Another important
`invention is that protocol overhead can be minimized.
`Still another important technical advantage of the present
`invention is that system capacity can be increased.
`Yet another important technical advantage of the present
`invention is that the number of feedback responses in a
`selective-repeat ARQ protocol can be minimized.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A more complete understanding of the method and appa-
`ratus of the present invention may be had by reference to the
`
`

`

`US 6,772,215 B1
`
`5
`following detailed description when taken in conjunction
`with the accompanying drawings wherein:
`FIG. 1 is a sequence diagram that illustrates the use of
`ARQ protocols;
`FIG. 2 is a diagram that shows an S-PDU which can be
`created by a receiver using an existing list method for coding
`SNs;
`FIG. 3 is a diagram that shows an S-PDU which can be
`created by a receiver using an existing bitmap method for
`coding SNs;
`FIG. 4 is a bitmap message for use in an S-PDU, con-
`structed in accordance with a first embodiment of the present
`invention;
`FIG. 5 is a diagram of a message with the fields and
`contents of the LIST S-PDU for row 2 in Table 1, con-
`structed in accordance with the first embodiment of the
`
`present invention;
`FIG. 6 is a diagram of the fields of a LIST’ message in an
`S-PDU, constructed in accordance with the first embodiment
`of the present invention;
`FIG. 7 is a diagram that shows the contents of an “ACK”
`message constructed in accordance with the second embodi-
`ment of the present invention;
`FIG. 8 is a diagram that illustrates how an S-PDU can be
`constructed in accordance with the combination method of
`the second embodiment;
`FIG. 9 is a diagram that shows the contents of row 1 of
`Table 1 in a combination S-PDL , constructed in accorc ance
`with the second embodiment of the present invention;
`FIG. 10 is a diagram that shows the contents of row 2 of
`Table 1 in a combination S-PDL , constructed in accorc ance
`with the second embodiment of the present invention;
`FIG. 11 is a. diagram that shows the contents of row 3 of
`Table 1 in a combination S-PDL , constructed in accorc ance
`with the second embodiment of the present invention;
`FIG. 12 is a diagram that shows the contents of row 4 of
`Table 1 in a combination S-PDL , constructed in accorc ance
`with the second embodiment of the present invention; and
`FIG. 13 is a diagram that shows the contents of row 5 of
`Table 1 in a combination S-PDL , constructed in accorc ance
`with the second embodiment of the present invention.
`DETAILED DESCRIPTIOI\ OF THE DRAWINGS
`
`
`
`
`
`invention and their
`The embodiments of the present
`advantages are best understood by referring to FIGS. 1—13
`of the drawings,
`like numerals being used for like and
`corresponding parts of the various drawings.
`Essentially, in accordance with a first embodiment of the
`present
`invention, a method for minimizing feedback
`responses in an ARQ protocol is provided, whereby different
`mechanisms can be used to indicate erroneous D-PDUs and
`construct S-PDUs. The S-PDUs are constructed so as to
`
`optimize performance in accordance with certain criteria.
`One such criterion used is to minimize the size of the
`S-PDUs. A second such criterion used is to maximize the
`number of SNs included in an S-PDU of limited size.
`
`the basic components being
`Specifically, hereinafter,
`described are messages. For this embodiment, such a mes-
`sage can be described by using a Type, Length, Value (TLV)
`syntax. In other words, each message includes three fields.
`One field includes type information,
`the second field
`includes length information, and the third field includes a
`value. The size of the type field is preferably non-zero, while
`the sizes of the other two fields can be zero.
`
`6
`Notably, as mentioned earlier, all existing bitmap solu-
`tions include information about the sequence number (herein
`called the SSN) of the last received in-sequence D-PDU in
`a constructed S-PDU. The SSN indicates that no errors exist
`
`prior to that sequence number. In other words, the SSN is
`used to acknowledge all D-PDUs having SNs up to that of
`the SSN.
`
`For this exemplary embodiment, a basic message to be
`used for minimizing feedback responses in an ARQ protocol
`can be constructed as follows. Using a BITMAP method for
`this embodiment, the SN included in a constructed S-PDU
`indicates the SN of any (not necessarily the first) erroneous
`D-PDU from the set of SNs. The status of the subsequent
`SNs are indicated in the bitmap. Although the SN of the first
`erroneous D-PDU is used in this exemplary embodiment, it
`should be understood that any D-PDU (from the SN set) can
`be used in the bitmap method instead. In that case,
`the
`bitmap also has to include the status (0 or 1) of the SN
`included in the constructed S-PDU. As such, a “BITMAP”
`message can be created with a type identifier field, a first SN
`(FSN) field, a bitmap length field, and a bitmap field. FIG.
`4 illustrates a bitmap message with such fields for use in an
`S-PDU,
`in accordance with the first embodiment of the
`present invention.
`Referring to the bitmap message shown in FIG. 4, a
`number of methods can be used to represent the length of the
`bitmap (LENGTH field). For one method, a predefined
`number of bits can be used to represent the size of the bitmap
`in a basic data unit. Such a data unit can have any granularity
`and include, for example, one or more bits, bytes, words, etc.
`For example, if a byte is used as the basic data unit, the
`value, x,
`in the LENGTH field means that 8*x SNs are
`covered by the bitmap. This resulting value also represents
`the size of the bitmap in bits.
`For a second method used to represent the length of the
`bitmap, a different SN can be used to indicate the last SN
`covered by the bitmap. The size of the LENGTH field is then
`equal to the size of the FSN field. As such, the size of the
`bitmap can be calculated by subtracting the FSN value from
`the LENGTH value.
`
`A third method that can be used for representing the
`length of the bitmap is to fix the size of the bitmap so that
`no LENGTH field is required in the S-PDU. Alternatively,
`the size of the LENGTH field can be set to zero. Also, the
`size of the FSN field can also be set to zero if the SN that
`
`the bitmap covers is signalled remotely. Such a method is
`described in more detail below.
`
`Notably, a conventional data compression method can be
`used to compress the information in the bitmap field. As
`such, both normal and compressed bitmaps can be included
`in one S-PDU. In this case, the value of the type field for the
`compressed bitmap would be different than that for a normal
`bitmap.
`As mentioned earlier, a significant drawback of the exist-
`ing LIST methods is that two SNs are required for each error
`group. An error group comprises a single error or several
`consecutive errors of D-PDUs. In order to resolve such a
`
`problem using a LIST method in accordance with this
`exemplary embodiment, only erroneous SNs are listed. In
`other words, a new LIST type can be defined wherein only
`single errors are listed. Consequently, the size of a resulting
`S-PDU can be significantly reduced for certain error
`situations, in comparison with the existing LIST solutions.
`Another method that can be used to reduce the size of
`S-PDUs, in accordance with this embodiment, is to combine
`an existing LIST method (2 SNs per error group) with the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`US 6,772,215 B1
`
`7
`above-described single error SN LIST method to create the
`list message. For example, the existing LIST method can be
`improved significantly by introducing the following rules for
`creating the LENGTH field value:
`(1) A zero value means that a single error SN LIST
`method is applied. A second (new) length field is
`included directly after the original LENGTH field to
`indicate the number of single erroneous SNs that follow
`directly after the second field. All list elements repre-
`sent single erroneous SNs, and no acknowledgment is
`provided while using this list method.
`(2) An odd value implies that the last list element is an
`acknowledgment.
`(3) An even value (excluding zero) implies that the last
`element is not an acknowledgment. Consequently, fol-
`lowing the above-described rules in accordance with
`this embodiment, the (LIST) S-PDU for row 2 in Table
`1 now contains the fields and contents shown in FIG. 5.
`As such,
`if the field sizes shown in row 2 of the
`example illustrated by Table 1 were to be used with
`respect to the embodiment illustrated by FIG. 5, then
`the total size of the S-PDU would be 59 bits.
`
`in accordance with the present
`Consequently,
`invention, the number of bits needed for the resulting
`S-PDU is significantly smaller than the number of bits
`(114) needed for the existing LIST solution.
`FIG. 6 is a diagram that illustrates another method that
`can be used to reduce the size of an S-PDU using a LIST
`method. The method used in accordance with this embodi-
`ment is to include a field after each list element which
`
`determines the length of the error, instead of indicating the
`length of the error with an “ending” SN. In most systems, the
`size of the length field would then be substantially smaller
`than the size of the SN field. Furthermore, typically there is
`no need to represent very large consecutive, erroneous
`D-PDUs (i.e., a large error group) in an S-PDU.
`Referring to FIG. 6, the fields of a new message (denoted
`as LIST’) in an S-PDU are shown. The new length field
`introduced after each SNl- is denoted L,- for 1 éIéLENGTH.
`Notably, a value of zero can be used for L,- to further improve
`the functionality of the resulting LIST’ message. As such,
`the following alternatives can be used:
`(1) A zero value for Lt. means that SNl. is an acknowledg-
`ment (i.e., Li is not pointing out an error).
`(2) A zero value represents the end of the LIST’ message.
`The first LENGTH field can be omitted if the interpretation
`of the last SN has been predefined. For example, the last SN
`can be restricted so as to always be an acknowledgment
`(e.g., as in the first alternative), or
`the length can be
`predefined (e.g., so as to point out a single error).
`In accordance with a second embodiment of the present
`invention, a number of different message types can be
`combined to create an S-PDU. These message types can be
`added in any arbitrary order in the S-PDU, and there is no
`rule on the number of messages or the type of message that
`can be included in the S-PDU. For
`this exemplary
`embodiment, each such message includes a type identifier,
`and the length is either fixed or indicated by a length field for
`each specific message. The first type identifier preferably has
`a predefined position in the resulting S-PDU. The rest of the
`type identifiers can be located at arbitrary locations depend-
`ing on the sizes of the included messages. For example, the
`messages, LIST’, BITMAP’ and ACK can be included in the
`S-PDU.
`
`The number of such messages that can possibly be
`included in an S-PDU determines the size (bits) of the type
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`identifier field used in the S-PDU. For example, the size of
`such a type identifier field can be determined by the follow-
`ing expression:
`
`ize(type. field)=[log2(number of possible messages+1)j,
`
`(3)
`
`where the operator L J rounds the argument off to the next
`highest integer value. The “+1” part of the argument is used
`so that a type identifier can be used to indicate that no other
`messages are included in an S-PDU. This special identifier
`is denoted herein as a “NOiMORE” message. As such, in
`accordance with Equation (3), the size of the type field is 2
`bits for three different messages, because [log2(4)J2.
`The contents of an “ACK” message constructed in accor-
`dance with this embodiment are shown in FIG. 7. The ACK
`
`message shown includes a type identifier field and SN. This
`ACK message marks the end of an S-PDU, and all prior
`D-PDUs not indicated to be erroneous within this S-PDU are
`
`acknowledged by the SN. Consequently, when such an ACK
`message is included in an S-PDU, there is no need to include
`a NOiMORE message to terminate the combined S-PDU.
`Assume that a LIST’ message with an acknowledgment
`feature (i.e., a zero value for Lt- means that SNl-
`is an
`acknowledgment) is used (with a LENGTH field). When a
`BITMAP’ message is included directly after a LIST’
`message, the size of the FSN field is zero. As such, the first
`SN which is represented in the bitmap is SNLENGTH+
`LLENGTH. Furthermore, a zero in the LENGTH field of the
`LIST’ message means that an additional LENGTH field is
`included, and the message is constructed as shown in FIG.
`5 with no LSNl- fields.
`Another way to obtain the above-described LIST feature
`is to define a new type (denoted, for example, “LIST”).
`However, the size of the type field can be affected, which can
`result in a larger S-PDU. In any event, there is a trade-off
`(which is system dependent) to consider in selecting the
`exact rules to follow for the combination method described
`above.
`
`FIG. 8 is a diagram that illustrates how an S—PDU can be
`constructed in accordance with the combination method
`
`described above. As shown, the resulting S-PDU includes
`two BITMAP’ messages and one LIST’ message. The
`second BITMAP’ message does not include an FSN field
`(or, the size of the FSN field is zero). Consequently, the first
`element in the bitmap represents the SN having the value,
`SNLENGTH+LLENGTH'
`In order to demonstrate the advantages of the above-
`described combination method,
`it can be applied to the
`example described above with respect to Table 1. As such,
`Table 2 shows different messages (along with their corre-
`sponding bit values) which can be combined in an S-PDU,
`in accordance with the second embodiment of the present
`invention. For this embodiment, each S-PDU starts with one
`of the type identifiers shown. Also, the sizes of the LENGTH
`and LSM- fields are fixed to 5 bits.
`Consequently, these fields can each hold a value between
`0—32(25) Notably, although the sizes of the fields are fixed,
`their sizes are not necessarily equal, as in this example (i.e.,
`the size of the LENGTH field in the BITMAP’ message can
`be different than the size of the LENGTH field in the LIST’
`
`message). The value of the LENGTH field in the BITMAP’
`message corresponds to the size of the bitmap in bytes (i.e.,
`a maximum of 8*32=256 SNs can be addressed in a single
`S-PDU). All of the fields containing an SN value have a size
`of 12 bits (i.e., the FSN, SN and SSN fields).
`
`

`

`US 6,772,215 B1
`
`9
`
`TABLE 2
`
`Type Identifier
`N07MORE
`LIST’
`BITMAP’
`ACK
`
`Value
`00
`01
`10
`11
`
`respectively, are diagrams that show the
`FIG. 9—13,
`contents of an S-PDU for each row shown in Table 1 for the
`above-described example. For this embodiment, the combi-
`nation is selected so as to minimize the total size of the
`S-PDU.
`As illustrated by the example described above with
`respect to Table 1, FIG. 9 shows the contents of row 1 in the
`resulting (combination) S-PDU, FIG. 10 shows the contents
`of row 2, and FIG. 11 shows the contents of row 3. Note that
`by including an ACK type instead of the list element SNi in
`FIG. 11, an additional 5 bits can be saved with respect to the
`total size of the S-PDU. FIG. 12 shows the contents of row
`4 in the resulting S-PDU, and FIG. 13 shows the contents of
`row 5. As such, the contents of the entire coded S-PDU can
`be obtained by concatenating all values from the “bits”
`column. For example, the contents of row 1 of the S-PDU
`(FIG. 9) would appear as:
`“01000010000001100