Over the last five years, a rapid growth in the development and use of wireless networks has taken place. Future networking environments are expected to be hybrid; That is to say, to incorporate both wired and wireless subnetworks. Some of the most important issues which are being raised, regarding the integration of mobility in current network infrastructures, are closely related with the fact that a great number of existing, widely used, protocols have been designed to operate over wired links.

TCP operates on the assumption that all packet losses occur due to congestion only. However, in wireless links packet losses might occur due to high bit error rates and handoffs. In all these cases standard TCP invokes congestion control mechanisms, which degrade throughput. This papers aims to review some of the proposed solutions to this problem, especcially the local recovery ([1], [2]) and the explicit bad state notification ([1]) approaches, and also provide an improvement to the second approach, which makes TCP operate in a more stable manner.

The author used the Network Simulator (ns), from Lawrence Berkeley Labs in order to test the various ways of improving the performance of TCP which are described in this paper.

1. Introduction

A quite large number of applications (email, ftp, gopher e.t.c) are based on reliable transport. The Transmission Control Protocol (TCP) has been developed to provide connection oriented data transfer between two users. TCP succeeds in delivering data reliably in sequenced order, by using sliding window retransmission mechanisms in a quite sophisticated way that combines ordered delivery with flow and congestion control.

The operation of TCP as presented in [5] can be described by the following algorithms :

• Slow Start : Whenever starting traffic, congestion window has the size of one segment and is being increased by one segment, for every acknowledgement that arrives. In errorless environments slow start results in exponential increase of the congestion window.
• Multiplicative Decrease. Upon loss of a segment congestion window is being reduced to the half of its previous size.Transmission timer is being increased exponentially.
• Congestion Avoidance. If congestion window reaches a level called slow start threshold, then it is being increased by one segment, when all packets in the allowed window are acknowledged by the receiver.
• Allowed Window is the minimum value between the congestion window and the space available at the receiver's buffer.

In order to accomodate the varying delays in round trip time (RTT), which reflect the way routes dynamically change in an Internet environment, TCP uses an adaptive algorithm to adjust timeout parameters. The basic idea behind this algorithm is that the proportionality factor which relates round trip time with timeout, should not be a fixed number, but it should be evaluated as a function of the round trip time variance.

Now, let us examine what happens when TCP is applied in wireless networks. Packet losses in wireless links occur, in most cases, due to extremely high bit error rates and make TCP enter the multiplicative decrease phase, or in the worst case the slow start phase; Of course such severe behaviour is unnecessary because the network is in most cases is uncongested. A simple quantitative analysis on the way damages in transit degrade throughput, shows that a packet loss probability p degrades throughput by a factor of 1/(1+2pw), where w is the size of allowed window. For example 1% damage loss degrades throughput by 14%. Therefore, the operation of standard TCP in wireless environments is not efficient.

The solutions proposed up to know are focused on adapting the network to TCP rathen than TCP to the network. The reason why this happens is because TCP is widely used, and the whole operation of Internet is based on the reliable transfer services it provides. The price that has to be paid for improving the performance of standard TCP depends on the nature of each individual approach: Split-connection approach, [3], results in violation of TCP end-to-end semantics; Snoop module approach, [2], violates Layer transparency; Finaly timer refreshing feedback schemes (EBSN), [1], are rather unpredictable.

The solution we propose is a modification to the Explicit Bad State Notification (EBSN) algorithm, presented in [1]. We examined the effects of round trip time variations due to multipath fading and propose an adaptive algorithm for notifying TCP senders of future variations in RTT, in order for undesired timeouts to be avoided. Detailed presentation of the algorithm is presented in section 4 of this paper.

2. Local recovery approach

Local recovery at the base station aims to hide the vagaries of the wireless link from the remote sender. Packets are being cached at the base station in order to be retransmitted, in case they are lost due to deep fades. This mechanism can be implemented in various ways. Prof R. Katz, in U.C. Berkeley proposed in [2] a method called Snoop module which implements local recovery by extracting information from Transport Protocol Data Units (T-PDUs) and thus violating layer transparency. Another way to reach the same goal is to carry out link layer retransmissions. Any of the existing ARQ schemes can be used for that purpose.

Simulation tests of local recovery indicate that the efficiency of this approach depends on whether fades occur for a relatively long or short period of time. The primary disadvantage of local recovery is its inability to deal with timeouts at the remote sender : The lack of synchronization betweeen two independent retransmission schemes that run concurrently (TCP - local ARQ) results in redundant retransmissions and performance degradation.( Snoop however captures and discards redundant retransmitted packets).

The significance of local recovery is that it minimizes packet loss probability. We can consider that the link behaves as though packets were not lost, but simply arrived late at the mobile receiver. So, the ARQ-enhanced wireless link can be modeled by a relatively reliable channel having its bandwidth fluctuating as a function of time. These virtual bandwidth fluctuations comprise an additional source of round trip time variations.

Therefore, local recovery moves the problem of improving the performance of TCP, from handling packet losses to providing an algorithm for preventing timeouts that occur due to rapid changes on round trip time.

3. Explicit bad state notification (EBSN) approach

EBSN is a solution to the problem of timeouts proposed by researchers of Texas A&M University ([1]). It faces the problem in a rather simple way: Once a packet loss is being encountered over a wireless link the base station sends an ICMP message back to the remote sender in order to cancel the previous timeout and set a new one based on the existing estimate of round trip time and variance. This ICMP message is called Explicit Bad State Notification (EBSN). For all subsequent packet losses new EBSN messages are sent.

This algorithm has been tested by the authors of [1] and us, on a network topology consisting of a remote sender, connected through a wired link to a base station, connected through an air interface to a mobile receiver. Simulation results showed that EBSN provides more than 50% improvement over basic TCP. However, we extended our simulations over more complicated topologies including TCP connections between mobile senders and mobile receivers and found out that EBSN fails to improve the performace of the network in the cases where there is at least one air interface in the path between the TCP sender and the base station serving the mobile receiver. Furthermore, we observed that when the average fade duration is high, performance degrades further, while EBSN works well when fades occur for a relatively short period of time.

In order to explain our simultaion results we present the way TCP estimates round trip times and computes timeout values :

Let us consider that a and v are the estimated values for the average RTT and its variance. If a new RTT measurement m is given then the values for a and v are being calculated from the following formulas :

Finaly, the new timeout value is being evaluated in the following way :

The equations presented above indicate that timeout values are being estimated in an adaptive way, based on the previous measurements of round trip time. In network environments supporting local recovery, fades correspond to rapid growths in round trip time. However, during the initial operation of a network a TCP sender is not aware of such changes; What is most likely to happen is that small timeout values are used for packets that experience much greater latencies during their transmission. This is the reason why EBSN messages, transmitted through air interfaces arrive in most cases after timers are expired and therefore, provide no actual improvement.

Another disadvantage of EBSN is that it may unnecessarily delay retransmissions, in cases when packets are dropped over the wireless links. All these facts demonstrate an inherent weekness of this algorithm : Because of the fact that EBSN carries no information, it is a rather unpredictable and uncontrollable mechanism. Other explicit feedback mechanisms such as the one we describe in the following section introduce some level of control in updating the timers at remote senders.

4. Round Trip Time notification (RTTN) approach

Varying delays in packet delivery and acknowledgement reception that occur in the Internet, reflect the fluctuating traffic intensity on intermediate hops, the dynamic updating of routing paths and the constantly changing population of competing conversations ([8]). This is the reason why future behaviour of round trip time is generally unpredictable.

However, this is not entirely true regarding the RTT variations caused by bursts of errors in wireless links. Fade duration can be measured and its average values can be stored and dynamically updated at the base station. This means that the base station is a system capable of notifying TCP senders what kind of behaviour they should expect from a particular air interface.

So, one more efficient approach to the problem of preventing timeouts at TCP senders, could be the explicit notification of future increases in round trip time. A sketch of an algorithm based on this approach is the following :

• When a base station receives for the first time TCP data from a remote sender, it sends back an ICMP message notifying the sender of its average fade duration.
• When a sender receives such a message it updates RTT, based on its previous estimation and adding into it a value that depends on the average fade duration. The exact function derives from conventional M/G/1 queue analysis.
• No other explicit timer refreshing is needed.

This algorithm predicates layer transparency violation -similar to snooping. Fade duration is also constantly changing and variations in RTT depend on a great number of parameters such as the receiver's movement, the surrounding environment's state a.s.o. However, we feel that future research on the Round Trip Time Notification (RTTN) algorithm may indeed provide some improvement regarding the issues discussed above, exactly because this solution includes the following advantages :

• It updates timer at the sender independently of packet losses.
• It controls the timer's updated value by providing the estimated values of fade durations.

5. Simulation

In order to test the various approaches described above, we used the Network Simulator (ns) from Lawrence Berkeley Laboratory. In this section we provide infomation about the way our tests were carried out, and in the next section we present our results.

A. The error model

The error model we used, was the same as the one proposed in [1]. This model is characterized by a two state markov chain shown in the following figure :

In each state, bit errors are poisson distributed with mean bit error rates :

The good state represents the error-free behaviour of the link, while the bad state represents a fade. We consider that each state's duration is exponentially distributed; This is equivallent to saying that transition rates between the good and bad state are poisson distributed. We chose the values of 10 sec and 4 sec for the average duration of the good and bad state respectively.

Simulation tests regarding the various approaches to improving TCP over Wireless Links need to take place on error conditions quite similar to each other, in order for the examined schemes to be comparable. This is the reason why the authors of [1], used constant values for each state's bit error rate and duration.We, instead used a more realistic model based on uniformal distributions in order to approximate the two state probabilistic model presented above.

B. Topologies tested

We tested wireless TCP on the following networks :

• Fixed host to mobile

• Mobile to mobile

We chose the values of 56 Kbps and 19.2 Kbps for the wired and wireless links' bandwidth respectively. In order to examine the operation of TCP we established ftp sources on the nodes marked as SRC and ftp sinks on the nodes marked as SNK. The maximum packet size was 128 bytes.

The first topology was used to test unmodified TCP, local recovery and EBSN. In fact we reproduced the results presented in [1], using this time a probabilistic error model and a Go Back N retransmission scheme for the wireless link. The second topology was used for further research on explicit feedback schemes (EBSN, RTTN)

C. Protocols used

We used a Go Back N link layer protocol in order to implement the local recovery mechanism. This protocol operates in a way quite similar to HDLC : A maximum number of N packets can be transmitted without any acknowledgement received. If no acknowledgement is received within a timeout period, then the whole group of N packets is being transmitted again. N is defined by the user.

Regarding the uplink, we used a selective retransmission scheme. The reason why this assymmetry exists is because uplink is usually characterized by less bandwidth than downlink. Selective retransmission causes the mobile host to quickly retransmit missing packets, and this behaviour counterbalances the difference in performance between uplink and downlink transmissions.

6. Results

The results from our simulation tests are presented by xgraph. In the following figures horizontal axis represents time, while vertical axis represents the sequence number mod 90, of the packets which are being delivered or dropped over the receiver's air interface

The figure above illustrates the bursty error characteristics of wireless links. Deep fades last for an average period of 4 sec and during these periods almost no packet is being succesfully delivered.

A Go back 3 Link Layer protocol is used for implementing Local Recovery at the base station. However this scheme suffers from timeouts and retransmissions from the remote sender cannot be avoided.

Explicit Bad State Notification offers over 50% improvement on the performance of TCP

Performance of TCP is unacceptable !

Local Recovery schemes imporve the performance of TCP. However EBSN messages fail to refresh the sender's timer and redundant retransmissions cannot be avoided.

7. References

[1] Bikram S. Bakshi, P. Krishna, N.H. Vaidya D. K Pradhan, "Improving Performance of TCP over Wireless Links"

[2] Hari Balakrishnan, Srinivasan Seshan, Randy Katz " ImprovingReliable Transport and Handoff performance in Cellular Wireless Networks"

[3] Ajay Bakre, B.R.Badrinath "I-TCP : Indirect TCP for Mobile Hosts"

[4] Ramon Caceres, Liviu Iftode, " Improving the Performance of Reliable Transport Protocols in Mobile Computing Environments"

[5] Van Jacobson, Michael J. Karels "Congestion Avoidance and Control"

[6] Sally Floyd "Issues of TCP with SACK "

[7] Sally Floyd "Simulator Tests"

[8] Douglas Comer " Internetworking with TCP/IP", Volume I

8. Source Code

The following modules have been added to the ns Tcl/Tk interface code regarding the description of the various topologies tested and the definition of simulation parameters

• wireless_tcp.tcl - operation on standard TCP on fixed to mobile topology
• wireless_tcp_ret.tcl - operation of TCP with local recovery on fixed to mobile topology
• wireless_tcp_ebsn.tcl - operation of TCP with EBSN on fixed to mobile topology
• s_mob-to-mob.tcl - operation of standard TCP on mobile to mobile topology
• mob-to-mob.tcl - operation of TCP with EBSN on mobile to mobile topology

The following extentions to the ns C++ simulation engine have taken place :

A. Implementation of markovian error model :

• loss-policy.cc - contains the new class WirelessLink which inherits from the class LossyLink

B. Implementation of Go Back N protocol :

• lossy.cc - contains the new class RetLossyLink which inherits form the class Lossy Link
• loss-policy.cc - contains the new class RetWirelessLink which inherits from the class RetLossyLink
• link.h - contains definitions of new classes

C. Implementation of Selective Retransmission scheme :

• lossy.cc - contains the new class LossyUpLink which inherits form the class Lossy Link
• loss-policy.cc - contains the new class WirelessUpLink which inherits from the class LossyUpLink
• link.h - contains definitions of new classes

D. Implementation of EBSN :

• lossy.cc - contains the new class EbsnLossyLink which inherits form the class RetLossy Link
• loss-policy.cc - contains the new class EbsnWirelessLink which inherits from the class EbsnLossyLink
• link.cc - contains modifications regarding ICMP message transmission
• tcp.cc - contains modifications regarding timer refreshment
• link.h - contains definitions of new classes

The ns v1.1 package containing the modified files described above can be obtained here

9. Acknowledgements

The author would like to express his gratitude to his advisor Prof. Andrew Campbel for his valuable guidance and support throughout the Fall 96 semester at Columbia.