3rd Edition: Chapter 3 - PDF Free Download

Chapter 3 Transport Layer A note on the use of these ppt slides: We re making these slides freely available to all (faculty, students, readers). They re in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, we d like people to use our book!) If you post any slides in substantially unaltered form on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material. Computer Networking: A Top Down Approach 5 th edition. Jim Kurose, Keith Ross Addison-Wesley, April 2009. Thanks and enjoy! JFK/KWR All material copyright 1996-2009 J.F Kurose and K.W. Ross, All Rights Reserved Transport Layer 3-1

Chapter 3: Transport Layer Our goals: understand principles behind transport layer services: multiplexing/demultipl exing reliable data transfer flow control congestion control learn about transport layer protocols in the Internet: UDP: connectionless transport TCP: connection-oriented transport TCP congestion control Transport Layer 3-2

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer 3-3

Transport services and protocols provide logical communication between app processes running on different hosts transport protocols run in end systems send side: breaks app messages into segments, passes to network layer rcv side: reassembles segments into messages, passes to app layer more than one transport protocol available to apps Internet: TCP and UDP application transport network data link physical application transport network data link physical Transport Layer 3-4

Transport vs. network layer network layer: logical communication between hosts transport layer: logical communication between processes relies on, enhances, network layer services Household analogy: 12 kids sending letters to 12 kids processes = kids app messages = letters in envelopes hosts = houses transport protocol = Ann and Bill network-layer protocol = postal service Transport Layer 3-5

Internet transport-layer protocols reliable, in-order delivery (TCP) congestion control flow control connection setup unreliable, unordered delivery: UDP no-frills extension of best-effort IP services not available: delay guarantees bandwidth guarantees application transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical application transport network data link physical Transport Layer 3-6

Multiplexing/demultiplexing Demultiplexing at rcv host: delivering received segments to correct socket = socket = process Multiplexing at send host: gathering data from multiple sockets, enveloping data with header (later used for demultiplexing) application P3 P1 P1 application P2 P4 application transport transport transport network network network link link link physical physical host 1 host 2 host 3 physical Transport Layer 3-8

How demultiplexing works host receives IP datagrams each datagram has source IP address, destination IP address each datagram carries 1 transport-layer segment each segment has source, destination port number host uses IP addresses & port numbers to direct segment to appropriate socket 32 bits source port # dest port # other header fields application data (message) TCP/UDP segment format Transport Layer 3-9

Connectionless demultiplexing Client 소켓생성 Transport 층에서 Port 번호자동생성하게함 - 일반적인경우 DatagramSocket mysocket1 = new DatagramSocket( ); Port 번호를 explicit 하게주어생성 DatagramSocket mysocket2 = new DatagramSocket(99222); 99222는 client 소켓의포트번호 Server 소켓생성 Port 번호를 explicit 하게줌 DatagramSocket serversocket = new DatagramSocket(6428); Transport Layer 3-10

Connectionless demultiplexing 두개의 UDP segment 가서로다른 source IP 주소 and/or source port 번호를가진고있다해도목적지 IP 주소와 port 번호가같으면동일한프로세스로전달됨 즉, UDP socket identified by dest. two-tuple: (dest IP address, dest port number) Src. IP 주소와 src. port 번호는 datagram 을 return 시 return 주소역할만을하는식별자 Transport Layer 3-11

Connectionless demux (cont) DatagramSocket serversocket = new DatagramSocket(6428); P2 P3 P1 P1 SP: 6428 DP: 9157 SP: 6428 DP: 5775 SP: 9157 SP: 5775 client IP: A DP: 6428 server IP: C DP: 6428 Client IP:B SP provides return address Transport Layer 3-12

Connection-oriented demux TCP socket identified by 4-tuple: source IP address source port number dest IP address dest port number recv host uses all four values to direct segment to appropriate socket Server host may support many simultaneous TCP sockets: each socket identified by its own 4-tuple Web servers have different sockets for each connecting client non-persistent HTTP will have different socket for each request Transport Layer 3-13

Connection-oriented demux (cont) S-IP 가같아도 SP 가다르므로다른소켓 P1 P4 P5 P6 P2 P1 P3 SP: 5775 DP: 80 S-IP: B D-IP:C SP: 9157 SP: 9157 client IP: A DP: 80 S-IP: A D-IP:C server IP: C DP: 80 S-IP: B D-IP:C Client IP:B SP 가같아도 S-IP 가다르므로다른소켓 Transport Layer 3-14

Connection-oriented demux: Threaded Web Server P1 P4 P2 P1 P3 SP: 5775 DP: 80 S-IP: B D-IP:C SP: 9157 SP: 9157 client IP: A DP: 80 S-IP: A D-IP:C server IP: C DP: 80 S-IP: B D-IP:C Client IP:B Transport Layer 3-15

UDP: User Datagram Protocol [RFC 768] no frills, bare bones Internet transport protocol best effort service, UDP segments may be: lost delivered out of order to app connectionless: no handshaking between UDP sender, receiver each UDP segment handled independently of others Why is there a UDP? no connection establishment (which can add delay) simple: no connection state at sender, receiver small segment header no congestion control: UDP can blast away as fast as desired Transport Layer 3-17

UDP: more often used for streaming multimedia apps loss tolerant rate sensitive other UDP uses DNS SNMP TCP 의 congestion control 메커니즘은원하지않으나, UDP 를사용하면서 reliable data transfer 를원한다면, application 층에서 Ack 와 retransmission 기능을갖도록해야함 Streaming application 에서많이이렇게함 Length, in bytes of UDP segment, including header 32 bits source port # dest port # length Application data (message) checksum UDP segment format Transport Layer 3-18

UDP checksum Goal: detect errors (e.g., flipped bits) in transmitted segment Sender: treat segment contents as sequence of 16-bit integers checksum: addition of segment contents make 1 s complement of sum 1 s complement: 1 은 0 으로, 0 은 1 로변환 sender puts checksum value into UDP checksum field Receiver: compute checksum of received segment check if computed checksum equals checksum field value: NO - error detected YES - no error detected. But maybe errors nonetheless? More later. Transport Layer 3-19

Internet Checksum Example Note When adding numbers, a carryout from the most significant bit needs to be added to the result Example: add two 16-bit integers 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 wraparound sum checksum 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 Transport Layer 3-20

UDP checksum UDP 에서 checksum 을하는이유 Src 와 dest 간의모든 link 가 error checking 을한다고장담할수없으므로 UDP segment 가라우터의메모리에저장되어있을때에러가발생가능하므로 Error recovery 는하지않음 Implementation dependent Discard damaged segment Pass damaged segment to app. Layer with warning Transport Layer 3-21

Principles of Reliable data transfer important in app., transport, link layers top-10 list of important networking topics! characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt) Transport Layer 3-23

Reliable data transfer: getting started rdt_send(): called from above, (e.g., by app.). Passed data to deliver to receiver upper layer deliver_data(): called by rdt to deliver data to upper send side receive side udt_send(): called by rdt, to transfer packet over unreliable channel to receiver rdt_rcv(): called when packet arrives on rcv-side of channel Transport Layer 3-26

Reliable data transfer: getting started We ll: incrementally develop sender, receiver sides of reliable data transfer protocol (rdt) consider only unidirectional data transfer but control info will flow on both directions! use finite state machines (FSM) to specify sender, receiver state: when in this state next state uniquely determined by next event state 1 event causing state transition actions taken on state transition event actions state 2 Transport Layer 3-27

Rdt1.0: reliable transfer over a reliable channel Bit error나 packet loss 가없는완벽한채널가정 error recovery에관한특별한기능필요없음 separate FSMs for sender, receiver: sender sends data into underlying channel receiver read data from underlying channel Wait for call from above rdt_send(data) packet = make_pkt(data) udt_send(packet) Wait for call from below rdt_rcv(packet) extract (packet,data) deliver_data(data) sender receiver Transport Layer 3-28

Rdt2.0: channel with bit errors Bit error 가날수있다는가정, loss 는가정하지않음 checksum to detect bit errors the question: how to recover from errors: ACKs (acknowledgements ): receiver explicitly tells sender that pkt received OK NAKs (negative acknowledgements ): receiver explicitly tells sender that pkt had errors sender retransmits pkt on receipt of NAK new mechanisms in rdt2.0 (beyond rdt1.0): error detection ACK, NAK 사용하는 stop-and-wait protocol stop and wait Sender sends one packet, then waits for receiver response Sol.: ACK, NAK 사용 Transport Layer 3-29

rdt2.0: FSM specification rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) Wait for call from above rdt_rcv(rcvpkt) && isack(rcvpkt) L sender Wait for ACK or NAK rdt_rcv(rcvpkt) && isnak(rcvpkt) udt_send(sndpkt) receiver rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(nak) Wait for call from below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ack) Transport Layer 3-30

rdt2.0: operation with no errors rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) Wait for call from above rdt_rcv(rcvpkt) && isack(rcvpkt) L Wait for ACK or NAK rdt_rcv(rcvpkt) && isnak(rcvpkt) udt_send(sndpkt) rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(nak) Wait for call from below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ack) Transport Layer 3-31

rdt2.0: error scenario rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) Wait for call from above rdt_rcv(rcvpkt) && isack(rcvpkt) L Wait for ACK or NAK rdt_rcv(rcvpkt) && isnak(rcvpkt) udt_send(sndpkt) rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(nak) Wait for call from below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ack) Transport Layer 3-32

rdt2.0 has a fatal flaw! rtd 2.1: ACK 나 NAK 도 error 가날수있다는문제를해결하기위함 해결책 송신측은 garbled 된 ACK 나 NAK 수신시 packet 을재전송함. 그러나이패킷을받은수신측은재전송인지앞의패킷과동일한형태의새로운패킷인지구별할수가없음. 해결책 패킷에 1 bit sequence number 를붙임. 새로운패킷들은 0 과 1 으로 alternate 하게 sequence number 를붙여보내므로수신측에서는재전송된것인지새로운패킷인지구별할수있음 Transport Layer 3-33

rdt2.1: sender, handles garbled ACK/NAKs rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt) L rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) isnak(rcvpkt) ) udt_send(sndpkt) rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) Wait for call 0 from above Wait for ACK or NAK 1 rdt_send(data) Wait for ACK or NAK 0 Wait for call 1 from above rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) isnak(rcvpkt) ) udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt) sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) L Transport Layer 3-34

rdt2.1: receiver, handles garbled ACK/NAKs rdt_rcv(rcvpkt) && (corrupt(rcvpkt) sndpkt = make_pkt(nak, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq1(rcvpkt) sndpkt = make_pkt(ack, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ack, chksum) udt_send(sndpkt) Wait for 0 from below Wait for 1 from below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) sndpkt = make_pkt(nak, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq0(rcvpkt) sndpkt = make_pkt(ack, chksum) udt_send(sndpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ack, chksum) udt_send(sndpkt) Transport Layer 3-35

rdt2.1: discussion Sender: seq # added to pkt two seq. # s (0,1) will suffice. Why? must check if received ACK/NAK corrupted twice as many states state must remember whether current pkt has 0 or 1 seq. # Receiver: must check if received packet is duplicate state indicates whether 0 or 1 is expected pkt seq # note: receiver can not know if its last ACK/NAK received OK at sender Transport Layer 3-36

rdt2.2: a NAK-free protocol rtd 2.1 과같으나 ACK, NAK 대신 ACK 0, ACK 1 을사용 ( 즉, sequence number 를 explicitly 하게사용 ) same functionality as rdt2.1, using ACKs only instead of NAK, receiver sends ACK for last pkt received OK receiver must explicitly include seq # of pkt being ACKed 동일한 ACK 가두번왔을경우 ( 예 : ACK 0 followed by ACK 0) 송신측은수신측에서받은 Packet 1 에문제가있다고판단하고 packet 1 을재전송함 Transport Layer 3-37

rdt2.2: sender, receiver fragments rdt_rcv(rcvpkt) && (corrupt(rcvpkt) has_seq1(rcvpkt)) udt_send(sndpkt) rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) Wait for call 0 from above Wait for 0 from below Wait for ACK 0 sender FSM fragment receiver FSM fragment rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) isack(rcvpkt,1) ) udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt,0) L rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ack1, chksum) udt_send(sndpkt) Transport Layer 3-38

rdt3.0: channels with errors and loss Bit error 뿐만아니라패킷손실도발생할경우 Sol.: 일정한시간내에 ACK 가오지않으면재전송 New assumption: underlying channel can also lose packets (data or ACKs) checksum, seq. #, ACKs, retransmissions will be of help, but not enough Approach: sender waits reasonable amount of time for ACK retransmits if no ACK received in this time if pkt (or ACK) just delayed (not lost): retransmission will be duplicate, but use of seq. # s already handles this receiver must specify seq # of pkt being ACKed requires countdown timer Transport Layer 3-39

rdt3.0 sender rdt_rcv(rcvpkt) L Wait for call 0from above rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt,1) stop_timer timeout udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) isack(rcvpkt,0) ) L Wait for ACK1 rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer rdt_send(data) Wait for ACK0 Wait for call 1 from above sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) isack(rcvpkt,1) ) L timeout udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt,0) stop_timer rdt_rcv(rcvpkt) L Transport Layer 3-40

rdt3.0 in action Transport Layer 3-41

rdt3.0 in action Pkt1 을재전송하고 ACK1 을받았으므로, 아무일도하지않으면된다 Transport Layer 3-42

Performance of rdt3.0 rdt3.0 works, but performance stinks ex: 1 Gbps link, 15 ms prop. delay, 8000 bit packet: d trans R L 8000bits 10 bps 9 8microseconds U sender : utilization fraction of time sender busy sending U sender = L / R RTT + L / R =.008 30.008 = 0.00027 microsec 1KB pkt every 30 msec -> 33kB/sec thruput over 1 Gbps link network protocol limits use of physical resources! Transport Layer 3-43

rdt3.0: stop-and-wait operation first packet bit transmitted, t = 0 last packet bit transmitted, t = L / R sender receiver RTT first packet bit arrives last packet bit arrives, send ACK ACK arrives, send next packet, t = RTT + L / R U sender = L / R RTT + L / R =.008 30.008 = 0.00027 microsec Transport Layer 3-44

Pipelined protocols Pipelining: ACK 를안받고도복수개의패킷을전송할수있게허용함 pipelined protocols: go-back-n, selective repeat range of sequence numbers must be increased buffering at sender and/or receiver Transport Layer 3-45

Pipelining: increased utilization first packet bit transmitted, t = 0 last bit transmitted, t = L / R sender receiver RTT ACK arrives, send next packet, t = RTT + L / R first packet bit arrives last packet bit arrives, send ACK last bit of 2 nd packet arrives, send ACK last bit of 3 rd packet arrives, send ACK Increase utilization by a factor of 3! U sender = 3 * L / R RTT + L / R =.024 30.008 = 0.0008 microsecon Transport Layer 3-46

Pipelining Protocols Go-back-N: big picture: Sender can have up to N unacked packets in pipeline Rcvr only sends cumulative acks Doesn t ack packet if there s a gap Sender has timer for oldest unacked packet If timer expires, retransmit all unacked packets Selective Repeat: big pic Sender can have up to N unacked packets in pipeline Rcvr acks individual packets Sender maintains timer for each unacked packet When timer expires, retransmit only unack packet Transport Layer 3-47

Selective repeat: big picture Sender can have up to N unacked packets in pipeline Rcvr acks individual packets Sender maintains timer for each unacked packet When timer expires, retransmit only unack packet Transport Layer 3-48

Go-Back-N Sender: Window size 가 N이면 N개까지의패킷이 ACK를받지않고도전송가능실제로는패킷헤더에 k-bit seq number 사용 Sequence number는 0~2 k -1 ( 이때 window size는 2 k 보다작게설정 ) Sender s window Transport Layer 3-49

Go-Back-N: 동작 ACK 는 cumulative ACK ACK n 은 sequence number 가 n 인패킷까지다잘받았다는것을의미 Lost data 나 lost ACK 를복구하기위하여 timer 사용 timer for each in-flight pkt timeout(n): 패킷 n 에대해 timeout 이걸리면 ( 즉, timer 가 expire 할때까지 ACK 가안오면 ) n 부터시작해서이미보낸모든패킷재전송 수신자는 out-of-order 패킷은모두 discard 즉, 패킷 1 이온후패킷 2 가오지않았는데, 패킷 3 이오면패킷 3 을 discard 이때 ACK 는 ACK 1 을다시보냄 (duplicate ACK) Transport Layer 3-50

GBN in action Window size N=4 의경우 Sequence number=0~5 Window 가고갈되어서 (Duplicate ACK) (Duplicate ACK) (Duplicate ACK) Transport Layer 3-51

Selective Repeat ACK 는 cumulative ACK 가아니라개별패킷에대한 ACK 즉, ACK 3 은패킷 3 에대한 ACK 수신측은 Out-of order 된패킷을받으면 buffering 을함 ACK 도보냄 Sender 는 ACK 가오지않은패킷만선택적으로재전송함 sender timer for each in-flight pkt 송수신 window 움직임 일반적으로수신윈도우는 ACK 를 1 개받으면 1 슬롯움직이고, 수신윈도우는한패킷을받으면한슬롯움직인다. 수신윈도우 Out-of order 된패킷을받았을때는수신 window 는움직이지않음 송신윈도우 ACK 를받아도그이전패킷에 ACK 가오지않은패킷이있을때는송신 window 는움직이지않는다 즉, 2 에대한 ACK 가오지않았는데, ACK3 을받으면윈도우는움직이지않음 Transport Layer 3-52

Selective repeat in action Window size N=4 의경우 Sequence number=0~9 Buffering 하고있는패킷에대해 window 는움직이지않음 ACK3 을받아도 2 에대한 ACK 를못받았으므로 window 는움직이지않음 (3 은 ACK 받았다고기록함 ) Transport Layer 3-53

Selective repeat: sender, receiver windows Transport Layer 3-54

Selective repeat sender data from above : if next available seq # in window, send pkt timeout(n): resend pkt n, restart timer ACK(n) in [sendbase,sendbase+n]: mark pkt n as received if n smallest unacked pkt, advance window base to next unacked seq # receiver pkt n in [rcvbase, rcvbase+n-1] send ACK(n) out-of-order: buffer in-order: deliver (also deliver buffered, in-order pkts), advance window to next not-yet-received pkt pkt n in [rcvbase-n,rcvbase-1] ACK(n) otherwise: ignore Transport Layer 3-55

Selective repeat: dilemma Example: seq number= 0~3 window size N =3 (old packet) 수신측에서볼때는 (a) 와 (b) 의경우가구별이안됨 (a) 의경우마지막받은패킷 0 는 new 패킷으로간주하게됨 Q: what relationship between seq # size and window size? A: N ½ seq # size (new packet) Transport Layer 3-56

TCP: Overview RFCs: 793, 1122, 1323, 2018, 2581 socket door point-to-point: one sender, one receiver reliable, in-order byte steam: no message boundaries pipelined: TCP congestion and flow control set window size send & receive buffers application writes data TCP send buffer segment application reads data TCP receive buffer socket door full duplex data: bi-directional data flow in same connection MSS: maximum segment size connection-oriented: handshaking (exchange of control msgs) init s sender, receiver state before data exchange flow controlled: sender will not overwhelm receiver Transport Layer 3-58

TCP segment structure URG: urgent data (generally not used) ACK: ACK # valid PSH: push data now (generally not used) RST, SYN, FIN: connection estab (setup, teardown commands) Internet checksum (as in UDP) 32 bits source port # dest port # head len sequence number acknowledgement number not used U A P R S F checksum Receive window Urg data pnter Options (variable length) application data (variable length) Header= 20 bytes counting by bytes of data (not segments!) # bytes rcvr willing to accept Transport Layer 3-59

TCP seq. # s and ACKs Sequence number 의의미 Segment 의 sequence number: Segment 의맨첫번째 data byte 가전체데이터 stream 에서몇번째 byte 인가를표시 data stream 이 500,000 bytes 짜리인 file 전송의예 MSS (maximum segment size)=1000 bytes 면 data stream 은 segment 크기가 1000 byte 인 segment 500 개로구성가능 1 번세그먼트의 seq. # = 0, 2 번세그먼트의 seq. #=1000 Transport Layer 3-60

TCP seq. # s and ACKs ACK number 의의미 수신측이다음에받기를원하는 byte 의 sequence number Cumulative ACK 사용 (GBN 에서와동일방법 ) 수신측이 out-of-order 패킷수신시처리방법 Implementation dependent Discard (GBN 에서와동일방법 ) Buffering (SR 에서와동일방법 ): 실제많이사용 TCP connection 이맺어질때, 초기의 sequence number 는송수신모두 random 하게선택 Transport Layer 3-61

TCP seq. # s and ACKs Telnet 예 User 가키보드로캐릭터 c 를입력하면이것이서버로전달되고다시서버로부터 echo back 되어 user 의 terminal 에 display 되는과정 번분석 A 가 seq # 79 를기대하므로 (ACK=79 이었으므로 ) seq # =79, 에서 seq# 는 42 이었고 c 라는한 byte 가왔으므로다음기대하는 seq # =43 번분석 에서 seq # 42 로한 byte 를보낸다음이므로 seq # = 43, 에서 seq# 는 79 이었고 c 라는한 byte 가왔으므로다음기대하는 seq # =80 User types C host ACKs receipt of echoed C Host A Host B simple telnet scenario host ACKs receipt of C, echoes back C Transport Layer 3-62 time

TCP Round Trip Time and Timeout Q: how to set TCP timeout value? longer than RTT but RTT varies too short: premature timeout unnecessary retransmissions too long: slow reaction to segment loss Q: how to estimate RTT? SampleRTT: measured time from segment transmission until ACK receipt ignore retransmissions SampleRTT will vary, want estimated RTT smoother average several recent measurements, not just current SampleRTT Transport Layer 3-63

TCP Round Trip Time and Timeout EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT Exponential weighted moving average influence of past sample decreases exponentially fast typical value: = 0.125 Transport Layer 3-64

RTT (milliseconds) Example RTT estimation: RTT: gaia.cs.umass.edu to fantasia.eurecom.fr 350 300 250 200 150 100 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 time (seconnds) SampleRTT Estimated RTT Transport Layer 3-65

TCP Round Trip Time and Timeout Setting the timeout EstimtedRTT plus safety margin large variation in EstimatedRTT -> larger safety margin first estimate of how much SampleRTT deviates from EstimatedRTT: DevRTT = (1- )*DevRTT + * SampleRTT-EstimatedRTT (typically, = 0.25) Then set timeout interval: TimeoutInterval = EstimatedRTT + 4*DevRTT Transport Layer 3-66

TCP reliable data transfer TCP creates rdt service on top of IP s unreliable service Pipelined segments Cumulative acks TCP uses single retransmission timer Retransmissions are triggered by: timeout events duplicate acks Initially consider simplified TCP sender: ignore duplicate acks ignore flow control, congestion control Transport Layer 3-68

TCP sender events: data rcvd from app: Create segment with seq # seq # is byte-stream number of first data byte in segment start timer if not already running (think of timer as for oldest unacked segment) expiration interval: TimeOutInterval timeout: retransmit segment that caused timeout restart timer Ack rcvd: If acknowledges previously unacked segments update what is known to be acked start timer if there are outstanding segments Transport Layer 3-69

NextSeqNum = InitialSeqNum SendBase = InitialSeqNum loop (forever) { switch(event) event: data received from application above create TCP segment with sequence number NextSeqNum if (timer currently not running) start timer pass segment to IP NextSeqNum = NextSeqNum + length(data) event: timer timeout retransmit not-yet-acknowledged segment with smallest sequence number start timer event: ACK received, with ACK field value of y if (y > SendBase) { SendBase = y if (there are currently not-yet-acknowledged segments) start timer } } /* end of loop forever */ TCP sender (simplified) Comment: SendBase: ACK 를받아야될최소 seq. 번호 ( 즉, SendBase-1 byte 로끝나는 segment 까지는 ACK 를받았음 ) 정상적 ACK 번호는 SendBase 보다커야한다 ( 송신측은 SendBase 로시작하는 segment 를보낸상태고수신측은이 segment 를받은후, 다음에받고자하는번호 ( 즉, 그 segment 의마지막 byte 번호 + 1) 를주므로 ). Example: SendBase=70; y=73, ( 송신측은 70 으로시작하는 segment 에대한 ACK 를기다리는데수신측은 73 을기다린다고왔음 ) ; y > SendBase 이고 cumulative ACK 를사용하므로 y-1 (=72) 까지는 ACK 를해주는것으로간주하므로 SendBase=y (=73) 으로 update Transport Layer 3-70

Seq=92 timeout timeout Seq=92 timeout TCP: retransmission scenarios Host A Host B Host A Host B X loss Sendbase = 100 SendBase = 120 SendBase = 100 time 99까지에대한 ACK가왔으므로다음에 ACK 받아야할 byte는 100번쨰 lost ACK scenario SendBase = 120 time premature timeout Transport Layer 3-71

timeout TCP retransmission scenarios (more) Host A Host B X loss SendBase = 120 Cumulative ACK 로해석하므로 119 까지잘받은것으로해석. Timer expire 하기전에왔으므로재전송하지않음 time Cumulative ACK scenario Transport Layer 3-72

TCP ACK generation [RFC 1122, RFC 2581] Event at Receiver Arrival of in-order segment with expected seq #. All data up to expected seq # already ACKed Arrival of in-order segment with expected seq #. One other segment has ACK pending Arrival of out-of-order segment higher-than-expect seq. #. Gap detected Arrival of segment that partially or completely fills gap TCP Receiver action Delayed ACK. Wait up to 500ms for next segment. If no next segment, send ACK Immediately send single cumulative ACK, ACKing both in-order segments Immediately send duplicate ACK, indicating seq. # of next expected byte Immediate send ACK, provided that segment starts at lower end of gap Transport Layer 3-73

Fast Retransmit Time-out period often relatively long: long delay before resending lost packet Detect lost segments via duplicate ACKs. Sender often sends many segments back-toback If segment is lost, there will likely be many duplicate ACKs. Timer 가 expire 하기전이라도동일한 ACK 를 3 번받으면바로재전송시작 (duplicate ACK 는 outof-order 패킷이수신될시수신측에서발생시키기때문에현재까지 ACK 가완료된패킷다음패킷이손실난상태에서그다음패킷들이계속수신되는경우임 ) If sender receives 3 ACKs for the same data, it supposes that segment after ACKed data was lost: fast retransmit: resend segment before timer expires Transport Layer 3-74

timeout Host A Host B X time Figure 3.37 Resending a segment after triple duplicate ACK Transport Layer 3-75

Fast retransmit algorithm: event: ACK received, with ACK field value of y if (y > SendBase) { SendBase = y if (there are currently not-yet-acknowledged segments) start timer } else { increment count of dup ACKs received for y if (count of dup ACKs received for y = 3) { resend segment with sequence number y } a duplicate ACK for already ACKed segment fast retransmit Transport Layer 3-76

TCP Flow Control receive side of TCP connection has a receive buffer: flow control sender won t overflow receiver s buffer by transmitting too much, too fast app process may be slow at reading from buffer speed-matching service: matching the send rate to the receiving app s drain rate Transport Layer 3-78

TCP Flow control: how it works (Suppose TCP receiver discards out-of-order segments) spare room in buffer = RcvWindow = RcvBuffer-[LastByteRcvd - LastByteRead] Rcvr advertises spare room by including value of RcvWindow in segments Sender limits unacked data to RcvWindow guarantees receive buffer doesn t overflow Transport Layer 3-79

TCP Connection Management Recall: TCP sender, receiver establish connection before exchanging data segments initialize TCP variables: seq. #s buffers, flow control info (e.g. RcvWindow) client: connection initiator Socket clientsocket = new Socket("hostname","port number"); server: contacted by client Socket connectionsocket = welcomesocket.accept(); Transport Layer 3-81

Three way handshake Step 1: client host sends TCP SYN segment(syn bit=1) to server specifies initial seq # (isn) no data Step 2: server host receives SYN, replies with SYNACK segment(syn bit=1) Allocate TCP buffers & variables server allocates buffers specifies server initial seq. # Step 3: client receives SYNACK, replies with ACK segment, which may contain data Transport Layer 3-82

timed wait TCP Connection Management (cont.) Closing a connection: client closes socket: clientsocket.close(); close client server Step 1: client end system sends TCP FIN control segment to server close Step 2: server receives FIN, replies with ACK. Closes connection, sends FIN. closed Transport Layer 3-83

timed wait TCP Connection Management (cont.) Step 3: client receives FIN, replies with ACK. Enters timed wait - will respond with ACK to received FINs closing client server closing Step 4: server, receives ACK. Connection closed. Note: with small modification, can handle simultaneous FINs. closed closed Transport Layer 3-84

TCP Connection Management (cont) TCP server lifecycle TCP client lifecycle Transport Layer 3-85

Principles of Congestion Control Congestion: informally: too many sources sending too much data too fast for network to handle different from flow control! manifestations: lost packets (buffer overflow at routers) long delays (queueing in router buffers) a top-10 problem! Transport Layer 3-87

Causes/costs of congestion: scenario 1 two senders, two receivers Host A l in : original data l out one router, infinite buffers Host B unlimited shared output link buffers no retransmission large delays when congested 라우터에서의 queueing delay 때문에 delay 는무한대로늘어난다 Max. achieavable throughput Transport Layer 3-88

Causes/costs of congestion: scenario 2 one router, finite buffers sender retransmission of lost packet Host A l in : original data l' in : original data, plus retransmitted data l out Host B finite shared output link buffers Transport Layer 3-89

Causes/costs of congestion: scenario 2 always: l = in l out (goodput) R/2 Case a: No loss인경우, 손실되는용량은없다 (TH=offered load) Case b: lost된경우만재전송, 1/3 트래픽용량은재전송에사용 (TH=0.67 offered load) Case c: case b에 timer expire되어재전송되는경우도추가, TH=0.5 offered load( 매패킷마다두번씩전송하는경우 ) R/2 R/2 R/3 l out l out l out R/4 l in R/2 l in R/2 l in R/2 a. b. c. costs of congestion: more work (retrans) for given goodput unneeded retransmissions: link carries multiple copies of pkt Transport Layer 3-90

Causes/costs of congestion: scenario 3 가정 : 4 개의 sender, 유한버퍼의라우터, 멀티홉경로존재하는경우 A-C 트래픽과 B-D 트래픽은모두라우터 2 를거쳐야함. 이때 B- D 트래픽이매우커지면 A- C 트래픽은매우작아진다. 이렇게되면 R1 을통과했던 A-C 트래픽용량이얼마인가는무의미해짐. 즉, R1 이처리했던일이무의미해짐 (waste 됨 ) Transport Layer 3-91

Causes/costs of congestion: scenario 3 H o s t A l o u t H o s t B cost of congestion: when packet dropped, any upstream transmission capacity used for that packet was wasted! (eg. work done in R1 is wasted) Transport Layer 3-92

Approaches towards congestion control Two broad approaches towards congestion control: End-end congestion control: 네트웍층이트랜스포트층에서의 congestion control 을전혀지원하지않는경우 no explicit feedback from network equipment end-system 에서관찰된 loss, delay 등의파라메타만가지고판단해야함 approach taken by TCP Network-assisted congestion control: routers provide feedback to end systems single bit indicating congestion (SNA, DECbit, TCP/IP ECN, ATM) ATM ABR congestion control: 라우터가자신의출력링크속도 (rate) 가얼마까지가능한지를 sender 에게알려줌 Transport Layer 3-93

Case study: ATM ABR congestion control ABR: available bit rate: elastic service if sender s path underloaded : sender should use available bandwidth if sender s path congested: sender throttled to predetermined minimum transmission rate RM (resource management) cells: 1 RM셀은일반적으로 source가만들어서데이터셀중간중간에넣으며 (32개데이터셀마다한개의 RM셀 ), dest. 까지왔을때 dest가 source로변형없이그대로 feedback 시킨다. Congestion 발생시 switch가지나가는 RM cell에표시 ( network-assisted ) NI bit: no increase in rate (mild congestion) CI bit: congestion indication Switch 는 RM 셀을직접만들어서 source 로보낼수도있다 Transport Layer 3-94

Case study: ATM ABR congestion control 2 3 two-byte ER (explicit rate) field in RM cell congested switch may lower ER value in cell Sender는이값으로전송 rate를낮춤 Congestion 발생시스위치는데이터셀의 EFCI bit를 1로표시 if data cell preceding RM cell has EFCI set, destination sets CI bit in returned RM cell to source Transport Layer 3-96

TCP Congestion control Algorithm 시작은 slow start CongWin이 Threshold값에도달하면 AIMD 가동 Timeout event 발생하면, Threshold 값을 CongWin의 ½ 로하고 slow start 다시시작 3-duplicate ACK 수신되는 event가발생하면, Threshold 값을 CongWin의 ½ 로하고, CongWin의값은이새로운 Threshold값으로하고 AIMD 가동 Transport Layer 3-98

TCP Congestion Control end-end control (no network assistance) sender limits transmission: LastByteSent-LastByteAcked min{congwin,rcvwindow} Roughly, sender s send rate rate = CongWin RTT Bytes/sec CongWin is dynamic, function of perceived network congestion Sender 가 congestion 발생을감지하는메커니즘 : loss event 감지 timeout 발생 3 duplicate acks 수신 TCP sender reduces rate (CongWin) after loss event three mechanisms: AIMD slow start threshold Transport Layer 3-99

TCP Congestion Control Sender 는 ACK 수신의의미를어떻게해석하나? 전송이잘된다고보고 CongWin 크기를증가시킴 즉, ACK 가느리게오면 CongWin 크기증가도느려짐 ACK 가빨리오면 CongWin 크기증가도빨라짐 따라서 TCP 는 self-clocking 이라고함 Transport Layer 3-100

TCP AIMD(additive-increase, multiplicative decrease) 24 Kbytes 16 Kbytes 8 Kbytes multiplicative decrease: loss event 발생시 CongWin 값을 ½ 로줄임 ( 최소값은 1 MSS) congestion window Saw-toothed pattern 을나타냄 Long-lived TCP connection additive increase: ACK 받을시 CongWin 값을 linear 하게증가시킴 Congestion avoidance 라고도함 time loss event 가없을때, CongWin 값을 RTT 마다 1 MSS 씩증가시키는것이목표 loss event 가없을때, ACK 를받을때마다 CongWin 값을매 (MSS/CongWin) MSS 만큼증가시킴 MSS=1460 bytes, CongWin=14600 bytes 이고 RTT 내에 10 개의세그멘트를전송했을때, 매 ACK 수신시 CongWin 을 1/10 MSS 증가 Transport Layer 3-101

TCP Slow Start 이름의의미 시작은느리지만증가는빠르게시킴 처음시작시 CongWin 크기가작은값에서 ( 즉, 1 MSS) 시작한다는의미 동작 1 TCP 연결시작시 CongWin =1 MSS로 setting 2 RTT마다 CongWin 크기를 2배씩증가시킴 ( 즉, 1,2,4,8 ) 처음에 1MSS의한세그먼트를보내고, loss event가발생하기전에 ACK가오면 CongWin 를 1MSS 만큼증가시키고 (CongWin = 2MSS가됨 ) 두개의최대크기세그먼트를전송. 이세그먼트들에대해 loss가발생하기전에오는 ACK마다 CongWin를 1MSS만큼증가시킴 ( 두개에대해서다오면 CongWin=4MSS) 그리고 4개의최대크기세그먼트를전송 exponential increase of rate 3 Loss event가발생하면 2배씩증가를멈추고 loss event시취해야할동작을함 Timeout 발생시 : Slow start 재시작 3개의중복 ACK수신시 : AIMD Transport Layer 3-102

RTT TCP Slow Start (more) When connection begins, increase rate exponentially until first loss event: double CongWin every RTT Host A Host B done by incrementing CongWin for every ACK received Summary: initial rate is slow but ramps up exponentially fast time Transport Layer 3-103

Threshold Threshold Slow start 에서 congestion avoidance 로넘어가는경계를정의하는수단 초기값은큰값으로정하고 (65Kbytes in practice), loss event 발생시마다현재 CongWin 값의 ½ 로정함 Transport Layer 3-104

TCP Tahoe & Reno TCP Tahoe Loss event 발생시무조건 slow start 가동 TCP Reno Loss event 중에서도 Timeout 이냐 3-dup. ACK 냐에따라다르게작동 Timeout 일때 : Slow start 가동 3-dup. ACK 일때 : AIMD 가동 이유 : ACK 가온다는것은 congestion 이있다하더라도트래픽이어느정도는왔다갔다할수있는상황으로판단할수있으므로 slow start 를하지않음 3-dup. ACK 시 slow start 를하지않는것을 fast recovery 라함 Transport Layer 3-105

예 3-dup. ACK 발생시의 Tahoe 와 Reno 의예 초기 CongWin=12MSS, Th=8MSS 3-dup. ACK 발생 TCP taho 동작 ( 즉, loss event 발생시무조건 slow start) Th 값은현재 CongWin 0.5=6MSS 로 setting Transport Layer 3-106

Summary: TCP Congestion Control When CongWin is below Threshold, sender in slow-start phase, window grows exponentially. When CongWin is above Threshold, sender is in congestion-avoidance phase, window grows linearly. When a triple duplicate ACK occurs, Threshold set to CongWin/2 and CongWin set to Threshold. When timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS. Transport Layer 3-107

TCP sender congestion control State Event TCP Sender Action Commentary Slow Start (SS) Congestion Avoidance (CA) SS or CA ACK receipt for previously unacked data ACK receipt for previously unacked data Loss event detected by triple duplicate ACK CongWin = CongWin + MSS, If (CongWin > Threshold) set state to Congestion Avoidance CongWin = CongWin+MSS * (MSS/CongWin) Threshold = CongWin/2, CongWin = Threshold, Set state to Congestion Avoidance SS or CA Timeout Threshold = CongWin/2, CongWin = 1 MSS, Set state to Slow Start SS or CA Duplicate ACK Increment duplicate ACK count for segment being acked Resulting in a doubling of CongWin every RTT Additive increase, resulting in increase of CongWin by 1 MSS every RTT Fast recovery, implementing multiplicative decrease. CongWin will not drop below 1 MSS. Enter slow start CongWin and Threshold not changed Transport Layer 3-108

TCP throughput What s the average throughout of TCP as a function of window size and RTT? Ignore slow start Let W be the window size when loss occurs. When window is W, throughput is W/RTT Just after loss, window drops to W/2, throughput to W/2RTT. Average throughout:.75 W/RTT Transport Layer 3-109

TCP Futures Example: 1500 byte segments, 100ms RTT, want 10 Gbps throughput Requires window size W = 83,333 in-flight segments 0.75WS/RTT=10Gbps Avg. throughput in terms of loss rate L: 1.22 MSS RTT L 10Gbps throughput을위해서, loss rate L은 2 10-10 이되어야함Wow! high speed environment를위해서는 TCP의 new version필요 1.22 1500bytes 10Gbits / s 100ms L Transport Layer 3-110

TCP Fairness Fairness goal: if K TCP sessions share same bottleneck link of bandwidth R, each should have average rate of R/K TCP connection 1 TCP connection 2 bottleneck router capacity R Transport Layer 3-111

경로공유시 Throughput 패턴 Two competing sessions: 두연결에의해소모된 BW 가 R 이되는 line: 이선보다아래쪽에있으면 loss event 가발생안하고, 위에있으면 loss 발생 Additive increase gives slope of 1, as throughput increases multiplicative decrease decreases throughput proportionally R equal bandwidth share Loss 발생 : decrease window by factor of 2 congestion avoidance: additive increase 출발 Connection 1 throughput R Loss 발생 : decrease window by factor of 2 congestion avoidance: additive increase Transport Layer 3-112

Fairness (more) Fairness and UDP Multimedia apps often do not use TCP do not want rate throttled by congestion control Instead use UDP: pump audio/video at constant rate, tolerate packet loss Research area: TCP friendly Fairness and parallel TCP connections nothing prevents app from opening parallel connections between 2 hosts. Web browsers do this Example: link of rate R supporting 9 connections; new app asks for 1 TCP, gets rate R/10 new app asks for 11 TCPs, gets R/2! Transport Layer 3-113

Chapter 3: Summary principles behind transport layer services: multiplexing, demultiplexing reliable data transfer flow control congestion control instantiation and implementation in the Internet UDP TCP Next: leaving the network edge (application, transport layers) into the network core Transport Layer 3-114