Fast Retransmit - an overview (2023)

1.3.4 Window Size Decrements, Part 2: Fast Retransmit and Fast Recovery

Section 1.3.3 discusses the rules that TCP Reno uses to increment its window in the absence of network congestion. This section discusses the rules that apply to decrementing the window size in the presence of congestion. TCP uses the design philosophy that dropped packets are the best indicator of network congestion, which falls within the implicit congestion indicator category from Section 1.2.4. When TCP Slow Start was first designed, this was the only feedback that could be expected from the simpler routers that existed at that time. In retrospect, this decision came with a few issues: The only way that the algorithm can detect congestion is by driving the system into a congestive state (i.e., near the cliff of the curve in Figure 1.2). Also, if the packet losses are because of a reason other than congestion (e.g., link errors), then this may lead to unnecessary rate decreases and hence performance loss. This problem is particularly acute for error-prone wireless links, as explained in Chapter 4.

The Fast Retransmit mechanism is able to efficiently recover from packet losses as long as no more than one packet is lost in the window. If more than one packet is lost, then usually the retransmit timer for the second or later expires, which triggers the more drastic step of resetting W back to one packet.

17.2.3 Fast Retransmit and Fast Recovery

The algorithms described so far, AIMD and slow start, are considered the main TCP congestion control mechanisms. In this section, we consider relatively newer features.

In early implementations of TCP, the sender retransmitted an unacknowledged packet only after the expiration of its timeout. It was observed that the coarse-grained implementation of TCP timers led to long periods of time during which the connection went dead. Thus, a new mechanism called fast retransmit was introduced that allows the retransmission of a lost packet even if the timeout for that packet has not expired. The fast retransmit mechanism does not replace the timeout mechanism of TCP, but it works in parallel to improve performance.

The idea behind fast retransmit is straightforward. Every time a packet arrives out of order because the previous packet was lost or delayed, the receiver sends an acknowledgment that is the same as the one sent the last time. The subsequent transmissions of the same acknowledgment is called a duplicate ACK. When the sender detects a duplicate ACK, it knows that the receiver must have received a packet out of order, implying that the earlier packet was lost or delayed. To detect reliably the packets that are lost, the sender waits until it sees some number of duplicate ACKs before retransmitting the missing packet. In practice, the sender waits until it has seen three duplicate ACKs, then retransmits the packet without waiting for its timer to expire.

Finally, there is another improvement we can make. Using the fast retransmit mechanism the sender detects a possible loss of a transmitted packet, implying congestion, and therefore, it is necessary to reduce its congestion window accordingly, after the transmission of the lost packet. However, when a fast retransmit algorithm is used and when duplicate ACKs are received by the sender, it means that the packets are still flowing to the receiver. How can it be safely deduced? The generation of duplicate ACKs at the receiver is triggered only on a packet arrival. This indicates that serious network congestion may not exist and the lost packet could be a transient condition. Thus, the sender, instead of reducing its transmission rate sharply using slow start, decreases the congestion window by half and performs only the additive increase part.

Transport-Layer and Application-Layer Solutions

Intelligence at the transport and application layers is very useful for providing good service quality for the applications. When QoS is narrowly scoped as using Diffserv and other traffic management schemes to provide some better-than-Best-Effort services, such intelligence may not be considered relevant to QoS. But with the QoS definition in this book, transport- and application-layer intelligence are relevant to QoS. It comprises the end-point part of a QoS solution.

Although the focus of this book is on network QoS, it is important to point out that end-point intelligence can be very useful to enhance user experience. To some extent, this can be an alternative or supplement to network QoS, because end users will not care whether the good performance comes from network QoS or end-point intelligence. The philosophy that a network should be simple and intelligence should be at the end points is generally referred to as the “End to End Principle,” originally expressed in [Saltzer]. In reality, end-point intelligence is widely used. Virtually every popular application in the Internet employs some sort of intelligence for enhancing performance.

14.5 Transmission Control Protocol

The TCP [31, 32] is the connection-oriented transport layer protocol designed to operate on the top of the datagram network layer IP. The two widely used protocols are known under the collective name TCP/IP. TCP provides a reliable end-to-end byte stream transport. The segmentation and reassembly of the messages are handled by IP, not by TCP.

TCP uses the selective repeat protocol (SRP) with positive acknowledgments and time-out. Each byte sent is numbered and must be acknowledged. A number of bytes can be sent in the same packet, and the acknowledgment (ACK) then indicates the sequence number of the next byte expected by the receiver. ACK carrying sequence number m provides acknowledgment for all packets up to, and including, packets with sequence number m −1. If a packet is lost, the receiver sends duplicate ACK for a subsequent correctly received packet.

The TCP header is at least 20 bytes, and has 16 error detection bits for the data and the header. The error detection bits are calculated by summing the 1's complements of the groups of 16 bits that make up the data and the header, and by taking the 1's complement of that sum. The number of data that can be sent before being acknowledged is the window size (W_max) which can be adjusted by either the sender or the receiver to control the flow based on the available buffers and the congestion. Initial sequence numbers are negotiated by means of a three-way handshake at the outset of connection. Connections are released by means of a three-way handshake.

TCP transmitter (Tx) uses an adaptive window based transmit strategy. Tx does not allow more than W_max unacknowledged packets outstanding at any given time. With the congestion window lower limit at time t equal to X(t), packets up to X(t) −1 have been transmitted and acknowledged. Tx can send starting from X(t). X(t) has a nondecreasing sample path. With congestion window width at time t equal to W(t), this is the amount of packets Tx is allowed to send starting with X(t). W(t) can increase or decrease (because of window adaptation), but never exceed W_max. Transitions in X(t) and W(t) are triggered by receipt of ACK. Receiver (Rx) of an ACK increases X(t) by an amount equal to the amount of data acknowledged. Changes in W(t), however, depend on the version of TCP and the congestion control process.

Tx starts a timer each time a new packet is sent. If the timer reaches a round trip time-out (RTO) value before the packet is acknowledged, a time-out occurs. Retransmission is initiated on time-out. RTO value is derived from a round trip timer estimation procedure. RTO is sent only in multiples of a timer granularity.

For a given object, the latency is defined as the time from when the client initiates a TCP connection until the time at which the client receives the requested object in its entirety. Using the following assumptions, we provide expressions for latency with a static and dynamic congestion window.

2.5 SACK

SACK (Khan, 2005) uses the slow-start and fast retransmit stages of the TCP Reno. SACK is an improvement of New Reno where segments are not acknowledged cumulatively. Segments in TCP SACK are acknowledged selectively. On entering fast recovery, it initializes a variable buffer that estimates how much data is remaining, and it also set congestion window to half of the current size. It reduces the buffer by one on every received ACK and increments it by one on every segment retransmission. When the buffer becomes smaller than the congestion window it sends the segments, which are not yet received. If buffer does not contain any outstanding segments then a new packet is sent. Thus, in one RTT, more than one lost segment can be sent. The problem with SACK is that, the receiver does not provide currently selective acknowledgements that are a necessary requirement for the proper functioning of SACK.

The TCP has been successfully adapted to several new environments like, long fat networks, wireless, and cellular networks. However, the unique workloads in data center environment break some basic regulations on which TCP was originally based upon. For example, round trip times (RTTs) in wide area networks (WANs) are multiple orders of magnitude greater than the average RTT in data centers. Similarly, because of the peculiar characteristics of a DCNs such as low-cost commodity switches with small buffers, high bandwidth, low latency links, and existence of data intensive applications (Web search, and email), new shortcomings in TCP are observed and one of them is termed as the incast problem. In general, TCP incast can be characterized as high-bandwidth and low-latency networks connected by switches with minimal buffer sizes. Within the network, barrier-synchronized requests are being issued by clients in a parallel fashion and servers simultaneously responding with a fragment of data block per request (Zhang and Ansari, 2011). There has been research done for designing efficient TCP schemes to avoid the typical TCP incast problem in DCNs.

4.7 Open research issues

Most TE approaches and schemes discussed in this section share a common overall objective: to provide predictable and high-bandwidth network under highly variable traffic demands while also meeting other criteria such as, e.g., energy consumption minimisation. The common underlying control loop includes monitoring, detecting, and adapting promptly to problematic link load, providing a model that reacts to adverse conditions such as congestion.

The transient load imbalance induced by load-agnostic flow admission can significantly affect other flows using a heavily-utilised link that is common to both routes. Flows contending for the bandwidth of the shared link are more likely to create congestion which in turn causes packet drops for flows sharing the same bottleneck link. In most TCP implementations, packet loss will trigger packet retransmission when the retransmission timer expires or when fast-retransmit conditions are met. This additional latency can be a primary contributor to degradation of network performance since the retransmission timeout is a factor of 100 or more than the round trip time over a DC network environment.

Traffic flows are usually shuffled over shortest paths between communicating hosts. In some cases, however, selecting a non-shortest path can be advantageous for avoiding congestion or routing around a faulty path/node [67]. The surveyed proposals in this section only use multiple equal cost path in DC environment. In comparison, Baatdaat[90] and MPEFT[67] opportunistically include non-shortest paths for packet forwarding. However, finding flow routes in a general network while not exceeding the capacity of any link is the multi-commodity flow problem which is NP-complete for integer number of flows. Hence, the routing algorithm might consider non-shortest paths constrained by no more than n hops longer than the shortest path in practice because it does not significantly increase computation complexity [90].

4.3 Congestion control algorithms for multiple paths

Multipath congestion control is a broad-ranging field; let us first spend some time to delineate our direction of research. Multipath congestion control algorithms can be explored along many aspects like TCP-friendliness, stability, Pareto optimality, resource pooling, among others (Xu et al., 2016a; Li et al., 2016). In keeping with the logical sequence of our paper (i.e., discussion on fair resource allocation in Section 2.3), we aspire to examine congestion control algorithms in terms of TCP-friendliness.

Note that congestion control algorithms have already been analyzed with regard to TCP fairness in Xu et al. (2016a) and Li et al. (2016). We intend to enhance the existing study by presenting three pieces. (1) We categorize the congestion control mechanism of various multipath transport-layer protocols with reference to uncoupled, uncoupled with shared bottleneck detection, and coupled. (2) Going deep into uncoupled and coupled methodology, we further compare and contrast the TCP-friendliness of different congestion control algorithms.¹³ (3) We study the strengths and weaknesses of congestion control algorithms along four aspects: flappiness, capture problem, resource pooling, and efficient network utilization. The discussion in the subsequent paragraphs harmonizes with the aforestated three points.

Congestion control algorithms for multiple paths can be broadly classified as uncoupled (or decoupled, Xu et al., 2016a) and coupled. Let us start our discussion with uncoupled congestion control. The simplest way to extend congestion control mechanism for use with multiple paths is to run traditional TCP congestion control (e.g., TCP Reno, TCP New Reno, Henderson et al., 2012, and TCP Westwood) on each sub-path. This design methodology was used in the early versions of SCTP and MPTCP (Xu et al., 2016a). However, this scheme runs the risk of being unfair to other Internet traffic in the case of shared bottlenecks¹⁴ as well as distinct bottlenecks.¹⁵

In order to ensure TCP fairness, researchers proposed the idea of identifying and detecting shared bottlenecks and suppressing them. This phenomenon is referred to as shared bottleneck detection (SBD). Using uncoupled congestion control with SBD addresses the problem of TCP fairness to some extent but has two serious limitations. (1) The problem of unfairness in the case of disjoint paths still remains. (2) The time required to identify and suppress shared bottlenecks can sometimes significantly degrade performance. In the pursuit of solving these shortcomings, researchers developed coupled congestion control algorithms.

Coupled congestion control algorithms, as the name suggests, couples the congestion windows across different paths in some ratio. A wide range of coupled congestion control algorithms (e.g., fully coupled, semi-coupled, BALIA) have been proposed in the literature with the plan of achieving better TCP fairness performance. Despite the fact that coupled refers to a broad spectrum of algorithms, we categorize multipath transport layer protocols in terms of uncoupled, uncoupled with SBD, and coupled for simplicity. We refer the reader to Table 2 in order to have a look at the results of our study.

Moving on to the second piece of our contribution, we first need to determine a group of algorithms for comparison. This task needs some foundation that we built next. Congestion control algorithms can be designed using different design methodologies, e.g., multipath additive increase and multiplicative decrease (AIMD) method, multipath multiplicative increase and multiplicative decrease (MIMD) (Kokku et al., 2007) scheme, utility optimization and control systems (Han et al., 2006; Radunovic et al., 2008; Lai et al., 2012; Peng et al., 2013), to name a few. We examine only multipath AIMD as it provides the necessary groundwork for descending on a set of algorithms for comparison.

This framework of multipath AIMD and design goals converge us on a handful of schemes: namely uncoupled Reno, evenly weighted TCP (EW-TCP), fully coupled, semi-coupled, linked increase adaptation (LIA), dynamic window coupling (DWC), opportunistic linked increase adaptation (OLIA), adapted OLIA (AOLIA), BALIA, EW-MPTCP, and Zhao et al. (2015), which will be inspected in terms of TCP fairness performance.¹⁶

We begin our discussion with uncoupled Reno. Uncoupled Reno, due to maintaining a separate congestion window for each path, aggressively uses bandwidth and can deprive other Internet traffic of their fair share in case of shared as well as distinct bottlenecks.

Next, fully coupled algorithm (Kelly and Voice, 2005; Han et al., 2004) emerged on the scene with the ambition of improving TCP fairness performance by using total window term, i.e., ${\sum }_{k\in s}{w}_k$, as shown in Table 5. This total window term couples the congestion window across all paths and provides better fairness in comparison to EW-TCP. However, the use of total window term makes fully coupled over ambitious in decreasing its window-size (since one bad path may result in decreasing traffic on good paths too). As a result, the algorithm may not conform to design goal 1 (performance) in some cases.

Realizing the performance loophole in fully coupled, semi-coupled algorithm (Wischik et al., 2011) came forth with a window-increase function that uses an additional aggressiveness factor to better meet design goals 1 (performance) and 2 (TCP fairness). Due to this aggressiveness factor, semi-coupled algorithm lies somewhere between EW-TCP and fully coupled in fairness performance.

Modified semi-coupled, also known as LIA (Raiciu et al., 2011b), is a modification to the window-increase function of semi-coupled to ensure that the total bandwidth obtained by multipath TCP flows does not starve regular TCP flows in case of shared bottlenecks. This tailoring in the window-increase function of LIA makes it more TCP-friendly than EW-TCP and semi-coupled. It is worth mentioning a very exciting enhancement to LIA, EW-MPTCP (Ming et al., 2014) that is targeted towards solving incast collision¹⁷ in datacenters. EW-MPTCP weights the size of congestion window in reverse proportion to the number of available paths and has same TCP-friendliness potential as LIA.

LIA, as mentioned before, assigns a bandwidth to subflows considering a shared bottleneck. But, what if the subflows are traversing distinct bottlenecks? In that case, LIA will unnecessarily reduce window size and consequently achieve less than actually available bandwidth. Furthermore, Khalili et al. (2013b) found out that LIA is not Pareto optimal.¹⁸ Investigation into the reasons behind non-Pareto optimality revealed that LIA inherently employs a trade-off between resource pooling and responsiveness, i.e., for good responsiveness LIA departs from Pareto optimality. This problem can also make LIA more aggressive towards other Internet traffic.

DWC (Hassayoun et al., 2011; Singh and Xiang, 2013a) addressed the first aforestated problem by coupling only those subflows that have a common bottleneck and keeping a separate congestion window for subflows belonging to distinct bottlenecks. Maintaining separate congestion windows for subflows belonging to shared and distinct bottlenecks makes DWC less TCP fair than LIA. OLIA (Khalili et al., 2013a) came out to solve the non-Pareto optimality of LIA. Its window-increase function, presented in Table 5, consists of two parts. The first part, based on the work of Kelly and Voice (2005), ensures Pareto optimality and improved TCP fairness while the second part guarantees good responsiveness. On this account, OLIA is more TCP-friendly than LIA.

Furthermore, Singh et al. (2013b) argued by comparing the first term in window-increase function of LIA and OLIA that the overall throughput of LIA is usually better than OLIA. In an effort to combine the best of both worlds (i.e., achieve a TCP fairness performance somewhere between LIA and OLIA), Singh et al. proposed adapted OLIA (AOLIA) that is a LIA-based extension of OLIA. Its window-increase function consists of two parts: the first part is a combination of OLIA and LIA while the second part is based on the regular TCP window-increase function.

Peng et al. (2016) developed BALIA on a theoretical framework. During their research, the authors observed that there exists an inevitable trade-off between TCP-friendliness and responsiveness (i.e., the most TCP-friendly algorithm is least responsive and vice versa). Due to this fact, BALIA is also referred to as the trade-off algorithm and has been found to strike the most balanced bargain between TCP-friendliness and responsiveness. Finally, Zhao et al. (2015) moved the theoretical setting of Peng et al. (2013) forward by proposing an algorithm that achieves better TCP fairness than BALIA and uses a congestion balancing factor b_r in its window-increase function to better meet design goal 3 (resource pooling).

Lastly, we go on to examine the strengths and weaknesses of congestion control algorithms along four attributes, which are flappiness, capture problem, resource pooling, and efficient network utilization. Flappiness and capture problem mark the deficiencies of an algorithm while resource pooling and efficient network utilization represent the benefits provided by an algorithm. In particular, flappiness measures stability while the other three attributes are related to MPTCP design objectives 1 (performance) and 3 (resource pooling).

We start our discussion with flappiness. Flappiness is a design imperfection that arises due to the flipping of subflows between optimal paths subject to small random fluctuations in the network. Uncoupled Reno maintains a separate window for each path and thus the question of flipping subflows never arises. EW-TCP, due to evenly splitting traffic among all available paths, is also safe from this defect. However, fully coupled algorithm that makes traffic splitting decision according to path characteristics is flappy. This is due to the fact that fully coupled treats temporary variations (e.g., small changes in bandwidth, congestion window size) in the network as permanent changes and keeps on shifting subflows between good paths that makes the algorithm unstable.

Wischik et al. (2010), while trying to solve flappiness, proposed the principle of equipoise. Equipoise defines a trade-off between resource pooling and traffic balancing by stating that congestion control algorithms should balance traffic among the best paths in such a way that it is robust to transient network fluctuations and responsive to persistent changes. This principle influenced all the subsequently proposed algorithms in the literature. As a result, later proposed algorithms do not suffer from flappiness.

Capture problem is a defect that causes subflows to be “trapped” or “captured” in a less desirable path and can significantly degrade the performance of an algorithm. Uncoupled Reno and EW-TCP do not suffer from this problem due to the same reasons as mentioned in flappiness. Fully coupled algorithm, however, experiences capture problem due to transmitting data on best paths and keeping very little traffic on worst path. Thus, if the path characteristics of worst path improve and that of good paths worsen, the algorithm cannot use the newly available better path due to insufficient probing traffic on it. The subflow in such a case is said to be trapped or captured in the less desirable paths and cannot utilize the available better paths. The principle of equipoise catered for this problem too, and because of that later proposed algorithms in the literature do not suffer from this handicap.

Resource pooling, in the context of coupled congestion control algorithms, is a big strength that allows an algorithm to pool congestion windows across multiple paths. This results in achieving more bandwidth, better reliability, and more robustness than each individual paths. Since uncoupled Reno does not unite the congestion windows on different paths, it is not able to reap the benefits of resource pooling while all aforenamed coupled algorithms implement resource pooling.

Efficient network utilization works on the brilliant idea of transmitting more traffic on good paths and less on bad paths. Uncoupled Reno, due to maintaining a window per path, cannot make very effective data distribution decisions. Also, EW-TCP allocates data without taking into account heterogeneous path characteristics. The available bandwidth could be utilized more efficiently if more traffic is sent on path with better path characteristics (i.e., low drop probability, small delay, small size of congestion window) as it will reduce congestion in the network and provide better load balancing. Therefore, coupled algorithms (other than EW-TCP) have been designed while keeping in mind efficient network utilization, i.e., they all assign traffic according to path characteristics. Table 5 provides a quick rundown of the above discussion by summarizing the strengths and weaknesses of heterogeneous congestion control algorithms.