《计算机网络》课程教学资源（参考文献）A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

Appeared in IEEE/ACM Transactions on Newworking, Dec 1997. This is a much-extended and revised version of a paper that appeared at ACMSIGCOMM, 1996 A Comparison of Mechanisms for Improving TCP Performance over Wireless links Hari Balakrishnan, Venkata N. Padmanabhan, Srinivasan Seshan and Randy h. Katz lari, padmanab, ss, randy )@cs. berkeley. edu Computer Science Division, Department of EECS, University of california at Berkeley Abstract the estimated round-trip delay and the mean linear deviation from it. The sender identifies the loss of a packet either by Reliable transport protocols such as TCP are tuned to per- the arrival of several duplicate cumulative acknowled form well in traditional networks where packet losses occur ments or the absence of an acknowledgment for the packet mostly because of congestion. However, networks with within a timeout interval equal to the sum of the smoothed wireless and other lossy links also suffer from significant round-trip delay and four times its mean deviation. TCP losses due to bit errors and handoffs. TCP responds to all reacts to packet losses by dropping its transmission(conges- losses by invoking congestion control and avoidance algo- tion) window size before retransmitting packets, initiating rithms, resulting in degraded end-to-end performance in congestion control or avoidance mechanisms(e.g, slow wireless and lossy systems. In this paper, we compare sev- start[13) and backing off its retransmission timer(Karn's eral schemes designed to improve the performance of TCP Algorithm[16]). These measures result in a reduction in the in such networks. We classify these schemes into three load on the intermediate links, thereby controlling the con- broad categories: end-to-end protocols, where loss recovery gestion in the network is performed by the sender; link-layer protocols, that pro- vide local reliability; and split-connection protocols, that Unfortunately, when packets are lost in networks for rea- break the end-to-end connection into two parts at the base sons other than congestion, these measures result in an station. We present the results of several experiments per- unnecessary reduction in end-to-end throughput and hence formed in both lan and Wan environments. using sub-optimal performance. Communication over wireless throughput and goodput as the metrics for comparison links is often characterized by spor gh bit-error rates and intermittent connectivity due to handoffs. TCP perfor Our results show that a reliable link-layer protocol that is mance in such networks suffers from significant throughput TCP-aware provides very good performance. Furthermore, gh it is possible to achieve good performance without splitting the end-to-end connection at the base station We also dem- Recently, several schemes have been proposed to the allevi- onstrate that selective acknowledgments and explicit loss ate the effects of non-congestion-related losses on TCP per- notifications result in significant performance improve- loss links 3, 7, 28]. These schemes choose from a variety of mechanisms, such as local retransmissions, split-TCP con- nections, and forward error correction, to improve end-to- L. ntroduction end throughput. However, it is unclear to what extent each The increasing popularity of wireless networks indicates of the mechanisms contributes to the improvement in per- that wireless links will play an important role in future inter formance. In this paper, we examine and compare the effec networks. Reliable transport protocols such as TCP [24. 261 tiveness of these schemes and their variants, and have been tuned for traditional networks comprising wired experimentally analyze the individual mechanisms and the links and stationary hosts. These protocols assume conges- degree of performance improvement due to each tion in the network to be the primary cause for packet losses There are two different approaches to improving TCP per and unusual delays. TCP performs well over such networks formance in such lossy systems. The first approach hides by adapting to end-to-end delays and congestion losses. The any non-congestion-related losses from the TCP sender and TCP sender uses the cumulative acknowledgments it therefore requires no changes to existing sender implemen- receives to determine which packets have reached the tations. The intuition behind this approach is that since the receiver,and provides reliability by retransmitting lost problem is local, it should be solved locally, and that the It maintains a ort layer need not be aware of the ch the individual links. Protocols that adopt this appr attempt to make the lossy link appear as a higher quality 1.WebpageUrlhttp://daedalus.cs.berkeley.edu. link with a reduced effective bandwidth. As a result most of rinivasan Seshan is now at IBM TJ. Watson Research Center Hawthorne,NY(srini@watson.ibm.com) the losses seen by the TCP sender are caused by congestion

A Comparison of Mechanisms for Improving TCP Performance over Wireless Links Hari Balakrishnan, Venkata N. Padmanabhan, Srinivasan Seshan and Randy H. Katz1 {hari,padmanab,ss,randy}@cs.berkeley.edu Computer Science Division, Department of EECS, University of California at Berkeley Abstract Reliable transport protocols such as TCP are tuned to per￾form well in traditional networks where packet losses occur mostly because of congestion. However, networks with wireless and other lossy links also suffer from significant losses due to bit errors and handoffs. TCP responds to all losses by invoking congestion control and avoidance algo￾rithms, resulting in degraded end-to-end performance in wireless and lossy systems. In this paper, we compare sev￾eral schemes designed to improve the performance of TCP in such networks. We classify these schemes into three broad categories: end-to-end protocols, where loss recovery is performed by the sender; link-layer protocols, that pro￾vide local reliability; and split-connection protocols, that break the end-to-end connection into two parts at the base station. We present the results of several experiments per￾formed in both LAN and WAN environments, using throughput and goodput as the metrics for comparison. Our results show that a reliable link-layer protocol that is TCP-aware provides very good performance. Furthermore, it is possible to achieve good performance without splitting the end-to-end connection at the base station. We also dem￾onstrate that selective acknowledgments and explicit loss notifications result in significant performance improve￾ments. 1. Introduction The increasing popularity of wireless networks indicates that wireless links will play an important role in future inter￾networks. Reliable transport protocols such as TCP [24, 26] have been tuned for traditional networks comprising wired links and stationary hosts. These protocols assume conges￾tion in the network to be the primary cause for packet losses and unusual delays. TCP performs well over such networks by adapting to end-to-end delays and congestion losses. The TCP sender uses the cumulative acknowledgments it receives to determine which packets have reached the receiver, and provides reliability by retransmitting lost packets. For this purpose, it maintains a running average of 1. Web page URL http://daedalus.cs.berkeley.edu. Srinivasan Seshan is now at IBM T.J. Watson Research Center, Hawthorne, NY (srini@watson.ibm.com). the estimated round-trip delay and the mean linear deviation from it. The sender identifies the loss of a packet either by the arrival of several duplicate cumulative acknowledg￾ments or the absence of an acknowledgment for the packet within a timeout interval equal to the sum of the smoothed round-trip delay and four times its mean deviation. TCP reacts to packet losses by dropping its transmission (conges￾tion) window size before retransmitting packets, initiating congestion control or avoidance mechanisms (e.g., slow start [13]) and backing off its retransmission timer (Karn’s Algorithm [16]). These measures result in a reduction in the load on the intermediate links, thereby controlling the con￾gestion in the network. Unfortunately, when packets are lost in networks for rea￾sons other than congestion, these measures result in an unnecessary reduction in end-to-end throughput and hence, sub-optimal performance. Communication over wireless links is often characterized by sporadic high bit-error rates, and intermittent connectivity due to handoffs. TCP perfor￾mance in such networks suffers from significant throughput degradation and very high interactive delays [8]. Recently, several schemes have been proposed to the allevi￾ate the effects of non-congestion-related losses on TCP per￾formance over networks that have wireless or similar high￾loss links [3, 7, 28]. These schemes choose from a variety of mechanisms, such as local retransmissions, split-TCP con￾nections, and forward error correction, to improve end-to￾end throughput. However, it is unclear to what extent each of the mechanisms contributes to the improvement in per￾formance. In this paper, we examine and compare the effec￾tiveness of these schemes and their variants, and experimentally analyze the individual mechanisms and the degree of performance improvement due to each. There are two different approaches to improving TCP per￾formance in such lossy systems. The first approach hides any non-congestion-related losses from the TCP sender and therefore requires no changes to existing sender implemen￾tations. The intuition behind this approach is that since the problem is local, it should be solved locally, and that the transport layer need not be aware of the characteristics of the individual links. Protocols that adopt this approach attempt to make the lossy link appear as a higher quality link with a reduced effective bandwidth. As a result, most of the losses seen by the TCP sender are caused by congestion. Appeared in IEEE/ACM Transactions on Networking, Dec.1997. This is a much-extended and revised version of a paper that appeared at ACM SIGCOMM, 1996

Examples of this approach include wireless links with reli- 2. How important is it for link-layer schemes to be aware ble link-layer protocols such as AIRMAIL [I, split con of TCP algorithms to achieve high end-to-end through nection approaches such as Indirect-TCPB3, and TCP- aware link-layer schemes such as the snoop protocol [7 The second class of techniques attempts to make the sender 3. How useful are selective acknowledgments in dealing aware of the existence of wireless hops and realize that with lossy links, especially in the presence of burst ome packet losses are not due to congestion, The sender can then avoid invoking congestion control algorithms 4. Is it important for the end-to-end connection to be split when non-congestion-related losses occur-we describe in order to effectively shield the sender from wireless some of these techniques in Section 3. Finally, it is possible losses and obtain the best performance? for a wireless-aware transport protocol to coexist with link layer schemes to achieve good performance We answer these questions by implementing and testing the various protocols in a wireless testbed consisting of Pentium We classify the many schemes into three basic groups, PC base stations and IBM ThinkPad mobile hosts communi based on their fundamental philosophy: end-to-end propos- cating over a 915 MHz AT& T Wavelan, all running BSD/ als, split-connection proposals and link-layer proposals. The OS 2.0. For each protocol, we measure the end-to-end end-to-end protocols attempt to make the TCP sender han- throughput, and goodputs for the wired and(one-hop)wire- dle losses through the use of two techniques. First, the ev use less paths. For any path(or link), goodput is defined as the some form of selective acknowledgments(SACKs) to allow ratio of the actual transfer size to the total number of bytes the sender to recover from multiple packet losses in a win- transmitted over that path. In general, the wired and wireless dow without resorting to a coarse timeout. Second, they goodputs differ because of wireless losses, local retransmis- attempt to have the sender distinguish between congestion sions and congestion losses in the wired network. These nd other forms of losses using an Explicit Loss Notifica- metrics allow us to determine the end-to-end performance tion(ELN) mechanism. At the other end of the solution as well as the transmission efficiency across the network spectrum, split-connection approaches completely hide the While we used a wireless hop as the lossy link in our exper nection at the base station. Such schemes use a separate e a. iments, we believe our results are applicable in a wider con- wireless link from the sender by terminating the TCP cor text to links where significant losses occur for reasons other le connection between the base station and the destination than congestion Examples of such links include high-speed ost. The second connection can use techniques such as modems and cable modems negative or selective acknowledgments, rather than just tandard TCP, to perform well over the wireless link. The We show that a reliable link-layer protocol with some third class of protocols, link-layer solutions, lie between the knowledge of TCP results in very good performance. Our other two classes. These protocols attempt to hide link experiments indicate that shielding the TCP sender from related losses from the TCP sender by using local retrans. duplicate acknowledgments caused by wireless losses missions and perhaps forward error correction [e.g, 18] Improves throughput by 10-30%.Furthermore, it is possible ver the wireless link. The local retransmissions use tech to achieve good performance without splitting the end-to- niques that are tuned to the characteristics of the wireless end connection at the base station. We also demonstrate that ink to provide a significant increase in performance. Since selective ac knowledgments and explicit loss notifications the end-to-end TCP connection passes through the lossy result in significant performance improvements.For nk, the TCP sender may not be fully shielded from wire- instance, the simple eln scheme we evaluated improved less losses. This can happen either because of timer interac- the end-to-end throughput by a factor of more than two tions between the two layers [101, or more likely because of ompared to TCP Reno, with comparable goodput values TCP's duplicate acknowledgments causing sender fast The rest of this paper is organized as follows. Section 2 transmissions even for segments that are locally retrans- briefly describes some proposed solutions to the problem of mance use mechanisms based on t improve TCP perfor- reliable transport protocols over wireless links. Section 3 messaging to shield the TCP sender more effectively and cols in our wireless testbed, and Section 4 presents the avoid competing and redundant retransmissions [7] results and analysis of several experiments. Section 5 dis In this paper, we evaluate the performance of several end cusses some miscellaneous issues related to handoffs ELN to-end, split-connection and link-layer protocols using end- Implementation and selective acknowledgmentsWe present to-end throughput and goodput as performance metrics, in our conclusions in Section 6. and mention some future work both LAN and WAN configurations. In particular, we seek in Section 7 to answer the following specific question: 1. What combination of mechanisms results in best per- formance for each of the protocol classes?

Examples of this approach include wireless links with reli￾able link-layer protocols such as AIRMAIL [1], split con￾nection approaches such as Indirect-TCP [3], and TCP￾aware link-layer schemes such as the snoop protocol [7]. The second class of techniques attempts to make the sender aware of the existence of wireless hops and realize that some packet losses are not due to congestion. The sender can then avoid invoking congestion control algorithms when non-congestion-related losses occur — we describe some of these techniques in Section 3. Finally, it is possible for a wireless-aware transport protocol to coexist with link￾layer schemes to achieve good performance. We classify the many schemes into three basic groups, based on their fundamental philosophy: end-to-end propos￾als, split-connection proposals and link-layer proposals. The end-to-end protocols attempt to make the TCP sender han￾dle losses through the use of two techniques. First, they use some form of selective acknowledgments (SACKs) to allow the sender to recover from multiple packet losses in a win￾dow without resorting to a coarse timeout. Second, they attempt to have the sender distinguish between congestion and other forms of losses using an Explicit Loss Notifica￾tion (ELN) mechanism. At the other end of the solution spectrum, split-connection approaches completely hide the wireless link from the sender by terminating the TCP con￾nection at the base station. Such schemes use a separate reli￾able connection between the base station and the destination host. The second connection can use techniques such as negative or selective acknowledgments, rather than just standard TCP, to perform well over the wireless link. The third class of protocols, link-layer solutions, lie between the other two classes. These protocols attempt to hide link￾related losses from the TCP sender by using local retrans￾missions and perhaps forward error correction [e.g., 18] over the wireless link. The local retransmissions use tech￾niques that are tuned to the characteristics of the wireless link to provide a significant increase in performance. Since the end-to-end TCP connection passes through the lossy link, the TCP sender may not be fully shielded from wire￾less losses. This can happen either because of timer interac￾tions between the two layers [10], or more likely because of TCP’s duplicate acknowledgments causing sender fast retransmissions even for segments that are locally retrans￾mitted. As a result, some proposals to improve TCP perfor￾mance use mechanisms based on the knowledge of TCP messaging to shield the TCP sender more effectively and avoid competing and redundant retransmissions [7]. In this paper, we evaluate the performance of several end￾to-end, split-connection and link-layer protocols using end￾to-end throughput and goodput as performance metrics, in both LAN and WAN configurations. In particular, we seek to answer the following specific questions: 1. What combination of mechanisms results in best per￾formance for each of the protocol classes? 2. How important is it for link-layer schemes to be aware of TCP algorithms to achieve high end-to-end through￾put? 3. How useful are selective acknowledgments in dealing with lossy links, especially in the presence of burst losses? 4. Is it important for the end-to-end connection to be split in order to effectively shield the sender from wireless losses and obtain the best performance? We answer these questions by implementing and testing the various protocols in a wireless testbed consisting of Pentium PC base stations and IBM ThinkPad mobile hosts communi￾cating over a 915 MHz AT&T Wavelan, all running BSD/ OS 2.0. For each protocol, we measure the end-to-end throughput, and goodputs for the wired and (one-hop) wire￾less paths. For any path (or link), goodput is defined as the ratio of the actual transfer size to the total number of bytes transmitted over that path. In general, the wired and wireless goodputs differ because of wireless losses, local retransmis￾sions and congestion losses in the wired network. These metrics allow us to determine the end-to-end performance as well as the transmission efficiency across the network. While we used a wireless hop as the lossy link in our exper￾iments, we believe our results are applicable in a wider con￾text to links where significant losses occur for reasons other than congestion. Examples of such links include high-speed modems and cable modems. We show that a reliable link-layer protocol with some knowledge of TCP results in very good performance. Our experiments indicate that shielding the TCP sender from duplicate acknowledgments caused by wireless losses improves throughput by 10-30%. Furthermore, it is possible to achieve good performance without splitting the end-to￾end connection at the base station. We also demonstrate that selective acknowledgments and explicit loss notifications result in significant performance improvements. For instance, the simple ELN scheme we evaluated improved the end-to-end throughput by a factor of more than two compared to TCP Reno, with comparable goodput values. The rest of this paper is organized as follows. Section 2 briefly describes some proposed solutions to the problem of reliable transport protocols over wireless links. Section 3 describes the implementation details of the different proto￾cols in our wireless testbed, and Section 4 presents the results and analysis of several experiments. Section 5 dis￾cusses some miscellaneous issues related to handoffs, ELN implementation and selective acknowledgments. We present our conclusions in Section 6, and mention some future work in Section 7

2 Related work ever, as our experiments indicate, the choice of TCP over the wireless link results in several performance In this section, we summarize some protocols that have problems. Since TCP is not well-tuned for the lossy link been proposed to improve the performance of TCP over the tcp sender of the wireless connection often times wireless links. We also briefly describe some proposed out, causing the original sender to stall. In addition methods to add SaCKs to tcP every packet incurs the overhead of going through TCP Link-layer protocols: There have been several propos- protocol processing twice at the base station(as com- als for reliable link-layer protocols. The two main pared to zero times for a non-split-connection approach) classes of techniques employed by these protocols are although extra copies are avoided by an efficient kernel error correction, using techniques such as forward error implementation. Another disadvantage of split connec correction(FEC), and retransmission of lost packets in tions is that the end-to-end semantics of tcp acknowl- response to automatic repeat request(ARQ)messages edgments is violated, since acknowledgments to packets The link-layer protocols for the digital cellular systems can now reach the source even before the packets actu- in the U.S.-both CDMA [15] and TDMA [22]-pri- ally reach the mobile host. Also, since split-connection marily use ArQ techniques. While the TDMa protocol protocols maintain a significant amount of state at the guarantees reliable, in-order delivery of link-layer base station per TCP connection, handoff procedures frames, the CDMa protocol only makes a limited tend to be complicated and slow. Section 5.1 discusses attempt and leaves eventual error recovery to the(reli some issues related to cellular handoffs and TCP perfor able)transport layer. Other protocols like the AIRMAIL mance protocol [1] employ a combination of FEC and ARQ The Snoop Protocol [7: The snoop protocol introduces a module, called the snoop agent, at the base station. The The main advantage of employing a link-layer protocol agent monitors every packet that passes through the TCP for loss recovery is that it fits naturally into the layered connection in both directions and maintains a cache of structure of network protocols. The link-layer protocol TCP segments sent across the link that have not yet been operates independently of higher-layer protocols and acknowledged by the receiver. A packet loss is detected does not maintain any per-connection state. The main by the arrival of a small number of duplicate acknowl- concern about link-layer protocols is the possibility of edgments from the receiver or by a local timeout. The adverse effect on certain transport-layer protocols such snoop agent retransmits the lost packet if it has it cached as tCP as described in Section 1. We investigate this in and suppresses the duplicate acknowledgments In our detail in our experiments classification of the protocols, the snoop protocol is a link-layer protocol that takes advantage of the knowl Split connection protocols [3, 28 Split connection protocols split each TCP connection between a sender and receiver into two separate connections at the base The main advantage of this approach is that it suppresses station- one tcp connection between the sender and duplicate acknowledgments for TCP segments lost and the base station and the other between the base station retransmitted locally, thereby avoiding unnecessary fast and the receiver. Over the wireless hop, a specialized retransmissions and congestion control invocations by protocol tuned to the wireless environment may be used the sender. The per-connection state maintained by the 2281, the authors propose two protocols -one in snoop agent at the base station is soft, and is not essential which the wireless hop uses TCP, and another in which for correctness. Like other link-layer solutions, the the wireless hop uses a selective repeat protocol (SRP) snoop approach could also suffer from not being able to on top of UDP. They study the impact of handoffs on completely shield the sender from wireless losses performance and conclude that they obtain no significant Selective Acknowledgments: Since standard TCP uses advantage by using SRP instead of TCP over the wire- a cumulative acknowledgment scheme it often does not less connection in their experiments. However, our provide the sender with sufficient information to recover xperiments demonstrate benefits in using a simple quickly from multiple packet losses within a single selective acknowledgment scheme with tCP over the transmission window. Several studies [e.g., 1l]have wireless connection shown that tCP enhanced with selective acknowledg Indirect-TCP [Bakre95] is a split-connection solution ments performs better than standard TCP in such situa- that uses standard tcP for its connection over the wire. tions. SACKs were added as an option to TCP by RFC less link. Like other split-connection proposals, it 1072[14. However, disagreements over the use of attempts to separate loss recovery over the wireless link SACKs prevented the specification from being adopted from that across the wireline network, thereby shielding and the Sack option was removed from later TCP he original tcp sender from the wireless link. how- RFCs. Recently, there has been renewed interest in add ing SACKs to TCP. Two relevant proposals are the

2. Related Work In this section, we summarize some protocols that have been proposed to improve the performance of TCP over wireless links. We also briefly describe some proposed methods to add SACKs to TCP. • Link-layer protocols: There have been several propos￾als for reliable link-layer protocols. The two main classes of techniques employed by these protocols are: error correction, using techniques such as forward error correction (FEC), and retransmission of lost packets in response to automatic repeat request (ARQ) messages. The link-layer protocols for the digital cellular systems in the U.S. — both CDMA [15] and TDMA [22] — pri￾marily use ARQ techniques. While the TDMA protocol guarantees reliable, in-order delivery of link-layer frames, the CDMA protocol only makes a limited attempt and leaves eventual error recovery to the (reli￾able) transport layer. Other protocols like the AIRMAIL protocol [1] employ a combination of FEC and ARQ techniques for loss recovery. The main advantage of employing a link-layer protocol for loss recovery is that it fits naturally into the layered structure of network protocols. The link-layer protocol operates independently of higher-layer protocols and does not maintain any per-connection state. The main concern about link-layer protocols is the possibility of adverse effect on certain transport-layer protocols such as TCP, as described in Section 1. We investigate this in detail in our experiments. • Split connection protocols [3, 28]: Split connection protocols split each TCP connection between a sender and receiver into two separate connections at the base station — one TCP connection between the sender and the base station, and the other between the base station and the receiver. Over the wireless hop, a specialized protocol tuned to the wireless environment may be used. In [28], the authors propose two protocols — one in which the wireless hop uses TCP, and another in which the wireless hop uses a selective repeat protocol (SRP) on top of UDP. They study the impact of handoffs on performance and conclude that they obtain no significant advantage by using SRP instead of TCP over the wire￾less connection in their experiments. However, our experiments demonstrate benefits in using a simple selective acknowledgment scheme with TCP over the wireless connection. Indirect-TCP [Bakre95] is a split-connection solution that uses standard TCP for its connection over the wire￾less link. Like other split-connection proposals, it attempts to separate loss recovery over the wireless link from that across the wireline network, thereby shielding the original TCP sender from the wireless link. How￾ever, as our experiments indicate, the choice of TCP over the wireless link results in several performance problems. Since TCP is not well-tuned for the lossy link, the TCP sender of the wireless connection often times out, causing the original sender to stall. In addition, every packet incurs the overhead of going through TCP protocol processing twice at the base station (as com￾pared to zero times for a non-split-connection approach), although extra copies are avoided by an efficient kernel implementation. Another disadvantage of split connec￾tions is that the end-to-end semantics of TCP acknowl￾edgments is violated, since acknowledgments to packets can now reach the source even before the packets actu￾ally reach the mobile host. Also, since split-connection protocols maintain a significant amount of state at the base station per TCP connection, handoff procedures tend to be complicated and slow. Section 5.1 discusses some issues related to cellular handoffs and TCP perfor￾mance. • The Snoop Protocol [7]: The snoop protocol introduces a module, called the snoop agent, at the base station. The agent monitors every packet that passes through the TCP connection in both directions and maintains a cache of TCP segments sent across the link that have not yet been acknowledged by the receiver. A packet loss is detected by the arrival of a small number of duplicate acknowl￾edgments from the receiver or by a local timeout. The snoop agent retransmits the lost packet if it has it cached and suppresses the duplicate acknowledgments. In our classification of the protocols, the snoop protocol is a link-layer protocol that takes advantage of the knowl￾edge of the higher-layer transport protocol (TCP). The main advantage of this approach is that it suppresses duplicate acknowledgments for TCP segments lost and retransmitted locally, thereby avoiding unnecessary fast retransmissions and congestion control invocations by the sender. The per-connection state maintained by the snoop agent at the base station is soft, and is not essential for correctness. Like other link-layer solutions, the snoop approach could also suffer from not being able to completely shield the sender from wireless losses. • Selective Acknowledgments: Since standard TCP uses a cumulative acknowledgment scheme, it often does not provide the sender with sufficient information to recover quickly from multiple packet losses within a single transmission window. Several studies [e.g., 11] have shown that TCP enhanced with selective acknowledg￾ments performs better than standard TCP in such situa￾tions. SACKs were added as an option to TCP by RFC 1072 [14]. However, disagreements over the use of SACKs prevented the specification from being adopted, and the SACK option was removed from later TCP RFCs. Recently, there has been renewed interest in add￾ing SACKs to TCP. Two relevant proposals are the

Name Category Special mechanisms Standard TCP-Reno E2E-NEWRENO TCP-NewReno E2E-SMART end-to-ene SMART-based selective acks E2E-IETF-SACK end-to-end IETF Selective acks E2E-ELN end-to-end Explicit Loss Notification (ELN) E2E-ELN-RXMT end-to-end ELN with retransmit on first dupack link-layer LL-TCP-AWARE link-layer LL-SMART link-layer SMART-based selective acks LL-SMART-TCP-AWARE link-layer SMART and duplicate ack suppression SPLIT SPLIT-SMART split-connection SMART-based wireless connection Table 1. Summary of protocols studied in this papei Acknowledgments Returning at Send→2345 N TCP Receiver re l. a typical loss situation recent RFC on ICP SACKs 119 and the SMART receiver. When the sender detects a gap in the bitmask, It scheme [171 immediately assumes that the missing packets have been The SACK rfC proposes that each acknowledgment lost without considering the possibility that they simply ontain information about up to three non-contiguous may have been reordered. Thus this scheme trades of blocks of data that have been received successfully by some resilience to reordering and lost acknowledgments the receiver. Each block of data is described by its start- in exchange for a reduction in overhead to generate and and ending sequence number. Due to the limited umber of blocks. it is best to inform the sender about the most recent blocks received. The rFC does not spec 3. Implementation Details ify the sender behavior, except to require that standard TCP congestion control actions be performed when This section describes the protocols we have implemented losses occur and evaluated. Table I summarizes the key ideas in each scheme and the main differences between them Fi An alternate prope SMART, uses acknowledgments shows a typical loss situation over the wireless link. Here, that contain the cumulative acknowledgment and the the TCP sender is in the middle of a transfer across a two- sequence number of the packet that caused the receiver hop network to a mobile host. At the depicted time, the to generate the acknowledgment(this information is a sender's congestion window consists of 5 packets Of the subset of the three-blocks scheme proposed in the RFC). five packets in the network, the first two packets are lost on The sender uses this information to create a bitmask of the wireless link. As described in the rest of this section packets that have been delivered successfully to the each protocol reacts to these losses in different ways and

recent RFC on TCP SACKs [19] and the SMART scheme [17]. The SACK RFC proposes that each acknowledgment contain information about up to three non-contiguous blocks of data that have been received successfully by the receiver. Each block of data is described by its start￾ing and ending sequence number. Due to the limited number of blocks, it is best to inform the sender about the most recent blocks received. The RFC does not spec￾ify the sender behavior, except to require that standard TCP congestion control actions be performed when losses occur. An alternate proposal, SMART, uses acknowledgments that contain the cumulative acknowledgment and the sequence number of the packet that caused the receiver to generate the acknowledgment (this information is a subset of the three-blocks scheme proposed in the RFC). The sender uses this information to create a bitmask of packets that have been delivered successfully to the receiver. When the sender detects a gap in the bitmask, it immediately assumes that the missing packets have been lost without considering the possibility that they simply may have been reordered. Thus this scheme trades off some resilience to reordering and lost acknowledgments in exchange for a reduction in overhead to generate and transmit acknowledgments. 3. Implementation Details This section describes the protocols we have implemented and evaluated. Table 1 summarizes the key ideas in each scheme and the main differences between them. Figure 1 shows a typical loss situation over the wireless link. Here, the TCP sender is in the middle of a transfer across a two￾hop network to a mobile host. At the depicted time, the sender’s congestion window consists of 5 packets. Of the five packets in the network, the first two packets are lost on the wireless link. As described in the rest of this section, each protocol reacts to these losses in different ways and Name Category Special Mechanisms E2E end-to-end standard TCP-Reno E2E-NEWRENO end-to-end TCP-NewReno E2E-SMART end-to-end SMART-based selective acks E2E-IETF-SACK end-to-end IETF selective acks E2E-ELN end-to-end Explicit Loss Notification (ELN) E2E-ELN-RXMT end-to-end ELN with retransmit on first dupack LL link-layer none LL-TCP-AWARE link-layer duplicate ack suppression LL-SMART link-layer SMART-based selective acks LL-SMART-TCP-AWARE link-layer SMART and duplicate ack suppression SPLIT split-connection none SPLIT-SMART split-connection SMART-based wireless connection Table 1. Summary of protocols studied in this paper. 1 2 3 4 4 3 2 1 5 5 congestion window = 5 Figure 1. A typical loss situation TCP Source Base Station TCP Receiver Lossy Link Packets Stored at Sender Packets in Flight Acknowledgments Returning

generates messages that result in loss recovery. Although option allows us to identify what percentage of the end-to- this figure only shows data packets being lost, our experi- end performance degradation is associated with TCP ments have wireless errors in both directions incorrect invocation of congestion control algorithms when it does a fast retransmission of a packet lost on the wireless 3.1 End-To-End Schemes hop. The E2E-ELN-RXMT protocol is an enhancement of the previous one, where the sender retransmits the packet on Internet, the current de facto standard for TCP implementa. receiving the first duplicate acknowledgement with the ELN tions is TCP Reno [26]. We call this the E2E protocol, and ment in the case of TCP Reno), in addition to not shrinking use it as the standard basis for performance comparison its window size in response to wireless losses The EZ E-NEWRENO protocol improves the pertormance In practice, it might be difficult to identify which packets are lost due to errors on a lossy link. However, in our expe remaining in fast recovery mode if the first new acknowl iments we assume sufficient knowledge at the receiver ments are indicative of multiple packet losses within the gies for the ELn mechanism in Section f2 tion.We edgment received after a fast retransmission is"partial, 1.e, about wireless losses to generate ELN information. We is less than the value of the last byte transmitted when the describe some possible implementation pol nd strate fast retransmission was done. Such partial acknowledge original window of data. Remaining in fast recovery mode 3.2 Link-Layer Schemes enables the connection to recover from losses at the rate of one segment per round trip time, rather than stall until a Unlike TCP for the transport layer, there is no de facto stan- coarse timeout as TCP-Reno often would [9, 12 dard for link-layer protocols. Existing link-layer protocol choose from techniques such as Stop-and-Wait, Go-Back-N The E2E-SMART and E2E-IETF-SACK protocols add Selective Repeat and Forward Error Correction to provide SMART-based and IETF selective acknowledgments reliability. Our base link-layer algorithm, called LL, uses respectively to the standard TCP Reno stack. This allows cumulative acknowledgments to determine lost packets that the sender to handle multiple losses within a window of out- are retransmitted locally from the base station to the mobile standing data more efficiently. However, the sender still assumes that losses are a result of congestion and invokes leverages off TCP acknowledgments instead of generating he end-to-end performance degradation is associated with taining a smoothed round-trip time estimate, with a mini standard TCP's handling of error detection and retransmis- mum timeout granularity of 200 ms to limit the overhead of sion. We used the SMArT-based scheme [17] only for the processing timer events. This still allows the LL scheme to LAN experiments. This scheme is well-suited to situations retransmit packets several times before a typical TCP Reno transmitter would time out. LL is equivalent to the snoop one-hop wireless systems such as ours. Unlike the scheme agent that does not suppress any duplicate acknowledg- proposed in [17], we do not use any special techniques to ments, and does not attempt in-order delivery of packets detect the loss of a retransmission the sender retransmits a across the link(unlike protocols proposed in [15],[22) packet when it receives a SMART acknowledgment only if While the use of TCP acknowledgments by our LL protocol the same packet was not retransmitted within the last round- renders it atypical of traditional ARQ protocols, we believe trip time. If no further SMART acknowledgments arrive, the that it still preserves the key feature of such protocols: the sender falls back to the coarse timeout mechanism to ability to retransmit packets locally, independently of and ecover from the loss. We used the IETF selective acknowl- on a much faster time scale than TCP. Therefore, we expect edgement scheme both for the Lan and the wan experi- the qualitative aspects of our results to be applicable to gen- ments. Our implementation is based on the RFC and takes eral link-layer protocols appropriate congestion control actions upon receiving SACK information [41 We also investigated a more sophisticated link-layer proto- col (Ll-SMART) that uses selective retransmissions to The E2E-ELN protocol adds an Explicit Loss Notification improve performance. The LL-SMART protocol performs (ELN) option to TCP acknowledgments. When a packet is this by applying a SMART-based acknowledgment scheme dropped on the wireless link, future cumulative acknowl- at the link layer. Like the LL protocol, LL-SMART uses edgments corresponding to the lost packet are marked to TCP acknowledgments instead of generating its own and identify that a non-congestion related loss has occurred. limits its minimum timeout to 200 ms. LL-SMART is Upon receiving this information with duplicate acknowl- equivalent to the snoop agent performing retransmissions edgments, the sender may perform retransmissions without based on selective acknowledgements but not suppressing invoking the associated congestion-control procedures. This duplicate acknowledgments at the base station

generates messages that result in loss recovery. Although this figure only shows data packets being lost, our experi￾ments have wireless errors in both directions. 3.1 End-To-End Schemes Although a wide variety of TCP versions are used on the Internet, the current de facto standard for TCP implementa￾tions is TCP Reno [26]. We call this the E2E protocol, and use it as the standard basis for performance comparison. The E2E-NEWRENO protocol improves the performance of TCP-Reno after multiple packet losses in a window by remaining in fast recovery mode if the first new acknowl￾edgment received after a fast retransmission is “partial”, i.e, is less than the value of the last byte transmitted when the fast retransmission was done. Such partial acknowledge￾ments are indicative of multiple packet losses within the original window of data. Remaining in fast recovery mode enables the connection to recover from losses at the rate of one segment per round trip time, rather than stall until a coarse timeout as TCP-Reno often would [9, 12]. The E2E-SMART and E2E-IETF-SACK protocols add SMART-based and IETF selective acknowledgments respectively to the standard TCP Reno stack. This allows the sender to handle multiple losses within a window of out￾standing data more efficiently. However, the sender still assumes that losses are a result of congestion and invokes congestion control procedures, shrinking its congestion window size. This allows us to identify what percentage of the end-to-end performance degradation is associated with standard TCP’s handling of error detection and retransmis￾sion. We used the SMART-based scheme [17] only for the LAN experiments. This scheme is well-suited to situations where there is little reordering of packets, which is true for one-hop wireless systems such as ours. Unlike the scheme proposed in [17], we do not use any special techniques to detect the loss of a retransmission. The sender retransmits a packet when it receives a SMART acknowledgment only if the same packet was not retransmitted within the last round￾trip time. If no further SMART acknowledgments arrive, the sender falls back to the coarse timeout mechanism to recover from the loss. We used the IETF selective acknowl￾edgement scheme both for the LAN and the WAN experi￾ments. Our implementation is based on the RFC and takes appropriate congestion control actions upon receiving SACK information [4]. The E2E-ELN protocol adds an Explicit Loss Notification (ELN) option to TCP acknowledgments. When a packet is dropped on the wireless link, future cumulative acknowl￾edgments corresponding to the lost packet are marked to identify that a non-congestion related loss has occurred. Upon receiving this information with duplicate acknowl￾edgments, the sender may perform retransmissions without invoking the associated congestion-control procedures. This option allows us to identify what percentage of the end-to￾end performance degradation is associated with TCP’s incorrect invocation of congestion control algorithms when it does a fast retransmission of a packet lost on the wireless hop. The E2E-ELN-RXMT protocol is an enhancement of the previous one, where the sender retransmits the packet on receiving the first duplicate acknowledgement with the ELN option set (as opposed to the third duplicate acknowledge￾ment in the case of TCP Reno), in addition to not shrinking its window size in response to wireless losses. In practice, it might be difficult to identify which packets are lost due to errors on a lossy link. However, in our exper￾iments we assume sufficient knowledge at the receiver about wireless losses to generate ELN information. We describe some possible implementation policies and strate￾gies for the ELN mechanism in Section 5.2. 3.2 Link-Layer Schemes Unlike TCP for the transport layer, there is no de facto stan￾dard for link-layer protocols. Existing link-layer protocols choose from techniques such as Stop-and-Wait, Go-Back-N, Selective Repeat and Forward Error Correction to provide reliability. Our base link-layer algorithm, called LL, uses cumulative acknowledgments to determine lost packets that are retransmitted locally from the base station to the mobile host. To minimize overhead, our implementation of LL leverages off TCP acknowledgments instead of generating its own. Timeout-based retransmissions are done by main￾taining a smoothed round-trip time estimate, with a mini￾mum timeout granularity of 200 ms to limit the overhead of processing timer events. This still allows the LL scheme to retransmit packets several times before a typical TCP Reno transmitter would time out. LL is equivalent to the snoop agent that does not suppress any duplicate acknowledg￾ments, and does not attempt in-order delivery of packets across the link (unlike protocols proposed in [15], [22]). While the use of TCP acknowledgments by our LL protocol renders it atypical of traditional ARQ protocols, we believe that it still preserves the key feature of such protocols: the ability to retransmit packets locally, independently of and on a much faster time scale than TCP. Therefore, we expect the qualitative aspects of our results to be applicable to gen￾eral link-layer protocols. We also investigated a more sophisticated link-layer proto￾col (LL-SMART) that uses selective retransmissions to improve performance. The LL-SMART protocol performs this by applying a SMART-based acknowledgment scheme at the link layer. Like the LL protocol, LL-SMART uses TCP acknowledgments instead of generating its own and limits its minimum timeout to 200 ms. LL-SMART is equivalent to the snoop agent performing retransmissions based on selective acknowledgements but not suppressing duplicate acknowledgments at the base station

Our experimental testbed consists of IBM ThinkPad laptops ng BSD/OS) and Pentium-based personal computers running BSD/OS 2.1 from bsdl. The machines are interconnected a10 TCP Rece Mbps ethernet and 915 MHz at&T WaveLANs [271,a 2 Mbps WaveLAN Y ning Silos) shared-medium wireless Lan with a raw signalling band (lossy link Pentium-based Pc width of 2 Mbps. The network topology for our experiments is shown in Figure 2. The peak throughput for TCP bulk transfers is 1. 5 Mbps in the local area testbed and 1 Mbps in the wide area testbed in the absence of congestion tional 16 Internet hops between the souree and base sta- or wireless losses. These testbed topologies represent typi Figure 2. Experimental topology. There were an addi- cal scenarios of wireless links and mobile hosts such as cel- tion during the WAN experiments lular wireless networks. In addition, our experiments focus on data transfer to the mobile host. which is the common We added TCP awareness to both the LL and LL-SMArT case for mobile applications (e.g, Web accesses) protocols, resulting in the LL-TCP-AWARE and lL- SMART-TCP-AWARE schemes. The LL-TCP-AWARE In order to measure the performance of the protocols under protocol is identical to the snoop protocol, while the LL- controlled conditions, we generate errors on the lossy link SMART-TCP-AWARE protocol uses SMART-based tech- using an exponentially distributed bit-error model. The niques for further optimization using selective repeat. LL- receiving entity on the lossy link generates an exponential SMART-TCP-AWARE iS the best link-layer protocol in our distribution for each bit-error rate and changes the tcp experiments- it performs local retransmissions based on checksum of the packet if the error generator determines selective acknowledgments and shields the sender from that the packet should be dropped. Losses are generated in duplicate acknowledgments caused by wireless losses both directions of the wireless channel. so tcp acknowl edgments are dropped too. The TCP data packet size in 3.3 Split-Connection Schemes experiments is 1400 bytes. We first measure and analyze the Like i-tcp our sPlit scheme uses an intermediate host to performance of the various protocols at an average error rate of one every 64 KBytes(this corresponds to a bit-error rate divide a TCP connection into two separate TCP connec- of about 1.9x10-6) Note that since the exponential distribu ions. The implementation avoids data copying in the inter tion has a standard deviation equal to its mean, there are mediate host by passing the pointers to the same buffer several occasions when multiple packets are lost in close between the two TCP connections. A variant of the SPLIT succession. We then report the results of some burst error approach we investigated, SPLIT-SMART, uses a SMART- situations, where between two and six packets are dropped based selective acknowledgment scheme on the wireless connection to perform selective retransmissions. There is formance of many of these protocols across a range of erro little chance of reordering of packets over the wireless con- rates from one every 16 KB to one every 256 KB. The nection since the intermediate host is only one hop away choice of the exponentially distributed error model is moti from the final destination vated by our desire to understand the precise dynamics of each protocol in response to a wireless loss, and is not an 4. Experimental Results attempt to empirically model a wireless channel. While the actual performance numbers will be a function of the exact In this section, we describe the experiments we performed error model, the relative performance is dependent on how and the results we obtained, including detailed explanations the protocol behaves after one or more losses in a single for observed performance. We start by describing the exper- TCP window. Thus, we expect our overall conclusions to be imental testbed and methodology. We then describe the per- pplicable under other patterns of wireless loss as well formance of the various link-layer, end-to-end and split- Finally, we believe that though wireless errors are generated artificially in our experiments, the use of a real testbed still valuable in that it introduces realistic effects such as 4.1 Experimental Methodolog wireless bandwidth limitation. media access contention We performed several experiments to determine the protocol processing delays, etc, which are hard to model mance and efficiency of each of the protocols. The realistically in a simulation cols were implemented as a set of modifications to the In our experiments, we attempt to ensure that losses are only OS TCP/IP(Reno)network stack. To ensure a fair basis for due to wireless errors(and not congestion). This allows us comparison, none of the protocols implementations intro- to focus on the effectiveness of the mechanisms in handling duce any additional data copying at intermediate points such losses. The WAN experiments are performed across 16 from sender to receiver

We added TCP awareness to both the LL and LL-SMART protocols, resulting in the LL-TCP-AWARE and LL￾SMART-TCP-AWARE schemes. The LL-TCP-AWARE protocol is identical to the snoop protocol, while the LL￾SMART-TCP-AWARE protocol uses SMART-based tech￾niques for further optimization using selective repeat. LL￾SMART-TCP-AWARE is the best link-layer protocol in our experiments — it performs local retransmissions based on selective acknowledgments and shields the sender from duplicate acknowledgments caused by wireless losses. 3.3 Split-Connection Schemes Like I-TCP, our SPLIT scheme uses an intermediate host to divide a TCP connection into two separate TCP connec￾tions. The implementation avoids data copying in the inter￾mediate host by passing the pointers to the same buffer between the two TCP connections. A variant of the SPLIT approach we investigated, SPLIT-SMART, uses a SMART￾based selective acknowledgment scheme on the wireless connection to perform selective retransmissions. There is little chance of reordering of packets over the wireless con￾nection since the intermediate host is only one hop away from the final destination. 4. Experimental Results In this section, we describe the experiments we performed and the results we obtained, including detailed explanations for observed performance. We start by describing the exper￾imental testbed and methodology. We then describe the per￾formance of the various link-layer, end-to-end and split￾connection schemes. 4.1 Experimental Methodology We performed several experiments to determine the perfor￾mance and efficiency of each of the protocols. The proto￾cols were implemented as a set of modifications to the BSD/ OS TCP/IP (Reno) network stack. To ensure a fair basis for comparison, none of the protocols implementations intro￾duce any additional data copying at intermediate points from sender to receiver. Our experimental testbed consists of IBM ThinkPad laptops and Pentium-based personal computers running BSD/OS 2.1 from BSDI. The machines are interconnected using a 10 Mbps Ethernet and 915 MHz AT&T WaveLANs [27], a shared-medium wireless LAN with a raw signalling band￾width of 2 Mbps. The network topology for our experiments is shown in Figure 2. The peak throughput for TCP bulk transfers is 1.5 Mbps in the local area testbed and 1.35 Mbps in the wide area testbed in the absence of congestion or wireless losses. These testbed topologies represent typi￾cal scenarios of wireless links and mobile hosts, such as cel￾lular wireless networks. In addition, our experiments focus on data transfer to the mobile host, which is the common case for mobile applications (e.g., Web accesses). In order to measure the performance of the protocols under controlled conditions, we generate errors on the lossy link using an exponentially distributed bit-error model. The receiving entity on the lossy link generates an exponential distribution for each bit-error rate and changes the TCP checksum of the packet if the error generator determines that the packet should be dropped. Losses are generated in both directions of the wireless channel, so TCP acknowl￾edgments are dropped too. The TCP data packet size in our experiments is 1400 bytes. We first measure and analyze the performance of the various protocols at an average error rate of one every 64 KBytes (this corresponds to a bit-error rate of about 1.9x10-6 ). Note that since the exponential distribu￾tion has a standard deviation equal to its mean, there are several occasions when multiple packets are lost in close succession. We then report the results of some burst error situations, where between two and six packets are dropped in every burst (Section 4.5). Finally, we investigate the per￾formance of many of these protocols across a range of error rates from one every 16 KB to one every 256 KB. The choice of the exponentially distributed error model is moti￾vated by our desire to understand the precise dynamics of each protocol in response to a wireless loss, and is not an attempt to empirically model a wireless channel. While the actual performance numbers will be a function of the exact error model, the relative performance is dependent on how the protocol behaves after one or more losses in a single TCP window. Thus, we expect our overall conclusions to be applicable under other patterns of wireless loss as well. Finally, we believe that though wireless errors are generated artificially in our experiments, the use of a real testbed is still valuable in that it introduces realistic effects such as wireless bandwidth limitation, media access contention, protocol processing delays, etc., which are hard to model realistically in a simulation. In our experiments, we attempt to ensure that losses are only due to wireless errors (and not congestion). This allows us to focus on the effectiveness of the mechanisms in handling such losses. The WAN experiments are performed across 16 TCP Source 10 Mbps Ethernet TCP Receiver 2 Mbps WaveLAN (lossy link) Pentium-based PC running BSD/OS) Base Station (Pentium PC running BSD/OS) (Pentium laptop running BSD/OS) Figure 2. Experimental topology. There were an addi￾tional 16 Internet hops between the source and base sta￾tion during the WAN experiments

Wired Goodput reless Goodput LAN: Absolute□ Percentage of max□ 100 WAN: Absolute Percentage of max Throughput 三 LL-TCP-AWARE LL-SMART LL-SMART-TCP-AWARE Figure 3. Performance of link-layer protocols: bit-error rate=1.9x10(I error/65536 bytes), socket buffer size= 32 KB. For each case there are two bars: the thick one corresponds to the scale on the left and denotes the throughput in Mbps: the thin one corresponds to the scale on the right and shows the throughput as a percentage of the maximum, i.e. in the absence of wireless errors(1.5 Mbps in the Lan environment and 1.35 Mbps in the WAN environment). Internet hops with minimal congestion" in order to study the the link and transport layers often lead to significant perfor impact of large delay-bandwidth products mance degradation. However, this is not the dominating effect when link layer schemes, such as LL, are used with Each run in the experiment consists of an 8 MByte transfer TCP Reno and its variants. These TCP implementations from the source to receiver across the wired net and the have coarse retransmission timeout granularities that WaveLAN link. We chose this rather long transfer size in order to limit the impact of transient behavior at the start of typically multiples of 500 ms, while link-layer protocols a TCP connection. During each run, we measure the typically have much finer timeout granularities. The real problem is that when packets are lost, link-layer protocol throughput at the receiver in Mbps, and the wired and wire- that do not attempt in-order delivery across the link(e.g less goodputs as percentages. In addition, all packet trans- LL) cause packets to reach the TCP receiver out-of-order missions on the ethernet and waveLan are recorded for This leads to the generation of duplicate acknowledgments nalysis using tcpdump [201, and the sender's TCP code by the TCP receiver, which causes the sender to invoke fast instrumented to record events such as coarse timeouts retransmission and recovery. This can potentially cause retransmission times, duplicate acknowledgment arrivals, degraded throughput and goodput, especially when the congestion window size changes, etc. The rest of this sec tion presents and discusses the results of these experiments delay-bandwidth product is large Our results substantiate this claim, as can be seen by com- 4.2 Link-Laver Protocols paring the LL and LL-TCP-AWARE results(Figure 3 and Traditional link-layer protocols operate independently of Table 2). For a packet size of 1400 bytes, a bit error rate of 1.9x10-0(1/65536 bytes)translates to a packet error rate of the higher-layer protocol, and consequently, do not neces- about 2.2 to 2.3%. Therefore, an optimal link-layer protocol sarily shield the sender from the lossy link. In spite of local that recovers from errors locally and does not compete with retransmissions, TCP performance could be poor for two TCP retransmissions should have a wireless goodput of tting of timers wo lay ers. an sary invocations of the TCP fast retransmission mechanism gestion. In the LAN experiments, the throughput difference between LL and LL-TCP-AWARE is about 10%. however due to out-of-order delivery of data In[10], the effects or the LL wireless goodput is only 95.5%, significantly less the first situation are simulated and analyzed for a TCP-like than LL- TCP-AWARE's wireless goodput of97.6%,which transport protocol (that closely tracks the round-trip time to set its retransmission timeout) and a reliable link-layer pro- is close to the maximum achievable goodput. When a loss tocol. The conclusion was that unless the packet loss rate is high(more than about 10%), competing retransmissions by atively quickly. However, enough packets are typically in transit to create more than 3 duplicate acknowledgments These duplicates eventually propagate to the sender and 2. WAN experiments across the US were performed between 10 trigger a fast retransmission and the associated congestion pm and 4 am, PST and we verified that no congestion losses control mechanisms. These fast retransmissions result in occurred in the runs reported

Internet hops with minimal congestion2 in order to study the impact of large delay-bandwidth products. Each run in the experiment consists of an 8 MByte transfer from the source to receiver across the wired net and the WaveLAN link. We chose this rather long transfer size in order to limit the impact of transient behavior at the start of a TCP connection. During each run, we measure the throughput at the receiver in Mbps, and the wired and wire￾less goodputs as percentages. In addition, all packet trans￾missions on the Ethernet and WaveLan are recorded for analysis using tcpdump [20], and the sender’s TCP code instrumented to record events such as coarse timeouts, retransmission times, duplicate acknowledgment arrivals, congestion window size changes, etc. The rest of this sec￾tion presents and discusses the results of these experiments. 4.2 Link-Layer Protocols Traditional link-layer protocols operate independently of the higher-layer protocol, and consequently, do not neces￾sarily shield the sender from the lossy link. In spite of local retransmissions, TCP performance could be poor for two reasons: (i) competing retransmissions caused by an incom￾patible setting of timers at the two layers, and (ii) unneces￾sary invocations of the TCP fast retransmission mechanism due to out-of-order delivery of data. In [10], the effects of the first situation are simulated and analyzed for a TCP-like transport protocol (that closely tracks the round-trip time to set its retransmission timeout) and a reliable link-layer pro￾tocol. The conclusion was that unless the packet loss rate is high (more than about 10%), competing retransmissions by the link and transport layers often lead to significant perfor￾mance degradation. However, this is not the dominating effect when link layer schemes, such as LL, are used with TCP Reno and its variants. These TCP implementations have coarse retransmission timeout granularities that are typically multiples of 500 ms, while link-layer protocols typically have much finer timeout granularities. The real problem is that when packets are lost, link-layer protocols that do not attempt in-order delivery across the link (e.g., LL) cause packets to reach the TCP receiver out-of-order. This leads to the generation of duplicate acknowledgments by the TCP receiver, which causes the sender to invoke fast retransmission and recovery. This can potentially cause degraded throughput and goodput, especially when the delay-bandwidth product is large. Our results substantiate this claim, as can be seen by com￾paring the LL and LL-TCP-AWARE results (Figure 3 and Table 2). For a packet size of 1400 bytes, a bit error rate of 1.9x10-6 (1/65536 bytes) translates to a packet error rate of about 2.2 to 2.3%. Therefore, an optimal link-layer protocol that recovers from errors locally and does not compete with TCP retransmissions should have a wireless goodput of 97.7% and a wired goodput of 100% in the absence of con￾gestion. In the LAN experiments, the throughput difference between LL and LL-TCP-AWARE is about 10%. However, the LL wireless goodput is only 95.5%, significantly less than LL-TCP-AWARE’s wireless goodput of 97.6%, which is close to the maximum achievable goodput. When a loss occurs, the LL protocol performs a local retransmission rel￾atively quickly. However, enough packets are typically in transit to create more than 3 duplicate acknowledgments. These duplicates eventually propagate to the sender and trigger a fast retransmission and the associated congestion control mechanisms. These fast retransmissions result in 2. WAN experiments across the US were performed between 10 pm and 4 am, PST and we verified that no congestion losses occurred in the runs reported. LL LL-TCP-AWARE LL-SMART LL-SMART-TCP-AWARE Throughput (Mbps) Wireless Goodput LAN: Absolute Wired Goodput Figure 3. Performance of link-layer protocols: bit-error rate = 1.9x10-6 (1 error/65536 bytes), socket buffer size = 32 KB. For each case there are two bars: the thick one corresponds to the scale on the left and denotes the throughput in Mbps; the thin one corresponds to the scale on the right and shows the throughput as a percentage of the maximum, i.e. in the absence of wireless errors (1.5 Mbps in the LAN environment and 1.35 Mbps in the WAN environment). Throughput 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Percentage of max. WAN: Absolute Percentage of max. Throughput (% of maximum) 0 10 20 30 40 50 60 70 80 90 100 95.5 97.9 1.20 95.5 98.4 0.82 97.6 100.0 1.36 97.6 100.0 1.19 95.5 98.3 1.29 95.3 99.4 0.93 97.7 100.0 1.39 97.6 100.0 1.22

LL-SMART-TCP- LL LL-TCP-AWARE LL-SMART AWARE LAN (8 KB) 1.20(956%,97.9%) 129(976%6100%0129(%%989%)137(976%100% LAN(32KB)120(95.5%979% 1.36(97.6%,1009 29(955%.983%)1.39(977%100% WAN(32KB)0.82(95.5%984%)119(976%100%)093(953%9949)122(97.6%.009 Table 2. This table summarizes the results for the link-layer schemes for an average error rate of one every 65536 bytes of data. Each entry is of the form: throughput (wireless goodput, wired goodput). Throughput is measured in Mbps. Goodput is expressed as a percentage. 65536 65536 LL-TCP-AWARE 57344 49152 49152 32768 32768 =24576 24576 16384 s8192 8192 1020304050607080 ime(sec) Figure 4. Congestion window size for link-layer protocols in wide area tests. The horizontal dashed line in the ll graph shows the 23000 byte WAN bandwidth-delay prod g8e+06 LL-TCP-AWARE 三 1e+06 Wireless retransmissions Wired, retransmissions 1e+06 010203imc°06050 01020304050607080 Time(sec) Figure 5. Packet sequence traces for LL-TCP-AWARE and LL. No coarse timeouts occur in either case For LL-TCP- AWARE, the horizontal row of dots shows the times of wireless link retransmissions For Ll, the top row shows sender fast retransmission times and the bottom row shows both local wireless and sender retransmissions reduced goodput; about 90% of the lost packets are retrans- dow and the receiver advertised window. This is bounded mitted by both the source and the base station by the receiver's socket buffer size. In the congestion win- The effects of this interaction are much more pronounced in dow graphs for each protocol, the receiver socket buffer is the wide-area experiments- the throughput difference is 32KB bout 30% in this case. The cause for the more pronounced In the wide area, the bandwidth-delay product is about deterioration in performance is the higher bandwidth-delay 23000 bytes(1.35 Mbps*135 ms), and the congestion win- product of the wide-area connection. The LL scheme causes dow drops below this value several times during each TCP the sender to invoke congestion control procedures often transfer. On the other hand, the lan experiments do no due to duplicate acknowledgments and causes the average suffer from such a large throughput degradation because window size of the transmitter to be lower than for LL-TCP- LLs lower congestion-window size is usually still larger AWARE. This is shown in Figure 4, which compares the than the connections delay-bandwidth product of about congestion window size of LL and LL-TCP-AWARE as a 1900 bytes(1.5 Mbps*10 ms). Therefore, the LL scheme function of time. Note that the number of outstanding data can maintain a nearly full"data pipe between the sender bytes in the network is the minimum of the congestion win- and receiver in the local connection but not in the wide area

reduced goodput; about 90% of the lost packets are retrans￾mitted by both the source and the base station. The effects of this interaction are much more pronounced in the wide-area experiments — the throughput difference is about 30% in this case. The cause for the more pronounced deterioration in performance is the higher bandwidth-delay product of the wide-area connection. The LL scheme causes the sender to invoke congestion control procedures often due to duplicate acknowledgments and causes the average window size of the transmitter to be lower than for LL-TCP￾AWARE. This is shown in Figure 4, which compares the congestion window size of LL and LL-TCP-AWARE as a function of time. Note that the number of outstanding data bytes in the network is the minimum of the congestion win￾dow and the receiver advertised window. This is bounded by the receiver’s socket buffer size. In the congestion win￾dow graphs for each protocol, the receiver socket buffer is 32KB. In the wide area, the bandwidth-delay product is about 23000 bytes (1.35 Mbps * 135 ms), and the congestion win￾dow drops below this value several times during each TCP transfer. On the other hand, the LAN experiments do not suffer from such a large throughput degradation because LL’s lower congestion-window size is usually still larger than the connection’s delay-bandwidth product of about 1900 bytes (1.5 Mbps * 10 ms). Therefore, the LL scheme can maintain a nearly full “data pipe” between the sender and receiver in the local connection but not in the wide area LL LL-TCP-AWARE LL-SMART LL-SMART-TCP￾AWARE LAN (8 KB) 1.20 (95.6%,97.9%) 1.29 (97.6%,100%) 1.29 (96.1%,98.9%) 1.37 (97.6%,100%) LAN (32 KB) 1.20 (95.5%,97.9%) 1.36 (97.6%,100%) 1.29 (95.5%,98.3%) 1.39 (97.7%,100%) WAN (32 KB) 0.82 (95.5%,98.4%) 1.19 (97.6%,100%) 0.93 (95.3%,99.4%) 1.22 (97.6%,100%) Table 2. This table summarizes the results for the link-layer schemes for an average error rate of one every 65536 bytes of data. Each entry is of the form: throughput (wireless goodput, wired goodput). Throughput is measured in Mbps. Goodput is expressed as a percentage. LL-TCP-AWARE Figure 4. Congestion window size for link-layer protocols in wide area tests. The horizontal dashed line in the LL graph shows the 23000 byte WAN bandwidth-delay product. LL 0 8192 16384 24576 32768 40960 49152 57344 65536 Congestion Window (bytes) 0 10 20 30 40 50 60 70 80 Time (sec) 0 8192 16384 24576 32768 40960 49152 57344 65536 Congestion Window (bytes) 0 10 20 30 40 50 60 70 80 Time (sec) Figure 5. Packet sequence traces for LL-TCP-AWARE and LL. No coarse timeouts occur in either case. For LL-TCP￾AWARE, the horizontal row of dots shows the times of wireless link retransmissions. For LL, the top row shows sender fast retransmission times and the bottom row shows both local wireless and sender retransmissions. Wired retransmissions Wireless retransmissions Wireless retransmissions LL-TCP-AWARE LL 0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06 7e+06 8e+06 9e+06 0 10 20 30 40 50 60 70 80 Sequence Number (bytes) Time (sec) 0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06 7e+06 8e+06 9e+06 Sequence Number (bytes) 0 10 20 30 40 50 60 70 80 Time (sec)

LAN: Absolute L Percentage of maxD WAN: Absolute 1 Percentage of max180 975 三 目目8 0.2 E2E E2E-NEWRENO E2E-SMART E2E-IETF- E2E-ELN E2E-ELNRXMT SACK Figure 6. Performance of end-to-end protocols: bit error rate=1.9x10(I error/65536 bytes). E2E- E2E-IETF E2E-ELN NEWRENO E2E-SMAR SACK E2E-ELN RXMT LAN(8KB)055(970,90)06(97.3973)1.12(976976)0.68(973,97.3)069(973,972)0.6(974973) LAN(32KB)070(975975)0.89(977973)1.25(97.2972)1.12(97.5,97.5)093(975,975)0.95(97975) AN(32KB)031(973973)064(975,975)NA 080(97.5975)064(976976)0.72(97974) Table 3. This table summarizes the results for the end-to-end schemes for an average error rate of one every 65536 bytes of data. The numbers in the cells follow the same convention as in Table 2. gradation is almost entirely due to puts close to the opti value excessive retransmissions over the wireless link and to the reason for the low throughput is the large number of time smaller average congestion window size compared to LL- outs that occur during the transfer( Figure 7). The resulting TCP-AWARE. Another important point to note is that LL average window size during the transfer is small, preventing successfully prevents coarse timeouts from happening at the the "data pipe " from being kept full and reducing the effec- source. Figure 5 shows the sequence traces of TCP transfers tiveness of the fast retransmission mechanism(Figure 8) for LL-TCP-AWARE and LL The modified end-to-end protocols improve throughput by In summary, our results indicate that a simple link-layer retransmitting packets known to have been lost on the wire- retransmission scheme does not entirely avoid the adverse less hop earlier than they would have been by the baseline ffects of TCP fast retransmissions and the consequent per- E2E protocol, and by reducing the fluctuations in window formance degradation. An enhanced link-layer scheme that size. The E2E-NEWRENO, E2E-ELN, E2E-SMART and uses knowledge of TCP semantics to prevent duplicate E2E-IETF-SACK protocols each use new TCP options and acknowledgments caused by wireless losses from reaching more sophisticated acknowledgment processing techniques the sender and locally retransmits packets achieves signifi- to improve the speed and accuracy of identifying and antly better performance retransmitting lost packets, as well as by recovering from multiple losses in a single transmission window without 4.3 End-To-End Protocols timing out. The remainder of this section discusses the ben- efits of three techniques- partial acknowledgments The performance of the various end-to-end protocols is summarized in Figure 6 and Table 3. The performance of explicit loss notifications, and selective acknowledgments TCP Reno, the baseline E2E protocol, highlights the prob- Partial acknowledgments: E2E-NEWRENO, which uses lems with TCP over lossy links. At a 2.3% packet loss rate partial acknowledgment information to recover from multi (as explained in Section 4.2), the E2E protocol achieves a ple losses in a window at the rate of one packet per round throughput of less than 50% of the maximum(i.e, through- trip time, performs between 10 and 25% better than E2E put in the absence of wireless losses) in the local-area and over a lan and about 2 times better than E2E in the WAN less than 25% of the maximum in the wide-area experi- experiments. The performance improvement is a function of ments. However, all the end-to-end protocols achieve good he socket buffer size- the larger the buffer size, the better

one. The 10% LAN degradation is almost entirely due to the excessive retransmissions over the wireless link and to the smaller average congestion window size compared to LL￾TCP-AWARE. Another important point to note is that LL successfully prevents coarse timeouts from happening at the source. Figure 5 shows the sequence traces of TCP transfers for LL-TCP-AWARE and LL. In summary, our results indicate that a simple link-layer retransmission scheme does not entirely avoid the adverse effects of TCP fast retransmissions and the consequent per￾formance degradation. An enhanced link-layer scheme that uses knowledge of TCP semantics to prevent duplicate acknowledgments caused by wireless losses from reaching the sender and locally retransmits packets achieves signifi￾cantly better performance. 4.3 End-To-End Protocols The performance of the various end-to-end protocols is summarized in Figure 6 and Table 3. The performance of TCP Reno, the baseline E2E protocol, highlights the prob￾lems with TCP over lossy links. At a 2.3% packet loss rate (as explained in Section 4.2), the E2E protocol achieves a throughput of less than 50% of the maximum (i.e., through￾put in the absence of wireless losses) in the local-area and less than 25% of the maximum in the wide-area experi￾ments. However, all the end-to-end protocols achieve good￾puts close to the optimal value of 97.7%. The primary reason for the low throughput is the large number of time￾outs that occur during the transfer (Figure 7). The resulting average window size during the transfer is small, preventing the “data pipe” from being kept full and reducing the effec￾tiveness of the fast retransmission mechanism (Figure 8). The modified end-to-end protocols improve throughput by retransmitting packets known to have been lost on the wire￾less hop earlier than they would have been by the baseline E2E protocol, and by reducing the fluctuations in window size. The E2E-NEWRENO, E2E-ELN, E2E-SMART and E2E-IETF-SACK protocols each use new TCP options and more sophisticated acknowledgment processing techniques to improve the speed and accuracy of identifying and retransmitting lost packets, as well as by recovering from multiple losses in a single transmission window without timing out. The remainder of this section discusses the ben￾efits of three techniques — partial acknowledgments, explicit loss notifications, and selective acknowledgments. Partial acknowledgments: E2E-NEWRENO, which uses partial acknowledgment information to recover from multi￾ple losses in a window at the rate of one packet per round￾trip time, performs between 10 and 25% better than E2E over a LAN and about 2 times better than E2E in the WAN experiments. The performance improvement is a function of the socket buffer size — the larger the buffer size, the better Throughput (Mbps) E2E E2E-NEWRENO E2E-SMART E2E-ELN E2E-ELNRXMT Figure 6. Performance of end-to-end protocols: bit error rate = 1.9x10-6 (1 error/65536 bytes). 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 Throughput (% of maximum) 0 10 20 30 40 50 60 70 80 90 E2E-IETF￾SACK LAN: Absolute Percentage of max. WAN: Absolute Percentage of max. 97.5 97.5 0.70 97.3 97.3 0.31 97.7 97.3 0.89 97.5 97.5 0.64 97.2 97.2 1.25 97.5 97.5 0.80 97.5 97.5 1.12 97.5 97.5 0.93 97.6 97.6 0.64 97.5 97.5 0.95 97.4 97.4 0.72 E2E E2E￾NEWRENO E2E-SMART E2E-IETF￾SACK E2E-ELN E2E-ELN￾RXMT LAN (8 KB) 0.55 (97.0,96.0) 0.66 (97.3,97.3) 1.12 (97.6,97.6) 0.68 (97.3,97.3) 0.69 (97.3,97.2) 0.86 (97.4,97.3) LAN (32 KB) 0.70 (97.5,97.5) 0.89 (97.7,97.3) 1.25 (97.2,97.2) 1.12 (97.5,97.5) 0.93 (97.5,97.5) 0.95 (97.5,97.5) WAN (32 KB) 0.31 (97.3,97.3) 0.64 (97.5,97.5) N.A. 0.80 (97.5,97.5) 0.64 (97.6,97.6) 0.72 (97.4,97.4) Table 3. This table summarizes the results for the end-to-end schemes for an average error rate of one every 65536 bytes of data. The numbers in the cells follow the same convention as in Table 2

E2E E2E-ELN 7e+06 已7e+0 L6e+06 4e+06 4e+06 2e+06 Fast retransmissions ast retransmissions 1e+06 1e+06 150 200 Time(sec) Time(sec Figure 7. Packet sequence traces for E2E ( TCP Reno)and E2E-ELN. The top row of horizontal dots shows the times when fast retransmissions occur: the bottom row shows the coarse timeouts. a65536 65536 E2E-ELN ≥49152 ≥49152 40960 40960 524576 824576 g8192 MwAk减 g8192 100 Figure 8. Congestion window size as a function of time for E2E (TCP Reno) and E2E-ELN. This figure clearly shows the utility of ELN in preventing rapid fluctuations, thereby maintaining a larger average congestion window size the relative performance. This is because in situations that mitting a packet, if it has eln information for it. The maxi- E2E suffers a coarse timeout for a loss, the probability that mum socket buffer size of 8 KB limits the number of E2E-NEWRENO does not, increases with the number of unacknowledged packets to a small number at any point in outstanding packets in the network time, which reduces the probability of three duplicate Explicit Loss Notification: One way of eliminating the long acknowledgments arriving after a loss and triggering a fast delays caused by coarse timeouts is to maintain as large a window size as possible. E2E-NEWRENO remains in fast Despite explicit awareness of wireless losses, timeouts recovery if the new acknowledgment is only partial, but sometimes occur in the ELN-based protocols. This is a reduces the window size to half its original value upon the result of our implementation of the eln protocol, which arrival of the first new acknowledgment. The E2E-ELN and does not convey information about multiple wireless-related E2E-ELN-RXMT protocols use ELn information losses to the sender. Since it is coupled with only cumula (Section 3. 1)to prevent the sender from reducing the size of tive acknowledgments, the sender is unaware of the occur the congestion window in response to a wireless loss. Both rence of multiple wireless-related losses in a window, we these schemes perform better than E2E-NEWRENO, and plan to couple SACKs and ELn together in future work sender's explicit awareness of the wireless link, which gies and policies for ELN possible implementation strate- over two times better than e2E. This is a result of the Section 5.2 discusses som reduces the number of coarse timeouts(Figure 7)and rapid window size fluctuations(Figure 8). The E2E-ELN-RXMT Selective acknowledgments: We experimented with two protocol performs only slightly better than E2E-ELN when different SACK schemes. In the LAN case, we used a sim- the socket buffer size is 32 KB. This is because there is usu- ple SACK scheme based on a subset of the SMArT pro- ally enough data in the pipe to trigger a fast retransmission posal. This protocol was the best of the end-to-end protocols for E2E-ELN. The performance benefits of E2E-ELN- in this situation, achieving a throughput of 1.25 Mbps(in RXMT are more pronounced when the socket buffer size is contrast. the best local scheme. LL-SMART-TCP-AWARE smaller as the numbers for the 8 KB socket buffer size indi obtained a throughput of 1.39 Mbps) cate(Table 3). This is because E2E-ELN-RXMT does not In the WAN case, we based our SACK implementation [4] wait for three duplicate acknowledgments before retrans- on RFC 2018. For the exponentially-distributed loss pattern

the relative performance. This is because in situations that E2E suffers a coarse timeout for a loss, the probability that E2E-NEWRENO does not, increases with the number of outstanding packets in the network. Explicit Loss Notification: One way of eliminating the long delays caused by coarse timeouts is to maintain as large a window size as possible. E2E-NEWRENO remains in fast recovery if the new acknowledgment is only partial, but reduces the window size to half its original value upon the arrival of the first new acknowledgment. The E2E-ELN and E2E-ELN-RXMT protocols use ELN information (Section 3.1) to prevent the sender from reducing the size of the congestion window in response to a wireless loss. Both these schemes perform better than E2E-NEWRENO, and over two times better than E2E. This is a result of the sender’s explicit awareness of the wireless link, which reduces the number of coarse timeouts (Figure 7) and rapid window size fluctuations (Figure 8). The E2E-ELN-RXMT protocol performs only slightly better than E2E-ELN when the socket buffer size is 32 KB. This is because there is usu￾ally enough data in the pipe to trigger a fast retransmission for E2E-ELN. The performance benefits of E2E-ELN￾RXMT are more pronounced when the socket buffer size is smaller, as the numbers for the 8 KB socket buffer size indi￾cate (Table 3). This is because E2E-ELN-RXMT does not wait for three duplicate acknowledgments before retrans￾mitting a packet, if it has ELN information for it. The maxi￾mum socket buffer size of 8 KB limits the number of unacknowledged packets to a small number at any point in time, which reduces the probability of three duplicate acknowledgments arriving after a loss and triggering a fast retransmission. Despite explicit awareness of wireless losses, timeouts sometimes occur in the ELN-based protocols. This is a result of our implementation of the ELN protocol, which does not convey information about multiple wireless-related losses to the sender. Since it is coupled with only cumula￾tive acknowledgments, the sender is unaware of the occur￾rence of multiple wireless-related losses in a window; we plan to couple SACKs and ELN together in future work. Section 5.2 discusses some possible implementation strate￾gies and policies for ELN. Selective acknowledgments: We experimented with two different SACK schemes. In the LAN case, we used a sim￾ple SACK scheme based on a subset of the SMART pro￾posal. This protocol was the best of the end-to-end protocols in this situation, achieving a throughput of 1.25 Mbps (in contrast, the best local scheme, LL-SMART-TCP-AWARE, obtained a throughput of 1.39 Mbps). In the WAN case, we based our SACK implementation [4] on RFC 2018. For the exponentially-distributed loss pattern Figure 7. Packet sequence traces for E2E (TCP Reno) and E2E-ELN. The top row of horizontal dots shows the times when fast retransmissions occur; the bottom row shows the coarse timeouts. 0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06 7e+06 8e+06 9e+06 0 50 100 150 200 250 Sequence Number (bytes) Time (sec) 0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06 7e+06 8e+06 9e+06 0 50 100 150 200 250 Sequence Number (bytes) Time (sec) E2E E2E-ELN Fast retransmissions Coarse timeouts Fast retransmissions Coarse timeouts Figure 8. Congestion window size as a function of time for E2E (TCP Reno) and E2E-ELN. This figure clearly shows the utility of ELN in preventing rapid fluctuations, thereby maintaining a larger average congestion window size. 0 8192 16384 24576 32768 40960 49152 57344 65536 0 50 100 150 200 250 Congestion Window (bytes) Time (sec) 0 8192 16384 24576 32768 40960 49152 57344 65536 0 50 100 150 200 250 Congestion Window (bytes) Time (sec) E2E E2E-ELN