Network Working Group Choong Seon Hong Internet-Draft Kyung Hee University Expires: April 16, 2006 Hyung-Keun Ryu KT Advanced Technology Lab October 16, 2005 A TCP for Heterogeneous Networks draft-hong-tcp-for-heterogeneous-networks-00.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on April 16, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abtract Based on incorporating the ECN - Explicit Congestion Notification [RFC3168] and the end-to-end Available Bandwidth Estimation, TCP for heterogeneous networks accommodates a way for TCP sender to be ability of distinguishing the wireless packet losses from the congestion packet losses, as well as estimating of the available bandwidth to adjust transmission rate when the neworks become congested. Hong & Ryu Expires April 16, 2006 [Page 1] Internet-Draft A TCP for Heterogeneous Networks October, 2005 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . 2 2. Proposed approaches for the last wireless hop . . . . . . . . 3 2.1 Link layer approachs . . . . . . . . . . . . . . . . . . . 3 2.2 Transport layer approach . . . . . . . . . . . . . . . . . 3 2.3 Split-connection approach . . . . . . . . . . . . . . . . 4 3. Explicit Congestion Notifications . . . . . . . . . . . . . 4 4. End-to-End bandwidth estimation . . . . . . . . . . . . . 5 5. TCP for heterogeneous networks . . . . . . . . . . . . . . . 6 5.1 Algorithm after receiving ACK or n DupACKs . . . . . . . 6 5.2 Algorithm after timeout expiration . . . . . . . . . . . . 7 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 6.1 Normative references . . . . . . . . . . . . . . . . . . 8 6.2 Informative references . . . . . . . . . . . . . . . . . 8 7. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 9 Hong & Ryu Expires April 16, 2006 [Page 2] Internet-Draft A TCP for Heterogeneous Networks October, 2005 1. Introduction This document specifies TCP protocol for heterogeneous networks. TCP for heterogeneous networks is a congesion control mechanism designed for TCP operating in heterogeneous networks where wireless and wired-wireless hybrid networks exist. TCP was originally developed for the wired networks, where bit-error rate is trivial and packet losses are caused by network congestion. However, cellular/wireless networks and wired-wireless networks issue performance degradation challenges to TCP because TCP congestion control cannot distinguish between packet losses caused by random error of wireless link, signal fading and mobile handoff processing, and those caused by network congestion. At TCP sender, there are two state variables, congestion window size (cwnd) and slow start threshold (ssthresh) are maintained by congestion control to control the transmission rate. In slow start phase, at beginning of connection, cwnd is increased by 1 for every arrived ACK at the sender. Until cwnd reaches ssthresh, the sender TCP congestion control goes to congestion avoidance phase, where cwnd is increased by 1/cwnd for every arrived ACK at the sender. cwnd is additively increased to reach the network bandwidth and is abundantly decreased to one half of current value when the condition of network congestion occurs by indicating received Duplicate ACKs at the sender. TCP Reno then sets ssthresh to be the same as cwnd. If packet losses occur by random errors before ssthresh reaches the network capacity, ssthresh can be gotten a smaller value, thus blindly reducing the sending rate (i.e degrading TCP performance). TCP and many of its variants implement flow control and congestion control algorithms [J88] based on the sliding window and additive increase multiplicative decrease (AIMD)[CJ89] algorithms. TCP versions, such as Reno[RFC2001] and NewReno[RFC2582] have showed the heavy throughput degradation over links with high BER, fading, and backout, such as wireless links, due to TCP's congestion control, avoidance mechanism based on the assumption that all packet losses are due to congestions. 1.1 Terminology In this circumstance of document, we define the following terminologies. Heterogeneous network: In a heterogeneous network it is possible to use a combination of several networks, each of which is wired networks, wireless networks, or satellite networks. This means that intermediate links may be wireless links or satellite links. Last wireless hop, the term implies that accessing to Internet of the mobile node is supported by a base station through the radio interface. Hong & Ryu Expires April 16, 2006 [Page 3] Internet-Draft A TCP for Heterogeneous Networks October, 2005 2. Proposed approaches for the last wireless hop 2.1 Link layer approach This approach tries to increase the quality of the lossy wireless link. Thus, it hides the characteristics of the wireless link from the transport layer and tries to solve the problem at the link layer. The intuition behind link layer protocols is that the problem is local, and hence should be solved locally. These protocols involve forward error correction (FEC), retransmission in response to automatic repeat request (ARQ) messages, or a hybrid of the two. Another popular link-layer solution that uses knowledge of TCP is the Snoop protocol [BSK95], which works to hide losses over the wireless link from TCP. At a base station, a ‘snoop agent?keeps a cache of transmitted TCP segments that have not been acknowledged by the mobile user. When a link-local timeout or duplicate acknowledgements indicate a packet loss over the link, the snoop agent accesses its cache and resends the packet without notifying TCP. Thus TCP is shielded from duplicate ACKs, which avoids unnecessary fast retransmissions and initiation of congestion avoidance. 2.2 Transport layer approach One modification to TCP that would improve performance over wireless links is the use of Selective Acknowledgement (SACK)[RFC2018]. The use of cumulative ACKs in traditional TCP result in poor performance when multiple packets are lost during one transmission window. The cumulative ACKs do not provide information quickly enough to allow for fast recovery. Explicit loss notification (ELN) is a solution aimed at providing the sender with information to distinguish between losses due to congestion and those due to errors on the wireless link. 2.3 Split-connection approach As wireless networks usually connect to a wired infrastructure, a split-connection approach can be used whereby distinct connections are set up for the wired and wireless links. A TCP session could be used on each link, or a specialized transport protocol that is suited to a wireless environment could be used for the wireless link. Hong & Ryu Expires April 16, 2006 [Page 4] Internet-Draft A TCP for Heterogeneous Networks October, 2005 The basic idea behind MTCP[BS96] is to protect the long connection over the wired network from the impact of the erratic behavior of the short connection over the wireless link and also recover quickly from errors over the wireless link. If a mobile host need to communicate to a fixed host using I-TCP[BB94], a request is sent to the current base station to open a TCP connection with the fixed host on behalf of the mobile host. The mobile host communicates with its base station on a separate connection using a variation of TCP that is tuned for wireless links and is aware of mobility. 3. Explicit Congestion Notifications Dectecting packet loss with explicit notification from the network it is possible to determine when a loss is due to congestion. Several proposals along these lines include: - Explicit Loss Notification (ELN) [BPSK96] - Explicit Bad State Notification (EBSN) [BBKVP96] - Explicit Loss Notification to the Receiver (ELNR), and Explicit Delayed Dupack Activation Notification (EDDAN) (notifications to mobile receiver) [MV97] - Explicit Congestion Notification (ECN) [RFC3168] Of these proposals, Explicit Congestion Notification (ECN) seems closest to deployment on the Internet, and will provide some benefit for TCP connections on long thin networks (as well as for all other TCP connections). ECN uses the TOS byte in the IP header to carry congestion information (ECN-capable and Congestion-encountered). This byte is not encrypted in IPSEC, so ECN can be used on TCP connections that are encrypted using IPSEC. ECN is an explicit signaling mechanism designed to convey network congestion information from routers to end stations; however, since the signaling only uses one bit for such congestion information, the information conveyed is not quantitative. For TCP flow control, ECN works by configuring the intermediate router to mark packets with congestion experienced (CE) bit in the IP header when the router’s average queue occupancy exceeds a threshold, so that the TCP receiver can echo this information back to the sender via ACK by setting the explicit congestion echo (ECE) bit in the TCP header. Hong & Ryu Expires April 16, 2006 [Page 5] Internet-Draft A TCP for Heterogeneous Networks October, 2005 4. End-to-End bandwidth estimation Regular TCP detects the available bandwidth of the bottleneck link by continuously increasing the window size until the network is congested and then decrease the window size multiplicatively, e.g., the AIMD algorithm. However, the decrement of window size is rather heuristic and coarse, i.e., halving the current window size. This is because regular TCP scheme lacks the ability to quantitatively estimate the available bandwidth before the congestion happens. Regular TCP scheme’s congestion control mechanisms are reactive rather than proactive and preventive. We propose a stable accurate rapid bandwidth estimate (SARBE) algorithm incorporating ECN to improve TCP performance over heterogeneous networks. The SARBE algorithm estimates the bandwidth sample of the forward path of connection by monitoring the sending time intervals of ACKs sent by the receiver. By using the stability-based filter, the current bandwidth samples are eliminated from transient changes, while keeping reasonably persistent changes in the absence of noise. In SARBE approach, the estimate of the forward path is not be affected by ACK compression [ZSC91] that results in overestimate. When the kth ACK arrives at the sender, the sender simply uses information of the kth ACK to compute an available bandwidth sample as Bw[k] = L[k]/(ts[k] - ts[k-1]) (1) where L[k] is the amount of data acknowledged by the kth ACK, ts[k] is timestamp of the kth ACK, ts[k-1] is the timestamp of the previous ACK arrived at the sender. Obviously, sample Bwk represents the current network condition, which faces noises. So the bandwidth estimator has to eliminate transient noise but responds rapidly to persistent changes. The stability-based filter [KN00] is similar to the EWMA filter, except using a measure function of the samples?large variance to dynamically change the gain in the EWMA filter. After computing the bandwidth sample Bwk from (1), the stability-based filter is computed as U[k] = beta*U[k-1] + (1 - beta)*|Bw[k] - Bw[k-1]| (2) Umax = max(U[k-N],...U[k-1],U[k]) alpha = U[k]/Umax (3) eBw[k]= alpha*eBw[k-1] + (1-alpha)*Bw[k] (4) where U[k] is the network instability (beta=0.8); Umax is the largest network instability observed in the last N instabilities (N=8); and eBw[k] is the estimated smoothed bandwidth, eBw[k-1] is the previous estimate and the gain alpha is computed dynamically as (3) when the bandwidth samples vary largely. Hong & Ryu Expires April 16, 2006 [Page 6] Internet-Draft A TCP for Heterogeneous Networks October, 2005 5. TCP for Heterogeneous Networks TCP scheme for heterogeneous networks incorporates ECN and available bandwidth estimation algorithm SARBE. The optimal congestion window (ownd) size is computed based on bandwidth estimation of SARBE, following: ownd = eBw[k]*RTTmin/seg_size The RTTmin is the smallest RTT sample observed over the duration of the connection. Seg_size is the length of the TCP segment. 5.1 Algorithm after receiving ACK or n DupACKs if (ACK is received) if (ECE == 1 ) /* the network has been congested */ ssthresh = ownd; endif endif if ( n DupACKs are received) ssthresh = ownd; if (ECE == 0) /* the network has not been congested */ /* the loss is occured by random error of wireless links */ /* in the congestion avoidance phase */ if (cwnd > ssthresh ) cwnd = ssthresh; endif endif endif When n DUPACKs are received without the sign of the congested network, TCP-aware of the packet drop is caused by a wireless link, and therefore it does not adjust the window size. Hong & Ryu Expires April 16, 2006 [Page 7] Internet-Draft A TCP for Heterogeneous Networks October, 2005 5.2 Algorithm after timeout expiration if ( timeout expires) ssthresh = ownd; if (ECE == 1) /* the network has been congested */ if (ssthresh < 2) ssthresh = 2; endif cwnd = 1; /* go to Slow Start phase */ else /* the timeout is occured by random error of wireless links */ /* in the congestion avoidance phase */ if (cwnd > ssthresh ) cwnd = ssthresh; endif endif endif After the timer expires, if the network has been congested by notifying from an intermediate router, cwnd and ssthresh are set equal to 1 and ownd, respectively. Otherwise, the timeout is occured by random error of wireless links, forcing TCP congestion control into beginning of the congestion avoidance phase during it has been being in the congestion avoidance phase. Hong & Ryu Expires April 16, 2006 [Page 8] Internet-Draft A TCP for Heterogeneous Networks October, 2005 6. References 6.1 Normative references [KN00] M. Kim and B. D. Noble, "SANE: stable agile network estimation," Technical Report CSE-TR-432-00, University of Michigan, Department of Electrical Engineering and Computer Science, Ann Arbor, MI, August 2000. [MV97] Mehta, M., Vaidya, N., "Delayed Duplicate- Acknowledgements: A Proposal to Improve Performance of TCP on Wireless Links," Texas A&M University, December 24, 1997. [BBKVP96] Bakshi, B., P., Krishna, N., Vaidya, N., Pradhan, D.K., "Improving Performance of TCP over Wireless Networks," Technical Report 96-014, Texas A&M University, 1996. [BPSK96] Balakrishnan, H., Padmanabhan, V., Seshan, S., Katz,R., "A Comparison of Mechanisms for Improving TCP Performance over Wireless Links," in ACM SIGCOMM, Stanford, California, August 1996. [BS96] Brown, K. Singh, S., "A Network Architecture for Mobile Computing," Proc. IEEE INFOCOM'96, pp. 1388- 1396, March 1996. 6.2 Informative references [J88] V. Jacobson, "Congestion avoidance and control", in Proc. ACM SIGCOMM, Aug. 1988, pp. 314- 329. [CJ89] D. Chiu and R. Jain, "Analysis of the increase/decrease algorithms for congestion avoidance in computer networks", J. Comput. Networks, vol. 17, no. 1, pp. 1-14, June 1989. [RFC3168] K. Ramakrishnan, S. Floyd, and D. Black, "The Addition of Explicit Congestion Notification (ECN) to IP", RFC 3168, September 2001. [RFC2582] S. Floyd, T. Henderson, "The NewReno Modification to TCP's Fast Recovery Algorithm", RFC 2582, April 1999. [RFC2001] W. Stevens, "TCP slow start, congestion avoidance, fast retransmit and fast recovery algorithms", RFC 2001, 1997. Hong & Ryu Expires April 16, 2006 [Page 9] Internet-Draft A TCP for Heterogeneous Networks October, 2005 [RFC2018] M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow, "TCP Selective Acknowledgment Options", RFC 2018, October 1996. [BSK95] H.Balakrishnan, S.Seshan, and R.H.Katz, "Improving reliable transport and handoff performance in cellular wireless networks," ACM Wireless Networks, vol.1, Dec 1995. [BB94] Ajay Bakre, and B.R. Badrinath, "I-TCP: Indirect TCP for Mobile Hosts," October, 1994. [ZSC91] L. Zhang, S. Shenker, and D. Clark, "Observations on the Dynamics of a Congestion Control Algorithm: The Effects of Two-Way Traffic," Proc. SIGCOMM Symp. Comm. Architectures and Protocols, pp. 133-147, Sept. 1991. 7. Authors' Addresses Questions about this memo can be directed to: Choong Seon Hong Department of Computer Engineering Kyung Hee University 1 Seocheon, Giheung, Yongin, Gyeongi-Do, 449-701, Korea E-mail : cshong@khu.ac.kr Hyung-Keun Ryu KT Advanced Technology Lab Woomyun, Seocho, Seoul, Korea Email : hkryu@kt.co.kr Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Hong & Ryu Expires April 16, 2006 [Page 10]