Methods and apparatus for determining reverse path delay

According to the present invention, methods and apparatus are provided for determining components of a round trip time (RTT). A source node sends data to a destination node. The destination node inserts a timestamp into an acknowledgment and sends the acknowledgment back to the source node. The source node determines the RTT from its own measurements and estimates reverse path delay by comparing timestamps to expected timestamps. Considerations for destination node timestamp speed differences are provided.

CROSS REFERENCE TO RELATED CASES

The present application is related to concurrently filed U.S. Patent Application No. 60/75220, titled TRANSMISSION CONTROL PROTOCOL (TCP) CONGESTION CONTROL by Guglielmo M. Morandin, the entirety of which is incorporated by reference for all purposes.

BACKGROUND OF THE INVENTION

1. Field of the Invention.

The present invention generally relates to networking. More specifically, the present invention provides techniques and mechanisms for determining reverse path delay associated with a round trip time measurement.

2. Description of Related Art

Round trip time (RTT) is a commonly used networking metric for determining congestion between a source and a destination in a variety of networks. Networking tools and utilities allow a source to send data to a destination and the destination to respond to the source. The measured time between transmission of the data and receipt of the acknowledgment is referred to as the RTT. The RTT can be used by the source to estimate network congestion and latency between a source and a destination.

The RTT can also be used to set transmission rates and window sizes at a source. For example, if the RTT is relatively small, a source may interpret it as an indication of reduced network congestion and elect a higher transmission rate and a larger window size. Some improvements to TCP such as FastTCP described in “FastTCP: Motivation, Architecture, Algorithms, Performance” by Chen Jin, David Wei, and Steven Low, IEEE Infocom, March 2004, Hong Kong, explicitly use RTT to optimize window sizes.

However, using RTT as a metric for determining congestion has significant limitations. Consequently, it is desirable to provide techniques for improving the measurement of RTT components, such as reverse path delay or reverse delay components associated with RTT.

SUMMARY OF THE INVENTION

According to the present invention, methods and apparatus are provided for determining components of a round trip time (RTT). A source node sends data to a destination node. The destination node inserts a timestamp into an acknowledgment and sends the acknowledgment back to the source node. The source node determines the RTT from its own measurements and estimates reverse path delay by comparing timestamps to expected timestamps. Considerations for node timestamp speed differences are provided.

In one embodiment, a technique for determining reverse path delay associated with data transmission between a source and a destination is provided. Multiple packets are sent from a source to a destination. Multiple acknowledgments are received from the destination. Multiple acknowledgments include multiple timestamps provided by the destination. Multiple expected timestamps and a timestamp speed associated with the destination are identified. The multiple expected timestamps are compared to the multiple timestamps provided by the destination and the timestamp speed associated with the destination to determine reverse path delay.

In another embodiment, a system for determining reverse path delay associated with data transmission between the system and a destination is provided. The system includes an interface and a processor. The interface is configured to send multiple packets from a source to a destination and receive multiple acknowledgments from the destination. The multiple acknowledgments include multiple timestamps provided by the destination. The processor is configured to identify multiple expected timestamps and a timestamp speed associated with the destination and compare the multiple expected timestamps to the multiple timestamps provided by the destination and the timestamp speed associated with the destination to determine reverse path delay.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

For example, the techniques of the present invention will be described in the context of the transmission control protocol (TCP) stack implemented in an intelligent fibre channel switch. However, it should be noted that the techniques of the present invention can be applied to different variations and flavors of TCP as well as to alternatives to TCP. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. The present invention may be practiced without some or all of these specific details. In other instances, well known process operations have not been described in detail in order not to unnecessarily obscure the present invention.

Furthermore, techniques and mechanisms of the present invention will sometimes be described in singular form for clarity. However, it should be noted that some embodiments can include multiple iterations of a technique or multiple instantiations of a mechanism unless noted otherwise. For example, a processor is used in a variety of contexts. However, it will be appreciated that multiple processors can also be used while remaining within the scope of the present invention.

Round trip time (RTT) is a metric used by a source to determine a variety of network characteristics, including congestion, latency, etc. Tools and utilities such as ping and traceroute measure the time required for a source to receive an acknowledgment from a destination after sending data to the destination. In some examples, an increase in RTT is an indication that one or more links on the path between a source and a destination is congested.

It is relatively straightforward to obtain RTT estimates with precision limited only by the local clock at a source. For example, most processors provide a register that is automatically incremented every clock cycle. Processor and hardware based clocks can be used as very high resolution local clocks. Transmission of data and receipt of a corresponding acknowledgment from a destination are measured using clock cycles. All measurements can be performed in terms of clock cycles, and converted to a conventional time unit only when strictly necessary.

Software based clocks can also be used, although software based clocks do not necessarily have the same precision. Timestamp schemes can be used in conjunction with hardware and software based clocks, although timestamps in the actual packets sent are not required. A source can simply send a packet, record the current time, and calculate the elapsed time once an acknowledgment for the packet is received. Any corresponding response packet is referred to herein as an acknowledgment. A source can obtain RTT measurements frequently and with a considerable degree of accuracy.

However, the techniques of the present invention recognize that measurements such as RTT are not necessarily ideal for determining network characteristics such as congestion. For example, RTT does not isolate delay due to congestion on the forward path from a source to a destination from other causes of delay. The techniques of the present invention recognize that round trip times are sensitive to congestion happening in the forward direction from a source to a destination as well as congestion happening in the reverse direction from the destination back to the source. It is recognized that it would be beneficial to determine forward and reverse components of RTT. In one example, it is preferable to consider only forward direction congestion, since forward direction congestion or forward queuing is what should affect window sizes and transmission rates from a source. Conventional TCP and FastTCP both are sensitive to reverse direction congestion. Reverse direction congestion or reverse queuing should only affect window sizes and transmission rates for data being sent from the connection peer.

Having accurate measurements of forward component delay and reverse component delay would allow more effective control and optimization of network transmissions. For example, a maximum window size as well as a congestion window size are calculated using values associated with forward direction queuing and delay. Forward delay is referred to herein as a value determined by subtracting the reverse delay from the total delay. In some embodiments, forward delay is determined by subtracting the reverse delay and the inherent delay from the total delay.

FIG. 1is a diagrammatic representation showing a network topology that can use the techniques of the present invention. Although one particular network topology is shown, it should be recognized that the techniques of the present invention can be applied to a variety of IP and non-IP networks and network configurations including TCP improvements. In some examples, fibre channel protocols such as Remote Domain Loopback can use some of the techniques of the present invention. According to various embodiments, a storage area network101includes hosts121and123along with storage node125. Storage node125may include a disk or tape array. The storage area network101can also include multiple fibre channel switches. The storage area network101is coupled to an IP network103through a tunneling switch111. Storage area network105includes host127, storage129, as well as other fibre channel switches and tunneling switch113. The tunneling switches111and113allow the formation of a tunnel to transmit storage network data over an IP network103.

According to various embodiments, a tunneling switch111as well as other nodes have forward buffers for holding data for transmission from storage area network101to storage area network105. In some examples, the forward buffers may be full, causing delay at tunneling switch111for data transmitted from storage area network101to storage area network105. In other examples, reverse buffers may be full, causing delay at tunneling switch111for data transmitted from storage area network105to storage area network101. Round trip time is a rough metric that can estimate the amount of congestion in general. However, round trip time can not distinguish between congestion caused at least in part by forward delay and congestion cause by reverse delay. In some instances, only reverse delay may be present, and it would not make sense to slow transmission from a source. However, protocols such as FastTCP use round trip time as a congestion metric and would slow transmission from a source even when the only delay present is reverse delay.

FIG. 2is a diagrammatic representation showing one example of a source node and a destination node. According to various embodiments, a source node201is connected to a destination node203over a network211. The network211may include multiple switches, routers, subnetworks, etc. The source node201includes a clock221. The destination node203includes a clock223and a timestamp mechanism225. The source node201may also include a timestamp mechanism. In one embodiment, both the source node and the destination node insert timestamps into their generated packets, even though the source node may not use its own timestamps to perform precise round trip time measurements.

According to various embodiments, a source node201tracks the time of transmission of a packet. The destination node203receives the packet, inserts a timestamp, and sends the acknowledgment. The source node201then uses the difference between send time and acknowledgment reception time to determine a round trip time and also has the acknowledge timestamp to make additional determinations. If it were possible to globally synchronize and maintain precise global synchronization of clocks221and223, very simple processing would be required to determine forward and reverse delays. However, precisely and accurately synchronization of clocks residing in disparate nodes is difficult, and even though not impossible, at least in principle, it certainly requires collaboration and intention to do so by the two entities involved. In many conventional network implementations, it is only possible to periodically roughly synchronize clocks of distant nodes. The clocks of disparate nodes then can begin to get out of synchronization. Clock drift prevents consistently and accurately synchronized disparate clocks.

According to various embodiments, the techniques of the present invention recognize that global synchronization is difficult and consequently no global timestamp synchronization is required. In fact, it is not required for the destination node203to perform any extra processing beyond its normal functions and timestamp insertion. According to various embodiments, only the source node201receiving timestamp information from destination node203is required to estimate queuing delay in both directions. The destination node203can only measure the round trip time for retransmission timer setup purposes, and may or may not take advantage of timestamp information from the source node201. Of course it is perfectly valid that both nodes operate in a symmetric way, both estimating reverse and forward congestion, without any need to classify the peer as a normal TCP or a TCP with capabilities similar to its own.

The timestamps are normally assigned by the destination node203as a result of an interrupt triggered by a real time clock. For this reason, the timestamp value used by the destination node203changes at points in time that deviate from the precise actual time for several reasons, including variable interrupt latency and drift of the real time clock. The variation in interrupt latency at a network node is difficult to estimate, but it is likely to be much smaller than the timestamp tick. In the case of Remote Domain Loopback, the timestamp is implemented completely in hardware, so the interrupt latency is nearly nonexistent. Only the drift of the real time clock becomes a factor.

The real time clock can be commonly expected to drift less than50parts per million. The destination node203sends packets to the source node201at arbitrary instances in time, but uses the current timestamp that has been updated by hardware or a software interrupt routine. It is not assumed that the timestamp tick is the same between node201and node203(in fact S does not use its own timestamps to perform the reverse delay estimation). It is recognized that almost all TCP implementations use a tick of 10 ms or, less likely, 1 ms.

To determine components of round trip time, the source node201initially observes timestamps in packets arriving from the destination node in order to estimate the speed at which node D updates its timestamp. The speed can be determined using the following equation:

where ts_val is a timestamp received at time t; and

ts0is a timestamp received at time t0.

By observing the remote end for a sufficiently long period of time, any desired precision can be achieved. However, to be able to perform the delay estimation after a reasonably short time (on the order of seconds) a more pragmatic method can be used. According to various embodiments, it is sufficient to observe the remote timestamp for a few seconds to be able to disambiguate timestamp speed possibilities, such as the 1 ms and 10 ms cases. If the estimated timestamp speed is reasonably close to one of the expected speeds, the algorithm is activated. Otherwise, it is disabled. Of course, in some instances, the problem is trivial because it is appreciated that all the network nodes employ the same timestamp tick.

All the following mathematical formulas are expressed for clarity using conventional arithmetic, however it should be noted that timestamps, like sequence numbers, are integer numbers of finite size. TCP, for example, employs 32 bit timestamps. For this reason those skilled in the art will appreciate that operation and comparisons can be performed using modular arithmetic.

Once the remote timestamp speed is known, it is possible to estimate the timestamp of an incoming packet using the following formula:
ts—est←ts0+ts_speed(t−t0)  (Equation 2)

where ts_est is the predicted timestamp;

ts0is a timestamp received at time to; and

t is the current time.

The incoming timestamp (ts_val) is compared to the integer part of the predicted timestamp. The predicted timestamp could be before, after or the same as the incoming timestamp. According to various embodiments, if the integer part of ts_est and ts_val are the same no evidence of reverse delay is present, since the remote end is expected to use the same timestamp value for the duration of one tick.

FIG. 3is a diagrammatic representation showing timestamp estimates graphed with timestamp values showing no delay. The x-axis shows time301while the y-axis shows timestamps305. After a period of one tick307, it is expected that a timestamp will be received from the destination node. Timestamps may arrive readily and steadily at periodic intervals. The exact send time of each packet containing a timestamp is determined by the peer and is in general not predictable. However the value of the timestamp put in each packet is predictable. One particular time stamp arrives at time303. In this example, the timestamp expected is the timestamp value after two ticks. The timestamp value received is the timestamp value after two ticks. No delay is evident. However, if the timestamp value is not received until later due to reverse delay, the expected timestamp at that point would be the timestamp value after say three or four ticks. If the received timestamp value is still only the timestamp value after two ticks, delay is evident. That is, the ts_val is smaller than the ts_est. If the incoming timestamp is smaller than the predicted timestamp, it is interpreted as evidence of reverse delay. The reverse delay sample can be calculated by using the following formula:

where ts_est is the predicted timestamp;

ts_val is the timestamp value; and

ts_speed is the timestamp speed.

FIG. 4is a diagrammatic representation showing timestamp estimates graphed with timestamp values showing delay. The x-axis shows time401while the y-axis shows timestamps405. After a period of one tick407, it is expected that a timestamp will be received from the destination node. Timestamps may arrive readily and steadily at periodic intervals. One particular time stamp arrives at time403. The timestamp estimate at time403is less than the timestamp value received. In this example, the timestamp expected is the timestamp value after three ticks. The timestamp value received is the timestamp value after one tick. Delay in the amount of Δt is evident. That is, the ts_val is smaller than the ts_est. If the incoming timestamp is smaller than the predicted timestamp, it is interpreted as evidence of reverse delay. The delay sample can be computed graphically. However, the delay is merely one sample of possible delay.

It should be noted that assuming random packet departure times, even in case of constant reverse delay the sample values will not be constant:

where tick is the clock tick period;

Δt is the reverse delay sample; and

reverse_delay is the actual reverse delay;

To obtain an accurate reverse delay estimation, the maximum Δt is computed over time on the order of several timestamp ticks. According to various embodiments, the max is computed over the last round trip time, and is then fed to a first order filter to obtain the average reverse delay. In order to reduce the number of divisions performed, an optimization is possible by calculating using the following equations:

where ts_est is the predicted timestamp;

avg_rev_delay is the average reverse delay;

max Δt is the maximum delay;

max Δt stamp is the maximum time stamp;

ts_val is the timestamp value; and

ts_speed is the timestamp speed.

The maximum is scaled only once per RTT, before feeding it to the averaging filter. The estimated delay is actually the total reverse delay minus the constant (ignoring routing changes) propagation delay. If ts_val, the incoming timestamp, is bigger than the estimated timestamp, then some extra reverse delay was present at the time of the first recorded timestamp, and only now the delay was reduced enough to notice the timestamp discrepancy. In this case the initial timestamp is adjusted, so that future timestamp predictions will be correct. The initial timestamp can be adjusted using the following equation:
ts0←ts—val−ts_speed(t−t0)
or
ts0←ts—val−ts—est(Equation 8)

where ts_speed is the timestamp speed;

ts0is the initial timestamp;

ts_val is the received timestamp value; and

ts_est is the predicted timestamp;

FIG. 5is a diagrammatic representation showing initial timestamp estimates and newly determined timestamp estimates. The x-axis shows time501while the y-axis shows timestamps505. At a particular time503, an actual ts_val is determined. The ts_est subtracted from the ts_val is used to determine a new initial timestamp or ts0.

It is recognized that one of the difficulties in estimating forward and reverse delays is that ts_speed may not be calculated precisely. The variable ts_speed is estimated by observing the remote timestamp ts_val. According to various embodiments, it is important that the estimated ts_speed be smaller than the actual speed, or the Δt value obtained through Equation 3 will be monotonically increasing even in absence of any reverse delay.

FIG. 6shows a timestamp speed uncertainty cone associated with inaccuracies in estimating ts_speed. Overestimating ts_speed is shown at601. Underestimating ts_speed is shown at605. An ideal measurement of ts_speed is shown at603. It is recognized that a constantly increasing Δt value is undesirable. According to various embodiments, the techniques of the present invention recognize that it is beneficial to underestimate the ts_speed value. In some embodiments, the ts_speed value is adjusted using a timestamp speed reduction factor. In some embodiments, the amount of uncertainty is assumed to be less than 50 ppm, so it is sufficient to use a timestamp speed reduction factor of a fraction of the estimated ts_speed bigger than 50/106to avoid the risk of overestimation.

where ts_speed is the timestamp speed; and

η is the timestamp speed reduction factor.

This effectively bends downwards, below the ideal line, the ts_speed uncertainty cone. According to various embodiments, the timestamp speed reduction factor is chosen to be only slightly bigger than the constraint in Equation 8, in order to be able to actually measure the reverse delay. Using an excessive correction factor would result in the estimated timestamp mostly likely being smaller than the received timestamp and cause underestimation errors. The reverse delay is unlikely to be constant in actual networks. During periods of low reverse delay, the incoming timestamp can be larger than the predicted one. Application of Equation 8 realigns the variables, so that on the next period a higher reverse delay is properly detected. In case of long lasting connections it is possible to estimate ts_speed with a precision that is better than the assumed 50 ppm. In this case it is possible to adjust the timestamp speed reduction factor accordingly. At the cost of additional calculations, it is possible to perform multiple estimates with different timestamp reduction factors concurrently and choose the smallest reduction factor for which no long term increase in the reverse delay is evident.

According to various embodiments, if the initial estimate of ts_speed is 100 ticks/s, for example, observing timestamps for more than 200 s results in a precision better than 50 ppm. In some implementations, the initial estimate is adjusted by observing the timestamp increase over periods of 10 minutes and averaging the corresponding samples.

The techniques of the present invention can be implemented on a variety of devices such as hosts and switches. In some examples, the reverse path delay estimation techniques can be implemented at any source originating traffic or destination receiving traffic. In other examples, the techniques of the present invention can also be implemented at tunneling switches used to transmit storage application data over IP networks.

FIG. 7is a diagrammatic representation of one example of a fibre channel switch that can be used to implement techniques of the present invention. Although one particular configuration will be described, it should be noted that a wide variety of switch and router configurations are available. The tunneling switch701may include one or more supervisors711. According to various embodiments, the supervisor711has its own processor, memory, and storage resources.

Line cards703,705, and707can communicate with an active supervisor711through interface circuitry783,785, and787and the backplane715. According to various embodiments, each line card includes a plurality of ports that can act as either input ports or output ports for communication with external fibre channel network entities751and753. The backplane715can provide a communications channel for all traffic between line cards and supervisors. Individual line cards703and707can also be coupled to external fibre channel network entities751and753through fibre channel ports743and747.

External fibre channel network entities751and753can be nodes such as other fibre channel switches, disks, RAIDS, tape libraries, or servers. It should be noted that the switch can support any number of line cards and supervisors. In the embodiment shown, only a single supervisor is connected to the backplane715and the single supervisor communicates with many different line cards. The active supervisor711may be configured or designed to run a plurality of applications such as routing, domain manager, system manager, and utility applications.

According to one embodiment, a routing application is configured to populate hardware forwarding tables used to direct frames towards their intended destination by choosing the appropriate output port and next hop. A utility application can be configured to track the number of buffers and the number of credits used. A domain manager application can be used to assign domains in the fibre channel storage area network. Various supervisor applications may also be configured to provide functionality such as flow control, credit management, and quality of service (QoS) functionality for various fibre channel protocol layers.

According to various embodiments, the switch also includes line cards775and777with IP interfaces765and767. In one example, the IP port765is coupled to an external IP network entity755. The line cards775and777can also be coupled to the backplane715through interface circuitry795and797.

According to various embodiments, the switch can have a single IP port and a single fibre channel port. In one embodiment, two fibre channel switches used to form an FCIP tunnel each have one fibre channel line card and one IP line card. Each fibre channel line card connects to an external fibre channel network entity and each IP line card connects to a shared IP network.

In addition, although an exemplary switch is described, the above-described embodiments may be implemented in a variety of network devices (e.g., servers) as well as in a variety of mediums. For instance, instructions and data for implementing the above-described invention may be stored on a disk drive, a hard drive, a floppy disk, a server computer, or a remotely networked computer. Accordingly, the present embodiments are to be considered as illustrative and not restrictive, and the invention is not to be limited to the details given herein, but may be modified within the scope and equivalents of the appended claims.

While the invention has been particularly shown and described with reference to specific embodiments thereof, it will be understood by those skilled in the art that changes in the form and details of the disclosed embodiments may be made without departing from the spirit or scope of the invention. For example, embodiments of the present invention may be employed with a variety of network protocols and architectures. It is therefore intended that the invention be interpreted to include all variations and equivalents that fall within the true spirit and scope of the present invention.