Determining client latencies over a network

• US 7,747,729 B2
• Filed: 06/14/2002
• Issued: 06/29/2010
• Est. Priority Date: 06/14/2002
• Status: Active Grant

• Current Assignee: Zarbana Digital Fund LLC (Intellectual Ventures LLC)
• Original Assignee: Khorsabad Lockdown LLC (Intellectual Ventures LLC)
• Inventors: Levy, Hanoch, Marshak, Marik
• Primary Examiner(s): Winder; Patrice
• Assistant Examiner(s): AILES, BENJAMIN A
• Application Number:
  US10/170,460
• Publication Number:
  US 20030233445A1
• Time in Patent Office: 2,937 Days
• Field of Search: 709/224, 370/229, 370/232, 702/176, 702/186
• US Class Current: 709/224
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• 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 69/28 Timers or timing mechanisms used in protocols

Abstract

A network latency estimation apparatus for estimating latency in a network communication between a server and a client. The apparatus includes an event observer to observe occurrences of pre-selected events occurring at the server. A logging device associated with the event observer logs into a data store the occurrence of the events together with corresponding time information. A latency estimator associated with the logging device uses the logged occurrences with the corresponding time information to arrive at an estimation of the latency for the communication.

Claims

1. An apparatus for estimating a web page latency for a web page transaction, comprising:

a server, including one or more processors, configured to estimate a queuing latency time for the server to accept a new request from a client and establish a connection with the client (T_QUEUING), wherein the server is configured to estimate a round trip time between the server and the client (RTT), wherein the server is configured to estimate a time required for the client to receive a web page (T<sub>CLIENT—

RECV</sub>) pursuant to the request, wherein the server is configured to determine a time the server receives the request (T<sub>SERVE—

RECV</sub>) from the client, wherein the server is configured to provide the web page to the client responsive to the received request, and wherein the server is configured to estimate a client perceived latency from when the client sends the request and receives back the web page according to the estimated queuing latency time T_QUEUING, the estimated round trip time RTT, and a difference between the estimated time required for the client to receive the web page pursuant to the request T<sub>CLIENT—

RECV</sub> and the determined time the server receives the request T<sub>SERVE—

RECV</sub>.

2. The apparatus according to claim 1 wherein the one or more processors are further configured to estimate a main page latency for receiving Hyper Text Markup Language (HTML) for a main web page of the web page transaction according to:

T_QUEUING+(1.5×

RTT)+T<sub>CLIENT—

RECV-HTML</sub>−

T<sub>SERVE—

RECV</sub>,

wherein T<sub>CLIENT—

RECV-HTML</sub> is an estimated time the client receives an HTML portion of the web page and T<sub>SERVE—

RECV</sub> is the time the server receives the request from the client for the HTML.

3. The apparatus according to claim 1 wherein the one or more processors are further configured to identify multiple different connections the client opens with the server for the web page transaction and use a last sent data on any of the multiple different connections for estimating the time T_CLIENT—

_RECV when the client receives the web page.

4. The apparatus according to claim 1 wherein the one or more processors are further configured to operate a queuing probe that measures the queuing latency T_QUEUING by identifying a time required for the server to accept a new Transmission Control Protocol/Internet Protocol (TCP/IP) connection request from the client.

5. The apparatus according to claim 1 wherein the one or more processors are further configured to:

insert a sentry in web page Hyper Text Markup Language (HTML) sent by the server to the client, the sentry prompting the client to send a request back to the server when substantially all of the HTML for the web page is downloaded by the client; and

use the client request to determine the time T<sub>CLIENT—

RECV</sub> when the client received the last of the web page data.

6. The apparatus according to claim 5 wherein the sentry is located at the end of the web page sent to the client by the server.

7. The apparatus according to claim 1 wherein the one or more processors are further configured to:

identify a ping time (T1) for the current web transaction;

use the ping time T1 as an initial estimate of the round trip time RTT between the server and the client;

search logs for a smallest inter-request time (T2) for the web transaction, the inter-request time being a time between the server sending a response to the client and the server receiving a subsequent request back from the client on a same channel; and

use the smaller of the ping time T1 and the inter-request time T2 as an estimation of the round trip time RTT between the client and the server.

8. The apparatus according to claim 1 wherein the one or more processors are further configured to:

estimate perceived packet rates (Rate_{INTER-REQUEST}) for each new download of web page data to the client;

estimate connection packet rates (Rate_CONN) by averaging the perceived packet rates Rate_{INTER-REQUEST} for each particular connection to a particular channel of the web page transaction; and

estimate a web transaction packet rate (Rate_WEB-TRANs) for the entire web transaction by averaging the estimated connection packet rates Rate_CONN for the different connections used in the web page transaction.

9. The apparatus according to claim 8 wherein the one or more processors are further configured to estimate the perceived packet rates Rate_{INTER-REQUEST} as follows:

${\mathrm{Rate}}_{\mathrm{INTER}-\mathrm{REQUEST}}=\frac{\left[\mathrm{RESPONSE}<br><br><br><br>{\mathrm{SIZE}}_i÷<br><br>\mathrm{PACKET}<br><br><br><br>\mathrm{SIZE}\right]}{\max <br><br>\left\{T_{\mathrm{SERVER\_RECVi}+1}-T_{\mathrm{SERV\_SENDi}}-0.5\times <br><br>\mathrm{RTT},0.5<br><br>\mathrm{RTT}\right\}}$

where;

RESPONSE SIZE_i is a size of a web page response to the client;

PACKET SIZE is a size of packets sent from the server to the client;

T<sub>SERVER—

RECVi+1</sub> is a time the server receives a request subsequent to a present request i; and

T<sub>SERV—

SENDi</sub> is a time the server starts sending a response to the present request i.

10. The apparatus according to claim 1 wherein the one or more processors are further configured to:

identify a time T1 for the server to finish writing any remaining data for the web page to a channel, the time T1 including the estimated time it takes for the remaining data to arrive at the client once the server finishes writing the data to the channel;

identify a time T2 for the server to receive a request for data from the client after writing the data, the time T2 offset by half the round trip time RTT;

identify a time T3 when the server receives a sentry request back from the client, the time T3 offset by half the round trip time RTT and the sentry request contained in Hyper Text Markup Language (HTML) sent by the server that prompts the client to send a request back to the server when substantially all of the HTML for the web page has been downloaded by the client;

estimate the time when the client receives the web page T<sub>CLIENT—

RECV</sub> as a minimum or earliest of T1, T2, and T3.

11. The apparatus according to claim 1 wherein the one or more processors are further configured to estimate a time (T_CLIENT—

<sub>REV-LAST—

RESPONSE</sub>) when the client receives the entire web page that includes a Hyper Text Markup Language (HTML) portion of the web page and images or other components, if any, contained in the web page, the one or more processors configured to;

identify the channels that the client has opened with the server for the web transaction;

estimate T<sub>CLIENT—

REV-LAST—

RESPONSE</sub> as a time the client receives the HTML for the web page when there is only one request for data on a current channel for the web transaction and the current channel is used requesting the HTML.

12. The apparatus according to claim 1 wherein when more than one request for data is made on the current channel or when the current channel is not used for requesting the HTML, the one or more processors are further configured to:

estimate T<sub>CLIENT—

REV-LAST—

RESPONSE</sub> as a time when the server finishes writing remaining data for the web page to the current channel plus an estimated time required for the remaining data to arrive at the client.

13. The apparatus according to claim 12 wherein:

when an estimated line rate (Rate_LINE) is valid, the time when the data for the web page arrives at the client is estimated by determining a number of remaining packets once the server has finished writing to the current channel and dividing the number of remaining packets by the line rate (Rate_LINE); and

when the estimated line rate Rate_LINE is invalid, the time for the data to arrive at the client is estimated by determining a number of remaining packets once the server has finished writing to the current channel and dividing the number of remaining packets by a perceived packet rate for the web transaction (Rate_WEB-TRANS).

14. The apparatus according to claim 13 wherein the one or more processors are further configured to:

estimate perceived packet rates (Rate_{INTER-REQUEST}) for each new download of web page data to the client;

identify the perceived packet rates Rate_{INTER-REQUEST} that are within a certain time range;

determine the estimated packet line rate (Rate_LINE) is invalid when a given number of the identified perceived packet rates Rate_{INTER-REQUEST} are not within the time range; and

determine the packet line rate Rate_LINE as an average of the identified perceived packet rates Rate_{INTER-REQUEST} when a given number of Rate_{INTER-REQUEST} are within the time range.

15. The apparatus according to claim 1 wherein the one or more processors are further configured to:

identify a client queuing time for sending a request for an initial web page;

identify a time required for the request to be received by the server;

identify a time for the server to process the request;

identify a time for the server to write responses to the request;

identify a time when the client receives the server responses;

identify a time for additional client requests for components of the initial web page to get to the server;

identify a time for the server to process the additional requests;

identify a time for the server to write additional responses to the additional requests to the connection;

identify a time when the client receives the additional responses from the server; and

use all of the identified times to estimate the client perceived latency time for the web transaction.

16. The apparatus according to claim 1 wherein the one or more processors are further configured to estimate a client latency for a given download of a complete web page as follows:

T_QUEUING+(1.5×

RTT)+T<sub>CLIENT—

RECV-LAST—

RESPONSE</sub>−

T<sub>SERVE—

RECV-HTML</sub>,

wherein T<sub>CLIENT—

RECV-LAST—

RESPONSE</sub> is a time the client receives a last response from the server for the entire web page; and

T<sub>SERVE—

RECV-HTML</sub> is the time when the server receives a first request for HTML from the client.

17. A method comprising:

estimating, with a server, a queuing latency time for the server to accept a new request from a client and establish a connection with the client (T_QUEUING);

estimating, with the server, a time required for the client to receive a web page (T<sub>cLIENT—

RECV</sub>) pursuant to the request;

identifying, with the server, a time when the server receives the request from the client (T<sub>SERvE—

RECV</sub>), wherein the server is configured to provide the web page to the client responsive to the received request; and

estimating, with the server, a client perceived latency for a web transaction according to the estimated queuing latency time T_QUEUING, an estimated round trip time RTT, and a difference between the estimated time required for the client to receive the web page pursuant to the request T<sub>CLIENT—

RECV</sub> and the identified time the server receives the request T<sub>SERVE—

RECV</sub>.

18. The method according to claim 17 further comprising estimating the client perceived latency according to:

T_QUEUING+(1.5×

RTT)+T<sub>CLIENT—

RECV-HTML</sub>−

T<sub>SERVE—

RECV</sub>,

wherein T<sub>CLIENT—

RECV-HTML</sub> is an estimated time the client receives an Hyper Text Markup Language (HTML) portion of the web page, and T<sub>SERVE—

RECV</sub> is the time the server receives the request from the client for the HTML.

19. The method according to claim 17 further comprising:

identifying multiple different connections the client opens with the server for the web page transaction; and

using a last sent data on any of the multiple different connections for estimating the time T<sub>CLIENT—

RECV</sub> when the client receives the web page.

20. The method according to claim 17 further comprising:

measuring the queuing latency T_QUEUING by identifying a time required for the server to accept a new Transmission Control Protocol/Internet Protocol (TCP/IP) connection request from the client.

21. The method according to claim 17 further comprising:

inserting a tag in web page Hyper Text Markup Language (HTML) sent to the client that causes the client to send a request back to the server when substantially all of the HTML for the web page is downloaded; and

using the client request to determine the time T<sub>CLIENT—

RECV</sub> when the client received the last of the web page data.

22. The method according to claim 17 further comprising:

identifying a ping time (T1) for a current web transaction;

using the ping time T1 as an initial estimate of the round trip time RTT between the server and the client;

searching logs for a smallest inter-request time (T2) for the web transaction, the inter-request time being a time between the server sending a response to the client and the server receiving a subsequent request back from the client on a same channel; and

using the smaller of the ping time T1 and the inter-request time T2 as an estimation of the round trip time RTT between the client and the server.

23. The method according to claim 17 further comprising:

estimating perceived packet rates (Rate_{INTER-REQUEST}) for each new download of web page data to the client;

estimating connection packet rates (Rate_CONN) by averaging the perceived packet rates Rate_{INTER-REQUEST} for each particular connection to a particular channel of the web page transaction; and

estimating a web transaction packet rate (Rate_WEB-TRANS) for the entire web transaction by averaging the estimated connection packet rates Rate_CONN for the different connections used in the web page transaction.

24. The method according to claim 23 further comprising:

estimating the perceived packet rates Rate_{INTER-REQUEST} as follows;

${\mathrm{Rate}}_{\mathrm{INTER}-\mathrm{REQUEST}}=\frac{\left[\mathrm{RESPONSE}<br><br><br><br>{\mathrm{SIZE}}_i÷<br><br>\mathrm{PACKET}<br><br><br><br>\mathrm{SIZE}\right]}{\max <br><br>\left\{T_{\mathrm{SERVER\_RECVi}+1}-T_{\mathrm{SERV\_SENDi}}-0.5\times <br><br>\mathrm{RTT},0.5<br><br>\mathrm{RTT}\right\}}$

where;

RESPONSE SIZE_i is a size of a web page response to the client,

PACKET SIZE is a size of packets sent from the server to the client,

T<sub>SERVER—

RECVi+1</sub> is a time the server receives a request subsequent to a present request i, and

T<sub>SERV—

SENDi</sub> is a time the server starts sending a response to the present request i.

25. The method according to claim 17 further comprising:

identifying a time T1 for the server to finish writing any remaining data for the web page to a channel, the time T1 including the estimated time it takes for the remaining data to arrive at the client once the server finishes writing the data to the channel;

identifying a time T2 for the server to receive a request for data from the client after writing the data, the time T2 offset by half the round trip time RTT;

inserting a sentry request in Hyper Text Markup Language (HTML) that causes the client to send a request back to the server when substantially all of the HTML for the web page has been downloaded;

identifying a time T3 when the server receives the sentry request back from the client and offsetting time T3 by half the round trip time RTT; and

estimating the time when the client receives the web page T<sub>CLIENT—

RECV</sub> as a minimum or earliest of T1, T2, and T3.

26. The method according to claim 17 further comprising:

identifying the channels that the client has opened with the server for the web transaction; and

estimating a time T<sub>CLIENT—

REV-LAST—

RESPONSE</sub> when the client receives the entire web page that includes a Hyper Text Markup Language (HTML) portion of the web page and images or other components, if any, contained in the web page;

wherein a time T<sub>CLIENT—

REV-LAST—

RESPONSE</sub> is selected as a time when the client receives the HTML for the web page when there is only one request for data on a current channel for the web transaction and the current channel is used requesting the HTML.

27. The method according to claim 26 further comprising:

estimating T<sub>CLIENT—

REV-LAST—

RESPONSE</sub> as a time when the server finishes writing remaining data for the web page to the current channel plus an estimated time required for the remaining data to arrive at the client when there is more than one request for data is made on the current channel or when the current channel is not used for requesting the HTML.

28. The method according to claim 27 further comprising:

when a line rate (Rate_LINE) is valid, estimating the time when the data for the web page arrives at the client by determining a number of remaining packets once the server has finished writing to the current channel and dividing the number of remaining packets by the line rate Rate_LINE; and

when an estimated line rate Rate_LINE is invalid, estimating the time for the data to arrive at the client by determining a number of remaining packets once the server has finished writing to the current channel and dividing the number of remaining packets by a perceived packet rate for the web transaction (Rate_WEB-TRANS).

29. The method according to claim 28 further comprising:

estimating the perceived packet rates (Rate_{INTER-REQUEST}) for each new download of web page data to the client;

identifying the perceived packet rates Rate_{INTER-REQUEST} that are within a certain time range;

determining the estimated packet line rate (Rate_LINE) is invalid when a given number of the identified perceived packet rates Rate_{INTER-REQUEST} are not within the time range; and

determining the packet line rate Rate_LINE as an average of the identified perceived packet rates Rate_{INTER-REQUEST} when a given number of Rate_{INTER-REQUEST} are within the time range.

30. The method according to claim 17 further comprising:

identifying a client queuing time for sending a request for an initial web page;

identifying a time required for the request to be received by the server;

identifying a time for the server to process the request;

identifying a time for the server to write responses to the request;

identifying a time when the client receives the server responses;

identifying a time for additional client requests for components of the initial web page to get to the server;

identifying a time for the server to process the additional requests;

identifying a time for the server to write additional responses to the additional requests to the connection;

identifying a time when the client receives the additional responses from the server; and

using all of the identified times to estimate the client perceived latency time for the web transaction.

31. The method according to claim 17 further comprising estimating a client latency for a given download of the web page as follows:

T_QUEUING+(1.5×

RTT)+T<sub>CLIENT—

RECV-LAST—

RESPONSE</sub>−

T<sub>SERVE—

RECV-HTML</sub>,

wherein T<sub>CLIENT—

RECV-LAST—

RESPONSE</sub> is a time the client receives a last response from the server for the entire web page; and

T<sub>SERVE—

RECV-HTML</sub> is the time when the server receives a first request for HTML from the client.

32. A network processing device, comprising:

a server to determine a time when the server receives a request from a client (T<sub>SERVE—

RECV</sub>), wherein the server is configured to provide an entire web page to the client responsive to the received request, wherein the server is configured to estimate a client receive time for the client to receive the entire web page (T<sub>CLIENT—

RECV</sub>) from the server during a web transaction, and wherein the server is configured to estimate a client perceived latency for the web transaction according to a difference between the estimated client receive time T<sub>CLIENT—

RECV</sub> and the determined time the server receives the request T<sub>SERVE—

RECV</sub>.

33. The network processing device according to claim 32 wherein the one or more processors are further configured to estimate a main page latency for the client to receive Hyper Text Markup Language (HTML) for a main web page of the web page transaction according to:

T_QUEUING+(1.5×

RTT)+T<sub>CLIENT—

RECV-HTML</sub>−

T<sub>SERVE—

RECV</sub>,

wherein T<sub>CLIENT—

RECV-HTML</sub> is an estimated time the client receives an HTML portion of the web page, and T<sub>SERVE—

RECV</sub> is the time the server receives a request from the client for the HTML.

34. The network processing device according to claim 32 wherein the server is configured to identify multiple different connections the client opens with the server for the web page transaction and use a last sent data on any of the multiple different connections for estimating the time T_CLIENT—

_RECV when the client receives the web page.

35. The network processing device according to claim 32 wherein the server is further configured to:

identify a time T1 for the server to finish writing any remaining data for the web page to a channel, the time T1 including the estimated time it takes for the remaining data to arrive at the client once the server finishes writing the data to the channel;

identify a time T2 for the server to receive a request for data from the client after writing the data, the time T2 offset by half the round trip time RTT;

identify a time T3 when the server receives a sentry request back from the client, the time T3 offset by half the round trip time RTT and the sentry request contained in Hyper Text Markup Language (HTML) sent by the server that prompts the client to send a request back to the server when substantially all of the HTML for the web page has been downloaded by the client;

estimate the time when the client receives the web page T<sub>CLIENT—

RECV</sub> as a minimum or earliest of T1, T2, and T3.

36. The network processing device according to claim 32 wherein the server is further configured to:

identify one or more channels that the client has opened with the server for the web transaction;

estimate a time (T<sub>CLIENT—

REV-LAST—

RESPONSE</sub>) when the client receives the entire web page that includes a Hyper Text Markup Language (HTML) portion of the web page and images or other components, if any, contained in the web page, T<sub>CLIENT—

REV-LAST—

RESPONSE</sub> estimated as a time the client receives the HTML for the web page when there is only one request for data on a current channel for the web transaction and the current channel is used requesting the HTML.

37. The network processing device according to claim 36 wherein when more than one request for data is made on the current channel or when the current channel is not used for requesting the HTML, the server is configured to:

estimate T<sub>CLIENT—

REV-LAST—

RESPONSE</sub> as a time when the server finishes writing remaining data for the web page to the current channel plus an estimated time required for the remaining data to arrive at the client.

38. The network processing device according to claim 32 wherein the server is further configured to estimate a client latency for a given download of a complete web page as follows:

T_QUEUING+(1.5×

RTT)+T<sub>CLIENT—

RECV-LAST—

RESPONSE</sub>−

T<sub>SERVE—

RECV-HTML</sub>,

wherein T<sub>CLIENT—

RECV-LAST—

RESPONSE</sub> is a time the client receives a last response from the server for the entire web page; and

T<sub>SERVE—

RECV-HTML</sub> is the time when the server receives a first request for HTML from the client.