《无线网络教学资料》rr-ch00-wireless-tcp-cuiyong

1、Wireless TCP,CS 80240333 Instructor: CUI Yong,1,1,Outline,Traditional TCP Solutions Split approach based solutions Link layer solutions End to end solutions Impact of mobility,2,2,Outline,Traditional TCP Solutions Split approach based solutions Link layer solutions End to end solutions Impact of mob

2、ility,3,3,Review of TCP/IP,IP Packets may be delivered out-of-order Packets may be lost Packets may be duplicated,4,4,Nitin H. Vaidya Infocom06,Review of TCP/IP (contd),TCP connection-oriented Reliable delivery Achieved by means of retransmissions if necessary Congestion avoidance and control End-to

3、-end semantics Acknowledgements sent to TCP sender confirm delivery of data received by TCP receiver Ack for data sent only after data has reached receiver,5,5,6,Slow start,Congestion avoidance,Slow start threshold,Example assumes that acks are not delayed,Review of TCP/IP (contd),Window based flow

4、control Congestion window size bounds the amount of data that can be sent per round-trip time Throughput = W / RTT Congestion Avoidance and Control,How does TCP detect a packet loss?,Retransmission timeout (RTO) TCP sender sets retransmission timer for only one packet If ACK for the timed packet is

5、not received before timer goes off, the packet is assumed to be lost RTO dynamically calculated Duplicate acknowledgements TCP sender assumes that a packet loss has occurred if it receives three dupacks consecutively,7,7,Review of TCP/IP (contd),8,ssthresh = 8,ssthresh = 10,cwnd = 20,After timeout,C

6、ongestion Control,Fast Retransmit Fast retransmit occurs when multiple (= 3) dupacks come back Fast recovery follows fast retransmit Fast Recovery ssthresh = min(cwnd, receivers advertised window)/2 (at least 2 MSS) retransmit the missing segment (fast retransmit) cwnd = ssthresh + number of dupacks

7、 when a new ack comes: cwnd = ssthresh enter congestion avoidance,9,Congestion Control,10,Window size is reduced in half after fast retransmit and fast recovery,Receivers advertised window,After fast recovery,TCP problems in wireless network,TCP assumption Packet loss is due to congestion Need to re

8、duce the transmitting rate But in wireless network Packet loss may be caused by High BER, BER of a wireless channel is 10-3 - 10-5, while that of wired link is 10-8 - 10-10 or better Unstable channel User mobility Need fast retransmission,11,11,Impact of transmission errors,Random errors may cause f

9、ast retransmit retransmission of lost packet reduction in congestion window Burst errors may cause timeouts Timeout results in slow start Slow start reduces congestion window to 1 MSS, reducing throughput Random errors may also cause timeout Multiple packet losses in a window can result in timeout w

10、hen using TCP-Reno (and to a lesser extent when using SACK),12,Impact of transmission errors,TCP cannot distinguish between packet losses due to congestion and transmission errors Reducing congestion window in response to errors is unnecessary Reduction in congestion window reduces the throughput: T

11、hroughput = W / RTT Ideally: W = delay * bandwidth With loss rate p: W (=delay * bandwidth) Throughput suffers,13,Impact of random errors,14,Exponential error model 2 Mbps wireless full duplex link No congestion losses,The throughput is inversely proportional to the error rate,Nitin H. Vaidya ASSET9

12、9,Hidden and exposed station problems,Hidden station problems,15,Exposed station problems,Instability problem,In some scenarios the throughput may drop down to zero which makes the connection unstable even if there is only one TCP connection If station 1 is sending to station 5, the throughput can d

13、rop down to zero in some scenarios because of the following The hidden and exposed station problems that may prevent station 2 from receiving RTS or sending CTS to station 1 The random backoff time High window size that the TCP uses Solutions for the Instability Problem Decreasing the maximum window

14、 size of the TCP layer making the interfering range the same as the communication range,16,In-compatibility problem,Two simultaneous TCP traffics cannot coexist in the network Once one session develops, the other one is shut down The overturn can happen at any time randomly The main cause of this pr

15、oblem The hidden station problem The exposed node problem The exponential back-off scheme in the MAC layer Solutions for the In-Compatibility Problem Changing the back-off policy by penalizing stations that transmit too much data, so the other stations can still use the media Adjusting the interferi

16、ng and the sensing range,17,One-hop unfairness problem,If there are two simultaneous TCP connections one is a single-hop connection and the other is a multi-hop connection, the single-hop connection will be activated even if the multi-hop connection started first Causes are hidden station problem, t

17、he exposed node problem and the exponential back-off scheme Solutions for the Unfairness Problem Active Neighbor Estimation (ANE) based back-off scheme: used instead of the exponential back-off scheme Receiving beam forming (RBF) antennas: A directional antenna will be used to get rid of the undesir

18、ed interference from competing stations.,18,Outline,Traditional TCP Solutions Split approach based solutions Link layer solutions End to end solutions Impact of mobility,19,19,Solutions of TCP over Wireless,Snoop TCP,20,TCP over Wireless,Link layer solutions,Split approach based solutions,End-to-end

19、 solutions,TCP-unaware link layer,I-TCP,Mobile-TCP,ELN,WTCP,TCP SACK,TTCP,Outline,Traditional TCP Solutions Split approach based solutions Link layer solutions End to end solutions Impact of mobility,21,21,Solutions of TCP over Wireless,Snoop TCP,22,TCP over Wireless,Link layer solutions,Split appro

20、ach based solutions,End-to-end solutions,TCP-unaware link layer,I-TCP,Mobile-TCP,ELN,WTCP,TCP SACK,TTCP,Split approach based solutions,Consideration The wired portion is more reliable than wireless portion Wireless link may be a bottleneck So separate the control A single TCP connection split into t

21、wo TCP connections FH-MH = FH-BS + BS-MH,23,23,Split connection approach,24,Per-TCP connection state,TCP connection,TCP connection,Fixed Host,Base Station,Mobile Host,ITCP (Indirect-TCP),Consideration Splitting of TCP connection into two distinct connections one between the MN and BS one between BS

22、and CN,25,A. Bakre ICDCS95,ITCP (contd),Mobile node send a special I-TCP calls to current AP to establish a connection. The Fixed Host is completely unaware of the indirection,26,ITCP Socket and State Migration,27,When MN shifts to a new AP The old AP acts as a foreign agent buffering and forwarding

23、 the packets to the new AP (foreign agent),ITCP (contd),Advantages No changes in the fixed network necessary, no changes for the hosts (TCP protocol) necessary, all current optimizations to TCP still work Transmission errors on the wireless link do not propagate into the fixed network Simple to cont

24、rol, wireless TCP is used only for one hop between a foreign agent and mobile host Fast retransmission of packets is possible,28,ITCP (contd),Disadvantages Loss of end-to-end semantics Higher latency in handoff, due to buffering of data within the foreign agent and forwarding to a new foreign agent,

25、29,MTCP (Mobile-TCP),Problem Mobility - Connection between MN and BS is lost for small intervals of time, this leads to Time out at sender; Slow start at sender Data buffered by AP may be too large MTCP solve this problem with the help of Supervisory Host (SH),30,30,Remains one Ack to FH,Z. Haas ICC

26、97,MTCP (contd),Supervisory host The node in the wired network that controls a number of APs No caching, no retransmission Remains one Ack to FH Monitors all packets, if disconnection detected set sender window size to 0 sender automatically goes into persistent mode (the state of the sender will no

27、t change no matter how long the receiver is disconnected) Old or new SH reopen the window,31,MTCP (contd),Advantages Maintains E2E semantics (Even though TCP connection is split at the supervisory host) Supports disconnection No buffer forwarding Avoids slow start at the sender Disadvantages Loss on

28、 wireless link propagated into fixed network Adapted TCP on wireless link,32,32,Split-based Approach : Classification,Hides transmission errors from sender Primary responsibility at base station If specialized transport protocol used on wireless, then wireless host also needs modification,33,Split-b

29、ased Approach : Advantages,BS-MH connection can be optimized independent of FH-BS connection Different flow / error control on the two connections Local recovery of errors Faster recovery due to relatively shorter RTT on wireless link Good performance achievable using appropriate BS-MH protocol Stan

30、dard TCP on BS-MH performs poorly when multiple packet losses occur per window (Selective acks improve performance for such cases),34,Split-based Approach : Disadvantages,End-to-end semantics violated Ack may be delivered to sender, before data delivered to the receiver May not be a problem for appl

31、ications that do not rely on TCP for the end-to-end semantics,35,BS retains hard state BS failure can result in loss of data (unreliability) If BS fails, packet 40 will be lost Because it is ackd to sender, the sender does not buffer 40,36,Split-based Approach : Disadvantages,Split-based Approach :

32、Disadvantages,BS retains hard state Hand-off latency increases due to state transfer Data that has been ackd to sender, must be moved to new base station,37,Split-based Approach : Disadvantages,Buffer space needed at BS for each TCP connection BS buffers tend to get full, when wireless link slower (

33、one window worth of data on wired connection could be stored at the base station, for each split connection) Window on BS-MH connection reduced in response to errors may not be an issue for wireless links with small delay-bw product,38,Split-based Approach : Disadvantages,Extra copying of data at BS

34、 copying from FH-BS socket buffer to BS-MH socket buffer increases end-to-end latency May not be useful if data and acks traverse different paths (both do not go through the base station) Example: data on a satellite wireless hop, acks on a dial-up channel,39,ack,Outline,Traditional TCP Solutions Sp

35、lit approach based solutions Link layer solutions End to end solutions Impact of mobility,40,40,Solutions of TCP over Wireless,Snoop TCP,41,TCP over Wireless,Link layer solutions,Split approach based solutions,End-to-end solutions,TCP-unaware link layer,I-TCP,Mobile-TCP,ELN,WTCP,TCP SACK,TTCP,Link l

36、ayer solution,Goal: Let link layer correct all errors Mechanism FEC (Forward Error Correction): redundancy is encoded into the message Used to correct small number of errors FEC incurs overhead even when errors do not occur ARQ (Automatic Repeat Request): Retransmission at link layer Used when FEC c

37、apability is exceeded Retransmission overhead incurred only if errors occur HARQ: FEC+ARQ,42,42,Link level retransmissions,43,TCP connection,Link layer state,Link level retransmissions: Issues,How many times to retransmit at the link level before giving up? Finite bound - semi-reliable link layer No

38、 bound - reliable link layer What triggers link level retransmissions? Link layer timeout mechanism Link level acks (negative acks, dupacks, ) Other mechanisms (e.g., Snoop, as discussed later) How much time is required for a link layer retransmission? Small fraction of end-to-end TCP RTT Large frac

39、tion/multiple of end-to-end TCP RTT,44,Link level retransmissions: Issues,Should the link layer deliver packets as they arrive, or deliver them in-order? Link layer may need to buffer packets and reorder if necessary so as to deliver packets in-order Retransmissions can cause head-of-the-line blocki

40、ng,45,Although link to receiver 1 may be in a bad state, the link to receiver 2 may be in a good state Retransmissions to receiver 1 are lost, and also block a packet from being sent to receiver 2,Base station,Link level retransmissions: Issues,Retransmissions can cause congestion losses Attempting

41、to retransmit a packet at the front of the queue, effectively reduces the available bandwidth, potentially making the queue at base station longer If the queue gets full, packets may be lost, indicating congestion to the sender Is this desirable or not ?,46,Link level retransmissions:An early study,

42、The senders Retransmission Timeout (RTO) is a function of measured RTT (round-trip times) Link level retransmits increase RTT, therefore, RTO If errors not frequent, RTO will not account for RTT variations due to link level retransmissions When errors occur, the sender may timeout & retransmit befor

43、e link level retransmission is successful Sender and link layer both retransmit Duplicate retransmissions (interference) waste wireless bandwidth Timeouts also result in reduced congestion window Disadvantage: not accurately model real TCP stacks,47,A. DeSimone Globecom93,Link level retransmissions:

44、A more accurate picture,Frequent errors increase RTO significantly on slow wireless links Likelihood of interference between link layer and TCP retransmissions smaller But congestion response will be delayed due to larger RTO When wireless losses do cause timeout, much time wasted Large TCP Retransm

45、ission Timeout Intervals Good for reducing interference with link level retransmits Bad for recovery from congestion losses Need a timeout mechanism that responds appropriately for both types of losses (Open problem),48,H. Balakrishnan Sigcomm96,Link level retransmissions:In-order delivery,To avoid

46、unnecessary fast retransmit, link layer using retransmission should attempt to deliver packets “almost in-order” In-order delivery Not all connections benefit from retransmissions or ordered delivery (audio) Need to be able to specify requirements on a per-packet basis Should the packet be retransmi

47、tted? How many times? Enforce in-order delivery? Need a standard mechanism to specify the requirements open issue (IETF PILC working group),49,R. Ludwig Sigmetrics98,Link layer schemes: Summary,When is a reliable link layer beneficial to TCP performance? If it provides almost in-order delivery and T

48、CP retransmission timeout large enough to tolerate additional delays due to link level retransmits,50,Link layer schemes: Classification,Hide wireless losses from TCP sender Link layer modifications needed at both ends of wireless link TCP need not be modified,51,Snoop TCP,“Transparent” extension of

49、 TCP within the BS(foreign agent) Buffering of packets sent to the mobile node Lost packets on the wireless link (both directions!) will be retransmitted immediately by the mobile node or base station (foreign agent), The BS therefore “snoops” the packet flow and recognizes acknowledgements in both

50、directions Changes of TCP only within the BS,52,H. Balakrishnan ACM95,Snoop TCP,53,Data transfer to the mobile host FA buffers data until it receives ACK of the MH, FA detects packet loss via duplicated ACKs (DUPACKs) or time-out Fast retransmission possible, transparent for the fixed network,Data t

51、ransfer from the mobile host FA detects packet loss on the wireless link via sequence numbers, FA answers directly with a NACK to the MH MH can now retransmit data with only a very short delay,Snoop TCP,Retains local recovery of Split Connection approach and link level retransmission schemes Integra

52、tion of the MAC layer MAC layer often has similar mechanisms to those of TCP The MAC layer can already detect duplicated packets due to retransmissions and discard them Improves on split connection end-to-end semantics retained soft state at base station, instead of hard state Hides wireless losses

53、from the sender Requires modification to only BS (network-centric approach),54,Snoop TCP,55,2 Mbps Wireless link,Throughput gain of Snoop compared to base TCP,Snoop TCP: When Beneficial?,Snoop prevents fast retransmit from sender despite transmission errors, and out-of-order delivery on the wireless

54、 link Out-of-order delivery causes fast retransmit only if it results in at least 3 dupacks If wireless link level delay-bandwidth product is less than 4 packets, a simple (TCP-unaware) link level retransmission scheme can suffice Since delay-bandwidth product is small, the retransmission scheme can

55、 deliver the lost packet without resulting in 3 dupacks from the TCP receiver,56,Snoop TCP: Advantages,High throughput can be achieved performance further improved using selective acks Local recovery from wireless losses Fast retransmit not triggered at sender despite out-of-order link layer deliver

56、y End-to-end semantics retained Soft state at base station loss of the soft state affects performance, but not correctness,57,Snoop TCP: Disadvantages,Link layer at base station needs to be TCP-aware Does not isolate the wireless link as good as I-TCP Not useful if TCP headers are encrypted (IPsec)

57、Cannot be used if TCP data and TCP acks traverse different paths (both do not go through the base station),58,TCP-unaware link layer,Goal Simulate the behavior of the snoop TCP Without requiring the link layer at the BS to be TCP aware At the BS, link layer retransmission is used to perform local er

58、ror recovery In snoop-TCP retransmissions are triggered by TCP duplicate acknowledgements, but in TCP-unaware link layer retransmissions are triggered by link level ACKs,59,59,TCP-unaware link layer (contd),MN reduces interference between TCP and link level retransmission For the first two packets,

59、sending dupacks immediately For further consecutive packets, dupacks are delayed for duration d,60,60,Interference in Traditional TCP,61,61,TCP-unaware link layer (contd),62,62,TCP-unaware link layer (contd),Advantages Link Layer need not be TCP aware. Works well for small round trip times (RTTs) over the wireless link. Disadvantage Optimal value of DUPACK delay is dependent on the wireless link.,63,63,Outline,Traditional TCP Solutions Split approach based solutions Link layer solutions End to end solutions Impact of mobility,64,