Topics in High-Performance Messaging

2.1. TCP Latency Behavior

Broadly speaking, the way that TCP does rate control makes it unsuitable for latency-sensitive applications. (See Section 3 for a contrast with other ways of doing rate control.) A TCP receiver will add latency whenever packet loss or network routing causes packets to arrive out of order. A TCP sender will add latency when going faster would cause network congestion or when it would be sending faster than the receiver can process the incoming data.

2.2. TCP Receiver-Side Latency

TCP only supports one delivery model: in-order delivery. This means that a TCP receiver must add latency whenever data arrives out of order so as to put the data back in order. TCP also often unnecessarily retransmits data that was already successfully received after out-of-order data is received.

There are two main causes of out-of-order data reception. The most frequent cause is packet loss, either at the physical or network-layer. Another, less frequent cause of out-of-order data reception is that packets can take different paths through the network; one path have more latency than another. In either case, TCP inserts latency to put the packets back in order, as illustrated in Figure 1.

Note that the receiving application cannot receive packet 3 until (the retransmitted) packet 2 has arrived. The receiving TCP stack adds latency while waiting for the successful arrival of packet 2 before packet 3 can be delivered.

Contrast this with the case where a transport with an arrival-order delivery model is used as shown in Figure 2.

Note that packet 3 is delivered to the application layer as soon as it arrives.

TCP cannot provide arrival order delivery, but UDP can. However, simple UDP is awkward for many applications because it provides no reliability in delivery. In the above example, it becomes the application's responsibility to detect packet 2's loss and request its retransmission.

With this in mind, we created a reliable multicast protocol called LBT-RM. It offers lower latency than TCP since it uses UDP and arrival order delivery, but it can also provide reliability through the built-in loss detection and retransmission logic. Of course, each message delivered by LBT-RM has a sequence number so that the application has message sequencing information available if needed.

If you're curious about how much latency is being added by the TCP in-order delivery model, you can often get a hint by looking at output from the netstat -s command. Look for statistics from TCP. In particular, look for out-of-order packets received and total packets received. Divide these two numbers to get a percentage of packets that are being delayed by TCP in-order delivery.

For example, consider this output from netstat -s.

tcp:
. . .
      2854 packets received
. . .
          172 out-of-order packets (151915 bytes)

The above example statistics show that about 6% of all incoming TCP packets are being delayed due the requirement of in-order delivery (this is pretty high; we hope that you are not experiencing this degree of packet loss). Be aware that netstat output tends to vary quite a bit from operating system to operating system, so your output may look quite different from the above.

2.3. TCP Sender-Side Latency

TCP is designed to send as fast as possible while maintaining equal bandwidth sharing with all other TCP streams and reliable delivery. A TCP sender may slow down for two reasons:

1. Going faster would cause network congestion.

2. Going faster would send data faster than the receiver can process it.

If you were to liken TCP to an automobile driver, you'd have to call TCP the most lead-footed yet considerate driver on the road. As long as the road ahead is clear, TCP will drive as fast as possible. But as soon as other traffic appears on the road, TCP will slow down so that other drivers (i.e. other TCP streams) have a equal shot at using the road too. The technical term for this behavior is congestion control. When a network becomes congested, the TCP algorithms insure that the pain is felt equally by all active TCP streams, which is exactly the behavior you want if your primary concern is bandwidth sharing and network stability. However, if you have a latency-sensitive application, you would prefer that it get priority, leaving the other less-critical applications to divide up the remaining bandwidth. That is, you would like to be able to add flashing lights and a siren to your latency-sensitive applications.

It's important to note that TCP uses two different mechanisms to measure congestion: round-trip time (RTT) and packet loss. (See Myth: All Packet Loss is Bad for details.) Sticking with the automobile analogy, an increase in RTT causes TCP to take its foot off the gas to coast while packet loss causes it to step on the brakes. TCP cuts its transmission rate by 1/2 every time it detects loss. This can add additional latency after the original loss. Even small amounts of loss can drastically cut TCP throughput.

TCP also makes sure that the sender does not send data faster than the receiver can process it. A certain amount of buffer space is allocated on the receiver, and when that buffer fills, the sender is blocked from sending more. The technical term for this behavior is flow control. TCP's philosophy is "better late than never". Many latency-sensitive applications prefer the "better never than late" philosophy. At the very least, a slow, possibly problematic receiver should not cause unnecessary latency with other receivers. Obviously, there needs to be enough buffer space to handle normal periods of traffic bursts and temporary receiver slow-downs, but if/when those buffers do fill up, it's better to drop data than block the sender.

2.4. TCP Latency Recommendations

It's probably best to avoid using TCP for latency-sensitive applications. As an alternative, consider protocols that slow down a sender only when required for network stability. For example, the Ultra Messaging product offers protocols like LBT-RM that have been designed specifically for latency-sensitive applications. Such protocols allow reliable yet latency-bounded delivery without sacrificing network stability.

When TCP cannot be avoided, it's probably best to:

• Use clever buffering and non-blocking sockets with TCP to drop data for congested TCP connections when data loss is preferable over latency. Ultra Messaging uses such buffering for its source-paced TCP feature.

• Consider disabling Nagle's algorithm with the TCP_NODELAY option to setsockopt(). Although this may produce decreased latency, it often does so at the expense of efficiency.

• Route latency-sensitive TCP traffic over a dedicated network where congestion is minimized or eliminated.

• Keep kernel socket buffers to a minimum so that latency is not added as data is stored in such buffers. TCP windows substantially larger than the bandwidth-delay product (BDP) for the network will not increase TCP throughput but they can add latency.

3.1. The Crybaby Receiver Problem

Often, the whole group suffers due to the problems of one member. In extreme cases, the throughput for the group falls to zero because resources that the group shares are dedicated to the needs of one or a few members. Examples of shared resources include the sender's CPU, memory, and network bandwidth. This phenomenon is sometimes called the "crybaby receiver problem" because the cries (e.g. retransmission requests) from one receiver dominate the attention of the parent (the sender).

The chance of encountering a crybaby receiver problem increases as the number of receivers in the group increases. Odds are that at least one receiver will be having difficulty keeping up if the group is large enough.

As long as all receivers in the group are best served by the sender running at the same speed, there is no conflict within the group. Scenarios such as crybaby receivers often present a conflict between what's best for a few members and what's best for the majority. Robust systems will have policies for dealing with the apparent conflict and consistently resolving it.

3.2. Group Rate Control Policies

There are three rate control policies that a sender can use for dealing with such conflict within a group. Two are extremes and the third is a middle ground.

3.3. Group Rate Control Consequences

The extreme policies have potentially dire consequences for many applications. For example, neither is ideal for market data and other types of latency-sensitive data.

Extreme 2 is the policy most often used. Successful use of it requires that networks and receivers be provisioned to keep up with the fastest rate that might be convenient for the sender. Such policies often leave little bandwidth for TCP traffic and can be vulnerable to "NAK storms" and other maladies which can destabilize the entire network.

Extreme 1 is appropriate only for transactional applications where it's more important for the group to stay in sync than for the group to have low latency.

The middle ground policy is ideal for many latency-sensitive applications such as transport of financial market data. It allows for low-latency reliable delivery while maintaining the stability of the network. No amount of overload can cause a "NAK storm" or other network outage when the policy is established with knowledge of the capabilities of the network.

3.4. Policy Selection

The need to establish a group rate control policy is often not apparent to those accustomed to dealing with two-party communication (e.g. TCP). When there are only two parties communicating, one policy is commonly used: the sender goes as fast as it can without going faster than the receiver or being unfair to others on the network. (See Section 2 for details.) This is the only sensible policy for applications that can withstand some latency and cannot withstand data loss. With two-party communication using TCP, it's the only policy choice you have. However, group communication with one sender and many receivers opens up all of the policy possibilities mentioned above.

Some messaging systems support only one policy and hence require no policy configuration. Others may allow a choice of policy. Any middle ground policy will need to be configured to establish the boundaries within which it should operate.

The best results are obtained when the specific needs of a messaging application have been considered and the messaging system has been configured to reflect them. A messaging system has no means to automatically select from among the available group rate control policies. Human judgment is required.

3.5. Group Rate Control Recommendations

A group rate control policy should be chosen to match the needs of the application serving the group. The choice is often made by weighing the benefits of low latency against reliable delivery. These benefits have to be considered for individuals within the group and for the group as a whole.

In some applications, members of the group benefit from the presence of other members. In these applications, the group benefit from reliable reception among all receivers may outweigh the pain of added latency or limited group throughput. Consider a group of servers that share the load from a common set of clients. Assume that the servers have to stay synchronized with a stream of messages to be able to answer client queries. If one server leaves the group because it lost some messages, the clients it was serving would move to the remaining servers. This could lead to a domino effect where a traffic burst caused the slowest server to drop from the group which in turn increased the load on the other servers causing them to fail in turn as well. Clearly in a situation like this, it's better for the whole group of servers to slow down a bit during a traffic peak so that even the slowest among them can keep up without loss. The appropriate group rate control policy for such an application is Extreme 1 (see Section 3.2.1).

Other applications see no incremental benefit for the group if all members experience reliable reception. Consider a group of independent traders who all subscribe to a market data stream. Traders who can keep up with the rate convenient for the sender do not want the sender to slow down for those who can't. Extreme 2 (see Section 3.2.2) is probably the appropriate policy for an application like this. However, care must be taken to prevent the sender from going faster than even the fastest trader as that often leads to NAK storms from which there is no recovery.

The Ultra Messaging team recommends a careful analysis of the policies that are best for the group using an application and for individual members of the group. The rate control policy best suited to your application will generally emerge from such an analysis. We have found that it is possible to build stable, low-latency messaging systems with careful network design and a messaging layer like Ultra Messaging that supports a middle ground policy through the use of rate controls.

3.6. Group Rate Control and Transport Protocols

Once you've chosen a group rate control policy appropriate for your application, it's important to chose a transport protocol that can implement your chosen policy. Some transport protocols offer only the extreme policies while others allow parameters to be set to implement a middle ground policy.

UDP provides no rate control at all, so it follows group policy Extreme 2 above (see Section 3.2.2).

TCP doesn't operate naturally as a group communication protocol since it only supports unicast addressing. However, when TCP is used to send copies of the same data stream to more than one receiver, all of the group rate control issues discussed above are present. TCP's inherent flow control feature follows group policy Extreme 1 described above (see Section 3.2.1). If the sender is willing to use non-blocking I/O and manage buffering, then Extreme 2 and middle ground policies can be implemented to some degree.

Some reliable multicast transport protocols provide no rate control at all (e.g. TIBCO Rendezvous), some provide only a fixed maximum rate limit (e.g. PGM), and some provide separate rate controls for initial data transmission and retransmission (e.g. LBT-RM from Ultra Messaging). See Section 15 for details.

7.1. Function of UDP Buffering

UDP packets may arrive in bursts because they were sent rapidly or because they were bunched together by the normal buffering action of network switches and routers.

Similarly, UDP packets may be consumed rapidly when CPU time is available to run the consuming application. Or they may be consumed slowly because CPU time is being used to run other processes.

UDP receive buffering serves to match the arrival rate of UDP packets (or "datagrams") with their consumption rate by an application program. Of course, buffering cannot help cases where the long-term average send rate exceeds the average receive rate.

7.2. Importance of UDP Buffering

UDP receive buffering is done in the operating system kernel. Typically the kernel allocates a fixed-size buffer for each socket receiving UDP. Buffer space is consumed for every UDP packet that has arrived but has not yet been delivered to the consuming application. Unused space is generally unavailable for other purposes because it must be readily available for the possible arrival of more packets. See Section 7.4 for a further explanation.

If a UDP packet arrives for a socket with a full buffer, it is discarded by the kernel and a counter is incremented. See Section 8.9 for information on detecting UDP loss. A common myth is that all UDP loss is bad. (See Myth: All Packet Loss is Bad.) Even if it's not all bad, UDP loss does have its consequences. (See Section 8.3.)

7.3. Kernel and User Mode Roles in UDP Buffering

The memory required for the kernel to do UDP buffering is a scarce resource that the kernel tries to allocate wisely. (See Section 7.4 for more on the rationale.) Applications expecting low-volume UDP traffic or those expecting low CPU scheduling latency (see Section 17.6) need not consume very much of this scarce resource. Applications expecting high-volume UDP traffic or those expecting a high CPU scheduling latency may be justified in consuming more UDP buffer space than others.

Typically, the kernel allocates a modest-size buffer when a UDP socket is created. This is generally adequate for less-demanding applications. Applications requiring a larger UDP receive buffer can request it with the system call setsockopt(...SO_RCVBUF...).

Explicit configuration of the application may be required before it will request a larger UDP buffer. (For UM, this is the context option transport_lbtrm_receiver_socket_buffer.)

The kernel configuration will allow such requests to succeed only up to a set size limit. This limit may often be increased by changing the kernel configuration. See Section 8.8 for information on setting kernel UDP buffer limits.

Hence two steps are often required to get adequate UDP buffer space:

• Change the kernel configuration to increase the limit on the largest UDP buffer allocation that it will allow.

• Change the application to request a larger UDP buffer.

7.4. Unix Kernel UDP Buffer Limit Rationale

It may seem to some that the default maximum UDP buffer size on many Unix kernels is a bit stingy. Understanding the rationale behind these limits may help.

UDP is typically used for low-volume query/response work (e.g. DNS, NTP, etc.). The kernel default limits assume that UDP will be used in this way.

UDP kernel buffer space is allocated from physical memory for the exclusive use of one process. The kernel tries to make sure that one process can't starve others for physical memory by allocating large UDP buffers that exhaust all the physical memory on a machine.

To some degree, the meager default limits are a legacy from the days when 4 MB was a lot of physical memory. In these days when several gigabytes of physical memory space is common, such small default limits seem particularly stingy.

7.5. UDP Buffering and CPU Scheduling Latency

For the lowest-possible latency, the operating system would run a process wishing to receive a UDP packet as soon as the packet arrives. In practice, the operating system may allow other processes to finish using their CPU time slice first. It may also seek to improve efficiency by accumulating several UDP packets before running the application. We will call the time that elapses between when a UDP packet arrives and when the consuming application gets to run on a CPU the CPU scheduling latency. See Section 17.6 for more information. UDP buffer space fills during CPU scheduling latency and empties when the consuming process runs on a CPU. CPU scheduling latency plays a key role optimal UDP buffer sizing. See Section 8.1 for more information.

7.6. TCP Receive Buffering vs. UDP Receive Buffering

The operating system kernel automatically allocates TCP receive buffer space based on policy settings, available memory, and other factors. TCP in the sending kernel continuously monitors available receive buffer space in the receiving kernel. When a TCP receive buffer fills up, the sending kernel prevents the sending application from using CPU time to generate any more data for the connection. This behavior is called "flow control." In a nutshell, it prevents the receiver buffer space from overflowing by adding latency at the sender. We say that the speed of a TCP sender is "receiver-paced" because the sending application is prevented from sending when data cannot be delivered to the receiving application.

The OS kernel also allocates UDP receive buffer space based on policy settings. However, UDP senders do not monitor available UDP receive buffer space in the receiving kernel. UDP receivers simply discard incoming packets once all available buffer space is exhausted. We say that the speed of a UDP sender is "sender-paced" because the sending application can send whenever it wants without regard to available buffer space in the receiving kernel.

The default TCP buffer settings are generally adequate and usually require adjustment only for unusual network parameters or performance goals.

The appropriate size for an application's UDP receive buffer is influenced by factors that cannot be known when operating system default policies are established. Further, there is nothing the operating system can do to automatically discover the appropriate size. An application may know that it would benefit from a UDP receive buffer larger or smaller than the default used by the operating system. It can request a non-default UDP buffer size from the operating system, but the request may not be granted due to a policy limit. See Section 7.4 for reasons behind such policy limits. Operating system policies may have to be adjusted to successfully run high-performance UDP applications like UM. See Section 8.8 to change operating system policies.

8.1. Optimal UDP Buffer Sizing

UDP buffer sizes should be large enough to allow an application to endure the normal variance in CPU scheduling latency without suffering packet loss. They should also be small enough to prevent the application from having to read through excessively old data following an unusual spike in CPU scheduling latency.

8.2. UDP Buffer Space Too Small: Consequences

Too little UDP buffer space causes the operating system kernel to discard UDP packets. The resulting packet loss has consequences described below.

The kernel often keeps counts of UDP packets received and lost. See Section 8.9 for information on detecting UDP loss due to UDP buffer space overflow. A common myth is that all UDP loss is bad (see Myth: All Packet Loss is Bad).

8.3. UDP Loss: Consequences

In most cases, it's the secondary effects of UDP loss that matter most. That is, it's the reaction to the loss that has material consequences more so than the loss itself. Note that the consequences discussed here are independent of the cause of the loss. Inadequate UDP receive buffering is just one of the more common causes we've encountered deploying UM.

Consider these areas when assessing the consequences of UDP loss:

• Latency--The time that passes between the initial transmission of a UDP packet and the eventual successful reception of a retransmission is latency that could have been avoided were it not for the intervening loss.

• Bandwidth--UDP loss usually results in requests for retransmission, unless more up-to-date information is expected soon (e.g. in the case of stock quote updates). Bandwidth used for retransmissions may become significant, especially in cases where there is a large amount of loss or a large number of receivers experiencing loss. See Section 15 for more information on multicast retransmissions.

• CPU Time--UDP loss causes the receiver to use CPU time to detect the loss, request one or more retransmissions, and perform the repair. Note that efficiently dealing with loss among a group of receivers requires the use of many timers, often of short-duration. Scheduling and processing such timers generally requires CPU time in both the operating system kernel ("system time") and in the application receiving UDP ("user time"). Additional CPU time is required to switch between kernel and user modes.

  On the sender, CPU time is used to process retransmission requests and to send retransmissions as appropriate. As on the receiver, many timers are required for efficient retransmission processing, thus requiring many switches between kernel and user modes.

• Memory--UDP receivers that can only process data in the order that it was initially sent must allocate memory while waiting for retransmissions to arrive. UDP loss causes such receivers to receive data in an order different than that used by the sender. Memory is used to restore the order in which it was initially sent.

  Even UDP receivers that can process UDP packets in the order they arrive may not be able to tolerate duplication of packets. Such receivers must allocate memory to track which packets have been successfully processed and which have not.

  UDP senders interested in reliable reception by their receivers must allocate memory to retain UDP packets after their initial transmission. Retained packets are used to fill retransmission requests.

8.4. UDP Buffer Space Too Large: Consequences

Even though too little UDP buffer space is definitely bad and more is generally better, it is still possible to have too much of a good thing. Perhaps the two most significant consequences of too much UDP buffer space are slower recovery from loss and physical memory usage. Each of these is discussed in turn below.

• Slower Recovery--To best understand the consequences of too much UDP buffer space, consider a stream of packets that regularly updates the current value of a rapidly-changing variable in every tenth packet. Why buffer more than ten packets? Doing so would only increase the number of stale packets that must be discarded at the application layer. Given a data stream like this, it's generally better to configure a ten-packet buffer in the kernel so that no more than ten stale packets have to be read by the application before a return to fresh ones from the stream.

  It's often counter-intuitive, but excessive UDP buffering can actually increase the recovery time following a large packet loss event. UDP receive buffers should be sized to match the latency budget allocated for CPU scheduling latency with knowledge of expected data rates. See Section 16 for more information on latency budgets. See Section 8.6 for a UDP buffer sizing equation.

• Physical Memory Usage--It is possible to exhaust available physical memory with UDP buffer space. Requesting a UDP receive buffer of 32 MB and then invoking ten receiver applications uses 320 MB of physical memory. See Section 7.4 for more information.

8.5. UDP Buffer Size Equations: Latency

Assuming that an average rate is known for a UDP data stream, the amount of latency that would be added by a full UDP receive buffer can be computed as:

Max Latency = Buffer Size / Average Rate

8.6. UDP Buffer Size Equations: Buffer Size

Assuming that an average rate is known for a UDP data stream, the buffer size needed to avoid loss a given worst case CPU scheduling latency can be computed as:

Buffer Size = Max Latency * Average Rate

8.7. UDP Buffer Kernel Defaults

The kernel variable that limits the maximum size allowed for a UDP receive buffer has different names and default values by kernel given in the following table:

8.8. Setting Kernel UDP Buffer Limits

The examples in this table give the commands needed to set the kernel UDP buffer limit to 8 MB. Root privilege is required to execute these commands.

8.9. Detecting UDP Loss

Interpreting the output of netstat is important in detecting UDP loss. Unfortunately, the output varies considerably from one flavor of Unix to another. Hence we can't give one set of instructions that will work with all flavors.

For each Unix flavor, we tested under normal conditions and then under conditions forcing UDP loss while keeping a close eye on the output of netstat -s before and after the tests. This revealed the statistics that appeared to have a relationship with UDP packet loss. Output from Solaris and FreeBSD netstat was the most intuitive; Linux and AIX much less so. Following sections give the command we used and highlight the important output for detecting UDP loss.

IPv4:
      udpInOverflows      = 82427

Udp:
      38799 packet receive errors

ip:
      77070 fragments dropped (dup or out of space)

udp:
      6343 dropped due to full socket buffers

12.1. Solution: Increase TTL

At the risk of stating the obvious, we have to say that one potential solution is to configure all multicast sources so that they will always have a TTL larger than the network diameter and hence will never hit this problem. However, this is best thought of as voluntary compliance by multicast sources rather than an administrative prohibition. A common goal is to establish multicast connectivity within one group of networks while preventing it outside those nets. Source TTL settings alone are often inadequate for meeting such goals so we present other methods below.

12.2. Solution: IP Multicast TTL-Threshold

The Cisco IOS command ip multicast ttl-threshold looks like it might help, but it forces all multicast traffic leaving the interface to be routed via the mcache. This may be better than having the TTL expire and the traffic be process switched, but ip multicast boundary is probably a better solution (see Section 12.3).

12.3. Solution: IP Multicast Boundary

The Cisco IOS command ip multicast boundary can be used to establish a layer-2 boundary that multicast will not cross. This example configuration shows how traffic outside the range 239.192.0.0/16 can be prevented from ever passing passing up to layer-3 processing:

interface Vlan13
 ip multicast boundary 57
. . .
access-list 57 permit 239.192.0.0 0.0.255.255
access-list 57 deny any

12.4. Solution: Hardware Rate Limit

Recent versions (PFC3B or later) of the Supervisor 720 module have hardware that can be used to limit how often the CPU will be interrupted by packets with expiring TTL. This example shows how to enable the hardware rate limiter and check its operation:

Router#mls rate-limit all ttl-failure 500 100
Router#show mls rate-limit
  Sharing Codes: S - static, D - dynamic
  Codes dynamic sharing: H - owner (head) of the group, g - guest of the group

    Rate Limiter Type       Status     Packets/s   Burst  Sharing
  ---------------------   ----------   ---------   -----  -------
. . .
            TTL FAILURE   On                 500     100  Not sharing
. . .
Router#

15.1. Retransmission Cost/Benefit

It's important to note how small group loss differs from the case where the packet loss is experienced by many receivers in the group. When loss is widespread, there is widespread benefit from the consequent multicast retransmissions. When loss is isolated to one or a few receivers, they benefit from the retransmissions, but the other receivers may experience latency while the sender retransmits. In the common case where there is a limited amount of network bandwidth between the sender and receivers, the bandwidth needed for retransmissions must be subtracted from that available for new data transmission. For example, the LBT-RM reliable multicast protocol within Ultra Messaging always prioritizes retransmissions ahead of new data, so they add a small amount of latency when there there is new data waiting to be sent to all members of the group.

15.2. Multicast Retransmission Control Techniques

Reliable delivery to a multicast group in the face of loss involves a trade off between throughput/latency and reliable reception for all members. Ideally, administrative policy should establish the boundaries within which reliability will be maintained. A simple and effective way to establish a boundary is to limit the amount of bandwidth that will be used for retransmissions. Establishing such a boundary can effectively defend a group of receivers against an "attack" from a crybaby receiver. No matter how much loss is experienced across the receiver set, the sender will limit the retransmission rate to be within the boundary set by administrative policy.

Note that limiting the retransmission request rate on receivers might be better than doing nothing, but it's not as effective as limiting the bandwidth available for retransmission. For example, if a large number of receivers experience loss, then the combined retransmission request rate could be unacceptably high, even if each individual receiver limits its own retransmission request rate.

15.3. Avoiding Multicast Receiver Loss

Even if retransmission rates have been limited, it is still important to identify the cause of isolated receiver loss problems and repair them. Usually, such loss is caused by overrunning NIC buffers or UDP socket buffers. Assuming that the sender cannot be slowed down, receiver loss can generally avoided by one or more of these means:

• Increasing NIC ring buffer size (e.g. use a brand name, server-class NIC instead of a generic, workstation-class NIC, also see Section 18.3)

• Decreasing the OS NIC interrupt service latency (e.g. decrease CPU workload or add more CPUs to a multi-CPU machine)

• Increasing UDP socket buffer size (see Section 8.8)

• Decreasing the OS process context switching time (e.g. decrease CPU workload or add more CPUs to a multi-CPU machine)

Establishing a bandwidth limit on retransmissions will not help an isolated receiver experiencing loss, but it can be a critical factor in ensuring that one receiver does not take down the whole group with excessive retransmission requests. Retransmission rate limits are likely to increase the number of unrecoverable losses on receivers experiencing loss. Still, it's generally best for the group to first establish a defense against future crybaby receivers before working to fix any individual receiver problems.

17.1. Intermediaries

Many messaging systems contain components that add little value to the overall system. The time taken for communication between these components often adds up to a substantial fraction of the total system latency. To eliminate this extra and unnecessary overhead, and therefore provide the best possible performance (both throughput and latency) in any given network and application environment, we adopted a "no daemons" design philosophy in our Ultra Messaging product.

17.2. Garbage Collection

One of the compelling benefits of managed languages like Java and C# is that programmers need not worry about tracking reference counts and freeing memory occupied by unused objects. This pushes the burden of reference counting to the language run-time code (Java's JVM or C#'s CLR). A common source of intermittent but significant latency for messaging systems involving managed languages is garbage collection in the language run-time code.

The latency happens when the run-time systems stops execution of all user code while counting references. More modern run-time systems allow execution even while garbage collection is happening (e.g. mark and sweep techniques).

Garbage collection latency generally happens infrequently, but depending on the system, it can be significant when it does happen. It impacts all messages that arrive during collection and those that are queued as a result of the latency.

17.3. Retransmissions

It is common for messaging applications to expect loss-free message delivery even if the network layer drops packets. This implies that either the messaging layer itself or a transport layer protocol under it must repair the loss. The time taken to discover the loss, request retransmission, and the arrival of the retransmission all contribute to retransmission latency. See Section 15 for more information on multicast retransmissions.

Retransmission latency typically only happens when physical- or network-layer loss requires retransmission. This is infrequent in well-managed networks. In the event that retransmission is requested by a receiver detecting loss, the fixed component of retransmission latency is the RTT from source to receiver while the remainder is variable.

17.4. Reordering

Messages may arrive out of order at a receiver due to network loss or simply because the network has multiple paths allowing some messages faster paths than others. When a message arrives ahead of some that were sent before it, it can be held until its predecessors also arrive or may be delivered immediately. The holding process allows applications to receive messages in order even when they arrive out of order, but it adds a reordering latency. Ultra Messaging offers an arrival-order delivery feature that avoids this delay, but TCP offers no such option. See Section 2 for a deeper discussion of reordering latency in TCP.

Note that in the case where a lost message cannot be recovered, the reordering latency can become very large. Following loss, TCP uses an exponential retransmission algorithm which can lead to latencies measured in minutes. Bounded-reliability protocols like LBT-RM and LBT-RU allow control over the timers that detect unrecoverable loss. These timers can be set to move on much more quickly following unrecoverable loss.

Reordering latency only happens when messages arrive out of order. It is entirely variable with no fixed component. However, in cases where loss is the cause of reordering latency, reordering latency is the lesser of the retransmission latency or unrecoverable loss detection threshold.

17.5. Batching

Achieving low latency is almost always at odds with efficient use of resources. There is a fixed overhead associated with every network packet generated and every interrupt serviced. CPU time is required to generate and decode the packet. Network bandwidth is required for physical, network, and transport layer protocols. When message payloads are small relative to the network MTU, this overhead can be amortized over many messages by batching them together into a single packet. This provides a significant efficiency improvement over the simple, low-latency alternative of sending one message per packet.

Similarly, in the world of NIC hardware, a NIC can often be configured to interrupt the CPU for each network packet as it is received. This provides the lowest possible latency, but doesn't get very much work done for the fixed cost of servicing the interrupt. Many modern Gigabit Ethernet NICs have a feature that allows the NIC to delay interrupting the CPU until several packets have arrived, thus amortizing the fixed cost of servicing the interrupt over all of the packets serviced. This adds latency in the interest of efficiency and performance under load. See Section 18 for more information.

Batching latency may be small or insignificant if messages are sent very quickly. The most difficult trade offs have to be made when it can't be known in advance when the next message will be sent. Trade offs may be specified as a maximum latency that would be added before sending a network packet. Additionally, a minimum size required to trigger transmission of a network packet could be specified. UM offers applications control over these batching parameters so that they can optimize the trade off between efficiency and latency.

Batching latency is variable depending on the batching control parameters and the time between messages.

Batching can happen in the transport layer as well as in the messaging layer. Nagle's algorithm is widely used in TCP to improve efficiency by delaying packet transmissions. See Section 2.4 for more information.

17.6. CPU Scheduling

One of the critical resources a messaging system needs is CPU time. There is often some latency between when messaging code is ready to run and when it actually gets a CPU scheduled.

There are generally both fixed and variable components to CPU scheduling latency. The fixed component is the latency when a CPU is idle and can be immediately scheduled to messaging code following a device interrupt that makes it ready to run. See Section 20 for more background and measurements we've taken.

The variable component of CPU scheduling latency is often due to contention over CPU resources. If no idle CPUs are available when messaging code becomes ready to run, then the CPU scheduling latency will also include CPU contention latency. See Section 21 for more background and measurements we've taken.

17.7. Socket Buffers

Socket buffers are present in the OS kernel on both the sending and receiving ends. These buffers help to smooth out fluctuations in message generation and consumption rates. However, like any buffering, socket buffers can add latency to a messaging system. The worst-case latency can be computed by dividing the size of the socket buffer by the data rate flowing through the buffer.

Socket buffer latency can vary from near zero to the maximum computed above. The faster messages are produced or the more slowly they are consumed, the more likely they are to be delayed by socket buffering.

17.8. Network Queuing

Switches and routers buffer partial or complete packets on queues before forwarding them. Such buffering helps to smooth out peaks in packet entrance rates that may briefly exceed the wire speed of an exit interface.

Desktop and consumer-grade switches tend to have little memory for buffering and hence are generally only willing to queue a packet or two for each exit interface. However, routers and infrastructure-grade switches have enough memory to buffer several dozen packets per exit interface. Each queued packet adds latency equal to the time needed to serialize it (see Section 17.10).

Network queuing latency is present whenever switches and routers are used. However, it is highly variable. On an idle network with cut-through switching, it could be just the serialization latency for the portion of a packet needed to determine its destination. On a congested routed network, it could be many dozen times the serialization latency of an MTU-sized packet.

17.9. Network Access Control

Sometimes also called network admission control, this latency source is a combination of factors that may add latency before a packet is sent. The simplest case is where messages are being sent faster than the wire speed of the network. Latency may also be added before a packet is sent if there is contention for network bandwidth. (It is a common misconception that switched networks eliminate such contention. Switches do help, but the contention point often becomes getting packets out of the switch rather than into it.) See Section 4 for a possible cause of network access control latency.

Transport-layer protocols like LBT-RM may also add latency if an application attempts to send messages faster than the network can safely deliver them. The rate controls that impose this latency promise stable network operation in return. Indeed, most forms of network access control latency end up being beneficial by preventing unfair use or congestive collapse of the network.

Network access control latency should happen infrequently on modern networks where message generation rates are matched to the ability of the network to safely carry them. It can be highly variable and difficult to estimate because it may arise from the actions of others on the network.

17.10. Serialization

Networks employ various techniques for serializing data so that it can be moved conveniently. Typically, a fixed-frequency clock coordinates the action of a sender and receiver. One bit is often transmitted for each beat of the clock. Serialization latency is due to the fact that a receiver cannot use a packet until its last bit has arrived.

The common DS0 communications line operates at 56 Kbps and hence adds 214 ms of serialization latency to a 1500-byte packet. A DS1 line ("T1") operates at 1.5 Mbps, adding 8 ms of latency. Even a 100 Mbps Ethernet adds 120 μs of latency on a 1500-byte packet.

Serialization latency should be constant for a given clock rate. It should be consistent across all messages.

17.11. Speed of Light

186,000 miles per second--it's not just a good idea, it's the law!

Although often insignificant under one roof or even around a campus, latency due to the speed of light can be a significant issue in WAN communication. Signals travel through copper wires and optical fibers at only about 60% of their speed in a vacuum. Hence the 3,000 km trip from Chicago to San Francisco takes about 15 ms while the 6,400 km trip from Chicago to London takes about 33 ms.

As far as we know, the speed of light is a constant of the universe so we'd expect the latency it adds over a fixed path to also be constant.

17.12. Address Resolution Protocol (ARP)

Address Resolution Protocol, or ARP, is invoked the first time a unicast message is sent to an IP address.

• ARP on the sending host sends a broadcast message to every host on the subnet, asking "Who has IP x.x.x.x?"

• The host with IP address "x.x.x.x" responds with its Ethernet address in an ARP reply.

• The sending host can now resolve the IP address to an Ethernet address, and send messages to it.

ARP will cache the Ethernet address for a specific period of time and reuse that information for future message send operations. After the ARP cache timeout period, the address is typically dropped from the ARP cache, adding application latency to the next message sent from that host to that IP address because of the overhead of the address resolution process. A complicating factor is that different operating systems have different defaults for this timeout, for example, Linux often uses 1 minute, whereas Solaris often uses 5 minutes.

Another potential source of latency is an application that is sending unicast messages very fast while ARP resolution is holding up the sending process. These messages must be buffered until the ARP reply message is received, which causes latency, and may lead to loss, adding additional latency for the recovery of those messages.

Note that ARP latency is the total roundtrip cost of the originating host sending the "Who has..." message and waiting for the response. Users on 1Gbe networks may estimate a minimum of 80-100 usecs.

All of the above applies to unicast addressing only. With multicast addressing, ARP is not an issue, because the network router takes care of managing the list of interested network ports.

One way to eliminate ARP latency completely is to use a static ARP cache, with the hosts configured to know about each other. Of course, this is a very labor-intensive solution, and maintaining such configurations can be onerous and error-prone.

Yet another solution is to configure the ARP cache timeout on all hosts on the network to be much longer, say, 12 hours. This may also require devoting more memory to the ARP cache itself. If an initial heartbeat message is built into every app to absorb the latency hit on a meaningless message before the start of the business day, there should be no ARP-induced latency during business hours. However, one downside to this approach is if a host's IP address or MAC address were to change during this time, a manual ARP flush would be required.

18.1. Linux Interrupt Coalescing

On Linux, the conventional way to configure interrupt coalescing seems to be the ethtool command. However, some NIC drivers seem to require configuration in other ways. In our experience, if ethtool -c eth0 did not work, then another method was available.

For example, we have seen that with some Intel NICs on Linux, interrupt coalescing is controlled through the modprobe method of configuring loadable drivers. /etc/modprobe.conf might look like this:

options e1000 InterruptThrottleRate=8000

Some default configurations set InterruptThrottleRate to 1 which selects dynamic interrupt coalescing. We have seen significant reductions in latency by changing this to a fixed value (e.g. 8,000) as suggested in Intel Application Note AP-450. Using a value of 8,000 would limit receive latency to 1 second/8000 = 125 μs worst case.

For NICs and drivers configured with ethtool, make sure the adaptive-rx parameter is off for the lowest possible latency. Also check the settings of all of the rx-usecs and rx-frames parameters.

18.2. Linux "ethtool" Command Parameters

The Linux "ethtool -C" command provides a wide array of different types of parameters that can be configured in various ways to set values related to interrupt coalescing.

Please note that even though "ethtool" provides support for these parameters, the NIC driver itself may not. Use the "man ethtool" page along with the NIC documentation to research the exact parameters available in more detail.

The tables below are organized by type of parameter: RX Parameters, TX Parameters, and Other Parameters.

RX Parameters

TX Parameters

Other Parameters

18.3. Windows Interrupt Coalescing

We haven't had as much experience configuring interrupt coalescing on Windows as we have had on Linux. For a given type of NIC, we'd expect the relevant parameters name to be similar to those given for Linux above.

18.4. Windows NIC Loss Avoidance and Detection

We know of a few ways to avoid and detect loss at the NIC level, depending on the brand of NIC on your Windows machine. Below, we cover Windows and Intel NICs and Windows and Broadcom NICs.