(12) United States Patent
`Abrol
`
`USOO6507582B1
`(10) Patent No.:
`US 6,507,582 B1
`(45) Date of Patent:
`Jan. 14, 2003
`
`(54) RADIO LINK PROTOCOL ENHANCEMENTS
`FOR DYNAMIC CAPACITY WIRELESS
`DATA CHANNELS
`
`(75) Inventor: Nischal Abrol, San Diego, CA (US)
`(73) Assignee: Qualcomm Incorporated, San Diego,
`CA (US)
`
`(*) 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.: 09/321,296
`(22) Filed:
`May 27, 1999
`(51) Int. Cl. .......................... H04L 1228. H04B 7,212
`(52) U.S. Cl. ....................... 370,394 370.252, 370,335.
`370/342
`(58) Field of Search ................................. 370/246,389,
`370/252,392,393, 465, 473, 474, 475
`394 335 342. 348,384. 345/132. 153.
`714/782, 701
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,617,657 A * 10/1986 Drynan et al. .............. zoo
`5.151899 A 9/1992 Thomas et al. ............ 370/94.1
`5,444,709 A 8/1995 Riddle ....................... 370/94.1
`5,703,902 A * 12/1997 Ziv et al. ...
`... 370/228
`5,771,033 A * 6/1998 Katzenberger .............. 345/132
`
`5,793,744. A * 8/1998 Kanerva et al. ............ 370/209
`5,920,352 A
`7/1999 Inoue ......................... 348/384
`6,011.806 A * 1/2000 Herring ...................... 370/494
`6,088,342 A * 7/2000 Cheng et al. ............... 370/320
`OTHER PUBLICATIONS
`TIA/EIA/IS-707–A.2 “Data Service Options for Spread
`Spectrum Systems: Radio Link Protocol’ pp. i-section 4-11
`(Mar. 1999).
`TIA/EIA-707-A.8 “Data Service Options for Spread Spec
`trum Systems: Radio Link Protocol Type 2 pp. i-section
`4–12 (Mar. 1999).
`* cited by examiner
`Primary Examiner Steven Nguyen
`Assistant Examiner Phuongchau Ba Nguyen
`(74) Attorney, Agent, or Firm-Philip Wadsworth; Kent D.
`Baker; Byron Ya?uso
`ABSTRACT
`(57)
`An improved method and System for transmitting a stream
`of data bytes through a channel whose capacity may change
`during transmission. By utilization of Selective regions of
`Sequence number Space, the enhanced radio link protocol
`(RLP) provides the benefits of large byte sequence numbers
`while transmitting a fraction of the Sequence number bits in
`the majority of over-the-air frames. Frame header Sequence
`numbers are shortened by dividing the byte sequence num
`ber by a page size, and by performing a modulo function on
`the byte Sequence number.
`
`12 Claims, 6 Drawing Sheets
`
`
`
`100
`
`102
`
`104
`
`1 10
`
`DATA
`
`UNUSED DATA
`
`UNUSED
`
`-122--124-2-126-pk-128--130--132
`k-134A->-134B->H134C->
`150
`OO
`140
`
`DATA UNUSED
`
`
`
`
`
`154
`
`164
`
`104 144
`
`Page 1 of 15
`
`

`

`U.S. Patent
`
`Jan. 14, 2003
`
`Sheet 1 of 6
`
`US 6,507,582 B1
`
`100
`
`102
`
`104
`
`110
`
`DATA UNUSED
`
`DATA
`
`UNUSED DATA
`
`UNUSED
`
`-122--124-2-126-k- 128-2-130-k-132->
`kH 134A->-134B->-134C->
`150
`100
`40
`
`SEQ
`
`152
`
`SEQ
`
`DATA
`
`102
`
`DATA
`
`154 - 164 -104 44
`
`142
`
`FIG. 1
`
`
`
`200N-1
`
`200A
`
`DATA
`-220A->
`
`
`
`
`
`200N
`
`210
`
`DATA
`DATA
`:-on--- 220N
`228->
`
`240A -250A
`
`200A
`
`230A
`
`240N-1
`
`250N-1
`
`200N-1
`
`230N-1
`
`240N
`
`250N
`
`200N 230N
`
`FIG 2
`
`Page 2 of 15
`
`

`

`Sheet 2 of 6
`
`U.S. Patent
`
`Jan. 14, 2003
`
`Caan CCE
`
`I-07Tind
`
`éOFS
`
`SHAééOSLId-8OSLId-8
`
`I€
`
`SHA
`
`80¢
`
`HTdIWaos
`
`AWVdd
`
`LINSNVULadWaOALINSNVLadWaOdAINVddWud
`
`
`
` OSLId-07/MANVOdSLid-viU/MANVaAOdSLIG-r1/M
`
`pie
`
`US 6,507,582 B1
`
`
`
`OCC
`
`LINSNVaL
`
`HNVas
`
`€“OIA
`
`
`
`LINSNVaLadWaOsAWNVddWaOt
`
`
`
`OdSLId-8/MFNVAOSLId-8/M
`
`Page 3 of 15
`
`Page 3 of 15
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 14, 2003
`
`Sheet 3 of 6
`
`US 6,507,582 B1
`
`
`
`
`
`RIO HTICII CINEIS
`
`
`
`?, JLSOTI VJLVCI
`
`
`
`
`
`V LVCI JLOVRIJLXEI CINV
`
`
`
`EIWNWRIH HAIGHOETRI
`
`YHOEFICIVQHH QH LV (TTVAGI
`
`
`
`
`
`
`
`
`
`
`
`
`CINEIS CINV INDRIOH
`
`
`
`EIWIVNIH VJLVCI
`
`
`
`{{WIVYHH XIV.N.
`
`Page 4 of 15
`
`

`

`U.S. Patent
`
`Jan. 14, 2003
`
`Sheet 4 of 6
`
`US 6,507,582 B1
`
`
`
`9 IS
`
`XQHOWNEIWN
`
`0 IS
`
`XQHOWNEIWN
`
`809
`
`Page 5 of 15
`
`

`

`U.S. Patent
`
`Jan. 14, 2003
`
`Sheet 5 of 6
`
`US 6,507,582 B1
`
`ASSIGN
`SEQUENCE
`NUMBERS
`
`602
`
`604
`
`GENERATE SHORTENED
`SEQUENCE
`NUMBER
`
`606
`
`FORMAT SHORTENED
`SEQUENCE NUMBER INTO
`A FRAME HEADER
`
`
`
`608
`
`TRANSMIT
`FRAME WITH
`FRAME HEADER
`
`FIG. 6
`
`Page 6 of 15
`
`

`

`U.S. Patent
`
`Jan. 14, 2003
`
`Sheet 6 of 6
`
`US 6,507,582 B1
`
`702
`
`704
`
`706
`
`708
`
`EXTRACT SHORTENED
`SEQUENCE NUMBER
`FROM FRAME HEADER
`
`GENERATE
`UNSHORTENED
`SEQUENCE NUMBER
`
`ASSIGNSEQUENCE
`NUMBERS
`
`FORM BYTE STREAM
`FROM THE ASSIGNED
`SEQUENCE NUMBERS
`
`FIG. 7
`
`
`
`
`
`
`
`Page 7 of 15
`
`

`

`US 6,507,582 B1
`
`1
`RADIO LINK PROTOCOL ENHANCEMENTS
`FOR DYNAMIC CAPACITY WIRELESS
`DATA CHANNELS
`
`2
`Radio Link Protocol (RLP) is described in TIA/EIA/IS
`707-A.8, entitled “DATA SERVICE OPTIONS FOR
`SPREAD SPECTRUM SYSTEMS: RADIO LINK PRO
`TOCOL TYPE 2', hereinafter referred to as RLP2, and
`incorporated herein by reference. RLP2 incorporates an
`error control protocol with frame retransmission procedures
`over the IS-95 frame layer. RLP is of a class of error control
`protocols known as NAK-based ARQ protocols, which are
`well known in the art. The IS-707 RLP, facilitates the
`transmission of a byte-stream, rather than a Series of Voice
`frames, through an IS-95 communication System.
`Several protocol layers typically reside above the RLP
`layer. IP datagrams, for example, are typically converted
`into a Point-To-Point Protocol (PPP) byte stream before
`being presented as a byte Stream to the RLP protocol layer.
`AS the RLPlayer ignores the protocol and framing of higher
`protocol layers, the stream of data transported by RLP is said
`to be a “featureless byte stream”.
`RLP was originally designed to Satisfy the requirements
`of sending large frames through an IS-95 channel. For
`example, if an IP datagram of 500 bytes were to be simply
`sent in IS-95 frames carrying 20 bytes each, the IP datagram
`would fill 25 consecutive IS-95 frames. Without Some kind
`of error control layer, all 25 of these frames would have to
`be received without error in order for the IP datagram to be
`useful to higher protocol layers. On an IS-95 channel having
`a 1% frame error rate, the effective error rate of the IP
`datagram delivery would be (1-(0.99)), or 22%. This is a
`very high error rate compared to most networks used to carry
`Internet Protocol traffic. RLP was designed as a link layer
`protocol which would decrease the error rate of IP traffic to
`be comparable to the error rate typical of a 10Base2 ethernet
`channel.
`The International Telecommunications Union recently
`requested the Submission of proposed methods for providing
`high rate data and high-quality Speech Services over wireleSS
`communication channels. A first of these proposals was
`issued by the Telecommunications Industry ASSociation,
`entitled “The cdma2000 ITU-R RTT Candidate
`Submission', and hereinafter referred to as cdma2000. A
`Second of these proposals was issued by the European
`Telecommunications Standards Institute (ETSI), entitled
`“The ETSI UMTS Terrestrial Radio Access (UTRA) ITU-R
`RTT Candidate Submission', also known as “wideband
`CDMA and hereinafter referred to as W-CDMA. A third
`proposal was submitted by U.S. TG 8/1 entitled “The
`UWC-136 Candidate Submission', hereinafter referred to as
`EDGE. The contents of these submissions are public record
`and are well known in the art.
`RLP2 is optimized for use with IS-95B, in which the rate
`Set, derived from channel capacity, and used during a packet
`data call remains essentially fixed for the duration of the call.
`Based on this assumption of fixed rate sets, RLP2 is
`designed with the assumption that retransmitted RLP frames
`can be sent within a maximum of three consecutive RLP
`Segments. The probability that one of three Segments is lost,
`causing the loSS of a retransmitted RLP frame, has been
`deemed acceptable by the designers of RLP2.
`In cdma2000, however, the channel capacity available to
`a single user, and hence the maximum data rate used during
`a packet data call, can vary widely and rapidly. For example,
`during the course of a single cdma2000 call, the Supplemen
`tal channel capacity used by a packet data Service option
`may vary from 9.6 kilo-bits per second (kbps) to more than
`307 kbps. In a simple extension of the RLP2, the maximum
`number of Segments used during retransmissions could be
`
`BACKGROUND OF THE INVENTION
`I. Field of the Invention
`The current invention relates to wireleSS communications.
`More particularly, the present invention relates to an
`improved method and System for reliably transmitting data
`through a wireleSS channel while minimizing the overhead
`inherent in the error control protocol.
`II. Description of the Related Art
`The use of code division multiple access (CDMA) modu
`lation techniques is one of Several techniques for facilitating
`communications in which a large number of System users are
`present. Other multiple access communication System
`techniques, Such as time division multiple access (TDMA),
`frequency division multiple access (FDMA) and AM modu
`lation Schemes Such as amplitude companded Single Side
`band (ACSSB) are known in the art. These techniques have
`been Standardized to facilitate interoperation between equip
`ment manufactured by different companies. Code division
`multiple acceSS communications Systems have been Stan
`dardized in the United States in Telecommunications Indus
`try Association TIA/EIA/IS-95-B, entitled “MOBILE
`STATION-BASE STATION COMPATIBILITY STAN
`DARD FOR DUAL-MODE WIDEBAND SPREAD SPEC
`TRUM CELLULAR SYSTEMS, incorporated by refer
`ence herein, and hereinafter referred to as IS-95.
`IS-95 was originally optimized for transmission of
`variable-rate Voice frames. In order to Support two-way
`Voice communications, as typified in wireleSS phone
`applications, it is desirable that a communication System
`provide fairly constant and minimal data delay. For this
`reason, IS-95 systems are designed with powerful forward
`error correction (FEC) protocols and vocoders which are
`designed to respond gracefully to Voice frame errors. Error
`control protocols which require frame retransmission pro
`cedures add unacceptable delays to Voice transmission, So
`are not designed into the IS-95 specification.
`The optimizations which make the standalone IS-95
`Specification ideal for voice applications make it difficult to
`use for packet data applications. In many non-voice
`applications, Such as the transmission of Internet protocol
`(IP) data, the delay requirements of the communication
`System are much leSS Stringent than in Voice applications. In
`the Transmission Control Protocol (TCP), probably the most
`prevalent of protocols used in an IP network, virtually
`infinite transmission delays are allowed in order to guarantee
`error-free transmission. TCP uses retransmissions of IP
`datagrams, as IP packets are commonly called, to provide
`this transport reliability.
`IP datagrams are generally too large to fit into a single
`IS-95 frame. Even after dividing an IP datagram into seg
`ments small enough to fit into a series of IS-95 frames, an
`entire series of IS-95 frames would have to be received
`without error for the single IP datagram to be useful to TCP.
`The frame error rate typical of an IS-95 system make the
`probability of error-free reception of all Segments of a single
`datagram very low.
`As described in IS-95, alternative service options enable
`the transmission of other types of data in lieu of Voice
`frames. The TIA/EIA/IS-707-A, entitled “DATASERVICE
`OPTIONS FOR SPREAD SPECTRUM SYSTEMS”, here
`after referred to as IS-707, describes procedures used in the
`transmission of packet data in an IS-95 System.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 8 of 15
`
`

`

`3
`increased as necessary to accommodate the change in data
`rates. Because the capacity of a call channel may diminish
`during a call, a full-rate frame transmitted unsuccessfully at
`a high rate might span 30 or more consecutive lower-rate-set
`cdma2000 segments. The high likelihood that one or more of
`those cdma2000 Segments makes Such a simple extension of
`the RLP2 largely impractical for use with cdma2000.
`RLP2 has been optimized to require minimal protocol
`overhead space over the two IS-95 rate sets, known as Rate
`Set 1 (RS1) and Rate Set 2 (RS2). The RLP frame sequence
`numbers in RLP2 are 8 bits long, a size which is ideal for
`computer processing. Since the rate Sets Specified in
`cdma2000 include RS1 and RS2, it would be highly desir
`able for an RLP designed for cdma2000 (RLP2000) to be at
`least as efficient as RLP2 mwhen used at RS1 and RS2.
`Because Switching RLP protocols whenever the rate set
`changes would add complexity to RLP2000, it is desirable
`that a single RLP2000 protocol efficiently support RS1,
`RS2, and all the higher cdma2000 data rates without requir
`ing resynchronization or Substantial protocol complexity.
`
`5
`
`15
`
`SUMMARY OF THE INVENTION
`The present invention may be used to design an enhanced
`RLP to enable efficient transmission of a featureless byte
`Stream through a channel of varying capacity. An exemplary
`embodiment of the invention is as efficient as RLP2 when
`used over a channel having the same capacity as IS-95 RS1
`and RS2. At the same time, an enhanced RLP, designed in
`accordance with the current invention, also enables efficient
`transmission of data at varying channel capacities up to and
`exceeding the maximum specified in cdma2000. The present
`invention is applicable to any communication System
`employing transmission of a byte Stream over a wireleSS
`channel. The present invention is applicable to Systems. Such
`as cdma2000, W-CDMA, and EDGE, wherein a byte stream
`may be carried within over-the-air frames Specified for use
`by the wireleSS communication System.
`The efficiency of the embodiments of the invention at
`varying rates is made possible by changing the interpretation
`of the sequence numbers carried in the RLP protocol header.
`In RLP2, Sequence numbers are used to denote frame
`numbers. This is appropriate for RLP2, as the channel
`capacity used in a packet data call, and hence the maximum
`number of data bytes carried in a full-rate frame, are both
`constant. RLP2 uses a one-byte frame Sequence number, and
`frames are transmitted at 20 millisecond (ms) intervals.
`When an RLP2 frame is lost during transmission, the data of
`the lost frame is Segmented into as many as three retransmit
`Segments, each having the same Sequence number as the
`original lost frame.
`In trying to adapt RLP2 for use over channels with widely
`varying capacity, difficulty arises when a frame transmitted
`on a high-capacity channel (for example, 307 kbps) must be
`retransmitted on a low-capacity channel (for example, 9.6
`kbps). Using a frame interval of 20 ms, a full-rate frame on
`a 307 kbps channel could carry as many as 750 bytes of data.
`Such a frame could be lost during transmission, and at the
`Same time, the channel capacity might be reduced to 9.6
`kbps. In RLP2, the capacity of a 9.6 kbps full-rate 20 ms
`frame is 20 bytes. In a simple extension of the maximum
`allowable retransmission Segments, Successful retransmis
`sion of a single frame of 750 bytes of data would require
`Successful transmission of approximately 38 consecutive 9.6
`kbps full-rate RLP2 retransmit segments. Because all
`retransmit Segments would have the same Sequence number,
`the loSS of one of those 38 retransmit Segments would cause
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,507,582 B1
`
`4
`the loss of the entire retransmitted frame. The receiver could
`not negatively-acknowledge (NAK) individual retransmit
`Segments. If the Over-the-air frame error rate were 1%, the
`probability of Successful transmission of 38 consecutive
`full-rate RLP2 retransmit segments would be approximately
`68%. In this Scenario, the retransmission of the Segments
`would often fail, causing data loSS and a break in the byte
`Stream due to RLP2 resynchronization. Thus, Such a simple
`extension of RLP2 would frequently result in lost data
`whenever a high-capacity full-rate frame had to be retrans
`mitted over a low-capacity channel.
`One way to accomplish more reliable data retransmission
`would be to use a byte sequence number in the RLP header
`instead of a frame Sequence number. Then, upon the loss of
`a large, high-rate RLP frame followed closely by a decrease
`in channel capacity, the data in the lost frame could be
`divided into small, independent RLP retransmit frames. The
`receiver would not be required to receive 38 consecutive
`retransmit frames without error. The receiver could accept
`whichever retransmit frames it Successfully received and
`Simply negatively acknowledge (NAK) any lost retransmit
`ted frames. Again using an over-the-air frame error rate of
`1%, the probability of the same retransmit Segment being
`lost twice in a row would be 0.01%.
`One disadvantage of using a byte Sequence number
`instead of a frame Sequence number is the larger number of
`bits in a byte Sequence number to represent the same data.
`If a byte sequence number were used in a 9.6 kbps full-rate
`RLP2 frame, the sequence number would have to be 5 bits
`longer than the 8-bit frame sequence number. In cdma2000,
`where channel capacity may vary from 9.6 kbps to 32 times
`that capacity (approximately 307 kbps), a full-rate 307 kbps
`frame could carry as many as 750 RLP data bytes. The
`number of byte Sequence number bits necessary to track the
`same duration of 20-millisecond frames as in RLP2 is at
`least 18 bits. To make room for an 18-bit byte sequence
`number in a 9.6 kbps RLP frame, the frame would be able
`to carry two fewer data bytes, a decrease of 10%.
`The embodiments of the invention provide the benefits of
`large byte Sequence numbers while transmitting a fraction of
`the Sequence number bits in the majority of over-the-air
`frames. In one embodiment of the invention, a 20-bit byte
`Sequence number is used to track received data. The number
`of bytes which may be tracked with a sequence number is
`called the Sequence number Space. In the case of a 20-bit
`Sequence number, the size of the Sequence number Space is
`220.
`Gaining the benefits of a large Sequence number without
`adding to the average frame header size is accomplished by
`carefully Selecting portions of the Sequence number Space
`which will go unassigned to transmitted data bytes. In other
`words, Some of the Sequence number space will not be used
`to track actual transmitted bytes, and may be viewed as
`wasted. The size of the Sequence number is chosen Such that
`wastage of the Sequence number Space is permissible with
`out impacting the performance of the protocol. For example,
`if an 18-bit Sequence number is necessary to endure a
`5-second transmission loss on a 307 kbps channel, the use of
`a 20-bit sequence number allows three fourths of the
`Sequence number Space to go unused without impacting the
`maximum allowable length of transmission loSS.
`The unused portion of Sequence number space is chosen
`such that the first byte of each new transmitted data frame
`Starts at a predetermined distance, called a page size, from
`the first byte of the previous data frame. For example, if the
`first byte in frame n has a sequence number of 1000, and the
`
`Page 9 of 15
`
`

`

`S
`page size is 100, the first byte of frame n+1 will start on the
`next page with a Sequence number of 1100. If frame n only
`carries 40 bytes, numbered 1000 to 1039, then the sequence
`number space from 1040 to 1099 would go unused. The
`motivation to allow the Seeming waste of Sequence number
`Space allows a decrease in the bit size of the Sequence
`number Sent in the frame. In the example just shown, the
`sequence number could be divided by 100 before inserting
`it into the frame, and could therefore be represented by at
`least 6 fewer bits. In a preferred embodiment of the
`invention, pageSizes are powers of 2, Such as 64, to facilitate
`computer Software manipulation of Sequence numbers.
`In the previously described scenario, in which a 750 data
`bytes in a high-rate frame are lost, the preferred embodiment
`of the invention easily adapts to retransmission on high
`capacity and low capacity channels alike. In a high capacity
`channel, the data is easily retransmitted in one or two
`retransmit frames. If, however, the capacity of the channel
`has decreased, the data bytes to be retransmitted are divided
`among Several independent retransmit frames, each having
`its own Sequence number. The use of independent retransmit
`Sequence numbers has advantages over the Segmented
`retransmission specified by RLP2. If a single RLP2 retrans
`mit Segment is lost in transmission, then all the Segments
`carrying the Same Sequence number must be again retrans
`mitted in order to recover the data of the lost Segment. In
`contrast, if one or more of the independently-numbered
`retransmit frames are lost in transmission, the receiver can
`negatively-acknowledge (NAK) the individual, lost retrans
`mit frame. After receiving the second NAK, the transmitter
`may send the individual retransmit frame for a Second time.
`Again, using an over-the-air frame error rate of 1%, the
`probability of the same retransmit frame being lost twice in
`a row is 0.01%. RLP resynchronization, its associated data
`loSS, and byte Stream discontinuity, is rarely necessary.
`One disadvantage of using Sequence numbers correspond
`ing to bytes instead of frames is that more bits are generally
`needed to represent the Sequence number. This can cause a
`Slight increase in the number of independently-numbered
`retransmit frames needed to carry the data of a lost frame. In
`an exemplary embodiment of the invention, however, this
`impact is minimized by Sometimes omitting most significant
`and least Significant bits from the Sequence number.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The features, objects, and advantages of the present
`invention will become more apparent from the detailed
`description Set forth below when taken in conjunction with
`the drawings in which like reference characters identify
`correspondingly throughout and wherein:
`FIG. 1 is a diagram of Sequence number space and its use
`in several new RLP frames in accordance with an embodi
`ment of the invention.
`FIG. 2 is a diagram of Sequence number space and its use
`in several RLP retransmit frames in accordance with an
`embodiment of the invention.
`FIG. 3 is a flow chart of the steps used to transmit a data
`frame in accordance with an embodiment of the invention.
`FIG. 4 is a flow chart of the steps used to extract data from
`a received data frame in accordance with an embodiment of
`the invention.
`FIG. 5 is a diagram of a data communications System
`configured in accordance with an embodiment of the inven
`tion.
`FIG. 6 is a flow chart showing the operation of the
`processor in the transmitter of FIG. 5.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,507,582 B1
`
`6
`FIG. 7 is a flow chart showing the operation of the
`processor in the receiver of FIG. 5.
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`FIG. 1 shows how Sequence number Space is used in an
`embodiment of the invention. New data 100 to be transmit
`tedisplaced into full-rate RLP frame 140. Within RLP frame
`140 are a sequence number 150 and the data 100. New data
`102 to be transmitted is placed into full-rate RLP frame 142.
`Within RLP frame 142 are a sequence number 152 and the
`data 102.
`If new data 104 has fewer bytes than the maximum for a
`full-rate RLP frame, it is placed into non-full-rate RLP frame
`144. Within RLP frame 144 are not only a sequence number
`154 and the data 104, but-also a data length 164. As with
`RLP2, this embodiment of the invention allows the use of
`lower-rate frames within a given channel capacity, for
`example half-rate frames in a 9600 bps channel, to carry
`Smaller RLP frames.
`In an exemplary embodiment of the invention, each
`Sequence number corresponds to the first byte of the data in
`the RLP frame. The sequence number carried within an RLP
`frame is called the RLP sequence number.
`The data 100, 102, and 104 transmitted in the three RLP
`frames 140, 142, and 144, reside within sequence number
`space 110. In an exemplary embodiment of the invention,
`the Sequence numbers are byte Sequence numbers, proceed
`ing Sequentially from low values on the left to high values
`on the right. In the current embodiment, as Sequence num
`bers are either used or skipped, they increase monotonically.
`When a predetermined maximum Sequence number value is
`reached, the Sequence numbers begin again at Zero.
`As the data bytes 102 are placed into RLP frame 142, they
`are each assigned Sequential byte numbers from a block of
`Sequence numbers 126. In an exemplary embodiment, the
`first byte of block 126 is a predetermined numeric distance
`134a from the first byte of block 122 used to transmit the
`previous RLP frame. This predetermined distance is called
`a page size, and Sequence numbers within the predetermined
`distance are collectively called a page. The Sequence number
`block used to Send data always starts at the beginning of a
`page. For example, Sequence number block 122 starts at the
`beginning of page 134a, Sequence number block 126 starts
`at the beginning of page 134b, sequence number block 130
`Starts at the beginning of page 134c. One side-effect of
`always Starting a new frame at the beginning of a page is that
`a block of Sequence numbers at the end of a page, for
`example 124, 128, and 132, may not be assigned to trans
`mitted data bytes.
`In an exemplary embodiment of the invention, a short
`ened RLP Sequence number is used, which is equal to the
`byte sequence number of the first data byte in the RLP frame
`divided by the page size. The number of bits required to
`represent a shortened RLP Sequence number is fewer than
`the bits required to represent the actual byte Sequence
`number.
`In another embodiment of the invention, the most
`Significant bits are also omitted from the byte Sequence
`number when Such omission causes no ambiguity about
`which data is contained in the data portion of the RLP frame.
`For example, if a byte Sequence number of 20 bits is used,
`but fewer than 2'' bytes are outstanding (have not been
`explicitly or implicitly acknowledged), the most significant
`4 bits of the byte sequence number need not be sent in the
`RLP sequence number. These 4 most significant bits can be
`
`Page 10 of 15
`
`

`

`8
`time of transmission of the original RLP frame and the
`retransmission of its data.
`In the example shown, the Sequence number Space 228
`used to represent the bytes in the original, lost RLP frame is
`divided among several RLP retransmit frames 230.
`Sequence number Space 228 is divided into Smaller portions
`220, each having a size less than or equal to the capacity of
`full-rate frames on the current transmit channel. The data
`200 corresponding to each of the Smaller Sequence number
`space portions 220 is placed into an RLP retransmit frame
`230.
`Each RLP retransmit segment has an RLP sequence
`number 240 corresponding to the first byte of its respective
`Sequence number Space 220. For example, Sequence number
`240 has a value representative of the first value in Sequence
`number space 220. The RLP sequence number 240 in each
`retransmit frame 230 may optionally be shortened in the
`Same ways as discussed for RLP Sequence numbers as long
`as doing So causes no Sequence number ambiguity.
`Each RLP retransmit frame may optionally have a data
`length 250. The data length 250 carried by each RLP
`retransmit frame indicates the number of data bytes 200
`within the frame. For example, data length 250 is equal to
`the number of data bytes 200 in retransmit frame 230. If
`the length of data is indicated in other parts of the retransmit
`frame 230, for example in a type field not shown in the
`figure, the data length field 250 may be omitted.
`Formation of RLP retransmit frames continues until the
`last portion of data 200, is placed into an RLP retransmit
`frame 230. The last in a series of RLP retransmit frames
`often contains fewer than the maximum number of data
`bytes 200, and so typically contains a data length 250.
`In the preferred embodiment of the invention, RLP
`Sequence numbers for the most common transmit frames are
`Shortened by omitting the least Significant bits and most
`Significant bits. In an exemplary embodiment of the
`invention, the byte Sequence number has 20 bits, a page size
`of 64 bytes is used, and the number of outstanding RLP
`transmit frames rarely exceeds 256.
`
`15
`
`25
`
`35
`
`40
`
`US 6,507,582 B1
`
`7
`safely omitted from the RLP sequence number without
`causing ambiguity in the Sequence numbers of the bytes
`contained in the frame.
`Though the shortening of the Sequence number is por
`trayed herein as omitting a number of most significant bits
`from the Sequence number, one skilled in the art will
`appreciate that the same result may be obtained by perform
`ing a modulo function on the Sequence number without
`departing from the current invention.
`If, however, more than 2" bytes are outstanding, it may
`be that more than one of the Outstanding data bytes have the
`Same shortened RLP Sequence number. In an exemplary
`embodiment of the invention, retransmit frames carrying
`such data bytes will include the entire 20-bit sequence
`number.
`When an RLP frame is negatively acknowledged
`(NAK'd) and must be retransmitted, the data is inserted into
`RLP retransmit frames and retransmitted. If the channel
`capacity during retransmission is Sufficient, then the retrans
`mit frame is the same size as the original, lost RLP frame.
`In the case where the retransmit frame and the original RLP
`frame are the same size, the retransmit frame may use the
`Same shortened RLP Sequence number as the original, as
`long as doing So causes no Sequence number ambiguity.
`If an original transmit frame carries more data than will fit
`into a single retransmit frame, as is possible when channel
`capacity decreases, then the data from the original transmit
`frame is divided among Several Smaller retransmit frames.
`Each retransmit frame contains its own RLP Sequence
`number, which may or may not be shortened in one of the
`ways previously discussed. If a retransmit frame is lost
`during transmission, that individual retransmit frame may be
`NAK’d, and Subsequently retransmitted. In the rare event
`that channel capacity decreases before a retransmit frame is
`NAK'd, the data in that retransmit frame may be further
`divided among even Smaller, independent retransmit frames
`before their Second retransmission.
`This procedure differs from RLP2, in which retransmit
`Segments corresponding to a single lost frame all carry the
`Same RLP Sequence number. In order to recover the data in
`a Single, lost retransmit Segment, all retransmit Segments
`carrying the Sequence number of the lost frame must again
`be retransmitted.
`
`TABLE 1.
`
`Example RLP Frame Headers
`
`RLP Frame Header Fields
`
`Type Bit O-
`bits
`Bit 1
`
`Bit 4
`Bit 2 Bit 3 Bit 7
`
`Byte 1
`
`Byte 2 Byte 3 Frame Type Descriptions
`
`11
`1O
`O1
`OO
`OO
`OO
`OO
`OO
`OO
`
`Data
`Data
`Len
`
`8 bit seq #
`8 bit seq #
`8 bit seq #
`11
`14 bit seq #
`1O
`14 bit seq #
`O1
`14 bit seq #
`Len
`20 bit seq #
`OO
`1.
`1.
`Len
`20 bit seq #
`OO
`1.
`O
`OO
`O
`More formats for NAKs, Status, SYNC,
`ACK, SYNC/ACK, Idle, End of Frame
`
`Data
`Data
`Len
`Length
`
`Data
`
`1. New: 8-bit RLP sequence number
`2. Retransmit: 8-bit RLP sequence number
`3. New: 8-bit RLP sequence number, 8-bit length
`4. 14-bit RLP sequence number, No length
`5. 14-bit RLP sequence number, 8-bit length
`6. 14-bit RLP sequence number 16-bit length
`7. Retransmit: Move to next page boundary.
`8. Retransmit: Don't move to next page boundary
`9. Extended control/sequence
`
`FIG. 2. Shows the use of byte Sequence number Space and
`RLP sequence numbers when the data in a lost RLP frame
`must be retransmitted in several Smaller RLP retransmit
`frames, and in accordance with an exemplary embodiment
`of the invention. The division of retransmit bytes may be
`necessary when channel capacity is reduced between the
`
`65
`
`Table 1 shows the fields of RLP frame headers used in
`accordance with the preferred embodiment of the invention.
`The contents of the frame headers may be placed at the
`beginning, the end, or dispersed deterministically through
`out the RLP frame. In the preferred embodiment of the
`invention, the RLP frame header appears at the beginning of
`
`Page 11 of 15
`
`

`

`US 6,507,582 B1
`
`5
`
`15
`
`35
`
`25
`
`9
`each RLP frame. Dispersion of the contents of the header
`throughout the frame may be desirable if a non-uniform
`probability of bit error exists throughout the RLP frame
`when rec