(12) Unlted States Patent
`(10) Patent N0.:
`US 6,424,625 B1
`
`Larsson et al.
`(45) Date of Patent:
`Jul. 23, 2002
`
`U5006424625B1
`
`(54) METHOD AND APPARATUS FOR
`DISCARDING PACKETS IN A DATA
`NETWORK HAVING AUTOMATIC REPEAT
`REQUEST
`
`(75)
`
`Inventors: Peter Larsson, Euro Asia View;
`Mikael Larsson, Doer Park, both of
`(SG)
`
`(73) Assignee: Telefonaktiebolaget LM Ericsson
`(publ), Stockholm (SE)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.2 09/179,952
`(22) Filed:
`Oct. 28, 1998
`
`H04L 12/26
`Int. Cl.7
`(51)
`iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii 370/236 370/410
`(52) U s C]
`(58) Field of Search ................................. 370/389, 394,
`370/410, 426, 428, 429, 470, 471, 473,
`236; 714/748, 749, 750
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`*
`.
`>1:
`8/1982 Lm et al‘ ““““““““““ 714/751
`4’344’171 A
`
`:fig’ggg 2 * 3133: 1512:1253: al'
`""" 3115::
`578269028 A
`10/1998 Bennett et a1:
`iiiiiiiiiiiii
`6,163,861 A 4 12/2000 Yoshioka et a1.
`........... 714/712
`FOREIGN PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`“
`.
`.
`Heliomar M. de lea and Otto Carlos MHB Duarte, A
`Go—Back—N Protocol with Multicopy Retransmission for
`High Speed Satellite Communications”, 1994, pp. 859—863.
`F. Argenti and G. Benelli, “An ARQ Protocol For Mobile
`Radio System”, 1992, PP 13234326
`Nachum Shacham and Byung Cheol Shin, “A Selective—Re-
`peat—ARQ Protocol for Paralle Channels and Its Resequenc-
`ing Analysis”, Apr. 1992, pp. 773—782.
`Standard Search Report dated Jul. 16, 1999.
`
`* cited by examiner
`
`Primary Examiner—Kwang B. Yao
`(74) Attorney, Agent, or Firm—Burns, Doane, Swecker &
`Mathlsr LLP‘
`(57)
`
`ABSTRACT
`
`Techniques are provided for use with automatic repeat
`request (ARQ) schemes in a data network to minimize a
`bandwidth used by a receiver and a transmitter in the
`network to transfer data packets, by discarding outdated
`packets that have not yet been successfully transferred. In
`accordance with an embodiment of the invention, a bit is set
`in the ARQ packet header to force the receiver to accept
`packets subsequent to one or more erroneous or unreceived
`packets that have been discarded and not resent. In accor-
`dance with another embodiment of the invention, after data
`packets have been discarded, sequence numbers are reas-
`signed to the non-discarded data packets that are yet to be
`sent
`to the receiver, so that a transmitted stream of the
`non-discarded packets will have consecutive sequence num-
`bers.
`
`WO
`
`98/42108
`
`9/1998
`
`19 Claims, 12 Drawing Sheets
`
`BROADCOM l 0 0 l
`
`

`

`US. Patent
`
`n,m.
`
`v.
`
`US 6,424,625 B1
`
`X o<Z
`
`ummums>ocxo<
`
`
`
`MFE<Egan:mw.MV_H_
`
`952£3mxo<n_
`2ammuw§ocxo<
`
`
`
`Ch?EOE—n:(F.o_H_
`
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 2 0f 12
`
`US 6,424,625 B1
`
`
`mmumStan522mEmEoo5E5.mao<
`
`mum3853
`
`
`
`
`
`
`
`
`
`
`
`
`
`coonwW...o..oanWu-o....-uu........wW..:o..........hOUNOIhmumw—t—thmOI503$”:mm.m..nmu.950.anQ.980z.950
`
`
`....................E3“.3“.éw
`
`
`
`Chm—.1EOE—n:N.mv_H_
`
`2m:
`
`
`
`
`
`
`
`X<_2.2m...2m._.umEEmcmb:082mm
`
`92SE;SE
`
`
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 3 0f 12
`
`US 6,424,625 B1
`
`.2mh2a:@z:5:
`
`:0_mw_Em:m.=mN_
`
`¥0<Z<.wDQQ0.3
`
`52._omzomcotm
`
`.Evz2flow2zwm
`.832m_zmmLEz5E
`
`.EmwmDDQ0.:
`
`.82899m=<
`
`<m.OE
`
`Om.OE
`
`
`
`Om,.®_n_
`
`mm.9“.
`
`Ct<EOE—n:
`
`CHEEOE—n:
`
`
`
`Ch?EOE—n:
`
`
`
`at”?EOEnC
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 4 0f 12
`
`US 6,424,625 B1
`
`.vaz2“mma2mm
`
`Emmmann—0.:
`
`.82on2m.3
`
`Dv.0_n_
`
`EOEnc
`
` Cum/x
`
`
`
`.cwzmfl¥O<n_
`
`0v.OE
`
`ChgEOE—n:
`
`.EwmwDDQOn..—
`
`.82822m.2
`
`mv.OE
`
`CHEEOE—n:
`
`
`
`<6..07.
`
`Cm<moan:
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 5 0f 12
`
`US 6,424,625 B1
`
`514
`
`k bit sequence number
`
`FIG. 5
`
`(PRIOR ART)
`
` ACK message
`
`614
`
`616
`
`FIG. 6
`
`(PRIOR ART)
`
`

`

`US. Patent
`
`20023a2u
`
`mhS
`
`US 6,424,625 B1
`
`6:33>=2mwmoo=wmm:mézwm
`
`
`
`cmfiEmcge:98mm:rzmm
`
`
`
`
`
`.8289262.60can
`
`.mc_mw_EEmQN.F2mm
`
`v..E8:08oflm«>229.03M26:99:mEom60289
`
`02322mm.um=_Em:§2
`
`
`
`mEmn>_Em._._:om_szm
`
`53>v_o<z.3.F-szm
`
`
`
`
`
`8..xo<n_02:23:50
`
`Oh.GE
`
`
`
`Ch?IOEnc
`
`
`
` CE<EOE—n:mi.®_n_
`
`
`
`.mfixomq05880.5
`
`{K.GE
`
`CHEEOE—n:
`
`LE“comEmEEgo/«z
`
`
`
`.9303mafia—33:0=m
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 7 0f 12
`
`US 6,424,625 B1
`
` k bit sequence number
`
`+
`
`Receive PDU enforcement Bit
`
`FIG. 8
`
`
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 8 0f 12
`
`US 6,424,625 B1
`
`
`
`
`
`
`
` EoEooEtna
`_m30<
`
` >>H
`
`wN_mLotusx92
`
`o
`
`a
`
`N53onEnummzj@3onm.980.Eoo.600m+._n_w+._n_winw
`
`580:
`
`.ano
` zm
`
`ooooooooooooooooooooooooooooounovooo.uccuocu-.oouuo.uv.uuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
`
`.
`
`<2.oE
`
`V2229
`
`.zw._.
`
`2m:
`
`>>
`
`22SE;SE
`
`
`
`uoEEwcm::98
`
`
`
`m=moumEmowE
`
`2mm
`
`2mm
`
`
`
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 9 0f 12
`
`US 6,424,625 B1
`
`2w._.
`
`
`
`mo?.OE
`
`xm_>_“mHAmI:iV”numuEmucoo.mtsn_m30<”"
`
`
`
`
`$ng523:uu.Hz.z.mummnmmmmmmm38mzamm0N6Etna
`
`>>H
`
`
`
`@528SE9m;5:;BE3252;SEm__mo89820
`
`.x<_2BEEmcgé
`
`
`
`
`
`
`
`2mm.:o_mm_Em:m=8%2w...:me6»6:2m_umEEmcgé582mm2mm
`
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 10 0f 12
`
`US 6,424,625 B1
`
`
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 11 of 12
`
`US 6,424,625 B1
`
`
`
`FIG. 12
`
`

`

`US. Patent
`
`Jul. 23, 2002
`
`Sheet 12 of 12
`
`US 6,424,625 B1
`
` @e‘y
`
`FIG. 13
`
`

`

`US 6,424,625 B1
`
`1
`METHOD AND APPARATUS FOR
`DISCARDING PACKETS IN A DATA
`NETWORK HAVING AUTOMATIC REPEAT
`REQUEST
`
`FIELD OF THE INVENTION
`
`invention relates to Automatic Repeat
`The present
`Request (ARQ) techniques for transferring data in fixed/
`wireless data networks.
`
`BACKGROUND OF THE INVENTION
`
`ARQ techniques are commonly used in data networks to
`ensure reliable data transfer and to protect data sequence
`integrity. Data packets are encoded with an error detecting
`code, so that when a transmitter in the data network sends or
`transfers data packets to a receiver in the data network, the
`receiver receiving the data packets can detect corrupted,
`erroneous or
`lost packets and thereby request
`that
`the
`transmitter retransmit the affected data packets. The integrity
`of a data sequence is normally protected by sequentially
`numbering packets and applying certain transmission rules.
`There are three main ARQ schemes: Stop-and-Wait;
`Go—Back—N; and Selective Reject (sometimes referred to as
`Selective Repeat). All three methods provide mechanisms
`for transferring packets to a receiver in a data network in an
`appropriate order. In terms of throughput efficiency as a
`function of the signal to noise ratio, generally Selective
`Reject is most efficient, Stop-and-Wait is least efficient, and
`Go-Back-N is intermediate. Also, various mixtures of the
`Selective Reject and Go-Back-N techniques exist, and fall
`between pure Selective Reject and pure Go-Back-N tech-
`niques in both efficiency and complexity.
`With respect
`to Go-Back-N, several different variants
`exist which differ in terms of how they use positive acknowl-
`edgments (PACKS), negative acknowledgments (NACKS),
`retransmission timers, polling schemes, etc.
`One type of Go—Back—N technique uses both PACKS and
`NACKS that have the following characteristics:
`A PACK for a data packet having a sequence number
`N(R) gives a cumulative positive acknowledgment for data
`packets having sequence numbers before N(R), but does not
`positively acknowledge the data packet having the sequence
`number N(R), as shown for example in FIG. 1A.
`The NACK positively acknowledges all data packets
`before the data packet it negatively acknowledges. The data
`packet which the NACK negatively acknowledges is indi-
`cated by N(R), as shown for example in FIG. 1B.
`FIG. 2 shows a simplified ARQ transmitter window, in
`which five variables are used to keep track of a transmitter
`state. The five variables include: a bottom sequence number,
`BSN; a top sequence number, TSN; a maximum top
`sequence number, TSNW; an instant sequence number,
`ISN; and an expected sequence number, ESN.
`BSN denotes the oldest packet in the transmitter buffer,
`and can also indicate that all packets before the BSN packet
`have been acknowledged or discarded. Packets prior to the
`packet indicated by TSN have been sent. ESN denotes the
`expected sequence number of a packet to be received. ISN
`indicates the sequence number of the next packet to be sent.
`When a packet is sent for the first time, TSN and ISN will
`be identical. However, when a retransmission is performed,
`ISN will start over from the first retransmitted packet and
`progress in consecutive order, one packet at a time, up to
`TSN. TSN cannot exceed TSNMAX, which is defined by the
`window size W. Assuming that a sequence number field has
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`k bits, 2k different sequence numbers can be created. Thus,
`the maximum size W of the window shown in FIG. 2 is 2k—1.
`
`Operation of the Go-Back-N technique using both PACKS
`and NACKS can be envisioned by imagining a clockwise
`consecutive modulo 2k sequence numbering superimposed
`upon the circumference of the circles shown in FIGS.
`3A—3D. FIG. 3A shows a circle indicating a state where no
`packets have yet been sent, and TSN, ESN, BSN and ISN all
`have the same value, i.e., point to the same packet. The circle
`shown in FIG. 3B indicates that (TSN-BSN) packets have
`been sent and also received, since ESN=TSN. An erroneous
`or lost packet causes ESN to stop progressing forward,
`although more packets have been sent. For example, in FIG.
`3C packets up to the packet indicated by TSN and ISN have
`been sent, but ESN indicates a prior packet which was not
`received. After a packet is lost or an erroneous packet is
`received, the ARQ receiver sends a NACK to the ARQ
`transmitter to inform the ARQ transmitter about the lost or
`erroneous packet. The NACK includes a returned sequence
`number N(R) that is set equal to ESN, thereby acknowledg-
`ing that all previous packets were correctly received. BSN
`and ISN are set equal to ESN (and N(R)) so that BSN moves
`forward and ISN moves backward to the sequence number
`representing the lost or erroneous packet. Thereafter, as
`shown in FIG. 3D, ISN and ESN move forward together as
`the lost or erroneous packet is retransmitted, and as the
`succeeding packets are also retransmitted.
`FIGS. 4A—4D illustrate use of a PACK. For example, FIG.
`4A shows a state where nothing has yet been sent, and
`TSN=ISN=BSN=ESN. FIG. 4B shows a situation where all
`
`sent packets have been correctly received. FIG. 4C shows
`that a timer-initiated PACK is sent, conveying the sequence
`number N(R) of a packet between BSN and TSN=ESN=
`ISN. As shown in FIG. 4D, after the PACK is sent, BSN is
`set to N(R).
`Sending PACKS ensures that sequence number starvation
`does not occur. Since TSN may not pass BSN,
`if the
`transmitter does not receive PACKS, it may continue to send
`data packets up to TSNMAX. However, if data packets up to
`TSNMAX are sent but no PACKS are received, then TSNMAX
`cannot progress and sequence number starvation occurs. The
`transmitter must wait until it receives a PACK, which will
`allow BSN and thus TSNMAX to progress.
`FIG. 5 shows a general example of an ARQ data packet
`510. The packet 510 typically includes an ARQ header 512
`and a data portion 516. The header 512 contains a k-bit
`sequence number 514, and can be located at the front of the
`packet 510 as shown in FIG. 5, or at any predefined position
`within the packet 510.
`FIG. 6 shows an exemplary ACK message 610, with an
`identifier field 612 that identifies the responding terminal
`sending the ACK message 610, a NACK/PACK type indi-
`cator 614 indicating whether a PACK or a NACK is being
`sent, and finally a sequence number field N(R) 616 that
`indicates for which sequence number the ACK message 610
`is valid.
`
`In a Selective Reject scheme, a sender window having a
`size of 2k"1 or less is normally used in order to avoid certain
`ambiguities which appear in conjunction with an automatic
`(timer-initiated) retransmission. The receiver window size in
`a Selective Reject scheme can include up to 2k"1 positions,
`instead of just one position as in a Go-Back-N scheme. In
`Selective Reject a range of packets can be received since the
`receiver window can include up to 2’“1 positions.
`As long as packets are received correctly, they are sent or
`forwarded to the next higher layer. When an outstanding
`
`

`

`US 6,424,625 B1
`
`3
`packet is detected, i.e., a packet that has been sent but not
`received or not correctly received, the sending of subsequent
`packets up to the higher layer is halted and a list of correct
`and missing packets is built up. A NACK is used to initiate
`a request for a retransmission of the outstanding packet or of
`a multitude of outstanding packets. When the first detected
`outstanding packet is correctly received, that packet and all
`subsequent packets are sent to the higher layer, until the next
`outstanding packet is detected and the process repeats with
`respect to the new outstanding packet.
`FIG. 7A, for example, shows a situation wherein three
`packets are outstanding. The outstanding packets are
`denoted by ESNl, ESN2 and ESN3. The receiver sends one
`or several NACKs indicating the sequence number of these
`outstanding packets. In FIGS. 7B and 7C, the transmitter has
`received the one or several NACKs and in response retrans-
`mits the outstanding packets. The transmission of new
`packets can proceed to the TSNW limit, which of course
`can also occur when no NACKs are received. In particular,
`FIG. 7B shows a situation where ESNl has been retrans-
`
`mitted and correctly received, and ESNZ is currently being
`retransmitted. BSN has also been set to ESNl. In other
`words,
`the NACK for ESNl functions as a cumulative
`positive acknowledgment for packets preceding ESNl, and
`BSN is adjusted accordingly.
`to reach the transmitter for
`Sometimes, NACKs fail
`unknown reasons. In such a situation, after a specified or
`predetermined time has expired, packets in the sender buffer
`that have not been acknowledged (by either a NACK or a
`PACK) can be automatically retransmitted.
`NACKs can be efficiently sent by sending a NACK and
`explicitly indicating the oldest NACK’s sequence number,
`here represented by ESNl, and using a bitmap to thereafter
`represent correctly received packets and missing packets.
`This type of NACK performs a cumulative PACK for the
`packets preceding the sequence number which is NACKed.
`Other NACK options can also be used, for example NACK
`options where a cumulative positive ACK is not performed
`or sent for the packets preceding the sequence number which
`is NACKed.
`
`The Selective Reject and Go-Back-N techniques differ in
`the sense that Selective Reject does not require packets to be
`sent in any particular order, while the Go-Back-N receiver
`needs to receive packets in consecutive sequence number
`order.
`
`Normally, in data networks it is desirable to transfer all
`packets without any packet loss. Sometimes, however, send-
`ing significantly delayed packets provides no benefit, for
`example where the delay causes the information in the
`packets to become outdated and therefore useless to the
`receiver. Examples of delay sensitive applications are, e.g.,
`telephony, video conferencing and delay sensitive control
`systems.
`Furthermore, non-time-critical applications commonly
`issue higher level retransmissions whenever they detect an
`absence of responses or acknowledgments from the receiv-
`ing end, which can give rise to situations where the ARQ
`buffers are filled with not-yet-successfully transmitted data,
`and/or with newly retransmitted data. This can be avoided if
`data is associated with a validity time, and the validity time
`is set to be slightly shorter than the retransmission time for
`the application. However, in practice it can be difficult or
`impossible to discern which retransmission time is used,
`since the lower layer (LLC) is unaware which application is
`at the top level. In such a situation one has to assume a
`certain application and specially design the communication
`system based on that assumption.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`For certain service classes and after a certain transfer
`delay time, discarding of data packets is allowed in Asyn—
`chronous Transfer Mode (ATM). An ARQ in conjunction
`with ATM can use transfer delay information provided by
`the ATM layer in order to adjust connection-specific discard
`timers in the ARQ function. However,
`the ARQ in the
`receiver may detect missing or incomplete packets and
`require retransmission.
`In summary, current ARQ methods do not recognize and
`allow for situations where data packets have a limited
`lifetime, and therefore fail to minimize bandwidth usage by
`not sending (or resending) significantly delayed or outdated
`data packets.
`SUMMARY OF THE INVENTION
`
`In accordance with exemplary embodiments of the
`invention, ARQ techniques are provided that minimize
`bandwidth usage by accounting for data packets that have an
`arbitrary but limited lifetime. The lifetime can either be
`assumed to be fixed, or can be deduced from ATM layer
`information. In particular, exemplary embodiments of the
`invention variously illustrate enhanced Go-Back-N and also
`Selective Reject
`techniques that discard outdated data
`packets, and which embody principles that can be applied to
`Stop-and-Wait techniques to discard outdated data packets.
`In accordance with an embodiment of the invention, a bit
`is set in the ARQ header to force the receiver to accept
`packets subsequent to one or more erroneous or unreceived
`packets that have been discarded and not resent.
`In accordance with another embodiment of the invention,
`when a NACK has been received and data packets have been
`discarded, sequence numbers are reassigned to the non-
`discarded data packets so that a transmitted stream of the
`non—discarded packets will have consecutive sequence num—
`bers.
`
`In accordance with another embodiment of the invention,
`at a packet discard the transmitter monitors the receiver
`state. If a packet
`is expected which has already been
`discarded, then the transmitter resynchronizes by renumber-
`ing data packets or by commanding the receiver to accept an
`arbitrarily chosen sequence number.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Other objects and advantages of the invention will
`become apparent to those skilled in the art from the follow-
`ing detailed description of preferred embodiments, when
`read in conjunction with the accompanying drawings. Like
`elements in the drawings have been designated by like
`reference numerals.
`
`FIGS. 1A and 1B illustrate a prior art Go-Back-N tech-
`nique.
`FIG. 2 illustrates a window in a prior art Go-Back-N
`technique.
`FIGS. 3A—3D illustrate a transmission sequence in a prior
`art Go-Back-N technique.
`FIGS. 4A—4D illustrate use of a positive acknowledgment
`in a prior art Go-Back-N technique.
`FIG. 5 illustrates a prior art example of an ARQ data
`packet.
`FIG. 6 illustrates a prior art example of an acknowledge-
`ment message.
`FIGS. 7A—7C illustrate use of a negative acknowledg-
`ment in a prior art Selective Reject technique.
`FIG. 8 illustrates a receiver packet enforcement bit in
`accordance with an embodiment of the invention.
`
`

`

`US 6,424,625 B1
`
`5
`FIG. 9 illustrates operation of an embodiment of the
`invention.
`
`FIGS. 10A and 10B illustrate operation of an embodiment
`of the invention.
`
`FIG. 11 illustrates operation of an embodiment of the
`invention.
`
`FIG. 12 illustrates operation of an embodiment of the
`invention.
`
`FIG. 13 illustrates operation of an embodiment of the
`invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`In accordance with an exemplary embodiment of the
`invention involving a communications system wherein a
`transmitter and a receiver are exchanging data packets, at a
`packet discard procedure, the progress of a bottom part of a
`sender window of the transmitter is reported to the receiver
`in order to allow the receiver to properly skip packets which
`do not exist anymore because they have been discarded.
`Thus, the receiver can be commanded to skip or overlook the
`packets which have been discarded, or in other words, to
`release any expectation of receiving the packets which have
`been discarded. To prevent ambiguity problems, special
`rules are defined for, and followed by, the receiver and the
`transmitter.
`
`In the case where the transmitter discards a packet, it
`orders the receiver to accept the next packet, by setting a
`certain Receiver Packet Enforcement Bit (RPEB) in the
`ARQ header of the next packet and sending the packet to the
`receiver. When the receiver receives the packet, the RPEB
`bit will cause the receiver to accept the packet. FIG. 8 shows
`an ARQ packet 810 with an ARQ header 812 and a data
`portion 818. The header 812 includes a receive packet
`enforcement bit RPEB 814, and a k-bit sequence number
`N(S) 816. Alternatively, a plurality of enforcement bits can
`be sent separately from the ARQ packets together with
`implicit or explicit indications as to which ARQ packet each
`enforcement bit belongs.
`This enforcement function of sending an RPEB associated
`with a particular ARQ packet, can be used a variety of
`situations. For example, a situation can arise where a NACK
`associated with an ARQ packet designated by a sequence
`number N(R) is sent by the ARQ receiver and properly
`received by the ARQ transmitter. If the NACK is valid for
`one discarded data packet, then the next data packet to be
`retransmitted can have an RPEB set to TRUE.
`
`In another example situation, a retransmission timer
`expires and one or more data packets have been discarded.
`The next incoming data packet to be transmitted, or the first
`data packet to be retransmitted, can have an RPEB set to
`TRUE.
`
`The system can be further configured so that in all other
`situations, the RPEB associated with a data packet is set
`FALSE.
`
`In particular, when the system uses a Go-Back-N type
`packet exchange, two types of packet enforcement schemes
`can be used. The first type is a general method with an
`arbitrary window size W, and the second type is a special
`case of the general method. In the special case, the window
`size is W=2k'1, i.e., half the maximum sequence number.
`In the method of the special case, ambiguities can be
`circumvented by applying very simple rules. The method of
`the special case employs a new variable, DSN. DSN is
`shown, for example, in FIG. 9, and indicates that all previous
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`packets have been acknowledged as having been properly
`transmitted and received. In FIG. 9, all packets from DSN
`through BSN-1 have been discarded due to a packet discard
`time-out. Apacket discard time-out can occur, for example,
`when the oldest packets in the buffer have been in the buffer
`for a predetermined amount of time, and are discarded upon
`expiration of the predetermined amount of time. When the
`old packets are discarded, the value of BSN is incremented
`until it points to the oldest remaining (i.e., undiscarded)
`packet in the buffer. FIG. 9 shows BSN pointing to the oldest
`remaining packet in the buffer. After the predetermined
`amount of time expires, the value of TSN is greater than or
`equal to the new value of BSN. This indicates that packets
`from BSN through TSN-1 have been sent. TSN indicates the
`next new packet to send, and ISN has the same function as
`indicated earlier, namely, to indicate the sequence number of
`the next packet to be sent. ESN (e.g., ESN1) indicates the
`sequence number of the next packet that the receiver expects
`to receive. To prevent ambiguities, TSN must not pass
`TSNMAX. In this alternative, TSNMAX is DSN+2k'1.
`Although the data packets between DSN and BSN have
`been discarded as shown in FIG. 9, for some unknown
`reason either the previous ACKs have not made their way
`from the ARQ receiver to the ARQ transmitter or the ARQ
`packets from ESNl up to TSN have not been received. That
`explains why ESNl is in the sequence of sequence numbers
`representing discarded ARQ packets, or in other words, why
`the receiver is expecting a sequence number which has been
`discarded. At this juncture either a retransmission timer
`initiates the retransmission, or a NACK is properly received.
`In both cases, the RPEB is set to TRUE for the next packet
`to be transmitted. If the difference between N(S) and ESN
`(for example, ESN1) is less than 2k"1 and RPEB=TRUE at
`a packet reception, then the packet will be accepted and
`forwarded to higher layer as long as the data carried in the
`packet is also correct.
`FIG. 9 also shows that no ambiguity will occur when
`TSNMAX is defined as DSN+2k'1. When ESN (ESN1) lags
`behind BSN, the receiver can always be forced to receive an
`ARQ packet whose RPEB=TRUE. If ESN (ESN1) is leading
`BSN and the RPEB for a received ARQ packet is TRUE,
`then the packet shall not be accepted. This can be determined
`by discerning whether BSN-ESN exceeds W=2k'1. If a
`NACK is received in the ARQ transmitter for a higher
`sequence number than TSN, then a fault has occurred and a
`reinitialization or a restart
`is likely to take place. In a
`reinitialization or a restart, all counters and/or variables are
`reset to a certain value so that the ARQ can restart anew. For
`example, the variables can be set so that TSN=ISN=BSN=
`ESN=DSN, and so forth.
`FIGS. 10A and 10B show the variable definitions more
`
`precisely, by showing two cases. FIG. 10A shows a case
`where the content in the buffer is low, and FIG. 10B shows
`a case where the buffer is very full. FIGS. 10A and 10B also
`indicate that an upper limit (fixed or dynamic) may exist for
`the packet buffer. There may also be packets which have
`been received from the higher layer, but were not allowed to
`be transmitted since TSN might have reached TSNMAX.
`Such packets would be pending for transmission, and indi—
`cated by pending sequence number PSN shown in FIG. 10B.
`As soon as clearance is given to proceed,
`the pending
`packets will be transmitted. Clearance is given when a
`NACK or PACK is properly received, thereby causing DSN
`and perhaps also BSN to progress forward. This allows
`TSNMAX to progress forward also.
`The more general case, on the other hand, requires more
`complex rules. The function of the ARQ transmitter with an
`
`

`

`US 6,424,625 B1
`
`7
`arbitrary window size representing a more general case is
`next described.
`
`FIG. 11 shows an arbitrary state of the ARQ. The general
`case differs from the special case described above in that the
`window size (W) is defined using BSN rather than DSN.
`This gives the greatest possible distance between the last
`acknowledged packet (DSN) and the highest sent packet
`(TSN). As in the special case, TSN may not pass TSNMAX.
`TSNMAX=BSN+W, where 1§w;2’°—1-
`Below, the sign E is used. It is used more in the “before”
`and “after” sense than in the ordinary mathematical sense,
`since we are using modulus arithmetic. For example, assume
`k=8 bits, BSN=192 and W=128. This yields BSN+W=(192+
`128)mod2k=64. TSN can be, e.g., 254, which is before
`BSN+W, even though mathematically 254>(192+128)
`mod2k=64.
`
`Some important conditions are TSNéDSN-l,
`TSNéTSNW, and DSNéBSNéTSN, where TSNMAX=
`BSN+W. W can assume an arbitrary value between 1 and
`2k'1. However, the receiver and transmitter must both use
`the same arbitrary value for W.
`from the normal
`A packet shall be accepted, apart
`Go-Back-N function, when N(S)-ESN<2k—W, RPEB=
`TRUE and the data in the packet are correct.
`An additional rule for the general case is that in order to
`avoid ambiguity problems, BSN-DSN shall always be less
`than 2k—W. If a situation arises where (BSN-DSN)=2k—W,
`then typically either a resynchronization will take place, or
`a notification indicating bad link performance will be sent to
`the control and management layer. The control and man-
`agement
`layer can then implement a countermeasure to
`handle the problem.
`In another exemplary embodiment of the invention illus-
`trated for example in FIG. 12, a Selective Reject type packet
`exchange is used that relies on the same basic principles
`described above with respect to the special and general cases
`for use with a Go-Back-N type packet exchange. Namely, a
`receive enforcement bit such as the RPEB described above
`
`is sent
`with respect to other embodiments,
`discarding of packets from a transmitter buffer.
`In this embodiment,
`the basic rules include
`DSNéBSNé TSNé TSNMAX and TSNMAX—DSN=2k'1. The
`variable definitions are the same as those described above
`
`to facilitate
`
`with respect to other embodiments. Some additional rules on
`how to handle NACK, PACK and automatic retransmission
`of packets will also be described below.
`In a situation where a number of packet retransmissions
`have taken place, a packet discard time-out can occur that
`will cause the oldest, not-yet-acknowledged packets in the
`buffer to be discarded. This can be seen, for example, in FIG.
`12, where the packets having sequence numbers between
`DSN and BSN have been discarded.
`
`After the old packets have been discarded from the
`transmitter buffer, two things can happen. Either a packet
`retransmission command is invoked by a timer expiration, or
`a NACK is received for a sequence number falling between
`DSN and BSN. First, consider the NACK case.
`Assume that one use of NACK includes the following
`characteristics. When a NACK is sent, the oldest not-yet-
`received packet is explicitly indicated by its sequence num-
`ber. Packets with sequence numbers preceding this oldest,
`outstanding packet are at the same time positively acknowl-
`edged by this NACK message. Accompanying this NACK
`can be a) a bitmap of length n indicating outstanding
`packets, wherein, for example, those bits that are set to one
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`indicate outstanding packets, or b) a number N of explicitly
`indicated sequence numbers for which packets have not
`been received, or c) some combination of a) and b).
`In a first case, with reference to FIG. 12, if a NACK is
`received for ESN1 in the interval DSN to BSN and the
`
`covered ACK range for the NACK is less than BSN-ESN1
`and at least one packet is not yet discarded (TSNasBSN),
`then the packet indicated by BSN with RPEB set to True, is
`retransmitted. Note that the transmitter can also send a short
`control message, in order to inform the receiver that packets
`have been discarded, thereby saving bandwidth.
`In a second case, if a NACK is received for ESN1 located
`in the interval between DSN and BSN and the covered ACK
`
`range for the NACK is less than BSN—ESN1 and all packets
`have been discarded, i.e. BSN=TSN, then a pending packet
`with RPEB=TRUE is sent. However, if no packet is pending
`for transmission, then the system either a) waits until the
`next packet is received from the higher layer and then sends
`this packet with RPEB=TRUE, or b) informs the receiver
`that there are currently no more packets to send. A shorter
`message than the packet can be used instead to inform the
`receiver that packets have been discarded; thereby conserv-
`ing bandwidth.
`In a third case, if a NACK is received for ESN1 in the
`interval DSN to BSN, and the covered ACK range for the
`NACK is greater than BSN-ESN1, and at least one packet is
`not yet discarded, and at least one outstanding packet exists
`that has a sequence number EBSN, then the first outstanding
`packet after BSN, as indicated by the NACK message, is
`retransmitted with RPEB=TRUE.
`
`In a fourth case, if a) a NACK is received for ESN1 in the
`interval between DSN and BSN, and b) the covered ACK
`range for the NACK is greater than BSN—ESN1, and c) at
`least one packet exists that has been sent but not acknowl-
`edged either positively or negatively and which has a
`sequence number after the packet indicated by the NACK
`message, and d) there are no outstanding packets indicated
`in the NACK message with sequence numbers EBSN, then
`the first packet after the packets indicated in the NACK
`message is retransmitted with RPEB=TRUE. A shorter mes—
`sage than the packet can be used instead to inform the
`receiver that packets have been discarded, thereby saving
`bandwidth.
`
`In a fifth case, if a) a NACK is received for ESN1 in the
`interval DSN to BSN, and b) the covered ACK range for the
`NACK is greater than BSN-ESN1, and c) no packet exists
`after the packet indicated by the NACK message, and d)
`there are no outstanding packets indicated in the NACK
`message with sequence numbers EBSN,
`then a packet
`which is pending for transmission is sent with RPEB=
`TRUE. In other words, when all packets having sequence
`numbers N(S) in the range from BSN to TSN (i.e., TSNéN
`(S)§BSN) have been positively acknowledged,
`then a
`packet which is pending for
`transmission is sent with
`RPEB=TRUE. However,
`if no packet
`is pending for
`transmission, then the system waits until the next packet is
`received from the higher layer and then sends this next
`packet with RPEB=TRUE, or alerts the receiver that there
`are currently no more packets to send. A shorter message
`than the packet can be used instead to alert the receiver that
`packets have been discarded, thereby saving bandwidth.
`In a sixth case, when a timer-initiated retransmission of a
`packet occurs, and ISN=BSN, then RPEB should be set to
`TRUE. Otherwise, RPEB should be set
`to FALSE.
`Alternati