PATENT APPLICATION SERIAL NO.
`
`U.S. DEPARTMENT OF COMMERCE
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`
`11/04/19a Samu 00000087 017Ms
`790.00 O
`01 FC%101
`SL.00p
`02 FCt10e
`
`PTO-1556
`(5/87)
`'U.S. GPO: 19We4M.-214/00404
`
`

`
`SERIAL NUMBER
`
`PIIG AE
`
`CLASS
`
`GROUP ART UNIT
`
`ATTORNEY DOCKET NO.
`
`09/179,952
`
`102/8
`
`370
`
`2731
`
`040000-101
`
`PETER LARSSON,
`SINGAPORE.
`
`SINGAPORE, SINGAPORE1 MIKARL LARSSON, SINGAPORE,
`
`**CONTINUJING DOMESTIC DAA**********n
`VERIFVIED
`
`,i(
`
`**371 (NAT'L STAGE)DAA**********q
`VERI FIRD
`
`JtL-
`
`"*FOREIGN APPLICATIONS************
`VERIFTIED
`
`q lxe
`
`SHTSTOTAL
`QenoSAEO
`.5reUgn Priority claimed
`3 ISC1 (a.d) condition, met OVeafWno O]Met after Allowance CONRY DAIG
`Verified and Acknowledged
`SG~9BX
`5
`
`CLAIMS
`19
`
`INDEPENDENT
`CAM
`4
`
`RONALD L. GRUDZIECKI
`BURNS DOANE SWECKCER AND MATHIS
`Po0sOX 1404
`ALEXANDRIA VA 22323-1404
`
`METHOD AND APPARATUS FOR DISCARDING PACKETS
`&UTO0"TZC RNPIAT ANIQUE111
`
`IN A DATA NETWORK HAVING
`
`FILING FEE
`RECEIVED
`
`$1,002
`
`FEES: Authority has been given In Paper
`to charge/credit DEPOSIT ACCOUNT
`No. ___
`No. _______
`for the following:
`
`_____________________________________________
`
`Alfe
`15 1 AlFees
`(iig
`1.17 Fees (Processing Ext. of time)
`1.18 Fees tissue)
`Ej Other _______
`[] Credit
`
`

`
`-25-
`
`ABSTRACT OF THE DISCLOSURE
`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
`
`5
`
`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 accordance with another embodiment of thle
`invention, after data packets have been discarded, sequence numbers are
`reassigned 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
`
`fl
`
`10
`
`sequence numbers.
`
`ru
`
`rVl
`
`

`
`Ul
`
`-FU
`4
`61
`
`PATENT
`Atty Dkt. No.040000-101
`
`METHOD AND APPARATUS FOR DISCARDING PACKETS IN
`A DATA NETWORK HAVING AUTOMATIC REPEAT REQUEST
`
`FIELD OF THE INVENTION
`The present invention relates to Automatic Repeat Request (ARQ)
`
`5
`
`techniques for transferring data in fixed/wireless data networks,
`
`10
`
`ARQ techniques are commonly used in data networks to ensure reliable
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`20
`
`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 techniques in both efficiency and complexity.
`
`

`
`rn
`
`ru
`
`LI
`
`W
`
`With respect to Go-Back-N, several different variants exist which differ in
`terms of how they use positive acknowledgments (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. IA.
`The NACK positively acknowledges all data packets before the data packet
`it negatively acknowledges. The data packet which the NACK negatively
`acknowledges is indicated by N(R), as shown for example in FIG. 113.
`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, TSNMAX; an instant sequence number, ISN; and an expected
`sequence number, ESN.
`BSN denotes the oldest packet in the transmitter buffet, 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 TSNmA,
`which is defined by the window size W. Assuming that a sequence number field
`has k bits, 2 ' different sequence numbers can be created. Thus, the maximum size
`W of the window shown in FIG. 2 is 2k 11
`
`5
`
`10
`
`15
`
`20
`
`25
`
`

`
`Ill
`
`5
`
`NW
`
`5
`
`10
`
`15
`
`20
`
`25
`
`Operation of the Go-Back-N technique using both PACKs and NACKS can
`be envisioned by imagining a clockwise consecutive module 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 acknowledging that all previous packets were correctly received. BSN and
`ISN are set equal to ESN (and N(R)) so that BSN moves forward and LSN 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 =ESNT= SN, 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
`
`

`
`-4-
`
`sequence number starvation occurs. The transmitter must wait until it receives a
`to progress.
`PACK, which will allow BSN and thus TSNM,
`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.
`Figure 6 shows an exemplary ACK message 610, with an identifier field
`612 that identifies the responding terminal sending the ACK message 610, a
`NACKIPACK type indicator 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 21 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 21(. 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 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 ESN I, ESN2 and ESN3. The
`receiver sends one or several NACKs indicating the sequence number of these
`
`M
`IV
`
`n.j
`
`5
`
`10
`
`15 i
`
`20
`
`25
`
`

`
`outstanding packets. In FIGS. 7B and 7C, the transmitter has received the one or
`several NACKs and in response retransmits the outstanding packets. The
`transmission of new packets can proceed to the TSNMAX limit, which of course can
`also occur when no NACKs are received. In particular, FIG. 7B shows a situation
`where ESNI has been retransmitted and correctly received, and ESN2 is currently
`being retransmitted. BSN has also been set to ESNI. In other words, the NACK
`for ESN I functions as a cumulative positive acknowledgment for packets
`preceding ESNI, and BSN is adjusted accordingly.
`Sometimes, NACKs fail to reach the transmitter for 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 ESN1, 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
`he 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 sequ1ence number
`order.
`
`Normally, in data networks it is desirable to transfer all packets without
`any packet loss. Sometimes, however, sending 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
`
`5
`
`10
`
`15
`
`20
`
`25
`
`w1
`W
`
`0
`
`N
`
`W
`
`

`
`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
`
`5
`
`from the receiving 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
`
`10 t
`
`Wl
`
`assumption.
`
`9
`
`(U
`
`15
`
`20
`
`25
`
`For certain service classes and after a certain transfer delay time,
`discarding of data packets is allowed in Asynchronous 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 fir 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
`
`

`
`-7-
`
`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 numbers.
`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 renumbering
`data packets or by commanding the receiver to accept an arbitrarily chosen
`sequence number.
`
`5
`
`10
`
`Ill
`
`Tb
`
`iii
`
`15
`
`20
`
`25
`
`BRIEF DESCRIPTION OF THTE DRAWINGS
`Other objects and advantages of the invention will become apparent to
`those skilled in the art from the following detailed description of preferred
`embodiments, when read it.)6onijunction with the accompanying drawings. Like
`elements in the dry*ing/have been designated by like reference numerals.
`FIGS. r)A'and 11141lustrate a prior art Go-Back-N technique.
`/etrts a window in a prior art Go-Back-N technique.
`i
`FIG
`FIGS. 3L-D illust ifte a transmission sequence in a prior art Go-Back-N
`technique.7
`FIGS. 4/A-4D) illustrate use of a positive acknowledgment in a prior art Go
`Back-N techniq e
`FIG. 5/4lustrates a prior art example of an ARQ data packet.
`
`

`
`Lni
`
`0
`
`Z
`co
`
`5
`
`10
`
`~fl
`
`20
`
`25
`
`FIG. 6 illpstra/sa prior art example of an acknowledgement message.
`FIGS. 7A-7C illustrate use of a negative acknowledgment in a prior art
`
`hcini,ue.
`Selective Reject
`FIG. 8 7illustrates a receiver packet enforcement bit in accordance with an
`invention.
`embodiment of #l~
`FIG. 9 illustrakes opa~tion of an embodiment of the invention.
`FIGS. 1706nd 1083 illustrate operation of an embodiment of the invention.
`FIG. I llstrates 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
`
`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 8 10 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 hits can be sent separately from the ARQ packets
`
`

`
`l"
`
`5
`
`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
`NCR) 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
`10i more data packets have been discarded, The next incoming data packet to be
`transmitted, or the first data packet to he retransmitted, can have an RPEB set to
`TRUE.
`
`15
`
`20
`
`25
`
`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=2-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 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. A packet 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-1I 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., ESNI) 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+2'k'.
`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 ESNM up to TSN have not been received. That explains why ESN1 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 tinier initiates the
`retransmission, or a NACK is properly received. In both cases, die RPEB is set to
`TRUE for the next packet to be transmitted. If the difference between N(S) and
`
`5
`
`10
`
`Ul
`
`flJ
`
`ru
`
`15
`
`ESN (for example, ESNI) 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
`
`20
`
`25
`
`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+2"1' When ESN (ESNI) lags behind BSN, the receiver can always be
`forced to receive an ARQ packet whose RPEB =TRUE. If ESN (ESN I) 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 NACKC 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
`
`

`
`5
`
`10
`
`U1
`
`H.
`
`[u
`
`ru
`
`PA
`
`15
`
`ej
`
`20
`
`25
`
`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. IOA and IOB show the variable definitions more precisely, by
`showing two cases. FIG. 1OA shows a case where the content in the buffer is low,
`and FIG. IOB shows a ease where the buffer is very full. FIGS. IOA and IOB 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 indicated by pending sequence
`number PSN shown in FIG. 1OB. 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 arbitrary window size representing a
`more general case is next described.
`Figure 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 ligW 2k-1.
`Below, the sign - 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+1l28)mod2kl=64. TSN can be, e.g., 254, which is before BSN +t
`W, even though mathematically 254> (192+ 128)mod2k=64.
`Some important conditions are TSN DSN-I, TSN
`TSNmmJ, and DSN
`BSN - TSN, where TSNmx=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.
`A packet shall be accepted, apart from the normal Go-Back-N function,
`when N(S)-ESN < 2kW, 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 2 k_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 management layer can then implement a
`countermeasure to handle the problem.
`In another exemplary embodiment of the invention illustrated 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 with respect to other embodiments, is sent to
`facilitate 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
`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
`
`5
`
`10
`
`15
`
`20
`
`25
`
`ILn
`ru
`
`ru
`
`a
`CO
`
`

`
`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 number, Packets with sequence numbers preceding this oldest,
`outstanding packet are at the same time positively acknowledged 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 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 ESNI
`in the interval DSN to BSN and the covered ACK range for the NACK is less than
`BSN-ESNI and at least one packet is not yet discarded (TSN * BSN), then the
`packet indicated by BSN with RPEB set to True, is retransmitted. Note that the
`
`5
`
`10
`
`Ln
`
`o
`
`15
`
`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 ESNI located in the interval
`between DSN and RSN and the covered ACK range for the NACK is less than
`BSN-ESN I and all packets have been discarded, i.ec. 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 conserving bandwidth.
`In a third case, if a NACK is received for ESNI 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
`
`20
`
`25
`
`ni
`
`ru
`
`dw,
`
`COj
`
`

`
`5
`
`10
`
`15
`
`n.J
`
`ru
`
`~fl
`Ln
`
`CO
`
`20
`
`25
`
`that has a sequence number > BSN, 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 ESNI in the interval between
`DSN and BSN, and b) the covered ACK range for the NACK is greater than BSN-
`ESNI, and c) at least one packet exists that has been sent but not acknowledged
`
`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
`, BSN, then the first packet after
`in the NACK message with sequence numbers
`the packets indicated in the NACK message is retransmitted with RPEB = TRUE.
`A shorter message 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 ESN I 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
`, BSN, then a packet which is pending for transmission is Sent with
`numbers
`RPEBH=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 = B3SN, then RPEB should be set to TRUE. Otherwise, RPEB should be
`set to FALSE. Alternatively, RPEB can be set to TRUE when ((ISN=BSN) and
`(BSNoDSN)), and can otherwise be set to FALSE.
`
`

`
`5
`
`10
`
`When a correct packet with RPEB =TRUE is received, then all packets
`
`preceding this packet and up to the next outstanding packet will be released from
`the buffer and forwarded to the higher layer. The application or the other layers
`
`decide whether the packets can be used or not, if delay and assembly requirements
`
`are met.
`In the case where a window of size < 2k
`capability concerns are necessary to consider, beyond the ordinary requirement
`imposed by Selective Reject itself.
`
`is used, no additional discard
`
`In another embodiment of the invention for use with a Go-Back-N scheme,
`
`it is assumed that resynchronization takes place only when a NACK is received
`and N(R) < BSN. Then the transmitter will have full knowledge of the receiver
`state, i.e., ESN is known. Note that there exists a case where a NACK as
`
`described above is received and the receiver can wait one round-trip delay period
`to ensure full] knowledge of the receiver state. In other words, when a
`
`15
`
`retransmission of the NACKed packet has just been performed and it is not known
`
`20
`
`25
`
`if the packet has passed all buffers and other delay-causing functions, the receiver
`can wait one round-trip delay period. Here, renumbering of packets sequence
`number can be performed, such that the first ARQ packet sent after the
`
`renumbering will carr y the same sequence number as that of the packet to which
`the NACK referred.
`In FIG. 13, a NACK is received for a discarded packet, since ESN
`
`precedes BSN. Consequently, all subsequent packets from BSN and onwards are
`renumbered such that the BSN packet starts with ESN, the BSN + I packet is
`renumbered to ESN + 1, and so on. Note, renumbering is not performed for timer-
`initiated retranismissions.
`In another embodiment of the invention for use with a basic Go-Back-N
`scheme, the receiver and the transmitter are resynchronized at each discard
`
`occasion. In this embodiment, ARQ packets can only be discarded if they have not
`previously been acknowledged.
`
`NZ
`
`f
`
`LII
`ru
`
`ru
`
`

`
`The resynebronization is initiated by the transmitter, since it knows when a
`discard has been performed. The transmitter ask for a sequence number, up to
`which (but not including) the receiver has accepted ARQ packets. If the sequence
`number is before the last discarded sequence number, then the transmitter
`corrmands the receiver to start over from some arbitrarily chosen, but predefined,
`sequence number. The next sent packets are numbered upwards from this
`arbitrarily