CMPE 257 Wireless and Mobile Networking Katia Obraczka Computer Engineering UCSC Baskin Engineering Lecture 9 CMPE 257 Winter 11 1 Student Presentations Feb 28 March 9 Mobility management Tyler and Niosha March 2 DTNs Philip and Rance March 7 Energy management Mohamed Security Jim March 14 Security Chris and and Seth Hybrid networks Gregg and Darien CMPE 257 Winter 11 2 Schedule Exam Feb 23 Project presentations March 17 Time change 5 8pm Approximately 15 minutes for each presentation CMPE 257 Winter 11 3 Today End to end protocols CMPE 257 Winter 11 4 E2E Protocols Reliable point to point Reliable multipoint CMPE 257 Winter 11 5 Reliable Point2Point Transport Layer Outline TCP IP basics Impact of transmission errors on TCP performance Approaches to improve TCP performance on wireless networks Classification TCP on cellular TCP on MANETs CMPE 257 Winter 11 6 Internet Protocol IP Best effort service Packets may be delivered out of order Packets may be lost Packets may be duplicated CMPE 257 Winter 11 7 Transmission Control Protocol Reliable ordered delivery Implements flow and congestion control Reliability through retransmissions End to end semantics ACKs sent to TCP sender confirm delivery of data by TCP receiver ACK for data sent only after it reached receiver CMPE 257 Winter 11 8 TCP Basics Cumulative acknowledgements ACK i acknowledges receipt of packets through i 1 TCP uses byte sequence numbers For simplicity usually refer to packet sequence numbers CMPE 257 Winter 11 9 Cumulative ACKs New ACK generated only on receipt of new in sequence packet 40 39 33 41 38 34 40 34 37 35 39 35 CMPE 257 Winter 11 36 38 36 37 10 Delayed ACKs ACK delayed until Another packet is received or Delayed ACK timer expires 200 ms typical Reduces ACK traffic CMPE 257 Winter 11 11 Delayed ACKs New ACK not produced on receipt of packet 36 but on receipt of 37 40 39 38 33 41 37 35 40 39 35 CMPE 257 Winter 11 38 37 12 Duplicate ACKs A dupack is generated whenever an out of order segment arrives at the receiver CMPE 257 Winter 11 13 Duplicate ACKs 40 39 38 37 34 42 41 36 40 36 Above example assumes delayed acks CMPE 257 Winter 11 39 36 Dupack On receipt of 38 14 Duplicate ACKs Duplicate ACKs are not delayed Duplicate ACKs may be generated when a packet is lost or a packet is delivered out of order OOO CMPE 257 Winter 11 15 Out of Order Packets 40 39 37 38 34 41 40 36 39 37 36 36 Dupack On receipt of 37 CMPE 257 Winter 11 16 Number of Dupacks 40 39 New Ack 41 37 42 New Ack 34 40 New Ack 34 38 39 36 37 New Ack 36 Dupack 36 41 New Ack 36 40 39 Dupack 36 New Ack 38 CMPE 257 Winter 11 17 Window Based Control Sliding window protocol Window size minimum of receiver s advertised window function of available receiver buffer size congestion window determined by sender based on feedback from the network CMPE 257 Winter 11 18 Sliding Window Sender s window 1 2 3 4 5 6 7 8 9 10 11 12 13 Acks received Not transmitted Ack 5 1 2 3 4 5 6 7 8 9 10 11 12 13 Sender s window CMPE 257 Winter 11 19 Self Clocking New data sent when old data is ack d Helps maintain equilibrium Congestion window size bounds the amount of data that can be sent per round trip time Throughput W RTT CMPE 257 Winter 11 20 Window Size Ideal size delay bandwidth What if window size delay bw Inefficiency wasted bandwidth What if delay bw Queuing at intermediate routers Potential for packet loss CMPE 257 Winter 11 21 TCP Packet Loss Detection TCP assumes that packet loss indicates congestion Packet loss detection Retransmission timeout RTO Duplicate acknowledgements CMPE 257 Winter 11 22 RTO For very packet transmitted TCP sender starts timer If acknowledgement for timed packet not received before timer RTO packet assumed lost RTO dynamically calculated CMPE 257 Winter 11 23 RTO Calculation RTO mean 4 mean deviation Large variations in the RTT increase the deviation leading to larger RTO CMPE 257 Winter 11 24 Exponential Backoff Double RTO on each timeout T1 T2 2 T1 Timeout interval doubled Packet transmitted Time out occurs before ack received packet retransmitted CMPE 257 Winter 11 25 Duplicate ACKs Timeouts can take too long How to initiate retransmission sooner Use Duplicate ACKs as loss indicator Dupacks may be generated due to Packet loss or Out of order packet delivery TCP sender assumes packet loss if it receives 3 consecutive dupacks CMPE 257 Winter 11 26 Note on Duplicate ACKs 12 8 11 10 9 7 3 dupacks are also generated if a packet is delivered at least 3 places beyond its in sequence location CMPE 257 Winter 11 27 TCP Congestion Control Slow start Congestion avoidance Fast retransmit Fast recovery Selective acknowledgements SACK CMPE 257 Winter 11 28 Slow Start Initially cwnd 1 MSS max segment size Increment cwnd by 1 MSS on each new ACK Slow start ends when cwnd reaches the slowstart threshold cwnd grows exponentially in slow start Factor of 1 5 per RTT if every other packet ack d Factor of 2 per RTT if every packet ack d Could be less if sender does not always have data to send CMPE 257 Winter 11 29 Congestion Avoidance On each new ACK increase cwnd by 1 cwnd packets cwnd increases linearly with time during congestion avoidance 1 2 MSS per RTT if every other packet ack d 1 MSS per RTT if every packet ack d CMPE 257 Winter 11 30 Congestion Window size segments 14 Congestion avoidance 12 10 Slow start threshold 8 6 4 Slow start 2 0 0 1 2 3 4 5 6 7 8 Time round trips Assumes acks are not delayed CMPE 257 Winter 11 31 Congestion On detecting a packet loss TCP sender assumes network congestion CMPE 257 Winter 11 32 Timeout On a timeout slow start is invoked cwnd is reduced to the initial value of 1 MSS Slow start threshold is set to half the window size before packet loss or ssthresh maximum min cwnd receiver s advertised window 2 2 MSS CMPE 257 Winter 11 33 Timeout cont d After timeout cwnd 20 20 15 10 ssthresh 10 ssthresh 8 5 25 22 20 15 9 12 6 3 0 0 Congestion window segments 25 Time round trips CMPE 257 Winter 11 34 Fast Retransmit When sender receives multiple 3 duplicate ACKs assumes packet lost without waiting for timeout Retransmits packet TCP Tahoe slow start congestion avoidance fast retransmit CMPE 257 Winter 11 35 Fast Recovery Avoids slow start after single packet loss Operates in conjunction with fast retransmit After TCP sender receives 3 duplicate ACKs Retransmits one packet Reduces cwnd by half Every subsequent duplicate ACK clocks transmission New ACK causes sender to exit fast recovery CMPE 257 Winter 11 36 Fast Recovery