Automatic retransmit request protocol for channels with time-varying capacity

A method for transmitting an IP packet segmented into protocol units to a receiver over a data link in frames whose data-carrying capacity may vary from frame to frame, the method comprising, when data-carrying capacity of L bytes is made available in a frame, the IP packet to be transmitted is in a transmission queue, and any protocol units to be retransmitted are in a retransmission queue, repeating the following until L is zero:

• (P) determining whether the retransmission queue is empty (block 402), and
• if the retransmission queue is empty, then
• (Q) determining whether the transmission queue is empty (block 404), and if the transmission queue is not empty,
• dequeuing L bytes or the remaining bytes of the IP packet from the transmission queue, whichever is the lesser, and decrementing L by the number of bytes dequeued (block 406),
• calculating a next sequence number (block 408), and
• forming a protocol unit having the next sequence number in a header and the dequeued data in a payload, the dequeued data implicitly divided into sequence number blocks consecutively numbered starting at the present sequence number, and adding the protocol unit to the frame to be transmitted, each sequence number block having a fixed length, except if the number of bytes dequeued is not an integer multiple of the fixed length, then the last block, or the only block if the number of bytes dequeued is less than the fixed length, is shorter than the fixed length (block 410),
• but if the retransmission queue is not empty,
• (R) determining whether the length of the sequence number block at the head of the retransmission queue is greater than L (blocks 414, 416), and
• if the length of the sequence number block at the head of the retransmission queue is greater than L, proceeding to the step labeled Q above,
• but, if the length of the sequence number block at the head of the retransmission queue is not greater than L, determining whether a new protocol unit is partially formed (block 418), and
• if no new protocol unit is partially formed, then
• dequeuing the sequence number block at the head of the retransmission queue, decrementing L by the number bytes dequeued, starting the formation of a new protocol unit having the present sequence number in a header and the dequeued sequence number block as a payload (420), and
• (S) determining whether the retransmission queue is empty (block 422), and
• if the retransmission queue is empty,
• (T) completing the new protocol unit and adding it to the frame to be transmitted (block 424), and
• proceeding to the step labeled P above, and
• if the retransmission queue is not empty,
• proceeding to the step labeled R above,
• but, if a new protocol unit is partially formed, then
• if (i) the sequence number block at the head of the retransmission queue has a sequence number that is consecutive with the sequence number block at the tail of the partially formed protocol unit and (ii) the sequence number block at the tail block of the partially formed protocol unit is the fixed length (block 426), then
• dequeuing the sequence number block at the head of the retransmission queue, appending the dequeued sequence number block to the tail of the partially formed new protocol unit, and decrementing L by the number bytes dequeued (block 428), and
• proceeding to the step labeled S above,
• but otherwise, proceeding to the step labeled T above.

A system for transmitting data over a data link, comprising:

• (a) a receiver including a microprocessor, a modem, a radio and an antenna, capable of receiving frames transmitted over the data link, the data-carrying capacity of the frames varying from time to time;
• and
• (b) a transmitter including a microprocessor, a modem, a radio and an antenna, operable to transmit frames to the receiver over the data link, the frames including one or more protocol units, each discrete protocol unit having a data payload portion that is implicitly divided into sequentially numbered blocks each having a fixed length, except if the number of bytes carried in the payload portion is not an integer multiple of the fixed length, then the last block, or the only block if the number of bytes in the payload portion is less than the fixed length, is shorter than the fixed length, and a header portion including the sequence number of the first block in the data payload portion, wherein the sequence numbers are chosen so that all blocks transmitted over the data link can be identified by sequence number,
• whereby, if it is determined that the receiver did not receive an uncorrupted copy of a previously transmitted protocol unit, then the transmitter retransmits the previously transmitted protocol unit in the next available frame to be transmitted if there is sufficient data-carrying capacity in the next available frame, but otherwise the transmitter
• forms a new protocol unit from the blocks of the previously transmitted protocol unit starting with the first block of the previously transmitted protocol unit and proceeds sequentially through the previously transmitted protocol unit adding blocks to the newly formed protocol unit until the data-carrying capacity of the next available frame is used,
• transmits the newly formed protocol unit over the data link, and
• forms and transmits further new protocol units whenever data-carrying capacity in a frame is available until all blocks of the previously transmitted protocol unit have been successfully retransmitted, each newly formed protocol unit having a header including the sequence number of the first block in its data payload portion.