Systems and methods for requesting packets for transmission over a wirless channel having a dynamically changing capacity due to a highly varibale delay

• US 6,687,227 B1
• Filed: 03/13/2000
• Issued: 02/03/2004
• Est. Priority Date: 03/13/2000
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Li, Yalun, Cao, Carl F., Brost, Leslie K.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Swickhamer, Christopher M
• Application Number:
  US09/523,697
• Time in Patent Office: 1,422 Days
• Field of Search: 370/230,231,232,234,236,238,252,253,349,401,412,413,419,516,519
• US Class Current: 370/231
• CPC Class Codes: H04L 1/1835 Buffer management
• CPC Class Codes: H04L 2001/0092 Error control systems characterised by the topology of the transmission link
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

Systems and methods which allow the under-utilization of high-speed radio channels to be reduced significantly are provided which feature packet buffering and buffer management for a specific link segment of the end-to-end TCP connection. Dynamic rate control (DRC) is performed in a manner which transparently uses the advertised receiver window size mechanism provided within TCP, to maintain a steady stream of packets to be transported onto a long and variable delay high-speed channel. A queue is managed by dynamically relating the current size of the queue to the amount of incoming data by enlarging or shrinking the client advertised window size to the predicted buffer growth. DRC does not perform end-to-end flow control, but rather it supplements this function of TCP. The invention may be implemented as an agent of TCP in the sense that it is hidden in the middle of the network.

Claims

1. A method of requesting packets from a first end-point for transmission to a second end-point over a first channel followed by a second channel which is a wireless channel having a dynamically changing capacity due to a highly variable delay, the method comprising at an interface between the first and second channels:

queuing packets received on the first channel in a queue having a queue length equal to the number of packets queued, and dequeueing them onto the second channel as capacity of the second channel permits;

making an estimate representative of the instantaneous capacity of the second channel;

as a function of the queue length and the estimate, requesting packet transmissions from the first end-point in a manner which avoids the queue becoming empty when the first end-point still has further packets to transmit.

2. A method according to claim 1 for application in the context of an end-to-end packet delivery system in which the first end-host is permitted to send packets as a function of a window size specified in acknowledgement packets it receives, the method further comprising:

receiving acknowledgement packets over the second channel;

for each acknowledgement packet received;

extracting an original window size specified in the acknowledgement packet received;

calculating a new window size as a function of the queue length, the estimate and the original window size;

generating a new acknowledgement packet which is substantially the same as the acknowledgement packet received except that the new window size has been substituted in place of the original window size;

requesting packet transmissions from the first end-point by forwarding the acknowledgement packet on the first channel.

3. A method according to claim 2 further comprising:

determining as said estimate one or more acknowledgement frequency parameters representative of the rate at which acknowledgements are being received over the second channel.

4. A method according to claim 3 wherein determining one or more acknowledgement frequency parameters comprises:

maintaining an average time between acknowledgement packets;

determining a difference between a most recent time between acknowledgement packets and the average time between acknowledgement packets.

5. A method according to claim 4 wherein said new window size is computed according to:

new window size=α

(original window size)+β

/(number of packets in queue+1)+δ

(Difference between most recent acknowledgement inter-arrival time and average inter-arrival time) where α

, β and

δ

are parameters.

6. A method according to claim 5 for use in the context of TCP/IP, where said acknowledgments are TCP acknowledgements.

7. A method according to claim 6 wherein said original window size is a TCP client advertised window size, and wherein said new window size is a TCP advertised window size.

8. A method according to claim 2 wherein said new window size is computed as an increasing function of the original window size, an increasing function of the instantaneous capacity of the second channel, and a decreasing function of the number of packets in the queue.

9. A method according to claim 2 for use in the context of TCP/IP, where said acknowledgments are TCP acknowledgements.

10. A method according to claim 9 wherein said original window size is a TCP client advertised window size, and wherein said new window size is a TCP advertised window size.

11. A method according to claim 1 for application in the context of an end-to-end packet delivery system in which the first end-host is permitted to send packets as a function of a window size specified in acknowledgement packets it receives, the method further comprising:

determining as said estimate one or more acknowledgement frequency parameters representative of the rate at which acknowledgements are being received over the second channel.

12. A method according to claim 1 further comprising computing a number of packets to request as an increasing function of the instantaneous capacity on the second channel, and a decreasing function of the number of packets in the queue, wherein requesting packet transmissions from the first end-point comprises requesting said number of packets to request.

13. A method according to claim 1 for use in the context of TCP/IP (Transport Control Protocol/Internet Protocol), wherein requesting packet transmissions is done using a TCP (Transport Control Protocol) advertised window size mechanism.

14. A method according to claim 1 wherein there is an end-to-end acknowledgement protocol between the two end-hosts.

15. A method according to claim 14 wherein said second channel features a link layer ARQ (Automatic Repeat Request) protocol which functions below the level of the end-to-end acknowledgement protocol.

16. A method according to claim 15 wherein the link layer ARQ protocol is RLP-III (Radio Link Protocol-III).

17. An apparatus for requesting packets from a first end-point for transmission to a second end-point over a first channel followed by a second channel which is a wireless channel having a dynamically changing capacity due to a highly variable delay, the apparatus comprising a queue adapted to queue packets and having a queue length equal to the number of packets queued, and a processing element adapted to queue packets received on the first channel in the queue, and to dequeue them onto the second channel as capacity of the second channel permits, the processing element being further adapted to make an estimate representative of the instantaneous capacity of the second channel, and as a function of the queue length and the estimate, request packet transmissions from the first end-point in a manner which avoids the queue becoming empty when the first end-point still has further packets to transmit.

18. An intermediate node comprising the apparatus of claim 17.

19. A wireless access node comprising the apparatus of claim 17.

20. A digital signal processor comprising the apparatus of claim 17.

21. An application specific integrated circuit comprising the apparatus of claim 17.

22. A printed circuit card comprising the apparatus of claim 17.

23. An apparatus for requesting packets from a first end-point for transmission to a second end-point over a first channel followed by a second channel which is a wireless channel having a dynamically changing capacity due to a highly variable delay, the method comprising at an interface between the first and second channels:

queuing means for queuing packets received on the first channel and for dequeueing them onto the second channel as capacity of the second channel permits;

processing means for making an estimate representative of the instantaneous capacity of the second channel;

packet transmission requesting means for, as a function of the queue length and the estimate, requesting packet transmissions from the first end-point in a manner which avoids the queue becoming empty when the first end-point still has further packets to transmit.