Transmission control protocol window size adjustment for out-of-order protocol data unit removal

Abstract

A system and method for sharing a WAN TCP tunnel between multiple flows without having head of the line blocking problem is disclosed. When a complete but out of order PDU is stuck behind an incomplete PDU in a TCP tunnel, the complete but out of order PDU is removed from the tunnel. To do that, first the boundaries of the PDUs of the different flows are preserved and the TCP receive window advertisement is increased. The receive window is opened when initially receiving out-of-order data. As out-of-order complete PDUs are pulled out of the receive queue, to address double counting, place holders are used in the receive queue to indicate data that was in the queue. As out-of-order data PDUs are pulled out of the queue the window advertisement is increased. This keeps the sending side from running out of TX window and stopping transmission of new data.

What is claimed is:  
     
       1. A network device comprising:
 a physical port for connection to a wide area network (WAN) carrying Transmission Control Protocol (TCP) traffic; 
 a TCP receive queue coupled to said physical port to which first and second protocol data units (PDUs) are added; 
 a PDU removal logic coupled to said TCP receive queue to pull PDUs from said TCP receive queue, wherein if the first PDU is incomplete and the second PDU is complete, said PDU removal logic pulls the second PDU prior to the first PDU being complete; and 
 a TCP receive window advertisement logic coupled to said PDU removal logic and said port to provide a frame to the WAN which increases a TCP advertised receive window size by the size of the second PDU when the second PDU is pulled before the first PDU is complete. 
 
     
     
       2. The network device of  claim 1 , wherein the boundaries of each of the first and the second PDUs are preserved in said TCP receive queue. 
     
     
       3. The network device of  claim 2 , wherein the boundaries of each of the first and the second PDUs are preserved by using an urgent pointer in each of the PDUs to point to a PDU boundary. 
     
     
       4. The network device of  claim 3 , wherein the urgent pointer is pointed to the first byte of a PDU header. 
     
     
       5. The network device of  claim 2 , wherein the boundaries of each of the first and the second PDUs are preserved by parsing the first and the second PDUs to look for PDU headers. 
     
     
       6. The network device of  claim 1 , wherein a placeholder is placed in the TCP receive queue for the second PDU when the second PDU is pulled. 
     
     
       7. The network device of  claim 6 , wherein the placeholder has a byte counter for any PDU that is pulled out of the TCP receive queue. 
     
     
       8. The network device of  claim 6 , wherein the placeholder has a byte counter for any PDU that is still remaining in the TCP receive queue. 
     
     
       9. The network device of  claim 1 , wherein when the first PDU is complete, said PDU removal logic pulls the first PDU and said TCP receive window advertisement logic decreases the TCP advertised receive window by the size of the second PDU when the first PDU is pulled. 
     
     
       10. A method comprising:
 receiving from a wide area network (WAN) connection a plurality of two or more protocol data units (PDUs) by a Transmission Control Protocol (TCP) receive queue, wherein at least one of the PDUs is incomplete and one or more of the remaining PDUs are complete; 
 pulling the complete PDUs out of the TCP receive queue prior to completing a preceding PDU; and 
 providing a TCP receive window advertisement which increases a TCP advertised receive window size by the size of a pulled PDU each time a complete PDU is pulled out of the TCP receive queue prior to a preceding PDU being completed. 
 
     
     
       11. The method of  claim 10 , further comprising preserving the boundaries of each of the plurality of the PDUs in the TCP receive queue. 
     
     
       12. The method of  claim 11 , wherein the boundaries of each of the PDUs are preserved by using an urgent pointer in each of the PDUs to point to a PDU boundary. 
     
     
       13. The method of  claim 12 , further comprising pointing the urgent pointer to the first byte of a PDU header. 
     
     
       14. The method of  claim 11 , wherein the boundaries of each of the PDUs are preserved by parsing the PDUs to look for PDU headers. 
     
     
       15. The method of  claim 10 , further comprising placing a placeholder in the TCP receive queue for each complete PDU that is pulled. 
     
     
       16. The method of  claim 15 , wherein the placeholder has a byte counter for any PDU that is pulled of the TCP receive queue. 
     
     
       17. The method of  claim 15 , wherein the placeholder has a byte counter for any PDU that is still remaining in the TCP receive queue. 
     
     
       18. The method of  claim 10 , further comprising pulling the previously incomplete PDU from the TCP receive queue, when the previously incomplete PDU is complete and decreasing the TCP advertised receive window size by the size of the PDUs following the now complete PDU which have been previously pulled, when the now complete PDU is pulled. 
     
     
       19. A network device comprising:
 a physical port for connection to a wide area network (WAN) carrying Transmission Control Protocol (TCP) traffic; 
 a TCP receive queue coupled to said physical port to which a plurality of protocol data units (PDUs) are added; 
 a PDU removal logic coupled to said TCP receive queue to pull PDUs from said TCP receive queue, wherein if one of the plurality of PDUs is incomplete and one or more of the plurality of PDUs following the incomplete PDU are complete, said PDU removal logic pulls the one or more of the plurality of complete PDUs prior to the preceding incomplete PDU becoming complete; and 
 a TCP receive window advertisement logic coupled to said PDU removal logic and said port to provide a frame to the WAN which increases a TCP advertised receive window size by the size of a pulled PDU each time a complete PDU is pulled out of the TCP receive queue prior to a preceding PDU being completed. 
 
     
     
       20. The network device of  claim 19 , wherein the boundaries of each of the PDUs in said TCP receive queue are preserved. 
     
     
       21. The network device of  claim 20 , wherein the boundaries of each of the PDUs are preserved by using an urgent pointer in each of the PDUs to point to a PDU boundary. 
     
     
       22. The network device of  claim 21 , wherein the urgent pointer is pointed to the first byte of a PDU header. 
     
     
       23. The network device of  claim 20 , wherein the boundaries of each of the PDUs are preserved by parsing the PDUs to look for PDU headers. 
     
     
       24. The network device of  claim 19 , wherein a placeholder is placed in the TCP receive queue for each complete PDU when a complete PDU is pulled. 
     
     
       25. The network device of  claim 24 , wherein the placeholder has a byte counter for any PDU that is pulled out of the TCP receive queue. 
     
     
       26. The network device of  claim 24 , wherein the placeholder has a byte counter for any PDU that is still remaining in the TCP receive queue. 
     
     
       27. A method comprising:
 receiving a first and a second protocol data unit (PDU) by a Transmission Control Protocol (TCP) receive queue, the first PDU being incomplete and the second PDU being complete; 
 pulling the second PDU out of the TCP receive queue prior to the first PDU being complete; and 
 providing a TCP receive window advertisement which increases a TCP advertised receive window size by the size of the second PDU when the second PDU is pulled out of the TCP receive queue prior to the first PDU being complete. 
 
     
     
       28. The method of  claim 27 , further comprising preserving the boundaries of each of the first and the second PDUs in the TCP receive queue. 
     
     
       29. The method of  claim 28 , wherein the boundaries of each of the first and the second PDUs are preserved by using an urgent pointer in each of the PDUs to point to a PDU boundary. 
     
     
       30. The method of  claim 29 , further comprising pointing the urgent pointer to the first byte of a PDU header. 
     
     
       31. The method of  claim 28 , wherein the boundaries of each of the first and the second PDUs are preserved by parsing the first and the second PDUs to look for PDU headers. 
     
     
       32. The method of  claim 27 , further comprising placing a placeholder in the TCP receive queue for the second PDU when the second PDU is pulled. 
     
     
       33. The method of  claim 32 , wherein the placeholder has a byte counter for any PDU that is pulled of the TCP receive queue. 
     
     
       34. The method of  claim 32 , wherein the placeholder has a byte counter for any PDU that is still remaining in the TCP receive queue. 
     
     
       35. The method of  claim 27 , further comprising pulling the first PDU out of the TCP receive queue when the first PDU becomes complete and decreasing the TCP receive window size by the size of the second PDU when the first PDU is pulled.