Method and apparatus for transmitting data over a network within a specified time limit

• US 20030012212A1
• Filed: 03/14/2001
• Published: 01/16/2003
• Est. Priority Date: 03/14/2001
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Earnshaw, Mark, Huang, Wei, Cheong, Yoon Chae
• Granted Patent: US 7,058,085 B2
• Time in Patent Office: Days
• US Class Current: 370/428
• CPC Class Codes: H04L 1/1621 Group acknowledgement, i.e. the acknowledgement message defining a range of identifiers, e.g. of sequence numbers
• CPC Class Codes: H04L 1/1685 the supervisory signal being transmitted in response to a specific request, e.g. to a polling signal
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

A radio link protocol for a communications system ensures that delivery of Internet protocol data packets occurs within a set delay bound for the packets, in order to satisfy specified quality of service levels. Data packets arriving at a transmitter are subdivided into data blocks. As each block is transmitted, the transmitter starts an associated acknowledgement timer. The timer is turned off, before it expires, if the transmitter timely receives from a receiver a message informing the transmitter that the associated block was successfully received. If such message is not received, the timer expires and the transmitter sends an acknowledgement request signal to the receiver and starts an associated panic timer. The panic timer is turned off, before it expires, if the transmitter subsequently timely receives a message that the associated block was successfully received. If such message not received, the panic timer expires and the transmitter sends one of more copies of the corresponding block to the receiver before occurrence of the delay bound. If the transmitter receives a negative acknowledgement message from the receiver, that a block is missing or corrupted, the transmitter retransmits a copy of the block to the receiver. To reduce messaging traffic, the transmitter cancels acknowledgement and panic timers based upon information contained in negative acknowledgement messages, and the receiver can periodically send acknowledgement messages to inform the transmitter of successfully received blocks.

Claims

1. An apparatus, comprising:

means for transmitting data blocks to a receiver;

means for receiving messages identifying successfully received data blocks; and

means for retransmitting a data block to the receiver in response to absence of receipt, within a predetermined time referenced to the time of transmission of the data block, of a message identifying the data block as having been successfully received.

2. Apparatus as in claim 1, wherein the retransmitted data block is part of a data packet and said retransmitting means retransmits the data block before a delay bound set for the data packet

3. Apparatus as in claim 1, wherein said means for retransmitting includes:

means responsive to absence of receipt by the end of a first interval of time, of a message that a data block has been successfully received, for transmitting to the receiver a request for a message identifying successfully received data blocks, and

means responsive to continued absence of receipt by the end of a second and later interval of time, of a message that the data block has been successfully received, for retransmitting the data block to the receiver.

4. Apparatus as in claim 3, wherein said first and second intervals of time are referenced to the time of transmission of the data block.

5. Apparatus as in claim 3, wherein:

said first interval of time is referenced to the time of transmission to the receiver of the data block, and

said second interval of time is referenced to the time of transmission to the receiver of the request for a message identifying successfully received data blocks.

6. Apparatus as in claim 5, wherein the data block is part of a data packet and said second interval of time ends before a delay bound set for the data packet

7. Apparatus as in claim 6, wherein:

said first interval of time expires at a time A+D−

T₁, where A is the arrival time at said means for transmitting of the data packet, D is the delay bound time set for the data packet and T₁ is a threshold value, and

said second interval of time expires at a time A+D−

T₂, where T₂ is a threshold value lower than T₁

8. Apparatus as in claim 1, wherein said transmitting means transmits to the receiver sequentially identified data blocks and said retransmitting means is inoperative to retransmit a data block M upon said receiving means receiving a message that either:

data block N has been successfully received, and M≦

N, or

data block P has been successfully received, and M≦

P+1.

9. Apparatus as in claim 1, further including:

means for receiving negative acknowledgement messages from the receiver identifying data blocks that have not been successfully received, the negative acknowledgement messages including an identification of successfully received data blocks,

said means for retransmitting being responsive to receipt of a negative acknowledgement message that a data block has not been successfully received to retransmit the data block to the receiver.

10. A transmitter, comprising:

a transmitter circuit for transmitting data blocks to a receiver and for receiving from the receiver messages identifying successfully received data blocks; and

a timer circuit, said transmitter circuit retransmitting a data block to the receiver in response to absence of receipt from the receiver, by a time determined by said timer circuit and referenced to the time of transmission of the data block, of a message identifying the data block as having been successfully received.

11. A transmitter as in claim 10, wherein said transmitter circuit is:

responsive to absence of receipt by the end of a first interval of time determined by said timer circuit, of a message from the receiver that a data block has been successfully received, to transmit to the receiver a request for a message identifying successfully received data blocks, and is responsive to continued absence of receipt by the end of a second and later interval of time determined by said timer circuit, of a message from the receiver that the data block has been successfully received, to retransmit the data block to the receiver

12. A transmitter as in claim 11, wherein said first and second intervals of time are referenced to the time of transmission to the receiver of the data block.

13. A transmitter as in claim 11, wherein:

said first interval of time is referenced to the time of transmission to the receiver of the data block, and

said second interval of time is referenced to the time of transmission to the receiver of the request for a message identifying successfully received data blocks.

14. A transmitter as in claim 13,wherein the data block is part of a data packet and said second interval of time ends before a delay bound set for the data packet.

15. A transmitter as in claim 14, wherein:

said first interval of time expires at a time A+D−

T₁, where A is the arrival time of the data packet at said transmitter control circuit, D is the delay bound time set for the data packet and T₁ is a threshold value, and

said second interval of time expires at a time A+D−

T₂, where T₂ is a threshold value lower than T₁.

16. A transmitter as in claim 10, wherein said transmitter circuit transmits sequentially identified data blocks, and is inoperative to retransmit a data block M upon receiving from the receiver a message that either:

data block N has been successfully received, and M≦

N, or data block P has been successfully received, and M≦

P+1.

17. A transmitter as in claim 10, wherein said transmitter circuit is responsive to receipt from the receiver of negative acknowledgement messages identifying data blocks that have not been successfully received, to retransmit the identified data blocks to the receiver, the negative acknowledgement messages including identifications of successfully received data blocks.

18. A transmitter as in claim 10, further comprising:

a data block storage buffer for storing copies of transmitted data blocks, said transmitter circuit obtaining, from said data block storage buffer, data blocks for retransmission.

19. A transmitter as in claim 10, wherein said transmitter circuit, upon transmission of each data block to the receiver, controls said timer circuit to start an acknowledgement timer associated with the transmitted data block.

20. A transmitter as in claim 19, wherein said transmitter circuit, in response to receipt before expiry of an acknowledgement timer of a message from the receiver that the associated data block has been successfully received, controls said timer circuit to cancel the acknowledgement timer.

21. A transmitter as in claim 20, wherein said transmitter circuit, in the absence of receipt before expiry of an acknowledgement timer of a message from the receiver that the associated data block has been successfully received, transmits to the receiver a request for a message identifying successfully received data blocks and controls said timer circuit to start an associated panic timer.

22. A transmitter as in claim 21, wherein said transmitter circuit, in response to receipt before expiry of a panic timer of a message from the receiver that the associated data block has been successfully received, controls said timer circuit to cancel the panic timer.

23. A transmitter as in claim 22, wherein said transmitter circuit, in the absence of receipt before expiry of a panic timer of a message from the receiver that the associated data block has been successfully received, retransmits the associated data block to the receiver.

25. Apparatus as in claim 24, wherein said transmitter includes:

a transmitter control circuit; and

a data block storage buffer for storing copies of transmitted data blocks, said transmitter control circuit obtaining from said data block storage buffer data blocks for retransmission to said receiver.

26. Apparatus as in claim 24, wherein said transmitter includes:

a transmitter control circuit; and

a timer circuit, said transmitter control circuit being responsive to absence of receipt by the end of a first interval of time determined by said timer circuit, of a message from said receiver that a data block has been successfully received, to transmit to the receiver a request for a message identifying successfully received data blocks, and being responsive to continued absence of receipt by the end of a second and later interval of time determined by said timer circuit, of a message from said receiver that the data block has been successfully received, to retransmit the data block to said receiver.

27. Apparatus as in claim 26, wherein said first and second time intervals are referenced to the time of transmission by said transmitter to said receiver of the data block.

28. Apparatus as in claim 26, wherein said first time interval is referenced to the time of transmission by said transmitter to said receiver of the data block, and said second time interval is referenced to the time of transmission by said transmitter to said receiver of the request for the message identifying successfully received data blocks.

29. Apparatus as in claim 26, wherein the data block is part of a data packet and said second interval of time ends before a delay bound set for the data packet.

30. Apparatus as in claim 29, wherein:

said first interval of time expires at a time A+D−

T₁, where A is the arrival time of the data packet at said transmitter, D is the delay bound time set for the data packet and T₁ is a threshold value, and

said second interval of time expires at a time A+D−

T₂, where T₂ is a threshold value lower than T₁.

31. Apparatus as in claim 24, wherein said transmitter transmits to said receiver sequentially identified data blocks, and is inoperative to retransmit a data block M upon receiving from said receiver a message that either:

data block N has been successfully received, and M≦

N, or

data block P has been successfully received, and M≦

P+1.

32. Apparatus as in claim 24, wherein said transmitter is responsive to receipt from said receiver of negative acknowledgement messages identifying data blocks that have not been successfully received, to retransmit the data blocks to said receiver, the negative acknowledgement messages including identifications of successfully received data blocks.

33. Apparatus as in claim 24, wherein said transmitter includes:

a timer circuit,

said transmitter, in response to transmission of each data block to said receiver, controlling said timer circuit to start an acknowledgement timer associated with the transmitted data block.

34. Apparatus as in claim 33, wherein said transmitter, in response to receipt before expiry of an acknowledgement timer of a message from said receiver that the associated data block has been successfully received, controls said timer circuit to cancel the acknowledgement timer.

35. Apparatus as in claim 34, wherein said transmitter, in the absence of receipt before expiry of an acknowledgement timer of a message from said receiver that the associated data block has been successfully received, transmits to said receiver a request for a message identifying successfully received data blocks, and controls said timer circuit to start an associated panic timer.

36. Apparatus as in claim 35, wherein said transmitter, in response to receipt before expiry of a panic timer of a message from said receiver that the associated data block has been successfully received, controls said timer circuit to cancel the panic timer.

37. Apparatus as in claim 36, wherein said transmitter, in the absence of receipt before expiry of a panic timer of a message from said receiver that the associated data block has been successfully received, retransmits the associated data block to said receiver.

38. Apparatus as in claim 24, wherein said transmitter transmits sequentially identified data blocks to said receiver and said receiver, in the messages sent to said transmitter identifying successfully received data blocks, identifies the most recent data block received.

39. Apparatus as in claim 38, wherein said receiver periodically sends to said transmitter a message identifying the most recent data block received.

40. Apparatus as in claim 24, wherein:

said receiver sends to said transmitter negative acknowledgement messages identifying data blocks that said receiver has not successfully received, and

said transmitter is responsive to receipt of a negative acknowledgement message to retransmit to said receiver the data block identified as not having been successfully received,

the negative acknowledgement messages including identifications of successfully received data blocks.

24. Apparatus for transmitting data over a network, comprising:

a transmitter for transmitting data blocks; and

a receiver for receiving the transmitted data blocks, said receiver being operable to send to said transmitter messages identifying successfully received data blocks,

said transmitter retransmitting a data block to the receiver in response to absence of receipt by said transmitter, by a time determined by said timer circuit and referenced to the time of transmission of the data block, of a message from said receiver identifying the data block as having been successfully received.

41. A method, comprising:

transmitting data blocks to a receiver;

receiving from the receiver messages identifying successfully received data blocks; and

retransmitting a data block to the receiver in response to absence of receipt by a predetermined time referenced to the time of transmission of the data block, of a message from the receiver identifying the data block as having been successfully received.

42. A method as in claim 41, wherein the data block is part of a data packet and said retransmitting step retransmits the data block before a delay bound set for the data packet.

43. A method as in claim 41, including the step of:

sending to the receiver, in response to absence of receipt by the end of a first interval of time of a message from the receiver identifying a data block as having been successfully received, a request for a message identifying successfully received data blocks, and wherein

said retransmitting step is responsive to continued absence of receipt by the end of a second and later interval of time, of a message from the receiver that the data block has been successfully received, to retransmit the data block to the receiver.

44. A method as in claim 43, wherein the first time interval is referenced to the time of performance of said transmitting step for the data block and the second time interval is referenced to the time of performance of said sending step for the data block.

45. A method as in claim 44, wherein the data block is part of a data packet and the second time interval ends before a delay bound set for the data packet.

46. A method as in claim 41, including the steps of:

receiving from the receiver negative acknowledgement messages identifying data blocks that have not been successfully received; and

retransmitting the identified data blocks to the receiver in response to receipt of the negative acknowledgement messages, and wherein

the negative acknowledgement messages include identifications of successfully received data blocks.

47. A method as in claim 41, including the step of:

separating data packets into data blocks, and wherein said transmitting step transmits the data blocks sequentially.

48. A method as in claim 41, including the step of:

storing copies of transmitted data blocks, and wherein

said retransmitting step includes obtaining a stored copy of a data block for retransmission.

49. A method as in claim 41, including the step of:

starting, upon each performance of said transmitting step, an acknowledgement timer associated with the transmitted data block.

50. A method as in claim 49, including the step of:

canceling an acknowledgment timer in response to receipt, before expiry of the acknowledgment timer, of a message from the receiver that the associated data block has been successfully received.

51. A method as in claim 50, including the steps of:

sending to the receiver, in response to expiration of an acknowledgement timer in the absence of receipt before expiry of the acknowledgement timer of a message from the receiver that the associated data block has been successfully received, a request for a message identifying successfully received data blocks, and

starting a panic timer associated with the data block.

52. A method as in claim 51, including the step of:

canceling a panic timer associated with a data block in response to receipt, before expiry of the panic timer, of a message from the receiver identifying the data block as having been successfully received.

53. A method as in claim 51, including the step of:

retransmitting, in 52 to receipt before expiry of a panic timer of a message from the receiver that the associated data block has been successfully received, the associated data block to the receiver.

54. A method as in claim 41, including the step of:

periodically sending from the receiver to the transmitter messages identifying successfully received data blocks.

55. A transmitter as in claim 44, wherein:

the first interval of time expires at a time A+D−

T₁, where A is the arrival time of the data packet for transmission by said transmitting step, D is the delay bound time set for the data packet and T₁ is a threshold value, and

the second interval of time expires at a time A+D−

T₂, where T₂ is a threshold value lower than T₁.

56. A method as in claim 41, wherein said transmitting step transmits sequentially identified data blocks, and said retransmitting step is inoperative to retransmit a data block M upon receiving a message that either:

data block N has been successfully received, and M≦

N, or

data block P has been successfully received, and M≦

P+1.

58. A method as in claim 57, wherein the data blocks are constituent part of data packets and the predetermined time is shorter than a delay bound set for the data packets.

59. A method as in claim 57, including the step of:

storing copies of transmitted data blocks, and wherein said retransmitting step obtains a stored copy of a data block for retransmission.

60. A method as in claim 57, including the step of:

sending to the receiver, in response to absence of receipt by the end of a first interval of time of a message from the receiver identifying a data block as having been successfully received, a request for a message identifying successfully received data blocks, and wherein

said retransmitting step is responsive to continued absence of receipt by the end of a second and later interval of time, of a message from the receiver that the data block has been successfully received, to retransmit the data block to the receiver.

61. A method as in claim 60, wherein the first and second time intervals are referenced to the time of performance of said transmitting step for the data block.

62. A method as in claim 60, wherein the first time interval begins with performance of said transmitting step for the data block, and the second time interval begins with performance of said sending step for the data block.

63. A method as in claim 60, wherein the data block is part of a data packet and the second time interval ends before a delay bound set for the data packet.

64. A method as in claim 57 including the steps of:

sending from the receiver to the transmitter negative acknowledgement messages identifying data blocks that have not been successfully received; and

retransmitting the identified data blocks from the transmitter to the receiver in response to receipt of the negative acknowledgement messages, and wherein

the negative acknowledgement messages include identifications of successfully received data blocks

65. A method as in claim 57, including the step of:

starting, upon each performance of said transmitting step, an acknowledgement timer associated with the transmitted data block.

66. A method as in claim 65, including the step of:

canceling an acknowledgment timer in response to receipt, before expiry of the acknowledgment timer, of a message from the receiver that the associated data block has been successfully received.

67. A method as in claim 66, including the steps of:

sending to the receiver, in response to expiration of an acknowledgement timer in the absence of receipt before expiry of the acknowledgement timer of a message from the receiver that the associated data block has been successfully received, a request for a message identifying successfully received data blocks, and

starting a panic timer associated with the data block.

68. A method as in claim 67, including the step of:

canceling a panic timer associated with a data block in response to receipt, before expiry of the panic timer, of a message from the receiver identifying the data block as having been successfully received.

69. A method as in claim 68, including the step of:

retransmitting, in response to expiry of a panic timer, the associated data block to the receiver

70. A method as in claim 57, including the step of:

periodically sending from the receiver to the transmitter an identification of successfully received data blocks.

71. A method as in claim 57, including the steps of:

sequentially identifying data blocks transmitted to the receiver, and periodically sending from the receiver to the transmitter an acknowledgement message identifying the most recent data block received.

72. A method as in claim 57, wherein:

said sending step includes sending from the receiver to the transmitter negative acknowledgement messages identifying data blocks that have not been successfully received, and

said retransmitting step includes retransmitting the identified data blocks.

73. A method as in claim 72, including the steps of:

setting a negative acknowledgement timer in response to sending a negative acknowledgement message from the receiver to the transmitter, and

resending the negative acknowledgement message from the receiver to the transmitter in the absence of receiving at the receiver, by the time of expiry of the negative acknowledgement timer, a retransmission of the identified data block.

74. A method as in claim 62, wherein:

the first interval of time expires at a time A+D−

T₁, where A is the arrival time of the data packet for transmission by said transmitting step, D is the delay bound time set for the data packet and T₁ is a threshold value, and the second interval of time expires at a time A+D−

T₂, where T₂ is a threshold value lower than T₁.

75. A method as in claim 57, wherein said transmitting step transmits data blocks that are sequentially identified, and said retransmitting step is inoperative to retransmit a data block M upon receiving a message that either:

data block N has been successfully received, and M≦

N, or

data block P has been successfully received, and M≦

P+1.

57. A method, comprising:

transmitting data blocks from a transmitter to a receiver;

sending messages from the receiver to the transmitter identifying successfully received data blocks; and

retransmitting a data block to the receiver in response to absence of receipt at the transmitter, by a predetermined time referenced to the time of transmission of the data block, of a message from the receiver identifying the data block as having been successfully received.