Method for rapid data rate detection in a packet communication environment without data rate supervision

• US 5,802,106 A
• Filed: 12/06/1996
• Issued: 09/01/1998
• Est. Priority Date: 12/06/1996
• Status: Expired due to Term

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: Packeteer Incorporated (Gen Digital Inc.)
• Inventors: Packer, Robert L.
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): GHAYOUR, MOHAMMAD H
• Application Number:
  US08/762,828
• Time in Patent Office: 634 Days
• Field of Search: 375/225, 370/229, 370/233, 370/234, 370/235, 370/236, 370/253
• US Class Current: 375/225
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/225 Determination of shaping rate, e.g. using a moving window
• 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 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method for data flow rate detection useful with data flow rate control is introduced into a TCP packet communication environment which does not have data rate supervision by computing presumed speed based on latency between packets during the initial interchange of synchronization (SYN) packet and the acknowledgement (ACK) packet, presuming to know the initial length of each. This information may be utilized to determine potential rate of data flow for further use in making bandwidth allocation and rate enforcement decisions.

Claims

1. A method for detecting data rate of data packets in a digital data packet communication environment having a plurality of digital packet transmission stations interconnectable in a data path, wherein said data packet communication environment employs the Transmission Control Protocol (TCP), wherein said data packet communication environment lacks explicit end-to-end data rate control, said method comprising the steps of:

causing a first digital packet transmission station at a remote first end to send a first synchronization packet to a second digital packet transmission station at a local second end in the regular course of requesting that a connection be established;

causing said second digital packet transmission station to send a second synchronization packet of known data length to said first digital packet transmission station at said second end in the regular course of establishing a connection;

waiting at said second digital packet transmission station for an acknowledgement packet;

noting time of arrival of said acknowledgement packet;

waiting at said second digital packet transmission station for receipt of a first data packet;

noting time of arrival of said first data packet and data length of said first data packet;

thereafter

determining an initial estimate of serialization speed by dividing the data length of the first data packet by the difference in time of arrival of said acknowledgement packet and time of arrival of said first data packet; and

recording said initial estimate of serialization speed for further use.

4. The method according to claim 1 further including separating estimates of latency from estimates of serialization speed;

and

recording said estimates of latency along with said estimates of serialization speed.

2. A method for detecting data rate of data packets in a digital data packet communication environment having a plurality of digital packet transmission stations interconnectable in a data path, wherein said data packet communication environment employs the Transmission Control Protocol (TCP), wherein said data packet communication environment lacks explicit end-to-end data rate control, said method comprising the steps of:

causing a first digital packet transmission station at a remote first end to send a first synchronization packet to a second digital packet transmission station at a local second end in the regular course of requesting that a connection be established;

causing said second digital packet transmission station to send a second synchronization packet of known data length to said first digital packet transmission station at said second end in the regular course of establishing a connection;

waiting at said second digital packet transmission station for an acknowledgement packet;

noting time of arrival of said acknowledgement packet;

waiting at said second digital packet transmission station for receipt of a first data packet;

noting time of arrival of said first data packet and data length of said first data packet;

timing from the sending of said second synchronization packet;

determining a lower limit on serialization speed by dividing the sum of the data length of the synchronization packet and said acknowledgement packet by the time of arrival of said acknowledgement packet relative to the time of sending said second synchronization packet; and

recording said lower limit on serialization speed for further use.

3. The method according to claim 2 further including:

thereafter refining estimates of serialization speed by measuring amounts of data which are actually received per unit time.

5. A method for detecting data rate of data packets in a digital data packet communication environment having a plurality of digital packet transmission stations interconnectable in a data path, wherein said data packet communication environment employs the Transmission Control Protocol (TCP), wherein said data packet communication environment lacks explicit end-to-end data rate control, and wherein said acknowledgement packet is inseparable from said first data packet said method comprising the steps of:

causing a first digital packet transmission station at a remote first end to send a first synchronization packet to a second digital packet transmission station at a local second end in the regular course of requesting that a connection be established;

causing said second digital packet transmission station to send a second synchronization packet of known data length to said first digital packet transmission station at said second end in the regular course of establishing a connection;

waiting at said second digital packet transmission station for an acknowledgement packet;

noting time of arrival of said acknowledgement packet;

waiting at said second digital packet transmission station for receipt of a first data packet;

noting time of arrival of said first data packet and data length of said first data packet;

thereafter

estimating latency by;

first assuming zero latency;

calculating said serialization speed given an assumption of zero latency;

thereafter

sanitizing said serialization speed to a lower speed; and

thereafter

recalculating said serialization speed given an assumption of latency at said lower speed; and

thereafter

recording said estimates of latency along with said estimates of serialization speed.

6. The method according to claim 5 further including:

thereafter refining estimates of serialization speed by measuring amounts of data which is actually received per unit time.

7. A method for controlling data rate of data packets in a digital data packet communication environment having a plurality of digital packet transmission stations interconnectable in a data path, wherein said data packet communication environment lacks explicit end-to-end data rate control and wherein said data packet communication environment employs the Transmission Control Protocol (TCP), said method comprising the steps of:

causing a second digital packet transmission station at a local second end to initiate a first synchronization packet of known data length to request a connection to a first digital data packet transmission station at a remote first end in the regular course of requesting that a connection be established, while initiating timing from said request;

thereby

causing said first digital packet transmission station at said remote first end to send a second synchronization packet of known data length to said second digital packet transmission station at said local second end in the regular course of establishing a connection;

causing said second digital packet transmission station to send an acknowledgement packet of known data length to said first digital packet transmission station at said second end while logging timing of each transmission and reception event;

causing said second digital packet transmission station to send a first data packet of known data length to said first digital packet transmission station at said second end;

waiting at said second digital packet transmission station for at least an acknowledgement and any data in a return packet;

noting time of arrival and size of said return packet;

thereafter

determining an initial estimate of serialization speed plus the invariant portion of round trip transit time by dividing the data length of the first data packet plus said return packet by their round trip transit time;

determining a second estimate of serialization speed plus said invariant portion of said round trip transit time by comparing with an estimate of serialization speed derived from round trip transit time of said first synchronization packet and said second synchronization packet, given known data length of said first synchronization packet and said second synchronization packet; and

comparing said initial estimate with said second estimate to remove effects of said time invariant round trip transit time (invariant latency) in order to obtain the serialization speed; and

recording said serialization speed for further use.

8. The method according to claim 7 further including:

thereafter refining estimates of serialization speed by measuring amounts of data which are actually received per unit time.