«Von der Fakultät für Mathematik, Informatik und Naturwissenschaften der Rheinisch-Westfälischen Technischen Hochschule Aachen zur Erlangung des ...»
Eliminating Inefficient Cross-Layer Interactions
in Wireless Networking
Von der Fakultät für Mathematik, Informatik und Naturwissenschaften
der Rheinisch-Westfälischen Technischen Hochschule Aachen
zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften
Reiner Eric Ludwig
aus Bishop, California (USA)
Prof. Dr. rer. nat. Otto Spaniol
Prof. Randy H. Katz Ph.D. (University of California at Berkeley) Tag der mündlichen Prüfung: 04.04.2000 D 82 (Diss. RWTH Aachen) Acknowledgements Foremost, I want to thank my wife, Monika Ludwig, for her patience, faith, and support over the past five years.
I would like to thank Prof. O. Spaniol and Prof. R. H. Katz for their advice.
Many thanks to Almudena Konrad, Kimberly Oden, Bela Rathonyi, and Keith Sklower who contributed to the development of the measurement tools and the collection of many hours of traces.
This work greatly benefited from disscussions with Badri Badrinath, Hari Balakrishnan, Stephan Bauke, Jean Bolot, Mikael Degermark, David Eckhardt, Andreas Fasbender, Sally Floyd, Tom Henderson, Anthony Joseph, Roger Kalden, Phil Karn, Markku Kojo, Michael Meyer, Venkata Padmanabhan, and Vern Paxson.
Last but not least I want to thank Norbert Niebert, Frank Reichert, Olle Viktorsson, and Fiona Williams for supporting my work within Ericsson Research.
vii Table of Contents Chapter 1 Introduction and Outline 1 Chapter 2 Background 5
2.2 End-to-End Error Recovery with TCP
2.2.1 Basic Operation
2.2.2 TCP-Lite’s Retransmission Timer
2.2.3 TCP/IP Header Compression
2.3 End-to-End Congestion Control in the Internet
2.3.1 Objectives and Principles
2.3.2 Congestion Control in TCP
2.3.3 New Developments
2.4 Link Layer Error Control in Wireless Networks
2.4.1 Circuit-Switched Data Transmission in GSM
2.4.2 Handover Control
2.4.3 Link Layer Error Recovery
2.4.4 Forward Error Correction and Interleaving
2.5 The Problem: Inefficient Cross-Layer Interactions
2.5.1 Underestimation of the Available Bandwidth
2.5.2 Inefficiency of End-to-End Error Control
2.5.3 Overly Strong Link Layer Error Control
2.5.4 Competing Error Recovery
2.5.5 Failure of Link Layer Differential Encodings
2.6 Related Work
2.6.1 Classification of Existing Approaches
2.7 Brief Motivation and Outline of our Approach
5.2 The Eifel Algorithm
5.2.1 Resolving the Retransmission Ambiguity
5.2.2 The Sender’s Response
5.2.3 Performance Evaluation
5.3 Problems of TCP-Lite’s Retransmission Timer
5.3.1 Prediction Flaw when the RTT Drops
5.3.2 Failure of the “Magic Numbers”
5.3.3 The “REXMT-Restart Bug”
5.3.4 Timer Granularity
5.3.5 Validating the Model
5.4 The Eifel Retransmission Timer
5.4.1 Predicting a Decreasing RTT
5.4.2 Scaling the Estimator Gains and the Variation Weight
5.4.3 Shock Absorbers
5.4.4 The RTO Minimum
5.4.5 Implementing REXMT Precisely
5.4.6 Adapting to Spurious Timeouts
5.4.7 Validating the Implementation of RTO-Eifel
Appendix C Lebenslauf von Reiner Eric Ludwig 135 C.1 Angaben zur Person
C.2 Ausbildung und Beruflicher Werdegang
The Internet has evolved into the communication medium of the future. It will not be long before virtually all people-to-people, people-to-machine, and machine-to-machine communication are carried end-to-end in Internet Protocol (IP) [RFC791], [RFC2460] packets. The recent tremendous growth of the Internet in terms of connected hosts is only matched by the similar growth rate of cellular telephone subscribers. While most hosts on today’s Internet are still wired, the next big wave of hosts has yet to hit the Internet. We believe that the predominant Internet access of the future will be wireless. Not only every cellular phone, but the majority of general communication devices will have: (1) an IP protocol stack and (2) a wireless network interface.
Figure 1-1: Cross-Layer Interactions in Wireless Networking.
Wireless networking and more specifically, the problems related to protocol performance of “IP over Wireless”, are high priority research topics in both academia and industry. Yet, a number of difficult problems remain unsolved. The root of these lies in inefficient cross-layer interactions, caused by events occurring at the link layer that affect the performance of end-to-end error and congestion control schemes (see Figure 1-1). Those events are packet losses due to transmission error and increased packet transmission delays caused by link layer error control.
Internet traffic today is still largely generated by applications that use the Transmission Control Protocol (TCP) [RFC793] as the underlying communications protocol. The most popular Internet applications, namely World Wide Web (WWW), e-mail, and file transfer, all rely on TCP. In the Internet backbone studied in [TMW97], the authors find that TCP averages about 80 percent of the flows. Related traffic analysis studies find similar numbers. This motivates why TCP has been the focus when it comes to studying inefficient cross-layer interactions in wireless networking.
The solution we develop in this dissertation is, however, not “TCP-specific”, but is independent from any specific protocol. Nevertheless, to demonstrate the feasibility of our approach, most of our measurements, analysis, and implementation work is based on TCP. Our solution comprises new end-to-end and link layer mechanisms that make the protocol implementations on those layers more “intelligent” and robust. For flows that are loss responsive and fully-reliable, in particular those based on TCP, our solution eliminates all known inefficient cross-layer interactions. It provides optimal end-to-end performance over a wide range of conditions of the wireless link while efficiently utilizing radio resources. Beyond solving the problems for such flows, our solution provides a framework that accommodates loss responsive real-time flows, e.g., semi-reliable, or error-resilient flows.
Related work suggests solutions that are either pure end-to-end (e.g., [SF98]), leaving unexploited the potential of link layer error control schemes to optimize end-to-end performance, or only suggest link layer mechanisms (e.g., [BBKT97], [ES98], [Kar93]), none of which is capable of solving all inefficient interactions with end-to-end control schemes. Most prior work (e.g., [BB95], [BK98], [BS97], [DMT96], [HK99], [KRLKA97]), however, suggests Performance Enhancing Proxies (PEPs) that couple link layer and end-to-end control schemes to solve inefficient cross-layer interactions. These solutions violate the fundamental design principle in data communications, protocol layering, by requiring access to transport layer headers by the PEPs. Our approach is fundamentally different in that we do not require - in fact, we argue against - such cross-layer couplings. The key advantages of our solution over PEP-based approaches are (A) its independence from transport (or higher) layer protocol semantics making it a “non-TCP-specific” solution, (B) the possibility of co-existence with network layer encryption, e.g., IPsec [RFC2401], and (C) that no per-flow state needs to be maintained in the
network making it more scalable. The main contributions of this dissertation are the following:
1. The new concept of flow-adaptive wireless links and its application for fully-reliable flows. This work has been published in [LR99], [LRKOJ99], and [LKJK00].
2. Two new mechanisms for reliable end-to-end protocols, the Eifel algorithm and the Eifel retransmission timer. The former has been published in [LK00] while the latter is described in [LS99]. We have implemented both mechanisms for TCP, and refer to that implementation as TCP-Eifel that we have made publicly available [Lud99c].
3. New measurement methods and tools we developed throughout our work.
Introduction and Outline 3 The remainder of this chapter describes and motivates the outline of this dissertation.
Chapter 2 provides required background. After we introduce related terminology in Section 2.1, the following three sections review those functions of the control schemes shown in Figure 1-1 that are relevant for our studies. Since all our “real-world” measurements in wireless networks were carried out using GSM-CSD, the Circuit-Switched Data (CSD) service implemented in the Global System for Mobile communications (GSM), we explain that network in more detail. In Section 2.5 we describe all inefficient cross-layer interactions in wireless networking that are known in literature. Related work is reviewed and evaluated in Section 2.6. We present a brief motivation and outline of the approach taken in this dissertation in Section 2.7.
Chapter 3 explains the analysis methodology we applied and the tools we developed to obtain the results presented in Chapter 4 and Chapter 5. We first motivate why we have mostly chosen a measurement-based analysis approach. In Section 3.1, we then explain the methodology we use in Section 4.3 to evaluate the benefit of link layer error recovery for reliable flows. We explain how we capture and analyze the error characteristics of the GSM-CSD wireless link.
Our ReTracer tool is described, which we developed to reverse-engineer target metrics such as throughput given certain parameters like the link layer frame size. In Section 3.2, we explain the methodology we use in Section 4.2 to detect inefficient cross-layer interactions between TCP and the link layer error control implemented in GSM-CSD. We describe the tools we developed for that purpose: rlpdump, an event logging tool for the reliable link layer protocol implemented in GSM-CSD, and MultiTracer, used to correlated events on different protocol layers. There we also explain how to interpret TCP trace plots, which we often use to illustrate certain effects, problems, or solutions. In Section 3.3, we explain the methodology we use in Section 5.1 to study the problem of competing error recovery for the case of TCP, and to develop the Eifel algorithm in Section 5.2 that eliminates this problem. We explain how we used the hiccup tool that we developed to reproduce inefficient cross-layer interactions in a “non-wireless” but controllable network environment. In Section 3.4, we explain the methodology we use in Section 5.3 to study and reveal the problems of TCP-Lite’s retransmission timer. We use the same model in Section 5.4 to develop the Eifel retransmission timer that eliminates those problems. We explain the model that we developed to analyze those end-toend retransmission timers, and the measurement setup we used to validate the correctness of the model. In Section 3.5, we provide a summary of the chapter.
Chapter 4 introduces the concept of flow-adaptive wireless links, and validates it for fully-reliable flows. In Section 4.1, we explain that concept and discuss its deployment concerns, and possible implementation alternatives. The key idea is that network end-points use the IP layer as a level of indirection through which their QoS requirements are signalled to each link layer along the path, on a per packet basis. This allows for a (wireless) link layer to adapt its error _________________________________________________________________________________________________