计算机网络-自顶向下方法与INTERNET特色.ppt

1、Computer Networking A Top-Down Approach Featuring the Internet计算机网络-自顶向下方法与Internet特色,Chapter3 Transport Layer,Chapter 3: Transport Layer,Our goals: understand principles behind transport layer services: multiplexing/demultiplexing reliable data transfer flow control congestion control,learn about t

2、ransport layer protocols in the Internet: UDP: connectionless transport TCP: connection-oriented transport TCP congestion control,Chapter 3 Roadmap,3.1 Introduction and Transport-layer services 3.2 Multiplexing and Demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data tran

3、sfer 3.5 Connection-oriented transport: TCP 3.6 Principles of congestion control 3.7 TCP congestion control 3.8 Summary,Introduction,Transport layer protocol provides for logical communication between app processes running on different hosts. From an applications perspective, it is as if the hosts r

4、unning the processes were directly connected In reality, the hosts may be connected via numerous routers and a wide range of link types.,3.1 Introduction and Transport-Layer Services,Introduction,3.1 Introduction and Transport-Layer Services,transport protocols run in end systems send side: breaks a

5、pp messages into segments, passes to network layer rcv side: reassembles segments into messages, passes to app layer Internet provides two transport services for apps TCP and UDP,Introduction,3.1 Introduction and Transport-Layer Services,network layer logical communication between hosts transport la

6、yer logical communication between processes relies on and enhances network layer services,Transport vs. Network Layer,3.1 Introduction and Transport-Layer Services,Household analogy: 12 kids sending letters to each of 12 kids in another family app messages = letters in envelopes transport protocol =

7、 Ann and Bill network-layer protocol = postal service hosts = houses processes = kids,Transport vs. Network Layer,3.1 Introduction and Transport-Layer Services,Application developer must specify one of the two transport services. TCP reliable, in-order, connection-oriented delivery congestion contro

8、l flow control UDP unreliable, unordered , connectionless delivery no-frills extension of “best-effort” IP,3.1 Introduction and Transport-Layer Services,Internet transport-layer protocols,IPs service model is a best-effort service IP makes its best-effort to deliver segments between hosts, but it ma

9、kes no guarantees. Transport protocols extend IPs delivery service between two hosts to delivery service between two processes. transport-layer multiplexing SMTP:25,3.2 Multiplexing and Demultiplexing,A UDP socket is fully identified by a two-tuple: When host receives UDP segment: checks destination

10、 port number in the segment directs UDP segment to socket with that port number demultiplexing,Connectionless demultiplexing,3.2 Multiplexing and Demultiplexing,Connectionless demux (cont),P3: DatagramSocket serverSocket = new DatagramSocket(6428);,segments with different source IP addresses and/or

11、source port numbers directed to same socket,Connection-Oriented demultiplexing,TCP socket identified by a four-tuple recv host uses all four values to direct segment to appropriate socket,ServerSocket welcomeSocket=new ServerSocket(PNum); Socket connectionSocket =welcomeScoekt.Accept();,3.2 Multiple

12、xing and Demultiplexing,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,Connection-Oriented demultiplexing,3.2 Multiplexing a

13、nd Demultiplexing,Web Server and TCP,3.2 Multiplexing no loss of packets; in-order . separate FSM for sender, receiver sender sends data into underlying channel receiver read data from underlying channel,3.4 Principles of Reliable Data Transfer,Sender accepts data from app via rdt_send(data) event a

14、ction: creates a packet containing the data: make_pkt(data) sends the packet into the channel: udt_send(packet) Receiver receives a packet from channel via rdt_rcv(packet) event action: extracts data from the packet : extract(packet, data) passes the data to upper : deliver_data(data),1.1 reliable t

15、ransfer over a perfectly reliable channel: rdt1.0,3.4 Principles of Reliable Data Transfer,a packet may be corrupted, but no loss however. How should rdt do to handle corrupted pkts? Who should be responsible for checking the possible error in the packet(s)? receiver checks if there is a error in th

16、e received pkt sender must adds extra bits in packet How to handle the error? receiver informs the sender sender retransmits the corrupted packet,1.2 reliable transfer over a channel with bit errors: rdt2.0,3.4 Principles of Reliable Data Transfer,Reliable data transfer protocols based on such retra

17、nsmission are Automatic Repeat reQuest (ARQ) protocols Error detection feedback positive acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK negative acknowledgements (NAKs): receiver explicitly tells sender that pkt has errors Retransmission,1.2 reliable transfer over a c

18、hannel with bit errors: rdt2.0,3.4 Principles of Reliable Data Transfer,rdt2.0 : FSM specification,sndpkt = make_pkt(data, checksum) udt_send(sndpkt),rdt_rcv(rcvpkt) y= 73, so the rcvrwants 73+ ;y SendBase, sothat new data is acked,4.1 TCP: retransmission scenarios,Host A,Seq=100, 20 bytes data,ACK=

19、100,2) premature timeout,Host B,Seq=92, 8 bytes data,ACK=120,Seq=92, 8 bytes data,ACK=120,Host A,Seq=92, 8 bytes data,ACK=100,loss,timeout,1) lost ACK scenario duplicated segment,Host B,X,Seq=92, 8 bytes data,ACK=100,time,Seq=92 timeout,SendBase = 100,SendBase= 120,SendBase = 120,Sendbase= 100,4.1 T

20、CP retransmission scenarios,Host A,Seq=92, 8 bytes data,ACK=100,loss,timeout,3) Cumulative ACK scenario,Host B,X,Seq=100, 20 bytes data,ACK=120,time,SendBase = 120,4.2 Doubling the timeout interval,timeout event retransmits the not yet acknowledged segment with the smallest seq #. set timeout interv

21、al to twice the previous value rather than deriving it from last EstimatedRTT and DevRTT limited form of congestion control slow down the senders rate rather than retransmit packets persistently,3.5 Connection-Oriented Transport Service : TCP,4.3 Fast Retransmit,Time-out period often relatively long

22、: long delay before resending lost packet Detect lost segments via duplicate ACKs. Sender often sends many segments back-to-back If segment is lost, there will likely be many duplicate ACKs.,3.5 Connection-Oriented Transport Service : TCP,TCP ACK Generation RFC 1122, RFC 2581,Event at Receiver Arriv

23、al 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

24、,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 en

25、d of gap,4.3 Fast Retransmit,3.5 Connection-Oriented Transport Service : TCP,If sender receives 3 ACKs for a same segment, it supposes that the segment after the ACKed segment was lost: fast retransmit: resends the segment before timer expires,event: ACK received, with ACK field value of y if (y Sen

26、dBase) 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,4.3 Fast Retransmit,3.5 Co

27、nnection-Oriented Transport Service : TCP,4.4 TCP is GBN or SR?,sender only maintain Send_Base, NextSeqNum and receiver adopts cumulative ACK TCP looks like a GBN protocol Differences between TCP and GBN most TCP receivers buffering the out-of-order segment sender only retransmits segment: send_base

28、 when timeout sender doesnt retransmit segment n if the ack of segment n+1 arrived before the timeout of segment n.,3.5 Connection-Oriented Transport Service : TCP,RFC2018 (SACK)-selective acknowledgment： Receiver selectively ACKs the out-of-order segments Sender selectively retransmits the segment

29、except the ACKed segment Looks like SR TCPs error-recovery mechanism is a hybrid of GBN and SR,4.4 TCP is GBN or SR?,3.5 Connection-Oriented Transport Service : TCP,5. Flow Control,receive has a receive buffer:,app process may be slow at reading from the buffer than the sending rate of sender,3.5 Co

30、nnection-Oriented Transport Service : TCP,speed-matching service matching the sending rate to the receiving apps draining rate sender maintains a variable called receive window to indicate how much free buffer space available at the receiver.,5. Flow Control,3.5 Connection-Oriented Transport Service

31、 : TCP,spare room in receivers buffer RcvWindow = RcvBuffer-LastByteRcvd - LastByteRead,3.5 Connection-Oriented Transport Service : TCP,5. TCP Flow control: how it works?,receiver advertises the size of spare room in buffer by including RcvWindow in the segments header. Sender limits unACKed data to

32、 RcvWindow A problem: If a host A advertises to B that RcvWindow is 0, B can not send any data to A even when A empty the buffer some time later. TCPs specification requires A to continue to send one-byte data segment to B when Rcv_Window =0.,3.5 Connection-Oriented Transport Service : TCP,5. TCP Fl

33、ow control: how it works?,6. TCP Connection Management,Recall: TCP must establish “connection” before exchanging data. initialize seq. #s , buffers, flow control info (e.g. RcvWindow) initiated by the client socket clientSocket = new Socket( host, port); socket connectionSocket = welcomeSocket.accep

34、t();,3.5 Connection-Oriented Transport Service : TCP,6.1 TCP Connection Management,Step 1: client sends SYN segment (S=1, no data) initial seq # is randomly chosen: client_isn Step 2: server replies with SYNACK segment (S=1,A=1, no data) allocates buffers and variables Acknowledgment= client_isn + 1

35、 randomly chooses the seq.#: server_isn Step 3: client replies with ACK segment, which may contain data (piggyback) client allocates buffers and variables A=1 Acknowledgment= server_isn+1,3.5 Connection-Oriented Transport Service : TCP,6.1 TCP Connection Management,Step 1: client sends a FIN segment

36、 Step 2: server replies with a ACK and a FIN segment. Step 3: client replies with a ACK segment. enters “timed wait” - will respond with ACK to received FINs Typically 30s Step 4: server receives ACK. The connection is closed.,3.5 Connection-Oriented Transport Service : TCP,6.2 Close a Connection,6.

37、3 TCP Connection Management,TCP client lifecycle,TCP server lifecycle,3.5 Connection-Oriented Transport - TCP,Connection-oriented point-to-point and full-duplex allocate buffers and variables, initializes the sequence number TCP segment structure RTT estimation and Timeout reliable data transfer dou

38、ble timeout interval fast retransmit a hybrid of GBN and SR flow control connection management,Chapter 3 Roadmap,3.1 Introduction and Transport-layer services 3.2 Multiplexing and Demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transp

39、ort: TCP 3.6 Principles of congestion control 3.7 TCP congestion control 3.8 Summary,Introduction,Whats congestion? informally: “too many sources sending too much data too fast for network to handle” quite different from flow control! congestion manifestations: lost packets (buffer overflow at route

40、rs) long delays (queueing in router buffers) a top-10 problem!,3.6 Principles of congestion control,6.1.1 Causes/costs of congestion: scenario 1,two senders, two receivers in one router, infinite buffers link capacity: C Suppose : no retransmission,large delays when congested maximum achievable thro

41、ughput,1.2 Causes/costs of congestion: scenario 2,one router, finite buffers sender retransmits lost packets,finite shared buffers,Host A,lin : original data,Host B,lout,lin : original plus retransmitted data,3.6 Principles of congestion control,a- no packet lost ： in=out b- “perfect” retransmission

42、 only when loss: in out c- retransmit delayed (not lost) packet： in larger than perfect case for same out .,“costs” of congestion: more work (retrans) for given “goodput” unneeded retransmissions,R/2,R/2,lout,b.,R/2,R/2,lout,a.,R/2,R/2,lout,c.,R/4,R/3,3.6 Principles of congestion control,1.2 Causes/

43、costs of congestion: scenario 2,four senders multi-hop paths timeout/retransmit,Q: what happens as in and in increase ?,finite shared output link buffers,lin : original data,lout,lin : original data, plus retransmitted data,Host D,Host C,3.6 Principles of congestion control,1.3 Causes/costs of conge

44、stion: scenario 3,Another “cost” of congestion: when packet dropped, any “upstream” transmission capacity used for that packet was wasted!,R2,R1,R3,R4,A,B,C,D,3.6 Principles of congestion control,1.3 Causes/costs of congestion: scenario 3,2. Approaches to Congestion Control,approaches to congestion

45、control End-to-End congestion control no explicit feedback from network congestion inferred from end-system observed loss, delay network-assisted congestion control routers provide feedback to end systems single bit indicating congestion (SNA, DECbit, ECN, ATM) explicit rate sender should send at,3.

46、6 Principles of congestion control,Chapter 3 Roadmap,3.1 Introduction and 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 3.6 Principles of congestion control 3.7 TCP conges

47、tion control 3.8 Summary,Introduction,TCP has each sender limit sending rate as a function of perceived congestion How does a sender perceive that network is in congestion? How does a sender limit sending rate? What algorithm should the sender use to change its sending rate as a function of congesti

48、on?,3.7 TCP Congestion Control,sender limits transmission: LastByteSent-LastByteAcked minCongWin,RcvWin RcvWin CongWin LastByteSent-LastByteAcked CongWin Roughly, CongWin is dynamic, function of perceived network congestion,1. How to Limit Send Rate?,3.7 TCP Congestion Control,2. How to Conceive the

49、 Congestion?,Retransmission indicates congestion loss event = timeout or 3-duplicate ACKs TCP sender reduces sending rate (CongWin) after loss event,3.7 TCP Congestion Control,3. Algorithm of Changing Send Rate,ACKs arrival indicates the network is OK increase the sending rate by increasing the Cong

50、Win Timeout or 3 duplicate ACKs decrease the sending rate by reducing the CongWin Congestion Control Algorithm AIMD Additive Increase, Multiplicative Decrease slow start reaction to timeout events,3.7 TCP Congestion Control,4. AIMD (1),multiplicative decrease: cut CongWin in half after loss event Co

51、ngWin = CongWin/2, but CongWin should always =1MSS additive increase: increase CongWin by 1 MSS every a RTT period probing：one ACK, CongWin increase MSS2/CongWin (bytes) Congestion Avoidance phase,3.7 TCP Congestion Control,Long-lived TCP connection,4. AIMD (2),3.7 TCP Congestion Control,5. Slow Sta

52、rt,When connection begins, CongWin = 1 MSS Example: MSS = 500 bytes window then grows exponentially （Slow Start) to a threshold, then grows linearly (AIMD) threshold=CongWin/2,3.7 TCP Congestion Control,Threshold determines the CongWin at which slow start will end and congestion avoidance will begin

53、. Threshold initially set to a large value Loss event occurs, threshold = CongWin/2 Timeout: CongWin = 1 MSS slow start until reaches Threshold, then congestion avoidance 3DupACKs Threshold=CongWin/2; CongWin=Threshold Increase linearly（congestion avoidance） Canceling of the slow-start phase after 3

54、-dup ACKs is called fast recovery,3.7 TCP Congestion Control,6. Reaction to Timeout Events,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 l

55、inearly. 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.,3.7 TCP Congestion Control,TCP sender congestion control,3.7 TCP Congestion Control,6. Reaction to Timeout Events,RTT,Ign

56、oring the slow start, Whats the average throughout of TCP as a function of window size and RTT? Let W be the window size when loss occurs. When window size is W, throughput is W/RTT Just after loss, window drops to W/2, throughput to W/2RTT. Average throughout: 0.75 W/RTT,3.7 TCP Congestion Control,

57、7. TCP Throughput,Consider a TCP connection with 1500-byte MSS and a 100ms RTT, and we want to send data through this connection at 10 Gbps throughput = W*MSS*8/RTT, then W=throughput*RTT/(MSS*8) throughput=10Gbps, then W=83,333,8. TCP Futures,3.7 TCP Congestion Control,throughput in terms of loss r

58、ate CongWin increase from W/2 to W, total pkts number: W/2+(W/2+1)+(W/2+2)+.+W = 3W2/8+3W/4 if W is large, then 3W2/83W/4, so L 8/(3W2) L = 210-10 Wow! new versions of TCP for high-speed needed!,8. TCP Futures,3.7 TCP Congestion Control,fairness goal: if K TCP sessions share same bottleneck link of

59、bandwidth R, each should have average rate of R/K,3.7 TCP Congestion Control,9. TCP Fairness,R,R,equal bandwidth share,Connection 1 throughput,Connection 2 throughput,congestion avoidance: additive increase,loss: decrease window by factor of 2,congestion avoidance: additive increase,loss: decrease window by factor of 2,3.7 TCP Congestion Control,9. TCP Fairness,multimed