Method for pacing data flow in a packet-based network

• US 6,115,357 A
• Filed: 06/29/1998
• Issued: 09/05/2000
• Est. Priority Date: 07/01/1997
• Status: Expired due to Term

• Current Assignee: Gen Digital Inc.
• Original Assignee: Packeteer Incorporated (Gen Digital Inc.)
• Inventors: Galloway, Brett D., Packer, Robert L.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/106,924
• Time in Patent Office: 799 Days
• Field of Search: 370/519, 370/389, 370/231, 370/235, 370/229, 370/230, 370/232, 370/233, 370/234, 370/236-238, 709/232, 709/233, 709/234, 709/235
• US Class Current: 370/231
• 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/22 Traffic shaping
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• 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/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/323 Discarding or blocking control packets, e.g. ACK packets

Abstract

A method for pacing data flows in packet switched networks by arranging data transmission over a period of time based upon a set of ascertainable factors about the underlying transmission link to derive an intersegment transmission interval. The intersegment transmission interval can be used to pace either data packets or acknowledgment packets. The method is especially useful for pacing the transmission of data in a digital data packet communication environment having a plurality of digital packet transmission stations inter-connectable in a data path and employing the Transmission Control Protocol (TCP) suite.

Claims

1. A method for pacing transmission of data in a packet communication environment having a plurality of transmission stations inter-connectable via a link through a wide area network cloud, said method comprising the steps of:

determining a round trip time for a packet issued by a transmitter and acknowledged by a receiver;

determining number of data segments in a flow control window;

determining a window transmission time as the amount of time required to transmit the data segments of the flow control window;

computing an intersegment transmission interval based on the round trip time, window transmission time and number of segments per flow control window; and

during a communication connection

successively transmitting packets, each containing a data segment, with intersegment transmission intervals between selected packets.

2. The method of claim 1 wherein the round trip time determining step comprises the steps of:

sending a first packet to a remote transmission station;

receiving a second packet as an acknowledgment from the remote transmission station;

measuring a time delay between the first packet and the second packet; and

computing the round trip time from the time delay.

3. The method of claim 1 wherein the intersegment transmission interval is randomly varied from its computed value during the transmitting step.

4. The method of claim 1 wherein the round trip time determining step is effected only once in conjunction with a single connection.

5. The method according to claim 1 wherein said intersegment transmission interval establishes a delay bound for scheduling of packets for transmission.

6. The method of claim 1 including a further step of recomputing the intersegment transmission interval upon a change of any one of round trip time, window transmission time and number of segments per window.

7. The method according to claim 1 wherein any one of said determining steps is effected prior to said first transmitting step.

8. The method according to claim 1 wherein said round trip time (RTT) determining step includes computation based on an arbitrary rate (AR) according to the relation:

(RTT)=(WB)/(AR), where (WB) is number of bits in a flow control window, in order to compute said intersegment transmission interval.

9. The method according to claim 1 wherein said intersegment transmission interval computing step comprises a computation according to the relation:

space="preserve" listing-type="equation">ITI=(RTT-WTT)/(NSW-1)

where

RTT is round trip time,

WTT is window transmission time,

NSW is number of segments per window,

RTT>

WTT, and

NSW>

1.

18. The method according to claim 1 wherein said intersegment transmission internal computing step comprises a computation according to the relation:

space="preserve" listing-type="equation">ITI=(RTT-WTT)/(NSW-1)

where

RTT is round trip time,

WTT is window transmission time,

NSW is number of segments per window,

RTT>

WTT, and

NSW>

1.

10. A method for pacing transmission of data in a packet communication environment having a plurality of transmission stations inter-connectable via a link through a wide area network cloud, said method comprising the steps of:

determining a round trip time for a packet issued by a transmitter and acknowledged by a receiver;

determining number of data segments in a flow control window;

determining a window transmission time as the amount of time required to transmit the data segments of the flow control window;

computing an intersegment transmission interval based on the round trip time, window transmission time and number of segments per flow control window; and

during a communication connection,

successively transmitting packets, each containing an acknowledgment of receipt of data, with intersegment transmission intervals between selected packets.

11. The method of claim 10 wherein the round trip time determining step comprises the steps of:

sending a first packet to a remote transmission station;

receiving a second packet as an acknowledgment from the remote transmission station;

measuring a time delay between the first packet and the second packet; and

computing the round trip time from the time delay.

12. The method of claim 10 wherein the intersegment transmission interval is randomly varied from its computed value during the transmitting step.

13. The method of claim 10 wherein the round trip time determining step is effected only once in conjunction with a single connection.

14. The method according to claim 10 wherein said intersegment transmission interval establishes a delay bound for scheduling of packets for transmission.

15. The method of claim 10 including a further step of recomputing the intersegment transmission interval upon a change of any one of round trip time, window transmission time and number of segments per window.

16. The method according to claim 10 wherein any one of said determining steps is effected prior to said first transmitting step.

17. The method according to claim 10 wherein said round trip time (RTT) determining step includes computation based on an arbitrary rate (AR) according to the relation:

(RTT)=(WB)/(AR), where (WB) is number of bits in a flow control window, in order to compute said intersegment transmission interval.