Transmission control protocol queue sorting

• US 7,876,677 B2
• Filed: 05/22/2007
• Issued: 01/25/2011
• Est. Priority Date: 05/22/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Cheshire, Stuart D.
• Primary Examiner(s): Kumar; Pankaj
• Assistant Examiner(s): Choi; Eunsook
• Application Number:
  US11/805,503
• Publication Number:
  US 20080291937A1
• Time in Patent Office: 1,344 Days
• Field of Search: None
• US Class Current: 370/230.1
• 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/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/624 Altering the ordering of packets in an individual queue

Abstract

A device that queues and transmits data packets is described. This device includes: a queue configured to store data packets awaiting transmission; a controller configured to dynamically determine an order in which the data packets are transmitted from the queue; and a transmission mechanism configured to transmit the data packets from the queue in the determined order. The transmission order is determined using Transmission Control Protocol (TCP) sequence numbers and/or TCP timestamps contained in the data packets in the queue in order to provide increased utility without reducing existing fairness between independent data streams.

Claims

1. An apparatus that queues and transmits data packets, comprising:

a queue configured to store data packets awaiting transmission;

a controller configured to dynamically determine an order in which the data packets are transmitted from the queue using Transmission Control Protocol (TCP) sequence numbers and/or TCP timestamps contained in the data packets in the queue, wherein while removing a data packet from the head of the queue in preparation for transmission, the controller is further configured to ensure that the packets are transmitted in the determined order by;

searching the queue for the data packet with an earliest sequence number belonging to a same TCP connection as the data packet at the head of the queue;

determining that the data packet with an earliest sequence number is not the data packet currently at the head of the queue; and

swapping the data packet at the head of the queue with the earliest data packet, wherein swapping the data packets involves modifying a preference value associated with the packets to cause the earliest data packet to be processed before any other data packets for the same TCP connection; and

a transmission mechanism configured to transmit the data packets from the queue in the determined order.

2. The apparatus of claim 1, wherein while ensuring that the packets are transmitted in the determined order, the controller is configured to use the TCP sequence numbers and/or TCP timestamps to ensure that if other data packets belonging to the same TCP connection are also in the queue at that time, then the data packet which is removed is the data packet that is earliest in sequence associated with the TCP connection.

3. The apparatus of claim 2, wherein the controller is configured to maintain relative fairness between different TCP connections by restricting data packet reordering to be performed only with respect to other data packets belonging to the same TCP connection, so that for any given set of data packets in the queue awaiting transmission, the order in which associated TCP connections will each transmit data packets remains unchanged, but during a turn for a given TCP connection, the data packet selected for transmission, from the data packets for the given TCP connection currently waiting in the queue, is the data packet that is earliest in the sequence for the given TCP connection.

4. The apparatus of claim 3, wherein while removing the data packet from the head of the queue in preparation for transmission, the controller is further configured to:

determine that the data packet with the earliest sequence number is the data packet currently at the head of the queue;

remove the data packet at the head of the queue; and

cause the data packet to be transmitted.

5. The apparatus of claim 3, wherein searching the queue involves searching a linked list, a hash table, a heap, or other data structure so that the search is performed more efficiently than a simple linear search.

6. The apparatus of claim 3, wherein when a new data packet is to be inserted into the queue, the controller is configured to:

place the new data packet at the tail end of the queue, or as otherwise dictated by a queuing policy that is presently in effect;

search the queue, starting at the head, in order of expected transmission, and to examine each waiting data packet that belongs to the same TCP connection as the new data packet;

if another data packet is found that belongs to the same TCP connection as the new data packet but falls later in the sequence compared to the new data packet, to swap the data packet and the new data packet so that the data packet that falls later in the sequence now becomes the new data packet; and

to

continue searching from the current position in the queue, wherein after every data packet belonging to the same TCP connection as the new data packet has been examined, the insertion of the new data packet into the queue is complete.

7. The apparatus of claim 6, wherein searching the queue involves searching a linked list, a hash table, a heap, or other data structure so that the search is performed more efficiently than a simple linear search.

8. The apparatus of claim 6, wherein the new data packet is a retransmission of a previously dropped data packet.

9. The apparatus of claim 1, wherein the data packets in the queue are further reordered based on active queue management.

10. The apparatus of claim 1, wherein the data packets in the queue are further reordered based on weighted-fair queuing, queue reservations, or queue priority flags.

11. The apparatus of claim 1, wherein the process of dynamically determining the processing order of the data packets in the queue is performed recursively.

12. The method of claim 1, wherein modifying the preference value includes updating a preference value for each packet in the queue, but not sorting the actual packets in a memory in the queue.

13. A method for queuing and transmitting data packets, comprising:

queuing data packets awaiting transmission;

dynamically determining an order in which the data packets are transmitted from the queue using Transmission Control Protocol (TCP) sequence numbers and/or TCP timestamps contained in the data packets in the queue, wherein while removing a data packet from the head of the queue in preparation for transmission, the method further comprises ensuring that the packets are transmitted in the determined order by;

searching the queue for the data packet with an earliest sequence number belonging to the same a same TCP connection as the data packet at the head of the queue;

determining that the data packet with the earliest sequence number is not the data packet currently at the head of the queue; and

swapping the data packet at the head of the queue with the earliest data packet, wherein swapping the data packets involves modifying a preference value associated with the packets to cause the earliest data packet to be processed before any other data packets for the same TCP connection; and

transmitting data packets from the queue in the determined order.

14. The method of claim 13, wherein ensuring that the packets are transmitted in the determined order comprises using the TCP sequence numbers and/or TCP timestamps to ensure that if other data packets belonging to the same TCP connection are also in the queue at that time, then the data packet which is removed is the data packet that is earliest in sequence associated with the TCP connection.

15. The method of claim 14, wherein relative fairness between different TCP connections is maintained by restricting data packet reordering to be performed only with respect to other data packets belonging to the same TCP connection, so that for any given set of data packets in the queue awaiting transmission, the order in which associated TCP connections will each transmit data packets remains unchanged, but during a turn for a given TCP connection, the data packet that is selected for transmission, from the data packets for the given TCP connection currently waiting in the queue, is the data packet that is earliest in the sequence for the TCP connection.

16. The method of claim 15, wherein while removing the data packet from the head of the queue in preparation for transmission, the method involves:

determining that the data packet with the earliest sequence number is the data packet currently at the head of the queue;

removing the data packet at the head of the queue; and

causing this data packet to be transmitted.

17. The method of claim 15, wherein searching the queue involves searching a linked list, a hash table, a heap, or other data structure so that the search is performed more efficiently than a simple linear search.

18. The method of claim 15, wherein when a new data packet is to be inserted into the queue, the method involves:

placing the new data packet at the tail end of the queue, or as otherwise dictated by a queuing policy that is presently in effect;

searching the queue, starting at the head, in order of expected transmission, and examining each waiting data packet that belongs to the same TCP connection as the new data packet;

if another data packet is found that belongs to the same TCP connection as the new data packet but falls later in the sequence compared to the new data packet, swapping the data packet and the new data packet so that the data packet that falls later in the sequence now becomes the new data packet; and

continuing to search from the current position in the queue, wherein after every data packet belonging to the same TCP connection as the new data packet has been examined, the insertion of the new data packet into the queue is complete.

19. The method of claim 18, wherein searching the queue involves searching a linked list, a hash table, a heap, or other data structure so that the search is performed more efficiently than a simple linear search.

20. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

queuing data packets awaiting transmission;

dynamically determining an order in which the data packets are transmitted from the queue using Transmission Control Protocol (TCP) sequence numbers and/or TCP timestamps contained in the data packets in the queue, wherein while removing a data packet from the head of the queue in preparation for transmission, the method further comprises ensuring that the packets are transmitted in the determined order by;

searching the queue for the data packet with an earliest sequence number belonging to a same TCP connection as the data packet at the head of the queue;

determining that the data packet with the earliest sequence number is not the data packet currently at the head of the queue; and

swapping the data packet at the head of the queue with the earliest data packet, wherein swapping the data packets involves modifying a preference value associated with the packets to cause the earliest data packet to be processed before any other data packets for the same TCP connection; and

transmitting data packets from the queue in the determined order.