Transcript ppt - CSE Buffalo

Wireless TCP Introduction
The problems of Standard TCP over
wireless link and basic solution
Several implementations of wireless TCP
I-TCP (Indirect TCP)
Snoop Protocol
Delayed duplicated ACK
Multiple Acknowledgements
Freeze TCP
Comments and discussion
1
The problems of standard
TCP in wireless networks
Standard TCP assume that the packet
losses are due to the congestion.(99%)
This not valid considering the
characteristic of wireless link
sporadic high bit-error rate, high latencies
 temporary disconnection due to handoff
Misinterpretation packet loss for
congestion
2
Basic ideas to overcome the
problem in wireless network
Hide any non-congestion-related losses
from TCP
Split TCP connection
Local retransmissions
IP Layer
Link layer
Let TCP aware the non-congestion-related
losses and not apply congestion control
3
Basics topology
Figure 1 Topology
4
I-TCP: Indirect TCP
Breaks the TCP connection between FH
and MH into two connections at MSR
Connection between FH and MSR is
regular TCP
Connection between MSR and MH is any
transport layer protocol tuned for wireless
links.
5
I-TCP indirect TCP (Cont.)
BS cache packets from FH and send back
ACK for MH.
if MH switches to another cell the center
point of the connection moves to the new
MSR, no need of reconnection.
FH is completely unaware of the
indirection and is not affected even when
the MH switches cells.
6
Figure 2
I-TCP setup and handoff
7
I-TCP Result in LAN
TABLE 1 I-TCP Throughput Performance over
Local Area
8
I-TCP Result in WAN
Table 2 I-TCP Throughput Performance over Wide
Area
9
Snoop Protocol
Basic idea
Modify the IP layer in the BS, and let BS
cache the TCP packets sent from FH before
route it to the MH.
If packet lost on wireless link, IP layer on the
BS will retransmit the packet .
BS suppress DUPACKs sent from MH to FH.
BS use shorter local timer for local timeout.
10
Three kinds of data packets
from FH
A new packet in the normal TCP
sequence. (common case)
An out-of-sequence packet that has been
cached earlier. (sender retransmission)
An out-of-sequence packet that has not
been cached earlier. (congestion loss)
11
Flowchart for snoop_data
Packet arrives
1. Forward Packet
2. Reset local rexmit
counter
No
New Packets?
No
Acknowledged
Sender
rexmition
Yes
No
In sequence?
1. Mark as cong. loss
2. Forward packet
Yes
Send back lasted
ACK
Congestion loss
Yes
1. Cache packet
2. Forward to mobile
host
Figure 3.
Common case
Flowchart for snoop_data()
12
Process three kinds of ACKs
A new ACK from MH
A spurious ACK, sequence number less
than the lasted acknowledged one
A duplicate ACK (DUPACK)
13
Flowchart for snoop_ack
Ack arrives
Yes
New ACK?
No
Discard
No
1. Free buffers
2. Update RTT
3. Propagate ACK
to sender
Common case
Dup ACK?
Yes
Spurious Ack
No
Discard
Later dup Acks,
for lost packet
Yes
First one?
Retransmit lost
packets with high
priority
Next packet lost
Figure 4. Flowchart for snoop_ack
14
Data from MH to FH
Can not differentiate between BER loss or
Congestion loss.
Using SACK (selective acknowledge)
BS keep track packet losses in a transmit
window.
BS send NACK to MH with SACK option
indicate the boundary of the lost packets.
15
Routing in snoop protocol
Similar to Mobile IP.
Using multicast and intelligent buffering in
nearby base stations.
One prime BS forward packets
Several nearby BS cache the last several
packets
16
Figure:
Intelligent cache
17
Handoff process in snoop
protocol
Initiated by mobile host
MH send control messages to the various
BS, request them either begin or end
forwarding and buffering of packets
The activated forwarding BS synchronizing
its buffer using information in the control
message
18
Handoff process Cont.
since snoop module does not change any
of the end-to-end semantics of TCP, it is
resistant the random packet losses when
handoff.
19
Handoff process
BS_OLD
MH
BS_NEW
packet1
beacon
Stronger
beacon
packet2
Buffer request
Forward request
packet3
Handoff
latency
packet4
packet5
20
Topology for experiment
Ethernet
Transmitter
Home Agent
BS1
BS2
AT&T Wavelan
2Mbits/s
MH
21
Throughput: Snoop vs. Regular TCP
22
Sequence number: Snoop vs. Regular TCP
23
Delayed Duplicate ACK
Motivations
TCP may be encrypted
ACK may go different paths from that of
data.
Basic ideas
The idea is to delay the third and subsequent
duplicate acknowledgments for some time, let
BS link layer do local retransmissions.
24
Delayed Duplicate ACK (cont.)
TCP not changed in BS , only changed in
MH
BS data link layer re-transmission
triggered by link level acknowledgements.
Performance depend on the ratio of BER
loss and congestion loss.
25
Reduce interference
FH timer is very coarse (multiple of 200 or
500ms), link layer timer in BS is much
smaller. Interference is small.
Reduce interference between fast
retransmission and local retransmission
by delay the third dupack for a time
interval T.
26
Delay interval T
If T = 0, regular TCP.
All congestion loss
If T = infinity, regular TCP without fast
retransmission.
All BER loss
Appropriate T should be a function of RTT
of the wireless link, and relate to BER and
congestion loss rate.
27
Simulation Result
Use ns-2 simulator
Wired network with 10Mbps bandwidth
and delay of 20ms.
Wireless network with 2Mbps bandwidth
and delay of 1ms - 40ms
packet data size is 1000 byte.
T ranges from 0 to 0.2 second
28
Multiple Acknowledgements
Protocol
Distinguish the losses on the wired
portion from the losses on the wireless
link.
ACKp: partial acknowledgment that inform
the sender the packet is received by BS.
ACKc: complete acknowledgment has the
same semantics as the normal TCP.
RTT: round trip time between the sender
and the receiver. (end to end)
31
Multiple Acknowledgements
protocol (Cont.)
RTTB: round trip time between the base
station and the mobile host.
RTO: timer value for end-to-end
acknowledgement.
RTOB: maximum time which can elapse
between the reception of a packet at the
base station and its acknowledgement by
the mobile host
32
Figure : Multiple Acknowledgement
33
TCP on sender and receiver
Sender
When receive a ACKp, reset timer RTO to
avoid time out while BS is retranslating.
Update RTT when receive ACKp, suitable for
transit bandwidth drop
Update RTT when receive ACKc, reflect the
real round trip time
No change is made to Receiver TCP
34
Snoop protocol on BS
Snoop data
On receiving new packet, cache it and start
RTOB
On receiving out of order and cached packet,
S > Sa, and packet still in cache, send ACKp to
FH
S > Sa, and packet not in cache, as new packet
S < Sa, generate a fake ACKc to FH
On receiving out of order and un-cached
packet, cache it and forward
35
Snoop protocol on BS (Cont.)
Retransmissions
When RTOB expires, the packet must be
retransmitted and ACKp is sent back to the to
the sender if all packets before it have been
received by the base station. (important
difference from Berkley Snoop Protocol)
Snoop ACK is the exactly the same with
the Berkeley Snoop Protocol
36
Implementation of ACKp and
ACKc
For ACKc, it is the normal TCP ACK
For ACKp, An option is implemented with
the a type byte, length byte and a 4
bytes sequence number, total of 6 bytes.
37
Freeze-TCP
Motivations
Most wireless TCP implementations do not
handle frequent handoff or long temporary
disconnection properly.
Freeze-TCP can handle it efficiently.
Freeze-TCP can be integrated with other
existing solutions.
Only change TCP on the mobile client side
38
Handle frequent handoff
ZWP - zero window probes
When advertise window become zero,
sender send ZWP.
If ZWP is lost, the sender does not shrink
congestion window, but exponentially
back off.
Sender resume transmission after receive
a non-zero advertised window
39
Handle frequent handoff
(cont.)
Mobile client sense the strength of signal
to judge if there will be a handoff or
disconnection.
Send ZWA (Zero Window Advertisement)
to sender before handoff.
Warning period choose as RTT.
40
Avoid long freeze time
The interval between successive ZWPs
grow exponentially.
Long freeze time if reconnect immediately
after a ZWP lost.
Use TR-ACK to avoid long unnecessary
freeze time, send 3 copies of ACKs for the
last data segment it received prior to the
disconnection.
41
Illustration of throughput
Freeze vs Regular TCP
In LAN
Freeze vs Regular TCP In
WAN
Comments and discussion
I-TCP
Well performed in most of the wireless links,
no change in FH
Change semantics of end-to-end ACK,
Berkeley Snoop
Well performed in wireless LAN, keep
semantics of end-to-end ACK
45
Comments and discussion
Cont.
Not perform well in wireless links with long
latency, fail when TCP is encrypted.
Multiple Acknowledgement
Can be used in high bit-error rate
environment, keep ACK semantics
Fail when TCP is encrypted
46
Comments and discussion
Cont.
Delayed Acknowledgement
Can be used when TCP is encrypted
Use link layer retransmission, must have
reliable link layer support
47
Comparison between different
protocols
SNOOP I-TCP MTCP Delayed Freeze
Dupacks TCP
Need intermediate
Yes
Yes
Yes
No
No
node?
Handle encrypted
No
No
No
Yes
Yes
traffic
End-to-end TCP
Yes
No
No
Yes
Yes
semantics
Handle long
No
Costly Costly
No
Yes
disconnection
Frequent
No
Costly Costly
No
Yes
disconnection
Handle high BER
Yes
Yes
Yes
No
No
TCP propagation delay
introduction
Long RTTs are now becoming prevalent in the
Internet with the introduction of paths crossing
satellite links.
At long RTT, TCP congestion mechanism may
result in an inefficient utilization of network
resources.
Since TCP is based on the ACK clock, the
congestion window increase rate is lower
because of long RTT.
49
Effect of propagation delay
The performance that suffer the most is
during congestion avoidance at a low
slow start threshold.
Slow start requires more time to achieve
in long RTT link. Therefore TCP
performance degrades.
It is more critical for small file transfer
and WWW browsing.
50
Solutions overview for
propagation delay
Many propositions have been suggested to
increase window growing rate at the
beginning of the connection.
These propose try to reduce RTTs required to
reach network capacity. But the absence of
any kind of bandwidth estimation may result
in bursts which can cause losses of packets.
This problem is exacerbated in the presence
of ack loss.
51
Solutions for propagation
delay
TCP level solutions
Application level solutions
Network level solutions
52
TCP level solutions for
propagation delay
The first proposition:
Use a window larger than one segment at the
beginning of slow start. (proposed maximum 4
segments)
After Timeout, the network is supposed to be
severely congested so that a transmission at a small
initial window is required.
The second proposition:Byte Counting
It increases the window by the number of bytes
covered by an ack rather than number of acks.
This decouples the window increase algorithm from
ack clock which may result in burstiness when acks
53
are lost.
Application level solutions for
propagation delay
The solution is to establish many
simultaneous TCP connections for the
transfer of a single file.
This increases the growth rate of resultant
window during slow start, and makes the
recovery algorithm more efficient due to
distribution of losses on many connections.
However, this solution increases the
aggressiveness of the transfer.
54
Network level solutions for
propagation delay
Source
Long Delay Link
TCP
Connection 1
A
Optimized
Transport
Protocol
No Slow Start
Generation of ACKs
Destination
B
TCP
Connection 2
Suppression of
Destination ACKs
55
Network level solutions for
propagation delay (contd)
TCP spoofing
In order to decrease the RTT of the connection, the
acks are generated by the router at the input of this
link.
Because packets have already acknowledged (by
router A), any loss between the input and destination
must be retransmitted on behalf the source.
Also, acknowledgements from the receiver must be
silently discarded so as not to confuse the source.
56
Network level solutions for
propagation delay (contd.)
The main gain in performance comes
from not using slow start.
Drawbacks
it breaks the end-to-end semantics of TCP.
It doesn’t work when encryption is
accomplished at the IP layer and it introduce
a heavy overload on intermediate routers.
57
TCP bandwidth asymmetry
introduction
The asymmetric network is motivated by
technological and economic considerations as
well as by the popularity of applications such
as Web access which involve a substantially
larger data flow towards the client (the
forward direction) and from it (the
reverse direction).
Example: Direct Broadcast Satellite networks,
Cable Modem, Asymmetric Digital Subscriber
Loop (ADSL)
58
Asymmetry network topology
59
Effect of bandwidth
asymmetry
TCP assumes that forward channel and
reverse channel have the same bandwidth.
That means the source can rely on the ACK
clock to guess what is happening on the
forward channel.
If the reverse channel has lower bandwidth,
the TCP congestion algorithm may
miscalculate RTT and has lower throughput.
If reverse channel is also used for data, the
problem of asymmetry will be exacerbated.
60
Solution for asymmetry effect
in one-way transfer
Definition: data transfer in forward link
and acks transfer in reverse link.
Receiver:
Ack Congestion Control (ACC)
Ack Filtering (AF)
Sender:
TCP Sender Adaptation (SA)
Ack Reconstruction (AR)
61
Ack Congestion Control (ACC)
- decrease frequency of acks
Use Random Early Detection (RED) algorithm at the
gateway of the reverse link to aid congestion
control.
The gateway detects incipient congestion by tracking
the average queue size over a time in the recent
past.
If the average exceed a threshold, the gateway set
an Explicit Congestion Notification (ECN) bit using the
RED algorithm. This notification is reflected to data
packets (forward link) and acks (reverse link).
62
Ack Congestion Control (ACC)
(contd.)
Once sender receives the packet, the sender reduces
its sending rate.
The TCP receiver maintains a dynamically varying
delayed-ack factor d, and send one ack for every d
data packets.
When it receives a packet with ECN bit set, it increases d
multiplicatively.
When it does not receive an ECN, it linearly decrease the
factor d.
Conclusion: the receiver mimics the standard congestion
control behavior of TCP sender.
63
Ack Filtering (AF) - decrease
the number of acks
Based on the fact that TCP acks are cumulative.
When an ack from the receiver is about to be
enqueued, the router traverses its queue to check if
any previous acks belonging to the same connection
are already in the queue.
It so, then it removes some fraction of acks and frees
up bandwidth.
The acks dropping policy can be deterministic or
random.
64
The drawback of receiver
solution
Fact: ACC and AF acknowledge several
data packets in one ack.
It can cause problem such as sender
burstiness, a slowdown in window growth,
and a decrease in the effectiveness of the
fast retransmission algorithm.
65
TCP Sender Adaptation (SA)
sender burstiness solution: put a upper
bound on the number of packets the sender
can transmit, even if the window allows the
transmission of more data.
The sender can avoid a slowdown in window
growth by simply taking into account the
amount of data acknowledged by each ack,
rather than the number of acks.
66
TCP Sender Adaptation (SA)
(contd.)
Fast retransmission degrading problem solution:
solve by not requiring the sender to count the
number of duplicate acks.
With ACC, when receiver observers a threshold
number of out-of-order packets, it marks all of the
subsequent duplicate acks with a bit to request a
fast retransmission.
With AF, the reverse channel router request fast
retransmission when it has filtered out a threshold
number of duplicate acks. The receipt of even one
such marked packet causes the sender to do a fast
retransmission.
67
Ack Reconstruction (AR)
A technique to reconstruct the ack stream
after it has traversed the reverse direction
bottleneck link.
This enables us to use schemes such as ACC
and AF without having to modify sources and
perform SA, which is asymmetric network
providers may able to locally deploy.
The main idea is for the reconstructor to fill
in the gaps in the ack sequence to “smooth
out” the ack stream seen by the sender.
68
Ack Reconstruction (AR)
(contd.)
AR interspersing acks to provide the sender with a
larger number of acks at a consistent rate.
When an ack arrives at B, all the missing acks
between the sequence number it carries and that of
the ack received at B are generated.
Example: Suppose 2 acks a1 and a2 arrive at the
reconstructor after traversing the constrained reverse
link. Let a2-a1 = a >1
When a2 reaches the sender, at least a packets are sent by
sender. Congestion window increases by at most 1.
AR remedies this situation by interspersing acks to provide
to sender with large number of acks.
It reduces degree of burstiness and causes the congestion
window to increase faster.
69
Asymmetry effect in two-way
transfer
Definition: both data and acks transfer in
forward and reverse link.
In this case, a single FIFO queue for both data
and acks could cause problems.
For example, an 1KB sized data packet takes
280ms to go through 28.8kbps dialup line. If
more such data packets get queued ahead of
ack packets, it would block out the ack packets
for a long time.
70
Solution for asymmetry effect
in two-way transfer
Acks-first scheduling. This algorithm always
gives higher priority to acks over data packets.
By combining with header compression
techniques, the transmission time of acks
becomes small enough that it affects
subsequent data packets very little.
At the same time, it minimizes the idle time for
the forward link by minimizing the amount of
time acks remain queued behind data packets.
71
Asymmetry effect summary
ACC and AF are schemes to reduce the
frequency of acks on the reverse channel.
SA and AR are schemes to overcome the
adverse effects of reduced ack feedback.
In experiments, we use ACC conjunction with
SA, and AF in conjunction with SA or AR.
Acks-first scheduling scheme is designed to
prevent the forward transfer from being starved
by data packets of the reverse transfer.
72
Figure: one-way transfer
comparison
73
Figure: one-way throughput
74
Figure: congestion window
75
Figure: two-way transfer
comparison
76
References
Chadi Barakat, Eitan Altman,Walid Dabbous, “On TCP
Performance in an Heterogeneous Network: A Survey”,
INRIA-France, Research Report N=3737, July 1999
H. Balakrishnan, V. Padmanabhan, and R. Katz, “The Effects
of Asymmetry on TCP Performance”, in ACM MobiCom, Sep
1997.
T. V. Lakshman, U. Madhow, and B. Suter, “Window-based
error recovery and flow control with a slow acknowledgment
channel: a study of TCP/IP performance”, INFO-COM’97.
D. Lin and R. Morris, “Dynamics of Random Early Detection”,
in ACM SIGCOMM, Cannes, France, Sep 1997.
L. Zhang, S. Shenker, and D.D. Clark, “Observations on the
Dynamics of a Congestion Control Algorithm: The Effects of
Two-Way Traffic”, in ACM SIGCOMM, Sep 1991.
77
Reference (contd)
A comparison of Mechanisms for Improving TCP
Performance over Wireless Links, IEEE/ACM TRANSACTIONS
ON NETWORKING VOL.5 NO.6 1997 IEEE
TCP Extensions for Wireless Networks, http://www.cis.ohiostate.edu/~deshpand
Badrinath B R, Bakre A "I-TCP :Indirect TCP for mobile
hosts”, Proc. 15th Int'l Conference on Distributed Computing,
May 1995, 18 pages. ftp://paul.rutgers.edu/pub/badri/itcptr314.ps.Z
Balakrishna H, Katz, Seshan S "Improving reliable Transport
and handoff performance in cellular wireless networks”,
Wireless Networks,1(4), Dec 95, 19 pages,
http://www.cs.berkeley.edu/~ss/papers/winet/html/winet.ht
ml
78
Reference (contd)
Vaidya N, Mehta M "Delayed duplicate acknowledgements: A
TCP-unaware approach to improve performance of TCP over
wireless" Texas A&M University, Technical Report 99-003,
February 1999, 16 pages.
http://www.cs.tamu.edu/faculty/vaidya/papers/mobilecomputing/99-003.ps
Biaz S, Vaidya N et al "TCP over wireless networks using
multiple acknowledgements” , Texas A&M University,
Technical Report 97-001, January 1997, 10 pages.
http://www.cs.tamu.edu/faculty/vaidya/papers/mobilecomputing/97-001.ps
Freeze-TCP: A True End-to-End TCP Enhancement
Mechanism for Mobile Environments http://www.ieeeinfocom.org/2000/papers/501.pdf
RFC2581 "TCP congestion control", The Internet Society
1999
79