Title of Invention

METHOD OF TRANSMITTING A DATA PACKET WITH SHORTENED SEQUENCE NUMBERS IN HEADERS OF ARQ PROTOCOLS

Abstract The invention relates to the field of link protocols that are used in communication systems. Link protocols perform reliable data transfer by assigning sequence numbers to each data unit being transmitted. The transmitter retransmits the data units when it identifies that the receiver had not received the data units,which the transmitter had sent earlier, based on sequence numbers. The invention relates to a method of using value adaptive sequence numbers in which the transmitter and the receiver involved in a ARQ mechanism shortens the number of bits used to denote sequence number, based on the number of leading zero bits in the sequence number allotted to the data unit. The transmitter would add length control bits to indicate the receiver about the dynamic sequence length filled in the packet header. The receiver extracts the sequence number using length control bits, and forms the complete sequence number by adding zeros to make sequence number size same as the complete sequence length. In another method, the length control bits also indicate a sequence offset, which can be used to extract complete sequence number.
Full Text FIELD OF THE INVENTION
The present invention, in general, relates to the field of communications. It is related to Link Protocols used in Communication Systems, which performs reliable data transfer by assigning sequence numbers to each data unit transmitted. The sequence numbers are used to identify missed data units and thereby enable retransmission of those data units. The invention is related to a method for reducing length of sequence number specified in the header of ARQ protocols. The objective of the invention is to remove the leading, octet-aligned zero bits in the sequence number for each data unit transmitted. More particularly, the present invention relates to a method for value based shortening . of sequence numbers in headers of ARQ protocols, used in communication systems.
DESCRIPTION OF RELATED ART
Communication systems employ ARQ methods in link protocols to provide reliable data transfer for higher layer protocols or applications. Link Protocols are designed for providing retransmission and duplicate detection by identifying each data unit with a sequence number. Sequence numbers are used by the transmitter in each data unit transmitted, and the receiver identifies missing data units when sequence numbers in received data units are not contiguous. The transmitter retransmits the data units when it identifies that the receiver had not received the data units which the transmitter had sent earlier.
Octet stream and Packet stream are the two common modes of data transfer known in the related art. In Octet Stream, each octet is assigned a sequence number and sequence number of first octet of the payload being transmitted, is filled as the sequence number in the header of the specific RLP packet. In Packet Stream, group of octets sent together, also referred as a packet, are allotted a sequence number and the specific sequence number is incremented for each packet sent by the transmitter.
A sequence space identifies the range of sequence numbers that would be used. Modulo operations are used in related art, for resetting the sequence number when maximum value of sequence number is reached with N bits (that is when sequence number reaches ((2AN)-1)). The term wrap-around is used to denote one complete usage of the sequence space. A sequence space for sequence number with N bits is 0 till ((2AN)-1). One skilled in the prior art would note that more the bits allotted for denoting the sequence length, less the number of cycles for sequence numbers, when sending data in a given time period.
Some ARQ mechanisms have a 32-bit sequence number, widely used Transmission Control Protocol (TCP) is one such example. In some communication systems like Radio Link Protocol, also referred as RLP, used in CDMA based systems, the sequence number length is made fixed or variable based on the requirements of the user applications. Though the sequence length is made variable depending on the application characteristics, the sequence number in each packet sent for the specific link or instance is kept constant.
contiguous zero bits in the most significant part of the sequence number. SUMMARY OF THE INVENTION
The invention relates to the field of link protocols that are used in communication systems. Link protocols perform reliable data transfer by assigning sequence numbers to each data unit being transmitted. The sequence number is added in the header of each transmitted data unit. A receiver identifies missed data units when sequence numbers in received data units are not contiguous. The transmitter retransmits the data units when it identifies that the transmitted data units were not received by the intended receiver. The transmitter may identify data units to be retransmitted based on a Negative Acknowledgment (NAK) received from the receiver, or based on failure of reception of Acknowledgment (ACK) from the receiver for transmitted data units.
The objective of the invention is to reduce the length of the sequence number for reliable data transfer in a communication system. The length of the sequence number can be reduced based on the number of leading zero bits in the sequence number allotted to the data unit. The transmitter will add Length Control (LC) bits to indicate the receiver about the dynamic sequence length filled in the packet header. The receiver extracts the sequence number using LC bits, and forms the complete sequence number by adding zeros to make sequence number size same as the complete sequence length. Alternatively, the LC bits are also used to indicate a sequence offset, which can be used to extract complete sequence number using a mutually understood method by the transmitter and the receiver.
Accordingly the invention explains a method for value based shortening of sequence numbers in headers of ARQ protocols, wherein the length of the sequence number is reduced based on the number of leading zero bits in the sequence number allotted to the data unit.
The length of the sequence number is reduced based on the number of leading zero bits in the sequence number allotted to the data unit. The transmitter adds Length Control (LC) bits to indicate the receiver about the dynamic sequence length filled in packet header. The receiver extracts the sequence number using LC bits, and forms the complete sequence number by adding zeros to make sequence number size same as the complete sequence length. The LC bits are used to indicate a sequence offset, which is used to extract complete sequence number.
Other objects, features, and advantages of the present invention will become more apparent from the ensuing detailed description of the invention, taken in conjunction with the accompanying drawings, which depicts the flowchart of the various stages of the methods involved.
BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
Figure 1 depicts Algorithm for procedures performed in ARQ Transmitter in prior art.
Figure 2 depicts Algorithm for procedures performed in ARQ Receiver in prior art.
Figure 3 depicts fields in header of ARQ protocol.
Figure 4 depicts Algorithm for procedures performed in ARQ Transmitter in present invention.
Figure 5 depicts Algorithm for procedures performed in ARQ Receiver in present invention.
Figure 6 depicts an example sequence mapping table, when length control bits are taken from sequence space.
Figure 7 depicts an example sequence mapping table, when length control bits are not taken from sequence space.
DETAILED DESCRIPTION OF THE INVENTION
The preferred embodiments of the present invention will now be explained with reference to the accompanying drawings. However, it should be understood that the disclosed embodiments are merely exemplary of the invention, which may be embodied in various forms. Therefore the details disclosed herein are not to be interpreted as limiting but merely as the basis for the claims and as a basis for teaching one skilled in the art how to make or use the invention.
The protocol providing reliable data transfer, adds a sequence number in the header of each transmitted data unit. The receiver identifies missed data units when sequence numbers in received data units are not continuous. The transmitter retransmits the data units when it identifies that the transmitted data units were not received by the intended receiver. The transmitter may identify data units to be retransmitted based on a NAK received from the receiver or based on failure of reception of ACK from the receiver for transmitted data units.
The objective of the invention is to shorten the number of bits used for denoting sequence number for reliable data transfer in a communication system, by removing octet aligned, contiguous zero bits in the most significant part of the sequence number. The transmitter and the receiver operate over the entire sequence space of N bits for modulo operations as in related art, but the sequence number in the header of transmitted data unit is shortened by removing leading, octet aligned zero bits. The number of removed zero bits are intended to be octet-aligned so that more data octets can be sent instead of using the bits for header.
Zero bits removal
As a primary embodiment of the invention, the sequence number specified in each transmitted data unit does not include contiguous octet aligned zero bits in the most significant or leading bits, when number of such zero bits is non zero multiple of eight. Such a sequence number is hereby referred as shortened sequence number. In the receiver, the insignificant zero bits are implicitly understood and used to perform receiver procedures. In the transmitter, the shortened sequence number can be of different lengths based on the number of contiguous zero bits excluded.
In an embodiment of the invention, a length control field is added by the transmitter in the header of each data unit transmitted. The length of said length control field is L bits in all transmitted data units. The length control field is preferably added just before the sequence number in the header of each data unit. It can be noted that the length control field can be added anywhere in the data unit, provided the receiver can identify the location of the length control field in the received data unit. The length control field is used to denote different sequence length values for the possible sequence numbers. The value specified in the length control field is referred as LC, and is decided based on the sequence number of the transmitted data unit.
The length control field of L bits can be taken from the sequence space of N bits or from outside the sequence space of N bits. The length control field can be taken from N bits sequence space, if taking L bits outside sequence length leads to octet alignment discrepancy. If L bits are available outside sequence length of N bits in the header, then the L bits can be used as length control field without any impact to other procedures.
When length control field of L bits are taken from sequence length of prior art, the number of bits available for denoting sequence length gets reduced by L bits. As described in figure 3,
Sequence length in prior art, N >= Length control field, L + Shortened sequence length S.
For example, when L is 2 bits and N is 32 bits, S can be one of 6,14,22,30 bits as shown in figure 6.
When length control field of L bits is taken from outside sequence length of prior art, the number of bits, S used to denote shortened sequence number, can be one of multiple sequence length values differing by 8, till N.
Sequence length in prior art, N >= Shortened sequence length S.
For example, when L is 2 bits and N is 32 bits, S can be one of 8,16,24,32 bits
as shown in figure 7.
As the primary embodiment of the invention, the value of the length control field is used to denote the number of bits in the shortened sequence number based on a mapping expression. One such mapping expression when length control field is taken from sequence length in prior art, is S = ((LC + 1) * 8) - L
A mapping expression when length control field is taken from outside sequence length, is
S = (LC + 1) * 8
Where S denotes length of shortened sequence number, LC denotes value in the length control field, and L denotes number of bits in length control field.
It can be noted that the number of possible values for length control field LC, and the number of bits used to denote length control field, L, are derived from number of possible sequence lengths with a difference of 8 bits, till the sequence length becomes N bits. For example, when sequence space (N) is 32 bits, L can be chosen as 2 bits since there are only four (2A2) non zero multiples of 8 - 8,16,24,32. Similarly, when sequence space (N) is 64 bits, L can be chosen as 3 bits since there are eight (2A3) different non zero multiples of 8 - 8,16,24,32,40,48,56,64.
As an embodiment of the invention, the values for L, LC and S are chosen based on the sequence space N. L is determined based on the number of sequence length options 0, for a given sequence space of N bits. It can be noted that each of the said sequence length option is offset by 8.
L >= Log2(0)
where L is an integer and O = Largest integer greater than or equal to N/8. LC can take values from the complete set or subset, LC 6 { 0,1,..(2AL) }, and S is calculated based on values of LC and L.
The transmitter identifies the value to be filled for length control field LC, by fitting
the sequence number in one of the possible shortened sub sequence spaces, as shown in figure 4. The sequence number is shortened appropriately by removing leading zero bits, and the entire payload is transmitted after adding length control and sequence number fields.
In the receiver, the value in the length control field is used to identify the number of bits to be extracted as the shortened sequence number based on the mapping expression for LC and S, used by the transmitter. Figure 6 and 7 provides an example set of values for LC, S as a mapping table. The receiver extracts the shortened sequence number of S bits, and forms the complete sequence number by adding zeros if necessary, in the most significant part of the sequence number to make the sequence length as N bits. Further receiver operations are performed on the complete sequence number, as known in prior art. The procedures followed at the receiver are shown in figure 5.
It can be noted that when transmitted sequence number is of varying length and less than or equal to N, the average number of bits used to denote sequence number gets reduced. The metric, average number of bits used to denote the sequence number in one wrap-around can be used for measuring the performance of sequence length shortening techniques. With a fixed size sequence number representation in each transmitted data unit, the average number of sequence number bits used in packet based transmission will be N bits within one wrap-around. In the present invention, the average number of sequence number bits used in packet based transmission scheme within one wrap-around, will be


where
If L bits are taken from the sequence space of N bits or
If L bits are taken outside sequence space of N bits,

It can be noted that the present invention reduces the average number of bits used for denoting sequence number over a period of time i.e., Average SEQ bits is normally Zero bits removal with implicit offset
As another embodiment of the invention, the length control field implicitly denotes a sequence number offset of 2AS(LC-1) when LC >= 0, and 0 otherwise.
It can be noted that in such a method, the shortened sequence number gets reset to zero in every sub sequence space. In a packet stream transmission, the sequence number spans from 0 till 2AS(1) for transmitting S(1) data units, and then 0 till 2AS(2) for S(1)+S(2) data units.
For example, if N is taken to be 32 bits, giving S as {8,16,24,32}, where L=2 bits are taken outside sequence space of N bits. 2A8 packets can be transmitted with 8 bit header, 2A16 packets can be transmitted with 16 bit header, 2A24 packets can be transmitted with 24 bit header, and 2A32 packets can be transmitted with 32 bit header. The receiver will add an implicit offset of S(LC-1) to every received packet, i.e, when LC is set as '01' to identify S as 16, the receiver will add 2A8 to the sequence number of each received packet with 16 bit header and then add zeros to make the length as N bits for performing receiver procedures.
In this method, the average number of bits within one wrap-around gets reduced further than the method of SS1 & SS3.
where
If L bits are taken from the sequence space of N bits or
If L bits are taken outside sequence space of N bits,

It can be noted that this method reduces the average number of bits AVG2 further compared to average AVG1. The number of bits for sequence number and corresponding length control field values can be referred from figure 6 and figure 7 where SS2 and SS4 denote the shortened sequence numbers when L bits are taken from inside or outside sequence space of N bits, respectively.
Effects of shortening sequence length-
The reduction in average number of bits denoting sequence number, improves throughput experienced by the user applications, since more number of bits can be used to accommodate data of higher layer, when the header length is shortened. Sequence space of N bits may get shortened by L bits if the L bits are taken from the sequence number. In these cases, there would be 2AL more wrap-around compared to a single wrap-around when sequence space was of size N bits. Change in effective sequence length in such a scenario, may impact the value of abort timer and transmission data rate. It can be noted that either the value of abort timer or transmission data rate could be modified to suit the shortened sequence space, depending on required QoS characteristics of the user application.
The increase in throughput will be more pronounced in packet stream data transmission, since successive sequence numbers are transmitted for data units. In case of octet stream transmission, the sub sequence space may be completed with transmission of less number of data units, since filled sequence number is increased based on number of octets transmitted in previous data unit. The increase in throughput is better in case of simultaneous data transfer with multiple sequence spaces, like in multi link or multi user data transfer, where more number of sequence number bits will be shortened.
ADVANTAGES
The application throughput above the ARQ protocol would be better, since the header of the ARQ protocol is shortened during transmission.
Although, the present invention has been fully described in connection with the preferred embodiments thereof with reference to the accompanying drawings, it is to be noted that various changes and modifications are possible and are apparent to those skilled in the art. Such changes and modifications are to be understood as included within the scope of the present invention as defined by the appended claims unless they depart there from.
GLOSSARY OF TERMS AND DEFINITIONS THEREOF
Abort Timer- Time for when the receiver waits to retrieve the missed data units from the transmitter.
ACK- An acknowledgement message sent by the receiver to the transmitter on successful reception of each reliable data unit.
ARQ- Automatic Repeat Request - error control method for data transfer in which the receiver detects transmission error s in packets transmitted and automatically requests a retransmission from the transmitter. Wrap-around- One complete usage cycle of sequence space, when assigning and incrementing sequence numbers for reliable data transfer. NAK- A message sent by the receiver to the transmitter on failure of reception of some reliable data units. Starting sequence number of the data unit and number of missed data units may be informed in a NAK.
QoS- Quality of Service - application characteristics serviced by the protocols. Reliable- A delivery type in which the transmitter ensures that the packet is received by the receiver, by retrying transmission multiple rounds. Retransmission- The functionality of transmitter transmitting the already transmitted fragment again, when the receiver does not seem to have received the fragment.
RLP- Radio Link Protocol - protocol used in communication systems for defining rules and properties to ensure reliable delivery of data packets, by providing retransmission and duplicate detection. Fragmentation and reassembly of packets may also be performed by the Radio Link Protocol.


We claim:
1. A method for value based shortening of sequence numbers in headers of ARQ protocols, wherein the length of the sequence number is reduced based on the number of leading zero bits in the sequence number allotted to the data unit.
2. A method as claimed in claim 1 wherein a transmitter adds Length Control (LC) bits to indicate the receiver about the dynamic sequence length filled in packet header.
3. A method as claimed in claim 1 wherein a receiver extracts the sequence number using LC bits, and forms the complete sequence number by adding zeros to make sequence number size same as the complete sequence length.
4. A method as claimed in claim 1 wherein, the LC bits are used to indicate a sequence offset, which is used to extract complete sequence number.
5. A method for value based shortening of sequence numbers in headers of ARQ protocols, used in communication systems substantially described particularly with reference to the accompanying drawings.

Documents:

1450-CHE-2006 AMENDED PAGES OF SPECIFICATION 07-06-2013.pdf

1450-CHE-2006 AMENDED CLAIMS 05-08-2013.pdf

1450-CHE-2006 AMENDED CLAIMS 07-06-2013.pdf

1450-CHE-2006 EXAMINATION REPORT REPLY RECEIVED 07-06-2013.pdf

1450-CHE-2006 EXAMINATION REPORT REPLY RECEIVED 05-08-2013.pdf

1450-CHE-2006 FORM-1 07-06-2013.pdf

1450-CHE-2006 FORM-13 07-06-2013.pdf

1450-CHE-2006 OTHER PATENT DOCUMENT 07-06-2013.pdf

1450-CHE-2006 POWER OF ATTORNEY 05-08-2013.pdf

1450-CHE-2006 POWER OF ATTORNEY 07-06-2013.pdf

1450-CHE-2006 CORRESPONDENCE OTHERS 20-09-2013.pdf

1450-CHE-2006 POWER OF ATTORNEY 20-09-2013.pdf

1450-CHE-2006 ABSTRACT.pdf

1450-CHE-2006 CLAIMS.pdf

1450-CHE-2006 CORRESPONDENCE OTHERS.pdf

1450-CHE-2006 DESCRIPTION (COMPLETE).pdf

1450-CHE-2006 DRAWINGS.pdf

1450-CHE-2006 FORM 1.pdf

1450-CHE-2006 FORM 18.pdf

1450-CHE-2006 FORM 5.pdf

1450-che-2006-correspondnece-others.pdf

1450-che-2006-description(provisional).pdf

1450-che-2006-drawings.pdf

1450-che-2006-form 1.pdf

1450-che-2006-form 26.pdf


Patent Number 257366
Indian Patent Application Number 1450/CHE/2006
PG Journal Number 40/2013
Publication Date 04-Oct-2013
Grant Date 27-Sep-2013
Date of Filing 17-Aug-2006
Name of Patentee SAMSUNG INDIA SOFTWARE OPERATIONS PRIVATE LIMITED
Applicant Address Bagmane Lakeview, Block 'B', No. 66/1, Bagmane Tech Park, C V Raman Nagar, Byrasandra, Bangalore-560093.
Inventors:
# Inventor's Name Inventor's Address
1 SUNDAR RAJAN K Samsung India Software Operations Pvt. Ltd., Bagmane Lakeview, Block 'B', No. 66/1, Bagmane Tech Park, C V Raman Nagar, Byrasandra, Bangalore-560093.
2 VADLAPUDI TIRUMALA SREE HARI VARA PRASAD Samsung India Software Operations Pvt. Ltd., Bagmane Lakeview, Block 'B', No. 66/1, Bagmane Tech Park, C V Raman Nagar, Byrasandra, Bangalore-560093.
PCT International Classification Number H04L 12/00
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 NA